| Prove byte-identity for base16ct by enumerating whole input domains 99b8376 nandithebull 10h ago | 1 | //@ cfg: feature=alloc |
| 2 | // Exhaustive differential driver for base16ct. |
| 3 | // |
| 4 | // This is the crate root for the proof harness. The five module files are the |
| 5 | // crate's own sources, referenced in place rather than copied, so this cannot |
| 6 | // drift from what `tests/cases/026-base16ct-crate/` transpiles. `lib.rs`'s |
| 7 | // core is carried here verbatim, as it is there. |
| 8 | // |
| 9 | // The point of this file is to enumerate *entire input domains* rather than a |
| 10 | // handful of examples. See PROOF.md for what that does and does not establish. |
| 11 | |
| 12 | #[path = "../tests/cases/026-base16ct-crate/display.rs"] |
| 13 | mod display; |
| 14 | #[path = "../tests/cases/026-base16ct-crate/error.rs"] |
| 15 | mod error; |
| 16 | #[path = "../tests/cases/026-base16ct-crate/lower.rs"] |
| 17 | mod lower; |
| 18 | #[path = "../tests/cases/026-base16ct-crate/mixed.rs"] |
| 19 | mod mixed; |
| 20 | #[path = "../tests/cases/026-base16ct-crate/upper.rs"] |
| 21 | mod upper; |
| 22 | |
| 23 | #[cfg(feature = "alloc")] |
| 24 | pub use std::{string::String, vec::Vec}; |
| 25 | |
| 26 | pub use crate::display::HexDisplay; |
| 27 | pub use crate::error::{Error, Result}; |
| 28 | |
| 29 | /// Compute decoded length of the given hex-encoded input. |
| 30 | #[inline(always)] |
| 31 | pub fn decoded_len(bytes: &[u8]) -> Result<usize> { |
| 32 | if bytes.len() & 1 == 0 { |
| 33 | Ok(bytes.len() / 2) |
| 34 | } else { |
| 35 | Err(Error::InvalidLength) |
| 36 | } |
| 37 | } |
| 38 | |
| 39 | /// Get the length of Base16 (hex) produced by encoding the given bytes. |
| 40 | #[inline(always)] |
| 41 | pub fn encoded_len(bytes: &[u8]) -> usize { |
| 42 | bytes.len() * 2 |
| 43 | } |
| 44 | |
| 45 | fn decode_inner<'a>( |
| 46 | src: &[u8], |
| 47 | dst: &'a mut [u8], |
| 48 | decode_nibble: impl Fn(u8) -> u16, |
| 49 | ) -> Result<&'a [u8]> { |
| 50 | let dst = dst |
| 51 | .get_mut(..decoded_len(src)?) |
| 52 | .ok_or(Error::InvalidLength)?; |
| 53 | |
| 54 | let mut err: u16 = 0; |
| 55 | for (src, dst) in src.chunks_exact(2).zip(dst.iter_mut()) { |
| 56 | let byte = (decode_nibble(src[0]) << 4) | decode_nibble(src[1]); |
| 57 | err |= byte >> 8; |
| 58 | *dst = byte as u8; |
| 59 | } |
| 60 | |
| 61 | match err { |
| 62 | 0 => Ok(dst), |
| 63 | _ => Err(Error::InvalidEncoding), |
| 64 | } |
| 65 | } |
| 66 | |
| 67 | // --------------------------------------------------------------- reporting |
| 68 | |
| 69 | /// One decode result, rendered so that any difference in status, length or |
| 70 | /// content shows up as a difference in these bytes. |
| 71 | fn report(tag: &str, r: Result<&[u8]>) { |
| 72 | match r { |
| 73 | Ok(v) => { |
| 74 | print!("{}=", tag); |
| 75 | for b in v.iter() { |
| 76 | print!("{:02x}", b); |
| 77 | } |
| 78 | print!("/{}", v.len()); |
| 79 | } |
| 80 | Err(e) => print!("{}!{:?}", tag, e), |
| 81 | } |
| 82 | } |
| 83 | |
| 84 | fn main() { |
| 85 | // -- Domain A: every two-byte input, all three decoders. 65,536 inputs, |
| 86 | // which is the complete domain of a single decode chunk and therefore |
| 87 | // pins the nibble function exactly. |
| 88 | println!("A two-byte decode, exhaustive"); |
| 89 | let mut hi: u32 = 0; |
| 90 | while hi < 256 { |
| 91 | let mut lo: u32 = 0; |
| 92 | while lo < 256 { |
| 93 | let src: [u8; 2] = [hi as u8, lo as u8]; |
| 94 | let mut b1 = [0u8; 4]; |
| 95 | let mut b2 = [0u8; 4]; |
| 96 | let mut b3 = [0u8; 4]; |
| 97 | print!("{:02x}{:02x} ", hi, lo); |
| 98 | report("l", lower::decode(&src, &mut b1)); |
| 99 | print!(" "); |
| 100 | report("u", upper::decode(&src, &mut b2)); |
| 101 | print!(" "); |
| 102 | report("m", mixed::decode(&src, &mut b3)); |
| 103 | println!(""); |
| 104 | lo += 1; |
| 105 | } |
| 106 | hi += 1; |
| 107 | } |
| 108 | |
| 109 | // -- Domain B: every two-byte input, both encoders. Encoding is defined |
| 110 | // per byte, so this is the complete domain of an encode step too. |
| 111 | println!("B two-byte encode, exhaustive"); |
| 112 | let mut a: u32 = 0; |
| 113 | while a < 256 { |
| 114 | let mut b: u32 = 0; |
| 115 | while b < 256 { |
| 116 | let src: [u8; 2] = [a as u8, b as u8]; |
| 117 | let mut e1 = [0u8; 4]; |
| 118 | let mut e2 = [0u8; 4]; |
| 119 | print!("{:02x}{:02x} ", a, b); |
| 120 | report("l", lower::encode(&src, &mut e1)); |
| 121 | print!(" "); |
| 122 | report("u", upper::encode(&src, &mut e2)); |
| 123 | println!(""); |
| 124 | b += 1; |
| 125 | } |
| 126 | a += 1; |
| 127 | } |
| 128 | |
| 129 | // -- Domain C: every single byte, encode_str and HexDisplay. |
| 130 | println!("C single-byte encode_str and HexDisplay, exhaustive"); |
| 131 | let mut c: u32 = 0; |
| 132 | while c < 256 { |
| 133 | let src: [u8; 1] = [c as u8]; |
| 134 | let mut e = [0u8; 2]; |
| 135 | match lower::encode_str(&src, &mut e) { |
| 136 | Ok(s) => print!("{:02x} s={} ", c, s), |
| 137 | Err(er) => print!("{:02x} s!{:?} ", c, er), |
| 138 | } |
| 139 | println!("x={:x} X={:X} d={}", HexDisplay(&src), HexDisplay(&src), HexDisplay(&src)); |
| 140 | c += 1; |
| 141 | } |
| 142 | |
| 143 | // -- Domain D: lengths 0..=128, both length functions and the buffer-size |
| 144 | // boundary. Covers odd/even and the too-small-destination path. |
| 145 | println!("D lengths, exhaustive to 128"); |
| 146 | let big = [b'a'; 128]; |
| 147 | let mut n: usize = 0; |
| 148 | while n <= 128 { |
| 149 | let src = &big[..n]; |
| 150 | match decoded_len(src) { |
| 151 | Ok(v) => print!("{} dl={} el={}", n, v, encoded_len(src)), |
| 152 | Err(e) => print!("{} dl!{:?} el={}", n, e, encoded_len(src)), |
| 153 | } |
| 154 | // Destination exactly one byte too small, to exercise the bound. |
| 155 | let mut tight = [0u8; 64]; |
| 156 | let want = n / 2; |
| 157 | if want > 0 && want <= 64 { |
| 158 | let fit = &mut tight[..want - 1]; |
| 159 | print!(" "); |
| 160 | report("t", mixed::decode(src, fit)); |
| 161 | } |
| 162 | println!(""); |
| 163 | n += 1; |
| 164 | } |
| 165 | |
| 166 | // -- Domain E: pseudorandom inputs of varied length, from a generator |
| 167 | // defined here so both sides produce the identical sequence. |
| 168 | println!("E pseudorandom, 20000 cases"); |
| 169 | let mut state: u32 = 2463534242; |
| 170 | let mut i: u32 = 0; |
| 171 | while i < 20000 { |
| 172 | // xorshift32, chosen because it is exactly representable in both |
| 173 | // languages: u32 wrapping shifts and xor, nothing else. |
| 174 | state ^= state << 13; |
| 175 | state ^= state >> 17; |
| 176 | state ^= state << 5; |
| 177 | let len: usize = (state % 49) as usize; |
| 178 | |
| 179 | let mut buf = [0u8; 48]; |
| 180 | let mut j: usize = 0; |
| 181 | while j < len { |
| 182 | state ^= state << 13; |
| 183 | state ^= state >> 17; |
| 184 | state ^= state << 5; |
| 185 | // Mostly hex characters, sometimes not, so both the accepting and |
| 186 | // the rejecting paths are exercised. |
| 187 | let pick = state % 20; |
| 188 | if pick < 16 { |
| 189 | let d = (state >> 8) % 16; |
| 190 | if d < 10 { |
| 191 | buf[j] = 48 + d as u8; |
| 192 | } else if (state >> 4) % 2 == 0 { |
| 193 | buf[j] = 87 + d as u8; |
| 194 | } else { |
| 195 | buf[j] = 55 + d as u8; |
| 196 | } |
| 197 | } else { |
| 198 | buf[j] = (state >> 16) as u8; |
| 199 | } |
| 200 | j += 1; |
| 201 | } |
| 202 | let src = &buf[..len]; |
| 203 | |
| 204 | let mut d1 = [0u8; 24]; |
| 205 | let mut d2 = [0u8; 24]; |
| 206 | let mut d3 = [0u8; 24]; |
| 207 | print!("{} {} ", i, len); |
| 208 | report("l", lower::decode(src, &mut d1)); |
| 209 | print!(" "); |
| 210 | report("u", upper::decode(src, &mut d2)); |
| 211 | print!(" "); |
| 212 | report("m", mixed::decode(src, &mut d3)); |
| 213 | |
| 214 | // Round trip: encode the bytes, decode them back. |
| 215 | let mut enc = [0u8; 96]; |
| 216 | report(" e", lower::encode(src, &mut enc)); |
| 217 | println!(""); |
| 218 | i += 1; |
| 219 | } |
| 220 | |
| 221 | println!("done"); |
| 222 | } |