Memory efficient int to chars without division (bitshift OK) for binary bases.

[zapta]

I guess it is architecture dependent whether code like "c < 10 ? c + '0' : c + 'A' - 10" uses less ROM than indexing a character array, e.g. "characters[c]" where

Code: [Select]

static char characters[] = {'0','1','2','3','4','5','6','7','8','9','A','B','C','D','E','F'};


IIRC avrgcc copies const arrays like this to RAM so this will also choose you RAM.

The flash is in different memory space that can't be accessed by standard C pointers.

[c4757p]

avr-gcc supports memory spaces now, so you can do:

Code: [Select]

static const __flash char characters[] = "0123456789ABCDEF";


[zapta]

avr-gcc supports memory spaces now, so you can do:

Code: [Select]

static const __flash char characters[] = "0123456789ABCDEF";


Good to know. I presume that you can also access it with standard array/pointer indexing rather than explicit flash read.

[c4757p]

Yes, that's the whole idea. Any pointer with the type qualifier __flash will be accessed as flash. There's also __memx, which uses 24-bit pointers with a bit specifying flash or RAM to linearize the address space - it automatically inserts the code the test which space the data is in.

Relatively new feature added to GCC itself, around 4.8ish I think. Named Address Spaces

[Kalvin]

I was able to squeeze the size to 199 bytes (112 + 87 bytes). Attached is the C source code and the generated assembly code.

[sleemanj]

Checked my algorithm using AVR C++ compiler (Arduino 1.6): 134 bytes + 87 bytes for the lookup table and the digits. However, the RAM size is *very* minimal as no digit buffer is required. (Changed the n and leadingzero from int to uint8_t in the the original code).

Edit: below was in regard to your first PROGMEM version

Nice job Kalvin, experimentally determined with -Os an a tiny13, compared to my implementation of TassiloH's process, your solution appears to use a couple bytes less SRAM (measured from inside writech()) and 32 bytes less flash, while still being easy to understand and handling decimals.  Well done that man.

Incidentally, I'm working on all this for a "more standardly capable" ATtiny13 Arduino "core", I may just have to adopt your ideas into what I did yesterday.

I have no practical use for it at all, but, you know, making it fit hooked me.

[westfw]

ATtiny13 doesn't have a multiplier.

x * 10 = (x << 3) + (x << 1) = ((x << 2) + x) << 1; 

Yeah, but the algorithm in question was multiplying by 1/10 (0x1999, I think?)  Rather more difficult.

[ralphd]

If you are writing a small Arduino core for the t13, I stripped down the Serial classs in picoWiring.
http://nerdralph.blogspot.ca/2015/10/beta-picowiring-arduino-compatible.html

For a small bitbang uart with timing accurate to within 1 cycle +-1, I don't think you'll find better than mine.
https://github.com/nerdralph/nerdralph/tree/master/avr/libs/bbuart

[sleemanj]

If you are writing a small Arduino core for the t13, I stripped down the Serial classs in picoWiring.

Yes I'm using your "AVR305 half-duplex serial uart implementation" (BasicSerial), wrapped into a stream handler.  It works very well.  On the 13 I wouldn't dare to dream of two-way serial, but one-way is just perfect.

[Kalvin]

Checked my algorithm using AVR C++ compiler (Arduino 1.6): 134 bytes + 87 bytes for the lookup table and the digits. However, the RAM size is *very* minimal as no digit buffer is required. (Changed the n and leadingzero from int to uint8_t in the the original code).

Edit: below was in regard to your first PROGMEM version

The first version is clean and maintainable. The latest version was just an effort to make it more compact at the price of code clarity. The main idea was to get rid of the switch statement and use a lookup table for the bases in order to save 20-30 bytes. And there were some dirty C hacks which reduced code size here and there.

Nice job Kalvin, experimentally determined with -Os an a tiny13, compared to my implementation of TassiloH's process, your solution appears to use a couple bytes less SRAM (measured from inside writech()) and 32 bytes less flash, while still being easy to understand and handling decimals.  Well done that man.

Incidentally, I'm working on all this for a "more standardly capable" ATtiny13 Arduino "core", I may just have to adopt your ideas into what I did yesterday.

I have no practical use for it at all, but, you know, making it fit hooked me.

Glad to hear that you found my code useful and might want to put it into good use. This was nice little puzzle for the Saturday night.

[ralphd]

If you are writing a small Arduino core for the t13, I stripped down the Serial classs in picoWiring.

Yes I'm using your "AVR305 half-duplex serial uart implementation" (BasicSerial), wrapped into a stream handler.  It works very well.  On the 13 I wouldn't dare to dream of two-way serial, but one-way is just perfect.

The version on my github is better.  No jitter between 1 and 0 bits now because I use the T bit instead of carry.

[ralphd]

If you are implementing millis(), I saw a tiny core that used the WD timer.  I'd do it as a 16-bit timer instead of 32 to save on memory.

[ralphd]

I was able to squeeze the size to 199 bytes (112 + 87 bytes). Attached is the C source code and the generated assembly code.

In practice I think that version will be larger since many programs only use decimal or hex.  With a switch instead of lookup table, unused code can be optimized away.

[Kalvin]

I was able to squeeze the size to 199 bytes (112 + 87 bytes). Attached is the C source code and the generated assembly code.

In practice I think that version will be larger since many programs only use decimal or hex.  With a switch instead of lookup table, unused code can be optimized away.

