| ; match.asm -- Pentium-Pro optimized version of longest_match() | |
| ; | |
| ; Updated for zlib 1.1.3 and converted to MASM 6.1x | |
| ; Copyright (C) 2000 Dan Higdon <hdan@kinesoft.com> | |
| ; and Chuck Walbourn <chuckw@kinesoft.com> | |
| ; Corrections by Cosmin Truta <cosmint@cs.ubbcluj.ro> | |
| ; | |
| ; This is free software; you can redistribute it and/or modify it | |
| ; under the terms of the GNU General Public License. | |
| ; Based on match.S | |
| ; Written for zlib 1.1.2 | |
| ; Copyright (C) 1998 Brian Raiter <breadbox@muppetlabs.com> | |
| ; | |
| ; Modified by Gilles Vollant (2005) for add gzhead and gzindex | |
| .686P | |
| .MODEL FLAT | |
| ;=========================================================================== | |
| ; EQUATES | |
| ;=========================================================================== | |
| MAX_MATCH EQU 258 | |
| MIN_MATCH EQU 3 | |
| MIN_LOOKAHEAD EQU (MAX_MATCH + MIN_MATCH + 1) | |
| MAX_MATCH_8 EQU ((MAX_MATCH + 7) AND (NOT 7)) | |
| ;=========================================================================== | |
| ; STRUCTURES | |
| ;=========================================================================== | |
| ; This STRUCT assumes a 4-byte alignment | |
| DEFLATE_STATE STRUCT | |
| ds_strm dd ? | |
| ds_status dd ? | |
| ds_pending_buf dd ? | |
| ds_pending_buf_size dd ? | |
| ds_pending_out dd ? | |
| ds_pending dd ? | |
| ds_wrap dd ? | |
| ; gzhead and gzindex are added in zlib 1.2.2.2 (see deflate.h) | |
| ds_gzhead dd ? | |
| ds_gzindex dd ? | |
| ds_data_type db ? | |
| ds_method db ? | |
| db ? ; padding | |
| db ? ; padding | |
| ds_last_flush dd ? | |
| ds_w_size dd ? ; used | |
| ds_w_bits dd ? | |
| ds_w_mask dd ? ; used | |
| ds_window dd ? ; used | |
| ds_window_size dd ? | |
| ds_prev dd ? ; used | |
| ds_head dd ? | |
| ds_ins_h dd ? | |
| ds_hash_size dd ? | |
| ds_hash_bits dd ? | |
| ds_hash_mask dd ? | |
| ds_hash_shift dd ? | |
| ds_block_start dd ? | |
| ds_match_length dd ? ; used | |
| ds_prev_match dd ? ; used | |
| ds_match_available dd ? | |
| ds_strstart dd ? ; used | |
| ds_match_start dd ? ; used | |
| ds_lookahead dd ? ; used | |
| ds_prev_length dd ? ; used | |
| ds_max_chain_length dd ? ; used | |
| ds_max_laxy_match dd ? | |
| ds_level dd ? | |
| ds_strategy dd ? | |
| ds_good_match dd ? ; used | |
| ds_nice_match dd ? ; used | |
| ; Don't need anymore of the struct for match | |
| DEFLATE_STATE ENDS | |
| ;=========================================================================== | |
| ; CODE | |
| ;=========================================================================== | |
| _TEXT SEGMENT | |
| ;--------------------------------------------------------------------------- | |
| ; match_init | |
| ;--------------------------------------------------------------------------- | |
| ALIGN 4 | |
| PUBLIC _match_init | |
| _match_init PROC | |
| ; no initialization needed | |
| ret | |
| _match_init ENDP | |
| ;--------------------------------------------------------------------------- | |
| ; uInt longest_match(deflate_state *deflatestate, IPos curmatch) | |
| ;--------------------------------------------------------------------------- | |
| ALIGN 4 | |
| PUBLIC _longest_match | |
| _longest_match PROC | |
| ; Since this code uses EBP for a scratch register, the stack frame must | |
| ; be manually constructed and referenced relative to the ESP register. | |
| ; Stack image | |
| ; Variables | |
| chainlenwmask = 0 ; high word: current chain len | |
| ; low word: s->wmask | |
| window = 4 ; local copy of s->window | |
| windowbestlen = 8 ; s->window + bestlen | |
| scanend = 12 ; last two bytes of string | |
| scanstart = 16 ; first two bytes of string | |
| scanalign = 20 ; dword-misalignment of string | |
| nicematch = 24 ; a good enough match size | |
| bestlen = 28 ; size of best match so far | |
| scan = 32 ; ptr to string wanting match | |
| varsize = 36 ; number of bytes (also offset to last saved register) | |
| ; Saved Registers (actually pushed into place) | |
| ebx_save = 36 | |
| edi_save = 40 | |
| esi_save = 44 | |
| ebp_save = 48 | |
| ; Parameters | |
| retaddr = 52 | |
| deflatestate = 56 | |
| curmatch = 60 | |
| ; Save registers that the compiler may be using | |
| push ebp | |
| push edi | |
| push esi | |
| push ebx | |
| ; Allocate local variable space | |
| sub esp,varsize | |
| ; Retrieve the function arguments. ecx will hold cur_match | |
| ; throughout the entire function. edx will hold the pointer to the | |
| ; deflate_state structure during the function's setup (before | |
| ; entering the main loop). | |
| mov edx, [esp+deflatestate] | |
| ASSUME edx:PTR DEFLATE_STATE | |
| mov ecx, [esp+curmatch] | |
| ; uInt wmask = s->w_mask; | |
| ; unsigned chain_length = s->max_chain_length; | |
| ; if (s->prev_length >= s->good_match) { | |
| ; chain_length >>= 2; | |
| ; } | |
| mov eax, [edx].ds_prev_length | |
| mov ebx, [edx].ds_good_match | |
| cmp eax, ebx | |
| mov eax, [edx].ds_w_mask | |
| mov ebx, [edx].ds_max_chain_length | |
| jl SHORT LastMatchGood | |
| shr ebx, 2 | |
| LastMatchGood: | |
| ; chainlen is decremented once beforehand so that the function can | |
| ; use the sign flag instead of the zero flag for the exit test. | |
| ; It is then shifted into the high word, to make room for the wmask | |
| ; value, which it will always accompany. | |
| dec ebx | |
| shl ebx, 16 | |
| or ebx, eax | |
| mov [esp+chainlenwmask], ebx | |
| ; if ((uInt)nice_match > s->lookahead) nice_match = s->lookahead; | |
| mov eax, [edx].ds_nice_match | |
| mov ebx, [edx].ds_lookahead | |
| cmp ebx, eax | |
| jl SHORT LookaheadLess | |
| mov ebx, eax | |
| LookaheadLess: | |
| mov [esp+nicematch], ebx | |
| ;/* register Bytef *scan = s->window + s->strstart; */ | |
| mov esi, [edx].ds_window | |
| mov [esp+window], esi | |
| mov ebp, [edx].ds_strstart | |
| lea edi, [esi+ebp] | |
| mov [esp+scan],edi | |
| ;/* Determine how many bytes the scan ptr is off from being */ | |
| ;/* dword-aligned. */ | |
| mov eax, edi | |
| neg eax | |
| and eax, 3 | |
| mov [esp+scanalign], eax | |
| ;/* IPos limit = s->strstart > (IPos)MAX_DIST(s) ? */ | |
| ;/* s->strstart - (IPos)MAX_DIST(s) : NIL; */ | |
| mov eax, [edx].ds_w_size | |
| sub eax, MIN_LOOKAHEAD | |
| sub ebp, eax | |
| jg SHORT LimitPositive | |
| xor ebp, ebp | |
| LimitPositive: | |
| ;/* int best_len = s->prev_length; */ | |
| mov eax, [edx].ds_prev_length | |
| mov [esp+bestlen], eax | |
| ;/* Store the sum of s->window + best_len in %esi locally, and in %esi. */ | |
| add esi, eax | |
| mov [esp+windowbestlen], esi | |
| ;/* register ush scan_start = *(ushf*)scan; */ | |
| ;/* register ush scan_end = *(ushf*)(scan+best_len-1); */ | |
| ;/* Posf *prev = s->prev; */ | |
| movzx ebx, WORD PTR[edi] | |
| mov [esp+scanstart], ebx | |
| movzx ebx, WORD PTR[eax+edi-1] | |
| mov [esp+scanend], ebx | |
| mov edi, [edx].ds_prev | |
| ;/* Jump into the main loop. */ | |
| mov edx, [esp+chainlenwmask] | |
| jmp SHORT LoopEntry | |
| ;/* do { | |
| ; * match = s->window + cur_match; | |
| ; * if (*(ushf*)(match+best_len-1) != scan_end || | |
| ; * *(ushf*)match != scan_start) continue; | |
| ; * [...] | |
| ; * } while ((cur_match = prev[cur_match & wmask]) > limit | |
| ; * && --chain_length != 0); | |
| ; * | |
| ; * Here is the inner loop of the function. The function will spend the | |
| ; * majority of its time in this loop, and majority of that time will | |
| ; * be spent in the first ten instructions. | |
| ; * | |
| ; * Within this loop: | |
| ; * %ebx = scanend | |
| ; * %ecx = curmatch | |
| ; * %edx = chainlenwmask - i.e., ((chainlen << 16) | wmask) | |
| ; * %esi = windowbestlen - i.e., (window + bestlen) | |
| ; * %edi = prev | |
| ; * %ebp = limit | |
| ; */ | |
| ALIGN 4 | |
| LookupLoop: | |
| and ecx, edx | |
| movzx ecx, WORD PTR[edi+ecx*2] | |
| cmp ecx, ebp | |
| jbe LeaveNow | |
| sub edx, 000010000H | |
| js LeaveNow | |
| LoopEntry: | |
| movzx eax, WORD PTR[esi+ecx-1] | |
| cmp eax, ebx | |
| jnz SHORT LookupLoop | |
| mov eax, [esp+window] | |
| movzx eax, WORD PTR[eax+ecx] | |
| cmp eax, [esp+scanstart] | |
| jnz SHORT LookupLoop | |
| ;/* Store the current value of chainlen. */ | |
| mov [esp+chainlenwmask], edx | |
| ;/* Point %edi to the string under scrutiny, and %esi to the string we */ | |
| ;/* are hoping to match it up with. In actuality, %esi and %edi are */ | |
| ;/* both pointed (MAX_MATCH_8 - scanalign) bytes ahead, and %edx is */ | |
| ;/* initialized to -(MAX_MATCH_8 - scanalign). */ | |
| mov esi, [esp+window] | |
| mov edi, [esp+scan] | |
| add esi, ecx | |
| mov eax, [esp+scanalign] | |
| mov edx, -MAX_MATCH_8 | |
| lea edi, [edi+eax+MAX_MATCH_8] | |
| lea esi, [esi+eax+MAX_MATCH_8] | |
| ;/* Test the strings for equality, 8 bytes at a time. At the end, | |
| ; * adjust %edx so that it is offset to the exact byte that mismatched. | |
| ; * | |
| ; * We already know at this point that the first three bytes of the | |
| ; * strings match each other, and they can be safely passed over before | |
| ; * starting the compare loop. So what this code does is skip over 0-3 | |
| ; * bytes, as much as necessary in order to dword-align the %edi | |
| ; * pointer. (%esi will still be misaligned three times out of four.) | |
| ; * | |
| ; * It should be confessed that this loop usually does not represent | |
| ; * much of the total running time. Replacing it with a more | |
| ; * straightforward "rep cmpsb" would not drastically degrade | |
| ; * performance. | |
| ; */ | |
| LoopCmps: | |
| mov eax, DWORD PTR[esi+edx] | |
| xor eax, DWORD PTR[edi+edx] | |
| jnz SHORT LeaveLoopCmps | |
| mov eax, DWORD PTR[esi+edx+4] | |
| xor eax, DWORD PTR[edi+edx+4] | |
| jnz SHORT LeaveLoopCmps4 | |
| add edx, 8 | |
| jnz SHORT LoopCmps | |
| jmp LenMaximum | |
| ALIGN 4 | |
| LeaveLoopCmps4: | |
| add edx, 4 | |
| LeaveLoopCmps: | |
| test eax, 00000FFFFH | |
| jnz SHORT LenLower | |
| add edx, 2 | |
| shr eax, 16 | |
| LenLower: | |
| sub al, 1 | |
| adc edx, 0 | |
| ;/* Calculate the length of the match. If it is longer than MAX_MATCH, */ | |
| ;/* then automatically accept it as the best possible match and leave. */ | |
| lea eax, [edi+edx] | |
| mov edi, [esp+scan] | |
| sub eax, edi | |
| cmp eax, MAX_MATCH | |
| jge SHORT LenMaximum | |
| ;/* If the length of the match is not longer than the best match we */ | |
| ;/* have so far, then forget it and return to the lookup loop. */ | |
| mov edx, [esp+deflatestate] | |
| mov ebx, [esp+bestlen] | |
| cmp eax, ebx | |
| jg SHORT LongerMatch | |
| mov esi, [esp+windowbestlen] | |
| mov edi, [edx].ds_prev | |
| mov ebx, [esp+scanend] | |
| mov edx, [esp+chainlenwmask] | |
| jmp LookupLoop | |
| ALIGN 4 | |
| ;/* s->match_start = cur_match; */ | |
| ;/* best_len = len; */ | |
| ;/* if (len >= nice_match) break; */ | |
| ;/* scan_end = *(ushf*)(scan+best_len-1); */ | |
| LongerMatch: | |
| mov ebx, [esp+nicematch] | |
| mov [esp+bestlen], eax | |
| mov [edx].ds_match_start, ecx | |
| cmp eax, ebx | |
| jge SHORT LeaveNow | |
| mov esi, [esp+window] | |
| add esi, eax | |
| mov [esp+windowbestlen], esi | |
| movzx ebx, WORD PTR[edi+eax-1] | |
| mov edi, [edx].ds_prev | |
| mov [esp+scanend], ebx | |
| mov edx, [esp+chainlenwmask] | |
| jmp LookupLoop | |
| ALIGN 4 | |
| ;/* Accept the current string, with the maximum possible length. */ | |
| LenMaximum: | |
| mov edx, [esp+deflatestate] | |
| mov DWORD PTR[esp+bestlen], MAX_MATCH | |
| mov [edx].ds_match_start, ecx | |
| ;/* if ((uInt)best_len <= s->lookahead) return (uInt)best_len; */ | |
| ;/* return s->lookahead; */ | |
| LeaveNow: | |
| mov edx, [esp+deflatestate] | |
| mov ebx, [esp+bestlen] | |
| mov eax, [edx].ds_lookahead | |
| cmp ebx, eax | |
| jg SHORT LookaheadRet | |
| mov eax, ebx | |
| LookaheadRet: | |
| ; Restore the stack and return from whence we came. | |
| add esp, varsize | |
| pop ebx | |
| pop esi | |
| pop edi | |
| pop ebp | |
| ret | |
| _longest_match ENDP | |
| _TEXT ENDS | |
| END |