Frustrating bug in C++ program

[mike3]

Hi.

I was writing a program in C++ that generates fractals. I got this
weird bug though right now that's holding it up and was wondering if
you could help.

Anyway, it seems that when this code is executed, it corrupts the
memory causing a crash later on (the program actually causes an
"access violation" error in Windows, which the program is running
under):

*WindowXStep_W /= (*Mag_W * (u32)2);
*WindowYStep_W /= (*Mag_W * (u32)2);

Here "WindowXStep_W", "Mag_W" are of a custom type called "BigFloat"
that contains a bignum implementation, with overloaded operators. I've
looked over all the calculation routines and can't find any reason
they would corrupt the memory. It seems to have something to do with
the use of operators that take two operands and then output one --
things like the multiplication above. When the code is changed to

*WindowXStep_W /= *Mag_W ;
*WindowYStep_W /= *Mag_W;
*WindowXStep_W /= (u32)2;
*WindowYStep_W /= (u32)2;

or even

*Mag_W *= (u32)2;
*WindowXStep_W /= *Mag_W;
*WindowYStep_W /= *Mag_W;

(which of cours secrews up Mag_W's value, but the change is for
debugging this specific problem.)

there's no problem. Similar problems seem to occur with any use of
operators that return a "BigFloat", like "*", "+", and "-", and not
"const BigFloat &" operators like "/=" and "*=" above. I even
"debased" them to remove the calculation guts and leave just "return
BigFloat(...)" at the end and still it crashes. I checked through
"EquateBF" which equates one BigFloat to another, and couldn't find
anyhting that would create a memory overflow or something.

Here's a few code snippets in case they might help:

/* Construct a BigFloat that is a copy of another. */
BigFloat::BigFloat(const BigFloat & bfValue)
{
FG3DError err;

/* Initialize */
err = this->Init(bfValue.length);
if(err.dwErrCode != FG3D_SUCCESS)
throw Exception(err);

/* Set to BigFloat */
err = this->EquateBF(&bfValue);
if(err.dwErrCode != FG3D_SUCCESS)
throw Exception(err);

/* Done! */
return;
}

(note: "u32" = "unsigned long")

BigFloat operator*(const BigFloat &a, u32 b)
{
FG3DError err;
BigFloat tmp = BigFloat((BOOL)FALSE, a.length);

/* Mul */
err = FG3DMPFloat_MulSmallU(&tmp, &a, b);
if(err.dwErrCode != FG3D_SUCCESS)
throw Exception(err);

/* Return result */
return(tmp);
}

/* Division operator: /= */
const BigFloat & BigFloat:perator/=(const BigFloat &a)
{
FG3DError err;

/* Div */
err = FG3DMPFloat_Div(this, this, &a);
if(err.dwErrCode != FG3D_SUCCESS)
throw Exception(err);

/* Return result */
return(*this);
}

 

[tony_in_da_uk]

*WindowXStep_W /= (*Mag_W * (u32)2);
*WindowYStep_W /= (*Mag_W * (u32)2);

Here "WindowXStep_W", "Mag_W" are of a custom type called "BigFloat"
that contains a bignum implementation, with overloaded operators. I've

Are they BigFloats, or BigFloat*s? If they really are BigFloats, then
please post the unary BigFloat:perator*() if any....

Tony

 

[Frank Birbacher]

Hi!

/* Construct a BigFloat that is a copy of another. */
BigFloat::BigFloat(const BigFloat & bfValue)
{ [snip]
}

Do you also have a custom operator = ?

BigFloat operator*(const BigFloat &a, u32 b)
{
FG3DError err;
BigFloat tmp = BigFloat((BOOL)FALSE, a.length);

/* Mul */
err = FG3DMPFloat_MulSmallU(&tmp, &a, b);
if(err.dwErrCode != FG3D_SUCCESS)
throw Exception(err);

/* Return result */
return(tmp);
}

There is a canonical implementation of binary operators which reuses the
other code:

BigFloat operator* (BigFloat tmp, u32 const b)
{
tmp *= b; //modify a copy
return tmp; //return
}

Also see here for automatic generation of operators:
http://www.boost.org/libs/utility/operators.htm

Frank

 

[mike3]

Hi!

/* Construct a BigFloat that is a copy of another. */
BigFloat::BigFloat(const BigFloat & bfValue)
{ [snip]
}

Do you also have a custom operator = ?

Yes there is:

/* Assignment operator: = */
BigFloat & BigFloat:perator=(const BigFloat & a)
{
/* Equate */
FG3DError err = this->EquateBF(&a);
if(err.dwErrCode != FG3D_SUCCESS) throw Exception(err);
return(*this);
}

EquateBF method is defined as (The "FG3DRawInt"
routines operate on the raw string of "digits".
Here "DIGIT32" = "unsigned long"):

