By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
432,384 Members | 845 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 432,384 IT Pros & Developers. It's quick & easy.

first different character in string

P: n/a
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
Nov 16 '05 #1
Share this Question
Share on Google+
15 Replies


P: n/a
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
news:uy******************@TK2MSFTNGP10.phx.gbl...
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

Nov 16 '05 #2

P: n/a

"Vijaye Raji" <no*************@hotmail.com> wrote in message
news:O3*************@TK2MSFTNGP10.phx.gbl...
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)
That's what I've resorted to.

In x86 asm, you should use the string optimized lodsb, cmpsb instructions.
Know any examples?

-vJ

"Beeeeeves" <1234512345789123456789> wrote in message
news:uy******************@TK2MSFTNGP10.phx.gbl...
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


Nov 16 '05 #3

P: n/a
Come on, you know you want to. I'd love to get a bit of assembly language
into this program ;-)

"Vijaye Raji" <no*************@hotmail.com> wrote in message
news:O3*************@TK2MSFTNGP10.phx.gbl...
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
news:uy******************@TK2MSFTNGP10.phx.gbl...
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


Nov 16 '05 #4

P: n/a
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][i] == skipper[1][i]); 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

}

"Vijaye Raji" <no*************@hotmail.com> wrote in message
news:O3*************@TK2MSFTNGP10.phx.gbl...
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
news:uy******************@TK2MSFTNGP10.phx.gbl...
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


Nov 16 '05 #5

P: n/a
I don't have my dev machine in front of me, but I could spot a few problems
in this code.

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.

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.

-vJ
"Beeeeeves" <1234512345789123456789> wrote in message
news:%2****************@TK2MSFTNGP10.phx.gbl...
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][i] == skipper[1][i]); 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

}

"Vijaye Raji" <no*************@hotmail.com> wrote in message
news:O3*************@TK2MSFTNGP10.phx.gbl...
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
news:uy******************@TK2MSFTNGP10.phx.gbl...
> 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
>
>



Nov 16 '05 #6

P: n/a
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...

"Beeeeeves" <1234512345789123456789> wrote in message
news:%2****************@TK2MSFTNGP10.phx.gbl... 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][i] == skipper[1][i]); 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

}

"Vijaye Raji" <no*************@hotmail.com> wrote in message
news:O3*************@TK2MSFTNGP10.phx.gbl...
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
news:uy******************@TK2MSFTNGP10.phx.gbl...
> 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
>
>




Nov 16 '05 #7

P: n/a
p.s. sorry about the readability... quite impressed you made it to be honest
;-)

"Vijaye Raji" <no*************@hotmail.com> wrote in message
news:e5**************@TK2MSFTNGP11.phx.gbl...
I don't have my dev machine in front of me, but I could spot a few problems in this code.

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.

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.

-vJ
"Beeeeeves" <1234512345789123456789> wrote in message
news:%2****************@TK2MSFTNGP10.phx.gbl...
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][i] == skipper[1][i]); 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

}

"Vijaye Raji" <no*************@hotmail.com> wrote in message
news:O3*************@TK2MSFTNGP10.phx.gbl...
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
news:uy******************@TK2MSFTNGP10.phx.gbl...
> 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
>
>



Nov 16 '05 #8

P: n/a
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

"Beeeeeves" <1234512345789123456789> wrote in message
news:Ou**************@TK2MSFTNGP12.phx.gbl...
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...

"Beeeeeves" <1234512345789123456789> wrote in message
news:%2****************@TK2MSFTNGP10.phx.gbl...
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][i] == skipper[1][i]); 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

}

"Vijaye Raji" <no*************@hotmail.com> wrote in message
news:O3*************@TK2MSFTNGP10.phx.gbl...
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
news:uy******************@TK2MSFTNGP10.phx.gbl...
> 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
>
>



Nov 16 '05 #9

P: n/a
Ooops, the 'jne Loop' should be 'je Loop' instead.
"Relvinian" <m@msn.com> wrote in message
news:Du********************@comcast.com...
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

"Beeeeeves" <1234512345789123456789> wrote in message
news:Ou**************@TK2MSFTNGP12.phx.gbl...
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...

"Beeeeeves" <1234512345789123456789> wrote in message
news:%2****************@TK2MSFTNGP10.phx.gbl...
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][i] == skipper[1][i]); 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
}

