編集履歴

回答編集履歴

scanf() 対策を追加

2020/03/01 22:59

投稿

スコア1382

answer CHANGED Viewed

@@ -283,4 +283,19 @@
 K[] という配列名は #define K 128*2 と被ります。コードの可読性・保守性の観点から、両方の「K」という名前をそれぞれ変更したほうが良いと思います。
 ・・・と、これだけでも、他の人が使えるコード品質になるには道のり長そうですね。
-Enjoy !
+Enjoy !
+> scanfを入れているのは、表示を確認するために一時停止をしたいから
+そのためにグローバル変数に読み込むのは本末転倒・言語道断。その後 fwrite() はどうなるか考えよ。
+scanf() で停止するなら <stdio.h> の入力関数 fgets() 等でも停まります。getchar(); とだけ書いたこともあるけど、普通は小さな関数を作って、停めたい所で呼ぶでしょう。
+```C
+//  extern int n;     ← ＮＧ！　現状、こうなっている
+void wait4keyinput(void)
+{
+    int n;                    // 読み込む変数はローカルに取るべし
+    printf(" (hit return) "); // 何か表示させたほうが良いだろう
+    fflush(stdout);           // just in case
+    scanf("%d", &n);          // fgets(line, LINESIZE, stdin); という手も
+}
+```

コードレビュー、さらに追加

2020/03/01 22:59

投稿

rubato6809

スコア1382

answer CHANGED Viewed

