clvm_fuzzing/
serialized_len.rs

1use clvmr::serde::node_to_bytes;
2use clvmr::{Allocator, NodePtr, SExp};
3use std::collections::HashMap;
4use std::collections::hash_map::Entry;
5
6enum Op {
7    Cons(NodePtr),
8    Traverse(NodePtr),
9}
10pub fn compute_serialized_len(a: &Allocator, n: NodePtr) -> u64 {
11    let mut stack: Vec<u64> = vec![];
12    let mut op_stack = vec![Op::Traverse(n)];
13    let mut cache = HashMap::<NodePtr, u64>::new();
14
15    while let Some(op) = op_stack.pop() {
16        match op {
17            Op::Cons(node) => {
18                let right = stack.pop().expect("internal error, empty stack");
19                let left = stack.pop().expect("internal error, empty stack");
20                match cache.entry(node) {
21                    Entry::Occupied(e) => stack.push(*e.get()),
22                    Entry::Vacant(e) => {
23                        e.insert(1 + left + right);
24                        stack.push(1 + left + right);
25                    }
26                }
27            }
28            Op::Traverse(node) => match cache.entry(node) {
29                Entry::Occupied(e) => stack.push(*e.get()),
30                Entry::Vacant(e) => match a.sexp(node) {
31                    SExp::Pair(left, right) => {
32                        op_stack.push(Op::Cons(node));
33                        op_stack.push(Op::Traverse(left));
34                        op_stack.push(Op::Traverse(right));
35                    }
36                    SExp::Atom => {
37                        let ser_len = node_to_bytes(a, node)
38                            .expect("internal error, failed to serialize")
39                            .len() as u64;
40                        e.insert(ser_len);
41                        stack.push(ser_len);
42                    }
43                },
44            },
45        }
46    }
47    assert_eq!(stack.len(), 1);
48    *stack.last().expect("internal error, empty stack")
49}
clvm_fuzzing/serialized_len.rs

clvm_fuzzing/
serialized_len.rs
