Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Search Sum Exercise in x86-Assembly
SECTION .TEXT
GLOBAL search_sum_asm
search_sum_asm:
;; Arguments:
;;
;; rdi = int* arr
;; rsi = int len
;; rdx = int sum
;; rcx = int *r
;; r8 = int *l
;;
;; Alias Register Names
%define arr_p rdi
%define idx_r rsi
%define idx_l r9
%define sum edx
;; Initialize Variables
mov idx_l, 0
dec idx_r
mov DWORD [rcx], 0
mov DWORD [r8], 0
LOOP:
cmp idx_l, idx_r
jge NOTFOUND
mov eax, [arr_p + 4 * idx_r]
add eax, [arr_p + 4 * idx_l]
cmp eax, sum
je FOUND
jl LOWER
jg GREATER
LOWER:
inc idx_l
jmp LOOP
GREATER:
dec idx_r
jmp LOOP
FOUND:
mov rax, 1
mov [rcx], idx_r
mov [r8], idx_l
ret
NOTFOUND:
mov rax, 0
ret
/*
* Task:
*
* Given an sorted array of integers e.g. a = [ 1, 2, 5, 7, 11 ] and an integer e.g. sum = 8.
* Find distinct indices x,y so that a[x] + a[y] = sum, if this is possible.
*
*/
#include<stdio.h>
/* array length */
#define LEN(a) sizeof(a) / sizeof(a[0])
/*
* Arguments:
* - int *arr -- pointer to array
* - int arr_len -- length of array
* - int sum -- sum
* - int *x,*y -- place to put solution
*
* Return: 1 if match is found, 0 otherwise.
*/
int search_sum_c(int *arr, int arr_len, int sum, int *x, int *y) {
int l = 0, r = arr_len - 1;
while (l < r) {
int s = arr[l] + arr[r];
if (s == sum) {
*x = r;
*y = l;
return 1;
} else if (s < sum) {
l++;
} else if (s > sum) {
r--;
}
};
return 0;
};
/* Declare asm implementation that will be linked */
extern int search_sum_asm(int* a, int len_a, int sum, int*x, int*y);
void test_search_sum(int *arr, int len, int sum) {
int r,l;
int ok = search_sum_asm(arr, len, sum, &r, &l);
printf("A = [");
for (int i = 0; i < len; i++) {
printf("%d,", arr[i]);
}
printf("], sum = %d; ", sum);
if (!ok) {
printf("No match found\n");
} else {
printf("Found @ (%d,%d) => ", l, r);
if (arr[r] + arr[l] == sum) {
printf("OK\n");
} else {
printf("FAILED\n");
}
}
}
int main() {
int arr[] = {1, 2, 6, 7, 9, 12};
int sum = 8;
test_search_sum(arr, LEN(arr), sum);
int arr2[] = {1, 7};
int sum2 = 8;
test_search_sum(arr2, LEN(arr2), sum2);
int arr3[] = {};
int sum3 = 8;
test_search_sum(arr3, LEN(arr3), sum3);
int arr4[] = {1, 2, 3};
int sum4 = 0;
test_search_sum(arr4, LEN(arr4), sum4);
int arr5[] = {4};
int sum5 = 8;
test_search_sum(arr5, LEN(arr5), sum5);
int arr6[] = {4, 4};
int sum6 = 8;
test_search_sum(arr6, LEN(arr6), sum6);
return 0;
}
main: main.c lib.asm
nasm -f elf64 -o lib.o lib.asm
gcc -o main main.c lib.o
run: main
./main
./main
A = [1,2,6,7,9,12,], sum = 8; Found @ (0,3) => OK
A = [1,7,], sum = 8; Found @ (0,1) => OK
A = [], sum = 8; No match found
A = [1,2,3,], sum = 0; No match found
A = [4,], sum = 8; No match found
A = [4,4,], sum = 8; Found @ (0,1) => OK
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment