Search code examples
assemblyasciiavrdata-conversion

How to get ascii for each digit from a binary number


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?


Solution

  • 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.