Head

GCC Code Coverage Report

Directory:	cvmfs/		Exec	Total	Coverage
File:	cvmfs/murmur.h	Lines:	19	50	38.0 %
Date:	2019-02-03 02:48:13	Branches:	3	16	18.8 %


//-----------------------------------------------------------------------------
// MurmurHash2 was written by Austin Appleby, and is placed in the public
// domain. The author hereby disclaims copyright to this source code.

// Note - This code makes a few assumptions about how your machine behaves -

// 1. We can read a 4-byte value from any address without crashing
// 2. sizeof(int) == 4

// And it has a few limitations -

// 1. It will not work incrementally.
// 2. It will not produce the same results on little-endian and big-endian
//    machines.

#ifndef CVMFS_MURMUR_H_
#define CVMFS_MURMUR_H_

#include <stdint.h>

#define BIG_CONSTANT(x) (x##LLU)

inline uint32_t MurmurHash2 ( const void * key, int len, uint32_t seed )
{
  // 'm' and 'r' are mixing constants generated offline.
  // They're not really 'magic', they just happen to work well.

  const uint32_t m = 0x5bd1e995;
  const int r = 24;

  // Initialize the hash to a 'random' value

  uint32_t h = seed ^ len;

  // Mix 4 bytes at a time into the hash

  const unsigned char * data = (const unsigned char *)key;

  while(len >= 4)
  {
    uint32_t k = *(uint32_t*)data;

    k *= m;
    k ^= k >> r;
    k *= m;

    h *= m;
    h ^= k;

    data += 4;
    len -= 4;
  }

  // Handle the last few bytes of the input array

  switch(len)
  {
  case 3: h ^= data[2] << 16;
  case 2: h ^= data[1] << 8;
  case 1: h ^= data[0];
      h *= m;
  };

  // Do a few final mixes of the hash to ensure the last few
  // bytes are well-incorporated.

  h ^= h >> 13;
  h *= m;
  h ^= h >> 15;

  return h;
}


//-----------------------------------------------------------------------------
// MurmurHash2, 64-bit versions, by Austin Appleby

// The same caveats as 32-bit MurmurHash2 apply here - beware of alignment
// and endian-ness issues if used across multiple platforms.

// 64-bit hash for 64-bit platforms

inline uint64_t MurmurHash64A ( const void * key, int len, uint64_t seed )
{
  const uint64_t m = BIG_CONSTANT(0xc6a4a7935bd1e995);
  const int r = 47;

  uint64_t h = seed ^ (len * m);

  const uint64_t * data = (const uint64_t *)key;
  const uint64_t * end = data + (len/8);

  while(data != end)
  {
    uint64_t k = *data++;

    k *= m;
    k ^= k >> r;
    k *= m;

    h ^= k;
    h *= m;
  }

  const unsigned char * data2 = (const unsigned char*)data;

  switch(len & 7)
  {
    case 7: h ^= uint64_t(data2[6]) << 48;
    case 6: h ^= uint64_t(data2[5]) << 40;
    case 5: h ^= uint64_t(data2[4]) << 32;
    case 4: h ^= uint64_t(data2[3]) << 24;
    case 3: h ^= uint64_t(data2[2]) << 16;
    case 2: h ^= uint64_t(data2[1]) << 8;
    case 1: h ^= uint64_t(data2[0]);
      h *= m;
  };

  h ^= h >> r;
  h *= m;
  h ^= h >> r;

  return h;
}

#endif  // CVMFS_MURMUR_H_


Generated by: GCOVR (Version 4.1)

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_MURMUR_H_
17			#define CVMFS_MURMUR_H_
18
19			#include <stdint.h>
20
21			#define BIG_CONSTANT(x) (x##LLU)
22
23		165438363	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		165438363	const uint32_t m = 0x5bd1e995;
29		165438363	const int r = 24;
30
31			// Initialize the hash to a 'random' value
32
33		165438363	uint32_t h = seed ^ len;
34
35			// Mix 4 bytes at a time into the hash
36
37		165438363	const unsigned char * data = (const unsigned char *)key;
38
39	✓✓	599591026	while(len >= 4)
40			{
41		268714300	uint32_t k = (uint32_t)data;
42
43		268714300	k *= m;
44		268714300	k ^= k >> r;
45		268714300	k *= m;
46
47		268714300	h *= m;
48		268714300	h ^= k;
49
50		268714300	data += 4;
51		268714300	len -= 4;
52			}
53
54			// Handle the last few bytes of the input array
55
56	✗✗✗✓	165438363	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		165438363	h ^= h >> 13;
68		165438363	h *= m;
69		165438363	h ^= h >> 15;
70
71		165438363	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_MURMUR_H_