fibonacci_codec/
encode.rs

1use bit_vec::BitVec;
2use failure::Fail;
3use num::CheckedSub;
4use std::fmt::{Debug, Display, Error, Formatter};
5
6/// Indicates that encoding a number failed.
7#[derive(Debug, PartialEq)]
8pub enum EncodeError<T>
9where
10    T: Debug + Send + Sync + 'static,
11{
12    /// Indicates an attempt to encode the number `0`, which can't be
13    /// represented in fibonacci encoding.
14    ValueTooSmall(T),
15
16    /// A bug in fibonacci_codec in which encoding the contained
17    /// number resulted in an attempt to subtract a larger fibonacci
18    /// number than the number to encode.
19    Underflow(T),
20}
21
22impl<T> Display for EncodeError<T>
23where
24    T: Debug + Send + Sync + 'static,
25{
26    fn fmt(&self, f: &mut Formatter<'_>) -> Result<(), Error> {
27        match *self {
28            EncodeError::ValueTooSmall(ref n) => write!(f, "value {:?} is too small to encode", n),
29            EncodeError::Underflow(ref n) => {
30                write!(f, "underflow occurred, could not encode {:?}", n)
31            }
32        }
33    }
34}
35
36impl<T> Fail for EncodeError<T> where T: Debug + Send + Sync + 'static {}
37
38/// Indicates that encoding an iterator failed at an element.
39#[derive(Debug, PartialEq)]
40pub struct ElementEncodeError<T>
41where
42    T: Debug + Send + Sync + 'static,
43{
44    /// The element where encoding of iterator elements failed.
45    pub index: usize,
46
47    /// The error encountered when encoding an element on the iterator.
48    pub error: EncodeError<T>,
49}
50
51impl<T> Fail for ElementEncodeError<T> where T: Debug + Send + Sync + 'static {}
52
53impl<T> Display for ElementEncodeError<T>
54where
55    T: Debug + Send + Sync + 'static,
56{
57    fn fmt(&self, f: &mut Formatter<'_>) -> Result<(), Error> {
58        write!(
59            f,
60            "could not encode iterator element {:?}: {}",
61            self.index, self.error
62        )
63    }
64}
65
66/// Allows encoding single primitive integers (> 0) using fibonacci
67/// coding.
68pub trait EncodeOne
69where
70    Self: Sized + Debug + Send + Sync,
71{
72    /// Fibonacci-encodes an integer into a bit vector and returns the
73    /// resulting vector.
74    /// # Errors
75    /// Returns an error when attempting to encode 0.
76    fn fib_encode(self) -> Result<BitVec, EncodeError<Self>> {
77        let mut vec = BitVec::default();
78        self.fib_encode_mut(&mut vec)?;
79        Ok(vec)
80    }
81
82    /// Fibonacci-encodes an integer onto the end of an existing bit
83    /// vector. It extends the bit vector by the numer of bits
84    /// required to hold the output.
85    /// # Errors
86    /// Returns an error when attempting to encode 0.
87    fn fib_encode_mut(self, vec: &mut BitVec) -> Result<(), EncodeError<Self>>;
88}
89
90/// Allows encoding enumerations of unsigned integers (> 0) using
91/// fibonacci coding.
92///
93/// This crate implements this trait for anything that is
94/// `IntoIterator` with primitive unsigned integer elements.
95///
96/// ## A note about zero
97/// The number `0` can't be encoded using fibonacci coding. If you
98/// need to encode a zero, you can use `.map(|x| x+1)` before encoding
99/// and invert this when decoding.
100pub trait Encode<T>
101where
102    Self: Sized + Debug + Send + Sync,
103    T: Debug + Send + Sync,
104{
105    /// Fibonacci-encodes an iterator of integers into bits and
106    /// returns the resulting bit vector.
107    fn fib_encode(self) -> Result<BitVec, ElementEncodeError<T>> {
108        let mut vec = BitVec::default();
109        self.fib_encode_mut(&mut vec)?;
110        Ok(vec)
111    }
112
113    /// Fibonacci-encodes an iterator yielding integers onto the end
114    /// of an existing bit vector, until the iterator is exhausted. It
115    /// extends the bit vector by the number of bits required to hold
116    /// the entire output.
117    ///
118    /// # Error handling
119    /// When encountering an encoding error at any element,
120    /// `fib_encode_mut` returns an error indicating at which element
121    /// the error occurred. It leaves the previous, correctly-encoded
122    /// values' bits in the result bit vector.
123    fn fib_encode_mut(self, vec: &mut BitVec) -> Result<(), ElementEncodeError<T>>;
124}
125
126#[inline]
127pub(crate) fn bits_from_table<T>(
128    n: T,
129    table: &'static [T],
130    result: &mut BitVec,
131) -> Result<(), EncodeError<T>>
132where
133    T: CheckedSub + PartialOrd + Debug + Copy + Send + Sync + 'static,
134{
135    let mut current = n;
136    let split_pos = table
137        .iter()
138        .rposition(|elt| *elt <= n)
139        .ok_or(EncodeError::ValueTooSmall::<T>(n))?;
140
141    let mut i = result.len() + split_pos + 1;
142    result.grow(split_pos + 2, false);
143    result.set(i, true);
144    for elt in table.split_at(split_pos + 1).0.iter().rev() {
145        i -= 1;
146        let bit = if elt > &current {
147            false
148        } else {
149            let next = match current.checked_sub(elt) {
150                Some(next) => next,
151                None => {
152                    // We encountered an underflow. This is a bug, and
153                    // I have no idea how it could even occur in real
154                    // life. However, let's clean up and return a
155                    // reasonable error:
156                    result.truncate(split_pos + 2);
157                    return Err(EncodeError::Underflow(n));
158                }
159            };
160            current = next;
161            true
162        };
163        result.set(i, bit);
164    }
165    Ok(())
166}
fibonacci_codec/encode.rs

fibonacci_codec/
encode.rs
