[−][src]Module ramp::ll

This module provides the low-level operations for working with arbitrary precision numbers.

Overview

This module forms the core of the library. As such, the functions are required to be highly performant, even small inefficiencies can cause a large impact given how frequently some of these functions are called. addmul for example is one of the most frequently called functions in the library, so an efficiencies there will be multiplied out to almost the entire library.

There are no real restrictions on the functions that can implemented in here. Exposed functions should be generally useful to high-level code, but otherwise any operation that can be more efficiently implemented here and then exposed by a higher-level API is a candidate.

The functions in this module assume that all inputs are valid, though some checking is performed in debug builds.

Limbs

A Limb is a single "digit" in an arbitrary-precision integer. To explain, consider the standard base we work in, base-10. Base-10 uses represents numbers as a sequence of the digits 0-9. The number 251 is 2 x 10^2 + 5 x 10^1 + 1 x 10^0. Similarly base-16 (hexadecimal) uses sixteen digits and a base of 16 to represent numbers.

A Limb is one word, with N bits (32 on a 32-bit platform, 64 on a 64-bit platform), so it can represent 2^N unique values. It can therefore form the basis of a base-2^N number system. The word "Limb" is used by GMP to distinguish it from a regular numerical digit, and there is no obvious reason to use different terminology.

Limb itself implements a number of useful methods. The basic mathematical operators are implemented to provide wrapping behaviour by default. The most basic operations are also implemented on Limb, notably multiplication with a two-word output and division of a two-word numerator by a one-word denominator. The implementations of these operations are done with inline assembly on x86 platforms with a Rust implementation as fallback.

Integer representation

Integers are passed around as pointers to a series of Limbs. The limbs are stored least-significant first. If required, a size parameter is also provided, but otherwise is omitted when it can be inferred from other sources of information. This is the case with the output pointers used to store the result, they are assumed to have enough memory store the result as the maximum output size is bounded by the size of the inputs.

The integers are not required to be "normalized" in most cases. That is, they may have zero-value limbs in the highest positions. Functions should aim to avoid requiring normalized integers but otherwise explicitly document said requirement.

Memory allocation

No function will allocate memory for a return value. However, it is sometimes required to allocate "scratch space" for storing intermediate values. This scratch space is always temporary and freed before the function returns. Functions that need to make heavy use of scratch space while also being recursive, are split so that scratch space can be re-used.

Argument Conventions

There are no hard-and-fast rules for the argument conventions in this module. There are however some general conventions:

Output/Result pointer goes first (if applicable).
Pointer and matching size are kept close together in the argument list.
Sizes come after the matching pointers. For example, add_n takes two pointers and a length, the length applies to both pointers and so comes after both of them.

Modules

base	Base conversion utilities
limb
limb_ptr
pow

Functions

add ^⚠
add_1 ^⚠
add_n ^⚠	Adds the `n` least signficant limbs of `xp` and `yp`, storing the result in {wp, n}. If there was a carry, it is returned.
addmul_1 ^⚠	Multiplies the `n` least-signficiant digits of `xp` by `vl` and adds them to the `n` least-significant digits of `wp`. Returns the highest limb of the result.
and_n ^⚠	Performs a bitwise "and" (`&`) of the n least signficant limbs of `xp` and `yp`, storing the result in `wp`
and_not_n ^⚠	Performs a bitwise and of the n least signficant limbs of `xp` and `yp`, with the limbs of `yp` being first inverted. The result is stored in `wp`.
cmp ^⚠	Compares the `n` least-significant limbs of `xp` and `yp`, returning whether {xp, n} is less than, equal to or greater than {yp, n}
copy_decr ^⚠	Copies the `n` limbs from `src` to `dst` in a decremental fashion.
copy_incr ^⚠	Copies the `n` limbs from `src` to `dst` in an incremental fashion.
copy_rest ^⚠	Copies the `n - start` limbs from `src + start` to `dst + start`
decr ^⚠
divide_by_zero	Called when a divide by zero occurs.
divrem ^⚠	Divides {np, ns} by {dp, ds}. If ns <= ds, the quotient is stored in {qp, 1}, otherwise the quotient is stored to {qp, (ns - ds) + 1}. The remainder is always stored to {rp, ds}.
divrem_1 ^⚠	Divides the `xs` least-significant limbs at `xp` by `d`, storing the result in {qp, qxn + xs}.
divrem_2 ^⚠
gcd ^⚠
incr ^⚠
is_zero ^⚠	Checks that all `nn` limbs in `np` are zero
mul ^⚠	Multiplies `{xp, xs}` by `{yp, ys}`, storing the result to `{wp, xs + ys}`.
mul_1 ^⚠	Multiplies the `n` least-significant limbs of `xp` by `vl` storing the `n` least-significant limbs of the product in `{wp, n}`.
nand_n ^⚠	Performs a bitwise "nand" of the n least signficant limbs of `xp` and `yp`, storing the result in `wp`
nor_n ^⚠	Performs a bitwise "nor" of the n least signficant limbs of `xp` and `yp`, storing the result in `wp`
normalize ^⚠	Returns the size of the integer pointed to by `p` such that the most significant limb is non-zero.
not ^⚠	Performs a bitwise inversion ("not") of the n least signficant limbs of `xp`, storing the result in `wp`
or_n ^⚠	Performs a bitwise "or" (`\|`) of the n least signficant limbs of `xp` and `yp`, storing the result in `wp`
or_not_n ^⚠	Performs a bitwise "or" of the n least signficant limbs of `xp` and `yp`, with the limbs of `yp` being first inverted. The result is stored in `wp`.
overlap ^⚠
same_or_decr ^⚠
same_or_incr ^⚠
same_or_separate ^⚠
scan_0 ^⚠	Scans for the first 0 bit starting from the least-significant bit the the most, returning the bit index.
scan_1 ^⚠	Scans for the first 1 bit starting from the least-significant bit the the most, returning the bit index.
shl ^⚠	Performs a bit-shift of the limbs in {xp, xs}, left by `cnt` bits storing the result in {rp, rs}. The top-most shifted bits are returned.
shr ^⚠	Performs a bit-shift of the limbs in {xp, xs}, right by `cnt` bits storing the result in {rp, rs}. The bottom-most shifted bits are returned.
sqr ^⚠	Squares the number in `{xp, xs}` storing the result in `{wp, xs*2}`. This is slightly more efficient than regular multiplication with both inputs the same.
sub ^⚠
sub_1 ^⚠
sub_n ^⚠	Subtracts the `n` least signficant limbs of `yp` from `xp`, storing the result in {wp, n}. If there was a borrow from a higher-limb (i.e., the result would be negative), it is returned.
submul_1 ^⚠	Multiplies the `n` least-signficiant digits of `xp` by `vl` and subtracts them from the `n` least-significant digits of `wp`. Returns the highest limb of the result, adjust for borrow.
twos_complement ^⚠	Computes the two's complement of the `xs` least significant words of `xp`. The result is stored the result in `wp`, and a carry is returned, if there is one.
xor_n ^⚠	Performs a bitwise "xor" (`^`) of the n least signficant limbs of `xp` and `yp`, storing the result in `wp`
zero ^⚠