```################################################################################
##
## 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.

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.

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.

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.

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.

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.
bne \$t4, \$t5, COPY_LOOP
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
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
TB_LOOP_CLEAR:
sb \$0, 0(\$a1)
bne \$a1, \$t0, TB_LOOP_CLEAR
la \$a1, data_out

jal unsqw
nop
la \$a2, dname_better
jal TB_CHECK
nop

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
bne \$t2, \$0, TB_COMPARE
j TB_CORRECT
nop

TB_ERROR:
la \$a0, msg_err
la \$t5, data_out
sub \$t4, \$t1, \$t5
addi \$t7, \$0, 10 # Amount of context
sub \$t6, \$t4, \$t7
bgez \$t6, TB_POS
nop
TB_POS:
la \$t7, uncomp
sb \$0, 1(\$t0)
sb \$0, 2(\$t1)
syscall
nop
j TB_DONE
nop

TB_CORRECT:
la \$a0, msg_correct