ApInt - Arbitrary Precision Integer

| Linux | Windows | Codecov | Coveralls | Docs | Crates.io | |:-------------------:|:-------------------:|:--------------------:|:--------------------:|:----------------:|:--------------------:| | | | | | | |

Development in progress: The implementation has not been finished and may not work.

Arbitrary precision Integers (ApInt) represent integers that have an arbitrary but fixed runtime bit-width and offers two's complement modulo arithmetic equal to machine integers.

The integer types offered by this library are:

• ApInt: A low-level arbitrary-precision integer without static signedness information. (General)
• Int: A signed arbitrary-precision integer. (Convenience for iN.)
• UInt: An unsigned arbitrary-precision integer. (Convenience for uN.)

The API is based on the LLVM APInt support library.

Example Use Cases

• Emulate machine arithmetic on compilation, e.g. for constant evaluation and some optimizations.
• SMT solvers may use this as an underlying model for the theory of bitvectors.
• Operations and backend for cryptographic keys.
• Also usable as a simple bitset with runtime length information.

Internals

The design focus is at efficiency and robustness. ApInt instances are small-value-optimized. This means that only ApInt instances with a bit-width larger than 64 bits allocate dynamic memory.

An ApInt constists of a sequence of 64-bit Digits. Computations are done within their 128-bit DoubleDigit form to prevent bit-loss on over- or underflows. This implies a dependency on 128-bit integers which are currently unstable in Rust.

Differences & Parallels

The below table lists public and internal differences between ApInt and num::BigInt.

| Topic | num::BigInt | ApInt | |:------------------------:|:------------------------------------------|:----------------------------------------| | Abstraction | High-level unbounded integers. | Twos-complement machine integers. | | Behaviour | Behaves like an immutable type most often. This results in lots of copies and better usability. | API design with a focus on efficient operations and machine emulation. | | Small Value Optimization | No | Yes: Up to 64-bits. | | Building Blocks | 32-bit BigDigit aka u32 | 64-bit Digit | | Compute Unit | 64-bit DoubleBigDigit aka u64 | 128-bit DoubleDigit | | Signed | Yes: num::BigUint is for unsigned. | No: Operations know signedness instead. | | mem::size_of<..> | About 24 bytes + some signedness info. | Exactly 128 bits (16 bytes). | | Width interoperability | No restriction to operate between BigInt instances with different bit-widths. | Only ApInt instances with the same bit-width can interoperate. | | Memory footprint | Determined by current value stored. | Determined by bit-width. | | Can grow and shrink? | Yes | No, see above. | | Unstable features? | None | Stable as of Rust 1.26. |

Current State

Currently only a few parts of the implementation are done - especially the implementation of ApInt's with bit-widths greater than 64 bits is incomplete.

State of the API modules implemented so far:

| Module | Design | Implementation | Testing | TODO | |:-------------------:|:------:|:--------------:|:-------:|:----:| | arithmetic | done | unfinished | unfinished | | | constructors | done | done | done | | | casting | done | done | not started | issue #4 | | bitwise | done | done | not started | | | shift | done | done | done | | | relational | done | done | not started | | | utils | done | done | not started | | | serialization | done | unfinished | unfinished | depends on arithmetic | | to_primitive | done | done | done | | | serde_impl (opt.) | done | done | done | | | rand_impl (opt.) | done | done | done | |

Planned Features

• Full and efficient ApInt implementation and decent test coverage.
• Mid-level ApsInt wrapper around ApInt that stores a run-time sign information. This is different from Int and UInt since those types store their sign immutable in their type. This is the same as LLVM's APSInt data type.

License

Licensed under either of

• Apache License, Version 2.0, (LICENSE-APACHE or http://www.apache.org/licenses/LICENSE-2.0)
• MIT license (LICENSE-MIT or http://opensource.org/licenses/MIT)

at your option.

Dual licence:

Contribution

Unless you explicitly state otherwise, any contribution intentionally submitted for inclusion in the work by you, as defined in the Apache-2.0 license, shall be dual licensed as above, without any additional terms or conditions.

Release Notes

Version 0.2.0 - 2018-05-16

• Add Binary, LowerHex and UpperHex impls to Int, UInt and ApInt.
  Note that implementations for Octal are still missing.

Version 0.1.0 - 2018-04-15

• Removed strict casting methods in ApInt, Int and UInt.
• Add into_bitnot to ApInt, Int and UInt.
• Add division-by-zero error and managing around it for respective operations.
• Add a crate prelude module for simple usage of commonly used types.
• Fixed bug in ApInt::sign_extend and Int::extend (issue #15). Thanks AaronKutch for reporting!
• Fixed markdown headers of many public impl blocks.
• Fixed several documentation comments of public APIs, like ApInt::from_{i128, u128}.
• Fixed several minor bugs due to forwarding to wrong implementation methods.