### 5 releases (3 breaking)

0.4.0 | Aug 17, 2024 |
---|---|

0.3.0 | Jul 7, 2024 |

0.2.0 | Jul 4, 2023 |

0.1.1 | Dec 27, 2020 |

0.1.0 | Dec 20, 2020 |

#**69** in Math

**MIT**license

270KB

7K
SLoC

# bva

This crate is for manipulating and doing arithmetics on bit vectors of fixed but arbitrary size. They are meant to behave like CPU hardware registers with wrap-around on overflow.

This crate provides multiple implementations relying on different memory management strategies.

- The

implementation uses statically sized arrays of unsigned integers as storage and thus has a fixed capacity but does not require dynamic memory allocation.`Bvf` - The

implementation uses a dynamically allocated array of integers as storage and therefore has a dynamic capacity and support resizing operations.`Bvd` - The

implementation is capable of switching at runtime between the`Bv`

and`Bvf`

implementations to try to minimize dynamic memory allocations whenever possible.`Bvd`

All of those implementations implement the

trait and can be freely mixed together
and abstracted through generic traits.`BitVector`

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

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 from or to memory.`.``len``(``)` `-` `1`

Arithmetic operation can be applied to bit vectors of different types and different lengths. The result will always have the type and the length of the left hand side operand. The right hand side operand will be zero extended if needed. Operations will wrap-around in the case of overflows. This should match the behavior of unsigned integer arithmetics on CPU registers.

## Examples

Bit vectors expose an API similar to Rust

:`std ::`

`collections`Vec

`::``use` `bva``::``{`Bit`,` BitVector`,` Bvd`}``;`
`let` `mut` bv `=` `Bvd``::`with_capacity`(``128``)``;`
`assert_eq!``(`bv`.``capacity``(``)``,` `128``)``;`
bv`.``push``(``Bit``::`One`)``;`
bv`.``push``(``Bit``::`One`)``;`
bv`.``resize``(``16``,` `Bit``::`Zero`)``;`
`assert_eq!``(`bv`.``len``(``)``,` `16``)``;`
`assert_eq!``(`bv`.``first``(``)``,` `Some``(``Bit``::`One`)``)``;`
`assert_eq!``(`bv`.``last``(``)``,` `Some``(``Bit``::`Zero`)``)``;`
`let` pop_count `=` bv`.``iter``(``)``.``fold``(``0``u32``,` `|``acc``,` `b``|` `acc ``+` `u32``::`from`(`b`)``)``;`
`assert_eq!``(`pop_count`,` `2``)``;`

Additionally, bit vector specific operations are available:

`use` `bva``::``{`Bit`,` BitVector`,` Bv32`}``;`
`//` While Bv32 has a capacity of 32 bits, it inherits the length of the u8.
`let` `mut` a `=` `Bv32``::`try_from`(``0b111``u8``)``.``unwrap``(``)``;`
a`.``rotr``(``2``)``;`
`assert_eq!``(`a`,` `Bv32``::`try_from`(``0b11000001``u8``)``.``unwrap``(``)``)``;`
`assert_eq!``(`a`.``get``(``7``)``,` `Bit``::`One`)``;`
a`.``set``(``1``,` `Bit``::`One`)``;`
`assert_eq!``(`a`,` `Bv32``::`try_from`(``0b11000011``u8``)``.``unwrap``(``)``)``;`
`assert_eq!``(`a`.``copy_range``(``1``..``7``)``,` `Bv32``::`try_from`(``0b100001``u8``)``.``unwrap``(``)``)``;`

Bit vectors behave like unsigned integers with wrap-around on overflow:

`use` `bva``::``{`Bit`,` BitVector`,` Bv32`}``;`
`//` Bv32 is a type alias for a Bvf with 32 bits of capacity.
`let` a `=` `Bv32``::`ones`(``32``)``;`
`let` b `=` `Bv32``::`try_from`(``1``u32``)``.``unwrap``(``)``;`
`assert_eq!``(`b`.``leading_zeros``(``)``,` `31``)``;`
`let` c `=` a `+` b`;`
`assert_eq!``(`c`,` `Bv32``::`zeros`(``32``)``)``;`

Generic traits can be used to abstract over the different bit vector implementations:

`use` `core``::``ops``::`AddAssign`;`
`use` `bva``::``{`Bit`,` BitVector`,` Bv`,` Bvd`,` Bvf`}``;`
`fn` `fibonnaci``<`B`:` BitVector `+` for`<``'a``>` AddAssign`<``&``'a` B`>``>``(``n``:` `usize``)`` ``->` B `{`
`let` `mut` f0 `=` `B``::`zeros`(``1``)``;`
`let` `mut` f1 `=` `B``::`ones`(``1``)``;`
`if` n `==` `0` `{`
`return` f0`;`
`}`
`for` `_` `in` `1``..`n `{`
`//` Avoid overflow
f0`.``resize``(`f1`.``significant_bits``(``)` `+` `1``,` `Bit``::`Zero`)``;`
`//` Addition is done in place
f0 `+=` `&`f1`;`
`//` Swap f0 and f1
`std``::``mem``::`swap`(``&``mut` f0`,` `&``mut` f1`)``;`
`}`
`return` f1`;`
`}`
`assert_eq!``(``fibonnaci``::``<`Bvf`<``u8`, 2`>``>``(``15``)``,` `Bvf``::``<``u8`, 2`>``::`try_from`(``610``u16``)``.``unwrap``(``)``)``;`
`assert_eq!``(``fibonnaci``::``<`Bvd`>``(``18``)``,` `Bvd``::`from`(``2584``u32``)``)``;`
`assert_eq!``(``fibonnaci``::``<`Bv`>``(``19``)``,` `Bv``::`from`(``4181``u32``)``)``;`

## Changelog

- 2024/08/18 - 0.4.0
- 100% function test coverage, 98% line test coverage
- Some bug were fixed in the process

- Better API and proper documentation
- extend, append, prepend, repeat, first, last and sign_extend functions
- Constructing bit vectors from array of integers
- Operation with unsigned integers as right hand side

- 100% function test coverage, 98% line test coverage
- 2024/07/07 - 0.3.0
- Multiplication, division and modulo operations
- Various helper functions
- Much more rigorous testing reaching high code coverage.

- 2023/07/04 - 0.2.0
- Major rewrite using const generics
- Iterator support

- 2020/12/20 - 0.1.0
- BitVector trait with fixed, dynamic and auto implementations.
- Conversion between all the implementations
- Basic arithmetic operations between the different implementations.
- Reading and writing bit vector in various format.

## Roadmap

- no-std support
- More convenience BitVector functions
- Signed operation support.
- Borrowing of bits and bit slice inside a bit vector.
- Numerical algorithms such as gcd, modular exponentiation, ...

## Why

None of the existing crate really satisfied me and I wanted an implementation capable of minimizing dynamic memory allocations by automatically switching to fixed storage. I also wanted a crate that was capable of doing arithmetics on arbitrarily sized bit vectors, not just powers of two. Also it was great practice for my rust macro writing skills.