增量表示为字符串的二进制数字

Question

我在集会方面是个业余爱好者，但我正在努力使它变得更好。为了好玩，我决定编写包含char数组的代码，并增加二进制表示的数字。

以下是几个输入输出示例：

inc("10001010") = "10001011"
inc("0") = "1"
inc("1") = "10"
inc("100") = "101"

代码：

section .bss
    result: resb 1024

section .text
_strlen:
    ; rdi -> string
    ; rax -> output

    ; i -> rax

    xor rax, rax ; i = 0

    ; first of all, the string being
    ; empty turns out to be an edge
    ; case. we handle it here
    cmp byte[rdi], 0x0
    je _strlen_ret

    _strlen_loop:
        inc rax
        cmp byte[rdi + rax], 0x0
        jnz _strlen_loop

    _strlen_ret:
        ret

global _asm_inc
_asm_inc:
    ; carryFlag -> bl
    ; i = r11

    mov bl, 1 ; carryFlag = true
    call _strlen ; call _strlen on the input
    mov r11, rax ; move the length into r11
    mov r12, r11 ; make a copy of the length
    _asm_inc_for_1:
        dec r11 ; i--
        cmp bl, 1
        jnz _no_carry_flag
        ; if carryFlag
            cmp byte[rdi + r11], 48
            jne _current_char_1
            ; if s[i] == '0'
                mov byte[rdi + r11], 49
                xor bl, bl
                jmp _after_current_char_1
            _current_char_1:
            ; else
                mov byte[rdi + r11], 48
            _after_current_char_1:
        _no_carry_flag:
        cmp r11, 0
        jg _asm_inc_for_1
    mov rax, rdi ; return value = input string
                 ; well, after these modifications

    cmp bl, 1
    jnz _asm_inc_ret
    ; if carryFlag
    mov byte[result], 49
    _asm_inc_exceptional_case_loop:
        mov bl, byte[rdi + r11]
        mov byte[result + r11 + 1], bl
        inc r11
        cmp r11, r12
        jnz _asm_inc_exceptional_case_loop
    mov byte[result + r11 + 1], 0x0
    mov rax, result

    _asm_inc_ret:
        ret

这段代码工作得很好，但我相信它还可以改进。你有什么建议吗？

Answer 1

字符串为空确实是一个边缘情况，但您可以以更简单的方式处理。不要将您的RAX索引初始化为0，而是将其以-1作为素数，并让循环中发生的第一个增量将其提高到0。那样的话，你就会刮掉两条指令：

  mov  rax, -1
_strlen_loop:
  inc  rax
  cmp  byte [rdi + rax], 0
  jne  _strlen_loop
  ret

您的字符串不会长到需要64位长度。因此，我们可以安全地使用较短的inc eax指令以及自动零扩展到完整RAX寄存器的较短的mov eax, -1。

  mov  eax, -1
_strlen_loop:
  inc  eax
  cmp  byte [rdi + rax], 0
  jne  _strlen_loop
  ret

如果长度应该是0，那么根本不应该运行后面的递增循环！

cmp bl，1 jnz _no_carry_flag

您的BL‘进位标志’仅限于值0和1。而不是3字节cmp bl, 1指令，您可以在“零”条件下使用2字节test bl, bl指令和分支：

test bl, bl
jz   _no_carry_flag

cmp r11，0 jg _asm_inc_for_1

R11寄存器包含一个长度，这将被认为是一个无符号的数量，所以最好使用无符号条件跳转指令。此外，对零的测试最好通过test <reg>, <reg>指令进行，而且由于长度肯定比32位小得多，所以我们可以使用R11D：

test r11d, r11d
jnz  _asm_inc_for_1

实际上将1添加到二进制数中的代码跳得太多了，跳转速度是昂贵的！

考虑一下当您必须将1添加到二进制字符时会发生什么。

For "0" (00110000b), BL becomes 0 and the digit becomes "1"
For "1" (00110001b), BL stays 1 and the digit becomes "0"

新的BL与要修改(i)的数字的ASCII代码的最低位完全相同，二进制字符只需切换即可使用单个xor byte [rdi + r11], 1指令(ii)。

