Home | History | Annotate | Line # | Download | only in libkern
crc32.c revision 1.4.8.2 
      1 /*	$NetBSD: crc32.c,v 1.4.8.2 2009/05/13 17:22:15 jym Exp $	*/
      2 
      3 /* crc32.c -- compute the CRC-32 of a data stream
      4  *
      5  * Adapted from zlib's crc code.
      6  *
      7  * Copyright (C) 1995-2005 Mark Adler
      8  * For conditions of distribution and use, see copyright notice in zlib.h
      9  *
     10  * Thanks to Rodney Brown <rbrown64 (at) csc.com.au> for his contribution of faster
     11  * CRC methods: exclusive-oring 32 bits of data at a time, and pre-computing
     12  * tables for updating the shift register in one step with three exclusive-ors
     13  * instead of four steps with four exclusive-ors.  This results in about a
     14  * factor of two increase in speed on a Power PC G4 (PPC7455) using gcc -O3.
     15  */
     16 
     17 /* @(#) Id */
     18 
     19 #include <sys/param.h>
     20 #include <machine/endian.h>
     21 
     22 #define z_ptrdiff_t int32_t
     23 
     24 typedef uint32_t u4;
     25 
     26 /* Definitions for doing the crc four data bytes at a time. */
     27 #define REV(w) (((w)>>24)+(((w)>>8)&0xff00)+ \
     28                (((w)&0xff00)<<8)+(((w)&0xff)<<24))
     29 
     30 /* ========================================================================
     31  * Tables of CRC-32s of all single-byte values, made by make_crc_table().
     32  */
     33 #include "crc32.h"
     34 
     35 #if BYTE_ORDER == LITTLE_ENDIAN
     36 /* ========================================================================= */
     37 #define DOLIT4 c ^= *buf4++; \
     38         c = crc_table[3][c & 0xff] ^ crc_table[2][(c >> 8) & 0xff] ^ \
     39             crc_table[1][(c >> 16) & 0xff] ^ crc_table[0][c >> 24]
     40 #define DOLIT32 DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4
     41 
     42 /* ========================================================================= */
     43 uint32_t crc32(
     44     uint32_t crc,
     45     const unsigned char *buf,
     46     unsigned len)
     47 {
     48     register u4 c;
     49     register const u4 *buf4;
     50 
     51     if (buf == NULL) return 0UL;
     52 
     53     c = (u4)crc;
     54     c = ~c;
     55     while (len && ((z_ptrdiff_t)buf & 3)) {
     56         c = crc_table[0][(c ^ *buf++) & 0xff] ^ (c >> 8);
     57         len--;
     58     }
     59 
     60     buf4 = (const u4 *)(const void *)buf;
     61     while (len >= 32) {
     62         DOLIT32;
     63         len -= 32;
     64     }
     65     while (len >= 4) {
     66         DOLIT4;
     67         len -= 4;
     68     }
     69     buf = (const unsigned char *)buf4;
     70 
     71     if (len) do {
     72         c = crc_table[0][(c ^ *buf++) & 0xff] ^ (c >> 8);
     73     } while (--len);
     74     c = ~c;
     75     return (uint32_t)c;
     76 }
     77 
     78 #else /* BIG_ENDIAN */
     79 
     80 /* ========================================================================= */
     81 #define DOBIG4 c ^= *++buf4; \
     82         c = crc_table[4][c & 0xff] ^ crc_table[5][(c >> 8) & 0xff] ^ \
     83             crc_table[6][(c >> 16) & 0xff] ^ crc_table[7][c >> 24]
     84 #define DOBIG32 DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4
     85 
     86 /* ========================================================================= */
     87 uint32_t crc32(
     88     uint32_t crc,
     89     const unsigned char *buf,
     90     unsigned len)
     91 {
     92     register u4 c;
     93     register const u4 *buf4;
     94 
     95     if (buf == NULL) return 0UL;
     96 
     97     c = REV((u4)crc);
     98     c = ~c;
     99     while (len && ((z_ptrdiff_t)buf & 3)) {
    100         c = crc_table[4][(c >> 24) ^ *buf++] ^ (c << 8);
    101         len--;
    102     }
    103 
    104     buf4 = (const u4 *)(const void *)buf;
    105     buf4--;
    106     while (len >= 32) {
    107         DOBIG32;
    108         len -= 32;
    109     }
    110     while (len >= 4) {
    111         DOBIG4;
    112         len -= 4;
    113     }
    114     buf4++;
    115     buf = (const unsigned char *)buf4;
    116 
    117     if (len) do {
    118         c = crc_table[4][(c >> 24) ^ *buf++] ^ (c << 8);
    119     } while (--len);
    120     c = ~c;
    121     return (uint32_t)(REV(c));
    122 }
    123 #endif
    124