Add more 2-stage lookup tables

9 files changed, 619 insertions, 386 deletions

diff --git a/gen/prop/gcb b/gen/prop/gcb
index 4565d40..06685b0 100755
--- a/gen/prop/gcb
+++ b/gen/prop/gcb
@@ -104,7 +104,7 @@ def main() -> None:
 		cs = set(Cs)
 
 		sz_s1 = len(Cs) * isize(len(cs) - 1)
-		sz_s2 = len(cs) * bs * 2
+		sz_s2 = len(cs) * bs
 		sz = sz_s1 + sz_s2
 
 		if sz < smallest:
diff --git a/gen/prop/hst b/gen/prop/hst
index a2765fd..8af4a4b 100755
--- a/gen/prop/hst
+++ b/gen/prop/hst
@@ -83,7 +83,7 @@ def main() -> None:
 		cs = set(Cs)
 
 		sz_s1 = len(Cs) * isize(len(cs) - 1)
-		sz_s2 = len(cs) * bs * 2
+		sz_s2 = len(cs) * bs
 		sz = sz_s1 + sz_s2
 
 		if sz < smallest:
diff --git a/gen/prop/inpc b/gen/prop/inpc
index 6a8561f..c4d35ef 100755
--- a/gen/prop/inpc
+++ b/gen/prop/inpc
@@ -83,7 +83,7 @@ def main() -> None:
 		cs = set(Cs)
 
 		sz_s1 = len(Cs) * isize(len(cs) - 1)
-		sz_s2 = len(cs) * bs * 2
+		sz_s2 = len(cs) * bs
 		sz = sz_s1 + sz_s2
 
 		if sz < smallest:
