xpcom/io/crc32c.c

   1 /*
   2  * Based on file found here:
   3  *
   4  *   https://svnweb.freebsd.org/base/stable/10/sys/libkern/crc32.c?revision=256281
   5  */
   6
   7 /*-
   8  *  COPYRIGHT (C) 1986 Gary S. Brown.  You may use this program, or
   9  *  code or tables extracted from it, as desired without restriction.
  10  */
  11
  12 /*
  13  *  First, the polynomial itself and its table of feedback terms.  The
  14  *  polynomial is
  15  *  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
  16  *
  17  *  Note that we take it "backwards" and put the highest-order term in
  18  *  the lowest-order bit.  The X^32 term is "implied"; the LSB is the
  19  *  X^31 term, etc.  The X^0 term (usually shown as "+1") results in
  20  *  the MSB being 1
  21  *
  22  *  Note that the usual hardware shift register implementation, which
  23  *  is what we're using (we're merely optimizing it by doing eight-bit
  24  *  chunks at a time) shifts bits into the lowest-order term.  In our
  25  *  implementation, that means shifting towards the right.  Why do we
  26  *  do it this way?  Because the calculated CRC must be transmitted in
  27  *  order from highest-order term to lowest-order term.  UARTs transmit
  28  *  characters in order from LSB to MSB.  By storing the CRC this way
  29  *  we hand it to the UART in the order low-byte to high-byte; the UART
  30  *  sends each low-bit to hight-bit; and the result is transmission bit
  31  *  by bit from highest- to lowest-order term without requiring any bit
  32  *  shuffling on our part.  Reception works similarly
  33  *
  34  *  The feedback terms table consists of 256, 32-bit entries.  Notes
  35  *
  36  *      The table can be generated at runtime if desired; code to do so
  37  *      is shown later.  It might not be obvious, but the feedback
  38  *      terms simply represent the results of eight shift/xor opera
  39  *      tions for all combinations of data and CRC register values
  40  *
  41  *      The values must be right-shifted by eight bits by the "updcrc
  42  *      logic; the shift must be unsigned (bring in zeroes).  On some
  43  *      hardware you could probably optimize the shift in assembler by
  44  *      using byte-swap instructions
  45  *      polynomial $edb88320
  46  *
  47  *
  48  * CRC32 code derived from work by Gary S. Brown.
  49  */
  50
  51 #include "crc32c.h"
  52
  53 /* CRC32C routines, these use a different polynomial */
  54 /*****************************************************************/
  55 /*                                                               */
  56 /* CRC LOOKUP TABLE                                              */
  57 /* ================                                              */
  58 /* The following CRC lookup table was generated automagically    */
  59 /* by the Rocksoft^tm Model CRC Algorithm Table Generation       */
  60 /* Program V1.0 using the following model parameters:            */
  61 /*                                                               */
  62 /*    Width   : 4 bytes.                                         */
  63 /*    Poly    : 0x1EDC6F41L                                      */
  64 /*    Reverse : TRUE.                                            */
  65 /*                                                               */
  66 /* For more information on the Rocksoft^tm Model CRC Algorithm,  */
  67 /* see the document titled "A Painless Guide to CRC Error        */
  68 /* Detection Algorithms" by Ross Williams                        */
  69 /* (ross@guest.adelaide.edu.au.). This document is likely to be  */
  70 /* in the FTP archive "ftp.adelaide.edu.au/pub/rocksoft".        */
  71 /*                                                               */
  72 /*****************************************************************/
  73
  74 static const uint32_t crc32Table[256] = {
  75         0x00000000L, 0xF26B8303L, 0xE13B70F7L, 0x1350F3F4L,
  76         0xC79A971FL, 0x35F1141CL, 0x26A1E7E8L, 0xD4CA64EBL,
  77         0x8AD958CFL, 0x78B2DBCCL, 0x6BE22838L, 0x9989AB3BL,
  78         0x4D43CFD0L, 0xBF284CD3L, 0xAC78BF27L, 0x5E133C24L,
  79         0x105EC76FL, 0xE235446CL, 0xF165B798L, 0x030E349BL,
  80         0xD7C45070L, 0x25AFD373L, 0x36FF2087L, 0xC494A384L,
  81         0x9A879FA0L, 0x68EC1CA3L, 0x7BBCEF57L, 0x89D76C54L,
  82         0x5D1D08BFL, 0xAF768BBCL, 0xBC267848L, 0x4E4DFB4BL,
  83         0x20BD8EDEL, 0xD2D60DDDL, 0xC186FE29L, 0x33ED7D2AL,
  84         0xE72719C1L, 0x154C9AC2L, 0x061C6936L, 0xF477EA35L,
  85         0xAA64D611L, 0x580F5512L, 0x4B5FA6E6L, 0xB93425E5L,
  86         0x6DFE410EL, 0x9F95C20DL, 0x8CC531F9L, 0x7EAEB2FAL,
  87         0x30E349B1L, 0xC288CAB2L, 0xD1D83946L, 0x23B3BA45L,
  88         0xF779DEAEL, 0x05125DADL, 0x1642AE59L, 0xE4292D5AL,
  89         0xBA3A117EL, 0x4851927DL, 0x5B016189L, 0xA96AE28AL,
  90         0x7DA08661L, 0x8FCB0562L, 0x9C9BF696L, 0x6EF07595L,
  91         0x417B1DBCL, 0xB3109EBFL, 0xA0406D4BL, 0x522BEE48L,
  92         0x86E18AA3L, 0x748A09A0L, 0x67DAFA54L, 0x95B17957L,
  93         0xCBA24573L, 0x39C9C670L, 0x2A993584L, 0xD8F2B687L,
  94         0x0C38D26CL, 0xFE53516FL, 0xED03A29BL, 0x1F682198L,
  95         0x5125DAD3L, 0xA34E59D0L, 0xB01EAA24L, 0x42752927L,
  96         0x96BF4DCCL, 0x64D4CECFL, 0x77843D3BL, 0x85EFBE38L,
  97         0xDBFC821CL, 0x2997011FL, 0x3AC7F2EBL, 0xC8AC71E8L,
  98         0x1C661503L, 0xEE0D9600L, 0xFD5D65F4L, 0x0F36E6F7L,
  99         0x61C69362L, 0x93AD1061L, 0x80FDE395L, 0x72966096L,
 100         0xA65C047DL, 0x5437877EL, 0x4767748AL, 0xB50CF789L,
 101         0xEB1FCBADL, 0x197448AEL, 0x0A24BB5AL, 0xF84F3859L,
 102         0x2C855CB2L, 0xDEEEDFB1L, 0xCDBE2C45L, 0x3FD5AF46L,
 103         0x7198540DL, 0x83F3D70EL, 0x90A324FAL, 0x62C8A7F9L,
 104         0xB602C312L, 0x44694011L, 0x5739B3E5L, 0xA55230E6L,
 105         0xFB410CC2L, 0x092A8FC1L, 0x1A7A7C35L, 0xE811FF36L,
 106         0x3CDB9BDDL, 0xCEB018DEL, 0xDDE0EB2AL, 0x2F8B6829L,
 107         0x82F63B78L, 0x709DB87BL, 0x63CD4B8FL, 0x91A6C88CL,
 108         0x456CAC67L, 0xB7072F64L, 0xA457DC90L, 0x563C5F93L,
 109         0x082F63B7L, 0xFA44E0B4L, 0xE9141340L, 0x1B7F9043L,
 110         0xCFB5F4A8L, 0x3DDE77ABL, 0x2E8E845FL, 0xDCE5075CL,
 111         0x92A8FC17L, 0x60C37F14L, 0x73938CE0L, 0x81F80FE3L,
 112         0x55326B08L, 0xA759E80BL, 0xB4091BFFL, 0x466298FCL,
 113         0x1871A4D8L, 0xEA1A27DBL, 0xF94AD42FL, 0x0B21572CL,
 114         0xDFEB33C7L, 0x2D80B0C4L, 0x3ED04330L, 0xCCBBC033L,
 115         0xA24BB5A6L, 0x502036A5L, 0x4370C551L, 0xB11B4652L,
 116         0x65D122B9L, 0x97BAA1BAL, 0x84EA524EL, 0x7681D14DL,
 117         0x2892ED69L, 0xDAF96E6AL, 0xC9A99D9EL, 0x3BC21E9DL,
 118         0xEF087A76L, 0x1D63F975L, 0x0E330A81L, 0xFC588982L,
 119         0xB21572C9L, 0x407EF1CAL, 0x532E023EL, 0xA145813DL,
 120         0x758FE5D6L, 0x87E466D5L, 0x94B49521L, 0x66DF1622L,
 121         0x38CC2A06L, 0xCAA7A905L, 0xD9F75AF1L, 0x2B9CD9F2L,
 122         0xFF56BD19L, 0x0D3D3E1AL, 0x1E6DCDEEL, 0xEC064EEDL,
 123         0xC38D26C4L, 0x31E6A5C7L, 0x22B65633L, 0xD0DDD530L,
 124         0x0417B1DBL, 0xF67C32D8L, 0xE52CC12CL, 0x1747422FL,
 125         0x49547E0BL, 0xBB3FFD08L, 0xA86F0EFCL, 0x5A048DFFL,
 126         0x8ECEE914L, 0x7CA56A17L, 0x6FF599E3L, 0x9D9E1AE0L,
 127         0xD3D3E1ABL, 0x21B862A8L, 0x32E8915CL, 0xC083125FL,
 128         0x144976B4L, 0xE622F5B7L, 0xF5720643L, 0x07198540L,
 129         0x590AB964L, 0xAB613A67L, 0xB831C993L, 0x4A5A4A90L,
 130         0x9E902E7BL, 0x6CFBAD78L, 0x7FAB5E8CL, 0x8DC0DD8FL,
 131         0xE330A81AL, 0x115B2B19L, 0x020BD8EDL, 0xF0605BEEL,
 132         0x24AA3F05L, 0xD6C1BC06L, 0xC5914FF2L, 0x37FACCF1L,
 133         0x69E9F0D5L, 0x9B8273D6L, 0x88D28022L, 0x7AB90321L,
 134         0xAE7367CAL, 0x5C18E4C9L, 0x4F48173DL, 0xBD23943EL,
 135         0xF36E6F75L, 0x0105EC76L, 0x12551F82L, 0xE03E9C81L,
 136         0x34F4F86AL, 0xC69F7B69L, 0xD5CF889DL, 0x27A40B9EL,
 137         0x79B737BAL, 0x8BDCB4B9L, 0x988C474DL, 0x6AE7C44EL,
 138         0xBE2DA0A5L, 0x4C4623A6L, 0x5F16D052L, 0xAD7D5351L
 139 };
 140
 141 // NOTE: See source URL at top of this file for multitable implementation which
 142 //       offers a performance boost at the cost of ~8KB of static tables.
 143
 144 uint32_t
 145 ComputeCrc32c(uint32_t crc, const void *buf, size_t size)
 146 {
 147         const uint8_t *p = buf;
 148
 149
 150         while (size--)
 151                 crc = crc32Table[(crc ^ *p++) & 0xff] ^ (crc >> 8);
 152
 153         return crc;
 154 }