← Back to branch summary

~ubuntu-branches/ubuntu/vivid/samba/vivid

« back to all changes in this revision

Viewing changes to lib/tdb/common/hash.c

  • Committer: Package Import Robot
  • Author(s): Chuck Short
  • Date: 2011-12-21 13:18:04 UTC
  • mfrom: (0.39.21 sid)
  • Revision ID: package-import@ubuntu.com-20111221131804-xtlr39wx6njehxxr
Tags: 2:3.6.1-3ubuntu1
* Merge from Debian testing.  Remaining changes:
  + debian/patches/VERSION.patch:
    - set SAMBA_VERSION_SUFFIX to Ubuntu.
  + debian/patches/error-trans.fix-276472:
    - Add the translation of Unix Error code -ENOTSUP to NT Error Code
    - NT_STATUS_NOT_SUPPORTED to prevent the Permission denied error.
  + debian/smb.conf:
    - add "(Samba, Ubuntu)" to server string.
    - comment out the default [homes] share, and add a comment about
      "valid users = %S" to show users how to restrict access to
      \\server\username to only username.
    - Set 'usershare allow guests', so that usershare admins are 
      allowed to create public shares in addition to authenticated
      ones.
    - add map to guest = Bad user, maps bad username to guest access.
  + debian/samba-common.config:
    - Do not change priority to high if dhclient3 is installed.
    - Use priority medium instead of high for the workgroup question.
  + debian/control:
    - Don't build against or suggest ctdb.
    - Add dependency on samba-common-bin to samba.
  + Add ufw integration:
    - Created debian/samba.ufw.profile
    - debian/rules, debian/samba.dirs, debian/samba.files: install
      profile
    - debian/control: have samba suggest ufw
  + Add apport hook:
    - Created debian/source_samba.py.
    - debian/rules, debian/samba.dirs, debian/samba-common-bin.files: install
  + Switch to upstart:
    - Add debian/samba.{nmbd,smbd}.upstart.
  + debian/samba.logrotate, debian/samba-common.dhcp, debian/samba.if-up:
    - Make them upstart compatible
  + debian/samba.postinst: 
    - Avoid scary pdbedit warnings on first import.
  + debian/samba-common.postinst: Add more informative error message for
    the case where smb.conf was manually deleted
  + debian/patches/fix-debuglevel-name-conflict.patch: don't use 'debug_level'
    as a global variable name in an NSS module 
  + Dropped:
    - debian/patches/error-trans.fix-276472
    - debian/patches/fix-debuglevel-name-conflict.patch

Show diffs side-by-side

added added

removed removed

Lines of Context:
lib/tdb/common/hash.c
 
1
 /*
 
2
   Unix SMB/CIFS implementation.
 
3
 
 
4
   trivial database library
 
5
 
 
6
   Copyright (C) Rusty Russell             2010
 
7
 
 
8
     ** NOTE! The following LGPL license applies to the tdb
 
9
     ** library. This does NOT imply that all of Samba is released
 
10
     ** under the LGPL
 
11
 
 
12
   This library is free software; you can redistribute it and/or
 
13
   modify it under the terms of the GNU Lesser General Public
 
14
   License as published by the Free Software Foundation; either
 
15
   version 3 of the License, or (at your option) any later version.
 
16
 
 
17
   This library is distributed in the hope that it will be useful,
 
18
   but WITHOUT ANY WARRANTY; without even the implied warranty of
 
19
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 
20
   Lesser General Public License for more details.
 
21
 
 
22
   You should have received a copy of the GNU Lesser General Public
 
23
   License along with this library; if not, see <http://www.gnu.org/licenses/>.
 
24
*/
 
25
#include "tdb_private.h"
 
26
 
 
27
/* This is based on the hash algorithm from gdbm */
 
28
unsigned int tdb_old_hash(TDB_DATA *key)
 
29
{
 
30
        uint32_t value; /* Used to compute the hash value.  */
 
31
        uint32_t   i;   /* Used to cycle through random values. */
 
32
 
 
33
        /* Set the initial value from the key size. */
 
34
        for (value = 0x238F13AF * key->dsize, i=0; i < key->dsize; i++)
 
35
                value = (value + (key->dptr[i] << (i*5 % 24)));
 
36
 
 
37
        return (1103515243 * value + 12345);
 
38
}
 
39
 
 
40
#ifndef WORDS_BIGENDIAN
 
