Death of The For Loop: Conditional Loops in AVR Assembly (100% Pseudocode)

I think there are generally 3 fundamental Conditional Loop structures that you will encounter in practically all programming languages, from C, up. The While loop, the For loop, and the Do While loop. However, In AVR Assembly code at least, I feel that fundamentally, there are only 2 types of loops. I think there are simply: While Loops, and Do While Loops. For loops are simply While or Do While loops with a counter included. And once you include a counter, the structure can become arbitrarily complex based on where you place the counter and how you choose to increment it or compare it to a condition.

The While Loop will first evaluate the condition to determine whether or not code in the body should be executed, or simply skipped over. If the condition is false, the body is skipped. If the condition is true, the code in the body is executed, then the condition will be checked again, and if it is found true again, will continue to execute the code in the body ad infinitum until something causes the condition to not be true.

while(condition){
    //bodycode...
}

This boils down to a compare operation, a branching operation, and then some arbitrary body of code.

1. COMPARE
2. BRANCH to step 5
3. BODYCODE...
4. JUMP to step 1
5. ...

It turns out I also need a JUMP instruction to keep the body looping. I can even re-arrange the order of these instructions, which I often do when I am writing loops in assembly. I tend to prefer placing the jump at the beginning….

1. JUMP to step 3
2. BODYCODE...
3. COMPARE
4. BRANCH to step 2

…and it works out the same. You just need different addresses. Part of the reason I like this ordering is because if I simply remove that pesky extra JUMP instruction, then the While Loop structure reveals a Do While structure!

1. BODYCODE...
2. COMPARE
3. BRANCH

Which usually looks like this…

do{
  //bodycode...
}
while(condition)

It is efficient to use Do While structures when you have complete certainty that you want to perform the operation of the body at least once; which turns out to be a surprisingly common scenario to someone like me who previously avoided Do While loops when coding in any language.

But what happens if I remove the JUMP instruction from that first ordering? the one where I placed the COMPARE instruction on top and the JUMP on the bottom.

1. COMPARE
2. BRANCH
3. BODYCODE...

This actually reveals the If Conditional structure! Which usually looks like this…

if(condition){
  //bodycode...
}

Thus, a While Loop structure could effectively be thought of as an If Condition structure with a JUMP at the end. But also, as a Do While Loop structure with a JUMP at the beginning. The only structure we haven’t discovered yet is the For Loop structure…

for(int counter=0; counter<limit; counter++){
  //bodycode...
}

In Assembly, it seems like you can set up the for loop in a couple different ways. It is essentially just a While Loop with a counter.

1. CLEAR counter
2. COMPARE counter w/ limit
3. BRANCH to step 7 if conditional is false
4. BODYCODE....
5. INCREMENT counter
6. JUMP to step 2
7. ...

That being said, there is no reason you can’t write a Do For Loop structure.

1. CLEAR counter
2. BODYCODE....
3. INCREMENT counter
4. COMPARE counter w/ limit
5. BRANCH to step 2 if conditional is true

Or with the other ordering of the While Structure(the one with the JUMP at the beginning) with an added counter…

1. CLEAR counter
2. JUMP to step 5
3. BODYCODE...
4. INCREMENT counter
5. COMPARE counter w/ limit
6. BRANCH to step 3 if conditional is true

I find this version interesting because by simply changing step 2 to JUMP to step 4, instead of 5, we can include the counter as part of the conditional block instead of the body. At this point, using labels will be helpful…

init:
  1. CLEAR counter
  2. JUMP condition
body:
  3. BODYCODE...
condition:
  4. INCREMENT counter
  5. COMPARE counter w/ limit
  6. BRANCH body

This completely changes the way the counter works, because now it is counting the times the condition was checked, not the times that the body was executed. This might be useful for some particular problems. You can also have double conditionals by simply tacking more COMPARE’s and BRANCH’es to the end of this. Of course you can add as many counters as you have free registers. And of course you can modify them however you like; you need not be restricted to merely INCREMENT’ing.

