;/*static char *SCCSID = "@(#)asfbcb.asm	6.3 91/11/03";*/
;***	ASFBCB.ASM - scan for bit block run ending on a cache block boundary

.286
.model MEDIUM, PASCAL

ifdef MEDIUM_MODEL
CALLTYPE    equ <far>
else
CALLTYPE    equ <near>
endif

.data

extrn abCont:byte
extrn abRCont:byte
extrn abLCont:byte
extrn abFillMask:byte

;***	BUGBUG - cleanup for future.  When we go to a MASM that no longer has
;	bugs for local variables, the following should become part of the
;	procedure header.  Since local vars do NOT work, we make these
;	variables be static data references.  We can do this because this
;	routine never blocks and never calls another routine.

.data
cFFtoScan	dw  ?			; number of FFs to find (one
					; less than number needed)
cbLeftInBitmap	dw  ?			; number of bytes left in bitmap
					; after second byte in 0xFF string
oSecondByte	dw  ?			; offset to second byte in 0xFF string

.CODE ASWAP0

;
;
;	One of the most performance sensitive parts of pinball is the scan
;	for blocks of free sectors.  This occurs on all file creations as
;	well as for directory splitting and file extension.  It is crucial
;	that this be as fast as possible.
;
;	Being so performance critical, we divide the problem of looking
;	within a bitmap for a block of contiguous bits into two cases:
;
;	Looking for 8 bits or less
;	    L1: scan for non-zero word
;		check word.  If it has sufficient contig, we're done.
;		take "right contig" add to "left contig" of next.  If it's
;		    enough, we're done
;		goto L1:
;
;	Looking for 9-14 bits
;	    L1: scan for non-zero word w/ right-most (high order) bit
;		take "right contig" add to "left contig" of next.  If it's
;		    enough, we're done
;		if next != 0xFF, goto L1
;		add left contig of next+1.  If enough, done, else skip one
;		goto L1:
;
;	Looking for 15 bits or more
;		I = (N-7)/8
;	    L1: scan for I 0xFF bytes in string.
;		add right contig of preceding byte to left contig of trailing
;		byte, if OK, done, else
;		skip I bytes
;		goto L1:
;
;
;	ENTRY:	(cusBitsReq)	    number of contiguous bits that we want
;		(cbToSearch)	    remaining bytes in bitmap band to search
;		(pbStart)	    starting address for search
;		(poffusFirstFound)  offset into search area of first sector found
;
;	EXIT:	returns TRUE if bits were found
;		    *poffusFirstFound = offset in bits from beginning of bitmap
;		returns FALSE otherwise
;
;	USES:	AX, BX, CX, DX, ES

SFBCB	proc CALLTYPE	uses	si di,	\
    cusBitsReq:WORD,		\
    cbToSearch:WORD,		\
    pbStart:DWORD,		\
    poffusFirstFound:DWORD

	mov	ax,cusBitsReq		; (ax) = # of contig bits that we want
	mov	cx,cbToSearch		; (cx) = remaning bytes in bitmap structure (from DI),non-zero
	les	di,pbStart		; (es:di) = address of bitmap in memory

	xor	bx,bx			; (bx) = 0
	cmp	ax,8			; looking for more than 8 sectors?
	jbe	sfb2                    ; no
	jmp	sfbBigAlloc		; yes
sfb2:
	xchg	ah,al			; (ah) = sectors needed, (al) = 0

;	Need 8 or less.  First, scan for a non-zero byte.
;
;   L1: scan for non-zero word
;	check word.  If it has sufficient contig, we're done.
;	take "right contig" add to "left contig" of next.  If it's enough,
;		we're done
;	goto L1:
;
;	(ah)	= sectors needed
;	(al)	= 0
;	(bx)	= high byte is zero
;	(cx)	= length of bit map left
;	(es:di) = next available place in the bit map

sfb3:	or	al,al			; set 'Z' in case (cx) == 0

;	Zero must be set here to handle the case where (cx) == 0

