module booth #(parameter WIDTH=4) 
(
  input                    clk,
  input                    enable,
  input        [WIDTH-1:0] multiplier,                            
  input        [WIDTH-1:0] multiplicand,
  output reg               done,
  output reg [2*WIDTH-1:0] product
);

// state encodings.
parameter   IDLE   = 2'b00,
            ADD    = 2'b01,
            SHIFT  = 2'b10,
            OUTPUT = 2'b11;

reg  [1:0]              current_state, next_state;  // state registers.
reg  [2*WIDTH+1:0]      a_reg,s_reg,p_reg,sum_reg;  // computational values.
reg  [WIDTH-1:0]        iter_cnt;                   // iteration count for determining when done.
wire [WIDTH:0]          multiplier_neg;             // negative value of multiplier

// state machine.
always @(posedge clk)
  if (!enable) current_state = IDLE;
  else current_state <= next_state;

always @* begin
  next_state = 2'bx;
  case (current_state)
    IDLE : if (enable) next_state = ADD;
    else        next_state = IDLE;
    ADD  : next_state = SHIFT;
    SHIFT : if (iter_cnt==WIDTH) next_state = OUTPUT;
    else next_state = ADD;
    OUTPUT : next_state = IDLE;
  endcase
end

// negative value of multiplier.
assign multiplier_neg = -{multiplier[WIDTH-1],multiplier}; 
// algorithm implemenation details.
always @(posedge clk) begin
  case (current_state)
    IDLE :  begin
      a_reg    <= {multiplier[WIDTH-1],multiplier,{(WIDTH+1){1'b0}}};
      s_reg    <= {multiplier_neg,{(WIDTH+1){1'b0}}};
      p_reg    <= {{(WIDTH+1){1'b0}},multiplicand,1'b0};
      iter_cnt <= 0;
      done     <= 1'b0;
    end
    ADD  :  begin
      case (p_reg[1:0])
        2'b01       : sum_reg <= p_reg+a_reg;
        2'b10       : sum_reg <= p_reg+s_reg;
        2'b00,2'b11 : sum_reg <= p_reg;
      endcase
      iter_cnt <= iter_cnt + 1;
    end
    SHIFT :  begin
      p_reg <= {sum_reg[2*WIDTH+1],sum_reg[2*WIDTH+1:1]};
    end
    OUTPUT : begin
      product <= p_reg[2*WIDTH:1];
      done <= 1'b1;
    end
  endcase
end
endmodule

// Basic exhaustive self checking test bench.
`define TEST_WIDTH 10
module tb_booth;

reg clk;
reg enable;
integer multiplier;
integer multiplicand;
wire    done;
wire signed [2*`TEST_WIDTH-1:0] product;
wire signed [`TEST_WIDTH-1:0]                m1_in;
wire signed [`TEST_WIDTH-1:0]                m2_in;

assign m1_in = multiplier[`TEST_WIDTH-1:0];
assign m2_in = multiplicand[`TEST_WIDTH-1:0];

booth #(.WIDTH(`TEST_WIDTH)) booth 
(
  .clk(clk),
  .enable(enable),
  .multiplier(multiplier),                            
  .multiplicand(multiplicand),
  .done  (done),
  .product(product)
 );

initial begin
  clk <= 1'b0;
  forever #10 clk = ~clk;
end

integer num_good;
initial begin
  enable = 0;
  num_good = 0;
  repeat (100) @(posedge clk);
  for (multiplier = 0; multiplier < (1<<`TEST_WIDTH); multiplier = multiplier + 1) begin
    for (multiplicand = 0; multiplicand < (1<<`TEST_WIDTH); multiplicand = multiplicand + 1) begin
      enable = 1;
      wait (done == 0);
      wait (done == 1);
      if (m1_in*m2_in !== product) begin
        $display("multiplier = %d multiplicand = %d proudct =%d",m1_in,m2_in,product);
        @(posedge clk);
        $stop;
      end
      else begin
        num_good = num_good + 1;
      end
    end
  end
  $display("sim done. num good = %d",num_good);
  $stop;
end

endmodule