stdlib + MCU haters: std itoa() uses less resources!

[brucehoult]

Just had to show this to the old "I never use std libs in MCU" dogs  , showing it's not always the case.
(Sure enough, the flash usage will blast off when using any std print function)
Custom itoa, taken form here (Can it get more simple than this?):

Code: [Select]

char* _itoa(int val, int base){
    static char buf[32];
    int i=30;
    for(; val && i ; --i, val /= base)
      buf[i] = "0123456789ABCDEF"[val % base];
    return &buf[i+1];
  }

End result was standard itoa using less resources overall  . In custom itoa, sdtlib is not used at all.

I don't know if this has been already said on this thread (it's a long thread) but "short and efficient looking code" does not automatically translate to "short and efficient assembly / machine code".

For example, on Cortex-M0 ...

Code: [Select]

"0123456789ABCDEF"[...]

... uses 17 bytes for the string plus 4 bytes for a constant pool pointer to the string, plus 4 bytes of code, for a total of 25 bytes.

An alternative method that tests the value and adds either '0' or 'A'-10 uses only 8 bytes of code.

[AVI-crak]

It also calls the built-in function __aeabi_idivmod - insanely slow even for Cortex-M0.

[cv007]

I don't know if this has been already said

The signed division library brought in is about 200 bytes more than the unsigned version. The library version of itoa uses utoa to do the work, which is unsigned division. The library version is larger/does more work, but since it does unsigned division it gets a 200 byte head start. Had both signed/unsigned division been brought in due to other code, the real size difference would be revealed.

In the end, the user could have used the library version thinking it was the size winner, and would never realize it was actually larger. And would also make no difference in the 16k mcu, and the 'error' would never be noticed. Ever.

[Siwastaja]

An alternative method that tests the value and adds either '0' or 'A'-10 uses only 8 bytes of code.

And think about the case where one only needs to print base-10 numbers which is quite often in user interfaces of small gadgets!

[Siwastaja]

In the end, the user could have used the library version thinking it was the size winner, and would never realize it was actually larger. And would also make no difference in the 16k mcu, and the 'error' would never be noticed. Ever.

Yes - as others have said, DavidAlfa's methodology is pretty flawed. Size analysis isn't rocket science, but not that easy either. One needs to carefully look at the size of the actual function but also what else it calls, and then decide if those dependencies are used - or maybe useful for future code - elsewhere.

[voltsandjolts]

And think about the case where one only needs to print base-10 numbers which is quite often in user interfaces of small gadgets!

Yup.
I mostly use M0 and mutiply-shift does ok.

Code: [Select]

/*
 * https://stackoverflow.com/questions/7890194/optimized-itoa-function
 * Convert an unsigned number in the range 0...99,000 to decimal 5 ascii digits using Q4.28 notation.
 * Terminating NULL is NOT provided.
 */
void utl_unsigned_to_5digit_ascii(char *buf, uint32_t val) {
    const uint32_t f1_10000 = ((1UL << 28) / 10000UL);

    /* 2^28 / 10000 is 26843.5456, but 26843.75 is sufficiently close */
    uint32_t tmp = val * (f1_10000 + 1) - (val / 4);

    for(uint32_t i = 0; i < 5; i++)
    {
        uint8_t digit = (uint8_t)(tmp >> 28);
        buf[i] = '0' + (uint8_t) digit;
        tmp = (tmp & 0x0fffffff) * 10;
    }
}


[brucehoult]

An alternative method that tests the value and adds either '0' or 'A'-10 uses only 8 bytes of code.

And think about the case where one only needs to print base-10 numbers which is quite often in user interfaces of small gadgets!

Sure. Saves 6 of those 8 bytes.

Also saves linking in __aeabi_idivmod or __aeabi_uidivmod as if you write "10" explicitly as the divisor then any decent compiler will do the "multiply by 0xcccccccd and shift right by 35" trick.

[brucehoult]

Ahhh .. I did that directly on ARM7TDMI, but  needed to use an A32 function to get 32x32 multiply, so CM0 won't have that.

