//////////////////////////////////////////////////////////////////////////////// // /// 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). uwire [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; 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 /// // // Categorize incoming character and write to register. // logic [7:0] char_in_1; 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 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. // uwire [3:0] char_bin = char_in[3:0]; uwire [3:0] char_bin_1 = char_in_1[3:0]; // Combine digit at char_in with current value of val_encode. // uwire [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 uwire 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; uwire start_encoding = encoding_2 && overflow_1 && is_digit_1 && is_digit || !is_digit_2 && is_nz_digit_1 && is_digit; uwire end_encoding = encoding_2 && ( overflow_1 || insert_req && !is_digit ); /// SOLUTION -- Problem 2 // Use encoding if unencoded length > 2, rather than length > max_digits. // uwire use_encoding = end_encoding && ( ascii_int_len > 2 ) && ( !val_wait_full || end_draining ); uwire 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. // uwire [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 uwire [max_chars:0] [7:0] val_encode = val_encode_1; uwire [size_lg:1] write_idx = write_idx_1; uwire [size_lg:1] tail = tail_1; uwire [size_lg:1] tail_at_enc_start = tail_at_enc_start_1; uwire 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 uwire clock_reactive, input uwire clock); assign clock_reactive = clock; endprogram module testbench(); localparam int elts_lg = 4; localparam int elts = 1 << elts_lg; localparam int max_chars = 6; uwire [7:0] char_out; uwire 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; uwire 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