`var_len_buf_from_slice` in benchmarks is wrong

[apoelstra]

We have a method var_len_buf_from_slice whose goal is to take a byte slice and convert it to a Simplicity "buffer" type Ctx8. From simplicity/jets.c:

/* sha_256_ctx_8_init : ONE |- CTX8
 * where
 * CTX8 = (TWO^8)^<64 * TWO^64 * TWO^256
 */

and from simplicity/frame.c

/* ...
 * The notation X^<2 is notation for the type (S X)
 * The notation X^<(2*n) is notation for the type S (X^n) * X^<n
 */

IOW the buffer type is S(TWO^8) * S(TWO^16) * ... * S(TWO^(8*32)) * TWO^64 * TWO^256. Ignoring the last two words, this lets us encode up to 63 bytes by encoding it as a sequence of optional power-of-two-length words.

Critically, the Ctx8 type counts bytes, not bits. But in jets-bench/src/data_structures.rs we have

pub struct SimplicityCtx8 {
    buffer: [u8; 512],
    h: [u32; 8],
    length: usize,
}

so immediately, our buffer is 8 times as large as it should be. (In fact regardless of how Simplicity represents things, if we're using a u8 array in Rust our counts should all be 64 not 512.) So we fix this, as well as the initialization points, and one place where we mod our total message length by 512.

Next, we see

/// Read bytes from a Simplicity buffer of type (TWO^8)^<2^(n+1) as [`Value`].
/// The notation X^<2 is notation for the type (S X)
/// The notation X^<(2*n) is notation for the type S (X^n) * X^<n
///
/// Cannot represent >= 2**16 bytes 0 <= n < 16 as simplicity consensus rule.
///
/// # Panics:
///
/// Panics if the length of the slice is >= 2^(n + 1) bytes
pub fn var_len_buf_from_slice(v: &[u8], mut n: usize) -> Result<Value, Error> {
    // Simplicity consensus rule for n < 16 while reading buffers.
    assert!(n < 16);
    assert!(v.len() < (1 << (n + 1)));
    let mut iter = BitIter::new(v.iter().copied());
    let mut res = None;
    while n > 0 {
        let ty = Final::two_two_n(n);
        let v = if v.len() >= (1 << (n + 1)) {
            let val = iter.read_value(&ty)?;
            Value::some(val)
        } else {
            Value::none(ty)
        };
        res = match res {
            Some(prod) => Some(Value::product(prod, v)),
            None => Some(v),
        };
        n -= 1;
    }
    Ok(res.unwrap_or(Value::unit()))
}

...

let buf = var_len_buf_from_slice(&self.buffer[..buf_len], 8).unwrap();

Multiple problems here. According to our docs, we are reading a buffer of type (TWO^8)^<2^(n+1) so as per above, n should be 5. But we're calling it with n hardcoded to 8. Okay. Then second, we have a while n > 0 loop which iterates n times but (TWO^8)^<2^(n+1) is defined to have n+1 terms. So even if we were calling this function correctly it's iterating the wrong number of times. And then, in each iteration we are reading the type Final::two_two_n(n) which reads 2^n bits, but because we're byte oriented we actually want to read 2^(n+3) bits. So each of our iterations are wrong.

Then the comparison if v.len() >= (1 << (n + 1)) is (a) again offsetting n incorrectly (+1 shouldn't be there) and (b) is nonsense. We want to be checking the nth bit of v.len() not checking numerically if v.len() is greater than or equal to that bit.

[apoelstra]

All of these problems date to the original version of this code from #101. However, until #244 they were disguised because:

• the nonsense comparison was hidden because we only ever call this with v.len() equal to 511
• the bits-vs-bytes confusion was hidden because when writing values produced by this function to the bit machine, we were using Value::do_each_bit, which encodes the value in its compact form, which for the mangled values we were producing was always smaller than the padded form that the bit machine was expecting. So we would under-write to the frame and simply call the jet with uninitialized values, which is harmless

After #244 we switched to correctly using the padded form, and our mangled values were then larger than the type they were supposed to be. This caused us to write off the end of the frame, which triggered a segfault, which we didn't notice because we never ran the benchmarks after this change.