Back to index

lightning-sunbird  0.9+nobinonly
adler32.c
Go to the documentation of this file.
00001 /* adler32.c -- compute the Adler-32 checksum of a data stream
00002  * Copyright (C) 1995-2004 Mark Adler
00003  * For conditions of distribution and use, see copyright notice in zlib.h
00004  */
00005 
00006 /* @(#) $Id: adler32.c,v 1.5 2005/07/20 20:32:42 wtchang%redhat.com Exp $ */
00007 
00008 #define ZLIB_INTERNAL
00009 #include "zlib.h"
00010 
00011 #define BASE 65521UL    /* largest prime smaller than 65536 */
00012 #define NMAX 5552
00013 /* NMAX is the largest n such that 255n(n+1)/2 + (n+1)(BASE-1) <= 2^32-1 */
00014 
00015 #define DO1(buf,i)  {adler += (buf)[i]; sum2 += adler;}
00016 #define DO2(buf,i)  DO1(buf,i); DO1(buf,i+1);
00017 #define DO4(buf,i)  DO2(buf,i); DO2(buf,i+2);
00018 #define DO8(buf,i)  DO4(buf,i); DO4(buf,i+4);
00019 #define DO16(buf)   DO8(buf,0); DO8(buf,8);
00020 
00021 /* use NO_DIVIDE if your processor does not do division in hardware */
00022 #ifdef NO_DIVIDE
00023 #  define MOD(a) \
00024     do { \
00025         if (a >= (BASE << 16)) a -= (BASE << 16); \
00026         if (a >= (BASE << 15)) a -= (BASE << 15); \
00027         if (a >= (BASE << 14)) a -= (BASE << 14); \
00028         if (a >= (BASE << 13)) a -= (BASE << 13); \
00029         if (a >= (BASE << 12)) a -= (BASE << 12); \
00030         if (a >= (BASE << 11)) a -= (BASE << 11); \
00031         if (a >= (BASE << 10)) a -= (BASE << 10); \
00032         if (a >= (BASE << 9)) a -= (BASE << 9); \
00033         if (a >= (BASE << 8)) a -= (BASE << 8); \
00034         if (a >= (BASE << 7)) a -= (BASE << 7); \
00035         if (a >= (BASE << 6)) a -= (BASE << 6); \
00036         if (a >= (BASE << 5)) a -= (BASE << 5); \
00037         if (a >= (BASE << 4)) a -= (BASE << 4); \
00038         if (a >= (BASE << 3)) a -= (BASE << 3); \
00039         if (a >= (BASE << 2)) a -= (BASE << 2); \
00040         if (a >= (BASE << 1)) a -= (BASE << 1); \
00041         if (a >= BASE) a -= BASE; \
00042     } while (0)
00043 #  define MOD4(a) \
00044     do { \
00045         if (a >= (BASE << 4)) a -= (BASE << 4); \
00046         if (a >= (BASE << 3)) a -= (BASE << 3); \
00047         if (a >= (BASE << 2)) a -= (BASE << 2); \
00048         if (a >= (BASE << 1)) a -= (BASE << 1); \
00049         if (a >= BASE) a -= BASE; \
00050     } while (0)
00051 #else
00052 #  define MOD(a) a %= BASE
00053 #  define MOD4(a) a %= BASE
00054 #endif
00055 
00056 /* ========================================================================= */
00057 uLong ZEXPORT adler32(adler, buf, len)
00058     uLong adler;
00059     const Bytef *buf;
00060     uInt len;
00061 {
00062     unsigned long sum2;
00063     unsigned n;
00064 
00065     /* split Adler-32 into component sums */
00066     sum2 = (adler >> 16) & 0xffff;
00067     adler &= 0xffff;
00068 
00069     /* in case user likes doing a byte at a time, keep it fast */
00070     if (len == 1) {
00071         adler += buf[0];
00072         if (adler >= BASE)
00073             adler -= BASE;
00074         sum2 += adler;
00075         if (sum2 >= BASE)
00076             sum2 -= BASE;
00077         return adler | (sum2 << 16);
00078     }
00079 
00080     /* initial Adler-32 value (deferred check for len == 1 speed) */
00081     if (buf == Z_NULL)
00082         return 1L;
00083 
00084     /* in case short lengths are provided, keep it somewhat fast */
00085     if (len < 16) {
00086         while (len--) {
00087             adler += *buf++;
00088             sum2 += adler;
00089         }
00090         if (adler >= BASE)
00091             adler -= BASE;
00092         MOD4(sum2);             /* only added so many BASE's */
00093         return adler | (sum2 << 16);
00094     }
00095 
00096     /* do length NMAX blocks -- requires just one modulo operation */
00097     while (len >= NMAX) {
00098         len -= NMAX;
00099         n = NMAX / 16;          /* NMAX is divisible by 16 */
00100         do {
00101             DO16(buf);          /* 16 sums unrolled */
00102             buf += 16;
00103         } while (--n);
00104         MOD(adler);
00105         MOD(sum2);
00106     }
00107 
00108     /* do remaining bytes (less than NMAX, still just one modulo) */
00109     if (len) {                  /* avoid modulos if none remaining */
00110         while (len >= 16) {
00111             len -= 16;
00112             DO16(buf);
00113             buf += 16;
00114         }
00115         while (len--) {
00116             adler += *buf++;
00117             sum2 += adler;
00118         }
00119         MOD(adler);
00120         MOD(sum2);
00121     }
00122 
00123     /* return recombined sums */
00124     return adler | (sum2 << 16);
00125 }
00126 
00127 /* ========================================================================= */
00128 uLong ZEXPORT adler32_combine(adler1, adler2, len2)
00129     uLong adler1;
00130     uLong adler2;
00131     z_off_t len2;
00132 {
00133     unsigned long sum1;
00134     unsigned long sum2;
00135     unsigned rem;
00136 
00137     /* the derivation of this formula is left as an exercise for the reader */
00138     rem = (unsigned)(len2 % BASE);
00139     sum1 = adler1 & 0xffff;
00140     sum2 = rem * sum1;
00141     MOD(sum2);
00142     sum1 += (adler2 & 0xffff) + BASE - 1;
00143     sum2 += ((adler1 >> 16) & 0xffff) + ((adler2 >> 16) & 0xffff) + BASE - rem;
00144     if (sum1 > BASE) sum1 -= BASE;
00145     if (sum1 > BASE) sum1 -= BASE;
00146     if (sum2 > (BASE << 1)) sum2 -= (BASE << 1);
00147     if (sum2 > BASE) sum2 -= BASE;
00148     return sum1 | (sum2 << 16);
00149 }