• Rich (unregistered) in reply to Zlodo
    Anonymous:

    Yes, but we are almost in 2007. Your example involved a basic interpreter on a 8 bit computer, which is kind of prehistoric.

    Bwahahah. This whole thread's topic is based from a code snippet for an embedded device, a domain where 8-bit is still king. But that's irrelevant anyway (Like an example using Pascal).

     My point is simply that you can't always discount hand optimization, particularly in more niche markets where compilers may be designed around the concept that if you want performance, you *will* hand optimize and that to build such nitpicky optimizations into the compiler would not be worthwhile.

     Is there any compiler out there that really optimizes *10 into a handful of shifts and a couple of adds? Does it do the same for 11, 12, 13 or do most just have a generic multiply routine?

     We're in the realm of these (www.microchip.com) devices. It's a very different world from 2GHz 64bit microprocessord with built-in FPUs and two Gigs of ram hanging off the side.

    Rich
     

     

     

     

  • (cs) in reply to Kevin Puetz
    Anonymous:

    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.

    Don't forget 8 bit micros either.  Many of those can't do shifts by more han 1 bit at a time without a loop.

    There are basically two big things wrong with that function.  Using the "m" multiplier rather than starting at the most significant digit and working down so that you only need to multiply by 10 each time.  That way the only 32-bit operation is addition, and the multiply always fits in one byte.  That's only a performance issue though (most apps don't require high speed atoi routines). The second major problem as pointed out is the lack of correctness checking.  I'm gratified to see some comments in the code.

    (other lesser problems include not implementing "strtol" instead and define "atoi" from that...)

    There are open source C libraries out there that can be used if necessary, even non-GPL ones.  Rolling your own is seldom needed, and can be complicated to do correctly (and even harder to make it conform to the standard).

  • (cs) in reply to Kevin Puetz

    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...

    Indeed, even though modern x86s have blisteringly fast FPUs, their integer multipliers usually have a 3 or 4 cycle latency, so shifts and adds will still be quicker. Indeed, an LEA can do most of the work:

       lea eax, [eax*4+eax]
       add eax, eax

    As for (I believe) a reasonably efficient x86 implementation of atoi (although it's limited to ASCII and bytewide characters):

    _atoi:
        ; string is in eax, result in eax, we trash e?x
        ; I've not tested it, so it won't work :-)
       xor ecx, ecx    ; accumulate our result in here...
       mov edx, ecx   ; sign flag goes here
        ; skip over initial whitespace
       dec eax    ; do this so we only have to jump backwards below
    ws:
       movzx ebx, byte ptr [eax + 1]
       or ebx, ebx
       jz done    ; quit at end of string
       inc eax
       cmp ebx, ' '   ; test for space - and for ASCII control chars too
       jle ws
        ; sign test
       cmp ebx, '+'
       jne nopos
       inc eax    ; positive signs get ignored
       jmp digit
    nopos:
       cmp ebx, '-'
       jne gotdigit
       dec edx   ; edx now -1 IFF result needs negating
       inc eax
        ; process digits - temp.result in ecx
    digit:
       movzx ebx, byte ptr [eax]
    gotdigit:
       sub ebx, '0'    ; if digit is non-numeric (inc. EOS), we're done
       jl done
       cmp ebx, 9
       ja done
       lea ebx, [ecx*2 + ebx]    ; D = 2*r + d...
       inc eax   ; help out P1 pairing a bit :-)
       lea ecx, [ecx*8 + ebx]  ; ...so r = 8*r + D = 10*r + d
       jmp digit
    done:    ; out of number
       lea eax, [ecx + edx]   ; result = r (or r-1, if negating needed)
       xor eax, edx   ; (result-1) xor -1 = -result; result xor 0 = result
       ret

    (It's reading week, so I've got nothing better to do except my law coursework. Incidentally, why do so many computer people seem to go into law as their second career?)

  • (cs)

    Well, 'embedded' programming is my main job, and it has changed a lot in the last 5-6 years. Right now I get a well-equiped 'embedded' platform with an ARM 200mhz, 4mb ram and 8mb flash... 3y ago this still was an m86k with 1mb RAM / 2mb Flash. Go back another 2 years, and I'd get an m86k with half that memory... If you were really unfortunate you'd get a 8-bit ehm PIC-on-steroids-pretending-to-be-a-cpu (commonly used in thermostats) with 512kb or 1mb of paged battery-backupped ram (in 16kb or 32kb pages). A nightmare to port a rather big application to, and we ended up using all the available memory on a 1mb device, with only a few bytes left (page-swapping for a function call is quite code-intensive: on a m68k, the codesize was in the order of 130/140kb, on that specific device it was over 600kb...). Well - this is what you get when a salesman sells a desk-clock to do the job of the Big Ben....

    The standard libraries underwent the same evolution. We provide a number of portable programs with a common hardware abstraction layer, making them available on multiple platforms, and for each of these platforms we have a specific config.h file filled with things like:

    #define BUGGY_MEMCMP
    #define BUGGY_MEMCPY
    #define BUGGY_STRCPY
    #define BUGGY_STRCMP
    //#define BUGGY_PRINTF
    #define BUGGY_ATOI
    ...

    And yes, we rewrote most of those functions, using them with a capitalised first character everywhere. There are (sadly enough) platforms where very few of the lines above are commented out. The part above actually is (a partial) copy/paste from one of these platforms.

    atoi() being buggy is very common, more common than you wish for at least. I can vividly imagine a certain platform actually having this exact atoi() implementation :P

    A buggy printf/sprintf implementation is also very common, though basic stuff usually works fine. Especially formatting of signed numbers, leading zero and alignment format strings tend to be a problem. Currently I always use the self-written (s)printf functions to ensure consistency between platforms, since the self-written version is merely a (well-documented) stripdown. This void's some rather good compiler's (like the ARM and MRI compilers) optimizations and warnings about possibly invalid formatting strings, but it's something I'll have to live with, for the sake of portability. Should write a 'wrapper' layer though that only checks compatability with the own implementation in debug mode and in a final build let the compiler & standard libs do their job, but well - in an ideal world... sigh

    That said, my implementations are well-tested now, I have well-defined test-scenario's I unleash on each new platform, and it passes them without any problems. New platforms tend to have less & less problems over the years. 5-6 years ago, this was disastrous...

    I in general decided against 'platform' optimalisations in general, with a few notable exceptions. The illustration that 5 years ago, using malloc on these platforms was the coding equivalent of flying a plane into the WTC, while now this is actually no problem at all on newer platforms (and yes - I did write a portable heap-manager - though it still is a bit too buggy to be used in production). I sure hope I don't encounter a 128kb flash/32kb ram thing anymore... The stuff got so cheap it's simply not worth developping anymore for anything with less than 1mb ram/1mb flash (which is plenty for running our applications).

  • Bill (unregistered)

    It was a rather small book written by P.J. Plauger (sp?) "The Standard C Library".

    It was a simple book that showed AN implementation of the complete Standard C library.  It was very eye openning for me.  I had always thought of the C library as "magic" - to see its guts openned like that was just amazing to me (Arthur C. Clark - any advanced technology is indistinguishable from Magic).  I guess that was the time almost 20 years ago that my eyes were openned and everything became "Just a matter of 1s and 0s".

    Now the REAL WTF is why the author didn't grab one of MANY acceptably debugged atoi funcitons available and modify it for the platform - so at least the basic structure of the function call was correct.  The real WTF is why don't people just grab an implementation that you have sitting on your machine (and if you don't have an implementation there is another WTF).

    /***
    *int atoi(char *nptr) - Convert string to long
    *
    *Purpose:
    *       Converts ASCII string pointed to by nptr to binary.
    *       Overflow is not detected.  Because of this, we can just use
    *       atol().
    *
    *Entry:
    *       nptr = ptr to string to convert
    *
    *Exit:
    *       return int value of the string
    *
    *Exceptions:
    *       None - overflow is not detected.
    *
    *******************************************************************************/

    int __cdecl _tstoi(
            const _TCHAR *nptr
            )
    {
            return (int)_tstol(nptr);
    }

    #ifndef _NO_INT64

    __int64 __cdecl _tstoi64(
            const _TCHAR *nptr
            )
    {
            int c;              /* current char */
            __int64 total;      /* current total */
            int sign;           /* if '-', then negative, otherwise positive */
    #if defined (_MT) && !defined (_UNICODE)
            pthreadlocinfo ptloci = _getptd()->ptlocinfo;

            if ( ptloci != __ptlocinfo )
                ptloci = __updatetlocinfo();

            /* skip whitespace */
            while ( __isspace_mt(ptloci, (int)(_TUCHAR)*nptr) )
    #else  /* defined (_MT) && !defined (_UNICODE) */
            while ( _istspace((int)(_TUCHAR)*nptr) )
    #endif  /* defined (_MT) && !defined (_UNICODE) */
                ++nptr;

            c = (int)(_TUCHAR)*nptr++;
            sign = c;           /* save sign indication */
            if (c == _T('-') || c == _T('+'))
                c = (int)(_TUCHAR)*nptr++;    /* skip sign */

            total = 0;

            while ( (c = _tchartodigit(c)) != -1 ) {
                total = 10 * total + c;     /* accumulate digit */
                c = (_TUCHAR)*nptr++;    /* get next char */
            }

            if (sign == _T('-'))
                return -total;
            else
                return total;   /* return result, negated if necessary */
    }

    Captcha "Perfection"

  • (cs) in reply to Dash

    If the target platform has just a numeric input, a character other than a digit, '+' or '-' signal would be never input anyway.

    A good point - but if the target platform has just a numeric input, surely there's a better way of converting a number from that input than calling atoi on it? (For instance, a jump table that directly adds the digit keyed to the number in question.)
     

  • (cs) in reply to gwenhwyfaer

    I said:

       dec eax    ; do this so we only have to jump backwards below
    ws:
       movzx ebx, byte ptr [eax + 1]

    Make that:

       sub eax, 1    ; do this so we only have to jump backwards below
       jc done    ; test for NULLness :-O
    ws:
       movzx ebx, byte ptr [eax + 1]

  • Eddie Pedant (unregistered)
    Tim Gallagher:

    sqrt uses a fixed loop count (rather than a target epsilon) to terminate the convergence, resulting in wildly inaccurate values as the input increases. e.g. sqrt(10000) == 1251.5

    While that is the wrong answer, there's nothing wrong per se with a sqrt that uses a fixed loop count.  One fast sqrt algorithm uses a small table for the top few bits of the representation, then refines the lookup with one or two iterations of Newton-Rhapson.  This is the method the Cell uses for sqrt with a 256- (or is it 512-?) entry table giving 12-bit accuracy and a single iteration of NR giving the full 23 bits for a float.  Three iterations are appropriate for a double-precision result.  Since Newton Rhapson doubles the number of bits for each iteration, a fixed count is correct assuming a fixed word size.  Checking epsilons is more cycles and it's quite difficult to code correctly.

    An implementation that has greater errors for larger numbers is simply failing to normalize.  sqrt(4 * x) = 2 * sqrt(x) so you only need to consider the LSB of the exponent.  sqrt(10000) should be as accurate as sqrt(0.611).

  • (cs) in reply to Rich

    It's astonishing how many people in this thread can't grasp the simple point that a wrong answer obtained faster is still wrong.

     

  • (cs) in reply to Bob Cobb

    Anonymous:

    So what exactly is undefined behavior? I ask this in the context of writing your own function that is in compliance with the standard.  I always assumed this meant the standard doesn't specify (define) what the result is under that condition so it will depend on the (your) implementation, but I've heard others argue that your output cannot be defined... i.e. it cannot be guaranteed in your implementation...it must be somewhat random... it cannot return a consistent, definable, expected result

    "implementation-defined": An implementation can do whatever is convenient, but what it does must be documented.

    "undefined":  An implementation can do whatever the heck the implementer wants, and can document it or not, the standard doesn't give a whoop.

    The way an implementation handles an undefined behavior scenario can never cause it to be out of compliance with the standard. Never ever. That's what "undefined" means.

     

  • (cs) in reply to DaBookshah


    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.


    Come on, you know it is a real WTF, don't you ? Start by the end of the string (as parsing by the end is surely faster on his micro-hardware for sure), add the digit to the multiplication of the subtotal by the multiplier or vice versa WTF i can not even remember the algorithm he coded, multiply the multiplier no wait let us cleverly shift it...
     

    This guy just implemented the most complicated way for atoi, maybe to backup the false assumption that he is a genius, or to be sure to be the only one to be able to debug his code, which can be a good strategy... Or maybe he wanted to make us all laugh very loud ? I must confess that i did :o)))
     

    As for myself this is even a FWTF as i learned programing in C and Assembler decades ago, and i can not stand how this guy is ruining the Honorable Reputation of Good Old Developers from the Good Old Days... So i suggest a new category, the f....g WTF category, and i vote for this one as FTWF of the week ;o)

     And please, can the poster share some other "optimized" functions ? Thanks in advance !
     

  • Gadfly (unregistered) in reply to John Hensley

    John Hensley:
    The way an implementation handles an undefined behavior scenario can never cause it to be out of compliance with the standard. Never ever. That's what "undefined" means.

    So atoi could call a routine that flips a random bit in the boot sector.  Cool.
     

  • (cs) in reply to Nachoo

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

    Unless you have to implement your own VM.  Most people never have to do that of course, just like most people never need to implement their own C run time library.  That's the nature of having to port to new platforms, your "standard" support needs to be ported as well regardless of what language it is.

  • (cs) in reply to DaBookshah
    DaBookshah:
    Ottokar:

    Better would be something like

    {
        char *p; p=0; *p=0;
    }

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

    That doesn't always cause crashes in embedded systems.  It's generally good practice to ensure that this crashes, so that you can find errors earlier during development.  But a lot of people don't do the extra work or realize that it would be useful.

    I remember in the past, an otherwise very bright student at my university had several glaring blind spots (at one point he said "why do we need to learn how to write compilers, we already have a C compiler.")  He knew all the ins and outs of programming optimally on VAXes using C, whether i++ or ++i was faster, etc.  Some of the labs started getting Sun workstations, and he complained when he ported over his code because his optimization tricks didn't work anymore.  His loudest griping point was the fact that dereferencing a null pointer on a Sun caused a crash, because his code relied on the fact that a VAX would return 0 when you did that.

  • Clinton Pierce (unregistered)

    What annoys me about this WTF is that on the surface it could be easily avoided by adapting code from K&R or from an OSS implementation of atoi.  Except:

     * The K&R version -- or any other published version -- is copyrighted and I'm sure that embedding it in a product's source code is just asking for trouble.

     * An "OSS" implementation of this is a legal nightmare.  Taking it from a GNU implementation, for example, binds you to all of the copyleft licensing crap.  So while a perfectly good implementation exists and is supposedly "free" it's not.  It could throw his product into a quagmire.

    So a programmer has to re-invent yet another wheel that shouldn't have been necessary.  Sad.



     

  • antred (unregistered)

    Anonymous:
    Ummm, actually you can assume that NULL == 0.  It's required by the standard.

     

    Is NULL actually part of the standard? If I'm not mistaken (which I may very well be), NULL is simply just a define provided by many implementations, but the standard doesn't actually say anything about NULL. 

  • (cs) in reply to John Hensley
    John Hensley:

    It's astonishing how many people in this thread can't grasp the simple point that a wrong answer obtained faster is still wrong.

    but...but... its faster!

  • (cs) in reply to brendan
    brendan:

    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.

     What I love about reading WTF is the WTF's that are posted as a "solution"

    WHY oh WHY would atoi return -1 when it sees a character larger than '0'+9? When it is supposed to return "The equivalent value, or zero if the string does not represent a number. "

    And what happens if the string contains a character less than '0'?

  • antred (unregistered) in reply to chrismcb

    Perhaps the poor bugger should just have called his function something other than "atoi". It might still have all the same shortcomings, but at least it wouldn't be subject to any "but the standard says atoi must do this" complaints.

  • PlasmaB (unregistered) in reply to John Hensley

    > It's astonishing how many people in this thread can't grasp the simple point that a wrong answer obtained

    > faster is still wrong.

     

    Wrong is subjective. For many embeded applications close is good enough. It is often understood that you need to jump through hoops at the embedded level. I agree that its a WTF if its on anything capable of running Linux or uCLinux... but there are loads of devices out there that dont. And they are used all the time in simple devices. AMX/DMX512 controllers and drivers,  serial to serial converters etc etc.

     

    The example of the sine table lookups is something I have done myself on any number of occasions. In many cases 6 deg accuracy is more than fine... if all you're doing is turning lights on smoothly or regulating stepper motors.

     

    The only WTF is the ANSI stamp.

     

  • (cs) in reply to pbounaix
    pbounaix:
    John Hensley:

    It's astonishing how many people in this thread can't grasp the simple point that a wrong answer obtained faster is still wrong.

    but...but... its faster!

     

    "...the right way, the wrong way, and the Max Powers way."

     

  • (cs) in reply to Hans
    Hans:

    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.

     

    This is usually different on RISC processors where instructions are usually all the same size (never immediate data in a following address).  On the PowerPC, loading a 16-bit immediate into a 32-bit register can done with a single instruction.  Compilers tend to use the variant that doesn't set condition codes (unlike xor).

  • Rich (unregistered)
    Anonymous:

    Ummm, actually you can assume that NULL == 0.  It's required by the standard.

    You may be confused by a different rule which says that you can't assume that the following prints "true":

     

     

    Possibly. Or I may have been misremembering this bit from the FAQ

     

    In pre-standard code, NULL was/is sometimes defined to something unsuitable and therefore had/has to be avoided. That's less common these days.

    as meaning that NULL was not (necessarily) zero.

     I think it's more readable to treat them differently anyway. Not that I code much C/C++ anymore.

     

    Rich 

     

  • (cs) in reply to DaveK
    Anonymous:

     Now that is a WTF.  Non-re-entrant library functions for long multiplication?  I won't believe it until I see one.  I can promise you that gcc's [u/s]mul[qi/si/di]3 are all perfectly re-entrant.  I can't speak for other compilers but there's no good reason why they shouldn't run entirely in registers/stack local variables.

     

    Unfortunately, that stuff happens.  Ie, if you've got no stack space to speak of and registers are scarce (most 8-bit systems).  Usually what happens is that someone writes the routine assuming re-entrancy isn't needed, but over time the application changes to make that assumption wrong.  Many systems will only allow context switches at predetermined places (non-preemptive) so you're safe with non-reentrant functions as long as you make sure your interrupt handler doesn't use them.

  • (cs) in reply to romuloceccon

    romuloceccon:
    The while(l) line is also wonderful. It took me a minute to figure out why I couldn't find the break statement that would leave the infinite loop. :-)

    Just a historical note for you newbies.  Older manual typewriters used to have no 0 or 1 keys, you were to use O and l instead (oh and ell if you can't figure it out). Some typing texts also taught this way.  I've ran across people who took that habit with them to computers and had trouble.

  • (cs) in reply to antred
    Anonymous:

    Is NULL actually part of the standard? If I'm not mistaken (which I may very well be), NULL is simply just a define provided by many implementations, but the standard doesn't actually say anything about NULL. 

    Yes you are quite egregiously mistaken.

    Among other things the standard defines NULL as 0, although it is not necessarily zero.

     

  • reptar (unregistered) in reply to who wants to know

    Ah yes, the joys of 6502 machine code, with its slow mathematics and page boundary issues.  Still, it and the 6510 provided us with some of the best computers...

  • (cs)
    Anonymous:

    What does the sophistication of the target hardware has to do with that of the compiler? The compiler does run on a desktop pc and thus has lots of cpu power and memory available.

    The PIC compiler from Hi-Tech seems pretty sophisticated at times with what I can manage to do on the hardware.  I don't think there is a GCC port.  There are times when I think it's doing stupid things, but usually closer inspection clears things up, and remembering that it is often optimizing for space instead of speed.  It's definately smart enough to turn "m = ((m<<2) + m) << 1)" into a function call to multiply by 5 and add the result to itself.

  • (cs) in reply to Clinton Pierce
    Anonymous:

     * An "OSS" implementation of this is a legal nightmare.  Taking it from a GNU implementation, for example, binds you to all of the copyleft licensing crap.  So while a perfectly good implementation exists and is supposedly "free" it's not.

    Newlib tends to use BSD licenses or other licenses that allow use without requiring the full application source code to be made available.

  • Your Name (unregistered)

    It seems like a lot of you do not appreciate how bad commercial uC compiler's optimizers are (and gcc isn't much better for the embedded systems I've used), nor do you understand how many cycles a multiply really takes. Yes, it is clearer to use '*', but this isn't always possible or advisiable. Whether it was premature or not, this function doesn't really deserve this scorn.

     

    Is it incorrect? Yes. Is it really that bad? No. 

  • (cs)

    Funny, my first reaction to this was... "Hey, at least it's commented!"

    Oh, and the thing about the shift operators, it's not so weird IMO, but what is weird that you'd go so far as to define 10 as shift operations and not registerize the location...

    Oh well, I guess the fact that we all see WTFs all over the place makes this a classic bit of WTF code!

  • Scottford (unregistered) in reply to Mike Dimmick
    Mike Dimmick:

    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).

    There are drawbacks to XOR. It sets the condition codes, which restricts code motion. For example,

     mov eax,0 

     cmp ebx,ecx

     je Foo 

    In the above case, the CMP and MOV could be swapped, possibly speeding up the code. If the MOV were XOR, then CMP could not be moved, becuase the XOR clobbers the condition codes that JE depends on.

    Second, the XOR creates a false dependency on eax. If a prior instruction is writing to eax, the processor has to wait for that to finish before it can execute the XOR. Except that I believe modern CPUs special-case XOR to avoid this false dependency.

    Third, the drawback you cited for MOV (extra code size) is not generally an issue. Any decent x86 design should be able to sustain 4 or 6 bytes per instruction without the instruction fetch falling behind.

    Bottom line: it's not so simple. Fortunately, we don't have to care. Let the compiler do its job.

     

    Someone else replied that XOR will "mark the register as unused"...?? Not sure why the processor would try to keep track of which registers are "used," or what it would do with that information. I've never heard of that.

     

  • (cs) in reply to Clinton Pierce
    Anonymous:

    What annoys me about this WTF is that on the surface it could be easily avoided by adapting code from K&R or from an OSS implementation of atoi.  Except:

     * The K&R version -- or any other published version -- is copyrighted and I'm sure that embedding it in a product's source code is just asking for trouble.

     * An "OSS" implementation of this is a legal nightmare.  Taking it from a GNU implementation, for example, binds you to all of the copyleft licensing crap.  So while a perfectly good implementation exists and is supposedly "free" it's not.  It could throw his product into a quagmire.

    So a programmer has to re-invent yet another wheel that shouldn't have been necessary.  Sad.

    This brings up an interesting point. At what point does similar code constitute as copyright infringement. If I had a version of atoi that compiled into identical machine code as K&R's version but looked very different, would that be ok or no? It's copyrighten but not patented.

    Or what if I came up with very similar piece of code without ever having knowledge of the copyrighten version? After all, there are only so many good ways of implementing atoi, etc.

  • Tobi (unregistered) in reply to DaBookshah
    DaBookshah:
    Ottokar:

    Better would be something like

    {

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

    }

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

    Well, knowing embedded controllers, I have to disagree on that. The Programm won't crash, as on most microcontrollers, "0" is a valid address.

    (Taken the Frescale S12 as example, the address "0" is "PORTA" with default memory mapping)

    It won't crash. if one want to do something like "crashing", one would either call a error-hook function or enter a while(1) loop....

     

     

     

  • (cs) 
    if(negative) t = -t;

    This, and every other "fixed" version posted, has an overflow bug: it assumes that the range of representible positive integers is at least as big as the range of representible negative integers.  This is almost never true; almost all computers nowadays use two's complement.

    Try getting this atoi() to return -32768 on a machine with 16-bit signed ints.

  • (cs) in reply to Ottokar
    Ottokar:

     
    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.

    Yes, we wouldn't want to penalize any of those performance-critical applications that use atoi in the inner loop. Far better to let an application error produce Undefined Behavior and likely lose application data. That'll teach 'em a lesson.

    Ottokar:

    Returning "-1" for a atoi function is wrong since the result is a correct value.

     

    Wrong. Returning a value that's within the normal range of the function is one possible consequence of undefined behavior. There's nothing in ISO 9899:1999 that makes returning -1 from atoi(NULL) incorrect.

     

  • (cs)

    What's interesting is that this code starts at the end and works backwards. That approach doesn't make sense for atoi (requires more complexity, the strlen() operation, and the awkward "*= m" after trying to efficiently doing a "m *= 10"), but it does make sense for itoa. They must have copied code from the opposite algorithm, and done so badly...


    But the REAL WTF is many of the comments here, like this one:

    <blockquote>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?</blockquote>

    This <b>is</b> a library. Someone has to write libc...

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

    That's not a characteristic of Java. It's a characteristic of only using systems to which the porting has already been done. You do realize that the JVM calls these functions, right?


  • CGod (unregistered) in reply to anonymous
    Anonymous:

    I dont rewrite standard library stuff normally because is always better written on the library.

    EXCEPT: 

    But If you want to add more defensive programming, you can make your own version, a slower but safer one.

    Also having your own malloc and free, able nice stuff, like garbage collection and leak detection.

    Theres also the need to make a function shorter.    scmp as short version of strncmp, but you can do that with a define.

     

     

    Another EXCEPTION: Coding guidlines FORBIDS usage of standard library functions (e.g MISRA -- automotive rules)

    (atoi is usally also forbidden in embedded, also dynamic memory allocation) 

  • (cs) in reply to Raafschild
    Anonymous:

     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. 

    Stop the madness, please. This is an embedded system.



    5*10 will likely be computed by:

    temp = 0
    temp = temp + 5
    m = m-1
    check if m = 0
    temp = temp + 5
    m = m-1
    
