Debian Codegraph @

win32/gvmat64.asm

raw
1 ;uInt longest_match_x64(
2 ; deflate_state *s,
3 ; IPos cur_match); /* current match */
4
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.
7 ;
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.
10 ;
11 ; and by taking inspiration on asm686 with masm, optimised assembly code
12 ; from Brian Raiter, written 1998
13 ;
14 ; http://www.zlib.net
15 ; http://www.winimage.com/zLibDll
16 ; http://www.muppetlabs.com/~breadbox/software/assembly.html
17 ;
18 ; to compile this file for infozip Zip, I use option:
19 ; ml64.exe /Flgvmat64 /c /Zi /DINFOZIP gvmat64.asm
20 ;
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)
26 ;
27 ; This file compile with Microsoft Macro Assembler (x64) for AMD64
28 ;
29 ; ml64.exe is given with Visual Studio 2005 and Windows 2003 server DDK
30 ;
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)
33 ;
34
35
36 ;uInt longest_match(s, cur_match)
37 ; deflate_state *s;
38 ; IPos cur_match; /* current match */
39 .code
40 longest_match PROC
41
42
43 ;LocalVarsSize equ 88
44 LocalVarsSize equ 72
45
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
49
50 chainlenwmask equ rsp + 8 - LocalVarsSize ; high word: current chain len
51 ; low word: s->wmask
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
59 IFDEF INFOZIP
60 ELSE
61 nicematch equ (rsp + 16 - LocalVarsSize) ; a good enough match size
62 ENDIF
63
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
72
73
74
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
79
80
81 MAX_MATCH equ 258
82 MIN_MATCH equ 3
83 MIN_LOOKAHEAD equ (MAX_MATCH+MIN_MATCH+1)
84
85
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.)
92
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").
98
99
100 IFDEF INFOZIP
101
102 _DATA SEGMENT
103 COMM window_size:DWORD
104 ; WMask ; 7fff
105 COMM window:BYTE:010040H
106 COMM prev:WORD:08000H
107 ; MatchLen : unused
108 ; PrevMatch : unused
109 COMM strstart:DWORD
110 COMM match_start:DWORD
111 ; Lookahead : ignore
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
119 _DATA ENDS
120 WMask equ 07fffh
121
122 ELSE
123
124 IFNDEF zlib1222add
125 zlib1222add equ 0
126 ENDIF
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
140
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]
152 ENDIF
153
154 ; parameter 1 in r8(deflate state s), param 2 in rdx (cur match)
155
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
158 ;
159 ; All registers must be preserved across the call, except for
160 ; rax, rcx, rdx, r8, r9, r10, and r11, which are scratch.
161
162
163
164 ;;; Save registers that the compiler may be using, and adjust esp to
165 ;;; make room for our stack frame.
166
167
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.
172
173 ; parameter 1 in rcx (deflate_state* s), param 2 in edx -> r8 (cur match)
174
175 ; this clear high 32 bits of r8, which can be garbage in both r8 and rdx
176
177 mov [save_rdi],rdi
178 mov [save_rsi],rsi
179 mov [save_rbx],rbx
180 mov [save_rbp],rbp
181 IFDEF INFOZIP
182 mov r8d,ecx
183 ELSE
184 mov r8d,edx
185 ENDIF
186 mov [save_r12],r12
187 mov [save_r13],r13
188 ; mov [save_r14],r14
189 ; mov [save_r15],r15
190
191
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;
196 ;;; }
197
198 mov edi, prev_length
199 mov esi, good_match
200 mov eax, WMask
201 mov ebx, max_chain_length
202 cmp edi, esi
203 jl LastMatchGood
204 shr ebx, 2
205 LastMatchGood:
206
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.
211
212 dec ebx
213 shl ebx, 16
214 or ebx, eax
215
216 ;;; on zlib only
217 ;;; if ((uInt)nice_match > s->lookahead) nice_match = s->lookahead;
218
219 IFDEF INFOZIP
220 mov [chainlenwmask], ebx
221 ; on infozip nice_match = [nice_match]
222 ELSE
223 mov eax, nice_match
224 mov [chainlenwmask], ebx
225 mov r10d, Lookahead
226 cmp r10d, eax
227 cmovnl r10d, eax
228 mov [nicematch],r10d
229 ENDIF
230
231 ;;; register Bytef *scan = s->window + s->strstart;
232 mov r10, window_ad
233 mov ebp, strstart
234 lea r13, [r10 + rbp]
235
236 ;;; Determine how many bytes the scan ptr is off from being
237 ;;; dword-aligned.
238
239 mov r9,r13
240 neg r13
241 and r13,3
242
243 ;;; IPos limit = s->strstart > (IPos)MAX_DIST(s) ?
244 ;;; s->strstart - (IPos)MAX_DIST(s) : NIL;
245 IFDEF INFOZIP
246 mov eax,07efah ; MAX_DIST = (WSIZE-MIN_LOOKAHEAD) (0x8000-(3+8+1))
247 ELSE
248 mov eax, window_size
249 sub eax, MIN_LOOKAHEAD
250 ENDIF
251 xor edi,edi
252 sub ebp, eax
253
254 mov r11d, prev_length
255
256 cmovng ebp,edi
257
258 ;;; int best_len = s->prev_length;
259
260
261 ;;; Store the sum of s->window + best_len in esi locally, and in esi.
262
263 lea rsi,[r10+r11]
264
265 ;;; register ush scan_start = *(ushf*)scan;
266 ;;; register ush scan_end = *(ushf*)(scan+best_len-1);
267 ;;; Posf *prev = s->prev;
268
269 movzx r12d,word ptr [r9]
270 movzx ebx, word ptr [r9 + r11 - 1]
271
272 mov rdi, prev_ad
273
274 ;;; Jump into the main loop.
275
276 mov edx, [chainlenwmask]
277
278 cmp bx,word ptr [rsi + r8 - 1]
279 jz LookupLoopIsZero
280
281 LookupLoop1:
282 and r8d, edx
283
284 movzx r8d, word ptr [rdi + r8*2]
285 cmp r8d, ebp
286 jbe LeaveNow
287 sub edx, 00010000h
288 js LeaveNow
289
290 LoopEntry1:
291 cmp bx,word ptr [rsi + r8 - 1]
292 jz LookupLoopIsZero
293
294 LookupLoop2:
295 and r8d, edx
296
297 movzx r8d, word ptr [rdi + r8*2]
298 cmp r8d, ebp
299 jbe LeaveNow
300 sub edx, 00010000h
301 js LeaveNow
302
303 LoopEntry2:
304 cmp bx,word ptr [rsi + r8 - 1]
305 jz LookupLoopIsZero
306
307 LookupLoop4:
308 and r8d, edx
309
310 movzx r8d, word ptr [rdi + r8*2]
311 cmp r8d, ebp
312 jbe LeaveNow
313 sub edx, 00010000h
314 js LeaveNow
315
316 LoopEntry4:
317
318 cmp bx,word ptr [rsi + r8 - 1]
319 jnz LookupLoop1
320 jmp LookupLoopIsZero
321
322
323 ;;; do {
324 ;;; match = s->window + cur_match;
325 ;;; if (*(ushf*)(match+best_len-1) != scan_end ||
326 ;;; *(ushf*)match != scan_start) continue;
327 ;;; [...]
328 ;;; } while ((cur_match = prev[cur_match & wmask]) > limit
329 ;;; && --chain_length != 0);
330 ;;;
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.
334 ;;;
335 ;;; Within this loop:
336 ;;; ebx = scanend
337 ;;; r8d = curmatch
338 ;;; edx = chainlenwmask - i.e., ((chainlen << 16) | wmask)
339 ;;; esi = windowbestlen - i.e., (window + bestlen)
340 ;;; edi = prev
341 ;;; ebp = limit
342
343 LookupLoop:
344 and r8d, edx
345
346 movzx r8d, word ptr [rdi + r8*2]
347 cmp r8d, ebp
348 jbe LeaveNow
349 sub edx, 00010000h
350 js LeaveNow
351
352 LoopEntry:
353
354 cmp bx,word ptr [rsi + r8 - 1]
355 jnz LookupLoop1
356 LookupLoopIsZero:
357 cmp r12w, word ptr [r10 + r8]
358 jnz LookupLoop1
359
360
361 ;;; Store the current value of chainlen.
362 mov [chainlenwmask], edx
363
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).
368
369 lea rsi,[r8+r10]
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]
373
374 prefetcht1 [rsi+rdx]
375 prefetcht1 [rdi+rdx]
376
377
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.
380 ;;;
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.)
386 ;;;
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
390 ;;; performance.
391
392
393 LoopCmps:
394 mov rax, [rsi + rdx]
395 xor rax, [rdi + rdx]
396 jnz LeaveLoopCmps
397
398 mov rax, [rsi + rdx + 8]
399 xor rax, [rdi + rdx + 8]
400 jnz LeaveLoopCmps8
401
402
403 mov rax, [rsi + rdx + 8+8]
404 xor rax, [rdi + rdx + 8+8]
405 jnz LeaveLoopCmps16
406
407 add rdx,8+8+8
408
409 jmp short LoopCmps
410 LeaveLoopCmps16: add rdx,8
411 LeaveLoopCmps8: add rdx,8
412 LeaveLoopCmps:
413
414 test eax, 0000FFFFh
415 jnz LenLower
416
417 test eax,0ffffffffh
418
419 jnz LenLower32
420
421 add rdx,4
422 shr rax,32
423 or ax,ax
424 jnz LenLower
425
426 LenLower32:
427 shr eax,16
428 add rdx,2
429 LenLower: sub al, 1
430 adc rdx, 0
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.
433
434 lea rax, [rdi + rdx]
435 sub rax, r9
436 cmp eax, MAX_MATCH
437 jge LenMaximum
438
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 ;///////////////////////////////////
442
443 cmp eax, r11d
444 jg LongerMatch
445
446 lea rsi,[r10+r11]
447
448 mov rdi, prev_ad
449 mov edx, [chainlenwmask]
450 jmp LookupLoop
451
452 ;;; s->match_start = cur_match;
453 ;;; best_len = len;
454 ;;; if (len >= nice_match) break;
455 ;;; scan_end = *(ushf*)(scan+best_len-1);
456
457 LongerMatch:
458 mov r11d, eax
459 mov match_start, r8d
460 cmp eax, [nicematch]
461 jge LeaveNow
462
463 lea rsi,[r10+rax]
464
465 movzx ebx, word ptr [r9 + rax - 1]
466 mov rdi, prev_ad
467 mov edx, [chainlenwmask]
468 jmp LookupLoop
469
470 ;;; Accept the current string, with the maximum possible length.
471
472 LenMaximum:
473 mov r11d,MAX_MATCH
474 mov match_start, r8d
475
476 ;;; if ((uInt)best_len <= s->lookahead) return (uInt)best_len;
477 ;;; return s->lookahead;
478
479 LeaveNow:
480 IFDEF INFOZIP
481 mov eax,r11d
482 ELSE
483 mov eax, Lookahead
484 cmp r11d, eax
485 cmovng eax, r11d
486 ENDIF
487
488 ;;; Restore the stack and return from whence we came.
489
490
491 mov rsi,[save_rsi]
492 mov rdi,[save_rdi]
493 mov rbx,[save_rbx]
494 mov rbp,[save_rbp]
495 mov r12,[save_r12]
496 mov r13,[save_r13]
497 ; mov r14,[save_r14]
498 ; mov r15,[save_r15]
499
500
501 ret 0
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
506 longest_match ENDP
507
508 match_init PROC
509 ret 0
510 match_init ENDP
511
512
513 END