Instring

[guga]

Hi JJ

how do i use Instring ?

I´m having troubles trying to use in order to see if i can port it. Do you have the plain masm code for it ?

I´m trying to make a simple string search inside a text like this:

[INSTR_CASE 0] ; Is this the proper equate/flag ?
[INSTR_NO_CASE 2] ; Is this the proper equate/flag ?
[INSTR_INTELLISENSE 64] ; Is this the proper equate/flag ?


[BigString: B$ "Hello, my name is guga and i want to buy a car", 0]
[SmallString: B$ "guga", 0]

call InStringSSE2 BigString, SmallString, INSTR_NO_CASE

The goal is to search for the string "guga" (case sensitive,. case insensitive and intellisense) inside the main bigger string "Hello, my name is guga and i want to buy a car" and return the position (or address which would be better) where the string was found

What is the proper syntax for it ? I tested with masmbasic, but without any suces

[jj2007]

Instr_(...):

Code Select Expand

                mov pos, Instr_(1, L$(n), "equ", 1+4)    ; 1=start pos, 1=case-insensitive + 4=full word
Rem        - returns relative pos in edx, absolute in eax
                - if no match is found, zero is returned in edx, and eax points to the start of the 'haystack'; same if 'needle' is empty
                - six syntax variants allowed:
                    A: has startpos:        Instr_(1, "Test", "Te", 2)                            ; 4 args
                    B: no startpos:            Instr_("Test", "Te", 2)                                ; 3 args, last one immediate = mode
                    C: has startpos:        Instr_(1, "Test", "Te")                                ; 3 args, last one not immediate
                    D: no startpos:            Instr_("Test", "Te")                        ; 2 args
)                                                                            ; 2 args
                    E: test several patterns:        InstrOr("Test", "Te" or "st", 1)                ; 3 args (startpos is 1)
                    F: extra fast mode:    Instr_(FAST, My$(ecx), "Hello", 0)            ; 4 args, no startpos, modes 0+2 only
                - case & mode (bitwise flag):
                    0=case-sensitive, +1=insensitive, +2=intellisense (Name=name, i.e. case of first char ignored),
                    +4=full word search, +8=include start of line in text block search, +4+16=not full word
InString is a Masm32 SDK algo, also used with the Masm32 find$(big$, small$) macro.
InStr_() is a MasmBasic macro.

Full test:

Code Select Expand

include \masm32\MasmBasic\MasmBasic.inc
  SetGlobals BigString, SmallString
  Init
  Let BigString="Hello, my name is guga and i want to buy a car"
  Let SmallString="guga"
  .if Instr_(BigString, SmallString)
xchg eax, ecx
Inkey "[", Left$(ecx, Len(SmallString)), "]"
  .endif
EndOfCode
Shorter:

Code Select Expand

include \masm32\MasmBasic\MasmBasic.inc
  SetGlobals Big$="Hello, my name is guga and i want to buy a car", Small$="guga"
  Init
  .if Instr_(Big$, Small$)
xchg eax, ecx
Inkey "[", Left$(ecx, Len(Small$)), "]"
  .endif
EndOfCode
The xchg eax,  ecx is needed because Len() destroys resp. returns eax.

[mineiro]

Hello sir guga;
Search by Boyer Moore into this board. Need some optimizations link bellow:
https://masm32.com/board/index.php?msg=109922
Sir jj2007 have done some tests, you can check results from that post to front.

[jj2007]

Hello sir guga;
Search by Boyer Moore into this board. Need some optimizations link bellow:
https://masm32.com/board/index.php?msg=109922
Sir jj2007 have done some tests, you can check results from that post to front.

Timings are here. Example:

Code Select Expand

... using a 6 bytes substring [Doplic]
599 ms  for CRT strstr          result=105560497
563 ms  for M32 InString        result=105560497
181 ms  for BMHBinsearch        result=105560497
158 ms  for BMBinSearch         result=0
420 ms  for Boyer-M Mineiro 1   result=105560497
417 ms  for Boyer-M Mineiro 2   result=105560497
61 ms   for MB Instr_()         result=105560497

[lingo]

Code Select Expand


.const
EQUAL_ANY           equ 0000b
RANGES              equ 0100b
EQUAL_EACH          equ 1000b
EQUAL_ORDERED       equ 1100b
NEGATIVE_POLARITY   equ 010000b
BYTE_MASK           equ 1000000b

.code
align 16     
InstrLingo      proc        haystack:DWORD,needle:DWORD
                mov         ecx,  haystack                 ; ecx = haystack, edx = needle
                push        esi
                mov         edx,  needle
                push        edi
                mov         eax,  ecx
                movdqu      xmm2, oword ptr[edx]           ; load 1st 16 bytes of needle
                pxor        xmm3, xmm3
