;;; -*- TI-Asm -*-
;;;
;;; Mimas - Assembly language IDE for the TI-83 Plus
;;; 
;;; Copyright (C) 2010 Benjamin Moody
;;;
;;; This program is free software: you can redistribute it and/or
;;; modify it under the terms of the GNU General Public License as
;;; published by the Free Software Foundation; either version 3 of the
;;; License, or (at your option) any later version.
;;;
;;; This program is distributed in the hope that it will be useful,
;;; but WITHOUT ANY WARRANTY; without even the implied warranty of
;;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
;;; General Public License for more details.
;;;
;;; You should have received a copy of the GNU General Public License
;;; along with this program.  If not, see <http://www.gnu.org/licenses/>.

;; BSearch1:
;;
;; Search for a given byte value in a sorted array.
;;
;; Input:
;; - HL = address of start of array
;; - BC = number of elements
;; - E = value to search for
;;
;; Output:
;; - If the value is found, zero flag set and HL is the address of the
;;   first matching value in the array
;; - If the value is not found, zero flag clear and HL is the address
;;   of the first value that is greater than E.  (If there are none,
;;   then HL will equal the sum of the input HL and BC.)
;;
;; Destroys:
;; - AF, BC

; BSearch1_UpperHalf:
; 	 pop af
; 	inc hl
; 	jr c,BSearch1
; 	dec bc
; BSearch1:
; 	ld a,b
; 	or c
; 	jr z,BSearch1_Finished
; 	srl b
; 	rr c
; 	push af
; 	 add hl,bc
; 	 ld a,(hl)
; 	 cp e
; 	 jr c,BSearch1_UpperHalf
; 	 sbc hl,bc
; 	 pop af
; 	jr BSearch1
; BSearch1_Finished:
; 	ld a,(hl)
; 	cp e
; 	ret


;; BSearch2:
;;
;; Search a sorted array of 2-byte entries.
;;
;; The callback function is called with the given value in DE, and the
;; address of an array element in HL.  It must return with the zero
;; flag set if HL "equals" DE, or with the carry flag set if HL is
;; "less than" DE.  The callback function must preserve DE if it cares
;; about the value, but it need not preserve HL, BC, or AF.
;;
;; Input:
;; - HL = address of first element
;; - BC = number of elements
;; - DE = search key
;; - IX = comparison function
;;
;; Output:
;; - If an exact match was found, zero flag set and HL is the address
;;   of the matching array element
;; - If an exact match was not found, zero flag clear and HL is the
;;   address of the first array element that is "greater" than DE.
;;   (If there are none, then HL will equal the sum of the input HL
;;   and BC.)
;;
;; Destroys:
;; - AF, BC

; BSearch2_UpperHalf:
; 	   pop hl
; 	  pop af
; 	 pop bc
; 	;; top half has size ceil(BC / 2) - 1 = floor((BC - 1) / 2)
; 	inc hl
; 	inc hl
; 	dec bc
; BSearch2_Continue:
; 	srl b
; 	rr c
; BSearch2:
; 	ld a,b
; 	or c
; 	jr z,BSearch_Failed
; 	push bc
; 	 push hl
; 	  ;; add 2 * floor(BC / 2)
; 	  res 0,c
; 	  add hl,bc
; 	  push hl
; 	   call Call_IX
; 	   jr z,BSearch2_Success
; 	   jr c,BSearch2_UpperHalf
; 	   pop af
; 	  pop hl
; 	 pop bc
; 	;; bottom half has size floor(BC / 2)
; 	jr BSearch2_Continue
; BSearch2_Success:
; 	   pop hl
; 	  pop bc
; 	 pop bc
; 	ret


