contrib/masmx64/gvmat64.asm

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