commit	525f49f7aeed6982af3c942b275265406b483fa1	[log] [tgz]
author	Android Build Coastguard Worker <[email protected]>	Fri Jul 07 04:54:12 2023 +0000
committer	Android Build Coastguard Worker <[email protected]>	Fri Jul 07 04:54:12 2023 +0000
tree	b0d778382e65123821d6af73cf53d38d94ecdd68
parent	19bea87b0d522149c42a7e3b842fdbccc71983e8 [diff]
parent	a555e78cea9d472dc5c3dfe6a1cb2f0979d93864 [diff]

tree: b0d778382e65123821d6af73cf53d38d94ecdd68

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