LXR uboot/lib/crc32.c

   1/*
   2 * This file is derived from crc32.c from the zlib-1.1.3 distribution
   3 * by Jean-loup Gailly and Mark Adler.
   4 */
   5
   6/* crc32.c -- compute the CRC-32 of a data stream
   7 * Copyright (C) 1995-1998 Mark Adler
   8 * For conditions of distribution and use, see copyright notice in zlib.h
   9 */
  10
  11#ifdef USE_HOSTCC
  12#include <arpa/inet.h>
  13#else
  14#include <common.h>
  15#endif
  16#include <compiler.h>
  17#include <u-boot/crc.h>
  18
  19#if defined(CONFIG_HW_WATCHDOG) || defined(CONFIG_WATCHDOG)
  20#include <watchdog.h>
  21#endif
  22#include "u-boot/zlib.h"
  23
  24#define local static
  25#define ZEXPORT /* empty */
  26
  27#define tole(x) cpu_to_le32(x)
  28
  29#ifdef DYNAMIC_CRC_TABLE
  30
  31local int crc_table_empty = 1;
  32local uint32_t crc_table[256];
  33local void make_crc_table OF((void));
  34
  35/*
  36  Generate a table for a byte-wise 32-bit CRC calculation on the polynomial:
  37  x^32+x^26+x^23+x^22+x^16+x^12+x^11+x^10+x^8+x^7+x^5+x^4+x^2+x+1.
  38
  39  Polynomials over GF(2) are represented in binary, one bit per coefficient,
  40  with the lowest powers in the most significant bit.  Then adding polynomials
  41  is just exclusive-or, and multiplying a polynomial by x is a right shift by
  42  one.  If we call the above polynomial p, and represent a byte as the
  43  polynomial q, also with the lowest power in the most significant bit (so the
  44  byte 0xb1 is the polynomial x^7+x^3+x+1), then the CRC is (q*x^32) mod p,
  45  where a mod b means the remainder after dividing a by b.
  46
  47  This calculation is done using the shift-register method of multiplying and
  48  taking the remainder.  The register is initialized to zero, and for each
  49  incoming bit, x^32 is added mod p to the register if the bit is a one (where
  50  x^32 mod p is p+x^32 = x^26+...+1), and the register is multiplied mod p by
  51  x (which is shifting right by one and adding x^32 mod p if the bit shifted
  52  out is a one).  We start with the highest power (least significant bit) of
  53  q and repeat for all eight bits of q.
  54
  55  The table is simply the CRC of all possible eight bit values.  This is all
  56  the information needed to generate CRC's on data a byte at a time for all
  57  combinations of CRC register values and incoming bytes.
  58*/
  59local void make_crc_table()
  60{
  61  uint32_t c;
  62  int n, k;
  63  uLong poly;           /* polynomial exclusive-or pattern */
  64  /* terms of polynomial defining this crc (except x^32): */
  65  static const Byte p[] = {0,1,2,4,5,7,8,10,11,12,16,22,23,26};
  66
  67  /* make exclusive-or pattern from polynomial (0xedb88320L) */
  68  poly = 0L;
  69  for (n = 0; n < sizeof(p)/sizeof(Byte); n++)
  70    poly |= 1L << (31 - p[n]);
  71
  72  for (n = 0; n < 256; n++)
  73  {
  74    c = (uLong)n;
  75    for (k = 0; k < 8; k++)
  76      c = c & 1 ? poly ^ (c >> 1) : c >> 1;
  77    crc_table[n] = tole(c);
  78  }
  79  crc_table_empty = 0;
  80}
  81#else
  82/* ========================================================================
  83 * Table of CRC-32's of all single-byte values (made by make_crc_table)
  84 */
  85
  86local const uint32_t crc_table[256] = {
  87tole(0x00000000L), tole(0x77073096L), tole(0xee0e612cL), tole(0x990951baL),
  88tole(0x076dc419L), tole(0x706af48fL), tole(0xe963a535L), tole(0x9e6495a3L),
  89tole(0x0edb8832L), tole(0x79dcb8a4L), tole(0xe0d5e91eL), tole(0x97d2d988L),
  90tole(0x09b64c2bL), tole(0x7eb17cbdL), tole(0xe7b82d07L), tole(0x90bf1d91L),
  91tole(0x1db71064L), tole(0x6ab020f2L), tole(0xf3b97148L), tole(0x84be41deL),
  92tole(0x1adad47dL), tole(0x6ddde4ebL), tole(0xf4d4b551L), tole(0x83d385c7L),
  93tole(0x136c9856L), tole(0x646ba8c0L), tole(0xfd62f97aL), tole(0x8a65c9ecL),
  94tole(0x14015c4fL), tole(0x63066cd9L), tole(0xfa0f3d63L), tole(0x8d080df5L),
  95tole(0x3b6e20c8L), tole(0x4c69105eL), tole(0xd56041e4L), tole(0xa2677172L),
  96tole(0x3c03e4d1L), tole(0x4b04d447L), tole(0xd20d85fdL), tole(0xa50ab56bL),
  97tole(0x35b5a8faL), tole(0x42b2986cL), tole(0xdbbbc9d6L), tole(0xacbcf940L),
  98tole(0x32d86ce3L), tole(0x45df5c75L), tole(0xdcd60dcfL), tole(0xabd13d59L),
  99tole(0x26d930acL), tole(0x51de003aL), tole(0xc8d75180L), tole(0xbfd06116L),
 100tole(0x21b4f4b5L), tole(0x56b3c423L), tole(0xcfba9599L), tole(0xb8bda50fL),
 101tole(0x2802b89eL), tole(0x5f058808L), tole(0xc60cd9b2L), tole(0xb10be924L),
 102tole(0x2f6f7c87L), tole(0x58684c11L), tole(0xc1611dabL), tole(0xb6662d3dL),
 103tole(0x76dc4190L), tole(0x01db7106L), tole(0x98d220bcL), tole(0xefd5102aL),
 104tole(0x71b18589L), tole(0x06b6b51fL), tole(0x9fbfe4a5L), tole(0xe8b8d433L),
 105tole(0x7807c9a2L), tole(0x0f00f934L), tole(0x9609a88eL), tole(0xe10e9818L),
 106tole(0x7f6a0dbbL), tole(0x086d3d2dL), tole(0x91646c97L), tole(0xe6635c01L),
 107tole(0x6b6b51f4L), tole(0x1c6c6162L), tole(0x856530d8L), tole(0xf262004eL),
 108tole(0x6c0695edL), tole(0x1b01a57bL), tole(0x8208f4c1L), tole(0xf50fc457L),
 109tole(0x65b0d9c6L), tole(0x12b7e950L), tole(0x8bbeb8eaL), tole(0xfcb9887cL),
 110tole(0x62dd1ddfL), tole(0x15da2d49L), tole(0x8cd37cf3L), tole(0xfbd44c65L),
 111tole(0x4db26158L), tole(0x3ab551ceL), tole(0xa3bc0074L), tole(0xd4bb30e2L),
 112tole(0x4adfa541L), tole(0x3dd895d7L), tole(0xa4d1c46dL), tole(0xd3d6f4fbL),
 113tole(0x4369e96aL), tole(0x346ed9fcL), tole(0xad678846L), tole(0xda60b8d0L),
 114tole(0x44042d73L), tole(0x33031de5L), tole(0xaa0a4c5fL), tole(0xdd0d7cc9L),
 115tole(0x5005713cL), tole(0x270241aaL), tole(0xbe0b1010L), tole(0xc90c2086L),
 116tole(0x5768b525L), tole(0x206f85b3L), tole(0xb966d409L), tole(0xce61e49fL),
 117tole(0x5edef90eL), tole(0x29d9c998L), tole(0xb0d09822L), tole(0xc7d7a8b4L),
 118tole(0x59b33d17L), tole(0x2eb40d81L), tole(0xb7bd5c3bL), tole(0xc0ba6cadL),
 119tole(0xedb88320L), tole(0x9abfb3b6L), tole(0x03b6e20cL), tole(0x74b1d29aL),
 120tole(0xead54739L), tole(0x9dd277afL), tole(0x04db2615L), tole(0x73dc1683L),
 121tole(0xe3630b12L), tole(0x94643b84L), tole(0x0d6d6a3eL), tole(0x7a6a5aa8L),
 122tole(0xe40ecf0bL), tole(0x9309ff9dL), tole(0x0a00ae27L), tole(0x7d079eb1L),
 123tole(0xf00f9344L), tole(0x8708a3d2L), tole(0x1e01f268L), tole(0x6906c2feL),
 124tole(0xf762575dL), tole(0x806567cbL), tole(0x196c3671L), tole(0x6e6b06e7L),
 125tole(0xfed41b76L), tole(0x89d32be0L), tole(0x10da7a5aL), tole(0x67dd4accL),
 126tole(0xf9b9df6fL), tole(0x8ebeeff9L), tole(0x17b7be43L), tole(0x60b08ed5L),
 127tole(0xd6d6a3e8L), tole(0xa1d1937eL), tole(0x38d8c2c4L), tole(0x4fdff252L),
 128tole(0xd1bb67f1L), tole(0xa6bc5767L), tole(0x3fb506ddL), tole(0x48b2364bL),
 129tole(0xd80d2bdaL), tole(0xaf0a1b4cL), tole(0x36034af6L), tole(0x41047a60L),
 130tole(0xdf60efc3L), tole(0xa867df55L), tole(0x316e8eefL), tole(0x4669be79L),
 131tole(0xcb61b38cL), tole(0xbc66831aL), tole(0x256fd2a0L), tole(0x5268e236L),
 132tole(0xcc0c7795L), tole(0xbb0b4703L), tole(0x220216b9L), tole(0x5505262fL),
 133tole(0xc5ba3bbeL), tole(0xb2bd0b28L), tole(0x2bb45a92L), tole(0x5cb36a04L),
 134tole(0xc2d7ffa7L), tole(0xb5d0cf31L), tole(0x2cd99e8bL), tole(0x5bdeae1dL),
 135tole(0x9b64c2b0L), tole(0xec63f226L), tole(0x756aa39cL), tole(0x026d930aL),
 136tole(0x9c0906a9L), tole(0xeb0e363fL), tole(0x72076785L), tole(0x05005713L),
 137tole(0x95bf4a82L), tole(0xe2b87a14L), tole(0x7bb12baeL), tole(0x0cb61b38L),
 138tole(0x92d28e9bL), tole(0xe5d5be0dL), tole(0x7cdcefb7L), tole(0x0bdbdf21L),
 139tole(0x86d3d2d4L), tole(0xf1d4e242L), tole(0x68ddb3f8L), tole(0x1fda836eL),
 140tole(0x81be16cdL), tole(0xf6b9265bL), tole(0x6fb077e1L), tole(0x18b74777L),
 141tole(0x88085ae6L), tole(0xff0f6a70L), tole(0x66063bcaL), tole(0x11010b5cL),
 142tole(0x8f659effL), tole(0xf862ae69L), tole(0x616bffd3L), tole(0x166ccf45L),
 143tole(0xa00ae278L), tole(0xd70dd2eeL), tole(0x4e048354L), tole(0x3903b3c2L),
 144tole(0xa7672661L), tole(0xd06016f7L), tole(0x4969474dL), tole(0x3e6e77dbL),
 145tole(0xaed16a4aL), tole(0xd9d65adcL), tole(0x40df0b66L), tole(0x37d83bf0L),
 146tole(0xa9bcae53L), tole(0xdebb9ec5L), tole(0x47b2cf7fL), tole(0x30b5ffe9L),
 147tole(0xbdbdf21cL), tole(0xcabac28aL), tole(0x53b39330L), tole(0x24b4a3a6L),
 148tole(0xbad03605L), tole(0xcdd70693L), tole(0x54de5729L), tole(0x23d967bfL),
 149tole(0xb3667a2eL), tole(0xc4614ab8L), tole(0x5d681b02L), tole(0x2a6f2b94L),
 150tole(0xb40bbe37L), tole(0xc30c8ea1L), tole(0x5a05df1bL), tole(0x2d02ef8dL)
 151};
 152#endif
 153
 154#if 0
 155/* =========================================================================
 156 * This function can be used by asm versions of crc32()
 157 */
 158const uint32_t * ZEXPORT get_crc_table()
 159{
 160#ifdef DYNAMIC_CRC_TABLE
 161  if (crc_table_empty) make_crc_table();
 162#endif
 163  return (const uint32_t *)crc_table;
 164}
 165#endif
 166
 167/* ========================================================================= */
 168# if __BYTE_ORDER == __LITTLE_ENDIAN
 169#  define DO_CRC(x) crc = tab[(crc ^ (x)) & 255] ^ (crc >> 8)
 170# else
 171#  define DO_CRC(x) crc = tab[((crc >> 24) ^ (x)) & 255] ^ (crc << 8)
 172# endif
 173
 174/* ========================================================================= */
 175
 176/* No ones complement version. JFFS2 (and other things ?)
 177 * don't use ones compliment in their CRC calculations.
 178 */
 179uint32_t ZEXPORT crc32_no_comp(uint32_t crc, const Bytef *buf, uInt len)
 180{
 181    const uint32_t *tab = crc_table;
 182    const uint32_t *b =(const uint32_t *)buf;
 183    size_t rem_len;
 184#ifdef DYNAMIC_CRC_TABLE
 185    if (crc_table_empty)
 186      make_crc_table();
 187#endif
 188    crc = cpu_to_le32(crc);
 189    /* Align it */
 190    if (((long)b) & 3 && len) {
 191         uint8_t *p = (uint8_t *)b;
 192         do {
 193              DO_CRC(*p++);
 194         } while ((--len) && ((long)p)&3);
 195         b = (uint32_t *)p;
 196    }
 197
 198    rem_len = len & 3;
 199    len = len >> 2;
 200    for (--b; len; --len) {
 201         /* load data 32 bits wide, xor data 32 bits wide. */
 202         crc ^= *++b; /* use pre increment for speed */
 203         DO_CRC(0);
 204         DO_CRC(0);
 205         DO_CRC(0);
 206         DO_CRC(0);
 207    }
 208    len = rem_len;
 209    /* And the last few bytes */
 210    if (len) {
 211         uint8_t *p = (uint8_t *)(b + 1) - 1;
 212         do {
 213              DO_CRC(*++p); /* use pre increment for speed */
 214         } while (--len);
 215    }
 216
 217    return le32_to_cpu(crc);
 218}
 219#undef DO_CRC
 220
 221uint32_t ZEXPORT crc32 (uint32_t crc, const Bytef *p, uInt len)
 222{
 223     return crc32_no_comp(crc ^ 0xffffffffL, p, len) ^ 0xffffffffL;
 224}
 225
 226/*
 227 * Calculate the crc32 checksum triggering the watchdog every 'chunk_sz' bytes
 228 * of input.
 229 */
 230uint32_t ZEXPORT crc32_wd (uint32_t crc,
 231                           const unsigned char *buf,
 232                           uInt len, uInt chunk_sz)
 233{
 234#if defined(CONFIG_HW_WATCHDOG) || defined(CONFIG_WATCHDOG)
 235        const unsigned char *end, *curr;
 236        int chunk;
 237
 238        curr = buf;
 239        end = buf + len;
 240        while (curr < end) {
 241                chunk = end - curr;
 242                if (chunk > chunk_sz)
 243                        chunk = chunk_sz;
 244                crc = crc32 (crc, curr, chunk);
 245                curr += chunk;
 246                WATCHDOG_RESET ();
 247        }
 248#else
 249        crc = crc32 (crc, buf, len);
 250#endif
 251
 252        return crc;
 253}
 254
 255void crc32_wd_buf(const unsigned char *input, unsigned int ilen,
 256                unsigned char *output, unsigned int chunk_sz)
 257{
 258        uint32_t crc;
 259
 260        crc = crc32_wd(0, input, ilen, chunk_sz);
 261        crc = htonl(crc);
 262        memcpy(output, &crc, sizeof(crc));
 263}
 264