ARSV/Docs/set9_ru.md

Реализация set:version в set9.c

Документ описывает экспериментальную реализацию reimplement/set9.c. Общий смысл механизма set:version и устройство исходного set.c разобраны в set:version_ru.md. Здесь основное внимание уделено отличиям set9.c: потоковому кодированию и декодированию, сортировке, двум LRU-кэшам и новому алгоритму сравнения отсортированных множеств.

Назначение

ALT RPM записывает наборы ELF-символов в версии зависимостей вида:

libfoo.so.X()(64bit) = set:<encoded-set>
libfoo.so.X()(64bit) >= set:<encoded-set>

Provides содержит хэши предоставляемых символов, а Requires — хэши символов, требуемых от конкретной библиотеки. rpmsetcmp() сравнивает декодированные множества по включению, а не как обычные RPM-версии.

set9.c сохраняет формат строк и Jenkins OAAT из исходной реализации. Поэтому его задача — изменить внутреннее представление и горячие пути, не меняя смысл корректных set-строк. Совпадение формата не устраняет фундаментальную вероятность коллизий: сравниваются усечённые 32-битные хэши, а не исходные имена символов.

Основные отличия от исходного set.c

Область	Исходный set.c	set9.c
Хранение имён	отдельный xstrdup() для каждого имени	общая растущая строковая арена и массив смещений
Сортировка	всегда qsort()	qsort() для < 128 элементов, LSD radix sort для остальных
Кодирование	отдельные массивы delta, битов и Base62	один поток hash -> delta -> Golomb-Rice -> Base62
Декодирование	сложный табличный декодер пар символов	простой потоковый декодер с 64-битным аккумулятором
Кэш	один кэш первого операнда на 256 записей	два независимых кэша по 512 записей, по одному на каждый операнд
Поиск в кэше	линейный просмотр и memmove()	хэш-бакеты и двусвязный LRU со сменой позиции за O(1)
Нормализация bpp	выполняется для каждого сравнения	выполняется при промахе кэша и сохраняется в записи кэша
Сравнение	флаги ge/le, sentinel-элементы и макросы прыжков	проверка мощности, memcmp() и sorted_subset()
Освобождение struct set	сама структура не освобождается	освобождаются арена, массив символов и сама структура

Публичный API

Как и исходная реализация, файл предоставляет пять функций:

int rpmsetcmp(const char *set1, const char *set2);

struct set *set_new(void);
void set_add(struct set *set, const char *sym);
const char *set_fini(struct set *set, int bpp);
struct set *set_free(struct set *set);

set_new()

Создаёт пустой struct set. Все счётчики и ёмкости устанавливаются в ноль, указатели — в NULL.

set_add()

Добавляет копию строки символа во внутреннюю строковую арену:

1. массив symbols_v увеличивается блоками по 1024 элемента;
2. строковая арена при первом выделении получает 4096 байт;
3. при нехватке места ёмкость арены удваивается, пока не вместит новую строку;
4. в symbols_v сохраняются смещение строки в арене и нулевое начальное значение хэша.

В отличие от хранения отдельных указателей, перемещение арены через xrealloc() не делает записи массива недействительными: в них находятся смещения, а не адреса строк.

set_fini()

Хэширует, сортирует и кодирует добавленные имена. Возвращаемая строка выделена через xstrdup() и не содержит префикс set:. Префикс добавляет вызывающий код, например mkset.

В set9.c контракт проверяется через assert():

set != NULL
set->cnt > 0
10 <= bpp <= 32

Это отличается от исходного set.c, где пустое множество или недопустимый bpp приводят к NULL. При сборке с NDEBUG проверки assert() исчезают, поэтому передавать некорректные аргументы нельзя.

set_free()

Освобождает строковую арену, массив symbols_v и сам struct set, затем возвращает NULL. Типичный вызов:

set = set_free(set);

rpmsetcmp()

Сравнивает две set-строки. Префикс set: у каждого операнда необязателен.

Результаты совместимы с исходным API:

Код	Значение
1	первое множество строго содержит второе
0	множества равны
-1	первое множество строго содержится во втором
-2	множества несравнимы по включению
-3	ошибка метаданных или декодирования первого операнда
-4	ошибка метаданных или декодирования второго операнда

В типичном RPM-вызове первым операндом остаётся Provides, вторым — Requires.

Формат set-строки

После необязательного set: строка имеет структуру:

<bpp><Mshift><payload>

Первые два символа кодируют числа формулой:

value = character + 7 - 'a';
character = value - 7 + 'a';

Ограничения:

