GCC Code Coverage Report

Directory: cvmfs/
File: cvmfs/util/murmur.hxx
Date: 2024-04-21 02:33:16
Exec Total Coverage
Lines: 19 50 38.0%
Branches: 3 16 18.8%
Line Branch Exec Source
1 //-----------------------------------------------------------------------------
2 // MurmurHash2 was written by Austin Appleby, and is placed in the public
3 // domain. The author hereby disclaims copyright to this source code.
4
5 // Note - This code makes a few assumptions about how your machine behaves -
6
7 // 1. We can read a 4-byte value from any address without crashing
8 // 2. sizeof(int) == 4
9
10 // And it has a few limitations -
11
12 // 1. It will not work incrementally.
13 // 2. It will not produce the same results on little-endian and big-endian
14 // machines.
15
16 #ifndef CVMFS_UTIL_MURMUR_H_
17 #define CVMFS_UTIL_MURMUR_H_
18
19 #include <stdint.h>
20
21 #define BIG_CONSTANT(x) (x##LLU)
22
23 47536060 inline uint32_t MurmurHash2 ( const void * key, int len, uint32_t seed )
24 {
25 // 'm' and 'r' are mixing constants generated offline.
26 // They're not really 'magic', they just happen to work well.
27
28 47536060 const uint32_t m = 0x5bd1e995;
29 47536060 const int r = 24;
30
31 // Initialize the hash to a 'random' value
32
33 47536060 uint32_t h = seed ^ len;
34
35 // Mix 4 bytes at a time into the hash
36
37 47536060 const unsigned char * data = (const unsigned char *)key;
38
39
2/2
✓ Branch 0 taken 153306420 times.
✓ Branch 1 taken 47536060 times.
 200842480 while(len >= 4)
40 {
41 153306420 uint32_t k = *(uint32_t*)data;
42
43 153306420 k *= m;
44 153306420 k ^= k >> r;
45 153306420 k *= m;
46
47 153306420 h *= m;
48 153306420 h ^= k;
49
50 153306420 data += 4;
51 153306420 len -= 4;
52 }
53
54 // Handle the last few bytes of the input array
55
56
1/4
✗ Branch 0 not taken.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✓ Branch 3 taken 47536060 times.
 47536060 switch(len)
57 {
58 ✗ case 3: h ^= data[2] << 16;
59 ✗ case 2: h ^= data[1] << 8;
60 ✗ case 1: h ^= data[0];
61 ✗ h *= m;
62 };
63
64 // Do a few final mixes of the hash to ensure the last few
65 // bytes are well-incorporated.
66
67 47536060 h ^= h >> 13;
68 47536060 h *= m;
69 47536060 h ^= h >> 15;
70
71 47536060 return h;
72 }
73
74
75 //-----------------------------------------------------------------------------
76 // MurmurHash2, 64-bit versions, by Austin Appleby
77
78 // The same caveats as 32-bit MurmurHash2 apply here - beware of alignment
79 // and endian-ness issues if used across multiple platforms.
80
81 // 64-bit hash for 64-bit platforms
82
83 ✗ inline uint64_t MurmurHash64A ( const void * key, int len, uint64_t seed )
84 {
85 ✗ const uint64_t m = BIG_CONSTANT(0xc6a4a7935bd1e995);
86 ✗ const int r = 47;
87
88 ✗ uint64_t h = seed ^ (len * m);
89
90 ✗ const uint64_t * data = (const uint64_t *)key;
91 ✗ const uint64_t * end = data + (len/8);
92
93 ✗ while(data != end)
94 {
95 ✗ uint64_t k = *data++;
96
97 ✗ k *= m;
98 ✗ k ^= k >> r;
99 ✗ k *= m;
100
101 ✗ h ^= k;
102 ✗ h *= m;
103 }
104
105 ✗ const unsigned char * data2 = (const unsigned char*)data;
106
107 ✗ switch(len & 7)
108 {
109 ✗ case 7: h ^= uint64_t(data2[6]) << 48;
110 ✗ case 6: h ^= uint64_t(data2[5]) << 40;
111 ✗ case 5: h ^= uint64_t(data2[4]) << 32;
112 ✗ case 4: h ^= uint64_t(data2[3]) << 24;
113 ✗ case 3: h ^= uint64_t(data2[2]) << 16;
114 ✗ case 2: h ^= uint64_t(data2[1]) << 8;
115 ✗ case 1: h ^= uint64_t(data2[0]);
116 ✗ h *= m;
117 };
118
119 ✗ h ^= h >> r;
120 ✗ h *= m;
121 ✗ h ^= h >> r;
122
123 ✗ return h;
124 }
125
126 #endif // CVMFS_UTIL_MURMUR_H_
127