/rust/registry/src/index.crates.io-1949cf8c6b5b557f/bitstream-io-4.10.0/src/huffman.rs

Source
// Copyright 2017 Brian Langenberger
//
// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
// option. This file may not be copied, modified, or distributed
// except according to those terms.

//! Traits and implementations for reading or writing Huffman codes
//! from or to a stream.

#![warn(missing_docs)]

/// A trait for building a final value from individual bits
///
/// Though similar to the [`crate::read::FromBitStream`] trait,
/// this is intended to parse short symbols from a stream of bits
/// while `FromBitStream` is meant for parsing larger structs from
/// a whole reader.
/// For example, one might have several [`FromBits`] implementations
/// in a single program that all generate `i32` symbols from bits,
/// but implementing `FromBitStream` multiple times for `i32`
/// isn't possible (or practical).
pub trait FromBits {
    /// Our returned symbol type
    type Symbol;

    /// Given a fallable bit generator, return our output type
    ///
    /// # Errors
    ///
    /// Passes along any error from the bit generator
    fn from_bits<F, E>(next: F) -> Result<Self::Symbol, E>
    where
        F: FnMut() -> Result<bool, E>;
}

/// For building individual bits from a final value
///
/// Though similar to the [`crate::write::ToBitStream`] trait,
/// this is intended to generate a stream of bits from short symbols
/// while `ToBitStream` is meant for writing larger structs to
/// a whole writer.
/// For example, one might have several [`ToBits`] implementations
/// in a single program that all write `i32` symbols to bits,
/// but implementing `ToBitStream` multiple times for `i32`
/// isn't possible (or practical).
pub trait ToBits {
    /// The type we accept to output
    type Symbol;

    /// Given a value to generate, write out bits as needed.
    ///
    /// Outputs nothing if the symbol isn't defined.
    ///
    /// # Errors
    ///
    /// Passes along any error from the bit generator
    fn to_bits<F, E>(value: Self::Symbol, write: F) -> Result<(), E>
    where
        F: FnMut(bool) -> Result<(), E>;
}

/// Defines a new Huffman tree for reading and writing
///
/// Its syntax is: `define_huffman_tree!(name : type = nodes)`
/// where `name` is some identifier to identify the tree in the
/// macro's current scope, `type` is the tree's output
/// type (which should implement `Copy` and `Eq`), and `nodes` is either a
/// final leaf value or a `[bit_0, bit_1]` pair where `bit_0` is
/// the tree visited on a `0` bit, and `bit_1` is the tree visited
/// on a `1` bit.
///
/// # Example
///
/// ```
/// use bitstream_io::{define_huffman_tree, huffman::FromBits};
/// define_huffman_tree!(TreeName : &'static str = ["bit 0", ["bit 1->0", "bit 1->1"]]);
/// let mut bits = [true, false].iter().copied();
/// assert_eq!(TreeName::from_bits(|| bits.next().ok_or(())).unwrap(), "bit 1->0");
/// ```
#[macro_export]
macro_rules! define_huffman_tree {
    ($name:ident : $type:ty = $nodes:tt) => {
        #[derive(Copy, Clone, Debug)]
        struct $name;

        impl $crate::huffman::FromBits for $name {
            type Symbol = $type;

            fn from_bits<F, E>(mut next: F) -> Result<Self::Symbol, E>
            where
                F: FnMut() -> Result<bool, E>,
            {
                $crate::compile_read_tree_nodes!(next, $nodes)
            }
        }

        impl $crate::huffman::ToBits for $name {
            type Symbol = $type;

            fn to_bits<F, E>(value: Self::Symbol, mut write: F) -> Result<(), E>
            where
                F: FnMut(bool) -> Result<(), E>
            {
                $crate::compile_write_tree_nodes!(value ; write ; $nodes ; );
                Ok(())
            }
        }
    };
}

/// A helper macro for compiling individual Huffman tree nodes
#[macro_export]
macro_rules! compile_read_tree_nodes {
    ($next:ident , [$bit_0:tt, $bit_1:tt]) => {
        if $next()? {
            $crate::compile_read_tree_nodes!($next, $bit_1)
        } else {
            $crate::compile_read_tree_nodes!($next, $bit_0)
        }
    };
    ($next:ident , $final:tt) => {
        Ok($final)
    };
}

