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)
{
    return mp_read_radix(a, str, 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;
    if (radix != 10) {
        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;
 }
 if ((e = mp_toradix(&tmp, *str, radix)) != MP_OKAY) {
 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;
    if (radix < 2 || radix > 64)) {
        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;
    }
    if ((e = mp_toradix(&tmp, *str, radix)) != MP_OKAY) {
	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.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s