🔒 Locked

Fixing 'strlen' Code [Resolved - Now Discussion Stuff]

Started by Drew_Benton Apr 25, 2005 at 3:06 PM 19 replies 5.6k views

Original Post

Apr 25, 2005 at 3:06 PM

So I've been browsing though some of the older posts in the forums and I cam across this from Magmai Kai Holmlor:

  
  int strlen(const char* cszStr)
  {
	DWORD* p = (DWORD*) cszStr;
	DWORD k,kk;
	
	while(DWORD(p)&3)
		{
		if(*(char*)(p)==0)
			return (char*)(p)-cszStr;
		p = (DWORD*) (((char*)(p)) + 1);
		}
	
	do
		{
		k = *p;
		kk = k + 0x7efefeff;
		k ^= -1;
		k ^= kk;
		p++;
		} while(!(k&0x81010100));
	
	k = *(--p);
	if(!(k&0x000000ff))
		return (char*)(p)-cszStr;
	
	//if(!(k&0x0000ffff)) Thanks Kippesoep! [smile]
        if(!(k&0x0000ff00))
		return (char*)(p)-cszStr+1;
	
	if(!(k&0x00ff0000))
		return (char*)(p)-cszStr+2;
	
	if(!(k&0xff000000))
		return (char*)(p)-cszStr+3;
	
	return (char*)(p)-cszStr;
  }

Looked fairly interesting so I gave it a try. Worked good for the most part, except when the string sent in is one character, as seen in this demo program:


int main( int argc, char* argv[] )
{
	char* str = "";
	// Returns 0 (as expected)
	printf("Length of %s: %i\n", str, __strlen__(str) );

	// Returns 2 (not as expected)
	str = "a";
	printf("Length of %s: %i\n", str, __strlen__(str) );

	// Returns 2 (as expected)
	str = "ab";
	printf("Length of %s: %i\n", str, __strlen__(str) );

	// Returns 100 (as expected)
	str = "1111111111__________1111111111__________1111111111__________1111111111__________1111111111__________";
	printf("Length of %s: %i\n", str, __strlen__(str) );

        // Returns 3 (as expected)
	char temp[256] = { '1', '2', '3', '\0' };
	printf("Length of %s: %i\n", temp, __strlen__(temp) );
}

So does anyone have any ideas to how it can work for a character of length 1? In particular, is this algorithm 'acceptable' to find the length of a string? This is just for knowledge and understanding, so please no "use strlen()" or "use std::string.size()" [wink]. Thanks! [Edited by - Drew_Benton on April 26, 2005 2:34:33 AM]

Kippesoep

Apr 25, 2005 at 3:58 PM

The line

if(!(k&0x0000ffff))

should be

if(!(k&0x0000ff00))

Ready4Dis

Apr 25, 2005 at 4:07 PM

Is that really that much more efficient than just doing:

int strlen(char* cszStr){ int ctr=0; while (*cszStr++)   ++ctr; return ctr;}

Especially considering that most calls to strlen aren't really the cause for a slowdown in a game :P. You could even do something like this if you're concerned about comparing chars vs. integers:

int strlen(char* cszStr){ int ctr=0; unsigned int *ptrStr = (unsigned int*)cszStr; do {  if (!(ptrStr&0x000000ff))   break;  ++ctr;  if (!(ptrStr&0x0000ff00))   break;  ++ctr;  if (!(ptrStr&0x00ff0000))   break;  ++ctr;  if (!(ptrStr&0xff000000))   break;  ++ctr; } return ctr;}

I don't really think that'll be any more efficient though :P.

Drew_Benton

Apr 25, 2005 at 4:12 PM

Quote:
Original post by Kippesoep
The line
if(!(k&0x0000ffff))
should be
if(!(k&0x0000ff00))

[smile] Thanks! That was it. I hope Magmai sees this...

Oh, Ready4Dis, I was only interested in this method because I've never seen it before [wink]. I have yet to play around with other techniques that are the most efficient or fast. I just wanted to see if this does indeed work, as it does thanks to the fix Kippesoep found.

I will be doing further 'research' just for fun. I'll be glad to post my findings on how good this is, but so far, it looks excelent! it's definitly not O( n ) as is when you go though looking for a NULL [grin].

_Madman_

Apr 25, 2005 at 6:05 PM

Sheeeshhh, optimized strlen!!! Use Pascal type strings then, where you store lenght in 1st n bytes...

Deranged

Apr 25, 2005 at 6:16 PM

unsigned int strlen(const char* str) {    const char *s;    for (s = str; *s; ++s)       ;    return (s - str); }

Works well for me.

smart_idiot

Apr 25, 2005 at 6:51 PM

Optimizing strlen is just silly. Needing to go through the entire string just to see how long it is will always be slow no matter how clever you are. Real string implementations store the string's length or a pointer to the end of the string.

Shannon Barber

Apr 25, 2005 at 8:19 PM

Quote:
Original post by _Madman_
Sheeeshhh, optimized strlen!!! Use Pascal type strings then, where you store lenght in 1st n bytes...

