`timescale 1ns / 1ps

module crt(
        input clk,
        input rst,
        input start,

        input [7:0] x_in,

        output busy,
        output reg [7:0] y_out
    );

    // states

    localparam idle = 4'b0000;
    localparam next = 4'b0001;
    localparam reset = 4'b0010;

    localparam y_double_mul_ready = 4'b0011;
    localparam y_triple_mul_start = 4'b0100;
    localparam y_triple_mul_ready = 4'b0101;
    localparam y_inc_b_mul_start = 4'b0110;
    localparam y_inc_b_mul_ready = 4'b0111;
    localparam b_inc_and_shift = 4'b1000;
    localparam x_b_condition = 4'b1001;
    localparam loop = 4'b1010;

    reg [3:0] state, next_state;

    reg [7:0] y, b, x;
    reg [7:0] a_mul1, b_mul1;
    reg start_mul1;
    wire [7:0] result_mul1;
    reg reset_mul1;
    wire busy_mul1;
    reg [4:0] s;
    wire [4:0] end_step;

    mult mul1(
        .clk_i(clk),
        .rst_i(reset_mul1),
        .a_bi(a_mul1),
        .b_bi(b_mul1),
        .start_i(start_mul1),
        .busy_o(busy_mul1),
        .y_bo(result_mul1)
    );

    assign busy = (state != idle);
    assign end_step = (s == 5'd0);

    always@ (posedge clk)
        if(rst)begin
           s <= 6;
           y_out <= 0;
           y <= 0;
           state <= idle;
        end else begin

            case (state)
                reset:
                    begin
                       reset_mul1 <= 0;
                       state <= next;
                    end
                next:
                    begin
                        state <= next_state;
                    end
                idle:
                    if(start) begin // starting y * 2 mul process
                        state <= reset;
                        next_state <= y_double_mul_ready;
                        s <= 6;
                        y <= 0;
                        x <= x_in;
                        reset_mul1 <= 1;
                        start_mul1 <= 1;
                        a_mul1 <= 2;
                        b_mul1 <= y;
                    end
                y_double_mul_ready:  // y = 2 * y
                    if(!busy_mul1) begin
                        state <= y_triple_mul_start;
                        start_mul1 <= 0;
                        y <= result_mul1;
                    end
                y_triple_mul_start: // starting y * 3 mul process
                    begin
                        state <= reset;
                        next_state <= y_triple_mul_ready;
                        reset_mul1 <= 1;
                        start_mul1 <= 1;
                        a_mul1 <= y;
                        b_mul1 <= 3;
                    end
                y_triple_mul_ready: // b = y * 3
                    if(!busy_mul1) begin
                        state <= y_inc_b_mul_start;
                        start_mul1 <= 0;
                        b <= result_mul1;
                    end
                y_inc_b_mul_start: // starting b*(y+1) or 3*y*(y+1) mul process
                    begin
                        state <= reset;
                        next_state <= y_inc_b_mul_ready;
                        reset_mul1 <= 1;
                        start_mul1 <= 1;
                        a_mul1 <= y+1;
                        b_mul1 <= b;
                    end
                y_inc_b_mul_ready: // b = 3*y*(y+1)
                    if(!busy_mul1) begin
                        state <= b_inc_and_shift;
                        b <= result_mul1;
                    end
                b_inc_and_shift: // b = (3*y*(y+1))+1 << s
                    begin
                        state <= x_b_condition;
                        b <= (b+1) << s;
                    end
                x_b_condition: // checking for x >= b and doing operations according to algorithm
                    if( x >= b ) begin
                        state <= loop;
                        x <= x - b;
                        y <= y + 1;
                    end else begin
                        state <= loop;
                    end
                loop: // starting again or finishing calculation
                    begin
                        if (end_step) begin // finishing calculation
                            state <= idle;
                            y_out <= y;
                        end else begin // starting again
                            s <= s-3;
                            state <= reset;
                            next_state <= y_double_mul_ready;
                            a_mul1 <= 2; // starting y * 2 mul process again
                            b_mul1 <= y;
                            reset_mul1 <= 1;
                        end
                    end
            endcase
        end
endmodule


//////////////////////////////////////////////

`timescale 1ns / 1ps

