Is this a c++ program ???
What is 'ssize_t'

On 31 Mar 2007 10:44:45 -0700,

This contest is open to everyone who knows C++. To enter all you need
to do<snip>

Sounds like spec work to me. Unless you're PAYING ME, UP
FRONT...*shakes head*...I don't fuckin think so, kid. I don't work on
spec...EVER.

--

Onideus Mad Hatter
mhm =B9 x =B9http://www.backwater-productions.nethttp://www.backwater-pro=

Hatter Quotes
-------------
"You're only one of the best if you're striving to become one of the
best."

"I didn't make reality, Sunshine, I just verbally ***** slapped you
with it."

"I'm not a professional, I'm an artist."

"Your Usenet blinders are my best friend."

"Usenet Filters - Learn to shut yourself the ***** up!"

"Drugs killed Jesus you know...oh wait, no, that was the Jews, my
bad."

"There are clingy things in the grass...burrs 'n such...mmmm..."

"The more I learn the more I'm killing my idols."

"Is it wrong to incur and then use the hate ridden, vengeful stupidity
of complete strangers in random Usenet froups to further my art?"

"Freedom is only a concept, like race it's merely a social construct
that doesn't really exist outside of your ability to convince others
of its relevancy."

"Next time slow up a lil, then maybe you won't jump the gun and start
creamin yer panties before it's time to pop the champagne proper."

"Reality is directly proportionate to how creative you are."

"People are pretty fucking high on themselves if they think that
they're just born with a soul. *snicker*...yeah, like they're just
givin em out for free."

"Quible, quible said the Hare. Quite a lot of quibling...everywhere.
So the Hare took a long stare and decided at best, to leave the rest,
to their merry little mess."

"There's a difference between 'bad' and 'so earth shatteringly
horrible it makes the angels scream in terror as they violently rip
their heads off, their blood spraying into the faces of a thousand
sweet innocent horrified children, who will forever have the terrible
images burned into their tiny little minds'."

"How sad that you're such a poor judge of style that you can't even
properly gauge the artistic worth of your own efforts."

"Those who record history are those who control history."

"I am the living embodiment of hell itself in all its tormentive rage,
endless suffering, unfathomable pain and unending horror...but you
don't get sent to me...I come for you."

"Ideally in a fight I'd want a BGM-109A with a W80 250 kiloton
tactical thermonuclear fusion based war head."

"Tell me, would you describe yourself more as a process or a
function?"

"Apparently this group has got the market cornered on stupid.
Intelligence is down 137 points across the board and the forecast
indicates an increase in Webtv users."

"Is my .sig delimiter broken? Really? You're sure? Awww,
gee...that's too bad...for YOU!" `, )

On 31 Mar 2007 10:44:45 -0700,

This contest is open to everyone who knows C++. To enter all you need
to do<snip>

Sounds like spec work to me. Unless you're PAYING ME, UP
FRONT...*shakes head*...I don't fuckin think so, kid. I don't work on
spec...EVER.

On Mar 31, 1:44 pm,

This contest is open to everyone who knows C++. To enter all you need
to do is take the Boyer-Moore String Search Algorithm, as it is
written in C, and make the fastest running C++ program you can out of
it. I'm going to try to write code myself, and if you can beet me,
and your code executes faster, then you win a free I-Pod. My I-Pod is
used, but it comes jam packed with songs I've been listening to. So
take a crack at this problem and post your solution to the group. :)

http://en.wikipedia.org/wiki/Boyer-Moore_string_search_algorithm

#include <string.h>
#include <limits.h>

/* This helper function checks, whether the last "portion" bytes
* of "needle" (which is "nlen" bytes long) exist within the "needle"
* at offset "offset" (counted from the end of the string),
* and whether the character preceding "offset" is not a match.
* Notice that the range being checked may reach beyond the
* beginning of the string. Such range is ignored.
*/
static int boyermoore_needlematch
(const unsigned char* needle, size_t nlen, size_t portion, size_t
offset)
{
ssize_t virtual_begin = nlen-offset-portion;
ssize_t ignore = 0;
if(virtual_begin < 0) { ignore = -virtual_begin; virtual_begin =
0; }

if(virtual_begin > 0 && needle[virtual_begin-1] == needle[nlen-
portion-1])
return 0;

return
memcmp(needle + nlen - portion + ignore,
needle + virtual_begin,
portion - ignore) == 0;

}

