Summary

This RFC adds the i128 and u128 primitive types to Rust.

Motivation

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 __int128 type.

Detailed design

Compiler support

The first step for implementing this feature is to add support for the i128/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 i128/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 i128/u128 types.

Runtime library support

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 u64 and 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

The 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 i128/u128 to be available on all architectures. Note that this can only be done with a compiler that already supports i128/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.

Modifications to libcore

Several changes need to be done to libcore:

  • src/libcore/num/i128.rs: Define MIN and MAX.
  • src/libcore/num/u128.rs: Define MIN and MAX.
  • src/libcore/num/mod.rs: Implement inherent methods, Zero, One, From and FromStr for u128 and i128.
  • src/libcore/num/wrapping.rs: Implement methods for Wrapping<u128> and Wrapping<i128>.
  • src/libcore/fmt/num.rs: Implement Binary, Octal, LowerHex, UpperHex, Debug and Display for u128 and i128.
  • src/libcore/cmp.rs: Implement Eq, PartialEq, Ord and PartialOrd for u128 and i128.
  • src/libcore/nonzero.rs: Implement Zeroable for u128 and i128.
  • src/libcore/iter.rs: Implement Step for u128 and i128.
  • src/libcore/clone.rs: Implement Clone for u128 and i128.
  • src/libcore/default.rs: Implement Default for u128 and i128.
  • src/libcore/hash/mod.rs: Implement Hash for u128 and i128 and add write_i128 and write_u128 to Hasher.
  • src/libcore/lib.rs: Add the u128 and i128 modules.

Modifications to libstd

A few minor changes are required in libstd:

  • src/libstd/lib.rs: Re-export core::{i128, u128}.
  • src/libstd/primitive_docs.rs: Add documentation for i128 and u128.

Modifications to other crates

A few external crates will need to be updated to support the new types:

  • rustc-serialize: Add the ability to serialize i128 and u128.
  • serde: Add the ability to serialize i128 and u128.
  • rand: Add the ability to generate random i128s and u128s.

Drawbacks

One possible issue is that a u128 can hold a very large number that doesn’t fit in a f32. We need to make sure this doesn’t lead to any undefs from LLVM. See this comment, and this example code.

Alternatives

There have been several attempts to create u128/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.

Unresolved questions

None