#include <stdlib.h>
#include <stdio.h>

#define ARRAY_LENGTH (100)
#define ARRAY_ELEMENT_SIZE (sizeof(long))
#define ARRAY_SIZE (ARRAY_ELEMENT_SIZE * ARRAY_LENGTH)
#define SAMPLE_LENGTH (5)
#define SAMPLE_SIZE (ARRAY_ELEMENT_SIZE * SAMPLE_LENGTH)
#define QUERY_LENGTH (10)
#define QUERY_SIZE (ARRAY_ELEMENT_SIZE * QUERY_LENGTH)
#define PRINT_ARRAY (1)

/*
First create a downsampled array (create an array and populate it with every Nth element from array)
Search the downsampled array for the number closest but smaller than desired. Then look in the area between that number and next number in the sample
*/

int random(int min, int max){
	return (rand()%(max-min))+min;	
}

void populateArray(long* array, long i){
	array[i] = i;
	if(PRINT_ARRAY)
		printf("array[%ld] = %ld\n",i,array[i]);
}

void populateSample(long* array, long *sample,long i){
	sample[i] = array[i * ARRAY_LENGTH / SAMPLE_LENGTH];
	if(PRINT_ARRAY)
		printf("sample[%ld] = %ld\n",i,sample[i]);
}

void populateQuery(long* query, long i){
	query[i] = random(0,100);
	if(PRINT_ARRAY)
		printf("query[%ld] = %ld\n",i,query[i]);
}

long binary_search_guess(long *array, long number_of_elements, long key)
{
	long low = 0, high = number_of_elements-1, mid;
	while(low <= high)
	{
		mid = (low + high)/2;
		if(array[mid] < key)
		{
			low = mid + 1; 
		}
		else if(array[mid] == key)
		{
			return mid;
		}
		else if(array[mid] > key)
		{
			high = mid-1;
		}
	}

	if(array[mid] > key){
		while(mid > 0 && array[mid] > key){
			mid--;
		}
	}
	return mid;
}

long binary_search_precise(long *array, long key,long low, long high)
{
	long mid;
	while(low <= high)
	{
		mid = (low + high)/2;
		if(array[mid] < key)
		{
			low = mid + 1; 
		}
		else if(array[mid] == key)
		{
			return mid;
		}
		else if(array[mid] > key)
		{
			high = mid-1;
		}
	}
	return -1;
}


void search(long* array, long *sample, long*output, long* query, long index){
	/*if(query[index] < *array || query[index] >= sample[SAMPLE_LENGTH-1] + ARRAY_LENGTH / SAMPLE_LENGTH)
		output[index] = -1;*/
	
	long guess = binary_search_guess(sample,SAMPLE_LENGTH,query[index]);	
	output[index] = binary_search_precise(
		array,
		query[index],
		guess * ARRAY_LENGTH / SAMPLE_LENGTH,
		(guess + 1) * ARRAY_LENGTH / SAMPLE_LENGTH
	); 
}

int main(int argc,char* argv[]){
	long *array = (long*)malloc(ARRAY_SIZE);
	long *sample = (long*)malloc(SAMPLE_SIZE);
	long *output = (long*)malloc(QUERY_SIZE);
	long *query = (long*)malloc(QUERY_SIZE);

	long *device_array;
	long *device_sample;
	long *device_output;
	long *device_query;

	cudaMalloc((void**)&device_array,ARRAY_SIZE);
	cudaMalloc((void**)&device_sample,SAMPLE_SIZE);
	cudaMalloc((void**)&device_output,QUERY_SIZE);
	cudaMalloc((void**)&device_query,QUERY_SIZE);

	// cpu
	printf("Populating Array\n");
	for(long i=0;i<ARRAY_LENGTH;i++)
		populateArray(array,i);

	// cpu
	printf("Populating Query\n");
	for(long i=0;i<QUERY_LENGTH;i++)
		populateQuery(query,i);

	// cpu
	printf("Populating Sample\n");
	for(long i=0;i<SAMPLE_LENGTH;i++)
		populateSample(array,sample,i);

	// gpu
	printf("Processing Query\n");
	for(long i=0;i<QUERY_LENGTH;i++)
		search(array,sample,output,query,i);

	// copy the results from the gpu to the cpu
	//cudaMemcpy(output,device_output,QUERY_SIZE,cudaMemcpyDeviceToHost);
	
	printf("Printing Results\n");
	for(long i=0;i<QUERY_LENGTH;i++)
		printf("results[%ld] = (%ld == [%ld])\n",i,output[i],query[i]);

	cudaFree(device_array);
	cudaFree(device_sample);
	cudaFree(device_output);
	cudaFree(device_query);

	free(array);
	free(sample);
	free(output);
	free(query);

	return 0;
}
	.file	"tmpxft_00206008_00000000-6_main.cudafe1.cpp"
	.text
#APP

#NO_APP
	.type	_ZL26__cudaUnregisterBinaryUtilv, @function
_ZL26__cudaUnregisterBinaryUtilv:
.LFB2037:
	.cfi_startproc
	endbr64
	movq	_ZL20__cudaFatCubinHandle(%rip), %rdi
	jmp	__cudaUnregisterFatBinary@PLT
	.cfi_endproc
.LFE2037:
	.size	_ZL26__cudaUnregisterBinaryUtilv, .-_ZL26__cudaUnregisterBinaryUtilv
	.globl	_Z6randomii
	.type	_Z6randomii, @function
