reference/library/2e.md · urbit.org

git.iko.soy/urbit.org

on 159efe7 help sign in

urbit.org/reference/library/2e.md

275 lines 5.2 kB history raw

1+++

2title = "2e: Insecure Hashing"

3weight = 8

4template = "doc.html"

5+++

6### `++fnv`

8FNV scrambler

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

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

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

14#### Accepts

16`a` is an atom.

18#### Produces

20An atom.

22#### Source

24```

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

26```

28#### Examples

30```

31 > (fnv 10.000)

32 272.465.456

34 > (fnv 10.001)

35 289.243.075

37 > (fnv 1)

38 16.777.619

39```

42---

43### `++mug`

45FNV-1a scrambler

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

48producing an atom.

50#### Accepts

52`a` is a noun.

54#### Produces

56An atom.

58#### Source

60```

61 ++ mug

62 ~/ %mug

63 |= a=*

64 ?^ a

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

66 |- ^- @

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

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

69 ?. =(0 d) d

70 $(q.b +(q.b))

71 =+ b=2.166.136.261

72 |- ^- @

73 =+ c=b

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

75 |- ^- @

76 ?: =(d e)

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

78 ?. =(0 f) f

79 ^$(b +(b))

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

81```

83#### Examples

85```

86 > (mug 10.000)

87 178.152.889

89 > (mug 10.001)

90 714.838.017

92 > (mug 1)

93 67.918.732

95 > (mug (some 10))

96 1.872.403.737

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

99 1.067.931.605

100```

101

102

103---

104### `++muk`

105

106Standard MurmurHash3

107

108Implementation of the 32-bit

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

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

111in [blocks](./docs/reference/library/2c.md) of size 3, and `c` as the key, producing an atom.

113#### Accepts

115`a` is an atom.

117`b` is an atom.

119`c` is an atom.

121#### Produces

123An atom.

125#### Source

127```

128 ++ muk

129 ~% %muk ..muk ~

130 =+ ~(. fe 5)

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

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

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

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

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

136 =/ h1 syd

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

138 =/ blocks (rip 5 key)

139 =/ i nblocks

140 =. h1 =/ hi h1 |-

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

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

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

144 =. k1 (rol 0 15 k1)

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

146 =. hi (mix hi k1)

147 =. hi (rol 0 13 hi)

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

149 $(i (dec i))

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

151 =/ k1 0

152 =/ tlen (dis len 3)

153 =. h1

154 ?+ tlen h1 :: fallthrough switch

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

156 =. 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 $2 =. k1 (mix k1 (lsh 0 8 (snag 1 tail)))

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

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

165 =. k1 (rol 0 15 k1)

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

167 (mix h1 k1)

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

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

170 =. k1 (rol 0 15 k1)

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

172 (mix h1 k1)

173 ==

174 =. h1 (mix h1 len)

175 |^ (fmix32 h1)

176 ++ fmix32

177 |= h=@

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

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

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

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

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

183 h

184 --

185```

186

187#### Examples

188

189```

190 > (muk 6 1 3)

191 3.427.677.118

192

193 > (muk 6 2 'jerry')

194 ! exit

195

196 > (muk 6 2 'je')

197 3.602.081.716

198

199 > (met 3 'jerry')

200 5

201

202 > (met 3 'je')

203 2

204

205 > (muk 6 5 'jerry')

206 1.276.447.489

207

208 > (muk 6 15 'jerry')

209 2.881.503.571

210

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

212 > e

213 44.228

214

215 > (muk e 11 10.000)

216 246.077.549

217```

218

219

220---

221### `++mum`

222

22331-bit MurmurHash3 scrambler

224

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

226producing an atom.

228#### Accepts

230`a` is a noun.

232#### Produces

234An atom.

236#### Source

238```

239 ++ mum

240 ~/ %mum

241 |= a=*

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

243 ++ trim

244 |= key=@

245 =+ syd=0xcafe.babe

246 |- ^- @

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

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

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

250```

251

252#### Examples

253

254```

255 > (mum 10.000)

256 795.713.195

257

258 > (mum 10.001)

259 420.521.697

260

261 > (mum 'jerry')

262 1.540.161.753

263

264 > (mum 1)

265 1.901.865.568

266

267 > (mum (some 10))

268 2.099.076.946

269

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

271 1.719.833.228

272```

273

274

275---