objects/util/line_diff/
scratch.rs

1// SPDX-License-Identifier: Apache-2.0
2//! Caller-scratch layout for line offsets, Myers V arrays, and the conquer stack.
3
4use std::mem::{align_of, size_of};
5
6use super::super::budget::{BudgetExceeded, ResourceKind};
7use super::scan::LineOff;
8
9#[repr(C)]
10#[derive(Clone, Copy)]
11pub(super) struct ConquerJob {
12    pub old_lo: u32,
13    pub old_hi: u32,
14    pub new_lo: u32,
15    pub new_hi: u32,
16    pub kind: u8,
17    pub eq_old: u32,
18    pub eq_new: u32,
19    pub eq_len: u32,
20}
21
22pub(super) const JOB_RANGE: u8 = 0;
23pub(super) const JOB_EQUAL: u8 = 1;
24
25pub fn max_scratch_align() -> usize {
26    align_of::<LineOff>()
27        .max(align_of::<usize>())
28        .max(align_of::<ConquerJob>())
29}
30
31pub fn scratch_bytes_for_line_counts(old_lines: usize, new_lines: usize) -> usize {
32    let (needed, _) = layout_sizes(old_lines, new_lines);
33    needed.saturating_add(max_scratch_align().saturating_sub(1))
34}
35
36#[cfg(test)]
37pub(super) fn aligned_layout_bytes(old_lines: usize, new_lines: usize) -> usize {
38    let (needed, _) = layout_sizes(old_lines, new_lines);
39    needed
40}
41
42/// Shift `scratch` so the returned suffix starts at [`max_scratch_align`].
43///
44/// The pad is computed from the actual pointer, not from a layout that
45/// assumed the slice was already aligned.
46pub(super) fn align_scratch(scratch: &mut [u8]) -> Result<(&mut [u8], usize), BudgetExceeded> {
47    let align = max_scratch_align();
48    let addr = scratch.as_mut_ptr() as usize;
49    let pad = if align <= 1 {
50        0
51    } else {
52        (align - (addr % align)) % align
53    };
54    if pad > scratch.len() {
55        return Err(BudgetExceeded {
56            kind: ResourceKind::ScratchBytes,
57            limit: scratch.len() as u64,
58            needed: (pad as u64).saturating_add(1),
59        });
60    }
61    Ok((&mut scratch[pad..], pad))
62}
63
64pub(super) struct ScratchLayout {
65    pub old_off: usize,
66    pub new_off: usize,
67    pub vf: usize,
68    pub vb: usize,
69    pub jobs: usize,
70    pub old_off_bytes: usize,
71    pub new_off_bytes: usize,
72    pub vf_bytes: usize,
73    pub vb_bytes: usize,
74    pub jobs_bytes: usize,
75}
76
77pub(super) fn layout_sizes(old_lines: usize, new_lines: usize) -> (usize, ScratchLayout) {
78    let max_d = max_d(old_lines, new_lines);
79    let v_len = 2 * max_d + 1;
80    let job_cap = old_lines.saturating_add(new_lines).saturating_add(8);
81
82    let mut cursor = 0usize;
83    let old_off = align_up(cursor, align_of::<LineOff>());
84    let old_off_bytes = old_lines.saturating_mul(size_of::<LineOff>());
85    cursor = old_off.saturating_add(old_off_bytes);
86
87    let new_off = align_up(cursor, align_of::<LineOff>());
88    let new_off_bytes = new_lines.saturating_mul(size_of::<LineOff>());
89    cursor = new_off.saturating_add(new_off_bytes);
90
91    let vf = align_up(cursor, align_of::<usize>());
92    let vf_bytes = v_len.saturating_mul(size_of::<usize>());
93    cursor = vf.saturating_add(vf_bytes);
94
95    let vb = align_up(cursor, align_of::<usize>());
96    let vb_bytes = v_len.saturating_mul(size_of::<usize>());
97    cursor = vb.saturating_add(vb_bytes);
98
99    let jobs = align_up(cursor, align_of::<ConquerJob>());
100    let jobs_bytes = job_cap.saturating_mul(size_of::<ConquerJob>());
101    cursor = jobs.saturating_add(jobs_bytes);
102
103    (
104        cursor,
105        ScratchLayout {
106            old_off,
107            new_off,
108            vf,
109            vb,
110            jobs,
111            old_off_bytes,
112            new_off_bytes,
113            vf_bytes,
114            vb_bytes,
115            jobs_bytes,
116        },
117    )
118}
119
120pub(super) fn max_d(old_lines: usize, new_lines: usize) -> usize {
121    old_lines
122        .saturating_add(new_lines)
123        .div_ceil(2)
124        .saturating_add(1)
125}
126
127fn align_up(value: usize, align: usize) -> usize {
128    if align <= 1 {
129        return value;
130    }
131    let rem = value % align;
132    if rem == 0 {
133        value
134    } else {
135        value + (align - rem)
136    }
137}
138
139pub(super) fn require_scratch(scratch_len: usize, needed: usize) -> Result<(), BudgetExceeded> {
140    if needed > scratch_len {
141        return Err(BudgetExceeded {
142            kind: ResourceKind::ScratchBytes,
143            limit: scratch_len as u64,
144            needed: needed as u64,
145        });
146    }
147    Ok(())
148}
objects/util/line_diff/scratch.rs

objects/util/line_diff/
scratch.rs