diff --git a/gen/prop/insc b/gen/prop/insc
index 7ed2b96..9ee3a34 100755
--- a/gen/prop/insc
+++ b/gen/prop/insc
@@ -1,63 +1,101 @@
-#!/bin/sh
-
-set -e
-cd "${0%/*}/../.."
-exec >lib/unicode/prop/uprop_get_insc.c
-
-gawk '
-BEGIN {
-	FS = "( *#.*| +; +)"
-
-	print "/* This file is autogenerated by gen/prop/insc; DO NOT EDIT. */"
-	print ""
-	print "#include \"_bsearch.h\""
-	print "#include \"macros.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] = "INSC_" toupper($2)
-	}
-}
-
-END {
-	print "static constexpr enum uprop_insc lookup_lat1[LATIN1_MAX] = {"
-	for (i = 0; i < 0x100; i++) {
-		if (props[i])
-			printf "\t[0x%02X] = %s,\n", i, props[i]
-	}
-	print "};"
-	print ""
-	print "static const struct {"
-	print "\trune lo, hi;"
-	print "\tenum uprop_insc val;"
-	print "} lookup[] = {"
-
-	for (i = 0x100; 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_insc, lookup, INSC_OTHER)"
-	print ""
-	print "enum uprop_insc"
-	print "uprop_get_insc(rune ch)"
-	print "{"
-	print "\treturn ch < lengthof(lookup_lat1) ? lookup_lat1[ch] : mlib_lookup(ch);"
-	print "}"
-}
-' data/IndicSyllabicCategory | sed 's/\s*$//'
+#!/usr/bin/python3
+
+import math
+
+from lib import *
+
+
+longest = 0
+
+def parse(file: str) -> list[bool]:
+	global longest
+
+	xs = ['INSC_OTHER'] * 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 = 'INSC_' + 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/insc; 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_insc 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_insc
+uprop_get_insc(rune ch)
+{{
+	return stage2[stage1[ch / {blksize}]][ch % {blksize}];
+}}''')
+
+def main() -> None:
+	cwd_init()
+	xs = parse('data/IndicSyllabicCategory')
+
+	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('lib/unicode/prop/uprop_get_insc.c', 'w') as f:
+		sys.stdout = f
+		genfile(Cs, blksize)
+
+	report_size(len(xs), smallest)
+
+if __name__ == '__main__':
+	main()
diff --git a/gen/prop/jg b/gen/prop/jg
index e88442d..c0cc31a 100755
--- a/gen/prop/jg
+++ b/gen/prop/jg
@@ -1,52 +1,101 @@
-#!/bin/sh
-
-set -e
-cd "${0%/*}/../.."
-exec >lib/unicode/prop/uprop_get_jg.c
-
-gawk '
-BEGIN {
-	FS = "[ ;]+"
-
-	print "/* This file is autogenerated by gen/prop/jg; DO NOT EDIT. */"
-	print ""
-	print "#include \"_bsearch.h\""
-	print "#include \"rune.h\""
-	print "#include \"unicode/prop.h\""
-	print ""
-}
-
-/^[A-F0-9]/ {
-	n = split($1, a, /\.\./)
-	lo = strtonum("0X" a[1])
-	hi = strtonum("0X" a[n])
-
-	for (i = lo; i <= hi; i++)
-		props[i] = "JG_" toupper($2)
-}
-
-END {
-	print "static const struct {"
-	print "\trune lo, hi;"
-	print "\tenum uprop_jg val;"
-	print "} lookup[] = {"
-
-	for (i = 0; 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_jg, lookup, JG_NO_JOINING_GROUP)"
-	print ""
-	print "enum uprop_jg"
-	print "uprop_get_jg(rune ch)"
-	print "{"
-	print "\treturn ch < lookup[0].lo ? JG_NO_JOINING_GROUP : mlib_lookup(ch);"
-	print "}"
-}
-' data/DerivedJoiningGroup | sed 's/\s*$//'
+#!/usr/bin/python3
+
+import math
+
+from lib import *
+
+
+longest = 0
+
+def parse(file: str) -> list[bool]:
+	global longest
+
+	xs = ['JG_NO_JOINING_GROUP'] * 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 = 'JG_' + 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/jg; 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_jg 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_jg
+uprop_get_jg(rune ch)
+{{
+	return stage2[stage1[ch / {blksize}]][ch % {blksize}];
+}}''')
+
+def main() -> None:
+	cwd_init()
+	xs = parse('data/DerivedJoiningGroup')
+
+	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('lib/unicode/prop/uprop_get_jg.c', 'w') as f:
+		sys.stdout = f
+		genfile(Cs, blksize)
+
+	report_size(len(xs), smallest)
+
+if __name__ == '__main__':
+	main()
diff --git a/gen/prop/jt b/gen/prop/jt
index d8ca9ff..23a4c9e 100755
--- a/gen/prop/jt
+++ b/gen/prop/jt
@@ -1,62 +1,101 @@
-#!/bin/sh
-
-set -e
-cd "${0%/*}/../.."
-exec >lib/unicode/prop/uprop_get_jt.c
-
-gawk '
-BEGIN {
-	FS = "[ ;]+"
-
-	print "/* This file is autogenerated by gen/prop/jt; DO NOT EDIT. */"
-	print ""
-	print "#include \"_bsearch.h\""
-	print "#include \"macros.h\""
-	print "#include \"rune.h\""
-	print "#include \"unicode/prop.h\""
-	print ""
-}
-
-/^[A-F0-9]/ {
-	n = split($1, a, /\.\./)
-	lo = strtonum("0X" a[1])
-	hi = strtonum("0X" a[n])
-
-	for (i = lo; i <= hi; i++)
-		props[i] = "JT_" $2
-}
-
-END {
-	print "static constexpr enum uprop_jt lookup_lat1[] = {"
-	for (i = 0; i < 0x100; i++) {
-		if (i % 8 == 0)
-			printf "\t"
-		printf "%s%s", (props[i] ? props[i] : "JT_U") ",", \
-			i % 8 == 7 ? "\n" : " "
-	}
-	print "};"
-	print ""
-	print "static const struct {"
-	print "\trune lo, hi;"
-	print "\tenum uprop_jt 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_jt, lookup, JT_U)"
-	print ""
-	print "enum uprop_jt"
-	print "uprop_get_jt(rune ch)"
-	print "{"
-	print "\treturn ch < lengthof(lookup_lat1) ? lookup_lat1[ch] : mlib_lookup(ch);"
-	print "}"
-}
-' data/DerivedJoiningType | sed 's/\s*$//'
+#!/usr/bin/python3
+
+import math
+
+from lib import *
+
+
+longest = 0
+
+def parse(file: str) -> list[bool]:
+	global longest
+
+	xs = ['JT_U'] * 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 = 'JT_' + 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/jt; 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_jt 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_jt
+uprop_get_jt(rune ch)
+{{
+	return stage2[stage1[ch / {blksize}]][ch % {blksize}];
+}}''')
+
+def main() -> None:
+	cwd_init()
+	xs = parse('data/DerivedJoiningType')
+
+	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('lib/unicode/prop/uprop_get_jt.c', 'w') as f:
+		sys.stdout = f
+		genfile(Cs, blksize)
+
+	report_size(len(xs), smallest)
+
+if __name__ == '__main__':
+	main()
diff --git a/gen/prop/lb b/gen/prop/lb
index 2abab6c..e003d13 100755
--- a/gen/prop/lb
+++ b/gen/prop/lb
@@ -1,65 +1,101 @@
-#!/bin/sh
-
-set -e
-cd "${0%/*}/../.."
-exec >lib/unicode/prop/uprop_get_lb.c
-
-gawk '
-BEGIN {
-	FS = "( *#.*| *; +)"
-
-	print "/* This file is autogenerated by gen/prop/lb; DO NOT EDIT. */"
-	print ""
-	print "#include \"_bsearch.h\""
-	print "#include \"macros.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] = "LB_" $2
-	}
-}
-
-END {
-	print "static constexpr enum uprop_lb lookup_lat1[] = {"
-	for (i = 0; i < 0x100; i++) {
-		if (i % 8 == 0)
-			printf "\t"
-		printf "%-6s%s", (props[i] ? props[i] : "LB_XX") ",", \
-			i % 8 == 7 ? "\n" : " "
-	}
-	print "};"
-	print ""
-	print "static const struct {"
-	print "\trune lo, hi;"
-	print "\tenum uprop_lb val;"
-	print "} lookup[] = {"
-
-	for (i = 0x100; 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_lb, lookup, LB_XX)"
-	print ""
-	print "enum uprop_lb"
-	print "uprop_get_lb(rune ch)"
-	print "{"
-	print "\treturn ch < lengthof(lookup_lat1) ? lookup_lat1[ch] : mlib_lookup(ch);"
-	print "}"
-}
-' data/DerivedLineBreak | sed 's/\s*$//'
+#!/usr/bin/python3
+
+import math
+
+from lib import *
+
+
+longest = 0
+
+def parse(file: str) -> list[bool]:
+	global longest
+
+	xs = ['LB_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 = 'LB_' + 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/lb; 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_lb 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_lb
+uprop_get_lb(rune ch)
+{{
+	return stage2[stage1[ch / {blksize}]][ch % {blksize}];
+}}''')
+
+def main() -> None:
+	cwd_init()
+	xs = parse('data/DerivedLineBreak')
+
+	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('lib/unicode/prop/uprop_get_lb.c', 'w') as f:
+		sys.stdout = f
+		genfile(Cs, blksize)
+
+	report_size(len(xs), smallest)
+
+if __name__ == '__main__':
+	main()
diff --git a/gen/prop/nfXX_qc b/gen/prop/nfXX_qc
index fed603e..24fcf45 100755
--- a/gen/prop/nfXX_qc
+++ b/gen/prop/nfXX_qc
@@ -1,77 +1,110 @@
-#!/bin/sh
-
-set -e
-cd "${0%/*}/../.."
-
-for x in c d kc kd
-do
-	gawk -v s=$x '
-	BEGIN {
-		FS = "[ ;]+"
-
-		_default = "NF" toupper(s) "_QC_Y"
-
-		print "/* This file is autogenerated by gen/prop/nfXX_qc; DO NOT EDIT. */"
-		print ""
-		print "/* The macros.h include may be unused */"
-		print ""
-		print "#include \"_bsearch.h\""
-		print "#include \"macros.h\""
-		print "#include \"rune.h\""
-		print "#include \"unicode/prop.h\""
-		print ""
-	}
-
-	/^[A-F0-9]/ && $2 == "NF" toupper(s) "_QC" {
-		n = split($1, a, /\.\./)
-		lo = strtonum("0X" a[1])
-		hi = strtonum("0X" a[n])
-
-		for (i = lo; i <= hi; i++)
-			props[i] = "NF" toupper(s) "_QC_" $3
-		if (lo < 0x100)
-			want_lat1_tbl = 1
-	}
-
-	END {
-		if (want_lat1_tbl) {
-			print "static constexpr enum uprop_nf" s "_qc lookup_lat1[] = {"
-			for (i = 0; i < 0x100; i++) {
-				if (i % 8 == 0)
-					printf "\t"
-				printf "%s,%s", props[i] ? props[i] : _default, \
-					i % 8 == 7 ? "\n" : " "
-			}
-			print "};"
-			print ""
-		}
-
-		print "static const struct {"
-		print "\trune lo, hi;"
-		print "\tenum uprop_nf" s "_qc val;"
-		print "} lookup[] = {"
-
-		for (i = want_lat1_tbl ? 0x100 : 0; i <= 0x10FFFF; i++) {
-			if (!props[i])
+#!/usr/bin/python3
+
+import math
+
+from lib import *
+
+
+longest = 0
+TYPES = ['c', 'd', 'kc', 'kd']
+
+def parse(file: str, _type: str) -> list[bool]:
+	global longest
+
+	_type = _type.upper()
+
+	xs = [f'NF{_type}_QC_Y'] * 0x110000
+	with open(file, 'r') as f:
+		for line in f.readlines():
+			if (
+				len(line.strip()) == 0
+				or line[0] == '#'
+				or f'NF{_type}_QC' not in line
+			):
 				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_nf" s "_qc, lookup, " _default ")"
-		print ""
-		print "enum uprop_nf" s "_qc"
-		print "uprop_get_nf" s "_qc(rune ch)"
-		print "{"
-		if (want_lat1_tbl)
-			print "\treturn ch < lengthof(lookup_lat1) ? lookup_lat1[ch] : mlib_lookup(ch);"
-		else
-			print "\treturn ch < lookup[0].lo ? " _default " : mlib_lookup(ch);"
-		print "}"
-	}
-	' data/DerivedNormalizationProps \
-	| sed 's/\s*$//' >lib/unicode/prop/uprop_get_nf${x}_qc.c
-done
+
+			parts = line.split(';')
+			ranges = [int(x, 16) for x in parts[0].strip().split('..')]
+			prop = f'NF{_type}_QC_' + parts[2].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, _type: str) -> None:
+	Cs = cs
+	cs = list(dict.fromkeys(Cs))
+
+	print('''\
+/* This file is autogenerated by gen/prop/nfXX_qc; 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_nf{_type}_qc 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_nf{_type}_qc
+uprop_get_nf{_type}_qc(rune ch)
+{{
+	return stage2[stage1[ch / {blksize}]][ch % {blksize}];
+}}''')
+
+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_nf{_type}_qc.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)
diff --git a/gen/prop/nt b/gen/prop/nt
index 835bc3f..477789c 100755
--- a/gen/prop/nt
+++ b/gen/prop/nt
@@ -1,69 +1,107 @@
-#!/bin/sh
-
-set -e
-cd "${0%/*}/../.."
-exec >lib/unicode/prop/uprop_get_nt.c
-
-gawk '
-BEGIN {
-	FS = "( *#.*| +; +)"
-
-	map["Decimal"] = "DE"
-	map["Digit"]   = "DI"
-	map["Numeric"] = "NU"
-
-	print "/* This file is autogenerated by gen/prop/nt; 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] = "NT_" map[$2]
-	}
-}
 
