Skip to content

Commit 24a5890

Browse files
jkeiserjkeiser
committed
Add script I used to explain the lookup4 tables
1 parent 51b835f commit 24a5890

File tree

1 file changed

+163
-0
lines changed

1 file changed

+163
-0
lines changed

‎scripts/ruby/explain-utf8-validation-lookup-table.rb

Lines changed: 163 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,163 @@
1+
def expand_binary(*specs)
2+
specs.flat_map do |spec|
3+
values = [0]
4+
spec.each_char do |ch|
5+
case ch
6+
when '0'
7+
values = values.map { |v| v<<1 }
8+
when '1'
9+
values = values.map { |v| (v<<1)+1 }
10+
when '_'
11+
values = values.flat_map { |v| [ v<<1, (v<<1)+1 ] }
12+
else
13+
raise "Unknown char"
14+
end
15+
end
16+
values
17+
end
18+
end
19+
20+
MAX = 1<<12
21+
possible_values = Array.new(MAX)
22+
0.upto(MAX) do |i|
23+
possible_values[i] = {}
24+
end
25+
26+
categories = {
27+
"Too Long 1" => { binary: %w{0_______10__} },
28+
"Too Short" => { binary: %w{11______0___ 11______11__} },
29+
"5+ Byte" => { binary: %w{11111___10__} },
30+
"Overlong 2" => { binary: %w{1100000_10__} },
31+
"Overlong 3" => { binary: %w{11100000100_} },
32+
"Overlong 4" => { binary: %w{111100001000} },
33+
"Surrogate" => { binary: %w{11101101101_} },
34+
"Too Large" => { binary: %w{111101001001 11110100101_ 1111010110__ 1111011_10__} },
35+
"Two Conts" => { binary: %w{10______10__} },
36+
}
37+
categories.each do |(name,category)|
38+
category[:values] = expand_binary(*category[:binary])
39+
category[:values].each do |value|
40+
if possible_values[value][:category]
41+
raise "Value #{value.to_s(2)} already has error #{possible_values[value][:category]}"
42+
end
43+
possible_values[value][:category] = name;
44+
end
45+
category[:required_bits] = (0..8).map { || 0 }
46+
category[:bits] = (0..8).map { || 0 }
47+
end
48+
49+
# high1 = [102, 102, 102, 102, 102, 102, 102, 102, 128, 128, 128, 128, 37, 1, 21, 89]
50+
# low1 = [231, 163, 131, 131, 139, 203, 203, 203, 203, 203, 203, 203, 203, 219, 203, 203]
51+
# high2 = [25, 25, 25, 25, 25, 25, 25, 25, 230, 174, 186, 186, 25, 25, 25, 25]
52+
TOO_SHORT = 1<<0
53+
TOO_LONG = 1<<1
54+
OVERLONG_3 = 1<<2
55+
SURROGATE = 1<<4
56+
OVERLONG_2 = 1<<5
57+
TWO_CONTS = 1<<7
58+
TOO_LARGE = 1<<3
59+
TOO_LARGE_1000 = 1<<6
60+
OVERLONG_4 = 1<<6
61+
high1 = [
62+
TOO_LONG, TOO_LONG, TOO_LONG, TOO_LONG,
63+
TOO_LONG, TOO_LONG, TOO_LONG, TOO_LONG,
64+
TWO_CONTS, TWO_CONTS, TWO_CONTS, TWO_CONTS,
65+
TOO_SHORT | OVERLONG_2,
66+
TOO_SHORT,
67+
TOO_SHORT | OVERLONG_3 | SURROGATE,
68+
TOO_SHORT | TOO_LARGE | TOO_LARGE_1000 | OVERLONG_4
69+
]
70+
CARRY = TOO_SHORT | TOO_LONG | TWO_CONTS
71+
low1 = [
72+
CARRY | OVERLONG_3 | OVERLONG_2 | OVERLONG_4,
73+
CARRY | OVERLONG_2,
74+
CARRY,
75+
CARRY,
76+
CARRY | TOO_LARGE,
77+
CARRY | TOO_LARGE | TOO_LARGE_1000,
78+
CARRY | TOO_LARGE | TOO_LARGE_1000,
79+
CARRY | TOO_LARGE | TOO_LARGE_1000,
80+
CARRY | TOO_LARGE | TOO_LARGE_1000,
81+
CARRY | TOO_LARGE | TOO_LARGE_1000,
82+
CARRY | TOO_LARGE | TOO_LARGE_1000,
83+
CARRY | TOO_LARGE | TOO_LARGE_1000,
84+
CARRY | TOO_LARGE | TOO_LARGE_1000,
85+
CARRY | TOO_LARGE | TOO_LARGE_1000 | SURROGATE,
86+
CARRY | TOO_LARGE | TOO_LARGE_1000,
87+
CARRY | TOO_LARGE | TOO_LARGE_1000
88+
]
89+
high2 = [
90+
TOO_SHORT, TOO_SHORT, TOO_SHORT, TOO_SHORT,
91+
TOO_SHORT, TOO_SHORT, TOO_SHORT, TOO_SHORT,
92+
TOO_LONG | OVERLONG_2 | TWO_CONTS | OVERLONG_3 | TOO_LARGE_1000 | OVERLONG_4,
93+
TOO_LONG | OVERLONG_2 | TWO_CONTS | OVERLONG_3 | TOO_LARGE,
94+
TOO_LONG | OVERLONG_2 | TWO_CONTS | SURROGATE | TOO_LARGE,
95+
TOO_LONG | OVERLONG_2 | TWO_CONTS | SURROGATE | TOO_LARGE,
96+
TOO_SHORT, TOO_SHORT, TOO_SHORT, TOO_SHORT
97+
]
98+
0.upto(MAX-1) do |value|
99+
lookup = high1[(value >> 8) & 0x0F] & low1[(value >> 4) & 0x0F] & high2[value & 0x0F]
100+
category = possible_values[value][:category]
101+
if lookup != 0
102+
if !category
103+
raise "#{value.to_s(2).rjust(12, "0")} is not an error or two-cont value, but matches #{lookup.to_s(2).rjust(8, "0")}!"
104+
end
105+
possible_values[value][:bits] = (0..8).select { |bit| (lookup & (1 << bit)) != 0 }
106+
if possible_values[value][:bits].size == 1
107+
categories[category][:required_bits][possible_values[value][:bits][0]] += 1
108+
end
109+
possible_values[value][:bits].each do |bit|
110+
categories[category][:bits][bit] += 1
111+
end
112+
else
113+
if category
114+
raise "#{value.to_s(2).rjust(12, "0")} is a #{category}, but does not match the lookup tables!"
115+
end
116+
end
117+
end
118+
119+
# We now know which bits are required for each category.
120+
121+
bits = (0..8).map { || { required_for: {} } }
122+
123+
print "| Bit "
124+
categories.each do |(name, category)|
125+
print "| #{name} (#{category[:values].size})"
126+
end
127+
puts "|"
128+
129+
print "|---"
130+
categories.each do ||
131+
print "|---"
132+
end
133+
puts "|"
134+
135+
0.upto(7) do |bit|
136+
print "| #{bit}"
137+
categories.each do |(name,category)|
138+
print " | "
139+
if category[:required_bits][bit] > 0
140+
if category[:required_bits][bit] == category[:values].size
141+
print "REQ "
142+
else
143+
print "REQ #{category[:required_bits][bit]} / "
144+
end
145+
end
146+
if category[:bits][bit] == category[:values].size
147+
print "FULL"
148+
elsif category[:bits][bit] > 0
149+
print "#{category[:bits][bit]}"
150+
end
151+
end
152+
puts " |"
153+
end
154+
# Find out which categories are *covered* by
155+
# Find which bits are *required* for each category
156+
#
157+
158+
159+
160+
# bits.each_with_index do |bit, bit_value|
161+
# if bit_value[:categories].size == 1
162+
# end
163+
# actual_matches.

0 commit comments

Comments
 (0)