Home | History | Annotate | Line # | Download | only in libkern
crc32.c revision 1.4.8.3 
      1 /*	$NetBSD: crc32.c,v 1.4.8.3 2009/05/16 01:25:32 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 typedef uint32_t u4;
     23 
     24 /* Definitions for doing the crc four data bytes at a time. */
     25 #define REV(w) (((w)>>24)+(((w)>>8)&0xff00)+ \
     26                (((w)&0xff00)<<8)+(((w)&0xff)<<24))
     27 
     28 /* ========================================================================
     29  * Tables of CRC-32s of all single-byte values, made by make_crc_table().
     30  */
     31 #include <lib/libkern/libkern.h>
     32 #include "crc32.h"
     33 
     34 #if BYTE_ORDER == LITTLE_ENDIAN
     35 /* ========================================================================= */
     36 #define DOLIT4 c ^= *buf4++; \
     37         c = crc_table[3][c & 0xff] ^ crc_table[2][(c >> 8) & 0xff] ^ \
     38             crc_table[1][(c >> 16) & 0xff] ^ crc_table[0][c >> 24]
     39 #define DOLIT32 DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4
     40 
     41 /* ========================================================================= */
     42 uint32_t crc32(uint32_t crc, const uint8_t *buf, size_t len)
     43 {
     44     register u4 c;
     45     register const u4 *buf4;
     46 
     47     if (buf == NULL) return 0UL;
     48 
     49     c = (u4)crc;
     50     c = ~c;
     51     while (len && ((uintptr_t)buf & 3)) {
     52         c = crc_table[0][(c ^ *buf++) & 0xff] ^ (c >> 8);
     53         len--;
     54     }
     55 
     56     buf4 = (const u4 *)(const void *)buf;
     57     while (len >= 32) {
     58         DOLIT32;
     59         len -= 32;
     60     }
     61     while (len >= 4) {
     62         DOLIT4;
     63         len -= 4;
     64     }
     65     buf = (const unsigned char *)buf4;
     66 
     67     if (len) do {
     68         c = crc_table[0][(c ^ *buf++) & 0xff] ^ (c >> 8);
     69     } while (--len);
     70     c = ~c;
     71     return (uint32_t)c;
     72 }
     73 
     74 #else /* BIG_ENDIAN */
     75 
     76 /* ========================================================================= */
     77 #define DOBIG4 c ^= *++buf4; \
     78         c = crc_table[4][c & 0xff] ^ crc_table[5][(c >> 8) & 0xff] ^ \
     79             crc_table[6][(c >> 16) & 0xff] ^ crc_table[7][c >> 24]
     80 #define DOBIG32 DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4
     81 
     82 /* ========================================================================= */
     83 uint32_t crc32(uint32_t crc, const uint8_t *buf, size_t len)
     84 {
     85     register u4 c;
     86     register const u4 *buf4;
     87 
     88     if (buf == NULL) return 0UL;
     89 
     90     c = REV((u4)crc);
     91     c = ~c;
     92     while (len && ((uintptr_t)buf & 3)) {
     93         c = crc_table[4][(c >> 24) ^ *buf++] ^ (c << 8);
     94         len--;
     95     }
     96 
     97     buf4 = (const u4 *)(const void *)buf;
     98     buf4--;
     99     while (len >= 32) {
    100         DOBIG32;
    101         len -= 32;
    102     }
    103     while (len >= 4) {
    104         DOBIG4;
    105         len -= 4;
    106     }
    107     buf4++;
    108     buf = (const unsigned char *)buf4;
    109 
    110     if (len) do {
    111         c = crc_table[4][(c >> 24) ^ *buf++] ^ (c << 8);
    112     } while (--len);
    113     c = ~c;
    114     return (uint32_t)(REV(c));
    115 }
    116 #endif
    117