bitcut 1.0.0

Create and apply binary patches
Documentation 
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
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292

//! Property-based tests for the v1.0 API.
//!
//! Run with `cargo test --test property`.

#![allow(
    clippy::indexing_slicing,
    clippy::unwrap_used,
    clippy::expect_used,
    clippy::arithmetic_side_effects,
    clippy::default_numeric_fallback,
    clippy::cast_possible_truncation,
    clippy::as_conversions,
    clippy::missing_panics_doc,
    clippy::needless_pass_by_value,
    clippy::missing_errors_doc,
    dead_code
)]

use bitcut::{apply_patch, base_fingerprint, inspect, make_patch, Op, PatchError};
use proptest::collection::vec;
use proptest::prelude::*;

/// Naive byte-by-byte common-prefix length, used as a reference oracle for
/// the SIMD `simd_memcmp` paths (which we exercise indirectly through
/// `make_patch` over crafted inputs).
fn common_prefix_len(a: &[u8], b: &[u8]) -> usize {
    a.iter().zip(b.iter()).take_while(|(x, y)| x == y).count()
}

// =============================================================================
// 17. Round-trip property
// =============================================================================

proptest! {
    #![proptest_config(ProptestConfig {
        cases: 2048,
        max_shrink_iters: 10_000,
        ..ProptestConfig::default()
    })]

    /// For any (old, new): apply_patch(old, make_patch(old, new)) == new.
    #[test]
    fn roundtrip_arbitrary(
        old in vec(any::<u8>(), 0..512),
        new in vec(any::<u8>(), 0..512),
    ) {
        let patch = make_patch(&old, &new).expect("make_patch must succeed");
        let restored = apply_patch(&old, &patch).expect("apply_patch must succeed on a valid patch");
        prop_assert_eq!(restored, new);
    }

    /// Round-trip when `new` is a substring/shifted variant of `old` —
    /// the realistic case where Copy ops dominate.
    #[test]
    fn roundtrip_shifted(
        old in vec(any::<u8>(), 32..512),
        skip in 0usize..32,
        tail in vec(any::<u8>(), 0..32),
    ) {
        let take = old.len().saturating_sub(skip);
        let mut new: Vec<u8> = old.iter().copied().skip(skip).take(take).collect();
        new.extend_from_slice(&tail);
        let patch = make_patch(&old, &new).expect("make_patch must succeed");
        let restored = apply_patch(&old, &patch).expect("valid patch");
        prop_assert_eq!(restored, new);
    }

    /// Repeated patterns — exercises rolling hash collisions and long matches.
    #[test]
    fn roundtrip_repeated_pattern(
        unit in vec(any::<u8>(), 1..16),
        repeat_old in 1usize..40,
        repeat_new in 1usize..40,
    ) {
        let old: Vec<u8> = unit.iter().cycle().copied().take(unit.len() * repeat_old).collect();
        let new: Vec<u8> = unit.iter().cycle().copied().take(unit.len() * repeat_new).collect();
        let patch = make_patch(&old, &new).expect("make_patch must succeed");
        let restored = apply_patch(&old, &patch).expect("valid patch");
        prop_assert_eq!(restored, new);
    }
}

// =============================================================================
// 18. Fuzz: arbitrary patch bytes must never panic
// =============================================================================

proptest! {
    #![proptest_config(ProptestConfig {
        cases: 4096,
        max_shrink_iters: 10_000,
        ..ProptestConfig::default()
    })]

    /// Feeding arbitrary bytes to `apply_patch` must never panic — only
    /// return Err. This stresses the deserializer for overflow / OOB.
    #[test]
    fn apply_patch_never_panics(
        old in vec(any::<u8>(), 0..256),
        patch in vec(any::<u8>(), 0..1024),
    ) {
        // Just ensure no panic — both Ok and Err are acceptable.
        let _ = apply_patch(&old, &patch);
    }

    /// `Op::iter` on arbitrary bytes also must not panic.
    #[test]
    fn op_iter_never_panics(patch in vec(any::<u8>(), 0..1024)) {
        for _ in Op::iter(&patch) {
            // drain
        }
    }

    /// Crafted Copy with huge offset/len must produce a clean Err, not panic.
    #[test]
    fn crafted_copy_overflow_never_panics(
        old in vec(any::<u8>(), 0..64),
        offset in any::<u32>(),
        len in any::<u32>(),
    ) {
        let mut patch = Vec::with_capacity(9);
        patch.push(0x00);
        patch.extend_from_slice(&offset.to_le_bytes());
        patch.extend_from_slice(&len.to_le_bytes());
        let _ = apply_patch(&old, &patch);
    }

    /// Crafted Add with huge declared length must produce a clean Err.
    #[test]
    fn crafted_add_overflow_never_panics(
        old in vec(any::<u8>(), 0..64),
        declared_len in any::<u32>(),
        body in vec(any::<u8>(), 0..64),
    ) {
        let mut patch = Vec::with_capacity(5 + body.len());
        patch.push(0x01);
        patch.extend_from_slice(&declared_len.to_le_bytes());
        patch.extend_from_slice(&body);
        let _ = apply_patch(&old, &patch);
    }
}

// =============================================================================
// SIMD memcmp coverage — exercised indirectly through make_patch/apply_patch
// =============================================================================

