Кодирование UTF-8 без ветвления

Можно ли кодировать UTF-8 без ветвлений?

Да.

Вопрос

Натан Голдбаум задал в чате Recurse вопрос:

Я знаю, как декодировать UTF-8 с помощью битовой математики и таблиц поиска (см. https://github.com/skeeto/branchless-utf8), но если я хочу преобразовать кодовую точку UTF-8, то можно ли сделать это без ветвлений?

Для начала, можно ли как-то написать эту функцию на C, которая возвращает количество байтов, необходимых для хранения байтов UTF-8 кодовой точки, без использования ветвления? Или для этого потребуется огромная таблица поиска?

int num_utf8_bytes_for_codepoint(uint32_t code) {     if (code <= 0x7F) {         return 1;     }     else if (code <= 0x07FF) {         return 2;     }     else if (code <= 0xFFFF) {         if ((code >= 0xD800) && (code <= 0xDFFF)) {             // суррогаты - это недопустимые кодовые точки UCS4             return -1;         }         return 3;         }     else if (code <= 0x10FFFF) {         return 4;     }     else {         // кодовая точка вне пределов интервала Unicode         return -1;     } }

Я поразмыслил на этим вопросом, но не смог сходу придумать, как это сделать без огромной таблицы поиска (2^32).

Почти полный ответ

Но потом Lorenz оставил такой комментарий:

Пока очень смутная идея: закодировать 32-битную кодовую точку в utf8, но хранить результат снова в 32-битном слове. Подсчитать количество начальных/конечных нулей, чтобы понять, сколько байтов необходимо. Записать четыре байта в буфер вывода, но смещать позицию в выводе только на действительно необходимое количество байтов.

Ага!

В начале будет от 12 до 32 нулей¹ — вполне разумный размер для таблицы поиска. Далее мы сможем искать другие параметры по длине (не больше 4).

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

/// Возвращает количество байтов, необходимых для кодирования кодовой точки в UTF-8. /// Возвращает 0 для суррогатов и значений вне интервала. const fn utf8_bytes_for_codepoint(codepoint: u32) -> usize {     let len = LEN[codepoint.leading_zeros() as usize] as usize;      // Обрабатывает суррогаты манипуляциями с битами.     // Rust гарантирует true == 1 и false == 0:     let surrogate_bit = ((codepoint >= 0xD800) && (codepoint <= 0xDFFF)) as usize;     // Расширяем этот один бит до трёх и используем обратное ему значение в качестве маски для длины     let surrogate_mask = surrogate_bit << 2 | surrogate_bit << 1 | surrogate_bit;      // Обрабатываем выходящие за пределы значения при помощи манипуляций с битами.     // К сожалению, они не точно выровнены с границей начальных нулей;     // самая большая кодовая точка - это U+10FFFF.     let exceeded_bit = (codepoint > 0x10_FFFF) as usize;     let exceeded_mask = exceeded_bit << 2 | exceeded_bit << 1 | exceeded_bit;      len & !surrogate_mask & !exceeded_mask }  /// Длина на основании количества начальных нулей. const LEN: [u8; 33] = [     // 0-10 начальных нулей: значение невалидно     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,     // 11-15 начальных нулей: 4 байта     4, 4, 4, 4, 4,     //16-20 начальных нулей: 3 байта     3, 3, 3, 3, 3,     // 21-24 начальных нулей: 2 байта     2, 2, 2, 2,     // 25-32 начальных нулей: 1 байт     1, 1, 1, 1, 1, 1, 1, 1, ];  /// Кодируем кодовую точку UTF-8. /// Возвращаем буфер и количество валидных байтов в буфере. /// /// Чтобы добавить эту кодовую точку к строке, добавляем все четыре байта в правильном порядке /// и записываем, что к строке было добавлено (usize) байтов. /// /// Возвращаем нулевую длину для недопустимых кодовых точек (суррогатов и значений вне интервала). pub fn branchless_utf8(codepoint: u32) -> ([u8; 4], usize) {     let len = utf8_bytes_for_codepoint(codepoint);     let buf = [         PREFIX[len][0] | ((codepoint >> SHIFT[len][0]) & MASK[len][0] as u32) as u8,         PREFIX[len][1] | ((codepoint >> SHIFT[len][1]) & MASK[len][1] as u32) as u8,         PREFIX[len][2] | ((codepoint >> SHIFT[len][2]) & MASK[len][2] as u32) as u8,         PREFIX[len][3] | ((codepoint >> SHIFT[len][3]) & MASK[len][3] as u32) as u8,     ];      (buf, len) }  type Table = [[u8; 4]; 5];  // Байтовый префикс для continuation byte. const CONTINUE: u8 = 0b1000_0000; const PREFIX: Table = [     [0u8; 4],     [0, 0, 0, 0],     [0b1100_0000, CONTINUE, 0, 0],     [0b1110_0000, CONTINUE, CONTINUE, 0],     [0b1111_0000, CONTINUE, CONTINUE, CONTINUE], ];  // Мы должны сделать так, чтобы самые старшие байты всегда находились в байте 0. const SHIFT: Table = [     [0u8; 4],     [0, 0, 0, 0],     [6, 0, 0, 0],     [12, 6, 0, 0],     [18, 12, 6, 0], ];  const MASK: Table = [     [0u8; 4],     [0x7f, 0, 0, 0],     [0x1f, 0x3f, 0, 0],     [0x0f, 0x3f, 0x3f, 0],     [0x07, 0x3f, 0x3f, 0x3f], ];

Ветвления

Никаких операторов if, циклов и других условных конструкций. То есть, вроде бы, ветвления нет?

… ну, на самом деле, это не так.

Если заглянуть в код (оптимизированный) в Compiler Explorer, то мы увидим, что ассемблерный код x86_64 имеет два разных вида ветвлений.

Подсчёт начальных нулей

Прямо в начале функции есть ветвление:

            test    esi, esi             je      .LBB0_1             bsr     eax, esi             xor     eax, 31             jmp     .LBB0_3     .LBB0_1:             mov     eax, 32     .LBB0_3:             mov     eax, eax

Я не понимал, что это такое, пока пошагово не выполнил код. Похоже, «особый» случай — это нулевой ввод (esi); в этом случае код возвращает 32.

Зачем нужен этот особый случай? В подсказке Compiler Explorer по команде bsr написано следующее:

Если содержимое операнда источника равно 0, то содержимое конечного операнда undefined.

То есть в процессорах x86_64 существует ветвление, сообщающее «32-битное нулевое значение имеет 32 начальных нулей». Иными словами, встроенный объект (intrinsic) «подсчёта начальных нулей» необязательно оказывается командой без ветвления. Возможно, в другой архитектуре это выглядит красивее!

Проверки границ

Другой переход, похоже, является слиянием множества проверок границ массива.

        cmp     eax, 4         ja      .LBB0_5         ... LBB0_5:         lea     rdx, [rip + .L__unnamed_5]         mov     esi, 5         mov     rdi, rax         call    qword ptr [rip + core::panicking::panic_bounds_check::h8307ccead484a122@GOTPCREL]

Все массивы переходов имеют одинаковую границу (4), поэтому компилятор может решить выполнить проверку только один раз, и при этом всё равно обеспечить гарантии безопасности Rust.

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

Но, похоже, константы настолько далеко не распространяются.

Устраняем ветвление

Изменив код и перейдя к небезопасному доступу к массивам, можно избавиться от проверки границ массивов. Но у нас по-прежнему остаётся ветвление подсчёта начальных нулей. Как от него избавиться?

Давайте ещё раз взглянем на код обработки значений вне интервала:

let exceeded_bit = (codepoint > 0x10_FFFF) as usize;

Здесь я сделал трюк с преобразованием типов из boolean (true или false) в integer
(1 или 0). Семантика Rust гарантирует безопасность такого преобразования, и с таким представлением может работать оборудование; оно не создаёт дополнительных условных конструкций после компиляции².

Я использовал эти преобразования boolean в integer для выполнения маскирования. А знаете, что ещё можно делать с integer?

Складывать их.

Ответ

Мы можем избавиться от всех ветвлений, изменив функцию вычисления длины:

const fn utf8_bytes_for_codepoint(codepoint: u32) -> usize {     let mut len = 1;     // В Rust true преобразуется в 1, а false - в 0, поэтому мы можем "просто" суммировать длины.     len += (codepoint > 0x7f) as usize;     len += (codepoint > 0x7ff) as usize;     len += (codepoint > 0xffff) as usize;      // Как и раньше:     let surrogate_bit = ((codepoint >= 0xD800) && (codepoint <= 0xDFFF)) as usize;     let surrogate_mask = surrogate_bit << 2 | surrogate_bit << 1 | surrogate_bit;     let exceeded_bit = (codepoint > 0x10_FFFF) as usize;     let exceeded_mask = exceeded_bit << 2 | exceeded_bit << 1 | exceeded_bit;      len & !surrogate_mask & !exceeded_mask }

И это ответ на вопрос Натана про определение количества байтов. Compiler explorer подтверждает, что при включенных оптимизациях эта функция не содержит ветвлений.

К счастью, это преобразование также позволило компилятору осознать, что len <= 4 на всех путях выполнения, и статически устранить проверку границ массивов. Благодаря этому весь код тоже избавился от ветвления. Победа!

Тонкости

Хоть в коде и нет ветвления, я не утверждаю, что он оптимизирован — моя единственная цель заключалась в доказательстве концепции отсутствия ветвлений. Я даже не проверял код бенчмарками!

Крис Уэллонс отмечает в своём посте о декодировании без ветвления, что декодер на основе DFA может иметь схожую производительность; SIMD и другие техники «используем то, что нам даёт оборудование», вероятно, будут даже лучше. Я бы не стал использовать свой кодировщик вместо того, который есть в вашей любимой стандартной библиотеке.

Также я не утверждаю, что он полезен. Но вы можете делать с кодом почти что угодно: я выпустил его под лицензией MIT. Полный код и тесты, которые я использовал для его сравнения с реализацией на Rust, находятся здесь.

Примечания

1. Я хотел сделать эту функцию определённой всюду (total function), поэтому поиск длины включает все значения от 0 до 32.
2. Разумеется, как мы видели выше, то, что делает компилятор, может быть непрозрачным. Я говорю лишь о том, что rustc +1.83 -O делает сегодня, у вас может быть другая картина.