;
; BINSRD.MAC
; SOURCE FOR MACRO SUBROUTINE TO DO A BINARY SEARCH ON AN INDEX FILE
; THIS ROUTINE FINDS THE FIRST INDEX RECORD THAT MATCHES THE GIVEN STRING.
; BASIC CALL:
;       CALL "BINSRC"(A$,A,B[,C,D])
; OR
;	CALL "NXTSRC"(A$,A,B[,C,D])
; WHERE:
;	A$ = STRING TO BE SEARCHED FOR
;	A  = FILE # OF INDEX FILE (PRODUCED BY EITHER V1 OR V2 SORT)
;	     VALUE IS THAT ASSIGNED IN BASIC OPEN COMMAND.
;	     EXECUTED ONCE BEFORE FIRST CALL TO SUBROUTINE.
;	B  = REC # RETURNED BY SUBROUTINE
;		IF NEGATIVE, NO MATCH BUT VALUE IS PLACE WHERE A
;		MATCH WOULD GO. ZERO MEANS FILE NOT OPEN.
;	(NXTSRC ONLY) ON ENTRY THIS WILL BE FILLED IN WITH THE
;		RECORD NUMBER OF THE LAST INDEX FILE RECORD WHICH
;		MATCHED. THE SEARCH WILL THEN LOOK ONLY AT THE NEXT
;		INDEX FILE RECORD. NXTSRC IS USEFUL ONLY IF USING
;		THE OPTIONAL ARGUMENTS TO OBTAIN THE MAIN FILE
;		RECORD.
;	C = (OPTIONAL) REC # RETURNED FOR MAIN FILE
;		NOT CHANGED IF B NEG OR ZERO.
;	D = RECORD SIZE FOR MAIN FILE (NECESSARY IF C SPECIFIED)
;		SIGNIFICANT ONLY IF INDEX FILE PRODUCED BY SORT V2.
;
	.MCALL	ULODHD	FDOF$L	FCSBT$
	ULODHD	START,END,BINSRC,NXTSRC
;
; FOLLOWING MACRO IS USED TO GET THE ABSOLUTE ADDRESS OF A LOCALLY
; DEFINED LABEL IN POSITION INDEPENDENT FASHION (NEEDED FOR LOADABLE
; ROUTINES).
;
	.MACRO GTABAD	ADDRES,LOC
	.NTYPE	...ATP,LOC
	.IF	GT	...ATP-5
	MOV	PC,-(SP)
	ADD	#ADDRES-.,(SP)
	MOV	(SP)+,LOC
	.IFF
	MOV	PC,LOC
	ADD	#ADDRES-.,LOC
	.ENDC
	.ENDM	GTABAD
;
; DEFINE FLOATING REGS
;
AC0=%0
AC1=%1
AC2=%2
AC3=%3
AC4=%4
AC5=%5
FDOF$L
FCSBT$
;
; DEFINE ADDRESS OF .GET ROUTINE IN SYSRES
; THIS VALUE WILL BE DEFINED IN TKB COMMAND FILE
	.GLOBL	ADDGET
START:
NXT:	.WORD	0	;FLAG FOR WHICH ENTRY POINT
RSIZE:	.WORD	0
STROFF:	.WORD	0
RECNAD:	.BLKW	3
;
NXTSRC:
	INC	NXT		;INDICATE WHICH ENTRY POINT
	BR	COM
BINSRC:
	CLR	NXT		;KEEP TRACK OF ENTRY POINT
COM:
	CLR	RECNAD		;CLEAR RECORD NUMBER ADDRESS
	SETI			;MAKE SURE IN INTEGER MODE
	JSR	R4,@#GTRGPI	;GET ARGUMENTS
	.BYTE	3,1,2,0		;STRING,NUMERIC,NUMERIC RETURNED,END
	.EVEN
	CMPB	(R1),#',	;MORE ARGS?
	BNE	2$		;IF NOT, BRANCH
	JSR	R4,@#GTRGPI	;GET THEM IF SO
	.BYTE	2,1,0
	.EVEN
	MOV	(SP)+,RECNAD	;STORE ADDRESS
	MOV	(SP)+,RECNAD+2	;(3 WORDS)
	MOV	(SP)+,RECNAD+4
	ADD	#4,SP		;SKIP VALUE OF C
	LDF	(SP)+,AC1	;RECORD SIZE -> AC1
	STCFI	AC1,R3		;INTEGERIZE IT
	INC	R3		;ROUND IT UP TO NEAREST
	BIC	#1,R3		;WORD BOUNDARY
	MOV	R3,RSIZE	;AND REMEMBER IT