sfb4:	cld
	repz	scasb			; scan for a non-zero byte
	jz	sfb15			; none to be had, go return failure
	mov	bl,es:[di-1]		; (bl) = non-zero byte

; new stuff below

	cmp	ah, 4			; (ah) = number of sectors needed
	ja	sfbGetCacheBlocks	; more than 1 cache block required

;	we need up to 1 cache block
;
;	(bh)	= 0
;	(bl)	= bitmap

	xor	dx, dx			; prep bit offset just in case
	and	bl, 0fh			; mask off bits 7-4
	cmp	bl, 0fh			; cache block lsn available?
	jz	sfbGotMyBlock		; yes

	mov	dx, 4			; prep bit offset just in case
	mov	bl, es:[di-1]		; cache block lsn is found

	and	bl, 0f0h		; mask off bits 3-0
	cmp	bl, 0f0h		; cache block lsn available?
	jz	sfbGotMyBlock		; yes
	jcxz	sfb15			; bit map exhausted
	jmp short sfb3			; find next nonzero byte


;	Got our allocation
;
;	(dl)	= number of right contiguous bits
;	(ah)	= requested count
;	(al)	= 0

sfbGotMyBlock:
	dec	di			; (di) = ptr to found byte
	sub	di,word ptr (pbStart)	; (di) = offset to found byte
	shl	di,3			; (di) = # of bits + 8
	add	di,dx			; (di) = bit offset of alloc start
	les	bx,poffusFirstFound	; (es:bx) point to return value
	mov	es:[bx],di		; store beginning offset
	mov	ax,-1			; (ax) = TRUE
	ret

;*	We couldn't find our cache block lsn

sfb15:	xor	ax,ax			; (ax) = FALSE
	ret

sfbGetCacheBlocks:
	cmp	ah, 8			; (ah) = number of sectors needed
	ja	sfbBigAlloc		; more than 2 cache blocks required

;	we need a maximum of 2 cache blocks
;
;	(bh)	= 0
;	(bl)	= bitmap

	xor	dx, dx			; prep bit offset just in case
	cmp	ah, abCont[bx]		; enough contiguous bits?
	jbe	sfbCheckAlign      	; yes, check for alignment
	jcxz	sfb15			; bit map exhausted
	jmp short sfb3			; find next non-zero byte

sfbCheckAlign:
        cmp     bl, 0ffh                ; quick check
        je      sfbGotMyBlock           ; it worked
	and	bl, 0fh			; mask off bits 7-4
	cmp	bl, 0fh			; cache block lsn available?
	mov	bl, es:[di-1]		; get bit map byte back
	je	sfb20			; yes, check if next is available
	jcxz	sfb15			; bit map exhausted
	jmp short sfb25			; check spanning byte

sfb20:
	cmp	ah, abCont[bx]		; enough contiguous bits?
	jbe	sfbGotMyBlock		; yes
	jmp short sfb3			; find next non-zero byte

sfb25:
	and	bl, 0f0h		; mask off bits 3-0
	cmp	bl, 0f0h		; cache block lsn available?
	je	sfb30			; yes
	jmp	sfb3			; no; scan for next non-zero byte
sfb30:
	mov	dx, 0404h		; nibbles = # of right contig bits
	mov	bl, es:[di]		; byte to the right of contig one
	add	dh, abLCont[bx]		; number of spanning contig bits
	cmp	dh, ah			; is number too small?
	jae	sfbGotMy2Blocks		; no, got at least what I needed
	jmp	sfb3			; yes, go scan some more

;	Got our allocation
;
;	(dl)	= number of right contiguous bits
;	(ah)	= requested count
;	(al)	= 0

sfbGotMy2Blocks:
	dec	di			; (di) = ptr to found byte
	sub	di,word ptr (pbStart)	; (di) = offset to found byte
	shl	di,3			; (di) = # of bits + 8
	xor	dh, dh
	add	di,dx			; (di) = bit offset of alloc start
	les	bx,poffusFirstFound	; (es:bx) point to return value
	mov	es:[bx],di		; store beginning offset
	mov	ax,-1			; (ax) = TRUE
	ret