I have a shortstring template for that.

Nice Coder

Apr 25, 2005 at 9:37 PM

Thats a really nifty method magmai.

Any chance you could tell us how it actually works?

From,
Nice coder

smart_idiot

Apr 26, 2005 at 1:03 AM

And I mysteriously got logged out somehow. And the code tags that were supposed to make that all nice and pretty vanished from existance.

iMalc

Apr 26, 2005 at 1:21 AM

Quote:
Original post by smart_idiot
Optimizing strlen is just silly. Needing to go through the entire string just to see how long it is will always be slow no matter how clever you are. Real string implementations store the string's length or a pointer to the end of the string.

Yes I agree. This is talked about a lot in some article I read a little while ago.

MaulingMonkey

Apr 26, 2005 at 2:19 AM

Just to play the Devil's advocado... the true way to fix strlen is to remove it completely :-P (although I understand some poor SOBs have to work with legacy code, or just don't feel like rewriting it all...)

To hijack this thread, bastard that I am:

template < typename char_t >class literal{public:    typedef char_t char_type;    typedef size_t size_type;private:    size_type length;    const char_type * data;public:    literal( const literal< char_type > & copy )        : length( copy.length )        , data( copy.data )    {    }    template < size_type array_size >    literal( const char_type (& array) [ array_size ] )        : length( array_size )        , data( array )    {    }    operator const char_type * ( void ) const    {        return data;    }    template < typename char_type >    friend std::basic_string< char_type > & operator=( std::basic_string< char_type > & lhs , const literal< char_type > & rhs )    {        string value( rhs.data , rhs.data + rhs.length );        lhs.swap( value );        return lhs;    }};template < typename char_type , size_t length >literal< char_type > make_literal( const char_type (& l)[ length ] ){    return literal< char_type >( l );}#define DEFINE_THAT_EVIL_UNDERSCORE_THINGY "pretty please with suger on top"#ifdef DEFINE_THAT_EVIL_UNDERSCORE_THINGY#define _( x ) make_literal( x )#endif //def DEFINE_THAT_EVIL_UNDERSCORE_THINGYint main ( int argc , char ** argv ){    string a_string;    a_string = _("I like pie, oh yes I do, lots of pie, for me and you");}

Very basic, but you could extend it as desired.. :).

Drew_Benton

Apr 26, 2005 at 2:23 AM

Quote:
Original post by Anonymous Poster
Magmai_strlen: 11390 ms 95.92%
Ready4Dis_strlen: 29234 ms 246.18%
DerAnged_strlen: 28078 ms 236.45%
std::strlen: 11875 ms 100%

I had done some primitive testing earlier:

#include <windows.h>#include <stdio.h>int __strlen__(const char* cszStr){	DWORD* p = (DWORD*) cszStr;	DWORD k,kk;	while(DWORD(p)&3)	{		if(*(char*)(p)==0)			return (char*)(p)-cszStr;		p = (DWORD*) (((char*)(p)) + 1);	}	do	{		k = *p;		kk = k + 0x7efefeff;		k ^= -1;		k ^= kk;		p++;	}	while(!(k&0x81010100));	k = *(--p);	if(!(k&0x000000ff))		return (char*)(p)-cszStr;	if(!(k&0x0000ff00))		return (char*)(p)-cszStr+1;	if(!(k&0x00ff0000))		return (char*)(p)-cszStr+2;	if(!(k&0xff000000))		return (char*)(p)-cszStr+3;	return (char*)(p)-cszStr;}unsigned int strlen2(const char* str) {    const char *s;    for (s = str; *s; ++s)       ;    return (s - str); }#define SIZE 1073741823int main( int argc, char* argv[] ){	char* str = new char[SIZE];	for( int x=0;x<SIZE;x++)	{		str[x] = rand() % 26 + 65;	}	str[SIZE-1] = '\0';	/*DWORD start = ::GetTickCount();	printf("Length: %i\n", strlen(str) );	DWORD final = GetTickCount() - start;	printf("strlen time: %i\n", final );*/	/*DWORD start = ::GetTickCount();	printf("Length: %i\n", __strlen__(str) );	DWORD final = GetTickCount() - start;	printf("__strlen__ time: %i\n", final );*/	DWORD start = ::GetTickCount();	printf("Length: %i\n", strlen2(str) );	DWORD final = GetTickCount() - start;	printf("strlen2 time: %i\n", final );	delete [] str;	return 0;}/*Length: 1073741823__strlen__ time: 39281Press any key to continue*//*Length: 1073741823strlen time: 50266Press any key to continue*//*Length: 1073741823strlen time: 40703Press any key to continue*//*Length: 1073741823__strlen__ time: 36562Press any key to continue*//*Length: 1073741823__strlen__ time: 37343Press any key to continue*//*Length: 1073741822strlen2 time: 52782Press any key to continue*//*Length: 1073741822strlen2 time: 33985Press any key to continue*/

Weird results when I ran them one after another though, that's why I did them by themselves. Overall looks like Magmai did win [wink].

@MaulingMonkey, very interesting, I will take a look at that later. [smile]

