(1) Modexp with better API. (2) Adding working residue module. (3) Adding new shift32 with carry module needed by the residue module.

3 files changed, 373 insertions, 108 deletions

diff --git a/src/rtl/modexp.v b/src/rtl/modexp.v
index b0e8aa3..8721ce9 100644
--- a/src/rtl/modexp.v
+++ b/src/rtl/modexp.v
@@ -17,10 +17,10 @@
 //
 // The core has a 32-bit memory like interface, but provides
 // status signals to inform the system that a given operation
-// has is done. Additionally, any errors will also be asserted.
+// has completed. Additionally, any errors will also be asserted.
 //
 //
-// Author: Peter Magnusson, Joachim Strombergson
+// Author: Joachim Strombergson, Peter Magnusson
 // Copyright (c) 2015, NORDUnet A/S All rights reserved.
 //
 // Redistribution and use in source and binary forms, with or without
@@ -72,8 +72,15 @@ module modexp(
   localparam ADDR_NAME1          = 8'h01;
   localparam ADDR_VERSION        = 8'h02;
 
-  localparam ADDR_MODSIZE        = 8'h10;
-  localparam ADDR_EXPONENT       = 8'h20;
+  localparam ADDR_CTRL           = 8'h00;
+  localparam CTRL_INIT_BIT       = 0;
+  localparam CTRL_NEXT_BIT       = 1;
+
+  localparam ADDR_STATUS         = 8'h09;
+
+  localparam ADDR_MODSIZE        = 8'h20;
+  localparam ADDR_LENGTH         = 8'h21;
+  localparam ADDR_EXPONENT       = 8'h22;
 
   localparam MODULUS_PREFIX      = 4'h1;
   localparam ADDR_MODULUS_START  = 8'h00;
@@ -117,8 +124,8 @@ module modexp(
   localparam CTRL_CALCULATE_ZN   = 4'h8;
   localparam CTRL_DONE           = 4'h9;
 
-  localparam CORE_NAME0          = 32'h72736120; // "rsa "
-  localparam CORE_NAME1          = 32'h38313932; // "8192"
+  localparam CORE_NAME0          = 32'h6d6f6465; // "mode"
+  localparam CORE_NAME1          = 32'h78702020; // "xp  "
   localparam CORE_VERSION        = 32'h302e3031; // "0.01"
 
 
@@ -309,15 +316,15 @@ module modexp(
                          );
 
   blockmem2r1w p_mem(
-                           .clk(clk),
-                           .read_addr0(p_mem_rd0_addr),
-                           .read_data0(p_mem_rd0_data),
-                           .read_addr1(p_mem_rd1_addr),
-                           .read_data1(p_mem_rd1_data),
-                           .wr(p_mem_we),
-                           .write_addr(p_mem_wr_addr),
-                           .write_data(p_mem_wr_data)
-                           );
+                     .clk(clk),
+                     .read_addr0(p_mem_rd0_addr),
+                     .read_data0(p_mem_rd0_data),
+                     .read_addr1(p_mem_rd1_addr),
+                     .read_data1(p_mem_rd1_data),
+                     .wr(p_mem_we),
+                     .write_addr(p_mem_wr_addr),
+                     .write_data(p_mem_wr_data)
+                    );
 
 
   //----------------------------------------------------------------
@@ -357,8 +364,8 @@ module modexp(
 
           if (length_we)
             begin
-              length_reg <= length_new;
-              length_m1_reg <= length_m1_new;
+              length_reg    <= write_data[7 : 0];
+              length_m1_reg <= write_data[7 : 0] - 8'h1;
             end
 
           if (loop_counter_we)
@@ -382,67 +389,51 @@ module modexp(
       modulus_mem_api_we  = 1'b0;
       exponent_mem_api_we = 1'b0;
       message_mem_api_we  = 1'b0;
+      length_we           = 1'b0;
       tmp_read_data       = 32'h00000000;
 
-      length_new = write_data[7 : 0];
-      length_m1_new = write_data[7 : 0] - 8'h1;
-      length_we = 1'b0;
-
       if (cs)
         begin
           case (address[11 : 8])
             GENERAL_PREFIX:
               begin
-//                if (we)
-//                  begin
-//                    case (address)
-//                      // Write operations.
-//                      ADDR_MODSIZE:
-//                        begin
-//                          modsize_we  = 1;
-//                        end
-//
-//                      ADDR_EXPONENT:
-//                        begin
-//                          exponent_we = 1;
-//                        end
-//
-//                      default:
-//                        begin
-//                          tmp_error = 1;
-//                        end
-//                    endcase // case (addr)
-//                  end // if (write_read)
-//                else
-//                  begin
-//                    case (address)
-//                      // Read operations.
-//                      ADDR_NAME0:
-//                        begin
-//                          tmp_read_data = CORE_NAME0;
-//                        end
-//
-//                      ADDR_NAME1:
-//                        begin
-//                          tmp_read_data = CORE_NAME1;
-//                        end
-//
-//                      ADDR_VERSION:
-//                        begin
-//                          tmp_read_data = CORE_VERSION;
-//                        end
-//
-//                      ADDR_MODSIZE:
-//                        begin
-//                          tmp_read_data = {28'h0000000, modsize_reg};
-//                        end
-//
-//                      default:
-//                        begin
-//                          tmp_error = 1;
-//                        end
-//                    endcase // case (addr)
-//                  end
+                if (we)
+                  begin
+                    case (address[7 : 0])
+                      ADDR_LENGTH:
+                        length_we = 1'b1;
+
+                      default:
+                        begin
+                        end
+                    endcase // case (address[7 : 0])
+                  end
+                else
+                  begin
+                    case (address[7 : 0])
+                      ADDR_NAME0:
+                        tmp_read_data = CORE_NAME0;
+
+                      ADDR_NAME1:
+                        tmp_read_data = CORE_NAME1;
+
+                      ADDR_VERSION:
+                        tmp_read_data = CORE_VERSION;
+
+                      ADDR_CTRL:
+                        tmp_read_data = 32'h00000000;
+
+                      ADDR_STATUS:
+                        tmp_read_data = 32'h00000000;
+
+                      ADDR_LENGTH:
+                        tmp_read_data = {24'h000000, length_reg};
+
+                      default:
+                        begin
+                        end
+                    endcase // case (address[7 : 0])
+                  end
               end
 
             MODULUS_PREFIX:
@@ -486,24 +477,6 @@ module modexp(
                 tmp_read_data = result_mem_api_rd_data;
               end
 
-            LENGTH_PREFIX:
-              begin
-                if (we)
-                  length_we = 1'b1;
-              end
-
-//            RESULT_PREFIX:
-//              begin
-//                if (we)
-//                  begin
-//                    modulus_mem_api_we = 1'b1;
-//                  end
-//                else
-//                  begin
-//                    tmp_read_data = modulus_mem_int_rd_data;
-//                  end
-//              end
-
             default:
               begin
 
@@ -574,6 +547,7 @@ module modexp(
       endcase // case (montprod_selcect_reg)
     end
 
+
   //----------------------------------------------------------------
   // memory write mux
   //
@@ -604,6 +578,7 @@ module modexp(
         result_mem_int_we = result_mem_int_we & ei_reg;
     end
 
+
   //----------------------------------------------------------------
   // loop_counter
   //
@@ -640,6 +615,7 @@ module modexp(
       endcase
     end
 
+
   //----------------------------------------------------------------
   // exponent
   //
@@ -660,6 +636,7 @@ module modexp(
         ei_we = 1'b0;
     end
 
+
   //----------------------------------------------------------------
   // modexp_ctrl
   //
diff --git a/src/rtl/residue.v b/src/rtl/residue.v
index 2991dd6..3fa1666 100644
--- a/src/rtl/residue.v
+++ b/src/rtl/residue.v
@@ -52,7 +52,7 @@ module residue(
   input wire  calculate,
   output wire ready,
 
-  input wire  [07 : 0] nn,
+  input wire  [14 : 0] nn, //MAX(2*N)=8192*2 (14 bit)
   input wire  [07 : 0] length,
 
   output wire [07 : 0] opa_rd_addr,
@@ -71,16 +71,24 @@ module residue(
 //----------------------------------------------------------------
 
 
+// m_residue_2_2N_array( N, M, Nr)
+//   Nr = 00...01 ; Nr = 1 == 2**(2N-2N)
+//   for (int i = 0; i < 2 * N; i++)
+//     Nr = Nr shift left 1
+//     if (Nr less than M) continue;
+//     Nr = Nr - M
+// return Nr
+//
 localparam CTRL_IDLE          = 4'h0;
-localparam CTRL_INIT          = 4'h1;
+localparam CTRL_INIT          = 4'h1; // Nr = 00...01 ; Nr = 1 == 2**(2N-2N)
 localparam CTRL_INIT_STALL    = 4'h2;
-localparam CTRL_SHL           = 4'h3;
+localparam CTRL_SHL           = 4'h3; // Nr = Nr shift left 1
 localparam CTRL_SHL_STALL     = 4'h4;
-localparam CTRL_COMPARE       = 4'h5;
+localparam CTRL_COMPARE       = 4'h5; //if (Nr less than M) continue;
 localparam CTRL_COMPARE_STALL = 4'h6;
-localparam CTRL_SUB           = 4'h7;
+localparam CTRL_SUB           = 4'h7; //Nr = Nr - M
 localparam CTRL_SUB_STALL     = 4'h8;
-localparam CTRL_LOOP          = 4'h9;
+localparam CTRL_LOOP          = 4'h9; //for (int i = 0; i < 2 * N; i++)
 
 //----------------------------------------------------------------
 // Registers including update variables and write enable.
@@ -99,7 +107,27 @@ reg [03 : 0] residue_ctrl_new;
 reg          residue_ctrl_we;
 reg          reset_word_index;
 reg          reset_n_counter;
-reg [07 : 0] word_index;
+reg [14 : 0] loop_counter_1_to_nn_reg; //for i = 1 to nn (2*N)
+reg [14 : 0] loop_counter_1_to_nn_new;
+reg          loop_counter_1_to_nn_we;
+reg [14 : 0] nn_reg;
+reg          nn_we;
+reg [07 : 0] length_m1_reg;
+reg [07 : 0] length_m1_new;
+reg          length_m1_we;
+reg [07 : 0] word_index_reg;
+reg [07 : 0] word_index_new;
+reg          word_index_we;
+
+reg  [31 : 0] one_data;
+wire [31 : 0] sub_data;
+wire [31 : 0] shl_data;
+reg           sub_carry_in_new;
+reg           sub_carry_in_reg;
+wire          sub_carry_out;
+reg           shl_carry_in_new;
+reg           shl_carry_in_reg;
+wire          shl_carry_out;
 
 //----------------------------------------------------------------
 // Concurrent connectivity for ports etc.
@@ -107,10 +135,29 @@ reg [07 : 0] word_index;
 assign opa_rd_addr = opa_rd_addr_reg;
 assign opa_wr_addr = opa_wr_addr_reg;
 assign opa_wr_data = opa_wr_data_reg;
+assign opa_wr_we   = opa_wr_we_reg;
 assign opm_addr    = opm_addr_reg;
 assign ready       = ready_reg;
 
 
+  //----------------------------------------------------------------
+  // Instantions
+  //----------------------------------------------------------------
+  adder32 subcmp(
+    .a(opa_rd_data),
+    .b( ~ opm_data),
+    .carry_in(sub_carry_in_reg),
+    .sum(sub_data),
+    .carry_out(sub_carry_out)
+  );
+
+  shl32 shl(
+    .a(opa_rd_data),
+    .carry_in(shl_carry_in_reg),
+    .amul2(shl_data),
+    .carry_out(shl_carry_out)
+  );
+
 
 
   //----------------------------------------------------------------
@@ -121,25 +168,168 @@ assign ready       = ready_reg;
       if (!reset_n)
         begin
           residue_ctrl_reg <= CTRL_IDLE;
+          word_index_reg   <= 8'h0;
+          length_m1_reg    <= 8'h0;
+          nn_reg           <= 15'h0;
+          loop_counter_1_to_nn_reg <= 15'h0;
+          ready_reg        <= 1'b1;
+          sub_carry_in_reg <= 1'b0;
+          shl_carry_in_reg <= 1'b0;
         end
       else
         begin
           if (residue_ctrl_we)
             residue_ctrl_reg <= residue_ctrl_new;
+
+          if (word_index_we)
+            word_index_reg <= word_index_new;
+
+          if (length_m1_we)
+            length_m1_reg <= length_m1_new;
+
+          if (nn_we)
+            nn_reg <= nn;
+
+          if (loop_counter_1_to_nn_we)
+            loop_counter_1_to_nn_reg <= loop_counter_1_to_nn_new;
+
+          if (ready_we)
+            ready_reg <= ready_new;
+
+          sub_carry_in_reg <= sub_carry_in_new;
+          shl_carry_in_reg <= shl_carry_in_new;
         end
     end // reg_update
 
 
   //----------------------------------------------------------------
+  // loop counter process. implements for (int i = 0; i < 2 * N; i++)
+  //
+  // m_residue_2_2N_array( N, M, Nr)
+  //   Nr = 00...01 ; Nr = 1 == 2**(2N-2N)
+  //   for (int i = 0; i < 2 * N; i++)
+  //     Nr = Nr shift left 1
+  //     if (Nr less than M) continue;
+  //     Nr = Nr - M
+  // return Nr
+  //
   //----------------------------------------------------------------
   always @*
     begin : process_1_to_2n
+      loop_counter_1_to_nn_new = loop_counter_1_to_nn_reg + 15'h1;
+      loop_counter_1_to_nn_we  = 1'b0;
+
+      if (reset_n_counter)
+        begin
+         loop_counter_1_to_nn_new = 15'h1;
+         loop_counter_1_to_nn_we  = 1'b1;
+        end
+
+      if (residue_ctrl_reg == CTRL_LOOP)
+        loop_counter_1_to_nn_we  = 1'b1;
     end
 
   //----------------------------------------------------------------
+  // implements looping over words in a multiword operation
   //----------------------------------------------------------------
   always @*
     begin : word_index_process
+      word_index_new = word_index_reg - 8'h1;
+      word_index_we  = 1'b1;
+
+      if (reset_word_index)
+        word_index_new = length_m1_reg;
+
+      if (residue_ctrl_reg == CTRL_IDLE)
+        word_index_new = length_m1_new; //reduce a pipeline stage with early read
+
+    end
+
+  //----------------------------------------------------------------
+  // writer process. implements:
+  //   Nr = 00...01 ; Nr = 1 == 2**(2N-2N)
+  //   Nr = Nr shift left 1
+  //   Nr = Nr - M
+  //
+  // m_residue_2_2N_array( N, M, Nr)
+  //   Nr = 00...01 ; Nr = 1 == 2**(2N-2N)
+  //   for (int i = 0; i < 2 * N; i++)
+  //     Nr = Nr shift left 1
+  //     if (Nr less than M) continue;
+  //     Nr = Nr - M
+  // return Nr
+  //----------------------------------------------------------------
+  always @*
+    begin : writer_process
+      opa_wr_addr_reg = word_index_reg;
+      case (residue_ctrl_reg)
+        CTRL_INIT:
+          begin
+            opa_wr_data_reg = one_data;
+            opa_wr_we_reg   = 1'b1;
+          end
+
+        CTRL_SUB:
+          begin
+            opa_wr_data_reg = sub_data;
+            opa_wr_we_reg   = 1'b1;
+          end
+
+        CTRL_SHL:
+          begin
+            opa_wr_data_reg = shl_data;
+            opa_wr_we_reg   = 1'b1;
+          end
+
+        default:
+          begin
+            opa_wr_data_reg = 32'h0;
+            opa_wr_we_reg   = 1'b0;
+          end
+      endcase
+    end
+
+  //----------------------------------------------------------------
+  // reader process. reads from new value because it occurs one
+  // cycle earlier than the writer.
+  //----------------------------------------------------------------
+  always @*
+    begin : reader_process
+      opa_rd_addr_reg = word_index_new;
+      opm_addr_reg    = word_index_new;
+    end
+
+  //----------------------------------------------------------------
+  // carry process. "Ripple carry awesomeness!"
+  //----------------------------------------------------------------
+  always @*
+    begin : carry_process
+      case (residue_ctrl_reg)
+        CTRL_COMPARE:
+          sub_carry_in_new = sub_carry_out;
+        CTRL_SUB:
+          sub_carry_in_new = sub_carry_out;
+        default:
+          sub_carry_in_new = 1'b1;
+      endcase
+
+      case (residue_ctrl_reg)
+        CTRL_SHL:
+          shl_carry_in_new = shl_carry_out;
+        default:
+          shl_carry_in_new = 1'b0;
+      endcase
+    end
+
+  //----------------------------------------------------------------
+  // Nr = 00...01 ; Nr = 1 == 2**(2N-2N)
+  //----------------------------------------------------------------
+  always @*
+    begin : one_process
+      one_data = 32'h0;
+      if (residue_ctrl_reg == CTRL_INIT)
+        if (word_index_reg == length_m1_reg)
+          one_data = 32'h1;
     end
 
 //----------------------------------------------------------------
@@ -151,11 +341,18 @@ always @*
   begin : residue_ctrl
     ready_new = 1'b0;
     ready_we  = 1'b0;
+
     residue_ctrl_new = CTRL_IDLE;
     residue_ctrl_we  = 1'b0;
+
     reset_word_index = 1'b0;
     reset_n_counter  = 1'b0;
 
+    length_m1_new  = length - 8'h1;
+    length_m1_we   = 1'b0;
+
+    nn_we = 1'b0;
+
     case (residue_ctrl_reg)
       CTRL_IDLE:
         if (calculate)
@@ -165,10 +362,12 @@ always @*
             residue_ctrl_new = CTRL_INIT;
             residue_ctrl_we  = 1'b1;
             reset_word_index = 1'b1;
+            length_m1_we     = 1'b1;
+            nn_we            = 1'b1;
           end
 
       CTRL_INIT:
-        if (word_index == 8'h0)
+        if (word_index_reg == 8'h0)
           begin
             residue_ctrl_new = CTRL_INIT_STALL;
             residue_ctrl_we  = 1'b1;
@@ -178,36 +377,72 @@ always @*
         begin
           reset_word_index = 1'b1;
           reset_n_counter  = 1'b1;
-          residue_ctrl_new = CTRL_COMPARE;
+          residue_ctrl_new = CTRL_SHL;
           residue_ctrl_we  = 1'b1;
         end
 
-      CTRL_COMPARE:
+      CTRL_SHL:
         begin
+        if (word_index_reg == 8'h0)
+          begin
+            residue_ctrl_new = CTRL_SHL_STALL;
+            residue_ctrl_we  = 1'b1;
+          end
         end
 
-      CTRL_COMPARE_STALL:
+      CTRL_SHL_STALL:
         begin
+          reset_word_index = 1'b1;
+          residue_ctrl_new = CTRL_COMPARE;
+          residue_ctrl_we  = 1'b1;
         end
 
-      CTRL_SUB:
-        begin
-        end
+      CTRL_COMPARE:
+        if (word_index_reg == 8'h0)
+          begin
+            residue_ctrl_new = CTRL_COMPARE_STALL;
+            residue_ctrl_we  = 1'b1;
+          end
 
-      CTRL_SUB_STALL:
+      CTRL_COMPARE_STALL:
         begin
+          reset_word_index = 1'b1;
+          residue_ctrl_we  = 1'b1;
+          if (sub_carry_in_reg == 1'b1)
+            //TODO: Bug! detect CF to detect less than, but no detect ZF to detect equal to.
+            residue_ctrl_new = CTRL_SUB;
+          else
+            residue_ctrl_new = CTRL_LOOP;
         end
 
-      CTRL_SHL:
-        begin
-        end
+      CTRL_SUB:
+        if (word_index_reg == 8'h0)
+          begin
+            residue_ctrl_new = CTRL_SUB_STALL;
+            residue_ctrl_we  = 1'b1;
+          end
 
-      CTRL_SHL_STALL:
+      CTRL_SUB_STALL:
         begin
+          residue_ctrl_new = CTRL_LOOP;
+          residue_ctrl_we  = 1'b1;
         end
 
       CTRL_LOOP:
         begin
+          if (loop_counter_1_to_nn_reg == nn_reg)
+            begin
+              ready_new = 1'b1;
+              ready_we  = 1'b1;
+              residue_ctrl_new = CTRL_IDLE;
+              residue_ctrl_we  = 1'b1;
+            end
+          else
+            begin
+              reset_word_index = 1'b1;
+              residue_ctrl_new = CTRL_SHL;
+              residue_ctrl_we  = 1'b1;
+            end
         end
 
       default:
diff --git a/src/rtl/shl32.v b/src/rtl/shl32.v
new file mode 100644
index 0000000..d0dd1bc
--- /dev/null
+++ b/src/rtl/shl32.v
@@ -0,0 +1,53 @@
+//======================================================================
+//
+// shr32.v
+// ---------
+// 32bit shifter with carry in / carry out.
+//
+//
+// Author: Peter Magnusson
+// Copyright (c) 2015, NORDUnet A/S All rights reserved.
+//
+// Redistribution and use in source and binary forms, with or without
+// modification, are permitted provided that the following conditions are
+// met:
+// - Redistributions of source code must retain the above copyright notice,
+//   this list of conditions and the following disclaimer.
+//
+// - Redistributions in binary form must reproduce the above copyright
+//   notice, this list of conditions and the following disclaimer in the
+//   documentation and/or other materials provided with the distribution.
+//
+// - Neither the name of the NORDUnet nor the names of its contributors may
+//   be used to endorse or promote products derived from this software
+//   without specific prior written permission.
+//
+// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
+// IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
+// TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
+// PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
+// HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
+// TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+// PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
+// LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
+// NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
+// SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+//
+//======================================================================
+
+
+module shl32(
+   input       [31 : 0] a,
+   input                carry_in,
+   output wire [31 : 0] amul2,
+   output wire          carry_out);
+
+   reg [32 : 0] shl_result;
+
+   assign amul2     = shl_result[31:0];
+   assign carry_out = shl_result[32];
+
+   always @(a, carry_in)
+     shl_result = { a, carry_in };
+endmodule