fibonacci_codec/
decode.rs

1use num::{CheckedAdd, One, Zero};
2use std::fmt::Debug;
3
4/// Returned if decoding a number fails. Usually indicates an overflow
5/// of the number being decoded.
6#[derive(Fail, Debug, PartialEq)]
7pub enum DecodeError {
8    /// Indicates that the decoded number depends on a fibonacci
9    /// sequence element that doesn't fit the return type.
10    #[fail(
11        display = "fibonacci sequence element would overflow result type at bit position {:?}",
12        bit_pos
13    )]
14    FibonacciElementOverflow { bit_pos: usize },
15
16    /// Indicates that the decoded number does not fit into the given
17    /// result type. This more than anything indicates that a bit flip
18    /// has occurred, and the next number can't be trusted either.
19    #[fail(
20        display = "constructing number would overflow at bit position {:?}",
21        bit_pos
22    )]
23    ConstructionOverflow { bit_pos: usize },
24}
25
26fn multiplier<T>(bit: bool) -> T
27where
28    T: Zero + One,
29{
30    if bit {
31        T::one()
32    } else {
33        T::zero()
34    }
35}
36
37fn is_terminator(bit: bool, last: bool) -> bool {
38    bit && last
39}
40
41fn consume_overflow<I>(elt: bool, iterator: &mut I)
42where
43    I: Iterator<Item = bool>,
44{
45    let mut last = elt;
46    for elt in iterator {
47        if is_terminator(elt, last) {
48            break;
49        }
50        last = elt;
51    }
52}
53
54// Can't write the loop as `for elt in iterator` because we use the
55// iterator again later:
56#[cfg_attr(feature = "cargo-clippy", allow(clippy::while_let_on_iterator))]
57#[inline]
58pub(crate) fn decode_from<I, T>(
59    iterator: &mut I,
60    table: &'static [T],
61) -> Option<Result<T, DecodeError>>
62where
63    I: Iterator<Item = bool>,
64    T: CheckedAdd + PartialOrd + Debug + Copy + Zero + One,
65{
66    let mut i = 0;
67    let mut accumulator: T = T::zero();
68    let mut last = false;
69    while let Some(elt) = iterator.next() {
70        if is_terminator(elt, last) {
71            return Some(Ok(accumulator));
72        }
73
74        if let Some(fib) = table.get(i) {
75            let digit = multiplier::<T>(elt) * *fib;
76            if let Some(new_acc) = accumulator.checked_add(&digit) {
77                accumulator = new_acc;
78            } else {
79                consume_overflow(elt, iterator);
80                return Some(Err(DecodeError::ConstructionOverflow { bit_pos: i }));
81            }
82        } else {
83            consume_overflow(elt, iterator);
84            return Some(Err(DecodeError::FibonacciElementOverflow { bit_pos: i }));
85        }
86        i += 1;
87        last = elt;
88    }
89    // Done with this stream:
90    None
91}
fibonacci_codec/decode.rs

fibonacci_codec/
decode.rs
