chiark / gitweb /
Generate, but do not use, composition mappings.
[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 #  - ...
35 #
36 # NB the generated files DO NOT offer a stable ABI and so are not immediately
37 # suitable for use in a general-purpose library.  Things that would need to
38 # be done:
39 #  - Hide unidata.h from applications; it will never be ABI- or even API-stable.
40 #  - Stablized General_Category values
41 #  - Extend the unicode.h API to general utility rather than just what
42 #    DisOrder needs.
43 #  - ...
44 #
45 use strict;
46 use File::Basename;
47
48 sub out {
49     print @_ or die "$!\n";
50 }
51
52 sub key {
53     my $d = shift;
54     local $_;
55
56     return join("-", map($d->{$_}, sort keys %$d));
57 }
58
59 # Size of a subtable
60 #
61 # This can be varied to trade off the number of subtables against their size.
62 # 16 gave the smallest results last time I checked (on a Mac with a 32-bit
63 # build).
64 our $modulus = 16;
65
66 if(@ARGV) {
67     $modulus = shift;
68 }
69
70 # Where to break the table.  There is a huge empty section of the Unicode
71 # code space and we deal with this by simply leaving it out of the table.
72 # This complicates the lookup function a little but should not affect
73 # performance in the cases we care about.
74 our $break_start = 0x30000;
75 our $break_end = 0xE0000;
76
77 # Similarly we simply omit the very top of the table and sort it out in the
78 # lookup function.
79 our $break_top = 0xE0200;
80
81 my %cats = ();                  # known general categories
82 my %data = ();                  # mapping of codepoints to information
83 my $max = 0;                    # maximum codepoint
84 my $maxccc = 0;                 # maximum combining class
85 my $maxud = 0;
86 my $minud = 0;                  # max/min upper case offset
87 my $maxld = 0;
88 my $minld = 0;                  # max/min lower case offset
89
90 # Make sure we have our desired input files.  We explicitly specify a
91 # Unicode standard version to make sure that a given version of DisOrder
92 # supports a given version of Unicode.
93 sub input {
94     my $path = shift;
95     my $lpath = basename($path);
96     if(!-e $lpath) {
97         system("wget http://www.unicode.org/Public/5.0.0/ucd/$path");
98         chmod(0444, $lpath) or die "$lpath: $!\n";
99     }
100     open(STDIN, "<$lpath") or die "$lpath: $!\n";
101     print STDERR "Reading $lpath...\n";
102 }
103
104
105 # Read the main data file
106 input("UnicodeData.txt");
107 my ($start, $end);
108 while(<>) {
109     my @f = split(/;/, $_);
110     my $c = hex($f[0]);         # codepoint
111     my $name = $f[1];
112     die "$f[0] $name is in the break\n" 
113         if $c >= $break_start && $c < $break_end;
114     my $gc = $f[2];             # General_Category
115     # Variuos GCs we don't expect to see in UnicodeData.txt
116     $cats{$gc} = 1;             # always record all GCs
117     if($name =~ /first>/i) {
118         $start = $c;
119         next;
120     } elsif($name =~ /last>/i) {
121         $end = $c;
122     } else {
123         $start = $end = $c;
124     }
125     die "unexpected Cn" if $gc eq 'Cn';
126     my $ccc = $f[3];            # Canonical_Combining_Class
127     my $dm = $f[5];             # Decomposition_Type + Decomposition_Mapping
128     my $sum = hex($f[12]) || $c; # Simple_Uppercase_Mapping
129     my $slm = hex($f[13]) || $c; # Simple_Lowercase_Mapping
130     # recalculate the upper/lower case mappings as offsets
131     my $ud = $sum - $c;
132     my $ld = $slm - $c;
133     # update bounds on various values
134     $maxccc = $ccc if $ccc > $maxccc; # assumed never to be -ve
135     $minud = $ud if $ud < $minud;
136     $maxud = $ud if $ud > $maxud;
137     $minld = $ld if $ld < $minld;
138     $maxld = $ld if $ld > $maxld;
139     if($start != $end) {
140         printf STDERR "> range %04X-%04X is %s\n", $start, $end, $gc;
141     }
142     for($c = $start; $c <= $end; ++$c) {
143         my $d = {
144             "gc" => $gc,
145             "ccc" => $ccc,
146             "ud" => $ud,
147             "ld" => $ld,
148         };
149         if($dm ne '') {
150             if($dm =~ /</) {
151                 # This is a compatibility decomposition
152                 $dm =~ s/^<.*>\s*//;
153                 $d->{compat} = 1;
154             }
155             $d->{decomp} = [map(hex($_), split(/\s+/, $dm))];
156         }
157         $data{$c} = $d;
158     }
159     $cats{$gc} = 1;
160     $max = $end if $end > $max;
161 }
162
163 sub read_prop_with_ranges {
164     my $path = shift;
165     my $propkey = shift;
166     input($path);
167     while(<>) {
168         chomp;
169         s/\s*\#.*//;
170         next if $_ eq '';
171         my ($range, $propval) = split(/\s*;\s*/, $_);
172         if($range =~ /(.*)\.\.(.*)/) {
173             for my $c (hex($1) .. hex($2)) {
174                 $data{$c}->{$propkey} = $propval;
175             }
176         } else {
177             my $c = hex($range);
178             $data{$c}->{$propkey} = $propval;
179         }
180     }
181 }
182
183 # Grapheme_Break etc
184 read_prop_with_ranges("auxiliary/GraphemeBreakProperty.txt", "gbreak");
185 read_prop_with_ranges("auxiliary/WordBreakProperty.txt", "wbreak");
186 read_prop_with_ranges("auxiliary/SentenceBreakProperty.txt", "sbreak");
187
188 # Compute the full list and fill in the Extend category properly
189 my %gbreak = ();
190 my %wbreak = ();
191 my %sbreak = ();
192 for my $c (keys %data) {
193     if(!exists $data{$c}->{gbreak}) {
194         $data{$c}->{gbreak} = 'Other';
195     }
196     $gbreak{$data{$c}->{gbreak}} = 1;
197
198     if(!exists $data{$c}->{wbreak}) {
199         if($data{$c}->{gbreak} eq 'Extend') {
200             $data{$c}->{wbreak} = 'Extend';
201         } else {
202             $data{$c}->{wbreak} = 'Other';
203         }
204     }
205     $wbreak{$data{$c}->{wbreak}} = 1;
206
207     if(!exists $data{$c}->{sbreak}) {
208         if($data{$c}->{gbreak} eq 'Extend') {
209             $data{$c}->{sbreak} = 'Extend';
210         } else {
211             $data{$c}->{sbreak} = 'Other';
212         }
213     }
214     $sbreak{$data{$c}->{sbreak}} = 1;
215 }
216
217 # Various derived properties
218 input("DerivedNormalizationProps.txt");
219 while(<>) {
220     chomp;
221     s/\s*\#.*//;
222     next if $_ eq '';
223     my @f = split(/\s*;\s*/, $_);
224     if(@f == 2) {
225         push(@f, 1);
226     }
227     my ($range, $propkey, $propval) = @f;
228     if($range =~ /(.*)\.\.(.*)/) {
229         for my $c (hex($1) .. hex($2)) {
230             $data{$c}->{$propkey} = $propval
231         }
232     } else {
233         my $c = hex($range);
234         $data{$c}->{$propkey} = $propval
235     }
236 }
237
238 # Round up the maximum value to a whole number of subtables
239 $max += ($modulus - 1) - ($max % $modulus);
240
241 # Private use characters
242 # We only fill in values below $max, utf32__unidata() 
243 my $Co = {
244     "gc" => "Co",
245     "ccc" => 0,
246     "ud" => 0,
247     "ld" => 0
248 };
249 for(my $c = 0xE000; $c <= 0xF8FF && $c <= $max; ++$c) {
250     $data{$c} = $Co;
251 }
252 for(my $c = 0xF0000; $c <= 0xFFFFD && $c <= $max; ++$c) {
253     $data{$c} = $Co;
254 }
255 for(my $c = 0x100000; $c <= 0x10FFFD && $c <= $max; ++$c) {
256     $data{$c} = $Co;
257 }
258
259 # Anything left is not assigned
260 my $Cn = {
261     "gc" => "Cn",               # not assigned
262     "ccc" => 0,
263     "ud" => 0,
264     "ld" => 0
265 };
266 for(my $c = 0; $c <= $max; ++$c) {
267     if(!exists $data{$c}) {
268         $data{$c} = $Cn;
269     }
270     if(!exists $data{$c}->{wbreak}) {
271         $data{$c}->{wbreak} = 'Other';
272     }
273     if(!exists $data{$c}->{gbreak}) {
274         $data{$c}->{gbreak} = 'Other';
275     }
276     if(!exists $data{$c}->{sbreak}) {
277         $data{$c}->{sbreak} = 'Other';
278     }
279 }
280 $cats{'Cn'} = 1;
281
282 # Read the casefolding data too
283 input("CaseFolding.txt");
284 while(<>) {
285     chomp;
286     next if /^\#/ or $_ eq '';
287     my @f = split(/\s*;\s*/, $_);
288     # Full case folding means use status C and F.
289     # We discard status T, Turkish users may wish to change this.
290     if($f[1] eq 'C' or $f[1] eq 'F') {
291         my $c = hex($f[0]);
292         $data{$c}->{casefold} = $f[2];
293         # We are particularly interest in combining characters that
294         # case-fold to non-combining characters, or characters that
295         # case-fold to sequences with combining characters in non-initial
296         # positions, as these required decomposiiton before case-folding
297         my @d = map(hex($_), split(/\s+/, $data{$c}->{casefold}));
298         if($data{$c}->{ccc} != 0) {
299             # This is a combining character
300             if($data{$d[0]}->{ccc} == 0) {
301                 # The first character of its case-folded form is NOT
302                 # a combining character.  The field name is the example
303                 # explicitly mentioned in the spec.
304                 $data{$c}->{ypogegrammeni} = 1;
305             }
306         } else {
307             # This is a non-combining character; inspect the non-initial
308             # code points of the case-folded sequence
309             shift(@d);
310             if(grep($data{$_}->{ccc} != 0, @d)) {
311                 # Some non-initial code point in the case-folded for is NOT a
312                 # a combining character.
313                 $data{$c}->{ypogegrammeni} = 1;
314             }
315         }
316     }
317 }
318
319 # Generate the header file
320 print STDERR "Generating unidata.h...\n";
321 open(STDOUT, ">unidata.h") or die "unidata.h: $!\n";
322
323 out("/* Automatically generated file, see scripts/make-unidata */\n",
324     "#ifndef UNIDATA_H\n",
325     "#define UNIDATA_H\n");
326
327 # TODO choose stable values for General_Category
328 out("enum unicode_General_Category {\n",
329     join(",\n",
330          map("  unicode_General_Category_$_", sort keys %cats)), "\n};\n");
331
332 out("enum unicode_Grapheme_Break {\n",
333     join(",\n",
334          map("  unicode_Grapheme_Break_$_", sort keys %gbreak)),
335     "\n};\n");
336 out("extern const char *const unicode_Grapheme_Break_names[];\n");
337
338 out("enum unicode_Word_Break {\n",
339     join(",\n",
340          map("  unicode_Word_Break_$_", sort keys %wbreak)),
341     "\n};\n");
342 out("extern const char *const unicode_Word_Break_names[];\n");
343
344 out("enum unicode_Sentence_Break {\n",
345     join(",\n",
346          map("  unicode_Sentence_Break_$_", sort keys %sbreak)),
347     "\n};\n");
348 out("extern const char *const unicode_Sentence_Break_names[];\n");
349
350 out("enum unicode_flags {\n",
351     "  unicode_normalize_before_casefold = 1,\n",
352     "  unicode_compatibility_decomposition = 2\n",
353     "};\n",
354     "\n");
355
356 # Choose the narrowest type that will fit the required values
357 sub choosetype {
358     my ($min, $max) = @_;
359     if($min >= 0) {
360         return "char" if $max <= 127;
361         return "unsigned char" if $max <= 255;
362         return "int16_t" if $max < 32767;
363         return "uint16_t" if $max < 65535;
364         return "int32_t";
365     } else {
366         return "char" if $min >= -127 && $max <= 127;
367         return "int16_t" if $min >= -32767 && $max <= 32767;
368         return "int32_t";
369     }
370 }
371
372 out("struct unidata {\n",
373     # decomposition (canonical or compatibility;
374     # unicode_compatibility_decomposition distinguishes) or NULL
375     "  const uint32_t *decomp;\n",
376
377     # case-folded string or NULL
378     "  const uint32_t *casefold;\n",
379
380     # composed characters that start with this code point.  This only
381     # includes primary composites, i.e. the decomposition mapping is
382     # canonical and this code point is not in the exclusion table.
383     "  const uint32_t *composed;\n",
384
385 #    "  ".choosetype($minud, $maxud)." upper_offset;\n",
386 #    "  ".choosetype($minld, $maxld)." lower_offset;\n",
387
388     # canonical combining class
389     "  ".choosetype(0, $maxccc)." ccc;\n",
390     "  char general_category;\n",
391
392     # see unicode_flags enum
393     "  uint8_t flags;\n",
394     "  char grapheme_break;\n",
395     "  char word_break;\n",
396     "  char sentence_break;\n",
397     "};\n");
398 # decomp and  casefold do have have non-BMP characters, so we
399 # can't use a simple 16-bit table.  We could use UTF-8 or UTF-16
400 # though, saving a bit of space (probably not that much...) at the
401 # cost of marginally reduced performance and additional complexity
402
403 out("extern const struct unidata *const unidata[];\n");
404
405 out("extern const struct unicode_utf8_row {\n",
406     "  uint8_t count;\n",
407     "  uint8_t min2, max2;\n",
408     "} unicode_utf8_valid[];\n");
409
410 out("#define UNICODE_NCHARS ", ($max + 1), "\n");
411 out("#define UNICODE_MODULUS $modulus\n");
412 out("#define UNICODE_BREAK_START $break_start\n");
413 out("#define UNICODE_BREAK_END $break_end\n");
414 out("#define UNICODE_BREAK_TOP $break_top\n");
415
416 out("#endif\n");
417
418 close STDOUT or die "unidata.h: $!\n";
419
420 print STDERR "Generating unidata.c...\n";
421 open(STDOUT, ">unidata.c") or die "unidata.c: $!\n";
422
423 out("/* Automatically generated file, see scripts/make-unidata */\n",
424     "#include <config.h>\n",
425     "#include \"types.h\"\n",
426     "#include \"unidata.h\"\n");
427
428 # Short aliases to keep .c file small
429
430 out(map(sprintf("#define %s unicode_General_Category_%s\n", $_, $_),
431         sort keys %cats));
432 out(map(sprintf("#define GB%s unicode_Grapheme_Break_%s\n", $_, $_),
433         sort keys %gbreak));
434 out(map(sprintf("#define WB%s unicode_Word_Break_%s\n", $_, $_),
435         sort keys %wbreak));
436 out(map(sprintf("#define SB%s unicode_Sentence_Break_%s\n", $_, $_),
437         sort keys %sbreak));
438 out("#define NBC unicode_normalize_before_casefold\n");
439 out("#define CD unicode_compatibility_decomposition\n");
440
441 # Names for *_Break properties
442 out("const char *const unicode_Grapheme_Break_names[] = {\n",
443     join(",\n",
444          map("  \"$_\"", sort keys %gbreak)),
445     "\n};\n");
446 out("const char *const unicode_Word_Break_names[] = {\n",
447     join(",\n",
448          map("  \"$_\"", sort keys %wbreak)),
449     "\n};\n");
450 out("const char *const unicode_Sentence_Break_names[] = {\n",
451     join(",\n",
452          map("  \"$_\"", sort keys %sbreak)),
453     "\n};\n");
454
455 our $ddnum = 0;
456 our $ddsaved = 0;
457 our %ddnums = ();
458 my $ddfirst = 1;
459 out("static const uint32_t ");
460 sub dedupe {
461     my $s = join(",", @_);
462     if(!exists $ddnums{$s}) {
463         if($ddfirst) {
464             $ddfirst = 0;
465         } else {
466             out(",\n");
467         }
468         out("dd$ddnum\[]={$s}");
469         $ddnums{$s} = $ddnum++;
470     } else {
471         ++$ddsaved;
472     }
473     return "dd$ddnums{$s}";
474 }
475
476 # Generate the decomposition mapping tables.  We look out for duplicates
477 # in order to save space and report this as decompsaved at the end.  In
478 # Unicode 5.0.0 this saves 1795 entries, which is at least 14Kbytes.
479 print STDERR "> decomposition mappings\n";
480 for(my $c = 0; $c <= $max; ++$c) {
481     if(exists $data{$c} && exists $data{$c}->{decomp}) {
482         $data{$c}->{decompsym} = dedupe(@{$data{$c}->{decomp}}, 0);
483     }
484 }
485
486 print STDERR "> composition mappings\n";
487 # First we must generate the mapping of each code point to possible
488 # compositions
489 for(my $c = 0; $c <= $max; ++$c) {
490     if(exists $data{$c}
491        && exists $data{$c}->{decomp}
492        && !exists $data{$c}->{compat}
493        && !$data{$c}->{Full_Composition_Exclusion}) {
494         # $c has a non-excluded canonical decomposition, i.e. it is
495         # a primary composite.  Find the first code point of the decomposition
496         my $first = ${$data{$c}->{decomp}}[0];
497         if(!exists $data{$first}->{compose}) {
498             $data{$first}->{compose} = [$first];
499         } else {
500             push(@{$data{$first}->{compose}}, $first);
501         }
502     }
503 }
504 for(my $c = 0; $c <= $max; ++$c) {
505     if(exists $data{$c} && exists $data{$c}->{compose}) {
506         $data{$c}->{compsym} = dedupe(@{$data{$c}->{compose}}, 0);
507     }
508 }
509
510 # ...and the case folding table.  Again we compress equal entries to save
511 # space.  In Unicode 5.0.0 this saves 51 entries or at least 408 bytes.
512 # This doesns't seem as worthwhile as the decomposition mapping saving above.
513 print STDERR "> case-fold mappings\n";
514 for(my $c = 0; $c <= $max; ++$c) {
515     if(exists $data{$c} && exists $data{$c}->{casefold}) {
516         $data{$c}->{cfsym} = dedupe(map(hex($_), split(/\s+/,
517                                                        $data{$c}->{casefold})),
518                                     0);
519     }
520 }
521
522 # End of de-dupable arrays
523 out(";\n");
524
525 # Visit all the $modulus-character blocks in turn and generate the
526 # required subtables.  As above we spot duplicates to save space.  In
527 # Unicode 5.0.0 with $modulus=128 and current table data this saves
528 # 1372 subtables or at least three and a half megabytes on 32-bit
529 # platforms.
530 print STDERR "> subtables\n";
531 my %subtable = ();              # base->subtable number
532 my %subtableno = ();            # subtable number -> content
533 my $subtablecounter = 0;        # counter for subtable numbers
534 my $subtablessaved = 0;         # number of tables saved
535 for(my $base = 0; $base <= $max; $base += $modulus) {
536     next if $base >= $break_start && $base < $break_end;
537     next if $base >= $break_top;
538     my @t;
539     for(my $c = $base; $c < $base + $modulus; ++$c) {
540         my $d = $data{$c};
541         my $decompsym = ($data{$c}->{decompsym} or "0");
542         my $cfsym = ($data{$c}->{cfsym} or "0");
543         my $compsym = ($data{$c}->{compsym} or "0");
544         my @flags = ();
545         if($data{$c}->{ypogegrammeni}) {
546             push(@flags, "NBC");
547         }
548         if($data{$c}->{compat}) {
549             push(@flags, "CD");
550         }
551         my $flags = @flags ? join("|", @flags) : 0;
552         push(@t, "{".
553              join(",",
554                   $decompsym,
555                   $cfsym,
556                   $compsym,
557 #                 $d->{ud},
558 #                 $d->{ld},
559                   $d->{ccc},
560                   $d->{gc},
561                   $flags,
562                   "GB$d->{gbreak}",
563                   "WB$d->{wbreak}",
564                   "SB$d->{sbreak}",
565              )."}");
566     }
567     my $t = join(",\n", @t);
568     if(!exists $subtable{$t}) {
569         out(sprintf("/* %04X-%04X */\n", $base, $base + $modulus - 1));
570         out("static const struct unidata st$subtablecounter\[] = {\n",
571             "$t\n",
572             "};\n");
573         $subtable{$t} = $subtablecounter++;
574     } else {
575         ++$subtablessaved;
576     }
577     $subtableno{$base} = $subtable{$t};
578 }
579
580 print STDERR "> main table\n";
581 out("const struct unidata *const unidata[]={\n");
582 for(my $base = 0; $base <= $max; $base += $modulus) {
583     next if $base >= $break_start && $base < $break_end;
584     next if $base >= $break_top;
585     #out("st$subtableno{$base} /* ".sprintf("%04x", $base)." */,\n");
586     out("st$subtableno{$base},\n");
587 }
588 out("};\n");
589
590 print STDERR "> UTF-8 table\n";
591 out("const struct unicode_utf8_row unicode_utf8_valid[] = {\n");
592 for(my $c = 0; $c <= 0x7F; ++$c) {
593     out(" { 1, 0, 0 }, /* $c */\n");
594 }
595 for(my $c = 0x80; $c < 0xC2; ++$c) {
596     out(" { 0, 0, 0 }, /* $c */\n");
597 }
598 for(my $c = 0xC2; $c <= 0xDF; ++$c) {
599     out(" { 2, 0x80, 0xBF }, /* $c */\n");
600 }
601 for(my $c = 0xE0; $c <= 0xE0; ++$c) {
602     out(" { 3, 0xA0, 0xBF }, /* $c */\n");
603 }
604 for(my $c = 0xE1; $c <= 0xEC; ++$c) {
605     out(" { 3, 0x80, 0xBF }, /* $c */\n");
606 }
607 for(my $c = 0xED; $c <= 0xED; ++$c) {
608     out(" { 3, 0x80, 0x9F }, /* $c */\n");
609 }
610 for(my $c = 0xEE; $c <= 0xEF; ++$c) {
611     out(" { 3, 0x80, 0xBF }, /* $c */\n");
612 }
613 for(my $c = 0xF0; $c <= 0xF0; ++$c) {
614     out(" { 4, 0x90, 0xBF }, /* $c */\n");
615 }
616 for(my $c = 0xF1; $c <= 0xF3; ++$c) {
617     out(" { 4, 0x80, 0xBF }, /* $c */\n");
618 }
619 for(my $c = 0xF4; $c <= 0xF4; ++$c) {
620     out(" { 4, 0x80, 0x8F }, /* $c */\n");
621 }
622 for(my $c = 0xF5; $c <= 0xFF; ++$c) {
623     out(" { 0, 0, 0 }, /* $c */\n");
624 }
625 out("};\n");
626
627 close STDOUT or die "unidata.c: $!\n";
628
629 print STDERR "Done.\n\n";
630 printf STDERR "modulus=%d\n", $modulus;
631 printf STDERR "max=%04X\n", $max;
632 print STDERR "subtables=$subtablecounter, subtablessaved=$subtablessaved\n";
633 print STDERR "ddsaved=$ddsaved\n";