;*	We couldn't find our cache block(s)

sfb50:	xor	ax,ax			; (ax) = FALSE
	ret

;*	More than 8 to allocate.

sfbBigAlloc:
	cmp	ax,12			; are we allocating more than 12?
	ja	sfb200			; yes, go handle big case
	xchg	ah,al			; (ah) = 12 sectors needed, (al) = 0



;*	We want to allocate 12 sectors cache-block bounded.

;
;   L1: scan for non-zero word w/ right-most (high order) bit
;	take "right contig" add to "left contig" of next.  If it's enough,
;		we're done
;	if next != 0xFF, goto L1
;	add left contig of next+1.  If enough, done, else skip one
;	goto L1:
;
;	(ah)	= sectors needed
;	(al)	= 0
;	(bx)	= high byte is zero
;	(es:di) = next available place in the bit map
;	(cx)	= length of bit map left

sfb102: or	al,al			; set 'Z' in case cx = 0

sfb103: cld
	repz	scasb			; scan for a non-zero byte
	jz	sfb50			; none to be had, go return failure

	mov	bl, es:[di-1]		; (bl) = found non-zero byte

	cmp	bl, 0ffh		; are both cache blocks available?
	je	sfbCheckNextByte	; yes
	jcxz	sfb50			; end of allocation bit map space
	jmp short sfbCheckNibble1

sfbCheckNextByte:
	mov	bl, es:[di]		; (bl) = next allocation map byte
	xor     dx, dx	                ; prep bit offset just in case
	and	bl, 0fh			; mask off bits 7-4
	cmp	bl, 0fh			; cache block lsn available?
	je	sfbFound12		; yes, done with scan, di= bit offset
					; to found byte
	jcxz	sfb50			; bit map exhausted
	jmp short sfb102		; scan for next nonzero byte

sfbCheckNibble1:
	and	bl, 0f0h		; mask off bits 3-0
	cmp	bl, 0f0h		; cache block lsn available?
	jne	sfb102			; scan for next nonzero byte
	mov	bl, es:[di]		; (bl) = next allocation map byte
	mov	dx, 4			; prep bit offset just in case
	cmp	bl, 0ffh		; cache block lsn available?
	je	sfbFound12		; yes, done with scan, di= bit offset
					; to found byte
	jcxz	sfb50			; bit map exhausted
	jmp short sfb102		; scan for next nonzero byte

sfbFound12:
	sub	di, word ptr (pbStart)	; (di) = offset to byte found + 1
        dec     di                      ; (di) = offset to byte found
	shl	di, 3			; (di) = # of bits + 8
	add	di, dx			; (di) = bit offset to start of
					; cache block triple we just found
	les	bx,poffusFirstFound	; (es:bx) point to return value
	mov	es:[bx],di		; store beginning offset
	mov	ax,-1			; (ax) = TRUE
	ret


;*	Request is for 16 or more sectors (i.e., 4 or more cache blocks).
;
;	We know that any successful allocation will have 0xFF bytes
;	in it, so we'll scan for one of them, first.
;
;	I = (N-7)/8
;   L1: scan for I 0xFF bytes in string.
;	add right contig of preceding byte to left contig of trailing byte,
;	if OK, done, else
;	skip I bytes
;	goto L1:
;
;	Also note that we don't have a special case check for requests for
;	allocations > a single band.  We'll just compute a large requirement
;	of 0xFFs, scan for the first 0xFF, then blow off at that point.  So
;	we waste that initial scan-for-FF, but in exchange we don't have
;	to slow every call with a check for a request > 8meg, which is
;	uncommon....
;
;	(ax)	= sectors needed
;	(bx)	= 0
;	(cx)	= length of bit map left
;	(es:di) = start of bit map


