# Lab2: RISC-V `RV32I[MA]` emulator with ELF support
###### tags: `108-1_RISC-V`
## [Count leading zero](https://hackmd.io/@WeiCheng14159/rkUifs2Hw)
Problem Definition: Given a 32 bit unsigned integer, this function counts the number of leading zeros in that integer. The C code implementation is as follow.
The following assembly program was implemented by 鄭惟同學.
(link in the title)

.data
input:	  .word 0x0000000f
one: 	  .word 0x80000000
str1:     .string "clz value of "
str2:     .string " is "

.text
main:
        lw  a0, input   # Load input from static data
        jal ra, clz     # Jump-and-link to the 'clz' label

        # Print the result to console
        mv  a1, a0
        lw  a0, input
        jal ra, printResult

        # Exit program
        li a7, 10
        ecall

clz: 
# t0 = one
# t1 = cnt = 32
# t2 = res
# a0 = i
        lw   t0, one 
        li   t1, 32
        li   t2, 0
_beg:   bne  t1, zero, cnt
_ret:   mv   a0, t2
        ret
cnt:    addi t1,t1,-1
        and  t3, a0, t0 # i & one
        bne  t3, zero, _ret		
        addi t2, t2, 1
        srli t0, t0, 1
        j _beg

# --- printResult ---
# a0: input
# a1: result
printResult:
        mv t0, a0
        mv t1, a1
        la a0, str1
        li a7, 4
        ecall
        mv a0, t0
        li a7, 1
        ecall
        la a0, str2
        li a7, 4
        ecall
        mv a0, t1
        li a7, 1
        ecall
        ret

#### Rewrite Count leading zero function in C
main() was replaced by _start() meaning that the code will start at this position.

#include<stdio.h>
int _start(){
    unsigned int one = 0x80000000;
    unsigned int res = 0;
    unsigned int i   = 0x00000400;
    for (int count = 0; count < 32; count++) {
        if ((i & one) == 0)
            res++;
        one = one >> 1;
    }

    volatile char *tx = (volatile char *) 0x40002000;
   *tx = res;  

   return 0;
}

### run it

./emu-rv32i CountLeadingZero

>>> Execution time: 15509 ns
>>> Instruction count: 201 (IPS=12960216)
>>> Jumps: 32 (15.92%) - 0 forwards, 32 backwards
>>> Branching T=31 (96.88%) F=1 (3.12%)

---
### objdump

I see the generated code which print out the result not very effect to the length of the code. Therefore, i decide not to use the not print out result code for compare

00010054 <_start>:
   10054:       fd010113                addi    sp,sp,-48
   10058:       02812623                sw      s0,44(sp)
   1005c:       03010413                addi    s0,sp,48
   10060:       800007b7                lui     a5,0x80000
   10064:       fef42623                sw      a5,-20(s0)
   10068:       fe042423                sw      zero,-24(s0)
   1006c:       40000793                li      a5,1024
   10070:       fef42023                sw      a5,-32(s0)
   10074:       fe042223                sw      zero,-28(s0)
   10078:       0380006f                j       100b0 <_start+0x5c>
   1007c:       fe042703                lw      a4,-32(s0)
   10080:       fec42783                lw      a5,-20(s0)
   10084:       00f777b3                and     a5,a4,a5
   10088:       00079863                bnez    a5,10098 <_start+0x44>
   1008c:       fe842783                lw      a5,-24(s0)
   10090:       00178793                addi    a5,a5,1 # 80000001 <__global_pointer$+0x7ffee719>
   10094:       fef42423                sw      a5,-24(s0)
   10098:       fec42783                lw      a5,-20(s0)
   1009c:       0017d793                srli    a5,a5,0x1
   100a0:       fef42623                sw      a5,-20(s0)
   100a4:       fe442783                lw      a5,-28(s0)
   100a8:       00178793                addi    a5,a5,1
   100ac:       fef42223                sw      a5,-28(s0)
   100b0:       fe442703                lw      a4,-28(s0)
   100b4:       01f00793                li      a5,31
   100b8:       fce7d2e3                bge     a5,a4,1007c <_start+0x28>
   100bc:       400027b7                lui     a5,0x40002
   100c0:       fcf42e23                sw      a5,-36(s0)
   100c4:       fe842783                lw      a5,-24(s0)
   100c8:       0ff7f713                andi    a4,a5,255
   100cc:       fdc42783                lw      a5,-36(s0)
   100d0:       00e78023                sb      a4,0(a5) # 40002000 <__global_pointer$+0x3fff0718>
   100d4:       00000793                li      a5,0
   100d8:       00078513                mv      a0,a5
   100dc:       02c12403                lw      s0,44(sp)
   100e0:       03010113                addi    sp,sp,48
   100e4:       00008067                ret

---
### readelf

ELF Header:
Magic: 7f 45 4c 46 01 01 01 00 00 00 00 00 00 00 00 00
Class: ELF32
Data: 2's complement, little endian
Version: 1 (current)
OS/ABI: UNIX - System V
ABI Version: 0
Type: EXEC (Executable file)
Machine: RISC-V
Version: 0x1
Entry point address: 0x10054
Start of program headers: 52 (bytes into file)
Start of section headers: 624 (bytes into file)
Flags: 0x0
Size of this header: 52 (bytes)
Size of program headers: 32 (bytes)
Number of program headers: 1
Size of section headers: 40 (bytes)
Number of section headers: 6
Section header string table index: 5

---
### size    

   text    data     bss     dec     hex filename
    148       0       0     148      94 CountLeadingZero

---

:::success
### Optimization comparison
| Compile | without optimization | with -O1 | with -O2 | with -O3 |
| ----------------- | -------- | -------------------- | --- | ---------------- |
| Execution Time(ns)| 40663 | 18990 | 16583| 15509 |
| Total instruction | 534 | 201 | 201| 201 |
| Jump | 35 | 32 | 32| 32 |
| Jump forwards | 2 | 0 | 0 | 0 |
| Jump backwards | 33 | 32 | 32| 32 |
| Branch True | 33 | 31 | 31| 31 |
| Branch False | 32 | 1 | 1 | 1 |

:::