← Back to branch summary

~paul-lucas/zorba/bug-932374

« back to all changes in this revision

Viewing changes to src/util/hash/hash.cpp

  • Committer: Paul J. Lucas
  • Date: 2012-09-21 20:26:47 UTC
  • mfrom: (10819.2.235 zorba)
  • Revision ID: paul@lucasmail.org-20120921202647-fy9n4jduhrnljrnb
Merge from trunk.

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/util/hash/hash.cpp
 
1
/*
 
2
 * Copyright 2006-2008 The FLWOR Foundation.
 
3
 * 
 
4
 * Licensed under the Apache License, Version 2.0 (the "License");
 
5
 * you may not use this file except in compliance with the License.
 
6
 * You may obtain a copy of the License at
 
7
 * 
 
8
 * http://www.apache.org/licenses/LICENSE-2.0
 
9
 * 
 
10
 * Unless required by applicable law or agreed to in writing, software
 
11
 * distributed under the License is distributed on an "AS IS" BASIS,
 
12
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 
13
 * See the License for the specific language governing permissions and
 
14
 * limitations under the License.
 
15
 */
 
16
 
 
17
// standard
 
18
#include <limits>
 
19
 
 
20
// local
 
21
#include "hash.h"
 
22
 
 
23
using namespace std;
 
24
 
 
25
namespace zorba {
 
26
namespace ztd {
 
27
 
 
28
///////////////////////////////////////////////////////////////////////////////
 
29
 
 
30
size_t hash_bytes( void const *p, size_t len, size_t result ) {
 
31
  unsigned char const *c = reinterpret_cast<unsigned char const*>( p );
 
32
  unsigned char const *const end = c + len;
 
33
#ifdef ZORBA_HASH_FN_FNV_1a
 
34
  //
 
35
  // FNV-1a (Fowler/Noll/Vo) hashing algorithm.
 
36
  //
 
37
  while ( c < end ) {
 
38
    result *= Hash_Prime;
 
39
    result ^= *c++;
 
40
  }
 
41
#endif /* ZORBA_HASH_FN_FNV_1a */
 
42
#ifdef ZORBA_HASH_FN_PJW
 
43
  //
 
44
  // An adaptation of Peter J. Weinberger's (PJW) generic hashing algorithm
 
45
  // based on Allen Holub's version.  This version works for any hash code
 
46
  // size (in this case, size_t) and not only 'unsigned' as in PJW's version.
 
47
  //
 
48
  // The original PJW algorithm can be found in:
 
49
  //
 
50
  //    Fig. 7.35: Hash function hashpjw, written in C
 
51
  //    "Compilers: Principles, Techniques, and Tools," Section 7.6: "Symbol
 
52
  //    Tables," Alfred Aho, Ravi Sethi, and Jeffrey D. Ullman, Addison-Wesley,
 
53
  //    Reading, MA, 1986, pp. 435-436.
 
54
  //
 
55
  static size_t const BitsInSizeT   = sizeof( size_t ) *
 
56
                                      numeric_limits<unsigned char>::digits;
 
57
  static size_t const ThreeFourths  = BitsInSizeT * 3 / 4;
 
58
  static size_t const OneEighth     = BitsInSizeT / 8;
 
59
  static size_t const HighBits      = ~( (size_t)(~0ul) >> OneEighth );
 
60
 
 
61
  while ( c < end ) {
 
62
    result = (result << OneEighth) + *c++;
 
63
    if ( size_t temp = result & HighBits )
 
64
      result = (result ^ (temp >> ThreeFourths)) & ~HighBits;
 
65
  }
 
66
#endif /* ZORBA_HASH_FN_PJW */
 
67
  return result;
 
68
}
 
69
 
 
70
///////////////////////////////////////////////////////////////////////////////
 
71
 
 
72
} // namespace ztd
 
73
} // namespace zorba
 
74
 
 
75
/* vim:set et ts=2 sw=2: */