10

GNU Multi-Precision (GMP) ライブラリ コードを使用して、任意の長さの整数を使用するコードを調べていました。MP 整数の型はmpz_t、gmp.h ヘッダー ファイルで定義されているとおりです。

しかし、このライブラリ定義mpz_t型の下位レベルの定義についていくつか質問があります。ヘッダー コード内:

/* THIS IS FROM THE GNU MP LIBRARY gmp.h HEADER FILE */
typedef struct
{
    /* SOME OTHER STUFF HERE */
} __mpz_struct;

typedef __mpz_struct mpz_t[1];

最初の質問: は と[1]関連してい__mpz_structますか? つまり、型を 1 回出現する配列としてtypedef定義しているのでしょうか。mpz_t__mpz_struct

2 番目の質問: なぜ配列なのか? (そして、なぜ 1 回しか発生しないのですか?) これは私が聞いた構造体ハックの 1 つですか?

3 番目の質問 (おそらく 2 番目の質問に間接的に関連している):mpz_init_set(mpz_t, unsigned long int)関数の GMP ドキュメントでは、値渡しのみとして使用するように指示されていますが、この関数は呼び出された関数内の内容を変更していると想定されます (したがって、参照渡し) 構文。私のコードを参照してください：

/* FROM MY CODE */
mpz_t fact_val;                /* declaration */
mpz_init_set_ui(fact_val, 1);  /* Initialize fact_val */

単一出現配列は、参照渡しを自動的に有効にしますか (C の配列/ポインターのセマンティクスが壊れているため)? 私はこれを少し分析しすぎていることを率直に認めますが、これについての議論が大好きです. ありがとう！

4

3 に答える 3

5

これは、C2 で説明されている意味での構造体ハックではないようです。彼らmpz_tはポインターのセマンティクスを望んでいるようです (おそらく、人々に不透明なポインターのように使用してもらいたいのでしょう)。次のスニペットの構文上の違いを考慮してください。

struct __mpz_struct data[1];

(&data[0])->access = 1;
gmp_func(data, ...);

と

mpz_t data;

data->access = 1;
gmp_func(data, ...);

C 配列はポインターに分解されるため、これによりmpz_t型の自動参照渡しも可能になります。

mallocまたはそれを必要とせずにポインタのような型を使用することもできますfree。

于 2011-01-29T04:29:35.347 に答える
3

この理由は、 の実装に由来しmpnます。具体的には、数学に傾倒している場合は、N が自然数の集合 (1,2,3,4...) であるのに対し、Z は整数の集合 (...,-2,-1,0) であることに気付くでしょう。 、1、2、...)。

Z に bignum ライブラリを実装することは、N に実装することと同じであり、符号演算に関するいくつかの特別なルールを考慮します。つまり、加算または減算を行う必要があるかどうか、および結果がどうなるかを追跡します。

さて、bignum ライブラリがどのように実装されているかについては、次の行で手がかりが得られます。

typedef unsigned int        mp_limb_t;
typedef mp_limb_t *     mp_ptr;

それでは、それを操作する関数シグネチャを見てみましょう。

__GMP_DECLSPEC mp_limb_t mpn_add __GMP_PROTO ((mp_ptr, mp_srcptr, mp_size_t, mp_srcptr,mp_size_t));

基本的に、「リム」は数値のビットを表す整数フィールドであり、整数は巨大な配列として表されます。巧妙な部分は、gmp がこれらすべてを非常に効率的で最適化された方法で行うことです。

とにかく、議論に戻ります。基本的に、C で配列を渡す唯一の方法は、ご存知のように、これらの配列へのポインターを渡すことです。これにより、効果的に参照渡しが可能になります。ここで、何が起こっているかを追跡するために、2 つの型が定義されています。1 つは数値を格納するのに十分な大きさmp_ptrの配列であり、もう 1 つはその const バージョンであり、ソースのビットを誤って変更することはありません。あなたが操作しているもののbignums。基本的な考え方は、ほとんどの関数が次のパターンに従うということです。mp_limb_tmp_srcptr

func(ptr output, src in1, src in2)

したがって、mpz_*関数は単に一貫性を保つためにこの規則に従っているのではないかと思います。

短いバージョン: bignum lib を実装する必要があるため、これが必要です。

于 2011-01-29T08:06:46.430 に答える
3

*最初の質問: は[1]__mpz_struct と関連していますか? つまり、typedef は mpz_t 型を __mpz_struct 配列として 1 回出現するように定義していますか? *

はい。

2 番目の質問: なぜ配列なのか? (そして、なぜ 1 回しか発生しないのですか?) これは私が聞いた構造体ハックの 1 つですか?

私を殴る。わかりませんが、1 つの可能性は、作成者が自動的に参照渡しされるオブジェクトを作成したかったか、「はい」、おそらく構造体ハックを作成したかったことです。オブジェクトが構造体の最後のメンバーであることmpz_tがわかった場合、「ほぼ確実に」それは構造体ハックです。次のような割り当て

malloc(sizeof(struct whatever) + sizeof(mpz_t) * some_number)`

デッドプレゼントになります。

単一出現配列は自動的に参照渡しを有効にしますか?

ああ、あなたもそれを理解しました。「はい」、考えられる理由の 1 つは、より複雑な参照を犠牲にして参照渡しを単純化することです。

もう 1 つの可能性は、データ モデルまたはアルゴリズムで何かが変更され、作成者がすべての参照を見つけて何らかの方法で変更したかったことです。このように型を変更すると、プログラムの基本型は同じままになりますが、変換されていない参照ごとにエラーが発生します。

于 2011-01-29T04:21:47.343 に答える