@Loop:                                                     ; find the first possible match of 16-byte fragment in haystack       
                pcmpistri   xmm2, oword ptr[eax], EQUAL_ORDERED
                lea         eax, [eax+16]
                ja          @Loop
                lea         eax, [eax+ecx-16]               ; save the possible match start
                mov         edi, edx
                mov         esi, eax
                jnc         @NotFound
                sub         edi, eax
@@:                                                         ; compare the strings
                movdqu      xmm1, oword ptr [esi + edi]
                pcmpistrm   xmm3, xmm1, EQUAL_EACH + NEGATIVE_POLARITY + BYTE_MASK ; mask out invalid bytes in the haystack
                movdqu      xmm4, oword ptr[esi]
                pand        xmm4, xmm0
                pcmpistri   xmm1, xmm4, EQUAL_EACH + NEGATIVE_POLARITY
                lea         esi, [esi+16]
                ja          @b
                jnc         @Found
                add         eax, 1                          ; continue searching from the next byte
                jmp         @Loop
@NotFound:
                xor         eax, eax
@Found:     
                pop         edi
                pop         esi
                ret
InstrLingo      endp


  

[jj2007]

Hi Lingo,

Not surprisingly, your code performs exactly like MasmBasic Instr_(), but how come it returns a different position? Did you forget to subtract the start position?

Code Select Expand

Intel(R) Core(TM) i5-2450M CPU @ 2.50GHz
Finding a string 5 times in a 100MB 'haystack' from\Masm32\include\Windows.inc
... using a 8 bytes substring [Doplicat]
603 ms  for CRT strstr          result=105560497
586 ms  for M32 InString        result=105560497
162 ms  for BMHBinsearch        result=105560497
134 ms  for BMBinSearch        result=0
323 ms  for Boyer-M Mineiro 1  result=0
324 ms  for Boyer-M Mineiro 2  result=0
60 ms  for Lingo              result=143964624
63 ms  for MB Instr_()        result=105560497

... using a 7 bytes substring [Doplica]
624 ms  for CRT strstr          result=105560497
588 ms  for M32 InString        result=105560497
172 ms  for BMHBinsearch        result=105560497
146 ms  for BMBinSearch        result=105560497
374 ms  for Boyer-M Mineiro 1  result=105560497
369 ms  for Boyer-M Mineiro 2  result=105560497
62 ms  for Lingo              result=143964624
63 ms  for MB Instr_()        result=105560497

... using a 6 bytes substring [Doplic]
610 ms  for CRT strstr          result=105560497
581 ms  for M32 InString        result=105560497
186 ms  for BMHBinsearch        result=105560497
162 ms  for BMBinSearch        result=0
423 ms  for Boyer-M Mineiro 1  result=105560497
427 ms  for Boyer-M Mineiro 2  result=105560497
63 ms  for Lingo              result=143964624
62 ms  for MB Instr_()        result=105560497

[Caché GB]

Hi lingo

Thanks for this algo, it works perfectly.

Code Select Expand


         invoke  InstrLingo, addr longString, addr shortString

            lea  ecx, longString        ;  eax returns Address of shortString
            sub  eax, ecx
            mov  BytePosition, eax      ;  now eax = Position of shortString


Awrsome.

[jj2007]

Hi lingo

Thanks for this algo, it works perfectly.

It was added to MasmBasic Instr_() over a year ago. Credits should go to Peter Kankowski (13 years ago):

Code Select Expand

strstr_sse42:
  ; ecx = haystack, edx = needle

  push esi
  push edi
  MovDqU xmm2, dqword[edx] ; load the first 16 bytes of neddle
  Pxor xmm3, xmm3
  lea eax, [ecx - 16]

  ; find the first possible match of 16-byte fragment in haystack
STRSTR_MAIN_LOOP:
    add eax, 16
    PcmpIstrI xmm2, dqword[eax], EQUAL_ORDERED
    ja STRSTR_MAIN_LOOP

  jnc STRSTR_NOT_FOUND

  add eax, ecx ; save the possible match start
  mov edi, edx
  mov esi, eax
  sub edi, esi
  sub esi, 16

  ; compare the strings
@@:
    add esi, 16
    MovDqU    xmm1, dqword[esi + edi]
    ; mask out invalid bytes in the haystack
    PcmpIstrM xmm3, xmm1, EQUAL_EACH + NEGATIVE_POLARITY + BYTE_MASK
    MovDqU xmm4, dqword[esi]
    PAnd xmm4, xmm0
    PcmpIstrI xmm1, xmm4, EQUAL_EACH + NEGATIVE_POLARITY
    ja @B

  jnc STRSTR_FOUND

  ; continue searching from the next byte
  sub eax, 15
  jmp STRSTR_MAIN_LOOP

