Book a Demo!
CoCalc Logo Icon
StoreFeaturesDocsShareSupportNewsAboutPoliciesSign UpSign In
awilliam
GitHub Repository: awilliam/linux-vfio
 Path: blob/master/net/ceph/crush/hash.c
37212 views
1


2
#include <linux/types.h>

3
#include <linux/crush/hash.h>

4


5
/*

6
 * Robert Jenkins' function for mixing 32-bit values

7
 * http://burtleburtle.net/bob/hash/evahash.html

8
 * a, b = random bits, c = input and output

9
 */

10
#define crush_hashmix(a, b, c) do {			\

11
		a = a-b;  a = a-c;  a = a^(c>>13);	\

12
		b = b-c;  b = b-a;  b = b^(a<<8);	\

13
		c = c-a;  c = c-b;  c = c^(b>>13);	\

14
		a = a-b;  a = a-c;  a = a^(c>>12);	\

15
		b = b-c;  b = b-a;  b = b^(a<<16);	\

16
		c = c-a;  c = c-b;  c = c^(b>>5);	\

17
		a = a-b;  a = a-c;  a = a^(c>>3);	\

18
		b = b-c;  b = b-a;  b = b^(a<<10);	\

19
		c = c-a;  c = c-b;  c = c^(b>>15);	\

20
	} while (0)

21


22
#define crush_hash_seed 1315423911

23


24
static __u32 crush_hash32_rjenkins1(__u32 a)

25
{

26
	__u32 hash = crush_hash_seed ^ a;

27
	__u32 b = a;

28
	__u32 x = 231232;

29
	__u32 y = 1232;

30
	crush_hashmix(b, x, hash);

31
	crush_hashmix(y, a, hash);

32
	return hash;

33
}

34


35
static __u32 crush_hash32_rjenkins1_2(__u32 a, __u32 b)

36
{

37
	__u32 hash = crush_hash_seed ^ a ^ b;

38
	__u32 x = 231232;

39
	__u32 y = 1232;

40
	crush_hashmix(a, b, hash);

41
	crush_hashmix(x, a, hash);

42
	crush_hashmix(b, y, hash);

43
	return hash;

44
}

45


46
static __u32 crush_hash32_rjenkins1_3(__u32 a, __u32 b, __u32 c)

47
{

48
	__u32 hash = crush_hash_seed ^ a ^ b ^ c;

49
	__u32 x = 231232;

50
	__u32 y = 1232;

51
	crush_hashmix(a, b, hash);

52
	crush_hashmix(c, x, hash);

53
	crush_hashmix(y, a, hash);

54
	crush_hashmix(b, x, hash);

55
	crush_hashmix(y, c, hash);

56
	return hash;

57
}

58


59
static __u32 crush_hash32_rjenkins1_4(__u32 a, __u32 b, __u32 c, __u32 d)

60
{

61
	__u32 hash = crush_hash_seed ^ a ^ b ^ c ^ d;

62
	__u32 x = 231232;

63
	__u32 y = 1232;

64
	crush_hashmix(a, b, hash);

65
	crush_hashmix(c, d, hash);

66
	crush_hashmix(a, x, hash);

67
	crush_hashmix(y, b, hash);

68
	crush_hashmix(c, x, hash);

69
	crush_hashmix(y, d, hash);

70
	return hash;

71
}

72


73
static __u32 crush_hash32_rjenkins1_5(__u32 a, __u32 b, __u32 c, __u32 d,

74
				      __u32 e)

75
{

76
	__u32 hash = crush_hash_seed ^ a ^ b ^ c ^ d ^ e;

77
	__u32 x = 231232;

78
	__u32 y = 1232;

79
	crush_hashmix(a, b, hash);

80
	crush_hashmix(c, d, hash);

81
	crush_hashmix(e, x, hash);

82
	crush_hashmix(y, a, hash);

83
	crush_hashmix(b, x, hash);

84
	crush_hashmix(y, c, hash);

85
	crush_hashmix(d, x, hash);

86
	crush_hashmix(y, e, hash);

87
	return hash;

88
}

89


90


91
__u32 crush_hash32(int type, __u32 a)

92
{

93
	switch (type) {

94
	case CRUSH_HASH_RJENKINS1:

95
		return crush_hash32_rjenkins1(a);

96
	default:

97
		return 0;

98
	}

99
}

100


101
__u32 crush_hash32_2(int type, __u32 a, __u32 b)

102
{

103
	switch (type) {

104
	case CRUSH_HASH_RJENKINS1:

105
		return crush_hash32_rjenkins1_2(a, b);

106
	default:

107
		return 0;

108
	}

109
}

110


111
__u32 crush_hash32_3(int type, __u32 a, __u32 b, __u32 c)

112
{

113
	switch (type) {

114
	case CRUSH_HASH_RJENKINS1:

115
		return crush_hash32_rjenkins1_3(a, b, c);

116
	default:

117
		return 0;

118
	}

119
}

120


121
__u32 crush_hash32_4(int type, __u32 a, __u32 b, __u32 c, __u32 d)

122
{

123
	switch (type) {

124
	case CRUSH_HASH_RJENKINS1:

125
		return crush_hash32_rjenkins1_4(a, b, c, d);

126
	default:

127
		return 0;

128
	}

129
}

130


131
__u32 crush_hash32_5(int type, __u32 a, __u32 b, __u32 c, __u32 d, __u32 e)

132
{

133
	switch (type) {

134
	case CRUSH_HASH_RJENKINS1:

135
		return crush_hash32_rjenkins1_5(a, b, c, d, e);

136
	default:

137
		return 0;

138
	}

139
}

140


141
const char *crush_hash_name(int type)

142
{

143
	switch (type) {

144
	case CRUSH_HASH_RJENKINS1:

145
		return "rjenkins1";

146
	default:

147
		return "unknown";

148
	}

149
}

150


151