# Lab 4
Name: P Akilesh
Roll No.: CS22B040

---
## Question 1
**Given C program**

int s=3;
// initialize the 11 elements of array x to some random values
for(int i=10;i>=0;i=i-1){
    x[i] = x[i] + s;
}

**RISC-V Assembly Code of the above C program**

.data
array:  .word 11,10,9,8,7,6,5,4,3,2,1  
size:   .word 11          # Size of the array

.text
#variable s is considered in register x10
li x10,3    

#Lets consider the variable i in x11
li x11,10
#address is stored in x12
la x12,array
#temp address
mv x4,x12
addi x4,x4,40
j loop

loop:
    bgt x0,x11,exit
    lw x13,0(x4)
    add x13,x13,x10
    sw x13,0(x4)
    addi x4,x4,-4
    addi x11,x11,-1
    j loop
    
exit:
    li a7,10
    ecall

---
## Question 2
**RISC-V Assembly language for Three Consecutive Odd Question**

.data
array:  .word 1,2,34,3,4,5,7,23,12   # Array to be sorted
size:   .word 9                # Size of the array
true:   .string "true"
false:   .string "false"

.text   
#Output 1 means true and 0 means false
#address is stored in x12
la x12,array
#size in x11
lw x11,size
addi x11,x11,-2
#Lets consider the variable i in x13
li x13,0
#temp address
mv x6,x12
li x5,1
#Lets store 1 if it is odd in x1,x2,x3
#if all x1,x2,x3 are 1 then x4 is also 1
#i.e x4 = x1 &  x2 & x3
j loop

loop:
    bgt x13,x11,exit
    beq x4,x5,exit
    lw x7,0(x6)
    lw x8,4(x6)
    lw x9,8(x6)
    and x1,x7,x5
    and x2,x8,x5
    and x3,x9,x5
    and x4,x1,x2
    and x4,x4,x3
    addi x6,x6 4
    addi x13,x13,1
    j loop
    
exit:
    li a7,4
    beq x4,x5,success
    j fail

success:
    la a0,true
    ecall
    li a7,10
    ecall

fail:
    la a0,false
    ecall
    li a7,10
    ecall

---
## Question 3
The below code is implemented without considering extra array by taking shift logic.

**working :**
* Input the given array in .data segment
* Mention also the size of array
* Mention n

.data
array:  .word 1,2,3,4,4,3,2,1  # Array to be sorted
size:   .word 8        # Size of the array
n:      .word 4
constant:.word 1023
str:    .string " "

.text  
#constant in x25
lw x25,constant
#Address in x4
la x4,array
#normal pointer to iterate over array in x7
li x7,1
#int i in x2
lw x2,n
#int j in x3
lw x3,size
#back pointer in x12
mv x5,x4
#middle pointer in x9
mv x9,x4
j backpointer
    

loop1:
    # x5 is last pointer
    beq x2,x0,restart_pointer2
    lw x10,0(x5)
    slli x10,x10,10
    lw x11,0(x9)
    or x10,x10,x11
    sw x10,0(x5)
    addi x5,x5,-4
    addi x9,x9,-4
    addi x2,x2,-1
    j loop1
    
loop2:
    beq x3,x2,print_int
    #x4 has initial address and x12 has final address
    lw x30,0(x4)
    lw x31,0(x12)
    and x30,x31,x25
    sw x30,0(x4)
    addi x4,x4,4
    lw x30,0(x4)
    srli x30,x31,10
    sw x30,0(x4)
    addi x4,x4,4
    addi x12,x12,4
    addi x2,x2,1
    j loop2

backpointer:
    beq x7,x3,restart_pointer
    addi x5,x5,4
    addi x7,x7,1
    j backpointer
       
restart_pointer:
    mv x12,x5
    li x7,1
    j middlepointer
       
restart_pointer2:
    li x7,1
    mv x12,x17
    addi x12,x12,4
    lw x2,n
    j loop2

middlepointer:
    beq x7,x2,loop1
    addi x9,x9,4
    addi x7,x7,1
    mv x17,x9
    j middlepointer

print_int:
    la x4,array
    li x5,1
    lw x6,size
    j print
    
print:
    blt x6,x5,exit
    li a7,1
    lw a0,0(x4)
    ecall
    li a7,4
    la a0,str
    ecall 
    addi x4,x4,4
    addi x5,x5,1
    j print
    

exit:
    li a7,10
    ecall

**Output**

1 4 2 3 3 2 4 1
Program exited with code: 0

---
## Question 4
**Chosen Question : Q26 from Leet Code**
*Description :* Given a sorted array remove all the duplicate in the array. Return the unique elements

.data
array:  .word 1,1,1,2,2,3,3,3,3,3,3,3,4,4,4,4,4,4,4,5,5,5,6,  # Array to be sorted
size:   .word 23        # Size of the array
str:    .string " "

.text
#loading the address in x4
la x4,array
#loading size of array in x5
lw x5,size
#incrementor i in x6
li x6,0
#counter in x11
li x11,1
#unique counter in x23
#address in x9
mv x12,x4
j solve

solve:
    lw x7,0(x4)
    sw x7,0(x12)
    addi x12,x12,4
    addi x23,x23,1
    mv x9,x4
    beq x5,x11,print_int
    jal x1,unique
    
unique:
    addi x4,x4,4
    addi x11,x11,1
    lw x8,0(x4)
    bne x8,x7,solve
    j unique
    
print_int:
    la x4,array
    li x1,0
    j print

print:
    li a7,1
    lw x2,0(x4)
    mv a0,x2
    ecall
    li a7,4
    la a0,str
    ecall
    addi x4,x4,4
    addi x1,x1,1
    beq x1,x23,exit
    j print

exit:
    li a7,10
    ecall

**Output**

1 2 3 4 5 6
Program exited with code: 0

---
## Question 5
**This pseudo-code assumes a simple linked list with nodes containing two 4-byte values**

Lets define a node fot the linked list assuming that each node takes total of 8 bytes - 4 each for data and next pointer

#Define Node structure
.data 
node_size:  .word 8
head:   .word 0         #Head pointer initialized to NULL

On many RISC-V systems, the number 9 corresponds to the sbrk system call, which is used to adjust the program's data space (heap) and allocate additional memory.

.text
#Allocate memory for a new node
malloc_node:
    #Size of the node in bytes
    li a0, node_size   
    li a7, 9  
    #System call for sbrk 
    ecall
    #Result (address of allocated memory) is in a0
    ret

To insert a new node, first, read the value from the register to access the head node. Load the next pointer from the head node. If the next pointer is equal to x0 (indicating an empty or uninitialized node), add the address of the new node at this position. Save the new node's data and address in memory, and store the address in the designated location.

#Traversing the linked list 
traverse_print:
    lw a0, head         
    loop_start:
        lw a1, 0(a0)    #Load data from the current node
        lw a0, 4(a0)    # Load the next pointer
        bnez a0, loop_start  
    ret

Searching can be easily accomplished by traversing through consecutive memory locations pointed to by each node until the desired data is found or a NULL pointer is encountered.
After searching delete operation can also be done. By updating the previous node pointer value to current node's pointer value

---
## Question 6

* We need to first determine the size of the allocated block pointed to by the pointer .Lets assume it is stored some where.
* We also need to flag the places which are available for reuse and which are not .We can try using a book keeping algo for this
* We need to combine consecutive free blocks into a larger contiguous block and return the initial address when sbrk() is called.
* This address and the size will be sored in the record.
* when we free this memory, the func should check the record for the a the size it should free and then flag these memory cells as free for reuse
---