Некоторые вопросы о массиве с одним экземпляром в typedef - PullRequest
Новая
       11

Некоторые вопросы о массиве с одним экземпляром в typedef

8 голосов
/ 29 января 2011

Я просматривал некоторый код, используя целые числа произвольной длины, используя код библиотеки 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?Другими словами, определяет ли typedef тип mpz_t как массив __mpz_struct с одним вхождением?

Второй вопрос: почему массив?(И почему только одно вхождение?) Это один из тех struct hacks , о которых я слышал?

Третий вопрос (возможно, косвенно связанный со вторым вопросом): документация GMP для *Функция 1019 * говорит, что она должна использоваться только как передаваемое по значению, хотя предполагалось бы , что эта функция изменяет свое содержимое в вызываемом синтаксисе функции (и, следовательно, ей потребуется передача по ссылке).См. Мой код: 

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

Включает ли массив единого вхождения автоматическую передачу по ссылке (из-за нарушения семантики массива / указателя в C)?Я свободно признаю, что я немного переоцениваю это, но я бы с радостью обсудил это.Спасибо!

Ответы [ 3 ]

4 голосов
/ 29 января 2011

Это не похоже на структурный взлом в смысле, описанном на С2. Похоже, они хотят, чтобы 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 it.

3 голосов
/ 29 января 2011

* Первый вопрос: ассоциируется ли [1] с __mpz_struct? Другими словами, определяет ли typedef тип mpz_t как массив __mpz_struct с одним вхождением? *

Да.

Второй вопрос: почему массив? (И почему только одно вхождение?) Это один из тех структурных хаков, о которых я слышал?

Бьет меня. Не знаю, но одна возможность состоит в том, что автор хотел создать объект, который был передан по ссылке автоматически, или, да, возможно, взломать структуру. Если вы когда-либо видели объект mpz_t как последний член структуры, то «почти наверняка» это взлом структуры. Распределение выглядит как 

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

был бы мертвым подарком.

Разрешает ли массив единого вхождения автоматическую передачу по ссылке ...?

Ага, ты тоже это понял. «Да», одной из возможных причин является упрощение передачи по ссылке за счет более сложных ссылок.

Полагаю, другая возможность заключается в том, что что-то изменилось в модели данных или алгоритме, и автор хотел найти каждую ссылку и изменить ее каким-то образом. Подобное изменение типа оставит программу с тем же базовым типом, но с ошибкой при каждой неконвертированной ссылке.

2 голосов
/ 29 января 2011

Причина этого кроется в реализации mpn. В частности, если вы склонны математически, вы поймете, что N - это набор натуральных чисел (1,2,3,4 ...), тогда как Z - это набор целых чисел (..., - 2, -1,0 1,2, ...).

Внедрение библиотеки bignum для Z равносильно тому, чтобы сделать это для 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 - это, как вы знаете, передавать указатели на эти массивы, что эффективно позволяет передавать по ссылке. Теперь, чтобы отслеживать, что происходит, определены два типа: mp_ptr, который представляет собой массив mp_limb_t, достаточно большой для хранения вашего числа, и mp_srcptr, который является константной версией этого, так что вы не можете случайно изменить биты исходных текстов того, что вы используете. Основная идея заключается в том, что большинство функций следуют этой схеме: 

func(ptr output, src in1, src in2)

и т.д.. Таким образом, я подозреваю, что mpz_* функции следуют этому соглашению просто чтобы быть последовательными, и это потому, что так думают авторы.

Короткая версия: из-за того, как вам нужно реализовать bignum lib, это необходимо.

...