41
# define HASH_LITTLE_ENDIAN 1
 
42
# define HASH_BIG_ENDIAN 0
 
43
#else
 
44
# define HASH_LITTLE_ENDIAN 0
 
45
# define HASH_BIG_ENDIAN 1
 
46
#endif
 
47
 
 
48
/*
 
49
-------------------------------------------------------------------------------
 
50
lookup3.c, by Bob Jenkins, May 2006, Public Domain.
 
51
 
 
52
These are functions for producing 32-bit hashes for hash table lookup.
 
53
hash_word(), hashlittle(), hashlittle2(), hashbig(), mix(), and final()
 
54
are externally useful functions.  Routines to test the hash are included
 
55
if SELF_TEST is defined.  You can use this free for any purpose.  It's in
 
56
the public domain.  It has no warranty.
 
57
 
 
58
You probably want to use hashlittle().  hashlittle() and hashbig()
 
59
hash byte arrays.  hashlittle() is is faster than hashbig() on
 
60
little-endian machines.  Intel and AMD are little-endian machines.
 
61
On second thought, you probably want hashlittle2(), which is identical to
 
62
hashlittle() except it returns two 32-bit hashes for the price of one.
 
63
You could implement hashbig2() if you wanted but I haven't bothered here.
 
64
 
 
65
If you want to find a hash of, say, exactly 7 integers, do
 
66
  a = i1;  b = i2;  c = i3;
 
67
  mix(a,b,c);
 
68
  a += i4; b += i5; c += i6;
 
69
  mix(a,b,c);
 
70
  a += i7;
 
71
  final(a,b,c);
 
72
then use c as the hash value.  If you have a variable length array of
 
73
4-byte integers to hash, use hash_word().  If you have a byte array (like
 
74
a character string), use hashlittle().  If you have several byte arrays, or
 
75
a mix of things, see the comments above hashlittle().
 
76
 
 
77
Why is this so big?  I read 12 bytes at a time into 3 4-byte integers,
 
78
then mix those integers.  This is fast (you can do a lot more thorough
 
79
mixing with 12*3 instructions on 3 integers than you can with 3 instructions
 
80
on 1 byte), but shoehorning those bytes into integers efficiently is messy.
 
81
*/
 
82
 
 
83
#define hashsize(n) ((uint32_t)1<<(n))
 
84
#define hashmask(n) (hashsize(n)-1)
 
85
#define rot(x,k) (((x)<<(k)) | ((x)>>(32-(k))))
 
86
 
 
87
/*
 
88
-------------------------------------------------------------------------------
 
89
mix -- mix 3 32-bit values reversibly.
 
90
 
 
91
This is reversible, so any information in (a,b,c) before mix() is
 
92
still in (a,b,c) after mix().
 
93
 
 
94
If four pairs of (a,b,c) inputs are run through mix(), or through
 
95
mix() in reverse, there are at least 32 bits of the output that
 
96
are sometimes the same for one pair and different for another pair.
 
97
This was tested for:
 
98
* pairs that differed by one bit, by two bits, in any combination
 
99
  of top bits of (a,b,c), or in any combination of bottom bits of
 
100
  (a,b,c).
 
101
* "differ" is defined as +, -, ^, or ~^.  For + and -, I transformed
 
102
  the output delta to a Gray code (a^(a>>1)) so a string of 1's (as
 
103
  is commonly produced by subtraction) look like a single 1-bit
 
104
  difference.
 
105
* the base values were pseudorandom, all zero but one bit set, or
 
106
  all zero plus a counter that starts at zero.
 
107
 
 
108
Some k values for my "a-=c; a^=rot(c,k); c+=b;" arrangement that
 
109
satisfy this are
 
110
    4  6  8 16 19  4
 
111
    9 15  3 18 27 15
 
112
   14  9  3  7 17  3
 
113
Well, "9 15 3 18 27 15" didn't quite get 32 bits diffing
 
114
for "differ" defined as + with a one-bit base and a two-bit delta.  I
 
115
used http://burtleburtle.net/bob/hash/avalanche.html to choose
 
116
the operations, constants, and arrangements of the variables.
 
117
 
 
118
This does not achieve avalanche.  There are input bits of (a,b,c)
 
119
that fail to affect some output bits of (a,b,c), especially of a.  The
 
120
most thoroughly mixed value is c, but it doesn't really even achieve
 
121
avalanche in c.
 
122
 
 
123
This allows some parallelism.  Read-after-writes are good at doubling
 
124
the number of bits affected, so the goal of mixing pulls in the opposite
 
125
direction as the goal of parallelism.  I did what I could.  Rotates
 
126
seem to cost as much as shifts on every machine I could lay my hands
 
127
on, and rotates are much kinder to the top and bottom bits, so I used
 
128
rotates.
 
129
-------------------------------------------------------------------------------
 
130
*/
 
