git.oblomov.eu Git - wine/blob - 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 /* DISPLAY OPTIONS */
 287 /*-----------------------------------------------------------------------
 288    Function:    mirror
 289
 290     Crudely implements rule L4 of the Unicode Bidirectional Algorithm
 291     Demonstrate mirrored brackets, braces and parens
 292
 293
 294     Input:    Array of levels
 295             Count of characters
 296
 297     In/Out:    Array of characters (should be array of glyph ids)
 298
 299     Note;
 300     A full implementation would need to substitute mirrored glyphs even
 301     for characters that are not paired (e.g. integral sign).
 302 -----------------------------------------------------------------------*/
 303 static void mirror(LPWSTR pszInput, const BYTE* plevel, int cch)
 304 {
 305     static int warn_once;
 306     int i;
 307
 308     for (i = 0; i < cch; ++i)
 309     {
 310         if (!odd(plevel[i]))
 311             continue;
 312         /* This needs the data from http://www.unicode.org/Public/UNIDATA/BidiMirroring.txt */
 313         if (!warn_once++)
 314             FIXME("stub: mirroring of characters not yet implemented\n");
 315         break;
 316     }
 317 }
 318
 319 /*------------------------------------------------------------------------
 320     Function: BidiLines
 321
 322     Implements the Line-by-Line phases of the Unicode Bidi Algorithm
 323
 324       Input:     Count of characters
 325              flag whether to mirror
 326
 327     Inp/Out: Input text
 328              Array of character directions
 329              Array of levels
 330
 331 ------------------------------------------------------------------------*/
 332 static void BidiLines(int baselevel, LPWSTR pszOutLine, LPCWSTR pszLine, WORD * pclsLine,
 333                       BYTE * plevelLine, int cchPara, int fMirror, BOOL * pbrk)
 334 {
 335     int cchLine = 0;
 336     int done = 0;
 337     int *run;
 338
 339     run = HeapAlloc(GetProcessHeap(), 0, cchPara * sizeof(int));
 340     if (!run)
 341     {
 342         WARN("Out of memory\n");
 343         return;
 344     }
 345
 346     do
 347     {
 348         /* break lines at LS */
 349         cchLine = resolveLines(pszLine, pbrk, cchPara);
 350
 351         /* resolve whitespace */
 352         resolveWhitespace(baselevel, pclsLine, plevelLine, cchLine);
 353
 354         if (pszOutLine)
 355         {
 356             int i;
 357             if (fMirror)
 358                 mirror(pszOutLine, plevelLine, cchLine);
 359
 360             /* reorder each line in place */
 361             ScriptLayout(cchLine, plevelLine, run, NULL);
 362             for (i = 0; i < cchLine; i++)
 363                 pszOutLine[done+run[i]] = pszLine[i];
 364         }
 365
 366         pszLine += cchLine;
 367         plevelLine += cchLine;
 368         pbrk += pbrk ? cchLine : 0;
 369         pclsLine += cchLine;
 370         cchPara -= cchLine;
 371         done += cchLine;
 372
 373     } while (cchPara);
 374
 375     HeapFree(GetProcessHeap(), 0, run);
 376 }
 377
 378 /*************************************************************
 379  *    BIDI_Reorder
 380  */
 381 BOOL BIDI_Reorder(
 382                 LPCWSTR lpString,       /* [in] The string for which information is to be returned */
 383                 INT uCount,     /* [in] Number of WCHARs in string. */
 384                 DWORD dwFlags,  /* [in] GetCharacterPlacement compatible flags specifying how to process the string */
 385                 DWORD dwWineGCP_Flags,       /* [in] Wine internal flags - Force paragraph direction */
 386                 LPWSTR lpOutString, /* [out] Reordered string */
 387                 INT uCountOut,  /* [in] Size of output buffer */
 388                 UINT *lpOrder /* [out] Logical -> Visual order map */
 389     )
 390 {
 391     WORD *chartype;
 392     BYTE *levels;
 393     unsigned i, done;
 394
 395     int maxItems;
 396     int nItems;
 397     SCRIPT_CONTROL Control;
 398     SCRIPT_STATE State;
 399     SCRIPT_ITEM *pItems;
 400     HRESULT res;
 401
 402     TRACE("%s, %d, 0x%08x lpOutString=%p, lpOrder=%p\n",
 403           debugstr_wn(lpString, uCount), uCount, dwFlags,
 404           lpOutString, lpOrder);
 405
 406     memset(&Control, 0, sizeof(Control));
 407     memset(&State, 0, sizeof(State));
 408
 409     if (!(dwFlags & GCP_REORDER))
 410     {
 411         FIXME("Asked to reorder without reorder flag set\n");
 412         return FALSE;
 413     }
 414
 415     if (uCountOut < uCount)
 416     {
 417         FIXME("lpOutString too small\n");
 418         return FALSE;
 419     }
 420
 421     chartype = HeapAlloc(GetProcessHeap(), 0, uCount * sizeof(WORD));
 422     if (!chartype)
 423     {
 424         WARN("Out of memory\n");
 425         return FALSE;
 426     }
 427
 428     if (lpOutString)
 429         memcpy(lpOutString, lpString, uCount * sizeof(WCHAR));
 430
 431     /* Verify reordering will be required */
 432     if ((WINE_GCPW_FORCE_RTL == (dwWineGCP_Flags&WINE_GCPW_DIR_MASK)) ||
 433         ((dwWineGCP_Flags&WINE_GCPW_DIR_MASK) == WINE_GCPW_LOOSE_RTL))
 434         State.uBidiLevel = 1;
 435     else
 436     {
 437         done = 1;
 438         classify(lpString, chartype, uCount);
 439         for (i = 0; i < uCount; i++)
 440             switch (chartype[i])
 441             {
 442                 case R:
 443                 case AL:
 444                 case RLE:
 445                 case RLO:
 446                     done = 0;
 447                     break;
 448             }
 449         if (done)
 450         {
 451             HeapFree(GetProcessHeap(), 0, chartype);
 452             return TRUE;
 453         }
 454     }
 455
 456     levels = HeapAlloc(GetProcessHeap(), 0, uCount * sizeof(BYTE));
 457     if (!levels)
 458     {
 459         WARN("Out of memory\n");
 460         HeapFree(GetProcessHeap(), 0, chartype);
 461         return FALSE;
 462     }
 463
 464     maxItems = 5;
 465     pItems = HeapAlloc(GetProcessHeap(),0, maxItems * sizeof(SCRIPT_ITEM));
 466     if (!pItems)
 467     {
 468         WARN("Out of memory\n");
 469         HeapFree(GetProcessHeap(), 0, chartype);
 470         HeapFree(GetProcessHeap(), 0, levels);
 471         return FALSE;
 472     }
 473
 474     done = 0;
 475     while (done < uCount)
 476     {
 477         unsigned j;
 478         classify(lpString + done, chartype, uCount - done);
 479         /* limit text to first block */
 480         i = resolveParagraphs(chartype, uCount - done);
 481         for (j = 0; j < i; ++j)
 482             switch(chartype[j])
 483             {
 484                 case B:
 485                 case S:
 486                 case WS:
 487                 case ON: chartype[j] = N;
 488                 default: continue;
 489             }
 490
 491         if ((dwWineGCP_Flags&WINE_GCPW_DIR_MASK) == WINE_GCPW_LOOSE_RTL)
 492             State.uBidiLevel = 1;
 493         else if ((dwWineGCP_Flags&WINE_GCPW_DIR_MASK) == WINE_GCPW_LOOSE_LTR)
 494             State.uBidiLevel = 0;
 495
 496         if (dwWineGCP_Flags & WINE_GCPW_LOOSE_MASK)
 497         {
 498             for (j = 0; j < i; ++j)
 499                 if (chartype[j] == L)
 500                 {
 501                     State.uBidiLevel = 0;
 502                     break;
 503                 }
 504                 else if (chartype[j] == R || chartype[j] == AL)
 505                 {
 506                     State.uBidiLevel = 1;
 507                     break;
 508                 }
 509         }
 510
 511         res = ScriptItemize(lpString + done, i, maxItems, &Control, &State, pItems, &nItems);
 512         while (res == E_OUTOFMEMORY)
 513         {
 514             maxItems = maxItems * 2;
 515             pItems = HeapReAlloc(GetProcessHeap(), 0, pItems, sizeof(SCRIPT_ITEM) * maxItems);
 516             if (!pItems)
 517             {
 518                 WARN("Out of memory\n");
 519                 HeapFree(GetProcessHeap(), 0, chartype);
 520                 HeapFree(GetProcessHeap(), 0, levels);
 521                 return FALSE;
 522             }
 523             res = ScriptItemize(lpString + done, i, maxItems, &Control, &State, pItems, &nItems);
 524         }
 525
 526         for (j = 0; j < nItems; j++)
 527         {
 528             int k;
 529             for (k = pItems[j].iCharPos; k < pItems[j+1].iCharPos; k++)
 530                 levels[k] = pItems[j].a.s.uBidiLevel;
 531         }
 532
 533         /* assign directional types again, but for WS, S this time */
 534         classify(lpString + done, chartype, i);
 535
 536         BidiLines(State.uBidiLevel, lpOutString ? lpOutString + done : NULL, lpString + done,
 537                     chartype, levels, i, !(dwFlags & GCP_SYMSWAPOFF), 0);
 538
 539
 540         if (lpOrder)
 541         {
 542             int k, lastgood;
 543             for (j = lastgood = 0; j < i; ++j)
 544                 if (levels[j] != levels[lastgood])
 545                 {
 546                     --j;
 547                     if (odd(levels[lastgood]))
 548                         for (k = j; k >= lastgood; --k)
 549                             lpOrder[done + k] = done + j - k;
 550                     else
 551                         for (k = lastgood; k <= j; ++k)
 552                             lpOrder[done + k] = done + k;
 553                     lastgood = ++j;
 554                 }
 555             if (odd(levels[lastgood]))
 556                 for (k = j - 1; k >= lastgood; --k)
 557                     lpOrder[done + k] = done + j - 1 - k;
 558             else
 559                 for (k = lastgood; k < j; ++k)
 560                     lpOrder[done + k] = done + k;
 561         }
 562         done += i;
 563     }
 564
 565     HeapFree(GetProcessHeap(), 0, chartype);
 566     HeapFree(GetProcessHeap(), 0, levels);
 567     HeapFree(GetProcessHeap(), 0, pItems);
 568     return TRUE;
 569 }