-
Memory efficient int to chars without division (bitshift OK) for binary bases.
Posted by
sleemanj
on 20 Nov, 2015 23:08
-
Very SRAM and Flash constrained microcontroller (ATtiny13) - this is an personal educational exercise more than anything so "change the micro" defeats the purpose.
Given an unsigned integer, and a base of 2, 8, or 16.
Given a function write(char) which outputs the given character.
Given that we can't use division (too expensive in code space, no hardware divide).
Given that it can be as slow as you want (optimise for space, not speed).
Given that it is RAM which is the issue, we can eat a small amount more ROM if necessary.
Can it be done better (less RAM usage) than this?
// base constrained to 2, 8 and 16, anything else will be promoted to 16 with 'x' prefixed
void printNumber(unsigned int n, uint8_t base)
{
char buf[17]; // worst case binary base, 16 characters, plus null
char *str = &buf[sizeof(buf) - 1];
*str = '\0';
uint8_t shifter = 0;
switch(base)
{
case 2: shifter = 1; break;
case 8: shifter = 3; break;
default: write('x');
case 16: shifter = 4; break;
}
do
{
char c = n - ((n >>= shifter)<<shifter);
*--str = c < 10 ? c + '0' : c + 'A' - 10;
} while(n);
while(*str)
{
write(*str++);
}
}
Edit to add: my thinking is that it is not possible, the only way to meaningfully do so would be to find a way to convert the integer most significant digits first (left to right) instead of least significant as current (right to left), if that was possible then buffer is no longer required. But is it possible? My brain is weak on this :-/
-
#1 Reply
Posted by
nctnico
on 20 Nov, 2015 23:57
-
The brute force method is to add an extra loop which gets to the first digit and then to the second. So basically going through the number a couple of times. The first iteration prints the left most digit and throws away the result of the rest. There is probably a more efficient method though.
-
#2 Reply
Posted by
TassiloH
on 21 Nov, 2015 00:00
-
You could do it like this:
- determine the value of the most significant digit of you base that fits into the unsigned int. For base-16, this would be 0x1000. Lets call this dvalue.
- while (dvalue) {
- set curent digit to 0. Lets call this digit.
- while (n>dvalue) {n-=dvalue; digit++}
- output digit
- switch (base) { case 2: dvalue>>=1; break; case 8: dvalue>>=3; break; case 16: dvalue>>=4; }
- }
If you need to suppress leading zeros, you can add a flag storing if something was already written and skip writing zeros if not.
-
#3 Reply
Posted by
richardman
on 21 Nov, 2015 00:02
-
char c = n - ((n >>= shifter)<<shifter);
Whatever you are trying to do, this is asking for trouble The evaluation order of "n" and "n >>= shifter" is undefined. So the first "n" may be before the shift or after. I write compilers and I just wrote a C book, I know this :-)
-
-
Why do "c = n - ((n >>= shifter) << shifter)" when you could just do "c = n & mask", where mask is 0x1, 0x7, or 0xF respectively?
-
#5 Reply
Posted by
westfw
on 21 Nov, 2015 01:07
-
The only way to meaningfully do so would be to find a way to convert the integer most significant digits first (left to right) instead of least significant as current (right to left), if that was possible then buffer is no longer required. But is it possible?
Of course it's possible, though it might be easier in assembly language (because you can shift into a new register.) Do you need leading-zero suppression?
-
#6 Reply
Posted by
sleemanj
on 21 Nov, 2015 01:14
-
Whatever you are trying to do, this is asking for trouble The evaluation order of "n" and "n >>= shifter" is undefined.
Interesting, I did wonder if I was kosher with that, avr-gcc gave the results I expected so left it as is, but I'll bow to your wisdom on that one
Why do "c = n - ((n >>= shifter) << shifter)" when you could just do "c = n & mask", where mask is 0x1, 0x7, or 0xF respectively?
I had an existing division based function and this was the way I did it in my head (divide became shift right, multiply became shift left)
You could do it like this:
Ah that is exactly what I needed, and here is the results, I can even extend it to base-10 without much more overhead....
printNumber(unsigned int n, uint8_t base)
{
unsigned int dValue;
switch(base)
{
case 2:
dValue = 32768;
break;
case 8:
dValue = 32768;
break;
case 10:
dValue = 10000;
break;
default:
write('x');
base = 16;
case 16:
dValue = 4096;
break;
}
uint8_t digit = (1 << 7); // Top bit indicates if have seen the msd or not, 0 = seen, 1 = not
while(dValue)
{
digit &= (1 << 7); // Clear bottom 7 bits
while(n >= dValue)
{
n -= dValue;
digit++;
}
// If the top bit is zero, or the bottom bits are greater than 0
// then we have a digit to print (top bit zero means we have seen
// the MSD and skipped the leading zeros)
if(!(digit & (1 << 7)) || (digit & ~(1<<7)) > 0 )
{
digit = digit & ~(1<<7); // Clears the top bit for us and gives the actual number
write(digit < 10 ? digit + '0' : digit + 'A' - 10);
digit = 0; // This is really peculiar, this really shouldn't be necessary since it's cleaned up
// at the top of the loop, but what is REALLY weird is that if you remove this line
// the flash usage INCREASES by about 25 bytes. Weird optimisation stuff I guess!
}
switch(base)
{
case 2: dValue >>= 1; break;
case 8: dValue >>= 3; break;
case 16: dValue >>= 4; break;
case 10:
switch(dValue)
{
case 10000: dValue = 1000; break;
case 1000: dValue = 100; break;
case 100: dValue = 10; break;
case 10: dValue = 1; break;
default: dValue = 0; break;
}
break;
}
}
return 1;
}
Edit: off-by-one error
-
#7 Reply
Posted by
rs20
on 21 Nov, 2015 01:47
-
Interesting, I did wonder if I was kosher with that, avr-gcc gave the results I expected so left it as is, but I'll bow to your wisdom on that one
It turns out "undefined" doesn't mean "basically works the way you'd expect", it actually means "basically works the way you'd expect until you stop debugging/deploy to production".
In other words, undefined means "obey's Murphy's Law".
More concretely, this sort of thing is what leads to software suddenly not working when you enable optimizations, update your compiler, move to a different platform, etc...
-
#8 Reply
Posted by
westfw
on 21 Nov, 2015 01:48
-
void pNumber(unsigned int n, uint8_t base)
{
uint8_t tbase, c, ndigits;
switch (base)
{
case 2: ndigits = 16; break;
case 8: ndigits = 5;
// Base 8 needs some additional processing because 16 is
// not a multiple of 3.
if (n & 0x8000) {
Serial.write('1');
} else {
Serial.write('0');
}
n += n; // Shift left.
break;
default: Serial.write('x');
case 16: ndigits = 4; break;
}
while (ndigits--) {
tbase = base;
c = 0;
while (tbase >>= 1) {
c += c;
if (n & 0x8000) {
c += 1;
}
n += n;
}
Serial.write(c < 10 ? c + '0' : c + 'A' - 10);
}
}
-
#9 Reply
Posted by
hamster_nz
on 21 Nov, 2015 03:44
-
There is always the shift and carry sort of approach - only needs 1 byte of RAM per char of result.
It is something like....
function convert_to_chars(n.base)
/* Empty out result */
for j = 1 to number of chars in result
result[j] = 0;
next
/* Shift bit by bit into the result */
for i = 1 to number of bits in n
if MSB of n is set
carry = 1
else
carry = 0
end if;
for j = 1 to number of chars in result
result[j] = (result[j] << 1) + carry
carry = 0;
if result[j] < base then
result[j] = result[j] - base;
carry = 1;
end if;
next
n = n <<1;
next
/* Convert to chars */
for j = 1 to number of chars in result
if result[j] > 9 then
result[j] = result[j]-10+'A';
else
result[j] = result[j] +'0';
end if;
next
end function
-
#10 Reply
Posted by
rs20
on 21 Nov, 2015 03:51
-
void pNumber(unsigned int n, uint8_t base)
{
uint8_t tbase, c, ndigits;
switch (base)
{
case 2: ndigits = 16; break;
case 8: ndigits = 5;
// Base 8 needs some additional processing because 16 is
// not a multiple of 3.
if (n & 0x8000) {
Serial.write('1');
} else {
Serial.write('0');
}
n += n; // Shift left.
break;
default: Serial.write('x');
case 16: ndigits = 4; break;
}
while (ndigits--) {
tbase = base;
c = 0;
while (tbase >>= 1) {
c += c;
if (n & 0x8000) {
c += 1;
}
n += n;
}
Serial.write(c < 10 ? c + '0' : c + 'A' - 10);
}
}
Hmm, why would you respond with deliberately obfuscated code?
-
#11 Reply
Posted by
westfw
on 21 Nov, 2015 06:08
-
It's not supposed to be obfuscated. It has more comments than the other posted code.
It is supposed to be avoiding calculations of additional values that already have an equivalent. ( ie number of bits when there is already 2<<bits....)
-
#12 Reply
Posted by
rs20
on 21 Nov, 2015 06:46
-
It's not supposed to be obfuscated. It has more comments than the other posted code.
It is supposed to be avoiding calculations of additional values that already have an equivalent. ( ie number of bits when there is already 2<<bits....)
I think the line "n += n; // Shift left" is probably more clearly stated as "n <<= 1; // Shift left". Arguably, the comment becomes redundant... And surely any decent compiler will arrive at the same opcode regardless.
Same comments for "for (tbase = base; tbase != 0; tbase >>= 1)". Believe me, I love writing tricky code like yours, but I do it in the privacy of my own home...
-
#13 Reply
Posted by
dfmischler
on 21 Nov, 2015 07:27
-
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
static char characters[] = {'0','1','2','3','4','5','6','7','8','9','A','B','C','D','E','F'};
-
#14 Reply
Posted by
rs20
on 21 Nov, 2015 07:40
-
Or, my old favourite (the hypocrisy I'm demonstrating here is noted):
write(c["0123456789ABCDEF"]);
Think I made a mistake? Try it!
-
#15 Reply
Posted by
T3sl4co1l
on 21 Nov, 2015 08:21
-
English integers are printed in reverse order, so you necessarily have to start at the LSBs, divide to find the last digit, then the second last, and so on until zero (or continuing past zero until the required number of digits have been generated, if you want leading zeroes). These have to go in a sequential array (buffer), so that they can come out correct (left to right, rising index) if the entries were stored backwards (i.e., descending index).
Now, if you can do shifts instead of divisions, you can cheat, and obtain the digits directly without dividing. So you can do it in O(1) memory, i.e., no array/buffer. You have to know what size of number you're starting with (and you have to iterate through zeroes whether you print them or not, rather than terminating on the first zero), but that's rather trivial as the datatype must be specified in the first place. (Speaking of, do use size-specific integers! int should be deprecated, because it has inconsistent sizes on different platforms. uint16_t and such are preferred.)
As for actual memory usage, you'll have to check the assembled output. Even on "high" optimization settings, C compilers are usually mediocre (and this has been my experience with GCC on AVR). The entirety of this routine should be doable in maybe three registers, including the input variable, and probably under 50 words of instructions. It will incur more stack size than strictly necessary, of course, due to its own footprint and that of the write(char) function required. (If you wish to save that as well, consider combining them into a custom function. It will take more ROM due to the duplication of write functionality though. Which might perhaps be saved by nesting jumps inside the assembly routine ... ah, but now we're bordering on the dark realm of spaghettification in search of dubious bytes, so I shall digress.)
Justification for "reverse order", as it may not be obvious:
1. Wouldn't it be nice to tell how big a number is, at a glance?
2. Wouldn't it make sense that, each subsequent digit you read, is getting more and more significant, until the final and most significant digit at the end?
3. Wouldn't it make sense that integer and fractional parts read with the same order of significance?
4. Wouldn't it be easier to write all of these on a [little-endian] computer system?
If one million were written "0000001", then it would be very simple to print: each character (or position in the write buffer, incrementing from left to right) is generated in order, from each division step, in real time, no buffering needed.
This is very natural to a [little-endian] computer, because if you mentally group the bits in a variable as numerals in a base-2^N number, then you can treat each group in precisely the same order, as stored in memory and as printed to the screen. Suppose instead of hexadecimal (4 bits per digit), you have, sexaquinbicentimal I suppose it would be (i.e., base 256, 8 bits per digit -- a byte at a time). And suppose you have a 32 bit integer stored in byte-width memory. This number has up to four digits (except not "digits", but, sexaquinbicentits? erm, nevermind..). The first byte (at address (pointer)) is the low byte, the ones column (except not really "ones", but representing the addition of 0-255 to the total). The second byte is in the second address, (pointer+1), and represents "256s column" (a value of 0-255, multiplied by 256^1). And so on, with the high byte at (pointer+3) being the most significant. To print this number (in base 256, assuming you had a character encoding to do so), you simply copy the bytes straight out of memory!
Note that:
1. The order of magnitude is simply the number of digits (well.. duh, it always has, that's no help),
2. The weight of each digit is increasing, at the same time the address is increasing, and at the same time the iterations are increasing.
Everything is always consistently increasing, from left to right.
Conversely, for fractional components, starting from the decimal point, you multiply iteratively, so that the overflow from each step is the digit to print or store. (Which again, in base 2^N, is just shifting.) These come out as correct (normal reading) order as-is, so nothing's wrong to begin with. That's good.
Although, if we were to start writing numbers as, e.g. "one thousand and three sixteenths" =>
0001.1875
we have the problem of increasing power, then a sudden jump to decreasingly negative powers!
I would propose that numbers "should" be written thusly:
0001
.1875
so that, from left to right, the orders are always iterating, one in the positive direction and one in the negative direction. It's complementary. You can tell at a glance what the integral and fractional parts are (just as you can tell with the proper fraction "1000 3/16"). And you can compute, represent and store them at the same time (i.e., within the same loop, one digit of each at a time), on a little-endian computer, without any extra trouble.
This does hinge on the commonality of the little-endian computer. Reverse digit order would be just as justifiable on a big-endian machine. However, we commonly refer to the "upper" bits positively: bit 7 is stored in byte 0, so bit 8 should be stored in byte 1, not byte -1. I suggest little-endian is the more ideal system for this reason. (Which, still, is rooted in our bias towards incrementality, if that can be considered such a thing. But having one or two of something still makes more physical sense than the absence of one or two, so this doesn't seem like much of a cop-out, even on an abstract basis. That is, the notion of positivity is rooted in "successor of" and set theory counting principles, with negative numbers seemingly defined by abstraction of the process.)
Tim
-
#16 Reply
Posted by
Kalvin
on 21 Nov, 2015 14:09
-
My solution is a bit brute-force but it doesn't require shifts, multiplications or divisions. I also handles base 10 and leading zero suppression. Using lookup table should consume less code memory compared to more complicated algorithms (just my guess).
#include <stdio.h>
#include <stdint.h>
void writech(char ch)
{
printf("%c", ch);
}
void writenum(uint16_t val, uint8_t base)
{
static const char digit[] = "0123456789ABCDEF";
static const uint16_t base2[] = {0x8000, 0x4000, 0x2000, 0x1000, 0x800, 0x400, 0x200, 0x100, 0x80, 0x40, 0x20, 0x10, 0x8, 0x4, 0x2, 0x1, 0};
static const uint16_t base8[] = {0x8000, 0x1000, 0x0200, 0x0040, 0x0008, 0x0001, 0};
static const uint16_t base10[] = {10000, 1000, 100, 10, 1, 0};
static const uint16_t base16[] = {0x1000, 0x0100, 0x0010, 0x0001, 0};
uint16_t const * bt;
int leadingzero = 1;
switch(base)
{
case 2: bt = base2; break;
case 8: bt = base8; break;
case 10: bt = base10; leadingzero = 0; break;
case 16: bt = base16; break;
default: return;
}
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);
}
int main()
{
uint16_t n;
n = 0;
writenum(n, 2); writech('\n');
writenum(n, 8 ); writech('\n');
writenum(n, 10); writech('\n');
writenum(n, 16); writech('\n');
n = -1;
writenum(n, 2); writech('\n');
writenum(n, 8 ); writech('\n');
writenum(n, 10); writech('\n');
writenum(n, 16); writech('\n');
n = 1024;
writenum(n, 2); writech('\n');
writenum(n, 8 ); writech('\n');
writenum(n, 10); writech('\n');
writenum(n, 16); writech('\n');
return 0;
}
-
#17 Reply
Posted by
T3sl4co1l
on 21 Nov, 2015 19:35
-
This looks *really* heavy weight... like, no compiler on Earth will make that very small. (Example: appreciate what code a switch statement compiles into!)
FWIW, division by a known constant can be implemented as multiplication by a fraction, so the code and cycles required can be quite modest:
;
; uDivTen
;
; Unsigned division by ten. 45 words, takes 60 cycles (plus rcall).
;
; Input:
; r17:r16 = operand
; Output:
; r1:r0 = quotient
; r3:r2 = remainder
; (r16 = 10, r17 = 0)
;
uDivTen:
push r7 ; register usage:
push r6 ; r7:r6 = operand (in[0..1])
push r5 ; r5:r4:r3:r2 = 40 bit accumulator, D[1..3] (byte 0 discarded)
push r4 ; r1:r0 = partial products
movw r6, r16 ; r16 = temp, r17 = zero
clr r17 ; (but first, save operand)
; multiply by K = 2^20 * 16 / 10 to make D[0..3] = in[0..1] * K[0..2]
; (implicitly discarding D[0])
ldi r16, (((exp2(24) / 10) + 1) & (0x0000ff << 16)) >> 16
mul r7, r16 ; in[1] * K[2]
movw r4, r0 ; save high word
ldi r16, (((exp2(24) / 10) + 1) & (0x0000ff << 0)) >> 0
mul r7, r16 ; in[1] * K[0]
movw r2, r0 ; save low word
mul r6, r16 ; in[0] * K[0]
add r2, r1 ; accumulate to D[1] (discard lowest byte)
adc r3, r17
adc r4, r17
adc r5, r17
ldi r16, (((exp2(24) / 10) + 1) & (0x0000ff << 8)) >> 8
mul r6, r16 ; in[0] * K[1]
add r2, r0 ; accumulate to D[1..2]
adc r3, r1
adc r4, r17
adc r5, r17
mul r7, r16 ; in[1] * K[1]
add r3, r0 ; accumulate to D[2..3]
adc r4, r1
adc r5, r17
ldi r16, (((exp2(24) / 10) + 1) & (0x0000ff << 16)) >> 16
mul r6, r16 ; in[0] * K[2]
add r3, r0 ; accumulate to D[2..3]
adc r4, r1
adc r5, r17
; dig remainder out of the fractional part
ldi r16, 0x10 ; rounding bit
add r3, r16
ldi r16, 10
mul r3, r16 ; frac * 10
mov r2, r1
clr r3
movw r0, r4 ; quotient out
; r3 = 0, r2 = [0...9], r1:r0 = [0...6553]
pop r4
pop r5
pop r6
pop r7
ret
; END PROC uDivTen
The string function using this operation has the heading,
;
; toDec16u
;
; Converts the given number to an ASCIIZ string representing its
; unsigned decimal value.
;
; Executes in 83-329 cycles (24 + (59-61)*N digits).
;
; Input:
; r17:r16: number to convert
; Register X: buffer location in SRAM (maximum 6 bytes required)
; Returns:
; nothing (modified buffer).
; (X --> byte after end of string; r16 = ASCII code of last digit,
; r17 = 0)
Longhand division (16 bits) takes ~200 cycles a go (>1000 cycles for a 5 digit string!), so it helps quite a bit.
Tim
-
#18 Reply
Posted by
Kalvin
on 21 Nov, 2015 20:53
-
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).
-
#19 Reply
Posted by
rs20
on 21 Nov, 2015 21:33
-
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).
I would have thought that as you've written it, all those lookup tables are loaded into RAM on startup, so your RAM usage would be huge, comparable to the code size.
EDIT: Confirmed, commenting out the insides of your function reveals that it consumed 88 bytes of RAM. You need to use PROGMEM and calls into avr/pgmspace.h to prevent that.
-
#20 Reply
Posted by
Kalvin
on 21 Nov, 2015 21:58
-
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).
I would have thought that as you've written it, all those lookup tables are loaded into RAM on startup, so your RAM usage would be huge, comparable to the code size. You need to use PROGMEM and calls into avr/pgmspace.h to prevent that.
You are right. However, I wasn't intended to target it to AVR in the first place, so I missed that one. Here's code with proper PROGMEM directives. Code size is 144 bytes plus 87 bytes lookup data. 10 bytes more with PROGMEM pointer access. The attachment contains the source code and the assembly listing for the function.
-
#21 Reply
Posted by
westfw
on 21 Nov, 2015 23:28
-
you necessarily have to start at the LSB
nonsense. The "repeated subtractions of powers of (base)" algorithm starts with the MSD and works fine for any base. IIRC there is some pretty highly optimized code out there for implementing the repeated subtractions. It does lose some attractiveness if you have to implement multiple bases.
Otherwise:
http://www.ietf.org/rfc/ien/ien137.txt :-)
division by a known constant can be implemented as multiplication by a fraction
ATtiny13 doesn't have a multiplier.
I love writing tricky code like yours, but I do it in the privacy of my own home.
I *was* in the privacy of my own home :-)
I wonder if the code/ram usage would be smaller overall if we implemented three different functions for the different bases...
The original code (compiled for Arduino MEGA, which is what I had hooked up at the time) is 164 bytes of program code, and the 17 bytes of stack frame, plus 4 bytes of saved registers on the stack. pNumber is 136 bytes of code and 4 bytes of saved registers.
-
#22 Reply
Posted by
T3sl4co1l
on 21 Nov, 2015 23:55
-
division by a known constant can be implemented as multiplication by a fraction
ATtiny13 doesn't have a multiplier.
Ah yeah, that's true. In that case, multiplication is still a bit faster than division, but if you have other things to be doing alongside, it may be worth actually performing the division (i.e., you may spend as much time half-assing it as just doing it straightaway).
The algorithms for multiplication and division are very similar: shift and conditional accumulate (or in the case for division, the shifting and accumulation are reversed in sign).
Tim
-
#23 Reply
Posted by
rs20
on 22 Nov, 2015 00:43
-
ATtiny13 doesn't have a multiplier.
x * 10 = (x << 3) + (x << 1) = ((x << 2) + x) << 1;
-
#24 Reply
Posted by
Lukas
on 22 Nov, 2015 00:46
-