[ASAP] Stack corruption

[Peter Schmitz]

Hi,

I'm currently developing an application that includes an implementation of
the well-known Boyer- Moore algorithm. For this, I use the implementation of
Thierry Lecrq from http://www-igm.univ-mlv.fr/~lecroq/string/node14.html.

But unfortunately, this source code (see below) somtimes causes a stack
corruption when I compile and run it.

#define ASIZE 256 //binary
#define MAX(a, b) ((a) > (b) ? (a) : (b))

void preBmBc(char *x, int m, int bmBc[]) {
int i;

for (i = 0; i < ASIZE; ++i)
bmBc[i] = m;
for (i = 0; i < m - 1; ++i)
bmBc[x[i]] = m - i - 1;
}
void suffixes(char *x, int m, int *suff) {
int f, g, i;

suff[m - 1] = m;
g = m - 1;
for (i = m - 2; i >= 0; --i) {
if (i > g && suff[i + m - 1 - f] < i - g)
suff[i] = suff[i + m - 1 - f];
else {
if (i < g)
g = i;
f = i;
while (g >= 0 && x[g] == x[g + m - 1 - f])
--g;
suff[i] = f - g;
}
}
}

void preBmGs(char *x, int m, int *bmGs) {
int i, j;
int *suff = new int[m];

suffixes(x, m, suff);

for (i = 0; i < m; ++i)
bmGs[i] = m;
j = 0;
for (i = m - 1; i >= -1; --i)
if (i == -1 || suff[i] == i + 1)
for (; j < m - 1 - i; ++j)
if (bmGs[j] == m)
bmGs[j] = m - 1 - i;
for (i = 0; i <= m - 2; ++i)
bmGs[m - 1 - suff[i]] = m - 1 - i;
delete suff;
}
BOOL TUNEDBM(char *x, int m, char *y, int n, int &lastpos) {

int i, j;
int *bmBc = new int(ASIZE);
int *bmGs = new int(m);
/* Preprocessing */
preBmGs(x, m, bmGs);
preBmBc(x, m, bmBc);

/* Searching */
j = 0;
while (j <= n - m) {
for (i = m - 1; i >= 0 && x[i] == y[i + j]; --i);
if (i < 0) {
lastpos = j + m;
delete bmGs;
delete bmBc;
return TRUE;
j += bmGs[0];
}
else
j += MAX(bmGs[i], bmBc[y[i + j]] - m + 1 + i);
}
delete bmGs;
delete bmBc;
return FALSE;
}

Does anyone have an idea on what I'm doing wrong? I've done some debugging
and it seems to me that the corruption takes place at the 'preBmGs'- function
- but I might be wrong so better don't rely on it.

Thanks a lot for any help or suggestion

Peter

P.S.: Merry Christmas to everyone!!!

[Tim Robinson]

Peter Schmitz wrote:
[...]

int *bmBc = new int(ASIZE);
int *bmGs = new int(m);
Use [], not ().

[...] delete bmGs;
delete bmBc;

[...]

Use delete[], not delete.

However, these mistakes would cause heap corruption, not stack
corruption. What error message are you seeing?

--
Tim Robinson (MVP, Windows SDK)
http://mobius.sourceforge.net/

[Peter Schmitz]

Thanks for answering. At your advice, I changed my code as follows:

