compactly/v2/
mod.rs

1//! The `ans` format of compactly.
2//!
3//! This format should be unmodified after the 1.0 release, except for addition
4//! of support for new strategies, which won't change the binary format of types
5//! that don't use those strategies.
6pub use compactly_derive::EncodeV2 as Encode;
7
8mod ans;
9mod arc;
10mod arith;
11mod array;
12mod bit_context;
13mod bits;
14mod bools;
15mod byte;
16mod bytes;
17mod floats;
18#[cfg(feature = "generate_bit_context")]
19pub mod generate_bit_context;
20mod ints;
21mod low_cardinality;
22mod maps;
23mod millibits;
24mod option;
25mod other_crate_types;
26mod raw;
27mod sets;
28mod string;
29mod tuples;
30mod ulessthan;
31mod usizes;
32mod vecs;
33
34use crate::{LowCardinality, Small};
35pub use ans::Ans;
36pub use arith::Range;
37pub use millibits::Millibits;
38pub use raw::Raw;
39pub use ulessthan::ULessThan;
40
41const FIFTY_PERCENT: ans::Probability = ans::Probability::new(127, 127);
42
43/// A place where we can put bits where we have estimated the probabilities.
44pub trait EntropyCoder: Default {
45    /// Encode a given bit with its probability
46    fn encode_bit(&mut self, probability: ans::Probability, bit: bool);
47
48    /// Encode the `value` into a `Vec<u8>` of bytes.`
49    fn encode<T: Encode>(value: &T) -> Self {
50        let mut writer = Self::default();
51        value.encode(&mut writer, &mut T::Context::default());
52        writer
53    }
54
55    /// Encode a given slice of incompressible bytes.
56    ///
57    /// Note that ideall implementations will do something more efficient than
58    /// just omitting to track probabilities, but the default implementation
59    /// should suffice for correctness.
60    fn encode_incompressible_bytes(&mut self, bytes: &[u8]) {
61        for mut b in bytes.iter().copied() {
62            for _ in 0..8 {
63                self.encode_bit(FIFTY_PERCENT, (b & 1) == 1);
64                b >>= 1;
65            }
66        }
67    }
68}
69
70/// A way .
71pub trait EntropyDecoder {
72    /// Decode a given bit with the given probability
73    fn decode_bit_nonadaptive(
74        &mut self,
75        probability: ans::Probability,
76    ) -> Result<bool, std::io::Error>;
77
78    /// Encode a given bit with its probability
79    #[inline(always)]
80    fn decode_bit(
81        &mut self,
82        context: &mut bit_context::BitContext,
83    ) -> Result<bool, std::io::Error> {
84        let bit = self.decode_bit_nonadaptive(context.probability())?;
85        *context = context.adapt(bit);
86        Ok(bit)
87    }
88
89    /// Decode a fixed number of incompressible bytes into a slice.
90    #[inline(always)]
91    fn decode_incompressible_bytes(&mut self, bytes: &mut [u8]) -> Result<(), std::io::Error> {
92        for v in bytes {
93            let mut b = 0;
94            for i in 0..8 {
95                b = b | ((self.decode_bit_nonadaptive(FIFTY_PERCENT)? as u8) << i);
96            }
97            *v = b;
98        }
99        Ok(())
100    }
101}
102
103/// Trait for types that can be compactly encoded.
104///
105/// Normally you will derive this for your own types, although it can be
106/// implemented manually.
107pub trait Encode: Sized {
108    /// Context storing probability model for this type.
109    type Context: Default + Clone;
110
111    /// Encode this value to the [`Writer<W>`].
112    fn encode<E: EntropyCoder>(&self, encoder: &mut E, ctx: &mut Self::Context);
113
114    /// Decode value from ['Reader<R>`].
115    fn decode<D: EntropyDecoder>(
116        entropy_decoder: &mut D,
117        ctx: &mut Self::Context,
118    ) -> Result<Self, std::io::Error>;
119
120    /// Estimate the size of this value
121    fn millibits(&self) -> Millibits {
122        let mut m = Millibits::default();
123        self.encode(&mut m, &mut Self::Context::default());
124        m
125    }
126}
127
128/// Encode the `value` into a `Vec<u8>` of bytes.`
129pub fn encode<T: Encode>(value: &T) -> Vec<u8> {
130    let mut writer = arith::Range::default();
131    value.encode(&mut writer, &mut T::Context::default());
132    writer.into_vec()
133}
134
135/// Decode a value of this type from `bytes`.
136///
137/// Returns `None` if the bytes do not encode a valid value.
138pub fn decode<T: Encode>(mut bytes: &[u8]) -> Option<T> {
139    let mut reader = arith::Decoder::new(&mut bytes);
140    T::decode(&mut reader, &mut T::Context::default()).ok()
141}
142
143/// An encoding strategy for type `T`.
144///
145/// You *can* implement this for your own types, if you want them to support
146/// e.g. `Small` encodings.  But I expect this to be unusual.  It would be
147/// possible to create a `Derive` macro for this, but I don't think it is
148/// needed.  If you want such a macro file an issue.
149///
150/// Note that besides implementing existing strategies for your own types, you
151/// can also create entirely new strategies in your crates.  If you do that, you
152/// can use full paths in your derive macros, e.g.
153/// `#[compactly(your_crate::SuperCoolEncodingStratgy]`.
154pub trait EncodingStrategy<T> {
155    /// The conext (i.e. probability model) for this encoding strategy applied to this type.
156    type Context: Default + Clone;
157
158    /// Encode the value with this strategy.
159    fn encode<E: EntropyCoder>(value: &T, writer: &mut E, ctx: &mut Self::Context);
160
161    /// Decode the value using this strategy.
162    fn decode<D: EntropyDecoder>(
163        reader: &mut D,
164        ctx: &mut Self::Context,
165    ) -> Result<T, std::io::Error>;
166}
167
168/// Encode a value with a specific strategy (into a `Vec<u8>`).
169///
170/// I don't expect this to be used in practice, but it can be helpful for
171/// testing.
172pub fn encode_with<T: Encode, S: EncodingStrategy<T>>(_: S, value: &T) -> Vec<u8> {
173    let mut writer = Range::default();
174    S::encode(value, &mut writer, &mut S::Context::default());
175    writer.into_vec()
176}
177
178/// Decode a value with a specific strategy (from a bytes slice).
179///
180/// I don't expect this to be used in practice, but it can be helpful for
181/// testing.
182pub fn decode_with<T: Encode, S: EncodingStrategy<T>>(_: S, mut bytes: &[u8]) -> Option<T> {
183    let mut reader = arith::Decoder::new(&mut bytes);
184    S::decode(&mut reader, &mut S::Context::default()).ok()
185}
186
187impl<T, S: EncodingStrategy<T>> Encode for crate::Encoded<T, S> {
188    type Context = S::Context;
189    #[inline]
190    fn encode<E: EntropyCoder>(&self, writer: &mut E, ctx: &mut Self::Context) {
191        S::encode(&self.value, writer, ctx)
192    }
193    #[inline]
194    fn decode<D: EntropyDecoder>(
195        reader: &mut D,
196        ctx: &mut Self::Context,
197    ) -> Result<Self, std::io::Error> {
198        Ok(Self {
199            value: S::decode(reader, ctx)?,
200            _phantom: std::marker::PhantomData,
201        })
202    }
203}
204
205impl<T: Encode> EncodingStrategy<T> for crate::Normal {
206    type Context = <T as Encode>::Context;
207    #[inline]
208    fn encode<E: EntropyCoder>(value: &T, writer: &mut E, ctx: &mut Self::Context) {
209        value.encode(writer, ctx)
210    }
211    fn decode<D: EntropyDecoder>(
212        reader: &mut D,
213        ctx: &mut Self::Context,
214    ) -> Result<T, std::io::Error> {
215        T::decode(reader, ctx)
216    }
217}
218
219#[cfg(test)]
220macro_rules! assert_size {
221    ($v:expr, $size:expr) => {
222        let v = $v;
223        let bytes = super::encode(&v);
224        let decoded = super::decode(&bytes);
225        assert_eq!(decoded, Some(v), "decoded value is incorrect");
226        assert_eq!(bytes.len(), $size, "unexpected size");
227    };
228}
229#[cfg(test)]
230pub(crate) use assert_size;
231
232#[cfg(test)]
233macro_rules! assert_bits {
234    ($v:expr, $size:expr) => {
235        let ans = $v;
236        let bytes = super::encode(&ans);
237        println!("Bytes are {bytes:?} for {ans:?}");
238        let decoded = super::decode(&bytes);
239        assert_eq!(decoded, Some(ans), "decoded value is incorrect");
240        let v = (
241            ($v, $v, $v, $v, $v, $v, $v, $v),
242            ($v, $v, $v, $v, $v, $v, $v, $v),
243            ($v, $v, $v, $v, $v, $v, $v, $v),
244            ($v, $v, $v, $v, $v, $v, $v, $v),
245            ($v, $v, $v, $v, $v, $v, $v, $v),
246            ($v, $v, $v, $v, $v, $v, $v, $v),
247            ($v, $v, $v, $v, $v, $v, $v, $v),
248            ($v, $v, $v, $v, $v, $v, $v, $v),
249        );
250        let bytes = super::encode(&v);
251        let decoded = super::decode(&bytes);
252        assert_eq!(decoded, Some(v), "decoded tuple value is incorrect");
253        assert_eq!((bytes.len() + 4) / 8, $size, "unexpected number of bits");
254    };
255    ($v:expr, $size:expr, $msg:expr) => {
256        let ans = $v;
257        let bytes = super::encode(&ans);
258        let decoded = super::decode(&bytes);
259        assert_eq!(decoded, Some(ans), "decoded value is incorrect: {}", $msg);
260        let v = (
261            ($v, $v, $v, $v, $v, $v, $v, $v),
262            ($v, $v, $v, $v, $v, $v, $v, $v),
263            ($v, $v, $v, $v, $v, $v, $v, $v),
264            ($v, $v, $v, $v, $v, $v, $v, $v),
265            ($v, $v, $v, $v, $v, $v, $v, $v),
266            ($v, $v, $v, $v, $v, $v, $v, $v),
267            ($v, $v, $v, $v, $v, $v, $v, $v),
268            ($v, $v, $v, $v, $v, $v, $v, $v),
269        );
270        let bytes = super::encode(&v);
271        let decoded = super::decode(&bytes);
272        assert_eq!(
273            decoded,
274            Some(v),
275            "decoded tuple value is incorrect: {}",
276            $msg
277        );
278        assert_eq!(
279            (bytes.len() + 4) / 8,
280            $size,
281            "unexpected number of bits: {}",
282            $msg
283        );
284    };
285}
286#[cfg(test)]
287pub(crate) use assert_bits;
288
289#[cfg(test)]
290macro_rules! raw_bits {
291    ($v:expr, $size:expr) => {
292        let v = $v;
293        let encoded = super::Raw::encode(&v);
294        let decoded = super::Raw::decode(&encoded);
295        let (bits, entropy) = super::Raw::sizes(&v);
296        assert_eq!(decoded, Some(v));
297        assert_eq!(bits, $size, "unexpected number of raw bits");
298        assert_eq!(entropy, super::Millibits::bits($size), "unexpected entropy");
299    };
300    ($v:expr, $size:expr, $millibits:expr) => {
301        let (bits, entropy) = super::Raw::sizes(&$v);
302        assert_eq!(bits, $size, "unexpected number of raw bits");
303        assert_eq!(entropy, $millibits, "unexpected entropy");
304    };
305}
306#[cfg(test)]
307pub(crate) use raw_bits;
308
309#[cfg(test)]
310macro_rules! assert_ans_bits {
311    ($v:expr, $size:expr) => {
312        let ans = $v;
313        let bytes = super::Ans::encode(&ans);
314        let decoded = super::Ans::decode(&bytes);
315        assert_eq!(decoded, Some(ans), "decoded value is incorrect");
316        let v = (
317            ($v, $v, $v, $v, $v, $v, $v, $v),
318            ($v, $v, $v, $v, $v, $v, $v, $v),
319            ($v, $v, $v, $v, $v, $v, $v, $v),
320            ($v, $v, $v, $v, $v, $v, $v, $v),
321            ($v, $v, $v, $v, $v, $v, $v, $v),
322            ($v, $v, $v, $v, $v, $v, $v, $v),
323            ($v, $v, $v, $v, $v, $v, $v, $v),
324            ($v, $v, $v, $v, $v, $v, $v, $v),
325        );
326        let bytes = super::Ans::encode(&v);
327        let decoded = super::Ans::decode(&bytes);
328        assert_eq!(decoded, Some(v), "decoded tuple value is incorrect");
329        assert_eq!((bytes.len() + 4) / 8, $size, "unexpected number of bits");
330    };
331    ($v:expr, $size:expr, $msg:expr) => {
332        let ans = $v;
333        let bytes = super::Ans::encode(&ans);
334        let decoded = super::Ans::decode(&bytes);
335        assert_eq!(decoded, Some(ans), "decoded value is incorrect: {}", $msg);
336        let v = (
337            ($v, $v, $v, $v, $v, $v, $v, $v),
338            ($v, $v, $v, $v, $v, $v, $v, $v),
339            ($v, $v, $v, $v, $v, $v, $v, $v),
340            ($v, $v, $v, $v, $v, $v, $v, $v),
341            ($v, $v, $v, $v, $v, $v, $v, $v),
342            ($v, $v, $v, $v, $v, $v, $v, $v),
343            ($v, $v, $v, $v, $v, $v, $v, $v),
344            ($v, $v, $v, $v, $v, $v, $v, $v),
345        );
346        let bytes = super::Ans::encode(&v);
347        let decoded = super::Ans::decode(&bytes);
348        assert_eq!(
349            decoded,
350            Some(v),
351            "decoded tuple value is incorrect: {}",
352            $msg
353        );
354        assert_eq!(
355            (bytes.len() + 4) / 8,
356            $size,
357            "unexpected number of bits: {}",
358            $msg
359        );
360    };
361}
362#[cfg(test)]
363pub(crate) use assert_ans_bits;
compactly/v2/mod.rs

compactly/v2/
mod.rs
