src/sprite_trace.c at rrdc-perf · doomsdayone/enhanced-x16-emulator

◆ rrdc-perf enhanced-x16-emulator / src / sprite_trace.c

17.3 KiB · C · last changed chore(): initial commit 25 days ago source blame history raw

// Commander X16 Emulator — sprite multiplexing trace. See sprite_trace.h for
// the data model and why the recording is split into a renderer stream and a
// mutation stream.

#include "sprite_trace.h"

#include <stdlib.h>
#include <string.h>

#define LINE_SLOTS (SPRITE_TRACE_LINES * SPRITE_TRACE_SLOTS)

// Generations start small and double. A frame using every slot without any
// multiplexing needs 128; a 1024-sprite multiplexer needs a little over that
// many. The ceiling exists so a runaway program cannot grow the trace without
// bound -- past it, further values in a slot are folded into the last
// generation, which understates the count rather than exhausting memory.
#define GEN_CAP_INITIAL 512
#define GEN_CAP_MAX     8192

// Attribute writes kept per frame. A multiplexer rewriting 8 bytes for each of
// 1024 sprites lands 8192, so this leaves headroom. On overflow later writes
// are counted but not stored: keeping an unbroken prefix means the burst
// analysis stays valid for what was kept, which a wrapping ring would not.
#define MUTATION_CAP 16384

#define DEFAULT_BURST_GAP 128

typedef struct {
	sprite_gen_t      *gens;
	uint16_t           gen_count;
	uint16_t           gen_cap;

	sprite_mutation_t *mutations;
	uint32_t           mutation_count;
	uint32_t           mutation_dropped;

	sprite_line_stat_t lines[SPRITE_TRACE_LINES];

	uint16_t          *line_gen;    // [LINE_SLOTS] index into gens, or SPRITE_TRACE_NO_GEN
	uint8_t           *line_flags;  // [LINE_SLOTS] SPRITE_TRACE_*
	uint16_t          *line_budget; // [LINE_SLOTS] sprite-fetch cycles

	sprite_frame_summary_t summary;
} trace_buffer_t;

bool sprite_trace_active = false;

static trace_buffer_t  buffers[2];
static trace_buffer_t *recording = &buffers[0];
static trace_buffer_t *published = &buffers[1];
static bool            have_published = false;
static bool            allocated = false;

// Per-slot recording state, valid only while a frame is in progress.
static uint16_t cur_gen[SPRITE_TRACE_SLOTS];
static bool     slot_dirty[SPRITE_TRACE_SLOTS];
static uint16_t slot_dirty_line[SPRITE_TRACE_SLOTS];
static uint32_t slot_dirty_cycle[SPRITE_TRACE_SLOTS];
static uint16_t slot_dirty_writes[SPRITE_TRACE_SLOTS];

static uint32_t frame_start_cycle;
static uint32_t frame_number;
static uint32_t burst_gap = DEFAULT_BURST_GAP;

// For attributing CPU cycles to the scanline the beam was on: line_begin for
// line N+1 tells us how many cycles elapsed since line N started.
static uint16_t prev_begin_line  = SPRITE_TRACE_NO_LINE;
static uint32_t prev_begin_cycle;

static sprite_trace_frame_t public_view;

static void
buffer_free(trace_buffer_t *b)
{
	free(b->gens);
	free(b->mutations);
	free(b->line_gen);
	free(b->line_flags);
	free(b->line_budget);
	memset(b, 0, sizeof(*b));
}

static bool
buffer_alloc(trace_buffer_t *b)
{
	memset(b, 0, sizeof(*b));
	b->gen_cap     = GEN_CAP_INITIAL;
	b->gens        = (sprite_gen_t *)malloc(sizeof(sprite_gen_t) * b->gen_cap);
	b->mutations   = (sprite_mutation_t *)malloc(sizeof(sprite_mutation_t) * MUTATION_CAP);
	b->line_gen    = (uint16_t *)malloc(sizeof(uint16_t) * LINE_SLOTS);
	b->line_flags  = (uint8_t *)malloc(LINE_SLOTS);
	b->line_budget = (uint16_t *)malloc(sizeof(uint16_t) * LINE_SLOTS);
	if (!b->gens || !b->mutations || !b->line_gen || !b->line_flags || !b->line_budget) {
		buffer_free(b);
		return false;
	}
	return true;
}

// Clear a buffer for a new frame. The residency map is reset to "the renderer
// never reached this slot" rather than zero, because slot 0 is a real index.
static void
buffer_begin(trace_buffer_t *b)
{
	b->gen_count        = 0;
	b->mutation_count   = 0;
	b->mutation_dropped = 0;
	memset(&b->summary, 0, sizeof(b->summary));
	memset(b->lines, 0, sizeof(b->lines));
	memset(b->line_flags, 0, LINE_SLOTS);
	memset(b->line_budget, 0, sizeof(uint16_t) * LINE_SLOTS);
	for (int i = 0; i < LINE_SLOTS; i++) {
		b->line_gen[i] = SPRITE_TRACE_NO_GEN;
	}
	for (int i = 0; i < SPRITE_TRACE_LINES; i++) {
		b->lines[i].cut_slot = SPRITE_TRACE_NO_LINE;
	}
}

size_t
sprite_trace_memory_usage(void)
{
	if (!allocated) {
		return 0;
	}
	size_t per = sizeof(sprite_mutation_t) * MUTATION_CAP + sizeof(uint16_t) * LINE_SLOTS +
	             (size_t)LINE_SLOTS + sizeof(uint16_t) * LINE_SLOTS + sizeof(((trace_buffer_t *)0)->lines);
	return 2 * per + sizeof(sprite_gen_t) * (buffers[0].gen_cap + buffers[1].gen_cap);
}