/// A helper macro for compiling individual Huffman tree nodes
#[macro_export]
macro_rules! compile_write_tree_nodes {
    // end case for calculate tree node count
    ($final:tt) => {
        1
    };
    // recursive case for calculating tree node count
    ([$bit_0:tt, $bit_1:tt]) => {
        compile_write_tree_nodes!($bit_0) + compile_write_tree_nodes!($bit_1)
    };
    // entry point for generating conditional recursively
    ($value:ident ; $write:ident ; [$bit_0:tt, $bit_1:tt] ; ) => {
        if $crate::compile_write_tree_nodes!($bit_0) <= $crate::compile_write_tree_nodes!($bit_1) {
            $crate::compile_write_tree_nodes!($value ; $write ; $bit_0 ; false);
            $crate::compile_write_tree_nodes!($value ; $write ; $bit_1 ; true);
        } else {
            $crate::compile_write_tree_nodes!($value ; $write ; $bit_1 ; false);
            $crate::compile_write_tree_nodes!($value ; $write ; $bit_0 ; true);
        }
    };
    // recursive case for generating conditional
    ($value:ident ; $write:ident ; [$bit_0:tt, $bit_1:tt] ; $($bits:tt),*) => {
        if $crate::compile_write_tree_nodes!($bit_0) <= $crate::compile_write_tree_nodes!($bit_1) {
            $crate::compile_write_tree_nodes!($value ; $write ; $bit_0 ; $($bits),* , false);
            $crate::compile_write_tree_nodes!($value ; $write ; $bit_1 ; $($bits),* , true);
        } else {
            $crate::compile_write_tree_nodes!($value ; $write ; $bit_1 ; $($bits),* , false);
            $crate::compile_write_tree_nodes!($value ; $write ; $bit_0 ; $($bits),* , true);
        }
    };
    // final case for generating conditonal which generates bits
    ($value:ident ; $write:ident ; $final:tt ; $( $bits:tt),* ) => {
        if $value == $final {
            $( $write($bits)?; )*
            return Ok(());
        }
    };
}

/// A limited unary reader which stops at the given maximum.
///
/// Counts non-`STOP_BIT` values (which must be 0 or 1)
/// until `STOP_BIT`, or until `MAXIMUM` is reached.
/// Returns the number of non-`STOP_BIT` bits, or `None` if
/// maximum is reached beforehand.
///
/// # Examples
/// ```
/// use bitstream_io::{BitReader, BitRead, BigEndian, huffman::LimitedUnary};
///
/// let data: &[u8] = &[0b001_00000, 0b1111_1111];
/// let mut r = BitReader::endian(data, BigEndian);
/// // get 2 bits until the next 1 bit
/// assert_eq!(r.read_huffman::<LimitedUnary<1, 5>>().unwrap(), Some(2));
/// // but 5 bits in a row is our maximum
/// assert_eq!(r.read_huffman::<LimitedUnary<1, 5>>().unwrap(), None);
/// // the remaining 8 bits are ok to be read
/// assert_eq!(r.read::<8, u8>().unwrap(), 0b1111_1111);
/// ```
///
/// ```
/// use bitstream_io::{BitWriter, BitWrite, BigEndian, huffman::LimitedUnary};
///
/// let mut w = BitWriter::endian(vec![], BigEndian);
/// // writes 2 as a regular unary value which stops at the 1 bit
/// w.write_huffman::<LimitedUnary<1, 5>>(Some(2)).unwrap();
/// // writing values beyond the maximum does nothing
/// w.write_huffman::<LimitedUnary<1, 5>>(Some(10)).unwrap();
/// // writes 5, 0 bits (which is our maximum)
/// w.write_huffman::<LimitedUnary<1, 5>>(None).unwrap();
/// // write some 1 bits to pad out the stream
/// w.write::<8, u8>(0b1111_1111);
///
/// assert_eq!(w.into_writer(), &[0b001_00000, 0b1111_1111]);
/// ```
#[derive(Copy, Clone, Debug)]
pub struct LimitedUnary<const STOP_BIT: u8, const MAXIMUM: u32>;

impl<const STOP_BIT: u8, const MAXIMUM: u32> FromBits for LimitedUnary<STOP_BIT, MAXIMUM> {
    type Symbol = Option<u32>;

