rpm  5.2.1
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 
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 
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 
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 
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 
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 
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 
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 
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 }