// Build (old, new) pairs that force `simd_memcmp` to run with the mismatch
// at every possible offset within / across SIMD chunks (16-byte NEON,
// 32-byte AVX2). Covers the NEON scalar tail and AVX2 movemask path.
proptest! {
    #![proptest_config(ProptestConfig {
        cases: 2048,
        ..ProptestConfig::default()
    })]

    /// For each mismatch position `pos`, build old=[A;N], new=[A;pos] ++ [B] ++ [A; N-pos-1]
    /// with N from 1..200, and verify that the round-trip succeeds.
    /// This exercises every possible mismatch offset in `simd_memcmp`.
    #[test]
    fn simd_memcmp_mismatch_at_every_offset(
        (n, pos) in (1usize..200).prop_flat_map(|n| (Just(n), 0usize..n)),
    ) {
        let old = vec![0xAA_u8; n];
        let mut new = vec![0xAA_u8; n];
        new[pos] = 0xBB;
        let patch = make_patch(&old, &new).expect("make_patch must succeed");
        let restored = apply_patch(&old, &patch).expect("valid patch");
        prop_assert_eq!(restored, new);
    }

    /// Identical inputs of varying lengths — `simd_memcmp` should walk to
    /// the end without breaking on the chunk boundary.
    #[test]
    fn simd_memcmp_full_match(n in 0usize..300) {
        let buf = vec![0xCC_u8; n];
        let patch = make_patch(&buf, &buf).expect("make_patch must succeed");
        let restored = apply_patch(&buf, &patch).expect("valid patch");
        prop_assert_eq!(restored, buf);
    }
}

#[test]
fn common_prefix_len_oracle_smoke() {
    // Trivial sanity check on the oracle helper itself.
    assert_eq!(common_prefix_len(b"abcdef", b"abcxyz"), 3);
    assert_eq!(common_prefix_len(b"", b"x"), 0);
    assert_eq!(common_prefix_len(b"abc", b"abc"), 3);
}

// =============================================================================
// Targeted SIMD mismatch tests across critical chunk boundaries
// =============================================================================

/// Drives the SIMD path for every byte length 0..=160 (covers NEON 16-byte
/// chunks 0..10 and AVX2 32-byte chunks 0..5) and every mismatch position.
/// This is the deterministic complement to the property tests above —
/// guarantees coverage of SIMD chunk-boundary edge cases (point 8).
#[test]
fn simd_memcmp_exhaustive_small() {
    for n in 0_usize..=160 {
        let a = vec![0x55_u8; n];
        // Full match
        let patch = make_patch(&a, &a).expect("make_patch must succeed");
        let restored = apply_patch(&a, &patch).expect("valid patch");
        assert_eq!(restored, a, "full-match failed at n={n}");

        // Mismatch at every position
        for pos in 0..n {
            let mut b = a.clone();
            b[pos] = 0xAA;
            let patch = make_patch(&a, &b).expect("make_patch must succeed");
            let restored = apply_patch(&a, &patch).expect("valid patch");
            assert_eq!(restored, b, "mismatch at pos={pos}, n={n}");

            // Also reverse direction
            let patch = make_patch(&b, &a).expect("make_patch must succeed");
            let restored = apply_patch(&b, &patch).expect("valid patch");
            assert_eq!(restored, a, "reverse mismatch at pos={pos}, n={n}");
        }
    }
}

// =============================================================================
// Base identity
// =============================================================================

proptest! {
    #![proptest_config(ProptestConfig { cases: 512, ..ProptestConfig::default() })]

    /// A patch must refuse any base other than the one it was built from.
    #[test]
    fn wrong_base_is_always_rejected(
        old in vec(any::<u8>(), 1..512),
        new in vec(any::<u8>(), 0..512),
        flip in 0usize..512,
    ) {
        let patch = make_patch(&old, &new).expect("make_patch must succeed");
        let mut other = old.clone();
        let at = flip % other.len();
        other[at] ^= 0xFF;

        let rejected = matches!(
            apply_patch(&other, &patch),
            Err(PatchError::WrongBase { .. })
        );
        prop_assert!(rejected);
        prop_assert_eq!(apply_patch(&old, &patch).expect("valid base"), new);
    }

    /// The header must describe the base the patch was actually built from.
    #[test]
    fn header_matches_the_base(
        old in vec(any::<u8>(), 0..512),
        new in vec(any::<u8>(), 0..512),
    ) {
        let patch = make_patch(&old, &new).expect("make_patch must succeed");
        let header = inspect(&patch).expect("readable header").expect("v2 patch");
        prop_assert_eq!((header.base_len, header.base_hash), base_fingerprint(&old));
    }
}

// =============================================================================
// Format limits
// =============================================================================

/// Inputs at the 4 GiB boundary must be refused, not truncated into a patch
/// that reconstructs the wrong document.
///
/// Allocates over 4 GiB, so it is opt-in:
/// `cargo test --test property -- --ignored four_gib`.
#[test]
#[ignore = "allocates more than 4 GiB"]
fn four_gib_boundary_is_refused() {
    let over = vec![0_u8; usize::try_from(u32::MAX).unwrap() + 1];
    let small = b"small".to_vec();

    assert_eq!(
        make_patch(&over, &small),
        Err(PatchError::InputTooLarge { len: over.len() })
    );
    assert_eq!(
        make_patch(&small, &over),
        Err(PatchError::InputTooLarge { len: over.len() })
    );

    // One byte below the boundary must still work.
    let at_limit = vec![0_u8; usize::try_from(u32::MAX).unwrap()];
    let patch = make_patch(&at_limit, &at_limit).expect("u32::MAX bytes must be accepted");
    assert_eq!(
        apply_patch(&at_limit, &patch).expect("valid patch"),
        at_limit
    );
}