Converting fraction notation in strings to a Rational data type

Question

I've been messing around with a RationalInt type, using a simple int-based structure for the time being. I've created code to convert strings to the RationalInt type, but I'm not happy with it; it is too convoluted for comfort (though this second rewrite isn't as bad as the first rewrite, and the initial revision treated too many mal-formatted fractions as valid).

Simple examples of valid fractions are:

• 1
• 1/3
• -1 1/4
• 1.5

The input code does not require the fraction representation to be minimal. For example:

• +6 17/3 is valid enough, but corresponds to 11 2/3 or 35/3.

The code allows arbitrary sequences of blanks and tabs (but not newlines) between the components of a fraction, but only allows a sign at the start. (That is, neither 6 +17/3 nor 6 17/-3 is a valid fraction, but the 6 would be recognized as a valid integer, and hence fraction; the end of the conversion would be the blank after the 6.)

However, the code ensures that values which exceed the range of the int type (assumed to be 32-bit int) are not allowed. For example:

• 1234567 192214/662391 is invalid because the exact fraction 155375261911 / 662391 cannot be represented with two 32-bit integers.

The code identifies the end of the 'subject string' which it recognizes as a fraction, like the strtol() and related functions do. When it returns an error, it sets errno to either EINVAL or ERANGE (but does not set errno to zero, of course).

The function really under review is ri_scn() and the functions it calls. It uses the ri_new() function, so that's included. It does not use the rest of the RationalInt package.

The only external non-standard function used is chk_strtoi(). This is based on the interface for strtol(), but limits the range of valid values to the range of int (INT_MIN..INT_MAX), and checks that the conversion was valid and reports that via the boolean return value.

rational.h (extract)

#ifndef RATIONAL_H_INCLUDED
#define RATIONAL_H_INCLUDED

typedef struct RationalInt
{
    int     numerator;
    int     denominator;
} RationalInt;

extern RationalInt ri_new(int numerator, int denominator);

/* Computation and formatting functions omitted */

extern int ri_scn(const char *str, const char **eor, RationalInt *result);

#endif /* RATIONAL_H_INCLUDED */

rational.c (extract)

At just over 200 lines of code dedicated to scanning, this is about 40% of the code in the package. There are about 270 lines of code in this extract.

/*
** Storage rules:
** 1. Denominator is never zero.
** 2. Denominator stores the sign and is not INT_MIN (2's complement assumed).
** 3. Numerator is never negative.
** 4. gcd(abs(numerator), abs(denominator)) == 1 unless numerator == 0.
*/

#include "rational.h"
#include <assert.h>
#include <ctype.h>
#include <errno.h>
#include <limits.h>
#include <stdbool.h>

//#include "chkstrint.h"
extern bool chk_strtoi(const char *data, char **eon, int base, int *result);

#ifndef ENOERROR
#define ENOERROR 0
#endif

static inline int iabs(int x) { return (x < 0) ? -x : x; }  /* abs() from <stdlib.h>? */
static inline int signum(int x) { return (x > 0) ? +1 : (x < 0) ? -1 : 0; }

static int gcd(int x, int y)
{
    int r;

    if (x == 0 || y == 0)
        return(0);

    while ((r = x % y) != 0)
    {
        x = y;
        y = r;
    }
    return(y);
}

RationalInt ri_new(int numerator, int denominator)
{
    assert(denominator != 0);
    RationalInt ri;
    if (numerator == 0 || denominator == 0)
    {
        ri.numerator = 0;
        ri.denominator = 1;
    }
    else
    {
        int sign = signum(numerator) * signum(denominator);
        assert(sign == +1 || sign == -1);
        int dv = gcd(iabs(numerator), iabs(denominator));
        assert(dv != 0);
        ri.numerator = iabs(numerator) / dv;
        ri.denominator = sign * iabs(denominator) / dv;
    }
    return ri;
}

/* -- Scan Functions -- */

static inline int seteor_return(const char **eor, const char *eoc, int rv, int errnum)
{
    if (eor != 0)
        *eor = eoc;
    if (errnum != ENOERROR)
        errno = errnum;
    return rv;
}

static inline const char *skip_blank(const char *str)
{
    while (isblank(*str))
        str++;
    return str;
}

static inline const char *skip_digits(const char *str)
{
    while (isdigit(*str))
        str++;
    return str;
}

typedef struct FractionString
{
    int sign;
    const char *i_start;
    const char *i_end;
    const char *n_start;
    const char *n_end;
    const char *d_start;
    const char *d_end;
} FractionString;

static int cvt_integer(const FractionString *fs, const char **eor, RationalInt *res)
{
    int i;
    char *eon;
    if (!chk_strtoi(fs->i_start, &eon, 10, &i))
    {
        assert(eon == fs->i_end);
        return seteor_return(eor, eon, -1, ERANGE);
    }
    *res = ri_new(i, fs->sign);
    return seteor_return(eor, fs->i_end, 0, ENOERROR);
}

