rpm 5.3.12
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     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 }