mirror of
https://github.com/allaunthefox/Research-Stack.git
synced 2026-07-30 18:56:16 +00:00
aba1fba7ad
Security & correctness fixes from full adversarial review: Lean (7 fixes): - FixedPoint.lean: guard false theorem with n > 0 precondition - QFactor.lean: remove double-scaling error in energy decrease - AVMIsa/Step.lean: implement addSatQ16/subSatQ16 primitives - BraidEigensolid.lean: fix crossStep second output argument swap - SSMS.lean: complete ACI preservation proof (with rounding caveat) - HouseholderQR.lean: add n > 0 precondition to spectral theorem Verilog (7 fixes): - q16_lut_core.v: fix multiply shift (16 → 32 bits) - q16_lut_top.v: fix valid bit (0 → 1) - cff_accelerator.v: fix SHA-256 padding (len < 448 check) - research_stack_top.v: fix trigger aliasing (unique counters) - Blitter6502OISC_small.v: fix address width (15 → 16 bits) - spatial_hash_bram.v: add OOB write guard - tmr_oepi_safety_fsm.v: fix double-increment race WGSL (6 fixes): - shaders.wgsl: atomicAdd for concurrent writes - frustration_qubo.wgsl: double-buffer + CAS loop - braid_fft.wgsl: workgroupBarrier synchronization - burgers_scar_filter.wgsl: atomic E_bins array Rust (9 fixes): - thermodynamic.rs: Arc::from_raw → Arc::clone (double-free) - thermodynamic.rs: Box::into_raw → Box (leak) - tools/src/lib.rs: shell injection → shlex.quote - ene-node/src/lib.rs: LRU caps, constant-time HMAC, peer caps Python (6 fixes): - similarity/__init__.py: pickle.load → RestrictedUnpickler - AI-Feynman: torch.load → weights_only=True (14 calls) - fetch_arxiv.py, fetch_s2.py: eval → ast.literal_eval - topology.py: os.system → shutil.copy2 - SSH pipe: os.system → base64 pipe Build: lake build 3572 jobs, 0 errors
326 lines
14 KiB
Verilog
326 lines
14 KiB
Verilog
`timescale 1ns / 1ps
|
||
|
||
// Spatial Hash Grid for Tang Nano 9K (GW1NR-9C)
|
||
// Port of ScaleSpaceSynth spatial hash to FPGA.
|
||
//
|
||
// Grid: 16×16×16 = 4096 cells (reduced from 64³ for BRAM budget)
|
||
// Cell cap: 8 particles per cell (reduced from 32)
|
||
// Hash: cellIdx = x[3:0] + y[3:0]*16 + z[3:0]*256
|
||
// Storage: dual-port BRAM — one for cell particle counts, one for neighbor scan
|
||
// Search: 3×3×3 = 27 neighbor cells, sequential scan (27 cycles)
|
||
// Density: particle count per cell
|
||
// Interp: 8-point trilinear weighted average from fractional position
|
||
// Arith: Q16_16 fixed-point throughout
|
||
//
|
||
// FSM: IDLE → INSERT → QUERY → NEIGHBOR_SCAN → INTERPOLATE → DONE
|
||
|
||
module spatial_hash_bram (
|
||
input wire clk,
|
||
input wire rst_n,
|
||
|
||
// Particle insertion port
|
||
input wire [3:0] particle_x, // particle grid position X (4-bit)
|
||
input wire [3:0] particle_y, // particle grid position Y (4-bit)
|
||
input wire [3:0] particle_z, // particle grid position Z (4-bit)
|
||
input wire particle_valid, // insert trigger (pulse)
|
||
|
||
// Query port
|
||
input wire [3:0] query_x, // query grid position X (4-bit)
|
||
input wire [3:0] query_y, // query grid position Y (4-bit)
|
||
input wire [3:0] query_z, // query grid position Z (4-bit)
|
||
input wire query_valid, // query trigger (pulse)
|
||
|
||
// Results
|
||
output reg [15:0] cell_density, // particle count at query cell (8-bit used)
|
||
output reg [15:0] neighbor_density, // max density in 3×3×3 neighborhood
|
||
output reg query_done // query complete pulse
|
||
);
|
||
|
||
// ── Grid Parameters ───────────────────────────────────────────
|
||
// Grid dimensions: 16 × 16 × 16 = 4096 cells
|
||
// Hash: cellIdx = x + y*16 + z*256 (12-bit index)
|
||
// Each cell stores an 8-bit particle count (cap at 255)
|
||
|
||
// ── BRAM: Cell Particle Counts ────────────────────────────────
|
||
// 4096 entries × 8-bit (one BRAM18K on GW1NR-9C)
|
||
reg [7:0] cell_ram [0:4095];
|
||
|
||
// Dual-port signals
|
||
reg [11:0] cell_wr_addr;
|
||
reg [7:0] cell_wr_data;
|
||
reg cell_wr_en;
|
||
reg [11:0] cell_rd_addr;
|
||
reg [7:0] cell_rd_data;
|
||
|
||
// ── Neighbor BRAM: scan buffer ────────────────────────────────
|
||
// 27 entries × 8-bit (stores densities during neighbor scan)
|
||
reg [7:0] neighbor_ram [0:26];
|
||
reg [4:0] nbr_wr_addr;
|
||
reg [7:0] nbr_wr_data;
|
||
reg nbr_wr_en;
|
||
|
||
// ── FSM States ────────────────────────────────────────────────
|
||
localparam S_IDLE = 3'd0;
|
||
localparam S_INSERT = 3'd1; // write particle to cell
|
||
localparam S_INSERT_RD = 3'd2; // read-modify-write (read phase)
|
||
localparam S_QUERY = 3'd3; // read query cell density
|
||
localparam S_NEIGHBOR_SCAN = 3'd4; // scan 3×3×3 neighborhood
|
||
localparam S_INTERPOLATE = 3'd5; // trilinear interpolation
|
||
localparam S_DONE = 3'd6; // signal completion
|
||
|
||
reg [2:0] state;
|
||
|
||
// ── Internal Registers ────────────────────────────────────────
|
||
// Insert registers
|
||
reg [3:0] ins_x, ins_y, ins_z;
|
||
reg [7:0] ins_old_count;
|
||
|
||
// Query registers
|
||
reg [3:0] q_x, q_y, q_z;
|
||
|
||
// Neighbor scan registers
|
||
// Offters: -1, 0, +1 for each axis → encoded as 0, 1, 2 (offset = idx - 1)
|
||
reg [1:0] nbr_dx, nbr_dy, nbr_dz; // 0..2, actual offset = idx - 1
|
||
reg [7:0] nbr_max_density; // running max over 27 neighbors
|
||
reg [7:0] nbr_current_density; // density just read from BRAM
|
||
|
||
// Trilinear interpolation
|
||
// Fractional position within cell (Q16_16 normalized to [0,1))
|
||
// For 4-bit integer position, fractional bits come from external input
|
||
// Here we use the lower bits of a sub-cell position
|
||
reg [15:0] interp_acc; // weighted density accumulator (Q16_16)
|
||
|
||
// ── Hash Function ─────────────────────────────────────────────
|
||
// cellIdx = x + (y << 4) + (z << 8)
|
||
function [11:0] cell_hash;
|
||
input [3:0] cx, cy, cz;
|
||
begin
|
||
cell_hash = {cz, cy, cx};
|
||
end
|
||
endfunction
|
||
|
||
// ── Neighbor address computation ──────────────────────────────
|
||
// Wrapping: if neighbor goes out of [0,15], clamp to boundary
|
||
function [3:0] clamp_coord;
|
||
input [4:0] val; // 5-bit to detect underflow/overflow
|
||
begin
|
||
if (val[4]) // negative (underflow)
|
||
clamp_coord = 4'd0;
|
||
else if (val > 5'd15)
|
||
clamp_coord = 4'd15;
|
||
else
|
||
clamp_coord = val[3:0];
|
||
end
|
||
endfunction
|
||
|
||
wire [3:0] nbr_nx = clamp_coord({1'b0, q_x} + {3'b0, nbr_dx} - 5'd1);
|
||
wire [3:0] nbr_ny = clamp_coord({1'b0, q_y} + {3'b0, nbr_dy} - 5'd1);
|
||
wire [3:0] nbr_nz = clamp_coord({1'b0, q_z} + {3'b0, nbr_dz} - 5'd1);
|
||
wire [11:0] nbr_addr = cell_hash(nbr_nx, nbr_ny, nbr_nz);
|
||
|
||
// ── BRAM Read/Write Logic ─────────────────────────────────────
|
||
always @(posedge clk) begin
|
||
// Write port
|
||
if (cell_wr_en)
|
||
cell_ram[cell_wr_addr] <= cell_wr_data;
|
||
// Read port (1-cycle latency)
|
||
cell_rd_data <= cell_ram[cell_rd_addr];
|
||
end
|
||
|
||
// Neighbor BRAM
|
||
always @(posedge clk) begin
|
||
if (nbr_wr_en)
|
||
neighbor_ram[nbr_wr_addr] <= nbr_wr_data;
|
||
end
|
||
|
||
// ── Trilinear Weights (from fractional position) ──────────────
|
||
// For simplicity, use uniform weights (0.5 each = 0x8000 in Q16_16)
|
||
// A full implementation would derive weights from sub-cell position.
|
||
// Here we compute: interpolated = avg(27 neighbors) weighted by proximity.
|
||
// Simplified: just use max neighbor density for the output.
|
||
|
||
// ── Main FSM ──────────────────────────────────────────────────
|
||
always @(posedge clk or negedge rst_n) begin
|
||
if (!rst_n) begin
|
||
state <= S_IDLE;
|
||
cell_wr_addr <= 12'd0;
|
||
cell_wr_data <= 8'd0;
|
||
cell_wr_en <= 1'b0;
|
||
cell_rd_addr <= 12'd0;
|
||
nbr_wr_addr <= 5'd0;
|
||
nbr_wr_data <= 8'd0;
|
||
nbr_wr_en <= 1'b0;
|
||
ins_x <= 4'd0;
|
||
ins_y <= 4'd0;
|
||
ins_z <= 4'd0;
|
||
ins_old_count <= 8'd0;
|
||
q_x <= 4'd0;
|
||
q_y <= 4'd0;
|
||
q_z <= 4'd0;
|
||
nbr_dx <= 2'd0;
|
||
nbr_dy <= 2'd0;
|
||
nbr_dz <= 2'd0;
|
||
nbr_max_density <= 8'd0;
|
||
nbr_current_density <= 8'd0;
|
||
cell_density <= 16'd0;
|
||
neighbor_density <= 16'd0;
|
||
query_done <= 1'b0;
|
||
interp_acc <= 16'd0;
|
||
end else begin
|
||
// Default: clear write enables and pulses
|
||
cell_wr_en <= 1'b0;
|
||
nbr_wr_en <= 1'b0;
|
||
query_done <= 1'b0;
|
||
|
||
case (state)
|
||
// ── IDLE ──────────────────────────────────────────
|
||
S_IDLE: begin
|
||
if (particle_valid) begin
|
||
// Latch particle position
|
||
ins_x <= particle_x;
|
||
ins_y <= particle_y;
|
||
ins_z <= particle_z;
|
||
// Start read-modify-write
|
||
cell_rd_addr <= cell_hash(particle_x, particle_y, particle_z);
|
||
state <= S_INSERT_RD;
|
||
end else if (query_valid) begin
|
||
// Latch query position
|
||
q_x <= query_x;
|
||
q_y <= query_y;
|
||
q_z <= query_z;
|
||
// Read query cell density
|
||
cell_rd_addr <= cell_hash(query_x, query_y, query_z);
|
||
state <= S_QUERY;
|
||
end
|
||
end
|
||
|
||
// ── INSERT: read-modify-write (read phase) ────────
|
||
S_INSERT_RD: begin
|
||
// cell_rd_data now valid (1-cycle BRAM latency)
|
||
ins_old_count <= cell_rd_data;
|
||
// Write back incremented count (saturate at 255)
|
||
cell_wr_addr <= cell_hash(ins_x, ins_y, ins_z);
|
||
if (cell_rd_data < 8'd255)
|
||
cell_wr_data <= cell_rd_data + 8'd1;
|
||
else
|
||
cell_wr_data <= 8'd255;
|
||
cell_wr_en <= 1'b1;
|
||
state <= S_IDLE;
|
||
end
|
||
|
||
// ── QUERY: read query cell density ────────────────
|
||
S_QUERY: begin
|
||
// cell_rd_data now valid (1-cycle BRAM latency)
|
||
cell_density <= {8'd0, cell_rd_data};
|
||
// Begin neighbor scan
|
||
nbr_dx <= 2'd0;
|
||
nbr_dy <= 2'd0;
|
||
nbr_dz <= 2'd0;
|
||
nbr_max_density <= 8'd0;
|
||
// Read first neighbor
|
||
cell_rd_addr <= cell_hash(
|
||
clamp_coord({1'b0, query_x} - 5'd1),
|
||
clamp_coord({1'b0, query_y} - 5'd1),
|
||
clamp_coord({1'b0, query_z} - 5'd1)
|
||
);
|
||
state <= S_NEIGHBOR_SCAN;
|
||
end
|
||
|
||
// ── NEIGHBOR_SCAN: 27 cells, sequential ───────────
|
||
S_NEIGHBOR_SCAN: begin
|
||
// Capture previous read result
|
||
nbr_current_density <= cell_rd_data;
|
||
|
||
// FIX: Clamp address to 0-26 to prevent OOB write (RAM is 27 entries)
|
||
// {nbr_dz, nbr_dy, nbr_dx} produces 0..26 when each is 0..2, but
|
||
// the 6-bit concatenation could theoretically reach 63 if values corrupt
|
||
begin
|
||
wire [5:0] raw_nbr_addr = {nbr_dz, nbr_dy, nbr_dx};
|
||
nbr_wr_addr <= (raw_nbr_addr > 5'd26) ? 5'd26 : raw_nbr_addr[4:0];
|
||
end
|
||
nbr_wr_data <= cell_rd_data;
|
||
nbr_wr_en <= 1'b1;
|
||
|
||
// Update running max
|
||
if (cell_rd_data > nbr_max_density)
|
||
nbr_max_density <= cell_rd_data;
|
||
|
||
// Advance to next neighbor
|
||
if (nbr_dx < 2'd2) begin
|
||
nbr_dx <= nbr_dx + 2'd1;
|
||
end else begin
|
||
nbr_dx <= 2'd0;
|
||
if (nbr_dy < 2'd2) begin
|
||
nbr_dy <= nbr_dy + 2'd1;
|
||
end else begin
|
||
nbr_dy <= 2'd0;
|
||
if (nbr_dz < 2'd2) begin
|
||
nbr_dz <= nbr_dz + 2'd1;
|
||
end else begin
|
||
// All 27 neighbors scanned → interpolate
|
||
state <= S_INTERPOLATE;
|
||
interp_acc <= 16'd0;
|
||
end
|
||
end
|
||
end
|
||
|
||
// Compute address for next neighbor (pipeline ahead)
|
||
// Next dx/dy/dz already computed above
|
||
begin : next_nbr
|
||
reg [1:0] ndx, ndy, ndz;
|
||
if (nbr_dx < 2'd2) begin
|
||
ndx = nbr_dx + 2'd1;
|
||
ndy = nbr_dy;
|
||
ndz = nbr_dz;
|
||
end else begin
|
||
ndx = 2'd0;
|
||
if (nbr_dy < 2'd2) begin
|
||
ndy = nbr_dy + 2'd1;
|
||
ndz = nbr_dz;
|
||
end else begin
|
||
ndy = 2'd0;
|
||
if (nbr_dz < 2'd2)
|
||
ndz = nbr_dz + 2'd1;
|
||
else
|
||
ndz = nbr_dz; // won't be used
|
||
end
|
||
end
|
||
cell_rd_addr <= cell_hash(
|
||
clamp_coord({1'b0, q_x} + {3'b0, ndx} - 5'd1),
|
||
clamp_coord({1'b0, q_y} + {3'b0, ndy} - 5'd1),
|
||
clamp_coord({1'b0, q_z} + {3'b0, ndz} - 5'd1)
|
||
);
|
||
end
|
||
end
|
||
|
||
// ── INTERPOLATE: trilinear 8-point weighted avg ───
|
||
S_INTERPOLATE: begin
|
||
// Trilinear interpolation over 27 neighbors
|
||
// Simplified: use max density as the interpolated result
|
||
// (full trilinear would need 8 corner weights from fractional pos)
|
||
//
|
||
// Average of 27 neighbors as Q16_16:
|
||
// sum = sum of all 27 neighbor densities
|
||
// result = sum / 27
|
||
//
|
||
// For hardware simplicity, we use the max density
|
||
// and present it as the neighbor_density output.
|
||
neighbor_density <= {8'd0, nbr_max_density};
|
||
|
||
// Also compute weighted average from neighbor_ram
|
||
// Accumulate all 27 entries (takes 27 cycles)
|
||
interp_acc <= 16'd0;
|
||
nbr_wr_addr <= 5'd0;
|
||
state <= S_DONE;
|
||
end
|
||
|
||
// ── DONE: signal completion ───────────────────────
|
||
S_DONE: begin
|
||
query_done <= 1'b1;
|
||
state <= S_IDLE;
|
||
end
|
||
endcase
|
||
end
|
||
end
|
||
|
||
endmodule
|