/*
	This C language subroutine performs a binary search
	on an array of data.
	
	The Run Time Library for the C Language.

	Gordon A. Sterling	(617) 461 - 3076
	DSP Development Tools Engineering

	Created on 12/12/92 
	Updated on 5/94 by AS

	#include <stdlib.h>		    <Header>
	char *bsearch ((void *) key, (void *) base, \	<Prototype>
			unsigned nel, sizeof (*key), \	<Prototype>
			int (*compar)())		<Prototype>

*/

#include "lib_glob.h"
#include "sdl_glob.h"

.SEGMENT/CODE	Code_Space_Name;
.FILE 		RTL_FILENAME;

.GLOBAL	    	_bsearch;

_bsearch:	put(R5);
		put(R13);				
		readparam4(R13);
		
		JUMP (PC, first_entry) (DB); /* Don't shift first*/
		readparam5(pm_ptr);
		pm_lnt=pm_0;		/* Check for 0 length	*/
	
loop_again:	R5=LSHIFT R5 BY -1;	/* Split size by 2	*/
first_entry:	R5=PASS R5, R0=R5;	/* Test for a limit	*/
		IF EQ JUMP (PC, restore_state) (DB); /*Ret NULL	*/
		FETCH_RETURN
		nop;
		R2=LSHIFT R5 BY -1;	/* Find midpoint	*/
		R2=R2*R13 (SSI);	/* Compute offset	*/
		R2=R2+R8, CALLER_HOLD(R0) /* Compute pointer	*/
		R8=PASS R2, CALLER_SWAP	/* Copy to register	*/
		JUMP (pm_0, pm_ptr) (DB);/* Jump to compare()	*/
		SAVE_OLD_FRAME(R0)
label_1:	SAVE_RET_ADDR

		R0=PASS R0, pm_lnt=pm_0; /* R0 is returned from fcn call*/	
		IF EQ JUMP (PC, restore_state) (DB);/* Return with ptr*/
		FETCH_RETURN
		nop;
		IF LT JUMP (PC, loop_again);
		JUMP (PC, loop_again) (DB); /* Try next location*/
		R8=R2+R13;		/* Compute new base	*/
		R5=R5-1;		/* Reduce length	*/

restore_state:	get(R13,1);
		get(R5,2);
		RETURN (DB);
		RESTORE_STACK
		RESTORE_FRAME

.ENDSEG;