How to get ascii for each digit from a binary number

Question

I am getting an 8 bit binary number and want to represent that as a decimal number on a LCD screen.

So for example if I get 01000011 as input, which is 67 in decimal I first have to get the 8 bit ascii code for 6, then the 8 bit ascii code for 7 and send those to the LCD.

Any idea on how this could be done in AVR Assembler?

Answer 1

This is an algorithm from @Sebastian which computes the quotient after dividing by 10, correctly in the range of [0, 99].

typedef unsigned char byte;

byte div10(byte x) {
    x >>= 1;
    return (byte)((byte)(x * 3) + (x >> 2)) >> 4;
}

The casts to byte is necessary because the C standard requires to promote any intermediate result to an int which is at least 16-bit, and such conversion results to inefficient code for 8-bit processors like AVR.

GCC translates to this.

div10:
        mov r18,r24
        lsr r18
        mov r25,r24
        andi r25,lo8(-2)
        add r25,r18
        lsr r24
        lsr r24
        lsr r24
        add r24,r25
        swap r24
        andi r24,lo8(15)
        ret

You can always calculate the remainder by dividend - quotient * 10.

---

Here is an explanation on how the above method works based on @Sebastian's comments. Read the comments if you'd like a mathematically sophisticated explanation, but this is what I can vaguely grasp with some basic math.

Basically, you can divide a number by multiplying the divisor's inverse. n / 3 = n * 0.33...

To calculate the integer quotient of n / 3, you can use these expressions, derived from 1 / 3 = 0.33...

n * (3 + 1) / 10^1 ; n <= 4
n * (33 + 1) / 10^2 ; n <= 49
n * (333 + 1) / 10^3 ; n <= 499
n * (3333 + 1) / 10^4 ; n <= 4999
...

With a larger multiplier, you get higher precision, so the result will be accurate for a bigger dividend.

Same with binary numbers. You can calculate the integer quotient of n / 5 by these expressions, derived from the binary point expression of 1 / 5 = 0.001100110011..(2).

n * (11(2) + 1) / 2^4 ; n <= 3
n * (110(2) + 1) / 2^5 ; n <= 13
n * (1100(2) + 1) / 2^6 ; n <= 63
n * (11001(2) + 1) / 2^7 ; n <= 63
n * (110011(2) + 1) / 2^8 ; n <= 63
n * (1100110(2) + 1) / 2^9 ; n <= 173
n * (11001100(2) + 1) / 2^10 ; n <= 1023

The required size of the multiplier for a certain precision looks kind of irregular, and I still haven't figured out how it works, but for our purpose, we need to divide a number N in [0, 99] by 10, which is N / 2 / 5. N / 2 <= 49, so n * (1100(2) + 1) / 2^6 which works up to n <= 63 suffices.

We can thus transform N / 10 to N / 2 * 13 >> 6. Let h = N / 2. h * 13 overflows in 8 bits, but since >> 6 will discard some of the lower bits after the multiplication, it's okay to do some shifts beforehand.

h * 13 >> 6
= h * 12 + h >> 6
= h * 6 + (h >> 1) >> 5
= h * 3 + (h >> 2) >> 4

Since h <= 49, h * 3 + (h >> 2) fits in 8 bits, and this is represented in the C code that we've seen before.

byte div10(byte x) {
    x >>= 1;
    return (byte)((byte)(x * 3) + (x >> 2)) >> 4;
}

GCC thinks a different way of calculation is better. The assembly output of GCC can be rewritten in C as follows.

byte div10(byte x) {
    return (byte)((x & 0b11111110) + (x >> 1) + (x >> 3)) >> 4;
}

/*
div10:
        mov r18,r24
        lsr r18
        mov r25,r24
        andi r25,lo8(-2)
        add r25,r18
        lsr r24
        lsr r24
        lsr r24
        add r24,r25
        swap r24
        andi r24,lo8(15)
        ret
*/

---

old answer

If you are looking for an algorithm to calculate the quotient and remainder when an 8-bit number is divided by 10, in AVR assembler, this code does the trick.

But don't ask me how it works. It is the optimized output of AVR GCC translating a C function that I wrote by reverse-engineering the optimized output of x86 Clang. So I basically stole the work of two compilers.

From this C code.

#include <stdint.h>

typedef uint8_t byte;

typedef struct {
    byte _0;
    byte _1;
} bytepair;

bytepair divmod10(byte x) {
    return (bytepair){x / 10, x % 10};
}

x86 Clang produced this.

imul    ecx, edi, 205
shr     ecx, 11
lea     eax, [rcx + rcx]
lea     eax, [rax + 4*rax]
sub     dil, al
movzx   eax, dil
shl     eax, 8
or      eax, ecx
ret

which I translated to C.

bytepair divmod10(byte x) {
    byte y = (uint16_t)x * 205 >> 11;
    return (bytepair){y, x - y * 10};
}

which then I put into AVR GCC.

mov r20,r24
ldi r25,0
mov r19,r25
mov r18,r24
lsl r18
rol r19
lsl r18
rol r19
add r18,r24
adc r19,r25
lsl r18
rol r19
lsl r18
rol r19
lsl r18
rol r19
add r18,r24
adc r19,r25
mov r25,r19
mov r24,r18
lsl r24
rol r25
lsl r24
rol r25
add r18,r24
adc r19,r25
mov r24,r19
lsr r24
lsr r24
lsr r24
mov r25,r24
swap r25
lsl r25
andi r25,lo8(-32)
sub r25,r24
lsl r25
lsl r25
sub r25,r24
lsl r25
add r25,r20
ret

It seems AVR is a very simple 8-bit machine without even variable shifts. Well, still it will do the job probably faster than GCC's software division built-in.

---

• AVR GCC output
• test