saml/zlib/adler32.c

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