Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c > #58570 > unrolled thread

Code for strtol/strtoul

Back to article view | Back to comp.lang.c

Contents

  Code for strtol/strtoul jacob navia <jacob@jacob.remcomp.fr> - 2015-03-21 12:09 +0100
    Re: Code for strtol/strtoul Bartc <bc@freeuk.com> - 2015-03-21 11:33 +0000
      Re: Code for strtol/strtoul Bartc <bc@freeuk.com> - 2015-03-21 11:47 +0000
      Re: Code for strtol/strtoul Greg Martin <greg.at.softsprocket@dot.com> - 2015-03-21 15:58 +0000
    Re: Code for strtol/strtoul Lőrinczy Zsigmond <nospam@for.me> - 2015-03-21 16:10 +0100
      Re: Code for strtol/strtoul jacob navia <jacob@jacob.remcomp.fr> - 2015-03-21 16:34 +0100
        Re: Code for strtol/strtoul Kaz Kylheku <kaz@kylheku.com> - 2015-03-21 16:10 +0000
      Re: Code for strtol/strtoul James Kuyper <jameskuyper@verizon.net> - 2015-03-21 12:53 -0400
      Re: Code for strtol/strtoul Keith Thompson <kst-u@mib.org> - 2015-03-21 14:18 -0700
        Re: Code for strtol/strtoul jacob navia <jacob@jacob.remcomp.fr> - 2015-03-21 22:46 +0100
          Re: Code for strtol/strtoul Keith Thompson <kst-u@mib.org> - 2015-03-21 15:23 -0700
            Re: Code for strtol/strtoul jacob navia <jacob@jacob.remcomp.fr> - 2015-03-21 23:42 +0100
              Re: Code for strtol/strtoul Keith Thompson <kst-u@mib.org> - 2015-03-21 16:06 -0700
                Re: Code for strtol/strtoul jacob navia <jacob@jacob.remcomp.fr> - 2015-03-22 00:29 +0100
                  Re: Code for strtol/strtoul Keith Thompson <kst-u@mib.org> - 2015-03-21 20:18 -0700
        Re: Code for strtol/strtoul Keith Thompson <kst-u@mib.org> - 2015-03-21 15:54 -0700
          Re: Code for strtol/strtoul jacob navia <jacob@jacob.remcomp.fr> - 2015-03-22 08:34 +0100
          Re: Code for strtol/strtoul Tim Rentsch <txr@alumni.caltech.edu> - 2015-03-24 19:42 -0700
            Re: Code for strtol/strtoul Keith Thompson <kst-u@mib.org> - 2015-03-25 10:40 -0700
              Re: Code for strtol/strtoul Tim Rentsch <txr@alumni.caltech.edu> - 2015-03-25 16:17 -0700
                Re: Code for strtol/strtoul Keith Thompson <kst-u@mib.org> - 2015-03-25 20:27 -0700
                  Re: Code for strtol/strtoul Tim Rentsch <txr@alumni.caltech.edu> - 2015-03-28 09:08 -0700
    Re: Code for strtol/strtoul Greg Martin <greg.at.softsprocket@dot.com> - 2015-03-21 15:53 +0000
      Re: Code for strtol/strtoul Tim Rentsch <txr@alumni.caltech.edu> - 2015-03-24 21:50 -0700
        Re: Code for strtol/strtoul jacob navia <jacob@jacob.remcomp.fr> - 2015-03-25 06:54 +0100
          Re: Code for strtol/strtoul Ian Collins <ian-news@hotmail.com> - 2015-03-25 19:18 +1300
            Re: Code for strtol/strtoul jacob navia <jacob@jacob.remcomp.fr> - 2015-03-25 09:57 +0100
              Re: Code for strtol/strtoul Ian Collins <ian-news@hotmail.com> - 2015-03-26 07:07 +1300
                Re: Code for strtol/strtoul Ian Collins <ian-news@hotmail.com> - 2015-03-26 14:22 +1300
                  Re: Code for strtol/strtoul asetofsymbols@gmail.com - 2015-03-26 00:17 -0700
                    Re: Code for strtol/strtoul Ian Collins <ian-news@hotmail.com> - 2015-03-28 12:07 +1300
                    Re: Code for strtol/strtoul asetofsymbols@gmail.com - 2015-03-28 02:53 -0700
          Re: Code for strtol/strtoul Tim Rentsch <txr@alumni.caltech.edu> - 2015-03-25 08:19 -0700
          Re: Code for strtol/strtoul Tim Rentsch <txr@alumni.caltech.edu> - 2015-03-28 16:13 -0700
        Re: Code for strtol/strtoul Greg Martin <greg.at.softsprocket@dot.com> - 2015-03-25 13:42 +0000
          Re: Code for strtol/strtoul Tim Rentsch <txr@alumni.caltech.edu> - 2015-03-25 17:20 -0700
            Re: Code for strtol/strtoul Kaz Kylheku <kaz@kylheku.com> - 2015-03-26 04:16 +0000
              Re: Code for strtol/strtoul asetofsymbols@gmail.com - 2015-03-26 00:27 -0700
                Re: Code for strtol/strtoul Kaz Kylheku <kaz@kylheku.com> - 2015-03-26 13:44 +0000
                  Re: Code for strtol/strtoul fir <profesor.fir@gmail.com> - 2015-03-26 07:13 -0700
                  Re: Code for strtol/strtoul asetofsymbols@gmail.com - 2015-03-26 08:30 -0700
                    Re: Code for strtol/strtoul raltbos@xs4all.nl (Richard Bos) - 2015-03-29 15:13 +0000
              Re: Code for strtol/strtoul Tim Rentsch <txr@alumni.caltech.edu> - 2015-03-28 09:47 -0700
            Re: Code for strtol/strtoul Greg Martin <greg.at.softsprocket@dot.com> - 2015-03-26 15:00 +0000
              Re: Code for strtol/strtoul Ian Collins <ian-news@hotmail.com> - 2015-03-27 07:12 +1300
                Re: Code for strtol/strtoul Bartc <bc@freeuk.com> - 2015-03-26 19:11 +0000
                  Re: Code for strtol/strtoul Malcolm McLean <malcolm.mclean5@btinternet.com> - 2015-03-26 15:09 -0700
                    Re: Code for strtol/strtoul Richard Heathfield <rjh@cpax.org.uk> - 2015-03-26 22:13 +0000
                      Re: Code for strtol/strtoul Malcolm McLean <malcolm.mclean5@btinternet.com> - 2015-03-26 15:20 -0700
                    Re: Code for strtol/strtoul raltbos@xs4all.nl (Richard Bos) - 2015-03-30 09:59 +0000
                      Re: Code for strtol/strtoul Malcolm McLean <malcolm.mclean5@btinternet.com> - 2015-03-30 06:38 -0700
                        Re: Code for strtol/strtoul Richard Heathfield <rjh@cpax.org.uk> - 2015-03-30 14:41 +0100
                          Re: Code for strtol/strtoul raltbos@xs4all.nl (Richard Bos) - 2015-04-06 12:52 +0000
                  Re: Code for strtol/strtoul Ian Collins <ian-news@hotmail.com> - 2015-03-27 18:07 +1300
                    Re: Code for strtol/strtoul raltbos@xs4all.nl (Richard Bos) - 2015-03-29 15:17 +0000
                      Re: Code for strtol/strtoul Kaz Kylheku <kaz@kylheku.com> - 2015-03-29 15:26 +0000
                      Re: Code for strtol/strtoul Ian Collins <ian-news@hotmail.com> - 2015-03-30 07:09 +1300
                        Re: Code for strtol/strtoul raltbos@xs4all.nl (Richard Bos) - 2015-03-30 10:02 +0000
                    Re: Code for strtol/strtoul Bartc <bc@freeuk.com> - 2015-03-29 18:53 +0100
              Re: Code for strtol/strtoul Tim Rentsch <txr@alumni.caltech.edu> - 2015-03-28 15:38 -0700
    Re: Code for strtol/strtoul Robert Wessel <robertwessel2@yahoo.com> - 2015-03-21 16:48 -0500
    Re: Code for strtol/strtoul Ian Collins <ian-news@hotmail.com> - 2015-03-22 20:45 +1300
      Re: Code for strtol/strtoul Ike Naar <ike@iceland.freeshell.org> - 2015-03-23 09:40 +0000
        Re: Code for strtol/strtoul Richard Heathfield <rjh@cpax.org.uk> - 2015-03-23 09:46 +0000
          Re: Code for strtol/strtoul Reinhardt Behm <rbehm@hushmail.com> - 2015-03-23 18:44 +0800
          Re: Code for strtol/strtoul Les Cargill <lcargill99@comcast.com> - 2015-03-23 20:29 -0500
            Re: Code for strtol/strtoul Richard Heathfield <rjh@cpax.org.uk> - 2015-03-24 08:12 +0000
        Re: Code for strtol/strtoul Robert Wessel <robertwessel2@yahoo.com> - 2015-03-23 05:27 -0500
        Re: Code for strtol/strtoul Ian Collins <ian-news@hotmail.com> - 2015-03-24 07:03 +1300
          Re: Code for strtol/strtoul Ike Naar <ike@iceland.freeshell.org> - 2015-03-23 22:40 +0000
            Re: Code for strtol/strtoul Ian Collins <ian-news@hotmail.com> - 2015-03-24 17:17 +1300
              Re: Code for strtol/strtoul Tim Rentsch <txr@alumni.caltech.edu> - 2015-03-24 21:42 -0700
                Re: Code for strtol/strtoul Ian Collins <ian-news@hotmail.com> - 2015-03-25 17:55 +1300
                  Re: Code for strtol/strtoul Tim Rentsch <txr@alumni.caltech.edu> - 2015-03-25 08:43 -0700
                    Re: Code for strtol/strtoul Ian Collins <ian-news@hotmail.com> - 2015-03-26 14:15 +1300
                    Re: Code for strtol/strtoul Tim Rentsch <txr@alumni.caltech.edu> - 2015-03-28 14:53 -0700
                      Re: Code for strtol/strtoul Ian Collins <ian-news@hotmail.com> - 2015-03-29 11:04 +1300
                        Re: Code for strtol/strtoul Tim Rentsch <txr@alumni.caltech.edu> - 2015-03-30 12:34 -0700
                          Re: Code for strtol/strtoul Ian Collins <ian-news@hotmail.com> - 2015-03-31 21:20 +1300
    Re: Code for strtol/strtoul Tim Rentsch <txr@alumni.caltech.edu> - 2015-03-24 22:31 -0700
      Re: Code for strtol/strtoul Ian Collins <ian-news@hotmail.com> - 2015-03-25 19:30 +1300
        Re: Code for strtol/strtoul Tim Rentsch <txr@alumni.caltech.edu> - 2015-03-25 08:24 -0700
    Re: Code for strtol/strtoul jacob navia <jacob@jacob.remcomp.fr> - 2015-03-25 22:43 +0100
      Re: Code for strtol/strtoul Ian Collins <ian-news@hotmail.com> - 2015-03-27 19:18 +1300
      Re: Code for strtol/strtoul Steve Thompson <stevet810@gmail.com> - 2015-03-27 15:02 +0000
        Re: Code for strtol/strtoul jacob navia <jacob@jacob.remcomp.fr> - 2015-03-27 16:10 +0100
          Re: Code for strtol/strtoul Steve Thompson <stevet810@gmail.com> - 2015-03-27 22:44 +0000
          Re: Code for strtol/strtoul raltbos@xs4all.nl (Richard Bos) - 2015-03-29 15:18 +0000
            Re: Code for strtol/strtoul jacob navia <jacob@jacob.remcomp.fr> - 2015-03-29 17:35 +0200
      Re: Code for strtol/strtoul Robert Wessel <robertwessel2@yahoo.com> - 2015-03-28 03:57 -0500
        Re: Code for strtol/strtoul jacob navia <jacob@jacob.remcomp.fr> - 2015-03-28 14:09 +0100
    Re: Code for strtol/strtoul Ian Collins <ian-news@hotmail.com> - 2015-03-28 22:58 +1300
      Re: Code for strtol/strtoul Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-03-28 11:33 +0000
        Re: Code for strtol/strtoul Ian Collins <ian-news@hotmail.com> - 2015-03-29 08:49 +1300
          Re: Code for strtol/strtoul Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-03-28 22:11 +0000
            Re: Code for strtol/strtoul Ian Collins <ian-news@hotmail.com> - 2015-03-29 11:30 +1300

