[SOLVED] Decimal to ascii using reduced instruction cycles

[ponnus]

Hai,
I want to enter digits into a character array. For example, I want to enter decimal 123 as '1','2','3'.
But it should take only few instruction cycles.

I tried sprintf, but it is taking too much time.

I also tried to convert the decimal number to hex, separate each nibble of the hex ,add 0x30 to convert to ascii. But, decimal to hex conversion used division in that, which takes more time than actually needed.

So, is there any way to print digits to ascii or an easy method for division(such as using shifts) which use only few instruction cycles?

Thank you

 

[alexan_e]

There is no way to do it just with a few instructions , it will take about 100 cycles and maybe more.

I'm not sure what is the range that you refer to but check https://www.avrfreaks.net/index.php?name=PNphpBB2&file=viewtopic&p=1018549#1018549, it is intended to convert a 10bit ADC result (0-1023) but can be modified for any range

 

[ponnus]

Hai,
Thank you very much.....I'm having the same issue....
I'll check it....

Thanks

 

[FvM]

For a binary to decimal conversion that doesn't involve division/modulo function, you may want to review the double dabble algorithm. https://en.wikipedia.org/wiki/Double_dabble

In C-programming, itoa() or sprintf() are mostly the reasonable method.

 

[alexan_e]

For a binary to decimal conversion that doesn't involve division/modulo function, you may want to review the double dabble algorithm. http://en.wikipedia.org/wiki/Double_dabble

This is a great method but kind of tricky to apply in C at least when trying to get the most efficient code

In C-programming, itoa() or sprintf() are mostly the reasonable method.

Not the most efficient way for a microcontroller, for example in AVR the clocks that a utoa takes for three digit conversion is about 700 when a custom routine can do it in less that 1/4 of that.
sprintf is similarly inefficient (actually worse) so when looking for the most efficient code I don't think it is the way to go

- - - Updated - - -

By the way this is another implementation that achieves even less cycles that the previous link I have provided using a half-interval search algorithm
http://www.avrfreaks.net/index.php?name=PNphpBB2&file=viewtopic&p=1018577#1018577

 

[FvM]

This is a great method but kind of tricky to apply in C at least when trying to get the most efficient code

Yes, but it's the closest answer to the question in the original post ("using shifts").

 

[kripacharya]

Hai,
I want to enter digits into a character array. For example, I want to enter decimal 123 as '1','2','3'.
But it should take only few instruction cycles.
.......I also tried to convert the decimal number to hex, separate each nibble of the hex ,add 0x30 to convert to ascii. But, decimal to hex conversion used division in that, which takes more time than actually needed.

when you say decimal, what exactly do you mean ? is your data already in BCD form ?
I have to assume it is, otherwise why would you need/ want to convert to hex.

And if it is, then all you need to do is add 48 (0x30) to each, and you're done. If its packed, then a mask & swap is all the additional thats required. 3-4 cycles tops on an AVR

Or am i missing something......

 

[ponnus]

Hai alexan_e,
Thanks for the link.
I checked the link you provided. I found that ChaunceyGardiner has provided an efficient code for the conversion. But, unfortunately, I need to convert numbers greater than 1023. So, I'm checking your code 'ULongToStr ' for the conversion and will reply you back.

Actually, I'm using PIC24FJ128GA010 with 32MHz clock and C30 compiler. Suppose if the code takes 100 cycles to convert one number(say 123d) to ascii('1','2','3'), then time for the conversion in this device is (FOSC/2)*100. Sorry, if I am wrong

I'll try the code and i'm also planning to change my platform to dsPIC with 80MHz clock, hope I can run the program faster.

Hai kripacharya,

I've a number (say 20d or 14h). I want to split 2 and 0 and enter to a character array as '2' and '3'.
If I need '1' and '4', then I can easily do that as you said. but that's not what I needed.

Thanks

 

[kripacharya]

Okay so thats cleared up. But do you know what is your largest number to be converted ?
Generic library functions are designed to be able to handle unknown lengths, hence take longer. With a known length/ size I would think using the double dabble would probably be the fastest - as also suggested by FvM

 

[ponnus]

Hai,
Now I changed my decision of converting larger numbers. i decided to print values from a 12 bit ADC.
So, I need to convert values upto 4095. i'm trying to edit the double dabber algorithm code which I got from the link provided by alexan_e.

Thanks

 

[alexan_e]

So, I need to convert values upto 4095. i'm trying to edit the double dabber algorithm code which I got from the link provided by alexan_e.

There was no function using the double dabber algorithm in the avrfreaks link I have provided, do you mean the link that FvM has provided to the wikipedia article that has a C function example?

