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