adler32.c revision 299742 
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 */
48apr_uint32_t
49svn__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 efficiently 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}
102