baryl 0.0.4

//! A ready-made byte mutator, for a harness that would rather not write one.
//!
//! [`havoc`] is the whole of it: hand it the case and a seeded [`Rng`] and it
//! makes between one and eight random edits — bit flips, small arithmetic,
//! interesting constants, block copies and deletions. It is AFL's havoc stage,
//! and it is a reasonable default for a target with no structure worth
//! respecting.
//!
//! Every edit is also exported on its own, so a harness that knows its format
//! can pick — flip bits in a header, splice blocks in a body — instead of
//! taking the stack whole.
//!
//! These are plain functions over a buffer. Nothing here talks to a subsystem,
//! and a component that does not call them links none of it.
//!
//! # Examples
//!
//! ```ignore
//! #[fuzz(case_start)]
//! fn start(&mut self, t: &mut Control) {
//!     // Seed from the run's own stream, so --seed still reproduces the run.
//!     self.rng = Rng::from_seed(t.subs.fuzz.rand());
//! }
//!
//! #[fuzz(mutate)]
//! fn mutate(&mut self, _t: &mut Control, input: &mut Input) {
//!     havoc(input, &mut self.rng);
//! }
//! ```

use crate::fuzz::Input;

/// xoshiro256\*\*, for drawing without a call into the subsystem per word.
///
/// Seed it from `FuzzRef::rand` and every draw still descends from the run's
/// `--seed`, so the run reproduces. Seed it from anything else and it does not.
pub struct Rng([u64; 4]);

/// One 64-bit word of splitmix64, which is what expands a seed into a state.
fn splitmix64(z: &mut u64) -> u64 {
    *z = z.wrapping_add(0x9e37_79b9_7f4a_7c15);
    let mut x = *z;
    x = (x ^ (x >> 30)).wrapping_mul(0xbf58_476d_1ce4_e5b9);
    x = (x ^ (x >> 27)).wrapping_mul(0x94d0_49bb_1331_11eb);
    x ^ (x >> 31)
}

impl Rng {
    /// Expand one word into a generator state. The same `seed` always gives the
    /// same sequence.
    pub fn from_seed(seed: u64) -> Rng {
        let mut z = seed;
        Rng([
            splitmix64(&mut z),
            splitmix64(&mut z),
            splitmix64(&mut z),
            splitmix64(&mut z),
        ])
    }

    /// The next word in the sequence.
    pub fn next_u64(&mut self) -> u64 {
        let s = &mut self.0;
        let out = s[1].wrapping_mul(5).rotate_left(7).wrapping_mul(9);
        let t = s[1] << 17;
        s[2] ^= s[0];
        s[3] ^= s[1];
        s[1] ^= s[2];
        s[0] ^= s[3];
        s[2] ^= t;
        s[3] = s[3].rotate_left(45);
        out
    }

    /// A draw in `0..n`, and 0 when `n` is 0 — a draw from nothing is not an
    /// error.
    ///
    /// Reduced with a modulo, so the low values are very slightly likelier for
    /// an `n` that is not a power of two. That does not matter for choosing an
    /// offset in a buffer; it would for anything measuring a distribution.
    pub fn below(&mut self, n: u64) -> u64 {
        if n == 0 { 0 } else { self.next_u64() % n }
    }

    /// One element of `xs`, or `None` for an empty slice.
    pub fn pick<'a, T>(&mut self, xs: &'a [T]) -> Option<&'a T> {
        xs.get(self.below(xs.len() as u64) as usize)
    }
}

/// The values an off-by-one lands on: type bounds, sign flips, and the powers
/// of two around them. AFL's table.
const INTERESTING_8: &[i8] = &[-128, -1, 0, 1, 16, 32, 64, 100, 127];
const INTERESTING_16: &[i16] = &[-32768, -129, 128, 255, 256, 512, 1000, 1024, 4096, 32767];
const INTERESTING_32: &[i32] = &[
    -2147483648,
    -100663046,
    -32769,
    32768,
    65535,
    65536,
    2147483647,
];
/// How much an arithmetic edit may add or subtract, either way.
const ARITH_MAX: u64 = 35;
/// The most stacked edits one havoc pass makes; the least is one.
const HAVOC_STACK: u64 = 8;

/// One havoc pass: between one and eight edits, stacked on top of each other,
/// each drawn at random from the ten below.
///
/// Grows the case up to its capacity and never past it. Does nothing useful on
/// an empty case — most of the edits need a byte to work on — so plant a seed
/// input before the first pass.
pub fn havoc(input: &mut Input, rng: &mut Rng) {
    let edits: &[fn(&mut Input, &mut Rng)] = &[
        bit_flip,
        byte_flip,
        arith8,
        arith16,
        arith32,
        interesting8,
        interesting16,
        interesting32,
        block_dup,
        block_del,
    ];
    for _ in 0..=rng.below(HAVOC_STACK) {
        if let Some(edit) = rng.pick(edits) {
            edit(input, rng);
        }
    }
}

