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/debug.h"
53 #include "gdi_private.h"
55 WINE_DEFAULT_DEBUG_CHANNEL(bidi
);
57 /* HELPER FUNCTIONS AND DECLARATIONS */
59 #define odd(x) ((x) & 1)
61 /*------------------------------------------------------------------------
62 Bidirectional Character Types
64 as defined by the Unicode Bidirectional Algorithm Table 3-7.
68 The list of bidirectional character types here is not grouped the
69 same way as the table 3-7, since the numberic values for the types
70 are chosen to keep the state and action tables compact.
71 ------------------------------------------------------------------------*/
75 /* ON MUST be zero, code relies on ON = N = 0 */
76 ON
= 0, /* Other Neutral */
79 AN
, /* Arabic Number */
80 EN
, /* European Number */
81 AL
, /* Arabic Letter (Right-to-left) */
82 NSM
, /* Non-spacing Mark */
83 CS
, /* Common Separator */
84 ES
, /* European Separator */
85 ET
, /* European Terminator (post/prefix e.g. $ and %) */
88 BN
, /* Boundary neutral (type of RLE etc after explicit levels) */
91 S
, /* Segment Separator (TAB) // used only in L1 */
92 WS
, /* White space // used only in L1 */
93 B
, /* Paragraph Separator (aka as PS) */
95 /* types for explicit controls */
96 RLO
, /* these are used only in X1-X9 */
102 /* resolved types, also resolved directions */
103 N
= ON
, /* alias, where ON, WS and S are treated the same */
106 /* HELPER FUNCTIONS */
108 /* grep -r ';BN;' data.txt | grep -v [0-9A-F][0-9A-F][0-9A-F][0-9A-F][0-9A-F] | sed -e s@\;.*@@ -e s/^..../0x\&,\ / | xargs echo */
109 static const WCHAR BNs
[] = {
110 0x0000, 0x0001, 0x0002, 0x0003, 0x0004, 0x0005, 0x0006, 0x0007, 0x0008,
111 0x000E, 0x000F, 0x0010, 0x0011, 0x0012, 0x0013, 0x0014, 0x0015, 0x0016,
112 0x0017, 0x0018, 0x0019, 0x001A, 0x001B, 0x007F, 0x0080, 0x0081, 0x0082,
113 0x0083, 0x0084, 0x0086, 0x0087, 0x0088, 0x0089, 0x008A, 0x008B, 0x008C,
114 0x008D, 0x008E, 0x008F, 0x0090, 0x0091, 0x0092, 0x0093, 0x0094, 0x0095,
115 0x0096, 0x0097, 0x0098, 0x0099, 0x009A, 0x009B, 0x009C, 0x009D, 0x009E,
116 0x009F, 0x00AD, 0x070F, 0x200B, 0x200C, 0x200D, 0x2060, 0x2061, 0x2062,
117 0x2063, 0x206A, 0x206B, 0x206C, 0x206D, 0x206E, 0x206F, 0xFEFF
120 /* Idem, but with ';R;' instead of ';BN;' */
121 static const WCHAR Rs
[] = {
122 0x05BE, 0x05C0, 0x05C3, 0x05C6, 0x05D0, 0x05D1, 0x05D2, 0x05D3, 0x05D4,
123 0x05D5, 0x05D6, 0x05D7, 0x05D8, 0x05D9, 0x05DA, 0x05DB, 0x05DC, 0x05DD,
124 0x05DE, 0x05DF, 0x05E0, 0x05E1, 0x05E2, 0x05E3, 0x05E4, 0x05E5, 0x05E6,
125 0x05E7, 0x05E8, 0x05E9, 0x05EA, 0x05F0, 0x05F1, 0x05F2, 0x05F3, 0x05F4,
126 0x07C0, 0x07C1, 0x07C2, 0x07C3, 0x07C4, 0x07C5, 0x07C6, 0x07C7, 0x07C8,
127 0x07C9, 0x07CA, 0x07CB, 0x07CC, 0x07CD, 0x07CE, 0x07CF, 0x07D0, 0x07D1,
128 0x07D2, 0x07D3, 0x07D4, 0x07D5, 0x07D6, 0x07D7, 0x07D8, 0x07D9, 0x07DA,
129 0x07DB, 0x07DC, 0x07DD, 0x07DE, 0x07DF, 0x07E0, 0x07E1, 0x07E2, 0x07E3,
130 0x07E4, 0x07E5, 0x07E6, 0x07E7, 0x07E8, 0x07E9, 0x07EA, 0x07F4, 0x07F5,
131 0x07FA, 0x200F, 0xFB1D, 0xFB1F, 0xFB20, 0xFB21, 0xFB22, 0xFB23, 0xFB24,
132 0xFB25, 0xFB26, 0xFB27, 0xFB28, 0xFB2A, 0xFB2B, 0xFB2C, 0xFB2D, 0xFB2E,
133 0xFB2F, 0xFB30, 0xFB31, 0xFB32, 0xFB33, 0xFB34, 0xFB35, 0xFB36, 0xFB38,
134 0xFB39, 0xFB3A, 0xFB3B, 0xFB3C, 0xFB3E, 0xFB40, 0xFB41, 0xFB43, 0xFB44,
135 0xFB46, 0xFB47, 0xFB48, 0xFB49, 0xFB4A, 0xFB4B, 0xFB4C, 0xFB4D, 0xFB4E,
139 /* Convert the incomplete win32 table to some slightly more useful data */
140 static void classify(LPCWSTR lpString
, WORD
*chartype
, DWORD uCount
)
143 GetStringTypeW(CT_CTYPE2
, lpString
, uCount
, chartype
);
144 for (i
= 0; i
< uCount
; ++i
)
147 case C2_LEFTTORIGHT
: chartype
[i
] = L
; break;
150 for (j
= 0; j
< sizeof(Rs
)/sizeof(WCHAR
); ++j
)
151 if (Rs
[j
] == lpString
[i
])
158 case C2_EUROPENUMBER
: chartype
[i
] = EN
; break;
159 case C2_EUROPESEPARATOR
: chartype
[i
] = ES
; break;
160 case C2_EUROPETERMINATOR
: chartype
[i
] = ET
; break;
161 case C2_ARABICNUMBER
: chartype
[i
] = AN
; break;
162 case C2_COMMONSEPARATOR
: chartype
[i
] = CS
; break;
163 case C2_BLOCKSEPARATOR
: chartype
[i
] = B
; break;
164 case C2_SEGMENTSEPARATOR
: chartype
[i
] = S
; break;
165 case C2_WHITESPACE
: chartype
[i
] = WS
; break;
166 case C2_OTHERNEUTRAL
:
169 case 0x202A: chartype
[i
] = LRE
; break;
170 case 0x202B: chartype
[i
] = RLE
; break;
171 case 0x202C: chartype
[i
] = PDF
; break;
172 case 0x202D: chartype
[i
] = LRO
; break;
173 case 0x202E: chartype
[i
] = RLO
; break;
174 default: chartype
[i
] = ON
; break;
177 case C2_NOTAPPLICABLE
:
179 for (j
= 0; j
< sizeof(BNs
)/sizeof(WCHAR
); ++j
)
180 if (BNs
[j
] == lpString
[i
])
188 /* According to BiDi spec, unassigned characters default to L */
189 FIXME("Unhandled character type: %04x\n", chartype
[i
]);
195 /* reverse cch characters */
196 static void reverse(LPWSTR psz
, int cch
)
200 for (; ich
< --cch
; ich
++)
208 /* Set a run of cval values at locations all prior to, but not including */
209 /* iStart, to the new value nval. */
210 static void SetDeferredRun(WORD
*pval
, int cval
, int iStart
, int nval
)
213 for (; i
>= iStart
- cval
; i
--)
219 /* THE PARAGRAPH LEVEL */
221 /*------------------------------------------------------------------------
222 Function: resolveParagraphs
224 Resolves the input strings into blocks over which the algorithm
227 Implements Rule P1 of the Unicode Bidi Algorithm
232 Output: revised character count
234 Note: This is a very simplistic function. In effect it restricts
235 the action of the algorithm to the first paragraph in the input
236 where a paragraph ends at the end of the first block separator
237 or at the end of the input text.
239 ------------------------------------------------------------------------*/
241 static int resolveParagraphs(WORD
*types
, int cch
)
243 /* skip characters not of type B */
245 for(; ich
< cch
&& types
[ich
] != B
; ich
++);
246 /* stop after first B, make it a BN for use in the next steps */
247 if (ich
< cch
&& types
[ich
] == B
)
253 /*------------------------------------------------------------------------
254 Function: resolveLines
256 Breaks a paragraph into lines
258 Input: Character count
259 In/Out: Array of characters
260 Array of line break flags
262 Returns the count of characters on the first line
264 Note: This function only breaks lines at hard line breaks. Other
265 line breaks can be passed in. If pbrk[n] is TRUE, then a break
266 occurs after the character in pszInput[n]. Breaks before the first
267 character are not allowed.
268 ------------------------------------------------------------------------*/
269 static int resolveLines(LPCWSTR pszInput
, BOOL
* pbrk
, int cch
)
271 /* skip characters not of type LS */
273 for(; ich
< cch
; ich
++)
275 if (pszInput
[ich
] == (WCHAR
)'\n' || (pbrk
&& pbrk
[ich
]))
285 /*------------------------------------------------------------------------
286 Function: resolveWhiteSpace
288 Resolves levels for WS and S
289 Implements rule L1 of the Unicode bidi Algorithm.
291 Input: Base embedding level
293 Array of direction classes (for one line of text)
295 In/Out: Array of embedding levels (for one line of text)
297 Note: this should be applied a line at a time. The default driver
298 code supplied in this file assumes a single line of text; for
299 a real implementation, cch and the initial pointer values
300 would have to be adjusted.
301 ------------------------------------------------------------------------*/
302 static void resolveWhitespace(int baselevel
, const WORD
*pcls
, WORD
*plevel
, int cch
)
305 int oldlevel
= baselevel
;
308 for (; ich
< cch
; ich
++)
313 cchrun
= 0; /* any other character breaks the run */
325 plevel
[ich
] = oldlevel
;
331 /* reset levels for WS before eot */
332 SetDeferredRun(plevel
, cchrun
, ich
, baselevel
);
334 plevel
[ich
] = baselevel
;
337 oldlevel
= plevel
[ich
];
339 /* reset level before eot */
340 SetDeferredRun(plevel
, cchrun
, ich
, baselevel
);
344 /*------------------------------------------------------------------------
345 Functions: reorder/reorderLevel
347 Recursively reorders the display string
348 "From the highest level down, reverse all characters at that level and
349 higher, down to the lowest odd level"
351 Implements rule L2 of the Unicode bidi Algorithm.
353 Input: Array of embedding levels
355 Flag enabling reversal (set to false by initial caller)
357 In/Out: Text to reorder
359 Note: levels may exceed 15 resp. 61 on input.
361 Rule L3 - reorder combining marks is not implemented here
362 Rule L4 - glyph mirroring is implemented as a display option below
364 Note: this should be applied a line at a time
365 -------------------------------------------------------------------------*/
366 static int reorderLevel(int level
, LPWSTR pszText
, const WORD
* plevel
, int cch
, BOOL fReverse
)
370 /* true as soon as first odd level encountered */
371 fReverse
= fReverse
|| odd(level
);
373 for (; ich
< cch
; ich
++)
375 if (plevel
[ich
] < level
)
379 else if (plevel
[ich
] > level
)
381 ich
+= reorderLevel(level
+ 1, pszText
+ ich
, plevel
+ ich
,
382 cch
- ich
, fReverse
) - 1;
387 reverse(pszText
, ich
);
392 static int reorder(int baselevel
, LPWSTR pszText
, const WORD
* plevel
, int cch
)
398 ich
+= reorderLevel(baselevel
, pszText
+ ich
, plevel
+ ich
,
404 /* DISPLAY OPTIONS */
405 /*-----------------------------------------------------------------------
408 Crudely implements rule L4 of the Unicode Bidirectional Algorithm
409 Demonstrate mirrored brackets, braces and parens
412 Input: Array of levels
415 In/Out: Array of characters (should be array of glyph ids)
418 A full implementation would need to substitute mirrored glyphs even
419 for characters that are not paired (e.g. integral sign).
420 -----------------------------------------------------------------------*/
421 static void mirror(LPWSTR pszInput
, const WORD
* plevel
, int cch
)
423 static int warn_once
;
426 for (i
= 0; i
< cch
; ++i
)
430 /* This needs the data from http://www.unicode.org/Public/UNIDATA/BidiMirroring.txt */
432 FIXME("stub: mirroring of characters not yet implemented\n");
437 /*------------------------------------------------------------------------
440 Implements the Line-by-Line phases of the Unicode Bidi Algorithm
442 Input: Count of characters
443 flag whether to mirror
446 Array of character directions
449 ------------------------------------------------------------------------*/
450 static void BidiLines(int baselevel
, LPWSTR pszOutLine
, LPCWSTR pszLine
, WORD
* pclsLine
,
451 WORD
* plevelLine
, int cchPara
, int fMirror
, BOOL
* pbrk
)
457 /* break lines at LS */
458 cchLine
= resolveLines(pszLine
, pbrk
, cchPara
);
460 /* resolve whitespace */
461 resolveWhitespace(baselevel
, pclsLine
, plevelLine
, cchLine
);
466 mirror(pszOutLine
, plevelLine
, cchLine
);
468 /* reorder each line in place */
469 reorder(baselevel
, pszOutLine
, plevelLine
, cchLine
);
473 plevelLine
+= cchLine
;
474 pbrk
+= pbrk
? cchLine
: 0;
481 /*************************************************************
485 LPCWSTR lpString
, /* [in] The string for which information is to be returned */
486 INT uCount
, /* [in] Number of WCHARs in string. */
487 DWORD dwFlags
, /* [in] GetCharacterPlacement compatible flags specifying how to process the string */
488 DWORD dwWineGCP_Flags
, /* [in] Wine internal flags - Force paragraph direction */
489 LPWSTR lpOutString
, /* [out] Reordered string */
490 INT uCountOut
, /* [in] Size of output buffer */
491 UINT
*lpOrder
/* [out] Logical -> Visual order map */
500 SCRIPT_CONTROL Control
;
505 TRACE("%s, %d, 0x%08x lpOutString=%p, lpOrder=%p\n",
506 debugstr_wn(lpString
, uCount
), uCount
, dwFlags
,
507 lpOutString
, lpOrder
);
509 memset(&Control
, 0, sizeof(Control
));
510 memset(&State
, 0, sizeof(State
));
512 if (!(dwFlags
& GCP_REORDER
))
514 FIXME("Asked to reorder without reorder flag set\n");
518 if (uCountOut
< uCount
)
520 FIXME("lpOutString too small\n");
524 chartype
= HeapAlloc(GetProcessHeap(), 0, uCount
* sizeof(WORD
));
527 WARN("Out of memory\n");
532 memcpy(lpOutString
, lpString
, uCount
* sizeof(WCHAR
));
534 /* Verify reordering will be required */
535 if ((WINE_GCPW_FORCE_RTL
== (dwWineGCP_Flags
&WINE_GCPW_DIR_MASK
)) ||
536 ((dwWineGCP_Flags
&WINE_GCPW_DIR_MASK
) == WINE_GCPW_LOOSE_RTL
))
537 State
.uBidiLevel
= 1;
541 classify(lpString
, chartype
, uCount
);
542 for (i
= 0; i
< uCount
; i
++)
554 HeapFree(GetProcessHeap(), 0, chartype
);
559 levels
= HeapAlloc(GetProcessHeap(), 0, uCount
* sizeof(WORD
));
562 WARN("Out of memory\n");
563 HeapFree(GetProcessHeap(), 0, chartype
);
568 pItems
= HeapAlloc(GetProcessHeap(),0, maxItems
* sizeof(SCRIPT_ITEM
));
571 WARN("Out of memory\n");
572 HeapFree(GetProcessHeap(), 0, chartype
);
573 HeapFree(GetProcessHeap(), 0, levels
);
578 while (done
< uCount
)
581 classify(lpString
+ done
, chartype
, uCount
- done
);
582 /* limit text to first block */
583 i
= resolveParagraphs(chartype
, uCount
- done
);
584 for (j
= 0; j
< i
; ++j
)
590 case ON
: chartype
[j
] = N
;
594 if ((dwWineGCP_Flags
&WINE_GCPW_DIR_MASK
) == WINE_GCPW_LOOSE_RTL
)
595 State
.uBidiLevel
= 1;
596 else if ((dwWineGCP_Flags
&WINE_GCPW_DIR_MASK
) == WINE_GCPW_LOOSE_LTR
)
597 State
.uBidiLevel
= 0;
599 if (dwWineGCP_Flags
& WINE_GCPW_LOOSE_MASK
)
601 for (j
= 0; j
< i
; ++j
)
602 if (chartype
[j
] == L
)
604 State
.uBidiLevel
= 0;
607 else if (chartype
[j
] == R
|| chartype
[j
] == AL
)
609 State
.uBidiLevel
= 1;
614 res
= ScriptItemize(lpString
+ done
, i
, maxItems
, &Control
, &State
, pItems
, &nItems
);
615 while (res
== E_OUTOFMEMORY
)
617 maxItems
= maxItems
* 2;
618 pItems
= HeapReAlloc(GetProcessHeap(), 0, pItems
, sizeof(SCRIPT_ITEM
) * maxItems
);
621 WARN("Out of memory\n");
622 HeapFree(GetProcessHeap(), 0, chartype
);
623 HeapFree(GetProcessHeap(), 0, levels
);
626 res
= ScriptItemize(lpString
+ done
, i
, maxItems
, &Control
, &State
, pItems
, &nItems
);
629 for (j
= 0; j
< nItems
; j
++)
632 for (k
= pItems
[j
].iCharPos
; k
< pItems
[j
+1].iCharPos
; k
++)
633 levels
[k
] = pItems
[j
].a
.s
.uBidiLevel
;
636 /* assign directional types again, but for WS, S this time */
637 classify(lpString
+ done
, chartype
, i
);
639 BidiLines(State
.uBidiLevel
, lpOutString
? lpOutString
+ done
: NULL
, lpString
+ done
,
640 chartype
, levels
, i
, !(dwFlags
& GCP_SYMSWAPOFF
), 0);
646 for (j
= lastgood
= 0; j
< i
; ++j
)
647 if (levels
[j
] != levels
[lastgood
])
650 if (odd(levels
[lastgood
]))
651 for (k
= j
; k
>= lastgood
; --k
)
652 lpOrder
[done
+ k
] = done
+ j
- k
;
654 for (k
= lastgood
; k
<= j
; ++k
)
655 lpOrder
[done
+ k
] = done
+ k
;
658 if (odd(levels
[lastgood
]))
659 for (k
= j
- 1; k
>= lastgood
; --k
)
660 lpOrder
[done
+ k
] = done
+ j
- 1 - k
;
662 for (k
= lastgood
; k
< j
; ++k
)
663 lpOrder
[done
+ k
] = done
+ k
;
668 HeapFree(GetProcessHeap(), 0, chartype
);
669 HeapFree(GetProcessHeap(), 0, levels
);
670 HeapFree(GetProcessHeap(), 0, pItems
);