Dependencies/zlib/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 \r
 199 ;;; Save registers that the compiler may be using, and adjust esp to\r
 200 ;;; make room for our stack frame.\r
 201 \r
 202         push    ebp\r
 203         push    edi\r
 204         push    esi\r
 205         push    ebx\r
 206         sub esp, LocalVarsSize\r
 207 \r
 208 ;;; Retrieve the function arguments. ecx will hold cur_match\r
 209 ;;; throughout the entire function. edx will hold the pointer to the\r
 210 ;;; deflate_state structure during the function's setup (before\r
 211 ;;; entering the main loop.\r
 212 \r
 213         mov edx, [deflatestate]\r
 214         mov ecx, [curmatch]\r
 215 \r
 216 ;;; uInt wmask = s->w_mask;\r
 217 ;;; unsigned chain_length = s->max_chain_length;\r
 218 ;;; if (s->prev_length >= s->good_match) {\r
 219 ;;;     chain_length >>= 2;\r
 220 ;;; }\r
 221 \r
 222         mov eax, [edx + dsPrevLen]\r
 223         mov ebx, [edx + dsGoodMatch]\r
 224         cmp eax, ebx\r
 225         mov eax, [edx + dsWMask]\r
 226         mov ebx, [edx + dsMaxChainLen]\r
 227         jl  LastMatchGood\r
 228         shr ebx, 2\r
 229 LastMatchGood:\r
 230 \r
 231 ;;; chainlen is decremented once beforehand so that the function can\r
 232 ;;; use the sign flag instead of the zero flag for the exit test.\r
 233 ;;; It is then shifted into the high word, to make room for the wmask\r
 234 ;;; value, which it will always accompany.\r
 235 \r
 236         dec ebx\r
 237         shl ebx, 16\r
 238         or  ebx, eax\r
 239         mov [chainlenwmask], ebx\r
 240 \r
 241 ;;; if ((uInt)nice_match > s->lookahead) nice_match = s->lookahead;\r
 242 \r
 243         mov eax, [edx + dsNiceMatch]\r
 244         mov ebx, [edx + dsLookahead]\r
 245         cmp ebx, eax\r
 246         jl  LookaheadLess\r
 247         mov ebx, eax\r
 248 LookaheadLess:  mov [nicematch], ebx\r
 249 \r
 250 ;;; register Bytef *scan = s->window + s->strstart;\r
 251 \r
 252         mov esi, [edx + dsWindow]\r
 253         mov [window], esi\r
 254         mov ebp, [edx + dsStrStart]\r
 255         lea edi, [esi + ebp]\r
 256         mov [scan], edi\r
 257 \r
 258 ;;; Determine how many bytes the scan ptr is off from being\r
 259 ;;; dword-aligned.\r
 260 \r
 261         mov eax, edi\r
 262         neg eax\r
 263         and eax, 3\r
 264         mov [scanalign], eax\r
 265 \r
 266 ;;; IPos limit = s->strstart > (IPos)MAX_DIST(s) ?\r
 267 ;;;     s->strstart - (IPos)MAX_DIST(s) : NIL;\r
 268 \r
 269         mov eax, [edx + dsWSize]\r
 270         sub eax, MIN_LOOKAHEAD\r
 271         sub ebp, eax\r
 272         jg  LimitPositive\r
 273         xor ebp, ebp\r
 274 LimitPositive:\r
 275 \r
 276 ;;; int best_len = s->prev_length;\r
 277 \r
 278         mov eax, [edx + dsPrevLen]\r
 279         mov [bestlen], eax\r
 280 \r
 281 ;;; Store the sum of s->window + best_len in esi locally, and in esi.\r
 282 \r
 283         add esi, eax\r
 284         mov [windowbestlen], esi\r
 285 \r
 286 ;;; register ush scan_start = *(ushf*)scan;\r
 287 ;;; register ush scan_end   = *(ushf*)(scan+best_len-1);\r
 288 ;;; Posf *prev = s->prev;\r
 289 \r
 290         movzx   ebx, word ptr [edi]\r
 291         mov [scanstart], ebx\r
 292         movzx   ebx, word ptr [edi + eax - 1]\r
 293         mov [scanend], ebx\r
 294         mov edi, [edx + dsPrev]\r
 295 \r
 296 ;;; Jump into the main loop.\r
 297 \r
 298         mov edx, [chainlenwmask]\r
 299         jmp short LoopEntry\r
 300 \r
 301 align 4\r
 302 \r
 303 ;;; do {\r
 304 ;;;     match = s->window + cur_match;\r
 305 ;;;     if (*(ushf*)(match+best_len-1) != scan_end ||\r
 306 ;;;         *(ushf*)match != scan_start) continue;\r
 307 ;;;     [...]\r
 308 ;;; } while ((cur_match = prev[cur_match & wmask]) > limit\r
 309 ;;;          && --chain_length != 0);\r
 310 ;;;\r
 311 ;;; Here is the inner loop of the function. The function will spend the\r
 312 ;;; majority of its time in this loop, and majority of that time will\r
 313 ;;; be spent in the first ten instructions.\r
 314 ;;;\r
 315 ;;; Within this loop:\r
 316 ;;; ebx = scanend\r
 317 ;;; ecx = curmatch\r
 318 ;;; edx = chainlenwmask - i.e., ((chainlen << 16) | wmask)\r
 319 ;;; esi = windowbestlen - i.e., (window + bestlen)\r
 320 ;;; edi = prev\r
 321 ;;; ebp = limit\r
 322 \r
 323 LookupLoop:\r
 324         and ecx, edx\r
 325         movzx   ecx, word ptr [edi + ecx*2]\r
 326         cmp ecx, ebp\r
 327         jbe LeaveNow\r
 328         sub edx, 00010000h\r
 329         js  LeaveNow\r
 330 LoopEntry:  movzx   eax, word ptr [esi + ecx - 1]\r
 331         cmp eax, ebx\r
 332         jnz LookupLoop\r
 333         mov eax, [window]\r
 334         movzx   eax, word ptr [eax + ecx]\r
 335         cmp eax, [scanstart]\r
 336         jnz LookupLoop\r
 337 \r
 338 ;;; Store the current value of chainlen.\r
 339 \r
 340         mov [chainlenwmask], edx\r
 341 \r
 342 ;;; Point edi to the string under scrutiny, and esi to the string we\r
 343 ;;; are hoping to match it up with. In actuality, esi and edi are\r
 344 ;;; both pointed (MAX_MATCH_8 - scanalign) bytes ahead, and edx is\r
 345 ;;; initialized to -(MAX_MATCH_8 - scanalign).\r
 346 \r
 347         mov esi, [window]\r
 348         mov edi, [scan]\r
 349         add esi, ecx\r
 350         mov eax, [scanalign]\r
 351         mov edx, 0fffffef8h; -(MAX_MATCH_8)\r
 352         lea edi, [edi + eax + 0108h] ;MAX_MATCH_8]\r
 353         lea esi, [esi + eax + 0108h] ;MAX_MATCH_8]\r
 354 \r
 355 ;;; Test the strings for equality, 8 bytes at a time. At the end,\r
 356 ;;; adjust edx so that it is offset to the exact byte that mismatched.\r
 357 ;;;\r
 358 ;;; We already know at this point that the first three bytes of the\r
 359 ;;; strings match each other, and they can be safely passed over before\r
 360 ;;; starting the compare loop. So what this code does is skip over 0-3\r
 361 ;;; bytes, as much as necessary in order to dword-align the edi\r
 362 ;;; pointer. (esi will still be misaligned three times out of four.)\r
 363 ;;;\r
 364 ;;; It should be confessed that this loop usually does not represent\r
 365 ;;; much of the total running time. Replacing it with a more\r
 366 ;;; straightforward "rep cmpsb" would not drastically degrade\r
 367 ;;; performance.\r
 368 \r
 369 LoopCmps:\r
 370         mov eax, [esi + edx]\r
 371         xor eax, [edi + edx]\r
 372         jnz LeaveLoopCmps\r
 373         mov eax, [esi + edx + 4]\r
 374         xor eax, [edi + edx + 4]\r
 375         jnz LeaveLoopCmps4\r
 376         add edx, 8\r
 377         jnz LoopCmps\r
 378         jmp short LenMaximum\r
 379 LeaveLoopCmps4: add edx, 4\r
 380 LeaveLoopCmps:  test    eax, 0000FFFFh\r
 381         jnz LenLower\r
 382         add edx,  2\r
 383         shr eax, 16\r
 384 LenLower:   sub al, 1\r
 385         adc edx, 0\r
 386 \r
 387 ;;; Calculate the length of the match. If it is longer than MAX_MATCH,\r
 388 ;;; then automatically accept it as the best possible match and leave.\r
 389 \r
 390         lea eax, [edi + edx]\r
 391         mov edi, [scan]\r
 392         sub eax, edi\r
 393         cmp eax, MAX_MATCH\r
 394         jge LenMaximum\r
 395 \r
 396 ;;; If the length of the match is not longer than the best match we\r
 397 ;;; have so far, then forget it and return to the lookup loop.\r
 398 \r
 399         mov edx, [deflatestate]\r
 400         mov ebx, [bestlen]\r
 401         cmp eax, ebx\r
 402         jg  LongerMatch\r
 403         mov esi, [windowbestlen]\r
 404         mov edi, [edx + dsPrev]\r
 405         mov ebx, [scanend]\r
 406         mov edx, [chainlenwmask]\r
 407         jmp LookupLoop\r
 408 \r
 409 ;;;         s->match_start = cur_match;\r
 410 ;;;         best_len = len;\r
 411 ;;;         if (len >= nice_match) break;\r
 412 ;;;         scan_end = *(ushf*)(scan+best_len-1);\r
 413 \r
 414 LongerMatch:    mov ebx, [nicematch]\r
 415         mov [bestlen], eax\r
 416         mov [edx + dsMatchStart], ecx\r
 417         cmp eax, ebx\r
 418         jge LeaveNow\r
 419         mov esi, [window]\r
 420         add esi, eax\r
 421         mov [windowbestlen], esi\r
 422         movzx   ebx, word ptr [edi + eax - 1]\r
 423         mov edi, [edx + dsPrev]\r
 424         mov [scanend], ebx\r
 425         mov edx, [chainlenwmask]\r
 426         jmp LookupLoop\r
 427 \r
 428 ;;; Accept the current string, with the maximum possible length.\r
 429 \r
 430 LenMaximum: mov edx, [deflatestate]\r
 431         mov dword ptr [bestlen], MAX_MATCH\r
 432         mov [edx + dsMatchStart], ecx\r
 433 \r
 434 ;;; if ((uInt)best_len <= s->lookahead) return (uInt)best_len;\r
 435 ;;; return s->lookahead;\r
 436 \r
 437 LeaveNow:\r
 438         mov edx, [deflatestate]\r
 439         mov ebx, [bestlen]\r
 440         mov eax, [edx + dsLookahead]\r
 441         cmp ebx, eax\r
 442         jg  LookaheadRet\r
 443         mov eax, ebx\r
 444 LookaheadRet:\r
 445 \r
 446 ;;; Restore the stack and return from whence we came.\r
 447 \r
 448         add esp, LocalVarsSize\r
 449         pop ebx\r
 450         pop esi\r
 451         pop edi\r
 452         pop ebp\r
 453 \r
 454         ret\r
 455 ; please don't remove this string !\r
 456 ; Your can freely use match686 in any free or commercial app if you don't remove the string in the binary!\r
 457     db     0dh,0ah,"asm686 with masm, optimised assembly code from Brian Raiter, written 1998",0dh,0ah\r
 458 \r
 459 \r
 460     IFDEF NOUNDERLINE\r
 461     longest_match       endp\r
 462     ELSE\r
 463     _longest_match      endp\r
 464     ENDIF\r
 465 \r
 466     IFDEF NOUNDERLINE\r
 467     match_init      proc near\r
 468                     ret\r
 469     match_init      endp\r
 470     ELSE\r
 471     _match_init     proc near\r
 472                     ret\r
 473     _match_init     endp\r
 474     ENDIF\r
 475 \r
 476 \r
 477 _TEXT   ends\r
 478 end\r