_Z6randomii:
.LFB2027:
	.cfi_startproc
	endbr64
	pushq	%rbp
	.cfi_def_cfa_offset 16
	.cfi_offset 6, -16
	movl	%edi, %ebp
	pushq	%rbx
	.cfi_def_cfa_offset 24
	.cfi_offset 3, -24
	movl	%esi, %ebx
	pushq	%rax
	.cfi_def_cfa_offset 32
	subl	%ebp, %ebx
	call	rand@PLT
	cltd
	idivl	%ebx
	leal	(%rdx,%rbp), %eax
	popq	%rdx
	.cfi_def_cfa_offset 24
	popq	%rbx
	.cfi_def_cfa_offset 16
	popq	%rbp
	.cfi_def_cfa_offset 8
	ret
	.cfi_endproc
.LFE2027:
	.size	_Z6randomii, .-_Z6randomii
	.section	.rodata.str1.1,"aMS",@progbits,1
.LC0:
	.string	"array[%ld] = %ld\n"
	.text
	.globl	_Z13populateArrayPll
	.type	_Z13populateArrayPll, @function
_Z13populateArrayPll:
.LFB2028:
	.cfi_startproc
	endbr64
	movq	%rsi, (%rdi,%rsi,8)
	movq	%rsi, %rdx
	movq	%rsi, %rcx
	movl	$2, %edi
	leaq	.LC0(%rip), %rsi
	xorl	%eax, %eax
	jmp	__printf_chk@PLT
	.cfi_endproc
.LFE2028:
	.size	_Z13populateArrayPll, .-_Z13populateArrayPll
	.section	.rodata.str1.1
.LC1:
	.string	"sample[%ld] = %ld\n"
	.text
	.globl	_Z14populateSamplePlS_l
	.type	_Z14populateSamplePlS_l, @function
_Z14populateSamplePlS_l:
.LFB2029:
	.cfi_startproc
	endbr64
	imulq	$160, %rdx, %rax
	movq	(%rdi,%rax), %rcx
	movl	$2, %edi
	xorl	%eax, %eax
	movq	%rcx, (%rsi,%rdx,8)
	leaq	.LC1(%rip), %rsi
	jmp	__printf_chk@PLT
	.cfi_endproc
.LFE2029:
	.size	_Z14populateSamplePlS_l, .-_Z14populateSamplePlS_l
	.section	.rodata.str1.1
.LC2:
	.string	"query[%ld] = %ld\n"
	.text
	.globl	_Z13populateQueryPll
	.type	_Z13populateQueryPll, @function
_Z13populateQueryPll:
.LFB2030:
	.cfi_startproc
	endbr64
	pushq	%rbp
	.cfi_def_cfa_offset 16
	.cfi_offset 6, -16
	movq	%rdi, %rbp
	pushq	%rbx
	.cfi_def_cfa_offset 24
	.cfi_offset 3, -24
	movq	%rsi, %rbx
	pushq	%rax
	.cfi_def_cfa_offset 32
	call	rand@PLT
	movl	$100, %ecx
	movl	$2, %edi
	leaq	.LC2(%rip), %rsi
	cltd
	idivl	%ecx
	xorl	%eax, %eax
	movslq	%edx, %rcx
	movq	%rbx, %rdx
	movq	%rcx, 0(%rbp,%rbx,8)
	popq	%r8
	.cfi_def_cfa_offset 24
	popq	%rbx
	.cfi_def_cfa_offset 16
	popq	%rbp
	.cfi_def_cfa_offset 8
	jmp	__printf_chk@PLT
	.cfi_endproc
.LFE2030:
	.size	_Z13populateQueryPll, .-_Z13populateQueryPll
	.globl	_Z19binary_search_guessPlll
	.type	_Z19binary_search_guessPlll, @function
_Z19binary_search_guessPlll:
.LFB2031:
	.cfi_startproc
	endbr64
	movq	%rdx, %rcx
	decq	%rsi
	xorl	%eax, %eax
	xorl	%r8d, %r8d
	movl	$2, %r9d
.L9:
	cmpq	%rsi, %r8
	jg	.L18
	leaq	(%r8,%rsi), %rax
	cqto
	idivq	%r9
	cmpq	%rcx, (%rdi,%rax,8)
	jge	.L10
	leaq	1(%rax), %r8
	jmp	.L9
.L10:
	je	.L8
	leaq	-1(%rax), %rsi
	jmp	.L9
.L18:
	cmpq	%rcx, (%rdi,%rax,8)
	jg	.L14
	ret
.L19:
	cmpq	%rcx, (%rdi,%rax,8)
	jle	.L8
	decq	%rax
.L14:
	testq	%rax, %rax
	jg	.L19
.L8:
	ret
	.cfi_endproc
.LFE2031:
	.size	_Z19binary_search_guessPlll, .-_Z19binary_search_guessPlll
	.globl	_Z21binary_search_precisePllll
	.type	_Z21binary_search_precisePllll, @function
_Z21binary_search_precisePllll:
.LFB2032:
	.cfi_startproc
	endbr64
	movq	%rdi, %r8
	movl	$2, %r9d
	movq	%rdx, %rdi
.L21:
	cmpq	%rcx, %rdi
	jg	.L26
	leaq	(%rdi,%rcx), %rax
	cqto
	idivq	%r9
	movq	%rax, %rdx
	cmpq	%rsi, (%r8,%rax,8)
	jge	.L22
	leaq	1(%rax), %rdi
	jmp	.L21
.L22:
	je	.L20
	leaq	-1(%rax), %rcx
	jmp	.L21
.L26:
	orq	$-1, %rdx
.L20:
	movq	%rdx, %rax
	ret
	.cfi_endproc
