Click here to Skip to main content
13,763,429 members
Click here to Skip to main content

Stats

170.6K views
3.1K downloads
69 bookmarked
Posted 9 Sep 2011
Licenced CPOL

Fastest strstr-like function in C!?

, 22 Aug 2016
Tuned function for searching a needle in a haystack
Nakamichi_Kintaro++_source_executables_64bit_(GCC510-vs-Intel150)_(TW-vs-RG)_BENCHMARK
MokujIN 224 prompt.lnk
Railgun_Trolldom_28-pages.pdf
Railgun_Swampshine_BailOut_source_(Two-Way_benchmark)
// Scheherezade -> Hasherezade
// Version: This is Hasherezade r.3
// Copyleft 2013-Oct-09, Kaze
// Purpose: This is optimized strstr-like (memmem in fact) for short needles (up not to 255 bytes but to uint32_t - 1) function.
// Caution: For better speed the case 'if (cbPattern==1)' was removed, so Pattern must be longer than 1 char.
#define _rotl_KAZE(x, n) (((x) << (n)) | ((x) >> (32-(n))))
#define _rotl_KAZE64(x, n) (((x) << (n)) | ((x) >> (64-(n))))
#define HaystackThresholdr3 961 // Quadruplet works up to this value, if bigger then BMHS takes over
#define HashTableSizer3 17
//#define HasherezadeOrder8r3 // If commented then Order12
//#define HasherezadeBYTEWISEr3 // If commented then BITWISE, HashTable becomes 8 times smaller i.e. '-3' bits.
#ifdef HasherezadeBYTEWISEr3
	#define HashTableShrinkr3 0 // Don't change!
#else				
	#define HashTableShrinkr3 3 // Don't change!
#endif
#ifdef HasherezadeOrder8r3
	#define NeedleThresholdr3 9 // Should be bigger than 'HasherezadeOrder'. BMS works up to this value (inclusive), if PatternLength is bigger than NeedleThresholdr3 i.e. 10>9 then the best skip/jump is obtained from BMH/BMS/BMHorder2/BMHorder8.
#else				
	#define NeedleThresholdr3 13 // Should be bigger than 'HasherezadeOrder'. BMS works up to this value (inclusive), if PatternLength is bigger than NeedleThresholdr3 i.e. 14>13 then the best skip/jump is obtained from BMH/BMS/BMHorder2/BMHorder8.