    fn from_bits<F, E>(mut next: F) -> Result<Self::Symbol, E>
    where
        F: FnMut() -> Result<bool, E>,
    {
        const {
            assert!(matches!(STOP_BIT, 0 | 1), "stop bit must be 0 or 1");
        }

        let mut bits = 0;
        while bits < MAXIMUM {
            if next()?
                != match STOP_BIT {
                    0 => false,
                    1 => true,
                    _ => unreachable!(),
                }
            {
                bits += 1;
            } else {
                return Ok(Some(bits));
            }
        }
        Ok(None)
    }
}

impl<const STOP_BIT: u8, const MAXIMUM: u32> ToBits for LimitedUnary<STOP_BIT, MAXIMUM> {
    type Symbol = Option<u32>;

    fn to_bits<F, E>(value: Option<u32>, mut write: F) -> Result<(), E>
    where
        F: FnMut(bool) -> Result<(), E>,
    {
        const {
            assert!(matches!(STOP_BIT, 0 | 1), "stop bit must be 0 or 1");
        }

        match value {
            Some(bits) if bits < MAXIMUM => {
                (0..bits).try_for_each(|_| {
                    write(match STOP_BIT {
                        0 => true,
                        1 => false,
                        _ => unreachable!(),
                    })
                })?;
                write(match STOP_BIT {
                    0 => false,
                    1 => true,
                    _ => unreachable!(),
                })
            }
            Some(_) => {
                /*more bits than MAXIMUM, so output nothing*/
                Ok(())
            }
            None => (0..MAXIMUM).try_for_each(|_| {
                write(match STOP_BIT {
                    0 => true,
                    1 => false,
                    _ => unreachable!(),
                })
            }),
        }
    }
}

Coverage Report

Created: 2026-09-01 07:45