.LFE2032:
	.size	_Z21binary_search_precisePllll, .-_Z21binary_search_precisePllll
	.globl	_Z6searchPlS_S_S_l
	.type	_Z6searchPlS_S_S_l, @function
_Z6searchPlS_S_S_l:
.LFB2033:
	.cfi_startproc
	endbr64
	pushq	%rbp
	.cfi_def_cfa_offset 16
	.cfi_offset 6, -16
	movq	%rdi, %r11
	movq	%rdx, %r10
	movq	%rsi, %rdi
	pushq	%rbx
	.cfi_def_cfa_offset 24
	.cfi_offset 3, -24
	movq	(%rcx,%r8,8), %rbx
	movl	$5, %esi
	leaq	0(,%r8,8), %rbp
	addq	%rbp, %r10
	movq	%rbx, %rdx
	call	_Z19binary_search_guessPlll
	movq	%rbx, %rsi
	movq	%r11, %rdi
	leaq	1(%rax), %rcx
	imulq	$20, %rcx, %rcx
	leaq	-20(%rcx), %rdx
	call	_Z21binary_search_precisePllll
	movq	%rax, (%r10)
	popq	%rbx
	.cfi_def_cfa_offset 16
	popq	%rbp
	.cfi_def_cfa_offset 8
	ret
	.cfi_endproc
.LFE2033:
	.size	_Z6searchPlS_S_S_l, .-_Z6searchPlS_S_S_l
	.section	.rodata.str1.1
.LC3:
	.string	"Populating Array\n"
.LC4:
	.string	"Populating Query\n"
.LC5:
	.string	"Populating Sample\n"
.LC6:
	.string	"Processing Query\n"
.LC7:
	.string	"Printing Results\n"
.LC8:
	.string	"results[%ld] = (%ld == [%ld])\n"
	.section	.text.startup,"ax",@progbits
	.globl	main
	.type	main, @function
main:
.LFB2034:
	.cfi_startproc
	endbr64
	pushq	%r15
	.cfi_def_cfa_offset 16
	.cfi_offset 15, -16
	movl	$800, %edi
	pushq	%r14
	.cfi_def_cfa_offset 24
	.cfi_offset 14, -24
	pushq	%r13
	.cfi_def_cfa_offset 32
	.cfi_offset 13, -32
	pushq	%r12
	.cfi_def_cfa_offset 40
	.cfi_offset 12, -40
	xorl	%r12d, %r12d
	pushq	%rbp
	.cfi_def_cfa_offset 48
	.cfi_offset 6, -48
	pushq	%rbx
	.cfi_def_cfa_offset 56
	.cfi_offset 3, -56
	subq	$56, %rsp
	.cfi_def_cfa_offset 112
	movq	%fs:40, %rax
	movq	%rax, 40(%rsp)
	xorl	%eax, %eax
	call	malloc@PLT
	movl	$40, %edi
	movq	%rax, %rbp
	call	malloc@PLT
	movl	$80, %edi
	movq	%rax, %r14
	call	malloc@PLT
	movl	$80, %edi
	movq	%rax, %r13
	call	malloc@PLT
	leaq	8(%rsp), %rdi
	movl	$800, %esi
	movq	%rax, %rbx
	call	cudaMalloc@PLT
	leaq	16(%rsp), %rdi
	movl	$40, %esi
	call	cudaMalloc@PLT
	leaq	24(%rsp), %rdi
	movl	$80, %esi
	call	cudaMalloc@PLT
	leaq	32(%rsp), %rdi
	movl	$80, %esi
	call	cudaMalloc@PLT
	leaq	.LC3(%rip), %rsi
	movl	$2, %edi
	xorl	%eax, %eax
	call	__printf_chk@PLT
.L30:
	movq	%r12, %rsi
	movq	%rbp, %rdi
	incq	%r12
	call	_Z13populateArrayPll
	cmpq	$100, %r12
	jne	.L30
	leaq	.LC4(%rip), %rsi
	movl	$2, %edi
	xorl	%eax, %eax
	xorl	%r12d, %r12d
	call	__printf_chk@PLT
.L31:
	movq	%r12, %rsi
	movq	%rbx, %rdi
	incq	%r12
	call	_Z13populateQueryPll
	cmpq	$10, %r12
	jne	.L31
	leaq	.LC5(%rip), %rsi
	movl	$2, %edi
	xorl	%eax, %eax
	xorl	%r12d, %r12d
	call	__printf_chk@PLT
.L32:
	movq	%r12, %rdx
	movq	%r14, %rsi
	movq	%rbp, %rdi
	incq	%r12
	call	_Z14populateSamplePlS_l
	cmpq	$5, %r12
	jne	.L32
	leaq	.LC6(%rip), %rsi
	movl	$2, %edi
	xorl	%eax, %eax
	xorl	%r12d, %r12d
	call	__printf_chk@PLT
.L33:
	movq	%r12, %r8
	movq	%rbx, %rcx
	movq	%r13, %rdx
	movq	%r14, %rsi
	movq	%rbp, %rdi
	incq	%r12
	call	_Z6searchPlS_S_S_l
	cmpq	$10, %r12
	jne	.L33
	leaq	.LC7(%rip), %rsi
	movl	$2, %edi
	xorl	%eax, %eax
	xorl	%r12d, %r12d
	call	__printf_chk@PLT
	leaq	.LC8(%rip), %r15