- - - Updated - - -

The function of the first link I have provided can be modified for 12bit values like

void adc2ascii(uint16_t value, char *str)
{
    char *p = str;
		
		if      (value > 3999) { *p++ = '4'; value -= 4000; }
        else if (value > 2999) { *p++ = '3'; value -= 3000; }
        else if (value > 1999) { *p++ = '2'; value -= 2000; }
        else if (value > 999) { *p++ = '1'; value -= 1000; }
		else 				  { *p++ = '0'; }
				
        if      (value > 899) { *p++ = '9'; value -= 900; }
        else if (value > 799) { *p++ = '8'; value -= 800; }
        else if (value > 699) { *p++ = '7'; value -= 700; }
        else if (value > 599) { *p++ = '6'; value -= 600; }
        else if (value > 499) { *p++ = '5'; value -= 500; }
        else if (value > 399) { *p++ = '4'; value -= 400; }
        else if (value > 299) { *p++ = '3'; value -= 300; }
        else if (value > 199) { *p++ = '2'; value -= 200; }
        else if (value >  99) { *p++ = '1'; value -= 100; }
		else 				  { *p++ = '0'; }

        if      (value > 89) { *p++ = '9'; value -= 90; }
        else if (value > 79) { *p++ = '8'; value -= 80; }
        else if (value > 69) { *p++ = '7'; value -= 70; }
        else if (value > 59) { *p++ = '6'; value -= 60; }
        else if (value > 49) { *p++ = '5'; value -= 50; }
        else if (value > 39) { *p++ = '4'; value -= 40; }
        else if (value > 29) { *p++ = '3'; value -= 30; }
        else if (value > 19) { *p++ = '2'; value -= 20; }
        else if (value >  9) { *p++ = '1'; value -= 10; }
        else if (p != str)   { *p++ = '0'; }

        *p++ = value + '0';
		
     *p = 0;
}

- - - Updated - - -

And this is the modified 12bit version of the one using the half-interval method which will be faster

void adc2ascii(uint16_t value, char *str)
{
    char *p = str;
	
		if (value > 2999)
		{
			if (value > 3999) { *p++ = '4'; value -= 4000; }
			else             { *p++ = '3'; value -= 3000; }
		}
		else
		{
			if      (value > 1999) { *p++ = '2'; value -= 2000; }
			else if (value >  999) { *p++ = '1'; value -= 1000; }
			else 				   { *p++ = '0'; }
		}
			
        if (value > 499)
        {
            if (value > 699)
            {
                if      (value > 899) { *p++ = '9'; value -= 900; }
                else if (value > 799) { *p++ = '8'; value -= 800; }
                else                  { *p++ = '7'; value -= 700; }
            }
            else
            {
                if (value > 599) { *p++ = '6'; value -= 600; }
                else             { *p++ = '5'; value -= 500; }
            }
        }
        else
        {
            if (value > 299)
            {
                if (value > 399) { *p++ = '4'; value -= 400; }
                else             { *p++ = '3'; value -= 300; }
            }
            else
            {
                if      (value > 199) { *p++ = '2'; value -= 200; }
                else if (value >  99) { *p++ = '1'; value -= 100; }
				else 				  { *p++ = '0'; }
            }
        }

        if (value > 49)
        {
            if (value > 69)
            {
                if      (value > 89) { *p++ = '9'; value -= 90; }
                else if (value > 79) { *p++ = '8'; value -= 80; }
                else                 { *p++ = '7'; value -= 70; }
            }
            else
            {
                if (value > 59) { *p++ = '6'; value -= 60; }
                else            { *p++ = '5'; value -= 50; }
            }
        }
        else
        {
            if (value > 19)
            {
                if      (value > 39) { *p++ = '4'; value -= 40; }
                else if (value > 29) { *p++ = '3'; value -= 30; }
                else                 { *p++ = '2'; value -= 20; }
            }
            else
            {
                if      (value >  9) { *p++ = '1'; value -= 10; }
                else if (p != str)   { *p++ = '0'; }
            }
        }
    

    *p++ = value + '0';
    *p = 0;
}

 

[ponnus]

Oh,,Sorry...I meant this one .

