# Increment a binary number represented as a string

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?

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

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"
--------                         --------
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"
--------                         --------
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.

• 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. Commented Aug 25, 2022 at 7:49
• 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? Commented Aug 25, 2022 at 7:56
• 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? Commented Aug 25, 2022 at 13:24