;; BSearchS:
;;
;; Search a sorted list of variable-length entries, such as
;; zero-terminated strings or compressed symbol strings.
;;
;; The callback function is called with the given value in DE, and an
;; arbitrary address in the list (which might either be at the start
;; or the middle of an entry) in HL.  It must do one of the following:
;;
;; - Set HL to the address of the start of the given entry, and return
;;   with the zero flag set, indicating that the given entry "equals"
;;   DE;
;; - Set HL to the address of the start of the given entry, and return
;;   with zero and carry flags reset, indicating that the given entry
;;   is "greater" than DE; or
;; - Set HL to the address of the start of the *next* entry, and
;;   return with zero flag reset and carry flag set, indicating that
;;   the given entry is "less" than DE.
;;
;; The callback function must preserve DE if it cares about the value,
;; but it need not preserve BC or AF.
;;
;; Note that the list usually needs to have a sentinel value placed
;; before the first byte, and occasionally also after the last byte,
;; so that the callback function will be able to identify the start
;; and end of the first and last string in the list, respectively.
;;
;; There is no reason, however, why the "addresses" given in HL and
;; BC, and passed to and returned by the callback function, need to be
;; actual Z80 memory addresses; see SeekCompare_oI8SStr_pZStr and
;; SeekCompare_Char_pZStr for examples of other types of "addresses".
;;
;; Input:
;; - HL = address of start of list
;; - BC = address of byte following end of list
;; - DE = search key
;; - IX = seek/compare function
;;
;; Output:
;; - If an exact match was found, zero flag set and HL is the address
;;   of the matching array element
;; - If an exact match was not found, zero flag clear and HL is the
;;   address of the first array element that is "greater" than DE.
;;   (If there are none, HL equals the input BC.)
;;
;; Destroys:
;; - AF, BC

BSearchS_UpperHalf:
	  pop bc
	 pop af
BSearchS:
	xor a
	sbc hl,bc
	add hl,bc
	jr z,BSearch_Failed
	jr nc,BSearchS_Error
	push hl
	 push bc
	  add hl,bc
	  rr h
	  rr l
	  call Call_IX
	  jr z,BSearchS_Success
	  jr c,BSearchS_UpperHalf
	  ld b,h
	  ld c,l
	  pop af
	 pop hl
	jr BSearchS
BSearchS_Success:
	  pop bc
	 pop bc
	ret
BSearch_Failed:
	inc a
	ret
BSearchS_Error:
	;; If we ever get here, it means that either the array was not
	;; properly terminated, or there is a bug in the callback
	;; function.
	BCALL _ErrSignChange
	;; UNREACHABLE


;; SeekCompare_pI8ZStr_pWStr:
;;
;; Seek/compare function for register strings (strings of uppercase
;; ASCII letters, zero terminated and preceded by a single-byte
;; register value.)
;;
;; Input:
;; - HL = address within a register string
;; - DE = address of string (terminated by 0 or a non-word char)
;;
;; Output:
;; - Zero flag set, and HL = start of string, if HL "equals" DE
;; - Zero and carry flags reset, and HL = start of string, if HL is
;;   "greater" than DE
;; - Zero flag reset, carry flag set, and HL = end of string, if HL is
;;   "less" than DE
;;
;; Destroys:
;; - AF, BC

SeekCompare_pI8ZStr_pWStr:
	;; search backwards for the previous zero byte
	dec hl
	ld a,(hl)
	or a
	jr nz,SeekCompare_pI8ZStr_pWStr
	inc hl			; skip that zero byte
	inc hl			; skip register value
	;; HL = start of register string
	call CompareWords
	jr c,SeekCompare_pI8ZStr_pWStr_Next
	dec hl			; HL -> register value
	ret
SeekCompare_pI8ZStr_pWStr_Next:
	;; search for end of register string
	ld a,(hl)
	inc hl
	cp 1
	jr nc,SeekCompare_pI8ZStr_pWStr_Next
	ret

