The Design and Implementation of the FreeBSD Operating System, Second Edition
Now available: The Design and Implementation of the FreeBSD Operating System (Second Edition)


[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]

FreeBSD/Linux Kernel Cross Reference
sys/libkern/crc32.c

Version: -  FREEBSD  -  FREEBSD-12-STABLE  -  FREEBSD-12-0  -  FREEBSD-11-STABLE  -  FREEBSD-11-2  -  FREEBSD-11-1  -  FREEBSD-11-0  -  FREEBSD-10-STABLE  -  FREEBSD-10-4  -  FREEBSD-10-3  -  FREEBSD-10-2  -  FREEBSD-10-1  -  FREEBSD-10-0  -  FREEBSD-9-STABLE  -  FREEBSD-9-3  -  FREEBSD-9-2  -  FREEBSD-9-1  -  FREEBSD-9-0  -  FREEBSD-8-STABLE  -  FREEBSD-8-4  -  FREEBSD-8-3  -  FREEBSD-8-2  -  FREEBSD-8-1  -  FREEBSD-8-0  -  FREEBSD-7-STABLE  -  FREEBSD-7-4  -  FREEBSD-7-3  -  FREEBSD-7-2  -  FREEBSD-7-1  -  FREEBSD-7-0  -  FREEBSD-6-STABLE  -  FREEBSD-6-4  -  FREEBSD-6-3  -  FREEBSD-6-2  -  FREEBSD-6-1  -  FREEBSD-6-0  -  FREEBSD-5-STABLE  -  FREEBSD-5-5  -  FREEBSD-5-4  -  FREEBSD-5-3  -  FREEBSD-5-2  -  FREEBSD-5-1  -  FREEBSD-5-0  -  FREEBSD-4-STABLE  -  FREEBSD-3-STABLE  -  FREEBSD22  -  linux-2.6  -  linux-2.4.22  -  MK83  -  MK84  -  PLAN9  -  DFBSD  -  NETBSD  -  NETBSD5  -  NETBSD4  -  NETBSD3  -  NETBSD20  -  OPENBSD  -  xnu-517  -  xnu-792  -  xnu-792.6.70  -  xnu-1228  -  xnu-1456.1.26  -  xnu-1699.24.8  -  xnu-2050.18.24  -  OPENSOLARIS  -  minix-3-1-1 
SearchContext: -  none  -  3  -  10 

    1 /*-
    2  *  COPYRIGHT (C) 1986 Gary S. Brown.  You may use this program, or
    3  *  code or tables extracted from it, as desired without restriction.
    4  *
    5  *  First, the polynomial itself and its table of feedback terms.  The
    6  *  polynomial is
    7  *  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+X^0
    8  *
    9  *  Note that we take it "backwards" and put the highest-order term in
   10  *  the lowest-order bit.  The X^32 term is "implied"; the LSB is the
   11  *  X^31 term, etc.  The X^0 term (usually shown as "+1") results in
   12  *  the MSB being 1
   13  *
   14  *  Note that the usual hardware shift register implementation, which
   15  *  is what we're using (we're merely optimizing it by doing eight-bit
   16  *  chunks at a time) shifts bits into the lowest-order term.  In our
   17  *  implementation, that means shifting towards the right.  Why do we
   18  *  do it this way?  Because the calculated CRC must be transmitted in
   19  *  order from highest-order term to lowest-order term.  UARTs transmit
   20  *  characters in order from LSB to MSB.  By storing the CRC this way
   21  *  we hand it to the UART in the order low-byte to high-byte; the UART
   22  *  sends each low-bit to hight-bit; and the result is transmission bit
   23  *  by bit from highest- to lowest-order term without requiring any bit
   24  *  shuffling on our part.  Reception works similarly
   25  *
   26  *  The feedback terms table consists of 256, 32-bit entries.  Notes
   27  *
   28  *      The table can be generated at runtime if desired; code to do so
   29  *      is shown later.  It might not be obvious, but the feedback
   30  *      terms simply represent the results of eight shift/xor opera
   31  *      tions for all combinations of data and CRC register values
   32  *
   33  *      The values must be right-shifted by eight bits by the "updcrc
   34  *      logic; the shift must be unsigned (bring in zeroes).  On some
   35  *      hardware you could probably optimize the shift in assembler by
   36  *      using byte-swap instructions
   37  *      polynomial $edb88320
   38  *
   39  * CRC32 code derived from work by Gary S. Brown.
   40  *
   41  * $FreeBSD: src/sys/libkern/crc32.c,v 1.1.2.1 2002/07/31 09:08:34 imp Exp $
   42  * $DragonFly: src/sys/libkern/crc32.c,v 1.7 2008/11/03 08:41:31 swildner Exp $
   43  */
   44 
   45 /*
   46  * WARNING: This code is used by various subsystems including the HAMMER
   47  * filesystem.  This code may be directly compiled in userland or kernel
   48  * builds.
   49  */
   50 
   51 #ifdef _KERNEL
   52 #include <sys/param.h>
   53 #include <sys/systm.h>
   54 #else
   55 #include <sys/types.h>
   56 #endif
   57 
   58 #ifndef _KERNEL
   59 /* prototypes for the kernel are in <sys/systm.h> */
   60 uint32_t crc32(const void *buf, size_t size);
   61 uint32_t crc32_ext(const void *buf, size_t size, uint32_t ocrc);
   62 #endif
   63 
   64 uint32_t crc32_tab[] = {
   65         0x00000000, 0x77073096, 0xee0e612c, 0x990951ba, 0x076dc419, 0x706af48f,
   66         0xe963a535, 0x9e6495a3, 0x0edb8832, 0x79dcb8a4, 0xe0d5e91e, 0x97d2d988,
   67         0x09b64c2b, 0x7eb17cbd, 0xe7b82d07, 0x90bf1d91, 0x1db71064, 0x6ab020f2,
   68         0xf3b97148, 0x84be41de, 0x1adad47d, 0x6ddde4eb, 0xf4d4b551, 0x83d385c7,
   69         0x136c9856, 0x646ba8c0, 0xfd62f97a, 0x8a65c9ec, 0x14015c4f, 0x63066cd9,
   70         0xfa0f3d63, 0x8d080df5, 0x3b6e20c8, 0x4c69105e, 0xd56041e4, 0xa2677172,
   71         0x3c03e4d1, 0x4b04d447, 0xd20d85fd, 0xa50ab56b, 0x35b5a8fa, 0x42b2986c,
   72         0xdbbbc9d6, 0xacbcf940, 0x32d86ce3, 0x45df5c75, 0xdcd60dcf, 0xabd13d59,
   73         0x26d930ac, 0x51de003a, 0xc8d75180, 0xbfd06116, 0x21b4f4b5, 0x56b3c423,
   74         0xcfba9599, 0xb8bda50f, 0x2802b89e, 0x5f058808, 0xc60cd9b2, 0xb10be924,
   75         0x2f6f7c87, 0x58684c11, 0xc1611dab, 0xb6662d3d, 0x76dc4190, 0x01db7106,
   76         0x98d220bc, 0xefd5102a, 0x71b18589, 0x06b6b51f, 0x9fbfe4a5, 0xe8b8d433,
   77         0x7807c9a2, 0x0f00f934, 0x9609a88e, 0xe10e9818, 0x7f6a0dbb, 0x086d3d2d,
   78         0x91646c97, 0xe6635c01, 0x6b6b51f4, 0x1c6c6162, 0x856530d8, 0xf262004e,
   79         0x6c0695ed, 0x1b01a57b, 0x8208f4c1, 0xf50fc457, 0x65b0d9c6, 0x12b7e950,
   80         0x8bbeb8ea, 0xfcb9887c, 0x62dd1ddf, 0x15da2d49, 0x8cd37cf3, 0xfbd44c65,
   81         0x4db26158, 0x3ab551ce, 0xa3bc0074, 0xd4bb30e2, 0x4adfa541, 0x3dd895d7,
   82         0xa4d1c46d, 0xd3d6f4fb, 0x4369e96a, 0x346ed9fc, 0xad678846, 0xda60b8d0,
   83         0x44042d73, 0x33031de5, 0xaa0a4c5f, 0xdd0d7cc9, 0x5005713c, 0x270241aa,
   84         0xbe0b1010, 0xc90c2086, 0x5768b525, 0x206f85b3, 0xb966d409, 0xce61e49f,
   85         0x5edef90e, 0x29d9c998, 0xb0d09822, 0xc7d7a8b4, 0x59b33d17, 0x2eb40d81,
   86         0xb7bd5c3b, 0xc0ba6cad, 0xedb88320, 0x9abfb3b6, 0x03b6e20c, 0x74b1d29a,
   87         0xead54739, 0x9dd277af, 0x04db2615, 0x73dc1683, 0xe3630b12, 0x94643b84,
   88         0x0d6d6a3e, 0x7a6a5aa8, 0xe40ecf0b, 0x9309ff9d, 0x0a00ae27, 0x7d079eb1,
   89         0xf00f9344, 0x8708a3d2, 0x1e01f268, 0x6906c2fe, 0xf762575d, 0x806567cb,
   90         0x196c3671, 0x6e6b06e7, 0xfed41b76, 0x89d32be0, 0x10da7a5a, 0x67dd4acc,
   91         0xf9b9df6f, 0x8ebeeff9, 0x17b7be43, 0x60b08ed5, 0xd6d6a3e8, 0xa1d1937e,
   92         0x38d8c2c4, 0x4fdff252, 0xd1bb67f1, 0xa6bc5767, 0x3fb506dd, 0x48b2364b,
   93         0xd80d2bda, 0xaf0a1b4c, 0x36034af6, 0x41047a60, 0xdf60efc3, 0xa867df55,
   94         0x316e8eef, 0x4669be79, 0xcb61b38c, 0xbc66831a, 0x256fd2a0, 0x5268e236,
   95         0xcc0c7795, 0xbb0b4703, 0x220216b9, 0x5505262f, 0xc5ba3bbe, 0xb2bd0b28,
   96         0x2bb45a92, 0x5cb36a04, 0xc2d7ffa7, 0xb5d0cf31, 0x2cd99e8b, 0x5bdeae1d,
   97         0x9b64c2b0, 0xec63f226, 0x756aa39c, 0x026d930a, 0x9c0906a9, 0xeb0e363f,
   98         0x72076785, 0x05005713, 0x95bf4a82, 0xe2b87a14, 0x7bb12bae, 0x0cb61b38,
   99         0x92d28e9b, 0xe5d5be0d, 0x7cdcefb7, 0x0bdbdf21, 0x86d3d2d4, 0xf1d4e242,
  100         0x68ddb3f8, 0x1fda836e, 0x81be16cd, 0xf6b9265b, 0x6fb077e1, 0x18b74777,
  101         0x88085ae6, 0xff0f6a70, 0x66063bca, 0x11010b5c, 0x8f659eff, 0xf862ae69,
  102         0x616bffd3, 0x166ccf45, 0xa00ae278, 0xd70dd2ee, 0x4e048354, 0x3903b3c2,
  103         0xa7672661, 0xd06016f7, 0x4969474d, 0x3e6e77db, 0xaed16a4a, 0xd9d65adc,
  104         0x40df0b66, 0x37d83bf0, 0xa9bcae53, 0xdebb9ec5, 0x47b2cf7f, 0x30b5ffe9,
  105         0xbdbdf21c, 0xcabac28a, 0x53b39330, 0x24b4a3a6, 0xbad03605, 0xcdd70693,
  106         0x54de5729, 0x23d967bf, 0xb3667a2e, 0xc4614ab8, 0x5d681b02, 0x2a6f2b94,
  107         0xb40bbe37, 0xc30c8ea1, 0x5a05df1b, 0x2d02ef8d
  108 };
  109 
  110 uint32_t
  111 crc32(const void *buf, size_t size)
  112 {
  113         const uint8_t *p;
  114         uint32_t crc;
  115 
  116         p = buf;
  117         crc = ~0U;
  118 
  119         while (size--)
  120                 crc = crc32_tab[(crc ^ *p++) & 0xFF] ^ (crc >> 8);
  121 
  122         return crc ^ ~0U;
  123 }
  124 
  125 uint32_t
  126 crc32_ext(const void *buf, size_t size, uint32_t ocrc)
  127 {
  128         const uint8_t *p;
  129         uint32_t crc;
  130 
  131         p = buf;
  132         crc = ~ocrc;
  133 
  134         while (size--)
  135                 crc = crc32_tab[(crc ^ *p++) & 0xFF] ^ (crc >> 8);
  136 
  137         return crc ^ ~0U;
  138 }
  139 

Cache object: 55322c8dd7bb3687185694bee646af85


[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]


This page is part of the FreeBSD/Linux Linux Kernel Cross-Reference, and was automatically generated using a modified version of the LXR engine.