Comment On The Magnitude of Ineptitude

Actually, the use of shifts to do the (fast m* 10) is not particularly unusual, since m is a long and this is an "embedded" target. A fair number of 16bit micros don't have long multiplication in hardware, and if one of the two numbers is fixed a significant speed gain can be had by unrolling it to shifts vs. calling a library function to do it. Additionally, such lib functions are almost never reentrancy-safe, so they call all manner of bad things if you have interrupts.

 
I know we're all used to assuming the compiler will do this sort of transformation, but platforms that don't have long multiply don't tend to have particularly stellar compilers either :-)

This is what happens when you give assembly programmers a C compiler.

I was beaten to it, but yeah, the TRUE WTF is that the article writer thought the multiply by 10 was a WTF.

we have (2^3)*m + 2*m = 10*m.



Makes perfect sense.

 

Oh yeah, and I like the comment that the bias on rand to 0 is non-linear. Please show us the other 8 files.

long atoi(char *s){
   if (s == NULL)
     return -1;

   char *p = s + 1;
   int Acum = 0;

   while(*p){
   /* I used an unsigned char because to a computer -1(255)
   is greater 0*/ 

      unsigned char = *p - '0';
      if (value >= 9)
         return -1;
      Acum = (Acum * 10) + value;
p++;
   }

   if (*s == '-')
      Acum = -Acum;

   return Acum;

}

and by the way the stdc libaray version causes a memory violation when passed NULL.

Anonymous:

This is what happens when you give assembly programmers a C compiler.

Hardly. This code uses 12 bytes of local variables (assuming points are 2 bytes), which is truly wasteful if your target has limited ram and can't put locals on the stack due to not having relative addressing hardware.

A true embedded or assembly programmer would do it all in a couple of variables, which would just fit in the registers.

 /Had to do itoa on several platforms.
 

 

 

Anonymous:

This is what happens when you give assembly programmers a C compiler.

And actually I think I'll change the string to BCDs then use some inline assembly to convert it back to integer, and apply 2's compliment when applicable.

 And seasoned assembly language programmers should be able to done better than that.
 

int atoi(char s[])

What I really love about this is how he performs a multiplication the normal way (and possibly the slow way for the embedded device) and then uses the faster method for multiplying the multiplier.  Extremely inefficient. 

 

CAPTCHA: 1337

I think NOT! 

brendan: That is still not a legal atoi. It's supposed to allow isspace() characters at the beginning and optional +/-. Also, if it hits any non-digit after that, that's considered to be the end of the string. Here is an example of a conforming atoi function

int atoi(const char *s) {
    int n = 0;
    char sign = 0;
    unsigned int digit;
    while (isspace(*s))
        s++;
    if (*s == '+' || *s == '-')
        sign = *s++;
    while ((digit = *s - '0') < 10) {
        n = n * 10 + digit;
        s++;
    }
    if (sign == '-') n = -n;
    return n;
}

Anonymous:

I know we're all used to assuming the compiler will do this sort of
transformation, but platforms that don't have long multiply don't tend
to have particularly stellar compilers either :-)

Amen! Preach it, brother. ;-)

This
code is aimed at one goal, and only one goal. The WTF is, imho, to
claim ANSI compliance. The routine is capable of parsing numbers which
are embedded into, say, a config file for the target which is generated
by a tool so it would be a good assumption to think these numbers to be
correct.

I would not like to bash the author without full
knowledge of what the code was supposed to do and what platform was
beneath it. As one poster put it : "this happens when you give an
assembly...", well, i much more prefer this code to the code i see from
ppl. who think that setting the target to "CE" in the VisuHell IDE and
clicking "compile" was all you needed for embedded systems. That's when
you see "printf("irq %d called, time in irq: %f\n", iIrqNum,
fIrqTime);"  (almost quote) in the driver source codes.

--

One KB of RAM is enough for every toaster

cheesy:

Anything wrong with the implementation in K&R?

did you test this code?

 it not only doesn't compile, it returns incorrect results.

atoi( "1" ), returns 0 with this code.

I don't get reasons of not implementing standard functions in libraries. They are still there, eating RAM and CPU cycles and introducing new bugs. Why not give one good implementation instead of many ugly ones?