10 <= bpp <= 32
7 <= Mshift <= 31
Mshift < bpp
payload не пуст

payload использует алфавит:

0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ

Его числовые значения расположены как 0..9, a..z, A..Z. Символ Z имеет значение 61 и одновременно служит escape-маркером для исходных шестибитных значений 61, 62 и 63.

Внутреннее представление создаваемого множества

struct set {
    size_t cnt;
    size_t symbols_cap;
    size_t strings_len;
    size_t strings_cap;
    char *strings;
    struct symbols {
        size_t offset;
        unsigned hash;
    } *symbols_v;
};

Здесь:

• cnt — число добавленных имён;
• symbols_cap — ёмкость массива метаданных;
• strings_len и strings_cap — занятая и выделенная части строковой арены;
• strings — последовательность NUL-терминированных имён;
• offset — начало конкретного имени относительно strings;
• hash — хэш, вычисляемый только при set_fini().

Такое представление сокращает число отдельных выделений памяти при построении больших наборов.

Работа set_fini()

Полный путь выглядит так:

строковая арена и offsets
  | Jenkins OAAT + mask(bpp)
  v
массив struct symbols с хэшами
  | qsort или LSD radix sort
  v
отсортированные хэши
  | предупреждения о коллизиях + удаление повторов
  v
массив уникальных хэшей
  | потоковый delta + Golomb-Rice + Base62
  v
строка <bpp><Mshift><payload>

Jenkins OAAT и усечение

Для каждого имени вычисляется тот же Jenkins one-at-a-time hash, что и в исходном файле. Начальное состояние равно 0x9e3779b9. Результат ограничивается младшими bpp битами:

unsigned mask = (bpp < 32) ? (1u << bpp) - 1 : ~0u;
hash_value = hash(symbol) & mask;

sort_symbols()

Для малых наборов (count < 128) используется qsort(). Для больших наборов применяется стабильная LSD radix sort по байтам хэша:

1. число проходов равно ceil(bpp / 8);
2. на каждом проходе строятся 256 счётчиков/смещений;
3. элементы стабильно распределяются по текущему байту;
4. источник и приёмник меняются местами;
5. если итог оказался во временном массиве, он копируется назад.

Поскольку перед сортировкой хэш уже ограничен bpp битами, обработки ceil(bpp / 8) байтов достаточно. Временный массив размером count размещается на стеке.

Коллизии и повторяющиеся символы

После сортировки соседние равные хэши проверяются попарно. Для разных строк печатается:

warning: hash collision: <left> <right>

Две одинаковые строки предупреждения не создают. Затем все одинаковые хэш-значения схлопываются в одно. Поэтому настоящая хэш-коллизия после предупреждения всё равно становится одним элементом кодируемого множества — это свойство исходного формата.

Выбор Mshift

Параметр Golomb-Rice вычисляется как:

Mshift = bpp - floor(log2(count)) - 1

После этого значение ограничивается диапазоном 7..31 и проверяется условие Mshift < bpp. Идея та же, что в исходной реализации: при примерно равномерном распределении хэшей средняя дельта близка к 2^bpp / count.

Потоковый encode_set()

Исходный set.c сначала создаёт массив дельт, затем массив по одному байту на бит и лишь потом Base62-строку. В set9.c эти стадии объединены.

Для каждого отсортированного хэша вычисляется:

unsigned delta = current - previous;
unsigned q = delta >> Mshift;
unsigned r = delta & ((1u << Mshift) - 1);

В encode_writer последовательно добавляются:

q нулевых битов
1 — разделитель
Mshift младших битов r

Все биты идут младшими вперёд (LSB-first), как и в исходном формате.

struct encode_writer

"Писатель" содержит:

• uint64_t bits — накопленные ещё не выведенные биты;
• filled — число занятых битов;
• escaped — ожидание второй половины escape-пары;
• pending_high — старшие два бита значения 61, 62 или 63;
• output — текущую позицию в выходной строке.

encode_writer_put() добавляет обычное поле битов. encode_writer_zeros() добавляет длинную unary-последовательность нулей блоками не более 56 бит, чтобы аккумулятор оставался в пределах uint64_t. encode_writer_flush() выводит накопленные Base62-цифры.

В обычном состоянии потребляется шесть потоковых битов. Если значение равно 61, 62 или 63:

1. выводится Z;
2. различие между 61/62/63 сохраняется как два старших бита следующего символа;
3. из потока для следующего символа берутся только четыре бита.

При завершении неполный символ дополняется нулями. После payload записывается \0.

Метаданные декодируемой строки

