# Assignment1: RISC-V Assembly and Finding the Closest Power of Two Greater Than or Equal to a Number

:information_source:

## Finding the Closest Power of Two Greater Than or Equal to a Number

> Description:
> I come up with this problem from shift-add multipier in digital circuit design.
> Given a number n, the task is to find the closest power of two that is greater than or equal to n.

## Solution

### Idea for problem solving

A straightforward approach is to start with 1 and keep doubling the number until it becomes greater than or equal to n. However, this can be inefficient for large numbers.

### C program

#### First version

#include <stdio.h>

// Find closest power of two greater than or equal to n
int closest_power_of_two(unsigned int n) {
    int power = 1;
    while (power < n) {
        power *= 2;
    }
    return power;
}

int main() {
    int n;
    printf("Enter a number: %d\n", n);

    int result = closest_power_of_two(n);
    printf("Closest power of two greater than or equal to %d is %d\n", n, result);

    return 0;
}

#### Second version
> The idea of second version is to use a 32-bits binary mask to verify if the target is more than 0.
> At the begining, the mask is 0x8000_00000, and we keep shifting left to verify next digit of target. If it was more than 0, then the answer of the leading zero will be n (the time we shift) - 1.
> if target is:
> 0x0000_3000
> mask hould be:
> 0x0000_2000
> this means we shift totally 19 times from x8000_00000 to 0x0000_2000

#include <stdio.h>
int clz(int x) {
    int count = 0;
    for (int i = 31; i >= 0; --i) {
        if (x & (1U << i))
            break;
        count++;
    }
    return count;
}
// Optimized approach using binary manipulation
int closest_power_of_two(int n) {
    // If n is already a power of two, return n
    if ((n & (n - 1)) == 0) {
        return n;
    }
    // Count the number of leading zeros in the binary representation of n
    int leading_zero_count = clz(n); 

    // Calculate the closest power of two by shifting left (bit-wise operation)
    return 1 << (32 - leading_zero_count);
}
int main() {
    int n = 20;
    printf("Enter a number: %d\n", n);


    int result = closest_power_of_two(n);
    printf("Closest power of two greater than or equal to %d is %d\n", n, result);

    return 0;
}

#### Third version

#include <stdio.h>
int clz(int x)
{
    x |= (x >> 1);
    x |= (x >> 2);
    x |= (x >> 4);
    x |= (x >> 8);
    x |= (x >> 16);
    x |= (x >> 32);

    /* count ones (population count) */
    x -= ((x >> 1) & 0x55555555);
    x = ((x >> 2) & 0x33333333) + (x & 0x33333333);
    x = ((x >> 4) + x) & 0x0f0f0f0f;
    x += (x >> 8);
    x += (x >> 16);
    x += (x >> 32);

    return (32 - (x & 0x7f));
}
// Optimized approach using binary manipulation
int closest_power_of_two(int n) {
    // If n is already a power of two, return n
    if ((n & (n - 1)) == 0) {
        return n;
    }
    // Count the number of leading zeros in the binary representation of n
    int leading_zero_count = clz(n); 

    // Calculate the closest power of two by shifting left (bit-wise operation)
    return 1 << (32 - leading_zero_count);
}
int main() {
    int n = 20;
    printf("Enter a number: %d\n", n);


    int result = closest_power_of_two(n);
    printf("Closest power of two greater than or equal to %d is %d\n", n, result);

    return 0;
}

### Assembly

.data
str1: .string "Closest power of two greater than or equal to "
str2: .string " is "
arg:  .word   48

.text
main:
    lw  a0, arg
    jal ra, closest_power_of_two
    
    la a0 str1
    jal ra printfstr
    
    lw  a0, arg
    jal ra printfint
    
    la a0 str2
    jal ra printfstr
    
    add a0, x0, a1
    jal ra printfint
    
    jal ra, end
    

closest_power_of_two:
    addi a1, x0, 1
while:
    bgeu a1, a0 return
    slli a1, a1, 1
    j while
return:
    jalr ra
    
printfint:
    li a7, 1
    ecall
    jalr ra
printfstr:
    li a7, 4
    ecall
    jalr ra
end:
    li a7, 10
    ecall

### Optimization
#### cls version

.data
str1: .string "Closest power of two greater than or equal to "
str2: .string " is "
arg:  .word   0x00003000

