Senior Host-Controller Architecture

   MMIO registers          the doorbell, and the operational regs
        |
   Device Context Base Address Array
        |
   Device Context  (one per attached device)
        |
   Endpoint Context (one per endpoint, holds the dequeue pointer)
        |
   TRANSFER RING   <-- one per endpoint. Software produces, the
        |               controller consumes.
        |
   COMMAND RING    <-- one, for configure/address/reset commands
   EVENT RING      <-- one or more, and the direction is REVERSED:
                       the CONTROLLER produces, software consumes

   Then, and only then, the logic:
     scheduler  ->  DMA engine  ->  root hub ports  ->  PHYs

   enq == deq   and   PCS == CCS   ->   EMPTY
   enq == deq   and   PCS != CCS   ->   FULL

   The pointers are equal in BOTH cases. The cycle states
   differ only when the producer has lapped the consumer
   exactly once.

// =====================================================================
//  xhci_ring -- "Whiteboard an xHCI host controller" in hardware.
//
//  An xHCI controller is a large block diagram with one genuinely clever
//  idea in it, and the interview is about whether you can name it:
//
//      Software and hardware share a ring buffer with NO LOCK and no
//      head/tail pointer exchange. Ownership of each entry is carried
//      by a single bit in the entry itself -- the CYCLE BIT.
//
//  How it works: the ring has a "current cycle state" that both sides
//  track, and it INVERTS every time the pointer wraps. An entry whose
//  cycle bit equals the consumer's cycle state is owned by the consumer;
//  one that differs is owned by the producer. Software writes an entry
//  and sets its cycle bit last; that single write transfers ownership.
//
//  There is no shared counter to race on, no lock to take, and no
//  doorbell strictly required for correctness. A full ring and an empty
//  ring are distinguishable -- which the classic head==tail ring buffer
//  cannot do without wasting an entry or adding a counter.
//
//  It is a beautiful mechanism and it has exactly one way to get it
//  wrong: failing to invert the cycle state on wrap. Do that and the
//  consumer reads the whole ring exactly once and then stops forever,
//  having decided every entry belongs to the producer.
// =====================================================================
module xhci_ring #(
  parameter integer RING_N = 8       // entries, including the Link TRB
) (
  input  wire        clk,
  input  wire        rst_n,

  // ---- the PRODUCER side (software enqueuing a transfer) ----
  input  wire        prod_req,
  input  wire [15:0] prod_data,
  output wire        prod_ack,
  output wire        ring_full,

  // ---- the CONSUMER side (the controller fetching work) ----
  input  wire        cons_req,
  output wire        cons_valid,
  output wire [15:0] cons_data,
  output wire        ring_empty,

  // ---- the state both sides track ----
  output wire        pcs,            // producer cycle state
  output wire        ccs,            // consumer cycle state
  output wire [3:0]  enq_ptr,
  output wire [3:0]  deq_ptr,

  // ---- observability ----
  output wire [31:0] n_enq,
  output wire [31:0] n_deq,
  output wire [31:0] n_prod_wrap,
  output wire [31:0] n_cons_wrap,
  output wire [31:0] n_full_reject,
  output wire [31:0] n_empty_read,
  output wire [31:0] n_owner_error   // must always read 0
);

  // The ring entries, plus the cycle bit that carries ownership.
  reg [15:0] data  [0:RING_N-1];
  reg        cyc   [0:RING_N-1];

  reg [3:0]  enq_r, deq_r;
  reg        pcs_r, ccs_r;

  reg        pa_r;
  reg        cv_r;
  reg [15:0] cd_r;

  reg [31:0] enq_c, deq_c, pwrap_c, cwrap_c, full_c, empty_c, own_c;

  assign prod_ack   = pa_r;
  assign cons_valid = cv_r;
  assign cons_data  = cd_r;
  assign pcs        = pcs_r;
  assign ccs        = ccs_r;
  assign enq_ptr    = enq_r;
  assign deq_ptr    = deq_r;

  assign n_enq         = enq_c;
  assign n_deq         = deq_c;
  assign n_prod_wrap   = pwrap_c;
  assign n_cons_wrap   = cwrap_c;
  assign n_full_reject = full_c;
  assign n_empty_read  = empty_c;
  assign n_owner_error = own_c;

  // =================================================================
  //  THE MECHANISM, and it is the whole design.
  //
  //  There are two separate claims here and conflating them is the
  //  commonest way to get a ring buffer wrong.
  //
  //  (1) IS THIS ENTRY READY?  A single-bit test, and the only thing
  //      the cycle bit itself answers. An entry whose cycle bit equals
  //      the consumer's cycle state has been finished by the producer;
  //      one that differs has not. Software writes the payload and sets
  //      the cycle bit LAST, and that single store transfers ownership.
  //      No lock, no barrier beyond ordering the two writes.
  //
  //  (2) IS THE RING FULL OR EMPTY?  The cycle bit alone cannot say,
  //      because the consumer never writes anything -- so the producer
  //      has no per-entry evidence that an entry has been consumed.
  //      What distinguishes the two is the pair of CYCLE STATES:
  //
  //          enq == deq  and  pcs == pcs  ->  EMPTY
  //          enq == deq  and  pcs != ccs  ->  FULL
  //
  //      The pointers are equal in both cases. The cycle states differ
  //      only when the producer has lapped the consumer exactly once.
  //      That is how this ring holds RING_N entries rather than
  //      RING_N-1, without a counter and without a wasted slot -- which
  //      a plain head/tail ring cannot do.
  // =================================================================
  wire ptr_eq        = (enq_r == deq_r);
  wire cons_owns_deq = (cyc[deq_r] == ccs_r);

  assign ring_empty = ptr_eq && (pcs_r == ccs_r);
  assign ring_full  = ptr_eq && (pcs_r != ccs_r);

  wire prod_owns_enq = !ring_full;

  integer k;

  always @(posedge clk or negedge rst_n) begin
    if (!rst_n) begin
      enq_r   <= 4'd0;
      deq_r   <= 4'd0;
      // Both sides start at cycle state 1 and every entry starts at 0,
      // so the ring begins EMPTY: cyc != ccs everywhere.
      pcs_r   <= 1'b1;
      ccs_r   <= 1'b1;
      pa_r    <= 1'b0;
      cv_r    <= 1'b0;
      cd_r    <= 16'd0;
      enq_c   <= 32'd0;
      deq_c   <= 32'd0;
      pwrap_c <= 32'd0;
      cwrap_c <= 32'd0;
      full_c  <= 32'd0;
      empty_c <= 32'd0;
      own_c   <= 32'd0;
      for (k = 0; k < RING_N; k = k + 1) begin
        data[k] <= 16'd0;
        cyc[k]  <= 1'b0;
      end
    end else begin
      pa_r <= 1'b0;
      cv_r <= 1'b0;

      // ---- PRODUCER: write the entry, then its cycle bit ----
      //
      // In hardware both happen on the same edge; in software the cycle
      // bit MUST be written last, because that single store is what
      // transfers ownership. A controller that observed the cycle bit
      // before the payload would fetch a half-written descriptor.
      if (prod_req) begin
        if (prod_owns_enq) begin
          data[enq_r] <= prod_data;
          cyc[enq_r]  <= pcs_r;          // ownership handed over
          pa_r        <= 1'b1;
          enq_c       <= enq_c + 32'd1;

          if (enq_r == RING_N - 1) begin
            // ---- THE WRAP, and the one line the whole thing hinges on ----
            //
            // At the end of the ring the pointer returns to zero AND the
            // cycle state INVERTS. Without the inversion the producer
            // would write entries whose cycle bit still matches what the
            // consumer already consumed, and the ring would appear
            // permanently empty from the consumer's side.
            enq_r   <= 4'd0;
            pcs_r   <= ~pcs_r;
            pwrap_c <= pwrap_c + 32'd1;
          end else begin
            enq_r <= enq_r + 4'd1;
          end
        end else begin
          // The ring is full. Counted rather than silently dropped,
          // because a producer that cannot tell "full" from "accepted"
          // loses transfers with no error anywhere.
          full_c <= full_c + 32'd1;
        end
      end

      // ---- CONSUMER: take the entry if it is ours ----
      if (cons_req) begin
        if (cons_owns_deq) begin
          cv_r  <= 1'b1;
          cd_r  <= data[deq_r];
          deq_c <= deq_c + 32'd1;

          if (deq_r == RING_N - 1) begin
            deq_r   <= 4'd0;
            ccs_r   <= ~ccs_r;
            cwrap_c <= cwrap_c + 32'd1;
          end else begin
            deq_r <= deq_r + 4'd1;
          end
        end else begin
          empty_c <= empty_c + 32'd1;
        end
      end

      // ---- the self-check: the two formulations must AGREE ----
      //
      // "The entry at the dequeue pointer is ready" and "the ring is not
      // empty" are computed by completely different means -- a single-bit
      // ownership test on one entry, and a comparison of two pointers and
      // two cycle states. They are the same claim, so they must always
      // agree, and a broken cycle-state inversion breaks exactly one of
      // them.
      //
      // Unreachable on a correct design, counted so a run can publish the
      // number zero.
      if (cons_owns_deq == ring_empty)
        own_c <= own_c + 32'd1;
    end
  end

