home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 9 Archive / 09-Archive.zip / zip21.zip / msdos / match.asm < prev    next >
Assembly Source File  |  1996-04-01  |  14KB  |  446 lines

  1. ;
  2. ; Copyright (C) 1990-1996 Mark Adler, Richard B. Wales, and Jean-loup Gailly.
  3. ; Permission is granted to any individual or institution to use, copy, or
  4. ; redistribute this software so long as all of the original files are included,
  5. ; that it is not sold for profit, and that this copyright notice is retained.
  6. ;
  7. ; match.asm by Jean-loup Gailly.
  8.  
  9. ; match.asm, optimized version of longest_match() in deflate.c
  10. ; Must be assembled with masm -ml. To be used only with C compact model
  11. ; or large model. (For large model, assemble with -D__LARGE__).
  12. ; This file is only optional. If you don't have masm or tasm, use the
  13. ; C version (add -DNO_ASM to CFLAGS in makefile.msc and remove match.obj
  14. ; from OBJI). If you have reduced WSIZE in zip.h, then make sure this is
  15. ; assembled with an equivalent -DWSIZE=<whatever>.
  16. ;
  17. ; The code has been prepared for two different C compiler calling conventions
  18. ; and contains some support for dynamically allocated working space.
  19. ; The different environments are selected by two conditional flags:
  20. ;   DYN_ALLOC  : select support for malloc'ed working space
  21. ;   SS_NEQ_DS  : relaxes assumption that stack and default data segments
  22. ;                are identical
  23. ; When SS_NEQ_DS is defined, the code segment is used to store some
  24. ; local variables. This (bad) coding practice is very likely to break any
  25. ; `segment protection scheme', it will most probably only work for real
  26. ; mode programs.
  27. ;
  28. ; Turbo C 2.0 does not support static allocation of more than 64K bytes per
  29. ; file, and does not have SS == DS. So TC and BC++ users must use:
  30. ;   tasm -ml -DDYN_ALLOC -DSS_NEQ_DS match;
  31. ;
  32. ; To simplify the code, the option -DDYN_ALLOC is supported for OS/2
  33. ; only if the arrays are guaranteed to have zero offset (allocated by
  34. ; halloc). We also require SS==DS. This is satisfied for MSC but not Turbo C.
  35. ;
  36. ; Per default, test code is included to check if the above requirements are
  37. ; fulfilled. This test code can be disabled by defining the compile time
  38. ; option flag NO_SECURE_TESTS when compiling for a production executable.
  39. ; This shortens the code size (but the performance gain is neglectable).
  40. ; The security tests should remain enabled, when a new C compiler
  41. ; and/or a new set of compilation options is tried.
  42.  
  43.         name    match
  44.  
  45. ifdef     DEBUG
  46.   VERBOSE_INFO EQU 1
  47. else
  48.   ifdef _AS_MSG_
  49.     VERBOSE_INFO EQU 1
  50.   else
  51.     VERBOSE_INFO EQU 0
  52.   endif
  53. endif
  54.  
  55. ifndef __SMALL__
  56.   ifndef __COMPACT__
  57.     ifndef __MEDIUM__
  58.       ifndef __LARGE__
  59.         ifndef __HUGE__
  60. ;         __SMALL__ EQU 1
  61.         endif
  62.       endif
  63.     endif
  64.   endif
  65. endif
  66.  
  67. ifdef __HUGE__
  68. ; .MODEL Huge
  69.    @CodeSize  EQU 1
  70.    @DataSize  EQU 1
  71.    Save_DS    EQU 1
  72.    if VERBOSE_INFO
  73.     if1
  74.       %out Assembling for C, Huge memory model
  75.     endif
  76.    endif
  77. else
  78.    ifdef __LARGE__
  79. ;      .MODEL Large
  80.       @CodeSize  EQU 1
  81.       @DataSize  EQU 1
  82.       if VERBOSE_INFO
  83.        if1
  84.          %out Assembling for C, Large memory model
  85.        endif
  86.       endif
  87.    else
  88.       ifdef __COMPACT__
  89. ;         .MODEL Compact
  90.          @CodeSize  EQU 0
  91.          @DataSize  EQU 1
  92.          if VERBOSE_INFO
  93.           if1
  94.             %out Assembling for C, Compact memory model
  95.           endif
  96.          endif
  97.       else
  98.          ifdef __MEDIUM__
  99. ;            .MODEL Medium
  100.             @CodeSize  EQU 1
  101.             @DataSize  EQU 0
  102.             if VERBOSE_INFO
  103.              if1
  104.                %out Assembling for C, Medium memory model
  105.              endif
  106.             endif
  107.          else
  108. ;            .MODEL Small
  109.             @CodeSize  EQU 0
  110.             @DataSize  EQU 0
  111.             if VERBOSE_INFO
  112.              if1
  113.                %out Assembling for C, Small memory model
  114.              endif
  115.             endif
  116.          endif
  117.       endif
  118.    endif
  119. endif
  120.  
  121. if @CodeSize
  122.         LCOD_OFS        EQU     2
  123. else
  124.         LCOD_OFS        EQU     0
  125. endif
  126.  
  127. IF @DataSize
  128.         LDAT_OFS        EQU     2
  129. else
  130.         LDAT_OFS        EQU     0
  131. endif
  132.  
  133. ifdef Save_DS
  134. ;                       (di,si,ds)+(size, return address)
  135.         SAVE_REGS       EQU     6+(4+LCOD_OFS)
  136. else
  137. ;                       (di,si)+(size, return address)
  138.         SAVE_REGS       EQU     4+(4+LCOD_OFS)
  139. endif
  140.  
  141. ;
  142. ; Selection of the supported CPU instruction set and initialization
  143. ; of CPU type related macros:
  144. ;
  145. ifdef __586
  146.         Use_286_code    EQU     1
  147.         Align_Size      EQU     16      ; paragraph alignment on Pentium
  148.         Alig_PARA       EQU     1       ; paragraph aligned code segment
  149. else
  150. ifdef __486
  151.         Use_286_code    EQU     1
  152.         Align_Size      EQU     4       ; dword alignment on 32 bit processors
  153.         Alig_PARA       EQU     1       ; paragraph aligned code segment
  154. else
  155. ifdef __386
  156.         Use_286_code    EQU     1
  157.         Align_Size      EQU     4       ; dword alignment on 32 bit processors
  158.         Alig_PARA       EQU     1       ; paragraph aligned code segment
  159. else
  160. ifdef __286
  161.         Use_286_code    EQU     1
  162.         Align_Size      EQU     2       ; word alignment on 16 bit processors
  163.         Alig_PARA       EQU     0       ; word aligned code segment
  164. else
  165. ifdef __186
  166.         Use_186_code    EQU     1
  167.         Align_Size      EQU     2       ; word alignment on 16 bit processors
  168.         Alig_PARA       EQU     0       ; word aligned code segment
  169. else
  170.         Align_Size      EQU     2       ; word alignment on 16 bit processors
  171.         Alig_PARA       EQU     0       ; word aligned code segment
  172. endif   ;?__186
  173. endif   ;?__286
  174. endif   ;?__386
  175. endif   ;?__486
  176. endif   ;?__586
  177.  
  178. ifdef Use_286_code
  179.         .286
  180.         Have_80x86      EQU     1
  181. else
  182. ifdef Use_186_code
  183.         .186
  184.         Have_80x86      EQU     1
  185. else
  186.         .8086
  187.         Have_80x86      EQU     0
  188. endif   ;?Use_186_code
  189. endif   ;?Use_286_code
  190.  
  191. ifndef DYN_ALLOC
  192.         extrn   _prev         : word
  193.         extrn   _window       : byte
  194.         prev    equ  _prev    ; offset part
  195.         window  equ  _window
  196. endif
  197.  
  198. _DATA    segment  word public 'DATA'
  199.         extrn   _nice_match   : word
  200.         extrn   _match_start  : word
  201.         extrn   _prev_length  : word
  202.         extrn   _good_match   : word
  203.         extrn   _strstart     : word
  204.         extrn   _max_chain_length : word
  205. ifdef DYN_ALLOC
  206.         extrn   _prev         : word
  207.         extrn   _window       : word
  208.         prev    equ 0         ; offset forced to zero
  209.         window  equ 0
  210.         window_seg equ _window[2]
  211.         window_off equ 0
  212. else
  213.         wseg    dw seg _window
  214.         window_seg equ wseg
  215.         window_off equ offset _window
  216. endif
  217. _DATA    ends
  218.  
  219. DGROUP  group _DATA
  220.  
  221. if @CodeSize
  222. if Alig_PARA
  223. MATCH_TEXT      SEGMENT  PARA PUBLIC 'CODE'
  224. else
  225. MATCH_TEXT      SEGMENT  WORD PUBLIC 'CODE'
  226. endif
  227.         assume  cs: MATCH_TEXT, ds: DGROUP
  228. else    ;!@CodeSize
  229. if Alig_PARA
  230. _TEXT   segment para public 'CODE'
  231. else
  232. _TEXT   segment word public 'CODE'
  233. endif
  234.         assume  cs: _TEXT, ds: DGROUP
  235. endif   ;?@CodeSize
  236.  
  237.         public  _match_init
  238.         public  _longest_match
  239.  
  240. ifndef      WSIZE
  241.         WSIZE         equ 32768         ; keep in sync with zip.h !
  242. endif
  243.         MIN_MATCH     equ 3
  244.         MAX_MATCH     equ 258
  245.         MIN_LOOKAHEAD equ (MAX_MATCH+MIN_MATCH+1)
  246.         MAX_DIST      equ (WSIZE-MIN_LOOKAHEAD)
  247.  
  248. ifdef DYN_ALLOC
  249.   ifdef SS_NEQ_DS
  250.     prev_ptr    dw  seg _prev           ; pointer to the prev array
  251.   endif
  252. else
  253.     prev_ptr    dw  seg _prev           ; pointer to the prev array
  254. endif
  255. ifdef SS_NEQ_DS
  256.     match_start dw  0                   ; copy of _match_start if SS != DS
  257.     nice_match  dw  0                   ; copy of _nice_match  if SS != DS
  258. endif
  259.  
  260. ; initialize or check the variables used in match.asm.
  261.  
  262. if @CodeSize
  263. _match_init proc far                    ; 'proc far' for large model
  264. else
  265. _match_init proc near                   ; 'proc near' for compact model
  266. endif
  267. ifdef SS_NEQ_DS
  268.         ma_start equ cs:match_start     ; does not work on OS/2
  269.         nice     equ cs:nice_match
  270.         mov     ax,_nice_match
  271.         mov     cs:nice_match,ax        ; ugly write to code, crash on OS/2
  272. else
  273.         assume ss: DGROUP
  274.         ma_start equ ss:_match_start
  275.         nice     equ ss:_nice_match
  276.   ifndef NO_SECURE_TESTS
  277.         mov     ax,ds
  278.         mov     bx,ss
  279.         cmp     ax,bx                   ; SS == DS?
  280.         jne     fatal_err
  281.   endif
  282. endif
  283. ifdef DYN_ALLOC
  284.   ifndef NO_SECURE_TESTS
  285.         cmp     _prev[0],0              ; verify zero offset
  286.         jne     fatal_err
  287.         cmp     _window[0],0
  288.         jne     fatal_err
  289.   endif
  290.   ifdef SS_NEQ_DS
  291.         mov     ax,_prev[2]             ; segment value
  292.         mov     cs:prev_ptr,ax          ; ugly write to code, crash on OS/2
  293.         prev_seg  equ cs:prev_ptr
  294.   else
  295.         prev_seg  equ ss:_prev[2]       ; works on OS/2 if SS == DS
  296.   endif
  297. else
  298.         prev_seg  equ cs:prev_ptr
  299. endif
  300.         ret
  301. ifndef NO_SECURE_TESTS
  302. if @CodeSize
  303.         extrn   _exit : far             ; 'far' for large model
  304. else
  305.         extrn   _exit : near            ; 'near' for compact model
  306. endif
  307. fatal_err:                              ; (quiet) emergency stop:
  308.         call    _exit                   ; incompatible "global vars interface"
  309. endif
  310.  
  311. _match_init endp
  312.  
  313. ; -----------------------------------------------------------------------
  314. ; Set match_start to the longest match starting at the given string and
  315. ; return its length. Matches shorter or equal to prev_length are discarded,
  316. ; in which case the result is equal to prev_length and match_start is
  317. ; garbage.
  318. ; IN assertions: cur_match is the head of the hash chain for the current
  319. ;   string (strstart) and its distance is <= MAX_DIST, and prev_length >= 1
  320.  
  321. ; int longest_match(cur_match)
  322.  
  323.         align   Align_Size
  324.  
  325. if @CodeSize
  326. _longest_match  proc far                 ; 'proc far' for large model
  327. else
  328. _longest_match  proc near                ; 'proc near' for compact model
  329. endif
  330.         push    bp
  331.         mov     bp,sp
  332.         push    di
  333.         push    si
  334.         push    ds
  335.  
  336. if @CodeSize
  337.         cur_match    equ word ptr [bp+6] ; [bp+6] for large model
  338. else
  339.         cur_match    equ word ptr [bp+4] ; [bp+4] for compact model
  340. endif
  341.  
  342. ;       window       equ es:window (es:0 for DYN_ALLOC)
  343. ;       prev         equ ds:prev
  344. ;       match        equ es:si
  345. ;       scan         equ es:di
  346. ;       chain_length equ bp
  347. ;       best_len     equ bx
  348. ;       limit        equ dx
  349.  
  350.         mov     si,cur_match            ; use bp before it is destroyed
  351.         mov     dx,_strstart
  352.         mov     bp,_max_chain_length    ; chain_length = max_chain_length
  353.         mov     di,dx
  354.         sub     dx,MAX_DIST             ; limit = strstart-MAX_DIST
  355.         cld                             ; string ops increment si and di
  356.         jae     limit_ok
  357.         sub     dx,dx                   ; limit = NIL
  358. limit_ok:
  359.         add     di,2+window_off         ; di = offset(window + strstart + 2)
  360.         mov     bx,_prev_length         ; best_len = prev_length
  361.         mov     es,window_seg
  362.         mov     ax,es:[bx+di-3]         ; ax = scan[best_len-1..best_len]
  363.         mov     cx,es:[di-2]            ; cx = scan[0..1]
  364.         cmp     bx,_good_match          ; do we have a good match already?
  365.         mov     ds,prev_seg             ; (does not destroy the flags)
  366.         assume  ds: nothing
  367.         jb      do_scan                 ; good match?
  368. if Have_80x86
  369.         shr     bp,2                    ; chain_length >>= 2
  370. else
  371.         shr     bp,1                    ; chain_length >>= 2
  372.         shr     bp,1
  373. endif
  374.         jmp     short do_scan
  375.  
  376.         align   Align_Size              ; align destination of branch
  377. long_loop:
  378. ; at this point, ds:di == scan+2, ds:si == cur_match
  379.         mov     ax,[bx+di-3]            ; ax = scan[best_len-1..best_len]
  380.         mov     cx,[di-2]               ; cx = scan[0..1]
  381.         mov     ds,prev_seg             ; reset ds to address the prev array
  382. short_loop:
  383. ; at this point, di == scan+2, si = cur_match,
  384. ; ax = scan[best_len-1..best_len] and cx = scan[0..1]
  385. if (WSIZE-32768)
  386.         and     si,WSIZE-1              ; not needed if WSIZE=32768
  387. endif
  388.         shl     si,1                    ; cur_match as word index
  389.         dec     bp                      ; --chain_length
  390.         mov     si,prev[si]             ; cur_match = prev[cur_match]
  391.         jz      the_end
  392.         cmp     si,dx                   ; cur_match <= limit ?
  393.         jbe     the_end
  394. do_scan:
  395.         cmp     ax,word ptr es:window[bx+si-1] ; check match at best_len-1
  396.         jne     short_loop
  397.         cmp     cx,word ptr es:window[si]      ; check min_match_length match
  398.         jne     short_loop
  399.  
  400.         mov     cx,es
  401.         add     si,2+window_off         ; si = match
  402.         mov     ds,cx                   ; ds = es = window
  403.         mov     cx,(MAX_MATCH-2)/2      ; scan for at most MAX_MATCH bytes
  404.         mov     ax,di                   ; ax = scan+2
  405.         repe    cmpsw                   ; loop until mismatch
  406.         je      maxmatch                ; match of length MAX_MATCH?
  407. mismatch:
  408.         mov     cl,[di-2]               ; mismatch on first or second byte?
  409.         xchg    ax,di                   ; di = scan+2, ax = end of scan
  410.         sub     cl,[si-2]               ; cl = 0 if first bytes equal
  411.         sub     ax,di                   ; ax = len
  412.         sub     si,2+window_off         ; si = cur_match + len
  413.         sub     si,ax                   ; si = cur_match
  414.         sub     cl,1                    ; set carry if cl == 0 (can't use DEC)
  415.         adc     ax,0                    ; ax = carry ? len+1 : len
  416.         cmp     ax,bx                   ; len > best_len ?
  417.         jle     long_loop
  418.         mov     ma_start,si             ; match_start = cur_match
  419.         mov     bx,ax                   ; bx = best_len = len
  420.         cmp     ax,nice                 ; len >= nice_match ?
  421.         jl      long_loop
  422. the_end:
  423.         pop     ds
  424.         assume  ds: DGROUP
  425. ifdef SS_NEQ_DS
  426.         mov     ax,ma_start             ; garbage if no match found
  427.         mov     ds:_match_start,ax
  428. endif
  429.         pop     si
  430.         pop     di
  431.         pop     bp
  432.         mov     ax,bx                   ; result = ax = best_len
  433.         ret
  434. maxmatch:                               ; come here if maximum match
  435.         cmpsb                           ; increment si and di
  436.         jmp     mismatch                ; force match_length = MAX_LENGTH
  437.  
  438. _longest_match  endp
  439.  
  440. if @CodeSize
  441. MATCH_TEXT      ENDS
  442. else
  443. _TEXT   ENDS
  444. endif
  445. end
  446.