contrib/subversion/subversion/libsvn_subr/adler32.c

   1 /*
   2  * adler32.c :  routines for handling Adler-32 checksums
   3  *
   4  * ====================================================================
   5  *    Licensed to the Apache Software Foundation (ASF) under one
   6  *    or more contributor license agreements.  See the NOTICE file
   7  *    distributed with this work for additional information
   8  *    regarding copyright ownership.  The ASF licenses this file
   9  *    to you under the Apache License, Version 2.0 (the
  10  *    "License"); you may not use this file except in compliance
  11  *    with the License.  You may obtain a copy of the License at
  12  *
  13  *      http://www.apache.org/licenses/LICENSE-2.0
  14  *
  15  *    Unless required by applicable law or agreed to in writing,
  16  *    software distributed under the License is distributed on an
  17  *    "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
  18  *    KIND, either express or implied.  See the License for the
  19  *    specific language governing permissions and limitations
  20  *    under the License.
  21  * ====================================================================
  22  */
  23
  24
  25 #include <apr.h>
  26 #include <zlib.h>
  27
  28 #include "private/svn_adler32.h"
  29
  30 /**
  31  * An Adler-32 implementation per RFC1950.
  32  *
  33  * "The Adler-32 algorithm is much faster than the CRC32 algorithm yet
  34  * still provides an extremely low probability of undetected errors"
  35  */
  36
  37 /*
  38  * 65521 is the largest prime less than 65536.
  39  * "That 65521 is prime is important to avoid a possible large class of
  40  *  two-byte errors that leave the check unchanged."
  41  */
  42 #define ADLER_MOD_BASE 65521
  43
  44 /*
  45  * Start with CHECKSUM and update the checksum by processing a chunk
  46  * of DATA sized LEN.
  47  */
  48 apr_uint32_t
  49 svn__adler32(apr_uint32_t checksum, const char *data, apr_off_t len)
  50 {
  51   /* The actual limit can be set somewhat higher but should
  52    * not be lower because the SIMD code would not be used
  53    * in that case.
  54    *
  55    * However, it must be lower than 5552 to make sure our local
  56    * implementation does not suffer from overflows.
  57    */
  58   if (len >= 80)
  59     {
  60       /* Larger buffers can be effiently handled by Marc Adler's
  61        * optimized code. Also, new zlib versions will come with
  62        * SIMD code for x86 and x64.
  63        */
  64       return (apr_uint32_t)adler32(checksum,
  65                                    (const Bytef *)data,
  66                                    (uInt)len);
  67     }
  68   else
  69     {
  70       const unsigned char *input = (const unsigned char *)data;
  71       apr_uint32_t s1 = checksum & 0xFFFF;
  72       apr_uint32_t s2 = checksum >> 16;
  73       apr_uint32_t b;
  74
  75       /* Some loop unrolling
  76        * (approx. one clock tick per byte + 2 ticks loop overhead)
  77        */
  78       for (; len >= 8; len -= 8, input += 8)
  79       {
  80         s1 += input[0]; s2 += s1;
  81         s1 += input[1]; s2 += s1;
  82         s1 += input[2]; s2 += s1;
  83         s1 += input[3]; s2 += s1;
  84         s1 += input[4]; s2 += s1;
  85         s1 += input[5]; s2 += s1;
  86         s1 += input[6]; s2 += s1;
  87         s1 += input[7]; s2 += s1;
  88       }
  89
  90       /* Adler-32 calculation as a simple two ticks per iteration loop.
  91        */
  92       while (len--)
  93         {
  94           b = *input++;
  95           s1 += b;
  96           s2 += s1;
  97         }
  98
  99       return ((s2 % ADLER_MOD_BASE) << 16) | (s1 % ADLER_MOD_BASE);
 100     }
 101 }