rpm 5.2.1

- Main Page
- Related Pages
- Modules
- Data Structures
- Files

- File List
- Globals

crc.c
Go to the documentation of this file.
1
5 #include "system.h"
6 #include "crc.h"
7 #include "debug.h"
8
9 /* ========================================================================= */
10 rpmuint32_t __crc32(rpmuint32_t crc, const rpmuint8_t * data, size_t size)
11 {
12 static rpmuint32_t polynomial = 0xedb88320; /* reflected 0x04c11db7 */
13 static rpmuint32_t xorout = 0xffffffff;
14 static rpmuint32_t table[256];
15
16 crc ^= xorout;
17
18 if (data == NULL) {
19 /* generate the table of CRC remainders for all possible bytes */
20 rpmuint32_t c;
21 rpmuint32_t i, j;
22 for (i = 0; i < 256; i++) {
23 c = i;
24 for (j = 0; j < 8; j++) {
25 if (c & 1)
26 c = polynomial ^ (c >> 1);
27 else
28 c = (c >> 1);
29 }
30 table[i] = c;
31 }
32 } else
33 while (size) {
34 crc = table[(crc ^ *data) & 0xff] ^ (crc >> 8);
35 size--;
36 data++;
37 }
38
39 crc ^= xorout;
40
41 return crc;
42
43 }
44
45 /*
46 * Swiped from zlib, using rpmuint32_t rather than unsigned long computation.
47 */
48 /*@unchecked@*/
49 static int gf2_dim32 = 32;
50
53 static rpmuint32_t gf2_matrix_times32(rpmuint32_t *mat, rpmuint32_t vec)
54 /*@*/
55 {
56 rpmuint32_t sum;
57
58 sum = 0;
59 while (vec) {
60 if (vec & 1)
61 sum ^= *mat;
62 vec >>= 1;
63 mat++;
64 }
65 return sum;
66 }
67
70 static void gf2_matrix_square32(/*@out@*/ rpmuint32_t *square, rpmuint32_t *mat)
71 /*@modifies square @*/
72 {
73 int n;
74
75 for (n = 0; n < gf2_dim32; n++)
76 square[n] = gf2_matrix_times32(mat, mat[n]);
77 }
78
79 rpmuint32_t __crc32_combine(rpmuint32_t crc1, rpmuint32_t crc2, size_t len2)
80 {
81 int n;
82 rpmuint32_t row;
83 size_t nb = gf2_dim32 * sizeof(row);
84 rpmuint32_t * even = alloca(nb); /* even-power-of-two zeros operator */
85 rpmuint32_t * odd = alloca(nb); /* odd-power-of-two zeros operator */
86
87 /* degenerate case */
88 if (len2 == 0)
89 return crc1;
90
91 /* put operator for one zero bit in odd */
92 odd[0] = 0xedb88320UL; /* CRC-32 polynomial */
93 row = 1;
94 for (n = 1; n < gf2_dim32; n++) {
95 odd[n] = row;
96 row <<= 1;
97 }
98
99 /* put operator for two zero bits in even */
100 gf2_matrix_square32(even, odd);
101
102 /* put operator for four zero bits in odd */
103 gf2_matrix_square32(odd, even);
104
105 /* apply len2 zeros to crc1 (first square will put the operator for one
106 zero byte, eight zero bits, in even) */
107 do {
108 /* apply zeros operator for this bit of len2 */
109 gf2_matrix_square32(even, odd);
110 if (len2 & 1)
111 crc1 = gf2_matrix_times32(even, crc1);
112 len2 >>= 1;
113
114 /* if no more bits set, then done */
115 if (len2 == 0)
116 break;
117
118 /* another iteration of the loop with odd and even swapped */
119 gf2_matrix_square32(odd, even);
120 if (len2 & 1)
121 crc1 = gf2_matrix_times32(odd, crc1);
122 len2 >>= 1;
123
124 /* if no more bits set, then done */
125 } while (len2 != 0);
126
127 /* return combined crc */
128 crc1 ^= crc2;
129 return crc1;
130 }
131
132 /* ========================================================================= */
133 /*
134 * ECMA-182 polynomial, see
135 * http://www.ecma-international.org/publications/files/ECMA-ST/Ecma-182.pdf
136 */
137 rpmuint64_t __crc64(rpmuint64_t crc, const rpmuint8_t * data, size_t size)
138 {
139 static rpmuint64_t polynomial =
140 0xc96c5795d7870f42ULL; /* reflected 0x42f0e1eba9ea3693ULL */
141 static rpmuint64_t xorout = 0xffffffffffffffffULL;
142 static rpmuint64_t table[256];
143
144 crc ^= xorout;
145
146 if (data == NULL) {
147 /* generate the table of CRC remainders for all possible bytes */
148 rpmuint64_t c;
149 rpmuint32_t i, j;
150 for (i = 0; i < 256; i++) {
151 c = i;
152 for (j = 0; j < 8; j++) {
153 if (c & 1)
154 c = polynomial ^ (c >> 1);
155 else
156 c = (c >> 1);
157 }
158 table[i] = c;
159 }
160 } else
161 while (size) {
162 crc = table[(crc ^ *data) & 0xff] ^ (crc >> 8);
163 size--;
164 data++;
165 }
166
167 crc ^= xorout;
168
169 return crc;
170
171 }
172
173 /*
174 * Swiped from zlib, using rpmuint64_t rather than unsigned long computation.
175 */
176 /*@unchecked@*/
177 static int gf2_dim64 = 64;
178
181 static rpmuint64_t gf2_matrix_times64(rpmuint64_t *mat, rpmuint64_t vec)
182 /*@*/
183 {
184 rpmuint64_t sum;
185
186 sum = 0;
187 while (vec) {
188 if (vec & 1)
189 sum ^= *mat;
190 vec >>= 1;
191 mat++;
192 }
193 return sum;
194 }
195
198 static void gf2_matrix_square64(/*@out@*/ rpmuint64_t *square, rpmuint64_t *mat)
199 /*@modifies square @*/
200 {
201 int n;
202
203 for (n = 0; n < gf2_dim64; n++)
204 square[n] = gf2_matrix_times64(mat, mat[n]);
205 }
206
207 rpmuint64_t __crc64_combine(rpmuint64_t crc1, rpmuint64_t crc2, size_t len2)
208 {
209 int n;
210 rpmuint64_t row;
211 size_t nb = gf2_dim64 * sizeof(row);
212 rpmuint64_t * even = alloca(nb); /* even-power-of-two zeros operator */
213 rpmuint64_t * odd = alloca(nb); /* odd-power-of-two zeros operator */
214
215 /* degenerate case */
216 if (len2 == 0)
217 return crc1;
218
219 /* put operator for one zero bit in odd */
220 odd[0] = 0xc96c5795d7870f42ULL; /* reflected 0x42f0e1eba9ea3693ULL */
221 row = 1;
222 for (n = 1; n < gf2_dim64; n++) {
223 odd[n] = row;
224 row <<= 1;
225 }
226
227 /* put operator for two zero bits in even */
228 gf2_matrix_square64(even, odd);
229
230 /* put operator for four zero bits in odd */
231 gf2_matrix_square64(odd, even);
232
233 /* apply len2 zeros to crc1 (first square will put the operator for one
234 zero byte, eight zero bits, in even) */
235 do {
236 /* apply zeros operator for this bit of len2 */
237 gf2_matrix_square64(even, odd);
238 if (len2 & 1)
239 crc1 = gf2_matrix_times64(even, crc1);
240 len2 >>= 1;
241
242 /* if no more bits set, then done */
243 if (len2 == 0)
244 break;
245
246 /* another iteration of the loop with odd and even swapped */
247 gf2_matrix_square64(odd, even);
248 if (len2 & 1)
249 crc1 = gf2_matrix_times64(odd, crc1);
250 len2 >>= 1;
251
252 /* if no more bits set, then done */
253 } while (len2 != 0);
254
255 /* return combined crc */
256 crc1 ^= crc2;
257 return crc1;
258 }
259
260 /* ========================================================================= */
261 /* adler32.c -- compute the Adler-32 checksum of a data stream
262 * Copyright (C) 1995-2004 Mark Adler
263 * For conditions of distribution and use, see copyright notice in zlib.h
264 */
265
266 #define BASE 65521UL /* largest prime smaller than 65536 */
267 #define NMAX 5552
268 /* NMAX is the largest n such that 255n(n+1)/2 + (n+1)(BASE-1) <= 2^32-1 */
269
270 #define DO1(buf,i) {adler += (rpmuint32_t) (buf)[i]; sum2 += adler;}
271 #define DO2(buf,i) DO1(buf,i); DO1(buf,i+1);
272 #define DO4(buf,i) DO2(buf,i); DO2(buf,i+2);
273 #define DO8(buf,i) DO4(buf,i); DO4(buf,i+4);
274 #define DO16(buf) DO8(buf,0); DO8(buf,8);
275
276 /* use NO_DIVIDE if your processor does not do division in hardware */
277 #ifdef NO_DIVIDE
278 # define MOD(a) \
279 do { \
280 if (a >= (BASE << 16)) a -= (BASE << 16); \
281 if (a >= (BASE << 15)) a -= (BASE << 15); \
282 if (a >= (BASE << 14)) a -= (BASE << 14); \
283 if (a >= (BASE << 13)) a -= (BASE << 13); \
284 if (a >= (BASE << 12)) a -= (BASE << 12); \
285 if (a >= (BASE << 11)) a -= (BASE << 11); \
286 if (a >= (BASE << 10)) a -= (BASE << 10); \
287 if (a >= (BASE << 9)) a -= (BASE << 9); \
288 if (a >= (BASE << 8)) a -= (BASE << 8); \
289 if (a >= (BASE << 7)) a -= (BASE << 7); \
290 if (a >= (BASE << 6)) a -= (BASE << 6); \
291 if (a >= (BASE << 5)) a -= (BASE << 5); \
292 if (a >= (BASE << 4)) a -= (BASE << 4); \
293 if (a >= (BASE << 3)) a -= (BASE << 3); \
294 if (a >= (BASE << 2)) a -= (BASE << 2); \
295 if (a >= (BASE << 1)) a -= (BASE << 1); \
296 if (a >= BASE) a -= BASE; \
297 } while (0)
298 # define MOD4(a) \
299 do { \
300 if (a >= (BASE << 4)) a -= (BASE << 4); \
301 if (a >= (BASE << 3)) a -= (BASE << 3); \
302 if (a >= (BASE << 2)) a -= (BASE << 2); \
303 if (a >= (BASE << 1)) a -= (BASE << 1); \
304 if (a >= BASE) a -= BASE; \
305 } while (0)
306 #else
307 # define MOD(a) a %= BASE
308 # define MOD4(a) a %= BASE
309 #endif
310
311 rpmuint32_t __adler32(rpmuint32_t adler, const rpmuint8_t * buf, rpmuint32_t len)
312 {
313 rpmuint32_t sum2;
314 unsigned n;
315
316 /* split Adler-32 into component sums */
317 sum2 = (adler >> 16) & 0xffff;
318 adler &= 0xffff;
319
320 /* in case user likes doing a byte at a time, keep it fast */
321 if (len == 1) {
322 adler += (rpmuint32_t) buf[0];
323 if (adler >= BASE)
324 adler -= BASE;
325 sum2 += adler;
326 if (sum2 >= BASE)
327 sum2 -= BASE;
328 return adler | (sum2 << 16);
329 }
330
331 /* initial Adler-32 value (deferred check for len == 1 speed) */
332 if (buf == NULL)
333 return 1UL;
334
335 /* in case short lengths are provided, keep it somewhat fast */
336 if (len < 16) {
337 while (len--) {
338 adler += (rpmuint32_t) *buf++;
339 sum2 += adler;
340 }
341 if (adler >= BASE)
342 adler -= BASE;
343 MOD4(sum2); /* only added so many BASE's */
344 return adler | (sum2 << 16);
345 }
346
347 /* do length NMAX blocks -- requires just one modulo operation */
348 while (len >= NMAX) {
349 len -= NMAX;
350 n = NMAX / 16; /* NMAX is divisible by 16 */
351 do {
352 DO16(buf); /* 16 sums unrolled */
353 buf += 16;
354 } while (--n);
355 MOD(adler);
356 MOD(sum2);
357 }
358
359 /* do remaining bytes (less than NMAX, still just one modulo) */
360 if (len) { /* avoid modulos if none remaining */
361 while (len >= 16) {
362 len -= 16;
363 DO16(buf);
364 buf += 16;
365 }
366 while (len--) {
367 adler += (rpmuint32_t) *buf++;
368 sum2 += adler;
369 }
370 MOD(adler);
371 MOD(sum2);
372 }
373
374 /* return recombined sums */
375 return adler | (sum2 << 16);
376 }
377
378 rpmuint32_t __adler32_combine(rpmuint32_t adler1, rpmuint32_t adler2, size_t len2)
379 /*@*/
380 {
381 rpmuint32_t sum1;
382 rpmuint32_t sum2;
383 unsigned rem;
384
385 /* the derivation of this formula is left as an exercise for the reader */
386 rem = (unsigned)(len2 % BASE);
387 sum1 = adler1 & 0xffff;
388 sum2 = rem * sum1;
389 MOD(sum2);
390 sum1 += (adler2 & 0xffff) + BASE - 1;
391 sum2 += ((adler1 >> 16) & 0xffff) + ((adler2 >> 16) & 0xffff) + BASE - rem;
392 if (sum1 > BASE) sum1 -= BASE;
393 if (sum1 > BASE) sum1 -= BASE;
394 if (sum2 > (BASE << 1)) sum2 -= (BASE << 1);
395 if (sum2 > BASE) sum2 -= BASE;
396 return sum1 | (sum2 << 16);
397 }
398
399 int sum32Reset(register sum32Param * mp)
400 {
401 if (mp->update)
402 mp->crc = (*mp->update) (0, NULL, 0);
403 return 0;
404 }
405
406 int sum32Update(sum32Param * mp, const rpmuint8_t * data, size_t size)
407 {
408 if (mp->update)
409 mp->crc = (*mp->update) (mp->crc, data, size);
410 return 0;
411 }
412
413 int sum32Digest(sum32Param * mp, rpmuint8_t * data)
414 {
415 rpmuint32_t c = mp->crc;
416
417 data[ 0] = (rpmuint8_t)(c >> 24);
418 data[ 1] = (rpmuint8_t)(c >> 16);
419 data[ 2] = (rpmuint8_t)(c >> 8);
420 data[ 3] = (rpmuint8_t)(c );
421
422 (void) sum32Reset(mp);
423
424 return 0;
425 }
426
427 int sum64Reset(register sum64Param * mp)
428 {
429 if (mp->update)
430 mp->crc = (*mp->update) (0, NULL, 0);
431 return 0;
432 }
433
434 int sum64Update(sum64Param * mp, const rpmuint8_t * data, size_t size)
435 {
436 if (mp->update)
437 mp->crc = (*mp->update) (mp->crc, data, size);
438 return 0;
439 }
440
441 int sum64Digest(sum64Param * mp, rpmuint8_t * data)
442 {
443 rpmuint64_t c = mp->crc;
444
445 data[ 0] = (rpmuint8_t)(c >> 56);
446 data[ 1] = (rpmuint8_t)(c >> 48);
447 data[ 2] = (rpmuint8_t)(c >> 40);
448 data[ 3] = (rpmuint8_t)(c >> 32);
449 data[ 4] = (rpmuint8_t)(c >> 24);
450 data[ 5] = (rpmuint8_t)(c >> 16);
451 data[ 6] = (rpmuint8_t)(c >> 8);
452 data[ 7] = (rpmuint8_t)(c );
453
454 (void) sum64Reset(mp);
455
456 return 0;
457 }