CODEWITHSUNDEEP
assemblyx86-64stdio
apilat
apilat

Reputation: 1510

Assembly - Print arbitrary length integer

I created an assembly program that implements biginteger to calculate big fibonacci numbers. The program works and using gdb I can verify that the numbers are correctly stored in memory.

The problem comes when I want to print the numbers. Normally I would just use printf but AFAIK it doesn't support numbers bigger than 64-bit. This means that I need to implement the conversion myself. I know that I need to calculate remainders mod 10 but I don't know how to do that for numbers so big.

Code

section .text
global _start

_start: mov eax, 192
        xor ebx, ebx
        mov ecx, 2048
        mov edx, 0x6
        mov esi, 0x22
        mov edi, -1
        xor ebp, ebp
        int 0x80 ; allocate memory
        lea r8, [eax] ; a
        lea r9, [eax+1024] ; b
        mov qword [r8], 0x1
        mov qword [r9], 0x1
        mov rbx, 0x2 ; fib num counter
        jmp fib

fib:    inc rbx ; num counter++
        mov rsi, 0x0 ; addr for int
        mov rdx, 128; counter for int
        clc ; clear carry flag
add:    mov rax, [r8+8*rsi]
        adc rax, [r9+8*rsi] ; rax = a + b
        mov rcx, [r8+8*rsi]
        mov [r9+8*rsi], rcx ; b = a
        mov [r8+8*rsi], rax ; a = a + b
        inc rsi
        dec rdx
        jnz add ; repeat for whole bigint
        call print
        cmp rbx, 100 ; repeat for 100 fib nums
        jl fib
        jmp exit

print:  ; what to do here?
        ret    

exit:   mov eax, 0x1
        xor ebx, ebx
        int 0x80

Upvotes: 3

Views: 1224

Answers (1)

Gene
Gene

Reputation: 46960

There's an interesting classical algorithm called double-dabble (easy to find many references) that uses only shift and add to convert binary unsigned integers to binary-coded decimal (BCD). BCD is very simple to print as ASCII decimal.

For arbitrary-length integers double-dabble is not particularly efficient, but it's simple to implement.

Here's C code for multi-word double-dabble. It assumes unsigned ints are 32 bits and works fine on my machine where that's true. One could make it more portable, but I'm not bothering because you intend to translate to assembly anyway.

The multi-word shift and add can be much smaller, simpler, and faster in assembly language because you have direct access to carry bits.

#include <stdio.h>

typedef unsigned int word;

// Print BCD in x of given size.
void print(word *x, int size) {
  for (int i = size - 1; i >= 0; --i)
    for (int j = 28; j >= 0; j -= 4) {
      unsigned d = (x[i] >> j) & 0xf;
      putchar('0' + d);
    }
  putchar('\n');
}

// Shift x of given size in words left one bit
void shift_left(word *x, int size) {
  for (int i = size - 1; i > 0; --i) x[i] = (x[i] << 1) | (x[i - 1] >> 31);
  x[0] <<= 1;
}

// Add small constant c to x of given size in words.
void add(word *x, int size, word c) {
  word x0 = x[0] + c;
  word carry = x0 < x[0];
  x[0] = x0;
  for (int i = 1; carry && i < size; ++i) {
    word xi = x[i] + carry;
    carry = xi < x[i];
    xi = xi;
  } 
}

// Do the double dabble increment.
void double_dable_increment(word *bcd, int size) {
  for (int i = 0; i < size; ++i) {
    for (int j = 28; j >= 0; j -= 4) {
      word digit = (bcd[i] >> j) & 0xfu;
      if (digit >= 5) add(bcd + i, size - i, 3u << j);
    }
  }
}

// Convert binary in the low words of x into BCD in the high words.
void convert(word *x, int bin_size, int bcd_size) {
  for (int i = 0; i < 32 * bin_size; ++i) {
    double_dable_increment(x + bin_size, bcd_size);
    shift_left(x, bin_size + bcd_size);
  }
}

// Warning: Not portable. For simplicity, assumes 32-bit words.
#define BCD_BITS_PER_BINARY_BIT (1.20411998267)
#define WORDS_FROM_BITS(N) (((int)(N) + 31) / 32)
#define BCD_WORDS_FROM_BINARY_WORDS(N) \
  WORDS_FROM_BITS(BCD_BITS_PER_BINARY_BIT * 32 * (N))

// Test problem uses 4 words.
#define SIZE 4
#define BCD_SIZE BCD_WORDS_FROM_BINARY_WORDS(SIZE)

int main(void) {
  // Binary rep of 12345678901234567890123456789
  word x[10] = { 0xae398115, 0xaadfa328u, 0x6015fec5u, 0x5ce0e9a5u, };
  convert(x, SIZE, BCD_SIZE);
  print(x + SIZE, BCD_SIZE);
  return 0;
}

And if we run it,

$ ./a.out
0123456789012345678901234567890123456789

Upvotes: 4

Related Questions