////////////////////////////////////////////////////////////////////////////////
//
/// LSU EE 4755 Fall 2015 Homework 6
//
 /// SOLUTION

 /// Assignment  http://www.ece.lsu.edu/koppel/v/2015/hw06.pdf
 /// Solution discussion  http://www.ece.lsu.edu/koppel/v/2015/hw06_sol.pdf

typedef enum
  { Char_escape = 128,
    Char_escape_stop = 200,
    Char_EOS = 255,
    Char_0 = 48,
    Char_9 = 57
    } Chars_Special;


//////////////////////////////////////////////////////////////////////////////
///
/// Homework Solution Is Here.
//
//
//  Solutions to Problems 1 and 2 are in the module below,
//  search for SOLUTION

module icomp_sol
  #( int size_lg = 4,
     int max_chars = 4 )
  ( output [7:0] char_out,
    output can_insert, can_remove,
    input [7:0] char_in,
    input insert_req, remove_req,
    input reset, clk);

   localparam int mc_bits = $clog2(max_chars+1);
   localparam int size = 1 << size_lg;

   // Storage for characters.
   logic [7:0] storage [size];

   // Location at which encoded number should start.  That is,
   // if esc_here[x] is 1, then storage[x] is the first character of
   // an ASCII string that should be replaced with an escape character
   // and a binary encoded value;

   /// SOLUTION -- Problem 2
   //  Increase the size of the "escape here" marker from 1 bit to
   //  mc_bits. Its value now indicates the size of the encoded
   //  integer in bytes.
   logic [mc_bits-1:0] esc_here [size];

   // Registers used for preparing encoded integer.
   logic [max_chars:0][7:0] val_encode_1, val_encode_2;

   // Register for holding encoded integer until all characters removed.
   logic [max_chars-1:0][7:0] val_wait;

   // True if val_wait holds a value that has not yet been read.
   logic val_wait_full;

   // Pointers into storage.
   logic [size_lg:1] head;      // Location being read (sent to module output).
   wire [size_lg:1] write_idx_1;  // Next location to write.
   logic [size_lg:1] tail_1;      // Possible next location to write.
   logic [size_lg:1] tail_at_enc_start_1;

   // Length of ASCII string read so far.
   logic [7:0] ascii_int_len;

   // Note: draining refers to sending the bytes in val_wait to the
   // module outputs.
   logic draining;
   logic [$clog2(max_chars)-1:0] drain_idx;
   wire   start_draining, end_draining;

   wire   empty, full;

   // cadence translate_off
   initial for ( int i=0; i<size; i++ ) storage[i] = 255;
   // cadence translate_on


   ///
   /// Hardware For Encoding ASCII Digits into Binary
   ///

   //
   // Categorize incoming character and write to register.
   //

   logic [7:0] char_in_1;

   wire is_digit =    char_in >= Char_0 && char_in <= Char_9;
   wire is_nz_digit = char_in >  Char_0 && char_in <= Char_9;  // Non-Zero
   logic is_digit_1, is_digit_2, is_nz_digit_1, is_nz_digit_2;

   always_ff @( posedge clk )
     if ( reset ) begin
        is_digit_1 <= 0;
        is_digit_2 <= 0;
        is_nz_digit_1 <= 0;
        is_nz_digit_2 <= 0;
     end else if ( insert_req ) begin
        char_in_1 <= char_in;
        is_digit_1 <= is_digit;
        is_nz_digit_1 <= is_nz_digit;
        is_digit_2 <= is_digit_1;
        is_nz_digit_2 <= is_nz_digit_1;
      end

   // Convert ASCII digit to an integer.
   //
   wire [3:0] char_bin = char_in[3:0];
   wire [3:0] char_bin_1 = char_in_1[3:0];

   // Combine digit at char_in with current value of val_encode.
   //
   wire [max_chars:0] [7:0] val_encode_0 = val_encode_1 * 10 + char_bin;

   /// SOLUTION -- Problem 1
   //
   // Determine the current size of the encoded integer, and set overflow
   // if necessary.
   //
   logic [mc_bits:0] val_encode_size_1;
   always_comb begin
      val_encode_size_1 = 0;
      for ( int i=0; i<max_chars; i++ )
        if ( val_encode_1[i] ) val_encode_size_1 = i + 1;
   end
   wire overflow_1 = val_encode_1[max_chars] != 0;

   always_ff @( posedge clk ) if ( insert_req ) val_encode_2 <= val_encode_1;

   ///
   /// Hardware to Detect the Start, End, and Suitability of a String of Digits
   //

   logic encoding_2;

   wire start_encoding = encoding_2 && overflow_1 && is_digit_1 && is_digit
                       || !is_digit_2 && is_nz_digit_1 && is_digit;
   wire end_encoding = encoding_2 && ( overflow_1 || insert_req && !is_digit );

   /// SOLUTION -- Problem 2
   //  Use encoding if unencoded length > 2, rather than length > max_digits.
   //
   wire use_encoding = end_encoding
        && ( ascii_int_len > 2 )
        && ( !val_wait_full || end_draining );

   wire encoding_1 = start_encoding || encoding_2 && !end_encoding;

   always_ff @( posedge clk )
     if ( reset ) encoding_2 <= 0;
     else if ( insert_req ) encoding_2 <= encoding_1;

   always_ff @( posedge clk )
     if ( reset ) begin

        val_encode_1 <= 0;
        tail_at_enc_start_1 <= 0;

     end else if ( insert_req ) begin

        val_encode_1 <= start_encoding
                        ? char_bin + char_bin_1 * 10
                        : val_encode_0;

        ascii_int_len <= start_encoding ? 2 : ascii_int_len + 1;

        if ( start_encoding ) tail_at_enc_start_1 <= write_idx_1;

        if ( use_encoding )
          val_wait <= overflow_1 ? val_encode_2 : val_encode_1;

   end

   ///
   /// Hardware for Writing Characters into Storage
   ///

   // If the encoded integer is used we need to move the tail back by
   // the number of characters saved. That's easier to compute using
   // the location at which the encoded number started.

   /// SOLUTION -- Problem 2
   //
   //  Tail adjustment computed based on size of encoded integer
   //  rather than max chars.
   //
   wire [size_lg:1] tail_adj =
     tail_at_enc_start_1 + val_encode_size_1 + overflow_1;

   // Location at which to write current character.
   assign write_idx_1 = use_encoding ? tail_adj : tail_1;

   logic  reset_1;
   always_ff @( posedge clk )
     if ( reset ) reset_1 <= 1; else if ( insert_req ) reset_1 <= 0;

   /// Write the Storage and the Tail Pointer
   //
   always_ff @( posedge clk ) if ( reset ) begin

      tail_1 <= 0;

   end else begin

      if ( insert_req && !reset_1 ) begin

         if ( use_encoding ) begin
            esc_here[tail_adj] <= 0;
            storage[tail_adj] <= char_in_1;
         end else begin
            esc_here[tail_1] <= 0;
            storage[tail_1] <= char_in_1;
         end

         tail_1 <= write_idx_1 + 1;

      end

      // If we've decided to use an encoded number remember
      // where. When head reaches tail_at_enc_start we will start
      // sending the encoded number to the output.

      /// SOLUTION -- Problem 2
      //
      //  Write the size of the encoded integer into the esc_here array.
      //  (Previously we just wrote a 1, to indicate that an encoded
      //  integer starts at this position.)
      //
      if ( use_encoding ) esc_here[tail_at_enc_start_1] <= val_encode_size_1;

   end


   ///
   /// Hardware For Removing Characters From Storage
   ///

   /// Character Out Mux
   //
   //  The char_out port can be connected to three things:
   //
   //    - A memory holding stored characters: storage[].
   //    - The escape character (a constant, Char_escape).
   //    - A register holding a number encoded in binary, val_wait.
   //
   /// SOLUTION -- Problem 2
   //
   //  When we reach an encoded integer output the escape character
   //  plus the size of the encoded integer.
   //
   assign char_out =
          start_draining  ?  Char_escape + esc_here[head] :
          draining        ?  val_wait[drain_idx] :
                             storage[head];

   assign start_draining = !empty && esc_here[head];
   assign end_draining = remove_req && draining && drain_idx == 0;

   // Update the register that indicates whether val_wait is holding
   // something.
   always_ff @( posedge clk )

     if ( reset )             val_wait_full <= 0;
     else if ( use_encoding && insert_req ) val_wait_full <= 1;
     else if ( end_draining ) val_wait_full <= 0;

   always_ff @( posedge clk ) if ( reset ) begin

      draining <= 0;
      drain_idx <= 0;
      head <= 0;

   end else if ( remove_req ) begin

      head <= head + 1;

      /// SOLUTION -- Problem 2
      //
      //  Initialize drain_idx with one minus the size of
      //  the encoded integer, rather than max_chars - 1.
      //
      drain_idx <= start_draining  ?  esc_here[head] - 1 :
                   drain_idx > 0   ?  drain_idx - 1 :
                                      0;

      draining <= start_draining  ?  1 :
                  remove_req && drain_idx == 0  ?  0 :
                  draining;

   end


   ///
   /// Hardware to Related to Storage Full and Empty Status
   ///

   assign empty = head == tail_1;
   assign full = tail_1 + 1 == head;

   assign can_remove = !empty && ( !encoding_2 || head != tail_at_enc_start_1 );
   assign can_insert = !full;


   ///
   /// Wires for use by testbench only.
   ///
   // cadence translate_off
   wire [max_chars:0] [7:0] val_encode = val_encode_1;
   wire [size_lg:1] write_idx = write_idx_1;
   wire [size_lg:1]  tail = tail_1;
   wire [size_lg:1]  tail_at_enc_start = tail_at_enc_start_1;
   wire              now_encoding = encoding_1;

   // cadence translate_on

