2 * GDI BiDirectional handling
4 * Copyright 2003 Shachar Shemesh
5 * Copyright 2007 Maarten Lankhorst
6 * Copyright 2010 CodeWeavers, Aric Stewart
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.
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.
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
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"
26 * -- Copyright (C) 1999-2005, ASMUS, Inc.
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
52 #include "wine/unicode.h"
53 #include "wine/debug.h"
54 #include "gdi_private.h"
56 WINE_DEFAULT_DEBUG_CHANNEL(bidi
);
58 /* HELPER FUNCTIONS AND DECLARATIONS */
60 #define odd(x) ((x) & 1)
62 /*------------------------------------------------------------------------
63 Bidirectional Character Types
65 as defined by the Unicode Bidirectional Algorithm Table 3-7.
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 ------------------------------------------------------------------------*/
76 /* ON MUST be zero, code relies on ON = N = 0 */
77 ON
= 0, /* Other Neutral */
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 %) */
89 BN
, /* Boundary neutral (type of RLE etc after explicit levels) */
92 S
, /* Segment Separator (TAB) // used only in L1 */
93 WS
, /* White space // used only in L1 */
94 B
, /* Paragraph Separator (aka as PS) */
96 /* types for explicit controls */
97 RLO
, /* these are used only in X1-X9 */
103 /* resolved types, also resolved directions */
104 N
= ON
, /* alias, where ON, WS and S are treated the same */
107 /* HELPER FUNCTIONS */
109 /* Convert the libwine information to the direction enum */
110 static void classify(LPCWSTR lpString
, WORD
*chartype
, DWORD uCount
)
112 static const enum directions dir_map
[16] =
114 L
, /* unassigned defaults to L */
129 PDF
/* also LRE, LRO, RLE, RLO */
134 for (i
= 0; i
< uCount
; ++i
)
136 chartype
[i
] = dir_map
[get_char_typeW(lpString
[i
]) >> 12];
137 if (chartype
[i
] == PDF
)
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;
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
)
156 for (; i
>= iStart
- cval
; i
--)
162 /* THE PARAGRAPH LEVEL */
164 /*------------------------------------------------------------------------
165 Function: resolveParagraphs
167 Resolves the input strings into blocks over which the algorithm
170 Implements Rule P1 of the Unicode Bidi Algorithm
175 Output: revised character count
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.
182 ------------------------------------------------------------------------*/
184 static int resolveParagraphs(WORD
*types
, int cch
)
186 /* skip characters not of type B */
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
)
196 /*------------------------------------------------------------------------
197 Function: resolveLines
199 Breaks a paragraph into lines
201 Input: Character count
202 In/Out: Array of characters
203 Array of line break flags
205 Returns the count of characters on the first line
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
)
214 /* skip characters not of type LS */
216 for(; ich
< cch
; ich
++)
218 if (pszInput
[ich
] == (WCHAR
)'\n' || (pbrk
&& pbrk
[ich
]))
228 /*------------------------------------------------------------------------
229 Function: resolveWhiteSpace
231 Resolves levels for WS and S
232 Implements rule L1 of the Unicode bidi Algorithm.
234 Input: Base embedding level
236 Array of direction classes (for one line of text)
238 In/Out: Array of embedding levels (for one line of text)
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
)
248 BYTE oldlevel
= baselevel
;
251 for (; ich
< cch
; ich
++)
256 cchrun
= 0; /* any other character breaks the run */
268 plevel
[ich
] = oldlevel
;
274 /* reset levels for WS before eot */
275 SetDeferredRun(plevel
, cchrun
, ich
, baselevel
);
277 plevel
[ich
] = baselevel
;
280 oldlevel
= plevel
[ich
];
282 /* reset level before eot */
283 SetDeferredRun(plevel
, cchrun
, ich
, baselevel
);
286 /*------------------------------------------------------------------------
289 Implements the Line-by-Line phases of the Unicode Bidi Algorithm
291 Input: Count of characters
294 Array of character directions
297 ------------------------------------------------------------------------*/
298 static void BidiLines(int baselevel
, LPWSTR pszOutLine
, LPCWSTR pszLine
, WORD
* pclsLine
,
299 BYTE
* plevelLine
, int cchPara
, BOOL
* pbrk
)
305 run
= HeapAlloc(GetProcessHeap(), 0, cchPara
* sizeof(int));
308 WARN("Out of memory\n");
314 /* break lines at LS */
315 cchLine
= resolveLines(pszLine
, pbrk
, cchPara
);
317 /* resolve whitespace */
318 resolveWhitespace(baselevel
, pclsLine
, plevelLine
, cchLine
);
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
];
330 plevelLine
+= cchLine
;
331 pbrk
+= pbrk
? cchLine
: 0;
338 HeapFree(GetProcessHeap(), 0, run
);
341 /*************************************************************
344 * Returns TRUE if reordering was required and done.
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 */
361 unsigned i
, done
, glyph_i
;
365 SCRIPT_CONTROL Control
;
369 SCRIPT_CACHE psc
= NULL
;
370 WORD
*run_glyphs
= NULL
;
371 WORD
*pwLogClust
= NULL
;
372 SCRIPT_VISATTR
*psva
= NULL
;
373 DWORD cMaxGlyphs
= 0;
374 BOOL doGlyphs
= TRUE
;
376 TRACE("%s, %d, 0x%08x lpOutString=%p, lpOrder=%p\n",
377 debugstr_wn(lpString
, uCount
), uCount
, dwFlags
,
378 lpOutString
, lpOrder
);
380 memset(&Control
, 0, sizeof(Control
));
381 memset(&State
, 0, sizeof(State
));
385 if (!(dwFlags
& GCP_REORDER
))
387 FIXME("Asked to reorder without reorder flag set\n");
391 if (lpOutString
&& uCountOut
< uCount
)
393 FIXME("lpOutString too small\n");
397 chartype
= HeapAlloc(GetProcessHeap(), 0, uCount
* sizeof(WORD
));
400 WARN("Out of memory\n");
405 memcpy(lpOutString
, lpString
, uCount
* sizeof(WCHAR
));
407 /* Verify reordering will be required */
408 if ((WINE_GCPW_FORCE_RTL
== (dwWineGCP_Flags
&WINE_GCPW_DIR_MASK
)) ||
409 ((dwWineGCP_Flags
&WINE_GCPW_DIR_MASK
) == WINE_GCPW_LOOSE_RTL
))
410 State
.uBidiLevel
= 1;
414 classify(lpString
, chartype
, uCount
);
415 for (i
= 0; i
< uCount
; i
++)
427 HeapFree(GetProcessHeap(), 0, chartype
);
430 for (i
= 0; i
< uCount
; i
++)
437 levels
= HeapAlloc(GetProcessHeap(), 0, uCount
* sizeof(BYTE
));
440 WARN("Out of memory\n");
441 HeapFree(GetProcessHeap(), 0, chartype
);
446 pItems
= HeapAlloc(GetProcessHeap(),0, maxItems
* sizeof(SCRIPT_ITEM
));
449 WARN("Out of memory\n");
450 HeapFree(GetProcessHeap(), 0, chartype
);
451 HeapFree(GetProcessHeap(), 0, levels
);
457 cMaxGlyphs
= 1.5 * uCount
+ 16;
458 run_glyphs
= HeapAlloc(GetProcessHeap(),0,sizeof(WORD
) * cMaxGlyphs
);
461 WARN("Out of memory\n");
462 HeapFree(GetProcessHeap(), 0, chartype
);
463 HeapFree(GetProcessHeap(), 0, levels
);
464 HeapFree(GetProcessHeap(), 0, pItems
);
467 pwLogClust
= HeapAlloc(GetProcessHeap(),0,sizeof(WORD
) * uCount
);
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
);
477 psva
= HeapAlloc(GetProcessHeap(),0,sizeof(SCRIPT_VISATTR
) * uCount
);
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 HeapFree(GetProcessHeap(), 0, pwLogClust
);
492 while (done
< uCount
)
495 classify(lpString
+ done
, chartype
, uCount
- done
);
496 /* limit text to first block */
497 i
= resolveParagraphs(chartype
, uCount
- done
);
498 for (j
= 0; j
< i
; ++j
)
504 case ON
: chartype
[j
] = N
;
508 if ((dwWineGCP_Flags
&WINE_GCPW_DIR_MASK
) == WINE_GCPW_LOOSE_RTL
)
509 State
.uBidiLevel
= 1;
510 else if ((dwWineGCP_Flags
&WINE_GCPW_DIR_MASK
) == WINE_GCPW_LOOSE_LTR
)
511 State
.uBidiLevel
= 0;
513 if (dwWineGCP_Flags
& WINE_GCPW_LOOSE_MASK
)
515 for (j
= 0; j
< i
; ++j
)
516 if (chartype
[j
] == L
)
518 State
.uBidiLevel
= 0;
521 else if (chartype
[j
] == R
|| chartype
[j
] == AL
)
523 State
.uBidiLevel
= 1;
528 res
= ScriptItemize(lpString
+ done
, i
, maxItems
, &Control
, &State
, pItems
, &nItems
);
529 while (res
== E_OUTOFMEMORY
)
531 maxItems
= maxItems
* 2;
532 pItems
= HeapReAlloc(GetProcessHeap(), 0, pItems
, sizeof(SCRIPT_ITEM
) * maxItems
);
535 WARN("Out of memory\n");
536 HeapFree(GetProcessHeap(), 0, chartype
);
537 HeapFree(GetProcessHeap(), 0, levels
);
540 res
= ScriptItemize(lpString
+ done
, i
, maxItems
, &Control
, &State
, pItems
, &nItems
);
543 if (lpOutString
|| lpOrder
)
544 for (j
= 0; j
< nItems
; j
++)
547 for (k
= pItems
[j
].iCharPos
; k
< pItems
[j
+1].iCharPos
; k
++)
548 levels
[k
] = pItems
[j
].a
.s
.uBidiLevel
;
553 /* assign directional types again, but for WS, S this time */
554 classify(lpString
+ done
, chartype
, i
);
556 BidiLines(State
.uBidiLevel
, lpOutString
+ done
, lpString
+ done
,
557 chartype
, levels
, i
, 0);
563 for (j
= lastgood
= 0; j
< i
; ++j
)
564 if (levels
[j
] != levels
[lastgood
])
567 if (odd(levels
[lastgood
]))
568 for (k
= j
; k
>= lastgood
; --k
)
569 lpOrder
[done
+ k
] = done
+ j
- k
;
571 for (k
= lastgood
; k
<= j
; ++k
)
572 lpOrder
[done
+ k
] = done
+ k
;
575 if (odd(levels
[lastgood
]))
576 for (k
= j
- 1; k
>= lastgood
; --k
)
577 lpOrder
[done
+ k
] = done
+ j
- 1 - k
;
579 for (k
= lastgood
; k
< j
; ++k
)
580 lpOrder
[done
+ k
] = done
+ k
;
583 if (lpGlyphs
&& doGlyphs
)
586 BYTE runOrder
[maxItems
];
587 int visOrder
[maxItems
];
588 SCRIPT_ITEM
*curItem
;
590 for (j
= 0; j
< nItems
; j
++)
591 runOrder
[j
] = pItems
[j
].a
.s
.uBidiLevel
;
593 ScriptLayout(nItems
, runOrder
, visOrder
, NULL
);
595 for (j
= 0; j
< nItems
; j
++)
598 int cChars
,cOutGlyphs
;
599 curItem
= &pItems
[visOrder
[j
]];
601 cChars
= pItems
[visOrder
[j
]+1].iCharPos
- curItem
->iCharPos
;
603 res
= ScriptShape(hDC
, &psc
, lpString
+ done
+ curItem
->iCharPos
, cChars
, cMaxGlyphs
, &curItem
->a
, run_glyphs
, pwLogClust
, psva
, &cOutGlyphs
);
604 while (res
== E_OUTOFMEMORY
)
607 run_glyphs
= HeapReAlloc(GetProcessHeap(), 0, run_glyphs
, sizeof(WORD
) * cMaxGlyphs
);
610 WARN("Out of memory\n");
611 HeapFree(GetProcessHeap(), 0, chartype
);
612 HeapFree(GetProcessHeap(), 0, levels
);
613 HeapFree(GetProcessHeap(), 0, pItems
);
614 HeapFree(GetProcessHeap(), 0, psva
);
615 HeapFree(GetProcessHeap(), 0, pwLogClust
);
616 HeapFree(GetProcessHeap(), 0, *lpGlyphs
);
617 ScriptFreeCache(&psc
);
621 res
= ScriptShape(hDC
, &psc
, lpString
+ done
+ curItem
->iCharPos
, cChars
, cMaxGlyphs
, &curItem
->a
, run_glyphs
, pwLogClust
, psva
, &cOutGlyphs
);
625 if (res
== USP_E_SCRIPT_NOT_IN_FONT
)
626 TRACE("Unable to shape with currently selected font\n");
628 FIXME("Unable to shape string (%x)\n",res
);
631 HeapFree(GetProcessHeap(), 0, *lpGlyphs
);
637 *lpGlyphs
= HeapReAlloc(GetProcessHeap(), 0, *lpGlyphs
, sizeof(WORD
) * (glyph_i
+ cOutGlyphs
));
639 *lpGlyphs
= HeapAlloc(GetProcessHeap(), 0, sizeof(WORD
) * (glyph_i
+ cOutGlyphs
));
640 for (k
= 0; k
< cOutGlyphs
; k
++)
641 (*lpGlyphs
)[glyph_i
+k
] = run_glyphs
[k
];
642 glyph_i
+= cOutGlyphs
;
652 HeapFree(GetProcessHeap(), 0, chartype
);
653 HeapFree(GetProcessHeap(), 0, levels
);
654 HeapFree(GetProcessHeap(), 0, pItems
);
655 HeapFree(GetProcessHeap(), 0, run_glyphs
);
656 HeapFree(GetProcessHeap(), 0, pwLogClust
);
657 HeapFree(GetProcessHeap(), 0, psva
);
658 ScriptFreeCache(&psc
);