.L34:
	movq	0(%r13,%r12,8), %rcx
	movq	(%rbx,%r12,8), %r8
	movq	%r12, %rdx
	movq	%r15, %rsi
	movl	$2, %edi
	xorl	%eax, %eax
	incq	%r12
	call	__printf_chk@PLT
	cmpq	$10, %r12
	jne	.L34
	movq	8(%rsp), %rdi
	call	cudaFree@PLT
	movq	16(%rsp), %rdi
	call	cudaFree@PLT
	movq	24(%rsp), %rdi
	call	cudaFree@PLT
	movq	32(%rsp), %rdi
	call	cudaFree@PLT
	movq	%rbp, %rdi
	call	free@PLT
	movq	%r14, %rdi
	call	free@PLT
	movq	%r13, %rdi
	call	free@PLT
	movq	%rbx, %rdi
	call	free@PLT
	movq	40(%rsp), %rax
	subq	%fs:40, %rax
	je	.L35
	call	__stack_chk_fail@PLT
.L35:
	addq	$56, %rsp
	.cfi_def_cfa_offset 56
	xorl	%eax, %eax
	popq	%rbx
	.cfi_def_cfa_offset 48
	popq	%rbp
	.cfi_def_cfa_offset 40
	popq	%r12
	.cfi_def_cfa_offset 32
	popq	%r13
	.cfi_def_cfa_offset 24
	popq	%r14
	.cfi_def_cfa_offset 16
	popq	%r15
	.cfi_def_cfa_offset 8
	ret
	.cfi_endproc
.LFE2034:
	.size	main, .-main
	.type	_ZL24__sti____cudaRegisterAllv, @function
_ZL24__sti____cudaRegisterAllv:
.LFB2060:
	.cfi_startproc
	endbr64
	pushq	%rax
	.cfi_def_cfa_offset 16
	leaq	_ZL15__fatDeviceText(%rip), %rdi
	call	__cudaRegisterFatBinary@PLT
	movq	%rax, %rdi
	movq	%rax, _ZL20__cudaFatCubinHandle(%rip)
	call	__cudaRegisterFatBinaryEnd@PLT
	leaq	_ZL26__cudaUnregisterBinaryUtilv(%rip), %rdi
	popq	%rdx
	.cfi_def_cfa_offset 8
	jmp	atexit@PLT
	.cfi_endproc
.LFE2060:
	.size	_ZL24__sti____cudaRegisterAllv, .-_ZL24__sti____cudaRegisterAllv
	.section	.init_array,"aw"
	.align 8
	.quad	_ZL24__sti____cudaRegisterAllv
	.section	.nvFatBinSegment,"aw"
	.align 8
	.type	_ZL15__fatDeviceText, @object
	.size	_ZL15__fatDeviceText, 24
_ZL15__fatDeviceText:
	.long	1180844977
	.long	1
	.quad	fatbinData
	.quad	0
	.local	_ZL20__cudaFatCubinHandle
	.comm	_ZL20__cudaFatCubinHandle,8,8
	.ident	"GCC: (Ubuntu 13.3.0-6ubuntu2~24.04) 13.3.0"
	.section	.note.GNU-stack,"",@progbits
	.section	.note.gnu.property,"a"
	.align 8
	.long	1f - 0f
	.long	4f - 1f
	.long	5
0:
	.string	"GNU"
1:
	.align 8
	.long	0xc0000002
	.long	3f - 2f
2:
	.long	0x3
3:
	.align 8
4:


#include <hip/hip_runtime.h>
#include <stdlib.h>
#include <stdio.h>

#define ARRAY_LENGTH (100)
#define ARRAY_ELEMENT_SIZE (sizeof(long))
#define ARRAY_SIZE (ARRAY_ELEMENT_SIZE * ARRAY_LENGTH)
#define SAMPLE_LENGTH (5)
#define SAMPLE_SIZE (ARRAY_ELEMENT_SIZE * SAMPLE_LENGTH)
#define QUERY_LENGTH (10)
#define QUERY_SIZE (ARRAY_ELEMENT_SIZE * QUERY_LENGTH)
#define PRINT_ARRAY (1)

/*
First create a downsampled array (create an array and populate it with every Nth element from array)
Search the downsampled array for the number closest but smaller than desired. Then look in the area between that number and next number in the sample
*/

int random(int min, int max){
	return (rand()%(max-min))+min;	
}

void populateArray(long* array, long i){
	array[i] = i;
	if(PRINT_ARRAY)
		printf("array[%ld] = %ld\n",i,array[i]);
}

void populateSample(long* array, long *sample,long i){
	sample[i] = array[i * ARRAY_LENGTH / SAMPLE_LENGTH];
	if(PRINT_ARRAY)
		printf("sample[%ld] = %ld\n",i,sample[i]);
}

void populateQuery(long* query, long i){
	query[i] = random(0,100);
	if(PRINT_ARRAY)
		printf("query[%ld] = %ld\n",i,query[i]);
}

long binary_search_guess(long *array, long number_of_elements, long key)
{
	long low = 0, high = number_of_elements-1, mid;
	while(low <= high)
	{
		mid = (low + high)/2;
		if(array[mid] < key)
		{
			low = mid + 1; 
		}
		else if(array[mid] == key)
		{
			return mid;
		}
		else if(array[mid] > key)
		{
			high = mid-1;
		}
	}

	if(array[mid] > key){
		while(mid > 0 && array[mid] > key){
			mid--;
		}
	}
	return mid;
}

long binary_search_precise(long *array, long key,long low, long high)
{
	long mid;
	while(low <= high)
	{
		mid = (low + high)/2;
		if(array[mid] < key)
		{
			low = mid + 1; 
		}
		else if(array[mid] == key)
		{
			return mid;
		}
		else if(array[mid] > key)
		{
			high = mid-1;
		}
	}
	return -1;
}


