lib/crc32c.c

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