Line	Count	Source
1		// Copyright 2017 Brian Langenberger
2		//
3		// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
4		// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
5		// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
6		// option. This file may not be copied, modified, or distributed
7		// except according to those terms.
8
9		//! Traits and implementations for reading or writing Huffman codes
10		//! from or to a stream.
11
12		#![warn(missing_docs)]
13
14		/// A trait for building a final value from individual bits
15		///
16		/// Though similar to the [`crate::read::FromBitStream`] trait,
17		/// this is intended to parse short symbols from a stream of bits
18		/// while `FromBitStream` is meant for parsing larger structs from
19		/// a whole reader.
20		/// For example, one might have several [`FromBits`] implementations
21		/// in a single program that all generate `i32` symbols from bits,
22		/// but implementing `FromBitStream` multiple times for `i32`
23		/// isn't possible (or practical).
24		pub trait FromBits {
25		/// Our returned symbol type
26		type Symbol;
27
28		/// Given a fallable bit generator, return our output type
29		///
30		/// # Errors
31		///
32		/// Passes along any error from the bit generator
33		fn from_bits<F, E>(next: F) -> Result<Self::Symbol, E>
34		where
35		F: FnMut() -> Result<bool, E>;
36		}
37
38		/// For building individual bits from a final value
39		///
40		/// Though similar to the [`crate::write::ToBitStream`] trait,
41		/// this is intended to generate a stream of bits from short symbols
42		/// while `ToBitStream` is meant for writing larger structs to
43		/// a whole writer.
44		/// For example, one might have several [`ToBits`] implementations
45		/// in a single program that all write `i32` symbols to bits,
46		/// but implementing `ToBitStream` multiple times for `i32`
47		/// isn't possible (or practical).
48		pub trait ToBits {
49		/// The type we accept to output
50		type Symbol;
51
52		/// Given a value to generate, write out bits as needed.
53		///
54		/// Outputs nothing if the symbol isn't defined.
55		///
56		/// # Errors
57		///
58		/// Passes along any error from the bit generator
59		fn to_bits<F, E>(value: Self::Symbol, write: F) -> Result<(), E>
60		where
61		F: FnMut(bool) -> Result<(), E>;
62		}
63
64		/// Defines a new Huffman tree for reading and writing
65		///
66		/// Its syntax is: `define_huffman_tree!(name : type = nodes)`
67		/// where `name` is some identifier to identify the tree in the
68		/// macro's current scope, `type` is the tree's output
69		/// type (which should implement `Copy` and `Eq`), and `nodes` is either a
70		/// final leaf value or a `[bit_0, bit_1]` pair where `bit_0` is
71		/// the tree visited on a `0` bit, and `bit_1` is the tree visited
72		/// on a `1` bit.
73		///
74		/// # Example
75		///
76		/// ```
77		/// use bitstream_io::{define_huffman_tree, huffman::FromBits};
78		/// define_huffman_tree!(TreeName : &'static str = ["bit 0", ["bit 1->0", "bit 1->1"]]);
79		/// let mut bits = [true, false].iter().copied();
80		/// assert_eq!(TreeName::from_bits(\|\| bits.next().ok_or(())).unwrap(), "bit 1->0");
81		/// ```
82		#[macro_export]
83		macro_rules! define_huffman_tree {
84		($name:ident : $type:ty = $nodes:tt) => {
85		#[derive(Copy, Clone, Debug)]
86		struct $name;
87
88		impl $crate::huffman::FromBits for $name {
89		type Symbol = $type;
90
91		fn from_bits<F, E>(mut next: F) -> Result<Self::Symbol, E>
92		where
93		F: FnMut() -> Result<bool, E>,
94		{
95		$crate::compile_read_tree_nodes!(next, $nodes)
96		}
97		}
98
99		impl $crate::huffman::ToBits for $name {
100		type Symbol = $type;
101
102		fn to_bits<F, E>(value: Self::Symbol, mut write: F) -> Result<(), E>
103		where
104		F: FnMut(bool) -> Result<(), E>
105		{
106		$crate::compile_write_tree_nodes!(value ; write ; $nodes ; );
107		Ok(())
108		}
109		}
110		};
111		}
112
113		/// A helper macro for compiling individual Huffman tree nodes
114		#[macro_export]
115		macro_rules! compile_read_tree_nodes {
116		($next:ident , [$bit_0:tt, $bit_1:tt]) => {
117		if $next()? {
118		$crate::compile_read_tree_nodes!($next, $bit_1)
119		} else {
120		$crate::compile_read_tree_nodes!($next, $bit_0)
121		}
122		};
123		($next:ident , $final:tt) => {
124		Ok($final)
125		};
126		}
127
128		/// A helper macro for compiling individual Huffman tree nodes
129		#[macro_export]
130		macro_rules! compile_write_tree_nodes {
131		// end case for calculate tree node count
132		($final:tt) => {
133		1
134		};
135		// recursive case for calculating tree node count
136		([$bit_0:tt, $bit_1:tt]) => {
137		compile_write_tree_nodes!($bit_0) + compile_write_tree_nodes!($bit_1)
138		};
139		// entry point for generating conditional recursively
140		($value:ident ; $write:ident ; [$bit_0:tt, $bit_1:tt] ; ) => {
141		if $crate::compile_write_tree_nodes!($bit_0) <= $crate::compile_write_tree_nodes!($bit_1) {
142		$crate::compile_write_tree_nodes!($value ; $write ; $bit_0 ; false);
143		$crate::compile_write_tree_nodes!($value ; $write ; $bit_1 ; true);
144		} else {
145		$crate::compile_write_tree_nodes!($value ; $write ; $bit_1 ; false);
146		$crate::compile_write_tree_nodes!($value ; $write ; $bit_0 ; true);
147		}
148		};
149		// recursive case for generating conditional
150		($value:ident ; $write:ident ; [$bit_0:tt, $bit_1:tt] ; $($bits:tt),*) => {
151		if $crate::compile_write_tree_nodes!($bit_0) <= $crate::compile_write_tree_nodes!($bit_1) {
152		$crate::compile_write_tree_nodes!($value ; $write ; $bit_0 ; $($bits),* , false);
153		$crate::compile_write_tree_nodes!($value ; $write ; $bit_1 ; $($bits),* , true);
154		} else {
155		$crate::compile_write_tree_nodes!($value ; $write ; $bit_1 ; $($bits),* , false);
156		$crate::compile_write_tree_nodes!($value ; $write ; $bit_0 ; $($bits),* , true);
157		}
158		};
159		// final case for generating conditonal which generates bits
160		($value:ident ; $write:ident ; $final:tt ; $( $bits:tt),* ) => {
161		if $value == $final {
162		$( $write($bits)?; )*
163		return Ok(());
164		}
165		};
166		}
167
168		/// A limited unary reader which stops at the given maximum.
169		///
170		/// Counts non-`STOP_BIT` values (which must be 0 or 1)
171		/// until `STOP_BIT`, or until `MAXIMUM` is reached.
172		/// Returns the number of non-`STOP_BIT` bits, or `None` if
173		/// maximum is reached beforehand.
174		///
175		/// # Examples
176		/// ```
177		/// use bitstream_io::{BitReader, BitRead, BigEndian, huffman::LimitedUnary};
178		///
179		/// let data: &[u8] = &[0b001_00000, 0b1111_1111];
180		/// let mut r = BitReader::endian(data, BigEndian);
181		/// // get 2 bits until the next 1 bit
182		/// assert_eq!(r.read_huffman::<LimitedUnary<1, 5>>().unwrap(), Some(2));
183		/// // but 5 bits in a row is our maximum
184		/// assert_eq!(r.read_huffman::<LimitedUnary<1, 5>>().unwrap(), None);
185		/// // the remaining 8 bits are ok to be read
186		/// assert_eq!(r.read::<8, u8>().unwrap(), 0b1111_1111);
187		/// ```
188		///
189		/// ```
190		/// use bitstream_io::{BitWriter, BitWrite, BigEndian, huffman::LimitedUnary};
191		///
192		/// let mut w = BitWriter::endian(vec![], BigEndian);
193		/// // writes 2 as a regular unary value which stops at the 1 bit
194		/// w.write_huffman::<LimitedUnary<1, 5>>(Some(2)).unwrap();
195		/// // writing values beyond the maximum does nothing
196		/// w.write_huffman::<LimitedUnary<1, 5>>(Some(10)).unwrap();
197		/// // writes 5, 0 bits (which is our maximum)
198		/// w.write_huffman::<LimitedUnary<1, 5>>(None).unwrap();
199		/// // write some 1 bits to pad out the stream
200		/// w.write::<8, u8>(0b1111_1111);
201		///
202		/// assert_eq!(w.into_writer(), &[0b001_00000, 0b1111_1111]);
203		/// ```
204		#[derive(Copy, Clone, Debug)]
205		pub struct LimitedUnary<const STOP_BIT: u8, const MAXIMUM: u32>;
206
207		impl<const STOP_BIT: u8, const MAXIMUM: u32> FromBits for LimitedUnary<STOP_BIT, MAXIMUM> {
208		type Symbol = Option<u32>;
209
210	0	fn from_bits<F, E>(mut next: F) -> Result<Self::Symbol, E>
211	0	where
212	0	F: FnMut() -> Result<bool, E>,
213		{
214		const {
215		assert!(matches!(STOP_BIT, 0 \| 1), "stop bit must be 0 or 1");
216		}
217
218	0	let mut bits = 0;
219	0	while bits < MAXIMUM {
220	0	if next()?
221	0	!= match STOP_BIT {
222	0	0 => false,
223	0	1 => true,
224	0	_ => unreachable!(),
225		}
226	0	{
227	0	bits += 1;
228	0	} else {
229	0	return Ok(Some(bits));
230		}
231		}
232	0	Ok(None)
233	0	}
234		}
235
236		impl<const STOP_BIT: u8, const MAXIMUM: u32> ToBits for LimitedUnary<STOP_BIT, MAXIMUM> {
237		type Symbol = Option<u32>;
238
239	0	fn to_bits<F, E>(value: Option<u32>, mut write: F) -> Result<(), E>
240	0	where
241	0	F: FnMut(bool) -> Result<(), E>,
242		{
243		const {
244		assert!(matches!(STOP_BIT, 0 \| 1), "stop bit must be 0 or 1");
245		}
246
247	0	match value {
248	0	Some(bits) if bits < MAXIMUM => {
249	0	(0..bits).try_for_each(\|_\| {
250	0	write(match STOP_BIT {
251	0	0 => true,
252	0	1 => false,
253	0	_ => unreachable!(),
254		})
255	0	})?;
256	0	write(match STOP_BIT {
257	0	0 => false,
258	0	1 => true,
259	0	_ => unreachable!(),
260		})
261		}
262		Some(_) => {
263		/more bits than MAXIMUM, so output nothing/
264	0	Ok(())
265		}
266	0	None => (0..MAXIMUM).try_for_each(\|_\| {
267	0	write(match STOP_BIT {
268	0	0 => true,
269	0	1 => false,
270	0	_ => unreachable!(),
271		})
272	0	}),
273		}
274	0	}
275		}