Behavioral algorithms (GCD) in Verilog - possible?

Question

I want to write a module for GCD computing, using extended Euclidean algorithm. But the main problem is that I completely don't know how to do that without getting to the lowest (RTL) level. What I mean is to have FSM with three states:

1. IDLE (waiting for input)
2. COMPUTING (as many clock cycles as needed)
3. FINISHED (ready to read output).

However, when I try to separate FSM & computations into separate processes, like this:

module modinv(clk, reset, number, prime, finished, gcd, inverse_fail, inverse);

    input [31:0] number, prime;
    input wire clk, reset;

    output integer gcd, inverse;
    output reg finished, inverse_fail;

    parameter [2:0] IDLE = 3'b001, COMPUTING = 3'b010, END = 3'b100;
    reg [2:0] state, state_next;

    integer a, b, c, q, p, r;

    always @ (posedge clk, posedge reset)
    begin
        if (reset == 1)
            begin
                state <= IDLE;
            end
        else
            begin              
                state <= state_next;
            end
    end

    always @(state or b)
    begin
        finished <= 0;
        inverse_fail <= 0;

        case (state)
            IDLE:
                begin
                    a <= number;
                    b <= prime;
                    p <= 1;
                    r <= 0;
                    state_next <= COMPUTING;
                end
            COMPUTING:
                begin
                    c = a % b;
                    q = a / b;
                    a = b;
                    b = c;
                    r = p - q * r;
                    p = r;

                    if (b == 0)
                        begin
                            state_next <= END;
                        end
                    else
                        begin
                            state_next <= COMPUTING;
                        end
                end
            END:
                begin
                    gcd <= a;
                    inverse <= p;
                    finished <= 1;
                    if (gcd != 1)
                        begin
                            inverse_fail <= 1;
                        end
                end
        endcase
    end

endmodule

And when I try to put computation in the second process, in COMPUTING state case, it only works once - what is correct in means of verilog, because until computing is done, state doesn't change, so the process isn't called again.

However, when I put computation in the first process, there isn't any non-ugly way to limit the computations only to correct STATE, which results in wrong output (as soon as FSM is in FINISHED state, the output is already incorrect - one step further).

So, my question is - how to do it correctly without using FSM + datapath (low-level RTL) solution?

My current waveform:

Answer 1

You seem to be missing some clocked elements in your design.

From what I understand of your design, you seem to expect once the state goes to COMPUTING, it should keep iterating the values of a and b until b reaches 0. But the only thing you're actually clocking on a clock edge is the state variable, so there's no memory of a and b from one state to the next. If you want variables like a and b to have memory from one clock cycle to the next, then you need to latch these variables as well:

I made some modifications to your program, it might not be 100% correct, but you should see what I'm getting at. See if this makes sense how you do the combinational logic in the second block, but you register the values on the posedge so that you can use them at the start of the next clock cycle.

module modinv(clk, reset, number, prime, finished, gcd, inverse_fail, inverse);

    input [31:0] number, prime;
    input wire clk, reset;

    output integer gcd, inverse;
    output reg finished, inverse_fail;

    parameter [2:0] IDLE = 3'b001, COMPUTING = 3'b010, END = 3'b100;
    reg [2:0] state, state_next;

    integer a, b, c, q, p, r;
    integer a_next, b_next, p_next, r_next;

    always @ (posedge clk, posedge reset)
    begin
        if (reset == 1)
            begin
                state <= IDLE;
                a <= 0;
                b <= 0;
                p <= 0;
                r <= 0;
            end
        else
            begin              
                state <= state_next;
                a     <= a_next;
                b     <= b_next;
                p     <= p_next;
                r     <= r_next;
            end
    end

    always @* //just use the auto-triggered '@*' operator
    begin
        finished <= 0;
        inverse_fail <= 0;

        case (state)
            IDLE:
                begin
                    a_next <= number;
                    b_next <= prime;
                    p_next <= 1;
                    r_next <= 0;
                    state_next <= COMPUTING;
                end
            COMPUTING:
                begin
                    c = a % b;
                    q = a / b;
                    a_next = b;
                    b_next = c;
                    r_next = p - q * r;
                    p_next = r;

                    if (b == 0)
                        begin
                            state_next <= END;
                        end
                    else
                        begin
                            state_next <= COMPUTING;
                        end
                end
            END:
                begin
                    gcd <= a;
                    inverse <= p;
                    finished <= 1;
                    if (gcd != 1)
                        begin
                            inverse_fail <= 1;
                        end
                end
        endcase
    end

endmodule