Generating Data in C

Part II · Module 22 · Chapter 22.8 · Generating Data in C

1. An Import With No Input

Every import in this module so far has been asked a question about something the testbench already had. This one is asked to produce — a payload, an address, a delay, a packet's worth of stimulus — and that removes the thing all the previous chapters leaned on.

There is no input to be a function of. next_byte() called twice must give two different answers or it is useless, so it cannot be tested by calling it and comparing against an expected value.

What replaces that is reproducibility: the same run, repeated, must produce the same data. Chapter 22.7 gave up per-call testability for state and got it back by giving every test its own handle. This chapter does the same thing for randomness, and the measurement shows the obvious version of it does not work.

2. The Generator Belongs in Your Source

First decision, and it is not about randomness quality.

Measured, the library generator on this machine:

  rand() first five here: 207482415 1790989824 2035175616 77048696 24794531
  RAND_MAX here = 2147483647

Those five numbers are correct, reproducible on this machine, and worth nothing as a contract. From the C standard, neither the algorithm behind rand nor the value of RAND_MAX is specified — an implementation may use any generator and any maximum. So that sequence is a property of this C library, not of the seed, and a colleague running the same test with the same seed on a different toolchain gets different stimulus.

The fix is the one Chapter 22.4 §3 used for the CRC: put the algorithm in your own file.

typedef struct { uint64_t s; } rng;

uint64_t rng_next(rng *r) {
    uint64_t x = r->s;
    x ^= x >> 12; x ^= x << 25; x ^= x >> 27;
    r->s = x;
    return x * UINT64_C(0x2545F4914F6CDD1D);
}

Twelve lines, Chapter 15.3's shifts, and now the sequence belongs to the file. Anyone with the source reproduces it exactly, on any conforming implementation, forever.

Measured, the basic promises:

  two generators seeded 12345, 1000 draws each: identical: yes
  first five draws: 9857FB32C9EFB5E4 C0CEBA4B4A71BCE4 1399CE5B8ADB52C4 …
  seeds 12345 vs 12346: 1000 of 1000 draws differ

Both hold. A seed reproduces a sequence, and a different seed gives a different one.

3. The Finding: What Seeding Does Not Guarantee

Here is the property people actually rely on, stated as they would state it:

"The run recorded its seed, so every component will see the same stimulus if I run it again."

Measured, one generator with two consumers taking turns:

  one consumer, draws 0..5 : 9857FB32C9EFB5E4 C0CEBA4B4A71BCE4 ...
  two consumers taking turns from the SAME generator:
    consumer 1 got        : 9857FB32C9EFB5E4 1399CE5B8ADB52C4 ...
    consumer 1's values are draws 0, 2, 4 -- same seed, different stream

Consumer 1 received draws 0, 2 and 4. Same seed, same generator, same algorithm — and a different sequence than it saw when running alone.

Nothing is wrong with the generator. The sequence it produced is identical in both runs; what changed is which draws went to whom, and that is decided by the order the consumers happened to ask — which depends on scheduling, on how many transactions each component processed, on a conditional somewhere that took the other branch.

So the precise statement:

A seed reproduces the generator's sequence. It does not reproduce any consumer's sequence, because the split between consumers is decided by the order of consumption, and the seed does not capture that.

And the fix is Chapter 22.7's, in the same shape. Measured, one generator per consumer:

  consumer 1 with its own generator reproduces the solo sequence: yes

Give each consumer its own rng, seed each one from the run's master seed plus a per-consumer constant, and every consumer's stream becomes independent of what every other consumer did.

4. Bounded Draws

A model rarely wants a 64-bit number; it wants a value below some bound — a length, an index, a delay. The obvious version has a flaw:

uint32_t v = (uint32_t)(rng_next(r) >> 32);
return v % bound;                    /* biased */

If bound does not divide 2³² exactly, the low residues occur once more often than the high ones. The fix is to reject the values that cause it:

uint32_t limit = (uint32_t)(UINT32_MAX - (UINT32_MAX % bound));
for (;;) { uint32_t v = (uint32_t)(rng_next(r) >> 32); if (v < limit) return v % bound; }

Measured, 600,000 draws below 6:

  600000 draws below 6: 99409 100435 100515 99701 100193 99747
  spread 1106 (1.106% of the 100000 expected)

Flat, as expected. And the next section is why that sentence should not be read as a confirmation.

5. The Limit of This Chapter's Own Measurement

The histogram above looks like evidence that the rejection loop works. It is not, and saying so is the most useful thing in the chapter.

Computed, the size of the bias the loop removes:

  2^32 mod 6 = 4  -> 4 of 4294967296 values are over-represented
  relative bias ~ 9.3e-10
  expected excess over 600000 draws: 0.0006 counts
  measured spread between buckets: 1106

The bias is seven orders of magnitude below the noise. A naive % 6 would have produced a histogram indistinguishable from the measured one — not similar, indistinguishable, because the effect is four ten-thousandths of a count against a spread of eleven hundred.

So the flat histogram confirms that the generator is not grossly broken, which is worth knowing, and says nothing whatever about modulo bias. The rejection loop is justified by the arithmetic, not by the measurement.

This module has spent eight chapters measuring things, so it is the right place to be precise about what measurement is for:

A measurement answers the question it is sensitive to. Before accepting a result as confirmation, ask how large the effect would be if the thing you are worried about were present, and whether this experiment could see it. Here it could not, by a factor of ten million.

That is the same discipline as Chapter 22.5 §5's — a round trip answers "are these consistent?" rather than "are these correct?" — and Chapter 21.6 §4's, where a sum cannot detect a permutation. Three chapters, three checks that pass for reasons unrelated to the property being claimed.

