untested grapheme cluster boundary detection
[disorder] / scripts / make-unidata
1 #! /usr/bin/perl -w
2 #
3 # This file is part of DisOrder.
4 # Copyright (C) 2007 Richard Kettlewell
5 #
6 # This program is free software; you can redistribute it and/or modify
7 # it under the terms of the GNU General Public License as published by
8 # the Free Software Foundation; either version 2 of the License, or
9 # (at your option) any later version.
10 #
11 # This program is distributed in the hope that it will be useful, but
12 # WITHOUT ANY WARRANTY; without even the implied warranty of
13 # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 # General Public License for more details.
15 #
16 # You should have received a copy of the GNU General Public License
17 # along with this program; if not, write to the Free Software
18 # Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307
19 # USA
20 #
21 #
22 # Generate Unicode support tables
23 #
24 # This script will download data from unicode.org if the required files
25 # aren't in the current directory.
26 #
27 # After modifying this script you should run:
28 # make -C lib rebuild-unicode check
29 #
30 # Things not supported yet:
31 # - SpecialCasing.txt data for case mapping
32 # - Title case offsets
33 # - Some kind of hinting for composition
34 # - Word boundary support
35 # - ...
36 #
37 # NB the generated files DO NOT offer a stable ABI and so are not immediately
38 # suitable for use in a general-purpose library. Things that would need to
39 # be done:
40 # - Hide unidata.h from applications; it will never be ABI- or even API-stable.
41 # - Stablized General_Category values
42 # - Extend the unicode.h API to general utility rather than just what
43 # DisOrder needs.
44 # - ...
45 #
46 use strict;
47 use File::Basename;
48
49 sub out {
50 print @_ or die "$!\n";
51 }
52
53 sub key {
54 my $d = shift;
55 local $_;
56
57 return join("-", map($d->{$_}, sort keys %$d));
58 }
59
60 # Size of a subtable
61 #
62 # This can be varied to trade off the number of subtables against their size.
63 our $modulus = 128;
64
65 my %cats = (); # known general categories
66 my %data = (); # mapping of codepoints to information
67 my $max = 0; # maximum codepoint
68 my $maxccc = 0; # maximum combining class
69 my $maxud = 0;
70 my $minud = 0; # max/min upper case offset
71 my $maxld = 0;
72 my $minld = 0; # max/min lower case offset
73
74 # Make sure we have our desired input files. We explicitly specify a
75 # Unicode standard version to make sure that a given version of DisOrder
76 # supports a given version of Unicode.
77 sub need_input {
78 my $path = shift;
79 my $lpath = basename($path);
80 if(!-e $lpath) {
81 system("wget http://www.unicode.org/Public/5.0.0/ucd/$path");
82 chmod(0444, $lpath) or die "$lpath: $!\n";
83 }
84 }
85
86 need_input("UnicodeData.txt");
87 need_input("CaseFolding.txt");
88 need_input("auxiliary/GraphemeBreakProperty.txt");
89
90 # Read the main data file
91 open(STDIN, "<UnicodeData.txt") or die "UnicodeData.txt: $!\n";
92 while(<>) {
93 my @f = split(/;/, $_);
94 my $c = hex($f[0]); # codepoint
95 next if $c >= 0xE0000; # ignore various high-numbered stuff
96 # TODO justify this exclusion!
97 my $name = $f[1];
98 my $gc = $f[2]; # General_Category
99 my $ccc = $f[3]; # Canonical_Combining_Class
100 my $dm = $f[5]; # Decomposition_Type + Decomposition_Mapping
101 my $sum = hex($f[12]) || $c; # Simple_Uppercase_Mapping
102 my $slm = hex($f[13]) || $c; # Simple_Lowercase_Mapping
103 # recalculate the upper/lower case mappings as offsets
104 my $ud = $sum - $c;
105 my $ld = $slm - $c;
106 # update bounds on various values
107 $maxccc = $ccc if $ccc > $maxccc; # assumed never to be -ve
108 $minud = $ud if $ud < $minud;
109 $maxud = $ud if $ud > $maxud;
110 $minld = $ld if $ld < $minld;
111 $maxld = $ld if $ld > $maxld;
112 $data{$c} = {
113 "gc" => $gc,
114 "ccc" => $ccc,
115 "ud" => $ud,
116 "ld" => $ld,
117 };
118 if($dm ne '') {
119 if($dm !~ /</) {
120 # This is a canonical decomposition
121 $data{$c}->{canon} = $dm;
122 $data{$c}->{compat} = $dm;
123 } else {
124 # This is only a compatibility decomposition
125 $dm =~ s/^<.*>\s*//;
126 $data{$c}->{compat} = $dm;
127 }
128 }
129 $cats{$gc} = 1;
130 $max = $c if $c > $max;
131 }
132
133 # Grapheme break data
134 # NB we do this BEFORE filling in blanks so that the Hangul characters
135 # don't get filled in; we can compute their properties mechanically.
136 open(STDIN, "<GraphemeBreakProperty.txt") or die "GraphemeBreakProperty.txt: $!\n";
137 while(<>) {
138 chomp;
139 s/\s*\#.*//;
140 next if $_ eq '';
141 my ($range, $propval) = split(/\s*;\s*/, $_);
142 if($range =~ /(.*)\.\.(.*)/) {
143 for my $c (hex($1) .. hex($2)) {
144 if(exists $data{$c}) {
145 $data{$c}->{gbreak} = $propval;
146 }
147 }
148 } else {
149 my $c = hex($range);
150 if(exists $data{$c}) {
151 $data{$c}->{gbreak} = $propval;
152 }
153 }
154 }
155
156 # Round up the maximum value to a whole number of subtables
157 $max += ($modulus - 1) - ($max % $modulus);
158
159 # Make sure there are no gaps
160 for(my $c = 0; $c <= $max; ++$c) {
161 if(!exists $data{$c}) {
162 $data{$c} = {
163 "gc" => "Cn", # not assigned
164 "ccc" => 0,
165 "ud" => 0,
166 "ld" => 0
167 };
168 }
169 }
170 $cats{'Cn'} = 1;
171
172 # Read the casefolding data too
173 open(STDIN, "<CaseFolding.txt") or die "CaseFolding.txt: $!\n";
174 while(<>) {
175 chomp;
176 next if /^\#/ or $_ eq '';
177 my @f = split(/\s*;\s*/, $_);
178 # Full case folding means use status C and F.
179 # We discard status T, Turkish users may wish to change this.
180 if($f[1] eq 'C' or $f[1] eq 'F') {
181 my $c = hex($f[0]);
182 $data{$c}->{casefold} = $f[2];
183 # We are particularly interest in combining characters that
184 # case-fold to non-combining characters, or characters that
185 # case-fold to sequences with combining characters in non-initial
186 # positions, as these required decomposiiton before case-folding
187 my @d = map(hex($_), split(/\s+/, $data{$c}->{casefold}));
188 if($data{$c}->{ccc} != 0) {
189 # This is a combining character
190 if($data{$d[0]}->{ccc} == 0) {
191 # The first character of its case-folded form is NOT
192 # a combining character. The field name is the example
193 # explicitly mentioned in the spec.
194 $data{$c}->{ypogegrammeni} = 1;
195 }
196 } else {
197 # This is a non-combining character; inspect the non-initial
198 # code points of the case-folded sequence
199 shift(@d);
200 if(grep($data{$_}->{ccc} != 0, @d)) {
201 # Some non-initial code point in the case-folded for is NOT a
202 # a combining character.
203 $data{$c}->{ypogegrammeni} = 1;
204 }
205 }
206 }
207 }
208
209 # Generate the header file
210 open(STDOUT, ">unidata.h") or die "unidata.h: $!\n";
211
212 out("/* Automatically generated file, see scripts/make-unidata */\n",
213 "#ifndef UNIDATA_H\n",
214 "#define UNIDATA_H\n");
215
216 # TODO choose stable values for General_Category
217 out("enum unicode_gc_cat {\n",
218 join(",\n",
219 map(" unicode_gc_$_", sort keys %cats)), "\n};\n");
220
221 out("enum unicode_flags {\n",
222 " unicode_normalize_before_casefold = 1,\n",
223 " unicode_grapheme_break_extend = 2\n",
224 "};\n",
225 "\n");
226
227 # Choose the narrowest type that will fit the required values
228 sub choosetype {
229 my ($min, $max) = @_;
230 if($min >= 0) {
231 return "char" if $max <= 127;
232 return "unsigned char" if $max <= 255;
233 return "int16_t" if $max < 32767;
234 return "uint16_t" if $max < 65535;
235 return "int32_t";
236 } else {
237 return "char" if $min >= -127 && $max <= 127;
238 return "int16_t" if $min >= -32767 && $max <= 32767;
239 return "int32_t";
240 }
241 }
242
243 out("struct unidata {\n",
244 " const uint32_t *compat;\n",
245 " const uint32_t *canon;\n",
246 " const uint32_t *casefold;\n",
247 " ".choosetype($minud, $maxud)." upper_offset;\n",
248 " ".choosetype($minld, $maxld)." lower_offset;\n",
249 " ".choosetype(0, $maxccc)." ccc;\n",
250 " char gc;\n",
251 " uint8_t flags;\n",
252 "};\n");
253 # compat, canon and casefold do have have non-BMP characters, so we
254 # can't use a simple 16-bit table. We could use UTF-8 or UTF-16
255 # though, saving a bit of space (probably not that much...) at the
256 # cost of marginally reduced performance and additional complexity
257
258 out("extern const struct unidata *const unidata[];\n");
259
260 out("#define UNICODE_NCHARS ", ($max + 1), "\n");
261 out("#define UNICODE_MODULUS $modulus\n");
262
263 out("#endif\n");
264
265 close STDOUT or die "unidata.h: $!\n";
266
267 open(STDOUT, ">unidata.c") or die "unidata.c: $!\n";
268
269 out("/* Automatically generated file, see scripts/make-unidata */\n",
270 "#include <config.h>\n",
271 "#include \"types.h\"\n",
272 "#include \"unidata.h\"\n");
273
274 # Short aliases for general category codes
275
276 out(map(sprintf("#define %s unicode_gc_%s\n", $_, $_), sort keys %cats));
277
278 # Generate the decomposition mapping tables. We look out for duplicates
279 # in order to save space and report this as decompsaved at the end. In
280 # Unicode 5.0.0 this saves 1795 entries, which is at least 14Kbytes.
281 my $decompnum = 0;
282 my %decompnums = ();
283 my $decompsaved = 0;
284 out("static const uint32_t ");
285 for(my $c = 0; $c <= $max; ++$c) {
286 # If canon is set then compat will be too and will be identical.
287 # If compat is set the canon might be clear. So we use the
288 # compat version and fix up the symbols after.
289 if(exists $data{$c}->{compat}) {
290 my $s = join(",",
291 (map(hex($_), split(/\s+/, $data{$c}->{compat})), 0));
292 if(!exists $decompnums{$s}) {
293 out(",\n") if $decompnum != 0;
294 out("cd$decompnum\[]={$s}");
295 $decompnums{$s} = $decompnum++;
296 } else {
297 ++$decompsaved;
298 }
299 $data{$c}->{compatsym} = "cd$decompnums{$s}";
300 if(exists $data{$c}->{canon}) {
301 $data{$c}->{canonsym} = "cd$decompnums{$s}";
302 }
303 }
304 }
305 out(";\n");
306
307 # ...and the case folding table. Again we compress equal entries to save
308 # space. In Unicode 5.0.0 this saves 51 entries or at least 408 bytes.
309 # This doesns't seem as worthwhile as the decomposition mapping saving above.
310 my $cfnum = 0;
311 my %cfnums = ();
312 my $cfsaved = 0;
313 out("static const uint32_t ");
314 for(my $c = 0; $c <= $max; ++$c) {
315 if(exists $data{$c}->{casefold}) {
316 my $s = join(",",
317 (map(hex($_), split(/\s+/, $data{$c}->{casefold})), 0));
318 if(!exists $cfnums{$s}) {
319 out(",\n") if $cfnum != 0;
320 out("cf$cfnum\[]={$s}");
321 $cfnums{$s} = $cfnum++;
322 } else {
323 ++$cfsaved;
324 }
325 $data{$c}->{cfsym} = "cf$cfnums{$s}";
326 }
327 }
328 out(";\n");
329
330 # Visit all the $modulus-character blocks in turn and generate the
331 # required subtables. As above we spot duplicates to save space. In
332 # Unicode 5.0.0 with $modulus=128 and current table data this saves
333 # 1372 subtables or at least three and a half megabytes on 32-bit
334 # platforms.
335
336 my %subtable = (); # base->subtable number
337 my %subtableno = (); # subtable number -> content
338 my $subtablecounter = 0; # counter for subtable numbers
339 my $subtablessaved = 0; # number of tables saved
340 for(my $base = 0; $base <= $max; $base += $modulus) {
341 my @t;
342 for(my $c = $base; $c < $base + $modulus; ++$c) {
343 my $d = $data{$c};
344 my $canonsym = ($data{$c}->{canonsym} or "0");
345 my $compatsym = ($data{$c}->{compatsym} or "0");
346 my $cfsym = ($data{$c}->{cfsym} or "0");
347 my @flags = ();
348 if($data{$c}->{ypogegrammeni}) {
349 push(@flags, "unicode_normalize_before_casefold");
350 }
351 # Currently we only store the Extend class, using a bit that would
352 # otherwise be wasted. The other classes are readily computable.
353 # If there is a conveninet way to compute Extend at runtime I have
354 # yet to discover it.
355 if(exists $data{$c}->{gbreak} and $data{$c}->{gbreak} eq 'Extend') {
356 push(@flags, "unicode_grapheme_break_extend");
357 }
358 my $flags = @flags ? join("|", @flags) : 0;
359 push(@t, "{".
360 join(",",
361 $compatsym,
362 $canonsym,
363 $cfsym,
364 "$d->{ud}",
365 "$d->{ld}",
366 "$d->{ccc}",
367 "$d->{gc}",
368 $flags,
369 )."}");
370 }
371 my $t = join(",\n", @t);
372 if(!exists $subtable{$t}) {
373 out("static const struct unidata st$subtablecounter\[] = {\n",
374 "$t\n",
375 "};\n");
376 $subtable{$t} = $subtablecounter++;
377 } else {
378 ++$subtablessaved;
379 }
380 $subtableno{$base} = $subtable{$t};
381 }
382
383 out("const struct unidata*const unidata[]={\n");
384 for(my $base = 0; $base <= $max; $base += $modulus) {
385 out("st$subtableno{$base},\n");
386 }
387 out("};\n");
388
389 close STDOUT or die "unidata.c: $!\n";
390
391 print STDERR "max=$max, subtables=$subtablecounter, subtablessaved=$subtablessaved\n";
392 print STDERR "decompsaved=$decompsaved cfsaved=$cfsaved\n";