| 1 | /* adler32.c -- compute the Adler-32 checksum of a data stream
|
|---|
| 2 | * Copyright (C) 1995-2004 Mark Adler
|
|---|
| 3 | * For conditions of distribution and use, see copyright notice in zlib.h
|
|---|
| 4 | */
|
|---|
| 5 |
|
|---|
| 6 | /* @(#) $Id$ */
|
|---|
| 7 |
|
|---|
| 8 | #define ZLIB_INTERNAL
|
|---|
| 9 | #include "zlib.h"
|
|---|
| 10 |
|
|---|
| 11 | #define BASE 65521UL /* largest prime smaller than 65536 */
|
|---|
| 12 | #define NMAX 5552
|
|---|
| 13 | /* NMAX is the largest n such that 255n(n+1)/2 + (n+1)(BASE-1) <= 2^32-1 */
|
|---|
| 14 |
|
|---|
| 15 | #define DO1(buf,i) {adler += (buf)[i]; sum2 += adler;}
|
|---|
| 16 | #define DO2(buf,i) DO1(buf,i); DO1(buf,i+1);
|
|---|
| 17 | #define DO4(buf,i) DO2(buf,i); DO2(buf,i+2);
|
|---|
| 18 | #define DO8(buf,i) DO4(buf,i); DO4(buf,i+4);
|
|---|
| 19 | #define DO16(buf) DO8(buf,0); DO8(buf,8);
|
|---|
| 20 |
|
|---|
| 21 | /* use NO_DIVIDE if your processor does not do division in hardware */
|
|---|
| 22 | #ifdef NO_DIVIDE
|
|---|
| 23 | # define MOD(a) \
|
|---|
| 24 | do { \
|
|---|
| 25 | if (a >= (BASE << 16)) a -= (BASE << 16); \
|
|---|
| 26 | if (a >= (BASE << 15)) a -= (BASE << 15); \
|
|---|
| 27 | if (a >= (BASE << 14)) a -= (BASE << 14); \
|
|---|
| 28 | if (a >= (BASE << 13)) a -= (BASE << 13); \
|
|---|
| 29 | if (a >= (BASE << 12)) a -= (BASE << 12); \
|
|---|
| 30 | if (a >= (BASE << 11)) a -= (BASE << 11); \
|
|---|
| 31 | if (a >= (BASE << 10)) a -= (BASE << 10); \
|
|---|
| 32 | if (a >= (BASE << 9)) a -= (BASE << 9); \
|
|---|
| 33 | if (a >= (BASE << 8)) a -= (BASE << 8); \
|
|---|
| 34 | if (a >= (BASE << 7)) a -= (BASE << 7); \
|
|---|
| 35 | if (a >= (BASE << 6)) a -= (BASE << 6); \
|
|---|
| 36 | if (a >= (BASE << 5)) a -= (BASE << 5); \
|
|---|
| 37 | if (a >= (BASE << 4)) a -= (BASE << 4); \
|
|---|
| 38 | if (a >= (BASE << 3)) a -= (BASE << 3); \
|
|---|
| 39 | if (a >= (BASE << 2)) a -= (BASE << 2); \
|
|---|
| 40 | if (a >= (BASE << 1)) a -= (BASE << 1); \
|
|---|
| 41 | if (a >= BASE) a -= BASE; \
|
|---|
| 42 | } while (0)
|
|---|
| 43 | # define MOD4(a) \
|
|---|
| 44 | do { \
|
|---|
| 45 | if (a >= (BASE << 4)) a -= (BASE << 4); \
|
|---|
| 46 | if (a >= (BASE << 3)) a -= (BASE << 3); \
|
|---|
| 47 | if (a >= (BASE << 2)) a -= (BASE << 2); \
|
|---|
| 48 | if (a >= (BASE << 1)) a -= (BASE << 1); \
|
|---|
| 49 | if (a >= BASE) a -= BASE; \
|
|---|
| 50 | } while (0)
|
|---|
| 51 | #else
|
|---|
| 52 | # define MOD(a) a %= BASE
|
|---|
| 53 | # define MOD4(a) a %= BASE
|
|---|
| 54 | #endif
|
|---|
| 55 |
|
|---|
| 56 | /* ========================================================================= */
|
|---|
| 57 | uLong ZEXPORT adler32(adler, buf, len)
|
|---|
| 58 | uLong adler;
|
|---|
| 59 | const Bytef *buf;
|
|---|
| 60 | uInt len;
|
|---|
| 61 | {
|
|---|
| 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 | MOD4(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_combine(adler1, adler2, len2)
|
|---|
| 129 | uLong adler1;
|
|---|
| 130 | uLong adler2;
|
|---|
| 131 | z_off_t len2;
|
|---|
| 132 | {
|
|---|
| 133 | unsigned long sum1;
|
|---|
| 134 | unsigned long sum2;
|
|---|
| 135 | unsigned rem;
|
|---|
| 136 |
|
|---|
| 137 | /* the derivation of this formula is left as an exercise for the reader */
|
|---|
| 138 | rem = (unsigned)(len2 % BASE);
|
|---|
| 139 | sum1 = adler1 & 0xffff;
|
|---|
| 140 | sum2 = rem * sum1;
|
|---|
| 141 | MOD(sum2);
|
|---|
| 142 | sum1 += (adler2 & 0xffff) + BASE - 1;
|
|---|
| 143 | sum2 += ((adler1 >> 16) & 0xffff) + ((adler2 >> 16) & 0xffff) + BASE - rem;
|
|---|
| 144 | if (sum1 > BASE) sum1 -= BASE;
|
|---|
| 145 | if (sum1 > BASE) sum1 -= BASE;
|
|---|
| 146 | if (sum2 > (BASE << 1)) sum2 -= (BASE << 1);
|
|---|
| 147 | if (sum2 > BASE) sum2 -= BASE;
|
|---|
| 148 | return sum1 | (sum2 << 16);
|
|---|
| 149 | }
|
|---|
