- Feature Articles
- CodeSOD
- Error'd
-
Forums
-
Other Articles
- Random Article
- Alex's Soapbox
- Announcements
- Best of…
- Best of Email
- Best of the Sidebar
- Bring Your Own Code
- Coded Smorgasbord
- Mandatory Fun Day
- Off Topic
- Representative Line
- News Roundup
- Editor's Soapbox
- Software on the Rocks
- Souvenir Potpourri
- Sponsor Post
- Tales from the Interview
- The Daily WTF: Live
- Virtudyne
Admin
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 :-)
Admin
This is what happens when you give assembly programmers a C compiler.
Admin
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 + 2m = 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.
Admin
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.
Admin
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.
Admin
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.
Admin
Admin
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!
Admin
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;
}
Admin
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
Admin
Admin
did you test this code?
it not only doesn't compile, it returns incorrect results.
atoi( "1" ), returns 0 with this code.
Admin
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?
Admin
I am just happy that with Java I will never have to port any standard functions to another platform. Thank you Mr. Gosling.
Admin
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?
Admin
Admin
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;
}
Admin
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.
Admin
@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.Admin
True, crashing would have to be an improvement wouldn't it.
Admin
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.
Admin
I don't really understand that expression (although I do program). Can anyone enlighten me?
Admin
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.
Admin
See post 101120
Admin
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.
Admin
No, no, no, no, no....
This will leave p pointing to the second non-whitespace character.
It should be:
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.
Admin
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...
Admin
The shift operator is a kind of mulitpling. For example:
nt x = 1357; // Bitmuster: 00000000000000000000010101001101int 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
Admin
Well, of course it means
value "x << 1" means "x * 2"
value "x << 2" means "x * 4"
and so on.
Admin
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
Admin
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
Admin
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.
Admin
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.
Admin
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".
Admin
Admin
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. :-(
Admin
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.
Admin
Chapter and verse, please.
Admin
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...Admin
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".
Admin
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.
Admin
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.
Admin
Someone's never had to develop for a J2ME platform....
Admin
Surely though that's not a crash, just undefined behavior?
Admin
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).
Admin
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:
captcha: perfection
Admin
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".
Admin
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.
Admin
Ok.. now it is much clearer.
I do understand binary numbers ; I just didn't know that the "<<" operator is for bitshifting
Admin
Using "xor ax, ax" (or the local equivalent) is in fact the preferred way to initialize a register to 0 on many
processors, for the simple reason that the whole operation will be encoded in the instruction word rather than using immediate data in a second word.