source: vis_dev/vis-2.1/examples/gcd/gcd.v @ 11

// Testbench for the gcd circuit.
module testGcd(clock,x,y,s);
    parameter     N = 8;
    parameter     logN = 3;
    input         clock;
    input [N-1:0] x,y;
    input         s;
    reg [N-1:0]   a,b;
    reg           start;
    wire          busy;
    wire [N-1:0]  o;

    // Unit under test.
    gcd #(N,logN) g(clock,start,a,b,busy,o);

    initial begin
        a = 0;
        b = 0;
        start = 0;
    end

    always @ (posedge clock) begin
        a = x;
        b = y;
        start = s;
    end // always @ (posedge clock)

endmodule // testGcd

// GCD circuit for unsigned N-bit numbers
// a[0], b[0], and o[0] are the least significant bits
//
// Author: Fabio Somenzi <Fabio@Colorado.EDU>
module gcd(clock,start,a,b,busy,o);
    parameter      N = 8;
    parameter      logN = 3;
    input          clock;
    input          start;
    input [N-1:0]  a;
    input [N-1:0]  b;
    output         busy;
    output [N-1:0] o;

    reg [logN-1:0] lsb;
    reg [N-1:0]    x;
    reg [N-1:0]    y;
    wire           done;
    wire           load;
    reg            busy;
    reg [N-1:0]    o;

    wire [1:0]     xy_lsb;
    wire [N-1:0]   diff;

    function select;
        input [N-1:0] z;
        input [logN-1:0] lsb;
        begin: _select
            if (lsb == 3'd0)
              select = z[0];
            else if (lsb == 3'd1)
              select = z[1];
            else if (lsb == 3'd2)
              select = z[2];
            else if (lsb == 3'd3)
              select = z[3];
            else if (lsb == 3'd4)
              select = z[4];
            else if (lsb == 3'd5)
              select = z[5];
            else if (lsb == 3'd6)
              select = z[6];
            else
              select = z[7];
        end // block: _select
    endfunction // select

    assign xy_lsb[1] = select(x,lsb);
    assign xy_lsb[0] = select(y,lsb);
    assign diff = x < y ? y - x : x - y;
    assign done = ((x == y) | (x == 0) | (y == 0)) & busy;      
    assign load = start & ~busy; 
   
    initial begin
        busy = 0;
        x = 0;
        y = 0;
        o = 0;
        lsb = 0;
    end // initial begin

    // Data path.
    always @(posedge clock) begin
        if (load) begin
            x = a;
            y = b;
            lsb = 0;
        end // if (load)
        else if (busy & ~done) begin
            case (xy_lsb)
              2'b00:
                 
                  lsb = lsb + 1;
            
              2'b01:
                  begin
                  x[N-2:0] = x[N-1:1];
                  x[N-1] = 0;
                  end
              2'b10:
                  begin
                  y[N-2:0] = y[N-1:1];
                  y[N-1] = 0;
                  end
              2'b11: begin
                  if (x < y) begin
                      y[N-2:0] = diff[N-1:1];
                      y[N-1] = 0;
                  end // if (x < y)
                  else begin
                      x[N-2:0] = diff[N-1:1];
                      x[N-1] = 0;
                  end // else: !if(x < y)
              end // case: 2b'11
            endcase // case (xy_lsb)
        end // if (~done)
        else if (done) begin
            o = (x < y) ? x : y;
        end // else: !if(~done)
    end // always @ (posedge clock)

   

    // Controller.
    always @(posedge clock) begin
        if (~busy) begin
            if (start) begin
                busy = 1;
            end // if (start)
        end // if (~busy)
        else begin
            if (done) begin
                busy = 0;
            end
        end // else: !if(~busy)
    end // always @ (posedge clock)

endmodule // gcd