We start with v0.1 of bsdnt. See the github branch:

Firstly, we set up a bit of infrastructure before we add our first function,

the addition function.

We begin that with some basic types in nn.h:

word_t - represents a machine word (either 32 or 64 bit)

dword_t - twice the size of a machine word (to handle carries from addition)

nn_t - our basic multiprecision integer type, consisting of an array of words

nn_src_t - same as an nn_t, but declared const, so it can't be modified, used

for input/source parameters

len_t - the length in words of a multiprecision integer. We don't use a struct

as we'd have to pass it by reference, which would be less efficient due

to having to dereference the pointer all the time

rand_t - a random state, unused for now. This will ensure thread safety of our

random functions later on.

We also define WORD_BITS, the number of bits in a machine word. To simplify

things, we'll informally let B refer to the number 2^WORD_BITS in what follows.

Our basic bignum type is a pair {c, len} consisting of an nn_t c and a len_t len

counting the number of limbs of our bignum. At this stage we restrict len to

being non-negative, and we allow leading zero limbs in our representation of

our bignums. This allows for twos complement arithmetic with fixed length

bignums (arithmetic modulo B^len for some fixed len).

The first function we write is a simple addition function. This needs to be

pretty sophisticated. In particular, we want to be able to pass in a carry, so

that addition functions can be chained together, or on the end of other functions.

The first addition function will add two operands of the same length (number of

machine words), which we signify with an m at the end of the function name.

We signify that the function takes a carry-in by appending c to the function name.

We will also want the function to pass a carry-out. It'll return this carry out as a

word_t.

The function nn_add_mc is defined in nn.c. Notice how we cast each word to a

dword first, then do the addition, then cast back to a word for the low word of

the sum, and shift by WORD_BITS to get the high word of the result.

The compiler is *supposed* to optimise this combination. Actually, it makes poor

use of the processor carry flag, and screws up the loop, which is why C is not

the best language for a bignum library. But for now it is the best we can do.

Later on we'll add assembly optimisations to our library.

We could unroll the loop (write the contents four times in a row, say, to amortise

the cost of the loop counter arithmetic over four iterations). However, we are

after a cleanly coded library, so we resist this temptation until we write some

assembly code.

Now we introduce some extra macros in nn.h for our addition function. These

represent various permutations of allowing a carry in or not, and one more

interesting macro, nn_s_add_m. This function checks whether the result

and first input are aliased. If so (in other words, we have a = a + c), then the

carry-out gets *added* to the correct limb of a.

If a and b are not aliased (we have a = b + c), then the carry is *written*

and not added, to the correct limb of a. This macro will make coding cleaner

later on.

Notionally, the extra 's' in the function name stands for 'store'.

We use macros for these functions to stop code duplication, and because macros

prevent extra function call overhead, and sometimes offer an opportunity for the

compiler to optimise further.

Note that C macros are not hygienic. In fact they are just text replacement macros.

Thus we need to be careful about naming the macro variables so they are unlikely

to conflict with symbols passed in by the caller. In this case we don't introduce

any variables inside our macros, so this precaution is not necessary.

We also need to take care when using the macro parameters inside the macro. In

some cases it is necessary to put parentheses around the parameters in case

the caller passes in a complex expression which combines badly with expressions

inside our macro (e.g. due to operator precedence). Where there can be no

confusion when substituting a macro, we do not need to do this.

Next we will need to add some random functions, to generate random integers to add

in our test code. In nn.c, we add functions to generate a random word of data, a

random integer up to a limit and a random multiprecision integer.

The random functions take a random state as a parameter. This is essential to

ensure that we can make our random functions threadsafe at a later date. For now

the random state and associated init and clear functions do nothing.

The random word function generates two random integers slightly bigger than half

a word and stitches them together. This is done using an el cheapo pseudorandom

function which works modulo a prime slightly bigger than half a word. We take some

care not to always end up with even output, or output divisible by a given small

prime.

The test code is in t-nn.c. We add a comparison function nn_equal_m to nn.h, to

test equality of two mp integers, to be used in our test code, and some other

convenience functions. We generate random length mp integers, and check an

identity, in this case the associative law for addition. This is not a very

sophisticated test, and we'll have to improve out test code at a later date.

For now, it passes, and we move on to grander things.

Previous article: BSDNT-introduction

Next article: v0.2 - subtraction, shifting

## No comments:

## Post a Comment