Still, three multiplies (single cycle on every CM0 I've seen) and a handful of shifts (5?) and adds (3?) and ANDs (2) will let you do that in if I've counted right 13 cycles. Which is much faster than a bit by bit divide, and not much worse than the 7 cycles a UMULL plus shift takes on ARM7TDMI.

[AVI-crak]

A small test for cortex m0:

Code: [Select]

char* __attribute__(( noinline, used )) u32_char_m3 (char* tail_txt, uint32_t value)//204
{
    *tail_txt = 0;
    uint32_t res, tmp;
    do{
        tmp = ((uint64_t) value * 3435973837UL >> 32);
        res = value + '0';
        value = tmp >> 3;
        res -= value * 10;
        *(--tail_txt) = res;
    }while (value > 0);
    return tail_txt;
};

char* __attribute__(( noinline, used )) u32_char_shift (char* tail_txt, uint32_t value)//142
{
    *tail_txt = 0;
    uint32_t res, rem;
    do{
        res = value >> 1;
        res += res >> 1;
        res += res >> 4;
        res += res >> 8;
        res += res >> 16;
        rem = value + '0';
        value = res >> 3;
        res = value + (value << 2);
        rem -= res << 1;
        if (rem > ('9')){value++; rem -= 10;};
        *(--tail_txt) = rem;
    }while (value > 0);
    return tail_txt;
};

char* __attribute__(( noinline, used )) u16_char_m0(char* tail_txt, uint16_t value)//96
{
    uint32_t val = value;
    uint32_t res, tmp;
    do{
        res = val + '0';
        val *= 52429UL;
        val >>= 19;
        tmp = val + (val << 2);
        res -= tmp << 1;
        *(--tail_txt) = res;
    }while (val);
    return tail_txt;
};

char* __attribute__(( noinline, used )) _itoa_1(int val, int base)//100
{
    static char buf[32];
    int i=30;
    for(; val && i ; --i, val /= base)
      buf[i] = "0123456789ABCDEF"[val % base];
    return &buf[i+1];
};


int main(void)
{
    char texx1[12];
    char* out;
    uint16_t rez[16];
    uint32_t test, nc, hc;
    uint32_t tim;
    uint32_t dats[]= {1,65535,2147483647,4294967295};

    RCC->APB2ENR |= RCC_APB2ENR_TIM1EN;
    TIM1->PSC =1;
    TIM1->CR1 |= TIM_CR1_ARPE;
    TIM1->ARR = 65535;
    TIM1->DIER = TIM_DIER_UDE;
    TIM1->CR1 |= TIM_CR1_CEN;

    nc = -1; hc = 0;
do{
    test = dats[hc];
    tim = TIM1->CNT;
    out = u16_char_m0(&texx1[11],test);
    tim = TIM1->CNT - tim;
    rez[++nc] = (uint16_t) tim;
    printo("u16_char_m0=    ",out,", tic=",rez[nc],"\n");

    tim = TIM1->CNT;
    out = u32_char_shift(&texx1[11],test);
    tim = TIM1->CNT - tim;
    rez[++nc] = (uint16_t) tim;
    printo("u32_char_shift= ",out,", tic=",rez[nc],"\n");

    tim = TIM1->CNT;
    out = u32_char_m3(&texx1[11],test);
    tim = TIM1->CNT - tim;
    rez[++nc] = (uint16_t) tim;
    printo("u32_char_m3=    ",out,", tic=",rez[nc],"\n");

    tim = TIM1->CNT;
    out = _itoa_1(test, 10);
    tim = TIM1->CNT - tim;
    rez[++nc] = (uint16_t) tim;
    printo("_itoa=          ",out,", tic=",rez[nc],"\n\n");
    hc++;
}while(hc < 4);

while (1){};Test result:

u16_char_m0=    1, tic=99
u32_char_shift= 1, tic=131
u32_char_m3=    1, tic=183
_itoa=          1, tic=143

u16_char_m0=    65535, tic=303
u32_char_shift= 65535, tic=479
u32_char_m3=    65535, tic=723
_itoa=          65535, tic=997

u16_char_m0=    65535, tic=303
u32_char_shift= 2147483647, tic=461
u32_char_m3=    2147483647, tic=699
_itoa=          2147483647, tic=1465

u16_char_m0=    65535, tic=151
u32_char_shift= 4294967295, tic=461
u32_char_m3=    4294967295, tic=699
_itoa=          G, tic=109

 Cortex-M7:

u16_char_m0=    1, tic=26
u32_char_shift= 1, tic=48
u32_char_m3=    1, tic=30
_itoa=          1, tic=56

u16_char_m0=    65535, tic=62
u32_char_shift= 65535, tic=110
u32_char_m3=    65535, tic=64
_itoa=          65535, tic=120

u16_char_m0=    65535, tic=56
u32_char_shift= 2147483647, tic=96
u32_char_m3=    2147483647, tic=49
_itoa=          2147483647, tic=109

u16_char_m0=    65535, tic=28
u32_char_shift= 4294967295, tic=96
u32_char_m3=    4294967295, tic=49
_itoa=          ÿ, tic=24

[Nominal Animal]

Cortex-M0 (ARMv6-M) is an interesting architecture: 32-bit, no hardware division, only 32×32=low-32 multiplication which can either be a slow or a fast single-cycle one, and no DWT cycle counter support.  Compiler options (especially optimization, -O2 vs. -Os) matter a lot.
(I only have Cortex-M0+ (NXP Kinetis MKL26, Teensy LC), which has single-cycle 32×32=low-32 multiplication (and I/O port access), so my testing is limited.)

As to the itoa() implementation, I would suggest [Edited:]

Code: [Select]

char basis[] = "0123456789abcdef"; // assuming radix = 2..16

char *utoa(unsigned int val, char *dst, unsigned int radix)
{
    char *p = dst, *d = dst;
    do {
        *(p++) = basis[val % radix];
        val /= radix;
    } while (val > 0);
    *(p--) = '\0';
    while (d < p) {
        char  c = *d;
        *(d++) = *p;
        *(p--) = c;
    }
    return dst;
}

char *itoa(int val, char *dst, unsigned int radix)
{
    if (val < 0) {
        *dst = '-';
        utoa(-val, dst + 1, radix);
        return dst;
    } else {
        return utoa( val, dst, radix);
    }
}iff using __aeabi_uidivmod is acceptable.  As I already argued, I prefer a different interface myself.

Edited; the original version forgot to swap the digit order, and itoa returned dst+1.

[nctnico]

I have a feeling utoa is printing the numbers in reverse.

[AVI-crak]

As to the itoa() implementation, I would suggest

You cannot use an external buffer. You cannot use the function in several metas at once (debugging, exit to a graphical or character screen, log...).
If you need several functions that are identical in functionality, then you need to write several universal functions with a one-time use.
And in general, 2k memory is enough for everyone.

Stop using the microwave with kittens inside.!!!

[Nominal Animal]

I have a feeling utoa is printing the numbers in reverse.

Yep.

I forgot that when one returns the buffer pointer, and/or the string is expected to be at the beginning of the buffer, you need to either reverse the digits (as the fixed version above now does), or you build the string backwards and move the string to the origin of the buffer.

The reversing option is more robust, because callers might know the value is always say between -999999 and 9999999, and thus only reserve eight chars for buf.  The interface does not allow passing the buffer size, so we cannot do the move option safely.  (Except if we check the number of digits in the value first, and that'd be wasteful.)

Stop using the microwave with kittens inside.!!!

I assure you, my intent was only to suggest an improvement, not microwave kittens. 

[SiliconWizard]

An alternative method that tests the value and adds either '0' or 'A'-10 uses only 8 bytes of code.

And think about the case where one only needs to print base-10 numbers which is quite often in user interfaces of small gadgets!

Yes, if all you need is base 10, then do not write a generic function for any base, but one just for base 10. GCC and probably most decently recent compilers will optimize the divide and modulo using multiplication and bit shift only, which is insanely faster.

[AVI-crak]

I assure you, my intent was only to suggest an improvement, not microwave kittens. 

I don't know where it started, why this style became the standard, and I don't understand how you can use such functions without input parameter errors. This is wrong in itself.
1) The number input parameter must have a strict type, "int" is not suitable for this role at all - it is simply equal to the size of the microprocessor register. This point has already been discussed a thousand times. Valid: "int8_t, int16_t, int32_t" and so on.
2) The format number "uint32_t" can contain "int32_t" - but not vice versa. This means that you need a function for the unsigned number, which will additionally be used in the signed number function.
3) The strict type holds a limited range of possible number values, for example "uint32_t", and "int32_t" can contain up to 11 characters, and a terminating zero = 12 bytes. Making the buffer size no longer makes sense.
4) The most optimal and fastest algorithm is to fill the buffer from the end. Only one version of the string "0b01010011" is displayed head first. And there is a good reason for this - the number is bitwise shifted to the left and checked for "less than zero". The size is known, it's just a loop for "n" steps. This function doesn't even need to return a pointer!!
However, the "0b01010011" variant is considered stillborn, precisely for this reason (head first).
However, if the function fills the buffer from the end, this must be indicated in the name of the input parameter.
5) The buffer itself must have a static variable modifier outside the function boundary. This will force GCC to make copies of the buffers in every project file - wherever printing is used. In this case, printing will work without failures as part of the OS.

