#!/usr/bin/env python # License: GPLv3 Copyright: 2026, Kovid Goyal # 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 ' 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'])