Mercurial > hg > sv-dependency-builds

annotate src/zlib-1.2.7/contrib/asm686/match.S @ 169:223a55898ab9 tip default

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Add null config files
author Chris Cannam <cannam@all-day-breakfast.com>
date Mon, 02 Mar 2020 14:03:47 +0000
parents 8a15ff55d9af
children
rev   line source
cannam@89 1 /* match.S -- x86 assembly version of the zlib longest_match() function.
cannam@89 2 * Optimized for the Intel 686 chips (PPro and later).
cannam@89 3 *
cannam@89 4 * Copyright (C) 1998, 2007 Brian Raiter <breadbox@muppetlabs.com>
cannam@89 5 *
cannam@89 6 * This software is provided 'as-is', without any express or implied
cannam@89 7 * warranty. In no event will the author be held liable for any damages
cannam@89 8 * arising from the use of this software.
cannam@89 9 *
cannam@89 10 * Permission is granted to anyone to use this software for any purpose,
cannam@89 11 * including commercial applications, and to alter it and redistribute it
cannam@89 12 * freely, subject to the following restrictions:
cannam@89 13 *
cannam@89 14 * 1. The origin of this software must not be misrepresented; you must not
cannam@89 15 * claim that you wrote the original software. If you use this software
cannam@89 16 * in a product, an acknowledgment in the product documentation would be
cannam@89 17 * appreciated but is not required.
cannam@89 18 * 2. Altered source versions must be plainly marked as such, and must not be
cannam@89 19 * misrepresented as being the original software.
cannam@89 20 * 3. This notice may not be removed or altered from any source distribution.
cannam@89 21 */
cannam@89 22
cannam@89 23 #ifndef NO_UNDERLINE
cannam@89 24 #define match_init _match_init
cannam@89 25 #define longest_match _longest_match
cannam@89 26 #endif
cannam@89 27
cannam@89 28 #define MAX_MATCH (258)
cannam@89 29 #define MIN_MATCH (3)
cannam@89 30 #define MIN_LOOKAHEAD (MAX_MATCH + MIN_MATCH + 1)
cannam@89 31 #define MAX_MATCH_8 ((MAX_MATCH + 7) & ~7)
cannam@89 32
cannam@89 33 /* stack frame offsets */
cannam@89 34
cannam@89 35 #define chainlenwmask 0 /* high word: current chain len */
cannam@89 36 /* low word: s->wmask */
cannam@89 37 #define window 4 /* local copy of s->window */
cannam@89 38 #define windowbestlen 8 /* s->window + bestlen */
cannam@89 39 #define scanstart 16 /* first two bytes of string */
cannam@89 40 #define scanend 12 /* last two bytes of string */
cannam@89 41 #define scanalign 20 /* dword-misalignment of string */
cannam@89 42 #define nicematch 24 /* a good enough match size */
cannam@89 43 #define bestlen 28 /* size of best match so far */
cannam@89 44 #define scan 32 /* ptr to string wanting match */
cannam@89 45
cannam@89 46 #define LocalVarsSize (36)
cannam@89 47 /* saved ebx 36 */
cannam@89 48 /* saved edi 40 */
cannam@89 49 /* saved esi 44 */
cannam@89 50 /* saved ebp 48 */
cannam@89 51 /* return address 52 */
cannam@89 52 #define deflatestate 56 /* the function arguments */
cannam@89 53 #define curmatch 60
cannam@89 54
cannam@89 55 /* All the +zlib1222add offsets are due to the addition of fields
cannam@89 56 * in zlib in the deflate_state structure since the asm code was first written
cannam@89 57 * (if you compile with zlib 1.0.4 or older, use "zlib1222add equ (-4)").
cannam@89 58 * (if you compile with zlib between 1.0.5 and 1.2.2.1, use "zlib1222add equ 0").
cannam@89 59 * if you compile with zlib 1.2.2.2 or later , use "zlib1222add equ 8").
cannam@89 60 */
cannam@89 61
cannam@89 62 #define zlib1222add (8)
cannam@89 63
cannam@89 64 #define dsWSize (36+zlib1222add)
cannam@89 65 #define dsWMask (44+zlib1222add)
cannam@89 66 #define dsWindow (48+zlib1222add)
cannam@89 67 #define dsPrev (56+zlib1222add)
cannam@89 68 #define dsMatchLen (88+zlib1222add)
cannam@89 69 #define dsPrevMatch (92+zlib1222add)
cannam@89 70 #define dsStrStart (100+zlib1222add)
cannam@89 71 #define dsMatchStart (104+zlib1222add)
cannam@89 72 #define dsLookahead (108+zlib1222add)
cannam@89 73 #define dsPrevLen (112+zlib1222add)
cannam@89 74 #define dsMaxChainLen (116+zlib1222add)
cannam@89 75 #define dsGoodMatch (132+zlib1222add)
cannam@89 76 #define dsNiceMatch (136+zlib1222add)
cannam@89 77
cannam@89 78
cannam@89 79 .file "match.S"
cannam@89 80
cannam@89 81 .globl match_init, longest_match
cannam@89 82
cannam@89 83 .text
cannam@89 84
cannam@89 85 /* uInt longest_match(deflate_state *deflatestate, IPos curmatch) */
cannam@89 86 .cfi_sections .debug_frame
cannam@89 87
cannam@89 88 longest_match:
cannam@89 89
cannam@89 90 .cfi_startproc
cannam@89 91 /* Save registers that the compiler may be using, and adjust %esp to */
cannam@89 92 /* make room for our stack frame. */
cannam@89 93
cannam@89 94 pushl %ebp
cannam@89 95 .cfi_def_cfa_offset 8
cannam@89 96 .cfi_offset ebp, -8
cannam@89 97 pushl %edi
cannam@89 98 .cfi_def_cfa_offset 12
cannam@89 99 pushl %esi
cannam@89 100 .cfi_def_cfa_offset 16
cannam@89 101 pushl %ebx
cannam@89 102 .cfi_def_cfa_offset 20
cannam@89 103 subl $LocalVarsSize, %esp
cannam@89 104 .cfi_def_cfa_offset LocalVarsSize+20
cannam@89 105
cannam@89 106 /* Retrieve the function arguments. %ecx will hold cur_match */
cannam@89 107 /* throughout the entire function. %edx will hold the pointer to the */
cannam@89 108 /* deflate_state structure during the function's setup (before */
cannam@89 109 /* entering the main loop). */
cannam@89 110
cannam@89 111 movl deflatestate(%esp), %edx
cannam@89 112 movl curmatch(%esp), %ecx
cannam@89 113
cannam@89 114 /* uInt wmask = s->w_mask; */
cannam@89 115 /* unsigned chain_length = s->max_chain_length; */
cannam@89 116 /* if (s->prev_length >= s->good_match) { */
cannam@89 117 /* chain_length >>= 2; */
cannam@89 118 /* } */
cannam@89 119
cannam@89 120 movl dsPrevLen(%edx), %eax
cannam@89 121 movl dsGoodMatch(%edx), %ebx
cannam@89 122 cmpl %ebx, %eax
cannam@89 123 movl dsWMask(%edx), %eax
cannam@89 124 movl dsMaxChainLen(%edx), %ebx
cannam@89 125 jl LastMatchGood
cannam@89 126 shrl $2, %ebx
cannam@89 127 LastMatchGood:
cannam@89 128
cannam@89 129 /* chainlen is decremented once beforehand so that the function can */
cannam@89 130 /* use the sign flag instead of the zero flag for the exit test. */
cannam@89 131 /* It is then shifted into the high word, to make room for the wmask */
cannam@89 132 /* value, which it will always accompany. */
cannam@89 133
cannam@89 134 decl %ebx
cannam@89 135 shll $16, %ebx
cannam@89 136 orl %eax, %ebx
cannam@89 137 movl %ebx, chainlenwmask(%esp)
cannam@89 138
cannam@89 139 /* if ((uInt)nice_match > s->lookahead) nice_match = s->lookahead; */
cannam@89 140
cannam@89 141 movl dsNiceMatch(%edx), %eax
cannam@89 142 movl dsLookahead(%edx), %ebx
cannam@89 143 cmpl %eax, %ebx
cannam@89 144 jl LookaheadLess
cannam@89 145 movl %eax, %ebx
cannam@89 146 LookaheadLess: movl %ebx, nicematch(%esp)
cannam@89 147
cannam@89 148 /* register Bytef *scan = s->window + s->strstart; */
cannam@89 149
cannam@89 150 movl dsWindow(%edx), %esi
cannam@89 151 movl %esi, window(%esp)
cannam@89 152 movl dsStrStart(%edx), %ebp
cannam@89 153 lea (%esi,%ebp), %edi
cannam@89 154 movl %edi, scan(%esp)
cannam@89 155
cannam@89 156 /* Determine how many bytes the scan ptr is off from being */
cannam@89 157 /* dword-aligned. */
cannam@89 158
cannam@89 159 movl %edi, %eax
cannam@89 160 negl %eax
cannam@89 161 andl $3, %eax
cannam@89 162 movl %eax, scanalign(%esp)
cannam@89 163
cannam@89 164 /* IPos limit = s->strstart > (IPos)MAX_DIST(s) ? */
cannam@89 165 /* s->strstart - (IPos)MAX_DIST(s) : NIL; */
cannam@89 166
cannam@89 167 movl dsWSize(%edx), %eax
cannam@89 168 subl $MIN_LOOKAHEAD, %eax
cannam@89 169 subl %eax, %ebp
cannam@89 170 jg LimitPositive
cannam@89 171 xorl %ebp, %ebp
cannam@89 172 LimitPositive:
cannam@89 173
cannam@89 174 /* int best_len = s->prev_length; */
cannam@89 175
cannam@89 176 movl dsPrevLen(%edx), %eax
cannam@89 177 movl %eax, bestlen(%esp)
cannam@89 178
cannam@89 179 /* Store the sum of s->window + best_len in %esi locally, and in %esi. */
cannam@89 180
cannam@89 181 addl %eax, %esi
cannam@89 182 movl %esi, windowbestlen(%esp)
cannam@89 183
cannam@89 184 /* register ush scan_start = *(ushf*)scan; */
cannam@89 185 /* register ush scan_end = *(ushf*)(scan+best_len-1); */
cannam@89 186 /* Posf *prev = s->prev; */
cannam@89 187
cannam@89 188 movzwl (%edi), %ebx
cannam@89 189 movl %ebx, scanstart(%esp)
cannam@89 190 movzwl -1(%edi,%eax), %ebx
cannam@89 191 movl %ebx, scanend(%esp)
cannam@89 192 movl dsPrev(%edx), %edi
cannam@89 193
cannam@89 194 /* Jump into the main loop. */
cannam@89 195
cannam@89 196 movl chainlenwmask(%esp), %edx
cannam@89 197 jmp LoopEntry
cannam@89 198
cannam@89 199 .balign 16
cannam@89 200
cannam@89 201 /* do {
cannam@89 202 * match = s->window + cur_match;
cannam@89 203 * if (*(ushf*)(match+best_len-1) != scan_end ||
cannam@89 204 * *(ushf*)match != scan_start) continue;
cannam@89 205 * [...]
cannam@89 206 * } while ((cur_match = prev[cur_match & wmask]) > limit
cannam@89 207 * && --chain_length != 0);
cannam@89 208 *
cannam@89 209 * Here is the inner loop of the function. The function will spend the
cannam@89 210 * majority of its time in this loop, and majority of that time will
cannam@89 211 * be spent in the first ten instructions.
cannam@89 212 *
cannam@89 213 * Within this loop:
cannam@89 214 * %ebx = scanend
cannam@89 215 * %ecx = curmatch
cannam@89 216 * %edx = chainlenwmask - i.e., ((chainlen << 16) | wmask)
cannam@89 217 * %esi = windowbestlen - i.e., (window + bestlen)
cannam@89 218 * %edi = prev
cannam@89 219 * %ebp = limit
cannam@89 220 */
cannam@89 221 LookupLoop:
cannam@89 222 andl %edx, %ecx
cannam@89 223 movzwl (%edi,%ecx,2), %ecx
cannam@89 224 cmpl %ebp, %ecx
cannam@89 225 jbe LeaveNow
cannam@89 226 subl $0x00010000, %edx
cannam@89 227 js LeaveNow
cannam@89 228 LoopEntry: movzwl -1(%esi,%ecx), %eax
cannam@89 229 cmpl %ebx, %eax
cannam@89 230 jnz LookupLoop
cannam@89 231 movl window(%esp), %eax
cannam@89 232 movzwl (%eax,%ecx), %eax
cannam@89 233 cmpl scanstart(%esp), %eax
cannam@89 234 jnz LookupLoop
cannam@89 235
cannam@89 236 /* Store the current value of chainlen. */
cannam@89 237
cannam@89 238 movl %edx, chainlenwmask(%esp)
cannam@89 239
cannam@89 240 /* Point %edi to the string under scrutiny, and %esi to the string we */
cannam@89 241 /* are hoping to match it up with. In actuality, %esi and %edi are */
cannam@89 242 /* both pointed (MAX_MATCH_8 - scanalign) bytes ahead, and %edx is */
cannam@89 243 /* initialized to -(MAX_MATCH_8 - scanalign). */
cannam@89 244
cannam@89 245 movl window(%esp), %esi
cannam@89 246 movl scan(%esp), %edi
cannam@89 247 addl %ecx, %esi
cannam@89 248 movl scanalign(%esp), %eax
cannam@89 249 movl $(-MAX_MATCH_8), %edx
cannam@89 250 lea MAX_MATCH_8(%edi,%eax), %edi
cannam@89 251 lea MAX_MATCH_8(%esi,%eax), %esi
cannam@89 252
cannam@89 253 /* Test the strings for equality, 8 bytes at a time. At the end,
cannam@89 254 * adjust %edx so that it is offset to the exact byte that mismatched.
cannam@89 255 *
cannam@89 256 * We already know at this point that the first three bytes of the
cannam@89 257 * strings match each other, and they can be safely passed over before
cannam@89 258 * starting the compare loop. So what this code does is skip over 0-3
cannam@89 259 * bytes, as much as necessary in order to dword-align the %edi
cannam@89 260 * pointer. (%esi will still be misaligned three times out of four.)
cannam@89 261 *
cannam@89 262 * It should be confessed that this loop usually does not represent
cannam@89 263 * much of the total running time. Replacing it with a more
cannam@89 264 * straightforward "rep cmpsb" would not drastically degrade
cannam@89 265 * performance.
cannam@89 266 */
cannam@89 267 LoopCmps:
cannam@89 268 movl (%esi,%edx), %eax
cannam@89 269 xorl (%edi,%edx), %eax
cannam@89 270 jnz LeaveLoopCmps
cannam@89 271 movl 4(%esi,%edx), %eax
cannam@89 272 xorl 4(%edi,%edx), %eax
cannam@89 273 jnz LeaveLoopCmps4
cannam@89 274 addl $8, %edx
cannam@89 275 jnz LoopCmps
cannam@89 276 jmp LenMaximum
cannam@89 277 LeaveLoopCmps4: addl $4, %edx
cannam@89 278 LeaveLoopCmps: testl $0x0000FFFF, %eax
cannam@89 279 jnz LenLower
cannam@89 280 addl $2, %edx
cannam@89 281 shrl $16, %eax
cannam@89 282 LenLower: subb $1, %al
cannam@89 283 adcl $0, %edx
cannam@89 284
cannam@89 285 /* Calculate the length of the match. If it is longer than MAX_MATCH, */
cannam@89 286 /* then automatically accept it as the best possible match and leave. */
cannam@89 287
cannam@89 288 lea (%edi,%edx), %eax
cannam@89 289 movl scan(%esp), %edi
cannam@89 290 subl %edi, %eax
cannam@89 291 cmpl $MAX_MATCH, %eax
cannam@89 292 jge LenMaximum
cannam@89 293
cannam@89 294 /* If the length of the match is not longer than the best match we */
cannam@89 295 /* have so far, then forget it and return to the lookup loop. */
cannam@89 296
cannam@89 297 movl deflatestate(%esp), %edx
cannam@89 298 movl bestlen(%esp), %ebx
cannam@89 299 cmpl %ebx, %eax
cannam@89 300 jg LongerMatch
cannam@89 301 movl windowbestlen(%esp), %esi
cannam@89 302 movl dsPrev(%edx), %edi
cannam@89 303 movl scanend(%esp), %ebx
cannam@89 304 movl chainlenwmask(%esp), %edx
cannam@89 305 jmp LookupLoop
cannam@89 306
cannam@89 307 /* s->match_start = cur_match; */
cannam@89 308 /* best_len = len; */
cannam@89 309 /* if (len >= nice_match) break; */
cannam@89 310 /* scan_end = *(ushf*)(scan+best_len-1); */
cannam@89 311
cannam@89 312 LongerMatch: movl nicematch(%esp), %ebx
cannam@89 313 movl %eax, bestlen(%esp)
cannam@89 314 movl %ecx, dsMatchStart(%edx)
cannam@89 315 cmpl %ebx, %eax
cannam@89 316 jge LeaveNow
cannam@89 317 movl window(%esp), %esi
cannam@89 318 addl %eax, %esi
cannam@89 319 movl %esi, windowbestlen(%esp)
cannam@89 320 movzwl -1(%edi,%eax), %ebx
cannam@89 321 movl dsPrev(%edx), %edi
cannam@89 322 movl %ebx, scanend(%esp)
cannam@89 323 movl chainlenwmask(%esp), %edx
cannam@89 324 jmp LookupLoop
cannam@89 325
cannam@89 326 /* Accept the current string, with the maximum possible length. */
cannam@89 327
cannam@89 328 LenMaximum: movl deflatestate(%esp), %edx
cannam@89 329 movl $MAX_MATCH, bestlen(%esp)
cannam@89 330 movl %ecx, dsMatchStart(%edx)
cannam@89 331
cannam@89 332 /* if ((uInt)best_len <= s->lookahead) return (uInt)best_len; */
cannam@89 333 /* return s->lookahead; */
cannam@89 334
cannam@89 335 LeaveNow:
cannam@89 336 movl deflatestate(%esp), %edx
cannam@89 337 movl bestlen(%esp), %ebx
cannam@89 338 movl dsLookahead(%edx), %eax
cannam@89 339 cmpl %eax, %ebx
cannam@89 340 jg LookaheadRet
cannam@89 341 movl %ebx, %eax
cannam@89 342 LookaheadRet:
cannam@89 343
cannam@89 344 /* Restore the stack and return from whence we came. */
cannam@89 345
cannam@89 346 addl $LocalVarsSize, %esp
cannam@89 347 .cfi_def_cfa_offset 20
cannam@89 348 popl %ebx
cannam@89 349 .cfi_def_cfa_offset 16
cannam@89 350 popl %esi
cannam@89 351 .cfi_def_cfa_offset 12
cannam@89 352 popl %edi
cannam@89 353 .cfi_def_cfa_offset 8
cannam@89 354 popl %ebp
cannam@89 355 .cfi_def_cfa_offset 4
cannam@89 356 .cfi_endproc
cannam@89 357 match_init: ret