This is the mail archive of the
libc-alpha@sources.redhat.com
mailing list for the glibc project.
[PATCH] i386 strtok.S optimization
- From: Jhair Tocancipa Triana <jhair_tocancipa at gmx dot net>
- To: Glibc Alpha <libc-alpha at sources dot redhat dot com>
- Date: 10 Aug 2002 11:42:13 +0000
- Subject: [PATCH] i386 strtok.S optimization
Hi,
This short patch drops out the current loop to terminate tokens. When
a delimiter is found the token is terminated immediately.
We need now to distinguish between NULL and not NULL tokens (the
latter not allowed by the definition of strtok). This results in a
shorter version of strtok.S, though.
I tested this change against string/tst-strtok.c and
string/tst-strtok.c with success (and against other tests from myself
;-)).
Comments are welcome,
--
--Jhair
2002-08-10 Jhair Tocancipa <jhair_tocancipa@gmx.net>
* sysdeps/i386/strtok.S: Don't use a new loop to terminate
tokens. Get tokens in one pass through the string.
--- sysdeps/i386/strtok.S 6 Jul 2001 04:55:52
+++ sysdeps/i386/strtok.S 10 Aug 2002 08:59:53
@@ -3,7 +3,8 @@
Copyright (C) 1996, 1997, 1998, 2000, 2001 Free Software Foundation, Inc.
This file is part of the GNU C Library.
Contributed by Ulrich Drepper <drepper@cygnus.com>, 1996.
-
+ New optimization by Jhair Tocancipa <jhair_tocancipa@gmx.net>, 2002.
+
The GNU C Library is free software; you can redistribute it and/or
modify it under the terms of the GNU Lesser General Public
License as published by the Free Software Foundation; either
@@ -189,132 +190,100 @@
pushl $0
pushl $0
-/* For understanding the following code remember that %ecx == 0 now.
- Although all the following instruction only modify %cl we always
- have a correct zero-extended 32-bit value in %ecx. */
-
-L(2): movb (%eax), %cl /* get byte from stopset */
- testb %cl, %cl /* is NUL char? */
- jz L(1_1) /* yes => start compare loop */
- movb %cl, (%esp,%ecx) /* set corresponding byte in stopset table */
+L(2):
+ movb (%eax), %cl /* get byte from stopset */
+ testb %cl, %cl /* is NUL char? */
+ jz L(3) /* yes => look for delimiters in the string */
+ movb %cl, (%esp, %ecx) /* no => put the byte in our flags table */
movb 1(%eax), %cl /* get byte from stopset */
- testb $0xff, %cl /* is NUL char? */
- jz L(1_2) /* yes => start compare loop */
- movb %cl, (%esp,%ecx) /* set corresponding byte in stopset table */
+ testb $0xff, %cl /* is NUL char? */
+ jz L(3) /* yes => look for delimiters in the string */
+ movb %cl, (%esp, %ecx) /* no => put the byte in our flags table */
movb 2(%eax), %cl /* get byte from stopset */
testb $0xff, %cl /* is NUL char? */
- jz L(1_3) /* yes => start compare loop */
- movb %cl, (%esp,%ecx) /* set corresponding byte in stopset table */
+ jz L(3) /* yes => look for delimiters in the string */
+ mov %cl, (%esp, %ecx) /* no => put the byte in our flags table */
- movb 3(%eax), %cl /* get byte from stopset */
- addl $4, %eax /* increment stopset pointer */
- movb %cl, (%esp,%ecx) /* set corresponding byte in stopset table */
+ movb 3(%eax), %cl /* get byte from stopset */
testb $0xff, %cl /* is NUL char? */
- jnz L(2) /* no => process next dword from stopset */
-
-#if __BOUNDED_POINTERS__
- jmp L(1_0) /* pointer is correct for bounds check */
-L(1_3): incl %eax /* adjust pointer for bounds check */
-L(1_2): incl %eax /* ditto */
-L(1_1): incl %eax /* ditto */
-L(1_0): CHECK_BOUNDS_HIGH (%eax, DELIM(%esp), jbe)
-#else
-L(1_3):; L(1_2):; L(1_1): /* fall through */
-#endif
- leal -4(%edx), %eax /* prepare loop */
-
- /* We use a neat trick for the following loop. Normally we would
- have to test for two termination conditions
- 1. a character in the stopset was found
- and
- 2. the end of the string was found
- As a sign that the character is in the stopset we store its
- value in the table. The value of NUL is NUL so the loop
- terminates for NUL in every case. */
-
-L(3): addl $4, %eax /* adjust pointer for full loop round */
-
- movb (%eax), %cl /* get byte from string */
- testb %cl, (%esp,%ecx) /* is it contained in stopset? */
- jz L(4) /* no => start of token */
-
- movb 1(%eax), %cl /* get byte from string */
- testb %cl, (%esp,%ecx) /* is it contained in stopset? */
- jz L(5) /* no => start of token */
-
- movb 2(%eax), %cl /* get byte from string */
- testb %cl, (%esp,%ecx) /* is it contained in stopset? */
- jz L(6) /* no => start of token */
-
- movb 3(%eax), %cl /* get byte from string */
- testb %cl, (%esp,%ecx) /* is it contained in stopset? */
- jnz L(3) /* yes => start of loop */
-
- incl %eax /* adjust pointer */
-L(6): incl %eax
-L(5): incl %eax
-
- /* Now we have to terminate the string. */
-
-L(4): leal -4(%eax), %edx /* We use %EDX for the next run. */
+ jz L(3) /* yes => look for delimiters in the string */
+ mov %cl, (%esp, %ecx) /* no => put the byte in our flags table */
+ addl $0x4, %eax /* increment stopset pointer */
+ jmp L(2)
-L(7): addl $4, %edx /* adjust pointer for full loop round */
+L(3):
+ movl %edx, %eax /* save the begin of string */
+L(3_5):
movb (%edx), %cl /* get byte from string */
- cmpb %cl, (%esp,%ecx) /* is it contained in skipset? */
- je L(8) /* yes => return */
+ cmpb %cl, (%esp, %ecx) /* is it contained in stopset? */
+ je L(3_1) /* a (possibly NULL) token was found */
movb 1(%edx), %cl /* get byte from string */
- cmpb %cl, (%esp,%ecx) /* is it contained in skipset? */
- je L(9) /* yes => return */
+ cmpb %cl, (%esp, %ecx) /* is it contained in stopset? */
+ je L(3_2) /* a (possibly NULL) token was found */
- movb 2(%edx), %cl /* get byte from string */
- cmpb %cl, (%esp,%ecx) /* is it contained in skipset? */
- je L(10) /* yes => return */
-
- movb 3(%edx), %cl /* get byte from string */
- cmpb %cl, (%esp,%ecx) /* is it contained in skipset? */
- jne L(7) /* no => start loop again */
-
- incl %edx /* adjust pointer */
-L(10): incl %edx
-L(9): incl %edx
-
-L(8): /* Remove the stopset table. */
- addl $256, %esp
-
- cmpl %eax, %edx
- je L(returnNULL) /* There was no token anymore. */
-
- movb $0, (%edx) /* Terminate string. */
-
- /* Are we at end of string? */
- cmpb $0, %cl
- je L(11)
-
- incl %edx
-L(11):
-
- /* Store the pointer to the next character. */
+ movb 2(%edx), %cl /* get byte from string */
+ cmpb %cl, (%esp, %ecx) /* is it contained in stopset? */
+ je L(3_3) /* a (possibly NULL) token was found */
+
+ movb 3(%edx), %cl /* get byte from string */
+ cmpb %cl, (%esp, %ecx) /* is it contained in stopset? */
+ je L(3_4) /* a (possibly NULL) token was found */
+ addl $0x4, %edx /* increment string pointer */
+ jmp L(3_5)
+
+L(3_4):
+ incl %edx /* adjust string pointer */
+L(3_3):
+ incl %edx /* adjust string pointer */
+L(3_2):
+ incl %edx /* adjust string pointer */
+L(3_1):
+ cmpb $0x0, 0(%edx) /* is the end of string? */
+ je L(5)
+
+ leal 1(%edx), %edx
#ifdef USE_AS_STRTOK_R
- movl SAVE(%esp), %ecx
+ /* +0x100 since we haven't flushed the flags table yet */
+ movl SAVE+0x100(%esp), %ecx
#endif
- movl %edx, SAVE_PTR
+ movl %edx, SAVE_PTR /* store the pointer to the next character */
CHECK_BOUNDS_HIGH (%edx, SAVE_PTR, jb)
RETURN_BOUNDED_POINTER (SAVE_PTR)
+
+ leal -1(%edx), %ecx /* we point to the last 'delimiter' found */
+ cmpl %ecx, %eax /* is a NULL token? */
+ je L(4) /* look forth for tokens */
+ movb $0x0, -1(%edx) /* terminate the valid token found */
L(epilogue):
+ addl $0x100, %esp /* free the flags table */
#if !defined USE_AS_STRTOK_R && defined PIC
popl %ebx
#endif
LEAVE
RET_PTR
+
+L(4):
+ xorl %ecx, %ecx /* we use %cl to match delimiters */
+ jmp L(3)
+L(5):
+#ifdef USE_AS_STRTOK_R
+ movl SAVE+0x100(%esp), %ecx
+#endif
+ movl %edx, SAVE_PTR /* store the pointer to the next character */
+ CHECK_BOUNDS_HIGH (%edx, SAVE_PTR, jb)
+ RETURN_BOUNDED_POINTER (SAVE_PTR)
+ cmpl %edx, %eax /* is the last token? */
+ jne L(epilogue) /* return the last token */
+
L(returnNULL):
- xorl %eax, %eax
+ xorl %eax, %eax /* we return NULL */
RETURN_NULL_BOUNDED_POINTER
jmp L(epilogue)
-
-END (BP_SYM (FUNCTION))
+
+END (BP_SYM (FUNCTION))