/// Flip one bit, anywhere in the case. A no-op on an empty case.
pub fn bit_flip(input: &mut Input, rng: &mut Rng) {
    let bits = input.len() * 8;
    if bits == 0 {
        return;
    }
    let at = rng.below(bits);
    let (byte, bit) = ((at / 8) as usize, at % 8);
    input.as_mut_slice()[byte] ^= 1 << bit;
}

/// XOR one byte with a random value, so several bits move at once. A no-op on
/// an empty case.
pub fn byte_flip(input: &mut Input, rng: &mut Rng) {
    let Some(at) = offset(input, rng, 1) else {
        return;
    };
    let v = rng.next_u64() as u8;
    input.as_mut_slice()[at] ^= v;
}

/// Add or subtract 1 to 35 at some byte, wrapping.
///
/// The edit that walks a length or an index just past a bound, which a bit flip
/// rarely does. A no-op on an empty case.
pub fn arith8(input: &mut Input, rng: &mut Rng) {
    let Some(at) = offset(input, rng, 1) else {
        return;
    };
    let delta = delta(rng) as u8;
    let buf = input.as_mut_slice();
    buf[at] = buf[at].wrapping_add(delta);
}

/// [`arith8`] over a little-endian `u16`. A no-op on a case under two bytes.
pub fn arith16(input: &mut Input, rng: &mut Rng) {
    let Some(at) = offset(input, rng, 2) else {
        return;
    };
    let buf = input.as_mut_slice();
    let old = u16::from_le_bytes([buf[at], buf[at + 1]]);
    let new = old.wrapping_add(delta(rng) as u16);
    buf[at..at + 2].copy_from_slice(&new.to_le_bytes());
}

/// [`arith8`] over a little-endian `u32`. A no-op on a case under four bytes.
pub fn arith32(input: &mut Input, rng: &mut Rng) {
    let Some(at) = offset(input, rng, 4) else {
        return;
    };
    let buf = input.as_mut_slice();
    let old = u32::from_le_bytes([buf[at], buf[at + 1], buf[at + 2], buf[at + 3]]);
    let new = old.wrapping_add(delta(rng) as u32);
    buf[at..at + 4].copy_from_slice(&new.to_le_bytes());
}

/// Overwrite one byte with a value from the table above — 0, 1, -1, 127, and so
/// on. A no-op on an empty case.
pub fn interesting8(input: &mut Input, rng: &mut Rng) {
    let (Some(at), Some(v)) = (offset(input, rng, 1), rng.pick(INTERESTING_8)) else {
        return;
    };
    input.as_mut_slice()[at] = *v as u8;
}

/// [`interesting8`] over a little-endian `u16`. A no-op on a case under two
/// bytes.
pub fn interesting16(input: &mut Input, rng: &mut Rng) {
    let (Some(at), Some(v)) = (offset(input, rng, 2), rng.pick(INTERESTING_16).copied()) else {
        return;
    };
    input.as_mut_slice()[at..at + 2].copy_from_slice(&(v as u16).to_le_bytes());
}

/// [`interesting8`] over a little-endian `u32`. A no-op on a case under four
/// bytes.
pub fn interesting32(input: &mut Input, rng: &mut Rng) {
    let (Some(at), Some(v)) = (offset(input, rng, 4), rng.pick(INTERESTING_32).copied()) else {
        return;
    };
    input.as_mut_slice()[at..at + 4].copy_from_slice(&(v as u32).to_le_bytes());
}

/// Copy one run of bytes over another place in the same case.
///
/// Lengthens the case when the copy runs off the end and there is capacity for
/// it, and is cut short at capacity when there is not. A no-op on an empty
/// case.
pub fn block_dup(input: &mut Input, rng: &mut Rng) {
    let len = input.len();
    if len == 0 {
        return;
    }
    let from = rng.below(len) as usize;
    let n = (rng.below(len - from as u64) + 1) as usize;
    let to = rng.below(len) as usize;
    let block: Vec<u8> = input.as_slice()[from..from + n].to_vec();
    let room = (input.cap() as usize).saturating_sub(to);
    let n = n.min(room);
    if to + n > len as usize {
        input.set_len((to + n) as u64);
    }
    input.as_mut_slice()[to..to + n].copy_from_slice(&block[..n]);
}

/// Cut one run of bytes out: the tail slides down and the case shortens. A
/// no-op on a case under two bytes.
pub fn block_del(input: &mut Input, rng: &mut Rng) {
    let len = input.len() as usize;
    if len < 2 {
        return;
    }
    let at = rng.below(len as u64 - 1) as usize;
    let n = (rng.below((len - at) as u64) + 1) as usize;
    input.as_mut_slice().copy_within(at + n.., at);
    input.set_len((len - n) as u64);
}

/// A random offset that `width` bytes fit at, or `None` when the case is
/// shorter than one field.
fn offset(input: &Input, rng: &mut Rng, width: u64) -> Option<usize> {
    let len = input.len();
    (len >= width).then(|| rng.below(len - width + 1) as usize)
}

/// `+/- ARITH_MAX`, never zero: an edit that changes nothing is a wasted case.
fn delta(rng: &mut Rng) -> i64 {
    let n = (rng.below(ARITH_MAX) + 1) as i64;
    if rng.next_u64() & 1 == 0 { n } else { -n }
}