Chapter 5. Arrays, Strings, and Matrices: n, n², n³

Learning objectives

After this chapter you should be able to:

Do unaided:

Draw one- and two-dimensional arrays in memory and convert m[i][j] to its row-major index and byte offset.
Trace every byte of a C string, terminator included, through strcpy, strcat, strncpy and snprintf, and compute the buffer size an operation needs.
Write a bounded string copy and a line parser using fgets and strtol with full error checking.
Recognize a buffer overflow, name it as CWE-787 or CWE-120, and read the first lines of the AddressSanitizer report.
Count the operations of single, double and triple loops, predict their growth when n doubles, and check the prediction with a timing run.

May delegate:

A tutor review of your string code against your CWE checklist, after you have run the checklist yourself.
An agent-written version of a PA1 function, used only as comparison material, never submitted.

Opening case

A composite case, not a real student or course.

Sam is still working on the field station's display code. The logger's small screen shows eight characters per line, so Sam's display row holds char name[8]. Some sensor names in the configuration file are longer: PRESSURE-03, HUMIDITY-02. Sam knows strcpy is dangerous and asks the tutor for "a safe way to copy a sensor name into an 8-byte field."

The chapter continues from here.

The loop in this chapter

Open a step to see what it asks of you and how it plays out in the Tutor phase.

Predictthe bytes after two strncpy calls, with a confidence; each kernel's slowdown when n doubles.

Step 1 of 6 · You, no AI

What you hand in: A written prediction: the output, the memory state, the operation count, and how sure you are.

Why this step: A prediction written before the run is the only way to learn whether your model of the machine is right. A miss is the most useful result there is, because it shows exactly where the model is wrong.

The first prediction is never delegated.

Ask yourself: What will this print, what will memory look like when it ends, and how many operations will it take?

Log the prediction in your work log · Predict in every chapter · ← Predict in Chapter 4 · Predict in Chapter 6 →
Writea bounded string copy and the PA1 functions by hand, edge-case tests first.

Step 2 of 6 · You, no AI

What you hand in: One small piece written by hand, to build the mental model.

Why this step: You can only check what you could have built. Writing a small piece yourself gives you the model you will need to judge the agent's version later.

Ask yourself: Could I write this piece again tomorrow without notes?

Browse the companion code · Write in every chapter · ← Write in Chapter 4 · Write in Chapter 6 →
Specifythe PA1 edge cases (negative, zero, NaN, non-convergence, float equality, overflow) in a table and in each function's comment, plus the question for the tutor.

Step 3 of 6 · You

What you hand in: The header or class interface, unit tests, a complexity budget and the ownership rules.

Why this step: The specification is the contract the code will be held to. Tests written first, a cost budget and ownership rules turn "looks right" into something you can check.

Tutor In the Tutor phase you specify a question instead of code: what you want explained, quizzed or drilled.

The ownership and lifetime section of a specification is never delegated.

Ask yourself: Who allocates, who frees, what does it cost, and what input would break it?

Prompt and specification templates · Specify in every chapter · ← Specify in Chapter 4 · Specify in Chapter 6 →
Delegatea tutor review against your CWE checklist; an agent's PA1 version as comparison material, never submitted.

Step 4 of 6 · The agent

What you hand in: The implementation from your specification, or an explanation in the Tutor phase, with the prompts and transcript saved.

Why this step: The agent does the typing; you keep the judgment. Saving the prompts and the transcript makes the delegation something you can audit afterward.

Tutor Tutor phase: the agent explains, quizzes and makes practice problems. It writes no code you submit.

Ask yourself: Did I hand over my specification and tests, and did I save what the agent said?

Prompt templates · Delegate in every chapter · ← Delegate in Chapter 4 · Delegate in Chapter 6 →
AuditASan, UBSan, gdb x/8cb, edge-case tests with timeout, an -O2 run, and the timing plot against your counts, in the PA1 Audit Report.

Step 5 of 6 · You and the tools

What you hand in: The Audit Report: tests, sanitizer and Valgrind output, your own cost derivation against a timing plot, the defects found, and a keep-or-rewrite decision.

Why this step: What the agent says is testimony until an instrument confirms it. Tests, sanitizers, Valgrind and a timing plot are evidence.

Tutor In the Tutor phase the audit checks the tutor's claims as well as your own code.

The final judgment that the code is correct is never delegated.

Ask yourself: What did the sanitizer report, does the timing plot match my derivation, and would I keep this code or rewrite it?

The Audit Report template · Audit in every chapter · ← Audit in Chapter 4 · Audit in Chapter 6 →
Defendyour version against the agent's, and the plot's departures from n, n² and n³.

Step 6 of 6 · You, live

What you hand in: A five-minute oral defense.

Why this step: If you can explain it live, you own it. The oral checks that the understanding is yours and not the agent's.

Ask yourself: Why this bound, what input breaks it, and where is this memory freed?

How the loop works · Defend in every chapter · ← Defend in Chapter 4 · Defend in Chapter 6 →

What agents get wrong here

Patterns observed in agent-written code, to test for, not guarantees. If the agent no longer makes the mistake, your job is to prove it got it right, with the same instrument.

Pre-2011 string code: strcpy, strcat, sprintf, bare %s, strncpy as "safe"

