- Feature Name: int128
- Start Date: 2016-02-21
- RFC PR: rust-lang/rfcs#1504
- Rust Issue: rust-lang/rust#35118
This RFC adds the
u128 primitive types to Rust.
Some algorithms need to work with very large numbers that don't fit in 64 bits, such as certain cryptographic algorithms. One possibility would be to use a BigNum library, but these use heap allocation and tend to have high overhead. LLVM has support for very efficient 128-bit integers, which are exposed by Clang in C as the
The first step for implementing this feature is to add support for the
u128 primitive types to the compiler. This will requires changes to many parts of the compiler, from libsyntax to trans.
The compiler will need to be bootstrapped from an older compiler which does not support
u128, but rustc will want to use these types internally for things like literal parsing and constant propagation. This can be solved by using a "software" implementation of these types, similar to the one in the extprim crate. Once stage1 is built, stage2 can be compiled using the native LLVM
The LLVM code generator supports 128-bit integers on all architectures, however it will lower some operations to runtime library calls. This similar to how we currently handle
i64 on 32-bit platforms: "complex" operations such as multiplication or division are lowered by LLVM backends into calls to functions in the
compiler-rt runtime library.
Here is a rough breakdown of which operations are handled natively instead of through a library call:
- Add/Sub/Neg: native, including checked overflow variants
- Compare (eq/ne/gt/ge/lt/le): native
- Bitwise and/or/xor/not: native
- Shift left/right: native on most architectures (some use libcalls instead)
- Bit counting, parity, leading/trailing ones/zeroes: native
- Byte swapping: native
- Mul/Div/Mod: libcall (including checked overflow multiplication)
- Conversion to/from f32/f64: libcall
compiler-rt library that comes with LLVM only implements runtime library functions for 128-bit integers on 64-bit platforms (
#ifdef __LP64__). We will need to provide our own implementations of the relevant functions to allow
u128 to be available on all architectures. Note that this can only be done with a compiler that already supports
u128 to match the calling convention that LLVM is expecting.
Here is the list of functions that need to be implemented:
fn __ashlti3(a: i128, b: i32) -> i128; fn __ashrti3(a: i128, b: i32) -> i128; fn __divti3(a: i128, b: i128) -> i128; fn __fixdfti(a: f64) -> i128; fn __fixsfti(a: f32) -> i128; fn __fixunsdfti(a: f64) -> u128; fn __fixunssfti(a: f32) -> u128; fn __floattidf(a: i128) -> f64; fn __floattisf(a: i128) -> f32; fn __floatuntidf(a: u128) -> f64; fn __floatuntisf(a: u128) -> f32; fn __lshrti3(a: i128, b: i32) -> i128; fn __modti3(a: i128, b: i128) -> i128; fn __muloti4(a: i128, b: i128, overflow: &mut i32) -> i128; fn __multi3(a: i128, b: i128) -> i128; fn __udivti3(a: u128, b: u128) -> u128; fn __umodti3(a: u128, b: u128) -> u128;
Implementations of these functions will be written in Rust and will be included in libcore. Note that it is not possible to write these functions in C or use the existing implementations in
compiler-rt since the
__int128 type is not available in C on 32-bit platforms.
Several changes need to be done to libcore:
src/libcore/num/mod.rs: Implement inherent methods,
src/libcore/num/wrapping.rs: Implement methods for
src/libcore/lib.rs: Add the
A few minor changes are required in libstd:
src/libstd/primitive_docs.rs: Add documentation for
A few external crates will need to be updated to support the new types:
rustc-serialize: Add the ability to serialize
serde: Add the ability to serialize
rand: Add the ability to generate random
There have been several attempts to create
i128 wrappers based on two
u64 values, but these can't match the performance of LLVM's native 128-bit integers. For example LLVM is able to lower a 128-bit add into just 2 instructions on 64-bit platforms and 4 instructions on 32-bit platforms.