I am just happy that with Java I will never have to port any standard functions to another platform. Thank you Mr. Gosling.

I think the title for this posting is unjust. The code clearly shows signs of useful activity in the author's brain while it was being written, even though it is far from optimal and not ANSI-compliant.

It's those who cannot understand m=(m<<3)+(m<<1) who should not be programming.

Performance vs readability tradeoff is common, and you don't know what kind of platform it was. We were told "embedded". And by the way, who said it was expected to be ANSI-compliant?

 

Goplat:

cheesy:

Anything wrong with the implementation in K&R?

That's legal, though probably not as fast as mine ;)

of course isspace could be replaced with (s[i] == ' ' || s[i] == '\n' || s[i] == '\t') etc

oops a couple of thing I forgot

long atoi(char *s){
   if (s == NULL)
      return -1;

   char *p = s;

   int Acum = 0; 

   while(isspace(*p++));

   if ((*p == '-') || (*p == '+'))
      p++;

   while(*p){
   /* I used an unsigned char because to a computer -1(255)
   is greater 0*/ 

     unsigned char = *p - '0';
     if (value >= 9)
         break;
     Acum = (Acum * 10) + value;
     p++;
   }

   if (*s == '-')
     return (long)-Acum;
   else
     return (long)Acum;

}

Tim Gallagher:

In this implementation of atoi you need to be totally certain what you give the function has a valid integer representation (and nothing extra!) or you're hosed. To put it plainly, you need to know the result before attempting to get the result.

You may not believe this but the ISO C standard is pretty clear on this point.

 7.20.1: [...] If the value of the result cannot be represented, the behavior is undefined.

 

brendan:

   if (s == NULL)
     return -1;

 

@brendan: That  is a bad style. The (historical) philosophy for plain old stdlibc functions is: Don't check for errors. K&R said that the programer has to check parameters for him self. The stdlibc must be fast.

 But anyway: Returning "-1" for a atoi function is wrong since the result is a correct value. Better would be something like

{

    char *p; p=0; *p=0; 

}
 

regards.

Ottokar:

Better would be something like

{

    char *p; p=0; *p=0; 

}

True, crashing would have to be an improvement wouldn't it. 

DaBookshah:

I was beaten to it, but yeah, the TRUE WTF is that the article writer thought the multiply by 10 was a WTF. we have (2^3)*m + 2*m = 10*m. Makes perfect sense.

Except that just about every compiler does this optimization for you when it makes sense. On the other hand if multiplying is faster on an architecture than a set of shifts and adds, chances are the compiler isn't anymore capable of making a cow out of a hamburger. Premature optimization at its finest.

Anonymous:

I think the title for this posting is unjust. The code clearly shows signs of useful activity in the author's brain while it was being written, even though it is far from optimal and not ANSI-compliant.

It's those who cannot understand m=(m<<3)+(m<<1) who should not be programming.

Performance vs readability tradeoff is common, and you don't know what kind of platform it was. We were told "embedded". And by the way, who said it was expected to be ANSI-compliant?

 

I don't really understand that expression (although I do program). Can anyone enlighten me? 

Anonymous:

What I really love about this is how he performs a multiplication the normal way (and possibly the slow way for the embedded device) and then uses the faster method for multiplying the multiplier.  Extremely inefficient. 

The "faster way" here can only be used when one of the multiplicands is a constant (in this case, 10). When neither multiplicand is constant, you don't know what shifts and adds to use.

It goes without saying that hand-tooled shifts and adds would also be the best way of writing a multiplication when both multiplicands are constant.

Quincy5:

don't really understand that expression (although I do program). Can anyone enlighten me? 

See post 101120

 

Anonymous:

You may not believe this but the ISO C standard is pretty clear on this point.

 7.20.1: [...] If the value of the result cannot be represented, the behavior is undefined.

That refers to overflow. The result is well defined in cases like "123adsf", it's 123 and can thus be represented by an int. The standard isn't trivial reading. Sometimes you need to look at other paragraphs as well.

while(isspace(*p++));

No, no, no, no, no....

