# Array Search

### Code :

int arraySearch(int *p_a, int arr_size, int target)
{
    int result = -1;

    asm volatile(
        // Your code
        // t0:counter
        // t1:a[i]
        "mv   t0, zero                  \n\t"
        "loop:                          \n\t"
        "beq  t0, %[arr_size], end      \n\t"
        "lw   t1, 0(%[p_a])             \n\t"
        "beq  t1, %[target], find_out   \n\t"
        "addi %[p_a], %[p_a], 4         \n\t"
        "addi t0, t0, 1                 \n\t"
        "j    loop                      \n\t"
        "find_out:                      \n\t"
        "mv   %[result], t0             \n\t"
        "end:                           \n\t"
        :[p_a] "+r"(p_a), [result] "=r"(result)
        :[arr_size] "r"(arr_size), [target] "r"(target)
        :"t0", "t1"
        );

    return result;
}

### Explanation

**GOAL : Find the index of specified element**

- `t0` : Counter and index, `t1` : The value of a[i]
- If the element is found, set `target` to `t0`; otherwise, keep it as -1.

# Swap two element

### Code :

asm volatile(
    // Your code
    "mv   t0, %[j]         \n\t"
    "slli t0, t0, 2        \n\t"
    "add  t1, %[array], t0 \n\t"
    "lw   t2, 0(t1)        \n\t"
    "lw   t3, 4(t1)        \n\t"
    "blt  t2, t3, over     \n\t"
    "sw   t2, 4(t1)        \n\t"
    "sw   t3, 0(t1)        \n\t"
    "over:                 \n\t"
    :
    :[j] "r"(j), [array] "r"(p_a)
    :"t0", "t1", "t2", "t3"
);

### Exlanation :

**GOAL: Swap two elements if the previous one is bigger**
- Calculate the addresses of `a[j]` and `a[j+1]`
- Swap them by storing values at the opposite locations

# Merge Sort

## splitList

### Code :

// Split the linked list into two parts
void splitList(Node *head, Node **firstHalf, Node **secondHalf)
{
    asm volatile(
        /*
        Block A (splitList), which splits the linked list into two halves
        */
        // t1 : *fast, t2 : *slow 
        // t3 : pointer to previous node of t2
        "mv   t1, %[head]           \n\t"
        "mv   t2, %[head]           \n\t"
        "cut_loop:                  \n\t"
        "mv   t3, t2                \n\t"
        "ld   t2, 8(t2)             \n\t"
        "ld   t1, 8(t1)             \n\t"
        "beqz t1, cut_over          \n\t"
        "ld   t1, 8(t1)             \n\t"
        "beqz t1, cut_over          \n\t"
        "j    cut_loop              \n\t"
        "cut_over:                  \n\t"
        "mv   %[firstHalf], %[head] \n\t"
        "mv   %[secondHalf], t2     \n\t"
        "sd   zero, 8(t3)           \n\t"
        :[firstHalf] "+r"(*firstHalf), [secondHalf] "+r"(*secondHalf), [head] "+r"(head)
        :
        :"t1", "t2", "t3"
    );
}

### Explanation :

**GOAL : use specified pointer to split one linked list to two linked list**

- Use the [Fast-Slow pointer](https://medium.com/@arifimran5/fast-and-slow-pointer-pattern-in-linked-list-43647869ac99) to find the middle of the linked list `Line 10 to 19`
- `t1` : fast pointer, `t2` : slow pointer, `t3` : a pointer to the node preceding the slow pointer
- Here I use `t3` because I find pointer-to-pointer operations too complex. This pointer helps maintain the tail of the first half by setting its NEXT to 0.

## mergeSortLists

### Code :

Node *mergeSortedLists(Node *a, Node *b)
{
    Node *result = NULL;
    Node *tail = NULL;

    asm volatile(
        /*
        Block B (mergeSortedList), which merges two sorted lists into one
        */
        // t1:data of node *a
        // t2:data of node *b
        // use tail to construct the merged list
        "lw   t1, 0(%[a])           \n\t"
        "lw   t2, 0(%[b])           \n\t"
        "bge  t1, t2, result_tob    \n\t"
        "mv   %[result], %[a]       \n\t"
        "ld   %[a], 8(%[a])         \n\t"
        "j    merge_start           \n\t"
        "result_tob:                \n\t"
        "mv   %[result], %[b]       \n\t"
        "ld   %[b], 8(%[b])         \n\t"
        "merge_start:               \n\t"
        "mv   %[tail], %[result]    \n\t"
        "merge_loop:                \n\t"
        "beqz %[a], a_isNULL        \n\t"
        "beqz %[b], b_isNULL        \n\t"
        "lw   t1, 0(%[a])           \n\t"
        "lw   t2, 0(%[b])           \n\t"
        "bgt  t1, t2, b_smaller     \n\t"
        "a_smaller:                 \n\t"
        "sd   %[a], 8(%[tail])      \n\t"
        "ld   %[tail], 8(%[tail])   \n\t"
        "ld   %[a], 8(%[a])         \n\t"
        "j    merge_loop            \n\t"
        "b_smaller:                 \n\t"
        "sd   %[b], 8(%[tail])      \n\t"
        "ld   %[tail], 8(%[tail])   \n\t"
        "ld   %[b], 8(%[b])         \n\t"
        "j    merge_loop            \n\t"
        "a_isNULL:                  \n\t"
        "sd   %[b], 8(%[tail])      \n\t"
        "j    end                   \n\t"
        "b_isNULL:                  \n\t"
        "sd   %[a], 8(%[tail])      \n\t"
        "end:"
        :[a] "+r"(a), [b] "+r"(b), [tail] "+r"(tail), [result] "+r"(result)
        :
        :"t0", "t1"
    );

    return result;
}

### Explanation :

**GOAL : merge two sorted list to one sorted list**

Since I want to use recursion to merge two lists, I first compare the heads to determine the initial pointer `result` and then use `tail` to construct the new list.

The recursive steps are as follows:
1. Check that neither pointer `a`, `b` is NULL. If one is, end the recursion `Line 25, 26`
2. Move `tail` to the smaller node and link it `Line 27 to 39`
3. If one list is empty (meaning the other is not), set the NEXT of `tail` to the remaining nodes `Line 40 to 44`

## print list

### Code :

cur = head;
while (cur) {
    printf("%d ", cur->data);
    asm volatile(
        /*
        Block C (Move to the next node), which updates the pointer to
        traverse the linked list
        */
        "ld   %[cur], 8(%[cur]) \n\t"
        :[cur] "+r"(cur)
        :
        :
    );
}

### Explanation :

Because:
1. The pointer stores the address of the node
2. According to memory alignment, data is allocated 8 bytes (the same as next)

Hence, we access the next node by loading 8 bytes (`ld`) from `*(cur) + 8`

## Verificationlinked_list_sort.c

I use following two instructions to print the result of merge sort

riscv64-unknown-linux-gnu-gcc -static -march=rv64gcv -o MergeSort linked_list_sort.c

spike --isa=RV64GCV /opt/riscv/riscv64-unknown-linux-gnu/bin/pk MergeSort ../testcases/input/3_1.txt