Arbitrary Precision — удобная C++ библиотека для работы с длинными целыми числами

Предисловие

Вопреки тому, что авторских C++ библиотек для длинных целых очень много, мне было трудно найти решение, которое было бы простым в использовании на всех этапах (интеграция зависимости, разработка, релиз с зависимостями). Авторские библиотеки имеют одну или несколько проблем реализации: используютв качестве базы счисления, нужна компиляция исходников, не оттестированные, неполный интерфейс (отсутствуют побитовые операторы), не кроссплатформенные. Что касается известных библиотек, то они далеко не просты в использовании:

• Boost.Multiprecision - это часть огромного фреймворка. Для больших проектов это отлично, так как в Boost много полезных вещей, но мы далеко не каждый день пишем большие проекты. Кроме того, в Boost длинное целое со знаком хранит несоответствующий размеру диапазон значений, так как у него ещё один бит под знак.

• GNU MP - это C библиотека, требует отдельной компиляции и нацелена на Unix-подобные системы. Даже с C++ обёрткой её далеко не просто скомпилировать и использовать.

• Crypto++ (https://github.com/weidai11/cryptopp) - самый простой из трёх, но обязательно надо компилировать исходники, с чем не всегда хочется возиться.

Все эти библиотеки отличные для больших и серьёзных проектов. Но есть и простые ситуации: студент первого или второго курса, который хочет сделать более-менее реальный RSA, хотя бы с точки зрения количества бит; программист разрабатывает свой проект, стартап, или даже коммерческий PoC, где не хотелось бы тратить много времени на добавление внешних библиотек, но в то же время не хочется рисковать и брать что-то не совсем надёжное. Авторские библиотеки очень часто протестированы не самым убедительным способом.

Также, в Java, C# и Python длинное целое доступно "из коробки". Всё это подтолкнуло меня к написанию собственной реализации, с надеждой, что в будущем она кому-то будет полезной.

О библиотеке

Arbitrary Precision размещена на GitHub: https://github.com/arbitrary-precision/ap.
В будущем планируется поддерживать длинные числа с плавающей запятой, предлагать более богатый функционал, при этом не изменяя фундаментальному качеству - простота на всех этапах.

Arbitrary Precision как библиотека обладает такими качествами:

• Header-only (по умолчанию, с возможностью включить опцию компиляции).

• Кроссплатформенность (GCC, MSVC, не должно быть проблем и с другими).

• Совместима с разными стандартами (C++11, C++14, C++17).

• Не генерирует предупреждений.

• Тщательно протестирована.

• Интуитивная.

Версия 1.2.0, актуальная на момент написания статьи, предлагает типы для знакового и беззнакового длинного целого фиксированного размера со следующим интерфейсом:

• Конструкторы копирования и перемещения. Перегружены для свободного преобразования между разными экземплярами класса длинного целого.

• Все операторы и конструкторы перегружены для работы с базовыми целыми типами.

• Конструктор, методы и операторы для инициализации из std::string, const char*. Преобразование вstd::string с поддержкой базы до 16.

• Все бинарные арифметические и побитовые операторы (кроме сдвига), их варианты с присваиванием и операторы сравнения перегружены для всех базовых целых типов и для всех экземпляров класса длинного целого.

• Операторы сдвига в качестве правого операнда принимают только базовые целые типы (пока что).

• Все унарные операторы (~, +, -, ++, --).

• Операторы ввода и вывода с распознаванием флагов базы для вывода.

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

Добавление библиотеки в проект элементарное. Нужно скачать исходный код и подключить заголовок ap.hpp (где бы он не находился, обычно это будет <ap/ap.hpp>). В глобальном пространстве имён доступно два шаблона: знаковый ap_int<size_t> и беззнаковый ap_uint<size_t>, которые в качестве параметра принимают размер типа в битах.

Нет смысла детально расписывать и демонстрировать использование операторов сравнения, арифметических и побитовых операторов во всевозможных ситуациях. Эти типы ведут себя точно так же, как и обычный int и unsigned int. Краткий пример:

#include <iostream>
#include <ap/ap.hpp>

ap_int<256> fact(ap_uint<256> val)
{
    ap_int<256> result = 1; // Инициализация копированием.
    for (ap_int<128> i = 1; i <= val; ++i) // Инкремент, сравнение разных типов.
    {
        result *= i; // Умножение разных типов.
    }
    return result;
}

int main()
{
    std::cout << fact(30) << std::endl; // Неявно, конструирование с базовых типов разрешено
    std::cout << fact(ap_int<128>(30)) << std::endl;  // Неявно, тип меньше размером.
    std::cout << fact(ap_uint<256>(30)) << std::endl; // Тот же тип.
    std::cout << fact(ap_int<256>(30)) << std::endl;  // Неявно, та же ширина.
    // std::cout << fact(ap_uint<512>(30)) << std::endl; // Ошибка, необходимо явно привести тип.     
    return 0;
}

Список важных моментов, которые следует помнить при использовании:

• Знаковые числа ведут себя так, будто они представлены в дополнительном коде (изнутри это не так). Диапазон значений соответствует размеру, указанному в качестве параметра шаблона.

• Деление на ноль задействует обычный сценарий (просто делит на ноль).

• Сдвиги арифметические. Если сдвиг происходит на количество битов, большее, чем размер типа, то результат 0. Если это была операция сдвига вправо и число было отрицательным, то результат -1.

• Размер типа в битах должен быть строго больше unsigned long long.

• Размер типа в битах должен быть кратен размеру AP_WORD - типа, который используется для хранения данных (unsigned int по умолчанию).

Более интересным является взаимодействие со строками. Основным методом класса для преобразования из строки является set:

integer& set(const char* str, index_t size = 0, index_t base = 0, const char* digits = AP_DEFAULT_STR);       
// str    - строка, представляющая значение.
// size   - размер строки. По умолчанию определяется при помощи strlen.
// base   - база числа, используемая строкой. По умолчанию определяется автоматически.
// digits - система знаков для отображения значения. По умолчанию "0123456789ABCDEF".

Этот метод вызывается другими вариантами:

// set() для std::string.
integer& set(const std::string& str, index_t base = 0, const char* digits = AP_DEFAULT_STR);
// Конструкторы.
explicit integer(const std::string& str, index_t base = 0, const char* digits = AP_DEFAULT_STR);
explicit integer(const char* str, index_t size = 0, index_t base = 0, const char* digits = AP_DEFAULT_STR);         
// Операторы присваивания.
integer& operator=(const std::string& str)
integer& operator=(const char* str)

Чтобы преобразовать в строку, есть два способа:

// Гибкий вариант.
std::string str(index_t base = AP_DEFAULT_STR_BASE, const char* digits = AP_DEFAULT_STR) const;        
// base   - база, в которую надо преобразовать. По умолчанию 10.
// digits - набор символ, который нужно использовать. По умолчанию "0123456789ABCDEF".

// Преобразовывает в десятичное число.
explicit operator std::string() const;

Пример использования:

#include <iostream>
#include "ap/ap.hpp"

int main()
{
    ap_int<128> a{"0b1"}; // Тривиальное преобразование, автоматическое определение базы. 
    ap_int<128> b{std::string("-Z"), 3, "XYZ"}; // Собственная система знаков.
    ap_int<128> c;
    c = "3"; // Присваивание.
    ap_int<128> d; 
    d.set("-1009736", 4, 2); // Явное указание размера строки 4 и базы 2. Т.е. "-100", или же -4.                      
    
    // Десятичное представление, 1 -2 3 -4:
    std::cout << std::string(a) << ' ' << std::string(b) << ' ' << std::string(c) << ' ' << std::string(d) << '\n';
    // Двоичное представление, 0b1 -0b10 0b11 -0b100:
    std::cout << a.str(2) << ' ' << b.str(2) << ' ' << c.str(2) << ' ' << d.str(2) << '\n';
    // Собственное представление в троичной системе, Y -Z YX -YY:
    std::cout << a.str(3, "XYZ") << ' ' << b.str(3, "XYZ") << ' ' << c.str(3, "XYZ") << ' ' << d.str(3, "XYZ") << '\n';         
}

Нюансы:

• Вне зависимости от базы, преобразованная строка имеет представление "знак и модуль".

• Если при преобразовании в строку указана база 2, 8 или 16, то всегда добавляется префикс.

Также перегружены операторы ввода-вывода. Тут ничего особенного. Ввод - чтение строки и преобразование из нее. Вывод - преобразование в строку, если установлены флаги std::ios_base::oct или std::ios_base::hex то будет использована соответствующая база.

Режим компиляции исходников

Если определить макрос AP_USE_SOURCES, то .cpp файлы должны быть скомпилированы отдельно. Это опция для тех, кто предпочитает компиляцию, а не header-only подход. Если макрос AP_USE_SOURCES не определён, а .cpp всё равно компилируют, то эту ситуацию обработает compile guard (на примере asm.*):

// asm.hpp
#ifndef DEOHAYER_AP_ASM_HPP
#define DEOHAYER_AP_ASM_HPP

// ...
// Объявления функций.
// ...

// Если .cpp не компилируются - включить их в .hpp.
#ifndef AP_USE_SOURCES
#define DEOHAYER_AP_ASM_CPP 0 // Для совместимости с compile guard.
#include "asm.cpp"
#endif

#endif

// asm.cpp
#ifndef DEOHAYER_AP_ASM_CPP
#define DEOHAYER_AP_ASM_CPP 1 // Случай компиляции.
#endif
// Код не будет проигнорирован только если значения совпадают.
// .hpp устанавливает макрос в 0, поэтому код попадёт в .hpp файл.
// .cpp устанавливает макрос в 1, а при случайной компиляции AP_USE_SOURCES не определён.
// код после if для компилируемой версии .cpp файла в таком случае просто будет отброшен.      
#if (DEOHAYER_AP_ASM_CPP == 1) == defined(AP_USE_SOURCES)

// ...
// Определения функций.
// ...

#endif

Быстродействие

Данные замерялись простым способом. Для указанного размера целого числа генерируется левый операнд, где значение занимает 25-50% размера и правый операнд, где значение занимает 12-25% размера. Дальше выполняется операция, и замеряется время исполнения для AP и Boost. В таблице указано соотношение AP/Boost.

Версия компилятора GCC: Ubuntu 7.5.0-3ubuntu1~18.04:

AP несущественно проигрывает Boost на больших значениях (1.1-1.5 раза), деление же намного лучше. Малые значения пока что не оптимизированы, из-за этого такая заметная разница. (2-6 раз).

Примечание: для замера использовалась программа https://github.com/arbitrary-precision/ws/blob/master/src/measure/measure.cpp. Из-за того, что Boost использует __int128 при компиляции с GCC, пришлось сконфигурировать AP, чтобы она тоже использовала этот тип (корневой CMakeLists.txt):

add_executable(measure ${MEASURE_SRC_FILES})
target_compile_options(measure PUBLIC
  -DAP_WORD=unsigned\ long\ long
  -DAP_DWORD=unsigned\ __int128
) 

__int128 не полностью поддерживается сейчас - он ломает взаимодействие с базовыми типами. На операции с длинными числами это не влияет, они работают корректно.

Внутреннее устройство

Вся библиотека базируется на трёх типах:

• word_t, или слово. Аналог limb-ов в GNU MP и Boost, служит для хранения данных. Этот тип можно задать через макрос AP_WORD.

• dword_t, или двойное слово. Аналог limb в GNU MP и Boost, служит для выполнения операций и хранения промежуточных значений. Этот тип можно задать через макрос AP_DWORD, размер должен быть ровно в два раза больше, чем размер word_t.

• index_t, аналог size_t.

Можно выделить пять основных сущностей библиотеки:

• Шаблон integer<size_t Size, bool Sign> (как контейнер значения, integer.hpp) - его частичными специализациями являются ap_int<size_t> и ap_uint<size_t>.

• dregister<T> (core.hpp), или "регистр" - POD тип, единое легковесное представление длинного целого. Хранит указатель на массив слов (word_t), T и есть типом указателя - const word_t* или word_t* в зависимости от того, разрешена ли запись значения. Остальные поля - размер массива, размер значения (сколько слов задействовано в данный момент), и знак.

• Внешние функции (integer.hpp) - все методы integer<size_t, bool> и все внешние операторы, перегруженные для него. Работают на только на уровне класса integer<size_t, bool>. Ответственность - обеспечение взаимодействия всевозможных типов.

• Внутренние функции (integer_api.*) - набор функций, которые использует integer в своих методах. Работают на уровне dregister<T>. Разделены на две группы - для знаковых и беззнаковых, не накладывают никаких ограничений на операнды. Ответственность - подготовка операндов для вызова алгоритмических функций, корректная расстановка знаков, нормализация после выполнения алгоритма (о ней чуть ниже).

• Алгоритмические функции (asm.*) - являются чистым алгоритмом, работают с dregister<T>, но интерпретируют его исключительно как беззнаковое целое. Кроме того, они накладывают строгие ограничения на операнды и могут иметь очень специфическое поведение. Арифметические алгоритмы - это алгоритмы A, S, M, D из "Искусство программирования (Том 2)" Д. Кнута. Остальные написаны самостоятельно. Ответственность - выполнение операции, получение корректного с точки зрения беззнакового числа битового паттерна.

Нормализация, упомянутая выше, это процесс приведения знакового и беззнакового числа к нормальной форме:

• Размер должен быть установлен таким образом, что word_t с индексом [размер - 1] не равен нулю.

• Знак при размере 0 должен быть 0.

• (только знаковое) Арифметическое значение, представляемое dregister<T> числа не должно выходить за рамки диапазона , где n - битовый размер числа.

С первыми двумя пунктами всё вполне прозрачно: "-0" это недопустимое значение, а нули в начале старших разрядов ломают алгоритм деления и оперировать нулями не имеет смысла. Третий пункт обеспечивает то, что знаковое ведёт себя так, будто оно представлено в дополнительном коде. После выполнения операции проверяется старший бит массива слов. Если он 1, то весь массив перекидывается в его дополнительный код и числу выставляется знак "-". Это работает даже если ненулевым является исключительно старший бит (дополнительный код такого паттерна это он сам). После этого выполняется нормализация по первым двум пунктам.

Тестирование

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

В качестве эталонной библиотеки выбрана Boost.Multiprecision. Единое строковое представление - "знак и модуль" в шестнадцатеричной системе. Целое число в тестировании характеризуется следующими параметрами:

• Битовый размер. Большой (L, 512 бит) или малый (S, 256 бит).

• Размер (данных). Одно слово, 25%, 50%, 75%. 100% от битового размера (это всегда целое количество слов).

• Знаковость. Знаковое или беззнаковое.

• Битовый паттерн. Определено 10:

Всего отдельных комбинаций для абстрактной бинарной операции 80000:

• 8 комбинаций битовых размеров (левый операнд, правый операнд, результат) - LLL, LLS, LSL, LSS, SLL, SLS, SSL, SSS. Считается, что все три аргумента передаются независимо друг от друга.

• 25 комбинаций размеров (5 левый, 5 правый).

• 4 комбинации знаковости операндов (в отличие от битового размера, зависит от операндов).

• 100 комбинаций битовых паттернов (10 левый, 10 правый).

Эти тесты запускаются и для внешних, и для внутренних функций отдельно. Некоторые сценарии не релевантны, они отсеяны. Внешние функции никогда не могут иметь сценарий битовых размеров LLS или SSL (int + int != long long int), а внутренние не имеют функций, которые бы работали с операндами разной знаковости. Т.е. количество тестов 60000 и 40000 соответственно.

Отдельная проверка выглядит следующим образом:

1. Сгенерировать операнды заданного размера относительно заданного битового размера.

2. Инициализировать целые Boost, результат конвертировать в беззнаковою строку (т.е дополнительный код). Эту строку подогнать под заданные размер и знаковость третьего аргумента (хранящего результат).

3. Инициализировать операнды ap (для внешних функций это integer<size_t, bool>, для внутренних - dregister<T>. Затем выполнить операцию и просто конвертировать результат в строку, не выполняя никаких других превращений.

4. Сравнить полученные строки, они должны быть идентичны.

Реализовано это в репозитории ws, который был н енапрямую упомянут в "Быстродействие": https://github.com/arbitrary-precision/ws (подпроект src/validate). Детали реализации в этой статье приводиться не будут, это довольно большой объём информации.

Что в планах

• Написать тесты для взаимодействия с базовыми типами.

• Разобраться с C++20 и SpaceX оператором.

• Оптимизация унарных операторов.

• Написать специализацию integer<size_t, bool> для битового размера равному unsigned long long и меньше.

• Учесть существование __int128 и возможность существования ещё больших intX.

• Написание исчерпывающей документации как для использования, так и для разработки.

• Оптимизация работы с базовым типом.

• Оптимизация алгоритмов.

• Улучшить взаимодействие между signed и unsigned (избегать приведения типа).

• Расширить интерфейс дополнительными базовыми алгоритмами (sqrt, lcm, gcd, pow etc.).

• (floating<>).

• (Ассемблерная оптимизация).