;; SeekCompare_oI8SStr_pZStr:
;;
;; Seek/compare function for user symbol strings (0-nibble-terminated
;; packed strings preceded by an 8-bit symbol-number hint.)
;;
;; Input:
;; - HL = program offset within a symbol string
;; - DE = address of zero-terminated string
;;
;; Output:
;; - Zero flag set, and HL = start of string, if HL "equals" DE
;; - Zero and carry flags reset, and HL = start of string, if HL is
;;   "greater" than DE
;; - Zero flag reset, carry flag set, and HL = end of string, if HL is
;;   "less" than DE
;;
;; Destroys:
;; - AF, BC

SeekCompare_oI8SStr_pZStr:
	;; seek backwards to find previous byte with low nibble clear
	dec hl
	call GetProgramDataByte
	and 0Fh
	jr nz,SeekCompare_oI8SStr_pZStr
	inc hl			; skip that byte
	push hl
	 inc hl			; skip symbol-number hint
	 ;; HL = offset to start of symbol string
	 call ProgramOffsetToAddress
	 or a
	 jr z,SeekCompare_oI8SStr_pZStr_InRAM
	 push de
	  ld de,OP4
	  push de
	   call SymbolStringToRAM
	   pop hl
	  pop de
SeekCompare_oI8SStr_pZStr_InRAM:
	 push de
	  call CompareToSymbolString
	  bit 6,c
	  pop de
	 pop hl
	ret z
	ccf
	ret nc
SeekCompare_oI8SStr_pZStr_Next:
	;; search for end of this symbol string
	call GetProgramDataByte
	inc hl
	and 0Fh
	jr nz,SeekCompare_oI8SStr_pZStr_Next
	sub 1
	ret

;; Extract_oI8SStr:
;;
;; Extract a symbol name from the current program.
;;
;; Input:
;; - HL = program offset to symbol info (8 bit symbol-number hint
;;   followed by 0-nibble-terminated packed string)
;; - DE = address of buffer to place result (at least 66 bytes)
;;
;; Output:
;; - HL = address of zero-terminated string (stored somewhere within
;;   the input buffer)
;;
;; Destroys:
;; - AF, BC, DE

Extract_oI8SStr:
	inc hl
	call ProgramOffsetToAddress
;	ld de,OP1
	push de
	 call SymbolStringToRAM
	 pop hl
	push de
	 call UnpackSymbolString
	 pop hl
	ret

