1381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes/* match.S -- x86 assembly version of the zlib longest_match() function. 2381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes * Optimized for the Intel 686 chips (PPro and later). 39e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * 4381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes * Copyright (C) 1998, 2007 Brian Raiter <breadbox@muppetlabs.com> 5381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes * 6381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes * This software is provided 'as-is', without any express or implied 7381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes * warranty. In no event will the author be held liable for any damages 8381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes * arising from the use of this software. 9381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes * 10381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes * Permission is granted to anyone to use this software for any purpose, 11381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes * including commercial applications, and to alter it and redistribute it 12381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes * freely, subject to the following restrictions: 13381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes * 14381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes * 1. The origin of this software must not be misrepresented; you must not 15381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes * claim that you wrote the original software. If you use this software 16381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes * in a product, an acknowledgment in the product documentation would be 17381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes * appreciated but is not required. 18381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes * 2. Altered source versions must be plainly marked as such, and must not be 19381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes * misrepresented as being the original software. 20381716e9396b55b1adb8235b020c37344f60ab07Elliott Hughes * 3. This notice may not be removed or altered from any source distribution. 219e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project */ 229e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 239e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project#ifndef NO_UNDERLINE 249e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project#define match_init _match_init 259e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project#define longest_match _longest_match 269e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project#endif 279e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 289e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project#define MAX_MATCH (258) 299e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project#define MIN_MATCH (3) 309e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project#define MIN_LOOKAHEAD (MAX_MATCH + MIN_MATCH + 1) 319e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project#define MAX_MATCH_8 ((MAX_MATCH + 7) & ~7) 329e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 339e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project/* stack frame offsets */ 349e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 359e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project#define chainlenwmask 0 /* high word: current chain len */ 369e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project /* low word: s->wmask */ 379e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project#define window 4 /* local copy of s->window */ 389e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project#define windowbestlen 8 /* s->window + bestlen */ 399e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project#define scanstart 16 /* first two bytes of string */ 409e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project#define scanend 12 /* last two bytes of string */ 419e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project#define scanalign 20 /* dword-misalignment of string */ 429e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project#define nicematch 24 /* a good enough match size */ 439e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project#define bestlen 28 /* size of best match so far */ 449e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project#define scan 32 /* ptr to string wanting match */ 459e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 469e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project#define LocalVarsSize (36) 479e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project/* saved ebx 36 */ 489e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project/* saved edi 40 */ 499e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project/* saved esi 44 */ 509e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project/* saved ebp 48 */ 519e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project/* return address 52 */ 529e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project#define deflatestate 56 /* the function arguments */ 539e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project#define curmatch 60 549e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 559e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project/* All the +zlib1222add offsets are due to the addition of fields 569e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * in zlib in the deflate_state structure since the asm code was first written 579e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * (if you compile with zlib 1.0.4 or older, use "zlib1222add equ (-4)"). 589e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * (if you compile with zlib between 1.0.5 and 1.2.2.1, use "zlib1222add equ 0"). 599e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * if you compile with zlib 1.2.2.2 or later , use "zlib1222add equ 8"). 609e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project */ 619e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 629e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project#define zlib1222add (8) 639e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 649e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project#define dsWSize (36+zlib1222add) 659e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project#define dsWMask (44+zlib1222add) 669e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project#define dsWindow (48+zlib1222add) 679e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project#define dsPrev (56+zlib1222add) 689e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project#define dsMatchLen (88+zlib1222add) 699e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project#define dsPrevMatch (92+zlib1222add) 709e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project#define dsStrStart (100+zlib1222add) 719e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project#define dsMatchStart (104+zlib1222add) 729e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project#define dsLookahead (108+zlib1222add) 739e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project#define dsPrevLen (112+zlib1222add) 749e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project#define dsMaxChainLen (116+zlib1222add) 759e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project#define dsGoodMatch (132+zlib1222add) 769e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project#define dsNiceMatch (136+zlib1222add) 779e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 789e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 799e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project.file "match.S" 809e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 819e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project.globl match_init, longest_match 829e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 839e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project.text 849e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 859e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project/* uInt longest_match(deflate_state *deflatestate, IPos curmatch) */ 86ee9e11d0d4e3361533860bf04896abb86a291bfbElliott Hughes.cfi_sections .debug_frame 879e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 889e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Projectlongest_match: 899e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 90ee9e11d0d4e3361533860bf04896abb86a291bfbElliott Hughes.cfi_startproc 919e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project/* Save registers that the compiler may be using, and adjust %esp to */ 929e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project/* make room for our stack frame. */ 939e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 949e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project pushl %ebp 95ee9e11d0d4e3361533860bf04896abb86a291bfbElliott Hughes .cfi_def_cfa_offset 8 96ee9e11d0d4e3361533860bf04896abb86a291bfbElliott Hughes .cfi_offset ebp, -8 979e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project pushl %edi 98ee9e11d0d4e3361533860bf04896abb86a291bfbElliott Hughes .cfi_def_cfa_offset 12 999e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project pushl %esi 100ee9e11d0d4e3361533860bf04896abb86a291bfbElliott Hughes .cfi_def_cfa_offset 16 1019e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project pushl %ebx 102ee9e11d0d4e3361533860bf04896abb86a291bfbElliott Hughes .cfi_def_cfa_offset 20 1039e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project subl $LocalVarsSize, %esp 104ee9e11d0d4e3361533860bf04896abb86a291bfbElliott Hughes .cfi_def_cfa_offset LocalVarsSize+20 1059e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 1069e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project/* Retrieve the function arguments. %ecx will hold cur_match */ 1079e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project/* throughout the entire function. %edx will hold the pointer to the */ 1089e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project/* deflate_state structure during the function's setup (before */ 1099e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project/* entering the main loop). */ 1109e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 1119e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project movl deflatestate(%esp), %edx 1129e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project movl curmatch(%esp), %ecx 1139e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 1149e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project/* uInt wmask = s->w_mask; */ 1159e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project/* unsigned chain_length = s->max_chain_length; */ 1169e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project/* if (s->prev_length >= s->good_match) { */ 1179e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project/* chain_length >>= 2; */ 1189e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project/* } */ 119ee9e11d0d4e3361533860bf04896abb86a291bfbElliott Hughes 1209e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project movl dsPrevLen(%edx), %eax 1219e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project movl dsGoodMatch(%edx), %ebx 1229e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project cmpl %ebx, %eax 1239e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project movl dsWMask(%edx), %eax 1249e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project movl dsMaxChainLen(%edx), %ebx 1259e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project jl LastMatchGood 1269e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project shrl $2, %ebx 1279e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source ProjectLastMatchGood: 1289e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 1299e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project/* chainlen is decremented once beforehand so that the function can */ 1309e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project/* use the sign flag instead of the zero flag for the exit test. */ 1319e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project/* It is then shifted into the high word, to make room for the wmask */ 1329e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project/* value, which it will always accompany. */ 1339e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 1349e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project decl %ebx 1359e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project shll $16, %ebx 1369e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project orl %eax, %ebx 1379e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project movl %ebx, chainlenwmask(%esp) 1389e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 1399e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project/* if ((uInt)nice_match > s->lookahead) nice_match = s->lookahead; */ 1409e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 1419e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project movl dsNiceMatch(%edx), %eax 1429e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project movl dsLookahead(%edx), %ebx 1439e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project cmpl %eax, %ebx 1449e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project jl LookaheadLess 1459e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project movl %eax, %ebx 1469e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source ProjectLookaheadLess: movl %ebx, nicematch(%esp) 1479e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 1489e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project/* register Bytef *scan = s->window + s->strstart; */ 1499e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 1509e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project movl dsWindow(%edx), %esi 1519e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project movl %esi, window(%esp) 1529e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project movl dsStrStart(%edx), %ebp 1539e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project lea (%esi,%ebp), %edi 1549e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project movl %edi, scan(%esp) 1559e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 1569e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project/* Determine how many bytes the scan ptr is off from being */ 1579e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project/* dword-aligned. */ 1589e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 1599e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project movl %edi, %eax 1609e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project negl %eax 1619e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project andl $3, %eax 1629e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project movl %eax, scanalign(%esp) 1639e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 1649e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project/* IPos limit = s->strstart > (IPos)MAX_DIST(s) ? */ 1659e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project/* s->strstart - (IPos)MAX_DIST(s) : NIL; */ 1669e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 1679e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project movl dsWSize(%edx), %eax 1689e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project subl $MIN_LOOKAHEAD, %eax 1699e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project subl %eax, %ebp 1709e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project jg LimitPositive 1719e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project xorl %ebp, %ebp 1729e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source ProjectLimitPositive: 1739e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 1749e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project/* int best_len = s->prev_length; */ 1759e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 1769e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project movl dsPrevLen(%edx), %eax 1779e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project movl %eax, bestlen(%esp) 1789e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 1799e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project/* Store the sum of s->window + best_len in %esi locally, and in %esi. */ 1809e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 1819e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project addl %eax, %esi 1829e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project movl %esi, windowbestlen(%esp) 1839e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 1849e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project/* register ush scan_start = *(ushf*)scan; */ 1859e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project/* register ush scan_end = *(ushf*)(scan+best_len-1); */ 1869e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project/* Posf *prev = s->prev; */ 1879e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 1889e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project movzwl (%edi), %ebx 1899e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project movl %ebx, scanstart(%esp) 1909e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project movzwl -1(%edi,%eax), %ebx 1919e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project movl %ebx, scanend(%esp) 1929e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project movl dsPrev(%edx), %edi 1939e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 1949e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project/* Jump into the main loop. */ 1959e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 1969e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project movl chainlenwmask(%esp), %edx 1979e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project jmp LoopEntry 1989e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 1999e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project.balign 16 2009e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 2019e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project/* do { 2029e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * match = s->window + cur_match; 2039e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * if (*(ushf*)(match+best_len-1) != scan_end || 2049e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * *(ushf*)match != scan_start) continue; 2059e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * [...] 2069e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * } while ((cur_match = prev[cur_match & wmask]) > limit 2079e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * && --chain_length != 0); 2089e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * 2099e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * Here is the inner loop of the function. The function will spend the 2109e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * majority of its time in this loop, and majority of that time will 2119e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * be spent in the first ten instructions. 2129e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * 2139e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * Within this loop: 2149e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * %ebx = scanend 2159e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * %ecx = curmatch 2169e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * %edx = chainlenwmask - i.e., ((chainlen << 16) | wmask) 2179e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * %esi = windowbestlen - i.e., (window + bestlen) 2189e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * %edi = prev 2199e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * %ebp = limit 2209e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project */ 2219e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source ProjectLookupLoop: 2229e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project andl %edx, %ecx 2239e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project movzwl (%edi,%ecx,2), %ecx 2249e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project cmpl %ebp, %ecx 2259e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project jbe LeaveNow 2269e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project subl $0x00010000, %edx 2279e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project js LeaveNow 2289e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source ProjectLoopEntry: movzwl -1(%esi,%ecx), %eax 2299e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project cmpl %ebx, %eax 2309e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project jnz LookupLoop 2319e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project movl window(%esp), %eax 2329e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project movzwl (%eax,%ecx), %eax 2339e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project cmpl scanstart(%esp), %eax 2349e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project jnz LookupLoop 2359e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 2369e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project/* Store the current value of chainlen. */ 2379e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 2389e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project movl %edx, chainlenwmask(%esp) 2399e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 2409e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project/* Point %edi to the string under scrutiny, and %esi to the string we */ 2419e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project/* are hoping to match it up with. In actuality, %esi and %edi are */ 2429e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project/* both pointed (MAX_MATCH_8 - scanalign) bytes ahead, and %edx is */ 2439e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project/* initialized to -(MAX_MATCH_8 - scanalign). */ 2449e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 2459e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project movl window(%esp), %esi 2469e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project movl scan(%esp), %edi 2479e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project addl %ecx, %esi 2489e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project movl scanalign(%esp), %eax 2499e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project movl $(-MAX_MATCH_8), %edx 2509e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project lea MAX_MATCH_8(%edi,%eax), %edi 2519e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project lea MAX_MATCH_8(%esi,%eax), %esi 2529e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 2539e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project/* Test the strings for equality, 8 bytes at a time. At the end, 2549e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * adjust %edx so that it is offset to the exact byte that mismatched. 2559e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * 2569e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * We already know at this point that the first three bytes of the 2579e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * strings match each other, and they can be safely passed over before 2589e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * starting the compare loop. So what this code does is skip over 0-3 2599e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * bytes, as much as necessary in order to dword-align the %edi 2609e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * pointer. (%esi will still be misaligned three times out of four.) 2619e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * 2629e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * It should be confessed that this loop usually does not represent 2639e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * much of the total running time. Replacing it with a more 2649e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * straightforward "rep cmpsb" would not drastically degrade 2659e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project * performance. 2669e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project */ 2679e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source ProjectLoopCmps: 2689e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project movl (%esi,%edx), %eax 2699e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project xorl (%edi,%edx), %eax 2709e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project jnz LeaveLoopCmps 2719e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project movl 4(%esi,%edx), %eax 2729e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project xorl 4(%edi,%edx), %eax 2739e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project jnz LeaveLoopCmps4 2749e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project addl $8, %edx 2759e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project jnz LoopCmps 2769e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project jmp LenMaximum 2779e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source ProjectLeaveLoopCmps4: addl $4, %edx 2789e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source ProjectLeaveLoopCmps: testl $0x0000FFFF, %eax 2799e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project jnz LenLower 2809e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project addl $2, %edx 2819e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project shrl $16, %eax 2829e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source ProjectLenLower: subb $1, %al 2839e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project adcl $0, %edx 2849e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 2859e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project/* Calculate the length of the match. If it is longer than MAX_MATCH, */ 2869e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project/* then automatically accept it as the best possible match and leave. */ 2879e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 2889e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project lea (%edi,%edx), %eax 2899e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project movl scan(%esp), %edi 2909e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project subl %edi, %eax 2919e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project cmpl $MAX_MATCH, %eax 2929e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project jge LenMaximum 2939e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 2949e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project/* If the length of the match is not longer than the best match we */ 2959e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project/* have so far, then forget it and return to the lookup loop. */ 2969e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 2979e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project movl deflatestate(%esp), %edx 2989e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project movl bestlen(%esp), %ebx 2999e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project cmpl %ebx, %eax 3009e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project jg LongerMatch 3019e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project movl windowbestlen(%esp), %esi 3029e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project movl dsPrev(%edx), %edi 3039e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project movl scanend(%esp), %ebx 3049e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project movl chainlenwmask(%esp), %edx 3059e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project jmp LookupLoop 3069e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 3079e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project/* s->match_start = cur_match; */ 3089e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project/* best_len = len; */ 3099e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project/* if (len >= nice_match) break; */ 3109e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project/* scan_end = *(ushf*)(scan+best_len-1); */ 3119e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 3129e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source ProjectLongerMatch: movl nicematch(%esp), %ebx 3139e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project movl %eax, bestlen(%esp) 3149e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project movl %ecx, dsMatchStart(%edx) 3159e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project cmpl %ebx, %eax 3169e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project jge LeaveNow 3179e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project movl window(%esp), %esi 3189e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project addl %eax, %esi 3199e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project movl %esi, windowbestlen(%esp) 3209e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project movzwl -1(%edi,%eax), %ebx 3219e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project movl dsPrev(%edx), %edi 3229e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project movl %ebx, scanend(%esp) 3239e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project movl chainlenwmask(%esp), %edx 3249e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project jmp LookupLoop 3259e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 3269e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project/* Accept the current string, with the maximum possible length. */ 3279e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 3289e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source ProjectLenMaximum: movl deflatestate(%esp), %edx 3299e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project movl $MAX_MATCH, bestlen(%esp) 3309e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project movl %ecx, dsMatchStart(%edx) 3319e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 3329e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project/* if ((uInt)best_len <= s->lookahead) return (uInt)best_len; */ 3339e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project/* return s->lookahead; */ 3349e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 3359e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source ProjectLeaveNow: 3369e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project movl deflatestate(%esp), %edx 3379e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project movl bestlen(%esp), %ebx 3389e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project movl dsLookahead(%edx), %eax 3399e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project cmpl %eax, %ebx 3409e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project jg LookaheadRet 3419e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project movl %ebx, %eax 3429e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source ProjectLookaheadRet: 3439e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 3449e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project/* Restore the stack and return from whence we came. */ 3459e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project 3469e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project addl $LocalVarsSize, %esp 347ee9e11d0d4e3361533860bf04896abb86a291bfbElliott Hughes .cfi_def_cfa_offset 20 3489e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project popl %ebx 349ee9e11d0d4e3361533860bf04896abb86a291bfbElliott Hughes .cfi_def_cfa_offset 16 3509e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project popl %esi 351ee9e11d0d4e3361533860bf04896abb86a291bfbElliott Hughes .cfi_def_cfa_offset 12 3529e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project popl %edi 353ee9e11d0d4e3361533860bf04896abb86a291bfbElliott Hughes .cfi_def_cfa_offset 8 3549e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Project popl %ebp 355ee9e11d0d4e3361533860bf04896abb86a291bfbElliott Hughes .cfi_def_cfa_offset 4 356ee9e11d0d4e3361533860bf04896abb86a291bfbElliott Hughes.cfi_endproc 3579e38dfa2f95fce609707a0941f10af9a785288deThe Android Open Source Projectmatch_init: ret 358