"Vijaye Raji" <no*************@hotmail.com> wrote in message
news:O3*************@TK2MSFTNGP10.phx.gbl...
> 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
> news:uy******************@TK2MSFTNGP10.phx.gbl...
> > 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
> >
> >
>
>



Nov 16 '05 #10

P: n/a
> 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
news:Ou**************@TK2MSFTNGP12.phx.gbl...
[Stripped out]
Nov 16 '05 #11

P: n/a
"Vijaye Raji" <no*************@hotmail.com> wrote in message
news:%2***************@TK2MSFTNGP11.phx.gbl...
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!)
Nov 16 '05 #12

P: n/a
True.

Thanks for the correction.

-vJ

"James Curran" <Ja*********@mvps.org> wrote in message
news:eJ**************@TK2MSFTNGP09.phx.gbl...
"Vijaye Raji" <no*************@hotmail.com> wrote in message
news:%2***************@TK2MSFTNGP11.phx.gbl...
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!)

Nov 16 '05 #13

P: n/a
Thanks a lot
Any idea how to put it into a C++ function

e.g
int GetCharOffset(void* array1, void* array2

_as

....???????..

}
Nov 16 '05 #14

P: n/a
If you'd tell me how to put it into a C++ function then I could debug it and would be able to understand it

thanks!!!
Nov 16 '05 #15

P: n/a
They are comparing byte by byte. That is what the 'byte ptr' is referencing
in the two 'cmp' statements and the two 'mov' with the cmp al,dl statement.

As for comparing DWORDs instead of BYTEs, there is a more a lot more work
involved. First, you would have to compare the strings byte-by-byte until
you are aligned on a dword boundary then you could check dword-by-dword.
Once you found a non-match, then you would have to take that dword and do a
byte-by-byte check on it to find out which byte isn't the same. In all
this process, you would also have to correctly find a NULL-terminator for
each of the strings while comparing dwords.

There are tricks by anding/oring/etc the dword values to find a
NULL-terminator which can be done to help make the algorythm quicker in this
process.

It can be done and it could be well worth it if the strings you are trying
to compare are long in length. If they are short, (not really sure of
length without testing -- a rough guess would be less then 256 bytes), I
would stay with just a byte comparison.

Just a quick note: if you are running this on a P4 machine, change the 'inc
ecx' to a 'add ecx, 1'. This will speed up the loop a little too. Also, if
this is the full function, you don't need the 'long s = SCALE;'. You can
remove this.

Let me know if you have any more questions.

Relvinian

"Beeeeeeves" <an*******@discussions.microsoft.com> wrote in message
news:CA**********************************@microsof t.com...
That's great Relvinian it's working.
I changed it to:

long _cdecl GetCharOffset(void* str1, void* str2)
{
long s = SCALE;
_asm
{
mov esi, [str1]
mov edi, [str2]
mov ecx, 0
mov eax, ecx
LoopStart:
cmp byte ptr [esi+ecx], 0
je EndLoop
cmp byte ptr [edi+ecx], 0
je EndLoop
inc ecx
mov al, byte ptr [esi+ecx-1]
mov dl, byte ptr [edi+ecx-1]
cmp al, dl
je LoopStart
EndLoop:
mov eax, ecx
}
}

However I'm unsure about:
How it knows what the size of the individual elements it's comparing are. They are presumably bytes? If they are bytes how can I make them DWORDs until it finds a different one, then make them bytes again? (i'm a beginner so please explain it...)
----- Relvinian wrote: -----

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

"Beeeeeves" <1234512345789123456789> wrote in message
news:Ou**************@TK2MSFTNGP12.phx.gbl...
> 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...
>> "Beeeeeves" <1234512345789123456789> wrote in message

> news:%2****************@TK2MSFTNGP10.phx.gbl...
>> 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][i] == skipper[1][i]); 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 >>>> }
>>>> "Vijaye Raji" <no*************@hotmail.com> wrote in message
>> news:O3*************@TK2MSFTNGP10.phx.gbl...
>>> 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
>>> news:uy******************@TK2MSFTNGP10.phx.gbl...
>>>> 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
>>>>>>>>>>>>>>>>>>>>>

Nov 16 '05 #16

This discussion thread is closed

Replies have been disabled for this discussion.