libwave

libwave is the engine for a waveform-based replay debugger.

The problem

A VCD is a clock-major event log containing something along the lines of "at time T, these signals changed." Most things a debugger is concerned about are signal-major, such as breakpoint conditions which are checked constantly. Dumping memory, however, is clock-major and deserves to be handled well.

The solution

Short version: signal-major change streams are stored inside time-based blocks. Every signal carries a sorted occupancy list that tells you in which blocks it changed.

1. Transpose once

Conversion transposes the VCD into per-signal change lists: for each signal, a sorted array of step indexes and a parallel array of values. Everything a debugger does becomes an array operation:

query	mechanism	cost
value(sig, t)	binary search	O(log n)
next / previous change	index +/- 1	O(1)
step / reverse-step	cursor walk	O(1) amortized
"break when X == v"	scan X's list only	O(changes of X)
condition over k signals	k-way cursor merge	O(sum of changes)

2. Divide into blocks

The time axis is chunked into blocks of 2^block_shift steps (default 2^16). Within a block, changes are grouped by signal. This bounds memory at ingest, the converter holds one block of changes plus O(signals) state. The sparsity allows queries to only touch signals they need.

3. Occupancy lists

libwave does not snapshot all signal values at block boundaries. Instead, each signal carries an occupancy list: the ordered set of blocks in which it changed, along with a change count.

value(sig, T): find the signal's last occupied block <= block(T). If it's an earlier block, the answer is that block's last change. We don't need a snapshot, and we can skip over all irrelevant intermediate blocks.

4. mmap

Every struct contains offsets instead of pointers, has 8-byte alignment, and a fixed stride. Linux gets us lazy lookup and caching for free.

Compression is possible. dirent.z_size and header.z_level are reserved. Per-stream zstd is planned, but that doesn't affect the API either way.

5. Two-state fast path, exact four-state semantics

Values are packed little-endian at stride = ceil(width/8) bytes. x/z bits are stored as 0. Changes carrying x/z are listed in a per-stream sorted exception array (in-block change index + x-mask + z-mask). A pure 2-state dump doesn't pay anything for 4-state support. x/z-heavy regions pay in proportion to their x/z density.

6. Only steps are stored

Change lists don't store simulation time. A global table maps step index to VCD time units, and when the dump sits on a regular grid (as is the case for single clock domain synchronous designs) the table collapses to zero. It's only materialized on the first irregular delta.

7. Deduplication

We dedup identity and changes.

• Vars sharing a VCD identifier map to one stored signal. The name/hierarchy tables are only for presentation.
• In case there are redundant changes in the VCD, they're dropped.
• Multiple changes of one signal within one time step keep only the final value.

Usage

Converting and interrogating dumps:

wave convert wave.vcd wave.wst [--block-shift N]
wave info wave.wst                       # stats, busiest signals
wave ls wave.wst [prefix]                # list vars
wave get wave.wst u_cpu.pc 2.5ms         # value + neighboring changes
wave changes wave.wst u_cpu.pc --from @1000 --limit 20
wave when wave.wst u_cpu.pc 0x4f2        # proto-breakpoint scan
wave mem wave.wst tb.g_arr 5.1ms         # array/memory table at a time
wave verify wave.wst design.vcd          # replay VCD, cross-check store
wave bench wave.wst                      # query microbenchmarks
wave debug wave.wst                      # interactive debugger (below)

Times are raw VCD units, suffixed reals (500ns, 12.5us), or @step. Signal paths are full hierarchical names or any unique suffix.

Structurally, wave is a thin wrapper over the library (libwave.hpp). wave mem is a prototype: it groups prefix[i] vars and renders them at a chosen step.

The debugger

wave debug is the proof of concept for the replay debugger. It's GDB-like:

(wave) b u_cpu.pc == 0x46          # value condition; b SIG alone = any change
bp 1: break tb_soc_long.u_cpu.pc == 0x46
(wave) c
bp 1: tb_soc_long.u_cpu.pc == 0x46
stopped at @42667 (t=213335000, 213.335 us)
(wave) rc                          # reverse-continue

Commands: s/rs step either direction, c/rc continue either direction, g jumps to a time, p/display/mem inspect state, changed lists the signals with a change at the current step, l shows a signal's changes around the position, help has the full list.

