1
;uInt longest_match_x64(
3
; IPos cur_match); /* current match */
5
; gvmat64.asm -- Asm portion of the optimized longest_match for 32 bits x86
6
; Copyright (C) 1995-2005 Jean-loup Gailly, Brian Raiter and Gilles Vollant.
8
; File written by Gilles Vollant, by converting to assembly the longest_match
9
; from Jean-loup Gailly in deflate.c of zLib and infoZip zip.
11
; and by taking inspiration on asm686 with masm, optimised assembly code
12
; from Brian Raiter, written 1998
15
; http://www.winimage.com/zLibDll
16
; http://www.muppetlabs.com/~breadbox/software/assembly.html
18
; to compile this file for infozip Zip, I use option:
19
; ml64.exe /Flgvmat64 /c /Zi /DINFOZIP gvmat64.asm
21
; to compile this file for zLib, I use option:
22
; ml64.exe /Flgvmat64 /c /Zi gvmat64.asm
23
; Be carrefull to adapt zlib1222add below to your version of zLib
24
; (if you use a version of zLib before 1.0.4 or after 1.2.2.2, change
25
; value of zlib1222add later)
27
; This file compile with Microsoft Macro Assembler (x64) for AMD64
29
; ml64.exe is given with Visual Studio 2005 and Windows 2003 server DDK
31
; (you can get Windows 2003 server DDK with ml64 and cl for AMD64 from
32
; http://www.microsoft.com/whdc/devtools/ddk/default.mspx for low price)
36
;uInt longest_match(s, cur_match)
38
; IPos cur_match; /* current match */
46
; register used : rax,rbx,rcx,rdx,rsi,rdi,r8,r9,r10,r11,r12
47
; free register : r14,r15
48
; register can be saved : rsp
50
chainlenwmask equ rsp + 8 - LocalVarsSize ; high word: current chain len
52
;window equ rsp + xx - LocalVarsSize ; local copy of s->window ; stored in r10
53
;windowbestlen equ rsp + xx - LocalVarsSize ; s->window + bestlen , use r10+r11
54
;scanstart equ rsp + xx - LocalVarsSize ; first two bytes of string ; stored in r12w
55
;scanend equ rsp + xx - LocalVarsSize ; last two bytes of string use ebx
56
;scanalign equ rsp + xx - LocalVarsSize ; dword-misalignment of string r13
57
;bestlen equ rsp + xx - LocalVarsSize ; size of best match so far -> r11d
58
;scan equ rsp + xx - LocalVarsSize ; ptr to string wanting match -> r9
61
nicematch equ (rsp + 16 - LocalVarsSize) ; a good enough match size
64
save_rdi equ rsp + 24 - LocalVarsSize
65
save_rsi equ rsp + 32 - LocalVarsSize
66
save_rbx equ rsp + 40 - LocalVarsSize
67
save_rbp equ rsp + 48 - LocalVarsSize
68
save_r12 equ rsp + 56 - LocalVarsSize
69
save_r13 equ rsp + 64 - LocalVarsSize
70
;save_r14 equ rsp + 72 - LocalVarsSize
71
;save_r15 equ rsp + 80 - LocalVarsSize
75
; all the +4 offsets are due to the addition of pending_buf_size (in zlib
76
; in the deflate_state structure since the asm code was first written
77
; (if you compile with zlib 1.0.4 or older, remove the +4).
78
; Note : these value are good with a 8 bytes boundary pack structure
83
MIN_LOOKAHEAD equ (MAX_MATCH+MIN_MATCH+1)
86
;;; Offsets for fields in the deflate_state structure. These numbers
87
;;; are calculated from the definition of deflate_state, with the
88
;;; assumption that the compiler will dword-align the fields. (Thus,
89
;;; changing the definition of deflate_state could easily cause this
90
;;; program to crash horribly, without so much as a warning at
91
;;; compile time. Sigh.)
93
; all the +zlib1222add offsets are due to the addition of fields
94
; in zlib in the deflate_state structure since the asm code was first written
95
; (if you compile with zlib 1.0.4 or older, use "zlib1222add equ (-4)").
96
; (if you compile with zlib between 1.0.5 and 1.2.2.1, use "zlib1222add equ 0").
97
; if you compile with zlib 1.2.2.2 or later , use "zlib1222add equ 8").
103
COMM window_size:DWORD
105
COMM window:BYTE:010040H
106
COMM prev:WORD:08000H
110
COMM match_start:DWORD
112
COMM prev_length:DWORD ; PrevLen
113
COMM max_chain_length:DWORD
114
COMM good_match:DWORD
115
COMM nice_match:DWORD
116
prev_ad equ OFFSET prev
117
window_ad equ OFFSET window
118
nicematch equ nice_match
127
dsWSize equ 56+zlib1222add+(zlib1222add/2)
128
dsWMask equ 64+zlib1222add+(zlib1222add/2)
129
dsWindow equ 72+zlib1222add
130
dsPrev equ 88+zlib1222add
131
dsMatchLen equ 128+zlib1222add
132
dsPrevMatch equ 132+zlib1222add
133
dsStrStart equ 140+zlib1222add
134
dsMatchStart equ 144+zlib1222add
135
dsLookahead equ 148+zlib1222add
136
dsPrevLen equ 152+zlib1222add
137
dsMaxChainLen equ 156+zlib1222add
138
dsGoodMatch equ 172+zlib1222add
139
dsNiceMatch equ 176+zlib1222add
141
window_size equ [ rcx + dsWSize]
142
WMask equ [ rcx + dsWMask]
143
window_ad equ [ rcx + dsWindow]
144
prev_ad equ [ rcx + dsPrev]
145
strstart equ [ rcx + dsStrStart]
146
match_start equ [ rcx + dsMatchStart]
147
Lookahead equ [ rcx + dsLookahead] ; 0ffffffffh on infozip
148
prev_length equ [ rcx + dsPrevLen]
149
max_chain_length equ [ rcx + dsMaxChainLen]
150
good_match equ [ rcx + dsGoodMatch]
151
nice_match equ [ rcx + dsNiceMatch]
154
; parameter 1 in r8(deflate state s), param 2 in rdx (cur match)
156
; see http://weblogs.asp.net/oldnewthing/archive/2004/01/14/58579.aspx and
157
; http://msdn.microsoft.com/library/en-us/kmarch/hh/kmarch/64bitAMD_8e951dd2-ee77-4728-8702-55ce4b5dd24a.xml.asp
159
; All registers must be preserved across the call, except for
160
; rax, rcx, rdx, r8, r9, r10, and r11, which are scratch.
164
;;; Save registers that the compiler may be using, and adjust esp to
165
;;; make room for our stack frame.
168
;;; Retrieve the function arguments. r8d will hold cur_match
169
;;; throughout the entire function. edx will hold the pointer to the
170
;;; deflate_state structure during the function's setup (before
171
;;; entering the main loop.
173
; parameter 1 in rcx (deflate_state* s), param 2 in edx -> r8 (cur match)
175
; this clear high 32 bits of r8, which can be garbage in both r8 and rdx
192
;;; uInt wmask = s->w_mask;
193
;;; unsigned chain_length = s->max_chain_length;
194
;;; if (s->prev_length >= s->good_match) {
195
;;; chain_length >>= 2;
201
mov ebx, max_chain_length
207
;;; chainlen is decremented once beforehand so that the function can
208
;;; use the sign flag instead of the zero flag for the exit test.
209
;;; It is then shifted into the high word, to make room for the wmask
210
;;; value, which it will always accompany.
217
;;; if ((uInt)nice_match > s->lookahead) nice_match = s->lookahead;
220
mov [chainlenwmask], ebx
221
; on infozip nice_match = [nice_match]
224
mov [chainlenwmask], ebx
231
;;; register Bytef *scan = s->window + s->strstart;
236
;;; Determine how many bytes the scan ptr is off from being
243
;;; IPos limit = s->strstart > (IPos)MAX_DIST(s) ?
244
;;; s->strstart - (IPos)MAX_DIST(s) : NIL;
246
mov eax,07efah ; MAX_DIST = (WSIZE-MIN_LOOKAHEAD) (0x8000-(3+8+1))
249
sub eax, MIN_LOOKAHEAD
254
mov r11d, prev_length
258
;;; int best_len = s->prev_length;
261
;;; Store the sum of s->window + best_len in esi locally, and in esi.
265
;;; register ush scan_start = *(ushf*)scan;
266
;;; register ush scan_end = *(ushf*)(scan+best_len-1);
267
;;; Posf *prev = s->prev;
269
movzx r12d,word ptr [r9]
270
movzx ebx, word ptr [r9 + r11 - 1]
274
;;; Jump into the main loop.
276
mov edx, [chainlenwmask]
278
cmp bx,word ptr [rsi + r8 - 1]
284
movzx r8d, word ptr [rdi + r8*2]
291
cmp bx,word ptr [rsi + r8 - 1]
297
movzx r8d, word ptr [rdi + r8*2]
304
cmp bx,word ptr [rsi + r8 - 1]
310
movzx r8d, word ptr [rdi + r8*2]
318
cmp bx,word ptr [rsi + r8 - 1]
324
;;; match = s->window + cur_match;
325
;;; if (*(ushf*)(match+best_len-1) != scan_end ||
326
;;; *(ushf*)match != scan_start) continue;
328
;;; } while ((cur_match = prev[cur_match & wmask]) > limit
329
;;; && --chain_length != 0);
331
;;; Here is the inner loop of the function. The function will spend the
332
;;; majority of its time in this loop, and majority of that time will
333
;;; be spent in the first ten instructions.
335
;;; Within this loop:
338
;;; edx = chainlenwmask - i.e., ((chainlen << 16) | wmask)
339
;;; esi = windowbestlen - i.e., (window + bestlen)
346
movzx r8d, word ptr [rdi + r8*2]
354
cmp bx,word ptr [rsi + r8 - 1]
357
cmp r12w, word ptr [r10 + r8]
361
;;; Store the current value of chainlen.
362
mov [chainlenwmask], edx
364
;;; Point edi to the string under scrutiny, and esi to the string we
365
;;; are hoping to match it up with. In actuality, esi and edi are
366
;;; both pointed (MAX_MATCH_8 - scanalign) bytes ahead, and edx is
367
;;; initialized to -(MAX_MATCH_8 - scanalign).
370
mov rdx, 0fffffffffffffef8h; -(MAX_MATCH_8)
371
lea rsi, [rsi + r13 + 0108h] ;MAX_MATCH_8]
372
lea rdi, [r9 + r13 + 0108h] ;MAX_MATCH_8]
378
;;; Test the strings for equality, 8 bytes at a time. At the end,
379
;;; adjust rdx so that it is offset to the exact byte that mismatched.
381
;;; We already know at this point that the first three bytes of the
382
;;; strings match each other, and they can be safely passed over before
383
;;; starting the compare loop. So what this code does is skip over 0-3
384
;;; bytes, as much as necessary in order to dword-align the edi
385
;;; pointer. (rsi will still be misaligned three times out of four.)
387
;;; It should be confessed that this loop usually does not represent
388
;;; much of the total running time. Replacing it with a more
389
;;; straightforward "rep cmpsb" would not drastically degrade
398
mov rax, [rsi + rdx + 8]
399
xor rax, [rdi + rdx + 8]
403
mov rax, [rsi + rdx + 8+8]
404
xor rax, [rdi + rdx + 8+8]
410
LeaveLoopCmps16: add rdx,8
411
LeaveLoopCmps8: add rdx,8
431
;;; Calculate the length of the match. If it is longer than MAX_MATCH,
432
;;; then automatically accept it as the best possible match and leave.
439
;;; If the length of the match is not longer than the best match we
440
;;; have so far, then forget it and return to the lookup loop.
441
;///////////////////////////////////
449
mov edx, [chainlenwmask]
452
;;; s->match_start = cur_match;
454
;;; if (len >= nice_match) break;
455
;;; scan_end = *(ushf*)(scan+best_len-1);
465
movzx ebx, word ptr [r9 + rax - 1]
467
mov edx, [chainlenwmask]
470
;;; Accept the current string, with the maximum possible length.
476
;;; if ((uInt)best_len <= s->lookahead) return (uInt)best_len;
477
;;; return s->lookahead;
488
;;; Restore the stack and return from whence we came.
502
; please don't remove this string !
503
; Your can freely use gvmat64 in any free or commercial app
504
; but it is far better don't remove the string in the binary!
505
db 0dh,0ah,"asm686 with masm, optimised assembly code from Brian Raiter, written 1998, converted to amd 64 by Gilles Vollant 2005",0dh,0ah,0