void adc2ascii(unsigned short value)
{
    unsigned char v, a, b;
    if (value > 499)
    {
        if (value > 799)
        {
            if (value > 999)
            {
                // Treated as a special case as there
                // are only 24 values above 999
                str[0] = '1';
                str[1] = '0';

                v = value - 1000;
                if      (v > 19) { str[2] = '2'; v -= 20; }
                else if (v >  9) { str[2] = '1'; v -= 10; }
                else             { str[2] = '0'; }

                str[3] = v + '0';
                str[4] = 0;
                return;
            }

            if (value > 899) { a = '9'; v = value - 900; }
            else             { a = '8'; v = value - 800; }
        }
        else if (value > 699) { a = '7'; v = value - 700; }
        else if (value > 599) { a = '6'; v = value - 600; }
        else                  { a = '5'; v = value - 500; }
    }
    else if (value > 299)
    {
        if (value > 399) { a = '4'; v = value - 400; }
        else             { a = '3'; v = value - 300; }
    }
    else if (value > 199) { a = '2'; v = value - 200; }
    else if (value >  99) { a = '1'; v = value - 100; }
    else                  { a = '0'; v = value; }

    if (v > 49)
    {
        if (v > 69)
        {
            if      (v > 89) { b = '9'; v -= 90; }
            else if (v > 79) { b = '8'; v -= 80; }
            else             { b = '7'; v -= 70; }
        }
        else if (v > 59) { b = '6'; v -= 60; }
        else             { b = '5'; v -= 50; }
    }
    else if (v > 19)
    {
        if      (v > 39) { b = '4'; v -= 40; }
        else if (v > 29) { b = '3'; v -= 30; }
        else             { b = '2'; v -= 20; }
    }
    else if (v > 9) { b = '1'; v -= 10; }
    else            { b = '0'; }

    if (a == '0')
    {
        if (b == '0')
        {
            str[0] = v + '0';
            str[1] = 0;
        }
        else
        {
            str[0] = b;
            str[1] = v + '0';
            str[2] = 0;
        }
    }
    else
    {
        str[0] = a;
        str[1] = b;
        str[2] = v + '0';
        str[3] = 0;
    }
}

But the code using half interval time is suitable for my application..Thanks

 

[alexan_e]

But the code using half interval time is suitable for my application..Thanks

It basically uses a binary search pattern.
For the modified version that works with 12bit values (0-4095) refer to the second function in my previous post, I believe that this method gives the best compromise between speed and size.

A conversion based on a flash lookup table would be almost instant but it takes a lot of space.

 

[doraemon]

Hello!

As there are many microcontrollers in the 12-bit ADC range, another way to do it
is to use a multiplication instead of a division (if dividing by 10, use a coefficient
for 1/10). This way you can perform a division by 10 in a few clocks (I just tried
with MSP430 : 2 clocks for the multiplication by 1/10, and 2 to move the result)
and also 2 clocks for the x10 multiplication.

And the bonus: no huge lookup table, no endless if-else statements. It can be
written a little bit shorter at the expense of efficiency (with a loop).

Here is the trick. Example with a = 1234.

1. Divide by 10, obtain 123
2. Multiply 123 by 10, obtain 1230
3. Last digit is the original value (1234) to which 1230 has been subtracted.
4. Set the original value to 123, repeat the trick until done.

As for the code (see below), without further optimization than the normal one (low optimization),
I get 100 clocks for this method, vs 82 ~ 91 for the half interval method above. The variation
is due to the number of if..else needed for a given number.

BUT: this method can translate any number from 0 to 9999, so the range is twice the
half-interval method.

NB: This code is not portable. It is efficient because of the hardware multiplier.
It can be done without hardware multiplier by using 32 bit multiplications and would
also be quite fast, I believe.

---

Code C - [expand]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
#include "MSP430F5529.h"
#include "Types.h"
 
void adc2ascii(uint16 value, char *str) ;
void IToA(uint16 value, char * str);
 
char str1[6];
char str2[6];
 
void main(void) {
    uint16 i;
    uint16 div10, trick10;
    MPY = 6554;
    for(i = 100 ; i < 200 ; ++i) {
        IToA(i, str1);      //  Runs in 100 clocks for range [0..9999] (*)
        adc2ascii(i, str2);     //  Runs in 82 to 91 clocks for range [0..4999]
    }
}
 