check if m = 0
    temp = temp + 5
    m = m-1
    
check if m = 0
    temp = temp + 5
    m = m-1
    
check if m = 0
    temp = temp + 5
    m = m-1
    
check if m = 0
    temp = temp + 5
    m = m-1
    
check if m = 0
    temp = temp + 5
    m = m-1
    
check if m = 0
    temp = temp + 5
    m = m-1
    
check if m = 0
    temp = temp + 5
    m = m-1
    
check if m = 0
    temp = temp + 5
    m = m-1
    
check if m = 0
    done

    That's at least 30 computed instructions, even more if there is no branch prediction (extra bubbles added in the pipeline during each branch).

    Now compare with


    m = m << 3
    temp = m << 1
    m = m + temp

    No branches either. Whether or not this could have been optimised by the compiler is not known, do not speculate

  • (cs) in reply to John Hensley
    John Hensley:
    Anonymous:

    Is NULL actually part of the standard? If I'm not mistaken (which I may very well be), NULL is simply just a define provided by many implementations, but the standard doesn't actually say anything about NULL. 

    Yes you are quite egregiously mistaken.

    Among other things the standard defines NULL as 0, although it is not necessarily zero.

     

    ISO 9899:1999 defines NULL as an implementation-defined null pointer constant (7.17 #3), which is any integer constant expression with value 0, or such an expression cast to void * (6.3.2.3 #3).  Typical implementations define NULL as "0" or "(void *)0" (without the quotes, obviously), but arbitrarily silly definitions are possible.

    A null pointer constant always has value 0, even if the implementation's representation of a null pointer is not all-bits-zero.  The implementation is required to generate a null pointer representation where it encounters a null pointer constant in a pointer context.  I assume that's what "it is not necessarily zero" means above.

    The standard also says that NULL must be defined by locale.h (7.11), stddef.h (7.17), stdio.h (7.19.1), stdlib.h (7.20), string.h (7.21.1), time.h (7.23.1), and wchar.h (7.24.1).  Most of those are only required for hosted implementations, but even freestanding implementations have to provide stdlib.h, so any conforming implementation will define NULL in this way.

     

  • (cs) in reply to Zlodo

    Anonymous:
    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.

    Next time put your contact info for resume filtering purposes. Thanks 

  • Tobi (unregistered) in reply to Defensive Programming Ruleshttp://thedailywtf.com/forums/AddPost

    1st one, defintly (a & 1 ) == 1
    But I would write if (a & 1), only, because MCU are easier in comparing "not zero" instead to a
    specific value ("==1")...


    Code size is also smaller -- proved today at a current project.
    My solution one was about 12 bytes smaller in code.
     

  • (cs) in reply to Scottford
    Scottford:
    Someone else replied that XOR will "mark the register as unused"...?? Not sure why the processor would try to keep track of which registers are "used," or what it would do with that information. I've never heard of that.

    That would be me, and I qualified it with "for Pentium Pro class x86 CPUs". That's because of the partial register stall issue - which brings code like

        mov [SOME_INT], eax
        mov ax, [    SOME_SHORT]
        add ebx, eax          ; this will stall!

    screeching to a halt, because the PPro allocates separate physical registers to eax and ax in this instance and has to wait for the write to ax to retire before it can execute the add. However, Intel (cognisant of this) decreed that "xor eax, eax" would effectively insulate any use of part of eax after it from any use of all of eax before - so that

        mov [SOME_INT], eax
        xor eax, eax      ;     prevent a stall
        mov ax, [    SOME_SHORT]
        add ebx, eax

    doesn't stall. Unfortunately, as you note, "xor eax, eax" isn't recognised as not being dependent on the value of eax, so the first two instructions above have to execute in order; so if you need to break that dependency as well, you need to add the mov:

        mov [SOME_INT], eax
        mov eax,     0      ; break dependency on eax
        xor eax, eax      ;     insulate against partial reg stalls
        mov ax, [    SOME_SHORT]
        add ebx, eax

    So all told, it's a lot easier, in that situation, to just write:

        mov [SOME_INT], eax
        movzx eax, word ptr [    SOME_SHORT]
        add ebx, eax

    and save all the hassle :) But that's what I meant by "mark the register as unused".

  • (cs) in reply to achille

    achille, you say...

    Stop the madness, please. This is an embedded system.

    ...but then suggest that constant multiplication will be implemented by a downcounted loop, rather than by the series of shifts and adds that machines without hardware multipliers have used for about the last 40 years....? And then suggest "m = (m<<3) + (m<<1)" as a better alternative, when m<<3 is going to end up in a loop itself on any CPU without a barrel shifter...?

    ...Oops.
     

  • fivetrees (unregistered) in reply to romuloceccon

    romuloceccon:
    The while(l) line is also wonderful. It took me a minute to figure out why I couldn't find the break statement that would leave the infinite loop. :-)

    Gah. It bugged me why I was stumped over a while( TRUE ) when nobody else was. In fact it was more of a case of while( wtf_are_people_still_using_single_character_variable_names??? )

     Steve

  • Scottford (unregistered) in reply to gwenhwyfaer
    gwenhwyfaer:

    So all told, it's a lot easier, in that situation, to just write:

        mov [SOME_INT], eax
        movzx eax, word ptr [    SOME_SHORT]
        add ebx, eax

    and save all the hassle :) But that's what I meant by "mark the register as unused".

     Wow. Fascinating. It's even more complicated than I thought. Thanks for clarifying.

    I guess you found this from Intel optimization guides or something? The term "partial register stall" does ring a bell. I used to skim through those kinds of books years ago.

     

  • Zlodo (unregistered) in reply to gwenhwyfaer
    gwenhwyfaer:

    achille, you say...

    Stop the madness, please. This is an embedded system.

    ...but then suggest that constant multiplication will be implemented by a downcounted loop, rather than by the series of shifts and adds that machines without hardware multipliers have used for about the last 40 years....? And then suggest "m = (m<<3) + (m<<1)" as a better alternative, when m<<3 is going to end up in a loop itself on any CPU without a barrel shifter...?

    ...Oops.
     

     
    Well, that same guy also said "do not speculate" after spending a whole page doing exactly that, so he does seem to lack consistency in his argumentation.

    Achille, given how generally horrible the code in this WTF was, I'm still going with the theory that the author was a premature optimizer who probably didn't check what the compiler generated with *= 10. And if you preach going "the safe way" and writing shift/add code directly in case the compiler doesn't do it, then you are a premature optimizer, and I'm happy to be talking with you because guys with similar philosophy as yours wrote a lot of shitty code that I have to maintain at work, and I can't be as obnoxious with them as I can with a stranger on the net.

    Short version: I hate you :p

    But really, people seem to be quite ignorant of what compilers can achieve nowadays. You guys would probably have a heart attack if you saw the byzantine template based contraption I'm currently working on in my hobby project. Lots of classes, function calls, callbacks, temporary variables all over the place. And most of it gets elided and turned into nice, straightforward, linear code, only not excruciatingly written manually.

    But noooo, compilers can't conceivably turn a multiplication into a bunch of shift and adds. Makes you wonder what those guys think compilers are actually doing using all that ram and cpu. Probably generating lots of useless, horrible, mysterious and slow code just for the heck of it.

    Oh, and I do want you to have a heart attack. I used c++ and templates in a gameboy advance game, running on an arm7. And also on a nintendo ds. I may have violated some sacred law of embedded system programming there. The gods of misguided optimization are probably not amused.

  • vDave (unregistered) in reply to brendan
    brendan:

    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.

     

    On the odd chance noone else has corrected this, you fail to catch the first char of the source string when it is not a '-'.

    atoi("12") == [ 2 ]  =)         

  • Erk (unregistered)

    I have only one comment: Open source!

    It would have done two things for the people developing these functions:

    1. They could have copied the source, even the original source from the original stdlib implementation

    2. No way in hell anyone other than the programmer responsible would ever have let that kind of implementation (and the others like it) pass the first cursory check through... i.e. it would have gotten kicked out of the version control as quickly as it was shoved into it...

    ;o)

     
    /E
     

  • (cs) in reply to Bill
    bill:

    It was a rather small book written by P.J. Plauger (sp?) "The Standard C Library".

    It was a simple book that showed AN implementation of the complete Standard C library.  It was very eye openning for me.  I had always thought of the C library as "magic" - to see its guts openned like that was just amazing to me (Arthur C. Clark - any advanced technology is indistinguishable from Magic).  I guess that was the time almost 20 years ago that my eyes were openned and everything became "Just a matter of 1s and 0s".

    Now the REAL WTF is why the author didn't grab one of MANY acceptably debugged atoi funcitons available and modify it for the platform - so at least the basic structure of the function call was correct.  The real WTF is why don't people just grab an implementation that you have sitting on your machine (and if you don't have an implementation there is another WTF).

    <<SNIP COPYRIGHTED CODE>>

    Oh come on - not only do you advocate ripping off Microsoft's copyrighted version of atoi() but you even quote it minus the copyright notice to encourage its reuse!

    Remember to post back and let us know how it went in court... 

Leave a comment on “The Magnitude of Ineptitude”

Log In or post as a guest

Replying to comment #:

Log Out

« Return to Article