#endif
#define NeedleThresholdBIGr3 49 // Should be bigger than 'HasherezadeOrder'. BMH/BMS/BMHorder2/BMHorder8 work up to this value (inclusive), if PatternLength is bigger than NeedleThresholdr3 i.e. 50>49 then the best skip/jump is obtained from BMHorder12.
#define JumpThresholdr3 11 // The cost (the-bigger-the-threshold-the-less-hashing) of hashing = JumpThresholdr3 < MAXjump-CURRENTjump: if jump/stride obtained with (BMHS + JumpThresholdr3) is smaller than HASH jump/stride than go hashing
char * Railgun_Hasherezade_r3 (char * pbTarget, char * pbPattern, uint32_t cbTarget, uint32_t cbPattern)
{
	char * pbTargetMax = pbTarget + cbTarget;
	register uint32_t ulHashPattern;
	register uint32_t ulHashTarget;
	signed long count;
	signed long countSTATIC;

	unsigned char SINGLET;
	uint32_t Quadruplet2nd;
	uint32_t Quadruplet3rd;
	uint32_t Quadruplet4th;

	uint32_t AdvanceHopperGrass;

	long i; //BMH needed
	int a, j;
	unsigned int bm_bc[256]; // BMH needed
	unsigned int bm_bc2nd[256]; // BMS needed
	unsigned char bm_Horspool_Order2[256*256]; // BMHSS(Elsiane) needed, 'char' limits patterns to 255, if 'long' then table becomes 256KB, grrr.
	unsigned char bm_Hasherezade_HASH[1<<(HashTableSizer3-HashTableShrinkr3)];
	uint32_t hash32;
	uint32_t hash32B;
	uint32_t hash32C;
	uint32_t Gulliver; // or unsigned char or unsigned short

	if (cbPattern > cbTarget) return(NULL);

	if ( cbPattern<4 ) { 

        	pbTarget = pbTarget+cbPattern;
		ulHashPattern = ( (*(char *)(pbPattern))<<8 ) + *(pbPattern+(cbPattern-1));
		if ( cbPattern==3 ) {
			for ( ;; ) {
				if ( ulHashPattern == ( (*(char *)(pbTarget-3))<<8 ) + *(pbTarget-1) ) {
					if ( *(char *)(pbPattern+1) == *(char *)(pbTarget-2) ) return((pbTarget-3));
				}
				if ( (char)(ulHashPattern>>8) != *(pbTarget-2) ) { 
					pbTarget++;
					if ( (char)(ulHashPattern>>8) != *(pbTarget-2) ) pbTarget++;
				}
				pbTarget++;
				if (pbTarget > pbTargetMax) return(NULL);
			}
		} else {
		}
		for ( ;; ) {
			if ( ulHashPattern == ( (*(char *)(pbTarget-2))<<8 ) + *(pbTarget-1) ) return((pbTarget-2));
			if ( (char)(ulHashPattern>>8) != *(pbTarget-1) ) pbTarget++;
			pbTarget++;
			if (pbTarget > pbTargetMax) return(NULL);
		}

	} else {
		if (cbTarget<HaystackThresholdr3) { // This value is arbitrary (don't know how exactly), it ensures (at least must) better performance than 'Boyer_Moore_Horspool'.

		pbTarget = pbTarget+cbPattern;
		ulHashPattern = *(uint32_t *)(pbPattern);
		SINGLET = ulHashPattern & 0xFF;
		Quadruplet2nd = SINGLET<<8;
		Quadruplet3rd = SINGLET<<16;
		Quadruplet4th = SINGLET<<24;
		for ( ;; ) {
			AdvanceHopperGrass = 0;
			ulHashTarget = *(uint32_t *)(pbTarget-cbPattern);
			if ( ulHashPattern == ulHashTarget ) { // Three unnecessary comparisons here, but 'AdvanceHopperGrass' must be calculated - it has a higher priority.
				count = cbPattern-1;
				while ( count && *(char *)(pbPattern+(cbPattern-count)) == *(char *)(pbTarget-count) ) {
					if ( cbPattern-1==AdvanceHopperGrass+count && SINGLET != *(char *)(pbTarget-count) ) AdvanceHopperGrass++;
					count--;
				}
				if ( count == 0) return((pbTarget-cbPattern));
			} else { // The goal here: to avoid memory accesses by stressing the registers.
				if ( Quadruplet2nd != (ulHashTarget & 0x0000FF00) ) {
					AdvanceHopperGrass++;
					if ( Quadruplet3rd != (ulHashTarget & 0x00FF0000) ) {
						AdvanceHopperGrass++;
						if ( Quadruplet4th != (ulHashTarget & 0xFF000000) ) AdvanceHopperGrass++;
					}
				}
			}
			AdvanceHopperGrass++;
			pbTarget = pbTarget + AdvanceHopperGrass;
			if (pbTarget > pbTargetMax) return(NULL);
		}

		} else { //if (cbTarget<HaystackThresholdr3)

	if ( cbPattern<=NeedleThresholdBIGr3 ) { 

			countSTATIC = cbPattern-2-2;

			for (a=0; a < 256; a++) {bm_bc[a]=cbPattern; bm_bc2nd[a]=cbPattern+1;}
			for (j=0; j < cbPattern-1; j++) bm_bc[pbPattern[j]]=cbPattern-j-1; 
			for (j=0; j < cbPattern; j++) bm_bc2nd[pbPattern[j]]=cbPattern-j; 

			ulHashPattern = *(uint32_t *)(pbPattern); // First four bytes
			//ulHashTarget = *(unsigned short *)(pbPattern+cbPattern-1-1); // Last two bytes
		
			i=0;
			for (a=0; a < 256*256; a++) {bm_Horspool_Order2[a]= cbPattern-1;} // cbPattern-(Order-1) for Horspool; 'memset' if not optimized
			for (j=0; j < cbPattern-1; j++) bm_Horspool_Order2[*(unsigned short *)(pbPattern+j)]=j; // Rightmost appearance/position is needed

	if ( cbPattern>NeedleThresholdr3 ) { 

			for (a=0; a < 1<<(HashTableSizer3-HashTableShrinkr3); a++) {bm_Hasherezade_HASH[a]= 0;} // to-do: 'memset' if not optimized
			// cbPattern - Order + 1 i.e. number of BBs for 11 'fastest fox' 11-8+1=4: 'fastest ', 'astest f', 'stest fo', 'test fox'
#ifdef HasherezadeOrder8r3
			for (j=0; j < cbPattern-8+1; j++) {
				// An overkill, that's why commented, simply no need for one loop, no need of seed!
				//hash32 = (2166136261 ^ *(uint32_t*)(pbPattern+j+0)) * 709607;
				//hash32B = (2166136261 ^ *(uint32_t*)(pbPattern+j+4)) * 709607;
				hash32 = *(uint32_t*)(pbPattern+j+0);
				hash32B = *(uint32_t*)(pbPattern+j+4);
				hash32 = (hash32 ^ _rotl_KAZE(hash32B,27) ) * 709607;
#ifdef HasherezadeBYTEWISEr3
				bm_Hasherezade_HASH[( hash32 ^ (hash32 >> 16) ) & ( (1<<(HashTableSizer3))-1 )]=1;
#else				
				hash32 = ( hash32 ^ (hash32 >> 16) ) & ( (1<<(HashTableSizer3))-1 );
				bm_Hasherezade_HASH[hash32>>3]= bm_Hasherezade_HASH[hash32>>3] | (1<<(hash32&0x7));
#endif
#else
			for (j=0; j < cbPattern-12+1; j++) {
				hash32 = (2166136261 ^ *(uint32_t *)(pbPattern+j+0)) * 709607;        
				hash32B = (2166136261 ^ *(uint32_t *)(pbPattern+j+4)) * 709607;        
				hash32C = (2166136261 ^ *(uint32_t *)(pbPattern+j+8)) * 709607;        
				hash32 = (hash32 ^ _rotl_KAZE(hash32C,5) ) * 709607;
				hash32 = (hash32 ^ _rotl_KAZE(hash32B,5) ) * 709607;
#ifdef HasherezadeBYTEWISEr3
				bm_Hasherezade_HASH[( hash32 ^ (hash32 >> 16) ) & ( (1<<(HashTableSizer3))-1 )]=1;
#else				
				hash32 = ( hash32 ^ (hash32 >> 16) ) & ( (1<<(HashTableSizer3))-1 );
				bm_Hasherezade_HASH[hash32>>3]= bm_Hasherezade_HASH[hash32>>3] | (1<<(hash32&0x7));
#endif
#endif
			}

			while (i <= cbTarget-cbPattern-1) { // -1 because Sunday is used
				Gulliver = bm_Horspool_Order2[*(unsigned short *)&pbTarget[i+cbPattern-1-1]];

				if ( Gulliver == cbPattern-2 ) { // CASE #1: means the pair (char order 2) is found
					if ( *(uint32_t *)&pbTarget[i] == ulHashPattern) {
						count = countSTATIC; // Last two chars already matched, to be fixed with -2
						while ( count !=0 && *(char *)(pbPattern+(countSTATIC-count)+4) == *(char *)(&pbTarget[i]+(countSTATIC-count)+4) )
							count--;
						if ( count == 0) return(pbTarget+i);
					}
					//if ( bm_bc[(unsigned char)pbTarget[i+cbPattern-1]] < bm_bc2nd[(unsigned char)pbTarget[i+(cbPattern)]] )
					         Gulliver =  bm_bc2nd[(unsigned char)pbTarget[i+(cbPattern)]];
					//else
					//         Gulliver =  bm_bc[(unsigned char)pbTarget[i+cbPattern-1]];
				} else if ( Gulliver != cbPattern-1 ) // CASE #2: if equal means the pair (char order 2) is not found i.e. Gulliver remains intact, skip the whole pattern and fall back (Order-1) chars i.e. one char for Order 2
					Gulliver = cbPattern - Gulliver - 2; // CASE #3: the pair is found and not as suffix i.e. rightmost position
			
				// The goal: to jump when the rightmost 8bytes (Order 8 Horspool) of window do not look like any of Needle prefixes i.e. are not to be found. This maximum jump equals cbPattern-(Order-1) or 11-(8-1)=4 for 'fastest fox' - a small one but for Needle 31 bytes the jump equals 31-(8-1)=24
#ifdef HasherezadeOrder8r3
				if (Gulliver + (JumpThresholdr3) < cbPattern-(8-1)) { 
				GlobalHashSectionExecution++; // Comment it, it is only for stats.
					// An overkill, that's why commented, simply no need for one loop, no need of seed!
					//hash32 = (2166136261 ^ *(uint32_t*)(pbTarget+i+cbPattern-8+0)) * 709607;
					//hash32B = (2166136261 ^ *(uint32_t*)(pbTarget+i+cbPattern-8+4)) * 709607;
					hash32 = *(uint32_t*)(pbTarget+i+cbPattern-8+0);
					hash32B = *(uint32_t*)(pbTarget+i+cbPattern-8+4);
					hash32 = (hash32 ^ _rotl_KAZE(hash32B,27) ) * 709607;
#ifdef HasherezadeBYTEWISEr3
					if ( bm_Hasherezade_HASH[( hash32 ^ (hash32 >> 16) ) & ( (1<<(HashTableSizer3))-1 )]==0 )
						Gulliver = cbPattern-(8-1);
#else
					hash32 = ( hash32 ^ (hash32 >> 16) ) & ( (1<<(HashTableSizer3))-1 );
					if ( (bm_Hasherezade_HASH[hash32>>3] & (1<<(hash32&0x7))) ==0 )
						Gulliver = cbPattern-(8-1);
#endif
				}
#else
				if (Gulliver + (JumpThresholdr3) < cbPattern-(12-1)) { 
				GlobalHashSectionExecution++; // Comment it, it is only for stats.
					hash32 = (2166136261 ^ *(uint32_t *)(pbTarget+i+cbPattern-12+0)) * 709607;        
					hash32B = (2166136261 ^ *(uint32_t *)(pbTarget+i+cbPattern-12+4)) * 709607;        
					hash32C = (2166136261 ^ *(uint32_t *)(pbTarget+i+cbPattern-12+8)) * 709607;        
					hash32 = (hash32 ^ _rotl_KAZE(hash32C,5) ) * 709607;
					hash32 = (hash32 ^ _rotl_KAZE(hash32B,5) ) * 709607;
#ifdef HasherezadeBYTEWISEr3
					if ( bm_Hasherezade_HASH[( hash32 ^ (hash32 >> 16) ) & ( (1<<(HashTableSizer3))-1 )]==0 )
						Gulliver = cbPattern-(12-1);
#else
					hash32 = ( hash32 ^ (hash32 >> 16) ) & ( (1<<(HashTableSizer3))-1 );
					if ( (bm_Hasherezade_HASH[hash32>>3] & (1<<(hash32&0x7))) ==0 )
						Gulliver = cbPattern-(12-1);
#endif
				}
#endif
					i = i + Gulliver;
				GlobalI++; // Comment it, it is only for stats.
			}

	} else { //if ( cbPattern>NeedleThresholdr3 )
// Slower than pure Sunday, that's why commented (for small needles there is no much gain in choosing a bigger stride):
/*
			while (i <= cbTarget-cbPattern-1) { // -1 because Sunday is used
				Gulliver = bm_Horspool_Order2[*(unsigned short *)&pbTarget[i+cbPattern-1-1]];

				if ( Gulliver == cbPattern-2 ) { // CASE #1: means the pair (char order 2) is found
					if ( *(uint32_t *)&pbTarget[i] == ulHashPattern) {
						count = countSTATIC; // Last two chars already matched, to be fixed with -2
						while ( count !=0 && *(char *)(pbPattern+(countSTATIC-count)+4) == *(char *)(&pbTarget[i]+(countSTATIC-count)+4) )
							count--;
						if ( count == 0) return(pbTarget+i);
					}
					//i = i + 1; // r.1, obviuosly this is the worst skip so turning to 'SunHorse': lines below
					if ( bm_bc[(unsigned char)pbTarget[i+cbPattern-1]] < bm_bc2nd[(unsigned char)pbTarget[i+(cbPattern)]] )
					         Gulliver =  bm_bc2nd[(unsigned char)pbTarget[i+(cbPattern)]];
					else
					         Gulliver =  bm_bc[(unsigned char)pbTarget[i+cbPattern-1]];
				} else if ( Gulliver != cbPattern-1 ) // CASE #2: if equal means the pair (char order 2) is not found i.e. Gulliver remains intact, skip the whole pattern and fall back (Order-1) chars i.e. one char for Order 2
					Gulliver = cbPattern - Gulliver - 2; // CASE #3: the pair is found and not as suffix i.e. rightmost position

				i = i + Gulliver;

// 32323218 Order 1 Horspool Skip-table A
// 01234568 Order 1 Horspool Skip-table B
// fa af fa af fa as st Order 2 Horspool Skip-table B
//  0  1  2  3  4  5  6
// HIKARIfast
// fafafast
//   fafafast +2 Order 1 'a' vs 't'
//   fafafast +2 = (cbPattern-SkipB-Order = 8-5-1 = 2) Order 1 'a' vs 't'
//   fafafast +2 = (cbPattern-SkipB-Order = 8-4-2 = 2) Order 2 'fa' vs 'st' i.e. CASE #3

// 76543218 Order 1 Horspool
// lo on ng gp pa ac ce Order 2 Horspool
//  0  1  2  3  4  5  6
// HIKARIfast
// longpace
//   longpace +2 Order 1 'a' vs 'e'
//        longpace +7 = (cbPattern-(Order-1) = 8-(2-1) = 7) Order 2 'fa' vs 'ce' i.e. CASE #2

				GlobalI++; // Comment it, it is only for stats.
			}
*/
			while (i <= cbTarget-cbPattern-1) {
				if ( *(unsigned long *)&pbTarget[i] == ulHashPattern) {
					count = countSTATIC;
					while ( count !=0 && *(char *)(pbPattern+(countSTATIC-count)+4) == *(char *)(&pbTarget[i]+(countSTATIC-count)+4) ) { // if pattern length is 4 or 5 we have count=-1 and count=0 respectively i.e. no need of comparing in-between chars.
						count--;
					}
					if ( count == 0) return(pbTarget+i);
				}
				i= i + bm_bc2nd[(unsigned char)pbTarget[i+(cbPattern)]];
				GlobalI++; // Comment it, it is only for stats.
			}
	} //if ( cbPattern>NeedleThresholdr3 )

			if (i == cbTarget-cbPattern) {
				if ( *(uint32_t *)&pbTarget[i] == ulHashPattern) {
					count = countSTATIC;
					while ( count !=0 && *(char *)(pbPattern+(countSTATIC-count)+4) == *(char *)(&pbTarget[i]+(countSTATIC-count)+4) )
						count--;
					if ( count == 0) return(pbTarget+i);
				}
				GlobalI++; // Comment it, it is only for stats.
			}
			return(NULL);

	} else { //	if ( cbPattern<=255 )
// MEMMEM() MEMMEM() MEMMEM() MEMMEM() MEMMEM() MEMMEM() MEMMEM() MEMMEM() MEMMEM() MEMMEM() MEMMEM() MEMMEM() MEMMEM() MEMMEM() [
			countSTATIC = cbPattern-2-2;

			ulHashPattern = *(uint32_t *)(pbPattern); // First four bytes
			//ulHashTarget = *(unsigned short *)(pbPattern+cbPattern-1-1); // Last two bytes
		
			i=0;

			for (a=0; a < 1<<(HashTableSizer3-HashTableShrinkr3); a++) {bm_Hasherezade_HASH[a]= 0;} // to-do: 'memset' if not optimized
			// cbPattern - Order + 1 i.e. number of BBs for 11 'fastest fox' 11-8+1=4: 'fastest ', 'astest f', 'stest fo', 'test fox'
#ifdef HasherezadeOrder8r3
			for (j=0; j < cbPattern-8+1; j++) {
				// An overkill, that's why commented, simply no need for one loop, no need of seed!
				//hash32 = (2166136261 ^ *(uint32_t*)(pbPattern+j+0)) * 709607;
				//hash32B = (2166136261 ^ *(uint32_t*)(pbPattern+j+4)) * 709607;
				hash32 = *(uint32_t*)(pbPattern+j+0);
				hash32B = *(uint32_t*)(pbPattern+j+4);
				hash32 = (hash32 ^ _rotl_KAZE(hash32B,27) ) * 709607;
#ifdef HasherezadeBYTEWISEr3
				bm_Hasherezade_HASH[( hash32 ^ (hash32 >> 16) ) & ( (1<<(HashTableSizer3))-1 )]=1;
#else				
				hash32 = ( hash32 ^ (hash32 >> 16) ) & ( (1<<(HashTableSizer3))-1 );
				bm_Hasherezade_HASH[hash32>>3]= bm_Hasherezade_HASH[hash32>>3] | (1<<(hash32&0x7));
#endif
#else
			for (j=0; j < cbPattern-12+1; j++) {
				hash32 = (2166136261 ^ *(uint32_t *)(pbPattern+j+0)) * 709607;        
				hash32B = (2166136261 ^ *(uint32_t *)(pbPattern+j+4)) * 709607;        
				hash32C = (2166136261 ^ *(uint32_t *)(pbPattern+j+8)) * 709607;        
				hash32 = (hash32 ^ _rotl_KAZE(hash32C,5) ) * 709607;
				hash32 = (hash32 ^ _rotl_KAZE(hash32B,5) ) * 709607;
#ifdef HasherezadeBYTEWISEr3
				bm_Hasherezade_HASH[( hash32 ^ (hash32 >> 16) ) & ( (1<<(HashTableSizer3))-1 )]=1;
#else				
				hash32 = ( hash32 ^ (hash32 >> 16) ) & ( (1<<(HashTableSizer3))-1 );
				bm_Hasherezade_HASH[hash32>>3]= bm_Hasherezade_HASH[hash32>>3] | (1<<(hash32&0x7));
#endif
#endif
			}

			while (i <= cbTarget-cbPattern) {
				Gulliver = 1; // Assume minimal jump as initial value.
				// The goal: to jump when the rightmost 8bytes (Order 8 Horspool) of window do not look like any of Needle prefixes i.e. are not to be found. This maximum jump equals cbPattern-(Order-1) or 11-(8-1)=4 for 'fastest fox' - a small one but for Needle 31 bytes the jump equals 31-(8-1)=24
#ifdef HasherezadeOrder8r3
				GlobalHashSectionExecution++; // Comment it, it is only for stats.
					// An overkill, that's why commented, simply no need for one loop, no need of seed!
					//hash32 = (2166136261 ^ *(uint32_t*)(pbTarget+i+cbPattern-8+0)) * 709607;
					//hash32B = (2166136261 ^ *(uint32_t*)(pbTarget+i+cbPattern-8+4)) * 709607;
					hash32 = *(uint32_t*)(pbTarget+i+cbPattern-8+0);
					hash32B = *(uint32_t*)(pbTarget+i+cbPattern-8+4);
					hash32 = (hash32 ^ _rotl_KAZE(hash32B,27) ) * 709607;
#ifdef HasherezadeBYTEWISEr3
					if ( bm_Hasherezade_HASH[( hash32 ^ (hash32 >> 16) ) & ( (1<<(HashTableSizer3))-1 )]==0 )
						Gulliver = cbPattern-(8-1);
#else
					hash32 = ( hash32 ^ (hash32 >> 16) ) & ( (1<<(HashTableSizer3))-1 );
					if ( (bm_Hasherezade_HASH[hash32>>3] & (1<<(hash32&0x7))) ==0 )
						Gulliver = cbPattern-(8-1);
#endif
#else
				GlobalHashSectionExecution++; // Comment it, it is only for stats.
					hash32 = (2166136261 ^ *(uint32_t *)(pbTarget+i+cbPattern-12+0)) * 709607;        
					hash32B = (2166136261 ^ *(uint32_t *)(pbTarget+i+cbPattern-12+4)) * 709607;        
					hash32C = (2166136261 ^ *(uint32_t *)(pbTarget+i+cbPattern-12+8)) * 709607;        
					hash32 = (hash32 ^ _rotl_KAZE(hash32C,5) ) * 709607;
					hash32 = (hash32 ^ _rotl_KAZE(hash32B,5) ) * 709607;
#ifdef HasherezadeBYTEWISEr3
					if ( bm_Hasherezade_HASH[( hash32 ^ (hash32 >> 16) ) & ( (1<<(HashTableSizer3))-1 )]==0 )
						Gulliver = cbPattern-(12-1);
#else
					hash32 = ( hash32 ^ (hash32 >> 16) ) & ( (1<<(HashTableSizer3))-1 );
					if ( (bm_Hasherezade_HASH[hash32>>3] & (1<<(hash32&0x7))) ==0 )
						Gulliver = cbPattern-(12-1);
#endif
#endif
				if ( Gulliver == 1 ) { // Means the Building-Block order 8/12 is found somewhere i.e. NO MAXIMUM SKIP
					if ( *(uint32_t *)&pbTarget[i] == ulHashPattern) {
						count = countSTATIC;
						while ( count !=0 && *(char *)(pbPattern+(countSTATIC-count)+4) == *(char *)(&pbTarget[i]+(countSTATIC-count)+4) )
							count--;
						if ( count == 0) return(pbTarget+i);
					}
				}
					i = i + Gulliver;
				GlobalI++; // Comment it, it is only for stats.
			} // while (i <= cbTarget-cbPattern)
			return(NULL);
// MEMMEM() MEMMEM() MEMMEM() MEMMEM() MEMMEM() MEMMEM() MEMMEM() MEMMEM() MEMMEM() MEMMEM() MEMMEM() MEMMEM() MEMMEM() MEMMEM() ]
	} // if ( cbPattern<=255 )
		} //if (cbTarget<HaystackThresholdr3)
	} //if ( cbPattern<4 )
}

By viewing downloads associated with this article you agree to the Terms of Service and the article's licence.

If a file you wish to view isn't highlighted, and is a text file (not binary), please let us know and we'll add colourisation support for it.

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

Sanmayce
Other
Bulgaria Bulgaria
A Bulgarian old boy interested in search techniques, nothing special.

You may also be interested in...

Pro
Permalink | Advertise | Privacy | Cookies | Terms of Use | Mobile
Web01-2016 | 2.8.181112.3 | Last Updated 22 Aug 2016
Article Copyright 2011 by Sanmayce
Everything else Copyright © CodeProject, 1999-2018
Layout: fixed | fluid