This will leave p pointing to the second non-whitespace character.

It should be:

while(isspace(*p)) p++;

 

Also... embedded compilers vary in quality - some are very very crude. I have even used ones that produce invalid code if you turn on optimization!!  There is nothing wrong with using m = (m<<3) + (m<<1) if you know that your compiler won't do better. Most embedded system compilers let you examine their output assembler so you could judge this quite easily.

 

Quincy5:

Anonymous:

I think the title for this posting is unjust. The code clearly shows signs of useful activity in the author's brain while it was being written, even though it is far from optimal and not ANSI-compliant.

It's those who cannot understand m=(m<<3)+(m<<1) who should not be programming.

Performance vs readability tradeoff is common, and you don't know what kind of platform it was. We were told "embedded". And by the way, who said it was expected to be ANSI-compliant?

 

I don't really understand that expression (although I do program). Can anyone enlighten me? 

 

The "<<" is bit-shifting. That is, simply put: pad a number of 0-bits to the binary number. The number before the "<<" is the number to pad the bits to, the number to it's right is the number of bits to pad.

For instance:

5 (binary 101b) << 1 will become 1010b (pad 1 0-bit)

5 (binary 101b) << 2 will become 10100b (pad 2 0-bits)

etc.

Now, if you concider how to translate binary numbers to decimal numbers, it makes sense that (m << n) equals m*(2 to the power of n).

For instance take the number 101b. If we translate it to decimal, we get (2 to the power of 2) + (2 to the power of 1). If you don't know how to translate binary to decimal, look that up first. Now if we add a 0-bit extra, all we have to change is that is increase the powers. So 1010b will become: (2 to the power of 3)+(2 to the power of 2) = (2 to the power of 1)*((2 to the power of 2)+(2 to the power of 1)) = (2 to the power of 1)*101b.

So: m=(m<<3) +(m<<1) = m*(2 to the power of 3) + m*(2 to the power of 1) = m*8 + m*2 = m*(8+2) = m*10

 

 

Although I doubt that it'll make more sense after reading this post... 

Quincy5:

Anonymous:

It's those who cannot understand m=(m<<3)+(m<<1) who should not be programming.

I don't really understand that expression (although I do program). Can anyone enlighten me? 

The shift operator is a kind of mulitpling. For example:

nt x = 1357;   // Bitmuster: 00000000000000000000010101001101
int y = x << 2; // Bitmuster: 00000000000000000001010100110100

That means:

Value x << 1 means "1 * 2"

Value x <<2 means "1 * 4"

value x <<3 means "1 * 8"

and m=(m<<3)+(m<<1) means "m * 10". Since mulitplying with 10 isn't possible with shift operators the programer wrote "(m * 8) + ( m * 2)".

The
idea is that the shift operator could me much faster than multiplying.
The danger is that this might not work for all platforms. It isn't
human readable too and it might be not portable for platforms with
different integer lens or integer types (16bit-system vs. 64bit-system).

Nowadays
people need the shift operator very seldom. Compilers makes such
optimization for them self. But it might be useful on embedded
platforms. They use oft ancient compilers and slow CPUs.

Regards

Well, of course it means

value "x << 1" means "x * 2"

value "x << 2" means "x * 4"

 and so on.
 

Anonymous:

Quincy5:

Anonymous:

I think the title for this posting is unjust. The code clearly shows signs of useful activity in the author's brain while it was being written, even though it is far from optimal and not ANSI-compliant.

It's those who cannot understand m=(m<<3)+(m<<1) who should not be programming.

Performance vs readability tradeoff is common, and you don't know what kind of platform it was. We were told "embedded". And by the way, who said it was expected to be ANSI-compliant?

 

I don't really understand that expression (although I do program). Can anyone enlighten me? 

 

The "<<" is bit-shifting. That is, simply put: pad a number of 0-bits to the binary number. The number before the "<<" is the number to pad the bits to, the number to it's right is the number of bits to pad.

For instance:

5 (binary 101b) << 1 will become 1010b (pad 1 0-bit)

5 (binary 101b) << 2 will become 10100b (pad 2 0-bits)

etc.

