1 /*

     2  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.

     3  *

     4  * This code is free software; you can redistribute it and/or modify it

     5  * under the terms of the GNU General Public License version 2 only, as

     6  * published by the Free Software Foundation.  Oracle designates this

     7  * particular file as subject to the "Classpath" exception as provided

     8  * by Oracle in the LICENSE file that accompanied this code.

     9  *

    10  * This code is distributed in the hope that it will be useful, but WITHOUT

    11  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or

    12  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License

    13  * version 2 for more details (a copy is included in the LICENSE file that

    14  * accompanied this code).

    15  *

    16  * You should have received a copy of the GNU General Public License version

    17  * 2 along with this work; if not, write to the Free Software Foundation,

    18  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.

    19  *

    20  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA

    21  * or visit www.oracle.com if you need additional information or have any

    22  * questions.

    23  */

    24 

    25 /* adler32.c -- compute the Adler-32 checksum of a data stream

    26  * Copyright (C) 1995-2004 Mark Adler

    27  * For conditions of distribution and use, see copyright notice in zlib.h

    28  */

    29 

    30 /* @(#) $Id$ */

    31 

    32 #define ZLIB_INTERNAL

    33 #include "zlib.h"

    34 

    35 #define BASE 65521UL    /* largest prime smaller than 65536 */

    36 #define NMAX 5552

    37 /* NMAX is the largest n such that 255n(n+1)/2 + (n+1)(BASE-1) <= 2^32-1 */

    38 

    39 #define DO1(buf,i)  {adler += (buf)[i]; sum2 += adler;}

    40 #define DO2(buf,i)  DO1(buf,i); DO1(buf,i+1);

    41 #define DO4(buf,i)  DO2(buf,i); DO2(buf,i+2);

    42 #define DO8(buf,i)  DO4(buf,i); DO4(buf,i+4);

    43 #define DO16(buf)   DO8(buf,0); DO8(buf,8);

    44 

    45 /* use NO_DIVIDE if your processor does not do division in hardware */

    46 #ifdef NO_DIVIDE

    47 #  define MOD(a) \

    48     do { \

    49         if (a >= (BASE << 16)) a -= (BASE << 16); \

    50         if (a >= (BASE << 15)) a -= (BASE << 15); \

    51         if (a >= (BASE << 14)) a -= (BASE << 14); \

    52         if (a >= (BASE << 13)) a -= (BASE << 13); \

    53         if (a >= (BASE << 12)) a -= (BASE << 12); \

    54         if (a >= (BASE << 11)) a -= (BASE << 11); \

    55         if (a >= (BASE << 10)) a -= (BASE << 10); \

    56         if (a >= (BASE << 9)) a -= (BASE << 9); \

    57         if (a >= (BASE << 8)) a -= (BASE << 8); \

    58         if (a >= (BASE << 7)) a -= (BASE << 7); \

    59         if (a >= (BASE << 6)) a -= (BASE << 6); \

    60         if (a >= (BASE << 5)) a -= (BASE << 5); \

    61         if (a >= (BASE << 4)) a -= (BASE << 4); \

    62         if (a >= (BASE << 3)) a -= (BASE << 3); \

    63         if (a >= (BASE << 2)) a -= (BASE << 2); \

    64         if (a >= (BASE << 1)) a -= (BASE << 1); \

    65         if (a >= BASE) a -= BASE; \

    66     } while (0)

    67 #  define MOD4(a) \

    68     do { \

    69         if (a >= (BASE << 4)) a -= (BASE << 4); \

    70         if (a >= (BASE << 3)) a -= (BASE << 3); \

    71         if (a >= (BASE << 2)) a -= (BASE << 2); \

    72         if (a >= (BASE << 1)) a -= (BASE << 1); \

    73         if (a >= BASE) a -= BASE; \

    74     } while (0)

    75 #else

    76 #  define MOD(a) a %= BASE

    77 #  define MOD4(a) a %= BASE

    78 #endif

    79 

    80 /* ========================================================================= */

    81 uLong ZEXPORT adler32(adler, buf, len)

    82     uLong adler;

    83     const Bytef *buf;

    84     uInt len;

    85 {

    86     unsigned long sum2;

    87     unsigned n;

    88 

    89     /* split Adler-32 into component sums */

    90     sum2 = (adler >> 16) & 0xffff;

    91     adler &= 0xffff;

    92 

    93     /* in case user likes doing a byte at a time, keep it fast */

    94     if (len == 1) {

    95         adler += buf[0];

    96         if (adler >= BASE)

    97             adler -= BASE;

    98         sum2 += adler;

    99         if (sum2 >= BASE)

   100             sum2 -= BASE;

   101         return adler | (sum2 << 16);

   102     }

   103 

   104     /* initial Adler-32 value (deferred check for len == 1 speed) */

   105     if (buf == Z_NULL)

   106         return 1L;

   107 

   108     /* in case short lengths are provided, keep it somewhat fast */

   109     if (len < 16) {

   110         while (len--) {

   111             adler += *buf++;

   112             sum2 += adler;

   113         }

   114         if (adler >= BASE)

   115             adler -= BASE;

   116         MOD4(sum2);             /* only added so many BASE's */

   117         return adler | (sum2 << 16);

   118     }

   119 

   120     /* do length NMAX blocks -- requires just one modulo operation */

   121     while (len >= NMAX) {

   122         len -= NMAX;

   123         n = NMAX / 16;          /* NMAX is divisible by 16 */

   124         do {

   125             DO16(buf);          /* 16 sums unrolled */

   126             buf += 16;

   127         } while (--n);

   128         MOD(adler);

   129         MOD(sum2);

   130     }

   131 

   132     /* do remaining bytes (less than NMAX, still just one modulo) */

   133     if (len) {                  /* avoid modulos if none remaining */

   134         while (len >= 16) {

   135             len -= 16;

   136             DO16(buf);

   137             buf += 16;

   138         }

   139         while (len--) {

   140             adler += *buf++;

   141             sum2 += adler;

   142         }

   143         MOD(adler);

   144         MOD(sum2);

   145     }

   146 

   147     /* return recombined sums */

   148     return adler | (sum2 << 16);

   149 }

   150 

   151 /* ========================================================================= */

   152 uLong ZEXPORT adler32_combine(adler1, adler2, len2)

   153     uLong adler1;

   154     uLong adler2;

   155     z_off_t len2;

   156 {

   157     unsigned long sum1;

   158     unsigned long sum2;

   159     unsigned rem;

   160 

   161     /* the derivation of this formula is left as an exercise for the reader */

   162     rem = (unsigned)(len2 % BASE);

   163     sum1 = adler1 & 0xffff;

   164     sum2 = rem * sum1;

   165     MOD(sum2);

   166     sum1 += (adler2 & 0xffff) + BASE - 1;

   167     sum2 += ((adler1 >> 16) & 0xffff) + ((adler2 >> 16) & 0xffff) + BASE - rem;

   168     if (sum1 > BASE) sum1 -= BASE;

   169     if (sum1 > BASE) sum1 -= BASE;

   170     if (sum2 > (BASE << 1)) sum2 -= (BASE << 1);

   171     if (sum2 > BASE) sum2 -= BASE;

   172     return sum1 | (sum2 << 16);

   173 }