Skip to main content

tpt_basestation_littlefs/
lib.rs

1//! Pure-Rust LittleFS v2 implementation.
2//!
3//! This module implements the LittleFS v2 on-disk metadata format without any C
4//! dependencies. Phase 1 covered read-only access to the root directory's metadata
5//! pair (blocks 0/1), including inline file data. Phase 1b adds subdirectory
6//! traversal by following each directory entry's `DIRSTRUCT` tag to its child
7//! metadata pair, and decodes CTZ skip-lists for files too large to fit inline.
8//! Phase 2 adds write support — `write_file`/`delete_file`/`rename_file` — real
9//! device-round-trip verified (see `TODO.md`). All three accept a `/`-joined
10//! path and operate inside any **already-existing** directory (root or
11//! nested), not just root; `rename_file` is same-directory only (no
12//! cross-directory moves). `write_file` transparently picks inline vs.
13//! CTZ-skip-list encoding based on size (`LittleFs::INLINE_MAX`), so large
14//! files are supported too — this is the one operation that needs to find
15//! blocks to put the new data in, via `used_blocks`/`allocate_free_blocks`,
16//! since littlefs keeps no on-disk free-block bitmap: the only safe way to
17//! find an unused block is scanning every metadata pair and every file's CTZ
18//! chain in the *entire* filesystem for what's referenced, and treating
19//! everything else as free. That scan is a meaningfully bigger risk surface
20//! than every other write operation here (which only ever rewrite an
21//! already-known, already-referenced pair in place) — see the real-hardware
22//! verification notes in `TODO.md` for how this was checked before ever
23//! writing a large file to a real device. One thing remains deliberately out
24//! of scope: **no directory creation** — writing into a path whose directory
25//! doesn't exist yet errors, since a brand-new directory's metadata pair would
26//! also need two blocks from that same allocator, and (unlike a file, whose
27//! only reference is the one CTZSTRUCT tag this writer itself just wrote) a
28//! new subdirectory immediately becomes something *other* code could try to
29//! resolve into mid-construction — not worth the added complexity for this
30//! pass.
31//!
32//! Byte layout verified against the real `mklittlefs` reference tool (bundled with
33//! the ESP32 Arduino board package) by building known-content images (including a
34//! subdirectory and a >1KB file) and comparing this reader's output byte-for-byte
35//! against `mklittlefs -l`'s ground truth and the original source files. In
36//! particular, the CTZ skip-list algorithm below (pointer count `ctz(n) + 1` per
37//! block index `n`, backward traversal via each block's first pointer) was derived
38//! by hex-dumping a real 2-block and a real 5-block file and matching offsets
39//! against the pre-image source bytes, not guessed from the spec text alone. The
40//! write path's CRC/FCRC tag encoding was derived the same way: by brute-forcing
41//! candidate algorithms/byte ranges against a real image's stored values until an
42//! exact match was found, then cross-checking the result by having the real
43//! `mklittlefs -u`/`-l` tool itself read back files this writer produced.
44//!
45//! Reference: <https://github.com/littlefs-project/littlefs/blob/master/SPEC.md>
46
47use std::collections::HashSet;
48
49/// LittleFS v2 metadata-block layout constants.
50pub mod superblock {
51    /// Logical block size this reader assumes when chunking a partition image.
52    /// Cross-checked against the superblock's own reported `block_size` field
53    /// during parsing; a mismatch is reported as `LittleFsError::BlockSizeMismatch`.
54    pub const BLOCK_SIZE: usize = 4096;
55
56    /// Highest on-disk major version this reader understands. LittleFS's disk
57    /// format is backward compatible within a major version, so any minor version
58    /// under this major is accepted (the previous implementation incorrectly
59    /// rejected the real reference tool's own output — v2.1 — because it compared
60    /// against the full 2.0.0 constant instead of just the major version).
61    pub const MAX_MAJOR_VERSION: u32 = 2;
62}
63
64/// Tag type constants for LittleFS metadata-pair tags (see SPEC.md's "Metadata
65/// tags" section). Tags are 32-bit big-endian words, XOR-chained together within
66/// a block starting from `0xffffffff`, encoding a 1-bit parity flag, an 11-bit
67/// type, a 10-bit id, and a 10-bit length: `[1][type:11][id:10][len:10]`.
68pub mod tag {
69    /// Superblock name entry (id 0 in the root metadata pair), payload is the
70    /// literal ASCII string `"littlefs"` — this, not a numeric constant, is the
71    /// real on-disk magic.
72    pub const SUPERBLOCK: u32 = 0x0ff;
73    /// Regular file name entry.
74    pub const REG: u32 = 0x001;
75    /// Directory name entry.
76    pub const DIR: u32 = 0x002;
77    /// Creates a new id in the directory (shifts subsequent ids up by one).
78    pub const CREATE: u32 = 0x401;
79    /// Deletes an id from the directory (shifts subsequent ids down by one).
80    pub const DELETE: u32 = 0x4ff;
81    /// Inline file data (small files) or the superblock's own config struct
82    /// (24 bytes: version, block_size, block_count, name_max, file_max, attr_max)
83    /// when associated with id 0.
84    pub const INLINESTRUCT: u32 = 0x201;
85    /// CTZ skip-list pointer for files too large to store inline. Payload is
86    /// `[head_block: u32 LE][file_size: u32 LE]`.
87    pub const CTZSTRUCT: u32 = 0x202;
88    /// Directory-struct pointer: the child directory's own metadata-pair block
89    /// numbers. Payload is `[block_a: u32 LE][block_b: u32 LE]`.
90    pub const DIRSTRUCT: u32 = 0x200;
91    /// User-attribute type family (`0x300 | attr_char`); we only care about the
92    /// `'t'` (0x74) mtime attribute that `mklittlefs`/Arduino's LittleFS set.
93    pub const USERATTR_FAMILY_MASK: u32 = 0x700;
94    pub const USERATTR_FAMILY: u32 = 0x300;
95    pub const MTIME_ATTR: u32 = b't' as u32;
96    /// CRC/FCRC commit-terminator family — not a directory entry, just marks the
97    /// end of a commit within the block.
98    pub const CRC_FAMILY: u32 = 0x500;
99    /// Forward-CRC tag: written just before the terminating `CRC` tag, payload
100    /// `[lookahead_size: u32 LE][crc_of_that_many_erased_bytes: u32 LE]` — an
101    /// assertion about what immediately follows this commit, letting a reader
102    /// sanity-check the block is truly empty there without scanning it.
103    pub const FCRC: u32 = 0x5ff;
104    /// Terminating CRC tag for a commit: payload's first 4 bytes are the
105    /// little-endian CRC32 (no final complement — see `lfs_crc`) of every byte
106    /// of this commit from the block's start through this tag's own 4-byte
107    /// header (not including this payload). A real on-disk commit may pad the
108    /// payload beyond 4 bytes to round out to a fixed alignment; this reader
109    /// and writer both only ever produce/expect exactly 4.
110    pub const CRC: u32 = 0x501;
111    /// Reserved id used by CRC-family tags — not a real directory entry id.
112    pub const CRC_TAG_ID: u32 = 0x3ff;
113    /// Fixed lookahead size (bytes) asserted by the `FCRC` tag, matching the
114    /// value observed in every real `mklittlefs`-built image inspected.
115    pub const FCRC_LOOKAHEAD: usize = 64;
116}
117
118/// A file entry in LittleFS.
119#[derive(Debug, Clone)]
120pub struct FileEntry {
121    pub name: String,
122    pub size: u32,
123    pub mtime: Option<u32>,
124}
125
126/// A directory entry in LittleFS.
127#[derive(Debug, Clone)]
128pub struct DirEntry {
129    pub name: String,
130}
131
132/// A file or directory entry from a directory listing.
133#[derive(Debug, Clone)]
134pub enum FsEntry {
135    File(FileEntry),
136    Dir(DirEntry),
137}
138
139/// Live state for one directory-entry id while replaying a metadata block's
140/// commit log. Id 0 is reserved for the superblock in the root directory and is
141/// never surfaced as a listed entry; in any other directory's metadata pair, id 0
142/// is just an ordinary entry.
143#[derive(Debug, Clone, Default)]
144struct IdState {
145    name: Option<String>,
146    is_dir: bool,
147    inline_data: Option<Vec<u8>>,
148    /// Set instead of `inline_data` when the file uses a CTZ skip-list (too large
149    /// to inline) — `(head_block, size)`.
150    ctz: Option<(u32, u32)>,
151    /// Set for directory entries: the child directory's own metadata-pair block
152    /// numbers, from its `DIRSTRUCT` tag.
153    child_pair: Option<(u32, u32)>,
154    mtime: Option<u32>,
155}
156
157/// A fully-resolved directory entry (file or directory), carrying whatever is
158/// needed to read its contents or descend into it, independent of the public
159/// `FsEntry` shape returned by `list_dir`.
160#[derive(Debug, Clone)]
161struct ResolvedEntry {
162    name: String,
163    is_dir: bool,
164    size: u32,
165    mtime: Option<u32>,
166    child_pair: Option<(u32, u32)>,
167    inline_data: Option<Vec<u8>>,
168    ctz: Option<(u32, u32)>,
169}
170
171/// LittleFS filesystem representation.
172#[derive(Debug, Clone)]
173pub struct LittleFs {
174    /// Raw block data, indexed by block number.
175    blocks: Vec<Vec<u8>>,
176    /// Erase block count.
177    erase_blocks: u32,
178    /// Logical block size.
179    block_size: usize,
180    /// Resolved entries of the root directory (excludes the superblock's own id 0).
181    root_entries: Vec<ResolvedEntry>,
182    /// The root pair's superblock config, retained so writes can re-emit it
183    /// unchanged.
184    superblock: SuperblockInfo,
185}
186
187impl LittleFs {
188    /// Create a new LittleFS from raw partition data.
189    pub fn from_bytes(data: &[u8]) -> Result<Self, LittleFsError> {
190        let block_size = superblock::BLOCK_SIZE;
191
192        if data.len() % block_size != 0 {
193            return Err(LittleFsError::UnalignedPartition);
194        }
195
196        let erase_blocks = data.len() as u32 / block_size as u32;
197        if erase_blocks < 2 {
198            return Err(LittleFsError::Corrupted);
199        }
200
201        let blocks: Vec<Vec<u8>> = data.chunks(block_size).map(|c| c.to_vec()).collect();
202
203        // The root directory's metadata pair is assumed to live at blocks {0, 1}
204        // (Phase 1 scope — see module docs). Of the pair, the block with the
205        // higher revision count is authoritative; comparison is wraparound-aware
206        // since the counter is a plain incrementing u32.
207        let rev0 = read_revision(&blocks[0]);
208        let rev1 = read_revision(&blocks[1]);
209        let (current_idx, other_idx) = if rev1.wrapping_sub(rev0) as i32 > 0 {
210            (1, 0)
211        } else {
212            (0, 1)
213        };
214
215        let mut scan = parse_block(&blocks[current_idx]);
216        if scan.superblock.is_none() {
217            // Fall back to the other block of the pair (e.g. the "current" one
218            // was mid-write and doesn't have a complete superblock commit yet).
219            scan = parse_block(&blocks[other_idx]);
220        }
221
222        let sb = scan
223            .superblock
224            .ok_or(LittleFsError::Corrupted)?;
225
226        if sb.name != "littlefs" {
227            return Err(LittleFsError::BadMagic {
228                expected: "littlefs",
229                actual: sb.name,
230            });
231        }
232
233        let major_version = sb.version >> 16;
234        if major_version > superblock::MAX_MAJOR_VERSION {
235            return Err(LittleFsError::UnsupportedVersion(sb.version));
236        }
237
238        if sb.block_size as usize != block_size {
239            return Err(LittleFsError::BlockSizeMismatch {
240                expected: block_size as u32,
241                actual: sb.block_size,
242            });
243        }
244
245        let mut fs = Self {
246            blocks,
247            erase_blocks,
248            block_size,
249            root_entries: Vec::new(),
250            superblock: sb,
251        };
252        fs.root_entries = fs.scan_dir_pair((0, 1), true)?;
253        Ok(fs)
254    }
255
256    /// Replay one directory's metadata pair into resolved entries. `is_root`
257    /// excludes id 0 (the superblock's own slot, only meaningful for the root
258    /// directory pair at blocks {0,1} — every other directory's id 0 is an
259    /// ordinary entry).
260    fn scan_dir_pair(&self, pair: (u32, u32), is_root: bool) -> Result<Vec<ResolvedEntry>, LittleFsError> {
261        let (a, b) = (pair.0 as usize, pair.1 as usize);
262        let block_a = self.blocks.get(a).ok_or(LittleFsError::Corrupted)?;
263        let block_b = self.blocks.get(b).ok_or(LittleFsError::Corrupted)?;
264
265        let rev_a = read_revision(block_a);
266        let rev_b = read_revision(block_b);
267        let current = if rev_b.wrapping_sub(rev_a) as i32 > 0 { block_b } else { block_a };
268
269        let scan = parse_block(current);
270        let skip = if is_root { 1 } else { 0 };
271
272        let mut entries = Vec::new();
273        for id in scan.ids.into_iter().skip(skip) {
274            let Some(name) = id.name else { continue };
275            let size = id
276                .inline_data
277                .as_ref()
278                .map(|d| d.len() as u32)
279                .or(id.ctz.map(|(_, size)| size))
280                .unwrap_or(0);
281            entries.push(ResolvedEntry {
282                name,
283                is_dir: id.is_dir,
284                size,
285                mtime: id.mtime,
286                child_pair: id.child_pair,
287                inline_data: id.inline_data,
288                ctz: id.ctz,
289            });
290        }
291        Ok(entries)
292    }
293
294    /// Resolve the entries of the directory at `path` (empty or `/` for root),
295    /// following each intermediate directory's `DIRSTRUCT` tag to its child
296    /// metadata pair.
297    fn resolve_dir_entries(&self, path: &str) -> Result<Vec<ResolvedEntry>, LittleFsError> {
298        let trimmed = path.trim_matches('/');
299        if trimmed.is_empty() {
300            return Ok(self.root_entries.clone());
301        }
302
303        let mut current = self.root_entries.clone();
304        for component in trimmed.split('/') {
305            let entry = current
306                .iter()
307                .find(|e| e.is_dir && e.name == component)
308                .ok_or_else(|| LittleFsError::FileNotFound(path.to_string()))?;
309            let pair = entry.child_pair.ok_or(LittleFsError::Corrupted)?;
310            current = self.scan_dir_pair(pair, false)?;
311        }
312        Ok(current)
313    }
314
315    /// Like `resolve_dir_entries`, but also returns the resolved directory's
316    /// own metadata-pair block numbers and whether it's the root pair (which
317    /// reserves id 0 for the superblock) — everything `commit_dir` needs to
318    /// write a fresh commit there. Used by the write/delete/rename paths so
319    /// they work against any already-existing directory, not just root.
320    fn resolve_dir_pair_and_entries(&self, path: &str) -> Result<((u32, u32), bool, Vec<ResolvedEntry>), LittleFsError> {
321        let trimmed = path.trim_matches('/');
322        if trimmed.is_empty() {
323            return Ok(((0, 1), true, self.root_entries.clone()));
324        }
325
326        let mut current = self.root_entries.clone();
327        let mut current_pair = (0u32, 1u32);
328        for component in trimmed.split('/') {
329            let entry = current
330                .iter()
331                .find(|e| e.is_dir && e.name == component)
332                .ok_or_else(|| LittleFsError::FileNotFound(path.to_string()))?;
333            let pair = entry.child_pair.ok_or(LittleFsError::Corrupted)?;
334            current = self.scan_dir_pair(pair, false)?;
335            current_pair = pair;
336        }
337        Ok((current_pair, false, current))
338    }
339
340    /// Split a `/`-joined path into its parent directory path and final component.
341    fn split_parent(path: &str) -> (&str, &str) {
342        let trimmed = path.trim_matches('/');
343        match trimmed.rsplit_once('/') {
344            Some((dir, name)) => (dir, name),
345            None => ("", trimmed),
346        }
347    }
348
349    /// List entries in a directory (read-only). `path` is `/`-joined relative to
350    /// the partition root; empty or `/` lists the root directory.
351    pub fn list_dir(&self, path: &str) -> Result<Vec<FsEntry>, LittleFsError> {
352        let entries = self.resolve_dir_entries(path)?;
353        Ok(entries
354            .into_iter()
355            .map(|e| {
356                if e.is_dir {
357                    FsEntry::Dir(DirEntry { name: e.name })
358                } else {
359                    FsEntry::File(FileEntry {
360                        name: e.name,
361                        size: e.size,
362                        mtime: e.mtime,
363                    })
364                }
365            })
366            .collect())
367    }
368
369    /// Read file contents (read-only). Works for both inline files and files
370    /// stored via a CTZ skip-list (too large to inline).
371    pub fn read_file(&self, path: &str) -> Result<Vec<u8>, LittleFsError> {
372        let (dir_path, file_name) = Self::split_parent(path);
373        let entries = self.resolve_dir_entries(dir_path)?;
374        let entry = entries
375            .iter()
376            .find(|e| !e.is_dir && e.name == file_name)
377            .ok_or_else(|| LittleFsError::FileNotFound(path.to_string()))?;
378
379        if let Some(data) = &entry.inline_data {
380            return Ok(data.clone());
381        }
382        if let Some((head_block, size)) = entry.ctz {
383            return self.read_ctz(head_block, size);
384        }
385        Ok(Vec::new())
386    }
387
388    /// Decode a file's CTZ skip-list into its full contents.
389    ///
390    /// LittleFS stores large files as a chain of data blocks, indexed 0 (first
391    /// written) through N-1 (`head_block`, the last written / most recent).
392    /// Block index `n >= 1` is prefixed with `ctz(n) + 1` little-endian u32
393    /// block-number pointers (`ctz` = trailing zero bits), the first of which
394    /// always points to index `n - 1`; index 0 has no prefix at all. Each
395    /// block's data capacity is therefore `block_size - 4 * pointer_count`,
396    /// with only the head (last) block holding a partial remainder when the file
397    /// size isn't an exact multiple of capacity.
398    ///
399    /// This reads every block's own first pointer to walk backward from the
400    /// head to index 0 (skip-list levels beyond that first pointer exist only to
401    /// let a real device seek without reading every block — a linear walk is
402    /// simpler and this reader always reads the whole file), then reads forward
403    /// concatenating each block's data span.
404    ///
405    /// Verified against `mklittlefs`-built images: a 2-block (5000-byte) and a
406    /// 5-block (20000-byte) file, both reconstructed byte-for-byte against the
407    /// original source file.
408    fn read_ctz(&self, head_block: u32, size: u32) -> Result<Vec<u8>, LittleFsError> {
409        if size == 0 {
410            return Ok(Vec::new());
411        }
412
413        let plan = self.ctz_plan(size)?;
414        let phys_by_index = self.ctz_chain_blocks(head_block, size)?;
415
416        let mut out = Vec::with_capacity(size as usize);
417        for (index, (pointer_count, take)) in plan.into_iter().enumerate() {
418            let phys = phys_by_index[index] as usize;
419            let block = self.blocks.get(phys).ok_or(LittleFsError::Corrupted)?;
420            let start = 4 * pointer_count as usize;
421            let end = start + take;
422            if end > block.len() {
423                return Err(LittleFsError::Corrupted);
424            }
425            out.extend_from_slice(&block[start..end]);
426        }
427        Ok(out)
428    }
429
430    /// Compute the `(pointer_count, data_take)` for each block index of a
431    /// `size`-byte CTZ chain, given this filesystem's block size — the pure
432    /// arithmetic half of the CTZ format, shared by reading (`read_ctz`),
433    /// writing (`write_ctz_chain`), and free-block accounting
434    /// (`ctz_chain_blocks`, `used_blocks`).
435    fn ctz_plan(&self, size: u32) -> Result<Vec<(u32, usize)>, LittleFsError> {
436        let mut plan = Vec::new();
437        let mut n: u32 = 0;
438        let mut offset: usize = 0;
439        while offset < size as usize {
440            let pointer_count = if n == 0 { 0 } else { n.trailing_zeros() + 1 };
441            let capacity = self.block_size.saturating_sub(4 * pointer_count as usize);
442            if capacity == 0 {
443                return Err(LittleFsError::Corrupted);
444            }
445            let take = capacity.min(size as usize - offset);
446            plan.push((pointer_count, take));
447            offset += take;
448            n += 1;
449        }
450        Ok(plan)
451    }
452
453    /// Walk a CTZ chain's physical block numbers in forward (index 0..N-1)
454    /// order, by following each block's own first pointer backward from
455    /// `head_block`. Used both to actually read a file's data and, via
456    /// `used_blocks`, to know which physical blocks a large file currently
457    /// occupies (so free-block allocation never reuses them).
458    fn ctz_chain_blocks(&self, head_block: u32, size: u32) -> Result<Vec<u32>, LittleFsError> {
459        if size == 0 {
460            return Ok(Vec::new());
461        }
462        let total_blocks = self.ctz_plan(size)?.len();
463        let mut phys_by_index = vec![0u32; total_blocks];
464        phys_by_index[total_blocks - 1] = head_block;
465        let mut cur = head_block;
466        for index in (1..total_blocks).rev() {
467            let block = self.blocks.get(cur as usize).ok_or(LittleFsError::Corrupted)?;
468            if block.len() < 4 {
469                return Err(LittleFsError::Corrupted);
470            }
471            let ptr0 = u32::from_le_bytes(block[0..4].try_into().unwrap());
472            phys_by_index[index - 1] = ptr0;
473            cur = ptr0;
474        }
475        Ok(phys_by_index)
476    }
477
478    /// Encode `contents` into a fresh CTZ skip-list chain occupying exactly
479    /// `blocks` (one physical block per chain index, in order — from
480    /// `allocate_free_blocks`), returning the head block number (the chain's
481    /// last index) to store in a `CTZSTRUCT` tag. Every pointer in the chain
482    /// is written correctly, not just index `n-1` (all `read_ctz` itself
483    /// needs), so other implementations that use the full skip list for seeking
484    /// read it correctly too. Unused tail space in the final (head) block is
485    /// padded with `0xFF`, matching real erased-NOR-flash convention (see
486    /// `build_dir_commit`).
487    fn write_ctz_chain(&mut self, contents: &[u8], blocks: &[u32]) -> Result<u32, LittleFsError> {
488        let plan = self.ctz_plan(contents.len() as u32)?;
489        debug_assert_eq!(plan.len(), blocks.len());
490
491        let mut offset = 0usize;
492        for (n, (pointer_count, take)) in plan.iter().enumerate() {
493            let mut block_bytes = Vec::with_capacity(self.block_size);
494            for i in 0..*pointer_count {
495                let target_index = n - (1usize << i);
496                block_bytes.extend_from_slice(&blocks[target_index].to_le_bytes());
497            }
498            block_bytes.extend_from_slice(&contents[offset..offset + take]);
499            offset += take;
500            block_bytes.resize(self.block_size, 0xff);
501
502            let phys = blocks[n] as usize;
503            self.blocks[phys] = block_bytes;
504        }
505        Ok(*blocks.last().expect("CTZ chain always has at least one block"))
506    }
507
508    /// Every block index currently referenced anywhere in the filesystem: the
509    /// root pair, every (sub)directory's own metadata-pair blocks, and every
510    /// file's full CTZ data-block chain. The complement of this set is safe
511    /// to allocate for a new large file — see the module docs for why this
512    /// scan is unavoidable (littlefs keeps no on-disk free-block bitmap).
513    fn used_blocks(&self) -> Result<HashSet<u32>, LittleFsError> {
514        let mut used = HashSet::new();
515        used.insert(0);
516        used.insert(1);
517        self.mark_used_recursive(self.root_entries.clone(), &mut used)?;
518        Ok(used)
519    }
520
521    fn mark_used_recursive(&self, entries: Vec<ResolvedEntry>, used: &mut HashSet<u32>) -> Result<(), LittleFsError> {
522        for entry in entries {
523            if entry.is_dir {
524                if let Some((a, b)) = entry.child_pair {
525                    used.insert(a);
526                    used.insert(b);
527                    let child_entries = self.scan_dir_pair((a, b), false)?;
528                    self.mark_used_recursive(child_entries, used)?;
529                }
530            } else if let Some((head, size)) = entry.ctz {
531                for block in self.ctz_chain_blocks(head, size)? {
532                    used.insert(block);
533                }
534            }
535        }
536        Ok(())
537    }
538
539    /// Find `count` blocks not referenced anywhere in the filesystem,
540    /// suitable for a new large file's data chain. Errors with
541    /// `PartitionFull` if fewer than `count` are available.
542    fn allocate_free_blocks(&self, count: usize) -> Result<Vec<u32>, LittleFsError> {
543        let used = self.used_blocks()?;
544        let mut free = Vec::with_capacity(count);
545        for idx in 0..self.erase_blocks {
546            if !used.contains(&idx) {
547                free.push(idx);
548                if free.len() == count {
549                    return Ok(free);
550                }
551            }
552        }
553        Err(LittleFsError::PartitionFull { needed: count, available: free.len() })
554    }
555
556    /// Get total partition size in bytes.
557    pub fn total_size(&self) -> usize {
558        self.blocks.len() * self.block_size
559    }
560
561    /// Get the number of erase blocks.
562    pub fn erase_block_count(&self) -> u32 {
563        self.erase_blocks
564    }
565
566    /// Check if a file exists at `path` (root or nested).
567    pub fn file_exists(&self, path: &str) -> bool {
568        let (dir_path, file_name) = Self::split_parent(path);
569        self.resolve_dir_entries(dir_path)
570            .map(|entries| entries.iter().any(|e| !e.is_dir && e.name == file_name))
571            .unwrap_or(false)
572    }
573
574    /// Recursively walk the entire filesystem tree. Nested entries' `name` is
575    /// the full `/`-joined path from the root (e.g. `subdir/nested.txt`), since
576    /// a bare filename can't disambiguate entries in different directories.
577    pub fn walk(&self) -> Result<Vec<FsEntry>, LittleFsError> {
578        let mut out = Vec::new();
579        self.walk_into("", &mut out)?;
580        Ok(out)
581    }
582
583    fn walk_into(&self, path: &str, out: &mut Vec<FsEntry>) -> Result<(), LittleFsError> {
584        for entry in self.resolve_dir_entries(path)? {
585            let full_path = if path.is_empty() {
586                entry.name.clone()
587            } else {
588                format!("{path}/{}", entry.name)
589            };
590            if entry.is_dir {
591                out.push(FsEntry::Dir(DirEntry { name: full_path.clone() }));
592                self.walk_into(&full_path, out)?;
593            } else {
594                out.push(FsEntry::File(FileEntry {
595                    name: full_path,
596                    size: entry.size,
597                    mtime: entry.mtime,
598                }));
599            }
600        }
601        Ok(())
602    }
603
604    /// Size threshold (bytes) at which `write_file` switches from inline
605    /// storage to a CTZ skip-list, matching littlefs's own typical default
606    /// `inline_max` of `block_size / 8`.
607    pub const INLINE_MAX: usize = 512;
608
609    /// Create or overwrite a file at `path` with `contents`. `path` may
610    /// address a file inside an **already-existing** subdirectory (e.g.
611    /// `sub/file.txt`) — creating a new subdirectory itself isn't supported,
612    /// since that needs free-block allocation this writer doesn't do (see the
613    /// module docs). Content up to `INLINE_MAX` bytes is stored inline;
614    /// larger content is encoded as a CTZ skip-list, allocating fresh blocks
615    /// via `allocate_free_blocks` (errors with `PartitionFull` if the
616    /// partition doesn't have enough free space). Also errors if the target
617    /// directory doesn't exist, or if a directory already exists with that
618    /// name.
619    pub fn write_file(&mut self, path: &str, contents: &[u8]) -> Result<(), LittleFsError> {
620        let (dir_path, file_name) = Self::split_parent(path);
621        if file_name.is_empty() {
622            return Err(LittleFsError::InvalidName(path.to_string()));
623        }
624
625        let (pair, is_root, mut entries) = self.resolve_dir_pair_and_entries(dir_path)?;
626        if entries.iter().any(|e| e.is_dir && e.name == file_name) {
627            return Err(LittleFsError::NameCollision(file_name.to_string()));
628        }
629
630        let (inline_data, ctz) = if contents.len() <= Self::INLINE_MAX {
631            (Some(contents.to_vec()), None)
632        } else {
633            let plan = self.ctz_plan(contents.len() as u32)?;
634            let blocks = self.allocate_free_blocks(plan.len())?;
635            let head = self.write_ctz_chain(contents, &blocks)?;
636            (None, Some((head, contents.len() as u32)))
637        };
638
639        match entries.iter_mut().find(|e| e.name == file_name) {
640            Some(existing) => {
641                existing.inline_data = inline_data;
642                existing.ctz = ctz;
643                existing.size = contents.len() as u32;
644            }
645            None => {
646                entries.push(ResolvedEntry {
647                    name: file_name.to_string(),
648                    is_dir: false,
649                    size: contents.len() as u32,
650                    mtime: None,
651                    child_pair: None,
652                    inline_data,
653                    ctz,
654                });
655            }
656        }
657        self.commit_dir(pair, is_root, entries)
658    }
659
660    /// Delete a file at `path`, which may be inside an already-existing
661    /// subdirectory. Errors if it doesn't exist as a file (deleting
662    /// directories isn't supported yet).
663    pub fn delete_file(&mut self, path: &str) -> Result<(), LittleFsError> {
664        let (dir_path, file_name) = Self::split_parent(path);
665        let (pair, is_root, mut entries) = self.resolve_dir_pair_and_entries(dir_path)?;
666        let idx = entries
667            .iter()
668            .position(|e| !e.is_dir && e.name == file_name)
669            .ok_or_else(|| LittleFsError::FileNotFound(path.to_string()))?;
670        entries.remove(idx);
671        self.commit_dir(pair, is_root, entries)
672    }
673
674    /// Rename a file at `old_path` to `new_name` **within the same
675    /// directory** (moving a file into a different directory isn't
676    /// supported). Cheap and low-risk given this writer's
677    /// full-compaction-rewrite design: unlike littlefs's own incremental
678    /// append (which uses dedicated create/delete-with-id-shift tags to
679    /// implement rename), every write here already re-emits every entry from
680    /// scratch, so a rename is just changing one entry's `name` before that
681    /// happens — no new tag encoding is needed.
682    pub fn rename_file(&mut self, old_path: &str, new_name: &str) -> Result<(), LittleFsError> {
683        if new_name.is_empty() || new_name.contains('/') {
684            return Err(LittleFsError::InvalidName(new_name.to_string()));
685        }
686        let (dir_path, old_file_name) = Self::split_parent(old_path);
687        let (pair, is_root, mut entries) = self.resolve_dir_pair_and_entries(dir_path)?;
688        if old_file_name != new_name && entries.iter().any(|e| e.name == new_name) {
689            return Err(LittleFsError::NameCollision(new_name.to_string()));
690        }
691        let idx = entries
692            .iter()
693            .position(|e| !e.is_dir && e.name == old_file_name)
694            .ok_or_else(|| LittleFsError::FileNotFound(old_path.to_string()))?;
695        entries[idx].name = new_name.to_string();
696        self.commit_dir(pair, is_root, entries)
697    }
698
699    /// Flatten this filesystem's in-memory blocks back into one raw partition
700    /// image, suitable for pushing back to a device.
701    pub fn to_bytes(&self) -> Vec<u8> {
702        self.blocks.concat()
703    }
704
705    /// Commit a new entry list for the directory whose metadata pair is
706    /// `pair`: builds a fresh single-commit block (superblock included only
707    /// when `is_root`) containing every surviving entry re-numbered
708    /// sequentially, and writes it into whichever of the pair's two blocks is
709    /// **not** currently authoritative — the same alternate-block,
710    /// revision+1 pattern real littlefs uses when compacting, so the other
711    /// block simply becomes stale rather than being touched. Existing
712    /// subdirectories and large (CTZ) files not part of this edit are
713    /// re-emitted with their original `child_pair`/`ctz` pointers untouched,
714    /// so they remain valid without this writer ever needing to touch their
715    /// data blocks. Only ever targets a directory's *existing* pair — creating
716    /// a brand-new directory would need free-block allocation this writer
717    /// doesn't do (see the module docs).
718    fn commit_dir(&mut self, pair: (u32, u32), is_root: bool, entries: Vec<ResolvedEntry>) -> Result<(), LittleFsError> {
719        let (a, b) = (pair.0 as usize, pair.1 as usize);
720        let rev_a = read_revision(self.blocks.get(a).ok_or(LittleFsError::Corrupted)?);
721        let rev_b = read_revision(self.blocks.get(b).ok_or(LittleFsError::Corrupted)?);
722        let (current_rev, target_idx) = if rev_b.wrapping_sub(rev_a) as i32 > 0 {
723            (rev_b, a)
724        } else {
725            (rev_a, b)
726        };
727
728        let new_block = self.build_dir_commit(current_rev.wrapping_add(1), is_root, &entries)?;
729        self.blocks[target_idx] = new_block;
730        if is_root {
731            self.root_entries = self.scan_dir_pair((0, 1), true)?;
732        }
733        Ok(())
734    }
735
736    /// Build one fully self-contained metadata-block commit (superblock +
737    /// every entry, freshly numbered) for a directory. See the tag format
738    /// documented in `mod tag` and the module-level docs for how the CRC/FCRC
739    /// encoding here was derived from real `mklittlefs` images rather than
740    /// guessed from the spec text.
741    fn build_dir_commit(&self, revision: u32, is_root: bool, entries: &[ResolvedEntry]) -> Result<Vec<u8>, LittleFsError> {
742        let mut out = Vec::with_capacity(self.block_size);
743        out.extend_from_slice(&revision.to_le_bytes());
744
745        let mut ptag: u32 = 0xffff_ffff;
746        let mut next_id: u32 = 0;
747
748        if is_root {
749            ptag = write_tag(&mut out, ptag, tag::SUPERBLOCK, 0, self.superblock.name.as_bytes());
750
751            let sb = &self.superblock;
752            let mut cfg = Vec::with_capacity(24);
753            cfg.extend_from_slice(&sb.version.to_le_bytes());
754            cfg.extend_from_slice(&(self.block_size as u32).to_le_bytes());
755            cfg.extend_from_slice(&sb.block_count.to_le_bytes());
756            cfg.extend_from_slice(&sb.name_max.to_le_bytes());
757            cfg.extend_from_slice(&sb.file_max.to_le_bytes());
758            cfg.extend_from_slice(&sb.attr_max.to_le_bytes());
759            ptag = write_tag(&mut out, ptag, tag::INLINESTRUCT, 0, &cfg);
760            next_id = 1;
761        }
762
763        for entry in entries.iter() {
764            let id = next_id;
765            next_id += 1;
766            ptag = write_tag(&mut out, ptag, tag::CREATE, id, &[]);
767            let name_tag = if entry.is_dir { tag::DIR } else { tag::REG };
768            ptag = write_tag(&mut out, ptag, name_tag, id, entry.name.as_bytes());
769
770            if entry.is_dir {
771                let (a, b) = entry.child_pair.ok_or(LittleFsError::Corrupted)?;
772                let mut payload = Vec::with_capacity(8);
773                payload.extend_from_slice(&a.to_le_bytes());
774                payload.extend_from_slice(&b.to_le_bytes());
775                ptag = write_tag(&mut out, ptag, tag::DIRSTRUCT, id, &payload);
776            } else if let Some((head, size)) = entry.ctz {
777                let mut payload = Vec::with_capacity(8);
778                payload.extend_from_slice(&head.to_le_bytes());
779                payload.extend_from_slice(&size.to_le_bytes());
780                ptag = write_tag(&mut out, ptag, tag::CTZSTRUCT, id, &payload);
781            } else {
782                let data = entry.inline_data.as_deref().unwrap_or(&[]);
783                ptag = write_tag(&mut out, ptag, tag::INLINESTRUCT, id, data);
784            }
785        }
786
787        // FCRC: assert that the next FCRC_LOOKAHEAD bytes are erased (0xFF,
788        // matching real flash after an erase — not the 0x00 padding
789        // `mklittlefs`'s own desktop-only image builder happens to use).
790        let lookahead_crc = lfs_crc(0xffff_ffff, &[0xff; tag::FCRC_LOOKAHEAD]);
791        let mut fcrc_payload = Vec::with_capacity(8);
792        fcrc_payload.extend_from_slice(&(tag::FCRC_LOOKAHEAD as u32).to_le_bytes());
793        fcrc_payload.extend_from_slice(&lookahead_crc.to_le_bytes());
794        ptag = write_tag(&mut out, ptag, tag::FCRC, tag::CRC_TAG_ID, &fcrc_payload);
795
796        // Terminating CRC tag: covers everything written so far, including
797        // this tag's own 4-byte header but not its (about to be appended)
798        // payload — verified against real images in the module docs.
799        let crc_tag_actual = (tag::CRC << 20) | (tag::CRC_TAG_ID << 10) | 4;
800        let crc_tag_stored = crc_tag_actual ^ ptag;
801        out.extend_from_slice(&crc_tag_stored.to_be_bytes());
802        let commit_crc = lfs_crc(0xffff_ffff, &out);
803        out.extend_from_slice(&commit_crc.to_le_bytes());
804
805        let available = self.block_size.saturating_sub(out.len());
806        if available < tag::FCRC_LOOKAHEAD {
807            return Err(LittleFsError::CommitTooLarge {
808                needed: out.len() + tag::FCRC_LOOKAHEAD,
809                available: self.block_size,
810            });
811        }
812        out.resize(self.block_size, 0xff);
813        Ok(out)
814    }
815}
816
817/// Append one tag (header + payload) to `out`, XOR-encoding the header against
818/// `prev` as the on-disk format requires, and return the new "previous actual
819/// tag" for the caller's next entry (mirrors the test helper `push_tag`, kept
820/// separate since this one is production code with a `u32`-length assertion
821/// rather than a test-only debug helper).
822fn write_tag(out: &mut Vec<u8>, prev: u32, ty: u32, id: u32, payload: &[u8]) -> u32 {
823    debug_assert!(payload.len() < 0x3ff, "tag payload too long to encode in 10 bits");
824    let actual = (ty << 20) | (id << 10) | (payload.len() as u32);
825    let stored = actual ^ prev;
826    out.extend_from_slice(&stored.to_be_bytes());
827    out.extend_from_slice(payload);
828    actual
829}
830
831/// LittleFS's on-disk CRC32: standard reflected CRC-32 (polynomial
832/// `0xEDB88320`, i.e. the same table as zlib/PNG/gzip) but — unlike that
833/// "public" CRC-32 — stored as the **raw running register value**, with no
834/// final complement. Confirmed by brute-forcing candidate algorithms/byte
835/// ranges against real `mklittlefs`-built images until the stored value
836/// matched exactly (see the Phase 2 write-support writeup in `TODO.md`); not
837/// taken from the spec text alone.
838fn lfs_crc(seed: u32, data: &[u8]) -> u32 {
839    let mut crc = seed;
840    for &byte in data {
841        crc ^= byte as u32;
842        for _ in 0..8 {
843            crc = if crc & 1 != 0 {
844                (crc >> 1) ^ 0xEDB8_8320
845            } else {
846                crc >> 1
847            };
848        }
849    }
850    crc
851}
852
853/// Parsed superblock config (from the root pair's id-0 inlinestruct tag).
854/// Retained in full (not just `version`/`block_size`) so a write can re-emit
855/// an identical superblock commit — these fields are otherwise opaque to this
856/// reader and must round-trip unchanged.
857#[derive(Debug, Clone)]
858struct SuperblockInfo {
859    name: String,
860    version: u32,
861    block_size: u32,
862    block_count: u32,
863    name_max: u32,
864    file_max: u32,
865    attr_max: u32,
866}
867
868/// Result of replaying one metadata block's commit log.
869struct BlockScan {
870    superblock: Option<SuperblockInfo>,
871    ids: Vec<IdState>,
872}
873
874fn read_revision(block: &[u8]) -> u32 {
875    u32::from_le_bytes([block[0], block[1], block[2], block[3]])
876}
877
878fn tag_type(t: u32) -> u32 {
879    (t >> 20) & 0x7ff
880}
881
882fn tag_id(t: u32) -> u32 {
883    (t >> 10) & 0x3ff
884}
885
886fn tag_len(t: u32) -> u32 {
887    t & 0x3ff
888}
889
890/// Replay a metadata block's tag log, reconstructing per-id state.
891///
892/// Tags are big-endian 32-bit words, XOR-chained together starting from
893/// `0xffffffff` at the start of the block (immediately after the 4-byte
894/// revision count) and continuing across every commit in the block — commits
895/// are not independent XOR chains. A stored word of all-zero or all-one bytes
896/// marks the end of written data (erased flash reads as `0xff`; this tool's
897/// synthetic images pad with `0x00`), since no legitimate tag XORs down to
898/// either sentinel in practice.
899fn parse_block(block: &[u8]) -> BlockScan {
900    // id 0 is reserved for the superblock in the root directory's metadata pair.
901    let mut ids: Vec<IdState> = vec![IdState::default()];
902    let mut superblock: Option<SuperblockInfo> = None;
903    let mut pos = 4usize;
904    let mut ptag: u32 = 0xffff_ffff;
905
906    while pos + 4 <= block.len() {
907        let stored_bytes: [u8; 4] = match block[pos..pos + 4].try_into() {
908            Ok(b) => b,
909            Err(_) => break,
910        };
911        let stored = u32::from_be_bytes(stored_bytes);
912        if stored == 0x0000_0000 || stored == 0xffff_ffff {
913            break;
914        }
915
916        let tag = stored ^ ptag;
917        ptag = tag;
918        pos += 4;
919
920        let ty = tag_type(tag);
921        let id = tag_id(tag) as usize;
922        let len = tag_len(tag);
923
924        if len == 0x3ff {
925            break;
926        }
927        let len = len as usize;
928        if pos + len > block.len() {
929            break;
930        }
931        let payload = &block[pos..pos + len];
932        pos += len;
933
934        if (ty & tag::USERATTR_FAMILY_MASK) == tag::CRC_FAMILY {
935            continue;
936        }
937
938        match ty {
939            tag::SUPERBLOCK if id == 0 => {
940                superblock = Some(SuperblockInfo {
941                    name: String::from_utf8_lossy(payload).to_string(),
942                    version: 0,
943                    block_size: 0,
944                    block_count: 0,
945                    name_max: 0,
946                    file_max: 0,
947                    attr_max: 0,
948                });
949            }
950            tag::CREATE => {
951                if id <= ids.len() {
952                    ids.insert(id, IdState::default());
953                }
954            }
955            tag::DELETE => {
956                if id < ids.len() {
957                    ids.remove(id);
958                }
959            }
960            tag::REG | tag::DIR => {
961                if let Some(entry) = ids.get_mut(id) {
962                    entry.name = Some(String::from_utf8_lossy(payload).to_string());
963                    entry.is_dir = ty == tag::DIR;
964                }
965            }
966            tag::INLINESTRUCT if id == 0 && payload.len() == 24 => {
967                if let Some(sb) = superblock.as_mut() {
968                    sb.version = u32::from_le_bytes(payload[0..4].try_into().unwrap());
969                    sb.block_size = u32::from_le_bytes(payload[4..8].try_into().unwrap());
970                    sb.block_count = u32::from_le_bytes(payload[8..12].try_into().unwrap());
971                    sb.name_max = u32::from_le_bytes(payload[12..16].try_into().unwrap());
972                    sb.file_max = u32::from_le_bytes(payload[16..20].try_into().unwrap());
973                    sb.attr_max = u32::from_le_bytes(payload[20..24].try_into().unwrap());
974                }
975            }
976            tag::INLINESTRUCT => {
977                if let Some(entry) = ids.get_mut(id) {
978                    entry.inline_data = Some(payload.to_vec());
979                    entry.ctz = None;
980                }
981            }
982            tag::CTZSTRUCT => {
983                if let Some(entry) = ids.get_mut(id) {
984                    if payload.len() >= 8 {
985                        let head = u32::from_le_bytes(payload[0..4].try_into().unwrap());
986                        let size = u32::from_le_bytes(payload[4..8].try_into().unwrap());
987                        entry.ctz = Some((head, size));
988                        entry.inline_data = None;
989                    }
990                }
991            }
992            tag::DIRSTRUCT => {
993                if let Some(entry) = ids.get_mut(id) {
994                    if payload.len() >= 8 {
995                        let block_a = u32::from_le_bytes(payload[0..4].try_into().unwrap());
996                        let block_b = u32::from_le_bytes(payload[4..8].try_into().unwrap());
997                        entry.child_pair = Some((block_a, block_b));
998                    }
999                }
1000            }
1001            t if (t & tag::USERATTR_FAMILY_MASK) == tag::USERATTR_FAMILY => {
1002                if (t & 0xff) == tag::MTIME_ATTR {
1003                    if let Some(entry) = ids.get_mut(id) {
1004                        if payload.len() >= 4 {
1005                            entry.mtime =
1006                                Some(u32::from_le_bytes(payload[0..4].try_into().unwrap()));
1007                        }
1008                    }
1009                }
1010            }
1011            _ => {}
1012        }
1013    }
1014
1015    BlockScan { superblock, ids }
1016}
1017
1018/// Errors from LittleFS operations.
1019#[derive(Debug, thiserror::Error)]
1020pub enum LittleFsError {
1021    #[error("corrupted filesystem: invalid structure")]
1022    Corrupted,
1023
1024    #[error("bad magic: expected superblock name {expected:?}, got {actual:?}")]
1025    BadMagic { expected: &'static str, actual: String },
1026
1027    #[error("partition data not aligned to block size")]
1028    UnalignedPartition,
1029
1030    #[error("file not found: {0}")]
1031    FileNotFound(String),
1032
1033    #[error("unsupported LittleFS on-disk version: 0x{0:08x}")]
1034    UnsupportedVersion(u32),
1035
1036    #[error("superblock reports block_size {actual}, reader assumes {expected}")]
1037    BlockSizeMismatch { expected: u32, actual: u32 },
1038
1039    #[error("invalid file name: {0:?}")]
1040    InvalidName(String),
1041
1042    #[error("a directory already exists with that name: {0:?}")]
1043    NameCollision(String),
1044
1045    #[error("write does not fit in one metadata block: needed {needed} bytes, {available} available")]
1046    CommitTooLarge { needed: usize, available: usize },
1047
1048    #[error("not enough free space: need {needed} block(s), only {available} available")]
1049    PartitionFull { needed: usize, available: usize },
1050}
1051
1052#[cfg(test)]
1053mod tests {
1054    use super::*;
1055
1056    /// Encode a big-endian tag word for `raw = actual_tag ^ prev_actual_tag`,
1057    /// mirroring the on-disk XOR chain, and append it (plus payload) to `out`.
1058    /// Returns the new "previous actual tag" for the caller's next entry.
1059    fn push_tag(out: &mut Vec<u8>, prev: u32, ty: u32, id: u32, payload: &[u8]) -> u32 {
1060        let actual = (ty << 20) | (id << 10) | (payload.len() as u32);
1061        let stored = actual ^ prev;
1062        out.extend_from_slice(&stored.to_be_bytes());
1063        out.extend_from_slice(payload);
1064        actual
1065    }
1066
1067    /// Build a minimal, correctly-tagged root metadata block: revision count,
1068    /// superblock name+config, then whatever extra (tag, id, payload) entries
1069    /// are supplied, matching the real format confirmed against `mklittlefs`.
1070    fn build_block(revision: u32, block_size: usize, extra: &[(u32, u32, &[u8])]) -> Vec<u8> {
1071        let mut out = Vec::new();
1072        out.extend_from_slice(&revision.to_le_bytes());
1073
1074        let mut ptag: u32 = 0xffff_ffff;
1075        ptag = push_tag(&mut out, ptag, tag::SUPERBLOCK, 0, b"littlefs");
1076
1077        let mut cfg = Vec::new();
1078        cfg.extend_from_slice(&0x0002_0001u32.to_le_bytes()); // version 2.1
1079        cfg.extend_from_slice(&(block_size as u32).to_le_bytes());
1080        cfg.extend_from_slice(&352u32.to_le_bytes()); // block_count (unused by reader)
1081        cfg.extend_from_slice(&255u32.to_le_bytes()); // name_max
1082        cfg.extend_from_slice(&0x7fff_ffffu32.to_le_bytes()); // file_max
1083        cfg.extend_from_slice(&1022u32.to_le_bytes()); // attr_max
1084        ptag = push_tag(&mut out, ptag, tag::INLINESTRUCT, 0, &cfg);
1085
1086        for (ty, id, payload) in extra {
1087            ptag = push_tag(&mut out, ptag, *ty, *id, payload);
1088        }
1089        let _ = ptag;
1090
1091        out.resize(block_size, 0);
1092        out
1093    }
1094
1095    /// Build a plain (non-root) directory metadata block: revision count plus
1096    /// whatever (tag, id, payload) entries are supplied — no superblock tag,
1097    /// matching the real on-disk layout of a subdirectory's own metadata pair.
1098    fn build_plain_block(revision: u32, block_size: usize, extra: &[(u32, u32, &[u8])]) -> Vec<u8> {
1099        let mut out = Vec::new();
1100        out.extend_from_slice(&revision.to_le_bytes());
1101        let mut ptag: u32 = 0xffff_ffff;
1102        for (ty, id, payload) in extra {
1103            ptag = push_tag(&mut out, ptag, *ty, *id, payload);
1104        }
1105        let _ = ptag;
1106        out.resize(block_size, 0);
1107        out
1108    }
1109
1110    #[test]
1111    fn rejects_unaligned_partition() {
1112        let unaligned = vec![0u8; superblock::BLOCK_SIZE - 100];
1113        assert!(matches!(
1114            LittleFs::from_bytes(&unaligned),
1115            Err(LittleFsError::UnalignedPartition)
1116        ));
1117    }
1118
1119    #[test]
1120    fn rejects_bad_magic() {
1121        let mut out = Vec::new();
1122        out.extend_from_slice(&1u32.to_le_bytes());
1123        push_tag(&mut out, 0xffff_ffff, tag::SUPERBLOCK, 0, b"notlittlefs");
1124        out.resize(superblock::BLOCK_SIZE, 0);
1125        let block1 = vec![0u8; superblock::BLOCK_SIZE];
1126
1127        let mut data = out;
1128        data.extend_from_slice(&block1);
1129
1130        assert!(matches!(
1131            LittleFs::from_bytes(&data),
1132            Err(LittleFsError::BadMagic { .. })
1133        ));
1134    }
1135
1136    #[test]
1137    fn accepts_valid_superblock_with_no_files() {
1138        let block0 = build_block(1, superblock::BLOCK_SIZE, &[]);
1139        let block1 = vec![0u8; superblock::BLOCK_SIZE];
1140        let mut data = block0;
1141        data.extend_from_slice(&block1);
1142
1143        let fs = LittleFs::from_bytes(&data).expect("valid superblock should parse");
1144        assert_eq!(fs.erase_block_count(), 2);
1145        assert!(fs.list_dir("").unwrap().is_empty());
1146    }
1147
1148    #[test]
1149    fn parses_inline_file_matching_real_mklittlefs_layout() {
1150        // Mirrors the exact tag sequence observed in a real `mklittlefs`-built
1151        // image: CREATE id=1, REG name, INLINESTRUCT content.
1152        let extra: &[(u32, u32, &[u8])] = &[
1153            (tag::CREATE, 1, &[]),
1154            (tag::REG, 1, b"hello.txt"),
1155            (tag::INLINESTRUCT, 1, b"hello world\n"),
1156        ];
1157        let block0 = build_block(1, superblock::BLOCK_SIZE, extra);
1158        let block1 = vec![0u8; superblock::BLOCK_SIZE];
1159        let mut data = block0;
1160        data.extend_from_slice(&block1);
1161
1162        let fs = LittleFs::from_bytes(&data).expect("should parse");
1163        let entries = fs.list_dir("").unwrap();
1164        assert_eq!(entries.len(), 1);
1165        match &entries[0] {
1166            FsEntry::File(f) => {
1167                assert_eq!(f.name, "hello.txt");
1168                assert_eq!(f.size, 12);
1169            }
1170            FsEntry::Dir(_) => panic!("expected a file entry"),
1171        }
1172        assert_eq!(fs.read_file("hello.txt").unwrap(), b"hello world\n");
1173        assert!(fs.file_exists("hello.txt"));
1174    }
1175
1176    #[test]
1177    fn picks_higher_revision_block_of_the_pair() {
1178        // block0 is stale (rev 1, no files); block1 is current (rev 2, one file).
1179        let block0 = build_block(1, superblock::BLOCK_SIZE, &[]);
1180        let extra: &[(u32, u32, &[u8])] = &[
1181            (tag::CREATE, 1, &[]),
1182            (tag::REG, 1, b"a.txt"),
1183            (tag::INLINESTRUCT, 1, b"x"),
1184        ];
1185        let block1 = build_block(2, superblock::BLOCK_SIZE, extra);
1186
1187        let mut data = block0;
1188        data.extend_from_slice(&block1);
1189
1190        let fs = LittleFs::from_bytes(&data).unwrap();
1191        let entries = fs.list_dir("").unwrap();
1192        assert_eq!(entries.len(), 1);
1193    }
1194
1195    #[test]
1196    fn delete_shifts_subsequent_ids_down() {
1197        let extra: &[(u32, u32, &[u8])] = &[
1198            (tag::CREATE, 1, &[]),
1199            (tag::REG, 1, b"a.txt"),
1200            (tag::INLINESTRUCT, 1, b"a"),
1201            (tag::CREATE, 2, &[]),
1202            (tag::REG, 2, b"b.txt"),
1203            (tag::INLINESTRUCT, 2, b"b"),
1204            (tag::DELETE, 1, &[]),
1205        ];
1206        let block0 = build_block(1, superblock::BLOCK_SIZE, extra);
1207        let block1 = vec![0u8; superblock::BLOCK_SIZE];
1208        let mut data = block0;
1209        data.extend_from_slice(&block1);
1210
1211        let fs = LittleFs::from_bytes(&data).unwrap();
1212        let entries = fs.list_dir("").unwrap();
1213        assert_eq!(entries.len(), 1);
1214        match &entries[0] {
1215            FsEntry::File(f) => assert_eq!(f.name, "b.txt"),
1216            FsEntry::Dir(_) => panic!("expected a file entry"),
1217        }
1218    }
1219
1220    #[test]
1221    fn subdirectory_traversal_reads_nested_file() {
1222        // Root (blocks 0/1): one directory "sub" whose DIRSTRUCT points at the
1223        // child metadata pair (blocks 2/3) — mirrors the exact tag sequence
1224        // observed in a real `mklittlefs`-built image with a subdirectory.
1225        let mut dirstruct_payload = Vec::new();
1226        dirstruct_payload.extend_from_slice(&2u32.to_le_bytes());
1227        dirstruct_payload.extend_from_slice(&3u32.to_le_bytes());
1228        let root_extra: &[(u32, u32, &[u8])] = &[
1229            (tag::CREATE, 1, &[]),
1230            (tag::DIR, 1, b"sub"),
1231            (tag::DIRSTRUCT, 1, &dirstruct_payload),
1232        ];
1233        let block0 = build_block(1, superblock::BLOCK_SIZE, root_extra);
1234        let block1 = vec![0u8; superblock::BLOCK_SIZE];
1235
1236        // Child directory pair (blocks 2/3): one file, id 0 (no reserved
1237        // superblock slot here, unlike the root pair).
1238        let child_extra: &[(u32, u32, &[u8])] = &[
1239            (tag::CREATE, 0, &[]),
1240            (tag::REG, 0, b"nested.txt"),
1241            (tag::INLINESTRUCT, 0, b"nested contents\n"),
1242        ];
1243        let block2 = build_plain_block(1, superblock::BLOCK_SIZE, child_extra);
1244        let block3 = vec![0u8; superblock::BLOCK_SIZE];
1245
1246        let mut data = block0;
1247        data.extend_from_slice(&block1);
1248        data.extend_from_slice(&block2);
1249        data.extend_from_slice(&block3);
1250
1251        let fs = LittleFs::from_bytes(&data).expect("should parse");
1252
1253        let root_entries = fs.list_dir("").unwrap();
1254        assert_eq!(root_entries.len(), 1);
1255        assert!(matches!(&root_entries[0], FsEntry::Dir(d) if d.name == "sub"));
1256
1257        let sub_entries = fs.list_dir("sub").unwrap();
1258        assert_eq!(sub_entries.len(), 1);
1259        match &sub_entries[0] {
1260            FsEntry::File(f) => {
1261                assert_eq!(f.name, "nested.txt");
1262                assert_eq!(f.size, 16);
1263            }
1264            FsEntry::Dir(_) => panic!("expected a file entry"),
1265        }
1266
1267        assert_eq!(fs.read_file("sub/nested.txt").unwrap(), b"nested contents\n");
1268        assert!(fs.file_exists("sub/nested.txt"));
1269        assert!(!fs.file_exists("sub/missing.txt"));
1270
1271        let walked = fs.walk().unwrap();
1272        assert_eq!(walked.len(), 2);
1273    }
1274
1275    #[test]
1276    fn ctz_skip_list_reads_multi_block_file() {
1277        // Build a 2-block (5000-byte) file CTZ chain by hand, matching the
1278        // exact pointer layout derived from a real `mklittlefs` image.
1279        // Partition layout: blocks 0,1 = root pair; blocks 2,3 = CTZ chain (index 0, index 1/head)
1280        let block_size = superblock::BLOCK_SIZE;
1281        let index0_data: Vec<u8> = (0..block_size).map(|i| (i % 256) as u8).collect();
1282        let mut block3 = index0_data.clone(); // index 0: 4096 bytes data, no pointer prefix
1283        block3.resize(block_size, 0);
1284        let mut block2 = Vec::new(); // index 1 (head): 1 pointer to index 0 + 904 bytes data
1285        block2.extend_from_slice(&3u32.to_le_bytes()); // pointer to block 3 (index 0)
1286        block2.push(0x42);
1287        block2.resize(block_size, 0);
1288
1289        let ctz_payload: Vec<u8> = {
1290            let mut v = Vec::new();
1291            v.extend_from_slice(&2u32.to_le_bytes()); // head block = partition block 2
1292            v.extend_from_slice(&5000u32.to_le_bytes()); // file size
1293            v
1294        };
1295
1296        let root_extra: &[(u32, u32, &[u8])] = &[
1297            (tag::CREATE, 1, &[]),
1298            (tag::REG, 1, b"big.bin"),
1299            (tag::CTZSTRUCT, 1, &ctz_payload),
1300        ];
1301        let block0 = build_block(1, block_size, root_extra);
1302        let block1 = vec![0u8; block_size];
1303
1304        let mut data = block0;
1305        data.extend_from_slice(&block1);
1306        data.extend_from_slice(&block2); // partition block 2 = CTZ index 1 (head)
1307        data.extend_from_slice(&block3); // partition block 3 = CTZ index 0
1308
1309        let fs = LittleFs::from_bytes(&data).expect("should parse");
1310        let contents = fs.read_file("big.bin").unwrap();
1311        assert_eq!(contents.len(), 5000);
1312        assert_eq!(&contents[..block_size], &index0_data[..]);
1313        assert_eq!(contents[block_size], 0x42);
1314    }
1315
1316    #[test]
1317    fn write_file_creates_and_reads_back() {
1318        let block0 = build_block(1, superblock::BLOCK_SIZE, &[]);
1319        let block1 = vec![0u8; superblock::BLOCK_SIZE];
1320        let mut data = block0;
1321        data.extend_from_slice(&block1);
1322
1323        let mut fs = LittleFs::from_bytes(&data).expect("should parse");
1324        fs.write_file("new.txt", b"new content\n").expect("write new file");
1325
1326        assert_eq!(fs.read_file("new.txt").unwrap(), b"new content\n");
1327        assert!(fs.file_exists("new.txt"));
1328
1329        let roundtrip = LittleFs::from_bytes(&fs.to_bytes()).expect("re-parse");
1330        assert_eq!(roundtrip.read_file("new.txt").unwrap(), b"new content\n");
1331    }
1332
1333    #[test]
1334    fn write_file_encodes_large_content_as_ctz_and_reads_back() {
1335        let block_size = superblock::BLOCK_SIZE;
1336        // Need 2 blocks for root pair + 3 blocks for 9000-byte CTZ file = 5 blocks minimum
1337        let block0 = build_block(1, block_size, &[]);
1338        let block1 = vec![0u8; block_size];
1339        let block2 = vec![0u8; block_size];
1340        let block3 = vec![0u8; block_size];
1341        let block4 = vec![0u8; block_size];
1342        let mut data = block0;
1343        data.extend_from_slice(&block1);
1344        data.extend_from_slice(&block2);
1345        data.extend_from_slice(&block3);
1346        data.extend_from_slice(&block4);
1347
1348        let mut fs = LittleFs::from_bytes(&data).expect("should parse");
1349        let large_content = vec![0xAAu8; 9000]; // > INLINE_MAX, triggers CTZ
1350        fs.write_file("big.bin", &large_content).expect("write large file");
1351
1352        let read_back = fs.read_file("big.bin").unwrap();
1353        assert_eq!(read_back.len(), 9000);
1354        assert_eq!(read_back, large_content);
1355
1356        let roundtrip = LittleFs::from_bytes(&fs.to_bytes()).expect("re-parse");
1357        assert_eq!(roundtrip.read_file("big.bin").unwrap(), large_content);
1358    }
1359
1360    #[test]
1361    fn write_file_overwrites_existing_and_alternates_blocks() {
1362        let block_size = superblock::BLOCK_SIZE;
1363        let block0 = build_block(1, block_size, &[]);
1364        let block1 = vec![0u8; block_size];
1365        let mut data = block0;
1366        data.extend_from_slice(&block1);
1367
1368        let mut fs = LittleFs::from_bytes(&data).expect("should parse");
1369        fs.write_file("test.txt", b"first").expect("first write");
1370        fs.write_file("test.txt", b"second").expect("second write");
1371
1372        assert_eq!(fs.read_file("test.txt").unwrap(), b"second");
1373
1374        let roundtrip = LittleFs::from_bytes(&fs.to_bytes()).expect("re-parse");
1375        assert_eq!(roundtrip.read_file("test.txt").unwrap(), b"second");
1376    }
1377
1378    #[test]
1379    fn write_file_errors_when_partition_has_no_free_blocks() {
1380        let block_size = superblock::BLOCK_SIZE;
1381        let block0 = build_block(1, block_size, &[]);
1382        let block1 = vec![0u8; block_size];
1383        let mut data = block0;
1384        data.extend_from_slice(&block1);
1385
1386        let mut fs = LittleFs::from_bytes(&data).expect("should parse");
1387        let large_content = vec![0xAAu8; 9000];
1388        let result = fs.write_file("big.bin", &large_content);
1389        assert!(matches!(result, Err(LittleFsError::PartitionFull { .. })));
1390    }
1391
1392    #[test]
1393    fn write_file_rejects_invalid_name_and_directory_collision() {
1394        let block0 = build_block(1, superblock::BLOCK_SIZE, &[]);
1395        let block1 = vec![0u8; superblock::BLOCK_SIZE];
1396        let mut data = block0;
1397        data.extend_from_slice(&block1);
1398
1399        let mut fs = LittleFs::from_bytes(&data).expect("should parse");
1400
1401        // Empty name
1402        assert!(matches!(
1403            fs.write_file("", b"x"),
1404            Err(LittleFsError::InvalidName(_))
1405        ));
1406
1407        // Directory collision
1408        let mut dirstruct_payload = Vec::new();
1409        dirstruct_payload.extend_from_slice(&2u32.to_le_bytes());
1410        dirstruct_payload.extend_from_slice(&3u32.to_le_bytes());
1411        let root_extra: &[(u32, u32, &[u8])] = &[
1412            (tag::CREATE, 1, &[]),
1413            (tag::DIR, 1, b"sub"),
1414            (tag::DIRSTRUCT, 1, &dirstruct_payload),
1415        ];
1416        let block0 = build_block(1, superblock::BLOCK_SIZE, root_extra);
1417        let block1 = vec![0u8; superblock::BLOCK_SIZE];
1418        let block2 = build_plain_block(1, superblock::BLOCK_SIZE, &[]);
1419        let block3 = vec![0u8; superblock::BLOCK_SIZE];
1420        let mut data = block0;
1421        data.extend_from_slice(&block1);
1422        data.extend_from_slice(&block2);
1423        data.extend_from_slice(&block3);
1424
1425        let mut fs = LittleFs::from_bytes(&data).expect("should parse");
1426        assert!(matches!(
1427            fs.write_file("sub", b"x"),
1428            Err(LittleFsError::NameCollision(_))
1429        ));
1430    }
1431
1432    #[test]
1433    fn delete_file_removes_entry_and_missing_file_errors() {
1434        let extra: &[(u32, u32, &[u8])] = &[
1435            (tag::CREATE, 1, &[]),
1436            (tag::REG, 1, b"a.txt"),
1437            (tag::INLINESTRUCT, 1, b"a"),
1438        ];
1439        let block0 = build_block(1, superblock::BLOCK_SIZE, extra);
1440        let block1 = vec![0u8; superblock::BLOCK_SIZE];
1441        let mut data = block0;
1442        data.extend_from_slice(&block1);
1443
1444        let mut fs = LittleFs::from_bytes(&data).unwrap();
1445        fs.delete_file("a.txt").expect("delete existing");
1446        assert!(!fs.file_exists("a.txt"));
1447        assert!(fs.list_dir("").unwrap().is_empty());
1448
1449        assert!(matches!(
1450            fs.delete_file("missing.txt"),
1451            Err(LittleFsError::FileNotFound(_))
1452        ));
1453    }
1454
1455    #[test]
1456    fn rename_file_updates_name_preserves_contents() {
1457        let extra: &[(u32, u32, &[u8])] = &[
1458            (tag::CREATE, 1, &[]),
1459            (tag::REG, 1, b"old.txt"),
1460            (tag::INLINESTRUCT, 1, b"contents"),
1461        ];
1462        let block0 = build_block(1, superblock::BLOCK_SIZE, extra);
1463        let block1 = vec![0u8; superblock::BLOCK_SIZE];
1464        let mut data = block0;
1465        data.extend_from_slice(&block1);
1466
1467        let mut fs = LittleFs::from_bytes(&data).unwrap();
1468        fs.rename_file("old.txt", "new.txt").unwrap();
1469
1470        assert!(!fs.file_exists("old.txt"));
1471        assert_eq!(fs.read_file("new.txt").unwrap(), b"contents");
1472
1473        let roundtrip = LittleFs::from_bytes(&fs.to_bytes()).unwrap();
1474        assert_eq!(roundtrip.read_file("new.txt").unwrap(), b"contents");
1475    }
1476
1477    #[test]
1478    fn rename_file_rejects_missing_source_and_name_collision() {
1479        let extra: &[(u32, u32, &[u8])] = &[
1480            (tag::CREATE, 1, &[]),
1481            (tag::REG, 1, b"a.txt"),
1482            (tag::INLINESTRUCT, 1, b"a"),
1483            (tag::CREATE, 2, &[]),
1484            (tag::REG, 2, b"b.txt"),
1485            (tag::INLINESTRUCT, 2, b"b"),
1486        ];
1487        let block0 = build_block(1, superblock::BLOCK_SIZE, extra);
1488        let block1 = vec![0u8; superblock::BLOCK_SIZE];
1489        let mut data = block0;
1490        data.extend_from_slice(&block1);
1491
1492        let mut fs = LittleFs::from_bytes(&data).unwrap();
1493
1494        assert!(matches!(
1495            fs.rename_file("missing.txt", "c.txt"),
1496            Err(LittleFsError::FileNotFound(_))
1497        ));
1498        assert!(matches!(
1499            fs.rename_file("a.txt", "b.txt"),
1500            Err(LittleFsError::NameCollision(_))
1501        ));
1502        // Renaming a file to its own current name is a harmless no-op collision.
1503        assert!(fs.rename_file("a.txt", "a.txt").is_ok());
1504    }
1505
1506    #[test]
1507    fn write_delete_rename_operate_inside_existing_subdirectory() {
1508        let mut dirstruct_payload = Vec::new();
1509        dirstruct_payload.extend_from_slice(&2u32.to_le_bytes());
1510        dirstruct_payload.extend_from_slice(&3u32.to_le_bytes());
1511        let root_extra: &[(u32, u32, &[u8])] = &[
1512            (tag::CREATE, 1, &[]),
1513            (tag::DIR, 1, b"sub"),
1514            (tag::DIRSTRUCT, 1, &dirstruct_payload),
1515        ];
1516        let block0 = build_block(1, superblock::BLOCK_SIZE, root_extra);
1517        let block1 = vec![0u8; superblock::BLOCK_SIZE];
1518
1519        let sub_extra: &[(u32, u32, &[u8])] = &[
1520            (tag::CREATE, 0, &[]),
1521            (tag::REG, 0, b"existing.txt"),
1522            (tag::INLINESTRUCT, 0, b"already here"),
1523        ];
1524        let block2 = build_plain_block(1, superblock::BLOCK_SIZE, sub_extra);
1525        let block3 = vec![0u8; superblock::BLOCK_SIZE];
1526
1527        let mut data = block0;
1528        data.extend_from_slice(&block1);
1529        data.extend_from_slice(&block2);
1530        data.extend_from_slice(&block3);
1531
1532        let mut fs = LittleFs::from_bytes(&data).expect("should parse");
1533
1534        // Create a new file inside the existing subdirectory.
1535        fs.write_file("sub/new.txt", b"new content").expect("create in subdir");
1536        assert_eq!(fs.read_file("sub/new.txt").unwrap(), b"new content");
1537        assert_eq!(fs.read_file("sub/existing.txt").unwrap(), b"already here");
1538
1539        // Rename a file inside the subdirectory.
1540        fs.rename_file("sub/existing.txt", "renamed.txt").expect("rename in subdir");
1541        assert!(!fs.file_exists("sub/existing.txt"));
1542        assert_eq!(fs.read_file("sub/renamed.txt").unwrap(), b"already here");
1543
1544        // The root directory itself must be untouched by any of this.
1545        let root_entries = fs.list_dir("").unwrap();
1546        assert_eq!(root_entries.len(), 1);
1547        assert!(matches!(&root_entries[0], FsEntry::Dir(d) if d.name == "sub"));
1548
1549        // Delete a file inside the subdirectory.
1550        fs.delete_file("sub/new.txt").expect("delete in subdir");
1551        assert!(!fs.file_exists("sub/new.txt"));
1552
1553        let sub_entries = fs.list_dir("sub").unwrap();
1554        assert_eq!(sub_entries.len(), 1);
1555        assert!(matches!(&sub_entries[0], FsEntry::File(f) if f.name == "renamed.txt"));
1556
1557        // Everything survives a full re-parse from the flattened bytes too.
1558        let roundtrip = LittleFs::from_bytes(&fs.to_bytes()).expect("re-parse");
1559        assert_eq!(roundtrip.read_file("sub/renamed.txt").unwrap(), b"already here");
1560    }
1561
1562    #[test]
1563    fn commit_root_preserves_untouched_subdirectory_and_ctz_file() {
1564        let block_size = superblock::BLOCK_SIZE;
1565        // 20000 bytes = 5 CTZ blocks (indices 0-4, head=4)
1566        // Partition layout: blocks 0,1 = root pair; 2,3 = sub dir pair; 4,5,6,7,8 = CTZ chain
1567        // ctz_plan for 20000 bytes with 4096-byte blocks:
1568        //   n=0: ptr=0, cap=4096, take=4096
1569        //   n=1: ptr=1, cap=4092, take=4092
1570        //   n=2: ptr=2, cap=4088, take=4088
1571        //   n=3: ptr=1, cap=4092, take=4092
1572        //   n=4: ptr=3, cap=4084, take=3632
1573        let ctz_file_size = 20000u32; // 5 blocks
1574        let ctz_payload: Vec<u8> = {
1575            let mut v = Vec::new();
1576            v.extend_from_slice(&8u32.to_le_bytes()); // head block = partition block 8 (CTZ index 4)
1577            v.extend_from_slice(&ctz_file_size.to_le_bytes());
1578            v
1579        };
1580
1581        let mut dirstruct_payload = Vec::new();
1582        dirstruct_payload.extend_from_slice(&2u32.to_le_bytes());
1583        dirstruct_payload.extend_from_slice(&3u32.to_le_bytes());
1584        let root_extra: &[(u32, u32, &[u8])] = &[
1585            (tag::CREATE, 1, &[]),
1586            (tag::DIR, 1, b"sub"),
1587            (tag::DIRSTRUCT, 1, &dirstruct_payload),
1588            (tag::CREATE, 2, &[]),
1589            (tag::REG, 2, b"keep.txt"),
1590            (tag::INLINESTRUCT, 2, b"keep me\n"),
1591            (tag::CREATE, 3, &[]),
1592            (tag::REG, 3, b"big.bin"),
1593            (tag::CTZSTRUCT, 3, &ctz_payload),
1594        ];
1595        let block0 = build_block(1, block_size, root_extra);
1596        let block1 = vec![0u8; block_size];
1597
1598        let sub_extra: &[(u32, u32, &[u8])] = &[
1599            (tag::CREATE, 0, &[]),
1600            (tag::REG, 0, b"nested.txt"),
1601            (tag::INLINESTRUCT, 0, b"nested\n"),
1602        ];
1603        let block2 = build_plain_block(1, block_size, sub_extra);
1604        let block3 = vec![0u8; block_size];
1605
1606        // Build 5-block CTZ chain (indices 0-4, head=4 at partition block 8)
1607        // with correct pointer counts per ctz(n)+1: [0, 1, 2, 1, 3]
1608        let index0_data: Vec<u8> = (0..block_size).map(|i| (i % 256) as u8).collect();
1609        let mut ctz_blocks = Vec::new();
1610        
1611        // Index 0 (block 4): 0 pointers, 4096 bytes data
1612        let mut b4 = index0_data.clone();
1613        b4.resize(block_size, 0);
1614        ctz_blocks.push(b4);
1615        
1616        // Index 1 (block 5): 1 pointer to block 4, 4092 bytes data
1617        let mut b5 = Vec::new();
1618        b5.extend_from_slice(&4u32.to_le_bytes()); // pointer to index 0 (block 4)
1619        b5.extend_from_slice(&index0_data[..4092]);
1620        b5.resize(block_size, 0);
1621        ctz_blocks.push(b5);
1622        
1623        // Index 2 (block 6): 2 pointers (to index 1=block 5, index 0=block 4), 4088 bytes data
1624        let mut b6 = Vec::new();
1625        b6.extend_from_slice(&5u32.to_le_bytes()); // pointer to index 1 (block 5)
1626        b6.extend_from_slice(&4u32.to_le_bytes()); // pointer to index 0 (block 4)
1627        b6.extend_from_slice(&index0_data[..4088]);
1628        b6.resize(block_size, 0);
1629        ctz_blocks.push(b6);
1630        
1631        // Index 3 (block 7): 1 pointer (to index 2=block 6), 4092 bytes data
1632        let mut b7 = Vec::new();
1633        b7.extend_from_slice(&6u32.to_le_bytes()); // pointer to index 2 (block 6)
1634        b7.extend_from_slice(&index0_data[..4092]);
1635        b7.resize(block_size, 0);
1636        ctz_blocks.push(b7);
1637        
1638        // Index 4 (head, block 8): 3 pointers (to index 3=block 7, index 2=block 6, index 0=block 4), 3632 bytes data (ends with 0x42)
1639        let mut b8 = Vec::new();
1640        b8.extend_from_slice(&7u32.to_le_bytes()); // pointer to index 3 (block 7)
1641        b8.extend_from_slice(&6u32.to_le_bytes()); // pointer to index 2 (block 6)
1642        b8.extend_from_slice(&4u32.to_le_bytes()); // pointer to index 0 (block 4)
1643        let mut head_data = index0_data[..3631].to_vec();
1644        head_data.push(0x42);
1645        b8.extend_from_slice(&head_data);
1646        b8.resize(block_size, 0);
1647        ctz_blocks.push(b8);
1648
1649        let mut data = block0;
1650        data.extend_from_slice(&block1);
1651        data.extend_from_slice(&block2);
1652        data.extend_from_slice(&block3);
1653        for b in ctz_blocks {
1654            data.extend_from_slice(&b);
1655        }
1656
1657        let mut fs = LittleFs::from_bytes(&data).expect("should parse");
1658        fs.write_file("new.txt", b"new\n").expect("write new file");
1659
1660        // The new file is there...
1661        assert_eq!(fs.read_file("new.txt").unwrap(), b"new\n");
1662        // ...and every pre-existing, untouched entry survived the rewrite.
1663        assert_eq!(fs.read_file("keep.txt").unwrap(), b"keep me\n");
1664        let ctz_contents = fs.read_file("big.bin").unwrap();
1665        assert_eq!(ctz_contents.len(), ctz_file_size as usize);
1666        assert_eq!(&ctz_contents[..block_size], &index0_data[..]);
1667        // The 0x42 marker is at the end of the 20000-byte file (byte 19999)
1668        assert_eq!(ctz_contents[ctz_file_size as usize - 1], 0x42);
1669        assert_eq!(fs.read_file("sub/nested.txt").unwrap(), b"nested\n");
1670
1671        let roundtrip = LittleFs::from_bytes(&fs.to_bytes()).expect("re-parse");
1672        assert_eq!(roundtrip.read_file("new.txt").unwrap(), b"new\n");
1673        assert_eq!(roundtrip.read_file("keep.txt").unwrap(), b"keep me\n");
1674        assert_eq!(roundtrip.read_file("sub/nested.txt").unwrap(), b"nested\n");
1675    }
1676
1677    #[test]
1678    fn deleting_a_large_file_frees_its_blocks_for_reuse() {
1679        let block_size = superblock::BLOCK_SIZE;
1680        // 20000 bytes = 5 CTZ blocks (indices 0-4, head=4)
1681        // Partition layout: blocks 0,1 = root pair; 2,3,4,5,6 = CTZ chain (5 blocks)
1682        let ctz_file_size = 20000u32; // 5 blocks
1683        let ctz_payload: Vec<u8> = {
1684            let mut v = Vec::new();
1685            v.extend_from_slice(&6u32.to_le_bytes()); // head block = partition block 6 (CTZ index 4)
1686            v.extend_from_slice(&ctz_file_size.to_le_bytes());
1687            v
1688        };
1689
1690        let root_extra: &[(u32, u32, &[u8])] = &[
1691            (tag::CREATE, 1, &[]),
1692            (tag::REG, 1, b"big.bin"),
1693            (tag::CTZSTRUCT, 1, &ctz_payload),
1694        ];
1695        let block0 = build_block(1, block_size, root_extra);
1696        let block1 = vec![0u8; block_size];
1697
1698        let index0_data: Vec<u8> = (0..block_size).map(|i| (i % 256) as u8).collect();
1699        let mut ctz_blocks = Vec::new();
1700        
1701        // Index 0: partition block 2, 4096 bytes data, no pointer
1702        let mut b2 = index0_data.clone();
1703        b2.resize(block_size, 0);
1704        ctz_blocks.push(b2);
1705        
1706        // Index 1: partition block 3, 1 pointer to block 2 + 4092 bytes data
1707        let mut b3 = Vec::new();
1708        b3.extend_from_slice(&2u32.to_le_bytes());
1709        b3.extend_from_slice(&index0_data[..4092]);
1710        b3.resize(block_size, 0);
1711        ctz_blocks.push(b3);
1712        
1713        // Index 2: partition block 4, 1 pointer to block 3 + 4092 bytes data
1714        let mut b4 = Vec::new();
1715        b4.extend_from_slice(&3u32.to_le_bytes());
1716        b4.extend_from_slice(&index0_data[..4092]);
1717        b4.resize(block_size, 0);
1718        ctz_blocks.push(b4);
1719        
1720        // Index 3: partition block 5, 2 pointers (to 4, 2) + 4088 bytes data
1721        let mut b5 = Vec::new();
1722        b5.extend_from_slice(&4u32.to_le_bytes());
1723        b5.extend_from_slice(&2u32.to_le_bytes());
1724        b5.extend_from_slice(&index0_data[..4088]);
1725        b5.resize(block_size, 0);
1726        ctz_blocks.push(b5);
1727        
1728        // Index 4 (head): partition block 6, 1 pointer to block 5 + 3632 bytes data
1729        let mut b6 = Vec::new();
1730        b6.extend_from_slice(&5u32.to_le_bytes());
1731        b6.extend_from_slice(&index0_data[..3632]);
1732        b6.resize(block_size, 0);
1733        ctz_blocks.push(b6);
1734
1735        let mut data = block0;
1736        data.extend_from_slice(&block1);
1737        for b in ctz_blocks {
1738            data.extend_from_slice(&b);
1739        }
1740
1741        let mut fs = LittleFs::from_bytes(&data).expect("should parse");
1742        fs.delete_file("big.bin").expect("delete large file");
1743
1744        // Now write a new large file — it should reuse the freed blocks.
1745        let new_content = vec![0xEEu8; 9000]; // 3 blocks
1746        fs.write_file("new_big.bin", &new_content).expect("write new large file");
1747
1748        let read_back = fs.read_file("new_big.bin").unwrap();
1749        assert_eq!(read_back.len(), 9000);
1750        assert_eq!(read_back, new_content);
1751
1752        let roundtrip = LittleFs::from_bytes(&fs.to_bytes()).expect("re-parse");
1753        assert_eq!(roundtrip.read_file("new_big.bin").unwrap(), new_content);
1754    }
1755}