fast_ntfs 1.0.2

// Copyright 2021-2026 Colin Finck <colin@reactos.org>
// SPDX-License-Identifier: MIT OR Apache-2.0

use alloc::vec::Vec;

use crate::error::{NtfsError, Result};
use crate::io::{Read, Seek, SeekFrom};
use crate::types::NtfsPosition;

#[derive(Clone, Debug)]
struct MappedDataRun {
    start: u64,
    end: u64,
    position: NtfsPosition,
}

/// Maps logical byte ranges of a non-resident value to their filesystem positions.
#[derive(Clone, Debug)]
pub(crate) struct MappedDataRuns {
    data_size: u64,
    runs: Vec<MappedDataRun>,
}

impl MappedDataRuns {
    pub(crate) fn new(data_size: u64) -> Self {
        Self {
            data_size,
            runs: Vec::new(),
        }
    }

    /// Appends a data run, returning `false` if its logical end would overflow.
    pub(crate) fn push(&mut self, allocated_size: u64, position: NtfsPosition) -> bool {
        let start = self.runs.last().map_or(0, |run| run.end);
        let Some(end) = start.checked_add(allocated_size) else {
            return false;
        };
        self.runs.push(MappedDataRun {
            start,
            end,
            position,
        });
        true
    }

    /// Ensures that the collected runs cover the complete logical value.
    pub(crate) fn validate_complete(&self, position: NtfsPosition) -> Result<()> {
        let mapped_size = self.runs.last().map_or(0, |run| run.end);
        if mapped_size < self.data_size {
            return Err(NtfsError::InvalidDataRunMapping {
                position,
                expected: self.data_size,
                actual: mapped_size,
            });
        }

        Ok(())
    }

    /// Reads one logical range, stitching physical and sparse data runs into `data`.
    pub(crate) fn read_exact_at<T, F>(
        &self,
        fs: &mut T,
        offset: u64,
        data: &mut [u8],
        out_of_bounds: F,
    ) -> Result<NtfsPosition>
    where
        T: Read + Seek,
        F: Fn() -> NtfsError,
    {
        let data_len = u64::try_from(data.len()).map_err(|_| out_of_bounds())?;
        let end = offset
            .checked_add(data_len)
            .filter(|end| *end <= self.data_size)
            .ok_or_else(&out_of_bounds)?;
        let mut run_index = self.runs.partition_point(|run| run.end <= offset);
        let first_run = self
            .runs
            .get(run_index)
            .filter(|run| run.start <= offset && offset < run.end)
            .ok_or_else(&out_of_bounds)?;
        let position = first_run.position + (offset - first_run.start);
        let mut data_offset = 0usize;
        let mut stream_offset = offset;

        while stream_offset < end {
            let run = self
                .runs
                .get(run_index)
                .filter(|run| run.start <= stream_offset && stream_offset < run.end)
                .ok_or_else(&out_of_bounds)?;
            let offset_in_run = stream_offset - run.start;
            let bytes_in_run = usize::try_from(run.end - stream_offset).unwrap_or(usize::MAX);
            let bytes_to_read = bytes_in_run.min(data.len() - data_offset);
            let target = &mut data[data_offset..data_offset + bytes_to_read];
            if let Some(run_position) = (run.position + offset_in_run).value() {
                fs.seek(SeekFrom::Start(run_position.get()))?;
                fs.read_exact(target)?;
            } else {
                target.fill(0);
            }
            data_offset += bytes_to_read;
            stream_offset += bytes_to_read as u64;
            run_index += 1;
        }

        Ok(position)
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn incomplete_mapping_is_rejected() {
        let mut runs = MappedDataRuns::new(8);
        assert!(runs.push(4, NtfsPosition::none()));

        assert!(matches!(
            runs.validate_complete(NtfsPosition::none()),
            Err(NtfsError::InvalidDataRunMapping {
                expected: 8,
                actual: 4,
                ..
            })
        ));
    }

    #[test]
    fn complete_or_overallocated_mapping_is_accepted() {
        let mut complete = MappedDataRuns::new(8);
        assert!(complete.push(8, NtfsPosition::none()));
        assert!(complete.validate_complete(NtfsPosition::none()).is_ok());

        let mut overallocated = MappedDataRuns::new(8);
        assert!(overallocated.push(16, NtfsPosition::none()));
        assert!(
            overallocated
                .validate_complete(NtfsPosition::none())
                .is_ok()
        );
    }
}