/* cvt_decimal() handles both ddd. and .ddd as well as ddd.ddd */
static int cvt_decimal(const FractionString *fs, const char **eor, RationalInt *res)
{
    int val = 0;
    int num_i_digits = 0;
    int num_z_digits = 0;
    const char *ptr = fs->i_start;
    if (ptr == 0)
        ptr = fs->d_start;
    else
    {
        assert(isdigit(*ptr));
        while (*ptr == '0')         /* Skip leading zeroes */
        {
            num_z_digits++;
            ptr++;
        }
        while (isdigit(*ptr))
        {
            char c = *ptr++ - '0';
            num_i_digits++;
            if (val > INT_MAX / 10 || (val == INT_MAX / 10 && c > INT_MAX % 10))
                return seteor_return(eor, fs->d_end, -1, ERANGE);
            val = val * 10 + c;
        }
        assert(*ptr == '.');
        ptr++;
    }
    int i_pow10 = 1;
    if (ptr != 0)
    {
        while (isdigit(*ptr))
        {
            char c = *ptr++ - '0';
            if (c == 0)
            {
                /* Trailing zeros are ignored! */
                /* Modestly slow for 1.000001 as it scans over the zeros on each iteration */
                const char *trz = ptr;
                while (*trz == '0')
                    trz++;
                if (!isdigit(*trz))
                {
                    *res = ri_new(val, i_pow10 * fs->sign);
                    return seteor_return(eor, trz, 0, ENOERROR);
                }
            }
            if (val > INT_MAX / 10 || (val == INT_MAX / 10 && c > INT_MAX % 10))
                return seteor_return(eor, fs->d_end, -1, ERANGE);
            val = val * 10 + c;
            i_pow10 *= 10;
        }
    }
    if (i_pow10 == 1 && num_i_digits + num_z_digits == 0)
        return seteor_return(eor, fs->d_end, -1, EINVAL);
    *res = ri_new(val, i_pow10 * fs->sign);
    return seteor_return(eor, ptr, 0, ENOERROR);
}

static int cvt_simple(const FractionString *fs, const char **eor, RationalInt *res)
{
    int i;
    char *eon;
    if (!chk_strtoi(fs->i_start, &eon, 10, &i))
        return seteor_return(eor, fs->d_end, -1, ERANGE);
    assert(eon == fs->i_end);
    int d;
    if (!chk_strtoi(fs->d_start, &eon, 10, &d))
        return seteor_return(eor, fs->d_end, -1, ERANGE);
    assert(eon == fs->d_end);
    *res = ri_new(i, fs->sign * d);
    return seteor_return(eor, fs->d_end, 0, ENOERROR);
}

static int cvt_compound(const FractionString *fs, const char **eor, RationalInt *res)
{
    int i;
    char *eon;
    if (!chk_strtoi(fs->i_start, &eon, 10, &i))
        return seteor_return(eor, fs->d_end, -1, ERANGE);
    assert(eon == fs->i_end);
    int n;
    if (!chk_strtoi(fs->n_start, &eon, 10, &n))
        return seteor_return(eor, fs->d_end, -1, ERANGE);
    assert(eon == fs->n_end);
    int d;
    if (!chk_strtoi(fs->d_start, &eon, 10, &d))
        return seteor_return(eor, fs->d_end, -1, ERANGE);
    /* i, n, d are all valid integers, but can i + n/d be represented? */
    if (i > (INT_MAX - d) / n)
        return seteor_return(eor, fs->d_end, -1, ERANGE);
    *res = ri_new(d * i + n, fs->sign * d);
    return seteor_return(eor, fs->d_end, 0, ENOERROR);
}

