| blob | 0a72a31ec41525baec7aba1f63e4032836edd0a1 |
1 /*\r
2 * CRC32 implementation.\r
3 *\r
4 * The basic concept of a CRC is that you treat your bit-string\r
5 * abcdefg... as a ludicrously long polynomial M=a+bx+cx^2+dx^3+...\r
6 * over Z[2]. You then take a modulus polynomial P, and compute the\r
7 * remainder of M on division by P. Thus, an erroneous message N\r
8 * will only have the same CRC if the difference E = M-N is an\r
9 * exact multiple of P. (Note that as we are working over Z[2], M-N\r
10 * = N-M = M+N; but that's not very important.)\r
11 *\r
12 * What makes the CRC good is choosing P to have good properties:\r
13 *\r
14 * - If its first and last terms are both nonzero then it cannot\r
15 * be a factor of any single term x^i. Therefore if M and N\r
16 * differ by exactly one bit their CRCs will guaranteeably\r
17 * be distinct.\r
18 *\r
19 * - If it has a prime (irreducible) factor with three terms then\r
20 * it cannot divide a polynomial of the form x^i(1+x^j).\r
21 * Therefore if M and N differ by exactly _two_ bits they will\r
22 * have different CRCs.\r
23 *\r
24 * - If it has a factor (x+1) then it cannot divide a polynomial\r
25 * with an odd number of terms. Therefore if M and N differ by\r
26 * _any odd_ number of bits they will have different CRCs.\r
27 *\r
28 * - If the error term E is of the form x^i*B(x) where B(x) has\r
29 * order less than P (i.e. a short _burst_ of errors) then P\r
30 * cannot divide E (since no polynomial can divide a shorter\r
31 * one), so any such error burst will be spotted.\r
32 *\r
33 * The CRC32 standard polynomial is\r
34 * 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\r
35 *\r
36 * In fact, we don't compute M mod P; we compute M*x^32 mod P.\r
37 *\r
38 * The concrete implementation of the CRC is this: we maintain at\r
39 * all times a 32-bit word which is the current remainder of the\r
40 * polynomial mod P. Whenever we receive an extra bit, we multiply\r
41 * the existing remainder by x, add (XOR) the x^32 term thus\r
42 * generated to the new x^32 term caused by the incoming bit, and\r
43 * remove the resulting combined x^32 term if present by replacing\r
44 * it with (P-x^32).\r
45 *\r
46 * Bit 0 of the word is the x^31 term and bit 31 is the x^0 term.\r
47 * Thus, multiplying by x means shifting right. So the actual\r
48 * algorithm goes like this:\r
49 *\r
50 * x32term = (crcword & 1) ^ newbit;\r
51 * crcword = (crcword >> 1) ^ (x32term * 0xEDB88320);\r
52 *\r
53 * In practice, we pre-compute what will happen to crcword on any\r
54 * given sequence of eight incoming bits, and store that in a table\r
55 * which we then use at run-time to do the job:\r
56 * \r
57 * outgoingplusnew = (crcword & 0xFF) ^ newbyte;\r
58 * crcword = (crcword >> 8) ^ table[outgoingplusnew];\r
59 *\r
60 * where table[outgoingplusnew] is computed by setting crcword=0\r
61 * and then iterating the first code fragment eight times (taking\r
62 * the incoming byte low bit first).\r
63 *\r
64 * Note that all shifts are rightward and thus no assumption is\r
65 * made about exact word length! (Although word length must be at\r
66 * _least_ 32 bits, but ANSI C guarantees this for `unsigned long'\r
67 * anyway.)\r
68 */\r
69 \r
70 #include <stdlib.h>\r
71 \r
72 #include "ssh.h"\r
73 \r
74 /* ----------------------------------------------------------------------\r
75 * Multi-function module. Can be compiled three ways.\r
76 *\r
77 * - Compile with no special #defines. Will generate a table\r
78 * that's already initialised at compile time, and one function\r
79 * crc32_compute(buf,len) that uses it. Normal usage.\r
80 *\r
81 * - Compile with INITFUNC defined. Will generate an uninitialised\r
82 * array as the table, and as well as crc32_compute(buf,len) it\r
83 * will also generate void crc32_init(void) which sets up the\r
84 * table at run time. Useful if binary size is important.\r
85 *\r
86 * - Compile with GENPROGRAM defined. Will create a standalone\r
87 * program that does the initialisation and outputs the table as\r
88 * C code.\r
89 */\r
90 \r
91 #define POLY (0xEDB88320L)\r
92 \r
93 #ifdef GENPROGRAM\r
94 #define INITFUNC /* the gen program needs the init func :-) */\r
95 #endif\r
96 \r
97 #ifdef INITFUNC\r
98 \r
99 /*\r
100 * This variant of the code generates the table at run-time from an\r
101 * init function.\r
102 */\r
103 static unsigned long crc32_table[256];\r
104 \r
105 void crc32_init(void)\r
106 {\r
107 unsigned long crcword;\r
108 int i;\r
109 \r
110 for (i = 0; i < 256; i++) {\r
111 unsigned long newbyte, x32term;\r
112 int j;\r
113 crcword = 0;\r
114 newbyte = i;\r
115 for (j = 0; j < 8; j++) {\r
116 x32term = (crcword ^ newbyte) & 1;\r
117 crcword = (crcword >> 1) ^ (x32term * POLY);\r
118 newbyte >>= 1;\r
119 }\r
120 crc32_table[i] = crcword;\r
121 }\r
122 }\r
123 \r
124 #else\r
125 \r
126 /*\r
127 * This variant of the code has the data already prepared.\r
128 */\r
129 static const unsigned long crc32_table[256] = {\r
130 0x00000000L, 0x77073096L, 0xEE0E612CL, 0x990951BAL,\r
131 0x076DC419L, 0x706AF48FL, 0xE963A535L, 0x9E6495A3L,\r
132 0x0EDB8832L, 0x79DCB8A4L, 0xE0D5E91EL, 0x97D2D988L,\r
133 0x09B64C2BL, 0x7EB17CBDL, 0xE7B82D07L, 0x90BF1D91L,\r
134 0x1DB71064L, 0x6AB020F2L, 0xF3B97148L, 0x84BE41DEL,\r
135 0x1ADAD47DL, 0x6DDDE4EBL, 0xF4D4B551L, 0x83D385C7L,\r
136 0x136C9856L, 0x646BA8C0L, 0xFD62F97AL, 0x8A65C9ECL,\r
137 0x14015C4FL, 0x63066CD9L, 0xFA0F3D63L, 0x8D080DF5L,\r
138 0x3B6E20C8L, 0x4C69105EL, 0xD56041E4L, 0xA2677172L,\r
139 0x3C03E4D1L, 0x4B04D447L, 0xD20D85FDL, 0xA50AB56BL,\r
140 0x35B5A8FAL, 0x42B2986CL, 0xDBBBC9D6L, 0xACBCF940L,\r
141 0x32D86CE3L, 0x45DF5C75L, 0xDCD60DCFL, 0xABD13D59L,\r
142 0x26D930ACL, 0x51DE003AL, 0xC8D75180L, 0xBFD06116L,\r
143 0x21B4F4B5L, 0x56B3C423L, 0xCFBA9599L, 0xB8BDA50FL,\r
144 0x2802B89EL, 0x5F058808L, 0xC60CD9B2L, 0xB10BE924L,\r
145 0x2F6F7C87L, 0x58684C11L, 0xC1611DABL, 0xB6662D3DL,\r
146 0x76DC4190L, 0x01DB7106L, 0x98D220BCL, 0xEFD5102AL,\r
147 0x71B18589L, 0x06B6B51FL, 0x9FBFE4A5L, 0xE8B8D433L,\r
148 0x7807C9A2L, 0x0F00F934L, 0x9609A88EL, 0xE10E9818L,\r
149 0x7F6A0DBBL, 0x086D3D2DL, 0x91646C97L, 0xE6635C01L,\r
150 0x6B6B51F4L, 0x1C6C6162L, 0x856530D8L, 0xF262004EL,\r
151 0x6C0695EDL, 0x1B01A57BL, 0x8208F4C1L, 0xF50FC457L,\r
152 0x65B0D9C6L, 0x12B7E950L, 0x8BBEB8EAL, 0xFCB9887CL,\r
153 0x62DD1DDFL, 0x15DA2D49L, 0x8CD37CF3L, 0xFBD44C65L,\r
154 0x4DB26158L, 0x3AB551CEL, 0xA3BC0074L, 0xD4BB30E2L,\r
155 0x4ADFA541L, 0x3DD895D7L, 0xA4D1C46DL, 0xD3D6F4FBL,\r
156 0x4369E96AL, 0x346ED9FCL, 0xAD678846L, 0xDA60B8D0L,\r
157 0x44042D73L, 0x33031DE5L, 0xAA0A4C5FL, 0xDD0D7CC9L,\r
158 0x5005713CL, 0x270241AAL, 0xBE0B1010L, 0xC90C2086L,\r
159 0x5768B525L, 0x206F85B3L, 0xB966D409L, 0xCE61E49FL,\r
160 0x5EDEF90EL, 0x29D9C998L, 0xB0D09822L, 0xC7D7A8B4L,\r
161 0x59B33D17L, 0x2EB40D81L, 0xB7BD5C3BL, 0xC0BA6CADL,\r
162 0xEDB88320L, 0x9ABFB3B6L, 0x03B6E20CL, 0x74B1D29AL,\r
163 0xEAD54739L, 0x9DD277AFL, 0x04DB2615L, 0x73DC1683L,\r
164 0xE3630B12L, 0x94643B84L, 0x0D6D6A3EL, 0x7A6A5AA8L,\r
165 0xE40ECF0BL, 0x9309FF9DL, 0x0A00AE27L, 0x7D079EB1L,\r
166 0xF00F9344L, 0x8708A3D2L, 0x1E01F268L, 0x6906C2FEL,\r
167 0xF762575DL, 0x806567CBL, 0x196C3671L, 0x6E6B06E7L,\r
168 0xFED41B76L, 0x89D32BE0L, 0x10DA7A5AL, 0x67DD4ACCL,\r
169 0xF9B9DF6FL, 0x8EBEEFF9L, 0x17B7BE43L, 0x60B08ED5L,\r
170 0xD6D6A3E8L, 0xA1D1937EL, 0x38D8C2C4L, 0x4FDFF252L,\r
171 0xD1BB67F1L, 0xA6BC5767L, 0x3FB506DDL, 0x48B2364BL,\r
172 0xD80D2BDAL, 0xAF0A1B4CL, 0x36034AF6L, 0x41047A60L,\r
173 0xDF60EFC3L, 0xA867DF55L, 0x316E8EEFL, 0x4669BE79L,\r
174 0xCB61B38CL, 0xBC66831AL, 0x256FD2A0L, 0x5268E236L,\r
175 0xCC0C7795L, 0xBB0B4703L, 0x220216B9L, 0x5505262FL,\r
176 0xC5BA3BBEL, 0xB2BD0B28L, 0x2BB45A92L, 0x5CB36A04L,\r
177 0xC2D7FFA7L, 0xB5D0CF31L, 0x2CD99E8BL, 0x5BDEAE1DL,\r
178 0x9B64C2B0L, 0xEC63F226L, 0x756AA39CL, 0x026D930AL,\r
179 0x9C0906A9L, 0xEB0E363FL, 0x72076785L, 0x05005713L,\r
180 0x95BF4A82L, 0xE2B87A14L, 0x7BB12BAEL, 0x0CB61B38L,\r
181 0x92D28E9BL, 0xE5D5BE0DL, 0x7CDCEFB7L, 0x0BDBDF21L,\r
182 0x86D3D2D4L, 0xF1D4E242L, 0x68DDB3F8L, 0x1FDA836EL,\r
183 0x81BE16CDL, 0xF6B9265BL, 0x6FB077E1L, 0x18B74777L,\r
184 0x88085AE6L, 0xFF0F6A70L, 0x66063BCAL, 0x11010B5CL,\r
185 0x8F659EFFL, 0xF862AE69L, 0x616BFFD3L, 0x166CCF45L,\r
186 0xA00AE278L, 0xD70DD2EEL, 0x4E048354L, 0x3903B3C2L,\r
187 0xA7672661L, 0xD06016F7L, 0x4969474DL, 0x3E6E77DBL,\r
188 0xAED16A4AL, 0xD9D65ADCL, 0x40DF0B66L, 0x37D83BF0L,\r
189 0xA9BCAE53L, 0xDEBB9EC5L, 0x47B2CF7FL, 0x30B5FFE9L,\r
190 0xBDBDF21CL, 0xCABAC28AL, 0x53B39330L, 0x24B4A3A6L,\r
191 0xBAD03605L, 0xCDD70693L, 0x54DE5729L, 0x23D967BFL,\r
192 0xB3667A2EL, 0xC4614AB8L, 0x5D681B02L, 0x2A6F2B94L,\r
193 0xB40BBE37L, 0xC30C8EA1L, 0x5A05DF1BL, 0x2D02EF8DL\r
194 };\r
195 \r
196 #endif\r
197 \r
198 #ifdef GENPROGRAM\r
199 int main(void)\r
200 {\r
201 unsigned long crcword;\r
202 int i;\r
203 \r
204 crc32_init();\r
205 for (i = 0; i < 256; i++) {\r
206 printf("%s0x%08XL%s",\r
207 (i % 4 == 0 ? " " : " "),\r
208 crc32_table[i],\r
209 (i % 4 == 3 ? (i == 255 ? "\n" : ",\n") : ","));\r
210 }\r
211 \r
212 return 0;\r
213 }\r
214 #endif\r
215 \r
216 unsigned long crc32_update(unsigned long crcword, const void *buf, size_t len)\r
217 {\r
218 const unsigned char *p = (const unsigned char *) buf;\r
219 while (len--) {\r
220 unsigned long newbyte = *p++;\r
221 newbyte ^= crcword & 0xFFL;\r
222 crcword = (crcword >> 8) ^ crc32_table[newbyte];\r
223 }\r
224 return crcword;\r
225 }\r
226 \r
227 unsigned long crc32_compute(const void *buf, size_t len)\r
228 {\r
229 return crc32_update(0L, buf, len);\r
230 }\r