/src/openvswitch/lib/crc32c.c

Source (jump to first uncovered line)
/*-
 *  COPYRIGHT (C) 1986 Gary S. Brown.  You may use this program, or
 *  code or tables extracted from it, as desired without restriction.
 */

/*
 *  First, the polynomial itself and its table of feedback terms.  The
 *  polynomial is
 *  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
 *
 *  Note that we take it "backwards" and put the highest-order term in
 *  the lowest-order bit.  The X^32 term is "implied"; the LSB is the
 *  X^31 term, etc.  The X^0 term (usually shown as "+1") results in
 *  the MSB being 1
 *
 *  Note that the usual hardware shift register implementation, which
 *  is what we're using (we're merely optimizing it by doing eight-bit
 *  chunks at a time) shifts bits into the lowest-order term.  In our
 *  implementation, that means shifting towards the right.  Why do we
 *  do it this way?  Because the calculated CRC must be transmitted in
 *  order from highest-order term to lowest-order term.  UARTs transmit
 *  characters in order from LSB to MSB.  By storing the CRC this way
 *  we hand it to the UART in the order low-byte to high-byte; the UART
 *  sends each low-bit to hight-bit; and the result is transmission bit
 *  by bit from highest- to lowest-order term without requiring any bit
 *  shuffling on our part.  Reception works similarly
 *
 *  The feedback terms table consists of 256, 32-bit entries.  Notes
 *
 *      The table can be generated at runtime if desired; code to do so
 *      can be found in FreeBSD.  It might not be obvious, but the feedback
 *      terms simply represent the results of eight shift/xor opera
 *      tions for all combinations of data and CRC register values
 *
 *      The values must be right-shifted by eight bits by the "updcrc
 *      logic; the shift must be unsigned (bring in zeroes).  On some
 *      hardware you could probably optimize the shift in assembler by
 *      using byte-swap instructions
 *      polynomial $edb88320
 *
 *
 * CRC32 code derived from work by Gary S. Brown.
 */

#include <config.h>
#include "crc32c.h"
#include "byte-order.h"