static size_t max(ssize_t a, ssize_t b) { return a>b ? a : b; }

/* Returns a pointer to the first occurrence of "needle"
* within "haystack", or NULL if not found.
*/
const unsigned char* memmem_boyermoore
(const unsigned char* haystack, size_t hlen,
const unsigned char* needle, size_t nlen)
{
size_t skip[nlen]; /* Array of shifts with self-substring match
check */
ssize_t occ[UCHAR_MAX+1]; /* Array of last occurrence of each
character */
size_t a, hpos;

if(nlen > hlen || nlen <= 0 || !haystack || !needle) return NULL;

/* Preprocess #1: init occ[]*/

/* Initialize the table to default value */
for(a=0; a<UCHAR_MAX+1; ++a) occ[a] = -1;

/* Then populate it with the analysis of the needle */
/* But ignoring the last letter */
for(a=0; a<nlen-1; ++a) occ[needle[a]] = a;

/* Preprocess #2: init skip[] */
/* Note: This step could be made a lot faster.
* A simple implementation is shown here. */
for(a=0; a<nlen; ++a)
{
size_t value = 0;
while(value < nlen && !boyermoore_needlematch(needle, nlen, a,
value))
++value;
skip[nlen-a-1] = value;
}

/* Search: */
for(hpos=0; hpos <= hlen-nlen; )
{
size_t npos=nlen-1;
while(needle[npos] == haystack[npos+hpos])
{
if(npos == 0) return haystack + hpos;
--npos;
}
hpos += max(skip[npos], npos - occ[haystack[npos+hpos]]);
}
return NULL;

}

OKAY! I Golfed the algorithm. I just couldn't find an object
oriented way to do it. That means the contest is still open!

bool match()(const string & a, const string & b)
{
int len = a.size();
int mc = len;
int cnt = mc;

while(mc>0){
if(a[mc]==b[cnt]){ mc--; }
else if(mc<len){ mc=len;}
if(cnt==b.size(){ return false; }
cnt++;
}
return true;
}

On Mar 31, 7:44 pm,

This contest is open to everyone who knows C++. To enter all you need
to do is take the Boyer-Moore String Search Algorithm, as it is
written in C, and make the fastest running C++ program you can out of
it. I'm going to try to write code myself, and if you can beet me,
and your code executes faster, then you win a free I-Pod. My I-Pod is
used, but it comes jam packed with songs I've been listening to. So
take a crack at this problem and post your solution to the group. :)

http://en.wikipedia.org/wiki/Boyer-Moore_string_search_algorithm

#include <string.h>
#include <limits.h>

/* This helper function checks, whether the last "portion" bytes
* of "needle" (which is "nlen" bytes long) exist within the "needle"
* at offset "offset" (counted from the end of the string),
* and whether the character preceding "offset" is not a match.
* Notice that the range being checked may reach beyond the
* beginning of the string. Such range is ignored.
*/
static int boyermoore_needlematch
(const unsigned char* needle, size_t nlen, size_t portion, size_t
offset)
{
ssize_t virtual_begin =3D nlen-offset-portion;
ssize_t ignore =3D 0;
if(virtual_begin < 0) { ignore =3D -virtual_begin; virtual_begin =

0; }

if(virtual_begin > 0 && needle[virtual_begin-1] =3D=3D needle[nlen-
portion-1])
return 0;

return
memcmp(needle + nlen - portion + ignore,
needle + virtual_begin,
portion - ignore) =3D=3D 0;

}

static size_t max(ssize_t a, ssize_t b) { return a>b ? a : b; }