You are probably right, depending how good the optimizer is. That version was created just for testing the idea of replacing the switch statement with a lookup table, and its effect on code size. In that particular case the compiler produced smaller code. But the code is ugly and pretty much useless for a real project.

[SuzyC]

I am trying to understand the programming code in this thread but hit several bumps!

Someone please explain what is the meaning of the compound operator  statement: while(tbase>>=1)

while (tbase >>= 1) {
      c += c;
      if (n & 0x8000) {
        c += 1;
      }

Does it mean shift right and and compare the result =1?

[hamster_nz]

I am trying to understand the programming code in this thread but hit several bumps!

Someone please explain what is the meaning of the compound operator  statement: while(tbase>>=1)

while (tbase >>= 1) {
      c += c;
      if (n & 0x8000) {
        c += 1;
      }

Does it mean shift right and and compare the result =1?

Hi,

it means "while the result of halving tbase is not zero"

"tbase >>= 1" performs an shift to the right by one bit, with the result being the updated value for tbase

and of course "while(x)" will loop while the expression 'x' is non-zero.

So the whole loop could be re-written as

Code: [Select]

tbase = tbase/2;
while (tbase != 0) {
      c += c;
      if (n & 0x8000) {
        c += 1;
      }
      n += n;   // from original post
      tbase = tbase/2;
}


[sleemanj]

If you are implementing millis(), I saw a tiny core that used the WD timer.  I'd do it as a 16-bit timer instead of 32 to save on memory.

I think you're regarding "Coding Badly"'s (unfinished I think) arduino-tiny core v2 which I stumbled across a few days ago too.

I'm working on my fork of SpenceKonde's (detached) fork of TCWorlds fork of Coding Badly's original arduino-tiny which was presumably derived at some point from some standard arduino files at some revision, but there's no history of that.  I dug myself deeper and deeper into a hole for 2 days thinking I could figure out the history and rebase on top of a standard arduino core... fail.

I'll have to take a look at that CB did in his core2 to see what can be incorporated.  Looks like I have another hole to fall into....

[dannyf]

Code: [Select]

do
    {
        uint16_t b = *bt++;
        int n = 0;
        while (val >= b)
        {
            n++;
            val = val - b;
        }
        leadingzero = leadingzero ? leadingzero : n;
        if (b == 1 || leadingzero)
        {
            writech(digit[n]);
        }
    }
    while (*bt); 

this is what I used in performing long-multifications and long-divisions concurrently on a DDS:

Code: [Select]

   for( BitCount=W_AD9850; BitCount!=0; BitCount-- ) {
       Dividend <<= 1;
       Quotient <<= 1;

       if( Dividend >= Divisor ) {
           Dividend -= Divisor;

           Quotient |= 1;
       }
   }

It is fairly easy to re-write it for your purposes.

[dannyf]

A time-dumb but space-smart approach is to use successive subtraction to perform division.

For example, assume the following:

Code: [Select]

//return: quotient of dividend / divsor, plus remainder
uint32_t div10(uint32_t dividend, uint32_t divisor, and uint32_t *remainder);
Something like this may work for you:

Code: [Select]

  //convert val (0...9999) to a string in vRAM[]
  vRAM[0]=div10(val, 1000, &val) + '0';
  vRAM[1]=div10(val, 100, &val) + '0';
  vRAM[2]=div10(val, 10, &val) + '0';
  vRAM[3]=val + '0';

Writing div10() is fairly easy.

edit: compiled under an old winavr, the routine takes 148bytes of flash, unoptimized; 26 bytes of flash, optimized.

[dannyf]

An alternative approach, likely more time-efficient, is to use shifts to perform 10x multiplication, or even hardware multipliers, and use subtractions to perform division after that.

[westfw]

Someone please explain what is the meaning of the compound operator  statement: while(tbase>>=1)

while (tbase >>= 1) {

Shifts tbase one bit to the right, before comparing the result with 0.  It's supposed to be a smaller way of looping for n bits per digit, instead of having to derive "n
 separately.
This only works because the bases in question are all powers of two.  Base 16 is (1<<4) so the bitshift loop executes 4 times.  Base 8 is (1<<3) and we shift 3 bits.   Base 2 is (1<<1), so it's only one bit.

[ralphd]

FYI, the digispark tiny core has been reasonably well maintained.
https://github.com/digistump/DigistumpArduino

[richardman]

Or, my old favourite (the hypocrisy I'm demonstrating here is noted):

Code: [Select]

write(c["0123456789ABCDEF"]);
Think I made a mistake? Try it!

Learned that from PJ Plauger, the writer of the first commercial C compiler outside of Bell Labs, back in the 1980s.

Now explain it why it works. 

[ralphd]

Or, my old favourite (the hypocrisy I'm demonstrating here is noted):

Code: [Select]

write(c["0123456789ABCDEF"]);
Think I made a mistake? Try it!

Learned that from PJ Plauger, the writer of the first commercial C compiler outside of Bell Labs, back in the 1980s.

Now explain it why it works. 

Arrays are implemented as pointer addition.
arr

• == *arr + x == x[arr]

[grumpydoc]

Arrays are implemented as pointer addition.
arr

• == *arr + x == x[arr]

SMF formatting ate your answer a bit. Also I'd put in the extra step.

arr[y]  = *(arr + y)  = *(y + arr)  = y[arr]

EDIT: that's annoying - I wanted to use three-bar "is equivalent to", one of those symbols which looks OK in preview but not in the post. Had to use = instead  >:(