1 import Base 2 import ./types.bend as T 3 import ./compress.bend as C 4 5 # BLAKE3 hash mode, 32-byte output. 6 # 7 # blake3(words, byte_length): the message is packed little-endian, four bytes 8 # per U32 word, and byte_length is its logical length. The result is None when 9 # byte_length exceeds 4 * the array's capacity, else the 32-byte digest as 10 # eight little-endian U32 words. Bytes past byte_length in the last word do not 11 # influence the result. 12 # 13 # The message is split into 1024-byte chunks (the last one holds the remaining 14 # 1..1024 bytes, or 0 for the empty message). Every chunk but the last is 15 # compressed to its chaining value as soon as it is read and pushed on a stack 16 # of subtree chaining values, merged like a binary counter: a slot holds the 17 # chaining value of a complete subtree of 2^i chunks, and pushing into a full 18 # slot merges both into a parent node carried to the next slot. The last chunk 19 # stays pending; at the end the stack is folded into it from the smallest 20 # subtree up, and the resulting root node is compressed with ROOT. 21 22 def iv() -> T.CV: 23 T.CV{1779033703,3144134277,1013904242,2773480762,1359893119,2600822924,528734635,1541459225} 24 25 # GENERATED BEGIN (tools/generators/blake3/gen.py) 26 # Reads the 16 words of a block at word `index`, threading the array. 27 def read15(+index: U32, w0: U32, w1: U32, w2: U32, w3: U32, w4: U32, w5: U32, w6: U32, w7: U32, w8: U32, w9: U32, w10: U32, w11: U32, w12: U32, w13: U32, w14: U32, pair: Array & U32) -> Array & T.Block: 28 (a,w15) = pair 29 (a,T.B{w0,w1,w2,w3,w4,w5,w6,w7,w8,w9,w10,w11,w12,w13,w14,w15}) 30 31 def read14(+index: U32, w0: U32, w1: U32, w2: U32, w3: U32, w4: U32, w5: U32, w6: U32, w7: U32, w8: U32, w9: U32, w10: U32, w11: U32, w12: U32, w13: U32, pair: Array & U32) -> Array & T.Block: 32 (a,w14) = pair 33 read15(index,w0,w1,w2,w3,w4,w5,w6,w7,w8,w9,w10,w11,w12,w13,w14,Array.get(U32,a,U32.add(index,15))) 34 35 def read13(+index: U32, w0: U32, w1: U32, w2: U32, w3: U32, w4: U32, w5: U32, w6: U32, w7: U32, w8: U32, w9: U32, w10: U32, w11: U32, w12: U32, pair: Array & U32) -> Array & T.Block: 36 (a,w13) = pair 37 read14(index,w0,w1,w2,w3,w4,w5,w6,w7,w8,w9,w10,w11,w12,w13,Array.get(U32,a,U32.add(index,14))) 38 39 def read12(+index: U32, w0: U32, w1: U32, w2: U32, w3: U32, w4: U32, w5: U32, w6: U32, w7: U32, w8: U32, w9: U32, w10: U32, w11: U32, pair: Array & U32) -> Array & T.Block: 40 (a,w12) = pair 41 read13(index,w0,w1,w2,w3,w4,w5,w6,w7,w8,w9,w10,w11,w12,Array.get(U32,a,U32.add(index,13))) 42 43 def read11(+index: U32, w0: U32, w1: U32, w2: U32, w3: U32, w4: U32, w5: U32, w6: U32, w7: U32, w8: U32, w9: U32, w10: U32, pair: Array & U32) -> Array & T.Block: 44 (a,w11) = pair 45 read12(index,w0,w1,w2,w3,w4,w5,w6,w7,w8,w9,w10,w11,Array.get(U32,a,U32.add(index,12))) 46 47 def read10(+index: U32, w0: U32, w1: U32, w2: U32, w3: U32, w4: U32, w5: U32, w6: U32, w7: U32, w8: U32, w9: U32, pair: Array & U32) -> Array & T.Block: 48 (a,w10) = pair 49 read11(index,w0,w1,w2,w3,w4,w5,w6,w7,w8,w9,w10,Array.get(U32,a,U32.add(index,11))) 50 51 def read9(+index: U32, w0: U32, w1: U32, w2: U32, w3: U32, w4: U32, w5: U32, w6: U32, w7: U32, w8: U32, pair: Array & U32) -> Array & T.Block: 52 (a,w9) = pair 53 read10(index,w0,w1,w2,w3,w4,w5,w6,w7,w8,w9,Array.get(U32,a,U32.add(index,10))) 54 55 def read8(+index: U32, w0: U32, w1: U32, w2: U32, w3: U32, w4: U32, w5: U32, w6: U32, w7: U32, pair: Array & U32) -> Array & T.Block: 56 (a,w8) = pair 57 read9(index,w0,w1,w2,w3,w4,w5,w6,w7,w8,Array.get(U32,a,U32.add(index,9))) 58 59 def read7(+index: U32, w0: U32, w1: U32, w2: U32, w3: U32, w4: U32, w5: U32, w6: U32, pair: Array & U32) -> Array & T.Block: 60 (a,w7) = pair 61 read8(index,w0,w1,w2,w3,w4,w5,w6,w7,Array.get(U32,a,U32.add(index,8))) 62 63 def read6(+index: U32, w0: U32, w1: U32, w2: U32, w3: U32, w4: U32, w5: U32, pair: Array & U32) -> Array & T.Block: 64 (a,w6) = pair 65 read7(index,w0,w1,w2,w3,w4,w5,w6,Array.get(U32,a,U32.add(index,7))) 66 67 def read5(+index: U32, w0: U32, w1: U32, w2: U32, w3: U32, w4: U32, pair: Array & U32) -> Array & T.Block: 68 (a,w5) = pair 69 read6(index,w0,w1,w2,w3,w4,w5,Array.get(U32,a,U32.add(index,6))) 70 71 def read4(+index: U32, w0: U32, w1: U32, w2: U32, w3: U32, pair: Array & U32) -> Array & T.Block: 72 (a,w4) = pair 73 read5(index,w0,w1,w2,w3,w4,Array.get(U32,a,U32.add(index,5))) 74 75 def read3(+index: U32, w0: U32, w1: U32, w2: U32, pair: Array & U32) -> Array & T.Block: 76 (a,w3) = pair 77 read4(index,w0,w1,w2,w3,Array.get(U32,a,U32.add(index,4))) 78 79 def read2(+index: U32, w0: U32, w1: U32, pair: Array & U32) -> Array & T.Block: 80 (a,w2) = pair 81 read3(index,w0,w1,w2,Array.get(U32,a,U32.add(index,3))) 82 83 def read1(+index: U32, w0: U32, pair: Array & U32) -> Array & T.Block: 84 (a,w1) = pair 85 read2(index,w0,w1,Array.get(U32,a,U32.add(index,2))) 86 87 def read0(+index: U32, pair: Array & U32) -> Array & T.Block: 88 (a,w0) = pair 89 read1(index,w0,Array.get(U32,a,U32.add(index,1))) 90 91 def read_block(a: Array, +index: U32) -> Array & T.Block: 92 read0(index,Array.get(U32,a,index)) 93 # GENERATED END 94 95 # The block truncated to its first `len` bytes: the word at byte offset pos 96 # keeps its low len - pos bytes (all four when at least four remain). 97 def partial(w: U32, delta: Nat) -> U32: 98 match delta: 99 case 0n: 0 100 case 1n: U32.and(w,255) 101 case 2n: U32.and(w,65535) 102 case 3n: U32.and(w,16777215) 103 case 4n+q: w 104 105 def mask(w: U32, +pos: Nat, +len: Nat) -> U32: 106 partial(w,Nat.sub(len,pos)) 107 108 def mask_block(b: T.Block, +len: Nat) -> T.Block: 109 match b: 110 case T.B{m0,m1,m2,m3,m4,m5,m6,m7,m8,m9,m10,m11,m12,m13,m14,m15}: 111 T.B{mask(m0,0n,len),mask(m1,4n,len),mask(m2,8n,len),mask(m3,12n,len),mask(m4,16n,len),mask(m5,20n,len),mask(m6,24n,len),mask(m7,28n,len),mask(m8,32n,len),mask(m9,36n,len),mask(m10,40n,len),mask(m11,44n,len),mask(m12,48n,len),mask(m13,52n,len),mask(m14,56n,len),mask(m15,60n,len)} 112 113 # A chunk that is not the last: n more full blocks after the current one, the 114 # current block in `pair`; flags is CHUNK_START on the first block and 0 after. 115 # Returns the chunk's chaining value. 116 def full_go(n: Nat, +counter: U32, +index: U32, +flags: U32, cv: T.CV, pair: Array & T.Block) -> Array & T.CV: 117 match n pair: 118 case 0n Tuple{a,b}: (a,C.compress(cv,b,counter,64,U32.or(flags,2))) 119 case 1n+p Tuple{a,b}: full_go(p,counter,U32.add(index,16),0,C.compress(cv,b,counter,64,flags),read_block(a,U32.add(index,16))) 120 121 def full_chunk(a: Array, +counter: U32, +index: U32) -> Array & T.CV: 122 full_go(15n,counter,index,1,iv(),read_block(a,index)) 123 124 # The last chunk: n full blocks before its last block of len bytes (1..64, or 125 # 0 for the empty message). Returns the pending output of the last block. 126 def last_go(n: Nat, +counter: U32, +index: U32, +flags: U32, +len: Nat, cv: T.CV, pair: Array & T.Block) -> Array & T.Out: 127 match n pair: 128 case 0n Tuple{a,b}: (a,T.Out{cv,mask_block(b,len),counter,U32.from_nat(len),U32.or(flags,2)}) 129 case 1n+p Tuple{a,b}: last_go(p,counter,U32.add(index,16),0,len,C.compress(cv,b,counter,64,flags),read_block(a,U32.add(index,16))) 130 131 def last_chunk(a: Array, +counter: U32, +index: U32, +len: Nat) -> Array & T.Out: 132 +n = Nat.div(Nat.sub(len,1n),64n) 133 last_go(n,counter,index,1,Nat.sub(len,Nat.mul(n,64n)),iv(),read_block(a,index)) 134 135 def out_cv(o: T.Out) -> T.CV: 136 match o: 137 case T.Out{cv,b,t,len,flags}: C.compress(cv,b,t,len,flags) 138 139 def root_cv(o: T.Out) -> T.CV: 140 match o: 141 case T.Out{cv,b,t,len,flags}: C.compress(cv,b,t,len,U32.or(flags,8)) 142 143 def parent_block(l: T.CV, r: T.CV) -> T.Block: 144 match l r: 145 case T.CV{l0,l1,l2,l3,l4,l5,l6,l7} T.CV{r0,r1,r2,r3,r4,r5,r6,r7}: 146 T.B{l0,l1,l2,l3,l4,l5,l6,l7,r0,r1,r2,r3,r4,r5,r6,r7} 147 148 def parent_out(l: T.CV, r: T.CV) -> T.Out: 149 T.Out{iv(),parent_block(l,r),0,64,4} 150 151 def parent_cv(l: T.CV, r: T.CV) -> T.CV: 152 C.compress(iv(),parent_block(l,r),0,64,4) 153 154 # The subtree stack, smallest subtree first: slot i is empty or holds the 155 # chaining value of a complete subtree of 2^i chunks. 156 type Stack is Data: 157 StkNil{} 158 SEmpty{rest: Stack} 159 SFull{cv: T.CV, rest: Stack} 160 161 def push(s: Stack, c: T.CV) -> Stack: 162 match s: 163 case StkNil{}: SFull{c,StkNil{}} 164 case SEmpty{r}: SFull{c,r} 165 case SFull{d,r}: SEmpty{push(r,parent_cv(d,c))} 166 167 # Folds the stack into the pending output of the rightmost subtree. 168 def finish(s: Stack, o: T.Out) -> T.Out: 169 match s: 170 case StkNil{}: o 171 case SEmpty{r}: finish(r,o) 172 case SFull{d,r}: finish(r,parent_out(d,out_cv(o))) 173 174 def pushed(s: Stack, pair: Array & T.CV) -> Array & Stack: 175 (a,c) = pair 176 (a,push(s,c)) 177 178 # n chunks before the last; len is the byte length of the last chunk. 179 def chunks(n: Nat, +counter: U32, +index: U32, +len: Nat, pair: Array & Stack) -> T.Out: 180 match n pair: 181 case 0n Tuple{a,s}: finish(s,Pair.snd(Array,T.Out,last_chunk(a,counter,index,len))) 182 case 1n+p Tuple{a,s}: chunks(p,U32.inc(counter),U32.add(index,256),len,pushed(s,full_chunk(a,counter,index))) 183 184 def unchecked(a: Array, +length: Nat) -> T.CV: 185 +n = Nat.div(Nat.sub(length,1n),1024n) 186 root_cv(chunks(n,0,0,Nat.sub(length,Nat.mul(n,1024n)),(a,StkNil{}))) 187 188 def digest(c: T.CV) -> Array: 189 match c: 190 case T.CV{h0,h1,h2,h3,h4,h5,h6,h7}: 191 a = Array.new(U32,3n,0) 192 a = Array.set(U32,a,0,h0) 193 a = Array.set(U32,a,1,h1) 194 a = Array.set(U32,a,2,h2) 195 a = Array.set(U32,a,3,h3) 196 a = Array.set(U32,a,4,h4) 197 a = Array.set(U32,a,5,h5) 198 a = Array.set(U32,a,6,h6) 199 a = Array.set(U32,a,7,h7) 200 a 201 202 def checked(valid: Bool, a: Array, +length: Nat) -> Maybe<&1,Array>: 203 match valid: 204 case False{}: None{} 205 case True{}: Some{digest(unchecked(a,length))} 206 207 def sized(+length: Nat, pair: Array & U32) -> Maybe<&1,Array>: 208 (a,capacity) = pair 209 checked(Nat.is_le(length,Nat.mul(4n,U32.to_nat(capacity))),a,length) 210 211 def blake3(words: Array, byte_length: Nat) -> Maybe<&1,Array>: 212 sized(byte_length,Array.size(U32,words))