Assembly course · Lesson 4

Loops and counting

At the end you can build loops that test at the top and at the bottom, add up a sum with a counter and put two loops inside each other. Prerequisite: lesson 3.

Architecture:

The video for this lesson is coming.

The idea: two forms

In lesson 3 you saw that a conditional jump backwards makes a loop. Depending on where the condition is tested there are two basic forms:

Form	Test	The body runs	Known from high-level languages as
Test at the top	before each pass	zero or more times	`while (i <= 10) { … }`
Test at the bottom	after each pass	at least once	`do { … } while (i != 0)`

A counting loop (for) is a special case: a register counts the passes, and the body calculates with it.

Test at the top: the sum of 1 to 10

The program adds 1 + 2 + … + 10. The register for i counts up from 1, a second one collects the sum.

; Lesson 4: a loop that tests at the top (like "while"). Adds 1 + 2 + ... + 10.

.format pe console
.arch i386
.import msvcrt.dll printf

.code
start:
  mov ecx, 1              ; i = 1
  xor edx, edx            ; sum = 0
top:
  cmp ecx, 10
  jg done                 ; i > 10: leave the loop
  add edx, ecx            ; sum = sum + i
  inc ecx                 ; i = i + 1
  jmp top                 ; and test again
done:
  push edx                ; the sum is the argument for %d
  push dword fmt
  call [printf]
  add esp, 8
  xor eax, eax
  ret

.data
fmt db 'The sum of 1 to 10 is %d', 10, 0

; Lesson 4: a loop that tests at the top (like "while"). Adds 1 + 2 + ... + 10.

.format pe console
.arch x64
.import msvcrt.dll printf

.code
start:
  sub rsp, 40
  mov ecx, 1              ; i = 1
  xor edx, edx            ; sum = 0 (edx is also the second argument of printf)
top:
  cmp ecx, 10
  jg done                 ; i > 10: leave the loop
  add edx, ecx            ; sum = sum + i
  inc ecx                 ; i = i + 1
  jmp top                 ; and test again
done:
  lea rcx, [fmt]          ; the format is the first argument, the sum is already in edx
  call [printf]
  xor eax, eax
  add rsp, 40
  ret

.data
fmt db 'The sum of 1 to 10 is %d', 10, 0

; Lesson 4: a loop that tests at the top (like "while"). Adds 1 + 2 + ... + 10.

.format pe console
.arch thumb
.import msvcrt.dll printf

.code
start:
  push {r4, lr}
  movs r1, #1             ; i = 1
  movs r2, #0             ; sum = 0
top:
  cmp r1, #10
  bgt done                ; i > 10: leave the loop
  adds r2, r2, r1         ; sum = sum + i
  adds r1, r1, #1         ; i = i + 1
  b top                   ; and test again
done:
  mov r1, r2              ; the sum is the argument for %d
  adr r0, fmt
  ldr r3, printf
  blx r3
  movs r0, #0
  pop {r4, pc}

.data
align 4
fmt db 'The sum of 1 to 10 is %d', 10, 0

; Lesson 4: a loop that tests at the top (like "while"). Adds 1 + 2 + ... + 10.

.format pe console
.arch arm64
.import msvcrt.dll printf

