NAME
fast_divide32,
fast_divide32_prepare,
fast_remainder32 —
fast 32bit division and
remainder
SYNOPSIS
#include
<sys/bitops.h>
uint32_t
fast_divide32(uint32_t
v, uint32_t div,
uint32_t m,
uint8_t s1,
uint8_t s2);
uint32_t
fast_remainder32(uint32_t
v, uint32_t div,
uint32_t m,
uint8_t s1,
uint8_t s2);
void
fast_divide32_prepare(uint32_t
div, uint32_t *m,
uint8_t *s1,
uint8_t *s2);
DESCRIPTION
Thefast_divide32 and
fast_remainder32 functions compute the equivalent of
v / div and v
% div using optimised CPU instructions. The
constants m, s1, and
s2 must first be preset for a given value of
div with the
fast_divide32_prepare function.
RATIONALE
These functions are useful for inner loops and other performance-sensitive tasks. The functions expand to code that is typically slightly larger than a plain division instruction, but requires less time to execute. The code for constant div arguments should be equivalent to the assembly created by GCC.
EXAMPLES
The following example computes q = a / b and r = a % b:
uint32_t a, b, q, r, m; uint8_t s1, s2; fast_divide32_prepare(b, &m, &s1, &s2); q = fast_divide32(a, b, m, s1, s2); r = fast_remainder32(a, b, m, s1, s2);
SEE ALSO
bitops(3), div(3), remainder(3)
Torbjörn Granlund and Peter L. Montgomery, Division by Invariant Integers Using Multiplication, ACM SIGPLAN Notices, Issue 6, Volume 29, http://gmplib.org/~tege/divcnst-pldi94.pdf, 61-72, June 1994.
HISTORY
The fast_divide32 function appeared in
NetBSD 6.0.