kitty/gen/utf8_decode_tables.py
Kovid Goyal b815054414
Much faster SIMD UTF-8 decoding of valid UTF-8
Decode 64 byte blocks of valid UTF-8 containing no ESC using the
approach of simdutf: blocks are validated with the lookup tables of
Keiser and Lemire and converted twelve bytes at a time using shuffles
looked up from a mask of the bytes that end code points, with fast
paths for runs of ASCII, two byte and three byte sequences. Anything
else, ESC, invalid UTF-8 and the end of the input, is decoded as
before.

The shuffle tables are generated by gen/utf8_decode_tables.py.

This decodes the text of the unicode benchmark 2.6 times faster, faster
than simdutf's own conversion with error checking, and speeds up the
unicode benchmark by ~8%.

The new AVX2 decoder is faster than the AVX-512 one, so remove the
AVX-512 decoder and use the AVX2 one on CPUs with AVX-512 as well.

Also add a test comparing the SIMD decoders with the scalar one on long
inputs, which exercise the decoding of blocks, as the existing tests use
short inputs.
2026-11-16 13:43:39 +05:30

124 lines
4.7 KiB
Python

#!/usr/bin/env python
# License: GPLv3 Copyright: 2026, Kovid Goyal <kovid at kovidgoyal.net>
# Generates the tables used by the SIMD UTF-8 decoder to convert up to twelve
# bytes of UTF-8 at a time into UTF-32, using the approach of simdutf
# (https://github.com/simdutf/simdutf).
#
# The decoder computes a bitmask of the bytes that are the last byte of a code
# point. The low twelve bits of this mask index utf8_decode_index which gives
# the row of utf8_decode_shuffles to use and how many bytes are consumed. The
# row is a byte shuffle that places the bytes of the leading code points into
# the lanes of a vector with the last byte of each code point in the lowest
# byte of its lane, from where they are combined into code points with a few
# shifts and masks. Depending on the lengths of the leading code points, one of
# three layouts is used:
#
# * Six code points of one or two bytes into 16 bit lanes
# * Four code points of one to three bytes into 32 bit lanes
# * Three code points of one to four bytes into 32 bit lanes
#
# Within a layout, the row is the lengths minus one of its code points, as the
# digits of a number with the first code point as the most significant digit.
import os
import sys
from collections.abc import Iterator
if __name__ == '__main__' and not __package__:
import __main__
__main__.__package__ = 'gen'
sys.path.insert(0, os.path.dirname(os.path.dirname(os.path.abspath(__file__))))
# (number of code points, maximum length of a code point, bytes per lane)
LAYOUTS = ((6, 2, 2), (4, 3, 4), (3, 4, 4))
def code_point_lengths(mask: int) -> list[int]:
# The lengths of the code points ending in the first twelve bytes
lengths, start = [], 0
for i in range(12):
if mask & (1 << i):
lengths.append(i + 1 - start)
start = i + 1
return lengths
def shuffles() -> tuple[list[list[int]], list[int]]:
rows: list[list[int]] = []
layout_starts: list[int] = []
for num, max_len, lane_size in LAYOUTS:
layout_starts.append(len(rows))
for idx in range(max_len**num):
lengths: list[int] = []
for _ in range(num):
lengths.append(idx % max_len + 1)
idx //= max_len
lengths.reverse()
row: list[int] = []
last = -1
for length in lengths:
last += length
# 255 has the high bit set, so the shuffle zeroes that lane byte
row += [last - j if j < length else 255 for j in range(lane_size)]
rows.append(row + [0] * (16 - len(row)))
return rows, layout_starts
def index(layout_starts: list[int], num_rows: int) -> list[tuple[int, int]]:
ans = []
for mask in range(4096):
lengths = code_point_lengths(mask)
for start, (num, max_len, lane_size) in zip(layout_starts, LAYOUTS):
if len(lengths) >= num and max(lengths[:num]) <= max_len:
row = 0
for length in lengths[:num]:
row = row * max_len + length - 1
ans.append((start + row, sum(lengths[:num])))
break
else:
# Not possible with valid UTF-8, which has at least three complete
# code points in any twelve bytes starting at a code point
ans.append((num_rows, 12))
return ans
def generate() -> Iterator[str]:
rows, layout_starts = shuffles()
yield '// Generated by gen/utf8_decode_tables.py, DO NOT EDIT.'
yield '// See that file for a description of these tables.'
yield ''
yield '#pragma once'
yield ''
yield '#include <stdint.h>'
yield ''
yield f'#define UTF8_DECODE_FOUR_CODE_POINTS_START {layout_starts[1]}'
yield f'#define UTF8_DECODE_THREE_CODE_POINTS_START {layout_starts[2]}'
yield f'#define UTF8_DECODE_NUM_SHUFFLES {len(rows)}'
yield ''
yield f'static const uint8_t utf8_decode_shuffles[{len(rows)}][16] = {{'
for row in rows:
yield ' {' + ', '.join(map(str, row)) + '},'
yield '};'
yield ''
yield '// The shuffle row and the number of bytes consumed, for each end of code point mask'
yield 'static const uint8_t utf8_decode_index[4096][2] = {'
entries = [f'{{{r}, {c}}}' for r, c in index(layout_starts, len(rows))]
for i in range(0, len(entries), 8):
yield ' ' + ', '.join(entries[i : i + 8]) + ','
yield '};'
def main(args: list[str] = sys.argv) -> None:
with open(os.path.join('kitty', 'utf8-decode-tables.h'), 'w') as f:
for line in generate():
print(line, file=f)
if __name__ == '__main__':
import runpy
m = runpy.run_path(os.path.dirname(os.path.abspath(__file__)))
m['main']([sys.executable, 'utf8-decode-tables'])