def tree

bend-collections-laws-crypto@1.0.0.0 · spec/crypto/blake/blake3.bend:244

import Base
import bend-collections-laws-crypto@1.0.0.0/src/crypto/blake/blake3/types.bend as T
import bend-collections-laws-crypto@1.0.0.0/spec/lib/common.bend as SC

244# The tree over the chunk outputs xs, 1 <= |xs| <= 2^h. The chunks are its
245# leaves in order; a left subtree is always complete with a power of two of
246# chunks, the largest one that leaves at least one chunk to its right: with
247# h = g+1 and |xs| > 2^g the left subtree takes the first 2^g chunks and the
248# right one the rest, while |xs| <= 2^g (nothing left for the right) means the
249# tree already fits in height g.
250def tree(+h: Nat, +xs: List<&2,T.Out>) -> T.Out:
251  match h xs:
252    case 0n Nil{}: first(Nil{})
253    case 0n Con{+x,+r}: first(Con{x,r})
254    case 1n+g Nil{}: first(Nil{})
255    case 1n+g Con{+x,+r}:
256      +k = SC.pow2(g)
257      join(tree(g,SC.take(T.Out,Con{x,r},k)),tree(g,SC.drop(T.Out,Con{x,r},k)),is_nil(SC.drop(T.Out,Con{x,r},k)))