minibidi.c

   1 /************************************************************************
   2  *
   3  * ------------
   4  * Description:
   5  * ------------
   6  * This is an implemention of Unicode's Bidirectional Algorithm
   7  * (known as UAX #9).
   8  *
   9  *   http://www.unicode.org/reports/tr9/
  10  *
  11  * Author: Ahmad Khalifa
  12  *
  13  * (www.arabeyes.org - under MIT license)
  14  *
  15  ************************************************************************/
  16
  17 /*
  18  * TODO:
  19  * =====
  20  * - Explicit marks need to be handled (they are not 100% now)
  21  * - Ligatures
  22  */
  23
  24 #include <stdlib.h>     /* definition of wchar_t*/
  25
  26 #include "misc.h"
  27
  28 #define LMASK   0x3F    /* Embedding Level mask */
  29 #define OMASK   0xC0    /* Override mask */
  30 #define OISL    0x80    /* Override is L */
  31 #define OISR    0x40    /* Override is R */
  32
  33 /* For standalone compilation in a testing mode.
  34  * Still depends on the PuTTY headers for snewn and sfree, but can avoid
  35  * _linking_ with any other PuTTY code. */
  36 #ifdef TEST_GETTYPE
  37 #define safemalloc malloc
  38 #define safefree free
  39 #endif
  40
  41 /* Shaping Helpers */
  42 #define STYPE(xh) ((((xh) >= SHAPE_FIRST) && ((xh) <= SHAPE_LAST)) ? \
  43 shapetypes[(xh)-SHAPE_FIRST].type : SU) /*))*/
  44 #define SISOLATED(xh) (shapetypes[(xh)-SHAPE_FIRST].form_b)
  45 #define SFINAL(xh) ((xh)+1)
  46 #define SINITIAL(xh) ((xh)+2)
  47 #define SMEDIAL(ch) ((ch)+3)
  48
  49 #define leastGreaterOdd(x) ( ((x)+1) | 1 )
  50 #define leastGreaterEven(x) ( ((x)+2) &~ 1 )
  51
  52 typedef struct bidi_char {
  53     unsigned int origwc, wc;
  54     unsigned short index;
  55 } bidi_char;
  56
  57 /* function declarations */
  58 void flipThisRun(bidi_char *from, unsigned char* level, int max, int count);
  59 int findIndexOfRun(unsigned char* level , int start, int count, int tlevel);
  60 unsigned char getType(int ch);
  61 unsigned char setOverrideBits(unsigned char level, unsigned char override);
  62 int getPreviousLevel(unsigned char* level, int from);
  63 int do_shape(bidi_char *line, bidi_char *to, int count);
  64 int do_bidi(bidi_char *line, int count);
  65 void doMirror(unsigned int *ch);
  66
  67 /* character types */
  68 enum {
  69     L,
  70     LRE,
  71     LRO,
  72     R,
  73     AL,
  74     RLE,
  75     RLO,
  76     PDF,
  77     EN,
  78     ES,
  79     ET,
  80     AN,
  81     CS,
  82     NSM,
  83     BN,
  84     B,
  85     S,
  86     WS,
  87     ON
  88 };
  89
  90 /* Shaping Types */
  91 enum {
  92     SL, /* Left-Joining, doesnt exist in U+0600 - U+06FF */
  93     SR, /* Right-Joining, ie has Isolated, Final */
  94     SD, /* Dual-Joining, ie has Isolated, Final, Initial, Medial */
  95     SU, /* Non-Joining */
  96     SC  /* Join-Causing, like U+0640 (TATWEEL) */
  97 };
  98
  99 typedef struct {
 100     char type;
 101     wchar_t form_b;
 102 } shape_node;
 103
 104 /* Kept near the actual table, for verification. */
 105 #define SHAPE_FIRST 0x621
 106 #define SHAPE_LAST (SHAPE_FIRST + lenof(shapetypes) - 1)
 107
 108 const shape_node shapetypes[] = {
 109     /* index, Typ, Iso, Ligature Index*/
 110     /* 621 */ {SU, 0xFE80},
 111     /* 622 */ {SR, 0xFE81},
 112     /* 623 */ {SR, 0xFE83},
 113     /* 624 */ {SR, 0xFE85},
 114     /* 625 */ {SR, 0xFE87},
 115     /* 626 */ {SD, 0xFE89},
 116     /* 627 */ {SR, 0xFE8D},
 117     /* 628 */ {SD, 0xFE8F},
 118     /* 629 */ {SR, 0xFE93},
 119     /* 62A */ {SD, 0xFE95},
 120     /* 62B */ {SD, 0xFE99},
 121     /* 62C */ {SD, 0xFE9D},
 122     /* 62D */ {SD, 0xFEA1},
 123     /* 62E */ {SD, 0xFEA5},
 124     /* 62F */ {SR, 0xFEA9},
 125     /* 630 */ {SR, 0xFEAB},
 126     /* 631 */ {SR, 0xFEAD},
 127     /* 632 */ {SR, 0xFEAF},
 128     /* 633 */ {SD, 0xFEB1},
 129     /* 634 */ {SD, 0xFEB5},
 130     /* 635 */ {SD, 0xFEB9},
 131     /* 636 */ {SD, 0xFEBD},
 132     /* 637 */ {SD, 0xFEC1},
 133     /* 638 */ {SD, 0xFEC5},
 134     /* 639 */ {SD, 0xFEC9},
 135     /* 63A */ {SD, 0xFECD},
 136     /* 63B */ {SU, 0x0},
 137     /* 63C */ {SU, 0x0},
 138     /* 63D */ {SU, 0x0},
 139     /* 63E */ {SU, 0x0},
 140     /* 63F */ {SU, 0x0},
 141     /* 640 */ {SC, 0x0},
 142     /* 641 */ {SD, 0xFED1},
 143     /* 642 */ {SD, 0xFED5},
 144     /* 643 */ {SD, 0xFED9},
 145     /* 644 */ {SD, 0xFEDD},
 146     /* 645 */ {SD, 0xFEE1},
 147     /* 646 */ {SD, 0xFEE5},
 148     /* 647 */ {SD, 0xFEE9},
 149     /* 648 */ {SR, 0xFEED},
 150     /* 649 */ {SR, 0xFEEF}, /* SD */
 151     /* 64A */ {SD, 0xFEF1},
 152     /* 64B */ {SU, 0x0},
 153     /* 64C */ {SU, 0x0},
 154     /* 64D */ {SU, 0x0},
 155     /* 64E */ {SU, 0x0},
 156     /* 64F */ {SU, 0x0},
 157     /* 650 */ {SU, 0x0},
 158     /* 651 */ {SU, 0x0},
 159     /* 652 */ {SU, 0x0},
 160     /* 653 */ {SU, 0x0},
 161     /* 654 */ {SU, 0x0},
 162     /* 655 */ {SU, 0x0},
 163     /* 656 */ {SU, 0x0},
 164     /* 657 */ {SU, 0x0},
 165     /* 658 */ {SU, 0x0},
 166     /* 659 */ {SU, 0x0},
 167     /* 65A */ {SU, 0x0},
 168     /* 65B */ {SU, 0x0},
 169     /* 65C */ {SU, 0x0},
 170     /* 65D */ {SU, 0x0},
 171     /* 65E */ {SU, 0x0},
 172     /* 65F */ {SU, 0x0},
 173     /* 660 */ {SU, 0x0},
 174     /* 661 */ {SU, 0x0},
 175     /* 662 */ {SU, 0x0},
 176     /* 663 */ {SU, 0x0},
 177     /* 664 */ {SU, 0x0},
 178     /* 665 */ {SU, 0x0},
 179     /* 666 */ {SU, 0x0},
 180     /* 667 */ {SU, 0x0},
 181     /* 668 */ {SU, 0x0},
 182     /* 669 */ {SU, 0x0},
 183     /* 66A */ {SU, 0x0},
 184     /* 66B */ {SU, 0x0},
 185     /* 66C */ {SU, 0x0},
 186     /* 66D */ {SU, 0x0},
 187     /* 66E */ {SU, 0x0},
 188     /* 66F */ {SU, 0x0},
 189     /* 670 */ {SU, 0x0},
 190     /* 671 */ {SR, 0xFB50},
 191     /* 672 */ {SU, 0x0},
 192     /* 673 */ {SU, 0x0},
 193     /* 674 */ {SU, 0x0},
 194     /* 675 */ {SU, 0x0},
 195     /* 676 */ {SU, 0x0},
 196     /* 677 */ {SU, 0x0},
 197     /* 678 */ {SU, 0x0},
 198     /* 679 */ {SD, 0xFB66},
 199     /* 67A */ {SD, 0xFB5E},
 200     /* 67B */ {SD, 0xFB52},
 201     /* 67C */ {SU, 0x0},
 202     /* 67D */ {SU, 0x0},
 203     /* 67E */ {SD, 0xFB56},
 204     /* 67F */ {SD, 0xFB62},
 205     /* 680 */ {SD, 0xFB5A},
 206     /* 681 */ {SU, 0x0},
 207     /* 682 */ {SU, 0x0},
 208     /* 683 */ {SD, 0xFB76},
 209     /* 684 */ {SD, 0xFB72},
 210     /* 685 */ {SU, 0x0},
 211     /* 686 */ {SD, 0xFB7A},
 212     /* 687 */ {SD, 0xFB7E},
 213     /* 688 */ {SR, 0xFB88},
 214     /* 689 */ {SU, 0x0},
 215     /* 68A */ {SU, 0x0},
 216     /* 68B */ {SU, 0x0},
 217     /* 68C */ {SR, 0xFB84},
 218     /* 68D */ {SR, 0xFB82},
 219     /* 68E */ {SR, 0xFB86},
 220     /* 68F */ {SU, 0x0},
 221     /* 690 */ {SU, 0x0},
 222     /* 691 */ {SR, 0xFB8C},
 223     /* 692 */ {SU, 0x0},
 224     /* 693 */ {SU, 0x0},
 225     /* 694 */ {SU, 0x0},
 226     /* 695 */ {SU, 0x0},
 227     /* 696 */ {SU, 0x0},
 228     /* 697 */ {SU, 0x0},
 229     /* 698 */ {SR, 0xFB8A},
 230     /* 699 */ {SU, 0x0},
 231     /* 69A */ {SU, 0x0},
 232     /* 69B */ {SU, 0x0},
 233     /* 69C */ {SU, 0x0},
 234     /* 69D */ {SU, 0x0},
 235     /* 69E */ {SU, 0x0},
 236     /* 69F */ {SU, 0x0},
 237     /* 6A0 */ {SU, 0x0},
 238     /* 6A1 */ {SU, 0x0},
 239     /* 6A2 */ {SU, 0x0},
 240     /* 6A3 */ {SU, 0x0},
 241     /* 6A4 */ {SD, 0xFB6A},
 242     /* 6A5 */ {SU, 0x0},
 243     /* 6A6 */ {SD, 0xFB6E},
 244     /* 6A7 */ {SU, 0x0},
 245     /* 6A8 */ {SU, 0x0},
 246     /* 6A9 */ {SD, 0xFB8E},
 247     /* 6AA */ {SU, 0x0},
 248     /* 6AB */ {SU, 0x0},
 249     /* 6AC */ {SU, 0x0},
 250     /* 6AD */ {SD, 0xFBD3},
 251     /* 6AE */ {SU, 0x0},
 252     /* 6AF */ {SD, 0xFB92},
 253     /* 6B0 */ {SU, 0x0},
 254     /* 6B1 */ {SD, 0xFB9A},
 255     /* 6B2 */ {SU, 0x0},
 256     /* 6B3 */ {SD, 0xFB96},
 257     /* 6B4 */ {SU, 0x0},
 258     /* 6B5 */ {SU, 0x0},
 259     /* 6B6 */ {SU, 0x0},
 260     /* 6B7 */ {SU, 0x0},
 261     /* 6B8 */ {SU, 0x0},
 262     /* 6B9 */ {SU, 0x0},
 263     /* 6BA */ {SR, 0xFB9E},
 264     /* 6BB */ {SD, 0xFBA0},
 265     /* 6BC */ {SU, 0x0},
 266     /* 6BD */ {SU, 0x0},
 267     /* 6BE */ {SD, 0xFBAA},
 268     /* 6BF */ {SU, 0x0},
 269     /* 6C0 */ {SR, 0xFBA4},
 270     /* 6C1 */ {SD, 0xFBA6},
 271     /* 6C2 */ {SU, 0x0},
 272     /* 6C3 */ {SU, 0x0},
 273     /* 6C4 */ {SU, 0x0},
 274     /* 6C5 */ {SR, 0xFBE0},
 275     /* 6C6 */ {SR, 0xFBD9},
 276     /* 6C7 */ {SR, 0xFBD7},
 277     /* 6C8 */ {SR, 0xFBDB},
 278     /* 6C9 */ {SR, 0xFBE2},
 279     /* 6CA */ {SU, 0x0},
 280     /* 6CB */ {SR, 0xFBDE},
 281     /* 6CC */ {SD, 0xFBFC},
 282     /* 6CD */ {SU, 0x0},
 283     /* 6CE */ {SU, 0x0},
 284     /* 6CF */ {SU, 0x0},
 285     /* 6D0 */ {SU, 0x0},
 286     /* 6D1 */ {SU, 0x0},
 287     /* 6D2 */ {SR, 0xFBAE},
 288 };
 289
 290 /*
 291  * Flips the text buffer, according to max level, and
 292  * all higher levels
 293  *
 294  * Input:
 295  * from: text buffer, on which to apply flipping
 296  * level: resolved levels buffer
 297  * max: the maximum level found in this line (should be unsigned char)
 298  * count: line size in bidi_char
 299  */
 300 void flipThisRun(bidi_char *from, unsigned char *level, int max, int count)
 301 {
 302     int i, j, k, tlevel;
 303     bidi_char temp;
 304
 305     j = i = 0;
 306     while (i<count && j<count) {
 307
 308         /* find the start of the run of level=max */
 309         tlevel = max;
 310         i = j = findIndexOfRun(level, i, count, max);
 311         /* find the end of the run */
 312         while (i<count && tlevel <= level[i]) {
 313             i++;
 314         }
 315         for (k = i - 1; k > j; k--, j++) {
 316             temp = from[k];
 317             from[k] = from[j];
 318             from[j] = temp;
 319         }
 320     }
 321 }
 322
 323 /*
 324  * Finds the index of a run with level equals tlevel
 325  */
 326 int findIndexOfRun(unsigned char* level , int start, int count, int tlevel)
 327 {
 328     int i;
 329     for (i=start; i<count; i++) {
 330         if (tlevel == level[i]) {
 331             return i;
 332         }
 333     }
 334     return count;
 335 }
 336
 337 /*
 338  * Returns the bidi character type of ch.
 339  *
 340  * The data table in this function is constructed from the Unicode
 341  * Character Database, downloadable from unicode.org at the URL
 342  *
 343  *     http://www.unicode.org/Public/UNIDATA/UnicodeData.txt
 344  *
 345  * by the following fragment of Perl:
 346
 347 perl -ne 'split ";"; $num = hex $_[0]; $type = $_[4];' \
 348       -e '$fl = ($_[1] =~ /First/ ? 1 : $_[1] =~ /Last/ ? 2 : 0);' \
 349       -e 'if ($type eq $runtype and ($runend == $num-1 or ' \
 350       -e '    ($fl==2 and $pfl==1))) {$runend = $num;} else { &reset; }' \
 351       -e '$pfl=$fl; END { &reset }; sub reset {' \
 352       -e 'printf"        {0x%04x, 0x%04x, %s},\n",$runstart,$runend,$runtype' \
 353       -e '  if defined $runstart and $runtype ne "ON";' \
 354       -e '$runstart=$runend=$num; $runtype=$type;}' \
 355     UnicodeData.txt
 356
 357  */
 358 unsigned char getType(int ch)
 359 {
 360     static const struct {
 361         int first, last, type;
 362     } lookup[] = {
 363         {0x0000, 0x0008, BN},
 364         {0x0009, 0x0009, S},
 365         {0x000a, 0x000a, B},
 366         {0x000b, 0x000b, S},
 367         {0x000c, 0x000c, WS},
 368         {0x000d, 0x000d, B},
 369         {0x000e, 0x001b, BN},
 370         {0x001c, 0x001e, B},
 371         {0x001f, 0x001f, S},
 372         {0x0020, 0x0020, WS},
 373         {0x0023, 0x0025, ET},
 374         {0x002b, 0x002b, ES},
 375         {0x002c, 0x002c, CS},
 376         {0x002d, 0x002d, ES},
 377         {0x002e, 0x002f, CS},
 378         {0x0030, 0x0039, EN},
 379         {0x003a, 0x003a, CS},
 380         {0x0041, 0x005a, L},
 381         {0x0061, 0x007a, L},
 382         {0x007f, 0x0084, BN},
 383         {0x0085, 0x0085, B},
 384         {0x0086, 0x009f, BN},
 385         {0x00a0, 0x00a0, CS},
 386         {0x00a2, 0x00a5, ET},
 387         {0x00aa, 0x00aa, L},
 388         {0x00ad, 0x00ad, BN},
 389         {0x00b0, 0x00b1, ET},
 390         {0x00b2, 0x00b3, EN},
 391         {0x00b5, 0x00b5, L},
 392         {0x00b9, 0x00b9, EN},
 393         {0x00ba, 0x00ba, L},
 394         {0x00c0, 0x00d6, L},
 395         {0x00d8, 0x00f6, L},
 396         {0x00f8, 0x0236, L},
 397         {0x0250, 0x02b8, L},
 398         {0x02bb, 0x02c1, L},
 399         {0x02d0, 0x02d1, L},
 400         {0x02e0, 0x02e4, L},
 401         {0x02ee, 0x02ee, L},
 402         {0x0300, 0x0357, NSM},
 403         {0x035d, 0x036f, NSM},
 404         {0x037a, 0x037a, L},
 405         {0x0386, 0x0386, L},
 406         {0x0388, 0x038a, L},
 407         {0x038c, 0x038c, L},
 408         {0x038e, 0x03a1, L},
 409         {0x03a3, 0x03ce, L},
 410         {0x03d0, 0x03f5, L},
 411         {0x03f7, 0x03fb, L},
 412         {0x0400, 0x0482, L},
 413         {0x0483, 0x0486, NSM},
 414         {0x0488, 0x0489, NSM},
 415         {0x048a, 0x04ce, L},
 416         {0x04d0, 0x04f5, L},
 417         {0x04f8, 0x04f9, L},
 418         {0x0500, 0x050f, L},
 419         {0x0531, 0x0556, L},
 420         {0x0559, 0x055f, L},
 421         {0x0561, 0x0587, L},
 422         {0x0589, 0x0589, L},
 423         {0x0591, 0x05a1, NSM},
 424         {0x05a3, 0x05b9, NSM},
 425         {0x05bb, 0x05bd, NSM},
 426         {0x05be, 0x05be, R},
 427         {0x05bf, 0x05bf, NSM},
 428         {0x05c0, 0x05c0, R},
 429         {0x05c1, 0x05c2, NSM},
 430         {0x05c3, 0x05c3, R},
 431         {0x05c4, 0x05c4, NSM},
 432         {0x05d0, 0x05ea, R},
 433         {0x05f0, 0x05f4, R},
 434         {0x0600, 0x0603, AL},
 435         {0x060c, 0x060c, CS},
 436         {0x060d, 0x060d, AL},
 437         {0x0610, 0x0615, NSM},
 438         {0x061b, 0x061b, AL},
 439         {0x061f, 0x061f, AL},
 440         {0x0621, 0x063a, AL},
 441         {0x0640, 0x064a, AL},
 442         {0x064b, 0x0658, NSM},
 443         {0x0660, 0x0669, AN},
 444         {0x066a, 0x066a, ET},
 445         {0x066b, 0x066c, AN},
 446         {0x066d, 0x066f, AL},
 447         {0x0670, 0x0670, NSM},
 448         {0x0671, 0x06d5, AL},
 449         {0x06d6, 0x06dc, NSM},
 450         {0x06dd, 0x06dd, AL},
 451         {0x06de, 0x06e4, NSM},
 452         {0x06e5, 0x06e6, AL},
 453         {0x06e7, 0x06e8, NSM},
 454         {0x06ea, 0x06ed, NSM},
 455         {0x06ee, 0x06ef, AL},
 456         {0x06f0, 0x06f9, EN},
 457         {0x06fa, 0x070d, AL},
 458         {0x070f, 0x070f, BN},
 459         {0x0710, 0x0710, AL},
 460         {0x0711, 0x0711, NSM},
 461         {0x0712, 0x072f, AL},
 462         {0x0730, 0x074a, NSM},
 463         {0x074d, 0x074f, AL},
 464         {0x0780, 0x07a5, AL},
 465         {0x07a6, 0x07b0, NSM},
 466         {0x07b1, 0x07b1, AL},
 467         {0x0901, 0x0902, NSM},
 468         {0x0903, 0x0939, L},
 469         {0x093c, 0x093c, NSM},
 470         {0x093d, 0x0940, L},
 471         {0x0941, 0x0948, NSM},
 472         {0x0949, 0x094c, L},
 473         {0x094d, 0x094d, NSM},
 474         {0x0950, 0x0950, L},
 475         {0x0951, 0x0954, NSM},
 476         {0x0958, 0x0961, L},
 477         {0x0962, 0x0963, NSM},
 478         {0x0964, 0x0970, L},
 479         {0x0981, 0x0981, NSM},
 480         {0x0982, 0x0983, L},
 481         {0x0985, 0x098c, L},
 482         {0x098f, 0x0990, L},
 483         {0x0993, 0x09a8, L},
 484         {0x09aa, 0x09b0, L},
 485         {0x09b2, 0x09b2, L},
 486         {0x09b6, 0x09b9, L},
 487         {0x09bc, 0x09bc, NSM},
 488         {0x09bd, 0x09c0, L},
 489         {0x09c1, 0x09c4, NSM},
 490         {0x09c7, 0x09c8, L},
 491         {0x09cb, 0x09cc, L},
 492         {0x09cd, 0x09cd, NSM},
 493         {0x09d7, 0x09d7, L},
 494         {0x09dc, 0x09dd, L},
 495         {0x09df, 0x09e1, L},
 496         {0x09e2, 0x09e3, NSM},
 497         {0x09e6, 0x09f1, L},
 498         {0x09f2, 0x09f3, ET},
 499         {0x09f4, 0x09fa, L},
 500         {0x0a01, 0x0a02, NSM},
 501         {0x0a03, 0x0a03, L},
 502         {0x0a05, 0x0a0a, L},
 503         {0x0a0f, 0x0a10, L},
 504         {0x0a13, 0x0a28, L},
 505         {0x0a2a, 0x0a30, L},
 506         {0x0a32, 0x0a33, L},
 507         {0x0a35, 0x0a36, L},
 508         {0x0a38, 0x0a39, L},
 509         {0x0a3c, 0x0a3c, NSM},
 510         {0x0a3e, 0x0a40, L},
 511         {0x0a41, 0x0a42, NSM},
 512         {0x0a47, 0x0a48, NSM},
 513         {0x0a4b, 0x0a4d, NSM},
 514         {0x0a59, 0x0a5c, L},
 515         {0x0a5e, 0x0a5e, L},
 516         {0x0a66, 0x0a6f, L},
 517         {0x0a70, 0x0a71, NSM},
 518         {0x0a72, 0x0a74, L},
 519         {0x0a81, 0x0a82, NSM},
 520         {0x0a83, 0x0a83, L},
 521         {0x0a85, 0x0a8d, L},
 522         {0x0a8f, 0x0a91, L},
 523         {0x0a93, 0x0aa8, L},
 524         {0x0aaa, 0x0ab0, L},
 525         {0x0ab2, 0x0ab3, L},
 526         {0x0ab5, 0x0ab9, L},
 527         {0x0abc, 0x0abc, NSM},
 528         {0x0abd, 0x0ac0, L},
 529         {0x0ac1, 0x0ac5, NSM},
 530         {0x0ac7, 0x0ac8, NSM},
 531         {0x0ac9, 0x0ac9, L},
 532         {0x0acb, 0x0acc, L},
 533         {0x0acd, 0x0acd, NSM},
 534         {0x0ad0, 0x0ad0, L},
 535         {0x0ae0, 0x0ae1, L},
 536         {0x0ae2, 0x0ae3, NSM},
 537         {0x0ae6, 0x0aef, L},
 538         {0x0af1, 0x0af1, ET},
 539         {0x0b01, 0x0b01, NSM},
 540         {0x0b02, 0x0b03, L},
 541         {0x0b05, 0x0b0c, L},
 542         {0x0b0f, 0x0b10, L},
 543         {0x0b13, 0x0b28, L},
 544         {0x0b2a, 0x0b30, L},
 545         {0x0b32, 0x0b33, L},
 546         {0x0b35, 0x0b39, L},
 547         {0x0b3c, 0x0b3c, NSM},
 548         {0x0b3d, 0x0b3e, L},
 549         {0x0b3f, 0x0b3f, NSM},
 550         {0x0b40, 0x0b40, L},
 551         {0x0b41, 0x0b43, NSM},
 552         {0x0b47, 0x0b48, L},
 553         {0x0b4b, 0x0b4c, L},
 554         {0x0b4d, 0x0b4d, NSM},
 555         {0x0b56, 0x0b56, NSM},
 556         {0x0b57, 0x0b57, L},
 557         {0x0b5c, 0x0b5d, L},
 558         {0x0b5f, 0x0b61, L},
 559         {0x0b66, 0x0b71, L},
 560         {0x0b82, 0x0b82, NSM},
 561         {0x0b83, 0x0b83, L},
 562         {0x0b85, 0x0b8a, L},
 563         {0x0b8e, 0x0b90, L},
 564         {0x0b92, 0x0b95, L},
 565         {0x0b99, 0x0b9a, L},
 566         {0x0b9c, 0x0b9c, L},
 567         {0x0b9e, 0x0b9f, L},
 568         {0x0ba3, 0x0ba4, L},
 569         {0x0ba8, 0x0baa, L},
 570         {0x0bae, 0x0bb5, L},
 571         {0x0bb7, 0x0bb9, L},
 572         {0x0bbe, 0x0bbf, L},
 573         {0x0bc0, 0x0bc0, NSM},
 574         {0x0bc1, 0x0bc2, L},
 575         {0x0bc6, 0x0bc8, L},
 576         {0x0bca, 0x0bcc, L},
 577         {0x0bcd, 0x0bcd, NSM},
 578         {0x0bd7, 0x0bd7, L},
 579         {0x0be7, 0x0bf2, L},
 580         {0x0bf9, 0x0bf9, ET},
 581         {0x0c01, 0x0c03, L},
 582         {0x0c05, 0x0c0c, L},
 583         {0x0c0e, 0x0c10, L},
 584         {0x0c12, 0x0c28, L},
 585         {0x0c2a, 0x0c33, L},
 586         {0x0c35, 0x0c39, L},
 587         {0x0c3e, 0x0c40, NSM},
 588         {0x0c41, 0x0c44, L},
 589         {0x0c46, 0x0c48, NSM},
 590         {0x0c4a, 0x0c4d, NSM},
 591         {0x0c55, 0x0c56, NSM},
 592         {0x0c60, 0x0c61, L},
 593         {0x0c66, 0x0c6f, L},
 594         {0x0c82, 0x0c83, L},
 595         {0x0c85, 0x0c8c, L},
 596         {0x0c8e, 0x0c90, L},
 597         {0x0c92, 0x0ca8, L},
 598         {0x0caa, 0x0cb3, L},
 599         {0x0cb5, 0x0cb9, L},
 600         {0x0cbc, 0x0cbc, NSM},
 601         {0x0cbd, 0x0cc4, L},
 602         {0x0cc6, 0x0cc8, L},
 603         {0x0cca, 0x0ccb, L},
 604         {0x0ccc, 0x0ccd, NSM},
 605         {0x0cd5, 0x0cd6, L},
 606         {0x0cde, 0x0cde, L},
 607         {0x0ce0, 0x0ce1, L},
 608         {0x0ce6, 0x0cef, L},
 609         {0x0d02, 0x0d03, L},
 610         {0x0d05, 0x0d0c, L},
 611         {0x0d0e, 0x0d10, L},
 612         {0x0d12, 0x0d28, L},
 613         {0x0d2a, 0x0d39, L},
 614         {0x0d3e, 0x0d40, L},
 615         {0x0d41, 0x0d43, NSM},
 616         {0x0d46, 0x0d48, L},
 617         {0x0d4a, 0x0d4c, L},
 618         {0x0d4d, 0x0d4d, NSM},
 619         {0x0d57, 0x0d57, L},
 620         {0x0d60, 0x0d61, L},
 621         {0x0d66, 0x0d6f, L},
 622         {0x0d82, 0x0d83, L},
 623         {0x0d85, 0x0d96, L},
 624         {0x0d9a, 0x0db1, L},
 625         {0x0db3, 0x0dbb, L},
 626         {0x0dbd, 0x0dbd, L},
 627         {0x0dc0, 0x0dc6, L},
 628         {0x0dca, 0x0dca, NSM},
 629         {0x0dcf, 0x0dd1, L},
 630         {0x0dd2, 0x0dd4, NSM},
 631         {0x0dd6, 0x0dd6, NSM},
 632         {0x0dd8, 0x0ddf, L},
 633         {0x0df2, 0x0df4, L},
 634         {0x0e01, 0x0e30, L},
 635         {0x0e31, 0x0e31, NSM},
 636         {0x0e32, 0x0e33, L},
 637         {0x0e34, 0x0e3a, NSM},
 638         {0x0e3f, 0x0e3f, ET},
 639         {0x0e40, 0x0e46, L},
 640         {0x0e47, 0x0e4e, NSM},
 641         {0x0e4f, 0x0e5b, L},
 642         {0x0e81, 0x0e82, L},
 643         {0x0e84, 0x0e84, L},
 644         {0x0e87, 0x0e88, L},
 645         {0x0e8a, 0x0e8a, L},
 646         {0x0e8d, 0x0e8d, L},
 647         {0x0e94, 0x0e97, L},
 648         {0x0e99, 0x0e9f, L},
 649         {0x0ea1, 0x0ea3, L},
 650         {0x0ea5, 0x0ea5, L},
 651         {0x0ea7, 0x0ea7, L},
 652         {0x0eaa, 0x0eab, L},
 653         {0x0ead, 0x0eb0, L},
 654         {0x0eb1, 0x0eb1, NSM},
 655         {0x0eb2, 0x0eb3, L},
 656         {0x0eb4, 0x0eb9, NSM},
 657         {0x0ebb, 0x0ebc, NSM},
 658         {0x0ebd, 0x0ebd, L},
 659         {0x0ec0, 0x0ec4, L},
 660         {0x0ec6, 0x0ec6, L},
 661         {0x0ec8, 0x0ecd, NSM},
 662         {0x0ed0, 0x0ed9, L},
 663         {0x0edc, 0x0edd, L},
 664         {0x0f00, 0x0f17, L},
 665         {0x0f18, 0x0f19, NSM},
 666         {0x0f1a, 0x0f34, L},
 667         {0x0f35, 0x0f35, NSM},
 668         {0x0f36, 0x0f36, L},
 669         {0x0f37, 0x0f37, NSM},
 670         {0x0f38, 0x0f38, L},
 671         {0x0f39, 0x0f39, NSM},
 672         {0x0f3e, 0x0f47, L},
 673         {0x0f49, 0x0f6a, L},
 674         {0x0f71, 0x0f7e, NSM},
 675         {0x0f7f, 0x0f7f, L},
 676         {0x0f80, 0x0f84, NSM},
 677         {0x0f85, 0x0f85, L},
 678         {0x0f86, 0x0f87, NSM},
 679         {0x0f88, 0x0f8b, L},
 680         {0x0f90, 0x0f97, NSM},
 681         {0x0f99, 0x0fbc, NSM},
 682         {0x0fbe, 0x0fc5, L},
 683         {0x0fc6, 0x0fc6, NSM},
 684         {0x0fc7, 0x0fcc, L},
 685         {0x0fcf, 0x0fcf, L},
 686         {0x1000, 0x1021, L},
 687         {0x1023, 0x1027, L},
 688         {0x1029, 0x102a, L},
 689         {0x102c, 0x102c, L},
 690         {0x102d, 0x1030, NSM},
 691         {0x1031, 0x1031, L},
 692         {0x1032, 0x1032, NSM},
 693         {0x1036, 0x1037, NSM},
 694         {0x1038, 0x1038, L},
 695         {0x1039, 0x1039, NSM},
 696         {0x1040, 0x1057, L},
 697         {0x1058, 0x1059, NSM},
 698         {0x10a0, 0x10c5, L},
 699         {0x10d0, 0x10f8, L},
 700         {0x10fb, 0x10fb, L},
 701         {0x1100, 0x1159, L},
 702         {0x115f, 0x11a2, L},
 703         {0x11a8, 0x11f9, L},
 704         {0x1200, 0x1206, L},
 705         {0x1208, 0x1246, L},
 706         {0x1248, 0x1248, L},
 707         {0x124a, 0x124d, L},
 708         {0x1250, 0x1256, L},
 709         {0x1258, 0x1258, L},
 710         {0x125a, 0x125d, L},
 711         {0x1260, 0x1286, L},
 712         {0x1288, 0x1288, L},
 713         {0x128a, 0x128d, L},
 714         {0x1290, 0x12ae, L},
 715         {0x12b0, 0x12b0, L},
 716         {0x12b2, 0x12b5, L},
 717         {0x12b8, 0x12be, L},
 718         {0x12c0, 0x12c0, L},
 719         {0x12c2, 0x12c5, L},
 720         {0x12c8, 0x12ce, L},
 721         {0x12d0, 0x12d6, L},
 722         {0x12d8, 0x12ee, L},
 723         {0x12f0, 0x130e, L},
 724         {0x1310, 0x1310, L},
 725         {0x1312, 0x1315, L},
 726         {0x1318, 0x131e, L},
 727         {0x1320, 0x1346, L},
 728         {0x1348, 0x135a, L},
 729         {0x1361, 0x137c, L},
 730         {0x13a0, 0x13f4, L},
 731         {0x1401, 0x1676, L},
 732         {0x1680, 0x1680, WS},
 733         {0x1681, 0x169a, L},
 734         {0x16a0, 0x16f0, L},
 735         {0x1700, 0x170c, L},
 736         {0x170e, 0x1711, L},
 737         {0x1712, 0x1714, NSM},
 738         {0x1720, 0x1731, L},
 739         {0x1732, 0x1734, NSM},
 740         {0x1735, 0x1736, L},
 741         {0x1740, 0x1751, L},
 742         {0x1752, 0x1753, NSM},
 743         {0x1760, 0x176c, L},
 744         {0x176e, 0x1770, L},
 745         {0x1772, 0x1773, NSM},
 746         {0x1780, 0x17b6, L},
 747         {0x17b7, 0x17bd, NSM},
 748         {0x17be, 0x17c5, L},
 749         {0x17c6, 0x17c6, NSM},
 750         {0x17c7, 0x17c8, L},
 751         {0x17c9, 0x17d3, NSM},
 752         {0x17d4, 0x17da, L},
 753         {0x17db, 0x17db, ET},
 754         {0x17dc, 0x17dc, L},
 755         {0x17dd, 0x17dd, NSM},
 756         {0x17e0, 0x17e9, L},
 757         {0x180b, 0x180d, NSM},
 758         {0x180e, 0x180e, WS},
 759         {0x1810, 0x1819, L},
 760         {0x1820, 0x1877, L},
 761         {0x1880, 0x18a8, L},
 762         {0x18a9, 0x18a9, NSM},
 763         {0x1900, 0x191c, L},
 764         {0x1920, 0x1922, NSM},
 765         {0x1923, 0x1926, L},
 766         {0x1927, 0x192b, NSM},
 767         {0x1930, 0x1931, L},
 768         {0x1932, 0x1932, NSM},
 769         {0x1933, 0x1938, L},
 770         {0x1939, 0x193b, NSM},
 771         {0x1946, 0x196d, L},
 772         {0x1970, 0x1974, L},
 773         {0x1d00, 0x1d6b, L},
 774         {0x1e00, 0x1e9b, L},
 775         {0x1ea0, 0x1ef9, L},
 776         {0x1f00, 0x1f15, L},
 777         {0x1f18, 0x1f1d, L},
 778         {0x1f20, 0x1f45, L},
 779         {0x1f48, 0x1f4d, L},
 780         {0x1f50, 0x1f57, L},
 781         {0x1f59, 0x1f59, L},
 782         {0x1f5b, 0x1f5b, L},
 783         {0x1f5d, 0x1f5d, L},
 784         {0x1f5f, 0x1f7d, L},
 785         {0x1f80, 0x1fb4, L},
 786         {0x1fb6, 0x1fbc, L},
 787         {0x1fbe, 0x1fbe, L},
 788         {0x1fc2, 0x1fc4, L},
 789         {0x1fc6, 0x1fcc, L},
 790         {0x1fd0, 0x1fd3, L},
 791         {0x1fd6, 0x1fdb, L},
 792         {0x1fe0, 0x1fec, L},
 793         {0x1ff2, 0x1ff4, L},
 794         {0x1ff6, 0x1ffc, L},
 795         {0x2000, 0x200a, WS},
 796         {0x200b, 0x200d, BN},
 797         {0x200e, 0x200e, L},
 798         {0x200f, 0x200f, R},
 799         {0x2028, 0x2028, WS},
 800         {0x2029, 0x2029, B},
 801         {0x202a, 0x202a, LRE},
 802         {0x202b, 0x202b, RLE},
 803         {0x202c, 0x202c, PDF},
 804         {0x202d, 0x202d, LRO},
 805         {0x202e, 0x202e, RLO},
 806         {0x202f, 0x202f, WS},
 807         {0x2030, 0x2034, ET},
 808         {0x2044, 0x2044, CS},
 809         {0x205f, 0x205f, WS},
 810         {0x2060, 0x2063, BN},
 811         {0x206a, 0x206f, BN},
 812         {0x2070, 0x2070, EN},
 813         {0x2071, 0x2071, L},
 814         {0x2074, 0x2079, EN},
 815         {0x207a, 0x207b, ET},
 816         {0x207f, 0x207f, L},
 817         {0x2080, 0x2089, EN},
 818         {0x208a, 0x208b, ET},
 819         {0x20a0, 0x20b1, ET},
 820         {0x20d0, 0x20ea, NSM},
 821         {0x2102, 0x2102, L},
 822         {0x2107, 0x2107, L},
 823         {0x210a, 0x2113, L},
 824         {0x2115, 0x2115, L},
 825         {0x2119, 0x211d, L},
 826         {0x2124, 0x2124, L},
 827         {0x2126, 0x2126, L},
 828         {0x2128, 0x2128, L},
 829         {0x212a, 0x212d, L},
 830         {0x212e, 0x212e, ET},
 831         {0x212f, 0x2131, L},
 832         {0x2133, 0x2139, L},
 833         {0x213d, 0x213f, L},
 834         {0x2145, 0x2149, L},
 835         {0x2160, 0x2183, L},
 836         {0x2212, 0x2213, ET},
 837         {0x2336, 0x237a, L},
 838         {0x2395, 0x2395, L},
 839         {0x2488, 0x249b, EN},
 840         {0x249c, 0x24e9, L},
 841         {0x2800, 0x28ff, L},
 842         {0x3000, 0x3000, WS},
 843         {0x3005, 0x3007, L},
 844         {0x3021, 0x3029, L},
 845         {0x302a, 0x302f, NSM},
 846         {0x3031, 0x3035, L},
 847         {0x3038, 0x303c, L},
 848         {0x3041, 0x3096, L},
 849         {0x3099, 0x309a, NSM},
 850         {0x309d, 0x309f, L},
 851         {0x30a1, 0x30fa, L},
 852         {0x30fc, 0x30ff, L},
 853         {0x3105, 0x312c, L},
 854         {0x3131, 0x318e, L},
 855         {0x3190, 0x31b7, L},
 856         {0x31f0, 0x321c, L},
 857         {0x3220, 0x3243, L},
 858         {0x3260, 0x327b, L},
 859         {0x327f, 0x32b0, L},
 860         {0x32c0, 0x32cb, L},
 861         {0x32d0, 0x32fe, L},
 862         {0x3300, 0x3376, L},
 863         {0x337b, 0x33dd, L},
 864         {0x33e0, 0x33fe, L},
 865         {0x3400, 0x4db5, L},
 866         {0x4e00, 0x9fa5, L},
 867         {0xa000, 0xa48c, L},
 868         {0xac00, 0xd7a3, L},
 869         {0xd800, 0xfa2d, L},
 870         {0xfa30, 0xfa6a, L},
 871         {0xfb00, 0xfb06, L},
 872         {0xfb13, 0xfb17, L},
 873         {0xfb1d, 0xfb1d, R},
 874         {0xfb1e, 0xfb1e, NSM},
 875         {0xfb1f, 0xfb28, R},
 876         {0xfb29, 0xfb29, ET},
 877         {0xfb2a, 0xfb36, R},
 878         {0xfb38, 0xfb3c, R},
 879         {0xfb3e, 0xfb3e, R},
 880         {0xfb40, 0xfb41, R},
 881         {0xfb43, 0xfb44, R},
 882         {0xfb46, 0xfb4f, R},
 883         {0xfb50, 0xfbb1, AL},
 884         {0xfbd3, 0xfd3d, AL},
 885         {0xfd50, 0xfd8f, AL},
 886         {0xfd92, 0xfdc7, AL},
 887         {0xfdf0, 0xfdfc, AL},
 888         {0xfe00, 0xfe0f, NSM},
 889         {0xfe20, 0xfe23, NSM},
 890         {0xfe50, 0xfe50, CS},
 891         {0xfe52, 0xfe52, CS},
 892         {0xfe55, 0xfe55, CS},
 893         {0xfe5f, 0xfe5f, ET},
 894         {0xfe62, 0xfe63, ET},
 895         {0xfe69, 0xfe6a, ET},
 896         {0xfe70, 0xfe74, AL},
 897         {0xfe76, 0xfefc, AL},
 898         {0xfeff, 0xfeff, BN},
 899         {0xff03, 0xff05, ET},
 900         {0xff0b, 0xff0b, ET},
 901         {0xff0c, 0xff0c, CS},
 902         {0xff0d, 0xff0d, ET},
 903         {0xff0e, 0xff0e, CS},
 904         {0xff0f, 0xff0f, ES},
 905         {0xff10, 0xff19, EN},
 906         {0xff1a, 0xff1a, CS},
 907         {0xff21, 0xff3a, L},
 908         {0xff41, 0xff5a, L},
 909         {0xff66, 0xffbe, L},
 910         {0xffc2, 0xffc7, L},
 911         {0xffca, 0xffcf, L},
 912         {0xffd2, 0xffd7, L},
 913         {0xffda, 0xffdc, L},
 914         {0xffe0, 0xffe1, ET},
 915         {0xffe5, 0xffe6, ET},
 916         {0x10000, 0x1000b, L},
 917         {0x1000d, 0x10026, L},
 918         {0x10028, 0x1003a, L},
 919         {0x1003c, 0x1003d, L},
 920         {0x1003f, 0x1004d, L},
 921         {0x10050, 0x1005d, L},
 922         {0x10080, 0x100fa, L},
 923         {0x10100, 0x10100, L},
 924         {0x10102, 0x10102, L},
 925         {0x10107, 0x10133, L},
 926         {0x10137, 0x1013f, L},
 927         {0x10300, 0x1031e, L},
 928         {0x10320, 0x10323, L},
 929         {0x10330, 0x1034a, L},
 930         {0x10380, 0x1039d, L},
 931         {0x1039f, 0x1039f, L},
 932         {0x10400, 0x1049d, L},
 933         {0x104a0, 0x104a9, L},
 934         {0x10800, 0x10805, R},
 935         {0x10808, 0x10808, R},
 936         {0x1080a, 0x10835, R},
 937         {0x10837, 0x10838, R},
 938         {0x1083c, 0x1083c, R},
 939         {0x1083f, 0x1083f, R},
 940         {0x1d000, 0x1d0f5, L},
 941         {0x1d100, 0x1d126, L},
 942         {0x1d12a, 0x1d166, L},
 943         {0x1d167, 0x1d169, NSM},
 944         {0x1d16a, 0x1d172, L},
 945         {0x1d173, 0x1d17a, BN},
 946         {0x1d17b, 0x1d182, NSM},
 947         {0x1d183, 0x1d184, L},
 948         {0x1d185, 0x1d18b, NSM},
 949         {0x1d18c, 0x1d1a9, L},
 950         {0x1d1aa, 0x1d1ad, NSM},
 951         {0x1d1ae, 0x1d1dd, L},
 952         {0x1d400, 0x1d454, L},
 953         {0x1d456, 0x1d49c, L},
 954         {0x1d49e, 0x1d49f, L},
 955         {0x1d4a2, 0x1d4a2, L},
 956         {0x1d4a5, 0x1d4a6, L},
 957         {0x1d4a9, 0x1d4ac, L},
 958         {0x1d4ae, 0x1d4b9, L},
 959         {0x1d4bb, 0x1d4bb, L},
 960         {0x1d4bd, 0x1d4c3, L},
 961         {0x1d4c5, 0x1d505, L},
 962         {0x1d507, 0x1d50a, L},
 963         {0x1d50d, 0x1d514, L},
 964         {0x1d516, 0x1d51c, L},
 965         {0x1d51e, 0x1d539, L},
 966         {0x1d53b, 0x1d53e, L},
 967         {0x1d540, 0x1d544, L},
 968         {0x1d546, 0x1d546, L},
 969         {0x1d54a, 0x1d550, L},
 970         {0x1d552, 0x1d6a3, L},
 971         {0x1d6a8, 0x1d7c9, L},
 972         {0x1d7ce, 0x1d7ff, EN},
 973         {0x20000, 0x2a6d6, L},
 974         {0x2f800, 0x2fa1d, L},
 975         {0xe0001, 0xe0001, BN},
 976         {0xe0020, 0xe007f, BN},
 977         {0xe0100, 0xe01ef, NSM},
 978         {0xf0000, 0xffffd, L},
 979         {0x100000, 0x10fffd, L}
 980     };
 981
 982     int i, j, k;
 983
 984     i = -1;
 985     j = lenof(lookup);
 986
 987     while (j - i > 1) {
 988         k = (i + j) / 2;
 989         if (ch < lookup[k].first)
 990             j = k;
 991         else if (ch > lookup[k].last)
 992             i = k;
 993         else
 994             return lookup[k].type;
 995     }
 996
 997     /*
 998      * If we reach here, the character was not in any of the
 999      * intervals listed in the lookup table. This means we return
1000      * ON (`Other Neutrals'). This is the appropriate code for any
1001      * character genuinely not listed in the Unicode table, and
1002      * also the table above has deliberately left out any
1003      * characters _explicitly_ listed as ON (to save space!).
1004      */
1005     return ON;
1006 }
1007
1008 /*
1009  * Function exported to front ends to allow them to identify
1010  * bidi-active characters (in case, for example, the platform's
1011  * text display function can't conveniently be prevented from doing
1012  * its own bidi and so special treatment is required for characters
1013  * that would cause the bidi algorithm to activate).
1014  *
1015  * This function is passed a single Unicode code point, and returns
1016  * nonzero if the presence of this code point can possibly cause
1017  * the bidi algorithm to do any reordering. Thus, any string
1018  * composed entirely of characters for which is_rtl() returns zero
1019  * should be safe to pass to a bidi-active platform display
1020  * function without fear.
1021  *
1022  * (is_rtl() must therefore also return true for any character
1023  * which would be affected by Arabic shaping, but this isn't
1024  * important because all such characters are right-to-left so it
1025  * would have flagged them anyway.)
1026  */
1027 int is_rtl(int c)
1028 {
1029     /*
1030      * After careful reading of the Unicode bidi algorithm (URL as
1031      * given at the top of this file) I believe that the only
1032      * character classes which can possibly cause trouble are R,
1033      * AL, RLE and RLO. I think that any string containing no
1034      * character in any of those classes will be displayed
1035      * uniformly left-to-right by the Unicode bidi algorithm.
1036      */
1037     const int mask = (1<<R) | (1<<AL) | (1<<RLE) | (1<<RLO);
1038
1039     return mask & (1 << (getType(c)));
1040 }
1041
1042 /*
1043  * The most significant 2 bits of each level are used to store
1044  * Override status of each character
1045  * This function sets the override bits of level according
1046  * to the value in override, and reurns the new byte.
1047  */
1048 unsigned char setOverrideBits(unsigned char level, unsigned char override)
1049 {
1050     if (override == ON)
1051         return level;
1052     else if (override == R)
1053         return level | OISR;
1054     else if (override == L)
1055         return level | OISL;
1056     return level;
1057 }
1058
1059 /*
1060  * Find the most recent run of the same value in `level', and
1061  * return the value _before_ it. Used to process U+202C POP
1062  * DIRECTIONAL FORMATTING.
1063  */
1064 int getPreviousLevel(unsigned char* level, int from)
1065 {
1066     if (from > 0) {
1067         unsigned char current = level[--from];
1068
1069         while (from >= 0 && level[from] == current)
1070             from--;
1071
1072         if (from >= 0)
1073             return level[from];
1074
1075         return -1;
1076     } else
1077         return -1;
1078 }
1079
1080 /* The Main shaping function, and the only one to be used
1081  * by the outside world.
1082  *
1083  * line: buffer to apply shaping to. this must be passed by doBidi() first
1084  * to: output buffer for the shaped data
1085  * count: number of characters in line
1086  */
1087 int do_shape(bidi_char *line, bidi_char *to, int count)
1088 {
1089     int i, tempShape, ligFlag;
1090
1091     for (ligFlag=i=0; i<count; i++) {
1092         to[i] = line[i];
1093         tempShape = STYPE(line[i].wc);
1094         switch (tempShape) {
1095           case SC:
1096             break;
1097
1098           case SU:
1099             break;
1100
1101           case SR:
1102             tempShape = (i+1 < count ? STYPE(line[i+1].wc) : SU);
1103             if ((tempShape == SL) || (tempShape == SD) || (tempShape == SC))
1104                 to[i].wc = SFINAL((SISOLATED(line[i].wc)));
1105             else
1106                 to[i].wc = SISOLATED(line[i].wc);
1107             break;
1108
1109
1110           case SD:
1111             /* Make Ligatures */
1112             tempShape = (i+1 < count ? STYPE(line[i+1].wc) : SU);
1113             if (line[i].wc == 0x644) {
1114                 if (i > 0) switch (line[i-1].wc) {
1115                   case 0x622:
1116                     ligFlag = 1;
1117                     if ((tempShape == SL) || (tempShape == SD) || (tempShape == SC))
1118                         to[i].wc = 0xFEF6;
1119                     else
1120                         to[i].wc = 0xFEF5;
1121                     break;
1122                   case 0x623:
1123                     ligFlag = 1;
1124                     if ((tempShape == SL) || (tempShape == SD) || (tempShape == SC))
1125                         to[i].wc = 0xFEF8;
1126                     else
1127                         to[i].wc = 0xFEF7;
1128                     break;
1129                   case 0x625:
1130                     ligFlag = 1;
1131                     if ((tempShape == SL) || (tempShape == SD) || (tempShape == SC))
1132                         to[i].wc = 0xFEFA;
1133                     else
1134                         to[i].wc = 0xFEF9;
1135                     break;
1136                   case 0x627:
1137                     ligFlag = 1;
1138                     if ((tempShape == SL) || (tempShape == SD) || (tempShape == SC))
1139                         to[i].wc = 0xFEFC;
1140                     else
1141                         to[i].wc = 0xFEFB;
1142                     break;
1143                 }
1144                 if (ligFlag) {
1145                     to[i-1].wc = 0x20;
1146                     ligFlag = 0;
1147                     break;
1148                 }
1149             }
1150
1151             if ((tempShape == SL) || (tempShape == SD) || (tempShape == SC)) {
1152                 tempShape = (i > 0 ? STYPE(line[i-1].wc) : SU);
1153                 if ((tempShape == SR) || (tempShape == SD) || (tempShape == SC))
1154                     to[i].wc = SMEDIAL((SISOLATED(line[i].wc)));
1155                 else
1156                     to[i].wc = SFINAL((SISOLATED(line[i].wc)));
1157                 break;
1158             }
1159
1160             tempShape = (i > 0 ? STYPE(line[i-1].wc) : SU);
1161             if ((tempShape == SR) || (tempShape == SD) || (tempShape == SC))
1162                 to[i].wc = SINITIAL((SISOLATED(line[i].wc)));
1163             else
1164                 to[i].wc = SISOLATED(line[i].wc);
1165             break;
1166
1167
1168         }
1169     }
1170     return 1;
1171 }
1172
1173 /*
1174  * The Main Bidi Function, and the only function that should
1175  * be used by the outside world.
1176  *
1177  * line: a buffer of size count containing text to apply
1178  * the Bidirectional algorithm to.
1179  */
1180
1181 int do_bidi(bidi_char *line, int count)
1182 {
1183     unsigned char* types;
1184     unsigned char* levels;
1185     unsigned char paragraphLevel;
1186     unsigned char currentEmbedding;
1187     unsigned char currentOverride;
1188     unsigned char tempType;
1189     int i, j, yes, bover;
1190
1191     /* Check the presence of R or AL types as optimization */
1192     yes = 0;
1193     for (i=0; i<count; i++) {
1194         int type = getType(line[i].wc);
1195         if (type == R || type == AL) {
1196             yes = 1;
1197             break;
1198         }
1199     }
1200     if (yes == 0)
1201         return L;
1202
1203     /* Initialize types, levels */
1204     types = snewn(count, unsigned char);
1205     levels = snewn(count, unsigned char);
1206
1207     /* Rule (P1)  NOT IMPLEMENTED
1208      * P1. Split the text into separate paragraphs. A paragraph separator is
1209      * kept with the previous paragraph. Within each paragraph, apply all the
1210      * other rules of this algorithm.
1211      */
1212
1213     /* Rule (P2), (P3)
1214      * P2. In each paragraph, find the first character of type L, AL, or R.
1215      * P3. If a character is found in P2 and it is of type AL or R, then set
1216      * the paragraph embedding level to one; otherwise, set it to zero.
1217      */
1218     paragraphLevel = 0;
1219     for (i=0; i<count ; i++) {
1220         int type = getType(line[i].wc);
1221         if (type == R || type == AL) {
1222             paragraphLevel = 1;
1223             break;
1224         } else if (type == L)
1225             break;
1226     }
1227
1228     /* Rule (X1)
1229      * X1. Begin by setting the current embedding level to the paragraph
1230      * embedding level. Set the directional override status to neutral.
1231      */
1232     currentEmbedding = paragraphLevel;
1233     currentOverride = ON;
1234
1235     /* Rule (X2), (X3), (X4), (X5), (X6), (X7), (X8)
1236      * X2. With each RLE, compute the least greater odd embedding level.
1237      * X3. With each LRE, compute the least greater even embedding level.
1238      * X4. With each RLO, compute the least greater odd embedding level.
1239      * X5. With each LRO, compute the least greater even embedding level.
1240      * X6. For all types besides RLE, LRE, RLO, LRO, and PDF:
1241      *          a. Set the level of the current character to the current
1242      *              embedding level.
1243      *          b.  Whenever the directional override status is not neutral,
1244      *               reset the current character type to the directional
1245      *               override status.
1246      * X7. With each PDF, determine the matching embedding or override code.
1247      * If there was a valid matching code, restore (pop) the last
1248      * remembered (pushed) embedding level and directional override.
1249      * X8. All explicit directional embeddings and overrides are completely
1250      * terminated at the end of each paragraph. Paragraph separators are not
1251      * included in the embedding. (Useless here) NOT IMPLEMENTED
1252      */
1253     bover = 0;
1254     for (i=0; i<count; i++) {
1255         tempType = getType(line[i].wc);
1256         switch (tempType) {
1257           case RLE:
1258             currentEmbedding = levels[i] = leastGreaterOdd(currentEmbedding);
1259             levels[i] = setOverrideBits(levels[i], currentOverride);
1260             currentOverride = ON;
1261             break;
1262
1263           case LRE:
1264             currentEmbedding = levels[i] = leastGreaterEven(currentEmbedding);
1265             levels[i] = setOverrideBits(levels[i], currentOverride);
1266             currentOverride = ON;
1267             break;
1268
1269           case RLO:
1270             currentEmbedding = levels[i] = leastGreaterOdd(currentEmbedding);
1271             tempType = currentOverride = R;
1272             bover = 1;
1273             break;
1274
1275           case LRO:
1276             currentEmbedding = levels[i] = leastGreaterEven(currentEmbedding);
1277             tempType = currentOverride = L;
1278             bover = 1;
1279             break;
1280
1281           case PDF:
1282             {
1283                 int prevlevel = getPreviousLevel(levels, i);
1284
1285                 if (prevlevel == -1) {
1286                     currentEmbedding = paragraphLevel;
1287                     currentOverride = ON;
1288                 } else {
1289                     currentOverride = currentEmbedding & OMASK;
1290                     currentEmbedding = currentEmbedding & ~OMASK;
1291                 }
1292             }
1293             levels[i] = currentEmbedding;
1294             break;
1295
1296             /* Whitespace is treated as neutral for now */
1297           case WS:
1298           case S:
1299             levels[i] = currentEmbedding;
1300             tempType = ON;
1301             if (currentOverride != ON)
1302                 tempType = currentOverride;
1303             break;
1304
1305           default:
1306             levels[i] = currentEmbedding;
1307             if (currentOverride != ON)
1308                 tempType = currentOverride;
1309             break;
1310
1311         }
1312         types[i] = tempType;
1313     }
1314     /* this clears out all overrides, so we can use levels safely... */
1315     /* checks bover first */
1316     if (bover)
1317         for (i=0; i<count; i++)
1318             levels[i] = levels[i] & LMASK;
1319
1320     /* Rule (X9)
1321      * X9. Remove all RLE, LRE, RLO, LRO, PDF, and BN codes.
1322      * Here, they're converted to BN.
1323      */
1324     for (i=0; i<count; i++) {
1325         switch (types[i]) {
1326           case RLE:
1327           case LRE:
1328           case RLO:
1329           case LRO:
1330           case PDF:
1331             types[i] = BN;
1332             break;
1333         }
1334     }
1335
1336     /* Rule (W1)
1337      * W1. Examine each non-spacing mark (NSM) in the level run, and change
1338      * the type of the NSM to the type of the previous character. If the NSM
1339      * is at the start of the level run, it will get the type of sor.
1340      */
1341     if (types[0] == NSM)
1342         types[0] = paragraphLevel;
1343
1344     for (i=1; i<count; i++) {
1345         if (types[i] == NSM)
1346             types[i] = types[i-1];
1347         /* Is this a safe assumption?
1348          * I assumed the previous, IS a character.
1349          */
1350     }
1351
1352     /* Rule (W2)
1353      * W2. Search backwards from each instance of a European number until the
1354      * first strong type (R, L, AL, or sor) is found.  If an AL is found,
1355      * change the type of the European number to Arabic number.
1356      */
1357     for (i=0; i<count; i++) {
1358         if (types[i] == EN) {
1359             j=i;
1360             while (j >= 0) {
1361                 if (types[j] == AL) {
1362                     types[i] = AN;
1363                     break;
1364                 } else if (types[j] == R || types[j] == L) {
1365                     break;
1366                 }
1367                 j--;
1368             }
1369         }
1370     }
1371
1372     /* Rule (W3)
1373      * W3. Change all ALs to R.
1374      *
1375      * Optimization: on Rule Xn, we might set a flag on AL type
1376      * to prevent this loop in L R lines only...
1377      */
1378     for (i=0; i<count; i++) {
1379         if (types[i] == AL)
1380             types[i] = R;
1381     }
1382
1383     /* Rule (W4)
1384      * W4. A single European separator between two European numbers changes
1385      * to a European number. A single common separator between two numbers
1386      * of the same type changes to that type.
1387      */
1388     for (i=1; i<(count-1); i++) {
1389         if (types[i] == ES) {
1390             if (types[i-1] == EN && types[i+1] == EN)
1391                 types[i] = EN;
1392         } else if (types[i] == CS) {
1393             if (types[i-1] == EN && types[i+1] == EN)
1394                 types[i] = EN;
1395             else if (types[i-1] == AN && types[i+1] == AN)
1396                 types[i] = AN;
1397         }
1398     }
1399
1400     /* Rule (W5)
1401      * W5. A sequence of European terminators adjacent to European numbers
1402      * changes to all European numbers.
1403      *
1404      * Optimization: lots here... else ifs need rearrangement
1405      */
1406     for (i=0; i<count; i++) {
1407         if (types[i] == ET) {
1408             if (i > 0 && types[i-1] == EN) {
1409                 types[i] = EN;
1410                 continue;
1411             } else if (i < count-1 && types[i+1] == EN) {
1412                 types[i] = EN;
1413                 continue;
1414             } else if (i < count-1 && types[i+1] == ET) {
1415                 j=i;
1416                 while (j <count && types[j] == ET) {
1417                     j++;
1418                 }
1419                 if (types[j] == EN)
1420                     types[i] = EN;
1421             }
1422         }
1423     }
1424
1425     /* Rule (W6)
1426      * W6. Otherwise, separators and terminators change to Other Neutral:
1427      */
1428     for (i=0; i<count; i++) {
1429         switch (types[i]) {
1430           case ES:
1431           case ET:
1432           case CS:
1433             types[i] = ON;
1434             break;
1435         }
1436     }
1437
1438     /* Rule (W7)
1439      * W7. Search backwards from each instance of a European number until
1440      * the first strong type (R, L, or sor) is found. If an L is found,
1441      * then change the type of the European number to L.
1442      */
1443     for (i=0; i<count; i++) {
1444         if (types[i] == EN) {
1445             j=i;
1446             while (j >= 0) {
1447                 if (types[j] == L) {
1448                     types[i] = L;
1449                     break;
1450                 } else if (types[j] == R || types[j] == AL) {
1451                     break;
1452                 }
1453                 j--;
1454             }
1455         }
1456     }
1457
1458     /* Rule (N1)
1459      * N1. A sequence of neutrals takes the direction of the surrounding
1460      * strong text if the text on both sides has the same direction. European
1461      * and Arabic numbers are treated as though they were R.
1462      */
1463     if (count >= 2 && types[0] == ON) {
1464         if ((types[1] == R) || (types[1] == EN) || (types[1] == AN))
1465             types[0] = R;
1466         else if (types[1] == L)
1467             types[0] = L;
1468     }
1469     for (i=1; i<(count-1); i++) {
1470         if (types[i] == ON) {
1471             if (types[i-1] == L) {
1472                 j=i;
1473                 while (j<(count-1) && types[j] == ON) {
1474                     j++;
1475                 }
1476                 if (types[j] == L) {
1477                     while (i<j) {
1478                         types[i] = L;
1479                         i++;
1480                     }
1481                 }
1482
1483             } else if ((types[i-1] == R)  ||
1484                        (types[i-1] == EN) ||
1485                        (types[i-1] == AN)) {
1486                 j=i;
1487                 while (j<(count-1) && types[j] == ON) {
1488                     j++;
1489                 }
1490                 if ((types[j] == R)  ||
1491                     (types[j] == EN) ||
1492                     (types[j] == AN)) {
1493                     while (i<j) {
1494                         types[i] = R;
1495                         i++;
1496                     }
1497                 }
1498             }
1499         }
1500     }
1501     if (count >= 2 && types[count-1] == ON) {
1502         if (types[count-2] == R || types[count-2] == EN || types[count-2] == AN)
1503             types[count-1] = R;
1504         else if (types[count-2] == L)
1505             types[count-1] = L;
1506     }
1507
1508     /* Rule (N2)
1509      * N2. Any remaining neutrals take the embedding direction.
1510      */
1511     for (i=0; i<count; i++) {
1512         if (types[i] == ON) {
1513             if ((levels[i] % 2) == 0)
1514                 types[i] = L;
1515             else
1516                 types[i] = R;
1517         }
1518     }
1519
1520     /* Rule (I1)
1521      * I1. For all characters with an even (left-to-right) embedding
1522      * direction, those of type R go up one level and those of type AN or
1523      * EN go up two levels.
1524      */
1525     for (i=0; i<count; i++) {
1526         if ((levels[i] % 2) == 0) {
1527             if (types[i] == R)
1528                 levels[i] += 1;
1529             else if (types[i] == AN || types[i] == EN)
1530                 levels[i] += 2;
1531         }
1532     }
1533
1534     /* Rule (I2)
1535      * I2. For all characters with an odd (right-to-left) embedding direction,
1536      * those of type L, EN or AN go up one level.
1537      */
1538     for (i=0; i<count; i++) {
1539         if ((levels[i] % 2) == 1) {
1540             if (types[i] == L || types[i] == EN || types[i] == AN)
1541                 levels[i] += 1;
1542         }
1543     }
1544
1545     /* Rule (L1)
1546      * L1. On each line, reset the embedding level of the following characters
1547      * to the paragraph embedding level:
1548      *          (1)segment separators, (2)paragraph separators,
1549      *           (3)any sequence of whitespace characters preceding
1550      *           a segment separator or paragraph separator,
1551      *           (4)and any sequence of white space characters
1552      *           at the end of the line.
1553      * The types of characters used here are the original types, not those
1554      * modified by the previous phase.
1555      */
1556     j=count-1;
1557     while (j>0 && (getType(line[j].wc) == WS)) {
1558         j--;
1559     }
1560     if (j < (count-1)) {
1561         for (j++; j<count; j++)
1562             levels[j] = paragraphLevel;
1563     }
1564     for (i=0; i<count; i++) {
1565         tempType = getType(line[i].wc);
1566         if (tempType == WS) {
1567             j=i;
1568             while (j<count && (getType(line[j].wc) == WS)) {
1569                 j++;
1570             }
1571             if (j==count || getType(line[j].wc) == B ||
1572                 getType(line[j].wc) == S) {
1573                 for (j--; j>=i ; j--) {
1574                     levels[j] = paragraphLevel;
1575                 }
1576             }
1577         } else if (tempType == B || tempType == S) {
1578             levels[i] = paragraphLevel;
1579         }
1580     }
1581
1582     /* Rule (L4) NOT IMPLEMENTED
1583      * L4. A character that possesses the mirrored property as specified by
1584      * Section 4.7, Mirrored, must be depicted by a mirrored glyph if the
1585      * resolved directionality of that character is R.
1586      */
1587     /* Note: this is implemented before L2 for efficiency */
1588     for (i=0; i<count; i++)
1589         if ((levels[i] % 2) == 1)
1590             doMirror(&line[i].wc);
1591
1592     /* Rule (L2)
1593      * L2. From the highest level found in the text to the lowest odd level on
1594      * each line, including intermediate levels not actually present in the
1595      * text, reverse any contiguous sequence of characters that are at that
1596      * level or higher
1597      */
1598     /* we flip the character string and leave the level array */
1599     i=0;
1600     tempType = levels[0];
1601     while (i < count) {
1602         if (levels[i] > tempType)
1603             tempType = levels[i];
1604         i++;
1605     }
1606     /* maximum level in tempType. */
1607     while (tempType > 0) {     /* loop from highest level to the least odd, */
1608         /* which i assume is 1 */
1609         flipThisRun(line, levels, tempType, count);
1610         tempType--;
1611     }
1612
1613     /* Rule (L3) NOT IMPLEMENTED
1614      * L3. Combining marks applied to a right-to-left base character will at
1615      * this point precede their base character. If the rendering engine
1616      * expects them to follow the base characters in the final display
1617      * process, then the ordering of the marks and the base character must
1618      * be reversed.
1619      */
1620     sfree(types);
1621     sfree(levels);
1622     return R;
1623 }
1624
1625
1626 /*
1627  * Bad, Horrible function
1628  * takes a pointer to a character that is checked for
1629  * having a mirror glyph.
1630  */
1631 void doMirror(unsigned int *ch)
1632 {
1633     if ((*ch & 0xFF00) == 0) {
1634         switch (*ch) {
1635           case 0x0028: *ch = 0x0029; break;
1636           case 0x0029: *ch = 0x0028; break;
1637           case 0x003C: *ch = 0x003E; break;
1638           case 0x003E: *ch = 0x003C; break;
1639           case 0x005B: *ch = 0x005D; break;
1640           case 0x005D: *ch = 0x005B; break;
1641           case 0x007B: *ch = 0x007D; break;
1642           case 0x007D: *ch = 0x007B; break;
1643           case 0x00AB: *ch = 0x00BB; break;
1644           case 0x00BB: *ch = 0x00AB; break;
1645         }
1646     } else if ((*ch & 0xFF00) == 0x2000) {
1647         switch (*ch) {
1648           case 0x2039: *ch = 0x203A; break;
1649           case 0x203A: *ch = 0x2039; break;
1650           case 0x2045: *ch = 0x2046; break;
1651           case 0x2046: *ch = 0x2045; break;
1652           case 0x207D: *ch = 0x207E; break;
1653           case 0x207E: *ch = 0x207D; break;
1654           case 0x208D: *ch = 0x208E; break;
1655           case 0x208E: *ch = 0x208D; break;
1656         }
1657     } else if ((*ch & 0xFF00) == 0x2200) {
1658         switch (*ch) {
1659           case 0x2208: *ch = 0x220B; break;
1660           case 0x2209: *ch = 0x220C; break;
1661           case 0x220A: *ch = 0x220D; break;
1662           case 0x220B: *ch = 0x2208; break;
1663           case 0x220C: *ch = 0x2209; break;
1664           case 0x220D: *ch = 0x220A; break;
1665           case 0x2215: *ch = 0x29F5; break;
1666           case 0x223C: *ch = 0x223D; break;
1667           case 0x223D: *ch = 0x223C; break;
1668           case 0x2243: *ch = 0x22CD; break;
1669           case 0x2252: *ch = 0x2253; break;
1670           case 0x2253: *ch = 0x2252; break;
1671           case 0x2254: *ch = 0x2255; break;
1672           case 0x2255: *ch = 0x2254; break;
1673           case 0x2264: *ch = 0x2265; break;
1674           case 0x2265: *ch = 0x2264; break;
1675           case 0x2266: *ch = 0x2267; break;
1676           case 0x2267: *ch = 0x2266; break;
1677           case 0x2268: *ch = 0x2269; break;
1678           case 0x2269: *ch = 0x2268; break;
1679           case 0x226A: *ch = 0x226B; break;
1680           case 0x226B: *ch = 0x226A; break;
1681           case 0x226E: *ch = 0x226F; break;
1682           case 0x226F: *ch = 0x226E; break;
1683           case 0x2270: *ch = 0x2271; break;
1684           case 0x2271: *ch = 0x2270; break;
1685           case 0x2272: *ch = 0x2273; break;
1686           case 0x2273: *ch = 0x2272; break;
1687           case 0x2274: *ch = 0x2275; break;
1688           case 0x2275: *ch = 0x2274; break;
1689           case 0x2276: *ch = 0x2277; break;
1690           case 0x2277: *ch = 0x2276; break;
1691           case 0x2278: *ch = 0x2279; break;
1692           case 0x2279: *ch = 0x2278; break;
1693           case 0x227A: *ch = 0x227B; break;
1694           case 0x227B: *ch = 0x227A; break;
1695           case 0x227C: *ch = 0x227D; break;
1696           case 0x227D: *ch = 0x227C; break;
1697           case 0x227E: *ch = 0x227F; break;
1698           case 0x227F: *ch = 0x227E; break;
1699           case 0x2280: *ch = 0x2281; break;
1700           case 0x2281: *ch = 0x2280; break;
1701           case 0x2282: *ch = 0x2283; break;
1702           case 0x2283: *ch = 0x2282; break;
1703           case 0x2284: *ch = 0x2285; break;
1704           case 0x2285: *ch = 0x2284; break;
1705           case 0x2286: *ch = 0x2287; break;
1706           case 0x2287: *ch = 0x2286; break;
1707           case 0x2288: *ch = 0x2289; break;
1708           case 0x2289: *ch = 0x2288; break;
1709           case 0x228A: *ch = 0x228B; break;
1710           case 0x228B: *ch = 0x228A; break;
1711           case 0x228F: *ch = 0x2290; break;
1712           case 0x2290: *ch = 0x228F; break;
1713           case 0x2291: *ch = 0x2292; break;
1714           case 0x2292: *ch = 0x2291; break;
1715           case 0x2298: *ch = 0x29B8; break;
1716           case 0x22A2: *ch = 0x22A3; break;
1717           case 0x22A3: *ch = 0x22A2; break;
1718           case 0x22A6: *ch = 0x2ADE; break;
1719           case 0x22A8: *ch = 0x2AE4; break;
1720           case 0x22A9: *ch = 0x2AE3; break;
1721           case 0x22AB: *ch = 0x2AE5; break;
1722           case 0x22B0: *ch = 0x22B1; break;
1723           case 0x22B1: *ch = 0x22B0; break;
1724           case 0x22B2: *ch = 0x22B3; break;
1725           case 0x22B3: *ch = 0x22B2; break;
1726           case 0x22B4: *ch = 0x22B5; break;
1727           case 0x22B5: *ch = 0x22B4; break;
1728           case 0x22B6: *ch = 0x22B7; break;
1729           case 0x22B7: *ch = 0x22B6; break;
1730           case 0x22C9: *ch = 0x22CA; break;
1731           case 0x22CA: *ch = 0x22C9; break;
1732           case 0x22CB: *ch = 0x22CC; break;
1733           case 0x22CC: *ch = 0x22CB; break;
1734           case 0x22CD: *ch = 0x2243; break;
1735           case 0x22D0: *ch = 0x22D1; break;
1736           case 0x22D1: *ch = 0x22D0; break;
1737           case 0x22D6: *ch = 0x22D7; break;
1738           case 0x22D7: *ch = 0x22D6; break;
1739           case 0x22D8: *ch = 0x22D9; break;
1740           case 0x22D9: *ch = 0x22D8; break;
1741           case 0x22DA: *ch = 0x22DB; break;
1742           case 0x22DB: *ch = 0x22DA; break;
1743           case 0x22DC: *ch = 0x22DD; break;
1744           case 0x22DD: *ch = 0x22DC; break;
1745           case 0x22DE: *ch = 0x22DF; break;
1746           case 0x22DF: *ch = 0x22DE; break;
1747           case 0x22E0: *ch = 0x22E1; break;
1748           case 0x22E1: *ch = 0x22E0; break;
1749           case 0x22E2: *ch = 0x22E3; break;
1750           case 0x22E3: *ch = 0x22E2; break;
1751           case 0x22E4: *ch = 0x22E5; break;
1752           case 0x22E5: *ch = 0x22E4; break;
1753           case 0x22E6: *ch = 0x22E7; break;
1754           case 0x22E7: *ch = 0x22E6; break;
1755           case 0x22E8: *ch = 0x22E9; break;
1756           case 0x22E9: *ch = 0x22E8; break;
1757           case 0x22EA: *ch = 0x22EB; break;
1758           case 0x22EB: *ch = 0x22EA; break;
1759           case 0x22EC: *ch = 0x22ED; break;
1760           case 0x22ED: *ch = 0x22EC; break;
1761           case 0x22F0: *ch = 0x22F1; break;
1762           case 0x22F1: *ch = 0x22F0; break;
1763           case 0x22F2: *ch = 0x22FA; break;
1764           case 0x22F3: *ch = 0x22FB; break;
1765           case 0x22F4: *ch = 0x22FC; break;
1766           case 0x22F6: *ch = 0x22FD; break;
1767           case 0x22F7: *ch = 0x22FE; break;
1768           case 0x22FA: *ch = 0x22F2; break;
1769           case 0x22FB: *ch = 0x22F3; break;
1770           case 0x22FC: *ch = 0x22F4; break;
1771           case 0x22FD: *ch = 0x22F6; break;
1772           case 0x22FE: *ch = 0x22F7; break;
1773         }
1774     } else if ((*ch & 0xFF00) == 0x2300) {
1775         switch (*ch) {
1776           case 0x2308: *ch = 0x2309; break;
1777           case 0x2309: *ch = 0x2308; break;
1778           case 0x230A: *ch = 0x230B; break;
1779           case 0x230B: *ch = 0x230A; break;
1780           case 0x2329: *ch = 0x232A; break;
1781           case 0x232A: *ch = 0x2329; break;
1782         }
1783     } else if ((*ch & 0xFF00) == 0x2700) {
1784         switch (*ch) {
1785           case 0x2768: *ch = 0x2769; break;
1786           case 0x2769: *ch = 0x2768; break;
1787           case 0x276A: *ch = 0x276B; break;
1788           case 0x276B: *ch = 0x276A; break;
1789           case 0x276C: *ch = 0x276D; break;
1790           case 0x276D: *ch = 0x276C; break;
1791           case 0x276E: *ch = 0x276F; break;
1792           case 0x276F: *ch = 0x276E; break;
1793           case 0x2770: *ch = 0x2771; break;
1794           case 0x2771: *ch = 0x2770; break;
1795           case 0x2772: *ch = 0x2773; break;
1796           case 0x2773: *ch = 0x2772; break;
1797           case 0x2774: *ch = 0x2775; break;
1798           case 0x2775: *ch = 0x2774; break;
1799           case 0x27D5: *ch = 0x27D6; break;
1800           case 0x27D6: *ch = 0x27D5; break;
1801           case 0x27DD: *ch = 0x27DE; break;
1802           case 0x27DE: *ch = 0x27DD; break;
1803           case 0x27E2: *ch = 0x27E3; break;
1804           case 0x27E3: *ch = 0x27E2; break;
1805           case 0x27E4: *ch = 0x27E5; break;
1806           case 0x27E5: *ch = 0x27E4; break;
1807           case 0x27E6: *ch = 0x27E7; break;
1808           case 0x27E7: *ch = 0x27E6; break;
1809           case 0x27E8: *ch = 0x27E9; break;
1810           case 0x27E9: *ch = 0x27E8; break;
1811           case 0x27EA: *ch = 0x27EB; break;
1812           case 0x27EB: *ch = 0x27EA; break;
1813         }
1814     } else if ((*ch & 0xFF00) == 0x2900) {
1815         switch (*ch) {
1816           case 0x2983: *ch = 0x2984; break;
1817           case 0x2984: *ch = 0x2983; break;
1818           case 0x2985: *ch = 0x2986; break;
1819           case 0x2986: *ch = 0x2985; break;
1820           case 0x2987: *ch = 0x2988; break;
1821           case 0x2988: *ch = 0x2987; break;
1822           case 0x2989: *ch = 0x298A; break;
1823           case 0x298A: *ch = 0x2989; break;
1824           case 0x298B: *ch = 0x298C; break;
1825           case 0x298C: *ch = 0x298B; break;
1826           case 0x298D: *ch = 0x2990; break;
1827           case 0x298E: *ch = 0x298F; break;
1828           case 0x298F: *ch = 0x298E; break;
1829           case 0x2990: *ch = 0x298D; break;
1830           case 0x2991: *ch = 0x2992; break;
1831           case 0x2992: *ch = 0x2991; break;
1832           case 0x2993: *ch = 0x2994; break;
1833           case 0x2994: *ch = 0x2993; break;
1834           case 0x2995: *ch = 0x2996; break;
1835           case 0x2996: *ch = 0x2995; break;
1836           case 0x2997: *ch = 0x2998; break;
1837           case 0x2998: *ch = 0x2997; break;
1838           case 0x29B8: *ch = 0x2298; break;
1839           case 0x29C0: *ch = 0x29C1; break;
1840           case 0x29C1: *ch = 0x29C0; break;
1841           case 0x29C4: *ch = 0x29C5; break;
1842           case 0x29C5: *ch = 0x29C4; break;
1843           case 0x29CF: *ch = 0x29D0; break;
1844           case 0x29D0: *ch = 0x29CF; break;
1845           case 0x29D1: *ch = 0x29D2; break;
1846           case 0x29D2: *ch = 0x29D1; break;
1847           case 0x29D4: *ch = 0x29D5; break;
1848           case 0x29D5: *ch = 0x29D4; break;
1849           case 0x29D8: *ch = 0x29D9; break;
1850           case 0x29D9: *ch = 0x29D8; break;
1851           case 0x29DA: *ch = 0x29DB; break;
1852           case 0x29DB: *ch = 0x29DA; break;
1853           case 0x29F5: *ch = 0x2215; break;
1854           case 0x29F8: *ch = 0x29F9; break;
1855           case 0x29F9: *ch = 0x29F8; break;
1856           case 0x29FC: *ch = 0x29FD; break;
1857           case 0x29FD: *ch = 0x29FC; break;
1858         }
1859     } else if ((*ch & 0xFF00) == 0x2A00) {
1860         switch (*ch) {
1861           case 0x2A2B: *ch = 0x2A2C; break;
1862           case 0x2A2C: *ch = 0x2A2B; break;
1863           case 0x2A2D: *ch = 0x2A2C; break;
1864           case 0x2A2E: *ch = 0x2A2D; break;
1865           case 0x2A34: *ch = 0x2A35; break;
1866           case 0x2A35: *ch = 0x2A34; break;
1867           case 0x2A3C: *ch = 0x2A3D; break;
1868           case 0x2A3D: *ch = 0x2A3C; break;
1869           case 0x2A64: *ch = 0x2A65; break;
1870           case 0x2A65: *ch = 0x2A64; break;
1871           case 0x2A79: *ch = 0x2A7A; break;
1872           case 0x2A7A: *ch = 0x2A79; break;
1873           case 0x2A7D: *ch = 0x2A7E; break;
1874           case 0x2A7E: *ch = 0x2A7D; break;
1875           case 0x2A7F: *ch = 0x2A80; break;
1876           case 0x2A80: *ch = 0x2A7F; break;
1877           case 0x2A81: *ch = 0x2A82; break;
1878           case 0x2A82: *ch = 0x2A81; break;
1879           case 0x2A83: *ch = 0x2A84; break;
1880           case 0x2A84: *ch = 0x2A83; break;
1881           case 0x2A8B: *ch = 0x2A8C; break;
1882           case 0x2A8C: *ch = 0x2A8B; break;
1883           case 0x2A91: *ch = 0x2A92; break;
1884           case 0x2A92: *ch = 0x2A91; break;
1885           case 0x2A93: *ch = 0x2A94; break;
1886           case 0x2A94: *ch = 0x2A93; break;
1887           case 0x2A95: *ch = 0x2A96; break;
1888           case 0x2A96: *ch = 0x2A95; break;
1889           case 0x2A97: *ch = 0x2A98; break;
1890           case 0x2A98: *ch = 0x2A97; break;
1891           case 0x2A99: *ch = 0x2A9A; break;
1892           case 0x2A9A: *ch = 0x2A99; break;
1893           case 0x2A9B: *ch = 0x2A9C; break;
1894           case 0x2A9C: *ch = 0x2A9B; break;
1895           case 0x2AA1: *ch = 0x2AA2; break;
1896           case 0x2AA2: *ch = 0x2AA1; break;
1897           case 0x2AA6: *ch = 0x2AA7; break;
1898           case 0x2AA7: *ch = 0x2AA6; break;
1899           case 0x2AA8: *ch = 0x2AA9; break;
1900           case 0x2AA9: *ch = 0x2AA8; break;
1901           case 0x2AAA: *ch = 0x2AAB; break;
1902           case 0x2AAB: *ch = 0x2AAA; break;
1903           case 0x2AAC: *ch = 0x2AAD; break;
1904           case 0x2AAD: *ch = 0x2AAC; break;
1905           case 0x2AAF: *ch = 0x2AB0; break;
1906           case 0x2AB0: *ch = 0x2AAF; break;
1907           case 0x2AB3: *ch = 0x2AB4; break;
1908           case 0x2AB4: *ch = 0x2AB3; break;
1909           case 0x2ABB: *ch = 0x2ABC; break;
1910           case 0x2ABC: *ch = 0x2ABB; break;
1911           case 0x2ABD: *ch = 0x2ABE; break;
1912           case 0x2ABE: *ch = 0x2ABD; break;
1913           case 0x2ABF: *ch = 0x2AC0; break;
1914           case 0x2AC0: *ch = 0x2ABF; break;
1915           case 0x2AC1: *ch = 0x2AC2; break;
1916           case 0x2AC2: *ch = 0x2AC1; break;
1917           case 0x2AC3: *ch = 0x2AC4; break;
1918           case 0x2AC4: *ch = 0x2AC3; break;
1919           case 0x2AC5: *ch = 0x2AC6; break;
1920           case 0x2AC6: *ch = 0x2AC5; break;
1921           case 0x2ACD: *ch = 0x2ACE; break;
1922           case 0x2ACE: *ch = 0x2ACD; break;
1923           case 0x2ACF: *ch = 0x2AD0; break;
1924           case 0x2AD0: *ch = 0x2ACF; break;
1925           case 0x2AD1: *ch = 0x2AD2; break;
1926           case 0x2AD2: *ch = 0x2AD1; break;
1927           case 0x2AD3: *ch = 0x2AD4; break;
1928           case 0x2AD4: *ch = 0x2AD3; break;
1929           case 0x2AD5: *ch = 0x2AD6; break;
1930           case 0x2AD6: *ch = 0x2AD5; break;
1931           case 0x2ADE: *ch = 0x22A6; break;
1932           case 0x2AE3: *ch = 0x22A9; break;
1933           case 0x2AE4: *ch = 0x22A8; break;
1934           case 0x2AE5: *ch = 0x22AB; break;
1935           case 0x2AEC: *ch = 0x2AED; break;
1936           case 0x2AED: *ch = 0x2AEC; break;
1937           case 0x2AF7: *ch = 0x2AF8; break;
1938           case 0x2AF8: *ch = 0x2AF7; break;
1939           case 0x2AF9: *ch = 0x2AFA; break;
1940           case 0x2AFA: *ch = 0x2AF9; break;
1941         }
1942     } else if ((*ch & 0xFF00) == 0x3000) {
1943         switch (*ch) {
1944           case 0x3008: *ch = 0x3009; break;
1945           case 0x3009: *ch = 0x3008; break;
1946           case 0x300A: *ch = 0x300B; break;
1947           case 0x300B: *ch = 0x300A; break;
1948           case 0x300C: *ch = 0x300D; break;
1949           case 0x300D: *ch = 0x300C; break;
1950           case 0x300E: *ch = 0x300F; break;
1951           case 0x300F: *ch = 0x300E; break;
1952           case 0x3010: *ch = 0x3011; break;
1953           case 0x3011: *ch = 0x3010; break;
1954           case 0x3014: *ch = 0x3015; break;
1955           case 0x3015: *ch = 0x3014; break;
1956           case 0x3016: *ch = 0x3017; break;
1957           case 0x3017: *ch = 0x3016; break;
1958           case 0x3018: *ch = 0x3019; break;
1959           case 0x3019: *ch = 0x3018; break;
1960           case 0x301A: *ch = 0x301B; break;
1961           case 0x301B: *ch = 0x301A; break;
1962         }
1963     } else if ((*ch & 0xFF00) == 0xFF00) {
1964         switch (*ch) {
1965           case 0xFF08: *ch = 0xFF09; break;
1966           case 0xFF09: *ch = 0xFF08; break;
1967           case 0xFF1C: *ch = 0xFF1E; break;
1968           case 0xFF1E: *ch = 0xFF1C; break;
1969           case 0xFF3B: *ch = 0xFF3D; break;
1970           case 0xFF3D: *ch = 0xFF3B; break;
1971           case 0xFF5B: *ch = 0xFF5D; break;
1972           case 0xFF5D: *ch = 0xFF5B; break;
1973           case 0xFF5F: *ch = 0xFF60; break;
1974           case 0xFF60: *ch = 0xFF5F; break;
1975           case 0xFF62: *ch = 0xFF63; break;
1976           case 0xFF63: *ch = 0xFF62; break;
1977         }
1978     }
1979 }
1980
1981 #ifdef TEST_GETTYPE
1982
1983 #include <stdio.h>
1984 #include <assert.h>
1985
1986 int main(int argc, char **argv)
1987 {
1988     static const struct { int type; char *name; } typetoname[] = {
1989 #define TYPETONAME(X) { X , #X }
1990         TYPETONAME(L),
1991         TYPETONAME(LRE),
1992         TYPETONAME(LRO),
1993         TYPETONAME(R),
1994         TYPETONAME(AL),
1995         TYPETONAME(RLE),
1996         TYPETONAME(RLO),
1997         TYPETONAME(PDF),
1998         TYPETONAME(EN),
1999         TYPETONAME(ES),
2000         TYPETONAME(ET),
2001         TYPETONAME(AN),
2002         TYPETONAME(CS),
2003         TYPETONAME(NSM),
2004         TYPETONAME(BN),
2005         TYPETONAME(B),
2006         TYPETONAME(S),
2007         TYPETONAME(WS),
2008         TYPETONAME(ON),
2009 #undef TYPETONAME
2010     };
2011     int i;
2012
2013     for (i = 1; i < argc; i++) {
2014         unsigned long chr = strtoul(argv[i], NULL, 0);
2015         int type = getType(chr);
2016         assert(typetoname[type].type == type);
2017         printf("U+%04x: %s\n", chr, typetoname[type].name);
2018     }
2019
2020     return 0;
2021 }
2022
2023 #endif