In fact, we can reduce this even further by getting rid of the limit. Even though the limit will usually be a constant value, and thus won’t take up a register, it can still be redundant. If we set the counter to the limit, and choose to DECREMENT the counter instead of INCREMENT it, then we can use zero as our limit and simply BRANCH according to the counter’s position with respect to zero.

init:
  LOAD counter,limit
  JMP condition
body:
  BODYCODE...
  DECREMENT counter
condition:
  BRANCH to body

In fact, if we do this, we don’t even need the compare instruction in AVR. I think most Assembly languages will usually have a branching instruction that checks if the result of the last arithmetic operation was zero, which DECREMENT’ing the counter will eventually do.

Quick note: in Assembly, strings almost always have a zero appended to them, so that they can be “null terminated”. Because strings generally have a 0 appended to the end of them, when reading or copying them, null termination allows us to eliminate the counter and write a Do While loop that checks whether or not a byte read from memory is zero…

init:
  LOAD pointer
body:
  LOAD register,[pointer]
  INCREMENT pointer
condition:
  COMPARE register w/ 0
  BRANCH to body if not equal to 0

Reading or writing to Memory typically requires a pointer. A pointer is simply a register that contains an address to a location in memory. In the case of loading bytes from a string, I want the address of the first byte in the string. As I INCREMENT the pointer, I can load each consecutive byte of the string into a register, erasing the old one each time a new one is loaded. This is useful because before loading the new value, I can check the condition of the old one. But this isn’t very useful all by it self. More commonly, I am copying a string from one location in memory to another; and sometimes even back to the same location. This will require 2 pointers, though…

init:
  LOAD pointera
  LOAD pointerb
body:
  LOAD      register,[pointera]
  STORE    [pointerb],register
  INCREMENT pointera
  INCREMENT pointerb
condition:
  COMPARE   register,0
  BRANCH to body IF NOT EQUAL to 0

This loop is structured as a Do While, thus I am expecting the string to be AT LEAST one byte long! Because strings generally always have a zero appended to them for null termination. An empty string, often called a “null string”, is a string that is one byte long and only contains the value zero. Thus, so long as I am certain that I have fed this program the address of a valid string, it is okay to load the first byte right away before knowing what it is. The Do While Loop structure is perfect!

How about if I bring back that counter. Only, now that I don’t need it for counting up or down to a fixed value, I can use it to count the length of a string.

init:
  CLEAR counter
  LOAD pointer
  JUMP condition
body:
  INCREMENT counter
  INCREMENT pointer
condition:
  LOAD register,[pointer]
  COMPARE register w/ 0
  BRANCH to body IF NOT EQUAL body,0

Okay, so first notice I inserted a JUMP before the body, making it a While Loop structure(I’ve long abandoned thinking about the term For Loop). This is important, because when counting the Length of the string, I usually DON’T want to count the null terminator. Thus, it is important to check the condition of the first byte BEFORE deciding whether or not to increment the counter. Another interesting thing I have done is move the Load instruction into the condition segment, whereas in my prior examples, I would load the byte during the body segment. Theoretically, I could move it back to the body segment, but then I would have to add an extra instruction to the init segment pre-loading the first byte; otherwise the first conditional check will have nothing to compare. It would also make sense to increment the counter and pointer BEFORE loading the byte, otherwise we we redundantly load the same first byte twice.

init:
  CLEAR counter
  LOAD  pointer
  LOAD  register,[pointer]
  JUMP condition
body:
  INCREMENT counter
  INCREMENT pointer
  LOAD register,[pointer]
condition:
  COMPARE register,0
  BRANCH to body IF NOT EQUAL to 0

This is fine, because if we have reached the body at this point, we should be assured that the first byte of the string was not 0, thus a valid character and worthy of counting. In the very least, the next byte could be the null terminator, which case the conditional segment will catch it before getting a chance to branch to the body and increment the counter again.

There you have it! A demonstration of the immense flexibility of Assembly code when it comes to Conditional Loop structures! I guess I should name this blog post: Death of The For Loop.