1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126

//! Crate for manipulating bit vectors and doing arithmetic on arbitrarily sized bit vectors.
//!
//! This crate emphasizes optimizing storage by providing alternative storage options.
//! The module [`fixed`] contains implementations using unsigned integers as storage and thus
//! has a fixed capacity. The module [`dynamic`] contains an implementation using dynamically
//! allocated array of integers as storage and therefore has a dynamic capacity. The module
//! [`auto`] contains an implementation capable of switching at runtime between a fixed or
//! dynamic capacity implementation to try to minimize dynamic memory allocations.
//! All of those implementations implement the [`BitVector`] trait and can be freely mixed together
//! and converted into each other.
//!
//! The different bit vector types represent a vector of bits where the bit at index 0 is the least
//! significant bit and the bit at index `.len() - 1` is the most significant bit. There is no
//! notion of endianness for the bit vector themselves, endianness is only involved when reading or
//! writing a bit vector to or from memory or storage.
//!
//! Arithmetic operation can be applied to bit vectors of different length. The result will always
//! have the length of the longest operand and the smallest operand will be zero extended for the
//! operation. This should match the most intuitive behavior in most cases except when manipulating
//! bit vector supposed to have a sign bit.

use std::fmt::{Binary, Display, Debug, LowerHex, UpperHex};
use std::io::{Read, Write};
use std::ops::Range;

pub mod bit;
pub mod fixed;
pub mod dynamic;
pub mod auto;

use bit::Bit;

/// A enumeration representing the endianness of an I/O or memory operation.
pub enum Endianness {
    /// Little Endian ordering: bytes are stored from the least significant byte to the most significant byte.
    LE,
    /// big Endian ordering: bytes are stored from the most significant byte to the least significant byte.
    BE
}

/// A trait representing common bit vector operations.
pub trait BitVector: Sized + Clone + Debug + PartialEq + Eq + Display + Binary + LowerHex + UpperHex {
    /// Construct a bit vector made of `length` 0 bits.
    /// Will panic if there is not enough capacity and it is a fixed variant.
    fn zeros(length: usize) -> Self;

    /// Construct a bit vector made of `length` 1 bits.
    /// Will panic if there is not enough capacity and it is a fixed variant.
    fn ones(length: usize) -> Self;

    /// Construct a bit vector from a binary string made of `'0'` and `'1'`.
    /// Return `None` if the string is invalid or exceed the maximum capacity.
    fn from_binary<S: AsRef<str>>(string: S) -> Option<Self>;

    /// Construct a bit vector from a hex string made of lower case or upper case hexadecimal 
    /// characters (mixed case is accepted).
    /// Return `None` if the string is invalid or exceed the maximum capacity.
    fn from_hex<S: AsRef<str>>(string: S) -> Option<Self>;

    /// Construct a bit vector from `bytes` according to the specified `endianness`.
    /// Will panic if the length of `bytes` is larger than the maximum capacity.
    fn from_bytes<B: AsRef<[u8]>>(bytes: B, endianness: Endianness) -> Self;

    /// Construct a new vector of bytes from the bit vector according to the specified `endianness`.
    /// If the length is not a multiple of 8 bits, he highest weight bits will be padded with `'0'`.
    fn to_vec(&self, endianness: Endianness) -> Vec<u8>;

    /// Construct a bit vector by reading `length` bits from a type implementing `Read` and 
    /// arrange them according to the specified `endianness`. If `length` is not a multiple of 8,
    /// the bits remaining in the most signigicant byte will be dropped.
    /// Will panic if there is not enough capacity and it is a fixed variant.
    fn read<R: Read>(reader: &mut R, length: usize, endianness: Endianness) -> std::io::Result<Self>;

    /// Write the bit vector to a type implementing `Write` and according to the specified 
    /// `endianness`. If the length is not a multiple of 8 bits, the most significant byte will be 
    /// padded with `'0'`.
    fn write<W: Write>(&self, writer: &mut W, endianness: Endianness) -> std::io::Result<()>;

    /// Return the bit at `index`.
    /// Will panic if `index` is out of bound.
    fn get(&self, index: usize) -> Bit;

    /// Set the bit at `index`.
    /// Will panic if `index` is out of bound.
    fn set(&mut self, index: usize, bit: Bit);

    /// Slice the bit vector using the specified range and copy those bits in a new bit vector.
    /// Will panic if `range` start or end are out of bound.
    fn copy_slice(&self, range: Range<usize>) -> Self;

    /// Push a bit at the end of the bit vector as the most significant bit.
    /// Will panic if there is not enough capacity and it is a fixed variant.
    fn push(&mut self, bit: Bit);

    /// Pop a bit from the end of the bit vector.
    /// Return None if the bit vector is empty.
    fn pop(&mut self) -> Option<Bit>;

    /// Resize the bit vector in place so that its length is equal to `new_length`.
    /// This will either truncate or extend the bit vector. If it is extended, new bits are filled 
    /// with `bit`.
    /// Will panic if there is not enough capacity and it is a fixed variant.
    fn resize(&mut self, new_length: usize, bit: Bit);

    /// Shift the bits by one to the left.
    /// The rightmost bit is set to `bit` and the leftmost bit is returned.
    fn shl_in(&mut self, bit: Bit) -> Bit;

    /// Shift the bits by one to the right.
    /// The leftmost bit is set to `bit` and the rightmost bit is returned.
    fn shr_in(&mut self, bit: Bit) -> Bit;

    // Rotate the bits to the left by `rot` positions.
    // Will panic if the rotation amount is larger than this bit vector length.
    fn rotl(&mut self, rot: usize);

    // Rotate the bits to the right by `rot` positions.
    // Will panic if the rotation amount is larger than this bit vector length.
    fn rotr(&mut self, rot: usize);

    /// Return the length of the bit vector in bits.
    fn len(&self) -> usize;
}

#[cfg(test)]
mod tests;