/* Returns a pointer to the first occurrence of "needle"
* within "haystack", or NULL if not found.
*/
const unsigned char* memmem_boyermoore
(const unsigned char* haystack, size_t hlen,
const unsigned char* needle, size_t nlen)
{
size_t skip[nlen]; /* Array of shifts with self-substring match
check */
ssize_t occ[UCHAR_MAX+1]; /* Array of last occurrence of each
character */
size_t a, hpos;

if(nlen > hlen || nlen <=3D 0 || !haystack || !needle) return NULL;

/* Preprocess #1: init occ[]*/

/* Initialize the table to default value */
for(a=3D0; a<UCHAR_MAX+1; ++a) occ[a] =3D -1;

/* Then populate it with the analysis of the needle */
/* But ignoring the last letter */
for(a=3D0; a<nlen-1; ++a) occ[needle[a]] =3D a;

/* Preprocess #2: init skip[] */
/* Note: This step could be made a lot faster.
* A simple implementation is shown here. */
for(a=3D0; a<nlen; ++a)
{
size_t value =3D 0;
while(value < nlen && !boyermoore_needlematch(needle, nlen, a,
value))
++value;
skip[nlen-a-1] =3D value;
}

/* Search: */
for(hpos=3D0; hpos <=3D hlen-nlen; )
{
size_t npos=3Dnlen-1;
while(needle[npos] =3D=3D haystack[npos+hpos])
{
if(npos =3D=3D 0) return haystack + hpos;
--npos;
}
hpos +=3D max(skip[npos], npos - occ[haystack[npos+hpos]]);
}
return NULL;

}

Here's an idea. Take that the data file contains binary data, it
certainly does anyway.

