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