OpenCores
URL https://opencores.org/ocsvn/sudoku/sudoku/trunk

Subversion Repositories sudoku

Compare Revisions

  • This comparison shows the changes necessary to convert path 
    /sudoku/trunk
    from Rev 5 to Rev 7
    ↔ Reverse comparison
  •

Rev 5 → Rev 7

/parameterized_rtl/sudoku_search.v
0,0 → 1,459
module sudoku_search(/*AUTOARG*/
// Outputs
outGrid, done, error,
// Inputs
clk, rst, start, inGrid
);
 
function integer my_clog2;
input integer value;
begin
value = value-1;
for (my_clog2=0; value>0; my_clog2=my_clog2+1)
value = value>>1;
end
endfunction // for
 
parameter LG_DEPTH = 6;
parameter DIM = 3;
localparam DIM_S = (DIM*DIM);
localparam DIM_Q = (DIM_S*DIM_S);
localparam LG_DIM_S = my_clog2(DIM_S);
localparam LG_DIM_Q = my_clog2(DIM_Q);
localparam DEPTH = 1 << LG_DEPTH;
input clk;
input rst;
input start;
input [(DIM_S*DIM_S*DIM_S -1):0] inGrid;
output [(DIM_S*DIM_S*DIM_S - 1):0] outGrid;
output done;
output error;
 
reg [4:0] r_state, n_state;
reg [31:0] r_stack_pos, t_stack_pos;
reg [31:0] t_stack_addr;
 
reg t_write_stack, t_read_stack;
reg t_clr, t_start;
reg [(LG_DIM_Q-1):0] r_minIdx, t_minIdx;
reg [(DIM_S-1):0] r_cell, t_cell;
wire [(DIM_S-1):0] w_ffs_mask;
reg [(DIM_S*DIM_S*DIM_S-1):0] r_board;
reg [(DIM_S*DIM_S*DIM_S-1):0] n_board;
wire [(DIM_S*DIM_S*DIM_S -1):0] w_stack_out;
reg [(DIM_S*DIM_S*DIM_S -1):0] t_stack_in;
 
 
wire [(DIM_S*DIM_S*DIM_S -1):0] s_outGrid;
wire [(DIM_S-1):0] s_outGrid2d[(DIM_Q-1):0];
wire [(DIM_S*DIM_S*DIM_S -1):0] w_nGrid;
reg [(DIM_S-1):0] t_outGrid2d[(DIM_Q-1):0];
 
reg t_done, r_done;
reg t_error, r_error;
assign done = r_done;
assign error = r_error;
genvar i;
 
assign outGrid = s_outGrid;
wire [(LG_DIM_Q-1):0] w_minIdx, w_unsolvedCells;
wire [(LG_DIM_S-1):0] w_minPoss;
wire w_allDone, w_anyChanged, w_anyError, w_timeOut;
 
generate
for(i=0;i<DIM_Q;i=i+1)
begin: unflatten
assign s_outGrid2d[i] = s_outGrid[(DIM_S*(i+1))-1:DIM_S*i];
end
endgenerate
 
integer j;
always@(*)
begin
for(j=0;j<DIM_Q;j=j+1)
begin
t_outGrid2d[j] = s_outGrid2d[j];
end
t_outGrid2d[r_minIdx] = w_ffs_mask;
end
 
generate
for(i=0;i<DIM_Q;i=i+1)
begin: flatten
assign w_nGrid[(DIM_S*(i+1)-1):(DIM_S*i)] = t_outGrid2d[i];
end
endgenerate
find_first_set #(.DIM_S(DIM_S)) ffs0
(
.in(r_cell),
.out_mask(w_ffs_mask)
);
always@(*)
begin
t_clr = 1'b0;
t_start = 1'b0;
t_write_stack = 1'b0;
t_read_stack = 1'b0;
t_stack_in = 'd0;
t_stack_pos = r_stack_pos;
t_stack_addr = t_stack_pos;
n_state = r_state;
n_board = r_board;
 
t_minIdx = r_minIdx;
t_cell = r_cell;
 