How to catch it Search for each; run every hit with an input one character too long under ASan

Section 5.3.1 · AddressSanitizer

Buffers sized without the terminator; <= loops; > where >= belongs

How to catch it Tests at exactly capacity − 1 and capacity characters

Section 5.3.2 · Tests

Matrix loops whose inner index walks down a column of a row-major array

How to catch it Name each inner index's stride; time both loop orders above cache size

Section 5.3.3 · Timing and log-log plots, Your own trace

Happy-path numerics: no iteration cap, overflow "detected" after it happens, no check of n

How to catch it Edge tests written first; timeout 3; rerun at -O2 without sanitizers

Section 5.3.4 · Tests, Timing and log-log plots

What the chapter covers

5.1 The concept, by hand
- 5.1.1 Arrays in memory
- 5.1.2 Strings and the terminator
- 5.1.3 The string library and its traps
- 5.1.4 Buffer overflow as a security bug
- 5.1.5 Bounded functions: snprintf, fgets, strtol
- 5.1.6 Matrices in row-major order
- 5.1.7 A brief, honest note on the cache
- 5.1.8 Counting n, n², n³
5.2 Predict and check
5.3 What agents get wrong here
- 5.3.1 Code from before 2011
- 5.3.2 Off by one on the terminator
- 5.3.3 Column-order loops that thrash the cache
- 5.3.4 Happy-path numerics in PA1
5.4 Working with the agent
5.5 Lab: n, n², n³, and PA1 on the edges
- 5.5.1 A filled Audit Report for PA1
5.6 Defend it

Cost thread

You counted n additions, n(n − 1)/2 comparisons and n³ multiply-adds: for n = 4, that is 4, 6 and 64; for n = 1,000, it is 1,000, 499,500 and one billion. Doubling n multiplies the work by 2, about 4 and 8. Then you measured. In the run shown, the timing matched the pairs count almost exactly, matched the sum after one noisy step, and left the matrix count once its data outgrew the cache. That is the normal relation: the count gives the shape, and the timing shows whether something the count ignores has changed the cost per operation. Chapter 8 puts such data on a log-log plot, and Chapter 10 makes the counting formal.

Summary

A C array is a fixed run of same-typed elements with no stored length and no bounds check.
A C string ends at its terminator: length L needs L + 1 bytes, and strlen counts only L.
strcpy, strcat and gets copy without checking size (CWE-120, a form of CWE-787), and strncpy can leave a string unterminated; snprintf, fgets and fully checked strtol replace them.
ASan catches a one-byte overflow at the exact byte, while the unsanitized program may print the right answer.
In row-major order m[i][j] is at i * cols + j, and column-order traversal of a large matrix measured 6 to 12 times slower here.
Counts of n, n², n³ predicted 2×, 4×, 8× per doubling; the timing confirmed two and showed the third breaking away when memory behavior changed.

Key terms

array: a fixed number of same-typed elements stored contiguously, with no stored length.
C string: an array of char holding characters followed by a terminator.
terminator: the zero byte '\0' that ends a C string.
buffer overflow: a read or write outside the bounds of a buffer.
CWE-787: out-of-bounds write, writing outside the intended buffer.
CWE-120: classic buffer overflow, copying input without checking that it fits.
bounded function: a function that takes the destination's capacity and never writes beyond it.
truncation: output cut short to fit a buffer, which a correct program reports.
row-major order: storing a matrix row after row, so m[i][j] is at i * cols + j.
stride: the distance in bytes between consecutive accesses in a loop.
cache line: the block, typically 64 bytes, in which data moves into the processor's cache.
timing plot: run time plotted against input size to check a predicted growth rate.

Companion code

6 files for this chapter, compiled with the book's flags.

Read the code Download ch05.zip

Connections

Where this chapter and another point to each other most often.

Chapter 2: The Working Loop
PA link. Completes PA1; the Audit Report is graded with it. ### 5.5.1 A filled Audit Report for PA1 This is the book's first complete Audit Report, in the seven parts from Chapter 2 (template in Appendix A): a composite, as Maya might write it, trimmed to three functions.
Chapter 3: Control Flow, Functions, Recursion, and Counting Operations
Cache design beyond that is outside this course. ### 5.1.8 Counting n, n², n³ Chapter 3 counted loop iterations.
Chapter 4: Pointers
Passed to a function, it decays to a pointer (Chapter 4), which is why every C function that takes an array also takes its length.
Chapter 6: The Stack and the Heap: Dynamic Memory and Ownership
Chapter 6 shows how to get such an array from the heap. ### 5.1.7 A brief, honest note on the cache Operation counts treat every memory access as equal.
Chapter 9: Files, Bits, and Function Pointers: ADTs Behind a Header
strtol reports everything, if you look: end == s means no digits; errno == ERANGE means the value does not fit (errno, from <errno.h>, is a global error code that library functions set on failure; set it to 0 before the call, and see Chapter 9 for more); anything but whitespace after end is trailing junk.
Chapter 12: Moving to C++: Is It Really C++?
From Chapter 12: And the C original filled name with snprintf; the port uses strcpy, the unbounded copy Chapter 5 warned about.

See it on the map

05 Arrays, Strings, and Matrices: n, n², n³