2 * GDI BiDirectional handling
4 * Copyright 2003 Shachar Shemesh
5 * Copyright 2007 Maarten Lankhorst
7 * This library is free software; you can redistribute it and/or
8 * modify it under the terms of the GNU Lesser General Public
9 * License as published by the Free Software Foundation; either
10 * version 2.1 of the License, or (at your option) any later version.
12 * This library is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15 * Lesser General Public License for more details.
17 * You should have received a copy of the GNU Lesser General Public
18 * License along with this library; if not, write to the Free Software
19 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA
21 * Code derived from the modified reference implementation
22 * that was found in revision 17 of http://unicode.org/reports/tr9/
23 * "Unicode Standard Annex #9: THE BIDIRECTIONAL ALGORITHM"
25 * -- Copyright (C) 1999-2005, ASMUS, Inc.
27 * Permission is hereby granted, free of charge, to any person obtaining a
28 * copy of the Unicode data files and any associated documentation (the
29 * "Data Files") or Unicode software and any associated documentation (the
30 * "Software") to deal in the Data Files or Software without restriction,
31 * including without limitation the rights to use, copy, modify, merge,
32 * publish, distribute, and/or sell copies of the Data Files or Software,
33 * and to permit persons to whom the Data Files or Software are furnished
34 * to do so, provided that (a) the above copyright notice(s) and this
35 * permission notice appear with all copies of the Data Files or Software,
36 * (b) both the above copyright notice(s) and this permission notice appear
37 * in associated documentation, and (c) there is clear notice in each
38 * modified Data File or in the Software as well as in the documentation
39 * associated with the Data File(s) or Software that the data or software
49 #include "wine/debug.h"
50 #include "gdi_private.h"
52 WINE_DEFAULT_DEBUG_CHANNEL(bidi
);
54 #define ASSERT(x) do { if (!(x)) FIXME("assert failed: %s\n", #x); } while(0)
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
)
252 /* RESOLVE EXPLICIT */
254 static WORD
GreaterEven(int i
)
256 return odd(i
) ? i
+ 1 : i
+ 2;
259 static WORD
GreaterOdd(int i
)
261 return odd(i
) ? i
+ 2 : i
+ 1;
264 static WORD
EmbeddingDirection(int level
)
266 return odd(level
) ? R
: L
;
269 /*------------------------------------------------------------------------
270 Function: resolveExplicit
272 Recursively resolves explicit embedding levels and overrides.
273 Implements rules X1-X9, of the Unicode Bidirectional Algorithm.
275 Input: Base embedding level and direction
278 Output: Array of embedding levels
280 In/Out: Array of direction classes
283 Note: The function uses two simple counters to keep track of
284 matching explicit codes and PDF. Use the default argument for
285 the outermost call. The nesting counter counts the recursion
286 depth and not the embedding level.
287 ------------------------------------------------------------------------*/
289 static int resolveExplicit(int level
, int dir
, WORD
*pcls
, WORD
*plevel
, int cch
, int nNest
)
291 /* always called with a valid nesting level
292 nesting levels are != embedding levels */
293 int nLastValid
= nNest
;
296 /* check input values */
297 ASSERT(nNest
>= 0 && level
>= 0 && level
<= MAX_LEVEL
);
299 /* process the text */
300 for (; ich
< cch
; ich
++)
302 WORD cls
= pcls
[ich
];
308 if (GreaterEven(level
) <= MAX_LEVEL
- (cls
== LRO
? 2 : 0))
310 plevel
[ich
] = GreaterEven(level
);
312 ich
+= resolveExplicit(plevel
[ich
], (cls
== LRE
? N
: L
),
313 &pcls
[ich
+1], &plevel
[ich
+1],
314 cch
- (ich
+1), nNest
);
318 cls
= pcls
[ich
] = BN
;
324 if (GreaterOdd(level
) <= MAX_LEVEL
- (cls
== RLO
? 2 : 0))
326 plevel
[ich
] = GreaterOdd(level
);
328 ich
+= resolveExplicit(plevel
[ich
], (cls
== RLE
? N
: R
),
329 &pcls
[ich
+1], &plevel
[ich
+1],
330 cch
- (ich
+1), nNest
);
334 cls
= pcls
[ich
] = BN
;
338 cls
= pcls
[ich
] = BN
;
341 if (nLastValid
< nNest
)
347 cch
= ich
; /* break the loop, but complete body */
352 /* Apply the override */
365 /* RESOLVE WEAK TYPES */
367 enum states
/* possible states */
369 xa
, /* arabic letter */
370 xr
, /* right letter */
371 xl
, /* left letter */
373 ao
, /* arabic lett. foll by ON */
374 ro
, /* right lett. foll by ON */
375 lo
, /* left lett. foll by ON */
377 rt
, /* ET following R */
378 lt
, /* ET following L */
380 cn
, /* EN, AN following AL */
381 ra
, /* arabic number foll R */
382 re
, /* european number foll R */
383 la
, /* arabic number foll L */
384 le
, /* european number foll L */
386 ac
, /* CS following cn */
387 rc
, /* CS following ra */
388 rs
, /* CS,ES following re */
389 lc
, /* CS following la */
390 ls
, /* CS,ES following le */
392 ret
, /* ET following re */
393 let
, /* ET following le */
396 static const int stateWeak
[][10] =
398 /* N, L, R, AN, EN, AL,NSM, CS, ES, ET */
399 /*xa*/ { ao
, xl
, xr
, cn
, cn
, xa
, xa
, ao
, ao
, ao
}, /* arabic letter */
400 /*xr*/ { ro
, xl
, xr
, ra
, re
, xa
, xr
, ro
, ro
, rt
}, /* right letter */
401 /*xl*/ { lo
, xl
, xr
, la
, le
, xa
, xl
, lo
, lo
, lt
}, /* left letter */
403 /*ao*/ { ao
, xl
, xr
, cn
, cn
, xa
, ao
, ao
, ao
, ao
}, /* arabic lett. foll by ON*/
404 /*ro*/ { ro
, xl
, xr
, ra
, re
, xa
, ro
, ro
, ro
, rt
}, /* right lett. foll by ON */
405 /*lo*/ { lo
, xl
, xr
, la
, le
, xa
, lo
, lo
, lo
, lt
}, /* left lett. foll by ON */
407 /*rt*/ { ro
, xl
, xr
, ra
, re
, xa
, rt
, ro
, ro
, rt
}, /* ET following R */
408 /*lt*/ { lo
, xl
, xr
, la
, le
, xa
, lt
, lo
, lo
, lt
}, /* ET following L */
410 /*cn*/ { ao
, xl
, xr
, cn
, cn
, xa
, cn
, ac
, ao
, ao
}, /* EN, AN following AL */
411 /*ra*/ { ro
, xl
, xr
, ra
, re
, xa
, ra
, rc
, ro
, rt
}, /* arabic number foll R */
412 /*re*/ { ro
, xl
, xr
, ra
, re
, xa
, re
, rs
, rs
,ret
}, /* european number foll R */
413 /*la*/ { lo
, xl
, xr
, la
, le
, xa
, la
, lc
, lo
, lt
}, /* arabic number foll L */
414 /*le*/ { lo
, xl
, xr
, la
, le
, xa
, le
, ls
, ls
,let
}, /* european number foll L */
416 /*ac*/ { ao
, xl
, xr
, cn
, cn
, xa
, ao
, ao
, ao
, ao
}, /* CS following cn */
417 /*rc*/ { ro
, xl
, xr
, ra
, re
, xa
, ro
, ro
, ro
, rt
}, /* CS following ra */
418 /*rs*/ { ro
, xl
, xr
, ra
, re
, xa
, ro
, ro
, ro
, rt
}, /* CS,ES following re */
419 /*lc*/ { lo
, xl
, xr
, la
, le
, xa
, lo
, lo
, lo
, lt
}, /* CS following la */
420 /*ls*/ { lo
, xl
, xr
, la
, le
, xa
, lo
, lo
, lo
, lt
}, /* CS,ES following le */
422 /*ret*/{ ro
, xl
, xr
, ra
, re
, xa
,ret
, ro
, ro
,ret
}, /* ET following re */
423 /*let*/{ lo
, xl
, xr
, la
, le
, xa
,let
, lo
, lo
,let
}, /* ET following le */
426 enum actions
/* possible actions */
429 IX
= 0x100, /* increment */
430 XX
= 0xF, /* no-op */
433 xxx
= (XX
<< 4) + XX
, /* no-op */
434 xIx
= IX
+ xxx
, /* increment run */
435 xxN
= (XX
<< 4) + ON
, /* set current to N */
436 xxE
= (XX
<< 4) + EN
, /* set current to EN */
437 xxA
= (XX
<< 4) + AN
, /* set current to AN */
438 xxR
= (XX
<< 4) + R
, /* set current to R */
439 xxL
= (XX
<< 4) + L
, /* set current to L */
440 Nxx
= (ON
<< 4) + 0xF, /* set run to neutral */
441 Axx
= (AN
<< 4) + 0xF, /* set run to AN */
442 ExE
= (EN
<< 4) + EN
, /* set run to EN, set current to EN */
443 NIx
= (ON
<< 4) + 0xF + IX
, /* set run to N, increment */
444 NxN
= (ON
<< 4) + ON
, /* set run to N, set current to N */
445 NxR
= (ON
<< 4) + R
, /* set run to N, set current to R */
446 NxE
= (ON
<< 4) + EN
, /* set run to N, set current to EN */
448 AxA
= (AN
<< 4) + AN
, /* set run to AN, set current to AN */
449 NxL
= (ON
<< 4) + L
, /* set run to N, set current to L */
450 LxL
= (L
<< 4) + L
, /* set run to L, set current to L */
453 static const int actionWeak
[][10] =
455 /* N, L, R, AN, EN, AL, NSM, CS, ES, ET */
456 /*xa*/ { xxx
, xxx
, xxx
, xxx
, xxA
, xxR
, xxR
, xxN
, xxN
, xxN
}, /* arabic letter */
457 /*xr*/ { xxx
, xxx
, xxx
, xxx
, xxE
, xxR
, xxR
, xxN
, xxN
, xIx
}, /* right leter */
458 /*xl*/ { xxx
, xxx
, xxx
, xxx
, xxL
, xxR
, xxL
, xxN
, xxN
, xIx
}, /* left letter */
460 /*ao*/ { xxx
, xxx
, xxx
, xxx
, xxA
, xxR
, xxN
, xxN
, xxN
, xxN
}, /* arabic lett. foll by ON */
461 /*ro*/ { xxx
, xxx
, xxx
, xxx
, xxE
, xxR
, xxN
, xxN
, xxN
, xIx
}, /* right lett. foll by ON */
462 /*lo*/ { xxx
, xxx
, xxx
, xxx
, xxL
, xxR
, xxN
, xxN
, xxN
, xIx
}, /* left lett. foll by ON */
464 /*rt*/ { Nxx
, Nxx
, Nxx
, Nxx
, ExE
, NxR
, xIx
, NxN
, NxN
, xIx
}, /* ET following R */
465 /*lt*/ { Nxx
, Nxx
, Nxx
, Nxx
, LxL
, NxR
, xIx
, NxN
, NxN
, xIx
}, /* ET following L */
467 /*cn*/ { xxx
, xxx
, xxx
, xxx
, xxA
, xxR
, xxA
, xIx
, xxN
, xxN
}, /* EN, AN following AL */
468 /*ra*/ { xxx
, xxx
, xxx
, xxx
, xxE
, xxR
, xxA
, xIx
, xxN
, xIx
}, /* arabic number foll R */
469 /*re*/ { xxx
, xxx
, xxx
, xxx
, xxE
, xxR
, xxE
, xIx
, xIx
, xxE
}, /* european number foll R */
470 /*la*/ { xxx
, xxx
, xxx
, xxx
, xxL
, xxR
, xxA
, xIx
, xxN
, xIx
}, /* arabic number foll L */
471 /*le*/ { xxx
, xxx
, xxx
, xxx
, xxL
, xxR
, xxL
, xIx
, xIx
, xxL
}, /* european number foll L */
473 /*ac*/ { Nxx
, Nxx
, Nxx
, Axx
, AxA
, NxR
, NxN
, NxN
, NxN
, NxN
}, /* CS following cn */
474 /*rc*/ { Nxx
, Nxx
, Nxx
, Axx
, NxE
, NxR
, NxN
, NxN
, NxN
, NIx
}, /* CS following ra */
475 /*rs*/ { Nxx
, Nxx
, Nxx
, Nxx
, ExE
, NxR
, NxN
, NxN
, NxN
, NIx
}, /* CS,ES following re */
476 /*lc*/ { Nxx
, Nxx
, Nxx
, Axx
, NxL
, NxR
, NxN
, NxN
, NxN
, NIx
}, /* CS following la */
477 /*ls*/ { Nxx
, Nxx
, Nxx
, Nxx
, LxL
, NxR
, NxN
, NxN
, NxN
, NIx
}, /* CS,ES following le */
479 /*ret*/{ xxx
, xxx
, xxx
, xxx
, xxE
, xxR
, xxE
, xxN
, xxN
, xxE
}, /* ET following re */
480 /*let*/{ xxx
, xxx
, xxx
, xxx
, xxL
, xxR
, xxL
, xxN
, xxN
, xxL
}, /* ET following le */
483 static int GetDeferredType(int action
)
485 return (action
>> 4) & 0xF;
488 static int GetResolvedType(int action
)
493 /* Note on action table:
495 States can be of two kinds:
496 - Immediate Resolution State, where each input token
497 is resolved as soon as it is seen. These states have
498 only single action codes (xxN) or the no-op (xxx)
499 for static input tokens.
500 - Deferred Resolution State, where input tokens either
501 either extend the run (xIx) or resolve its Type (e.g. Nxx).
503 Input classes are of three kinds
504 - Static Input Token, where the class of the token remains
505 unchanged on output (AN, L, N, R)
506 - Replaced Input Token, where the class of the token is
507 always replaced on output (AL, BN, NSM, CS, ES, ET)
508 - Conditional Input Token, where the class of the token is
509 changed on output in some, but not all, cases (EN)
511 Where tokens are subject to change, a double action
512 (e.g. NxA, or NxN) is _required_ after deferred states,
513 resolving both the deferred state and changing the current token.
516 /*------------------------------------------------------------------------
517 Function: resolveWeak
519 Resolves the directionality of numeric and other weak character types
521 Implements rules X10 and W1-W6 of the Unicode Bidirectional Algorithm.
523 Input: Array of embedding levels
526 In/Out: Array of directional classes
528 Note: On input only these directional classes are expected
529 AL, HL, R, L, ON, BN, NSM, AN, EN, ES, ET, CS,
530 ------------------------------------------------------------------------*/
531 static void resolveWeak(int baselevel
, WORD
*pcls
, WORD
*plevel
, int cch
)
533 int state
= odd(baselevel
) ? xr
: xl
;
536 int level
= baselevel
;
537 int action
, clsRun
, clsNew
;
541 for (; ich
< cch
; ich
++)
543 /* ignore boundary neutrals */
546 /* must flatten levels unless at a level change; */
549 /* lookahead for level changes */
550 if (ich
+ 1 == cch
&& level
!= baselevel
)
552 /* have to fixup last BN before end of the loop, since
553 * its fix-upped value will be needed below the assert */
554 pcls
[ich
] = EmbeddingDirection(level
);
556 else if (ich
+ 1 < cch
&& level
!= plevel
[ich
+1] && pcls
[ich
+1] != BN
)
558 /* fixup LAST BN in front / after a level run to make
559 * it act like the SOR/EOR in rule X10 */
560 int newlevel
= plevel
[ich
+1];
561 if (level
> newlevel
) {
564 plevel
[ich
] = newlevel
;
566 /* must match assigned level */
567 pcls
[ich
] = EmbeddingDirection(newlevel
);
568 level
= plevel
[ich
+1];
572 /* don't interrupt runs */
581 ASSERT(pcls
[ich
] <= BN
);
584 action
= actionWeak
[state
][cls
];
586 /* resolve the directionality for deferred runs */
587 clsRun
= GetDeferredType(action
);
590 SetDeferredRun(pcls
, cchRun
, ich
, clsRun
);
594 /* resolve the directionality class at the current location */
595 clsNew
= GetResolvedType(action
);
599 /* increment a deferred run */
603 state
= stateWeak
[state
][cls
];
606 /* resolve any deferred runs
607 * use the direction of the current level to emulate PDF */
608 cls
= EmbeddingDirection(level
);
610 /* resolve the directionality for deferred runs */
611 clsRun
= GetDeferredType(actionWeak
[state
][cls
]);
613 SetDeferredRun(pcls
, cchRun
, ich
, clsRun
);
616 /* RESOLVE NEUTRAL TYPES */
621 /* action to resolve previous input */
622 nL
= L
, /* resolve EN to L */
623 En
= 3 << 4, /* resolve neutrals run to embedding level direction */
624 Rn
= R
<< 4, /* resolve neutrals run to strong right */
625 Ln
= L
<< 4, /* resolved neutrals run to strong left */
626 In
= (1<<8), /* increment count of deferred neutrals */
627 LnL
= (1<<4)+L
, /* set run and EN to L */
630 static int GetDeferredNeutrals(int action
, int level
)
632 action
= (action
>> 4) & 0xF;
633 if (action
== (En
>> 4))
634 return EmbeddingDirection(level
);
639 static int GetResolvedNeutrals(int action
)
641 action
= action
& 0xF;
651 /* new temporary class */
652 r
, /* R and characters resolved to R */
653 l
, /* L and characters resolved to L */
654 rn
, /* N preceded by right */
655 ln
, /* N preceded by left */
656 a
, /* AN preceded by left (the abbreviation 'la' is used up above) */
657 na
, /* N preceded by a */
661 /*------------------------------------------------------------------------
664 By rule W7, whenever a EN is 'dominated' by an L (including start of
665 run with embedding direction = L) it is resolved to, and further treated
668 This leads to the need for 'a' and 'na' states.
669 ------------------------------------------------------------------------*/
671 static const int actionNeutrals
[][5] =
673 /* N, L, R, AN, EN = cls */
674 { In
, 0, 0, 0, 0 }, /* r right */
675 { In
, 0, 0, 0, L
}, /* l left */
677 { In
, En
, Rn
, Rn
, Rn
}, /* rn N preceded by right */
678 { In
, Ln
, En
, En
, LnL
}, /* ln N preceded by left */
680 { In
, 0, 0, 0, L
}, /* a AN preceded by left */
681 { In
, En
, Rn
, Rn
, En
}, /* na N preceded by a */
684 static const int stateNeutrals
[][5] =
686 /* N, L, R, AN, EN */
687 { rn
, l
, r
, r
, r
}, /* r right */
688 { ln
, l
, r
, a
, l
}, /* l left */
690 { rn
, l
, r
, r
, r
}, /* rn N preceded by right */
691 { ln
, l
, r
, a
, l
}, /* ln N preceded by left */
693 { na
, l
, r
, a
, l
}, /* a AN preceded by left */
694 { na
, l
, r
, a
, l
}, /* na N preceded by la */
697 /*------------------------------------------------------------------------
698 Function: resolveNeutrals
700 Resolves the directionality of neutral character types.
702 Implements rules W7, N1 and N2 of the Unicode Bidi Algorithm.
704 Input: Array of embedding levels
708 In/Out: Array of directional classes
710 Note: On input only these directional classes are expected
711 R, L, N, AN, EN and BN
713 W8 resolves a number of ENs to L
714 ------------------------------------------------------------------------*/
715 static void resolveNeutrals(int baselevel
, WORD
*pcls
, const WORD
*plevel
, int cch
)
717 /* the state at the start of text depends on the base level */
718 int state
= odd(baselevel
) ? r
: l
;
722 int level
= baselevel
;
724 int action
, clsRun
, clsNew
;
726 for (; ich
< cch
; ich
++)
728 /* ignore boundary neutrals */
731 /* include in the count for a deferred run */
735 /* skip any further processing */
739 ASSERT(pcls
[ich
] < 5); /* "Only N, L, R, AN, EN are allowed" */
742 action
= actionNeutrals
[state
][cls
];
744 /* resolve the directionality for deferred runs */
745 clsRun
= GetDeferredNeutrals(action
, level
);
748 SetDeferredRun(pcls
, cchRun
, ich
, clsRun
);
752 /* resolve the directionality class at the current location */
753 clsNew
= GetResolvedNeutrals(action
);
760 state
= stateNeutrals
[state
][cls
];
764 /* resolve any deferred runs */
765 cls
= EmbeddingDirection(level
); /* eor has type of current level */
767 /* resolve the directionality for deferred runs */
768 clsRun
= GetDeferredNeutrals(actionNeutrals
[state
][cls
], level
);
770 SetDeferredRun(pcls
, cchRun
, ich
, clsRun
);
773 /* RESOLVE IMPLICIT */
775 /*------------------------------------------------------------------------
776 Function: resolveImplicit
778 Recursively resolves implicit embedding levels.
779 Implements rules I1 and I2 of the Unicode Bidirectional Algorithm.
781 Input: Array of direction classes
785 In/Out: Array of embedding levels
787 Note: levels may exceed 15 on output.
788 Accepted subset of direction classes
790 ------------------------------------------------------------------------*/
791 static const WORD addLevel
[][4] =
794 /* even */ { 0, 1, 2, 2, },
795 /* odd */ { 1, 0, 1, 1, }
799 static void resolveImplicit(const WORD
* pcls
, WORD
*plevel
, int cch
)
802 for (; ich
< cch
; ich
++)
804 /* cannot resolve bn here, since some bn were resolved to strong
805 * types in resolveWeak. To remove these we need the original
806 * types, which are available again in resolveWhiteSpace */
811 ASSERT(pcls
[ich
] > 0); /* "No Neutrals allowed to survive here." */
812 ASSERT(pcls
[ich
] < 5); /* "Out of range." */
813 plevel
[ich
] += addLevel
[odd(plevel
[ich
])][pcls
[ich
] - 1];
818 /*------------------------------------------------------------------------
819 Function: resolveLines
821 Breaks a paragraph into lines
823 Input: Character count
824 In/Out: Array of characters
825 Array of line break flags
827 Returns the count of characters on the first line
829 Note: This function only breaks lines at hard line breaks. Other
830 line breaks can be passed in. If pbrk[n] is TRUE, then a break
831 occurs after the character in pszInput[n]. Breaks before the first
832 character are not allowed.
833 ------------------------------------------------------------------------*/
834 static int resolveLines(LPCWSTR pszInput
, BOOL
* pbrk
, int cch
)
836 /* skip characters not of type LS */
838 for(; ich
< cch
; ich
++)
840 if (pszInput
[ich
] == (WCHAR
)'\n' || (pbrk
&& pbrk
[ich
]))
850 /*------------------------------------------------------------------------
851 Function: resolveWhiteSpace
853 Resolves levels for WS and S
854 Implements rule L1 of the Unicode bidi Algorithm.
856 Input: Base embedding level
858 Array of direction classes (for one line of text)
860 In/Out: Array of embedding levels (for one line of text)
862 Note: this should be applied a line at a time. The default driver
863 code supplied in this file assumes a single line of text; for
864 a real implementation, cch and the initial pointer values
865 would have to be adjusted.
866 ------------------------------------------------------------------------*/
867 static void resolveWhitespace(int baselevel
, const WORD
*pcls
, WORD
*plevel
, int cch
)
870 int oldlevel
= baselevel
;
873 for (; ich
< cch
; ich
++)
878 cchrun
= 0; /* any other character breaks the run */
890 plevel
[ich
] = oldlevel
;
896 /* reset levels for WS before eot */
897 SetDeferredRun(plevel
, cchrun
, ich
, baselevel
);
899 plevel
[ich
] = baselevel
;
902 oldlevel
= plevel
[ich
];
904 /* reset level before eot */
905 SetDeferredRun(plevel
, cchrun
, ich
, baselevel
);
909 /*------------------------------------------------------------------------
910 Functions: reorder/reorderLevel
912 Recursively reorders the display string
913 "From the highest level down, reverse all characters at that level and
914 higher, down to the lowest odd level"
916 Implements rule L2 of the Unicode bidi Algorithm.
918 Input: Array of embedding levels
920 Flag enabling reversal (set to false by initial caller)
922 In/Out: Text to reorder
924 Note: levels may exceed 15 resp. 61 on input.
926 Rule L3 - reorder combining marks is not implemented here
927 Rule L4 - glyph mirroring is implemented as a display option below
929 Note: this should be applied a line at a time
930 -------------------------------------------------------------------------*/
931 static int reorderLevel(int level
, LPWSTR pszText
, const WORD
* plevel
, int cch
, BOOL fReverse
)
935 /* true as soon as first odd level encountered */
936 fReverse
= fReverse
|| odd(level
);
938 for (; ich
< cch
; ich
++)
940 if (plevel
[ich
] < level
)
944 else if (plevel
[ich
] > level
)
946 ich
+= reorderLevel(level
+ 1, pszText
+ ich
, plevel
+ ich
,
947 cch
- ich
, fReverse
) - 1;
952 reverse(pszText
, ich
);
957 static int reorder(int baselevel
, LPWSTR pszText
, const WORD
* plevel
, int cch
)
963 ich
+= reorderLevel(baselevel
, pszText
+ ich
, plevel
+ ich
,
969 /* DISPLAY OPTIONS */
970 /*-----------------------------------------------------------------------
973 Crudely implements rule L4 of the Unicode Bidirectional Algorithm
974 Demonstrate mirrored brackets, braces and parens
977 Input: Array of levels
980 In/Out: Array of characters (should be array of glyph ids)
983 A full implementation would need to substitute mirrored glyphs even
984 for characters that are not paired (e.g. integral sign).
985 -----------------------------------------------------------------------*/
986 static void mirror(LPWSTR pszInput
, const WORD
* plevel
, int cch
)
988 static int warn_once
;
991 for (i
= 0; i
< cch
; ++i
)
995 /* This needs the data from http://www.unicode.org/Public/UNIDATA/BidiMirroring.txt */
997 FIXME("stub: mirroring of characters not yet implemented\n");
1002 /*------------------------------------------------------------------------
1005 Implements the Line-by-Line phases of the Unicode Bidi Algorithm
1007 Input: Count of characters
1008 flag whether to mirror
1011 Array of character directions
1014 ------------------------------------------------------------------------*/
1015 static void BidiLines(int baselevel
, LPWSTR pszOutLine
, LPCWSTR pszLine
, WORD
* pclsLine
,
1016 WORD
* plevelLine
, int cchPara
, int fMirror
, BOOL
* pbrk
)
1022 /* break lines at LS */
1023 cchLine
= resolveLines(pszLine
, pbrk
, cchPara
);
1025 /* resolve whitespace */
1026 resolveWhitespace(baselevel
, pclsLine
, plevelLine
, cchLine
);
1031 mirror(pszOutLine
, plevelLine
, cchLine
);
1033 /* reorder each line in place */
1034 reorder(baselevel
, pszOutLine
, plevelLine
, cchLine
);
1038 plevelLine
+= cchLine
;
1039 pbrk
+= pbrk
? cchLine
: 0;
1040 pclsLine
+= cchLine
;
1046 /*************************************************************
1050 LPCWSTR lpString
, /* [in] The string for which information is to be returned */
1051 INT uCount
, /* [in] Number of WCHARs in string. */
1052 DWORD dwFlags
, /* [in] GetCharacterPlacement compatible flags specifying how to process the string */
1053 DWORD dwWineGCP_Flags
, /* [in] Wine internal flags - Force paragraph direction */
1054 LPWSTR lpOutString
, /* [out] Reordered string */
1055 INT uCountOut
, /* [in] Size of output buffer */
1056 UINT
*lpOrder
/* [out] Logical -> Visual order map */
1061 unsigned i
, baselevel
= 0, done
;
1062 TRACE("%s, %d, 0x%08x lpOutString=%p, lpOrder=%p\n",
1063 debugstr_wn(lpString
, uCount
), uCount
, dwFlags
,
1064 lpOutString
, lpOrder
);
1066 if (!(dwFlags
& GCP_REORDER
))
1068 FIXME("Asked to reorder without reorder flag set\n");
1072 if (uCountOut
< uCount
)
1074 FIXME("lpOutString too small\n");
1078 chartype
= HeapAlloc(GetProcessHeap(), 0, uCount
* 2 * sizeof(WORD
));
1079 levels
= chartype
+ uCount
;
1082 WARN("Out of memory\n");
1087 memcpy(lpOutString
, lpString
, uCount
* sizeof(WCHAR
));
1089 if (WINE_GCPW_FORCE_RTL
== (dwWineGCP_Flags
&WINE_GCPW_DIR_MASK
))
1093 while (done
< uCount
)
1096 classify(lpString
+ done
, chartype
, uCount
- done
);
1097 /* limit text to first block */
1098 i
= resolveParagraphs(chartype
, uCount
- done
);
1099 for (j
= 0; j
< i
; ++j
)
1105 case ON
: chartype
[j
] = N
;
1109 if ((dwWineGCP_Flags
&WINE_GCPW_DIR_MASK
) == WINE_GCPW_LOOSE_RTL
)
1111 else if ((dwWineGCP_Flags
&WINE_GCPW_DIR_MASK
) == WINE_GCPW_LOOSE_LTR
)
1114 if (dwWineGCP_Flags
& WINE_GCPW_LOOSE_MASK
)
1116 for (j
= 0; j
< i
; ++j
)
1117 if (chartype
[j
] == L
)
1122 else if (chartype
[j
] == R
|| chartype
[j
] == AL
)
1129 /* resolve explicit */
1130 resolveExplicit(baselevel
, N
, chartype
, levels
, i
, 0);
1133 resolveWeak(baselevel
, chartype
, levels
, i
);
1135 /* resolve neutrals */
1136 resolveNeutrals(baselevel
, chartype
, levels
, i
);
1138 /* resolveImplicit */
1139 resolveImplicit(chartype
, levels
, i
);
1141 /* assign directional types again, but for WS, S this time */
1142 classify(lpString
+ done
, chartype
, i
);
1144 BidiLines(baselevel
, lpOutString
? lpOutString
+ done
: NULL
, lpString
+ done
,
1145 chartype
, levels
, i
, !(dwFlags
& GCP_SYMSWAPOFF
), 0);
1150 for (j
= lastgood
= 0; j
< i
; ++j
)
1151 if (levels
[j
] != levels
[lastgood
])
1154 if (odd(levels
[lastgood
]))
1155 for (k
= j
; k
>= lastgood
; --k
)
1156 lpOrder
[done
+ k
] = done
+ j
- k
;
1158 for (k
= lastgood
; k
<= j
; ++k
)
1159 lpOrder
[done
+ k
] = done
+ k
;
1162 if (odd(levels
[lastgood
]))
1163 for (k
= j
- 1; k
>= lastgood
; --k
)
1164 lpOrder
[done
+ k
] = done
+ j
- 1 - k
;
1166 for (k
= lastgood
; k
< j
; ++k
)
1167 lpOrder
[done
+ k
] = done
+ k
;
1172 HeapFree(GetProcessHeap(), 0, chartype
);