FastCDC chunking with a pinned gear table; oxy checkout with checkout-safety rules f9c98deef326

//! FastCDC content-defined chunking (spec §13.2).

//!

//! Parameters: 32 KiB minimum, 64 KiB target, 256 KiB maximum, normalized

//! chunking level 2. The gear table is derived from BLAKE3 so that every

//! implementation produces identical chunk boundaries:

//! `GEAR[i] = u64::from_le_bytes(XOF("oxy1 fastcdc gear")[8*i .. 8*i+8])`.

//! The masks have `16 + 2` and `16 - 2` one-bits spread evenly over 64 bits

//! (see `spread_mask`). Cut-point skipping starts hashing at the minimum size,

//! as in the FastCDC paper (Xia et al., 2016).

use std::sync::OnceLock;

pub const MIN_SIZE: usize = 32 * 1024;

pub const AVG_SIZE: usize = 64 * 1024;

pub const MAX_SIZE: usize = 256 * 1024;

const AVG_BITS: u32 = 16; // log2(AVG_SIZE)

const NORMALIZATION: u32 = 2;

pub const GEAR_SEED: &[u8] = b"oxy1 fastcdc gear";

fn gear() -> &'static [u64; 256] {

    static GEAR: OnceLock<[u64; 256]> = OnceLock::new();

    GEAR.get_or_init(|| {

        let mut out = [0u8; 256 * 8];

        blake3::Hasher::new().update(GEAR_SEED).finalize_xof().fill(&mut out);

        let mut g = [0u64; 256];

        for (i, v) in g.iter_mut().enumerate() {

            *v = u64::from_le_bytes(out[i * 8..i * 8 + 8].try_into().unwrap());

        }

        g

    })

}

/// A mask with `ones` one-bits at bit positions `63 - floor(i * 64 / ones)`.

pub const fn spread_mask(ones: u32) -> u64 {

    let mut m = 0u64;

    let mut i = 0;

    while i < ones {

        m |= 1u64 << (63 - (i * 64 / ones));

        i += 1;

    }

    m

}

pub const MASK_S: u64 = spread_mask(AVG_BITS + NORMALIZATION);

pub const MASK_L: u64 = spread_mask(AVG_BITS - NORMALIZATION);

/// Length of the first chunk of `data`.

pub fn cut_point(data: &[u8]) -> usize {

    let g = gear();

    let mut n = data.len();

    if n <= MIN_SIZE {

        return n;

    }

    let mut normal = AVG_SIZE;

    if n >= MAX_SIZE {

        n = MAX_SIZE;

    } else if n <= normal {

        normal = n;

    }

    let mut hash: u64 = 0;

    let mut i = MIN_SIZE;

    while i < normal {

        hash = (hash << 1).wrapping_add(g[data[i] as usize]);

        if hash & MASK_S == 0 {

            return i;

        }

        i += 1;

    }

    while i < n {

        hash = (hash << 1).wrapping_add(g[data[i] as usize]);

        if hash & MASK_L == 0 {

            return i;

        }

        i += 1;

    }

    n

}

/// Split `data` into chunks; the concatenation of the result is `data`.

pub fn chunks(data: &[u8]) -> Vec<&[u8]> {

    let mut out = Vec::new();

    let mut rest = data;

    while !rest.is_empty() {

        let n = cut_point(rest);

        out.push(&rest[..n]);

        rest = &rest[n..];

    }

    out

}

#[cfg(test)]

mod tests {

    use super::*;

    use rand::{RngCore, SeedableRng};

    fn random(len: usize, seed: u64) -> Vec<u8> {

        let mut v = vec![0u8; len];

        rand::rngs::StdRng::seed_from_u64(seed).fill_bytes(&mut v);

        v

    }

    #[test]

    fn masks_and_gear_are_pinned() {

        assert_eq!(MASK_S.count_ones(), 18);

        assert_eq!(MASK_L.count_ones(), 14);

        assert_eq!(MASK_S & (1 << 63), 1 << 63);

        // Pin the first gear entry so the table cannot drift silently.

        let mut out = [0u8; 8];

        blake3::Hasher::new().update(GEAR_SEED).finalize_xof().fill(&mut out);

        assert_eq!(gear()[0], u64::from_le_bytes(out));

        assert_ne!(gear()[1], gear()[2]);

    }

    #[test]

    fn small_inputs_are_one_chunk() {

        assert!(chunks(b"").is_empty());

        assert_eq!(chunks(b"abc"), vec![&b"abc"[..]]);

        let d = random(MIN_SIZE, 1);

        assert_eq!(chunks(&d).len(), 1);

    }

    #[test]

