home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 9 Archive / 09-Archive.zip / zip21.zip / match.S < prev    next >
Text File  |  1996-04-01  |  14KB  |  393 lines
  1. /*
  2.  * Copyright (C) 1990-1996 Mark Adler, Richard B. Wales, Jean-loup Gailly,
  3.  * Kai Uwe Rommel, Onno van der Linden and Igor Mandrichenko.
  4.  * Permission is granted to any individual or institution to use, copy, or
  5.  * redistribute this software so long as all of the original files are
  6.  * included, that it is not sold for profit, and that this copyright notice is
  7.  * retained.
  8.  *
  9.  * match.s by Jean-loup Gailly. Translated to 32 bit code by Kai Uwe Rommel.
  10.  * The 68020 version has been written by Francesco Potorti` <pot@cnuce.cnr.it>
  11.  * with adaptations by Carsten Steger <stegerc@informatik.tu-muenchen.de>,
  12.  * Andreas Schwab <schwab@lamothe.informatik.uni-dortmund.de> and
  13.  * Kristoffer Eriksson <ske@pkmab.se>
  14.  */
  15.  
  16. /* Preprocess with -DNO_UNDERLINE if your C compiler does not prefix
  17.  * external symbols with an underline character '_'.
  18.  */
  19. #if defined(NO_UNDERLINE) || defined(__ELF__)
  20. #  define _prev             prev
  21. #  define _window           window
  22. #  define _match_start      match_start
  23. #  define _prev_length      prev_length
  24. #  define _good_match       good_match
  25. #  define _nice_match       nice_match
  26. #  define _strstart         strstart
  27. #  define _max_chain_length max_chain_length
  28.  
  29. #  define _match_init       match_init
  30. #  define _longest_match    longest_match
  31. #endif
  32.  
  33. #ifdef DYN_ALLOC
  34.   error: DYN_ALLOC not yet supported in match.s
  35. #endif
  36.  
  37. /* Use 16-bytes alignment if your assembler supports it. Warning: gas
  38.  * uses a log(x) parameter (.align 4 means 16-bytes alignment). On SVR4
  39.  * the parameter is a number of bytes.
  40.  */
  41. #ifndef ALIGNMENT
  42. #  define ALIGNMENT 4
  43. #endif
  44.  
  45.  
  46. #ifndef WSIZE
  47. # define WSIZE          32768
  48. #endif
  49. #define MIN_MATCH       3
  50. #define MAX_MATCH       258
  51. #define MIN_LOOKAHEAD   (MAX_MATCH + MIN_MATCH + 1)
  52. #define MAX_DIST        (WSIZE - MIN_LOOKAHEAD)
  53.  
  54. #if defined(i386) || defined(_I386) || defined(_i386) || defined(__i386)
  55.  
  56. /* This version is for 386 Unix or OS/2 in 32 bit mode.
  57.  * Warning: it uses the AT&T syntax: mov source,dest
  58.  * This file is only optional. If you want to force the C version,
  59.  * add -DNO_ASM to CFLAGS in Makefile and set OBJA to an empty string.
  60.  * If you have reduced WSIZE in (g)zip.h, then make sure this is
  61.  * assembled with an equivalent -DWSIZE=<whatever>.
  62.  * This version assumes static allocation of the arrays (-DDYN_ALLOC not used).
  63.  */
  64.  
  65.         .file   "match.S"
  66.  
  67.         .globl  _match_init
  68.         .globl  _longest_match
  69.  
  70.         .text
  71.  
  72. _match_init:
  73.         ret
  74.  
  75. /*-----------------------------------------------------------------------
  76.  * Set match_start to the longest match starting at the given string and
  77.  * return its length. Matches shorter or equal to prev_length are discarded,
  78.  * in which case the result is equal to prev_length and match_start is
  79.  * garbage.
  80.  * IN assertions: cur_match is the head of the hash chain for the current
  81.  *   string (strstart) and its distance is <= MAX_DIST, and prev_length >= 1
  82.  */
  83.  
  84.         .align  ALIGNMENT
  85.  
  86. _longest_match: /* int longest_match(cur_match) */
  87.  
  88. #define cur_match   20(%esp)
  89.      /* return address */               /* esp+16 */
  90.         push    %ebp                    /* esp+12 */
  91.         push    %edi                    /* esp+8  */
  92.         push    %esi                    /* esp+4  */
  93.         push    %ebx                    /* esp    */
  94.  
  95. /*
  96.  *      match        equ esi
  97.  *      scan         equ edi
  98.  *      chain_length equ ebp
  99.  *      best_len     equ ebx
  100.  *      limit        equ edx
  101.  */
  102.         mov     cur_match,%esi
  103.         mov     _strstart,%edx
  104.         mov     _max_chain_length,%ebp /* chain_length = max_chain_length */
  105.         mov     %edx,%edi
  106.         sub     $(MAX_DIST),%edx       /* limit = strstart-MAX_DIST */
  107.         cld                            /* string ops increment si and di */
  108.         jae     limit_ok
  109.         sub     %edx,%edx              /* limit = NIL */
  110. limit_ok:
  111.         add     $2+_window,%edi        /* edi = offset(window+strstart+2) */
  112.         mov     _prev_length,%ebx      /* best_len = prev_length */
  113.         movw    -2(%edi),%cx           /* cx = scan[0..1] */
  114.         movw    -3(%ebx,%edi),%ax      /* ax = scan[best_len-1..best_len] */
  115.         cmp     _good_match,%ebx       /* do we have a good match already? */
  116.         jb      do_scan
  117.         shr     $2,%ebp                /* chain_length >>= 2 */
  118.         jmp     do_scan
  119.  
  120.         .align  ALIGNMENT
  121. long_loop:
  122. /* at this point, edi == scan+2, esi == cur_match */
  123.         movw    -3(%ebx,%edi),%ax       /* ax = scan[best_len-1..best_len] */
  124.         movw     -2(%edi),%cx           /* cx = scan[0..1] */
  125. short_loop:
  126. /*
  127.  * at this point, di == scan+2, si == cur_match,
  128.  * ax = scan[best_len-1..best_len] and cx = scan[0..1]
  129.  */
  130.         and     $(WSIZE-1), %esi
  131.         dec     %ebp                    /* --chain_length */
  132.         movw    _prev(,%esi,2),%si      /* cur_match = prev[cur_match] */
  133.                                         /* top word of esi is still 0 */
  134.         jz      the_end
  135.         cmp     %edx,%esi               /* cur_match <= limit ? */
  136.         jbe     the_end
  137. do_scan:
  138.         cmpw    _window-1(%ebx,%esi),%ax/* check match at best_len-1 */
  139.         jne     short_loop
  140.         cmpw    _window(%esi),%cx       /* check min_match_length match */
  141.         jne     short_loop
  142.  
  143.         add     $2+_window,%esi         /* si = match */
  144.         mov     $(MAX_MATCH/2-1),%ecx   /* scan for at most MAX_MATCH bytes */
  145.         mov     %edi,%eax               /* ax = scan+2 */
  146.         rep;    cmpsw                   /* loop until mismatch */
  147.         je      maxmatch                /* match of length MAX_MATCH? */
  148. mismatch:
  149.         movb    -2(%edi),%cl        /* mismatch on first or second byte? */
  150.         xchg    %edi,%eax           /* edi = scan+2, eax = end of scan */
  151.         subb    -2(%esi),%cl        /* cl = 0 if first bytes equal */
  152.         sub     %edi,%eax           /* eax = len */
  153.         sub     $2+_window,%esi     /* esi = cur_match + len */
  154.         sub     %eax,%esi           /* esi = cur_match */
  155.         subb    $1,%cl              /* set carry if cl == 0 (cannot use DEC) */
  156.         adc     $0,%eax             /* eax = carry ? len+1 : len */
  157.         cmp     %ebx,%eax           /* len > best_len ? */
  158.         jle     long_loop
  159.         mov     %esi,_match_start       /* match_start = cur_match */
  160.         mov     %eax,%ebx               /* ebx = best_len = len */
  161.         cmp     _nice_match,%eax        /* len >= nice_match ? */
  162.         jl      long_loop
  163. the_end:
  164.         mov     %ebx,%eax               /* result = eax = best_len */
  165.         pop     %ebx
  166.         pop     %esi
  167.         pop     %edi
  168.         pop     %ebp
  169.         ret
  170.         .align  ALIGNMENT
  171. maxmatch:
  172.         cmpsb
  173.         jmp     mismatch
  174.  
  175. #else /* !(i386 || _I386 || _i386 || __i386) */
  176.  
  177. /* ======================== 680x0 version ================================= */
  178.  
  179. #if defined(m68k)||defined(mc68k)||defined(__mc68000__)||defined(__MC68000__)
  180. #  ifndef mc68000
  181. #    define mc68000
  182. #  endif
  183. #endif
  184.  
  185. #if defined(__mc68020__) || defined(__MC68020__) || defined(sysV68)
  186. #  ifndef mc68020
  187. #    define mc68020
  188. #  endif
  189. #endif
  190.  
  191. #if defined(mc68020) || defined(mc68000)
  192.  
  193. #if (defined(mc68020) || defined(NeXT)) && !defined(UNALIGNED_OK)
  194. #  define UNALIGNED_OK
  195. #endif
  196.  
  197. #ifdef sysV68  /* Try Motorola Delta style */
  198.  
  199. #  define GLOBAL(symbol)        global  symbol
  200. #  define TEXT                  text
  201. #  define FILE(filename)        file    filename
  202. #  define invert_maybe(src,dst) dst,src
  203. #  define imm(data)             &data
  204. #  define reg(register)         %register
  205.  
  206. #  define addl                  add.l
  207. #  define addql                 addq.l
  208. #  define blos                  blo.b
  209. #  define bhis                  bhi.b
  210. #  define bras                  bra.b
  211. #  define clrl                  clr.l
  212. #  define cmpmb                 cmpm.b
  213. #  define cmpw                  cmp.w
  214. #  define cmpl                  cmp.l
  215. #  define lslw                  lsl.w
  216. #  define lsrl                  lsr.l
  217. #  define movel                 move.l
  218. #  define movew                 move.w
  219. #  define moveb                 move.b
  220. #  define moveml                movem.l
  221. #  define subl                  sub.l
  222. #  define subw                  sub.w
  223. #  define subql                 subq.l
  224.  
  225. #  define IndBase(bd,An)        (bd,An)
  226. #  define IndBaseNdxl(bd,An,Xn) (bd,An,Xn.l)
  227. #  define IndBaseNdxw(bd,An,Xn) (bd,An,Xn.w)
  228. #  define predec(An)            -(An)
  229. #  define postinc(An)           (An)+
  230.  
  231. #else /* default style (Sun 3, NeXT, Amiga, Atari) */
  232.  
  233. #  define GLOBAL(symbol)        .globl  symbol
  234. #  define TEXT                  .text
  235. #  define FILE(filename)        .even
  236. #  define invert_maybe(src,dst) src,dst
  237. #  if defined(sun) || defined(mc68k)
  238. #    define imm(data)           #data
  239. #  else
  240. #    define imm(data)           \#data
  241. #  endif
  242. #  define reg(register)         register
  243.  
  244. #  define blos                  bcss
  245. #  if defined(sun) || defined(mc68k)
  246. #    define movel               movl
  247. #    define movew               movw
  248. #    define moveb               movb
  249. #  endif
  250. #  define IndBase(bd,An)        An@(bd)
  251. #  define IndBaseNdxl(bd,An,Xn) An@(bd,Xn:l)
  252. #  define IndBaseNdxw(bd,An,Xn) An@(bd,Xn:w)
  253. #  define predec(An)            An@-
  254. #  define postinc(An)           An@+
  255.  
  256. #endif  /* styles */
  257.  
  258. #define Best_Len        reg(d0)         /* unsigned */
  259. #define Cur_Match       reg(d1)         /* Ipos */
  260. #define Loop_Counter    reg(d2)         /* int */
  261. #define Scan_Start      reg(d3)         /* unsigned short */
  262. #define Scan_End        reg(d4)         /* unsigned short */
  263. #define Limit           reg(d5)         /* IPos */
  264. #define Chain_Length    reg(d6)         /* unsigned */
  265. #define Scan_Test       reg(d7)
  266. #define Scan            reg(a0)         /* *uch */
  267. #define Match           reg(a1)         /* *uch */
  268. #define Prev_Address    reg(a2)         /* *Pos */
  269. #define Scan_Ini        reg(a3)         /* *uch */
  270. #define Match_Ini       reg(a4)         /* *uch */
  271. #define Stack_Pointer   reg(sp)
  272.  
  273.         GLOBAL  (_match_init)
  274.         GLOBAL  (_longest_match)
  275.  
  276.         TEXT
  277.  
  278.         FILE    ("match.S")
  279.  
  280. _match_init:
  281.         rts
  282.  
  283. /*-----------------------------------------------------------------------
  284.  * Set match_start to the longest match starting at the given string and
  285.  * return its length. Matches shorter or equal to prev_length are discarded,
  286.  * in which case the result is equal to prev_length and match_start is
  287.  * garbage.
  288.  * IN assertions: cur_match is the head of the hash chain for the current
  289.  *   string (strstart) and its distance is <= MAX_DIST, and prev_length >= 1
  290.  */
  291.  
  292. /* int longest_match (cur_match) */
  293.  
  294. #ifdef UNALIGNED_OK
  295. #  define pushreg       15928           /* d2-d6/a2-a4 */
  296. #  define popreg        7292
  297. #else
  298. #  define pushreg       16184           /* d2-d7/a2-a4 */
  299. #  define popreg        7420
  300. #endif
  301.  
  302. _longest_match:
  303.         movel   IndBase(4,Stack_Pointer),Cur_Match
  304.         moveml  imm(pushreg),predec(Stack_Pointer)
  305.         movel   _max_chain_length,Chain_Length
  306.         movel   _prev_length,Best_Len
  307.         movel   imm(_prev),Prev_Address
  308.         movel   imm(_window+MIN_MATCH),Match_Ini
  309.         movel   _strstart,Limit
  310.         movel   Match_Ini,Scan_Ini
  311.         addl    Limit,Scan_Ini
  312.         subw    imm(MAX_DIST),Limit
  313.         bhis    L__limit_ok
  314.         clrl    Limit
  315. L__limit_ok:
  316.         cmpl    invert_maybe(_good_match,Best_Len)
  317.         blos    L__length_ok
  318.         lsrl    imm(2),Chain_Length
  319. L__length_ok:
  320.         subql   imm(1),Chain_Length
  321. #ifdef UNALIGNED_OK
  322.         movew   IndBase(-MIN_MATCH,Scan_Ini),Scan_Start
  323.         movew   IndBaseNdxw(-MIN_MATCH-1,Scan_Ini,Best_Len),Scan_End
  324. #else
  325.         moveb   IndBase(-MIN_MATCH,Scan_Ini),Scan_Start
  326.         lslw    imm(8),Scan_Start
  327.         moveb   IndBase(-MIN_MATCH+1,Scan_Ini),Scan_Start
  328.         moveb   IndBaseNdxw(-MIN_MATCH-1,Scan_Ini,Best_Len),Scan_End
  329.         lslw    imm(8),Scan_End
  330.         moveb   IndBaseNdxw(-MIN_MATCH,Scan_Ini,Best_Len),Scan_End
  331. #endif
  332.         bras    L__do_scan
  333.  
  334. L__long_loop:
  335. #ifdef UNALIGNED_OK
  336.         movew   IndBaseNdxw(-MIN_MATCH-1,Scan_Ini,Best_Len),Scan_End
  337. #else
  338.         moveb   IndBaseNdxw(-MIN_MATCH-1,Scan_Ini,Best_Len),Scan_End
  339.         lslw    imm(8),Scan_End
  340.         moveb   IndBaseNdxw(-MIN_MATCH,Scan_Ini,Best_Len),Scan_End
  341. #endif
  342.  
  343. L__short_loop:
  344.         lslw    imm(1),Cur_Match
  345.         movew   IndBaseNdxl(0,Prev_Address,Cur_Match),Cur_Match
  346.         cmpw    invert_maybe(Limit,Cur_Match)
  347.         dbls    Chain_Length,L__do_scan
  348.         bras    L__return
  349.  
  350. L__do_scan:
  351.         movel   Match_Ini,Match
  352.         addl    Cur_Match,Match
  353. #ifdef UNALIGNED_OK
  354.         cmpw    invert_maybe(IndBaseNdxw(-MIN_MATCH-1,Match,Best_Len),Scan_End)
  355.         bne     L__short_loop
  356.         cmpw    invert_maybe(IndBase(-MIN_MATCH,Match),Scan_Start)
  357.         bne     L__short_loop
  358. #else
  359.         moveb   IndBaseNdxw(-MIN_MATCH-1,Match,Best_Len),Scan_Test
  360.         lslw    imm(8),Scan_Test
  361.         moveb   IndBaseNdxw(-MIN_MATCH,Match,Best_Len),Scan_Test
  362.         cmpw    invert_maybe(Scan_Test,Scan_End)
  363.         bne     L__short_loop
  364.         moveb   IndBase(-MIN_MATCH,Match),Scan_Test
  365.         lslw    imm(8),Scan_Test
  366.         moveb   IndBase(-MIN_MATCH+1,Match),Scan_Test
  367.         cmpw    invert_maybe(Scan_Test,Scan_Start)
  368.         bne     L__short_loop
  369. #endif
  370.  
  371.         movew   imm((MAX_MATCH-MIN_MATCH+1)-1),Loop_Counter
  372.         movel   Scan_Ini,Scan
  373. L__scan_loop:
  374.         cmpmb   postinc(Match),postinc(Scan)
  375.         dbne    Loop_Counter,L__scan_loop
  376.  
  377.         subl    Scan_Ini,Scan
  378.         addql   imm(MIN_MATCH-1),Scan
  379.         cmpl    invert_maybe(Best_Len,Scan)
  380.         bls     L__short_loop
  381.         movel   Scan,Best_Len
  382.         movel   Cur_Match,_match_start
  383.         cmpl    invert_maybe(_nice_match,Best_Len)
  384.         blos    L__long_loop
  385. L__return:
  386.         moveml  postinc(Stack_Pointer),imm(popreg)
  387.         rts
  388.  
  389. #else
  390.  error: this asm version is for 386 or 680x0 only
  391. #endif /* mc68000 || mc68020 */
  392. #endif /* i386 || _I386 || _i386 || __i386  */
  393.