← Back to branch summary

~ubuntu-branches/ubuntu/hardy/openswan/hardy-updates

« back to all changes in this revision

Viewing changes to linux/lib/zlib/match586.S

  • Committer: Bazaar Package Importer
  • Author(s): Rene Mayrhofer
  • Date: 2005-01-27 16:10:11 UTC
  • mfrom: (1.1.1 upstream)
  • Revision ID: james.westby@ubuntu.com-20050127161011-idgybmyz3vwhpfiq
Tags: 2.3.0-2
http://bugs.debian.org/292458
http://bugs.debian.org/291143
Urgency HIGH due to security issue and problems with build-deps in sarge.
* Fix the security issue. Please see
  http://www.idefense.com/application/poi/display?id=190&
      type=vulnerabilities&flashstatus=false
  for more details. Thanks to Martin Schulze for informing me about
  this issue.
  Closes: #292458: Openswan XAUTH/PAM Buffer Overflow Vulnerability
* Added a Build-Dependency to lynx.
  Closes: #291143: openswan: FTBFS: Missing build dependency.

Show diffs side-by-side

added added

removed removed

Lines of Context:
linux/lib/zlib/match586.S
1
 
/* match.s -- Pentium-optimized version of longest_match()
2
 
 * Written for zlib 1.1.2
3
 
 * Copyright (C) 1998 Brian Raiter <breadbox@muppetlabs.com>
4
 
 *
5
 
 * This is free software; you can redistribute it and/or modify it
6
 
 * under the terms of the GNU General Public License.
7
 
 */
8
 
 
9
 
#ifndef NO_UNDERLINE
10
 
#define match_init      _ipcomp_match_init
11
 
#define longest_match   _ipcomp_longest_match
12
 
#else
13
 
#define match_init      ipcomp_match_init
14
 
#define longest_match   ipcomp_longest_match
15
 
#endif
16
 
 
17
 
#define MAX_MATCH       (258)
18
 
#define MIN_MATCH       (3)
19
 
#define MIN_LOOKAHEAD   (MAX_MATCH + MIN_MATCH + 1)
20
 
#define MAX_MATCH_8     ((MAX_MATCH + 7) & ~7)
21
 
 
22
 
/* stack frame offsets */
23
 
 
24
 
#define wmask                   0       /* local copy of s->wmask       */
25
 
#define window                  4       /* local copy of s->window      */
26
 
#define windowbestlen           8       /* s->window + bestlen          */
27
 
#define chainlenscanend         12      /* high word: current chain len */
28
 
                                        /* low word: last bytes sought  */
29
 
#define scanstart               16      /* first two bytes of string    */
30
 
#define scanalign               20      /* dword-misalignment of string */
31
 
#define nicematch               24      /* a good enough match size     */
32
 
#define bestlen                 28      /* size of best match so far    */
33
 
#define scan                    32      /* ptr to string wanting match  */
34
 
 
35
 
#define LocalVarsSize           (36)
36
 
/*      saved ebx               36 */
37
 
/*      saved edi               40 */
38
 
/*      saved esi               44 */
39
 
/*      saved ebp               48 */
40
 
/*      return address          52 */
41
 
#define deflatestate            56      /* the function arguments       */
42
 
#define curmatch                60
43
 
 
44
 
/* Offsets for fields in the deflate_state structure. These numbers
45
 
 * are calculated from the definition of deflate_state, with the
46
 
 * assumption that the compiler will dword-align the fields. (Thus,
47
 
 * changing the definition of deflate_state could easily cause this
48
 
 * program to crash horribly, without so much as a warning at
49
 
 * compile time. Sigh.)
50
 
 */
51
 
#define dsWSize                 36
52
 
#define dsWMask                 44
53
 
#define dsWindow                48
54
 
#define dsPrev                  56
55
 
#define dsMatchLen              88
56
 
#define dsPrevMatch             92
57
 
#define dsStrStart              100
58
 
#define dsMatchStart            104
59
 
#define dsLookahead             108
60
 
#define dsPrevLen               112
61
 
#define dsMaxChainLen           116
62
 
#define dsGoodMatch             132
63
 
#define dsNiceMatch             136
64
 
 
65
 
 
66
 
.file "match.S"
67
 
 
68
 
.globl  match_init, longest_match
69
 
 
70
 
.text
71
 
 
72
 
/* uInt longest_match(deflate_state *deflatestate, IPos curmatch) */
73
 
 
74
 
longest_match:
75
 
 
76
 
/* Save registers that the compiler may be using, and adjust %esp to    */
77
 