131
#define mix(a,b,c) \
 
132
{ \
 
133
  a -= c;  a ^= rot(c, 4);  c += b; \
 
134
  b -= a;  b ^= rot(a, 6);  a += c; \
 
135
  c -= b;  c ^= rot(b, 8);  b += a; \
 
136
  a -= c;  a ^= rot(c,16);  c += b; \
 
137
  b -= a;  b ^= rot(a,19);  a += c; \
 
138
  c -= b;  c ^= rot(b, 4);  b += a; \
 
139
}
 
140
 
 
141
/*
 
142
-------------------------------------------------------------------------------
 
143
final -- final mixing of 3 32-bit values (a,b,c) into c
 
144
 
 
145
Pairs of (a,b,c) values differing in only a few bits will usually
 
146
produce values of c that look totally different.  This was tested for
 
147
* pairs that differed by one bit, by two bits, in any combination
 
148
  of top bits of (a,b,c), or in any combination of bottom bits of
 
149
  (a,b,c).
 
150
* "differ" is defined as +, -, ^, or ~^.  For + and -, I transformed
 
151
  the output delta to a Gray code (a^(a>>1)) so a string of 1's (as
 
152
  is commonly produced by subtraction) look like a single 1-bit
 
153
  difference.
 
154
* the base values were pseudorandom, all zero but one bit set, or
 
155
  all zero plus a counter that starts at zero.
 
156
 
 
157
These constants passed:
 
158
 14 11 25 16 4 14 24
 
159
 12 14 25 16 4 14 24
 
160
and these came close:
 
161
  4  8 15 26 3 22 24
 
162
 10  8 15 26 3 22 24
 
163
 11  8 15 26 3 22 24
 
164
-------------------------------------------------------------------------------
 
165
*/
 
166
#define final(a,b,c) \
 
167
{ \
 
168
  c ^= b; c -= rot(b,14); \
 
169
  a ^= c; a -= rot(c,11); \
 
170
  b ^= a; b -= rot(a,25); \
 
171
  c ^= b; c -= rot(b,16); \
 
172
  a ^= c; a -= rot(c,4);  \
 
173
  b ^= a; b -= rot(a,14); \
 
174
  c ^= b; c -= rot(b,24); \
 
175
}
 
176
 
 
177
 
 
178
/*
 
179
-------------------------------------------------------------------------------
 
180
hashlittle() -- hash a variable-length key into a 32-bit value
 
181
  k       : the key (the unaligned variable-length array of bytes)
 
182
  length  : the length of the key, counting by bytes
 
183
  val2    : IN: can be any 4-byte value OUT: second 32 bit hash.
 
184
Returns a 32-bit value.  Every bit of the key affects every bit of
 
185
the return value.  Two keys differing by one or two bits will have
 
186
totally different hash values.  Note that the return value is better
 
187
mixed than val2, so use that first.
 
188
 
 
189
The best hash table sizes are powers of 2.  There is no need to do
 
190
mod a prime (mod is sooo slow!).  If you need less than 32 bits,
 
191
use a bitmask.  For example, if you need only 10 bits, do
 
192
  h = (h & hashmask(10));
 
193
In which case, the hash table should have hashsize(10) elements.
 
194
 
 
195
If you are hashing n strings (uint8_t **)k, do it like this:
 
196
  for (i=0, h=0; i<n; ++i) h = hashlittle( k[i], len[i], h);
 
197
 
 
198
By Bob Jenkins, 2006.  bob_jenkins@burtleburtle.net.  You may use this
 
199
code any way you wish, private, educational, or commercial.  It's free.
 
200
 
 
201
Use for hash table lookup, or anything where one collision in 2^^32 is
 
202
acceptable.  Do NOT use for cryptographic purposes.
 
203
-------------------------------------------------------------------------------
 
204
*/
 
205
 
 
206
static uint32_t hashlittle( const void *key, size_t length )
 