void
sprite_trace_reset(void)
{
	have_published    = false;
	prev_begin_line   = SPRITE_TRACE_NO_LINE;
	frame_start_cycle = 0;
	frame_number      = 0;
	memset(slot_dirty, 0, sizeof(slot_dirty));
	memset(slot_dirty_writes, 0, sizeof(slot_dirty_writes));
	for (int i = 0; i < SPRITE_TRACE_SLOTS; i++) {
		cur_gen[i] = SPRITE_TRACE_NO_GEN;
	}
	if (allocated) {
		buffer_begin(recording);
		buffer_begin(published);
	}
}

bool
sprite_trace_set_enabled(bool on)
{
	if (on == sprite_trace_active) {
		return true;
	}
	if (on) {
		if (!allocated) {
			if (!buffer_alloc(&buffers[0])) {
				return false;
			}
			if (!buffer_alloc(&buffers[1])) {
				buffer_free(&buffers[0]);
				return false;
			}
			allocated = true;
		}
		recording = &buffers[0];
		published = &buffers[1];
		sprite_trace_reset();
		sprite_trace_active = true;
	} else {
		sprite_trace_active = false;
		have_published      = false;
		if (allocated) {
			buffer_free(&buffers[0]);
			buffer_free(&buffers[1]);
			allocated = false;
		}
	}
	return true;
}

void
sprite_trace_set_burst_gap(uint32_t cycles)
{
	burst_gap = cycles;
}

uint32_t
sprite_trace_get_burst_gap(void)
{
	return burst_gap;
}

// Decode the attribute bytes the way refresh_sprite_properties() does, so a
// generation carries the same interpretation the renderer used.
static void
decode_attr(sprite_gen_t *g, const uint8_t attr[8])
{
	memcpy(g->attr, attr, 8);

	g->zdepth         = (uint8_t)((attr[6] >> 2) & 3);
	g->collision_mask = (uint8_t)(attr[6] & 0xf0);
	g->hflip          = (attr[6] & 1) != 0;
	g->vflip          = ((attr[6] >> 1) & 1) != 0;

	g->x = (int16_t)(attr[2] | ((attr[3] & 3) << 8));
	g->y = (int16_t)(attr[4] | ((attr[5] & 3) << 8));

	g->width  = (uint16_t)(1u << ((((attr[7] >> 4) & 3) + 3)));
	g->height = (uint16_t)(1u << ((attr[7] >> 6) + 3));

	if (g->x >= (int16_t)(0x400 - g->width)) {
		g->x = (int16_t)(g->x - 0x400);
	}
	if (g->y >= (int16_t)(0x400 - g->height)) {
		g->y = (int16_t)(g->y - 0x400);
	}

	g->color_mode     = (uint8_t)((attr[1] >> 7) & 1);
	g->address        = (uint32_t)(attr[0] << 5 | (attr[1] & 0xf) << 13);
	g->palette_offset = (uint8_t)((attr[7] & 0x0f) << 4);
}

// Open a generation for a slot whose value the CPU changed. Returns the index,
// or the slot's existing generation if the table is full.
static uint16_t
open_gen(trace_buffer_t *b, uint8_t slot, const uint8_t attr[8])
{
	if (b->gen_count >= b->gen_cap) {
		if (b->gen_cap >= GEN_CAP_MAX) {
			return cur_gen[slot];
		}
		uint16_t     ncap = (uint16_t)(b->gen_cap * 2 > GEN_CAP_MAX ? GEN_CAP_MAX : b->gen_cap * 2);
		sprite_gen_t *ng  = (sprite_gen_t *)realloc(b->gens, sizeof(sprite_gen_t) * ncap);
		if (!ng) {
			return cur_gen[slot];
		}
		b->gens    = ng;
		b->gen_cap = ncap;
	}

	uint16_t      idx = b->gen_count++;
	sprite_gen_t *g   = &b->gens[idx];
	memset(g, 0, sizeof(*g));
	decode_attr(g, attr);
	g->slot       = slot;
	g->first_line = SPRITE_TRACE_NO_LINE;
	g->last_line  = SPRITE_TRACE_NO_LINE;

	uint16_t prev = cur_gen[slot];
	g->index_in_slot = (uint16_t)(prev == SPRITE_TRACE_NO_GEN ? 0 : b->gens[prev].index_in_slot + 1);

	return idx;
}

void
sprite_trace_note_write(uint8_t slot, uint8_t offset, uint8_t old_val, uint8_t new_val,
                        uint16_t line, uint32_t cpu_cycle)
{
	if (!sprite_trace_active || !allocated) {
		return;
	}
	slot &= (SPRITE_TRACE_SLOTS - 1);
	offset &= 7;

	trace_buffer_t *b = recording;

	b->summary.mutations++;
	if (line < SPRITE_TRACE_LINES) {
		b->summary.mutations_onscreen++;
	}

	if (b->mutation_count < MUTATION_CAP) {
		sprite_mutation_t *m = &b->mutations[b->mutation_count++];
		m->cycle             = cpu_cycle;
		m->line              = line;
		m->slot              = slot;
		m->offset            = offset;
		m->old_val           = old_val;
		m->new_val           = new_val;
	} else {
		b->mutation_dropped++;
	}

	// A write that stores the value already there costs the CPU exactly as much
	// as any other and belongs in the cost total, but it does not start a new
	// generation: nothing about what the beam will draw has changed.
	if (old_val == new_val) {
		return;
	}

	if (!slot_dirty[slot]) {
		slot_dirty[slot]        = true;
		slot_dirty_writes[slot] = 0;
	}
	// Kept as the most recent write, so the generation is stamped with the
	// moment its value became complete rather than when the update began. That
	// is the instant a late write has to be judged against.
	slot_dirty_line[slot]  = line;
	slot_dirty_cycle[slot] = cpu_cycle;
	slot_dirty_writes[slot]++;
}

