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

ssjgz · February 24, 2020, 9:37am

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 _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

cubefreak777 · February 24, 2020, 9:46am

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

ssjgz · February 24, 2020, 9:47am

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

shlok_dhara · February 24, 2020, 11:50am

@ssjgz Can you please tell me what is D_GLIBCXX_DEBUG ?

ssjgz · February 24, 2020, 11:56am

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> > >;
    }

shlok_dhara · February 24, 2020, 11:57am

Will it work in C ?

ssjgz · February 24, 2020, 12:02pm

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

shlok_dhara · February 24, 2020, 12:04pm

Thank for clearing my doubt

harshraj22 · February 24, 2020, 12:38pm

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.

ssjgz · February 24, 2020, 1:16pm

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

harshraj22 · February 24, 2020, 1:29pm

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

ssjgz · February 24, 2020, 1:31pm

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);
}

nihith123 · February 24, 2020, 2:51pm

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

ssjgz · February 24, 2020, 2:59pm

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

nihith123 · February 24, 2020, 3:19pm

Yeah thanks @ssjz

rahul_g · February 24, 2020, 6:28pm

The performance impact is noticeable
NwF8je - Online C++0x Compiler & Debugging Tool - Ideone.com (with)
l2fSzm - Online C++0x Compiler & Debugging Tool - Ideone.com (without)

ssjgz · February 24, 2020, 6:30pm

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

everule1 · March 8, 2020, 5:48pm

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?

ssjgz · March 8, 2020, 5:56pm

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.

everule1 · March 8, 2020, 5:58pm

Okay thanks, I thought i was using it incorrectly.