STRSTR_NOT_FOUND:
  xor eax, eax

STRSTR_FOUND:
  pop edi
  pop esi
  ret
Compare that to Lingo's code:

Code Select Expand

InstrLingo      proc        haystack:DWORD,needle:DWORD
                mov         ecx,  haystack                 ; ecx = haystack, edx = needle
                push        esi
                mov         edx,  needle
                push        edi
                mov         eax,  ecx
                movdqu      xmm2, oword ptr[edx]           ; load 1st 16 bytes of needle
                pxor        xmm3, xmm3
@Loop:                                                     ; find the first possible match of 16-byte fragment in haystack       
                pcmpistri   xmm2, oword ptr[eax], EQUAL_ORDERED
                lea         eax, [eax+16]
                ja          @Loop
                lea         eax, [eax+ecx-16]               ; save the possible match start
                mov         edi, edx
                mov         esi, eax
                jnc         @NotFound
                sub         edi, eax
@@:                                                         ; compare the strings
                movdqu      xmm1, oword ptr [esi + edi]
                pcmpistrm   xmm3, xmm1, EQUAL_EACH + NEGATIVE_POLARITY + BYTE_MASK ; mask out invalid bytes in the haystack
                movdqu      xmm4, oword ptr[esi]
                pand        xmm4, xmm0
                pcmpistri   xmm1, xmm4, EQUAL_EACH + NEGATIVE_POLARITY
                lea         esi, [esi+16]
                ja          @b
                jnc         @Found
                add         eax, 1                           ; continue searching from the next byte
                jmp         @Loop
@NotFound:
                xor         eax, eax
@Found:     
                pop         edi
                pop         esi
                ret
InstrLingo      endp
MasmBasic's Instr_() has minor optimisations for speed and size but is basically the same.

[lingo]

Thank you JJ,

My algo works without error.
Tested it with similar texts from the attachment.

[Biterider]

Hi
The code is fast but potentially unsafe. 
If the fetched memory blocks cross a page boundary to an uncommited page, an exception is raised.
The only way to use this code safely is to align the strings to 16.

Biterider

[jj2007]

My algo works without error.

If you subtract the source, as noted by myself and Caché GB, Kankowski's algo works fine indeed.

624 ms  for CRT strstr          result=105560497
588 ms  for M32 InString        result=105560497
172 ms  for BMHBinsearch        result=105560497
146 ms  for BMBinSearch        result=105560497
374 ms  for Boyer-M Mineiro 1  result=105560497
369 ms  for Boyer-M Mineiro 2  result=105560497
62 ms  for Lingo              result=143964624
63 ms  for MB Instr_()        result=105560497

The code is fast but potentially unsafe.
If the fetched memory blocks cross a page boundary to an uncommited page, an exception is raised.
The only way to use this code safely is to align the strings to 16.

Biterider

I had that suspicion, too. Maybe we need a test case...

[Biterider]

I had that suspicion, too. Maybe we need a test case...

Searching a bit I found some discussions about this issue, one of them is
https://www.purebasic.fr/english/viewtopic.php?p=605105

One possible solution is to align the pointer for the retrieved characters and invalidate the first characters that are not part of the string. Unfortunately, masking is not possible with this instruction, but the invalid characters can be replaced with non-zero characters (byte/word), e.g. "01", that are not in the string to be searched.
This means a little more execution time, but then the function could be used universally.

Biterider

[Biterider]

Hi
When trying to implement something to solve the pafe boundary problem, I quickly discovered that the "needle" has exactly the same problem, which increases the complexity considerably.
 
Atm I can't see a simple solution for both issues that are efficient enough. 

I wonder sometimes what the developers of such instructions have in mind when it comes to implementing the code...  

Biterider

[jj2007]

Atm I can't see a simple solution for both issues that are efficient enough. 

Test case:

Code Select Expand

  invoke VirtualAlloc, 0, 4096, MEM_COMMIT, PAGE_READWRITE
  xchg eax, edi
  invoke lstrcpyn, edi, esi, 4096 ; esi is a pointer e.g. to contents of Windows.inc
Now perform the instr() on edi

It works fine with SEH, but I agree there is no other efficient solution

[Biterider]

As it stands now, I strongly recommend not using these implementations for general purposes, as this will lead to unexplained and random crashes in customer code, resulting in a sh*storm.

Biterider