endmodule

// =====================================================================
//  xhci_ring -- SystemVerilog.
//
//  Same mechanism, and one thing the Verilog cannot say: the ring entry
//  is a STRUCT with the payload and the cycle bit in it, which is what a
//  TRB actually is. Keeping them in one object makes the ordering
//  requirement -- payload first, cycle bit last -- a property of one
//  assignment rather than an unwritten rule about two separate arrays.
//
//  An xHCI controller is a large block diagram with one genuinely clever
//  idea in it, and the interview is about whether you can name it:
//
//      Software and hardware share a ring buffer with NO LOCK and no
//      head/tail pointer exchange. Ownership of each entry is carried
//      by a single bit in the entry itself -- the CYCLE BIT.
//
//  How it works: the ring has a "current cycle state" that both sides
//  track, and it INVERTS every time the pointer wraps. An entry whose
//  cycle bit equals the consumer's cycle state is owned by the consumer;
//  one that differs is owned by the producer. Software writes an entry
//  and sets its cycle bit last; that single write transfers ownership.
//
//  There is no shared counter to race on, no lock to take, and no
//  doorbell strictly required for correctness. A full ring and an empty
//  ring are distinguishable -- which the classic head==tail ring buffer
//  cannot do without wasting an entry or adding a counter.
//
//  It is a beautiful mechanism and it has exactly one way to get it
//  wrong: failing to invert the cycle state on wrap. Do that and the
//  consumer reads the whole ring exactly once and then stops forever,
//  having decided every entry belongs to the producer.
// =====================================================================
module xhci_ring #(
  parameter int RING_N = 8       // entries, including the Link TRB
) (
  input  logic       clk,
  input  logic       rst_n,

  // ---- the PRODUCER side (software enqueuing a transfer) ----
  input  logic       prod_req,
  input  logic [15:0]prod_data,
  output logic       prod_ack,
  output logic       ring_full,

  // ---- the CONSUMER side (the controller fetching work) ----
  input  logic       cons_req,
  output logic       cons_valid,
  output logic [15:0]cons_data,
  output logic       ring_empty,

  // ---- the state both sides track ----
  output logic       pcs,            // producer cycle state
  output logic       ccs,            // consumer cycle state
  output logic [3:0] enq_ptr,
  output logic [3:0] deq_ptr,

  // ---- observability ----
  output logic [31:0]n_enq,
  output logic [31:0]n_deq,
  output logic [31:0]n_prod_wrap,
  output logic [31:0]n_cons_wrap,
  output logic [31:0]n_full_reject,
  output logic [31:0]n_empty_read,
  output logic [31:0]n_owner_error   // must always read 0
);

  // A ring entry, which is what a TRB is: a payload and a cycle bit that
  // carries ownership. Keeping them in one object makes "write the payload,
  // then the cycle bit" a property of one assignment rather than an
  // unwritten rule about two separate arrays.
  typedef struct packed {
    logic [15:0] data;
    logic        cyc;
  } trb_t;

  trb_t ring [RING_N];

  logic [3:0] enq_r, deq_r;
  logic      pcs_r, ccs_r;

  logic      pa_r;
  logic      cv_r;
  logic [15:0] cd_r;

  logic [31:0] enq_c, deq_c, pwrap_c, cwrap_c, full_c, empty_c, own_c;
  // Icarus Verilog 13 aborts its elaborator on a variable FIELD SELECT into
  // an unpacked array of packed structs -- `ring[enq_r].cyc` fails an
  // internal assertion rather than reporting an error. Reading the whole
  // element into a wire first and selecting the field from THAT is legal,
  // portable, and arguably clearer: it names the entry being examined.
  wire trb_t deq_trb = ring[deq_r];

  // A struct temporary for the write side. Icarus also rejects a
  // named-field assignment pattern, and building the entry field by
  // field on a local has a virtue anyway: the order in which the two
  // fields are set is visible, and in software that order is the
  // entire correctness argument.
  trb_t nxt_trb;


  assign prod_ack   = pa_r;
  assign cons_valid = cv_r;
  assign cons_data  = cd_r;
  assign pcs        = pcs_r;
  assign ccs        = ccs_r;
  assign enq_ptr    = enq_r;
  assign deq_ptr    = deq_r;

  assign n_enq         = enq_c;
  assign n_deq         = deq_c;
  assign n_prod_wrap   = pwrap_c;
  assign n_cons_wrap   = cwrap_c;
  assign n_full_reject = full_c;
  assign n_empty_read  = empty_c;
  assign n_owner_error = own_c;

  // =================================================================
  //  THE MECHANISM, and it is the whole design.
  //
  //  There are two separate claims here and conflating them is the
  //  commonest way to get a ring buffer wrong.
  //
  //  (1) IS THIS ENTRY READY?  A single-bit test, and the only thing
  //      the cycle bit itself answers. An entry whose cycle bit equals
  //      the consumer's cycle state has been finished by the producer;
  //      one that differs has not. Software writes the payload and sets
  //      the cycle bit LAST, and that single store transfers ownership.
  //      No lock, no barrier beyond ordering the two writes.
  //
  //  (2) IS THE RING FULL OR EMPTY?  The cycle bit alone cannot say,
  //      because the consumer never writes anything -- so the producer
  //      has no per-entry evidence that an entry has been consumed.
  //      What distinguishes the two is the pair of CYCLE STATES:
  //
  //          enq == deq  and  pcs == pcs  ->  EMPTY
  //          enq == deq  and  pcs != ccs  ->  FULL
  //
  //      The pointers are equal in both cases. The cycle states differ
  //      only when the producer has lapped the consumer exactly once.
  //      That is how this ring holds RING_N entries rather than
  //      RING_N-1, without a counter and without a wasted slot -- which
  //      a plain head/tail ring cannot do.
  // =================================================================
  wire ptr_eq        = (enq_r == deq_r);
  wire cons_owns_deq = (deq_trb.cyc == ccs_r);

  assign ring_empty = ptr_eq && (pcs_r == ccs_r);
  assign ring_full  = ptr_eq && (pcs_r != ccs_r);

  wire prod_owns_enq = !ring_full;


  always_ff @(posedge clk or negedge rst_n) begin
    if (!rst_n) begin
      enq_r   <= 4'd0;
      deq_r   <= 4'd0;
      // Both sides start at cycle state 1 and every entry starts at 0,
      // so the ring begins EMPTY: cyc != ccs everywhere.
      pcs_r   <= 1'b1;
      ccs_r   <= 1'b1;
      pa_r    <= 1'b0;
      cv_r    <= 1'b0;
      cd_r    <= 16'd0;
      enq_c   <= 32'd0;
      deq_c   <= 32'd0;
      pwrap_c <= 32'd0;
      cwrap_c <= 32'd0;
      full_c  <= 32'd0;
      empty_c <= 32'd0;
      own_c   <= 32'd0;
      for (int k = 0; k < RING_N; k++) begin
        ring[k] <= {16'd0, 1'b0};
      end
    end else begin
      pa_r <= 1'b0;
      cv_r <= 1'b0;

      // ---- PRODUCER: write the entry, then its cycle bit ----
      //
      // In hardware both happen on the same edge; in software the cycle
      // bit MUST be written last, because that single store is what
      // transfers ownership. A controller that observed the cycle bit
      // before the payload would fetch a half-written descriptor.
      if (prod_req) begin
        if (prod_owns_enq) begin
          // Payload AND ownership in ONE write. In software these are two
          // stores and the cycle bit MUST be second, because that store is
          // what hands the entry over: a controller that saw the cycle bit
          // before the payload would fetch a half-written descriptor.
          nxt_trb.data = prod_data;   // payload FIRST
          nxt_trb.cyc  = pcs_r;       // then ownership
          ring[enq_r]  <= nxt_trb;
          pa_r        <= 1'b1;
          enq_c       <= enq_c + 32'd1;

          if (enq_r == RING_N - 1) begin
            // ---- THE WRAP, and the one line the whole thing hinges on ----
            //
            // At the end of the ring the pointer returns to zero AND the
            // cycle state INVERTS. Without the inversion the producer
            // would write entries whose cycle bit still matches what the
            // consumer already consumed, and the ring would appear
            // permanently empty from the consumer's side.
            enq_r   <= 4'd0;
            pcs_r   <= ~pcs_r;
            pwrap_c <= pwrap_c + 32'd1;
          end else begin
            enq_r <= enq_r + 4'd1;
          end
        end else begin
          // The ring is full. Counted rather than silently dropped,
          // because a producer that cannot tell "full" from "accepted"
          // loses transfers with no error anywhere.
          full_c <= full_c + 32'd1;
        end
      end

      // ---- CONSUMER: take the entry if it is ours ----
      if (cons_req) begin
        if (cons_owns_deq) begin
          cv_r  <= 1'b1;
          cd_r  <= deq_trb.data;
          deq_c <= deq_c + 32'd1;

          if (deq_r == RING_N - 1) begin
            deq_r   <= 4'd0;
            ccs_r   <= ~ccs_r;
            cwrap_c <= cwrap_c + 32'd1;
          end else begin
            deq_r <= deq_r + 4'd1;
          end
        end else begin
          empty_c <= empty_c + 32'd1;
        end
      end

      // ---- the self-check: the two formulations must AGREE ----
      //
      // "The entry at the dequeue pointer is ready" and "the ring is not
      // empty" are computed by completely different means -- a single-bit
      // ownership test on one entry, and a comparison of two pointers and
      // two cycle states. They are the same claim, so they must always
      // agree, and a broken cycle-state inversion breaks exactly one of
      // them.
      //
      // Unreachable on a correct design, counted so a run can publish the
      // number zero.
      if (cons_owns_deq == ring_empty)
        own_c <= own_c + 32'd1;
    end
  end