_asm_inc_for_1:
    dec  r11d
    test bl, bl
    jz   _no_carry_flag

    mov  al, [rdi + r11]
    mov  bl, al
    and  bl, 1
    xor  al, 1
    mov  [rdi + r11], al

_no_carry_flag:
    test r11d, r11d
    jnz  _asm_inc_for_1

然后对杀手循环进行优化。一旦BL变为0，您就可以停止循环，因为左边的数字将不再被更改，而这些数字仍然保留在数字中。

当增量循环没有生成最终进位时，您将结果留在原来存储的位置，但当最终进位存在时，则将结果复制到另一个缓冲区(因为需要额外的空间)。一种更简单的方法是在字符串开始时始终保持一个额外的字节空闲。然后添加新的"1“变得非常容易..。

下一个片段实现了上面的大部分内容。我也更喜欢使用ECX寄存器而不是R11D寄存器，因为这样可以从编码中去除额外的REX前缀。

    call _strlen            ; -> RAX
    mov  ecx, eax
    dec  ecx
    js   _DONE              ; (iii) if taken then empty string

    mov  bl, 1              ; carry flag = true
_LOOP1:
    mov  al, [rdi + rcx]
    mov  bl, al             ; future carry flag
    xor  al, 1              ; new digit
    mov  [rdi + rcx], al
    and  bl, 1              ; new carry flag [0,1]
    jz   _DONE              ; (iii) if taken then carry clear
    dec  ecx
    jns  _LOOP1             ; (iii) if taken then more digits

    dec  rdi
    mov  byte [rdi], "1"    ; filling the kept-free-byte

_DONE:
    mov  rax, rdi           ; return value = new string
    ret

新的BL与要修改(i)的数字的ASCII代码的最低位相同，

该代码将AL中的当前字符复制到BL寄存器中，然后执行具有掩码值1的按位and。除最低位外，每一位都将为零：

AL   00110000  ASCII code for "0"     00110001  ASCII code for "1"
BL   00110000  ASCII code for "0"     00110001  ASCII code for "1"
     00000001  The AND mask           00000001  The AND mask
     --------                         --------
BL   00000000  New 'carry flag'       00000001  New 'carry flag'

和二进制字符只需切换一条xor byte [rdi + r11], 1指令(ii).

即可。

该代码在AL寄存器中具有当前字符，然后执行具有掩码值1的按位xor。这将使除切换状态的最低位之外的每一位保持不变：

AL   00110000  ASCII code for "0"     00110001  ASCII code for "1"
     00000001  The XOR mask           00000001  The XOR mask
     --------                         --------
AL   00110001  ASCII code for "1"     00110000  ASCII code for "0"

--通常我们在决定一个条件分支(iii)

之前不需要cmp

许多指令根据它们的操作结果定义标志。

在dec ecx js _DONE中，dec指令定义OF、SF、ZF、AF和PF。(它不接触CF)。接下来的js是基于定义好的SF的。

在这里，如果ECX变成-1 (与SF=1相同)，则完全绕过循环，因为这意味着二进制字符串的长度为0。

在and bl, 1 jz _DONE中，and指令定义SF、ZF和PF。(它还重置OF和CF。对AF的影响尚不明确)。接下来的jz是基于定义好的ZF的。

在这里，我们在BL=0 (与ZF=1一样)一开始就离开循环。

在dec ecx jns _LOOP1中，dec指令定义OF、SF、ZF、AF和PF。(它不接触CF)。接下来的jns是基于定义好的SF的。

这里，当ECX变为-1 (与SF=1相同)时，循环就停止迭代，因为这表明我们刚刚处理完二进制字符串的最左边的数字。

dec rdi不能“越界”，因为前提是在数字的最左边保留一个额外的字节。

没有任何风险，写特别的"1“每一次。只有在循环必须遍历二进制字符串的所有数字时，它才会被添加。当从查找BL=0开始时，代码的这一部分就被绕过了( _DONE:标签位于源代码中它的下方)。

ps。我把这个写在答案里，因为我现在使用的电脑上，我不能发表评论。