| Translations Blog |

Transparent PNG

Библиотека быстрой арифметики поля Галуа на C / C ++

Перевод статьи - Fast Galois Field Arithmetic Library in C/C++

Автор(ы) - James S. Plank

Источник оригинальной статьи:

http://web.eecs.utk.edu/~jplank/plank/papers/CS-07-593/

[email protected]

Технический отчет UT-CS-07-593
Департамент компьютерных наук
Университета Теннесси

 

Если вы используете этот код

Отправьте мне электронное письмо ( [email protected] ) и дайте мне знать. Один из способов, которым меня оценивают, - это влияние моей работы, и важны достоверные данные о том, сколько людей используют этот код.

Благодарности

Этот веб-сайт основан на работе, поддержанной Национальным научным фондом в рамках грантов CNS-0615221 и CNS-0437508. Я также хотел бы поблагодарить Cheng Huang, Lihao Xu, Jin Li и Mochan Shrestha за полезные обсуждения, а также Michel Machado за полезные предложения.

Вступление

Арифметика поля Галуа является фундаментальной для многих приложений, особенно для кодирования Рида-Соломона. В поле Галуа GF (2 w ) операции сложения, вычитания, умножения и деления определяются над числами 0, 1, ..., 2 w -1. таким образом, что:

 

Когда w = 8 , Поле Галуа GF (2 8 ) содержит элементы 0, 1, ..., 255. Это важное поле, потому что оно позволяет выполнять арифметические операции, которые придерживаются вышеуказанных свойств для отдельных байтов. Опять же, это важно в кодировании Рида-Соломона и других видах кодирования. Точно так же w = 16 и w = 32 - другие важные поля.

Есть полезные приложения для полей с другими значениями w . Например, кодирование Коши Рида-Соломона использует поля Галуа с другими значениями w и преобразует их в строго двоичные (XOR) коды.

Поля Галуа описаны в стандартных текстах по кодам исправления ошибок, таких как Peterson & Weldon [PW72], MacWilliams and Sloane [MS77] и Van Lint [VL82]. Эти процедуры являются тщательными и требуют времени, чтобы понять их. Для более краткого и прагматичного рассмотрения см. Учебник Планка 1997 года по кодированию Рида-Соломона [P97] , [PD05].

Файлы библиотеки

Эта библиотека представлена ​​в виде tar- файла: galois.tar . Файлы galois.tar :

Использование инструментов командной строки

Введите make, чтобы скомпилировать библиотеку и инструменты командной строки. Тестирование инструментов командной строки - хороший способ увидеть, как все работает с Полями Галуа. Во-первых, сложение и вычитание в Поле Галуа эквивалентны - они равны побитовой операции «исключающее ИЛИ». Программа gf_xor позволяет использовать побитовое исключающее или двух чисел:

Unix-Prompt> gf_xor 15 7
8
Unix-Prompt> gf_xor 8 7
15
Unix-Prompt> gf_xor 230498 2738947
2772833
Unix-Prompt> gf_xor 2772833 230498
2738947
Unix-Prompt>

Программа gf_mult принимает три аргумента: a, b и w, и выводит произведение a и b в GF (2 w) . Программа gf_div выполняет деление, а программа gf_inverse возвращает мультипликативное обратное число в GF (2 w):

 

Unix-Prompt> gf_mult 3 7 4
9
Unix-Prompt> gf_div 9 3 4
7
Unix-Prompt> gf_div 9 7 4
3
Unix-Prompt> gf_mult 1234567 2345678 32
1404360778
Unix-Prompt> gf_div 1404360778 1234567 32
2345678
Unix-Prompt> gf_div 1404360778 2345678 32
1234567
Unix-Prompt> gf_inverse 1404360778 32
106460795
Unix-Prompt> gf_mult 1404360778 106460795 32
1
Unix-Prompt>

Другие инструменты командной строки обсуждаются в конце этого документа.

Использование библиотеки

Файлы galois.h и galois.c реализуют библиотеку процедур для арифметики поля Галуа в GF (2 w) для w от 1 до 32. Библиотека написана на C, но будет работать и на C ++. Он специально разработан для w, равного 8, 16 и 32, но он также применим для любого другого значения w . Для меньших значений w (где таблицы умножения или логарифма умещаются в памяти) эти процедуры должны быть очень быстрыми.