;; Extract_pI16SStr:
;;
;; Extract a builtin symbol name.
;;
;; Input:
;; - HL = address of symbol info on page 1 (16-bit value followed by
;;   0-nibble-terminated symbol string
;; - DE = address of buffer to place result (at least 33 bytes)
;;
;; Output:
;; - HL = address of zero-terminated string (= input DE)
;;
;; Destroys:
;; - AF, BC, DE

Extract_pI16SStr:
	inc hl
	inc hl
;	ld de,OP1
	push de
	 call UnpackSymbolString
	 pop hl
	ret

;; SeekCompare_pMStr_pZStr:
;;
;; Seek/compare function for instruction mnemonic strings (strings of
;; uppercase ASCII letters terminated by a byte with bit 7 set.)
;;
;; Input:
;; - HL = address within a mnemonic string
;; - DE = address of zero-terminated string
;;
;; Output:
;; - Zero flag set, and HL = start of string, if HL "equals" DE
;; - Zero and carry flags reset, and HL = start of string, if HL is
;;   "greater" than DE
;; - Zero flag reset, carry flag set, and HL = end of string, if HL is
;;   "less" than DE
;;
;; Destroys:
;; - AF, BC

SeekCompare_pMStr_pZStr:
	;; search backwards to find previous byte with bit 7 set
	dec hl
	ld a,(hl)
	rla
	jr c,SeekCompare_pMStr_pZStr
	inc hl			; skip that byte
	;; HL = start of mnemonic string
	push hl
	 push de
SeekCompare_pMStr_pZStr_Loop:
	  ld a,(de)
	  and ~20h
	  jr z,SeekCompare_pMStr_pZStr_RetPrev ; string @ DE too short
					       ; -> return NZ, NC
	  ld b,(hl)
	  res 7,b
	  cp b
	  jr nz,SeekCompare_pMStr_pZStr_Failed
	  cp (hl)
	  inc hl
	  inc de
	  jr nz,SeekCompare_pMStr_pZStr_Loop
	  ld a,(de)
	  or a
	  jr z,SeekCompare_pMStr_pZStr_Match
	  ;; string @ DE too long -> HL already pointing to start of
	  ;; next str; return NZ, C
	  jr SeekCompare_pMStr_pZStr_RetNext

SeekCompare_pMStr_pZStr_Failed:
	  ;; C -> (DE) < (HL) -> return NZ, NC
	  ;; NC -> (DE) > (HL) -> move to next str, return NZ, C
	  jr c,SeekCompare_pMStr_pZStr_RetPrev
SeekCompare_pMStr_pZStr_Next:
	  ld a,(hl)
	  inc hl
	  rla
	  jr c,SeekCompare_pMStr_pZStr_Next
SeekCompare_pMStr_pZStr_RetNext:
	  scf
	  pop de
	 pop bc
	ret
SeekCompare_pMStr_pZStr_RetPrev:
	  or 1
SeekCompare_pMStr_pZStr_Match:
	  pop de
	 pop hl
	ret

;; Extract_pMStr:
;;
;; Extract an instruction mnemonic string.  (We also add 1 to 5 wide
;; space characters to the end of the string, so that arguments will
;; line up nicely on screen.)
;;
;; Input:
;; - HL = address of mnemonic string
;; - DE = address of buffer to place result (at least 7 bytes)
;;
;; Output:
;; - HL = address of zero-terminated string (= input DE)
;;
;; Destroys:
;; - AF, BC, DE

Extract_pMStr:
;	ld de,OP1
	push de
	 ld b,5			; number of spaces to append
Extract_pMStr_Loop:
	 dec b
	 jr nz,Extract_pMStr_BNot0
	 inc b
Extract_pMStr_BNot0:
	 ld a,(hl)
	 and 7Fh
	 ld (de),a
	 cp (hl)
	 inc hl
	 inc de
	 jr nz,Extract_pMStr_Loop
	 ld a,SFourSpaces
Extract_pMStr_PadLoop:
	 ld (de),a
	 inc de
	 djnz Extract_pMStr_PadLoop
	 xor a
	 ld (de),a
	 pop hl
	ret

;; SeekCompare_Char_pZStr:
;;
;; Seek/compare function for characters.  This function is only used
;; by the CHARACTER menu; as such, rather than actually comparing
;; character values, it interprets the input ZT string as a hex digit
;; and compares that to the MS nibble of the character (so that
;; pressing ALPHA+A selects the character A0h, etc.)
;;
;; Input:
;; - L = character
;; - DE = address of zero-terminated string
;;
;; Output:
;; - Zero flag set if L "equals" DE
;; - Zero and carry flags reset if L is "greater" than DE
;; - Zero flag reset, carry flag set, and L incremented, if L is
;;   "less" than DE
;;
;; Destroys:
;; - AF

SeekCompare_Char_pZStr:
	ld a,(de)
	sub '0'
	ccf
	ret nc
	cp 17h
	ccf
	jr c,SeekCompare_Char_pZStr_Next
	add a,a
	add a,a
	add a,a
	add a,a
	jr nc,SeekCompare_Char_pZStr_Digit
	add a,090h
SeekCompare_Char_pZStr_Digit:
	cp l
	ret z
	ccf
	ret nc
SeekCompare_Char_pZStr_Next:
	inc l
	ret

;; Extract_Char:
;;
;; "Extract" a single-character string.
;;
;; Input:
;; - L = character
;; - DE = address of buffer to place result (at least 2 bytes)
;;
;; Output:
;; - HL = address of zero-terminated string (= input DE)
;;
;; Destroys:
;; - AF, BC, DE

Extract_Char:
	ld a,l
;	ld hl,OP1
	ex de,hl
	ld (hl),a
	inc hl
	ld (hl),0
	dec hl
	ret