Saturday, 16 October 2010

BSDNT - v0.18 printx_word, nn_printx

It is time we improved our test code again. We'll spend a few days updating
things to make improvements in the way we test.

Today's update is quite straightforward. We currently have no way of printing
nn_t's. This is quite inconvenient when it comes to the test code, where
little to no diagnostic information is printed at all. In particular, we
aren't printing out any of the multiple precision integers for examination
when a test fails.

Now, it is actually quite a difficult job to print bignum integers in decimal.
In fact, as far as I can see, one requires a function which allocates temporary
space to efficiently print integers. This is an interesting challenge:
is there an algorithm to convert from binary to decimal and print the result,
with just O(1) temporary space, with any complexity.

I think it may be possible if one allows the input to be destroyed. If so, a
subsidiary question would be to do the same thing without destroying the
input. I doubt that is possible, but I do not have a proof. Of course, to be
practical, we'd require an algorithm which doesn't destroy the input.

To get around this issue, we'll start with a simple nn_printx algorithm,
which will print a bignum in hexadecimal. We also add an nn_printx_short
function which prints the first couple of words of a bignum, an ellipsis and
then the final couple of words. This is useful for large bignums that would
print for screens and screens due to their size. We'll use this in our test
code to prevent printing too much output upon test failure.

Another function we add is an nn_printx_diff function. It accepts two nn_t's
and prints information about the range of words where they differ and prints
the first and last differing word in each case.

There is one tricky aspect to our printing functions however. A word is often
an unsigned long, but on some platforms it will be an unsigned long long. For
this reason, when printing a word, we need to use %lx as the format specifier
on some platforms and %llx on others.

So we need to add a routine which will print a word and abstract away the
format specifier so the caller doesn't have to think about it. The function
we include to do this is caled printx_word. It prints a word without needing
to specify a format specifier.

We add files helper.c/h to bsdnt which will contain routines like this one
which aren't specific to our nn module. A few existing functions and macros
also get moved there. The configure system will automatically look for
architecture specific versions of helper.c, allowing us to override the
definition of the functions in that file on a per architecture basis.

We add the printx_word function to helper.c which can be overridden with
an architecture specific version. On a platform where %llx is required, an
architecture specific version will simply replace the generic version which
uses %lx.

In test.h we add some macros, print_debug and print_debug_diff which use the
stringizing operator to print the names of the variables and then print their
values. The stringizing operator (#) is a preprocessor macro which turns a
macro parameter into a string. In our case, we pass the variable name to the
macro and turn it into a string so that we can print the variable name.

A few modifications to the TEST_START and TEST_END macros in test.h also
allow us to give a unique name to each test which is then printed along with
the iteration at which the test failed. This also uses the stringizing
operator so that the caller of TEST_START can specify the unique name for the
test. It seems difficult to come up with an automatic way of generating
unique test names, so this will have to do.

It would also be a useful thing to have it print the value of the random seed
at the start of a failing iteration too. After we have improved the random
generation code in bsdnt v0.21, perhaps someone would like to try adding this
feature.

We roll out our new diagnostic printing routines to our test code. Of course,
to see any of this new code in action, one has to introduce a bug in one of
the tests so that the new diagnostic code is actually run. I leave it to you
to fiddle around introducing bugs to see that the new test code does actually
print useful diagnostic information.

Later on we'll add a bsdnt_printf function which will be variadic and accept
a format specifier like the C printf function and which will have a
consistent %w for printing a word. This will also make things easier on
Windows, where currently the format specifier will be wrong in many places.
We'll fix this problem in a later update.

The code for today's post is here: v0.18

Previous article: v0.17 - div_hensel
Next article: v0.19 - asserts