dlls/usp10/shape.c

   1 /*
   2  * Implementation of Shaping for the Uniscribe Script Processor (usp10.dll)
   3  *
   4  * Copyright 2010 CodeWeavers, Aric Stewart
   5  *
   6  * This library is free software; you can redistribute it and/or
   7  * modify it under the terms of the GNU Lesser General Public
   8  * License as published by the Free Software Foundation; either
   9  * version 2.1 of the License, or (at your option) any later version.
  10  *
  11  * This library is distributed in the hope that it will be useful,
  12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14  * Lesser General Public License for more details.
  15  *
  16  * You should have received a copy of the GNU Lesser General Public
  17  * License along with this library; if not, write to the Free Software
  18  * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA
  19  *
  20  */
  21 #include <stdarg.h>
  22
  23 #include "windef.h"
  24 #include "winbase.h"
  25 #include "wingdi.h"
  26 #include "winuser.h"
  27 #include "winnls.h"
  28 #include "usp10.h"
  29 #include "winternl.h"
  30
  31 #include "usp10_internal.h"
  32
  33 #include "wine/debug.h"
  34
  35 WINE_DEFAULT_DEBUG_CHANNEL(uniscribe);
  36
  37 #define FIRST_ARABIC_CHAR 0x0600
  38 #define LAST_ARABIC_CHAR  0x06ff
  39
  40 typedef VOID (*ContextualShapingProc)(HDC, ScriptCache*, SCRIPT_ANALYSIS*,
  41                                       WCHAR*, INT, WORD*, INT*, INT);
  42
  43 static void ContextualShape_Arabic(HDC hdc, ScriptCache *psc, SCRIPT_ANALYSIS *psa, WCHAR* pwcChars, INT cChars, WORD* pwOutGlyphs, INT* pcGlyphs, INT cMaxGlyphs);
  44
  45 extern const unsigned short wine_shaping_table[];
  46 extern const unsigned short wine_shaping_forms[LAST_ARABIC_CHAR - FIRST_ARABIC_CHAR + 1][4];
  47
  48 enum joining_types {
  49     jtU,
  50     jtT,
  51     jtR,
  52     jtL,
  53     jtD,
  54     jtC
  55 };
  56
  57 enum joined_forms {
  58     Xn=0,
  59     Xr,
  60     Xl,
  61     Xm
  62 };
  63
  64 #ifdef WORDS_BIGENDIAN
  65 #define GET_BE_WORD(x) (x)
  66 #else
  67 #define GET_BE_WORD(x) RtlUshortByteSwap(x)
  68 #endif
  69
  70 /* These are all structures needed for the GSUB table */
  71 #define MS_MAKE_TAG( _x1, _x2, _x3, _x4 ) \
  72           ( ( (ULONG)_x4 << 24 ) |     \
  73             ( (ULONG)_x3 << 16 ) |     \
  74             ( (ULONG)_x2 <<  8 ) |     \
  75               (ULONG)_x1         )
  76
  77 #define GSUB_TAG MS_MAKE_TAG('G', 'S', 'U', 'B')
  78 #define GSUB_E_NOFEATURE -2
  79 #define GSUB_E_NOGLYPH -1
  80
  81 typedef struct {
  82     DWORD version;
  83     WORD ScriptList;
  84     WORD FeatureList;
  85     WORD LookupList;
  86 } GSUB_Header;
  87
  88 typedef struct {
  89     CHAR ScriptTag[4];
  90     WORD Script;
  91 } GSUB_ScriptRecord;
  92
  93 typedef struct {
  94     WORD ScriptCount;
  95     GSUB_ScriptRecord ScriptRecord[1];
  96 } GSUB_ScriptList;
  97
  98 typedef struct {
  99     CHAR LangSysTag[4];
 100     WORD LangSys;
 101 } GSUB_LangSysRecord;
 102
 103 typedef struct {
 104     WORD DefaultLangSys;
 105     WORD LangSysCount;
 106     GSUB_LangSysRecord LangSysRecord[1];
 107 } GSUB_Script;
 108
 109 typedef struct {
 110     WORD LookupOrder; /* Reserved */
 111     WORD ReqFeatureIndex;
 112     WORD FeatureCount;
 113     WORD FeatureIndex[1];
 114 } GSUB_LangSys;
 115
 116 typedef struct {
 117     CHAR FeatureTag[4];
 118     WORD Feature;
 119 } GSUB_FeatureRecord;
 120
 121 typedef struct {
 122     WORD FeatureCount;
 123     GSUB_FeatureRecord FeatureRecord[1];
 124 } GSUB_FeatureList;
 125
 126 typedef struct {
 127     WORD FeatureParams; /* Reserved */
 128     WORD LookupCount;
 129     WORD LookupListIndex[1];
 130 } GSUB_Feature;
 131
 132 typedef struct {
 133     WORD LookupCount;
 134     WORD Lookup[1];
 135 } GSUB_LookupList;
 136
 137 typedef struct {
 138     WORD LookupType;
 139     WORD LookupFlag;
 140     WORD SubTableCount;
 141     WORD SubTable[1];
 142 } GSUB_LookupTable;
 143
 144 typedef struct {
 145     WORD CoverageFormat;
 146     WORD GlyphCount;
 147     WORD GlyphArray[1];
 148 } GSUB_CoverageFormat1;
 149
 150 typedef struct {
 151     WORD Start;
 152     WORD End;
 153     WORD StartCoverageIndex;
 154 } GSUB_RangeRecord;
 155
 156 typedef struct {
 157     WORD CoverageFormat;
 158     WORD RangeCount;
 159     GSUB_RangeRecord RangeRecord[1];
 160 } GSUB_CoverageFormat2;
 161
 162 typedef struct {
 163     WORD SubstFormat; /* = 1 */
 164     WORD Coverage;
 165     WORD DeltaGlyphID;
 166 } GSUB_SingleSubstFormat1;
 167
 168 typedef struct {
 169     WORD SubstFormat; /* = 2 */
 170     WORD Coverage;
 171     WORD GlyphCount;
 172     WORD Substitute[1];
 173 }GSUB_SingleSubstFormat2;
 174
 175 typedef struct {
 176     WORD SubstFormat; /* = 1 */
 177     WORD Coverage;
 178     WORD LigSetCount;
 179     WORD LigatureSet[1];
 180 }GSUB_LigatureSubstFormat1;
 181
 182 typedef struct {
 183     WORD LigatureCount;
 184     WORD Ligature[1];
 185 }GSUB_LigatureSet;
 186
 187 typedef struct{
 188     WORD LigGlyph;
 189     WORD CompCount;
 190     WORD Component[1];
 191 }GSUB_Ligature;
 192
 193 typedef struct{
 194     WORD SequenceIndex;
 195     WORD LookupListIndex;
 196
 197 }GSUB_SubstLookupRecord;
 198
 199 typedef struct{
 200     WORD SubstFormat; /* = 1 */
 201     WORD Coverage;
 202     WORD ChainSubRuleSetCount;
 203     WORD ChainSubRuleSet[1];
 204 }GSUB_ChainContextSubstFormat1;
 205
 206 typedef struct {
 207     WORD SubstFormat; /* = 3 */
 208     WORD BacktrackGlyphCount;
 209     WORD Coverage[1];
 210 }GSUB_ChainContextSubstFormat3_1;
 211
 212 typedef struct{
 213     WORD InputGlyphCount;
 214     WORD Coverage[1];
 215 }GSUB_ChainContextSubstFormat3_2;
 216
 217 typedef struct{
 218     WORD LookaheadGlyphCount;
 219     WORD Coverage[1];
 220 }GSUB_ChainContextSubstFormat3_3;
 221
 222 typedef struct{
 223     WORD SubstCount;
 224     GSUB_SubstLookupRecord SubstLookupRecord[1];
 225 }GSUB_ChainContextSubstFormat3_4;
 226
 227 typedef struct {
 228     WORD SubstFormat; /* = 1 */
 229     WORD Coverage;
 230     WORD AlternateSetCount;
 231     WORD AlternateSet[1];
 232 } GSUB_AlternateSubstFormat1;
 233
 234 typedef struct{
 235     WORD GlyphCount;
 236     WORD Alternate[1];
 237 } GSUB_AlternateSet;
 238
 239 static INT GSUB_apply_lookup(const GSUB_LookupList* lookup, INT lookup_index, WORD *glyphs, INT glyph_index, INT write_dir, INT *glyph_count);
 240
 241 /* the orders of joined_forms and contextual_features need to line up */
 242 static const char* contextual_features[] =
 243 {
 244     "isol",
 245     "fina",
 246     "init",
 247     "medi"
 248 };
 249
 250 static OPENTYPE_FEATURE_RECORD standard_features[] =
 251 {
 252     { 0x6167696c /*liga*/, 1},
 253     { 0x67696c63 /*clig*/, 1},
 254 };
 255
 256 static OPENTYPE_FEATURE_RECORD arabic_features[] =
 257 {
 258     { 0x67696c72 /*rlig*/, 1},
 259     { 0x746c6163 /*calt*/, 1},
 260     { 0x6167696c /*liga*/, 1},
 261     { 0x67696c64 /*dlig*/, 1},
 262     { 0x68777363 /*cswh*/, 1},
 263     { 0x7465736d /*mset*/, 1},
 264 };
 265
 266 static OPENTYPE_FEATURE_RECORD hebrew_features[] =
 267 {
 268     { 0x67696c64 /*dlig*/, 1},
 269 };
 270
 271 static OPENTYPE_FEATURE_RECORD syriac_features[] =
 272 {
 273     { 0x67696c72 /*rlig*/, 1},
 274     { 0x746c6163 /*calt*/, 1},
 275     { 0x6167696c /*liga*/, 1},
 276     { 0x67696c64 /*dlig*/, 1},
 277 };
 278
 279 typedef struct ScriptShapeDataTag {
 280     TEXTRANGE_PROPERTIES  defaultTextRange;
 281     CHAR                  otTag[5];
 282     ContextualShapingProc contextProc;
 283 } ScriptShapeData;
 284
 285 /* in order of scripts */
 286 static const ScriptShapeData ShapingData[] =
 287 {
 288     {{ standard_features, 2}, "", NULL},
 289     {{ standard_features, 2}, "latn", NULL},
 290     {{ standard_features, 2}, "latn", NULL},
 291     {{ standard_features, 2}, "latn", NULL},
 292     {{ standard_features, 2}, "" , NULL},
 293     {{ standard_features, 2}, "latn", NULL},
 294     {{ arabic_features, 6}, "arab", ContextualShape_Arabic},
 295     {{ arabic_features, 6}, "arab", ContextualShape_Arabic},
 296     {{ hebrew_features, 1}, "hebr", NULL},
 297     {{ syriac_features, 4}, "syrc", NULL},
 298     {{ arabic_features, 6}, "arab", ContextualShape_Arabic},
 299 };
 300
 301 static INT GSUB_is_glyph_covered(LPCVOID table , UINT glyph)
 302 {
 303     const GSUB_CoverageFormat1* cf1;
 304
 305     cf1 = table;
 306
 307     if (GET_BE_WORD(cf1->CoverageFormat) == 1)
 308     {
 309         int count = GET_BE_WORD(cf1->GlyphCount);
 310         int i;
 311         TRACE("Coverage Format 1, %i glyphs\n",count);
 312         for (i = 0; i < count; i++)
 313             if (glyph == GET_BE_WORD(cf1->GlyphArray[i]))
 314                 return i;
 315         return -1;
 316     }
 317     else if (GET_BE_WORD(cf1->CoverageFormat) == 2)
 318     {
 319         const GSUB_CoverageFormat2* cf2;
 320         int i;
 321         int count;
 322         cf2 = (const GSUB_CoverageFormat2*)cf1;
 323
 324         count = GET_BE_WORD(cf2->RangeCount);
 325         TRACE("Coverage Format 2, %i ranges\n",count);
 326         for (i = 0; i < count; i++)
 327         {
 328             if (glyph < GET_BE_WORD(cf2->RangeRecord[i].Start))
 329                 return -1;
 330             if ((glyph >= GET_BE_WORD(cf2->RangeRecord[i].Start)) &&
 331                 (glyph <= GET_BE_WORD(cf2->RangeRecord[i].End)))
 332             {
 333                 return (GET_BE_WORD(cf2->RangeRecord[i].StartCoverageIndex) +
 334                     glyph - GET_BE_WORD(cf2->RangeRecord[i].Start));
 335             }
 336         }
 337         return -1;
 338     }
 339     else
 340         ERR("Unknown CoverageFormat %i\n",GET_BE_WORD(cf1->CoverageFormat));
 341
 342     return -1;
 343 }
 344
 345 static const GSUB_Script* GSUB_get_script_table( const GSUB_Header* header, const char* tag)
 346 {
 347     const GSUB_ScriptList *script;
 348     const GSUB_Script *deflt = NULL;
 349     int i;
 350     script = (const GSUB_ScriptList*)((const BYTE*)header + GET_BE_WORD(header->ScriptList));
 351
 352     TRACE("%i scripts in this font\n",GET_BE_WORD(script->ScriptCount));
 353     for (i = 0; i < GET_BE_WORD(script->ScriptCount); i++)
 354     {
 355         const GSUB_Script *scr;
 356         int offset;
 357
 358         offset = GET_BE_WORD(script->ScriptRecord[i].Script);
 359         scr = (const GSUB_Script*)((const BYTE*)script + offset);
 360
 361         if (strncmp(script->ScriptRecord[i].ScriptTag, tag,4)==0)
 362             return scr;
 363         if (strncmp(script->ScriptRecord[i].ScriptTag, "dflt",4)==0)
 364             deflt = scr;
 365     }
 366     return deflt;
 367 }
 368
 369 static const GSUB_LangSys* GSUB_get_lang_table( const GSUB_Script* script, const char* tag)
 370 {
 371     int i;
 372     int offset;
 373     const GSUB_LangSys *Lang;
 374
 375     TRACE("Deflang %x, LangCount %i\n",GET_BE_WORD(script->DefaultLangSys), GET_BE_WORD(script->LangSysCount));
 376
 377     for (i = 0; i < GET_BE_WORD(script->LangSysCount) ; i++)
 378     {
 379         offset = GET_BE_WORD(script->LangSysRecord[i].LangSys);
 380         Lang = (const GSUB_LangSys*)((const BYTE*)script + offset);
 381
 382         if ( strncmp(script->LangSysRecord[i].LangSysTag,tag,4)==0)
 383             return Lang;
 384     }
 385     offset = GET_BE_WORD(script->DefaultLangSys);
 386     if (offset)
 387     {
 388         Lang = (const GSUB_LangSys*)((const BYTE*)script + offset);
 389         return Lang;
 390     }
 391     return NULL;
 392 }
 393
 394 static const GSUB_Feature * GSUB_get_feature(const GSUB_Header *header, const GSUB_LangSys *lang, const char* tag)
 395 {
 396     int i;
 397     const GSUB_FeatureList *feature;
 398     feature = (const GSUB_FeatureList*)((const BYTE*)header + GET_BE_WORD(header->FeatureList));
 399
 400     TRACE("%i features\n",GET_BE_WORD(lang->FeatureCount));
 401     for (i = 0; i < GET_BE_WORD(lang->FeatureCount); i++)
 402     {
 403         int index = GET_BE_WORD(lang->FeatureIndex[i]);
 404         if (strncmp(feature->FeatureRecord[index].FeatureTag,tag,4)==0)
 405         {
 406             const GSUB_Feature *feat;
 407             feat = (const GSUB_Feature*)((const BYTE*)feature + GET_BE_WORD(feature->FeatureRecord[index].Feature));
 408             return feat;
 409         }
 410     }
 411     return NULL;
 412 }
 413
 414 static INT GSUB_apply_SingleSubst(const GSUB_LookupTable *look, WORD *glyphs, INT glyph_index, INT write_dir, INT *glyph_count)
 415 {
 416     int j;
 417     TRACE("Single Substitution Subtable\n");
 418
 419     for (j = 0; j < GET_BE_WORD(look->SubTableCount); j++)
 420     {
 421         int offset;
 422         const GSUB_SingleSubstFormat1 *ssf1;
 423         offset = GET_BE_WORD(look->SubTable[j]);
 424         ssf1 = (const GSUB_SingleSubstFormat1*)((const BYTE*)look+offset);
 425         if (GET_BE_WORD(ssf1->SubstFormat) == 1)
 426         {
 427             int offset = GET_BE_WORD(ssf1->Coverage);
 428             TRACE("  subtype 1, delta %i\n", GET_BE_WORD(ssf1->DeltaGlyphID));
 429             if (GSUB_is_glyph_covered((const BYTE*)ssf1+offset, glyphs[glyph_index]) != -1)
 430             {
 431                 TRACE("  Glyph 0x%x ->",glyphs[glyph_index]);
 432                 glyphs[glyph_index] = glyphs[glyph_index] + GET_BE_WORD(ssf1->DeltaGlyphID);
 433                 TRACE(" 0x%x\n",glyphs[glyph_index]);
 434                 return glyph_index + 1;
 435             }
 436         }
 437         else
 438         {
 439             const GSUB_SingleSubstFormat2 *ssf2;
 440             INT index;
 441             INT offset;
 442
 443             ssf2 = (const GSUB_SingleSubstFormat2 *)ssf1;
 444             offset = GET_BE_WORD(ssf1->Coverage);
 445             TRACE("  subtype 2,  glyph count %i\n", GET_BE_WORD(ssf2->GlyphCount));
 446             index = GSUB_is_glyph_covered((const BYTE*)ssf2+offset, glyphs[glyph_index]);
 447             TRACE("  Coverage index %i\n",index);
 448             if (index != -1)
 449             {
 450                 TRACE("    Glyph is 0x%x ->",glyphs[glyph_index]);
 451                 glyphs[glyph_index] = GET_BE_WORD(ssf2->Substitute[index]);
 452                 TRACE("0x%x\n",glyphs[glyph_index]);
 453                 return glyph_index + 1;
 454             }
 455         }
 456     }
 457     return GSUB_E_NOGLYPH;
 458 }
 459
 460 static INT GSUB_apply_AlternateSubst(const GSUB_LookupTable *look, WORD *glyphs, INT glyph_index, INT write_dir, INT *glyph_count)
 461 {
 462     int j;
 463     TRACE("Alternate Substitution Subtable\n");
 464
 465     for (j = 0; j < GET_BE_WORD(look->SubTableCount); j++)
 466     {
 467         int offset;
 468         const GSUB_AlternateSubstFormat1 *asf1;
 469         INT index;
 470
 471         offset = GET_BE_WORD(look->SubTable[j]);
 472         asf1 = (const GSUB_AlternateSubstFormat1*)((const BYTE*)look+offset);
 473         offset = GET_BE_WORD(asf1->Coverage);
 474
 475         index = GSUB_is_glyph_covered((const BYTE*)asf1+offset, glyphs[glyph_index]);
 476         if (index != -1)
 477         {
 478             const GSUB_AlternateSet *as;
 479             offset =  GET_BE_WORD(asf1->AlternateSet[index]);
 480             as = (const GSUB_AlternateSet*)((const BYTE*)asf1+offset);
 481             FIXME("%i alternates, picking index 0\n",GET_BE_WORD(as->GlyphCount));
 482
 483             TRACE("  Glyph 0x%x ->",glyphs[glyph_index]);
 484             glyphs[glyph_index] = GET_BE_WORD(as->Alternate[0]);
 485             TRACE(" 0x%x\n",glyphs[glyph_index]);
 486             return glyph_index + 1;
 487         }
 488     }
 489     return GSUB_E_NOGLYPH;
 490 }
 491
 492 static INT GSUB_apply_LigatureSubst(const GSUB_LookupTable *look, WORD *glyphs, INT glyph_index, INT write_dir, INT *glyph_count)
 493 {
 494     int j;
 495
 496     TRACE("Ligature Substitution Subtable\n");
 497     for (j = 0; j < GET_BE_WORD(look->SubTableCount); j++)
 498     {
 499         const GSUB_LigatureSubstFormat1 *lsf1;
 500         int offset,index;
 501
 502         offset = GET_BE_WORD(look->SubTable[j]);
 503         lsf1 = (const GSUB_LigatureSubstFormat1*)((const BYTE*)look+offset);
 504         offset = GET_BE_WORD(lsf1->Coverage);
 505         index = GSUB_is_glyph_covered((const BYTE*)lsf1+offset, glyphs[glyph_index]);
 506         TRACE("  Coverage index %i\n",index);
 507         if (index != -1)
 508         {
 509             const GSUB_LigatureSet *ls;
 510             int k, count;
 511
 512             offset = GET_BE_WORD(lsf1->LigatureSet[index]);
 513             ls = (const GSUB_LigatureSet*)((const BYTE*)lsf1+offset);
 514             count = GET_BE_WORD(ls->LigatureCount);
 515             TRACE("  LigatureSet has %i members\n",count);
 516             for (k = 0; k < count; k++)
 517             {
 518                 const GSUB_Ligature *lig;
 519                 int CompCount,l,CompIndex;
 520
 521                 offset = GET_BE_WORD(ls->Ligature[k]);
 522                 lig = (const GSUB_Ligature*)((const BYTE*)ls+offset);
 523                 CompCount = GET_BE_WORD(lig->CompCount) - 1;
 524                 CompIndex = glyph_index+write_dir;
 525                 for (l = 0; l < CompCount && CompIndex >= 0 && CompIndex < *glyph_count; l++)
 526                 {
 527                     int CompGlyph;
 528                     CompGlyph = GET_BE_WORD(lig->Component[l]);
 529                     if (CompGlyph != glyphs[CompIndex])
 530                         break;
 531                     CompIndex += write_dir;
 532                 }
 533                 if (l == CompCount)
 534                 {
 535                     int replaceIdx = glyph_index;
 536                     if (write_dir < 0)
 537                         replaceIdx = glyph_index - CompCount;
 538
 539                     TRACE("    Glyph is 0x%x (+%i) ->",glyphs[glyph_index],CompCount);
 540                     glyphs[replaceIdx] = GET_BE_WORD(lig->LigGlyph);
 541                     TRACE("0x%x\n",glyphs[replaceIdx]);
 542                     if (CompCount > 0)
 543                     {
 544                         int j;
 545                         for (j = replaceIdx + 1; j < *glyph_count; j++)
 546                             glyphs[j] =glyphs[j+CompCount];
 547                         *glyph_count = *glyph_count - CompCount;
 548                     }
 549                     return replaceIdx + 1;
 550                 }
 551             }
 552         }
 553     }
 554     return GSUB_E_NOGLYPH;
 555 }
 556
 557 static INT GSUB_apply_ChainContextSubst(const GSUB_LookupList* lookup, const GSUB_LookupTable *look, WORD *glyphs, INT glyph_index, INT write_dir, INT *glyph_count)
 558 {
 559     int j;
 560     BOOL done = FALSE;
 561
 562     TRACE("Chaining Contextual Substitution Subtable\n");
 563     for (j = 0; j < GET_BE_WORD(look->SubTableCount) && !done; j++)
 564     {
 565         const GSUB_ChainContextSubstFormat1 *ccsf1;
 566         int offset;
 567         int dirLookahead = write_dir;
 568         int dirBacktrack = -1 * write_dir;
 569
 570         offset = GET_BE_WORD(look->SubTable[j]);
 571         ccsf1 = (const GSUB_ChainContextSubstFormat1*)((const BYTE*)look+offset);
 572         if (GET_BE_WORD(ccsf1->SubstFormat) == 1)
 573         {
 574             FIXME("  TODO: subtype 1 (Simple context glyph substitution)\n");
 575             return -1;
 576         }
 577         else if (GET_BE_WORD(ccsf1->SubstFormat) == 2)
 578         {
 579             FIXME("  TODO: subtype 2 (Class-based Chaining Context Glyph Substitution)\n");
 580             return -1;
 581         }
 582         else if (GET_BE_WORD(ccsf1->SubstFormat) == 3)
 583         {
 584             int k;
 585             int indexGlyphs;
 586             const GSUB_ChainContextSubstFormat3_1 *ccsf3_1;
 587             const GSUB_ChainContextSubstFormat3_2 *ccsf3_2;
 588             const GSUB_ChainContextSubstFormat3_3 *ccsf3_3;
 589             const GSUB_ChainContextSubstFormat3_4 *ccsf3_4;
 590             int newIndex = glyph_index;
 591
 592             ccsf3_1 = (const GSUB_ChainContextSubstFormat3_1 *)ccsf1;
 593
 594             TRACE("  subtype 3 (Coverage-based Chaining Context Glyph Substitution)\n");
 595
 596             for (k = 0; k < GET_BE_WORD(ccsf3_1->BacktrackGlyphCount); k++)
 597             {
 598                 offset = GET_BE_WORD(ccsf3_1->Coverage[k]);
 599                 if (GSUB_is_glyph_covered((const BYTE*)ccsf3_1+offset, glyphs[glyph_index + (dirBacktrack * (k+1))]) == -1)
 600                     break;
 601             }
 602             if (k != GET_BE_WORD(ccsf3_1->BacktrackGlyphCount))
 603                 return -1;
 604             TRACE("Matched Backtrack\n");
 605
 606             ccsf3_2 = (const GSUB_ChainContextSubstFormat3_2 *)(((LPBYTE)ccsf1)+sizeof(GSUB_ChainContextSubstFormat3_1) + (sizeof(WORD) * (GET_BE_WORD(ccsf3_1->BacktrackGlyphCount)-1)));
 607
 608             indexGlyphs = GET_BE_WORD(ccsf3_2->InputGlyphCount);
 609             for (k = 0; k < indexGlyphs; k++)
 610             {
 611                 offset = GET_BE_WORD(ccsf3_2->Coverage[k]);
 612                 if (GSUB_is_glyph_covered((const BYTE*)ccsf3_1+offset, glyphs[glyph_index + (write_dir * k)]) == -1)
 613                     break;
 614             }
 615             if (k != indexGlyphs)
 616                 return -1;
 617             TRACE("Matched IndexGlyphs\n");
 618
 619             ccsf3_3 = (const GSUB_ChainContextSubstFormat3_3 *)(((LPBYTE)ccsf3_2)+sizeof(GSUB_ChainContextSubstFormat3_2) + (sizeof(WORD) * (GET_BE_WORD(ccsf3_2->InputGlyphCount)-1)));
 620
 621             for (k = 0; k < GET_BE_WORD(ccsf3_3->LookaheadGlyphCount); k++)
 622             {
 623                 offset = GET_BE_WORD(ccsf3_3->Coverage[k]);
 624                 if (GSUB_is_glyph_covered((const BYTE*)ccsf3_1+offset, glyphs[glyph_index + (dirLookahead * (indexGlyphs + k+1))]) == -1)
 625                     break;
 626             }
 627             if (k != GET_BE_WORD(ccsf3_3->LookaheadGlyphCount))
 628                 return -1;
 629             TRACE("Matched LookAhead\n");
 630
 631             ccsf3_4 = (const GSUB_ChainContextSubstFormat3_4 *)(((LPBYTE)ccsf3_3)+sizeof(GSUB_ChainContextSubstFormat3_3) + (sizeof(WORD) * (GET_BE_WORD(ccsf3_3->LookaheadGlyphCount)-1)));
 632
 633             for (k = 0; k < GET_BE_WORD(ccsf3_4->SubstCount); k++)
 634             {
 635                 int lookupIndex = GET_BE_WORD(ccsf3_4->SubstLookupRecord[k].LookupListIndex);
 636                 int SequenceIndex = GET_BE_WORD(ccsf3_4->SubstLookupRecord[k].SequenceIndex) * write_dir;
 637
 638                 TRACE("SUBST: %i -> %i %i\n",k, SequenceIndex, lookupIndex);
 639                 newIndex = GSUB_apply_lookup(lookup, lookupIndex, glyphs, glyph_index + SequenceIndex, write_dir, glyph_count);
 640                 if (newIndex == -1)
 641                 {
 642                     ERR("Chain failed to generate a glyph\n");
 643                     return -1;
 644                 }
 645             }
 646             return newIndex + 1;
 647         }
 648     }
 649     return -1;
 650 }
 651
 652 static INT GSUB_apply_lookup(const GSUB_LookupList* lookup, INT lookup_index, WORD *glyphs, INT glyph_index, INT write_dir, INT *glyph_count)
 653 {
 654     int offset;
 655     const GSUB_LookupTable *look;
 656
 657     offset = GET_BE_WORD(lookup->Lookup[lookup_index]);
 658     look = (const GSUB_LookupTable*)((const BYTE*)lookup + offset);
 659     TRACE("type %i, flag %x, subtables %i\n",GET_BE_WORD(look->LookupType),GET_BE_WORD(look->LookupFlag),GET_BE_WORD(look->SubTableCount));
 660     switch(GET_BE_WORD(look->LookupType))
 661     {
 662         case 1:
 663             return GSUB_apply_SingleSubst(look, glyphs, glyph_index, write_dir, glyph_count);
 664         case 3:
 665             return GSUB_apply_AlternateSubst(look, glyphs, glyph_index, write_dir, glyph_count);
 666         case 4:
 667             return GSUB_apply_LigatureSubst(look, glyphs, glyph_index, write_dir, glyph_count);
 668         case 6:
 669             return GSUB_apply_ChainContextSubst(lookup, look, glyphs, glyph_index, write_dir, glyph_count);
 670         default:
 671             FIXME("We do not handle SubType %i\n",GET_BE_WORD(look->LookupType));
 672     }
 673     return GSUB_E_NOGLYPH;
 674 }
 675
 676 static INT GSUB_apply_feature(const GSUB_Header * header, const GSUB_Feature* feature, WORD *glyphs, INT glyph_index, INT write_dir, INT *glyph_count)
 677 {
 678     int i;
 679     int out_index = GSUB_E_NOGLYPH;
 680     const GSUB_LookupList *lookup;
 681
 682     lookup = (const GSUB_LookupList*)((const BYTE*)header + GET_BE_WORD(header->LookupList));
 683
 684     TRACE("%i lookups\n", GET_BE_WORD(feature->LookupCount));
 685     for (i = 0; i < GET_BE_WORD(feature->LookupCount); i++)
 686     {
 687         out_index = GSUB_apply_lookup(lookup, GET_BE_WORD(feature->LookupListIndex[i]), glyphs, glyph_index, write_dir, glyph_count);
 688         if (out_index != GSUB_E_NOGLYPH)
 689             break;
 690     }
 691     if (out_index == GSUB_E_NOGLYPH)
 692         TRACE("lookups found no glyphs\n");
 693     return out_index;
 694 }
 695
 696 static const char* get_opentype_script(HDC hdc, SCRIPT_ANALYSIS *psa)
 697 {
 698     UINT charset;
 699
 700     if (ShapingData[psa->eScript].otTag[0] != 0)
 701         return ShapingData[psa->eScript].otTag;
 702
 703     /*
 704      * fall back to the font charset
 705      */
 706     charset = GetTextCharsetInfo(hdc, NULL, 0x0);
 707     switch (charset)
 708     {
 709         case ANSI_CHARSET: return "latn";
 710         case BALTIC_CHARSET: return "latn"; /* ?? */
 711         case CHINESEBIG5_CHARSET: return "hani";
 712         case EASTEUROPE_CHARSET: return "latn"; /* ?? */
 713         case GB2312_CHARSET: return "hani";
 714         case GREEK_CHARSET: return "grek";
 715         case HANGUL_CHARSET: return "hang";
 716         case RUSSIAN_CHARSET: return "cyrl";
 717         case SHIFTJIS_CHARSET: return "kana";
 718         case TURKISH_CHARSET: return "latn"; /* ?? */
 719         case VIETNAMESE_CHARSET: return "latn";
 720         case JOHAB_CHARSET: return "latn"; /* ?? */
 721         case ARABIC_CHARSET: return "arab";
 722         case HEBREW_CHARSET: return "hebr";
 723         case THAI_CHARSET: return "thai";
 724         default: return "latn";
 725     }
 726 }
 727
 728 static LPCVOID load_GSUB_feature(HDC hdc, SCRIPT_ANALYSIS *psa, ScriptCache *psc, const char* feat)
 729 {
 730     const GSUB_Feature *feature;
 731     int i;
 732
 733     for (i = 0; i <  psc->feature_count; i++)
 734         if (strncmp(psc->features[i].tag,feat,4)==0)
 735             return psc->features[i].feature;
 736
 737     feature = NULL;
 738
 739     if (psc->GSUB_Table)
 740     {
 741         const GSUB_Script *script;
 742         const GSUB_LangSys *language;
 743
 744         script = GSUB_get_script_table(psc->GSUB_Table, get_opentype_script(hdc,psa));
 745         if (script)
 746         {
 747             language = GSUB_get_lang_table(script, "xxxx"); /* Need to get Lang tag */
 748             if (language)
 749                 feature = GSUB_get_feature(psc->GSUB_Table, language, feat);
 750         }
 751
 752         /* try in the default (latin) table */
 753         if (!feature)
 754         {
 755             script = GSUB_get_script_table(psc->GSUB_Table, "latn");
 756             if (script)
 757             {
 758                 language = GSUB_get_lang_table(script, "xxxx"); /* Need to get Lang tag */
 759                 if (language)
 760                     feature = GSUB_get_feature(psc->GSUB_Table, language, feat);
 761             }
 762         }
 763     }
 764
 765     TRACE("Feature %s located at %p\n",debugstr_an(feat,4),feature);
 766
 767     psc->feature_count++;
 768
 769     if (psc->features)
 770         psc->features = HeapReAlloc(GetProcessHeap(), 0, psc->features, psc->feature_count * sizeof(LoadedFeature));
 771     else
 772         psc->features = HeapAlloc(GetProcessHeap(), 0, psc->feature_count * sizeof(LoadedFeature));
 773
 774     lstrcpynA(psc->features[psc->feature_count - 1].tag,feat,4);
 775     psc->features[psc->feature_count - 1].feature = feature;
 776     return feature;
 777 }
 778
 779 static INT apply_GSUB_feature_to_glyph(HDC hdc, SCRIPT_ANALYSIS *psa, ScriptCache* psc, WORD *glyphs, INT index, INT write_dir, INT* glyph_count, const char* feat)
 780 {
 781     const GSUB_Feature *feature;
 782
 783     feature = load_GSUB_feature(hdc, psa, psc, feat);
 784     if (!feature)
 785         return GSUB_E_NOFEATURE;
 786
 787     TRACE("applying feature %s\n",feat);
 788     return GSUB_apply_feature(psc->GSUB_Table, feature, glyphs, index, write_dir, glyph_count);
 789 }
 790
 791 static VOID *load_gsub_table(HDC hdc)
 792 {
 793     VOID* GSUB_Table = NULL;
 794     int length = GetFontData(hdc, GSUB_TAG , 0, NULL, 0);
 795     if (length != GDI_ERROR)
 796     {
 797         GSUB_Table = HeapAlloc(GetProcessHeap(),0,length);
 798         GetFontData(hdc, GSUB_TAG , 0, GSUB_Table, length);
 799         TRACE("Loaded GSUB table of %i bytes\n",length);
 800     }
 801     return GSUB_Table;
 802 }
 803
 804 static int apply_GSUB_feature(HDC hdc, SCRIPT_ANALYSIS *psa, ScriptCache* psc, WORD *pwOutGlyphs, int write_dir, INT* pcGlyphs, const char* feat)
 805 {
 806     int i;
 807
 808     if (psc->GSUB_Table)
 809     {
 810         const GSUB_Feature *feature;
 811
 812         feature = load_GSUB_feature(hdc, psa, psc, feat);
 813         if (!feature)
 814             return GSUB_E_NOFEATURE;
 815
 816         i = 0;
 817         TRACE("applying feature %s\n",debugstr_an(feat,4));
 818         while(i < *pcGlyphs)
 819         {
 820                 INT nextIndex;
 821                 nextIndex = GSUB_apply_feature(psc->GSUB_Table, feature, pwOutGlyphs, i, write_dir, pcGlyphs);
 822                 if (nextIndex > GSUB_E_NOGLYPH)
 823                     i = nextIndex;
 824                 else
 825                     i++;
 826         }
 827         return *pcGlyphs;
 828     }
 829     return GSUB_E_NOFEATURE;
 830 }
 831
 832 static CHAR neighbour_joining_type(int i, int delta, const CHAR* context_type, INT cchLen, SCRIPT_ANALYSIS *psa)
 833 {
 834     if (i + delta < 0)
 835     {
 836         if (psa->fLinkBefore)
 837             return jtR;
 838         else
 839             return jtU;
 840     }
 841     if ( i+ delta >= cchLen)
 842     {
 843         if (psa->fLinkAfter)
 844             return jtL;
 845         else
 846             return jtU;
 847     }
 848
 849     i += delta;
 850
 851     if (context_type[i] == jtT)
 852         return neighbour_joining_type(i,delta,context_type,cchLen,psa);
 853     else
 854         return context_type[i];
 855 }
 856
 857 static inline BOOL right_join_causing(CHAR joining_type)
 858 {
 859     return (joining_type == jtL || joining_type == jtD || joining_type == jtC);
 860 }
 861
 862 static inline BOOL left_join_causing(CHAR joining_type)
 863 {
 864     return (joining_type == jtR || joining_type == jtD || joining_type == jtC);
 865 }
 866
 867 /*
 868  * ContextualShape_Arabic
 869  */
 870 static void ContextualShape_Arabic(HDC hdc, ScriptCache *psc, SCRIPT_ANALYSIS *psa, WCHAR* pwcChars, INT cChars, WORD* pwOutGlyphs, INT* pcGlyphs, INT cMaxGlyphs)
 871 {
 872     CHAR *context_type;
 873     INT *context_shape;
 874     INT dirR, dirL;
 875     int i;
 876
 877     if (*pcGlyphs != cChars)
 878     {
 879         ERR("Number of Glyphs and Chars need to match at the beginning\n");
 880         return;
 881     }
 882
 883     if (!psa->fLogicalOrder && psa->fRTL)
 884     {
 885         dirR = 1;
 886         dirL = -1;
 887     }
 888     else
 889     {
 890         dirR = -1;
 891         dirL = 1;
 892     }
 893
 894     if (!psc->GSUB_Table)
 895         psc->GSUB_Table = load_gsub_table(hdc);
 896
 897     context_type = HeapAlloc(GetProcessHeap(),0,cChars);
 898     context_shape = HeapAlloc(GetProcessHeap(),0,sizeof(INT) * cChars);
 899
 900     for (i = 0; i < cChars; i++)
 901         context_type[i] = wine_shaping_table[wine_shaping_table[pwcChars[i] >> 8] + (pwcChars[i] & 0xff)];
 902
 903     for (i = 0; i < cChars; i++)
 904     {
 905         if (context_type[i] == jtR && right_join_causing(neighbour_joining_type(i,dirR,context_type,cChars,psa)))
 906             context_shape[i] = Xr;
 907         else if (context_type[i] == jtL && left_join_causing(neighbour_joining_type(i,dirL,context_type,cChars,psa)))
 908             context_shape[i] = Xl;
 909         else if (context_type[i] == jtD && left_join_causing(neighbour_joining_type(i,dirL,context_type,cChars,psa)) && right_join_causing(neighbour_joining_type(i,dirR,context_type,cChars,psa)))
 910             context_shape[i] = Xm;
 911         else if (context_type[i] == jtD && right_join_causing(neighbour_joining_type(i,dirR,context_type,cChars,psa)))
 912             context_shape[i] = Xr;
 913         else if (context_type[i] == jtD && left_join_causing(neighbour_joining_type(i,dirL,context_type,cChars,psa)))
 914             context_shape[i] = Xl;
 915         else
 916             context_shape[i] = Xn;
 917     }
 918
 919     /* Contextual Shaping */
 920     i = 0;
 921     while(i < *pcGlyphs)
 922     {
 923         BOOL shaped = FALSE;
 924
 925         if (psc->GSUB_Table)
 926         {
 927             INT nextIndex;
 928             nextIndex = apply_GSUB_feature_to_glyph(hdc, psa, psc, pwOutGlyphs, i, dirL, pcGlyphs, contextual_features[context_shape[i]]);
 929             if (nextIndex > GSUB_E_NOGLYPH)
 930                 i = nextIndex;
 931             shaped = (nextIndex > GSUB_E_NOGLYPH);
 932         }
 933
 934         if (!shaped)
 935         {
 936             WORD newGlyph = pwOutGlyphs[i];
 937             if (pwcChars[i] >= FIRST_ARABIC_CHAR && pwcChars[i] <= LAST_ARABIC_CHAR)
 938             {
 939                 /* fall back to presentation form B */
 940                 WCHAR context_char = wine_shaping_forms[pwcChars[i] - FIRST_ARABIC_CHAR][context_shape[i]];
 941                 if (context_char != pwcChars[i] && GetGlyphIndicesW(hdc, &context_char, 1, &newGlyph, 0) != GDI_ERROR && newGlyph != 0x0000)
 942                     pwOutGlyphs[i] = newGlyph;
 943             }
 944             i++;
 945         }
 946     }
 947
 948     HeapFree(GetProcessHeap(),0,context_shape);
 949     HeapFree(GetProcessHeap(),0,context_type);
 950 }
 951
 952 void SHAPE_ContextualShaping(HDC hdc, ScriptCache *psc, SCRIPT_ANALYSIS *psa, WCHAR* pwcChars, INT cChars, WORD* pwOutGlyphs, INT* pcGlyphs, INT cMaxGlyphs)
 953 {
 954     if (ShapingData[psa->eScript].contextProc)
 955         ShapingData[psa->eScript].contextProc(hdc, psc, psa, pwcChars, cChars, pwOutGlyphs, pcGlyphs, cMaxGlyphs);
 956 }
 957
 958 void SHAPE_ApplyOpenTypeFeatures(HDC hdc, ScriptCache *psc, SCRIPT_ANALYSIS *psa, WORD* pwOutGlyphs, INT* pcGlyphs, INT cMaxGlyphs, const TEXTRANGE_PROPERTIES *rpRangeProperties)
 959 {
 960     int i;
 961     INT dirL;
 962
 963     if (!rpRangeProperties)
 964         return;
 965
 966     if (!psc->GSUB_Table)
 967         psc->GSUB_Table = load_gsub_table(hdc);
 968
 969     if (!psc->GSUB_Table)
 970         return;
 971
 972     if (!psa->fLogicalOrder && psa->fRTL)
 973         dirL = -1;
 974     else
 975         dirL = 1;
 976
 977     for (i = 0; i < rpRangeProperties->cotfRecords; i++)
 978     {
 979         if (rpRangeProperties->potfRecords[i].lParameter > 0)
 980             apply_GSUB_feature(hdc, psa, psc, pwOutGlyphs, dirL, pcGlyphs, (const char*)&rpRangeProperties->potfRecords[i].tagFeature);
 981     }
 982 }
 983
 984 void SHAPE_ApplyDefaultOpentypeFeatures(HDC hdc, ScriptCache *psc, SCRIPT_ANALYSIS *psa, WORD* pwOutGlyphs, INT* pcGlyphs, INT cMaxGlyphs)
 985 {
 986     const TEXTRANGE_PROPERTIES *rpRangeProperties;
 987     rpRangeProperties = &ShapingData[psa->eScript].defaultTextRange;
 988
 989     SHAPE_ApplyOpenTypeFeatures(hdc, psc, psa, pwOutGlyphs, pcGlyphs, cMaxGlyphs, rpRangeProperties);
 990 }