Now, if you concider how to translate binary numbers to decimal numbers, it makes sense that (m << n) equals m*(2 to the power of n).

For instance take the number 101b. If we translate it to decimal, we get (2 to the power of 2) + (2 to the power of 1). If you don't know how to translate binary to decimal, look that up first. Now if we add a 0-bit extra, all we have to change is that is increase the powers. So 1010b will become: (2 to the power of 3)+(2 to the power of 2) = (2 to the power of 1)*((2 to the power of 2)+(2 to the power of 1)) = (2 to the power of 1)*101b.

So: m=(m<<3) +(m<<1) = m*(2 to the power of 3) + m*(2 to the power of 1) = m*8 + m*2 = m*(8+2) = m*10

 

 

Although I doubt that it'll make more sense after reading this post... 

 

Woops, made a mistake here:

For instance take the number 101b. If we translate it to decimal, we
get (2 to the power of 2) + (2 to the power of 1). If you don't know
how to translate binary to decimal, look that up first. Now if we add a
0-bit extra, all we have to change is that is increase the powers. So
1010b will become: (2 to the power of 3)+(2 to the power of 2) = (2 to
the power of 1)*((2 to the power of 2)+(2 to the power of 1)) = (2 to
the power of 1)*101b.

 

Replace the 101b's with 110b...

 

Captcha: [lacking] quality
 

The left shift operator is like when in decimal we multiply by 100. Say you want to multiply 12 by 100, you simply throw 2 zeroes in front of the 12, to make 1200. So to left shift by 2 in binary means to put two zeroes in front of your number, which multiplies it by 2^2, or 4. It can be a lot quicker to shift a number rather than do the multiplication, like its easier to put 2 zeroes in front instead of writing it down on paper and multiplying it out like you might have to if you were multiplying by 36.

captcha: whiskey tango foxtrot 

Anonymous:

DaBookshah:

I was beaten to it, but yeah, the TRUE WTF is that the article writer thought the multiply by 10 was a WTF. we have (2^3)*m + 2*m = 10*m. Makes perfect sense.

Except that just about every compiler does this optimization for you when it makes sense. On the other hand if multiplying is faster on an architecture than a set of shifts and adds, chances are the compiler isn't anymore capable of making a cow out of a hamburger. Premature optimization at its finest.

Well, duh. But hardly wtf worthy. And as previously mentioned, it might NOT be premature optimisation, depending on the compiler used.

Either way its not a WTF.

It's funny to see that the scribbling done during recruitment gets into the production code ;)

I remember that a few years ago someone suggested that
mov ax, 0
should be replaced by
xor ax, ax
because it was taking a cycle less than the previous.
But that was in the ol' dark times when people learned assembler for fun.

Ottokar:

The
idea is that the shift operator could me much faster than multiplying.

 No, the idea is that programmers often want to shift bits (not multiply), and the shift operators let them do that directly instead of simulating it by multiplying or dividing by powers of 2.

Ottokar:

Nowadays
people need the shift operator very seldom. Compilers makes such
optimization for them self.

 It's nothing to do with optimisation, it's about writing code that does what it says. If you need to shift bits, you should use the shift operators. If you need to multiply, you should use the multiplication operator.

Perhaps what you mean is "nowadays people seldom need to abuse the shift operators to speed up multiplication and division by powers of 2".

GettinSadda:

while(isspace(*p++));

No, no, no, no, no....

This will leave p pointing to the second non-whitespace character.

It should be:

while(isspace(*p)) p++;

Anonymous:

DaBookshah:

I was beaten to it,
but yeah, the TRUE WTF is that the article writer thought the multiply
by 10 was a WTF. we have (2^3)*m + 2*m = 10*m. Makes perfect sense.

Except
that just about every compiler does this optimization for you when it
makes sense. On the other hand if multiplying is faster on an
architecture than a set of shifts and adds, chances are the
compiler isn't anymore capable of
making a cow out of a hamburger. Premature optimization at its finest.

