| 1 |
|
|---|
| 2 | ; match.asm -- Pentium-Pro optimized version of longest_match()
|
|---|
| 3 | ;
|
|---|
| 4 | ; Updated for zlib 1.1.3 and converted to MASM 6.1x
|
|---|
| 5 | ; Copyright (C) 2000 Dan Higdon <hdan@kinesoft.com>
|
|---|
| 6 | ; and Chuck Walbourn <chuckw@kinesoft.com>
|
|---|
| 7 | ; Corrections by Cosmin Truta <cosmint@cs.ubbcluj.ro>
|
|---|
| 8 | ;
|
|---|
| 9 | ; This is free software; you can redistribute it and/or modify it
|
|---|
| 10 | ; under the terms of the GNU General Public License.
|
|---|
| 11 |
|
|---|
| 12 | ; Based on match.S
|
|---|
| 13 | ; Written for zlib 1.1.2
|
|---|
| 14 | ; Copyright (C) 1998 Brian Raiter <breadbox@muppetlabs.com>
|
|---|
| 15 | ;
|
|---|
| 16 | ; Modified by Gilles Vollant (2005) for add gzhead and gzindex
|
|---|
| 17 |
|
|---|
| 18 | .686P
|
|---|
| 19 | .MODEL FLAT
|
|---|
| 20 |
|
|---|
| 21 | ;===========================================================================
|
|---|
| 22 | ; EQUATES
|
|---|
| 23 | ;===========================================================================
|
|---|
| 24 |
|
|---|
| 25 | MAX_MATCH EQU 258
|
|---|
| 26 | MIN_MATCH EQU 3
|
|---|
| 27 | MIN_LOOKAHEAD EQU (MAX_MATCH + MIN_MATCH + 1)
|
|---|
| 28 | MAX_MATCH_8 EQU ((MAX_MATCH + 7) AND (NOT 7))
|
|---|
| 29 |
|
|---|
| 30 | ;===========================================================================
|
|---|
| 31 | ; STRUCTURES
|
|---|
| 32 | ;===========================================================================
|
|---|
| 33 |
|
|---|
| 34 | ; This STRUCT assumes a 4-byte alignment
|
|---|
| 35 |
|
|---|
| 36 | DEFLATE_STATE STRUCT
|
|---|
| 37 | ds_strm dd ?
|
|---|
| 38 | ds_status dd ?
|
|---|
| 39 | ds_pending_buf dd ?
|
|---|
| 40 | ds_pending_buf_size dd ?
|
|---|
| 41 | ds_pending_out dd ?
|
|---|
| 42 | ds_pending dd ?
|
|---|
| 43 | ds_wrap dd ?
|
|---|
| 44 | ; gzhead and gzindex are added in zlib 1.2.2.2 (see deflate.h)
|
|---|
| 45 | ds_gzhead dd ?
|
|---|
| 46 | ds_gzindex dd ?
|
|---|
| 47 | ds_data_type db ?
|
|---|
| 48 | ds_method db ?
|
|---|
| 49 | db ? ; padding
|
|---|
| 50 | db ? ; padding
|
|---|
| 51 | ds_last_flush dd ?
|
|---|
| 52 | ds_w_size dd ? ; used
|
|---|
| 53 | ds_w_bits dd ?
|
|---|
| 54 | ds_w_mask dd ? ; used
|
|---|
| 55 | ds_window dd ? ; used
|
|---|
| 56 | ds_window_size dd ?
|
|---|
| 57 | ds_prev dd ? ; used
|
|---|
| 58 | ds_head dd ?
|
|---|
| 59 | ds_ins_h dd ?
|
|---|
| 60 | ds_hash_size dd ?
|
|---|
| 61 | ds_hash_bits dd ?
|
|---|
| 62 | ds_hash_mask dd ?
|
|---|
| 63 | ds_hash_shift dd ?
|
|---|
| 64 | ds_block_start dd ?
|
|---|
| 65 | ds_match_length dd ? ; used
|
|---|
| 66 | ds_prev_match dd ? ; used
|
|---|
| 67 | ds_match_available dd ?
|
|---|
| 68 | ds_strstart dd ? ; used
|
|---|
| 69 | ds_match_start dd ? ; used
|
|---|
| 70 | ds_lookahead dd ? ; used
|
|---|
| 71 | ds_prev_length dd ? ; used
|
|---|
| 72 | ds_max_chain_length dd ? ; used
|
|---|
| 73 | ds_max_laxy_match dd ?
|
|---|
| 74 | ds_level dd ?
|
|---|
| 75 | ds_strategy dd ?
|
|---|
| 76 | ds_good_match dd ? ; used
|
|---|
| 77 | ds_nice_match dd ? ; used
|
|---|
| 78 |
|
|---|
| 79 | ; Don't need anymore of the struct for match
|
|---|
| 80 | DEFLATE_STATE ENDS
|
|---|
| 81 |
|
|---|
| 82 | ;===========================================================================
|
|---|
| 83 | ; CODE
|
|---|
| 84 | ;===========================================================================
|
|---|
| 85 | _TEXT SEGMENT
|
|---|
| 86 |
|
|---|
| 87 | ;---------------------------------------------------------------------------
|
|---|
| 88 | ; match_init
|
|---|
| 89 | ;---------------------------------------------------------------------------
|
|---|
| 90 | ALIGN 4
|
|---|
| 91 | PUBLIC _match_init
|
|---|
| 92 | _match_init PROC
|
|---|
| 93 | ; no initialization needed
|
|---|
| 94 | ret
|
|---|
| 95 | _match_init ENDP
|
|---|
| 96 |
|
|---|
| 97 | ;---------------------------------------------------------------------------
|
|---|
| 98 | ; uInt longest_match(deflate_state *deflatestate, IPos curmatch)
|
|---|
| 99 | ;---------------------------------------------------------------------------
|
|---|
| 100 | ALIGN 4
|
|---|
| 101 |
|
|---|
| 102 | PUBLIC _longest_match
|
|---|
| 103 | _longest_match PROC
|
|---|
| 104 |
|
|---|
| 105 | ; Since this code uses EBP for a scratch register, the stack frame must
|
|---|
| 106 | ; be manually constructed and referenced relative to the ESP register.
|
|---|
| 107 |
|
|---|
| 108 | ; Stack image
|
|---|
| 109 | ; Variables
|
|---|
| 110 | chainlenwmask = 0 ; high word: current chain len
|
|---|
| 111 | ; low word: s->wmask
|
|---|
| 112 | window = 4 ; local copy of s->window
|
|---|
| 113 | windowbestlen = 8 ; s->window + bestlen
|
|---|
| 114 | scanend = 12 ; last two bytes of string
|
|---|
| 115 | scanstart = 16 ; first two bytes of string
|
|---|
| 116 | scanalign = 20 ; dword-misalignment of string
|
|---|
| 117 | nicematch = 24 ; a good enough match size
|
|---|
| 118 | bestlen = 28 ; size of best match so far
|
|---|
| 119 | scan = 32 ; ptr to string wanting match
|
|---|
| 120 | varsize = 36 ; number of bytes (also offset to last saved register)
|
|---|
| 121 |
|
|---|
| 122 | ; Saved Registers (actually pushed into place)
|
|---|
| 123 | ebx_save = 36
|
|---|
| 124 | edi_save = 40
|
|---|
| 125 | esi_save = 44
|
|---|
| 126 | ebp_save = 48
|
|---|
| 127 |
|
|---|
| 128 | ; Parameters
|
|---|
| 129 | retaddr = 52
|
|---|
| 130 | deflatestate = 56
|
|---|
| 131 | curmatch = 60
|
|---|
| 132 |
|
|---|
| 133 | ; Save registers that the compiler may be using
|
|---|
| 134 | push ebp
|
|---|
| 135 | push edi
|
|---|
| 136 | push esi
|
|---|
| 137 | push ebx
|
|---|
| 138 |
|
|---|
| 139 | ; Allocate local variable space
|
|---|
| 140 | sub esp,varsize
|
|---|
| 141 |
|
|---|
| 142 | ; Retrieve the function arguments. ecx will hold cur_match
|
|---|
| 143 | ; throughout the entire function. edx will hold the pointer to the
|
|---|
| 144 | ; deflate_state structure during the function's setup (before
|
|---|
| 145 | ; entering the main loop).
|
|---|
| 146 |
|
|---|
| 147 | mov edx, [esp+deflatestate]
|
|---|
| 148 | ASSUME edx:PTR DEFLATE_STATE
|
|---|
| 149 |
|
|---|
| 150 | mov ecx, [esp+curmatch]
|
|---|
| 151 |
|
|---|
| 152 | ; uInt wmask = s->w_mask;
|
|---|
| 153 | ; unsigned chain_length = s->max_chain_length;
|
|---|
| 154 | ; if (s->prev_length >= s->good_match) {
|
|---|
| 155 | ; chain_length >>= 2;
|
|---|
| 156 | ; }
|
|---|
| 157 |
|
|---|
| 158 | mov eax, [edx].ds_prev_length
|
|---|
| 159 | mov ebx, [edx].ds_good_match
|
|---|
| 160 | cmp eax, ebx
|
|---|
| 161 | mov eax, [edx].ds_w_mask
|
|---|
| 162 | mov ebx, [edx].ds_max_chain_length
|
|---|
| 163 | jl SHORT LastMatchGood
|
|---|
| 164 | shr ebx, 2
|
|---|
| 165 | LastMatchGood:
|
|---|
| 166 |
|
|---|
| 167 | ; chainlen is decremented once beforehand so that the function can
|
|---|
| 168 | ; use the sign flag instead of the zero flag for the exit test.
|
|---|
| 169 | ; It is then shifted into the high word, to make room for the wmask
|
|---|
| 170 | ; value, which it will always accompany.
|
|---|
| 171 |
|
|---|
| 172 | dec ebx
|
|---|
| 173 | shl ebx, 16
|
|---|
| 174 | or ebx, eax
|
|---|
| 175 | mov [esp+chainlenwmask], ebx
|
|---|
| 176 |
|
|---|
| 177 | ; if ((uInt)nice_match > s->lookahead) nice_match = s->lookahead;
|
|---|
| 178 |
|
|---|
| 179 | mov eax, [edx].ds_nice_match
|
|---|
| 180 | mov ebx, [edx].ds_lookahead
|
|---|
| 181 | cmp ebx, eax
|
|---|
| 182 | jl SHORT LookaheadLess
|
|---|
| 183 | mov ebx, eax
|
|---|
| 184 | LookaheadLess:
|
|---|
| 185 | mov [esp+nicematch], ebx
|
|---|
| 186 |
|
|---|
| 187 | ;/* register Bytef *scan = s->window + s->strstart; */
|
|---|
| 188 |
|
|---|
| 189 | mov esi, [edx].ds_window
|
|---|
| 190 | mov [esp+window], esi
|
|---|
| 191 | mov ebp, [edx].ds_strstart
|
|---|
| 192 | lea edi, [esi+ebp]
|
|---|
| 193 | mov [esp+scan],edi
|
|---|
| 194 |
|
|---|
| 195 | ;/* Determine how many bytes the scan ptr is off from being */
|
|---|
| 196 | ;/* dword-aligned. */
|
|---|
| 197 |
|
|---|
| 198 | mov eax, edi
|
|---|
| 199 | neg eax
|
|---|
| 200 | and eax, 3
|
|---|
| 201 | mov [esp+scanalign], eax
|
|---|
| 202 |
|
|---|
| 203 | ;/* IPos limit = s->strstart > (IPos)MAX_DIST(s) ? */
|
|---|
| 204 | ;/* s->strstart - (IPos)MAX_DIST(s) : NIL; */
|
|---|
| 205 |
|
|---|
| 206 | mov eax, [edx].ds_w_size
|
|---|
| 207 | sub eax, MIN_LOOKAHEAD
|
|---|
| 208 | sub ebp, eax
|
|---|
| 209 | jg SHORT LimitPositive
|
|---|
| 210 | xor ebp, ebp
|
|---|
| 211 | LimitPositive:
|
|---|
| 212 |
|
|---|
| 213 | ;/* int best_len = s->prev_length; */
|
|---|
| 214 |
|
|---|
| 215 | mov eax, [edx].ds_prev_length
|
|---|
| 216 | mov [esp+bestlen], eax
|
|---|
| 217 |
|
|---|
| 218 | ;/* Store the sum of s->window + best_len in %esi locally, and in %esi. */
|
|---|
| 219 |
|
|---|
| 220 | add esi, eax
|
|---|
| 221 | mov [esp+windowbestlen], esi
|
|---|
| 222 |
|
|---|
| 223 | ;/* register ush scan_start = *(ushf*)scan; */
|
|---|
| 224 | ;/* register ush scan_end = *(ushf*)(scan+best_len-1); */
|
|---|
| 225 | ;/* Posf *prev = s->prev; */
|
|---|
| 226 |
|
|---|
| 227 | movzx ebx, WORD PTR[edi]
|
|---|
| 228 | mov [esp+scanstart], ebx
|
|---|
| 229 | movzx ebx, WORD PTR[eax+edi-1]
|
|---|
| 230 | mov [esp+scanend], ebx
|
|---|
| 231 | mov edi, [edx].ds_prev
|
|---|
| 232 |
|
|---|
| 233 | ;/* Jump into the main loop. */
|
|---|
| 234 |
|
|---|
| 235 | mov edx, [esp+chainlenwmask]
|
|---|
| 236 | jmp SHORT LoopEntry
|
|---|
| 237 |
|
|---|
| 238 | ;/* do {
|
|---|
| 239 | ; * match = s->window + cur_match;
|
|---|
| 240 | ; * if (*(ushf*)(match+best_len-1) != scan_end ||
|
|---|
| 241 | ; * *(ushf*)match != scan_start) continue;
|
|---|
| 242 | ; * [...]
|
|---|
| 243 | ; * } while ((cur_match = prev[cur_match & wmask]) > limit
|
|---|
| 244 | ; * && --chain_length != 0);
|
|---|
| 245 | ; *
|
|---|
| 246 | ; * Here is the inner loop of the function. The function will spend the
|
|---|
| 247 | ; * majority of its time in this loop, and majority of that time will
|
|---|
| 248 | ; * be spent in the first ten instructions.
|
|---|
| 249 | ; *
|
|---|
| 250 | ; * Within this loop:
|
|---|
| 251 | ; * %ebx = scanend
|
|---|
| 252 | ; * %ecx = curmatch
|
|---|
| 253 | ; * %edx = chainlenwmask - i.e., ((chainlen << 16) | wmask)
|
|---|
| 254 | ; * %esi = windowbestlen - i.e., (window + bestlen)
|
|---|
| 255 | ; * %edi = prev
|
|---|
| 256 | ; * %ebp = limit
|
|---|
| 257 | ; */
|
|---|
| 258 |
|
|---|
| 259 | ALIGN 4
|
|---|
| 260 | LookupLoop:
|
|---|
| 261 | and ecx, edx
|
|---|
| 262 | movzx ecx, WORD PTR[edi+ecx*2]
|
|---|
| 263 | cmp ecx, ebp
|
|---|
| 264 | jbe LeaveNow
|
|---|
| 265 | sub edx, 000010000H
|
|---|
| 266 | js LeaveNow
|
|---|
| 267 |
|
|---|
| 268 | LoopEntry:
|
|---|
| 269 | movzx eax, WORD PTR[esi+ecx-1]
|
|---|
| 270 | cmp eax, ebx
|
|---|
| 271 | jnz SHORT LookupLoop
|
|---|
| 272 |
|
|---|
| 273 | mov eax, [esp+window]
|
|---|
| 274 | movzx eax, WORD PTR[eax+ecx]
|
|---|
| 275 | cmp eax, [esp+scanstart]
|
|---|
| 276 | jnz SHORT LookupLoop
|
|---|
| 277 |
|
|---|
| 278 | ;/* Store the current value of chainlen. */
|
|---|
| 279 |
|
|---|
| 280 | mov [esp+chainlenwmask], edx
|
|---|
| 281 |
|
|---|
| 282 | ;/* Point %edi to the string under scrutiny, and %esi to the string we */
|
|---|
| 283 | ;/* are hoping to match it up with. In actuality, %esi and %edi are */
|
|---|
| 284 | ;/* both pointed (MAX_MATCH_8 - scanalign) bytes ahead, and %edx is */
|
|---|
| 285 | ;/* initialized to -(MAX_MATCH_8 - scanalign). */
|
|---|
| 286 |
|
|---|
| 287 | mov esi, [esp+window]
|
|---|
| 288 | mov edi, [esp+scan]
|
|---|
| 289 | add esi, ecx
|
|---|
| 290 | mov eax, [esp+scanalign]
|
|---|
| 291 | mov edx, -MAX_MATCH_8
|
|---|
| 292 | lea edi, [edi+eax+MAX_MATCH_8]
|
|---|
| 293 | lea esi, [esi+eax+MAX_MATCH_8]
|
|---|
| 294 |
|
|---|
| 295 | ;/* Test the strings for equality, 8 bytes at a time. At the end,
|
|---|
| 296 | ; * adjust %edx so that it is offset to the exact byte that mismatched.
|
|---|
| 297 | ; *
|
|---|
| 298 | ; * We already know at this point that the first three bytes of the
|
|---|
| 299 | ; * strings match each other, and they can be safely passed over before
|
|---|
| 300 | ; * starting the compare loop. So what this code does is skip over 0-3
|
|---|
| 301 | ; * bytes, as much as necessary in order to dword-align the %edi
|
|---|
| 302 | ; * pointer. (%esi will still be misaligned three times out of four.)
|
|---|
| 303 | ; *
|
|---|
| 304 | ; * It should be confessed that this loop usually does not represent
|
|---|
| 305 | ; * much of the total running time. Replacing it with a more
|
|---|
| 306 | ; * straightforward "rep cmpsb" would not drastically degrade
|
|---|
| 307 | ; * performance.
|
|---|
| 308 | ; */
|
|---|
| 309 |
|
|---|
| 310 | LoopCmps:
|
|---|
| 311 | mov eax, DWORD PTR[esi+edx]
|
|---|
| 312 | xor eax, DWORD PTR[edi+edx]
|
|---|
| 313 | jnz SHORT LeaveLoopCmps
|
|---|
| 314 |
|
|---|
| 315 | mov eax, DWORD PTR[esi+edx+4]
|
|---|
| 316 | xor eax, DWORD PTR[edi+edx+4]
|
|---|
| 317 | jnz SHORT LeaveLoopCmps4
|
|---|
| 318 |
|
|---|
| 319 | add edx, 8
|
|---|
| 320 | jnz SHORT LoopCmps
|
|---|
| 321 | jmp LenMaximum
|
|---|
| 322 | ALIGN 4
|
|---|
| 323 |
|
|---|
| 324 | LeaveLoopCmps4:
|
|---|
| 325 | add edx, 4
|
|---|
| 326 |
|
|---|
| 327 | LeaveLoopCmps:
|
|---|
| 328 | test eax, 00000FFFFH
|
|---|
| 329 | jnz SHORT LenLower
|
|---|
| 330 |
|
|---|
| 331 | add edx, 2
|
|---|
| 332 | shr eax, 16
|
|---|
| 333 |
|
|---|
| 334 | LenLower:
|
|---|
| 335 | sub al, 1
|
|---|
| 336 | adc edx, 0
|
|---|
| 337 |
|
|---|
| 338 | ;/* Calculate the length of the match. If it is longer than MAX_MATCH, */
|
|---|
| 339 | ;/* then automatically accept it as the best possible match and leave. */
|
|---|
| 340 |
|
|---|
| 341 | lea eax, [edi+edx]
|
|---|
| 342 | mov edi, [esp+scan]
|
|---|
| 343 | sub eax, edi
|
|---|
| 344 | cmp eax, MAX_MATCH
|
|---|
| 345 | jge SHORT LenMaximum
|
|---|
| 346 |
|
|---|
| 347 | ;/* If the length of the match is not longer than the best match we */
|
|---|
| 348 | ;/* have so far, then forget it and return to the lookup loop. */
|
|---|
| 349 |
|
|---|
| 350 | mov edx, [esp+deflatestate]
|
|---|
| 351 | mov ebx, [esp+bestlen]
|
|---|
| 352 | cmp eax, ebx
|
|---|
| 353 | jg SHORT LongerMatch
|
|---|
| 354 | mov esi, [esp+windowbestlen]
|
|---|
| 355 | mov edi, [edx].ds_prev
|
|---|
| 356 | mov ebx, [esp+scanend]
|
|---|
| 357 | mov edx, [esp+chainlenwmask]
|
|---|
| 358 | jmp LookupLoop
|
|---|
| 359 | ALIGN 4
|
|---|
| 360 |
|
|---|
| 361 | ;/* s->match_start = cur_match; */
|
|---|
| 362 | ;/* best_len = len; */
|
|---|
| 363 | ;/* if (len >= nice_match) break; */
|
|---|
| 364 | ;/* scan_end = *(ushf*)(scan+best_len-1); */
|
|---|
| 365 |
|
|---|
| 366 | LongerMatch:
|
|---|
| 367 | mov ebx, [esp+nicematch]
|
|---|
| 368 | mov [esp+bestlen], eax
|
|---|
| 369 | mov [edx].ds_match_start, ecx
|
|---|
| 370 | cmp eax, ebx
|
|---|
| 371 | jge SHORT LeaveNow
|
|---|
| 372 | mov esi, [esp+window]
|
|---|
| 373 | add esi, eax
|
|---|
| 374 | mov [esp+windowbestlen], esi
|
|---|
| 375 | movzx ebx, WORD PTR[edi+eax-1]
|
|---|
| 376 | mov edi, [edx].ds_prev
|
|---|
| 377 | mov [esp+scanend], ebx
|
|---|
| 378 | mov edx, [esp+chainlenwmask]
|
|---|
| 379 | jmp LookupLoop
|
|---|
| 380 | ALIGN 4
|
|---|
| 381 |
|
|---|
| 382 | ;/* Accept the current string, with the maximum possible length. */
|
|---|
| 383 |
|
|---|
| 384 | LenMaximum:
|
|---|
| 385 | mov edx, [esp+deflatestate]
|
|---|
| 386 | mov DWORD PTR[esp+bestlen], MAX_MATCH
|
|---|
| 387 | mov [edx].ds_match_start, ecx
|
|---|
| 388 |
|
|---|
| 389 | ;/* if ((uInt)best_len <= s->lookahead) return (uInt)best_len; */
|
|---|
| 390 | ;/* return s->lookahead; */
|
|---|
| 391 |
|
|---|
| 392 | LeaveNow:
|
|---|
| 393 | mov edx, [esp+deflatestate]
|
|---|
| 394 | mov ebx, [esp+bestlen]
|
|---|
| 395 | mov eax, [edx].ds_lookahead
|
|---|
| 396 | cmp ebx, eax
|
|---|
| 397 | jg SHORT LookaheadRet
|
|---|
| 398 | mov eax, ebx
|
|---|
| 399 | LookaheadRet:
|
|---|
| 400 |
|
|---|
| 401 | ; Restore the stack and return from whence we came.
|
|---|
| 402 |
|
|---|
| 403 | add esp, varsize
|
|---|
| 404 | pop ebx
|
|---|
| 405 | pop esi
|
|---|
| 406 | pop edi
|
|---|
| 407 | pop ebp
|
|---|
| 408 | ret
|
|---|
| 409 |
|
|---|
| 410 | _longest_match ENDP
|
|---|
| 411 |
|
|---|
| 412 | _TEXT ENDS
|
|---|
| 413 | END
|
|---|
