/src/mozilla-central/xpcom/io/crc32c.c

Source (jump to first uncovered line)
/*
 * Based on file found here:
 *
 *   https://svnweb.freebsd.org/base/stable/10/sys/libkern/crc32.c?revision=256281
 */

/*-
 *  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
 *      is shown later.  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 "crc32c.h"

/* CRC32C routines, these use a different polynomial */
/*****************************************************************/
/*                                                               */
/* 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
};

// NOTE: See source URL at top of this file for multitable implementation which
//       offers a performance boost at the cost of ~8KB of static tables.

uint32_t
ComputeCrc32c(uint32_t crc, const void *buf, size_t size)
{
  const uint8_t *p = buf;


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

  return crc;
}

Coverage Report

Created: 2018-09-25 14:53

Line	Count	Source (jump to first uncovered line)
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	0	{
147	0	const uint8_t *p = buf;
148	0
149	0
150	0	while (size--)
151	0	crc = crc32Table[(crc ^ *p++) & 0xff] ^ (crc >> 8);
152	0
153	0	return crc;
154	0	}