/* Equate a BigFloat to another. */
FG3DError BigFloat::EquateBF(const BigFloat *x)
{
DIGIT32 carry;

/* Safety */
if(digits == NULL)
return(FG3DError(FG3D_MP_UNINITIALIZED, (DWORD)this));
if(x->digits == NULL)
return(FG3DError(FG3D_MP_UNINITIALIZED, (DWORD)x));


/* Equate fields */
sign = x->sign;
exp = x->exp;
err = x->err;

/* Equate digits */
if(length >= x->length)
{
FG3DRawInt_Copy(digits+(length-x->length), x->digits, x-

length);

FG3DRawInt_Zeroize(digits, length-x->length);
} else {
/* Round off excess digits */
carry = FG3DRawInt_CopyRounded(digits, x->digits, length, x-

length);

if(carry)
{
if(exp == MAX_EXP)
{
/* Zounds! Overflow! */
err = 1;
return(FG3DError(FG3D_MP_OVERFLOW, (DWORD)this));
}

/* Shift in carry */
FG3DRawInt_Rsh(digits, digits, 1, length);
digits[length-1] |= MSBMask;
exp++;
}
}

/* Done! */
return(FG3DError(FG3D_SUCCESS));
}

There is a canonical implementation of binary operators which reuses the
other code:

BigFloat operator* (BigFloat tmp, u32 const b)
{
tmp *= b; //modify a copy
return tmp; //return

}

I tried it, thing still fails. It seems to
happen with operators that return "BigFloat"
and not "const BigFloat &".

 

[mike3]

Are they BigFloats, or BigFloat*s? If they really are BigFloats, then
please post the unary BigFloat:perator*() if any....

Tony

"*xxxx" means the BigFloat pointed at by the pointer
xxxx. These BigFloats are stored in something called
a "FractalMaker" that it used to generate the fractal
images. It has a list of pointers to BigFloats that
are created by it's constructor (using "XXXX = new
BigFloat(...)" for the pointer XXXX), and that hold
coordinates, etc. for the fractal.

 

[Frank Birbacher]

Hi!

I tried it, thing still fails. It seems to
happen with operators that return "BigFloat"
and not "const BigFloat &".

It seems there is something wrong with your copy constructor. But your
code is to complex for manual analysis. Can you possibly cut your code
down to a little working example which shows the error? Maybe drop all
but one operator (i.e. +) and all sourrounding code?

Frank

 

[Frank Birbacher]

Hi!

These BigFloats are stored in something called
a "FractalMaker" that it used to generate the fractal
images. It has a list of pointers to BigFloats that
are created by it's constructor (using "XXXX = new
BigFloat(...)" for the pointer XXXX), and that hold
coordinates, etc. for the fractal.

Is there a reason to use "new"? Why are the BigFloats not just ordinary
members of "FractalMaker"? Or at least managed by a container?

Frank

 

[r]

Hi.

I was writing a program in C++ that generates fractals. I got this
weird bug though right now that's holding it up and was wondering if
you could help.

Anyway, it seems that when this code is executed, it corrupts the
memory causing a crash later on (the program actually causes an
"access violation" error in Windows, which the program is running
under):

Sorry, I can't tell what the problem is with your code. But the way
to handle access violations is run the code under a debugger, make it
crash, then go through the call stack looking for the stray pointer.

 

[mike3]

Hi!


Is there a reason to use "new"? Why are the BigFloats not just ordinary
members of "FractalMaker"? Or at least managed by a container?

Frank

I set up a class that would test this method:

class Tester {
private:
BigFloat a;
public:
Tester();
~Tester();
};

Tester::Tester()
{
a = BigFloat((u32)4, 16); /* construct 512-bit BigFloat
* set to the value +4.
*/
}

Tester::~Tester()
{
delete &a;
}


When a "Tester" is created the default BigFloat
constructor though is called FIRST which constructs
a BigFloat with 64 bits and a value of zero. The
statement in Tester::Tester() above then
assigns it the value of a TEMPORARY BigFloat with
value 4 and 512 bits of precision as best as
it can, which means we LOSE 448 bits of precision!
Yikes!

 

[mike3]

Hi!


It seems there is something wrong with your copy constructor. But your
code is to complex for manual analysis. Can you possibly cut your code
down to a little working example which shows the error? Maybe drop all
but one operator (i.e. +) and all sourrounding code?

Frank

See the thing is though that the problem
only became evident when it was used in a complex
program. But not using the offending area of code
seems to cause the problem to disappear. But I
can't just not use the code and I want the thing
to work.

 

[Jim Langston]

See the thing is though that the problem
only became evident when it was used in a complex
program. But not using the offending area of code
seems to cause the problem to disappear. But I
can't just not use the code and I want the thing
to work.

Copy your program to a new program. Start reducing the size trying to get it
to compile in a small a size as possible still showing the bug. Removing
things from the class that shouldn't be necessary to show the bug etc...

Either you'll reduce the program to something small enough to show us, or
you'll remove something and the program will stop working or the bug will go
away. At this point it might come up, "Oh, THAT'S why it's happening!"

 

[Frank Birbacher]

Hi!

I set up a class that would test this method:

class Tester {
private:
BigFloat a;
public:
Tester();
~Tester();
};

I replaced your ctor:

Tester::Tester()
: a((u32)4, 16) //construct "a"
{}

