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

git.iko.soy/urbit.org

on c19bc7a help sign in

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

279 lines 5.2 kB history raw

1:- :~ navhome/'/docs/'

2 sort/'8'

3 title/'2e: Insecure Hashing'

4 ==

6;>

8# 2e: insecure hashing

10### `++fnv`

12FNV scrambler

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

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

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

18#### Accepts

20`a` is an atom.

22#### Produces

24An atom.

26#### Source

28```

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

30```

32#### Examples

34```

35 > (fnv 10.000)

36 272.465.456

38 > (fnv 10.001)

39 289.243.075

41 > (fnv 1)

42 16.777.619

43```

46---

47### `++mug`

49FNV-1a scrambler

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

52producing an atom.

54#### Accepts

56`a` is a noun.

58#### Produces

60An atom.

62#### Source

64```

65 ++ mug

66 ~/ %mug

67 |= a=*

68 ?^ a

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

70 |- ^- @

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

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

73 ?. =(0 d) d

74 $(q.b +(q.b))

75 =+ b=2.166.136.261

76 |- ^- @

77 =+ c=b

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

79 |- ^- @

80 ?: =(d e)

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

82 ?. =(0 f) f

83 ^$(b +(b))

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

85```

87#### Examples

89```

90 > (mug 10.000)

91 178.152.889

93 > (mug 10.001)

94 714.838.017

96 > (mug 1)

97 67.918.732

99 > (mug (some 10))

100 1.872.403.737

101

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

103 1.067.931.605

104```

105

106

107---

108### `++muk`

109

110Standard MurmurHash3

111

112Implementation of the 32-bit

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

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

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

117#### Accepts

119`a` is an atom.

121`b` is an atom.

123`c` is an atom.

125#### Produces

127An atom.

129#### Source

131```

132 ++ muk

133 ~% %muk ..muk ~

134 =+ ~(. fe 5)

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

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

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

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

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

140 =/ h1 syd

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

142 =/ blocks (rip 5 key)

143 =/ i nblocks

144 =. h1 =/ hi h1 |-

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

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

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

148 =. k1 (rol 0 15 k1)

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

150 =. hi (mix hi k1)

151 =. hi (rol 0 13 hi)

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

153 $(i (dec i))

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

155 =/ k1 0

156 =/ tlen (dis len 3)

157 =. h1

158 ?+ tlen h1 :: fallthrough switch

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

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

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

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

163 =. k1 (rol 0 15 k1)

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

165 (mix h1 k1)

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

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

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

169 =. k1 (rol 0 15 k1)

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

171 (mix h1 k1)

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

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

174 =. k1 (rol 0 15 k1)

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

176 (mix h1 k1)

177 ==

178 =. h1 (mix h1 len)

179 |^ (fmix32 h1)

180 ++ fmix32

181 |= h=@

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

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

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

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

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

187 h

188 --

189```

190

191#### Examples

192

193```

194 > (muk 6 1 3)

195 3.427.677.118

196

197 > (muk 6 2 'jerry')

198 ! exit

199

200 > (muk 6 2 'je')

201 3.602.081.716

202

203 > (met 3 'jerry')

204 5

205

206 > (met 3 'je')

207 2

208

209 > (muk 6 5 'jerry')

210 1.276.447.489

211

212 > (muk 6 15 'jerry')

213 2.881.503.571

214

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

216 > e

217 44.228

218

219 > (muk e 11 10.000)

220 246.077.549

221```

222

223

224---

225### `++mum`

226

22731-bit MurmurHash3 scrambler

228

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

230producing an atom.

232#### Accepts

234`a` is a noun.

236#### Produces

238An atom.

240#### Source

242```

243 ++ mum

244 ~/ %mum

245 |= a=*

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

247 ++ trim

248 |= key=@

249 =+ syd=0xcafe.babe

250 |- ^- @

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

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

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

254```

255

256#### Examples

257

258```

259 > (mum 10.000)

260 795.713.195

261

262 > (mum 10.001)

263 420.521.697

264

265 > (mum 'jerry')

266 1.540.161.753

267

268 > (mum 1)

269 1.901.865.568

270

271 > (mum (some 10))

272 2.099.076.946

273

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

275 1.719.833.228

276```

277

278

279---