1/*!
2Types and routines that support the wire format of finite automata.
3
4Currently, this module just exports a few error types and some small helpers
5for deserializing [dense DFAs](crate::dfa::dense::DFA) using correct alignment.
6*/
7
8/*
9A collection of helper functions, types and traits for serializing automata.
10
11This crate defines its own bespoke serialization mechanism for some structures
12provided in the public API, namely, DFAs. A bespoke mechanism was developed
13primarily because structures like automata demand a specific binary format.
14Attempting to encode their rich structure in an existing serialization
15format is just not feasible. Moreover, the format for each structure is
16generally designed such that deserialization is cheap. More specifically, that
17deserialization can be done in constant time. (The idea being that you can
18embed it into your binary or mmap it, and then use it immediately.)
19
20In order to achieve this, the dense and sparse DFAs in this crate use an
21in-memory representation that very closely corresponds to its binary serialized
22form. This pervades and complicates everything, and in some cases, requires
23dealing with alignment and reasoning about safety.
24
25This technique does have major advantages. In particular, it permits doing
26the potentially costly work of compiling a finite state machine in an offline
27manner, and then loading it at runtime not only without having to re-compile
28the regex, but even without the code required to do the compilation. This, for
29example, permits one to use a pre-compiled DFA not only in environments without
30Rust's standard library, but also in environments without a heap.
31
32In the code below, whenever we insert some kind of padding, it's to enforce a
334-byte alignment, unless otherwise noted. Namely, u32 is the only state ID type
34supported. (In a previous version of this library, DFAs were generic over the
35state ID representation.)
36
37Also, serialization generally requires the caller to specify endianness,
38where as deserialization always assumes native endianness (otherwise cheap
39deserialization would be impossible). This implies that serializing a structure
40generally requires serializing both its big-endian and little-endian variants,
41and then loading the correct one based on the target's endianness.
42*/
43
44use core::{cmp, mem::size_of};
45
46#[cfg(feature = "alloc")]
47use alloc::{vec, vec::Vec};
48
49use crate::util::{
50 int::Pointer,
51 primitives::{PatternID, PatternIDError, StateID, StateIDError},
52};
53
54/// A hack to align a smaller type `B` with a bigger type `T`.
55///
56/// The usual use of this is with `B = [u8]` and `T = u32`. That is,
57/// it permits aligning a sequence of bytes on a 4-byte boundary. This
58/// is useful in contexts where one wants to embed a serialized [dense
59/// DFA](crate::dfa::dense::DFA) into a Rust a program while guaranteeing the
60/// alignment required for the DFA.
61///
62/// See [`dense::DFA::from_bytes`](crate::dfa::dense::DFA::from_bytes) for an
63/// example of how to use this type.
64#[repr(C)]
65#[derive(Debug)]
66pub struct AlignAs<B: ?Sized, T> {
67 /// A zero-sized field indicating the alignment we want.
68 pub _align: [T; 0],
69 /// A possibly non-sized field containing a sequence of bytes.
70 pub bytes: B,
71}
72
73/// An error that occurs when serializing an object from this crate.
74///
75/// Serialization, as used in this crate, universally refers to the process
76/// of transforming a structure (like a DFA) into a custom binary format
77/// represented by `&[u8]`. To this end, serialization is generally infallible.
78/// However, it can fail when caller provided buffer sizes are too small. When
79/// that occurs, a serialization error is reported.
80///
81/// A `SerializeError` provides no introspection capabilities. Its only
82/// supported operation is conversion to a human readable error message.
83///
84/// This error type implements the `std::error::Error` trait only when the
85/// `std` feature is enabled. Otherwise, this type is defined in all
86/// configurations.
87#[derive(Debug)]
88pub struct SerializeError {
89 /// The name of the thing that a buffer is too small for.
90 ///
91 /// Currently, the only kind of serialization error is one that is
92 /// committed by a caller: providing a destination buffer that is too
93 /// small to fit the serialized object. This makes sense conceptually,
94 /// since every valid inhabitant of a type should be serializable.
95 ///
96 /// This is somewhat exposed in the public API of this crate. For example,
97 /// the `to_bytes_{big,little}_endian` APIs return a `Vec<u8>` and are
98 /// guaranteed to never panic or error. This is only possible because the
99 /// implementation guarantees that it will allocate a `Vec<u8>` that is
100 /// big enough.
101 ///
102 /// In summary, if a new serialization error kind needs to be added, then
103 /// it will need careful consideration.
104 what: &'static str,
105}
106
107impl SerializeError {
108 pub(crate) fn buffer_too_small(what: &'static str) -> SerializeError {
109 SerializeError { what }
110 }
111}
112
113impl core::fmt::Display for SerializeError {
114 fn fmt(&self, f: &mut core::fmt::Formatter) -> core::fmt::Result {
115 write!(f, "destination buffer is too small to write {}", self.what)
116 }
117}
118
119#[cfg(feature = "std")]
120impl std::error::Error for SerializeError {}
121
122/// An error that occurs when deserializing an object defined in this crate.
123///
124/// Serialization, as used in this crate, universally refers to the process
125/// of transforming a structure (like a DFA) into a custom binary format
126/// represented by `&[u8]`. Deserialization, then, refers to the process of
127/// cheaply converting this binary format back to the object's in-memory
128/// representation as defined in this crate. To the extent possible,
129/// deserialization will report this error whenever this process fails.
130///
131/// A `DeserializeError` provides no introspection capabilities. Its only
132/// supported operation is conversion to a human readable error message.
133///
134/// This error type implements the `std::error::Error` trait only when the
135/// `std` feature is enabled. Otherwise, this type is defined in all
136/// configurations.
137#[derive(Debug)]
138pub struct DeserializeError(DeserializeErrorKind);
139
140#[derive(Debug)]
141enum DeserializeErrorKind {
142 Generic { msg: &'static str },
143 BufferTooSmall { what: &'static str },
144 InvalidUsize { what: &'static str },
145 VersionMismatch { expected: u32, found: u32 },
146 EndianMismatch { expected: u32, found: u32 },
147 AlignmentMismatch { alignment: usize, address: usize },
148 LabelMismatch { expected: &'static str },
149 ArithmeticOverflow { what: &'static str },
150 PatternID { err: PatternIDError, what: &'static str },
151 StateID { err: StateIDError, what: &'static str },
152}
153
154impl DeserializeError {
155 pub(crate) fn generic(msg: &'static str) -> DeserializeError {
156 DeserializeError(DeserializeErrorKind::Generic { msg })
157 }
158
159 pub(crate) fn buffer_too_small(what: &'static str) -> DeserializeError {
160 DeserializeError(DeserializeErrorKind::BufferTooSmall { what })
161 }
162
163 fn invalid_usize(what: &'static str) -> DeserializeError {
164 DeserializeError(DeserializeErrorKind::InvalidUsize { what })
165 }
166
167 fn version_mismatch(expected: u32, found: u32) -> DeserializeError {
168 DeserializeError(DeserializeErrorKind::VersionMismatch {
169 expected,
170 found,
171 })
172 }
173
174 fn endian_mismatch(expected: u32, found: u32) -> DeserializeError {
175 DeserializeError(DeserializeErrorKind::EndianMismatch {
176 expected,
177 found,
178 })
179 }
180
181 fn alignment_mismatch(
182 alignment: usize,
183 address: usize,
184 ) -> DeserializeError {
185 DeserializeError(DeserializeErrorKind::AlignmentMismatch {
186 alignment,
187 address,
188 })
189 }
190
191 fn label_mismatch(expected: &'static str) -> DeserializeError {
192 DeserializeError(DeserializeErrorKind::LabelMismatch { expected })
193 }
194
195 fn arithmetic_overflow(what: &'static str) -> DeserializeError {
196 DeserializeError(DeserializeErrorKind::ArithmeticOverflow { what })
197 }
198
199 fn pattern_id_error(
200 err: PatternIDError,
201 what: &'static str,
202 ) -> DeserializeError {
203 DeserializeError(DeserializeErrorKind::PatternID { err, what })
204 }
205
206 pub(crate) fn state_id_error(
207 err: StateIDError,
208 what: &'static str,
209 ) -> DeserializeError {
210 DeserializeError(DeserializeErrorKind::StateID { err, what })
211 }
212}
213
214#[cfg(feature = "std")]
215impl std::error::Error for DeserializeError {}
216
217impl core::fmt::Display for DeserializeError {
218 fn fmt(&self, f: &mut core::fmt::Formatter) -> core::fmt::Result {
219 use self::DeserializeErrorKind::*;
220
221 match self.0 {
222 Generic { msg } => write!(f, "{}", msg),
223 BufferTooSmall { what } => {
224 write!(f, "buffer is too small to read {}", what)
225 }
226 InvalidUsize { what } => {
227 write!(f, "{} is too big to fit in a usize", what)
228 }
229 VersionMismatch { expected, found } => write!(
230 f,
231 "unsupported version: \
232 expected version {} but found version {}",
233 expected, found,
234 ),
235 EndianMismatch { expected, found } => write!(
236 f,
237 "endianness mismatch: expected 0x{:X} but got 0x{:X}. \
238 (Are you trying to load an object serialized with a \
239 different endianness?)",
240 expected, found,
241 ),
242 AlignmentMismatch { alignment, address } => write!(
243 f,
244 "alignment mismatch: slice starts at address \
245 0x{:X}, which is not aligned to a {} byte boundary",
246 address, alignment,
247 ),
248 LabelMismatch { expected } => write!(
249 f,
250 "label mismatch: start of serialized object should \
251 contain a NUL terminated {:?} label, but a different \
252 label was found",
253 expected,
254 ),
255 ArithmeticOverflow { what } => {
256 write!(f, "arithmetic overflow for {}", what)
257 }
258 PatternID { ref err, what } => {
259 write!(f, "failed to read pattern ID for {}: {}", what, err)
260 }
261 StateID { ref err, what } => {
262 write!(f, "failed to read state ID for {}: {}", what, err)
263 }
264 }
265 }
266}
267
268/// Safely converts a `&[u32]` to `&[StateID]` with zero cost.
269#[cfg_attr(feature = "perf-inline", inline(always))]
270pub(crate) fn u32s_to_state_ids(slice: &[u32]) -> &[StateID] {
271 // SAFETY: This is safe because StateID is defined to have the same memory
272 // representation as a u32 (it is repr(transparent)). While not every u32
273 // is a "valid" StateID, callers are not permitted to rely on the validity
274 // of StateIDs for memory safety. It can only lead to logical errors. (This
275 // is why StateID::new_unchecked is safe.)
276 unsafe {
277 core::slice::from_raw_parts(
278 data:slice.as_ptr().cast::<StateID>(),
279 slice.len(),
280 )
281 }
282}
283
284/// Safely converts a `&mut [u32]` to `&mut [StateID]` with zero cost.
285pub(crate) fn u32s_to_state_ids_mut(slice: &mut [u32]) -> &mut [StateID] {
286 // SAFETY: This is safe because StateID is defined to have the same memory
287 // representation as a u32 (it is repr(transparent)). While not every u32
288 // is a "valid" StateID, callers are not permitted to rely on the validity
289 // of StateIDs for memory safety. It can only lead to logical errors. (This
290 // is why StateID::new_unchecked is safe.)
291 unsafe {
292 core::slice::from_raw_parts_mut(
293 data:slice.as_mut_ptr().cast::<StateID>(),
294 slice.len(),
295 )
296 }
297}
298
299/// Safely converts a `&[u32]` to `&[PatternID]` with zero cost.
300#[cfg_attr(feature = "perf-inline", inline(always))]
301pub(crate) fn u32s_to_pattern_ids(slice: &[u32]) -> &[PatternID] {
302 // SAFETY: This is safe because PatternID is defined to have the same
303 // memory representation as a u32 (it is repr(transparent)). While not
304 // every u32 is a "valid" PatternID, callers are not permitted to rely
305 // on the validity of PatternIDs for memory safety. It can only lead to
306 // logical errors. (This is why PatternID::new_unchecked is safe.)
307 unsafe {
308 core::slice::from_raw_parts(
309 data:slice.as_ptr().cast::<PatternID>(),
310 slice.len(),
311 )
312 }
313}
314
315/// Checks that the given slice has an alignment that matches `T`.
316///
317/// This is useful for checking that a slice has an appropriate alignment
318/// before casting it to a &[T]. Note though that alignment is not itself
319/// sufficient to perform the cast for any `T`.
320pub(crate) fn check_alignment<T>(
321 slice: &[u8],
322) -> Result<(), DeserializeError> {
323 let alignment: usize = core::mem::align_of::<T>();
324 let address: usize = slice.as_ptr().as_usize();
325 if address % alignment == 0 {
326 return Ok(());
327 }
328 Err(DeserializeError::alignment_mismatch(alignment, address))
329}
330
331/// Reads a possibly empty amount of padding, up to 7 bytes, from the beginning
332/// of the given slice. All padding bytes must be NUL bytes.
333///
334/// This is useful because it can be theoretically necessary to pad the
335/// beginning of a serialized object with NUL bytes to ensure that it starts
336/// at a correctly aligned address. These padding bytes should come immediately
337/// before the label.
338///
339/// This returns the number of bytes read from the given slice.
340pub(crate) fn skip_initial_padding(slice: &[u8]) -> usize {
341 let mut nread: usize = 0;
342 while nread < 7 && nread < slice.len() && slice[nread] == 0 {
343 nread += 1;
344 }
345 nread
346}
347
348/// Allocate a byte buffer of the given size, along with some initial padding
349/// such that `buf[padding..]` has the same alignment as `T`, where the
350/// alignment of `T` must be at most `8`. In particular, callers should treat
351/// the first N bytes (second return value) as padding bytes that must not be
352/// overwritten. In all cases, the following identity holds:
353///
354/// ```ignore
355/// let (buf, padding) = alloc_aligned_buffer::<StateID>(SIZE);
356/// assert_eq!(SIZE, buf[padding..].len());
357/// ```
358///
359/// In practice, padding is often zero.
360///
361/// The requirement for `8` as a maximum here is somewhat arbitrary. In
362/// practice, we never need anything bigger in this crate, and so this function
363/// does some sanity asserts under the assumption of a max alignment of `8`.
364#[cfg(feature = "alloc")]
365pub(crate) fn alloc_aligned_buffer<T>(size: usize) -> (Vec<u8>, usize) {
366 // NOTE: This is a kludge because there's no easy way to allocate a Vec<u8>
367 // with an alignment guaranteed to be greater than 1. We could create a
368 // Vec<u32>, but this cannot be safely transmuted to a Vec<u8> without
369 // concern, since reallocing or dropping the Vec<u8> is UB (different
370 // alignment than the initial allocation). We could define a wrapper type
371 // to manage this for us, but it seems like more machinery than it's worth.
372 let buf = vec![0; size];
373 let align = core::mem::align_of::<T>();
374 let address = buf.as_ptr().as_usize();
375 if address % align == 0 {
376 return (buf, 0);
377 }
378 // Let's try this again. We have to create a totally new alloc with
379 // the maximum amount of bytes we might need. We can't just extend our
380 // pre-existing 'buf' because that might create a new alloc with a
381 // different alignment.
382 let extra = align - 1;
383 let mut buf = vec![0; size + extra];
384 let address = buf.as_ptr().as_usize();
385 // The code below handles the case where 'address' is aligned to T, so if
386 // we got lucky and 'address' is now aligned to T (when it previously
387 // wasn't), then we're done.
388 if address % align == 0 {
389 buf.truncate(size);
390 return (buf, 0);
391 }
392 let padding = ((address & !(align - 1)).checked_add(align).unwrap())
393 .checked_sub(address)
394 .unwrap();
395 assert!(padding <= 7, "padding of {} is bigger than 7", padding);
396 assert!(
397 padding <= extra,
398 "padding of {} is bigger than extra {} bytes",
399 padding,
400 extra
401 );
402 buf.truncate(size + padding);
403 assert_eq!(size + padding, buf.len());
404 assert_eq!(
405 0,
406 buf[padding..].as_ptr().as_usize() % align,
407 "expected end of initial padding to be aligned to {}",
408 align,
409 );
410 (buf, padding)
411}
412
413/// Reads a NUL terminated label starting at the beginning of the given slice.
414///
415/// If a NUL terminated label could not be found, then an error is returned.
416/// Similarly, if a label is found but doesn't match the expected label, then
417/// an error is returned.
418///
419/// Upon success, the total number of bytes read (including padding bytes) is
420/// returned.
421pub(crate) fn read_label(
422 slice: &[u8],
423 expected_label: &'static str,
424) -> Result<usize, DeserializeError> {
425 // Set an upper bound on how many bytes we scan for a NUL. Since no label
426 // in this crate is longer than 256 bytes, if we can't find one within that
427 // range, then we have corrupted data.
428 let first_nul =
429 slice[..cmp::min(slice.len(), 256)].iter().position(|&b| b == 0);
430 let first_nul = match first_nul {
431 Some(first_nul) => first_nul,
432 None => {
433 return Err(DeserializeError::generic(
434 "could not find NUL terminated label \
435 at start of serialized object",
436 ));
437 }
438 };
439 let len = first_nul + padding_len(first_nul);
440 if slice.len() < len {
441 return Err(DeserializeError::generic(
442 "could not find properly sized label at start of serialized object"
443 ));
444 }
445 if expected_label.as_bytes() != &slice[..first_nul] {
446 return Err(DeserializeError::label_mismatch(expected_label));
447 }
448 Ok(len)
449}
450
451/// Writes the given label to the buffer as a NUL terminated string. The label
452/// given must not contain NUL, otherwise this will panic. Similarly, the label
453/// must not be longer than 255 bytes, otherwise this will panic.
454///
455/// Additional NUL bytes are written as necessary to ensure that the number of
456/// bytes written is always a multiple of 4.
457///
458/// Upon success, the total number of bytes written (including padding) is
459/// returned.
460pub(crate) fn write_label(
461 label: &str,
462 dst: &mut [u8],
463) -> Result<usize, SerializeError> {
464 let nwrite: usize = write_label_len(label);
465 if dst.len() < nwrite {
466 return Err(SerializeError::buffer_too_small(what:"label"));
467 }
468 dst[..label.len()].copy_from_slice(src:label.as_bytes());
469 for i: usize in 0..(nwrite - label.len()) {
470 dst[label.len() + i] = 0;
471 }
472 assert_eq!(nwrite % 4, 0);
473 Ok(nwrite)
474}
475
476/// Returns the total number of bytes (including padding) that would be written
477/// for the given label. This panics if the given label contains a NUL byte or
478/// is longer than 255 bytes. (The size restriction exists so that searching
479/// for a label during deserialization can be done in small bounded space.)
480pub(crate) fn write_label_len(label: &str) -> usize {
481 if label.len() > 255 {
482 panic!("label must not be longer than 255 bytes");
483 }
484 if label.as_bytes().iter().position(|&b: u8| b == 0).is_some() {
485 panic!("label must not contain NUL bytes");
486 }
487 let label_len: usize = label.len() + 1; // +1 for the NUL terminator
488 label_len + padding_len(non_padding_len:label_len)
489}
490
491/// Reads the endianness check from the beginning of the given slice and
492/// confirms that the endianness of the serialized object matches the expected
493/// endianness. If the slice is too small or if the endianness check fails,
494/// this returns an error.
495///
496/// Upon success, the total number of bytes read is returned.
497pub(crate) fn read_endianness_check(
498 slice: &[u8],
499) -> Result<usize, DeserializeError> {
500 let (n: u32, nr: usize) = try_read_u32(slice, what:"endianness check")?;
501 assert_eq!(nr, write_endianness_check_len());
502 if n != 0xFEFF {
503 return Err(DeserializeError::endian_mismatch(expected:0xFEFF, found:n));
504 }
505 Ok(nr)
506}
507
508/// Writes 0xFEFF as an integer using the given endianness.
509///
510/// This is useful for writing into the header of a serialized object. It can
511/// be read during deserialization as a sanity check to ensure the proper
512/// endianness is used.
513///
514/// Upon success, the total number of bytes written is returned.
515pub(crate) fn write_endianness_check<E: Endian>(
516 dst: &mut [u8],
517) -> Result<usize, SerializeError> {
518 let nwrite: usize = write_endianness_check_len();
519 if dst.len() < nwrite {
520 return Err(SerializeError::buffer_too_small(what:"endianness check"));
521 }
522 E::write_u32(n:0xFEFF, dst);
523 Ok(nwrite)
524}
525
526/// Returns the number of bytes written by the endianness check.
527pub(crate) fn write_endianness_check_len() -> usize {
528 size_of::<u32>()
529}
530
531/// Reads a version number from the beginning of the given slice and confirms
532/// that is matches the expected version number given. If the slice is too
533/// small or if the version numbers aren't equivalent, this returns an error.
534///
535/// Upon success, the total number of bytes read is returned.
536///
537/// N.B. Currently, we require that the version number is exactly equivalent.
538/// In the future, if we bump the version number without a semver bump, then
539/// we'll need to relax this a bit and support older versions.
540pub(crate) fn read_version(
541 slice: &[u8],
542 expected_version: u32,
543) -> Result<usize, DeserializeError> {
544 let (n: u32, nr: usize) = try_read_u32(slice, what:"version")?;
545 assert_eq!(nr, write_version_len());
546 if n != expected_version {
547 return Err(DeserializeError::version_mismatch(expected_version, found:n));
548 }
549 Ok(nr)
550}
551
552/// Writes the given version number to the beginning of the given slice.
553///
554/// This is useful for writing into the header of a serialized object. It can
555/// be read during deserialization as a sanity check to ensure that the library
556/// code supports the format of the serialized object.
557///
558/// Upon success, the total number of bytes written is returned.
559pub(crate) fn write_version<E: Endian>(
560 version: u32,
561 dst: &mut [u8],
562) -> Result<usize, SerializeError> {
563 let nwrite: usize = write_version_len();
564 if dst.len() < nwrite {
565 return Err(SerializeError::buffer_too_small(what:"version number"));
566 }
567 E::write_u32(n:version, dst);
568 Ok(nwrite)
569}
570
571/// Returns the number of bytes written by writing the version number.
572pub(crate) fn write_version_len() -> usize {
573 size_of::<u32>()
574}
575
576/// Reads a pattern ID from the given slice. If the slice has insufficient
577/// length, then this panics. If the deserialized integer exceeds the pattern
578/// ID limit for the current target, then this returns an error.
579///
580/// Upon success, this also returns the number of bytes read.
581pub(crate) fn read_pattern_id(
582 slice: &[u8],
583 what: &'static str,
584) -> Result<(PatternID, usize), DeserializeError> {
585 let bytes: [u8; PatternID::SIZE] =
586 slice[..PatternID::SIZE].try_into().unwrap();
587 let pid: PatternID = PatternID::from_ne_bytes(bytes)
588 .map_err(|err: PatternIDError| DeserializeError::pattern_id_error(err, what))?;
589 Ok((pid, PatternID::SIZE))
590}
591
592/// Reads a pattern ID from the given slice. If the slice has insufficient
593/// length, then this panics. Otherwise, the deserialized integer is assumed
594/// to be a valid pattern ID.
595///
596/// This also returns the number of bytes read.
597pub(crate) fn read_pattern_id_unchecked(slice: &[u8]) -> (PatternID, usize) {
598 let pid: PatternID = PatternID::from_ne_bytes_unchecked(
599 bytes:slice[..PatternID::SIZE].try_into().unwrap(),
600 );
601 (pid, PatternID::SIZE)
602}
603
604/// Write the given pattern ID to the beginning of the given slice of bytes
605/// using the specified endianness. The given slice must have length at least
606/// `PatternID::SIZE`, or else this panics. Upon success, the total number of
607/// bytes written is returned.
608pub(crate) fn write_pattern_id<E: Endian>(
609 pid: PatternID,
610 dst: &mut [u8],
611) -> usize {
612 E::write_u32(n:pid.as_u32(), dst);
613 PatternID::SIZE
614}
615
616/// Attempts to read a state ID from the given slice. If the slice has an
617/// insufficient number of bytes or if the state ID exceeds the limit for
618/// the current target, then this returns an error.
619///
620/// Upon success, this also returns the number of bytes read.
621pub(crate) fn try_read_state_id(
622 slice: &[u8],
623 what: &'static str,
624) -> Result<(StateID, usize), DeserializeError> {
625 if slice.len() < StateID::SIZE {
626 return Err(DeserializeError::buffer_too_small(what));
627 }
628 read_state_id(slice, what)
629}
630
631/// Reads a state ID from the given slice. If the slice has insufficient
632/// length, then this panics. If the deserialized integer exceeds the state ID
633/// limit for the current target, then this returns an error.
634///
635/// Upon success, this also returns the number of bytes read.
636pub(crate) fn read_state_id(
637 slice: &[u8],
638 what: &'static str,
639) -> Result<(StateID, usize), DeserializeError> {
640 let bytes: [u8; StateID::SIZE] =
641 slice[..StateID::SIZE].try_into().unwrap();
642 let sid: StateID = StateID::from_ne_bytes(bytes)
643 .map_err(|err: StateIDError| DeserializeError::state_id_error(err, what))?;
644 Ok((sid, StateID::SIZE))
645}
646
647/// Reads a state ID from the given slice. If the slice has insufficient
648/// length, then this panics. Otherwise, the deserialized integer is assumed
649/// to be a valid state ID.
650///
651/// This also returns the number of bytes read.
652pub(crate) fn read_state_id_unchecked(slice: &[u8]) -> (StateID, usize) {
653 let sid: StateID = StateID::from_ne_bytes_unchecked(
654 bytes:slice[..StateID::SIZE].try_into().unwrap(),
655 );
656 (sid, StateID::SIZE)
657}
658
659/// Write the given state ID to the beginning of the given slice of bytes
660/// using the specified endianness. The given slice must have length at least
661/// `StateID::SIZE`, or else this panics. Upon success, the total number of
662/// bytes written is returned.
663pub(crate) fn write_state_id<E: Endian>(
664 sid: StateID,
665 dst: &mut [u8],
666) -> usize {
667 E::write_u32(n:sid.as_u32(), dst);
668 StateID::SIZE
669}
670
671/// Try to read a u16 as a usize from the beginning of the given slice in
672/// native endian format. If the slice has fewer than 2 bytes or if the
673/// deserialized number cannot be represented by usize, then this returns an
674/// error. The error message will include the `what` description of what is
675/// being deserialized, for better error messages. `what` should be a noun in
676/// singular form.
677///
678/// Upon success, this also returns the number of bytes read.
679pub(crate) fn try_read_u16_as_usize(
680 slice: &[u8],
681 what: &'static str,
682) -> Result<(usize, usize), DeserializeError> {
683 try_read_u16(slice, what).and_then(|(n: u16, nr: usize)| {
684 usize::try_from(n)
685 .map(|n| (n, nr))
686 .map_err(|_| DeserializeError::invalid_usize(what))
687 })
688}
689
690/// Try to read a u32 as a usize from the beginning of the given slice in
691/// native endian format. If the slice has fewer than 4 bytes or if the
692/// deserialized number cannot be represented by usize, then this returns an
693/// error. The error message will include the `what` description of what is
694/// being deserialized, for better error messages. `what` should be a noun in
695/// singular form.
696///
697/// Upon success, this also returns the number of bytes read.
698pub(crate) fn try_read_u32_as_usize(
699 slice: &[u8],
700 what: &'static str,
701) -> Result<(usize, usize), DeserializeError> {
702 try_read_u32(slice, what).and_then(|(n: u32, nr: usize)| {
703 usize::try_from(n)
704 .map(|n| (n, nr))
705 .map_err(|_| DeserializeError::invalid_usize(what))
706 })
707}
708
709/// Try to read a u16 from the beginning of the given slice in native endian
710/// format. If the slice has fewer than 2 bytes, then this returns an error.
711/// The error message will include the `what` description of what is being
712/// deserialized, for better error messages. `what` should be a noun in
713/// singular form.
714///
715/// Upon success, this also returns the number of bytes read.
716pub(crate) fn try_read_u16(
717 slice: &[u8],
718 what: &'static str,
719) -> Result<(u16, usize), DeserializeError> {
720 check_slice_len(slice, at_least_len:size_of::<u16>(), what)?;
721 Ok((read_u16(slice), size_of::<u16>()))
722}
723
724/// Try to read a u32 from the beginning of the given slice in native endian
725/// format. If the slice has fewer than 4 bytes, then this returns an error.
726/// The error message will include the `what` description of what is being
727/// deserialized, for better error messages. `what` should be a noun in
728/// singular form.
729///
730/// Upon success, this also returns the number of bytes read.
731pub(crate) fn try_read_u32(
732 slice: &[u8],
733 what: &'static str,
734) -> Result<(u32, usize), DeserializeError> {
735 check_slice_len(slice, at_least_len:size_of::<u32>(), what)?;
736 Ok((read_u32(slice), size_of::<u32>()))
737}
738
739/// Try to read a u128 from the beginning of the given slice in native endian
740/// format. If the slice has fewer than 16 bytes, then this returns an error.
741/// The error message will include the `what` description of what is being
742/// deserialized, for better error messages. `what` should be a noun in
743/// singular form.
744///
745/// Upon success, this also returns the number of bytes read.
746pub(crate) fn try_read_u128(
747 slice: &[u8],
748 what: &'static str,
749) -> Result<(u128, usize), DeserializeError> {
750 check_slice_len(slice, at_least_len:size_of::<u128>(), what)?;
751 Ok((read_u128(slice), size_of::<u128>()))
752}
753
754/// Read a u16 from the beginning of the given slice in native endian format.
755/// If the slice has fewer than 2 bytes, then this panics.
756///
757/// Marked as inline to speed up sparse searching which decodes integers from
758/// its automaton at search time.
759#[cfg_attr(feature = "perf-inline", inline(always))]
760pub(crate) fn read_u16(slice: &[u8]) -> u16 {
761 let bytes: [u8; 2] = slice[..size_of::<u16>()].try_into().unwrap();
762 u16::from_ne_bytes(bytes)
763}
764
765/// Read a u32 from the beginning of the given slice in native endian format.
766/// If the slice has fewer than 4 bytes, then this panics.
767///
768/// Marked as inline to speed up sparse searching which decodes integers from
769/// its automaton at search time.
770#[cfg_attr(feature = "perf-inline", inline(always))]
771pub(crate) fn read_u32(slice: &[u8]) -> u32 {
772 let bytes: [u8; 4] = slice[..size_of::<u32>()].try_into().unwrap();
773 u32::from_ne_bytes(bytes)
774}
775
776/// Read a u128 from the beginning of the given slice in native endian format.
777/// If the slice has fewer than 16 bytes, then this panics.
778pub(crate) fn read_u128(slice: &[u8]) -> u128 {
779 let bytes: [u8; 16] = slice[..size_of::<u128>()].try_into().unwrap();
780 u128::from_ne_bytes(bytes)
781}
782
783/// Checks that the given slice has some minimal length. If it's smaller than
784/// the bound given, then a "buffer too small" error is returned with `what`
785/// describing what the buffer represents.
786pub(crate) fn check_slice_len<T>(
787 slice: &[T],
788 at_least_len: usize,
789 what: &'static str,
790) -> Result<(), DeserializeError> {
791 if slice.len() < at_least_len {
792 return Err(DeserializeError::buffer_too_small(what));
793 }
794 Ok(())
795}
796
797/// Multiply the given numbers, and on overflow, return an error that includes
798/// 'what' in the error message.
799///
800/// This is useful when doing arithmetic with untrusted data.
801pub(crate) fn mul(
802 a: usize,
803 b: usize,
804 what: &'static str,
805) -> Result<usize, DeserializeError> {
806 match a.checked_mul(b) {
807 Some(c: usize) => Ok(c),
808 None => Err(DeserializeError::arithmetic_overflow(what)),
809 }
810}
811
812/// Add the given numbers, and on overflow, return an error that includes
813/// 'what' in the error message.
814///
815/// This is useful when doing arithmetic with untrusted data.
816pub(crate) fn add(
817 a: usize,
818 b: usize,
819 what: &'static str,
820) -> Result<usize, DeserializeError> {
821 match a.checked_add(b) {
822 Some(c: usize) => Ok(c),
823 None => Err(DeserializeError::arithmetic_overflow(what)),
824 }
825}
826
827/// Shift `a` left by `b`, and on overflow, return an error that includes
828/// 'what' in the error message.
829///
830/// This is useful when doing arithmetic with untrusted data.
831pub(crate) fn shl(
832 a: usize,
833 b: usize,
834 what: &'static str,
835) -> Result<usize, DeserializeError> {
836 let amount: u32 = u32::try_from(b)
837 .map_err(|_| DeserializeError::arithmetic_overflow(what))?;
838 match a.checked_shl(amount) {
839 Some(c: usize) => Ok(c),
840 None => Err(DeserializeError::arithmetic_overflow(what)),
841 }
842}
843
844/// Returns the number of additional bytes required to add to the given length
845/// in order to make the total length a multiple of 4. The return value is
846/// always less than 4.
847pub(crate) fn padding_len(non_padding_len: usize) -> usize {
848 (4 - (non_padding_len & 0b11)) & 0b11
849}
850
851/// A simple trait for writing code generic over endianness.
852///
853/// This is similar to what byteorder provides, but we only need a very small
854/// subset.
855pub(crate) trait Endian {
856 /// Writes a u16 to the given destination buffer in a particular
857 /// endianness. If the destination buffer has a length smaller than 2, then
858 /// this panics.
859 fn write_u16(n: u16, dst: &mut [u8]);
860
861 /// Writes a u32 to the given destination buffer in a particular
862 /// endianness. If the destination buffer has a length smaller than 4, then
863 /// this panics.
864 fn write_u32(n: u32, dst: &mut [u8]);
865
866 /// Writes a u128 to the given destination buffer in a particular
867 /// endianness. If the destination buffer has a length smaller than 16,
868 /// then this panics.
869 fn write_u128(n: u128, dst: &mut [u8]);
870}
871
872/// Little endian writing.
873pub(crate) enum LE {}
874/// Big endian writing.
875pub(crate) enum BE {}
876
877#[cfg(target_endian = "little")]
878pub(crate) type NE = LE;
879#[cfg(target_endian = "big")]
880pub(crate) type NE = BE;
881
882impl Endian for LE {
883 fn write_u16(n: u16, dst: &mut [u8]) {
884 dst[..2].copy_from_slice(&n.to_le_bytes());
885 }
886
887 fn write_u32(n: u32, dst: &mut [u8]) {
888 dst[..4].copy_from_slice(&n.to_le_bytes());
889 }
890
891 fn write_u128(n: u128, dst: &mut [u8]) {
892 dst[..16].copy_from_slice(&n.to_le_bytes());
893 }
894}
895
896impl Endian for BE {
897 fn write_u16(n: u16, dst: &mut [u8]) {
898 dst[..2].copy_from_slice(&n.to_be_bytes());
899 }
900
901 fn write_u32(n: u32, dst: &mut [u8]) {
902 dst[..4].copy_from_slice(&n.to_be_bytes());
903 }
904
905 fn write_u128(n: u128, dst: &mut [u8]) {
906 dst[..16].copy_from_slice(&n.to_be_bytes());
907 }
908}
909
910#[cfg(all(test, feature = "alloc"))]
911mod tests {
912 use super::*;
913
914 #[test]
915 fn labels() {
916 let mut buf = [0; 1024];
917
918 let nwrite = write_label("fooba", &mut buf).unwrap();
919 assert_eq!(nwrite, 8);
920 assert_eq!(&buf[..nwrite], b"fooba\x00\x00\x00");
921
922 let nread = read_label(&buf, "fooba").unwrap();
923 assert_eq!(nread, 8);
924 }
925
926 #[test]
927 #[should_panic]
928 fn bad_label_interior_nul() {
929 // interior NULs are not allowed
930 write_label("foo\x00bar", &mut [0; 1024]).unwrap();
931 }
932
933 #[test]
934 fn bad_label_almost_too_long() {
935 // ok
936 write_label(&"z".repeat(255), &mut [0; 1024]).unwrap();
937 }
938
939 #[test]
940 #[should_panic]
941 fn bad_label_too_long() {
942 // labels longer than 255 bytes are banned
943 write_label(&"z".repeat(256), &mut [0; 1024]).unwrap();
944 }
945
946 #[test]
947 fn padding() {
948 assert_eq!(0, padding_len(8));
949 assert_eq!(3, padding_len(9));
950 assert_eq!(2, padding_len(10));
951 assert_eq!(1, padding_len(11));
952 assert_eq!(0, padding_len(12));
953 assert_eq!(3, padding_len(13));
954 assert_eq!(2, padding_len(14));
955 assert_eq!(1, padding_len(15));
956 assert_eq!(0, padding_len(16));
957 }
958}
959