int ri_scn(const char *str, const char **eor, RationalInt *res)
{
    struct FractionString fs = { 0, 0, 0, 0, 0, 0, 0, };
    const char *ptr = skip_blank(str);
    fs.sign = +1;
    if (*ptr == '+')
        ptr++;
    else if (*ptr == '-')
    {
        ptr++;
        fs.sign = -1;
    }
    if (*ptr == '.' && isdigit(ptr[1]))
    {
        /* .D */
        fs.d_start = ptr + 1;
        fs.d_end = skip_digits(ptr + 1);
        return cvt_decimal(&fs, eor, res);
    }
    if (!isdigit(*ptr))
        return seteor_return(eor, str, -1, EINVAL);
    fs.i_start = ptr;
    fs.i_end = ptr = skip_digits(ptr);
    if (*ptr == '.')
    {
        /* I.D */
        ptr++;
        if (isdigit(*ptr))
        {
            fs.d_start = ptr;
            fs.d_end = ptr = skip_digits(ptr);
        }
        return cvt_decimal(&fs, eor, res);
    }
    ptr = skip_blank(ptr);
    if (!isdigit(*ptr) && *ptr != '/')
    {
        /* I */
        return cvt_integer(&fs, eor, res);
    }
    if (*ptr == '/')
    {
        /* N / D or I (followed by /) */
        ptr = skip_blank(ptr + 1);
        if (!isdigit(*ptr))
            return cvt_integer(&fs, eor, res);
        fs.d_start = ptr;
        fs.d_end = ptr = skip_digits(ptr);
        /* Convert I / D to fraction */
        return cvt_simple(&fs, eor, res);
    }
    assert(isdigit(*ptr));
    /* I N - is that N/D? */
    fs.n_start = ptr;
    fs.n_end = ptr = skip_digits(ptr);
    ptr = skip_blank(ptr);
    if (*ptr != '/')
    {
        /* Got I */
        return cvt_integer(&fs, eor, res);
    }
    ptr = skip_blank(ptr+1);
    if (!isdigit(*ptr))
    {
        /* Got I */
        return cvt_integer(&fs, eor, res);
    }
    fs.d_start = ptr;
    fs.d_end = ptr = skip_digits(ptr);
    /* Got I N/D */
    return cvt_compound(&fs, eor, res);
}

Compilation

The code compiles cleanly on Mac OS X 10.11.1 running GCC 5.2.0 with the command line:

gcc -O3 -g -I$HOME/inc -std=c11 -Wall -Wextra -Wmissing-prototypes \
    -Wstrict-prototypes -Wold-style-definition -Werror \
    rational.c -o rational -L$HOME/lib/64 -ljl

The -I, -L and -l options pick up support code, such as the chk_strtoi() function and the test harness discussed briefly below.

Test cases

These are the test cases developed for a particular testing package. Phases 1-6 test the computational code and the formatting. I've omitted the actual test code; it isn't exciting. The test cases show what is valid (last column — the status — is 0) and what is invalid (status -1). The code above passes all these tests; that is, it produces the expected status value, identifies the correct offset as the end of the processed string, and produces the correct RationalInt value when the status is 0.

/* -- PHASE 7 TESTING -- */

/* -- Scanning fractions -- */
typedef struct p7_test_case
{
    const char *input;
    RationalInt output;
    int         offset;
    int         status;
} p7_test_case;

