2
\$\begingroup\$

I'm an amateur at assembly, but am trying to get better at it. For fun, I decided to write code that takes in a char array and increments the number represented in binary.

Here are a few input-output examples:

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

Code:

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

This code works perfectly, but I'm sure it could be improved. Have you got any suggestions?

\$\endgroup\$
4
  • \$\begingroup\$ You should add an appropriate architecture tag. \$\endgroup\$ Aug 23, 2022 at 16:44
  • \$\begingroup\$ How do I do that? \$\endgroup\$
    – avighnac
    Aug 23, 2022 at 17:29
  • \$\begingroup\$ Tell us the architecture and we'll edit it in, if you are having trouble locating the edit feature yourself. \$\endgroup\$
    – Mast
    Aug 23, 2022 at 18:39
  • \$\begingroup\$ Assembly for Linux, Intel-like syntax. \$\endgroup\$
    – avighnac
    Aug 24, 2022 at 0:59

1 Answer 1

1
\$\begingroup\$

The string being empty is indeed an edge case, but one that you can deal with in a simpler fashion. Instead of initializing your RAX index at 0, prime it with -1 and let the very first increment that happens in the loop already raise it to 0. That way, you'll have shaved off two instructions:

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

Your string will never be that long that it would require a 64-bit length. Therefore we can safely use the shorter inc eax instruction as well as the shorter mov eax, -1 that automatically zero extends into the full RAX register.

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

If the length should turn out to be 0, then you should not run the incrementation loop that follows at all!


cmp bl, 1
jnz _no_carry_flag

Your BL 'carry flag' is limited to the values 0 and 1. Instead of the 3-byte cmp bl, 1 instruction, you could use the 2-byte test bl, bl instruction and branch on the 'zero' condition:

test bl, bl
jz   _no_carry_flag
cmp r11, 0
jg _asm_inc_for_1

The R11 register contains a length and that is to be considered an unsigned quantity, so better use the unsigned conditional jump instructions. Also, testing for zero is better done via the test <reg>, <reg> instruction and because the length is surely very much smaller than 32-bit, we can use R11D:

test r11d, r11d
jnz  _asm_inc_for_1

The code that actually adds 1 to the binary number jumps around too much, and jumping is expensive speed-wise!
Consider what happens when you have to add 1 to a binary character.

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

The new BL is identical to the lowest bit of the ASCII code for the digit that is to be modified (i) , and the binary character just has to toggle which you can do with a single xor byte [rdi + r11], 1 instruction (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

And then for the killer loop optimization. As soon as BL becomes 0, you can stop the loop because no more changes will be made to the digits on the left that remain in the number.

When the incrementation loop did not produce a final carry, you leave the result where is was stored originally, but when a final carry does exist, you copy the result to another buffer (because you need the extra space). An easier approach would be to always keep one extra byte free at the start of the string. Then adding the new "1" becomes real easy...

Next snippet implements most of the above. I also prefer to use the ECX register instead of the R11D register because that shaves off an additional REX prefix from the encoding.

    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


The new BL is identical to the lowest bit of the ASCII code for the digit that is to be modified (i),

The code copies the current character in AL to the BL register and then performs a bitwise and with the mask value 1. This will zero every bit except the lowest bit:

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'

and the binary character just has to toggle which you can do with a single xor byte [rdi + r11], 1 instruction (ii).

The code has the current character in the AL register and then performs a bitwise xor with the mask value 1. This will keep every bit unmodified except the lowest bit that toggles state:

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"

Very often we don't need to cmp before deciding about a conditional branch (iii)

Many instructions define flags according to the result of their operation.

In dec ecx js _DONE, the dec instruction defines the OF, SF, ZF, AF, and PF. (It doesn't touch the CF). The js that immediately follows is based on the SF that got defined alright.
Here the loop gets completely bypassed if ECX became -1 (same as SF=1), because that would have meant that the binary string had a length of 0.

In and bl, 1 jz _DONE, the and instruction defines the SF, ZF, and PF. (It also resets the OF and CF. The effect on AF is undefined). The jz that immediately follows is based on the ZF that got defined alright.
Here we leave the loop early as soon as BL=0 (same as ZF=1).

In dec ecx jns _LOOP1, the dec instruction defines the OF, SF, ZF, AF, and PF. (It doesn't touch the CF). The jns that immediately follows is based on the SF that got defined alright.
Here the loop stops iterating as soon as ECX becomes -1 (same as SF=1), because that signals that we have just finished processing the leftmost digit of the binary string.



The dec rdi can't go 'out of bounds' since the premise was that you kept an extra byte at the ready at the far left of the number.

There's no risk of writing the special "1" every single time. It only gets added in case the loop has to iterate over all of the digits of the binary string. When the early out from finding BL=0 is taken, that part of the code gets bypassed (the label _DONE: sits below it in the source).

ps. I write this in the answer because on the computer that I'm using right now, I can't post comments.

\$\endgroup\$
3
  • \$\begingroup\$ Firstly, thank you. Secondly, one thing I don't understand here is how xorring a character ('0' or '1') can toggle it. Sure, xor 0, 1 = 1, and xor 1, 1 = 0, but how can you xor 48, 1 and xor 49, 1 and expect it to switch the values? Same question with the and instruction. \$\endgroup\$
    – avighnac
    Aug 25, 2022 at 7:49
  • \$\begingroup\$ Also, I didn't get the last part either (the way to add an extra byte). How do you call js without using a cmp? \$\endgroup\$
    – avighnac
    Aug 25, 2022 at 7:56
  • \$\begingroup\$ One more question, how is it safe to decrement rdi (would go out of bounds, right)? And there's no condition for that last part: wouldn't that add a '1' every single time? \$\endgroup\$
    – avighnac
    Aug 25, 2022 at 13:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.