Для декодирования используется struct set_meta:

struct set_meta {
    const char *str;
    const char *payload;
    size_t len;
    size_t payload_len;
    int bpp;
    int Mshift;
    int bit_capacity;
    int value_capacity;
};

Подготовка разделена на две части.

set_meta_init() — быстрая проверка

Функция читает только начало строки:

1. проверяет наличие двух метасимволов и хотя бы одного символа payload;
2. декодирует и проверяет bpp;
3. декодирует и проверяет Mshift;
4. сохраняет str, payload, bpp и Mshift.

На этой стадии strlen() не вызывается. Это позволяет сначала выполнить дешёвую проверку и поискать уже готовую запись в кэше.

set_meta_fini() — вычисление размеров

Функция вызывается только при промахе кэша:

len            = strlen(str)
payload_len    = len - 2
bit_capacity   = payload_len * 6
value_capacity = bit_capacity / (Mshift + 1)

bit_capacity является верхней границей: обычный символ даёт шесть битов, а два символа escape-пары дают десять битов, то есть не больше двенадцати. Каждое Golomb-Rice-значение требует как минимум Mshift + 1 бит. Если места нет даже для одного значения, строка отклоняется.

Потоковое декодирование

Путь декодирования объединяет три логических стадии:

Base62 payload
  | decode_chunk()
  v
6- или 10-битные блоки
  | q-state + r-state
  v
Golomb-Rice delta
  | previous += delta
  v
отсортированные хэши

Отдельные массивы битов и дельт не создаются.

Таблица char_to_num[]

Таблица из 256 элементов классифицирует любой байт:

• 0..60 — обычная Base62-цифра;
• 61 — Z;
• 0xff — конец строки;
• 0xee — недопустимый символ.

Индекс берётся как unsigned char, поэтому байты с установленным старшим битом тоже безопасно попадают в диапазон таблицы и отклоняются как недопустимые.

decode_chunk()

Обычный символ со значением меньше 61 возвращает шесть битов. При Z функция читает следующий символ и:

1. отклоняет конец строки сразу после Z;
2. отклоняет не-Base62 символ;
3. отклоняет комбинацию старших битов 11, которая создала бы новый Z;
4. собирает один 10-битный блок из значения 61/62/63 и четырёх младших битов второго символа.

Таким образом escape-пара сразу преобразуется в исходные десять потоковых битов.

decode_set()

Декодер хранит ещё не обработанные биты в uint64_t bits, а их количество — в filled. Для каждого значения он проходит два состояния.

Unary-часть q

Если аккумулятор пуст, загружается следующий блок. Полностью нулевой блок целиком прибавляется к q. Иначе __builtin_ctzll(bits) находит число нулей до разделительной единицы. Нули и сама единица удаляются из аккумулятора.

Остаток r

Пока доступно меньше Mshift битов, загружаются следующие блоки. Затем младшие Mshift битов образуют остаток, а дельта восстанавливается как:

unsigned delta = (q << Mshift) | r;

Дельта сразу превращается в исходный хэш:

previous += delta;
hash_arr[count++] = previous;

Завершение строки

Конец payload допустим в состоянии чтения q, если осталось не более пяти нулевых битов Base62-дополнения. Более длинный нулевой хвост даёт внутреннюю ошибку -10.

Конец строки во время набора Mshift битов остатка означает незавершённое значение и даёт внутреннюю ошибку -11. Ошибки decode_chunk() также возвращаются вверх. Публичный rpmsetcmp() скрывает конкретный внутренний код и преобразует его в -3 или -4 в зависимости от операнда.

Нормализация точности: downsample_set()

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

target_bpp = min(bpp1, bpp2)

Один вызов downsample_set() уменьшает точность с bpp + 1 до bpp:

1. маска равна (1u << bpp) - 1;
2. бинарным поиском находится первый элемент с удаляемым старшим битом;
3. исходный отсортированный массив делится на две отсортированные половины;
4. у второй половины удаляется старший бит;
5. половины сливаются как два отсортированных массива;
6. появившиеся после усечения дубликаты удаляются.

Если требуется убрать несколько битов, операция повторяется по одному биту. В set9.c результат нормализации сохраняется в кэше, поэтому та же строка при том же target_bpp не проходит этот цикл повторно.

Два кэша декодированных множеств

cache_decode_set() обслуживает два независимых кэша:

cache_id = 0 — первый операнд
cache_id = 1 — второй операнд

