← Back to branch summary

~ubuntu-branches/debian/sid/subversion/sid

« back to all changes in this revision

Viewing changes to subversion/libsvn_subr/fnv1a.c

  • Committer: Package Import Robot
  • Author(s): James McCoy
  • Date: 2015-08-07 21:32:47 UTC
  • mfrom: (0.2.15) (4.1.7 experimental)
  • Revision ID: package-import@ubuntu.com-20150807213247-ozyewtmgsr6tkewl
Tags: 1.9.0-1
http://bugs.debian.org/791844
* Upload to unstable
* New upstream release.
  + Security fixes
    - CVE-2015-3184: Mixed anonymous/authenticated path-based authz with
      httpd 2.4
    - CVE-2015-3187: svn_repos_trace_node_locations() reveals paths hidden
      by authz
* Add >= 2.7 requirement for python-all-dev Build-Depends, needed to run
  tests.
* Remove Build-Conflicts against ruby-test-unit.  (Closes: #791844)
* Remove patches/apache_module_dependency in favor of expressing the
  dependencies in authz_svn.load/dav_svn.load.
* Build-Depend on apache2-dev (>= 2.4.16) to ensure ap_some_authn_required()
  is available when building mod_authz_svn and Depend on apache2-bin (>=
  2.4.16) for runtime support.

Show diffs side-by-side

added added

removed removed

Lines of Context:
subversion/libsvn_subr/fnv1a.c
 
1
/*
 
2
 * fnv1a.c :  routines to create checksums derived from FNV-1a
 
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
#define APR_WANT_BYTEFUNC
 
25
 
 
26
#include <assert.h>
 
27
#include <apr.h>
 
28
 
 
29
#include "private/svn_subr_private.h"
 
30
#include "fnv1a.h"
 
31
 
 
32
/**
 
33
 * See http://www.isthe.com/chongo/tech/comp/fnv/ for more info on FNV-1
 
34
 */
 
35
 
 
36
/* FNV-1 32 bit constants taken from
 
37
 * http://www.isthe.com/chongo/tech/comp/fnv/
 
38
 */
 
39
#define FNV1_PRIME_32 0x01000193
 
40
#define FNV1_BASE_32 2166136261U
 
41
 
 
42
/* FNV-1a core implementation returning a 32 bit checksum over the first
 
43
 * LEN bytes in INPUT.  HASH is the checksum over preceding data (if any).
 
44
 */
 
45
static apr_uint32_t
 
46
fnv1a_32(apr_uint32_t hash, const void *input, apr_size_t len)
 
47
{
 
48
  const unsigned char *data = input;
 
49
  const unsigned char *end = data + len;
 
50
 
 
51
  for (; data != end; ++data)
 
52
    {
 
53
      hash ^= *data;
 
54
      hash *= FNV1_PRIME_32;
 
55
    }
 
56
 
 
57
  return hash;
 
58
}
 
59
 
 
60
/* Number of interleaved FVN-1a checksums we calculate for the modified
 
61
 * checksum algorithm.
 
62
 */
 
63
enum { SCALING = 4 };
 
64
 
 
65
/* FNV-1a core implementation updating 4 interleaved checksums in HASHES
 
66
 * over the first LEN bytes in INPUT.  This will only process multiples
 
67
 * of 4 and return the number of bytes processed.  LEN - ReturnValue < 4.
 
68
 */
 
69
static apr_size_t
 
70
fnv1a_32x4(apr_uint32_t hashes[SCALING], const void *input, apr_size_t len)
 
71
{
 
72
  /* calculate SCALING interleaved FNV-1a hashes while the input
 
73
     is large enough */
 
74
  const unsigned char *data = input;
 
75
  const unsigned char *end = data + len;
 
76
  for (; data + SCALING <= end; data += SCALING)
 
77
    {
 
78
      hashes[0] ^= data[0];
 
79
      hashes[0] *= FNV1_PRIME_32;
 
80
      hashes[1] ^= data[1];
 
81
      hashes[1] *= FNV1_PRIME_32;
 
82
      hashes[2] ^= data[2];
 
83
      hashes[2] *= FNV1_PRIME_32;
 
84
      hashes[3] ^= data[3];
 
85
      hashes[3] *= FNV1_PRIME_32;
 
86
    }
 
87
 
 
88
  return data - (const unsigned char *)input;
 
89
}
 
90
 
 
91
/* Combine interleaved HASHES plus LEN bytes from INPUT into a single
 
92
 * 32 bit hash value and return that.  LEN must be < 4.
 
93
 */
 
94
static apr_uint32_t
 
95
finalize_fnv1a_32x4(apr_uint32_t hashes[SCALING],
 
96
                    const void *input,
 
97
                    apr_size_t len)
 
98
{
 
99
  char final_data[sizeof(apr_uint32_t) * SCALING + SCALING - 1];
 
100
  apr_size_t i;
 
101
  assert(len < SCALING);
 
102
 
 
103
  for (i = 0; i < SCALING; ++i)
 
104
    hashes[i] = htonl(hashes[i]);
 
105
 
 
106
  /* run FNV-1a over the interleaved checksums plus the remaining
 
107
     (odd-lotted) input data */
 
108
  memcpy(final_data, hashes, sizeof(apr_uint32_t) * SCALING);
 
109
  if (len)
 
110
    memcpy(final_data + sizeof(apr_uint32_t) * SCALING, input, len);
 
111
 
 
112
  return fnv1a_32(FNV1_BASE_32,
 
113
                  final_data,
 
114
                  sizeof(apr_uint32_t) * SCALING + len);
 
115
}
 
116
 
 
117
apr_uint32_t
 
118
svn__fnv1a_32(const void *input, apr_size_t len)
 
119
{
 
120
  return fnv1a_32(FNV1_BASE_32, input, len);
 
121
}
 
122
 
 
123
apr_uint32_t
 
124
svn__fnv1a_32x4(const void *input, apr_size_t len)
 
125
{
 
126
  apr_uint32_t hashes[SCALING]
 
127
    = { FNV1_BASE_32, FNV1_BASE_32, FNV1_BASE_32, FNV1_BASE_32 };
 
128
  apr_size_t processed = fnv1a_32x4(hashes, input, len);
 
129
 
 
130
  return finalize_fnv1a_32x4(hashes,
 
131
                             (const char *)input + processed,
 
132
                             len - processed);
 
133
}
 
134
 
 
135
void
 
136
svn__fnv1a_32x4_raw(apr_uint32_t hashes[4],
 
137
                    const void *input,
 
138
                    apr_size_t len)
 
139
{
 
140
  apr_size_t processed;
 
141
 
 
142
  apr_size_t i;
 
143
  for (i = 0; i < SCALING; ++i)
 
144
    hashes[i] = FNV1_BASE_32;
 
145
 
 
146
  /* Process full 16 byte chunks. */
 
147
  processed = fnv1a_32x4(hashes, input, len);
 
148
 
 
149
  /* Fold the remainder (if any) into the first hash. */
 
150
  hashes[0] = fnv1a_32(hashes[0], (const char *)input + processed,
 
151
                       len - processed);
 
152
}
 
153
 
 
154
struct svn_fnv1a_32__context_t
 
155
{
 
156
  apr_uint32_t hash;
 
157
};
 
158
 
 
159
svn_fnv1a_32__context_t *
 
160
svn_fnv1a_32__context_create(apr_pool_t *pool)
 
161
{
 
162
  svn_fnv1a_32__context_t *context = apr_palloc(pool, sizeof(*context));
 
163
  context->hash = FNV1_BASE_32;
 
164
 
 
165
  return context;
 
166
}
 
167
 
 
168
void
 
169
svn_fnv1a_32__update(svn_fnv1a_32__context_t *context,
 
170
                     const void *data,
 
171
                     apr_size_t len)
 
172
{
 
173
  context->hash = fnv1a_32(context->hash, data, len);
 
174
}
 
175
 
 
176
apr_uint32_t
 
177
svn_fnv1a_32__finalize(svn_fnv1a_32__context_t *context)
 
178
{
 
179
  return context->hash;
 
180
}
 
181
 
 
182
 
 
183
struct svn_fnv1a_32x4__context_t
 
184
{
 
185
  apr_uint32_t hashes[SCALING];
 
186
  apr_size_t buffered;
 
187
  char buffer[SCALING];
 
188
};
 
189
 
 
190
svn_fnv1a_32x4__context_t *
 
191
svn_fnv1a_32x4__context_create(apr_pool_t *pool)
 
192
{
 
193
  svn_fnv1a_32x4__context_t *context = apr_palloc(pool, sizeof(*context));
 
194
 
 
195
  context->hashes[0] = FNV1_BASE_32;
 
196
  context->hashes[1] = FNV1_BASE_32;
 
197
  context->hashes[2] = FNV1_BASE_32;
 
198
  context->hashes[3] = FNV1_BASE_32;
 
199
 
 
200
  context->buffered = 0;
 
201
 
 
202
  return context;
 
203
}
 
204
 
 
205
void
 
206
svn_fnv1a_32x4__update(svn_fnv1a_32x4__context_t *context,
 
207
                       const void *data,
 
208
                       apr_size_t len)
 
209
{
 
210
  apr_size_t processed;
 
211
 
 
212
  if (context->buffered)
 
213
    {
 
214
      apr_size_t to_copy = SCALING - context->buffered;
 
215
      if (to_copy > len)
 
216
        {
 
217
          memcpy(context->buffer + context->buffered, data, len);
 
218
          context->buffered += len;
 
219
          return;
 
220
        }
 
221
 
 
222
      memcpy(context->buffer + context->buffered, data, to_copy);
 
223
      data = (const char *)data + to_copy;
 
224
      len -= to_copy;
 
225
 
 
226
      fnv1a_32x4(context->hashes, context->buffer, SCALING);
 
227
      context->buffered = 0;
 
228
    }
 
229
 
 
230
  processed = fnv1a_32x4(context->hashes, data, len);
 
231
  if (processed != len)
 
232
    {
 
233
      context->buffered = len - processed;
 
234
      memcpy(context->buffer,
 
235
             (const char*)data + processed,
 
236
             len - processed);
 
237
    }
 
238
}
 
239
 
 
240
apr_uint32_t
 
241
svn_fnv1a_32x4__finalize(svn_fnv1a_32x4__context_t *context)
 
242
{
 
243
  return finalize_fnv1a_32x4(context->hashes,
 
244
                             context->buffer,
 
245
                             context->buffered);
 
246
}