OpenCores
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 
    /
    from Rev 3 to Rev 4
    ↔ Reverse comparison
  •

Rev 3 → Rev 4

/integer_square_root/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
 
 
 
 
 
 
/integer_square_root/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`

powered by: WebSVN 2.1.0

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