URL
https://opencores.org/ocsvn/integer_square_root/integer_square_root/trunk
Subversion Repositories integer_square_root
Compare Revisions
- This comparison shows the changes necessary to convert path
/integer_square_root
- from Rev 3 to Rev 4
- ↔ Reverse comparison
Rev 3 → Rev 4
/trunk/src/ISR.sv
20,143 → 20,68
////////////////////////////////////////////////////////////////////////////////// |
|
|
typedef enum logic [3:0] { |
INIT, |
GUESS, |
MULT_LOAD, |
MULT_WAIT, |
COMPARE, |
CHANGE, |
CHECK, |
INCRE, |
ENDLOOP, |
DONE |
} state; |
|
module ISR_FSM( |
module ISR( |
input reset, |
input [63:0] value, |
input clock, |
input mult_done, |
input [63:0] mult_result, |
output logic mult_start, |
output logic mult_reset, |
output logic [63:0] mult_input, |
output logic [31:0] result, |
output logic done |
output logic done |
); |
logic [63:0] new_value, proposed_solution_square; |
logic [31:0] proposed_solution; |
logic [4:0] i; |
logic start, it_done, flush; |
logic reset_sync; |
|
logic [63:0] value_reg; |
logic [31:0] result_next, guess, guess_next; |
integer i, i_next; |
|
state current_state, next_state; |
|
assign mult_input = {32'b0, guess}; |
assign mult_start = current_state == MULT_LOAD | current_state == MULT_WAIT; |
assign done = current_state == DONE; |
assign mult_reset = current_state == INIT | current_state == COMPARE; |
|
|
mult Multiplier ( |
.clock(clock), |
.reset(reset), |
.mcand({32'h00000000, proposed_solution}), |
.mplier({32'h00000000, proposed_solution}), |
.start(start), |
.product(proposed_solution_square), |
.done(it_done) |
); |
|
always_comb begin |
guess_next = guess; |
i_next = i; |
result_next = result; |
case (current_state) |
INIT: begin |
guess_next = 32'h0000_0000; |
i_next = 31; |
result_next = 0; |
next_state = GUESS; |
end |
GUESS: begin |
guess_next = guess + (32'h0000_0001 << i); |
next_state = MULT_LOAD; |
end |
MULT_LOAD: next_state = MULT_WAIT; |
MULT_WAIT: next_state = (mult_done) ? COMPARE : MULT_WAIT; |
COMPARE: next_state = (mult_result > value_reg) ? CHANGE : CHECK; |
CHANGE: begin |
guess_next = guess - (32'h0000_0001 << i); |
next_state = CHECK; |
end |
CHECK: next_state = i ? INCRE : ENDLOOP; |
INCRE: begin |
i_next = i - 1; |
next_state = GUESS; |
end |
ENDLOOP: begin |
result_next = guess; |
next_state = DONE; |
end |
DONE: next_state = DONE; |
default: next_state = INIT; |
endcase |
// if (reset_async) begin |
// done = 0; |
// result = 0; |
// end |
// else begin |
// Reduction operator |
// see http://www.asic-world.com/verilog/operators2.html |
// done = ~|i & it_done & ~flush; |
// result[i] = (proposed_solution_square <= new_value) & it_done; |
done = ~|i & it_done & ~flush & ~reset_sync; |
result[i] = (proposed_solution_square <= new_value) & it_done & ~reset_sync; |
// end |
end |
|
always_ff @(posedge clock) begin |
always_ff @(posedge clock or posedge reset) begin |
if (reset) begin |
current_state <= INIT; |
value_reg <= value; |
result <= 32'b0; |
i <= 31; |
guess <= 32'h0000_0000; |
// done <= 0; |
// result <= 0; |
reset_sync <= 1; |
start <= 0; |
flush <= 0; |
i <= 5'b11111; |
proposed_solution <= 32'h80000000; |
new_value <= value; |
end |
else begin |
current_state <= next_state; |
value_reg <= value_reg; |
result <= result_next; |
i <= i_next; |
guess <= guess_next; |
reset_sync <= 0; |
start <= !it_done || !flush; |
flush <= it_done; |
// if (!it_done && flush) begin |
// flush <= 0; |
// end |
if (i && it_done && !flush) begin |
// flush <= 1; |
i <= i - 1; |
proposed_solution[i-1] <= 1; |
proposed_solution[i] <= result[i]; |
end |
end |
end |
|
endmodule |
|
|
|
module ISR( |
input reset, |
input [63:0] value, |
input clock, |
output logic [31:0] result, |
output logic done |
); |
logic mult_start; |
logic mult_done; |
logic [63:0] mult_result; |
logic [63:0] mult_input; |
logic mult_reset; |
|
|
mult multiplier( |
.clock(clock), |
.reset(mult_reset), |
.mcand(mult_input), |
.mplier(mult_input), |
.start(mult_start), |
.product(mult_result), |
.done(mult_done) |
); |
|
ISR_FSM FSM( |
.reset(reset), |
.value(value), |
.clock(clock), |
.mult_done(mult_done), |
.mult_result(mult_result), |
.mult_start(mult_start), |
.mult_reset(mult_reset), |
.mult_input(mult_input), |
.result(result), |
.done(done) |
); |
|
|
endmodule |
|
|
|
|
|
|
/trunk/README.md
0,0 → 1,48
# Integer Square Root |
|
## Algorithm |
|
``` |
procedure ISR(value) |
for i<-31 to 0 do |
proposed_solution[i]<-1 |
if proposed_solution^2 > value then |
proposed_solution[i]<-0 |
end if |
end for |
end procedure |
``` |
|
## Specification |
|
- If reset is asserted during a rising clock edge (synchronous reset), the value signal is to be stored. |
- If reset is asserted part way through a computation, the result of that computation is discarded and a new value is latched into the module. |
- When the module has finished computing the answer, the output is placed on the result line and done line is raised on the same cycle. |
- It must not take more than 600 clock cycles to compute a result (from the last |
clock that reset is asserted to the first clock that done is asserted.) |
|
## ISR State Machine |
|
Computing: $\sqrt{\mathtt{value}}$ |
|
- On a reset |
- guess initialized to `32'h8000_0000` |
- `value` is clocked into a register |
|
- guess gets the next bit set each time we cycle through the FSM again |
|
- Square `guess` (multiply it with itself) |
|
- Wait until the multiplier raises its done |
|
- if `guess` <= `value` |
|
- Keep the current bit |
|
- else |
|
- Clear the current bit |
|
- Move to the next bit |
|
- After the last bit, raise `done` |