~axehind007/libmemcached/axehind-testing

« back to all changes in this revision

Viewing changes to zlib/adler32.c

  • Committer: Brian Pontz
  • Date: 2011-05-05 04:37:26 UTC
  • Revision ID: bpontz@bpontz-laptop-20110505043726-2gv8ybayvoojydur
Adding required zlib files for memory compression

Show diffs side-by-side

added added

removed removed

Lines of Context:
 
1
/* adler32.c -- compute the Adler-32 checksum of a data stream
 
2
 * Copyright (C) 1995-2007 Mark Adler
 
3
 * For conditions of distribution and use, see copyright notice in zlib.h
 
4
 */
 
5
 
 
6
/* @(#) $Id$ */
 
7
 
 
8
#include "zutil.h"
 
9
 
 
10
#define local static
 
11
 
 
12
local uLong adler32_combine_(uLong adler1, uLong adler2, z_off64_t len2);
 
13
 
 
14
#define BASE 65521UL    /* largest prime smaller than 65536 */
 
15
#define NMAX 5552
 
16
/* NMAX is the largest n such that 255n(n+1)/2 + (n+1)(BASE-1) <= 2^32-1 */
 
17
 
 
18
#define DO1(buf,i)  {adler += (buf)[i]; sum2 += adler;}
 
19
#define DO2(buf,i)  DO1(buf,i); DO1(buf,i+1);
 
20
#define DO4(buf,i)  DO2(buf,i); DO2(buf,i+2);
 
21
#define DO8(buf,i)  DO4(buf,i); DO4(buf,i+4);
 
22
#define DO16(buf)   DO8(buf,0); DO8(buf,8);
 
23
 
 
24
/* use NO_DIVIDE if your processor does not do division in hardware */
 
25
#ifdef NO_DIVIDE
 
26
#  define MOD(a) \
 
27
    do { \
 
28
        if (a >= (BASE << 16)) a -= (BASE << 16); \
 
29
        if (a >= (BASE << 15)) a -= (BASE << 15); \
 
30
        if (a >= (BASE << 14)) a -= (BASE << 14); \
 
31
        if (a >= (BASE << 13)) a -= (BASE << 13); \
 
32
        if (a >= (BASE << 12)) a -= (BASE << 12); \
 
33
        if (a >= (BASE << 11)) a -= (BASE << 11); \
 
34
        if (a >= (BASE << 10)) a -= (BASE << 10); \
 
35
        if (a >= (BASE << 9)) a -= (BASE << 9); \
 
36
        if (a >= (BASE << 8)) a -= (BASE << 8); \
 
37
        if (a >= (BASE << 7)) a -= (BASE << 7); \
 
38
        if (a >= (BASE << 6)) a -= (BASE << 6); \
 
39
        if (a >= (BASE << 5)) a -= (BASE << 5); \
 
40
        if (a >= (BASE << 4)) a -= (BASE << 4); \
 
41
        if (a >= (BASE << 3)) a -= (BASE << 3); \
 
42
        if (a >= (BASE << 2)) a -= (BASE << 2); \
 
43
        if (a >= (BASE << 1)) a -= (BASE << 1); \
 
44
        if (a >= BASE) a -= BASE; \
 
45
    } while (0)
 
46
#  define MOD4(a) \
 
47
    do { \
 
48
        if (a >= (BASE << 4)) a -= (BASE << 4); \
 
49
        if (a >= (BASE << 3)) a -= (BASE << 3); \
 
50
        if (a >= (BASE << 2)) a -= (BASE << 2); \
 
51
        if (a >= (BASE << 1)) a -= (BASE << 1); \
 
52
        if (a >= BASE) a -= BASE; \
 
53
    } while (0)
 
54
#else
 
55
#  define MOD(a) a %= BASE
 
56
#  define MOD4(a) a %= BASE
 
57
#endif
 
58
 
 
59
/* ========================================================================= */
 
60
uLong ZEXPORT adler32(adler, buf, len)
 
61
    uLong adler;
 
62
    const Bytef *buf;
 
63
    uInt len;
 