endmodule


//////////////////////////////////////////////////////////////////////////////
/// Testbench
///
 // The testbench can be modified to help with your solution.
 // The TA-bot will run your code using a different testbench.


// cadence translate_off

program reac(output wire clock_reactive, input wire clock);
   assign clock_reactive = clock;
endprogram

module testbench();

   localparam int elts_lg = 4;
   localparam int elts = 1 << elts_lg;
   localparam int max_chars = 6;

   wire [7:0] char_out;
   wire       can_insert, can_remove;
   logic [7:0] char_in;
   logic insert_req, remove_req, reset, clk;
   icomp_sol #(elts_lg,max_chars) b1
     (char_out,can_insert,can_remove,char_in,insert_req,remove_req,reset,clk);

   int cycle_num;

   wire  clk_reactive;

   reac reactivator(clk_reactive, clk);

   initial begin
      clk = 0;
      cycle_num = 0;
      fork
         forever #1 clk = !clk;
         forever @( posedge clk ) cycle_num++;
      join
   end

   string in_str = "One 1 two 12 three 317 four 1029 six 123456 ten 1234567890 twelve 123456789012.  There are 60 seconds in a minute and 31536123 - 123 in a year.";
   string out_str = "";

   initial begin

      automatic string in_str_w_suffix = {in_str, Char_EOS, Char_EOS };
      automatic int insert_finished_cyc = 0;
      automatic int out_size = 0;
      automatic bit tb_insert_done = 0;
      automatic bit tb_remove_done = 0;
      automatic bit trace_this_cycle = 0;
      // Encoded integer is longer than allowed.
      automatic int err_oversize = 0;
      // Number of remaining encoded bytes expected from char_out.
      automatic int bytes_remaining = 0;
      automatic bit enc_start = 0; // If true, char_out is an escape char.
      automatic bit enc_middle = 0;

      /// Reset the module.
      //
      reset = 0;
      insert_req = 0;
      remove_req = 0;
      @( negedge clk ) reset = 1;
      @( negedge clk ) reset = 0;
      @( negedge clk );

      /// Check for one possible error.
      //
      if ( can_insert !== 1 ) begin

         $display("Module did not reset, can_insert: %h\n", can_insert);
         $fatal(1);

      end

      /// Start Main Testing Loops
      //
      fork

         /// Watchdog -- Stop simulation if it's taking too long.
         //
         fork begin

            automatic int cyc_limit = in_str.len() * 100;

            fork
               wait ( cycle_num == cyc_limit );
               wait ( tb_insert_done && tb_remove_done );
            join_any

            if ( cycle_num >= cyc_limit ) begin
               $write("Exceeded cycle limit, exiting.\n");
               $fatal(1);
            end

         end join_none

         /// Trace Execution -- Print Signal Values After Interesting Changes
         //

         while ( !tb_insert_done || !tb_remove_done )
            @( insert_req or remove_req or can_insert or can_remove
               or b1.tail or b1.head or tb_insert_done or tb_remove_done )
              trace_this_cycle = 1;

         while ( !tb_insert_done || !tb_remove_done ) begin

            @( negedge clk_reactive ) if ( !trace_this_cycle ) continue;
            trace_this_cycle = 0;

            /// Trace execution by showing removed character and
            /// related information.
            //
            $write( "In %c  Out %d %3s = %3s   tail %d/%d head %d %s%s%s%s %s%s%s es %d  ail %2d  val_encode %d  val_wait %d\n",
                    insert_req ? char_in : "-",
                    can_remove,
                    remove_req ? $sformatf("%3d",char_out) : "   ",
                    !remove_req ? "   " :
                    enc_start ? $sformatf("E-%1d",char_out-Char_escape) :
                    enc_middle ? $sformatf("x%02h",char_out) :
                    char_out >= 32 && char_out < 128 ? char_out
                    : $sformatf("x%02h",char_out),
                    b1.tail, b1.write_idx,
                    b1.head,
                    b1.start_encoding ? "s" : "_",
                    b1.now_encoding ? "n" : "_",
                    b1.end_encoding ? "e" : "_",
                    b1.use_encoding ? "u" : "_",
                    b1.val_wait_full ? "f" : "_",
                    b1.start_draining ? "s" : "_",
                    b1.end_draining ? "e" : "_",
                    b1.tail_at_enc_start,
                    b1.ascii_int_len,
                    b1.val_encode, b1.val_wait);

         end

         /// Insert Characters
         //
         begin

            automatic int in_pos = 0;

            while ( in_pos < in_str_w_suffix.len() ) begin

               @( negedge clk );

               // Flip a coin, and if it comes up tails send a character
               // in if module is ready for one.
               //
               if ( {$random} & 'h1 && can_insert ) begin

                  char_in = in_str_w_suffix[in_pos++];
                  insert_req = 1;

               end else begin

                  insert_req = 0;

               end

            end

            @( negedge clk );

            insert_req = 0;
            insert_finished_cyc = cycle_num;

            $write("Done feeding inputs.\n");
            tb_insert_done = 1;

         end

         /// Remove Characters
         //
         begin

            bit [max_chars-1:0][7:0] buffer;
            bytes_remaining = 0;

            while ( insert_finished_cyc == 0
                    || cycle_num < insert_finished_cyc + elts * 10 ) begin

               @( negedge clk );

               if ( can_remove
                    && bytes_remaining == 0
                    && char_out == Char_EOS ) break;

               if ( {$random} & 1 && can_remove ) begin

                  remove_req = 1;
                  out_size++;
                  enc_start = 0;
                  enc_middle = bytes_remaining > 0;

                  if ( bytes_remaining > 0 ) begin

                     buffer = ( buffer << 8 ) + char_out;
                     bytes_remaining--;

                     if ( bytes_remaining == 0 ) begin

                        // Convert binary number back to ASCII.
                        out_str = {out_str,$sformatf("%0d",buffer)};

                     end

                  end else if
                    ( char_out >= Char_escape && char_out < Char_escape_stop )
                    begin

                       enc_start = 1;
                       bytes_remaining =
                           char_out == Char_escape
                         ? max_chars
                         : char_out - Char_escape ;
                       buffer = 0;
                       if ( bytes_remaining > max_chars ) err_oversize++;

                    end else begin

                       out_str = {out_str,char_out};

                    end

               end else begin

                  remove_req = 0;

               end

            end

            $write("Done gathering outputs.\n");
            tb_remove_done = 1;

         end

      join

      if ( err_oversize )
        $write("** Error: %d encoded integers too long.\n", err_oversize);

      if ( in_str != out_str )
        $write("** Error: strings don't match.\n");
      else
        $write("Correct output, strings match. %s\n",
                 ( in_str.len() == out_size ) ? "But no compression!" : "");

      $write("In size %d bytes, out size %d bytes.\n",
               in_str.len(), out_size);
      $write("In - \"%s\"\nOut- \"%s\"\n",
               in_str, out_str);

      $finish(2);

   end

endmodule

// cadence translate_on