################################################################################ ## ## LSU EE 4720 Fall 2005 Homework 3 -- Solution ## ## # Original Assignment: http://www.ece.lsu.edu/ee4720/2005f/hw3.html .data name: .asciiz "David Koppelman" # Put your name between the quotes. ################################################################################ ## Problem 1 -- Unpack Routine -- Solution # The unpack routine below unpacks every string into "Not yet # implemented", which of course can't be right. Modify the routine so # that it unpacks correctly. Follow the guidelines below next to the # check boxes ([ ]). ## Register Usage # # $a0: Procedure call argument. Address of packed string. # $a1: Procedure call argument. Address of memory for unpacked string. # There are no return values. # [x] Make sure that the code at least runs to completion. # Substantial credit will be deducted for syntax # and run-time errors. # [x] Make sure the code passes the test in the demo routine # and works for other strings too. The unpack routine may be # graded using different strings. # # [x] Registers $t0-$t9 and $a0-$a3 can be used. # [x] Fill as many delay slots as possible. # [x] The only pseudo instructions that can be used are "nop" and "la". # [x] The code should be reasonable efficient, # don't use two instructions where one would do. .text unpack: la $t0, KEEP ULOOP: lhu $t1, 0($a0) # Load set of 3 encoded chars from packed string. andi $t2, $t1, 0x1f # Extract the first encoded character. add $t3, $t0, $t2 # Compute address of decoded character ... lbu $t4, 0($t3) # ...load from KEEP string ... sb $t4, 0($a1) # ...and store in unpacked string. srl $t1, $t1, 5 # Shift second character to lower bits of $t1 andi $t2, $t1, 0x1f # Extract second encoded character. add $t3, $t0, $t2 # Compute address of decoded character ... lbu $t4, 0($t3) # ...load from KEEP string ... sb $t4, 1($a1) # ...and store unpacked string. srl $t1, $t1, 5 # Shift third character to lower bits of $t1 andi $t2, $t1, 0x1f # Extract the third encoded character. add $t3, $t0, $t2 # Compute address of decoded character... lbu $t4, 0($t3) # ...load from KEEP string ... sb $t4, 2($a1) # ...and store in unpacked string. srl $t1, $t1, 5 # Shift end-of-string bit to LSB of $t1. addi $a0, $a0, 2 # Compute address of next set of 3 encoded chars. beq $t1, $0 ULOOP # If end-of-string bit not present, loop. addi $a1, $a1, 3 jr $ra sb $0, 0($a1) # Terminate the unpacked string. ################################################################################ ## Demonstration Routine # This routine calls the pack and unpack routines on a sample # string below (DEMO_STRING), displays the original and unpacked strings # side by side, and verifies whether the unpacked string is correct. .data # Indicate to the assembler that the stuff below is data. # # String to demonstrate pack and unpack routines. # DEMO_STRING: # Address of stuff immediately following. # Place string in memory here, end string with NULL (0). .asciiz ".,!Time flies like an arrow, fruit flies like a banana. azAZ09" .byte 0, 0, 0 # Put three zeros in memory here. # # Memory space for packed and unpacked strings. # .align 4 # Make sure the address below is a multiple of 4. BUFFER_PACK: .space 256 # Allocate 256 characters for use by the pack routine. .align 4 BUFFER_UNPACK: .space 256 # Allocate 256 characters for use by the unpack routine. # # Message printed by the demonstration routine. # MSG: .asciiz "Original:\n\"%/a2/s\"\nUnpacked: \n\"%/a1/s\"\n" MSGSPACES: .asciiz " " MSGERROR: .asciiz "%/s4/s |<---- First error here." MSGCORRECT: .asciiz "Unpack appears correct." # # Message displayed if name omitted. # who_are_you: .asciiz "Please put your name at the top of the file where indicated." .text # Indicate to the assembler that the stuff below is code. .globl __start __start: la $s0, name lb $s0, ($s0) bne $s0, $0, DOTESTS la $a0, who_are_you addi $v0, $0, 11 syscall addi $v0, $0, 10 syscall DOTESTS: # Load address of string and address of memory for packed # string and call the pack routine. # la $a0, DEMO_STRING la $a1, BUFFER_PACK jal pack nop # Load address of packed string and address of memory for unpacked # string and call the unpack routine. # la $a0, BUFFER_PACK la $a1, BUFFER_UNPACK jal unpack nop # Call a system (simulator) routine to display results. # la $a0, MSG la $a1, BUFFER_UNPACK la $a2, DEMO_STRING addi $v0, $0, 11 syscall la $s0, DEMO_STRING la $s1, LUT la $s2, BUFFER_UNPACK DVLOOP: lb $t0, 0($s0) beq $t0, $0 DVDONEOKAY add $t1, $s1, $t0 lb $t1, 0($t1) lb $t2, 0($s2) bne $t1, $0 DCHAR addi $s0, $s0, 1 addi $t0, $0, 46 # '.' DCHAR: beq $t0, $t2, DVLOOP addi $s2, $s2, 1 la $s3, DEMO_STRING sub $s3, $s0, $s3 la $s4, MSGERROR sub $s4, $s4, $s3 la $a0, MSGERROR j DVDONE nop DVDONEOKAY: la $a0, MSGCORRECT DVDONE: addi $v0, $0, 11 syscall addi $v0, $0, 10 syscall nop ################################################################################ ## Pack Routine ## Register Usage # # $a0: Call argument. Address of string to pack. (Original string.) # $a1: Call argument. Address of memory for packed string. # There are no return values. .data .align 4 LUT: .space 256 KEEP: .asciiz ".,!?;abcdefghijklmnopqrstuvwxyz " .byte 0, 0, 0, 0 .text pack: # ## Packed Data Format # # Groups of three characters from the original string are packed # into two characters in the packed string arranged as follows: # # # Start with three characters from original string: # _________________ _________________ _________________ # | char0 | | char1 | | char2 | # ^^^^^^^^^^^^^^^^^ ^^^^^^^^^^^^^^^^^ ^^^^^^^^^^^^^^^^^ # 7 6 5 4 3 2 1 0 7 6 5 4 3 2 1 0 7 6 5 4 3 2 1 0 # # # Convert 8-bit characters to 5-bit encodings: # # char0 -> enc0 E.g., 'b' -> 6 # char1 -> enc1 E.g., ',' -> 1 # char2 -> enc2 E.g., '#' -> 0 (# cannot be represented) # # # Arrange the encodings into a 16-bit quantity with a # termination bit (t, position 15) as shown. The termination # is 1 for the last group of three characters. Note that the # exact length of the original string is not remembered. # # ___________________________________ # | t | enc2 | enc1 | enc0 | # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ # 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 # 5 4 3 2 1 0 9 8 7 6 5 4 3 2 1 0 # ## Encoding # # Each character in the original string is encoded as a 5-bit # quantity, allowing for 32 different characters. The string # KEEP specifies a character's encoding by its position. For # example, 'a' is at position 5, so it is encoded in the # packed string as a 5. If a character is not in KEEP it # is encoded as a 0 (a period). # ## Prepare Lookup Table (LUT) # # To speed the encoding of large strings a lookup table (LUT) # is prepared based on the KEEP string. The i'th element of # LUT gives the encoding for character i. For example, element # 96 ('a') of LUT is a 5, meaning in the packed string an 'a' # appears as a 5. # Set lookup table to zeros. # la $t0, LUT addi $t2, $t0, 252 PLOOP1: sw $0, 0($t0) bne $t0, $t2, PLOOP1 addi $t0, $t0, 4 # Write entries of lookup table based on KEEP string. # la $t0, LUT la $t1, KEEP addi $t3, $0, 0 # Initialize encoding to zero. PLOOP2: lbu $t2, 0($t1) # Load character of KEEP string. add $t4, $t0, $t2 # Find corresponding position in LUT. sb $t3, 0($t4) # Write its encoding into LUT. addi $t1, $t1, 1 # Increment KEEP string address. bne $t2, $0 PLOOP2 addi $t3, $t3, 1 # Increment encoding, for next character. # Initialize first element of LUT (for the NULL character). # addi $t3, $0, -1 sb $t3, 0($t0) # ## Pack String # # Each iteration of the loop packs three characters. PLOOP: lbu $t4, 0($a0) # Load char from original string. add $t1, $t0, $t4 # Compute LUT address. lb $t2, 0($t1) # Load character's encoding. add $t5, $t2, $0 # Keep copy of encoding to check for end of string. lbu $t4, 1($a0) # Load next character from original string. add $t1, $t0, $t4 # Compute LUT address. lb $t3, 0($t1) # Load character's encoding. or $t5, $t5, $t3 # OR in encoding to remember if at end of string. sll $t3, $t3, 5 # Shift second encoding over... or $t2, $t2, $t3 # ...and OR into packed value. (Two chars so far.) lbu $t4, 2($a0) # Load next character from original string. add $t1, $t0, $t4 # Compute LUT address. lb $t3, 0($t1) # Load character's encoding. or $t5, $t5, $t3 # OR in encoding to remember if at end of string. sll $t3, $t3, 10 # Shift third encoding over... or $t2, $t2, $t3 # and OR into packed value. All three chars packed. sh $t2, 0($a1) # Store packed characters... addi $a1, $a1, 2 # ...and increment address. bgez $t5 PLOOP # If none of the 3 chars NULL continue with loop. addi $a0, $a0, 3 # Move to next group of three characters. # ## Terminate String and Return # ori $t2, $t2, 0x8000 # Add termination bit to last packed value. jr $ra sh $t2, -2($a1) # Re-write last packed value with termination.