first different character in string **give me ASM pleeeeeeeaaase!!!***

[Beeeeeves]

For the masm guys, which I hope will be able to make mincemeat out of this,
please read from the bottom up. It would make my day.
But this is where I'm up to with 'the pecker languages'.

1. tcslen - You are first finding the string lengths of the two strings.
Now, that is going to walk thru the string a character at a time looking for
zero termination. That is an overkill. As long as you're doing this,
there's no point in optimizing. You could very well compare the strings
right then. Try a loop method with character comparisons and time it.
You'll be surprised.

ok, that's something to consider... thanks

2. Your algorithm does the 4-byte boundary alignment. However, if the
string is already 4-byte aligned, your skipper will still go ahead and skip
4 bytes.

eh?
a) the string won't be 4-byte aligned, and
b) it should still work if it is, shouldn't it?

Give me an example of how to call it with some 4-byte aligned strings
(including how to create the 4-byte aligned strings in the first place)
that shows an incorrectness.
Or better still how to write it in assembly language...

I've written a couple of mean functions to do this, they seem to be
working
pretty well (0.6 seconds to execute each of them on strings of 749KB,
where
something had been deleted out of the middle, on a 1.3MHz Duron. That was
with the DLL in release mode.)

Anyone able to beat this with some assembly language?

#define SCALE (long)(sizeof(long) / sizeof(_TCHAR))
long __cdecl FirstDifferentIndex(_TCHAR* str1, _TCHAR* str2)

{

long minlen = min((long)_tcslen(str1), (long)_tcslen(str2)),

minlongs = minlen / SCALE,

i = 0, t = 0;

long* skipper[] = {(long*)str1, (long*)str2};

for(;(i < minlongs) && (skipper[0] == skipper[1]); i++);

for(t = i * SCALE; (t < minlen) && (str1[t] == str2[t]); t++);

return t == minlen ? -1 : t;

}

long _cdecl AmountSameAtEnd(_TCHAR* str1, _TCHAR* str2)

{

long len[] = {(long)_tcslen(str1), (long)_tcslen(str2)},

off[] = {len[0] % SCALE, len[1] % SCALE},

pos[] = {(len[0] - off[0])/SCALE, (len[1] - off[1])/SCALE},

t = 0,

* skipper[] = {

(long*)(str1 + SCALE - off[0]),

(long*)(str2 + SCALE - off[1])};

for(;(pos[0] >= 0) && (pos[1] >= 0) &&

(skipper[0][pos[0]] == skipper[1][pos[1]]);

pos[0]--, pos[1]--);

long fin[] = {

min((pos[0] + 1) * SCALE - 1, len[0] - 1),

min((pos[1] + 1) * SCALE - 1, len[1] - 1)};

for(;(fin[0] >= 0) && (fin[1] >= 0) && (str1[fin[0]] == str2[fin[1]]);

fin[0]--, fin[1]--);

return len[0] - fin[0] - 1; //should be the same as len[1] - fin[1] - 1

}

In a 32 bit environment, the fastest approach would be find the 4-byte
boundary and start reading and comparing 4 bytes at a time. When a mismatch
is found, you'll dig in and compare them at byte/word level (depending on if
your encoding is 8-bit or 16-bit)

In x86 asm, you should use the string optimized lodsb, cmpsb
instructions.

-vJ

 

[Relvinian]

This isn't the most efficient ASM method but it'll do your job. This is
MASM format. From here, you can play with it and learn the hows and whys.

; prototype
;int GetCharOffset(void* array1, void* array2);

GetCharOffset proc uses esi edi A1:dword, A2:dword
mov esi, [A1]
mov edi, [A2]
mov ecx, 0

Loop:
cmp byte ptr [esi+ecx], 0
je EndLoop
cmp byte ptr [edi+ecx], 0
je EndLoop
inc ecx
cmp byte ptr [esi+ecx-1], byte ptr [edi+ecx-1]
jne Loop

EndLoop:
mov eax, ecx
ret
GetCharOffset endp

For the masm guys, which I hope will be able to make mincemeat out of this,
please read from the bottom up. It would make my day.
But this is where I'm up to with 'the pecker languages'.

1. tcslen - You are first finding the string lengths of the two strings.
Now, that is going to walk thru the string a character at a time looking for
zero termination. That is an overkill. As long as you're doing this,
there's no point in optimizing. You could very well compare the strings
right then. Try a loop method with character comparisons and time it.
You'll be surprised.

ok, that's something to consider... thanks

2. Your algorithm does the 4-byte boundary alignment. However, if the
string is already 4-byte aligned, your skipper will still go ahead and skip
4 bytes.