/* make room for our stack frame.                                       */
78
 
 
79
 
                pushl   %ebp
80
 
                pushl   %edi
81
 
                pushl   %esi
82
 
                pushl   %ebx
83
 
                subl    $LocalVarsSize, %esp
84
 
 
85
 
/* Retrieve the function arguments. %ecx will hold cur_match            */
86
 
/* throughout the entire function. %edx will hold the pointer to the    */
87
 
/* deflate_state structure during the function's setup (before          */
88
 
/* entering the main loop).                                             */
89
 
 
90
 
                movl    deflatestate(%esp), %edx
91
 
                movl    curmatch(%esp), %ecx
92
 
 
93
 
/* if ((uInt)nice_match > s->lookahead) nice_match = s->lookahead;      */
94
 
 
95
 
                movl    dsNiceMatch(%edx), %eax
96
 
                movl    dsLookahead(%edx), %ebx
97
 
                cmpl    %eax, %ebx
98
 
                jl      LookaheadLess
99
 
                movl    %eax, %ebx
100
 
LookaheadLess:  movl    %ebx, nicematch(%esp)
101
 
 
102
 
/* register Bytef *scan = s->window + s->strstart;                      */
103
 
 
104
 
                movl    dsWindow(%edx), %esi
105
 
                movl    %esi, window(%esp)
106
 
                movl    dsStrStart(%edx), %ebp
107
 
                lea     (%esi,%ebp), %edi
108
 
                movl    %edi, scan(%esp)
109
 
 
110
 
/* Determine how many bytes the scan ptr is off from being              */
111
 
/* dword-aligned.                                                       */
112
 
 
113
 
                movl    %edi, %eax
114
 
                negl    %eax
115
 
                andl    $3, %eax
116
 
                movl    %eax, scanalign(%esp)
117
 
 
118
 
/* IPos limit = s->strstart > (IPos)MAX_DIST(s) ?                       */
119
 
/*     s->strstart - (IPos)MAX_DIST(s) : NIL;                           */
120
 
 
121
 
                movl    dsWSize(%edx), %eax
122
 
                subl    $MIN_LOOKAHEAD, %eax
123
 
                subl    %eax, %ebp
124
 
                jg      LimitPositive
125
 
                xorl    %ebp, %ebp
126
 
LimitPositive:
127
 
 
128
 
/* unsigned chain_length = s->max_chain_length;                         */
129
 
/* if (s->prev_length >= s->good_match) {                               */
130
 
/*     chain_length >>= 2;                                              */
131
 
/* }                                                                    */
132
 
 
133
 
                movl    dsPrevLen(%edx), %eax
134
 
                movl    dsGoodMatch(%edx), %ebx
135
 
                cmpl    %ebx, %eax
136
 
                movl    dsMaxChainLen(%edx), %ebx
137
 
                jl      LastMatchGood
138
 
                shrl    $2, %ebx
139
 
LastMatchGood:
140
 
 
141
 
/* chainlen is decremented once beforehand so that the function can     */
142
 
/* use the sign flag instead of the zero flag for the exit test.        */
143
 
/* It is then shifted into the high word, to make room for the scanend  */
144
 
/* scanend value, which it will always accompany.                       */
145
 
 
146
 
                decl    %ebx
147
 
                shll    $16, %ebx
148
 
 
149
 
/* int best_len = s->prev_length;                                       */
150
 
 
151
 
                movl    dsPrevLen(%edx), %eax
152
 
                movl    %eax, bestlen(%esp)
153
 
 
154
 
/* Store the sum of s->window + best_len in %esi locally, and in %esi.  */
155
 
 
156
 
                addl    %eax, %esi
157
 
                movl    %esi, windowbestlen(%esp)
158
 
 
159
 
/* register ush scan_start = *(ushf*)scan;                              */
160
 
/* register ush scan_end   = *(ushf*)(scan+best_len-1);                 */
161
 
 
162
 
                movw    (%edi), %bx
163
 
                movw    %bx, scanstart(%esp)
164
 
                movw    -1(%edi,%eax), %bx
165
 
                movl    %ebx, chainlenscanend(%esp)
166
 
 
167
 
/* Posf *prev = s->prev;                                                */
168
 
/* uInt wmask = s->w_mask;                                              */
169
 
 
170
 
                movl    dsPrev(%edx), %edi
171
 
                movl    dsWMask(%edx), %edx
172
 
                mov     %edx, wmask(%esp)
173
 
 
174
 
/* Jump into the main loop.                                             */
175
 
 
176
 
                jmp     LoopEntry