void search(long* array, long *sample, long*output, long* query, long index){
	/*if(query[index] < *array || query[index] >= sample[SAMPLE_LENGTH-1] + ARRAY_LENGTH / SAMPLE_LENGTH)
		output[index] = -1;*/
	
	long guess = binary_search_guess(sample,SAMPLE_LENGTH,query[index]);	
	output[index] = binary_search_precise(
		array,
		query[index],
		guess * ARRAY_LENGTH / SAMPLE_LENGTH,
		(guess + 1) * ARRAY_LENGTH / SAMPLE_LENGTH
	); 
}

int main(int argc,char* argv[]){
	long *array = (long*)malloc(ARRAY_SIZE);
	long *sample = (long*)malloc(SAMPLE_SIZE);
	long *output = (long*)malloc(QUERY_SIZE);
	long *query = (long*)malloc(QUERY_SIZE);

	long *device_array;
	long *device_sample;
	long *device_output;
	long *device_query;

	hipMalloc((void**)&device_array,ARRAY_SIZE);
	hipMalloc((void**)&device_sample,SAMPLE_SIZE);
	hipMalloc((void**)&device_output,QUERY_SIZE);
	hipMalloc((void**)&device_query,QUERY_SIZE);

	// cpu
	printf("Populating Array\n");
	for(long i=0;i<ARRAY_LENGTH;i++)
		populateArray(array,i);

	// cpu
	printf("Populating Query\n");
	for(long i=0;i<QUERY_LENGTH;i++)
		populateQuery(query,i);

	// cpu
	printf("Populating Sample\n");
	for(long i=0;i<SAMPLE_LENGTH;i++)
		populateSample(array,sample,i);

	// gpu
	printf("Processing Query\n");
	for(long i=0;i<QUERY_LENGTH;i++)
		search(array,sample,output,query,i);

	// copy the results from the gpu to the cpu
	//cudaMemcpy(output,device_output,QUERY_SIZE,cudaMemcpyDeviceToHost);
	
	printf("Printing Results\n");
	for(long i=0;i<QUERY_LENGTH;i++)
		printf("results[%ld] = (%ld == [%ld])\n",i,output[i],query[i]);

	hipFree(device_array);
	hipFree(device_sample);
	hipFree(device_output);
	hipFree(device_query);

	free(array);
	free(sample);
	free(output);
	free(query);

	return 0;
}
	.text
	.file	"main.hip"
	.globl	_Z6randomii                     # -- Begin function _Z6randomii
	.type	_Z6randomii,@function
_Z6randomii:                            # @_Z6randomii
	.cfi_startproc
# %bb.0:
	pushq	%rbp
	.cfi_def_cfa_offset 16
	pushq	%rbx
	.cfi_def_cfa_offset 24
	pushq	%rax
	.cfi_def_cfa_offset 32
	.cfi_offset %rbx, -24
	.cfi_offset %rbp, -16
	movl	%esi, %ebx
	movl	%edi, %ebp
	callq	rand
	subl	%ebp, %ebx
	cltd
	idivl	%ebx
	addl	%edx, %ebp
	movl	%ebp, %eax
	addq	$8, %rsp
	.cfi_def_cfa_offset 24
	popq	%rbx
	.cfi_def_cfa_offset 16
	popq	%rbp
	.cfi_def_cfa_offset 8
	retq
.Lfunc_end0:
	.size	_Z6randomii, .Lfunc_end0-_Z6randomii
	.cfi_endproc
                                        # -- End function
	.globl	_Z13populateArrayPll            # -- Begin function _Z13populateArrayPll
	.type	_Z13populateArrayPll,@function
_Z13populateArrayPll:                   # @_Z13populateArrayPll
	.cfi_startproc
# %bb.0:
	movq	%rsi, (%rdi,%rsi,8)
	movl	$.L.str, %edi
	movq	%rsi, %rdx
	xorl	%eax, %eax
	jmp	printf                          # TAILCALL
.Lfunc_end1:
	.size	_Z13populateArrayPll, .Lfunc_end1-_Z13populateArrayPll
	.cfi_endproc
                                        # -- End function
	.globl	_Z14populateSamplePlS_l         # -- Begin function _Z14populateSamplePlS_l
	.type	_Z14populateSamplePlS_l,@function
_Z14populateSamplePlS_l:                # @_Z14populateSamplePlS_l
	.cfi_startproc
# %bb.0:
	leaq	(%rdx,%rdx,4), %rax
	shlq	$5, %rax
	movq	(%rdi,%rax), %rax
	movq	%rax, (%rsi,%rdx,8)
	movl	$.L.str.1, %edi
	movq	%rdx, %rsi
	movq	%rax, %rdx
	xorl	%eax, %eax
	jmp	printf                          # TAILCALL
.Lfunc_end2:
	.size	_Z14populateSamplePlS_l, .Lfunc_end2-_Z14populateSamplePlS_l
	.cfi_endproc
                                        # -- End function
	.globl	_Z13populateQueryPll            # -- Begin function _Z13populateQueryPll
	.type	_Z13populateQueryPll,@function
_Z13populateQueryPll:                   # @_Z13populateQueryPll
	.cfi_startproc