module crt_tb;

reg rst;
reg clk;
reg start;
reg [7:0] x_in;
wire busy;
wire [7:0] y_out;

crt crt_1(
    .clk(clk),
    .rst(rst),
    .start(start),
    .x_in(x_in),
    .busy(busy),
    .y_out(y_out)
);

initial begin
   clk = 0;
   forever #8 clk = !clk;
end

task cub_root_test( input [7:0] x,y);
begin
    rst = 1;
    #100
    rst = 0;
    x_in = x;
    start = 1;
    @(posedge busy);
    start = 0;
    @(negedge busy);
    #5
    if (y == y_out) begin
    $display("x = %d, y = %d - test passed", x_in, y_out);
    end else begin
    $display("x = %d, y = %d - test failed. Correct result is: %d", x_in, y_out, y);
    end
end
endtask

initial begin
   cub_root_test(1,1);
   cub_root_test(8,2);
   cub_root_test(9,2);
   cub_root_test(10,2);
   cub_root_test(14,2);
   cub_root_test(26,2);
   cub_root_test(27,3);
   cub_root_test(64,4);
   cub_root_test(70,4);
   cub_root_test(101,4);
   cub_root_test(125,5);
   cub_root_test(135,5);
   cub_root_test(216,6);
   cub_root_test(255,6);
#1000 $stop;
end

endmodule

//////////////////////////////////////////////////////////////


module mult (
    input clk_i,
    input rst_i,

    input [7:0] a_bi,
    input [7:0] b_bi,
    input start_i,

    output busy_o,
    output reg [15:0] y_bo
);

    localparam IDLE = 1'b0;
    localparam WORK = 1'b1;

    reg  [3:0]  ctr;
    wire [2:0]  ctr_next, end_step;
    wire [7:0]  part_sum;
    wire [15:0] shifted_part_sum;
    reg [7:0]   a, b;
    reg [15:0]   part_res;
    reg state;

    assign part_sum = a & {8{b[ctr]}};
    assign shifted_part_sum = part_sum << ctr;
    assign ctr_next = ctr + 1;
    assign end_step = (ctr == 4'h8);
    assign busy_o = state;

    always@(posedge clk_i)
        if(rst_i) begin
           ctr      <= 0;
           part_res <= 0;
           y_bo     <= 0;

           state <= IDLE;
        end else begin

            case(state)
                IDLE:
                    if(start_i) begin
                        state  <= WORK;

                        a        <= a_bi;
                        b        <= b_bi;
                        ctr      <= 0;
                        part_res <= 0;
                    end
                WORK:
                    begin
                        if(end_step) begin
                            state  <= IDLE;
                            y_bo   <= part_res;
                        end

                        part_res = part_res + shifted_part_sum;
                        ctr <= ctr + 1;
                    end
            endcase
        end

endmodule

///////////////////////////////////

module mult_tb;
reg clk_i;
reg rst_i;
reg [7:0] a_bi;
reg [7:0] b_bi;
reg start_i;
wire busy_o;
wire [7:0] y_bo;

mult mul1 (
        .clk_i(clk_i),
        .rst_i(rst_i),
        .a_bi(a_bi),
        .b_bi(b_bi),
        .start_i(start_i),
        .busy_o(busy_o),
        .y_bo(y_bo)
    );

initial begin
   clk_i = 0;
   forever #8 clk_i = !clk_i;
end

task mull_test(input reg [7:0] a,b,c);
begin
    rst_i = 1;
    #100
    rst_i = 0;
    a_bi = a;
    b_bi = b;
    start_i = 1;
    @(posedge busy_o);
    start_i = 0;
    @(negedge busy_o);
    #5
    if (c == y_bo) begin
    $display("a = %d, b = %d, c = %d - test passed", a, b, c);
    end else begin
    $display("a = %d, b = %d, c = %d - test failed. Correct c is %d", a, b, y_bo, c);
    end
end
endtask

initial begin
mull_test(3,0,0);
mull_test(0,3,0);
mull_test(1,2,2);
mull_test(6,7,42);
#1000 $stop;
end

endmodule