void
sprite_trace_line_begin(uint16_t line, uint32_t cpu_cycle)
{
	if (!sprite_trace_active || !allocated) {
		return;
	}

	// Close out the previous line's CPU accounting before touching this one.
	// Accumulated rather than assigned: a line re-rendered by a mid-line split
	// gets begun twice, and both spans were spent with the beam on that line.
	if (prev_begin_line < SPRITE_TRACE_LINES) {
		recording->lines[prev_begin_line].cpu_cycles += cpu_cycle - prev_begin_cycle;
	}
	prev_begin_line  = line;
	prev_begin_cycle = cpu_cycle;

	if (line >= SPRITE_TRACE_LINES) {
		return;
	}

	trace_buffer_t *b   = recording;
	const size_t    off = (size_t)line * SPRITE_TRACE_SLOTS;
	for (int s = 0; s < SPRITE_TRACE_SLOTS; s++) {
		b->line_gen[off + s] = SPRITE_TRACE_NO_GEN;
	}
	memset(b->line_flags + off, 0, SPRITE_TRACE_SLOTS);
	memset(b->line_budget + off, 0, sizeof(uint16_t) * SPRITE_TRACE_SLOTS);

	uint32_t keep_cycles = b->lines[line].cpu_cycles;
	memset(&b->lines[line], 0, sizeof(b->lines[line]));
	b->lines[line].cpu_cycles = keep_cycles;
	b->lines[line].cut_slot   = SPRITE_TRACE_NO_LINE;
	b->lines[line].rendered   = true;
}

void
sprite_trace_note_slot(uint16_t line, uint8_t slot, const uint8_t attr[8],
                       uint16_t budget_used, uint8_t flags)
{
	if (!sprite_trace_active || !allocated || line >= SPRITE_TRACE_LINES) {
		return;
	}
	slot &= (SPRITE_TRACE_SLOTS - 1);

	trace_buffer_t *b = recording;

	// The renderer is reading this slot now, so now is when a pending change
	// becomes the value that was actually displayed -- half-written included.
	if (slot_dirty[slot]) {
		uint16_t idx = open_gen(b, slot, attr);
		if (idx != SPRITE_TRACE_NO_GEN) {
			sprite_gen_t *g = &b->gens[idx];
			if (idx == b->gen_count - 1) {
				g->write_line  = slot_dirty_line[slot];
				g->write_cycle = slot_dirty_cycle[slot];
				g->writes      = slot_dirty_writes[slot];
			} else {
				// Folded into the previous generation because the table is
				// full; keep its write count honest.
				g->writes = (uint16_t)(g->writes + slot_dirty_writes[slot]);
			}
			cur_gen[slot] = idx;
		}
		slot_dirty[slot]        = false;
		slot_dirty_writes[slot] = 0;
	}

	const size_t i  = (size_t)line * SPRITE_TRACE_SLOTS + slot;
	b->line_gen[i]  = cur_gen[slot];
	b->line_flags[i] = flags;
	b->line_budget[i] = budget_used;
}

void
sprite_trace_line_end(uint16_t line, const sprite_line_stat_t *result)
{
	if (!sprite_trace_active || !allocated || line >= SPRITE_TRACE_LINES || !result) {
		return;
	}
	sprite_line_stat_t *st = &recording->lines[line];
	const uint32_t      keep_cycles = st->cpu_cycles;
	*st                             = *result;
	st->cpu_cycles                  = keep_cycles;
	st->rendered                    = true;
}

