Big number implementation - access violation reading location

[krego]

Hello guys,

I'm working on implementation on big integer and meanwhile i found an error in my code which gives me sleepless nights because I'm not really sure what is happening there.

Here are relevant parts of code:

Header:

class BigNum {
private:
	const int BASE = 10;
	const char CHAR_TO_INT = '0';
	const int NEGATIVE = -1;
	const int POSITIVE = 1;
	const int SIGN_SIZE = 1;
	char *value;
	int size;
	int sign;
        void carry_multiplication(const BigNum&, const BigNum&);
public:
        BigNum(int=0);
        BigNum operator * (const BigNum&);
        BigNum operator *= (const BigNum&);
}

Cpp file:

BigNum::BigNum(const BigNum& big_num) {
	size = big_num.size;
	sign = big_num.sign;
	value = new char[size+1];
	strcpy(value, big_num.value);
}

BigNum::~BigNum() {
	delete[] value;
	value = 0;
	size = 0;
}

BigNum BigNum::operator = (const BigNum& big_num) {
	if (*this != big_num) {
		delete[] value;
		size = big_num.size;
		sign = big_num.sign;
		value = new char[size + 1];
		strcpy(value, big_num.value);
	}
	return *this;
}

BigNum BigNum::operator* (const BigNum& big_num) {
	BigNum *longer = ((*this).size > big_num.size) ? new BigNum(*this) : new BigNum(big_num);
	BigNum *shorter = (*this == *longer) ? new BigNum(big_num) : new BigNum(*this);
	BigNum *result = new BigNum();
	result->initialize_value(longer->size);
	result->carry_multiplication(*longer, *shorter);
	result->size = strlen(result->value);
	result->set_sign(longer->sign*shorter->sign);
	delete longer;
	delete shorter;
	return *result;
}

void BigNum::initialize_value(int arr_len) {
	size = arr_len;
	value = new char[size + 1];
	std::fill_n(value, size + 1, '0');
	value[size] = '\0';
}

BigNum::BigNum(int num) {
	set_sign(num);
	num = abs(num);
	size = get_int_size(num);
	value = new char[size + 1];
	num_to_char_array(num);
}

int my_atoi(char c) { return c - CHAR_TO_INT; };

void BigNum::carry_multiplication(const BigNum& longer, const BigNum& shorter) {
	int carry = 0;
	int row = 0;
	for (int i = shorter.size - 1; i >= 0; i--) {
		if (row > 0) {
			extend_value();
		}
		for (int y = longer.size - 1; y >= 0; y--) {
			int sum = my_atoi(longer.value[y]) * my_atoi(shorter.value[i]);
			if (carry != 0) {
				sum += carry;
			}
			carry = 0;
			int temp = value[y] - CHAR_TO_INT + sum;
			int val = temp % BASE;
			value[y] = val + CHAR_TO_INT;
			carry = sum / BASE;
		}
		row += 1;
	}
	if (carry != 0) {
		extend_value();
		value[0] = carry + CHAR_TO_INT;
	}
}

The error occurs when I try to use operator =*, sometimes I get "access violation reading location" and sometimes it compiles, but then when i try to quit the program it crashes. I'm sure it's about memory but I'm clueless where the bug can be hiding, I'm not returning anything from the heap nor deleting something which i'm using later and the algorithm works fine. Any help on this would be greatly appreciated! Thank you.

[Chervil]

Here are relevant parts of code:

There doesn't appear to be enough there to compile at all. Ideally there would be runnable code which demonstrates the problem.

[ne555]

> Here are relevant parts of code:
¿and the client code?
you also call some functions and don't provide their definition (like extend_value())

provide enough code to reproduce your problem.
We should be able to compile your program. If it has more than one file, upload them to github.


> BigNum *result = new BigNum();
there is no good reason to do that.

[krego]

You're right, here is full version on github: https://github.com/kregoslup/BigNum
It crashes on line 30 in main.cpp

[ne555]

$ valgrind ./a.out
==13109== Memcheck, a memory error detector
==13109== Copyright (C) 2002-2015, and GNU GPL'd, by Julian Seward et al.
==13109== Using Valgrind-3.12.0 and LibVEX; rerun with -h for copyright info
==13109== Command: ./a.out
==13109== 
==13109== Invalid write of size 1
==13109==    at 0x4C2DCA7: strcpy (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==13109==    by 0x401D72: BigNum::equals_operation(BigNum const&) (BigNum.cpp:226)
==13109==    by 0x401EDC: BigNum::operator+=(BigNum const&) (BigNum.cpp:245)
==13109==    by 0x402C9A: main (main.cpp:24)

l1 += 23; //main:24

BigNum BigNum::operator+= (const BigNum& big_num) {
	BigNum result = *this + big_num;
	equals_operation(result); //BigNum:245
	return *this;
}

void BigNum::equals_operation(const BigNum& result) {
	strcpy(value, result.value); //BigNum:226
	size = result.size;
	sign = result.sign;
}

If you check the variables there

(gdb) print *this
$1 = {
  BASE = 10,
  CHAR_TO_INT = 48 '0',
  NEGATIVE = -1,
  POSITIVE = 1,
  SIGN_SIZE = 1,
  value = 0x616c20 "9999",
  size = 4,
  sign = 1
}

(gdb) print result
$2 = (const BigNum &) @0x7fffffffdb80: {
  BASE = 10,
  CHAR_TO_INT = 48 '0',
  NEGATIVE = -1,
  POSITIVE = 1,
  SIGN_SIZE = 1,
  value = 0x617620 "10022",
  size = 5,
  sign = 1
}

notice how the `size' is too small, so out-of-bounds access.
¿what's the point of this `equals_operation()'? ¿why don't just use the copy constructor?

[krego]

Does the operator += (and *=, -=, /=) need to return *this? Do you mean use copy contructor like this:

BigNum result = *this + big_num;
*this = result;
return *this;

OK I fixed that and i can see no more errors on valgrind. Thank you. What have you meant by saying "

BigNum *result = new BigNum();

there is no good reason to do that." ? Is it better not to initialize result there yet?

[ne555]

> Does the operator += (and *=, -=, /=) need to return *this?
yes, that's expected.

> *this = result;
yes, that. Use the assignment operator (sorry, my bad)


About the dynamic allocation http://www.cplusplus.com/forum/general/138037/
you are leaking memory there
may simply do BigNum result;
`longer' and `shorter' are equally bad.