# Lab 4
Name: SHIVADHARSHAN S
Roll No.: CS22B057

---
## Question 1
**Code**

.data
arr: .word 1 2 3 4 5 6 7 8 9 10 11

.text
la a0 arr
addi a1 zero 10
addi a2 zero -1 # exit condition
addi a4 zero 3 # s
loop:
    beq a1 a2 exit
    lw a3 0(a0)
    add a3 a3 a4
    sw a3 0(a0)
    addi a0 a0 4
    addi a1 a1 -1
    j loop
exit:
    addi a7 zero 10
    ecall

**Memory Values Before**


**Memory Values After**


---

## Question 2
**Code**

.data
arr: .word 1 2 3 4 5 6 7 8 9 10 11 13 15
n: .word 13
str1: .string "true"
str2: .string "false"

.text
la a0 arr
la a1 n
lw a1 0(a1)
addi a2 zero 0
addi a7 zero 2
addi s2 zero 3
add a4 zero zero
loop:
    beq a1 a2 exit
    lw a3 0(a0)
    rem ra a3 a7
    beq ra a2 even
    addi a4 a4 1
    beq a4 s2 yes
    j noeven
    even:
        add a4 zero zero
    noeven:
        addi a0 a0 4
        addi a1 a1 -1
        j loop

exit:
    add x0 x0 x0
    j no

yes:
    la a0 str1
    addi a7 zero 4
    ecall
    j exit2
no:
    la a0 str2
    addi a7 zero 4
    ecall
exit2:
    addi a7 zero 10
    ecall

**Output**


---
## Question 3

*No constraint was given in leetcode regarding the use of extra memory.*

**Code**

.data
arr: .word 1 2 3 4 5 6 7 8 9 10 11 12 13 14
size: .word 14
arr2: .word 0
.text
la a0 arr
la t0 arr2
la ra size
addi x4 zero 4
lw ra 0(ra) # ra has 2n value
addi x2 zero 2
div ra ra x2 # n value
mul tp ra x4
add a1 a0 tp
add a4 zero zero
loop:
    beq ra a4 exit1
    lw a3 0(a0)
    lw a5 0(a1)
    sw a3 0(t0)
    addi t0 t0 4
    sw a5 0(t0)
    addi t0 t0 4
    addi a4 a4 1
    addi a0 a0 4
    addi a1 a1 4
    j loop
exit1:
    la a0 arr
    la ra size
    lw ra 0(ra)
    la t0 arr2
    add a4 zero zero
loop2:
    beq ra a4 exit
    lw a3 0(t0)
    sw a3 0(a0)
    addi a0 a0 4
    addi t0 t0 4
    addi a4 a4 1
    j loop2
exit:
    addi a7 zero 10
    ecall

**Memory Values Before**:


**Memory Values After**:


---
## Question 4
[Missing Number problem](https://leetcode.com/problems/missing-number/description)

**Code**

# Missing Number Problem From Leetcode
.data 
arr: .word 0 1 2 3
n: .word 4
str2: .string "Missing Number: "
.text
la ra n
lw ra 0(ra)
addi sp ra 1
mul t1 ra sp
addi s1 zero 2
div t1 t1 s1
la a1 arr


add a3 zero zero
loop:
    beq ra zero exit
    lw a2 0(a1)
    add a3 a3 a2
    addi a1 a1 4
    addi ra ra -1
    j loop 

exit:
     sub a3 t1 a3 
     la a0 str2
     addi a7 zero 4
     ecall
     add a0 zero a3
     addi a7 zero 1
     ecall
     addi a7 zero 10
     ecall

**Output**:

---
## Question 5

To implement linked list we first need to implement one node.
My implementation of node is a **data** and a **next pointer**, for this **two consecutive memory** address can be used.

The first memory location saves a 32 bit number as data. The next consecutive memory location saves the location of the next memory location to go to for finding the next node.

To create a linked list. We first create a **head** node. We save the head node in memory and also save the address of that memory in a register. In the next pointer in memory put **0x00000000** to mean **NULL**. Now to insert a new node, read from the register to go to head node, load the next pointer. if it is equal to x0 then you have to add the address of the new node here. Now save the new node anywhere in memory and save that address in this place.

Same way we have to find the instance of first NULL and then update it to the address of the new node to **insert** a node.

To **delete**, go to the node you want to delete, copy the next node's address and save it in a regiter, then copy this address into the next pointer of the previos node. This can be achieved by saving the location of the previous node's next pointer and then writing the new value to that location using **sw**.

**Searching** can be done trivially by just going to the next location in memory pointed by each node till we encounter the needed data or **NULL**.

Insert, delete and search can all be made into functions.

This implemenation assumes that the programmer will not create a node at **0x00000000**, which is true in RISC V.

___
## Question 6

Using the version of **malloc** provided, it won't be feasible to write a free function that takes only the pointer to the location to be freed. Instead I propose a modified malloc function as follows.

Whenever **malloc** is called, It will internally call sbrk with a bigger size argument (calling sbrk is expensive) but before returning the memory address, It will store the memory address and the size given to the user in a **in-use** hashmap. It will also store the remaining space available with it's start pointer in another **available** hashmap

When **free** is called, the function checks if the pointer provided is in the hashmap. If it is present, then the entry in the **in-use** hashmap is removed. Now this entry is added to the **available** hashmap.

This will approach will lead to **fragmentation** soon. One idea for overcoming that would be, whenever **free** is called, check if the adjacent memory is also in **available**. if yes then remove that entry and add a new entry spanning the whole free space. This however adds a overhead for every call of **free**. That would be the tradeoff of this design.
___