Return to crc32.c CVS log

Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / sudo / zlib

1.8.7

    1: /* crc32.c -- compute the CRC-32 of a data stream
    2:  * Copyright (C) 1995-2006, 2010, 2011 Mark Adler
    3:  * For conditions of distribution and use, see copyright notice in zlib.h
    4:  *
    5:  * Thanks to Rodney Brown <rbrown64@csc.com.au> for his contribution of faster
    6:  * CRC methods: exclusive-oring 32 bits of data at a time, and pre-computing
    7:  * tables for updating the shift register in one step with three exclusive-ors
    8:  * instead of four steps with four exclusive-ors.  This results in about a
    9:  * factor of two increase in speed on a Power PC G4 (PPC7455) using gcc -O3.
   10:  */
   11: 
   12: /* @(#) $Id: crc32.c,v 1.1.1.2 2013/07/22 10:46:14 misho Exp $ */
   13: 
   14: /*
   15:   Note on the use of DYNAMIC_CRC_TABLE: there is no mutex or semaphore
   16:   protection on the static variables used to control the first-use generation
   17:   of the crc tables.  Therefore, if you #define DYNAMIC_CRC_TABLE, you should
   18:   first call get_crc_table() to initialize the tables before allowing more than
   19:   one thread to use crc32().
   20: 
   21:   DYNAMIC_CRC_TABLE and MAKECRCH can be #defined to write out crc32.h.
   22:  */
   23: 
   24: #ifdef MAKECRCH
   25: #  include <stdio.h>
   26: #  ifndef DYNAMIC_CRC_TABLE
   27: #    define DYNAMIC_CRC_TABLE
   28: #  endif /* !DYNAMIC_CRC_TABLE */
   29: #endif /* MAKECRCH */
   30: 
   31: #include "zutil.h"      /* for STDC and FAR definitions */
   32: 
   33: #define local static
   34: 
   35: /* Find a four-byte integer type for crc32_little() and crc32_big(). */
   36: #ifndef NOBYFOUR
   37: #  ifdef STDC           /* need ANSI C limits.h to determine sizes */
   38: #    include <limits.h>
   39: #    define BYFOUR
   40: #    if (UINT_MAX == 0xffffffffUL)
   41:        typedef unsigned int u4;
   42: #    else
   43: #      if (ULONG_MAX == 0xffffffffUL)
   44:          typedef unsigned long u4;
   45: #      else
   46: #        if (USHRT_MAX == 0xffffffffUL)
   47:            typedef unsigned short u4;
   48: #        else
   49: #          undef BYFOUR     /* can't find a four-byte integer type! */
   50: #        endif
   51: #      endif
   52: #    endif
   53: #  endif /* STDC */
   54: #endif /* !NOBYFOUR */
   55: 
   56: /* Definitions for doing the crc four data bytes at a time. */
   57: #ifdef BYFOUR
   58:    typedef u4 crc_table_t;
   59: #  define REV(w) ((((w)>>24)&0xff)+(((w)>>8)&0xff00)+ \
   60:                 (((w)&0xff00)<<8)+(((w)&0xff)<<24))
   61:    local unsigned long crc32_little OF((unsigned long,
   62:                         const unsigned char FAR *, unsigned));
   63:    local unsigned long crc32_big OF((unsigned long,
   64:                         const unsigned char FAR *, unsigned));
   65: #  define TBLS 8
   66: #else
   67:    typedef unsigned long crc_table_t;
   68: #  define TBLS 1
   69: #endif /* BYFOUR */
   70: 
   71: /* Local functions for crc concatenation */
   72: local unsigned long gf2_matrix_times OF((unsigned long *mat,
   73:                                          unsigned long vec));
   74: local void gf2_matrix_square OF((unsigned long *square, unsigned long *mat));
   75: local uLong crc32_combine_ OF((uLong crc1, uLong crc2, z_off64_t len2));
   76: 
   77: 
   78: #ifdef DYNAMIC_CRC_TABLE
   79: 
   80: local volatile int crc_table_empty = 1;
   81: local crc_table_t FAR crc_table[TBLS][256];
   82: local void make_crc_table OF((void));
   83: #ifdef MAKECRCH
   84:    local void write_table OF((FILE *, const crc_table_t FAR *));
   85: #endif /* MAKECRCH */
   86: /*
   87:   Generate tables for a byte-wise 32-bit CRC calculation on the polynomial:
   88:   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.
   89: 
   90:   Polynomials over GF(2) are represented in binary, one bit per coefficient,
   91:   with the lowest powers in the most significant bit.  Then adding polynomials
   92:   is just exclusive-or, and multiplying a polynomial by x is a right shift by
   93:   one.  If we call the above polynomial p, and represent a byte as the
   94:   polynomial q, also with the lowest power in the most significant bit (so the
   95:   byte 0xb1 is the polynomial x^7+x^3+x+1), then the CRC is (q*x^32) mod p,
   96:   where a mod b means the remainder after dividing a by b.
   97: 
   98:   This calculation is done using the shift-register method of multiplying and
   99:   taking the remainder.  The register is initialized to zero, and for each
  100:   incoming bit, x^32 is added mod p to the register if the bit is a one (where
  101:   x^32 mod p is p+x^32 = x^26+...+1), and the register is multiplied mod p by
  102:   x (which is shifting right by one and adding x^32 mod p if the bit shifted
  103:   out is a one).  We start with the highest power (least significant bit) of
  104:   q and repeat for all eight bits of q.
  105: 
  106:   The first table is simply the CRC of all possible eight bit values.  This is
  107:   all the information needed to generate CRCs on data a byte at a time for all
  108:   combinations of CRC register values and incoming bytes.  The remaining tables
  109:   allow for word-at-a-time CRC calculation for both big-endian and little-
  110:   endian machines, where a word is four bytes.
  111: */
  112: local void make_crc_table()
  113: {
  114:     crc_table_t c;
  115:     int n, k;
  116:     crc_table_t poly;                   /* polynomial exclusive-or pattern */
  117:     /* terms of polynomial defining this crc (except x^32): */
  118:     static volatile int first = 1;      /* flag to limit concurrent making */
  119:     static const unsigned char p[] = {0,1,2,4,5,7,8,10,11,12,16,22,23,26};
  120: 
  121:     /* See if another task is already doing this (not thread-safe, but better
  122:        than nothing -- significantly reduces duration of vulnerability in
  123:        case the advice about DYNAMIC_CRC_TABLE is ignored) */
  124:     if (first) {
  125:         first = 0;
  126: 
  127:         /* make exclusive-or pattern from polynomial (0xedb88320UL) */
  128:         poly = 0;
  129:         for (n = 0; n < (int)(sizeof(p)/sizeof(unsigned char)); n++)
  130:             poly |= (crc_table_t)1 << (31 - p[n]);
  131: 
  132:         /* generate a crc for every 8-bit value */
  133:         for (n = 0; n < 256; n++) {
  134:             c = (crc_table_t)n;
  135:             for (k = 0; k < 8; k++)
  136:                 c = c & 1 ? poly ^ (c >> 1) : c >> 1;
  137:             crc_table[0][n] = c;
  138:         }
  139: 
  140: #ifdef BYFOUR
  141:         /* generate crc for each value followed by one, two, and three zeros,
  142:            and then the byte reversal of those as well as the first table */
  143:         for (n = 0; n < 256; n++) {
  144:             c = crc_table[0][n];
  145:             crc_table[4][n] = REV(c);
  146:             for (k = 1; k < 4; k++) {
  147:                 c = crc_table[0][c & 0xff] ^ (c >> 8);
  148:                 crc_table[k][n] = c;
  149:                 crc_table[k + 4][n] = REV(c);
  150:             }
  151:         }
  152: #endif /* BYFOUR */
  153: 
  154:         crc_table_empty = 0;
  155:     }
  156:     else {      /* not first */
  157:         /* wait for the other guy to finish (not efficient, but rare) */
  158:         while (crc_table_empty)
  159:             ;
  160:     }
  161: 
  162: #ifdef MAKECRCH
  163:     /* write out CRC tables to crc32.h */
  164:     {
  165:         FILE *out;
  166: 
  167:         out = fopen("crc32.h", "w");
  168:         if (out == NULL) return;
  169:         fprintf(out, "/* crc32.h -- tables for rapid CRC calculation\n");
  170:         fprintf(out, " * Generated automatically by crc32.c\n */\n\n");
  171:         fprintf(out, "local const crc_table_t FAR ");
  172:         fprintf(out, "crc_table[TBLS][256] =\n{\n  {\n");
  173:         write_table(out, crc_table[0]);
  174: #  ifdef BYFOUR
  175:         fprintf(out, "#ifdef BYFOUR\n");
  176:         for (k = 1; k < 8; k++) {
  177:             fprintf(out, "  },\n  {\n");
  178:             write_table(out, crc_table[k]);
  179:         }
  180:         fprintf(out, "#endif\n");
  181: #  endif /* BYFOUR */
  182:         fprintf(out, "  }\n};\n");
  183:         fclose(out);
  184:     }
  185: #endif /* MAKECRCH */
  186: }
  187: 
  188: #ifdef MAKECRCH
  189: local void write_table(out, table)
  190:     FILE *out;
  191:     const crc_table_t FAR *table;
  192: {
  193:     int n;
  194: 
  195:     for (n = 0; n < 256; n++)
  196:         fprintf(out, "%s0x%08lxUL%s", n % 5 ? "" : "    ",
  197:                 (unsigned long)(table[n]),
  198:                 n == 255 ? "\n" : (n % 5 == 4 ? ",\n" : ", "));
  199: }
  200: #endif /* MAKECRCH */
  201: 
  202: #else /* !DYNAMIC_CRC_TABLE */
  203: /* ========================================================================
  204:  * Tables of CRC-32s of all single-byte values, made by make_crc_table().
  205:  */
  206: #include "crc32.h"
  207: #endif /* DYNAMIC_CRC_TABLE */
  208: 
  209: /* =========================================================================
  210:  * This function can be used by asm versions of crc32()
  211:  */
  212: const unsigned long FAR * ZEXPORT get_crc_table()
  213: {
  214: #ifdef DYNAMIC_CRC_TABLE
  215:     if (crc_table_empty)
  216:         make_crc_table();
  217: #endif /* DYNAMIC_CRC_TABLE */
  218:     return (const unsigned long FAR *)(void FAR *)crc_table;
  219: }
  220: 
  221: /* ========================================================================= */
  222: #define DO1 crc = crc_table[0][((int)crc ^ (*buf++)) & 0xff] ^ (crc >> 8)
  223: #define DO8 DO1; DO1; DO1; DO1; DO1; DO1; DO1; DO1
  224: 
  225: /* ========================================================================= */
  226: unsigned long ZEXPORT crc32(crc, buf, len)
  227:     unsigned long crc;
  228:     const unsigned char FAR *buf;
  229:     uInt len;
  230: {
  231:     if (buf == Z_NULL) return 0UL;
  232: 
  233: #ifdef DYNAMIC_CRC_TABLE
  234:     if (crc_table_empty)
  235:         make_crc_table();
  236: #endif /* DYNAMIC_CRC_TABLE */
  237: 
  238: #ifdef BYFOUR
  239:     if (sizeof(void *) == sizeof(ptrdiff_t)) {
  240:         u4 endian;
  241: 
  242:         endian = 1;
  243:         if (*((unsigned char *)(&endian)))
  244:             return crc32_little(crc, buf, len);
  245:         else
  246:             return crc32_big(crc, buf, len);
  247:     }
  248: #endif /* BYFOUR */
  249:     crc = crc ^ 0xffffffffUL;
  250:     while (len >= 8) {
  251:         DO8;
  252:         len -= 8;
  253:     }
  254:     if (len) do {
  255:         DO1;
  256:     } while (--len);
  257:     return crc ^ 0xffffffffUL;
  258: }
  259: 
  260: #ifdef BYFOUR
  261: 
  262: /* ========================================================================= */
  263: #define DOLIT4 c ^= *buf4++; \
  264:         c = crc_table[3][c & 0xff] ^ crc_table[2][(c >> 8) & 0xff] ^ \
  265:             crc_table[1][(c >> 16) & 0xff] ^ crc_table[0][c >> 24]
  266: #define DOLIT32 DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4
  267: 
  268: /* ========================================================================= */
  269: local unsigned long crc32_little(crc, buf, len)
  270:     unsigned long crc;
  271:     const unsigned char FAR *buf;
  272:     unsigned len;
  273: {
  274:     register u4 c;
  275:     register const u4 FAR *buf4;
  276: 
  277:     c = (u4)crc;
  278:     c = ~c;
  279:     while (len && ((ptrdiff_t)buf & 3)) {
  280:         c = crc_table[0][(c ^ *buf++) & 0xff] ^ (c >> 8);
  281:         len--;
  282:     }
  283: 
  284:     buf4 = (const u4 FAR *)(const void FAR *)buf;
  285:     while (len >= 32) {
  286:         DOLIT32;
  287:         len -= 32;
  288:     }
  289:     while (len >= 4) {
  290:         DOLIT4;
  291:         len -= 4;
  292:     }
  293:     buf = (const unsigned char FAR *)buf4;
  294: 
  295:     if (len) do {
  296:         c = crc_table[0][(c ^ *buf++) & 0xff] ^ (c >> 8);
  297:     } while (--len);
  298:     c = ~c;
  299:     return (unsigned long)c;
  300: }
  301: 
  302: /* ========================================================================= */
  303: #define DOBIG4 c ^= *++buf4; \
  304:         c = crc_table[4][c & 0xff] ^ crc_table[5][(c >> 8) & 0xff] ^ \
  305:             crc_table[6][(c >> 16) & 0xff] ^ crc_table[7][c >> 24]
  306: #define DOBIG32 DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4
  307: 
  308: /* ========================================================================= */
  309: local unsigned long crc32_big(crc, buf, len)
  310:     unsigned long crc;
  311:     const unsigned char FAR *buf;
  312:     unsigned len;
  313: {
  314:     register u4 c;
  315:     register const u4 FAR *buf4;
  316: 
  317:     c = REV((u4)crc);
  318:     c = ~c;
  319:     while (len && ((ptrdiff_t)buf & 3)) {
  320:         c = crc_table[4][(c >> 24) ^ *buf++] ^ (c << 8);
  321:         len--;
  322:     }
  323: 
  324:     buf4 = (const u4 FAR *)(const void FAR *)buf;
  325:     buf4--;
  326:     while (len >= 32) {
  327:         DOBIG32;
  328:         len -= 32;
  329:     }
  330:     while (len >= 4) {
  331:         DOBIG4;
  332:         len -= 4;
  333:     }
  334:     buf4++;
  335:     buf = (const unsigned char FAR *)buf4;
  336: 
  337:     if (len) do {
  338:         c = crc_table[4][(c >> 24) ^ *buf++] ^ (c << 8);
  339:     } while (--len);
  340:     c = ~c;
  341:     return (unsigned long)(REV(c));
  342: }
  343: 
  344: #endif /* BYFOUR */
  345: 
  346: #define GF2_DIM 32      /* dimension of GF(2) vectors (length of CRC) */
  347: 
  348: /* ========================================================================= */
  349: local unsigned long gf2_matrix_times(mat, vec)
  350:     unsigned long *mat;
  351:     unsigned long vec;
  352: {
  353:     unsigned long sum;
  354: 
  355:     sum = 0;
  356:     while (vec) {
  357:         if (vec & 1)
  358:             sum ^= *mat;
  359:         vec >>= 1;
  360:         mat++;
  361:     }
  362:     return sum;
  363: }
  364: 
  365: /* ========================================================================= */
  366: local void gf2_matrix_square(square, mat)
  367:     unsigned long *square;
  368:     unsigned long *mat;
  369: {
  370:     int n;
  371: 
  372:     for (n = 0; n < GF2_DIM; n++)
  373:         square[n] = gf2_matrix_times(mat, mat[n]);
  374: }
  375: 
  376: /* ========================================================================= */
  377: local uLong crc32_combine_(crc1, crc2, len2)
  378:     uLong crc1;
  379:     uLong crc2;
  380:     z_off64_t len2;
  381: {
  382:     int n;
  383:     unsigned long row;
  384:     unsigned long even[GF2_DIM];    /* even-power-of-two zeros operator */
  385:     unsigned long odd[GF2_DIM];     /* odd-power-of-two zeros operator */
  386: 
  387:     /* degenerate case (also disallow negative lengths) */
  388:     if (len2 <= 0)
  389:         return crc1;
  390: 
  391:     /* put operator for one zero bit in odd */
  392:     odd[0] = 0xedb88320UL;          /* CRC-32 polynomial */
  393:     row = 1;
  394:     for (n = 1; n < GF2_DIM; n++) {
  395:         odd[n] = row;
  396:         row <<= 1;
  397:     }
  398: 
  399:     /* put operator for two zero bits in even */
  400:     gf2_matrix_square(even, odd);
  401: 
  402:     /* put operator for four zero bits in odd */
  403:     gf2_matrix_square(odd, even);
  404: 
  405:     /* apply len2 zeros to crc1 (first square will put the operator for one
  406:        zero byte, eight zero bits, in even) */
  407:     do {
  408:         /* apply zeros operator for this bit of len2 */
  409:         gf2_matrix_square(even, odd);
  410:         if (len2 & 1)
  411:             crc1 = gf2_matrix_times(even, crc1);
  412:         len2 >>= 1;
  413: 
  414:         /* if no more bits set, then done */
  415:         if (len2 == 0)
  416:             break;
  417: 
  418:         /* another iteration of the loop with odd and even swapped */
  419:         gf2_matrix_square(odd, even);
  420:         if (len2 & 1)
  421:             crc1 = gf2_matrix_times(odd, crc1);
  422:         len2 >>= 1;
  423: 
  424:         /* if no more bits set, then done */
  425:     } while (len2 != 0);
  426: 
  427:     /* return combined crc */
  428:     crc1 ^= crc2;
  429:     return crc1;
  430: }
  431: 
  432: /* ========================================================================= */
  433: uLong ZEXPORT crc32_combine(crc1, crc2, len2)
  434:     uLong crc1;
  435:     uLong crc2;
  436:     z_off_t len2;
  437: {
  438:     return crc32_combine_(crc1, crc2, len2);
  439: }
  440: 
  441: uLong ZEXPORT crc32_combine64(crc1, crc2, len2)
  442:     uLong crc1;
  443:     uLong crc2;
  444:     z_off64_t len2;
  445: {
  446:     return crc32_combine_(crc1, crc2, len2);
  447: }