// Walk the finished residency map once and turn it into per-generation totals
// and a frame summary. Done here rather than incrementally because a scanline
// can be rendered more than once and only the final pass counts.
static void
finalize(trace_buffer_t *b, uint32_t end_cycle)
{
	sprite_frame_summary_t *s = &b->summary;
	s->frame                  = frame_number;
	s->cpu_cycles             = end_cycle - frame_start_cycle;
	s->gen_count              = b->gen_count;
	s->burst_gap              = burst_gap;

	for (uint16_t line = 0; line < SPRITE_TRACE_LINES; line++) {
		const size_t off = (size_t)line * SPRITE_TRACE_SLOTS;
		for (int slot = 0; slot < SPRITE_TRACE_SLOTS; slot++) {
			uint16_t idx = b->line_gen[off + slot];
			if (idx == SPRITE_TRACE_NO_GEN || idx >= b->gen_count) {
				continue;
			}
			sprite_gen_t *g = &b->gens[idx];
			uint8_t       f = b->line_flags[off + slot];

			g->lines_resident++;
			g->budget_cycles += b->line_budget[off + slot];
			if (f & SPRITE_TRACE_CUT) {
				g->flags |= SPRITE_GEN_CUT;
			}
			if (f & SPRITE_TRACE_DREW) {
				g->flags |= SPRITE_GEN_DREW;
				g->lines_drawn++;
				if (g->first_line == SPRITE_TRACE_NO_LINE) {
					g->first_line = line;
				}
				g->last_line = line;
			}
		}
	}

	uint16_t drawn_gens_in_slot[SPRITE_TRACE_SLOTS];
	uint16_t gens_in_slot[SPRITE_TRACE_SLOTS];
	memset(drawn_gens_in_slot, 0, sizeof(drawn_gens_in_slot));
	memset(gens_in_slot, 0, sizeof(gens_in_slot));

	for (uint16_t i = 0; i < b->gen_count; i++) {
		sprite_gen_t *g = &b->gens[i];
		gens_in_slot[g->slot]++;

		if (g->flags & SPRITE_GEN_DREW) {
			s->effective_sprites++;
			drawn_gens_in_slot[g->slot]++;
		} else if (!(g->flags & SPRITE_GEN_CARRIED)) {
			s->phantom_writes++;
		}

		// Late: the value only became complete after the beam had already
		// passed the whole Y span it was meant to appear in, so nothing this
		// frame could ever have drawn it. Computed in int, because a sprite
		// parked just above the screen has a negative Y and its span ends at or
		// before line 0 -- which is late for every write, and would wrap to a
		// huge number if this were done in uint16_t.
		const int y_end = (int)g->y + (int)g->height;
		if (!(g->flags & SPRITE_GEN_CARRIED) && g->write_line < SPRITE_TRACE_LINES &&
		    g->zdepth != 0 && (int)g->write_line >= y_end) {
			g->flags |= SPRITE_GEN_LATE;
			s->late_writes++;
		}
	}

	for (int slot = 0; slot < SPRITE_TRACE_SLOTS; slot++) {
		if (drawn_gens_in_slot[slot] > 0) {
			s->slots_used++;
		}
		if (drawn_gens_in_slot[slot] > 1) {
			s->slots_multiplexed++;
		}
		if (gens_in_slot[slot] > s->max_gens_in_slot) {
			s->max_gens_in_slot = gens_in_slot[slot];
		}
	}
	s->multiplexing = s->slots_multiplexed > 0;

	for (uint16_t line = 0; line < SPRITE_TRACE_LINES; line++) {
		const sprite_line_stat_t *st = &b->lines[line];
		s->budget_used_total += st->budget_used;
		s->sprites_dropped += st->dropped;
		if (st->exhausted) {
			s->lines_exhausted++;
		}
		// Ranked by demand, not by clocks used: once several lines are over the
		// ceiling they all report the same usage, and the worst one is the one
		// that wanted the most.
		if (st->demand > s->peak_demand) {
			s->peak_demand = st->demand;
			s->peak_budget = st->budget_used;
			s->peak_line   = line;
		}
	}

	// Cluster the attribute writes into bursts. One burst is one visit to the
	// multiplexer's raster handler; the cycles it spans are what the
	// multiplexing costs the guest. It is a lower bound -- the handler's entry,
	// exit and any work after its final store fall outside the span.
	uint32_t burst_start = 0;
	uint32_t prev_cycle  = 0;
	bool     in_burst    = false;
	for (uint32_t i = 0; i < b->mutation_count; i++) {
		uint32_t c = b->mutations[i].cycle;
		if (!in_burst || c - prev_cycle > burst_gap) {
			if (in_burst) {
				s->mutation_cycles += prev_cycle - burst_start;
			}
			s->mutation_bursts++;
			burst_start = c;
			in_burst    = true;
		}
		prev_cycle = c;
	}
	if (in_burst) {
		s->mutation_cycles += prev_cycle - burst_start;
	}
}

void
sprite_trace_frame_advance(uint32_t frame, uint32_t cpu_cycle,
                           const uint8_t attrs[SPRITE_TRACE_SLOTS][8])
{
	if (!sprite_trace_active || !allocated) {
		return;
	}

	// Charge the final scanline before the totals are taken.
	if (prev_begin_line < SPRITE_TRACE_LINES) {
		recording->lines[prev_begin_line].cpu_cycles += cpu_cycle - prev_begin_cycle;
	}
	prev_begin_line = SPRITE_TRACE_NO_LINE;

	finalize(recording, cpu_cycle);

	trace_buffer_t *done = recording;
	recording            = published;
	published            = done;
	have_published       = true;

	frame_number      = frame;
	frame_start_cycle = cpu_cycle;
	buffer_begin(recording);

	// Seed each slot with the value it starts the frame holding, so a sprite
	// that is never rewritten still has a generation to be recorded against.
	memset(slot_dirty, 0, sizeof(slot_dirty));
	memset(slot_dirty_writes, 0, sizeof(slot_dirty_writes));
	for (int slot = 0; slot < SPRITE_TRACE_SLOTS; slot++) {
		cur_gen[slot] = SPRITE_TRACE_NO_GEN;
		uint16_t idx  = open_gen(recording, (uint8_t)slot, attrs[slot]);
		if (idx != SPRITE_TRACE_NO_GEN) {
			recording->gens[idx].write_line  = SPRITE_TRACE_NO_LINE;
			recording->gens[idx].write_cycle = cpu_cycle;
			recording->gens[idx].writes      = 0;
			recording->gens[idx].flags |= SPRITE_GEN_CARRIED;
			cur_gen[slot] = idx;
		}
	}
}

const sprite_trace_frame_t *
sprite_trace_last_frame(void)
{
	if (!sprite_trace_active || !allocated || !have_published) {
		return NULL;
	}
	const trace_buffer_t *b = published;

	public_view.summary           = b->summary;
	public_view.gens              = b->gens;
	public_view.gen_count         = b->gen_count;
	public_view.mutations         = b->mutations;
	public_view.mutation_count    = b->mutation_count;
	public_view.mutations_dropped = b->mutation_dropped;
	public_view.lines             = b->lines;
	public_view.line_gen          = b->line_gen;
	public_view.line_flags        = b->line_flags;
	public_view.line_budget       = b->line_budget;
	return &public_view;
}

`/`	Search
`g` `c`	Code
`g` `h`	History
`g` `b`	Bookmarks
`g` `t`	Trust
`y`	Permalink to this state (files and trees)
`?`	This sheet

