2020/11/14 GMPがver6.2.1にアップデートされた. いくつかバグが修正されたのだが,その中にmpz_cmpが含まれていた. Release noteによると
A possible overflow of type int is avoided for mpz_cmp on huge operands.
とのこと.大きな値をmpz_cmpに渡すとオーバーフローする可能性があったらしい.数を比較する関数でオーバーフロー・・?と思うかもしれないので,実際にコードを見てみる.
修正前
int mpz_cmp (mpz_srcptr u, mpz_srcptr v) __GMP_NOTHROW { mp_size_t usize, vsize, dsize, asize; mp_srcptr up, vp; int cmp; usize = SIZ(u); vsize = SIZ(v); dsize = usize - vsize; // 筆者コメント:ここでオーバーフローする if (dsize != 0) return dsize; asize = ABS (usize); up = PTR(u); vp = PTR(v); MPN_CMP (cmp, up, vp, asize); return (usize >= 0 ? cmp : -cmp); }
まずmpz_cmpの機能を説明すると,2つの数(u, v)を取り,u==vなら0を,u > vなら正の数を,u < vなら負の数を返す.
\begin{align} mpz\_cmp(u, v) = \begin{cases} 0 & (u = v) \cr Positive \, num & (u > v) \cr Negative \, num & (u < v) \end{cases} \end{align}
mpz_cmpの実装ではu, vのサイズ(ビット幅だと思おう.少し違うが.)を取ってきて差を計算している.これは,サイズの違う値なら大小比較が簡単にできるということを意味している.また,サイズはint型なのでもちろん負数を取ることができ,サイズが負のときは値が負であることを意味する.
例を示そう.
uのサイズが10, vのサイズが8だとする.明らかにuが大きい.mpz_cmpが返す値は10-8=2で,正の値を返しているので正しい.
片方が負数のときの例はどうか.uのサイズが10, vのサイズが-8としよう.
10 - (-8) = 18で正の値を返す.vは負数なので明らかにuの方が大きい.mpz_cmpは正しく動作している.
では次のような場合はどうか.
uのサイズを \( 2^{31} - 1 \) とする.サイズは符号付きのint型であるので,最大値を取っている.一方,vのサイズを負数にすると引き算の式が \( 2^{31} - 1 + |vsize| \)となり,オーバーフローして負の値を取ってしまう.正の値であるuの方がvより明らかに大きいのに,mpz_cmpは負の値を返してしまう.つまり,vがuより大きいと判断されてしまっている.
このバグを踏む条件はそこそこ厳しく,(2^{31}-1) * sizeof(mp_limb_t) * 8 ビットの値を計算するときくらいである.とは言えバグはバグなので次のように修正された.
修正後
int mpz_cmp (mpz_srcptr u, mpz_srcptr v) __GMP_NOTHROW { mp_size_t usize, vsize, asize; mp_srcptr up, vp; int cmp; usize = SIZ(u); vsize = SIZ(v); /* Cannot use usize - vsize, may overflow an "int" */ if (usize != vsize) return (usize > vsize) ? 1 : -1; asize = ABS (usize); up = PTR(u); vp = PTR(v); MPN_CMP (cmp, up, vp, asize); return (usize >= 0 ? cmp : -cmp); }
オーバーフローの可能性がある引き算をやめて,単純にサイズの大小を見ることにしている.
\begin{align} mpz\_cmp(u, v) = \begin{cases} 0 & (u = v) \cr 1 & (u > v) \cr -1 & (u < v) \end{cases} \end{align}
以上.