Page 4 of 5 — ← Prev page 1 2 3 [4] 5  Next page →

#58603

On Sat, 21 Mar 2015 12:09:25 +0100, jacob navia
<jacob@jacob.remcomp.fr> wrote:

>After some days working in those functions, I would like to share this 
>work with you. I think discussing C is as interesting as discussing UFOs 
>( :-) ), because there some interesting issues in this code.
>
>What to do with bad inputs? The "ever-green" question of what to do with 
>NULLs pops out.
>
>What to do with unspecified situations? In this case the standard 
>doesn't define a lot of situations.
>
>What to do with weird cases? For instance the sequence
>
>strtol(
>"56724399879677657653445435435456765675755435435432223444465444565466654666ULL",
>&endptr,10);
>
>I developed a formula for calculating the maximum number of digits to 
>read for a number base N. Is that formula correct?
>
>What about other stuff like code readability variable names, whatever.
>
>Thanks in advance for your comments.
>
>jacob
>
>P.S. COPYRIGHT:
>
>This code is my work. If you just read it, you should give me ALL YOUR 
>MONEY (and more, if possible). Anyway even if you do not read it, you
>are doomed since this copyright notice is copyrighted with the same
>rules!
>
>I have done all of this alone. I did NOT have any help from R. 
>Heathfield, that did not point me to the place in the standard where the
>"Ox" was specified, nor to Mr Wessel, that did not point me to test for
>errno when lost between a difference between the hybrid MSVC/gcc mingw
>that confused me completely.


