home *** CD-ROM | disk | FTP | other *** search
/ Current Shareware 1994 January / SHAR194.ISO / compress / gnuzip_.zip / MATCH.S < prev    next >
Text File  |  1993-03-28  |  8KB  |  258 lines
  1. /* match.s -- optional optimized asm version of longest match in deflate.c
  2.  * Copyright (C) 1992-1993 Jean-loup Gailly
  3.  * This is free software; you can redistribute it and/or modify it under the
  4.  * terms of the GNU General Public License, see the file COPYING.
  5.  */
  6.  
  7. /* $Id: match.S,v 0.8 1993/02/10 16:07:22 jloup Exp $ */
  8.  
  9. #ifdef i386
  10.  
  11. /* This version is for 386 Unix or OS/2 in 32 bit mode.
  12.  * Warning: it uses the AT&T syntax: mov source,dest
  13.  * This file is only optional. If you want to force the C version,
  14.  * add -DNO_ASM to CFLAGS in Makefile and set OBJA to an empty string.
  15.  * If you have reduced WSIZE in gzip.h, then change its value below.
  16.  * This version assumes static allocation of the arrays (-DDYN_ALLOC not used).
  17.  *
  18.  * Preprocess with -DNO_UNDERLINE if your C compiler does not prefix
  19.  * external symbols with an underline character '_'.
  20.  */
  21.  
  22.     .file   "match.s"
  23.  
  24. #ifdef NO_UNDERLINE
  25. #  define _prev             prev
  26. #  define _window           window
  27. #  define _match_start        match_start
  28. #  define _prev_length        prev_length
  29. #  define _good_match        good_match
  30. #  define _nice_match        nice_match
  31. #  define _strstart        strstart
  32. #  define _max_chain_length max_chain_length
  33.  
  34. #  define _match_init       match_init
  35. #  define _longest_match    longest_match
  36. #endif
  37.  
  38. #define MAX_MATCH     258
  39. #define MAX_MATCH2      128     /* MAX_MATCH/2-1 */
  40. #define MIN_MATCH    3
  41. #define WSIZE         32768
  42. #define MAX_DIST     WSIZE - MAX_MATCH - MIN_MATCH - 1
  43.  
  44.     .globl    _match_init
  45.     .globl  _longest_match
  46.  
  47.     .text
  48.  
  49. _match_init:
  50.     ret
  51.  
  52. /*-----------------------------------------------------------------------
  53.  * Set match_start to the longest match starting at the given string and
  54.  * return its length. Matches shorter or equal to prev_length are discarded,
  55.  * in which case the result is equal to prev_length and match_start is
  56.  * garbage.
  57.  * IN assertions: cur_match is the head of the hash chain for the current
  58.  *   string (strstart) and its distance is <= MAX_DIST, and prev_length >= 1
  59.  */
  60.  
  61. _longest_match:    /* int longest_match(cur_match) */
  62.  
  63. #define cur_match   20(%esp)
  64.      /* return address */               /* esp+16 */
  65.         push    %ebp                    /* esp+12 */
  66.         push    %edi                    /* esp+8  */
  67.     push    %esi                    /* esp+4  */
  68.     push    %ebx            /* esp    */
  69.  
  70. /*
  71.  *      match        equ esi
  72.  *      scan         equ edi
  73.  *      chain_length equ ebp
  74.  *      best_len     equ ebx
  75.  *      limit        equ edx
  76.  */
  77.     mov     cur_match,%esi
  78.         mov     _max_chain_length,%ebp /* chain_length = max_chain_length */
  79.     mov     _strstart,%edi
  80.     mov     %edi,%edx
  81.     sub    $ MAX_DIST,%edx        /* limit = strstart-MAX_DIST */
  82.     jae    limit_ok
  83.     sub    %edx,%edx              /* limit = NIL */
  84. limit_ok:
  85.         add    $ _window+2,%edi       /* edi = offset(window+strstart+2) */
  86.         mov    _prev_length,%ebx      /* best_len = prev_length */
  87.         movw     -3(%ebx,%edi),%ax      /* ax = scan[best_len-1..best_len] */
  88.         movw     -2(%edi),%cx           /* cx = scan[0..1] */
  89.     cmp    _good_match,%ebx       /* do we have a good match already? */
  90.         jb      do_scan
  91.     shr     $2,%ebp                /* chain_length >>= 2 */
  92.         jmp     do_scan
  93.  
  94.         .align  4
  95. long_loop:
  96. /* at this point, edi == scan+2, esi == cur_match */
  97.         movw    -3(%ebx,%edi),%ax       /* ax = scan[best_len-1..best_len] */
  98.         movw     -2(%edi),%cx           /* cx = scan[0..1] */
  99. short_loop:
  100. /*
  101.  * at this point, di == scan+2, si == cur_match,
  102.  * ax = scan[best_len-1..best_len] and cx = scan[0..1]
  103.  */
  104.         and     $ WSIZE-1, %esi
  105.         movw    _prev(%esi,%esi),%si    /* cur_match = prev[cur_match] */
  106.                                         /* top word of esi is still 0 */
  107.         cmp     %edx,%esi        /* cur_match <= limit ? */
  108.         jbe     the_end
  109.         dec     %ebp                    /* --chain_length */
  110.         jz      the_end
  111. do_scan:
  112.         cmpw    _window-1(%ebx,%esi),%ax/* check match at best_len-1 */
  113.         jne     short_loop
  114.         cmpw    _window(%esi),%cx       /* check min_match_length match */
  115.         jne     short_loop
  116.  
  117.         lea     _window+2(%esi),%esi    /* si = match */
  118.         mov     %edi,%eax               /* ax = scan+2 */
  119.         mov     $ MAX_MATCH2,%ecx       /* scan for at most MAX_MATCH bytes */
  120.         rep;    cmpsw                   /* loop until mismatch */
  121.         je      maxmatch                /* match of length MAX_MATCH? */
  122. mismatch:
  123.         movb    -2(%edi),%cl        /* mismatch on first or second byte? */
  124.         subb    -2(%esi),%cl        /* cl = 0 if first bytes equal */
  125.         xchg    %edi,%eax           /* edi = scan+2, eax = end of scan */
  126.         sub     %edi,%eax           /* eax = len */
  127.     sub    %eax,%esi           /* esi = cur_match + 2 + offset(window) */
  128.     sub    $ _window+2,%esi    /* esi = cur_match */
  129.         subb    $1,%cl              /* set carry if cl == 0 (cannot use DEC) */
  130.         adc     $0,%eax             /* eax = carry ? len+1 : len */
  131.         cmp     %ebx,%eax           /* len > best_len ? */
  132.         jle     long_loop
  133.         mov     %esi,_match_start       /* match_start = cur_match */
  134.         mov     %eax,%ebx               /* ebx = best_len = len */
  135.         cmp     _nice_match,%eax        /* len >= nice_match ? */
  136.         jl      long_loop
  137. the_end:
  138.         mov     %ebx,%eax               /* result = eax = best_len */
  139.     pop     %ebx
  140.         pop     %esi
  141.         pop     %edi
  142.         pop     %ebp
  143.         ret
  144. maxmatch:
  145.         cmpsb
  146.         jmp     mismatch
  147.  
  148. #else
  149. #if 0 /* not yet tested */
  150.  
  151. /* 68020 version, written by Francesco Potorti <pot@fly.cnuce.cnr.it> */
  152.  
  153. #define MAX_MATCH     0x102
  154. #define MIN_MATCH    3
  155. #define WSIZE         0x8000
  156. #define MAX_DIST     (WSIZE - MAX_MATCH - MIN_MATCH - 1)
  157.  
  158.     file    "match.S"
  159.  
  160.     global    match_init
  161.     global    longest_match
  162.  
  163.     text
  164.  
  165. match_init:
  166.     rts
  167.  
  168. /*-----------------------------------------------------------------------
  169.  * Set match_start to the longest match starting at the given string and
  170.  * return its length. Matches shorter or equal to prev_length are discarded,
  171.  * in which case the result is equal to prev_length and match_start is
  172.  * garbage.
  173.  * IN assertions: cur_match is the head of the hash chain for the current
  174.  *   string (strstart) and its distance is <= MAX_DIST, and prev_length >= 1
  175.  */
  176.  
  177. /* int longest_match (cur_match) */
  178.  
  179. #define    best_len    d0        /* unsigned */
  180. #define    cur_match    d1        /* Ipos */
  181. #define    tmp        d2        /* int */
  182. #define    scan_start    d3        /* unsigned */
  183. #define    scan_end    d4        /* unsigned */
  184. #define    limit        d5        /* IPos */
  185. #define    chain_length    d6        /* unsigned */
  186. #define    scan        a0        /* *uch */
  187. #define    match        a1        /* *uch */
  188. #define prev_address    a2        /* *Pos */
  189. #define    scan_init    a3        /* *uch */
  190. #define    match_init    a4        /* *uch */
  191. set    pushreg,0x3e38
  192. set    popreg,0x1c7c
  193.  
  194.  
  195. longest_match:
  196.     mov.l    0x4(%sp),%cur_match
  197.     movm.l    &pushreg,-(%sp)
  198.     mov.l    max_chain_length,%chain_length
  199.     mov.l    prev_length,%best_len
  200.     move.l    &prev,%prev_address
  201.     move.l    &(window+MIN_MATCH),%match_init
  202.     mov.l    strstart,%limit
  203.     mov.l    %match_init,%scan_init
  204.     add.l    %limit,%scan_init
  205.     sub.l    &MAX_DIST,%limit
  206.     bhi.b    limit_ok
  207.     clr.l    %limit
  208. limit_ok:
  209.     mov.l    good_match,%tmp
  210.     cmp.l    %tmp,prev_length
  211.     bhi.b    length_ok
  212.     lsr.l    &2,%chain_length
  213. length_ok:
  214.     sub.l    &1,%chain_length
  215.     move.w    -MIN_MATCH(%scan_init),%scan_start
  216.     move.w    -MIN_MATCH-1(%scan_init,%best_len.l),%scan_end
  217.     bra.b    do_scan
  218.  
  219. long_loop:
  220.     move.w    -MIN_MATCH-1(%scan_init,%best_len.l),%scan_end
  221.  
  222. short_loop:
  223.     lsl.w    &1,%cur_match
  224.     mov.w    (%prev_address,%cur_match.l),%cur_match
  225.     cmp.w    %cur_match,%limit
  226.     dbls    %chain_length,do_scan
  227.     bra.b    return
  228.  
  229. do_scan:
  230.     move.l    %match_init,%match
  231.     add.l    %cur_match,%match
  232.     cmp.w    %scan_end,-MIN_MATCH-1(%match,%best_len.l)
  233.     bne    short_loop
  234.     cmp.w    %scan_start,-MIN_MATCH(%match)
  235.     bne    short_loop
  236.  
  237.     move.w    &(MAX_MATCH-MIN_MATCH+1)-1,%tmp
  238.     move.l    %scan_init,%scan
  239. scan_loop:
  240.     cmp.b    (%match)+,(%scan)+
  241.     dbne    %tmp,scan_loop
  242.  
  243.     sub.l    %scan_init,%scan
  244.     add.l    &MIN_MATCH-1,%scan
  245.     cmp.l    %scan,%best_len
  246.     bls    short_loop
  247.     mov.l    %scan,%best_len
  248.     mov.l    %cur_match,match_start
  249.     cmp.l    %best_len,nice_match
  250.     blo    long_loop
  251. return:
  252.     movm.l    (%sp)+,&popreg
  253.     rts
  254. #else
  255.  error: this asm version is for 386 or 68020 only
  256. #endif
  257. #endif
  258.