# %bb.0:
	pushq	%r14
	.cfi_def_cfa_offset 16
	pushq	%rbx
	.cfi_def_cfa_offset 24
	pushq	%rax
	.cfi_def_cfa_offset 32
	.cfi_offset %rbx, -24
	.cfi_offset %r14, -16
	movq	%rsi, %rbx
	movq	%rdi, %r14
	callq	rand
	cltq
	imulq	$1374389535, %rax, %rcx         # imm = 0x51EB851F
	movq	%rcx, %rdx
	shrq	$63, %rdx
	sarq	$37, %rcx
	addl	%edx, %ecx
	imull	$100, %ecx, %ecx
	subl	%ecx, %eax
	movslq	%eax, %rdx
	movq	%rdx, (%r14,%rbx,8)
	movl	$.L.str.2, %edi
	movq	%rbx, %rsi
	xorl	%eax, %eax
	addq	$8, %rsp
	.cfi_def_cfa_offset 24
	popq	%rbx
	.cfi_def_cfa_offset 16
	popq	%r14
	.cfi_def_cfa_offset 8
	jmp	printf                          # TAILCALL
.Lfunc_end3:
	.size	_Z13populateQueryPll, .Lfunc_end3-_Z13populateQueryPll
	.cfi_endproc
                                        # -- End function
	.globl	_Z19binary_search_guessPlll     # -- Begin function _Z19binary_search_guessPlll
	.type	_Z19binary_search_guessPlll,@function
_Z19binary_search_guessPlll:            # @_Z19binary_search_guessPlll
	.cfi_startproc
# %bb.0:
	testq	%rsi, %rsi
	jle	.LBB4_1
# %bb.2:                                # %.lr.ph.preheader
	decq	%rsi
	xorl	%ecx, %ecx
.LBB4_3:                                # %.lr.ph
                                        # =>This Inner Loop Header: Depth=1
	leaq	(%rsi,%rcx), %r8
	movq	%r8, %rax
	shrq	$63, %rax
	addq	%r8, %rax
	sarq	%rax
	movq	(%rdi,%rax,8), %r9
	cmpq	%rdx, %r9
	jge	.LBB4_5
# %bb.4:                                #   in Loop: Header=BB4_3 Depth=1
	leaq	1(%rax), %rcx
	jmp	.LBB4_8
.LBB4_5:                                #   in Loop: Header=BB4_3 Depth=1
	je	.LBB4_14
# %bb.6:                                #   in Loop: Header=BB4_3 Depth=1
	jle	.LBB4_8
# %bb.7:                                #   in Loop: Header=BB4_3 Depth=1
	leaq	-1(%rax), %rsi
.LBB4_8:                                #   in Loop: Header=BB4_3 Depth=1
	cmpq	%rsi, %rcx
	jle	.LBB4_3
# %bb.9:                                # %._crit_edge
	cmpq	$2, %r8
	jl	.LBB4_14
# %bb.10:                               # %._crit_edge
	cmpq	%rdx, %r9
	jle	.LBB4_14
.LBB4_11:                               # %.preheader
                                        # =>This Inner Loop Header: Depth=1
	cmpq	%rdx, (%rdi,%rax,8)
	jle	.LBB4_14
# %bb.12:                               #   in Loop: Header=BB4_11 Depth=1
	leaq	-1(%rax), %rcx
	cmpq	$1, %rax
	movq	%rcx, %rax
	jg	.LBB4_11
# %bb.13:
	xorl	%eax, %eax
.LBB4_14:                               # %.critedge
	retq
.LBB4_1:
                                        # implicit-def: $rax
	retq
.Lfunc_end4:
	.size	_Z19binary_search_guessPlll, .Lfunc_end4-_Z19binary_search_guessPlll
	.cfi_endproc
                                        # -- End function
	.globl	_Z21binary_search_precisePllll  # -- Begin function _Z21binary_search_precisePllll
	.type	_Z21binary_search_precisePllll,@function
_Z21binary_search_precisePllll:         # @_Z21binary_search_precisePllll
	.cfi_startproc
# %bb.0:
	movq	$-1, %rax
.LBB5_1:                                # =>This Inner Loop Header: Depth=1
	cmpq	%rcx, %rdx
	jg	.LBB5_6
# %bb.2:                                # %.lr.ph
                                        #   in Loop: Header=BB5_1 Depth=1
	leaq	(%rcx,%rdx), %r9
	movq	%r9, %r8
	shrq	$63, %r8
	addq	%r9, %r8
	sarq	%r8
	movq	(%rdi,%r8,8), %r9
	cmpq	%rsi, %r9
	jge	.LBB5_4
# %bb.3:                                #   in Loop: Header=BB5_1 Depth=1
	incq	%r8
	movq	%r8, %rdx
	jmp	.LBB5_1
.LBB5_4:                                #   in Loop: Header=BB5_1 Depth=1
	je	.LBB5_5
# %bb.7:                                #   in Loop: Header=BB5_1 Depth=1
	jle	.LBB5_1
# %bb.8:                                #   in Loop: Header=BB5_1 Depth=1
	decq	%r8
	movq	%r8, %rcx
	jmp	.LBB5_1
.LBB5_5:
	movq	%r8, %rax
.LBB5_6:                                # %._crit_edge
	retq
.Lfunc_end5:
	.size	_Z21binary_search_precisePllll, .Lfunc_end5-_Z21binary_search_precisePllll
	.cfi_endproc
                                        # -- End function
	.globl	_Z6searchPlS_S_S_l              # -- Begin function _Z6searchPlS_S_S_l
	.type	_Z6searchPlS_S_S_l,@function
_Z6searchPlS_S_S_l:                     # @_Z6searchPlS_S_S_l
	.cfi_startproc
