1/* 2 * Copyright (c) 2008 Apple Inc. All rights reserved. 3 * 4 * @APPLE_OSREFERENCE_LICENSE_HEADER_START@ 5 * 6 * This file contains Original Code and/or Modifications of Original Code 7 * as defined in and that are subject to the Apple Public Source License 8 * Version 2.0 (the 'License'). You may not use this file except in 9 * compliance with the License. The rights granted to you under the License 10 * may not be used to create, or enable the creation or redistribution of, 11 * unlawful or unlicensed copies of an Apple operating system, or to 12 * circumvent, violate, or enable the circumvention or violation of, any 13 * terms of an Apple operating system software license agreement. 14 * 15 * Please obtain a copy of the License at 16 * http://www.opensource.apple.com/apsl/ and read it before using this file. 17 * 18 * The Original Code and all software distributed under the License are 19 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER 20 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES, 21 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY, 22 * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT. 23 * Please see the License for the specific language governing rights and 24 * limitations under the License. 25 * 26 * @APPLE_OSREFERENCE_LICENSE_HEADER_END@ 27 */ 28/* adler32.c -- compute the Adler-32 checksum of a data stream 29 * Copyright (C) 1995-2004 Mark Adler 30 * For conditions of distribution and use, see copyright notice in zlib.h 31 */ 32 33/* @(#) $Id$ */ 34 35 36#define ZLIB_INTERNAL 37#if KERNEL 38 #include <libkern/zlib.h> 39#else 40 #include "zlib.h" 41#endif /* KERNEL */ 42 43 44#define BASE 65521UL /* largest prime smaller than 65536 */ 45#define NMAX 5552 46/* NMAX is the largest n such that 255n(n+1)/2 + (n+1)(BASE-1) <= 2^32-1 */ 47 48#define DO1(buf,i) {adler += (buf)[i]; sum2 += adler;} 49#define DO2(buf,i) DO1(buf,i); DO1(buf,i+1); 50#define DO4(buf,i) DO2(buf,i); DO2(buf,i+2); 51#define DO8(buf,i) DO4(buf,i); DO4(buf,i+4); 52#define DO16(buf) DO8(buf,0); DO8(buf,8); 53 54/* use NO_DIVIDE if your processor does not do division in hardware */ 55#ifdef NO_DIVIDE 56# define MOD(a) \ 57 do { \ 58 if (a >= (BASE << 16)) a -= (BASE << 16); \ 59 if (a >= (BASE << 15)) a -= (BASE << 15); \ 60 if (a >= (BASE << 14)) a -= (BASE << 14); \ 61 if (a >= (BASE << 13)) a -= (BASE << 13); \ 62 if (a >= (BASE << 12)) a -= (BASE << 12); \ 63 if (a >= (BASE << 11)) a -= (BASE << 11); \ 64 if (a >= (BASE << 10)) a -= (BASE << 10); \ 65 if (a >= (BASE << 9)) a -= (BASE << 9); \ 66 if (a >= (BASE << 8)) a -= (BASE << 8); \ 67 if (a >= (BASE << 7)) a -= (BASE << 7); \ 68 if (a >= (BASE << 6)) a -= (BASE << 6); \ 69 if (a >= (BASE << 5)) a -= (BASE << 5); \ 70 if (a >= (BASE << 4)) a -= (BASE << 4); \ 71 if (a >= (BASE << 3)) a -= (BASE << 3); \ 72 if (a >= (BASE << 2)) a -= (BASE << 2); \ 73 if (a >= (BASE << 1)) a -= (BASE << 1); \ 74 if (a >= BASE) a -= BASE; \ 75 } while (0) 76# define MOD4(a) \ 77 do { \ 78 if (a >= (BASE << 4)) a -= (BASE << 4); \ 79 if (a >= (BASE << 3)) a -= (BASE << 3); \ 80 if (a >= (BASE << 2)) a -= (BASE << 2); \ 81 if (a >= (BASE << 1)) a -= (BASE << 1); \ 82 if (a >= BASE) a -= BASE; \ 83 } while (0) 84#else 85# define MOD(a) a %= BASE 86# define MOD4(a) a %= BASE 87#endif 88 89/* ========================================================================= */ 90uLong ZEXPORT adler32(adler, buf, len) 91 uLong adler; 92 const Bytef *buf; 93 uInt len; 94{ 95 unsigned long sum2; 96 unsigned n; 97 98 /* split Adler-32 into component sums */ 99 sum2 = (adler >> 16) & 0xffff; 100 adler &= 0xffff; 101 102 /* in case user likes doing a byte at a time, keep it fast */ 103 if (len == 1) { 104 adler += buf[0]; 105 if (adler >= BASE) 106 adler -= BASE; 107 sum2 += adler; 108 if (sum2 >= BASE) 109 sum2 -= BASE; 110 return adler | (sum2 << 16); 111 } 112 113 /* initial Adler-32 value (deferred check for len == 1 speed) */ 114 if (buf == Z_NULL) 115 return 1L; 116 117 /* in case short lengths are provided, keep it somewhat fast */ 118 if (len < 16) { 119 while (len--) { 120 adler += *buf++; 121 sum2 += adler; 122 } 123 if (adler >= BASE) 124 adler -= BASE; 125 MOD4(sum2); /* only added so many BASE's */ 126 return adler | (sum2 << 16); 127 } 128 129 130 /* do length NMAX blocks -- requires just one modulo operation */ 131 while (len >= NMAX) { 132 len -= NMAX; 133 n = NMAX / 16; /* NMAX is divisible by 16 */ 134 do { 135 DO16(buf); /* 16 sums unrolled */ 136 buf += 16; 137 } while (--n); 138 MOD(adler); 139 MOD(sum2); 140 } 141 142 /* do remaining bytes (less than NMAX, still just one modulo) */ 143 if (len) { /* avoid modulos if none remaining */ 144 while (len >= 16) { 145 len -= 16; 146 DO16(buf); 147 buf += 16; 148 } 149 while (len--) { 150 adler += *buf++; 151 sum2 += adler; 152 } 153 MOD(adler); 154 MOD(sum2); 155 } 156 157 /* return recombined sums */ 158 return adler | (sum2 << 16); 159} 160 161/* ========================================================================= */ 162uLong ZEXPORT adler32_combine(adler1, adler2, len2) 163 uLong adler1; 164 uLong adler2; 165 z_off_t len2; 166{ 167 unsigned long sum1; 168 unsigned long sum2; 169 unsigned rem; 170 171 /* the derivation of this formula is left as an exercise for the reader */ 172 rem = (unsigned)(len2 % BASE); 173 sum1 = adler1 & 0xffff; 174 sum2 = rem * sum1; 175 MOD(sum2); 176 sum1 += (adler2 & 0xffff) + BASE - 1; 177 sum2 += ((adler1 >> 16) & 0xffff) + ((adler2 >> 16) & 0xffff) + BASE - rem; 178 if (sum1 > BASE) sum1 -= BASE; 179 if (sum1 > BASE) sum1 -= BASE; 180 if (sum2 > (BASE << 1)) sum2 -= (BASE << 1); 181 if (sum2 > BASE) sum2 -= BASE; 182 return sum1 | (sum2 << 16); 183} 184