# Lab1: Assignment1: RISC-V Assembly and Instruction
## Case Problem
Write an algorithm to determine if a number n is happy.
A happy number is a number defined by the following process:
* Starting with any positive integer, replace the number by the sum of the squares of its digits.
* Repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1.
* Those numbers for which this process ends in 1 are happy.
Return true if n is a happy number, and false if not.
> Example 1
> Input: n = 19
> Output: true
> Example 2
> Input: n = 2
> Output: false
## Happy Number Theorem
A Happy Number n is defined by the following process. Starting with n, replace it with the sum of the squares of its digits, and repeat the process until n equals 1, or it loops endlessly in a cycle which does not include 1. Those numbers for which this process ends in 1 are Happy Numbers, while those that do not end in 1 are unhappy numbers.
First few happy numbers are 1, 7, 10, 13, 19, 23, 28, 31, 32, 44, 49, 68, 70, 79, 82, 86, 91, 94, 97, 100
## Solution
On this case, we repeated do sum of squares of digits. While doing so, we keep track of visited numbers using a hash. If we reach 1, we return true. Else if we reach a visited a number, we return false. One important observation is, the cycle always contains 4. So we don’t need to keep track of all numbers. We can simply check for 4.
## Approach
approach for solving this problem using no extra space. A number cannot be a happy number if, at any step, the sum of the square of digits obtained is a single-digit number except 1 or 7. This is because 1 and 7 are the only single-digit happy numbers. Using this information, we can develop an approach as shown in the code below.
> Input: n = 19
> Output: True
> 19 is Happy Number,
> 1^2 + 9^2 = 82
> 8^2 + 2^2 = 68
> 6^2 + 8^2 = 100
> 1^2 + 0^2 + 0^2 = 1
> As we reached to 1, 19 is a Happy Number.
> Input: n = 2
> Output: False
> Because 2 does not include a happy number
## C Code Implement for Happy Number
```
#include<stdio.h>
int main()
{
int n = 2 ,sum,rem;
while(n>0)
{
rem = n%10;
sum += rem * rem;
n=n/10;
if(n == 0 && sum >= 10)
{
n = sum;
sum = 0;
}
}
if(sum == 1){
printf("true");
}else{
printf("false");
}
}
```
## Assembly Code (Risc-V) Implement for Happy Number
```
.data
num: .word 19
str1: .string "true"
str2: .string "false"
.text
#a3 = num
#a2 = modulus data
#a1 = logical comparison data
#a4 = sum
main:
addi sp,sp,-16 # Add Immediate stack pointer
sw ra,12(sp) # store data in reg and store it to memory
lw a3,num # load integer data from num = 19, by the case of leetcode 202
li a2,10 # load immediate 10, this data for modulus operation
li a1,9 # load immediate 10, this data for sum decision sum>=10
exchange:
mv a4,a3 # n = sum
li a3,0 # sum = 0
operation:
rem a5,a4,a2 # rem = n%10
div a4,a4,a2 # n = n/10
mul a5,a5,a5 # multiplication rem * rem
add a3,a3,a5 #
bne a4,zero,operation # if n == 0 then will return to operation faunction
bgt a3,a1,exchange # if sum >= 10 then will process function
li a5,1 # load immediate 1, this data for sum == 1
beq a3,a5,true # if condition if(sum==1) then will return to true function
la a0, str2 # prepare to print string = false
li a7, 4 # print string
ecall
li a7, 10 # end program
ecall
false:
lw ra,12(sp) # load word form
li a0,0 # load immediate 0
addi sp,sp,16 #
li a7, 10 # end program
ecall
jr ra #
true:
la a0, str1 # prepare to print string = true
li a7, 4 # print string
ecall
j false # jump to false function if the condition false
```
## Result
1. C Code Result
*Input 19
*Input 2
3. Assembly Code(Risc-V) Result
*Input 19
*Input 2
## Pseudo Instruction
The Risc-V machine can actually execute, but the Ripes will replace the pseudo instruction with the real instruction. the ripes will demonstrate each line code to assembly address and translate it into 8-bit in heximal as below.
```
00000000 <main>:
0: ff010113 addi x2 x2 -16
4: 00112623 sw x1 12 x2
8: 10000697 auipc x13 0x10000
c: ff86a683 lw x13 -8 x13
10: 00a00613 addi x12 x0 10
14: 00900593 addi x11 x0 9
00000018 <exchange>:
18: 00068713 addi x14 x13 0
1c: 00000693 addi x13 x0 0
00000020 <operation>:
20: 02c767b3 rem x15 x14 x12
24: 02c74733 div x14 x14 x12
28: 02f787b3 mul x15 x15 x15
2c: 00f686b3 add x13 x13 x15
30: fe0718e3 bne x14 x0 -16 <operation>
34: fed5c2e3 blt x11 x13 -28 <exchange>
38: 00100793 addi x15 x0 1
3c: 02f68a63 beq x13 x15 52 <true>
40: 10000517 auipc x10 0x10000
44: fc950513 addi x10 x10 -55
48: 00400893 addi x17 x0 4
4c: 00000073 ecall
50: 00a00893 addi x17 x0 10
54: 00000073 ecall
00000058 <false>:
58: 00c12083 lw x1 12 x2
5c: 00000513 addi x10 x0 0
60: 01010113 addi x2 x2 16
64: 00a00893 addi x17 x0 10
68: 00000073 ecall
6c: 00008067 jalr x0 x1 0
00000070 <true>:
70: 10000517 auipc x10 0x10000
74: f9450513 addi x10 x10 -108
78: 00400893 addi x17 x0 4
7c: 00000073 ecall
80: fd9ff06f jal x0 -40 <false>
```
## Analysis
1. Instruction Fetch(IF)
First stage, processor will sent the instruction from PC with the address stored in PC from either the last instruction addr. Also, PC will add 4 for next instruction if there is no branch or jump instruction. Then, instruction will be fetched depending on the PC from the instr. memory.
* PC input the instruction address 0x00000004 to Instruction Memory
* The instruction memory output 0x00112623
* then, the data will distribute to ID pipeline register
2. Instruction Decode(ID)
this part the decoder will decode the instruction from PC as given before, then will determine the input of each MUX, andthe register file will be read to prepare for the next stage.
* instrution is decode, the output are :
> R1 : 0x20
> R2 : 0x10
* the output from R1 and R2 will sending to input register and the output value are :
> Reg1:0x7ffffff9
> Reg2:0x00000000.
3. Execute(EX)
* EX/IE are the stage is where the computation occurs, it's mean in this stage will execute all arithmetic and logical operation and memory address access calculation. The stage consists of ALU and Branch.
The ALU is responsible for computing the math operation, the boolean operation, and even the PC of the branch instruction. The Branch will use data from register to determine if the Branch taken or not.
* ALU will execute the addi instruction, based on the instruction there have the two operand 0x00000000 and 0x00000009 come from op1 and op2, then the result is 0x00000009.
> Op1 : 0x00000000
> Op2 : 0x00000009
> Result : 0x00000009
> ALU calculation process : Op1 + Op2 = Result
* In branch instruction will check the result is true/false to set the flag and change the PC as below.
4. Memory(MEM)
in MEM the data will be stored into memory or read the data from memory with the address calculated by ALU and at MEM stage we can use instruction access memory such as sw, lw, etc.
* Write/Read data with the data memory
* It has two signals MemRead and MemWrite which can distinguish between write and read operation.
* It’s decide the address of the memory according to opcode.
* based on my case, I have one sw instruction sw x1 12 x2, the instruction it will set MemWrite = true and then store 0x00000000， into addr. 0x7fffffec.
5. Write Back(WB)
Last stage is write back to register files,it will write back the result(from ALU calculation and data memory) into register files.
* the ALU output is 0x00000004 pass data memory and will go through multiplexer and write back to ID stage’s register files
* the data 0x00000004 will be store to the destination register in Register Files.
## References
[Leet Code 202 Problem "Happy Number"](https://leetcode.com/problems/happy-number/)
[Assignment Repository](https://github.com/jakariaaa27/2021_Fall_COMPUTER_ARCHITECTURE_HW1)
[Happy Number Theorem](https://en.wikipedia.org/wiki/Happy_number)
[Classic RISC pipeline](https://https://en.wikipedia.org/wiki/Classic_RISC_pipeline)
Sign in with Wallet
Connect another wallet