1use std::collections::HashMap;
27
28use crate::rng::Rng;
29use crate::writer::{Field, with_fields};
30
31pub const SEED: u64 = 0x6733_6200_5031_0001;
33
34pub const RANDOM_PER_INPUT: usize = 80;
36
37#[derive(Clone, Debug, PartialEq, Eq)]
39pub struct Mutant {
40 pub label: String,
42 pub bytes: Vec<u8>,
44}
45
46pub type Outputs = Vec<(String, Vec<u8>)>;
48
49fn fnv1a(name: &[u8]) -> u64 {
50 name.iter().fold(0xcbf2_9ce4_8422_2325, |h, b| {
51 (h ^ u64::from(*b)).wrapping_mul(0x0000_0100_0000_01B3)
52 })
53}
54
55fn mask(f: &Field) -> u64 {
57 if f.width >= 8 {
58 u64::MAX
59 } else {
60 (1u64 << (8 * f.width)) - 1
61 }
62}
63
64fn pairs(width: usize) -> ([u64; 2], [u64; 2]) {
66 if width == 4 {
67 ([0xFFFF_FFFF, 0x8000_0000], [0x7FFF_FFFF, 1 << 30])
68 } else {
69 ([u64::MAX, 1 << 63], [i64::MAX.unsigned_abs(), 1 << 40])
70 }
71}
72
73fn parallel<J: Sync, R: Send>(
75 jobs: &[J],
76 threads: usize,
77 run: &(dyn Fn(&J) -> R + Sync),
78) -> Vec<R> {
79 let threads = threads.clamp(1, jobs.len().max(1));
80 if threads == 1 {
81 return jobs.iter().map(run).collect();
82 }
83 let mut all: Vec<(usize, R)> = Vec::with_capacity(jobs.len());
84 std::thread::scope(|s| {
85 let handles: Vec<_> = (0..threads)
86 .map(|t| {
87 s.spawn(move || {
88 jobs.iter()
89 .enumerate()
90 .skip(t)
91 .step_by(threads)
92 .map(|(i, j)| (i, run(j)))
93 .collect::<Vec<_>>()
94 })
95 })
96 .collect();
97 for h in handles {
98 match h.join() {
100 Ok(part) => all.extend(part),
101 Err(e) => std::panic::resume_unwind(e),
102 }
103 }
104 });
105 all.sort_by_key(|(i, _)| *i);
106 all.into_iter().map(|(_, r)| r).collect()
107}
108
109fn rebuild(
111 build: &(dyn Fn() -> Outputs + Sync),
112 overrides: &[(usize, u64)],
113) -> HashMap<String, Vec<u8>> {
114 with_fields(overrides, build).0.into_iter().collect()
115}
116
117struct Planned {
119 output: usize,
120 field: usize,
121 value: u64,
122 label: String,
123}
124
125#[must_use]
129pub fn mutants_of(
130 build: &(dyn Fn() -> Outputs + Sync),
131 threads: usize,
132) -> Vec<(String, Vec<Mutant>)> {
133 let (base, fields) = with_fields(&[], build);
134 let ids: Vec<usize> = (0..fields.len()).collect();
137 let owners: Vec<Vec<usize>> = parallel(&ids, threads, &|k| {
138 let f = &fields[*k];
139 let again = rebuild(build, &[(*k, !f.value & mask(f))]);
140 base.iter()
141 .enumerate()
142 .filter(|(_, (name, bytes))| again.get(name).is_some_and(|b| b != bytes))
143 .map(|(o, _)| o)
144 .collect()
145 });
146 let mut own: Vec<Vec<usize>> = vec![Vec::new(); base.len()];
147 for (k, os) in owners.iter().enumerate() {
148 for o in os {
149 own[*o].push(k);
150 }
151 }
152 let mut rngs: Vec<Rng> = base
155 .iter()
156 .map(|(name, _)| Rng::new(SEED ^ fnv1a(name.as_bytes())))
157 .collect();
158 let mut planned: Vec<Vec<Planned>> = Vec::with_capacity(base.len());
159 for (o, ks) in own.iter().enumerate() {
160 let mut row = Vec::with_capacity(2 * ks.len());
161 for (i, k) in ks.iter().enumerate() {
162 let f = &fields[*k];
163 let end = if f.big_endian { "be" } else { "le" };
164 let (neg, huge) = pairs(f.width);
165 for (tag, pair) in [("n", neg), ("h", huge)] {
166 let pick = rngs[o].below(2);
167 let value = if pair[pick] == f.value {
169 pair[1 - pick]
170 } else {
171 pair[pick]
172 };
173 row.push(Planned {
174 output: o,
175 field: *k,
176 value,
177 label: format!("f{i}.{end}{}{tag}", f.width),
178 });
179 }
180 }
181 planned.push(row);
182 }
183 let rounds = planned.iter().map(Vec::len).max().unwrap_or(0);
187 let mut batches: Vec<Vec<&Planned>> = (0..rounds)
188 .map(|r| {
189 planned
190 .iter()
191 .filter_map(|row| row.get(r))
192 .filter(|p| owners[p.field].len() == 1)
193 .collect()
194 })
195 .collect();
196 batches.extend(
197 planned
198 .iter()
199 .flatten()
200 .filter(|p| owners[p.field].len() > 1)
201 .map(|p| vec![p]),
202 );
203 let made: Vec<Vec<(usize, usize, Mutant)>> = parallel(&batches, threads, &|batch| {
204 make(build, &base, &fields, &planned, batch)
205 });
206 let mut by_output: Vec<Vec<(usize, Mutant)>> = vec![Vec::new(); base.len()];
207 for (o, order, m) in made.into_iter().flatten() {
208 by_output[o].push((order, m));
209 }
210 base.into_iter()
211 .zip(by_output)
212 .zip(rngs.iter_mut())
213 .map(|(((name, data), mut fm), rng)| {
214 fm.sort_by_key(|(order, _)| *order);
215 let mut out: Vec<Mutant> = fm.into_iter().map(|(_, m)| m).collect();
216 out.extend(random_mutants(&data, rng));
217 (name, out)
218 })
219 .collect()
220}
221
222fn make(
231 build: &(dyn Fn() -> Outputs + Sync),
232 base: &Outputs,
233 fields: &[Field],
234 planned: &[Vec<Planned>],
235 batch: &[&Planned],
236) -> Vec<(usize, usize, Mutant)> {
237 let overrides: Vec<(usize, u64)> = batch.iter().map(|p| (p.field, p.value)).collect();
238 let (outputs, written) = with_fields(&overrides, build);
239 let shape = |f: &Field| (f.width, f.big_endian);
240 let numbered = written.len() == fields.len()
241 && written.iter().map(shape).eq(fields.iter().map(shape))
242 && batch
243 .iter()
244 .all(|p| written.get(p.field) == fields.get(p.field));
245 if batch.len() > 1 && !numbered {
246 return batch
247 .iter()
248 .flat_map(|p| make(build, base, fields, planned, &[*p]))
249 .collect();
250 }
251 let again: HashMap<String, Vec<u8>> = outputs.into_iter().collect();
252 batch
253 .iter()
254 .filter_map(|p| {
255 let (name, bytes) = &base[p.output];
256 let got = again.get(name).filter(|b| *b != bytes)?;
258 let order = planned[p.output].iter().position(|q| q.label == p.label)?;
259 Some((
260 p.output,
261 order,
262 Mutant {
263 label: p.label.clone(),
264 bytes: got.clone(),
265 },
266 ))
267 })
268 .collect()
269}
270
271fn random_mutants(data: &[u8], rng: &mut Rng) -> Vec<Mutant> {
273 let mut out = Vec::with_capacity(RANDOM_PER_INPUT);
274 let mut flip = true;
275 while out.len() < RANDOM_PER_INPUT && !data.is_empty() {
276 let mut bytes = data.to_vec();
277 let label = if flip {
278 let bits = 1 + rng.below(8);
279 rng.flip_bits(&mut bytes, bits);
280 while bytes == data {
282 rng.flip_bits(&mut bytes, 1);
283 }
284 format!("b{bits}")
285 } else {
286 let n = rng.below(data.len());
287 bytes.truncate(n);
288 format!("t{n}")
289 };
290 flip = !flip;
291 out.push(Mutant { label, bytes });
292 }
293 out
294}
295
296#[must_use]
306pub fn builder_outputs() -> Outputs {
307 let mut out = crate::bundle::matrix();
308 for (scene, s) in every_scene() {
309 for (name, bytes) in s.files.into_iter().chain(s.resolver) {
310 if is_web_file(&bytes) {
311 continue;
312 }
313 let name = String::from_utf8_lossy(&name).replace('/', "_");
314 out.push((format!("scene-{scene}-{name}"), bytes));
315 }
316 }
317 out
318}
319
320fn every_scene() -> Vec<(&'static str, crate::env::Scene)> {
323 let dependency = crate::env::dependency_scenes()
324 .into_iter()
325 .map(|(scene, d)| (scene, d.scene));
326 let find = crate::env::find_scenes()
327 .into_iter()
328 .map(|(scene, f)| (scene, f.scene));
329 let race = crate::env::race_scenes().into_iter().map(|(scene, r)| {
330 let mut s = r.scene;
331 s.files.push(r.other);
332 (scene, s)
333 });
334 crate::env::scenes()
335 .into_iter()
336 .chain(dependency)
337 .chain(find)
338 .chain(race)
339 .collect()
340}
341
342#[must_use]
346pub fn is_web_file(bytes: &[u8]) -> bool {
347 bytes.starts_with(b"UnityWebData") || bytes.starts_with(b"TuanjieWebData")
348}
349
350#[must_use]
352pub fn gate_mutants(threads: usize) -> Vec<(String, Vec<Mutant>)> {
353 mutants_of(&builder_outputs, threads)
354}
355
356#[cfg(test)]
357mod tests {
358 use super::{Outputs, RANDOM_PER_INPUT, builder_outputs, mutants_of};
359 use crate::bundle::{TestCodec, compress};
360 use crate::writer::{ByteWriter, with_fields};
361
362 fn body(count: u32) -> Vec<u8> {
364 let mut w = ByteWriter::le();
365 w.u32(count)
366 .u16(0xAAAA)
367 .set_big_endian(true)
368 .u64(3)
369 .bytes(b"xyz");
370 w.into_inner()
371 }
372
373 fn small() -> Outputs {
376 let plain = body(0);
377 let packed = compress(TestCodec::Lz4, &body(3));
378 let mut w = ByteWriter::be();
379 w.u32(u32::try_from(packed.len()).unwrap()).bytes(&packed);
380 let wrapped = w.into_inner();
381 let only_its_length = body(9).len();
382 vec![
383 ("plain".into(), plain),
384 ("wrapped".into(), wrapped),
385 ("sized".into(), vec![0; only_its_length]),
386 ]
387 }
388
389 #[test]
390 fn every_field_of_every_output_is_set_negative_and_huge() {
391 let all = mutants_of(&small, 1);
392 let names: Vec<&str> = all.iter().map(|(n, _)| n.as_str()).collect();
393 assert_eq!(names, ["plain", "wrapped", "sized"]);
394 let labels = |o: usize| -> Vec<&str> {
395 all[o]
396 .1
397 .iter()
398 .filter(|m| m.label.starts_with('f'))
399 .map(|m| m.label.as_str())
400 .collect()
401 };
402 assert_eq!(labels(0), ["f0.le4n", "f0.le4h", "f1.be8n", "f1.be8h"]);
404 assert_eq!(
406 labels(1),
407 [
408 "f0.le4n", "f0.le4h", "f1.be8n", "f1.be8h", "f2.be4n", "f2.be4h"
409 ]
410 );
411 assert_eq!(labels(2), Vec::<&str>::new());
413 let base = small();
415 let m = &all[0].1[0];
416 assert!(
417 [[0xFF; 4], [0, 0, 0, 0x80]].contains(&<[u8; 4]>::try_from(&m.bytes[..4]).unwrap())
418 );
419 assert_eq!(m.bytes[4..], base[0].1[4..]);
420 let w = &all[1].1[1];
422 let size = usize::try_from(u32::from_be_bytes(w.bytes[..4].try_into().unwrap())).unwrap();
423 let inner = lz4_flex::block::decompress(&w.bytes[4..4 + size], 17).unwrap();
424 let count = u32::from_le_bytes(inner[..4].try_into().unwrap());
425 assert!([0x7FFF_FFFF, 1 << 30].contains(&count), "{count:#x}");
426 assert_eq!(inner[4..], body(3)[4..]);
427 for (_, ms) in &all {
429 let random = ms.iter().filter(|m| !m.label.starts_with('f')).count();
430 assert_eq!(random, RANDOM_PER_INPUT);
431 }
432 }
433
434 fn renumbering() -> Outputs {
439 let mut counts = ByteWriter::le();
440 for _ in 0..16 {
441 counts.u32(0);
442 }
443 let packed = compress(TestCodec::Lz4, &counts.into_inner());
444 let mut per_byte = ByteWriter::le();
445 for _ in 0..packed.len() {
446 per_byte.u32(1);
447 }
448 let mut second = ByteWriter::le();
449 second.u32(2).u32(3);
450 vec![
451 ("first".into(), [packed, per_byte.into_inner()].concat()),
452 ("second".into(), second.into_inner()),
453 ]
454 }
455
456 #[test]
461 fn a_field_that_renumbers_later_fields_is_replaced_alone() {
462 let base = renumbering();
463 let all = mutants_of(&renumbering, 1);
464 let fields = |o: usize| all[o].1.iter().filter(|m| m.label.starts_with('f'));
465 let second: Vec<&str> = fields(1).map(|m| m.label.as_str()).collect();
466 assert_eq!(second, ["f0.le4n", "f0.le4h", "f1.le4n", "f1.le4h"]);
467 for m in fields(1) {
468 let at = if m.label.starts_with("f0") { 0 } else { 4 };
470 let keep = 4 - at;
471 assert_eq!(
472 m.bytes[keep..keep + 4],
473 base[1].1[keep..keep + 4],
474 "{}",
475 m.label
476 );
477 assert_ne!(m.bytes[at..at + 4], base[1].1[at..at + 4], "{}", m.label);
478 }
479 let (_, written) = with_fields(&[], renumbering);
480 assert_eq!(fields(0).count(), 2 * (written.len() - 2));
481 }
482
483 #[test]
484 fn the_mutants_do_not_depend_on_the_threads() {
485 assert_eq!(mutants_of(&small, 1), mutants_of(&small, 3));
486 }
487
488 #[test]
489 fn the_gate_mutates_every_field_of_its_outputs() {
490 let inputs = builder_outputs();
491 assert!(inputs.len() > 98, "{}", inputs.len());
492 let mut names: Vec<&String> = inputs.iter().map(|(n, _)| n).collect();
493 names.sort();
494 names.dedup();
495 assert_eq!(names.len(), inputs.len(), "names repeat");
496 assert_eq!(
499 with_fields(&[], builder_outputs),
500 with_fields(&[], builder_outputs)
501 );
502 let all = super::gate_mutants(4);
503 assert_eq!(all.len(), inputs.len());
504 let mut no_field = Vec::new();
505 for ((name, data), (n, ms)) in inputs.iter().zip(&all) {
506 assert_eq!(name, n);
507 assert!(
508 ms.iter().all(|m| m.bytes != *data),
509 "{name}: a mutant is its input"
510 );
511 let fields = ms.iter().filter(|m| m.label.starts_with('f')).count();
512 assert_eq!(fields % 2, 0, "{name}: {fields} field mutants");
513 if fields == 0 {
514 no_field.push(name.as_str());
515 }
516 assert_eq!(ms.len(), fields + RANDOM_PER_INPUT, "{name}");
517 }
518 assert_eq!(
520 no_field,
521 [
522 "scene-resolver_loads-CAB-H2.resS",
523 "scene-find_file_kinds-top.resS",
524 "scene-find_file_kinds-r.resS",
525 "scene-find_file_listing-x.resS"
526 ]
527 );
528 }
529
530 #[test]
539 fn every_file_of_every_scene_is_an_output() {
540 type Files = Vec<(Vec<u8>, Vec<u8>)>;
541 fn files(s: crate::env::Scene) -> Files {
542 s.files.into_iter().chain(s.resolver).collect()
543 }
544 let inputs = builder_outputs();
545 let lists: [(&str, Vec<(&str, Files)>); 4] = [
546 (
547 "scenes",
548 crate::env::scenes()
549 .into_iter()
550 .map(|(scene, s)| (scene, files(s)))
551 .collect(),
552 ),
553 (
554 "dependency_scenes",
555 crate::env::dependency_scenes()
556 .into_iter()
557 .map(|(scene, d)| (scene, files(d.scene)))
558 .collect(),
559 ),
560 (
561 "find_scenes",
562 crate::env::find_scenes()
563 .into_iter()
564 .map(|(scene, f)| (scene, files(f.scene)))
565 .collect(),
566 ),
567 (
568 "race_scenes",
569 crate::env::race_scenes()
570 .into_iter()
571 .map(|(scene, r)| {
572 let mut all = files(r.scene);
573 all.push(r.other);
574 (scene, all)
575 })
576 .collect(),
577 ),
578 ];
579 let (mut count, mut web) = (0, Vec::new());
580 for (list, scenes) in lists {
581 assert_ne!(scenes.len(), 0, "{list}");
582 for (scene, files) in scenes {
583 for (name, bytes) in files {
584 let name = String::from_utf8_lossy(&name).replace('/', "_");
585 let name = format!("scene-{scene}-{name}");
586 if super::is_web_file(&bytes) {
587 web.push(name);
588 continue;
589 }
590 assert!(
591 inputs.iter().any(|(n, b)| *n == name && *b == bytes),
592 "{list}: {name} is no output"
593 );
594 count += 1;
595 }
596 }
597 }
598 assert_eq!(web, ["scene-find_file_kinds-w.web"]);
599 assert_eq!(inputs.len(), crate::bundle::matrix().len() + count);
600 }
601}