# Re: [ASAP] Stack corruption

From: Mete Ciragan (a_at_b.c)
Date: 12/21/04

```Date: Tue, 21 Dec 2004 13:53:43 +0100

```

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" <PeterSchmitz@discussions.microsoft.com> schrieb im
Newsbeitrag news:ED6C468E-5259-49E5-951B-35F1EDFF5024@microsoft.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!!!

## Relevant Pages

• Re: [ASAP] Stack corruption
... > int f, g, i; ... > suffixes(x, m, suff); ... > preBmGs(x, m, bmGs); ... > preBmBc(x, m, bmBc); ...
(microsoft.public.dotnet.languages.vc)
• Re: [ASAP] Stack corruption
... > int f, g, i; ... > suffixes(x, m, suff); ... > preBmGs(x, m, bmGs); ... > preBmBc(x, m, bmBc); ...
(microsoft.public.vc.language)
• Re: [ASAP] Stack corruption
... > int f, g, i; ... > suffixes(x, m, suff); ... > preBmGs(x, m, bmGs); ... > preBmBc(x, m, bmBc); ...
(microsoft.public.win32.programmer.kernel)
• Re: [ASAP] Stack corruption
... > int f, g, i; ... > suffixes(x, m, suff); ... > preBmGs(x, m, bmGs); ... > preBmBc(x, m, bmBc); ...
(microsoft.public.vc.mfc)
• Re: [ASAP] Stack corruption
... You write (which allocates 1 int and initializes with ASIZE/m): ... instead of (allocates ASIZE/m ints, ... > preBmGs(x, m, bmGs); ... > preBmBc(x, m, bmBc); ...
(microsoft.public.vc.mfc)