6. The Misconception: We Record the Seed, So Failures Are Reproducible

"Every run logs its seed. Any failure can be reproduced by re-running with it."

Measured false whenever consumers share a generator. §3: consumer 1 got draws 0, 2 and 4, and it would have got draws 0, 1 and 2 had it been running alone. The seed was identical in both cases.

What the seed fixes is the generator's sequence. What a consumer receives is that sequence split among the consumers by the order they asked — and that order is decided by things the seed has no influence over:

• how many transactions each component happened to process before the failure
• a conditional that took a different branch because a timeout expired differently
• the order two components were constructed in, which can change with an unrelated edit

Re-run with the same seed after any of those shifts and every consumer gets a different stream, so the failing condition does not recur — which is experienced as "the bug went away" rather than as a reproducibility problem, and gets filed as intermittent.

The accurate position:

A seed makes a run reproducible only if every consumer's draws are independent of every other consumer's behaviour. Give each consumer its own generator, derive its seed from the master by a written rule, and the seed becomes the complete recipe it was supposed to be.

And the honest limit: if the model genuinely has one consumer, a single generator is correct and per-consumer generators are ceremony. The test is Chapter 22.7 §6's, unchanged: could two of them ever be alive at once?

7. What You Should Be Able to Say Now

1. A generating import has no input to be a function of — reproducibility replaces per-call testability.
2. Put the algorithm in your own source. Measured: RAND_MAX here is 2147483647 and the standard fixes neither it nor the algorithm, so a library sequence belongs to the library.
3. Measured, the basic promises hold: same seed → 1000 identical draws; different seed → 1000 of 1000 differ.
4. The finding: a seed does not reproduce a consumer's sequence — measured, consumer 1 got draws 0, 2 and 4 from a shared generator.
5. The order of consumption is part of the result, and nothing records it.
6. One generator per consumer fixes it — measured, the solo sequence reproduced exactly. Same shape as Chapter 22.7.
7. Bounded draws need rejection sampling, not a modulo.
8. And the histogram cannot show that — computed, the bias at bound 6 is 9.3e-10, an expected excess of 0.0006 counts against a measured spread of 1106.
9. A measurement answers the question it is sensitive to — ask how big the effect would be before reading a pass as confirmation.
10. Reproducibility is a property of the report: the master seed, the per-consumer rule, the generator's source, and nothing ambient.
11. "We record the seed" is false reassurance when consumers share a generator — the failure files itself as intermittent.

8. Exercises

1. Write a small generator in your own source and confirm two instances seeded alike produce identical draws. Why is this stronger than using the library's?
2. Print RAND_MAX on two different machines or toolchains. What does the comparison tell you about a seed recorded in a bug report?
3. Have two consumers draw alternately from one generator. Which draws does the first receive? Now give each its own and compare.
4. Describe a change to a testbench that would alter the order of consumption without changing anything about the generator or the seed.
5. Implement both the naive modulo and the rejection loop for a bound of 6. Could you distinguish them from a histogram of a million draws? Compute the expected difference first.
6. §5 says a measurement answers the question it is sensitive to. Find a passing check in your own work and compute how large the defect would have to be for it to fail.
7. Write the reproduction recipe for a failing run of a model you know. What would a colleague need beyond the seed?
8. For a generating import you have seen, apply Chapter 22.7 §6's test: could two consumers ever be alive at once?

9. Module 22 in One Page

Eight chapters from one premise: a C function called from a testbench is ordinary C reached through a connection, and nearly everything that goes wrong is on one side or the other of that sentence.

• The smallest import, broken four ways — three failures refuse to run or abort, and the one that exits 0 is the only one that returns a wrong number. A disconnected function returns zero, so never confirm an import with a test whose right answer could be zero (22.1).
• A returned value is narrowed by what you wrote, not by what you declared — measured, the declaration delivered 300 at every declared width, while a cast and an 8-bit destination both gave 44. Signedness is decided on landing: 0xff is 255 or -1 (22.2).
• An output argument is a place, not a value — and an unwritten one keeps the caller's previous answer, measured as 3 after a good call, where an unwritten return value is a conspicuous 0 (22.3).
• A CRC is the canonical first import because it can be checked — measured 0xF4 and 0x29B1 against published values, from one crc.c compiled into a plain binary and into a simulation (22.4).
• A pair checked against itself proves consistency, not correctness — measured, a symmetric bug round-tripped 16 of 16 while every codeword was wrong (22.5).
• A buffer handed over to be written adds capacity and overlap — measured, a shift in the wrong direction gave six copies of the first byte, in bounds, with nothing reported (22.6).
• State makes the identity the design — measured, all three designs give 0x52 for one stream, and only a C-issued handle can refuse an identity it never issued (22.7).
• And a seed reproduces a generator, not a consumer — measured, draws 0, 2 and 4 (22.8).

Two threads run through all eight. The first is Module 21's, unchanged: every one of these failures compiles and most of them return a plausible number, so the defence is a decision rather than a flag. The second is new, and it is what the measurements in this module kept producing: the test that confirms a thing is usually the test that cannot distinguish it from its most likely failure — zero from a disconnected function, one stream from three state designs, a round trip from a symmetric bug, a flat histogram from a biased draw. Choosing a check that could fail is most of the work.

Every chapter here has had the testbench asking and the C answering. The direction reverses next: what it means for a C model to call back into the simulator, which scope it re-enters when it does, and the hard limit on what a function called from SystemVerilog is allowed to do with simulation time.