В следующих разделах мы описываем процедуры, реализованные библиотекой.

 

1. Умножение и деление общего назначения: galois_single_multiply() and galois_single_divide()

Синтаксис этих двух вызовов:

int galois_single_multiply(int a, int b, int w);
int galois_single_divide(int a, int b, int w);

Galois_single_multiply () возвращает произведение a и b в GF (2 w ) , а galois_single_divide () возвращает qoutient a и b в GF (2 w ) . w может иметь любое значение от 1 до 32.

Решение использовать в этой процедуре обычные целые числа со знаком вместо целых чисел без знака было принято в основном для удобства. Это имеет значение только тогда, когда w равно 32, и в этом случае может быть установлен знаковый бит a , b или возвращаемые значения. Если это важно, просто преобразуйте целые числа в целые числа без знака. Процедуры в этой библиотеке будут работать независимо - когда w равно 32, они рассматриваются как потоки битов, а не целых чисел.

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

2. Умножение области байтов на одно число в GF(28), GF(216) and GF(232)

Обычное использование арифметики Поля Галуа - умножение области байтов на одно число. Это основная операция кодирования и декодирования Рида-Соломона. Эта библиотека предоставляет следующие три процедуры для выполнения умножения областей:

 

void galois_w08_region_multiply(char *region, int multby, int nbytes, char *r2, int add);
void galois_w16_region_multiply(char *region, int multby, int nbytes, char *r2, int add);
void galois_w32_region_multiply(char *region, int multby, int nbytes, char *r2, int add);

Они умножают область байтов, указанную параметром region и nbytes , на число multby в поле, указанном в имени процедуры. Region должен быть выровнен по длинному слову, иначе эти процедуры вызовут ошибку шины. У этих процедур есть три отдельные функции, обозначенные значениями r2 и add .

 

  1. Если r2 - NULL, байты в region заменяются их произведениями с multby.
  2. Если r2 не NULL и add равно нулю, то продукты помещаются в nbytes памяти, начиная с r2 . Эти две области не должны перекрываться, если r2 не меньше region.
  3. Если r2 не NULL, а add равно единице, то вычисляются продукты, а затем выполняется операция XOR с существующими байтами r2 .

Выполнение этих процедур настроено на очень быстрое. При w = 8 используется таблица умножения. Таблицы логарифма и обратного логарифма используются при w = 16, а семь таблиц умножения используются при w = 32 .

3. Выполнение операции XOR над областью байтов

Следующая процедура позволяет выполнять побитовое исключающее ИЛИ для области байтов.

 

void galois_region_xor(char *r1, char *r2, char *r3, int nbytes);

R3 может быть равно r1 или r2, если вы хотите перезаписать любой из них. Опять же, все указатели должны быть выровнены по длинным словам.

Расширенное использование - быстрое единичное умножение и деление

Хотя galois_single_multiply () и galois_single_divide () являются хорошими инструментами общего назначения, их универсальность делает их медленнее, чем они должны быть. Для повышения производительности вы можете использовать их базовые реализации, описанные ниже:

 

4. Использование таблицы умножения: galois_multtable_multiply() and galois_multtable_divide()

Когда w мало, самый быстрый способ выполнить умножение и деление - использовать таблицы умножения и деления. Эти таблицы занимают 2 (2w + 2) байта каждая, поэтому они применимы только тогда, когда w достаточно мало. Например, при w = 8 это 256 КБ на таблицу.

Чтобы напрямую использовать таблицы умножения и деления, используйте одну или несколько из следующих подпрограмм

int galois_create_mult_tables(int w);   
int galois_multtable_multiply(int a, int b, int w);
int galois_multtable_divide(int a, int b, int w);
int *galois_get_mult_table(int w);
int *galois_get_div_table(int w);

Galois_create_mult_tables (w) создает таблицы умножения и деления для заданного значения w и сохраняет их внутри. Если вы вызовете его дважды с тем же значением w , он не создаст новые таблицы во второй раз. Вы можете вызвать его с разными значениями w, и таблицы будут храниться отдельно.

