dlls/gdi32/bidi.c

   1 /*
   2  * GDI BiDirectional handling
   3  *
   4  * Copyright 2003 Shachar Shemesh
   5  * Copyright 2007 Maarten Lankhorst
   6  * Copyright 2010 CodeWeavers, Aric Stewart
   7  *
   8  * This library is free software; you can redistribute it and/or
   9  * modify it under the terms of the GNU Lesser General Public
  10  * License as published by the Free Software Foundation; either
  11  * version 2.1 of the License, or (at your option) any later version.
  12  *
  13  * This library is distributed in the hope that it will be useful,
  14  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  16  * Lesser General Public License for more details.
  17  *
  18  * You should have received a copy of the GNU Lesser General Public
  19  * License along with this library; if not, write to the Free Software
  20  * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA
  21  *
  22  * Code derived from the modified reference implementation
  23  * that was found in revision 17 of http://unicode.org/reports/tr9/
  24  * "Unicode Standard Annex #9: THE BIDIRECTIONAL ALGORITHM"
  25  *
  26  * -- Copyright (C) 1999-2005, ASMUS, Inc.
  27  *
  28  * Permission is hereby granted, free of charge, to any person obtaining a
  29  * copy of the Unicode data files and any associated documentation (the
  30  * "Data Files") or Unicode software and any associated documentation (the
  31  * "Software") to deal in the Data Files or Software without restriction,
  32  * including without limitation the rights to use, copy, modify, merge,
  33  * publish, distribute, and/or sell copies of the Data Files or Software,
  34  * and to permit persons to whom the Data Files or Software are furnished
  35  * to do so, provided that (a) the above copyright notice(s) and this
  36  * permission notice appear with all copies of the Data Files or Software,
  37  * (b) both the above copyright notice(s) and this permission notice appear
  38  * in associated documentation, and (c) there is clear notice in each
  39  * modified Data File or in the Software as well as in the documentation
  40  * associated with the Data File(s) or Software that the data or software
  41  * has been modified.
  42  */
  43
  44 #include "config.h"
  45
  46 #include <stdarg.h>
  47 #include "windef.h"
  48 #include "winbase.h"
  49 #include "wingdi.h"
  50 #include "winnls.h"
  51 #include "usp10.h"
  52 #include "wine/unicode.h"
  53 #include "wine/debug.h"
  54 #include "gdi_private.h"
  55
  56 WINE_DEFAULT_DEBUG_CHANNEL(bidi);
  57
  58 /* HELPER FUNCTIONS AND DECLARATIONS */
  59
  60 #define odd(x) ((x) & 1)
  61
  62 /*------------------------------------------------------------------------
  63     Bidirectional Character Types
  64
  65     as defined by the Unicode Bidirectional Algorithm Table 3-7.
  66
  67     Note:
  68
  69       The list of bidirectional character types here is not grouped the
  70       same way as the table 3-7, since the numberic values for the types
  71       are chosen to keep the state and action tables compact.
  72 ------------------------------------------------------------------------*/
  73 enum directions
  74 {
  75     /* input types */
  76              /* ON MUST be zero, code relies on ON = N = 0 */
  77     ON = 0,  /* Other Neutral */
  78     L,       /* Left Letter */
  79     R,       /* Right Letter */
  80     AN,      /* Arabic Number */
  81     EN,      /* European Number */
  82     AL,      /* Arabic Letter (Right-to-left) */
  83     NSM,     /* Non-spacing Mark */
  84     CS,      /* Common Separator */
  85     ES,      /* European Separator */
  86     ET,      /* European Terminator (post/prefix e.g. $ and %) */
  87
  88     /* resolved types */
  89     BN,      /* Boundary neutral (type of RLE etc after explicit levels) */
  90
  91     /* input types, */
  92     S,       /* Segment Separator (TAB)        // used only in L1 */
  93     WS,      /* White space                    // used only in L1 */
  94     B,       /* Paragraph Separator (aka as PS) */
  95
  96     /* types for explicit controls */
  97     RLO,     /* these are used only in X1-X9 */
  98     RLE,
  99     LRO,
 100     LRE,
 101     PDF,
 102
 103     /* resolved types, also resolved directions */
 104     N = ON,  /* alias, where ON, WS and S are treated the same */
 105 };
 106
 107 /* HELPER FUNCTIONS */
 108
 109 /* Convert the libwine information to the direction enum */
 110 static void classify(LPCWSTR lpString, WORD *chartype, DWORD uCount)
 111 {
 112     static const enum directions dir_map[16] =
 113     {
 114         L,  /* unassigned defaults to L */
 115         L,
 116         R,
 117         EN,
 118         ES,
 119         ET,
 120         AN,
 121         CS,
 122         B,
 123         S,
 124         WS,
 125         ON,
 126         AL,
 127         NSM,
 128         BN,
 129         PDF  /* also LRE, LRO, RLE, RLO */
 130     };
 131
 132     unsigned i;
 133
 134     for (i = 0; i < uCount; ++i)
 135     {
 136         chartype[i] = dir_map[get_char_typeW(lpString[i]) >> 12];
 137         if (chartype[i] == PDF)
 138         {
 139             switch (lpString[i])
 140             {
 141             case 0x202A: chartype[i] = LRE; break;
 142             case 0x202B: chartype[i] = RLE; break;
 143             case 0x202C: chartype[i] = PDF; break;
 144             case 0x202D: chartype[i] = LRO; break;
 145             case 0x202E: chartype[i] = RLO; break;
 146             }
 147         }
 148     }
 149 }
 150
 151 /* Set a run of cval values at locations all prior to, but not including */
 152 /* iStart, to the new value nval. */
 153 static void SetDeferredRun(BYTE *pval, int cval, int iStart, int nval)
 154 {
 155     int i = iStart - 1;
 156     for (; i >= iStart - cval; i--)
 157     {
 158         pval[i] = nval;
 159     }
 160 }
 161
 162 /* THE PARAGRAPH LEVEL */
 163
 164 /*------------------------------------------------------------------------
 165     Function: resolveParagraphs
 166
 167     Resolves the input strings into blocks over which the algorithm
 168     is then applied.
 169
 170     Implements Rule P1 of the Unicode Bidi Algorithm
 171
 172     Input: Text string
 173            Character count
 174
 175     Output: revised character count
 176
 177     Note:    This is a very simplistic function. In effect it restricts
 178             the action of the algorithm to the first paragraph in the input
 179             where a paragraph ends at the end of the first block separator
 180             or at the end of the input text.
 181
 182 ------------------------------------------------------------------------*/
 183
 184 static int resolveParagraphs(WORD *types, int cch)
 185 {
 186     /* skip characters not of type B */
 187     int ich = 0;
 188     for(; ich < cch && types[ich] != B; ich++);
 189     /* stop after first B, make it a BN for use in the next steps */
 190     if (ich < cch && types[ich] == B)
 191         types[ich++] = BN;
 192     return ich;
 193 }
 194
 195 /* REORDER */
 196 /*------------------------------------------------------------------------
 197     Function: resolveLines
 198
 199     Breaks a paragraph into lines
 200
 201     Input:  Character count
 202     In/Out: Array of characters
 203             Array of line break flags
 204
 205     Returns the count of characters on the first line
 206
 207     Note: This function only breaks lines at hard line breaks. Other
 208     line breaks can be passed in. If pbrk[n] is TRUE, then a break
 209     occurs after the character in pszInput[n]. Breaks before the first
 210     character are not allowed.
 211 ------------------------------------------------------------------------*/
 212 static int resolveLines(LPCWSTR pszInput, BOOL * pbrk, int cch)
 213 {
 214     /* skip characters not of type LS */
 215     int ich = 0;
 216     for(; ich < cch; ich++)
 217     {
 218         if (pszInput[ich] == (WCHAR)'\n' || (pbrk && pbrk[ich]))
 219         {
 220             ich++;
 221             break;
 222         }
 223     }
 224
 225     return ich;
 226 }
 227
 228 /*------------------------------------------------------------------------
 229     Function: resolveWhiteSpace
 230
 231     Resolves levels for WS and S
 232     Implements rule L1 of the Unicode bidi Algorithm.
 233
 234     Input:  Base embedding level
 235             Character count
 236             Array of direction classes (for one line of text)
 237
 238     In/Out: Array of embedding levels (for one line of text)
 239
 240     Note: this should be applied a line at a time. The default driver
 241           code supplied in this file assumes a single line of text; for
 242           a real implementation, cch and the initial pointer values
 243           would have to be adjusted.
 244 ------------------------------------------------------------------------*/
 245 static void resolveWhitespace(int baselevel, const WORD *pcls, BYTE *plevel, int cch)
 246 {
 247     int cchrun = 0;
 248     BYTE oldlevel = baselevel;
 249
 250     int ich = 0;
 251     for (; ich < cch; ich++)
 252     {
 253         switch(pcls[ich])
 254         {
 255         default:
 256             cchrun = 0; /* any other character breaks the run */
 257             break;
 258         case WS:
 259             cchrun++;
 260             break;
 261
 262         case RLE:
 263         case LRE:
 264         case LRO:
 265         case RLO:
 266         case PDF:
 267         case BN:
 268             plevel[ich] = oldlevel;
 269             cchrun++;
 270             break;
 271
 272         case S:
 273         case B:
 274             /* reset levels for WS before eot */
 275             SetDeferredRun(plevel, cchrun, ich, baselevel);
 276             cchrun = 0;
 277             plevel[ich] = baselevel;
 278             break;
 279         }
 280         oldlevel = plevel[ich];
 281     }
 282     /* reset level before eot */
 283     SetDeferredRun(plevel, cchrun, ich, baselevel);
 284 }
 285
 286 /*------------------------------------------------------------------------
 287     Function: BidiLines
 288
 289     Implements the Line-by-Line phases of the Unicode Bidi Algorithm
 290
 291       Input:     Count of characters
 292
 293     Inp/Out: Input text
 294              Array of character directions
 295              Array of levels
 296
 297 ------------------------------------------------------------------------*/
 298 static void BidiLines(int baselevel, LPWSTR pszOutLine, LPCWSTR pszLine, WORD * pclsLine,
 299                       BYTE * plevelLine, int cchPara, BOOL * pbrk)
 300 {
 301     int cchLine = 0;
 302     int done = 0;
 303     int *run;
 304
 305     run = HeapAlloc(GetProcessHeap(), 0, cchPara * sizeof(int));
 306     if (!run)
 307     {
 308         WARN("Out of memory\n");
 309         return;
 310     }
 311
 312     do
 313     {
 314         /* break lines at LS */
 315         cchLine = resolveLines(pszLine, pbrk, cchPara);
 316
 317         /* resolve whitespace */
 318         resolveWhitespace(baselevel, pclsLine, plevelLine, cchLine);
 319
 320         if (pszOutLine)
 321         {
 322             int i;
 323             /* reorder each line in place */
 324             ScriptLayout(cchLine, plevelLine, run, NULL);
 325             for (i = 0; i < cchLine; i++)
 326                 pszOutLine[done+run[i]] = pszLine[i];
 327         }
 328
 329         pszLine += cchLine;
 330         plevelLine += cchLine;
 331         pbrk += pbrk ? cchLine : 0;
 332         pclsLine += cchLine;
 333         cchPara -= cchLine;
 334         done += cchLine;
 335
 336     } while (cchPara);
 337
 338     HeapFree(GetProcessHeap(), 0, run);
 339 }
 340
 341 /*************************************************************
 342  *    BIDI_Reorder
 343  *
 344  *     Returns TRUE if reordering was required and done.
 345  */
 346 BOOL BIDI_Reorder(
 347                 HDC hDC,        /*[in] Display DC */
 348                 LPCWSTR lpString,       /* [in] The string for which information is to be returned */
 349                 INT uCount,     /* [in] Number of WCHARs in string. */
 350                 DWORD dwFlags,  /* [in] GetCharacterPlacement compatible flags specifying how to process the string */
 351                 DWORD dwWineGCP_Flags,       /* [in] Wine internal flags - Force paragraph direction */
 352                 LPWSTR lpOutString, /* [out] Reordered string */
 353                 INT uCountOut,  /* [in] Size of output buffer */
 354                 UINT *lpOrder, /* [out] Logical -> Visual order map */
 355                 WORD **lpGlyphs, /* [out] reordered, mirrored, shaped glyphs to display */
 356                 INT *cGlyphs /* [out] number of glyphs generated */
 357     )
 358 {
 359     WORD *chartype;
 360     BYTE *levels;
 361     unsigned i, done, glyph_i;
 362
 363     int maxItems;
 364     int nItems;
 365     SCRIPT_CONTROL Control;
 366     SCRIPT_STATE State;
 367     SCRIPT_ITEM *pItems;
 368     HRESULT res;
 369     SCRIPT_CACHE psc = NULL;
 370     WORD *run_glyphs = NULL;
 371     WORD *pwLogClust = NULL;
 372     SCRIPT_VISATTR *psva = NULL;
 373     DWORD cMaxGlyphs = 0;
 374     BOOL  doGlyphs = TRUE;
 375
 376     TRACE("%s, %d, 0x%08x lpOutString=%p, lpOrder=%p\n",
 377           debugstr_wn(lpString, uCount), uCount, dwFlags,
 378           lpOutString, lpOrder);
 379
 380     memset(&Control, 0, sizeof(Control));
 381     memset(&State, 0, sizeof(State));
 382     if (lpGlyphs)
 383         *lpGlyphs = NULL;
 384
 385     if (!(dwFlags & GCP_REORDER))
 386     {
 387         FIXME("Asked to reorder without reorder flag set\n");
 388         return FALSE;
 389     }
 390
 391     if (lpOutString && uCountOut < uCount)
 392     {
 393         FIXME("lpOutString too small\n");
 394         return FALSE;
 395     }
 396
 397     chartype = HeapAlloc(GetProcessHeap(), 0, uCount * sizeof(WORD));
 398     if (!chartype)
 399     {
 400         WARN("Out of memory\n");
 401         return FALSE;
 402     }
 403
 404     if (lpOutString)
 405         memcpy(lpOutString, lpString, uCount * sizeof(WCHAR));
 406
 407     /* Verify reordering will be required */
 408     if ((WINE_GCPW_FORCE_RTL == (dwWineGCP_Flags&WINE_GCPW_DIR_MASK)) ||
 409         ((dwWineGCP_Flags&WINE_GCPW_DIR_MASK) == WINE_GCPW_LOOSE_RTL))
 410         State.uBidiLevel = 1;
 411     else
 412     {
 413         done = 1;
 414         classify(lpString, chartype, uCount);
 415         for (i = 0; i < uCount; i++)
 416             switch (chartype[i])
 417             {
 418                 case R:
 419                 case AL:
 420                 case RLE:
 421                 case RLO:
 422                     done = 0;
 423                     break;
 424             }
 425         if (done)
 426         {
 427             HeapFree(GetProcessHeap(), 0, chartype);
 428             if (lpOrder)
 429             {
 430                 for (i = 0; i < uCount; i++)
 431                     lpOrder[i] = i;
 432             }
 433             return TRUE;
 434         }
 435     }
 436
 437     levels = HeapAlloc(GetProcessHeap(), 0, uCount * sizeof(BYTE));
 438     if (!levels)
 439     {
 440         WARN("Out of memory\n");
 441         HeapFree(GetProcessHeap(), 0, chartype);
 442         return FALSE;
 443     }
 444
 445     maxItems = 5;
 446     pItems = HeapAlloc(GetProcessHeap(),0, maxItems * sizeof(SCRIPT_ITEM));
 447     if (!pItems)
 448     {
 449         WARN("Out of memory\n");
 450         HeapFree(GetProcessHeap(), 0, chartype);
 451         HeapFree(GetProcessHeap(), 0, levels);
 452         return FALSE;
 453     }
 454
 455     if (lpGlyphs)
 456     {
 457         cMaxGlyphs = 1.5 * uCount + 16;
 458         run_glyphs = HeapAlloc(GetProcessHeap(),0,sizeof(WORD) * cMaxGlyphs);
 459         if (!run_glyphs)
 460         {
 461             WARN("Out of memory\n");
 462             HeapFree(GetProcessHeap(), 0, chartype);
 463             HeapFree(GetProcessHeap(), 0, levels);
 464             HeapFree(GetProcessHeap(), 0, pItems);
 465             return FALSE;
 466         }
 467         pwLogClust = HeapAlloc(GetProcessHeap(),0,sizeof(WORD) * uCount);
 468         if (!pwLogClust)
 469         {
 470             WARN("Out of memory\n");
 471             HeapFree(GetProcessHeap(), 0, chartype);
 472             HeapFree(GetProcessHeap(), 0, levels);
 473             HeapFree(GetProcessHeap(), 0, pItems);
 474             HeapFree(GetProcessHeap(), 0, run_glyphs);
 475             return FALSE;
 476         }
 477         psva = HeapAlloc(GetProcessHeap(),0,sizeof(SCRIPT_VISATTR) * uCount);
 478         if (!psva)
 479         {
 480             WARN("Out of memory\n");
 481             HeapFree(GetProcessHeap(), 0, chartype);
 482             HeapFree(GetProcessHeap(), 0, levels);
 483             HeapFree(GetProcessHeap(), 0, pItems);
 484             HeapFree(GetProcessHeap(), 0, run_glyphs);
 485             HeapFree(GetProcessHeap(), 0, pwLogClust);
 486             return FALSE;
 487         }
 488     }
 489
 490     done = 0;
 491     glyph_i = 0;
 492     while (done < uCount)
 493     {
 494         unsigned j;
 495         classify(lpString + done, chartype, uCount - done);
 496         /* limit text to first block */
 497         i = resolveParagraphs(chartype, uCount - done);
 498         for (j = 0; j < i; ++j)
 499             switch(chartype[j])
 500             {
 501                 case B:
 502                 case S:
 503                 case WS:
 504                 case ON: chartype[j] = N;
 505                 default: continue;
 506             }
 507
 508         if ((dwWineGCP_Flags&WINE_GCPW_DIR_MASK) == WINE_GCPW_LOOSE_RTL)
 509             State.uBidiLevel = 1;
 510         else if ((dwWineGCP_Flags&WINE_GCPW_DIR_MASK) == WINE_GCPW_LOOSE_LTR)
 511             State.uBidiLevel = 0;
 512
 513         if (dwWineGCP_Flags & WINE_GCPW_LOOSE_MASK)
 514         {
 515             for (j = 0; j < i; ++j)
 516                 if (chartype[j] == L)
 517                 {
 518                     State.uBidiLevel = 0;
 519                     break;
 520                 }
 521                 else if (chartype[j] == R || chartype[j] == AL)
 522                 {
 523                     State.uBidiLevel = 1;
 524                     break;
 525                 }
 526         }
 527
 528         res = ScriptItemize(lpString + done, i, maxItems, &Control, &State, pItems, &nItems);
 529         while (res == E_OUTOFMEMORY)
 530         {
 531             maxItems = maxItems * 2;
 532             pItems = HeapReAlloc(GetProcessHeap(), 0, pItems, sizeof(SCRIPT_ITEM) * maxItems);
 533             if (!pItems)
 534             {
 535                 WARN("Out of memory\n");
 536                 HeapFree(GetProcessHeap(), 0, chartype);
 537                 HeapFree(GetProcessHeap(), 0, levels);
 538                 return FALSE;
 539             }
 540             res = ScriptItemize(lpString + done, i, maxItems, &Control, &State, pItems, &nItems);
 541         }
 542
 543         if (lpOutString || lpOrder)
 544             for (j = 0; j < nItems; j++)
 545             {
 546                 int k;
 547                 for (k = pItems[j].iCharPos; k < pItems[j+1].iCharPos; k++)
 548                     levels[k] = pItems[j].a.s.uBidiLevel;
 549             }
 550
 551         if (lpOutString)
 552         {
 553             /* assign directional types again, but for WS, S this time */
 554             classify(lpString + done, chartype, i);
 555
 556             BidiLines(State.uBidiLevel, lpOutString + done, lpString + done,
 557                         chartype, levels, i, 0);
 558         }
 559
 560         if (lpOrder)
 561         {
 562             int k, lastgood;
 563             for (j = lastgood = 0; j < i; ++j)
 564                 if (levels[j] != levels[lastgood])
 565                 {
 566                     --j;
 567                     if (odd(levels[lastgood]))
 568                         for (k = j; k >= lastgood; --k)
 569                             lpOrder[done + k] = done + j - k;
 570                     else
 571                         for (k = lastgood; k <= j; ++k)
 572                             lpOrder[done + k] = done + k;
 573                     lastgood = ++j;
 574                 }
 575             if (odd(levels[lastgood]))
 576                 for (k = j - 1; k >= lastgood; --k)
 577                     lpOrder[done + k] = done + j - 1 - k;
 578             else
 579                 for (k = lastgood; k < j; ++k)
 580                     lpOrder[done + k] = done + k;
 581         }
 582
 583         if (lpGlyphs && doGlyphs)
 584         {
 585             int j;
 586             BYTE runOrder[maxItems];
 587             int visOrder[maxItems];
 588             SCRIPT_ITEM *curItem;
 589
 590             for (j = 0; j < nItems; j++)
 591                 runOrder[j] = pItems[j].a.s.uBidiLevel;
 592
 593             ScriptLayout(nItems, runOrder, NULL, visOrder);
 594
 595             for (j = 0; j < nItems; j++)
 596             {
 597                 int k;
 598                 int cChars,cOutGlyphs;
 599                 curItem = &pItems[visOrder[j]];
 600
 601                 cChars = pItems[visOrder[j]+1].iCharPos - curItem->iCharPos;
 602
 603                 res = ScriptShape(hDC, &psc, lpString + done + curItem->iCharPos, cChars, cMaxGlyphs, &curItem->a, run_glyphs, pwLogClust, psva, &cOutGlyphs);
 604                 while (res == E_OUTOFMEMORY)
 605                 {
 606                     cMaxGlyphs *= 2;
 607                     run_glyphs = HeapReAlloc(GetProcessHeap(), 0, run_glyphs, sizeof(WORD) * cMaxGlyphs);
 608                     if (!run_glyphs)
 609                     {
 610                         WARN("Out of memory\n");
 611                         HeapFree(GetProcessHeap(), 0, chartype);
 612                         HeapFree(GetProcessHeap(), 0, levels);
 613                         HeapFree(GetProcessHeap(), 0, pItems);
 614                         HeapFree(GetProcessHeap(), 0, psva);
 615                         HeapFree(GetProcessHeap(), 0, pwLogClust);
 616                         HeapFree(GetProcessHeap(), 0, *lpGlyphs);
 617                         ScriptFreeCache(&psc);
 618                         *lpGlyphs = NULL;
 619                         return FALSE;
 620                     }
 621                     res = ScriptShape(hDC, &psc, lpString + done + curItem->iCharPos, cChars, cMaxGlyphs, &curItem->a, run_glyphs, pwLogClust, psva, &cOutGlyphs);
 622                 }
 623                 if (res)
 624                 {
 625                     FIXME("Unable to shape string (%x)\n",res);
 626                     j = nItems;
 627                     doGlyphs = FALSE;
 628                     HeapFree(GetProcessHeap(), 0, *lpGlyphs);
 629                     *lpGlyphs = NULL;
 630                 }
 631                 else
 632                 {
 633                     if (*lpGlyphs)
 634                         *lpGlyphs = HeapReAlloc(GetProcessHeap(), 0, *lpGlyphs, sizeof(WORD) * (glyph_i + cOutGlyphs));
 635                    else
 636                         *lpGlyphs = HeapAlloc(GetProcessHeap(), 0, sizeof(WORD) * (glyph_i + cOutGlyphs));
 637                     for (k = 0; k < cOutGlyphs; k++)
 638                         (*lpGlyphs)[glyph_i+k] = run_glyphs[k];
 639                     glyph_i += cOutGlyphs;
 640                 }
 641             }
 642         }
 643
 644         done += i;
 645     }
 646     if (cGlyphs)
 647         *cGlyphs = glyph_i;
 648
 649     HeapFree(GetProcessHeap(), 0, chartype);
 650     HeapFree(GetProcessHeap(), 0, levels);
 651     HeapFree(GetProcessHeap(), 0, pItems);
 652     HeapFree(GetProcessHeap(), 0, run_glyphs);
 653     HeapFree(GetProcessHeap(), 0, pwLogClust);
 654     HeapFree(GetProcessHeap(), 0, psva);
 655     ScriptFreeCache(&psc);
 656     return TRUE;
 657 }