deps/libchdr/deps/zlib-1.3.1/adler32.c

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