3
\$\begingroup\$

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)?
\$\endgroup\$
2
  • \$\begingroup\$ Wah! Just realized the code doesn't properly handle overflow for values such as "0.000000000001" . It works correctly down to 0.000000001. After that, haywire. That's still a relatively minor issue — but justifies the comment about convoluted. A sufficient fix adds two lines if (i_pow10 > INT_MAX / 10) return seteor(eor, fs->d_end, -1, ERANGE); before the line i_pow10 *= 10;. Whether that's beautiful enough is a separate discussion. That test doesn't need to test for the least significant (decimal) digit; it's always zero in a power of 10. \$\endgroup\$ Dec 7, 2015 at 22:29
  • \$\begingroup\$ @chux: -1 1/4 is equivalent to -(1 1/4) or -1.25 in decimal or -5/4. At the moment, -1 -1/4 would return -1 and would indicate the space as where it stopped scanning (signs in the N/D fraction part are not allowed). \$\endgroup\$ Dec 8, 2015 at 3:42

1 Answer 1

2
\$\begingroup\$

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);
\$\endgroup\$
2
  • \$\begingroup\$ Thank you. Yes, that is a bug; the test case is nice and simple (and now incorporated into the tests) and your fix does indeed fix it. It's interesting that the tests intended to exercise that (those involving "134217727 N/16") all pass or fail correctly under both regimes. \$\endgroup\$ Dec 8, 2015 at 3:55
  • \$\begingroup\$ @JonathanLeffler I suppose it's because the failure point occurs at 16/16, where n and d are equal (making the old and new code the same). BTW I found the bug because when I saw d * i + n, it did not appear to me that (i > (INT_MAX - d) / n) was the correct "inverse function" because in one function you added n but the other you subtracted d. \$\endgroup\$
    – JS1
    Dec 8, 2015 at 4:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.