int *bmBc = new int[ASIZE];
int *bmGs = new int[m];
[...]
if (i < 0) {
lastpos = j + m;
delete[] bmGs;
delete[] bmBc;
return TRUE;
[...]
delete[] bmGs;
delete[] bmBc; //Line of Crash
return FALSE;

Unfortunately, the whole algorithm now crashes when I try to delete bmBc.
The debugging shows an error in dbgheap.c at line 1148 (see below).
The original error message I received was a 'Run-Time error #2': Stack
corruption around bmGs.

Any ideas?

Thanks a lot so far
Peter

Extract of dbgheap.c:

/* if we didn't already check entire heap, at least check this
object */
if (!(_crtDbgFlag & _CRTDBG_CHECK_ALWAYS_DF))
{
/* check no-mans-land gaps */
if (!CheckBytes(pHead->gap, _bNoMansLandFill, nNoMansLandSize))
_RPT3(_CRT_ERROR, "DAMAGE: before %hs block (#%d) at 0x%p.\n",
szBlockUseName[_BLOCK_TYPE(pHead->nBlockUse)],
pHead->lRequest,
(BYTE *) pbData(pHead));

if (!CheckBytes(pbData(pHead) + pHead->nDataSize,
_bNoMansLandFill, nNoMansLandSize))
_RPT3(_CRT_ERROR, "DAMAGE: after %hs block (#%d) at 0x%p.\n",
szBlockUseName[_BLOCK_TYPE(pHead->nBlockUse)],
pHead->lRequest,
(BYTE *) pbData(pHead)); //line of crash
}

////////////////////////////////////////////////////////////////////////////////////////

"Tim Robinson" wrote:

Peter Schmitz wrote:
[...]

int *bmBc = new int(ASIZE);
int *bmGs = new int(m);

Use [], not ().

[...]

delete bmGs;
delete bmBc;

[...]

Use delete[], not delete.

However, these mistakes would cause heap corruption, not stack
corruption. What error message are you seeing?

--
Tim Robinson (MVP, Windows SDK)
http://mobius.sourceforge.net/

[Tim Robinson]

Peter Schmitz wrote:
[...]

Unfortunately, the whole algorithm now crashes when I try to delete bmBc.
The debugging shows an error in dbgheap.c at line 1148 (see below).
The original error message I received was a 'Run-Time error #2': Stack
corruption around bmGs.

[...]

If you haven't already done so, download the 'Debugging Tools for
Windows' from the Microsoft web site. Then run gflags.exe, enter the
name of your executable, and enable Page Heap.

Doing this will cause your program to crash the moment it tries to
access unallocated memory, instead of crashing at some point later on.
Remember to disable Page Heap once you are done.

--
Tim Robinson (MVP, Windows SDK)
http://mobius.sourceforge.net/

[Peter Schmitz]

I downloaded the 6.4 version of the debugging tools, ran gflags.exe, chose
'Verifier', entered the name of my process, enabled pageheap and clicked on
OK - unfortunately this does not change anything. The application still
crashes at this certain point.

Any ideas?

Thanks
Peter

"Tim Robinson" wrote:

Peter Schmitz wrote:
[...]

Unfortunately, the whole algorithm now crashes when I try to delete bmBc.
The debugging shows an error in dbgheap.c at line 1148 (see below).
The original error message I received was a 'Run-Time error #2': Stack
corruption around bmGs.

[...]

If you haven't already done so, download the 'Debugging Tools for
Windows' from the Microsoft web site. Then run gflags.exe, enter the
name of your executable, and enable Page Heap.

Doing this will cause your program to crash the moment it tries to
access unallocated memory, instead of crashing at some point later on.
Remember to disable Page Heap once you are done.

--
Tim Robinson (MVP, Windows SDK)
http://mobius.sourceforge.net/

[Alexander Grigoriev]

I'm afraid page heap only works for HeapAlloc functions, not CRT allocation
(especially the debug one, where it reserves some guard space).
It's better just to set in the debugger a data breakpoint at the allocation
end, immediately after allocating the array. This way, the VC debugger will
stop the program.

"Tim Robinson" <ti**********************@nowhere.com> wrote in message
news:32*************@individual.net...

Peter Schmitz wrote:
[...]

Unfortunately, the whole algorithm now crashes when I try to delete bmBc.
The debugging shows an error in dbgheap.c at line 1148 (see below).
The original error message I received was a 'Run-Time error #2': Stack
corruption around bmGs.

[...]

If you haven't already done so, download the 'Debugging Tools for Windows'
from the Microsoft web site. Then run gflags.exe, enter the name of your
executable, and enable Page Heap.

Doing this will cause your program to crash the moment it tries to access
unallocated memory, instead of crashing at some point later on. Remember
to disable Page Heap once you are done.

--
Tim Robinson (MVP, Windows SDK)
http://mobius.sourceforge.net/

[Tim Robinson]

Alexander Grigoriev wrote:

I'm afraid page heap only works for HeapAlloc functions, not CRT allocation
(especially the debug one, where it reserves some guard space).
It's better just to set in the debugger a data breakpoint at the allocation
end, immediately after allocating the array. This way, the VC debugger will
stop the program.

Pageheap works fine for CRT allocations, because unless you have VC++ 5
compatibility turned on, malloc and new go straight to HeapAlloc.

Though you're correct in saying that it works best on Release builds.

--
Tim Robinson (MVP, Windows SDK)
http://mobius.sourceforge.net/

[Peter Schmitz]

Hi again! I've done some deeper debugging and therefore some information to
share:
It seems (!) that the stack corruption only occurs when length of the buffer
to search in is bigger by one (or equal) to the length of the search pattern
(6:5 or 6:6 in my debugging). Can't see an error in the algorithm that
supports this theory, can you?

Thanks so far
Peter

"Peter Schmitz" wrote:

Hi,

I'm currently developing an application that includes an implementation of
the well-known Boyer- Moore algorithm. For this, I use the implementation of
Thierry Lecrq from http://www-igm.univ-mlv.fr/~lecroq/string/node14.html.

But unfortunately, this source code (see below) somtimes causes a stack
corruption when I compile and run it.

#define ASIZE 256 //binary
#define MAX(a, b) ((a) > (b) ? (a) : (b))

void preBmBc(char *x, int m, int bmBc[]) {
int i;

for (i = 0; i < ASIZE; ++i)
bmBc[i] = m;
for (i = 0; i < m - 1; ++i)
bmBc[x[i]] = m - i - 1;
}
void suffixes(char *x, int m, int *suff) {
int f, g, i;

suff[m - 1] = m;
g = m - 1;
for (i = m - 2; i >= 0; --i) {
if (i > g && suff[i + m - 1 - f] < i - g)
suff[i] = suff[i + m - 1 - f];
else {
if (i < g)
g = i;
f = i;
while (g >= 0 && x[g] == x[g + m - 1 - f])
--g;
suff[i] = f - g;
}
}
}

void preBmGs(char *x, int m, int *bmGs) {
int i, j;
int *suff = new int[m];

suffixes(x, m, suff);

for (i = 0; i < m; ++i)
bmGs[i] = m;
j = 0;
for (i = m - 1; i >= -1; --i)
if (i == -1 || suff[i] == i + 1)
for (; j < m - 1 - i; ++j)
if (bmGs[j] == m)
bmGs[j] = m - 1 - i;
for (i = 0; i <= m - 2; ++i)
bmGs[m - 1 - suff[i]] = m - 1 - i;
delete suff;
}
BOOL TUNEDBM(char *x, int m, char *y, int n, int &lastpos) {

int i, j;
int *bmBc = new int(ASIZE);
int *bmGs = new int(m);
/* Preprocessing */
preBmGs(x, m, bmGs);
preBmBc(x, m, bmBc);

/* Searching */
j = 0;
while (j <= n - m) {
for (i = m - 1; i >= 0 && x[i] == y[i + j]; --i);
if (i < 0) {
lastpos = j + m;
delete bmGs;
delete bmBc;
return TRUE;
j += bmGs[0];
}
else
j += MAX(bmGs[i], bmBc[y[i + j]] - m + 1 + i);
}
delete bmGs;
delete bmBc;
return FALSE;
}

Does anyone have an idea on what I'm doing wrong? I've done some debugging
and it seems to me that the corruption takes place at the 'preBmGs'- function
- but I might be wrong so better don't rely on it.

Thanks a lot for any help or suggestion

Peter

P.S.: Merry Christmas to everyone!!!

[Steve Friedl [MVP/Security]]

"Peter Schmitz" <Pe**********@discussions.microsoft.com> wrote in message
news:A9**********************************@microsof t.com...

Any ideas?

How about posting a complete, standalone program with parameters that cause
it to crash. I have some ideas, but I'd like to see the whole thing first.

Please include a main() function with suggested parameters.

Steve
--
Steve Friedl -- Tustin, California USA -- www.unixwiz.net
Unix Wizard -- Microsoft MVP/Security -- I speak for me only

[Ivan Brugiolo [MSFT]]

And, on top of this advice, DO NOT use the debug version of the C-Rutnime.
It adds trailing patterns to the allocations that can delay
the detection of the problem with PageHeap.

--
This posting is provided "AS IS" with no warranties, and confers no rights.
Use of any included script samples are subject to the terms specified at
http://www.microsoft.com/info/cpyright.htm
"Tim Robinson" <ti**********************@nowhere.com> wrote in message
news:32*************@individual.net...

Peter Schmitz wrote:
[...]

Unfortunately, the whole algorithm now crashes when I try to delete bmBc. The debugging shows an error in dbgheap.c at line 1148 (see below).
The original error message I received was a 'Run-Time error #2': Stack
corruption around bmGs.

[...]

If you haven't already done so, download the 'Debugging Tools for
Windows' from the Microsoft web site. Then run gflags.exe, enter the
name of your executable, and enable Page Heap.

Doing this will cause your program to crash the moment it tries to
access unallocated memory, instead of crashing at some point later on.
Remember to disable Page Heap once you are done.

--
Tim Robinson (MVP, Windows SDK)
http://mobius.sourceforge.net/

[Fredrik Wahlgren]

"Peter Schmitz" <Pe**********@discussions.microsoft.com> wrote in message
news:EC**********************************@microsof t.com...

Thanks for answering. At your advice, I changed my code as follows:

int *bmBc = new int[ASIZE];
int *bmGs = new int[m];
[...]
if (i < 0) {
lastpos = j + m;
delete[] bmGs;
delete[] bmBc;
return TRUE;
[...]
delete[] bmGs;
delete[] bmBc; //Line of Crash
return FALSE;

Unfortunately, the whole algorithm now crashes when I try to delete bmBc.
The debugging shows an error in dbgheap.c at line 1148 (see below).
The original error message I received was a 'Run-Time error #2': Stack
corruption around bmGs.

Any ideas?

Thanks a lot so far
Peter

Extract of dbgheap.c:

/* if we didn't already check entire heap, at least check this
object */
if (!(_crtDbgFlag & _CRTDBG_CHECK_ALWAYS_DF))
{
/* check no-mans-land gaps */
if (!CheckBytes(pHead->gap, _bNoMansLandFill, nNoMansLandSize)) _RPT3(_CRT_ERROR, "DAMAGE: before %hs block (#%d) at 0x%p.\n", szBlockUseName[_BLOCK_TYPE(pHead->nBlockUse)],
pHead->lRequest,
(BYTE *) pbData(pHead));

if (!CheckBytes(pbData(pHead) + pHead->nDataSize,
_bNoMansLandFill, nNoMansLandSize))
_RPT3(_CRT_ERROR, "DAMAGE: after %hs block (#%d) at 0x%p.\n", szBlockUseName[_BLOCK_TYPE(pHead->nBlockUse)],
pHead->lRequest,
(BYTE *) pbData(pHead)); //line of crash
}

////////////////////////////////////////////////////////////////////////////
////////////
"Tim Robinson" wrote:

Peter Schmitz wrote:
[...]

int *bmBc = new int(ASIZE);
int *bmGs = new int(m);

Use [], not ().

[...]

delete bmGs;
delete bmBc;

[...]

Use delete[], not delete.

However, these mistakes would cause heap corruption, not stack
corruption. What error message are you seeing?

--
Tim Robinson (MVP, Windows SDK)
http://mobius.sourceforge.net/

Is it possible that you delete bmBc twice? I would suggest that you set bmBC
to NULL immeditely after delete [] bmBc.
In addition, check if bmBC <> NULL before deleting it. What's the value of
ASIZE? I guess there could be a problem if it's zero.

/ Fredrik

[Alexander Grigoriev]

Two approaches:

1. Use data access breakpoint.
2. Put ASSERT before each access, to validate the index against the array
size.

"Peter Schmitz" <Pe**********@discussions.microsoft.com> wrote in message
news:D3**********************************@microsof t.com...

Hi again! I've done some deeper debugging and therefore some information
to
share:
It seems (!) that the stack corruption only occurs when length of the
buffer
to search in is bigger by one (or equal) to the length of the search
pattern
(6:5 or 6:6 in my debugging). Can't see an error in the algorithm that
supports this theory, can you?

Thanks so far
Peter

"Peter Schmitz" wrote:

Hi,

I'm currently developing an application that includes an implementation
of
the well-known Boyer- Moore algorithm. For this, I use the implementation
of
Thierry Lecrq from http://www-igm.univ-mlv.fr/~lecroq/string/node14.html.

But unfortunately, this source code (see below) somtimes causes a stack
corruption when I compile and run it.

#define ASIZE 256 //binary
#define MAX(a, b) ((a) > (b) ? (a) : (b))

void preBmBc(char *x, int m, int bmBc[]) {
int i;

for (i = 0; i < ASIZE; ++i)
bmBc[i] = m;
for (i = 0; i < m - 1; ++i)
bmBc[x[i]] = m - i - 1;
}
void suffixes(char *x, int m, int *suff) {
int f, g, i;

suff[m - 1] = m;
g = m - 1;
for (i = m - 2; i >= 0; --i) {
if (i > g && suff[i + m - 1 - f] < i - g)
suff[i] = suff[i + m - 1 - f];
else {
if (i < g)
g = i;
f = i;
while (g >= 0 && x[g] == x[g + m - 1 - f])
--g;
suff[i] = f - g;
}
}
}

void preBmGs(char *x, int m, int *bmGs) {
int i, j;
int *suff = new int[m];

suffixes(x, m, suff);

for (i = 0; i < m; ++i)
bmGs[i] = m;
j = 0;
for (i = m - 1; i >= -1; --i)
if (i == -1 || suff[i] == i + 1)
for (; j < m - 1 - i; ++j)
if (bmGs[j] == m)
bmGs[j] = m - 1 - i;
for (i = 0; i <= m - 2; ++i)
bmGs[m - 1 - suff[i]] = m - 1 - i;
delete suff;
}
BOOL TUNEDBM(char *x, int m, char *y, int n, int &lastpos) {

int i, j;
int *bmBc = new int(ASIZE);
int *bmGs = new int(m);
/* Preprocessing */
preBmGs(x, m, bmGs);
preBmBc(x, m, bmBc);

/* Searching */
j = 0;
while (j <= n - m) {
for (i = m - 1; i >= 0 && x[i] == y[i + j]; --i);
if (i < 0) {
lastpos = j + m;
delete bmGs;
delete bmBc;
return TRUE;
j += bmGs[0];
}
else
j += MAX(bmGs[i], bmBc[y[i + j]] - m + 1 + i);
}
delete bmGs;
delete bmBc;
return FALSE;
}

Does anyone have an idea on what I'm doing wrong? I've done some
debugging
and it seems to me that the corruption takes place at the 'preBmGs'-
function
- but I might be wrong so better don't rely on it.

Thanks a lot for any help or suggestion

Peter

P.S.: Merry Christmas to everyone!!!

[Mete Ciragan]

You write (which allocates 1 int and initializes with ASIZE/m):
int *bmBc = new int(ASIZE);
int *bmGs = new int(m);

instead of (allocates ASIZE/m ints, unitialized):
int *bmBc = new int[ASIZE];
int *bmGs = new int[m];

- Mete Ciragan

"Peter Schmitz" <Pe**********@discussions.microsoft.com> schrieb im
Newsbeitrag news:ED**********************************@microsof t.com...

Hi,

I'm currently developing an application that includes an implementation of
the well-known Boyer- Moore algorithm. For this, I use the implementation
of
Thierry Lecrq from http://www-igm.univ-mlv.fr/~lecroq/string/node14.html.

But unfortunately, this source code (see below) somtimes causes a stack
corruption when I compile and run it.

#define ASIZE 256 //binary
#define MAX(a, b) ((a) > (b) ? (a) : (b))

void preBmBc(char *x, int m, int bmBc[]) {
int i;

for (i = 0; i < ASIZE; ++i)
bmBc[i] = m;
for (i = 0; i < m - 1; ++i)
bmBc[x[i]] = m - i - 1;
}
void suffixes(char *x, int m, int *suff) {
int f, g, i;

suff[m - 1] = m;
g = m - 1;
for (i = m - 2; i >= 0; --i) {
if (i > g && suff[i + m - 1 - f] < i - g)
suff[i] = suff[i + m - 1 - f];
else {
if (i < g)
g = i;
f = i;
while (g >= 0 && x[g] == x[g + m - 1 - f])
--g;
suff[i] = f - g;
}
}
}

void preBmGs(char *x, int m, int *bmGs) {
int i, j;
int *suff = new int[m];

suffixes(x, m, suff);

for (i = 0; i < m; ++i)
bmGs[i] = m;
j = 0;
for (i = m - 1; i >= -1; --i)
if (i == -1 || suff[i] == i + 1)
for (; j < m - 1 - i; ++j)
if (bmGs[j] == m)
bmGs[j] = m - 1 - i;
for (i = 0; i <= m - 2; ++i)
bmGs[m - 1 - suff[i]] = m - 1 - i;
delete suff;
}
BOOL TUNEDBM(char *x, int m, char *y, int n, int &lastpos) {

int i, j;
int *bmBc = new int(ASIZE);
int *bmGs = new int(m);
/* Preprocessing */
preBmGs(x, m, bmGs);
preBmBc(x, m, bmBc);

/* Searching */
j = 0;
while (j <= n - m) {
for (i = m - 1; i >= 0 && x[i] == y[i + j]; --i);
if (i < 0) {
lastpos = j + m;
delete bmGs;
delete bmBc;
return TRUE;
j += bmGs[0];
}
else
j += MAX(bmGs[i], bmBc[y[i + j]] - m + 1 + i);
}
delete bmGs;
delete bmBc;
return FALSE;
}

Does anyone have an idea on what I'm doing wrong? I've done some debugging
and it seems to me that the corruption takes place at the 'preBmGs'-
function
- but I might be wrong so better don't rely on it.

Thanks a lot for any help or suggestion

Peter

P.S.: Merry Christmas to everyone!!!

[Pavel Lebedinsky]

You also have mismatched new[]/delete:

int *suff = new int[m];
...
delete suff;
This should be delete[].

"Mete Ciragan" wrote:
You write (which allocates 1 int and initializes with ASIZE/m):
int *bmBc = new int(ASIZE);
int *bmGs = new int(m);

instead of (allocates ASIZE/m ints, unitialized):
int *bmBc = new int[ASIZE];
int *bmGs = new int[m];

I'm currently developing an application that includes an implementation
of
the well-known Boyer- Moore algorithm. For this, I use the implementation
of
Thierry Lecrq from http://www-igm.univ-mlv.fr/~lecroq/string/node14.html.

But unfortunately, this source code (see below) somtimes causes a stack
corruption when I compile and run it.

#define ASIZE 256 //binary
#define MAX(a, b) ((a) > (b) ? (a) : (b))

void preBmBc(char *x, int m, int bmBc[]) {
int i;

for (i = 0; i < ASIZE; ++i)
bmBc[i] = m;
for (i = 0; i < m - 1; ++i)
bmBc[x[i]] = m - i - 1;
}
void suffixes(char *x, int m, int *suff) {
int f, g, i;

suff[m - 1] = m;
g = m - 1;
for (i = m - 2; i >= 0; --i) {
if (i > g && suff[i + m - 1 - f] < i - g)
suff[i] = suff[i + m - 1 - f];
else {
if (i < g)
g = i;
f = i;
while (g >= 0 && x[g] == x[g + m - 1 - f])
--g;
suff[i] = f - g;
}
}
}

void preBmGs(char *x, int m, int *bmGs) {
int i, j;
int *suff = new int[m];

suffixes(x, m, suff);

for (i = 0; i < m; ++i)
bmGs[i] = m;
j = 0;
for (i = m - 1; i >= -1; --i)
if (i == -1 || suff[i] == i + 1)
for (; j < m - 1 - i; ++j)
if (bmGs[j] == m)
bmGs[j] = m - 1 - i;
for (i = 0; i <= m - 2; ++i)
bmGs[m - 1 - suff[i]] = m - 1 - i;
delete suff;
}
BOOL TUNEDBM(char *x, int m, char *y, int n, int &lastpos) {

int i, j;
int *bmBc = new int(ASIZE);
int *bmGs = new int(m);
/* Preprocessing */
preBmGs(x, m, bmGs);
preBmBc(x, m, bmBc);

/* Searching */
j = 0;
while (j <= n - m) {
for (i = m - 1; i >= 0 && x[i] == y[i + j]; --i);
if (i < 0) {
lastpos = j + m;
delete bmGs;
delete bmBc;
return TRUE;
j += bmGs[0];
}
else
j += MAX(bmGs[i], bmBc[y[i + j]] - m + 1 + i);
}
delete bmGs;
delete bmBc;
return FALSE;
}

[Stu Smith]

Looks like code from the school of "the shorter my variable names the faster
my code will run".

Rewrite it! It's horrible write-only code. Use vectors and strings instead
of arrays and char pointers.

Stu
"Peter Schmitz" <Pe**********@discussions.microsoft.com> wrote in message
news:ED**********************************@microsof t.com...

Hi,

I'm currently developing an application that includes an implementation of
the well-known Boyer- Moore algorithm. For this, I use the implementation of Thierry Lecrq from http://www-igm.univ-mlv.fr/~lecroq/string/node14.html.

But unfortunately, this source code (see below) somtimes causes a stack
corruption when I compile and run it.

#define ASIZE 256 //binary
#define MAX(a, b) ((a) > (b) ? (a) : (b))

void preBmBc(char *x, int m, int bmBc[]) {
int i;

for (i = 0; i < ASIZE; ++i)
bmBc[i] = m;
for (i = 0; i < m - 1; ++i)
bmBc[x[i]] = m - i - 1;
}
void suffixes(char *x, int m, int *suff) {
int f, g, i;

suff[m - 1] = m;
g = m - 1;
for (i = m - 2; i >= 0; --i) {
if (i > g && suff[i + m - 1 - f] < i - g)
suff[i] = suff[i + m - 1 - f];
else {
if (i < g)
g = i;
f = i;
while (g >= 0 && x[g] == x[g + m - 1 - f])
--g;
suff[i] = f - g;
}
}
}

void preBmGs(char *x, int m, int *bmGs) {
int i, j;
int *suff = new int[m];

suffixes(x, m, suff);

for (i = 0; i < m; ++i)
bmGs[i] = m;
j = 0;
for (i = m - 1; i >= -1; --i)
if (i == -1 || suff[i] == i + 1)
for (; j < m - 1 - i; ++j)
if (bmGs[j] == m)
bmGs[j] = m - 1 - i;
for (i = 0; i <= m - 2; ++i)
bmGs[m - 1 - suff[i]] = m - 1 - i;
delete suff;
}
BOOL TUNEDBM(char *x, int m, char *y, int n, int &lastpos) {

int i, j;
int *bmBc = new int(ASIZE);
int *bmGs = new int(m);
/* Preprocessing */
preBmGs(x, m, bmGs);
preBmBc(x, m, bmBc);

/* Searching */
j = 0;
while (j <= n - m) {
for (i = m - 1; i >= 0 && x[i] == y[i + j]; --i);
if (i < 0) {
lastpos = j + m;
delete bmGs;
delete bmBc;
return TRUE;
j += bmGs[0];
}
else
j += MAX(bmGs[i], bmBc[y[i + j]] - m + 1 + i);
}
delete bmGs;
delete bmBc;
return FALSE;
}

Does anyone have an idea on what I'm doing wrong? I've done some debugging
and it seems to me that the corruption takes place at the 'preBmGs'- function - but I might be wrong so better don't rely on it.

Thanks a lot for any help or suggestion

Peter

P.S.: Merry Christmas to everyone!!!