endmodule

-- =====================================================================
--  xhci_ring -- VHDL-2008.
--
--  VHDL gets the shape both other versions wanted: a RECORD per ring
--  entry, in an array, with a variable index -- and unlike Icarus it
--  will actually compile a field select on one.
--
--  It also refuses to let the two cycle states be confused with each
--  other by accident, because they are declared separately and used
--  separately, and a comparison between them is the one expression in
--  the file that has to be right.
-- =====================================================================
library ieee;
use ieee.std_logic_1164.all;
use ieee.numeric_std.all;

package xr_pkg is
  -- What a TRB is: a payload, and a cycle bit that carries ownership.
  type trb_t is record
    data : std_logic_vector(15 downto 0);
    cyc  : std_logic;
  end record;

  type trb_array is array (natural range <>) of trb_t;
end package;

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

entity xhci_ring is
  generic (
    RING_N : natural := 8
  );
  port (
    clk        : in  std_logic;
    rst_n      : in  std_logic;

    prod_req   : in  std_logic;
    prod_data  : in  std_logic_vector(15 downto 0);
    prod_ack   : out std_logic;
    ring_full  : out std_logic;

    cons_req   : in  std_logic;
    cons_valid : out std_logic;
    cons_data  : out std_logic_vector(15 downto 0);
    ring_empty : out std_logic;

    pcs        : out std_logic;
    ccs        : out std_logic;
    enq_ptr    : out std_logic_vector(3 downto 0);
    deq_ptr    : out std_logic_vector(3 downto 0);

    n_enq         : out std_logic_vector(31 downto 0);
    n_deq         : out std_logic_vector(31 downto 0);
    n_prod_wrap   : out std_logic_vector(31 downto 0);
    n_cons_wrap   : out std_logic_vector(31 downto 0);
    n_full_reject : out std_logic_vector(31 downto 0);
    n_empty_read  : out std_logic_vector(31 downto 0);
    n_owner_error : out std_logic_vector(31 downto 0)
  );
end entity;

architecture rtl of xhci_ring is
  signal ring : trb_array(0 to RING_N-1)
    := (others => (data => (others => '0'), cyc => '0'));

  signal enq_r, deq_r : natural range 0 to 15 := 0;
  -- Both start at 1 while every entry's cycle bit starts at 0, so the ring
  -- begins EMPTY: no entry's cycle bit matches the consumer's state.
  signal pcs_r, ccs_r : std_logic := '1';

  signal pa_r : std_logic := '0';
  signal cv_r : std_logic := '0';
  signal cd_r : std_logic_vector(15 downto 0) := (others => '0');

  signal enq_c, deq_c, pwrap_c, cwrap_c, full_c, empty_c, own_c
    : unsigned(31 downto 0) := (others => '0');

  -- =================================================================
  --  THE MECHANISM. Two separate claims, and conflating them is the
  --  commonest way to get a ring buffer wrong.
  --
  --  (1) IS THIS ENTRY READY?  A single-bit test, and the only thing the
  --      cycle bit itself answers. An entry whose cycle bit equals the
  --      consumer's cycle state has been finished by the producer.
  --      Software writes the payload and sets the cycle bit LAST, and
  --      that single store transfers ownership -- no lock at all.
  --
  --  (2) IS THE RING FULL OR EMPTY?  The cycle bit cannot say, because
  --      the consumer never writes anything and the producer therefore
  --      has no per-entry evidence that an entry was consumed. What
  --      separates the two is the pair of CYCLE STATES:
  --
  --          enq = deq  and  pcs = ccs   ->  EMPTY
  --          enq = deq  and  pcs /= ccs  ->  FULL
  --
  --      The pointers are equal in both. The cycle states differ only
  --      when the producer has lapped the consumer exactly once, which is
  --      how this ring holds RING_N entries rather than RING_N-1 without
  --      a counter and without a wasted slot.
  -- =================================================================
  signal ptr_eq        : boolean;
  signal cons_owns_deq : boolean;
  signal is_empty      : boolean;
  signal is_full       : boolean;
begin

  ptr_eq        <= enq_r = deq_r;
  cons_owns_deq <= ring(deq_r).cyc = ccs_r;
  is_empty      <= ptr_eq and (pcs_r = ccs_r);
  is_full       <= ptr_eq and (pcs_r /= ccs_r);

  ring_empty <= '1' when is_empty else '0';
  ring_full  <= '1' when is_full  else '0';

  prod_ack   <= pa_r;
  cons_valid <= cv_r;
  cons_data  <= cd_r;
  pcs        <= pcs_r;
  ccs        <= ccs_r;
  enq_ptr    <= std_logic_vector(to_unsigned(enq_r, 4));
  deq_ptr    <= std_logic_vector(to_unsigned(deq_r, 4));

  n_enq         <= std_logic_vector(enq_c);
  n_deq         <= std_logic_vector(deq_c);
  n_prod_wrap   <= std_logic_vector(pwrap_c);
  n_cons_wrap   <= std_logic_vector(cwrap_c);
  n_full_reject <= std_logic_vector(full_c);
  n_empty_read  <= std_logic_vector(empty_c);
  n_owner_error <= std_logic_vector(own_c);

  main : process(clk, rst_n)
    variable nxt : trb_t;
  begin
    if rst_n = '0' then
      enq_r   <= 0;
      deq_r   <= 0;
      pcs_r   <= '1';
      ccs_r   <= '1';
      pa_r    <= '0';
      cv_r    <= '0';
      cd_r    <= (others => '0');
      enq_c   <= (others => '0');
      deq_c   <= (others => '0');
      pwrap_c <= (others => '0');
      cwrap_c <= (others => '0');
      full_c  <= (others => '0');
      empty_c <= (others => '0');
      own_c   <= (others => '0');
      ring    <= (others => (data => (others => '0'), cyc => '0'));

    elsif rising_edge(clk) then
      pa_r <= '0';
      cv_r <= '0';

      -- ---- PRODUCER: the payload, then the cycle bit ----
      --
      -- In hardware both land on the same edge. In software the cycle bit
      -- MUST be written second, because that store is what hands the entry
      -- over: a controller that observed the cycle bit before the payload
      -- would fetch a half-written descriptor.
      if prod_req = '1' then
        if not is_full then
          nxt.data := prod_data;      -- payload FIRST
          nxt.cyc  := pcs_r;          -- then ownership
          ring(enq_r) <= nxt;
          pa_r  <= '1';
          enq_c <= enq_c + 1;

          if enq_r = RING_N - 1 then
            -- ---- THE WRAP, and the one line the whole thing hinges on ----
            --
            -- At the end of the ring the pointer returns to zero AND the
            -- cycle state INVERTS. Without the inversion the producer keeps
            -- writing entries whose cycle bit still matches what the
            -- consumer already consumed, and the ring looks permanently
            -- empty from the consumer's side: it reads the ring exactly
            -- once and then stops forever.
            enq_r   <= 0;
            pcs_r   <= not pcs_r;
            pwrap_c <= pwrap_c + 1;
          else
            enq_r <= enq_r + 1;
          end if;
        else
          -- The ring is full. Counted rather than silently dropped: a
          -- producer that cannot tell "full" from "accepted" loses
          -- transfers with no error anywhere.
          full_c <= full_c + 1;
        end if;
      end if;

      -- ---- CONSUMER: take the entry if it is ours ----
      if cons_req = '1' then
        -- Gated on the PER-ENTRY cycle bit, which is the actual xHCI
        -- mechanism -- not on the pointer/cycle-state comparison. The two
        -- are equivalent on a correct design (that is the self-check
        -- below), and they diverge the instant the cycle bits are wrong.
        -- Gating on the pointer test made this VHDL consumer immune to a
        -- mutation the Verilog one caught, and the two columns read
        -- 40184 against 358120.
        if cons_owns_deq then
          cv_r  <= '1';
          cd_r  <= ring(deq_r).data;
          deq_c <= deq_c + 1;

          if deq_r = RING_N - 1 then
            deq_r   <= 0;
            ccs_r   <= not ccs_r;
            cwrap_c <= cwrap_c + 1;
          else
            deq_r <= deq_r + 1;
          end if;
        else
          empty_c <= empty_c + 1;
        end if;
      end if;

      -- ---- the self-check: the two formulations must AGREE ----
      --
      -- "The entry at the dequeue pointer is ready" and "the ring is not
      -- empty" are computed by completely different means: a single-bit
      -- ownership test on one entry, and a comparison of two pointers and
      -- two cycle states. They are the same claim, so they must always
      -- agree -- and a broken cycle-state inversion breaks exactly one.
      --
      -- Unreachable on a correct design, counted so a run can publish zero.
      if cons_owns_deq = is_empty then
        own_c <= own_c + 1;
      end if;
    end if;
  end process;

