docs/reference/library/2e.umd · urbit.org

git.iko.soy/urbit.org

on 7fa97bd help sign in

urbit.org/docs/reference/library/2e.umd

265 lines 5.3 kB history raw

1---

2navhome: /docs/

3---

6# 2e: insecure hashing

7### `++fnv`

9FNV scrambler

11Hashes an atom with the 32-bit FNV non-cryptographic hash algorithm. Multiplies

12`a` by the prime number 16,777,619 and then takes the [block](../2c.md) of size

135 off the product's end, producing an atom.

15#### Accepts

17`a` is an atom.

19#### Produces

21An atom.

23#### Source

25 ++ fnv |=(a=@ (end 5 1 (mul 16.777.619 a)))

27#### Examples

29 > (fnv 10.000)

30 272.465.456

32 > (fnv 10.001)

33 289.243.075

35 > (fnv 1)

36 16.777.619

40***

41### `++mug`

43FNV-1a scrambler

45Hashes `a` with the 31-bit nonzero FNV-1a non-cryptographic hash algorithm,

46producing an atom.

48#### Accepts

50`a` is a noun.

52#### Produces

54An atom.

56#### Source

58 ++ mug

59 ~/ %mug

60 |= a=*

61 ?^ a

62 =+ b=[p=$(a -.a) q=$(a +.a)]

63 |- ^- @

64 =+ c=(fnv (mix p.b (fnv q.b)))

65 =+ d=(mix (rsh 0 31 c) (end 0 31 c))

66 ?. =(0 d) d

67 $(q.b +(q.b))

68 =+ b=2.166.136.261

69 |- ^- @

70 =+ c=b

71 =+ [d=0 e=(met 3 a)]

72 |- ^- @

73 ?: =(d e)

74 =+ f=(mix (rsh 0 31 c) (end 0 31 c))

75 ?. =(0 f) f

76 ^$(b +(b))

77 $(c (fnv (mix c (cut 3 [d 1] a))), d +(d))

80#### Examples

82 > (mug 10.000)

83 178.152.889

85 > (mug 10.001)

86 714.838.017

88 > (mug 1)

89 67.918.732

91 > (mug (some 10))

92 1.872.403.737

94 > (mug [1 2 3 4 5 ~])

95 1.067.931.605

99***

100### `++muk`

101

102Standard MurmurHash3

103

104Implementation of the 32-bit

105[MurmurHash3](https://en.wikipedia.org/wiki/MurmurHash#Algorithm)

106non-cryptographic hash algorithm. Takes `a` as the seed, `b` as the key length

107in [blocks](../2c) of size 3, and `c` as the key, producing an atom.

109#### Accepts

111`a` is an atom.

113`b` is an atom.

115`c` is an atom.

117#### Produces

119An atom.

121#### Source

122 ++ muk

123 ~% %muk ..muk ~

124 =+ ~(. fe 5)

125 |= [syd=@ len=@ key=@]

126 ?> &((lte (met 5 syd) 1) (lte (met 0 len) 31))

127 =/ pad (sub len (met 3 key))

128 =/ data (weld (rip 3 key) (reap pad 0))

129 =/ nblocks (div len 4) :: intentionally off-by-one

130 =/ h1 syd

131 =+ [c1=0xcc9e.2d51 c2=0x1b87.3593]

132 =/ blocks (rip 5 key)

133 =/ i nblocks

134 =. h1 =/ hi h1 |-

135 ?: =(0 i) hi :: negative array index

136 =/ k1 (snag (sub nblocks i) blocks)

137 =. k1 (sit (mul k1 c1))

138 =. k1 (rol 0 15 k1)

139 =. k1 (sit (mul k1 c2))

140 =. hi (mix hi k1)

141 =. hi (rol 0 13 hi)

142 =. hi (sum (sit (mul hi 5)) 0xe654.6b64)

143 $(i (dec i))

144 =/ tail (slag (mul 4 nblocks) data)

145 =/ k1 0

146 =/ tlen (dis len 3)

147 =. h1

148 ?+ tlen h1 :: fallthrough switch

149 $3 =. k1 (mix k1 (lsh 0 16 (snag 2 tail)))

150 =. k1 (mix k1 (lsh 0 8 (snag 1 tail)))

151 =. k1 (mix k1 (snag 0 tail))

152 =. k1 (sit (mul k1 c1))

153 =. k1 (rol 0 15 k1)

154 =. k1 (sit (mul k1 c2))

155 (mix h1 k1)

156 $2 =. k1 (mix k1 (lsh 0 8 (snag 1 tail)))

157 =. k1 (mix k1 (snag 0 tail))

158 =. k1 (sit (mul k1 c1))

159 =. k1 (rol 0 15 k1)

160 =. k1 (sit (mul k1 c2))

161 (mix h1 k1)

162 $1 =. k1 (mix k1 (snag 0 tail))

163 =. k1 (sit (mul k1 c1))

164 =. k1 (rol 0 15 k1)

165 =. k1 (sit (mul k1 c2))

166 (mix h1 k1)

167 ==

168 =. h1 (mix h1 len)

169 |^ (fmix32 h1)

170 ++ fmix32

171 |= h=@

172 =. h (mix h (rsh 0 16 h))

173 =. h (sit (mul h 0x85eb.ca6b))

174 =. h (mix h (rsh 0 13 h))

175 =. h (sit (mul h 0xc2b2.ae35))

176 =. h (mix h (rsh 0 16 h))

177 h

178 --

179

180

181#### Examples

182

183 > (muk 6 1 3)

184 3.427.677.118

185

186 > (muk 6 2 'jerry')

187 ! exit

188

189 > (muk 6 2 'je')

190 3.602.081.716

191

192 > (met 3 'jerry')

193 5

194

195 > (met 3 'je')

196 2

197

198 > (muk 6 5 'jerry')

199 1.276.447.489

200

201 > (muk 6 15 'jerry')

202 2.881.503.571

203

204 > =e (cut 3 [0 2] eny) :: `eny` is 512 bits of entropy (a random number).

205 > e

206 44.228

207

208 > (muk e 11 10.000)

209 246.077.549

210

211

212

213***

214### `++mum`

215

21631-bit MurmurHash3 scrambler

217

218Hashes `a` with the 31-bit MurmurHash3 non-cryptographic hash algorithm,

219producing an atom.

221#### Accepts

223`a` is a noun.

225#### Produces

227An atom.

229#### Source

231 ++ mum

232 ~/ %mum

233 |= a=*

234 |^ (trim ?@(a a (mix $(a -.a) (mix 0x7fff.ffff $(a +.a)))))

235 ++ trim

236 |= key=@

237 =+ syd=0xcafe.babe

238 |- ^- @

239 =+ haz=(muk syd (met 3 key) key)

240 =+ ham=(mix (rsh 0 31 haz) (end 0 31 haz))

241 ?.(=(0 ham) ham $(syd +(syd)))

242

243#### Examples

244

245 > (mum 10.000)

246 795.713.195

247

248 > (mum 10.001)

249 420.521.697

250

251 > (mum 'jerry')

252 1.540.161.753

253

254 > (mum 1)

255 1.901.865.568

256

257 > (mum (some 10))

258 2.099.076.946

259

260 > (mum [1 2 3 4 5 ~])

261 1.719.833.228

262

263

264

265***