CODEWITHSUNDEEP
c++stringc++11memory-managementdynamic-memory-allocation
antimatter96
antimatter96

Reputation: 3

Getting bad_alloc on specific inputs while using C++ strings

I am trying to create a basic program to implement Hamming code for my networking class

The program runs correctly for most cases but there are some specific cases where it breaks with -1073741819

The program takes a string of '0's and '1's as input

When the input string is of length of the form odd number ^ 2 an error occurs giving -1073741819 std::bad_alloc

All other cases seem to work
example input of 8 works, 10 works but of 9 doesn't work.
Similarly input of length 24 works, 26 works but 25 doesn't

Below is the code
It includes some code which does not give an error and I have marked when the irrelevant part starts. 

#include<iostream>
#include<cmath>
#include<vector>

using namespace std;

int main(){

string data;
cout<<"Enter data to send => :\n";
cin>>data;

int len = data.length();
int maxPowerOfTwo = log2(len-1) + 1;
int totalLength = len +  maxPowerOfTwo + 1;

vector< int > toSend;
toSend.reserve(totalLength);
toSend[0] = 0;

int l = 0;
int k = 0;

for(int i=0;i<totalLength+1;i++){
    if(l==i){
        toSend[i] = 0;
        if(l==0){
            l++;
        }
        else{
            l*=2;
        }
    }
    else{
        toSend[i] = data[k]-48;
        k++;
    }
}

int currentPower = 0;
int startPosition = 1;

for(;currentPower<maxPowerOfTwo+1;currentPower++){
    int tempSum = 0;
    int tempCounter = 0;
    for(int currentPosition = startPosition;currentPosition<totalLength+1;){
        tempSum = tempSum + toSend[currentPosition];
        tempCounter++;
        if(tempCounter==startPosition){
            currentPosition += startPosition + 1;
            tempCounter = 0;
        }
        else{
            currentPosition++;
        }
    }
    if(tempSum%2!=0){
        toSend[startPosition] = 1;
    }
    else{
        toSend[startPosition] = 0;
    }
    startPosition*=2;
}
string finaltoSend;

for(int i=1;i<=totalLength;i++){ // MARKED LOOP
    if(toSend[i]==0){
        finaltoSend.push_back('0');
    }
    else{
        finaltoSend.push_back('1');
    }
}

/*
==== NOT RELEVANT ====

cout<<"\nData to send => "<<finaltoSend<<'\n';
string received = finaltoSend;
cout<<"\nEnter data received of length "<<totalLength<<'\n';
cin>>received;
int t_len = received.length();
int t_maxPowerOfTwo = log2(t_len-1);
int t_currentPower = 0;
int t_startPosition = 1;
int errorAt = -1;
for(;t_currentPower<t_maxPowerOfTwo+1;t_currentPower++){
    int tempSum = 0;
    int tempCounter = 0;
    for(int currentPosition = t_startPosition;currentPosition<t_len+1;){
        tempSum = tempSum + received[currentPosition-1] - 48;
        tempCounter++;
        if(tempCounter==t_startPosition){
            currentPosition += t_startPosition + 1;
            tempCounter = 0;
        }
        else{
            currentPosition++;
        }
    }
    if(tempSum%2!=0){
        errorAt+=t_startPosition;
    }
    t_startPosition*=2;
}
if(errorAt == -1){
    cout<<"\nNo error";
}
else{
    errorAt++;
    cout<<"\n\nError at \n\n"<<errorAt;
}

==== END ====
*/

return 0;
}

While debugging with flags and basic debugging (printing where I am)I found that the program breaks in the second iteration of the marked loop

**While debugging new_allocator.h open pointing at void deallocate(pointer __p, size_type){ ::operator delete(__p); } at the end of the program

I have tried finaltoSend.append("0") and also reserving memory before hand but none of the options work

Any hints would be greatly appreciated

Upvotes: 0

Views: 217

Answers (2)

celtschk
celtschk

Reputation: 19721

You've actually got two errors in your code.

The first one is that you only reserve memory for the elements, but don't bring them into existence.

This is unlikely the reason for the behaviour you see (why you are technically writing into unused memory, that memory cannot be used by something else, however it's a latent bug waiting to happen when you further use your vector; also since ints are PODs, they don't require a constructor to call, so you won't see problems due to uninitialized objects, which will change if you use the same wrong approach for vectors of other objects).

To actually bring those ints into existence, use resize instead of reserve.

The second bug is that you go outside even the reserved memory: You reserve space for totalLength elements, but then write totalLength+1 elements. The last element writes beyond the reserved space, and is not unlikely to overwrite actual data used internally for memory management. Which given the error message is most likely what happened.

Note that this is the type of bug that is used by hackers to gain access to computer systems, by figuring out what is beyond that place, and replacing it with malicious stuff by specially crafted input. So consider yourself lucky that your code showed problems right away.

Upvotes: 2

Adrian Colomitchi
Adrian Colomitchi

Reputation: 3992

vector< int > toSend;
toSend.reserve(totalLength);

//...

for(int i=0;i<totalLength+1;i++){
  // Say...what? --------^
  toSend[i] = // different values on the two branches

Writing outside the reserved length?

Try using the 

  toSend.at(i)= // whatever

and see what the app will tell you at runtime. (hint: look at the difference between at and operator [] in respect with bounds check).

(see also why doesn't my program crash when I write past the end of an array? Hint: you can damage your memory and experience crashes much later: see the good-ol' fandango on core).

Upvotes: 4

Related Questions