2$:	JSR	PC,@#PARCHK	;CHECK FOR TRAILING PAREN
	MOV	SP,R5		;R5 HAS ARG LIST PTR
	CMP	(R5)+,(R5)+	;R5 POINTS TO NUMERIC FP VALUE
	LDF	(R5)+,AC0	;PUT LUN # IN AC0
	STCFI	AC0,R4		;CONVERT TO INTEGER
	DEC	R4		;ITS LUN - 1
	MOV	#17400,R0	;PUT MASK IN R0
	JSR	PC,@#SRCHFL	;FIND FCB ADDRESS
	TST	R3		;IF 0 ERROR
	BEQ	10$		;BRANCH TO ERROR ROUTINE
	ADD	#26,R3		;FCB + 26 = FDB
	MOV	R3,R0		;FDB ADDRESS WILL BE KEPT IN R0 FOR GETS
	LDCIF	#1,AC3		;WE WANT REC # 1
	SETL
	STCFL	AC3,F.RCNM(R0)	;PUT REC # WANTED IN FDB
	JSR	PC,GETCOM	;SET READBUF ADDRESS AND LENGTH
	JSR	PC,@#ADDGET	;DO GET
	MOV	#4,STROFF	;ASSUME V1 SORT INDEX FILE
	MOV	F.URBD+2(R0),R3	;ADDRESS OF RECORD -> R3
	TST	4(R3)		;CHECK 3RD WORD
	BEQ	14$		;IF ZERO, V1 SORT, SO BRANCH
	MOV	#6,STROFF	;ELSE IT'S V2 SORT, SO REMEMBER OFFSET
14$:	LDCLF	(R3),AC3	;GET MAX RECORD NUMBER IF V1 SORT
15$:	TST	NXT		;WHICH ROUTINE?
	BEQ	16$		;IF BINARY SEARCH, BRANCH
	LDF	16(SP),AC1	;GET INDEX FILE RECORD NUMBER FOR PREVIOUS MATCH
	ADDF	#1,AC1		;PUT UP TO NEXT RECORD
	LDF	AC1,AC2		;COPY FOR SUBSEQUENT PROCESSING
	CMPF	AC1,AC3		;CHECK AGAINST MAX
	CFCC
	BGT	20$		;IF TOO BIG, NO GO - SO BRANCH
	JSR	PC,READCM	;DO READ OF INDEX FILE
	BEQ	6$		;IF NULL COMPARISON STRING, SUCCESS ALREADY
17$:	CMPB	(R3)+,(R2)+	;SEE IF KEY STRING MATCHES
	BNE	20$		;IF NOT, BRANCH TO FAILURE POINT
	SOB	R4,17$
	BR	6$		;GO TO SUCCESS POINT IF FULL MATCH
16$:	ADDF	#1,AC3		;+1 = LAST REC IN FILE
	LDF	#2,AC0		;AC0 IS LOWER BOUNDARY
	STF	AC3,AC2		;AC2 IS UPPER BOUNDARY
1$:
	STF	AC0,AC1		;AC1 IS THE MIDDLE
	ADDF	AC2,AC1		;= (UPP + LOW + 1 )/2
	ADDF	#1,AC1
	DIVF	#2,AC1
	STCFL	AC1,-(SP)	;DO INTEGER CONVERSION ON STACK
	LDCLF	(SP)+,AC1	;AND BRING IT BACK
	CMPF	#2,AC1		;ARE WE AT LOWER BOUND?
	CFCC
	BEQ	11$		;IF SO, BRANCH TO NOT FOUND CODE
	CMPF	AC1,AC3		;IS MIDDLE EQUAL TO HIGH BOUND
	CFCC
	BEQ	12$		;BRANCH TO NOT FOUND
	JSR	PC,READCM
	BEQ	18$		;IF NULL COMPARISON STRING, SUCCESS AT 1ST REC.
3$:	CMPB	(R2)+,(R3)+	;COMPARE CHARS
	BLT	4$		;WANTED STRING IS LOWER THAN WHERE WE ARE
	BGT	5$		;WANTED STRING IS HIGHER THAN WHERE WE ARE
	SOB	R4,3$		;CHECK EACH CHAR
				;FOUND IT
9$:	STF	AC1,AC2		;PUT REC # IN AC2
	SUBF	#1,AC1		;BACKUP ONE RECORD
	JSR	PC,READCM
8$:	CMPB	(R3)+,(R2)+	;COMPARE CHARS
	BNE	6$		;BACKED UP TOO FAR
	SOB	R4,8$		;CHECK EACH CHAR
	BR	9$		;GO DO AGAIN
18$:	LDF	#3,AC2		;POINT TO FIRST REAL RECORD
	BR	6$		;AND GO TO SUCCESS
10$:	CLRF	AC2		;ERROR END
	BR	6$
11$:	LDF	#3,AC2		;WE WANT TO RETURN A -3
	BR	20$		;BRANCH TO NEGATE ROUTINE
12$:	STF	AC3,AC2		;STORE # OF RECORDS IN FILE + 1
	BR	20$		;BRANCH TO NEGATE