; Fastest binary string search algo with
; PPlain and PMMX type of processors
; <c> 2001 by buliaNaza ;
; ;
.data? ;
align 4 ; !!!
skip_table DD 256 Dup(?) ; skip table
; ;
;...............................;
; Usage: esi ->pBuffer ; esi->buffer with bytes to be
searched through
; ebp =3D lenBuffer ; ebp =3Dlength of the buffer
; ebx ->pSrchData ; ebx->pointer to data to be searched
for
; edx =3D lenSrchData ; edx=3Dlength of data to be searched
for
; edi ->pskip_table ; edi->pointer to skip table (must be
aligned)
; call BMCaseSNext ;
;.................................;
.code ;
BMCaseSNext: ;
cmp edx, 4 ; edx =3D length of data to be
searched for
jg Boyer_Moore ;
;... Brute Force Search ..........; for 4 digits or less only!
mov edi, [ebx] ; edi =3D dword of data to be searched
for
mov ecx, 5 ;
sub ecx, edx ;
lea eax, [esi+edx-1] ; eax->new starting address in
pBuffer
shl ecx, 3 ; *8
mov bl, [ebx+edx-1] ; get last byte only
mov bh, bl ; copy in bh
bswap edi ;
shr edi, cl ;
add ebp, esi ; ebp ->end of buffer
and ebx, 0FFFFh ; ebx =3D need the bx word only
mov ecx, ebx ;
mov esi, edx ; esi=3Dedx =3D length of data to be
searched for
shl ecx, 16 ;
test eax, 3 ;
lea ebx, [ebx+ecx] ;
jz Search_2 ;
Unalign_1: ;
cmp eax, ebp ; ebp ->end of buffer
jge Not_found ;
mov cl, [eax] ;
inc eax ;
cmp cl, bl ;
jz Compare_1 ;
Search_1: ;
test eax, 3 ;
jnz Unalign_1 ;
Search_2: ;
cmp eax, ebp ;u ebp ->end of buffer
jge Not_found ;v
mov ecx, [eax] ;u scasb for the last byte from
pSrchData
add eax, 4 ;v
xor ecx, ebx ;u
mov edx, 7EFEFEFFh ;v
add edx, ecx ;u
xor ecx, -1 ;v
xor ecx, edx ;u
mov edx, [eax-4] ;v
and ecx, 81010100h ;u
jz Search_2 ;v
;
cmp dl, bl ;
jz Minus_4 ;
cmp dh, bl ;
jz Minus_3 ;
shr edx, 16 ;
cmp dl, bl ;
jz Minus_2 ;
cmp dh, bl ;
jz Compare_1 ;
jnz Search_2 ;
Minus_2: ;
dec eax ;
jnz Compare_1 ;
Minus_4: ;
sub eax, 3 ;
jnz Compare_1 ;
Minus_3: ;
sub eax, 2 ;
Compare_1: ;
mov edx, edi ;
cmp eax, ebp ; ebp ->end of buffer
jg Not_found ;
cmp esi, 1 ;
jz Found_1 ;
cmp dl, [eax-2] ; eax->pBuffer
jnz Search_1 ;
cmp esi, 2 ;
jz Found_1 ;
cmp dh, [eax-3] ; eax->pBuffer
jnz Search_1 ;
cmp esi, 3 ;
jz Found_1 ;
shr edx, 16 ;
mov cl, [eax-4] ; eax->pBuffer
cmp dl, cl ;
jnz Search_1 ;
Found_1: ;
sub eax, esi ; in eax->pointer to 1st
ret ; occurrence of data found in
pBuffer
;...Boyer Moore Case Sens Next Search...;
Boyer_Moore: ;
add esi, ebp ; esi->pointer to the last byte of
pBuffer
lea ebx, [ebx+edx-1] ; ebx->pointer to the last byte of
pSrchData
neg edx ; edx=3D -lenSrchData
mov ecx, edx ; ecx =3D edx =3D -lenSrchData
add ebp, edx ; sub lenSrchData from lenBuffer
mov eax, 256 ; eax =3D counter
xor ebp, -1 ; not ebp->current negative index
MaxSkipLens: ;
mov [eax*4+edi-4], edx ; filling up the skip_table with -
lenSrchData
mov [eax*4+edi-8], edx ;
mov [eax*4+edi-12], edx ;
mov [eax*4+edi-16], edx ;
mov [eax*4+edi-20], edx ;
mov [eax*4+edi-24], edx ;
mov [eax*4+edi-28], edx ;
mov [eax*4+edi-32], edx ;
mov [eax*4+edi-36], edx ;
mov [eax*4+edi-40], edx ;
mov [eax*4+edi-44], edx ;
mov [eax*4+edi-48], edx ;
mov [eax*4+edi-52], edx ;
mov [eax*4+edi-56], edx ;
mov [eax*4+edi-60], edx ;
mov [eax*4+edi-64], edx ;
mov [eax*4+edi-68], edx ;
mov [eax*4+edi-72], edx ;
mov [eax*4+edi-76], edx ;
mov [eax*4+edi-80], edx ;
mov [eax*4+edi-84], edx ;
mov [eax*4+edi-88], edx ;
mov [eax*4+edi-92], edx ;
mov [eax*4+edi-96], edx ;
mov [eax*4+edi-100], edx ;
mov [eax*4+edi-104], edx ;
mov [eax*4+edi-108], edx ;
mov [eax*4+edi-112], edx ;
mov [eax*4+edi-116], edx ;
mov [eax*4+edi-120], edx ;
mov [eax*4+edi-124], edx ;
mov [eax*4+edi-128], edx ;
sub eax, 32 ;
jne MaxSkipLens ; loop while eax=3D0
SkipLens: ;
mov al, [ecx+ebx+1] ;u filling up with the real negative
offset of
inc ecx ;v every byte from the pSrchData,
starting from
mov [eax*4+edi], ecx ;u the last to the first, at the offset
in
jne SkipLens ;v skip_table equal to the ASCII code of
the
; byte, multiplied by 4
Search: ; the main searching loop-> FAST PART
mov al, [esi+ebp] ;u get a byte from pBuffer ->esi +ebp
mov ecx, edx ;v ecx=3Dedx=3D
...

read more =BB