Please send your bank information to my address in Nigeria, and I'll
promptly wire you the requested amount.  And my bank there requires a
fee up front for the transfer, please include that in your letter.

And just the be clear:  You're making a joke, and I'm not responding
to the idiot who's been spoofing your posts?


>Enjoy!
>
>/*----------------------------------------------------------------
>  * strtoul() strtol() - Conversion of a string of base n to a long
>  *
>  * Algorithm: Read into a long long, then reduce the result.
>  * Tested with long in 32 bits only.
>/*---------------------------------------------------------------*/
>#include <ctype.h>
>#include <errno.h>
>#include <limits.h>
>#include <math.h>
>#include <stdlib.h>
>
>static unsigned long Strtoul(const char *input,
>                      char **endptr, int base, int isSignedValue)
>{
>     char nbmax; // The maximum numerical digit that can be read
>     int tbase = 10; // Default base when base is zero
>     int MaxDigits;
>     int ScanSuffix = 0; // Do we scan any suffixes?
>     int ReadSomething=0; // Did we read something in?
>     char sign = 0;   // If negative sign is '-'
>     char cbmax = 0;  // Max digit that can be read for base > 10
>     int digit;       // Digit  read in
>     unsigned long long tvalue;
>     unsigned long long maxval; // Max value that doesn't overflow
>     unsigned long errval;
>     unsigned long long value = 0;
>
>     /* Store nptr into endptr immediately to save its value since
>        we are going to reuse input */
>     if (endptr) *endptr = input;
>
>     /* The value of the "base" argument should be zero or
>     2 <= base <= 36.
>     What happens with negative values of "base" or with base 1?
>     The standard is silent about that. We just do not accept any
>     other values for "base" besides those explicitely allowed
>     */
>     if (base < 0 || base == 1 || base > 36) {
>         errno = ERANGE;
>         return 0;
>     }
>     /* Is it better to crash later when dereferencing a NULL pointer?
>     Or to give just an error now? */
>     if (input == NULL) {
>         errno = ERANGE;
>         return 0;
>     }
>
>     /* C99: 7.20.1.4.2 First, they decompose the input string into
>       three parts:
>     * an initial, possibly empty, sequence of white-space characters
>     * (as specified by the isspace function), ...
>     */
>     while(isspace(*input)) {
>         input++;
>     }
>
>     if((*input == '-') || (*input == '+')) {
>         sign = *input;
>         input++;
>     }
>
>     /* C99: 7.20.1.4.5: If the subject sequence has the expected
>     form and the value of base is zero, the sequence of characters
>     starting with the first digit is interpreted as an integer
>     constant according to the rules of 6.4.4.1.
>     C99: 7.20.1.4.3: If the value of base is 16, the characters
>     0x or 0X may optionally precede the sequence of letters and
>     digits, following the sign if present.
>     */
>     if(*input == '0' && (base == 0 || base == 16)) {
>         if((input[1] == 'X') || (input[1] == 'x')) {
>             tbase = 16;
>             input+=2;
>         }
>         else if (base == 0) {
>             tbase = 8;
>             /* We have read a zero! We MUST bump "ReadSomething"
>                because if not the trivial sequence "0" wouldn't
>                be recognized!! Note that "0x" is NOT a valid
>                sequence so we haven't read anything UNTIL we read
>                a number later
>             */
>             ReadSomething=1;
>             input++;
>         }
>     }
>
>     /* C99: 7.20.1.4.7: If the subject sequence is empty or
>     does not have the expected form, no conversion is performed;
>     the value of nptr is stored in the object pointed to by
>     endptr, provided that endptr is not a null pointer.
>     */
>     if (*input == 0 && ReadSomething == 0)      return 0;
>
>     /* If we set tbase above put its value into base. We must
>     save the fact that if the original base was zero we should
>     look for an eventual suffix. Put that into the ScanSuffix
>     variable. Obviously ScanSuffix could be eliminated and
>     we could set tbase to 4876 say, since its value is no longer
>     used. At the end we could test if tbase is 4876. That would
>     save 4 bytes but make this more unreadable... Not worth */
>
>     if(base == 0) {
>         base = tbase;
>         ScanSuffix = 1;
>     }
>
>     if(base <= 10) {
>         nbmax = (char)((char)'0' + (char)(base - 1));
>     }
>     else {
>         nbmax = '9';
>         cbmax = (char)((char)'a' + (char)(base - 11));
>     }
>     if(isSignedValue) { /* We are returning a signed number */
>         maxval = LONG_MAX;
>         errval = LONG_MAX;
>         if(sign == '-') {
>             maxval = (long long)LONG_MAX+1LL;
>             errval = (unsigned long)LONG_MIN;
>         }
>         else {
>             maxval = LONG_MAX;
>             errval = LONG_MAX;
>         }
>     }
>     else { /* we are returning an unsigned number */
>         maxval = ULONG_MAX;
>         errval = ULONG_MAX;
>     }
>     /*
>     The number of digits for a number in base "base".
>     Assuming 2^base is the maximum number in the given base
>     (in bits), we take the logarithm and divide by the
>     logarithm of the base to get the number of digits.
>     We take the ceiling since in the last position,
>     a whole digit must be read
>     */
>     MaxDigits = (int)
>       (ceil(log(pow(2.0,sizeof(long)*CHAR_BIT))/log(base)));
>
>     /* Preliminary work is ended, we start converting the number */
>     while(*input && ReadSomething <= MaxDigits) {
>         if((*input >= '0') && (*input <= nbmax)) {
>             digit = *input - '0';
>         }
>         else if((*input >= 'a') && (*input <= cbmax)) {
>             digit = (*input - 'a') + 10;
>         }
>         else if((*input >= 'A') &&
>                    (*input <= (char)toupper(cbmax))) {
>             digit = (*input - 'A') + 10;
>         }
>         else { /* invalid char. Stop. */
>             break;
>         }
>         /* The only usage of tvalue is to nicely appear in
>         our debugger to easily follow the computation.
>         It will be eliminated when we KNOW that there are
>         no bugs in left this sofwtare... :-;) */
>         tvalue = (value* (unsigned long)base);
>         value = tvalue + digit;
>         input++;
>         ReadSomething++;
>     }
>     if (*input && ReadSomething > MaxDigits) {
>         /* Ignore all digits */
>         while (((*input >= '0') && (*input <= nbmax)) ||
>             ((*input >= 'a') && (*input <= cbmax)) ||
>             ((*input >= 'A') &&
>                  (*input <= (char)toupper(cbmax)))) {
>             input++;
>         }
>     }
>     if (endptr && ReadSomething && ScanSuffix) {
>         /* Accept U,L, UL, ULL suffixes.
>           All other suffixes are ignored */
>         if (*input == 'u' || *input == 'U') input++;
>         if (*input == 'l' || *input == 'L') input ++;
>         if (*input == 'l' || *input == 'L') input++;
>     }
>     if(endptr != NULL && ReadSomething > 0) {
>         *endptr = input;
>     }
>     if (value > maxval || ReadSomething > MaxDigits) {
>         errno = ERANGE;
>         value = errval;
>     }
>     else if (sign ==  '-') {
>         value = -(value&0xffffffffULL);
>     }
>     return(value);
>}
>
>/*-----------------------------------------------------------*/
>/* strtoul() - convert a string of base n to an unsigned long*/
>/*-----------------------------------------------------------*/
>unsigned long strtoul(const char *input, char **endptr, int base)
>{
>     return(Strtoul(input, endptr, base, 0));
>}
>
>/*-----------------------------------------------------------*/
>/* strtol() - convert a string of base n to a signed long    */
>/*-----------------------------------------------------------*/
>long strtol(const char *input, char **endptr, int base)
>{
>     return(Strtoul(input, endptr, base, 1));
>}