@@ -199,4 +199,88 @@
 #endif
 ```
 そもそも引数の f は、構造体そのものを引数にするのではなく、元の構造体へのポインタ（アドレス）だけ受け取れば十分なのではないか。構造体を引数にすると、実引数から仮引数へコピーが毎回発生するので効率悪い。
-（もう寝るｗ）
+（もう寝るｗ）
+---
+さらに追加します。
+- 実際、不要なローカル変数が山のよう・・・
+- 関数の最後にあるべき return 文が無く、関数の最後で目的の値を返さない経路がある。既に、上で int deg(vec a) 関数を指摘したが、他にもあった。コード品質の低さを示すもの。
+unsigned short oinv(unsigned short a)    // BUG !!!
+unsigned char chk(OP f)
+int isqrt(unsigned short u)
+OP osqrt(OP f, OP w)  --- 長大な関数
+- 信用を失う滅茶苦茶な関数w
+```C
+OP ToHorner(OP f)
+{
+    vec v = o2v(f);    // この計算は何？
+    OP h;
+    return h;          // 不定値を返す OMG
+}
+```
+- 変数に代入するが使わない。何をするつもりか意図が不明な処理が多数見つかる。
+```C
+// 計算結果を使わない例1
+int main(void)    // argc, argv を使わない
+{
+    unsigned short mm[T];      // mm[t] = {0} 初期化不要
+    // 途中省略
+        for (i = 0; i < T; i++) {
+            mm[i] = r.t[i].a;  // mm[i] に代入するも、使わない
+// 計算結果を使わない例2
+OP ogcd(OP f, OP g)       // ユークリッドの互除法?
+{
+    OP h, ww;             // 初期化不要
+    for (int i = 0; i < T; i++) {
+        h  = omod(f, g);
+        ww = odiv(f, g);  // この除算は不要
+        f = g;
+        g = h;
+    }
+//  一方、xgcd() は除算した結果 ww を使う。そこをコピペしたか？
+```
+lu.c を拝見しました。
+- 一文字のグローバル変数が！言語道断モノですw
+```C
+int i, j, k; // カウンタ      !!! OMG !!!
+int n = F;   // 配列の次数    ??? for fwrite()
+```
+ここをコメントアウトすると、これらに頼っているコードが判明します。
+この小文字変数 k に頼るコードが det() 関数に見つかります。
+```C
+void det(unsigned short g[])
+{
+    // 省略
+    k = cc[K];
+    // 途中省略
+    cc[K] = k;
+```
+この大文字「K」は #define K 128*2 という定数マクロです。大文字・小文字のK, kを一緒に使うのは、いかがなものかと（乱視が悪化してきた私は）思う。
+i, j, k は、頼っている関数にローカル変数を追加すれば削除できます。
+問題は n です。n の主目的は fwrite(dd, 1, n, fq); の引数とみられますが、他の箇所から n の値を変更可能です。たとえば oplib.c に scanf("%d", &n); が何箇所かあり、（意図通りかどうかは不明だが）キー入力した値がこの n に読み込まれるらしい。グローバル変数に対する典型的な戒めを変数「n」に見出すことができます。
+しかも「n」という変数名は、関数内のローカル変数にもあるうえに、oterm 構造体のメンバ変数でもある。カオスです。
+グローバル変数、マクロ名、寿命の長い変数、アルゴリズム的・意味的に重要な変数などはもっと長い変数名にしたほうが良いでしょう。ひとつの目安は grep コマンドで、それぞれの変数が登場する箇所を特定できること、でどうですか。
+- chash.cpp - 拡張子 cpp は C++ ソースを意味するが、実際は C 。
+```C
+void SHA512_transform(unsigned long long H[], unsigned long long W[])
+{
+    static const unsigned long long K[80] = {
+		0x428a2f98d728ae22ULL, 0x7137449123ef65cdULL,
+```
+K[] という配列名は #define K 128*2 と被ります。コードの可読性・保守性の観点から、両方の「K」という名前をそれぞれ変更したほうが良いと思います。
+・・・と、これだけでも、他の人が使えるコード品質になるには道のり長そうですね。
+Enjoy !

回答を修正、コードレビューを追加

2020/02/29 15:13

投稿

rubato6809

スコア1382

answer CHANGED Viewed

@@ -1,7 +1,7 @@
-多数のOP構造体変数がスタック領域に取られることから、**スタックオーバーフローが起こった**のではないかと見ています。
+多数のOP構造体変数がスタック領域に取られることから、**スタックオーバーフローが起こった**ようです。
-OP型構造体変数は3072バイトのサイズではないかと。それがローカル変数としてスタック上にいくつもとられ、pattarson(), xgdb() 関数の引数にもなっています。他にもサイズの大きな変数が見つかります。スタックオーバーフローを起こしているとすれば、コード全体で変数の設計を考えなおす必要があると思います。
+OP型構造体変数のサイズは3072バイトです。それがローカル変数としてスタック上にいくつもとられ、pattarson(), xgdb() 関数の引数にもなっています。他にもサイズの大きな変数が見つかります。コード全体で変数の設計を考えなおす必要があります。
-なお、-O2 最適化した場合は、ローカル変数の使用量を減らすような最適化がおこなわれるのではないかと想像しています。
+-O2 最適化した場合は、ローカル変数の使用量を減らす最適化がおこなわれるようです。
 oplib.c のみコンパイルして現象を再現できるようですが、コンパイルと起動方法、デバッグ操作が合ってるか、ご確認ください。ただしスタックオーバーフローは実行環境が異なれば、発生する場所が異なる可能性があると思います。以下は私の実行例です。
@@ -72,4 +72,131 @@
 ```
-コードレビューする側としてコメントしたいことはありますが、取り急ぎ問題点と思われる点を回答します。お気づきのように、既にコードに手を入れて、少しづつ私のスタイルに変更しつつあります。
+コードレビューする側としてコメントしたいことはありますが、取り急ぎ問題点と思われる点を回答します。お気づきのように、既にコードに手を入れて、少しづつ私のスタイルに変更しつつあります。
+---
+#スタックオーバーフローによってSegmentation Faultが起こった事は確実
+> 使ってないOP構造体がたくさんありすぎてメモリが溢れた
+その結果、
+> -O2 最適化した場合は、ローカル変数の使用量を減らす最適化がおこなわれる
+スタックオーバーフロー直前のスタックトップ付近のアドレスと、main() が動作開始した時点のスタックポインタ（付近）の差をとれば、どれだけスタック領域を消費したかがわかります。手元で調べたところ、約7.8MB消費したことがわかりました。xgcd() もスタックに巨大なローカル変数（v[K*2], u[K*2]等）を取りますので、それらを初期化しようとしたところで落ちたのでしょう。
+一方、-O2オプションでコンパイルすると未使用な変数は削除され、スタック領域の消費量が減り、3.8MB程度に半減したことがわかりました。
+> １６Gもメモリを積んでいるので暴走しないはず
+各プロセスは実装メモリを独り占めすることはできません。ＯＳ（Linux, Windows等）はメモリ資源を管理しており、プロセスには実装メモリの一部分しか与えないからです。
+[実行時スタックサイズ変更 on Linux](https://stakizawa.hatenablog.com/entry/20061017/t1)を見ると、デフォルトは8192であり、これは8MBがプロセスに与えられることを意味します。約7.8MB消費した時点でスタックは溢れる寸前だったわけです。このページに倣って、16MBのメモリを与えると最適化しないプログラムも動作を続けることができました。即ち、スタック領域が足りなかったことは確実です。
+```bash
+$ ulimit -s 16384           <<= 16MB に拡張する
+$ ./a.out                   <<= 動作できる
+```
+---
+コードレビューしてみます。
+- 不要な変数は削除しましょう。pattarson() 関数の中をざっと見ただけですが、
+```
+    unsigned short m[K],mm[T]={0},dd[K*D]={0};  // <<= すべて不要
+    OP h={0},r={0},aa[K]={0},tt={0},ff={0};     // aa[k] が不要
+```
+OP aa[K]; だけで 786KB (== 3072 * 256)を消費します。こうした未使用の変数を削除するには**全ての警告(warning)を出させる**オプション -Wallを指定するとよいです。
+$ cc oplib.c -Wall
+- 不要な変数を、各関数に同じようにとっているかのようにも見えます。そこから、変数のスコープを理解していないのではないか、各関数の役割を整理しないままコーディングしているのではないか、といったことを疑います。
+- コードが記述されたファイルをインクルードするのはイリーガル。インクルードするのはヘッダファイルにするのが普通。ヘッダファイルには定義を書き、コードは書かない。
+```
+#include "chash.cpp"    // インクルードしてはいけない。分割コンパイルせよ
+#include "lu.c"
+```
+一番簡単な分割コンパイルのやり方は次（他にも修正が必要になりそうなので私は試してない）。
+$ cc oplib.c chash.cpp lu.c
+- 計算式で定義する定数マクロはカッコで囲むのが安全。数字をカッコで囲む人もいる。
+```
+#define K   (128*2)         // こうしたマクロはカッコで守ろう
+#define DEG (3*K)
+#define T   (K/2)
+#define E   (13)
+#define D   6688            // こういう値の意味・根拠は？
+```
+- K, T, E, D, c[2 * K + 1], g[K + 1] ・・・このように文字数の少ない識別子が大手を振って使われるのは、よくありません。スコープが狭い、或いは寿命が短い変数であれば構いませんけど。
+- 構造体のメンバ名が短いのは、構わないけど、何か説明のコメントが欲しくなります。
+```
+typedef struct {
+    unsigned short n;    // 何かコメントを書こう
+    unsigned short a;
+} oterm;
+```
+- deg()関数はreturn値が不定となる可能性あり。-Wallは警告するかもしれない。
+```
+int deg(vec a)
+{
+    // 省略
+    if (n > 0)
+        return n;
+    // 警告！！！nが０なら戻り値は不定？
+}
+```
+if (n > 0) という条件判定は不要で、単に return n; すれば良いのではないか。
+- 構造体を返す関数に注意。o2v(), v2o(), init_op()等は、ポインタを受け取って、そこに結果を書き込んだほうが効率が良いのだけどなあ・・・
+- OP oadd(OP f, OP g) も、上記のようにポインタを受け取りそこに結果を書き込むこともできるが、今の仕様のままでもツッコミどころがいくつか。初期化が不要な変数だってある、初期化だけでも時間はかかる。
+```
+OP oadd(OP f, OP g)
+{
+#ifdef ORIGIN
+    vec a = {0}, b = {0}, c = {0};  // a, b は初期化不要
+#else
+    vec a, b, c = {0};              // c は０クリアしたほうが安全か
+#endif
+    int i, k;
+    OP h = {0};      // 不要。下の return を見よ
+    a = o2v(f);      // ここで a, b に値が代入される。０クリアする必要無し
+    b = o2v(g);
+#ifdef ORIGIN        // 元のコード
+    // 実行時、deg() を３回呼び出すが
+    if(deg(a) >= deg(b)){
+        k=deg(a)+1;
+    }else{
+        k=deg(b)+1;
+    }
+#else　　　　　　　　　　// 改良コード
+    int ka = deg(a);  // 一時変数に取れば、呼出しは２回で済む
+    int kb = deg(b);
+    if (ka >= kb) {
+        k = ka + 1;
+    } else {
+        k = kb + 1;
+    }
+#endif
+    // c を０で初期化しておく必要はあるか？　不明
+    for (i = 0; i < k; i++)
+        c.x[i] = a.x[i] ^ b.x[i];   // ここで c は x[k-1] まで決定する
+#ifdef ORIGIN
+    h = v2o(c);
+    return h;
+#else
+    return v2o(c);    // 元の２行は１行で書けるので h は不要
+#endif
+}
+```
+- ループの中で構造体変数 f の値は変化しないので、terms(f) は一回計算するだけで良い。
+```
+int odeg(OP f)
+{
+    int i, j = 0, k;
+#ifdef ORIGIN
+    for (i = 0; i < terms(f) + 1; i++) {   // terms(f) を毎回計算するの？
+#else
+    k = terms(f) + 1;                      // 計算は一回だけ
+    for (i = 0; i < k; i++) {
+#endif
+```
+そもそも引数の f は、構造体そのものを引数にするのではなく、元の構造体へのポインタ（アドレス）だけ受け取れば十分なのではないか。構造体を引数にすると、実引数から仮引数へコピーが毎回発生するので効率悪い。
+（もう寝るｗ）