6) Variant of processing a number into a string "0xFFEE0111" - requires an explicit indication of the string size. This is the only function - which should produce a stable beautiful version. Well, or at least a multiple of two signs.
Because "0x11F" is guaranteed to break the neck of half of the string parsers. For example, GCC processes a fuzzy character set about 30 times slower.

If you do everything correctly - you get about the same set of functions as mine. Because it's convenient.
In addition, I showed a test of all the functions that appeared in this topic a little higher.
Next to each function \\ is the size in bytes. The execution time is marked in ticks (tic).

I deliberately showed the representation of the string in natural form. The translator is doing something strange, even I find it hard to understand in reverse translation.

[Nominal Animal]

I deliberately showed the representation of the string in natural form.

The interface and behaviour of functions named itoa(), ltoa(), utoa(), ultoa() is fixed by convention (and the principle of Least Surprise), as they are implemented in a few standard C libraries already.

Like I said, I prefer a different interface myself.  I've discussed the interfaces I prefer (in very memory-constrained situations) in this thread I started, as well as replies #68 and #80 in the current thread.

There are two ways to make the atoi-like interface safer, without wasting memory:

• const char *itoa(const int len, char buf[len], int val, const unsigned char radix);
  which constructs the number at the end of the buffer (with final character being nul, '\0'), and returns a pointer to the leading character of the string ((const char *)buf to (const char *)buf + len - 2), or a constant pointer TOA_ERROR which points to say "(?)" if the buffer is too small (otherwise first char is set to NUL) or radix is invalid.
   