A couple of comments from skimming the code.

It appears that you'll generate the overflow condition whenever the
number of digits exceeds the computed maximum for the base.  But
AFAIK, strtoul("000000000000000000000000000000001", NULL, 0) is
perfectly valid, and should not return a range error.

So at least you'd need to eat any leading zeros before the loop
parsing the number (and after reading the sign).

Second, I don't like your computation of the maximum number of input
digits.  I discovered approximate the same method back in high school
for determining the number of digit positions a number needs to be
displayed.  But it has several problems.  Foremost is that it's not
that accurate, a bit of unavoidable error and you can be off a digit
near the boundaries.  In your case there's a restricted set of inputs
for which this needs to be correct, so you might get away with simply
testing all of the possible input combinations.  Second two logs() and
a pow() are going to be slower than all heck.

If you do want to use the maximum number of digits during your
parsing, I think you'd be much better off simply having a table and
looking up the value in that.  It would certainly be far faster.  This
does introduce the problem of how to vary the table for different
sized longs.

But frankly I think it would be better to just process input digits
and detect overflows along the way.  Something like:


  unsigned long n=0;
  unsigned long t;
  bool overflow=FALSE;
  base = (actual base in use);
  for(;;)
    {
    d=getnextdigit();
    if (...end of input...)
      break;

    t = n;
    n *= base;
    if (n/base != t)
      overflow=TRUE;
   
    n += d;
    if (n < d)
      overflow = TRUE;
  }


That's likely to be significantly faster that the single use of the
log/log/pow function, despite the division in each iteration of the
loop.

Also, that inherently works for any length input string.

An optimization to the overflow check would be:


  unsigned long n=0;
  unsigned long t;
  unsigned long ov = ULONG_MAX/base;
  bool overflow=FALSE;
  base = (actual base in use);
  for(;;)
    {
    d=getnextdigit();
    if (...end of input...)
      break;

    if (n<ov)
      n *= base;  // no overflow possible
    else
      { // overflow possible
      t = n;
      n *= base;
      if (n/base != t)
        overflow=TRUE;
      }
   
    n += d;
    if (n < d)
      overflow = TRUE;
  }


That would perform a single division for most inputs, two divisions if
the input number were close to the maximum, and more than two in the
case of an overflow, which seems quite reasonable.


If you know something about the target machine, namely that unsigned
long long is, in fact, large enough hold the largest possible unsigned
long multiplied by the largest possible base plus the highest value
digit in that base, you can simplify and speed up that loop
considerably:


  unsigned long long n=0;
  bool overflow=FALSE;
  base = (actual base in use);
  for(;;)
    {
    d=getnextdigit();
    if (...end of input...)
      break;

    n *= base;
    n += d;
    if (n > ULONG_MAX)
      overflow=TRUE;
  }


