---
# System prepended metadata

title: 'Assignment 1: RISC-V Assembly and Instruction Pipeline'

---

# Assignment 1: RISC-V Assembly and Instruction Pipeline
> ==Github: [dorobouharu133](https://github.com/dorobouharu133/ca2025-quizzes/tree/main)==

>[!Note] AI Tools Usage
>I used ChatGPT, Gemini and Copilot to find inspiration, refine the grammar of this article, explain the original C source code, debug and assist in generating the corresponding test data.
# Requirement 2
## Problem B
In uf8_encode, we can find some patterns in this function. In my first thought, I wanted to translate the C code to RISC-V instructions line-by-line. 
```c=
    /* Start from a good initial guess */
    uint8_t exponent = 0;
    uint32_t overflow = 0;

    if (msb >= 5) {
        /* Estimate exponent - the formula is empirical */
        exponent = msb - 4;
        if (exponent > 15)
            exponent = 15;

        /* Calculate overflow for estimated exponent */
        for (uint8_t e = 0; e < exponent; e++)
            overflow = (overflow << 1) + 16;
                    /* Adjust if estimate was off */
        while (exponent > 0 && value < overflow) {
            overflow = (overflow - 16) >> 1;
            exponent--;
        }
    }
```
During the translation, I found that the for loop did not need to be translate to RISC-V instruction directly, and we can just use some bit operation to have the same result.
Observe the above code, we can find that the range of exponent in the for loop is [1, 15], because only if `msb >= 5` then can enter the for loop, and then `exponent = msb - 4` which means exponent is at least 1, and the following if statement constrains exponent's upper bound.
Let's discuss the following for loop. `uint_8 e = 0`, the termination condition is `e < exponent`, since the range of exponent is [1, 15], so the for loop will run 1~15 times.
And the following step is my optimization.
```c=
        for (uint8_t e = 0; e < exponent; e++)
            overflow = (overflow << 1) + 16;
```
The initial value of overflow is 0, 
#### Pass 1
overflow<<$1= 0 << 1 = 0$, overflow = 0 + 16(in deicmal) = 0 + 10000(in binary) = 10000(in binary).
In the first pass, we get overflow = `10000`(in binary).

#### Pass 2
`Overflow<<1` = 10000 << 1 = 100000(binary), and `(Overflow<<1) + 16` = 100000 + 10000 = 110000(in binary).
In the second pass, we get overflow = `110000`(in binary).

---
#### Observation
I observe that the overflow has the pattern: overflow can be concatenated by (exponent) bits leading 1's + (fixed) 4 bits 0's.
Therefore, the translation of for loop is not needed, we can just use some bit operation to get this pattern.

#### Bit Operation
Overflow is consist of (exponent) bits leading 1's and 4 bits 0's.
How can we get the leading 1's of total exponent bits?
For example, we assume that exponent is 5, thus the overflow should be `111110000`, we want to get `11111` first.
This step we observe that `11111`(in binary) = 31(in decimal) = 32 - 1(in decimal). Therefore, we can calculate by $2^5 - 1$.
So exponent bits leading 1's can be obtained by $2^{\text{exponent}} - 1$, and we can easily get overflow by shift the above result 4 bits left.
```asm=
# t0: exponent
# t1: overflow
addi t1, x0, 1
sll t1, t1, t0 # get 2^exponent
addi t1, t1, -1 # get leading 1's
slli t1, t1. 4 # get overflow
```
Below is my approach 1, using bit operations to replace for loop.


### ==Approach 1==
> [Quiz 1 Problem B Approach 1](https://github.com/dorobouharu133/ca2025-quizzes/blob/main/quiz1_approach/q1-uf8-approach-1.S)
```asm=
.data
pass_msg: .string "All tests passed!\n"
fail_msg: .string "Test failed for value: "
test_msg: .string "Testing value: "
arrow_msg: .string " -> decoded: "
encoded_msg: .string " -> re-encoded: "
newline: .string "\n"
.align 2
.text
.globl main

main:
    # s0 will be our loop counter (0-255)
    # s1 will store the original value
    # s2 will store the decoded value
    # s3 will store the re-encoded value
    addi s0, x0, 0          

test_loop:
    # Print current test value
    la a0, test_msg
    addi a7, x0, 4
    ecall
    addi a0, s0, 0
    addi a7, x0, 1
    ecall

    # First decode the value
    addi a0, s0, 0
    addi s1, a0, 0    # Save original value
    jal uf8_decode
    addi s2, a0, 0    # Save decoded value

    # Print decoded value
    la a0, arrow_msg
    addi a7, x0, 4
    ecall
    addi a0, s2, 0
    addi a7, x0, 1
    ecall

    # Now encode the decoded value
    addi a0, s2, 0
    jal uf8_encode
    addi s3, a0, 0       # Save re-encoded value

    # Print re-encoded value
    la a0, encoded_msg
    addi a7, x0, 4
    ecall
    addi a0, s3, 0
    addi a7, x0, 1
    ecall
    
    la a0, newline
    addi a7, x0, 4
    ecall

    # Check if re-encoded value matches original
    bne s3, s1, test_fail

    # Increment counter and continue
    addi s0, s0, 1
    addi t0, x0, 256
    blt s0, t0, test_loop

    # All tests passed
    la a0, pass_msg
    addi a7, x0, 4
    ecall
    j exit

test_fail:
    la a0, fail_msg
    addi a7, x0, 4
    ecall
    addi a0, s1, 0
    addi a7, x0, 1
    ecall
    la a0, newline
    addi a7, x0, 4
    ecall

exit:
    addi a7, x0, 10         # exit
    ecall

#	a0: 	x
#	t0:	n
# 	t1:	c 
#	t2:	y
clz:
    addi t0, x0, 32	# n = 32
    addi t1, x0, 16	# c = 16
clz_while:
    srl t2, a0, t1		# y = x >> c
    beq t2, x0, clz_skip
    sub t0, t0, t1		# n -= c
    addi a0, t2, 0 	# x = y
clz_skip:
    srli t1, t1, 1		# c >>= 1
    bnez t1, clz_while # while (c != 0)
clz_ret:
    sub a0, t0, a0	# return n - x
    jr ra

# a0: f1
# t0: mantissa
# t1: exponent
# t2: offset
uf8_decode:
    andi t0, a0, 0x0f    # mantissa = f1 & 0x0f
    srli t1, a0, 4       # exponent = f1 >> 4
    addi t2, x0, 15
    sub t2, t2, t1
    
    addi t3, x0, 0x7F    # replace pseudo instruction li t3, 0x7FFF
    slli t3, t3, 8
    ori t3, t3, 0xFF 

    srl t3, t3, t2
    slli t3, t3, 4
    sll a0, t0, t1
    add a0, a0, t3
    jr ra 

# a0: value
# t0: lz
# t1: msb
# t2: exponent
# t3: overflow
# t4: temp
# t5: mantissa
# t6: next_overflow
uf8_encode:
    addi t4, x0, 16
    blt a0, t4, encode_return_lt16 # if(value < 16) then return value

encode_ge16: 
    addi sp, sp, -8
    sw ra, 0(sp)
    sw s0, 4(sp)
    addi s0, a0, 0 # save value, help us not to access the memory

    jal clz
    addi t0, a0, 0    # lz
    addi t1, x0, 31  
    sub t1, t1, t0    # msb = 31 - lz

    addi t2, x0, 0 # exponent = 0 
    addi t3, x0, 0 # overflow = 0
    addi t4, x0, 5

encode_if_1:
    blt t1, t4,  encode_while_2 # if(msb < 5) goto encode_while_2
    addi t2, t1, -4 # exponent = msb - 4
encode_if_2:
    addi t4, x0, 15 
    ble t2, t4, encode_for_1 # if (exponent <= 15) goto encode_for_1
    addi t2, x0, 15

encode_for_1: 
    addi t4, x0, 1
    sll t4, t4, t2
    addi t4, t4, -1
    slli t4, t4, 4
    addi t3, t4, 0

encode_while_1:
    beq t2, x0, encode_while_2
    bge s0, t3, encode_while_2
    addi t3, t3, -16
    srli t3, t3, 1
    addi t2, t2, -1
    jal x0, encode_while_1

encode_while_2:
    li t4, 15
    bge t2, t4, encode_return
    slli t6, t3, 1
    addi t6, t6, 16

encode_if_3:
    blt s0, t6, encode_return # if(value < nextoverflow) then break
    addi t3, t6, 0
    addi t2, t2, 1
    jal x0, encode_while_2

encode_return:
    sub t5, s0, t3
    srl t5, t5, t2  # mantissa = (value - overflow) >> exponent
    slli a0, t2, 4
    or a0, a0, t5
    lw s0, 4(sp)
    lw ra, 0(sp)
    addi sp, sp, 8
    jr ra    # can be omitted

encode_return_lt16:
    jr ra
```


#### Test cases
In this case, I want to use the test function in the original C code as the test cases.
The test function encodes and decodes 0 to 255 to bf16 format.
And I will encode from 0 to 255 and verify that whether the format is correct.

    All test passed!
    
    Program exited with code: 0

According to the test, the functionality of decode and encode are correct. 
#### Compare to Compiler
Below is the execution info of my RISC-V code.
(Run in 5-stage pipeline CPU)
```
// My approach 1
Cycles:             40004
Instrs. retired:    28164
CPI:                 1.42
IPC:                 0.74
Clock rate:           0Hz
```
And below is the execution info of the compiler(Compiler Explorer -O2)
(Run in 5-stage pipeline CPU)
> GitHub: [q1-uf8-complier.S](https://github.com/dorobouharu133/ca2025-quizzes/blob/main/quiz1_approach/q1-uf8-compiler.S)
```
// Compiler-optimized
Cycles:          106898
Instrs. retired:  73350
CPI:               1.46
IPC:              0.686
Clock rate:   152.73 Hz 
```
**Performance:** Our method is about **2.67x faster** than the compiler's.
**Code Size:** Compared to the compiler-optmized version, my improved approach reduces the code size by nearly **52%**.
___
### ==Approach 2==
> [Quiz 1 Problem B Approach 2](https://github.com/dorobouharu133/ca2025-quizzes/blob/main/quiz1_approach/q1-uf8-approach-2.S)
```asm=
.data
overflow_1: .word 0x10
overflow_2: .word 0x30
overflow_3: .word 0x70
overflow_4: .word 0xF0
overflow_5: .word 0x1F0
overflow_6: .word 0x3F0
overflow_7: .word 0x7F0
overflow_8: .word 0xFF0
overflow_9: .word 0x1FF0
overflow_10: .word 0x3FF0
overflow_11: .word 0x7FF0
overflow_12: .word 0xFFF0
overflow_13: .word 0x1FFF0
overflow_14: .word 0x3FFF0
overflow_15: .word 0x7FFF0
pass_msg: .string "All test passed!"

newline: .string "\n"
.align 2
.text
.globl main

main:
    # li a0, 54372
    lui  a0, 13
    addi a0, a0, 1124
    jal uf8_encode  # call function

    add s0, x0, a0       # save result
    addi a7, x0, 1        # print integer
    addi a0, s0, 0
    ecall

    la a0, newline
    addi a7, x0, 4
    ecall

    addi a7, x0, 10       # exit
    ecall

#	a0: 	x
#	t0:	n
# 	t1:	c 
#	t2:	y
clz:
	addi t0, x0, 32	# n = 32
	addi t1, x0, 16	# c = 16
clz_while:
	srl t2, a0, t1		# y = x >> c
	beq t2, x0, clz_skip
	sub t0, t0, t1		# n -= c
	addi a0, t2, 0 	# x = y
clz_skip:
	srli t1, t1, 1		# c >>= 1
	bnez t1, clz_while # while (c != 0)
clz_ret:
	sub a0, t0, a0	# return n - x
        jr ra

# a0: f1
# t0: mantissa
# t1: exponent
# t2: offset
uf8_decode:
    andi t0, a0, 0x0f    # mantissa = f1 & 0x0f
    srli t1, a0, 4       # exponent = f1 >> 4
    addi t2, x0, 15
    sub t2, t2, t1

    addi t3, x0, 0x7F    
    slli t3, t3, 8
    ori t3, t3, 0xFF 

    srl t3, t3, t2
    slli t3, t3, 4
    sll a0, t0, t1
    add a0, a0, t3
    jr ra

# a0: value
# t0: lz
# t1: msb
# t2: exponent
# t3: overflow
# t4: temp
# t5: mantissa
# t6: next_overflow
uf8_encode:
    addi t4, x0, 16
    blt a0, t4, encode_return_lt16 # if(value < 16) return value

encode_ge16: # function call, need to save ra, a0
    addi sp, sp, -8
    sw ra, 0(sp)
    sw s0, 4(sp)
    addi s0, a0, 0 # save value

    jal clz
    addi t0, a0, 0    # lz
    addi t1, x0, 31  
    sub t1, t1, t0     # msb = 31 - lz

    addi t2, x0, 0 # exponent = 0 
    addi t3, x0, 0 # overflow = 0
    addi t4, x0, 5

encode_if_1:
    blt t1, t4,  encode_while_2 # if(msb < 5) goto encode_while_2
    addi t2, t1, -4 # exponent = msb - 4
encode_if_2:
    addi t4, x0, 15 
    ble t2, t4, encode_for_1 # if (exponent <= 15) goto encode_for_1
    addi t2, x0, 15

encode_overflow:   # calculate overflow using memory lookup
    la, t3, overflow_1   # t3 = base address of table
    addi t4, t2, -1      # t4 = exponent - 1
    slli t4, t4, 2       
    add t3, t3, t4       # t3 = &overflow_{exponent}
    lw t3, 0(t3)         # t3 = overflow


encode_while_1: # adjust exponent # need to be optimized
    beq t2, x0, encode_while_2
    slt t4, s0, t3 # t4 = (value < overflow)
    beq t4, x0, encode_while_2
    addi t3, t3, -16
    srli t3, t3, 1
    addi t2, t2, -1
    jal x0, encode_while_1

    
encode_while_2: # optimize later # find exact exponent
    addi t4, x0, 15
    bge t2, t4, encode_return
    slli t6, t3, 1
    addi t6, t6, 16
encode_if_3:
    blt s0, t6, encode_return
    addi t3, t6, 0
    addi t2, t2, 1
    jal x0,  encode_while_2
encode_return:   

    sub t5, s0, t3
    srl t5, t5, t2 # mantissa = (value - overflow) >> exponent
    slli a0, t2, 4 
    or a0, a0, t5

    lw s0, 4(sp)
    lw ra, 0(sp)
    addi sp, sp, 8    # restore stack 
    jr ra

encode_return_lt16:
    jr ra
```
In my approach 2, I used lookup table to accelerate the procedure. As we had discussed in my approach 1, the overflow has some pattern in the for loop, thus we can put all patterns into memory, and we can quickly get the overflow.

```asm=
encode_overflow:   # calculate overflow using memory lookup
    la t3, overflow_1 # t3 = base address of table
    addi t4, t2, -1      # t4 = exponent - 1
    slli t4, t4, 2       
    add t3, t3, t4       # t3 = &overflow_{exponent}
    lw t3, 0(t3)         # t3 = overflow
```
As we do in the first approach, the overflow can be calculated by exponent bits leading 1's and fixed 4 bits 0's. So we access the memory table with the offset of the number of leading 1's.
```asm=
.data
overflow_1: .word 0x10
overflow_2: .word 0x30
overflow_3: .word 0x70
overflow_4: .word 0xF0
overflow_5: .word 0x1F0
overflow_6: .word 0x3F0
overflow_7: .word 0x7F0
overflow_8: .word 0xFF0
overflow_9: .word 0x1FF0
overflow_10: .word 0x3FF0
overflow_11: .word 0x7FF0
overflow_12: .word 0xFFF0
overflow_13: .word 0x1FFF0
overflow_14: .word 0x3FFF0
overflow_15: .word 0x7FFF0
```
Above is the lookup table, I list overflow in accending order. 
#### Test Cases
    All tests passed!
    
    Program exited with code: 0
My approach 2 passes the test too.
#### Compare to compiler
The below figure is the execution info of my approach2.
(Run in 5-stage pipeline CPU)
```
// My approach 2
Cycles:             40486
Instrs. retired:    28628
CPI:                 1.41
IPC:                0.707
Clock rate:           0Hz
```
**Performance:** My approach 2 is about **2.64x faser** than the compiler-optimized version.
**Code Size:** Compared to the compiler-optmized version, my approach 2 reduces the code size by nearly **42%**.
According to the clock cycles, the approach 2 is slower than the approach 1 slightly. But I think this is a good try for me to come up with the lookup table method, even though it does't perform better than my approach 1.

---
## Problem C
### ==bf16_sqrt==
> GitHub: [bf16_sqrt](https://github.com/dorobouharu133/ca2025-quizzes/tree/main/bf16_sqrt)

> Because the `mul` instruction is not included in the [RV32I instructions](https://docs.riscv.org/reference/isa/unpriv/rv32.html), I build up the architecture of the RISC-V code with the `mul` instruction, and I will develop some way to replace the `mul` instruction.
> I translate the C code to RISC-V code line-by-line first, and use `mul`. In the following steps, I will optimize the RISC-V code.
#### bf16_sqrt_with_mul
> GitHub: [bf16_sqrt_original.S](https://github.com/dorobouharu133/ca2025-quizzes/blob/8052ba042ba0f1216df9d70e5d97e2f7e00ebeb1/bf16_sqrt.S)
```asm=
.data
newline: .string "\n"
pass_msg: .string "bf16_sqrt All tests passed!"
fail_msg: .string "Tests failed!"
.text
.globl bf16_sqrt
.globl __mulsi3
.globl main

main:
# sqrt(+inf) = +inf
test_1:
    addi a0, x0, 0x7F
    slli a0, a0, 8
    ori a0, a0, 0x80
    jal ra, bf16_sqrt   

    addi s0, a0, 0
    addi t0, x0, 0x7F
    slli t0, t0, 8
    ori t0, t0, 0x80
    bne s0, t0, test_failed

# sqrt(NaN) = NaN
test_2:
    addi a0, x0, 0x7F
    slli a0, a0, 8
    ori a0, a0, 0xC0	
    jal ra, bf16_sqrt   

    addi s0, a0, 0
    addi t0, x0, 0x7F
    slli t0, t0, 8
    ori t0, t0, 0xC0
    bne s0, t0, test_failed

# sqrt(-1.000000) = NaN
test_3:
    addi a0, x0, 0xBF
    slli a0, a0, 8
    ori a0, a0, 0x80	
    jal ra, bf16_sqrt   

    addi s0, a0, 0
    addi t0, x0, 0x7F
    slli t0, t0, 8
    ori t0, t0, 0xC0
    bne s0, t0, test_failed

# sqrt(2.000000) = 1.414062
test_4:
    addi a0, x0, 0x40
    slli a0, a0, 8
    jal ra, bf16_sqrt   

    addi s0, a0, 0
    addi t0, x0, 0x3F
    slli t0, t0, 8
    ori t0, t0, 0xB5
    bne s0, t0, test_failed

# sqrt(1.000000) = 1.000000
test_5:
    addi a0, x0, 0x3F
    slli a0, a0, 8
    ori a0, a0, 0x80
    jal ra, bf16_sqrt
    addi t0, x0, 0x3F
    slli t0, t0, 8
    ori t0, t0, 0x80
    bne a0, t0, test_failed

# sqrt(0.000000) = 0.000000
test_6:
    addi a0, x0, 0
    jal ra, bf16_sqrt
    addi t0, x0, 0x0000
    bne a0, t0, test_failed

# sqrt(2648071397852762090550553127902248960.000000) = 1630303065108119552.000000
test_7:
    addi a0, x0, 0x7B
    slli a0, a0, 8
    ori a0, a0, 0xFF      
    jal ra, bf16_sqrt
    addi t0, x0, 0x5D
    slli t0, t0, 8
    ori t0, t0, 0xB5       
    bne a0, t0, test_failed

test_passed:
    la a0, pass_msg
    addi a7, x0, 4            
    ecall
    jal x0, end
test_failed:
    la a0, fail_msg
    addi a7, x0, 4            
    ecall
end:
    la a0, newline
    addi a7, x0, 4            
    ecall

    addi a7, x0, 10        
    ecall
 
# a0: a
# t0: sign
# t1: exp 
# t2: mant 
# t3: temp
# t4: e
# t5: m
# t6: new_exp
# s0: low
# s1: high
# s2: result
# s3: mid
# s4: sq
# s5: new_mant

bf16_sqrt:
    srli t0, a0, 15
    srli t1, a0, 7
    andi t1, t1, 0xFF 	# exp = (a.bits >> 7) & 0xFF
    andi t2, a0, 0x7F	# mant = a.bits & 0x7F 

sqrt_special_case:
    addi t3, x0, 0xFF
    bne t1, t3, sqrt_skip_1 # if(exp != 0xFF) then goto sqrt_skip_1
    bne t2, x0, sqrt_return_a
    bne t0, x0, sqrt_return_bf16_nan
    jal x0, sqrt_return_a

sqrt_skip_1:
    bne t1, x0, sqrt_skip_2
    beq t2, x0, sqrt_return_bf16_zero

sqrt_skip_2:
    bne t0, x0, sqrt_return_bf16_nan

sqrt_skip_3:    
    beq t1, x0, sqrt_return_bf16_zero

    addi t4, t1, -127 	# e = exp - BF16_EXP_BIAS
    ori t5, t2, 0x80 	# m = 0x80 | mant

adjust_for_odd_exponents_if:
    andi t3, t4, 1
    beq t3, x0, adjust_for_odd_exponents_else
    slli t5, t5, 1
    addi t3, t4, -1 # t4 = (e - 1)
    srli t3, t3, 1
    addi t6, t3, 127 # new_exp = ((e-1) >> 1) + BF16_EXP_BIAS
    beq x0, x0, sqrt_binary_search_initialize

adjust_for_odd_exponents_else:
    srli t3, t4, 1
    addi t6, t3, 127

sqrt_binary_search_initialize:
    addi s0, x0, 90	# low = 90
    addi s1, x0, 256 # high = 256
    addi s2, x0, 128 # result = 128

sqrt_while_loop: # binary_search
    bgt s0, s1, sqrt_normalize_greater_equal
    add s3, s0, s1 # s3 = (low + high)
    srli s3, s3, 1 # mid = (low + high) >> 1

sqrt_mul: ## mul is not allowed, need to be modified !!
    # s4: sq
    # mid*mid implement
    mul s4, s3, s3 # sq = mid * mid, need to be replaced
    srli s4, s4, 7    

sqrt_while_loop_if:
    bgt s4, t5, sqrt_while_loop_else
    addi s2, s3, 0 # result = mid
    addi s0, s3, 1 # low = mid + 1
    jal x0, sqrt_while_loop

sqrt_while_loop_else:
    addi s1, s3, -1 # high = mid - 1
    jal x0, sqrt_while_loop 

sqrt_normalize_greater_equal: # branchless
    addi t3, x0, 256
    sltu t3, s2, t3 # t3 = (result < 256) ? 1 : 0
    xori t3, t3, 1 # t3 = (t3) ? 0 : 1, reverse t3
    srl s2, s2, t3
    add t6, t6, t3 # t6: new_exp
    jal x0, sqrt_normalize_done

sqrt_normalize_less: 
    addi s6, x0, 128

sqrt_normalize_less_loop:    
    bge s2, s6, sqrt_normalize_done
    addi t3, x0, 1
    ble t6, t3, sqrt_normalize_done
    slli s2, s2, 1
    addi t6, t6, -1
    jal x0, sqrt_normalize_less_loop

sqrt_normalize_done:
    andi s5, s2, 0x7F # new_mant = result & 0x7F, use t2 to store new_mant

    addi t3, x0, 0xFF
    bge t6, t3, sqrt_return_pInf
    ble t6, x0, sqrt_return_bf16_zero
    andi t3, t6, 0xFF
    slli t3, t3, 7
    or a0, t3, s5 # .bits = (new_exp & 0xFF) << 7 | new_mant
    jr ra

sqrt_return_a:
    jr ra

sqrt_return_bf16_nan:
    li a0, 0x7FC0
    jr ra

sqrt_return_bf16_zero:
    andi a0, x0, 0
    jr ra

sqrt_return_pInf:
    addi a0, x0, 0x7F
    slli a0, a0, 8
    ori  a0, a0, 0x80
    jr ra
```
                                                
> **Note**: The code above serves as a **baseline** for implementing multiplication without the `mul` instruction.

#### bf16_sqrt Test Cases
Using the `mul` instruction, I want to verify whether the functionality of my approach is correct or not first.
Let's choose some corner cases as the test cases first.
```
1. sqrt(`0x7F80`) = `0x7F80`, sqrt(+inf) = +inf
2. sqrt(`0x7FC0`) = `0x7FC0`, sqrt(NaN) = NaN
3. sqrt(`0xBF80`) = `0x7FC0`, sqrt(-1.000000) = NaN
4. sqrt(`0x4000`) = `0x3FB5`, sqrt(2.000000) = 1.414062
5. sqrt(`0x3F80`) = `0x3F80`, sqrt(1.000000) = 1.000000
6. sqrt(`0x0000`) = `0x0000`, sqrt(0.000000) = 0.000000
7. sqrt(`0x7BFF`) = `0x5DB5`, sqrt(2648071397852762090550553127902248960.000000) = 1630303065108119552.000000
```
(Run in 5-stage pipeline CPU)
> GitHub: [bf16_sqrt_original.S](https://github.com/dorobouharu133/ca2025-quizzes/blob/8052ba042ba0f1216df9d70e5d97e2f7e00ebeb1/bf16_sqrt.S)
```
// My original approach for bf16_sqrt
Cycles:             555
Instrs. retired:    403
CPI:               1.38
IPC:              0.726
Clock rate:   584.21 Hz
```
___
#### ==bf16_sqrt_shift_add==
The next step to develop an alternative method to replace the `mul` instruction in the `bf16_sqrt_with_mul` function. 

A common approach is to manually implement multiplication, which we can motivate by revisting the classic [**long multiplication**](https://mathworld.wolfram.com/LongMultiplication.html).

The [**Shift-and-Add Multiplication**](https://users.utcluj.ro/%7Ebaruch/book_ssce/SSCE-Shift-Mult.pdf) method provides a strightforward way to realize the concept of [**long multiplication**](https://mathworld.wolfram.com/LongMultiplication.html) in software.

We can use a simple binary multiplication example to illustrate how the shift-and-add method is implemented.

For example, `0x81` $\times$ `0xC3` $=$ `0x6243` ($129 \times 195 = 25{,}155$).
In binary `1000 0001`(Multiplicand) $\times$ `1100 0011` (Multiplier) $=$ `110001001000011`.
```
              1000 0001  <- Multiplicand
          x   1100 0011  <- Multiplier
-------------------------------------------
pass0:        1000 0001    (Multiplier bit 0 is 1: Add)
pass1:       1000 0001     (Multiplier bit 1 is 1: Add)
pass2:      0000 0000      (Multiplier bit 2 is 0: Skip)
pass3:     0000 0000       (Multiplier bit 3 is 0: Skip)
pass4:    0000 0000        (Multiplier bit 4 is 0: Skip)
pass5:   0000 0000         (Multiplier bit 5 is 0: Skip)
pass6:  1000 0001          (Multiplier bit 6 is 1: Add)
pass7: 1000 0001           (Multiplier bit 7 is 1: Add) 
-------------------------------------------
Result:1100 0100 100 0011  (0x6243)
```
**Algorithm Logic**:
In each pass, we examine the **LSB** of the **Multiplier**:
- If bit 0 is 1, add the current Multiplicand to the partial product.
- If bit 0 is 0, skip the addition.

After each pass, we **shift the Multiplicand 1 bit to the left** and **shift the Multiplier 1 bit  to the right**. This allows us to consistently check the LSB of the Multiplier in every iteration.
The process continues until the Multiplier becomes zero.

I implement the **shift-and-add** logic as the below code:
```asm=
# a0: multiplicand
# a1: multiplier
# t0: accumulator
# t1: multiplier_copy
# t2: bit0

shift_and_add:
    # save stack if needed
    addi t0, x0, 0
    addi t1, a1, 0
    andi t2, a1, 1

shift_and_add_for_loop:
    andi t2, t1, 1
    beq t2, x0, shift_and_add_for_skip_add
    add t0, t0, a0
    
shift_and_add_for_skip_add:    
    slli a0, a0, 1
    srli t1, t1, 1
    bne t1, x0, shift_and_add_for_loop

shfit_and_add_end:
    # restore stack if needed
    addi a0, t0, 0
    jr ra 
```

And I implement a test to verify the correctness of the algorithm.
    
```asm=
.data
newline: .string "\n"
pass_msg: .string "SHIFT-AND-ADD implementation successful!"
fail_msg: .string "SHIFT-AND-ADD implementation failed!"
.text
.global shift_and_add
.global main

main:
    addi a0, x0, 0x80
    addi a1, x0, 0xC0
    jal ra, shift_and_add

    addi s0, a0, 0
    addi t0, x0, 0x60
    slli t0, t0, 8
    bne s0, t0, test_failed

test_passed:
    la a0, pass_msg
    addi a7, x0, 4            
    ecall
    jal x0, end

test_failed:
    la a0, fail_msg
    addi a7, x0, 4            
    ecall

end:
    la a0, newline
    addi a7, x0, 4            
    ecall

    addi a7, x0, 10        
    ecall
 
# a0: multiplicand
# a1: multiplier
# t0: accumulator
# t1: multiplier_copy
# t2: bit0

shift_and_add:
    # save stack if needed
    addi t0, x0, 0
    addi t1, a1, 0
    andi t2, a1, 1

shift_and_add_for_loop:
    andi t2, t1, 1
    beq t2, x0, shift_and_add_for_skip_add
    add t0, t0, a0

shift_and_add_for_skip_add:    
    slli a0, a0, 1
    srli t1, t1, 1
    bne t1, x0, shift_and_add_for_loop

shfit_and_add_end:
    # restore stack if needed
    addi a0, t0, 0
    jr ra    
```

    SHIFT-AND-ADD implementation successful!

We can now replace the `mul` instruction in the original code (note that the code must be modified to save and restore the stack).
> GitHub: [bf16_sqrt.S](https://github.com/dorobouharu133/ca2025-quizzes/blob/7e584d6ae8203d226c6e8bb119ce17bd55b7bdeb/bf16_sqrt.S)
```asm=
.data
newline: .string "\n"
pass_msg: .string "All tests passed!"
fail_msg: .string "Tests failed!"
.text
.global bf16_sqrt
.global main

main:
# sqrt(+inf) = +inf
test_1:
    addi a0, x0, 0x7F
    slli a0, a0, 8
    ori a0, a0, 0x80
    jal ra, bf16_sqrt   

    addi s0, a0, 0
    addi t0, x0, 0x7F
    slli t0, t0, 8
    ori t0, t0, 0x80
    bne s0, t0, test_failed

# sqrt(NaN) = NaN
test_2:
    addi a0, x0, 0x7F
    slli a0, a0, 8
    ori a0, a0, 0xC0	
    jal ra, bf16_sqrt   

    addi s0, a0, 0
    addi t0, x0, 0x7F
    slli t0, t0, 8
    ori t0, t0, 0xC0
    bne s0, t0, test_failed

# sqrt(-1.000000) = NaN
test_3:
    addi a0, x0, 0xBF
    slli a0, a0, 8
    ori a0, a0, 0x80	
    jal ra, bf16_sqrt   

    addi s0, a0, 0
    addi t0, x0, 0x7F
    slli t0, t0, 8
    ori t0, t0, 0xC0
    bne s0, t0, test_failed

# sqrt(2.000000) = 1.414062
test_4:
    addi a0, x0, 0x40
    slli a0, a0, 8
    jal ra, bf16_sqrt   

    addi s0, a0, 0
    addi t0, x0, 0x3F
    slli t0, t0, 8
    ori t0, t0, 0xB5
    bne s0, t0, test_failed

# sqrt(1.000000) = 1.000000
test_5:
    addi a0, x0, 0x3F
    slli a0, a0, 8
    ori a0, a0, 0x80
    jal ra, bf16_sqrt
    addi t0, x0, 0x3F
    slli t0, t0, 8
    ori t0, t0, 0x80
    bne a0, t0, test_failed

# sqrt(0.000000) = 0.000000
test_6:
    addi a0, x0, 0
    jal ra, bf16_sqrt
    addi t0, x0, 0x0000
    bne a0, t0, test_failed

# sqrt(2648071397852762090550553127902248960.000000) = 1630303065108119552.000000
test_7:
    addi a0, x0, 0x7B
    slli a0, a0, 8
    ori a0, a0, 0xFF      
    jal ra, bf16_sqrt
    addi t0, x0, 0x5D
    slli t0, t0, 8
    ori t0, t0, 0xB5       
    bne a0, t0, test_failed

test_passed:
    la a0, pass_msg
    la a0, pass_msg
    addi a7, x0, 4            
    ecall
    jal x0, end

test_failed:
    la a0, fail_msg
    addi a7, x0, 4            
    ecall

end:
    la a0, newline
    addi a7, x0, 4            
    ecall

    addi a7, x0, 10        
    ecall
 
# a0: a
# t0: sign
# t1: exp 
# t2: mant 
# t3: temp
# t4: e
# t5: m
# t6: new_exp
# s0: low
# s1: high
# s2: result
# s3: mid
# s4: sq
# s5: new_mant

bf16_sqrt:
    srli t0, a0, 15
    srli t1, a0, 7
    andi t1, t1, 0xFF 	# exp = (a.bits >> 7) & 0xFF
    andi t2, a0, 0x7F	# mant = a.bits & 0x7F 

sqrt_special_case:
    addi t3, x0, 0xFF
    bne t1, t3, sqrt_skip_1 # if(exp != 0xFF) then goto sqrt_skip_1
    bne t2, x0, sqrt_return_a
    bne t0, x0, sqrt_return_bf16_nan
    jal x0, sqrt_return_a

sqrt_skip_1:
    bne t1, x0, sqrt_skip_2
    beq t2, x0, sqrt_return_bf16_zero

sqrt_skip_2:
    bne t0, x0, sqrt_return_bf16_nan

sqrt_skip_3:    
    beq t1, x0, sqrt_return_bf16_zero

    addi t4, t1, -127 	# e = exp - BF16_EXP_BIAS
    ori t5, t2, 0x80 	# m = 0x80 | mant

adjust_for_odd_exponents_if:
    andi t3, t4, 1
    beq t3, x0, adjust_for_odd_exponents_else
    slli t5, t5, 1
    addi t3, t4, -1 # t4 = (e - 1)
    srli t3, t3, 1
    addi t6, t3, 127 # new_exp = ((e-1) >> 1) + BF16_EXP_BIAS
    beq x0, x0, sqrt_binary_search_initialize

adjust_for_odd_exponents_else:
    srli t3, t4, 1
    addi t6, t3, 127

sqrt_binary_search_initialize:
    addi s0, x0, 90	# low = 90
    addi s1, x0, 256 # high = 256
    addi s2, x0, 128 # result = 128

sqrt_while_loop: # binary_search
    bgt s0, s1, sqrt_normalize_greater_equal
    add s3, s0, s1 # s3 = (low + high)
    srli s3, s3, 1 # mid = (low + high) >> 1

sqrt_mul: # SHIFT-AND-ADD
    # s4: sq
    # mid*mid implemented by shift-and-add
    addi sp, sp, -12
    sw ra, 0(sp)
    sw a0, 4(sp)
    sw a1, 8(sp)
    
    addi a0, s3, 0
    addi a1, s3, 0
    jal ra, shift_and_add
    addi a3, a0, 0
    
    lw ra, 0(sp)
    lw a0, 4(sp)
    lw a1, 8(sp)
    addi sp, sp, 12
    addi s4, a3, 0
    srli s4, s4, 7    
    
sqrt_while_loop_if:
    bgt s4, t5, sqrt_while_loop_else
    addi s2, s3, 0 # result = mid
    addi s0, s3, 1 # low = mid + 1
    jal x0, sqrt_while_loop

sqrt_while_loop_else:
    addi s1, s3, -1 # high = mid - 1
    jal x0, sqrt_while_loop 

sqrt_normalize_greater_equal: # branchless
    addi t3, x0, 256
    sltu t3, s2, t3 # t3 = (result < 256) ? 1 : 0
    xori t3, t3, 1 # t3 = (t3) ? 0 : 1, reverse t3
    srl s2, s2, t3
    add t6, t6, t3 # t6: new_exp
    jal x0, sqrt_normalize_done

sqrt_normalize_less:
    addi s6, x0, 128

sqrt_normalize_less_loop:    
    bge s2, s6, sqrt_normalize_done
    addi t3, x0, 1
    ble t6, t3, sqrt_normalize_done
    slli s2, s2, 1
    addi t6, t6, -1
    jal x0, sqrt_normalize_less_loop
    
sqrt_normalize_done:
    andi s5, s2, 0x7F # new_mant = result & 0x7F, use t2 to store new_mant
    
    addi t3, x0, 0xFF
    bge t6, t3, sqrt_return_pInf
    ble t6, x0, sqrt_return_bf16_zero
    andi t3, t6, 0xFF
    slli t3, t3, 7
    or a0, t3, s5 # .bits = (new_exp & 0xFF) << 7 | new_mant
    jr ra

sqrt_return_a:
    jr ra

sqrt_return_bf16_nan:
    li a0, 0x7FC0
    jr ra

sqrt_return_bf16_zero:
    andi a0, x0, 0
    jr ra

sqrt_return_pInf:
    addi a0, x0, 0x7F
    slli a0, a0, 8
    ori  a0, a0, 0x80
    jr ra

# a0: multiplicand
# a1: multiplier
# t0: accumulator
# t1: multiplier_copy
# t2: bit0

shift_and_add:
    addi sp, sp, -12
    sw t0, 0(sp)
    sw t1, 4(sp)
    sw t2, 8(sp)
    
    addi t0, x0, 0
    addi t1, a1, 0
    andi t2, a1, 1

shift_and_add_for_loop:
    andi t2, t1, 1
    beq t2, x0, shift_and_add_for_skip_add
    add t0, t0, a0
    
shift_and_add_for_skip_add:    
    slli a0, a0, 1
    srli t1, t1, 1
    bne t1, x0, shift_and_add_for_loop

shfit_and_add_end:
    addi a1, t0, 0
    lw t0, 0(sp)
    lw t1, 4(sp)
    lw t2, 8(sp)
    addi sp, sp, 12
    addi a0, a1, 0
    jr ra 
```
#### bf16_sqrt Test Cases
(Run in 5-stage pipeline CPU)
> GitHub: [bf16_sqrt_test.S](https://github.com/dorobouharu133/ca2025-quizzes/blob/main/bf16_sqrt/bf16_sqrt_test.S)
```
// My improved approach for bf16_sqrt
Cycles:             2726
Instrs. retired:    2008
CPI:                1.36
IPC:               0.737
Clock rate:    259.26 Hz
```
> GitHub: [bf16_sqrt_compiler.S](https://github.com/dorobouharu133/ca2025-quizzes/blob/main/bf16_sqrt/bf16_sqrt_compiler.S)
```
// bf16_sqrt compiler version
Cycles:             3315
Instrs. retired:    2278
CPI:                1.46
IPC:               0.687
Clock rate:     7.37 KHz
```
**Performance:** My improved approach is **1.21x faster** than the compiler-optimized version.
**Code Size:** Compared to the compiler-optimized version, my improved approach reduces the code size by nearly **39%**.
While shift-and-add is an alternative to the mul instruction, its performance is significantly lower; it is approximately **5.1x slower** than the native hardware approach.

___
### ==bf16_add==
> GitHub: [bf16_add](https://github.com/dorobouharu133/ca2025-quizzes/tree/main/bf16_add)

The following code is the initial template for my **bf16_add** implementation. I will introduce the optimized version and provide the details in the next section.

#### [bf16_add_original code](https://github.com/dorobouharu133/ca2025-quizzes/blob/main/bf16_add/bf16_add_original.S)
The link above is the implementation of my original approach.

#### bf16_add Test Cases
```
1. `0x3F80` + `0xBF80`, +1.000000 + (-1.000000) = 0.000000
2. `0x7F7F` + `0x7F7F`, maximum finite positive number + minimal normalized number = +inf
3. `0x3F80` + `0x3B80`, 1.0000000 + 2^-8 = 1.000000
4. `0x7F80` + `0xFF80`, inf + (-inf) = NaN
```
> GitHub: [bf16_add_original.S](https://github.com/dorobouharu133/ca2025-quizzes/blob/main/bf16_add/bf16_add_original.S)
(Run in 5-stage pipeline CPU)
```
// My original approach for bf16_add
Cycles:              247
Instrs. retired:     189
CPI:                1.31
IPC:               0.765
Clock rate:    228.28 Hz
```
The above figure is the execution info of my approach, and the below is the execution info of compiler.
(Run in 5-stage pipeline CPU)
> GitHub: [bf16_add_compiler.S](https://github.com/dorobouharu133/ca2025-quizzes/blob/main/bf16_add/bf16_add_compiler.S)
```
// Compiler-optmized bf16_add
Cycles:                259    
Instrs. retired:       207 
CPI:                  1.25 
IPC:                 0.799
Clock rate:      254.92 Hz
```
My original approach is about **1.049x faster** than the compiler-optimized version (**o2-optimized**).


#### bf16_add_improved
**Observation:** This section implements the **alignment** logic.
```c=
    if (exp_diff > 0) {
        result_exp = exp_a;
        if (exp_diff > 8)
            return a;
        mant_b >>= exp_diff;
    } else if (exp_diff < 0) {
        result_exp = exp_b;
        if (exp_diff < -8)
            return b;
        mant_a >>= -exp_diff;
    } else {
        result_exp = exp_a;
    }
```
In floating-point addition, numbers with different exponents cannot be summed directly. For example, to add $3.0 \times 10^{4}$ and $1.5 \times 10^{2}$, we cannot simply add the mantissas ($3.0 + 1.5$). The **exponents** must be aligned first.
    
1. **Alignment Process:** The number with the smaller exponent is adjusted to match the larger exponent. 

$$
1.5 \times 10^{2} \to 0.15 \times 10^{3} \to 0.015 \times 10^{4}
$$
    
2. **Addition:** Now, we can sum the two numbers: 
$$
3.0 \times 10^{4} + 0.015 \times 10^{4} = (3.0 + 0.015) \times 10^{4} = 3.015 \times 10^{4}
$$
    
> **Note:** After addition, it is necessary to check whether normalization is requried or not. In this case, the result is already normalized, so no further adjustment is needed.
    
I implement a **branchless swap** to ensure that the **magnitude of operand A** is always greater than or equal to that of **operand B** (i.e., $|A| \ge |B|$).
    
And I explain how to use branchless logic to implement swap A and B.

Since we want to let $|A|$ is always larger or equal to $|B|$, therefore we only care about the magnitude, and the `result_exp` can be determind later.
First step is to get the absolute value, we can achieve this by using a mask.
```asm=
    addi t0, x0, 0x7F
    slli t0, t0, 8
    ori t0, t0, 0xFF # mask = 0x7F00
```
Because `0x7F00` = `0111 1111 1111 1111` in binary, we can clear the sign bit of a and b.
Implemented in my code as below:
```asm=
bf16_add_align_branchless:
    # a0: a
    # a1: b
    # s0: unsigned_a
    # s1: unsigned_b
    # t6: temp, used as mask
    addi t6, x0, 0x7F
    slli t6, t6, 8 
    ori t6, t6, 0xFF # mask = 0x7FFF

    andi s0, a0, 0x7FFF # unsigned_a = a.bits & mask
    andi s1, a1, 0x7FFF # unsigned_b = b.bits & mask
    slt t6, s0, s1 # t6 = (|A| < |B|) ? 1 : 0
    sub t6, x0, t6 # t6 = (|A| < |B|) ? 0xFFFF : 0x0
```
Here we can get `t6` as a mask:
- if $|A| < |B|$, then t6 = `0xFFFF`. (**Need to swap**)
- if $|A| >= |B|$, then t6 = `0x0000`. (**No need to swap**)

Then ths mask (t6) can be used to swap sign, exponent and mantissa simutaneously.
I explain the principle of using xor to swap, and below are the properties of xor oepration:
$$
\begin{aligned}
A \oplus 0 &= A && \\
(A \oplus B) \oplus A &= B && 
\end{aligned}
$$
$$
\begin{aligned}
\text{If} \quad & C = A \oplus B \\
\text{then} \quad & C \oplus A = B \\
\text{and} \quad & C \oplus B = A
\end{aligned}
$$

`and s0, s0, t6` is used to determine whether swap or not.


if $\text{C} = \text{A} \oplus \text{B}$, then
- $\text{C} \oplus \text{0x0000} = \text{C}$ 
- and $\text{C} \oplus \text{0xFFFF}$ = the 1's complement of $\text{C}$

> **Note:**  A, B, C here are all 16-bit binary numbers.

```asm=
    # Swap sign bit
    # t0: sign_a
    # t1: sign_b
    # t6: mask (0xFFFF or 0x0000)
    # s0: sign_a ^ sign_b
    xor s0, t0, t1 # s0 = sign_a ^ sign_b
    and s0, s0, t6 # use mask to check swap or not
    xor t0, t0, s0
    xor t1, t1, s0
```
For example, mask (t6) is `0xFFFF`, exp_a (t0) = `0x1001`, exp_b (t1) = `0x1011`. 
> Note: tha if mask is `0xFFFF`,i.e, need to swap, exp_a should less than exp_b.
```
s0 = 0x1001 ^ 0x1011 = 0x0010
s0 & t6 = 0x0010 & 0xFFFF = 0x0010

t0 ^ 0x0010 = 0x1001 ^ 0x0010 = 0x1011
t1 ^ 0x0010 = 0x1011 ^ 0x0010 = 0x1001
```
And another example, mask is `0x0000`, which means that there is no need to swap, and exp_a = `0x1100` and exp_b = `0x0011`.
```
s0 = 0x1100 ^ 0x0011 = 0x1111
s0 & t6 = 0x1111 & 0x0000 = 0x0000

t0 ^ 0x0000 = 0x1100 ^ 0x0000 = 0x1100
t1 ^ 0x0000 = 0x0011 ^ 0x0000 = 0x0011
```
Repeat the above procedure three times to implement branchless swap.
Below is the complete code of branchless swap implementation:
```asm=
bf16_add_align_branchless:
    # a0: a
    # a1: b
    # s0: unsigned_a
    # s1: unsigned_b
    # t6: temp, used as mask
    addi t6, x0, 0x7F
    slli t6, t6, 8 
    ori t6, t6, 0xFF # mask = 0x7FFF

    andi s0, a0, t6 # unsigned_a = a.bits & mask
    andi s1, a1, t6 # unsigned_b = b.bits & mask
    slt t6, s0, s1 # t6 = (|A| < |B|) ? 1 : 0
    sub t6, x0, t6 # t6 = (|A| < |B|) ? 0xFFFF : 0x0
    
bf16_add_branchless_swap_sign:
    # swap sign bit
    # t0: sign_a
    # t1: sign_b
    # t6: mask (0xFFFF or 0x0000)
    # s0: sign_a ^ sign_b
    xor s0, t0, t1 # s0 = sign_a ^ sign_b
    and s0, s0, t6 # use mask to check swap or not
    xor t0, t0, s0
    xor t1, t1, s0

bf16_add_branchless_swap_exponent:
    # swap exponent
    # t2: exp_a
    # t3: exp_b
    # t6: mask (0xFFFF or 0x0000)
    # s0: exp_a ^ exp_b
    xor s0, t2, t3 # s0 = exp_a ^ exp_b
    and s0, s0, t6
    xor t2, t2, s0
    xor t3, t3, s0
    
bf16_add_branchless_swap_mantissa:
    # swap mantissa
    # t4: mant_a
    # t5: mant_b
    # t6: mask (0xFFFF or 0x0000)
    # s0: mant_a ^ mant_b
    xor s0, t4, t5 # s0 = mant_a ^ mant_b
    and s0, s0, t6
    xor t4, t4, s0
    xor t5, t5, s0
```

We have to determine `exp_diff` and align the smaller part (i.e., `mant_b`) in the remaining part.
```c=
    int16_t exp_diff = exp_a - exp_b;
    uint16_t result_sign;
    int16_t result_exp;
    uint32_t result_mant;

    if (exp_diff > 0) {
        result_exp = exp_a;
        if (exp_diff > 8)
            return a;
        mant_b >>= exp_diff;
    } else if (exp_diff < 0) {
        result_exp = exp_b;
        if (exp_diff < -8)
            return b;
        mant_a >>= -exp_diff;
    } else {
        result_exp = exp_a;
    }
```
We also want to convert to above code into branchless logic, because the `exp_a` and `mant_a` are always larger than or euqal to the corresponding parts, we can **ignore** the part that deal with `exp_a` and `mant_a`.
The above code can be simplified as below:
```c=
    int16_t exp_diff = exp_a - exp_b;
    uint16_t result_sign;
    int16_t result_exp;
    uint32_t result_mant;
    
    if(exp_diff > 0) {
        result_exp = exp_a;
        if (exp_diff > 8)
            return a;
        mant_b >>= exp_diff;
    } else if (exp_diff == 0) {
        result_exp = exp_a;
    }
```

> **Note:** `exp_diff` = `exp_a` - `exp_b` $\ge$ 0.

We can use `srl` instruction to alignment `mant_b`, and
- if exp_diff > 8, then return a.
- else if 0 <= exp_diff and 8 >= exp_diff, retain `mant_b`.
> **Note:** `exp_diff` > 8 means that b is negligible relative to a, thus mant_b can be zeroed out by the mask.

```asm=
    # s3: exp_diff
    # t6: mask
    sub s3, t2, t3 # exp_diff = exp_a - exp_b
    
    addi t6, x0, 8
    slt t6, t6, s3
    sub t6, x0, t6 # t6 = (8 < exp_diff) ? 0xFFFFFFFF : 0x00000000
    xori t6, t6, -1 # t6 = (8 < exp_diff) ? 0x00000000 : 0xFFFFFFFF
    
    # align mant_b
    sra t5, t5, s3 # mant_b >>= exp_diff
    and t5, t5, t6 # mant_b &= ~mask
```
**Observation:** Logic Simplification

```c=
else {
        if (mant_a >= mant_b) {
            result_sign = sign_a;
            result_mant = mant_a - mant_b;
        } else {
            result_sign = sign_b;
            result_mant = mant_b - mant_a;
        }

        if (!result_mant)
            return BF16_ZERO();
        while (!(result_mant & 0x80)) {
            result_mant <<= 1;
            if (--result_exp <= 0)
                return BF16_ZERO();
        }
    }
```
                                 
Since we have enforeced $|A| \ge |B|$ using the **branchless swap**, this section can be significantly simplifed.

```c=
        // This conditional block is removed in my approach
        if (mant_a >= mant_b) {
            result_sign = sign_a;
            result_mant = mant_a - mant_b;
        } else {
            result_sign = sign_b;
            result_mant = mant_b - mant_a;
        }
```
In my approach, this condition check block is reduced to a single subtraction: `result_mant = mant_a - mant_b` as $|A| \ge |B|$ is guaranteed.

Implement the above logic into branchless code is as below:
```asm=
bf16_add_same_sign: 
    add s3, t4, t5 # result_mant = mant_a + mant_b

    andi t2, s3, 0x100 # result & 0x100, check if carry out
    beq t2, x0, bf16_add_return 
    srli s3, s3, 1 # result_mant >>= 1
    addi s1, s1, 1 # result_exp += 1
    addi t6, x0, 0xFF # check for overflow 
    bge s1, t6, bf16_add_return_overflow    
    jal x0, bf16_add_return

bf16_add_diff_sign: 
    sub s3, t4, t5 # result_mant = mant_a - mant_b 
    beq s3, x0, bf16_add_return_bf16_zero

bf16_add_normalize_loop: # normalize, maybe can optimize later
    andi t6, s3, 0x80 
    bne t6, x0, bf16_add_return 
    slli s3, s3, 1 # result_mant <<= 1
    addi s1, s1, -1 # result_exp -= 1
    blt s1, x0, bf16_add_return_bf16_zero
    jal x0, bf16_add_normalize_loop
```

##### Bug Fixed (Guard Bits)
> GitHub: [bf16_add_with_guard_bits](https://github.com/dorobouharu133/ca2025-quizzes/blob/b724ad166d63b936c33c774758720f2d98571cb7/bf16_add.S)
```
// Commit message
Fixed three logic errors in bf16_add improved approach:

1. Initialize result exponent s1 correctly before calculation loop.
2. Left shift mantissa 3 bits to protect precision.
3. Updated overflow mask from 0x100 to 0x800 due to point 2.
```
```
Test Case 3:
1.0000000 + 2^-8 = 1.000000
```
Since the above code faced a precision problem, I preserved 3 bits as guard bits.
```asm=
    # t4: mant_a
    # t5: mant_b
bf16_add_skip2:
    slli t4, t4, 3 # for further rounding (guard bits)
    slli t5, t5, 3 # for further rounding (guard bits)
```
Because I preserved 3 bits by shift left 3 bits, the below procedure also needed to be modify.
```asm=
    # t2: mask, to check carry out
    # s3: result_mant
    addi t2, x0, 0x10
    slli t2, t2, 4
    and t2, s3, t2 # result & 0x100, check if carry out
```
`0x100` is not enough to check overflow, we have to check **bit 11**(0x800) instead of bit 8 (0x100).
> **Reason:** Originally, the implicit 1 (hidden bit) is at **bit 7**, so a carry-out reaches **bit 8**. After shifting left 3 bits, the implicit 1 moves to **bit 10**. Therefore, adding two 10-bit mantissas may cause a carry-out to **bit 11**, so we have to use the mask **0x800**.
Since mantissa is 7 bits (bit 0 to bit 6), after shifting left 3 bit, the mantissa is 10 bits. Therefore, we use mask 0x800 to check whether the sum (including **the hidden bit at bit 10**) carries out to **bit 11** or not.
```
0x100 -> 0x800
```
```asm=
    addi t2, x0, 0x80
    slli t2, t2, 4
    and t2, s3, t2 # result & 0x800, check if carry out
```
#### bf16_add Test Cases
Original version with 5-stage pipeline CPU
```
// My original approach for bf16_add
Cycles:              247
Instrs. retired:     189
CPI:                1.31
IPC:               0.765
Clock rate:    228.28 Hz
```
**Branchless** version with 5-stage pipeline CPU
```
// Branchless
Cycles:            313
Instrs. retired:   265
CPI:              1.18
IPC:             0.847
Clock rate:  333.69 Hz
```
Compiler version with 5-stage pipeline CPU
```
// Compiler
Cycles:            259
Instrs. retired:   207
CPI:              1.25
IPC:             0.799
Clock rate:  254.92 Hz
```
**Performance:** My improved approach is about **1.21x slower** than the compiler-optimized version.
**Code Size:** Compared to the compiler-optimized version, my improved approach reduces the code size by nearly **49%**.
___
### ==bf16_sub==
```asm=
bf16_sub:
    addi t0, x0, 0x80
    slli t0, t0, 8
    addi sp, sp, -8
    sw ra, 4(sp)
    sw a1, 0(sp)
    xor a1, a1, t0      # negate b
    jal bf16_add
    lw a1, 0(sp)
    lw ra, 4(sp)
    addi sp, sp, 8
    jr ra
```
#### bf16_sub Test Cases
In the test of sub, I use 6 test cases.
```
1. `0x7F7F` - `0x0080`, maximal finite positive number - minimal normalized number
2. `0x7FC0` - `0x3F80`, NaN - 1.000000
3. `0x3F80` - `0x3B80`, 1.000000 - 2^(-8)
4. `0x7F80` - `0xFF80`, +inf - (-inf)
5. `0x4040` - `0x4000`, 3.000000 - 2.000000
6. `0x7F7F` - `0xFF7F`, maximal finite positive numbe - maximal finite negative number
```
#### Bug fixed (Precision)
```
# 1.0000000 - 2^(-8) = 1.000000
```
The correct answer should be `0x3B80`, but my approach gets `0x3B7F`.
In order to get the correct answer, we have to add **the guard bits** to my approach.
> GitHub: [bf16_sub_adjust_exp_diff](https://github.com/dorobouharu133/ca2025-quizzes/blob/main/bf16_sub/bf16_sub.S)
```
// My approach
Cycles:             586
Instrs. retired:    492
CPI:               1.19
IPC:               0.84
Clock rate:   350.06 Hz
```
> GitHub: [bf16_sub_compiler.S](https://github.com/dorobouharu133/ca2025-quizzes/blob/main/bf16_sub/bf16_sub_compiler.S)
```
// Compiler-optimized
Cycles:            1004
Instrs. retired:    750
CPI:               1.34
IPC:              0.747
Clock rate:    1.06 KHz
```
**Code Size:** Compared to the compiler-optimized version, my improved approach reduces the code size by nearly **53.6%**.
**Performance:** My approach is **1.71x faster** than the compiler-optimized version.

> Because `bf16_sub` is essentially derived from `bf16_add`, an additional `bf16_sub_improved` implementation is not required.
___
### ==bf16_mul==
> GitHub: [bf16_mul.S](https://github.com/dorobouharu133/ca2025-quizzes/tree/main/bf16_mul)

As before, I'll start with an **original version** that acts as a foundation for the enhanced version I will introduce later.
#### bf16_mul original
> GitHub: [bf16_mul_original.S](https://github.com/dorobouharu133/ca2025-quizzes/blob/main/bf16_mul/bf16_mul_original.S)

#### bf16_mul Test Cases
And I choose these test cases since:
```
1. `0x7F7F` x `0x0080`, `0x407F`, maximal finite positive number x minimal normalized number = 3.984375
2. `0x7FC0` x `0x3F80`, `0x7FC0`, NaN x 1.000000 -> NaN
3. `0x7F80` x `0xFF80`, `0x7F80`, +inf x (-inf) -> +inf
4. `0x4040` x `0x4000`, `0x40C0`, 3.000000 x 2.000000 = 6.000000
5. `0x3F80` x `0x3F80`, 1.000000 x 1.000000 = 1.000000
6. `0x0000` x `0x8000`, 0.000000 x (-0.000000) = (-0.000000)
7. `0x7F80` x `0x0000`, +inf x 0.000000 = NaN
8. `0x7F7F` x `0x4000`, maximal finite positive number x 2.000000 = +inf
9. `0x0080` x `0x0080`, minimal finite normalized positive number x minimal finite normalized positive number = 0.000000
10. `0x7FC0` x `0x3F80`, NaN x 1.000000 = NaN
11. `0xFF80` x `0x7F80`, (-inf) x +inf = -inf
12. `0x3F81` x `0x3F81`, 1.007812 x 1.007812 = 1.015625
13. `0xC000` x `0x4040`, -2.000000 x 3.000000 = -6.000000
14. `0x0040` x `0x0040`, minimal finite denormalized positive number x minimal finite denormalized positive number = 0.000000
15. `0x3F81` x `0x4000`, 1.007812 x 2.000000 = 2.015625
16. `0x4040` x `0x3F00`, 3.000000 x 0.500000 = 1.500000
17. `0x40A0` x `0x3F00`, 5.000000 x 0.500000 = 2.500000
18. `0x4010` x `0x4010`, 2.250000 x 2.250000 = 5.062500
``` 
(Run in 5-stage pipeline CPU)
> GitHub: [bf16_mul_original.S](https://github.com/dorobouharu133/ca2025-quizzes/blob/main/bf16_mul/bf16_mul_original.S)
```
// My original approach for bf16_mul
Cycles:             1095
Instrs. retired:     817
CPI:                1.34
IPC:               0.746
Clock rate:     1.22 KHz
```
The above figure is the execution info of my approach, and the below figure is the execution info of compiler.
(Run in 5-stage pipeline CPU)
> GitHub: [bf16_mul_compiler.S](https://github.com/dorobouharu133/ca2025-quizzes/blob/main/bf16_mul/bf16_mul_compiler.S)
```
// Compiler-optimized bf16_mul
Cycles:             3696
Instrs. retired:    2609
CPI:                1.42
IPC:               0.706
Clock rate:     1.60 KHz
```
**Performance:** My original approach is **3.37x faster** than the compiler-optimized version.
___
#### [bf16_mul_improved](https://github.com/dorobouharu133/ca2025-quizzes/blob/main/bf16_mul/bf16_mul.S)
> AI Usage: [bf16_mul improvement thought](https://gemini.google.com/share/60cc3a43aa7d)
```c=
    int16_t exp_adjust = 0;
    if (!exp_a) {
        while (!(mant_a & 0x80)) {
            mant_a <<= 1;
            exp_adjust--;
        }
        exp_a = 1;
    } else
        mant_a |= 0x80;
```
The goal here is to find the leading bit of the **mantissa** for **normalization**. Instead of using a loop, we can implement a **branchless 8-bit CLZ** approach to make the `bf16_mul` operation more efficient. Since the mantissa is 7-bit (8-bit if implicit 1 included), we can use a simpler way of CLZ.

#### Branchless 8-bit CLZ
**The below C code of 8-bit CLZ is [AI-generated](https://gemini.google.com/share/60cc3a43aa7d).**
```c=
// Gemini
uint32_t x = mant_a;
uint32_t s, shift = 0;

s = (x <= 0xF);  shift += (s << 2); x <<= (s << 2);
s = (x <= 0x3F); shift += (s << 1); x <<= (s << 1);
s = (x <= 0x7F); shift += (s << 0); x <<= (s << 0);

// Now shift is the number of Leading Zeros
```
I implemented the above code as the RISC-V instruction below:
```asm=
bf16_mul_exp_adjust_a: # normalize a
    addi s1, t4, 0 # s1 = x = mant_a
    addi s2, x0, 0 # s2 = shift
    addi s3, x0, 0 # s3 = s

    addi t6, x0, 0xF
    slt s3, t6, s1 # s3 = (x > 0xF) ? 1 : 0
    xori s3, s3, 1 # s3 = (x <= 0xF) ? 1 : 0

    slli t6, s3, 2
    add s2, s2, t6 # shift += (s << 2)
    sll s1, s1, t6 # x <<= (s << 2)
    #
    addi t6, x0, 0x3F
    slt s3, t6, s1 # s3 = (x > 0x3F) ? 1 : 0
    xori s3, s3, 1 # s3 = (x <= 0x3F) ? 1 : 0
    
    slli t6, s3, 1
    add s2, s2, t6 # shift += (s << 1)
    sll s1, s1, t6 # x <<= (s << 1)
    #
    addi t6, x0, 0x7F
    slt s3, t6, s1 # s3 = (x > 0x7F) ? 1 : 0
    xori s3, s3, 1 # s3 = (x <= 0x7F) ? 1 : 0
    # s2: shift = # of leading zeros
    # s4: exp_adjust_a
    sltiu t6, t2, 1 # t6 = (exp_a == 0) ? 1 : 0
    or t2, t2, t6 # exp_a = (exp_a == 0) ? 1 : exp_a
    addi t6, t6, -1
    xori t6, t6, -1
    and s4, s2, t6
    
    and s2, s2, t6
    sll t4, t4, s2

    ori t4, t4, 0x80 # mant_a |= 0x80
```
Below is my improved code with partial branchless:
```asm=
# a0: a
# a1: b
# t0: sign_a
# t1: sigb_b
# t2: exp_a
# t3: exp_b
# t4: mant_a
# t5: mant_b
# t6: temp
# s0: result_sign

bf16_mul:
    srli t0, a0, 15
    andi t0, t0, 1 # t0 = (a.bits >> 15) & 1
    srli t1, a1, 15
    andi t1, t1, 1 # t1 = (b.bits >> 15) & 1
    srli t2, a0, 7
    andi t2, t2, 0xFF # t2 = (a.bits >> 7) & 0xFF
    srli t3, a1, 7
    andi t3, t3, 0xFF # t3 = (b.bits >> 7) & 0xFF
    andi t4, a0, 0x7F # t4 = a.bits & 0x7F
    andi t5, a1, 0x7F # t5 = a.bits & 0x7F
    xor s0, t0, t1 # result_sign = sign_a ^ sign_b

bf16_mul_check_a_0xFF:
    addi t6, x0, 0xFF 
    bne t2, t6, bf16_mul_check_b_0xFF
    bne t4, x0, bf16_mul_return_a 
    bne t5, x0, bf16_mul_return_pInf
    bne t3, x0, bf16_mul_return_pInf
    jal x0, bf16_mul_return_NaN

bf16_mul_check_b_0xFF:
    addi t6, x0, 0xFF
    bne t3, t6, bf16_mul_check_zero
    bne t4, x0, bf16_mul_return_b
    bne t2, x0, bf16_mul_return_pInf
    bne t5, x0, bf16_mul_return_pInf
    jal x0, bf16_mul_return_NaN

bf16_mul_check_zero:
    or t6, t2, t4
    bne t6, x0, bf16_mul_exp_adjust
    or t6, t3, t5
    bne t6, x0, bf16_mul_exp_adjust
    jal x0, bf16_mul_return_zero

bf16_mul_exp_adjust:
bf16_mul_exp_adjust_a: # normalize a
    addi s1, t4, 0 # s1 = x = mant_a
    addi s2, x0, 0 # s2 = shift
    addi s3, x0, 0 # s3 = s

    addi t6, x0, 0xF
    slt s3, t6, s1 # s3 = (x > 0xF) ? 1 : 0
    xori s3, s3, 1 # s3 = (x <= 0xF) ? 1 : 0

    slli t6, s3, 2
    add s2, s2, t6 # shift += (s << 2)
    sll s1, s1, t6 # x <<= (s << 2)
    #
    addi t6, x0, 0x3F
    slt s3, t6, s1 # s3 = (x > 0x3F) ? 1 : 0
    xori s3, s3, 1 # s3 = (x <= 0x3F) ? 1 : 0
    
    slli t6, s3, 1
    add s2, s2, t6 # shift += (s << 1)
    sll s1, s1, t6 # x <<= (s << 1)
    #
    addi t6, x0, 0x7F
    slt s3, t6, s1 # s3 = (x > 0x7F) ? 1 : 0
    xori s3, s3, 1 # s3 = (x <= 0x7F) ? 1 : 0
    # s2: shift = # of leading zeros
    # s4: exp_adjust_a
    sltiu t6, t2, 1 # t6 = (exp_a == 0) ? 1 : 0
    or t2, t2, t6 # exp_a = (exp_a == 0) ? 1 : exp_a
    addi t6, t6, -1
    xori t6, t6, -1
    and s4, s2, t6
    
    and s2, s2, t6
    sll t4, t4, s2

    ori t4, t4, 0x80 # mant_a |= 0x80
bf16_mul_exp_adjust_b: # normalize b
    addi s1, t4, 0 # s1 = x = mant_b
    addi s2, x0, 0 # s2 = shift
    addi s3, x0, 0 # s3 = s

    addi t6, x0, 0xF
    slt s3, t6, s1 # s3 = (x > 0xF) ? 1 : 0
    xori s3, s3, 1 # s3 = (x <= 0xF) ? 1 : 0

    slli t6, s3, 2
    add s2, s2, t6 # shift += (s << 2)
    sll s1, s1, t6 # x <<= (s << 2)
    #
    addi t6, x0, 0x3F
    slt s3, t6, s1 # s3 = (x > 0x3F) ? 1 : 0
    xori s3, s3, 1 # s3 = (x <= 0x3F) ? 1 : 0
    
    slli t6, s3, 1
    add s2, s2, t6 # shift += (s << 1)
    sll s1, s1, t6 # x <<= (s << 1)
    #
    addi t6, x0, 0x7F
    slt s3, t6, s1 # s3 = (x > 0x7F) ? 1 : 0
    xori s3, s3, 1 # s3 = (x <= 0x7F) ? 1 : 0
    # s2: shift = # of leading zeros
    # s5: exp_adjust_b
    sltiu t6, t3, 1 # t6 = (exp_a == 0) ? 1 : 0
    or t3, t3, t6 # exp_a = (exp_a == 0) ? 1 : exp_a
    addi t6, t6, -1
    xori t6, t6, -1
    
    and s5, s2, t6
    
    and s2, s2, t6
    sll t5, t5, s2

    ori t5, t5, 0x80 # mant_b |= 0x80
    # s1: exp_adjust = exp_adjust_a + exp_adjust_b
    add s1, s4, s5
bf16_mul_normalize:
    # s2: result_mant
    # s3: result_exp
    mul s2, t4, t5 # result_mant = mant_a * mant_b, need to modify later
    add s3, t2, t3 # result_exp = exp_a + exp_b
    add s3, s3, s5 # result_exp += exp_adjust
    addi s3, s3, -127 # result_exp -= BF16_EXP_BIAS

bf16_mul_normalize_check: # branchless later

bf16_mul_normalize_check_result_mant_if:
    addi t6, x0, 0x80
    slli t6, t6, 8
    and t6, s2, t6
    beq t6, x0,  bf16_mul_normalize_check_result_mant_else
    srli t6, s2, 8
    andi s2, t6, 0xFF
    addi s3, s3, 1
    jal x0, bf16_mul_normalize_check_result_exp_if_ge_0xFF 

bf16_mul_normalize_check_result_mant_else:
    srli t6, s2, 7
    andi s2, t6, 0x7F

bf16_mul_normalize_check_result_exp_if_ge_0xFF:
    addi t6, x0, 0xFF
    bge s3, t6, bf16_mul_return_pInf

bf16_mul_normalize_check_result_exp_if_le_0:
    bgt s3, x0, bf16_mul_return
    addi t6, x0, -6
    bgt s3, t6, bf16_mul_return_zero
    addi t6, x0, 1
    sub t6, t6, s3 # t6 = 1 - result_exp
    sll s2, s2, t6
    addi s3, x0, 0

bf16_mul_return:
    slli a0, s0, 15
    andi s3, s3, 0xFF
    slli s3, s3, 7
    or a0, a0, s3
    andi s2, s2, 0x7F
    or a0, a0, s2
    jr ra
    
bf16_mul_return_a:
    jr ra

bf16_mul_return_b:
    addi a0, a1, 0
    jr ra

bf16_mul_return_pInf:
    addi a0, s0, 0
    slli a0, a0, 15
    addi t6, x0, 0x7F
    slli t6, t6, 8
    ori t6, t6, 0x80
    or a0, a0, t6
    jr ra

bf16_mul_return_NaN:
    addi a0, x0, 0x7F
    slli a0, a0, 8
    ori a0, a0, 0xC0
    jr ra

bf16_mul_return_zero:
    addi a0, s0, 0
    slli a0, a0, 15
    jr ra
```
I’ve finished converting the first section of the logic to be branchless. Next, I’ll apply the same optimization to the remaining parts of the code.

> AI Usage: [bf16_mul test cases & debug](https://gemini.google.com/share/7f33de0eeaf6)
**Debug Update:**
Found an error in the BF16 test data. For $2.25 \times 2.25$, the precise result is $5.0625$, which rounds to `0x402A` in BF16. The initial expected value of `0x4020` was a typo. The hardware implementation is actually correct; no precision fix is needed.

```c=
    uint32_t result_mant = (uint32_t) mant_a * mant_b;
    int32_t result_exp = (int32_t) exp_a + exp_b - BF16_EXP_BIAS + exp_adjust;
    if (result_mant & 0x8000) {
        result_mant = (result_mant >> 8) & 0x7F;
        result_exp++;
    } else
        result_mant = (result_mant >> 7) & 0x7F;
```
The concept of the above code is pretty simple, we want to check whether the result_mant is 15 bits or 16 bits,
- 16 bits means there is carry out for mant_a * mant_b, therefore result_mant & 0x8000 = 1 (using mask 0x8000 to check bit 15).
- 15 bits means there is no carry out for mant_a * mant_b, therefore result_mant & 0x8000 = 0.
Then use shift right 8 (or 7) bits to truncate `result_mant` and retain the upper 8-bits.
Note that if the result_mant is 16 bits, it has to be normalized, therefore result_exp is incremented 1.

I implement the above logic into RISC-V instructions.
Instead of serval codes and branch instrucion in the original approach, this section is quite simple.
Since we only want to check whether **result_mant is 16 bits or not**, we can **shift right logical 15 bits** to get bit 15, because the condition of shfit right result_mant is related to bit 15, we can determine the shift amount and result_mant by:
- `result_mant >> 15` == 1, shift right `7 + (result_mant>>15)` = 8 bits
- `result_mant >> 15` == 0, shfit right `7 + (result_mant>>15)` = 7 bits
And result_exp can be also determined by: `result_exp += (result_mant>>15)`.
> **Note:** `result_mant >> 15` here is effective to `result_mant & 0x8000`. 
```asm=
bf16_mul_normalize:
    # s2: result_mant
    # s3: result_exp
    mul s2, t4, t5 # result_mant = mant_a * mant_b, need to modify later
    add s3, t2, t3 # result_exp = exp_a + exp_b
    sub s3, s3, s5 # result_exp - exp_adjust_b
    sub s3, s3, s4 # result_exp - exp_adjust_a - exp_adjust_b
    addi s3, s3, -127 # result_exp -= BF16_EXP_BIAS

bf16_mul_normalize_check:
    srli t6, s2, 15
    addi t0, t6, 7 # t0 = (result_mant == 1) ? 8 : 7, shift_amount 
    srl s2, s2, t0 # result_mant >>= (shift_amount)
    add s3, s3, t6  # result_exp += t6
```
The next step is to replace `mul` instruction with the [**shift-and-add**](##==bf16_sqrt_shift_add==) method used in bf16_sqrt.

Below is the complete code of bf16_mul:
```asm=
.global bf16_mul
.global shift_and_add

# a0: a
# a1: b
# t0: sign_a
# t1: sigb_b
# t2: exp_a
# t3: exp_b
# t4: mant_a
# t5: mant_b
# t6: temp
# s0: result_sign

bf16_mul:
    srli t0, a0, 15
    andi t0, t0, 1 # t0 = (a.bits >> 15) & 1
    srli t1, a1, 15
    andi t1, t1, 1 # t1 = (b.bits >> 15) & 1
    srli t2, a0, 7
    andi t2, t2, 0xFF # t2 = (a.bits >> 7) & 0xFF
    srli t3, a1, 7
    andi t3, t3, 0xFF # t3 = (b.bits >> 7) & 0xFF
    andi t4, a0, 0x7F # t4 = a.bits & 0x7F
    andi t5, a1, 0x7F # t5 = a.bits & 0x7F
    xor s0, t0, t1 # result_sign = sign_a ^ sign_b

bf16_mul_check_a_0xFF:
    addi t6, x0, 0xFF 
    bne t2, t6, bf16_mul_check_b_0xFF
    bne t4, x0, bf16_mul_return_a 
    bne t5, x0, bf16_mul_return_pInf
    bne t3, x0, bf16_mul_return_pInf
    jal x0, bf16_mul_return_NaN

bf16_mul_check_b_0xFF:
    addi t6, x0, 0xFF
    bne t3, t6, bf16_mul_check_zero
    bne t4, x0, bf16_mul_return_b
    bne t2, x0, bf16_mul_return_pInf
    bne t5, x0, bf16_mul_return_pInf
    jal x0, bf16_mul_return_NaN

bf16_mul_check_zero:
    or t6, t2, t4
    bne t6, x0, bf16_mul_exp_adjust
    or t6, t3, t5
    bne t6, x0, bf16_mul_exp_adjust
    jal x0, bf16_mul_return_zero

bf16_mul_exp_adjust:
bf16_mul_exp_adjust_a: # normalize a
    addi s1, t4, 0 # s1 = x = mant_a
    addi s2, x0, 0 # s2 = shift
    addi s3, x0, 0 # s3 = s

    addi t6, x0, 0xF
    slt s3, t6, s1 # s3 = (x > 0xF) ? 1 : 0
    xori s3, s3, 1 # s3 = (x <= 0xF) ? 1 : 0

    slli t6, s3, 2
    add s2, s2, t6 # shift += (s << 2)
    sll s1, s1, t6 # x <<= (s << 2)
    #
    addi t6, x0, 0x3F
    slt s3, t6, s1 # s3 = (x > 0x3F) ? 1 : 0
    xori s3, s3, 1 # s3 = (x <= 0x3F) ? 1 : 0
    
    slli t6, s3, 1
    add s2, s2, t6 # shift += (s << 1)
    sll s1, s1, t6 # x <<= (s << 1)
    #
    addi t6, x0, 0x7F
    slt s3, t6, s1 # s3 = (x > 0x7F) ? 1 : 0
    xori s3, s3, 1 # s3 = (x <= 0x7F) ? 1 : 0
    # s2: shift = # of leading zeros
    # s4: exp_adjust_a
    sltiu t6, t2, 1 # t6 = (exp_a == 0) ? 1 : 0
    or t2, t2, t6 # exp_a = (exp_a == 0) ? 1 : exp_a
    addi t6, t6, -1
    xori t6, t6, -1
    and s4, s2, t6
    
    and s2, s2, t6
    sll t4, t4, s2

    ori t4, t4, 0x80 # mant_a |= 0x80
bf16_mul_exp_adjust_b: # normalize b
    addi s1, t4, 0 # s1 = x = mant_b
    addi s2, x0, 0 # s2 = shift
    addi s3, x0, 0 # s3 = s

    addi t6, x0, 0xF
    slt s3, t6, s1 # s3 = (x > 0xF) ? 1 : 0
    xori s3, s3, 1 # s3 = (x <= 0xF) ? 1 : 0

    slli t6, s3, 2
    add s2, s2, t6 # shift += (s << 2)
    sll s1, s1, t6 # x <<= (s << 2)
    #
    addi t6, x0, 0x3F
    slt s3, t6, s1 # s3 = (x > 0x3F) ? 1 : 0
    xori s3, s3, 1 # s3 = (x <= 0x3F) ? 1 : 0
    
    slli t6, s3, 1
    add s2, s2, t6 # shift += (s << 1)
    sll s1, s1, t6 # x <<= (s << 1)
    #
    addi t6, x0, 0x7F
    slt s3, t6, s1 # s3 = (x > 0x7F) ? 1 : 0
    xori s3, s3, 1 # s3 = (x <= 0x7F) ? 1 : 0
    # s2: shift = # of leading zeros
    # s5: exp_adjust_b
    sltiu t6, t3, 1 # t6 = (exp_a == 0) ? 1 : 0
    or t3, t3, t6 # exp_a = (exp_a == 0) ? 1 : exp_a
    addi t6, t6, -1
    xori t6, t6, -1
    
    and s5, s2, t6
    
    and s2, s2, t6
    sll t5, t5, s2

    ori t5, t5, 0x80 # mant_b |= 0x80
    # s1: exp_adjust = exp_adjust_a + exp_adjust_b
    add s1, s4, s5
bf16_mul_normalize:
    # s2: result_mant
    # s3: result_exp
    # mul s2, t4, t5 # result_mant = mant_a * mant_b
    addi sp, sp, -12
    sw ra, 0(sp)
    sw a0, 4(sp)
    sw a1, 8(sp)
    addi a0, t4, 0
    addi a1, t5, 0
    jal ra, shift_and_add
    addi s2, a0, 0
    lw ra, 0(sp)
    lw a0, 4(sp)
    lw a1, 8(sp)
    addi sp, sp, 12
    add s3, t2, t3 # result_exp = exp_a + exp_b
    sub s3, s3, s5 # result_exp - exp_adjust_b
    sub s3, s3, s4 # result_exp - exp_adjust_a - exp_adjust_b
    addi s3, s3, -127 # result_exp -= BF16_EXP_BIAS

bf16_mul_normalize_check:
    srli t6, s2, 15
    addi t0, t6, 7 # t0 = (result_mant == 1) ? 8 : 7, shift_amount 
    srl s2, s2, t0 # result_mant >>= (shift_amount)
    add s3, s3, t6  # result_exp += t6

bf16_mul_normalize_check_result_exp_if_ge_0xFF:
    addi t6, x0, 0xFF
    bge s3, t6, bf16_mul_return_pInf

bf16_mul_normalize_check_result_exp_if_le_0:
    bgt s3, x0, bf16_mul_return
    addi t6, x0, -6
    blt s3, t6, bf16_mul_return_zero
    addi t6, x0, 1
    sub t6, t6, s3 # t6 = 1 - result_exp
    srl s2, s2, t6
    addi s3, x0, 0

bf16_mul_return:
    slli a0, s0, 15
    andi s3, s3, 0xFF
    slli s3, s3, 7
    or a0, a0, s3
    andi s2, s2, 0x7F
    or a0, a0, s2
    jr ra
    
bf16_mul_return_a:
    jr ra

bf16_mul_return_b:
    addi a0, a1, 0
    jr ra

bf16_mul_return_pInf:
    addi a0, s0, 0
    slli a0, a0, 15
    addi t6, x0, 0x7F
    slli t6, t6, 8
    ori t6, t6, 0x80
    or a0, a0, t6
    jr ra

bf16_mul_return_NaN:
    addi a0, x0, 0x7F
    slli a0, a0, 8
    ori a0, a0, 0xC0
    jr ra

bf16_mul_return_zero:
    addi a0, s0, 0
    slli a0, a0, 15
    jr ra

# a0: multiplicand
# a1: multiplier
# t0: accumulator
# t1: multiplier_copy
# t2: bit0
shift_and_add:
    addi sp, sp, -12
    sw t0, 0(sp)
    sw t1, 4(sp)
    sw t2, 8(sp)
    
    addi t0, x0, 0
    addi t1, a1, 0
    andi t2, a1, 1
shift_and_add_for_loop:
    andi t2, t1, 1
    beq t2, x0, shift_and_add_for_skip_add
    add t0, t0, a0
    
shift_and_add_for_skip_add:    
    slli a0, a0, 1
    srli t1, t1, 1
    bne t1, x0, shift_and_add_for_loop
shfit_and_add_end:
    addi a1, t0, 0
    lw t0, 0(sp)
    lw t1, 4(sp)
    lw t2, 8(sp)
    addi sp, sp, 12
    addi a0, a1, 0
    jr ra 
```
#### bf16_mul Test Cases
> GitHub: [bf16_mul.S](https://github.com/dorobouharu133/ca2025-quizzes/blob/main/bf16_mul/bf16_mul.S)
```
Cycles:            2715
Instrs. retired:   2141
CPI:               1.27
IPC:              0.789
Clock rate:    2.26 KHz
```
**Performance:** My improverd approach is **1.36x faster** than the compiler-optmized version.
**Code Size:** Compared to the compiler-optimized version, my approach **reduces** the code size by nearly **39%**.
___
### ==bf16_div==
#### bf16_div original
> GitHub: [bf16_div original approach](https://github.com/dorobouharu133/ca2025-quizzes/blob/ddfb96a8105e4fa1adb2c97fd85c5c548076904b/bf16_div.S)


#### bf16_div Test Cases
```
1. `0x7F7F` / `0x0080`, maximal finite positive number / minimal normalized number
2. `0x7FC0` / `0x3F80`, NaN / 1.000000
3. `0x7F80` / `0xFF80`, +inf / (-inf)
4. `0x4040` / `0x4000`, 3.000000 / 2.000000
```

```
// Original Approach
Cycles:             643
Instrs. retired:    465 
CPI:               1.38
IPC:              0.723
Clock rate:   595.37 Hz
```
The above figure is the execution info of my approach, and the below is the execution info of the compiler-optimized version.
```
// Compiler
Cycles:            1479
Instrs. retired:   1028
CPI:               1.44
IPC:              0.695
Clock rate:    1.91 KHz
```
My original approach is **2.3x faster** than compiler's version. 
___
#### bf16_div_improved 
There are two loops in the original approach, we can improve it.
```c=
    for (int i = 0; i < 16; i++) {
        quotient <<= 1;
        if (dividend >= (divisor << (15 - i))) {
            dividend -= (divisor << (15 - i));
            quotient |= 1;
        }
    }
```
In my original approach, I translated it line-by-line:
```asm=
# Original approach

bf16_div_division:
    # t6: loop times
    # s1: dividend
    # s2: divisor
    # s3: quotient
    # s4: counter
    slli s1, t4, 15 # dividend = mant_a << 15
    addi s2, t5, 0   # divisor = mant_b
    addi s3, x0, 0   # quotient = 0
    addi t6, x0, 16  # loop times = 16
    addi s4, x0, 0   # counter = 0

bf16_div_division_loop:
    bge s4, t6, bf16_div_division_loop_end
    slli s3, s3, 1   # quotient <<= 1
    addi t4, x0, 15
    sub t4, t4, s4   # t4 = 15 - i
    sll t4, s2, t4  # temp = divisor << (15 - i)
    
    blt s1, t4, bf16_div_division_loop_sub_skip

bf16_div_division_loop_sub:
    sub s1, s1, t4 # dividend -= (divisor << (15 - i))
    ori s3, s3, 1   # quotient |= 1

bf16_div_division_loop_sub_skip:
    addi s4, s4, 1   # i++
    jal x0, bf16_div_division_loop
```
However, the code is actually doing division, 

---
```c=
    while (!(quotient & 0x8000) && result_exp > 1) {
        quotient <<= 1;
        result_exp--;
    }
    quotient >>= 8;
```
The purpose of the above code is to normalize the quotient, 
```asm=
# Original approah

bf16_div_normalize_quotient_while_loop:
    addi t4, x0, 0x80
    slli t4, t4, 8 # t6 = 0x8000
    and t4, s3, t4 # t6 = quotient & 0x8000
    bne t4, x0, bf16_div_normalize_quotient_while_loop_end
    addi t6, x0, 1
    ble s5, t6, bf16_div_normalize_quotient_while_loop_end
    slli s3, s3, 1 # quotient <<= 1
    addi s5, s5, -1 # result_exp -= 1
    jal x0, bf16_div_normalize_quotient_while_loop

bf16_div_normalize_quotient_while_loop_end:
    srli s3, s3, 8 # quotient >>= 8
```
Just like what we have done before, **this while loop tries to clz and normalize the quotient**.
Note that **the result_exp should greater than or equal to zero at the end of the loop**.

Therefore, we can use the [**clz concept**](###Branchless-8-bit-CLZ) that was used in the previous section.
```c=
// Gemini
uint32_t x = mant_a;
uint32_t s, shift = 0;

s = (x <= 0xF);  shift += (s << 2); x <<= (s << 2);
s = (x <= 0x3F); shift += (s << 1); x <<= (s << 1);
s = (x <= 0x7F); shift += (s << 0); x <<= (s << 0);

// Now shift is the number of Leading Zeros
```
**Observe the bit mask:**
```
# 8-bit clz
0xF  = 0000 1111
0x3F = 0011 1111
0x7F = 0111 1111
```
We can observe that **clz always divides the remaining range into two parts**. At each step, it checks the upper half and then repeats the same operation on the selected half.
Based on the observation, I implemented this logic to develop a 16-bit branchlss `clz`.
**16-bit branchless clz mask:**
```
# 16-bit clz
# divided into 2 parts
0000 0000 1111 1111 -> 0x00FF
0000 1111 1111 1111 -> 0x0FFF
0011 1111 1111 1111 -> 0x3FFF
0111 1111 1111 1111 -> 0x7FFF
```
> **Note:** Since $16 = 2^{4}$, the maximum shift amount in 16-bit CLZ is 2^4.

> GitHub: [Branchless 16-bit CLZ](https://github.com/dorobouharu133/ca2025-quizzes/blob/main/branchless_16_bit_clz.c)

So we can implemented in C code:
```c=
// My own approach
    uint32_t x = mant_a;
    uint32_t s, shift = 0;

    // 0000 0000 1111 1111 -> 0x00FF
    // 0000 1111 1111 1111 -> 0x0FFF
    // 0011 1111 1111 1111 -> 0x3FFF
    // 0111 1111 1111 1111 -> 0x7FFF
 
    s = (x <= 0x00FF);   shift += (s << 3); x <<= (s << 3);
    s = (x <= 0x0FFF);   shift += (s << 2); x <<= (s << 2);
    s = (x <= 0x3FFF);   shift += (s << 1); x <<= (s << 1);
    s = (x <= 0x7FFF);   shift += (s << 0); x <<= (s << 0);
// Now shift is the number of Leading Zeros
```
> **Note:** Verlidatation code is included in [GitHub](https://github.com/dorobouharu133/ca2025-quizzes/blob/main/branchless_16_bit_clz.c).


> GitHub: [Branchless 32-bit CLZ](https://github.com/dorobouharu133/ca2025-quizzes/blob/main/branchless_32_bit_clz.c)
```c=
// My own approach
    // My own approach
    uint32_t x = mant_a;
    uint32_t s, shift = 0;

    // 0000 0000 0000 0000 1111 1111 1111 1111 -> 0x0000FFFF
    // 0000 0000 1111 1111 1111 1111 1111 1111 -> 0x00FFFFFF
    // 0000 1111 1111 1111 1111 1111 1111 1111 -> 0x0FFFFFFF
    // 0011 1111 1111 1111 1111 1111 1111 1111 -> 0x3FFFFFFF
    // 0111 1111 1111 1111 1111 1111 1111 1111 -> 0x7FFFFFFF

    s = (x <= 0x0000FFFF);   shift += (s << 4); x <<= (s << 4); 
    s = (x <= 0x00FFFFFF);   shift += (s << 3); x <<= (s << 3);
    s = (x <= 0x0FFFFFFF);   shift += (s << 2); x <<= (s << 2);
    s = (x <= 0x3FFFFFFF);   shift += (s << 1); x <<= (s << 1);
    s = (x <= 0x7FFFFFFF);   shift += (s << 0); x <<= (s << 0);
// Now shift is the number of Leading Zeros
```
> **Note:** Verlidatation code is included in [GitHub](https://github.com/dorobouharu133/ca2025-quizzes/blob/main/branchless_32_bit_clz.c).

**Note:** Although the original branchless 8-bit CLZ implementation was AI-generated, **extending it to 16-bit and 32-bit was my own work**.

Though I develop 32-bit branchless CLZ, the 16-bit version is what we used in this case. Since **quotient is 16-bit**.
```c=
while (!(quotient & 0x8000) && result_exp > 1) {
    quotient <<= 1;
    result_exp--;
}
```
I will introduce how I improved this logic.
Since the purpose of this code segment is to normalize the quotient, 
we can use **branchless clz** instead of using while loop to iteratively find leading 1.
And note that the second condition: `result_exp > 1`, this means that the maximum shift amount is **result_exp-1**. Therefore, the number of leading zeros need compare the number of leading zeros and `result_exp - 1`.
That is:
- if (result_exp - 1) < the number of leading zeros, 
    - result_exp = 1
    - quotient <<= (result_exp - 1)
- if (result_exp - 1) >= the number of leading zeros, 
    - result_exp -= the number of leading zeros
    - quotient <<= the number of leading zeros

> GitHub: [bf16_div.S](https://github.com/dorobouharu133/ca2025-quizzes/blob/main/bf16_div/bf16_div.S)
```asm=
.data
newline: .string "\n"
pass_msg: .string "All tests passed!"
fail_msg: .string "Tests failed!"
.text
.globl bf16_div
.globl branchless_16_bit_clz
.globl main

main:
# maximal finite positive number / 0.000000 = +inf
test_1:
    addi a0, x0, 0x7F
    slli a0, a0, 8
    ori a0, a0, 0x7F
    addi a1, x0, 0x80
    jal ra, bf16_div   

    addi s0, a0, 0
    addi t0, x0, 0x7F
    slli t0, t0, 8
    ori t0, t0, 0x80
    bne s0, t0, test_failed

test_passed:
    la a0, pass_msg
    addi a7, x0, 4            
    ecall
    jal x0, end
test_failed:
    la a0, fail_msg
    addi a7, x0, 4            
    ecall
end:
    la a0, newline
    addi a7, x0, 4            
    ecall

    addi a7, x0, 10        
    ecall
    
# a0: a
# a1: b
# t0: sign_a
# t1: sign_b
# t2: exp_a
# t3: exp_b
# t4: mant_a
# t5: mant_b
# t6: temp
# s0: result_sign
bf16_div:
    srli t0, a0, 15
    andi t0, t0, 1 # t0 = (a.bits >> 15) & 1, sign_a

    srli t1, a1, 15
    andi t1, t1, 1 # t1 = (b.bits >> 15) & 1, sign_b

    srli t2, a0, 7
    andi t2, t2, 0xFF # t2 = (a.bits >> 7) & 0xFF, exp_a

    srli t3, a1, 7
    andi t3, t3, 0xFF # t3 = (b.bits >> 7) & 0xFF, exp_b

    andi t4, a0, 0x7F # t4 = a.bits & 0x7F, mant_a
    andi t5, a1, 0x7F # t5 = b.bits & 0x7F, mant_b

    xor s0, t0, t1 # result_sign = sign_a ^ sign_b

bf16_div_check_exp_b_0xFF: # maybe optimize later
    addi t6, x0, 0xFF
    bne t3, t6, bf16_div_check_b_NaN_inf
    bne t5, x0, bf16_div_return_b
    bne t2, t6, bf16_div_return_signed_zero
    bne t4, x0, bf16_div_return_signed_zero
    jal x0, bf16_div_return_NaN
    
bf16_div_check_b_NaN_inf: # maybe optimize later
    bne t3, x0, bf16_div_check_exp_a_0xFF
    bne t5, x0, bf16_div_check_exp_a_0xFF
    beq t2, x0, bf16_div_return_NaN
    beq t4, x0, bf16_div_return_NaN
    jal x0, bf16_div_return_signed_zero

bf16_div_check_exp_a_0xFF: # maybe optimize later
    bne t2, t6, bf16_div_check_a_NaN_inf
    bne t4, x0, bf16_div_return_a
    jal x0, bf16_div_return_signed_inf

bf16_div_check_a_NaN_inf: # maybe optimize later
    bne t2, x0, bf16_div_a_explicit_one
    bne t4, x0, bf16_div_a_explicit_one
    jal x0, bf16_div_return_signed_zero

bf16_div_a_explicit_one:
    beq t2, x0, bf16_div_b_explicit_one
    ori t4, t4, 0x80 # mant_a |= 0x80

bf16_div_b_explicit_one:
    beq t3, x0, bf16_div_division
    ori t5, t5, 0x80 # mant_b |= 0x80

bf16_div_division: # should be optimized
    # t6: loop times
    # s1: dividend
    # s2: divisor
    # s3: quotient
    # s4: counter
    slli s1, t4, 15 # dividend = mant_a << 15
    addi s2, t5, 0   # divisor = mant_b
    addi s3, x0, 0   # quotient = 0
    addi t6, x0, 16  # loop times = 16
    addi s4, x0, 0   # counter = 0
    
bf16_div_division_loop:
    bge s4, t6, bf16_div_division_loop_end
    slli s3, s3, 1   # quotient <<= 1
    addi t4, x0, 15
    sub t4, t4, s4   # t4 = 15 - i
    sll t4, s2, t4  # temp = divisor << (15 - i)
    
    blt s1, t4, bf16_div_division_loop_sub_skip
bf16_div_division_loop_sub:
    sub s1, s1, t4 # dividend -= (divisor << (15 - i))
    ori s3, s3, 1   # quotient |= 1
bf16_div_division_loop_sub_skip:
    addi s4, s4, 1   # i++
    jal x0, bf16_div_division_loop

bf16_div_division_loop_end:
    # s5: result_exp
    add s5, t2, x0 # result_exp = exp_a
    sub s5, s5, t3 # result_exp -= exp_b
    addi s5, s5, 127 # result_exp += bias (127)

bf16_div_normalize_exp_a:
    bne t2, x0, bf16_div_normalize_exp_b
    addi s5, s5, -1

bf16_div_normalize_exp_b:
    bne t3, x0, bf16_div_normalize_quotient_if
    addi s5, s5, 1

bf16_div_normalize_quotient_if:
    addi t6, x0, 0x80
    slli t6, t6, 8 # t6 = 0x8000
    and t4, s3, t6 # t4 = quotient & 0x8000
    beq t4, x0, bf16_div_normalize_quotient_else
    srli s3, s3, 8 # quotient >>= 8
    jal x0, bf16_div_normalize_quotient_end

bf16_div_normalize_quotient_else:

bf16_div_normalize_quotient_clz:
    addi sp, sp, -8
    sw ra, 0(sp)
    sw a0, 4(sp)
    
    addi a0, s3, 0
    jal ra, branchless_16_bit_clz
    addi t6, a0, 0 # t6 = # of leading zeros

    lw ra, 0(sp)
    lw a0, 4(sp)
    addi sp, sp, 8

    addi t4, s5, -1 # t4 = result_exp - 1
    bge t6, t4, bf16_div_normalize_quotient_clz_sub_result_exp_minus_1 # optimize to whole branchless later

bf16_div_normalize_quotient_clz_sub_clz:
    sub s5, s5, t6 # result_exp -= leading_zeros
    sll s3, s3, t6 # quotient <<= leading_zeros
    jal x0, bf16_div_normalize_quotient_clz_end

bf16_div_normalize_quotient_clz_sub_result_exp_minus_1:
    addi s5, x0, 1
    sll s3, s3, t4

bf16_div_normalize_quotient_clz_end:
    srli s3, s3, 8 # quotient >>= 8

bf16_div_normalize_quotient_end:
    andi s3, s3, 0x7F # quotient & 0x7F

bf16_div_return:
    addi t6, x0, 0xFF
    bge s5, t6, bf16_div_return_signed_inf
    ble s5, x0, bf16_div_return_signed_zero
    slli a0, s0, 15 # result_sign << 15
    andi s5, s5, 0xFF
    slli s5, s5, 7 # result_exp << 7
    or a0, a0, s5
    andi s3, s3, 0x7F
    or a0, a0, s3
    jr ra

bf16_div_return_a:
    jr ra

bf16_div_return_b:
    addi a0, a1, 0
    jr ra

bf16_div_return_signed_zero:
    slli a0, s0, 15 # result_sign << 15
    jr ra

bf16_div_return_signed_inf:
    slli a0, s0, 15 # result_sign << 15
    addi t6, x0, 0x7F
    slli t6, t6, 8
    ori t6, t6, 0x80
    or a0, a0, t6 # return Inf
    jr ra

bf16_div_return_NaN:
    addi a0, x0, 0x7F
    slli a0, a0, 8
    ori a0, a0, 0xC0
    jr ra

# a0: mant_a
# t0: x
# t1: s
# t2: shift
# t3: temp
# t4: temp2
branchless_16_bit_clz:
    addi sp, sp, -20
    sw t0, 0(sp)
    sw t1, 4(sp)
    sw t2, 8(sp)
    sw t3, 12(sp)
    sw t4, 16(sp)
    
    addi t0, a0, 0  # x = mant_a
    addi t1, x0, 0  # s = 0
    addi t2, x0, 0  # shift = 0

    addi t3, x0, 0x00FF
    slt t1, t3, t0 # s = (x > 0x00FF) ? 1 : 0
    xori t1, t1, 1 # s = (x <= 0x00FF) ? 1 : 0
    slli t4, t1, 3
    add t2, t2, t4 # shift += (s << 3)
    sll t0, t0, t4 # x <<= (s << 3)

    addi t3, x0, 0xF
    slli t3, t3, 8
    ori t3, t3, 0xFF
    slt t1, t3, t0 # s = (x > 0x0FFF) ? 1 : 0
    xori t1, t1, 1 # s = (x <= 0x0FFF) ? 1 : 0
    slli t4, t1, 2
    add t2, t2, t4 # shift += (s << 2)
    sll t0, t0, t4 # x <<= (s << 2)

    addi t3, x0, 0x3F
    slli t3, t3, 8
    ori t3, t3, 0xFF
    slt t1, t3, t0 # s = (x > 0x3FFF) ? 1 : 0
    xori t1, t1, 1 # s = (x <= 0x3FFF) ? 1 : 0
    slli t4, t1, 1
    add t2, t2, t4 # shift += (s << 1)
    sll t0, t0, t4 # x <<= (s << 1)

    addi t3, x0, 0x7F
    slli t3, t3, 8
    ori t3, t3, 0xFF
    slt t1, t3, t0 # s = (x > 0x7FFF) ? 1 : 0
    xori t1, t1, 1 # s = (x <= 0x7FFF) ? 1 : 0
    slli t4, t1, 0
    add t2, t2, t4 # shift += (s << 0)
    sll t0, t0, t4 # x <<= (s << 0)

    addi a0, t2, 0  # return shift

    lw t0, 0(sp)
    lw t1, 4(sp)
    lw t2, 8(sp)
    lw t3, 12(sp)
    lw t4, 16(sp)
    addi sp, sp, 20

    jr ra
```
#### bf16_div Test Cases
> GitHub: [bf16_div_test](https://github.com/dorobouharu133/ca2025-quizzes/blob/main/bf16_div/bf16_div_test.S)
```
// Improved Approach
Cycles:            643
Instrs. retired:   465 
CPI:              1.38
IPC:             0.723
Clock rate:  912.06 Hz
```
**Performance:** My improved approach is about **2.3x faster** than the compiler-optmized version.
**Code Size:** Compared to the compiler-optimized version, my improved approach reduces the code size by nearly **36%**.

#### division improvement
```c=
    for (int i = 0; i < 16; i++) {
        quotient <<= 1;
        if (dividend >= (divisor << (15 - i))) {
            dividend -= (divisor << (15 - i));
            quotient |= 1;
        }
    }
```
**Observe:** In my previoud improved approach, this part I shift right divisor at each iteration, but this logic can be simplifed as below.
```c=
    for (int i = 0; i < 16; i++) {
        quotient <<= 1;
        dividend << 1;
        if (dividend >= divisor) {
            dividend -= divisor;
            quotient |= 1;
        }
    }
```
We can shift the dividend to left in each iteration instead of shifing divisor. This allows us to **avoid calculating** `(15-i)` and performing a dynamic shift.
```asm=
bf16_div_division: # should be optimized
    # t6: loop times
    # s1: dividend
    # s2: divisor
    # s3: quotient
    # s4: counter
    slli s1, t4, 15 # dividend = mant_a << 15
    addi s2, t5, 0   # divisor = mant_b
    addi s3, x0, 0   # quotient = 0
    addi t6, x0, 16  # loop times = 16
    addi s4, x0, 0   # counter = 0
bf16_div_division_loop:
    bge s4, t6, bf16_div_division_loop_end
    slli s3, s3, 1   # quotient <<= 1
    addi t4, x0, 15
    sub t4, t4, s4   # t4 = 15 - i
    sll t4, s2, t4  # temp = divisor << (15 - i)

    blt s1, t4, bf16_div_division_loop_sub_skip
bf16_div_division_loop_sub:
    sub s1, s1, t4 # dividend -= (divisor << (15 - i))
    ori s3, s3, 1   # quotient |= 1
bf16_div_division_loop_sub_skip:
    addi s4, s4, 1   # i++
    jal x0, bf16_div_division_loop
```
In order to shift the dividend, we have to adjust the initialization for the dividend and the divisor.
- The dividend: Initialize with `mant_a`. 
> We shift left **gradually inside the loop** instead of shifting 15 bits **all at once**.
- The divisor: Initialize with `mant_b << 1`.
> Since the dividend gets shifted left **left** inside the loop, we have to pre-shift the divisor by 1 bit. Otherwise, the comparision **will be off**.
```asm=
bf16_div_division:
    # t6: loop times
    # s1: dividend
    # s2: divisor
    # s3: quotient
    # s4: counter
    addi s1, t4, 0   # dividend = mant_a
    slli s2, t5, 1   # divisor = mant_b << 1
    addi s3, x0, 0   # quotient = 0
    addi t6, x0, 16  # loop times = 16
    addi s4, x0, 0   # counter = 0
bf16_div_division_loop:
    bge s4, t6, bf16_div_division_loop_end
    slli s3, s3, 1   # quotient <<= 1
    slli s1, s1, 1    # dividend <<= 1

    blt s1, s2, bf16_div_division_loop_sub_skip
bf16_div_division_loop_sub:
    sub s1, s1, s2 # dividend -= divisor
    ori s3, s3, 1   # quotient |= 1
bf16_div_division_loop_sub_skip:
    addi s4, s4, 1   # i++
    jal x0, bf16_div_division_loop
```
I reduced the loop body from 15 to 13 instructions. Since the loop **iterates 16 times**, this results in a **total reduction of 32 dynamic instructions**.
> GitHub: [bf16_div_loop_improved](https://github.com/dorobouharu133/ca2025-quizzes/blob/main/bf16_div/bf16_div.S)
```
// Loop Improved Approach
Cycles:            579
Instrs. retired:   401 
CPI:              1.44
IPC:             0.693
Clock rate:  619.25 Hz
```
**Performance:** My latest improved approach is about **1.11x faster** than the previous improved version, and **2.55x faster** than the compiler-optmized version.
___
### ==Other functions==
```asm=
.data
newline:    .string "\n"

.text
.globl main
.globl bf16_isnan
.globl bf16_isinf
main:
    addi a0, x0, 0x40
    slli a0, a0, 8
    ori a0, a0, 0x49
    slli a0, a0, 8
    ori a0, a0, 0x0F
    slli a0, a0, 8
    ori a0, a0, 0xD0
    jal ra, f32_to_bf16     
    
    addi s0, a0, 0              
    
    addi a7, x0, 1               
    addi a0, s0, 0
    ecall

    la a0, newline
    addi a7, x0, 4
    ecall

    addi a7, x0, 10
    ecall

bf16_isnan:
    addi t0, x0, 0x7F
    slli t0, t0, 8
    ori t0, t0, 0x80			# BF16_EXP_MASK
    and t1, a0, t0			# a.bits & BF16_EXP_MASK
    bne t1, t0, bf16_isnan_return_false

    andi t1, a0, 0x007F	# a.bits & BF16_MANT_MASK
    beq t1, x0, bf16_isnan_return_false # mantissa == 0 

bf16_isnan_return_true:
    addi a0, x0, 1
    jr ra
    
bf16_isnan_return_false:
    addi a0, x0, 0
    jr ra
    

bf16_isinf:
    addi t0, x0, 0x7F
    slli t0, t0, 8
    ori t0, t0, 0x80			# BF16_EXP_MASK
    and t1, a0, t0			# a.bits & BF16_EXP_MASK
    bne t1, t0, bf16_isinf_return_false

    andi t1, a0, 0x007F	# a.bits & BF16_MANT_MASK
    bne t1, x0, bf16_isinf_return_false # mantissa != 0

bf16_isinf_return_true:
    addi a0, x0, 1
    jr ra
    
bf16_isinf_return_false:
    addi a0, x0, 0
    jr ra
    
bf16_iszero:
    addi t0, x0, 0x7F
    slli t0, t0, 8
    ori t0, t0, 0xFF
    and t1, a0, t0
    beq t1, x0, bf16_iszero_return_true
    
bf16_iszero_return_false:
    addi a0, x0, 0
    jr ra
    
bf16_iszero_return_true: 
    addi a0, x0, 1
    jr ra

f32_to_bf16:
    srli t0, a0, 23 # f32bits >> 23
    andi t0, t0, 0xFF
    addi t1, x0, 0xFF
    beq t0, t1, f32_to_bf16_return_if_equal # if(((f32bits >> 23) & 0xFF) == 0xFF) return

f32_to_bf16_return:
    srli t0, a0, 16
    andi t0, t0, 1
    addi t1, x0, 0x7F
    slli t1, t1, 8
    ori t1, t1, 0xFF
    add t0, t0, t1
    add a0, a0, t0
    
    srli a0, a0, 16
    and a0, a0, t1 
    jr ra
f32_to_bf16_return_if_equal:
    srli a0, a0, 16
    and a0, a0, t1
    jr ra
```
> I think this piece of code can be directly translated into RISC-V instructions, since the original C code is already very concise.

#### Test Cases
```
    1. bf16_isnan:  0x7FC1
    2. bf16_isinf:  0x7F80
    3. bf16_iszero: 0x0000
    4. f32_to_bf16: 0x40490FD0
```
```
// My approach
Cycles:             80
Instrs. retired:    80
CPI:                 1
IPC:                 1
Clock rate:        0Hz
```
Above is the execution info of my approach.
Below is the execution info of compiler.
```
// Compiler-optimized
Cycles:            132
Instrs. retired:   132
CPI:                 1
IPC:                 1
Clock rate:        0Hz
```
My approach is **1.65x faster** than compiler's version.

## Use Cases
### [LeetCode #973 K Closest Points to Origin](https://leetcode.com/problems/k-closest-points-to-origin/description/)
In [LeetCode #973](https://leetcode.com/problems/k-closest-points-to-origin/description/), we have to process a large amount of coordinate data. In real-world scenarios, such as on a drone with limited memory, using **uf8-encoding** allows us to convert 32-bit data into 8-bit. This reduces memory usage greatly, allowing the device to **store 4 times more data** in the same amount of Memory.

# Requirement 3
## [Branchless 16 bit CLZ](https://github.com/dorobouharu133/ca2025-quizzes/blob/main/branchless_clz/branchless_16_bit_clz.S)
```asm=
    li a0, 0x30
    jal branchless_16_bit_clz

# a0: mant_a
# t0: x
# t1: s
# t2: shift
# t3: temp
# t4: temp2
branchless_16_bit_clz:
    addi sp, sp, -20
    sw t0, 0(sp)
    sw t1, 4(sp)
    sw t2, 8(sp)
    sw t3, 12(sp)
    sw t4, 16(sp)
    
    addi t0, a0, 0  # x = mant_a
    addi t1, x0, 0  # s = 0
    addi t2, x0, 0  # shift = 0

    addi t3, x0, 0x00FF
    slt t1, t3, t0 # s = (x > 0x00FF) ? 1 : 0
    xori t1, t1, 1 # s = (x <= 0x00FF) ? 1 : 0
    slli t4, t1, 3
    add t2, t2, t4 # shift += (s << 3)
    sll t0, t0, t4 # x <<= (s << 3)

    addi t3, x0, 0xF
    slli t3, t3, 8
    ori t3, t3, 0xFF
    slt t1, t3, t0 # s = (x > 0x0FFF) ? 1 : 0
    xori t1, t1, 1 # s = (x <= 0x0FFF) ? 1 : 0
    slli t4, t1, 2
    add t2, t2, t4 # shift += (s << 2)
    sll t0, t0, t4 # x <<= (s << 2)

    addi t3, x0, 0x3F
    slli t3, t3, 8
    ori t3, t3, 0xFF
    slt t1, t3, t0 # s = (x > 0x3FFF) ? 1 : 0
    xori t1, t1, 1 # s = (x <= 0x3FFF) ? 1 : 0
    slli t4, t1, 1
    add t2, t2, t4 # shift += (s << 1)
    sll t0, t0, t4 # x <<= (s << 1)

    addi t3, x0, 0x7F
    slli t3, t3, 8
    ori t3, t3, 0xFF
    slt t1, t3, t0 # s = (x > 0x7FFF) ? 1 : 0
    xori t1, t1, 1 # s = (x <= 0x7FFF) ? 1 : 0
    slli t4, t1, 0
    add t2, t2, t4 # shift += (s << 0)
    sll t0, t0, t4 # x <<= (s << 0)

    addi a0, t2, 0  # return shift

    lw t0, 0(sp)
    lw t1, 4(sp)
    lw t2, 8(sp)
    lw t3, 12(sp)
    lw t4, 16(sp)
    addi sp, sp, 20

    jr ra
```

```asm=
    slt t1, t3, t0 # s = (x > 0x00FF) ? 1 : 0
    xori t1, t1, 1 # s = (x <= 0x00FF) ? 1 : 0
    slli t4, t1, 3
```
![image](https://hackmd.io/_uploads/SJ4r2mk4Ze.png)
**IF (Instruction Fetch):**
> PC Enable: 1 (High), since there is no pipeline stall
> Next PC Mux: 0 (Low), PC = PC＋４，because the instruction in ID is not branch.

**ID (Instruction Decode):**
> Reg Wr En: 1 (High), because the instruction in **WB** stage is `addi`, `addi` will write data back to rigister file (x5 register). 

**EX (Execute):**
> ALUOp1: from register file or forwarding path.
> ALUOp2: from immediate.
> ForwardA: (no forwarding), from ID/EX pipeline register.
> ForwardB: (no forwarding), from ID/EX pipeline register.
> Branch: not taken.

**MEM (Memory):**
> Data Memory Wr En: The instruction in **MEM** stage is `addi`, `addi` does not access data memory, therefore **Data Memory Wr En is 0 (Low)**.

**WB (Write Back):**
> WB Mux: from ALU result, since the instruction in WB is `addi`.

---
![image](https://hackmd.io/_uploads/ry-5bXkEZe.png)
**IF:** 
> PC Enable: 1 (High), since there is no pipeline stall
> Next PC Mux: 0 (Low), PC = PC＋４，because the instruction in ID is not branch.

**ID:**
> Reg Wr En: 1 (High), because the instruction in **WB** stage is `addi`, `addi` will write data back to rigister file (x6 register). 

**EX:**
> ALUOp1: from register file or forwarding path.
> ALUOp2: from immediate.
> ForwardA: (no forwarding), from ID/EX pipeline register.
> ForwardB: (no forwarding), from ID/EX pipeline register.
> Branch: not taken.

**MEM:**
> Data Memory Wr En: The instruction in **MEM** stage is `addi`, `addi` does not access data memory, therefore **Data Memory Wr En is 0 (Low)**.

**WB:**
> WB Mux: from ALU result, since the instruction in WB is `addi`.

---
![image](https://hackmd.io/_uploads/SyaX7Nk4bl.png)
**IF:**
> PC Enable: 1 (High), since there is no pipeline stall
> Next PC Mux: 0 (Low), PC = PC＋４，because the instruction in ID is not branch.

**ID:**
> Reg Wr En: 1 (High), because the instruction in **WB** stage is `addi`, `addi` will write data back to rigister file (x7 register). 

**EX:** (Forwarding Happens)
> ALUOp1: from register file or forwarding path.
> ALUOp2: from register file or forwarding path.
> ForwardA: (**forwarding**), from **EX/MEM** pipeline register.
> ForwardB: (no forwarding), from ID/EX pipeline register.
> Branch: not taken.

**MEM:**
> Data Memory Wr En: The instruction in **MEM** stage is `addi`, `addi` does not access data memory, therefore **Data Memory Wr En is 0 (Low)**.

**WB:**
> WB Mux: from ALU result, since the instruction in WB is `addi`.

![image](https://hackmd.io/_uploads/BkEZNEkEbg.png)
![image](https://hackmd.io/_uploads/Sk7NEN14Zl.png)
![image](https://hackmd.io/_uploads/ry4SVEJNbg.png)

> Because the x28 is litte than x5, so the result is, and will write back to register file (x6) when `slt` instruction is in WB stage.

---
![image](https://hackmd.io/_uploads/r1Mh-myE-x.png)
**IF:**
> PC Enable: 1 (High), since there is no pipeline stall
> Next PC Mux: 0 (Low), PC = PC＋４，because the instruction in ID is not branch.

**ID:**
> Reg Wr En: 1 (High), because the instruction in **WB** stage is `addi`, `addi` will write data back to rigister file (x28 register).

**EX:** (Forwarding happens)
> ALUOp1: from register file or forwarding path.
> ALUOp2: from immediate
> ForwardA: (**forwarding**), from **EX/MEM** pipeline register.
> ForwardB: (no forwarding), from ID/EX pipeline register.
> Branch: not taken.

**MEM:**
> Data Memory Wr En: The instruction in **MEM** stage is `slt`, `slt` does not access data memory, therefore **Data Memory Wr En is 0 (Low)**.

**WB:**
> WB Mux: from ALU result, since the instruction in WB is `addi`.

> With forwarding from EX/MEM pipeline register, the result of `xori x6, x6, 1` is the negative of `x6`, and `0 xor 0 = 1`. Therefore, `1` will be write back to x6 when the `xori` instruction is in **WB stage**.
---
![image](https://hackmd.io/_uploads/Hkp3WXkN-x.png)
**IF:**
> PC Enable: 1 (High), since there is no pipeline stall
> Next PC Mux: 0 (Low), PC = PC＋４，because the instruction in ID is not branch.

**ID:**
> Reg Wr En: 1 (High), because the instruction in **WB** stage is `addi`, `addi` will write data back to rigister file (x6 register).

**EX:** (forwarding happens)
> ALUOp1: from register file or forwarding path.
> ALUOp2: from immediate.
> ForwardA: (**forwarding**), from **EX/MEM** pipeline register.
> ForwardB: (no forwarding), from ID/EX pipeline register.
> Branch: not taken.

**MEM:**
> Data Memory Wr En: The instruction in **MEM** stage is `xori`, `xori` does not access data memory, therefore **Data Memory Wr En is 0 (Low)**.

**WB:**
> WB Mux: from ALU result, since the instruction in WB is `slt`.


---
![image](https://hackmd.io/_uploads/SJ26bQJVZx.png)
**IF:**
> PC Enable: 1 (High), since there is no pipeline stall
> Next PC Mux: 0 (Low), PC = PC＋４，because the instruction in ID is not branch.

**ID:**
> Reg Wr En: 1 (High), because the instruction in **WB** stage is `xori`, `xori` will write data back to rigister file (x6 register).

**EX:**
> ALUOp1: from register file or forwarding path.
> ALUOp2: from register file or forwarding path.
> ForwardA: (no forwarding), from ID/EX pipeline register.
> ForwardB: (**forwarding**), from **EX/MEM** pipeline register.
> Branch: not taken.

**MEM:**
> Data Memory Wr En: The instruction in **MEM** stage is `slli`, `slli` does not access data memory, therefore **Data Memory Wr En is 0 (Low)**.

**WB:**
> WB Mux: from ALU result, since the instruction in WB is `xori`.

> As mentioned before, the result of `xori x6, x6, 1` will write back to register file.
![image](https://hackmd.io/_uploads/SyzuOVJV-x.png)


In the next cycle, `x6` will be `0x00000001`.

---
![image](https://hackmd.io/_uploads/BJaC-X14be.png)

**IF:**
> PC Enable: 1 (High), since there is no pipeline stall
> Next PC Mux: 0 (Low), PC = PC＋４，because the instruction in ID is not branch.

**ID:**
> Reg Wr En: 1 (High), because the instruction in **WB** stage is `slli`, `slli` will write data back to rigister file (x29 register).

**EX:** (forwarding happens)
> ALUOp1: from register file or forwarding path.
> ALUOp2: from register file or forwarding path.
> ForwardA: (no forwarding), from ID/EX pipeline register.
> ForwardB: (**forwarding**), from **MEM/WB** pipeline register.
> Branch: not taken.

**MEM:**
> Data Memory Wr En: The instruction in **MEM** stage is `add`, `add` does not access data memory, therefore **Data Memory Wr En is 0 (Low)**.

**WB:**
> WB Mux: from ALU result, since the instruction in WB is `slli`.

![image](https://hackmd.io/_uploads/Sk8hdEJVWl.png)
Check: `x6` is `1`, the function is correct.

# References
[RISCV branchless coding - *stackoverflow*](https://stackoverflow.com/questions/72340698/riscv-branchless-coding)
[RISCV assembly 32bit multiplication without MUL giving incorrect result - *stackoverflow*](https://stackoverflow.com/questions/79503254/riscv-assembly-32bit-multiplication-without-mul-giving-incorrect-result)
[Intel® 64 and IA-32 Architectures Optimization Reference Manual Volume 1
](https://www.intel.com/content/www/us/en/content-details/671488/intel-64-and-ia-32-architectures-optimization-reference-manual-volume-1.html)
# AI Usage
[Copilot](https://copilot.microsoft.com/shares/iWjxqjKuh8HA6NGhFfUZD)
[Copilot, correct my test function to output the encode and decode values](https://copilot.microsoft.com/shares/pAcS6KRjp4fjSTUFdP3KN)
[ChatGPT](https://chatgpt.com/share/68f2559b-b4f0-8006-a075-d2c62339c95f)
[Copilot, bf16_mul debug](https://copilot.microsoft.com/shares/dz4MNC8W3mtAYefiprkGN)
[ChatGPT, bf16_mul debug](https://chatgpt.com/share/68f79767-7fb0-8006-8ac0-e30787814397)
[Gemini, bf16_add proofreading](https://gemini.google.com/share/8f267b63f019)
[Gemini, bf16_add test cases](https://gemini.google.com/share/f34265e85ffd)
[Gemini, bf16_sqrt proofreading](https://gemini.google.com/share/a882f07040c2)
[Gemini, bf16_mul proofreading](https://gemini.google.com/share/8ccf0e0f70a8)
[Gemini, Branchless Programming](https://gemini.google.com/share/f0e56a89944b)