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

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

Да.

Вопрос

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

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

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

Функция на C

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, находятся здесь.

Примечания

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

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