////////////////////////////////////////////////////////////////////////////////
//
/// LSU EE 4755 Fall 2014 Homework 4
//

 /// SOLUTION

 // Assignment  http://www.ece.lsu.edu/koppel/v/2014f/hw04.pdf

 /// The solution is in module asc_to_bin_sol.


typedef enum { Char_escape = 1, Char_0 = 48, Char_9 = 57 } Chars_Special;

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

   logic [7:0] storage [size];

   logic [size_lg:1] head, tail;

   uwire   is_digit = char_in >= Char_0 && char_in <= Char_9;

   uwire   empty = head == tail;
   uwire   full = tail + 1 == head;

   assign can_insert = !full;
   assign can_remove = !empty;

   assign char_out = storage[head];

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

   always @( posedge clk ) if ( reset ) begin

      tail <= 0;

   end else begin

      if ( insert_req ) begin

         storage[tail] = char_in;
         tail <= tail + 1;

      end

   end

   always @( posedge clk ) if ( reset ) begin

      head <= 0;

   end else if ( remove_req ) begin

      head <= head + 1;

   end

endmodule


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

   // 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;
   logic esc_here [size];

   // Register used for preparing encoded integer.
   logic [max_chars-1:0][7:0] val_encode;
   // 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).
   uwire [size_lg:1] write_idx;  // Next location to write.
   logic [size_lg:1] tail;      // Possible next location to write.
   logic [size_lg:1] tail_at_enc_start;

   // Note: encoding refers to the process of converting a string of
   // ASCII characters to an integer.
   uwire now_encoding, end_encoding;
   logic was_encoding;

   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;
   uwire   start_draining, end_draining;

   uwire   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
   ///

   // Check whether a digit is present.
   //
   uwire is_digit = char_in >= Char_0 && char_in <= Char_9;
   uwire is_nz_digit = char_in > Char_0 && char_in <= Char_9;  // Non-Zero

   // Convert ASCII digit to an integer.
   //
   uwire [3:0] char_bin = char_in - Char_0;

   // Combine digit at char_in with current value of val_encode.
   //
   uwire [max_chars:0] [7:0] next_val_encode = val_encode * 10 + char_bin;
   uwire overflow = next_val_encode[max_chars] != 0;

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

   logic was_digit;
   always @( posedge clk )
     if ( reset )           was_digit <= 0;
     else if ( insert_req ) was_digit <= is_digit;

   // True if we should start encoding a string of digits.
   uwire start_encoding =
        insert_req && is_nz_digit && ( !was_digit || overflow );

   assign now_encoding = start_encoding || was_encoding && !end_encoding;
   always @( posedge clk )
     if ( reset )           was_encoding <= 0;
     else if ( insert_req ) was_encoding <= now_encoding;

   // True if encoding should end, whether or not the encoding will be used.
   assign end_encoding =
          insert_req && was_encoding && ( !is_digit || overflow );

   // True if encoded integer should be used.
   // We don't want to do this if the ASCII string is too short,
   // or if val_wait is still occupied.
   uwire use_encoding = end_encoding
        && ( ascii_int_len > max_chars )
        && ( !val_wait_full || end_draining );


   // Update registers holding encoded integer, and those keeping
   // track of locations.
   //
   always @( posedge clk ) if ( insert_req ) begin

      if ( start_encoding ) begin

         // Initialize val_encode with first character.
         val_encode <= char_bin;

         // Remember where ASCII digits started.
         tail_at_enc_start <= write_idx;

         // Keep track of how many digits there are.
         ascii_int_len <= 1;

      end else begin

         // Update registers assuming that we are continuing to
         // encode. (It doesn't hurt if we are not currently encoding.)
         val_encode <= next_val_encode;
         ascii_int_len <= ascii_int_len + 1;

      end

      // Move val_encode to a second register so that the next string of
      // ASCII digits can be encoded without having to wait for this
      // value to be removed.
      if ( use_encoding ) val_wait <= val_encode;

   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.
   uwire [size_lg:1] tail_adj = tail_at_enc_start + max_chars + 1;

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


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

      tail <= 0;

   end else if ( insert_req ) begin

      // 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.
      if ( use_encoding ) esc_here[tail_at_enc_start] <= 1;

      storage[write_idx] <= char_in;
      esc_here[write_idx] <= 0;

      tail <= write_idx + 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.
   //
   assign char_out =
          start_draining ? Char_escape :
          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 @( posedge clk )
     if ( reset )             val_wait_full <= 0;
     else if ( use_encoding ) val_wait_full <= 1;
     else if ( end_draining ) val_wait_full <= 0;

   always @( posedge clk ) if ( reset ) begin

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

   end else if ( remove_req ) begin

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

      drain_idx <= start_draining ? max_chars-1
                   : drain_idx > 0 ? drain_idx - 1 : 0;

      head <= head + 1;

   end


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

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

   assign can_remove = !empty && ( !now_encoding || head != tail_at_enc_start );
   assign can_insert = !full;

endmodule




// cadence translate_off
module testbench();

   localparam int elts_lg = 4;
   localparam int elts = 1 << elts_lg;
   localparam int int_chars = 2;

   uwire [7:0] char_out;
   uwire       can_insert, can_remove;
   logic [7:0] char_in;
   logic insert_req, remove_req, reset, clk;
   asc_to_bin_sol #(elts_lg,int_chars) b1
     (char_out,can_insert,can_remove,char_in,insert_req,remove_req,reset,clk);

   int cycle_num;

   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.  There are 60 seconds in a minute and 31536000 in a year.";
   string out_str = "";

   initial begin

      automatic int insert_finished_cyc = 0;
      automatic int out_size = 0;
      automatic bit tb_insert_done = 0;
      automatic bit tb_remove_done = 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
               $display("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 ) begin

            @( 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 );
            @( negedge clk );

            /// Trace execution by showing removed character and
            /// related information.
            //
            $display( "c In %c  Out %d = %c   tail %d head %d  b2 %d",
                      char_in, char_out, char_out, b1.tail, b1.head, b1.val_wait);

         end

         /// Insert Characters
         //
         begin

            automatic int in_pos = 0;

            while ( in_pos < in_str.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[in_pos++];
                  insert_req = 1;

               end else begin

                  insert_req = 0;

               end

            end

            @( negedge clk );

            insert_req = 0;
            insert_finished_cyc = cycle_num;

            $display("Done feeding inputs.");
            tb_insert_done = 1;

         end

         /// Remove Characters
         //
         begin

            int buffer;
            automatic int bytes_remaining = 0;

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

               @( negedge clk );

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

                  remove_req = 1;
                  out_size++;

                  if ( bytes_remaining > 0 ) begin

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

                     if ( bytes_remaining == 0 ) begin

                        // Convert binary number back to ASCII.
                        string iasc;
                        iasc.itoa(buffer);
                        out_str = {out_str,iasc};

                     end

                  end else if ( char_out == Char_escape ) begin

                     bytes_remaining = int_chars;
                     buffer = 0;

                  end else begin

                     out_str = {out_str,char_out};

                  end

               end else begin

                  remove_req = 0;

               end

            end

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

         end

      join

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

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

      $finish(2);

   end

endmodule

// cadence translate_on