| Sanmayce |
07-21-2010 01:11 PM |
The function itself
Hi all,
Code:
#define ulPrime ((unsigned long) 0x00FF00F1)
#define ulBase ((unsigned long) 127)
// 9,223,372,036,854,775,807
// 257^7 = 74,051,159,531,521,793
// 257^8 = 19,031,147,999,601,100,801
// 127^9 = 8,594,754,748,609,397,887
// 57^10 = 362,033,331,456,891,249
// 13^16 = 665,416,609,183,179,841
// 5^12 = 244,140,625
// 13^8 = 815,730,721
long KarpRabinKaze (char * pbTarget,
char * pbPattern,
unsigned long cbTarget,
unsigned long cbPattern)
{
unsigned int i;
char * pbTargetMax = pbTarget + cbTarget;
char * pbPatternMax = pbPattern + cbPattern;
unsigned long ulBaseToPowerMod = 1;
register unsigned long ulHashPattern = 0;
unsigned long ulHashTarget = 0;
long hits = 0;
//unsigned long count;
//char * buf1;
//char * buf2;
if (cbPattern > cbTarget)
return(-1);
// Compute the power of the left most character in base ulBase
//for (i = 1; i < cbPattern; i++) ulBaseToPowerMod = (ulBase * ulBaseToPowerMod);
// Calculate the hash function for the src (and the first dst)
while (pbPattern < pbPatternMax)
{
// Below lines give 366KB/clock for 'underdog':
//ulHashPattern = (ulHashPattern*ulBase + *pbPattern);
//ulHashTarget = (ulHashTarget*ulBase + *pbTarget);
pbPattern++;
pbTarget++;
}
// Below lines give 436KB/clock for 'underdog' + requirement pattern to be 4 chars min.:
//ulHashPattern = ( (*(long *)(pbPattern-cbPattern)) & 0xffffff00 ) + *(pbPattern-1);
//ulHashTarget = ( (*(long *)(pbTarget-cbPattern)) & 0xffffff00 ) + *(pbTarget-1);
// Below lines give 482KB/clock for 'underdog' + requirement pattern to be 2 chars min.:
//ulHashPattern = ( (*(unsigned short *)(pbPattern-cbPattern)) | *(pbPattern-1) );
//ulHashTarget = ( (*(unsigned short *)(pbTarget-cbPattern)) | *(pbTarget-1) );
// Below lines give 482KB/clock for 'underdog' + requirement pattern to be 2 chars min.:
//ulHashPattern = ( (*(unsigned short *)(pbPattern-cbPattern)) & 0xff00 ) + *(pbPattern-1);
//ulHashTarget = ( (*(unsigned short *)(pbTarget-cbPattern)) & 0xff00 ) + *(pbTarget-1);
// Below lines give 605KB/clock for 'underdog' + requirement pattern to be 2 chars min.:
//ulHashPattern = ( (*(unsigned short *)(pbPattern-cbPattern))<<8 ) + *(pbPattern-1);
//ulHashTarget = ( (*(unsigned short *)(pbTarget-cbPattern))<<8 ) + *(pbTarget-1);
// Below lines give 668KB/clock for 'underdog':
ulHashPattern = ( (*(char *)(pbPattern-cbPattern))<<8 ) + *(pbPattern-1);
ulHashTarget = ( (*(char *)(pbTarget-cbPattern))<<8 ) + *(pbTarget-1);
// Dynamically produce hash values for the string as we go
for ( ;; )
{
if ( (ulHashPattern == ulHashTarget) && !memcmp(pbPattern-cbPattern, pbTarget-cbPattern, (unsigned int)cbPattern) )
// if ( ulHashPattern == ulHashTarget ) {
//
// count = cbPattern;
// buf1 = pbPattern-cbPattern;
// buf2 = pbTarget-cbPattern;
// while ( --count && *(char *)buf1 == *(char *)buf2 ) {
// buf1 = (char *)buf1 + 1;
// buf2 = (char *)buf2 + 1;
// }
//
// if ( *((unsigned char *)buf1) - *((unsigned char *)buf2) == 0) hits++;
// }
return((long)(pbTarget-cbPattern));
//hits++;
if (pbTarget == pbTargetMax)
return(-1);
// Below line gives 482KB/clock for 'underdog' + requirement pattern to be 2 chars min.:
//ulHashTarget = ( (*(unsigned short *)(pbTarget+1-cbPattern)) | *pbTarget );
// Below line gives 436KB/clock for 'underdog' + requirement pattern to be 4 chars min.:
//ulHashTarget = ( (*(long *)(pbTarget+1-cbPattern)) & 0xffffff00 ) + *pbTarget;
//; Line 696
// movsx esi, BYTE PTR [ebx]
// mov ecx, DWORD PTR [edx+1]
// and ecx, -256 ; ffffff00H
// add ecx, esi
// Below line gives 482KB/clock for 'underdog' + requirement pattern to be 2 chars min.:
//ulHashTarget = ( (*(unsigned short *)(pbTarget+1-cbPattern)) & 0xff00 ) + *pbTarget;
//; Line 691
// movsx esi, BYTE PTR [ebx]
// xor ecx, ecx
// mov cx, WORD PTR [edx+1]
// and ecx, 65280 ; 0000ff00H
// add ecx, esi
// Below line gives 605KB/clock for 'underdog' + requirement pattern to be 2 chars min.:
//ulHashTarget = ( (*(unsigned short *)(pbTarget+1-cbPattern))<<8 ) + *pbTarget;
// Below line gives 668KB/clock for 'underdog':
ulHashTarget = ( (*(char *)(pbTarget+1-cbPattern))<<8 ) + *pbTarget;
//; Line 718
// movsx ecx, BYTE PTR [eax+1]
// movsx edx, BYTE PTR [ebp]
// shl ecx, 8
// add ecx, edx
// Below line gives 366KB/clock for 'underdog':
//ulHashTarget = (ulHashTarget - *(pbTarget-cbPattern)*ulBaseToPowerMod)*ulBase + *pbTarget;
pbTarget++;
}
}
I wait for any improvements... |
