程序集 - 打印任意长度的整数

Question

我创建了一个汇编程序，它实现了 biginteger 来计算大的斐波那契数。该程序有效并使用 gdb 我可以验证这些数字是否正确存储在内存中。

当我要打印数字时，问题就来了。通常我只会使用 printf 但 AFAIK 它不支持大于 64 位的数字。这意味着我需要自己实现转换。我知道我需要计算余数 mod 10 但我不知道如何计算如此大的数字。

代码

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

Answer 1

有一个有趣的经典算法，称为 double-dabble（很容易找到很多参考资料），它仅使用移位和加法将二进制无符号整数转换为 binary-coded 十进制 (BCD)。 BCD 很容易打印为 ASCII 十进制。

对于arbitrary-length整数double-dabble不是特别有效，但实现起来很简单。

这是 multi-word double-dabble 的 C 代码。它假定 unsigned ints 是 32 位并且在我的机器上工作正常，这是真的。可以使它更便携，但我不介意，因为您无论如何都打算转换为汇编语言。

multi-word 移位和加法在汇编语言中可以更小、更简单、更快，因为您可以直接访问进位位。

#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;
}

如果我们运行它，

$ ./a.out
0123456789012345678901234567890123456789

程序集 - 打印任意长度的整数

Assembly - Print arbitrary length integer

assembly

x86-64

stdio