eh?
a) the string won't be 4-byte aligned, and
b) it should still work if it is, shouldn't it?

Give me an example of how to call it with some 4-byte aligned strings
(including how to create the 4-byte aligned strings in the first place)
that shows an incorrectness.
Or better still how to write it in assembly language...

I've written a couple of mean functions to do this, they seem to be
working
pretty well (0.6 seconds to execute each of them on strings of 749KB,
where
something had been deleted out of the middle, on a 1.3MHz Duron. That was
with the DLL in release mode.)

Anyone able to beat this with some assembly language?

#define SCALE (long)(sizeof(long) / sizeof(_TCHAR))
long __cdecl FirstDifferentIndex(_TCHAR* str1, _TCHAR* str2)

{

long minlen = min((long)_tcslen(str1), (long)_tcslen(str2)),

minlongs = minlen / SCALE,

i = 0, t = 0;

long* skipper[] = {(long*)str1, (long*)str2};

for(;(i < minlongs) && (skipper[0] == skipper[1]); i++);

for(t = i * SCALE; (t < minlen) && (str1[t] == str2[t]); t++);

return t == minlen ? -1 : t;

}

long _cdecl AmountSameAtEnd(_TCHAR* str1, _TCHAR* str2)

{

long len[] = {(long)_tcslen(str1), (long)_tcslen(str2)},

off[] = {len[0] % SCALE, len[1] % SCALE},

pos[] = {(len[0] - off[0])/SCALE, (len[1] - off[1])/SCALE},

t = 0,

* skipper[] = {

(long*)(str1 + SCALE - off[0]),

(long*)(str2 + SCALE - off[1])};

for(;(pos[0] >= 0) && (pos[1] >= 0) &&

(skipper[0][pos[0]] == skipper[1][pos[1]]);

pos[0]--, pos[1]--);

long fin[] = {

min((pos[0] + 1) * SCALE - 1, len[0] - 1),

min((pos[1] + 1) * SCALE - 1, len[1] - 1)};

for(;(fin[0] >= 0) && (fin[1] >= 0) && (str1[fin[0]] == str2[fin[1]]);

fin[0]--, fin[1]--);

return len[0] - fin[0] - 1; //should be the same as len[1] - fin[1] - 1

}

In a 32 bit environment, the fastest approach would be find the 4-byte
boundary and start reading and comparing 4 bytes at a time. When a mismatch
is found, you'll dig in and compare them at byte/word level (depending

on
if

your encoding is 8-bit or 16-bit)

In x86 asm, you should use the string optimized lodsb, cmpsb
instructions.

-vJ

"Beeeeeves" <1234512345789123456789> wrote in message
Is there a quick way to find the index of the first character

different
in

two strings?

For instance, if I had the strings
"abcdefghijkl"
and
"abcdefxyz"
I would want the return value to be 6.

Either in C# or C++. (I obviously know how to do it by looping

through
the

characters in the character array, but I was wondering if there was
some
smart-alec memory-manipulation function, asm even, or regexes I could use
that would do it.)

Thanks

 

[Relvinian]

Ooops, the 'jne Loop' should be 'je Loop' instead.

This isn't the most efficient ASM method but it'll do your job. This is
MASM format. From here, you can play with it and learn the hows and whys.

; prototype
;int GetCharOffset(void* array1, void* array2);

GetCharOffset proc uses esi edi A1:dword, A2:dword
mov esi, [A1]
mov edi, [A2]
mov ecx, 0

Loop:
cmp byte ptr [esi+ecx], 0
je EndLoop
cmp byte ptr [edi+ecx], 0
je EndLoop
inc ecx
cmp byte ptr [esi+ecx-1], byte ptr [edi+ecx-1]
jne Loop

EndLoop:
mov eax, ecx
ret
GetCharOffset endp

For the masm guys, which I hope will be able to make mincemeat out of this,
please read from the bottom up. It would make my day.
But this is where I'm up to with 'the pecker languages'.

1. tcslen - You are first finding the string lengths of the two strings.
Now, that is going to walk thru the string a character at a time

looking
for

zero termination. That is an overkill. As long as you're doing this,
there's no point in optimizing. You could very well compare the strings
right then. Try a loop method with character comparisons and time it.
You'll be surprised.

ok, that's something to consider... thanks

2. Your algorithm does the 4-byte boundary alignment. However, if the
string is already 4-byte aligned, your skipper will still go ahead and skip
4 bytes.

eh?
a) the string won't be 4-byte aligned, and
b) it should still work if it is, shouldn't it?

Give me an example of how to call it with some 4-byte aligned strings
(including how to create the 4-byte aligned strings in the first place)
that shows an incorrectness.
Or better still how to write it in assembly language...

