################################################################################ ## ## LSU EE 4720 Spring 2025 Homework 1 -- SOLUTION ## ## # Assignment https://www.ece.lsu.edu/ee4720/2025/hw01.pdf # Solution discussion: https://www.ece.lsu.edu/ee4720/2025/hw01_sol.pdf ## Additional Resources # # MIPS Architecture Manual Volume 2 (Contains a list of instructions.) # https://www.ece.lsu.edu/ee4720/mips32v2.pdf # Note: SPIM implements MIPS-I instructions. # # SPIM Documentation: # https://www.ece.lsu.edu/3755/spim.pdf # # Account Setup and Emacs (Text Editor) Instructions # https://www.ece.lsu.edu/ee4720/proc.html # To learn Emacs look for and follow instructions for the Emacs tutorial. ################################################################################ ## Problem 1 # # Copy text, breaking it into 64-character lines. p1_justify: # Input registers. # $a0: Address of start of text to justify. # $a1: Address where justified text is to be written. # $a2: Array of margins. Left margin, text length. # Each is 1 byte. Negative, go back? # Assume: Never two or more spaces. ## SOLUTION ori $t9, $0, 10 # t9: Line feed. p1_line_loop: ## Each iteration of p1_line_loop writes one 64-character line. addi $t0, $a1, 64 # t0: Where to end line based on write address. p1_text_loop: ## Each iteration of p1_text_loop copies one character. # # Loop body contains 6 instructions. # lb $t1, 0($a0) # Read one character from input string. sb $t1, 0($a1) # Write it to the output string. beq $t1, $0, p1_done # Check whether it's a null (end of string). addi $a1, $a1, 1 # Increment output string address. bne $a1, $t0, p1_text_loop # If not at 64'th char, continue. addi $a0, $a0, 1 # Increment input string address. sb $t9, 0($a1) # Put a line feed at the end of the line. j p1_line_loop addi $a1, $a1, 1 p1_done: jr $ra nop ################################################################################ ## Problem 2 # # Write memory at a1 with formatted version of input string at a0 # using left margins and text lengths found in shape table at a2. # See https://www.ece.lsu.edu/ee4720/2025/hw01.pdf for details. justify: # Input registers. # $a0: Address of start of text to justify. # $a1: Address where justified text is to be written. # $a2: Array of margins. Left margin, text length. # Each is 1 byte. Negative, go back? # Assume: Never two or more spaces. ## SOLUTION ## Put Useful Constants In Registers -- In Advance # # Put four spaces in $t4. # lui $t4, 0x2020 ori $t4, $t4, 0x2020 # t4: Four spaces. addi $t6, $0, 32 # t6: One space ori $t8, $0, 255 # t8: Value used for end of shape table. ori $t9, $0, 10 # t9: Line feed addi $v1, $0, -4 # v1: 0xfffffffc Mask used for rounding. ## Make Copies of Input Registers -- Important for a2. # addi $t5, $a1, 0 # t5: Address of next character to write. addi $t7, $a2, 0 # t7: Beginning of shape table. jf_line_loop: ## Each iteration of jf_line_loop processes one line of text. # Read an entry from the shape table. # lbu $t0, 0($t7) # t0: Left margin length. lbu $t1, 1($t7) # t1: Text length. # If this isn't the end of the table go to left-margin code. bne $t0, $t8, jf_alignment_check addi $t7, $t7, 2 # Advance to next shape table entry. # At this point we are at the end of the shape table .. # .. so reset the shape table address to the beginning of the table. j jf_line_loop addi $t7, $a2, 0 # Reset to beginning of shape table and try again. jf_alignment_check: ## Check whether t5 (write address) is word-aligned, if not align it. # # An address is word-aligned (in MIPS) if it's a multiple of 4. and $v0, $t5, $v1 # Using mask (v1), set v0 to t5 with 2 LSB zeroed. # # Note: v0 is t5 rounded *down* to a multiple of 4. # For example, if t5 = 0x1003 -> v0 = 0x1000 (zero 2 LSB). # if t5 = 0x1004 -> v0 = 0x1004 (no change). # If v0 = t5 then t5 is already aligned. beq $v0, $t5, jf_aligned_now add $t2, $t5, $t0 # t2: Starting address of text in current line. # At this point we know that t5 is not aligned. # Write 3 spaces. Maybe one or two of those won't be needed .. # .. but checking whether they are needed .. # .. is more trouble than just writing them. # sb $t6, 0($t5) # This space definitely needed. sb $t6, 1($t5) # Might be needed. sb $t6, 2($t5) # Might be needed. # Compute aligned address rounded *up* from t5. (v0 rounded down) # addi $t5, $v0, 4 # t5: Write address, now aligned (rounded up). jf_aligned_now: # We also need to round the left margin stop address, t2, up # to a multiple of 4. addi $t3, $t2, 3 # Add 3 to stop address. and $t3, $t3, $v1 # Round t3 *down* to a multiple of 4. jf_margin_loop_fast: ## Each iteration of margin_loop writes four spaces in the left margin. # # Loop body executes 3 instructions. # sw $t4, 0($t5) # Write four spaces. bne $t5, $t3, jf_margin_loop_fast addi $t5, $t5, 4 # Last iteration of loop above may write one to three extra spaces .. # .. and so t5 might be too large. ori $t5, $t2, 0 # Set t5 to the correct write address. add $t2, $t5, $t1 # Compute the minimum address to end the line. jf_text_loop: ## Each iteration copies one character of text. # # Loop body executes 6 instructions when within words. # lb $t0, 0($a0) jf_text_loop_plus_one: slt $t1, $t6, $t0 # Check for whitespace and null (zero terminator). addi $a0, $a0, 1 sb $t0, 0($t5) bne $t1, $0, jf_text_loop addi $t5, $t5, 1 # At this point character is whitespace or a null. # This is still part of the text loop body, though it is # executed less frequently. beq $t0, $0, jf_DONE # If character is a null we're done. slt $t1, $t5, $t2 # Check whether text length is below minimum. bne $t1, $0, jf_text_loop_plus_one lb $t0, 0($a0) # This is the "first" insn of next iteration. # At this point text on current line is at or above the # minimum length and the current character (t0) is whitespace, # so we can write a line feed and start a new line. j jf_line_loop sb $t9, -1($t5) # Write linefeed in same location as whitespace. jf_DONE: jr $ra nop ############################################################################## # ## Test Code # # The code below calls the justify routine. .data .align 2 tb_lengths_start: .byte 30, 10 .byte 25, 20 .byte 20, 30 .byte 15, 40 .byte 10, 50 .byte 5, 60 .byte 0, 70 .byte 5, 60 .byte 10, 50 .byte 15, 40 .byte 20, 30 .byte 25, 20 .byte 30, 10 .byte 255, 255 tb_text_start: .asciiz "We introduce our first-generation reasoning models, DeepSeek-R1-Zero and DeepSeek-R1. DeepSeek-R1-Zero, a model trained via large-scale reinforcement learning (RL) without supervised fine-tuning (SFT) as a preliminary step, demonstrated remarkable performance on reasoning. With RL, DeepSeek-R1-Zero naturally emerged with numerous powerful and interesting reasoning behaviors. However, DeepSeek-R1-Zero encounters challenges such as endless repetition, poor readability, and language mixing. To address these issues and further enhance reasoning performance, we introduce DeepSeek-R1, which incorporates cold-start data before RL. DeepSeek-R1 achieves performance comparable to OpenAI-o1 across math, code, and reasoning tasks. To support the research community, we have open-sourced DeepSeek-R1-Zero, DeepSeek-R1, and six dense models distilled from DeepSeek-R1 based on Llama and Qwen. DeepSeek-R1-Distill-Qwen-32B outperforms OpenAI-o1-mini across various benchmarks, achieving new state-of-the-art results for dense models." tb_msg: .ascii "Formatted text appears below.\n%/a1/s\n" .ascii "Formatted text appears above.\n" .ascii "Input string length %/f0/.0f characters.\n" .ascii "Output string length %/t0/d characters.\n" .asciiz "Executed %/s4/d instructions at rate of %/f6/.3f char/insn.\n" .align 4 tb_text_formatted: .space 2000 .text tb_strlen: ## Register Usage # # $a0: Address of first character of string. # $v0: Return value, the length of the string. # addi $v0, $a0, 1 # Set aside a copy of the string start + 1. STRLEN_LOOP: lbu $t0, 0($a0) # Load next character in string into $t0 bne $t0, $0, STRLEN_LOOP # If it's not zero, continue addi $a0, $a0, 1 # Increment address. (Note: Delay slot insn.) jr $ra sub $v0, $a0, $v0 .globl __start __start: mtc0 $0, $22 # Pause tracing. la $a0, tb_text_start la $a1, tb_text_formatted la $a2, tb_lengths_start addi $v0, $0, -1 mtc0 $v0, $22 # Resume tracing. (No effect if not stepping.) jal justify mfc0 $s5, $9 # Copy current instruction count. (Before.) mfc0 $s4, $9 # Copy current instruction count. (After.) mtc0 $0, $22 # Pause tracing. la $a0, tb_text_start jal tb_strlen nop addi $s4, $s4, -1 sub $s4, $s4, $s5 mtc1 $s4, $f4 mtc1 $v0, $f0 cvt.d.w $f0, $f0 cvt.d.w $f4, $f4 div.d $f6, $f0, $f4 la $a0, tb_text_formatted jal tb_strlen nop addi $t0, $v0, 0 la $a0, tb_msg la $a1, tb_text_formatted addi $v0, $0, 11 syscall nop addi $v0, $0, 10 syscall nop