lemon-project-template-glpk

annotate deps/glpk/src/zlib/adler32.c @ 9:33de93886c88

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