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 58 /* 59 The adler32 code below computes, in effect, 60 61 uLong high = 0; 62 uLong low = 1; 63 for (j = 0; j < len; j++) { 64 low = (low + buf[j]) % BASE; 65 high = (high + low) % BASE; 66 } 67 checksum = (high << 16) | low; 68 69 Both 16-bit halves of the checksum are between 0 and BASE-1 (inclusive). 70 Hence, the minimum possible checksum value is 0, and the maximum is 71 ((BASE-1) << 16) | (BASE-1). Applications may have reserved values 72 outside this range to carry special meanings. 73 74 NOTE: If adler32() is changed in ANY way, be absolutely sure that the 75 change will NOT cause checksums previously stored to not match the data 76 they were originally intended to match, or expand the range in such a 77 way that values reserved by applications to carry special meanings now 78 become checksums of valid data. Also, be sure to change adler32_range() 79 accordingly. 80 81 This explanation and adler32_range() are not part of original software 82 distribution. They are added at Google (2006) in accordance with the 83 copyright notice in zlib.h, which permits alteration and redistribution 84 of the original software provided, among other things, that altered 85 source versions must be plainly marked as such and not misrepresented as 86 being the original software. 87 */ 88 89 void ZEXPORT adler32_range(min, max) 90 uLong *min; 91 uLong *max; 92 { 93 *min = 0L; 94 *max = ((BASE-1) << 16) | (BASE-1); 95 } 96 97 uLong ZEXPORT adler32(adler, buf, len) 98 uLong adler; 99 const Bytef *buf; 100 uInt len; 101 { 102 unsigned long sum2; 103 unsigned n; 104 105 /* split Adler-32 into component sums */ 106 sum2 = (adler >> 16) & 0xffff; 107 adler &= 0xffff; 108 109 /* in case user likes doing a byte at a time, keep it fast */ 110 if (len == 1) { 111 adler += buf[0]; 112 if (adler >= BASE) 113 adler -= BASE; 114 sum2 += adler; 115 if (sum2 >= BASE) 116 sum2 -= BASE; 117 return adler | (sum2 << 16); 118 } 119 120 /* initial Adler-32 value (deferred check for len == 1 speed) */ 121 if (buf == Z_NULL) 122 return 1L; 123 124 /* in case short lengths are provided, keep it somewhat fast */ 125 if (len < 16) { 126 while (len--) { 127 adler += *buf++; 128 sum2 += adler; 129 } 130 if (adler >= BASE) 131 adler -= BASE; 132 MOD4(sum2); /* only added so many BASE's */ 133 return adler | (sum2 << 16); 134 } 135 136 /* do length NMAX blocks -- requires just one modulo operation */ 137 while (len >= NMAX) { 138 len -= NMAX; 139 n = NMAX / 16; /* NMAX is divisible by 16 */ 140 do { 141 DO16(buf); /* 16 sums unrolled */ 142 buf += 16; 143 } while (--n); 144 MOD(adler); 145 MOD(sum2); 146 } 147 148 /* do remaining bytes (less than NMAX, still just one modulo) */ 149 if (len) { /* avoid modulos if none remaining */ 150 while (len >= 16) { 151 len -= 16; 152 DO16(buf); 153 buf += 16; 154 } 155 while (len--) { 156 adler += *buf++; 157 sum2 += adler; 158 } 159 MOD(adler); 160 MOD(sum2); 161 } 162 163 /* return recombined sums */ 164 return adler | (sum2 << 16); 165 } 166 167 /* ========================================================================= */ 168 uLong ZEXPORT adler32_combine(adler1, adler2, len2) 169 uLong adler1; 170 uLong adler2; 171 z_off_t len2; 172 { 173 unsigned long sum1; 174 unsigned long sum2; 175 unsigned rem; 176 177 /* the derivation of this formula is left as an exercise for the reader */ 178 rem = (unsigned)(len2 % BASE); 179 sum1 = adler1 & 0xffff; 180 sum2 = rem * sum1; 181 MOD(sum2); 182 sum1 += (adler2 & 0xffff) + BASE - 1; 183 sum2 += ((adler1 >> 16) & 0xffff) + ((adler2 >> 16) & 0xffff) + BASE - rem; 184 if (sum1 >= BASE) sum1 -= BASE; 185 if (sum1 >= BASE) sum1 -= BASE; 186 if (sum2 >= (BASE << 1)) sum2 -= (BASE << 1); 187 if (sum2 >= BASE) sum2 -= BASE; 188 return sum1 | (sum2 << 16); 189 } 190