В случае успеха galois_create_mult_tables () вернет 0. В противном случае он вернет -1, и вся выделенная память будет освобождена.

Galois_multtable_multiply () и galois_multtable_divide () работают так же, как galois_single_multiply () и galois_single_divide () , за исключением того, что они предполагают, что вы вызвали galois_create_mult_tables () для соответствующего значения w и что это было успешно. Они не проверяют ошибки, поэтому, если вы не вызывали galois_create_mult_tables (), они будут сегментировать. Это решение было принято для скорости - хотя для небольших значений w (от 1 до 9) galois_single_multiply () использует galois_multtable_multiply (), это значительно медленнее из-за проверки ошибок, которую она выполняет.

Наконец, чтобы избавиться от накладных расходов на вызов процедур, подпрограммы galois_get_mult_table () и galois_get_div_table () возвращают сами таблицы. Произведение / частное a и b находится в элементе a * 2 w + b, который, конечно, можно быстро вычислить с помощью битовой арифметики как ((a << w) | b) . Вам не нужно вызывать galois_create_mult_tables () перед вызовом galois_get_mult_table () или galois_get_div_table ().

 

5. Использование таблиц журнала / анти-журнала: galois_logtable_multiply() and galois_logtable_divide()

Когда невозможно использовать таблицы умножения, следующий самый быстрый способ выполнить умножение и деление - это использовать журнальные и обратные журнальные таблицы, как описано в [P97] . Таблица журнала занимает 2 (w + 2) байта, а обратная таблица журнала занимает 3 * 2 (w + 2) байта, что означает, что можно обрабатывать средние значения w . Например, при w = 16 это 1 МБ таблиц.

Чтобы использовать таблицы журнала, используйте одну или несколько из следующих подпрограмм:

int galois_create_log_tables(int w);   
int galois_logtable_multiply(int a, int b, int w);
int galois_logtable_divide(int a, int b, int w);
int galois_log(int value, int w);
int galois_ilog(int value, int w);
int *galois_get_log_table(int w);
int *galois_get_ilog_table(int w);

Galois_create_log_tables (w) создает журнальные и обратные журнальные таблицы для заданного значения w и сохраняет их внутри. Если вы вызовете его дважды с тем же значением w , он не создаст новые таблицы во второй раз. Вы можете вызвать его с разными значениями w, и таблицы будут храниться отдельно.

В случае успеха функция galois_create_log_tables () вернет 0. В противном случае она вернет -1, и вся выделенная память будет освобождена.

Galois_logtable_multiply () и galois_logtable_divide () работают так же, как galois_single_multiply () и galois_single_divide (), за исключением того, что они предполагают, что вы вызвали galois_create_log_tables () для соответствующего значения w и что это было успешно. Они не проверяют ошибки, поэтому, если вы не вызывали galois_create_log_tables (), они будут сегментировать ошибки. Это решение было принято для скорости - хотя для средних значений w (от 10 до 22) galois_single_multiply () использует galois_logtable_multiply (), это значительно медленнее из-за проверки ошибок, которую она выполняет.

Galois_log () и galois_ilog () возвращают журнал и обратный журнал элемента GF (2 w ). Вы можете использовать их для умножения, используя следующую идентичность:

a * b = ilog[ (log[a] + log[b]) % ((1 << w)-1) ]
a / b = ilog[ (log[a] - log[b] + (1 << w)) % ((1 << w)-1) ]

Идентичность деления учитывает странное определение модульной арифметики с отрицательными числами в С.

Чтобы выполнить максимально быстрое умножение и деление с этими таблицами, вы должны получить доступ к самим таблицам с помощью galois_get_log_table (int w) и galois_get_ilog_table (int w) . Затем вы можете рассчитать произведение / частное a и b как:

a * b = ilog [ log[a] + log[b] ]
a / b = ilog [ log[a] - log[b] ]

Вам не нужно беспокоиться о модульной арифметике, потому что таблица ilog содержит три копии обратных журналов и определена для индексов от -2 w +1 до 2 2w -2 . Это экономит несколько инструкций.

 

6. Умножение со сдвигом и медленное деление: galois_shift_multiply() and galois_shift_divide()

