home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD1.mdf / magazine / pcmagazi / 1989 / 06 / bsearch.asm next >
Assembly Source File  |  1988-12-05  |  4KB  |  119 lines
  1. ; BSEARCH.ASM --- General purpose binary search routine (MS-DOS version)
  2. ; Copyright (c) 1989 Ziff Communications Co.
  3. ; PC Magazine * Ray Duncan
  4. ;
  5. ; Call with:    BX    = file handle
  6. ;               CX    = record length
  7. ;               DS:DX = record buffer address
  8. ;               SI    = first (left) record number
  9. ;               DI    = last (right) record number
  10. ;               ES:BP = key structure address
  11. ;
  12. ;               where the key structure is:
  13. ;               dw    n          length of key
  14. ;               dw    m          offset of key in record
  15. ;               db    n dup (?)  key value
  16. ;
  17. ; Returns:      if record found
  18. ;               Zero flag = set
  19. ;               AX    = record number
  20. ;
  21. ;               if record not found
  22. ;               Zero flag = clear
  23. ;               AX    = undefined
  24. ;
  25. ;               All other registers preserved
  26.  
  27. _TEXT   segment word public 'CODE'
  28.  
  29.         extrn   strcmp:near
  30.  
  31.         assume  cs:_TEXT
  32.  
  33. kbuff   equ     dword ptr [bp]          ; key address
  34. right   equ     word ptr [bp+4]         ; last record number
  35. left    equ     word ptr [bp+6]         ; first record number
  36. fbuff   equ     dword ptr [bp+8]        ; file buffer address
  37. flen    equ     word ptr [bp+12]        ; file record size
  38. fhandle equ     word ptr [bp+14]        ; file handle
  39.  
  40.         public  bsearch 
  41. bsearch proc    near
  42.  
  43.         cmp     si,di                   ; first > last record?
  44.         jng     bsch1                   ; no, jump
  45.         ret                             ; record absent, end search
  46.  
  47. bsch1:  push    bx                      ; save registers
  48.         push    cx
  49.         push    ds
  50.         push    dx
  51.         push    si
  52.         push    di
  53.         push    es
  54.         push    bp
  55.         mov     bp,sp                   ; point to stack frame
  56.  
  57.         mov     ax,si                   ; calculate record number
  58.         add     ax,di                   ; at middle of file segment             
  59.         shr     ax,1                    ; (left + right) / 2
  60.         push    ax                      ; save record number
  61.  
  62.                                         ; set file pointer...
  63.         mul     cx                      ; set CX:DX = file offset
  64.         mov     cx,ax                   ; (BX already = handle)
  65.         xchg    dx,cx
  66.         mov     ax,4200h                ; fxn. 42 subf. 00H = seek
  67.         int     21h                     ; transfer to MS-DOS
  68.  
  69.                                         ; now read record....
  70.         mov     cx,flen                 ; CX = record length
  71.         lds     dx,fbuff                ; DS:DX = record buffer
  72.         mov     ah,3fh                  ; fxn 3fh = read
  73.         int     21h                     ; transfer to MS-DOS
  74.  
  75.         les     di,kbuff                ; ES:DI = key structure
  76.         mov     si,dx                   ; DS:SI = record buffer
  77.         add     si,es:[di+2]            ; DS:SI = key within record
  78.         mov     bx,es:[di]              ; BX = length of key
  79.         mov     dx,bx                   ; DX = length of key
  80.         add     di,4                    ; ES:DI = address of key
  81.         call    strcmp                  ; now compare keys
  82.  
  83.         pop     ax                      ; recover record number
  84.         jz      bsch4                   ; match found, exit
  85.  
  86.         mov     bx,fhandle              ; set up to bisect file and
  87.         mov     cx,flen                 ; perform recursive search
  88.         mov     si,left
  89.         mov     di,right
  90.         lds     dx,fbuff
  91.         les     bp,kbuff
  92.         jl      bsch2                   ; branch on key comparison
  93.  
  94.         mov     di,ax                   ; record < search key
  95.         dec     di                      ; set right = current - 1
  96.         jmp     bsch3
  97.  
  98. bsch2:  mov     si,ax                   ; record > search key
  99.         inc     si                      ; set left = current + 1
  100.  
  101. bsch3:  call    bsearch                 ; inspect next middle record
  102.  
  103. bsch4:  pop     bp                      ; restore registers     
  104.         pop     es                      ; leaving Z flag undisturbed
  105.         pop     di
  106.         pop     si
  107.         pop     dx
  108.         pop     ds
  109.         pop     cx
  110.         pop     bx
  111.  
  112.         ret                             ; and return to caller
  113.  
  114. bsearch endp
  115.  
  116. _TEXT   ends
  117.  
  118.         end
  119.