9120e874 Andy McCall 25 days ago	1	// Commander X16 Emulator — sprite multiplexing trace. See sprite_trace.h for
	2	// the data model and why the recording is split into a renderer stream and a
	3	// mutation stream.
	4
	5	#include "sprite_trace.h"
	6
	7	#include <stdlib.h>
	8	#include <string.h>
	9
	10	#define LINE_SLOTS (SPRITE_TRACE_LINES * SPRITE_TRACE_SLOTS)
	11
	12	// Generations start small and double. A frame using every slot without any
	13	// multiplexing needs 128; a 1024-sprite multiplexer needs a little over that
	14	// many. The ceiling exists so a runaway program cannot grow the trace without
	15	// bound -- past it, further values in a slot are folded into the last
	16	// generation, which understates the count rather than exhausting memory.
	17	#define GEN_CAP_INITIAL 512
	18	#define GEN_CAP_MAX 8192
	19
	20	// Attribute writes kept per frame. A multiplexer rewriting 8 bytes for each of
	21	// 1024 sprites lands 8192, so this leaves headroom. On overflow later writes
	22	// are counted but not stored: keeping an unbroken prefix means the burst
	23	// analysis stays valid for what was kept, which a wrapping ring would not.
	24	#define MUTATION_CAP 16384
	25
	26	#define DEFAULT_BURST_GAP 128
	27
	28	typedef struct {
	29	sprite_gen_t *gens;
	30	uint16_t gen_count;
	31	uint16_t gen_cap;
	32
	33	sprite_mutation_t *mutations;
	34	uint32_t mutation_count;
	35	uint32_t mutation_dropped;
	36
	37	sprite_line_stat_t lines[SPRITE_TRACE_LINES];
	38
	39	uint16_t *line_gen; // [LINE_SLOTS] index into gens, or SPRITE_TRACE_NO_GEN
	40	uint8_t line_flags; // [LINE_SLOTS] SPRITE_TRACE_
	41	uint16_t *line_budget; // [LINE_SLOTS] sprite-fetch cycles
	42
	43	sprite_frame_summary_t summary;
	44	} trace_buffer_t;
	45
	46	bool sprite_trace_active = false;
	47
	48	static trace_buffer_t buffers[2];
	49	static trace_buffer_t *recording = &buffers[0];
	50	static trace_buffer_t *published = &buffers[1];
	51	static bool have_published = false;
	52	static bool allocated = false;
	53
	54	// Per-slot recording state, valid only while a frame is in progress.
	55	static uint16_t cur_gen[SPRITE_TRACE_SLOTS];
	56	static bool slot_dirty[SPRITE_TRACE_SLOTS];
	57	static uint16_t slot_dirty_line[SPRITE_TRACE_SLOTS];
	58	static uint32_t slot_dirty_cycle[SPRITE_TRACE_SLOTS];
	59	static uint16_t slot_dirty_writes[SPRITE_TRACE_SLOTS];
	60
	61	static uint32_t frame_start_cycle;
	62	static uint32_t frame_number;
	63	static uint32_t burst_gap = DEFAULT_BURST_GAP;
	64
