# Adventures of a Programmer: Parser Writing Peril II

While playing around with libtomfloat I came to the conclusion that the library is too incomplete, far from the maturity of libtomfloat and it would involve too much work to get it stable, so I shoved it back on the TODO list and started a rational library based on libtomfloat.

NB: libtommath has a bug in mp_n_root() that makes this function unusable slow. Again a problem with the initial value. I made a pull-request for a bugfix which may or may not be granted, it is even unknown if development is still active. For the time it needs to answer the questions above: my fork is available at Github but only the bugfix is included yet.

As I like to see the results directly and in detail I implemented some I/O. It was way easier this time because libtomfloat has all the necessary functions to write parsing and printing functions to write I/O functions with just a couple of lines.

Input is the easiest:

int mp_get_str(const char *str, mp_int * a, int radix)
{
}


See, just a wrapper around a fully functional string parser. It seems a bit senseless but it is meant to be extended later to automatically detect the radix. The value returned is, obviously, the error from mp_read_radix() or MP_OKAY respectively.

It is more complicated the other way around but not much. The function mp_toradix() exists but does not allocate memory. The number of digits $d_{b_1}$ necessary to represent a number in base $b_2$ in base $b_1$ is

$\displaystyle{ d_{b_1} = \left\lceil\dfrac{d_{b_2}}{log_{b_2} b_1 }\right\rceil}$

Restricting it to base 10 we get the following code:

#ifndef MPI_LOG2
# define MPI_LOG2 3.32192809488736234787031942948939017586483139302458061205
#endif
int mp_put_str(mp_int * a, char **str, int radix)
{
size_t buflen; int e;
mp_int tmp;
return MP_VAL;
}
/* mp_count_bits() would be more exact, but wouldn't save more than half a dozen
bytes */
buflen =
(size_t) ((double) ((a->used+1) * DIGIT_BIT) / (double) (MPI_LOG2)) + 1;
//printf("buflen %zu\n",buflen);
*str = malloc(buflen);
if (*str == NULL) {
return MP_MEM;
}
if ((e = mp_init(&tmp)) != MP_OKAY) {
return e;
}
if ((e = mp_copy(a, &tmp)) != MP_OKAY) {
return e;
}
return e;
}
mp_clear(&tmp);
return MP_OKAY;
}


For arbitrary radix (mp_toradix() supports up to radix 64 (sixty-four)) it would be:

int mp_put_str(mp_int * a, char **str, int radix)
{
size_t buflen;
int e;
mp_int tmp;
return MP_VAL;
}
buflen =
(size_t) ((double) ((a->used+1) * DIGIT_BIT) / (log(radix)/log(2)))+1;
*str = malloc(buflen);
if (*str == NULL) {
return MP_MEM;
}
if ((e = mp_init(&tmp)) != MP_OKAY) {
return e;
}
if ((e = mp_copy(a, &tmp)) != MP_OKAY) {
return e;
}
return e;
}
mp_clear(&tmp);
return MP_OKAY;
}


 That above needs a link to libmath, at least with GCC. Your mileage may vary; the logarithm function(s) might be a built-in of your compiler.

From here on the obligatory functions for file I/O are easy (all of them put out numbers in base 10 (ten) no matter which version of mp_put_str() is used.).

/*
* Prints "a" to stdout followed by a newline.
* Returns the number of characters printed or a value lower
* than zero in case of an error.
* FIXME: does not differ between errors of mp_put_str() and
*        errors of printf();
*/
int mp_puts(mp_int * a)
{
char *buf;
int e;
if ((e = mp_put_str(a, &(buf), 10)) != MP_OKAY) {
return e;
}
e = printf("%s\n", buf);
free(buf);
return e;
}
/*
* Prints "a" to "stream" followed by a newline.
* Returns the number of characters printed or a value lower
* than zero in case of an error.
* FIXME: does not differ between errors of mp_put_str() and
*        errors of fprintf();
*/
int mp_fputs(mp_int * a, FILE *stream)
{
char *buf;
int e;
if ((e = mp_put_str(a, &(buf), 10)) != MP_OKAY) {
return e;
}
e = fprintf(stream,"%s\n", buf);
free(buf);
return e;
}


These function are very basic and it would be nice to have a function like mp_tostr() that returns a direct pointer to the result.

char * mp_tostr(mp_int * a, char *buf)
{
int e;
if ((e = mp_put_str(a, &buf, 10)) != MP_OKAY) {
/* Where to put the error is a good question. errno? */
return NULL;
}
return buf;
}


That can be used in a normal printf now, just give the function a pointer to a nice comfy place to put the string. For example:

char *buf;
...
printf("The result is %s",mp_tostr(&a,buf);
...
free(buf);
buf = NULL;
...
printf(Another result is %s",mp_tostr(&b,buf);
...
free(buf);
buf = NULL;
...


Resetting the buffer instead of using realloc() in mp_put_str works for me, not necessary for you, so feel free to change it.

PS: libtommath has no very fast multiplication algorithms only fast ones. Does it need them? I think at least a simple FFT should be implemented. Let’s see what can be done to it.
In the next post.