colinpitrat / polynomial Goto Github PK

The following warning shows up in minusTimesXn method:
==2179== Invalid read of size 8
==2179== at 0x4013F1: G2Poly::minusTimesXn(G2Poly const&, unsigned long) (g2polynomial.h:140)
==2179== by 0x401665: operator%(G2Poly const&, G2Poly const&) (g2polynomial.h:173)
==2179== by 0x401FBF: gcd(G2Poly, G2Poly) (g2polynomial.h:321)
==2179== by 0x403B22: G2Poly::mceliece(unsigned long) const (g2polynomial.h:500)
==2179== by 0x404084: main (test_g2polynomial.cpp:15)
==2179== Address 0x4c39bb8 is 0 bytes after a block of size 56 alloc'd
==2179== at 0x4A068F3: operator new(unsigned long) (in /usr/lib64/valgrind/vgpreload_memcheck-amd64-linux.so)
==2179== by 0x4084CB: __gnu_cxx::new_allocator::allocate(unsigned long, void const*) (new_allocator.h:104)
==2179== by 0x4075CC: std::_Vector_base<unsigned long, std::allocator >::_M_allocate(unsigned long) (in /home/pierre/codingame/nintendo/soluce/test_g2polynomial)
==2179== by 0x406ADB: unsigned long* std::vector<unsigned long, std::allocator >::_M_allocate_and_copy<__gnu_cxx::__normal_iterator<unsigned long const*, std::vector<unsigned long, std::allocator > > >(unsigned long, __gnu_cxx::__normal_iterator<unsigned long const*, std::vector<unsigned long, std::allocator > >, __gnu_cxx::__normal_iterator<unsigned long const*, std::vector<unsigned long, std::allocator > >) (stl_vector.h:1138)
==2179== by 0x405519: std::vector<unsigned long, std::allocator >::operator=(std::vector<unsigned long, std::allocator > const&) (vector.tcc:188)
==2179== by 0x40474A: G2Poly::operator=(G2Poly const&) (g2polynomial.h:13)
==2179== by 0x401FA5: gcd(G2Poly, G2Poly) (g2polynomial.h:320)
==2179== by 0x403B22: G2Poly::mceliece(unsigned long) const (g2polynomial.h:500)
==2179== by 0x404084: main (test_g2polynomial.cpp:15)

This could be fixed with the following modifications:

void G2Poly::minusTimesXn(const G2Poly &b, uint64_t n) {
std::vector <uint64_t> result;
result.reserve(std::max(b.coeffs_.size(), coeffs_.size()));
size_t i(0), j(0);
auto size = coeffs_.size();
auto size2 = b.coeffs_.size();
auto ci = coeffs_[i];
auto cj = b.coeffs_[j] + n;
while(i < size && j < size2) {
if(ci > cj) {
result.push_back(ci);
++i; if (i<size) ci = coeffs_[i];
} else if(ci < cj) {
result.push_back(cj);
++j; if (j<size2) cj = b.coeffs_[j] + n;
} else {
++i; if (i<size) ci = coeffs_[i];
++j; if (j<size2) cj = b.coeffs_[j] + n;
}
}
// Insert remaining coeffs from other as they are obviously not in this
while(i < size) {
result.push_back(coeffs_[i]);
i++;
}
while(j < size2) {
result.push_back(b.coeffs_[j] + n);
j++;
}
this->coeffs_.swap(result);
}

Hope this helps.