177
 
 
178
 
.balign 16
179
 
 
180
 
/* do {
181
 
 *     match = s->window + cur_match;
182
 
 *     if (*(ushf*)(match+best_len-1) != scan_end ||
183
 
 *         *(ushf*)match != scan_start) continue;
184
 
 *     [...]
185
 
 * } while ((cur_match = prev[cur_match & wmask]) > limit
186
 
 *          && --chain_length != 0);
187
 
 *
188
 
 * Here is the inner loop of the function. The function will spend the
189
 
 * majority of its time in this loop, and majority of that time will
190
 
 * be spent in the first ten instructions.
191
 
 *
192
 
 * Within this loop:
193
 
 * %ebx = chainlenscanend - i.e., ((chainlen << 16) | scanend)
194
 
 * %ecx = curmatch
195
 
 * %edx = curmatch & wmask
196
 
 * %esi = windowbestlen - i.e., (window + bestlen)
197
 
 * %edi = prev
198
 
 * %ebp = limit
199
 
 *
200
 
 * Two optimization notes on the choice of instructions:
201
 
 *
202
 
 * The first instruction uses a 16-bit address, which costs an extra,
203
 
 * unpairable cycle. This is cheaper than doing a 32-bit access and
204
 
 * zeroing the high word, due to the 3-cycle misalignment penalty which
205
 
 * would occur half the time. This also turns out to be cheaper than
206
 
 * doing two separate 8-bit accesses, as the memory is so rarely in the
207
 
 * L1 cache.
208
 
 *
209
 
 * The window buffer, however, apparently spends a lot of time in the
210
 
 * cache, and so it is faster to retrieve the word at the end of the
211
 
 * match string with two 8-bit loads. The instructions that test the
212
 
 * word at the beginning of the match string, however, are executed
213
 
 * much less frequently, and there it was cheaper to use 16-bit
214
 
 * instructions, which avoided the necessity of saving off and
215
 
 * subsequently reloading one of the other registers.
216
 
 */
217
 
LookupLoop:
218
 
                                                        /* 1 U & V  */
219
 
                movw    (%edi,%edx,2), %cx              /* 2 U pipe */
220
 
                movl    wmask(%esp), %edx               /* 2 V pipe */
221
 
                cmpl    %ebp, %ecx                      /* 3 U pipe */
222
 
                jbe     LeaveNow                        /* 3 V pipe */
223
 
                subl    $0x00010000, %ebx               /* 4 U pipe */
224
 
                js      LeaveNow                        /* 4 V pipe */
225
 
LoopEntry:      movb    -1(%esi,%ecx), %al              /* 5 U pipe */
226
 
                andl    %ecx, %edx                      /* 5 V pipe */
227
 
                cmpb    %bl, %al                        /* 6 U pipe */
228
 
                jnz     LookupLoop                      /* 6 V pipe */
229
 
                movb    (%esi,%ecx), %ah
230
 
                cmpb    %bh, %ah
231
 
                jnz     LookupLoop
232
 
                movl    window(%esp), %eax
233
 
                movw    (%eax,%ecx), %ax
234
 
                cmpw    scanstart(%esp), %ax
235
 
                jnz     LookupLoop
236
 
 
237
 
/* Store the current value of chainlen.                                 */
238
 
 
239
 
                movl    %ebx, chainlenscanend(%esp)
240
 
 
241
 
/* Point %edi to the string under scrutiny, and %esi to the string we   */
242
 
/* are hoping to match it up with. In actuality, %esi and %edi are      */
243
 
/* both pointed (MAX_MATCH_8 - scanalign) bytes ahead, and %edx is      */
244
 
/* initialized to -(MAX_MATCH_8 - scanalign).                           */
245
 
 
246
 
                movl    window(%esp), %esi
247
 
                movl    scan(%esp), %edi
248
 
                addl    %ecx, %esi
249
 
                movl    scanalign(%esp), %eax
250
 
                movl    $(-MAX_MATCH_8), %edx
251
 
                lea     MAX_MATCH_8(%edi,%eax), %edi
252
 
                lea     MAX_MATCH_8(%esi,%eax), %esi
253
 
 
254
 
/* Test the strings for equality, 8 bytes at a time. At the end,
255
 
 * adjust %edx so that it is offset to the exact byte that mismatched.
256
 
 *
257
 
 * We already know at this point that the first three bytes of the
258
 
 * strings match each other, and they can be safely passed over before
259
 
 * starting the compare loop. So what this code does is skip over 0-3
260
 
 * bytes, as much as necessary in order to dword-align the %edi
261
 
 * pointer. (%esi will still be misaligned three times out of four.)
262
 
 *
263
 
 * It should be confessed that this loop usually does not represent
264
 
 * much of the total running time. Replacing it with a more
265
 
 * straightforward "rep cmpsb" would not drastically degrade
266
 
 * performance.
267
 
 */
