[PATCH] i386 strtok.S optimization

[Jhair Tocancipa Triana <jhair_tocancipa at gmx dot net>]

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))