← Back to branch summary

~zulcss/samba/server-dailies-3.4

« back to all changes in this revision

Viewing changes to lib/zlib/contrib/masm686/match.asm

  • Committer: Chuck Short
  • Date: 2010-09-28 20:38:39 UTC
  • Revision ID: zulcss@ubuntu.com-20100928203839-pgjulytsi9ue63x1
Initial version

Show diffs side-by-side

added added

removed removed

Lines of Context:
lib/zlib/contrib/masm686/match.asm
 
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