adler32.c revision 157046
117651Speter/* adler32.c -- compute the Adler-32 checksum of a data stream 2157046Sdes * Copyright (C) 1995-2004 Mark Adler 3131380Stjr * For conditions of distribution and use, see copyright notice in zlib.h 417651Speter */ 517651Speter 6146081Skientzle/* @(#) $Id$ */ 717651Speter 8131380Stjr#define ZLIB_INTERNAL 917651Speter#include "zlib.h" 1017651Speter 11131380Stjr#define BASE 65521UL /* largest prime smaller than 65536 */ 1217651Speter#define NMAX 5552 1317651Speter/* NMAX is the largest n such that 255n(n+1)/2 + (n+1)(BASE-1) <= 2^32-1 */ 1417651Speter 15157046Sdes#define DO1(buf,i) {adler += (buf)[i]; sum2 += adler;} 1617651Speter#define DO2(buf,i) DO1(buf,i); DO1(buf,i+1); 1717651Speter#define DO4(buf,i) DO2(buf,i); DO2(buf,i+2); 1817651Speter#define DO8(buf,i) DO4(buf,i); DO4(buf,i+4); 1917651Speter#define DO16(buf) DO8(buf,0); DO8(buf,8); 2017651Speter 21157046Sdes/* use NO_DIVIDE if your processor does not do division in hardware */ 22131380Stjr#ifdef NO_DIVIDE 23131380Stjr# define MOD(a) \ 24131380Stjr do { \ 25131380Stjr if (a >= (BASE << 16)) a -= (BASE << 16); \ 26131380Stjr if (a >= (BASE << 15)) a -= (BASE << 15); \ 27131380Stjr if (a >= (BASE << 14)) a -= (BASE << 14); \ 28131380Stjr if (a >= (BASE << 13)) a -= (BASE << 13); \ 29131380Stjr if (a >= (BASE << 12)) a -= (BASE << 12); \ 30131380Stjr if (a >= (BASE << 11)) a -= (BASE << 11); \ 31131380Stjr if (a >= (BASE << 10)) a -= (BASE << 10); \ 32131380Stjr if (a >= (BASE << 9)) a -= (BASE << 9); \ 33131380Stjr if (a >= (BASE << 8)) a -= (BASE << 8); \ 34131380Stjr if (a >= (BASE << 7)) a -= (BASE << 7); \ 35131380Stjr if (a >= (BASE << 6)) a -= (BASE << 6); \ 36131380Stjr if (a >= (BASE << 5)) a -= (BASE << 5); \ 37131380Stjr if (a >= (BASE << 4)) a -= (BASE << 4); \ 38131380Stjr if (a >= (BASE << 3)) a -= (BASE << 3); \ 39131380Stjr if (a >= (BASE << 2)) a -= (BASE << 2); \ 40131380Stjr if (a >= (BASE << 1)) a -= (BASE << 1); \ 41131380Stjr if (a >= BASE) a -= BASE; \ 42131380Stjr } while (0) 43157046Sdes# define MOD4(a) \ 44157046Sdes do { \ 45157046Sdes if (a >= (BASE << 4)) a -= (BASE << 4); \ 46157046Sdes if (a >= (BASE << 3)) a -= (BASE << 3); \ 47157046Sdes if (a >= (BASE << 2)) a -= (BASE << 2); \ 48157046Sdes if (a >= (BASE << 1)) a -= (BASE << 1); \ 49157046Sdes if (a >= BASE) a -= BASE; \ 50157046Sdes } while (0) 51131380Stjr#else 52131380Stjr# define MOD(a) a %= BASE 53157046Sdes# define MOD4(a) a %= BASE 54131380Stjr#endif 55131380Stjr 5617651Speter/* ========================================================================= */ 5733908SsteveuLong ZEXPORT adler32(adler, buf, len) 5817651Speter uLong adler; 5917651Speter const Bytef *buf; 6017651Speter uInt len; 6117651Speter{ 62157046Sdes unsigned long sum2; 63157046Sdes unsigned n; 6417651Speter 65157046Sdes /* split Adler-32 into component sums */ 66157046Sdes sum2 = (adler >> 16) & 0xffff; 67157046Sdes adler &= 0xffff; 6817651Speter 69157046Sdes /* in case user likes doing a byte at a time, keep it fast */ 70157046Sdes if (len == 1) { 71157046Sdes adler += buf[0]; 72157046Sdes if (adler >= BASE) 73157046Sdes adler -= BASE; 74157046Sdes sum2 += adler; 75157046Sdes if (sum2 >= BASE) 76157046Sdes sum2 -= BASE; 77157046Sdes return adler | (sum2 << 16); 78157046Sdes } 79157046Sdes 80157046Sdes /* initial Adler-32 value (deferred check for len == 1 speed) */ 81157046Sdes if (buf == Z_NULL) 82157046Sdes return 1L; 83157046Sdes 84157046Sdes /* in case short lengths are provided, keep it somewhat fast */ 85157046Sdes if (len < 16) { 86157046Sdes while (len--) { 87157046Sdes adler += *buf++; 88157046Sdes sum2 += adler; 89157046Sdes } 90157046Sdes if (adler >= BASE) 91157046Sdes adler -= BASE; 92157046Sdes MOD4(sum2); /* only added so many BASE's */ 93157046Sdes return adler | (sum2 << 16); 94157046Sdes } 95157046Sdes 96157046Sdes /* do length NMAX blocks -- requires just one modulo operation */ 97157046Sdes while (len >= NMAX) { 98157046Sdes len -= NMAX; 99157046Sdes n = NMAX / 16; /* NMAX is divisible by 16 */ 100157046Sdes do { 101157046Sdes DO16(buf); /* 16 sums unrolled */ 102157046Sdes buf += 16; 103157046Sdes } while (--n); 104157046Sdes MOD(adler); 105157046Sdes MOD(sum2); 106157046Sdes } 107157046Sdes 108157046Sdes /* do remaining bytes (less than NMAX, still just one modulo) */ 109157046Sdes if (len) { /* avoid modulos if none remaining */ 110157046Sdes while (len >= 16) { 111157046Sdes len -= 16; 11217651Speter DO16(buf); 113131380Stjr buf += 16; 11417651Speter } 115157046Sdes while (len--) { 116157046Sdes adler += *buf++; 117157046Sdes sum2 += adler; 118157046Sdes } 119157046Sdes MOD(adler); 120157046Sdes MOD(sum2); 12117651Speter } 122157046Sdes 123157046Sdes /* return recombined sums */ 124157046Sdes return adler | (sum2 << 16); 12517651Speter} 126157046Sdes 127157046Sdes/* ========================================================================= */ 128157046SdesuLong ZEXPORT adler32_combine(adler1, adler2, len2) 129157046Sdes uLong adler1; 130157046Sdes uLong adler2; 131157046Sdes z_off_t len2; 132157046Sdes{ 133157046Sdes unsigned long sum1; 134157046Sdes unsigned long sum2; 135157046Sdes unsigned rem; 136157046Sdes 137157046Sdes /* the derivation of this formula is left as an exercise for the reader */ 138157046Sdes rem = (unsigned)(len2 % BASE); 139157046Sdes sum1 = adler1 & 0xffff; 140157046Sdes sum2 = rem * sum1; 141157046Sdes MOD(sum2); 142157046Sdes sum1 += (adler2 & 0xffff) + BASE - 1; 143157046Sdes sum2 += ((adler1 >> 16) & 0xffff) + ((adler2 >> 16) & 0xffff) + BASE - rem; 144157046Sdes if (sum1 > BASE) sum1 -= BASE; 145157046Sdes if (sum1 > BASE) sum1 -= BASE; 146157046Sdes if (sum2 > (BASE << 1)) sum2 -= (BASE << 1); 147157046Sdes if (sum2 > BASE) sum2 -= BASE; 148157046Sdes return sum1 | (sum2 << 16); 149157046Sdes} 150