rpm 5.2.1

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 }