Return to adler32.c CVS log

Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / rsync / zlib

v 3.1.0

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