Simple Trick to Detect Integer Overflow (C/C++)

Getting WA on your submission but can’t figure out why? There are many, many possibilities, but one (which crops up all the time) is Integer Overflow.

There’s a very simple way to see if your submission is triggering one of these: simply add

#pragma GCC optimize "trapv"

to the top of your submission, and instead of silently overflowing an int and giving a WA, your program will crash and give a RE.

For example, the only difference between this WA submission and this RE submission is the use of this pragma.

There’s tons of ways to detect silly mistakes in your code at both runtime and compile-time - have a look at this Codeforces article for more info! _GLIBCXX_DEBUG in particular has helped me uncover tons of errors in other people’s code, though it doesn’t work with C-style arrays - which is yet another reason to use std::vector instead :slight_smile: _GLIBCXX_DEBUG has a big performance impact, though, so make sure you remove it when you’ve finished debugging!

Edit:

Important update: unfortunately, there are cases where this doesn’t work: if a calculation’s result is too big to fit in an int, but that calculation’s result is stored in a long long and then assigned to an int, then the error won’t be detected. Boo.

e.g.

[simon@simon-laptop][09:11:21]
[~/devel/hackerrank/otherpeoples]>cat ftrapv-count-example.cpp 
#pragma GCC optimize "trapv"
#include <iostream>

using namespace std;

int main()
{
    long long x;
    cin >> x;
    int tooSmallToStoreResultIfXIsMoreThan2 = 1'000'000'000;
    // Equivalent to long long temporary = static_cast<long long>(tooSmallToStoreResultIfXIsMoreThan2) * x; 
    // tooSmallToStoreResultIfXIsMoreThan2 = temporary;
    // This is an overflow, but -ftrapv does not detect it, alas.
    tooSmallToStoreResultIfXIsMoreThan2 *= x;
    cout << "x: " << x << " tooSmallToStoreResultIfXIsMoreThan2:" << tooSmallToStoreResultIfXIsMoreThan2 << endl;
}
[simon@simon-laptop][09:11:25]
[~/devel/hackerrank/otherpeoples]>g++ -std=c++17 ftrapv-count-example.cpp  -I ../../shared -O3 -g3 -Wall 
[simon@simon-laptop][09:11:30]
[~/devel/hackerrank/otherpeoples]>echo "3" | ./a.out
x: 3 tooSmallToStoreResultIfXIsMoreThan2:-1294967296
50 Likes

needed something like this since so long , added to my template already :smiley:

5 Likes

Do note that it likely has some performance impact (though I don’t know for sure) so make sure to comment it out after you’ve debugged :slight_smile:

4 Likes

@ssjgz Can you please tell me what is D_GLIBCXX_DEBUG ? :smile:

It’s a compiler flag used to enable debug mode in gcc’s C++ Standard Library implementation. It turns some things that are Undefined Behaviour - out-of-bounds accesses in e.g. std::vector, etc - into guaranteed runtime-errors.

You can enable it in a couple of ways - if you’re compiling locally, use e.g.

g++ -std=c++14 my-solution.cpp -O3 -g3  -D_GLIBCXX_DEBUG

or by adding

#define _GLIBCXX_DEBUG

at the top of your cpp file, before any #includes.

For example, the following code has an out-of-bounds access, but actually runs “fine” on my laptop (i.e. it doesn’t crash):

#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
   vector<pair<int, char>>  v;
   v.push_back ( { 6 , 'K' } ) ;
   v.push_back ( { 3 , 'T' } ) ;
   v.push_back ( { 6 , 'J' } ) ;
   sort ( v.begin() , v.end() ) ;

   for (const auto& pair : v)
   {
       cout << "(" << pair.first << " " << pair.second << ")";
   }
   cout << endl;

   cout << v[4].first << endl;  // Uh-oh - out-of-bounds access - almost certainly wrong!
}

Adding the #define at the top causes it to crash appropriately at runtime:

#define _GLIBCXX_DEBUG
#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
   vector<pair<int, char>>  v;
   v.push_back ( { 6 , 'K' } ) ;
   v.push_back ( { 3 , 'T' } ) ;
   v.push_back ( { 6 , 'J' } ) ;
   sort ( v.begin() , v.end() ) ;

   for (const auto& pair : v)
   {
       cout << "(" << pair.first << " " << pair.second << ")";
   }
   cout << endl;

   cout << v[4].first << endl;  // Uh-oh - out-of-bounds access - almost certainly wrong!
}
/usr/include/c++/7/debug/vector:417:
Error: attempt to subscript container with out-of-bounds index 4, but 
container only holds 3 elements.

Objects involved in the operation:
    sequence "this" @ 0x0x7ffcb7929500 {
      type = std::__debug::vector<std::pair<int, char>, std::allocator<std::pair<int, char> > >;
    }