This construct is called "initialization list". You can list all members
and base classes separated by comma and make calls to their
constructors. This way you can even create "const" members.

Tester::~Tester()
{
delete &a;
}

Yikes! There is no "new", thus there MUST NOT be a "delete".

which means we LOSE 448 bits of precision!

Just because you didn't use ctors properly. So now we made your class a
lot safer. Good, isn't it?

Frank

 

[mike3]

Hi!



I replaced your ctor:

Tester::Tester()
: a((u32)4, 16) //construct "a"
{}

This construct is called "initialization list". You can list all members
and base classes separated by comma and make calls to their
constructors. This way you can even create "const" members.


Yikes! There is no "new", thus there MUST NOT be a "delete".

<laughing and giggling>

No, I don't have a new. I DO have deletes though in FractalMaker
since there ARE news. I left that in since I had a "Tester"
with a new originally, but forgot to pull out the delete when
I removed the new.

Just because you didn't use ctors properly. So now we made your class a
lot safer. Good, isn't it?

I'll go and do that in the FractalMaker and see if my problem
goes away.

Oops, it's still there. (The problem, that is.) DARNIT.

 

[mike3]

Copy your program to a new program. Start reducing the size trying to get it
to compile in a small a size as possible still showing the bug. Removing
things from the class that shouldn't be necessary to show the bug etc...

Either you'll reduce the program to something small enough to show us, or
you'll remove something and the program will stop working or the bug will go
away. At this point it might come up, "Oh, THAT'S why it's happening!"

I've tried using debugger output functions to display messages that
wouldt
tell me what gets called, etc. before the crash and isolated it to
something
that uses memory (go figure), but it only fails when BigFloats are
used.
And that's where I'm stumped. Is the bug in BigFloat, or this? It's
this
peculiar interaction between BigFloat and this other thing that
doesn't make
any sense. None of them are supposed to overflow. And it's only when
"BigFloat"-returning operators get used in that thing I showed.

This is so strange.

 

[Jim Langston]

I've tried using debugger output functions to display messages that
wouldt
tell me what gets called, etc. before the crash and isolated it to
something
that uses memory (go figure), but it only fails when BigFloats are
used.
And that's where I'm stumped. Is the bug in BigFloat, or this? It's
this
peculiar interaction between BigFloat and this other thing that
doesn't make
any sense. None of them are supposed to overflow. And it's only when
"BigFloat"-returning operators get used in that thing I showed.

This is so strange.

It sounds like BigFloats may be overflowing some buffer somewhere and
screwing up the memory. Can you post the entire BigFloat class?

 

[mike3]

It sounds like BigFloats may be overflowing some buffer somewhere and
screwing up the memory. Can you post the entire BigFloat class?

It's not a simple thing -- over 5700 lines of code. This is
because it contains several implementations of the
arithmetic algorithms, some of which are trimmed-down versions
that are used in more time-critical areas of the program (ie.
fewer branch points, etc.). For example there's a "small integer"
multiply/divide that allows for easier multiplication/division
of BigFloats by small integers. I don't have a "small integer"
add/subtract yet since I haven't needed that operation in any
time-critical area and hence just fake it by constructing a
temporary BigFloat that is equal in value to a small integer.
There are also "fast" add/sub/mul routines that assume equal-sized
operands, for example, and hence don't do any resizing or
pointer gymnastics (hence reducing branch points/"if"s) and have
various optimizations (for instance the "fast add" and "fast sub"
routines use a loop that contains a bit shift and an add/sub
merged into one.).

 

[mike3]

It's not a simple thing -- over 5700 lines of code. This is
because it contains several implementations of the
arithmetic algorithms, some of which are trimmed-down versions
that are used in more time-critical areas of the program (ie.
fewer branch points, etc.). For example there's a "small integer"
multiply/divide that allows for easier multiplication/division
of BigFloats by small integers. I don't have a "small integer"
add/subtract yet since I haven't needed that operation in any
time-critical area and hence just fake it by constructing a
temporary BigFloat that is equal in value to a small integer.
There are also "fast" add/sub/mul routines that assume equal-sized
operands, for example, and hence don't do any resizing or
pointer gymnastics (hence reducing branch points/"if"s) and have
various optimizations (for instance the "fast add" and "fast sub"
routines use a loop that contains a bit shift and an add/sub
merged into one.).

Any response? Do you still want to see it?

 

[Jim Langston]

Any response? Do you still want to see it?

Well, I'm not a mind reader. I can't help to find a bug in something I
can't see.

Without seeing the code all I can say is, look for a buffer overrun or
something similar.

If you need more help than that then, yes, we will need to see the code.

 

[Frank Birbacher]

Hi!

Any response? Do you still want to see it?

Maybe start with some small pieces:

What are the attributes of class BigFloat. What does BigFloat::Init do?
Does BigFloat have a default ctor?

Frank

 

[mike3]

Well, I'm not a mind reader. I can't help to find a bug in something I
can't see.

Without seeing the code all I can say is, look for a buffer overrun or
something similar.

If you need more help than that then, yes, we will need to see the code.

Alright, I've got it zipped. The whole BigFloat implementation.
Where should I send it?