ac-library icon indicating copy to clipboard operation
ac-library copied to clipboard

modint.hpp static_modint unsigned integer overflow

Open CroMarmot opened this issue 3 years ago • 0 comments

I'm using clang++ with command like

clang++ -o "%<" "%" -std=gnu++17 -O2 -g -Wall -Wcomma -Wextra -fsanitize=integer,undefined,null,alignment

and cpp code

#include <bits/stdc++.h>
#include <atcoder/modint>

int main(){
  atcoder::modint998244353 x = 0;
  x -= 1;
  std::cout<< x.val() << std::endl;
  return 0;
}

then compile and run the code

it report that

/usr/local/include/atcoder/modint.hpp:80:12: runtime error: unsigned integer overflow: 0 - 1 cannot be represented in type 'unsigned int'
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior /usr/local/include/atcoder/modint.hpp:80:12 in 
/usr/local/include/atcoder/modint.hpp:81:30: runtime error: unsigned integer overflow: 4294967295 + 998244353 cannot be represented in type 'unsigned int'
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior /usr/local/include/atcoder/modint.hpp:81:30 in

So I took a look at the source code

https://github.com/atcoder/ac-library/blob/f669803f78c3acc72671ca6e41b4eeb0469364a8/atcoder/modint.hpp#L79-L83

I think it might be changed as

     mint& operator-=(const mint& rhs) {
-        _v -= rhs._v;
-        if (_v >= umod()) _v += umod();
+        _v += umod() - rhs._v;
+        if (_v >= umod()) _v -= umod();
         return *this;
     }

CroMarmot avatar Aug 11 '22 04:08 CroMarmot