MOM_murmur_hash.F90

1! This file is part of MOM6, the Modular Ocean Model version 6.

2! See the LICENSE file for licensing information.

3! SPDX-License-Identifier: Apache-2.0

4

5!> MurmurHash is a non-cryptographic hash function developed by Austin Appleby.

6!!

7!! This module provides an implementation of the 32-bit MurmurHash3 algorithm.

8!! It is used in MOM6 to generate unique hashes of field arrays. The hash is

9!! sensitive to order of elements and can detect changes that would otherwise

10!! be missed by the mean/min/max/bitcount tests.

11!!

12!! Sensitivity to order means that it must be used with care for tests such as

13!! processor layout.

14!!

15!! This implementation assumes data sizes of either 32 or 64 bits. It cannot

16!! be used for smaller types such as strings.

17!!

18!! https://github.com/aappleby/smhasher

19module mom_murmur_hash

20

21use, intrinsic :: iso_fortran_env, only : int32, int64, real32, real64

22

23implicit none ; private

24

25public :: murmur_hash

26

27!> Return the murmur3 hash of an array.

28interface murmur_hash

29 procedure murmurhash3_i32

30 procedure murmurhash3_i64

31 procedure murmurhash3_r32

32 procedure murmurhash3_r32_1d

33 procedure murmurhash3_r32_2d

34 procedure murmurhash3_r32_3d

35 procedure murmurhash3_r32_4d

36 procedure murmurhash3_r64

37 procedure murmurhash3_r64_1d

38 procedure murmurhash3_r64_2d

39 procedure murmurhash3_r64_3d

40 procedure murmurhash3_r64_4d

41end interface murmur_hash

42

43contains

44

45!> Return the murmur3 hash for a 32-bit integer array.

46function murmurhash3_i32(key, seed) result(hash)

47 integer(int32), intent(in) :: key(:)

48 !< Input array

49 integer(int32), intent(in), optional :: seed

50 !< Hash seed

51 integer(int32) :: hash

52 !< Murmur hash of array

53

54 integer(int32), parameter :: c1 = int(z'cc9e2d51', kind=int32)

55 integer(int32), parameter :: c2 = int(z'1b873593', kind=int32)

56 integer(int32), parameter :: c3 = int(z'e6546b64', kind=int32)

57

58 integer(int32), parameter :: c4 = int(z'85ebca6b', kind=int32)

59 integer(int32), parameter :: c5 = int(z'c2b2ae35', kind=int32)

60

61 integer :: i

62 integer(int32) :: k

63

64 hash = 0

65 if (present(seed)) hash = seed

66

67 do i = 1, size(key)

68 k = key(i)

69 k = k * c1

70 k = ishftc(k, 15)

71 k = k * c2

72

73 hash = ieor(hash, k)

74 hash = ishftc(hash, 13)

75 hash = 5 * hash + c3

76 enddo

77

78 ! NOTE: This is the point where the algorithm would handle trailing bytes.

79 ! Since our arrays are comprised of 4 or 8 byte elements, we skip this part.

80

81 hash = ieor(hash, 4*size(key))

82

83 hash = ieor(hash, ishft(hash, -16))

84 hash = hash * c4

85 hash = ieor(hash, ishft(hash, -13))

86 hash = hash * c5

87 hash = ieor(hash, ishft(hash, -16))

88end function murmurhash3_i32

89

90

91!> Return the murmur3 hash for a 64-bit integer array.

92function murmurhash3_i64(key, seed) result(hash)

93 integer(int64), intent(in) :: key(:)

94 !< Input array

95 integer(int32), intent(in), optional :: seed

96 !< Hash seed

97 integer(int32) :: hash

98 !< Murmur hash of array

99

100 integer(int32) :: ikey(2*size(key))

101

102 hash = murmur_hash(transfer(key, ikey), seed=seed)

103end function murmurhash3_i64

104

105

106!> Return the murmur3 hash for a 32-bit real array.

107function murmurhash3_r32(key, seed) result(hash)

108 real(real32), intent(in) :: key

109 !< Input array [arbitrary]

110 integer(int32), intent(in), optional :: seed

111 !< Hash seed

112 integer(int32) :: hash

113 !< Murmur hash of array

114

115 integer(int32) :: ikey(1)

116

117 hash = murmur_hash(transfer(key, ikey), seed=seed)

118end function murmurhash3_r32

119

120

121!> Return the murmur3 hash for a 32-bit real array.

122function murmurhash3_r32_1d(key, seed) result(hash)

123 real(real32), intent(in) :: key(:)

124 !< Input array [arbitrary]

125 integer(int32), intent(in), optional :: seed

126 !< Hash seed

