use std::collections::HashMap;
use crate::rng::Rng;
use crate::writer::{Field, with_fields};
pub const SEED: u64 = 0x6733_6200_5031_0001;
pub const RANDOM_PER_INPUT: usize = 80;
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct Mutant {
pub label: String,
pub bytes: Vec<u8>,
}
pub type Outputs = Vec<(String, Vec<u8>)>;
fn fnv1a(name: &[u8]) -> u64 {
name.iter().fold(0xcbf2_9ce4_8422_2325, |h, b| {
(h ^ u64::from(*b)).wrapping_mul(0x0000_0100_0000_01B3)
})
}
fn mask(f: &Field) -> u64 {
if f.width >= 8 {
u64::MAX
} else {
(1u64 << (8 * f.width)) - 1
}
}
fn pairs(width: usize) -> ([u64; 2], [u64; 2]) {
if width == 4 {
([0xFFFF_FFFF, 0x8000_0000], [0x7FFF_FFFF, 1 << 30])
} else {
([u64::MAX, 1 << 63], [i64::MAX.unsigned_abs(), 1 << 40])
}
}
fn parallel<J: Sync, R: Send>(
jobs: &[J],
threads: usize,
run: &(dyn Fn(&J) -> R + Sync),
) -> Vec<R> {
let threads = threads.clamp(1, jobs.len().max(1));
if threads == 1 {
return jobs.iter().map(run).collect();
}
let mut all: Vec<(usize, R)> = Vec::with_capacity(jobs.len());
std::thread::scope(|s| {
let handles: Vec<_> = (0..threads)
.map(|t| {
s.spawn(move || {
jobs.iter()
.enumerate()
.skip(t)
.step_by(threads)
.map(|(i, j)| (i, run(j)))
.collect::<Vec<_>>()
})
})
.collect();
for h in handles {
match h.join() {
Ok(part) => all.extend(part),
Err(e) => std::panic::resume_unwind(e),
}
}
});
all.sort_by_key(|(i, _)| *i);
all.into_iter().map(|(_, r)| r).collect()
}
fn rebuild(
build: &(dyn Fn() -> Outputs + Sync),
overrides: &[(usize, u64)],
) -> HashMap<String, Vec<u8>> {
with_fields(overrides, build).0.into_iter().collect()
}
struct Planned {
output: usize,
field: usize,
value: u64,
label: String,
}
#[must_use]
pub fn mutants_of(
build: &(dyn Fn() -> Outputs + Sync),
threads: usize,
) -> Vec<(String, Vec<Mutant>)> {
let (base, fields) = with_fields(&[], build);
let ids: Vec<usize> = (0..fields.len()).collect();
let owners: Vec<Vec<usize>> = parallel(&ids, threads, &|k| {
let f = &fields[*k];
let again = rebuild(build, &[(*k, !f.value & mask(f))]);
base.iter()
.enumerate()
.filter(|(_, (name, bytes))| again.get(name).is_some_and(|b| b != bytes))
.map(|(o, _)| o)
.collect()
});
let mut own: Vec<Vec<usize>> = vec![Vec::new(); base.len()];
for (k, os) in owners.iter().enumerate() {
for o in os {
own[*o].push(k);
}
}
let mut rngs: Vec<Rng> = base
.iter()
.map(|(name, _)| Rng::new(SEED ^ fnv1a(name.as_bytes())))
.collect();
let mut planned: Vec<Vec<Planned>> = Vec::with_capacity(base.len());
for (o, ks) in own.iter().enumerate() {
let mut row = Vec::with_capacity(2 * ks.len());
for (i, k) in ks.iter().enumerate() {
let f = &fields[*k];
let end = if f.big_endian { "be" } else { "le" };
let (neg, huge) = pairs(f.width);
for (tag, pair) in [("n", neg), ("h", huge)] {
let pick = rngs[o].below(2);
let value = if pair[pick] == f.value {
pair[1 - pick]
} else {
pair[pick]
};
row.push(Planned {
output: o,
field: *k,
value,
label: format!("f{i}.{end}{}{tag}", f.width),
});
}
}
planned.push(row);
}
let rounds = planned.iter().map(Vec::len).max().unwrap_or(0);
let mut batches: Vec<Vec<&Planned>> = (0..rounds)
.map(|r| {
planned
.iter()
.filter_map(|row| row.get(r))
.filter(|p| owners[p.field].len() == 1)
.collect()
})
.collect();
batches.extend(
planned
.iter()
.flatten()
.filter(|p| owners[p.field].len() > 1)
.map(|p| vec![p]),
);
let made: Vec<Vec<(usize, usize, Mutant)>> = parallel(&batches, threads, &|batch| {
make(build, &base, &fields, &planned, batch)
});
let mut by_output: Vec<Vec<(usize, Mutant)>> = vec![Vec::new(); base.len()];
for (o, order, m) in made.into_iter().flatten() {
by_output[o].push((order, m));
}
base.into_iter()
.zip(by_output)
.zip(rngs.iter_mut())
.map(|(((name, data), mut fm), rng)| {
fm.sort_by_key(|(order, _)| *order);
let mut out: Vec<Mutant> = fm.into_iter().map(|(_, m)| m).collect();
out.extend(random_mutants(&data, rng));
(name, out)
})
.collect()
}
fn make(
build: &(dyn Fn() -> Outputs + Sync),
base: &Outputs,
fields: &[Field],
planned: &[Vec<Planned>],
batch: &[&Planned],
) -> Vec<(usize, usize, Mutant)> {
let overrides: Vec<(usize, u64)> = batch.iter().map(|p| (p.field, p.value)).collect();
let (outputs, written) = with_fields(&overrides, build);
let shape = |f: &Field| (f.width, f.big_endian);
let numbered = written.len() == fields.len()
&& written.iter().map(shape).eq(fields.iter().map(shape))
&& batch
.iter()
.all(|p| written.get(p.field) == fields.get(p.field));
if batch.len() > 1 && !numbered {
return batch
.iter()
.flat_map(|p| make(build, base, fields, planned, &[*p]))
.collect();
}
let again: HashMap<String, Vec<u8>> = outputs.into_iter().collect();
batch
.iter()
.filter_map(|p| {
let (name, bytes) = &base[p.output];
let got = again.get(name).filter(|b| *b != bytes)?;
let order = planned[p.output].iter().position(|q| q.label == p.label)?;
Some((
p.output,
order,
Mutant {
label: p.label.clone(),
bytes: got.clone(),
},
))
})
.collect()
}
fn random_mutants(data: &[u8], rng: &mut Rng) -> Vec<Mutant> {
let mut out = Vec::with_capacity(RANDOM_PER_INPUT);
let mut flip = true;
while out.len() < RANDOM_PER_INPUT && !data.is_empty() {
let mut bytes = data.to_vec();
let label = if flip {
let bits = 1 + rng.below(8);
rng.flip_bits(&mut bytes, bits);
while bytes == data {
rng.flip_bits(&mut bytes, 1);
}
format!("b{bits}")
} else {
let n = rng.below(data.len());
bytes.truncate(n);
format!("t{n}")
};
flip = !flip;
out.push(Mutant { label, bytes });
}
out
}
#[must_use]
pub fn builder_outputs() -> Outputs {
let mut out = crate::bundle::matrix();
for (scene, s) in every_scene() {
for (name, bytes) in s.files.into_iter().chain(s.resolver) {
if is_web_file(&bytes) {
continue;
}
let name = String::from_utf8_lossy(&name).replace('/', "_");
out.push((format!("scene-{scene}-{name}"), bytes));
}
}
out
}
fn every_scene() -> Vec<(&'static str, crate::env::Scene)> {
let dependency = crate::env::dependency_scenes()
.into_iter()
.map(|(scene, d)| (scene, d.scene));
let find = crate::env::find_scenes()
.into_iter()
.map(|(scene, f)| (scene, f.scene));
let race = crate::env::race_scenes().into_iter().map(|(scene, r)| {
let mut s = r.scene;
s.files.push(r.other);
(scene, s)
});
crate::env::scenes()
.into_iter()
.chain(dependency)
.chain(find)
.chain(race)
.collect()
}
#[must_use]
pub fn is_web_file(bytes: &[u8]) -> bool {
bytes.starts_with(b"UnityWebData") || bytes.starts_with(b"TuanjieWebData")
}
#[must_use]
pub fn gate_mutants(threads: usize) -> Vec<(String, Vec<Mutant>)> {
mutants_of(&builder_outputs, threads)
}
#[cfg(test)]
mod tests {
use super::{Outputs, RANDOM_PER_INPUT, builder_outputs, mutants_of};
use crate::bundle::{TestCodec, compress};
use crate::writer::{ByteWriter, with_fields};
fn body(count: u32) -> Vec<u8> {
let mut w = ByteWriter::le();
w.u32(count)
.u16(0xAAAA)
.set_big_endian(true)
.u64(3)
.bytes(b"xyz");
w.into_inner()
}
fn small() -> Outputs {
let plain = body(0);
let packed = compress(TestCodec::Lz4, &body(3));
let mut w = ByteWriter::be();
w.u32(u32::try_from(packed.len()).unwrap()).bytes(&packed);
let wrapped = w.into_inner();
let only_its_length = body(9).len();
vec![
("plain".into(), plain),
("wrapped".into(), wrapped),
("sized".into(), vec![0; only_its_length]),
]
}
#[test]
fn every_field_of_every_output_is_set_negative_and_huge() {
let all = mutants_of(&small, 1);
let names: Vec<&str> = all.iter().map(|(n, _)| n.as_str()).collect();
assert_eq!(names, ["plain", "wrapped", "sized"]);
let labels = |o: usize| -> Vec<&str> {
all[o]
.1
.iter()
.filter(|m| m.label.starts_with('f'))
.map(|m| m.label.as_str())
.collect()
};
assert_eq!(labels(0), ["f0.le4n", "f0.le4h", "f1.be8n", "f1.be8h"]);
assert_eq!(
labels(1),
[
"f0.le4n", "f0.le4h", "f1.be8n", "f1.be8h", "f2.be4n", "f2.be4h"
]
);
assert_eq!(labels(2), Vec::<&str>::new());
let base = small();
let m = &all[0].1[0];
assert!(
[[0xFF; 4], [0, 0, 0, 0x80]].contains(&<[u8; 4]>::try_from(&m.bytes[..4]).unwrap())
);
assert_eq!(m.bytes[4..], base[0].1[4..]);
let w = &all[1].1[1];
let size = usize::try_from(u32::from_be_bytes(w.bytes[..4].try_into().unwrap())).unwrap();
let inner = lz4_flex::block::decompress(&w.bytes[4..4 + size], 17).unwrap();
let count = u32::from_le_bytes(inner[..4].try_into().unwrap());
assert!([0x7FFF_FFFF, 1 << 30].contains(&count), "{count:#x}");
assert_eq!(inner[4..], body(3)[4..]);
for (_, ms) in &all {
let random = ms.iter().filter(|m| !m.label.starts_with('f')).count();
assert_eq!(random, RANDOM_PER_INPUT);
}
}
fn renumbering() -> Outputs {
let mut counts = ByteWriter::le();
for _ in 0..16 {
counts.u32(0);
}
let packed = compress(TestCodec::Lz4, &counts.into_inner());
let mut per_byte = ByteWriter::le();
for _ in 0..packed.len() {
per_byte.u32(1);
}
let mut second = ByteWriter::le();
second.u32(2).u32(3);
vec![
("first".into(), [packed, per_byte.into_inner()].concat()),
("second".into(), second.into_inner()),
]
}
#[test]
fn a_field_that_renumbers_later_fields_is_replaced_alone() {
let base = renumbering();
let all = mutants_of(&renumbering, 1);
let fields = |o: usize| all[o].1.iter().filter(|m| m.label.starts_with('f'));
let second: Vec<&str> = fields(1).map(|m| m.label.as_str()).collect();
assert_eq!(second, ["f0.le4n", "f0.le4h", "f1.le4n", "f1.le4h"]);
for m in fields(1) {
let at = if m.label.starts_with("f0") { 0 } else { 4 };
let keep = 4 - at;
assert_eq!(
m.bytes[keep..keep + 4],
base[1].1[keep..keep + 4],
"{}",
m.label
);
assert_ne!(m.bytes[at..at + 4], base[1].1[at..at + 4], "{}", m.label);
}
let (_, written) = with_fields(&[], renumbering);
assert_eq!(fields(0).count(), 2 * (written.len() - 2));
}
#[test]
fn the_mutants_do_not_depend_on_the_threads() {
assert_eq!(mutants_of(&small, 1), mutants_of(&small, 3));
}
#[test]
fn the_gate_mutates_every_field_of_its_outputs() {
let inputs = builder_outputs();
assert!(inputs.len() > 98, "{}", inputs.len());
let mut names: Vec<&String> = inputs.iter().map(|(n, _)| n).collect();
names.sort();
names.dedup();
assert_eq!(names.len(), inputs.len(), "names repeat");
assert_eq!(
with_fields(&[], builder_outputs),
with_fields(&[], builder_outputs)
);
let all = super::gate_mutants(4);
assert_eq!(all.len(), inputs.len());
let mut no_field = Vec::new();
for ((name, data), (n, ms)) in inputs.iter().zip(&all) {
assert_eq!(name, n);
assert!(
ms.iter().all(|m| m.bytes != *data),
"{name}: a mutant is its input"
);
let fields = ms.iter().filter(|m| m.label.starts_with('f')).count();
assert_eq!(fields % 2, 0, "{name}: {fields} field mutants");
if fields == 0 {
no_field.push(name.as_str());
}
assert_eq!(ms.len(), fields + RANDOM_PER_INPUT, "{name}");
}
assert_eq!(
no_field,
[
"scene-resolver_loads-CAB-H2.resS",
"scene-find_file_kinds-top.resS",
"scene-find_file_kinds-r.resS",
"scene-find_file_listing-x.resS"
]
);
}
#[test]
fn every_file_of_every_scene_is_an_output() {
type Files = Vec<(Vec<u8>, Vec<u8>)>;
fn files(s: crate::env::Scene) -> Files {
s.files.into_iter().chain(s.resolver).collect()
}
let inputs = builder_outputs();
let lists: [(&str, Vec<(&str, Files)>); 4] = [
(
"scenes",
crate::env::scenes()
.into_iter()
.map(|(scene, s)| (scene, files(s)))
.collect(),
),
(
"dependency_scenes",
crate::env::dependency_scenes()
.into_iter()
.map(|(scene, d)| (scene, files(d.scene)))
.collect(),
),
(
"find_scenes",
crate::env::find_scenes()
.into_iter()
.map(|(scene, f)| (scene, files(f.scene)))
.collect(),
),
(
"race_scenes",
crate::env::race_scenes()
.into_iter()
.map(|(scene, r)| {
let mut all = files(r.scene);
all.push(r.other);
(scene, all)
})
.collect(),
),
];
let (mut count, mut web) = (0, Vec::new());
for (list, scenes) in lists {
assert_ne!(scenes.len(), 0, "{list}");
for (scene, files) in scenes {
for (name, bytes) in files {
let name = String::from_utf8_lossy(&name).replace('/', "_");
let name = format!("scene-{scene}-{name}");
if super::is_web_file(&bytes) {
web.push(name);
continue;
}
assert!(
inputs.iter().any(|(n, b)| *n == name && *b == bytes),
"{list}: {name} is no output"
);
count += 1;
}
}
}
assert_eq!(web, ["scene-find_file_kinds-w.web"]);
assert_eq!(inputs.len(), crate::bundle::matrix().len() + count);
}
}