LXR uboot/lib/zlib/adler32.c

   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/* ========================================================================= */
  57uLong ZEXPORT adler32(uLong adler, const Bytef *buf, uInt len)
  58{
  59    unsigned long sum2;
  60    unsigned n;
  61
  62    /* split Adler-32 into component sums */
  63    sum2 = (adler >> 16) & 0xffff;
  64    adler &= 0xffff;
  65
  66    /* in case user likes doing a byte at a time, keep it fast */
  67    if (len == 1) {
  68        adler += buf[0];
  69        if (adler >= BASE)
  70            adler -= BASE;
  71        sum2 += adler;
  72        if (sum2 >= BASE)
  73            sum2 -= BASE;
  74        return adler | (sum2 << 16);
  75    }
  76
  77    /* initial Adler-32 value (deferred check for len == 1 speed) */
  78    if (buf == Z_NULL)
  79        return 1L;
  80
  81    /* in case short lengths are provided, keep it somewhat fast */
  82    if (len < 16) {
  83        while (len--) {
  84            adler += *buf++;
  85            sum2 += adler;
  86        }
  87        if (adler >= BASE)
  88            adler -= BASE;
  89        MOD4(sum2);             /* only added so many BASE's */
  90        return adler | (sum2 << 16);
  91    }
  92
  93    /* do length NMAX blocks -- requires just one modulo operation */
  94    while (len >= NMAX) {
  95        len -= NMAX;
  96        n = NMAX / 16;          /* NMAX is divisible by 16 */
  97        do {
  98            DO16(buf);          /* 16 sums unrolled */
  99            buf += 16;
 100        } while (--n);
 101        MOD(adler);
 102        MOD(sum2);
 103    }
 104
 105    /* do remaining bytes (less than NMAX, still just one modulo) */
 106    if (len) {                  /* avoid modulos if none remaining */
 107        while (len >= 16) {
 108            len -= 16;
 109            DO16(buf);
 110            buf += 16;
 111        }
 112        while (len--) {
 113            adler += *buf++;
 114            sum2 += adler;
 115        }
 116        MOD(adler);
 117        MOD(sum2);
 118    }
 119
 120    /* return recombined sums */
 121    return adler | (sum2 << 16);
 122}
 123