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: Array of line break flags
202 Character count
203 In/Out: Array of characters
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, const 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 Array of character directions
293
294 Inp/Out: Input text
295 Array of levels
296
297 ------------------------------------------------------------------------*/
298 static void BidiLines(int baselevel, LPWSTR pszOutLine, LPCWSTR pszLine, const WORD * pclsLine,
299 BYTE * plevelLine, int cchPara, const 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, NULL, run);
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 BOOL is_complex;
363
364 int maxItems;
365 int nItems;
366 SCRIPT_CONTROL Control;
367 SCRIPT_STATE State;
368 SCRIPT_ITEM *pItems;
369 HRESULT res;
370 SCRIPT_CACHE psc = NULL;
371 WORD *run_glyphs = NULL;
372 WORD *pwLogClust = NULL;
373 SCRIPT_VISATTR *psva = NULL;
374 DWORD cMaxGlyphs = 0;
375 BOOL doGlyphs = TRUE;
376
377 TRACE("%s, %d, 0x%08x lpOutString=%p, lpOrder=%p\n",
378 debugstr_wn(lpString, uCount), uCount, dwFlags,
379 lpOutString, lpOrder);
380
381 memset(&Control, 0, sizeof(Control));
382 memset(&State, 0, sizeof(State));
383 if (lpGlyphs)
384 *lpGlyphs = NULL;
385
386 if (!(dwFlags & GCP_REORDER))
387 {
388 FIXME("Asked to reorder without reorder flag set\n");
389 return FALSE;
390 }
391
392 if (lpOutString && uCountOut < uCount)
393 {
394 FIXME("lpOutString too small\n");
395 return FALSE;
396 }
397
398 chartype = HeapAlloc(GetProcessHeap(), 0, uCount * sizeof(WORD));
399 if (!chartype)
400 {
401 WARN("Out of memory\n");
402 return FALSE;
403 }
404
405 if (lpOutString)
406 memcpy(lpOutString, lpString, uCount * sizeof(WCHAR));
407
408 is_complex = FALSE;
409 for (i = 0; i < uCount && !is_complex; i++)
410 {
411 if ((lpString[i] >= 0x900 && lpString[i] <= 0xfff) ||
412 (lpString[i] >= 0x1cd0 && lpString[i] <= 0x1cff) ||
413 (lpString[i] >= 0xa840 && lpString[i] <= 0xa8ff))
414 is_complex = TRUE;
415 }
416
417 /* Verify reordering will be required */
418 if ((WINE_GCPW_FORCE_RTL == (dwWineGCP_Flags&WINE_GCPW_DIR_MASK)) ||
419 ((dwWineGCP_Flags&WINE_GCPW_DIR_MASK) == WINE_GCPW_LOOSE_RTL))
420 State.uBidiLevel = 1;
421 else if (!is_complex)
422 {
423 done = 1;
424 classify(lpString, chartype, uCount);
425 for (i = 0; i < uCount; i++)
426 switch (chartype[i])
427 {
428 case R:
429 case AL:
430 case RLE:
431 case RLO:
432 done = 0;
433 break;
434 }
435 if (done)
436 {
437 HeapFree(GetProcessHeap(), 0, chartype);
438 if (lpOrder)
439 {
440 for (i = 0; i < uCount; i++)
441 lpOrder[i] = i;
442 }
443 return TRUE;
444 }
445 }
446
447 levels = HeapAlloc(GetProcessHeap(), 0, uCount * sizeof(BYTE));
448 if (!levels)
449 {
450 WARN("Out of memory\n");
451 HeapFree(GetProcessHeap(), 0, chartype);
452 return FALSE;
453 }
454
455 maxItems = 5;
456 pItems = HeapAlloc(GetProcessHeap(),0, maxItems * sizeof(SCRIPT_ITEM));
457 if (!pItems)
458 {
459 WARN("Out of memory\n");
460 HeapFree(GetProcessHeap(), 0, chartype);
461 HeapFree(GetProcessHeap(), 0, levels);
462 return FALSE;
463 }
464
465 if (lpGlyphs)
466 {
467 cMaxGlyphs = 1.5 * uCount + 16;
468 run_glyphs = HeapAlloc(GetProcessHeap(),0,sizeof(WORD) * cMaxGlyphs);
469 if (!run_glyphs)
470 {
471 WARN("Out of memory\n");
472 HeapFree(GetProcessHeap(), 0, chartype);
473 HeapFree(GetProcessHeap(), 0, levels);
474 HeapFree(GetProcessHeap(), 0, pItems);
475 return FALSE;
476 }
477 pwLogClust = HeapAlloc(GetProcessHeap(),0,sizeof(WORD) * uCount);
478 if (!pwLogClust)
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 return FALSE;
486 }
487 psva = HeapAlloc(GetProcessHeap(),0,sizeof(SCRIPT_VISATTR) * uCount);
488 if (!psva)
489 {
490 WARN("Out of memory\n");
491 HeapFree(GetProcessHeap(), 0, chartype);
492 HeapFree(GetProcessHeap(), 0, levels);
493 HeapFree(GetProcessHeap(), 0, pItems);
494 HeapFree(GetProcessHeap(), 0, run_glyphs);
495 HeapFree(GetProcessHeap(), 0, pwLogClust);
496 return FALSE;
497 }
498 }
499
500 done = 0;
501 glyph_i = 0;
502 while (done < uCount)
503 {
504 unsigned j;
505 classify(lpString + done, chartype, uCount - done);
506 /* limit text to first block */
507 i = resolveParagraphs(chartype, uCount - done);
508 for (j = 0; j < i; ++j)
509 switch(chartype[j])
510 {
511 case B:
512 case S:
513 case WS:
514 case ON: chartype[j] = N;
515 default: continue;
516 }
517
518 if ((dwWineGCP_Flags&WINE_GCPW_DIR_MASK) == WINE_GCPW_LOOSE_RTL)
519 State.uBidiLevel = 1;
520 else if ((dwWineGCP_Flags&WINE_GCPW_DIR_MASK) == WINE_GCPW_LOOSE_LTR)
521 State.uBidiLevel = 0;
522
523 if (dwWineGCP_Flags & WINE_GCPW_LOOSE_MASK)
524 {
525 for (j = 0; j < i; ++j)
526 if (chartype[j] == L)
527 {
528 State.uBidiLevel = 0;
529 break;
530 }
531 else if (chartype[j] == R || chartype[j] == AL)
532 {
533 State.uBidiLevel = 1;
534 break;
535 }
536 }
537
538 res = ScriptItemize(lpString + done, i, maxItems, &Control, &State, pItems, &nItems);
539 while (res == E_OUTOFMEMORY)
540 {
541 maxItems = maxItems * 2;
542 pItems = HeapReAlloc(GetProcessHeap(), 0, pItems, sizeof(SCRIPT_ITEM) * maxItems);
543 if (!pItems)
544 {
545 WARN("Out of memory\n");
546 HeapFree(GetProcessHeap(), 0, chartype);
547 HeapFree(GetProcessHeap(), 0, levels);
548 return FALSE;
549 }
550 res = ScriptItemize(lpString + done, i, maxItems, &Control, &State, pItems, &nItems);
551 }
552
553 if (lpOutString || lpOrder)
554 for (j = 0; j < nItems; j++)
555 {
556 int k;
557 for (k = pItems[j].iCharPos; k < pItems[j+1].iCharPos; k++)
558 levels[k] = pItems[j].a.s.uBidiLevel;
559 }
560
561 if (lpOutString)
562 {
563 /* assign directional types again, but for WS, S this time */
564 classify(lpString + done, chartype, i);
565
566 BidiLines(State.uBidiLevel, lpOutString + done, lpString + done,
567 chartype, levels, i, 0);
568 }
569
570 if (lpOrder)
571 {
572 int k, lastgood;
573 for (j = lastgood = 0; j < i; ++j)
574 if (levels[j] != levels[lastgood])
575 {
576 --j;
577 if (odd(levels[lastgood]))
578 for (k = j; k >= lastgood; --k)
579 lpOrder[done + k] = done + j - k;
580 else
581 for (k = lastgood; k <= j; ++k)
582 lpOrder[done + k] = done + k;
583 lastgood = ++j;
584 }
585 if (odd(levels[lastgood]))
586 for (k = j - 1; k >= lastgood; --k)
587 lpOrder[done + k] = done + j - 1 - k;
588 else
589 for (k = lastgood; k < j; ++k)
590 lpOrder[done + k] = done + k;
591 }
592
593 if (lpGlyphs && doGlyphs)
594 {
595 BYTE runOrder[maxItems];
596 int visOrder[maxItems];
597 SCRIPT_ITEM *curItem;
598
599 for (j = 0; j < nItems; j++)
600 runOrder[j] = pItems[j].a.s.uBidiLevel;
601
602 ScriptLayout(nItems, runOrder, visOrder, NULL);
603
604 for (j = 0; j < nItems; j++)
605 {
606 int k;
607 int cChars,cOutGlyphs;
608 curItem = &pItems[visOrder[j]];
609
610 cChars = pItems[visOrder[j]+1].iCharPos - curItem->iCharPos;
611
612 res = ScriptShape(hDC, &psc, lpString + done + curItem->iCharPos, cChars, cMaxGlyphs, &curItem->a, run_glyphs, pwLogClust, psva, &cOutGlyphs);
613 while (res == E_OUTOFMEMORY)
614 {
615 cMaxGlyphs *= 2;
616 run_glyphs = HeapReAlloc(GetProcessHeap(), 0, run_glyphs, sizeof(WORD) * cMaxGlyphs);
617 if (!run_glyphs)
618 {
619 WARN("Out of memory\n");
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 }
655
656 done += i;
657 }
658 if (cGlyphs)
659 *cGlyphs = glyph_i;
660
661 HeapFree(GetProcessHeap(), 0, chartype);
662 HeapFree(GetProcessHeap(), 0, levels);
663 HeapFree(GetProcessHeap(), 0, pItems);
664 HeapFree(GetProcessHeap(), 0, run_glyphs);
665 HeapFree(GetProcessHeap(), 0, pwLogClust);
666 HeapFree(GetProcessHeap(), 0, psva);
667 ScriptFreeCache(&psc);
668 return TRUE;
669 }
670
This page was automatically generated by the
LXR engine.
Visit the LXR main site for more
information.