Lib.rs

› Data structures
#precision #integer #int #integer-arithmetic #math #arbitrary #bit-set

apint

Arbitrary precision integers library

by Robbepop and 2 contributors

7 releases

Uses old Rust 2015

0.2.0 May 16, 2018
0.1.0 Apr 15, 2018
0.0.5 Mar 3, 2018
0.0.1 Feb 7, 2018
0.0.0-alpha.6 Dec 23, 2017

#1551 in Data structures

Download history 126/week @ 2024-03-11 85/week @ 2024-03-18 36/week @ 2024-03-25 244/week @ 2024-04-01 73/week @ 2024-04-08 23/week @ 2024-04-15 37/week @ 2024-04-22 73/week @ 2024-04-29 72/week @ 2024-05-06 71/week @ 2024-05-13 3/week @ 2024-05-20 60/week @ 2024-05-27 39/week @ 2024-06-03 126/week @ 2024-06-10 138/week @ 2024-06-17 46/week @ 2024-06-24

351 downloads per month
Used in 2 crates (via pliron)

MIT/Apache

325KB
7K SLoC

ApInt - Arbitrary Precision Integer

Linux Windows Codecov Coveralls Docs Crates.io
travisCI appveyor codecov coveralls docs crates

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

at your option.

Dual licence: badge badge

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.

Dependencies

~120–560KB