Of course that doesn't help for strtoull().


All of those will continue the multiple/add loop to the end of the
input even if overflow has been detected, but I can't imaging that's a
case in which anyone is going to care about performance too much.
OTOH, you could certainly break out of that loop when you detect the
overflow.

[toc] | [prev] | [next] | [standalone]

#58628

jacob navia wrote:
> After some days working in those functions, I would like to share this
> work with you. I think discussing C is as interesting as discussing UFOs
> ( :-) ), because there some interesting issues in this code.

By strange coincidence, I had been working a simple, limited (only clean 
decimal and hex conversions) version of these function for a resource 
constrained environment.  Just for fun this afternoon I knocked up a 
full version (including the long long functions) using TDD.

You'll be pleased to know that your version passed all the tests!

-- 
Ian Collins

[toc] | [prev] | [next] | [standalone]

#58728

On 2015-03-22, Ian Collins <ian-news@hotmail.com> wrote:
> jacob navia wrote:
>> After some days working in those functions, I would like to share this
>> work with you. I think discussing C is as interesting as discussing UFOs
>> ( :-) ), because there some interesting issues in this code.
>
> By strange coincidence, I had been working a simple, limited (only clean 
> decimal and hex conversions) version of these function for a resource 
> constrained environment.  Just for fun this afternoon I knocked up a 
> full version (including the long long functions) using TDD.
>
> You'll be pleased to know that your version passed all the tests!

Which only proves that the testset is incomplete.

[toc] | [prev] | [next] | [standalone]

#58729

On 23/03/15 09:40, Ike Naar wrote:
> On 2015-03-22, Ian Collins <ian-news@hotmail.com> wrote:

<snip>

>> Just for fun this afternoon I knocked up a
>> full version (including the long long functions) using TDD.
>>
>> You'll be pleased to know that your version passed all the tests!
>
> Which only proves that the testset is incomplete.

This should not surprise you. In one of the most important 
TDD-theoretical results of the 20th century, Gurt Koerdel proved that 
/any/ sufficiently powerful testset is either incomplete or inconsistent.

-- 
Richard Heathfield
Email: rjh at cpax dot org dot uk
"Usenet is a strange place" - dmr 29 July 1999
Sig line 4 vacant - apply within

[toc] | [prev] | [next] | [standalone]

#58733

Richard Heathfield wrote:

> On 23/03/15 09:40, Ike Naar wrote:
>> On 2015-03-22, Ian Collins <ian-news@hotmail.com> wrote:
> 
> <snip>
> 
>>> Just for fun this afternoon I knocked up a
>>> full version (including the long long functions) using TDD.
>>>
>>> You'll be pleased to know that your version passed all the tests!
>>
>> Which only proves that the testset is incomplete.
> 
> This should not surprise you. In one of the most important
> TDD-theoretical results of the 20th century, Gurt Koerdel proved that
> /any/ sufficiently powerful testset is either incomplete or inconsistent.

His colleague Edzel Murphy showed that both conditions are always fulfilled. 

-- 
Reinhardt

[toc] | [prev] | [next] | [standalone]

#58815

Richard Heathfield wrote:
> On 23/03/15 09:40, Ike Naar wrote:
>> On 2015-03-22, Ian Collins <ian-news@hotmail.com> wrote:
>
> <snip>
>
>>> Just for fun this afternoon I knocked up a
>>> full version (including the long long functions) using TDD.
>>>
>>> You'll be pleased to know that your version passed all the tests!
>>
>> Which only proves that the testset is incomplete.
>
> This should not surprise you. In one of the most important
> TDD-theoretical results of the 20th century, Gurt Koerdel proved that
> /any/ sufficiently powerful testset is either incomplete or inconsistent.
>

No. It proves nothing of the sort. Exhaustive proof of digital
algorithms isn't *easy*, but it's far from impossible. A given
digital system or subset of a digital system is far from uncountable.

Godel's  work concerns deriving "all of mathematics" from, nominally,
the Peano Postulates.

I've proven things correct before, using test rigs ( and a well-defined
set of constraints that were also checked - principally that event 
interarrivals were bounded in time ) . I don't recommend it,
but it was appropriate at the time. And C.A.R. Tony Hoare is really The
Guy for this.

-- 
Les Cargill

[toc] | [prev] | [next] | [standalone]

#58819

On 24/03/15 01:29, Les Cargill wrote:
> Richard Heathfield wrote:
>> On 23/03/15 09:40, Ike Naar wrote:
>>>
>>> Which only proves that the testset is incomplete.
>>
>> This should not surprise you. In one of the most important
>> TDD-theoretical results of the 20th century, Gurt Koerdel proved that
>> /any/ sufficiently powerful testset is either incomplete or inconsistent.
>>
>
> No. It proves nothing of the sort.

Whoooooosh! Never mind.

<snip>


-- 
Richard Heathfield
Email: rjh at cpax dot org dot uk
"Usenet is a strange place" - dmr 29 July 1999
Sig line 4 vacant - apply within

[toc] | [prev] | [next] | [standalone]

#58732

On Mon, 23 Mar 2015 09:40:57 +0000 (UTC), Ike Naar
<ike@iceland.freeshell.org> wrote:

>On 2015-03-22, Ian Collins <ian-news@hotmail.com> wrote:
>> jacob navia wrote:
>>> After some days working in those functions, I would like to share this
>>> work with you. I think discussing C is as interesting as discussing UFOs
>>> ( :-) ), because there some interesting issues in this code.
>>
>> By strange coincidence, I had been working a simple, limited (only clean 
>> decimal and hex conversions) version of these function for a resource 
>> constrained environment.  Just for fun this afternoon I knocked up a 
>> full version (including the long long functions) using TDD.
>>
>> You'll be pleased to know that your version passed all the tests!
>
>Which only proves that the testset is incomplete.


Actually it doesn't.  We knew that already.  OTOH, the back-handed
implication that there *must* be bugs in the tested routine is also
false.

