33 Repetition — loops and invariants
What to know first
Looking back
Chapter 2 said “even simple steps, taken billions of times a second, can build anything however complicated.” But our programs up to chapter 32 flow from top to bottom once and end — where do the billions of steps come from?
A. From a device that executes the same statements again. Going back to a block while a condition is true — the loop. If branching was the device that splits flow, the loop is the device that winds it up, and the moment we have both, C becomes a language that can write down everything computable (theoretically so as well — all chapter 2′s model of computation demands is “sequence, branch, repetition”).
The need for this chapter, and its context
while’s parentheses. And the invariant learned here becomes the thinking tool for nearly every array traversal to come.By the end of this chapter
while, for, do-while), new operators (++, +=), the place where do-while wins (counting backwards with an unsigned index), and the way a loop is trusted — the invariant: what it means, how it is used in practice, and which bugs it catches, in a section of its own. Then we take for apart slot by slot — what may be declared in the first one (C23 changed the rules there) and how far that name is visible and how long it lives, why the condition slot is not a “test” but code that runs every turn, the three reasons a loop fails to end, and the mistakes that appear as soon as loops are nested. Finally we meet the reunion booked in chapter 13 — Duff’s device.The questions this chapter answers
- So is walking backwards always a
do-while? - Does
continuego to the same place in all three? - Is
do-whilereally that rare? - If the invariant holds, is the loop guaranteed to end?
- Is this the same “loop invariant” formal verification talks about?
- What if the condition never becomes false?
- Then is the old style of declaring the index outside (
int i; for (i = 0; ...)) bad? - What, then, belongs in the first slot?
- If the condition has a side effect, does that effect always happen?
- In a double loop, which one should be on the outside?
33.1 The three siblings of the loop#
while — the most primitive form. “While the condition is true, repeat the block”:
while (condition) {
statements to repeat
}It checks the condition first, so if it is false from the start the loop never turns.
for — the form that gathers the loop’s housekeeping (start, condition, update) onto one line. Seen in a demonstration — the sum from 1 to 100:
examples-en/ch32/sum.c
#include <stdio.h>
int main(void)
{
int sum = 0;
for (int i = 1; i <= 100; i += 1) {
sum += i; /* invariant: sum == 1 + 2 + ... + (i - 1); after the update, ... + i */
}
printf("sum of 1..100 = %d\n", sum);
return 0;
}
Output
sum of 1..100 = 5050
Read for (int i = 1; i <= 100; i += 1) in three slots — start (int i = 1: make the loop variable), condition (i <= 100: checked before each turn), and update (i += 1: executed at the end of each turn). The new operator += is an abbreviation of chapter 24′s assignment, the same as i = i + 1, and the still shorter i++ (the increment operator) does the same job — idiomatically you will see the for (...; i++) shape most often. (++ has a prefix form and a postfix form, and subtle circumstances inside expressions — treated together with the next chapter’s story of sequence points.)
do-while — the form that executes the block first and checks the condition afterwards (do { ... } while (condition);). It is used for “work that must happen at least once” (showing a menu first and then asking whether to repeat), and is the least frequently seen of the three.
Put the three side by side and give them the same job.
examples-en/ch32/three.c
/* The same job written with each of the three siblings, so the differences show. */
#include <stdio.h>
/* summing 1..5 - while */
static int sum_while(void)
{
int sum = 0;
int i = 1; /* start: it sits outside the loop */
while (i <= 5) { /* condition */
sum += i;
i += 1; /* update: at the end of the body - easy to forget */
}
return sum;
}
/* the same job - for. The housekeeping (start, condition, update) is on one line */
static int sum_for(void)
{
int sum = 0;
for (int i = 1; i <= 5; i += 1)
sum += i;
return sum;
}
/* the same job - do-while. It runs the body once first */
static int sum_do(void)
{
int sum = 0;
int i = 1;
do {
sum += i;
i += 1;
} while (i <= 5);
return sum;
}
/* where the three differ, part 1 - when the condition is false from the start */
static int count_while(int n)
{
int turns = 0, i = 0;
while (i < n) { turns++; i++; }
return turns;
}
static int count_do(int n)
{
int turns = 0, i = 0;
do { turns++; i++; } while (i < n);
return turns;
}
/* where the three differ, part 2 - where continue goes.
A for loop's update always runs, even after continue. When the loop is
rewritten as a while with the update at the end of the body, continue jumps
over that update and the loop never stops. */
static int odd_sum_for(void)
{
int sum = 0;
for (int i = 1; i <= 9; i++) {
if (i % 2 == 0)
continue; /* i++ still runs */
sum += i;
}
return sum;
}
static int odd_sum_while_fixed(void)
{
int sum = 0;
int i = 1;
while (i <= 9) {
if (i % 2 == 0) {
i++; /* the update has to happen here too */
continue;
}
sum += i;
i++;
}
return sum;
}
/* Where do-while really earns its keep - walking backwards with an unsigned index.
size_t cannot go below 0, so for (size_t i = n-1; i >= 0; i--) is an endless
loop (chapter 41). do-while writes down exactly 'step down first, handle 0,
then stop'. Since the body runs first, n must not be 0 - and that check is
part of the pattern. */
static void countdown(size_t n)
{
if (n == 0) { /* guards do-while's at-least-once rule */
printf(" (nothing to visit)\n");
return;
}
printf(" ");
size_t i = n;
do {
i--; /* n-1 down to 0 */
printf("%s%zu", i == n - 1 ? "" : " ", i);
} while (i > 0);
printf("\n");
}
int main(void)
{
printf("[the same job, three ways]\n");
printf(" while : 1..5 -> %d\n", sum_while());
printf(" for : 1..5 -> %d\n", sum_for());
printf(" do-while : 1..5 -> %d\n", sum_do());
printf("\n[what changes when the condition is false from the start]\n");
printf(" while (i < 0) ran %d time(s)\n", count_while(0));
printf(" do ... while (i < 0) ran %d time(s)\n", count_do(0));
printf("\n[continue and the update step]\n");
printf(" for : sum of odd numbers 1..9 = %d\n", odd_sum_for());
printf(" while : sum of odd numbers 1..9 = %d\n", odd_sum_while_fixed());
printf("\n[walking backwards with an unsigned index]\n");
countdown(6);
countdown(1);
countdown(0);
printf(" do-while says it plainly: step down first, handle 0, then stop.\n");
printf(" in the for loop i++ runs even after continue;\n");
printf(" in the while loop the update sits in the body, so continue can skip it -\n");
printf(" that is how a working loop turns into an endless one when it is rewritten.\n");
return 0;
}
Output
[the same job, three ways]
while : 1..5 -> 15
for : 1..5 -> 15
do-while : 1..5 -> 15
[what changes when the condition is false from the start]
while (i < 0) ran 0 time(s)
do ... while (i < 0) ran 1 time(s)
[continue and the update step]
for : sum of odd numbers 1..9 = 25
while : sum of odd numbers 1..9 = 25
[walking backwards with an unsigned index]
5 4 3 2 1 0
0
(nothing to visit)
do-while says it plainly: step down first, handle 0, then stop.
in the for loop i++ runs even after continue;
in the while loop the update sits in the body, so continue can skip it -
that is how a working loop turns into an endless one when it is rewritten.
What the demonstration measured is the whole of the difference between them.
| form | when the condition is seen | minimum turns | where the housekeeping lives |
|---|---|---|---|
while | before the body | 0 | start before the loop, update inside the body — scattered |
for | before the body | 0 | gathered into three slots |
do-while | after the body | 1 | same as while — but “handle, then stop” comes naturally |
Table 33.1 — The three loop forms — where the condition is seen, and the minimum number of turns
The reason for is the most widely used lies in that third column — everything about “how many times does this turn?” sits on one line, so the accident of forgetting the update and producing an infinite loop is structurally rarer. Conversely, repetition whose turn count is not known in advance (read to the end of a file, keep going until the user says stop) is natural with while.
33.1.1 Where do-while really wins — counting backwards#
The place where “at least once” pays off best is walking backwards with an unsigned index: that very common 5, 4, 3, 2, 1, 0 traversal, which the naive spelling turns into an endless loop.
for (size_t i = n - 1; i >= 0; i--) /* never ends */size_t is unsigned, so it is always at least 0. The condition stays true forever, and subtracting one from 0 wraps round to SIZE_MAX (chapter 28). The last element, index 0, has to be handled and then the loop must stop — and that “handle, then stop” does not come out in one line from for or while, which test first.
do-while writes exactly that order down — step down first, use it, and stop when it reaches 0.
size_t i = n;
do {
i--; /* n-1, …, 1, 0 */
use(a[i]);
} while (i > 0); /* stops after 0 has been handled */That is what the demonstration’s countdown prints as 5 4 3 2 1 0. Because the body runs first, n must not be 0 (decrementing 0 wraps), and putting that check in front is part of the pattern — the demonstration’s countdown(0) returns having done nothing.
Q. So is walking backwards always a do-while?
A. No. There is a widely used one-line for for the same job.
for (size_t i = n; i-- > 0; ) /* the condition tests and decrements at once */It reads “look at the current value against 0, then subtract one”, so the body sees n-1 down to 0, and it is safe when n is 0 (it simply never turns). Short, but the condition slot is changing a value, which takes a moment to read the first time.
The dividing line is this — for something that may be empty, the for shape is safer; where “there is at least one” is a precondition (already checked, or the function is not entered without elements), do-while shows the intent better. Both shapes return in chapter 42′s section on backwards traversal.
Q. Does continue go to the same place in all three?
A. No — and this is the trap when a for is rewritten as a while.
In a for, continue goes to the condition by way of the update expression. So you can put if (...) continue; anywhere and i++ still runs. In a while the update sits inside the body, so continue jumps over it — a loop that worked becomes one that never ends the moment it is rewritten. That is why the demonstration’s odd_sum_while_fixed does one extra i++ before the continue. (do-while’s continue also goes to the condition test — we return to it in chapter 42.)
Q. Is do-while really that rare?
A. As repetition, yes. Yet if you count the word do in production code it shows up surprisingly often — and most of those are not repetition at all. They are the pattern do { ... } while (0), which turns a multi-statement macro into “one statement”. The headers of the Linux kernel alone contain thousands of them.
Why braces alone are not enough, and why of all things a loop that turns once, only makes sense once macros are known, so it is gathered in chapter 42 (macros themselves are chapter 61). One thing is worth carrying from here — when you meet a do-while, first check whether it is repetition or while (0).
33.2 The invariant — how a loop is trusted#
A loop is a statement that cannot be checked by eye. With an if you read both branches and you are done; with a loop, how many turns it takes is settled at run time. Counting the turns in your head does not give confidence, and in practice loop bugs happen at the two ends rather than in the middle — one turn too few, one turn too many. They usually give the right answer when run, so tests miss them too.
The tool people use for this is the loop invariant. The name is grand and the job is one sentence — pick a proposition that is always true at the same point of every turn, and read the loop through it.
examples-en/ch32/invariant.c
/* Seeing an invariant - the proposition that holds on every turn, actually checked.
assert writes down "this must be true here" as code (chapter 17). */
#include <assert.h>
#include <stdio.h>
/* 1. The sum from 1 to n - the invariant printed as a table.
On every entry to the body, sum == 1 + 2 + ... + (i-1) holds.
The right-hand side is counted separately and compared. */
static int sum_to(int n)
{
int sum = 0;
int checked = 0; /* 1 + ... + (i-1), counted on the side */
printf(" i | sum | 1+...+(i-1) | invariant\n");
printf(" ---+-----+-------------+----------\n");
for (int i = 1; i <= n; i++) {
assert(sum == checked); /* <- this is where it holds, every turn */
printf(" %2d | %3d | %11d | %s\n", i, sum, checked,
sum == checked ? "holds" : "BROKEN");
sum += i; /* the body grows the equation by one term */
checked += i; /* and the update i++ restores the shape */
}
/* Termination: i > n. Put i = n+1 into the invariant: sum == 1 + ... + n */
printf(" loop ended: sum = %d\n", sum);
return sum;
}
/* 2. What guarantees termination is not the invariant but a shrinking quantity.
Here that quantity is n - i, and it falls by exactly one per turn. */
static void measure_shrinks(int n)
{
int prev = n; /* how many steps were left last turn */
for (int i = 0; i < n; i++) {
int left = n - i; /* steps left = the shrinking quantity */
assert(left < prev || i == 0);
assert(left >= 0);
prev = left;
}
printf(" the quantity (n - i) fell from %d to 0, one step at a time\n", n);
}
/* 3. Binary search - where an invariant really earns its keep.
Invariant: if the key is in the array at all, it is inside [lo, hi).
The range narrows every turn (termination); an empty range means absent. */
static int binary_search(const int *a, int n, int key)
{
int lo = 0, hi = n; /* the half-open range [lo, hi) */
int steps = 0;
while (lo < hi) {
assert(0 <= lo && lo <= hi && hi <= n); /* the range stays valid */
int mid = lo + (hi - lo) / 2; /* lo+hi could overflow */
assert(lo <= mid && mid < hi); /* so mid is inside the range */
steps++;
if (a[mid] == key)
return mid;
if (a[mid] < key)
lo = mid + 1; /* the left half cannot hold the answer */
else
hi = mid; /* the right half cannot hold the answer */
}
printf(" (%d not found in %d steps)\n", key, steps);
return -1;
}
int main(void)
{
printf("[the invariant of a summing loop]\n");
int s = sum_to(5);
printf(" 1 + 2 + 3 + 4 + 5 = %d\n", s);
printf("\n[what makes a loop end is a quantity that shrinks]\n");
measure_shrinks(4);
printf("\n[binary search - the invariant is the search range]\n");
int a[] = { 2, 4, 8, 16, 32, 64, 128 };
int n = (int)(sizeof a / sizeof a[0]);
for (int key = 1; key <= 16; key *= 2)
printf(" key %3d -> index %d\n", key, binary_search(a, n, key));
printf(" key %3d -> index %d\n", 5, binary_search(a, n, 5));
printf("\n[the empty range is not a special case - the invariant covers it]\n");
printf(" searching an empty array for 42 -> index %d\n",
binary_search(a, 0, 42));
return 0;
}
Output
[the invariant of a summing loop]
i | sum | 1+...+(i-1) | invariant
---+-----+-------------+----------
1 | 0 | 0 | holds
2 | 1 | 1 | holds
3 | 3 | 3 | holds
4 | 6 | 6 | holds
5 | 10 | 10 | holds
loop ended: sum = 15
1 + 2 + 3 + 4 + 5 = 15
[what makes a loop end is a quantity that shrinks]
the quantity (n - i) fell from 4 to 0, one step at a time
[binary search - the invariant is the search range]
(1 not found in 3 steps)
key 1 -> index -1
key 2 -> index 0
key 4 -> index 1
key 8 -> index 2
key 16 -> index 3
(5 not found in 3 steps)
key 5 -> index -1
[the empty range is not a special case - the invariant covers it]
(42 not found in 0 steps)
searching an empty array for 42 -> index -1
33.2.1 Read it in three pieces#
Take the demonstration’s first loop (summing 1 to 5). On every entry to the body
holds — in words, “what has been added so far reaches up to just before ”. An invariant is always checked in three pieces.
| Piece | What it checks | In this loop |
|---|---|---|
| Initialization | is it true on first entering the loop? | i is 1 and sum is 0 — the empty sum, so yes |
| Maintenance | is it true again after one turn? | the body’s sum += i grows the right side to , and the update i++ restores “up to just before ” |
| Termination | what comes out when the ending value is substituted? | i is 6, so sum — the answer we wanted |
Table 33.2 — The three pieces of checking an invariant
With those three you have a proof that the loop is right. It is the shape of mathematical induction — true at the first step, and true at the next whenever it is true now, therefore true throughout — which answers “how can I be sure when I do not know how many turns it takes?”. The demonstration does not leave the proposition as prose: it checks it with assert on every turn and prints the table.
Q. If the invariant holds, is the loop guaranteed to end?
A. No. That is the most misunderstood part of the idea.
An invariant only says what is true while it turns. A loop that runs forever can keep its invariant perfectly. Ending has to be shown separately, and what shows it is a quantity that necessarily shrinks every turn (a variant, or measure). The demonstration’s second function measures exactly that: n - i falls by one per turn and cannot go below 0, so the loop must end.
The Zune accident later in this chapter is precisely this one piece missing. That loop’s invariant (days is the number of days left in the year) held perfectly well — but one branch made no progress at all. Hence a loop is interrogated with two questions, not one: “what is true every turn?” and “what shrinks every turn?”
33.2.2 How people actually use the word#
Outside textbooks the invariant shows up in four guises. None of them is about writing proofs; all four are about pinning down the thinking.
| Guise | What it looks like | What it buys |
|---|---|---|
| A one-line comment | /* invariant: sum == 1 + ... + (i-1) */ | the commonest form. Whoever edits the body learns what must not be broken |
An assert | an assert(...) at the head of the loop, as in the demonstration | the proposition becomes code and is checked while running. Conventionally kept to debug builds (chapter 18) |
| Names and notation | half-open ranges like [lo, hi), names like end and count | it forces the invariant into the shape of the code rather than prose — binary search below is the example |
| Data-structure invariants | “a ring buffer’s head and tail are always inside the buffer”, “this array is always sorted” | the same idea widened beyond loops. There it is called a representation invariant and becomes part of a contract (chapter 53) |
Table 33.3 — Four ways invariants are used in practice
The third is the most practical of the four. It is why C and the languages after it settled on ranges that point one past the end ([first, last)): “length = last - first” and “empty = first == last” then hold by themselves, and the boundaries stop needing separate thought. Pointer traversal in chapter 41, strings in chapter 43, and nearly every sweep in the standard library take this shape.
33.2.3 Binary search — where the invariant earns its keep#
The demonstration’s third function is the example. It halves a range [lo, hi) looking for a value, and the invariant is a single sentence.
“ If the key is in the array at all, it is inside [lo, hi). ”
That one line settles four things at once.
- How the ends move. If
a[mid] < key, nothing at or belowmidcan be the answer, solo = mid + 1; otherwisehi = mid. “Why does only one side get the+1?” follows from the invariant. - The empty input stops being a special case. With no elements
lo == hi, the loop never turns, and the answer is “absent”. The demonstration’s last line confirms it. - Termination is visible. The range
hi - loat least halves every turn — there is the shrinking quantity. - A missing value still gives the right answer. When the loop ends the range is empty, and by the invariant the key “would have been in that range if it were there at all”, so it is not there.
In practice. The binary search bug that hid in a standard library for nine years
Binary search was first published in 1946, but a version that works correctly for all n is said not to have appeared until 1962. And even after that one bug remained in hiding — the (lo + hi) / 2 inside Java’s Arrays.binarySearch, which by the time its author published it in 2006 had been in the JDK for nine years.1 For a big enough array lo + hi overflows first and turns negative, and at that moment mid leaves the range.
★ What is worth noticing is that the invariant catches this bug. Write down “mid is inside [lo, hi)” as a proposition — the demonstration does, with an assert — and it breaks the instant the overflow happens. Hence the safe spelling lo + (hi - lo) / 2, which is the same prescription as chapter 28′s “subtract first and it cannot overflow”.
The lesson is not “binary search is hard”. It is that boundaries cannot be guarded by eye; they have to be guarded by a proposition.
33.2.4 What it buys#
| What the invariant catches | How |
|---|---|
| off-by-one — one turn too few or too many | substitute the ending value into the proposition and a wrong answer shows immediately |
| empty and one-element inputs | the “zero turns” case is covered by the same proposition — no separate special case to write |
| boundary arithmetic mistakes | an assert that an index or mid is inside the range catches it while running |
| breaking it while editing | what must be preserved is written next to the body — a safety line for refactoring |
| loops that never end | the shrinking quantity written alongside guarantees termination |
Table 33.4 — What an invariant catches
None of this has to be written out every time. But the habit of stating the sentence before writing the loop pays well — if it cannot be stated, the thinking is usually not finished yet, and a loop written in that state goes wrong at the ends. It is also the first exercise in the perspective of code as contract (chapter 53).
Q. Is this the same “loop invariant” formal verification talks about?
A. The same idea, used more strictly. Tools that prove programs mechanically — in C, ACSL annotations with Frama-C are the well-known pair — require an invariant and a decreasing measure in annotation syntax for every loop, and build the proof from them. Aviation, medical and nuclear work, where testing is not enough, really do work that way.
What this chapter does is the scaled-down version of that tool: ask the same question with a human head, and half-automate it with assert. Even without the tools, the habit of asking keeps its value.
Q. What if the condition never becomes false?
A. An infinite loop — the program turns there forever. Usually it is the result of a bug in which the update was forgotten, but a deliberate infinite loop (while (true)) is a respectable idiom too — it is the skeleton of programs for which “not ending is normal”, such as servers, and you leave it from inside on a condition with break (leave the loop — the same word as switch’s break). What is dangerous is not the infinite loop itself but the unintended one.
33.3 for’s first slot — what may be declared there#
The standard gives the three slots names — clause-1, expression-2 and expression-3. Only the first has a different kind of name, for a reason: the other two are expressions, while the first may be an expression or a declaration. The rules attached to that declaration are this section’s story.
examples-en/ch32/for_decl.c
/* What may be declared in for's first slot (clause-1) - the measured version.
Built as C23. What the comments say about C99 and C11 was checked with
-std=c11 -pedantic-errors. */
#include <stdio.h>
/* 1. One declaration means one base type. Derived types may join it. */
static void one_base_type(void)
{
int a[3] = { 10, 20, 30 };
/* one int makes a value, two pointers and a count at once */
for (int *p = a, *end = a + 3, n = 0; p != end; p++, n++)
printf(" a[%d] = %d\n", n, *p);
/* for (int i = 0; double x = 0.0;) is a syntax error -
"expected expression before 'double'" on both gcc and clang */
}
/* 2. The name lives for one loop - the three slots and the body, and no further. */
static void scope_of_the_name(void)
{
int i = 100; /* the outer i */
for (int i = 0; i < 2; i++) /* the inner i shadows the outer one */
printf(" inside the loop i = %d\n", i);
printf(" after the loop i = %d (the outer one was never touched)\n", i);
}
/* 2b. Lifetime - the name in clause-1 is *one object* for the whole loop.
A variable declared in the body is not: it is born and dies every turn. */
static void lifetime_of_the_two(void)
{
int last_body = -1;
for (int i = 0; i < 3; i++) {
int body = 0; /* a new object each turn - so always from 0 */
body++;
last_body = body;
printf(" turn %d: counter i = %d (one object, kept), body = %d (reborn)\n",
i, i, body);
}
printf(" the body variable never grew past %d - it died at every closing brace\n",
last_body);
}
/* 2c. That it is one object shows in its address - the same on all three turns. */
static void one_object_one_address(void)
{
const void *first = nullptr;
for (int i = 0; i < 3; i++) {
if (i == 0)
first = (const void *)&i;
printf(" turn %d: &i %s\n", i,
(const void *)&i == first ? "is the same address as turn 0"
: "CHANGED (would mean a new object)");
}
/* Leaving the loop ends that object's lifetime. Reading the address kept
above would be undefined behaviour, so we do not. The name is gone too ---
writing i here would be a compile error. */
}
/* 3. C23's auto - the type is inferred from the initializer. */
static void c23_auto(void)
{
for (auto i = 0; i < 3; i++) /* i is inferred as int */
printf(" auto i = %d\n", i);
}
/* 4. C23 dropped the storage-class constraint, so static is allowed here.
Being allowed and being a good idea are two different things - this
function is the reason. */
static void static_counter(void)
{
for (static int calls = 0; calls < 2; calls++)
printf(" static clause-1: this line ran (calls = %d)\n", calls);
}
int main(void)
{
printf("[one declaration means one base type]\n");
one_base_type();
printf("\n[the name lives in the loop and nowhere else]\n");
scope_of_the_name();
printf("\n[the counter lives for the whole loop, a body variable does not]\n");
lifetime_of_the_two();
printf("\n[one object means one address]\n");
one_object_one_address();
printf("\n[C23: auto infers the type from the initializer]\n");
c23_auto();
printf("\n[C23: a static object in clause-1 is initialized once, ever]\n");
printf(" first call:\n");
static_counter();
printf(" second call:\n");
static_counter();
printf(" third call:\n");
static_counter();
printf(" the second and third calls print nothing - the counter kept its\n");
printf(" value from the first call, so the loop never ran again.\n");
return 0;
}
Output
[one declaration means one base type]
a[0] = 10
a[1] = 20
a[2] = 30
[the name lives in the loop and nowhere else]
inside the loop i = 0
inside the loop i = 1
after the loop i = 100 (the outer one was never touched)
[the counter lives for the whole loop, a body variable does not]
turn 0: counter i = 0 (one object, kept), body = 1 (reborn)
turn 1: counter i = 1 (one object, kept), body = 1 (reborn)
turn 2: counter i = 2 (one object, kept), body = 1 (reborn)
the body variable never grew past 1 - it died at every closing brace
[one object means one address]
turn 0: &i is the same address as turn 0
turn 1: &i is the same address as turn 0
turn 2: &i is the same address as turn 0
[C23: auto infers the type from the initializer]
auto i = 0
auto i = 1
auto i = 2
[C23: a static object in clause-1 is initialized once, ever]
first call:
static clause-1: this line ran (calls = 0)
static clause-1: this line ran (calls = 1)
second call:
third call:
the second and third calls print nothing - the counter kept its
value from the first call, so the loop never ran again.
Rule 1 — there is only one declaration. The first slot holds one declaration, so there is one base type. Something like for (int i = 0; double x = 0.0; ...) is not even grammar (both gcc and clang: “expected expression before double”). What derives from the same base type, however, may join freely — the demonstration’s
for (int *p = a, *end = a + 3, n = 0; p != end; p++, n++)is the example. One int produced two pointers and an integer. If the types must genuinely differ there are two ways out — move one outside the loop, or tie them into a single structure.
Rule 2 — the name is born in the loop and dies with it. Two different axes are folded together in that sentence, so they get a section of their own.
33.3.1 How far the name is visible, and how long it lives#
Separate the two questions first. Where the name is visible (scope) and when the object exists (lifetime) are different axes — an object can be alive while its name is invisible (our locals, while another function runs), though never the other way round.
Scope. The standard settles it in one sentence: “if clause-1 is a declaration, the scope of any identifiers it declares is the remainder of the declaration and the entire loop, including the other two expressions.”2 Drawn out:
int i = 100; /* the outer i */
for (int i = 0; i < 3; i++) { /* <- an i born here, */
printf("%d\n", i); /* visible in condition, update and body */
} /* <- and the name is gone here */
printf("%d\n", i); /* the outer i again — still 100 */A name of the same spelling outside is shadowed. In the demonstration the inner i prints 0 and 1 while the outer stays at 100. Shadowing is not a violation but normal behaviour, and because it confuses readers many codebases turn on -Wshadow in gcc and clang.
Lifetime. With no storage class written, the variable in the first slot has automatic storage duration. The rule: “its lifetime extends from entry into the block with which it is associated until execution of that block ends in any way. (Entering an enclosed block or calling a function suspends, but does not end, execution of the current block.)”3 Which block is “associated” is the crux, and C23 treats the loop itself as one block and the body as another block inside it.4
So the outcomes split like this.
| Declared where | Lifetime | Therefore |
|---|---|---|
first slot, for (int i = 0; ...) | one object for the whole loop | it is the same object from turn to turn — the value carries, and so does the address |
inside the body, for (...) { int t = 0; ... } | born and dead every turn | the initialization happens again each time — nothing can accumulate in it |
outside the loop, int i; for (i = 0; ...) | until the function’s block ends | the value survives the loop — and the next loop can inherit it by accident |
Table 33.5 — Lifetime, by where the variable is declared
The demonstration measures all three. The body variable never gets past 1 (it is reborn at 0 every turn), and the first slot’s i has the same address on all three turns — which is what “one object” means.
A common misconception. “the counter is created afresh on every turn of the loop”
Not in C. The variable in the first slot is one object per loop, and turning the loop merely changes its value. The demonstration compares &i across three turns and finds one address.
There is a reason for the confusion. A variable declared inside the body really is born anew every turn, and that is the far more common case. Habits from other languages play a part too — JavaScript’s let and languages that capture variables in closures chose to make a fresh variable per iteration. C has no such device, so if you want to keep each turn’s value separately you declare it in the body or store it somewhere yourself.
Counter-example. Keeping a pointer to the counter after the loop
int *p;
for (int i = 0; i < 3; i++)
p = &i; /* once the loop ends this points at a dead object */
printf("%d\n", *p); /* undefined behaviour */The name disappearing and the object disappearing are two different events, and here both happen. When the loop’s execution ends, objects with automatic storage duration in that block reach the end of their lifetime, so reading through a saved address is undefined behaviour whatever you kept it in (chapter 45 is the lifetime story). gcc catches some shapes of this with -Wdangling-pointer, but not the ones stored away and used later.
If a value is needed after the loop there are two ways — put it in a variable outside the loop, or copy out the value you found rather than the index.
Q. Then is the old style of declaring the index outside (int i; for (i = 0; ...)) bad?
A. In C89 it was the only way (declarations in the first slot arrived with C99). Seeing that shape today usually means old code, or a place where C89 must be kept.
For new code the first slot is better, and the reason is not taste but that a shorter lifetime leaves fewer places to be wrong — when the loop ends both the name and the object are gone, so the next loop cannot inherit a value and reusing i across a function cannot get tangled. It is chapter 59′s principle about names, met early: keep a name alive only as long as it is needed.
There is one exception. When the index’s value after the loop is what you want — “how far did it get?” asked after the loop — it has to be declared outside. Even then, copying out the result is usually easier to read.
Rule 3 — the storage class has a history. When C99 allowed a declaration in the first slot, it added a constraint alongside.
“The declaration part of a for statement shall only declare identifiers for objects having storage class auto or register.”5 In plain words, ordinary local variables only — static, extern, typedef and structure definitions were all violations.
And then C23 deleted the constraint outright. During standardization the question “may constexpr be used there?” was raised (the United Kingdom’s comment GB-125), and while looking for an answer the committee concluded that it was not even sure why the constraint existed, so the constraint itself was removed.6 Checking the drafts shows exactly that — the C23 committee draft N3054 still has it in 6.8.6.1, and from the next draft, N3096, it is gone. The only constraint left on iteration statements in today’s C23 text is that the controlling expression shall have scalar type.
Measured, the compilers have followed.
| written in the first slot | -std=c11 -pedantic-errors | -std=c23 | note |
|---|---|---|---|
int i = 0 | OK | OK | the basic shape |
int *p = a, n = 0 | OK | OK | derivations of one base type may join |
register int i = 0 | OK | OK | the other half of what the old constraint allowed |
static int i = 0 | diagnosed | OK | gcc: “declaration of static variable … in for loop initial declaration” / clang: “declaration of non-local variable in for loop is a C23 extension” |
typedef int T; | diagnosed | OK | clang: “non-variable declaration in for loop is a C23 extension” |
struct P { int x; } p | gcc diagnoses | OK | clang stayed silent even in C11 — a diagnostic is required, but its shape is the implementation’s choice |
constexpr int n = 3 | a C23 word | OK | this very question is what removed the constraint |
auto i = 0 | read as int | type inference | C23′s auto is inference, not a storage class |
_Thread_local int i | error | error | a function-scope name is implicitly auto, which clashes |
int i = 0( -std=c90) | error | — | “for loop initial declarations are only allowed in C99 or C11 mode” |
Table 33.6 — What may go in for’s first slot — by standard and compiler
The measurements used gcc 14.2 and clang 22.1. What stands out in the table is that the diagnostics appear only with -pedantic-errors turned on. Build with plain -std=c11 -Wall -Wextra and both compilers accept static in silence — chapter 16′s point that “no warning” does not mean “conforming”, again.
Counter-example. Writing static in the first slot
That C23 permits it does not make it a good idea. A static object is initialized once, when the program starts, and keeps its value. So a function containing
for (static int calls = 0; calls < 2; calls++)
...only turns on its first call. From the second call on, calls is already 2, and the = 0 that looks like initialization is never executed again. The demonstration prints that silence exactly — the second and third calls print nothing at all.
If static is what you want, you want its meaning (a value that survives between calls), so declare it in the function rather than in the loop’s first slot and let the intent show. Lifetimes are chapter 45.
Q. What, then, belongs in the first slot?
A. Only the loop’s housekeeping. MISRA (Motor Industry Software Reliability Association) C, the automotive coding guideline, even pins this down as a rule — “a for loop shall be well-formed” (rule 14.2, chapter 101): the first slot initializes the loop counter and nothing else, the condition slot only compares that counter (without side effects), and the update slot only increments or decrements it. A for (;;) with all three slots empty is allowed as the exception.
The rule earns its keep even where no guideline applies. The three slots are where a reader reconstructs “how many times does this turn?” at a glance, and that value disappears the moment other work is mixed in.
33.4 The condition slot is code, not a test#
If the first slot is the place that runs once, the condition slot is the place that runs every turn. And whatever runs can have side effects.
examples-en/ch32/cond_effect.c
/* The condition slot is not a test but code that runs every turn - measured. */
#include <stdio.h>
static int limit_calls = 0;
/* called on every turn, counting how often it was called */
static int limit(void)
{
limit_calls++;
return 5;
}
static int probe_calls = 0;
static int probe(int i)
{
probe_calls++;
return i < 3;
}
int main(void)
{
printf("[the condition runs once more than the body]\n");
int turns = 0;
for (int i = 0; i < limit(); i++)
turns++;
printf(" body ran %d times, limit() was called %d times\n", turns, limit_calls);
printf(" the last call is the one that fails and ends the loop\n");
printf("\n[short-circuit can skip the side effect entirely]\n");
probe_calls = 0;
int guard = 0; /* if the left side is false the right side is not evaluated */
for (int i = 0; guard && probe(i); i++)
;
printf(" guard is false: probe() was called %d time(s)\n", probe_calls);
probe_calls = 0;
guard = 1;
turns = 0;
for (int i = 0; guard && probe(i); i++)
turns++;
printf(" guard is true : probe() was called %d time(s), body ran %d times\n",
probe_calls, turns);
printf("\n[assignment inside the condition - the parentheses are the point]\n");
const char *text = "abc";
const char *p = text;
int c = 0, seen = 0, first = 0;
while ((c = *p++) != '\0') { /* store first, then compare */
if (seen == 0)
first = c;
seen++;
}
printf(" with parentheses : read %d characters, first value stored = %d ('%c')\n",
seen, first, (char)first);
p = text;
seen = 0;
first = 0;
while ((c = (*p++ != '\0'))) { /* comparing first stores only 0 or 1 */
if (seen == 0)
first = c;
seen++;
}
printf(" without parentheses: read %d characters, first value stored = %d\n",
seen, first);
printf(" the character is gone - only the truth value was kept\n");
printf(" gcc says: suggest parentheses around assignment used as truth value\n");
printf("\n[changing the counter inside the condition]\n");
int n = 3;
printf(" while (i < n) visits:");
for (int i = 0; i < n; i++)
printf(" %d", i);
printf("\n while (i++ < n) visits:");
int i = 0;
while (i++ < n)
printf(" %d", i);
printf("\n while (++i < n) visits:");
i = 0;
while (++i < n)
printf(" %d", i);
printf("\n i++ added 1 before the body saw i: 1..3 instead of 0..2,\n");
printf(" and ++i also compares the new value, so it turns one time fewer\n");
return 0;
}
Output
[the condition runs once more than the body]
body ran 5 times, limit() was called 6 times
the last call is the one that fails and ends the loop
[short-circuit can skip the side effect entirely]
guard is false: probe() was called 0 time(s)
guard is true : probe() was called 4 time(s), body ran 3 times
[assignment inside the condition - the parentheses are the point]
with parentheses : read 3 characters, first value stored = 97 ('a')
without parentheses: read 3 characters, first value stored = 1
the character is gone - only the truth value was kept
gcc says: suggest parentheses around assignment used as truth value
[changing the counter inside the condition]
while (i < n) visits: 0 1 2
while (i++ < n) visits: 1 2 3
while (++i < n) visits: 1 2
i++ added 1 before the body saw i: 1..3 instead of 0..2,
and ++i also compares the new value, so it turns one time fewer
A common misconception. “The condition just looks at true or false, so it does not matter how often it runs”
If the condition slot contains a function call, that function is called again on every turn. And the count is one higher than the body’s — the last call is the one made to answer “stop now”. The demonstration counted it: body 5, condition 6.
Put something that never changes in the condition and the whole cost is wasted. The textbook example is for (i = 0; i < strlen(s); i++), which recounts the entire string from the start for every single character (chapters 42–43). If the value does change, it is worse — it means the condition is changing state.
Side effects in the condition are not a sin in themselves. C has an idiom that depends on them.
while ((c = getchar()) != EOF) { ... } /* read, store, compare */One statement finishes “fetch the next value into a variable, then see whether it is the end marker” — a C-like sentence, and the standard library’s input loops mostly take this shape. But the parentheses are part of the grammar. Without them, while (c = getchar() != EOF) binds the comparison first, and c receives 0 or 1 instead of a character. The demonstration prints the value actually stored in each case (97 versus 1). gcc warns here — “suggest parentheses around assignment used as truth value”.
Q. If the condition has a side effect, does that effect always happen?
A. No. Because of the short-circuit evaluation of && and || (chapter 31), it may not happen at all.
for (int i = 0; guard && probe(i); i++) /* if guard is false, probe is never called */The demonstration counted the calls — when guard is false, probe() is called 0 times. Put “work that must happen” on the right-hand side of a condition and that work quietly disappears. CERT (Computer Emergency Response Team)‘s C coding standard keeps this as a rule of its own, which is how common the accident is (EXP02-C).7
As a rule: the only side effect that belongs in a condition is fetching the next value. Everything else — acquiring resources, changing state, logging — goes down into the body.
When the condition slot touches the loop variable as well, the count shifts by one.
| condition slot | values the body sees | what differs |
|---|---|---|
i < n | 0, 1, 2 | the update happens only in the update slot |
i++ < n | 1, 2, 3 | compared with the old value, but the body sees the already incremented one |
++i < n | 1, 2 | compared with the new value — one turn fewer as well |
Table 33.7 — When the condition slot touches the loop variable
The first two turn the same number of times while the values the body sees differ; the third turns one time fewer. Where they serve as an index, that one step is an access past the end of an array (chapter 39). The formal rules of side effects and evaluation order — where the boundaries are and what is undefined behavior — are the subject of chapters 34–35, the next two. From here we take only the discipline: the condition slot asks, it does not change.
33.5 Loops that never end#
An infinite loop arises in one of three ways — the update was forgotten, the update is there but some branch makes no progress, or the condition is forever true because of the type.
In practice. 31 December 2008, the day the Zune 30GB stopped
On the last day of that year, Microsoft’s Zune 30GB music players froze all over the world at once. A day later, on 1 January, they came back to life by themselves. The cause was a single loop inside the device’s clock driver — code understood to have come from its supplier, Freescale.8
while (days > 365) {
if (IsLeapYear(year)) {
if (days > 366) {
days -= 366;
year += 1;
}
} else {
days -= 365;
year += 1;
}
}The code converts a count of days since 1 January 1980 into a year, month and day. On the last day of the leap year 2008, days becomes 366. The condition days > 365 is true, so the loop is entered; it is a leap year, so control takes the upper branch; and days > 366 is false, so nothing happens. Neither days nor year changes, and back to the condition — forever.
The lesson is not about grammar but about how to think. What prevents an infinite loop is not “don’t forget the update” but asking whether every branch makes progress. That is the eye this chapter’s invariant box gave us — “what quantity is guaranteed to decrease on every turn of this loop?” Without an answer, there is no guarantee that the loop ends.
Counter-example. Ending on !=
for (int i = 0; i != n; i += 2) /* if n is odd, it steps straight past */!= stops only on exactly that value. If the step is not 1, or the body may touch the index, the loop overshoots the target and runs away. < and <= become false after overshooting too, so they catch the same mistake.
Rule: use < or <= to mark the end, and keep != for places where walking one step at a time is certain. (Sweeping an array with a pointer is such a certain place — chapter 41.)
Sometimes the type is the cause. An unsigned char cannot hold a value outside 0–255, so
for (unsigned char c = 0; c <= 255; c++) /* the condition is forever true */wraps from 255 back to 0 and never ends. Happily the compiler catches this shape — gcc says “comparison is always true due to limited range of data type” through -Wtype-limits, which -Wall -Wextra includes. Counting backwards with an unsigned index and i >= 0 belongs to the same family, and that story is in chapter 42.
A common misconception. “An infinite loop just sits there”
Not so, for two reasons.
1. It becomes a security problem. In 2022 a bug was found in OpenSSL’s BN_mod_sqrt(), which loops forever for moduli that are not prime (CVE-2022-0778, high severity).9 An attacker could tie up a server by sending a single certificate with deliberately invalid curve parameters — because parsing happens before the certificate’s signature is verified. A loop that does not end is a vulnerability by the name of denial of service.
2. The code may disappear. Since C11 the standard says that an iteration statement whose controlling expression is not a constant expression, and which performs no input/output, touches no volatile object and does no synchronization in its body, condition or update, may be assumed by the implementation to terminate.10 Optimize a loop that might not end on the assumption that it does, and the code after it can turn into code that always runs.
Measured, that is exactly what happens. The program below spins forever inside spin(1),
static unsigned spin(unsigned i) { while (i) i += 2; return i; }
int main(void) { puts("start"); spin(1); puts("done"); }| build | result | why |
|---|---|---|
gcc 14 · 16 (-O0–-O2) | hangs | the loop was left in place |
clang 22 -O0 | hangs | no optimization |
clang 22 -O1, -O2 | prints done and exits | assumed to terminate, so the loop was deleted |
while (1) { } | hangs (clang -O2) | a constant expression, so the assumption does not apply |
while (flag) { } (volatile) | hangs (clang -O2) | a volatile access excludes it |
Table 33.8 — What compilers do with a loop that may not end
The last two rows matter: the idiom “write a deliberate infinite loop as for (;;) or while (1)” rests on this. There is a reason the main loop of embedded firmware takes that shape (chapter 104).
When integer overflow joins in, the same program behaves differently at different optimization levels.
int n = 0;
for (int i = 1; i > 0; i *= 2) n++; /* signed overflow = undefined behavior */
printf("%d\n", n);Built with -O0 it prints 31 and ends; built with -O2 it never ends (measured with gcc 14). The compiler folded i > 0 to always-true on the premise that signed integers do not overflow. The answer is not wrong — the question is, and a place like this is what we call undefined behavior (chapters 28 and 54).
33.6 Nested loops — double, triple#
The body of a loop is a statement too, so another loop can go inside it. For every turn of the outer loop the inner one runs from beginning to end — which is why the turn counts are not added but multiplied.
examples-en/ch32/nested.c
/* Nested loops - double and triple, and the mistakes that nesting creates. */
#include <stdio.h>
/* 1. A double for - the inner loop restarts on every outer turn */
static void times_table(void)
{
for (int row = 2; row <= 4; row++) {
printf(" ");
for (int col = 1; col <= 5; col++)
printf("%s%2d x %d = %2d", col == 1 ? "" : " ", row, col, row * col);
printf("\n"); /* where the inner loop ends = the end of a row */
}
}
/* 2. Declare the inner counter outside and the restart disappears */
static void forgot_to_reset(void)
{
int visits = 0;
int col = 1; /* the initialization is outside */
for (int row = 2; row <= 4; row++)
for (; col <= 5; col++) /* from the second turn on, col is already 6 */
visits++;
printf(" counter declared outside : %d cells visited\n", visits);
visits = 0;
for (int row = 2; row <= 4; row++)
for (int c = 1; c <= 5; c++) /* declared inside, it starts over every turn */
visits++;
printf(" counter declared inside : %d cells visited\n", visits);
}
/* 3. Raising the outer counter inside the inner loop (the shape of a real case).
A limit is added here so that it stops - real code has no such guard. */
static void wrong_counter(void)
{
int steps = 0;
for (int j = 0; j < 3; j++) {
for (int k = 0; k < 3; j++) { /* it raises j, not k */
steps++;
if (steps >= 100) /* without this line it never ends */
break;
}
if (steps >= 100)
break;
}
printf(" wrong counter (k stands still): %d steps and still not done\n", steps);
steps = 0;
for (int j = 0; j < 3; j++)
for (int k = 0; k < 3; k++)
steps++;
printf(" right counter : %d steps, 3 x 3 as intended\n", steps);
}
/* 4. A triple for - the classic way to sweep three values. Pythagorean triples. */
static void triples(int n)
{
long long tries = 0;
int found = 0;
for (int a = 1; a <= n; a++)
for (int b = a; b <= n; b++) /* starting b at a removes duplicates */
for (int c = b; c <= n; c++) {
tries++;
if (a * a + b * b == c * c) {
printf(" %2d^2 + %2d^2 = %2d^2\n", a, b, c);
found++;
}
}
printf(" n = %d: %d triple(s) found in %lld checks\n", n, found, tries);
}
int main(void)
{
printf("[a double loop - the inner one restarts every outer turn]\n");
times_table();
printf("\n[where the inner counter is declared decides whether it restarts]\n");
forgot_to_reset();
printf("\n[raising the wrong counter in the inner loop]\n");
wrong_counter();
printf("\n[a triple loop - Pythagorean triples up to n]\n");
triples(20);
printf("\n[how fast the work grows]\n");
for (int n = 10; n <= 40; n *= 2) {
long long steps = 0;
for (int a = 1; a <= n; a++)
for (int b = 1; b <= n; b++)
for (int c = 1; c <= n; c++)
steps++;
printf(" n = %2d -> %lld steps (n^3)\n", n, steps);
}
return 0;
}
Output
[a double loop - the inner one restarts every outer turn]
2 x 1 = 2 2 x 2 = 4 2 x 3 = 6 2 x 4 = 8 2 x 5 = 10
3 x 1 = 3 3 x 2 = 6 3 x 3 = 9 3 x 4 = 12 3 x 5 = 15
4 x 1 = 4 4 x 2 = 8 4 x 3 = 12 4 x 4 = 16 4 x 5 = 20
[where the inner counter is declared decides whether it restarts]
counter declared outside : 5 cells visited
counter declared inside : 15 cells visited
[raising the wrong counter in the inner loop]
wrong counter (k stands still): 100 steps and still not done
right counter : 9 steps, 3 x 3 as intended
[a triple loop - Pythagorean triples up to n]
3^2 + 4^2 = 5^2
5^2 + 12^2 = 13^2
6^2 + 8^2 = 10^2
8^2 + 15^2 = 17^2
9^2 + 12^2 = 15^2
12^2 + 16^2 = 20^2
n = 20: 6 triple(s) found in 1540 checks
[how fast the work grows]
n = 10 -> 1000 steps (n^3)
n = 20 -> 8000 steps (n^3)
n = 40 -> 64000 steps (n^3)
The demonstration’s double loop prints a multiplication table. There is one trick to reading it — where the inner loop ends is where a row ends, and the newline sits at that spot.
With a third layer the multiplication becomes the cost. The demonstration finds Pythagorean triples () three levels deep, and at it looks at 1,540 combinations. The number of steps grows as — 1,000 at 10, 8,000 at 20, 64,000 at 40. Every added layer multiplies the cost by another factor, and that sense is the first thing to acquire about nesting. (This is why the demonstration starts the second loop at b = a and the third at c = b — it never looks at the same combination twice. The first optimization of a nested loop is usually just this: shrink the range.)
Nesting brings four mistakes that did not exist before.
| mistake | what happens | prevention |
|---|---|---|
| inner counter declared outside | from the second turn on, the inner loop does not restart. In the demonstration 15 cells became 5 | declare a counter in the first slot of the loop that uses it |
| inner loop updates the outer counter | the inner loop stands still, or the outer one skips | see the real case below |
| both loops use the same name | the inner shadows the outer, so the outer loop’s value vanishes inside the body | use names that mean something — row, col — instead of i and j |
using break to shed two layers | break sheds one layer only | the four methods in chapter 42 |
Table 33.9 — The mistakes that appear once loops are nested
In practice. Doom 3′s j and k
The Doom 3 source that id Software released in 2011 contains this double loop (neo/idlib/geometry/Surface_Polytope.cpp, line 65).
for ( j = 0; j < w.GetNumPoints(); j++ ) {
for ( k = 0; k < verts.Num(); j++ ) { /* should be k++ */The inner loop raises the outer j instead of its own k. Static analyzers keep a dedicated diagnostic for this shape, which is how common it is (PVS-Studio V533).11 The inner break usually fired first, so nothing showed — but the logic was already wrong; the same file in the BFG edition released the following year has k++.
The value of the case is that eyes cannot catch this kind of thing. It is one character. Which is why naming for meaning becomes a discipline — row, col, vert would have made it visible.
Q. In a double loop, which one should be on the outside?
A. By result, usually either. By speed, not. The order in which data is laid out in memory has to match the order in which you walk it, or the cache cannot make good use of what it fetched (chapter 12). The rule fits in one line — let the innermost loop move the most tightly through memory.
Using that rule for real means knowing “in what order does this lie in memory”, and that is the story of arrays with several layers (chapter 40). So traversal order and its measurement — the table where the same computation differs by up to eightfold — are in chapter 42, together with how to leave several layers of loop at once and where goto is legitimate.
33.7 The reunion — Duff’s device#
Time to meet the legend booked in chapter 13. We now know both switch’s fall-through (chapter 32) and the loop (this chapter).
In 1983 Tom Duff of Lucasfilm was struggling with a loop copying data to a device that was too slow. To reduce the housekeeping cost of each turn (checking the condition, updating) he processed eight at a time (unrolling) — and solved the handling of the remainder, when the count was not a multiple of eight, in a way nobody had imagined:
switch (count % 8) {
case 0: do { *to = *from++;
case 7: *to = *from++;
case 6: *to = *from++;
case 5: *to = *from++;
case 4: *to = *from++;
case 3: *to = *from++;
case 2: *to = *from++;
case 1: *to = *from++;
} while ((count -= 8) > 0);
}(The *to and *from++ parts are chapter 36′s pointer syntax, so for now look only at the outward shape — the point is the structure.) How to read it: the switch jumps into the middle of a loop. Remember chapter 32′s fact that a case is only a label — a label stamped inside the body of a do-while is not a grammatical violation. The first entry jumps to the point that processes just the remainder, and thereafter the do-while turns the whole eight-line body. Remainder handling and unrolling became one body.
Duff himself left the remark that on discovering it he felt “a mixture of pride and revulsion”, and the code stands as a monument, on the boundary of legality and grotesquerie, to the flexibility (or perhaps the looseness) of C’s grammar. And today’s lesson is exactly as chapter 13 foretold — this acrobatics is no longer a human’s job. A modern compiler unrolls an ordinarily written loop by itself (chapter 14′s editor). Admire Duff’s device as a masterpiece in the museum, and write our own loops plainly and readably like the demonstration’s for — that is modern C.
With repetition the tools of flow are complete — sequence (chapter 20), branch (chapter 32), repetition (chapter 33). The next chapter closes Part VI by digging into the meaning of that device the function — how values cross over, what exactly a side effect is, and the formal answer to the seed planted in chapter 21 (the order of evaluation).
(The remaining techniques of loops — matching traversal order to the cache by measurement, the four ways to shed several layers at once, the two places where goto is legitimate, the do { } while (0) that makes a macro one statement, and idioms such as walking backwards — need arrays and macros first, so they are gathered in chapter 42.)
Notes
- Joshua Bloch. Extra, Extra — Read All About It: Nearly All Binary Searches and Mergesorts are Broken. Google Research Blog, 2006-06-02. The same defect sat in several standard libraries and textbooks at once. ↩
- ISO/IEC 9899 (C23) 6.8.6.4, paragraph 1. Draft N3220. ↩
- ISO/IEC 9899 (C23) 6.2.4, paragraphs 5–6. ↩
- ISO/IEC 9899 (C23) 6.8.1. An iteration statement is a primary block and the loop body a secondary block: “whenever a block B appears in the syntax production as part of the definition of an enclosing block A, scopes of identifiers and lifetimes of objects that are associated with B do not extend to the parts of A that are outside of B.” ↩
- ISO/IEC 9899:2011 (C11) 6.8.5 Iteration statements, constraint 3. Draft N1570.
open-std.org/jtc1/sc22/wg14/www/docs/n1570.pdf↩ - N3078: Comment response for GB-125, WG14, 2023.
open-std.org/jtc1/sc22/wg14/www/docs/n3078.htm↩ - EXP02-C. Be aware of the short-circuit behavior of the logical AND and OR operators. SEI CERT C Coding Standard, Carnegie Mellon University.
wiki.sei.cmu.edu↩ - Brian Hayes. The Zune bug. bit-player, 2009-01-02.
bit-player.org/2009/the-zune-bugThe snippet is from the driver source as published at the time. ↩ - CVE-2022-0778: Infinite loop in
BN_mod_sqrt()reachable when parsing certificates. OpenSSL Security Advisory, 2022-03-15.openssl-library.org/news/secadv/20220315.txt↩ - ISO/IEC 9899 (C23) 6.8.6.1, paragraph 4. Draft N3220. Its footnote states the intent: “to allow compiler transformations such as removal of empty loops even when termination cannot be proven.” ↩
- PVS-Studio. Analyzing the Doom 3 source code, 2011.
pvs-studio.com/en/blog/posts/cpp/0120/Diagnostic V533 = “it is likely that a wrong variable is being incremented inside theforoperator”. ↩