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 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).

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

help lists all command with their help text.

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. Cursor queries are highly efficient.

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.

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.

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, run `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`.

Measured performance

202MB (some 12M lines) Verilator VCD on a 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.