[toc] | [prev] | [next] | [standalone]

#58775

Ike Naar wrote:
> On 2015-03-22, Ian Collins <ian-news@hotmail.com> wrote:
>> jacob navia wrote:
>>> After some days working in those functions, I would like to share this
>>> work with you. I think discussing C is as interesting as discussing UFOs
>>> ( :-) ), because there some interesting issues in this code.
>>
>> By strange coincidence, I had been working a simple, limited (only clean
>> decimal and hex conversions) version of these function for a resource
>> constrained environment.  Just for fun this afternoon I knocked up a
>> full version (including the long long functions) using TDD.
>>
>> You'll be pleased to know that your version passed all the tests!
>
> Which only proves that the testset is incomplete.

What did I miss?

-- 
Ian Collins

[toc] | [prev] | [next] | [standalone]

#58800

On 2015-03-23, Ian Collins <ian-news@hotmail.com> wrote:
> Ike Naar wrote:
>> On 2015-03-22, Ian Collins <ian-news@hotmail.com> wrote:
>>> jacob navia wrote:
>>>> After some days working in those functions, I would like to share this
>>>> work with you. I think discussing C is as interesting as discussing UFOs
>>>> ( :-) ), because there some interesting issues in this code.
>>>
>>> By strange coincidence, I had been working a simple, limited (only clean
>>> decimal and hex conversions) version of these function for a resource
>>> constrained environment.  Just for fun this afternoon I knocked up a
>>> full version (including the long long functions) using TDD.
>>>
>>> You'll be pleased to know that your version passed all the tests!
>>
>> Which only proves that the testset is incomplete.
>
> What did I miss?

Elsethread bugs in the code were pointed out.
Code that passed all the tests.

[toc] | [prev] | [next] | [standalone]

#58817

Ike Naar wrote:
> On 2015-03-23, Ian Collins <ian-news@hotmail.com> wrote:
>> Ike Naar wrote:
>>> On 2015-03-22, Ian Collins <ian-news@hotmail.com> wrote:
>>>> jacob navia wrote:
>>>>> After some days working in those functions, I would like to share this
>>>>> work with you. I think discussing C is as interesting as discussing UFOs
>>>>> ( :-) ), because there some interesting issues in this code.
>>>>
>>>> By strange coincidence, I had been working a simple, limited (only clean
>>>> decimal and hex conversions) version of these function for a resource
>>>> constrained environment.  Just for fun this afternoon I knocked up a
>>>> full version (including the long long functions) using TDD.
>>>>
>>>> You'll be pleased to know that your version passed all the tests!
>>>
>>> Which only proves that the testset is incomplete.
>>
>> What did I miss?
>
> Elsethread bugs in the code were pointed out.
> Code that passed all the tests.

Um, you're correct, it did fail a test, this one:

void
TestConversion::testSuccessfulConversionSetsEndPointerToFinalString()
{
   char* p = nullptr;
   const char* in = "123ul";

   auto result = UnsignedFn( in, &p, 0 );

   TS_ASSERT_EQUALS( "ul", p );
}

