path: root/src/rtl/residue.v

//======================================================================
//
// residue.v
// ---------
// Modulus 2**2N residue calculator for montgomery calculations.
//
// 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
//
//
//
// 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 residue(
  input wire clk,
  input wire reset_n,

  input wire  calculate,
  output wire ready,

  input wire  [14 : 0] nn, //MAX(2*N)=8192*2 (14 bit)
  input wire  [07 : 0] length,

  output wire [07 : 0] opa_rd_addr,
  input wire  [31 : 0] opa_rd_data,
  output wire [07 : 0] opa_wr_addr,
  output wire [31 : 0] opa_wr_data,
  output wire          opa_wr_we,

  output wire [07 : 0] opm_addr,
  input wire  [31 : 0] opm_data

);

//----------------------------------------------------------------
// Internal constant and parameter definitions.
//----------------------------------------------------------------


// 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; // Nr = 00...01 ; Nr = 1 == 2**(2N-2N)
localparam CTRL_INIT_STALL    = 4'h2;
localparam CTRL_SHL           = 4'h3; // Nr = Nr shift left 1
localparam CTRL_SHL_STALL     = 4'h4;
localparam CTRL_COMPARE       = 4'h5; //if (Nr less than M) continue;
localparam CTRL_COMPARE_STALL = 4'h6;
localparam CTRL_SUB           = 4'h7; //Nr = Nr - M
localparam CTRL_SUB_STALL     = 4'h8;
localparam CTRL_LOOP          = 4'h9; //for (int i = 0; i < 2 * N; i++)

//----------------------------------------------------------------
// Registers including update variables and write enable.
//----------------------------------------------------------------

reg [07 : 0] opa_rd_addr_reg;
reg [07 : 0] opa_wr_addr_reg;
reg [31 : 0] opa_wr_data_reg;
reg          opa_wr_we_reg;
reg [07 : 0] opm_addr_reg;
reg          ready_reg;
reg          ready_new;
reg          ready_we;
reg [03 : 0] residue_ctrl_reg;
reg [03 : 0] residue_ctrl_new;
reg          residue_ctrl_we;
reg          reset_word_index;
reg          reset_n_counter;
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.
//----------------------------------------------------------------
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)
  );



  //----------------------------------------------------------------
  // reg_update
  //----------------------------------------------------------------
  always @ (posedge clk or negedge reset_n)
    begin
      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

//----------------------------------------------------------------
// residue_ctrl
//
// Control FSM for residue
//----------------------------------------------------------------
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)
          begin
            ready_new = 1'b0;
            ready_we  = 1'b1;
            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_reg == 8'h0)
          begin
            residue_ctrl_new = CTRL_INIT_STALL;
            residue_ctrl_we  = 1'b1;
          end

      CTRL_INIT_STALL:
        begin
          reset_word_index = 1'b1;
          reset_n_counter  = 1'b1;
          residue_ctrl_new = CTRL_SHL;
          residue_ctrl_we  = 1'b1;
        end

      CTRL_SHL:
        begin
        if (word_index_reg == 8'h0)
          begin
            residue_ctrl_new = CTRL_SHL_STALL;
            residue_ctrl_we  = 1'b1;
          end
        end

      CTRL_SHL_STALL:
        begin
          reset_word_index = 1'b1;
          residue_ctrl_new = CTRL_COMPARE;
          residue_ctrl_we  = 1'b1;
        end

      CTRL_COMPARE:
        if (word_index_reg == 8'h0)
          begin
            residue_ctrl_new = CTRL_COMPARE_STALL;
            residue_ctrl_we  = 1'b1;
          end

      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_SUB:
        if (word_index_reg == 8'h0)
          begin
            residue_ctrl_new = CTRL_SUB_STALL;
            residue_ctrl_we  = 1'b1;
          end

      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:
        begin
        end

    endcase
  end

endmodule // residue

//======================================================================
// EOF residue.v
//======================================================================