    fn bounds_and_reassembly() {

        let d = random(3 * 1024 * 1024, 2);

        let cs = chunks(&d);

        assert!(cs.len() > 10, "{}", cs.len());

        let total: usize = cs.iter().map(|c| c.len()).sum();

        assert_eq!(total, d.len());

        assert_eq!(cs.concat(), d);

        for (i, c) in cs.iter().enumerate() {

            assert!(c.len() <= MAX_SIZE);

            if i + 1 < cs.len() {

                assert!(c.len() >= MIN_SIZE, "chunk {i} is {} bytes", c.len());

            }

        }

        let avg = total / cs.len();

        assert!(avg > MIN_SIZE && avg < MAX_SIZE, "average {avg}");

        assert_eq!(chunks(&d), cs, "deterministic");

    }

    #[test]

    fn insertion_only_disturbs_local_chunks() {

        let d = random(2 * 1024 * 1024, 3);

        let mut e = d.clone();

        e.splice(1_000_000..1_000_000, random(100, 4));

        let a: std::collections::HashSet<[u8; 32]> = chunks(&d).iter().map(|c| *blake3::hash(c).as_bytes()).collect();

        let b: Vec<[u8; 32]> = chunks(&e).iter().map(|c| *blake3::hash(c).as_bytes()).collect();

        let shared = b.iter().filter(|h| a.contains(*h)).count();

        assert!(shared * 10 >= b.len() * 8, "only {shared} of {} chunks shared", b.len());

    }

    #[test]

    fn adversarial_constant_input_hits_bounds() {

        let zeros = vec![0u8; 1024 * 1024];

        let cs = chunks(&zeros);

        for c in &cs[..cs.len() - 1] {

            assert!(c.len() >= MIN_SIZE && c.len() <= MAX_SIZE);

        }

        assert!(cs.len() >= 1024 * 1024 / MAX_SIZE);

        assert!(cs.len() <= 1024 * 1024 / MIN_SIZE + 1);

    }

}

pub mod chunk;

//! is `ObjectRef::ZERO`), packs, checkpoints, multiple workspaces, remotes,

