---
# System prepended metadata

title: CA Homework 2

---

# CA HOMEWORK 2
GITHUB: https://github.com/zhenfong07/ca2025-homework2/tree/main/my_playground/playground

## Uf8_main.c source code
- Change the Objective in the Makefile with the uf8_main.o
![fix uf8](https://hackmd.io/_uploads/BJCc8MzgZe.png)


For the source code that the teacher has given in the solution, we need to make some changes so that it can be run on the bare metal environment.
- First, we need to remove the library that are not able to use in the bare metal environment such as #include <stdio.h>, #include <stdlib.h>, #include <string.h>, #include <assert.h because it need the standard operation system to be run. 
- We also need to rename the function like $\mathbf{calloc(), realloc(), free()}$ to $\mathbf{my calloc(), my realloc(), my free()}$ because the initial ones may be linked to the library libc and it cannot been executed successfully on the bare metal environment.

```c
#include <stdbool.h>
#include <stdint.h>
#include <stddef.h> // Cần thiết cho kiểu size_t

/* ================================================
 * HÀM IN BARE-METAL (Dùng ECALL cho rv32emu -system)
 * ================================================ */

// Đây là macro 'printstr' gốc từ tệp main.c mẫu.
// Nó sử dụng 'ecall' (syscall) để in, đây là cách
// 'rv32emu -system' mong đợi.
#define printstr(ptr, length) \
    do { \
        asm volatile( \
            "add a7, x0, 0x40;" /* 64 = sys_write */ \
            "add a0, x0, 0x1;"  /* 1 = stdout */ \
            "add a1, x0, %0;"   /* con trỏ buffer */ \
            "mv a2, %1;"        /* độ dài */ \
            "ecall;" \
            : \
            : "r"(ptr), "r"(length) \
            : "a0", "a1", "a2", "a7"); \
    } while (0)

// Cập nhật macro TEST_OUTPUT và TEST_LOGGER
#define TEST_OUTPUT(msg, length) printstr(msg, (size_t) length)

#define TEST_LOGGER(msg)                       \
    {                                          \
        char _msg[] = msg;                     \
        TEST_OUTPUT(_msg, sizeof(_msg) - 1); \
    }

/* ================================================
 * CÁC HÀM HỖ TRỢ IN SỐ (Sửa để dùng printstr)
 * ================================================ */

static unsigned long udiv(unsigned long dividend, unsigned long divisor) {
    if (divisor == 0) return 0;
    unsigned long quotient = 0, remainder = 0;
    for (int i = 31; i >= 0; i--) {
        remainder <<= 1;
        remainder |= (dividend >> i) & 1;
        if (remainder >= divisor) {
            remainder -= divisor;
            quotient |= (1UL << i);
        }
    }
    return quotient;
}

static unsigned long umod(unsigned long dividend, unsigned long divisor) {
    if (divisor == 0) return 0;
    unsigned long remainder = 0;
    for (int i = 31; i >= 0; i--) {
        remainder <<= 1;
        remainder |= (dividend >> i) & 1;
        if (remainder >= divisor) {
            remainder -= divisor;
        }
    }
    return remainder;
}

static void print_hex(unsigned long val) {
    char buf[20];
    char *p = buf + sizeof(buf) - 1;
    *p = '\n'; // Thêm newline
    p--;
    if (val == 0) {
        *p = '0'; p--;
    } else {
        while (val > 0) {
            int digit = val & 0xf;
            *p = (digit < 10) ? ('0' + digit) : ('a' + digit - 10);
            p--;
            val >>= 4;
        }
    }
    p++;
    // Dùng printstr thay vì printstr_baremetal
    printstr(p, (buf + sizeof(buf) - p));
}

static void print_dec(unsigned long val) {
    char buf[20];
    char *p = buf + sizeof(buf) - 1;
    *p = '\n'; // Thêm newline
    p--;
    if (val == 0) {
        *p = '0'; p--;
    } else {
        while (val > 0) {
            *p = '0' + umod(val, 10);
            p--;
            val = udiv(val, 10);
        }
    }
    p++;
    // Dùng printstr thay vì printstr_baremetal
    printstr(p, (buf + sizeof(buf) - p));
}

/* ================================================
 * ĐO LƯỜNG HIỆU NĂNG (Giữ nguyên)
 * ================================================ */
extern uint64_t get_cycles(void);
extern uint64_t get_instret(void);


/* ================================================
 * HOMEWORK 1: UF8 IMPLEMENTATION (Mã của bạn)
 * ================================================ */
typedef uint8_t uf8;

static inline unsigned clz(uint32_t x) {
    int n = 32, c = 16;
    do {
        uint32_t y = x >> c;
        if (y) {
            n -= c;
            x = y;
        }
        c >>= 1;
    } while (c);
    return n - x;
}

uint32_t uf8_decode(uf8 fl) {
    uint32_t mantissa = fl & 0x0f;
    uint8_t exponent = fl >> 4;
    uint32_t offset = (0x7FFF >> (15 - exponent)) << 4;
    return (mantissa << exponent) + offset;
}

uf8 uf8_encode(uint32_t value) {
    if (value < 16)
        return value;
    int lz = clz(value);
    int msb = 31 - lz;
    uint8_t exponent = 0;
    uint32_t overflow = 0;
    if (msb >= 5) {
        exponent = msb - 4;
        if (exponent > 15)
            exponent = 15;
        for (uint8_t e = 0; e < exponent; e++)
            overflow = (overflow << 1) + 16;
        while (exponent > 0 && value < overflow) {
            overflow = (overflow - 16) >> 1;
            exponent--;
        }
    }
    while (exponent < 15) {
        uint32_t next_overflow = (overflow << 1) + 16;
        if (value < next_overflow)
            break;
        overflow = next_overflow;
        exponent++;
    }
    uint8_t mantissa = (value - overflow) >> exponent;
    return (exponent << 4) | mantissa;
}


/* ================================================
 * TEST SUITE CHO HW1
 * ================================================ */

static bool test_uf8_roundtrip(void) {
    int32_t previous_value = -1;
    bool passed = true;

    for (int i = 0; i < 256; i++) {
        uint8_t fl = i;
        int32_t value = uf8_decode(fl);
        uint8_t fl2 = uf8_encode(value);

        if (fl != fl2) {
            TEST_LOGGER("FAIL: "); print_hex(fl);
            TEST_LOGGER("  produces value "); print_dec(value);
            TEST_LOGGER("  but encodes back to "); print_hex(fl2);
            passed = false;
        }

        if (value <= previous_value) {
            TEST_LOGGER("FAIL: "); print_hex(fl);
            TEST_LOGGER("  value "); print_dec(value);
            TEST_LOGGER("  <= previous_value "); print_dec(previous_value);
            passed = false;
        }
        previous_value = value;
    }
    return passed;
}

/* ================================================
 * HÀM MAIN() CHÍNH
 * ================================================ */
int main(void) {
    uint64_t start_cycles, end_cycles, cycles_elapsed;
    uint64_t start_instret, end_instret, instret_elapsed;

    TEST_LOGGER("=== Bat dau Test Suite cho Homework 1: UF8 ===\n");

    // Lấy thời gian bắt đầu
    start_cycles = get_cycles();
    start_instret = get_instret();

    // Chạy test suite
    bool all_passed = test_uf8_roundtrip();

    // Lấy thời gian kết thúc
    end_cycles = get_cycles();
    end_instret = get_instret();

    // Tính toán
    cycles_elapsed = end_cycles - start_cycles;
    instret_elapsed = end_instret - start_instret;

    // In kết quả test
    if (all_passed) {
        TEST_LOGGER("== Homework 1: All tests PASSED ==\n");
    } else {
        TEST_LOGGER("== Homework 1: FAILED ==\n");
    }

    // In kết quả hiệu năng
    TEST_LOGGER("Cycles: ");
    print_dec((unsigned long) cycles_elapsed);
    TEST_LOGGER("Instructions: ");
    print_dec((unsigned long) instret_elapsed);
    TEST_LOGGER("\n=== All Tests Completed ===\n");

    return 0; // Sẽ thoát về start.S, sau đó gọi ecall (sys_exit)
}

```
![UF8](https://hackmd.io/_uploads/H1_BZjllbl.png)
####

# Adapt Question B quizz 3 and question A quizz 2
- Change the Objective in Makefile with main.o and hanoi.o to run 2 questions at the same time.
![hanoinew](https://hackmd.io/_uploads/HyeZXXflWx.png)

## Question C from quizz 3

## Introduction
The main goal of this question is to propose a significantly effective algorithm to implement an optimized function for the fast reciprocal square root ($\mathbf{1/\sqrt{x}}$) and 3D distance calculation ($\mathbf{\sqrt{dx^2 + dy^2 + dz^2}}$) on the RV32I architecture. The core challenge was to achieve high performance and acceptable precision ($\approx 3-8\%$ error) without relying on a Floating-Point Unit (FPU) or a high-speed hardware multiplier.The solution utilizes a hybrid approach combining Lookup Tables (LUT) and two iterations of the Newton-Raphson method, implemented entirely using Fixed-Point Arithmetic. I think the questions have been given some algorithm to optimize the process to run very fast so I mainly use the algorithms to implement the most optimized one.
### Algorithmic Principle and Fixed-Point Implementation
#### Fixed-Point Representation ($\mathbf{2^{16}}$ Scaling)
 To perform floating-point operations using integer hardware, the $\mathbf{2^{16}}$ Fixed-Point format (Q2.16) was adopted.
- Scaling: All fractional values are scaled by $2^{16}$ (65536).
- Conversion: $\mathbf{V_{\text{real}}} = \mathbf{V_{\text{integer}}} / 65536$.
- Reasoning: This scaling provides sufficient precision (16 fractional bits) while making shift operations efficient (>> 16 instead of >> 32) on the 32-bit architecture.
#### 2.2. Core Algorithm: $\mathbf{fast\_rsqrt(x)}$
##### A. LUT Initial Estimate
The initial estimate for $1/\sqrt{x}$ is retrieved using the MSB position ($exp$) as the index into the $\mathbf{rsqrt\_table}$.
- MSB Calculation: The position $exp$ is determined using the Count Leading Zeros function: $\mathbf{exp = 31 - \text{clz}(x)}$.
- Estimate: $y_{\text{base}} = \mathbf{rsqrt\_table}[exp]$. This step reduces the initial error to approximately $20\%$.
##### B. Linear Interpolation
To refine the estimate for inputs that are not exact powers of two, linear interpolation is performed between adjacent table entries ($y_{\text{base}}$ and $y_{\text{next}}$). This step further reduces the error to about $10\%$.
##### C. Newton-Raphson Iteration (2 Times)
The core precision refinement relies on the Newton's method for solving $f(y) = 1/y^2 - x = 0$. The resulting iterative formula, adapted for $2^{16}$ fixed-point, is:$$\mathbf{y_{n+1} = \frac{y_n \cdot (3 \cdot 2^{16} - x \cdot y_n^2)}{2^{17}}}$$
- Implementation Detail: The expression $\mathbf{x \cdot y_n^2}$ and the final multiplication $\mathbf{y_n \cdot (...) / 2}$ require intermediate 64-bit multiplication ((uint64_t)y*y) followed by specific shift operations ($\mathbf{>>16}$ and $\mathbf{>>17}$) to handle the scaling factors accurately. Two iterations guarantee the desired $3-8\%$ final precision. The below code is the implementation of algorithm.
```c
static inline unsigned clz(uint32_t x) {
    if (x==0) return 32;
    unsigned n=0; uint32_t bit=0x80000000;
    while ((x & bit)==0) { n++; bit>>=1; }
    return n;
}

static const uint16_t rsqrt_table[32] = {
    65535,46341,32768,23170,16384,11585,8192,5793,
    4096,2896,2048,1448,1024,724,512,362,
    256,181,128,90,64,45,32,23,
    16,11,8,6,4,3,2,1
};

uint32_t fast_rsqrt(uint32_t x) {
    if (x==0) return 0xFFFFFFFFu;
    if (x==1) return 65536;
    uint32_t exp = 31 - clz(x);
    uint32_t y_base = rsqrt_table[exp];
    uint32_t y_next = (exp==31)?1:rsqrt_table[exp+1];
    uint32_t delta = y_base - y_next;
    uint64_t frac_num_scaled = (uint64_t)(x-(1U<<exp))<<16;
    uint32_t frac = (uint32_t)(frac_num_scaled>>exp);
    uint32_t interp = (uint32_t)(((uint64_t)delta*frac)>>16);
    uint32_t y = y_base - interp;

    uint32_t y2 = (uint32_t)(((uint64_t)y*y)>>16); /* Compute y^2 in 2^32 scaling, then shift >> 16 to get Q2.16 result */
    uint32_t xy2 = (uint32_t)((uint64_t)x*y2);/* Compute x * y^2 / 2^16 */
    y = (uint32_t)(((uint64_t)y*((3U<<16)-xy2))>>17);/* Complete Newton step: y_n * (3*2^16 - x*y^2) / 2^17 */
    /* The next Newton Raphson Iteration*/
    y2 = (uint32_t)(((uint64_t)y*y)>>16);
    xy2 = (uint32_t)((uint64_t)x*y2);
    y = (uint32_t)(((uint64_t)y*((3U<<16)-xy2))>>17);

    return y;
}
```
For the rsqrt_table the value '65536' must be changed to '65535' because The maximum value that a $\mathbf{\text{uint16_t}}$ (16-bit unsigned integer) can hold is $\mathbf{2^{16} - 1 = 65535}$. ![Screenshot 2025-11-11 140032](https://hackmd.io/_uploads/Syd5bIegbx.png)
The Ubuntu terminal will give a warning in this so '65535' must be used and this adjustment is necessary for the compiler to correctly place the initial estimate into the LUT without error, while the subsequent Newton-Raphson iterations ensure the final result maintains high accuracy, even when starting with this slightly lower bound.

### 3. Application: $\mathbf{fast\_distance\_3d}$
The reciprocal square root is applied to calculate the 3D Euclidean distance $D = \sqrt{D^2}$:
- Distance Squared: $\mathbf{\text{dist_sq}} = dx^2 + dy^2 + dz^2$ is computed using $\mathbf{\text{uint64_t}}$ to prevent overflow.
- Square Root Calculation: The square root is calculated as a multiplication:
-$$\mathbf{D = D^2 \times (1/\sqrt{D^2})}$$$$\mathbf{\text{dist}} = (\text{dist_sq} \times \text{inv}) >> 16$$Where $\mathbf{\text{inv}}$ is the result from $\mathbf{\text{fast_rsqrt}(\text{dist_sq})}$.
```c
uint32_t fast_distance_3d(int32_t dx,int32_t dy,int32_t dz) {
    uint64_t dist_sq = (uint64_t)dx*dx + (uint64_t)dy*dy + (uint64_t)dz*dz;
    if (dist_sq>0xFFFFFFFFu) dist_sq>>=16;
    if (dist_sq==0) return 0;
    uint32_t inv = fast_rsqrt((uint32_t)dist_sq);
    uint64_t dist = ((uint64_t)dist_sq * inv)>>16;
    return (uint32_t)dist;
}

bool test_rsqrt() {
    int32_t dx=3,dy=4,dz=12;
    uint32_t distance = fast_distance_3d(dx,dy,dz);
    TEST_LOGGER("Test fast_distance_3d(3,4,12):");
    TEST_LOGGER("Expected: 13");
    TEST_LOGGER("Actual: ");
    print_dec_and_newline(distance);
    return (distance==13);
}
```
#### A. Initial Estimate (MSB)
We have $$D^2 = 3^2 + 4^2 + 12^2 = 9 + 16 + 144 = \mathbf{169}$$
- The goal of the fast_rsqrt function is to calculate $\frac{2^{16}}{\sqrt{x}}$.The input is $x = \text{dist_sq} = 3^2 + 4^2 + 12^2 = \mathbf{169}$.
- The Most Significant Bit (MSB) position of $169$ is $7$ (since $2^7 = 128 \le 169 < 2^8 = 256$).
The exponent is $\mathbf{exp} = 7$.
- The base estimate $\mathbf{y_{base}}$ is taken from the lookup table: $\mathbf{y_{base}} = \text{rsqrt_table}[7] = 5793$. 
This value is an initial approximation for $\frac{2^{16}}{\sqrt{128}}$.
#### B. The Role of the Initial Estimate in Linear Interpolation
The initial estimate $\mathbf{y_{base} = 5793}$ is used alongside the next value ($\mathbf{y_{next}}$) to perform Linear Interpolation.
- Base Value ($\mathbf{y_{base}}$): $\mathbf{y_{base}} = \text{rsqrt_table}[7] = \mathbf{5793}$ (the estimate for $x=128$).
- Next Value ($\mathbf{y_{next}}$): $\mathbf{y_{next}} = \text{rsqrt_table}[8] = \mathbf{4096}$ (the estimate for $x=256$).
- Difference ($\mathbf{delta}$): $\mathbf{delta} = y_{base} - y_{next} = 5793 - 4096 = \mathbf{1697}$.
- Fraction ($\mathbf{frac}$): This value calculates the position of $x=169$ between $128$ and $256$.The code calculates this as:
 --  $\text{frac} = (\text{uint32_t})( ( (\text{uint64_t})(169 - 128) \ll 16) \gg 7)$.
 --This value represents the fractional part $\frac{169-128}{128} \approx 0.3203$ in $Q16$ Fixed-Point format.
Interpolation Term ($\mathbf{interp}$): $\mathbf{interp} = (\text{uint32_t})(((\text{uint64_t})\text{delta} \times \text{frac}) \gg 16)$.$\mathbf{interp}$ = $(1697 \times \text{frac}_{Q16}) \gg 16$.
- Refined Initial Value ($\mathbf{y}$):$\mathbf{y = y_{base} - interp}$ (i.e., $5793 - \text{interp}$).
The resulting $\mathbf{y}$ value (approximately $\mathbf{5240}$) becomes the official starting value ($\mathbf{y_0}$) that is fed into the Newton-Raphson iteration, helping the calculation quickly achieve the result of $\mathbf{13}$. 
### Output and Optimization
#### Compare the $\mathbf{-O0,-0fast}$  in the Makefile source
#### A. Using $\mathbf{-O0}$. 
![O0 Makefile](https://hackmd.io/_uploads/Hk3Knugl-g.png)
The Cycles and the Instructions are 3265, the ticks are 3260. It is the very large number. There are some reasons:
##### 1. Stack Overhead (Memory Access)
- Frequent Stack Usage: With $\mathbf{O0}$ , the compiler tends to Store and Load (lw/sw instructions) most local variables to and from the Stack (RAM) for almost every operation.
- High Cycle Cost: Accessing RAM via lw/sw instructions is significantly more costly in cycles than keeping variables in the CPU's Registers, thereby increasing the total cycle count substantially.
##### 2. Inefficient Loops (e.g., clz)
clz (Count Leading Zeros) function is written as a while loop.
- With $\mathbf{-O0}$, the compiler directly translates this loop, including the internal branching instructions.
- In the worst-case scenario (for very small values of $x$), this loop must execute 32 iterations and 32 branches, consuming a large number of cycles and instructions.
##### Using $\mathbf{-Ofast}$.
![Ofast](https://hackmd.io/_uploads/ry2vFYleWl.png)
The Cycles and the Instructions are 2073, the ticks are 2072. It has been reduced. There are some reasons:
##### 1. Superior Register Allocation (Eliminating Stack Overhead)
- The $\mathbf{-O0}$ flag creates significant overhead by constantly Loading and Storing local variables to and from the slow Stack (RAM).
- The $\mathbf{-Ofast}$ flag performs optimal Register Allocation. It keeps the critical local variables (like $x, y, y_2,$ and $xy_2$) inside the fast CPU Registers.
##### 2. Hardware-Accelerated Fixed-Point Multiplication
- It uses instructions like MULHU (Multiply High Unsigned) to directly compute the high 32 bits of the 64-bit product. 
-  This high-bit information is precisely what's needed for the Q16 fixed-point shift (>> 16).
##### 3. Loop and Branch Optimization
- Inefficient clz Loop: The while loop used in the custom clz (Count Leading Zeros) function is slow because it may involve up to 32 costly branching decisions.
- Optimization: $\mathbf{-Ofast}$ optimizes this loop by either:
-- Loop Unrolling: Expanding the loop into a sequence of instructions to eliminate branch overhead.
-- Bitwise Heuristics: Replacing the iterative loop with an optimized sequence of shifts and logic operations that resolves the clz value with fewer, non-branching steps.
## Question A from quizz 2
The following is the original source code based on the solution.
```c
    .text
    .globl hanoi_asm

hanoi_asm:
    addi    x2, x2, -56
    sw      x8,  0(x2)
    sw      x9,  4(x2)
    sw      x18, 8(x2)
    sw      x19, 12(x2)
    sw      x20, 16(x2)
    sw      s2, 20(x2)
    sw      s3, 24(x2)
    sw      s4, 28(x2)
    sw      s5, 32(x2)
    sw      s6, 36(x2)
    sw      s7, 40(x2)

    # 3 disk positions stored at offsets 44,48,52
    sw      x0, 44(x2)
    sw      x0, 48(x2)
    sw      x0, 52(x2)

    li      x8, 1             # iteration counter

game_loop:
    # stop after 7 moves for 3 disks (2^3 - 1 = 7)
    addi    x5, x0, 8
    beq     x8, x5, finish_game

    # Gray code n: g(n) = n XOR (n >> 1)
    srli    x5, x8, 1
    xor     x6, x8, x5

    # Gray code n-1: g(n-1) = (n-1) XOR ((n-1)>>1)
    addi    x7, x8, -1
    srli    x28, x7, 1
    xor     x7, x7, x28

    # changed bit = g(n) XOR g(n-1)
    xor     x5, x6, x7

    # determine disk number
    addi    x9, x0, 0
    andi    x6, x5, 1
    bne     x6, x0, disk_found
    addi    x9, x0, 1
    andi    x6, x5, 2
    bne     x6, x0, disk_found
    addi    x9, x0, 2

disk_found:
    # base position entry = 44 + disk*4
    slli    x5, x9, 2
    addi    x5, x5, 44
    add     x5, x2, x5
    lw      x18, 0(x5)        # x18 = old source peg

    # compute destination peg
    bne     x9, x0, handle_large

    # disk 0 moves +2 mod 3
    addi    x19, x18, 2
    li      x6, 3
    blt     x19, x6, display_move
    sub     x19, x19, x6
    jal     x0, display_move

handle_large:
    lw      x6, 44(x2)        # pos of largest disk
    li      x19, 3
    sub     x19, x19, x18
    sub     x19, x19, x6

display_move:
    # x9  = disk index
    # x18 = source peg index
    # x19 = destination peg index

    # convert peg index → ASCII ('A'+index)
    addi    t2, x18, 65       # source char
    addi    t3, x19, 65       # dest char

    # ----- print "Move Disk " -----
    li      a0, 1
    la      a1, str1
    li      a2, 10
    li      a7, 64
    ecall

    # ----- disk number (ASCII) -----
    addi    t0, x9, 1         # disk number 1..3
    addi    t0, t0, 48        # '0' + number
    la      t1, char_buffer
    sb      t0, 0(t1)

    li      a0, 1
    la      a1, char_buffer
    li      a2, 1
    li      a7, 64
    ecall

    # ----- " from " -----
    li      a0, 1
    la      a1, str2
    li      a2, 6
    li      a7, 64
    ecall

    # ----- source peg -----
    la      t1, char_buffer
    sb      t2, 0(t1)

    li      a0, 1
    la      a1, char_buffer
    li      a2, 1
    li      a7, 64
    ecall

    # ----- " to " -----
    li      a0, 1
    la      a1, str3
    li      a2, 4
    li      a7, 64
    ecall

    # ----- destination peg -----
    la      t1, char_buffer
    sb      t3, 0(t1)

    li      a0, 1
    la      a1, char_buffer
    li      a2, 1
    li      a7, 64
    ecall

    # ----- newline -----
    li      t0, 10
    la      t1, char_buffer
    sb      t0, 0(t1)

    li      a0, 1
    la      a1, char_buffer
    li      a2, 1
    li      a7, 64
    ecall

    # update disk position table
    slli    x5, x9, 2
    addi    x5, x5, 44
    add     x5, x2, x5
    sw      x19, 0(x5)

    addi    x8, x8, 1
    jal     x0, game_loop

# -------------------------------------------------------
# RETURN
# -------------------------------------------------------
finish_game:
    lw      x8,  0(x2)
    lw      x9,  4(x2)
    lw      x18, 8(x2)
    lw      x19, 12(x2)
    lw      x20, 16(x2)
    lw      s2, 20(x2)
    lw      s3, 24(x2)
    lw      s4, 28(x2)
    lw      s5, 32(x2)
    lw      s6, 36(x2)
    lw      s7, 40(x2)

    addi    x2, x2, 56
    ret


# -------------------------------------------------------
# DATA
# -------------------------------------------------------
    .data
str1:        .asciz  "Move Disk "
str2:        .asciz  " from "
str3:        .asciz  " to "
char_buffer: .space  1

```

- After running, the teminal will appear like this
![problem code B](https://hackmd.io/_uploads/HkSFN7fxWe.png)

### Optimization for this question
Please change the objective of the Makefile like this:
![makefileforoptimation](https://hackmd.io/_uploads/rkhDjmMeWe.png)

#### 1. Modification : Function Prologue - Optimizing Register Saves
- the old version:
```c
hanoi_asm:
    addi    x2, x2, -56
    sw      x8,  0(x2)
    sw      x9,  4(x2)
    sw      x18, 8(x2)
    sw      x19, 12(x2)
    sw      x20, 16(x2)
    sw      s2, 20(x2)
    sw      s3, 24(x2)
    sw      s4, 28(x2)
    sw      s5, 32(x2)
    sw      s6, 36(x2)
    sw      s7, 40(x2)
```
remove x20, s2, s3, s4, s5, s6, s7 that are not used. This optimization successfully removed 7 sw instructions. Consequently, the stack frame allocation was decreased from 56 bytes to 32 bytes.
- new version:
```c
hanoi_asm:
    addi x2, x2, -32     # 32-byte stack frame (reduced from 56)
    sw   x8,  0(x2)      # ✓ KEPT - used as iteration counter
    sw   x9,  4(x2)      # ✓ KEPT - used for disk number
    sw   x18, 8(x2)      # ✓ KEPT - used for source peg
    sw   x19, 12(x2)     # ✓ KEPT - used for dest peg
                         # ✓ REMOVED 7 unnecessary sw instructions
```
#### Modification 2: Adjusting Stack Offsets
- the old version:
```c
# 3 disk positions stored at offsets 44,48,52
    sw   x0, 44(x2)
    sw   x0, 48(x2)
    sw   x0, 52(x2)
```
- the new version:
```c
# 3 disk positions stored at offsets 16,20,24
    sw   x0, 16(x2)     # ✓ Changed from 44 to 16
    sw   x0, 20(x2)     # ✓ Changed from 48 to 20
    sw   x0, 24(x2)     # ✓ Changed from 52 to 24
```
The reduction of the stack frame (from 56 to 32 bytes) required relocating the disk position data. These values now begin at an offset of 16 rather than the original 44.
#### Modification 3: Updating Disk Position Accessors
As a consequence of the offset changes in Modification 2, all instructions referencing these memory locations had to be updated.

1. disk_found block:

- Original: addi x5, x5, 44 (Old offset)
- Optimized: addi x5, x5, 16 (New offset)

2. handle_large block:

- Original: lw x6, 44(x2) (Old offset)
- Optimized: lw x6, 16(x2) (New offset)

3. Position update block (before game_loop):

- Original: addi x5, x5, 44 (Old offset)
- Optimized: addi x5, x5, 16 (New offset)

#### Modification 4: Epilogue - Reducing Register Restores
Mirroring the changes made in the prologue, the corresponding lw (load word) instructions for unused registers were removed. The stack deallocation command was also adjusted to match the new frame size in the function exit.

- the old version
```c
finish_game:
    lw      x8,  0(x2)
    lw      x9,  4(x2)
    lw      x18, 8(x2)
    lw      x19, 12(x2)
    lw      x20, 16(x2)
    lw      s2, 20(x2)
    lw      s3, 24(x2)
    lw      s4, 28(x2)
    lw      s5, 32(x2)
    lw      s6, 36(x2)
    lw      s7, 40(x2)

    addi    x2, x2, 56
    ret
```
- the new version:
```c
finish_game:
    lw   x8,  0(x2)      # ✓ KEPT - restore used register
    lw   x9,  4(x2)      # ✓ KEPT - restore used register
    lw   x18, 8(x2)      # ✓ KEPT - restore used register
    lw   x19, 12(x2)     # ✓ KEPT - restore used register
                         # ✓ REMOVED 7 unnecessary lw instructions
    addi x2, x2, 32      # ✓ Changed from 56 to 32
    ret
```
This change eliminated 7 lw instructions, and the stack pointer deallocation was corrected from 56 to 32.
Then the cycles, instructions and ticks have been reduced
![HANOI OPTIMIZE](https://hackmd.io/_uploads/SkYKqmGe-e.png)



