src/external/zlib-1.2.11/contrib/masmx86/match686.asm

   1 ; match686.asm -- Asm portion of the optimized longest_match for 32 bits x86\r
   2 ; Copyright (C) 1995-1996 Jean-loup Gailly, Brian Raiter and Gilles Vollant.\r
   3 ; File written by Gilles Vollant, by converting match686.S from Brian Raiter\r
   4 ; for MASM. This is as assembly version of longest_match\r
   5 ;  from Jean-loup Gailly in deflate.c\r
   6 ;\r
   7 ;         http://www.zlib.net\r
   8 ;         http://www.winimage.com/zLibDll\r
   9 ;         http://www.muppetlabs.com/~breadbox/software/assembly.html\r
  10 ;\r
  11 ; For Visual C++ 4.x and higher and ML 6.x and higher\r
  12 ;   ml.exe is distributed in\r
  13 ;  http://www.microsoft.com/downloads/details.aspx?FamilyID=7a1c9da0-0510-44a2-b042-7ef370530c64\r
  14 ;\r
  15 ; this file contain two implementation of longest_match\r
  16 ;\r
  17 ;  this longest_match was written by Brian raiter (1998), optimized for Pentium Pro\r
  18 ;   (and the faster known version of match_init on modern Core 2 Duo and AMD Phenom)\r
  19 ;\r
  20 ;  for using an assembly version of longest_match, you need define ASMV in project\r
  21 ;\r
  22 ;    compile the asm file running\r
  23 ;           ml /coff /Zi /c /Flmatch686.lst match686.asm\r
  24 ;    and do not include match686.obj in your project\r
  25 ;\r
  26 ; note: contrib of zLib 1.2.3 and earlier contained both a deprecated version for\r
  27 ;  Pentium (prior Pentium Pro) and this version for Pentium Pro and modern processor\r
  28 ;  with autoselect (with cpu detection code)\r
  29 ;  if you want support the old pentium optimization, you can still use these version\r
  30 ;\r
  31 ; this file is not optimized for old pentium, but it compatible with all x86 32 bits\r
  32 ; processor (starting 80386)\r
  33 ;\r
  34 ;\r
  35 ; see below : zlib1222add must be adjuster if you use a zlib version < 1.2.2.2\r
  36 \r
  37 ;uInt longest_match(s, cur_match)\r
  38 ;    deflate_state *s;\r
  39 ;    IPos cur_match;                             /* current match */\r
  40 \r
  41     NbStack         equ     76\r
  42     cur_match       equ     dword ptr[esp+NbStack-0]\r
  43     str_s           equ     dword ptr[esp+NbStack-4]\r
  44 ; 5 dword on top (ret,ebp,esi,edi,ebx)\r
  45     adrret          equ     dword ptr[esp+NbStack-8]\r
  46     pushebp         equ     dword ptr[esp+NbStack-12]\r
  47     pushedi         equ     dword ptr[esp+NbStack-16]\r
  48     pushesi         equ     dword ptr[esp+NbStack-20]\r
  49     pushebx         equ     dword ptr[esp+NbStack-24]\r
  50 \r
  51     chain_length    equ     dword ptr [esp+NbStack-28]\r
  52     limit           equ     dword ptr [esp+NbStack-32]\r
  53     best_len        equ     dword ptr [esp+NbStack-36]\r
  54     window          equ     dword ptr [esp+NbStack-40]\r
  55     prev            equ     dword ptr [esp+NbStack-44]\r
  56     scan_start      equ      word ptr [esp+NbStack-48]\r
  57     wmask           equ     dword ptr [esp+NbStack-52]\r
  58     match_start_ptr equ     dword ptr [esp+NbStack-56]\r
  59     nice_match      equ     dword ptr [esp+NbStack-60]\r
  60     scan            equ     dword ptr [esp+NbStack-64]\r
  61 \r
  62     windowlen       equ     dword ptr [esp+NbStack-68]\r
  63     match_start     equ     dword ptr [esp+NbStack-72]\r
  64     strend          equ     dword ptr [esp+NbStack-76]\r
  65     NbStackAdd      equ     (NbStack-24)\r
  66 \r
  67     .386p\r
  68 \r
  69     name    gvmatch\r
  70     .MODEL  FLAT\r
  71 \r
  72 \r
  73 \r
  74 ;  all the +zlib1222add offsets are due to the addition of fields\r
  75 ;  in zlib in the deflate_state structure since the asm code was first written\r
  76 ;  (if you compile with zlib 1.0.4 or older, use "zlib1222add equ (-4)").\r
  77 ;  (if you compile with zlib between 1.0.5 and 1.2.2.1, use "zlib1222add equ 0").\r
  78 ;  if you compile with zlib 1.2.2.2 or later , use "zlib1222add equ 8").\r
  79 \r
  80     zlib1222add         equ     8\r
  81 \r
  82 ;  Note : these value are good with a 8 bytes boundary pack structure\r
  83     dep_chain_length    equ     74h+zlib1222add\r
  84     dep_window          equ     30h+zlib1222add\r
  85     dep_strstart        equ     64h+zlib1222add\r
  86     dep_prev_length     equ     70h+zlib1222add\r
  87     dep_nice_match      equ     88h+zlib1222add\r
  88     dep_w_size          equ     24h+zlib1222add\r
  89     dep_prev            equ     38h+zlib1222add\r
  90     dep_w_mask          equ     2ch+zlib1222add\r
  91     dep_good_match      equ     84h+zlib1222add\r
  92     dep_match_start     equ     68h+zlib1222add\r
  93     dep_lookahead       equ     6ch+zlib1222add\r
  94 \r
  95 \r
  96 _TEXT                   segment\r
  97 \r
  98 IFDEF NOUNDERLINE\r
  99             public  longest_match\r
 100             public  match_init\r
 101 ELSE\r
 102             public  _longest_match\r
 103             public  _match_init\r
 104 ENDIF\r
 105 \r
 106     MAX_MATCH           equ     258\r
 107     MIN_MATCH           equ     3\r
 108     MIN_LOOKAHEAD       equ     (MAX_MATCH+MIN_MATCH+1)\r
 109 \r
 110 \r
 111 \r
 112 MAX_MATCH       equ     258\r
 113 MIN_MATCH       equ     3\r
 114 MIN_LOOKAHEAD   equ     (MAX_MATCH + MIN_MATCH + 1)\r
 115 MAX_MATCH_8_     equ     ((MAX_MATCH + 7) AND 0FFF0h)\r
 116 \r
 117 \r
 118 ;;; stack frame offsets\r
 119 \r
 120 chainlenwmask   equ  esp + 0    ; high word: current chain len\r
 121                     ; low word: s->wmask\r
 122 window      equ  esp + 4    ; local copy of s->window\r
 123 windowbestlen   equ  esp + 8    ; s->window + bestlen\r
 124 scanstart   equ  esp + 16   ; first two bytes of string\r
 125 scanend     equ  esp + 12   ; last two bytes of string\r
 126 scanalign   equ  esp + 20   ; dword-misalignment of string\r
 127 nicematch   equ  esp + 24   ; a good enough match size\r
 128 bestlen     equ  esp + 28   ; size of best match so far\r
 129 scan        equ  esp + 32   ; ptr to string wanting match\r
 130 \r
 131 LocalVarsSize   equ 36\r
 132 ;   saved ebx   byte esp + 36\r
 133 ;   saved edi   byte esp + 40\r
 134 ;   saved esi   byte esp + 44\r
 135 ;   saved ebp   byte esp + 48\r
 136 ;   return address  byte esp + 52\r
 137 deflatestate    equ  esp + 56   ; the function arguments\r
 138 curmatch    equ  esp + 60\r
 139 \r
 140 ;;; Offsets for fields in the deflate_state structure. These numbers\r
 141 ;;; are calculated from the definition of deflate_state, with the\r
 142 ;;; assumption that the compiler will dword-align the fields. (Thus,\r
 143 ;;; changing the definition of deflate_state could easily cause this\r
 144 ;;; program to crash horribly, without so much as a warning at\r
 145 ;;; compile time. Sigh.)\r
 146 \r
 147 dsWSize     equ 36+zlib1222add\r
 148 dsWMask     equ 44+zlib1222add\r
 149 dsWindow    equ 48+zlib1222add\r
 150 dsPrev      equ 56+zlib1222add\r
 151 dsMatchLen  equ 88+zlib1222add\r
 152 dsPrevMatch equ 92+zlib1222add\r
 153 dsStrStart  equ 100+zlib1222add\r
 154 dsMatchStart    equ 104+zlib1222add\r
 155 dsLookahead equ 108+zlib1222add\r
 156 dsPrevLen   equ 112+zlib1222add\r
 157 dsMaxChainLen   equ 116+zlib1222add\r
 158 dsGoodMatch equ 132+zlib1222add\r
 159 dsNiceMatch equ 136+zlib1222add\r
 160 \r
 161 \r
 162 ;;; match686.asm -- Pentium-Pro-optimized version of longest_match()\r
 163 ;;; Written for zlib 1.1.2\r
 164 ;;; Copyright (C) 1998 Brian Raiter <breadbox@muppetlabs.com>\r
 165 ;;; You can look at http://www.muppetlabs.com/~breadbox/software/assembly.html\r
 166 ;;;\r
 167 ;;\r
 168 ;;  This software is provided 'as-is', without any express or implied\r
 169 ;;  warranty.  In no event will the authors be held liable for any damages\r
 170 ;;  arising from the use of this software.\r
 171 ;;\r
 172 ;;  Permission is granted to anyone to use this software for any purpose,\r
 173 ;;  including commercial applications, and to alter it and redistribute it\r
 174 ;;  freely, subject to the following restrictions:\r
 175 ;;\r
 176 ;;  1. The origin of this software must not be misrepresented; you must not\r
 177 ;;     claim that you wrote the original software. If you use this software\r
 178 ;;     in a product, an acknowledgment in the product documentation would be\r
 179 ;;     appreciated but is not required.\r
 180 ;;  2. Altered source versions must be plainly marked as such, and must not be\r
 181 ;;     misrepresented as being the original software\r
 182 ;;  3. This notice may not be removed or altered from any source distribution.\r
 183 ;;\r
 184 \r
 185 ;GLOBAL _longest_match, _match_init\r
 186 \r
 187 \r
 188 ;SECTION    .text\r
 189 \r
 190 ;;; uInt longest_match(deflate_state *deflatestate, IPos curmatch)\r
 191 \r
 192 ;_longest_match:\r
 193     IFDEF NOUNDERLINE\r
 194     longest_match       proc near\r
 195     ELSE\r
 196     _longest_match      proc near\r
 197     ENDIF\r
 198 .FPO (9, 4, 0, 0, 1, 0)\r
 199 \r
 200 ;;; Save registers that the compiler may be using, and adjust esp to\r
 201 ;;; make room for our stack frame.\r
 202 \r
 203         push    ebp\r
 204         push    edi\r
 205         push    esi\r
 206         push    ebx\r
 207         sub esp, LocalVarsSize\r
 208 \r
 209 ;;; Retrieve the function arguments. ecx will hold cur_match\r
 210 ;;; throughout the entire function. edx will hold the pointer to the\r
 211 ;;; deflate_state structure during the function's setup (before\r
 212 ;;; entering the main loop.\r
 213 \r
 214         mov edx, [deflatestate]\r
 215         mov ecx, [curmatch]\r
 216 \r
 217 ;;; uInt wmask = s->w_mask;\r
 218 ;;; unsigned chain_length = s->max_chain_length;\r
 219 ;;; if (s->prev_length >= s->good_match) {\r
 220 ;;;     chain_length >>= 2;\r
 221 ;;; }\r
 222 \r
 223         mov eax, [edx + dsPrevLen]\r
 224         mov ebx, [edx + dsGoodMatch]\r
 225         cmp eax, ebx\r
 226         mov eax, [edx + dsWMask]\r
 227         mov ebx, [edx + dsMaxChainLen]\r
 228         jl  LastMatchGood\r
 229         shr ebx, 2\r
 230 LastMatchGood:\r
 231 \r
 232 ;;; chainlen is decremented once beforehand so that the function can\r
 233 ;;; use the sign flag instead of the zero flag for the exit test.\r
 234 ;;; It is then shifted into the high word, to make room for the wmask\r
 235 ;;; value, which it will always accompany.\r
 236 \r
 237         dec ebx\r
 238         shl ebx, 16\r
 239         or  ebx, eax\r
 240         mov [chainlenwmask], ebx\r
 241 \r
 242 ;;; if ((uInt)nice_match > s->lookahead) nice_match = s->lookahead;\r
 243 \r
 244         mov eax, [edx + dsNiceMatch]\r
 245         mov ebx, [edx + dsLookahead]\r
 246         cmp ebx, eax\r
 247         jl  LookaheadLess\r
 248         mov ebx, eax\r
 249 LookaheadLess:  mov [nicematch], ebx\r
 250 \r
 251 ;;; register Bytef *scan = s->window + s->strstart;\r
 252 \r
 253         mov esi, [edx + dsWindow]\r
 254         mov [window], esi\r
 255         mov ebp, [edx + dsStrStart]\r
 256         lea edi, [esi + ebp]\r
 257         mov [scan], edi\r
 258 \r
 259 ;;; Determine how many bytes the scan ptr is off from being\r
 260 ;;; dword-aligned.\r
 261 \r
 262         mov eax, edi\r
 263         neg eax\r
 264         and eax, 3\r
 265         mov [scanalign], eax\r
 266 \r
 267 ;;; IPos limit = s->strstart > (IPos)MAX_DIST(s) ?\r
 268 ;;;     s->strstart - (IPos)MAX_DIST(s) : NIL;\r
 269 \r
 270         mov eax, [edx + dsWSize]\r
 271         sub eax, MIN_LOOKAHEAD\r
 272         sub ebp, eax\r
 273         jg  LimitPositive\r
 274         xor ebp, ebp\r
 275 LimitPositive:\r
 276 \r
 277 ;;; int best_len = s->prev_length;\r
 278 \r
 279         mov eax, [edx + dsPrevLen]\r
 280         mov [bestlen], eax\r
 281 \r
 282 ;;; Store the sum of s->window + best_len in esi locally, and in esi.\r
 283 \r
 284         add esi, eax\r
 285         mov [windowbestlen], esi\r
 286 \r
 287 ;;; register ush scan_start = *(ushf*)scan;\r
 288 ;;; register ush scan_end   = *(ushf*)(scan+best_len-1);\r
 289 ;;; Posf *prev = s->prev;\r
 290 \r
 291         movzx   ebx, word ptr [edi]\r
 292         mov [scanstart], ebx\r
 293         movzx   ebx, word ptr [edi + eax - 1]\r
 294         mov [scanend], ebx\r
 295         mov edi, [edx + dsPrev]\r
 296 \r
 297 ;;; Jump into the main loop.\r
 298 \r
 299         mov edx, [chainlenwmask]\r
 300         jmp short LoopEntry\r
 301 \r
 302 align 4\r
 303 \r
 304 ;;; do {\r
 305 ;;;     match = s->window + cur_match;\r
 306 ;;;     if (*(ushf*)(match+best_len-1) != scan_end ||\r
 307 ;;;         *(ushf*)match != scan_start) continue;\r
 308 ;;;     [...]\r
 309 ;;; } while ((cur_match = prev[cur_match & wmask]) > limit\r
 310 ;;;          && --chain_length != 0);\r
 311 ;;;\r
 312 ;;; Here is the inner loop of the function. The function will spend the\r
 313 ;;; majority of its time in this loop, and majority of that time will\r
 314 ;;; be spent in the first ten instructions.\r
 315 ;;;\r
 316 ;;; Within this loop:\r
 317 ;;; ebx = scanend\r
 318 ;;; ecx = curmatch\r
 319 ;;; edx = chainlenwmask - i.e., ((chainlen << 16) | wmask)\r
 320 ;;; esi = windowbestlen - i.e., (window + bestlen)\r
 321 ;;; edi = prev\r
 322 ;;; ebp = limit\r
 323 \r
 324 LookupLoop:\r
 325         and ecx, edx\r
 326         movzx   ecx, word ptr [edi + ecx*2]\r
 327         cmp ecx, ebp\r
 328         jbe LeaveNow\r
 329         sub edx, 00010000h\r
 330         js  LeaveNow\r
 331 LoopEntry:  movzx   eax, word ptr [esi + ecx - 1]\r
 332         cmp eax, ebx\r
 333         jnz LookupLoop\r
 334         mov eax, [window]\r
 335         movzx   eax, word ptr [eax + ecx]\r
 336         cmp eax, [scanstart]\r
 337         jnz LookupLoop\r
 338 \r
 339 ;;; Store the current value of chainlen.\r
 340 \r
 341         mov [chainlenwmask], edx\r
 342 \r
 343 ;;; Point edi to the string under scrutiny, and esi to the string we\r
 344 ;;; are hoping to match it up with. In actuality, esi and edi are\r
 345 ;;; both pointed (MAX_MATCH_8 - scanalign) bytes ahead, and edx is\r
 346 ;;; initialized to -(MAX_MATCH_8 - scanalign).\r
 347 \r
 348         mov esi, [window]\r
 349         mov edi, [scan]\r
 350         add esi, ecx\r
 351         mov eax, [scanalign]\r
 352         mov edx, 0fffffef8h; -(MAX_MATCH_8)\r
 353         lea edi, [edi + eax + 0108h] ;MAX_MATCH_8]\r
 354         lea esi, [esi + eax + 0108h] ;MAX_MATCH_8]\r
 355 \r
 356 ;;; Test the strings for equality, 8 bytes at a time. At the end,\r
 357 ;;; adjust edx so that it is offset to the exact byte that mismatched.\r
 358 ;;;\r
 359 ;;; We already know at this point that the first three bytes of the\r
 360 ;;; strings match each other, and they can be safely passed over before\r
 361 ;;; starting the compare loop. So what this code does is skip over 0-3\r
 362 ;;; bytes, as much as necessary in order to dword-align the edi\r
 363 ;;; pointer. (esi will still be misaligned three times out of four.)\r
 364 ;;;\r
 365 ;;; It should be confessed that this loop usually does not represent\r
 366 ;;; much of the total running time. Replacing it with a more\r
 367 ;;; straightforward "rep cmpsb" would not drastically degrade\r
 368 ;;; performance.\r
 369 \r
 370 LoopCmps:\r
 371         mov eax, [esi + edx]\r
 372         xor eax, [edi + edx]\r
 373         jnz LeaveLoopCmps\r
 374         mov eax, [esi + edx + 4]\r
 375         xor eax, [edi + edx + 4]\r
 376         jnz LeaveLoopCmps4\r
 377         add edx, 8\r
 378         jnz LoopCmps\r
 379         jmp short LenMaximum\r
 380 LeaveLoopCmps4: add edx, 4\r
 381 LeaveLoopCmps:  test    eax, 0000FFFFh\r
 382         jnz LenLower\r
 383         add edx,  2\r
 384         shr eax, 16\r
 385 LenLower:   sub al, 1\r
 386         adc edx, 0\r
 387 \r
 388 ;;; Calculate the length of the match. If it is longer than MAX_MATCH,\r
 389 ;;; then automatically accept it as the best possible match and leave.\r
 390 \r
 391         lea eax, [edi + edx]\r
 392         mov edi, [scan]\r
 393         sub eax, edi\r
 394         cmp eax, MAX_MATCH\r
 395         jge LenMaximum\r
 396 \r
 397 ;;; If the length of the match is not longer than the best match we\r
 398 ;;; have so far, then forget it and return to the lookup loop.\r
 399 \r
 400         mov edx, [deflatestate]\r
 401         mov ebx, [bestlen]\r
 402         cmp eax, ebx\r
 403         jg  LongerMatch\r
 404         mov esi, [windowbestlen]\r
 405         mov edi, [edx + dsPrev]\r
 406         mov ebx, [scanend]\r
 407         mov edx, [chainlenwmask]\r
 408         jmp LookupLoop\r
 409 \r
 410 ;;;         s->match_start = cur_match;\r
 411 ;;;         best_len = len;\r
 412 ;;;         if (len >= nice_match) break;\r
 413 ;;;         scan_end = *(ushf*)(scan+best_len-1);\r
 414 \r
 415 LongerMatch:    mov ebx, [nicematch]\r
 416         mov [bestlen], eax\r
 417         mov [edx + dsMatchStart], ecx\r
 418         cmp eax, ebx\r
 419         jge LeaveNow\r
 420         mov esi, [window]\r
 421         add esi, eax\r
 422         mov [windowbestlen], esi\r
 423         movzx   ebx, word ptr [edi + eax - 1]\r
 424         mov edi, [edx + dsPrev]\r
 425         mov [scanend], ebx\r
 426         mov edx, [chainlenwmask]\r
 427         jmp LookupLoop\r
 428 \r
 429 ;;; Accept the current string, with the maximum possible length.\r
 430 \r
 431 LenMaximum: mov edx, [deflatestate]\r
 432         mov dword ptr [bestlen], MAX_MATCH\r
 433         mov [edx + dsMatchStart], ecx\r
 434 \r
 435 ;;; if ((uInt)best_len <= s->lookahead) return (uInt)best_len;\r
 436 ;;; return s->lookahead;\r
 437 \r
 438 LeaveNow:\r
 439         mov edx, [deflatestate]\r
 440         mov ebx, [bestlen]\r
 441         mov eax, [edx + dsLookahead]\r
 442         cmp ebx, eax\r
 443         jg  LookaheadRet\r
 444         mov eax, ebx\r
 445 LookaheadRet:\r
 446 \r
 447 ;;; Restore the stack and return from whence we came.\r
 448 \r
 449         add esp, LocalVarsSize\r
 450         pop ebx\r
 451         pop esi\r
 452         pop edi\r
 453         pop ebp\r
 454 \r
 455         ret\r
 456 ; please don't remove this string !\r
 457 ; Your can freely use match686 in any free or commercial app if you don't remove the string in the binary!\r
 458     db     0dh,0ah,"asm686 with masm, optimised assembly code from Brian Raiter, written 1998",0dh,0ah\r
 459 \r
 460 \r
 461     IFDEF NOUNDERLINE\r
 462     longest_match       endp\r
 463     ELSE\r
 464     _longest_match      endp\r
 465     ENDIF\r
 466 \r
 467     IFDEF NOUNDERLINE\r
 468     match_init      proc near\r
 469                     ret\r
 470     match_init      endp\r
 471     ELSE\r
 472     _match_init     proc near\r
 473                     ret\r
 474     _match_init     endp\r
 475     ENDIF\r
 476 \r
 477 \r
 478 _TEXT   ends\r
 479 end\r