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