.code
start:
  stp x29, x30, [sp, #-16]!
  mov w1, #1              ; i = 1
  mov w2, #0              ; sum = 0
top:
  cmp w1, #10
  b.gt done               ; i > 10: leave the loop
  add w2, w2, w1          ; sum = sum + i
  add w1, w1, #1          ; i = i + 1
  b top                   ; and test again
done:
  mov w1, w2              ; the sum is the argument for %d
  adrp x0, fmt
  add x0, x0, :lo12:fmt
  adrp x16, printf
  ldr x16, [x16, :lo12:printf]
  blr x16
  mov x0, #0
  ldp x29, x30, [sp], #16
  ret

.data
fmt db 'The sum of 1 to 10 is %d', 10, 0

The test is at the label top: cmp ecx, 10 and jg done leave the loop as soon as i is greater than 10.cmp r1, #10 and bgt done leave the loop as soon as i is greater than 10.cmp w1, #10 and b.gt done leave the loop as soon as i is greater than 10. If i is too large from the start, the body does not run at all.
The body adds i to the sum and increases i by 1. An unconditional jump (jmp top)(b top) goes back to the test.
ecx is i, edx the sum. Any function may change both; that is no problem here because the loop calls no function. Only afterwards comes printf, and the sum is put on the stack as its argument.
ecx is i, edx the sum. Any function may change both; that is no problem here because the loop calls no function. After the loop the sum is already in edx, the second argument of printf; only the format still has to go into rcx.
r1 is i, r2 the sum. Any function may change both; that is no problem here because the loop calls no function. After the loop mov r1, r2 copies the sum into the second argument of printf.
w1 is i, w2 the sum. Any function may change both; that is no problem here because the loop calls no function. After the loop mov w1, w2 copies the sum into the second argument of printf.

Test at the bottom: shorter

With the test at the bottom the body always runs at least once, and the unconditional jump is not needed: the conditional jump at the end goes back by itself. That saves one instruction per pass. For the sum it is best to count down from 10 to 1, because then no comparison is needed: decsubs sets the zero flag itself, as in lesson 3.

Asmonite lets you write this more readably: do marks the start of the loop, while not zero at the end jumps back as long as the result of the instruction before it was not 0. The assembler turns it into exactly the jump jnz (bne or b.ne on ARM). More on the page if, else, do … while.

; Lesson 4: the same sum with the do ... while of Asmonite (i386). It counts down from 10 to 1.
; "do" is a label, "while not zero" is the jnz back to it (it uses the flags of the dec in front of it).

.format pe console
.arch i386
.import msvcrt.dll printf

.code
start:
  mov ecx, 10             ; i = 10
  xor edx, edx            ; sum = 0
  do
    add edx, ecx          ; sum = sum + i
    dec ecx               ; i = i - 1
  while not zero          ; as long as i is not 0
  push edx
  push dword fmt
  call [printf]
  add esp, 8
  xor eax, eax
  ret

.data
fmt db 'The sum of 1 to 10 is %d', 10, 0

; Lesson 4: the same sum with the do ... while of Asmonite (x64). It counts down from 10 to 1.
; "do" is a label, "while not zero" is the jnz back to it (it uses the flags of the dec in front of it).

.format pe console
.arch x64
.import msvcrt.dll printf

.code
start:
  sub rsp, 40
  mov ecx, 10             ; i = 10
  xor edx, edx            ; sum = 0
  do
    add edx, ecx          ; sum = sum + i
    dec ecx               ; i = i - 1
  while not zero          ; as long as i is not 0
  lea rcx, [fmt]          ; the format is the first argument, the sum is already in edx
  call [printf]
  xor eax, eax
  add rsp, 40
  ret

.data
fmt db 'The sum of 1 to 10 is %d', 10, 0

; Lesson 4: the same sum with the do ... while of Asmonite (ARM 32, Thumb-2). It counts down from 10 to 1.
; "do" is a label, "while not zero" is the bne back to it (it uses the flags of the subs in front of it).

.format pe console
.arch thumb
.import msvcrt.dll printf

.code
start:
  push {r4, lr}
  movs r1, #10            ; i = 10
  movs r2, #0             ; sum = 0
  do
    adds r2, r2, r1       ; sum = sum + i
    subs r1, r1, #1       ; i = i - 1
  while not zero          ; as long as i is not 0
  mov r1, r2              ; the sum is the argument for %d
  adr r0, fmt
  ldr r3, printf
  blx r3
  movs r0, #0
  pop {r4, pc}

.data
align 4
fmt db 'The sum of 1 to 10 is %d', 10, 0

; Lesson 4: the same sum with the do ... while of Asmonite (ARM 64). It counts down from 10 to 1.
; "do" is a label, "while not zero" is the b.ne back to it (it uses the flags of the subs in front of it).

.format pe console
.arch arm64
.import msvcrt.dll printf

.code
start:
  stp x29, x30, [sp, #-16]!
  mov w1, #10             ; i = 10
  mov w2, #0              ; sum = 0
  do
    add w2, w2, w1        ; sum = sum + i
    subs w1, w1, #1       ; i = i - 1
  while not zero          ; as long as i is not 0
  mov w1, w2              ; the sum is the argument for %d
  adrp x0, fmt
  add x0, x0, :lo12:fmt
  adrp x16, printf
  ldr x16, [x16, :lo12:printf]
  blr x16
  mov x0, #0
  ldp x29, x30, [sp], #16
  ret

.data
fmt db 'The sum of 1 to 10 is %d', 10, 0

The Intel processors also have an instruction of their own for this: loop target counts ecx down by 1 and jumps as long as it is not 0. Compilers rarely use it (dec and jnz are faster on modern processors), but you will meet it in old code.

A loop inside a loop

The body of a loop may itself contain a loop. The program prints the small multiplication table from 1 to 3: the outer loop runs over the rows, the inner one over the columns.

; Lesson 4: a loop inside a loop. Prints the 3 x 3 multiplication table.

.format pe console
.arch i386
.import msvcrt.dll printf

.code
start:
  push ebx                ; ebx and esi must come back unchanged: we save them
  push esi
  mov ebx, 1              ; row = 1
row:
  mov esi, 1              ; column = 1
col:
  mov eax, ebx
  imul eax, esi           ; row * column
  push eax
  push dword f_cell
  call [printf]
  add esp, 8
  inc esi                 ; next column
  cmp esi, 3
  jle col                 ; column <= 3: next cell
  push dword f_nl         ; end of the row: a line break
  call [printf]
  add esp, 4
  inc ebx                 ; next row
  cmp ebx, 3
  jle row                 ; row <= 3: next row
  pop esi
  pop ebx
  xor eax, eax
  ret

.data
f_cell db '%3d', 0
f_nl   db 10, 0

; Lesson 4: a loop inside a loop. Prints the 3 x 3 multiplication table.

.format pe console
.arch x64
.import msvcrt.dll printf

.code
start:
  push rbx                ; rbx and rsi must come back unchanged: we save them
  push rsi
  sub rsp, 40
  mov ebx, 1              ; row = 1
row:
  mov esi, 1              ; column = 1
col:
  mov edx, ebx
  imul edx, esi           ; row * column: the second argument
  lea rcx, [f_cell]
  call [printf]
  inc esi                 ; next column
  cmp esi, 3
  jle col                 ; column <= 3: next cell
  lea rcx, [f_nl]         ; end of the row: a line break
  call [printf]
  inc ebx                 ; next row
  cmp ebx, 3
  jle row                 ; row <= 3: next row
  xor eax, eax
  add rsp, 40
  pop rsi
  pop rbx
  ret

.data
f_cell db '%3d', 0
f_nl   db 10, 0

; Lesson 4: a loop inside a loop. Prints the 3 x 3 multiplication table.

.format pe console
.arch thumb
.import msvcrt.dll printf

.code
start:
  push {r4, r5, r6, lr}   ; r4 to r6 must come back unchanged: we save them
  ldr r6, printf
  movs r4, #1             ; row = 1
row:
  movs r5, #1             ; column = 1
col:
  mul r1, r4, r5          ; row * column: the argument for %3d
  adr r0, f_cell
  blx r6
  adds r5, r5, #1         ; next column
  cmp r5, #3
  ble col                 ; column <= 3: next cell
  adr r0, f_nl            ; end of the row: a line break
  blx r6
  adds r4, r4, #1         ; next row
  cmp r4, #3
  ble row                 ; row <= 3: next row
  movs r0, #0
  pop {r4, r5, r6, pc}

.data
align 4
f_cell db '%3d', 0
align 4
f_nl   db 10, 0

; Lesson 4: a loop inside a loop. Prints the 3 x 3 multiplication table.

.format pe console
.arch arm64
.import msvcrt.dll printf

.code
start:
  stp x29, x30, [sp, #-48]!
  stp x19, x20, [sp, #16]       ; x19 to x21 must come back unchanged: we save them
  str x21, [sp, #32]
  adrp x21, printf
  ldr x21, [x21, :lo12:printf]
  mov w19, #1                   ; row = 1
row:
  mov w20, #1                   ; column = 1
col:
  mul w1, w19, w20              ; row * column: the argument for %3d
  adrp x0, f_cell
  add x0, x0, :lo12:f_cell
  blr x21
  add w20, w20, #1              ; next column
  cmp w20, #3
  b.le col                      ; column <= 3: next cell
  adrp x0, f_nl                 ; end of the row: a line break
  add x0, x0, :lo12:f_nl
  blr x21
  add w19, w19, #1              ; next row
  cmp w19, #3
  b.le row                      ; row <= 3: next row
  mov x0, #0
  ldp x19, x20, [sp, #16]
  ldr x21, [sp, #32]
  ldp x29, x30, [sp], #48
  ret

.data
f_cell db '%3d', 0
f_nl   db 10, 0

Each loop has its own counter: ebx for the row, esi for the columnebx for the row, esi for the columnr4 for the row, r5 for the columnw19 for the row, w20 for the column. The inner counter is set to 1 again for every row (the label col is behind this assignment, so the inner loop does not jump back to it).
The printf call is inside the inner loop and must not destroy the counters. That is why they live in registers that a function must return unchanged (ebx, esi) (r4 to r11) (x19 to x28). For that the program saves them on the stack at the start and gets them back at the end – you saw that for lr in lesson 2.
imul eax, esi multiplies; the result replaces the first operand.
mul r1, r4, r5 multiplies two registers and writes the result into a third.
The format %3d writes the number at least 3 places wide, padded with spaces, so that the columns line up. At the end of each row a second printf call writes a line break.

Try it in Asmonite

Open the sum program, assemble with Ctrl+F9 and set a breakpoint with F5 on the comparison cmp at the label top. Start with F9.
With every F9 the program stops at the cmp again. Watch the two registers: ecx counts 1, 2, 3 … and edx grows 0, 1, 3, 6, 10, 15 …r1 counts 1, 2, 3 … and r2 grows 0, 1, 3, 6, 10, 15 …w1 counts 1, 2, 3 … and w2 grows 0, 1, 3, 6, 10, 15 …
To avoid pressing ten times: put the text cursor on the line with the label done and press F4 (Run to Cursor). The program runs through the whole loop and stops behind it. The sum is now in the register.
Experiment: start again, stop at the first cmp and change the register for i by double-clicking its value (ecx)(r1)(x1) to 11. With F8 the program leaves the loop at once: the body does not run, the sum stays 0. That is the peculiarity of the test at the top.

What you see

The sum of 1 to 10 is 55

  1  2  3
  2  4  6
  3  6  9

The sum 55 matches the formula n·(n+1)/2 = 10·11/2.

Exercises

1. Up to 100

Change the sum program so that it calculates 1 + 2 + … + 100. What comes out? Check it with the formula n·(n+1)/2.

Solution

Change the limit in the comparison from 10 to 100 (and, so that the text is right, the numbers in the format text too). The result is 5050: 100·101/2.

2. Zero passes

How do the two loop forms behave when the sum from 1 to 0 is to be calculated? Predict it first. For the test at the top, change the limit to 0.

Solution

With the test at the top, i = 1 is already greater than the limit 0: the body never runs, and the sum stays 0 – which is correct. With the test at the bottom (counting down, start value 0) the body runs once, and counting down gives −1, which is not 0: the loop goes on until the counter reaches 0 again after about four billion passes. The result is wrong and the program takes a while (in the debugger: Pause or Ctrl+F2). Remember: use the form with the test at the bottom only if the body must surely run at least once.

3. Brain teaser: powers of two

Print the numbers 1, 2, 4, 8, … up to 512, each on its own line (ten numbers). You only need instructions you already know. Hint: doubling a number means adding it to itself.

Solution

; Lesson 4, exercise 3: the powers of two, 1 2 4 ... 512. Doubling = adding a number to itself.

.format pe console
.arch i386
.import msvcrt.dll printf

.code
start:
  push ebx                ; ebx and esi must come back unchanged: we save them
  push esi
  mov ebx, 10             ; ten numbers
  mov esi, 1              ; the first one
again:
  push esi
  push dword fmt
  call [printf]
  add esp, 8
  add esi, esi            ; doubled
  dec ebx
  jnz again
  pop esi
  pop ebx
  xor eax, eax
  ret

.data
fmt db '%d', 10, 0

; Lesson 4, exercise 3: the powers of two, 1 2 4 ... 512. Doubling = adding a number to itself.

.format pe console
.arch x64
.import msvcrt.dll printf

.code
start:
  push rbx                ; rbx and rsi must come back unchanged: we save them
  push rsi
  sub rsp, 40
  mov ebx, 10             ; ten numbers
  mov esi, 1              ; the first one
again:
  lea rcx, [fmt]
  mov edx, esi
  call [printf]
  add esi, esi            ; doubled
  dec ebx
  jnz again
  xor eax, eax
  add rsp, 40
  pop rsi
  pop rbx
  ret

.data
fmt db '%d', 10, 0

; Lesson 4, exercise 3: the powers of two, 1 2 4 ... 512. Doubling = adding a number to itself.

.format pe console
.arch thumb
.import msvcrt.dll printf

.code
start:
  push {r4, r5, r6, lr}   ; r4 to r6 must come back unchanged: we save them
  ldr r6, printf
  movs r4, #10            ; ten numbers
  movs r5, #1             ; the first one
again:
  adr r0, fmt
  mov r1, r5
  blx r6
  adds r5, r5, r5         ; doubled
  subs r4, r4, #1
  bne again
  movs r0, #0
  pop {r4, r5, r6, pc}

.data
align 4
fmt db '%d', 10, 0

; Lesson 4, exercise 3: the powers of two, 1 2 4 ... 512. Doubling = adding a number to itself.

.format pe console
.arch arm64
.import msvcrt.dll printf

.code
start:
  stp x29, x30, [sp, #-48]!
  stp x19, x20, [sp, #16]       ; x19 to x21 must come back unchanged: we save them
  str x21, [sp, #32]
  adrp x21, printf
  ldr x21, [x21, :lo12:printf]
  mov w19, #10                  ; ten numbers
  mov w20, #1                   ; the first one
again:
  adrp x0, fmt
  add x0, x0, :lo12:fmt
  mov w1, w20
  blr x21
  add w20, w20, w20             ; doubled
  subs w19, w19, #1
  b.ne again
  mov x0, #0
  ldp x19, x20, [sp, #16]
  ldr x21, [sp, #32]
  ldp x29, x30, [sp], #48
  ret

.data
fmt db '%d', 10, 0

One register holds the current number (in every pass it is added to itself), a second one counts down ten passes. Both must survive the call of printf and therefore live in registers that a function must return unchanged.

Remember

A loop is a conditional jump backwards. The test is at the top (zero or more passes) or at the bottom (at least one).
The test at the bottom is shorter, but only fits if the body must surely run once.
A counting register changes in every pass; if it counts down to 0 you save the comparison, because decsubs sets the flags.
A loop inside a loop needs its own counter. The inner counter is set again in every pass of the outer one.
If the loop calls a function, the counters must live in registers that the function returns unchanged (and that you save for that).