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