Using a Protocol Analyser

   arm ----> [ always writing, oldest overwritten ] ----> trigger
                          |<--- kept --->|<-- POST_N -->|

   The trigger chooses a WINDOW, and the window straddles it.

   pre_kept = min(events before the trigger, DEPTH - post_kept)

   DEPTH = 64, POST_N = 8    ->  at most 56 pre-trigger events
   DEPTH = 64, POST_N = 32   ->  at most 32
   DEPTH = 64, POST_N = 64   ->  none at all

   Filter on the way OUT, never on the way IN.

// usb_trace_filter -- why the capture you took does not contain the bug,
// and the two decisions that fix it.
//
// A TRIGGER FIRES ON THE SYMPTOM, AND THE SYMPTOM IS THE END OF THE STORY
//
// You set the analyser to trigger on a STALL. It triggers. You get a
// beautiful capture of everything that happened AFTER the STALL: the host
// giving up, the driver resetting the endpoint, the retry storm. None of
// which is the bug.
//
// The bug is whatever the firmware did three hundred transactions earlier
// that made it decide to stall. That is in the part of the trace you did
// not record, because you had not triggered yet.
//
//     A post-trigger-only capture records the AFTERMATH.
//     The cause is always before the trigger. Always.
//
// THE FIX IS TO RECORD ALWAYS AND LET THE TRIGGER DECIDE WHAT TO KEEP
//
// A circular buffer that is running the entire time. The trigger does not
// start the recording; it STOPS it, some number of events later. What you
// keep is a window that straddles the trigger.
//
//     arm ----> [ always writing, oldest overwritten ] ----> trigger
//                            |<--- kept --->|<-- POST_N -->|
//
// AND THE POST-TRIGGER WINDOW EATS THE PRE-TRIGGER HISTORY
//
// This is the part that surprises people. The buffer is a fixed DEPTH. Every
// event captured after the trigger overwrites the OLDEST pre-trigger entry.
// So asking for more post-trigger context costs you exactly that much
// pre-trigger context, and the pre-trigger context is where the bug is:
//
//     pre_kept = min(events before the trigger, DEPTH - post_kept)
//
// THE SECOND TRAP: FILTERING AT CAPTURE TIME
//
// "Just capture the errors" halves the file size and destroys the
// investigation. The error is the symptom; the surrounding ordinary traffic
// is the evidence. A capture filtered down to errors cannot answer "what was
// this endpoint doing immediately before", which is the only question.
//
//     Filter on the way OUT, never on the way IN.
//
// So the view mask here is applied at READ time. Every event is in the
// buffer; the mask only decides what is shown, and the hidden ones are
// counted so the number on screen is never mistaken for the number captured.
//
// AND THE CAPTURE HAS TO SAY WHEN IT IS NOT LONG ENOUGH
//
// If more events occurred before the trigger than the buffer could hold, the
// cause may be off the front -- and a full buffer looks exactly like a
// sufficient one. `pre_lost` is the difference between "the cause is not in
// this capture" and "there is no cause", which are not the same finding.
module usb_trace_filter #(
  parameter integer DEPTH  = 64,   // circular buffer entries
  parameter integer POST_N = 8     // events captured after the trigger
) (
  input  wire        clk,
  input  wire        rst_n,

  input  wire        arm,          // begin a fresh capture
  input  wire        ev_valid,
  input  wire [1:0]  ev_type,      // 0 token, 1 data, 2 handshake, 3 error
  input  wire [3:0]  ev_ep,
  input  wire [7:0]  ev_code,
  input  wire        trigger,      // the symptom fired

  input  wire        rd_en,
  input  wire [3:0]  view_mask,    // one bit per event type, applied ON READ

  output wire [1:0]  state,
  output wire [7:0]  n_valid,      // entries retained
  output wire [7:0]  pre_kept,
  output wire [7:0]  post_kept,
  output wire        pre_lost,     // the cause may be off the front

  output wire        rd_valid,
  output wire        rd_show,      // passes the view mask
  output wire [1:0]  rd_type,
  output wire [3:0]  rd_ep,
  output wire [7:0]  rd_code,
  output wire [7:0]  rd_index,     // 0 = oldest retained

  output reg [31:0] n_written,     // every event offered. NEVER filtered.
  output reg [31:0] n_overwritten, // lost to the circular buffer
  output reg [31:0] n_shown,
  output reg [31:0] n_hidden       // in the capture, not on the screen
);

  localparam [1:0] S_IDLE   = 2'd0,
                   S_ARMED  = 2'd1,   // recording, waiting for the symptom
                   S_CAPT   = 2'd2,   // triggered, taking POST_N more
                   S_FROZEN = 2'd3;   // done; drain it

  // The index width. Written as a localparam rather than $clog2 inline so
  // that the two places it is used cannot drift apart.
  localparam integer AW = (DEPTH <= 16)  ? 4 :
                          (DEPTH <= 32)  ? 5 :
                          (DEPTH <= 64)  ? 6 :
                          (DEPTH <= 128) ? 7 : 8;

  reg [1:0]  ty_m   [0:DEPTH-1];
  reg [3:0]  ep_m   [0:DEPTH-1];
  reg [7:0]  code_m [0:DEPTH-1];

  reg [1:0]      st_r;
  reg [AW-1:0]   wr_r;
  reg [15:0]     total_r;     // events written since arm, saturating
  reg [15:0]     pre_r;       // events written BEFORE the trigger
  reg [7:0]      post_r;      // events written after it
  reg [7:0]      rdi_r;       // drain index
  reg            rdv_r;

  // ---- What survived. ----
  //
  // post_kept is however many post-trigger events were actually taken --
  // fewer than POST_N if the capture was frozen early. pre_kept is what the
  // buffer had room for AFTER those, which is the subtraction that surprises
  // people.
  wire [7:0] post_k = post_r;
  // ---- DEPTH is bounded by the port widths, and that is stated here. ----
  //
  // pre_kept, post_kept and n_valid are eight-bit outputs, so a buffer
  // deeper than 255 cannot be reported through them whatever this expression
  // does. Rather than widen one number and leave the others, the bound is
  // made explicit: this block is correct for DEPTH <= 255. Chapter 25.4's
  // retry budget is the same question answered the other way, and the rule
  // is the same -- a width follows from what the value means, and a value
  // that cannot be expressed is a documented limit rather than a surprise.
  wire [7:0] depth8 = DEPTH;
  wire [7:0] room   = (depth8 > post_k) ? (depth8 - post_k) : 8'd0;
  wire [7:0] pre_k  = (pre_r > {8'd0, room}) ? room : pre_r[7:0];

  assign state     = st_r;
  assign pre_kept  = pre_k;
  assign post_kept = post_k;
  assign n_valid   = pre_k + post_k;
  // The cause may be off the front, and a full buffer looks exactly like a
  // sufficient one. This bit is the difference between "not in this capture"
  // and "no such event".
  assign pre_lost  = (pre_r > {8'd0, room});

  // ---- The read window. ----
  //
  // Chronological, oldest first. The oldest retained entry is n_valid slots
  // behind the write pointer, modulo the buffer -- which is the only place
  // the circularity is visible, and the only place it can be got wrong.
  wire [AW-1:0] rd_addr = wr_r - n_valid[AW-1:0] + rdi_r[AW-1:0];

  // ---- The read port is REGISTERED, all of it, together. ----
  //
  // A combinational read off `rdi_r` beside a registered `rd_valid` is off
  // by one: the pointer advances on the same edge that raises valid, so the
  // data presented alongside the valid pulse belongs to the NEXT entry. The
  // symptom is a capture that is correct in every respect except that it
  // starts one entry late and ends one entry early -- which is exactly the
  // kind of defect a length check cannot see, and exactly why this
  // testbench compares the contents rather than the count.
  reg [1:0] rdt_r;
  reg [3:0] rde_r;
  reg [7:0] rdc_r;
  reg [7:0] rdx_r;
  reg       rds_r;

  assign rd_valid = rdv_r;
  assign rd_type  = rdt_r;
  assign rd_ep    = rde_r;
  assign rd_code  = rdc_r;
  assign rd_index = rdx_r;
  // The mask decides what is SHOWN. The entry is in the buffer either way.
  assign rd_show  = rds_r;

  integer i;
  always @(posedge clk or negedge rst_n) begin
    if (!rst_n) begin
      st_r    <= S_IDLE;
      wr_r    <= {AW{1'b0}};
      total_r <= 16'd0;
      pre_r   <= 16'd0;
      post_r  <= 8'd0;
      rdi_r   <= 8'd0;
      rdv_r   <= 1'b0;
      rdt_r   <= 2'd0;
      rde_r   <= 4'd0;
      rdc_r   <= 8'd0;
      rdx_r   <= 8'd0;
      rds_r   <= 1'b0;
      n_written     <= 32'd0;
      n_overwritten <= 32'd0;
      n_shown       <= 32'd0;
      n_hidden      <= 32'd0;
      for (i = 0; i < DEPTH; i = i + 1) begin
        ty_m[i]   <= 2'd0;
        ep_m[i]   <= 4'd0;
        code_m[i] <= 8'd0;
      end
    end else begin
      rdv_r <= 1'b0;

      if (arm) begin
        st_r    <= S_ARMED;
        wr_r    <= {AW{1'b0}};
        total_r <= 16'd0;
        pre_r   <= 16'd0;
        post_r  <= 8'd0;
        rdi_r   <= 8'd0;
      end else begin
        // ---- WRITE FIRST, unconditionally, with no filter of any kind. ----
        //
        // Not "write if it is an error", not "write if it matches the mask".
        // The mask lives on the read side and nowhere else; the moment a
        // filter appears here, the context that explains the error is gone
        // and no amount of later processing brings it back.
        if (ev_valid && ((st_r == S_ARMED) || (st_r == S_CAPT))) begin
          ty_m[wr_r]   <= ev_type;
          ep_m[wr_r]   <= ev_ep;
          code_m[wr_r] <= ev_code;
          wr_r         <= wr_r + {{(AW-1){1'b0}}, 1'b1};
          n_written    <= n_written + 32'd1;
          if (total_r >= DEPTH) n_overwritten <= n_overwritten + 32'd1;
          if (total_r != 16'hFFFF) total_r <= total_r + 16'd1;

          if (st_r == S_ARMED) begin
            if (pre_r != 16'hFFFF) pre_r <= pre_r + 16'd1;
          end else begin
            post_r <= post_r + 8'd1;
            // ---- The post-trigger window is the last thing that happens.
            //
            // POST_N events after the symptom and the capture stops. Every
            // one of them has already overwritten an oldest pre-trigger
            // entry, which is the cost nobody budgets for.
            if (post_r + 8'd1 >= POST_N[7:0]) st_r <= S_FROZEN;
          end
        end

        // The trigger is sampled AFTER the write, so the event that caused
        // the symptom is itself the last pre-trigger entry rather than the
        // first post-trigger one. Off by one here moves the boundary of
        // every capture by one event, which is invisible until somebody
        // counts.
        if (trigger && (st_r == S_ARMED)) st_r <= S_CAPT;

        if (rd_en && (st_r == S_FROZEN)) begin
          if (rdi_r < n_valid) begin
            rdv_r <= 1'b1;
            rdi_r <= rdi_r + 8'd1;
            rdt_r <= ty_m[rd_addr];
            rde_r <= ep_m[rd_addr];
            rdc_r <= code_m[rd_addr];
            rdx_r <= rdi_r;
            rds_r <= view_mask[ty_m[rd_addr]];
            if (view_mask[ty_m[rd_addr]]) n_shown  <= n_shown  + 32'd1;
            else                          n_hidden <= n_hidden + 32'd1;
          end
        end
      end
    end
  end
endmodule

// usb_trace_filter -- why the capture you took does not contain the bug,
// and the two decisions that fix it.
//
// A TRIGGER FIRES ON THE SYMPTOM, AND THE SYMPTOM IS THE END OF THE STORY
//
// You set the analyser to trigger on a STALL. It triggers. You get a
// beautiful capture of everything that happened AFTER the STALL: the host
// giving up, the driver resetting the endpoint, the retry storm. None of
// which is the bug.
//
// The bug is whatever the firmware did three hundred transactions earlier
// that made it decide to stall. That is in the part of the trace you did
// not record, because you had not triggered yet.
//
//     A post-trigger-only capture records the AFTERMATH.
//     The cause is always before the trigger. Always.
//
// THE FIX IS TO RECORD ALWAYS AND LET THE TRIGGER DECIDE WHAT TO KEEP
//
// A circular buffer that is running the entire time. The trigger does not
// start the recording; it STOPS it, some number of events later. What you
// keep is a window that straddles the trigger.
//
//     arm ----> [ always writing, oldest overwritten ] ----> trigger
//                            |<--- kept --->|<-- POST_N -->|
//
// AND THE POST-TRIGGER WINDOW EATS THE PRE-TRIGGER HISTORY
//
// This is the part that surprises people. The buffer is a fixed DEPTH. Every
// event captured after the trigger overwrites the OLDEST pre-trigger entry.
// So asking for more post-trigger context costs you exactly that much
// pre-trigger context, and the pre-trigger context is where the bug is:
//
//     pre_kept = min(events before the trigger, DEPTH - post_kept)
//
// THE SECOND TRAP: FILTERING AT CAPTURE TIME
//
// "Just capture the errors" halves the file size and destroys the
// investigation. The error is the symptom; the surrounding ordinary traffic
// is the evidence. A capture filtered down to errors cannot answer "what was
// this endpoint doing immediately before", which is the only question.
//
//     Filter on the way OUT, never on the way IN.
//
// So the view mask here is applied at READ time. Every event is in the
// buffer; the mask only decides what is shown, and the hidden ones are
// counted so the number on screen is never mistaken for the number captured.
//
// AND THE CAPTURE HAS TO SAY WHEN IT IS NOT LONG ENOUGH
//
// If more events occurred before the trigger than the buffer could hold, the
// cause may be off the front -- and a full buffer looks exactly like a
// sufficient one. `pre_lost` is the difference between "the cause is not in
// this capture" and "there is no cause", which are not the same finding.
package usb_trace_pkg;
  typedef enum logic [1:0] {
    S_IDLE   = 2'd0,
    S_ARMED  = 2'd1,   // recording, waiting for the symptom
    S_CAPT   = 2'd2,   // triggered, taking POST_N more
    S_FROZEN = 2'd3    // done; drain it
  } cap_state_e;

  typedef enum logic [1:0] {
    EV_TOKEN = 2'd0,
    EV_DATA  = 2'd1,
    EV_HSHK  = 2'd2,
    EV_ERROR = 2'd3
  } ev_type_e;
endpackage

module usb_trace_filter
  import usb_trace_pkg::*;
 #(
  parameter int DEPTH  = 64,       // circular buffer entries
  parameter int POST_N = 8         // events captured after the trigger
) (
  input  logic       clk,
  input  logic       rst_n,

  input  logic       arm,          // begin a fresh capture
  input  logic       ev_valid,
  input  ev_type_e   ev_type,
  input  logic [3:0] ev_ep,
  input  logic [7:0] ev_code,
  input  logic       trigger,      // the symptom fired

  input  logic       rd_en,
  input  logic [3:0] view_mask,    // one bit per event type, applied ON READ

  output cap_state_e state,
  output logic [7:0] n_valid,      // entries retained
  output logic [7:0] pre_kept,
  output logic [7:0] post_kept,
  output logic       pre_lost,     // the cause may be off the front

  output logic       rd_valid,
  output logic       rd_show,      // passes the view mask
  output ev_type_e   rd_type,
  output logic [3:0] rd_ep,
  output logic [7:0] rd_code,
  output logic [7:0] rd_index,     // 0 = oldest retained

  output logic [31:0] n_written,     // every event offered. NEVER filtered.
  output logic [31:0] n_overwritten, // lost to the circular buffer
  output logic [31:0] n_shown,
  output logic [31:0] n_hidden       // in the capture, not on the screen
);

  // The index width. Written as a localparam rather than $clog2 inline so
  // that the two places it is used cannot drift apart.
  localparam int AW = (DEPTH <= 16)  ? 4 :
                          (DEPTH <= 32)  ? 5 :
                          (DEPTH <= 64)  ? 6 :
                          (DEPTH <= 128) ? 7 : 8;

  ev_type_e    ty_m   [DEPTH-1:0];
  logic [3:0]  ep_m   [DEPTH-1:0];
  logic [7:0]  code_m [DEPTH-1:0];

  cap_state_e    st_r;
  logic [AW-1:0] wr_r;
  logic [15:0]   total_r;   // events written since arm, saturating
  logic [15:0]   pre_r;     // events written BEFORE the trigger
  logic [7:0]    post_r;    // events written after it
  logic [7:0]    rdi_r;     // drain index
  logic          rdv_r;

  // ---- What survived. ----
  //
  // post_kept is however many post-trigger events were actually taken --
  // fewer than POST_N if the capture was frozen early. pre_kept is what the
  // buffer had room for AFTER those, which is the subtraction that surprises
  // people.
  logic [7:0] post_k, room, pre_k;
  assign post_k = post_r;
  // ---- DEPTH is bounded by the port widths, and that is stated here. ----
  //
  // pre_kept, post_kept and n_valid are eight-bit outputs, so a buffer
  // deeper than 255 cannot be reported through them whatever this expression
  // does. Rather than widen one number and leave the others, the bound is
  // made explicit: this block is correct for DEPTH <= 255. Chapter 25.4's
  // retry budget is the same question answered the other way, and the rule
  // is the same -- a width follows from what the value means, and a value
  // that cannot be expressed is a documented limit rather than a surprise.
  localparam logic [7:0] DEPTH8 = 8'(DEPTH);
  assign room   = (DEPTH8 > post_k) ? (DEPTH8 - post_k) : 8'd0;
  assign pre_k  = (pre_r > {8'd0, room}) ? room : pre_r[7:0];

  assign state     = st_r;
  assign pre_kept  = pre_k;
  assign post_kept = post_k;
  assign n_valid   = pre_k + post_k;
  // The cause may be off the front, and a full buffer looks exactly like a
  // sufficient one. This bit is the difference between "not in this capture"
  // and "no such event".
  assign pre_lost  = (pre_r > {8'd0, room});

  // ---- The read window. ----
  //
  // Chronological, oldest first. The oldest retained entry is n_valid slots
  // behind the write pointer, modulo the buffer -- which is the only place
  // the circularity is visible, and the only place it can be got wrong.
  logic [AW-1:0] rd_addr; assign rd_addr = wr_r - n_valid[AW-1:0] + rdi_r[AW-1:0];

  // ---- The read port is REGISTERED, all of it, together. ----
  //
  // A combinational read off `rdi_r` beside a registered `rd_valid` is off
  // by one: the pointer advances on the same edge that raises valid, so the
  // data presented alongside the valid pulse belongs to the NEXT entry. The
  // symptom is a capture that is correct in every respect except that it
  // starts one entry late and ends one entry early -- which is exactly the
  // kind of defect a length check cannot see, and exactly why this
  // testbench compares the contents rather than the count.
  ev_type_e   rdt_r;
  logic [3:0] rde_r;
  logic [7:0] rdc_r;
  logic [7:0] rdx_r;
  logic       rds_r;

  assign rd_valid = rdv_r;
  assign rd_type  = rdt_r;
  assign rd_ep    = rde_r;
  assign rd_code  = rdc_r;
  assign rd_index = rdx_r;
  // The mask decides what is SHOWN. The entry is in the buffer either way.
  assign rd_show  = rds_r;

  int i;
  always_ff @(posedge clk or negedge rst_n) begin
    if (!rst_n) begin
      st_r    <= S_IDLE;
      wr_r    <= {AW{1'b0}};
      total_r <= 16'd0;
      pre_r   <= 16'd0;
      post_r  <= 8'd0;
      rdi_r   <= 8'd0;
      rdv_r   <= 1'b0;
      rdt_r   <= EV_TOKEN;
      rde_r   <= 4'd0;
      rdc_r   <= 8'd0;
      rdx_r   <= 8'd0;
      rds_r   <= 1'b0;
      n_written     <= 32'd0;
      n_overwritten <= 32'd0;
      n_shown       <= 32'd0;
      n_hidden      <= 32'd0;
      for (i = 0; i < DEPTH; i = i + 1) begin
        ty_m[i]   <= EV_TOKEN;
        ep_m[i]   <= 4'd0;
        code_m[i] <= 8'd0;
      end
    end else begin
      rdv_r <= 1'b0;

      if (arm) begin
        st_r    <= S_ARMED;
        wr_r    <= {AW{1'b0}};
        total_r <= 16'd0;
        pre_r   <= 16'd0;
        post_r  <= 8'd0;
        rdi_r   <= 8'd0;
      end else begin
        // ---- WRITE FIRST, unconditionally, with no filter of any kind. ----
        //
        // Not "write if it is an error", not "write if it matches the mask".
        // The mask lives on the read side and nowhere else; the moment a
        // filter appears here, the context that explains the error is gone
        // and no amount of later processing brings it back.
        if (ev_valid && ((st_r == S_ARMED) || (st_r == S_CAPT))) begin
          ty_m[wr_r]   <= ev_type;
          ep_m[wr_r]   <= ev_ep;
          code_m[wr_r] <= ev_code;
          wr_r         <= wr_r + {{(AW-1){1'b0}}, 1'b1};
          n_written    <= n_written + 32'd1;
          if (total_r >= 16'(DEPTH)) n_overwritten <= n_overwritten + 32'd1;
          if (total_r != 16'hFFFF) total_r <= total_r + 16'd1;

          if (st_r == S_ARMED) begin
            if (pre_r != 16'hFFFF) pre_r <= pre_r + 16'd1;
          end else begin
            post_r <= post_r + 8'd1;
            // ---- The post-trigger window is the last thing that happens.
            //
            // POST_N events after the symptom and the capture stops. Every
            // one of them has already overwritten an oldest pre-trigger
            // entry, which is the cost nobody budgets for.
            if ((post_r + 8'd1) >= 8'(POST_N)) st_r <= S_FROZEN;
          end
        end

        // The trigger is sampled AFTER the write, so the event that caused
        // the symptom is itself the last pre-trigger entry rather than the
        // first post-trigger one. Off by one here moves the boundary of
        // every capture by one event, which is invisible until somebody
        // counts.
        if (trigger && (st_r == S_ARMED)) st_r <= S_CAPT;

        if (rd_en && (st_r == S_FROZEN)) begin
          if (rdi_r < n_valid) begin
            rdv_r <= 1'b1;
            rdi_r <= rdi_r + 8'd1;
            rdt_r <= ty_m[rd_addr];
            rde_r <= ep_m[rd_addr];
            rdc_r <= code_m[rd_addr];
            rdx_r <= rdi_r;
            rds_r <= view_mask[ty_m[rd_addr]];
            if (view_mask[ty_m[rd_addr]]) n_shown  <= n_shown  + 32'd1;
            else                          n_hidden <= n_hidden + 32'd1;
          end
        end
      end
    end
  end
endmodule

-- usb_trace_filter -- why the capture you took does not contain the bug, and
-- the two decisions that fix it.
--
-- A TRIGGER FIRES ON THE SYMPTOM, AND THE SYMPTOM IS THE END OF THE STORY
--
-- You set the analyser to trigger on a STALL. It triggers. You get a
-- beautiful capture of everything that happened AFTER the STALL: the host
-- giving up, the driver resetting the endpoint, the retry storm. None of
-- which is the bug.
--
-- The bug is whatever the firmware did three hundred transactions earlier
-- that made it decide to stall. That is in the part of the trace you did not
-- record, because you had not triggered yet.
--
--     A post-trigger-only capture records the AFTERMATH.
--     The cause is always before the trigger. Always.
--
-- THE FIX IS TO RECORD ALWAYS AND LET THE TRIGGER DECIDE WHAT TO KEEP
--
-- A circular buffer running the entire time. The trigger does not start the
-- recording; it STOPS it, some number of events later.
--
--     arm ----> [ always writing, oldest overwritten ] ----> trigger
--                            |<--- kept --->|<-- POST_N -->|
--
-- AND THE POST-TRIGGER WINDOW EATS THE PRE-TRIGGER HISTORY
--
-- The buffer is a fixed DEPTH. Every event captured after the trigger
-- overwrites the OLDEST pre-trigger entry, so asking for more post-trigger
-- context costs exactly that much pre-trigger context -- and the pre-trigger
-- context is where the bug is:
--
--     pre_kept = min(events before the trigger, DEPTH - post_kept)
--
-- THE SECOND TRAP: FILTERING AT CAPTURE TIME
--
-- "Just capture the errors" halves the file size and destroys the
-- investigation. The error is the symptom; the surrounding ordinary traffic
-- is the evidence.
--
--     Filter on the way OUT, never on the way IN.
--
-- So the view mask is applied at READ time. Every event is in the buffer;
-- the mask only decides what is shown, and the hidden ones are counted so
-- the number on screen is never mistaken for the number captured.
--
-- AND THE CAPTURE HAS TO SAY WHEN IT IS NOT LONG ENOUGH
--
-- If more events occurred before the trigger than the buffer could hold, the
-- cause may be off the front -- and a full buffer looks exactly like a
-- sufficient one. pre_lost is the difference between "the cause is not in
-- this capture" and "there is no cause", which are not the same finding.
library ieee;
use ieee.std_logic_1164.all;
use ieee.numeric_std.all;

package usb_trace_pkg is
  constant S_IDLE   : std_logic_vector(1 downto 0) := "00";
  constant S_ARMED  : std_logic_vector(1 downto 0) := "01";
  constant S_CAPT   : std_logic_vector(1 downto 0) := "10";
  constant S_FROZEN : std_logic_vector(1 downto 0) := "11";
end package;

library ieee;
use ieee.std_logic_1164.all;
use ieee.numeric_std.all;
use work.usb_trace_pkg.all;

entity usb_trace_filter is
  generic (
    DEPTH  : integer := 64;    -- circular buffer entries
    POST_N : integer := 8      -- events captured after the trigger
  );
  port (
    clk       : in  std_logic;
    rst_n     : in  std_logic;

    arm       : in  std_logic;                     -- begin a fresh capture
    ev_valid  : in  std_logic;
    ev_type   : in  std_logic_vector(1 downto 0);  -- token/data/hshk/error
    ev_ep     : in  std_logic_vector(3 downto 0);
    ev_code   : in  std_logic_vector(7 downto 0);
    trigger   : in  std_logic;                     -- the symptom fired

    rd_en     : in  std_logic;
    view_mask : in  std_logic_vector(3 downto 0);  -- applied ON READ

    state     : out std_logic_vector(1 downto 0);
    n_valid   : out unsigned(7 downto 0);          -- entries retained
    pre_kept  : out unsigned(7 downto 0);
    post_kept : out unsigned(7 downto 0);
    pre_lost  : out std_logic;                     -- cause may be off front

    rd_valid  : out std_logic;
    rd_show   : out std_logic;                     -- passes the view mask
    rd_type   : out std_logic_vector(1 downto 0);
    rd_ep     : out std_logic_vector(3 downto 0);
    rd_code   : out std_logic_vector(7 downto 0);
    rd_index  : out unsigned(7 downto 0);          -- 0 = oldest retained

    n_written     : out unsigned(31 downto 0);     -- every event. NEVER filtered.
    n_overwritten : out unsigned(31 downto 0);     -- lost to the circular buffer
    n_shown       : out unsigned(31 downto 0);
    n_hidden      : out unsigned(31 downto 0)      -- captured, not on screen
  );
end entity;

architecture rtl of usb_trace_filter is
  type ty_array   is array (0 to DEPTH-1) of std_logic_vector(1 downto 0);
  type ep_array   is array (0 to DEPTH-1) of std_logic_vector(3 downto 0);
  type code_array is array (0 to DEPTH-1) of std_logic_vector(7 downto 0);

  signal ty_m   : ty_array   := (others => (others => '0'));
  signal ep_m   : ep_array   := (others => (others => '0'));
  signal code_m : code_array := (others => (others => '0'));

  signal st_r    : std_logic_vector(1 downto 0) := S_IDLE;
  signal wr_r    : integer range 0 to DEPTH-1 := 0;
  signal total_r : unsigned(15 downto 0) := (others => '0');
  signal pre_r   : unsigned(15 downto 0) := (others => '0');
  signal post_r  : unsigned(7 downto 0)  := (others => '0');
  signal rdi_r   : unsigned(7 downto 0)  := (others => '0');
  signal rdv_r   : std_logic := '0';

  -- The read port is REGISTERED, all of it, together. A combinational read
  -- beside a registered rd_valid is off by one: the pointer advances on the
  -- same edge that raises valid, so the data presented alongside the valid
  -- pulse belongs to the NEXT entry. The symptom is a capture correct in
  -- every respect except that it starts one entry late and ends one early --
  -- exactly the defect a length check cannot see.
  signal rdt_r : std_logic_vector(1 downto 0) := (others => '0');
  signal rde_r : std_logic_vector(3 downto 0) := (others => '0');
  signal rdc_r : std_logic_vector(7 downto 0) := (others => '0');
  signal rdx_r : unsigned(7 downto 0) := (others => '0');
  signal rds_r : std_logic := '0';

  signal wrote_c, over_c, shown_c, hid_c : unsigned(31 downto 0)
    := (others => '0');

  -- Initialised at declaration. rd_addr is a concurrent expression over
  -- nval, so it evaluates at time 0 before any driver has resolved; left
  -- uninitialised these are all-U and numeric_std's to_integer emits a
  -- metavalue warning on every run. A warning that always fires is a
  -- warning nobody reads.
  signal post_k, room, pre_k, nval : unsigned(7 downto 0) := (others => '0');
  signal rd_addr : integer range 0 to DEPTH-1 := 0;
begin
  -- ---- What survived. ----
  --
  -- post_kept is however many post-trigger events were actually taken.
  -- pre_kept is what the buffer had room for AFTER those, which is the
  -- subtraction that surprises people.
  post_k <= post_r;
  room   <= to_unsigned(DEPTH, 8) - post_k when to_unsigned(DEPTH, 8) > post_k
            else (others => '0');
  pre_k  <= room when pre_r > resize(room, 16) else pre_r(7 downto 0);
  nval   <= pre_k + post_k;

  state     <= st_r;
  pre_kept  <= pre_k;
  post_kept <= post_k;
  n_valid   <= nval;
  -- The cause may be off the front, and a full buffer looks exactly like a
  -- sufficient one. This bit is the difference between "not in this capture"
  -- and "no such event".
  pre_lost  <= '1' when pre_r > resize(room, 16) else '0';

  -- ---- The read window. ----
  --
  -- Chronological, oldest first. The oldest retained entry is n_valid slots
  -- behind the write pointer, modulo the buffer -- the only place the
  -- circularity is visible, and the only place it can be got wrong.
  rd_addr <= (wr_r - to_integer(nval) + to_integer(rdi_r) + 2*DEPTH) mod DEPTH;

  rd_valid <= rdv_r;
  rd_type  <= rdt_r;
  rd_ep    <= rde_r;
  rd_code  <= rdc_r;
  rd_index <= rdx_r;
  rd_show  <= rds_r;

  n_written     <= wrote_c;
  n_overwritten <= over_c;
  n_shown       <= shown_c;
  n_hidden      <= hid_c;

  process (clk, rst_n)
  begin
    if rst_n = '0' then
      st_r    <= S_IDLE;
      wr_r    <= 0;
      total_r <= (others => '0');
      pre_r   <= (others => '0');
      post_r  <= (others => '0');
      rdi_r   <= (others => '0');
      rdv_r   <= '0';
      rdt_r   <= (others => '0');
      rde_r   <= (others => '0');
      rdc_r   <= (others => '0');
      rdx_r   <= (others => '0');
      rds_r   <= '0';
      wrote_c <= (others => '0');
      over_c  <= (others => '0');
      shown_c <= (others => '0');
      hid_c   <= (others => '0');
      ty_m    <= (others => (others => '0'));
      ep_m    <= (others => (others => '0'));
      code_m  <= (others => (others => '0'));
    elsif rising_edge(clk) then
      rdv_r <= '0';

      if arm = '1' then
        st_r    <= S_ARMED;
        wr_r    <= 0;
        total_r <= (others => '0');
        pre_r   <= (others => '0');
        post_r  <= (others => '0');
        rdi_r   <= (others => '0');
      else
        -- ---- WRITE FIRST, unconditionally, with no filter of any kind. ----
        --
        -- Not "write if it is an error", not "write if it matches the mask".
        -- The mask lives on the read side and nowhere else; the moment a
        -- filter appears here, the context that explains the error is gone
        -- and no amount of later processing brings it back.
        if ev_valid = '1' and (st_r = S_ARMED or st_r = S_CAPT) then
          ty_m(wr_r)   <= ev_type;
          ep_m(wr_r)   <= ev_ep;
          code_m(wr_r) <= ev_code;
          if wr_r = DEPTH-1 then wr_r <= 0; else wr_r <= wr_r + 1; end if;
          wrote_c <= wrote_c + 1;
          if total_r >= to_unsigned(DEPTH, 16) then over_c <= over_c + 1; end if;
          if total_r /= x"FFFF" then total_r <= total_r + 1; end if;

          if st_r = S_ARMED then
            if pre_r /= x"FFFF" then pre_r <= pre_r + 1; end if;
          else
            post_r <= post_r + 1;
            -- ---- The post-trigger window is the last thing that happens.
            --
            -- POST_N events after the symptom and the capture stops. Every
            -- one of them has already overwritten an oldest pre-trigger
            -- entry, which is the cost nobody budgets for.
            if (post_r + 1) >= to_unsigned(POST_N, 8) then
              st_r <= S_FROZEN;
            end if;
          end if;
        end if;

        -- The trigger is sampled AFTER the write, so the event that caused
        -- the symptom is itself the last pre-trigger entry rather than the
        -- first post-trigger one. Off by one here moves the boundary of
        -- every capture by one event, which is invisible until somebody
        -- counts.
        if trigger = '1' and st_r = S_ARMED then
          st_r <= S_CAPT;
        end if;

        if rd_en = '1' and st_r = S_FROZEN then
          if rdi_r < nval then
            rdv_r <= '1';
            rdi_r <= rdi_r + 1;
            rdt_r <= ty_m(rd_addr);
            rde_r <= ep_m(rd_addr);
            rdc_r <= code_m(rd_addr);
            rdx_r <= rdi_r;
            rds_r <= view_mask(to_integer(unsigned(ty_m(rd_addr))));
            if view_mask(to_integer(unsigned(ty_m(rd_addr)))) = '1' then
              shown_c <= shown_c + 1;
            else
              hid_c <= hid_c + 1;
            end if;
          end if;
        end if;
      end if;
    end if;
  end process;
end architecture;

   The arithmetic changes behaviour at exactly one place:

       DEPTH - POST_N

   below it, everything before the trigger survives
   above it, the oldest entries are gone and pre_lost must say so

   Phase 1 sweeps the pre-trigger count 0 .. DEPTH + 8 --
   every value on both sides and well past -- and drains and
   compares the entire capture on each of the 73 runs.

   result: 57 intact, 16 lost

`timescale 1ns/1ps
// Testbench for usb_trace_filter.
//
// THE CLAIM IS ABOUT WHAT SURVIVES, SO THE WHOLE CAPTURE IS COMPARED
//
// It is not enough to check that the block retained the right NUMBER of
// events. The failure this chapter is about is a capture that contains the
// wrong events -- the aftermath instead of the cause -- and a count cannot
// tell those apart. So every retained entry is drained and compared, in
// order, against an independently kept list of everything that was offered.
//
// THE EXHAUSTIVE CLAIM
//
// The retention arithmetic depends on how many events preceded the trigger,
// and it changes behaviour at exactly one place: DEPTH - POST_N, where the
// buffer stops being able to hold all of them. So phase 1 sweeps the
// pre-trigger event count from 0 to DEPTH + 8 -- every value on both sides
// of that edge and well past it -- and for each one drains the entire
// capture and compares it entry by entry.
module tb_tf_v;

  localparam integer DEPTH  = 64;
  localparam integer POST_N = 8;
  localparam integer MAXEV  = 400;

  localparam [1:0] S_IDLE = 2'd0, S_ARMED = 2'd1,
                   S_CAPT = 2'd2, S_FROZEN = 2'd3;

  reg        clk = 1'b0, rst_n = 1'b0;
  reg        arm = 1'b0, ev_valid = 1'b0, trigger = 1'b0, rd_en = 1'b0;
  reg [1:0]  ev_type = 2'd0;
  reg [3:0]  ev_ep = 4'd0;
  reg [7:0]  ev_code = 8'd0;
  reg [3:0]  view_mask = 4'hF;

  wire [1:0] state, rd_type;
  wire [7:0] n_valid, pre_kept, post_kept, rd_code, rd_index;
  wire [3:0] rd_ep;
  wire       pre_lost, rd_valid, rd_show;
  wire [31:0] n_written, n_overwritten, n_shown, n_hidden;

  usb_trace_filter #(.DEPTH(DEPTH), .POST_N(POST_N)) dut (
    .clk(clk), .rst_n(rst_n),
    .arm(arm), .ev_valid(ev_valid), .ev_type(ev_type), .ev_ep(ev_ep),
    .ev_code(ev_code), .trigger(trigger),
    .rd_en(rd_en), .view_mask(view_mask),
    .state(state), .n_valid(n_valid), .pre_kept(pre_kept),
    .post_kept(post_kept), .pre_lost(pre_lost),
    .rd_valid(rd_valid), .rd_show(rd_show), .rd_type(rd_type),
    .rd_ep(rd_ep), .rd_code(rd_code), .rd_index(rd_index),
    .n_written(n_written), .n_overwritten(n_overwritten),
    .n_shown(n_shown), .n_hidden(n_hidden)
  );

  always #5 clk = ~clk;

  // ---------------- the reference list ----------------
  //
  // Everything that was offered while the block was recording, in order.
  // The expected capture is a WINDOW into this list, and computing that
  // window from the chapter's rules is the whole oracle.
  reg [1:0] a_ty   [0:MAXEV-1];
  reg [3:0] a_ep   [0:MAXEV-1];
  reg [7:0] a_code [0:MAXEV-1];
  integer   n_all, n_pre;

  // ---------------- the shadow model of the recorder ----------------
  //
  // The drain comparison proves the CONTENTS. This proves the machine that
  // produced them: what state it is in, how much it wrote, and how much it
  // threw away -- every cycle, including the cycles where nothing happens,
  // because "nothing happens" is a claim too.
  reg [1:0]  m_state;
  integer    m_written, m_overwritten, m_total, m_post;

  integer errors = 0, checks = 0, steps = 0;
  integer k;

  reg [0:0] reach [0:15];    // state (4) x event type (4)
  integer   n_reach;

  task ck;
    input [255:0] nm;
    input [31:0]  got, exp;
    begin
      checks = checks + 1;
      if (got !== exp) begin
        errors = errors + 1;
        if (errors < 25)
          $display("FAIL t=%0t step=%0d %0s got=%0d exp=%0d",
                   $time, steps, nm, got, exp);
      end
    end
  endtask

  task model_cycle;
    begin
      if (arm) begin
        m_state = S_ARMED;
        m_total = 0;
        m_post  = 0;
      end else begin
        if (ev_valid && ((m_state == S_ARMED) || (m_state == S_CAPT))) begin
          m_written = m_written + 1;
          if (m_total >= DEPTH) m_overwritten = m_overwritten + 1;
          m_total = m_total + 1;
          if (m_state == S_CAPT) begin
            m_post = m_post + 1;
            if (m_post >= POST_N) m_state = S_FROZEN;
          end
        end
        // Sampled AFTER the write, so an event on the trigger cycle belongs
        // to the PRE side.
        if (trigger && (m_state == S_ARMED)) m_state = S_CAPT;
      end
    end
  endtask

  task tickc;
    begin
      model_cycle;
      @(posedge clk); #1;
      steps = steps + 1;
      ck("state",         {30'd0, state}, {30'd0, m_state});
      ck("n_written",     n_written,      m_written[31:0]);
      ck("n_overwritten", n_overwritten,  m_overwritten[31:0]);
    end
  endtask

  task do_arm;
    begin
      arm = 1'b1; ev_valid = 1'b0; trigger = 1'b0; rd_en = 1'b0;
      tickc;
      arm = 1'b0;
      n_all = 0; n_pre = 0;
    end
  endtask

  task ev; input [1:0] t; input [3:0] e; input [7:0] c;
    begin
      arm = 1'b0; ev_valid = 1'b1; trigger = 1'b0; rd_en = 1'b0;
      ev_type = t; ev_ep = e; ev_code = c;
      reach[{state, t}] = 1'b1;
      if ((state == S_ARMED) || (state == S_CAPT)) begin
        a_ty[n_all] = t; a_ep[n_all] = e; a_code[n_all] = c;
        n_all = n_all + 1;
        if (state == S_ARMED) n_pre = n_pre + 1;
      end
      tickc;
      ev_valid = 1'b0;
    end
  endtask

  task trig;
    begin
      arm = 1'b0; ev_valid = 1'b0; trigger = 1'b1; rd_en = 1'b0;
      tickc;
      trigger = 1'b0;
    end
  endtask

  task nothing;
    begin
      arm = 1'b0; ev_valid = 1'b0; trigger = 1'b0; rd_en = 1'b0;
      tickc;
    end
  endtask

  // ---- The expected retained window, from the chapter's rules. ----
  //
  //   post_kept = however many post-trigger events were taken
  //   pre_kept  = min(pre_total, DEPTH - post_kept)
  //
  // The subtraction is the point: every post-trigger event overwrote an
  // oldest pre-trigger one, so asking for more aftermath costs exactly that
  // much of the cause.
  function integer exp_post; input integer dummy;
    begin
      exp_post = n_all - n_pre;
      if (exp_post > POST_N) exp_post = POST_N;
    end
  endfunction

  function integer exp_pre; input integer dummy;
    integer room;
    begin
      room = DEPTH - exp_post(0);
      exp_pre = (n_pre > room) ? room : n_pre;
    end
  endfunction

  // Drain the whole capture and compare every entry, in order, against the
  // reference list. Returns the number of entries the view mask showed.
  task drain_and_check;
    integer want, first, idx, shown, hidden;
    begin
      want  = exp_pre(0) + exp_post(0);
      first = n_all - want;
      ck("n_valid",   {24'd0, n_valid},   want[31:0]);
      ck("pre_kept",  {24'd0, pre_kept},  exp_pre(0));
      ck("post_kept", {24'd0, post_kept}, exp_post(0));
      // The cause may be off the front, and a full buffer looks exactly like
      // a sufficient one.
      ck("pre_lost",  {31'd0, pre_lost},
         (n_pre > (DEPTH - exp_post(0))) ? 32'd1 : 32'd0);

      shown = 0; hidden = 0;
      for (idx = 0; idx < want; idx = idx + 1) begin
        rd_en = 1'b1;
        model_cycle;
        @(posedge clk); #1;
        steps = steps + 1;
        ck("state",         {30'd0, state}, {30'd0, m_state});
        ck("n_written",     n_written,      m_written[31:0]);
        ck("n_overwritten", n_overwritten,  m_overwritten[31:0]);
        ck("rd_valid", {31'd0, rd_valid}, 32'd1);
        ck("rd_index", {24'd0, rd_index}, idx[31:0]);
        // ---- The summary outputs are re-checked on every drain cycle. ----
        //
        // They are stable while frozen, so checking them once per capture is
        // "enough" in the sense that it catches a wrong value. It is not
        // enough in the sense that matters: pre_lost is the difference
        // between "the cause is not in this capture" and "there is no
        // cause", and a mutation that hard-wires it low was dying on ONE
        // check per capture. Re-checking it per entry costs nothing and
        // turns a cornered mutation into a killed one.
        ck("pre_lost stable",  {31'd0, pre_lost},
           (n_pre > (DEPTH - exp_post(0))) ? 32'd1 : 32'd0);
        ck("n_valid stable",   {24'd0, n_valid},   want[31:0]);
        ck("pre_kept stable",  {24'd0, pre_kept},  exp_pre(0));
        ck("post_kept stable", {24'd0, post_kept}, exp_post(0));
        // THE check. Not the count -- the contents, in order.
        ck("rd_type",  {30'd0, rd_type},  {30'd0, a_ty[first + idx]});
        ck("rd_ep",    {28'd0, rd_ep},    {28'd0, a_ep[first + idx]});
        ck("rd_code",  {24'd0, rd_code},  {24'd0, a_code[first + idx]});
        ck("rd_show",  {31'd0, rd_show},
           {31'd0, view_mask[a_ty[first + idx]]});
        if (view_mask[a_ty[first + idx]]) shown = shown + 1;
        else                              hidden = hidden + 1;
      end
      rd_en = 1'b0;
      // Reading past the end yields nothing at all rather than wrapping
      // round to the oldest entry again.
      rd_en = 1'b1;
      model_cycle;
      @(posedge clk); #1;
      steps = steps + 1;
      ck("rd_valid past end", {31'd0, rd_valid}, 32'd0);
      rd_en = 1'b0;
    end
  endtask

  integer p, i, m, w, base_shown, base_hidden;
  integer n_lost_cases, n_intact_cases;
  reg [1:0] save_ty [0:DEPTH-1];

  initial begin
    for (k = 0; k < 16; k = k + 1) reach[k] = 1'b0;
    n_all = 0; n_pre = 0;
    n_lost_cases = 0; n_intact_cases = 0;
    m_state = S_IDLE; m_written = 0; m_overwritten = 0;
    m_total = 0; m_post = 0;

    repeat (3) @(posedge clk);
    rst_n = 1'b1;
    @(negedge clk);

    // ================= PHASE 0 -- traffic before the capture is armed =====
    //
    // Every event type offered while the block is IDLE. None of it may be
    // recorded: a capture that quietly began before it was armed contains
    // events from whatever the bus was doing last time, in the same buffer,
    // with no marker between them.
    for (i = 0; i < 4; i = i + 1) ev(i[1:0], 4'd9, 8'h70 + i[7:0]);
    ck("idle state",       {30'd0, state}, {30'd0, S_IDLE});
    ck("nothing written",  n_written,      32'd0);

    // ================= PHASE 1 -- THE RETENTION EDGE, SWEPT ==============
    //
    // Every pre-trigger event count from 0 to DEPTH + 8. Below
    // DEPTH - POST_N everything before the trigger survives; above it the
    // oldest entries are gone and pre_lost must say so. The whole capture is
    // drained and compared entry by entry on every one of the 73 runs.
    for (p = 0; p <= DEPTH + 8; p = p + 1) begin
      do_arm;
      for (i = 0; i < p; i = i + 1)
        ev(i[1:0], i[3:0], i[7:0] + 8'd1);
      trig;
      for (i = 0; i < POST_N; i = i + 1)
        ev(2'd3, 4'hF, 8'hA0 + i[7:0]);
      ck("frozen", {30'd0, state}, {30'd0, S_FROZEN});
      drain_and_check;
      if (p > DEPTH - POST_N) n_lost_cases   = n_lost_cases + 1;
      else                    n_intact_cases = n_intact_cases + 1;
    end
    if (n_lost_cases != 16 || n_intact_cases != 57) begin
      errors = errors + 1;
      $display("FAIL edge split: lost=%0d intact=%0d expected 16 and 57",
               n_lost_cases, n_intact_cases);
    end

    // ================= PHASE 2 -- the trigger is sampled AFTER the write ==
    //
    // An event and the trigger on the same cycle: the event belongs to the
    // PRE side, because it is part of what led up to the symptom rather than
    // part of the aftermath. Off by one here moves the boundary of every
    // capture by one event, which is invisible until somebody counts.
    do_arm;
    for (i = 0; i < 10; i = i + 1) ev(2'd0, 4'd1, i[7:0] + 8'd1);
    arm = 1'b0; ev_valid = 1'b1; trigger = 1'b1; rd_en = 1'b0;
    ev_type = 2'd1; ev_ep = 4'd2; ev_code = 8'h5A;
    a_ty[n_all] = 2'd1; a_ep[n_all] = 4'd2; a_code[n_all] = 8'h5A;
    n_all = n_all + 1; n_pre = n_pre + 1;
    tickc;
    ev_valid = 1'b0; trigger = 1'b0;
    ck("state after simultaneous trigger", {30'd0, state}, {30'd0, S_CAPT});
    for (i = 0; i < POST_N; i = i + 1) ev(2'd3, 4'hF, 8'hB0 + i[7:0]);
    ck("pre_kept with simultaneous trigger", {24'd0, pre_kept}, 32'd11);
    drain_and_check;

    // ================= PHASE 3 -- the mask hides, it does not delete =====
    //
    // The same capture drained under all 16 view masks. The CONTENTS are
    // identical every time; only rd_show changes. A design that filtered on
    // the way in would return a different capture for each mask, and the
    // context that explains the error would be gone for fifteen of them.
    do_arm;
    for (i = 0; i < 40; i = i + 1) ev(i[1:0], i[3:0], i[7:0] + 8'd1);
    trig;
    for (i = 0; i < POST_N; i = i + 1) ev(2'd2, 4'd7, 8'hC0 + i[7:0]);
    for (m = 0; m < 16; m = m + 1) begin
      // Re-drain from the start. rd_index is only reset by a fresh arm, so
      // the capture is re-created identically instead -- which also proves
      // that an identical stimulus produces an identical capture.
      do_arm;
      for (i = 0; i < 40; i = i + 1) ev(i[1:0], i[3:0], i[7:0] + 8'd1);
      trig;
      for (i = 0; i < POST_N; i = i + 1) ev(2'd2, 4'd7, 8'hC0 + i[7:0]);
      view_mask = m[3:0];
      base_shown = n_shown; base_hidden = n_hidden;
      drain_and_check;
      // Everything drained is either shown or hidden, and nothing is lost.
      ck("shown + hidden",
         (n_shown - base_shown) + (n_hidden - base_hidden),
         {24'd0, n_valid});
    end
    view_mask = 4'hF;

    // ================= PHASE 4 -- draining before the freeze yields none ==
    do_arm;
    for (i = 0; i < 20; i = i + 1) ev(2'd0, 4'd3, i[7:0] + 8'd1);
    trig;
    ev(2'd3, 4'd3, 8'hD0);
    ck("still capturing", {30'd0, state}, {30'd0, S_CAPT});
    rd_en = 1'b1;
    model_cycle;
    @(posedge clk); #1; steps = steps + 1;
    ck("no drain while capturing", {31'd0, rd_valid}, 32'd0);
    rd_en = 1'b0;

    // ================= PHASE 5 -- re-arming throws the capture away ======
    //
    // And it must throw away the pre-trigger count with it. A stale pre_r
    // makes the NEXT capture report a pre_lost it did not earn.
    do_arm;
    for (i = 0; i < 5; i = i + 1) ev(2'd1, 4'd4, i[7:0] + 8'd1);
    trig;
    for (i = 0; i < POST_N; i = i + 1) ev(2'd3, 4'hE, 8'hE0 + i[7:0]);
    ck("re-armed pre_kept", {24'd0, pre_kept}, 32'd5);
    ck("re-armed pre_lost", {31'd0, pre_lost}, 32'd0);

    // ---- Traffic AFTER the freeze must not touch the capture. ----
    //
    // The bus does not stop because you triggered. If a frozen capture keeps
    // absorbing events, the trace changes while you are reading it -- and
    // the entries you already looked at are no longer the entries that are
    // there. Every type is offered, and the drain below is compared against
    // the model as though none of them happened, because none of them may.
    base_shown = n_written;
    for (i = 0; i < 4; i = i + 1) ev(i[1:0], 4'hA, 8'hF0 + i[7:0]);
    ck("frozen: nothing written", n_written, base_shown[31:0]);
    ck("frozen: still frozen",    {30'd0, state}, {30'd0, S_FROZEN});
    drain_and_check;

    // ================= PHASE 6 -- random ================================
    //
    // Random capture lengths and random event mixes, every one of them
    // drained and compared in full.
    for (i = 0; i < 300; i = i + 1) begin
      do_arm;
      w = $unsigned($random) % 90;
      for (p = 0; p < w; p = p + 1)
        ev($unsigned($random) % 4, $unsigned($random) % 16,
           $unsigned($random) % 256);
      trig;
      for (p = 0; p < POST_N; p = p + 1)
        ev($unsigned($random) % 4, $unsigned($random) % 16,
           $unsigned($random) % 256);
      view_mask = $unsigned($random) % 16;
      drain_and_check;
    end
    view_mask = 4'hF;

    // ================= the exhaustiveness proof ==========================
    n_reach = 0;
    for (k = 0; k < 16; k = k + 1) n_reach = n_reach + reach[k];
    if (n_reach != 16) begin
      errors = errors + 1;
      $display("FAIL state x type reach %0d/16", n_reach);
      for (k = 0; k < 16; k = k + 1)
        if (!reach[k]) $display("  unreached state=%0d type=%0d", k >> 2, k & 3);
    end

    $display("steps=%0d checks=%0d reach=%0d/16 errors=%0d",
             steps, checks, n_reach, errors);
    $display("retention edge: intact=%0d lost=%0d",
             n_intact_cases, n_lost_cases);
    $display("written=%0d overwritten=%0d shown=%0d hidden=%0d",
             n_written, n_overwritten, n_shown, n_hidden);
    $display("%0s: %0d errors in %0d checks",
             (errors == 0) ? "PASS" : "FAIL", errors, checks);
    $finish;
  end
endmodule

`timescale 1ns/1ps
// Testbench for usb_trace_filter.
//
// THE CLAIM IS ABOUT WHAT SURVIVES, SO THE WHOLE CAPTURE IS COMPARED
//
// It is not enough to check that the block retained the right NUMBER of
// events. The failure this chapter is about is a capture that contains the
// wrong events -- the aftermath instead of the cause -- and a count cannot
// tell those apart. So every retained entry is drained and compared, in
// order, against an independently kept list of everything that was offered.
//
// THE EXHAUSTIVE CLAIM
//
// The retention arithmetic depends on how many events preceded the trigger,
// and it changes behaviour at exactly one place: DEPTH - POST_N, where the
// buffer stops being able to hold all of them. So phase 1 sweeps the
// pre-trigger event count from 0 to DEPTH + 8 -- every value on both sides
// of that edge and well past it -- and for each one drains the entire
// capture and compares it entry by entry.
module tb_tf_sv;
  import usb_trace_pkg::*;

  localparam int DEPTH  = 64;
  localparam int POST_N = 8;
  localparam int MAXEV  = 400;

  logic       clk = 1'b0, rst_n = 1'b0;
  logic       arm = 1'b0, ev_valid = 1'b0, trigger = 1'b0, rd_en = 1'b0;
  ev_type_e   ev_type = EV_TOKEN;
  logic [3:0] ev_ep = 4'd0;
  logic [7:0] ev_code = 8'd0;
  logic [3:0] view_mask = 4'hF;

  cap_state_e state;
  ev_type_e   rd_type;
  logic [7:0] n_valid, pre_kept, post_kept, rd_code, rd_index;
  logic [3:0] rd_ep;
  logic       pre_lost, rd_valid, rd_show;
  logic [31:0] n_written, n_overwritten, n_shown, n_hidden;

  usb_trace_filter #(.DEPTH(DEPTH), .POST_N(POST_N)) dut (
    .clk(clk), .rst_n(rst_n),
    .arm(arm), .ev_valid(ev_valid), .ev_type(ev_type), .ev_ep(ev_ep),
    .ev_code(ev_code), .trigger(trigger),
    .rd_en(rd_en), .view_mask(view_mask),
    .state(state), .n_valid(n_valid), .pre_kept(pre_kept),
    .post_kept(post_kept), .pre_lost(pre_lost),
    .rd_valid(rd_valid), .rd_show(rd_show), .rd_type(rd_type),
    .rd_ep(rd_ep), .rd_code(rd_code), .rd_index(rd_index),
    .n_written(n_written), .n_overwritten(n_overwritten),
    .n_shown(n_shown), .n_hidden(n_hidden)
  );

  always #5 clk = ~clk;

  // ---------------- the reference list ----------------
  //
  // Everything that was offered while the block was recording, in order.
  // The expected capture is a WINDOW into this list, and computing that
  // window from the chapter's rules is the whole oracle.
  ev_type_e   a_ty   [MAXEV-1:0];
  logic [3:0] a_ep   [MAXEV-1:0];
  logic [7:0] a_code [MAXEV-1:0];
  int         n_all, n_pre;

  // ---------------- the shadow model of the recorder ----------------
  //
  // The drain comparison proves the CONTENTS. This proves the machine that
  // produced them: what state it is in, how much it wrote, and how much it
  // threw away -- every cycle, including the cycles where nothing happens,
  // because "nothing happens" is a claim too.
  cap_state_e m_state;
  int         m_written, m_overwritten, m_total, m_post;

  int errors = 0, checks = 0, steps = 0;
  int k;

  bit reach [16];            // state (4) x event type (4)
  int n_reach;

  task automatic ck(string nm, int unsigned got, int unsigned exp);
    checks++;
    if (got !== exp) begin
      errors++;
      if (errors < 25)
        $display("FAIL t=%0t step=%0d %0s got=%0d exp=%0d",
                 $time, steps, nm, got, exp);
    end
  endtask

  task automatic model_cycle;
    begin
      if (arm) begin
        m_state = S_ARMED;
        m_total = 0;
        m_post  = 0;
      end else begin
        if (ev_valid && ((m_state == S_ARMED) || (m_state == S_CAPT))) begin
          m_written = m_written + 1;
          if (m_total >= DEPTH) m_overwritten = m_overwritten + 1;
          m_total = m_total + 1;
          if (m_state == S_CAPT) begin
            m_post = m_post + 1;
            if (m_post >= POST_N) m_state = S_FROZEN;
          end
        end
        // Sampled AFTER the write, so an event on the trigger cycle belongs
        // to the PRE side.
        if (trigger && (m_state == S_ARMED)) m_state = S_CAPT;
      end
    end
  endtask

  task automatic tickc;
    begin
      model_cycle;
      @(posedge clk); #1;
      steps = steps + 1;
      ck("state",         state, m_state);
      ck("n_written",     n_written,      m_written[31:0]);
      ck("n_overwritten", n_overwritten,  m_overwritten[31:0]);
    end
  endtask

  task automatic do_arm;
    begin
      arm = 1'b1; ev_valid = 1'b0; trigger = 1'b0; rd_en = 1'b0;
      tickc;
      arm = 1'b0;
      n_all = 0; n_pre = 0;
    end
  endtask

  task automatic ev(ev_type_e t, logic [3:0] e, logic [7:0] c);
    begin
      arm = 1'b0; ev_valid = 1'b1; trigger = 1'b0; rd_en = 1'b0;
      ev_type = t; ev_ep = e; ev_code = c;
      reach[int'(state) * 4 + int'(t)] = 1'b1;
      if ((state == S_ARMED) || (state == S_CAPT)) begin
        a_ty[n_all] = t; a_ep[n_all] = e; a_code[n_all] = c;
        n_all = n_all + 1;
        if (state == S_ARMED) n_pre = n_pre + 1;
      end
      tickc;
      ev_valid = 1'b0;
    end
  endtask

  task automatic trig;
    begin
      arm = 1'b0; ev_valid = 1'b0; trigger = 1'b1; rd_en = 1'b0;
      tickc;
      trigger = 1'b0;
    end
  endtask

  task automatic nothing;
    begin
      arm = 1'b0; ev_valid = 1'b0; trigger = 1'b0; rd_en = 1'b0;
      tickc;
    end
  endtask

  // ---- The expected retained window, from the chapter's rules. ----
  //
  //   post_kept = however many post-trigger events were taken
  //   pre_kept  = min(pre_total, DEPTH - post_kept)
  //
  // The subtraction is the point: every post-trigger event overwrote an
  // oldest pre-trigger one, so asking for more aftermath costs exactly that
  // much of the cause.
  function automatic int exp_post(input int dummy);
    begin
      exp_post = n_all - n_pre;
      if (exp_post > POST_N) exp_post = POST_N;
    end
  endfunction

  function automatic int exp_pre(input int dummy);
    int room;
    begin
      room = DEPTH - exp_post(0);
      exp_pre = (n_pre > room) ? room : n_pre;
    end
  endfunction

  // Drain the whole capture and compare every entry, in order, against the
  // reference list. Returns the number of entries the view mask showed.
  task automatic drain_and_check;
    int want, first, idx, shown, hidden;
    begin
      want  = exp_pre(0) + exp_post(0);
      first = n_all - want;
      ck("n_valid",   {24'd0, n_valid},   want[31:0]);
      ck("pre_kept",  {24'd0, pre_kept},  exp_pre(0));
      ck("post_kept", {24'd0, post_kept}, exp_post(0));
      // The cause may be off the front, and a full buffer looks exactly like
      // a sufficient one.
      ck("pre_lost",  {31'd0, pre_lost},
         (n_pre > (DEPTH - exp_post(0))) ? 32'd1 : 32'd0);

      shown = 0; hidden = 0;
      for (idx = 0; idx < want; idx = idx + 1) begin
        rd_en = 1'b1;
        model_cycle;
        @(posedge clk); #1;
        steps = steps + 1;
        ck("state",         state, m_state);
        ck("n_written",     n_written,      m_written[31:0]);
        ck("n_overwritten", n_overwritten,  m_overwritten[31:0]);
        ck("rd_valid", {31'd0, rd_valid}, 32'd1);
        ck("rd_index", {24'd0, rd_index}, idx[31:0]);
        // ---- The summary outputs are re-checked on every drain cycle. ----
        //
        // They are stable while frozen, so checking them once per capture is
        // "enough" in the sense that it catches a wrong value. It is not
        // enough in the sense that matters: pre_lost is the difference
        // between "the cause is not in this capture" and "there is no
        // cause", and a mutation that hard-wires it low was dying on ONE
        // check per capture. Re-checking it per entry costs nothing and
        // turns a cornered mutation into a killed one.
        ck("pre_lost stable",  {31'd0, pre_lost},
           (n_pre > (DEPTH - exp_post(0))) ? 32'd1 : 32'd0);
        ck("n_valid stable",   {24'd0, n_valid},   want[31:0]);
        ck("pre_kept stable",  {24'd0, pre_kept},  exp_pre(0));
        ck("post_kept stable", {24'd0, post_kept}, exp_post(0));
        // THE check. Not the count -- the contents, in order.
        ck("rd_type",  rd_type, a_ty[first + idx]);
        ck("rd_ep",    {28'd0, rd_ep},    {28'd0, a_ep[first + idx]});
        ck("rd_code",  {24'd0, rd_code},  {24'd0, a_code[first + idx]});
        ck("rd_show",  {31'd0, rd_show},
           {31'd0, view_mask[int'(a_ty[first + idx])]});
        if (view_mask[int'(a_ty[first + idx])]) shown = shown + 1;
        else                              hidden = hidden + 1;
      end
      rd_en = 1'b0;
      // Reading past the end yields nothing at all rather than wrapping
      // round to the oldest entry again.
      rd_en = 1'b1;
      model_cycle;
      @(posedge clk); #1;
      steps = steps + 1;
      ck("rd_valid past end", {31'd0, rd_valid}, 32'd0);
      rd_en = 1'b0;
    end
  endtask

  int p, i, m, w, base_shown, base_hidden;
  int n_lost_cases, n_intact_cases;

  initial begin
    foreach (reach[q]) reach[q] = 1'b0;
    n_all = 0; n_pre = 0;
    n_lost_cases = 0; n_intact_cases = 0;
    m_state = S_IDLE; m_written = 0; m_overwritten = 0;
    m_total = 0; m_post = 0;

    repeat (3) @(posedge clk);
    rst_n = 1'b1;
    @(negedge clk);

    // ================= PHASE 0 -- traffic before the capture is armed =====
    //
    // Every event type offered while the block is IDLE. None of it may be
    // recorded: a capture that quietly began before it was armed contains
    // events from whatever the bus was doing last time, in the same buffer,
    // with no marker between them.
    for (i = 0; i < 4; i = i + 1) ev(ev_type_e'(i[1:0]), 4'd9, 8'h70 + i[7:0]);
    ck("idle state",       state, S_IDLE);
    ck("nothing written",  n_written,      32'd0);

    // ================= PHASE 1 -- THE RETENTION EDGE, SWEPT ==============
    //
    // Every pre-trigger event count from 0 to DEPTH + 8. Below
    // DEPTH - POST_N everything before the trigger survives; above it the
    // oldest entries are gone and pre_lost must say so. The whole capture is
    // drained and compared entry by entry on every one of the 73 runs.
    for (p = 0; p <= DEPTH + 8; p = p + 1) begin
      do_arm;
      for (i = 0; i < p; i = i + 1)
        ev(ev_type_e'(i[1:0]), i[3:0], i[7:0] + 8'd1);
      trig;
      for (i = 0; i < POST_N; i = i + 1)
        ev(EV_ERROR, 4'hF, 8'hA0 + i[7:0]);
      ck("frozen", state, S_FROZEN);
      drain_and_check;
      if (p > DEPTH - POST_N) n_lost_cases   = n_lost_cases + 1;
      else                    n_intact_cases = n_intact_cases + 1;
    end
    if (n_lost_cases != 16 || n_intact_cases != 57) begin
      errors = errors + 1;
      $display("FAIL edge split: lost=%0d intact=%0d expected 16 and 57",
               n_lost_cases, n_intact_cases);
    end

    // ================= PHASE 2 -- the trigger is sampled AFTER the write ==
    //
    // An event and the trigger on the same cycle: the event belongs to the
    // PRE side, because it is part of what led up to the symptom rather than
    // part of the aftermath. Off by one here moves the boundary of every
    // capture by one event, which is invisible until somebody counts.
    do_arm;
    for (i = 0; i < 10; i = i + 1) ev(EV_TOKEN, 4'd1, i[7:0] + 8'd1);
    arm = 1'b0; ev_valid = 1'b1; trigger = 1'b1; rd_en = 1'b0;
    ev_type = EV_DATA; ev_ep = 4'd2; ev_code = 8'h5A;
    a_ty[n_all] = EV_DATA; a_ep[n_all] = 4'd2; a_code[n_all] = 8'h5A;
    n_all = n_all + 1; n_pre = n_pre + 1;
    tickc;
    ev_valid = 1'b0; trigger = 1'b0;
    ck("state after simultaneous trigger", state, S_CAPT);
    for (i = 0; i < POST_N; i = i + 1) ev(EV_ERROR, 4'hF, 8'hB0 + i[7:0]);
    ck("pre_kept with simultaneous trigger", {24'd0, pre_kept}, 32'd11);
    drain_and_check;

    // ================= PHASE 3 -- the mask hides, it does not delete =====
    //
    // The same capture drained under all 16 view masks. The CONTENTS are
    // identical every time; only rd_show changes. A design that filtered on
    // the way in would return a different capture for each mask, and the
    // context that explains the error would be gone for fifteen of them.
    do_arm;
    for (i = 0; i < 40; i = i + 1) ev(ev_type_e'(i[1:0]), i[3:0], i[7:0] + 8'd1);
    trig;
    for (i = 0; i < POST_N; i = i + 1) ev(EV_HSHK, 4'd7, 8'hC0 + i[7:0]);
    for (m = 0; m < 16; m = m + 1) begin
      // Re-drain from the start. rd_index is only reset by a fresh arm, so
      // the capture is re-created identically instead -- which also proves
      // that an identical stimulus produces an identical capture.
      do_arm;
      for (i = 0; i < 40; i = i + 1) ev(ev_type_e'(i[1:0]), i[3:0], i[7:0] + 8'd1);
      trig;
      for (i = 0; i < POST_N; i = i + 1) ev(EV_HSHK, 4'd7, 8'hC0 + i[7:0]);
      view_mask = m[3:0];
      base_shown = n_shown; base_hidden = n_hidden;
      drain_and_check;
      // Everything drained is either shown or hidden, and nothing is lost.
      ck("shown + hidden",
         (n_shown - base_shown) + (n_hidden - base_hidden),
         {24'd0, n_valid});
    end
    view_mask = 4'hF;

    // ================= PHASE 4 -- draining before the freeze yields none ==
    do_arm;
    for (i = 0; i < 20; i = i + 1) ev(EV_TOKEN, 4'd3, i[7:0] + 8'd1);
    trig;
    ev(EV_ERROR, 4'd3, 8'hD0);
    ck("still capturing", state, S_CAPT);
    rd_en = 1'b1;
    model_cycle;
    @(posedge clk); #1; steps = steps + 1;
    ck("no drain while capturing", {31'd0, rd_valid}, 32'd0);
    rd_en = 1'b0;

    // ================= PHASE 5 -- re-arming throws the capture away ======
    //
    // And it must throw away the pre-trigger count with it. A stale pre_r
    // makes the NEXT capture report a pre_lost it did not earn.
    do_arm;
    for (i = 0; i < 5; i = i + 1) ev(EV_DATA, 4'd4, i[7:0] + 8'd1);
    trig;
    for (i = 0; i < POST_N; i = i + 1) ev(EV_ERROR, 4'hE, 8'hE0 + i[7:0]);
    ck("re-armed pre_kept", {24'd0, pre_kept}, 32'd5);
    ck("re-armed pre_lost", {31'd0, pre_lost}, 32'd0);

    // ---- Traffic AFTER the freeze must not touch the capture. ----
    //
    // The bus does not stop because you triggered. If a frozen capture keeps
    // absorbing events, the trace changes while you are reading it -- and
    // the entries you already looked at are no longer the entries that are
    // there. Every type is offered, and the drain below is compared against
    // the model as though none of them happened, because none of them may.
    base_shown = n_written;
    for (i = 0; i < 4; i = i + 1) ev(ev_type_e'(i[1:0]), 4'hA, 8'hF0 + i[7:0]);
    ck("frozen: nothing written", n_written, base_shown[31:0]);
    ck("frozen: still frozen",    state, S_FROZEN);
    drain_and_check;

    // ================= PHASE 6 -- random ================================
    //
    // Random capture lengths and random event mixes, every one of them
    // drained and compared in full.
    for (i = 0; i < 300; i = i + 1) begin
      do_arm;
      w = $unsigned($random) % 90;
      for (p = 0; p < w; p = p + 1)
        ev(ev_type_e'($unsigned($random) % 4),
           4'($unsigned($random) % 16), 8'($unsigned($random) % 256));
      trig;
      for (p = 0; p < POST_N; p = p + 1)
        ev(ev_type_e'($unsigned($random) % 4),
           4'($unsigned($random) % 16), 8'($unsigned($random) % 256));
      view_mask = 4'($unsigned($random) % 16);
      drain_and_check;
    end
    view_mask = 4'hF;

    // ================= the exhaustiveness proof ==========================
    n_reach = 0;
    for (k = 0; k < 16; k = k + 1) n_reach = n_reach + reach[k];
    if (n_reach != 16) begin
      errors = errors + 1;
      $display("FAIL state x type reach %0d/16", n_reach);
      for (k = 0; k < 16; k = k + 1)
        if (!reach[k]) $display("  unreached state=%0d type=%0d", k / 4, k % 4);
    end

    $display("steps=%0d checks=%0d reach=%0d/16 errors=%0d",
             steps, checks, n_reach, errors);
    $display("retention edge: intact=%0d lost=%0d",
             n_intact_cases, n_lost_cases);
    $display("written=%0d overwritten=%0d shown=%0d hidden=%0d",
             n_written, n_overwritten, n_shown, n_hidden);
    $display("%0s: %0d errors in %0d checks",
             (errors == 0) ? "PASS" : "FAIL", errors, checks);
    $finish;
  end
endmodule