207
{
 
208
  uint32_t a,b,c;                                          /* internal state */
 
209
  union { const void *ptr; size_t i; } u;     /* needed for Mac Powerbook G4 */
 
210
 
 
211
  /* Set up the internal state */
 
212
  a = b = c = 0xdeadbeef + ((uint32_t)length);
 
213
 
 
214
  u.ptr = key;
 
215
  if (HASH_LITTLE_ENDIAN && ((u.i & 0x3) == 0)) {
 
216
    const uint32_t *k = (const uint32_t *)key;         /* read 32-bit chunks */
 
217
#ifdef VALGRIND
 
218
    const uint8_t  *k8;
 
219
#endif
 
220
 
 
221
    /*------ all but last block: aligned reads and affect 32 bits of (a,b,c) */
 
222
    while (length > 12)
 
223
    {
 
224
      a += k[0];
 
225
      b += k[1];
 
226
      c += k[2];
 
227
      mix(a,b,c);
 
228
      length -= 12;
 
229
      k += 3;
 
230
    }
 
231
 
 
232
    /*----------------------------- handle the last (probably partial) block */
 
233
    /*
 
234
     * "k[2]&0xffffff" actually reads beyond the end of the string, but
 
235
     * then masks off the part it's not allowed to read.  Because the
 
236
     * string is aligned, the masked-off tail is in the same word as the
 
237
     * rest of the string.  Every machine with memory protection I've seen
 
238
     * does it on word boundaries, so is OK with this.  But VALGRIND will
 
239
     * still catch it and complain.  The masking trick does make the hash
 
240
     * noticably faster for short strings (like English words).
 
241
     */
 
242
#ifndef VALGRIND
 
243
 
 
244
    switch(length)
 
245
    {
 
246
    case 12: c+=k[2]; b+=k[1]; a+=k[0]; break;
 
247
    case 11: c+=k[2]&0xffffff; b+=k[1]; a+=k[0]; break;
 
248
    case 10: c+=k[2]&0xffff; b+=k[1]; a+=k[0]; break;
 
249
    case 9 : c+=k[2]&0xff; b+=k[1]; a+=k[0]; break;
 
250
    case 8 : b+=k[1]; a+=k[0]; break;
 
251
    case 7 : b+=k[1]&0xffffff; a+=k[0]; break;
 
252
    case 6 : b+=k[1]&0xffff; a+=k[0]; break;
 
253
    case 5 : b+=k[1]&0xff; a+=k[0]; break;
 
254
    case 4 : a+=k[0]; break;
 
255
    case 3 : a+=k[0]&0xffffff; break;
 
256
    case 2 : a+=k[0]&0xffff; break;
 
257
    case 1 : a+=k[0]&0xff; break;
 
258
    case 0 : return c;              /* zero length strings require no mixing */
 
259
    }
 
260
 
 
261
#else /* make valgrind happy */
 
262
 
 
263
    k8 = (const uint8_t *)k;
 
264
    switch(length)
 
265
    {
 
266
    case 12: c+=k[2]; b+=k[1]; a+=k[0]; break;
 
267
    case 11: c+=((uint32_t)k8[10])<<16;  /* fall through */
 
268
    case 10: c+=((uint32_t)k8[9])<<8;    /* fall through */
 
269
    case 9 : c+=k8[8];                   /* fall through */
 
270
    case 8 : b+=k[1]; a+=k[0]; break;
 
271
    case 7 : b+=((uint32_t)k8[6])<<16;   /* fall through */
 
272
    case 6 : b+=((uint32_t)k8[5])<<8;    /* fall through */
 
273
    case 5 : b+=k8[4];                   /* fall through */
 
274
    case 4 : a+=k[0]; break;
 
275
    case 3 : a+=((uint32_t)k8[2])<<16;   /* fall through */
 
276
    case 2 : a+=((uint32_t)k8[1])<<8;    /* fall through */
 
277
    case 1 : a+=k8[0]; break;
 
278
    case 0 : return c;
 
279
    }
 
280
 
 
281
#endif /* !valgrind */
 
282
 
 
283
  } else if (HASH_LITTLE_ENDIAN && ((u.i & 0x1) == 0)) {
 
284
    const uint16_t *k = (const uint16_t *)key;         /* read 16-bit chunks */
 
285
    const uint8_t  *k8;
 
286
 
 
287
    /*--------------- all but last block: aligned reads and different mixing */
 
288
    while (length > 12)
 
289
    {
 
290
      a += k[0] + (((uint32_t)k[1])<<16);
 
291
      b += k[2] + (((uint32_t)k[3])<<16);
 
292
      c += k[4] + (((uint32_t)k[5])<<16);
 
293
      mix(a,b,c);
 
294
      length -= 12;
 
295
      k += 6;
 
296
    }
 
297
 
 
298
    /*----------------------------- handle the last (probably partial) block */
 
299
    k8 = (const uint8_t *)k;
 
300
    switch(length)
 
301
    {
 
302
    case 12: c+=k[4]+(((uint32_t)k[5])<<16);
 
303
             b+=k[2]+(((uint32_t)k[3])<<16);
 
304
             a+=k[0]+(((uint32_t)k[1])<<16);
 
305
             break;
 
306
    case 11: c+=((uint32_t)k8[10])<<16;     /* fall through */
 
307
    case 10: c+=k[4];
 
308
             b+=k[2]+(((uint32_t)k[3])<<16);
 
309
             a+=k[0]+(((uint32_t)k[1])<<16);
 
310
             break;
 
311
    case 9 : c+=k8[8];                      /* fall through */
 
312
    case 8 : b+=k[2]+(((uint32_t)k[3])<<16);
 
313
             a+=k[0]+(((uint32_t)k[1])<<16);
 
314
             break;
 
315
    case 7 : b+=((uint32_t)k8[6])<<16;      /* fall through */
 
316
    case 6 : b+=k[2];
 
317
             a+=k[0]+(((uint32_t)k[1])<<16);
 
318
             break;
 
319
    case 5 : b+=k8[4];                      /* fall through */
 
320
    case 4 : a+=k[0]+(((uint32_t)k[1])<<16);
 
321
             break;
 
322
    case 3 : a+=((uint32_t)k8[2])<<16;      /* fall through */
 
323
    case 2 : a+=k[0];
 
324
             break;
 
325
    case 1 : a+=k8[0];
 
326
             break;
 
327
    case 0 : return c;                     /* zero length requires no mixing */
 
328
    }
 
329
 
 
330
  } else {                        /* need to read the key one byte at a time */
 
331
    const uint8_t *k = (const uint8_t *)key;
 
332
 
 
333
    /*--------------- all but the last block: affect some 32 bits of (a,b,c) */
 
334
    while (length > 12)
 
335
    {
 
336
      a += k[0];
 
337
      a += ((uint32_t)k[1])<<8;
 
338
      a += ((uint32_t)k[2])<<16;
 
339
      a += ((uint32_t)k[3])<<24;
 
340
      b += k[4];
 
341
      b += ((uint32_t)k[5])<<8;
 
342
      b += ((uint32_t)k[6])<<16;
 
343
      b += ((uint32_t)k[7])<<24;
 
344
      c += k[8];
 
345
      c += ((uint32_t)k[9])<<8;
 
346
      c += ((uint32_t)k[10])<<16;
 
347
      c += ((uint32_t)k[11])<<24;
 
348
      mix(a,b,c);
 
349
      length -= 12;
 
350
      k += 12;
 
351
    }
 
352
 
 
353
    /*-------------------------------- last block: affect all 32 bits of (c) */
 
354
    switch(length)                   /* all the case statements fall through */
 
355
    {
 
356
    case 12: c+=((uint32_t)k[11])<<24;
 
357
    case 11: c+=((uint32_t)k[10])<<16;
 
358
    case 10: c+=((uint32_t)k[9])<<8;
 
359
    case 9 : c+=k[8];
 
360
    case 8 : b+=((uint32_t)k[7])<<24;
 
361
    case 7 : b+=((uint32_t)k[6])<<16;
 
362
    case 6 : b+=((uint32_t)k[5])<<8;
 
363
    case 5 : b+=k[4];
 
364
    case 4 : a+=((uint32_t)k[3])<<24;
 
365
    case 3 : a+=((uint32_t)k[2])<<16;
 
366
    case 2 : a+=((uint32_t)k[1])<<8;
 
367
    case 1 : a+=k[0];
 
368
             break;
 
369
    case 0 : return c;
 
370
    }
 
371
  }
 
372
 
 
373
  final(a,b,c);
 
374
  return c;
 
375
}
 
376
 
 
377
_PUBLIC_ unsigned int tdb_jenkins_hash(TDB_DATA *key)
 
378
{
 
379
        return hashlittle(key->dptr, key->dsize);
 
380
}