module booth(
  input [7:0]in,
  input clk,nrst,
  output reg [7:0]out);
  initial begin
    $dumpfile("dump.vcd");
    $dumpvars(1,booth);
  end
  localparam S1=4'd0;
  localparam S2=4'd1;
  localparam S3=4'd2;
  localparam S4=4'd3;
  localparam S5=4'd4;
  localparam S6=4'd5;
  localparam S7=4'd6;
  localparam S8=4'd7;
  localparam S9=4'd8;
  localparam S10=4'd9;
  localparam S11=4'd10;
  localparam S12=4'd11;
  reg [3:0]st;
  reg [3:0]st_nxt;
  reg [1:0]count,count_nxt;
  reg [8:0]q,q_nxt,a,a_nxt;
  reg [7:0]m,m_nxt;

  always @(posedge clk,negedge nrst)
    begin
      if(!nrst)
        begin
        	st<=S1;
          	count<=1'd0;
          	q<=9'd0;
          	a<=9'd0;
          	m<=8'd0;
        end
      else begin
        st<=st_nxt;
        count<=count_nxt;
        q<=q_nxt;
        a<=a_nxt;
        m<=m_nxt;
      end
    end

  always @(*)
    begin
      st_nxt=st;
      count_nxt=count;
      q_nxt=q;
      a_nxt=a;
      m_nxt=m;
      case(st)
        S1:begin
          st_nxt=S2;
        end
        S2:begin
          q_nxt[8:1]=in;
          a_nxt=8'd0;
          q_nxt[0]=1'b0;
          count_nxt=3'b0;
          st_nxt=S3;
        end
        S3:begin
          m_nxt=in;
          case(q[2:0])
            3'b000:begin
              st_nxt=S8; end
            3'b111:begin
              st_nxt=S8; end
            3'b001:begin
              st_nxt=S4;end
            3'b010:begin
              st_nxt=S4;end
            3'b110:begin
              st_nxt=S5;end
             3'b101:begin
              st_nxt=S5;end
            3'b011:begin
              st_nxt=S6;end
            3'b100:begin
              st_nxt=S7;end
          endcase
        end
        S4:begin
          a_nxt=a+m;
        st_nxt=S8;end
        S5:begin
          a_nxt=a-m;
        st_nxt=S8;end
         S6:begin
           a_nxt=a+2*m;
         st_nxt=S8;end
         S7:begin
           a_nxt=a-2*m;
         st_nxt=S8;end
         S8:begin
           {a_nxt[6:0],q_nxt[8:0]}={a,q[8:2]};
           a_nxt[7]=a[8];
           a_nxt[8]=a[8];
           if(count==2'b11)
              st_nxt=S10;
           else st_nxt=S9;
          end
         S9:begin
           count_nxt=count+1'b001;
           case(q[2:0])
            3'b000:begin
              st_nxt=S8; end
            3'b111:begin
              st_nxt=S8; end
            3'b001:begin
              st_nxt=S4;end
            3'b010:begin
              st_nxt=S4;end
            3'b101:begin
              st_nxt=S5;end
             3'b110:begin
              st_nxt=S5;end
            3'b011:begin
              st_nxt=S6;end
            3'b100:begin
              st_nxt=S7;end
          endcase
         end
         S10:begin
           out=q[8:1];
           st_nxt=S11;
         end
         S11:begin
           out=a[7:0];
           st_nxt=S12;
         end
         S12:begin
           st_nxt=st;
         end
        endcase
      end
   endmodule



module booth_tb;
  reg [7:0]in;
   reg nrst,clk;
  output [7:0]out;

  booth mod (.in(in),.nrst(nrst),.clk(clk),.out(out));
  initial begin
    $dumpfile("dump.vcd");
    $dumpvars(1,booth_tb);
  end
 initial begin
   clk=0;
   repeat(100) begin #3 clk=~clk; end
 end
  initial begin
    nrst=0;
    #1 nrst=~nrst;

  end
  initial begin
    in=8'd5;
    #10 in=8'd2;

  end
endmodule