gnu/usr.bin/gzip/match.S

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