How it maps onto the library:

• continue seeks a merge_scan to the current step and walks the union of the breakpoint signals' change lists.
• reverse-continue is a mirrored cursor walk (bwd_scan in debug.cpp): take the max step among cursors, read values, step the movers back with prev(). Reverse costs the same as forward.
• conditions compare the low 64 value bits: x/z bits read as 0 and a signal reads as 0 before its first change. Exact 4-state inspection is in p/display.
• changed asks the block directory which streams contain the current step (sigs_changed_at).

API

#include "libwave.hpp"

libwave::wave w("wave.wst");                   // mmap

// hierarchy
auto vi = w.find_var("u_cpu.pc");              // unique-suffix or full path
uint32_t sig = w.vars()[*vi].signal;

// time
uint64_t step = w.step_at_time(t_units);       // last step at/before t
uint64_t t = w.step_time(step);                // VCD units; *_fs for fs
auto s2 = w.parse_step("12.5us", &err);        // "@N" | "500ns" | raw units

// point queries
libwave::value v = w.value(sig, step);         // last change at/before step
v.valid;                                       // false => before first change (all x)
v.u64(); v.bits; v.has_xz(); v.xmask; v.zmask; // pointers into the mapping
int64_t g  = w.change_at(sig, step);           // global change index, -1 if none
int64_t g2 = w.change_after(sig, step);        // first change after, -1 if none
uint64_t s = w.change_step(sig, g);            // step of change #g
libwave::value u = w.value_at_change(sig, g);
auto sigs = w.sigs_changed_at(step);           // who changed at `step`
                                               // (block directory scan)

// sequential scans: cursors avoid re-probing occupancy + directory
libwave::cursor c(w, sig);
for (bool ok = c.seek_index(0); ok; ok = c.next()) {
  c.step(); c.index(); c.u64(); c.has_xz();    // fast accessors
  if (c.u64() == 0x4f2) break;                 // "breakpoint"
}
c.seek(step);                                  // position at last change <= step
c.prev();                                      // reverse-step: same cost

Cursors

A cursor is a saved position on one signal's change list: an occupancy-list position, a view of that block's stream, and an index within it.

Point queries re-run the full lookup on every call: occupancy list, block directory, in-block binary search. Scans, which visit every change of a signal, would like to avoid that.

A cursor pays the lookup once, at seek:

• next() / prev() inside a block are an index bump.
• Crossing into the signal's next occupied block re-runs one directory lookup. Blocks it never appears in are skipped by construction, since the cursor walks the occupancy list, not the block sequence.

No allocations. A cursor is a few words plus a stream view, so a compound condition can hold one per signal.

The sequential-walk and merge rows in the performance table are cursor loops. The ~80 ns point query is what each iteration would cost without one.

State machine:

