ColinPitrat
commented
7 years ago Thanks for the feedback. Should be fix with https://github.com/ColinPitrat/polynomial/commit/b1a8b346d9075c0e4ffbe43d24860b42bc923909
Closed pierreg06 closed 7 years ago
ColinPitrat
commented
7 years ago Thanks for the feedback. Should be fix with https://github.com/ColinPitrat/polynomial/commit/b1a8b346d9075c0e4ffbe43d24860b42bc923909
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 result;
result.reserve(std::max(b.coeffs.size(), coeffs.size()));
sizet 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.pushback(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.pushback(coeffs[i]);
i++;
}
while(j < size2) {
result.pushback(b.coeffs[j] + n);
j++;
}
this->coeffs_.swap(result);
}
Hope this helps.