end architecture;

   Design:  full/empty from a single-bit ownership test plus
            two cycle states.  No counter anywhere.

   Model:   a queue and an integer count.

   If the cycle-state arithmetic is wrong -- and the one way
   to get it wrong is to forget the inversion on wrap -- the
   two disagree immediately, because a counter cannot make
   that mistake.

// =====================================================================
//  Testbench for xhci_ring.
//
//  The shadow model is independent in the strongest way available here:
//  it tracks occupancy with a COUNTER and a queue, which is exactly the
//  mechanism the design deliberately does NOT have.
//
//  The design decides full and empty from single-bit ownership tests on
//  one entry. The model decides them by counting. If the cycle-bit
//  arithmetic is wrong -- and the one way to get it wrong is to forget
//  the inversion on wrap -- the two disagree immediately, because a
//  counter cannot make that mistake.
// =====================================================================
`timescale 1ns/1ps
module tb_xr_v;

  localparam integer RING_N = 8;

  reg         clk = 1'b0, rst_n = 1'b0;
  reg         prod_req = 1'b0;
  reg  [15:0] prod_data = 16'd0;
  reg         cons_req = 1'b0;

  wire        prod_ack, ring_full, cons_valid, ring_empty;
  wire [15:0] cons_data;
  wire        pcs, ccs;
  wire [3:0]  enq_ptr, deq_ptr;
  wire [31:0] n_enq, n_deq, n_prod_wrap, n_cons_wrap,
              n_full_reject, n_empty_read, n_owner_error;

  xhci_ring #(.RING_N(RING_N)) dut (
    .clk(clk), .rst_n(rst_n),
    .prod_req(prod_req), .prod_data(prod_data),
    .prod_ack(prod_ack), .ring_full(ring_full),
    .cons_req(cons_req), .cons_valid(cons_valid),
    .cons_data(cons_data), .ring_empty(ring_empty),
    .pcs(pcs), .ccs(ccs), .enq_ptr(enq_ptr), .deq_ptr(deq_ptr),
    .n_enq(n_enq), .n_deq(n_deq),
    .n_prod_wrap(n_prod_wrap), .n_cons_wrap(n_cons_wrap),
    .n_full_reject(n_full_reject), .n_empty_read(n_empty_read),
    .n_owner_error(n_owner_error)
  );

  always #5 clk = ~clk;

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

  function [31:0] urand;
    input dummy;
    begin urand = $random(seed) & 32'h3FFF_FFFF; end
  endfunction

  // ---- the shadow: a COUNTER and a queue, not cycle bits ----
  reg [15:0] q [0:RING_N-1];
  integer    qh, qt, qn;         // head, tail, count
  reg [31:0] x_enq, x_deq, x_full, x_empty;

  // ---- the headline counters ----
  integer n_lost   = 0;   // an accepted entry never came back
  integer n_wrong  = 0;   // an entry came back with the wrong data or order
  integer n_stuck  = 0;   // the ring reported empty with entries in it

  // ---- exhaustive reach over (occupancy, dequeue pointer) ----
  //
  // The cycle PARITY is deliberately not a third dimension. pcs differs
  // from ccs exactly when the producer has lapped the consumer an odd
  // number of times, which is DETERMINED by the occupancy: it is 0 at
  // occupancy 0 and 1 at occupancy RING_N. Treating it as a free axis gives
  // a 144-point domain of which 72 points do not exist, and a coverage
  // figure that can never close -- which is how an honest 72/72 gets
  // reported as a suspicious 72/144.
  reg reach [0:71];
  integer ri, n_reach;

  task ck(input cond, input [255:0] what);
    begin
      checks = checks + 1;
      if (!cond) begin
        errors = errors + 1;
        if (errors <= 20)
          $display("  ERROR @%0t step=%0d: %0s", $time, steps, what);
      end
    end
  endtask

  task mark;
    begin
      ri = (qn * 8) + deq_ptr;
      if (ri < 72) reach[ri] = 1'b1;
    end
  endtask

  // ---------------------------------------------------------------
  //  One cycle: optionally enqueue, optionally dequeue, check both.
  // ---------------------------------------------------------------
  task step(input pr, input [15:0] pd, input cr);
    reg        e_pack, e_cvalid, e_full, e_empty;
    reg [15:0] e_cdata;
    begin
      prod_req = pr;  prod_data = pd;  cons_req = cr;

      // ---- what SHOULD happen, from the COUNTER ----
      e_full  = (qn == RING_N);
      e_empty = (qn == 0);
      e_pack  = pr && !e_full;
      e_cvalid = cr && !e_empty;
      e_cdata = e_cvalid ? q[qh] : 16'd0;

      mark;

      // ---- check the status flags BEFORE the edge ----
      //
      // They are combinational functions of the ring's state, and the
      // whole claim of the design is that a single-bit ownership test
      // computes them correctly. So they are compared against the
      // counter's answer on every cycle.
      ck(ring_full  === e_full,  "ring_full disagrees with the occupancy count");
      ck(ring_empty === e_empty, "ring_empty disagrees with the occupancy count");
      ck(!(ring_full && ring_empty), "the ring reported full AND empty");
      if (!e_empty && ring_empty) n_stuck = n_stuck + 1;
      ck(n_stuck == 0, "the ring reported empty with entries in it");

      // ---- advance the shadow ----
      if (e_pack) begin
        q[qt] = pd;
        qt    = (qt + 1) % RING_N;
        qn    = qn + 1;
        x_enq = x_enq + 1;
      end else if (pr) begin
        x_full = x_full + 1;
      end

      if (e_cvalid) begin
        qh    = (qh + 1) % RING_N;
        qn    = qn - 1;
        x_deq = x_deq + 1;
      end else if (cr) begin
        x_empty = x_empty + 1;
      end

      @(posedge clk);
      #1;
      steps = steps + 1;
      prod_req = 1'b0;  cons_req = 1'b0;

      // ---- PROPERTY 1: the handshakes ----
      ck(prod_ack   === e_pack,   "prod_ack disagrees");
      ck(cons_valid === e_cvalid, "cons_valid disagrees");

      // ---- PROPERTY 2: FIFO order and exact data ----
      if (e_cvalid) begin
        if (cons_data !== e_cdata) n_wrong = n_wrong + 1;
        ck(cons_data === e_cdata, "the wrong entry came back");
      end
      ck(n_wrong == 0, "an entry came back out of order or corrupted");

      // ---- PROPERTY 3: the counters agree ----
      ck(n_enq         === x_enq,   "enqueue count disagrees");
      ck(n_deq         === x_deq,   "dequeue count disagrees");
      ck(n_full_reject === x_full,  "full-reject count disagrees");
      ck(n_empty_read  === x_empty, "empty-read count disagrees");

      // ---- PROPERTY 4: ownership is exclusive ----
      ck(n_owner_error === 32'd0, "the design detected a doubly-owned entry");

      // ---- PROPERTY 5: nothing accepted is ever lost ----
      //
      // Enqueued minus dequeued must equal the occupancy, always. This is
      // the check that a broken wrap shows up in: the entries are still
      // in the ring and the consumer has decided they belong to somebody
      // else, so the difference stops matching.
      if ((x_enq - x_deq) != qn) n_lost = n_lost + 1;
      ck((x_enq - x_deq) == qn, "accepted entries went missing");
      ck(n_lost == 0, "an accepted entry was lost");

      mark;
    end
  endtask

  task reset_dut;
    begin
      rst_n = 1'b0;
      prod_req = 0; cons_req = 0;
      @(posedge clk); @(posedge clk);
      rst_n = 1'b1;
      qh = 0; qt = 0; qn = 0;
      x_enq = 0; x_deq = 0; x_full = 0; x_empty = 0;
      @(posedge clk); #1;
    end
  endtask

  integer k, j, occ, lap;

  initial begin
    for (ri = 0; ri < 72; ri = ri + 1) reach[ri] = 1'b0;
    seed = 32'd27007;

    // =============================================================
    //  PHASE 1 (DIRECTED, EXHAUSTIVE) -- fill and drain completely,
    //  several times round, so the ring WRAPS and the cycle state
    //  inverts in both directions.
    //
    //  Going round more than once is the entire point. A ring that is
    //  filled and drained once, without wrapping, cannot distinguish a
    //  correct cycle-state inversion from no inversion at all.
    // =============================================================
    reset_dut;
    for (lap = 0; lap < 6; lap = lap + 1) begin
      // fill it exactly full
      for (k = 0; k < RING_N; k = k + 1)
        step(1'b1, 16'hA000 + (lap * 16) + k, 1'b0);
      ck(ring_full === 1'b1, "the ring did not report full after RING_N entries");
      // one more must be refused, and must not disturb anything
      step(1'b1, 16'hDEAD, 1'b0);
      ck(prod_ack === 1'b0, "an entry was accepted into a full ring");
      // drain it exactly empty, in order
      for (k = 0; k < RING_N; k = k + 1)
        step(1'b0, 16'd0, 1'b1);
      ck(ring_empty === 1'b1, "the ring did not report empty after draining");
      // one more must be refused
      step(1'b0, 16'd0, 1'b1);
      ck(cons_valid === 1'b0, "an entry came out of an empty ring");
    end

    // =============================================================
    //  PHASE 2 (DIRECTED, EXHAUSTIVE) -- every occupancy from 0 to
    //  RING_N, reached by filling, then one enqueue and one dequeue
    //  attempted at that occupancy.
    // =============================================================
    for (occ = 0; occ <= RING_N; occ = occ + 1) begin
      reset_dut;
      for (k = 0; k < occ; k = k + 1) step(1'b1, 16'hB000 + k, 1'b0);
      // an enqueue at this occupancy
      step(1'b1, 16'hC0DE, 1'b0);
      // a dequeue at this occupancy
      step(1'b0, 16'd0, 1'b1);
      // and both at once, which must do both
      step(1'b1, 16'hBEEF, 1'b1);
    end

    // =============================================================
    //  PHASE 2b (DIRECTED, EXHAUSTIVE) -- close the domain.
    //
    //  The directed phases above reach only 59 of the 72
    //  (occupancy, dequeue pointer) pairs: the ring is only ever EMPTY or
    //  FULL at dequeue pointer 0, because every lap starts and ends there.
    //
    //  The BASE row of the directed-only run exposed this -- it read 1
    //  error, which is `exhaustive sweep incomplete`. The coverage claim
    //  was quietly depending on the RANDOM phase, which means the sweep was
    //  not exhaustive by directed stimulus at all.
    //
    //  Filling k and draining k leaves the ring empty with the pointer at
    //  k, and filling from there reaches full at k.
    // =============================================================
    for (j = 1; j < RING_N; j = j + 1) begin
      reset_dut;
      for (k = 0; k < j; k = k + 1) step(1'b1, 16'h3000 + k, 1'b0);
      for (k = 0; k < j; k = k + 1) step(1'b0, 16'd0, 1'b1);
      ck(ring_empty === 1'b1, "the ring is not empty after matched fill and drain");
      // now empty with the pointer at j: fill it completely and drain again
      for (k = 0; k < RING_N; k = k + 1) step(1'b1, 16'h4000 + k, 1'b0);
      ck(ring_full === 1'b1, "the ring is not full at a non-zero pointer");
      for (k = 0; k < RING_N; k = k + 1) step(1'b0, 16'd0, 1'b1);
      ck(ring_empty === 1'b1, "the ring is not empty after a full lap from j");
    end

    // =============================================================
    //  PHASE 3 (DIRECTED) -- simultaneous enqueue and dequeue, held
    //  at a steady occupancy for many laps.
    //
    //  This is the case that keeps the two pointers a fixed distance
    //  apart while both wrap, so the producer and consumer cycle states
    //  are unequal for half the run. A design that compared pointers
    //  instead of cycle bits would work here and fail nowhere else.
    // =============================================================
    for (occ = 1; occ < RING_N; occ = occ + 1) begin
      reset_dut;
      for (k = 0; k < occ; k = k + 1) step(1'b1, 16'hE000 + k, 1'b0);
      for (k = 0; k < 4 * RING_N; k = k + 1)
        step(1'b1, 16'hF000 + k, 1'b1);
    end

    // =============================================================
    //  PHASE 4 (DIRECTED) -- a full ring drained one entry at a time
    //  while the producer keeps pushing, so the ring stays full and
    //  the wrap happens under back-pressure.
    // =============================================================
    reset_dut;
    for (k = 0; k < RING_N; k = k + 1) step(1'b1, 16'h1000 + k, 1'b0);
    for (k = 0; k < 5 * RING_N; k = k + 1) begin
      // The ring does NOT stay exactly full, and that is correct. On a
      // full ring a simultaneous enqueue and dequeue refuses the enqueue:
      // the producer reads the ring's state as it stood BEFORE this cycle,
      // and a consumer freeing a slot on the same edge is a different agent
      // whose action it cannot have seen. Occupancy settles one below full.
      //
      // Asserting "stays full" here was wrong and produced 40 errors
      // against a correct design.
      step(1'b1, 16'h2000 + k, 1'b1);
      ck(qn >= RING_N - 1,
         "matched traffic drained the ring instead of holding it near full");
      ck(ring_empty === 1'b0, "a ring under matched traffic reported empty");
    end

    // =============================================================
    //  PHASE 5 (RANDOM) -- arbitrary interleaving.
    // =============================================================
`ifndef DIRECTED_ONLY
    reset_dut;
    for (k = 0; k < 40000; k = k + 1)
      step((urand(0) % 3) != 0, urand(0) & 16'hFFFF, (urand(0) % 3) != 0);
`endif

    n_reach = 0;
    for (ri = 0; ri < 72; ri = ri + 1) if (reach[ri]) n_reach = n_reach + 1;

    $display("steps=%0d checks=%0d reach=%0d/72 errors=%0d",
             steps, checks, n_reach, errors);
    $display("[ring] enq=%0d deq=%0d prod_wraps=%0d cons_wraps=%0d full_rejects=%0d empty_reads=%0d",
             n_enq, n_deq, n_prod_wrap, n_cons_wrap, n_full_reject, n_empty_read);
    $display("[the whole point] lost entries = %0d, out-of-order = %0d, false-empty = %0d",
             n_lost, n_wrong, n_stuck);
    if (n_reach != 72) begin
      $display("FAIL: exhaustive sweep incomplete"); errors = errors + 1;
    end
    if (errors == 0) $display("PASS: 0 errors in %0d checks", checks);
    else             $display("FAIL: %0d errors in %0d checks", errors, checks);
    $finish;
  end

endmodule

// =====================================================================
//  Testbench for xhci_ring.
//
//  The shadow model is independent in the strongest way available here:
//  it tracks occupancy with a COUNTER and a queue, which is exactly the
//  mechanism the design deliberately does NOT have.
//
//  The design decides full and empty from single-bit ownership tests on
//  one entry. The model decides them by counting. If the cycle-bit
//  arithmetic is wrong -- and the one way to get it wrong is to forget
//  the inversion on wrap -- the two disagree immediately, because a
//  counter cannot make that mistake.
// =====================================================================
`timescale 1ns/1ps
module tb_xr_sv;

  localparam integer RING_N = 8;

  logic       clk = 1'b0, rst_n = 1'b0;
  logic       prod_req = 1'b0;
  logic [15:0] prod_data = 16'd0;
  logic       cons_req = 1'b0;

  logic       prod_ack, ring_full, cons_valid, ring_empty;
  logic [15:0] cons_data;
  logic       pcs, ccs;
  logic [3:0] enq_ptr, deq_ptr;
  logic [31:0] n_enq, n_deq, n_prod_wrap, n_cons_wrap,
               n_full_reject, n_empty_read, n_owner_error;

  xhci_ring #(.RING_N(RING_N)) dut (
    .clk(clk), .rst_n(rst_n),
    .prod_req(prod_req), .prod_data(prod_data),
    .prod_ack(prod_ack), .ring_full(ring_full),
    .cons_req(cons_req), .cons_valid(cons_valid),
    .cons_data(cons_data), .ring_empty(ring_empty),
    .pcs(pcs), .ccs(ccs), .enq_ptr(enq_ptr), .deq_ptr(deq_ptr),
    .n_enq(n_enq), .n_deq(n_deq),
    .n_prod_wrap(n_prod_wrap), .n_cons_wrap(n_cons_wrap),
    .n_full_reject(n_full_reject), .n_empty_read(n_empty_read),
    .n_owner_error(n_owner_error)
  );

  always #5 clk = ~clk;

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

  function automatic logic [31:0] urand(bit dummy);
    return $random(seed) & 32'h3FFF_FFFF;
  endfunction

  // ---- the shadow: a COUNTER and a queue, not cycle bits ----
  logic [15:0] q [0:RING_N-1];
  integer    qh, qt, qn;         // head, tail, count
  logic [31:0] x_enq, x_deq, x_full, x_empty;

  // ---- the headline counters ----
  integer n_lost   = 0;   // an accepted entry never came back
  integer n_wrong  = 0;   // an entry came back with the wrong data or order
  integer n_stuck  = 0;   // the ring reported empty with entries in it

  // ---- exhaustive reach over (occupancy, dequeue pointer) ----
  //
  // The cycle PARITY is deliberately not a third dimension. pcs differs
  // from ccs exactly when the producer has lapped the consumer an odd
  // number of times, which is DETERMINED by the occupancy: it is 0 at
  // occupancy 0 and 1 at occupancy RING_N. Treating it as a free axis gives
  // a 144-point domain of which 72 points do not exist, and a coverage
  // figure that can never close -- which is how an honest 72/72 gets
  // reported as a suspicious 72/144.
  logic reach [0:71];
  integer ri, n_reach;

  task ck(input logic cond, input logic [255:0] what);
    begin
      checks = checks + 1;
      if (!cond) begin
        errors = errors + 1;
        if (errors <= 20)
          $display("  ERROR @%0t step=%0d: %0s", $time, steps, what);
      end
    end
  endtask

  task mark;
    begin
      ri = (qn * 8) + deq_ptr;
      if (ri < 72) reach[ri] = 1'b1;
    end
  endtask

  // ---------------------------------------------------------------
  //  One cycle: optionally enqueue, optionally dequeue, check both.
  // ---------------------------------------------------------------
  task step(input logic pr, input logic [15:0] pd, input logic cr);
    logic      e_pack, e_cvalid, e_full, e_empty;
    logic [15:0] e_cdata;
    begin
      prod_req = pr;  prod_data = pd;  cons_req = cr;

      // ---- what SHOULD happen, from the COUNTER ----
      e_full  = (qn == RING_N);
      e_empty = (qn == 0);
      e_pack  = pr && !e_full;
      e_cvalid = cr && !e_empty;
      e_cdata = e_cvalid ? q[qh] : 16'd0;

      mark;

      // ---- check the status flags BEFORE the edge ----
      //
      // They are combinational functions of the ring's state, and the
      // whole claim of the design is that a single-bit ownership test
      // computes them correctly. So they are compared against the
      // counter's answer on every cycle.
      ck(ring_full  === e_full,  "ring_full disagrees with the occupancy count");
      ck(ring_empty === e_empty, "ring_empty disagrees with the occupancy count");
      ck(!(ring_full && ring_empty), "the ring reported full AND empty");
      if (!e_empty && ring_empty) n_stuck = n_stuck + 1;
      ck(n_stuck == 0, "the ring reported empty with entries in it");

      // ---- advance the shadow ----
      if (e_pack) begin
        q[qt] = pd;
        qt    = (qt + 1) % RING_N;
        qn    = qn + 1;
        x_enq = x_enq + 1;
      end else if (pr) begin
        x_full = x_full + 1;
      end

      if (e_cvalid) begin
        qh    = (qh + 1) % RING_N;
        qn    = qn - 1;
        x_deq = x_deq + 1;
      end else if (cr) begin
        x_empty = x_empty + 1;
      end

      @(posedge clk);
      #1;
      steps = steps + 1;
      prod_req = 1'b0;  cons_req = 1'b0;

      // ---- PROPERTY 1: the handshakes ----
      ck(prod_ack   === e_pack,   "prod_ack disagrees");
      ck(cons_valid === e_cvalid, "cons_valid disagrees");

      // ---- PROPERTY 2: FIFO order and exact data ----
      if (e_cvalid) begin
        if (cons_data !== e_cdata) n_wrong = n_wrong + 1;
        ck(cons_data === e_cdata, "the wrong entry came back");
      end
      ck(n_wrong == 0, "an entry came back out of order or corrupted");

      // ---- PROPERTY 3: the counters agree ----
      ck(n_enq         === x_enq,   "enqueue count disagrees");
      ck(n_deq         === x_deq,   "dequeue count disagrees");
      ck(n_full_reject === x_full,  "full-reject count disagrees");
      ck(n_empty_read  === x_empty, "empty-read count disagrees");

      // ---- PROPERTY 4: ownership is exclusive ----
      ck(n_owner_error === 32'd0, "the design detected a doubly-owned entry");

      // ---- PROPERTY 5: nothing accepted is ever lost ----
      //
      // Enqueued minus dequeued must equal the occupancy, always. This is
      // the check that a broken wrap shows up in: the entries are still
      // in the ring and the consumer has decided they belong to somebody
      // else, so the difference stops matching.
      if ((x_enq - x_deq) != qn) n_lost = n_lost + 1;
      ck((x_enq - x_deq) == qn, "accepted entries went missing");
      ck(n_lost == 0, "an accepted entry was lost");

      mark;
    end
  endtask

  task reset_dut;
    begin
      rst_n = 1'b0;
      prod_req = 0; cons_req = 0;
      @(posedge clk); @(posedge clk);
      rst_n = 1'b1;
      qh = 0; qt = 0; qn = 0;
      x_enq = 0; x_deq = 0; x_full = 0; x_empty = 0;
      @(posedge clk); #1;
    end
  endtask

  integer k, j, occ, lap;

  initial begin
    for (ri = 0; ri < 72; ri = ri + 1) reach[ri] = 1'b0;
    seed = 32'd27007;

    // =============================================================
    //  PHASE 1 (DIRECTED, EXHAUSTIVE) -- fill and drain completely,
    //  several times round, so the ring WRAPS and the cycle state
    //  inverts in both directions.
    //
    //  Going round more than once is the entire point. A ring that is
    //  filled and drained once, without wrapping, cannot distinguish a
    //  correct cycle-state inversion from no inversion at all.
    // =============================================================
    reset_dut;
    for (lap = 0; lap < 6; lap = lap + 1) begin
      // fill it exactly full
      for (k = 0; k < RING_N; k = k + 1)
        step(1'b1, 16'hA000 + (lap * 16) + k, 1'b0);
      ck(ring_full === 1'b1, "the ring did not report full after RING_N entries");
      // one more must be refused, and must not disturb anything
      step(1'b1, 16'hDEAD, 1'b0);
      ck(prod_ack === 1'b0, "an entry was accepted into a full ring");
      // drain it exactly empty, in order
      for (k = 0; k < RING_N; k = k + 1)
        step(1'b0, 16'd0, 1'b1);
      ck(ring_empty === 1'b1, "the ring did not report empty after draining");
      // one more must be refused
      step(1'b0, 16'd0, 1'b1);
      ck(cons_valid === 1'b0, "an entry came out of an empty ring");
    end

    // =============================================================
    //  PHASE 2 (DIRECTED, EXHAUSTIVE) -- every occupancy from 0 to
    //  RING_N, reached by filling, then one enqueue and one dequeue
    //  attempted at that occupancy.
    // =============================================================
    for (occ = 0; occ <= RING_N; occ = occ + 1) begin
      reset_dut;
      for (k = 0; k < occ; k = k + 1) step(1'b1, 16'hB000 + k, 1'b0);
      // an enqueue at this occupancy
      step(1'b1, 16'hC0DE, 1'b0);
      // a dequeue at this occupancy
      step(1'b0, 16'd0, 1'b1);
      // and both at once, which must do both
      step(1'b1, 16'hBEEF, 1'b1);
    end

    // =============================================================
    //  PHASE 2b (DIRECTED, EXHAUSTIVE) -- close the domain.
    //
    //  The directed phases above reach only 59 of the 72
    //  (occupancy, dequeue pointer) pairs: the ring is only ever EMPTY or
    //  FULL at dequeue pointer 0, because every lap starts and ends there.
    //
    //  The BASE row of the directed-only run exposed this -- it read 1
    //  error, which is `exhaustive sweep incomplete`. The coverage claim
    //  was quietly depending on the RANDOM phase, which means the sweep was
    //  not exhaustive by directed stimulus at all.
    //
    //  Filling k and draining k leaves the ring empty with the pointer at
    //  k, and filling from there reaches full at k.
    // =============================================================
    for (j = 1; j < RING_N; j = j + 1) begin
      reset_dut;
      for (k = 0; k < j; k = k + 1) step(1'b1, 16'h3000 + k, 1'b0);
      for (k = 0; k < j; k = k + 1) step(1'b0, 16'd0, 1'b1);
      ck(ring_empty === 1'b1, "the ring is not empty after matched fill and drain");
      // now empty with the pointer at j: fill it completely and drain again
      for (k = 0; k < RING_N; k = k + 1) step(1'b1, 16'h4000 + k, 1'b0);
      ck(ring_full === 1'b1, "the ring is not full at a non-zero pointer");
      for (k = 0; k < RING_N; k = k + 1) step(1'b0, 16'd0, 1'b1);
      ck(ring_empty === 1'b1, "the ring is not empty after a full lap from j");
    end

    // =============================================================
    //  PHASE 3 (DIRECTED) -- simultaneous enqueue and dequeue, held
    //  at a steady occupancy for many laps.
    //
    //  This is the case that keeps the two pointers a fixed distance
    //  apart while both wrap, so the producer and consumer cycle states
    //  are unequal for half the run. A design that compared pointers
    //  instead of cycle bits would work here and fail nowhere else.
    // =============================================================
    for (occ = 1; occ < RING_N; occ = occ + 1) begin
      reset_dut;
      for (k = 0; k < occ; k = k + 1) step(1'b1, 16'hE000 + k, 1'b0);
      for (k = 0; k < 4 * RING_N; k = k + 1)
        step(1'b1, 16'hF000 + k, 1'b1);
    end

    // =============================================================
    //  PHASE 4 (DIRECTED) -- a full ring drained one entry at a time
    //  while the producer keeps pushing, so the ring stays full and
    //  the wrap happens under back-pressure.
    // =============================================================
    reset_dut;
    for (k = 0; k < RING_N; k = k + 1) step(1'b1, 16'h1000 + k, 1'b0);
    for (k = 0; k < 5 * RING_N; k = k + 1) begin
      // The ring does NOT stay exactly full, and that is correct. On a
      // full ring a simultaneous enqueue and dequeue refuses the enqueue:
      // the producer reads the ring's state as it stood BEFORE this cycle,
      // and a consumer freeing a slot on the same edge is a different agent
      // whose action it cannot have seen. Occupancy settles one below full.
      //
      // Asserting "stays full" here was wrong and produced 40 errors
      // against a correct design.
      step(1'b1, 16'h2000 + k, 1'b1);
      ck(qn >= RING_N - 1,
         "matched traffic drained the ring instead of holding it near full");
      ck(ring_empty === 1'b0, "a ring under matched traffic reported empty");
    end

    // =============================================================
    //  PHASE 5 (RANDOM) -- arbitrary interleaving.
    // =============================================================
`ifndef DIRECTED_ONLY
    reset_dut;
    for (k = 0; k < 40000; k = k + 1)
      step((urand(0) % 3) != 0, urand(0) & 16'hFFFF, (urand(0) % 3) != 0);
`endif

    n_reach = 0;
    for (ri = 0; ri < 72; ri = ri + 1) if (reach[ri]) n_reach = n_reach + 1;

    $display("steps=%0d checks=%0d reach=%0d/72 errors=%0d",
             steps, checks, n_reach, errors);
    $display("[ring] enq=%0d deq=%0d prod_wraps=%0d cons_wraps=%0d full_rejects=%0d empty_reads=%0d",
             n_enq, n_deq, n_prod_wrap, n_cons_wrap, n_full_reject, n_empty_read);
    $display("[the whole point] lost entries = %0d, out-of-order = %0d, false-empty = %0d",
             n_lost, n_wrong, n_stuck);
    if (n_reach != 72) begin
      $display("FAIL: exhaustive sweep incomplete"); errors = errors + 1;
    end
    if (errors == 0) $display("PASS: 0 errors in %0d checks", checks);
    else             $display("FAIL: %0d errors in %0d checks", errors, checks);
    $finish;
  end

endmodule

-- =====================================================================
--  Testbench for xhci_ring (VHDL-2008).
--
--  The shadow tracks occupancy with a COUNTER and a queue, which is
--  exactly the mechanism the design deliberately does not have. The
--  design decides full and empty from single-bit ownership and a pair of
--  cycle states; the model counts. If the cycle-state arithmetic is
--  wrong -- and the one way to get it wrong is to forget the inversion on
--  wrap -- the two disagree immediately, because a counter cannot make
--  that mistake.
-- =====================================================================
library ieee;
use ieee.std_logic_1164.all;
use ieee.numeric_std.all;
use std.textio.all;
use work.xr_pkg.all;

entity tb_xr_vhdl is
  generic (DIRECTED_ONLY : boolean := false);
end entity;

architecture sim of tb_xr_vhdl is
  constant RING_N : natural := 8;

  signal clk       : std_logic := '0';
  signal rst_n     : std_logic := '0';
  signal prod_req  : std_logic := '0';
  signal prod_data : std_logic_vector(15 downto 0) := (others => '0');
  signal cons_req  : std_logic := '0';

  signal prod_ack, ring_full, cons_valid, ring_empty : std_logic;
  signal cons_data : std_logic_vector(15 downto 0);
  signal pcs, ccs  : std_logic;
  signal enq_ptr, deq_ptr : std_logic_vector(3 downto 0);
  signal n_enq, n_deq, n_prod_wrap, n_cons_wrap,
         n_full_reject, n_empty_read, n_owner_error
    : std_logic_vector(31 downto 0);

  signal done : boolean := false;
begin

  dut : entity work.xhci_ring
    generic map (RING_N => RING_N)
    port map (
      clk => clk, rst_n => rst_n,
      prod_req => prod_req, prod_data => prod_data,
      prod_ack => prod_ack, ring_full => ring_full,
      cons_req => cons_req, cons_valid => cons_valid,
      cons_data => cons_data, ring_empty => ring_empty,
      pcs => pcs, ccs => ccs, enq_ptr => enq_ptr, deq_ptr => deq_ptr,
      n_enq => n_enq, n_deq => n_deq,
      n_prod_wrap => n_prod_wrap, n_cons_wrap => n_cons_wrap,
      n_full_reject => n_full_reject, n_empty_read => n_empty_read,
      n_owner_error => n_owner_error);

  clk <= not clk after 5 ns when not done else '0';

  stim : process
    variable errors : natural := 0;
    variable checks : natural := 0;
    variable steps  : natural := 0;

    type q_arr is array (0 to RING_N-1) of std_logic_vector(15 downto 0);
    variable q  : q_arr := (others => (others => '0'));
    variable qh, qt, qn : natural := 0;
    variable x_enq, x_deq, x_full, x_empty : natural := 0;

    variable n_lost, n_wrong, n_stuck : natural := 0;

    variable reach   : std_logic_vector(0 to 71) := (others => '0');
    variable n_reach : natural := 0;

    variable rnd : unsigned(31 downto 0) := x"0008C3D5";
    variable ln  : line;

    procedure ck(cond : boolean; what : string) is
    begin
      checks := checks + 1;
      if not cond then
        errors := errors + 1;
        if errors <= 20 then
          write(ln, string'("  ERROR step=") & integer'image(steps)
                & string'(": ") & what);
          writeline(output, ln);
        end if;
      end if;
    end procedure;

    -- boolean to std_logic: VHDL has no implicit conversion, and a
    -- conditional expression in argument position is VHDL-2019, not 2008.
    function sl_of(b : boolean) return std_logic is
    begin
      if b then return '1'; else return '0'; end if;
    end function;

    impure function nxt_rnd return natural is
    begin
      rnd := rnd xor (rnd sll 13);
      rnd := rnd xor (rnd srl 17);
      rnd := rnd xor (rnd sll 5);
      return to_integer(rnd(14 downto 0));
    end function;

    -- The cycle PARITY is deliberately not a third dimension of the reach
    -- domain: pcs differs from ccs exactly when the producer has lapped the
    -- consumer an odd number of times, which is DETERMINED by the occupancy.
    -- Treating it as free gives a domain half of whose points do not exist.
    procedure mark is
      variable ri : natural;
    begin
      ri := qn * 8 + to_integer(unsigned(deq_ptr));
      if ri < 72 then reach(ri) := '1'; end if;
    end procedure;

    procedure step(pr : std_logic; pd : std_logic_vector(15 downto 0);
                   cr : std_logic) is
      variable e_pack, e_cvalid, e_full, e_empty : boolean;
      variable e_cdata : std_logic_vector(15 downto 0);
    begin
      prod_req <= pr;  prod_data <= pd;  cons_req <= cr;

      -- what SHOULD happen, from the COUNTER
      e_full   := (qn = RING_N);
      e_empty  := (qn = 0);
      e_pack   := (pr = '1') and not e_full;
      e_cvalid := (cr = '1') and not e_empty;
      if e_cvalid then e_cdata := q(qh); else e_cdata := (others => '0'); end if;

      mark;

      -- The status flags are combinational functions of the ring's state,
      -- and the design's whole claim is that single-bit tests compute them
      -- correctly. So they are compared against the counter every cycle.
      ck((ring_full = '1') = e_full,
         "ring_full disagrees with the occupancy count");
      ck((ring_empty = '1') = e_empty,
         "ring_empty disagrees with the occupancy count");
      ck(not (ring_full = '1' and ring_empty = '1'),
         "the ring reported full AND empty");
      if not e_empty and ring_empty = '1' then n_stuck := n_stuck + 1; end if;
      ck(n_stuck = 0, "the ring reported empty with entries in it");

      if e_pack then
        q(qt) := pd;
        qt    := (qt + 1) mod RING_N;
        qn    := qn + 1;
        x_enq := x_enq + 1;
      elsif pr = '1' then
        x_full := x_full + 1;
      end if;

      if e_cvalid then
        qh    := (qh + 1) mod RING_N;
        qn    := qn - 1;
        x_deq := x_deq + 1;
      elsif cr = '1' then
        x_empty := x_empty + 1;
      end if;

      wait until rising_edge(clk);
      wait for 1 ns;
      steps := steps + 1;
      prod_req <= '0';  cons_req <= '0';

      ck((prod_ack = '1') = e_pack, "prod_ack disagrees");
      ck((cons_valid = '1') = e_cvalid, "cons_valid disagrees");

      if e_cvalid then
        if cons_data /= e_cdata then n_wrong := n_wrong + 1; end if;
        ck(cons_data = e_cdata, "the wrong entry came back");
      end if;
      ck(n_wrong = 0, "an entry came back out of order or corrupted");

      ck(to_integer(unsigned(n_enq))         = x_enq,   "enqueue count disagrees");
      ck(to_integer(unsigned(n_deq))         = x_deq,   "dequeue count disagrees");
      ck(to_integer(unsigned(n_full_reject)) = x_full,  "full-reject count disagrees");
      ck(to_integer(unsigned(n_empty_read))  = x_empty, "empty-read count disagrees");
      ck(to_integer(unsigned(n_owner_error)) = 0,
         "the design detected a doubly-owned entry");

      -- Enqueued minus dequeued must equal the occupancy, always. This is
      -- the check a broken wrap shows up in: the entries are still in the
      -- ring and the consumer has decided they belong to somebody else.
      if (x_enq - x_deq) /= qn then n_lost := n_lost + 1; end if;
      ck((x_enq - x_deq) = qn, "accepted entries went missing");
      ck(n_lost = 0, "an accepted entry was lost");

      mark;
    end procedure;

    procedure reset_dut is
    begin
      rst_n <= '0';
      prod_req <= '0';  cons_req <= '0';
      wait until rising_edge(clk);
      wait until rising_edge(clk);
      rst_n <= '1';
      qh := 0; qt := 0; qn := 0;
      x_enq := 0; x_deq := 0; x_full := 0; x_empty := 0;
      wait until rising_edge(clk);
      wait for 1 ns;
    end procedure;
  begin
    -- PHASE 1 (DIRECTED, EXHAUSTIVE) -- fill and drain completely, several
    -- laps, so the ring WRAPS and both cycle states invert.
    --
    -- Going round more than once is the entire point: a ring filled and
    -- drained once, without wrapping, cannot distinguish a correct
    -- cycle-state inversion from no inversion at all.
    reset_dut;
    for lap in 0 to 5 loop
      for k in 0 to RING_N-1 loop
        step('1', std_logic_vector(to_unsigned(16#A000# + lap*16 + k, 16)), '0');
      end loop;
      ck(ring_full = '1', "the ring did not report full after RING_N entries");
      step('1', x"DEAD", '0');
      ck(prod_ack = '0', "an entry was accepted into a full ring");
      for k in 0 to RING_N-1 loop
        step('0', x"0000", '1');
      end loop;
      ck(ring_empty = '1', "the ring did not report empty after draining");
      step('0', x"0000", '1');
      ck(cons_valid = '0', "an entry came out of an empty ring");
    end loop;

    -- PHASE 2 (DIRECTED, EXHAUSTIVE) -- every occupancy 0..RING_N
    for occ in 0 to RING_N loop
      reset_dut;
      for k in 0 to RING_N-1 loop
        if k < occ then
          step('1', std_logic_vector(to_unsigned(16#B000# + k, 16)), '0');
        end if;
      end loop;
      step('1', x"C0DE", '0');
      step('0', x"0000", '1');
      step('1', x"BEEF", '1');
    end loop;

    -- PHASE 2b (DIRECTED, EXHAUSTIVE) -- close the domain.
    --
    -- The directed phases above reach only 59 of the 72
    -- (occupancy, dequeue pointer) pairs: the ring is only ever EMPTY or FULL
    -- at dequeue pointer 0, because every lap starts and ends there. The BASE
    -- row of the directed-only run exposed it -- the coverage claim was
    -- quietly depending on the RANDOM phase.
    for j in 1 to RING_N-1 loop
      reset_dut;
      for k in 0 to RING_N-1 loop
        if k < j then
          step('1', std_logic_vector(to_unsigned(16#3000# + k, 16)), '0');
        end if;
      end loop;
      for k in 0 to RING_N-1 loop
        if k < j then step('0', x"0000", '1'); end if;
      end loop;
      ck(ring_empty = '1', "the ring is not empty after matched fill and drain");
      for k in 0 to RING_N-1 loop
        step('1', std_logic_vector(to_unsigned(16#4000# + k, 16)), '0');
      end loop;
      ck(ring_full = '1', "the ring is not full at a non-zero pointer");
      for k in 0 to RING_N-1 loop
        step('0', x"0000", '1');
      end loop;
      ck(ring_empty = '1', "the ring is not empty after a full lap from j");
    end loop;

    -- PHASE 3 (DIRECTED) -- simultaneous enqueue and dequeue held at a
    -- steady occupancy for many laps, so the two pointers stay a fixed
    -- distance apart while both wrap and the cycle states are unequal for
    -- half the run. A design that compared pointers instead of cycle states
    -- would work here and fail nowhere else.
    for occ in 1 to RING_N-1 loop
      reset_dut;
      for k in 0 to RING_N-1 loop
        if k < occ then
          step('1', std_logic_vector(to_unsigned(16#E000# + k, 16)), '0');
        end if;
      end loop;
      for k in 0 to 4*RING_N-1 loop
        step('1', std_logic_vector(to_unsigned(16#F000# + k, 16)), '1');
      end loop;
    end loop;

    -- PHASE 4 (DIRECTED) -- the wrap under back-pressure.
    --
    -- The ring does NOT stay exactly full, and that is correct: on a full
    -- ring a simultaneous enqueue and dequeue refuses the enqueue, because
    -- the producer reads the state as it stood BEFORE this cycle and a
    -- consumer freeing a slot on the same edge is a different agent whose
    -- action it cannot have seen.
    reset_dut;
    for k in 0 to RING_N-1 loop
      step('1', std_logic_vector(to_unsigned(16#1000# + k, 16)), '0');
    end loop;
    for k in 0 to 5*RING_N-1 loop
      step('1', std_logic_vector(to_unsigned(16#2000# + k, 16)), '1');
      ck(qn >= RING_N - 1,
         "matched traffic drained the ring instead of holding it near full");
      ck(ring_empty = '0', "a ring under matched traffic reported empty");
    end loop;

    -- PHASE 5 (RANDOM)
    if not DIRECTED_ONLY then
      reset_dut;
      for k in 0 to 39999 loop
        step(sl_of((nxt_rnd mod 3) /= 0),
             std_logic_vector(to_unsigned(nxt_rnd mod 65536, 16)),
             sl_of((nxt_rnd mod 3) /= 0));
      end loop;
    end if;

    n_reach := 0;
    for i in 0 to 71 loop
      if reach(i) = '1' then n_reach := n_reach + 1; end if;
    end loop;

    write(ln, string'("steps=") & integer'image(steps)
          & string'(" checks=") & integer'image(checks)
          & string'(" reach=") & integer'image(n_reach) & string'("/72")
          & string'(" errors=") & integer'image(errors));
    writeline(output, ln);
    write(ln, string'("[ring] enq=") & integer'image(x_enq)
          & string'(" deq=") & integer'image(x_deq)
          & string'(" prod_wraps=") & integer'image(to_integer(unsigned(n_prod_wrap)))
          & string'(" cons_wraps=") & integer'image(to_integer(unsigned(n_cons_wrap)))
          & string'(" full_rejects=") & integer'image(x_full)
          & string'(" empty_reads=") & integer'image(x_empty));
    writeline(output, ln);
    write(ln, string'("[the whole point] lost entries = ") & integer'image(n_lost)
          & string'(", out-of-order = ") & integer'image(n_wrong)
          & string'(", false-empty = ") & integer'image(n_stuck));
    writeline(output, ln);
    if n_reach /= 72 then
      write(ln, string'("FAIL: exhaustive sweep incomplete"));
      writeline(output, ln);
      errors := errors + 1;
    end if;
    if errors = 0 then
      write(ln, string'("PASS: 0 errors in ") & integer'image(checks)
            & string'(" checks"));
    else
      write(ln, string'("FAIL: ") & integer'image(errors)
            & string'(" errors in ") & integer'image(checks) & string'(" checks"));
    end if;
    writeline(output, ln);

    done <= true;
    wait;
  end process;

end architecture;