127 integer(int32) :: hash

128 !< Murmur hash of array

129

130 integer(int32) :: ikey(size(key))

131

132 hash = murmur_hash(transfer(key, ikey), seed=seed)

133end function murmurhash3_r32_1d

134

135

136!> Return the murmur3 hash for a 32-bit real 2D array.

137function murmurhash3_r32_2d(key, seed) result(hash)

138 real(real32), intent(in) :: key(:,:)

139 !< Input array [arbitrary]

140 integer(int32), intent(in), optional :: seed

141 !< Hash seed

142 integer(int32) :: hash

143 !< Murmur hash of array

144

145 integer(int32) :: ikey(size(key))

146

147 hash = murmur_hash(transfer(key, ikey), seed=seed)

148end function murmurhash3_r32_2d

149

150

151!> Return the murmur3 hash for a 32-bit real 3D array.

152function murmurhash3_r32_3d(key, seed) result(hash)

153 real(real32), intent(in) :: key(:,:,:)

154 !< Input array [arbitrary]

155 integer(int32), intent(in), optional :: seed

156 !< Hash seed

157 integer(int32) :: hash

158 !< Murmur hash of array

159

160 integer(int32) :: ikey(size(key))

161

162 hash = murmur_hash(transfer(key, ikey), seed=seed)

163end function murmurhash3_r32_3d

164

165

166!> Return the murmur3 hash for a 32-bit real 4D array.

167function murmurhash3_r32_4d(key, seed) result(hash)

168 real(real32), intent(in) :: key(:,:,:,:)

169 !< Input array [arbitrary]

170 integer(int32), intent(in), optional :: seed

171 !< Hash seed

172 integer(int32) :: hash

173 !< Murmur hash of array

174

175 integer(int32) :: ikey(size(key))

176

177 hash = murmur_hash(transfer(key, ikey), seed=seed)

178end function murmurhash3_r32_4d

179

180

181!> Return the murmur3 hash for a 64-bit real array.

182function murmurhash3_r64(key, seed) result(hash)

183 real(real64), intent(in) :: key

184 !< Input array [arbitrary]

185 integer(int32), intent(in), optional :: seed

186 !< Hash seed

187 integer(int32) :: hash

188 !< Murmur hash of array

189

190 integer(int32) :: ikey(2)

191

192 hash = murmur_hash(transfer(key, ikey), seed=seed)

193end function murmurhash3_r64

194

195

196!> Return the murmur3 hash for a 64-bit real array.

197function murmurhash3_r64_1d(key, seed) result(hash)

198 real(real64), intent(in) :: key(:)

199 !< Input array [arbitrary]

200 integer(int32), intent(in), optional :: seed

201 !< Hash seed

202 integer(int32) :: hash

203 !< Murmur hash of array

204

205 integer(int32) :: ikey(2*size(key))

206

207 hash = murmur_hash(transfer(key, ikey), seed=seed)

208end function murmurhash3_r64_1d

209

210

211!> Return the murmur3 hash for a 64-bit real 2D array.

212function murmurhash3_r64_2d(key, seed) result(hash)

213 real(real64), intent(in) :: key(:,:)

214 !< Input array [arbitrary]

215 integer(int32), intent(in), optional :: seed

216 !< Hash seed

217 integer(int32) :: hash

218 !< Murmur hash of array

219

220 integer(int32) :: ikey(2*size(key))

221

222 hash = murmur_hash(transfer(key, ikey), seed=seed)

223end function murmurhash3_r64_2d

224

225

226!> Return the murmur3 hash for a 64-bit real 3D array.

227function murmurhash3_r64_3d(key, seed) result(hash)

228 real(real64), intent(in) :: key(:,:,:)

229 !< Input array [arbitrary]

230 integer(int32), intent(in), optional :: seed

231 !< Hash seed

232 integer(int32) :: hash

233 !< Murmur hash of array

234

235 integer(int32) :: ikey(2*size(key))

236

237 hash = murmur_hash(transfer(key, ikey), seed=seed)

238end function murmurhash3_r64_3d

239

240

241!> Return the murmur3 hash for a 64-bit real 4D array.

242function murmurhash3_r64_4d(key, seed) result(hash)

243 real(real64), intent(in) :: key(:,:,:,:)

244 !< Input array [arbitrary]

245 integer(int32), intent(in), optional :: seed

246 !< Hash seed

247 integer(int32) :: hash

248 !< Murmur hash of array

249

250 integer(int32) :: ikey(2*size(key))

251

252 hash = murmur_hash(transfer(key, ikey), seed=seed)

253end function murmurhash3_r64_4d

254

255end module mom_murmur_hash