-END {
-	print "static constexpr enum uprop_nt lookup_lat1[] = {"
-	for (i = 0; i < 0x100; i++) {
-		if (i % 8 == 0)
-			printf "\t"
-		printf "%-8s%s", (props[i] ? props[i] : "NT_NONE") ",", \
-			i % 8 == 7 ? "\n" : " "
-	}
-	print "};"
-	print ""
-	print "static const struct {"
-	print "\trune lo, hi;"
-	print "\tenum uprop_nt val;"
-	print "} lookup[] = {"
-
-	for (i = 0x100; 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_nt, lookup, NT_NONE)"
-	print ""
-	print "enum uprop_nt"
-	print "uprop_get_nt(rune ch)"
-	print "{"
-	print "\treturn ch < lengthof(lookup_lat1) ? lookup_lat1[ch] : mlib_lookup(ch);"
-	print "}"
+MAP = {
+	'Decimal': 'DE',
+	'Digit':   'DI',
+	'Numeric': 'NU',
 }
-' data/DerivedNumericType | sed 's/\s*$//'
+
+longest = 0
+
+def parse(file: str) -> list[bool]:
+	global longest
+
+	xs = ['NT_NONE'] * 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 = 'NT_' + MAP[parts[1].split('#')[0].strip()]
+			longest = max(longest, len(prop), len('NT_NONE'))
+
+			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/nt; 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_nt 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_nt
+uprop_get_nt(rune ch)
+{{
+	return stage2[stage1[ch / {blksize}]][ch % {blksize}];
+}}''')
+
+def main() -> None:
+	cwd_init()
+	xs = parse('data/DerivedNumericType')
+
+	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('lib/unicode/prop/uprop_get_nt.c', 'w') as f:
+		sys.stdout = f
+		genfile(Cs, blksize)
+
+	report_size(len(xs), smallest)
+
+if __name__ == '__main__':
+	main()