1use super::{FlatDagCluster, FlatDagGroup};
5use crate::{codec, Workspace};
6use alloc::vec::Vec;
7
8#[path = "dag_format_v2.rs"]
9pub mod v2;
10
11pub const DEFAULT_PAGE_SIZE: usize = 128 * 1024;
13pub const V1_VERTEX_CODEC_VERSION: u8 = 1;
15pub const V1_VERTEX_CODEC_LEVEL: u8 = 2;
17pub const V1_INDEX_CODEC_VERSION: u8 = 1;
19#[derive(Clone, Copy, Debug, PartialEq, Eq)]
21#[non_exhaustive]
22pub enum Error {
23 Invalid,
25 Unsupported,
27 Limit,
29 Allocation,
31 Codec(crate::Error),
33}
34impl core::fmt::Display for Error {
35 fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
36 write!(f, "DAG format: {self:?}")
37 }
38}
39#[cfg(feature = "std")]
40impl std::error::Error for Error {}
41impl From<crate::Error> for Error {
42 fn from(e: crate::Error) -> Self {
43 Self::Codec(e)
44 }
45}
46fn add(a: usize, b: usize) -> Result<usize, Error> {
47 a.checked_add(b).ok_or(Error::Limit)
48}
49fn mul(a: usize, b: usize) -> Result<usize, Error> {
50 a.checked_mul(b).ok_or(Error::Limit)
51}
52fn uint(v: usize) -> Result<u32, Error> {
53 u32::try_from(v).map_err(|_| Error::Limit)
54}
55fn size(v: u32) -> Result<usize, Error> {
56 usize::try_from(v).map_err(|_| Error::Limit)
57}
58fn push(v: &mut Vec<u8>, b: &[u8]) -> Result<(), Error> {
59 v.try_reserve(b.len()).map_err(|_| Error::Allocation)?;
60 v.extend_from_slice(b);
61 Ok(())
62}
63fn copy_bytes(b: &[u8]) -> Result<Vec<u8>, Error> {
64 let mut out = Vec::new();
65 push(&mut out, b)?;
66 Ok(out)
67}
68fn put(v: &mut Vec<u8>, x: u32) -> Result<(), Error> {
69 push(v, &x.to_le_bytes())
70}
71fn word(b: &[u8], at: usize) -> Result<u32, Error> {
72 let a = b.get(at..add(at, 4)?).ok_or(Error::Invalid)?;
73 Ok(u32::from_le_bytes([a[0], a[1], a[2], a[3]]))
74}
75fn words(b: &[u8], at: usize, n: usize) -> Result<Vec<u32>, Error> {
76 let end = add(at, mul(n, 4)?)?;
77 let bytes = b.get(at..end).ok_or(Error::Invalid)?;
78 let mut out = Vec::new();
79 out.try_reserve_exact(n).map_err(|_| Error::Allocation)?;
80 for v in bytes.as_chunks::<4>().0 {
81 out.push(u32::from_le_bytes([v[0], v[1], v[2], v[3]]));
82 }
83 Ok(out)
84}
85fn bounds(w: &[u32]) -> Result<(), Error> {
86 if w[..4].iter().any(|&v| !f32::from_bits(v).is_finite()) || f32::from_bits(w[3]) < 0. {
87 return Err(Error::Invalid);
88 }
89 Ok(())
90}
91fn floats(v: &mut Vec<u8>, center: [f32; 3], radius: f32) -> Result<(), Error> {
92 for f in center.into_iter().chain([radius]) {
93 put(v, f.to_bits())?;
94 }
95 Ok(())
96}
97#[derive(Debug)]
100#[non_exhaustive]
101pub struct GeometryGeneric<I: crate::Index = u32> {
102 pub cluster: u32,
104 pub vertices: Vec<(u32, [f32; 3])>,
106 pub indices: Vec<I>,
108}
109#[derive(Debug)]
111#[non_exhaustive]
112pub struct Reader<'a> {
113 bytes: &'a [u8],
114 groups: usize,
115 clusters: usize,
116 pages: usize,
117 page_table: usize,
118}
119impl<'a> Reader<'a> {
120 pub fn read(bytes: &'a [u8], workspace: &mut Workspace) -> Result<Self, Error> {
126 if bytes.get(..4) != Some(b"MDAG") {
127 return Err(Error::Invalid);
128 }
129 if word(bytes, 4)? != 1 || word(bytes, 8)? != 0 {
130 return Err(Error::Unsupported);
131 }
132 let groups = size(word(bytes, 12)?)?;
133 let clusters = size(word(bytes, 16)?)?;
134 let pages = size(word(bytes, 20)?)?;
135 let page_size = size(word(bytes, 24)?)?;
136 if size(word(bytes, 28)?)? != bytes.len() || page_size == 0 {
137 return Err(Error::Invalid);
138 }
139 let page_table = add(add(32, mul(groups, 32)?)?, mul(clusters, 64)?)?;
140 let mut end = add(page_table, mul(pages, 16)?)?;
141 if end > bytes.len() {
142 return Err(Error::Invalid);
143 }
144 let r = Self {
145 bytes,
146 groups,
147 clusters,
148 pages,
149 page_table,
150 };
151 let mut next = 0;
152 for g in 0..groups {
153 let w = words(bytes, add(32, mul(g, 32)?)?, 8)?;
154 bounds(&w)?;
155 let error = f32::from_bits(w[4]);
156 if !error.is_finite() || error < 0. || w[5] >= 64 || size(w[6])? != next || w[7] == 0 {
157 return Err(Error::Invalid);
158 }
159 next = add(next, size(w[7])?)?;
160 if next > clusters {
161 return Err(Error::Invalid);
162 }
163 for c in size(w[6])?..next {
164 let cl = r.cluster(c)?;
165 if size(cl[0])? != g {
166 return Err(Error::Invalid);
167 }
168 }
169 }
170 if next != clusters {
171 return Err(Error::Invalid);
172 }
173 let mut next_cluster = 0;
174 let mut next_index = 0usize;
175 for p in 0..pages {
176 let w = r.page(p)?;
177 if size(w[0])? != end
178 || w[1] == 0
179 || size(w[1])? > page_size
180 || size(w[2])? != next_cluster
181 || w[3] == 0
182 {
183 return Err(Error::Invalid);
184 }
185 end = add(end, size(w[1])?)?;
186 if end > bytes.len() {
187 return Err(Error::Invalid);
188 }
189 next_cluster = add(next_cluster, size(w[3])?)?;
190 if next_cluster > clusters {
191 return Err(Error::Invalid);
192 }
193 for c in size(w[2])?..next_cluster {
194 let cl = r.cluster(c)?;
195 if size(cl[14])? != next_index {
196 return Err(Error::Invalid);
197 }
198 next_index = add(next_index, size(cl[7])?)?;
199 uint(next_index)?;
200 }
201 r.decode_page(p, &bytes[size(w[0])?..end], workspace)?;
202 }
203 if end != bytes.len() || next_cluster != clusters {
204 return Err(Error::Invalid);
205 }
206 Ok(r)
207 }
208 fn cluster(&self, c: usize) -> Result<Vec<u32>, Error> {
209 if c >= self.clusters {
210 return Err(Error::Invalid);
211 }
212 words(
213 self.bytes,
214 add(add(32, mul(self.groups, 32)?)?, mul(c, 64)?)?,
215 16,
216 )
217 }
218 fn page(&self, p: usize) -> Result<Vec<u32>, Error> {
219 if p >= self.pages {
220 return Err(Error::Invalid);
221 }
222 words(self.bytes, add(self.page_table, mul(p, 16)?)?, 4)
223 }
224 pub fn page_count(&self) -> usize {
226 self.pages
227 }
228 pub fn cluster_page(&self, c: usize) -> Result<usize, Error> {
234 size(self.cluster(c)?[2])
235 }
236 pub fn cluster_record(&self, c: usize) -> Result<FlatDagCluster, Error> {
240 let w = self.cluster(c)?;
241 Ok(FlatDagCluster {
242 first_index: w[14],
243 index_count: w[7],
244 group: w[0],
245 refined: i32::from_le_bytes(w[1].to_le_bytes()),
246 center: [
247 f32::from_bits(w[10]),
248 f32::from_bits(w[11]),
249 f32::from_bits(w[12]),
250 ],
251 radius: f32::from_bits(w[13]),
252 })
253 }
254 pub fn group_count(&self) -> usize {
256 self.groups
257 }
258 pub fn cluster_count(&self) -> usize {
260 self.clusters
261 }
262 pub fn page_range(&self, p: usize) -> Result<core::ops::Range<usize>, Error> {
266 let w = self.page(p)?;
267 let start = size(w[0])?;
268 Ok(start..add(start, size(w[1])?)?)
269 }
270 pub fn group(&self, g: usize) -> Result<FlatDagGroup, Error> {
274 if g >= self.groups {
275 return Err(Error::Invalid);
276 }
277 let w = words(self.bytes, add(32, mul(g, 32)?)?, 8)?;
278 Ok(FlatDagGroup {
279 center: [
280 f32::from_bits(w[0]),
281 f32::from_bits(w[1]),
282 f32::from_bits(w[2]),
283 ],
284 radius: f32::from_bits(w[3]),
285 error: f32::from_bits(w[4]),
286 depth: i32::try_from(w[5]).map_err(|_| Error::Invalid)?,
287 first_cluster: w[6],
288 cluster_count: w[7],
289 })
290 }
291 #[inline]
297 pub fn decode_page(
298 &self,
299 p: usize,
300 bytes: &[u8],
301 workspace: &mut Workspace,
302 ) -> Result<Vec<Geometry>, Error> {
303 self.decode_page_generic::<u32>(p, bytes, workspace)
304 .map(|values| values.into_iter().map(Into::into).collect())
305 }
306 pub fn decode_page_generic<I: crate::Index>(
308 &self,
309 p: usize,
310 bytes: &[u8],
311 workspace: &mut Workspace,
312 ) -> Result<Vec<GeometryGeneric<I>>, Error> {
313 let page = self.page(p)?;
314 if bytes.len() != size(page[1])? {
315 return Err(Error::Invalid);
316 }
317 let mut out = Vec::new();
318 let count = size(page[3])?;
319 if count > bytes.len() / 16 {
320 return Err(Error::Invalid);
321 }
322 out.try_reserve_exact(count)
323 .map_err(|_| Error::Allocation)?;
324 let mut next = 0;
325 for c in size(page[2])?..add(size(page[2])?, count)? {
326 let w = self.cluster(c)?;
327 bounds(&w[10..14])?;
328 let group = self.group(size(w[0])?)?;
329 let refined = i32::from_le_bytes(w[1].to_le_bytes());
330 if refined != -1 {
331 let child_id = usize::try_from(refined).map_err(|_| Error::Invalid)?;
332 if child_id >= size(w[0])? {
333 return Err(Error::Invalid);
334 }
335 let child = self.group(child_id)?;
336 if child.depth >= group.depth || child.error > group.error {
337 return Err(Error::Invalid);
338 }
339 } else if group.depth != 0 {
340 return Err(Error::Invalid);
341 }
342 if size(w[2])? != p || size(w[3])? != next || w[9] & !3 != 0 || w[15] != 0 {
343 return Err(Error::Invalid);
344 }
345 let nv = size(w[6])?;
346 let ni = size(w[7])?;
347 if nv == 0
348 || nv > 768
349 || ni == 0
350 || ni > 768
351 || !ni.is_multiple_of(3)
352 || w[8] != uint(add(mul(nv, 16)?, mul(ni, 4)?)?)?
353 {
354 return Err(Error::Invalid);
355 }
356 let split = add(next, size(w[4])?)?;
357 let end = add(split, size(w[5])?)?;
358 let vb = bytes.get(next..split).ok_or(Error::Invalid)?;
359 let ib = bytes.get(split..end).ok_or(Error::Invalid)?;
360 if (w[9] & 1 == 0 && vb.len() != mul(nv, 16)?)
361 || (w[9] & 2 == 0 && ib.len() != mul(ni, 4)?)
362 {
363 return Err(Error::Invalid);
364 }
365 if (w[9] & 1 != 0 && codec::decode_vertex_version(vb)? != V1_VERTEX_CODEC_VERSION)
366 || (w[9] & 2 != 0 && codec::decode_index_version(ib)? != V1_INDEX_CODEC_VERSION)
367 {
368 return Err(Error::Unsupported);
369 }
370 let vertices = if w[9] & 1 != 0 {
371 codec::decode_vertex_buffer(nv, 16, vb, workspace)?
372 } else {
373 copy_bytes(vb)?
374 };
375 let indices = if w[9] & 2 != 0 {
376 codec::decode_index_sequence(ni, 4, ib, workspace)?
377 } else {
378 copy_bytes(ib)?
379 };
380 if vertices.len() != mul(nv, 16)? || indices.len() != mul(ni, 4)? {
381 return Err(Error::Invalid);
382 }
383 let mut geometry = GeometryGeneric {
384 cluster: uint(c)?,
385 vertices: Vec::new(),
386 indices: I::from_vec(words(&indices, 0, ni)?, workspace)?,
387 };
388 geometry
389 .vertices
390 .try_reserve_exact(nv)
391 .map_err(|_| Error::Allocation)?;
392 for v in vertices.as_chunks::<16>().0 {
393 let w = words(v, 0, 4)?;
394 let pos = [
395 f32::from_bits(w[1]),
396 f32::from_bits(w[2]),
397 f32::from_bits(w[3]),
398 ];
399 if pos.iter().any(|v| !v.is_finite()) {
400 return Err(Error::Invalid);
401 }
402 geometry.vertices.push((w[0], pos));
403 }
404 if geometry
405 .indices
406 .iter()
407 .any(|&i| size(i.to_u32()).map_or(true, |i| i >= nv))
408 {
409 return Err(Error::Invalid);
410 }
411 let mut seen = 0usize;
413 for &i in &geometry.indices {
414 let i = size(i.to_u32())?;
415 if i > seen {
416 return Err(Error::Invalid);
417 }
418 if i == seen {
419 seen = add(seen, 1)?;
420 }
421 }
422 if seen != nv {
423 return Err(Error::Invalid);
424 }
425 let mut ids = Vec::new();
427 ids.try_reserve_exact(nv).map_err(|_| Error::Allocation)?;
428 ids.extend(geometry.vertices.iter().map(|v| v.0));
429 ids.sort_unstable();
430 if ids.windows(2).any(|p| p[0] == p[1]) {
431 return Err(Error::Invalid);
432 }
433 out.push(geometry);
434 next = end;
435 }
436 if next != bytes.len() {
437 return Err(Error::Invalid);
438 }
439 Ok(out)
440 }
441}
442
443pub fn write_generic<I: crate::Index>(
457 groups: &[FlatDagGroup],
458 clusters: &[FlatDagCluster],
459 positions: &[[f32; 3]],
460 indices: &[I],
461 page_size: usize,
462 workspace: &mut Workspace,
463) -> Result<Vec<u8>, Error> {
464 uint(page_size)?;
465 uint(groups.len())?;
466 uint(clusters.len())?;
467 if page_size == 0 {
468 return Err(Error::Invalid);
469 }
470 let mut tables = Vec::new();
471 let mut payload = Vec::new();
472 let mut pages = Vec::<[u32; 4]>::new();
473 let mut used = 0usize;
474 let mut first = 0usize;
475 let mut expected_index = 0usize;
476 for (c, cluster) in clusters.iter().enumerate() {
477 let start = size(cluster.first_index)?;
478 let ni = size(cluster.index_count)?;
479 if start != expected_index {
480 return Err(Error::Invalid);
481 }
482 expected_index = add(start, ni)?;
483 if ni == 0 || ni > 768 || !ni.is_multiple_of(3) {
484 return Err(Error::Invalid);
485 }
486 let src = indices.get(start..add(start, ni)?).ok_or(Error::Invalid)?;
487 let mut map = Vec::<u32>::new();
488 map.try_reserve_exact(ni).map_err(|_| Error::Allocation)?;
489 let mut vb = Vec::new();
490 let mut local = Vec::new();
491 local.try_reserve_exact(ni).map_err(|_| Error::Allocation)?;
492 for &id in src {
493 let id = id.to_u32();
494 let next = uint(map.len())?;
495 let index = match map.iter().position(|&v| v == id) {
496 Some(i) => uint(i)?,
497 None => {
498 map.push(id);
499 next
500 }
501 };
502 if index == next {
503 let pos = positions.get(size(id)?).ok_or(Error::Invalid)?;
504 put(&mut vb, id)?;
505 for f in pos {
506 put(&mut vb, f.to_bits())?;
507 }
508 }
509 local.push(index);
510 }
511 let nv = map.len();
512 let mut ib = Vec::new();
513 for &i in &local {
514 put(&mut ib, i)?;
515 }
516 let raw = add(vb.len(), ib.len())?;
517 let mut flags = 0;
518 let encoded = codec::encode_vertex_buffer(
519 &vb,
520 nv,
521 16,
522 codec::VertexEncoding::new(V1_VERTEX_CODEC_VERSION, V1_VERTEX_CODEC_LEVEL)?,
523 workspace,
524 )?;
525 if encoded.len() < vb.len() {
526 vb = encoded;
527 flags |= 1;
528 }
529 let encoded = codec::encode_index_sequence_generic(
530 &local,
531 codec::IndexEncoding::new(V1_INDEX_CODEC_VERSION)?,
532 workspace,
533 )?;
534 if encoded.len() < ib.len() {
535 ib = encoded;
536 flags |= 2;
537 }
538 let length = add(vb.len(), ib.len())?;
539 if length > page_size {
540 return Err(Error::Limit);
541 }
542 if add(used, length)? > page_size {
543 pages.try_reserve(1).map_err(|_| Error::Allocation)?;
544 pages.push([
545 uint(payload.len() - used)?,
546 uint(used)?,
547 uint(first)?,
548 uint(c - first)?,
549 ]);
550 first = c;
551 used = 0;
552 }
553 for w in [
554 cluster.group,
555 u32::from_le_bytes(cluster.refined.to_le_bytes()),
556 uint(pages.len())?,
557 uint(used)?,
558 uint(vb.len())?,
559 uint(ib.len())?,
560 uint(nv)?,
561 uint(ni)?,
562 uint(raw)?,
563 flags,
564 ] {
565 put(&mut tables, w)?;
566 }
567 floats(&mut tables, cluster.center, cluster.radius)?;
568 put(&mut tables, cluster.first_index)?;
569 put(&mut tables, 0)?;
570 push(&mut payload, &vb)?;
571 push(&mut payload, &ib)?;
572 used = add(used, length)?;
573 }
574 if expected_index != indices.len() {
575 return Err(Error::Invalid);
576 }
577 if used != 0 {
578 pages.try_reserve(1).map_err(|_| Error::Allocation)?;
579 pages.push([
580 uint(payload.len() - used)?,
581 uint(used)?,
582 uint(first)?,
583 uint(clusters.len() - first)?,
584 ]);
585 }
586 let base = add(
587 add(add(32, mul(groups.len(), 32)?)?, tables.len())?,
588 mul(pages.len(), 16)?,
589 )?;
590 let mut out = Vec::new();
591 push(&mut out, b"MDAG")?;
592 for w in [
593 1,
594 0,
595 uint(groups.len())?,
596 uint(clusters.len())?,
597 uint(pages.len())?,
598 uint(page_size)?,
599 uint(add(base, payload.len())?)?,
600 ] {
601 put(&mut out, w)?;
602 }
603 for g in groups {
604 floats(&mut out, g.center, g.radius)?;
605 for w in [
606 g.error.to_bits(),
607 u32::try_from(g.depth).map_err(|_| Error::Invalid)?,
608 g.first_cluster,
609 g.cluster_count,
610 ] {
611 put(&mut out, w)?;
612 }
613 }
614 push(&mut out, &tables)?;
615 for p in pages {
616 for w in [uint(add(base, size(p[0])?)?)?, p[1], p[2], p[3]] {
617 put(&mut out, w)?;
618 }
619 }
620 push(&mut out, &payload)?;
621 Reader::read(&out, workspace)?;
622 Ok(out)
623}
624
625#[inline]
627pub fn write(
628 groups: &[FlatDagGroup],
629 clusters: &[FlatDagCluster],
630 positions: &[[f32; 3]],
631 indices: &[u32],
632 page_size: usize,
633 workspace: &mut Workspace,
634) -> Result<Vec<u8>, Error> {
635 write_generic::<u32>(groups, clusters, positions, indices, page_size, workspace)
636}
637
638#[derive(Debug)]
642#[non_exhaustive]
643pub struct Geometry {
644 pub cluster: u32,
646 pub vertices: Vec<(u32, [f32; 3])>,
648 pub indices: Vec<u32>,
650}
651impl From<GeometryGeneric<u32>> for Geometry {
652 #[inline]
653 fn from(value: GeometryGeneric<u32>) -> Self {
654 Self {
655 cluster: value.cluster,
656 vertices: value.vertices,
657 indices: value.indices,
658 }
659 }
660}
661
662impl From<Geometry> for GeometryGeneric<u32> {
663 #[inline]
664 fn from(value: Geometry) -> Self {
665 Self {
666 cluster: value.cluster,
667 vertices: value.vertices,
668 indices: value.indices,
669 }
670 }
671}