; 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
Submit an article or tip