使用链表的无限精度 NASM 计算器

Question

作为我的项目的一部分，它是一个无限精度的 RPN 计算器，我正在尝试编写一种方法来接收大小最多为 80 字节的缓冲区。因为我想支持无限精度（或者至少只受堆大小限制），所以我想接受那个缓冲区并创建一个指向 linked 列表头部的指针，该列表将代表数字，所以例如，如果缓冲区内的输入是：0x7D12AF

然后由该输入生成的 linked 列表将类似于：

[AF, addr1] -addr1->[12, addr2] -addr2-> [7D, addr3] -addr3-> 0

其中每个 link 是 5 个字节，4 个用于指向下一个 link 的指针，一个字节用于数据。这是我的尝试，我会接受任何建议，因为我真的不确定自己在做什么：（假设 atoi 接受一个十六进制数字并将其转换为数值）

`section .bss
        ptr: resb 5
 section .data

setcion .text
align 16
extern malloc

_buffersize
    push ebp
    mov ebp, esp
    mov ecx, [ebp+8]


_buffersize:
    push ebp
    mov ebp, esp
    push ecx
    mov ecx, [ebp+8]
    xor eax, eax

    .loop:
        cmp [ecx], 20h
        jle .done
        inc ecx
        inc eax
        jmp .loop

    .done:
        pop ecx
        mov esp, ebp
        pop ebp
        ret

_listify:
    push ebp
    mov ebp, esp

    mov edx, [ebp+8]                ; pointer to the first byte in the number_string
    pushad

    push edx                        ; push function argument
    call _buffersize                ; eax now holds the size of the buffer 
    add esp, 4                      ; clean up stack after call


    mov ecx, eax                    ; count for the loop

    .loop:
        pushad                      ; allocate 5 bytes for a node : 4 for a next ptr, 1 for data
        push 5
        call malloc                 ; eax now points to the 5 bytes allocated
        add esp, 4                  ; clean up stack after call to malloc
        mov [ptr], eax              ; now ptr points to the address in memory of the 5 allocated bytes 
        popad
        push [edx]                  ; push the first byte pointed to by edx as an argument for atoi (atoi converts a signle HEX digit to it's numeric value)
        call _atoi
        add esp, 4                  ; eax now holds the numeric value of that 1 byte character
        mov ebx, [ptr]              ; ebx points to the allocated memory
        mov [ebx], dword 0          ; the address of the next link is NULL as we're insterting at the head of the lsit
        mov [ebx], byte eax         ; hopefully, ebx should now points to 5 bytes in memory of the form [b4b3b2b1b0] where b4b3b2b1 is the address of the next link & b0 is a 0 <= number <16
        mov [ptr], ebx              ; now ptr points to the address of the newly updated linked list representing the number
        inc edx                     ; get ready to read next byte
       loop .loop  

    popad
    mov esp, ebp
    pop ebp
    ret
`

我的另一个问题是：有没有办法以十六进制表示形式存储数字？我认为这是一个愚蠢的问题，因为表示只是我如何看待它但值是相同的..所以将十六进制数字 ASCII 表示转换为 int 是一样的，并且要制作十六进制我应该只对待它当从 char 转换为 int 时那样，反之亦然。如果我错了，请纠正我。谢谢！

Answer 1

4 for the pointer to the next link, and one byte for the data

因此您建议的格式仅使用 space 的 20% 用于实际数据。实际上比这少得多，因为 malloc 有内部开销，并且每个分配将至少对齐 8 个字节，也许是 16 个字节。所以你至少浪费了 7/8 或 15/16 的内存/缓存占用空间，如果包括 malloc 开销，则更多。

请参阅 this 了解更多关于为什么它很糟糕以及你应该做什么，以及添加每个节点 1 个十六进制数字（4 位）而不是你建议的 8 位的链接列表的实现（ 2 个十六进制数字）。

使用数组，如果需要增大它，请使用realloc。这使您可以添加 32 位或 64 位块（在 64 位模式下）。如果你愿意，通过像 C++ std::vector 那样分配额外的 space 来保存 realloc 调用，分别跟踪分配和使用中的 space。

数组更容易循环，效率更高。

Is there a way to store number in its hex representation? I think it's kind of a stupid question because the representation is just how I look at it but the value is the same

ASCII 十六进制是数字的序列化格式；它每 8 位（2 个半字节）数据使用两个 ASCII 字节。请参阅了解如何将二进制整数 转换为 十六进制字符串。

反过来，将从十六进制转换为寄存器中的二进制整数，您可以将数字转换为 total = (total<<4) | digit。其中 digit 是 0..15 范围内的整数。给定一个 ASCII 字符，您可以减去 '0' 并根据结果 > 9 进行分支，如果是，则减去 'A'。

对于任意长度的十六进制输入，您可以从缓冲区的末尾开始并将 2 个十六进制数字转换为一个字节，将其存储在缓冲区中并递减指针。

（如果输入最终是奇数个十六进制数字，这是一个问题，因为您希望数字的开头与字节边界对齐。因此，如果您知道十六进制字符串的长度，用它来决定是否从第一个数字本身转换开始。或者如果你有一个指向末尾的指针，你可以向后读取数字。

首选显式长度字符串/缓冲区来处理 ASCII 数字，这样您就知道首先有多少数字，而不必循环查找 0 字节作为 C 的终止符隐式长度字符串。)

使用链表的无限精度 NASM 计算器

unlimited precision NASM calculator using linked lists

x86

assembly

rpn

nasm

bigint