(UnsignedFn is a compile time macro so I can use the same tests for the 
long and long long functions, which Jacob hasn't implemented.)

I lost the failure in the noise (my version sets errno to EINVAL if the 
base or string are invalid.  So there a number of "failures" with 
Jacob's version.

Jacob's version also has a number of failures if built 64 bit on a Unix 
system.  Possibly due to this line:

              maxval = (long long)LONG_MAX+1LL;

given LONG_MAX == LLONG_MAX on an LP64 system.

-- 
Ian Collins

[toc] | [prev] | [next] | [standalone]

#58891

Ian Collins <ian-news@hotmail.com> writes:

> Ike Naar wrote:
>> On 2015-03-23, Ian Collins <ian-news@hotmail.com> wrote:
>>> Ike Naar wrote:
>>>> On 2015-03-22, Ian Collins <ian-news@hotmail.com> wrote:
>>>>> jacob navia wrote:
>>>>>> After some days working in those functions, I would like to
>>>>>> share this work with you.  I think discussing C is as
>>>>>> interesting as discussing UFOs ( :-) ), because there some
>>>>>> interesting issues in this code.
>>>>>
>>>>> By strange coincidence, I had been working a simple, limited
>>>>> (only clean decimal and hex conversions) version of these
>>>>> function for a resource constrained environment.  Just for fun
>>>>> this afternoon I knocked up a full version (including the long
>>>>> long functions) using TDD.
>>>>>
>>>>> You'll be pleased to know that your version passed all the
>>>>> tests!
>>>>
>>>> Which only proves that the testset is incomplete.
>>>
>>> What did I miss?
>>
>> Elsethread bugs in the code were pointed out.
>> Code that passed all the tests.
>
> Um, you're correct, it did fail a test, this one:
>
> void
> TestConversion::testSuccessfulConversionSetsEndPointerToFinalString()
> {
>   char* p = nullptr;
>   const char* in = "123ul";
>
>   auto result = UnsignedFn( in, &p, 0 );
>
>   TS_ASSERT_EQUALS( "ul", p );
> }
>
> (UnsignedFn is a compile time macro so I can use the same tests
> for the long and long long functions, which Jacob hasn't
> implemented.)

Does that mean you missed this definition in his code?

    /*-----------------------------------------------------------*/
    /* strtol() - convert a string of base n to a signed long    */
    /*-----------------------------------------------------------*/
    long strtol(const char *input, char **endptr, int base)
    {
        return(Strtoul(input, endptr, base, 1));
    }


> I lost the failure in the noise (my version sets errno to EINVAL
> if the base or string are invalid.  So there a number of
> "failures" with Jacob's version.

Were there any other real failures?  There should have been
at least one, assuming you were trying to test for a fully
conforming implementation of strtoul().

[toc] | [prev] | [next] | [standalone]

#58893

Tim Rentsch wrote:
> Ian Collins <ian-news@hotmail.com> writes:

>> void
>> TestConversion::testSuccessfulConversionSetsEndPointerToFinalString()
>> {
>>    char* p = nullptr;
>>    const char* in = "123ul";
>>
>>    auto result = UnsignedFn( in, &p, 0 );
>>
>>    TS_ASSERT_EQUALS( "ul", p );
>> }
>>
>> (UnsignedFn is a compile time macro so I can use the same tests
>> for the long and long long functions, which Jacob hasn't
>> implemented.)
>
> Does that mean you missed this definition in his code?
>
>      /*-----------------------------------------------------------*/
>      /* strtol() - convert a string of base n to a signed long    */
>      /*-----------------------------------------------------------*/
>      long strtol(const char *input, char **endptr, int base)
>      {
>          return(Strtoul(input, endptr, base, 1));
>      }

No, it mean I use one set of tests for strol and strtoll, building with 
different macro definitions for the functions and an the min and max 
values.  For example one build would be:

CC -c -DSignedFn=strtoll -DSignedMax=LLONG_MAX -DSignedMin=LLONG_MIN 
-DUnsignedFn=strtoull -DUnsignedMax=ULLONG_MAX TestConversion.cc

and the other

CC -c -DSignedFn=strtol -DSignedMax=LONG_MAX -DSignedMin=LONG_MIN 
-DUnsignedFn=strtoul -DUnsignedMax=ULONG_MAX TestConversion.cc

>> I lost the failure in the noise (my version sets errno to EINVAL
>> if the base or string are invalid.  So there a number of
>> "failures" with Jacob's version.
>
> Were there any other real failures?  There should have been
> at least one, assuming you were trying to test for a fully
> conforming implementation of strtoul().

I'm interested in knowing what I missed!

-- 
Ian Collins

[toc] | [prev] | [next] | [standalone]

#58919

Ian Collins <ian-news@hotmail.com> writes:

> Tim Rentsch wrote:
>> Ian Collins <ian-news@hotmail.com> writes:
>> [snip]
>> 
>>> I lost the failure in the noise (my version sets errno to EINVAL
>>> if the base or string are invalid.  So there a number of
>>> "failures" with Jacob's version.
>>
>> Were there any other real failures?  There should have been
>> at least one, assuming you were trying to test for a fully
>> conforming implementation of strtoul().
>
> I'm interested in knowing what I missed!

I'm deferring an answer on this until after I get my
own version written.  (Also does this mean you didn't
see any other real failures in Jacob's version?)

[toc] | [prev] | [next] | [standalone]

#58995

Tim Rentsch wrote:
> Ian Collins <ian-news@hotmail.com> writes:
>
>> Tim Rentsch wrote:
>>> Ian Collins <ian-news@hotmail.com> writes:
>>> [snip]
>>>
>>>> I lost the failure in the noise (my version sets errno to EINVAL
>>>> if the base or string are invalid.  So there a number of
>>>> "failures" with Jacob's version.
>>>
>>> Were there any other real failures?  There should have been
>>> at least one, assuming you were trying to test for a fully
>>> conforming implementation of strtoul().
>>
>> I'm interested in knowing what I missed!
>
> I'm deferring an answer on this until after I get my
> own version written.  (Also does this mean you didn't
> see any other real failures in Jacob's version?)

Several when built for 64 bit on an LP64 (Unix) system.

-- 
Ian Collins

[toc] | [prev] | [next] | [standalone]

#59170

Tim Rentsch <txr@alumni.caltech.edu> writes:

> Ian Collins <ian-news@hotmail.com> writes:
>
>> Tim Rentsch wrote:
>>> Ian Collins <ian-news@hotmail.com> writes:
>>> [snip]
>>>
>>>> I lost the failure in the noise (my version sets errno to
>>>> EINVAL if the base or string are invalid.  So there a number
>>>> of "failures" with Jacob's version.
>>>
>>> Were there any other real failures?  There should have been
>>> at least one, assuming you were trying to test for a fully
>>> conforming implementation of strtoul().
>>
>> I'm interested in knowing what I missed!
>
> I'm deferring an answer on this until after I get my
> own version written.

Now that I've done that I've taken a look at the code you posted
(along with the one update posted 26 Mar 2015 14:22:05 +1300,
assuming I understood what you were getting at with the
description).  There were a handful of defects.  I didn't
keep careful track because they sometimes interfered with
each other (at least in my testing harness), but here are
ones I remember:

  octal integer constants in base 0 (fixed in the update I guess)
  wrong end pointer for overly large values
  took the "no number" return in some cases (which showed up as
     having wrong end pointer value stored)
  some mistakes in identifying out-of-range (wrong value given,
     and errno not set)
  value returned for one of the unsigned versions when string
     has a leading - sign

The particular case I noticed from early on is an
input string "0x" in base 0 or base 16, which is a valid
numeric input, not a "no number" result.  IIRC correctly
the code of yours I tested first got one of these wrong
but not both (don't ask me how!).

[toc] | [prev] | [next] | [standalone]

#59173

Tim Rentsch wrote:
> Tim Rentsch <txr@alumni.caltech.edu> writes:
>
>> Ian Collins <ian-news@hotmail.com> writes:
>>
>>> Tim Rentsch wrote:
>>>> Ian Collins <ian-news@hotmail.com> writes:
>>>> [snip]
>>>>
>>>>> I lost the failure in the noise (my version sets errno to
>>>>> EINVAL if the base or string are invalid.  So there a number
>>>>> of "failures" with Jacob's version.
>>>>
>>>> Were there any other real failures?  There should have been
>>>> at least one, assuming you were trying to test for a fully
>>>> conforming implementation of strtoul().
>>>
>>> I'm interested in knowing what I missed!
>>
>> I'm deferring an answer on this until after I get my
>> own version written.
>
> Now that I've done that I've taken a look at the code you posted
> (along with the one update posted 26 Mar 2015 14:22:05 +1300,
> assuming I understood what you were getting at with the
> description).  There were a handful of defects.  I didn't
> keep careful track because they sometimes interfered with
> each other (at least in my testing harness), but here are
> ones I remember:
>
>    octal integer constants in base 0 (fixed in the update I guess)

Fixed in current version.

>    wrong end pointer for overly large values

Fixed in current version.

>    took the "no number" return in some cases (which showed up as
>       having wrong end pointer value stored)

Test case?

>    some mistakes in identifying out-of-range (wrong value given,
>       and errno not set)

Test case?

>    value returned for one of the unsigned versions when string
>       has a leading - sign

Fixed in current version.

-- 
Ian Collins

[toc] | [prev] | [next] | [standalone]

#59300

Ian Collins <ian-news@hotmail.com> writes:

> Tim Rentsch wrote:
>> Tim Rentsch <txr@alumni.caltech.edu> writes:
>>
>>> Ian Collins <ian-news@hotmail.com> writes:
>>>
>>>> Tim Rentsch wrote:
>>>>> Ian Collins <ian-news@hotmail.com> writes:
>>>>> [snip]
>>>>>
>>>>>> I lost the failure in the noise (my version sets errno to
>>>>>> EINVAL if the base or string are invalid.  So there a number
>>>>>> of "failures" with Jacob's version.
>>>>>
>>>>> Were there any other real failures?  There should have been
>>>>> at least one, assuming you were trying to test for a fully
>>>>> conforming implementation of strtoul().
>>>>
>>>> I'm interested in knowing what I missed!
>>>
>>> I'm deferring an answer on this until after I get my
>>> own version written.
>>
>> Now that I've done that I've taken a look at the code you posted
>> (along with the one update posted 26 Mar 2015 14:22:05 +1300,
>> assuming I understood what you were getting at with the
>> description).  There were a handful of defects.  I didn't
>> keep careful track because they sometimes interfered with
>> each other (at least in my testing harness), but here are
>> ones I remember [some snipped]:
>>
>>    took the "no number" return in some cases (which showed up as
>>       having wrong end pointer value stored)
>
> Test case?
>
>>    some mistakes in identifying out-of-range (wrong value given,
>>       and errno not set)
>
> Test case?

I wrote these down from memory, I don't have test cases
handy.  But you should be able to find some easily
enough by saturation testing near the boundaries (ie,
of short sequences and values near the respective numerical
limits), comparing results to what the functions in glibc
do.

[toc] | [prev] | [next] | [standalone]

#59334

Tim Rentsch wrote:
> Ian Collins <ian-news@hotmail.com> writes:
>
>> Tim Rentsch wrote:
>>>
>>> Now that I've done that I've taken a look at the code you posted
>>> (along with the one update posted 26 Mar 2015 14:22:05 +1300,
>>> assuming I understood what you were getting at with the
>>> description).  There were a handful of defects.  I didn't
>>> keep careful track because they sometimes interfered with
>>> each other (at least in my testing harness), but here are
>>> ones I remember [some snipped]:
>>>
>>>     took the "no number" return in some cases (which showed up as
>>>        having wrong end pointer value stored)
>>
>> Test case?
>>
>>>     some mistakes in identifying out-of-range (wrong value given,
>>>        and errno not set)
>>
>> Test case?
>
> I wrote these down from memory, I don't have test cases
> handy.  But you should be able to find some easily
> enough by saturation testing near the boundaries (ie,
> of short sequences and values near the respective numerical
> limits), comparing results to what the functions in glibc
> do.

I test with string values one more than the max signed limits and one 
less then the min signed limit.

-- 
Ian Collins

[toc] | [prev] | [next] | [standalone]

#58894

jacob navia <jacob@jacob.remcomp.fr> writes:

> After some days working in those functions, I would like to share
> this work with you [snip], because there some interesting issues
> in this code.

An outstanding programming exercise.  Implementing strtoul()
and friends is not nearly as easy as it might seem.

> What to do with bad inputs?  [eg, NULL]

An easy question, but not necessarily an easy answer.  In cases
where there is undefined behavior, you might abort, or return a
special value (with an errno setting), or have an option for
choosing one or the other (eg, by setting an environment variable).
The main thing is to do _something_ reliably whenver that is
possible.

> What to do with unspecified situations?  In this case the standard
> doesn't define a lot of situations.

Besides cases of undefined behavior, is there any leeway
in what the functions should do?  I had thought there
might be some choice in possibly setting errno, but under
the restrictions of 7.5 p3 I'm not sure that's allowed
here (not counting cases where the behavior is undefined).
Can you list what the different cases are, and what you
think the choices are in each case?

> What to do with weird cases?  For instance the sequence
>
> strtol(
> "56724399879677657653445435435456765675755435435432223444465444565466654666ULL",
> &endptr,10);

AFAIK the behavior in this case is completely specified (namely,
the return value is LONG_MAX, 'endptr' is set to point to the 'U'
character, and errno is set to ERANGE).  Do you have a different
reading?

> I developed a formula for calculating the maximum number of digits to
> read for a number base N.  Is that formula correct?

I didn't look at the formula closely because I think it's
easier and better to code around it.  It's possible a
conservative estimate might give a performance gain in
some common cases, but an exact formula (with floating
point and everything) just seems like more trouble than
help.

> What about other stuff like code readability variable names,
> whatever.

My main reaction on this question is that what's going on is
hard to follow/comprehend because the central function is
way too long.  I can be more specific and also could provide
comments on some other aspects if you are interested.

> [11 miscellaneous lines]
>
> static unsigned long Strtoul(const char *input,
>                      char **endptr, int base, int isSignedValue)
> {
>     [179 lines of function body]
> }
>
> /*-----------------------------------------------------------*/
> /* strtoul() - convert a string of base n to an unsigned long*/
> /*-----------------------------------------------------------*/
> unsigned long strtoul(const char *input, char **endptr, int base)
> {
>     return(Strtoul(input, endptr, base, 0));
> }
>
> /*-----------------------------------------------------------*/
> /* strtol() - convert a string of base n to a signed long    */
> /*-----------------------------------------------------------*/
> long strtol(const char *input, char **endptr, int base)
> {
>     return(Strtoul(input, endptr, base, 1));
> }

Minor remark - the implicit reliance on how the type conversion
works in strtol() deserves at least a comment.  Even better would
be to write the code so it is implementation-independent, or at
least more independent of implementation than it is now.

[toc] | [prev] | [next] | [standalone]

Page 4 of 5 — ← Prev page 1 2 3 [4] 5  Next page →

Back to top | Article view | comp.lang.c

csiph-web