Several of the vendor compilers for embedded
programming are an abomination in the book of aho,sethi and ullman.
Usually i read the disassembler files to check if the compiler really
did what i wanted it to do, well, untill i trust it not to be totally
braindead. Reading the compiler generated assembler files often does
not help because sometimes you do not see all the schedulings and
instruction expansions in the compiler listing. I can imagine the
author did this as well and found the compiler at hand not to generate
the desired code. That should result in a comment to this, but WTF...

Hmm,
i should start digging for some WFTs in that direction on my HD, but i
fear that this site is much too popular in this company to escape
unnoticed. :-(

Just go to the source:

int
atoi(const char *str)
{ return((int)strtol(str, (char **)NULL, 10));
}

( http://www.openbsd.org/cgi-bin/cvsweb/src/lib/libc/stdlib/strtol.c?rev=1.7 )

Iago:

No, the idea is that programmers often want to shift bits (not multiply), and the shift operators let them do that directly instead of simulating it by multiplying or dividing by powers of 2.

It's nothing to do with optimisation, it's about writing code that does what it says. If you need to shift bits, you should use the shift operators. If you need to multiply, you should use the multiplication operator.

Perhaps what you mean is "nowadays people seldom need to abuse the shift operators to speed up multiplication and division by powers of 2".

 

You are right at both comments. But ... I have never had any use for "shift bits" within 20 years.

And I have never seen an useful example  for something else then multiplication. Well, except for something really WTF code where programers tried to deal with net-byte intergers without to use the netinet macros. But that is a different story.

Another thing: I like to see those ancient C-Puzzle-Things. It shows me how old I am and what cruel code I wrote in those days. ;)  And it feels good to blame the bloody young guys how can read such code anymore. :)

 Regards.
 

Anonymous:

Anonymous:

You may not believe this but the ISO C standard is pretty clear on this point.

 7.20.1: [...] If the value of the result cannot be represented, the behavior is undefined.

That refers to overflow. The result is well defined in cases like "123adsf", it's 123 and can thus be represented by an int. The standard isn't trivial reading. Sometimes you need to look at other paragraphs as well.

Chapter and verse, please.
 

Anonymous:

I think the title for this posting is unjust. The code clearly shows signs of useful activity in the author's brain while it was being written, even though it is far from optimal and not ANSI-compliant.

It's those who cannot understand m=(m<<3)+(m<<1) who should not be programming.

Performance vs readability tradeoff is common, and you don't know what kind of platform it was. We were told "embedded". And by the way, who said it was expected to be ANSI-compliant?

 

Muh.... The point was that it was commented as "fast" multiply. Not that it in effect multiplies by 10, but that the author thought it was faster. (Which may or may not be correct).
 

Now, on some embedded systems, the bitshifting trick *might* be faster, but how performance-critical is atoi really?

And how anyone can defend this is beyond me. The code doesn't work, the function doesn't do what it's supposed to do. It doesn't matter whether bitshifting is faster, because 1) It's hardly the most performance-critical function, 2) the function doesn't even work, and 3) there are still plenty of other, much more obvious slowdowns in the function.

"Signs of useful activity in the author's brain"? Not really...

Anonymous:

Chapter and verse, please.

I don't have official standard around (costs money), but try 7.20.1.3#4 in n864 draft:

"First, they decompose the input string into three parts: an initial, possibly empty, sequence of white-space characters (as specified by the isspace function), a subject sequence resembling an integer represented in some radix determined by the value of base, and a final string of one or more unrecognized characters, including the terminating null character of the input string. Then, they attempt to convert the subject sequence to an integer, and return the result."

The "final string of one or more unrecognised characters" isn't what is being attempted to convert into "the result".

Anonymous:

DaBookshah:

I was beaten to it, but yeah, the TRUE WTF is that the article writer thought the multiply by 10 was a WTF. we have (2^3)*m + 2*m = 10*m. Makes perfect sense.

Except that just about every compiler does this optimization for you when it makes sense. On the other hand if multiplying is faster on an architecture than a set of shifts and adds, chances are the compiler isn't anymore capable of making a cow out of a hamburger. Premature optimization at its finest.

 
 I once "optimized" a program for DES encryption. The original version was in standard Pascal, and it did all bit shifts by multiplying with and dividing by 32, 16, 8, 4 and 2. I used Turbo Pascal, which has shift operators, so I went through the program and replaced dozens of multiplies and divides by shifts.