65	// For attributing CPU cycles to the scanline the beam was on: line_begin for
66	// line N+1 tells us how many cycles elapsed since line N started.
67	static uint16_t prev_begin_line = SPRITE_TRACE_NO_LINE;
68	static uint32_t prev_begin_cycle;
69
70	static sprite_trace_frame_t public_view;
71
72	static void
73	buffer_free(trace_buffer_t *b)
74	{
75	free(b->gens);
76	free(b->mutations);
77	free(b->line_gen);
78	free(b->line_flags);
79	free(b->line_budget);
80	memset(b, 0, sizeof(*b));
81	}
82
83	static bool
84	buffer_alloc(trace_buffer_t *b)
85	{
86	memset(b, 0, sizeof(*b));
87	b->gen_cap = GEN_CAP_INITIAL;
88	b->gens = (sprite_gen_t )malloc(sizeof(sprite_gen_t) b->gen_cap);
89	b->mutations = (sprite_mutation_t )malloc(sizeof(sprite_mutation_t) MUTATION_CAP);
90	b->line_gen = (uint16_t )malloc(sizeof(uint16_t) LINE_SLOTS);
91	b->line_flags = (uint8_t *)malloc(LINE_SLOTS);
92	b->line_budget = (uint16_t )malloc(sizeof(uint16_t) LINE_SLOTS);
93	if (!b->gens \|\| !b->mutations \|\| !b->line_gen \|\| !b->line_flags \|\| !b->line_budget) {
94	buffer_free(b);
95	return false;
96	}
97	return true;
98	}
99
100	// Clear a buffer for a new frame. The residency map is reset to "the renderer
101	// never reached this slot" rather than zero, because slot 0 is a real index.
102	static void
103	buffer_begin(trace_buffer_t *b)
104	{
105	b->gen_count = 0;
106	b->mutation_count = 0;
107	b->mutation_dropped = 0;
108	memset(&b->summary, 0, sizeof(b->summary));
109	memset(b->lines, 0, sizeof(b->lines));
110	memset(b->line_flags, 0, LINE_SLOTS);
111	memset(b->line_budget, 0, sizeof(uint16_t) * LINE_SLOTS);
112	for (int i = 0; i < LINE_SLOTS; i++) {
113	b->line_gen[i] = SPRITE_TRACE_NO_GEN;
114	}
115	for (int i = 0; i < SPRITE_TRACE_LINES; i++) {
116	b->lines[i].cut_slot = SPRITE_TRACE_NO_LINE;
117	}
118	}
119
120	size_t
121	sprite_trace_memory_usage(void)
122	{
123	if (!allocated) {
124	return 0;
125	}
126	size_t per = sizeof(sprite_mutation_t) * MUTATION_CAP + sizeof(uint16_t) * LINE_SLOTS +
127	(size_t)LINE_SLOTS + sizeof(uint16_t) * LINE_SLOTS + sizeof(((trace_buffer_t *)0)->lines);
128	return 2 * per + sizeof(sprite_gen_t) * (buffers[0].gen_cap + buffers[1].gen_cap);
129	}
130
131	void
132	sprite_trace_reset(void)
133	{
134	have_published = false;
135	prev_begin_line = SPRITE_TRACE_NO_LINE;
136	frame_start_cycle = 0;
137	frame_number = 0;
138	memset(slot_dirty, 0, sizeof(slot_dirty));
139	memset(slot_dirty_writes, 0, sizeof(slot_dirty_writes));
140	for (int i = 0; i < SPRITE_TRACE_SLOTS; i++) {
141	cur_gen[i] = SPRITE_TRACE_NO_GEN;
142	}
143	if (allocated) {
144	buffer_begin(recording);
145	buffer_begin(published);
146	}
147	}
148
149	bool
150	sprite_trace_set_enabled(bool on)
151	{
152	if (on == sprite_trace_active) {
153	return true;
154	}
155	if (on) {
156	if (!allocated) {
157	if (!buffer_alloc(&buffers[0])) {
158	return false;
159	}
160	if (!buffer_alloc(&buffers[1])) {
161	buffer_free(&buffers[0]);
162	return false;
163	}
164	allocated = true;
165	}
166	recording = &buffers[0];
167	published = &buffers[1];
168	sprite_trace_reset();
169	sprite_trace_active = true;
170	} else {
171	sprite_trace_active = false;
172	have_published = false;
173	if (allocated) {
174	buffer_free(&buffers[0]);
175	buffer_free(&buffers[1]);
176	allocated = false;
177	}
178	}
179	return true;
180	}
181
182	void
183	sprite_trace_set_burst_gap(uint32_t cycles)
184	{
185	burst_gap = cycles;
186	}
187
188	uint32_t
189	sprite_trace_get_burst_gap(void)
190	{
191	return burst_gap;
192	}
193
194	// Decode the attribute bytes the way refresh_sprite_properties() does, so a
195	// generation carries the same interpretation the renderer used.
196	static void
197	decode_attr(sprite_gen_t *g, const uint8_t attr[8])
198	{
199	memcpy(g->attr, attr, 8);
200
201	g->zdepth = (uint8_t)((attr[6] >> 2) & 3);
202	g->collision_mask = (uint8_t)(attr[6] & 0xf0);
203	g->hflip = (attr[6] & 1) != 0;
204	g->vflip = ((attr[6] >> 1) & 1) != 0;
205
206	g->x = (int16_t)(attr[2] \| ((attr[3] & 3) << 8));
207	g->y = (int16_t)(attr[4] \| ((attr[5] & 3) << 8));
208
209	g->width = (uint16_t)(1u << ((((attr[7] >> 4) & 3) + 3)));
210	g->height = (uint16_t)(1u << ((attr[7] >> 6) + 3));
211
212	if (g->x >= (int16_t)(0x400 - g->width)) {
213	g->x = (int16_t)(g->x - 0x400);
214	}
215	if (g->y >= (int16_t)(0x400 - g->height)) {
216	g->y = (int16_t)(g->y - 0x400);
217	}
218
219	g->color_mode = (uint8_t)((attr[1] >> 7) & 1);
220	g->address = (uint32_t)(attr[0] << 5 \| (attr[1] & 0xf) << 13);
221	g->palette_offset = (uint8_t)((attr[7] & 0x0f) << 4);
222	}
223
224	// Open a generation for a slot whose value the CPU changed. Returns the index,
225	// or the slot's existing generation if the table is full.
226	static uint16_t
227	open_gen(trace_buffer_t *b, uint8_t slot, const uint8_t attr[8])
228	{
229	if (b->gen_count >= b->gen_cap) {
230	if (b->gen_cap >= GEN_CAP_MAX) {
231	return cur_gen[slot];
232	}
233	uint16_t ncap = (uint16_t)(b->gen_cap * 2 > GEN_CAP_MAX ? GEN_CAP_MAX : b->gen_cap * 2);
234	sprite_gen_t ng = (sprite_gen_t )realloc(b->gens, sizeof(sprite_gen_t) * ncap);
235	if (!ng) {
236	return cur_gen[slot];
237	}
238	b->gens = ng;
239	b->gen_cap = ncap;
240	}
241
242	uint16_t idx = b->gen_count++;
243	sprite_gen_t *g = &b->gens[idx];
244	memset(g, 0, sizeof(*g));
245	decode_attr(g, attr);
246	g->slot = slot;
247	g->first_line = SPRITE_TRACE_NO_LINE;
248	g->last_line = SPRITE_TRACE_NO_LINE;
249
250	uint16_t prev = cur_gen[slot];
251	g->index_in_slot = (uint16_t)(prev == SPRITE_TRACE_NO_GEN ? 0 : b->gens[prev].index_in_slot + 1);
252
253	return idx;
254	}
255
256	void
257	sprite_trace_note_write(uint8_t slot, uint8_t offset, uint8_t old_val, uint8_t new_val,
258	uint16_t line, uint32_t cpu_cycle)
259	{
260	if (!sprite_trace_active \|\| !allocated) {
261	return;
262	}
263	slot &= (SPRITE_TRACE_SLOTS - 1);
264	offset &= 7;
265
266	trace_buffer_t *b = recording;
267
268	b->summary.mutations++;
269	if (line < SPRITE_TRACE_LINES) {
270	b->summary.mutations_onscreen++;
271	}
272
273	if (b->mutation_count < MUTATION_CAP) {
274	sprite_mutation_t *m = &b->mutations[b->mutation_count++];
275	m->cycle = cpu_cycle;
276	m->line = line;
277	m->slot = slot;
278	m->offset = offset;
279	m->old_val = old_val;
280	m->new_val = new_val;
281	} else {
282	b->mutation_dropped++;
283	}
284
285	// A write that stores the value already there costs the CPU exactly as much
286	// as any other and belongs in the cost total, but it does not start a new
287	// generation: nothing about what the beam will draw has changed.
288	if (old_val == new_val) {
289	return;
290	}
291
292	if (!slot_dirty[slot]) {
293	slot_dirty[slot] = true;
294	slot_dirty_writes[slot] = 0;
295	}
296	// Kept as the most recent write, so the generation is stamped with the
297	// moment its value became complete rather than when the update began. That
298	// is the instant a late write has to be judged against.
299	slot_dirty_line[slot] = line;
300	slot_dirty_cycle[slot] = cpu_cycle;
301	slot_dirty_writes[slot]++;
302	}
303
304	void
305	sprite_trace_line_begin(uint16_t line, uint32_t cpu_cycle)
306	{
307	if (!sprite_trace_active \|\| !allocated) {
308	return;
309	}
310
311	// Close out the previous line's CPU accounting before touching this one.
312	// Accumulated rather than assigned: a line re-rendered by a mid-line split
313	// gets begun twice, and both spans were spent with the beam on that line.
314	if (prev_begin_line < SPRITE_TRACE_LINES) {
315	recording->lines[prev_begin_line].cpu_cycles += cpu_cycle - prev_begin_cycle;
316	}
317	prev_begin_line = line;
318	prev_begin_cycle = cpu_cycle;
319
320	if (line >= SPRITE_TRACE_LINES) {
321	return;
322	}
323
324	trace_buffer_t *b = recording;
325	const size_t off = (size_t)line * SPRITE_TRACE_SLOTS;
326	for (int s = 0; s < SPRITE_TRACE_SLOTS; s++) {
327	b->line_gen[off + s] = SPRITE_TRACE_NO_GEN;
328	}
329	memset(b->line_flags + off, 0, SPRITE_TRACE_SLOTS);
330	memset(b->line_budget + off, 0, sizeof(uint16_t) * SPRITE_TRACE_SLOTS);
331
332	uint32_t keep_cycles = b->lines[line].cpu_cycles;
333	memset(&b->lines[line], 0, sizeof(b->lines[line]));
334	b->lines[line].cpu_cycles = keep_cycles;
335	b->lines[line].cut_slot = SPRITE_TRACE_NO_LINE;
336	b->lines[line].rendered = true;
337	}
338
339	void
340	sprite_trace_note_slot(uint16_t line, uint8_t slot, const uint8_t attr[8],
341	uint16_t budget_used, uint8_t flags)
342	{
343	if (!sprite_trace_active \|\| !allocated \|\| line >= SPRITE_TRACE_LINES) {
344	return;
345	}
346	slot &= (SPRITE_TRACE_SLOTS - 1);
347
348	trace_buffer_t *b = recording;
349
350	// The renderer is reading this slot now, so now is when a pending change
351	// becomes the value that was actually displayed -- half-written included.
352	if (slot_dirty[slot]) {
353	uint16_t idx = open_gen(b, slot, attr);
354	if (idx != SPRITE_TRACE_NO_GEN) {
355	sprite_gen_t *g = &b->gens[idx];
356	if (idx == b->gen_count - 1) {
357	g->write_line = slot_dirty_line[slot];
358	g->write_cycle = slot_dirty_cycle[slot];
359	g->writes = slot_dirty_writes[slot];
360	} else {
361	// Folded into the previous generation because the table is
362	// full; keep its write count honest.
363	g->writes = (uint16_t)(g->writes + slot_dirty_writes[slot]);
364	}
365	cur_gen[slot] = idx;
366	}
367	slot_dirty[slot] = false;
368	slot_dirty_writes[slot] = 0;
369	}
370
371	const size_t i = (size_t)line * SPRITE_TRACE_SLOTS + slot;
372	b->line_gen[i] = cur_gen[slot];
373	b->line_flags[i] = flags;
374	b->line_budget[i] = budget_used;
375	}
376
377	void
378	sprite_trace_line_end(uint16_t line, const sprite_line_stat_t *result)
379	{
380	if (!sprite_trace_active \|\| !allocated \|\| line >= SPRITE_TRACE_LINES \|\| !result) {
381	return;
382	}
383	sprite_line_stat_t *st = &recording->lines[line];
384	const uint32_t keep_cycles = st->cpu_cycles;
385	st = result;
386	st->cpu_cycles = keep_cycles;
387	st->rendered = true;
388	}
389
390	// Walk the finished residency map once and turn it into per-generation totals
391	// and a frame summary. Done here rather than incrementally because a scanline
392	// can be rendered more than once and only the final pass counts.
393	static void
394	finalize(trace_buffer_t *b, uint32_t end_cycle)
395	{
396	sprite_frame_summary_t *s = &b->summary;
397	s->frame = frame_number;
398	s->cpu_cycles = end_cycle - frame_start_cycle;
399	s->gen_count = b->gen_count;
400	s->burst_gap = burst_gap;
401
402	for (uint16_t line = 0; line < SPRITE_TRACE_LINES; line++) {
403	const size_t off = (size_t)line * SPRITE_TRACE_SLOTS;
404	for (int slot = 0; slot < SPRITE_TRACE_SLOTS; slot++) {
405	uint16_t idx = b->line_gen[off + slot];
406	if (idx == SPRITE_TRACE_NO_GEN \|\| idx >= b->gen_count) {
407	continue;
408	}
409	sprite_gen_t *g = &b->gens[idx];
410	uint8_t f = b->line_flags[off + slot];
411
412	g->lines_resident++;
413	g->budget_cycles += b->line_budget[off + slot];
414	if (f & SPRITE_TRACE_CUT) {
415	g->flags \|= SPRITE_GEN_CUT;
416	}
417	if (f & SPRITE_TRACE_DREW) {
418	g->flags \|= SPRITE_GEN_DREW;
419	g->lines_drawn++;
420	if (g->first_line == SPRITE_TRACE_NO_LINE) {
421	g->first_line = line;
422	}
423	g->last_line = line;
424	}
425	}
426	}
427
428	uint16_t drawn_gens_in_slot[SPRITE_TRACE_SLOTS];
429	uint16_t gens_in_slot[SPRITE_TRACE_SLOTS];
430	memset(drawn_gens_in_slot, 0, sizeof(drawn_gens_in_slot));
431	memset(gens_in_slot, 0, sizeof(gens_in_slot));
432
433	for (uint16_t i = 0; i < b->gen_count; i++) {
434	sprite_gen_t *g = &b->gens[i];
435	gens_in_slot[g->slot]++;
436
437	if (g->flags & SPRITE_GEN_DREW) {
438	s->effective_sprites++;
439	drawn_gens_in_slot[g->slot]++;
440	} else if (!(g->flags & SPRITE_GEN_CARRIED)) {
441	s->phantom_writes++;
442	}
443
444	// Late: the value only became complete after the beam had already
445	// passed the whole Y span it was meant to appear in, so nothing this
446	// frame could ever have drawn it. Computed in int, because a sprite
447	// parked just above the screen has a negative Y and its span ends at or
448	// before line 0 -- which is late for every write, and would wrap to a
449	// huge number if this were done in uint16_t.
450	const int y_end = (int)g->y + (int)g->height;
451	if (!(g->flags & SPRITE_GEN_CARRIED) && g->write_line < SPRITE_TRACE_LINES &&
452	g->zdepth != 0 && (int)g->write_line >= y_end) {
453	g->flags \|= SPRITE_GEN_LATE;
454	s->late_writes++;
455	}
456	}
457
458	for (int slot = 0; slot < SPRITE_TRACE_SLOTS; slot++) {
459	if (drawn_gens_in_slot[slot] > 0) {
460	s->slots_used++;
461	}
462	if (drawn_gens_in_slot[slot] > 1) {
463	s->slots_multiplexed++;
464	}
465	if (gens_in_slot[slot] > s->max_gens_in_slot) {
466	s->max_gens_in_slot = gens_in_slot[slot];
467	}
468	}
469	s->multiplexing = s->slots_multiplexed > 0;
470
471	for (uint16_t line = 0; line < SPRITE_TRACE_LINES; line++) {
472	const sprite_line_stat_t *st = &b->lines[line];
473	s->budget_used_total += st->budget_used;
474	s->sprites_dropped += st->dropped;
475	if (st->exhausted) {
476	s->lines_exhausted++;
477	}
478	// Ranked by demand, not by clocks used: once several lines are over the
479	// ceiling they all report the same usage, and the worst one is the one
480	// that wanted the most.
481	if (st->demand > s->peak_demand) {
482	s->peak_demand = st->demand;
483	s->peak_budget = st->budget_used;
484	s->peak_line = line;
485	}
486	}
487
488	// Cluster the attribute writes into bursts. One burst is one visit to the
489	// multiplexer's raster handler; the cycles it spans are what the
490	// multiplexing costs the guest. It is a lower bound -- the handler's entry,
491	// exit and any work after its final store fall outside the span.
492	uint32_t burst_start = 0;
493	uint32_t prev_cycle = 0;
494	bool in_burst = false;
495	for (uint32_t i = 0; i < b->mutation_count; i++) {
496	uint32_t c = b->mutations[i].cycle;
497	if (!in_burst \|\| c - prev_cycle > burst_gap) {
498	if (in_burst) {
499	s->mutation_cycles += prev_cycle - burst_start;
500	}
501	s->mutation_bursts++;
502	burst_start = c;
503	in_burst = true;
504	}
505	prev_cycle = c;
506	}
507	if (in_burst) {
508	s->mutation_cycles += prev_cycle - burst_start;
509	}
510	}
511
512	void
513	sprite_trace_frame_advance(uint32_t frame, uint32_t cpu_cycle,
514	const uint8_t attrs[SPRITE_TRACE_SLOTS][8])
515	{
516	if (!sprite_trace_active \|\| !allocated) {
517	return;
518	}
519
520	// Charge the final scanline before the totals are taken.
521	if (prev_begin_line < SPRITE_TRACE_LINES) {
522	recording->lines[prev_begin_line].cpu_cycles += cpu_cycle - prev_begin_cycle;
523	}
524	prev_begin_line = SPRITE_TRACE_NO_LINE;
525
526	finalize(recording, cpu_cycle);
527
528	trace_buffer_t *done = recording;
529	recording = published;
530	published = done;
531	have_published = true;
532
533	frame_number = frame;
534	frame_start_cycle = cpu_cycle;
535	buffer_begin(recording);
536
537	// Seed each slot with the value it starts the frame holding, so a sprite
538	// that is never rewritten still has a generation to be recorded against.
539	memset(slot_dirty, 0, sizeof(slot_dirty));
540	memset(slot_dirty_writes, 0, sizeof(slot_dirty_writes));
541	for (int slot = 0; slot < SPRITE_TRACE_SLOTS; slot++) {
542	cur_gen[slot] = SPRITE_TRACE_NO_GEN;
543	uint16_t idx = open_gen(recording, (uint8_t)slot, attrs[slot]);
544	if (idx != SPRITE_TRACE_NO_GEN) {
545	recording->gens[idx].write_line = SPRITE_TRACE_NO_LINE;
546	recording->gens[idx].write_cycle = cpu_cycle;
547	recording->gens[idx].writes = 0;
548	recording->gens[idx].flags \|= SPRITE_GEN_CARRIED;
549	cur_gen[slot] = idx;
550	}
551	}
552	}
553
554	const sprite_trace_frame_t *
555	sprite_trace_last_frame(void)
556	{
557	if (!sprite_trace_active \|\| !allocated \|\| !have_published) {
558	return NULL;
559	}
560	const trace_buffer_t *b = published;
561
562	public_view.summary = b->summary;
563	public_view.gens = b->gens;
564	public_view.gen_count = b->gen_count;
565	public_view.mutations = b->mutations;
566	public_view.mutation_count = b->mutation_count;
567	public_view.mutations_dropped = b->mutation_dropped;
568	public_view.lines = b->lines;
569	public_view.line_gen = b->line_gen;
570	public_view.line_flags = b->line_flags;
571	public_view.line_budget = b->line_budget;
572	return &public_view;
573	}

Keyboard