1 Replies - 324 Views - Last Post: 02 December 2018 - 11:06 PM

#1 tiburcino   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 1
  • Joined: 02-December 18

Binary Search in assembly

Posted 02 December 2018 - 05:46 AM

Hello, i'm doing this work for school but i don't understand the error i'm getting here:

This is the code in C and i'm putting it in assembly:

 Code in C 
#include <stdio.h>

extern void * binary_search(const void *key, const void *base, size_t nel, size_t width, int (*compar)(const void *, const void *));
int int_compare(const void *first, const void *second);

int main() {
	
	int data[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
	int key = 5;
	
	//printf("%d\n", binary_search(&key, data, sizeof(data) / sizeof(*data), sizeof(int), int_compare));
	
	void *p = binary_search(&key, data, sizeof(data) / sizeof(*data), sizeof(int), int_compare);
	if (p != NULL)
		printf("%d: found\n", *(int *)p); 		
	else
		printf("%d: not found!\n", key); 
	return 0;
}

int int_compare(const void *first, const void *second) {
	int f = *(int *)first;
	int s = *(int *)second;
	return (f < s) ? -1 : ((f > s) ? 1 : 0);
}

/*
void * binary_search(const void *key, const void *base, size_t nel, size_t width, int (*compar)(const void *, const void *)) {
	size_t low = 0, high = nel - 1;
	while (low <= high) {
		size_t mid = (low + high) / 2;
		char *midp = (char *)base + mid * width;
		int cond;
		if ((cond = (*compar)(midp, key)) < 0)
			low = mid + 1;
		else if (cond > 0) 
			high = mid - 1;
		else 
			return midp;
	}
	return NULL;
}*/
:code:

 Code in Assembly
	.text
	.globl binary_search
	
	# RDI = key
	# RSI = base
	# RDX = nel
	# RCX = width
	# R8  = compar
	# R9  = low
	# R10 = high
	# R11 = mid
	# R12 = midp
	
binary_search:
	mov $0, %r9 	  # R9 = low = 0
	mov %rdx, %r10	  # R10 = high = nel
	sub $1, %r10	  # R10 = nel - 1
	jmp while

while:
	cmp %r10, %r9 	  # R9 - R10
	ja retNull
	mov %r9, %r11 	  # R11 = mid = low
	add %r10, %r11 	  # R11 = low + high
	shr %r11 		  # R11 = mid = (low + high) / 2

	mov %r11, %rax	  # RAX = mid 
	push %rcx
	mul %rcx
	pop %rcx		  # RAX = mid * width
	add (%rsi), %rax  # RAX = midp = base + mid * width
	
	mov %rax, %r15
	mov %rdi, %rsi
	mov %rax, %rdi
	call *%r8
	cmp $0, %rax
	mov %r15, %rax
	je retMidP
	ja elseIf
	jb setLow
	
setLow:
	mov %r11, %r9   # low = mid
	add $1, %r9		# low = mid + 1
	jmp while

retMidP:
	ret

elseIf:
	mov %r11, %r10	# high = mid
	sub $1, %r10	# high = mid - 1
	jmp while

retNull:
	mov $0, %rax
	ret

	.end 
:code:

When I compile it and run I get "segmentation fault (core dumped)"

This post has been edited by modi123_1: 02 December 2018 - 10:43 AM
Reason for edit:: In the future please use the [code] tag button in the editor


Is This A Good Question/Topic? 0
  • +

Replies To: Binary Search in assembly

#2 turboscrew   User is offline

  • D.I.C Lover
  • member icon

Reputation: 171
  • View blog
  • Posts: 1,109
  • Joined: 03-April 12

Re: Binary Search in assembly

Posted 02 December 2018 - 11:06 PM

Before even reading the code: segmentation fault means that you access some memory location that is not allocated to your program.
Check for uninitialized pointer or out-of-range table accesses.

This makes me wonder...

Quote

32 add (%rsi), %rax # RAX = midp = base + mid * width
33
34 mov %rax, %r15
35 mov %rdi, %rsi
36 mov %rax, %rdi


If %rsi was the base address: add (%rsi), %rax?
And then mov %rdi, %rsi: base address is overwritten with key?
Then key is overwritten by midp?
Or is there something I missed?
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1