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