/*****************************************************************/
/*                                                               */
/* CRC LOOKUP TABLE                                              */
/* ================                                              */
/* The following CRC lookup table was generated automagically    */
/* by the Rocksoft^tm Model CRC Algorithm Table Generation       */
/* Program V1.0 using the following model parameters:            */
/*                                                               */
/*    Width   : 4 bytes.                                         */
/*    Poly    : 0x1EDC6F41L                                      */
/*    Reverse : TRUE.                                            */
/*                                                               */
/* For more information on the Rocksoft^tm Model CRC Algorithm,  */
/* see the document titled "A Painless Guide to CRC Error        */
/* Detection Algorithms" by Ross Williams                        */
/* (ross@guest.adelaide.edu.au.). This document is likely to be  */
/* in the FTP archive "ftp.adelaide.edu.au/pub/rocksoft".        */
/*                                                               */
/*****************************************************************/
static const uint32_t crc32Table[256] = {
    0x00000000L, 0xF26B8303L, 0xE13B70F7L, 0x1350F3F4L,
    0xC79A971FL, 0x35F1141CL, 0x26A1E7E8L, 0xD4CA64EBL,
    0x8AD958CFL, 0x78B2DBCCL, 0x6BE22838L, 0x9989AB3BL,
    0x4D43CFD0L, 0xBF284CD3L, 0xAC78BF27L, 0x5E133C24L,
    0x105EC76FL, 0xE235446CL, 0xF165B798L, 0x030E349BL,
    0xD7C45070L, 0x25AFD373L, 0x36FF2087L, 0xC494A384L,
    0x9A879FA0L, 0x68EC1CA3L, 0x7BBCEF57L, 0x89D76C54L,
    0x5D1D08BFL, 0xAF768BBCL, 0xBC267848L, 0x4E4DFB4BL,
    0x20BD8EDEL, 0xD2D60DDDL, 0xC186FE29L, 0x33ED7D2AL,
    0xE72719C1L, 0x154C9AC2L, 0x061C6936L, 0xF477EA35L,
    0xAA64D611L, 0x580F5512L, 0x4B5FA6E6L, 0xB93425E5L,
    0x6DFE410EL, 0x9F95C20DL, 0x8CC531F9L, 0x7EAEB2FAL,
    0x30E349B1L, 0xC288CAB2L, 0xD1D83946L, 0x23B3BA45L,
    0xF779DEAEL, 0x05125DADL, 0x1642AE59L, 0xE4292D5AL,
    0xBA3A117EL, 0x4851927DL, 0x5B016189L, 0xA96AE28AL,
    0x7DA08661L, 0x8FCB0562L, 0x9C9BF696L, 0x6EF07595L,
    0x417B1DBCL, 0xB3109EBFL, 0xA0406D4BL, 0x522BEE48L,
    0x86E18AA3L, 0x748A09A0L, 0x67DAFA54L, 0x95B17957L,
    0xCBA24573L, 0x39C9C670L, 0x2A993584L, 0xD8F2B687L,
    0x0C38D26CL, 0xFE53516FL, 0xED03A29BL, 0x1F682198L,
    0x5125DAD3L, 0xA34E59D0L, 0xB01EAA24L, 0x42752927L,
    0x96BF4DCCL, 0x64D4CECFL, 0x77843D3BL, 0x85EFBE38L,
    0xDBFC821CL, 0x2997011FL, 0x3AC7F2EBL, 0xC8AC71E8L,
    0x1C661503L, 0xEE0D9600L, 0xFD5D65F4L, 0x0F36E6F7L,
    0x61C69362L, 0x93AD1061L, 0x80FDE395L, 0x72966096L,
    0xA65C047DL, 0x5437877EL, 0x4767748AL, 0xB50CF789L,
    0xEB1FCBADL, 0x197448AEL, 0x0A24BB5AL, 0xF84F3859L,
    0x2C855CB2L, 0xDEEEDFB1L, 0xCDBE2C45L, 0x3FD5AF46L,
    0x7198540DL, 0x83F3D70EL, 0x90A324FAL, 0x62C8A7F9L,
    0xB602C312L, 0x44694011L, 0x5739B3E5L, 0xA55230E6L,
    0xFB410CC2L, 0x092A8FC1L, 0x1A7A7C35L, 0xE811FF36L,
    0x3CDB9BDDL, 0xCEB018DEL, 0xDDE0EB2AL, 0x2F8B6829L,
    0x82F63B78L, 0x709DB87BL, 0x63CD4B8FL, 0x91A6C88CL,
    0x456CAC67L, 0xB7072F64L, 0xA457DC90L, 0x563C5F93L,
    0x082F63B7L, 0xFA44E0B4L, 0xE9141340L, 0x1B7F9043L,
    0xCFB5F4A8L, 0x3DDE77ABL, 0x2E8E845FL, 0xDCE5075CL,
    0x92A8FC17L, 0x60C37F14L, 0x73938CE0L, 0x81F80FE3L,
    0x55326B08L, 0xA759E80BL, 0xB4091BFFL, 0x466298FCL,
    0x1871A4D8L, 0xEA1A27DBL, 0xF94AD42FL, 0x0B21572CL,
    0xDFEB33C7L, 0x2D80B0C4L, 0x3ED04330L, 0xCCBBC033L,
    0xA24BB5A6L, 0x502036A5L, 0x4370C551L, 0xB11B4652L,
    0x65D122B9L, 0x97BAA1BAL, 0x84EA524EL, 0x7681D14DL,
    0x2892ED69L, 0xDAF96E6AL, 0xC9A99D9EL, 0x3BC21E9DL,
    0xEF087A76L, 0x1D63F975L, 0x0E330A81L, 0xFC588982L,
    0xB21572C9L, 0x407EF1CAL, 0x532E023EL, 0xA145813DL,
    0x758FE5D6L, 0x87E466D5L, 0x94B49521L, 0x66DF1622L,
    0x38CC2A06L, 0xCAA7A905L, 0xD9F75AF1L, 0x2B9CD9F2L,
    0xFF56BD19L, 0x0D3D3E1AL, 0x1E6DCDEEL, 0xEC064EEDL,
    0xC38D26C4L, 0x31E6A5C7L, 0x22B65633L, 0xD0DDD530L,
    0x0417B1DBL, 0xF67C32D8L, 0xE52CC12CL, 0x1747422FL,
    0x49547E0BL, 0xBB3FFD08L, 0xA86F0EFCL, 0x5A048DFFL,
    0x8ECEE914L, 0x7CA56A17L, 0x6FF599E3L, 0x9D9E1AE0L,
    0xD3D3E1ABL, 0x21B862A8L, 0x32E8915CL, 0xC083125FL,
    0x144976B4L, 0xE622F5B7L, 0xF5720643L, 0x07198540L,
    0x590AB964L, 0xAB613A67L, 0xB831C993L, 0x4A5A4A90L,
    0x9E902E7BL, 0x6CFBAD78L, 0x7FAB5E8CL, 0x8DC0DD8FL,
    0xE330A81AL, 0x115B2B19L, 0x020BD8EDL, 0xF0605BEEL,
    0x24AA3F05L, 0xD6C1BC06L, 0xC5914FF2L, 0x37FACCF1L,
    0x69E9F0D5L, 0x9B8273D6L, 0x88D28022L, 0x7AB90321L,
    0xAE7367CAL, 0x5C18E4C9L, 0x4F48173DL, 0xBD23943EL,
    0xF36E6F75L, 0x0105EC76L, 0x12551F82L, 0xE03E9C81L,
    0x34F4F86AL, 0xC69F7B69L, 0xD5CF889DL, 0x27A40B9EL,
    0x79B737BAL, 0x8BDCB4B9L, 0x988C474DL, 0x6AE7C44EL,
    0xBE2DA0A5L, 0x4C4623A6L, 0x5F16D052L, 0xAD7D5351L
};

/*
 * Compute a CRC32c checksum as per the SCTP requirements in RFC4960. This
 * includes beginning with a checksum of all ones, and returning the negated
 * CRC. Unlike the RFC, we return the checksum in network byte-order.
 */
ovs_be32
crc32c(const uint8_t *data, size_t size)
{
    uint32_t crc = 0xffffffffL;

    while (size--) {
        crc = crc32Table[(crc ^ *data++) & 0xff] ^ (crc >> 8);
    }

    /* The result of this CRC calculation provides us a value in the reverse
     * byte-order as compared with our architecture. On big-endian systems,
     * this is opposite to our return type. So, to return a big-endian
     * value, we must swap the byte-order. */
#if defined(WORDS_BIGENDIAN)
    crc = uint32_byteswap(crc);
#endif

    /* Our value is in network byte-order. OVS_FORCE keeps sparse happy. */
    return (OVS_FORCE ovs_be32) ~crc;
}

Coverage Report

Created: 2023-03-26 07:41

Line	Count	Source (jump to first uncovered line)
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	0	{
143	0	uint32_t crc = 0xffffffffL;
144
145	0	while (size--) {
146	0	crc = crc32Table[(crc ^ *data++) & 0xff] ^ (crc >> 8);
147	0	}
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	0	return (OVS_FORCE ovs_be32) ~crc;
159	0	}