StrStrIW (unicode)

[KSS]

I use StrStrIW in my code, but this function is dramatically slow  :'(
I am try to find other function, code, piece of code — but not successful :(

I am looked in this forum for NOT Unicode function: i am found it but can't transform it in Unicode version.

All my trouble is UNICODE :)

Can anyone help me with good links or some algorithms ?

P.S. Google is my F.R.I.E.N.D. — I know this)))

[jj2007]

The CRT equivalents are usually a lot faster. Here is a working snippet, but I haven't timed it.

Code Select Expand

include \masm32\MasmBasic\MasmBasic.inc ; http://www.masm32.com/board/index.php?topic=12460

.code
start:
invoke crt_wcsstr, wChr$("Hello, this is Unicode!"), wChr$("this")
invoke MessageBoxW, 0, eax, wChr$("Result:"), MB_OK
Exit

end start


[KSS]

jj2007, thanks you for reply, but:
crt_wcsstr is case sensitive, but i need case insensitive Unicode function.

[hutch--]

A search algo in masm for unicode works the same way as a ansi version except that you use WORD (16 bit) instead of BYTE characters. Just remember that all of the counts are still in byte values so if you have 1000 unicode characters it takes twice as many bytes to make a working valid buffer.

[donkey]

jj2007, thanks you for reply, but:
crt_wcsstr is case sensitive, but i need case insensitive Unicode function.

Case mapping and folding are very complex in Unicode if you are using a western alphabet you are probably better off treating the characters as WORD sized ansi characters otherwise you can look at converting both strings to lower case then performing your search. The unicode case map is available here:

http://www.unicode.org/Public/3.2-Update/UnicodeData-3.2.0.txt

[jj2007]

jj2007, thanks you for reply, but:
crt_wcsstr is case sensitive, but i need case insensitive Unicode function.

Sorry, I had overlooked that. Here is a snippet that does case insensitive search, but it is probably slow. Writing one will take more time, but it could be as fast as the ANSI version. As Edgar pointed out, "real" Unicode is a different animal - we are talking of WORD comparisons here. What exactly do you want to achieve?

Code Select Expand

include \masm32\MasmBasic\MasmBasic.inc ; http://www.masm32.com/board/index.php?topic=12460

.data?
lcBuffer db 1024 dup(?)

.code
start:
if 1 ; either way will work - wChr$ is one line shorter...
wData wSearch$, "You won't believe it but THIS is Unicode", 0 ; use in code section
mov esi, offset wSearch$
else
mov esi, wChr$("You won't believe it but THIS is Unicode")
endif
mov edi, offset lcBuffer
push esi ; save the pointer to the original string
push edi
mov ecx, wLen(esi) ; returns chars, not bytes
rep movsw
pop edi
invoke CharLowerW, edi ; convert to lowercase
invoke crt_wcsstr, edi, wChr$("this") ; get the Instr
pop esi ; get pointer to the original string
sub eax, edi ; wcsstr returns an absolute address, so we must subtract edi
add esi, eax ; there we are: the address in the original string where THIS was found
invoke MessageBoxW, 0, esi, wChr$("Result:"), MB_OK
Exit

end start


Have a look at LCMapString, too.

[MichaelW]

StrStrIW really is slow, and the ANSI version is even slower. Running on a P3, and compared to the CRT wcsstr function preceded with two calls to _wcslwr, StrStrIW is 4.3X slower and StrStrIA is 11X slower.

[KSS]

To all,
I am write some kind of Sandbox for application — so I am need true unicode support (I am hooked ZwCreateFile and other system function)

StrStrIW really is slow, and the ANSI version is even slower. Running on a P3, and compared to the CRT wcsstr function preceded with two calls to _wcslwr, StrStrIW is 4.3X slower and StrStrIA is 11X slower.

Yes it is :) My app work great, but I am want more speed :) (My sandbox run on nettop with Atom CPU so speed is need)

