2 * COPYRIGHT (C) 1986 Gary S. Brown. You may use this program, or
3 * code or tables extracted from it, as desired without restriction.
7 * First, the polynomial itself and its table of feedback terms. The
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
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
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
28 * The feedback terms table consists of 256, 32-bit entries. Notes
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
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
42 * CRC32 code derived from work by Gary S. Brown.
47 #include "byte-order.h"
49 /*****************************************************************/
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: */
57 /* Width : 4 bytes. */
58 /* Poly : 0x1EDC6F41L */
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". */
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
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.
141 crc32c(const uint8_t *data, size_t size)
143 uint32_t crc = 0xffffffffL;
146 crc = crc32Table[(crc ^ *data++) & 0xff] ^ (crc >> 8);
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);
157 /* Our value is in network byte-order. OVS_FORCE keeps sparse happy. */
158 return (OVS_FORCE ovs_be32) ~crc;