• A fresh cursor is invalid. Position it with seek(step) (last change at or before step, false if the signal hasn't changed by then) or seek_index(g) (global change index, false if out of range).
• next() / prev() move one change and return false on walking off either end, which invalidates the cursor. An invalid cursor stays invalid until the next successful seek; calling accessors on it is undefined.
• While valid: step() and index() locate the change; u64() reads the low 64 value bits (x/z bits read as 0) without touching the exception array; has_xz() checks for exceptions; value() returns the full struct including masks.

Run-until on a compound condition is a k-way merge, provided by merge_scan: one cursor per signal in the condition plus a latched current value per signal. Each next() takes the smallest step among the live cursors, advances every cursor sitting at that step, and updates the latches; the caller evaluates its predicate over value(0..k-1). Each union event costs O(k) compares and touches nothing outside the k change lists. cmd_bench in src/main.cpp drives it over four signals; wave when is the one-signal version.

libwave::merge_scan m(w, {cyc, stb, we, ack});
m.seek(step);                                  // optional: start mid-dump
while (m.next()) {
  m.changed(2);                                // did `we` change this event?
  if (m.value(0) & m.value(1) & m.value(2) & m.value(3) & 1)
    break;                                     // "break at Wishbone write"
}

Codebase

src/format.hpp    on-disk format: structs + layout rules. The format
                  spec lives here; the file doubles as documentation.
src/vcd.*         streaming VCD reader. Tokenizer over a refilling 4MB
                  buffer; parses declarations eagerly, then yields
                  time/change events one at a time. Owns id-code
                  resolution (direct table when the base-94 key space
                  is small, hash map otherwise) and 4-state bit-string
                  decoding with IEEE-1364 extension rules.
src/convert.*     one-pass streaming converter. Transposes events into
                  per-signal current-block buffers, flushes each block
                  (streams + directory) as time crosses a boundary,
                  writes hierarchy/occupancy/time tables at the end,
                  then rewrites the header. Holds the cross-block dedup
                  state (last/prev value per signal).
src/libwave.*     the query engine described above, plus cursor and
                  value/time formatting helpers.
src/debug.cpp     the interactive debugger: REPL, breakpoint engine
                  (forward via merge_scan, backward via bwd_scan), and
                  the memory table shared with `wave mem`.
src/main.cpp      CLI subcommands; each is a thin wrapper over the API.
tests/run.sh      testsuite runner (see Testing below); `make check`.
tests/vcd/        corpus: every file here is converted at three block
                  shifts and replay-verified at every step.
tests/err/        malformed VCDs that must be rejected.
tests/debug/      scripted debugger sessions, piped into `wave debug`.
tests/golden/     pinned CLI outputs (regenerate: tests/run.sh --regen).
tests/coverage.sh gcov build + suite run + merged line coverage report;
                  `make coverage`.

Testing

make check runs tests/run.sh (~225 tests, ~4s). The suite's backbone is the replay oracle, which needs no expected-output files: any VCD dropped into tests/vcd/ gets converted at block shifts {1, 3, 16} and verified at every step, plus a byte-determinism check and a cross-shift change-count check.

• Replay verification (wave verify): re-reads the VCD holding complete simulator state; at sampled steps (--every N, default a prime to avoid aliasing with periodic activity) compares every signal (bits, x-mask, z-mask, validity) against store queries, plus step count/time mapping. Deliberately desynchronized store/VCD pairs (extra steps, shifted times, altered values, missing changes) must each fail with the right message.
• Corpus (tests/vcd/, 19 files): hand-written edge cases (x/z, aliases, reals, same-step re-changes, never-dumped vars, empty and timestamps-only dumps, occupancy gaps, dump-control blocks, over-wide writes, string skips, split $timescale, non-module scopes, width-mismatch aliases), two real Icarus CPU/SoC traces, and a synthesized stress set: 84k steps crossing blocks at the default shift, 4+ character id codes forcing the hash-map fallback, widths 1..1024, x/z-heavy churn, 4000 signals in 12-deep scopes, $dumpoff blackouts, an irregular fs-scale grid with 64-bit timestamps, and a 256-word memory.
• Goldens (tests/golden/, tests/run.sh --regen): pin CLI output for info/ls plus per-var change lists (capped at 400 vars x 50 changes; the oracle covers the values), selected get/mem/when outputs, and six scripted wave debug sessions covering both continue directions, edge-triggered conditions, displays, memory views, and every REPL error path.
• Malformed inputs: backwards time, over-long id codes, undeclared ids, bad value characters, stray tokens, plus corrupted stores (bad magic, version, step count, block shift, truncation, compressed flag) and CLI misuse, each asserted to fail with the right message.
• Big wave (skipped when absent): the 202MB SoC dump is converted, sample-verified, and pinned to known bench checksums plus a debugger session.
• Coverage (make coverage): instrumented build, full suite, merged per-file gcov report. Line coverage is 99.0%.
• Independent cross-check: a from-scratch Python scan of the raw VCD reproduced change lists and merge-scan results during development, sharing no code with the C++ path.
• Layout equivalence: bench checksums are identical across block sizes (2^8 vs 2^16 steps) and matched the pre-block flat prototype: three layouts, same answers.

Measured performance

202MB (some 12M lines) Verilator VCD, one Zen 4 core, default settings:

metric	result
convert	0.8s (~260 MB/s of VCD text)
store size	47MB (0.22x the VCD, no compression)
random value(sig, step)	~65 ns/query
sequential cursor walk	~540M changes/s
4-signal merge scan	~140M events/s
"break at pc == X" scan	365K changes in ~1 ms

Known limits

• 32-bit limit on time steps per store; wider needs a format revision (planned 64-bit step space with the same block structure).
• String-valued vars are skipped with a warning.
• No compression yet.