commit	757c347bd919c4584650d46d4286a6e6e863c44a	[log] [tgz]
author	Xin Li <delphij@google.com>	Sat Feb 20 00:24:02 2021 -0800
committer	Xin Li <delphij@google.com>	Sat Feb 20 00:24:02 2021 -0800
tree	9e71b2fb2df83e4bfd8abbc2bfa56c2a09d0118e
parent	59a9ff3c6f2a7fb2740120751b6d42bc9b51e3f9 [diff]
parent	4a39f58be5985e2ebb30f50d0f273b92573281a3 [diff]

tree: 9e71b2fb2df83e4bfd8abbc2bfa56c2a09d0118e

README.md

FXdiv

Header-only library for division via fixed-point multiplication by inverse

On modern CPUs and GPUs integer division is several times slower than multiplication. FXdiv implements an algorithm to replace an integer division with a multiplication and two shifts. This algorithm improves performance when an application performs repeated divisions by the same divisor.

Features

Integer division for uint32_t, uint64_t, and size_t
Header-only library, no installation or build required
Compatible with C99, C++, OpenCL, and CUDA
Uses platform-specific compiler intrinsics for optimal performance
Covered with unit tests and microbenchmarks

Example

#include <fxdiv.h>

/* Division of array by a constant: reference implementation */
void divide_array_c(size_t length, uint32_t array[], uint32_t divisor) {
  for (size_t i = 0; i < length; i++) {
    array[i] /= divisor;
  }
}

/* Division of array by a constant: implementation with FXdiv */
void divide_array_fxdiv(size_t length, uint32_t array[], uint32_t divisor) {
  const struct fxdiv_divisor_uint32_t precomputed_divisor =
    fxdiv_init_uint32_t(divisor);
  for (size_t i = 0; i < length; i++) {
    array[i] = fxdiv_quotient_uint32_t(array[i], precomputed_divisor);
  }
}

Status

Currently working features:

Platform	uint32_t	uint64_t	size_t
x86-64 gcc	Works	Works	Works
x86-64 clang	Works	Works	Works
x86-64 MSVC	Works	Works	Works
x86 gcc	Works	Works	Works
x86 clang	Works	Works	Works
x86 MSVC	Works	Works	Works
ARMv7 gcc	Works	Works	Works
ARMv7 clang	Works	Works	Works
ARMv7 MSVC*	Compiles	Compiles	Compiles
ARM64 gcc	Works	Works	Works
ARM64 clang	Works	Works	Works
ARM64 MSVC*	Compiles	Compiles	Compiles
PPC64 gcc	Works	Works	Works
WAsm clang	Works	Works	Works
Asm.js clang	Works	Works	Works
PNaCl clang	Works	Works	Works
CUDA	Untested	Untested	Untested
OpenCL	Untested	Untested	Untested

*ARMv7 and ARM64 builds with MSVC are presumed to work, but were only verified to compile successfully

References

Granlund, Torbjörn, and Peter L. Montgomery. “Division by invariant integers using multiplication.” In ACM SIGPLAN Notices, vol. 29, no. 6, pp. 61-72. ACM, 1994. Available: gmplib.org/~tege/divcnst-pldi94.pdf