1168404Spjd/* adler32.c -- compute the Adler-32 checksum of a data stream 2168404Spjd * Copyright (C) 1995-2004 Mark Adler 3168404Spjd * For conditions of distribution and use, see copyright notice in zlib.h 4168404Spjd */ 5168404Spjd 6168404Spjd#pragma ident "%Z%%M% %I% %E% SMI" 7168404Spjd 8168404Spjd#define ZLIB_INTERNAL 9168404Spjd#include "zlib.h" 10168404Spjd 11168404Spjd#define BASE 65521UL /* largest prime smaller than 65536 */ 12168404Spjd#define NMAX 5552 13168404Spjd/* NMAX is the largest n such that 255n(n+1)/2 + (n+1)(BASE-1) <= 2^32-1 */ 14168404Spjd 15168404Spjd#define DO1(buf,i) {adler += (buf)[i]; sum2 += adler;} 16168404Spjd#define DO2(buf,i) DO1(buf,i); DO1(buf,i+1); 17168404Spjd#define DO4(buf,i) DO2(buf,i); DO2(buf,i+2); 18168404Spjd#define DO8(buf,i) DO4(buf,i); DO4(buf,i+4); 19168404Spjd#define DO16(buf) DO8(buf,0); DO8(buf,8); 20168404Spjd 21168404Spjd/* use NO_DIVIDE if your processor does not do division in hardware */ 22168404Spjd#ifdef NO_DIVIDE 23168404Spjd# define MOD(a) \ 24168404Spjd do { \ 25168404Spjd if (a >= (BASE << 16)) a -= (BASE << 16); \ 26168404Spjd if (a >= (BASE << 15)) a -= (BASE << 15); \ 27168404Spjd if (a >= (BASE << 14)) a -= (BASE << 14); \ 28168404Spjd if (a >= (BASE << 13)) a -= (BASE << 13); \ 29168404Spjd if (a >= (BASE << 12)) a -= (BASE << 12); \ 30168404Spjd if (a >= (BASE << 11)) a -= (BASE << 11); \ 31168404Spjd if (a >= (BASE << 10)) a -= (BASE << 10); \ 32168404Spjd if (a >= (BASE << 9)) a -= (BASE << 9); \ 33168404Spjd if (a >= (BASE << 8)) a -= (BASE << 8); \ 34168404Spjd if (a >= (BASE << 7)) a -= (BASE << 7); \ 35168404Spjd if (a >= (BASE << 6)) a -= (BASE << 6); \ 36168404Spjd if (a >= (BASE << 5)) a -= (BASE << 5); \ 37168404Spjd if (a >= (BASE << 4)) a -= (BASE << 4); \ 38168404Spjd if (a >= (BASE << 3)) a -= (BASE << 3); \ 39168404Spjd if (a >= (BASE << 2)) a -= (BASE << 2); \ 40168404Spjd if (a >= (BASE << 1)) a -= (BASE << 1); \ 41168404Spjd if (a >= BASE) a -= BASE; \ 42168404Spjd } while (0) 43168404Spjd# define MOD4(a) \ 44168404Spjd do { \ 45168404Spjd if (a >= (BASE << 4)) a -= (BASE << 4); \ 46168404Spjd if (a >= (BASE << 3)) a -= (BASE << 3); \ 47168404Spjd if (a >= (BASE << 2)) a -= (BASE << 2); \ 48168404Spjd if (a >= (BASE << 1)) a -= (BASE << 1); \ 49168404Spjd if (a >= BASE) a -= BASE; \ 50168404Spjd } while (0) 51168404Spjd#else 52168404Spjd# define MOD(a) a %= BASE 53168404Spjd# define MOD4(a) a %= BASE 54168404Spjd#endif 55168404Spjd 56168404Spjd/* ========================================================================= */ 57168404SpjduLong ZEXPORT adler32(adler, buf, len) 58168404Spjd uLong adler; 59168404Spjd const Bytef *buf; 60168404Spjd uInt len; 61168404Spjd{ 62168404Spjd unsigned long sum2; 63168404Spjd unsigned n; 64168404Spjd 65168404Spjd /* split Adler-32 into component sums */ 66168404Spjd sum2 = (adler >> 16) & 0xffff; 67168404Spjd adler &= 0xffff; 68168404Spjd 69168404Spjd /* in case user likes doing a byte at a time, keep it fast */ 70168404Spjd if (len == 1) { 71168404Spjd adler += buf[0]; 72168404Spjd if (adler >= BASE) 73168404Spjd adler -= BASE; 74168404Spjd sum2 += adler; 75168404Spjd if (sum2 >= BASE) 76168404Spjd sum2 -= BASE; 77168404Spjd return adler | (sum2 << 16); 78168404Spjd } 79168404Spjd 80168404Spjd /* initial Adler-32 value (deferred check for len == 1 speed) */ 81168404Spjd if (buf == Z_NULL) 82168404Spjd return 1L; 83168404Spjd 84168404Spjd /* in case short lengths are provided, keep it somewhat fast */ 85168404Spjd if (len < 16) { 86168404Spjd while (len--) { 87168404Spjd adler += *buf++; 88168404Spjd sum2 += adler; 89168404Spjd } 90168404Spjd if (adler >= BASE) 91168404Spjd adler -= BASE; 92168404Spjd MOD4(sum2); /* only added so many BASE's */ 93168404Spjd return adler | (sum2 << 16); 94168404Spjd } 95168404Spjd 96168404Spjd /* do length NMAX blocks -- requires just one modulo operation */ 97168404Spjd while (len >= NMAX) { 98168404Spjd len -= NMAX; 99168404Spjd n = NMAX / 16; /* NMAX is divisible by 16 */ 100168404Spjd do { 101168404Spjd DO16(buf); /* 16 sums unrolled */ 102168404Spjd buf += 16; 103168404Spjd } while (--n); 104168404Spjd MOD(adler); 105168404Spjd MOD(sum2); 106168404Spjd } 107168404Spjd 108168404Spjd /* do remaining bytes (less than NMAX, still just one modulo) */ 109168404Spjd if (len) { /* avoid modulos if none remaining */ 110168404Spjd while (len >= 16) { 111168404Spjd len -= 16; 112168404Spjd DO16(buf); 113168404Spjd buf += 16; 114168404Spjd } 115168404Spjd while (len--) { 116168404Spjd adler += *buf++; 117168404Spjd sum2 += adler; 118168404Spjd } 119168404Spjd MOD(adler); 120168404Spjd MOD(sum2); 121168404Spjd } 122168404Spjd 123168404Spjd /* return recombined sums */ 124168404Spjd return adler | (sum2 << 16); 125168404Spjd} 126168404Spjd 127168404Spjd/* ========================================================================= */ 128168404SpjduLong ZEXPORT adler32_combine(adler1, adler2, len2) 129168404Spjd uLong adler1; 130168404Spjd uLong adler2; 131168404Spjd z_off_t len2; 132168404Spjd{ 133168404Spjd unsigned long sum1; 134168404Spjd unsigned long sum2; 135168404Spjd unsigned rem; 136168404Spjd 137168404Spjd /* the derivation of this formula is left as an exercise for the reader */ 138168404Spjd rem = (unsigned)(len2 % BASE); 139168404Spjd sum1 = adler1 & 0xffff; 140168404Spjd sum2 = rem * sum1; 141168404Spjd MOD(sum2); 142168404Spjd sum1 += (adler2 & 0xffff) + BASE - 1; 143168404Spjd sum2 += ((adler1 >> 16) & 0xffff) + ((adler2 >> 16) & 0xffff) + BASE - rem; 144168404Spjd if (sum1 > BASE) sum1 -= BASE; 145168404Spjd if (sum1 > BASE) sum1 -= BASE; 146168404Spjd if (sum2 > (BASE << 1)) sum2 -= (BASE << 1); 147168404Spjd if (sum2 > BASE) sum2 -= BASE; 148168404Spjd return sum1 | (sum2 << 16); 149168404Spjd} 150