jj2007, I am thinking about use CharLowerW and then call wcsstr from NTDLL.DLL (on my Windows7 this is fast function), but I am want really speed :)  So I am tring to find more speedy way.

Today after work I am will try to do something and write some speed test.

Thank to you all man for help me :)

[jj2007]

StrStrIW really is slow, and the ANSI version is even slower. Running on a P3, ...

Celeron M for comparison:

Code Select Expand


1924  StrStrIW
4143  StrStrIA
611   wcslwr+wcsstr


[ecube]

can't this be done easily with szLower and BinSearch? or am I miss understanding what this function does?

[jj2007]

Now it's lingo's turn :bg

Code Select Expand

Intel(R) Celeron(R) M CPU        420  @ 1.60GHz (SSE3)
1944     for StrStrIW
4185     for StrStrIA
77       for InstrCiW
627      for wcsstr

[KSS]

jj2007, oh man you are really fast, thank you  :U
My result:

Code Select Expand

AMD Athlon(tm) 64 X2 Dual Core Processor 4600+ (SSE3)    [2.96GHz]
6201     for StrStrIW
10187    for StrStrIA
78       for InstrCiW
514      for wcsstr

104 bytes

I am looked at the code and think about convert to lower case: Is this fully support unicode convert to lowercase?
I am understand why you use "or eax, 00000020h   ; to lowercase":

Code Select Expand


00C0;LATIN CAPITAL LETTER A WITH GRAVE;Lu;0;L;0041 0300;;;;N;LATIN CAPITAL LETTER A GRAVE;;;00E0;
00E0;LATIN SMALL LETTER A WITH GRAVE;Ll;0;L;0061 0300;;;;N;LATIN SMALL LETTER A GRAVE;;00C0;;00C0

so 00E0 - 00C0 = 0020, but:

Code Select Expand

0100;LATIN CAPITAL LETTER A WITH MACRON;Lu;0;L;0041 0304;;;;N;LATIN CAPITAL LETTER A MACRON;;;0101;
0101;LATIN SMALL LETTER A WITH MACRON;Ll;0;L;0061 0304;;;;N;LATIN SMALL LETTER A MACRON;;0100;;0100

How you convert to lower char in this case?
May be I am not understand something?

link: http://www.unicode.org/Public/3.2-Update/UnicodeData-3.2.0.txt

some comment to code:

Code Select Expand

    counter_begin 1000, HIGH_PRIORITY_CLASS
      invoke crt__wcslwr, ADDR first
      invoke crt__wcslwr, ADDR search
      invoke crt_wcsstr, ADDR first, ADDR search
    counter_end
Function StrStrIW() not change original string, so wee must allocate buffers for our strings, copy them to, and then only call wcslwr, so time is more then 514 (for my result)
After do this my result are:

Code Select Expand

