lib/match.c

   1 /* match.s -- optional optimized asm version of longest match in deflate.c
   2
   3    Copyright (C) 2002, 2006, 2009-2024 Free Software Foundation, Inc.
   4    Copyright (C) 1992-1993 Jean-loup Gailly
   5
   6    This program is free software; you can redistribute it and/or modify
   7    it under the terms of the GNU General Public License as published by
   8    the Free Software Foundation; either version 3, or (at your option)
   9    any later version.
  10
  11    This program is distributed in the hope that it will be useful,
  12    but WITHOUT ANY WARRANTY; without even the implied warranty of
  13    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14    GNU General Public License for more details.
  15
  16    You should have received a copy of the GNU General Public License
  17    along with this program; if not, write to the Free Software Foundation,
  18    Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.  */
  19
  20 /*
  21  * The 68020 version has been written by Francesco Potortì <pot@cnuce.cnr.it>
  22  * with adaptations by Carsten Steger <stegerc@informatik.tu-muenchen.de>,
  23  * Andreas Schwab <schwab@lamothe.informatik.uni-dortmund.de> and
  24  * Kristoffer Eriksson <ske@pkmab.se>
  25  *
  26  * The ia64 version has been written by Sverre Jarp (HP Labs) 2001-2002.
  27  * Unwind directives and some reformatting for better readability added by
  28  * David Mosberger-Tang <davidm@hpl.hp.com>.
  29  */
  30
  31 /* Preprocess with -DNO_UNDERLINE if your C compiler does not prefix
  32  * external symbols with an underline character '_'.
  33  */
  34 #ifdef NO_UNDERLINE
  35 #  define _prev             prev
  36 #  define _window           window
  37 #  define _match_start      match_start
  38 #  define _prev_length      prev_length
  39 #  define _good_match       good_match
  40 #  define _nice_match       nice_match
  41 #  define _strstart         strstart
  42 #  define _max_chain_length max_chain_length
  43
  44 #  define _match_init       match_init
  45 #  define _longest_match    longest_match
  46 #endif
  47
  48 #ifdef DYN_ALLOC
  49   error: DYN_ALLOC not yet supported in match.s
  50 #endif
  51
  52 /* On x86-64, Sun C 5.13 (Oracle Solaris Studio 12.4) 'cc -E -m64'
  53    defines i386 when compiling .s or .S files!  Luckily it also
  54    defines __x86_64__.  See Bug#23133.  */
  55 #if ((defined i386 || defined _I386 || defined __i386 || defined __i386__) \
  56      && !defined __x86_64__)
  57
  58 /* This version is for 386 Unix or OS/2 in 32 bit mode.
  59  * Warning: it uses the AT&T syntax: mov source,dest
  60  * This file is only optional. If you want to force the C version,
  61  * add -DNO_ASM to CFLAGS in Makefile and set OBJA to an empty string.
  62  * If you have reduced WSIZE in gzip.h, then change its value below.
  63  * This version assumes static allocation of the arrays (-DDYN_ALLOC not used).
  64  */
  65
  66         .file   "match.S"
  67
  68 #define MAX_MATCH       258
  69 #define MAX_MATCH2      $128 /* MAX_MATCH/2-1 */
  70 #define MIN_MATCH       3
  71 #define    WSIZE        $32768
  72 #define MAX_DIST        WSIZE - MAX_MATCH - MIN_MATCH - 1
  73
  74         .globl  _match_init
  75         .globl  _longest_match
  76
  77         .text
  78
  79 _match_init:
  80         ret
  81
  82 /*-----------------------------------------------------------------------
  83  * Set match_start to the longest match starting at the given string and
  84  * return its length. Matches shorter or equal to prev_length are discarded,
  85  * in which case the result is equal to prev_length and match_start is
  86  * garbage.
  87  * IN assertions: cur_match is the head of the hash chain for the current
  88  *   string (strstart) and its distance is <= MAX_DIST, and prev_length >= 1
  89  */
  90
  91 _longest_match: /* int longest_match(cur_match) */
  92
  93 #define cur_match   20(%esp)
  94      /* return address */               /* esp+16 */
  95         push    %ebp                    /* esp+12 */
  96         push    %edi                    /* esp+8  */
  97         push    %esi                    /* esp+4  */
  98         push    %ebx                    /* esp    */
  99
 100 /*
 101  *      match        equ esi
 102  *      scan         equ edi
 103  *      chain_length equ ebp
 104  *      best_len     equ ebx
 105  *      limit        equ edx
 106  */
 107         mov     cur_match,%esi
 108         mov     _max_chain_length,%ebp /* chain_length = max_chain_length */
 109         mov     _strstart,%edi
 110         mov     %edi,%edx
 111         sub     MAX_DIST,%edx          /* limit = strstart-MAX_DIST */
 112         jae     limit_ok
 113         sub     %edx,%edx              /* limit = NIL */
 114 limit_ok:
 115         add     $2+_window,%edi        /* edi = offset(window+strstart+2) */
 116         mov     _prev_length,%ebx      /* best_len = prev_length */
 117         movw    -3(%ebx,%edi),%ax      /* ax = scan[best_len-1..best_len] */
 118         movw    -2(%edi),%cx           /* cx = scan[0..1] */
 119         cmp     _good_match,%ebx       /* do we have a good match already? */
 120         jb      do_scan
 121         shr     $2,%ebp                /* chain_length >>= 2 */
 122         jmp     do_scan
 123
 124         .align  4
 125 long_loop:
 126 /* at this point, edi == scan+2, esi == cur_match */
 127         movw    -3(%ebx,%edi),%ax       /* ax = scan[best_len-1..best_len] */
 128         movw     -2(%edi),%cx           /* cx = scan[0..1] */
 129 short_loop:
 130 /*
 131  * at this point, di == scan+2, si == cur_match,
 132  * ax = scan[best_len-1..best_len] and cx = scan[0..1]
 133  */
 134         and     WSIZE-1, %esi
 135         movw    _prev(%esi,%esi),%si    /* cur_match = prev[cur_match] */
 136                                         /* top word of esi is still 0 */
 137         cmp     %edx,%esi               /* cur_match <= limit ? */
 138         jbe     the_end
 139         dec     %ebp                    /* --chain_length */
 140         jz      the_end
 141 do_scan:
 142         cmpw    _window-1(%ebx,%esi),%ax/* check match at best_len-1 */
 143         jne     short_loop
 144         cmpw    _window(%esi),%cx       /* check min_match_length match */
 145         jne     short_loop
 146
 147         lea     _window+2(%esi),%esi    /* si = match */
 148         mov     %edi,%eax               /* ax = scan+2 */
 149         mov     MAX_MATCH2,%ecx         /* scan for at most MAX_MATCH bytes */
 150         rep;    cmpsw                   /* loop until mismatch */
 151         je      maxmatch                /* match of length MAX_MATCH? */
 152 mismatch:
 153         movb    -2(%edi),%cl        /* mismatch on first or second byte? */
 154         subb    -2(%esi),%cl        /* cl = 0 if first bytes equal */
 155         xchg    %edi,%eax           /* edi = scan+2, eax = end of scan */
 156         sub     %edi,%eax           /* eax = len */
 157         sub     %eax,%esi           /* esi = cur_match + 2 + offset(window) */
 158         sub     $2+_window,%esi     /* esi = cur_match */
 159         subb    $1,%cl              /* set carry if cl == 0 (cannot use DEC) */
 160         adc     $0,%eax             /* eax = carry ? len+1 : len */
 161         cmp     %ebx,%eax           /* len > best_len ? */
 162         jle     long_loop
 163         mov     %esi,_match_start       /* match_start = cur_match */
 164         mov     %eax,%ebx               /* ebx = best_len = len */
 165         cmp     _nice_match,%eax        /* len >= nice_match ? */
 166         jl      long_loop
 167 the_end:
 168         mov     %ebx,%eax               /* result = eax = best_len */
 169         pop     %ebx
 170         pop     %esi
 171         pop     %edi
 172         pop     %ebp
 173         ret
 174 maxmatch:
 175         cmpsb
 176         jmp     mismatch
 177
 178 #else
 179
 180 /* ======================== 680x0 version ================================= */
 181
 182 #if defined(m68k)||defined(mc68k)||defined(__mc68000__)||defined(__MC68000__)
 183 #  ifndef mc68000
 184 #    define mc68000
 185 #  endif
 186 #endif
 187
 188 #if defined(__mc68020__) || defined(__MC68020__) || defined(sysV68)
 189 #  ifndef mc68020
 190 #    define mc68020
 191 #  endif
 192 #endif
 193
 194 #if defined(mc68020) || defined(mc68000)
 195
 196 #if (defined(mc68020) || defined(NeXT)) && !defined(UNALIGNED_OK)
 197 #  define UNALIGNED_OK
 198 #endif
 199
 200 #ifdef sysV68  /* Try Motorola Delta style */
 201
 202 #  define GLOBAL(symbol)        global  symbol
 203 #  define TEXT                  text
 204 #  define FILE(filename)        file    filename
 205 #  define invert_maybe(src,dst) dst,src
 206 #  define imm(data)             &data
 207 #  define reg(register)         %register
 208
 209 #  define addl                  add.l
 210 #  define addql                 addq.l
 211 #  define blos                  blo.b
 212 #  define bhis                  bhi.b
 213 #  define bras                  bra.b
 214 #  define clrl                  clr.l
 215 #  define cmpmb                 cmpm.b
 216 #  define cmpw                  cmp.w
 217 #  define cmpl                  cmp.l
 218 #  define lslw                  lsl.w
 219 #  define lsrl                  lsr.l
 220 #  define movel                 move.l
 221 #  define movew                 move.w
 222 #  define moveb                 move.b
 223 #  define moveml                movem.l
 224 #  define subl                  sub.l
 225 #  define subw                  sub.w
 226 #  define subql                 subq.l
 227
 228 #  define IndBase(bd,An)        (bd,An)
 229 #  define IndBaseNdxl(bd,An,Xn) (bd,An,Xn.l)
 230 #  define IndBaseNdxw(bd,An,Xn) (bd,An,Xn.w)
 231 #  define predec(An)            -(An)
 232 #  define postinc(An)           (An)+
 233
 234 #else /* default style (Sun 3, NeXT, Atari) */
 235
 236 #  define GLOBAL(symbol)        .globl  symbol
 237 #  define TEXT                  .text
 238 #  define FILE(filename)        .even
 239 #  define invert_maybe(src,dst) src,dst
 240 #  if defined(sun) || defined(mc68k)
 241 #    define imm(data)           #data
 242 #  else
 243 #    define imm(data)           \#data
 244 #  endif
 245 #  define reg(register)         register
 246
 247 #  define blos                  bcss
 248 #  if defined(sun) || defined(mc68k)
 249 #    define movel               movl
 250 #    define movew               movw
 251 #    define moveb               movb
 252 #  endif
 253 #  define IndBase(bd,An)        An@(bd)
 254 #  define IndBaseNdxl(bd,An,Xn) An@(bd,Xn:l)
 255 #  define IndBaseNdxw(bd,An,Xn) An@(bd,Xn:w)
 256 #  define predec(An)            An@-
 257 #  define postinc(An)           An@+
 258
 259 #endif  /* styles */
 260
 261 #define Best_Len        reg(d0)         /* unsigned */
 262 #define Cur_Match       reg(d1)         /* Ipos */
 263 #define Loop_Counter    reg(d2)         /* int */
 264 #define Scan_Start      reg(d3)         /* unsigned short */
 265 #define Scan_End        reg(d4)         /* unsigned short */
 266 #define Limit           reg(d5)         /* IPos */
 267 #define Chain_Length    reg(d6)         /* unsigned */
 268 #define Scan_Test       reg(d7)
 269 #define Scan            reg(a0)         /* *uch */
 270 #define Match           reg(a1)         /* *uch */
 271 #define Prev_Address    reg(a2)         /* *Pos */
 272 #define Scan_Ini        reg(a3)         /* *uch */
 273 #define Match_Ini       reg(a4)         /* *uch */
 274 #define Stack_Pointer   reg(sp)
 275
 276 #define MAX_MATCH       258
 277 #define MIN_MATCH       3
 278 #define WSIZE           32768
 279 #define MAX_DIST        (WSIZE - MAX_MATCH - MIN_MATCH - 1)
 280
 281         GLOBAL  (_match_init)
 282         GLOBAL  (_longest_match)
 283
 284         TEXT
 285
 286         FILE    ("match.S")
 287
 288 _match_init:
 289         rts
 290
 291 /*-----------------------------------------------------------------------
 292  * Set match_start to the longest match starting at the given string and
 293  * return its length. Matches shorter or equal to prev_length are discarded,
 294  * in which case the result is equal to prev_length and match_start is
 295  * garbage.
 296  * IN assertions: cur_match is the head of the hash chain for the current
 297  *   string (strstart) and its distance is <= MAX_DIST, and prev_length >= 1
 298  */
 299
 300 /* int longest_match (cur_match) */
 301
 302 #ifdef UNALIGNED_OK
 303 #  define pushreg       15928           /* d2-d6/a2-a4 */
 304 #  define popreg        7292
 305 #else
 306 #  define pushreg       16184           /* d2-d7/a2-a4 */
 307 #  define popreg        7420
 308 #endif
 309
 310 _longest_match:
 311         movel   IndBase(4,Stack_Pointer),Cur_Match
 312         moveml  imm(pushreg),predec(Stack_Pointer)
 313         movel   _max_chain_length,Chain_Length
 314         movel   _prev_length,Best_Len
 315         movel   imm(_prev),Prev_Address
 316         movel   imm(_window+MIN_MATCH),Match_Ini
 317         movel   _strstart,Limit
 318         movel   Match_Ini,Scan_Ini
 319         addl    Limit,Scan_Ini
 320         subw    imm(MAX_DIST),Limit
 321         bhis    L__limit_ok
 322         clrl    Limit
 323 L__limit_ok:
 324         cmpl    invert_maybe(_good_match,Best_Len)
 325         blos    L__length_ok
 326         lsrl    imm(2),Chain_Length
 327 L__length_ok:
 328         subql   imm(1),Chain_Length
 329 #ifdef UNALIGNED_OK
 330         movew   IndBase(-MIN_MATCH,Scan_Ini),Scan_Start
 331         movew   IndBaseNdxw(-MIN_MATCH-1,Scan_Ini,Best_Len),Scan_End
 332 #else
 333         moveb   IndBase(-MIN_MATCH,Scan_Ini),Scan_Start
 334         lslw    imm(8),Scan_Start
 335         moveb   IndBase(-MIN_MATCH+1,Scan_Ini),Scan_Start
 336         moveb   IndBaseNdxw(-MIN_MATCH-1,Scan_Ini,Best_Len),Scan_End
 337         lslw    imm(8),Scan_End
 338         moveb   IndBaseNdxw(-MIN_MATCH,Scan_Ini,Best_Len),Scan_End
 339 #endif
 340         bras    L__do_scan
 341
 342 L__long_loop:
 343 #ifdef UNALIGNED_OK
 344         movew   IndBaseNdxw(-MIN_MATCH-1,Scan_Ini,Best_Len),Scan_End
 345 #else
 346         moveb   IndBaseNdxw(-MIN_MATCH-1,Scan_Ini,Best_Len),Scan_End
 347         lslw    imm(8),Scan_End
 348         moveb   IndBaseNdxw(-MIN_MATCH,Scan_Ini,Best_Len),Scan_End
 349 #endif
 350
 351 L__short_loop:
 352         lslw    imm(1),Cur_Match
 353         movew   IndBaseNdxl(0,Prev_Address,Cur_Match),Cur_Match
 354         cmpw    invert_maybe(Limit,Cur_Match)
 355         dbls    Chain_Length,L__do_scan
 356         bras    L__return
 357
 358 L__do_scan:
 359         movel   Match_Ini,Match
 360         addl    Cur_Match,Match
 361 #ifdef UNALIGNED_OK
 362         cmpw    invert_maybe(IndBaseNdxw(-MIN_MATCH-1,Match,Best_Len),Scan_End)
 363         bne     L__short_loop
 364         cmpw    invert_maybe(IndBase(-MIN_MATCH,Match),Scan_Start)
 365         bne     L__short_loop
 366 #else
 367         moveb   IndBaseNdxw(-MIN_MATCH-1,Match,Best_Len),Scan_Test
 368         lslw    imm(8),Scan_Test
 369         moveb   IndBaseNdxw(-MIN_MATCH,Match,Best_Len),Scan_Test
 370         cmpw    invert_maybe(Scan_Test,Scan_End)
 371         bne     L__short_loop
 372         moveb   IndBase(-MIN_MATCH,Match),Scan_Test
 373         lslw    imm(8),Scan_Test
 374         moveb   IndBase(-MIN_MATCH+1,Match),Scan_Test
 375         cmpw    invert_maybe(Scan_Test,Scan_Start)
 376         bne     L__short_loop
 377 #endif
 378
 379         movew   imm((MAX_MATCH-MIN_MATCH+1)-1),Loop_Counter
 380         movel   Scan_Ini,Scan
 381 L__scan_loop:
 382         cmpmb   postinc(Match),postinc(Scan)
 383         dbne    Loop_Counter,L__scan_loop
 384
 385         subl    Scan_Ini,Scan
 386         addql   imm(MIN_MATCH-1),Scan
 387         cmpl    invert_maybe(Best_Len,Scan)
 388         bls     L__short_loop
 389         movel   Scan,Best_Len
 390         movel   Cur_Match,_match_start
 391         cmpl    invert_maybe(_nice_match,Best_Len)
 392         blos    L__long_loop
 393 L__return:
 394         moveml  postinc(Stack_Pointer),imm(popreg)
 395         rts
 396
 397 #else
 398
 399 # if defined (__ia64__)
 400
 401 /* ======================== ia64 version ================================= */
 402
 403 /*
 404  * 'longest_match.S' (assembly program for gzip for the IA-64 architecture)
 405  *
 406  * Optimized for McKinley, but with Merced-compatibility, such as
 407  * MIB+MIB, used wherever possible.
 408  *
 409  * Copyright: Sverre Jarp (HP Labs) 2001-2002
 410  *
 411  * See deflate.c for c-version
 412  * Version 2 - Optimize the outer loop
 413  */
 414
 415 #include <endian.h>
 416
 417 #if __BYTE_ORDER == ____BIG_ENDIAN
 418 #define  first  shl
 419 #define  second shr.u
 420 #define  count  czx1.l
 421 #else
 422 #define  first  shr.u
 423 #define  second shl
 424 #define  count  czx1.r
 425 #endif
 426
 427 // 24 rotating register (r32 - r55)
 428
 429 #define s_vmatch0               r32
 430 #define s_vmatch1               r33
 431 #define s_vmatbst               r34
 432 #define s_vmatbst1              r35
 433 #define s_amatblen              r36
 434
 435 #define s_tm1                   r56
 436 #define s_tm2                   r57
 437 #define s_tm3                   r58
 438 #define s_tm4                   r59
 439 #define s_tm5                   r60
 440 #define s_tm6                   r61
 441 #define s_tm7                   r62
 442 #define s_tm8                   r63
 443
 444 #define s_vlen                  r31
 445 #define s_vstrstart             r30
 446 #define s_vchainlen             r29
 447 #define s_awinbest              r28
 448 #define s_vcurmatch             r27
 449 #define s_vlimit                r26
 450 #define s_vscanend              r25
 451 #define s_vscanend1             r24
 452 #define s_anicematch            r23
 453 #define s_vscan0                r22
 454 #define s_vscan1                r21
 455
 456 #define s_aprev                 r20
 457 #define s_awindow               r19
 458 #define s_amatchstart           r18
 459 #define s_ascan                 r17
 460 #define s_amatch                r16
 461 #define s_wmask                 r15
 462 #define s_ascanend              r14
 463
 464 #define s_vspec_cmatch          r11             // next iteration
 465 #define s_lcsave                r10
 466 #define s_prsave                r9
 467 #define s_vbestlen              r8              // return register
 468
 469 #define s_vscan3                r3
 470 #define s_vmatch3               r2
 471
 472 #define p_no                    p2
 473 #define p_yes                   p3
 474 #define p_shf                   p4              //
 475 #define p_bn2                   p5              // Use in loop (indicating bestlen != 2)
 476
 477 #define p_nbs                   p9              // not new best_len
 478 #define p_nnc                   p10             // not nice_length
 479 #define p_ll                    p11
 480 #define p_end                   p12
 481
 482 #define MAX_MATCH               258
 483 #define MIN_MATCH                 4
 484 #define WSIZE                 32768
 485 #define MAX_DIST                WSIZE - MAX_MATCH - MIN_MATCH - 1
 486
 487 #define R_INPUT                 1
 488 #define R_LOCAL                 31
 489 #define R_OUTPUT                0
 490 #define R_ROTATING              24
 491 #define MLAT                    3
 492 #define SHLAT                   2
 493
 494 #define mova                    mov
 495 #define movi0                   mov
 496 #define cgtu                    cmp.gt.unc
 497 #define cgeu                    cmp.ge.unc
 498 #define cneu                    cmp.ne.unc
 499
 500         .global longest_match
 501         .proc longest_match
 502         .align 32
 503 longest_match:
 504 // --  Cycle: 0
 505         .prologue
 506 {.mmi
 507          alloc r2=ar.pfs,R_INPUT,R_LOCAL,R_OUTPUT,R_ROTATING
 508         .rotr scan[MLAT+2], match[MLAT+2], shscan0[SHLAT+1], \
 509               shscan1[SHLAT+1], shmatch0[SHLAT+1], shmatch1[SHLAT+1]
 510         .rotp lc[MLAT+SHLAT+2]
 511         mova s_vspec_cmatch=in0 // cur_match from input register
 512         add s_tm1=@gprel(strstart),gp // a(a(strstart))
 513 }{.mmi
 514         add s_tm3=@gprel(prev_length),gp // a(a(prev_length))
 515         add s_tm5=@ltoff(window),gp // a(a(window))
 516         add s_tm6=@ltoff(prev),gp // a(a(prev))
 517         ;;
 518 }{.mmb  //  Cycle: 1
 519         ld4 s_vstrstart=[s_tm1] // strstart
 520         ld4 s_vbestlen=[s_tm3] // best_len = prev_length
 521         brp.loop.imp .cmploop,.cmploop+48
 522 }{.mli
 523         add s_tm2=@gprel(max_chain_length),gp // a(a(max_chain_length))
 524         movl s_wmask=WSIZE-1
 525         ;;
 526 }{.mmi  //  Cycle: 2
 527         ld8 s_aprev=[s_tm6] // a(prev)
 528         ld8 s_awindow=[s_tm5] // a(window)
 529         .save pr, s_prsave
 530         movi0 s_prsave=pr // save predicates
 531 }{.mmi
 532         add s_tm4=@gprel(good_match),gp // a(a(good_match))
 533         add s_tm7=@ltoff(nice_match),gp // a(a(nice_match))
 534         add s_tm8=@ltoff(match_start),gp // a(match_start)
 535         ;;
 536 }{.mmi  //  Cycle: 3
 537         ld8 s_anicematch=[s_tm7] // a(nice_match)
 538         ld8 s_amatchstart=[s_tm8] // a(match_start)
 539         .save ar.lc, s_lcsave
 540         movi0 s_lcsave=ar.lc // save loop count register
 541 }{.mmi
 542         .body
 543         add s_tm1=-(MAX_MATCH + MIN_MATCH),s_wmask // maxdist
 544         cmp.eq p_ll,p0=r0,r0 // parallel compare initialized as 'true'
 545         mova s_vcurmatch=s_vspec_cmatch
 546         ;;
 547 }{.mmi  //  Cycle: 4
 548         ld4 s_vchainlen=[s_tm2] // chain_length=max_chain_length
 549         ld4 s_tm4=[s_tm4] // v(good_match)
 550         add s_ascan=s_awindow,s_vstrstart // scan=window + strstart
 551 }{.mmi
 552         sub s_vlimit=s_vstrstart, s_tm1 // limit=strstart - MAX_DIST
 553         add s_amatch=s_awindow,s_vspec_cmatch // match=window + cur_match
 554         and s_vspec_cmatch =s_vspec_cmatch,s_wmask
 555         ;;
 556 }{.mmi  //  Cycle: 5
 557         add s_amatblen=s_amatch,s_vbestlen //
 558         cneu p_bn2,p0=2,s_vbestlen // set if bestlen != 2
 559         add s_ascanend=s_ascan,s_vbestlen // compute a(scan) + best_len
 560 }{.mmi
 561         ld1 s_vscan0=[s_ascan],1 // NB: s_ascan++
 562         ld1 s_vmatch0=[s_amatch],1
 563         cgtu p0,p_no=s_vlimit,r0 // is result positive ?
 564         ;;
 565 }{.mmi  //  Cycle: 6
 566         ld1.nt1 s_vscan1=[s_ascan],2 // NB: s_ascan+3 in total
 567         ld1.nt1 s_vmatch1=[s_amatch],2
 568         add s_awinbest=s_awindow,s_vbestlen //
 569         ;;
 570 }{.mmi  //  Cycle: 7
 571         ld1.nt1 s_vscanend=[s_ascanend],-1 // scan_end=scan[best_len]
 572         ld1.nt1 s_vmatbst=[s_amatblen],-1
 573 (p_no)  mova s_vlimit=r0
 574         ;;
 575 }{.mmi  //  Cycle: 8
 576 (p_bn2) ld1.nt1 s_vscanend1=[s_ascanend],1 // scan_end1=scan[best_len-1]
 577 (p_bn2) ld1.nt1 s_vmatbst1=[s_amatblen]
 578         shladd s_vspec_cmatch =s_vspec_cmatch,1,s_aprev
 579 }{.mmi
 580         cgeu p_shf,p0=s_vbestlen,s_tm4 // is (prev_length >= good_match) ?
 581         ;;
 582 }{.mmi  //  Cycle: 9
 583         ld1.nt1 s_vscan3=[s_ascan]
 584         ld2.nt1 s_vspec_cmatch=[s_vspec_cmatch]
 585         mova    s_vlen=3
 586 }{.mmi
 587 (p_shf) shr.u s_vchainlen=s_vchainlen,2 // (cur_len) >> 2
 588         ;;
 589 }{.mmi  //  Cycle: 10
 590         ld1.nt1 s_vmatch3=[s_amatch]
 591         // p_ll switched on as soon as we get a mismatch:
 592         cmp.eq.and p_ll,p0=s_vmatch0,s_vscan0
 593         cmp.eq.and p_ll,p0=s_vmatbst,s_vscanend
 594 }{.mib
 595         cmp.eq.and p_ll,p0=s_vmatch1,s_vscan1
 596 (p_bn2) cmp.eq.and p_ll,p0=s_vmatbst1,s_vscanend1
 597 (p_ll)  br.cond.dpnt.many .test_more
 598         ;;
 599 }
 600
 601 .next_iter:
 602 {.mmi   // Cycle 0
 603         add s_amatch=s_awindow,s_vspec_cmatch   // match=window + cur_match
 604         mov s_vcurmatch=s_vspec_cmatch          // current value
 605         add s_vchainlen=-1,s_vchainlen          // --chain_length
 606 }{.mib
 607         cmp.le.unc p_end,p0=s_vspec_cmatch,s_vlimit
 608         and s_vspec_cmatch=s_vspec_cmatch,s_wmask
 609 (p_end) br.cond.dptk.many .terminate
 610         ;;
 611 }{.mmi  // Cycle 1
 612         ld1 s_vmatch0=[s_amatch],1              // load match[0]
 613         // compute prev[cur_match]:
 614         shladd s_vspec_cmatch=s_vspec_cmatch,1,s_aprev
 615         cmp.eq.unc p_end,p0=s_vchainlen,r0
 616 } {.mib
 617         nop.m 0
 618         add s_amatblen=s_awinbest,s_vcurmatch   // match=window + cur_match
 619 (p_end) br.cond.dptk.many .terminate
 620         ;;
 621 }{.mmi  // Cycle 2 (short)
 622         ld2.nt1 s_vspec_cmatch=[s_vspec_cmatch]         // get next cur_match
 623         ;;
 624 }{.mmi  // Cycle 3 (short)
 625         ld1.nt1 s_vmatbst=[s_amatblen],-1       // load match[best_len]
 626         cmp.ne.unc p_ll,p0=r0,r0     // parallel compare initialized as 'false'
 627         ;;
 628 }{.mmi  // Cycle 4 (short)
 629         // load match[1] - - note: match += 3 (in total):
 630         ld1.nt1 s_vmatch1=[s_amatch],2
 631         ;;
 632         // Cycle 5  (short)
 633 (p_bn2) ld1.nt1 s_vmatbst1=[s_amatblen]         // load match[best_len-1]
 634 }{.mib  // Here we (MOST LIKELY) pay a L2-fetch stall
 635         // p_ll switched on as soon as we get a mismatch:
 636         cmp.ne.or p_ll,p0=s_vmatch0,s_vscan0
 637         cmp.ne.or p_ll,p0=s_vmatbst,s_vscanend
 638 (p_ll)  br.cond.dptk.many .next_iter
 639         ;;
 640 }{.mmi  // Cycle 6
 641         ld1.nt1 s_vmatch3=[s_amatch]
 642         mova s_vlen=3
 643         nop.i 0
 644 }{.mib
 645         cmp.ne.or p_ll,p0=s_vmatch1,s_vscan1
 646 (p_bn2) cmp.ne.or p_ll,p0=s_vmatbst1,s_vscanend1
 647 (p_ll)  br.cond.dptk.many .next_iter
 648         ;;
 649 }
 650
 651 // We have passed the first hurdle - Are there additional matches ???
 652
 653 .test_more:
 654 {.mmi   // Cycle 0
 655         and s_tm3=7,s_ascan                     // get byte offset
 656         and s_tm4=7,s_amatch                    // get byte offset
 657         movi0 ar.ec=MLAT+SHLAT+2                // NB: One trip more than usual
 658 }{.mib
 659         cmp.ne.unc p_no,p0=s_vscan3,s_vmatch3   // does not next one differ?
 660 (p_no)  br.cond.dptk.many .only3
 661         ;;
 662 }{.mmi  // Cycle 1
 663         and s_tm1=-8,s_ascan    // get aligned address
 664         shladd s_tm3=s_tm3,3,r0
 665         movi0 ar.lc=31          // 32 times around the loop (8B at a time)
 666 }{.mib
 667         and s_tm2=-8,s_amatch                   // get aligned address
 668         shladd s_tm4=s_tm4,3,r0
 669         nop.b 0
 670         ;;
 671 }{.mmi  // Cycle 2
 672         ld8.nt1 scan[1]=[s_tm1],8                       // load first chunk
 673         sub s_tm5=64,s_tm3                              // 64 - amount
 674         movi0 pr.rot=1<<16
 675 }{.mmi
 676         ld8.nt1 match[1]=[s_tm2],8      // load first chunk
 677         sub s_tm6=64,s_tm4              // 64 - amount
 678         add s_vlen=-8,s_vlen            // will be updated at least once
 679         ;;
 680 }
 681         .align 32
 682 .cmploop:
 683 {.mmi   // Cycle 0
 684 (lc[0])                 ld8 scan[0]=[s_tm1],8           // next scan chunk
 685 (lc[MLAT+SHLAT+1])      add s_vlen=8,s_vlen
 686 (lc[MLAT])              first shscan0[0]=scan[MLAT+1],s_tm3
 687 }{.mib
 688 (lc[MLAT+SHLAT+1])      cmp.ne.unc p_no,p0=s_tm7,s_tm8  // break search if !=
 689 (lc[MLAT])              first shmatch0[0]=match[MLAT+1],s_tm4
 690 (p_no)                  br.cond.dpnt.many .mismatch
 691                         ;;
 692 }{.mii  // Cycle 1
 693 (lc[0])                 ld8 match[0]=[s_tm2],8
 694                         // shift left(le) or right(be):
 695 (lc[MLAT])              second shscan1[0]=scan[MLAT],s_tm5
 696 (lc[MLAT])              second shmatch1[0]=match[MLAT],s_tm6
 697 }{.mmb
 698 (lc[MLAT+SHLAT])        or s_tm7=shscan0[SHLAT],shscan1[SHLAT]
 699 (lc[MLAT+SHLAT])        or s_tm8=shmatch0[SHLAT],shmatch1[SHLAT]
 700                         br.ctop.dptk.many .cmploop
 701                         ;;
 702 }{.mfi
 703         mov s_vlen=258
 704         nop.f 0
 705 }{.mfi
 706         nop.f 0    // realign
 707         ;;
 708 }
 709 .mismatch:
 710 {.mii   // Cycle 0 (short)
 711 (p_no)  pcmp1.eq s_tm2=s_tm7,s_tm8      // find first non-matching character
 712         nop.i 0
 713         ;;
 714         // Cycle 1 (short)
 715 (p_no)  count s_tm1=s_tm2
 716         ;;
 717 }{.mib  // Cycle 2 (short)
 718 (p_no)  add s_vlen=s_vlen,s_tm1         // effective length
 719         nop.i 0
 720         clrrrb
 721         ;;
 722 }
 723
 724 .only3:
 725 {.mib   // Cycle 0 (short)
 726         cmp.gt.unc p0,p_nbs=s_vlen,s_vbestlen           // (len > best_len) ?
 727 (p_nbs) br.cond.dpnt.many .next_iter                    // if not, reiterate
 728         ;;
 729 }{.mmi  // Cycle 1 (short)
 730         ld4 s_tm7=[s_anicematch]                        // nice_match
 731         st4 [s_amatchstart]= s_vcurmatch
 732         add s_ascanend=s_ascan,s_vlen                   // reset with best_len
 733         ;;
 734 }{.mmi  // Cycle 2 (short)
 735         mova s_vbestlen=s_vlen
 736         add s_ascanend=-3,s_ascanend            // remember extra offset
 737         ;;
 738 }{.mmi  // Cycle 3 (short)
 739         ld1 s_vscanend=[s_ascanend],-1          // scan_end=scan[best_len]
 740         add s_awinbest=s_awindow,s_vbestlen     // update with new best_len
 741         cmp.ne.unc p_bn2,p0=2,s_vbestlen        // set if bestlen != 2
 742         ;;
 743 }{.mib  // Cycle 4 (short)
 744         // scan_end1=scan[best_len-1] NB: s_ascanend reset:
 745         ld1.nt1 s_vscanend1=[s_ascanend],1
 746         cmp.lt.unc p_nnc,p0=s_vlen,s_tm7        // compare with nice_match
 747 (p_nnc) br.cond.dptk.many .next_iter
 748         ;;
 749 }
 750 .terminate:
 751 {.mii   // Cycle 0/1
 752         nop.m 0
 753         movi0 ar.lc=s_lcsave
 754         movi0 pr=s_prsave,-1
 755 }{.mbb
 756         nop.m 0
 757         nop.b 0
 758         br.ret.sptk.many rp     // ret0 is identical to best_len
 759         ;;
 760 }
 761         .endp
 762
 763         .global match_init
 764         .proc match_init
 765 match_init:
 766         sub ret0=ret0,ret0
 767         br.ret.sptk.many rp
 768         .endp
 769
 770 # else
 771  error: this asm version is for 386 or 680x0 or ia64 only
 772 # endif /* __ia64__ */
 773 #endif /* mc68000 || mc68020 */
 774 #endif /* i386 || _I386   */