CODEWITHSUNDEEP
c++sorting
Mazeryt
Mazeryt

Reputation: 915

Heap overflow inside custom sort function

Hi I struggled with simple program that is doing lex sorting on the array of the integers

(full program here: https://pastebin.com/UMqEP62n )

Running sort on the big enough vector of ints causes random numbers appear in the array and then depends on the data causing segfault.

sort(nums.begin(), nums.end(), lex_compare);

Function to compare:

bool lex_compare(const int &a, const int &b) {
    int ap = a, bp = b;
    vector<int> da, db;

    if (ap == 0) da.insert(da.begin(), ap%10);
    while (ap > 0) {
        da.insert(da.begin(), ap%10);
        ap /= 10;
    }
    if (bp == 0) db.insert(db.begin(), bp%10);
    while (bp > 0) {
        db.insert(db.begin(), bp%10);
        bp /= 10;
    }
    size_t size;
    if (da.size() < db.size()) {
        size = da.size();
    } else {
        size = db.size();
    }

    for (size_t i = 0; i < size; ++i)
        if (da[i] > db[i])
            return true;
        else if (da[i] < db[i])
            return false;
        else
            continue;

    if (da.size() > db.size())
        return false;
    else
        return true;
}

Basically when array is too long memory corruption shows up as there is heap buffer overflow. When compiled with address Sanitizer it show that:

==4097==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x6140000001d0 at pc 0x00010aa396fe bp 0x7ffee51c5c50 sp 0x7ffee51c5c48
READ of size 4 at 0x6140000001d0 thread T0
#0 0x10aa396fd in lex_compare(int const&, int const&) main.cpp:8

Which is essentially first line of lex_compare function:

int ap = a, bp = b;

I cannot figure out kind of error here which causing this behavior? Is it due to size of compare function? or do I have some obvious memory read error? I work with clang 4.2.1 but other platforms are also causing same behavior so I presume is something fundamental wrong with sort function.

Upvotes: 7

Views: 2152

Answers (1)

NathanOliver
NathanOliver

Reputation: 180945

Your issue is you violate the compare requirement that the comparison function passed to std::sort is required to follow.

The compare requirement requires that If comp(a,b)==true then comp(b,a)==false but your comparison function does not do this. for example if a = 0 and b = 0 then comp(a, b) brings you to the

if (da.size() > db.size())
    return false;
else
    return true;

part of you comparison function. Since the sizes are equal it returns true. when we flip it and evaluate comp(b, a) we get to the same block and will return true again.

You need to return false when a == b and you don't do that.

Upvotes: 21

Related Questions