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