workbench/libs/z/contrib/masmx64/gvmat64.asm

   1 ;uInt longest_match_x64(
   2 ;    deflate_state *s,
   3 ;    IPos cur_match);                             /* current match */
   4
   5 ; gvmat64.asm -- Asm portion of the optimized longest_match for 32 bits x86_64
   6 ;  (AMD64 on Athlon 64, Opteron, Phenom
   7 ;     and Intel EM64T on Pentium 4 with EM64T, Pentium D, Core 2 Duo, Core I5/I7)
   8 ; Copyright (C) 1995-2010 Jean-loup Gailly, Brian Raiter and Gilles Vollant.
   9 ;
  10 ; File written by Gilles Vollant, by converting to assembly the longest_match
  11 ;  from Jean-loup Gailly in deflate.c of zLib and infoZip zip.
  12 ;
  13 ;  and by taking inspiration on asm686 with masm, optimised assembly code
  14 ;        from Brian Raiter, written 1998
  15 ;
  16 ;  This software is provided 'as-is', without any express or implied
  17 ;  warranty.  In no event will the authors be held liable for any damages
  18 ;  arising from the use of this software.
  19 ;
  20 ;  Permission is granted to anyone to use this software for any purpose,
  21 ;  including commercial applications, and to alter it and redistribute it
  22 ;  freely, subject to the following restrictions:
  23 ;
  24 ;  1. The origin of this software must not be misrepresented; you must not
  25 ;     claim that you wrote the original software. If you use this software
  26 ;     in a product, an acknowledgment in the product documentation would be
  27 ;     appreciated but is not required.
  28 ;  2. Altered source versions must be plainly marked as such, and must not be
  29 ;     misrepresented as being the original software
  30 ;  3. This notice may not be removed or altered from any source distribution.
  31 ;
  32 ;
  33 ;
  34 ;         http://www.zlib.net
  35 ;         http://www.winimage.com/zLibDll
  36 ;         http://www.muppetlabs.com/~breadbox/software/assembly.html
  37 ;
  38 ; to compile this file for infozip Zip, I use option:
  39 ;   ml64.exe /Flgvmat64 /c /Zi /DINFOZIP gvmat64.asm
  40 ;
  41 ; to compile this file for zLib, I use option:
  42 ;   ml64.exe /Flgvmat64 /c /Zi gvmat64.asm
  43 ; Be carrefull to adapt zlib1222add below to your version of zLib
  44 ;   (if you use a version of zLib before 1.0.4 or after 1.2.2.2, change
  45 ;    value of zlib1222add later)
  46 ;
  47 ; This file compile with Microsoft Macro Assembler (x64) for AMD64
  48 ;
  49 ;   ml64.exe is given with Visual Studio 2005/2008/2010 and Windows WDK
  50 ;
  51 ;   (you can get Windows WDK with ml64 for AMD64 from
  52 ;      http://www.microsoft.com/whdc/Devtools/wdk/default.mspx for low price)
  53 ;
  54
  55
  56 ;uInt longest_match(s, cur_match)
  57 ;    deflate_state *s;
  58 ;    IPos cur_match;                             /* current match */
  59 .code
  60 longest_match PROC
  61
  62
  63 ;LocalVarsSize   equ 88
  64  LocalVarsSize   equ 72
  65
  66 ; register used : rax,rbx,rcx,rdx,rsi,rdi,r8,r9,r10,r11,r12
  67 ; free register :  r14,r15
  68 ; register can be saved : rsp
  69
  70  chainlenwmask   equ  rsp + 8 - LocalVarsSize    ; high word: current chain len
  71                                                  ; low word: s->wmask
  72 ;window          equ  rsp + xx - LocalVarsSize   ; local copy of s->window ; stored in r10
  73 ;windowbestlen   equ  rsp + xx - LocalVarsSize   ; s->window + bestlen , use r10+r11
  74 ;scanstart       equ  rsp + xx - LocalVarsSize   ; first two bytes of string ; stored in r12w
  75 ;scanend         equ  rsp + xx - LocalVarsSize   ; last two bytes of string use ebx
  76 ;scanalign       equ  rsp + xx - LocalVarsSize   ; dword-misalignment of string r13
  77 ;bestlen         equ  rsp + xx - LocalVarsSize   ; size of best match so far -> r11d
  78 ;scan            equ  rsp + xx - LocalVarsSize   ; ptr to string wanting match -> r9
  79 IFDEF INFOZIP
  80 ELSE
  81  nicematch       equ  (rsp + 16 - LocalVarsSize) ; a good enough match size
  82 ENDIF
  83
  84 save_rdi        equ  rsp + 24 - LocalVarsSize
  85 save_rsi        equ  rsp + 32 - LocalVarsSize
  86 save_rbx        equ  rsp + 40 - LocalVarsSize
  87 save_rbp        equ  rsp + 48 - LocalVarsSize
  88 save_r12        equ  rsp + 56 - LocalVarsSize
  89 save_r13        equ  rsp + 64 - LocalVarsSize
  90 ;save_r14        equ  rsp + 72 - LocalVarsSize
  91 ;save_r15        equ  rsp + 80 - LocalVarsSize
  92
  93
  94 ; summary of register usage
  95 ; scanend     ebx
  96 ; scanendw    bx
  97 ; chainlenwmask   edx
  98 ; curmatch    rsi
  99 ; curmatchd   esi
 100 ; windowbestlen   r8
 101 ; scanalign   r9
 102 ; scanalignd  r9d
 103 ; window      r10
 104 ; bestlen     r11
 105 ; bestlend    r11d
 106 ; scanstart   r12d
 107 ; scanstartw  r12w
 108 ; scan        r13
 109 ; nicematch   r14d
 110 ; limit       r15
 111 ; limitd      r15d
 112 ; prev        rcx
 113
 114 ;  all the +4 offsets are due to the addition of pending_buf_size (in zlib
 115 ;  in the deflate_state structure since the asm code was first written
 116 ;  (if you compile with zlib 1.0.4 or older, remove the +4).
 117 ;  Note : these value are good with a 8 bytes boundary pack structure
 118
 119
 120     MAX_MATCH           equ     258
 121     MIN_MATCH           equ     3
 122     MIN_LOOKAHEAD       equ     (MAX_MATCH+MIN_MATCH+1)
 123
 124
 125 ;;; Offsets for fields in the deflate_state structure. These numbers
 126 ;;; are calculated from the definition of deflate_state, with the
 127 ;;; assumption that the compiler will dword-align the fields. (Thus,
 128 ;;; changing the definition of deflate_state could easily cause this
 129 ;;; program to crash horribly, without so much as a warning at
 130 ;;; compile time. Sigh.)
 131
 132 ;  all the +zlib1222add offsets are due to the addition of fields
 133 ;  in zlib in the deflate_state structure since the asm code was first written
 134 ;  (if you compile with zlib 1.0.4 or older, use "zlib1222add equ (-4)").
 135 ;  (if you compile with zlib between 1.0.5 and 1.2.2.1, use "zlib1222add equ 0").
 136 ;  if you compile with zlib 1.2.2.2 or later , use "zlib1222add equ 8").
 137
 138
 139 IFDEF INFOZIP
 140
 141 _DATA   SEGMENT
 142 COMM    window_size:DWORD
 143 ; WMask ; 7fff
 144 COMM    window:BYTE:010040H
 145 COMM    prev:WORD:08000H
 146 ; MatchLen : unused
 147 ; PrevMatch : unused
 148 COMM    strstart:DWORD
 149 COMM    match_start:DWORD
 150 ; Lookahead : ignore
 151 COMM    prev_length:DWORD ; PrevLen
 152 COMM    max_chain_length:DWORD
 153 COMM    good_match:DWORD
 154 COMM    nice_match:DWORD
 155 prev_ad equ OFFSET prev
 156 window_ad equ OFFSET window
 157 nicematch equ nice_match
 158 _DATA ENDS
 159 WMask equ 07fffh
 160
 161 ELSE
 162
 163   IFNDEF zlib1222add
 164     zlib1222add equ 8
 165   ENDIF
 166 dsWSize         equ 56+zlib1222add+(zlib1222add/2)
 167 dsWMask         equ 64+zlib1222add+(zlib1222add/2)
 168 dsWindow        equ 72+zlib1222add
 169 dsPrev          equ 88+zlib1222add
 170 dsMatchLen      equ 128+zlib1222add
 171 dsPrevMatch     equ 132+zlib1222add
 172 dsStrStart      equ 140+zlib1222add
 173 dsMatchStart    equ 144+zlib1222add
 174 dsLookahead     equ 148+zlib1222add
 175 dsPrevLen       equ 152+zlib1222add
 176 dsMaxChainLen   equ 156+zlib1222add
 177 dsGoodMatch     equ 172+zlib1222add
 178 dsNiceMatch     equ 176+zlib1222add
 179
 180 window_size     equ [ rcx + dsWSize]
 181 WMask           equ [ rcx + dsWMask]
 182 window_ad       equ [ rcx + dsWindow]
 183 prev_ad         equ [ rcx + dsPrev]
 184 strstart        equ [ rcx + dsStrStart]
 185 match_start     equ [ rcx + dsMatchStart]
 186 Lookahead       equ [ rcx + dsLookahead] ; 0ffffffffh on infozip
 187 prev_length     equ [ rcx + dsPrevLen]
 188 max_chain_length equ [ rcx + dsMaxChainLen]
 189 good_match      equ [ rcx + dsGoodMatch]
 190 nice_match      equ [ rcx + dsNiceMatch]
 191 ENDIF
 192
 193 ; parameter 1 in r8(deflate state s), param 2 in rdx (cur match)
 194
 195 ; see http://weblogs.asp.net/oldnewthing/archive/2004/01/14/58579.aspx and
 196 ; http://msdn.microsoft.com/library/en-us/kmarch/hh/kmarch/64bitAMD_8e951dd2-ee77-4728-8702-55ce4b5dd24a.xml.asp
 197 ;
 198 ; All registers must be preserved across the call, except for
 199 ;   rax, rcx, rdx, r8, r9, r10, and r11, which are scratch.
 200
 201
 202
 203 ;;; Save registers that the compiler may be using, and adjust esp to
 204 ;;; make room for our stack frame.
 205
 206
 207 ;;; Retrieve the function arguments. r8d will hold cur_match
 208 ;;; throughout the entire function. edx will hold the pointer to the
 209 ;;; deflate_state structure during the function's setup (before
 210 ;;; entering the main loop.
 211
 212 ; parameter 1 in rcx (deflate_state* s), param 2 in edx -> r8 (cur match)
 213
 214 ; this clear high 32 bits of r8, which can be garbage in both r8 and rdx
 215
 216         mov [save_rdi],rdi
 217         mov [save_rsi],rsi
 218         mov [save_rbx],rbx
 219         mov [save_rbp],rbp
 220 IFDEF INFOZIP
 221         mov r8d,ecx
 222 ELSE
 223         mov r8d,edx
 224 ENDIF
 225         mov [save_r12],r12
 226         mov [save_r13],r13
 227 ;        mov [save_r14],r14
 228 ;        mov [save_r15],r15
 229
 230
 231 ;;; uInt wmask = s->w_mask;
 232 ;;; unsigned chain_length = s->max_chain_length;
 233 ;;; if (s->prev_length >= s->good_match) {
 234 ;;;     chain_length >>= 2;
 235 ;;; }
 236
 237         mov edi, prev_length
 238         mov esi, good_match
 239         mov eax, WMask
 240         mov ebx, max_chain_length
 241         cmp edi, esi
 242         jl  LastMatchGood
 243         shr ebx, 2
 244 LastMatchGood:
 245
 246 ;;; chainlen is decremented once beforehand so that the function can
 247 ;;; use the sign flag instead of the zero flag for the exit test.
 248 ;;; It is then shifted into the high word, to make room for the wmask
 249 ;;; value, which it will always accompany.
 250
 251         dec ebx
 252         shl ebx, 16
 253         or  ebx, eax
 254
 255 ;;; on zlib only
 256 ;;; if ((uInt)nice_match > s->lookahead) nice_match = s->lookahead;
 257
 258 IFDEF INFOZIP
 259         mov [chainlenwmask], ebx
 260 ; on infozip nice_match = [nice_match]
 261 ELSE
 262         mov eax, nice_match
 263         mov [chainlenwmask], ebx
 264         mov r10d, Lookahead
 265         cmp r10d, eax
 266         cmovnl r10d, eax
 267         mov [nicematch],r10d
 268 ENDIF
 269
 270 ;;; register Bytef *scan = s->window + s->strstart;
 271         mov r10, window_ad
 272         mov ebp, strstart
 273         lea r13, [r10 + rbp]
 274
 275 ;;; Determine how many bytes the scan ptr is off from being
 276 ;;; dword-aligned.
 277
 278          mov r9,r13
 279          neg r13
 280          and r13,3
 281
 282 ;;; IPos limit = s->strstart > (IPos)MAX_DIST(s) ?
 283 ;;;     s->strstart - (IPos)MAX_DIST(s) : NIL;
 284 IFDEF INFOZIP
 285         mov eax,07efah ; MAX_DIST = (WSIZE-MIN_LOOKAHEAD) (0x8000-(3+8+1))
 286 ELSE
 287         mov eax, window_size
 288         sub eax, MIN_LOOKAHEAD
 289 ENDIF
 290         xor edi,edi
 291         sub ebp, eax
 292
 293         mov r11d, prev_length
 294
 295         cmovng ebp,edi
 296
 297 ;;; int best_len = s->prev_length;
 298
 299
 300 ;;; Store the sum of s->window + best_len in esi locally, and in esi.
 301
 302        lea  rsi,[r10+r11]
 303
 304 ;;; register ush scan_start = *(ushf*)scan;
 305 ;;; register ush scan_end   = *(ushf*)(scan+best_len-1);
 306 ;;; Posf *prev = s->prev;
 307
 308         movzx r12d,word ptr [r9]
 309         movzx ebx, word ptr [r9 + r11 - 1]
 310
 311         mov rdi, prev_ad
 312
 313 ;;; Jump into the main loop.
 314
 315         mov edx, [chainlenwmask]
 316
 317         cmp bx,word ptr [rsi + r8 - 1]
 318         jz  LookupLoopIsZero
 319
 320 LookupLoop1:
 321         and r8d, edx
 322
 323         movzx   r8d, word ptr [rdi + r8*2]
 324         cmp r8d, ebp
 325         jbe LeaveNow
 326         sub edx, 00010000h
 327         js  LeaveNow
 328
 329 LoopEntry1:
 330         cmp bx,word ptr [rsi + r8 - 1]
 331         jz  LookupLoopIsZero
 332
 333 LookupLoop2:
 334         and r8d, edx
 335
 336         movzx   r8d, word ptr [rdi + r8*2]
 337         cmp r8d, ebp
 338         jbe LeaveNow
 339         sub edx, 00010000h
 340         js  LeaveNow
 341
 342 LoopEntry2:
 343         cmp bx,word ptr [rsi + r8 - 1]
 344         jz  LookupLoopIsZero
 345
 346 LookupLoop4:
 347         and r8d, edx
 348
 349         movzx   r8d, word ptr [rdi + r8*2]
 350         cmp r8d, ebp
 351         jbe LeaveNow
 352         sub edx, 00010000h
 353         js  LeaveNow
 354
 355 LoopEntry4:
 356
 357         cmp bx,word ptr [rsi + r8 - 1]
 358         jnz LookupLoop1
 359         jmp LookupLoopIsZero
 360
 361
 362 ;;; do {
 363 ;;;     match = s->window + cur_match;
 364 ;;;     if (*(ushf*)(match+best_len-1) != scan_end ||
 365 ;;;         *(ushf*)match != scan_start) continue;
 366 ;;;     [...]
 367 ;;; } while ((cur_match = prev[cur_match & wmask]) > limit
 368 ;;;          && --chain_length != 0);
 369 ;;;
 370 ;;; Here is the inner loop of the function. The function will spend the
 371 ;;; majority of its time in this loop, and majority of that time will
 372 ;;; be spent in the first ten instructions.
 373 ;;;
 374 ;;; Within this loop:
 375 ;;; ebx = scanend
 376 ;;; r8d = curmatch
 377 ;;; edx = chainlenwmask - i.e., ((chainlen << 16) | wmask)
 378 ;;; esi = windowbestlen - i.e., (window + bestlen)
 379 ;;; edi = prev
 380 ;;; ebp = limit
 381
 382 LookupLoop:
 383         and r8d, edx
 384
 385         movzx   r8d, word ptr [rdi + r8*2]
 386         cmp r8d, ebp
 387         jbe LeaveNow
 388         sub edx, 00010000h
 389         js  LeaveNow
 390
 391 LoopEntry:
 392
 393         cmp bx,word ptr [rsi + r8 - 1]
 394         jnz LookupLoop1
 395 LookupLoopIsZero:
 396         cmp     r12w, word ptr [r10 + r8]
 397         jnz LookupLoop1
 398
 399
 400 ;;; Store the current value of chainlen.
 401         mov [chainlenwmask], edx
 402
 403 ;;; Point edi to the string under scrutiny, and esi to the string we
 404 ;;; are hoping to match it up with. In actuality, esi and edi are
 405 ;;; both pointed (MAX_MATCH_8 - scanalign) bytes ahead, and edx is
 406 ;;; initialized to -(MAX_MATCH_8 - scanalign).
 407
 408         lea rsi,[r8+r10]
 409         mov rdx, 0fffffffffffffef8h; -(MAX_MATCH_8)
 410         lea rsi, [rsi + r13 + 0108h] ;MAX_MATCH_8]
 411         lea rdi, [r9 + r13 + 0108h] ;MAX_MATCH_8]
 412
 413         prefetcht1 [rsi+rdx]
 414         prefetcht1 [rdi+rdx]
 415
 416
 417 ;;; Test the strings for equality, 8 bytes at a time. At the end,
 418 ;;; adjust rdx so that it is offset to the exact byte that mismatched.
 419 ;;;
 420 ;;; We already know at this point that the first three bytes of the
 421 ;;; strings match each other, and they can be safely passed over before
 422 ;;; starting the compare loop. So what this code does is skip over 0-3
 423 ;;; bytes, as much as necessary in order to dword-align the edi
 424 ;;; pointer. (rsi will still be misaligned three times out of four.)
 425 ;;;
 426 ;;; It should be confessed that this loop usually does not represent
 427 ;;; much of the total running time. Replacing it with a more
 428 ;;; straightforward "rep cmpsb" would not drastically degrade
 429 ;;; performance.
 430
 431
 432 LoopCmps:
 433         mov rax, [rsi + rdx]
 434         xor rax, [rdi + rdx]
 435         jnz LeaveLoopCmps
 436
 437         mov rax, [rsi + rdx + 8]
 438         xor rax, [rdi + rdx + 8]
 439         jnz LeaveLoopCmps8
 440
 441
 442         mov rax, [rsi + rdx + 8+8]
 443         xor rax, [rdi + rdx + 8+8]
 444         jnz LeaveLoopCmps16
 445
 446         add rdx,8+8+8
 447
 448         jnz short LoopCmps
 449         jmp short LenMaximum
 450 LeaveLoopCmps16: add rdx,8
 451 LeaveLoopCmps8: add rdx,8
 452 LeaveLoopCmps:
 453
 454         test    eax, 0000FFFFh
 455         jnz LenLower
 456
 457         test eax,0ffffffffh
 458
 459         jnz LenLower32
 460
 461         add rdx,4
 462         shr rax,32
 463         or ax,ax
 464         jnz LenLower
 465
 466 LenLower32:
 467         shr eax,16
 468         add rdx,2
 469 LenLower:   sub al, 1
 470         adc rdx, 0
 471 ;;; Calculate the length of the match. If it is longer than MAX_MATCH,
 472 ;;; then automatically accept it as the best possible match and leave.
 473
 474         lea rax, [rdi + rdx]
 475         sub rax, r9
 476         cmp eax, MAX_MATCH
 477         jge LenMaximum
 478
 479 ;;; If the length of the match is not longer than the best match we
 480 ;;; have so far, then forget it and return to the lookup loop.
 481 ;///////////////////////////////////
 482
 483         cmp eax, r11d
 484         jg  LongerMatch
 485
 486         lea rsi,[r10+r11]
 487
 488         mov rdi, prev_ad
 489         mov edx, [chainlenwmask]
 490         jmp LookupLoop
 491
 492 ;;;         s->match_start = cur_match;
 493 ;;;         best_len = len;
 494 ;;;         if (len >= nice_match) break;
 495 ;;;         scan_end = *(ushf*)(scan+best_len-1);
 496
 497 LongerMatch:
 498         mov r11d, eax
 499         mov match_start, r8d
 500         cmp eax, [nicematch]
 501         jge LeaveNow
 502
 503         lea rsi,[r10+rax]
 504
 505         movzx   ebx, word ptr [r9 + rax - 1]
 506         mov rdi, prev_ad
 507         mov edx, [chainlenwmask]
 508         jmp LookupLoop
 509
 510 ;;; Accept the current string, with the maximum possible length.
 511
 512 LenMaximum:
 513         mov r11d,MAX_MATCH
 514         mov match_start, r8d
 515
 516 ;;; if ((uInt)best_len <= s->lookahead) return (uInt)best_len;
 517 ;;; return s->lookahead;
 518
 519 LeaveNow:
 520 IFDEF INFOZIP
 521         mov eax,r11d
 522 ELSE
 523         mov eax, Lookahead
 524         cmp r11d, eax
 525         cmovng eax, r11d
 526 ENDIF
 527
 528 ;;; Restore the stack and return from whence we came.
 529
 530
 531         mov rsi,[save_rsi]
 532         mov rdi,[save_rdi]
 533         mov rbx,[save_rbx]
 534         mov rbp,[save_rbp]
 535         mov r12,[save_r12]
 536         mov r13,[save_r13]
 537 ;        mov r14,[save_r14]
 538 ;        mov r15,[save_r15]
 539
 540
 541         ret 0
 542 ; please don't remove this string !
 543 ; Your can freely use gvmat64 in any free or commercial app
 544 ; but it is far better don't remove the string in the binary!
 545     db     0dh,0ah,"asm686 with masm, optimised assembly code from Brian Raiter, written 1998, converted to amd 64 by Gilles Vollant 2005",0dh,0ah,0
 546 longest_match   ENDP
 547
 548 match_init PROC
 549   ret 0
 550 match_init ENDP
 551
 552
 553 END