// 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;
    
    initial begin
	busy = 0;
	x = 0;
	y = 0;
	o = 0;
	lsb = 0;
    end // initial begin

    assign done = ((x == y) | (x == 0) | (y == 0)) & busy;

    // 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)

    assign load = start & ~busy;

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