Каждый кэш содержит до CACHE_SIZE = 512 записей и 1024 бакета. Разделение не даёт потоку часто повторяющихся Requires вытеснять кэш Provides и наоборот, хотя реальный эффект зависит от порядка вызовов решателя зависимостей.

Ключ записи

Для быстрого предварительного отбора вычисляется fingerprint:

str[0] | (str[2] << 8) | (str[3] << 16)

Он смешивается с target_bpp, после чего выбирается бакет. Совпадения fingerprint недостаточно: успешный hit требует также равного target_bpp и полного strcmp() строки. Поэтому коллизия fingerprint влияет только на длину цепочки, но не подменяет декодированное множество.

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

Устройство записи

Одним xmalloc() выделяются:

struct cache_ent
массив unsigned для хэшей
копия исходной строки

Запись хранит fingerprint, исходную строку, число элементов и target_bpp.

Промах

При промахе происходят следующие шаги:

1. set_meta_fini() вычисляет длины и верхнюю границу числа значений;
2. выделяется новая запись;
3. decode_set() создаёт отсортированный массив хэшей;
4. при необходимости массив поэтапно уменьшается до target_bpp;
5. строка и метаданные копируются в запись;
6. запись добавляется в хэш-бакет и в начало логического LRU.

LRU

Все записи одного кэша образуют двусвязный список от oldest к newest. При hit запись отцепляется от текущего места и становится newest; это не требует сдвига массива записей. При заполненном кэше удаляется oldest, включая поиск ссылки на него в соответствующей цепочке бакета.

Сравнение в rpmsetcmp()

Последовательность работы:

1. снять set:, если он присутствует;
2. выполнить set_meta_init() для обеих строк;
3. выбрать минимальный target_bpp;
4. получить первый операнд из кэша 0 или декодировать его;
5. если строки полностью одинаковы, вернуть 0;
6. получить второй операнд из кэша 1 или декодировать его;
7. сравнить мощности и содержимое нормализованных массивов.

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

Равная мощность

Нормализованные массивы отсортированы и не содержат дубликатов. Если cnt1 == cnt2, два множества могут быть либо равны, либо несравнимы. Поэтому достаточно:

memcmp(hash_arr1, hash_arr2, cnt1 * sizeof(unsigned))

Совпадение даёт 0, различие — -2.

Разная мощность

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

cnt1 > cnt2: set2 ⊆ set1 ? 1  : -2
cnt1 < cnt2: set1 ⊆ set2 ? -1 : -2

Саму проверку выполняет sorted_subset(small, large).

sorted_subset()

Алгоритм выбирается по отношению размеров:

jump = large_count / small_count;

Если jump < 4, используется обычное линейное слияние: указатель большого массива двигается до текущего элемента малого. Для близких по размеру множеств это последовательный проход с хорошей локальностью.

Если jump >= 4, вызывается step_lower_bound(). Функция сначала делает шаги примерно на среднее расстояние между искомыми элементами, затем делит шаг пополам, пока не найдёт первый элемент, который не меньше искомого. Это позволяет пропускать части большого массива при разреженном малом множестве без sentinel-значений и выхода за границы.

При первом отсутствующем элементе sorted_subset() возвращает ложь.

SELF_TEST

При SELF_TEST компилируется main(), который проверяет только публичный API на коротких наборах:

1. строгое надмножество возвращает 1;
2. равные множества возвращают 0;
3. строгое подмножество возвращает -1;
4. пересекающиеся несравнимые множества возвращают -2;
5. выделенные строки и оба объекта освобождаются.

В отличие от исходного set.c, встроенный тест является smoke-тестом, а не полной проверкой совместимости.

"Карта функций"

Функция	Роль
set_new()	создание контейнера символов
set_add()	добавление имени в строковую арену
set_free()	освобождение контейнера
hash()	Jenkins OAAT
sort_symbols()	выбор qsort() или radix sort
encode_golomb_Mshift()	вычисление параметра Golomb-Rice
encode_writer_*()	потоковая упаковка битов в Base62
encode_set()	объединённые delta, Golomb-Rice и Base62
set_fini()	полный путь от имён до set-строки
set_meta_init()	быстрая проверка заголовка строки
set_meta_fini()	длины и верхние границы буферов
decode_chunk()	чтение обычного или escape Base62-блока
decode_set()	объединённые Base62, Golomb-Rice и delta
cache_decode_set()	два бакетных LRU-кэша
downsample_set()	уменьшение точности на один бит
step_lower_bound()	прыжок и уточнение позиции в большом массиве
sorted_subset()	проверка включения отсортированных множеств
rpmsetcmp()	публичное сравнение set-строк