3 files changed, 131 insertions, 0 deletions
diff --git a/collatz/apio.ini b/collatz/apio.ini
new file mode 100644
index 0000000..1faba9f
--- /dev/null
+++ b/collatz/apio.ini
@@ -0,0 +1,3 @@
+[env]
+board = icestick
+
diff --git a/collatz/collatz.v b/collatz/collatz.v
new file mode 100644
index 0000000..e046815
--- /dev/null
+++ b/collatz/collatz.v
@@ -0,0 +1,79 @@
+/**
+  * Collatz Conjecture module.
+  *
+  * Takes a start integer and calculates the number of steps
+  * required for that number to get down to 1 using the collatz
+  * conjecture.
+  */
+module collatz #(
+    parameter integer WIDTH = 16
+) (
+    /* Input clock and reset pin. */
+    input clk,
+    input rst,
+
+    /* The number to calculate. */
+    input wire [WIDTH-1:0] in_start,
+    /* Pulsing the start_int pin will start the calculation. */
+    input wire start_int,
+
+    /* Output count. */
+    output reg [WIDTH-1:0] o_count,
+
+    /* Set to high when the module is idle and ready to start.
+     * While computing, this output is set to low.
+     *
+     * A positive edge of this will indicate the output is ready
+     * to be consumed. */
+    output idle
+);
+
+  // Define some state parameters.
+  localparam integer IDLE = 0;
+  localparam integer SPINNING = 1;
+
+  reg state = 0;
+  reg [WIDTH-1:0] count = 0;
+  reg [WIDTH-1:0] n = 0;
+
+  wire is_even = ~n[0];  // Is the current value even.
+  assign idle = state == IDLE;
+
+  // When the start_int input is set to high, copy the in_start to the current
+  // number and set the state to SPINNING.
+  always @(posedge start_int) begin
+    if (state == IDLE) begin
+      state <= SPINNING;
+      n <= in_start;
+    end
+  end
+
+  // Each clock cycle, determine what needs to happen.
+  always @(posedge clk or posedge rst) begin
+    // On reset, reset the state.
+    if (rst == 1'b1) begin
+      count = 0;
+      state <= IDLE;
+      n <= 0;
+
+      // If the state is idle, reset the count to 0.
+    end else if (state == SPINNING) begin
+      // If n is 1, then  set the output and go back to the IDLE state.
+      if (n <= 1) begin
+        o_count = count;
+        n <= 0;
+        state   = IDLE;
+      end else begin
+        // If is_even, divide by two, otherwise multiply by 3 and add 1.
+        if (is_even) begin
+          n <= n >> 1;
+        end else begin
+          n <= n * 3 + 1;
+        end
+        // Increment the count.
+        count <= count + 1;
+      end
+    end
+  end
+
+endmodule
diff --git a/collatz/collatz_tb.v b/collatz/collatz_tb.v
new file mode 100644
index 0000000..c56b13c
--- /dev/null
+++ b/collatz/collatz_tb.v
@@ -0,0 +1,49 @@
+`timescale 1 ns / 10 ps
+
+module collatz_tb ();
+  reg  clk = 0;
+  reg  rst = 0;
+
+  wire idle;
+
+  localparam integer DURATION = 500_000;
+
+  always begin
+    #41.667;
+    clk = ~clk;
+  end
+
+  reg [24:0] n = 1_000_000;
+  reg start_int;
+
+  wire [24:0] count_out;
+
+  collatz #(
+      .WIDTH(32)
+  ) ctz (
+      .clk(clk),
+      .rst(rst),
+      .in_start(n),
+      .start_int(start_int),
+      .o_count(count_out),
+      .idle(idle)
+  );
+
+  initial begin
+    #10 rst = 1'b1;
+    #1 rst = 1'b0;
+  end
+
+  initial begin
+    $dumpfile("collatz_tb.vcd");
+    $dumpvars(0, collatz_tb);
+
+    #50 start_int = 1;
+    #10 start_int = 0;
+
+    #(DURATION);
+    $display("Finished!");
+    $finish;
+  end
+
+endmodule