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;
00013 static rpmuint32_t xorout = 0xffffffff;
00014 static rpmuint32_t table[256];
00015
00016 crc ^= xorout;
00017
00018 if (data == NULL) {
00019
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
00047
00048
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( rpmuint32_t *square, rpmuint32_t *mat)
00071
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);
00085 rpmuint32_t * odd = alloca(nb);
00086
00087
00088 if (len2 == 0)
00089 return crc1;
00090
00091
00092 odd[0] = 0xedb88320UL;
00093 row = 1;
00094 for (n = 1; n < gf2_dim32; n++) {
00095 odd[n] = row;
00096 row <<= 1;
00097 }
00098
00099
00100 gf2_matrix_square32(even, odd);
00101
00102
00103 gf2_matrix_square32(odd, even);
00104
00105
00106
00107 do {
00108
00109 gf2_matrix_square32(even, odd);
00110 if (len2 & 1)
00111 crc1 = gf2_matrix_times32(even, crc1);
00112 len2 >>= 1;
00113
00114
00115 if (len2 == 0)
00116 break;
00117
00118
00119 gf2_matrix_square32(odd, even);
00120 if (len2 & 1)
00121 crc1 = gf2_matrix_times32(odd, crc1);
00122 len2 >>= 1;
00123
00124
00125 } while (len2 != 0);
00126
00127
00128 crc1 ^= crc2;
00129 return crc1;
00130 }
00131
00132
00133
00134
00135
00136
00137 rpmuint64_t __crc64(rpmuint64_t crc, const rpmuint8_t * data, size_t size)
00138 {
00139 static rpmuint64_t polynomial =
00140 0xc96c5795d7870f42ULL;
00141 static rpmuint64_t xorout = 0xffffffffffffffffULL;
00142 static rpmuint64_t table[256];
00143
00144 crc ^= xorout;
00145
00146 if (data == NULL) {
00147
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
00175
00176
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( rpmuint64_t *square, rpmuint64_t *mat)
00199
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);
00213 rpmuint64_t * odd = alloca(nb);
00214
00215
00216 if (len2 == 0)
00217 return crc1;
00218
00219
00220 odd[0] = 0xc96c5795d7870f42ULL;
00221 row = 1;
00222 for (n = 1; n < gf2_dim64; n++) {
00223 odd[n] = row;
00224 row <<= 1;
00225 }
00226
00227
00228 gf2_matrix_square64(even, odd);
00229
00230
00231 gf2_matrix_square64(odd, even);
00232
00233
00234
00235 do {
00236
00237 gf2_matrix_square64(even, odd);
00238 if (len2 & 1)
00239 crc1 = gf2_matrix_times64(even, crc1);
00240 len2 >>= 1;
00241
00242
00243 if (len2 == 0)
00244 break;
00245
00246
00247 gf2_matrix_square64(odd, even);
00248 if (len2 & 1)
00249 crc1 = gf2_matrix_times64(odd, crc1);
00250 len2 >>= 1;
00251
00252
00253 } while (len2 != 0);
00254
00255
00256 crc1 ^= crc2;
00257 return crc1;
00258 }
00259
00260
00261
00262
00263
00264
00265
00266 #define BASE 65521UL
00267 #define NMAX 5552
00268
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
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
00317 sum2 = (adler >> 16) & 0xffff;
00318 adler &= 0xffff;
00319
00320
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
00332 if (buf == NULL)
00333 return 1UL;
00334
00335
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);
00344 return adler | (sum2 << 16);
00345 }
00346
00347
00348 while (len >= NMAX) {
00349 len -= NMAX;
00350 n = NMAX / 16;
00351 do {
00352 DO16(buf);
00353 buf += 16;
00354 } while (--n);
00355 MOD(adler);
00356 MOD(sum2);
00357 }
00358
00359
00360 if (len) {
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
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
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 }