static const p7_test_case p7_tests[] =
{
    { "0",                  {          0,          +1 },  1,  0 },
    { "-0",                 {          0,          +1 },  2,  0 },
    { "+0",                 {          0,          +1 },  2,  0 },
    { "- 0",                {          0,          +1 },  0, -1 },
    { "+ 0",                {          0,          +1 },  0, -1 },
    { "-. 0",               {          0,          +1 },  0, -1 },
    { "+. 0",               {          0,          +1 },  0, -1 },
    { "+0",                 {          0,          +1 },  2,  0 },
    { "+000",               {          0,          +1 },  4,  0 },
    { "+123",               {        123,          +1 },  4,  0 },
    { "-321",               {        321,          -1 },  4,  0 },
    { "-321.",              {        321,          -1 },  5,  0 },
    { "-0.321",             {        321,       -1000 },  6,  0 },
    { "-0.-321",            {          0,          +1 },  3,  0 },
    { "-.-321",             {          0,          +1 },  0, -1 },
    { "+0.00",              {          0,          +1 },  5,  0 },
    { "+0.+00",             {          0,          +1 },  3,  0 },
    { "+9.",                {          9,          +1 },  3,  0 },
    { "+9+00",              {          9,          +1 },  2,  0 },
    { "+6.25",              {         25,          +4 },  5,  0 },
    { "-.000",              {          0,          +1 },  5,  0 },
    { "-.001",              {          1,       -1000 },  5,  0 },
    { "+.001",              {          1,       +1000 },  5,  0 },
    { " .001",              {          1,       +1000 },  5,  0 },
    { "0.5XX",              {          1,          +2 },  3,  0 },
    { "-3.14159",           {     314159,     -100000 },  8,  0 },
    { "2147483647X",        { 2147483647,          +1 }, 10,  0 },
    { "-2147.483647 ",      { 2147483647,    -1000000 }, 12,  0 },
    { "0002147483.647",     { 2147483647,       +1000 }, 14,  0 },
    { "000000.7483647",     {    7483647,   +10000000 }, 14,  0 },
    { "-2147.483648 ",      {          0,          +1 }, 12, -1 },
    { "-2147.48364700",     { 2147483647,    -1000000 }, 14,  0 },
    { "-2147.4836470000",   { 2147483647,    -1000000 }, 16,  0 },
    { "-2147.2147480000",   {  536803687,     -250000 }, 16,  0 },
    { "-2147.4000000000",   {      10737,          -5 }, 16,  0 },
    { "-2147.2000000000",   {      10736,          -5 }, 16,  0 },
    { "-2147.2000000001",   {          0,          +1 }, 16, -1 },
    { "-214792000000001",   {          0,          +1 }, 16, -1 },
    { "    0",              {          0,          +1 },  5,  0 },
    { "    0    ",          {          0,          +1 },  5,  0 },
    { "    X",              {          0,          +1 },  0, -1 },

    { "0",                  {          0,          +1 },  1,  0 },
    { "+10",                {         10,          +1 },  3,  0 },
    { "-234",               {        234,          -1 },  4,  0 },
    { "-2147483647",        { 2147483647,          -1 }, 11,  0 },
    { "-2147483648",        {          0,          +1 }, 11, -1 },
    { "+2147483647",        { 2147483647,          +1 }, 11,  0 },
    { "+2147483648",        {          0,          +1 }, 11, -1 },
    { "1/2",                {          1,          +2 },  3,  0 },
    { "+1/2",               {          1,          +2 },  4,  0 },
    { "-1/2",               {          1,          -2 },  4,  0 },
    { "+3/2",               {          3,          +2 },  4,  0 },
    { "-2147483647/3192",   { 2147483647,       -3192 }, 16,  0 },
    { "+2147483648/3192",   {          0,          +1 }, 16, -1 },
    { "-2147483648/3192",   {          0,          +1 }, 16, -1 },
    { "-3192/2147483647",   {       3192, -2147483647 }, 16,  0 },
    { "-3192/2147483648",   {          0,          +1 }, 16, -1 },
    { "-319X/2147483647",   {        319,          -1 },  4,  0 },
    { "-3192/2147X83647",   {        168,        -113 }, 10,  0 },
    { "-3192/-214748347",   {       3192,          -1 },  5,  0 },
    { "+3192.2147",         {   31922147,       10000 }, 10,  0 },
    { "+1 1/2",             {          3,          +2 },  6,  0 },
    { "-1 1/2",             {          3,          -2 },  6,  0 },
    { "1 1/2",              {          3,          +2 },  5,  0 },
    { "12 15/3",            {         17,          +1 },  7,  0 },
    { " 134217727 13/16",   { 2147483645,         +16 }, 16,  0 },
    { "-134217727 14/16",   { 1073741823,          -8 }, 16,  0 },
    { "+134217727 15/16",   { 2147483647,         +16 }, 16,  0 },
    { " 134217727 16/16",   {          0,          +1 }, 16, -1 },
    { " 134217727 17/16",   {          0,          +1 }, 16, -1 },

    { "+312 123/235",       {      73443,        +235 }, 12,  0 },
    { "+312 X",             {        312,          +1 },  4,  0 },
    { "+312 123X",          {        312,          +1 },  4,  0 },
    { "+312 123/X",         {        312,          +1 },  4,  0 },
    { "+312 123/2X",        {        747,          +2 }, 10,  0 },
    { "+312.",              {        312,          +1 },  5,  0 },
    { "+312.X",             {        312,          +1 },  5,  0 },
    { "+312.123  ",         {     312123,       +1000 },  8,  0 },
    { "+312/123  ",         {        104,         +41 },  8,  0 },
    { "+312/X",             {        312,          +1 },  4,  0 },
    { "+312/",              {        312,          +1 },  4,  0 },

    { "     +1000138887464217727     \t  2314134213112217\t/\t112324233423432432422226",
                            {          0,          +1 }, 76, -1 },
};

Note that if the code allowed for bigger integers, the last sample would be valid. It is only invalid because each of the numbers is far too big to fit into a 32-bit int.

Questions

• Is there a better way to write the scanning code, ensuring that the valid inputs remain valid and the invalid inputs remain invalid?
• Is there a way to tweak the definitions of valid and invalid inputs that radically simplifies the scanning code without allowing egregious mal-formatted fractions through?
• Should the rule disallowing signs except at the beginning be relaxed?
• Should the rule allowing arbitrary amounts of white space be tightened (to allow a single space — not a tab, not multiple characters)?

Answer 1

Bug

Currently, if you try this input:

100000 1/100000

you will get this result:

1410065409 / 100000

The problem is with this overflow check in cvt_compound():

/* i, n, d are all valid integers, but can i + n/d be represented? */
if (i > (INT_MAX - d) / n)
    return seteor_return(eor, fs->d_end, -1, ERANGE);

The n and d need to be switched, like this:

/* i, n, d are all valid integers, but can i + n/d be represented? */
if (i > (INT_MAX - n) / d)
    return seteor_return(eor, fs->d_end, -1, ERANGE);