• int itoa(const int len, char buf[len], int val, const unsigned char radix);
  which constructs the number at the beginning of the buffer, always including the nul at end, and returns the length of the string (excluding the nul), or a negative (with buf[0] == '\0') in case of an error like invalid radix or the buffer being too small.

In both cases, the compiler is will detect buffer overruns at compile time, in both callers and in the implementation itself.  This array parameter form is valid since C99, and only requires that the array size is preceded by the array itself in the parameter list.

Also, even when users do not check the return value, the buffer is initialized to a safe value even in case of error, making the error case obvious (so no silent truncation or such).

It makes sense for the generic versions to be implemented as static in a header file, to simply check len>1 and radix, and immediately return the error; possibly check val to handle negative values; and call the optimized radix-10, radix-16, radix-8, radix-2, or generic version (with a nonnegative val).  With --ffunction-sections -Wl,--gc-sections the unused ones are then not linked in at all, and whenever radix is constant, the optimized version is called directly.

The first interface uses the efficient divide-and-modulus by radix approach.  By letting it return a pointer to the beginning of the string, the number can be constructed backwards, and no swap-or-move is needed.  On Cortex-M0/M0+/M1, it will use one call to __aeabi_uidivmod per digit converted.
It is most useful when it is used in direct print()-like interfaces.

The second interface also uses the divide-and-modulus by radix approach, but typically in reverse, followed by a string-reverse.  This is useful, because it makes concatenating the number string to an existing buffer easier, with the cost of the additional string reversion (which is tiny).

1) The number input parameter must have a strict type, "int" is not suitable for this role at all - it is simply equal to the size of the microprocessor register. This point has already been discussed a thousand times. Valid: "int8_t, int16_t, int32_t" and so on.

This is dictated by the API.  I personally prefer to use fixed-size two's complement types and fast types: uintN_t, intN_t, uint_fastN_t, and int_fastN_t for N = 8, 16, 32, and 64 if supported.

Again, my preference aligns with yours, but if you implement an existing API like I did, using a name for a well-known function with well-known interface and behaviour, you better duplicate its interface and behaviour and not diverge, or you will lead others to write buggy code.

5) The buffer itself must have a static variable modifier outside the function boundary. This will force GCC to make copies of the buffers in every project file - wherever printing is used. In this case, printing will work without failures as part of the OS.

First, that wastes a lot of memory, and is absolutely not suitable for constrained situations.
Second, that will fail whenever two or more numbers are converted using the same function, and are used concurrently in the caller, i.e.
    char *xs = your_itoa(x, 10);
    char *ys = your_itoa(y, 10);
will yield either a copy or partial garbage of ys in xs.

