sys/lib/libkern/crc32.c

   1 /*      $NetBSD: crc32.c,v 1.3 2009/03/25 19:21:39 tls 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@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