BeeCrypt
4.2.1
|
Multi-precision integer routines. More...
Go to the source code of this file.
Macros | |
#define | MP_HWBITS (MP_WBITS >> 1) |
#define | MP_WBYTES (MP_WBITS >> 3) |
#define | MP_WNIBBLES (MP_WBITS >> 2) |
#define | MP_WORDS_TO_BITS(x) ((x) << 5) |
#define | MP_WORDS_TO_NIBBLES(x) ((x) << 3) |
#define | MP_WORDS_TO_BYTES(x) ((x) << 2) |
#define | MP_BITS_TO_WORDS(x) ((x) >> 5) |
#define | MP_NIBBLES_TO_WORDS(x) ((x) >> 3) |
#define | MP_BYTES_TO_WORDS(x) ((x) >> 2) |
#define | MP_MSBMASK (((mpw) 0x1) << (MP_WBITS-1)) |
#define | MP_LSBMASK ((mpw) 0x1) |
#define | MP_ALLMASK ~((mpw) 0x0) |
#define | mpcopy(size, dst, src) memcpy(dst, src, MP_WORDS_TO_BYTES(size)) |
#define | mpmove(size, dst, src) memmove(dst, src, MP_WORDS_TO_BYTES(size)) |
Functions | |
void | mpzero (size_t size, mpw *data) |
This function zeroes a multi-precision integer of a given size. More... | |
void | mpfill (size_t size, mpw *data, mpw fill) |
This function fills each word of a multi-precision integer with a given value. More... | |
int | mpodd (size_t size, const mpw *data) |
This functions tests if a multi-precision integer is odd. More... | |
int | mpeven (size_t size, const mpw *data) |
This function tests if a multi-precision integer is even. More... | |
int | mpz (size_t size, const mpw *data) |
This function tests if a multi-precision integer is zero. More... | |
int | mpnz (size_t size, const mpw *data) |
This function tests if a multi-precision integer is not zero. More... | |
int | mpeq (size_t size, const mpw *xdata, const mpw *ydata) |
This function tests if two multi-precision integers of the same size are equal. More... | |
int | mpne (size_t size, const mpw *xdata, const mpw *ydata) |
This function tests if two multi-precision integers of the same size differ. More... | |
int | mpgt (size_t size, const mpw *xdata, const mpw *ydata) |
This function tests if the first of two multi-precision integers of the same size is greater than the second. More... | |
int | mplt (size_t size, const mpw *xdata, const mpw *ydata) |
This function tests if the first of two multi-precision integers of the same size is less than the second. More... | |
int | mpge (size_t size, const mpw *xdata, const mpw *ydata) |
This function tests if the first of two multi-precision integers of the same size is greater than or equal to the second. More... | |
int | mple (size_t size, const mpw *xdata, const mpw *ydata) |
This function tests if the first of two multi-precision integers of the same size is less than or equal to the second. More... | |
int | mpcmp (size_t size, const mpw *xdata, const mpw *ydata) |
This function performs a comparison of two multi-precision integers of the same size. More... | |
int | mpeqx (size_t xsize, const mpw *xdata, size_t ysize, const mpw *ydata) |
This function tests if two multi-precision integers of different size are equal. More... | |
int | mpnex (size_t xsize, const mpw *xdata, size_t ysize, const mpw *ydata) |
This function tests if two multi-precision integers of different size are equal. More... | |
int | mpgtx (size_t xsize, const mpw *xdata, size_t ysize, const mpw *ydata) |
This function tests if the first of two multi-precision integers of different size is greater than the second. More... | |
int | mpltx (size_t xsize, const mpw *xdata, size_t ysize, const mpw *ydata) |
This function tests if the first of two multi-precision integers of different size is less than the second. More... | |
int | mpgex (size_t xsize, const mpw *xdata, size_t ysize, const mpw *ydata) |
This function tests if the first of two multi-precision integers of different size is greater than or equal to the second. More... | |
int | mplex (size_t xsize, const mpw *xdata, size_t ysize, const mpw *ydata) |
This function tests if the first of two multi-precision integers of different size is less than or equal to the second. More... | |
int | mpcmpx (size_t xsize, const mpw *xdata, size_t ysize, const mpw *ydata) |
This function performs a comparison of two multi-precision integers of the different size. More... | |
int | mpisone (size_t size, const mpw *data) |
This functions tests if the value of a multi-precision integer is equal to one. More... | |
int | mpistwo (size_t size, const mpw *data) |
This function tests if the value of a multi-precision integer is equal to two. More... | |
int | mpleone (size_t size, const mpw *data) |
This function tests if the value of a multi-precision integer is less than or equal to one. More... | |
int | mpeqmone (size_t size, const mpw *xdata, const mpw *ydata) |
This function tests if multi-precision integer x is equal to y minus one. More... | |
int | mpmsbset (size_t size, const mpw *data) |
This function tests if the most significant bit of a multi-precision integer is set. More... | |
int | mplsbset (size_t size, const mpw *data) |
This function tests if the leiast significant bit of a multi-precision integer is set. More... | |
void | mpsetmsb (size_t size, mpw *data) |
This function sets the most significant bit of a multi-precision integer. More... | |
void | mpsetlsb (size_t size, mpw *data) |
This function sets the least significant bit of a multi-precision integer. More... | |
void | mpclrmsb (size_t size, mpw *data) |
This function clears the most significant bit of a multi-precision integer. More... | |
void | mpclrlsb (size_t size, mpw *data) |
This function clears the least significant bit of a multi-precision integer. More... | |
void | mpand (size_t size, mpw *xdata, const mpw *ydata) |
This function computes the bit-wise AND of two multi-precision integers. Modifies xdata. More... | |
void | mpor (size_t size, mpw *xdata, const mpw *ydata) |
This function computes the bit-wise OR of two multi-precision integers. Modifies xdata. More... | |
void | mpxor (size_t size, mpw *xdata, const mpw *ydata) |
This function computes the bit-wise XOR of two multi-precision integers. Modifies xdata. More... | |
void | mpnot (size_t size, mpw *data) |
This function flips all bits of a multi-precision integer. More... | |
void | mpsetw (size_t size, mpw *xdata, mpw y) |
This function sets the value of a multi-precision integer to the given word. The given value is copied into the least significant word, while the most significant words are zeroed. More... | |
void | mpsetws (size_t size, mpw *xdata, size_t y) |
This function sets the value of a multi-precision integer to the given word. The given value is copied into the least significant word(s), while the most significant words are zeroed. More... | |
void | mpsetx (size_t xsize, mpw *xdata, size_t ysize, const mpw *ydata) |
This function set the value of the first multi-precision integer to the second, truncating the most significant words if ysize > xsize, or zeroing the most significant words if ysize < xsize. More... | |
int | mpaddw (size_t size, mpw *xdata, mpw y) |
This function adds one word to a multi-precision integer. The performed operation is in pseudocode: x += y. More... | |
int | mpadd (size_t size, mpw *xdata, const mpw *ydata) |
This function adds two multi-precision integers of equal size. The performed operation is in pseudocode: x += y. More... | |
int | mpaddx (size_t xsize, mpw *xdata, size_t ysize, const mpw *ydata) |
This function adds two multi-precision integers of different size. The performed operation in pseudocode: x += y. More... | |
int | mpsubw (size_t size, mpw *xdata, mpw y) |
This function subtracts one word to a multi-precision integer. The performed operation in pseudocode: x -= y. More... | |
int | mpsub (size_t size, mpw *xdata, const mpw *ydata) |
This function subtracts two multi-precision integers of equal size. The performed operation in pseudocode: x -= y. More... | |
int | mpsubx (size_t xsize, mpw *xdata, size_t ysize, const mpw *ydata) |
This function subtracts two multi-precision integers of different size. The performed operation in pseudocode: x -= y. More... | |
int | mpmultwo (size_t size, mpw *data) |
void | mpneg (size_t size, mpw *data) |
This function negates a multi-precision integer. More... | |
size_t | mpsize (size_t size, const mpw *data) |
This function returns the true size of a multi-precision integer, after stripping leading zero words. More... | |
size_t | mpbits (size_t size, const mpw *data) |
This function returns the number of significant bits in a multi-precision integer. More... | |
size_t | mpmszcnt (size_t size, const mpw *data) |
size_t | mplszcnt (size_t size, const mpw *data) |
void | mplshift (size_t size, mpw *data, size_t count) |
void | mprshift (size_t size, mpw *data, size_t count) |
size_t | mprshiftlsz (size_t size, mpw *data) |
size_t | mpnorm (size_t size, mpw *data) |
void | mpdivtwo (size_t size, mpw *data) |
void | mpsdivtwo (size_t size, mpw *data) |
mpw | mpsetmul (size_t size, mpw *result, const mpw *data, mpw y) |
This function performs a multi-precision multiply-setup. More... | |
mpw | mpaddmul (size_t size, mpw *result, const mpw *data, mpw y) |
This function performs a mult-precision multiply-accumulate. More... | |
void | mpaddsqrtrc (size_t size, mpw *result, const mpw *data) |
This function is used in the calculation of a multi-precision squaring. More... | |
void | mpmul (mpw *result, size_t xsize, const mpw *xdata, size_t ysize, const mpw *ydata) |
This function computes a full multi-precision product. More... | |
void | mpsqr (mpw *result, size_t size, const mpw *data) |
This function computes a full multi-precision square. More... | |
void | mpgcd_w (size_t size, const mpw *xdata, const mpw *ydata, mpw *result, mpw *wksp) |
int | mpextgcd_w (size_t size, const mpw *xdata, const mpw *ydata, mpw *result, mpw *wksp) |
mpw | mppndiv (mpw xhi, mpw xlo, mpw y) |
void | mpmod (mpw *result, size_t xsize, const mpw *xdata, size_t ysize, const mpw *ydata, mpw *wksp) |
void | mpndivmod (mpw *result, size_t xsize, const mpw *xdata, size_t ysize, const mpw *ydata, mpw *wksp) |
void | mpprint (size_t size, const mpw *data) |
void | mpprintln (size_t size, const mpw *data) |
void | mpfprint (FILE *f, size_t size, const mpw *data) |
void | mpfprintln (FILE *f, size_t size, const mpw *data) |
int | i2osp (byte *osdata, size_t ossize, const mpw *idata, size_t isize) |
int | os2ip (mpw *idata, size_t isize, const byte *osdata, size_t ossize) |
int | hs2ip (mpw *idata, size_t isize, const char *hsdata, size_t hssize) |
Multi-precision integer routines.
The routines declared here are all low-level operations, most of them suitable to be implemented in assembler. Prime candidates are in order of importance (according to gprof):
With some smart use of available assembler instructions, it's possible to speed these routines up by a factor of 2 to 4.
#define MP_ALLMASK ~((mpw) 0x0) |
#define MP_BITS_TO_WORDS | ( | x | ) | ((x) >> 5) |
#define MP_BYTES_TO_WORDS | ( | x | ) | ((x) >> 2) |
#define MP_HWBITS (MP_WBITS >> 1) |
#define MP_LSBMASK ((mpw) 0x1) |
#define MP_MSBMASK (((mpw) 0x1) << (MP_WBITS-1)) |
#define MP_NIBBLES_TO_WORDS | ( | x | ) | ((x) >> 3) |
#define MP_WBYTES (MP_WBITS >> 3) |
#define MP_WNIBBLES (MP_WBITS >> 2) |
#define MP_WORDS_TO_BITS | ( | x | ) | ((x) << 5) |
#define MP_WORDS_TO_BYTES | ( | x | ) | ((x) << 2) |
#define MP_WORDS_TO_NIBBLES | ( | x | ) | ((x) << 3) |
#define mpcopy | ( | size, | |
dst, | |||
src | |||
) | memcpy(dst, src, MP_WORDS_TO_BYTES(size)) |
#define mpmove | ( | size, | |
dst, | |||
src | |||
) | memmove(dst, src, MP_WORDS_TO_BYTES(size)) |
int hs2ip | ( | mpw * | idata, |
size_t | isize, | ||
const char * | hsdata, | ||
size_t | hssize | ||
) |
This function adds two multi-precision integers of equal size. The performed operation is in pseudocode: x += y.
size | The size of the multi-precision integers. |
xdata | The first multi-precision integer. |
ydata | The second multi-precision integer. |
This function performs a mult-precision multiply-accumulate.
This function is used in the computation of a full multi-precision multiplication. It computes the product-by-one-word and accumulates it with the previous result.
size | The size of multi-precision integer multiplier. |
result | The place where result will be accumulated. |
data | The multi-precision integer multiplier. |
y | The multiplicand. |
The | carry-over multi-precision word. |
This function is used in the calculation of a multi-precision squaring.
This function adds one word to a multi-precision integer. The performed operation is in pseudocode: x += y.
size | The size of the multi-precision integer. |
xdata | The first multi-precision integer. |
y | The multi-precision word. |
This function adds two multi-precision integers of different size. The performed operation in pseudocode: x += y.
xsize | The size of the first multi-precision integer. |
xdata | The first multi-precision integer. |
ysize | The size of the second multi-precision integer. |
ydata | The second multi-precision integer. |
This function computes the bit-wise AND of two multi-precision integers. Modifies xdata.
size | The size of the multi-precision integers. |
xdata | The multi-precision integer data. |
ydata | The multi-precision integer data. |
size_t mpbits | ( | size_t | size, |
const mpw * | data | ||
) |
This function returns the number of significant bits in a multi-precision integer.
size | The size of the multi-precision integer. |
data | The multi-precision integer data. |
void mpclrlsb | ( | size_t | size, |
mpw * | data | ||
) |
This function clears the least significant bit of a multi-precision integer.
size | The size of the multi-precision integer. |
data | The multi-precision integer data. |
void mpclrmsb | ( | size_t | size, |
mpw * | data | ||
) |
This function clears the most significant bit of a multi-precision integer.
size | The size of the multi-precision integer. |
data | The multi-precision integer data. |
This function performs a comparison of two multi-precision integers of the same size.
-1 | if x < y |
0 | if x == y |
1 | if x > y |
This function performs a comparison of two multi-precision integers of the different size.
-1 | if x < y |
0 | if x == y |
1 | if x > y |
void mpdivtwo | ( | size_t | size, |
mpw * | data | ||
) |
This function tests if two multi-precision integers of the same size are equal.
size | The size of the multi-precision integers. |
xdata | The first multi-precision integer. |
ydata | The second multi-precision integer. |
1 | if equal |
0 | if not equal |
This function tests if multi-precision integer x is equal to y minus one.
size | The size of the multi-precision integers. |
xdata | The first multi-precision integer. |
ydata | The second multi-precision integer. |
1 | if less than or equal to one. |
0 | if greater than one. |
This function tests if two multi-precision integers of different size are equal.
xsize | The size of the first multi-precision integer. |
xdata | The first multi-precision integer. |
ysize | The size of the first multi-precision integer. |
ydata | The second multi-precision integer. |
1 | if equal |
0 | if not equal |
int mpeven | ( | size_t | size, |
const mpw * | data | ||
) |
This function tests if a multi-precision integer is even.
size | The size of the multi-precision integer. |
data | The multi-precision integer data. |
1 | if even |
0 | if odd |
This function fills each word of a multi-precision integer with a given value.
size | The size of the multi-precision integer. |
data | The multi-precision integer data. |
fill | The value fill the data with. |
void mpfprint | ( | FILE * | f, |
size_t | size, | ||
const mpw * | data | ||
) |
void mpfprintln | ( | FILE * | f, |
size_t | size, | ||
const mpw * | data | ||
) |
This function tests if the first of two multi-precision integers of the same size is greater than or equal to the second.
size | The size of the multi-precision integers. |
xdata | The first multi-precision integer. |
ydata | The second multi-precision integer. |
1 | if greater or equal |
0 | if less |
This function tests if the first of two multi-precision integers of different size is greater than or equal to the second.
xsize | The size of the first multi-precision integer. |
xdata | The first multi-precision integer. |
ysize | The size of the second multi-precision integer. |
ydata | The second multi-precision integer. |
1 | if greater or equal |
0 | if less |
This function tests if the first of two multi-precision integers of the same size is greater than the second.
size | The size of the multi-precision integers. |
xdata | The first multi-precision integer. |
ydata | The second multi-precision integer. |
1 | if greater |
0 | if less or equal |
This function tests if the first of two multi-precision integers of different size is greater than the second.
xsize | The size of the first multi-precision integer. |
xdata | The first multi-precision integer. |
ysize | The size of the second multi-precision integer. |
ydata | The second multi-precision integer. |
1 | if greater |
0 | if less or equal |
int mpisone | ( | size_t | size, |
const mpw * | data | ||
) |
This functions tests if the value of a multi-precision integer is equal to one.
size | The size of the multi-precision integer. |
data | The multi-precision integer data. |
1 | if one |
0 | if not one |
int mpistwo | ( | size_t | size, |
const mpw * | data | ||
) |
This function tests if the value of a multi-precision integer is equal to two.
size | The size of the multi-precision integer. |
data | The multi-precision integer data. |
1 | if two |
0 | if not two |
This function tests if the first of two multi-precision integers of the same size is less than or equal to the second.
size | The size of the multi-precision integers. |
xdata | The first multi-precision integer. |
ydata | The second multi-precision integer. |
1 | if less or equal |
0 | if greater |
int mpleone | ( | size_t | size, |
const mpw * | data | ||
) |
This function tests if the value of a multi-precision integer is less than or equal to one.
size | The size of the multi-precision integer. |
data | The multi-precision integer data. |
1 | if less than or equal to one. |
0 | if greater than one. |
This function tests if the first of two multi-precision integers of different size is less than or equal to the second.
xsize | The size of the first multi-precision integer. |
xdata | The first multi-precision integer. |
ysize | The size of the second multi-precision integer. |
ydata | The second multi-precision integer. |
1 | if less or equal |
0 | if greater |
int mplsbset | ( | size_t | size, |
const mpw * | data | ||
) |
This function tests if the leiast significant bit of a multi-precision integer is set.
size | The size of the multi-precision integer. |
data | The multi-precision integer data. |
1 | if set |
0 | if not set |
void mplshift | ( | size_t | size, |
mpw * | data, | ||
size_t | count | ||
) |
size_t mplszcnt | ( | size_t | size, |
const mpw * | data | ||
) |
This function tests if the first of two multi-precision integers of the same size is less than the second.
size | The size of the multi-precision integers. |
xdata | The first multi-precision integer. |
ydata | The second multi-precision integer. |
1 | if less |
0 | if greater or equal |
This function tests if the first of two multi-precision integers of different size is less than the second.
xsize | The size of the first multi-precision integer. |
xdata | The first multi-precision integer. |
ysize | The size of the second multi-precision integer. |
ydata | The second multi-precision integer. |
1 | if less |
0 | if greater or equal |
void mpmod | ( | mpw * | result, |
size_t | xsize, | ||
const mpw * | xdata, | ||
size_t | ysize, | ||
const mpw * | ydata, | ||
mpw * | wksp | ||
) |
int mpmsbset | ( | size_t | size, |
const mpw * | data | ||
) |
This function tests if the most significant bit of a multi-precision integer is set.
size | The size of the multi-precision integer. |
data | The multi-precision integer data. |
1 | if set |
0 | if not set |
size_t mpmszcnt | ( | size_t | size, |
const mpw * | data | ||
) |
This function computes a full multi-precision product.
int mpmultwo | ( | size_t | size, |
mpw * | data | ||
) |
void mpndivmod | ( | mpw * | result, |
size_t | xsize, | ||
const mpw * | xdata, | ||
size_t | ysize, | ||
const mpw * | ydata, | ||
mpw * | wksp | ||
) |
This function tests if two multi-precision integers of the same size differ.
size | The size of the multi-precision integers. |
xdata | The first multi-precision integer. |
ydata | The second multi-precision integer. |
1 | if not equal |
0 | if equal |
void mpneg | ( | size_t | size, |
mpw * | data | ||
) |
This function negates a multi-precision integer.
size | The size of the multi-precision integer. |
data | The multi-precision integer data. |
This function tests if two multi-precision integers of different size are equal.
xsize | The size of the first multi-precision integer. |
xdata | The first multi-precision integer. |
ysize | The size of the first multi-precision integer. |
ydata | The second multi-precision integer. |
1 | if equal |
0 | if not equal |
size_t mpnorm | ( | size_t | size, |
mpw * | data | ||
) |
mpnot | ( | size_t | size, |
mpw * | data | ||
) |
This function flips all bits of a multi-precision integer.
size | The size of the multi-precision integer. |
data | The multi-precision integer data. |
int mpnz | ( | size_t | size, |
const mpw * | data | ||
) |
This function tests if a multi-precision integer is not zero.
size | The size of the multi-precision integer. |
data | The multi-precision integer data. |
1 | if not zero |
0 | if zero |
int mpodd | ( | size_t | size, |
const mpw * | data | ||
) |
This functions tests if a multi-precision integer is odd.
size | The size of the multi-precision integer. |
data | The multi-precision integer data. |
1 | if odd |
0 | if even |
This function computes the bit-wise OR of two multi-precision integers. Modifies xdata.
size | The size of the multi-precision integer. |
xdata | The multi-precision integer data. |
ydata | The multi-precision integer data. |
void mpprint | ( | size_t | size, |
const mpw * | data | ||
) |
void mpprintln | ( | size_t | size, |
const mpw * | data | ||
) |
void mprshift | ( | size_t | size, |
mpw * | data, | ||
size_t | count | ||
) |
size_t mprshiftlsz | ( | size_t | size, |
mpw * | data | ||
) |
void mpsdivtwo | ( | size_t | size, |
mpw * | data | ||
) |
void mpsetlsb | ( | size_t | size, |
mpw * | data | ||
) |
This function sets the least significant bit of a multi-precision integer.
size | The size of the multi-precision integer. |
data | The multi-precision integer data. |
void mpsetmsb | ( | size_t | size, |
mpw * | data | ||
) |
This function sets the most significant bit of a multi-precision integer.
size | The size of the multi-precision integer. |
data | The multi-precision integer data. |
This function performs a multi-precision multiply-setup.
This function is used in the computation of a full multi-precision multiplication. By using it we can shave off a few cycles; otherwise we'd have to zero the least significant half of the result first and use another call to the slightly slower mpaddmul function.
size | The size of multi-precision integer multiplier. |
result | The place where result will be accumulated. |
data | The multi-precision integer multiplier. |
y | The multiplicand. |
This function sets the value of a multi-precision integer to the given word. The given value is copied into the least significant word, while the most significant words are zeroed.
size | The size of the multi-precision integer. |
xdata | The multi-precision integer data. |
y | The value to be assigned. |
void mpsetws | ( | size_t | size, |
mpw * | xdata, | ||
size_t | y | ||
) |
This function sets the value of a multi-precision integer to the given word. The given value is copied into the least significant word(s), while the most significant words are zeroed.
size | The size of the multi-precision integer. |
xdata | The multi-precision integer data. |
y | The value. |
This function set the value of the first multi-precision integer to the second, truncating the most significant words if ysize > xsize, or zeroing the most significant words if ysize < xsize.
xsize | The size of the first multi-precision integer. |
xdata | The first multi-precision integer. |
ysize | The size of the second multi-precision integer. |
ydata | The second multi-precision integer. |
size_t mpsize | ( | size_t | size, |
const mpw * | data | ||
) |
This function returns the true size of a multi-precision integer, after stripping leading zero words.
size | The size of the multi-precision integer. |
data | The multi-precision integer data. |
This function computes a full multi-precision square.
This function subtracts two multi-precision integers of equal size. The performed operation in pseudocode: x -= y.
size | The size of the multi-precision integers. |
xdata | The first multi-precision integer. |
ydata | The second multi-precision integer. |
This function subtracts one word to a multi-precision integer. The performed operation in pseudocode: x -= y.
size | The size of the multi-precision integers. |
xdata | The first multi-precision integer. |
y | The multi-precision word. |
This function subtracts two multi-precision integers of different size. The performed operation in pseudocode: x -= y.
xsize | The size of the first multi-precision integer. |
xdata | The first multi-precision integer. |
ysize | The size of the second multi-precision integer. |
ydata | The second multi-precision integer. |
This function computes the bit-wise XOR of two multi-precision integers. Modifies xdata.
size | The size of the multi-precision integer. |
xdata | The multi-precision integer data. |
ydata | The multi-precision integer data. |
int mpz | ( | size_t | size, |
const mpw * | data | ||
) |
This function tests if a multi-precision integer is zero.
size | The size of the multi-precision integer. |
data | The multi-precision integer data. |
1 | if zero |
0 | if not zero |
void mpzero | ( | size_t | size, |
mpw * | data | ||
) |
This function zeroes a multi-precision integer of a given size.
size | The size of the multi-precision integer. |
data | The multi-precision integer data. |