c2_0

Apr 26, 2005 at 5:07 PM

Most C/C++ runtime implementations would most like alreayd be optimized.

For instance, if you're using VC7.1, this is what the source looks like (provided in asm .. for anyone with VC installed: vc\crt\src\[cpu vendor]\strlen.asm)

;***;strlen - return the length of a null-terminated string;;Purpose:;       Finds the length in bytes of the given string, not including;       the final null character.;;       Algorithm:;       int strlen (const char * str);       {;           int length = 0;;;           while( *str++ );                   ++length;;;           return( length );;       };;Entry:;       const char * str - string whose length is to be computed;;Exit:;       EAX = length of the string "str", exclusive of the final null byte;;Uses:;       EAX, ECX, EDX;;Exceptions:;;*******************************************************************************        CODESEG        public  strlenstrlen  proc        .FPO    ( 0, 1, 0, 0, 0, 0 )string  equ     [esp + 4]        mov     ecx,string              ; ecx -> string        test    ecx,3                   ; test if string is aligned on 32 bits        je      short main_loopstr_misaligned:        ; simple byte loop until string is aligned        mov     al,byte ptr [ecx]        add     ecx,1        test    al,al        je      short byte_3        test    ecx,3        jne     short str_misaligned        add     eax,dword ptr 0         ; 5 byte nop to align label below        align   16                      ; should be redundantmain_loop:        mov     eax,dword ptr [ecx]     ; read 4 bytes        mov     edx,7efefeffh        add     edx,eax        xor     eax,-1        xor     eax,edx        add     ecx,4        test    eax,81010100h        je      short main_loop        ; found zero byte in the loop        mov     eax,[ecx - 4]        test    al,al                   ; is it byte 0        je      short byte_0        test    ah,ah                   ; is it byte 1        je      short byte_1        test    eax,00ff0000h           ; is it byte 2        je      short byte_2        test    eax,0ff000000h          ; is it byte 3        je      short byte_3        jmp     short main_loop         ; taken if bits 24-30 are clear and bit                                        ; 31 is setbyte_3:        lea     eax,[ecx - 1]        mov     ecx,string        sub     eax,ecx        retbyte_2:        lea     eax,[ecx - 2]        mov     ecx,string        sub     eax,ecx        retbyte_1:        lea     eax,[ecx - 3]        mov     ecx,string        sub     eax,ecx        retbyte_0:        lea     eax,[ecx - 4]        mov     ecx,string        sub     eax,ecx        retstrlen  endp

- EDIT -
Changed from code to source tags

msn12b

Apr 26, 2005 at 5:07 PM

Quote:
Original post by Anonymous Poster
i'm really no expert when it comes to 64 bit platforms.. but is this code safe for 64 bit? is someone able to comment on this issue?

It's not safe for any bits.

MSN

MaulingMonkey

Apr 26, 2005 at 5:24 PM

Quote:
Original post by Drew_Benton@MaulingMonkey, very interesting, I will take a look at that later. [smile]

The powerful aspect of it is extremely simple, really. It just takes an argument (specifically, an array, by reference), and uses a template argument so that any size array can be passed. The alternative, taking a pointer to the starting element, requires counting - aka strlen. The nice thing about it is that the length is calculated at compile time with this method rather than at run time with an O(n) function.

On a side note, I never actually use that template. I spend my time optimizing things that actually need optimizing, not string manipulation routines :P.

As a side note, assigning a string to a literal tagged in this manner has one minor difference: it assigns all of the array, rather than just until the last null. That is:

str::string test_string_1 , test_string_2;const char[] test_string_1_value = "Test string";const char[] test_string_2_value = "Test string\0Testy testy testy!";test_string_1 = _( test_string_1_value );test_string_2 = _( test_string_2_value );assert( strcmp( test_string_1.c_str() , test_string_2.c_str() ) == 0 ); //will succeed, only compares up to the null terminator.assert( test_string_1 == test_string_2 ); //will fail, as it compares the entire contents of the string, even past null

Whereas both asserts will succeed if the _(...) wrapper is removed.

Shannon Barber

May 1, 2005 at 10:52 AM

Quote:
Original post by Anonymous Poster
i'm really no expert when it comes to 64 bit platforms.. but is this code safe for 64 bit? is someone able to comment on this issue?

It needs to be extended to work optimally on a 64bit register machine, instead of &3 you'd need &7, the various bit-mask would need to be extended as well, e.g. 0x7efefeff would become 0x7efefefefefefeff.

I've wanted to sit down and explain how it works, but I just don't have the time right now to go in detail. The first loop aligns the string, then the seocnd loop checks 4 bytes at a time. If someone wants to understand it, you should look at the binary encoding, and see how the bits flip as the algorithm progresses, it essentially makes a sequence of 'catch' bits and filter the data in the such a way to set these bit if the byte is not null. By the nature of the algorithm, we can only tell if a byte is not null, but cannot tell what the first null byte is, so we have to go find it with the last 4 if statements (those statements can be optimized further, that's a slow way to check).

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.