copc_reader/
ranged.rs

1//! Lazy, range-request-driven COPC reading.
2//!
3//! [`CopcRangeReader`] fetches only what a query needs from a [`RangeRead`]
4//! source: the LAS header and VLRs at open, hierarchy pages on demand as
5//! queries touch their subtrees, and point chunks via coalesced range reads.
6
7use std::collections::{BTreeMap, HashSet};
8use std::io::{Read, Seek, SeekFrom};
9
10use copc_core::{
11    ColumnSelection, CopcInfo, Entry, EntryAvailability, Error, HierarchyPage, LasColumnBatch,
12    Result, VoxelKey,
13};
14use las::Point;
15use laz::LazVlr;
16
17use crate::points::{
18    decode_chunk_points, select_point_chunks_from, selected_column_builders,
19    total_candidate_points, validate_query, voxel_bounds, BoundsSelection, ChunkColumnDecoder,
20    PointQuery, MAX_INITIAL_COLUMN_RESERVE_POINTS,
21};
22use crate::range_read::RangeRead;
23use crate::{
24    extract_required_vlrs, insert_point_chunk_range, point_format_for, read_las_header, read_vlrs,
25    transforms_for, validate_hierarchy_entry, validate_hierarchy_page_byte_size,
26    validate_range_in_file, CopcDataRanges, HierarchyReadLimits, LasHeader, LAS_HEADER_SIZE_14,
27};
28
29/// Adjacent chunk ranges closer than this are fetched with one request.
30const RANGE_COALESCE_GAP_BYTES: u64 = 64 * 1024;
31/// Bound one remote allocation when many nearby chunks are coalesced.
32const MAX_COALESCED_RANGE_BYTES: u64 = 64 * 1024 * 1024;
33/// Cap on the VLR section fetched eagerly at open.
34const MAX_VLR_SECTION_BYTES: u64 = 64 * 1024 * 1024;
35
36/// Presents a fetched byte section at its absolute file offsets so the
37/// shared header/VLR parsers can run over it unchanged.
38struct SectionReader {
39    base: u64,
40    data: Vec<u8>,
41    position: u64,
42}
43
44impl SectionReader {
45    fn new(base: u64, data: Vec<u8>) -> Self {
46        Self {
47            base,
48            data,
49            position: base,
50        }
51    }
52}
53
54impl Read for SectionReader {
55    fn read(&mut self, buf: &mut [u8]) -> std::io::Result<usize> {
56        let start = usize::try_from(self.position.checked_sub(self.base).ok_or_else(|| {
57            std::io::Error::new(
58                std::io::ErrorKind::InvalidInput,
59                "read before fetched section",
60            )
61        })?)
62        .map_err(|_| {
63            std::io::Error::new(
64                std::io::ErrorKind::InvalidInput,
65                "fetched section position exceeds usize",
66            )
67        })?;
68        if start > self.data.len() {
69            return Err(std::io::Error::new(
70                std::io::ErrorKind::UnexpectedEof,
71                "read past fetched section",
72            ));
73        }
74        let available = &self.data[start..];
75        let take = available.len().min(buf.len());
76        buf[..take].copy_from_slice(&available[..take]);
77        self.position += take as u64;
78        Ok(take)
79    }
80}
81
82impl Seek for SectionReader {
83    fn seek(&mut self, pos: SeekFrom) -> std::io::Result<u64> {
84        let target = match pos {
85            SeekFrom::Start(offset) => Some(offset),
86            SeekFrom::Current(delta) => self.position.checked_add_signed(delta),
87            SeekFrom::End(delta) => (self.base + self.data.len() as u64).checked_add_signed(delta),
88        }
89        .ok_or_else(|| {
90            std::io::Error::new(std::io::ErrorKind::InvalidInput, "seek out of range")
91        })?;
92        self.position = target;
93        Ok(self.position)
94    }
95}
96
97/// Lazy COPC reader over a byte-range source.
98///
99/// Opening fetches the LAS header, the VLR section, and the root hierarchy
100/// page. Hierarchy pages for deeper subtrees are fetched only when a query's
101/// LOD/bounds selection can reach them, and point chunks are fetched with
102/// coalesced range requests.
103pub struct CopcRangeReader<S: RangeRead> {
104    source: S,
105    file_len: u64,
106    header: LasHeader,
107    copc_info: CopcInfo,
108    laszip_vlr: LazVlr,
109    hierarchy: BTreeMap<VoxelKey, Entry>,
110    pending_pages: Vec<Entry>,
111    visited_pages: HashSet<(u64, u64)>,
112    limits: HierarchyReadLimits,
113    loaded_point_total: u64,
114    data_ranges: CopcDataRanges,
115    point_ranges: BTreeMap<u64, (u64, VoxelKey)>,
116}
117
118impl<S: RangeRead> CopcRangeReader<S> {
119    pub fn open(mut source: S) -> Result<Self> {
120        let file_len = source.len()?;
121        if file_len < u64::from(LAS_HEADER_SIZE_14) {
122            return Err(Error::InvalidData(format!(
123                "file is {file_len} bytes; COPC requires at least {LAS_HEADER_SIZE_14}"
124            )));
125        }
126        let mut header_bytes = vec![0u8; usize::from(LAS_HEADER_SIZE_14)];
127        source.read_range(0, &mut header_bytes)?;
128        let mut header_section = SectionReader::new(0, header_bytes);
129        let header = read_las_header(&mut header_section, file_len)?;
130        let header_size = header_section
131            .stream_position()
132            .map_err(|e| Error::io("record header size", e))?;
133
134        let vlr_section_len = u64::from(header.offset_to_point_data)
135            .checked_sub(header_size)
136            .ok_or_else(|| Error::InvalidData("VLR section precedes LAS header end".into()))?;
137        if vlr_section_len > MAX_VLR_SECTION_BYTES {
138            return Err(Error::InvalidData(format!(
139                "VLR section is {vlr_section_len} bytes, max supported is {MAX_VLR_SECTION_BYTES}"
140            )));
141        }
142        let mut vlr_bytes = vec![0u8; vlr_section_len as usize];
143        source.read_range(header_size, &mut vlr_bytes)?;
144        let mut vlr_section = SectionReader::new(header_size, vlr_bytes);
145        let vlrs = read_vlrs(
146            &mut vlr_section,
147            header.number_of_vlrs,
148            file_len,
149            u64::from(header.offset_to_point_data),
150        )?;
151        let (copc_info, laszip_vlr) = extract_required_vlrs(&vlrs)?;
152        validate_hierarchy_page_byte_size(copc_info.root_hier_size)?;
153        let (hierarchy_start, hierarchy_len) =
154            validate_root_hierarchy_evlr(&mut source, file_len, &copc_info)?;
155        let data_ranges = CopcDataRanges::new(&header, hierarchy_start, hierarchy_len)?;
156
157        let mut reader = Self {
158            source,
159            file_len,
160            header,
161            copc_info,
162            laszip_vlr,
163            hierarchy: BTreeMap::new(),
164            pending_pages: Vec::new(),
165            visited_pages: HashSet::new(),
166            limits: HierarchyReadLimits::default(),
167            loaded_point_total: 0,
168            data_ranges,
169            point_ranges: BTreeMap::new(),
170        };
171        let root = Entry {
172            key: VoxelKey::root(),
173            offset: reader.copc_info.root_hier_offset,
174            byte_size: i32::try_from(reader.copc_info.root_hier_size)
175                .map_err(|_| Error::InvalidData("root hierarchy size exceeds i32".into()))?,
176            point_count: -1,
177        };
178        reader.load_page(root)?;
179        Ok(reader)
180    }
181
182    pub fn header(&self) -> &LasHeader {
183        &self.header
184    }
185
186    pub fn copc_info(&self) -> &CopcInfo {
187        &self.copc_info
188    }
189
190    /// Point-data hierarchy entries matching `query`, loading any hierarchy
191    /// pages the query can reach that have not been fetched yet.
192    pub fn hierarchy_for(&mut self, query: PointQuery) -> Result<Vec<Entry>> {
193        validate_query(query)?;
194        self.ensure_hierarchy_for(query)?;
195        select_point_chunks_from(self.hierarchy.values(), &self.copc_info, query)
196    }
197
198    /// Materialized column read over the chunks selected by `query`.
199    pub fn read_columns(
200        &mut self,
201        query: PointQuery,
202        selection: ColumnSelection,
203    ) -> Result<LasColumnBatch> {
204        let chunks = self.hierarchy_for(query)?;
205        let point_format = point_format_for(&self.header)?;
206        let bounds = match query.bounds {
207            BoundsSelection::All => None,
208            BoundsSelection::Within(bounds) => Some(bounds),
209        };
210        let decoder = ChunkColumnDecoder::new(
211            self.laszip_vlr.clone(),
212            point_format,
213            transforms_for(&self.header),
214            bounds,
215        )?;
216        let capacity = match bounds {
217            Some(_) => 0,
218            None => total_candidate_points(&chunks)?.min(MAX_INITIAL_COLUMN_RESERVE_POINTS),
219        };
220        let mut columns = selected_column_builders(point_format, selection, capacity)?;
221        let mut accepted_points = 0usize;
222        for group in coalesce_chunks(&chunks, RANGE_COALESCE_GAP_BYTES, MAX_COALESCED_RANGE_BYTES) {
223            let bytes = self.fetch_range(group.start, group.end)?;
224            for entry in group.entries {
225                let (slice, points_in_chunk) = chunk_slice(&bytes, group.start, entry)?;
226                accepted_points +=
227                    decoder.decode_into(slice, points_in_chunk, &mut columns, None)?;
228            }
229        }
230        let batch = LasColumnBatch {
231            len: accepted_points,
232            columns,
233        };
234        batch.validate()?;
235        Ok(batch)
236    }
237
238    /// Materialized row read over the chunks selected by `query`.
239    pub fn read_points(&mut self, query: PointQuery) -> Result<Vec<Point>> {
240        let chunks = self.hierarchy_for(query)?;
241        let point_format = point_format_for(&self.header)?;
242        let transforms = transforms_for(&self.header);
243        let bounds = match query.bounds {
244            BoundsSelection::All => None,
245            BoundsSelection::Within(bounds) => Some(bounds),
246        };
247        let capacity = match bounds {
248            Some(_) => 0,
249            None => total_candidate_points(&chunks)?.min(MAX_INITIAL_COLUMN_RESERVE_POINTS),
250        };
251        let mut points = Vec::with_capacity(capacity);
252        for group in coalesce_chunks(&chunks, RANGE_COALESCE_GAP_BYTES, MAX_COALESCED_RANGE_BYTES) {
253            let bytes = self.fetch_range(group.start, group.end)?;
254            for entry in group.entries {
255                let (slice, points_in_chunk) = chunk_slice(&bytes, group.start, entry)?;
256                decode_chunk_points(
257                    slice,
258                    points_in_chunk,
259                    &self.laszip_vlr,
260                    &point_format,
261                    &transforms,
262                    bounds,
263                    &mut points,
264                )?;
265            }
266        }
267        Ok(points)
268    }
269
270    fn fetch_range(&mut self, start: u64, end: u64) -> Result<Vec<u8>> {
271        let len = usize::try_from(
272            end.checked_sub(start)
273                .ok_or_else(|| Error::InvalidData("chunk range end precedes its start".into()))?,
274        )
275        .map_err(|_| Error::InvalidData("chunk range exceeds usize".into()))?;
276        let mut bytes = vec![0u8; len];
277        self.source.read_range(start, &mut bytes)?;
278        Ok(bytes)
279    }
280
281    /// Loads every pending hierarchy page whose subtree the query can reach.
282    fn ensure_hierarchy_for(&mut self, query: PointQuery) -> Result<()> {
283        loop {
284            let mut relevant = Vec::new();
285            let mut rest = Vec::new();
286            for entry in self.pending_pages.drain(..) {
287                if page_may_match(entry.key, &self.copc_info, query)? {
288                    relevant.push(entry);
289                } else {
290                    rest.push(entry);
291                }
292            }
293            self.pending_pages = rest;
294            if relevant.is_empty() {
295                return Ok(());
296            }
297            for entry in relevant {
298                self.load_page(entry)?;
299            }
300        }
301    }
302
303    fn load_page(&mut self, page_entry: Entry) -> Result<()> {
304        let byte_size = u64::try_from(page_entry.byte_size).map_err(|_| {
305            Error::InvalidData(format!(
306                "child hierarchy page {:?} has negative byte size {}",
307                page_entry.key, page_entry.byte_size
308            ))
309        })?;
310        if !self.visited_pages.insert((page_entry.offset, byte_size)) {
311            return Ok(());
312        }
313        if byte_size == 0 || !byte_size.is_multiple_of(copc_core::HIERARCHY_ENTRY_BYTES as u64) {
314            return Err(Error::InvalidData(format!(
315                "hierarchy page is {byte_size} bytes, not a multiple of {}",
316                copc_core::HIERARCHY_ENTRY_BYTES
317            )));
318        }
319        self.limits.add_page(byte_size)?;
320        validate_range_in_file(
321            page_entry.offset,
322            byte_size,
323            self.file_len,
324            "hierarchy page",
325        )?;
326        let bytes = self.fetch_range(page_entry.offset, page_entry.offset + byte_size)?;
327        let page = HierarchyPage::from_le_bytes(&bytes)?;
328        for entry in page.entries().iter().copied() {
329            validate_hierarchy_entry(entry, self.file_len, &self.data_ranges)?;
330            match self.hierarchy.get(&entry.key).copied() {
331                None => {}
332                Some(previous) if previous.is_child_page() && !entry.is_child_page() => {}
333                Some(previous) => {
334                    return Err(Error::InvalidData(format!(
335                        "duplicate hierarchy key {:?}: previous {previous:?}, new {entry:?}",
336                        entry.key
337                    )));
338                }
339            }
340            if entry.has_point_data() {
341                insert_point_chunk_range(&mut self.point_ranges, entry)?;
342            }
343            self.hierarchy.insert(entry.key, entry);
344            if let EntryAvailability::PointData { point_count } = entry.availability()? {
345                self.loaded_point_total = self
346                    .loaded_point_total
347                    .checked_add(u64::from(point_count))
348                    .ok_or_else(|| Error::InvalidData("hierarchy point total overflow".into()))?;
349            }
350            if entry.is_child_page() {
351                self.pending_pages.push(entry);
352            }
353        }
354        if self.loaded_point_total > self.header.number_of_points {
355            return Err(Error::InvalidData(format!(
356                "hierarchy point total {} exceeds LAS header point count {}",
357                self.loaded_point_total, self.header.number_of_points
358            )));
359        }
360        if self.pending_pages.is_empty() && self.loaded_point_total != self.header.number_of_points
361        {
362            return Err(Error::InvalidData(format!(
363                "hierarchy point total {} does not match LAS header point count {}",
364                self.loaded_point_total, self.header.number_of_points
365            )));
366        }
367        Ok(())
368    }
369}
370
371/// Whether the page rooted at `key` can contain entries matching `query`.
372/// Page entries all live in `key`'s subtree, so their levels are at least
373/// `key.level` and their bounds nest inside `key`'s voxel.
374fn page_may_match(key: VoxelKey, info: &CopcInfo, query: PointQuery) -> Result<bool> {
375    let (_, level_max) = crate::points::level_range(query.lod, info)?;
376    if key.level >= level_max {
377        return Ok(false);
378    }
379    if let BoundsSelection::Within(bounds) = query.bounds {
380        if key.level >= 0 && key.x >= 0 && key.y >= 0 && key.z >= 0 {
381            return Ok(voxel_bounds(key, info)?.intersects(bounds));
382        }
383    }
384    Ok(true)
385}
386
387struct ChunkGroup {
388    start: u64,
389    end: u64,
390    entries: Vec<Entry>,
391}
392
393/// Groups offset-sorted chunks so nearby ranges are fetched with one request.
394fn coalesce_chunks(chunks: &[Entry], gap: u64, max_range_bytes: u64) -> Vec<ChunkGroup> {
395    let mut groups: Vec<ChunkGroup> = Vec::new();
396    for entry in chunks {
397        let start = entry.offset;
398        let end = entry.offset + entry.byte_size.max(0) as u64;
399        match groups.last_mut() {
400            Some(group)
401                if start <= group.end.saturating_add(gap)
402                    && end.saturating_sub(group.start) <= max_range_bytes =>
403            {
404                group.end = group.end.max(end);
405                group.entries.push(*entry);
406            }
407            _ => groups.push(ChunkGroup {
408                start,
409                end,
410                entries: vec![*entry],
411            }),
412        }
413    }
414    groups
415}
416
417fn validate_root_hierarchy_evlr<S: RangeRead>(
418    source: &mut S,
419    file_len: u64,
420    info: &CopcInfo,
421) -> Result<(u64, u64)> {
422    let header_offset = info
423        .root_hier_offset
424        .checked_sub(60)
425        .ok_or_else(|| Error::InvalidData("COPC root hierarchy has no EVLR header".into()))?;
426    let mut header = [0u8; 60];
427    source.read_range(header_offset, &mut header)?;
428    let reserved = u16::from_le_bytes(header[0..2].try_into().expect("EVLR reserved width"));
429    let user_id = crate::trim_nul(&header[2..18]);
430    let record_id = u16::from_le_bytes(header[18..20].try_into().expect("EVLR record id width"));
431    let body_size = u64::from_le_bytes(header[20..28].try_into().expect("EVLR body size width"));
432    if reserved != 0 || user_id != "copc" || record_id != 1000 {
433        return Err(Error::InvalidData(
434            "COPC root hierarchy must immediately follow a copc/1000 EVLR header".into(),
435        ));
436    }
437    if info.root_hier_size > body_size {
438        return Err(Error::InvalidData(format!(
439            "COPC root hierarchy size {} exceeds hierarchy EVLR body size {body_size}",
440            info.root_hier_size
441        )));
442    }
443    crate::validate_range_in_file(
444        info.root_hier_offset,
445        body_size,
446        file_len,
447        "COPC hierarchy EVLR body",
448    )?;
449    Ok((info.root_hier_offset, body_size))
450}
451
452fn chunk_slice(group_bytes: &[u8], group_start: u64, entry: Entry) -> Result<(&[u8], usize)> {
453    let points_in_chunk = usize::try_from(entry.point_count).map_err(|_| {
454        Error::InvalidData(format!(
455            "negative point count {} for {:?}",
456            entry.point_count, entry.key
457        ))
458    })?;
459    let offset = usize::try_from(entry.offset - group_start)
460        .map_err(|_| Error::InvalidData("chunk offset exceeds usize".into()))?;
461    let byte_size = usize::try_from(entry.byte_size).map_err(|_| {
462        Error::InvalidData(format!(
463            "invalid byte size {} for {:?}",
464            entry.byte_size, entry.key
465        ))
466    })?;
467    let end = offset
468        .checked_add(byte_size)
469        .filter(|end| *end <= group_bytes.len())
470        .ok_or_else(|| Error::InvalidData("chunk range exceeds fetched group".into()))?;
471    Ok((&group_bytes[offset..end], points_in_chunk))
472}
copc_reader/ranged.rs

copc_reader/
ranged.rs
