Module div_limb 

Implementation of constant-time division via reciprocal precomputation, as described in “Improved Division by Invariant Integers” by Niels Möller and Torbjorn Granlund (DOI: 10.1109/TC.2010.143, https://gmplib.org/~tege/division-paper.pdf).

Structs

Reciprocal

A pre-calculated reciprocal for division by a single limb.

Functions

addhilo 🔒

Adds wide numbers represented by pairs of (most significant word, least significant word) and returns the result in the same format (hi, lo).

ct_lt 🔒

Returns u32::MAX if a < b and 0 otherwise.

ct_select 🔒

Returns a if c == 0 and b if c == u32::MAX.

div2by1 🔒

Calculate the quotient and the remainder of the division of a wide word (supplied as high and low words) by d, with a precalculated reciprocal v.

div_rem_limb_with_reciprocal 🔒

Divides u by the divisor encoded in the reciprocal, and returns the quotient and the remainder.

mulhilo 🔒

Multiplies x and y, returning the most significant and the least significant words as (hi, lo).

reciprocal

Calculates the reciprocal of the given 64-bit divisor with the highmost bit set.

short_div 🔒

Calculates dividend / divisor, given dividend and divisor along with their maximum bitsizes.