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 helpers for bitstream handling functionality
10//!
11//! Bitstream readers are for reading signed and unsigned integer
12//! values from a stream whose sizes may not be whole bytes.
13//! Bitstream writers are for writing signed and unsigned integer
14//! values to a stream, also potentially un-aligned at a whole byte.
15//!
16//! Both big-endian and little-endian streams are supported.
17//!
18//! The only requirement for wrapped reader streams is that they must
19//! implement the `Read` trait, and the only requirement
20//! for writer streams is that they must implement the `Write` trait.
21//!
22//! In addition, reader streams do not consume any more bytes
23//! from the underlying reader than necessary, buffering only a
24//! single partial byte as needed.
25//! Writer streams also write out all whole bytes as they are accumulated.
26//!
27//! Readers and writers are also designed to work with integer
28//! types of any possible size.
29//! Many of Rust's built-in integer types are supported by default.
30
31//! # Minimum Compiler Version
32//!
33//! Beginning with version 2.4, the minimum compiler version has been
34//! updated to Rust 1.79.
35//!
36//! The issue is that reading an excessive number of
37//! bits to a type which is too small to hold them,
38//! or writing an excessive number of bits from too small of a type,
39//! are always errors:
40//! ```
41//! use std::io::{Read, Cursor};
42//! use bitstream_io::{BigEndian, BitReader, BitRead};
43//! let data = [0; 10];
44//! let mut r = BitReader::endian(Cursor::new(&data), BigEndian);
45//! let x: Result<u32, _> = r.read(64); // reading 64 bits to u32 always fails at runtime
46//! assert!(x.is_err());
47//! ```
48//! but those errors will not be caught until the program runs,
49//! which is less than ideal for the common case in which
50//! the number of bits is already known at compile-time.
51//!
52//! But starting with Rust 1.79, we can now have read and write methods
53//! which take a constant number of bits and can validate the number of bits
54//! are small enough for the type being read/written at compile-time:
55//! ```rust,ignore
56//! use std::io::{Read, Cursor};
57//! use bitstream_io::{BigEndian, BitReader, BitRead};
58//! let data = [0; 10];
59//! let mut r = BitReader::endian(Cursor::new(&data), BigEndian);
60//! let x: Result<u32, _> = r.read_in::<64, _>(); // doesn't compile at all
61//! ```
62//! Since catching potential bugs at compile-time is preferable
63//! to encountering errors at runtime, this will hopefully be
64//! an improvement in the long run.
65
66//! # Migrating From Pre 1.0.0
67//!
68//! There are now `BitRead` and `BitWrite` traits for bitstream
69//! reading and writing (analogous to the standard library's
70//! `Read` and `Write` traits) which you will also need to import.
71//! The upside to this approach is that library consumers
72//! can now make functions and methods generic over any sort
73//! of bit reader or bit writer, regardless of the underlying
74//! stream byte source or endianness.
75
76#![warn(missing_docs)]
77#![forbid(unsafe_code)]
78#![cfg_attr(feature = "alloc", no_std)]
79
80#[cfg(feature = "alloc")]
81extern crate alloc;
82use core::fmt::Debug;
83use core::marker::PhantomData;
84use core::mem;
85use core::ops::{BitOrAssign, BitXor, Not, Rem, RemAssign, Shl, ShlAssign, Shr, ShrAssign, Sub};
86#[cfg(feature = "alloc")]
87use core2::io;
88#[cfg(not(feature = "alloc"))]
89use std::io;
90
91pub mod huffman;
92pub mod read;
93pub mod write;
94pub use read::{
95 BitRead, BitReader, ByteRead, ByteReader, FromBitStream, FromBitStreamWith, FromByteStream,
96 FromByteStreamWith, HuffmanRead,
97};
98pub use write::{
99 BitCounter, BitRecorder, BitWrite, BitWriter, ByteWrite, ByteWriter, HuffmanWrite, ToBitStream,
100 ToBitStreamWith, ToByteStream, ToByteStreamWith,
101};
102
103/// A trait intended for simple fixed-length primitives (such as ints and floats)
104/// which allows them to be read and written to streams of
105/// different endiannesses verbatim.
106pub trait Primitive {
107 /// The raw byte representation of this numeric type
108 type Bytes: AsRef<[u8]> + AsMut<[u8]>;
109
110 /// An empty buffer of this type's size
111 fn buffer() -> Self::Bytes;
112
113 /// Our value in big-endian bytes
114 fn to_be_bytes(self) -> Self::Bytes;
115
116 /// Our value in little-endian bytes
117 fn to_le_bytes(self) -> Self::Bytes;
118
119 /// Convert big-endian bytes to our value
120 fn from_be_bytes(bytes: Self::Bytes) -> Self;
121
122 /// Convert little-endian bytes to our value
123 fn from_le_bytes(bytes: Self::Bytes) -> Self;
124}
125
126macro_rules! define_primitive_numeric {
127 ($t:ty) => {
128 impl Primitive for $t {
129 type Bytes = [u8; mem::size_of::<$t>()];
130
131 #[inline(always)]
132 fn buffer() -> Self::Bytes {
133 [0; mem::size_of::<$t>()]
134 }
135 #[inline(always)]
136 fn to_be_bytes(self) -> Self::Bytes {
137 self.to_be_bytes()
138 }
139 #[inline(always)]
140 fn to_le_bytes(self) -> Self::Bytes {
141 self.to_le_bytes()
142 }
143 #[inline(always)]
144 fn from_be_bytes(bytes: Self::Bytes) -> Self {
145 <$t>::from_be_bytes(bytes)
146 }
147 #[inline(always)]
148 fn from_le_bytes(bytes: Self::Bytes) -> Self {
149 <$t>::from_le_bytes(bytes)
150 }
151 }
152 };
153}
154
155impl<const N: usize> Primitive for [u8; N] {
156 type Bytes = [u8; N];
157
158 #[inline(always)]
159 fn buffer() -> Self::Bytes {
160 [0; N]
161 }
162
163 #[inline(always)]
164 fn to_be_bytes(self) -> Self::Bytes {
165 self
166 }
167
168 #[inline(always)]
169 fn to_le_bytes(self) -> Self::Bytes {
170 self
171 }
172
173 #[inline(always)]
174 fn from_be_bytes(bytes: Self::Bytes) -> Self {
175 bytes
176 }
177
178 #[inline(always)]
179 fn from_le_bytes(bytes: Self::Bytes) -> Self {
180 bytes
181 }
182}
183
184/// This trait extends many common integer types (both unsigned and signed)
185/// with a few trivial methods so that they can be used
186/// with the bitstream handling traits.
187pub trait Numeric:
188 Primitive
189 + Sized
190 + Copy
191 + Default
192 + Debug
193 + PartialOrd
194 + Shl<u32, Output = Self>
195 + ShlAssign<u32>
196 + Shr<u32, Output = Self>
197 + ShrAssign<u32>
198 + Rem<Self, Output = Self>
199 + RemAssign<Self>
200 + BitOrAssign<Self>
201 + BitXor<Self, Output = Self>
202 + Not<Output = Self>
203 + Sub<Self, Output = Self>
204{
205 /// Size of type in bits
206 const BITS_SIZE: u32;
207
208 /// The value of 1 in this type
209 const ONE: Self;
210
211 /// Returns true if this value is 0, in its type
212 fn is_zero(self) -> bool;
213
214 /// Returns a `u8` value in this type
215 fn from_u8(u: u8) -> Self;
216
217 /// Assuming 0 <= value < 256, returns this value as a `u8` type
218 fn to_u8(self) -> u8;
219
220 /// Counts the number of 1 bits
221 fn count_ones(self) -> u32;
222
223 /// Counts the number of leading zeros
224 fn leading_zeros(self) -> u32;
225
226 /// Counts the number of trailing zeros
227 fn trailing_zeros(self) -> u32;
228
229 /// Convert to a generic unsigned write value for stream recording purposes
230 fn unsigned_value(self) -> write::UnsignedValue;
231}
232
233macro_rules! define_numeric {
234 ($t:ty) => {
235 define_primitive_numeric!($t);
236
237 impl Numeric for $t {
238 const BITS_SIZE: u32 = mem::size_of::<$t>() as u32 * 8;
239
240 const ONE: Self = 1;
241
242 #[inline(always)]
243 fn is_zero(self) -> bool {
244 self == 0
245 }
246 #[inline(always)]
247 fn from_u8(u: u8) -> Self {
248 u as $t
249 }
250 #[inline(always)]
251 fn to_u8(self) -> u8 {
252 self as u8
253 }
254 #[inline(always)]
255 fn count_ones(self) -> u32 {
256 self.count_ones()
257 }
258 #[inline(always)]
259 fn leading_zeros(self) -> u32 {
260 self.leading_zeros()
261 }
262 #[inline(always)]
263 fn trailing_zeros(self) -> u32 {
264 self.trailing_zeros()
265 }
266 #[inline(always)]
267 fn unsigned_value(self) -> write::UnsignedValue {
268 self.into()
269 }
270 }
271 };
272}
273
274/// This trait extends many common signed integer types
275/// so that they can be used with the bitstream handling traits.
276pub trait SignedNumeric: Numeric {
277 /// Returns true if this value is negative
278 fn is_negative(self) -> bool;
279
280 /// Given a two-complement positive value and certain number of bits,
281 /// returns this value as a negative number.
282 fn as_negative(self, bits: u32) -> Self;
283
284 /// Given a two-complement positive value and certain number of bits,
285 /// returns this value as a negative number.
286 fn as_negative_fixed<const BITS: u32>(self) -> Self;
287
288 /// Given a negative value and a certain number of bits,
289 /// returns this value as a twos-complement positive number.
290 fn as_unsigned(self, bits: u32) -> Self;
291
292 /// Given a negative value and a certain number of bits,
293 /// returns this value as a twos-complement positive number.
294 fn as_unsigned_fixed<const BITS: u32>(self) -> Self;
295
296 /// Converts to a generic signed value for stream recording purposes.
297 fn signed_value(self) -> write::SignedValue;
298}
299
300macro_rules! define_signed_numeric {
301 ($t:ty) => {
302 impl SignedNumeric for $t {
303 #[inline(always)]
304 fn is_negative(self) -> bool {
305 self < 0
306 }
307 #[inline(always)]
308 fn as_negative(self, bits: u32) -> Self {
309 self + (-1 << (bits - 1))
310 }
311 #[inline(always)]
312 fn as_negative_fixed<const BITS: u32>(self) -> Self {
313 self + (-1 << (BITS - 1))
314 }
315 #[inline(always)]
316 fn as_unsigned(self, bits: u32) -> Self {
317 self - (-1 << (bits - 1))
318 }
319 #[inline(always)]
320 fn as_unsigned_fixed<const BITS: u32>(self) -> Self {
321 self - (-1 << (BITS - 1))
322 }
323 #[inline(always)]
324 fn signed_value(self) -> write::SignedValue {
325 self.into()
326 }
327 }
328 };
329}
330
331define_numeric!(u8);
332define_numeric!(i8);
333define_numeric!(u16);
334define_numeric!(i16);
335define_numeric!(u32);
336define_numeric!(i32);
337define_numeric!(u64);
338define_numeric!(i64);
339define_numeric!(u128);
340define_numeric!(i128);
341
342define_signed_numeric!(i8);
343define_signed_numeric!(i16);
344define_signed_numeric!(i32);
345define_signed_numeric!(i64);
346define_signed_numeric!(i128);
347
348define_primitive_numeric!(f32);
349define_primitive_numeric!(f64);
350
351/// A stream's endianness, or byte order, for determining
352/// how bits should be read.
353///
354/// It comes in `BigEndian` and `LittleEndian` varieties
355/// (which may be shortened to `BE` and `LE`)
356/// and is not something programmers should have to implement
357/// in most cases.
358pub trait Endianness: Sized {
359 /// Pushes the given bits and value onto an accumulator
360 /// with the given bits and value.
361 fn push<N>(queue: &mut BitQueue<Self, N>, bits: u32, value: N)
362 where
363 N: Numeric;
364
365 /// Pushes the given constant number of bits and value onto an accumulator
366 /// with the given bits and value.
367 fn push_fixed<const B: u32, N>(queue: &mut BitQueue<Self, N>, value: N)
368 where
369 N: Numeric;
370
371 /// Pops a value with the given number of bits from an accumulator
372 /// with the given bits and value.
373 fn pop<N>(queue: &mut BitQueue<Self, N>, bits: u32) -> N
374 where
375 N: Numeric;
376
377 /// Pops a value with the given number of constant bits
378 /// from an accumulator with the given bits and value.
379 fn pop_fixed<const B: u32, N>(queue: &mut BitQueue<Self, N>) -> N
380 where
381 N: Numeric;
382
383 /// Drops the given number of bits from an accumulator
384 /// with the given bits and value.
385 fn drop<N>(queue: &mut BitQueue<Self, N>, bits: u32)
386 where
387 N: Numeric;
388
389 /// Returns the next number of 0 bits from an accumulator
390 /// with the given bits and value.
391 fn next_zeros<N>(queue: &BitQueue<Self, N>) -> u32
392 where
393 N: Numeric;
394
395 /// Returns the next number of 1 bits from an accumulator
396 /// with the given bits and value.
397 fn next_ones<N>(queue: &BitQueue<Self, N>) -> u32
398 where
399 N: Numeric;
400
401 /// Reads signed value from reader in this endianness
402 fn read_signed<R, S>(r: &mut R, bits: u32) -> io::Result<S>
403 where
404 R: BitRead,
405 S: SignedNumeric;
406
407 /// Reads signed value from reader in this endianness
408 fn read_signed_fixed<R, const B: u32, S>(r: &mut R) -> io::Result<S>
409 where
410 R: BitRead,
411 S: SignedNumeric;
412
413 /// Writes signed value to writer in this endianness
414 fn write_signed<W, S>(w: &mut W, bits: u32, value: S) -> io::Result<()>
415 where
416 W: BitWrite,
417 S: SignedNumeric;
418
419 /// Writes signed value to writer in this endianness
420 fn write_signed_fixed<W, const B: u32, S>(w: &mut W, value: S) -> io::Result<()>
421 where
422 W: BitWrite,
423 S: SignedNumeric;
424
425 /// Reads convertable numeric value from reader in this endianness
426 fn read_primitive<R, V>(r: &mut R) -> io::Result<V>
427 where
428 R: BitRead,
429 V: Primitive;
430
431 /// Writes convertable numeric value to writer in this endianness
432 fn write_primitive<W, V>(w: &mut W, value: V) -> io::Result<()>
433 where
434 W: BitWrite,
435 V: Primitive;
436
437 /// Reads entire numeric value from reader in this endianness
438 fn read_numeric<R, V>(r: R) -> io::Result<V>
439 where
440 R: io::Read,
441 V: Primitive;
442
443 /// Writes entire numeric value to writer in this endianness
444 fn write_numeric<W, V>(w: W, value: V) -> io::Result<()>
445 where
446 W: io::Write,
447 V: Primitive;
448}
449
450/// Big-endian, or most significant bits first
451#[derive(Copy, Clone, Debug)]
452pub struct BigEndian;
453
454/// Big-endian, or most significant bits first
455pub type BE = BigEndian;
456
457impl Endianness for BigEndian {
458 #[inline]
459 fn push<N>(queue: &mut BitQueue<Self, N>, bits: u32, value: N)
460 where
461 N: Numeric,
462 {
463 if !queue.value.is_zero() {
464 queue.value <<= bits;
465 }
466 queue.value |= value;
467 queue.bits += bits;
468 }
469
470 #[inline]
471 fn push_fixed<const B: u32, N>(queue: &mut BitQueue<Self, N>, value: N)
472 where
473 N: Numeric,
474 {
475 if !queue.value.is_zero() {
476 queue.value <<= B;
477 }
478 queue.value |= value;
479 queue.bits += B;
480 }
481
482 #[inline]
483 fn pop<N>(queue: &mut BitQueue<Self, N>, bits: u32) -> N
484 where
485 N: Numeric,
486 {
487 if bits < queue.bits {
488 let offset = queue.bits - bits;
489 let to_return = queue.value >> offset;
490 queue.value %= N::ONE << offset;
491 queue.bits -= bits;
492 to_return
493 } else {
494 let to_return = queue.value;
495 queue.value = N::default();
496 queue.bits = 0;
497 to_return
498 }
499 }
500
501 #[inline]
502 fn pop_fixed<const B: u32, N>(queue: &mut BitQueue<Self, N>) -> N
503 where
504 N: Numeric,
505 {
506 if B < queue.bits {
507 let offset = queue.bits - B;
508 let to_return = queue.value >> offset;
509 queue.value %= N::ONE << offset;
510 queue.bits -= B;
511 to_return
512 } else {
513 let to_return = queue.value;
514 queue.value = N::default();
515 queue.bits = 0;
516 to_return
517 }
518 }
519
520 #[inline]
521 fn drop<N>(queue: &mut BitQueue<Self, N>, bits: u32)
522 where
523 N: Numeric,
524 {
525 if bits < queue.bits {
526 queue.value %= N::ONE << (queue.bits - bits);
527 queue.bits -= bits;
528 } else {
529 queue.value = N::default();
530 queue.bits = 0;
531 }
532 }
533
534 #[inline]
535 fn next_zeros<N>(queue: &BitQueue<Self, N>) -> u32
536 where
537 N: Numeric,
538 {
539 queue.value.leading_zeros() - (N::BITS_SIZE - queue.bits)
540 }
541
542 #[inline]
543 fn next_ones<N>(queue: &BitQueue<Self, N>) -> u32
544 where
545 N: Numeric,
546 {
547 if queue.bits < N::BITS_SIZE {
548 (queue.value ^ ((N::ONE << queue.bits) - N::ONE)).leading_zeros()
549 - (N::BITS_SIZE - queue.bits)
550 } else {
551 (!queue.value).leading_zeros()
552 }
553 }
554
555 fn read_signed<R, S>(r: &mut R, bits: u32) -> io::Result<S>
556 where
557 R: BitRead,
558 S: SignedNumeric,
559 {
560 let is_negative = r.read_bit()?;
561 let unsigned = r.read::<S>(bits - 1)?;
562 Ok(if is_negative {
563 unsigned.as_negative(bits)
564 } else {
565 unsigned
566 })
567 }
568
569 fn read_signed_fixed<R, const B: u32, S>(r: &mut R) -> io::Result<S>
570 where
571 R: BitRead,
572 S: SignedNumeric,
573 {
574 let is_negative = r.read_bit()?;
575 let unsigned = r.read::<S>(B - 1)?;
576 Ok(if is_negative {
577 unsigned.as_negative_fixed::<B>()
578 } else {
579 unsigned
580 })
581 }
582
583 fn write_signed<W, S>(w: &mut W, bits: u32, value: S) -> io::Result<()>
584 where
585 W: BitWrite,
586 S: SignedNumeric,
587 {
588 if bits == S::BITS_SIZE {
589 w.write_bytes(value.to_be_bytes().as_ref())
590 } else if value.is_negative() {
591 w.write_bit(true)
592 .and_then(|()| w.write(bits - 1, value.as_unsigned(bits)))
593 } else {
594 w.write_bit(false).and_then(|()| w.write(bits - 1, value))
595 }
596 }
597
598 fn write_signed_fixed<W, const B: u32, S>(w: &mut W, value: S) -> io::Result<()>
599 where
600 W: BitWrite,
601 S: SignedNumeric,
602 {
603 if B == S::BITS_SIZE {
604 w.write_bytes(value.to_be_bytes().as_ref())
605 } else if value.is_negative() {
606 w.write_bit(true)
607 .and_then(|()| w.write(B - 1, value.as_unsigned(B)))
608 } else {
609 w.write_bit(false).and_then(|()| w.write(B - 1, value))
610 }
611 }
612
613 #[inline]
614 fn read_primitive<R, V>(r: &mut R) -> io::Result<V>
615 where
616 R: BitRead,
617 V: Primitive,
618 {
619 let mut buffer = V::buffer();
620 r.read_bytes(buffer.as_mut())?;
621 Ok(V::from_be_bytes(buffer))
622 }
623
624 #[inline]
625 fn write_primitive<W, V>(w: &mut W, value: V) -> io::Result<()>
626 where
627 W: BitWrite,
628 V: Primitive,
629 {
630 w.write_bytes(value.to_be_bytes().as_ref())
631 }
632
633 #[inline]
634 fn read_numeric<R, V>(mut r: R) -> io::Result<V>
635 where
636 R: io::Read,
637 V: Primitive,
638 {
639 let mut buffer = V::buffer();
640 r.read_exact(buffer.as_mut())?;
641 Ok(V::from_be_bytes(buffer))
642 }
643
644 #[inline]
645 fn write_numeric<W, V>(mut w: W, value: V) -> io::Result<()>
646 where
647 W: io::Write,
648 V: Primitive,
649 {
650 w.write_all(value.to_be_bytes().as_ref())
651 }
652}
653
654/// Little-endian, or least significant bits first
655#[derive(Copy, Clone, Debug)]
656pub struct LittleEndian;
657
658/// Little-endian, or least significant bits first
659pub type LE = LittleEndian;
660
661impl Endianness for LittleEndian {
662 #[inline]
663 fn push<N>(queue: &mut BitQueue<Self, N>, bits: u32, mut value: N)
664 where
665 N: Numeric,
666 {
667 if !value.is_zero() {
668 value <<= queue.bits;
669 queue.value |= value;
670 }
671 queue.bits += bits;
672 }
673
674 #[inline]
675 fn push_fixed<const B: u32, N>(queue: &mut BitQueue<Self, N>, mut value: N)
676 where
677 N: Numeric,
678 {
679 if !value.is_zero() {
680 value <<= queue.bits;
681 queue.value |= value;
682 }
683 queue.bits += B;
684 }
685
686 #[inline]
687 fn pop<N>(queue: &mut BitQueue<Self, N>, bits: u32) -> N
688 where
689 N: Numeric,
690 {
691 if bits < queue.bits {
692 let to_return = queue.value % (N::ONE << bits);
693 queue.value >>= bits;
694 queue.bits -= bits;
695 to_return
696 } else {
697 let to_return = queue.value;
698 queue.value = N::default();
699 queue.bits = 0;
700 to_return
701 }
702 }
703
704 fn pop_fixed<const B: u32, N>(queue: &mut BitQueue<Self, N>) -> N
705 where
706 N: Numeric,
707 {
708 if B < queue.bits {
709 let to_return = queue.value % (N::ONE << B);
710 queue.value >>= B;
711 queue.bits -= B;
712 to_return
713 } else {
714 let to_return = queue.value;
715 queue.value = N::default();
716 queue.bits = 0;
717 to_return
718 }
719 }
720
721 #[inline]
722 fn drop<N>(queue: &mut BitQueue<Self, N>, bits: u32)
723 where
724 N: Numeric,
725 {
726 if bits < queue.bits {
727 queue.value >>= bits;
728 queue.bits -= bits;
729 } else {
730 queue.value = N::default();
731 queue.bits = 0;
732 }
733 }
734
735 #[inline(always)]
736 fn next_zeros<N>(queue: &BitQueue<Self, N>) -> u32
737 where
738 N: Numeric,
739 {
740 queue.value.trailing_zeros()
741 }
742
743 #[inline]
744 fn next_ones<N>(queue: &BitQueue<Self, N>) -> u32
745 where
746 N: Numeric,
747 {
748 (queue.value ^ !N::default()).trailing_zeros()
749 }
750
751 fn read_signed<R, S>(r: &mut R, bits: u32) -> io::Result<S>
752 where
753 R: BitRead,
754 S: SignedNumeric,
755 {
756 let unsigned = r.read::<S>(bits - 1)?;
757 let is_negative = r.read_bit()?;
758 Ok(if is_negative {
759 unsigned.as_negative(bits)
760 } else {
761 unsigned
762 })
763 }
764
765 fn read_signed_fixed<R, const B: u32, S>(r: &mut R) -> io::Result<S>
766 where
767 R: BitRead,
768 S: SignedNumeric,
769 {
770 let unsigned = r.read::<S>(B - 1)?;
771 let is_negative = r.read_bit()?;
772 Ok(if is_negative {
773 unsigned.as_negative_fixed::<B>()
774 } else {
775 unsigned
776 })
777 }
778
779 fn write_signed<W, S>(w: &mut W, bits: u32, value: S) -> io::Result<()>
780 where
781 W: BitWrite,
782 S: SignedNumeric,
783 {
784 if bits == S::BITS_SIZE {
785 w.write_bytes(value.to_le_bytes().as_ref())
786 } else if value.is_negative() {
787 w.write(bits - 1, value.as_unsigned(bits))
788 .and_then(|()| w.write_bit(true))
789 } else {
790 w.write(bits - 1, value).and_then(|()| w.write_bit(false))
791 }
792 }
793
794 fn write_signed_fixed<W, const B: u32, S>(w: &mut W, value: S) -> io::Result<()>
795 where
796 W: BitWrite,
797 S: SignedNumeric,
798 {
799 if B == S::BITS_SIZE {
800 w.write_bytes(value.to_le_bytes().as_ref())
801 } else if value.is_negative() {
802 w.write(B - 1, value.as_unsigned_fixed::<B>())
803 .and_then(|()| w.write_bit(true))
804 } else {
805 w.write(B - 1, value).and_then(|()| w.write_bit(false))
806 }
807 }
808
809 #[inline]
810 fn read_primitive<R, V>(r: &mut R) -> io::Result<V>
811 where
812 R: BitRead,
813 V: Primitive,
814 {
815 let mut buffer = V::buffer();
816 r.read_bytes(buffer.as_mut())?;
817 Ok(V::from_le_bytes(buffer))
818 }
819
820 #[inline]
821 fn write_primitive<W, V>(w: &mut W, value: V) -> io::Result<()>
822 where
823 W: BitWrite,
824 V: Primitive,
825 {
826 w.write_bytes(value.to_le_bytes().as_ref())
827 }
828
829 fn read_numeric<R, V>(mut r: R) -> io::Result<V>
830 where
831 R: io::Read,
832 V: Primitive,
833 {
834 let mut buffer = V::buffer();
835 r.read_exact(buffer.as_mut())?;
836 Ok(V::from_le_bytes(buffer))
837 }
838
839 #[inline]
840 fn write_numeric<W, V>(mut w: W, value: V) -> io::Result<()>
841 where
842 W: io::Write,
843 V: Primitive,
844 {
845 w.write_all(value.to_le_bytes().as_ref())
846 }
847}
848
849/// A queue for efficiently pushing bits onto a value
850/// and popping them off a value.
851#[derive(Clone, Debug, Default)]
852pub struct BitQueue<E: Endianness, N: Numeric> {
853 phantom: PhantomData<E>,
854 value: N,
855 bits: u32,
856}
857
858impl<E: Endianness, N: Numeric> BitQueue<E, N> {
859 /// Returns a new empty queue
860 #[inline]
861 pub fn new() -> BitQueue<E, N> {
862 BitQueue {
863 phantom: PhantomData,
864 value: N::default(),
865 bits: 0,
866 }
867 }
868
869 /// Creates a new queue from the given value with the given size
870 /// Panics if the value is larger than the given number of bits.
871 #[inline]
872 pub fn from_value(value: N, bits: u32) -> BitQueue<E, N> {
873 assert!(if bits < N::BITS_SIZE {
874 value < (N::ONE << bits)
875 } else {
876 bits <= N::BITS_SIZE
877 });
878 BitQueue {
879 phantom: PhantomData,
880 value,
881 bits,
882 }
883 }
884
885 /// Sets the queue to a given value with the given number of bits
886 /// Panics if the value is larger than the given number of bits
887 #[inline]
888 pub fn set(&mut self, value: N, bits: u32) {
889 assert!(if bits < N::BITS_SIZE {
890 value < (N::ONE << bits)
891 } else {
892 bits <= N::BITS_SIZE
893 });
894 self.value = value;
895 self.bits = bits;
896 }
897
898 /// Consumes the queue and returns its current value
899 #[inline(always)]
900 pub fn value(self) -> N {
901 self.value
902 }
903
904 /// Returns the total bits in the queue
905 #[inline(always)]
906 pub fn len(&self) -> u32 {
907 self.bits
908 }
909
910 /// Returns the maximum bits the queue can hold
911 #[inline(always)]
912 pub fn max_len(&self) -> u32 {
913 N::BITS_SIZE
914 }
915
916 /// Returns the remaining bits the queue can hold
917 #[inline(always)]
918 pub fn remaining_len(&self) -> u32 {
919 self.max_len() - self.len()
920 }
921
922 /// Returns true if the queue is empty
923 #[inline(always)]
924 pub fn is_empty(&self) -> bool {
925 self.bits == 0
926 }
927
928 /// Returns true if the queue is full
929 #[inline(always)]
930 pub fn is_full(&self) -> bool {
931 self.bits == N::BITS_SIZE
932 }
933
934 /// Drops all values in the queue
935 #[inline(always)]
936 pub fn clear(&mut self) {
937 self.set(N::default(), 0)
938 }
939
940 /// Returns true if all bits remaining in the queue are 0
941 #[inline(always)]
942 pub fn all_0(&self) -> bool {
943 self.value.count_ones() == 0
944 }
945
946 /// Returns true if all bits remaining in the queue are 1
947 #[inline(always)]
948 pub fn all_1(&self) -> bool {
949 self.value.count_ones() == self.bits
950 }
951
952 /// Pushes a value with the given number of bits onto the tail of the queue
953 /// Panics if the number of bits pushed is larger than the queue can hold.
954 #[inline(always)]
955 pub fn push(&mut self, bits: u32, value: N) {
956 assert!(bits <= self.remaining_len()); // check for overflow
957 E::push(self, bits, value)
958 }
959
960 /// Pushes a value with the given number of bits onto the tail of the queue
961 /// Panics if the number of bits pushed is larger than the queue can hold.
962 #[inline(always)]
963 pub fn push_fixed<const B: u32>(&mut self, value: N) {
964 assert!(B <= self.remaining_len()); // check for overflow
965 E::push_fixed::<B, N>(self, value)
966 }
967
968 /// Pops a value with the given number of bits from the head of the queue
969 /// Panics if the number of bits popped is larger than the number
970 /// of bits in the queue.
971 #[inline(always)]
972 pub fn pop(&mut self, bits: u32) -> N {
973 assert!(bits <= self.len()); // check for underflow
974 E::pop(self, bits)
975 }
976
977 /// Pops a value with the given number of bits from the head of the queue
978 pub fn pop_fixed<const B: u32>(&mut self) -> N {
979 assert!(B <= self.len()); // check for underflow
980 E::pop_fixed::<B, N>(self)
981 }
982
983 /// Pops all the current bits from the queue
984 /// and resets it to an empty state.
985 #[inline]
986 pub fn pop_all(&mut self) -> N {
987 let to_return = self.value;
988 self.value = N::default();
989 self.bits = 0;
990 to_return
991 }
992
993 /// Drops the given number of bits from the head of the queue
994 /// without returning them.
995 /// Panics if the number of bits dropped is larger than the
996 /// number of bits in the queue.
997 #[inline(always)]
998 pub fn drop(&mut self, bits: u32) {
999 assert!(bits <= self.len()); // check for underflow
1000 E::drop(self, bits)
1001 }
1002
1003 /// Pops all 0 bits up to and including the next 1 bit
1004 /// and returns the amount of 0 bits popped
1005 #[inline]
1006 pub fn pop_0(&mut self) -> u32 {
1007 let zeros = E::next_zeros(self);
1008 self.drop(zeros + 1);
1009 zeros
1010 }
1011
1012 /// Pops all 1 bits up to and including the next 0 bit
1013 /// and returns the amount of 1 bits popped
1014 #[inline]
1015 pub fn pop_1(&mut self) -> u32 {
1016 let ones = E::next_ones(self);
1017 self.drop(ones + 1);
1018 ones
1019 }
1020}
1021
1022impl<E: Endianness> BitQueue<E, u8> {
1023 /// Returns the state of the queue as a single value
1024 /// which can be used to perform lookups.
1025 #[inline(always)]
1026 pub fn to_state(&self) -> usize {
1027 (1 << self.bits) | (self.value as usize)
1028 }
1029}
1030