13$:	ADDF	#1,AC2		;WE SUBTRACTED ONE SO NOW WE MUST ADD ONE
20$:	NEGF	AC2		;NEGATE ROUTINE
6$:
	TSTF	AC2		;CHECK ON INDEX FILE RECORD NUMBER
	CFCC
	BMI	7$		;IF NEG, ERROR RETURN, SO BRANCH
	TST	RECNAD		;SEE IF MAIN RECORD NUMBER REQUESTED
	BEQ	7$		;IF NOT, BRANCH
	JSR	PC,RCNOUT	;IF SO, GO RETURN IT
7$:
	STF	AC2,AC0		;COPY INDEX RECORD NUMBER -> AC0
	ADD	#10,SP		;PUT STACK AT ADDRESS FOR ANS
	MOV	SP,R5		;R5 SHOULD HAVE ADDRESS FOR ROUTINE
	SETI
	JSR	PC,@#NSTORE	;STORE THE RESULT
	ADD	#12,SP		;CLEAN STACK
	RTS	PC		;RETURN
4$:	SUBF	#1,AC2		;DEC AC2
	CMPF	AC2,AC0		;ARE HIGH AND LOW BOUND EQUAL
	CFCC
	BEQ	13$		;BRANCH TO NOT FOUND
	STF	AC1,AC2		;MOVE DOWN HIGH BOUND
	BR	1$		;BRANCH TO REPEAT
5$:	ADDF	#1,AC0		;INC AC0
	CMPF	AC0,AC2		;ARE HIGH AND LOW BOUND EQUAL
	CFCC
	BEQ	20$		;BRANCH TO NOT FOUND
	STF	AC1,AC0		;MOVE DOWN HIGH BOUND
	BR	1$		;BRANCH TO REPEAT
GETCOM:	MOV	R0,-(SP)	;PUT FDB ADDRESS ON STACK
	ADD	#S.FDB,(SP)	;ADD OFFSET
	MOV	(SP)+,F.URBD+2(R0);PUT ADDRESS OF READ BUF INTO FDB BLOCK
	MOV	F.RSIZ(R0),F.URBD(R0);PUT REC SIZE IN READ BUF LEN IN FDB BLOCK
	RTS	PC		;RETURN
READCM:
	STCFL	AC1,F.RCNM(R0)	;PUT REC # WANTED IN FDB
	JSR	PC,GETCOM	;SET READBUF ADDRESS AND LENGTH
	JSR	PC,@#ADDGET
	MOV	4(SP),R2	;R2 HAS ADDRESS OF CHECKING STRING
	MOV	F.URBD+2(R0),R3	;R3 HAS ADDRESS OF READ STRING
	ADD	STROFF,R3	;FIRST STROFF BYTES ARE RECORD PTR, SKIP
	MOV	2(SP),R4	;PUT LEN IN R4
	RTS	PC
RCNOUT:
	STCFL	AC2,F.RCNM(R0)	;STORE PROPER RECORD NUMBER
	JSR	PC,GETCOM
	JSR	PC,@#ADDGET	;GET OUR RECORD
	MOV	F.URBD+2(R0),R3	;ADDRESS -> R3
	CMP	STROFF,#4	;SORT V1?
	BNE	1$		;IF NOT, BRANCH
	LDCLF	(R3),AC0	;IF SO, IT'S EASY (JUST STORE RECORD NUMBER)
	SETI			;BETTER GET BACK TO SINGLE INTEGER MODE
	BR	2$		;AND GO STORE IT
1$:				;SORT V2 REQUIRES A LITTLE MORE EFFORT
	SETD			;DO DOUBLE PRECISION FOR FILES > 32 MEGABYTES
	MOV	(R3)+,-(SP)	;REVERSE THE ORDER OF THE BLOCK #
	MOV	(R3)+,-(SP)	;BECAUSE THEY'RE REVERSED IN THE FILE
	LDCLD	(SP)+,AC0	;BLOCK # -> AC0
	SUBD	#1,AC0		;BACK IT DOWN BY 1
	SETI
	LDCID	(R3),AC3	;BYTE NUMBER IN BLOCK -> AC3
	LDCID	#512.,AC1	;# BYTES PER BLOCK -> AC1
	MULD	AC1,AC0		;TOTAL BYTES TO START OF PRESENT BLOCK -> AC0
	ADDD	AC3,AC0		;ADD IN NUMBER OF BYTES IN THIS BLOCK
	LDCID	RSIZE,AC3	;GET RECORD SIZE -> AC3
	DIVD	AC3,AC0		;AND GET FINAL RECORD NUMBER -> AC0
	ADDD	#1,AC0		;RECORDS START AT 1 NOT 0
	SETF			;BACK TO SINGLE PRECISION MODE
2$:	GTABAD	RECNAD,R5	;MAKE R5 POINT TO STORAGE INFO FOR C
	JSR	PC,@#NSTORE	;STORE IT
	RTS	PC
END:
	.END