readcon_core/
frame_index.rs

1//! Frame offset index and its checked `.rcidx` sidecar.
2//!
3//! The sidecar stores the byte offset of every frame start in an
4//! uncompressed CON file, so later reads skip the offset scan.
5//! A sidecar is only used when its fingerprint matches the data file
6//! (size, mtime, and a hash of the first and last 4 KiB) and its own
7//! checksum is intact; any mismatch rebuilds the index instead.
8//!
9//! Layout (all integers little-endian):
10//!
11//! | bytes | field                                  |
12//! |-------|----------------------------------------|
13//! | 8     | magic `RCIDX\0\0\0`                    |
14//! | 4     | format version (1)                     |
15//! | 4     | reserved (0)                           |
16//! | 8     | data file size in bytes                |
17//! | 8     | data file mtime, ns since UNIX epoch   |
18//! | 8     | FNV-1a 64 of first and last 4 KiB      |
19//! | 8     | frame count `n`                        |
20//! | 8 n   | frame start offsets                    |
21//! | 8     | FNV-1a 64 of every preceding byte      |
22
23use std::io::{self, Read, Seek, SeekFrom, Write};
24use std::path::{Path, PathBuf};
25
26use crate::error::ParseError;
27use crate::iterators::ConFrameIterator;
28
29const MAGIC: &[u8; 8] = b"RCIDX\0\0\0";
30const VERSION: u32 = 1;
31const EDGE: u64 = 4096;
32const HEADER_LEN: usize = 8 + 4 + 4 + 8 + 8 + 8 + 8;
33
34/// Frame start offsets for one data file, plus its total length.
35#[derive(Debug, Clone, PartialEq, Eq)]
36pub struct FrameIndex {
37    /// Byte offset of each frame start, strictly increasing.
38    pub offsets: Vec<u64>,
39    /// Length of the data in bytes; the last frame ends here.
40    pub data_len: u64,
41}
42
43impl FrameIndex {
44    /// Number of frames.
45    pub fn len(&self) -> usize {
46        self.offsets.len()
47    }
48
49    /// True when the index has no frames.
50    pub fn is_empty(&self) -> bool {
51        self.offsets.is_empty()
52    }
53
54    /// Byte range `[start, end)` of frame `i`.
55    pub fn range(&self, i: usize) -> Option<std::ops::Range<usize>> {
56        let start = *self.offsets.get(i)? as usize;
57        let end = self.offsets.get(i + 1).copied().unwrap_or(self.data_len) as usize;
58        Some(start..end)
59    }
60
61    /// Scan `text` for frame starts, failing on the first malformed frame.
62    pub fn scan(text: &str) -> Result<Self, ParseError> {
63        Ok(FrameIndex {
64            offsets: frame_start_offsets_checked(text)?
65                .into_iter()
66                .map(|o| o as u64)
67                .collect(),
68            data_len: text.len() as u64,
69        })
70    }
71}
72
73/// Frame start offsets, returning the skip error instead of truncating.
74///
75/// [`crate::iterators::frame_start_offsets`] stops silently at the first
76/// malformed frame; an index written to disk must not do that.
77pub fn frame_start_offsets_checked(text: &str) -> Result<Vec<usize>, ParseError> {
78    let mut out = Vec::new();
79    let mut scanner = ConFrameIterator::new(text);
80    loop {
81        let start = scanner.byte_pos();
82        if start >= text.len() || text.as_bytes()[start..].iter().all(u8::is_ascii_whitespace) {
83            break;
84        }
85        out.push(start);
86        match scanner.forward_fast() {
87            Some(Ok(())) => {}
88            Some(Err(e)) => return Err(e),
89            None => return Err(ParseError::IncompleteFrame),
90        }
91    }
92    Ok(out)
93}
94
95/// Validate UTF-8 in newline-aligned slices, in parallel when available.
96///
97/// A newline byte never occurs inside a multi-byte UTF-8 sequence, so
98/// slices cut just after a `\n` validate independently.
99pub fn validate_utf8_sliced(bytes: &[u8]) -> Result<&str, std::str::Utf8Error> {
100    const MIN_SLICE: usize = 8 << 20;
101    let n_slices = (bytes.len() / MIN_SLICE).max(1);
102    let mut cuts = Vec::with_capacity(n_slices + 1);
103    cuts.push(0usize);
104    for k in 1..n_slices {
105        let target = k * bytes.len() / n_slices;
106        let prev = *cuts.last().unwrap();
107        if target <= prev {
108            continue;
109        }
110        match memchr::memchr(b'\n', &bytes[target..]) {
111            Some(p) => cuts.push(target + p + 1),
112            None => break,
113        }
114    }
115    cuts.push(bytes.len());
116    cuts.dedup();
117    let check = |w: &[usize]| -> Result<(), std::str::Utf8Error> {
118        std::str::from_utf8(&bytes[w[0]..w[1]]).map(|_| ())
119    };
120    #[cfg(feature = "parallel")]
121    {
122        use rayon::prelude::*;
123        let windows: Vec<&[usize]> = cuts.windows(2).collect();
124        windows.par_iter().try_for_each(|w| check(w))?;
125    }
126    #[cfg(not(feature = "parallel"))]
127    {
128        for w in cuts.windows(2) {
129            check(w)?;
130        }
131    }
132    // SAFETY: every byte lies in exactly one validated slice, and slice
133    // boundaries sit after ASCII newlines, so the whole buffer is UTF-8.
134    Ok(unsafe { std::str::from_utf8_unchecked(bytes) })
135}
136
137/// Path of the sidecar for `path`: `foo.con` becomes `foo.con.rcidx`.
138pub fn sidecar_path(path: &Path) -> PathBuf {
139    let mut s = path.as_os_str().to_owned();
140    s.push(".rcidx");
141    PathBuf::from(s)
142}
143
144fn fnv1a(mut h: u64, bytes: &[u8]) -> u64 {
145    for &b in bytes {
146        h ^= b as u64;
147        h = h.wrapping_mul(0x0000_0100_0000_01b3);
148    }
149    h
150}
151const FNV_OFFSET: u64 = 0xcbf2_9ce4_8422_2325;
152
153#[derive(Debug, Clone, Copy, PartialEq, Eq)]
154struct Fingerprint {
155    size: u64,
156    mtime_ns: u64,
157    edges: u64,
158}
159
160fn fingerprint(path: &Path) -> io::Result<Fingerprint> {
161    let mut f = std::fs::File::open(path)?;
162    let meta = f.metadata()?;
163    let size = meta.len();
164    let mtime_ns = meta
165        .modified()
166        .ok()
167        .and_then(|t| t.duration_since(std::time::UNIX_EPOCH).ok())
168        .map(|d| d.as_nanos() as u64)
169        .unwrap_or(0);
170    let mut buf = vec![0u8; EDGE.min(size) as usize];
171    f.read_exact(&mut buf)?;
172    let mut h = fnv1a(FNV_OFFSET, &buf);
173    let tail = EDGE.min(size);
174    f.seek(SeekFrom::Start(size - tail))?;
175    buf.resize(tail as usize, 0);
176    f.read_exact(&mut buf)?;
177    h = fnv1a(h, &buf);
178    Ok(Fingerprint {
179        size,
180        mtime_ns,
181        edges: h,
182    })
183}
184
185fn encode(fp: Fingerprint, idx: &FrameIndex) -> Vec<u8> {
186    let mut out = Vec::with_capacity(HEADER_LEN + 8 * idx.offsets.len() + 8);
187    out.extend_from_slice(MAGIC);
188    out.extend_from_slice(&VERSION.to_le_bytes());
189    out.extend_from_slice(&0u32.to_le_bytes());
190    out.extend_from_slice(&fp.size.to_le_bytes());
191    out.extend_from_slice(&fp.mtime_ns.to_le_bytes());
192    out.extend_from_slice(&fp.edges.to_le_bytes());
193    out.extend_from_slice(&(idx.offsets.len() as u64).to_le_bytes());
194    for o in &idx.offsets {
195        out.extend_from_slice(&o.to_le_bytes());
196    }
197    let sum = fnv1a(FNV_OFFSET, &out);
198    out.extend_from_slice(&sum.to_le_bytes());
199    out
200}
201
202fn u64_at(b: &[u8], at: usize) -> u64 {
203    u64::from_le_bytes(b[at..at + 8].try_into().unwrap())
204}
205
206/// Decode a sidecar and check it against `fp`; `None` means stale or corrupt.
207fn decode(bytes: &[u8], fp: Fingerprint) -> Option<FrameIndex> {
208    if bytes.len() < HEADER_LEN + 8 || &bytes[..8] != MAGIC {
209        return None;
210    }
211    if u32::from_le_bytes(bytes[8..12].try_into().unwrap()) != VERSION {
212        return None;
213    }
214    let body = &bytes[..bytes.len() - 8];
215    if fnv1a(FNV_OFFSET, body) != u64_at(bytes, bytes.len() - 8) {
216        return None;
217    }
218    let stored = Fingerprint {
219        size: u64_at(bytes, 16),
220        mtime_ns: u64_at(bytes, 24),
221        edges: u64_at(bytes, 32),
222    };
223    if stored != fp {
224        return None;
225    }
226    let n = u64_at(bytes, 40) as usize;
227    if body.len() != HEADER_LEN + 8 * n {
228        return None;
229    }
230    let offsets: Vec<u64> = (0..n).map(|i| u64_at(bytes, HEADER_LEN + 8 * i)).collect();
231    let ordered = offsets.windows(2).all(|w| w[0] < w[1]);
232    if !ordered || offsets.last().is_some_and(|&o| o >= fp.size) {
233        return None;
234    }
235    Some(FrameIndex {
236        offsets,
237        data_len: fp.size,
238    })
239}
240
241/// Read the sidecar for `path` if it exists and matches the data file.
242pub fn read_sidecar(path: &Path) -> io::Result<Option<FrameIndex>> {
243    let bytes = match std::fs::read(sidecar_path(path)) {
244        Ok(b) => b,
245        Err(e) if e.kind() == io::ErrorKind::NotFound => return Ok(None),
246        Err(e) => return Err(e),
247    };
248    Ok(decode(&bytes, fingerprint(path)?))
249}
250
251/// Write the sidecar for `path` atomically (temp file plus rename).
252pub fn write_sidecar(path: &Path, idx: &FrameIndex) -> io::Result<()> {
253    let fp = fingerprint(path)?;
254    if fp.size != idx.data_len {
255        return Err(io::Error::new(
256            io::ErrorKind::InvalidInput,
257            "frame index length does not match the data file size",
258        ));
259    }
260    let dst = sidecar_path(path);
261    let mut tmp = dst.as_os_str().to_owned();
262    tmp.push(".tmp");
263    let tmp = PathBuf::from(tmp);
264    {
265        let mut f = std::fs::File::create(&tmp)?;
266        f.write_all(&encode(fp, idx))?;
267        f.sync_all()?;
268    }
269    std::fs::rename(&tmp, &dst)
270}
271
272/// Return a trusted index for `text` (the contents of `path`).
273///
274/// Uses the sidecar when it is valid; otherwise scans and, when
275/// `write_back` is set, refreshes the sidecar (write errors are ignored,
276/// so read-only directories still work).
277pub fn load_or_build(path: &Path, text: &str, write_back: bool) -> Result<FrameIndex, ParseError> {
278    if let Ok(Some(idx)) = read_sidecar(path) {
279        if idx.data_len == text.len() as u64 {
280            return Ok(idx);
281        }
282    }
283    let idx = FrameIndex::scan(text)?;
284    if write_back {
285        let _ = write_sidecar(path, &idx);
286    }
287    Ok(idx)
288}
289
290#[cfg(test)]
291mod tests {
292    use super::*;
293
294    fn fixture(n: usize) -> String {
295        let one = std::fs::read_to_string(concat!(
296            env!("CARGO_MANIFEST_DIR"),
297            "/resources/test/tiny_cuh2.con"
298        ))
299        .unwrap();
300        one.repeat(n)
301    }
302
303    #[test]
304    fn checked_scan_matches_legacy_scan() {
305        let text = fixture(7);
306        let legacy = crate::iterators::frame_start_offsets(&text);
307        assert_eq!(frame_start_offsets_checked(&text).unwrap(), legacy);
308        assert_eq!(legacy.len(), 7);
309    }
310
311    #[test]
312    fn checked_scan_reports_truncation() {
313        let text = fixture(3);
314        let cut = &text[..text.len() - 40];
315        assert!(frame_start_offsets_checked(cut).is_err());
316    }
317
318    #[test]
319    fn sliced_utf8_matches_std() {
320        let mut s = "é\n".repeat(5 << 20);
321        s.push_str("ü end\n");
322        assert!(validate_utf8_sliced(s.as_bytes()).is_ok());
323        let mut bad = s.into_bytes();
324        let mid = bad.len() / 2;
325        bad[mid] = 0xff;
326        assert!(validate_utf8_sliced(&bad).is_err());
327    }
328
329    #[test]
330    fn sidecar_roundtrip_and_staleness() {
331        let dir = std::env::temp_dir().join(format!("rcidx-test-{}", std::process::id()));
332        std::fs::create_dir_all(&dir).unwrap();
333        let con = dir.join("t.con");
334        let text = fixture(5);
335        std::fs::write(&con, &text).unwrap();
336        let idx = load_or_build(&con, &text, true).unwrap();
337        assert_eq!(read_sidecar(&con).unwrap(), Some(idx.clone()));
338        for i in 0..idx.len() {
339            let r = idx.range(i).unwrap();
340            assert!(
341                crate::iterators::ConFrameIterator::new(&text[r])
342                    .next()
343                    .unwrap()
344                    .is_ok()
345            );
346        }
347        // Corrupt one offset byte: checksum must reject it.
348        let side = sidecar_path(&con);
349        let mut b = std::fs::read(&side).unwrap();
350        b[HEADER_LEN] ^= 1;
351        std::fs::write(&side, &b).unwrap();
352        assert_eq!(read_sidecar(&con).unwrap(), None);
353        // Change the data file: fingerprint must reject the old sidecar.
354        write_sidecar(&con, &idx).unwrap();
355        let text2 = fixture(6);
356        std::fs::write(&con, &text2).unwrap();
357        assert_eq!(read_sidecar(&con).unwrap(), None);
358        assert_eq!(load_or_build(&con, &text2, true).unwrap().len(), 6);
359        let _ = std::fs::remove_dir_all(&dir);
360    }
361}
readcon_core/frame_index.rs

readcon_core/
frame_index.rs