64
{
 
65
    unsigned long sum2;
 
66
    unsigned n;
 
67
 
 
68
    /* split Adler-32 into component sums */
 
69
    sum2 = (adler >> 16) & 0xffff;
 
70
    adler &= 0xffff;
 
71
 
 
72
    /* in case user likes doing a byte at a time, keep it fast */
 
73
    if (len == 1) {
 
74
        adler += buf[0];
 
75
        if (adler >= BASE)
 
76
            adler -= BASE;
 
77
        sum2 += adler;
 
78
        if (sum2 >= BASE)
 
79
            sum2 -= BASE;
 
80
        return adler | (sum2 << 16);
 
81
    }
 
82
 
 
83
    /* initial Adler-32 value (deferred check for len == 1 speed) */
 
84
    if (buf == Z_NULL)
 
85
        return 1L;
 
86
 
 
87
    /* in case short lengths are provided, keep it somewhat fast */
 
88
    if (len < 16) {
 
89
        while (len--) {
 
90
            adler += *buf++;
 
91
            sum2 += adler;
 
92
        }
 
93
        if (adler >= BASE)
 
94
            adler -= BASE;
 
95
        MOD4(sum2);             /* only added so many BASE's */
 
96
        return adler | (sum2 << 16);
 
97
    }
 
98
 
 
99
    /* do length NMAX blocks -- requires just one modulo operation */
 
100
    while (len >= NMAX) {
 
101
        len -= NMAX;
 
102
        n = NMAX / 16;          /* NMAX is divisible by 16 */
 
103
        do {
 
104
            DO16(buf);          /* 16 sums unrolled */
 
105
            buf += 16;
 
106
        } while (--n);
 
107
        MOD(adler);
 
108
        MOD(sum2);
 
109
    }
 
110
 
 
111
    /* do remaining bytes (less than NMAX, still just one modulo) */
 
112
    if (len) {                  /* avoid modulos if none remaining */
 
113
        while (len >= 16) {
 
114
            len -= 16;
 
115
            DO16(buf);
 
116
            buf += 16;
 
117
        }
 
118
        while (len--) {
 
119
            adler += *buf++;
 
120
            sum2 += adler;
 
121
        }
 
122
        MOD(adler);
 
123
        MOD(sum2);
 
124
    }
 
125
 
 
126
    /* return recombined sums */
 
127
    return adler | (sum2 << 16);
 
128
}
 
129
 
 
130
/* ========================================================================= */
 
131
local uLong adler32_combine_(adler1, adler2, len2)
 
132
    uLong adler1;
 
133
    uLong adler2;
 
134
    z_off64_t len2;
 
135
{
 
136
    unsigned long sum1;
 
137
    unsigned long sum2;
 
138
    unsigned rem;
 
139
 
 
140
    /* the derivation of this formula is left as an exercise for the reader */
 
141
    rem = (unsigned)(len2 % BASE);
 
142
    sum1 = adler1 & 0xffff;
 
143
    sum2 = rem * sum1;
 
144
    MOD(sum2);
 
145
    sum1 += (adler2 & 0xffff) + BASE - 1;
 
146
    sum2 += ((adler1 >> 16) & 0xffff) + ((adler2 >> 16) & 0xffff) + BASE - rem;
 
147
    if (sum1 >= BASE) sum1 -= BASE;
 
148
    if (sum1 >= BASE) sum1 -= BASE;
 
149
    if (sum2 >= (BASE << 1)) sum2 -= (BASE << 1);
 
150
    if (sum2 >= BASE) sum2 -= BASE;
 
151
    return sum1 | (sum2 << 16);
 
152
}
 
153
 
 
154
/* ========================================================================= */
 
155
uLong ZEXPORT adler32_combine(adler1, adler2, len2)
 
156
    uLong adler1;
 
157
    uLong adler2;
 
158
    z_off_t len2;
 
159
{
 
160
    return adler32_combine_(adler1, adler2, len2);
 
161
}
 
162
 
 
163
uLong ZEXPORT adler32_combine64(adler1, adler2, len2)
 
164
    uLong adler1;
 
165
    uLong adler2;
 
166
    z_off64_t len2;
 
167
{
 
168
    return adler32_combine_(adler1, adler2, len2);
 
169
}