################################################################################ ## ## LSU EE 4720 Fall 2018 Homework 1 -- SOLUTION ## ## # Assignment http://www.ece.lsu.edu/ee4720/2018/hw01.pdf ################################################################################ ## Problem 1 -- unsqw Routine .text unsqw: ## Register Usage # # CALL VALUES: # $a0: Address of start of compressed string. # $a1: Address of area to decompress into. # # RETURN: # [✔] Write memory starting at a1 with decompressed string. # # Note: # Can modify $t0-$t9, $a0-$a3 # [✔] Code should be correct. # [✔] Code should be reasonably efficient. # [✔] Do not use pseudoinstructions except for nop and la. ## Both Methods # # A reference starts with a character of value 0x80 or higher. # This byte is called the reference marker. # ## Simple Method: # 0x80 B1 B2 : # = 1000_0000 B1 B2 : # 0x80 is the reference marker. # B1 is length, # B2 is distance. # ## Better Method: # 1000_0000 B1 B2: # 0x80 = 1000_0000 is the reference marker. # B1 is length, # B2 is distance. # 10LL_LLLL B1: # 10LL_LLLL is the reference marker. # LL_LLLL (low 6 bits) are length, # B1 is distance. # 1100_0000 B1 B2 B3: # 0xc0 = 1100_0000 is the reference marker. # B1 holds length. # B2 holds bits 15:8 of distance and # B3 holds bits 7:0 of distance. # 11LL_LLLL B1 B2: # 11LL_LLLL is the reference marker. # LL_LLLL (low 6 bits) are length, # B1 holds bits 15:8 of distance and # B2 holds bits 7:0 of distance. ## SOLUTION j LOOP nop LITERAL_CHAR: sb $t0, 0($a1) # Write literal character to output buffer. beq $t0, $0, DONE # If 0, we're at the end of the string. addi $a1, $a1, 1 LOOP: lb $t0, 0($a0) # Load next character of compressed text. bgez $t0, LITERAL_CHAR # If it's non-negative, it's an ordinary char. addi $a0, $a0, 1 # Either way, increment address. REFERENCE: ## Reference Marker Found # # At this point in the code: # Reference Marker is in $t0. andi $t3, $t0, 0x3f # Extract length from marker. (Bits 6-0.) bne $t3, $0, SKIP_LB # If this length is non-zero, get distance. lbu $t4, 0($a0) # Load next byte. Could be length or dist. ## Case 1 and 3 -- Length is in byte immediately following marker. # # At this point in code: # Reference marker is in $t0 # Length is in register $t4. addi $t3, $t4, 0 # Move distance into register t3. lbu $t4, 1($a0) # Load next byte, the first distance byte. addi $a0, $a0, 1 SKIP_LB: ## Check whether distance is in one or two bytes (case 3 & 4). # At this point in code: # Reference marker is in $t0. # Length is in register $t3. # First distance byte is in register $t4. andi $t1, $t0, 0x40 # Check whether distance is stored in two bytes. beq $t1, $0, SKIP_2B_DISTANCE # If taken, $t4 is the distance. nop ## Cases 3 and 4 -- Length is stored in two bytes. # # At this point in code: # Reference marker is in $t0. # Length is in register $t3. # Most (more) significant distance byte is in register $t4. # lbu $t5, 1($a0) # Load second distance byte. sll $t4, $t4, 8 # Combine two distance bytes by shifting LSB ... or $t4, $t4, $t5 # ... and oring them together. addi $a0, $a0, 1 SKIP_2B_DISTANCE: ## All Cases # # Copy the prior occurrence of text from some part of the # output buffer to the end of the output buffer. # At this point in code: # Reference marker is in $t0. # Length is in register $t3. # Distance is in register $t4. # sub $t4, $a1, $t4 # Compute starting address of prior occurrence. add $t5, $t4, $t3 # Compute ending address of prior occurrence. addi $a0, $a0, 1 COPY_LOOP: lbu $t0, 0($t4) # Load character of prior occurrence .. sb $t0, 0($a1) # .. and write it to the end of the output buffer. addi $t4, $t4, 1 bne $t4, $t5, COPY_LOOP addi $a1, $a1, 1 j LOOP nop DONE: jr $ra nop ################################################################################ ## Testbench Routine # # .data uncomp: # Uncompressed data. .ascii "[Note: it has been cold cold cold cold!]" # Idx: 0 - 39 .ascii "\n=======================================" # Idx: 40 - 79 .ascii "===============================\nAnother " # Idx: 80 - 119 .ascii "frigid Arctic airmass is already pushing" # Idx: 120 - 159 .ascii " into the region\nand will provide bitter" # Idx: 160 - 199 .ascii "ly cold temperatures. Temperatures will\n" # Idx: 200 - 239 .ascii "plunge into the teens and 20s tonight an" # Idx: 240 - 279 .ascii "d could be quite similar\nWednesday night" # Idx: 280 - 319 .ascii ".\n======================================" # Idx: 320 - 359 .ascii "================================\n* TEMPE" # Idx: 360 - 399 .ascii "RATURE...Lows will fall into the mid tee" # Idx: 400 - 439 .ascii "ns to lower 20s\nalong and north of the I" # Idx: 440 - 479 .ascii "-10/12 corridor. South of I-10 lows\nwill" # Idx: 480 - 519 .ascii " range from 20 to 25. These temperatures" # Idx: 520 - 559 .ascii " will be similar\nWednesday night.\n\n* DUR" # Idx: 560 - 599 .ascii "ATION...Freezing conditions will likely " # Idx: 600 - 639 .ascii "last for 12 to 26\nhours over much of the" # Idx: 640 - 679 .ascii " warned area tonight and then 12 to 18\nh" # Idx: 680 - 719 .asciiz "ours Wednesday night." # Idx: 720 - 740 comp_simple: # Compressed data Simple Method. .ascii "[Note: it has been cold" # Idx: 0 - 22 # Idx: 18 = 23 - 5 = 0x17 - 0x5. Len: 15 = 0xf. .byte 0x80 15 5 # " cold cold cold" .ascii "!]\n=" # Idx: 38 - 41 # Idx: 41 = 42 - 1 = 0x2a - 0x1. Len: 69 = 0x45. .byte 0x80 69 1 # "=====================================================================" .ascii "\nAnother frigid Arctic airmass is alread" # Idx: 111 - 150 .ascii "y pushing into the region\nand will provi" # Idx: 151 - 190 .ascii "de bitterly" # Idx: 191 - 201 # Idx: 28 = 202 - 174 = 0xca - 0xae. Len: 6 = 0x6. .byte 0x80 6 174 # " cold " .ascii "temperatures. T" # Idx: 208 - 222 # Idx: 209 = 223 - 14 = 0xdf - 0xe. Len: 11 = 0xb. .byte 0x80 11 14 # "emperatures" # Idx: 180 = 234 - 54 = 0xea - 0x36. Len: 5 = 0x5. .byte 0x80 5 54 # " will" .ascii "\nplunge" # Idx: 239 - 245 # Idx: 160 = 246 - 86 = 0xf6 - 0x56. Len: 10 = 0xa. .byte 0x80 10 86 # " into the " .ascii "teens " # Idx: 256 - 261 # Idx: 177 = 262 - 85 = 0x106 - 0x55. Len: 4 = 0x4. .byte 0x80 4 85 # "and " .ascii "20s tonight" # Idx: 266 - 276 # Idx: 261 = 277 - 16 = 0x115 - 0x10. Len: 5 = 0x5. .byte 0x80 5 16 # " and " .ascii "could be quite similar\nWednesday " # Idx: 282 - 314 # Idx: 272 = 315 - 43 = 0x13b - 0x2b. Len: 5 = 0x5. .byte 0x80 5 43 # "night" .ascii ".\n" # Idx: 320 - 321 # Idx: 67 = 322 - 255 = 0x142 - 0xff. Len: 44 = 0x2c. .byte 0x80 44 255 # "============================================" # Idx: 365 = 366 - 1 = 0x16e - 0x1. Len: 26 = 0x1a. .byte 0x80 26 1 # "==========================" .ascii "\n* TEMPERATURE...Low" # Idx: 392 - 411 # Idx: 233 = 412 - 179 = 0x19c - 0xb3. Len: 6 = 0x6. .byte 0x80 6 179 # "s will" .ascii " fall" # Idx: 418 - 422 # Idx: 246 = 423 - 177 = 0x1a7 - 0xb1. Len: 10 = 0xa. .byte 0x80 10 177 # " into the " .ascii "mi" # Idx: 433 - 434 # Idx: 206 = 435 - 229 = 0x1b3 - 0xe5. Len: 4 = 0x4. .byte 0x80 4 229 # "d te" # Idx: 258 = 439 - 181 = 0x1b7 - 0xb5. Len: 4 = 0x4. .byte 0x80 4 181 # "ens " .ascii "to lower" # Idx: 443 - 450 # Idx: 265 = 451 - 186 = 0x1c3 - 0xba. Len: 4 = 0x4. .byte 0x80 4 186 # " 20s" .ascii "\nalong" # Idx: 455 - 460 # Idx: 277 = 461 - 184 = 0x1cd - 0xb8. Len: 5 = 0x5. .byte 0x80 5 184 # " and " .ascii "north of" # Idx: 466 - 473 # Idx: 428 = 474 - 46 = 0x1da - 0x2e. Len: 5 = 0x5. .byte 0x80 5 46 # " the " .ascii "I-10/12 corridor. Sou" # Idx: 479 - 499 # Idx: 469 = 500 - 31 = 0x1f4 - 0x1f. Len: 6 = 0x6. .byte 0x80 6 31 # "th of " # Idx: 479 = 506 - 27 = 0x1fa - 0x1b. Len: 4 = 0x4. .byte 0x80 4 27 # "I-10" # Idx: 445 = 510 - 65 = 0x1fe - 0x41. Len: 4 = 0x4. .byte 0x80 4 65 # " low" .ascii "s\n" # Idx: 514 - 515 # Idx: 414 = 516 - 102 = 0x204 - 0x66. Len: 5 = 0x5. .byte 0x80 5 102 # "will " .ascii "range from 20" # Idx: 521 - 533 # Idx: 442 = 534 - 92 = 0x216 - 0x5c. Len: 4 = 0x4. .byte 0x80 4 92 # " to " .ascii "25. These temperature" # Idx: 538 - 558 # Idx: 412 = 559 - 147 = 0x22f - 0x93. Len: 7 = 0x7. .byte 0x80 7 147 # "s will " .ascii "be similar\nWednesday night.\n\n* DURATION." # Idx: 566 - 605 .ascii "..Freezing condition" # Idx: 606 - 625 # Idx: 559 = 626 - 67 = 0x272 - 0x43. Len: 7 = 0x7. .byte 0x80 7 67 # "s will " .ascii "likely last for 12" # Idx: 633 - 650 # Idx: 534 = 651 - 117 = 0x28b - 0x75. Len: 5 = 0x5. .byte 0x80 5 117 # " to 2" .ascii "6\nhours over muc" # Idx: 656 - 671 # Idx: 470 = 672 - 202 = 0x2a0 - 0xca. Len: 9 = 0x9. .byte 0x80 9 202 # "h of the " .ascii "warned area to" # Idx: 681 - 694 # Idx: 587 = 695 - 108 = 0x2b7 - 0x6c. Len: 5 = 0x5. .byte 0x80 5 108 # "night" # Idx: 461 = 700 - 239 = 0x2bc - 0xef. Len: 5 = 0x5. .byte 0x80 5 239 # " and " .ascii "then" # Idx: 705 - 708 # Idx: 648 = 709 - 61 = 0x2c5 - 0x3d. Len: 7 = 0x7. .byte 0x80 7 61 # " 12 to " .ascii "18" # Idx: 716 - 717 # Idx: 657 = 718 - 61 = 0x2ce - 0x3d. Len: 7 = 0x7. .byte 0x80 7 61 # "\nhours " # Idx: 577 = 725 - 148 = 0x2d5 - 0x94. Len: 16 = 0x10. .byte 0x80 16 148 # "Wednesday night." .byte 0 # Original: 741 B, Simple Compressed: 508 B, Ratio: 0.686 comp_better: # Compressed data Better Method. .ascii "[Note: it has been cold" # Idx: 0 - 22 # Idx: 18 = 23 - 5 = 0x17 - 0x5. Len: 15 = 0xf. .byte 0x8f 0x05 # " cold cold cold" .ascii "!]\n=" # Idx: 38 - 41 # Idx: 41 = 42 - 1 = 0x2a - 0x1. Len: 69 = 0x45. .byte 0x80 0x45 0x01 # "=====================================================================" .ascii "\nAnother frigid Arctic airmass is alread" # Idx: 111 - 150 .ascii "y pushing into " # Idx: 151 - 165 # Idx: 115 = 166 - 51 = 0xa6 - 0x33. Len: 3 = 0x3. .byte 0x83 0x33 # "the" .ascii " region\nand will provide bitterly" # Idx: 169 - 201 # Idx: 28 = 202 - 174 = 0xca - 0xae. Len: 6 = 0x6. .byte 0x86 0xae # " cold " .ascii "temperatures. T" # Idx: 208 - 222 # Idx: 209 = 223 - 14 = 0xdf - 0xe. Len: 11 = 0xb. .byte 0x8b 0x0e # "emperatures" # Idx: 180 = 234 - 54 = 0xea - 0x36. Len: 5 = 0x5. .byte 0x85 0x36 # " will" .ascii "\nplunge" # Idx: 239 - 245 # Idx: 160 = 246 - 86 = 0xf6 - 0x56. Len: 10 = 0xa. .byte 0x8a 0x56 # " into the " .ascii "t" # Idx: 256 - 256 # Idx: 15 = 257 - 242 = 0x101 - 0xf2. Len: 3 = 0x3. .byte 0x83 0xf2 # "een" # Idx: 143 = 260 - 117 = 0x104 - 0x75. Len: 3 = 0x3. .byte 0x83 0x75 # "s a" # Idx: 178 = 263 - 85 = 0x107 - 0x55. Len: 3 = 0x3. .byte 0x83 0x55 # "nd " .ascii "20s tonight" # Idx: 266 - 276 # Idx: 261 = 277 - 16 = 0x115 - 0x10. Len: 5 = 0x5. .byte 0x85 0x10 # " and " .ascii "cou" # Idx: 282 - 284 # Idx: 205 = 285 - 80 = 0x11d - 0x50. Len: 3 = 0x3. .byte 0x83 0x50 # "ld " .ascii "be quite similar\nWednesday " # Idx: 288 - 314 # Idx: 272 = 315 - 43 = 0x13b - 0x2b. Len: 5 = 0x5. .byte 0x85 0x2b # "night" .ascii "." # Idx: 320 - 320 # Idx: 40 = 321 - 281 = 0x141 - 0x119. Len: 72 = 0x48. .byte 0xc0 0x48 0x01 0x19 # "\n======================================================================\n" .ascii "* TEMPERATURE...Low" # Idx: 393 - 411 # Idx: 233 = 412 - 179 = 0x19c - 0xb3. Len: 6 = 0x6. .byte 0x86 0xb3 # "s will" .ascii " fa" # Idx: 418 - 420 # Idx: 416 = 421 - 5 = 0x1a5 - 0x5. Len: 3 = 0x3. .byte 0x83 0x05 # "ll " # Idx: 247 = 424 - 177 = 0x1a8 - 0xb1. Len: 9 = 0x9. .byte 0x89 0xb1 # "into the " .ascii "mi" # Idx: 433 - 434 # Idx: 206 = 435 - 229 = 0x1b3 - 0xe5. Len: 4 = 0x4. .byte 0x84 0xe5 # "d te" # Idx: 258 = 439 - 181 = 0x1b7 - 0xb5. Len: 4 = 0x4. .byte 0x84 0xb5 # "ens " # Idx: 426 = 443 - 17 = 0x1bb - 0x11. Len: 3 = 0x3. .byte 0x83 0x11 # "to " .ascii "lower" # Idx: 446 - 450 # Idx: 265 = 451 - 186 = 0x1c3 - 0xba. Len: 4 = 0x4. .byte 0x84 0xba # " 20s" .ascii "\nalong" # Idx: 455 - 460 # Idx: 277 = 461 - 184 = 0x1cd - 0xb8. Len: 5 = 0x5. .byte 0x85 0xb8 # " and " .ascii "north of" # Idx: 466 - 473 # Idx: 428 = 474 - 46 = 0x1da - 0x2e. Len: 5 = 0x5. .byte 0x85 0x2e # " the " .ascii "I-10/12" # Idx: 479 - 485 # Idx: 281 = 486 - 205 = 0x1e6 - 0xcd. Len: 3 = 0x3. .byte 0x83 0xcd # " co" .ascii "rridor. Sou" # Idx: 489 - 499 # Idx: 469 = 500 - 31 = 0x1f4 - 0x1f. Len: 6 = 0x6. .byte 0x86 0x1f # "th of " # Idx: 479 = 506 - 27 = 0x1fa - 0x1b. Len: 4 = 0x4. .byte 0x84 0x1b # "I-10" # Idx: 445 = 510 - 65 = 0x1fe - 0x41. Len: 4 = 0x4. .byte 0x84 0x41 # " low" .ascii "s\n" # Idx: 514 - 515 # Idx: 414 = 516 - 102 = 0x204 - 0x66. Len: 5 = 0x5. .byte 0x85 0x66 # "will " .ascii "ra" # Idx: 521 - 522 # Idx: 243 = 523 - 280 = 0x20b - 0x118. Len: 4 = 0x4. .byte 0xc4 0x01 0x18 # "nge " .ascii "from" # Idx: 527 - 530 # Idx: 451 = 531 - 80 = 0x213 - 0x50. Len: 3 = 0x3. .byte 0x83 0x50 # " 20" # Idx: 442 = 534 - 92 = 0x216 - 0x5c. Len: 4 = 0x4. .byte 0x84 0x5c # " to " .ascii "25. Thes" # Idx: 538 - 545 # Idx: 254 = 546 - 292 = 0x222 - 0x124. Len: 4 = 0x4. .byte 0xc4 0x01 0x24 # "e te" # Idx: 224 = 550 - 326 = 0x226 - 0x146. Len: 15 = 0xf. .byte 0xcf 0x01 0x46 # "mperatures will" # Idx: 287 = 565 - 278 = 0x235 - 0x116. Len: 4 = 0x4. .byte 0xc4 0x01 0x16 # " be " # Idx: 297 = 569 - 272 = 0x239 - 0x110. Len: 25 = 0x19. .byte 0xd9 0x01 0x10 # "similar\nWednesday night.\n" # Idx: 392 = 594 - 202 = 0x252 - 0xca. Len: 3 = 0x3. .byte 0x83 0xca # "\n* " .ascii "DU" # Idx: 597 - 598 # Idx: 400 = 599 - 199 = 0x257 - 0xc7. Len: 3 = 0x3. .byte 0x83 0xc7 # "RAT" .ascii "ION" # Idx: 602 - 604 # Idx: 406 = 605 - 199 = 0x25d - 0xc7. Len: 3 = 0x3. .byte 0x83 0xc7 # "..." .ascii "Freez" # Idx: 608 - 612 # Idx: 157 = 613 - 456 = 0x265 - 0x1c8. Len: 4 = 0x4. .byte 0xc4 0x01 0xc8 # "ing " .ascii "conditio" # Idx: 617 - 624 # Idx: 440 = 625 - 185 = 0x271 - 0xb9. Len: 3 = 0x3. .byte 0x83 0xb9 # "ns " # Idx: 561 = 628 - 67 = 0x274 - 0x43. Len: 5 = 0x5. .byte 0x85 0x43 # "will " .ascii "likely last for " # Idx: 633 - 648 # Idx: 484 = 649 - 165 = 0x289 - 0xa5. Len: 3 = 0x3. .byte 0x83 0xa5 # "12 " # Idx: 535 = 652 - 117 = 0x28c - 0x75. Len: 4 = 0x4. .byte 0x84 0x75 # "to 2" .ascii "6\nhours ov" # Idx: 656 - 665 # Idx: 449 = 666 - 217 = 0x29a - 0xd9. Len: 3 = 0x3. .byte 0x83 0xd9 # "er " .ascii "muc" # Idx: 669 - 671 # Idx: 470 = 672 - 202 = 0x2a0 - 0xca. Len: 9 = 0x9. .byte 0x89 0xca # "h of the " .ascii "warned area" # Idx: 681 - 691 # Idx: 269 = 692 - 423 = 0x2b4 - 0x1a7. Len: 13 = 0xd. .byte 0xcd 0x01 0xa7 # " tonight and " # Idx: 677 = 705 - 28 = 0x2c1 - 0x1c. Len: 3 = 0x3. .byte 0x83 0x1c # "the" .ascii "n" # Idx: 708 - 708 # Idx: 648 = 709 - 61 = 0x2c5 - 0x3d. Len: 7 = 0x7. .byte 0x87 0x3d # " 12 to " .ascii "18" # Idx: 716 - 717 # Idx: 657 = 718 - 61 = 0x2ce - 0x3d. Len: 7 = 0x7. .byte 0x87 0x3d # "\nhours " # Idx: 577 = 725 - 148 = 0x2d5 - 0x94. Len: 16 = 0x10. .byte 0x90 0x94 # "Wednesday night." .byte 0 # Original: 741 B, Better Compressed: 428 B, Ratio: 0.578 msg: .asciiz "Unsqwished Data:\n------------------------------------------------------------------------------\n%/a2/s\n------------------------------------------------------------------------------\n\n" msg_err: .asciiz "Input %/a2/s: Error at idx %/t4/d. Text below is from idx %/t6/d - %/t8/d.\n Found: \"%/t5/s\"\nCorrect: \"%/t7/s\"\n\n"; msg_correct: .asciiz "Input %/a2/s: Decompressed text is all correct.\n\n" dname_simple: .asciiz "Simple" dname_better: .asciiz "Better" data_out: .space 512 .text .globl __start __start: la $a0, msg la $a2, uncomp addi $v0, $0, 11 syscall la $a0, comp_simple la $a1, data_out jal unsqw nop la $a2, dname_simple jal TB_CHECK nop la $a0, comp_better la $a1, data_out addi $t0, $a1, 512 TB_LOOP_CLEAR: sb $0, 0($a1) bne $a1, $t0, TB_LOOP_CLEAR addi $a1, $a1, 1 la $a1, data_out jal unsqw nop la $a2, dname_better jal TB_CHECK nop addi $v0, $0, 10 syscall nop TB_CHECK: la $t0, uncomp la $t1, data_out TB_COMPARE: lbu $t2, 0($t0) lbu $t3, 0($t1) bne $t2, $t3, TB_ERROR addi $t0, $t0, 1 bne $t2, $0, TB_COMPARE addi $t1, $t1, 1 j TB_CORRECT nop TB_ERROR: la $a0, msg_err addi $v0, $0, 11 la $t5, data_out sub $t4, $t1, $t5 addi $t7, $0, 10 # Amount of context sub $t6, $t4, $t7 bgez $t6, TB_POS nop addi $t6, $0, 0 TB_POS: add $t5, $t5, $t6 la $t7, uncomp add $t7, $t7, $t6 addi $t8, $t4, 1 sb $0, 1($t0) sb $0, 2($t1) syscall nop j TB_DONE nop TB_CORRECT: la $a0, msg_correct addi $v0, $0, 11 syscall TB_DONE: jr $ra nop