1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222

//@ cfg: feature=alloc
// Exhaustive differential driver for base16ct.
//
// This is the crate root for the proof harness. The five module files are the
// crate's own sources, referenced in place rather than copied, so this cannot
// drift from what `tests/cases/026-base16ct-crate/` transpiles. `lib.rs`'s
// core is carried here verbatim, as it is there.
//
// The point of this file is to enumerate *entire input domains* rather than a
// handful of examples. See PROOF.md for what that does and does not establish.

#[path = "../tests/cases/026-base16ct-crate/display.rs"]
mod display;
#[path = "../tests/cases/026-base16ct-crate/error.rs"]
mod error;
#[path = "../tests/cases/026-base16ct-crate/lower.rs"]
mod lower;
#[path = "../tests/cases/026-base16ct-crate/mixed.rs"]
mod mixed;
#[path = "../tests/cases/026-base16ct-crate/upper.rs"]
mod upper;

#[cfg(feature = "alloc")]
pub use std::{string::String, vec::Vec};

pub use crate::display::HexDisplay;
pub use crate::error::{Error, Result};

/// Compute decoded length of the given hex-encoded input.
#[inline(always)]
pub fn decoded_len(bytes: &[u8]) -> Result<usize> {
    if bytes.len() & 1 == 0 {
        Ok(bytes.len() / 2)
    } else {
        Err(Error::InvalidLength)
    }
}

/// Get the length of Base16 (hex) produced by encoding the given bytes.
#[inline(always)]
pub fn encoded_len(bytes: &[u8]) -> usize {
    bytes.len() * 2
}

fn decode_inner<'a>(
    src: &[u8],
    dst: &'a mut [u8],
    decode_nibble: impl Fn(u8) -> u16,
) -> Result<&'a [u8]> {
    let dst = dst
        .get_mut(..decoded_len(src)?)
        .ok_or(Error::InvalidLength)?;

    let mut err: u16 = 0;
    for (src, dst) in src.chunks_exact(2).zip(dst.iter_mut()) {
        let byte = (decode_nibble(src[0]) << 4) | decode_nibble(src[1]);
        err |= byte >> 8;
        *dst = byte as u8;
    }

    match err {
        0 => Ok(dst),
        _ => Err(Error::InvalidEncoding),
    }
}

// --------------------------------------------------------------- reporting

/// One decode result, rendered so that any difference in status, length or
/// content shows up as a difference in these bytes.
fn report(tag: &str, r: Result<&[u8]>) {
    match r {
        Ok(v) => {
            print!("{}=", tag);
            for b in v.iter() {
                print!("{:02x}", b);
            }
            print!("/{}", v.len());
        }
        Err(e) => print!("{}!{:?}", tag, e),
    }
}

fn main() {
    // -- Domain A: every two-byte input, all three decoders. 65,536 inputs,
    //    which is the complete domain of a single decode chunk and therefore
    //    pins the nibble function exactly.
    println!("A two-byte decode, exhaustive");
    let mut hi: u32 = 0;
    while hi < 256 {
        let mut lo: u32 = 0;
        while lo < 256 {
            let src: [u8; 2] = [hi as u8, lo as u8];
            let mut b1 = [0u8; 4];
            let mut b2 = [0u8; 4];
            let mut b3 = [0u8; 4];
            print!("{:02x}{:02x} ", hi, lo);
            report("l", lower::decode(&src, &mut b1));
            print!(" ");
            report("u", upper::decode(&src, &mut b2));
            print!(" ");
            report("m", mixed::decode(&src, &mut b3));
            println!("");
            lo += 1;
        }
        hi += 1;
    }

    // -- Domain B: every two-byte input, both encoders. Encoding is defined
    //    per byte, so this is the complete domain of an encode step too.
    println!("B two-byte encode, exhaustive");
    let mut a: u32 = 0;
    while a < 256 {
        let mut b: u32 = 0;
        while b < 256 {
            let src: [u8; 2] = [a as u8, b as u8];
            let mut e1 = [0u8; 4];
            let mut e2 = [0u8; 4];
            print!("{:02x}{:02x} ", a, b);
            report("l", lower::encode(&src, &mut e1));
            print!(" ");
            report("u", upper::encode(&src, &mut e2));
            println!("");
            b += 1;
        }
        a += 1;
    }

    // -- Domain C: every single byte, encode_str and HexDisplay.
    println!("C single-byte encode_str and HexDisplay, exhaustive");
    let mut c: u32 = 0;
    while c < 256 {
        let src: [u8; 1] = [c as u8];
        let mut e = [0u8; 2];
        match lower::encode_str(&src, &mut e) {
            Ok(s) => print!("{:02x} s={} ", c, s),
            Err(er) => print!("{:02x} s!{:?} ", c, er),
        }
        println!("x={:x} X={:X} d={}", HexDisplay(&src), HexDisplay(&src), HexDisplay(&src));
        c += 1;
    }

    // -- Domain D: lengths 0..=128, both length functions and the buffer-size
    //    boundary. Covers odd/even and the too-small-destination path.
    println!("D lengths, exhaustive to 128");
    let big = [b'a'; 128];
    let mut n: usize = 0;
    while n <= 128 {
        let src = &big[..n];
        match decoded_len(src) {
            Ok(v) => print!("{} dl={} el={}", n, v, encoded_len(src)),
            Err(e) => print!("{} dl!{:?} el={}", n, e, encoded_len(src)),
        }
        // Destination exactly one byte too small, to exercise the bound.
        let mut tight = [0u8; 64];
        let want = n / 2;
        if want > 0 && want <= 64 {
            let fit = &mut tight[..want - 1];
            print!(" ");
            report("t", mixed::decode(src, fit));
        }
        println!("");
        n += 1;
    }

    // -- Domain E: pseudorandom inputs of varied length, from a generator
    //    defined here so both sides produce the identical sequence.
    println!("E pseudorandom, 20000 cases");
    let mut state: u32 = 2463534242;
    let mut i: u32 = 0;
    while i < 20000 {
        // xorshift32, chosen because it is exactly representable in both
        // languages: u32 wrapping shifts and xor, nothing else.
        state ^= state << 13;
        state ^= state >> 17;
        state ^= state << 5;
        let len: usize = (state % 49) as usize;

        let mut buf = [0u8; 48];
        let mut j: usize = 0;
        while j < len {
            state ^= state << 13;
            state ^= state >> 17;
            state ^= state << 5;
            // Mostly hex characters, sometimes not, so both the accepting and
            // the rejecting paths are exercised.
            let pick = state % 20;
            if pick < 16 {
                let d = (state >> 8) % 16;
                if d < 10 {
                    buf[j] = 48 + d as u8;
                } else if (state >> 4) % 2 == 0 {
                    buf[j] = 87 + d as u8;
                } else {
                    buf[j] = 55 + d as u8;
                }
            } else {
                buf[j] = (state >> 16) as u8;
            }
            j += 1;
        }
        let src = &buf[..len];

        let mut d1 = [0u8; 24];
        let mut d2 = [0u8; 24];
        let mut d3 = [0u8; 24];
        print!("{} {} ", i, len);
        report("l", lower::decode(src, &mut d1));
        print!(" ");
        report("u", upper::decode(src, &mut d2));
        print!(" ");
        report("m", mixed::decode(src, &mut d3));

        // Round trip: encode the bytes, decode them back.
        let mut enc = [0u8; 96];
        report(" e", lower::encode(src, &mut enc));
        println!("");
        i += 1;
    }

    println!("done");
}