sfb200:
sfbRealBigAlloc:

;	Compute (N - 7) / 8 as the number of 0xFF bytes we must find
;	Compute number of bits beyond this too

	sub	ax,7
	mov	dx,ax
	and	dx,7			; (dx) = (number of bits - 7) mod 8
	add	dx,7			; (dx) = number of bits beyond 0xFF runs
	shr	ax,3			; (ax) = (number of bits - 7) / 8

	dec	ax
	mov	cFFToScan,ax		; (cFFToScan) = number of FF bytes needed - 1

;	(bx)	= high byte 0
;	(cx)	= bytes remaining in bit map (may be zero)
;	(es:di) = current bit map pointer
;	(dx)	= # of bits needed beyond the 0xFF string

sfb204: or	al,0FFh			; (al) = 0xFF, also clear 'Z'
	repne	scasb			; scan for a 0xFF byte
	jne	sfbRet2			; none found, go return failure

;	we've found an 0xFF byte (es:di-1).  See if we have the others we need

	cmp	cx,cFFToScan		; do we have enough bytes remaining?
	jb	sfbRet2			; no, go return failure
	mov	cbLeftInBitmap,cx	; save # of remaining bytes in bitmap
	mov	oSecondByte,di		; save offset to second byte
	mov	cx,cFFToScan		; (cx) = # of 0xFF bytes to find
	cmp	al,al			; set zero flag
	repe	scasb			; count number of contiguous 0xFF's
	jnz	sfb220			; not enough present, go advance pointers

;	We got our string of 0xFF's.  Count contiguous ajoiners at either end
;	and see if we make our goal.
;
;	(cx)	= 0
;	(dx)	= # of bits needed beyond the 0xFF string
;	(es:di) = offset of byte following string of 0xFF's
;	(oSecondByte) = offset to second byte of string of 0xFF's
;	(cbLeftInBitmap) = remaining bit map count from oSecondByte offset

	mov	bx,cx			; (bx) = 0
	mov	si,oSecondByte		; (es:si) = pointer to second 0xFF
	dec	si			; (es:si) = pointer to first 0xFF string
	cmp	si,word ptr (pbStart)	; are we at the beginning?
	jz	sfb205			; yes, skip byte at head
	mov	bl,es:[si-1]		; (bl) = byte before 0xFF string
sfb205:
	xor	ax, ax			; (ax) = 0
	cmp	bl, 0ffh		; 2 cache blocks available
	jne	sfbChk1			; no
	mov	al, 8			; yes, set ax = 8 sectors
	jmp short sfbCont1

;*	We found an 0xFF byte, but there weren't enough additional
;	0xFF bytes to meet our needs.  We'll restart searching just
;	past that non 0xFF byte
;
;	(bx)	= high byte 0
;	(dx)	= extra bits needed that aren't in our 0xFF string
;	(es:di) = offset of non-FF byte + 1
;	(oSecondByte) = offset to first of string of 0xFF's + 1
;	(cbLeftInBitmap) = remaining bit map count from (TOS) offset

sfb220: mov	si,oSecondByte		; (es:si) = offset of first byte in 0xFF string
	dec	si			; (es:si) point before string. Needed to
	jmp	sfb210


;**	No good - Counldn't get the bits.

sfbRet2:
	xor	ax,ax			; (ax) = FALSE
	ret

sfbChk1:
	and	bl, 0f0h		; mask off bits 7-4
	cmp	bl, 0f0h		; this cache block available?
	jne	sfbCont1		; no
	mov	al, 4			; yes, set bit offset to 4

sfbCont1:
	mov	ah,al			; (ah) = number of right contig bits before string
	mov	cx,cbLeftInBitmap	; (cx) = # of bytes left in bitmap
	cmp	cx,cFFToScan		; is there enough space in bitmap for trailing byte?
	je	sfb206			; no, go ignore trailing byte

	mov	bl,es:[di]		; (bl) = byte after 0xFF string

	cmp	abLCont[bx], 8		; two cache blocks available?
	jne	sfbChk11		; no, check if 1 cache block available
	add	al, 8			; yes, two cache blocks are available
	jmp short sfbCont2

