Skip to content

Instantly share code, notes, and snippets.

@jaytaylor

jaytaylor/railgun.c

Created December 23, 2013 18:38
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save jaytaylor/8102304 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save jaytaylor/8102304 to your computer and use it in GitHub Desktop.
Download ZIP
A blend of the famous Karp-Rabin-Boyer-Moore-Horspool-Sunday algorithms named Railgun.
Raw
railgun.c
// Originally found at: http://www.sanmayce.com/Railgun/index.html
// ---------------------------------------------------------------
// All Railgun variants are written by Georgi 'Kaze', they are free, however I expect the user to mention its homepage, that is: http://www.sanmayce.com/Railgun/index.html
// Author's email: [email protected]
// Caution: For better speed the case 'if (cbPattern==1)' was removed, so Pattern must be longer than 1 char.
char * Railgun_Doublet (char * pbTarget, char * pbPattern, uint32_t cbTarget, uint32_t cbPattern)
{
char * pbTargetMax = pbTarget + cbTarget;
register uint32_t ulHashPattern;
uint32_t ulHashTarget, count, countSTATIC;
if (cbPattern > cbTarget) return(NULL);
countSTATIC = cbPattern-2;
pbTarget = pbTarget+cbPattern;
ulHashPattern = (*(uint16_t *)(pbPattern));
for ( ;; ) {
if ( ulHashPattern == (*(uint16_t *)(pbTarget-cbPattern)) ) {
count = countSTATIC;
while ( count && *(char *)(pbPattern+2+(countSTATIC-count)) == *(char *)(pbTarget-cbPattern+2+(countSTATIC-count)) ) {
count--;
}
if ( count == 0 ) return((pbTarget-cbPattern));
}
pbTarget++;
if (pbTarget > pbTargetMax) return(NULL);
}
}
/*
; Listing generated by: Microsoft (R) C/C++ Optimizing Compiler Version 16.00.30319.01 for x64
PUBLIC Railgun_Doublet
pdata SEGMENT
$pdata$Railgun_Doublet DD imagerel $LN21
DD imagerel $LN21+25
DD imagerel $unwind$Railgun_Doublet
$pdata$2$Railgun_Doublet DD imagerel $LN21+25
DD imagerel $LN21+136
DD imagerel $chain$2$Railgun_Doublet
$pdata$4$Railgun_Doublet DD imagerel $LN21+136
DD imagerel $LN21+171
DD imagerel $chain$4$Railgun_Doublet
pdata ENDS
xdata SEGMENT
$unwind$Railgun_Doublet DD 020301H
DD 030026003H
$chain$2$Railgun_Doublet DD 061221H
DD 06c412H
DD 05740aH
DD 045405H
DD imagerel $LN21
DD imagerel $LN21+25
DD imagerel $unwind$Railgun_Doublet
$chain$4$Railgun_Doublet DD 060021H
DD 06c400H
DD 057400H
DD 045400H
DD imagerel $LN21
DD imagerel $LN21+25
DD imagerel $unwind$Railgun_Doublet
; Function compile flags: /Ogtpy
xdata ENDS
_TEXT SEGMENT
tv169 = 24
pbTarget$ = 24
pbPattern$ = 32
cbTarget$ = 40
cbPattern$ = 48
Railgun_Doublet PROC
; 2639 : {
$LN21:
00c30 40 53 push rbx
00c32 56 push rsi
; 2640 : char * pbTargetMax = pbTarget + cbTarget;
00c33 41 8b d8 mov ebx, r8d
00c36 48 8b f2 mov rsi, rdx
00c39 4c 8b d1 mov r10, rcx
00c3c 48 03 d9 add rbx, rcx
; 2641 : register uint32_t ulHashPattern;
; 2642 : uint32_t ulHashTarget, count, countSTATIC;
; 2643 :
; 2644 : if (cbPattern > cbTarget) return(NULL);
00c3f 45 3b c8 cmp r9d, r8d
00c42 76 05 jbe SHORT $LN8@Railgun_du
00c44 33 c0 xor eax, eax
; 2662 : }
00c46 5e pop rsi
00c47 5b pop rbx
00c48 c3 ret 0
$LN8@Railgun_du:
00c49 48 89 6c 24 20 mov QWORD PTR [rsp+32], rbp
00c4e 48 89 7c 24 28 mov QWORD PTR [rsp+40], rdi
; 2645 :
; 2646 : countSTATIC = cbPattern-2;
; 2647 :
; 2648 : pbTarget = pbTarget+cbPattern;
; 2649 : ulHashPattern = (*(uint16_t *)(pbPattern));
00c53 0f b7 3a movzx edi, WORD PTR [rdx]
00c56 4c 89 64 24 30 mov QWORD PTR [rsp+48], r12
00c5b 45 8b e1 mov r12d, r9d
; 2661 : }
00c5e 48 8b ea mov rbp, rdx
00c61 4d 03 d4 add r10, r12
00c64 45 8d 59 fe lea r11d, DWORD PTR [r9-2]
00c68 4d 8b c2 mov r8, r10
00c6b 4d 2b c4 sub r8, r12
00c6e 48 f7 dd neg rbp
$LL7@Railgun_du:
; 2650 :
; 2651 : for ( ;; ) {
; 2652 : if ( ulHashPattern == (*(uint16_t *)(pbTarget-cbPattern)) ) {
00c71 41 0f b7 00 movzx eax, WORD PTR [r8]
00c75 3b f8 cmp edi, eax
00c77 75 43 jne SHORT $LN2@Railgun_du
; 2653 : count = countSTATIC;
00c79 41 8b d3 mov edx, r11d
; 2654 : while ( count && *(char *)(pbPattern+2+(countSTATIC-count)) == *(char *)(pbTarget-cbPattern+2+(countSTATIC-count)) ) {
00c7c 45 85 db test r11d, r11d
00c7f 74 1f je SHORT $LN17@Railgun_du
00c81 48 8d 4e 02 lea rcx, QWORD PTR [rsi+2]
00c85 4d 8d 0c 28 lea r9, QWORD PTR [r8+rbp]
00c89 0f 1f 80 00 00
00 00 npad 7
$LL4@Railgun_du:
00c90 41 0f b6 04 09 movzx eax, BYTE PTR [r9+rcx]
00c95 38 01 cmp BYTE PTR [rcx], al
00c97 75 1f jne SHORT $LN3@Railgun_du
; 2655 : count--;
00c99 48 ff c1 inc rcx
00c9c ff ca dec edx
00c9e 75 f0 jne SHORT $LL4@Railgun_du
$LN17@Railgun_du:
00ca0 48 8b 7c 24 28 mov rdi, QWORD PTR [rsp+40]
00ca5 48 8b 6c 24 20 mov rbp, QWORD PTR [rsp+32]
; 2656 : }
; 2657 : if ( count == 0 ) return((pbTarget-cbPattern));
00caa 4d 2b d4 sub r10, r12
00cad 4c 8b 64 24 30 mov r12, QWORD PTR [rsp+48]
00cb2 49 8b c2 mov rax, r10
; 2662 : }
00cb5 5e pop rsi
00cb6 5b pop rbx
00cb7 c3 ret 0
$LN3@Railgun_du:
; 2656 : }
; 2657 : if ( count == 0 ) return((pbTarget-cbPattern));
00cb8 85 d2 test edx, edx
00cba 74 e4 je SHORT $LN17@Railgun_du
$LN2@Railgun_du:
; 2658 : }
; 2659 : pbTarget++;
00cbc 49 ff c2 inc r10
00cbf 49 ff c0 inc r8
; 2660 : if (pbTarget > pbTargetMax) return(NULL);
00cc2 4c 3b d3 cmp r10, rbx
00cc5 76 aa jbe SHORT $LL7@Railgun_du
00cc7 48 8b 7c 24 28 mov rdi, QWORD PTR [rsp+40]
00ccc 48 8b 6c 24 20 mov rbp, QWORD PTR [rsp+32]
00cd1 4c 8b 64 24 30 mov r12, QWORD PTR [rsp+48]
00cd6 33 c0 xor eax, eax
; 2662 : }
00cd8 5e pop rsi
00cd9 5b pop rbx
00cda c3 ret 0
Railgun_Doublet ENDP
_TEXT ENDS
*/
//
/*
Testbed: [File: OSHO.TXT 206,908,949 bytes; LinesEncountered: 2,459,508; Windows 7 64bit; Microsoft 2010 64bit compiler; E7500 2.93GHz dual DDR2]
Searching for Pattern('an',2bytes) into String(206908949bytes) line-by-line ...
strstr_Microsoft_hits/strstr_Microsoft_clocks: 1212509/544
strstr_Microsoft performance: 248KB/clock
StrnglenTRAVERSED: 138478024 bytes
strstr_GNU_C_Library_hits/strstr_GNU_C_Library_clocks: 1212509/359
strstr_GNU_C_Library performance: 376KB/clock
StrnglenTRAVERSED: 138478024 bytes
Railgun_Doublet_hits/Railgun_Doublet_clocks: 1212509/321
Railgun_Doublet performance: 421KB/clock
StrnglenTRAVERSED: 138478024 bytes
Railgun_Quadruplet_8Triplet_hits/Railgun_Quadruplet_8Triplet_clocks: 1212509/335
Railgun_Quadruplet_8Triplet performance: 403KB/clock
StrnglenTRAVERSED: 138478024 bytes
Railgun_Mischa_8Triplet_hits/Railgun_Mischa_8Triplet_clocks: 1212509/348
Railgun_Mischa_8Triplet performance: 388KB/clock
StrnglenTRAVERSED: 138478024 bytes
BNDM_32_hits/BNDM_32_clocks: 1212509/505
BNDM_32 performance: 267KB/clock
StrnglenTRAVERSED: 138478024 bytes
Searching for Pattern('to',2bytes) into String(206908949bytes) line-by-line ...
strstr_Microsoft_hits/strstr_Microsoft_clocks: 780175/616
strstr_Microsoft performance: 260KB/clock
StrnglenTRAVERSED: 164505415 bytes
strstr_GNU_C_Library_hits/strstr_GNU_C_Library_clocks: 780175/401
strstr_GNU_C_Library performance: 400KB/clock
StrnglenTRAVERSED: 164505415 bytes
Railgun_Doublet_hits/Railgun_Doublet_clocks: 780175/337
Railgun_Doublet performance: 476KB/clock
StrnglenTRAVERSED: 164505415 bytes
Railgun_Quadruplet_8Triplet_hits/Railgun_Quadruplet_8Triplet_clocks: 780175/366
Railgun_Quadruplet_8Triplet performance: 438KB/clock
StrnglenTRAVERSED: 164505415 bytes
Railgun_Mischa_8Triplet_hits/Railgun_Mischa_8Triplet_clocks: 780175/379
Railgun_Mischa_8Triplet performance: 423KB/clock
StrnglenTRAVERSED: 164505415 bytes
BNDM_32_hits/BNDM_32_clocks: 780175/553
BNDM_32 performance: 290KB/clock
StrnglenTRAVERSED: 164505415 bytes
Searching for Pattern('TDK',3bytes) into String(206908949bytes) line-by-line ...
strstr_Microsoft_hits/strstr_Microsoft_clocks: 0/627
strstr_Microsoft performance: 318KB/clock
StrnglenTRAVERSED: 204449441 bytes
strstr_GNU_C_Library_hits/strstr_GNU_C_Library_clocks: 0/354
strstr_GNU_C_Library performance: 564KB/clock
StrnglenTRAVERSED: 204449441 bytes
Railgun_Doublet_hits/Railgun_Doublet_clocks: 0/362
Railgun_Doublet performance: 551KB/clock
StrnglenTRAVERSED: 204449441 bytes
Railgun_Quadruplet_8Triplet_hits/Railgun_Quadruplet_8Triplet_clocks: 0/354
Railgun_Quadruplet_8Triplet performance: 564KB/clock
StrnglenTRAVERSED: 204449441 bytes
Railgun_Mischa_8Triplet_hits/Railgun_Mischa_8Triplet_clocks: 0/359
Railgun_Mischa_8Triplet performance: 556KB/clock
StrnglenTRAVERSED: 204449441 bytes
BNDM_32_hits/BNDM_32_clocks: 0/432
BNDM_32 performance: 462KB/clock
StrnglenTRAVERSED: 204449441 bytes
Searching for Pattern('the',3bytes) into String(206908949bytes) line-by-line ...
strstr_Microsoft_hits/strstr_Microsoft_clocks: 1192002/568
strstr_Microsoft performance: 233KB/clock
StrnglenTRAVERSED: 135882884 bytes
strstr_GNU_C_Library_hits/strstr_GNU_C_Library_clocks: 1192002/383
strstr_GNU_C_Library performance: 346KB/clock
StrnglenTRAVERSED: 135882884 bytes
Railgun_Doublet_hits/Railgun_Doublet_clocks: 1192002/337
Railgun_Doublet performance: 393KB/clock
StrnglenTRAVERSED: 135882884 bytes
Railgun_Quadruplet_8Triplet_hits/Railgun_Quadruplet_8Triplet_clocks: 1192002/354
Railgun_Quadruplet_8Triplet performance: 374KB/clock
StrnglenTRAVERSED: 135882884 bytes
Railgun_Mischa_8Triplet_hits/Railgun_Mischa_8Triplet_clocks: 1192002/363
Railgun_Mischa_8Triplet performance: 365KB/clock
StrnglenTRAVERSED: 135882884 bytes
BNDM_32_hits/BNDM_32_clocks: 1192002/519
BNDM_32 performance: 255KB/clock
StrnglenTRAVERSED: 135882884 bytes
Searching for Pattern('fast',4bytes) into String(206908949bytes) line-by-line ...
strstr_Microsoft_hits/strstr_Microsoft_clocks: 5384/640
strstr_Microsoft performance: 311KB/clock
StrnglenTRAVERSED: 204186782 bytes
strstr_GNU_C_Library_hits/strstr_GNU_C_Library_clocks: 5384/369
strstr_GNU_C_Library performance: 540KB/clock
StrnglenTRAVERSED: 204186782 bytes
Railgun_Doublet_hits/Railgun_Doublet_clocks: 5384/362
Railgun_Doublet performance: 550KB/clock
StrnglenTRAVERSED: 204186782 bytes
Railgun_Quadruplet_8Triplet_hits/Railgun_Quadruplet_8Triplet_clocks: 5384/485
Railgun_Quadruplet_8Triplet performance: 411KB/clock
StrnglenTRAVERSED: 204186782 bytes
Railgun_Mischa_8Triplet_hits/Railgun_Mischa_8Triplet_clocks: 5384/429
Railgun_Mischa_8Triplet performance: 464KB/clock
StrnglenTRAVERSED: 204186782 bytes
BNDM_32_hits/BNDM_32_clocks: 5384/510
BNDM_32 performance: 390KB/clock
StrnglenTRAVERSED: 204186782 bytes
Searching for Pattern('easy',4bytes) into String(206908949bytes) line-by-line ...
strstr_Microsoft_hits/strstr_Microsoft_clocks: 4825/771
strstr_Microsoft performance: 258KB/clock
StrnglenTRAVERSED: 204202166 bytes
strstr_GNU_C_Library_hits/strstr_GNU_C_Library_clocks: 4825/504
strstr_GNU_C_Library performance: 395KB/clock
StrnglenTRAVERSED: 204202166 bytes
Railgun_Doublet_hits/Railgun_Doublet_clocks: 4825/373
Railgun_Doublet performance: 534KB/clock
StrnglenTRAVERSED: 204202166 bytes
Railgun_Quadruplet_8Triplet_hits/Railgun_Quadruplet_8Triplet_clocks: 4825/549
Railgun_Quadruplet_8Triplet performance: 363KB/clock
StrnglenTRAVERSED: 204202166 bytes
Railgun_Mischa_8Triplet_hits/Railgun_Mischa_8Triplet_clocks: 4825/429
Railgun_Mischa_8Triplet performance: 464KB/clock
StrnglenTRAVERSED: 204202166 bytes
BNDM_32_hits/BNDM_32_clocks: 4825/526
BNDM_32 performance: 379KB/clock
StrnglenTRAVERSED: 204202166 bytes
Searching for Pattern('grmbl',5bytes) into String(206908949bytes) line-by-line ...
strstr_Microsoft_hits/strstr_Microsoft_clocks: 0/645
strstr_Microsoft performance: 309KB/clock
StrnglenTRAVERSED: 204449441 bytes
strstr_GNU_C_Library_hits/strstr_GNU_C_Library_clocks: 0/373
strstr_GNU_C_Library performance: 535KB/clock
StrnglenTRAVERSED: 204449441 bytes
Railgun_Doublet_hits/Railgun_Doublet_clocks: 0/361
Railgun_Doublet performance: 553KB/clock
StrnglenTRAVERSED: 204449441 bytes
Railgun_Quadruplet_8Triplet_hits/Railgun_Quadruplet_8Triplet_clocks: 0/483
Railgun_Quadruplet_8Triplet performance: 413KB/clock
StrnglenTRAVERSED: 204449441 bytes
Railgun_Mischa_8Triplet_hits/Railgun_Mischa_8Triplet_clocks: 0/429
Railgun_Mischa_8Triplet performance: 465KB/clock
StrnglenTRAVERSED: 204449441 bytes
BNDM_32_hits/BNDM_32_clocks: 0/442
BNDM_32 performance: 451KB/clock
StrnglenTRAVERSED: 204449441 bytes
Searching for Pattern('email',5bytes) into String(206908949bytes) line-by-line ...
strstr_Microsoft_hits/strstr_Microsoft_clocks: 1/764
strstr_Microsoft performance: 261KB/clock
StrnglenTRAVERSED: 204449414 bytes
strstr_GNU_C_Library_hits/strstr_GNU_C_Library_clocks: 1/497
strstr_GNU_C_Library performance: 401KB/clock
StrnglenTRAVERSED: 204449414 bytes
Railgun_Doublet_hits/Railgun_Doublet_clocks: 1/363
Railgun_Doublet performance: 550KB/clock
StrnglenTRAVERSED: 204449414 bytes
Railgun_Quadruplet_8Triplet_hits/Railgun_Quadruplet_8Triplet_clocks: 1/546
Railgun_Quadruplet_8Triplet performance: 365KB/clock
StrnglenTRAVERSED: 204449414 bytes
Railgun_Mischa_8Triplet_hits/Railgun_Mischa_8Triplet_clocks: 1/429
Railgun_Mischa_8Triplet performance: 465KB/clock
StrnglenTRAVERSED: 204449414 bytes
BNDM_32_hits/BNDM_32_clocks: 1/505
BNDM_32 performance: 395KB/clock
StrnglenTRAVERSED: 204449414 bytes
Searching for Pattern('pasting',7bytes) into String(206908949bytes) line-by-line ...
strstr_Microsoft_hits/strstr_Microsoft_clocks: 2/640
strstr_Microsoft performance: 311KB/clock
StrnglenTRAVERSED: 204449363 bytes
strstr_GNU_C_Library_hits/strstr_GNU_C_Library_clocks: 2/368
strstr_GNU_C_Library performance: 542KB/clock
StrnglenTRAVERSED: 204449363 bytes
Railgun_Doublet_hits/Railgun_Doublet_clocks: 2/357
Railgun_Doublet performance: 559KB/clock
StrnglenTRAVERSED: 204449363 bytes
Railgun_Quadruplet_8Triplet_hits/Railgun_Quadruplet_8Triplet_clocks: 2/475
Railgun_Quadruplet_8Triplet performance: 420KB/clock
StrnglenTRAVERSED: 204449363 bytes
Railgun_Mischa_8Triplet_hits/Railgun_Mischa_8Triplet_clocks: 2/429
Railgun_Mischa_8Triplet performance: 465KB/clock
StrnglenTRAVERSED: 204449363 bytes
BNDM_32_hits/BNDM_32_clocks: 2/498
BNDM_32 performance: 400KB/clock
StrnglenTRAVERSED: 204449363 bytes
Searching for Pattern('amazing',7bytes) into String(206908949bytes) line-by-line ...
strstr_Microsoft_hits/strstr_Microsoft_clocks: 319/710
strstr_Microsoft performance: 281KB/clock
StrnglenTRAVERSED: 204432134 bytes
strstr_GNU_C_Library_hits/strstr_GNU_C_Library_clocks: 319/438
strstr_GNU_C_Library performance: 455KB/clock
StrnglenTRAVERSED: 204432134 bytes
Railgun_Doublet_hits/Railgun_Doublet_clocks: 319/358
Railgun_Doublet performance: 557KB/clock
StrnglenTRAVERSED: 204432134 bytes
Railgun_Quadruplet_8Triplet_hits/Railgun_Quadruplet_8Triplet_clocks: 319/506
Railgun_Quadruplet_8Triplet performance: 394KB/clock
StrnglenTRAVERSED: 204432134 bytes
Railgun_Mischa_8Triplet_hits/Railgun_Mischa_8Triplet_clocks: 319/429
Railgun_Mischa_8Triplet performance: 465KB/clock
StrnglenTRAVERSED: 204432134 bytes
BNDM_32_hits/BNDM_32_clocks: 319/461
BNDM_32 performance: 433KB/clock
StrnglenTRAVERSED: 204432134 bytes
Searching for Pattern('underdog',8bytes) into String(206908949bytes) line-by-line ...
strstr_Microsoft_hits/strstr_Microsoft_clocks: 4/665
strstr_Microsoft performance: 300KB/clock
StrnglenTRAVERSED: 204449185 bytes
strstr_GNU_C_Library_hits/strstr_GNU_C_Library_clocks: 4/391
strstr_GNU_C_Library performance: 510KB/clock
StrnglenTRAVERSED: 204449185 bytes
Railgun_Doublet_hits/Railgun_Doublet_clocks: 4/361
Railgun_Doublet performance: 553KB/clock
StrnglenTRAVERSED: 204449185 bytes
Railgun_Quadruplet_8Triplet_hits/Railgun_Quadruplet_8Triplet_clocks: 4/482
Railgun_Quadruplet_8Triplet performance: 414KB/clock
StrnglenTRAVERSED: 204449185 bytes
Railgun_Mischa_8Triplet_hits/Railgun_Mischa_8Triplet_clocks: 4/430
Railgun_Mischa_8Triplet performance: 464KB/clock
StrnglenTRAVERSED: 204449185 bytes
BNDM_32_hits/BNDM_32_clocks: 4/476
BNDM_32 performance: 419KB/clock
StrnglenTRAVERSED: 204449185 bytes
Searching for Pattern('superdog',8bytes) into String(206908949bytes) line-by-line ...
strstr_Microsoft_hits/strstr_Microsoft_clocks: 0/695
strstr_Microsoft performance: 287KB/clock
StrnglenTRAVERSED: 204449441 bytes
strstr_GNU_C_Library_hits/strstr_GNU_C_Library_clocks: 0/426
strstr_GNU_C_Library performance: 468KB/clock
StrnglenTRAVERSED: 204449441 bytes
Railgun_Doublet_hits/Railgun_Doublet_clocks: 0/355
Railgun_Doublet performance: 562KB/clock
StrnglenTRAVERSED: 204449441 bytes
Railgun_Quadruplet_8Triplet_hits/Railgun_Quadruplet_8Triplet_clocks: 0/500
Railgun_Quadruplet_8Triplet performance: 399KB/clock
StrnglenTRAVERSED: 204449441 bytes
Railgun_Mischa_8Triplet_hits/Railgun_Mischa_8Triplet_clocks: 0/430
Railgun_Mischa_8Triplet performance: 464KB/clock
StrnglenTRAVERSED: 204449441 bytes
BNDM_32_hits/BNDM_32_clocks: 0/475
BNDM_32 performance: 420KB/clock
StrnglenTRAVERSED: 204449441 bytes
Searching for Pattern('participants',12bytes) into String(206908949bytes) line-by-line ...
strstr_Microsoft_hits/strstr_Microsoft_clocks: 141/640
strstr_Microsoft performance: 311KB/clock
StrnglenTRAVERSED: 204441500 bytes
strstr_GNU_C_Library_hits/strstr_GNU_C_Library_clocks: 141/369
strstr_GNU_C_Library performance: 541KB/clock
StrnglenTRAVERSED: 204441500 bytes
Railgun_Doublet_hits/Railgun_Doublet_clocks: 141/351
Railgun_Doublet performance: 568KB/clock
StrnglenTRAVERSED: 204441500 bytes
Railgun_Quadruplet_8Triplet_hits/Railgun_Quadruplet_8Triplet_clocks: 141/460
Railgun_Quadruplet_8Triplet performance: 434KB/clock
StrnglenTRAVERSED: 204441500 bytes
Railgun_Mischa_8Triplet_hits/Railgun_Mischa_8Triplet_clocks: 141/429
Railgun_Mischa_8Triplet performance: 465KB/clock
StrnglenTRAVERSED: 204441500 bytes
BNDM_32_hits/BNDM_32_clocks: 141/457
BNDM_32 performance: 436KB/clock
StrnglenTRAVERSED: 204441500 bytes
Searching for Pattern('skillessness',12bytes) into String(206908949bytes) line-by-line ...
strstr_Microsoft_hits/strstr_Microsoft_clocks: 0/695
strstr_Microsoft performance: 287KB/clock
StrnglenTRAVERSED: 204449441 bytes
strstr_GNU_C_Library_hits/strstr_GNU_C_Library_clocks: 0/425
strstr_GNU_C_Library performance: 469KB/clock
StrnglenTRAVERSED: 204449441 bytes
Railgun_Doublet_hits/Railgun_Doublet_clocks: 0/348
Railgun_Doublet performance: 573KB/clock
StrnglenTRAVERSED: 204449441 bytes
Railgun_Quadruplet_8Triplet_hits/Railgun_Quadruplet_8Triplet_clocks: 0/486
Railgun_Quadruplet_8Triplet performance: 410KB/clock
StrnglenTRAVERSED: 204449441 bytes
Railgun_Mischa_8Triplet_hits/Railgun_Mischa_8Triplet_clocks: 0/428
Railgun_Mischa_8Triplet performance: 466KB/clock
StrnglenTRAVERSED: 204449441 bytes
BNDM_32_hits/BNDM_32_clocks: 0/446
BNDM_32 performance: 447KB/clock
StrnglenTRAVERSED: 204449441 bytes
Searching for Pattern('I should have known',19bytes) into String(206908949bytes) line-by-line ...
strstr_Microsoft_hits/strstr_Microsoft_clocks: 1/630
strstr_Microsoft performance: 316KB/clock
StrnglenTRAVERSED: 204449346 bytes
strstr_GNU_C_Library_hits/strstr_GNU_C_Library_clocks: 1/358
strstr_GNU_C_Library performance: 557KB/clock
StrnglenTRAVERSED: 204449346 bytes
Railgun_Doublet_hits/Railgun_Doublet_clocks: 1/340
Railgun_Doublet performance: 587KB/clock
StrnglenTRAVERSED: 204449346 bytes
Railgun_Quadruplet_8Triplet_hits/Railgun_Quadruplet_8Triplet_clocks: 1/433
Railgun_Quadruplet_8Triplet performance: 461KB/clock
StrnglenTRAVERSED: 204449346 bytes
Railgun_Mischa_8Triplet_hits/Railgun_Mischa_8Triplet_clocks: 1/428
Railgun_Mischa_8Triplet performance: 466KB/clock
StrnglenTRAVERSED: 204449346 bytes
BNDM_32_hits/BNDM_32_clocks: 1/458
BNDM_32 performance: 435KB/clock
StrnglenTRAVERSED: 204449346 bytes
Searching for Pattern('human consciousness',19bytes) into String(206908949bytes) line-by-line ...
strstr_Microsoft_hits/strstr_Microsoft_clocks: 514/686
strstr_Microsoft performance: 291KB/clock
StrnglenTRAVERSED: 204422699 bytes
strstr_GNU_C_Library_hits/strstr_GNU_C_Library_clocks: 514/414
strstr_GNU_C_Library performance: 482KB/clock
StrnglenTRAVERSED: 204422699 bytes
Railgun_Doublet_hits/Railgun_Doublet_clocks: 514/336
Railgun_Doublet performance: 594KB/clock
StrnglenTRAVERSED: 204422699 bytes
Railgun_Quadruplet_8Triplet_hits/Railgun_Quadruplet_8Triplet_clocks: 514/456
Railgun_Quadruplet_8Triplet performance: 437KB/clock
StrnglenTRAVERSED: 204422699 bytes
Railgun_Mischa_8Triplet_hits/Railgun_Mischa_8Triplet_clocks: 514/428
Railgun_Mischa_8Triplet performance: 466KB/clock
StrnglenTRAVERSED: 204422699 bytes
BNDM_32_hits/BNDM_32_clocks: 514/452
BNDM_32 performance: 441KB/clock
StrnglenTRAVERSED: 204422699 bytes
D:\_KAZE_strstr_SHORT-SHOWDOWN_7Trident2_7Hasherezade_7Gulliver2>
*/
//
/*
Testbed: [File: OSHO.TXT 206,908,949 bytes; LinesEncountered: 2,459,508; Windows 7 64bit; Intel 2011 64bit compiler; E7500 2.93GHz dual DDR2]
Searching for Pattern('an',2bytes) into String(206908949bytes) line-by-line ...
strstr_Microsoft_hits/strstr_Microsoft_clocks: 1212509/567
strstr_Microsoft performance: 238KB/clock
StrnglenTRAVERSED: 138478024 bytes
strstr_GNU_C_Library_hits/strstr_GNU_C_Library_clocks: 1212509/456
strstr_GNU_C_Library performance: 296KB/clock
StrnglenTRAVERSED: 138478024 bytes
Railgun_Doublet_hits/Railgun_Doublet_clocks: 1212509/388
Railgun_Doublet performance: 348KB/clock
StrnglenTRAVERSED: 138478024 bytes
Railgun_Quadruplet_8Triplet_hits/Railgun_Quadruplet_8Triplet_clocks: 1212509/417
Railgun_Quadruplet_8Triplet performance: 324KB/clock
StrnglenTRAVERSED: 138478024 bytes
Railgun_Mischa_8Triplet_hits/Railgun_Mischa_8Triplet_clocks: 1212509/406
Railgun_Mischa_8Triplet performance: 333KB/clock
StrnglenTRAVERSED: 138478024 bytes
BNDM_32_hits/BNDM_32_clocks: 1212509/559
BNDM_32 performance: 241KB/clock
StrnglenTRAVERSED: 138478024 bytes
Searching for Pattern('to',2bytes) into String(206908949bytes) line-by-line ...
strstr_Microsoft_hits/strstr_Microsoft_clocks: 780175/628
strstr_Microsoft performance: 255KB/clock
StrnglenTRAVERSED: 164505415 bytes
strstr_GNU_C_Library_hits/strstr_GNU_C_Library_clocks: 780175/502
strstr_GNU_C_Library performance: 320KB/clock
StrnglenTRAVERSED: 164505415 bytes
Railgun_Doublet_hits/Railgun_Doublet_clocks: 780175/404
Railgun_Doublet performance: 397KB/clock
StrnglenTRAVERSED: 164505415 bytes
Railgun_Quadruplet_8Triplet_hits/Railgun_Quadruplet_8Triplet_clocks: 780175/451
Railgun_Quadruplet_8Triplet performance: 356KB/clock
StrnglenTRAVERSED: 164505415 bytes
Railgun_Mischa_8Triplet_hits/Railgun_Mischa_8Triplet_clocks: 780175/439
Railgun_Mischa_8Triplet performance: 365KB/clock
StrnglenTRAVERSED: 164505415 bytes
BNDM_32_hits/BNDM_32_clocks: 780175/611
BNDM_32 performance: 262KB/clock
StrnglenTRAVERSED: 164505415 bytes
Searching for Pattern('TDK',3bytes) into String(206908949bytes) line-by-line ...
strstr_Microsoft_hits/strstr_Microsoft_clocks: 0/618
strstr_Microsoft performance: 323KB/clock
StrnglenTRAVERSED: 204449441 bytes
strstr_GNU_C_Library_hits/strstr_GNU_C_Library_clocks: 0/474
strstr_GNU_C_Library performance: 421KB/clock
StrnglenTRAVERSED: 204449441 bytes
Railgun_Doublet_hits/Railgun_Doublet_clocks: 0/430
Railgun_Doublet performance: 464KB/clock
StrnglenTRAVERSED: 204449441 bytes
Railgun_Quadruplet_8Triplet_hits/Railgun_Quadruplet_8Triplet_clocks: 0/436
Railgun_Quadruplet_8Triplet performance: 457KB/clock
StrnglenTRAVERSED: 204449441 bytes
Railgun_Mischa_8Triplet_hits/Railgun_Mischa_8Triplet_clocks: 0/511
Railgun_Mischa_8Triplet performance: 390KB/clock
StrnglenTRAVERSED: 204449441 bytes
BNDM_32_hits/BNDM_32_clocks: 0/488
BNDM_32 performance: 409KB/clock
StrnglenTRAVERSED: 204449441 bytes
Searching for Pattern('the',3bytes) into String(206908949bytes) line-by-line ...
strstr_Microsoft_hits/strstr_Microsoft_clocks: 1192002/584
strstr_Microsoft performance: 227KB/clock
StrnglenTRAVERSED: 135882884 bytes
strstr_GNU_C_Library_hits/strstr_GNU_C_Library_clocks: 1192002/480
strstr_GNU_C_Library performance: 276KB/clock
StrnglenTRAVERSED: 135882884 bytes
Railgun_Doublet_hits/Railgun_Doublet_clocks: 1192002/404
Railgun_Doublet performance: 328KB/clock
StrnglenTRAVERSED: 135882884 bytes
Railgun_Quadruplet_8Triplet_hits/Railgun_Quadruplet_8Triplet_clocks: 1192002/427
Railgun_Quadruplet_8Triplet performance: 310KB/clock
StrnglenTRAVERSED: 135882884 bytes
Railgun_Mischa_8Triplet_hits/Railgun_Mischa_8Triplet_clocks: 1192002/454
Railgun_Mischa_8Triplet performance: 292KB/clock
StrnglenTRAVERSED: 135882884 bytes
BNDM_32_hits/BNDM_32_clocks: 1192002/567
BNDM_32 performance: 234KB/clock
StrnglenTRAVERSED: 135882884 bytes
Searching for Pattern('fast',4bytes) into String(206908949bytes) line-by-line ...
strstr_Microsoft_hits/strstr_Microsoft_clocks: 5384/633
strstr_Microsoft performance: 315KB/clock
StrnglenTRAVERSED: 204186782 bytes
strstr_GNU_C_Library_hits/strstr_GNU_C_Library_clocks: 5384/478
strstr_GNU_C_Library performance: 417KB/clock
StrnglenTRAVERSED: 204186782 bytes
Railgun_Doublet_hits/Railgun_Doublet_clocks: 5384/430
Railgun_Doublet performance: 463KB/clock
StrnglenTRAVERSED: 204186782 bytes
Railgun_Quadruplet_8Triplet_hits/Railgun_Quadruplet_8Triplet_clocks: 5384/558
Railgun_Quadruplet_8Triplet performance: 357KB/clock
StrnglenTRAVERSED: 204186782 bytes
Railgun_Mischa_8Triplet_hits/Railgun_Mischa_8Triplet_clocks: 5384/483
Railgun_Mischa_8Triplet performance: 412KB/clock
StrnglenTRAVERSED: 204186782 bytes
BNDM_32_hits/BNDM_32_clocks: 5384/565
BNDM_32 performance: 352KB/clock
StrnglenTRAVERSED: 204186782 bytes
Searching for Pattern('easy',4bytes) into String(206908949bytes) line-by-line ...
strstr_Microsoft_hits/strstr_Microsoft_clocks: 4825/773
strstr_Microsoft performance: 257KB/clock
StrnglenTRAVERSED: 204202166 bytes
strstr_GNU_C_Library_hits/strstr_GNU_C_Library_clocks: 4825/617
strstr_GNU_C_Library performance: 323KB/clock
StrnglenTRAVERSED: 204202166 bytes
Railgun_Doublet_hits/Railgun_Doublet_clocks: 4825/441
Railgun_Doublet performance: 452KB/clock
StrnglenTRAVERSED: 204202166 bytes
Railgun_Quadruplet_8Triplet_hits/Railgun_Quadruplet_8Triplet_clocks: 4825/619
Railgun_Quadruplet_8Triplet performance: 322KB/clock
StrnglenTRAVERSED: 204202166 bytes
Railgun_Mischa_8Triplet_hits/Railgun_Mischa_8Triplet_clocks: 4825/483
Railgun_Mischa_8Triplet performance: 412KB/clock
StrnglenTRAVERSED: 204202166 bytes
BNDM_32_hits/BNDM_32_clocks: 4825/580
BNDM_32 performance: 343KB/clock
StrnglenTRAVERSED: 204202166 bytes
Searching for Pattern('grmbl',5bytes) into String(206908949bytes) line-by-line ...
strstr_Microsoft_hits/strstr_Microsoft_clocks: 0/635
strstr_Microsoft performance: 314KB/clock
StrnglenTRAVERSED: 204449441 bytes
strstr_GNU_C_Library_hits/strstr_GNU_C_Library_clocks: 0/481
strstr_GNU_C_Library performance: 415KB/clock
StrnglenTRAVERSED: 204449441 bytes
Railgun_Doublet_hits/Railgun_Doublet_clocks: 0/429
Railgun_Doublet performance: 465KB/clock
StrnglenTRAVERSED: 204449441 bytes
Railgun_Quadruplet_8Triplet_hits/Railgun_Quadruplet_8Triplet_clocks: 0/554
Railgun_Quadruplet_8Triplet performance: 360KB/clock
StrnglenTRAVERSED: 204449441 bytes
Railgun_Mischa_8Triplet_hits/Railgun_Mischa_8Triplet_clocks: 0/484
Railgun_Mischa_8Triplet performance: 412KB/clock
StrnglenTRAVERSED: 204449441 bytes
BNDM_32_hits/BNDM_32_clocks: 0/496
BNDM_32 performance: 402KB/clock
StrnglenTRAVERSED: 204449441 bytes
Searching for Pattern('email',5bytes) into String(206908949bytes) line-by-line ...
strstr_Microsoft_hits/strstr_Microsoft_clocks: 1/767
strstr_Microsoft performance: 260KB/clock
StrnglenTRAVERSED: 204449414 bytes
strstr_GNU_C_Library_hits/strstr_GNU_C_Library_clocks: 1/611
strstr_GNU_C_Library performance: 326KB/clock
StrnglenTRAVERSED: 204449414 bytes
Railgun_Doublet_hits/Railgun_Doublet_clocks: 1/431
Railgun_Doublet performance: 463KB/clock
StrnglenTRAVERSED: 204449414 bytes
Railgun_Quadruplet_8Triplet_hits/Railgun_Quadruplet_8Triplet_clocks: 1/616
Railgun_Quadruplet_8Triplet performance: 324KB/clock
StrnglenTRAVERSED: 204449414 bytes
Railgun_Mischa_8Triplet_hits/Railgun_Mischa_8Triplet_clocks: 1/484
Railgun_Mischa_8Triplet performance: 412KB/clock
StrnglenTRAVERSED: 204449414 bytes
BNDM_32_hits/BNDM_32_clocks: 1/556
BNDM_32 performance: 359KB/clock
StrnglenTRAVERSED: 204449414 bytes
Searching for Pattern('pasting',7bytes) into String(206908949bytes) line-by-line ...
strstr_Microsoft_hits/strstr_Microsoft_clocks: 2/634
strstr_Microsoft performance: 314KB/clock
StrnglenTRAVERSED: 204449363 bytes
strstr_GNU_C_Library_hits/strstr_GNU_C_Library_clocks: 2/480
strstr_GNU_C_Library performance: 415KB/clock
StrnglenTRAVERSED: 204449363 bytes
Railgun_Doublet_hits/Railgun_Doublet_clocks: 2/425
Railgun_Doublet performance: 469KB/clock
StrnglenTRAVERSED: 204449363 bytes
Railgun_Quadruplet_8Triplet_hits/Railgun_Quadruplet_8Triplet_clocks: 2/547
Railgun_Quadruplet_8Triplet performance: 365KB/clock
StrnglenTRAVERSED: 204449363 bytes
Railgun_Mischa_8Triplet_hits/Railgun_Mischa_8Triplet_clocks: 2/484
Railgun_Mischa_8Triplet performance: 412KB/clock
StrnglenTRAVERSED: 204449363 bytes
BNDM_32_hits/BNDM_32_clocks: 2/544
BNDM_32 performance: 367KB/clock
StrnglenTRAVERSED: 204449363 bytes
Searching for Pattern('amazing',7bytes) into String(206908949bytes) line-by-line ...
strstr_Microsoft_hits/strstr_Microsoft_clocks: 319/706
strstr_Microsoft performance: 282KB/clock
StrnglenTRAVERSED: 204432134 bytes
strstr_GNU_C_Library_hits/strstr_GNU_C_Library_clocks: 319/543
strstr_GNU_C_Library performance: 367KB/clock
StrnglenTRAVERSED: 204432134 bytes
Railgun_Doublet_hits/Railgun_Doublet_clocks: 319/426
Railgun_Doublet performance: 468KB/clock
StrnglenTRAVERSED: 204432134 bytes
Railgun_Quadruplet_8Triplet_hits/Railgun_Quadruplet_8Triplet_clocks: 319/577
Railgun_Quadruplet_8Triplet performance: 345KB/clock
StrnglenTRAVERSED: 204432134 bytes
Railgun_Mischa_8Triplet_hits/Railgun_Mischa_8Triplet_clocks: 319/483
Railgun_Mischa_8Triplet performance: 413KB/clock
StrnglenTRAVERSED: 204432134 bytes
BNDM_32_hits/BNDM_32_clocks: 319/509
BNDM_32 performance: 392KB/clock
StrnglenTRAVERSED: 204432134 bytes
Searching for Pattern('underdog',8bytes) into String(206908949bytes) line-by-line ...
strstr_Microsoft_hits/strstr_Microsoft_clocks: 4/656
strstr_Microsoft performance: 304KB/clock
StrnglenTRAVERSED: 204449185 bytes
strstr_GNU_C_Library_hits/strstr_GNU_C_Library_clocks: 4/492
strstr_GNU_C_Library performance: 405KB/clock
StrnglenTRAVERSED: 204449185 bytes
Railgun_Doublet_hits/Railgun_Doublet_clocks: 4/430
Railgun_Doublet performance: 464KB/clock
StrnglenTRAVERSED: 204449185 bytes
Railgun_Quadruplet_8Triplet_hits/Railgun_Quadruplet_8Triplet_clocks: 4/553
Railgun_Quadruplet_8Triplet performance: 361KB/clock
StrnglenTRAVERSED: 204449185 bytes
Railgun_Mischa_8Triplet_hits/Railgun_Mischa_8Triplet_clocks: 4/484
Railgun_Mischa_8Triplet performance: 412KB/clock
StrnglenTRAVERSED: 204449185 bytes
BNDM_32_hits/BNDM_32_clocks: 4/521
BNDM_32 performance: 383KB/clock
StrnglenTRAVERSED: 204449185 bytes
Searching for Pattern('superdog',8bytes) into String(206908949bytes) line-by-line ...
strstr_Microsoft_hits/strstr_Microsoft_clocks: 0/691
strstr_Microsoft performance: 288KB/clock
StrnglenTRAVERSED: 204449441 bytes
strstr_GNU_C_Library_hits/strstr_GNU_C_Library_clocks: 0/528
strstr_GNU_C_Library performance: 378KB/clock
StrnglenTRAVERSED: 204449441 bytes
Railgun_Doublet_hits/Railgun_Doublet_clocks: 0/424
Railgun_Doublet performance: 470KB/clock
StrnglenTRAVERSED: 204449441 bytes
Railgun_Quadruplet_8Triplet_hits/Railgun_Quadruplet_8Triplet_clocks: 0/571
Railgun_Quadruplet_8Triplet performance: 349KB/clock
StrnglenTRAVERSED: 204449441 bytes
Railgun_Mischa_8Triplet_hits/Railgun_Mischa_8Triplet_clocks: 0/484
Railgun_Mischa_8Triplet performance: 412KB/clock
StrnglenTRAVERSED: 204449441 bytes
BNDM_32_hits/BNDM_32_clocks: 0/519
BNDM_32 performance: 384KB/clock
StrnglenTRAVERSED: 204449441 bytes
Searching for Pattern('participants',12bytes) into String(206908949bytes) line-by-line ...
strstr_Microsoft_hits/strstr_Microsoft_clocks: 141/632
strstr_Microsoft performance: 315KB/clock
StrnglenTRAVERSED: 204441500 bytes
strstr_GNU_C_Library_hits/strstr_GNU_C_Library_clocks: 141/480
strstr_GNU_C_Library performance: 415KB/clock
StrnglenTRAVERSED: 204441500 bytes
Railgun_Doublet_hits/Railgun_Doublet_clocks: 141/418
Railgun_Doublet performance: 477KB/clock
StrnglenTRAVERSED: 204441500 bytes
Railgun_Quadruplet_8Triplet_hits/Railgun_Quadruplet_8Triplet_clocks: 141/532
Railgun_Quadruplet_8Triplet performance: 375KB/clock
StrnglenTRAVERSED: 204441500 bytes
Railgun_Mischa_8Triplet_hits/Railgun_Mischa_8Triplet_clocks: 141/483
Railgun_Mischa_8Triplet performance: 413KB/clock
StrnglenTRAVERSED: 204441500 bytes
BNDM_32_hits/BNDM_32_clocks: 141/501
BNDM_32 performance: 398KB/clock
StrnglenTRAVERSED: 204441500 bytes
Searching for Pattern('skillessness',12bytes) into String(206908949bytes) line-by-line ...
strstr_Microsoft_hits/strstr_Microsoft_clocks: 0/689
strstr_Microsoft performance: 289KB/clock
StrnglenTRAVERSED: 204449441 bytes
strstr_GNU_C_Library_hits/strstr_GNU_C_Library_clocks: 0/527
strstr_GNU_C_Library performance: 378KB/clock
StrnglenTRAVERSED: 204449441 bytes
Railgun_Doublet_hits/Railgun_Doublet_clocks: 0/416
Railgun_Doublet performance: 479KB/clock
StrnglenTRAVERSED: 204449441 bytes
Railgun_Quadruplet_8Triplet_hits/Railgun_Quadruplet_8Triplet_clocks: 0/556
Railgun_Quadruplet_8Triplet performance: 359KB/clock
StrnglenTRAVERSED: 204449441 bytes
Railgun_Mischa_8Triplet_hits/Railgun_Mischa_8Triplet_clocks: 0/482
Railgun_Mischa_8Triplet performance: 414KB/clock
StrnglenTRAVERSED: 204449441 bytes
BNDM_32_hits/BNDM_32_clocks: 0/490
BNDM_32 performance: 407KB/clock
StrnglenTRAVERSED: 204449441 bytes
Searching for Pattern('I should have known',19bytes) into String(206908949bytes) line-by-line ...
strstr_Microsoft_hits/strstr_Microsoft_clocks: 1/623
strstr_Microsoft performance: 320KB/clock
StrnglenTRAVERSED: 204449346 bytes
strstr_GNU_C_Library_hits/strstr_GNU_C_Library_clocks: 1/477
strstr_GNU_C_Library performance: 418KB/clock
StrnglenTRAVERSED: 204449346 bytes
Railgun_Doublet_hits/Railgun_Doublet_clocks: 1/407
Railgun_Doublet performance: 490KB/clock
StrnglenTRAVERSED: 204449346 bytes
Railgun_Quadruplet_8Triplet_hits/Railgun_Quadruplet_8Triplet_clocks: 1/505
Railgun_Quadruplet_8Triplet performance: 395KB/clock
StrnglenTRAVERSED: 204449346 bytes
Railgun_Mischa_8Triplet_hits/Railgun_Mischa_8Triplet_clocks: 1/483
Railgun_Mischa_8Triplet performance: 413KB/clock
StrnglenTRAVERSED: 204449346 bytes
BNDM_32_hits/BNDM_32_clocks: 1/498
BNDM_32 performance: 400KB/clock
StrnglenTRAVERSED: 204449346 bytes
Searching for Pattern('human consciousness',19bytes) into String(206908949bytes) line-by-line ...
strstr_Microsoft_hits/strstr_Microsoft_clocks: 514/679
strstr_Microsoft performance: 294KB/clock
StrnglenTRAVERSED: 204422699 bytes
strstr_GNU_C_Library_hits/strstr_GNU_C_Library_clocks: 514/514
strstr_GNU_C_Library performance: 388KB/clock
StrnglenTRAVERSED: 204422699 bytes
Railgun_Doublet_hits/Railgun_Doublet_clocks: 514/404
Railgun_Doublet performance: 494KB/clock
StrnglenTRAVERSED: 204422699 bytes
Railgun_Quadruplet_8Triplet_hits/Railgun_Quadruplet_8Triplet_clocks: 514/526
Railgun_Quadruplet_8Triplet performance: 379KB/clock
StrnglenTRAVERSED: 204422699 bytes
Railgun_Mischa_8Triplet_hits/Railgun_Mischa_8Triplet_clocks: 514/482
Railgun_Mischa_8Triplet performance: 414KB/clock
StrnglenTRAVERSED: 204422699 bytes
BNDM_32_hits/BNDM_32_clocks: 514/492
BNDM_32 performance: 405KB/clock
StrnglenTRAVERSED: 204422699 bytes
D:\_KAZE_strstr_SHORT-SHOWDOWN_7Trident2_7Hasherezade_7Gulliver2>
*/
//
/*
; Listing generated by: Microsoft (R) 32-bit C/C++ Optimizing Compiler Version 16.00.30319.01 for 80x86
PUBLIC _Railgun_Doublet
; Function compile flags: /Ogtpy
_TEXT SEGMENT
_ulHashPattern$ = 8 ; size = 4
_pbTarget$ = 8 ; size = 4
_pbPattern$ = 12 ; size = 4
_pbTargetMax$ = 16 ; size = 4
_cbTarget$ = 16 ; size = 4
_cbPattern$ = 20 ; size = 4
_Railgun_Doublet PROC
; 2640 : char * pbTargetMax = pbTarget + cbTarget;
009d0 8b 44 24 0c mov eax, DWORD PTR _cbTarget$[esp-4]
009d4 53 push ebx
; 2641 : register uint32_t ulHashPattern;
; 2642 : uint32_t ulHashTarget, count, countSTATIC;
; 2643 :
; 2644 : if (cbPattern > cbTarget) return(NULL);
009d5 8b 5c 24 14 mov ebx, DWORD PTR _cbPattern$[esp]
009d9 55 push ebp
009da 8b 6c 24 0c mov ebp, DWORD PTR _pbTarget$[esp+4]
009de 8d 0c 28 lea ecx, DWORD PTR [eax+ebp]
009e1 89 4c 24 14 mov DWORD PTR _pbTargetMax$[esp+4], ecx
009e5 3b d8 cmp ebx, eax
009e7 76 05 jbe SHORT $LN8@Railgun_du
009e9 5d pop ebp
009ea 33 c0 xor eax, eax
009ec 5b pop ebx
; 2661 : }
; 2662 : }
009ed c3 ret 0
$LN8@Railgun_du:
; 2645 :
; 2646 : countSTATIC = cbPattern-2;
; 2647 :
; 2648 : pbTarget = pbTarget+cbPattern;
; 2649 : ulHashPattern = (*(uint16_t *)(pbPattern));
009ee 8b 54 24 10 mov edx, DWORD PTR _pbPattern$[esp+4]
009f2 0f b7 02 movzx eax, WORD PTR [edx]
009f5 57 push edi
009f6 03 eb add ebp, ebx
009f8 8b fd mov edi, ebp
009fa 89 44 24 10 mov DWORD PTR _ulHashPattern$[esp+8], eax
009fe 2b fb sub edi, ebx
00a00 56 push esi
$LL7@Railgun_du:
; 2650 :
; 2651 : for ( ;; ) {
; 2652 : if ( ulHashPattern == (*(uint16_t *)(pbTarget-cbPattern)) ) {
00a01 0f b7 0f movzx ecx, WORD PTR [edi]
00a04 39 4c 24 14 cmp DWORD PTR _ulHashPattern$[esp+12], ecx
00a08 75 2e jne SHORT $LN2@Railgun_du
; 2653 : count = countSTATIC;
00a0a 8d 4b fe lea ecx, DWORD PTR [ebx-2]
; 2654 : while ( count && *(char *)(pbPattern+2+(countSTATIC-count)) == *(char *)(pbTarget-cbPattern+2+(countSTATIC-count)) ) {
00a0d 85 c9 test ecx, ecx
00a0f 74 1a je SHORT $LN17@Railgun_du
; 2653 : count = countSTATIC;
00a11 8b 74 24 18 mov esi, DWORD PTR _pbPattern$[esp+12]
00a15 83 c6 02 add esi, 2
00a18 8d 57 02 lea edx, DWORD PTR [edi+2]
00a1b eb 03 8d 49 00 npad 5
$LL4@Railgun_du:
; 2654 : while ( count && *(char *)(pbPattern+2+(countSTATIC-count)) == *(char *)(pbTarget-cbPattern+2+(countSTATIC-count)) ) {
00a20 8a 06 mov al, BYTE PTR [esi]
00a22 3a 02 cmp al, BYTE PTR [edx]
00a24 75 0e jne SHORT $LN3@Railgun_du
; 2655 : count--;
00a26 42 inc edx
00a27 46 inc esi
00a28 49 dec ecx
00a29 75 f5 jne SHORT $LL4@Railgun_du
$LN17@Railgun_du:
00a2b 5e pop esi
00a2c 5f pop edi
; 2656 : }
; 2657 : if ( count == 0 ) return((pbTarget-cbPattern));
00a2d 8b c5 mov eax, ebp
00a2f 5d pop ebp
00a30 2b c3 sub eax, ebx
00a32 5b pop ebx
; 2661 : }
; 2662 : }
00a33 c3 ret 0
$LN3@Railgun_du:
; 2656 : }
; 2657 : if ( count == 0 ) return((pbTarget-cbPattern));
00a34 85 c9 test ecx, ecx
00a36 74 f3 je SHORT $LN17@Railgun_du
$LN2@Railgun_du:
; 2658 : }
; 2659 : pbTarget++;
00a38 45 inc ebp
00a39 47 inc edi
; 2660 : if (pbTarget > pbTargetMax) return(NULL);
00a3a 3b 6c 24 1c cmp ebp, DWORD PTR _pbTargetMax$[esp+12]
00a3e 76 c1 jbe SHORT $LL7@Railgun_du
00a40 5e pop esi
00a41 5f pop edi
00a42 5d pop ebp
00a43 33 c0 xor eax, eax
00a45 5b pop ebx
; 2661 : }
; 2662 : }
00a46 c3 ret 0
_Railgun_Doublet ENDP
_TEXT ENDS
*/
//
/*
Testbed: [File: OSHO.TXT 206,908,949 bytes; LinesEncountered: 2,459,508; Windows XP 32bit; Microsoft 2010 32bit compiler; T7500 2200MHz dual DDR2]
Searching for Pattern('an',2bytes) into String(206908949bytes) line-by-line ...
strstr_Microsoft_hits/strstr_Microsoft_clocks: 1212509/684
strstr_Microsoft performance: 197KB/clock
StrnglenTRAVERSED: 138478024 bytes
strstr_GNU_C_Library_hits/strstr_GNU_C_Library_clocks: 1212509/492
strstr_GNU_C_Library performance: 274KB/clock
StrnglenTRAVERSED: 138478024 bytes
Railgun_Doublet_hits/Railgun_Doublet_clocks: 1212509/493
Railgun_Doublet performance: 274KB/clock
StrnglenTRAVERSED: 138478024 bytes
Railgun_Quadruplet_8Triplet_hits/Railgun_Quadruplet_8Triplet_clocks: 1212509/442
Railgun_Quadruplet_8Triplet performance: 305KB/clock
StrnglenTRAVERSED: 138478024 bytes
Railgun_Mischa_8Triplet_hits/Railgun_Mischa_8Triplet_clocks: 1212509/435
Railgun_Mischa_8Triplet performance: 310KB/clock
StrnglenTRAVERSED: 138478024 bytes
BNDM_32_hits/BNDM_32_clocks: 1212509/625
BNDM_32 performance: 216KB/clock
StrnglenTRAVERSED: 138478024 bytes
Searching for Pattern('to',2bytes) into String(206908949bytes) line-by-line ...
strstr_Microsoft_hits/strstr_Microsoft_clocks: 780175/765
strstr_Microsoft performance: 209KB/clock
StrnglenTRAVERSED: 164505415 bytes
strstr_GNU_C_Library_hits/strstr_GNU_C_Library_clocks: 780175/544
strstr_GNU_C_Library performance: 295KB/clock
StrnglenTRAVERSED: 164505415 bytes
Railgun_Doublet_hits/Railgun_Doublet_clocks: 780175/526
Railgun_Doublet performance: 305KB/clock
StrnglenTRAVERSED: 164505415 bytes
Railgun_Quadruplet_8Triplet_hits/Railgun_Quadruplet_8Triplet_clocks: 780175/482
Railgun_Quadruplet_8Triplet performance: 333KB/clock
StrnglenTRAVERSED: 164505415 bytes
Railgun_Mischa_8Triplet_hits/Railgun_Mischa_8Triplet_clocks: 780175/471
Railgun_Mischa_8Triplet performance: 341KB/clock
StrnglenTRAVERSED: 164505415 bytes
BNDM_32_hits/BNDM_32_clocks: 780175/688
BNDM_32 performance: 233KB/clock
StrnglenTRAVERSED: 164505415 bytes
Searching for Pattern('TDK',3bytes) into String(206908949bytes) line-by-line ...
strstr_Microsoft_hits/strstr_Microsoft_clocks: 0/744
strstr_Microsoft performance: 268KB/clock
StrnglenTRAVERSED: 204449441 bytes
strstr_GNU_C_Library_hits/strstr_GNU_C_Library_clocks: 0/490
strstr_GNU_C_Library performance: 407KB/clock
StrnglenTRAVERSED: 204449441 bytes
Railgun_Doublet_hits/Railgun_Doublet_clocks: 0/575
Railgun_Doublet performance: 347KB/clock
StrnglenTRAVERSED: 204449441 bytes
Railgun_Quadruplet_8Triplet_hits/Railgun_Quadruplet_8Triplet_clocks: 0/453
Railgun_Quadruplet_8Triplet performance: 440KB/clock
StrnglenTRAVERSED: 204449441 bytes
Railgun_Mischa_8Triplet_hits/Railgun_Mischa_8Triplet_clocks: 0/445
Railgun_Mischa_8Triplet performance: 448KB/clock
StrnglenTRAVERSED: 204449441 bytes
BNDM_32_hits/BNDM_32_clocks: 0/537
BNDM_32 performance: 371KB/clock
StrnglenTRAVERSED: 204449441 bytes
Searching for Pattern('the',3bytes) into String(206908949bytes) line-by-line ...
strstr_Microsoft_hits/strstr_Microsoft_clocks: 1192002/704
strstr_Microsoft performance: 188KB/clock
StrnglenTRAVERSED: 135882884 bytes
strstr_GNU_C_Library_hits/strstr_GNU_C_Library_clocks: 1192002/519
strstr_GNU_C_Library performance: 255KB/clock
StrnglenTRAVERSED: 135882884 bytes
Railgun_Doublet_hits/Railgun_Doublet_clocks: 1192002/545
Railgun_Doublet performance: 243KB/clock
StrnglenTRAVERSED: 135882884 bytes
Railgun_Quadruplet_8Triplet_hits/Railgun_Quadruplet_8Triplet_clocks: 1192002/467
Railgun_Quadruplet_8Triplet performance: 284KB/clock
StrnglenTRAVERSED: 135882884 bytes
Railgun_Mischa_8Triplet_hits/Railgun_Mischa_8Triplet_clocks: 1192002/457
Railgun_Mischa_8Triplet performance: 290KB/clock
StrnglenTRAVERSED: 135882884 bytes
BNDM_32_hits/BNDM_32_clocks: 1192002/645
BNDM_32 performance: 205KB/clock
StrnglenTRAVERSED: 135882884 bytes
Searching for Pattern('fast',4bytes) into String(206908949bytes) line-by-line ...
strstr_Microsoft_hits/strstr_Microsoft_clocks: 5384/763
strstr_Microsoft performance: 261KB/clock
StrnglenTRAVERSED: 204186782 bytes
strstr_GNU_C_Library_hits/strstr_GNU_C_Library_clocks: 5384/507
strstr_GNU_C_Library performance: 393KB/clock
StrnglenTRAVERSED: 204186782 bytes
Railgun_Doublet_hits/Railgun_Doublet_clocks: 5384/574
Railgun_Doublet performance: 347KB/clock
StrnglenTRAVERSED: 204186782 bytes
Railgun_Quadruplet_8Triplet_hits/Railgun_Quadruplet_8Triplet_clocks: 5384/495
Railgun_Quadruplet_8Triplet performance: 402KB/clock
StrnglenTRAVERSED: 204186782 bytes
Railgun_Mischa_8Triplet_hits/Railgun_Mischa_8Triplet_clocks: 5384/580
Railgun_Mischa_8Triplet performance: 343KB/clock
StrnglenTRAVERSED: 204186782 bytes
BNDM_32_hits/BNDM_32_clocks: 5384/635
BNDM_32 performance: 314KB/clock
StrnglenTRAVERSED: 204186782 bytes
Searching for Pattern('easy',4bytes) into String(206908949bytes) line-by-line ...
strstr_Microsoft_hits/strstr_Microsoft_clocks: 4825/961
strstr_Microsoft performance: 207KB/clock
StrnglenTRAVERSED: 204202166 bytes
strstr_GNU_C_Library_hits/strstr_GNU_C_Library_clocks: 4825/673
strstr_GNU_C_Library performance: 296KB/clock
StrnglenTRAVERSED: 204202166 bytes
Railgun_Doublet_hits/Railgun_Doublet_clocks: 4825/586
Railgun_Doublet performance: 340KB/clock
StrnglenTRAVERSED: 204202166 bytes
Railgun_Quadruplet_8Triplet_hits/Railgun_Quadruplet_8Triplet_clocks: 4825/654
Railgun_Quadruplet_8Triplet performance: 304KB/clock
StrnglenTRAVERSED: 204202166 bytes
Railgun_Mischa_8Triplet_hits/Railgun_Mischa_8Triplet_clocks: 4825/580
Railgun_Mischa_8Triplet performance: 343KB/clock
StrnglenTRAVERSED: 204202166 bytes
BNDM_32_hits/BNDM_32_clocks: 4825/655
BNDM_32 performance: 304KB/clock
StrnglenTRAVERSED: 204202166 bytes
Searching for Pattern('grmbl',5bytes) into String(206908949bytes) line-by-line ...
strstr_Microsoft_hits/strstr_Microsoft_clocks: 0/769
strstr_Microsoft performance: 259KB/clock
StrnglenTRAVERSED: 204449441 bytes
strstr_GNU_C_Library_hits/strstr_GNU_C_Library_clocks: 0/512
strstr_GNU_C_Library performance: 389KB/clock
StrnglenTRAVERSED: 204449441 bytes
Railgun_Doublet_hits/Railgun_Doublet_clocks: 0/571
Railgun_Doublet performance: 349KB/clock
StrnglenTRAVERSED: 204449441 bytes
Railgun_Quadruplet_8Triplet_hits/Railgun_Quadruplet_8Triplet_clocks: 0/497
Railgun_Quadruplet_8Triplet performance: 401KB/clock
StrnglenTRAVERSED: 204449441 bytes
Railgun_Mischa_8Triplet_hits/Railgun_Mischa_8Triplet_clocks: 0/580
Railgun_Mischa_8Triplet performance: 344KB/clock
StrnglenTRAVERSED: 204449441 bytes
BNDM_32_hits/BNDM_32_clocks: 0/547
BNDM_32 performance: 365KB/clock
StrnglenTRAVERSED: 204449441 bytes
Searching for Pattern('email',5bytes) into String(206908949bytes) line-by-line ...
strstr_Microsoft_hits/strstr_Microsoft_clocks: 1/953
strstr_Microsoft performance: 209KB/clock
StrnglenTRAVERSED: 204449414 bytes
strstr_GNU_C_Library_hits/strstr_GNU_C_Library_clocks: 1/664
strstr_GNU_C_Library performance: 300KB/clock
StrnglenTRAVERSED: 204449414 bytes
Railgun_Doublet_hits/Railgun_Doublet_clocks: 1/574
Railgun_Doublet performance: 347KB/clock
StrnglenTRAVERSED: 204449414 bytes
Railgun_Quadruplet_8Triplet_hits/Railgun_Quadruplet_8Triplet_clocks: 1/653
Railgun_Quadruplet_8Triplet performance: 305KB/clock
StrnglenTRAVERSED: 204449414 bytes
Railgun_Mischa_8Triplet_hits/Railgun_Mischa_8Triplet_clocks: 1/580
Railgun_Mischa_8Triplet performance: 344KB/clock
StrnglenTRAVERSED: 204449414 bytes
BNDM_32_hits/BNDM_32_clocks: 1/626
BNDM_32 performance: 318KB/clock
StrnglenTRAVERSED: 204449414 bytes
Searching for Pattern('pasting',7bytes) into String(206908949bytes) line-by-line ...
strstr_Microsoft_hits/strstr_Microsoft_clocks: 2/763
strstr_Microsoft performance: 261KB/clock
StrnglenTRAVERSED: 204449363 bytes
strstr_GNU_C_Library_hits/strstr_GNU_C_Library_clocks: 2/506
strstr_GNU_C_Library performance: 394KB/clock
StrnglenTRAVERSED: 204449363 bytes
Railgun_Doublet_hits/Railgun_Doublet_clocks: 2/565
Railgun_Doublet performance: 353KB/clock
StrnglenTRAVERSED: 204449363 bytes
Railgun_Quadruplet_8Triplet_hits/Railgun_Quadruplet_8Triplet_clocks: 2/488
Railgun_Quadruplet_8Triplet performance: 409KB/clock
StrnglenTRAVERSED: 204449363 bytes
Railgun_Mischa_8Triplet_hits/Railgun_Mischa_8Triplet_clocks: 2/581
Railgun_Mischa_8Triplet performance: 343KB/clock
StrnglenTRAVERSED: 204449363 bytes
BNDM_32_hits/BNDM_32_clocks: 2/617
BNDM_32 performance: 323KB/clock
StrnglenTRAVERSED: 204449363 bytes
Searching for Pattern('amazing',7bytes) into String(206908949bytes) line-by-line ...
strstr_Microsoft_hits/strstr_Microsoft_clocks: 319/871
strstr_Microsoft performance: 229KB/clock
StrnglenTRAVERSED: 204432134 bytes
strstr_GNU_C_Library_hits/strstr_GNU_C_Library_clocks: 319/592
strstr_GNU_C_Library performance: 337KB/clock
StrnglenTRAVERSED: 204432134 bytes
Railgun_Doublet_hits/Railgun_Doublet_clocks: 319/565
Railgun_Doublet performance: 353KB/clock
StrnglenTRAVERSED: 204432134 bytes
Railgun_Quadruplet_8Triplet_hits/Railgun_Quadruplet_8Triplet_clocks: 319/569
Railgun_Quadruplet_8Triplet performance: 350KB/clock
StrnglenTRAVERSED: 204432134 bytes
Railgun_Mischa_8Triplet_hits/Railgun_Mischa_8Triplet_clocks: 319/580
Railgun_Mischa_8Triplet performance: 344KB/clock
StrnglenTRAVERSED: 204432134 bytes
BNDM_32_hits/BNDM_32_clocks: 319/569
BNDM_32 performance: 350KB/clock
StrnglenTRAVERSED: 204432134 bytes
Searching for Pattern('underdog',8bytes) into String(206908949bytes) line-by-line ...
strstr_Microsoft_hits/strstr_Microsoft_clocks: 4/799
strstr_Microsoft performance: 249KB/clock
StrnglenTRAVERSED: 204449185 bytes
strstr_GNU_C_Library_hits/strstr_GNU_C_Library_clocks: 4/533
strstr_GNU_C_Library performance: 374KB/clock
StrnglenTRAVERSED: 204449185 bytes
Railgun_Doublet_hits/Railgun_Doublet_clocks: 4/568
Railgun_Doublet performance: 351KB/clock
StrnglenTRAVERSED: 204449185 bytes
Railgun_Quadruplet_8Triplet_hits/Railgun_Quadruplet_8Triplet_clocks: 4/510
Railgun_Quadruplet_8Triplet performance: 391KB/clock
StrnglenTRAVERSED: 204449185 bytes
Railgun_Mischa_8Triplet_hits/Railgun_Mischa_8Triplet_clocks: 4/581
Railgun_Mischa_8Triplet performance: 343KB/clock
StrnglenTRAVERSED: 204449185 bytes
BNDM_32_hits/BNDM_32_clocks: 4/587
BNDM_32 performance: 340KB/clock
StrnglenTRAVERSED: 204449185 bytes
Searching for Pattern('superdog',8bytes) into String(206908949bytes) line-by-line ...
strstr_Microsoft_hits/strstr_Microsoft_clocks: 0/848
strstr_Microsoft performance: 235KB/clock
StrnglenTRAVERSED: 204449441 bytes
strstr_GNU_C_Library_hits/strstr_GNU_C_Library_clocks: 0/578
strstr_GNU_C_Library performance: 345KB/clock
StrnglenTRAVERSED: 204449441 bytes
Railgun_Doublet_hits/Railgun_Doublet_clocks: 0/562
Railgun_Doublet performance: 355KB/clock
StrnglenTRAVERSED: 204449441 bytes
Railgun_Quadruplet_8Triplet_hits/Railgun_Quadruplet_8Triplet_clocks: 0/556
Railgun_Quadruplet_8Triplet performance: 359KB/clock
StrnglenTRAVERSED: 204449441 bytes
Railgun_Mischa_8Triplet_hits/Railgun_Mischa_8Triplet_clocks: 0/580
Railgun_Mischa_8Triplet performance: 344KB/clock
StrnglenTRAVERSED: 204449441 bytes
BNDM_32_hits/BNDM_32_clocks: 0/585
BNDM_32 performance: 341KB/clock
StrnglenTRAVERSED: 204449441 bytes
Searching for Pattern('participants',12bytes) into String(206908949bytes) line-by-line ...
strstr_Microsoft_hits/strstr_Microsoft_clocks: 141/763
strstr_Microsoft performance: 261KB/clock
StrnglenTRAVERSED: 204441500 bytes
strstr_GNU_C_Library_hits/strstr_GNU_C_Library_clocks: 141/507
strstr_GNU_C_Library performance: 393KB/clock
StrnglenTRAVERSED: 204441500 bytes
Railgun_Doublet_hits/Railgun_Doublet_clocks: 141/549
Railgun_Doublet performance: 363KB/clock
StrnglenTRAVERSED: 204441500 bytes
Railgun_Quadruplet_8Triplet_hits/Railgun_Quadruplet_8Triplet_clocks: 141/478
Railgun_Quadruplet_8Triplet performance: 417KB/clock
StrnglenTRAVERSED: 204441500 bytes
Railgun_Mischa_8Triplet_hits/Railgun_Mischa_8Triplet_clocks: 141/580
Railgun_Mischa_8Triplet performance: 344KB/clock
StrnglenTRAVERSED: 204441500 bytes
BNDM_32_hits/BNDM_32_clocks: 141/560
BNDM_32 performance: 356KB/clock
StrnglenTRAVERSED: 204441500 bytes
Searching for Pattern('skillessness',12bytes) into String(206908949bytes) line-by-line ...
strstr_Microsoft_hits/strstr_Microsoft_clocks: 0/846
strstr_Microsoft performance: 236KB/clock
StrnglenTRAVERSED: 204449441 bytes
strstr_GNU_C_Library_hits/strstr_GNU_C_Library_clocks: 0/576
strstr_GNU_C_Library performance: 346KB/clock
StrnglenTRAVERSED: 204449441 bytes
Railgun_Doublet_hits/Railgun_Doublet_clocks: 0/547
Railgun_Doublet performance: 365KB/clock
StrnglenTRAVERSED: 204449441 bytes
Railgun_Quadruplet_8Triplet_hits/Railgun_Quadruplet_8Triplet_clocks: 0/543
Railgun_Quadruplet_8Triplet performance: 367KB/clock
StrnglenTRAVERSED: 204449441 bytes
Railgun_Mischa_8Triplet_hits/Railgun_Mischa_8Triplet_clocks: 0/580
Railgun_Mischa_8Triplet performance: 344KB/clock
StrnglenTRAVERSED: 204449441 bytes
BNDM_32_hits/BNDM_32_clocks: 0/546
BNDM_32 performance: 365KB/clock
StrnglenTRAVERSED: 204449441 bytes
Searching for Pattern('I should have known',19bytes) into String(206908949bytes) line-by-line ...
strstr_Microsoft_hits/strstr_Microsoft_clocks: 1/751
strstr_Microsoft performance: 265KB/clock
StrnglenTRAVERSED: 204449346 bytes
strstr_GNU_C_Library_hits/strstr_GNU_C_Library_clocks: 1/495
strstr_GNU_C_Library performance: 403KB/clock
StrnglenTRAVERSED: 204449346 bytes
Railgun_Doublet_hits/Railgun_Doublet_clocks: 1/528
Railgun_Doublet performance: 378KB/clock
StrnglenTRAVERSED: 204449346 bytes
Railgun_Quadruplet_8Triplet_hits/Railgun_Quadruplet_8Triplet_clocks: 1/450
Railgun_Quadruplet_8Triplet performance: 443KB/clock
StrnglenTRAVERSED: 204449346 bytes
Railgun_Mischa_8Triplet_hits/Railgun_Mischa_8Triplet_clocks: 1/580
Railgun_Mischa_8Triplet performance: 344KB/clock
StrnglenTRAVERSED: 204449346 bytes
BNDM_32_hits/BNDM_32_clocks: 1/553
BNDM_32 performance: 361KB/clock
StrnglenTRAVERSED: 204449346 bytes
Searching for Pattern('human consciousness',19bytes) into String(206908949bytes) line-by-line ...
strstr_Microsoft_hits/strstr_Microsoft_clocks: 514/834
strstr_Microsoft performance: 239KB/clock
StrnglenTRAVERSED: 204422699 bytes
strstr_GNU_C_Library_hits/strstr_GNU_C_Library_clocks: 514/563
strstr_GNU_C_Library performance: 354KB/clock
StrnglenTRAVERSED: 204422699 bytes
Railgun_Doublet_hits/Railgun_Doublet_clocks: 514/525
Railgun_Doublet performance: 380KB/clock
StrnglenTRAVERSED: 204422699 bytes
Railgun_Quadruplet_8Triplet_hits/Railgun_Quadruplet_8Triplet_clocks: 514/509
Railgun_Quadruplet_8Triplet performance: 392KB/clock
StrnglenTRAVERSED: 204422699 bytes
Railgun_Mischa_8Triplet_hits/Railgun_Mischa_8Triplet_clocks: 514/580
Railgun_Mischa_8Triplet performance: 344KB/clock
StrnglenTRAVERSED: 204422699 bytes
BNDM_32_hits/BNDM_32_clocks: 514/546
BNDM_32 performance: 365KB/clock
StrnglenTRAVERSED: 204422699 bytes
D:\_KAZE_strstr_SHORT-SHOWDOWN_7Trident2_7Hasherezade_7Gulliver2>
*/
//
// Notes on 80x86 and x64, 2012-Feb-25:
// Three compilers were used (first two on Windows 7 64bit, the third on Windows XP 32bit):
// Intel(R) C++ 64 Compiler XE for applications running on Intel(R) 64, Version 12.1.1.258 Build 20111011
// Microsoft (R) C/C++ Optimizing Compiler Version 16.00.30319.01 for x64
// Microsoft (R) 32-bit C/C++ Optimizing Compiler Version 16.00.30319.01 for 80x86
// I have been using x64 for more than 12 hours and quickly the picture has become clear: code written for 32bit must be replaced with dedicated 64bit counterpart, relying on former only is a gambling venture.
// For example Railgun_Doublet dominates when compiled as 64bit (both with Intel XE 2011 12.1 and Microsoft 2010 16.00.30319.01 for x64), but for 32bit it is inferior compared to Railgun_Quadruplet_8Triplet.
// Summary for strstr-like (i.e. memmem for short strings/patterns) usage:
// - for 32bit use Railgun_Quadruplet_8Triplet
// - for 64bit use Railgun_Doublet
// My interest has been shifted from strstr toward memmem, Railgun_Doublet will fill the gap (short strings/patterns cases) in Railgun_r8_Mimino_x64 whereas 'Trident2'+'Hasherezade' will deal with memmem part, 'Hasherezade' should be surely tuned for 64bit.
/*
A self-explanatory smackdown:
File: strstr_SHORT-SHOWDOWN_Microsoft_v16_Ox_64bit.exe
Testbed: Windows 7 64bit; Microsoft 2010 64bit compiler; E7500 2.93GHz dual DDR2
Target(as-one-line): OSHO.TXT 206908949 bytes
Pattern: fastest fox
Railgun_Quadruplet_7sun: 2000KB/clock / 0775%, 26672940 iterations
Railgun_Quadruplet_7Trident: 2149KB/clock / 0993%, 20834332 iterations BNDM screams here along with Horspool&Sunday
BNDM_32: 1507KB/clock / 1038%, 19926393 iterations
Railgun_Quadruplet_7Gulliver: 2104KB/clock / 0977%, 21166516 iterations
Railgun_Quadruplet_7Hasherezade: 1961KB/clock / 0980%, 21112673 iterations
Pattern: fastest fox with biggest strides
Railgun_Quadruplet_7sun: 3061KB/clock / 1584%, 13060463 iterations
Railgun_Quadruplet_7Trident: 3424KB/clock / 3058%, 06765272 iterations
BNDM_32: 3483KB/clock / 3113%, 06644708 iterations
Railgun_Quadruplet_7Gulliver: 3608KB/clock / 2924%, 07074287 iterations
Railgun_Quadruplet_7Hasherezade: 3367KB/clock / 3041%, 06801754 iterations Needs 64bit hand optimization!
File: strstr_SHORT-SHOWDOWN_Intel_O3_64bit.exe
Testbed: Windows 7 64bit; Intel C++ 64 Compiler XE 12.1; E7500 2.93GHz dual DDR2
Target(as-one-line): OSHO.TXT 206908949 bytes
Pattern: fastest fox
Railgun_Quadruplet_7sun: 1942KB/clock / 0775%, 26672940 iterations
Railgun_Quadruplet_7Trident: 2245KB/clock / 0993%, 20834332 iterations BNDM screams here along with Horspool&Sunday
BNDM_32: 1507KB/clock / 1038%, 19926393 iterations
Railgun_Quadruplet_7Gulliver: 1870KB/clock / 0977%, 21166516 iterations
Railgun_Quadruplet_7Hasherezade: 1697KB/clock / 0980%, 21112673 iterations
Pattern: fastest fox with biggest strides
Railgun_Quadruplet_7sun: 3061KB/clock / 1584%, 13060463 iterations
Railgun_Quadruplet_7Trident: 3424KB/clock / 3058%, 06765272 iterations
BNDM_32: 3544KB/clock / 3113%, 06644708 iterations
Railgun_Quadruplet_7Gulliver: 3608KB/clock / 2924%, 07074287 iterations
Railgun_Quadruplet_7Hasherezade: 3207KB/clock / 3041%, 06801754 iterations Needs 64bit hand optimization!
File: strstr_SHORT-SHOWDOWN_Microsoft_Ox_32bit.exe
Testbed: Windows XP 32bit; Microsoft 2010 32bit compiler; T7500 2200MHz dual DDR2
Target(as-one-line): OSHO.TXT 206908949 bytes
Pattern: fastest fox
Railgun_Quadruplet_7sun: 1683KB/clock / 0775%, 26672940 iterations
Railgun_Quadruplet_7Trident: 1888KB/clock / 0993%, 20834332 iterations
BNDM_32: 1135KB/clock / 1038%, 19926393 iterations
Railgun_Quadruplet_7Gulliver: 1942KB/clock / 0977%, 21166516 iterations
Railgun_Quadruplet_7Hasherezade: 1757KB/clock / 0980%, 21112673 iterations
Pattern: fastest fox with biggest strides
Railgun_Quadruplet_7sun: 2658KB/clock / 1584%, 13060463 iterations
Railgun_Quadruplet_7Trident: 3015KB/clock / 3058%, 06765272 iterations
BNDM_32: 2806KB/clock / 3113%, 06644708 iterations
Railgun_Quadruplet_7Gulliver: 3157KB/clock / 2924%, 07074287 iterations
Railgun_Quadruplet_7Hasherezade: 3061KB/clock / 3041%, 06801754 iterations
Bottom-line: Railgun_Quadruplet_7Trident is my choice for patterns up to 16chars (and for 32+KB haystacks, for 32--KB haystacks Railgun_Doublet takes over), it is to be used as backbone (along with Railgun_Quadruplet_7Hasherezade for patterns bigger than 16chars) of Railgun_r8_Mimino_x64.
*/
//
/*
Testbed: [File: OSHO.TXT 206,908,949 bytes; LinesEncountered: 2,459,508; Windows 7 64bit; E7500 2.93GHz dual DDR2]
Microsoft 2010 64bit compiler / Intel C++ 64 Compiler XE 12.1
Searching for Pattern('an',2bytes) into String(206908949bytes) line-by-line ...
strstr_Microsoft performance: 248KB/clock 238KB/clock
strstr_GNU_C_Library performance: 376KB/clock 296KB/clock
Railgun_Doublet performance: 421KB/clock 348KB/clock
BNDM_32 performance: 267KB/clock 241KB/clock
Searching for Pattern('to',2bytes) into String(206908949bytes) line-by-line ...
strstr_Microsoft performance: 260KB/clock 255KB/clock
strstr_GNU_C_Library performance: 400KB/clock 320KB/clock
Railgun_Doublet performance: 476KB/clock 397KB/clock
BNDM_32 performance: 290KB/clock 262KB/clock
Searching for Pattern('TDK',3bytes) into String(206908949bytes) line-by-line ...
strstr_Microsoft performance: 318KB/clock 323KB/clock
strstr_GNU_C_Library performance: 564KB/clock 421KB/clock
Railgun_Doublet performance: 551KB/clock 464KB/clock
BNDM_32 performance: 462KB/clock 409KB/clock
Searching for Pattern('the',3bytes) into String(206908949bytes) line-by-line ...
strstr_Microsoft performance: 233KB/clock 227KB/clock
strstr_GNU_C_Library performance: 346KB/clock 276KB/clock
Railgun_Doublet performance: 393KB/clock 328KB/clock
BNDM_32 performance: 255KB/clock 234KB/clock
Searching for Pattern('fast',4bytes) into String(206908949bytes) line-by-line ...
strstr_Microsoft performance: 311KB/clock 315KB/clock
strstr_GNU_C_Library performance: 540KB/clock 417KB/clock
Railgun_Doublet performance: 550KB/clock 463KB/clock
BNDM_32 performance: 390KB/clock 352KB/clock
Searching for Pattern('easy',4bytes) into String(206908949bytes) line-by-line ...
strstr_Microsoft performance: 258KB/clock 257KB/clock
strstr_GNU_C_Library performance: 395KB/clock 323KB/clock
Railgun_Doublet performance: 534KB/clock 452KB/clock
BNDM_32 performance: 379KB/clock 343KB/clock
Searching for Pattern('grmbl',5bytes) into String(206908949bytes) line-by-line ...
strstr_Microsoft performance: 309KB/clock 314KB/clock
strstr_GNU_C_Library performance: 535KB/clock 415KB/clock
Railgun_Doublet performance: 553KB/clock 465KB/clock
BNDM_32 performance: 451KB/clock 402KB/clock
Searching for Pattern('email',5bytes) into String(206908949bytes) line-by-line ...
strstr_Microsoft performance: 261KB/clock 260KB/clock
strstr_GNU_C_Library performance: 401KB/clock 326KB/clock
Railgun_Doublet performance: 550KB/clock 463KB/clock
BNDM_32 performance: 395KB/clock 359KB/clock
Searching for Pattern('pasting',7bytes) into String(206908949bytes) line-by-line ...
strstr_Microsoft performance: 311KB/clock 314KB/clock
strstr_GNU_C_Library performance: 542KB/clock 415KB/clock
Railgun_Doublet performance: 559KB/clock 469KB/clock
BNDM_32 performance: 400KB/clock 367KB/clock
Searching for Pattern('amazing',7bytes) into String(206908949bytes) line-by-line ...
strstr_Microsoft performance: 281KB/clock 282KB/clock
strstr_GNU_C_Library performance: 455KB/clock 367KB/clock
Railgun_Doublet performance: 557KB/clock 468KB/clock
BNDM_32 performance: 433KB/clock 392KB/clock
Searching for Pattern('underdog',8bytes) into String(206908949bytes) line-by-line ...
strstr_Microsoft performance: 300KB/clock 304KB/clock
strstr_GNU_C_Library performance: 510KB/clock 405KB/clock
Railgun_Doublet performance: 553KB/clock 464KB/clock
BNDM_32 performance: 419KB/clock 383KB/clock
Searching for Pattern('superdog',8bytes) into String(206908949bytes) line-by-line ...
strstr_Microsoft performance: 287KB/clock 288KB/clock
strstr_GNU_C_Library performance: 468KB/clock 378KB/clock
Railgun_Doublet performance: 562KB/clock 470KB/clock
BNDM_32 performance: 420KB/clock 384KB/clock
Searching for Pattern('participants',12bytes) into String(206908949bytes) line-by-line ...
strstr_Microsoft performance: 311KB/clock 315KB/clock
strstr_GNU_C_Library performance: 541KB/clock 415KB/clock
Railgun_Doublet performance: 568KB/clock 477KB/clock
BNDM_32 performance: 436KB/clock 398KB/clock
Searching for Pattern('skillessness',12bytes) into String(206908949bytes) line-by-line ...
strstr_Microsoft performance: 287KB/clock 289KB/clock
strstr_GNU_C_Library performance: 469KB/clock 378KB/clock
Railgun_Doublet performance: 573KB/clock 479KB/clock
BNDM_32 performance: 447KB/clock 407KB/clock
Searching for Pattern('I should have known',19bytes) into String(206908949bytes) line-by-line ...
strstr_Microsoft performance: 316KB/clock 320KB/clock
strstr_GNU_C_Library performance: 557KB/clock 418KB/clock
Railgun_Doublet performance: 587KB/clock 490KB/clock
BNDM_32 performance: 435KB/clock 400KB/clock
Searching for Pattern('human consciousness',19bytes) into String(206908949bytes) line-by-line ...
strstr_Microsoft performance: 291KB/clock 294KB/clock
strstr_GNU_C_Library performance: 482KB/clock 388KB/clock
Railgun_Doublet performance: 594KB/clock 494KB/clock
BNDM_32 performance: 441KB/clock 405KB/clock
Overview:
GNU Berg's performance (compiled with Microsoft 2010 64bit compiler): 376KB/clock+400KB/clock+564KB/clock+346KB/clock+540KB/clock+395KB/clock+535KB/clock+401KB/clock+542KB/clock+455KB/clock+510KB/clock+468KB/clock+541KB/clock+469KB/clock+557KB/clock+482KB/clock=7581
GNU Berg's performance (compiled with Intel C++ 64 Compiler XE 12.1): 296KB/clock+320KB/clock+421KB/clock+276KB/clock+417KB/clock+323KB/clock+415KB/clock+326KB/clock+415KB/clock+367KB/clock+405KB/clock+378KB/clock+415KB/clock+378KB/clock+418KB/clock+388KB/clock=5958
Railgun_Doublet performance (compiled with Microsoft 2010 64bit compiler): 421KB/clock+476KB/clock+551KB/clock+393KB/clock+550KB/clock+534KB/clock+553KB/clock+550KB/clock+559KB/clock+557KB/clock+553KB/clock+562KB/clock+568KB/clock+573KB/clock+587KB/clock+594KB/clock=8581
Railgun_Doublet performance (compiled with Intel C++ 64 Compiler XE 12.1): 348KB/clock+397KB/clock+464KB/clock+328KB/clock+463KB/clock+452KB/clock+465KB/clock+463KB/clock+469KB/clock+468KB/clock+464KB/clock+470KB/clock+477KB/clock+479KB/clock+490KB/clock+494KB/clock=7191
BNDM_32 performance (compiled with Microsoft 2010 64bit compiler): 267KB/clock+290KB/clock+462KB/clock+255KB/clock+390KB/clock+379KB/clock+451KB/clock+395KB/clock+400KB/clock+433KB/clock+419KB/clock+420KB/clock+436KB/clock+447KB/clock+435KB/clock+441KB/clock=6320
BNDM_32 performance (compiled with Intel C++ 64 Compiler XE 12.1): 241KB/clock+262KB/clock+409KB/clock+234KB/clock+352KB/clock+343KB/clock+402KB/clock+359KB/clock+367KB/clock+392KB/clock+383KB/clock+384KB/clock+398KB/clock+407KB/clock+400KB/clock+405KB/clock=5738
Summary for all 16 patterns:
GNU Berg's performance: 7581 Microsoft / 5958 Intel
Railgun_Doublet performance: 8581 Microsoft / 7191 Intel
BNDM_32 performance: 6320 Microsoft / 5738 Intel
Using Microsoft:
Railgun_Doublet is (8581-7581)/7581*100% = 13% faster than GNU Berg's
Railgun_Doublet is (8581-6320)/6320*100% = 35% faster than BNDM_32
Using Intel:
Railgun_Doublet is (7191-5958)/5958*100% = 20% faster than GNU Berg's
Railgun_Doublet is (7191-5738)/5738*100% = 25% faster than BNDM_32
*/
The C source(revision 6) follows:
// ### Mix(2in1) of Karp-Rabin & Boyer-Moore-Horspool algorithm [
// Caution: For better speed the case 'if (cbPattern==1)' was removed, so Pattern must be longer than 1 char.
char * Railgun_Quadruplet (char * pbTarget,
char * pbPattern,
unsigned long cbTarget,
unsigned long cbPattern)
{
char * pbTargetMax = pbTarget + cbTarget;
register unsigned long ulHashPattern;
unsigned long ulHashTarget;
unsigned long count;
unsigned long countSTATIC;
// unsigned long countRemainder;
/*
const unsigned char SINGLET = *(char *)(pbPattern);
const unsigned long Quadruplet2nd = SINGLET<<8;
const unsigned long Quadruplet3rd = SINGLET<<16;
const unsigned long Quadruplet4th = SINGLET<<24;
*/
unsigned char SINGLET;
unsigned long Quadruplet2nd;
unsigned long Quadruplet3rd;
unsigned long Quadruplet4th;
unsigned long AdvanceHopperGrass;
long i; //BMH needed
int a, j, bm_bc[ASIZE]; //BMH needed
unsigned char ch; //BMH needed
// unsigned char lastch, firstch; //BMH needed
if (cbPattern > cbTarget)
return(NULL);
// Doesn't work when cbPattern = 1
// The next IF-fragment works very well with cbPattern>1, OBVIOUSLY IT MUST BE UNROLLED(but crippled with less functionality) SINCE either cbPattern=2 or cbPattern=3!
if ( cbPattern<4) { // This IF makes me unhappy: it slows down from 390KB/clock to 367KB/clock for 'fast' pattern. This fragment(for 2..3 pattern lengths) is needed because I need a function different than strchr but sticking to strstr i.e. lengths above 1 are to be handled.
pbTarget = pbTarget+cbPattern;
ulHashPattern = ( (*(char *)(pbPattern))<<8 ) + *(pbPattern+(cbPattern-1));
countSTATIC = cbPattern-2;
for ( ;; )
{
// The line below gives for 'cbPattern'>=1:
// Karp_Rabin_Kaze_4_OCTETS_hits/Karp_Rabin_Kaze_4_OCTETS_clocks: 4/543
// Karp_Rabin_Kaze_4_OCTETS performance: 372KB/clock
/*
if ( (ulHashPattern == ( (*(char *)(pbTarget-cbPattern))<<8 ) + *(pbTarget-1)) && !memcmp(pbPattern, pbTarget-cbPattern, (unsigned int)cbPattern) )
return((long)(pbTarget-cbPattern));
*/
// The fragment below gives for 'cbPattern'>=2:
// Karp_Rabin_Kaze_4_OCTETS_hits/Karp_Rabin_Kaze_4_OCTETS_clocks: 4/546
// Karp_Rabin_Kaze_4_OCTETS performance: 370KB/clock
if ( ulHashPattern == ( (*(char *)(pbTarget-cbPattern))<<8 ) + *(pbTarget-1) ) {
count = countSTATIC;
while ( count && *(char *)(pbPattern+1+(countSTATIC-count)) == *(char *)(pbTarget-cbPattern+1+(countSTATIC-count)) ) {
count--;
}
if ( count == 0) return((pbTarget-cbPattern));
}
// The fragment below gives for 'cbPattern'>=2:
// Karp_Rabin_Kaze_4_OCTETS_hits/Karp_Rabin_Kaze_4_OCTETS_clocks: 4/554
// Karp_Rabin_Kaze_4_OCTETS performance: 364KB/clock
/*
if ( ulHashPattern == ( (*(char *)(pbTarget-cbPattern))<<8 ) + *(pbTarget-1) ) {
count = countSTATIC>>2;
countRemainder = countSTATIC % 4;
while ( count && *(unsigned long *)(pbPattern+1+((count-1)<<2)) == *(unsigned long *)(pbTarget-cbPattern+1+((count-1)<<2)) ) {
count--;
}
//if (count == 0) { // Disastrous degradation only from this line(317KB/clock when 1+2x4+2+1 bytes pattern: 'skillessness'; 312KB/clock when 1+1x4+2+1 bytes pattern: 'underdog'), otherwise 368KB/clock.
while ( countRemainder && *(char *)(pbPattern+1+(countSTATIC-countRemainder)) == *(char *)(pbTarget-cbPattern+1+(countSTATIC-countRemainder)) ) {
countRemainder--;
}
//if ( countRemainder == 0) return((long)(pbTarget-cbPattern));
if ( count+countRemainder == 0) return((long)(pbTarget-cbPattern));
//}
}
*/
pbTarget++;
if (pbTarget > pbTargetMax)
return(NULL);
}
} else { //if ( cbPattern<4)
if (cbTarget<961) // This value is arbitrary(don't know how exactly), it ensures(at least must) better performance than 'Boyer_Moore_Horspool'.
{
pbTarget = pbTarget+cbPattern;
ulHashPattern = *(unsigned long *)(pbPattern);
countSTATIC = cbPattern-1;
//SINGLET = *(char *)(pbPattern);
SINGLET = ulHashPattern & 0xFF;
Quadruplet2nd = SINGLET<<8;
Quadruplet3rd = SINGLET<<16;
Quadruplet4th = SINGLET<<24;
for ( ;; )
{
AdvanceHopperGrass = 0;
ulHashTarget = *(unsigned long *)(pbTarget-cbPattern);
if ( ulHashPattern == ulHashTarget ) { // Three unnecessary comparisons here, but 'AdvanceHopperGrass' must be calculated - it has a higher priority.
count = countSTATIC;
while ( count && *(char *)(pbPattern+1+(countSTATIC-count)) == *(char *)(pbTarget-cbPattern+1+(countSTATIC-count)) ) {
if ( countSTATIC==AdvanceHopperGrass+count && SINGLET != *(char *)(pbTarget-cbPattern+1+(countSTATIC-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<961)
countSTATIC = cbPattern-2;
/* Preprocessing */
for (a=0; a < ASIZE; a++) bm_bc[a]=cbPattern;
for (j=0; j < cbPattern-1; j++) bm_bc[pbPattern[j]]=cbPattern-j-1;
/* Searching */
//lastch=pbPattern[cbPattern-1];
//firstch=pbPattern[0];
i=0;
while (i <= cbTarget-cbPattern) {
ch=pbTarget[i+cbPattern-1];
//if (ch ==lastch)
//if (memcmp(&pbTarget[i],pbPattern,cbPattern-1) == 0) OUTPUT(i);
//if (ch == lastch && pbTarget[i] == firstch && memcmp(&pbTarget[i],pbPattern,cbPattern-1) == 0) return(i); // Kaze: The idea(to prevent execution of slower 'memcmp') is borrowed from Karp-Rabin i.e. to perform a slower check only when the target "looks like".
if (ch == pbPattern[cbPattern-1] && pbTarget[i] == pbPattern[0])
{
count = countSTATIC;
while ( count && *(char *)(pbPattern+1+(countSTATIC-count)) == *(char *)(&pbTarget[i]+1+(countSTATIC-count)) ) {
count--;
}
if ( count == 0) return(pbTarget+i);
}
i+=bm_bc[ch];
}
return(NULL);
} //if (cbTarget<961)
} //if ( cbPattern<4)
}
// ### Mix(2in1) of Karp-Rabin & Boyer-Moore-Horspool algorithm ]
The C source(revision 7) follows:
// Caution: For better speed the case 'if (cbPattern==1)' was removed, so Pattern must be longer than 1 char.
char * Railgun_Quadruplet_7 (char * pbTarget, char * pbPattern, unsigned long cbTarget, unsigned long cbPattern)
{
char * pbTargetMax = pbTarget + cbTarget;
register unsigned long ulHashPattern;
unsigned long ulHashTarget;
signed long count;
signed long countSTATIC;
unsigned char SINGLET;
unsigned long Quadruplet2nd;
unsigned long Quadruplet3rd;
unsigned long Quadruplet4th;
unsigned long AdvanceHopperGrass;
long i;
int a, j, bm_bc[ASIZE];
unsigned char ch;
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++;
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<961) {
pbTarget = pbTarget+cbPattern;
ulHashPattern = *(unsigned long *)(pbPattern);
SINGLET = ulHashPattern & 0xFF;
Quadruplet2nd = SINGLET<<8;
Quadruplet3rd = SINGLET<<16;
Quadruplet4th = SINGLET<<24;
for ( ;; ) {
AdvanceHopperGrass = 0;
ulHashTarget = *(unsigned long *)(pbTarget-cbPattern);
if ( ulHashPattern == ulHashTarget ) {
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 {
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 {
countSTATIC = cbPattern-2-2;
ulHashPattern = *(unsigned long *)(pbPattern);
for (a=0; a < ASIZE; a++) bm_bc[a]=cbPattern;
for (j=0; j < cbPattern-1; j++) bm_bc[pbPattern[j]]=cbPattern-j-1;
i=0;
while (i <= cbTarget-cbPattern) {
if ( *(unsigned long *)&pbTarget[i] == ulHashPattern ) {
count = countSTATIC;
while ( count !=0 && *(char *)(pbPattern+1+3+(countSTATIC-count)) == *(char *)(&pbTarget[i]+1+3+(countSTATIC-count)) ) count--;
if ( count == 0) return(pbTarget+i);
}
i= i + bm_bc[(unsigned char)pbTarget[i+cbPattern-1]];
}
return(NULL);
}
}
}
The C source(revision Railgun_Quadruplet_7Gulliver_count_hits) follows:
// ### Mix(2in1) of Karp-Rabin & Boyer-Moore-Sunday-Horspool algorithm [
/*
Tuning continues but the skeleton is built, I see 'Gulliver' as a really High-Performance etude.
And not to be empty-handed here the Gulliver's swiftness is benchmarked on String(206,908,949bytes) as-one-line:
Pattern: fast
Railgun_Quadruplet_7sun performance: 1057KB/clock / 456%, 45330622 skips/iterations
Railgun_Quadruplet_7 performance: 0976KB/clock / 377%, 54788054 skips/iterations
Railgun_Quadruplet_7sunhorse performance: 0649KB/clock / 480%, 43103056 skips/iterations
Railgun_Quadruplet_7deuce performance: 0564KB/clock / 389%, 53138919 skips/iterations
Railgun_Quadruplet_7Elsiane performance: 0505KB/clock / 551%, 37541955 skips/iterations
Railgun_Quadruplet_7Gulliver performance: 0780KB/clock / 300%, 68943184 skips/iterations
Boyer_Moore_Flensburg performance: 0486KB/clock / 377%, 54788139 skips/iterations
Pattern: faster
Railgun_Quadruplet_7sun performance: 1356KB/clock / 591%, 34996936 skips/iterations
Railgun_Quadruplet_7 performance: 1320KB/clock / 514%, 40194194 skips/iterations
Railgun_Quadruplet_7sunhorse performance: 0771KB/clock / 656%, 31504148 skips/iterations
Railgun_Quadruplet_7deuce performance: 0651KB/clock / 567%, 36434006 skips/iterations
Railgun_Quadruplet_7Elsiane performance: 0535KB/clock / 710%, 29101626 skips/iterations
Railgun_Quadruplet_7Gulliver performance: 1195KB/clock / 498%, 41544613 skips/iterations
Boyer_Moore_Flensburg performance: 0684KB/clock / 514%, 40194282 skips/iterations
Pattern: fastest
Railgun_Quadruplet_7sun performance: 1554KB/clock / 687%, 30084306 skips/iterations
Railgun_Quadruplet_7 performance: 1519KB/clock / 599%, 34540430 skips/iterations
Railgun_Quadruplet_7sunhorse performance: 0918KB/clock / 761%, 27188853 skips/iterations
Railgun_Quadruplet_7deuce performance: 0771KB/clock / 663%, 31175827 skips/iterations
Railgun_Quadruplet_7Elsiane performance: 0627KB/clock / 818%, 25281493 skips/iterations
Railgun_Quadruplet_7Gulliver performance: 1453KB/clock / 595%, 34744153 skips/iterations
Boyer_Moore_Flensburg performance: 0792KB/clock / 621%, 33278240 skips/iterations
Pattern: fastest fox
Railgun_Quadruplet_7sun performance: 1712KB/clock / 775%, 26672940 skips/iterations
Railgun_Quadruplet_7 performance: 1669KB/clock / 669%, 30925578 skips/iterations
Railgun_Quadruplet_7sunhorse performance: 0962KB/clock / 912%, 22663583 skips/iterations
Railgun_Quadruplet_7deuce performance: 0808KB/clock / 797%, 25945709 skips/iterations
Railgun_Quadruplet_7Elsiane performance: 0719KB/clock / 931%, 22213101 skips/iterations
Railgun_Quadruplet_7Gulliver performance: 2126KB/clock / 977%, 21166516 skips/iterations
Boyer_Moore_Flensburg performance: 1074KB/clock / 669%, 30925649 skips/iterations
Pattern: fastest fox with biggest strides
Railgun_Quadruplet_7sun performance: 2658KB/clock / 1584%, 13060463 skips/iterations
Railgun_Quadruplet_7 performance: 2767KB/clock / 1511%, 13689243 skips/iterations
Railgun_Quadruplet_7sunhorse performance: 1820KB/clock / 2138%, 09677267 skips/iterations
Railgun_Quadruplet_7deuce performance: 1669KB/clock / 2053%, 10075650 skips/iterations
Railgun_Quadruplet_7Elsiane performance: 1554KB/clock / 2143%, 09652548 skips/iterations
Railgun_Quadruplet_7Gulliver performance: 3157KB/clock / 2924%, 07074287 skips/iterations Stratosphere-borne!
Boyer_Moore_Flensburg performance: 1836KB/clock / 1554%, 13307181 skips/iterations
Pattern: fastest fox with biggest strides known to me
Railgun_Quadruplet_7sun performance: 2590KB/clock / 1548%, 13363356 skips/iterations
Railgun_Quadruplet_7 performance: 2694KB/clock / 1447%, 14292419 skips/iterations
Railgun_Quadruplet_7sunhorse performance: 1924KB/clock / 2234%, 09259505 skips/iterations
Railgun_Quadruplet_7deuce performance: 1741KB/clock / 2011%, 10287584 skips/iterations
Railgun_Quadruplet_7Elsiane performance: 1683KB/clock / 2240%, 09236188 skips/iterations
Railgun_Quadruplet_7Gulliver performance: 3157KB/clock / 3832%, 05399116 skips/iterations Mesosphere-borne!
Boyer_Moore_Flensburg performance: 1741KB/clock / 1540%, 13431751 skips/iterations
Pattern: fastest fox with biggest strides known to me up to 2012 January 26 namely 'Gulliver'
Railgun_Quadruplet_7sun performance: 3108KB/clock / 2890%, 07159321 skips/iterations
Railgun_Quadruplet_7 performance: 3108KB/clock / 2742%, 07545141 skips/iterations
Railgun_Quadruplet_7sunhorse performance: 2590KB/clock / 4138%, 04999777 skips/iterations
Railgun_Quadruplet_7deuce performance: 2464KB/clock / 4029%, 05135444 skips/iterations
Railgun_Quadruplet_7Elsiane performance: 2557KB/clock / 4141%, 04995463 skips/iterations
Railgun_Quadruplet_7Gulliver performance: 3157KB/clock / 7218%, 02866192 skips/iterations Vacuum-borne!
Boyer_Moore_Flensburg performance: 2767KB/clock / 2745%, 07536097 skips/iterations
*/
//
// Revision: 2, 2012-Jan-30, the main disadvantage: the preprocessing overhead.
// Caution: For better speed the case 'if (cbPattern==1)' was removed, so Pattern must be longer than 1 char.
//
char * Railgun_Quadruplet_7Gulliver_count_hits (char * pbTarget, char * pbPattern, unsigned long cbTarget, unsigned long cbPattern)
{
char * pbTargetMax = pbTarget + cbTarget;
register unsigned long ulHashPattern;
register unsigned long ulHashTarget;
signed long count;
signed long countSTATIC;
unsigned char SINGLET;
unsigned long Quadruplet2nd;
unsigned long Quadruplet3rd;
unsigned long Quadruplet4th;
unsigned long 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 long 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) ) Railgunhits++; //return((pbTarget-3));
}
if ( (char)(ulHashPattern>>8) != *(pbTarget-2) ) pbTarget++;
pbTarget++;
if (pbTarget > pbTargetMax)
return(NULL);
}
} else {
}
for ( ;; ) {
if ( ulHashPattern == ( (*(char *)(pbTarget-2))<<8 ) + *(pbTarget-1) )
Railgunhits++; //return((pbTarget-2));
if ( (char)(ulHashPattern>>8) != *(pbTarget-1) ) pbTarget++;
pbTarget++;
if (pbTarget > pbTargetMax)
return(NULL);
}
} else { //if ( cbPattern<4)
if (cbTarget<961) { // This value is arbitrary(don't know how exactly), it ensures(at least must) better performance than 'Boyer_Moore_Horspool'.
/*
// A better strstr, with no asm code
// Written by Mischa Sandberg
// http://mischasan.wordpress.com
// static char const *
// scanstrm(char const *tgt, char const *pat, int len)
// {
// uint32_t head = MSBF32(pat), wind = 0, next;
//
// pat += 4, len -= 4;
// while ((next = *(uint8_t const*)tgt++)) {
// wind = ( wind << 8 ) + next;
// if (wind == head && !memcmp(tgt, pat, len))
// return tgt - 4;
// }
// return NULL;
//}
ulHashPattern = 0;
ulHashPattern = ( ulHashPattern << 8 ) + *(uint8_t const*)pbPattern++;
ulHashPattern = ( ulHashPattern << 8 ) + *(uint8_t const*)pbPattern++;
ulHashPattern = ( ulHashPattern << 8 ) + *(uint8_t const*)pbPattern++;
ulHashPattern = ( ulHashPattern << 8 ) + *(uint8_t const*)pbPattern++;
AdvanceHopperGrass = 0;
cbPattern -= 4;
while ((ulHashTarget = *(uint8_t const*)pbTarget++)) {
AdvanceHopperGrass = ( AdvanceHopperGrass << 8 ) + ulHashTarget;
if (AdvanceHopperGrass == ulHashPattern && !memcmp(pbTarget, pbPattern, cbPattern))
Railgunhits++; //return pbTarget - 4;
}
return NULL;
*/
pbTarget = pbTarget+cbPattern;
ulHashPattern = *(unsigned long *)(pbPattern);
SINGLET = ulHashPattern & 0xFF;
Quadruplet2nd = SINGLET<<8;
Quadruplet3rd = SINGLET<<16;
Quadruplet4th = SINGLET<<24;
for ( ;; ) {
AdvanceHopperGrass = 0;
ulHashTarget = *(unsigned long *)(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) Railgunhits++; //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<961)
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 = *(unsigned long *)(pbPattern); // First four bytes
//ulHashTarget = *(unsigned short *)(pbPattern+cbPattern-1-1); // Last two bytes
AdvanceHopperGrass = 0;
i=0;
// Elsiane r.2 [
for (a=0; a < 256*256; a++) {bm_Horspool_Order2[a]= cbPattern-1;} // cbPattern-(Order-1) for Horspool; 'memset' if not optimized
// alfalfa 7 long 6 BBs (al lf fa al lf fa) 3 distinct BBs (al lf fa)
// fast 4 0-1-2 fa as st
for (j=0; j < cbPattern-1; j++) bm_Horspool_Order2[*(unsigned short *)(pbPattern+j)]=j; // Rightmost appearance/position is needed
// Elsiane r.2 ]
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 ( *(unsigned long *)&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) Railgunhits++; //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
AdvanceHopperGrass++;
}
if (i == cbTarget-cbPattern) {
if ( *(unsigned long *)&pbTarget[i] == ulHashPattern) {
count = countSTATIC;
while ( count !=0 && *(char *)(pbPattern+(countSTATIC-count)+4) == *(char *)(&pbTarget[i]+(countSTATIC-count)+4) )
count--;
if ( count == 0) Railgunhits++; //return(pbTarget+i);
}
AdvanceHopperGrass++;
}
GlobalSP += (int)((double)cbTarget/AdvanceHopperGrass*100);
GlobalI += AdvanceHopperGrass;
printf("Skip-Performance(bigger-the-better): %d%%, %d skips/iterations\n",(int)((double)cbTarget/AdvanceHopperGrass*100), AdvanceHopperGrass);
return(NULL);
} //if (cbTarget<961)
} //if ( cbPattern<4)
}
// ### Mix(2in1) of Karp-Rabin & Boyer-Moore-Sunday-Horspool algorithm ]
The C source(revision Railgun_Quadruplet_7Hasherezade_count_hits) follows:
// ### Mix(2in1) of Karp-Rabin & Boyer-Moore-Sunday-Horspool algorithm [
// Scheherezade -> Hasherezade
// [Italian: buffa, feminine of buffo, comic.]
/*
First off: I am heavily disappointed from Speed-Performance of 'Hasherezade' and comparing Skip-Performance of 'Gulliver' and 'Hasherezade' doesn't make me happy, either.
Pattern: fastest fox
Doing Search for Pattern(11bytes) into String(206908949bytes) as-one-line ...
Railgun_Quadruplet_7sun performance: 1,683KB/clock / 00,775%, 26,672,940 skips/iterations
Railgun_Quadruplet_7 performance: 1,642KB/clock / 00,669%, 30,925,578 skips/iterations
Railgun_Quadruplet_7sunhorse performance: 0,944KB/clock / 00,912%, 22,663,583 skips/iterations
Railgun_Quadruplet_7deuce performance: 0,801KB/clock / 00,797%, 25,945,709 skips/iterations
Railgun_Quadruplet_7Elsiane performance: 0,704KB/clock / 00,931%, 22,213,101 skips/iterations
Railgun_Quadruplet_7Gulliver performance: 2,104KB/clock / 00,977%, 21,166,516 skips/iterations
Railgun_Quadruplet_7Hasherezade performance: 1,496KB/clock / 00,980%, 21,112,657 skips/iterations 18bit HashTable
Railgun_Quadruplet_7Hasherezade performance: 1,642KB/clock / 00,980%, 21,112,646 skips/iterations 14bit HashTable
Railgun_Quadruplet_7Hasherezade performance: 1,642KB/clock / 00,980%, 21,112,735 skips/iterations 10bit HashTable
Boyer_Moore_Flensburg performance: 1,057KB/clock / 00,669%, 30,925,578 skips/iterations
Pattern: and every day a continuous cleaning goes on
Doing Search for Pattern(43bytes) into String(206908949bytes) as-one-line ...
Railgun_Quadruplet_7sun performance: 2,557KB/clock / 01,495%, 13,832,201 skips/iterations
Railgun_Quadruplet_7 performance: 2,590KB/clock / 01,404%, 14,731,326 skips/iterations
Railgun_Quadruplet_7sunhorse performance: 1,888KB/clock / 02,222%, 09,308,136 skips/iterations
Railgun_Quadruplet_7deuce performance: 1,741KB/clock / 01,971%, 10,494,460 skips/iterations
Railgun_Quadruplet_7Elsiane performance: 1,642KB/clock / 02,229%, 09,279,871 skips/iterations
Railgun_Quadruplet_7Gulliver performance: 3,157KB/clock / 03,795%, 05,450,890 skips/iterations
Railgun_Quadruplet_7Hasherezade performance: 2,322KB/clock / 04,100%, 05,046,049 skips/iterations 18bit HashTable
Railgun_Quadruplet_7Hasherezade performance: 2,971KB/clock / 04,100%, 05,046,445 skips/iterations 14bit HashTable
Railgun_Quadruplet_7Hasherezade performance: 3,015KB/clock / 04,090%, 05,058,667 skips/iterations 10bit HashTable
Boyer_Moore_Flensburg performance: 1,683KB/clock / 01,447%, 14,294,963 skips/iterations
Pattern: And let this be your very fundamental insight... about everything. Just for one year, don't choose.
Doing Search for Pattern(99bytes) into String(206908949bytes) as-one-line ...
Railgun_Quadruplet_7sun performance: 2,845KB/clock / 02,248%, 09,200,917 skips/iterations
Railgun_Quadruplet_7 performance: 2,928KB/clock / 02,105%, 09,827,389 skips/iterations
Railgun_Quadruplet_7sunhorse performance: 2,270KB/clock / 03,283%, 06,302,096 skips/iterations
Railgun_Quadruplet_7deuce performance: 2,149KB/clock / 03,196%, 06,472,407 skips/iterations
Railgun_Quadruplet_7Elsiane performance: 2,172KB/clock / 03,282%, 06,303,154 skips/iterations
Railgun_Quadruplet_7Gulliver performance: 2,928KB/clock / 07,820%, 02,645,814 skips/iterations
Railgun_Quadruplet_7Hasherezade performance: 2,494KB/clock / 09,575%, 02,160,890 skips/iterations 18bit HashTable
Railgun_Quadruplet_7Hasherezade performance: 3,015KB/clock / 09,568%, 02,162,493 skips/iterations 14bit HashTable
Railgun_Quadruplet_7Hasherezade performance: 3,015KB/clock / 09,438%, 02,192,204 skips/iterations 10bit HashTable
Boyer_Moore_Flensburg performance: 2,349KB/clock / 02,135%, 09,689,008 skips/iterations
Pattern: Then, singing among the savage branches, it impales itself upon the longest, sharpest spine. And, dying, it rises above its own agony to outcarol the lark and the nightingale.
Doing Search for Pattern(175bytes) into String(206908949bytes) as-one-line ...
Railgun_Quadruplet_7sun performance: 2,658KB/clock / 03,142%, 06,583,682 skips/iterations
Railgun_Quadruplet_7 performance: 2,658KB/clock / 03,095%, 06,685,179 skips/iterations
Railgun_Quadruplet_7sunhorse performance: 2,377KB/clock / 04,776%, 04,331,865 skips/iterations
Railgun_Quadruplet_7deuce performance: 2,349KB/clock / 04,728%, 04,376,097 skips/iterations
Railgun_Quadruplet_7Elsiane performance: 2,525KB/clock / 04,778%, 04,330,200 skips/iterations
Railgun_Quadruplet_7Gulliver performance: 2,245KB/clock / 12,024%, 01,720,711 skips/iterations
Railgun_Quadruplet_7Hasherezade performance: 2,434KB/clock / 17,127%, 01,208,072 skips/iterations 18bit HashTable
Railgun_Quadruplet_7Hasherezade performance: 2,590KB/clock / 17,084%, 01,211,064 skips/iterations 14bit HashTable
Railgun_Quadruplet_7Hasherezade performance: 2,590KB/clock / 16,379%, 01,263,238 skips/iterations 10bit HashTable
Boyer_Moore_Flensburg performance: 2,525KB/clock / 03,198%, 06,469,280 skips/iterations Five times more main-cycles and faster than 'Hasherezade', pshaw!
*/
#define ROL(x, n) (((x) << (n)) | ((x) >> (32-(n))))
#define HashTableSize 18
// Revision: 1, 2012-Feb-01, the main disadvantage: the preprocessing overhead PLUS a hasher.
// Caution: For better speed the case 'if (cbPattern==1)' was removed, so Pattern must be longer than 1 char.
char * Railgun_Quadruplet_7Hasherezade_count_hits (char * pbTarget, char * pbPattern, unsigned long cbTarget, unsigned long cbPattern)
{
char * pbTargetMax = pbTarget + cbTarget;
register unsigned long ulHashPattern;
register unsigned long ulHashTarget;
signed long count;
signed long countSTATIC;
unsigned char SINGLET;
unsigned long Quadruplet2nd;
unsigned long Quadruplet3rd;
unsigned long Quadruplet4th;
unsigned long 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<<(HashTableSize)]; // Jesteressing 8bytes (Horspool Order 8) for fast lookup, should be bitwise (i.e. 8times smaller) since it says yes/no for presence.
uint32_t hash32;
unsigned long 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) ) Railgunhits++; //return((pbTarget-3));
}
if ( (char)(ulHashPattern>>8) != *(pbTarget-2) ) pbTarget++;
pbTarget++;
if (pbTarget > pbTargetMax)
return(NULL);
}
} else {
}
for ( ;; ) {
if ( ulHashPattern == ( (*(char *)(pbTarget-2))<<8 ) + *(pbTarget-1) )
Railgunhits++; //return((pbTarget-2));
if ( (char)(ulHashPattern>>8) != *(pbTarget-1) ) pbTarget++;
pbTarget++;
if (pbTarget > pbTargetMax)
return(NULL);
}
} else { //if ( cbPattern<4)
if (cbTarget<961) { // This value is arbitrary(don't know how exactly), it ensures(at least must) better performance than 'Boyer_Moore_Horspool'.
/*
// A better strstr, with no asm code
// Written by Mischa Sandberg
// http://mischasan.wordpress.com
// static char const *
// scanstrm(char const *tgt, char const *pat, int len)
// {
// uint32_t head = MSBF32(pat), wind = 0, next;
//
// pat += 4, len -= 4;
// while ((next = *(uint8_t const*)tgt++)) {
// wind = ( wind << 8 ) + next;
// if (wind == head && !memcmp(tgt, pat, len))
// return tgt - 4;
// }
// return NULL;
//}
ulHashPattern = 0;
ulHashPattern = ( ulHashPattern << 8 ) + *(uint8_t const*)pbPattern++;
ulHashPattern = ( ulHashPattern << 8 ) + *(uint8_t const*)pbPattern++;
ulHashPattern = ( ulHashPattern << 8 ) + *(uint8_t const*)pbPattern++;
ulHashPattern = ( ulHashPattern << 8 ) + *(uint8_t const*)pbPattern++;
AdvanceHopperGrass = 0;
cbPattern -= 4;
while ((ulHashTarget = *(uint8_t const*)pbTarget++)) {
AdvanceHopperGrass = ( AdvanceHopperGrass << 8 ) + ulHashTarget;
if (AdvanceHopperGrass == ulHashPattern && !memcmp(pbTarget, pbPattern, cbPattern))
Railgunhits++; //return pbTarget - 4;
}
return NULL;
*/
pbTarget = pbTarget+cbPattern;
ulHashPattern = *(unsigned long *)(pbPattern);
SINGLET = ulHashPattern & 0xFF;
Quadruplet2nd = SINGLET<<8;
Quadruplet3rd = SINGLET<<16;
Quadruplet4th = SINGLET<<24;
for ( ;; ) {
AdvanceHopperGrass = 0;
ulHashTarget = *(unsigned long *)(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) Railgunhits++; //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<961)
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 = *(unsigned long *)(pbPattern); // First four bytes
//ulHashTarget = *(unsigned short *)(pbPattern+cbPattern-1-1); // Last two bytes
AdvanceHopperGrass = 0;
i=0;
// Elsiane r.2 [
for (a=0; a < 256*256; a++) {bm_Horspool_Order2[a]= cbPattern-1;} // cbPattern-(Order-1) for Horspool; 'memset' if not optimized
// alfalfa 7 long 6 BBs (al lf fa al lf fa) 3 distinct BBs (al lf fa)
// fast 4 0-1-2 fa as st
for (j=0; j < cbPattern-1; j++) bm_Horspool_Order2[*(unsigned short *)(pbPattern+j)]=j; // Rightmost appearance/position is needed
// Elsiane r.2 ]
if ( cbPattern>10) {
// Hasherezade r.1 [
// OSHO.TXT has 00,046,486 03bytes distinct BBs
// OSHO.TXT has 00,248,019 04bytes distinct BBs
// OSHO.TXT has 00,855,682 05bytes distinct BBs
// OSHO.TXT has 02,236,138 06bytes distinct BBs
// OSHO.TXT has 04,803,152 07bytes distinct BBs
// OSHO.TXT has 08,956,496 08bytes distinct BBs to be hashed in 18bit i.e. 256KB i.e. 262,144 slots i.e. 34 vs 1.
// OSHO.TXT has 15,006,172 09bytes distinct BBs
// OSHO.TXT has 22,992,127 10bytes distinct BBs
// Note: BB stands for Building-Block (also suffix)
for (a=0; a < 1<<(HashTableSize); a++) {bm_Hasherezade_HASH[a]= 0;} // to-do: bit to replace byte; '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'
for (j=0; j < cbPattern-8+1; j++) {
hash32 = (2166136261 ^ (ROL(*(uint32_t *)(pbPattern+j),5)^*(uint32_t *)(pbPattern+j+4))) * 709607;
bm_Hasherezade_HASH[( hash32 ^ (hash32 >> 16) ) & ( (1<<(HashTableSize))-1 )]=1;
/*
for (a=0; a<8; a++)
printf("%c",*(char *)(pbPattern+j+a) );
printf(" %lu\n",( hash32 ^ (hash32 >> 16) ) & ( (1<<(HashTableSize))-1 ));
//Input Pattern(up to 19+2000 chars): and every day a continuous cleaning goes on
//Doing Search for Pattern(43bytes) into String(206908949bytes) as-one-line ...
BBs Slot(HashCode for 18bit HashTable)
and ever 117013
nd every 108604
d every 155516
every d 170959
every da 115291
very day 73191
ery day 97042
ry day a 83793
y day a 11244
day a c 115855
day a co 101797
ay a con 222568
y a cont 29130
a conti 20978
a contin 258405
continu 252691
continuo 123607
ontinuou 56546
ntinuous 135857
tinuous 15332
inuous c 250584
nuous cl 48224
uous cle 106616
ous clea 137020
us clean 35751
s cleani 178989
cleanin 213855
cleaning 63337
leaning 97138
eaning g 62366
aning go 247590
ning goe 36571
ing goes 41142
ng goes 228365
g goes o 229696
goes on 176852
*/
}
// Hasherezade r.1 ]
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 ( *(unsigned long *)&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) Railgunhits++; //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
// 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
if (Gulliver < cbPattern-(8-1)) {
hash32 = (2166136261 ^ (ROL(*(uint32_t *)(pbTarget+i+cbPattern-8),5)^*(uint32_t *)(pbTarget+i+cbPattern-8+4))) * 709607;
if ( bm_Hasherezade_HASH[( hash32 ^ (hash32 >> 16) ) & ( (1<<(HashTableSize))-1 )]==0 )
Gulliver = cbPattern-(8-1);
}
i = i + Gulliver;
AdvanceHopperGrass++;
/*
; 4155 : // 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
; 4156 : if (Gulliver < cbPattern-(8-1)) {
01f16 8d 43 f9 lea eax, DWORD PTR [ebx-7]
01f19 3b c8 cmp ecx, eax
01f1b 73 30 jae SHORT $LN18@Railgun_Qu@8
; 4157 : hash32 = (2166136261 ^ (ROL(*(uint32_t *)(pbTarget+i+cbPattern-8),5)^*(uint32_t *)(pbTarget+i+cbPattern-8+4))) * 709607;
01f1d 8b 44 32 f8 mov eax, DWORD PTR [edx+esi-8]
01f21 c1 c0 05 rol eax, 5
01f24 33 44 32 fc xor eax, DWORD PTR [edx+esi-4]
01f28 35 c5 9d 1c 81 xor eax, -2128831035 ; 811c9dc5H
01f2d 69 c0 e7 d3 0a
00 imul eax, 709607 ; 000ad3e7H
; 4158 : if ( bm_Hasherezade_HASH[( hash32 ^ (hash32 >> 16) ) & ( (1<<(HashTableSize))-1 )]==0 )
01f33 8b f8 mov edi, eax
01f35 c1 ef 10 shr edi, 16 ; 00000010H
01f38 33 f8 xor edi, eax
01f3a 81 e7 ff ff 03
00 and edi, 262143 ; 0003ffffH
01f40 80 bc 3c 28 08
01 00 00 cmp BYTE PTR _bm_Hasherezade_HASH$[esp+edi+329776], 0
01f48 75 03 jne SHORT $LN18@Railgun_Qu@8
; 4159 : Gulliver = cbPattern-(8-1);
01f4a 8d 4b f9 lea ecx, DWORD PTR [ebx-7]
$LN18@Railgun_Qu@8:
; 4160 : }
; 4161 : i = i + Gulliver;
; 4162 : AdvanceHopperGrass++;
*/
}
} else {
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 ( *(unsigned long *)&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) Railgunhits++; //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
AdvanceHopperGrass++;
}
} //if ( cbPattern>10) {
if (i == cbTarget-cbPattern) {
if ( *(unsigned long *)&pbTarget[i] == ulHashPattern) {
count = countSTATIC;
while ( count !=0 && *(char *)(pbPattern+(countSTATIC-count)+4) == *(char *)(&pbTarget[i]+(countSTATIC-count)+4) )
count--;
if ( count == 0) Railgunhits++; //return(pbTarget+i);
}
AdvanceHopperGrass++;
}
GlobalSP += (int)((double)cbTarget/AdvanceHopperGrass*100);
GlobalI += AdvanceHopperGrass;
printf("Skip-Performance(bigger-the-better): %d%%, %d skips/iterations\n",(int)((double)cbTarget/AdvanceHopperGrass*100), AdvanceHopperGrass);
return(NULL);
} //if (cbTarget<961)
} //if ( cbPattern<4)
}
// ### Mix(2in1) of Karp-Rabin & Boyer-Moore-Sunday-Horspool algorithm ]
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment