minibidi.c

putty

/************************************************************************
 * $Id: minibidi.c 6910 2006-11-18 15:10:48Z simon $
 *
 * ------------
 * Description:
 * ------------
 * This is an implemention of Unicode's Bidirectional Algorithm
 * (known as UAX #9).
 *
 *   http://www.unicode.org/reports/tr9/
 *
 * Author: Ahmad Khalifa
 *
 * -----------------
 * Revision Details:    (Updated by Revision Control System)
 * -----------------
 *  $Date: 2006-11-18 15:10:48 +0000 (Sat, 18 Nov 2006) $
 *  $Author: simon $
 *  $Revision: 6910 $
 *
 * (www.arabeyes.org - under MIT license)
 *
 ************************************************************************/

/*
 * TODO:
 * =====
 * - Explicit marks need to be handled (they are not 100% now)
 * - Ligatures
 */

#include <stdlib.h>	/* definition of wchar_t*/

#include "misc.h"

#define LMASK	0x3F	/* Embedding Level mask */
#define OMASK	0xC0	/* Override mask */
#define OISL	0x80	/* Override is L */
#define OISR	0x40	/* Override is R */

/* For standalone compilation in a testing mode.
 * Still depends on the PuTTY headers for snewn and sfree, but can avoid
 * _linking_ with any other PuTTY code. */
#ifdef TEST_GETTYPE
#define safemalloc malloc
#define safefree free
#endif

/* Shaping Helpers */
#define STYPE(xh) ((((xh) >= SHAPE_FIRST) && ((xh) <= SHAPE_LAST)) ? \
shapetypes[(xh)-SHAPE_FIRST].type : SU) /*))*/
#define SISOLATED(xh) (shapetypes[(xh)-SHAPE_FIRST].form_b)
#define SFINAL(xh) ((xh)+1)
#define SINITIAL(xh) ((xh)+2)
#define SMEDIAL(ch) ((ch)+3)

#define leastGreaterOdd(x) ( ((x)+1) | 1 )
#define leastGreaterEven(x) ( ((x)+2) &~ 1 )

typedef struct bidi_char {
    wchar_t origwc, wc;
    unsigned short index;
} bidi_char;

/* function declarations */
void flipThisRun(bidi_char *from, unsigned char* level, int max, int count);
int findIndexOfRun(unsigned char* level , int start, int count, int tlevel);
unsigned char getType(int ch);
unsigned char setOverrideBits(unsigned char level, unsigned char override);
int getPreviousLevel(unsigned char* level, int from);
int do_shape(bidi_char *line, bidi_char *to, int count);
int do_bidi(bidi_char *line, int count);
void doMirror(wchar_t* ch);

/* character types */
enum {
    L,
    LRE,
    LRO,
    R,
    AL,
    RLE,
    RLO,
    PDF,
    EN,
    ES,
    ET,
    AN,
    CS,
    NSM,
    BN,
    B,
    S,
    WS,
    ON
};

/* Shaping Types */
enum {
    SL, /* Left-Joining, doesnt exist in U+0600 - U+06FF */
    SR, /* Right-Joining, ie has Isolated, Final */
    SD, /* Dual-Joining, ie has Isolated, Final, Initial, Medial */
    SU, /* Non-Joining */
    SC  /* Join-Causing, like U+0640 (TATWEEL) */
};

typedef struct {
    char type;
    wchar_t form_b;
} shape_node;

/* Kept near the actual table, for verification. */
#define SHAPE_FIRST 0x621
#define SHAPE_LAST 0x64A

const shape_node shapetypes[] = {
    /* index, Typ, Iso, Ligature Index*/
    /* 621 */ {SU, 0xFE80},
    /* 622 */ {SR, 0xFE81},
    /* 623 */ {SR, 0xFE83},
    /* 624 */ {SR, 0xFE85},
    /* 625 */ {SR, 0xFE87},
    /* 626 */ {SD, 0xFE89},
    /* 627 */ {SR, 0xFE8D},
    /* 628 */ {SD, 0xFE8F},
    /* 629 */ {SR, 0xFE93},
    /* 62A */ {SD, 0xFE95},
    /* 62B */ {SD, 0xFE99},
    /* 62C */ {SD, 0xFE9D},
    /* 62D */ {SD, 0xFEA1},
    /* 62E */ {SD, 0xFEA5},
    /* 62F */ {SR, 0xFEA9},
    /* 630 */ {SR, 0xFEAB},
    /* 631 */ {SR, 0xFEAD},
    /* 632 */ {SR, 0xFEAF},
    /* 633 */ {SD, 0xFEB1},
    /* 634 */ {SD, 0xFEB5},
    /* 635 */ {SD, 0xFEB9},
    /* 636 */ {SD, 0xFEBD},
    /* 637 */ {SD, 0xFEC1},
    /* 638 */ {SD, 0xFEC5},
    /* 639 */ {SD, 0xFEC9},
    /* 63A */ {SD, 0xFECD},
    /* 63B */ {SU, 0x0},
    /* 63C */ {SU, 0x0},
    /* 63D */ {SU, 0x0},
    /* 63E */ {SU, 0x0},
    /* 63F */ {SU, 0x0},
    /* 640 */ {SC, 0x0},
    /* 641 */ {SD, 0xFED1},
    /* 642 */ {SD, 0xFED5},
    /* 643 */ {SD, 0xFED9},
    /* 644 */ {SD, 0xFEDD},
    /* 645 */ {SD, 0xFEE1},
    /* 646 */ {SD, 0xFEE5},
    /* 647 */ {SD, 0xFEE9},
    /* 648 */ {SR, 0xFEED},
    /* 649 */ {SR, 0xFEEF}, /* SD */
    /* 64A */ {SD, 0xFEF1}
};

/*
 * Flips the text buffer, according to max level, and
 * all higher levels
 *
 * Input:
 * from: text buffer, on which to apply flipping
 * level: resolved levels buffer
 * max: the maximum level found in this line (should be unsigned char)
 * count: line size in bidi_char
 */
void flipThisRun(bidi_char *from, unsigned char *level, int max, int count)
{
    int i, j, k, tlevel;
    bidi_char temp;

    j = i = 0;
    while (i<count && j<count) {

	/* find the start of the run of level=max */
	tlevel = max;
	i = j = findIndexOfRun(level, i, count, max);
	/* find the end of the run */
	while (i<count && tlevel <= level[i]) {
	    i++;
	}
	for (k = i - 1; k > j; k--, j++) {
	    temp = from[k];
	    from[k] = from[j];
	    from[j] = temp;
	}
    }
}

/*
 * Finds the index of a run with level equals tlevel
 */
int findIndexOfRun(unsigned char* level , int start, int count, int tlevel)
{
    int i;
    for (i=start; i<count; i++) {
	if (tlevel == level[i]) {
	    return i;
	}
    }
    return count;
}

/*
 * Returns the bidi character type of ch.
 *
 * The data table in this function is constructed from the Unicode
 * Character Database, downloadable from unicode.org at the URL
 * 
 *     http://www.unicode.org/Public/UNIDATA/UnicodeData.txt
 * 
 * by the following fragment of Perl:

perl -ne 'split ";"; $num = hex $_[0]; $type = $_[4];' \
      -e '$fl = ($_[1] =~ /First/ ? 1 : $_[1] =~ /Last/ ? 2 : 0);' \
      -e 'if ($type eq $runtype and ($runend == $num-1 or ' \
      -e '    ($fl==2 and $pfl==1))) {$runend = $num;} else { &reset; }' \
      -e '$pfl=$fl; END { &reset }; sub reset {' \
      -e 'printf"        {0x%04x, 0x%04x, %s},\n",$runstart,$runend,$runtype' \
      -e '  if defined $runstart and $runtype ne "ON";' \
      -e '$runstart=$runend=$num; $runtype=$type;}' \
    UnicodeData.txt

 */
unsigned char getType(int ch)
{
    static const struct {
	int first, last, type;
    } lookup[] = {
        {0x0000, 0x0008, BN},
        {0x0009, 0x0009, S},
        {0x000a, 0x000a, B},
        {0x000b, 0x000b, S},
        {0x000c, 0x000c, WS},
        {0x000d, 0x000d, B},
        {0x000e, 0x001b, BN},
        {0x001c, 0x001e, B},
        {0x001f, 0x001f, S},
        {0x0020, 0x0020, WS},
        {0x0023, 0x0025, ET},
        {0x002b, 0x002b, ES},
        {0x002c, 0x002c, CS},
        {0x002d, 0x002d, ES},
        {0x002e, 0x002f, CS},
        {0x0030, 0x0039, EN},
        {0x003a, 0x003a, CS},
        {0x0041, 0x005a, L},
        {0x0061, 0x007a, L},
        {0x007f, 0x0084, BN},
        {0x0085, 0x0085, B},
        {0x0086, 0x009f, BN},
        {0x00a0, 0x00a0, CS},
        {0x00a2, 0x00a5, ET},
        {0x00aa, 0x00aa, L},
        {0x00ad, 0x00ad, BN},
        {0x00b0, 0x00b1, ET},
        {0x00b2, 0x00b3, EN},
        {0x00b5, 0x00b5, L},
        {0x00b9, 0x00b9, EN},
        {0x00ba, 0x00ba, L},
        {0x00c0, 0x00d6, L},
        {0x00d8, 0x00f6, L},
        {0x00f8, 0x0236, L},
        {0x0250, 0x02b8, L},
        {0x02bb, 0x02c1, L},
        {0x02d0, 0x02d1, L},
        {0x02e0, 0x02e4, L},
        {0x02ee, 0x02ee, L},
        {0x0300, 0x0357, NSM},
        {0x035d, 0x036f, NSM},
        {0x037a, 0x037a, L},
        {0x0386, 0x0386, L},
        {0x0388, 0x038a, L},
        {0x038c, 0x038c, L},
        {0x038e, 0x03a1, L},
        {0x03a3, 0x03ce, L},
        {0x03d0, 0x03f5, L},
        {0x03f7, 0x03fb, L},
        {0x0400, 0x0482, L},
        {0x0483, 0x0486, NSM},
        {0x0488, 0x0489, NSM},
        {0x048a, 0x04ce, L},
        {0x04d0, 0x04f5, L},
        {0x04f8, 0x04f9, L},
        {0x0500, 0x050f, L},
        {0x0531, 0x0556, L},
        {0x0559, 0x055f, L},
        {0x0561, 0x0587, L},
        {0x0589, 0x0589, L},
        {0x0591, 0x05a1, NSM},
        {0x05a3, 0x05b9, NSM},
        {0x05bb, 0x05bd, NSM},
        {0x05be, 0x05be, R},
        {0x05bf, 0x05bf, NSM},
        {0x05c0, 0x05c0, R},
        {0x05c1, 0x05c2, NSM},
        {0x05c3, 0x05c3, R},
        {0x05c4, 0x05c4, NSM},
        {0x05d0, 0x05ea, R},
        {0x05f0, 0x05f4, R},
        {0x0600, 0x0603, AL},
        {0x060c, 0x060c, CS},
        {0x060d, 0x060d, AL},
        {0x0610, 0x0615, NSM},
        {0x061b, 0x061b, AL},
        {0x061f, 0x061f, AL},
        {0x0621, 0x063a, AL},
        {0x0640, 0x064a, AL},
        {0x064b, 0x0658, NSM},
        {0x0660, 0x0669, AN},
        {0x066a, 0x066a, ET},
        {0x066b, 0x066c, AN},
        {0x066d, 0x066f, AL},
        {0x0670, 0x0670, NSM},
        {0x0671, 0x06d5, AL},
        {0x06d6, 0x06dc, NSM},
        {0x06dd, 0x06dd, AL},
        {0x06de, 0x06e4, NSM},
        {0x06e5, 0x06e6, AL},
        {0x06e7, 0x06e8, NSM},
        {0x06ea, 0x06ed, NSM},
        {0x06ee, 0x06ef, AL},
        {0x06f0, 0x06f9, EN},
        {0x06fa, 0x070d, AL},
        {0x070f, 0x070f, BN},
        {0x0710, 0x0710, AL},
        {0x0711, 0x0711, NSM},
        {0x0712, 0x072f, AL},
        {0x0730, 0x074a, NSM},
        {0x074d, 0x074f, AL},
        {0x0780, 0x07a5, AL},
        {0x07a6, 0x07b0, NSM},
        {0x07b1, 0x07b1, AL},
        {0x0901, 0x0902, NSM},
        {0x0903, 0x0939, L},
        {0x093c, 0x093c, NSM},
        {0x093d, 0x0940, L},
        {0x0941, 0x0948, NSM},
        {0x0949, 0x094c, L},
        {0x094d, 0x094d, NSM},
        {0x0950, 0x0950, L},
        {0x0951, 0x0954, NSM},
        {0x0958, 0x0961, L},
        {0x0962, 0x0963, NSM},
        {0x0964, 0x0970, L},
        {0x0981, 0x0981, NSM},
        {0x0982, 0x0983, L},
        {0x0985, 0x098c, L},
        {0x098f, 0x0990, L},
        {0x0993, 0x09a8, L},
        {0x09aa, 0x09b0, L},
        {0x09b2, 0x09b2, L},
        {0x09b6, 0x09b9, L},
        {0x09bc, 0x09bc, NSM},
        {0x09bd, 0x09c0, L},
        {0x09c1, 0x09c4, NSM},
        {0x09c7, 0x09c8, L},
        {0x09cb, 0x09cc, L},
        {0x09cd, 0x09cd, NSM},
        {0x09d7, 0x09d7, L},
        {0x09dc, 0x09dd, L},
        {0x09df, 0x09e1, L},
        {0x09e2, 0x09e3, NSM},
        {0x09e6, 0x09f1, L},
        {0x09f2, 0x09f3, ET},
        {0x09f4, 0x09fa, L},
        {0x0a01, 0x0a02, NSM},
        {0x0a03, 0x0a03, L},
        {0x0a05, 0x0a0a, L},
        {0x0a0f, 0x0a10, L},
        {0x0a13, 0x0a28, L},
        {0x0a2a, 0x0a30, L},
        {0x0a32, 0x0a33, L},
        {0x0a35, 0x0a36, L},
        {0x0a38, 0x0a39, L},
        {0x0a3c, 0x0a3c, NSM},
        {0x0a3e, 0x0a40, L},
        {0x0a41, 0x0a42, NSM},
        {0x0a47, 0x0a48, NSM},
        {0x0a4b, 0x0a4d, NSM},
        {0x0a59, 0x0a5c, L},
        {0x0a5e, 0x0a5e, L},
        {0x0a66, 0x0a6f, L},
        {0x0a70, 0x0a71, NSM},
        {0x0a72, 0x0a74, L},
        {0x0a81, 0x0a82, NSM},
        {0x0a83, 0x0a83, L},
        {0x0a85, 0x0a8d, L},
        {0x0a8f, 0x0a91, L},
        {0x0a93, 0x0aa8, L},
        {0x0aaa, 0x0ab0, L},
        {0x0ab2, 0x0ab3, L},
        {0x0ab5, 0x0ab9, L},
        {0x0abc, 0x0abc, NSM},
        {0x0abd, 0x0ac0, L},
        {0x0ac1, 0x0ac5, NSM},
        {0x0ac7, 0x0ac8, NSM},
        {0x0ac9, 0x0ac9, L},
        {0x0acb, 0x0acc, L},
        {0x0acd, 0x0acd, NSM},
        {0x0ad0, 0x0ad0, L},
        {0x0ae0, 0x0ae1, L},
        {0x0ae2, 0x0ae3, NSM},
        {0x0ae6, 0x0aef, L},
        {0x0af1, 0x0af1, ET},
        {0x0b01, 0x0b01, NSM},
        {0x0b02, 0x0b03, L},
        {0x0b05, 0x0b0c, L},
        {0x0b0f, 0x0b10, L},
        {0x0b13, 0x0b28, L},
        {0x0b2a, 0x0b30, L},
        {0x0b32, 0x0b33, L},
        {0x0b35, 0x0b39, L},
        {0x0b3c, 0x0b3c, NSM},
        {0x0b3d, 0x0b3e, L},
        {0x0b3f, 0x0b3f, NSM},
        {0x0b40, 0x0b40, L},
        {0x0b41, 0x0b43, NSM},
        {0x0b47, 0x0b48, L},
        {0x0b4b, 0x0b4c, L},
        {0x0b4d, 0x0b4d, NSM},
        {0x0b56, 0x0b56, NSM},
        {0x0b57, 0x0b57, L},
        {0x0b5c, 0x0b5d, L},
        {0x0b5f, 0x0b61, L},
        {0x0b66, 0x0b71, L},
        {0x0b82, 0x0b82, NSM},
        {0x0b83, 0x0b83, L},
        {0x0b85, 0x0b8a, L},
        {0x0b8e, 0x0b90, L},
        {0x0b92, 0x0b95, L},
        {0x0b99, 0x0b9a, L},
        {0x0b9c, 0x0b9c, L},
        {0x0b9e, 0x0b9f, L},
        {0x0ba3, 0x0ba4, L},
        {0x0ba8, 0x0baa, L},
        {0x0bae, 0x0bb5, L},
        {0x0bb7, 0x0bb9, L},
        {0x0bbe, 0x0bbf, L},
        {0x0bc0, 0x0bc0, NSM},
        {0x0bc1, 0x0bc2, L},
        {0x0bc6, 0x0bc8, L},
        {0x0bca, 0x0bcc, L},
        {0x0bcd, 0x0bcd, NSM},
        {0x0bd7, 0x0bd7, L},
        {0x0be7, 0x0bf2, L},
        {0x0bf9, 0x0bf9, ET},
        {0x0c01, 0x0c03, L},
        {0x0c05, 0x0c0c, L},
        {0x0c0e, 0x0c10, L},
        {0x0c12, 0x0c28, L},
        {0x0c2a, 0x0c33, L},
        {0x0c35, 0x0c39, L},
        {0x0c3e, 0x0c40, NSM},
        {0x0c41, 0x0c44, L},
        {0x0c46, 0x0c48, NSM},
        {0x0c4a, 0x0c4d, NSM},
        {0x0c55, 0x0c56, NSM},
        {0x0c60, 0x0c61, L},
        {0x0c66, 0x0c6f, L},
        {0x0c82, 0x0c83, L},
        {0x0c85, 0x0c8c, L},
        {0x0c8e, 0x0c90, L},
        {0x0c92, 0x0ca8, L},
        {0x0caa, 0x0cb3, L},
        {0x0cb5, 0x0cb9, L},
        {0x0cbc, 0x0cbc, NSM},
        {0x0cbd, 0x0cc4, L},
        {0x0cc6, 0x0cc8, L},
        {0x0cca, 0x0ccb, L},