Utilities to assist with implementing big number arithmetic. More...

#include <BigNumberUtil.h>

Static Public Member Functions
static void	unpackLE (limb_t limbs, size_t count, const uint8_t bytes, size_t len)
	Unpacks the little-endian byte representation of a big number into a limb array. More...

static void	unpackBE (limb_t limbs, size_t count, const uint8_t bytes, size_t len)
	Unpacks the big-endian byte representation of a big number into a limb array. More...

static void	packLE (uint8_t bytes, size_t len, const limb_t limbs, size_t count)
	Packs the little-endian byte representation of a big number into a byte array. More...

static void	packBE (uint8_t bytes, size_t len, const limb_t limbs, size_t count)
	Packs the big-endian byte representation of a big number into a byte array. More...

static limb_t	add (limb_t result, const limb_t x, const limb_t *y, size_t size)
	Adds two big numbers. More...

static limb_t	sub (limb_t result, const limb_t x, const limb_t *y, size_t size)
	Subtracts one big number from another. More...

static void	mul (limb_t result, const limb_t x, size_t xcount, const limb_t *y, size_t ycount)
	Multiplies two big numbers. More...

static void	reduceQuick (limb_t result, const limb_t x, const limb_t *y, size_t size)
	Reduces x modulo y using subtraction. More...

static limb_t	add_P (limb_t result, const limb_t x, const limb_t *y, size_t size)
	Adds two big numbers where one of them is in program memory. More...

static limb_t	sub_P (limb_t result, const limb_t x, const limb_t *y, size_t size)
	Subtracts one big number from another where one is in program memory. More...

static void	mul_P (limb_t result, const limb_t x, size_t xcount, const limb_t *y, size_t ycount)
	Multiplies two big numbers where one is in program memory. More...

static void	reduceQuick_P (limb_t result, const limb_t x, const limb_t *y, size_t size)
	Reduces x modulo y using subtraction where y is in program memory. More...

static limb_t	isZero (const limb_t *x, size_t size)
	Determine if a big number is zero. More...

Detailed Description

Utilities to assist with implementing big number arithmetic.

Big numbers are represented as arrays of limb_t words, which may be 8 bits, 16 bits, or 32 bits in size depending upon how the library was configured. For AVR, 16 bit limbs usually give the best performance.

Limb arrays are ordered from the least significant word to the most significant.

Definition at line 72 of file BigNumberUtil.h.

Member Function Documentation

◆ add()

limb_t BigNumberUtil::add	(	limb_t *	result,
		const limb_t *	x,
		const limb_t *	y,
		size_t	size
	)

static

Adds two big numbers.

Parameters

result	The result of the addition. This can be the same as either x or y.
x	The first big number.
y	The second big number.
size	The size of the values in limbs.

Returns: Returns 1 if there was a carry out or 0 if there was no carry out.

See also: sub(), mul()

Definition at line 495 of file BigNumberUtil.cpp.

◆ add_P()

limb_t BigNumberUtil::add_P	(	limb_t *	result,
		const limb_t *	x,
		const limb_t *	y,
		size_t	size
	)

static

Adds two big numbers where one of them is in program memory.

Parameters

result	The result of the addition. This can be the same as x.
x	The first big number.
y	The second big number. This must point into program memory.
size	The size of the values in limbs.

Returns: Returns 1 if there was a carry out or 0 if there was no carry out.

See also: sub_P(), mul_P()

Definition at line 628 of file BigNumberUtil.cpp.

◆ isZero()

limb_t BigNumberUtil::isZero	(	const limb_t *	x,
		size_t	size
	)

static

Determine if a big number is zero.

Parameters

x	Points to the number to test.
size	The number of limbs in x.

Returns: Returns 1 if x is zero or 0 otherwise.

This function attempts to make the determination in constant time.

Definition at line 761 of file BigNumberUtil.cpp.

◆ mul()

void BigNumberUtil::mul	(	limb_t *	result,
		const limb_t *	x,
		size_t	xcount,
		const limb_t *	y,
		size_t	ycount
	)

static

Multiplies two big numbers.

Parameters

result	The result of the multiplication. The array must be xcount + ycount limbs in size.
x	Points to the first value to multiply.
xcount	The number of limbs in x.
y	Points to the second value to multiply.
ycount	The number of limbs in y.

See also: mul_P()

Definition at line 546 of file BigNumberUtil.cpp.

◆ mul_P()

void BigNumberUtil::mul_P	(	limb_t *	result,
		const limb_t *	x,
		size_t	xcount,
		const limb_t *	y,
		size_t	ycount
	)

static

Multiplies two big numbers where one is in program memory.

Parameters

result	The result of the multiplication. The array must be xcount + ycount limbs in size.
x	Points to the first value to multiply.
xcount	The number of limbs in x.
y	Points to the second value to multiply. This must point into program memory.
ycount	The number of limbs in y.

See also: mul()

Definition at line 680 of file BigNumberUtil.cpp.

◆ packBE()

void BigNumberUtil::packBE	(	uint8_t *	bytes,
		size_t	len,
		const limb_t *	limbs,
		size_t	count
	)

static

Packs the big-endian byte representation of a big number into a byte array.

