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