// (*) The above figures are given for MSP430F5529, IAR compiler, with low optimization
//
void IToA(uint16 value, char * str) {
    //  Get d0
    MPY = 6554;                 //  Divide by 10
    OP2 = value;                //  Example val = 1234
    MPY=10;                     //  Multiply by 10
    OP2 = RES1;                 //  Recycle last result as an operand to multiply it back by 10
    str[3] = '0' + value - RES0;
    value = OP2;                //  Use last operand (that was divided by 10 as a new value, and do the same stuff again.
    MPY = 6554;
    OP2 = value;
    MPY=10;
    OP2=RES1;
    str[2] = '0' + value - RES0;
    value = OP2;
    MPY = 6554;
    OP2 = value;
    str[0] = '0' + RES1;
    MPY=10;
    OP2=RES1;
    str[1] = '0' + value - RES0;
}
 
 
void adc2ascii(uint16 value, char *str) {
    char *p = str;
        if (value > 2999) {
            if (value > 3999) {
                *p++ = '4';
                value -= 4000;
            }
            else {
                *p++ = '3';
                value -= 3000;
            }
        }
        else {
            if(value > 1999) {
                *p++ = '2';
                value -= 2000;
            }
            else if(value >  999) {
                *p++ = '1';
                value -= 1000;
            }
            else {
                *p++ = '0';
            }
        }
        if (value > 499) {
            if (value > 699) {
                if (value > 899) {
                    *p++ = '9';
                    value -= 900;
                }
                else if (value > 799) {
                    *p++ = '8';
                    value -= 800;
                }
                else {
                    *p++ = '7';
                    value -= 700;
                }
            }
            else {
                if (value > 599) {
                    *p++ = '6';
                    value -= 600;
                }
                else {
                    *p++ = '5';
                    value -= 500;
                }
            }
        }
        else {
            if (value > 299) {
                if (value > 399) {
                    *p++ = '4';
                    value -= 400;
                }
                else {
                    *p++ = '3';
                    value -= 300;
                }
            }
            else {
                if (value > 199) {
                    *p++ = '2';
                    value -= 200;
                }
                else if (value >  99) {
                    *p++ = '1';
                    value -= 100;
                }
                else {
                    *p++ = '0';
                }
            }
        }
        if (value > 49) {
            if (value > 69) {
                if (value > 89) {
                    *p++ = '9';
                    value -= 90;
                }
                else if (value > 79) {
                    *p++ = '8'; value -= 80;
                }
                else {
                    *p++ = '7';
                    value -= 70;
                }
            }
            else {
                if (value > 59) {
                    *p++ = '6';
                    value -= 60;
                }
                else {
                    *p++ = '5';
                    value -= 50;
                }
            }
        }
        else {
            if (value > 19) {
                if (value > 39) {
                    *p++ = '4';
                    value -= 40;
                }
                else if (value > 29) {
                    *p++ = '3';
                    value -= 30;
                }
                else {
                    *p++ = '2';
                    value -= 20;
                }
            }
            else {
                if (value >  9) { *p++ = '1'; value -= 10; }
                else if (p != str)   { *p++ = '0'; }
            }
        }
    *p++ = value + '0';
    *p = 0;
}

---

Dora.

 

[ponnus]

Hai,
Now my program seems to be more faster. Thanks for the help.....

Hai Dora,
Now,I am actually using PIC24 which has a 16 bit architecture. But, I'll be porting the code to dsPIC, which is also of 16 bit architecture. It has a 16 bit hardware multiplier. So, I think it'll take more time, when this code runs on a 16-bit microcontroller. Thanks for the suggestion

 

[doraemon]

Hello!

Actually you can do that kind of fake division if you can do 16 bit x 16 bit integer multiplication
and get the result on 32 bits (or on 2 16-bit) registers.
Of course the 16 x 16 multiplication is not very efficient without a hardware multiplier, but anyway
it's better than doing a division. But be careful: 6554 is a rounded value of 1/10. The error is
2 lsbs on 16 bits, so it works well (error free) until 14 bits only.

Beside this, I have also looked at the double dabble algorithm mentioned above. But it looks
very inefficient. There are 3 nested loops, one up to n, whatever it is, and the other up to 16,
and inside these 2 nested loops, there is a third one called twice.
Without reading further, let's be optimistic: n and nscratch are small, we have a small number
of loops, which should be 2*(nscratch - smin)*16*n
Here are only the loops of the double dabble algorithm:

---

Code C - [expand]
1
2
3
4
for (i=0; i < n; ++i) {
        for (j=0; j < 16; ++j) {
              for (k=smin; k < nscratch; ++k)
              for (k=smin; k < nscratch-1; ++k) {

---

This is a lot. Even if n = 2, nscratch - smin = 2, we would have 128 loops. On my favorite processor,
this would mean 1280 clocks doing nothing worth. And on top of that there is some memory allocation
(malloc and calloc) which makes absolutely no sense for a few bytes. Even less sense on a microcontroller.

BUT: looking at the principle on wikipedia, I think it should be extremely efficient to do it with
some kind of PLD. Or FPGA. I'm not sure whether it can be done in combinatory logic but even
in sequential, it should take just the number of bits to shift. 16 clocks to transform 16 bits, etc...

Dora,