More 2-stage lookup tables

1 files changed, 120 insertions, 64 deletions

diff --git a/gen/prop/nfkc_Xcf b/gen/prop/nfkc_Xcf
index ba5a905..58c3abc 100755
--- a/gen/prop/nfkc_Xcf
+++ b/gen/prop/nfkc_Xcf
@@ -1,65 +1,121 @@
-#!/bin/sh
-
-set -e
-cd "${0%/*}/../.."
-
-for x in cf scf
-do
-	gawk -v s=$x '
-	BEGIN {
-		FS = "( *; *| *#.*)"
-
-		print "/* This file is autogenerated by gen/prop/nfkc_Xcf; DO NOT EDIT. */"
-		print ""
-		print "#include \"_bsearch.h\""
-		print "#include \"macros.h\""
-		print "#include \"rune.h\""
-		print "#include \"unicode/prop.h\""
-		print ""
-		print "#define M(...) ((struct rview)_(__VA_ARGS__))"
-		print "#define _(...) \\"
-		print "\t{(const rune []){__VA_ARGS__}, lengthof(((const rune []){__VA_ARGS__}))}"
-		print ""
-		print "static const struct {"
-		print "\trune lo, hi;"
-		print "\tstruct rview val;"
-		print "} lookup[] = {"
-	}
-
-	$2 == "NFKC_" toupper(s) {
-		n = split($1, xs, /\.\./)
-		lo = strtonum("0X" xs[1])
-		hi = strtonum("0X" xs[n])
-
-		for (i = lo; i <= hi; i++)
-			props[i] = $3 ? $3 : "-"
-	}
-
-	END {
-		for (i = 0; i <= 0x10FFFD; i++) {
-			if (!props[i])
+#!/usr/bin/python3
+
+import math
+
+from lib import *
+
+
+longest = 0
+TYPES = ['cf', 'scf']
+
+def parse(file: str, _type: str) -> list[bool]:
+	global longest
+
+	_type = _type.upper()
+
+	xs = ['_(SENTINAL)'] * 0x110000
+	with open(file, 'r') as f:
+		for line in f.readlines():
+			if (
+				len(line.strip()) == 0
+				or line[0] == '#'
+				or f'NFKC_{_type}' not in line
+			):
 				continue
-			for (lo = i; props[lo] == props[i + 1]; i++)
-				;
-			printf "\t{RUNE_C(0x%06X), RUNE_C(0x%06X), _(", lo, i
-			n = split(props[i] == "-" ? "" : props[i], xs, / /)
-			for (j = 1; j <= n; j++) {
-				printf "RUNE_C(0x%s)", xs[j]
-				if (j < n)
-					printf ", "
-			}
-			print ")},"
-		}
-
-		print "};"
-		print ""
-		print "_MLIB_DEFINE_BSEARCH(struct rview, lookup, M(ch))"
-		print ""
-		print "struct rview"
-		print "uprop_get_nfkc_" s "(rune ch)"
-		print "{"
-		print "\treturn ch < lookup[0].lo ? M(ch) : mlib_lookup(ch);"
-		print "}"
-	}
-	' data/DerivedNormalizationProps >lib/unicode/prop/uprop_get_nfkc_${x}.c
-done
+
+			parts = line.split(';')
+			ranges = [int(x, 16) for x in parts[0].strip().split('..')]
+			prop = ', '.join(
+				f'0x{x}' for x in parts[2].split('#')[0].strip().split()
+			)
+			prop = f'_({prop})'
+			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, _type: str) -> None:
+	Cs = cs
+	cs = list(dict.fromkeys(Cs))
+
+	print('''\
+/* This file is autogenerated by gen/prop/nfkc_Xcf; DO NOT EDIT. */
+
+#include "macros.h"
+#include "unicode/prop.h"
+
+#define M(...) ((struct rview)_(__VA_ARGS__))
+#define _(...) \\
+	{(const rune []){__VA_ARGS__}, lengthof(((const rune []){__VA_ARGS__}))}
+
+constexpr rune SENTINAL = 0x110000;
+''')
+
+	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 const struct rview 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'''\
+struct rview
+uprop_get_nfkc_{_type}(rune ch)
+{{
+	struct rview rv = stage2[stage1[ch / {blksize}]][ch % {blksize}];
+	return rv.len == 1 && rv.p[0] == SENTINAL ? M(ch) : rv;
+}}''')
+
+def main(_type: str) -> None:
+	cwd_init()
+	xs = parse('data/DerivedNormalizationProps', _type)
+
+	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(f'lib/unicode/prop/uprop_get_nfkc_{_type}.c', 'w') as f:
+		sys.stdout = f
+		genfile(Cs, blksize, _type)
+
+	report_size(len(xs), smallest)
+
+if __name__ == '__main__':
+	for _type in TYPES:
+		longest = 0
+		main(_type)