From 19621b67f7f23518df1c27d50c4d52dc99f6f65c Mon Sep 17 00:00:00 2001 From: Thomas Voss Date: Tue, 7 May 2024 23:07:38 +0200 Subject: Use a 2-stage lookup for u8wnext() and u8wcnt() --- gen/string/wbrk | 272 +++++++++++++++++++++++++++++++++++--------------------- 1 file changed, 169 insertions(+), 103 deletions(-) (limited to 'gen/string/wbrk') diff --git a/gen/string/wbrk b/gen/string/wbrk index 1966356..8016550 100755 --- a/gen/string/wbrk +++ b/gen/string/wbrk @@ -1,109 +1,175 @@ -#!/bin/sh - -set -e -cd "${0%/*}/../.." -exec >include/unicode/_wbrk.h - -gawk ' -BEGIN { - FS = " *(; *|#.*)" - - map["ALetter"] = "LE" - map["CR"] = "CR" - map["Double_Quote"] = "DQ" - map["E_Base"] = "EB" - map["E_Base_GAZ"] = "EBG" - map["E_Modifier"] = "EM" - map["Extended_Pictographic"] = "EXTPICT" - map["Extend"] = "EXTEND" - map["ExtendNumLet"] = "EX" - map["Format"] = "FO" - map["Glue_After_Zwj"] = "GAZ" - map["Hebrew_Letter"] = "HL" - map["Katakana"] = "KA" - map["LF"] = "LF" - map["MidLetter"] = "ML" - map["MidNumLet"] = "MB" - map["MidNum"] = "MN" - map["Newline"] = "NL" - map["Numeric"] = "NU" - map["Other"] = "XX" - map["Regional_Indicator"] = "RI" - map["Single_Quote"] = "SQ" - map["WSegSpace"] = "WSEGSPACE" - map["ZWJ"] = "ZWJ" - - print "/* This file is autogenerated by gen/string/wbrk; DO NOT EDIT. */" - print "" - print "#ifndef MLIB_UNICODE__WBRK_H" - print "#define MLIB_UNICODE__WBRK_H" - print "" - print "#include " - print "" - print "#include \"rune.h\"" - print "" - print "enum wbrk_prop : uint_least8_t {" - print "\tWBRK_XX = 0, /* Other */" - print "\tWBRK_CR, /* CR */" - print "\tWBRK_DQ, /* Double Quote */" - print "\tWBRK_EB, /* E Base */" - print "\tWBRK_EBG, /* E Base GAZ */" - print "\tWBRK_EM, /* E Modifier */" - print "\tWBRK_EOT, /* End of Text */" - print "\tWBRK_EX, /* ExtendNumLet */" - print "\tWBRK_EXTEND, /* Extend */" - print "\tWBRK_EXTPICT, /* Extended Pictographic */" - print "\tWBRK_EXTPICT_LE, /* Extended Pictographic and ALetter */" - print "\tWBRK_FO, /* Format */" - print "\tWBRK_GAZ, /* Glue After Zwj */" - print "\tWBRK_HL, /* Hebrew Letter */" - print "\tWBRK_KA, /* Katakana */" - print "\tWBRK_LE, /* ALetter */" - print "\tWBRK_LF, /* LF */" - print "\tWBRK_MB, /* MidNumLet */" - print "\tWBRK_ML, /* MidLetter */" - print "\tWBRK_MN, /* MidNum */" - print "\tWBRK_NL, /* Newline */" - print "\tWBRK_NU, /* Numeric */" - print "\tWBRK_RI, /* Regional Indicator */" - print "\tWBRK_SQ, /* Single Quote */" - print "\tWBRK_WSEGSPACE, /* WSegSpace */" - print "\tWBRK_ZWJ, /* ZWJ */" - print "};" - print "" - print "const struct {" - print "\trune lo, hi;" - print "\tenum wbrk_prop val;" - print "} wbrk_lookup[] = {" -} +#!/usr/bin/python3 + +import math -/^[A-F0-9]/ { - if (map[$2] == "") - next +from lib import * - n = split($1, a, /\.\./) - lo = strtonum("0X" a[1]) - hi = strtonum("0X" a[n]) - for (i = lo; i <= hi; i++) { - s = "WBRK_" map[$2] - if (props[i] == "WBRK_LE" && s == "WBRK_EXTPICT") - s = "WBRK_EXTPICT_LE" - props[i] = s - } +MAP = { + 'ALetter': 'LE', + 'CR': 'CR', + 'Double_Quote': 'DQ', + 'E_Base': 'EB', + 'E_Base_GAZ': 'EBG', + 'E_Modifier': 'EM', + 'Extended_Pictographic': 'EXTPICT', + 'Extend': 'EXTEND', + 'ExtendNumLet': 'EX', + 'Format': 'FO', + 'Glue_After_Zwj': 'GAZ', + 'Hebrew_Letter': 'HL', + 'Katakana': 'KA', + 'LF': 'LF', + 'MidLetter': 'ML', + 'MidNumLet': 'MB', + 'MidNum': 'MN', + 'Newline': 'NL', + 'Numeric': 'NU', + 'Other': 'XX', + 'Regional_Indicator': 'RI', + 'Single_Quote': 'SQ', + 'WSegSpace': 'WSEGSPACE', + 'ZWJ': 'ZWJ', } -END { - for (i = 0; i <= 0x10FFFF; i++) { - if (!props[i]) +longest = -1 + +def parse(*files: str) -> list[bool]: + global longest + + xs = ['WBRK_XX'] * 0x110000 + + lines = [] + for file in files: + with open(file, 'r') as f: + lines.extend(f.readlines()) + + for line in lines: + if len(line.strip()) == 0 or line[0] == '#': continue - for (lo = i; props[i] == props[i + 1]; i++) - ; - printf "\t{RUNE_C(0x%06X), RUNE_C(0x%06X), %s},\n", lo, i, props[i] - } - - print "};" - print "" - print "#endif /* !MLIB_UNICODE__WBRK_H */" -} -' data/WordBreakProperty data/emoji-data | sed 's/\s*$//' + + parts = line.split(';') + ranges = [int(x, 16) for x in parts[0].strip().split('..')] + + try: + prop = 'WBRK_' + MAP[parts[1].split('#')[0].strip()] + except KeyError: + continue + longest = max(longest, len(prop)) + + for i in range(ranges[0], ranges[len(ranges) - 1] + 1): + xs[i] = prop + return list(map(str, xs)) + +def genfile(cs: list[tuple[bool, ...]], blksize: int) -> None: + Cs = cs + cs = list(dict.fromkeys(Cs)) + + print('''\ +/* This file is autogenerated by gen/string/wbrk; DO NOT EDIT. */ + +#ifndef MLIB_UNICODE__WBRK_H +#define MLIB_UNICODE__WBRK_H + +#include + +#include "_attrs.h" +#include "_rune.h" + +enum uprop_wbrk : uint_least8_t { + WBRK_XX = 0, /* Other */ + WBRK_CR, /* CR */ + WBRK_DQ, /* Double Quote */ + WBRK_EB, /* E Base */ + WBRK_EBG, /* E Base GAZ */ + WBRK_EM, /* E Modifier */ + WBRK_EOT, /* End of Text */ + WBRK_EX, /* ExtendNumLet */ + WBRK_EXTEND, /* Extend */ + WBRK_EXTPICT, /* Extended Pictographic */ + WBRK_EXTPICT_LE, /* Extended Pictographic and ALetter */ + WBRK_FO, /* Format */ + WBRK_GAZ, /* Glue After Zwj */ + WBRK_HL, /* Hebrew Letter */ + WBRK_KA, /* Katakana */ + WBRK_LE, /* ALetter */ + WBRK_LF, /* LF */ + WBRK_MB, /* MidNumLet */ + WBRK_ML, /* MidLetter */ + WBRK_MN, /* MidNum */ + WBRK_NL, /* Newline */ + WBRK_NU, /* Numeric */ + WBRK_RI, /* Regional Indicator */ + WBRK_SQ, /* Single Quote */ + WBRK_WSEGSPACE, /* WSegSpace */ + WBRK_ZWJ, /* ZWJ */ +}; +''') + + print(f'static constexpr {typename(len(cs) - 1)} stage1[] = {{') + for i, c in enumerate(Cs): + print(f'%c%{len(str(len(cs) - 1))}d,' % ('\t' if i % 16 == 0 else ' ', cs.index(c)), end='') + if i % 16 == 15: + print() + print('};') + + print() + + ppc = columns(blksize, longest + 1) + print(f'static constexpr enum uprop_wbrk stage2[][{blksize}] = {{') + for c in cs: + for i in range(blksize // ppc): + print('\t{' if i == 0 else '\t ', end='') + for j in range(ppc): + print(c[i*ppc + j], end='') + if i < blksize // ppc - 1 or j < ppc - 1: + print(',', end='') + if j < ppc - 1: + print(' ' * (longest + 1 - len(c[i*ppc + j])), end='') + if i < blksize // ppc - 1: + print() + print('},') + print('};') + + print() + + print(f'''\ +[[_mlib_pure, _mlib_inline]] +static enum uprop_wbrk +uprop_get_wbrk(rune ch) +{{ + return stage2[stage1[ch / {blksize}]][ch % {blksize}]; +}} + +#endif /* !MLIB_UNICODE__WBRK_H */''') + +def main() -> None: + cwd_init() + xs = parse('data/WordBreakProperty', 'data/emoji-data') + + blksize = -1 + smallest = math.inf + + for bs in powers_of_2(): + if bs > len(xs): + break + Cs = [tuple(x) for x in chunks(xs, bs)] + cs = set(Cs) + + sz_s1 = len(Cs) * isize(len(cs) - 1) + sz_s2 = len(cs) * bs + sz = sz_s1 + sz_s2 + + if sz < smallest: + smallest = sz + blksize = bs + + Cs = [tuple(x) for x in chunks(xs, blksize)] + with open('include/unicode/_wbrk.h', 'w') as f: + sys.stdout = f + genfile(Cs, blksize) + + report_size(len(xs), smallest) + +if __name__ == '__main__': + main() -- cgit v1.2.3