268
 
LoopCmps:
269
 
                movl    (%esi,%edx), %eax
270
 
                movl    (%edi,%edx), %ebx
271
 
                xorl    %ebx, %eax
272
 
                jnz     LeaveLoopCmps
273
 
                movl    4(%esi,%edx), %eax
274
 
                movl    4(%edi,%edx), %ebx
275
 
                xorl    %ebx, %eax
276
 
                jnz     LeaveLoopCmps4
277
 
                addl    $8, %edx
278
 
                jnz     LoopCmps
279
 
                jmp     LenMaximum
280
 
LeaveLoopCmps4: addl    $4, %edx
281
 
LeaveLoopCmps:  testl   $0x0000FFFF, %eax
282
 
                jnz     LenLower
283
 
                addl    $2, %edx
284
 
                shrl    $16, %eax
285
 
LenLower:       subb    $1, %al
286
 
                adcl    $0, %edx
287
 
 
288
 
/* Calculate the length of the match. If it is longer than MAX_MATCH,   */
289
 
/* then automatically accept it as the best possible match and leave.   */
290
 
 
291
 
                lea     (%edi,%edx), %eax
292
 
                movl    scan(%esp), %edi
293
 
                subl    %edi, %eax
294
 
                cmpl    $MAX_MATCH, %eax
295
 
                jge     LenMaximum
296
 
 
297
 
/* If the length of the match is not longer than the best match we      */
298
 
/* have so far, then forget it and return to the lookup loop.           */
299
 
 
300
 
                movl    deflatestate(%esp), %edx
301
 
                movl    bestlen(%esp), %ebx
302
 
                cmpl    %ebx, %eax
303
 
                jg      LongerMatch
304
 
                movl    chainlenscanend(%esp), %ebx
305
 
                movl    windowbestlen(%esp), %esi
306
 
                movl    dsPrev(%edx), %edi
307
 
                movl    wmask(%esp), %edx
308
 
                andl    %ecx, %edx
309
 
                jmp     LookupLoop
310
 
 
311
 
/*         s->match_start = cur_match;                                  */
312
 
/*         best_len = len;                                              */
313
 
/*         if (len >= nice_match) break;                                */
314
 
/*         scan_end = *(ushf*)(scan+best_len-1);                        */
315
 
 
316
 
LongerMatch:    movl    nicematch(%esp), %ebx
317
 
                movl    %eax, bestlen(%esp)
318
 
                movl    %ecx, dsMatchStart(%edx)
319
 
                cmpl    %ebx, %eax
320
 
                jge     LeaveNow
321
 
                movl    window(%esp), %esi
322
 
                addl    %eax, %esi
323
 
                movl    %esi, windowbestlen(%esp)
324
 
                movl    chainlenscanend(%esp), %ebx
325
 
                movw    -1(%edi,%eax), %bx
326
 
                movl    dsPrev(%edx), %edi
327
 
                movl    %ebx, chainlenscanend(%esp)
328
 
                movl    wmask(%esp), %edx
329
 
                andl    %ecx, %edx
330
 
                jmp     LookupLoop
331
 
 
332
 
/* Accept the current string, with the maximum possible length.         */
333
 
 
334
 
LenMaximum:     movl    deflatestate(%esp), %edx
335
 
                movl    $MAX_MATCH, bestlen(%esp)
336
 
                movl    %ecx, dsMatchStart(%edx)
337
 
 
338
 
/* if ((uInt)best_len <= s->lookahead) return (uInt)best_len;           */
339
 
/* return s->lookahead;                                                 */
340
 
 
341
 
LeaveNow:
342
 
                movl    deflatestate(%esp), %edx
343
 
                movl    bestlen(%esp), %ebx
344
 
                movl    dsLookahead(%edx), %eax
345
 
                cmpl    %eax, %ebx
346
 
                jg      LookaheadRet
347
 
                movl    %ebx, %eax
348
 
LookaheadRet:
349
 
 
350
 
/* Restore the stack and return from whence we came.                    */
351
 
 
352
 
                addl    $LocalVarsSize, %esp
353
 
                popl    %ebx
354
 
                popl    %esi
355
 
                popl    %edi
356
 
                popl    %ebp
357
 
match_init:     ret