t_done = r_done;
t_error = r_error;
case(r_state)
/* copy input to stack */
5'd0:
begin
if(start)
begin
t_write_stack = 1'b1;
t_stack_pos = r_stack_pos + 32'd1;
n_state = 5'd1;
t_stack_in = inGrid;
end
else
begin
n_state = 5'd0;
end
end
/* pop state off the top of the stack,
* data valid in the next state */
5'd1:
begin
t_read_stack = 1'b1;
//$display("reading new board");
t_stack_pos = r_stack_pos - 32'd1;
t_stack_addr = t_stack_pos;
n_state = (r_stack_pos == 32'd0) ? 5'd31 : 5'd2;
end
/* data out of stack ram is
* valid .. save in register */
5'd2:
begin
t_clr = 1'b1;
n_board = w_stack_out;
n_state = 5'd3;
end
 
/* stack read..valid in r_state */
5'd3:
begin
t_start = 1'b1;
n_state = 5'd4;
if(r_board === 'dx)
begin
$display("GOT X!");
$display("%b", r_board);
$finish();
end
end
/* wait for exact cover
* hardware to complete */
5'd4:
begin
if(w_allDone)
begin
n_state = w_anyError ? 5'd1 : 5'd8;
end
else if(w_timeOut)
begin
$display("got time out, min cell in %d", w_minIdx);
t_minIdx = w_minIdx;
n_state = 5'd5;
end
else
begin
n_state = 5'd4;
end
end // case: 5'd4
 
5'd5:
begin
/* extra cycle */
t_cell = s_outGrid2d[r_minIdx];
n_state = 5'd6;
end
/* timeOut -> push next states onto the stack */
5'd6:
begin
/* if min cell is zero, the board is incorrect
* and we have no need to push successors */
if(r_cell == 9'd0)
begin
n_state = 5'd1;
end
else
begin
t_cell = r_cell & (~w_ffs_mask);
t_stack_in = w_nGrid;
t_write_stack = 1'b1;
t_stack_pos = r_stack_pos + 32'd1;
n_state = (t_stack_pos == (DEPTH-1)) ? 5'd31: 5'd7;
end
end
 
5'd7:
begin
n_state = (r_cell == 9'd0) ? 5'd1 : 5'd6;
end
 
5'd8:
begin
t_done = 1'b1;
n_state = 5'd8;
end
5'd31:
begin
n_state = 5'd31;
t_error = 1'b1;
end
default:
begin
n_state = 5'd0;
end
endcase // case (r_state)
end
 
always@(posedge clk)
begin
if(rst)
begin
r_board <= 'd0;
r_state <= 5'd0;
r_stack_pos <= 32'd0;
r_minIdx <= 7'd0;
r_cell <= 9'd0;
r_done <= 1'b0;
r_error <= 1'b0;
end
else
begin
r_board <= n_board;
r_state <= n_state;
r_stack_pos <= t_stack_pos;
r_minIdx <= t_minIdx;
r_cell <= t_cell;
r_done <= t_done;
r_error <= t_error;
end
end // always@ (posedge clk)
 
/* stack ram */
stack_ram #(.LG_DEPTH(LG_DEPTH), .WIDTH(DIM_Q*DIM_S))
stack0
(
// Outputs
.d_out (w_stack_out),
// Inputs
.clk (clk),
.w (t_write_stack),
.addr (t_stack_addr[(LG_DEPTH-1):0] ),
.d_in (t_stack_in)
);
 
sudoku #(.DIM(DIM))
cover0 (
// Outputs
.outGrid (s_outGrid),
.unsolvedCells (w_unsolvedCells),
.timeOut (w_timeOut),
.allDone (w_allDone),
.anyChanged (w_anyChanged),
.anyError (w_anyError),
.minIdx (w_minIdx),
.minPoss (w_minPoss),
// Inputs
.clk (clk),
.rst (rst),
.clr (t_clr),
.start (t_start),
.inGrid (r_board)
);
endmodule // sudoku_search
 
 
 
module stack_ram(/*AUTOARG*/
// Outputs
d_out,
// Inputs
clk, w, addr, d_in
);
parameter LG_DEPTH = 4;
parameter WIDTH = 16;
localparam DEPTH = 1 << LG_DEPTH;
input clk;
input w;
input [(LG_DEPTH-1):0] addr;
input [(WIDTH-1):0] d_in;
output [(WIDTH-1):0] d_out;
 
reg [(WIDTH-1):0] r_dout;
assign d_out = r_dout;
 
reg [(WIDTH-1):0] mem [(DEPTH-1):0];
always@(posedge clk)
begin
if(w)
begin
if(d_in == 'dx)
begin
$display("pushing X!!!");
$finish();
end
mem[addr] <= d_in;
end
else
begin
r_dout <= mem[addr];
end
end // always@ (posedge clk)
 
endmodule // stack_ram
 
module find_first_set(out_mask,in);
parameter DIM_S = 9;
input [(DIM_S-1):0] in;
output [(DIM_S-1):0] out_mask;
genvar i;
wire [(DIM_S-1):0] w_fz;
wire [(DIM_S-1):0] w_fzo;
assign w_fz[0] = in[0];
assign w_fzo[0] = in[0];
 
assign out_mask = w_fzo;
generate
for(i=1;i<DIM_S;i=i+1)
begin : www
fz fzN (
.out(w_fzo[i]),
.f_out(w_fz[i]),
.f_in(w_fz[i-1]),
.in(in[i])
);
end
endgenerate
endmodule // find_first_set
 
module fz(/*AUTOARG*/
// Outputs
out, f_out,
// Inputs
f_in, in
);
input f_in;
input in;
output out;
output f_out;
assign out = in & (~f_in);
assign f_out = f_in | in;
endmodule
module chk_pow2(in, out);
parameter DIM_S = 9;
input [(DIM_S-1):0] in;
output out;
 
wire [(DIM_S-1):0] w_ones = ~('d0);
wire [(DIM_S-1):0] w_m = in + w_ones;
assign out = ((w_m & in) == 'd0) && (in != 'd0);
endmodule // one_set
 
module checkCorrect(/*AUTOARG*/
// Outputs
y,
// Inputs
in
);
parameter DIM_S = 9;
localparam DIM_Q = DIM_S*DIM_S;
input [(DIM_Q-1):0] in;
output y;
wire [(DIM_S-1):0] grid1d [(DIM_S-1):0];
wire [(DIM_S-1):0] w_set;
 
wire [(DIM_S-1):0] w_mask = ~('d0);
wire [(DIM_S-1):0] w_accum_or [(DIM_S-1):0];
genvar i;
generate
for(i=0;i<DIM_S;i=i+1)
begin: accum_or
if(i==0)
begin
assign w_accum_or[i] = grid1d[i];
end
else
begin
assign w_accum_or[i] = w_accum_or[i-1] | grid1d[i];
end
end
endgenerate
 
wire [(DIM_S-1):0] w_gridOR = w_accum_or[(DIM_S-1)];
wire w_allSet = (w_gridOR == w_mask);
wire w_allAssign = (w_set == w_mask);
assign y = w_allSet & w_allAssign;
generate
for(i=0;i<DIM_S;i=i+1)
begin: unflatten
assign grid1d[i] = in[(DIM_S*(i+1))-1:DIM_S*i];
chk_pow2 #(.DIM_S(DIM_S)) pchk (.in(grid1d[i]), .out(w_set[i]));
end
endgenerate
endmodule // checkCorrect
 
/parameterized_rtl/piece.v
0,0 → 1,357
module piece(/*AUTOARG*/
// Outputs
changed, done, curr_value, error,
// Inputs
clk, rst, start, clr, start_value, my_row, my_col, my_square
);
parameter DIM_S = 9;
 
input clk;
input rst;
input start;
input clr;
output changed;
output done;
output error;
input [(DIM_S-1):0] start_value;
output [(DIM_S-1):0] curr_value;
input [(DIM_S*(DIM_S-1)-1):0] my_row;
input [(DIM_S*(DIM_S-1)-1):0] my_col;
input [(DIM_S*(DIM_S-1)-1):0] my_square;
wire [(DIM_S-1):0] row2d [(DIM_S-2):0];
wire [(DIM_S-1):0] col2d [(DIM_S-2):0];
wire [(DIM_S-1):0] sqr2d [(DIM_S-2):0];
 
wire [(DIM_S-1):0] row2d_solv [(DIM_S-2):0];
wire [(DIM_S-1):0] col2d_solv [(DIM_S-2):0];
wire [(DIM_S-1):0] sqr2d_solv [(DIM_S-2):0];
 
reg [(DIM_S-1):0] r_curr_value;
reg [(DIM_S-1):0] t_next_value;
assign curr_value = r_curr_value;
 
reg [2:0] r_state, n_state;
reg r_solved, t_solved;
reg t_changed,r_changed;
reg t_error,r_error;
assign done = r_solved;
assign changed = r_changed;
assign error = r_error;
wire [(DIM_S-1):0] w_solved;
wire w_piece_solved = (w_solved != 'd0);
one_set #(.DIM_S(DIM_S)) s0 (r_curr_value, w_solved);
always@(posedge clk)
begin
if(rst)
begin
r_curr_value <= 'd0;
r_state <= 3'd0;
r_solved <= 1'b0;
r_changed <= 1'b0;
r_error <= 1'b0;
end
else
begin
r_curr_value <= clr ? 'd0 : t_next_value;
r_state <= clr ? 3'd0 : n_state;
r_solved <= clr ? 1'b0 : t_solved;
r_changed <= clr ? 1'b0 : t_changed;
r_error <= clr ? 1'b0 : t_error;
end
end // always@ (posedge clk)
genvar i;
generate
for(i=0;i<(DIM_S-1);i=i+1)
begin: unflatten
assign row2d[i] = my_row[(DIM_S*(i+1))-1:DIM_S*i];
assign col2d[i] = my_col[(DIM_S*(i+1))-1:DIM_S*i];
assign sqr2d[i] = my_square[(DIM_S*(i+1))-1:DIM_S*i];
end
endgenerate
 
generate
for(i=0;i<(DIM_S-1);i=i+1)
begin: unique_rows
one_set #(.DIM_S(DIM_S)) rs (row2d[i], row2d_solv[i]);
one_set #(.DIM_S(DIM_S)) cs (col2d[i], col2d_solv[i]);
one_set #(.DIM_S(DIM_S)) ss (sqr2d[i], sqr2d_solv[i]);
end
endgenerate
 
/* OR output of one_set to find cells
* that are already set in col, grid, row */
wire [(DIM_S-1):0] set_row, set_col, set_sqr;
wire [(DIM_S-1):0] row_or, col_or, sqr_or;
wire [(DIM_S-1):0] w_accum_row2d [(DIM_S-2):0];
wire [(DIM_S-1):0] w_accum_col2d [(DIM_S-2):0];
wire [(DIM_S-1):0] w_accum_sqr2d [(DIM_S-2):0];
 
wire [(DIM_S-1):0] w_accum_row_or [(DIM_S-2):0];
wire [(DIM_S-1):0] w_accum_col_or [(DIM_S-2):0];
wire [(DIM_S-1):0] w_accum_sqr_or [(DIM_S-2):0];
 
generate
for(i=0;i<(DIM_S-1);i=i+1)
begin: set_accums
if(i==0)
begin
assign w_accum_row2d[i] = row2d_solv[i];
assign w_accum_col2d[i] = col2d_solv[i];
assign w_accum_sqr2d[i] = sqr2d_solv[i];
 
assign w_accum_row_or[i] = row2d[i];
assign w_accum_col_or[i] = col2d[i];
assign w_accum_sqr_or[i] = sqr2d[i];
end
else
begin
assign w_accum_row2d[i] = w_accum_row2d[i-1] | row2d_solv[i];
assign w_accum_col2d[i] = w_accum_col2d[i-1] | col2d_solv[i];
assign w_accum_sqr2d[i] = w_accum_sqr2d[i-1] | sqr2d_solv[i];
 
assign w_accum_row_or[i] = w_accum_row_or[i-1] | row2d[i];
assign w_accum_col_or[i] = w_accum_col_or[i-1] | col2d[i];
assign w_accum_sqr_or[i] = w_accum_sqr_or[i-1] | sqr2d[i];
end
end
endgenerate
assign set_row = w_accum_row2d[DIM_S-2];
assign set_col = w_accum_col2d[DIM_S-2];
assign set_sqr = w_accum_sqr2d[DIM_S-2];
 
assign row_or = w_accum_row_or[DIM_S-2];
assign col_or = w_accum_col_or[DIM_S-2];
assign sqr_or = w_accum_sqr_or[DIM_S-2];
 
integer ii;
always@(posedge clk)
begin
if(rst==1'b0)
begin
for(ii=0;ii<(DIM_S-1);ii=ii+1)
begin
if(row2d_solv[ii] === 'dx)
begin
$display("row %d", ii);
$stop();
end
end
end
end
 
 
wire [(DIM_S-1):0] row_nor = ~row_or;
wire [(DIM_S-1):0] col_nor = ~col_or;
wire [(DIM_S-1):0] sqr_nor = ~sqr_or;
 
wire [(DIM_S-1):0] row_singleton;
wire [(DIM_S-1):0] col_singleton;
wire [(DIM_S-1):0] sqr_singleton;
one_set #(.DIM_S(DIM_S)) s1 (r_curr_value & row_nor, row_singleton);
one_set #(.DIM_S(DIM_S)) s2 (r_curr_value & col_nor, col_singleton);
one_set #(.DIM_S(DIM_S)) s3 (r_curr_value & sqr_nor, sqr_singleton);
/* these are the values of the set rows, columns, and
* squares */
wire [(DIM_S-1):0] not_poss = set_row | set_col | set_sqr;
wire [(DIM_S-1):0] new_poss = r_curr_value & (~not_poss);
wire w_piece_zero = (r_curr_value == 'd0);
always@(*)
begin
t_next_value = r_curr_value;
n_state = r_state;
t_solved = r_solved;
t_changed = 1'b0;
t_error = r_error;
case(r_state)
3'd0:
begin
if(start)
begin
t_next_value = start_value;
n_state = 3'd1;
t_changed = 1'b1;
t_error = 1'b0;
end
end
3'd1:
begin
if(w_piece_solved | w_piece_zero)
begin
t_solved = 1'b1;
n_state = 3'd7;
t_changed = 1'b1;
t_error = w_piece_zero;
end
else
begin
t_changed = (new_poss != r_curr_value);
t_next_value = new_poss;
n_state = 3'd2;
end
end // case: 3'd1
3'd2:
begin
if(w_piece_solved | w_piece_zero)
begin
t_solved = 1'b1;
n_state = 3'd7;
t_error = w_piece_zero;
end
else
begin
if(row_singleton != 'd0)
begin
//$display("used row singleton");
t_next_value = row_singleton;
t_changed = 1'b1;
t_solved = 1'b1;
n_state = 3'd7;
end
else if(col_singleton != 'd0)
begin
//$display("used col singleton");
t_next_value = col_singleton;
t_changed = 1'b1;
t_solved = 1'b1;
n_state = 3'd7;
end
else if(sqr_singleton != 'd0)
begin
//$display("used sqr singleton");
t_next_value = sqr_singleton;
t_changed = 1'b1;
t_solved = 1'b1;
n_state = 3'd7;
end
else
begin
n_state = 3'd1;
end
end
end
3'd7:
begin
t_solved = 1'b1;
n_state = 3'd7;
end
 
endcase // case (r_state)
end
endmodule // piece
 
module one_set(in, out);
parameter DIM_S = 9;
input [(DIM_S-1):0] in;
output [(DIM_S-1):0] out;
 
wire [(DIM_S-1):0] w_ones = ~('d0);
wire [(DIM_S-1):0] w_m = in + w_ones;
wire w_pow2 = ((w_m & in) == 'd0) && (in != 'd0);
assign out = {DIM_S{w_pow2}} & in;
endmodule // one_set
 
module ones_count(in, out);
parameter LG_IN_WIDTH = 4;
localparam IN_WIDTH= (1 << LG_IN_WIDTH);
localparam OUT_WIDTH = LG_IN_WIDTH;
input [(IN_WIDTH-1):0] in;
output [(OUT_WIDTH-1):0] out;
 
localparam NUM_COUNT4 = IN_WIDTH/4;
wire [2:0] w_cnt4 [(NUM_COUNT4-1):0];
wire [(OUT_WIDTH-1):0] w_sum [(NUM_COUNT4-1):0];
genvar i;
generate
for(i=0;i<NUM_COUNT4;i=i+1)
begin: count4z
one_count4 cc (in[(4*(i+1))-1:4*(i)], w_cnt4[i]);
end
endgenerate
 
generate
for(i=0;i<NUM_COUNT4;i=i+1)
begin: sumz
if(i==0)
begin
assign w_sum[i] = { {(OUT_WIDTH-3){1'b0}}, w_cnt4[i]};
end
else
begin
assign w_sum[i] = w_sum[i-1] + { {(OUT_WIDTH-3){1'b0}}, w_cnt4[i]};
end
end
endgenerate
 
assign out = w_sum[NUM_COUNT4-1];
endmodule // ones_count
 
/*
module ones_count81(input [80:0] in, output [6:0] out);
wire [83:0] w_in = {3'd0, in};
wire [2:0] ps [20:0];
 
integer x;
reg [6:0] t_sum;
genvar i;
generate
for(i=0;i<21;i=i+1)
begin : builders
one_count4 os (w_in[(4*(i+1)) - 1 : 4*i], ps[i]);
end
endgenerate
always@(*)
begin
t_sum = 7'd0;
for(x = 0; x < 21; x=x+1)
begin
t_sum = t_sum + {3'd0, ps[x]};
end
end
assign out = t_sum;
endmodule // ones_count81
*/
 
module one_count4(input [3:0] in, output [2:0] out);
assign out =
(in == 4'b0000) ? 3'd0 :
(in == 4'b0001) ? 3'd1 :
(in == 4'b0010) ? 3'd1 :
(in == 4'b0011) ? 3'd2 :
(in == 4'b0100) ? 3'd1 :
(in == 4'b0101) ? 3'd2 :
(in == 4'b0110) ? 3'd2 :
(in == 4'b0111) ? 3'd3 :
(in == 4'b1000) ? 3'd1 :
(in == 4'b1001) ? 3'd2 :
(in == 4'b1010) ? 3'd2 :
(in == 4'b1011) ? 3'd3 :
(in == 4'b1100) ? 3'd2 :
(in == 4'b1101) ? 3'd3 :
(in == 4'b1110) ? 3'd3 :
3'd4;
endmodule // one_count4
 
/parameterized_rtl/minPiece.v
0,0 → 1,197
module minPiece(/*AUTOARG*/
// Outputs
minPoss, minIdx,
// Inputs
clk, rst, inGrid
);
 
function integer my_clog2;
input integer value;
begin
value = value-1;
for (my_clog2=0; value>0; my_clog2=my_clog2+1)
value = value>>1;
end
endfunction
parameter DIM = 3;
localparam DIM_S = DIM*DIM;
localparam DIM_Q = DIM_S*DIM_S;
 
localparam LG_DIM_S = my_clog2(DIM_S);
localparam LG_DIM_Q = my_clog2(DIM_Q);
 
localparam PAD_WIDTH = (1<<LG_DIM_Q);
localparam PAD = PAD_WIDTH - DIM_Q;
 
input clk;
input rst;
input [(DIM_S*DIM_S*DIM_S -1):0] inGrid;
 
output [(LG_DIM_S-1):0] minPoss;
output [(LG_DIM_Q-1):0] minIdx;
reg [(LG_DIM_S-1):0] r_minPoss;
reg [(LG_DIM_Q-1):0] r_minIdx;
assign minPoss = r_minPoss;
assign minIdx = r_minIdx;
wire [(DIM_S-1):0] grid2d [(DIM_Q-1):0];
 
wire [(LG_DIM_S-1):0] w_reduce_poss [(LG_DIM_Q):0][(PAD_WIDTH-1):0];
wire [(LG_DIM_Q-1):0] w_reduce_indices [(LG_DIM_Q):0][(PAD_WIDTH-1):0];
genvar i,j;
 
/* unflatten */
generate
for(i=0;i<PAD_WIDTH;i=i+1)
begin: unflatten
if(i < DIM_Q)
begin
assign grid2d[i] = inGrid[(DIM_S*(i+1))-1:DIM_S*i];
countPoss #(.DIM(DIM)) cP1 (.clk(clk), .rst(rst), .in(grid2d[i]), .out(w_reduce_poss[0][i]));
assign w_reduce_indices[0][i] = i;
end
else
begin
assign w_reduce_poss[0][i] = ~0;
assign w_reduce_indices[0][i] = i;
end // else: !if(i < DIM_Q)
//assign w_reduce_indices[0][i] = i;
end
endgenerate
 
localparam RIDX=LG_DIM_Q;
generate
for(i=1;i<(LG_DIM_Q+1);i=i+1)
begin: level_reduce
for(j=0;j<(1<<(LG_DIM_Q-i));j=j+1)
begin: elem_reduce
cmpPiece #(.DIM(DIM)) cmpr
(
.outPoss(w_reduce_poss[i][j]),
.outIdx(w_reduce_indices[i][j]),
.inPoss_0(w_reduce_poss[i-1][2*j]),
.inIdx_0(w_reduce_indices[i-1][2*j]),
.inPoss_1(w_reduce_poss[i-1][2*j+1]),
.inIdx_1(w_reduce_indices[i-1][2*j+1])
);
end
end
endgenerate
always@(posedge clk)
begin
if(rst)
begin
r_minIdx <= 0;
r_minPoss <= (~0);
end
else
begin
r_minIdx <= w_reduce_indices[RIDX][0];
r_minPoss <= w_reduce_poss[RIDX][0];
end
end // always@ (posedge clk)
endmodule // minPiece
 
 
module cmpPiece(/*AUTOARG*/
// Outputs
outPoss, outIdx,
// Inputs
inPoss_0, inIdx_0, inPoss_1, inIdx_1
);
 
function integer my_clog2;
input integer value;
begin
value = value-1;
for (my_clog2=0; value>0; my_clog2=my_clog2+1)
value = value>>1;
end
endfunction // for
parameter DIM=3;
localparam DIM_S = DIM*DIM;
localparam DIM_Q = DIM_S*DIM_S;
localparam LG_DIM_S = my_clog2(DIM_S);
localparam LG_DIM_Q = my_clog2(DIM_Q);
 
input [(LG_DIM_S-1):0] inPoss_0;
input [(LG_DIM_Q-1):0] inIdx_0;
 
input [(LG_DIM_S-1):0] inPoss_1;
input [(LG_DIM_Q-1):0] inIdx_1;
 
output [(LG_DIM_S-1):0] outPoss;
output [(LG_DIM_Q-1):0] outIdx;
wire w_cmp = (inPoss_0 < inPoss_1);
 
assign outPoss = w_cmp ? inPoss_0 : inPoss_1;
assign outIdx = w_cmp ? inIdx_0 : inIdx_1;
endmodule // cmpPiece
 
module countPoss(clk,rst,in,out);
function integer my_clog2;
input integer value;
begin
value = value-1;
for (my_clog2=0; value>0; my_clog2=my_clog2+1)
value = value>>1;
end
endfunction // for
parameter DIM=3;
localparam DIM_S = DIM*DIM;
localparam DIM_Q = DIM_S*DIM_S;
 
localparam LG_DIM_S = my_clog2(DIM_S);
localparam LG_DIM_Q = my_clog2(DIM_Q);
localparam PAD = (1<<LG_DIM_S) - DIM_S;
localparam PAD_WIDTH = (1<<LG_DIM_S);
input [(DIM_S-1):0] in;
input clk;
input rst;
output [(LG_DIM_S-1):0] out;
reg [(LG_DIM_S-1):0] r_out;
assign out = r_out;
 
wire [(PAD_WIDTH-1):0] w_pad_in;
generate
begin: padding
if(PAD > 0)
begin
assign w_pad_in = { {PAD{1'b0}}, in};
end
else
begin
assign w_pad_in = in;
end
end
endgenerate
 
wire [(LG_DIM_S-1):0] w_cnt;
ones_count #(.LG_IN_WIDTH(LG_DIM_S)) c0 (.in(w_pad_in), .out(w_cnt));
wire [(LG_DIM_S-1):0] w_out = (w_cnt == 'd1) ? ~0 : w_cnt;
always@(posedge clk)
begin
r_out <= rst ? ~0 : w_out;
end
endmodule // countPoss
 
/parameterized_rtl/sudoku.v
0,0 → 1,286
module sudoku(/*AUTOARG*/
// Outputs
outGrid, unsolvedCells, timeOut, allDone, anyChanged, anyError,
minIdx, minPoss,
// Inputs
clk, rst, clr, start, inGrid
);
function integer my_clog2;
input integer value;
begin
value = value-1;
for (my_clog2=0; value>0; my_clog2=my_clog2+1)
value = value>>1;
end
endfunction // for
parameter DIM = 3;
localparam DIM_S = (DIM*DIM);
localparam DIM_Q = (DIM_S*DIM_S);
 
localparam LG_DIM_S = my_clog2(DIM_S);
localparam LG_DIM_Q = my_clog2(DIM_Q);
 
localparam PAD_WIDTH = (1<<LG_DIM_Q);
localparam PAD = PAD_WIDTH - DIM_Q;
input clk;
input rst;
input clr;
input start;
input [(DIM_S*DIM_S*DIM_S -1):0] inGrid;
output [(DIM_S*DIM_S*DIM_S - 1):0] outGrid;
 
/* TODO: PARAMETERIZE */
output [(LG_DIM_Q-1):0] unsolvedCells;
output [(LG_DIM_Q-1):0] minIdx;
output [(LG_DIM_S-1):0] minPoss;
output timeOut;
output allDone;
output anyChanged;
output anyError;
 
wire [(DIM_S-1):0] grid2d [(DIM_Q-1):0];
wire [(DIM_S-1):0] currGrid [(DIM_Q-1):0];
wire [(DIM_Q-1):0] done;
wire [(DIM_Q-1):0] changed;
wire [(DIM_Q-1):0] error;
assign allDone = &done;
assign anyChanged = |changed;
//assign anyError = |error;
reg [3:0] r_cnt;
assign timeOut = (r_cnt == 4'b1111);
always@(posedge clk)
begin
if(rst)
begin
r_cnt <= 4'd0;
end
else
begin
r_cnt <= start ? 4'd0 : (|changed ? 4'd0 : r_cnt + 4'd1);
end
end // always@ (posedge clk)
 
minPiece #(.DIM(DIM)) mP0
(
.minPoss(minPoss),
.minIdx(minIdx),
.clk(clk),
.rst(rst),
.inGrid(outGrid)
);
genvar i, j;
genvar ii,jj;
generate
for(i=0;i<DIM_Q;i=i+1)
begin: unflatten
assign grid2d[i] = inGrid[(DIM_S*(i+1))-1:(DIM_S*i)];
end
endgenerate
 
wire [(LG_DIM_Q-1):0] w_unSolvedCells;
reg [(LG_DIM_Q-1):0] r_unSolvedCells;
always@(posedge clk)
begin
if(rst)
begin
r_unSolvedCells <= DIM_Q;
end
else
begin
r_unSolvedCells <= start ? DIM_Q : w_unSolvedCells;
end
end // always@ (posedge clk)
assign unsolvedCells = r_unSolvedCells;
 
wire [(PAD_WIDTH-1):0] w_pad_in;
generate
begin: padding
if(PAD > 0)
begin
assign w_pad_in = { {PAD{1'b0}}, (~done)};
end
else
begin
assign w_pad_in = ~done;
end
end
endgenerate
 
ones_count #(.LG_IN_WIDTH(LG_DIM_Q)) oc1 (.in(w_pad_in), .out(w_unSolvedCells));
wire [(DIM_S*(DIM_S-1)-1):0] w_rows [(DIM_Q-1):0];
wire [(DIM_S*(DIM_S-1)-1):0] w_cols [(DIM_Q-1):0];
wire [(DIM_S*(DIM_S-1)-1):0] w_sqrs [(DIM_Q-1):0];
generate
for(i=0;i<DIM_Q;i=i+1)
begin: pieces
piece # (.DIM_S(DIM_S))
pg (
// Outputs
.changed (changed[i]),
.done (done[i]),
.curr_value (currGrid[i]),
.error (error[i]),
// Inputs
.clk (clk),
.rst (rst),
.clr (clr),
.start (start),
.start_value (grid2d[i]),
.my_row (w_rows[i]),
.my_col (w_cols[i]),
.my_square (w_sqrs[i])
);
end // block: pieces
endgenerate
 
generate
for(i=0;i<DIM_S;i=i+1)
begin: col_outer
for(ii=0;ii<DIM_S;ii=ii+1)
begin: gen_cols
for(jj=0;jj<DIM_S;jj=jj+1)
begin: gen_col_elem
if(i > jj)
begin
assign w_cols[i*DIM_S+ii][(DIM_S*(jj+1)-1):DIM_S*jj] = currGrid[DIM_S*(jj)+ii];
end
 
else if(jj > i)
begin
assign w_cols[i*DIM_S+ii][ (DIM_S*(jj)-1):DIM_S*(jj-1)] = currGrid[ DIM_S*(jj) + ii];
end
end
end // block: gen_cols
end // block: col_outer
endgenerate
 
generate
for(i=0;i<DIM_S;i=i+1)
begin: row_outer
for(ii=0;ii<DIM_S;ii=ii+1)
begin: rows_cols
for(jj=0;jj<DIM_S;jj=jj+1)
begin: gen_row_elem
if(ii > jj)
begin
assign w_rows[i*DIM_S+ii][(DIM_S*(jj+1)-1):DIM_S*jj] = currGrid[DIM_S*(i)+jj];
end
 
else if(jj > ii)
begin
assign w_rows[i*DIM_S+ii][ (DIM_S*(jj)-1):DIM_S*(jj-1)] = currGrid[ DIM_S*(i)+jj];
end
end
end
end
endgenerate
 
 
generate
for(i=0;i<DIM_S;i=i+1)
begin: outer_y_sqr
for(j=0;j<DIM_S;j=j+1)
begin: outer_x_sqr
for(ii=DIM*(i/DIM); ii < DIM*((i/DIM)+1); ii=ii+1)
begin: inner_y_sqr
for(jj=DIM*(j/DIM); jj < DIM*((j/DIM)+1); jj=jj+1)
begin: inner_x_sqr
if((i*DIM_S + j) > (ii*DIM_S + jj))
begin
assign w_sqrs[i*DIM_S+j][(DIM_S*((ii-(DIM*(i/DIM)))*DIM + (jj-(DIM*(j/DIM)))+1) - 1):(DIM_S*((ii-(DIM*(i/DIM)))*DIM + (jj-(DIM*(j/DIM)))))] = currGrid[DIM_S*(ii)+jj];
end
 
else if((i*DIM_S + j) < (ii*DIM_S + jj))
begin
assign w_sqrs[i*DIM_S+j][(DIM_S*((ii-(DIM*(i/DIM)))*DIM + (jj-(DIM*(j/DIM))-1)+1) - 1):(DIM_S*((ii-(DIM*(i/DIM)))*DIM + (jj-(DIM*(j/DIM))-1)))] = currGrid[DIM_S*(ii)+jj];
end
end
end
end
end // block: outer_y_sqr
endgenerate
 
generate
for(i=0;i<DIM_Q;i=i+1)
begin: outGridGen
assign outGrid[(DIM_S*(i+1)-1):(DIM_S*i)] = currGrid[i];
 
end
endgenerate
wire [(DIM_Q-1):0] c_rows [(DIM_S-1):0];
wire [(DIM_Q-1):0] c_cols [(DIM_S-1):0];
wire [(DIM_Q-1):0] c_grds [(DIM_S-1):0];
wire [(3*DIM_S - 1):0] w_correct;
generate
for(ii=0;ii<DIM_S;ii=ii+1)
begin: row_check
for(jj=0;jj<DIM_S;jj=jj+1)
begin: row_elem_check
assign c_rows[jj][(DIM_S*(ii+1)-1):DIM_S*ii] = currGrid[(DIM_S*jj) + ii];
end
end
endgenerate
generate
for(ii=0;ii<DIM_S;ii=ii+1)
begin: col_check
for(jj=0;jj<DIM_S;jj=jj+1)
begin: col_elem_check
assign c_cols[jj][(DIM_S*(ii+1)-1):DIM_S*ii] = currGrid[DIM_S*ii + jj];
end
end
endgenerate
 
genvar iii,jjj;
generate
for(ii=0; ii < DIM; ii=ii+1)
begin: grd_check_y
for(jj = 0; jj < DIM; jj=jj+1)
begin: grd_check_x
for(iii=DIM*ii; iii < DIM*(ii+1); iii=iii+1)
begin: gg_y
for(jjj=DIM*jj; jjj < DIM*(jj+1); jjj=jjj+1)
begin: gg_x
assign c_grds[DIM*ii+jj][DIM_S*(DIM*(iii-DIM*ii) + (jjj-DIM*jj)+1)-1:DIM_S*(DIM*(iii-DIM*ii) + (jjj-DIM*jj))] = currGrid[DIM_S*iii + jjj];
end
end
end
end
endgenerate
generate
for(ii=0;ii<DIM_S;ii=ii+1)
begin: checks
checkCorrect #(.DIM_S(DIM_S)) cC_R
(.y(w_correct[0*(DIM_S) + ii]), .in(c_rows[ii]));
checkCorrect #(.DIM_S(DIM_S)) cC_C
(.y(w_correct[1*(DIM_S) + ii]), .in(c_cols[ii]));
checkCorrect #(.DIM_S(DIM_S)) cC_G
(.y(w_correct[2*(DIM_S) + ii]), .in(c_grds[ii]));
end
endgenerate
assign anyError = ~(&w_correct);
endmodule

powered by: WebSVN 2.1.0

© copyright 1999-2024 OpenCores.org, equivalent to Oliscience, all rights reserved. OpenCores®, registered trademark.