Using mine, if I have earlier checks that verify -9999 <= x, y <= 99999, I could safely use in a function
    char  xs[6], ys[6];
    (void)itoa(x, xs, 10);
    (void)itoa(y, ys, 10);
with only 12 bytes used on stack for the two stringlets.  If I have no such checks, then [(278+sizeof(int)*CHAR_BIT*28)/93], which works for any number of bits.  (278 = 3*93-1, and 28/93≃0.301075269 > 0.301029996 ≃ log(2)/log(10).)

If you do everything correctly - you get about the same set of functions as mine. Because it's convenient.

No.  I suspect a bit of Dunning-Kruger here, because "convenient to the library developer" != "correct".

[AVI-crak]

It is very difficult to argue with you, almost impossible.
I'll be brief - the standard C libraries piss me off.

[Nominal Animal]

It is very difficult to argue with you, almost impossible.

Sorry about that.  It is not my intention.  I just want to get to the bottom of things, to discover the reasons behind various opinions, as that is the only way I can truly learn.  Simply adopting others' opinions – no matter from how respected an authority the opinion originates from – is just copying, not learning.

I wish I could do this without being 'almost impossible' to argue with because I often learn something new myself from such arguments.

I'll be brief - the standard C libraries piss me off.

I don't like it much myself either, especially in memory and resource restricted environments like microcontrollers.

Instead of trying to replace the entire C language wholesale, it is very possible to just replace the standard library with something else.  In the C standard, this is called the freestanding environment (the "normal" one is hosted environment).  When running under an OS, you do need to write the syscall wrapper/wrappers yourself (I recommend inline extended asm if using GCC, Clang, or compatible compilers) for your target architecture.

Simply put, if you are writing code for AVRs, using avr-libc is not a requirement, just an option.  Similarly for all other embedded development wrt. newlib.  You can do your own, and if you tell the compiler you want the freestanding environment, you don't need to implement the standard library API either.

[AVI-crak]

I just want to get to the bottom of things

Well, then, catch the brainwasher.
Play around with the number type "value", right in the function.
https://godbolt.org/z/son3EsKaK

[MMMarco]

Again, my preference aligns with yours, but if you implement an existing API like I did, using a name for a well-known function with well-known interface and behaviour, you better duplicate its interface and behaviour and not diverge, or you will lead others to write buggy code.

I agree with that. As others have already pointed out, it just happens to be that the C standard library API sucks to begin with.

[wek]

As others have already pointed out, it just happens to be that the C standard library API sucks to begin with.

C sucks to begin with. So what.

JW

[wek]

The good, the bad and the ugly: I've just dared to write this:

Code: [Select]

static const char * Num0_15(char * s, uint32_t n) {
  if (n <= 9) {
    s[0] = '0' + n; s[1] = '\0';
  } else {
    s[0] = '1'; s[1] = '0' + n - 10;  s[2] = '\0';
  }
  return s;
}
JW

[MMMarco]

As others have already pointed out, it just happens to be that the C standard library API sucks to begin with.

C sucks to begin with. So what.

JW

I don't think C sucks. Sure there are some things that are borderline evil like unsafe functions like gets etc. but I much prefer C over C++.

The question is, what other alternatives do you have for embedded apart from assembly, C and C++?

I know there is Rust and Go (if I'm not mistaken) but I think those projects are still in their early stages.

[Siwastaja]

C sucks to begin with. So what.

C core language is still quite A) consistent, B) powerful. Standard library on the other hand is very inconsistent and limited in its abilities (so that programmer needs to re-write simple things over and over again), it looks like some people just cobbled something together in 1970's and then it was locked down with no changes allowed. BTW, PHP standard library has the same problem, it's not well thought out but just some random shit put together.

C itself has improved through revisions like C89/90/99/11 etc. Those revision could easily have added new, better standard functions while leaving the old ones for compatibility - if there is will, there is way - but nope. Therefore I applaud Nominal Animal's effort in a replacement standard library and actually see a replacement over freestanding C much better than overly complicated stuff like Boost in C++.

[MMMarco]

BTW, PHP standard library has the same problem, it's not well thought out but just some random shit put together.

Thank you for saying this! PHP would be a pretty good language if it wasn't so inconsistent with its API and behaviour.

BTW, the inconsistencies of PHP are partly owed to the fact that C itself was inconsistent back when PHP was in its early stages.

And I 100% agree with

C core language is still quite A) consistent, B) powerful. Standard library on the other hand is very inconsistent and limited in its abilities [...]

The language itself is fine, it's just that the C standard functions are a mess.