introduction

fp256 is an efficient library implemented in C and assembly for 256 bit integer arithmetic.

It supports Windows, Linux and Macosx on x86_64 and arm64 processor, and can be compiled with MSVC, mingw-w64, gcc and clang.

implementation

• Use 4×64bit to represent 256 bit integer.

• Leveled api :
  low level api operates directly on integer array, most low level api are specific for 256 bit integer, there are also a few api for arbitrary length array.
  high level api operates on 256 bit integer.

• Most low level arithmetic are implemented in assembly, including add, mul, u256 mul, div, shift, exgcd, mont mul, etc, they are very efficient and (maybe)well commented, see ll/x64, ll/aarch64 and ll/riscv64.

compilation

$ mkdir build
$ cd build
$ cmake ..
$ make -j
$ make test

Or cross compilation (cmake toolchain files are here):

$ mkdir build
$ cd build
$ cmake -DCMAKE_TOOLCHAIN_FILE=../cmake/toolchain/aarch64-linux-gcc.cmake ..
$ make -j

configuration

-DCMAKE_BUILD_TYPE : possible values are empty, Debug, Release, RelWithDebInfo and MinSizeRel, default is Release.
-DCMAKE_INSTALL_PREFIX : where to install fp256 library, default is /usr/local.
-DBUILD_STATIC : build static library, default is ON.
-DBUILD_SHARED : build shared library, default is ON.
-DUSE_DEV_RANDOM : use /dev/random to get random number, default is OFF(use /dev/urandom).
-DUSE_ASM : use assembly code, default is ON. it can not be turned off since some algorithms have no C implementation to fall back yet.
-DUSE_ASAN : use AddressSanitizer, default is OFF.

TODO

• Add prime test, modular exponential, square root related, etc.
• Constant-time implementation of division and exgcd.
• more tests.

benchmark

Some of benchmark results are listed below. Build and run build/bench/bench to get full result.

AMD Ryzen 5 4600U 2.1GHz, Ubuntu 20.04 LTS, gcc-9.3.0

arithmetic(256 bit)	cycles / op	op / s
naive div	428	4890000
gcd	3784	554000
mod add	330	6340000
mod sqr	491	4260000
mod mul	509	4110000
mod inv	4628	453000
mod exp	17000	123000
mont mul	130	16000000
mont sqr	117	17800000

license

Apache 2.0