# %bb.0:
	pushq	%r15
	.cfi_def_cfa_offset 16
	pushq	%r14
	.cfi_def_cfa_offset 24
	pushq	%r12
	.cfi_def_cfa_offset 32
	pushq	%rbx
	.cfi_def_cfa_offset 40
	pushq	%rax
	.cfi_def_cfa_offset 48
	.cfi_offset %rbx, -40
	.cfi_offset %r12, -32
	.cfi_offset %r14, -24
	.cfi_offset %r15, -16
	movq	%r8, %rbx
	movq	%rdx, %r14
	movq	%rsi, %rax
	movq	%rdi, %r15
	movq	(%rcx,%r8,8), %r12
	movl	$5, %esi
	movq	%rax, %rdi
	movq	%r12, %rdx
	callq	_Z19binary_search_guessPlll
	leaq	(,%rax,4), %rcx
	imulq	$100, %rax, %rax
	addq	$100, %rax
	movabsq	$7378697629483820647, %rdx      # imm = 0x6666666666666667
	imulq	%rdx
	leaq	(%rcx,%rcx,4), %rcx
	movq	%rdx, %rax
	shrq	$63, %rax
	sarq	%rdx
	addq	%rax, %rdx
	movq	$-1, %rax
.LBB6_1:                                # =>This Inner Loop Header: Depth=1
	cmpq	%rdx, %rcx
	jg	.LBB6_6
# %bb.2:                                # %.lr.ph.i
                                        #   in Loop: Header=BB6_1 Depth=1
	leaq	(%rcx,%rdx), %rdi
	movq	%rdi, %rsi
	shrq	$63, %rsi
	addq	%rdi, %rsi
	sarq	%rsi
	movq	(%r15,%rsi,8), %rdi
	cmpq	%r12, %rdi
	jge	.LBB6_4
# %bb.3:                                #   in Loop: Header=BB6_1 Depth=1
	incq	%rsi
	movq	%rsi, %rcx
	jmp	.LBB6_1
.LBB6_4:                                #   in Loop: Header=BB6_1 Depth=1
	je	.LBB6_5
# %bb.7:                                #   in Loop: Header=BB6_1 Depth=1
	jle	.LBB6_1
# %bb.8:                                #   in Loop: Header=BB6_1 Depth=1
	decq	%rsi
	movq	%rsi, %rdx
	jmp	.LBB6_1
.LBB6_5:
	movq	%rsi, %rax
.LBB6_6:                                # %_Z21binary_search_precisePllll.exit
	movq	%rax, (%r14,%rbx,8)
	addq	$8, %rsp
	.cfi_def_cfa_offset 40
	popq	%rbx
	.cfi_def_cfa_offset 32
	popq	%r12
	.cfi_def_cfa_offset 24
	popq	%r14
	.cfi_def_cfa_offset 16
	popq	%r15
	.cfi_def_cfa_offset 8
	retq
.Lfunc_end6:
	.size	_Z6searchPlS_S_S_l, .Lfunc_end6-_Z6searchPlS_S_S_l
	.cfi_endproc
                                        # -- End function
	.globl	main                            # -- Begin function main
	.type	main,@function
main:                                   # @main
	.cfi_startproc
# %bb.0:
	pushq	%rbp
	.cfi_def_cfa_offset 16
	pushq	%r15
	.cfi_def_cfa_offset 24
	pushq	%r14
	.cfi_def_cfa_offset 32
	pushq	%r13
	.cfi_def_cfa_offset 40
	pushq	%r12
	.cfi_def_cfa_offset 48
	pushq	%rbx
	.cfi_def_cfa_offset 56
	subq	$40, %rsp
	.cfi_def_cfa_offset 96
	.cfi_offset %rbx, -56
	.cfi_offset %r12, -48
	.cfi_offset %r13, -40
	.cfi_offset %r14, -32
	.cfi_offset %r15, -24
	.cfi_offset %rbp, -16
	movl	$800, %edi                      # imm = 0x320
	callq	malloc
	movq	%rax, %rbx
	movl	$40, %edi
	callq	malloc
	movq	%rax, %r14
	movl	$80, %edi
	callq	malloc
	movq	%rax, %r15
	movl	$80, %edi
	callq	malloc
	movq	%rax, %r12
	leaq	32(%rsp), %rdi
	movl	$800, %esi                      # imm = 0x320
	callq	hipMalloc
	leaq	24(%rsp), %rdi
	movl	$40, %esi
	callq	hipMalloc
	leaq	16(%rsp), %rdi
	movl	$80, %esi
	callq	hipMalloc
	leaq	8(%rsp), %rdi
	movl	$80, %esi
	callq	hipMalloc
	movl	$.Lstr, %edi
	callq	puts@PLT
	xorl	%r13d, %r13d
.LBB7_1:                                # =>This Inner Loop Header: Depth=1
	movq	%r13, (%rbx,%r13,8)
	movl	$.L.str, %edi
	movq	%r13, %rsi
	movq	%r13, %rdx
	xorl	%eax, %eax
	callq	printf
	incq	%r13
	cmpq	$100, %r13
	jne	.LBB7_1
# %bb.2:
	movl	$.Lstr.1, %edi
	callq	puts@PLT
	xorl	%r13d, %r13d
.LBB7_3:                                # =>This Inner Loop Header: Depth=1
	callq	rand
	cltq
	imulq	$1374389535, %rax, %rcx         # imm = 0x51EB851F
	movq	%rcx, %rdx
	shrq	$63, %rdx
	sarq	$37, %rcx
	addl	%edx, %ecx
	imull	$100, %ecx, %ecx
	subl	%ecx, %eax
	movslq	%eax, %rdx
	movq	%rdx, (%r12,%r13,8)
	movl	$.L.str.2, %edi
	movq	%r13, %rsi
	xorl	%eax, %eax
	callq	printf
	incq	%r13
	cmpq	$10, %r13
	jne	.LBB7_3