It was exactly as slow as before. 

Azrael:

GettinSadda:

while(isspace(*p++));

No, no, no, no, no....

This will leave p pointing to the second non-whitespace character.

It should be:

while(isspace(*p)) p++;

There is a difference between p++ and ++p.

The first is postfix, the second is prefix.

And as the post- and pre- prefixes to -fix are equivilant to when the operation happens

p++ is

{

    char* temp = p;

    p = p + 1;

    return temp;

}

++p is

{

    p = p + 1;

    return p;

}

... so it really doesn't matter. isSpace(...) still gets the same character. Now if it was ++p, you would have an argument.

Also because no one seems to have commented on it. The shift shortcut only works on unsigned integers. i.e Cardinal numbers.

Your reply is true - but adds nothing to my post.

The problem with the original code that offended me was that the post-increment is unconditional; so it will be performed while the pointer is pointing to the non-whitespace character that causes the while loop to terminate. The result is that after the loop the pointer will always point to the second non-whitespace character.

Nachoo:

I am just happy that with Java I will never have to port any standard functions to another platform. Thank you Mr. Gosling.

Someone's never had to develop for a J2ME platform.... 

Surely though that's not a crash, just undefined behavior?

Anonymous:

It's funny to see that the scribbling done during recruitment gets into the production code ;) I remember that a few years ago someone suggested that mov ax, 0 should be replaced by xor ax, ax because it was taking a cycle less than the previous. But that was in the ol' dark times when people learned assembler for fun.

The XOR AX, AX is always two bytes (as is the 32-bit version XOR EAX, EAX). MOV AX, 0 takes two bytes for 'MOV AX, immediate value' with another two bytes for the immediate value 0 (in 32-bits, this goes up to four). So you have two bytes of instruction fetch for XOR vs four or six for MOV.

In the core, the processor doesn't have to do anything for a MOV, just committing the value to the register, but there's a hardware XOR circuit too (adding two bits is an XOR operation, disregarding the carry to the next bit, i.e. 0+0 = 0, 0+1 = 1, 1+0 = 1, 1+1=(1)0) so that isn't likely to add another cycle.

All in all, XOR is the best choice for zeroing a register, so any decent compiler will generate that (probably even if you disable optimizations).

Anonymous:

It's those who cannot understand m=(m<<3)+(m<<1) who should not be programming.

Performance vs readability tradeoff is common, and you don't know what kind of platform it was.

Performance versus readability tradeoffs are way too often pointless premature optimizations. If your compiler sucks ass, you may have to use shifts like he did, but I'm willing to bet that like most premature optimizers he didn't even check whether the compiler transformed * 10 the same way he did.

And even if I understand m=(m<<3)+(m<<1), it is more difficult to parse when reading the code than m *= 10. I thoroughly hate code that pointlessly obfuscate what it intends to do. When you're trying to pinpoint the cause of a bug and come across code like this, you must waste time to read it carefully to determine whether there is an error in the logic. I have a particularly hard time to trust obfuscated code.

People who needlessly write m=(m<<3)+(m<<1) instead of m *= 10 should not be allowed near a keyboard. It's pretty stupid to waste time trying to be clever when doing trivial things like a multiplication instead of trying to apply that cleverness to the overall architecture and design, or to solve real problems.

As for the remark that it is an embedded system and the compiler might suck, there's also big chances that the compiler was gcc. Which doesn't suck.

That said, I really have a soft spot for very helpful comments like this:

	long m=1, t=0;  /* init some vars */ 

 captcha: perfection

Azrael, GettingSadda is right - the "while(isspace(*p++));" simply doesn't do what you think it does,
something that a simple test run will show. Likewise, when you test it, you'll find that your version can't handle the digit "9".

Nachoo:

I am just happy that with Java I will never have to port any standard functions to another platform. Thank you Mr. Gosling.

Yeah, right. Because Java, unlike the standard C library, never needs to be ported on platforms where it doesn't exists. It just magically works.
 

Ok.. now it is much clearer.

 

I do understand binary numbers ; I just didn't know that the "<<" operator is for bitshifting