Results 1 to 10 of 10
  1. #1
    Departure's Avatar
    Join Date
    Nov 2010
    Gender
    male
    Posts
    818
    Reputation
    125
    Thanks
    1,785
    My Mood
    Doh

    [Release] Super Fast Search Pattern

    Haven't been here for awhile, Thought I would release a boyermore implementation search in Delphi, super fast.. just change the Chars to byte and your set or modify it for wild cards by changing

    Orginal(Find this)
    Code:
    While pTarget[i] = pPattern[j] Do
    WildCard(Replace With)
    Code:
    While (pTarget[i] = pPattern[j]) or (pPattern[j] = '*') Do
    ^ Ofcause "*" can be any char or byte you want...



    BoyerMore Search Pattern:
    Code:
    (*
     ByerMore Search Pattern Coded By Departure
    *)
    
    Function SearchPattern(Const pTarget, pPattern: PChar): DWORD;
    Var
      i             :Integer;
      j             :Integer;
      k             :Integer;
      iTargetLen    :Integer;
      iPatternLen   :Integer;
      baStep: Array[0..255] Of Byte;
    Begin
        Result := 0;
        iTargetLen  := Length(pTarget);
        iPatternLen := Length(pPattern);
        If iTargetLen * iPatternLen = 0 Then Exit;
        FillChar(baStep,SizeOf(baStep), iPatternLen);
    
        For K := 0 to iPatternLen -1 do baStep[Ord(pPattern[k])]:= iPatternLen - K;
    
        While K <= iTargetLen Do
        Begin
          i := k - 1;
          j := iPatternLen - 1;
          While pTarget[i] = pPattern[j] Do
          Begin
            Dec(i);
            Dec(j);
          End;
          If j = -1 Then
          Begin
            Result := i + 2;
            Exit;
          End;
          Inc(K, baStep[Ord(pTarget[k])]);
        End;
    End;

  2. The Following 2 Users Say Thank You to Departure For This Useful Post:

    pDevice (09-02-2012),Saltine (10-24-2011)

  3. #2
    Se lutar tú vai além, humilde igual Jesus.
    MPGH Member
    Turbulence's Avatar
    Join Date
    Aug 2010
    Gender
    male
    Posts
    2,182
    Reputation
    10
    Thanks
    741
    My Mood
    Pensive
    God job Departure


  4. #3
    ISmokeWeedAmICoolNow's Avatar
    Join Date
    Aug 2011
    Gender
    male
    Posts
    54
    Reputation
    10
    Thanks
    19
    My Mood
    Bitchy
    Quote Originally Posted by Turbulence View Post
    God job Departure
    God job /BR.

  5. #4
    Saltine's Avatar
    Join Date
    Jun 2011
    Gender
    male
    Posts
    494
    Reputation
    104
    Thanks
    625
    I decided to port this over to C++. Not sure if it is 100% correct, due to some of the Delphi functions you used (Ord, etc.)
    Code:
    #include <cstring>
    unsigned long SearchPattern(const char* pTarget,const char* pPattern)
    {
    	int i,j,k,iTargetLen,iPatternLen;
    	unsigned char baStep[255];
    	unsigned long result = 0;
    	iTargetLen = strlen(pTarget);
    	iPatternLen = strlen(pPattern);
    	if( iTargetLen*iPatternLen == 0) return result;
    	for(int i = 0 ; i < iPatternLen; i++) baStep[i] = sizeof(baStep);
    	for(k=0; k<iPatternLen; k++) baStep[(int)pPattern[k]] = iPatternLen - k;
    	while(k<=iTargetLen){
    		i=k-1;
    		j=iPatternLen-1;
    		while((pTarget[i] == pPattern[j]) || (pPattern[j] == '*')){
    			i--;
    			j--;
    		}
    		if(j=(-1))
    		{
    		result = i+2;
    		return result;
    		}
    		k+=baStep[((int)pTarget[k])];
    	}
    
    }
    How does it look?
    @Departure

  6. #5
    Departure's Avatar
    Join Date
    Nov 2010
    Gender
    male
    Posts
    818
    Reputation
    125
    Thanks
    1,785
    My Mood
    Doh
    @Saltine

    Nice work mate, does it work have you tested it?

    Ord function is the "Ordinal" value of a char, byte ect... yes I am pretty sure typecasting it as "Int" in C++ should do the trick also, for example if we had a byte $31 which is the character "1" in ascii, its Ordinal value would be 49 in decimal.

    an example using Wildcard as you have done. in delphi it would be

    iPos:= SearchPattern('hello this is a simple test of how to search in a string', '*ow');

    Writeln('Index: ', iPos); //returns 32 with 'how'

  7. #6
    yodaliketaco's Avatar
    Join Date
    Jan 2010
    Gender
    male
    Location
    winsock.dll
    Posts
    646
    Reputation
    45
    Thanks
    511
    My Mood
    Tired
    I wrote this a few months ago...

    Code:
    #define realAddy( cast, base, offset ) (cast)((DWORD)(base) + (DWORD)(offset))
    bool bExist(BYTE part, BYTE *whole, char *mask)
    {
    	BYTE *start = (BYTE*)(whole + sizeof(whole) - 1);
    	for(DWORD loc = 0; loc < sizeof(whole); loc++)
    		if((*(BYTE*)(start - loc) == part) || (*(mask + (strlen(mask) - 1) - loc) == '?')) return true;
    	return false;
    }
    DWORD lastLocationOfByte(BYTE part, BYTE *whole, char *mask)
    {
    	BYTE *start = (BYTE*)(whole + sizeof(whole) - 1);
    	for(DWORD loc = 0; loc < sizeof(whole); loc++)
    		if((*(BYTE*)(start - loc) == part) || (*(mask + (strlen(mask) - 1) - loc) == '?')) return (sizeof(whole) - loc);
    }
    DWORD FindPattern(DWORD first, DWORD total, BYTE *val, char *mask)
    {
    	size_t next = sizeof(*val);
    	BYTE *addy = (BYTE*)((val + next) - 1);
    	bool exist = false;
    	BYTE *loc;
    	for(DWORD n = (next - 1); n < total;)
    	{
    		DWORD spot;
    		for(spot = 0; (*(unsigned char*)(first + n - spot) == *(unsigned char*)(addy - spot)) || (*(mask + (strlen(mask) - 1) - spot) == '?'); spot++);
    		if(spot == next) return realAddy( DWORD, first, n );
    		else if(bExist(*(BYTE*)(first + n), val, mask))
    			n += lastLocationOfByte(*(BYTE*)(first + n), val, mask);
    		else n += next;
    	}
    	return false;
    }
    I never got around to testing it. If you test it, let me know if it works.

  8. #7
    Departure's Avatar
    Join Date
    Nov 2010
    Gender
    male
    Posts
    818
    Reputation
    125
    Thanks
    1,785
    My Mood
    Doh
    @yodaliketaco

    Looks like Naive search algorithm, this type of search routine is good for small patterns but not as fast as a boyer-more algorithm. The idea in boyer-more algo is the stepping code which calculate how many places to step so not every single byte needs to be "checked". While the naive algo could scan 2,400 bytes per millisecond the boyer-more reached upto 8,600 bytes per millisecond based on some testing with a 36mb file, Also the longer the pattern the faster the boyer-more algo was. If I had C++ compiler I would test out your code but im not a c++ programmer so I don't have any compilers installed.

  9. #8
    Saltine's Avatar
    Join Date
    Jun 2011
    Gender
    male
    Posts
    494
    Reputation
    104
    Thanks
    625
    Quote Originally Posted by Departure View Post
    @Saltine

    Nice work mate, does it work have you tested it?

    Ord function is the "Ordinal" value of a char, byte ect... yes I am pretty sure typecasting it as "Int" in C++ should do the trick also, for example if we had a byte $31 which is the character "1" in ascii, its Ordinal value would be 49 in decimal.

    an example using Wildcard as you have done. in delphi it would be

    iPos:= SearchPattern('hello this is a simple test of how to search in a string', '*ow');

    Writeln('Index: ', iPos); //returns 32 with 'how'
    Haven't tested it yet, I'll go do so now.
    Edit: something's fucked up, I'll mess around with the function and see if I can fix it.
    Last edited by Saltine; 10-25-2011 at 06:18 AM.

  10. #9
    yodaliketaco's Avatar
    Join Date
    Jan 2010
    Gender
    male
    Location
    winsock.dll
    Posts
    646
    Reputation
    45
    Thanks
    511
    My Mood
    Tired
    Quote Originally Posted by Departure View Post
    @yodaliketaco

    Looks like Naive search algorithm, this type of search routine is good for small patterns but not as fast as a boyer-more algorithm. The idea in boyer-more algo is the stepping code which calculate how many places to step so not every single byte needs to be "checked". While the naive algo could scan 2,400 bytes per millisecond the boyer-more reached upto 8,600 bytes per millisecond based on some testing with a 36mb file, Also the longer the pattern the faster the boyer-more algo was. If I had C++ compiler I would test out your code but im not a c++ programmer so I don't have any compilers installed.
    I coded this based on the boyer-moore algorithm. It's probably not the most concise version, but if it works it should still be much more efficient than the Naive search algorithm. I don't have a base working atm, but if I get back around to coding for this game I will probably test and revise this a bit.

  11. #10
    Apoc91's Avatar
    Join Date
    Apr 2010
    Gender
    male
    Posts
    59
    Reputation
    10
    Thanks
    35
    My Mood
    Twisted
    Sorry to bump the thread but as I was reading through here I noticed that @Saltine said he messed up translating the procedure to C(++), I don't know if he's fixed it or not (I'd assume so) but I went ahead and took the liberty to translate it.

    Code:
    DWORD SearchPattern(LPCWSTR szTarget, LPCWSTR szPattern)
    {
    	int i, j, k;
    	int iTargetLen, iPatternLen;
    	char baStep[255];
    
    	iTargetLen = _***len(szTarget); // (The *** is t-c-s without the -s, no fucking idea why it's *'d out...
    	iPatternLen = _***len(szPattern); // Same here.
    
    	if(iTargetLen * iPatternLen == 0)
    		return -1;
    
    	memset(baStep, iPatternLen, sizeof(baStep));
    
    	for(k = 0; k < iPatternLen; k++)
    	{
    		baStep[(int)szPattern[k]] = iPatternLen - k;
    	}
    
    	while(k <= iTargetLen)
    	{
    		i = k - 1;
    		j = iPatternLen - 1;
    
    		while(szTarget[i] == szPattern[j] || szPattern[j] == '*')
    		{
    			i--;
    			j--;
    		}
    
    		if(j == -1)
    			return i + 2;
    		k += baStep[(int)(szTarget[k])];
    	}
    }
    No idea why the forum ***s the _t-c-slen function but oh well, that works as expected, at least given Departure's test case that he had Saltine try it against.

  12. The Following 2 Users Say Thank You to Apoc91 For This Useful Post:

    Departure (02-08-2012),Saltine (01-02-2012)

Similar Threads

  1. [RELEASE] SUPER KNIFE, NO RECOIL, INSTA-SPAWN, INSTA-CLIP, AND MORE
    By NeverBorn in forum Combat Arms Europe Hacks
    Replies: 30
    Last Post: 08-21-2009, 09:42 AM
  2. [TUT][How-To] Super-Fast Speedhack
    By cyanmage in forum Combat Arms Hacks & Cheats
    Replies: 63
    Last Post: 08-14-2009, 02:11 AM
  3. [Release] SUPER JUMP HACK!!
    By FatEmoLLaMa in forum Combat Arms Hacks & Cheats
    Replies: 38
    Last Post: 10-07-2008, 09:26 PM
  4. [Release] Super TuT Package
    By 9Lives CatsEyes in forum Programming Tutorials
    Replies: 5
    Last Post: 08-31-2008, 12:14 AM
  5. [Release] Be Fast V1
    By sidnietje in forum WarRock - International Hacks
    Replies: 7
    Last Post: 11-28-2007, 09:34 PM