//! and resolving conflicts by editing markers.

            chunks: crate::chunk::chunks(content).into_iter().map(|c| hash_object(ObjectType::Chunk, c)).collect(),

        for c in crate::chunk::chunks(content) {

    /// Move the working copy to the state whose heads are `heads` (spec §12.3):

    /// the working directory is rewritten to that state and a fresh

    /// working-copy change is started on it. The bookmark does not move.

    pub fn checkout(&self, heads: &[ChangeHash], discard: bool, command: &str) -> Result<CheckoutReport> {

        let snap = self.snapshot(command)?;

        if !discard && (!snap.wc.tree_ops.is_empty() || !snap.wc.edits.is_empty()) {

            return fail("the working copy has changes; commit them first or pass --discard");

        }

        let target_state = self.load_state(heads)?;

        let heads = target_state.maximal(heads);

        let target = target_state.materialize();

        let current = self.walk_working_copy()?;

        let mut report = CheckoutReport::default();

        // Remove tracked paths that the target does not have.

        let mut dirs_to_prune: BTreeSet<PathBuf> = BTreeSet::new();

        for path in current.keys() {

            if !target.files.contains_key(path) {

                let full = self.safe_path(path)?;

                fs::remove_file(&full)?;

                report.removed += 1;

                if let Some(parent) = full.parent() {

                    dirs_to_prune.insert(parent.to_path_buf());

                }

            }

        }

        // Write target files that differ.

        for (path, f) in &target.files {

            match &f.content {

                FileContent::Dir => continue,

                FileContent::Text { bytes, .. } => {

                    let same = current.get(path).is_some_and(|c| c.kind == NodeKind::File && &c.content == bytes && c.exec == f.mode.exec);

                    if !same {

                        self.write_file(path, bytes, f.mode.exec)?;

                        report.written += 1;

                    }

                }

                FileContent::Opaque { blobs } => {

                    let Some(blob) = blobs.first() else { continue };

                    let bytes = self.read_blob(blob)?;

                    if f.kind == NodeKind::Symlink {

                        let same = current.get(path).is_some_and(|c| c.kind == NodeKind::Symlink && c.content == bytes);

                        if !same {

                            self.write_symlink(path, &bytes)?;

                            report.written += 1;

                        }

                    } else {

                        let same = current.get(path).is_some_and(|c| c.kind == NodeKind::File && c.content == bytes && c.exec == f.mode.exec);

                        if !same {

                            self.write_file(path, &bytes, f.mode.exec)?;

                            report.written += 1;

                        }

                    }

                    if blobs.len() > 1 {

                        for (i, b) in blobs.iter().enumerate().skip(1) {

                            self.write_file(&format!("{path}.oxy-conflict-{}", i + 1), &self.read_blob(b)?, f.mode.exec)?;

                        }

                    }

                }

            }

        }

        // Prune directories left empty, deepest first.

        for d in dirs_to_prune.iter().rev() {

            let mut d = d.clone();

            while d != self.root && fs::read_dir(&d).map(|mut i| i.next().is_none()).unwrap_or(false) {

                fs::remove_dir(&d)?;

                let Some(p) = d.parent() else { break };

                d = p.to_path_buf();

            }

        }

        let (op_ref, op) = self.head_op()?;

        let wc = self.new_working_copy(heads, "");

        let wc_hash = self.store.put_change(&wc)?;

        let mut view = op.view.clone();

        view.workspaces.insert(self.workspace, wc_hash);

        self.record_op(&[op_ref], command, view)?;

        report.conflicted = target.is_conflicted();

        Ok(report)

    }

    /// The absolute path for a repository path, refusing anything that would

    /// escape the workspace or write through a symlink (spec §7.7).

    fn safe_path(&self, rel: &str) -> Result<PathBuf> {

        let mut full = self.root.clone();

        let comps: Vec<&str> = rel.split('/').collect();

        for (i, comp) in comps.iter().enumerate() {

            if comp.is_empty() || *comp == "." || *comp == ".." || comp.contains('\\') {

                return fail(format!("refusing unsafe path {rel:?}"));

            }

            if i == 0 && *comp == OXY_DIR {

                return fail(format!("refusing to write inside {OXY_DIR}: {rel:?}"));

            }

            if i + 1 < comps.len() {

                full.push(comp);

                if let Ok(m) = fs::symlink_metadata(&full) {

                    if m.file_type().is_symlink() {

                        return fail(format!("refusing to write through symlink {}", full.display()));

                    }

                }

            } else {

                full.push(comp);

            }

        }

        Ok(full)

    }

    fn write_file(&self, rel: &str, bytes: &[u8], exec: bool) -> Result<()> {

        let full = self.safe_path(rel)?;

        if let Some(parent) = full.parent() {

            fs::create_dir_all(parent)?;

        }

        if fs::symlink_metadata(&full).is_ok_and(|m| m.file_type().is_symlink() || m.is_dir()) {

            remove_any(&full)?;

        }

        fs::write(&full, bytes)?;

        set_executable(&full, exec)?;

        Ok(())

    }

    fn write_symlink(&self, rel: &str, target: &[u8]) -> Result<()> {

        let full = self.safe_path(rel)?;

        if let Some(parent) = full.parent() {

            fs::create_dir_all(parent)?;

        }

        if fs::symlink_metadata(&full).is_ok() {

            remove_any(&full)?;

        }

        #[cfg(unix)]

        {

            std::os::unix::fs::symlink(String::from_utf8_lossy(target).as_ref(), &full)?;

            Ok(())

        }

        #[cfg(not(unix))]

        {

            // Spec §7.7: without symlink support, write the target as a plain file.

            fs::write(&full, target)?;

            Ok(())

        }

    }

#[derive(Debug, Default, Clone, PartialEq, Eq)]

pub struct CheckoutReport {

    pub written: usize,

    pub removed: usize,

    pub conflicted: bool,

}

fn remove_any(path: &Path) -> std::io::Result<()> {

    let m = fs::symlink_metadata(path)?;

    if m.is_dir() { fs::remove_dir_all(path) } else { fs::remove_file(path) }

}

fn set_executable(path: &Path, exec: bool) -> std::io::Result<()> {

    use std::os::unix::fs::PermissionsExt;

    let mut perms = fs::metadata(path)?.permissions();

    let mode = perms.mode();

    let want = if exec { mode | 0o111 } else { mode & !0o111 };

    if want != mode {

        perms.set_mode(want);

        fs::set_permissions(path, perms)?;

    }

    Ok(())

}

#[cfg(not(unix))]

fn set_executable(_path: &Path, _exec: bool) -> std::io::Result<()> {

    Ok(())

}

#[cfg(unix)]

    fn checkout_moves_the_working_copy() {

        let dir = tempfile::tempdir().unwrap();

        let root = dir.path();

        let repo = Repo::init(root).unwrap();

        write(root, "a.txt", b"one\n");

        write(root, "sub/deep/b.txt", b"b\n");

        let h1 = repo.commit("first", &[]).unwrap();

        write(root, "a.txt", b"two\n");

        fs::remove_file(root.join("sub/deep/b.txt")).unwrap();

        write(root, "bin.dat", &[0, 1, 2, 3]);

        let h2 = repo.commit("second", &[]).unwrap();

        let r = repo.checkout(&[h1], false, "oxy checkout").unwrap();

        assert_eq!(r, CheckoutReport { written: 2, removed: 1, conflicted: false });

        assert_eq!(fs::read(root.join("a.txt")).unwrap(), b"one\n");

        assert_eq!(fs::read(root.join("sub/deep/b.txt")).unwrap(), b"b\n");

        assert!(!root.join("bin.dat").exists());

        let (_, wc) = repo.working_copy().unwrap();

        assert_eq!(wc.deps, vec![h1]);

        assert!(!repo.snapshot("status").unwrap().changed, "checkout leaves a clean working copy");

        // The bookmark still points at h2.

        assert_eq!(repo.bookmark_heads().unwrap(), vec![h2]);

        // Dirty working copy refuses without --discard.

        write(root, "a.txt", b"dirty\n");

        assert!(repo.checkout(&[h2], false, "oxy checkout").is_err());

        let r = repo.checkout(&[h2], true, "oxy checkout --discard").unwrap();

        assert_eq!(fs::read(root.join("a.txt")).unwrap(), b"two\n");

        assert_eq!(fs::read(root.join("bin.dat")).unwrap(), [0, 1, 2, 3]);

        assert!(!root.join("sub").exists(), "empty directories are pruned");

        assert_eq!(r.removed, 1);

        assert!(!repo.snapshot("status").unwrap().changed);

        // Refuses to write through a symlinked directory.

        #[cfg(unix)]

        {

            fs::remove_dir_all(root.join("sub")).ok();

            std::os::unix::fs::symlink("/tmp", root.join("sub")).unwrap();

            assert!(repo.checkout(&[h1], true, "oxy checkout").is_err());

        }

    }

    #[test]

    fn large_files_are_chunked_and_read_back() {

        let dir = tempfile::tempdir().unwrap();

        let repo = Repo::init(dir.path()).unwrap();

        let mut big = vec![0u8; 700 * 1024];

        for (i, b) in big.iter_mut().enumerate() {

            *b = (i as u32).wrapping_mul(2654435761).to_le_bytes()[0];

        }

        let r = repo.store_blob(&big).unwrap();

        let blob = Blob::decode(&repo.store().get_typed(&r, ObjectType::Blob).unwrap()).unwrap();

        assert!(blob.chunks.len() >= 3, "{}", blob.chunks.len());

        assert_eq!(repo.read_blob(&r).unwrap(), big);

        assert_eq!(Repo::blob_ref(&big), r);

    }

    #[test]

File content is split with FastCDC (Xia et al., 2016) using a 32 KiB minimum, 64 KiB target, and 256 KiB maximum chunk size, with normalized chunking level 2 and cut-point skipping from the minimum size. Files of 32 KiB or less are a single chunk, and the final chunk of a file may be shorter than the minimum. The minimum and maximum bounds guarantee that adversarial content produces at most `len / 32 KiB` chunks and at least `len / 256 KiB` chunks, bounding both index growth and dedup loss.

So that every implementation produces identical boundaries, the parameters are fixed:

- **Gear table.** `GEAR[i]` for `i` in `0..256` is the little-endian `u64` at bytes `8i..8i+8` of the BLAKE3 extendable output of the ASCII string `oxy1 fastcdc gear`.

- **Rolling hash.** `h = (h << 1) + GEAR[byte]` in 64-bit wrapping arithmetic, starting from zero at the minimum size.

- **Masks.** A mask with `k` one-bits has them at bit positions `63 - floor(i * 64 / k)` for `i` in `0..k`. The small mask has 18 one-bits (used until the target size) and the large mask has 14 (used until the maximum). A cut occurs at the first position where `h & mask == 0`.

*Changelog.* Draft 0.4a (2026-09-26): §13.2 pins the FastCDC gear table, rolling hash, and masks so boundaries are identical across implementations.

Draft 0.4 (2026-09-26): overview no longer describes the constrained profile by word size; HLC drift bound replaces timestamp-based rejection; node kinds reduced to file, dir, symlink with a separate content mode and defined mode switching; symlinks always opaque; checkout safety rules (§7.7); workspace conflicts (§9.7) replace the case-folding tree conflict and cover normalization, reserved names, and path length; operation log entries suppressed for empty snapshots.

    /// Move the working copy to the state formed by CHANGE... (default: the bookmark heads)

    Checkout {

        changes: Vec<String>,

        /// Throw away uncommitted working-copy changes

        #[arg(long)]

        discard: bool,

    },

        Cmd::Checkout { changes, discard } => {

            let repo = open()?;

            let heads = if changes.is_empty() {

                repo.bookmark_heads()?

            } else {

                changes.iter().map(|c| repo.resolve_change(c)).collect::<Result<Vec<_>, _>>()?

            };

            let spec = if changes.is_empty() { repo.config.bookmark.clone() } else { changes.join(" ") };

            let r = repo.checkout(&heads, discard, &format!("oxy checkout {spec}"))?;

            println!("Working copy now on {spec}: {} file(s) written, {} removed", r.written, r.removed);

            if r.conflicted {

                println!("This state has conflicts; see oxy status.");

            }

            Ok(0)

        }