sfbChk11:
	cmp	abLCont[bx], 4		; one cache block available?
	jb	sfbCont2		; no
	add	al, 4			; yes, one cache block is available

sfbCont2:
sfb206: cmp	al,dl			; is there enough bits?
	jae	sfb240			; yes, go return success

;	Major disappointment.  We got our string of 0xFFs, but we couldn't get
;	enuf surrounding bits by adding those in the left-of-string
;	neighbor and those in the right-of-string neighbor (bits must be
;	contig with the 0xFF string, of course).  Don't give up, though... if
;	the right neighbor is 0xFF, we can go right one more and maybe find
;	satisfaction
;
;	(ah)	= bits we'll take from the right part of byte before 0xFF's
;	(bl)	= bitmap byte after string of 0xFFs
;	(es:si) = offset of first byte of 0xFF string
;	(es:di) = offset of first byte following string of 0xFF's
;	(dx)	= extra bits needed that aren't in our 0xFF string
;	(cbLeftInBitmap) = remaining bit map count from (es:si), - 1

	inc	bl			; quick test for bl == 0xFF
	jne	sfb210			; no, bl was not 0xFF, go skip this run
	mov	cx,cbLeftInBitmap	; (cx) = number of bytes left in bitmap
					; starting at second 0xFF byte
	sub	cx,cFFToScan		; (cx) = bytes of map left after 0xFFs
	dec	cx			; quick test for 1 or 2
	jz	sfb210			; no more bytes after most
					; recent 0xFF, go return failure
	mov	bl,es:[di+1]		; (bl) = byte after last 0xFF
	cmp	abLCont[bx], 8		; two cache blocks available?
	jne	sfbChk22		; no, check if 1 cache block available
	add	al, 8			; yes, two cache blocks are available
	jmp short sfbCont3


sfbChk22:
	cmp	abLCont[bx], 4		; one cache block available?
	jb	sfbCont3		; no
	add	al, 4			; yes, one cache block is available

sfbCont3:
	cmp	al,dl			; is there enough bits now?
	jae	sfb240			; yes, go return success

;*	OK, we got a string of 0xFF's of the proper size, but we still didn't
;	make it.  Since we know that this string of ones is bounded on either
;	side by 0 bits, we just skip the whole shebang and start looking
;	again at the byte after the last 0xFF.
;
;	(bx) = high byte 0
;	(dx) = extra bits needed that aren't in our 0xFF string
;	(es:si) = offset of first byte of 0xFF string
;	(es:di) = offset of first byte following string of 0xFF's
;	(cbLeftInBitmap) = remaining bit map count from (es:si), -1

sfb210: mov	cx,cbLeftInBitmap	; (cx) = number of bytes in bitmap from es:si+1
	add	cx,si			; (cx) = offset to end of buffer - 1
	inc	cx			; (cx) = offset to end of buffer
	sub	cx,di			; (cx) = number of bytes in bitmap from es:di
	jmp	sfb204			; go back and scan some more


;**	We got our guy.
;
;	(ah) = bits we'll take from the right part of byte before 0xFF's
;	(bx) = high byte 0
;	(dx) = extra bits needed that aren't in our 0xFF string
;	(si) = offset to first of string of 0xFF's
;	(cbLeftInBitmap) = remaining bit map count from (TOS) offset

sfb240: sub	si,word ptr (pbStart)	; (dx) = start of bit map table
	shl	si,3			; (si) = bit index to start of 0xFF's
	mov	bl,ah			; (bl) = number of right contig bits
	sub	si,bx			; (si) = number of bits
	les	bx,poffusFirstFound	; (es:bx) point to return value location
	mov	es:[bx],si		; store number of bits
	mov	ax,-1			; (ax) = TRUE
	ret

SFBCB	ENDP

end
