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 to11 2/3
or35/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 fraction155375261911 / 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)?
if (i_pow10 > INT_MAX / 10) return seteor(eor, fs->d_end, -1, ERANGE);
before the linei_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\$-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\$