Annotation of embedaddon/sudo/zlib/adler32.c, revision 1.1.1.1

1.1       misho       1: /* adler32.c -- compute the Adler-32 checksum of a data stream
                      2:  * Copyright (C) 1995-2007 Mark Adler
                      3:  * For conditions of distribution and use, see copyright notice in zlib.h
                      4:  */
                      5: 
                      6: /* @(#) $Id$ */
                      7: 
                      8: #include "zutil.h"
                      9: 
                     10: #define local static
                     11: 
                     12: local uLong adler32_combine_(uLong adler1, uLong adler2, z_off64_t len2);
                     13: 
                     14: #define BASE 65521UL    /* largest prime smaller than 65536 */
                     15: #define NMAX 5552
                     16: /* NMAX is the largest n such that 255n(n+1)/2 + (n+1)(BASE-1) <= 2^32-1 */
                     17: 
                     18: #define DO1(buf,i)  {adler += (buf)[i]; sum2 += adler;}
                     19: #define DO2(buf,i)  DO1(buf,i); DO1(buf,i+1);
                     20: #define DO4(buf,i)  DO2(buf,i); DO2(buf,i+2);
                     21: #define DO8(buf,i)  DO4(buf,i); DO4(buf,i+4);
                     22: #define DO16(buf)   DO8(buf,0); DO8(buf,8);
                     23: 
                     24: /* use NO_DIVIDE if your processor does not do division in hardware */
                     25: #ifdef NO_DIVIDE
                     26: #  define MOD(a) \
                     27:     do { \
                     28:         if (a >= (BASE << 16)) a -= (BASE << 16); \
                     29:         if (a >= (BASE << 15)) a -= (BASE << 15); \
                     30:         if (a >= (BASE << 14)) a -= (BASE << 14); \
                     31:         if (a >= (BASE << 13)) a -= (BASE << 13); \
                     32:         if (a >= (BASE << 12)) a -= (BASE << 12); \
                     33:         if (a >= (BASE << 11)) a -= (BASE << 11); \
                     34:         if (a >= (BASE << 10)) a -= (BASE << 10); \
                     35:         if (a >= (BASE << 9)) a -= (BASE << 9); \
                     36:         if (a >= (BASE << 8)) a -= (BASE << 8); \
                     37:         if (a >= (BASE << 7)) a -= (BASE << 7); \
                     38:         if (a >= (BASE << 6)) a -= (BASE << 6); \
                     39:         if (a >= (BASE << 5)) a -= (BASE << 5); \
                     40:         if (a >= (BASE << 4)) a -= (BASE << 4); \
                     41:         if (a >= (BASE << 3)) a -= (BASE << 3); \
                     42:         if (a >= (BASE << 2)) a -= (BASE << 2); \
                     43:         if (a >= (BASE << 1)) a -= (BASE << 1); \
                     44:         if (a >= BASE) a -= BASE; \
                     45:     } while (0)
                     46: #  define MOD4(a) \
                     47:     do { \
                     48:         if (a >= (BASE << 4)) a -= (BASE << 4); \
                     49:         if (a >= (BASE << 3)) a -= (BASE << 3); \
                     50:         if (a >= (BASE << 2)) a -= (BASE << 2); \
                     51:         if (a >= (BASE << 1)) a -= (BASE << 1); \
                     52:         if (a >= BASE) a -= BASE; \
                     53:     } while (0)
                     54: #else
                     55: #  define MOD(a) a %= BASE
                     56: #  define MOD4(a) a %= BASE
                     57: #endif
                     58: 
                     59: /* ========================================================================= */
                     60: uLong ZEXPORT adler32(adler, buf, len)
                     61:     uLong adler;
                     62:     const Bytef *buf;
                     63:     uInt len;
                     64: {
                     65:     unsigned long sum2;
                     66:     unsigned n;
                     67: 
                     68:     /* split Adler-32 into component sums */
                     69:     sum2 = (adler >> 16) & 0xffff;
                     70:     adler &= 0xffff;
                     71: 
                     72:     /* in case user likes doing a byte at a time, keep it fast */
                     73:     if (len == 1) {
                     74:         adler += buf[0];
                     75:         if (adler >= BASE)
                     76:             adler -= BASE;
                     77:         sum2 += adler;
                     78:         if (sum2 >= BASE)
                     79:             sum2 -= BASE;
                     80:         return adler | (sum2 << 16);
                     81:     }
                     82: 
                     83:     /* initial Adler-32 value (deferred check for len == 1 speed) */
                     84:     if (buf == Z_NULL)
                     85:         return 1L;
                     86: 
                     87:     /* in case short lengths are provided, keep it somewhat fast */
                     88:     if (len < 16) {
                     89:         while (len--) {
                     90:             adler += *buf++;
                     91:             sum2 += adler;
                     92:         }
                     93:         if (adler >= BASE)
                     94:             adler -= BASE;
                     95:         MOD4(sum2);             /* only added so many BASE's */
                     96:         return adler | (sum2 << 16);
                     97:     }
                     98: 
                     99:     /* do length NMAX blocks -- requires just one modulo operation */
                    100:     while (len >= NMAX) {
                    101:         len -= NMAX;
                    102:         n = NMAX / 16;          /* NMAX is divisible by 16 */
                    103:         do {
                    104:             DO16(buf);          /* 16 sums unrolled */
                    105:             buf += 16;
                    106:         } while (--n);
                    107:         MOD(adler);
                    108:         MOD(sum2);
                    109:     }
                    110: 
                    111:     /* do remaining bytes (less than NMAX, still just one modulo) */
                    112:     if (len) {                  /* avoid modulos if none remaining */
                    113:         while (len >= 16) {
                    114:             len -= 16;
                    115:             DO16(buf);
                    116:             buf += 16;
                    117:         }
                    118:         while (len--) {
                    119:             adler += *buf++;
                    120:             sum2 += adler;
                    121:         }
                    122:         MOD(adler);
                    123:         MOD(sum2);
                    124:     }
                    125: 
                    126:     /* return recombined sums */
                    127:     return adler | (sum2 << 16);
                    128: }
                    129: 
                    130: /* ========================================================================= */
                    131: local uLong adler32_combine_(adler1, adler2, len2)
                    132:     uLong adler1;
                    133:     uLong adler2;
                    134:     z_off64_t len2;
                    135: {
                    136:     unsigned long sum1;
                    137:     unsigned long sum2;
                    138:     unsigned rem;
                    139: 
                    140:     /* the derivation of this formula is left as an exercise for the reader */
                    141:     rem = (unsigned)(len2 % BASE);
                    142:     sum1 = adler1 & 0xffff;
                    143:     sum2 = rem * sum1;
                    144:     MOD(sum2);
                    145:     sum1 += (adler2 & 0xffff) + BASE - 1;
                    146:     sum2 += ((adler1 >> 16) & 0xffff) + ((adler2 >> 16) & 0xffff) + BASE - rem;
                    147:     if (sum1 >= BASE) sum1 -= BASE;
                    148:     if (sum1 >= BASE) sum1 -= BASE;
                    149:     if (sum2 >= (BASE << 1)) sum2 -= (BASE << 1);
                    150:     if (sum2 >= BASE) sum2 -= BASE;
                    151:     return sum1 | (sum2 << 16);
                    152: }
                    153: 
                    154: /* ========================================================================= */
                    155: uLong ZEXPORT adler32_combine(adler1, adler2, len2)
                    156:     uLong adler1;
                    157:     uLong adler2;
                    158:     z_off_t len2;
                    159: {
                    160:     return adler32_combine_(adler1, adler2, len2);
                    161: }
                    162: 
                    163: uLong ZEXPORT adler32_combine64(adler1, adler2, len2)
                    164:     uLong adler1;
                    165:     uLong adler2;
                    166:     z_off64_t len2;
                    167: {
                    168:     return adler32_combine_(adler1, adler2, len2);
                    169: }

FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>