LinuxQuestions.org
View the Most Wanted LQ Wiki articles.
Go Back   LinuxQuestions.org > Forums > Non-*NIX Forums > Programming
User Name
Password
Programming This forum is for all programming questions.
The question does not have to be directly related to Linux and any language is fair game.

Notices

View Poll Results: Do you find this thread useful?
Yes 1 100.00%
No 0 0%
Voters: 1. You may not vote on this poll

Reply
 
Search this Thread
Old 07-15-2010, 02:15 PM   #1
Sanmayce
LQ Newbie
 
Registered: Jul 2010
Location: Sofia
Posts: 10

Rep: Reputation: 2
Karp-Rabin fast implementation


Hello everyone,

I want to share my tuned Karp-Rabin C function with Linux community:
http://encode.ru/threads/612-Fastest...ll=1#post21905

I would be glad to see an improved(more versatile) version,
regards.
 
Old 07-21-2010, 02:11 PM   #2
Sanmayce
LQ Newbie
 
Registered: Jul 2010
Location: Sofia
Posts: 10

Original Poster
Rep: Reputation: 2
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...
 
  


Reply

Tags
fast, search, text


Thread Tools Search this Thread
Search this Thread:

Advanced Search

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is Off
HTML code is Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Rabin-Karp Algo Questions mpapet Programming 3 02-10-2010 05:50 PM
FAST (Mega fast Mirror) SUSE 10 beta 4 download 1kyle Suse/Novell 2 09-07-2005 11:13 AM
Slamd64 is FAST FAST !!! SML Slackware 10 05-03-2005 06:36 AM
KDE 3.4 Beta 1 - Fast, Fast, very nice linchat Suse/Novell 0 01-26-2005 12:42 AM
Questions on Linux 2.4.20 TCP fast recovery and ECN implementation enjoyzj Linux - Networking 0 07-16-2004 08:57 AM


All times are GMT -5. The time now is 04:11 AM.

Main Menu
My LQ
Write for LQ
LinuxQuestions.org is looking for people interested in writing Editorials, Articles, Reviews, and more. If you'd like to contribute content, let us know.
Main Menu
Syndicate
RSS1  Latest Threads
RSS1  LQ News
Twitter: @linuxquestions
identi.ca: @linuxquestions
Facebook: linuxquestions Google+: linuxquestions
Open Source Consulting | Domain Registration