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

Subversion Repositories sudoku

[/] [sudoku/] [branches/] [zynq/] [rtl/] [sudoku_search.v] - Blame information for rev 6

Details | Compare with Previous | View Log


module sudoku_search(/*AUTOARG*/
   // Outputs
   outGrid, done, error,
   // Inputs
   clk, rst, start, inGrid
   );
   parameter LG_DEPTH = 6;
   localparam DEPTH = 1 << LG_DEPTH;
 
   input clk;
   input rst;
   input start;
 
   input [728:0] inGrid;
   output [728: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 [6:0]       r_minIdx, t_minIdx;
   reg [8:0]       r_cell, t_cell;
   wire [3:0]      w_ffs;
   wire [8:0]      w_ffs_mask;
 
 
   reg [728:0]     r_board, n_board;
   wire [728:0]   w_stack_out;
   reg [728:0]     t_stack_in;
 
 
   wire [728:0]   s_outGrid;
   wire [8:0]      s_outGrid2d[80:0];
   wire [728:0]   w_nGrid;
 
   reg [8:0]       t_outGrid2d[80: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 [6:0]      w_minIdx, w_unsolvedCells;
   wire [3:0]      w_minPoss;
   wire           w_allDone, w_anyChanged, w_anyError, w_timeOut;
 
   generate
      for(i=0;i<81;i=i+1)
        begin: unflatten
           assign s_outGrid2d[i] = s_outGrid[(9*(i+1))-1:9*i];
        end
   endgenerate
 
   integer j;
   always@(*)
     begin
        for(j=0;j<81;j=j+1)
          begin
             t_outGrid2d[j] = s_outGrid2d[j];
          end
        t_outGrid2d[r_minIdx] = w_ffs_mask;
     end
 
   generate
      for(i=0;i<81;i=i+1)
        begin: flatten
           assign w_nGrid[(9*(i+1)-1):(9*i)] = t_outGrid2d[i];
        end
   endgenerate
 
 
 
   find_first_set ffs0
     (
      .in(r_cell),
      .out(w_ffs),
      .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 = 729'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 === 729'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
                    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 <= 729'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)) 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 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;
   localparam DEPTH = 1 << LG_DEPTH;
 
   input clk;
   input w;
   input [(LG_DEPTH-1):0] addr;
 
   input [728:0] d_in;
   output [728:0] d_out;
 
   reg [728:0]     r_dout;
   assign d_out = r_dout;
 
   reg [728:0]     mem [(DEPTH-1):0];
 
   always@(posedge clk)
     begin
        if(w)
          begin
             if(d_in == 729'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,out_mask,in);
   input [8:0] in;
   output [3:0] out;
   output [8:0] out_mask;
 
   genvar       i;
   wire [8:0]    w_fz;
   wire [8:0]    w_fzo;
   assign w_fz[0] = in[0];
   assign w_fzo[0] = in[0];
 
   assign out = (w_fzo == 9'd1) ? 4'd1 :
                (w_fzo == 9'd2) ? 4'd2 :
                (w_fzo == 9'd4) ? 4'd3 :
                (w_fzo == 9'd8) ? 4'd4 :
                (w_fzo == 9'd16) ? 4'd5 :
                (w_fzo == 9'd32) ? 4'd6 :
                (w_fzo == 9'd64) ? 4'd7 :
                (w_fzo == 9'd128) ? 4'd8 :
                (w_fzo == 9'd256) ? 4'd9 :
                4'hf;
 
   assign out_mask = w_fzo;
 
   generate
      for(i=1;i<9;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 checkCorrect(/*AUTOARG*/
   // Outputs
   y,
   // Inputs
   in
   );
   input [80:0] in;
 
   output       y;
 
   wire [8:0]    grid1d [8:0];
   wire [8:0]    w_set;
 
 
   wire [8:0] w_gridOR =
              grid1d[0] |
              grid1d[1] |
              grid1d[2] |
              grid1d[3] |
              grid1d[4] |
              grid1d[5] |
              grid1d[6] |
              grid1d[7] |
              grid1d[8];
 
   wire       w_allSet = (w_gridOR == 9'b111111111);
   wire       w_allAssign = (w_set == 9'b111111111);
 
   assign y = w_allSet & w_allAssign;
 
   genvar     i;
 
   generate
      for(i=0;i<9;i=i+1)
        begin: unflatten
           assign grid1d[i] = in[(9*(i+1))-1:9*i];
           assign w_set[i] =
                             (grid1d[i] == 9'd1)   |
                             (grid1d[i] == 9'd2)   |
                             (grid1d[i] == 9'd4)   |
                             (grid1d[i] == 9'd8)   |
                             (grid1d[i] == 9'd16)  |
                             (grid1d[i] == 9'd32)  |
                             (grid1d[i] == 9'd64)  |
                             (grid1d[i] == 9'd128) |
                             (grid1d[i] == 9'd256);
        end
   endgenerate
endmodule // correct

Browse

Tools

Subversion Repositories sudoku

[/] [sudoku/] [branches/] [zynq/] [rtl/] [sudoku_search.v] - Blame information for rev 6

Line No.	Rev	Author	Line
1	6	dsheffie	`module sudoku_search(/AUTOARG/`
2			`// Outputs`
3			`outGrid, done, error,`
4			`// Inputs`
5			`clk, rst, start, inGrid`
6			`);`
7			`parameter LG_DEPTH = 6;`
8			`localparam DEPTH = 1 << LG_DEPTH;`
9
10			`input clk;`
11			`input rst;`
12			`input start;`
13
14			`input [728:0] inGrid;`
15			`output [728:0] outGrid;`
16			`output done;`
17			`output error;`
18
19
20			`reg [4:0] r_state, n_state;`
21			`reg [31:0] r_stack_pos, t_stack_pos;`
22			`reg [31:0] t_stack_addr;`
23
24
25			`reg t_write_stack, t_read_stack;`
26			`reg t_clr, t_start;`
27			`reg [6:0] r_minIdx, t_minIdx;`
28			`reg [8:0] r_cell, t_cell;`
29			`wire [3:0] w_ffs;`
30			`wire [8:0] w_ffs_mask;`
31
32
33			`reg [728:0] r_board, n_board;`
34			`wire [728:0] w_stack_out;`
35			`reg [728:0] t_stack_in;`
36
37
38			`wire [728:0] s_outGrid;`
39			`wire [8:0] s_outGrid2d[80:0];`
40			`wire [728:0] w_nGrid;`
41
42			`reg [8:0] t_outGrid2d[80:0];`
43
44			`reg t_done, r_done;`
45			`reg t_error, r_error;`
46
47			`assign done = r_done;`
48			`assign error = r_error;`
49
50			`genvar i;`
51
52			`assign outGrid = s_outGrid;`
53
54			`wire [6:0] w_minIdx, w_unsolvedCells;`
55			`wire [3:0] w_minPoss;`
56			`wire w_allDone, w_anyChanged, w_anyError, w_timeOut;`
57
58			`generate`
59			`for(i=0;i<81;i=i+1)`
60			`begin: unflatten`
61			`assign s_outGrid2d[i] = s_outGrid[(9(i+1))-1:9i];`
62			`end`
63			`endgenerate`
64
65			`integer j;`
66			`always@(*)`
67			`begin`
68			`for(j=0;j<81;j=j+1)`
69			`begin`
70			`t_outGrid2d[j] = s_outGrid2d[j];`
71			`end`
72			`t_outGrid2d[r_minIdx] = w_ffs_mask;`
73			`end`
74
75			`generate`
76			`for(i=0;i<81;i=i+1)`
77			`begin: flatten`
78			`assign w_nGrid[(9(i+1)-1):(9i)] = t_outGrid2d[i];`
79			`end`
80			`endgenerate`
81
82
83
84			`find_first_set ffs0`
85			`(`
86			`.in(r_cell),`
87			`.out(w_ffs),`
88			`.out_mask(w_ffs_mask)`
89			`);`
90
91			`always@(*)`
92			`begin`
93			`t_clr = 1'b0;`
94			`t_start = 1'b0;`
95
96			`t_write_stack = 1'b0;`
97			`t_read_stack = 1'b0;`
98			`t_stack_in = 729'd0;`
99
100			`t_stack_pos = r_stack_pos;`
101			`t_stack_addr = t_stack_pos;`
102
103			`n_state = r_state;`
104			`n_board = r_board;`
105
106			`t_minIdx = r_minIdx;`
107			`t_cell = r_cell;`
108
109			`t_done = r_done;`
110			`t_error = r_error;`
111
112			`case(r_state)`
113			`/* copy input to stack */`
114			`5'd0:`
115			`begin`
116			`if(start)`
117			`begin`
118			`t_write_stack = 1'b1;`
119			`t_stack_pos = r_stack_pos + 32'd1;`
120			`n_state = 5'd1;`
121			`t_stack_in = inGrid;`
122			`end`
123			`else`
124			`begin`
125			`n_state = 5'd0;`
126			`end`
127			`end`
128			`/* pop state off the top of the stack,`
129			`* data valid in the next state */`
130			`5'd1:`
131			`begin`
132			`t_read_stack = 1'b1;`
133			`//$display("reading new board");`
134
135			`t_stack_pos = r_stack_pos - 32'd1;`
136			`t_stack_addr = t_stack_pos;`
137
138			`n_state = (r_stack_pos == 32'd0) ? 5'd31 : 5'd2;`
139			`end`
140			`/* data out of stack ram is`
141			`* valid .. save in register */`
142			`5'd2:`
143			`begin`
144			`t_clr = 1'b1;`
145
146			`n_board = w_stack_out;`
147			`n_state = 5'd3;`
148			`end`
149
150			`/* stack read..valid in r_state */`
151			`5'd3:`
152			`begin`
153			`t_start = 1'b1;`
154			`n_state = 5'd4;`
155			`if(r_board === 729'dx)`
156			`begin`
157			`$display("GOT X!");`
158			`$display("%b", r_board);`
159
160			`$finish();`
161			`end`
162			`end`
163
164			`/* wait for exact cover`
165			`* hardware to complete */`
166			`5'd4:`
167			`begin`
168			`if(w_allDone)`
169			`begin`
170			`n_state = w_anyError ? 5'd1 : 5'd8;`
171			`end`
172			`else if(w_timeOut)`
173			`begin`
174			`t_minIdx = w_minIdx;`
175			`n_state = 5'd5;`
176			`end`
177			`else`
178			`begin`
179			`n_state = 5'd4;`
180			`end`
181			`end // case: 5'd4`
182
183			`5'd5:`
184			`begin`
185			`/* extra cycle */`
186			`t_cell = s_outGrid2d[r_minIdx];`
187			`n_state = 5'd6;`
188			`end`
189
190			`/* timeOut -> push next states onto the stack */`
191			`5'd6:`
192			`begin`
193			`/* if min cell is zero, the board is incorrect`
194			`* and we have no need to push successors */`
195			`if(r_cell == 9'd0)`
196			`begin`
197			`n_state = 5'd1;`
198			`end`
199			`else`
200			`begin`
201			`t_cell = r_cell & (~w_ffs_mask);`
202			`t_stack_in = w_nGrid;`
203			`t_write_stack = 1'b1;`
204			`t_stack_pos = r_stack_pos + 32'd1;`
205			`n_state = (t_stack_pos == (DEPTH-1)) ? 5'd31: 5'd7;`
206			`end`
207			`end`
208
209			`5'd7:`
210			`begin`
211			`n_state = (r_cell == 9'd0) ? 5'd1 : 5'd6;`
212			`end`
213
214			`5'd8:`
215			`begin`
216			`t_done = 1'b1;`
217			`n_state = 5'd8;`
218			`end`
219
220			`5'd31:`
221			`begin`
222			`n_state = 5'd31;`
223			`t_error = 1'b1;`
224			`end`
225
226			`default:`
227			`begin`
228			`n_state = 5'd0;`
229			`end`
230			`endcase // case (r_state)`
231			`end`
232
233
234			`always@(posedge clk)`
235			`begin`
236			`if(rst)`
237			`begin`
238			`r_board <= 729'd0;`
239			`r_state <= 5'd0;`
240			`r_stack_pos <= 32'd0;`
241			`r_minIdx <= 7'd0;`
242			`r_cell <= 9'd0;`
243			`r_done <= 1'b0;`
244			`r_error <= 1'b0;`
245			`end`
246			`else`
247			`begin`
248			`r_board <= n_board;`
249			`r_state <= n_state;`
250			`r_stack_pos <= t_stack_pos;`
251			`r_minIdx <= t_minIdx;`
252			`r_cell <= t_cell;`
253			`r_done <= t_done;`
254			`r_error <= t_error;`
255			`end`
256			`end // always@ (posedge clk)`
257
258			`/* stack ram */`
259
260			`stack_ram #(.LG_DEPTH(LG_DEPTH)) stack0`
261			`(`
262			`// Outputs`
263			`.d_out (w_stack_out),`
264			`// Inputs`
265			`.clk (clk),`
266			`.w (t_write_stack),`
267			`.addr (t_stack_addr[(LG_DEPTH-1):0] ),`
268			`.d_in (t_stack_in)`
269			`);`
270
271
272			`sudoku cover0 (`
273			`// Outputs`
274			`.outGrid (s_outGrid),`
275			`.unsolvedCells (w_unsolvedCells),`
276			`.timeOut (w_timeOut),`
277			`.allDone (w_allDone),`
278			`.anyChanged (w_anyChanged),`
279			`.anyError (w_anyError),`
280			`.minIdx (w_minIdx),`
281			`.minPoss (w_minPoss),`
282			`// Inputs`
283			`.clk (clk),`
284			`.rst (rst),`
285			`.clr (t_clr),`
286			`.start (t_start),`
287			`.inGrid (r_board)`
288			`);`
289
290			`endmodule // sudoku_search`
291
292
293
294			`module stack_ram(/AUTOARG/`
295			`// Outputs`
296			`d_out,`
297			`// Inputs`
298			`clk, w, addr, d_in`
299			`);`
300			`parameter LG_DEPTH = 4;`
301			`localparam DEPTH = 1 << LG_DEPTH;`
302
303			`input clk;`
304			`input w;`
305			`input [(LG_DEPTH-1):0] addr;`
306
307			`input [728:0] d_in;`
308			`output [728:0] d_out;`
309
310			`reg [728:0] r_dout;`
311			`assign d_out = r_dout;`
312
313			`reg [728:0] mem [(DEPTH-1):0];`
314
315			`always@(posedge clk)`
316			`begin`
317			`if(w)`
318			`begin`
319			`if(d_in == 729'dx)`
320			`begin`
321			`$display("pushing X!!!");`
322			`$finish();`
323			`end`
324			`mem[addr] <= d_in;`
325			`end`
326			`else`
327			`begin`
328			`r_dout <= mem[addr];`
329			`end`
330			`end // always@ (posedge clk)`
331
332			`endmodule // stack_ram`
333
334			`module find_first_set(out,out_mask,in);`
335			`input [8:0] in;`
336			`output [3:0] out;`
337			`output [8:0] out_mask;`
338
339			`genvar i;`
340			`wire [8:0] w_fz;`
341			`wire [8:0] w_fzo;`
342			`assign w_fz[0] = in[0];`
343			`assign w_fzo[0] = in[0];`
344
345			`assign out = (w_fzo == 9'd1) ? 4'd1 :`
346			`(w_fzo == 9'd2) ? 4'd2 :`
347			`(w_fzo == 9'd4) ? 4'd3 :`
348			`(w_fzo == 9'd8) ? 4'd4 :`
349			`(w_fzo == 9'd16) ? 4'd5 :`
350			`(w_fzo == 9'd32) ? 4'd6 :`
351			`(w_fzo == 9'd64) ? 4'd7 :`
352			`(w_fzo == 9'd128) ? 4'd8 :`
353			`(w_fzo == 9'd256) ? 4'd9 :`
354			`4'hf;`
355
356			`assign out_mask = w_fzo;`
357
358			`generate`
359			`for(i=1;i<9;i=i+1)`
360			`begin : www`
361			`fz fzN (`
362			`.out(w_fzo[i]),`
363			`.f_out(w_fz[i]),`
364			`.f_in(w_fz[i-1]),`
365			`.in(in[i])`
366			`);`
367			`end`
368			`endgenerate`
369			`endmodule // find_first_set`
370
371			`module fz(/AUTOARG/`
372			`// Outputs`
373			`out, f_out,`
374			`// Inputs`
375			`f_in, in`
376			`);`
377			`input f_in;`
378			`input in;`
379			`output out;`
380			`output f_out;`
381
382			`assign out = in & (~f_in);`
383			`assign f_out = f_in \| in;`
384
385			`endmodule`
386
387
388
389			`module checkCorrect(/AUTOARG/`
390			`// Outputs`
391			`y,`
392			`// Inputs`
393			`in`
394			`);`
395			`input [80:0] in;`
396
397			`output y;`
398
399			`wire [8:0] grid1d [8:0];`
400			`wire [8:0] w_set;`
401
402
403			`wire [8:0] w_gridOR =`
404			`grid1d[0] \|`
405			`grid1d[1] \|`
406			`grid1d[2] \|`
407			`grid1d[3] \|`
408			`grid1d[4] \|`
409			`grid1d[5] \|`
410			`grid1d[6] \|`
411			`grid1d[7] \|`
412			`grid1d[8];`
413
414			`wire w_allSet = (w_gridOR == 9'b111111111);`
415			`wire w_allAssign = (w_set == 9'b111111111);`
416
417			`assign y = w_allSet & w_allAssign;`
418
419			`genvar i;`
420
421			`generate`
422			`for(i=0;i<9;i=i+1)`
423			`begin: unflatten`
424			`assign grid1d[i] = in[(9(i+1))-1:9i];`
425			`assign w_set[i] =`
426			`(grid1d[i] == 9'd1) \|`
427			`(grid1d[i] == 9'd2) \|`
428			`(grid1d[i] == 9'd4) \|`
429			`(grid1d[i] == 9'd8) \|`
430			`(grid1d[i] == 9'd16) \|`
431			`(grid1d[i] == 9'd32) \|`
432			`(grid1d[i] == 9'd64) \|`
433			`(grid1d[i] == 9'd128) \|`
434			`(grid1d[i] == 9'd256);`
435			`end`
436			`endgenerate`
437			`endmodule // correct`