rpm 5.2.1

- Main Page
- Related Pages
- Modules
- Data Structures
- Files

- File List
- Globals

rpmio/crc.c
Go to the documentation of this file.

    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 }