mirror of
https://github.com/kovidgoyal/kitty.git
synced 2026-11-16 13:08:25 +00:00
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.
124 lines
4.7 KiB
Python
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'])
|