# %bb.4:
	movl	$.Lstr.2, %edi
	callq	puts@PLT
	movq	%rbx, %rbp
	xorl	%r13d, %r13d
.LBB7_5:                                # =>This Inner Loop Header: Depth=1
	movq	(%rbp), %rdx
	movq	%rdx, (%r14,%r13,8)
	movl	$.L.str.1, %edi
	movq	%r13, %rsi
	xorl	%eax, %eax
	callq	printf
	incq	%r13
	addq	$160, %rbp
	cmpq	$5, %r13
	jne	.LBB7_5
# %bb.6:
	movl	$.Lstr.3, %edi
	callq	puts@PLT
	xorl	%r13d, %r13d
.LBB7_7:                                # =>This Inner Loop Header: Depth=1
	movq	%rbx, %rdi
	movq	%r14, %rsi
	movq	%r15, %rdx
	movq	%r12, %rcx
	movq	%r13, %r8
	callq	_Z6searchPlS_S_S_l
	incq	%r13
	cmpq	$10, %r13
	jne	.LBB7_7
# %bb.8:
	movl	$.Lstr.4, %edi
	callq	puts@PLT
	xorl	%r13d, %r13d
.LBB7_9:                                # =>This Inner Loop Header: Depth=1
	movq	(%r15,%r13,8), %rdx
	movq	(%r12,%r13,8), %rcx
	movl	$.L.str.8, %edi
	movq	%r13, %rsi
	xorl	%eax, %eax
	callq	printf
	incq	%r13
	cmpq	$10, %r13
	jne	.LBB7_9
# %bb.10:
	movq	32(%rsp), %rdi
	callq	hipFree
	movq	24(%rsp), %rdi
	callq	hipFree
	movq	16(%rsp), %rdi
	callq	hipFree
	movq	8(%rsp), %rdi
	callq	hipFree
	movq	%rbx, %rdi
	callq	free
	movq	%r14, %rdi
	callq	free
	movq	%r15, %rdi
	callq	free
	movq	%r12, %rdi
	callq	free
	xorl	%eax, %eax
	addq	$40, %rsp
	.cfi_def_cfa_offset 56
	popq	%rbx
	.cfi_def_cfa_offset 48
	popq	%r12
	.cfi_def_cfa_offset 40
	popq	%r13
	.cfi_def_cfa_offset 32
	popq	%r14
	.cfi_def_cfa_offset 24
	popq	%r15
	.cfi_def_cfa_offset 16
	popq	%rbp
	.cfi_def_cfa_offset 8
	retq
.Lfunc_end7:
	.size	main, .Lfunc_end7-main
	.cfi_endproc
                                        # -- End function
	.type	.L.str,@object                  # @.str
	.section	.rodata.str1.1,"aMS",@progbits,1
.L.str:
	.asciz	"array[%ld] = %ld\n"
	.size	.L.str, 18

	.type	.L.str.1,@object                # @.str.1
.L.str.1:
	.asciz	"sample[%ld] = %ld\n"
	.size	.L.str.1, 19

	.type	.L.str.2,@object                # @.str.2
.L.str.2:
	.asciz	"query[%ld] = %ld\n"
	.size	.L.str.2, 18

	.type	.L.str.8,@object                # @.str.8
.L.str.8:
	.asciz	"results[%ld] = (%ld == [%ld])\n"
	.size	.L.str.8, 31

	.type	__hip_cuid_,@object             # @__hip_cuid_
	.bss
	.globl	__hip_cuid_
__hip_cuid_:
	.byte	0                               # 0x0
	.size	__hip_cuid_, 1

	.type	.Lstr,@object                   # @str
	.section	.rodata.str1.1,"aMS",@progbits,1
.Lstr:
	.asciz	"Populating Array"
	.size	.Lstr, 17

	.type	.Lstr.1,@object                 # @str.1
.Lstr.1:
	.asciz	"Populating Query"
	.size	.Lstr.1, 17

	.type	.Lstr.2,@object                 # @str.2
.Lstr.2:
	.asciz	"Populating Sample"
	.size	.Lstr.2, 18

	.type	.Lstr.3,@object                 # @str.3
.Lstr.3:
	.asciz	"Processing Query"
	.size	.Lstr.3, 17

	.type	.Lstr.4,@object                 # @str.4
.Lstr.4:
	.asciz	"Printing Results"
	.size	.Lstr.4, 17

	.ident	"AMD clang version 18.0.0git (https://github.com/RadeonOpenCompute/llvm-project roc-6.3.2 25012 e5bf7e55c91490b07c49d8960fa7983d864936c4)"
	.section	".note.GNU-stack","",@progbits
	.addrsig
	.addrsig_sym __hip_cuid_

	.text
	.p2alignl 7, 3214868480
	.fill 96, 4, 3214868480
	.type	__hip_cuid_,@object             ; @__hip_cuid_
	.section	.bss,"aw",@nobits
	.globl	__hip_cuid_
__hip_cuid_:
	.byte	0                               ; 0x0
	.size	__hip_cuid_, 1

	.ident	"AMD clang version 18.0.0git (https://github.com/RadeonOpenCompute/llvm-project roc-6.3.2 25012 e5bf7e55c91490b07c49d8960fa7983d864936c4)"
	.section	".note.GNU-stack","",@progbits
	.addrsig
	.addrsig_sym __hip_cuid_
	.amdgcn_target "amdgcn-amd-amdhsa--gfx1100"
	.amdgpu_metadata
---
amdhsa.kernels:  []
amdhsa.target:   amdgcn-amd-amdhsa--gfx1100
amdhsa.version:
  - 1
  - 2
...

	.end_amdgpu_metadata
