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

objects/util/line_diff/
scratch.rs
