clvm_fuzzing/
fuzzing_utils.rs

1use chia_sha2::Sha256;
2use clvmr::allocator::{Allocator, NodePtr, SExp};
3use std::collections::hash_map::Entry;
4use std::collections::HashMap;
5
6pub fn hash_atom(buf: &[u8]) -> [u8; 32] {
7    let mut ctx = Sha256::new();
8    ctx.update([1_u8]);
9    ctx.update(buf);
10    ctx.finalize()
11}
12
13pub fn hash_pair(left: &[u8; 32], right: &[u8; 32]) -> [u8; 32] {
14    let mut ctx = Sha256::new();
15    ctx.update([2_u8]);
16    ctx.update(left);
17    ctx.update(right);
18    ctx.finalize()
19}
20
21enum TreeOp {
22    SExp(NodePtr),
23    Cons(NodePtr),
24}
25
26pub fn tree_hash(a: &Allocator, node: NodePtr) -> [u8; 32] {
27    let mut hashes = Vec::<[u8; 32]>::new();
28    let mut ops = vec![TreeOp::SExp(node)];
29    let mut cache = HashMap::<NodePtr, [u8; 32]>::new();
30
31    while let Some(op) = ops.pop() {
32        match op {
33            TreeOp::SExp(node) => match cache.entry(node) {
34                Entry::Occupied(e) => hashes.push(*e.get()),
35                Entry::Vacant(e) => match a.sexp(node) {
36                    SExp::Atom => {
37                        let hash = hash_atom(a.atom(node).as_ref());
38                        e.insert(hash);
39                        hashes.push(hash);
40                    }
41                    SExp::Pair(left, right) => {
42                        ops.push(TreeOp::Cons(node));
43                        ops.push(TreeOp::SExp(left));
44                        ops.push(TreeOp::SExp(right));
45                    }
46                },
47            },
48            TreeOp::Cons(node) => {
49                let first = hashes.pop().unwrap();
50                let rest = hashes.pop().unwrap();
51                match cache.entry(node) {
52                    Entry::Occupied(e) => hashes.push(*e.get()),
53                    Entry::Vacant(e) => {
54                        let hash = hash_pair(&first, &rest);
55                        e.insert(hash);
56                        hashes.push(hash);
57                    }
58                }
59            }
60        }
61    }
62
63    assert!(hashes.len() == 1);
64    hashes[0]
65}
66
67pub fn visit_tree(a: &Allocator, node: NodePtr, mut visit: impl FnMut(&Allocator, NodePtr)) {
68    let mut nodes = vec![node];
69    let mut visited_index = 0;
70
71    while nodes.len() > visited_index {
72        match a.sexp(nodes[visited_index]) {
73            SExp::Atom => {}
74            SExp::Pair(left, right) => {
75                nodes.push(left);
76                nodes.push(right);
77            }
78        }
79        visited_index += 1;
80    }
81
82    // visit nodes bottom-up (right to left).
83    for node in nodes.into_iter().rev() {
84        visit(a, node);
85    }
86}
clvm_fuzzing/fuzzing_utils.rs

clvm_fuzzing/
fuzzing_utils.rs