.text
main:

    lw  a0, arg
    jal ra, closest_power_of_two
    
    la a0 str1
    jal ra printfstr
    
    lw  a0, arg
    jal ra printfint
    
    la a0 str2
    jal ra printfstr
    
    add a0, x0, a1
    jal ra printfint
    
    jal ra, end
    
######################
closest_power_of_two:
    addi    sp,sp,-4
    sw      ra,0(sp)
    
    addi t1, a0, -1
    and t1, t1, a0
    add a1, x0, a0
    beq t1, x0, cp2_return
    
    jal ra clz
    addi t0, x0, 32
    sub a1, t0, a1
    addi t3, x0, 1
    sll a1, t3, a1
cp2_return:
    lw ra, 0(sp)
    addi sp, sp, 4
    jalr ra
######################
clz:
    addi    sp,sp,-4
    sw      ra,0(sp)
    
    addi t0, x0, 1
    slli t0, t0, 31
    addi a1, x0, 0 # int count = 0
clz_for:
    beq t0, x0, clz_return
    and t1, a0, t0
    bgt t1, x0, clz_return
    addi a1, a1, 1 # count++
    srli t0, t0, 1
    j clz_for

clz_return:
    lw ra, 0(sp)
    addi sp, sp, 4
    jalr ra
######################
printfint:
    li a7, 1
    ecall
    jalr ra
printfstr:
    li a7, 4
    ecall
    jalr ra
end:
    li a7, 10
    ecall

#### clz optimization

.data
str1: .string "Closest power of two greater than or equal to "
str2: .string " is "
arg:  .word   0x0000002c

.text
main:

    lw  a0, arg
    jal ra, closest_power_of_two
    
    la a0 str1
    jal ra printfstr
    
    lw  a0, arg
    jal ra printfint
    
    la a0 str2
    jal ra printfstr
    
    add a0, x0, a1
    jal ra printfint
    
    jal ra, end
    
######################
closest_power_of_two:
    addi    sp,sp,-4
    sw      ra,0(sp)
    
    addi t1, a0, -1
    and t1, t1, a0
    add a1, x0, a0
    beq t1, x0, cp2_return
    
    jal ra clz
    addi t0, x0, 32
    sub a1, t0, a1
    addi t3, x0, 1
    sll a1, t3, a1
cp2_return:
    lw ra, 0(sp)
    addi sp, sp, 4
    jalr ra
######################
clz:
    addi    sp,sp,-4
    sw      ra,0(sp)
    
    srli a1, a0, 1
    or   a1, a1, a0
    srli t1, a1, 2
    or   a1, a1, t1
    srli t1, a1, 4
    or   a1, a1, t1
    srli t1, a1, 8
    or   a1, a1, t1
    srli t1, a1, 16
    or   a1, a1, t1
    
    srai    t0,a1,1
    li      t1,1431654400
    addi    t1,t1,1365
    and     t0,t0,t1
    sub     a1,a1,t0
    
    srai    t0,a1,2
    li      t1,858992640
    addi    t1,t1,819
    and     t0,t0,t1
    and     t1,a1,t1
    add     a1, t0, t1
    
    srai    t0,a1,4
    li      t1,252645376
    addi    t1,t1,-241
    add     t0,t0,a1
    and     a1,t0,t1
    
    srai    t0, a1, 8
    add     a1,t0,a1
    srai    t0, a1, 16
    add     a1,t0,a1 
    
    andi    a1, a1, 0x7f
    addi    t0, x0, 32
    sub     a1,t0,a1  
clz_return:
    lw ra, 0(sp)
    addi sp, sp, 4
    jalr ra
######################
printfint:
    li a7, 1
    ecall
    jalr ra
printfstr:
    li a7, 4
    ecall
    jalr ra
end:
    li a7, 10
    ecall

## Cycles
The effect value is ranged from 0x0000_0000 to 0x8000_0000
|version|0x0000_0000|0x0000_0001|0x0000_4001|0x0020_0900|0x7700_0000|0x8000_0000|
|-------|-----------|-----------|-----------|-----------|-----------|-----------|
|ver.0 |70 cycles |75 cycles |145 cycles |180 cycles |225 cycles |225 cycles |
|ver.1 |76 cycles |76 cycles |232 cycles |176 cycles |104 cycles |76 cycles |
|ver.2 |76 cycles |76 cycles |121 cycles |121 cycles |121 cycles |76 cycles |