1c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott/* adler32.c -- compute the Adler-32 checksum of a data stream 2c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott * Copyright (C) 1995-2004 Mark Adler 3c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott * For conditions of distribution and use, see copyright notice in zlib.h 4c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott */ 5c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 6c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott/* @(#) $Id$ */ 7c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 8c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott#define ZLIB_INTERNAL 9c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott#include "zlib.h" 10c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 11c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott#define BASE 65521UL /* largest prime smaller than 65536 */ 12c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott#define NMAX 5552 13c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott/* NMAX is the largest n such that 255n(n+1)/2 + (n+1)(BASE-1) <= 2^32-1 */ 14c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 15c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott#define DO1(buf,i) {adler += (buf)[i]; sum2 += adler;} 16c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott#define DO2(buf,i) DO1(buf,i); DO1(buf,i+1); 17c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott#define DO4(buf,i) DO2(buf,i); DO2(buf,i+2); 18c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott#define DO8(buf,i) DO4(buf,i); DO4(buf,i+4); 19c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott#define DO16(buf) DO8(buf,0); DO8(buf,8); 20c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 21c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott/* use NO_DIVIDE if your processor does not do division in hardware */ 22c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott#ifdef NO_DIVIDE 23c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott# define MOD(a) \ 24c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott do { \ 25c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (a >= (BASE << 16)) a -= (BASE << 16); \ 26c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (a >= (BASE << 15)) a -= (BASE << 15); \ 27c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (a >= (BASE << 14)) a -= (BASE << 14); \ 28c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (a >= (BASE << 13)) a -= (BASE << 13); \ 29c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (a >= (BASE << 12)) a -= (BASE << 12); \ 30c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (a >= (BASE << 11)) a -= (BASE << 11); \ 31c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (a >= (BASE << 10)) a -= (BASE << 10); \ 32c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (a >= (BASE << 9)) a -= (BASE << 9); \ 33c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (a >= (BASE << 8)) a -= (BASE << 8); \ 34c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (a >= (BASE << 7)) a -= (BASE << 7); \ 35c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (a >= (BASE << 6)) a -= (BASE << 6); \ 36c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (a >= (BASE << 5)) a -= (BASE << 5); \ 37c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (a >= (BASE << 4)) a -= (BASE << 4); \ 38c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (a >= (BASE << 3)) a -= (BASE << 3); \ 39c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (a >= (BASE << 2)) a -= (BASE << 2); \ 40c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (a >= (BASE << 1)) a -= (BASE << 1); \ 41c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (a >= BASE) a -= BASE; \ 42c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } while (0) 43c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott# define MOD4(a) \ 44c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott do { \ 45c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (a >= (BASE << 4)) a -= (BASE << 4); \ 46c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (a >= (BASE << 3)) a -= (BASE << 3); \ 47c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (a >= (BASE << 2)) a -= (BASE << 2); \ 48c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (a >= (BASE << 1)) a -= (BASE << 1); \ 49c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (a >= BASE) a -= BASE; \ 50c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } while (0) 51c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott#else 52c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott# define MOD(a) a %= BASE 53c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott# define MOD4(a) a %= BASE 54c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott#endif 55c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 56c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott/* ========================================================================= */ 57c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 58c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott/* 59c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott The adler32 code below computes, in effect, 60c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 61c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott uLong high = 0; 62c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott uLong low = 1; 63c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott for (j = 0; j < len; j++) { 64c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott low = (low + buf[j]) % BASE; 65c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott high = (high + low) % BASE; 66c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } 67c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott checksum = (high << 16) | low; 68c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 69c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott Both 16-bit halves of the checksum are between 0 and BASE-1 (inclusive). 70c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott Hence, the minimum possible checksum value is 0, and the maximum is 71c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott ((BASE-1) << 16) | (BASE-1). Applications may have reserved values 72c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott outside this range to carry special meanings. 73c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 74c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott NOTE: If adler32() is changed in ANY way, be absolutely sure that the 75c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott change will NOT cause checksums previously stored to not match the data 76c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott they were originally intended to match, or expand the range in such a 77c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott way that values reserved by applications to carry special meanings now 78c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott become checksums of valid data. Also, be sure to change adler32_range() 79c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott accordingly. 80c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 81c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott This explanation and adler32_range() are not part of original software 82c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott distribution. They are added at Google (2006) in accordance with the 83c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott copyright notice in zlib.h, which permits alteration and redistribution 84c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott of the original software provided, among other things, that altered 85c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott source versions must be plainly marked as such and not misrepresented as 86c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott being the original software. 87c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott*/ 88c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 89c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scottvoid ZEXPORT adler32_range(min, max) 90c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott uLong *min; 91c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott uLong *max; 92c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott{ 93c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott *min = 0L; 94c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott *max = ((BASE-1) << 16) | (BASE-1); 95c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott} 96c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 97c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick ScottuLong ZEXPORT adler32(adler, buf, len) 98c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott uLong adler; 99c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott const Bytef *buf; 100c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott uInt len; 101c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott{ 102c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott unsigned long sum2; 103c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott unsigned n; 104c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 105c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott /* split Adler-32 into component sums */ 106c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott sum2 = (adler >> 16) & 0xffff; 107c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott adler &= 0xffff; 108c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 109c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott /* in case user likes doing a byte at a time, keep it fast */ 110c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (len == 1) { 111c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott adler += buf[0]; 112c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (adler >= BASE) 113c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott adler -= BASE; 114c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott sum2 += adler; 115c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (sum2 >= BASE) 116c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott sum2 -= BASE; 117c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return adler | (sum2 << 16); 118c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } 119c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 120c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott /* initial Adler-32 value (deferred check for len == 1 speed) */ 121c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (buf == Z_NULL) 122c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return 1L; 123c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 124c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott /* in case short lengths are provided, keep it somewhat fast */ 125c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (len < 16) { 126c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott while (len--) { 127c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott adler += *buf++; 128c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott sum2 += adler; 129c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } 130c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (adler >= BASE) 131c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott adler -= BASE; 132c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott MOD4(sum2); /* only added so many BASE's */ 133c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return adler | (sum2 << 16); 134c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } 135c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 136c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott /* do length NMAX blocks -- requires just one modulo operation */ 137c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott while (len >= NMAX) { 138c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott len -= NMAX; 139c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott n = NMAX / 16; /* NMAX is divisible by 16 */ 140c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott do { 141c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott DO16(buf); /* 16 sums unrolled */ 142c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott buf += 16; 143c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } while (--n); 144c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott MOD(adler); 145c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott MOD(sum2); 146c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } 147c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 148c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott /* do remaining bytes (less than NMAX, still just one modulo) */ 149c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (len) { /* avoid modulos if none remaining */ 150c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott while (len >= 16) { 151c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott len -= 16; 152c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott DO16(buf); 153c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott buf += 16; 154c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } 155c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott while (len--) { 156c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott adler += *buf++; 157c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott sum2 += adler; 158c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } 159c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott MOD(adler); 160c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott MOD(sum2); 161c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott } 162c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 163c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott /* return recombined sums */ 164c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return adler | (sum2 << 16); 165c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott} 166c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 167c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott/* ========================================================================= */ 168c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick ScottuLong ZEXPORT adler32_combine(adler1, adler2, len2) 169c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott uLong adler1; 170c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott uLong adler2; 171c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott z_off_t len2; 172c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott{ 173c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott unsigned long sum1; 174c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott unsigned long sum2; 175c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott unsigned rem; 176c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott 177c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott /* the derivation of this formula is left as an exercise for the reader */ 178c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott rem = (unsigned)(len2 % BASE); 179c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott sum1 = adler1 & 0xffff; 180c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott sum2 = rem * sum1; 181c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott MOD(sum2); 182c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott sum1 += (adler2 & 0xffff) + BASE - 1; 183c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott sum2 += ((adler1 >> 16) & 0xffff) + ((adler2 >> 16) & 0xffff) + BASE - rem; 184c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (sum1 >= BASE) sum1 -= BASE; 185c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (sum1 >= BASE) sum1 -= BASE; 186c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (sum2 >= (BASE << 1)) sum2 -= (BASE << 1); 187c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott if (sum2 >= BASE) sum2 -= BASE; 188c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott return sum1 | (sum2 << 16); 189c7f5f8508d98d5952d42ed7648c2a8f30a4da156Patrick Scott} 190