Вопрос

Я знаю, как декодировать 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;
    }
}

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

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

/// Возвращает количество байтов, необходимых для кодирования кодовой точки в 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],
];

Ветвления

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

            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

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

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

        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]

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

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

Ответ

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
}

Тонкости

Примечания

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