# 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)