1use crate::bytes::Cursor;
2use std::collections::{BTreeMap, BTreeSet};
3use std::fmt;
4use std::ops::Range;
5
6#[derive(Debug, Clone, Copy, PartialEq, Eq, serde::Serialize)]
7pub struct Error {
8 /// Parser byte offset; zero also represents errors without a byte location.
9 pub offset: usize,
10 /// Diagnostic text, not a stable machine-readable error code.
11 pub message: &'static str,
12}
13
14impl fmt::Display for Error {
15 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
16 write!(f, "{} at byte {:#x}", self.message, self.offset)
17 }
18}
19
20impl std::error::Error for Error {}
21
22type Result<T> = std::result::Result<T, Error>;
23
24impl Cursor<'_> {
25 fn chunk(&mut self) -> Result<Chunk> {
26 Ok(Chunk {
27 offset: u64::from_le_bytes(self.read()?),
28 length: u64::from(u32::from_le_bytes(self.read()?)),
29 })
30 }
31}
32
33#[derive(Debug, Clone, Copy, PartialEq, Eq)]
34pub enum FileType {
35 Section,
36 TableOfContents,
37}
38
39#[derive(Debug, Clone, Copy, PartialEq, Eq)]
40pub struct Chunk {
41 pub offset: u64,
42 pub length: u64,
43}
44
45impl Chunk {
46 pub(crate) fn absent(self) -> bool {
47 self.length == 0 && (self.offset == 0 || self.offset == u64::MAX)
48 }
49
50 fn range(self, data: &[u8]) -> Result<Range<usize>> {
51 let start = usize::try_from(self.offset).map_err(|_| Error {
52 offset: 0,
53 message: "Chunk offset exceeds address space",
54 })?;
55 let size = usize::try_from(self.length).map_err(|_| Error {
56 offset: start,
57 message: "Chunk length exceeds address space",
58 })?;
59 let end = start.checked_add(size).filter(|end| *end <= data.len());
60 match end {
61 Some(end) if start >= 1024 && end > start => Ok(start..end),
62 _ => Err(Error {
63 offset: start,
64 message: "Chunk extends outside the data area",
65 }),
66 }
67 }
68}
69
70#[derive(Debug)]
71pub struct Header {
72 pub file_type: FileType,
73 pub file_id: [u8; 16],
74 /// The parent table of contents' file identity; zero outside a notebook.
75 pub ancestor: [u8; 16],
76 /// CRC of the file name (a section's file name, a group's folder name).
77 pub name_crc: u32,
78 pub transaction_count: u32,
79 pub expected_length: u64,
80 pub version_id: [u8; 16],
81 pub generation: u64,
82 pub deny_read_id: [u8; 16],
83 pub transaction_log: Chunk,
84 pub root: Chunk,
85 pub hashed_chunks: Chunk,
86}
87
88impl Header {
89 pub fn parse(data: &[u8]) -> Result<Self> {
90 let mut c = Cursor {
91 bytes: data,
92 offset: 0,
93 };
94 let bytes = c.take(1024)?;
95 let mut c = Cursor { bytes, offset: 0 };
96 let file_type = match c.read()? {
97 [
98 0xe4,
99 0x52,
100 0x5c,
101 0x7b,
102 0x8c,
103 0xd8,
104 0xa7,
105 0x4d,
106 0xae,
107 0xb1,
108 0x53,
109 0x78,
110 0xd0,
111 0x29,
112 0x96,
113 0xd3,
114 ] => FileType::Section,
115 [
116 0xa1,
117 0x2f,
118 0xff,
119 0x43,
120 0xd9,
121 0xef,
122 0x76,
123 0x4c,
124 0x9e,
125 0xe2,
126 0x10,
127 0xea,
128 0x57,
129 0x22,
130 0x76,
131 0x5f,
132 ] => FileType::TableOfContents,
133 _ => {
134 return Err(Error {
135 offset: 0,
136 message: "Unrecognized revision-store file type",
137 });
138 }
139 };
140 let file_id = c.read()?;
141 c.take(16)?;
142 if c.read::<16>()?
143 != [
144 0x3f, 0xdd, 0x9a, 0x10, 0x1b, 0x91, 0xf5, 0x49, 0xa5, 0xd0, 0x17, 0x91, 0xed, 0xc8,
145 0xae, 0xd8,
146 ]
147 {
148 return Err(Error {
149 offset: 48,
150 message: "Unrecognized revision-store format",
151 });
152 }
153 c.take(12)?;
154 let version = u32::from_le_bytes(c.read()?);
155 let supported = match file_type {
156 FileType::Section => 0x2a,
157 FileType::TableOfContents => 0x1b,
158 };
159 if version != supported {
160 return Err(Error {
161 offset: 76,
162 message: "Unsupported file-format version",
163 });
164 }
165 c.take(16)?;
166 let transaction_count = u32::from_le_bytes(c.read()?);
167 if transaction_count == 0 {
168 return Err(Error {
169 offset: 96,
170 message: "Missing committed transaction",
171 });
172 }
173 c.take(28)?;
174 let ancestor = c.read()?;
175 let name_crc = u32::from_le_bytes(c.read()?);
176 let hashed_chunks = c.chunk()?;
177 let transaction_log = c.chunk()?;
178 let root = c.chunk()?;
179 c.take(12)?;
180 let expected_length = u64::from_le_bytes(c.read()?);
181 c.take(8)?;
182 let version_id = c.read()?;
183 let generation = u64::from_le_bytes(c.read()?);
184 let deny_read_id = c.read()?;
185 Ok(Self {
186 file_type,
187 file_id,
188 ancestor,
189 name_crc,
190 transaction_count,
191 expected_length,
192 version_id,
193 generation,
194 deny_read_id,
195 transaction_log,
196 root,
197 hashed_chunks,
198 })
199 }
200}
201
202#[derive(Debug, Clone, Copy, PartialEq, Eq)]
203pub enum Reference {
204 Data(Chunk),
205 NodeList(Chunk),
206}
207
208#[derive(Debug)]
209pub struct Node<'a> {
210 pub id: u16,
211 pub offset: usize,
212 pub payload: &'a [u8],
213 pub reference: Option<Reference>,
214}
215
216#[derive(Debug)]
217pub struct NodeList<'a> {
218 pub fragments: Vec<Chunk>,
219 pub nodes: Vec<Node<'a>>,
220}
221
222/// A file-node list fragment (MS-ONESTORE 2.4.1) before its nodes are decoded.
223pub(crate) struct Fragment<'a> {
224 pub id: u32,
225 pub sequence: u32,
226 pub next: Chunk,
227 body: Cursor<'a>,
228}
229
230impl<'a> Fragment<'a> {
231 /// The fragment `bytes`, which start at file offset `offset`.
232 pub(crate) fn parse(bytes: &'a [u8], offset: usize) -> Result<Self> {
233 if bytes.len() < 36 {
234 return Err(Error {
235 offset,
236 message: "Truncated file-node fragment",
237 });
238 }
239 let mut c = Cursor { bytes, offset };
240 if u64::from_le_bytes(c.read()?) != 0xa4567ab1f5f7f4c4 {
241 return Err(Error {
242 offset,
243 message: "Incorrect file-node fragment signature",
244 });
245 }
246 let id = u32::from_le_bytes(c.read()?);
247 let sequence = u32::from_le_bytes(c.read()?);
248 let end = offset + bytes.len();
249 let mut tail = Cursor {
250 bytes: &bytes[bytes.len() - 20..],
251 offset: end - 20,
252 };
253 let next = tail.chunk()?;
254 if u64::from_le_bytes(tail.read()?) != 0x8bc215c38233ba4b {
255 return Err(Error {
256 offset: end - 8,
257 message: "Incorrect file-node fragment footer",
258 });
259 }
260 Ok(Self {
261 id,
262 sequence,
263 next,
264 body: Cursor {
265 bytes: &bytes[16..bytes.len() - 20],
266 offset: offset + 16,
267 },
268 })
269 }
270
271 /// Decodes nodes into `nodes` until it holds `required` or the fragment ends; `data`
272 /// checks each data reference.
273 pub(crate) fn nodes(
274 self,
275 required: usize,
276 nodes: &mut Vec<Node<'a>>,
277 data: impl Fn(Chunk) -> Result<()>,
278 ) -> Result<()> {
279 let mut c = self.body;
280 while nodes.len() < required && c.bytes.len() >= 4 {
281 let offset = c.offset;
282 let raw = u32::from_le_bytes(c.read()?);
283 let size = usize::try_from((raw >> 10) & 0x1fff).unwrap();
284 if size < 4 {
285 return Err(Error {
286 offset,
287 message: "File node is shorter than its header",
288 });
289 }
290 let id = u16::try_from(raw & 0x3ff).unwrap();
291 let body = c.take(size - 4)?;
292 if id == 0xff {
293 break;
294 }
295 let mut fields = Cursor {
296 bytes: body,
297 offset: offset + 4,
298 };
299 let reference = match (raw >> 27) & 0xf {
300 0 => None,
301 base @ (1 | 2) => {
302 let (stp, nil, shift) = match (raw >> 23) & 3 {
303 0 => (u64::from_le_bytes(fields.read()?), u64::MAX, 0),
304 1 => (
305 u64::from(u32::from_le_bytes(fields.read()?)),
306 u64::from(u32::MAX),
307 0,
308 ),
309 2 => (
310 u64::from(u16::from_le_bytes(fields.read()?)),
311 u64::from(u16::MAX),
312 3,
313 ),
314 3 => (
315 u64::from(u32::from_le_bytes(fields.read()?)),
316 u64::from(u32::MAX),
317 3,
318 ),
319 _ => unreachable!(),
320 };
321 let cb = match (raw >> 25) & 3 {
322 0 => u64::from(u32::from_le_bytes(fields.read()?)),
323 1 => u64::from_le_bytes(fields.read()?),
324 2 => u64::from(fields.read::<1>()?[0]) * 8,
325 3 => u64::from(u16::from_le_bytes(fields.read()?)) * 8,
326 _ => unreachable!(),
327 };
328 let reference = Chunk {
329 offset: if cb == 0 && stp == nil {
330 u64::MAX
331 } else {
332 stp << shift
333 },
334 length: cb,
335 };
336 if base == 1 {
337 if !reference.absent() {
338 data(reference)?;
339 }
340 Some(Reference::Data(reference))
341 } else {
342 Some(Reference::NodeList(reference))
343 }
344 }
345 _ => {
346 return Err(Error {
347 offset,
348 message: "Unsupported file-node base type",
349 });
350 }
351 };
352 nodes.push(Node {
353 id,
354 offset,
355 payload: fields.bytes,
356 reference,
357 });
358 }
359 Ok(())
360 }
361}
362
363/// Where a store's next transaction appends, as its committed transactions leave it.
364#[derive(Clone, Debug)]
365pub(crate) struct StoreState {
366 pub stamp: crate::Stamp,
367 pub file_type: FileType,
368 /// The last transaction-log fragment and the entry bytes it holds.
369 pub log: (Chunk, usize),
370 /// The log's checksum through its last entry.
371 pub log_crc: u32,
372 /// The highest file-node list identity the log names.
373 pub max_list: u32,
374 pub root: ListTail,
375 /// The file-data store list, once one exists.
376 pub files: Option<ListTail>,
377 /// Each object space's revision manifest list.
378 pub spaces: BTreeMap<crate::ExGuid, ListTail>,
379}
380
381/// The last fragment of a file-node list, where appending continues.
382#[derive(Clone, Copy, Debug)]
383pub(crate) struct ListTail {
384 pub id: u32,
385 pub fragments: u32,
386 pub last: Chunk,
387 pub nodes: usize,
388 /// The file offset past the list's last node.
389 pub end: u64,
390}
391
392#[derive(Debug)]
393pub(crate) struct TransactionFragment<'a> {
394 pub chunk: Chunk,
395 pub entries: &'a [u8],
396}
397
398#[derive(Debug)]
399pub struct Store<'a> {
400 pub(crate) data: &'a [u8],
401 pub(crate) transaction_fragments: Vec<TransactionFragment<'a>>,
402 pub header: Header,
403 pub lists: BTreeMap<u32, NodeList<'a>>,
404 pub checksum_mismatches: Vec<usize>,
405}
406
407fn claim(occupied: &mut BTreeMap<usize, usize>, range: Range<usize>) -> Result<()> {
408 if occupied
409 .range(..range.end)
410 .next_back()
411 .is_some_and(|(_, end)| *end > range.start)
412 {
413 return Err(Error {
414 offset: range.start,
415 message: "Overlapping structural chunks or a reference cycle",
416 });
417 }
418 occupied.insert(range.start, range.end);
419 Ok(())
420}
421
422pub(crate) fn crc(mut value: u32, bytes: &[u8], file_type: FileType) -> u32 {
423 for byte in bytes {
424 match file_type {
425 FileType::Section => {
426 value ^= u32::from(*byte);
427 for _ in 0..8 {
428 value = (value >> 1) ^ if value & 1 != 0 { 0xedb88320 } else { 0 };
429 }
430 }
431 FileType::TableOfContents => {
432 let mut entry = ((value >> 24) ^ u32::from(*byte)) << 24;
433 for _ in 0..8 {
434 entry = (entry << 1) ^ if entry & 0x80000000 != 0 { 0xaf } else { 0 };
435 }
436 value = (value << 8) ^ (entry & 0xffff);
437 }
438 }
439 }
440 value
441}
442
443pub(crate) fn transaction_crc(value: u32, bytes: &[u8], file_type: FileType, full: bool) -> u32 {
444 // OneNote excludes the entry flushed at a TOC fragment boundary (MS-ONESTORE 2.3.3.2 note 8).
445 let bytes = if full && file_type == FileType::TableOfContents {
446 &bytes[..bytes.len().saturating_sub(8)]
447 } else {
448 bytes
449 };
450 crc(value, bytes, file_type)
451}
452
453impl<'a> Store<'a> {
454 /// Parses committed storage while retaining checksum mismatches for diagnostic inspection.
455 pub fn parse(data: &'a [u8]) -> Result<Self> {
456 let header = Header::parse(data)?;
457 let mut occupied = BTreeMap::new();
458 let mut counts = BTreeMap::new();
459 let mut checksum_mismatches = Vec::new();
460 let mut chunk = header.transaction_log;
461 let initial_crc = if header.file_type == FileType::Section {
462 u32::MAX
463 } else {
464 0
465 };
466 let mut checksum = initial_crc;
467 let mut committed = 0;
468 let mut transaction_fragments = Vec::new();
469 while committed < header.transaction_count {
470 let current_chunk = chunk;
471 let range = chunk.range(data)?;
472 claim(&mut occupied, range.clone())?;
473 let mut c = Cursor {
474 bytes: &data[range.clone()],
475 offset: range.start,
476 };
477 let end = loop {
478 if committed == header.transaction_count {
479 break c.offset;
480 }
481 if (12..20).contains(&c.bytes.len()) {
482 let end = c.offset;
483 chunk = c.chunk()?;
484 break end;
485 }
486 let offset = c.offset;
487 let entry = c.take(8)?;
488 let id = u32::from_le_bytes(entry[..4].try_into().unwrap());
489 let value = u32::from_le_bytes(entry[4..].try_into().unwrap());
490 if id == 1 {
491 let expected = if header.file_type == FileType::Section {
492 !checksum
493 } else {
494 checksum
495 };
496 if value != expected {
497 checksum_mismatches.push(offset);
498 }
499 committed += 1;
500 } else {
501 if id < 0x10 || counts.get(&id).is_some_and(|previous| *previous > value) {
502 return Err(Error {
503 offset,
504 message: "Incorrect file-node count in transaction log",
505 });
506 }
507 counts.insert(id, value);
508 }
509 checksum = transaction_crc(checksum, entry, header.file_type, c.bytes.len() < 20);
510 };
511 transaction_fragments.push(TransactionFragment {
512 chunk: current_chunk,
513 entries: &data[range.start..end],
514 });
515 }
516 let mut pending = vec![header.root];
517 if !header.hashed_chunks.absent() {
518 pending.push(header.hashed_chunks);
519 }
520 let mut lists = BTreeMap::new();
521 let mut list_ids = BTreeSet::new();
522 while let Some(mut chunk) = pending.pop() {
523 let mut nodes = Vec::new();
524 let mut fragments = Vec::new();
525 let mut list_id = None;
526 let mut required = 0;
527 loop {
528 let range = chunk.range(data)?;
529 claim(&mut occupied, range.clone())?;
530 let fragment = Fragment::parse(&data[range.clone()], range.start)?;
531 if usize::try_from(fragment.sequence).ok() != Some(fragments.len())
532 || list_id.is_some_and(|previous| fragment.id != previous)
533 {
534 return Err(Error {
535 offset: range.start + 8,
536 message: "Incorrect file-node fragment sequence",
537 });
538 }
539 if list_id.is_none() {
540 if !list_ids.insert(fragment.id) {
541 return Err(Error {
542 offset: range.start + 8,
543 message: "Duplicate file-node list identity",
544 });
545 }
546 required = usize::try_from(*counts.get(&fragment.id).ok_or(Error {
547 offset: range.start + 8,
548 message: "File-node list is absent from the transaction log",
549 })?)
550 .map_err(|_| Error {
551 offset: range.start + 8,
552 message: "File-node count exceeds address space",
553 })?;
554 list_id = Some(fragment.id);
555 }
556 let next = fragment.next;
557 fragment.nodes(required, &mut nodes, |reference| {
558 reference.range(data).map(drop)
559 })?;
560 fragments.push(chunk);
561 if nodes.len() == required {
562 break;
563 }
564 chunk = next;
565 }
566 let last_revision_list = nodes.iter().rposition(|node| node.id == 0x10);
567 for (index, node) in nodes.iter().enumerate() {
568 if let Some(Reference::NodeList(reference)) = node.reference
569 && !reference.absent()
570 && (node.id != 0x10 || Some(index) == last_revision_list)
571 {
572 pending.push(reference);
573 }
574 }
575 nodes.shrink_to_fit();
576 lists.insert(list_id.unwrap(), NodeList { fragments, nodes });
577 }
578 Ok(Self {
579 data,
580 transaction_fragments,
581 header,
582 lists,
583 checksum_mismatches,
584 })
585 }
586
587 /// Where the next transaction appends.
588 pub(crate) fn state(&self) -> Result<StoreState> {
589 let file_type = self.header.file_type;
590 let mut log_crc = if file_type == FileType::Section {
591 u32::MAX
592 } else {
593 0
594 };
595 for fragment in &self.transaction_fragments {
596 log_crc = transaction_crc(
597 log_crc,
598 fragment.entries,
599 file_type,
600 fragment.entries.len() + 20 > fragment.chunk.length as usize,
601 );
602 }
603 let last = self.transaction_fragments.last().unwrap();
604 let root = self.list(self.header.root)?;
605 let files = match root.nodes.iter().find(|node| node.id == 0x90) {
606 Some(node) => {
607 let Some(Reference::NodeList(chunk)) = node.reference else {
608 return Err(Error {
609 offset: node.offset,
610 message: "File-data store reference lacks a list",
611 });
612 };
613 Some(self.tail(chunk)?)
614 }
615 None => None,
616 };
617 let mut spaces = BTreeMap::new();
618 for node in root
619 .nodes
620 .iter()
621 .filter(|node| node.id == 8 && !node.freed())
622 {
623 let revisions = node
624 .referenced_list(self)?
625 .iter()
626 .rfind(|node| node.id == 0x10);
627 if let Some(Node {
628 reference: Some(Reference::NodeList(chunk)),
629 ..
630 }) = revisions
631 {
632 spaces.insert(node.fields(self).exguid()?, self.tail(*chunk)?);
633 }
634 }
635 Ok(StoreState {
636 stamp: crate::Stamp::of(self.data)?,
637 file_type,
638 log: (last.chunk, last.entries.len()),
639 log_crc,
640 max_list: self
641 .transaction_fragments
642 .iter()
643 .flat_map(|fragment| fragment.entries.chunks_exact(8))
644 .map(|entry| u32::from_le_bytes(entry[..4].try_into().unwrap()))
645 .max()
646 .unwrap(),
647 root: self.tail(self.header.root)?,
648 files,
649 spaces,
650 })
651 }
652
653 fn tail(&self, chunk: Chunk) -> Result<ListTail> {
654 let list = self.list(chunk)?;
655 let last = *list.fragments.last().unwrap();
656 let start = usize::try_from(last.offset).unwrap();
657 let node = list.nodes.last().ok_or(Error {
658 offset: start,
659 message: "Cannot append to an empty file-node list",
660 })?;
661 let header =
662 u32::from_le_bytes(self.data[node.offset..node.offset + 4].try_into().unwrap());
663 Ok(ListTail {
664 id: u32::from_le_bytes(self.data[start + 8..start + 12].try_into().unwrap()),
665 fragments: u32::try_from(list.fragments.len()).map_err(|_| Error {
666 offset: start,
667 message: "File-node fragment sequences are exhausted",
668 })?,
669 last,
670 nodes: list.nodes.len(),
671 end: (node.offset + usize::try_from((header >> 10) & 0x1fff).unwrap()) as u64,
672 })
673 }
674
675 pub fn chunk_data(&self, chunk: Chunk) -> Result<&'a [u8]> {
676 Ok(&self.data[chunk.range(self.data)?])
677 }
678
679 pub(crate) fn list(&self, chunk: Chunk) -> Result<&NodeList<'a>> {
680 let data = self.chunk_data(chunk)?;
681 let mut c = Cursor {
682 bytes: data,
683 offset: usize::try_from(chunk.offset).unwrap(),
684 };
685 c.take(8)?;
686 let id = u32::from_le_bytes(c.read()?);
687 self.lists
688 .get(&id)
689 .filter(|list| list.fragments.first() == Some(&chunk))
690 .ok_or(Error {
691 offset: c.offset - 4,
692 message: "Reference does not identify a committed file-node list",
693 })
694 }
695}