Parameters

bytes	The byte array to pack into.
len	The number of bytes in the destination bytes array.
limbs	The limb array representing the big number, starting with the least significant word.
count	The number of elements in the limbs array.

If len is shorter than the length of limbs, then the number will be truncated to the least significant len bytes. If len is longer than the length of limbs, then the high bytes will be filled with zeroes.

See also: unpackLE(), packBE()

Definition at line 375 of file BigNumberUtil.cpp.

◆ packLE()

void BigNumberUtil::packLE	(	uint8_t *	bytes,
		size_t	len,
		const limb_t *	limbs,
		size_t	count
	)

static

Packs the little-endian byte representation of a big number into a byte array.

Parameters

bytes	The byte array to pack into.
len	The number of bytes in the destination bytes array.
limbs	The limb array representing the big number, starting with the least significant word.
count	The number of elements in the limbs array.

If len is shorter than the length of limbs, then the number will be truncated to the least significant len bytes. If len is longer than the length of limbs, then the high bytes will be filled with zeroes.

See also: unpackLE(), packBE()

Definition at line 264 of file BigNumberUtil.cpp.

◆ reduceQuick()

void BigNumberUtil::reduceQuick	(	limb_t *	result,
		const limb_t *	x,
		const limb_t *	y,
		size_t	size
	)

static

Reduces x modulo y using subtraction.

Parameters

result	The result of the reduction. This can be the same as x.
x	The number to be reduced.
y	The base to use for the modulo reduction.
size	The size of the values in limbs.

It is assumed that x is less than y * 2 so that a single conditional subtraction will bring it down below y. The reduction is performed in constant time.

See also: reduceQuick_P()

Definition at line 598 of file BigNumberUtil.cpp.

◆ reduceQuick_P()

void BigNumberUtil::reduceQuick_P	(	limb_t *	result,
		const limb_t *	x,
		const limb_t *	y,
		size_t	size
	)

static

Reduces x modulo y using subtraction where y is in program memory.

Parameters

result	The result of the reduction. This can be the same as x.
x	The number to be reduced.
y	The base to use for the modulo reduction. This must point into program memory.
size	The size of the values in limbs.

It is assumed that x is less than y * 2 so that a single conditional subtraction will bring it down below y. The reduction is performed in constant time.

See also: reduceQuick()

Definition at line 734 of file BigNumberUtil.cpp.

◆ sub()

limb_t BigNumberUtil::sub	(	limb_t *	result,
		const limb_t *	x,
		const limb_t *	y,
		size_t	size
	)

static

Subtracts one big number from another.

Parameters

result	The result of the subtraction. This can be the same as either x or y.
x	The first big number.
y	The second big number to subtract from x.
size	The size of the values in limbs.

Returns: Returns 1 if there was a borrow, or 0 if there was no borrow.

See also: add(), mul()

Definition at line 522 of file BigNumberUtil.cpp.

◆ sub_P()

limb_t BigNumberUtil::sub_P	(	limb_t *	result,
		const limb_t *	x,
		const limb_t *	y,
		size_t	size
	)

static

Subtracts one big number from another where one is in program memory.

Parameters

result	The result of the subtraction. This can be the same as x.
x	The first big number.
y	The second big number to subtract from x. This must point into program memory.
size	The size of the values in limbs.

Returns: Returns 1 if there was a borrow, or 0 if there was no borrow.

See also: add_P(), mul_P()

Definition at line 655 of file BigNumberUtil.cpp.

◆ unpackBE()

void BigNumberUtil::unpackBE	(	limb_t *	limbs,
		size_t	count,
		const uint8_t *	bytes,
		size_t	len
	)

static

Unpacks the big-endian byte representation of a big number into a limb array.

Parameters

limbs	The limb array, starting with the least significant word.
count	The number of elements in the limbs array.
bytes	The bytes to unpack.
len	The number of bytes to unpack.

If len is shorter than the length of limbs, then the high bytes will be filled with zeroes. If len is longer than the length of limbs, then the high bytes will be truncated and lost.

See also: packBE(), unpackLE()

Definition at line 163 of file BigNumberUtil.cpp.

◆ unpackLE()

void BigNumberUtil::unpackLE	(	limb_t *	limbs,
		size_t	count,
		const uint8_t *	bytes,
		size_t	len
	)

static

Unpacks the little-endian byte representation of a big number into a limb array.

Parameters

limbs	The limb array, starting with the least significant word.
count	The number of elements in the limbs array.
bytes	The bytes to unpack.
len	The number of bytes to unpack.

If len is shorter than the length of limbs, then the high bytes will be filled with zeroes. If len is longer than the length of limbs, then the high bytes will be truncated and lost.

See also: packLE(), unpackBE()

Definition at line 55 of file BigNumberUtil.cpp.

The documentation for this class was generated from the following files:

Static Public Member Functions

Detailed Description

Member Function Documentation

◆ add()

◆ add_P()

◆ isZero()

◆ mul()

◆ mul_P()

◆ packBE()

◆ packLE()

◆ reduceQuick()

◆ reduceQuick_P()

◆ sub()

◆ sub_P()

◆ unpackBE()

◆ unpackLE()