Когда таблицы непригодны для использования, умножение и деление общего назначения осуществляется с помощью следующих двух процедур:

int galois_shift_multiply(int a, int b, int w);
int galois_shift_divide(int a, int b, int w);

Galois_shift_multiply () преобразует b в битовую матрицу w * w и умножает ее на битовый вектор a, чтобы создать вектор произведения. Вы можете увидеть квазиучебное описание этой техники в статье [P05]. Это значительно медленнее, чем методы, использующие таблицы. Однако он универсален и не требует предварительного выделения памяти.

Для деления Galois_shift_divide () также преобразует b в битовую матрицу, инвертирует ее, а затем умножает обратную матрицу на a. Таким образом, он * очень * медленный. Если я пойму, как реализовать это быстрее, я это сделаю.

Galois_single_multiply () использует galois_shift_multiply () для w между 23 и 31. Galois_single_divide () использует galois_shift_divide () для w между 23 и 32.

 

7. Частный случай w=32: galois_split_w8_multiply()

Наконец, для w = 32 определены следующие процедуры:

 

int galois_create_split_w8_tables();
int galois_split_w8_multiply(int a, int b);

 

Galois_create_split_w8_tables () создает семь таблиц по 256 КБ каждая. Galois_split_w8_multiply () использует эти таблицы для умножения 32-битных чисел, разбивая их на четыре восьмибитовых числа каждое, а затем выполняя шестнадцать умножений и исключающих ИЛИ для вычисления произведения. Это крутая техника, предложенная мне Ченг Хуангом из Microsoft, и она в 16 раз быстрее, чем использование galois_shift_multiply () .

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

Galois_single_multiply () использует galois_split_w8_multiply () для w = 32 .

Безопасность потоков

Единственно возможные условия гонки в этих кодах - это когда создаются различные таблицы. По этой причине galois_create_mult_tables () и galois_create_log_tables () должны быть защищены мьютексом, если безопасность потоков является проблемой.

Поскольку galois_single_multiply () и galois_single_divide () вызывают подпрограммы создания таблиц всякий раз, когда таблицы не существуют, если вы беспокоитесь о безопасности потоков, то для каждого значения w, которое вы будете использовать, вы должны убедиться, что первый вызов galois_single_multiply ( ) или galois_single_divide () защищен. После этого никакой защиты не требуется.

Тестирование приложений

Программы gf_mult, gf_div, gf_log, gf_ilog gf_inverse и gf_xor просты и позволяют тестировать различные подпрограммы для различных значений w .

Gf_basic_tester и gf_xor_tester проверяют и правильность, и скорость. Вызовите gf_xor_tester без аргументов, чтобы проверить скорость gf_region_xor () в вашей системе. Вот он, Macbook, процессор которого немного занят другими делами:

Unix-Prompt> gf_xor_tester
XOR Tester
Seeding random number generator with 1172533188
Passed correctness test -- doing 10-second timing
1827.79986 Megabytes of XORs per second
Unix-Prompt>

Gf_basic_tester принимает следующие аргументы командной строки:

После проверки на корректность gf_basic_tester проверяет скорость. Есть три особых случая. Когда method = default и w равно 8, 16 и 32, gf_basic_tester также проверяет скорость gf_w xx _region_multiply () .

Например (опять же, на моем MacBook):

Unix-Prompt> gf_basic_tester 16 default 100000
W: 16
Method: default
Seeding random number generator with 1172533569
Doing 100000 trials for single-operation correctness.
Passed Single-Operations Correctness Tests.

Doing galois_w16_region_multiply correctness test.
Passed galois_w16_region_multiply correctness test.

Speed Test #1: 10 Seconds of Multiply operations
Speed Test #1: 42.23862 Mega Multiplies per second
Speed Test #2: 10 Seconds of Divide operations
Speed Test #2: 43.42448 Mega Divides per second

Doing 10 seconds worth of region_multiplies - Three tests:
   Test 0: Overwrite initial region
   Test 1: Products to new region
   Test 2: XOR products into second region

   Test 0: 253.45548 Megabytes of Multiplies per second
   Test 1: 238.59569 Megabytes of Multiplies per second
   Test 2: 167.99968 Megabytes of Multiplies per second

Reference