From d3cc478c3ebcfc65d89ddad7446e9652b50ab0df Mon Sep 17 00:00:00 2001
From: Thomas Voss <mail@thomasvoss.com>
Date: Fri, 3 May 2024 01:31:27 +0200
Subject: Add more 2-stage lookup tables
---
gen/prop/gcb | 197 +++++++++++++++++++++++++++++++++++-----------------------
gen/prop/hst | 156 ++++++++++++++++++++++++++++++----------------
gen/prop/inpc | 156 ++++++++++++++++++++++++++++++----------------
3 files changed, 320 insertions(+), 189 deletions(-)
(limited to 'gen')
diff --git a/gen/prop/gcb b/gen/prop/gcb
index 17d3136..4565d40 100755
--- a/gen/prop/gcb
+++ b/gen/prop/gcb
@@ -1,83 +1,122 @@
-#!/bin/sh
-
-set -e
-cd "${0%/*}/../.."
-exec >lib/unicode/prop/uprop_get_gcb.c
-
-gawk '
-BEGIN {
- FS = "( *#.*| *; +)"
-
- map["Control"] = "CN"
- map["CR"] = "CR"
- map["E_Base"] = "EB"
- map["E_Base_GAZ"] = "EBG"
- map["E_Modifier"] = "EM"
- map["Extend"] = "EX"
- map["Glue_After_Zwj"] = "GAZ"
- map["LF"] = "LF"
- map["L"] = "L"
- map["LV"] = "LV"
- map["LVT"] = "LVT"
- map["Other"] = "XX"
- map["Prepend"] = "PP"
- map["Regional_Indicator"] = "RI"
- map["SpacingMark"] = "SM"
- map["T"] = "T"
- map["V"] = "V"
- map["ZWJ"] = "ZWJ"
-
- print "/* This file is autogenerated by gen/prop/gcb; DO NOT EDIT. */"
- print ""
- print "#include \"_bsearch.h\""
- print "#include \"macros.h\""
- print "#include \"rune.h\""
- print "#include \"unicode/prop.h\""
- print ""
-}
+#!/usr/bin/python3
-/^[^#]/ {
- n = split($1, a, /\.\./)
- lo = strtonum("0X" a[1])
- hi = strtonum("0X" a[n])
+import math
+
+from lib import *
- for (i = lo; i <= hi; i++) {
- gsub(/^; /, "", $2)
- props[i] = "GCB_" map[$2]
- }
-}
-END {
- print "static constexpr enum uprop_gcb lookup_lat1[] = {"
- for (i = 0; i < 0x100; i++) {
- if (i % 8 == 0)
- printf "\t"
- printf "%-7s%s", (props[i] ? props[i] : "GCB_XX") ",", \
- i % 8 == 7 ? "\n" : " "
- }
- print "};"
- print ""
- print "static const struct {"
- print "\trune lo, hi;"
- print "\tenum uprop_gcb val;"
- print "} lookup[] = {"
-
- for (i = 0x100; i <= 0x10FFFF; i++) {
- if (!props[i])
- continue
- for (lo = i; props[lo] == props[i + 1]; i++)
- ;
- printf "\t{RUNE_C(0x%06X), RUNE_C(0x%06X), %s},\n", lo, i, props[i]
- }
-
- print "};"
- print ""
- print "_MLIB_DEFINE_BSEARCH(enum uprop_gcb, lookup, GCB_XX)"
- print ""
- print "enum uprop_gcb"
- print "uprop_get_gcb(rune ch)"
- print "{"
- print "\treturn ch < lengthof(lookup_lat1) ? lookup_lat1[ch] : mlib_lookup(ch);"
- print "}"
+MAP = {
+ 'Control': 'CN',
+ 'CR': 'CR',
+ 'E_Base': 'EB',
+ 'E_Base_GAZ': 'EBG',
+ 'E_Modifier': 'EM',
+ 'Extend': 'EX',
+ 'Glue_After_Zwj': 'GAZ',
+ 'LF': 'LF',
+ 'L': 'L',
+ 'LV': 'LV',
+ 'LVT': 'LVT',
+ 'Other': 'XX',
+ 'Prepend': 'PP',
+ 'Regional_Indicator': 'RI',
+ 'SpacingMark': 'SM',
+ 'T': 'T',
+ 'V': 'V',
+ 'ZWJ': 'ZWJ',
}
-' data/GraphemeBreakProperty | sed 's/\s*$//'
+
+longest = 0
+
+def parse(file: str) -> list[bool]:
+ global longest
+
+ xs = ['GCB_XX'] * 0x110000
+ with open(file, 'r') as f:
+ for line in f.readlines():
+ if len(line.strip()) == 0 or line[0] == '#':
+ continue
+
+ parts = line.split(';')
+ ranges = [int(x, 16) for x in parts[0].strip().split('..')]
+ prop = 'GCB_' + MAP[parts[1].split('#')[0].strip()]
+ longest = max(longest, len(prop))
+
+ for i in range(ranges[0], ranges[len(ranges) - 1] + 1):
+ xs[i] = prop
+ return xs
+
+def genfile(cs: list[tuple[bool, ...]], blksize: int) -> None:
+ Cs = cs
+ cs = list(dict.fromkeys(Cs))
+
+ print('''\
+/* This file is autogenerated by gen/prop/gcb; DO NOT EDIT. */
+
+#include "unicode/prop.h"
+''')
+
+ 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_gcb 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'''\
+enum uprop_gcb
+uprop_get_gcb(rune ch)
+{{
+ return stage2[stage1[ch / {blksize}]][ch % {blksize}];
+}}''')
+
+def main() -> None:
+ cwd_init()
+ xs = parse('data/GraphemeBreakProperty')
+
+ 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 * 2
+ sz = sz_s1 + sz_s2
+
+ if sz < smallest:
+ smallest = sz
+ blksize = bs
+
+ Cs = [tuple(x) for x in chunks(xs, blksize)]
+ with open('lib/unicode/prop/uprop_get_gcb.c', 'w') as f:
+ sys.stdout = f
+ genfile(Cs, blksize)
+
+ report_size(len(xs), smallest)
+
+if __name__ == '__main__':
+ main()
diff --git a/gen/prop/hst b/gen/prop/hst
index 3cb241d..a2765fd 100755
--- a/gen/prop/hst
+++ b/gen/prop/hst
@@ -1,55 +1,101 @@
-#!/bin/sh
-
-set -e
-cd "${0%/*}/../.."
-exec >lib/unicode/prop/uprop_get_hst.c
-
-gawk '
-BEGIN {
- FS = "( *#.*| +; +)"
-
- print "/* This file is autogenerated by gen/prop/hst; DO NOT EDIT. */"
- print ""
- print "#include \"_bsearch.h\""
- print "#include \"rune.h\""
- print "#include \"unicode/prop.h\""
- print ""
-}
-
-/^[^#]/ {
- n = split($1, a, /\.\./)
- lo = strtonum("0X" a[1])
- hi = strtonum("0X" a[n])
-
- for (i = lo; i <= hi; i++) {
- gsub(/^; /, "", $2)
- props[i] = "HST_" toupper($2)
- }
-}
-
-END {
- print "static const struct {"
- print "\trune lo, hi;"
- print "\tenum uprop_hst val;"
- print "} lookup[] = {"
-
- for (i = 0x1100; i <= 0x10FFFF; i++) {
- if (!props[i])
- continue
- lo = i
- while (props[lo] == props[i + 1])
- i++
- printf "\t{RUNE_C(0x%06X), RUNE_C(0x%06X), %s},\n", lo, i, props[i]
- }
-
- print "};"
- print ""
- print "_MLIB_DEFINE_BSEARCH(enum uprop_hst, lookup, HST_NA)"
- print ""
- print "enum uprop_hst"
- print "uprop_get_hst(rune ch)"
- print "{"
- print "\treturn ch < lookup[0].lo ? HST_NA : mlib_lookup(ch);"
- print "}"
-}
-' data/HangulSyllableType | sed 's/\s*$//'
+#!/usr/bin/python3
+
+import math
+
+from lib import *
+
+
+longest = 0
+
+def parse(file: str) -> list[bool]:
+ global longest
+
+ xs = ['HST_NA'] * 0x110000
+ with open(file, 'r') as f:
+ for line in f.readlines():
+ if len(line.strip()) == 0 or line[0] == '#':
+ continue
+
+ parts = line.split(';')
+ ranges = [int(x, 16) for x in parts[0].strip().split('..')]
+ prop = 'HST_' + parts[1].split('#')[0].strip()
+ longest = max(longest, len(prop))
+
+ for i in range(ranges[0], ranges[len(ranges) - 1] + 1):
+ xs[i] = prop
+ return xs
+
+def genfile(cs: list[tuple[bool, ...]], blksize: int) -> None:
+ Cs = cs
+ cs = list(dict.fromkeys(Cs))
+
+ print('''\
+/* This file is autogenerated by gen/prop/hst; DO NOT EDIT. */
+
+#include "unicode/prop.h"
+''')
+
+ 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_hst 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'''\
+enum uprop_hst
+uprop_get_hst(rune ch)
+{{
+ return stage2[stage1[ch / {blksize}]][ch % {blksize}];
+}}''')
+
+def main() -> None:
+ cwd_init()
+ xs = parse('data/HangulSyllableType')
+
+ 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 * 2
+ sz = sz_s1 + sz_s2
+
+ if sz < smallest:
+ smallest = sz
+ blksize = bs
+
+ Cs = [tuple(x) for x in chunks(xs, blksize)]
+ with open('lib/unicode/prop/uprop_get_hst.c', 'w') as f:
+ sys.stdout = f
+ genfile(Cs, blksize)
+
+ report_size(len(xs), smallest)
+
+if __name__ == '__main__':
+ main()
diff --git a/gen/prop/inpc b/gen/prop/inpc
index b4bd85c..6a8561f 100755
--- a/gen/prop/inpc
+++ b/gen/prop/inpc
@@ -1,55 +1,101 @@
-#!/bin/sh
-
-set -e
-cd "${0%/*}/../.."
-exec >lib/unicode/prop/uprop_get_inpc.c
-
-gawk '
-BEGIN {
- FS = "( *#.*| +; +)"
-
- print "/* This file is autogenerated by gen/prop/inpc; DO NOT EDIT. */"
- print ""
- print "#include \"_bsearch.h\""
- print "#include \"rune.h\""
- print "#include \"unicode/prop.h\""
- print ""
-}
-
-/^[^#]/ {
- n = split($1, a, /\.\./)
- lo = strtonum("0X" a[1])
- hi = strtonum("0X" a[n])
-
- for (i = lo; i <= hi; i++) {
- gsub(/^; /, "", $2)
- props[i] = "INPC_" toupper($2)
- }
-}
-
-END {
- print "static const struct {"
- print "\trune lo, hi;"
- print "\tenum uprop_inpc val;"
- print "} lookup[] = {"
-
- for (i = 0x900; i <= 0x10FFFF; i++) {
- if (!props[i])
- continue
- lo = i
- while (props[lo] == props[i + 1])
- i++
- printf "\t{RUNE_C(0x%06X), RUNE_C(0x%06X), %s},\n", lo, i, props[i]
- }
-
- print "};"
- print ""
- print "_MLIB_DEFINE_BSEARCH(enum uprop_inpc, lookup, INPC_NA)"
- print ""
- print "enum uprop_inpc"
- print "uprop_get_inpc(rune ch)"
- print "{"
- print "\treturn ch < lookup[0].lo ? INPC_NA : mlib_lookup(ch);"
- print "}"
-}
-' data/IndicPositionalCategory | sed 's/\s*$//'
+#!/usr/bin/python3
+
+import math
+
+from lib import *
+
+
+longest = 0
+
+def parse(file: str) -> list[bool]:
+ global longest
+
+ xs = ['INPC_NA'] * 0x110000
+ with open(file, 'r') as f:
+ for line in f.readlines():
+ if len(line.strip()) == 0 or line[0] == '#':
+ continue
+
+ parts = line.split(';')
+ ranges = [int(x, 16) for x in parts[0].strip().split('..')]
+ prop = 'INPC_' + parts[1].split('#')[0].strip().upper()
+ longest = max(longest, len(prop))
+
+ for i in range(ranges[0], ranges[len(ranges) - 1] + 1):
+ xs[i] = prop
+ return xs
+
+def genfile(cs: list[tuple[bool, ...]], blksize: int) -> None:
+ Cs = cs
+ cs = list(dict.fromkeys(Cs))
+
+ print('''\
+/* This file is autogenerated by gen/prop/inpc; DO NOT EDIT. */
+
+#include "unicode/prop.h"
+''')
+
+ 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_inpc 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'''\
+enum uprop_inpc
+uprop_get_inpc(rune ch)
+{{
+ return stage2[stage1[ch / {blksize}]][ch % {blksize}];
+}}''')
+
+def main() -> None:
+ cwd_init()
+ xs = parse('data/IndicPositionalCategory')
+
+ 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 * 2
+ sz = sz_s1 + sz_s2
+
+ if sz < smallest:
+ smallest = sz
+ blksize = bs
+
+ Cs = [tuple(x) for x in chunks(xs, blksize)]
+ with open('lib/unicode/prop/uprop_get_inpc.c', 'w') as f:
+ sys.stdout = f
+ genfile(Cs, blksize)
+
+ report_size(len(xs), smallest)
+
+if __name__ == '__main__':
+ main()
--
cgit v1.2.3