# Lab1: RV32I Simulator
###### tags: `Computer Architecture 2022`
## Problem
### Find Numbers with Even Number of Digits
This problem is based on [LeetCode1295](https://leetcode.com/problems/find-numbers-with-even-number-of-digits/). Given a array of integers, return how many of them contain an even number of digits.
### example 1
```
Input: nums = [12,345,2,6,7896]
Output: 2
Explanation:
12 contains 2 digits (even number of digits).
345 contains 3 digits (odd number of digits).
2 contains 1 digit (odd number of digits).
6 contains 1 digit (odd number of digits).
7896 contains 4 digits (even number of digits).
Therefore only 12 and 7896 contain an even number of digits.
```
### example 2
```
Input: nums = [555,901,482,1771]
Output: 1
Explanation:
Only 1771 contains an even number of digits.
```
## Solution
If you want to know how many digits are in a number, you just need to compare it with the smallest number in "x-digit numbers".If the result is greater than, then add one to x, if it is less than it means that the number has only x-1 or less digits.
## C Code
```cpp
#include <stdio.h>
int arr1[5] = {11, 2, 52, 14, 62};
int arr2[4] = {95, 8711, 26, 6};
int arr3[3] = {19, 137, 55, 77, 33, 22};
int size1 = 5;
int size2 = 4;
int size3 = 6;
int calculate(int a){
int base = 10;
int digit = 1;
while(a>=base){
digit = digit+1;
base = (base<<3)+(base<<1);
}
return digit;
}
int findNumbers(int* nums, int size){
int i, val;
val=0;
for(i=0; i<size; i++){
if((calculate(nums[i])&1)==0){
val=val+1;
}
}
return val;
}
int main(void){
int save;
save = findNumbers(arr1, size1);
printf("The array has %d even digit numbers.\n", save);
save = findNumbers(arr2, size2);
printf("The array has %d even digit numbers.\n", save);
save = findNumbers(arr3, size3);
printf("The array has %d even digit numbers.\n", save);
return 0;
}
```
I have prepared three test data, respectively, arr1, arr2, arr3 three arrays, size1, size2, size3 are their corresponding sizes.
```cpp
int calculate(int a){
int base = 10;
int digit = 1;
while(a>=base){
digit = digit+1;
base = (base<<3)+(base<<1);
}
return digit;
}
```
The function "calculate" counts the digits of the input number by comparing it with 10, 100, 1000... and return the value.
```cpp
int findNumbers(int* nums, int size){
int i, val;
val=0;
for(i=0; i<size; i++){
if((calculate(nums[i])&1)==0){
val=val+1;
}
}
return val;
}
```
The function "findNumbers" receives the return value from the function "calculate" and use the bitwise operation with 1 to decide if it's odd or even.
## Assembly code
### prototype
```cpp
.data
arr1: .word 11, 2, 52, 14, 62
arr2: .word 95, 8711, 26, 6
arr3: .word 19, 137, 55, 77, 33, 22
size1: .word 5
size2: .word 4
size3: .word 6
startline: .string "The array has "
endline: .string " even digit numbers.\n"
.text
main:
la a0, arr1 # a0=arr
la a1, size1
lw a1, 0(a1) # a1=size1
jal ra, findNumbers
jal ra, print
la a0, arr2 # a0=arr
la a1, size2
lw a1, 0(a1) # a1=size2
jal ra, findNumbers
jal ra, print
la a0, arr3 # a0=arr
la a1, size3
lw a1, 0(a1) # a1=size3
jal ra, findNumbers
jal ra, print
j exit
findNumbers:
li t0, 0 # val=0
li t1, 0 # i=0
FLOOP:
bge t1, a1, FEND #i>=arrsize
slli t2, t1, 2 # t2=i*4
add t2, a0, t2 # t2=arr+i
lw t2, 0(t2) #t2=arr[i]
addi sp, sp, -20
sw ra, 16(sp) # save ra
sw a0, 12(sp) # save a0
sw t0, 8(sp) # save t0
sw t1, 4(sp) # save t1
sw t2, 0(sp) # save t2
mv a0, t2 # a0=arr[i]
jal ra, calculate # do calculate function
mv s0, a0
lw t2, 0(sp) # load t2
lw t1, 4(sp) # load t1
lw t0, 8(sp) # load t0
lw a0, 12(sp) # load a0
lw ra, 16(sp) # load ra
addi sp, sp, 20
andi t3, s0, 1 # and(s0,1)
bne t3, zero, IFEND
addi t0, t0, 1 # val=val+1
IFEND:
addi t1, t1, 1 # i=i+1
j FLOOP
FEND:
mv a0, t0 # return val
ret
calculate:
li t0, 10 # base=10
li t1, 1 # digit=1
WLOOP:
blt a0, t0, WEND
addi t1, t1, 1 # digit=digit+1
slli t2, t0, 1 # t2=base<<1
slli t0, t0, 3 # t0=base<<3
add t0, t0, t2 # t0=base<<3+base<<1
j WLOOP
WEND:
mv a0, t1
ret
print:
mv s0, a0
la a0, startline
li a7, 4
ecall
mv a0, s0
li a7, 1
ecall
la a0, endline
li a7, 4
ecall
ret
exit:
li a7, 10
ecall
```
### new version
```cpp
.data
arr1: .word 11, 2, 52, 14, 62
arr2: .word 95, 8711, 26, 6
arr3: .word 19, 137, 55, 77, 33, 22
base: .word 10, 100, 1000, 10000, 100000
size1: .word 5
size2: .word 4
size3: .word 6
startline: .string "The array has "
endline: .string " even digit numbers.\n"
.text
main:
la a0, arr1 # a0=arr
la a1, size1
lw a1, 0(a1) # a1=size1
jal ra, findNumbers
la a0, arr2 # a0=arr
la a1, size2
lw a1, 0(a1) # a1=size2
jal ra, findNumbers
la a0, arr3 # a0=arr
la a1, size3
lw a1, 0(a1) # a1=size3
jal ra, findNumbers
j exit
findNumbers:
li t0, 0 # val=0
li t1, 0 # i=0
FLOOP:
bge t1, a1, FEND #if i<arrsize the branch isn't taken
slli t2, t1, 2
add t2, a0, t2 # t2=arr+i
lw t2, 0(t2) #t2=arr[i]
li t4, 0
li s0, 1
la s1, base
WLOOP:
add t5, t4, s1
lw t5, 0(t5)
blt t2, t5, WEND
addi t4, t4, 4
addi s0, s0, 1
j WLOOP
WEND:
andi t3, s0, 1 # and(s0,1)
bne t3, zero, IFEND
addi t0, t0, 1 # val=val+1
IFEND:
addi t1, t1, 1 # i=i+1
j FLOOP
FEND:
la a0, startline
li a7, 4
ecall
mv a0, t0
li a7, 1
ecall
la a0, endline
li a7, 4
ecall
ret
exit:
li a7, 10
ecall
```
:::warning
:warning: Can you use fewer instructions?
:notes: jserv
:::
In made two version of my assembly code. One is the prototype which is nearly directly translated by the c code and the revised new version. In the new version, I canceled the stack operation part since my remaining registers are enough and concatenated the findNumbers, calculate and print function to reduce the function call frequency. In the calculation function part, I replaced the base updating step by using a prepared table {10, 100, 1000...}. However, this doesn't really reduce the instruction counts since you have to save the index value additionally while using the prepared table.
:::warning
check https://github.com/sysprog21/bignum/blob/master/format.c for the technique of precomputed radix.
:notes: jserv
:::
### output
```
The array has 4 even digit numbers.
The array has 3 even digit numbers.
The array has 5 even digit numbers.
Program exited with code: 0
```
## Pipeline feature in Ripes
```cpp
la a0, arr1 # a0=arr
```
Take the first line of the assembly code as example.
```cpp
auipc x10 0x10000
```
The first line of the code would be transformed as the assembly code into the code above since la is merely a psuedo instruction convenient for the programmer to identify the function. And let us focus on how it works in the pipeline.
### IF stage
In IF stage, the output of the program counter accesses the instruction memory and fetch the instruction.The program counter also selects the the signal that add the currect pc by 4 (one word is 4 byte) as the next pc in this case.
### ID stage
In ID stage, the instruction auipc doesn't need to catch the data from register file, so the both register source are 0, but the register destination is necessary, so the address of x10(0x0a) is exported. 0x10000 would be the input of the Imm and the output should be 0x10000 << 12 = 0x10000000 according to the definition of AUIPC instruction.
### EX stage
Apparently, there are no data hazard in this instruction since it's the first instruction, so the two left side multiplexers all chose the middle(register file output) input as the output. However, the ALU source of the instruction AUIPC is the pc current and the immediate, so the two right side multiplexers just chose the inputs from the IDEX pipeline register as the output, and the output of ALU would be 0x00000000+0x10000000=0x10000000 as result.
### MEM stage
We don't need to access data memory for the auipc instruction, so the output of the ALU and the register destination address just passed this stage and save their value to MEM/WB register.The Write enable signal, of course, is zero.
### WB stage
The output of the multiplexer would be the ALU output 0x10000000 and the register destination is 0x0a, these values would be transfered to the Registers unit to save 0x10000000 into x10 regitster.
### Memory update steps
```cpp
addi sp, sp, -20
sw ra, 16(sp) # save ra
sw a0, 12(sp) # save a0
sw t0, 8(sp) # save t0
sw t1, 4(sp) # save t1
sw t2, 0(sp) # save t2
mv a0, t2 # a0=arr[i]
jal ra, calculate # do calculate function
mv s0, a0
lw t2, 0(sp) # load t2
lw t1, 4(sp) # load t1
lw t0, 8(sp) # load t0
lw a0, 12(sp) # load a0
lw ra, 16(sp) # load ra
addi sp, sp, 20
```
Let's take those assembly codes above to explain the memory update steps.
First, we can see that the memory address of the stack pointer is 0x7ffffff0, after the WB stage, its value would be 0x7fffffdc (minus 20).
In the memory viewer, we can see that the five words between address 0x7fffffdc to 0x7fffffec were actually been accessed, their saved value were 0x00000018, 0x10000000, 0x00000000, 0x00000000, 0x0000000b respectively.
After the function calculate returned, we can see that the stack pointer register also returned to 0xfffffff0
The ra, a0, t0, t1, t2 register value are 0x00000018, 0x10000000, 0x00000000, 0x00000000, 0x0000000b respectively, which is match with the saved values in the stack section of the memory.
Sign in with Wallet
Connect another wallet