dlp_api/diff/algorithm.rs
1use std::cmp::{min, Ordering};
2
3use pinocchio::error::ProgramError;
4use rkyv::util::AlignedVec;
5
6use super::{
7 DiffSet, OffsetInData, SizeChanged, SIZE_OF_CHANGED_LEN,
8 SIZE_OF_NUM_OFFSET_PAIRS, SIZE_OF_SINGLE_OFFSET_PAIR,
9};
10use crate::{error::DlpError, require_eq, require_le};
11
12///
13/// Compute diff between original and changed.
14///
15/// Returns:
16///
17/// - AlignedVec (a vector of u8) which is aligned to 16-byte boundary that can be used
18/// to construct DiffSet.
19///
20/// Note that DiffSet::try_new() requires the argument &[u8] to be aligned to 4-byte
21/// boundary, but compute_diff provides much stricter alignment guarantee.
22///
23/// ref: https://docs.rs/rkyv/0.7.45/rkyv/util/struct.AlignedVec.html
24///
25/// ---
26///
27/// Scenarios:
28/// - original.len() == changed.len()
29/// - diff is computed by comparing corresponding indices.
30/// - bytes comparison
31/// original: o1 o2 o3 o4 ... oN
32/// changed: c1 c2 c3 c4 ... cN
33/// - diff consists of the bytes from the "changed" slice.
34/// - original.len() < changed.len()
35/// - that implies the account has been reallocated and expanded
36/// - bytes comparison
37/// original: o1 o2 o3 o4 ... oN
38/// changed: c1 c2 c3 c4 ... cN cN+1 cN+2 ... cN+M
39/// - original.len() > changed.len()
40/// - that implies the account has been reallocated and shrunk
41/// - bytes comparison
42/// original: o1 o2 o3 o4 ... oN oN+1 oN+2 ... oN+M
43/// changed: c1 c2 c3 c4 ... cN
44///
45/// ---
46///
47/// Diff Format:
48///
49/// Since an account could have modifications at multiple places (i.e imagine modifying
50/// multiple fields in a struct), the diff could consist of multiple segments of [u8], one
51/// segment for each contiguous change. So we compute these segments of change, and concatenate them
52/// to form one big segment/slice. However, in doing so, we lose the lengths of each segment and the
53/// position of change in the original data. So the headers below captures all these necessary information:
54///
55/// - Length of the given changed data (the second argument to compute_diff).
56/// - Number of slices: first 4 bytes.
57/// - Then follows offset-pairs, for each slice/segment, that captures offset in concatenated diff
58/// as well as in the original account.
59/// - Then follows the concatenated diff bytes.
60///
61/// | Length | # Offset Pairs | Offset Pair 0 | Offset Pair 1 | ... | Offset Pair N-1 | Concatenated Diff |
62/// |= 4 bytes =|==== 4 bytes ====|=== 8 bytes ===|=== 8 bytes ===| ... |==== 8 bytes ====|==== M bytes =====|
63///
64/// Offset Pair Format:
65///
66/// | OffsetInDiffBytes | OffsetInAccountData |
67/// | ==== 4 bytes ===== | ===== 4 bytes ===== |
68///
69/// where,
70///
71/// - OffsetInDiffBytes is the index in ConcatenatedDiff indicating the beginning of the slice
72/// and the next OffsetInDiffBytes from the next pair indicates the end of the slice, i.e the length of
73/// slice[i] is OffsetInDiffBytes[i+1] - OffsetInDiffBytes[i].
74/// - Note that the OffsetInDiffBytes is relative to the beginning of ConcatenatedDiff, not
75/// relative to the beginning of the whole serialized data, that implies the OffsetInDiffBytes
76/// in the first pair is always 0.
77/// - M is a variable and is the sum of the length of the diff-slices.
78/// - M = diff_segments.map(|s| s.len()).sum()
79/// - The length of ith slice = OffsetInDiffBytes@(i+1) - OffsetInDiffBytes@i, as noted earlier.
80///
81/// ---
82///
83/// Example,
84///
85/// Suppose we have an account with datalen = 100:
86///
87/// ```text
88/// ----------------------------
89/// | a 100 bytes account |
90/// ----------------------------
91/// | M | A | G | I | ... | C |
92/// ----------------------------
93/// | 0 | 1 | 2 | 3 | ... | 99 |
94/// ----------------------------
95/// ```
96///
97/// Also, suppose we have modifications at two locations (say u32 and u64), so we have 2 slices of size 4
98/// and 8 bytes respectively, and the corresponding indices are the followings (note that these are "indices"
99/// in the original account, not the indices in the concatenated diff):
100///
101/// - | 11 | 12 | 13 | 14 | -- 4 bytes
102/// - | 71 | 72 | 73 | 74 | 75 | 76 | 77 | 78 | -- 8 bytes
103///
104/// In this case, the serialized bytes would be:
105///
106/// ```text
107/// ------------------------------------------------------
108/// | len | num | offsets | concatenated slices |
109/// ------------------------------------------------------
110/// | 100 | 2 | 0 11 | 4 71 | 11 12 13 14 71 72 ... 78 | OffsetInAccountData
111/// ------------------------------------------------------
112/// | 0 1 2 3 4 5 ... 11 | OffsetInDiffBytes
113/// ----------------------------
114/// ```
115///
116/// - 100 : u32 : changed.len()
117/// - 2 : u32 : number of offset pairs
118/// - 0 11 : u32, u32 : first offset pair (offset in diff, offset in account)
119/// - 4 71 : u32, u32 : second offset pair (offset in diff, offset in account)
120/// - 11 ... 78 : each u8 : concatenated diff bytes
121pub fn compute_diff(original: &[u8], changed: &[u8]) -> AlignedVec {
122 // 1. identify contiguous diff slices
123 let mut diffs: Vec<(usize, &[u8])> = Vec::new();
124 let min_len = min(original.len(), changed.len());
125 let mut diff_size = 0;
126 let mut i = 0;
127 while i < min_len {
128 if original[i] != changed[i] {
129 // start of diff
130 let start = i;
131 while i < min_len && original[i] != changed[i] {
132 i += 1;
133 }
134 diffs.push((start, &changed[start..i]));
135 diff_size += i - start;
136 } else {
137 i += 1;
138 }
139 }
140
141 // 2. handle expansion/shrinkage
142 match changed.len().cmp(&original.len()) {
143 Ordering::Greater => {
144 // extra bytes at the end
145 diffs.push((original.len(), &changed[original.len()..]));
146 diff_size += changed.len() - original.len();
147 }
148 Ordering::Less => {
149 // account shrunk: data truncated
150 // nothing to do here
151 }
152 Ordering::Equal => {
153 // already handled
154 }
155 };
156
157 // 3. serialize according to the spec
158 let mut output = AlignedVec::with_capacity(
159 SIZE_OF_CHANGED_LEN
160 + SIZE_OF_NUM_OFFSET_PAIRS
161 + SIZE_OF_SINGLE_OFFSET_PAIR * diffs.len()
162 + diff_size,
163 );
164
165 // size of changed data (4 bytes)
166 output.extend_from_slice(&(changed.len() as u32).to_le_bytes());
167
168 // number of slices / offset-pairs (4 bytes)
169 output.extend_from_slice(&(diffs.len() as u32).to_le_bytes());
170
171 // compute offset pairs (offset_in_diff: 4 bytes, offset_in_account: 4 bytes)
172 let mut offset_in_diff = 0u32;
173 for (offset_in_account, slice) in &diffs {
174 output.extend_from_slice(&offset_in_diff.to_le_bytes());
175 output.extend_from_slice(&(*offset_in_account as u32).to_le_bytes());
176 offset_in_diff += slice.len() as u32;
177 }
178
179 // append concatenated diff bytes: concatenated len = sum of len of the diff-segments
180 for (_, slice) in diffs {
181 output.extend_from_slice(slice);
182 }
183
184 output
185}
186
187/// Detects if there is size change in the changed data.
188/// - None means NO change
189/// - Some(size_changed) means the data size has changed and size_changed indicates
190/// whether it has expanded or shrunk.
191pub fn detect_size_change(
192 original: &[u8],
193 diffset: &DiffSet<'_>,
194) -> Option<SizeChanged> {
195 match diffset.changed_len().cmp(&original.len()) {
196 Ordering::Less => Some(SizeChanged::Shrunk(diffset.changed_len())),
197 Ordering::Greater => Some(SizeChanged::Expanded(diffset.changed_len())),
198 Ordering::Equal => None,
199 }
200}
201
202/// This function applies the diff to the first argument (i.e original) to update it.
203///
204/// Precondition:
205/// - original.len() must be equal to the length encoded in the diff.
206pub fn apply_diff_in_place(
207 original: &mut [u8],
208 diffset: &DiffSet<'_>,
209) -> Result<(), ProgramError> {
210 if let Some(_layout) = detect_size_change(original, diffset) {
211 return Err(ProgramError::InvalidInstructionData);
212 }
213 apply_diff_impl(original, diffset)
214}
215
216/// This function creates a copy of original, possibly extending or shrinking it,
217/// and then applies the diff to it, before returning it.
218pub fn apply_diff_copy(
219 original: &[u8],
220 diffset: &DiffSet<'_>,
221) -> Result<Vec<u8>, ProgramError> {
222 Ok(match detect_size_change(original, diffset) {
223 Some(SizeChanged::Expanded(new_size)) => {
224 let mut applied = Vec::with_capacity(new_size);
225 applied.extend_from_slice(original);
226 applied.resize(new_size, 0);
227 apply_diff_impl(applied.as_mut(), diffset)?;
228 applied
229 }
230 Some(SizeChanged::Shrunk(new_size)) => {
231 let mut applied = Vec::from(&original[0..new_size]);
232 apply_diff_impl(applied.as_mut(), diffset)?;
233 applied
234 }
235 None => {
236 let mut applied = Vec::from(original);
237 apply_diff_impl(applied.as_mut(), diffset)?;
238 applied
239 }
240 })
241}
242
243/// Constructs destination by applying the diff to original, such that destination becomes the
244/// post-diff state of the original.
245///
246/// Precondition:
247/// - destination.len() == diffset.changed_len()
248/// - original.len() may differ from destination.len() to allow Solana
249/// account resizing (shrink or expand).
250/// Assumption:
251/// - destination is assumed to be zero-initialized. That automatically holds true for freshly
252/// allocated Solana account data. The function does NOT validate this assumption for performance reason.
253/// Returns:
254/// - Ok(&mut [u8]) where the slice contains the trailing unwritten bytes in destination and are
255/// assumed to be already zero-initialized. Callers may write to those bytes or validate it.
256/// Notes:
257/// - Merge consists of:
258/// - bytes covered by diff segments are written from diffset.
259/// - unmodified regions are copied directly from original.
260/// - In shrink case, extra trailing bytes from original are ignored.
261/// - In expansion case, any remaining bytes beyond both the diff coverage
262/// and original.len() stay unwritten and are assumed to be zero-initialized.
263///
264pub fn merge_diff_copy<'a>(
265 destination: &'a mut [u8],
266 original: &[u8],
267 diffset: &DiffSet<'_>,
268) -> Result<&'a mut [u8], ProgramError> {
269 require_eq!(
270 destination.len(),
271 diffset.changed_len(),
272 DlpError::MergeDiffError
273 );
274
275 let mut write_index = 0;
276 for item in diffset.iter() {
277 let (diff_segment, OffsetInData { start, end }) = item?;
278
279 if write_index < start {
280 require_le!(start, original.len(), DlpError::InvalidDiff);
281 // copy the unchanged bytes
282 destination[write_index..start]
283 .copy_from_slice(&original[write_index..start]);
284 }
285
286 destination[start..end].copy_from_slice(diff_segment);
287 write_index = end;
288 }
289
290 // Ensure we have overwritten all bytes in destination, otherwise "construction" of destination
291 // will be considered incomplete.
292 let num_bytes_written = match write_index.cmp(&destination.len()) {
293 Ordering::Equal => {
294 // It means the destination is fully constructed.
295 // Nothing to do here.
296
297 // It is possible that destination.len() <= original.len() i.e destination might have shrunk
298 // in which case we do not care about those bytes of original which are not part of
299 // destination anymore.
300 write_index
301 }
302 Ordering::Less => {
303 // destination is NOT fully constructed yet. Few bytes in the destination are still unwritten.
304 // Let's say the number of these unwritten bytes is: N.
305 //
306 // Now how do we construct these N unwritten bytes? We have already processed the
307 // diffset, so now where could the values for these N bytes come from?
308 //
309 // There are 3 scenarios:
310 // - All N bytes must be copied from remaining region of the original:
311 // - that means, destination.len() <= original.len()
312 // - and the destination might have shrunk, in which case we do not care about
313 // the extra bytes in the original: they're discarded.
314 // - Only (N-M) bytes come from original and the rest M bytes stay unwritten and are
315 // "assumed" to be already zero-initialized.
316 // - that means, destination.len() > original.len()
317 // - write_index + (N-M) == original.len()
318 // - and the destination has expanded.
319 // - None of these N bytes come from original. It's basically a special case of
320 // the second scenario: when M = N i.e all N bytes stay unwritten.
321 // - that means, destination.len() > original.len()
322 // - and also, write_index == original.len().
323 // - the destination has expanded just like the above case.
324 // - all N bytes are "assumed" to be already zero-initialized (by the caller)
325
326 if destination.len() <= original.len() {
327 // case: all n bytes come from original
328 let dest_len = destination.len();
329 destination[write_index..]
330 .copy_from_slice(&original[write_index..dest_len]);
331 dest_len
332 } else if write_index < original.len() {
333 // case: some bytes come from original and the rest are "assumed" to be
334 // zero-initialized (by the caller).
335 destination[write_index..original.len()]
336 .copy_from_slice(&original[write_index..]);
337 original.len()
338 } else {
339 // case: all N bytes are "assumed" to be zero-initialized (by the caller).
340 write_index
341 }
342 }
343 Ordering::Greater => {
344 // It is an impossible scenario. Even if the diff is corrupt, or the lengths of destinatiare are same
345 // or different, we'll not encounter this case. It only implies logic error.
346 return Err(DlpError::InfallibleError.into());
347 }
348 };
349
350 let (_, unwritten_bytes) = destination.split_at_mut(num_bytes_written);
351
352 Ok(unwritten_bytes)
353}
354
355// private function that does the actual work.
356fn apply_diff_impl(
357 original: &mut [u8],
358 diffset: &DiffSet<'_>,
359) -> Result<(), ProgramError> {
360 for item in diffset.iter() {
361 let (diff_segment, offset_range) = item?;
362 original[offset_range].copy_from_slice(diff_segment);
363 }
364 Ok(())
365}
366
367#[cfg(test)]
368mod tests {
369
370 use rand::{
371 rngs::{OsRng, StdRng},
372 seq::IteratorRandom,
373 Rng, RngCore, SeedableRng,
374 };
375
376 use crate::diff::{
377 apply_diff_copy, apply_diff_in_place, compute_diff, merge_diff_copy,
378 DiffSet,
379 };
380
381 #[test]
382 fn test_no_change() {
383 let original = [0; 100];
384 let diff = compute_diff(&original, &original);
385
386 assert_eq!(diff.len(), 8);
387 assert_eq!(
388 diff.as_slice(),
389 [
390 100u32.to_le_bytes().as_slice(),
391 0u32.to_le_bytes().as_slice()
392 ]
393 .concat::<u8>()
394 );
395 }
396
397 fn get_example_expected_diff(
398 changed_len: usize,
399 // additional_changes must apply after index 78 (index-in-data) !!
400 additional_changes: Vec<(u32, &[u8])>,
401 ) -> Vec<u8> {
402 // expected: | 100 | 2 | 0 11 | 4 71 | 11 12 13 14 71 72 ... 78 |
403
404 let mut expected_diff = vec![];
405
406 // changed_len (u32)
407 expected_diff.extend_from_slice(&(changed_len as u32).to_le_bytes());
408
409 if additional_changes.is_empty() {
410 // 2 (u32)
411 expected_diff.extend_from_slice(&2u32.to_le_bytes());
412 } else {
413 expected_diff.extend_from_slice(
414 &(2u32 + additional_changes.len() as u32).to_le_bytes(),
415 );
416 }
417
418 // -- offsets
419
420 // 0 11 (each u32)
421 expected_diff.extend_from_slice(&0u32.to_le_bytes());
422 expected_diff.extend_from_slice(&11u32.to_le_bytes());
423
424 // 4 71 (each u32)
425 expected_diff.extend_from_slice(&4u32.to_le_bytes());
426 expected_diff.extend_from_slice(&71u32.to_le_bytes());
427
428 let mut offset_in_diff = 12u32;
429 for (offset_in_data, diff) in additional_changes.iter() {
430 expected_diff.extend_from_slice(&offset_in_diff.to_le_bytes());
431 expected_diff.extend_from_slice(&offset_in_data.to_le_bytes());
432 offset_in_diff += diff.len() as u32;
433 }
434
435 // -- segments --
436
437 // 11 12 13 14 (each u8)
438 expected_diff.extend_from_slice(&0x01020304u32.to_le_bytes());
439 // 71 72 ... 78 (each u8)
440 expected_diff.extend_from_slice(&0x0102030405060708u64.to_le_bytes());
441
442 // append diff from additional_changes
443 for (_, diff) in additional_changes.iter() {
444 expected_diff.extend_from_slice(diff);
445 }
446
447 expected_diff
448 }
449
450 #[test]
451 fn test_using_example_data() {
452 let original = [0; 100];
453 let changed = {
454 let mut copy = original;
455 // | 11 | 12 | 13 | 14 |
456 copy[11..=14].copy_from_slice(&0x01020304u32.to_le_bytes());
457 // | 71 | 72 | 73 | 74 | 75 | 76 | 77 | 78 |
458 copy[71..=78].copy_from_slice(&0x0102030405060708u64.to_le_bytes());
459 copy
460 };
461
462 let actual_diff = compute_diff(&original, &changed);
463 let actual_diffset = DiffSet::try_new(&actual_diff).unwrap();
464 let expected_diff = get_example_expected_diff(changed.len(), vec![]);
465
466 assert_eq!(actual_diff.len(), 4 + 4 + 8 + 8 + (4 + 8));
467 assert_eq!(actual_diff.as_slice(), expected_diff.as_slice());
468
469 let expected_changed =
470 apply_diff_copy(&original, &actual_diffset).unwrap();
471
472 assert_eq!(changed.as_slice(), expected_changed.as_slice());
473
474 let expected_changed = {
475 let mut destination = vec![255; original.len()];
476 merge_diff_copy(&mut destination, &original, &actual_diffset)
477 .unwrap();
478 destination
479 };
480
481 assert_eq!(changed.as_slice(), expected_changed.as_slice());
482 }
483
484 #[test]
485 fn test_shrunk_account_data() {
486 // Note that changed_len cannot be lower than 79 because the last "changed" index is
487 // 78 in the diff.
488 const CHANGED_LEN: usize = 80;
489
490 let original = vec![0; 100];
491 let changed = {
492 let mut copy = original.clone();
493 copy.truncate(CHANGED_LEN);
494
495 // | 11 | 12 | 13 | 14 |
496 copy[11..=14].copy_from_slice(&0x01020304u32.to_le_bytes());
497 // | 71 | 72 | 73 | 74 | 75 | 76 | 77 | 78 |
498 copy[71..=78].copy_from_slice(&0x0102030405060708u64.to_le_bytes());
499 copy
500 };
501
502 let actual_diff = compute_diff(&original, &changed);
503
504 let actual_diffset = DiffSet::try_new(&actual_diff).unwrap();
505
506 let expected_diff = get_example_expected_diff(CHANGED_LEN, vec![]);
507
508 assert_eq!(actual_diff.len(), 4 + 4 + 8 + 8 + (4 + 8));
509 assert_eq!(actual_diff.as_slice(), expected_diff.as_slice());
510
511 let expected_changed = {
512 let mut destination = vec![255; CHANGED_LEN];
513 merge_diff_copy(&mut destination, &original, &actual_diffset)
514 .unwrap();
515 destination
516 };
517
518 assert_eq!(changed.as_slice(), expected_changed.as_slice());
519 }
520
521 #[test]
522 fn test_expanded_account_data() {
523 const CHANGED_LEN: usize = 120;
524
525 let original = vec![0; 100];
526 let changed = {
527 let mut copy = original.clone();
528 copy.resize(CHANGED_LEN, 0); // new bytes are zero-initialized
529
530 // | 11 | 12 | 13 | 14 |
531 copy[11..=14].copy_from_slice(&0x01020304u32.to_le_bytes());
532 // | 71 | 72 | 73 | 74 | 75 | 76 | 77 | 78 |
533 copy[71..=78].copy_from_slice(&0x0102030405060708u64.to_le_bytes());
534 copy
535 };
536
537 let actual_diff = compute_diff(&original, &changed);
538
539 let actual_diffset = DiffSet::try_new(&actual_diff).unwrap();
540
541 // When an account expands, the extra bytes at the end become part of the diff, even if
542 // all of them are zeroes, that is why (100, &[0; 32]) is passed as additional_changes to
543 // the following function.
544 //
545 // TODO (snawaz): we could optimize compute_diff to not include the zero bytes which are
546 // part of the expansion.
547 let expected_diff =
548 get_example_expected_diff(CHANGED_LEN, vec![(100, &[0; 20])]);
549
550 assert_eq!(actual_diff.len(), 4 + 4 + (8 + 8) + (4 + 8) + (4 + 4 + 20));
551 assert_eq!(actual_diff.as_slice(), expected_diff.as_slice());
552
553 let expected_changed = {
554 let mut destination = vec![255; CHANGED_LEN];
555 let unwritten =
556 merge_diff_copy(&mut destination, &original, &actual_diffset)
557 .unwrap();
558
559 // TODO (snawaz): unwritten == &mut [], is because currently the expanded bytes are part of the diff.
560 // Once compute_diff is optimized further, written must be &mut [0; 20].
561 assert_eq!(unwritten, &mut [] as &mut [u8]);
562
563 destination
564 };
565
566 assert_eq!(changed.as_slice(), expected_changed.as_slice());
567 }
568
569 #[test]
570 fn test_using_large_random_data() {
571 // Test Plan:
572 // - Use a random account size (between 2 MB and 10 MB).
573 // - Mutate it at random, non-overlapping and 8-byte-separated regions.
574 // - Use random patch sizes (2–256 bytes).
575 // - Verify that apply_diff(original, diff) reproduces changed.
576
577 const MB: usize = 1024 * 1024;
578
579 let seed = OsRng.next_u64();
580 println!("Use seed = {seed} to reproduce the input data in case of test failure");
581
582 let mut rng = StdRng::seed_from_u64(seed);
583
584 let original = {
585 let account_size: usize = rng.gen_range(2 * MB..10 * MB);
586 // println!("account_size: {account_size}");
587 let mut data = vec![0u8; account_size];
588 rng.fill(&mut data[..]);
589 data
590 };
591
592 let (changed, slices) = {
593 let mut copy = original.clone();
594 let mut slices = vec![];
595
596 let slab = MB / 2;
597 let mut offset_range = 0..slab;
598
599 while offset_range.end < copy.len() {
600 let diff_offset = rng.gen_range(offset_range);
601 let diff_len = (1..256).choose(&mut rng).unwrap();
602 let diff_end = (diff_offset + diff_len).min(copy.len());
603
604 // Overwrite with new random data
605 for i in diff_offset..diff_end {
606 let old = copy[i];
607 while old == copy[i] {
608 copy[i] = rng.gen::<u8>();
609 }
610 }
611 // println!("{diff_offset}, {diff_end} => {diff_len}");
612 slices
613 .push((diff_offset, copy[diff_offset..diff_end].to_vec()));
614
615 offset_range = (diff_end + 8)..(diff_end + 8 + slab);
616 }
617 (copy, slices)
618 };
619
620 let actual_diff = compute_diff(&original, &changed);
621 let actual_diffset = DiffSet::try_new(&actual_diff).unwrap();
622 let expected_diff = {
623 let mut diff = vec![];
624
625 diff.extend_from_slice(&(changed.len() as u32).to_le_bytes());
626
627 diff.extend_from_slice(&(slices.len() as u32).to_le_bytes());
628
629 let mut offset_in_diff = 0u32;
630 for (offset_in_account, slice) in slices.iter() {
631 diff.extend_from_slice(&offset_in_diff.to_le_bytes());
632 diff.extend_from_slice(
633 &(*offset_in_account as u32).to_le_bytes(),
634 );
635 offset_in_diff += slice.len() as u32;
636 }
637
638 for (_, slice) in slices.iter() {
639 diff.extend_from_slice(slice);
640 }
641 diff
642 };
643
644 assert_eq!(
645 actual_diff.len(),
646 expected_diff.len(),
647 "number of slices {}",
648 slices.len()
649 );
650
651 // apply diff back to verify correctness
652 let expected_changed = {
653 let mut copy = original.clone();
654 apply_diff_in_place(&mut copy, &actual_diffset).unwrap();
655 copy
656 };
657
658 assert_eq!(changed, expected_changed);
659
660 let expected_changed = {
661 let mut destination = vec![255; original.len()];
662 merge_diff_copy(&mut destination, &original, &actual_diffset)
663 .unwrap();
664 destination
665 };
666
667 assert_eq!(changed, expected_changed);
668 }
669}