AMD Athlon(tm) 64 X2 Dual Core Processor 4600+ (SSE3)
6151     for StrStrIW
9233     for StrStrIA
78       for InstrCiW
15061    for wcsstr
So slow wcsstr :(  Maybe I used slow memory allocation?
See attach

[jj2007]

So slow wcsstr :(  Maybe I used slow memory allocation?

Hi KSS,
Yes, the downside of wcsstr is that, if you don't want to destroy your original string, you need a copy - and that costs many cycles.

InstrCiW can be so fast because it treats Unicode as word-sized Ansi, as mentioned by Edgar (Donkey) above. The downside is that as soon as you use "real" Unicode, you are in trouble as the or 32 method doesn't work any more.

The only alternative I can offer is the MasmBasic wInstr function:

   ; wInstr returns absolute address in eax, char position in edx (1-based, as usual in Basic)
   void wInstr(1, offset first, offset search, 1)  ; 1=case-insensitive
   mov esi, eax
   invoke MessageBoxW, 0, esi, wStr$("The brother is at position %i", edx), MB_OK

It works with "real" Unicode, and the timings are quite reasonable:

Code Select Expand

My Other Brother Darryl
BrOtHeR
my other brother darryl
Brother

18      result StrStrIW
9       result StrStrIA
10      result wInstr (MasmBasic)
18      result InstrCiW

Intel(R) Pentium(R) 4 CPU 3.40GHz (SSE3)
6424     for StrStrIW
7207     for StrStrIA
834      for wInstr (MasmBasic)
91       for InstrCiW
957      for wcsstr - in-buffer conversion

108 bytes for InstrCiW - short and fast but works with 'or 32 lowercase'

I am curious to see Atom timings :bg

[KSS]

I am curious to see Atom timings  :bg

Code Select Expand

Intel(R) Celeron(R) M processor          900MHz (SSE2)
2119     for StrStrIW
4256     for StrStrIA
623      for wInstr (MasmBasic)
76       for InstrCiW
623      for wcsstr - in-buffer conversion
This is my netbook EeePC 4G — Intel Atom not speedy, but really fastest   :toothy

Code Select Expand

AMD Athlon(tm) 64 X2 Dual Core Processor 4600+ (SSE3)
6571     for StrStrIW
9518     for StrStrIA
1245     for wInstr (MasmBasic)
76       for InstrCiW
517      for wcsstr - in-buffer conversion

Thank you for wInstr(), I am look at it code some later and post result at this topic.

I am looked in code and can't understand what you do with unicode string before you pass them to InstrCi() (Are you convert string to Ansi?? I am bad understand macros :()

P.S. I am read this topic

[jj2007]

Hi,
Since the macro (below, simplified) has an EXITM <edx>, the void just avoids a pretty useless mov eax, edx. Normally, you would use it like this (where wRes$(ID) are Unicode resource strings):

Print Str$("The match was at char %i\n", wInstr(wRes$(103), wRes$(104), 1))

(note this is assembler, not Basic :green)

wInstr MACRO args:VARARG
  ucInstr=128
  EXITM Instr_(args)
ENDM
ucInstr=0
Instr_ [/color]MACRO sPos, Src$, Sub$, sMode
   push sMode+ucInstr   ;; A: 4 args, easiest case
   push reparg_offset(Sub$)
   PushString Src$
   push sPos
  ucInstr=0      ;; restore mode
  call InstrCi      ;; invoke InstrCi, sPos, reparg_offset(Src$), reparg_offset(Sub$), sMode
  EXITM <edx>   ;; relative pos in edx, absolute in eax
ENDM
[/b]

Now, if you code for example...

Code Select Expand

    nop
void wInstr(1, offset first, offset search, 1) ; 1=case-insensitive
    nop

... this will translate into this code (from OllyDbg):

Code Select Expand

00401371       |.  90                  |nop
00401372       |.  68 81000000         |push 81
00401377       |.  68 4B404000         |push 0040404B   ;  UNICODE "BrOtHeR"
0040137C       |.  68 1B404000         |push 0040401B   ;  UNICODE "My Other Brother Darryl"
00401381       |.  6A 01               |push 1
00401383       |.  E8 880D0000         |call 00402110
00401388       |.  90                  |nop

"push 81" is mode 1, case insensitive, or 80h, Unicode.

As you can see, the wide strings are just being passed by their pointers, the rest is handled inside InstrCi.

I have updated the MasmBasic library with a slightly faster wInstr; version number is still 9w.

Code Select Expand

Intel(R) Celeron(R) M CPU        420  @ 1.60GHz (SSE3)
2066     for StrStrIW
4146     for StrStrIA
420      for wInstr (MasmBasic, wide)
89       for Instr_ (MasmBasic, ANSI)
78       for InstrCiW
634      for wcsstr - in-buffer conversion

As you can see, the Basic ANSI version is four times as fast as the Unicode version - in contrast to StrStrI, where it is the other way round. So it seems StrStrIA makes some ugly internal conversions...