5 Likes

Will it work in C ?

1 Like

I don’t think it has any effect in C - at least, I can’t think of any errors it could detect.

2 Likes

Thank for clearing my doubt :smile:

1 Like

Do you mind sharing your template code for debugging ?
Also if possible, please shift all flags from command line to #define. It might be helpful to many. :smile:

3 Likes

I don’t really have one for debugging, but I’ve quickly shoved those two #defines into my existing one (untested!)

2 Likes

Don’t know if problem is with my internet or the website, but I can’t open it. :slightly_frowning_face:

Hmmm … strange. Anyway, here’s a copy-n-paste of it:

// Simon St James (ssjgz) - 2020-XX-XX
// 
// Solution to: TODO - problem link here!
//
//#define SUBMISSION
#define BRUTE_FORCE
#ifdef SUBMISSION
#undef BRUTE_FORCE
#define NDEBUG
#else
#define _GLIBCXX_DEBUG       // Iterator safety; out-of-bounds access for Containers, etc.
#pragma GCC optimize "trapv" // abort() on (signed) integer overflow.
#endif
#include <iostream>
#include <vector>

#include <cassert>

#include <sys/time.h> // TODO - this is only for random testcase generation.  Remove it when you don't need new random testcases!

using namespace std;

template <typename T>
T read()
{
    T toRead;
    cin >> toRead;
    assert(cin);
    return toRead;
}

#if 0
SolutionType solveBruteForce()
{
    SolutionType result;
    
    return result;
}
#endif

#if 0
SolutionType solveOptimised()
{
    SolutionType result;
    
    return result;
}
#endif


int main(int argc, char* argv[])
{
    ios::sync_with_stdio(false);
    if (argc == 2 && string(argv[1]) == "--test")
    {
        struct timeval time;
        gettimeofday(&time,NULL);
        srand((time.tv_sec * 1000) + (time.tv_usec / 1000));
        // TODO - generate randomised test.
        //const int T = rand() % 100 + 1;
        const int T = 1;
        cout << T << endl;

        for (int t = 0; t < T; t++)
        {
        }

        return 0;
    }
    
    // TODO - read in testcase.
    const auto T = read<int>();

    for (int t = 0; t < T; t++)
    {

#ifdef BRUTE_FORCE
#if 0
        const auto solutionBruteForce = solveBruteForce();
        cout << "solutionBruteForce: " << solutionBruteForce << endl;
#endif
#if 0
        const auto solutionOptimised = solveOptimised();
        cout << "solutionOptimised:  " << solutionOptimised << endl;

        assert(solutionOptimised == solutionBruteForce);
#endif
#else
        const auto solutionOptimised = solveOptimised();
        cout << solutionOptimised << endl;
#endif
    }

    assert(cin);
}
3 Likes

while submitting solution should we comment this line #define _GLIBCXX_DEBUG?

In my template? Assuming I haven’t made a mistake, it should be enough to just uncomment the

//#define SUBMISSION

Obviously, only do this when you’ve finished debugging and are sure your solution is correct :slight_smile:

1 Like

Yeah thanks @ssjz

1 Like

The performance impact is noticeable
https://ideone.com/NwF8je (with)
https://ideone.com/l2fSzm (without)

8 Likes

Great - thanks for doing the experiment and providing some hard numbers :slight_smile:

1 Like

I’m trying to use the

#pragma GCC optimize "trapv"

But when i use the following code

#pragma GCC optimize "trapv"
#include<iostream>
#include<bits/stdc++.h>
#define ll long long int
using namespace std;
int main(){
        int a=10000000,b=1000000000;
        cout<<a<<" "<<b<<'\n';
        int f=a*b;
        cout<<f;
}

It’s not crashing. How do I use it correctly?

1 Like

Interesting - it’s not crashing for me, either. However:

[simon@simon-laptop][17:53:24]
[~/devel/hackerrank/otherpeoples]>cat everule1-ftrapv-test.cpp 
#pragma GCC optimize "trapv"
#include<iostream>
#include<bits/stdc++.h>
#define ll long long int
using namespace std;
int main(){
        int a,b;
        cin >> a >> b;
        cout<<a<<" "<<b<<'\n';
        int f=a*b;
        cout<<f;
}

[simon@simon-laptop][17:53:32]
[~/devel/hackerrank/otherpeoples]>g++ -std=c++14 everule1-ftrapv-test.cpp  -O3
[simon@simon-laptop][17:53:37]
[~/devel/hackerrank/otherpeoples]>echo "10000000 1000000000" | ./a.out
10000000 1000000000
Aborted (core dumped)

crashes as expected.

I’d guess that with the original version, the compiler is computing the result of a * b at compile-time, and so not triggering the runtime error.

2 Likes

Okay thanks, I thought i was using it incorrectly.

1 Like