rpm 5.3.12
|
00001 00005 #include "system.h" 00006 #include "crc.h" 00007 #include "debug.h" 00008 00009 /* ========================================================================= */ 00010 rpmuint32_t __crc32(rpmuint32_t crc, const rpmuint8_t * data, size_t size) 00011 { 00012 static rpmuint32_t polynomial = 0xedb88320; /* reflected 0x04c11db7 */ 00013 static rpmuint32_t xorout = 0xffffffff; 00014 static rpmuint32_t table[256]; 00015 static int oneshot = 0; 00016 00017 crc ^= xorout; 00018 00019 if (!oneshot) { 00020 /* generate the table of CRC remainders for all possible bytes */ 00021 rpmuint32_t c; 00022 rpmuint32_t i, j; 00023 for (i = 0; i < 256; i++) { 00024 c = i; 00025 for (j = 0; j < 8; j++) { 00026 if (c & 1) 00027 c = polynomial ^ (c >> 1); 00028 else 00029 c = (c >> 1); 00030 } 00031 table[i] = c; 00032 } 00033 oneshot = 1; 00034 } 00035 if (data != NULL) 00036 while (size) { 00037 crc = table[(crc ^ *data) & 0xff] ^ (crc >> 8); 00038 size--; 00039 data++; 00040 } 00041 00042 crc ^= xorout; 00043 00044 return crc; 00045 00046 } 00047 00048 /* 00049 * Swiped from zlib, using rpmuint32_t rather than unsigned long computation. 00050 */ 00051 /*@unchecked@*/ 00052 static int gf2_dim32 = 32; 00053 00056 static rpmuint32_t gf2_matrix_times32(rpmuint32_t *mat, rpmuint32_t vec) 00057 /*@*/ 00058 { 00059 rpmuint32_t sum; 00060 00061 sum = 0; 00062 while (vec) { 00063 if (vec & 1) 00064 sum ^= *mat; 00065 vec >>= 1; 00066 mat++; 00067 } 00068 return sum; 00069 } 00070 00073 static void gf2_matrix_square32(/*@out@*/ rpmuint32_t *square, rpmuint32_t *mat) 00074 /*@modifies square @*/ 00075 { 00076 int n; 00077 00078 for (n = 0; n < gf2_dim32; n++) 00079 square[n] = gf2_matrix_times32(mat, mat[n]); 00080 } 00081 00082 rpmuint32_t __crc32_combine(rpmuint32_t crc1, rpmuint32_t crc2, size_t len2) 00083 { 00084 int n; 00085 rpmuint32_t row; 00086 size_t nb = gf2_dim32 * sizeof(row); 00087 rpmuint32_t * even = alloca(nb); /* even-power-of-two zeros operator */ 00088 rpmuint32_t * odd = alloca(nb); /* odd-power-of-two zeros operator */ 00089 00090 /* degenerate case */ 00091 if (len2 == 0) 00092 return crc1; 00093 00094 /* put operator for one zero bit in odd */ 00095 odd[0] = 0xedb88320UL; /* CRC-32 polynomial */ 00096 row = 1; 00097 for (n = 1; n < gf2_dim32; n++) { 00098 odd[n] = row; 00099 row <<= 1; 00100 } 00101 00102 /* put operator for two zero bits in even */ 00103 gf2_matrix_square32(even, odd); 00104 00105 /* put operator for four zero bits in odd */ 00106 gf2_matrix_square32(odd, even); 00107 00108 /* apply len2 zeros to crc1 (first square will put the operator for one 00109 zero byte, eight zero bits, in even) */ 00110 do { 00111 /* apply zeros operator for this bit of len2 */ 00112 gf2_matrix_square32(even, odd); 00113 if (len2 & 1) 00114 crc1 = gf2_matrix_times32(even, crc1); 00115 len2 >>= 1; 00116 00117 /* if no more bits set, then done */ 00118 if (len2 == 0) 00119 break; 00120 00121 /* another iteration of the loop with odd and even swapped */ 00122 gf2_matrix_square32(odd, even); 00123 if (len2 & 1) 00124 crc1 = gf2_matrix_times32(odd, crc1); 00125 len2 >>= 1; 00126 00127 /* if no more bits set, then done */ 00128 } while (len2 != 0); 00129 00130 /* return combined crc */ 00131 crc1 ^= crc2; 00132 return crc1; 00133 } 00134 00135 /* ========================================================================= */ 00136 /* 00137 * ECMA-182 polynomial, see 00138 * http://www.ecma-international.org/publications/files/ECMA-ST/Ecma-182.pdf 00139 */ 00140 rpmuint64_t __crc64(rpmuint64_t crc, const rpmuint8_t * data, size_t size) 00141 { 00142 static rpmuint64_t polynomial = 00143 0xc96c5795d7870f42ULL; /* reflected 0x42f0e1eba9ea3693ULL */ 00144 static rpmuint64_t xorout = 0xffffffffffffffffULL; 00145 static rpmuint64_t table[256]; 00146 static int oneshot = 0; 00147 00148 crc ^= xorout; 00149 00150 if (!oneshot) { 00151 /* generate the table of CRC remainders for all possible bytes */ 00152 rpmuint64_t c; 00153 rpmuint32_t i, j; 00154 for (i = 0; i < 256; i++) { 00155 c = i; 00156 for (j = 0; j < 8; j++) { 00157 if (c & 1) 00158 c = polynomial ^ (c >> 1); 00159 else 00160 c = (c >> 1); 00161 } 00162 table[i] = c; 00163 } 00164 oneshot = 1; 00165 } 00166 if (data != NULL) 00167 while (size) { 00168 crc = table[(crc ^ *data) & 0xff] ^ (crc >> 8); 00169 size--; 00170 data++; 00171 } 00172 00173 crc ^= xorout; 00174 00175 return crc; 00176 00177 } 00178 00179 /* 00180 * Swiped from zlib, using rpmuint64_t rather than unsigned long computation. 00181 */ 00182 /*@unchecked@*/ 00183 static int gf2_dim64 = 64; 00184 00187 static rpmuint64_t gf2_matrix_times64(rpmuint64_t *mat, rpmuint64_t vec) 00188 /*@*/ 00189 { 00190 rpmuint64_t sum; 00191 00192 sum = 0; 00193 while (vec) { 00194 if (vec & 1) 00195 sum ^= *mat; 00196 vec >>= 1; 00197 mat++; 00198 } 00199 return sum; 00200 } 00201 00204 static void gf2_matrix_square64(/*@out@*/ rpmuint64_t *square, rpmuint64_t *mat) 00205 /*@modifies square @*/ 00206 { 00207 int n; 00208 00209 for (n = 0; n < gf2_dim64; n++) 00210 square[n] = gf2_matrix_times64(mat, mat[n]); 00211 } 00212 00213 rpmuint64_t __crc64_combine(rpmuint64_t crc1, rpmuint64_t crc2, size_t len2) 00214 { 00215 int n; 00216 rpmuint64_t row; 00217 size_t nb = gf2_dim64 * sizeof(row); 00218 rpmuint64_t * even = alloca(nb); /* even-power-of-two zeros operator */ 00219 rpmuint64_t * odd = alloca(nb); /* odd-power-of-two zeros operator */ 00220 00221 /* degenerate case */ 00222 if (len2 == 0) 00223 return crc1; 00224 00225 /* put operator for one zero bit in odd */ 00226 odd[0] = 0xc96c5795d7870f42ULL; /* reflected 0x42f0e1eba9ea3693ULL */ 00227 row = 1; 00228 for (n = 1; n < gf2_dim64; n++) { 00229 odd[n] = row; 00230 row <<= 1; 00231 } 00232 00233 /* put operator for two zero bits in even */ 00234 gf2_matrix_square64(even, odd); 00235 00236 /* put operator for four zero bits in odd */ 00237 gf2_matrix_square64(odd, even); 00238 00239 /* apply len2 zeros to crc1 (first square will put the operator for one 00240 zero byte, eight zero bits, in even) */ 00241 do { 00242 /* apply zeros operator for this bit of len2 */ 00243 gf2_matrix_square64(even, odd); 00244 if (len2 & 1) 00245 crc1 = gf2_matrix_times64(even, crc1); 00246 len2 >>= 1; 00247 00248 /* if no more bits set, then done */ 00249 if (len2 == 0) 00250 break; 00251 00252 /* another iteration of the loop with odd and even swapped */ 00253 gf2_matrix_square64(odd, even); 00254 if (len2 & 1) 00255 crc1 = gf2_matrix_times64(odd, crc1); 00256 len2 >>= 1; 00257 00258 /* if no more bits set, then done */ 00259 } while (len2 != 0); 00260 00261 /* return combined crc */ 00262 crc1 ^= crc2; 00263 return crc1; 00264 } 00265 00266 /* ========================================================================= */ 00267 /* adler32.c -- compute the Adler-32 checksum of a data stream 00268 * Copyright (C) 1995-2004 Mark Adler 00269 * For conditions of distribution and use, see copyright notice in zlib.h 00270 */ 00271 00272 #define BASE 65521UL /* largest prime smaller than 65536 */ 00273 #define NMAX 5552 00274 /* NMAX is the largest n such that 255n(n+1)/2 + (n+1)(BASE-1) <= 2^32-1 */ 00275 00276 #define DO1(buf,i) {adler += (rpmuint32_t) (buf)[i]; sum2 += adler;} 00277 #define DO2(buf,i) DO1(buf,i); DO1(buf,i+1); 00278 #define DO4(buf,i) DO2(buf,i); DO2(buf,i+2); 00279 #define DO8(buf,i) DO4(buf,i); DO4(buf,i+4); 00280 #define DO16(buf) DO8(buf,0); DO8(buf,8); 00281 00282 /* use NO_DIVIDE if your processor does not do division in hardware */ 00283 #ifdef NO_DIVIDE 00284 # define MOD(a) \ 00285 do { \ 00286 if (a >= (BASE << 16)) a -= (BASE << 16); \ 00287 if (a >= (BASE << 15)) a -= (BASE << 15); \ 00288 if (a >= (BASE << 14)) a -= (BASE << 14); \ 00289 if (a >= (BASE << 13)) a -= (BASE << 13); \ 00290 if (a >= (BASE << 12)) a -= (BASE << 12); \ 00291 if (a >= (BASE << 11)) a -= (BASE << 11); \ 00292 if (a >= (BASE << 10)) a -= (BASE << 10); \ 00293 if (a >= (BASE << 9)) a -= (BASE << 9); \ 00294 if (a >= (BASE << 8)) a -= (BASE << 8); \ 00295 if (a >= (BASE << 7)) a -= (BASE << 7); \ 00296 if (a >= (BASE << 6)) a -= (BASE << 6); \ 00297 if (a >= (BASE << 5)) a -= (BASE << 5); \ 00298 if (a >= (BASE << 4)) a -= (BASE << 4); \ 00299 if (a >= (BASE << 3)) a -= (BASE << 3); \ 00300 if (a >= (BASE << 2)) a -= (BASE << 2); \ 00301 if (a >= (BASE << 1)) a -= (BASE << 1); \ 00302 if (a >= BASE) a -= BASE; \ 00303 } while (0) 00304 # define MOD4(a) \ 00305 do { \ 00306 if (a >= (BASE << 4)) a -= (BASE << 4); \ 00307 if (a >= (BASE << 3)) a -= (BASE << 3); \ 00308 if (a >= (BASE << 2)) a -= (BASE << 2); \ 00309 if (a >= (BASE << 1)) a -= (BASE << 1); \ 00310 if (a >= BASE) a -= BASE; \ 00311 } while (0) 00312 #else 00313 # define MOD(a) a %= BASE 00314 # define MOD4(a) a %= BASE 00315 #endif 00316 00317 rpmuint32_t __adler32(rpmuint32_t adler, const rpmuint8_t * buf, rpmuint32_t len) 00318 { 00319 rpmuint32_t sum2; 00320 unsigned n; 00321 00322 /* split Adler-32 into component sums */ 00323 sum2 = (adler >> 16) & 0xffff; 00324 adler &= 0xffff; 00325 00326 /* in case user likes doing a byte at a time, keep it fast */ 00327 if (len == 1) { 00328 adler += (rpmuint32_t) buf[0]; 00329 if (adler >= BASE) 00330 adler -= BASE; 00331 sum2 += adler; 00332 if (sum2 >= BASE) 00333 sum2 -= BASE; 00334 return adler | (sum2 << 16); 00335 } 00336 00337 /* initial Adler-32 value (deferred check for len == 1 speed) */ 00338 if (buf == NULL) 00339 return 1UL; 00340 00341 /* in case short lengths are provided, keep it somewhat fast */ 00342 if (len < 16) { 00343 while (len--) { 00344 adler += (rpmuint32_t) *buf++; 00345 sum2 += adler; 00346 } 00347 if (adler >= BASE) 00348 adler -= BASE; 00349 MOD4(sum2); /* only added so many BASE's */ 00350 return adler | (sum2 << 16); 00351 } 00352 00353 /* do length NMAX blocks -- requires just one modulo operation */ 00354 while (len >= NMAX) { 00355 len -= NMAX; 00356 n = NMAX / 16; /* NMAX is divisible by 16 */ 00357 do { 00358 DO16(buf); /* 16 sums unrolled */ 00359 buf += 16; 00360 } while (--n); 00361 MOD(adler); 00362 MOD(sum2); 00363 } 00364 00365 /* do remaining bytes (less than NMAX, still just one modulo) */ 00366 if (len) { /* avoid modulos if none remaining */ 00367 while (len >= 16) { 00368 len -= 16; 00369 DO16(buf); 00370 buf += 16; 00371 } 00372 while (len--) { 00373 adler += (rpmuint32_t) *buf++; 00374 sum2 += adler; 00375 } 00376 MOD(adler); 00377 MOD(sum2); 00378 } 00379 00380 /* return recombined sums */ 00381 return adler | (sum2 << 16); 00382 } 00383 00384 rpmuint32_t __adler32_combine(rpmuint32_t adler1, rpmuint32_t adler2, size_t len2) 00385 /*@*/ 00386 { 00387 rpmuint32_t sum1; 00388 rpmuint32_t sum2; 00389 unsigned rem; 00390 00391 /* the derivation of this formula is left as an exercise for the reader */ 00392 rem = (unsigned)(len2 % BASE); 00393 sum1 = adler1 & 0xffff; 00394 sum2 = rem * sum1; 00395 MOD(sum2); 00396 sum1 += (adler2 & 0xffff) + BASE - 1; 00397 sum2 += ((adler1 >> 16) & 0xffff) + ((adler2 >> 16) & 0xffff) + BASE - rem; 00398 if (sum1 > BASE) sum1 -= BASE; 00399 if (sum1 > BASE) sum1 -= BASE; 00400 if (sum2 > (BASE << 1)) sum2 -= (BASE << 1); 00401 if (sum2 > BASE) sum2 -= BASE; 00402 return sum1 | (sum2 << 16); 00403 } 00404 00405 int sum32Reset(register sum32Param * mp) 00406 { 00407 if (mp->update) 00408 mp->crc = (*mp->update) (0, NULL, 0); 00409 return 0; 00410 } 00411 00412 int sum32Update(sum32Param * mp, const rpmuint8_t * data, size_t size) 00413 { 00414 if (mp->update) 00415 mp->crc = (*mp->update) (mp->crc, data, size); 00416 return 0; 00417 } 00418 00419 int sum32Digest(sum32Param * mp, rpmuint8_t * data) 00420 { 00421 rpmuint32_t c = mp->crc; 00422 00423 data[ 0] = (rpmuint8_t)(c >> 24); 00424 data[ 1] = (rpmuint8_t)(c >> 16); 00425 data[ 2] = (rpmuint8_t)(c >> 8); 00426 data[ 3] = (rpmuint8_t)(c ); 00427 00428 (void) sum32Reset(mp); 00429 00430 return 0; 00431 } 00432 00433 int sum64Reset(register sum64Param * mp) 00434 { 00435 if (mp->update) 00436 mp->crc = (*mp->update) (0, NULL, 0); 00437 return 0; 00438 } 00439 00440 int sum64Update(sum64Param * mp, const rpmuint8_t * data, size_t size) 00441 { 00442 if (mp->update) 00443 mp->crc = (*mp->update) (mp->crc, data, size); 00444 return 0; 00445 } 00446 00447 int sum64Digest(sum64Param * mp, rpmuint8_t * data) 00448 { 00449 rpmuint64_t c = mp->crc; 00450 00451 data[ 0] = (rpmuint8_t)(c >> 56); 00452 data[ 1] = (rpmuint8_t)(c >> 48); 00453 data[ 2] = (rpmuint8_t)(c >> 40); 00454 data[ 3] = (rpmuint8_t)(c >> 32); 00455 data[ 4] = (rpmuint8_t)(c >> 24); 00456 data[ 5] = (rpmuint8_t)(c >> 16); 00457 data[ 6] = (rpmuint8_t)(c >> 8); 00458 data[ 7] = (rpmuint8_t)(c ); 00459 00460 (void) sum64Reset(mp); 00461 00462 return 0; 00463 }