I've written a couple of mean functions to do this, they seem to be
working
pretty well (0.6 seconds to execute each of them on strings of 749KB,
where
something had been deleted out of the middle, on a 1.3MHz Duron. That was
with the DLL in release mode.)

Anyone able to beat this with some assembly language?

#define SCALE (long)(sizeof(long) / sizeof(_TCHAR))
long __cdecl FirstDifferentIndex(_TCHAR* str1, _TCHAR* str2)

{

long minlen = min((long)_tcslen(str1), (long)_tcslen(str2)),

minlongs = minlen / SCALE,

i = 0, t = 0;

long* skipper[] = {(long*)str1, (long*)str2};

for(;(i < minlongs) && (skipper[0] == skipper[1]); i++);

for(t = i * SCALE; (t < minlen) && (str1[t] == str2[t]); t++);

return t == minlen ? -1 : t;

}

long _cdecl AmountSameAtEnd(_TCHAR* str1, _TCHAR* str2)

{

long len[] = {(long)_tcslen(str1), (long)_tcslen(str2)},

off[] = {len[0] % SCALE, len[1] % SCALE},

pos[] = {(len[0] - off[0])/SCALE, (len[1] - off[1])/SCALE},

t = 0,

* skipper[] = {

(long*)(str1 + SCALE - off[0]),

(long*)(str2 + SCALE - off[1])};

for(;(pos[0] >= 0) && (pos[1] >= 0) &&

(skipper[0][pos[0]] == skipper[1][pos[1]]);

pos[0]--, pos[1]--);

long fin[] = {

min((pos[0] + 1) * SCALE - 1, len[0] - 1),

min((pos[1] + 1) * SCALE - 1, len[1] - 1)};

for(;(fin[0] >= 0) && (fin[1] >= 0) && (str1[fin[0]] == str2[fin[1]]);

fin[0]--, fin[1]--);

return len[0] - fin[0] - 1; //should be the same as len[1] - fin[1] - 1

}

In a 32 bit environment, the fastest approach would be find the 4-byte
boundary and start reading and comparing 4 bytes at a time. When a
mismatch
is found, you'll dig in and compare them at byte/word level

(depending

on

 

[Vijaye Raji]

eh?

a) the string won't be 4-byte aligned, and
b) it should still work if it is, shouldn't it?

Give me an example of how to call it with some 4-byte aligned strings
(including how to create the 4-byte aligned strings in the first place)
that shows an incorrectness.
Or better still how to write it in assembly language...

What I meant was, if your string was already 4-byte aligned, your skipper is
going to skip 4 bytes and read them byte by byte. A small optimization
here, but your code will still work.

Again, I'm sorry I'm unable to give you ASM at this time, but I'd rather you
worry about the algorithm first, before jumping to ASM.
[Not Tested]
int CompareStrX (TCHAR *str1, TCHAR *str2)
{
int ret = 0;
while (str1[ret] == str2[ret])
{
if (str1[ret] == NULL)
return -1;
ret++;
}

return ret;
}

This will throw out a real tight loop. Compare your previous code to this.
Your C++ compiler will probably generate the most efficient code for this
already and you wouldn't need to write a line of assembly.

-vJ

"Beeeeeves" <1234512345789123456789> wrote in message
[Stripped out]

 

[James Curran]

if (str1[ret] == NULL)

This is a pet peeve of mine. "NULL" refers to an *address* of zero.
Here, what you actually want is a *character* of zero. The official ASCII
name for that is "NUL" (one L). In ANSI C, that line would probably give
you a warning (as NULL as #defined to "(void*)0"). Since C++'s strict
typing manke that definition non-viable and requires a compromised #define
for NULL(of just "0"), you won't get the warning, but it's still just wrong.

--
Truth,
James Curran
Home: www.noveltheory.com Work: www.njtheater.com
Blog: www.honestillusion.com Day Job: www.partsearch.com
(note new day job!)

 

[Vijaye Raji]

True.

Thanks for the correction.

-vJ

if (str1[ret] == NULL)

This is a pet peeve of mine. "NULL" refers to an *address* of zero.
Here, what you actually want is a *character* of zero. The official ASCII
name for that is "NUL" (one L). In ANSI C, that line would probably give
you a warning (as NULL as #defined to "(void*)0"). Since C++'s strict
typing manke that definition non-viable and requires a compromised #define
for NULL(of just "0"), you won't get the warning, but it's still just
wrong.

--
Truth,
James Curran
Home: www.noveltheory.com Work: www.njtheater.com
Blog: www.honestillusion.com Day Job: www.partsearch.com
(note new day job!)