1 /*
2 * GDI BiDirectional handling
3 *
4 * Copyright 2003 Shachar Shemesh
5 * Copyright 2007 Maarten Lankhorst
6 *
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.
11 *
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.
16 *
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
20 *
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"
24 *
25 * -- Copyright (C) 1999-2005, ASMUS, Inc.
26 *
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
40 * has been modified.
41 */
42
43 #include "config.h"
44
45 #include <stdarg.h>
46 #include "windef.h"
47 #include "winbase.h"
48 #include "wingdi.h"
49 #include "wine/debug.h"
50 #include "gdi_private.h"
51
52 WINE_DEFAULT_DEBUG_CHANNEL(bidi);
53
54 #define ASSERT(x) do { if (!(x)) FIXME("assert failed: %s\n", #x); } while(0)
55 #define MAX_LEVEL 61
56
57 /* HELPER FUNCTIONS AND DECLARATIONS */
58
59 #define odd(x) ((x) & 1)
60
61 /*------------------------------------------------------------------------
62 Bidirectional Character Types
63
64 as defined by the Unicode Bidirectional Algorithm Table 3-7.
65
66 Note:
67
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 ------------------------------------------------------------------------*/
72 enum directions
73 {
74 /* input types */
75 /* ON MUST be zero, code relies on ON = N = 0 */
76 ON = 0, /* Other Neutral */
77 L, /* Left Letter */
78 R, /* Right Letter */
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 %) */
86
87 /* resolved types */
88 BN, /* Boundary neutral (type of RLE etc after explicit levels) */
89
90 /* input types, */
91 S, /* Segment Separator (TAB) // used only in L1 */
92 WS, /* White space // used only in L1 */
93 B, /* Paragraph Separator (aka as PS) */
94
95 /* types for explicit controls */
96 RLO, /* these are used only in X1-X9 */
97 RLE,
98 LRO,
99 LRE,
100 PDF,
101
102 /* resolved types, also resolved directions */
103 N = ON, /* alias, where ON, WS and S are treated the same */
104 };
105
106 /* HELPER FUNCTIONS */
107
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
118 };
119
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,
136 0xFB4F
137 };
138
139 /* Convert the incomplete win32 table to some slightly more useful data */
140 static void classify(LPCWSTR lpString, WORD *chartype, DWORD uCount)
141 {
142 unsigned i, j;
143 GetStringTypeW(CT_CTYPE2, lpString, uCount, chartype);
144 for (i = 0; i < uCount; ++i)
145 switch (chartype[i])
146 {
147 case C2_LEFTTORIGHT: chartype[i] = L; break;
148 case C2_RIGHTTOLEFT:
149 chartype[i] = AL;
150 for (j = 0; j < sizeof(Rs)/sizeof(WCHAR); ++j)
151 if (Rs[j] == lpString[i])
152 {
153 chartype[i] = R;
154 break;
155 }
156 break;
157
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:
167 switch (lpString[i])
168 {
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;
175 }
176 break;
177 case C2_NOTAPPLICABLE:
178 chartype[i] = NSM;
179 for (j = 0; j < sizeof(BNs)/sizeof(WCHAR); ++j)
180 if (BNs[j] == lpString[i])
181 {
182 chartype[i] = BN;
183 break;
184 }
185 break;
186
187 default:
188 /* According to BiDi spec, unassigned characters default to L */
189 FIXME("Unhandled character type: %04x\n", chartype[i]);
190 chartype[i] = L;
191 break;
192 }
193 }
194
195 /* reverse cch characters */
196 static void reverse(LPWSTR psz, int cch)
197 {
198 WCHAR chTemp;
199 int ich = 0;
200 for (; ich < --cch; ich++)
201 {
202 chTemp = psz[ich];
203 psz[ich] = psz[cch];
204 psz[cch] = chTemp;
205 }
206 }
207
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)
211 {
212 int i = iStart - 1;
213 for (; i >= iStart - cval; i--)
214 {
215 pval[i] = nval;
216 }
217 }
218
219 /* THE PARAGRAPH LEVEL */
220
221 /*------------------------------------------------------------------------
222 Function: resolveParagraphs
223
224 Resolves the input strings into blocks over which the algorithm
225 is then applied.
226
227 Implements Rule P1 of the Unicode Bidi Algorithm
228
229 Input: Text string
230 Character count
231
232 Output: revised character count
233
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.
238
239 ------------------------------------------------------------------------*/
240
241 static int resolveParagraphs(WORD *types, int cch)
242 {
243 /* skip characters not of type B */
244 int ich = 0;
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)
248 types[ich++] = BN;
249 return ich;
250 }
251
252 /* RESOLVE EXPLICIT */
253
254 static WORD GreaterEven(int i)
255 {
256 return odd(i) ? i + 1 : i + 2;
257 }
258
259 static WORD GreaterOdd(int i)
260 {
261 return odd(i) ? i + 2 : i + 1;
262 }
263
264 static WORD EmbeddingDirection(int level)
265 {
266 return odd(level) ? R : L;
267 }
268
269 /*------------------------------------------------------------------------
270 Function: resolveExplicit
271
272 Recursively resolves explicit embedding levels and overrides.
273 Implements rules X1-X9, of the Unicode Bidirectional Algorithm.
274
275 Input: Base embedding level and direction
276 Character count
277
278 Output: Array of embedding levels
279
280 In/Out: Array of direction classes
281
282
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 ------------------------------------------------------------------------*/
288
289 static int resolveExplicit(int level, int dir, WORD *pcls, WORD *plevel, int cch, int nNest)
290 {
291 /* always called with a valid nesting level
292 nesting levels are != embedding levels */
293 int nLastValid = nNest;
294 int ich = 0;
295
296 /* check input values */
297 ASSERT(nNest >= 0 && level >= 0 && level <= MAX_LEVEL);
298
299 /* process the text */
300 for (; ich < cch; ich++)
301 {
302 WORD cls = pcls[ich];
303 switch (cls)
304 {
305 case LRO:
306 case LRE:
307 nNest++;
308 if (GreaterEven(level) <= MAX_LEVEL - (cls == LRO ? 2 : 0))
309 {
310 plevel[ich] = GreaterEven(level);
311 pcls[ich] = BN;
312 ich += resolveExplicit(plevel[ich], (cls == LRE ? N : L),
313 &pcls[ich+1], &plevel[ich+1],
314 cch - (ich+1), nNest);
315 nNest--;
316 continue;
317 }
318 cls = pcls[ich] = BN;
319 break;
320
321 case RLO:
322 case RLE:
323 nNest++;
324 if (GreaterOdd(level) <= MAX_LEVEL - (cls == RLO ? 2 : 0))
325 {
326 plevel[ich] = GreaterOdd(level);
327 pcls[ich] = BN;
328 ich += resolveExplicit(plevel[ich], (cls == RLE ? N : R),
329 &pcls[ich+1], &plevel[ich+1],
330 cch - (ich+1), nNest);
331 nNest--;
332 continue;
333 }
334 cls = pcls[ich] = BN;
335 break;
336
337 case PDF:
338 cls = pcls[ich] = BN;
339 if (nNest)
340 {
341 if (nLastValid < nNest)
342 {
343 nNest--;
344 }
345 else
346 {
347 cch = ich; /* break the loop, but complete body */
348 }
349 }
350 }
351
352 /* Apply the override */
353 if (dir != N)
354 {
355 cls = dir;
356 }
357 plevel[ich] = level;
358 if (pcls[ich] != BN)
359 pcls[ich] = cls;
360 }
361
362 return ich;
363 }
364
365 /* RESOLVE WEAK TYPES */
366
367 enum states /* possible states */
368 {
369 xa, /* arabic letter */
370 xr, /* right letter */
371 xl, /* left letter */
372
373 ao, /* arabic lett. foll by ON */
374 ro, /* right lett. foll by ON */
375 lo, /* left lett. foll by ON */
376
377 rt, /* ET following R */
378 lt, /* ET following L */
379
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 */
385
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 */
391
392 ret, /* ET following re */
393 let, /* ET following le */
394 } ;
395
396 static const int stateWeak[][10] =
397 {
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 */
402
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 */
406
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 */
409
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 */
415
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 */
421
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 */
424 };
425
426 enum actions /* possible actions */
427 {
428 /* primitives */
429 IX = 0x100, /* increment */
430 XX = 0xF, /* no-op */
431
432 /* actions */
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 */
447
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 */
451 } ;
452
453 static const int actionWeak[][10] =
454 {
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 letter */
458 /*xl*/ { xxx, xxx, xxx, xxx, xxL, xxR, xxL, xxN, xxN, xIx }, /* left letter */
459
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 */
463
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 */
466
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 */
472
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 */
478
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 */
481 };
482
483 static int GetDeferredType(int action)
484 {
485 return (action >> 4) & 0xF;
486 }
487
488 static int GetResolvedType(int action)
489 {
490 return action & 0xF;
491 }
492
493 /* Note on action table:
494
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).
502
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)
510
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.
514 */
515
516 /*------------------------------------------------------------------------
517 Function: resolveWeak
518
519 Resolves the directionality of numeric and other weak character types
520
521 Implements rules X10 and W1-W6 of the Unicode Bidirectional Algorithm.
522
523 Input: Array of embedding levels
524 Character count
525
526 In/Out: Array of directional classes
527
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)
532 {
533 int state = odd(baselevel) ? xr : xl;
534 int cls;
535
536 int level = baselevel;
537 int action, clsRun, clsNew;
538 int cchRun = 0;
539 int ich = 0;
540
541 for (; ich < cch; ich++)
542 {
543 /* ignore boundary neutrals */
544 if (pcls[ich] == BN)
545 {
546 /* must flatten levels unless at a level change; */
547 plevel[ich] = level;
548
549 /* lookahead for level changes */
550 if (ich + 1 == cch && level != baselevel)
551 {
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);
555 }
556 else if (ich + 1 < cch && level != plevel[ich+1] && pcls[ich+1] != BN)
557 {
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) {
562 newlevel = level;
563 }
564 plevel[ich] = newlevel;
565
566 /* must match assigned level */
567 pcls[ich] = EmbeddingDirection(newlevel);
568 level = plevel[ich+1];
569 }
570 else
571 {
572 /* don't interrupt runs */
573 if (cchRun)
574 {
575 cchRun++;
576 }
577 continue;
578 }
579 }
580
581 ASSERT(pcls[ich] <= BN);
582 cls = pcls[ich];
583
584 action = actionWeak[state][cls];
585
586 /* resolve the directionality for deferred runs */
587 clsRun = GetDeferredType(action);
588 if (clsRun != XX)
589 {
590 SetDeferredRun(pcls, cchRun, ich, clsRun);
591 cchRun = 0;
592 }
593
594 /* resolve the directionality class at the current location */
595 clsNew = GetResolvedType(action);
596 if (clsNew != XX)
597 pcls[ich] = clsNew;
598
599 /* increment a deferred run */
600 if (IX & action)
601 cchRun++;
602
603 state = stateWeak[state][cls];
604 }
605
606 /* resolve any deferred runs
607 * use the direction of the current level to emulate PDF */
608 cls = EmbeddingDirection(level);
609
610 /* resolve the directionality for deferred runs */
611 clsRun = GetDeferredType(actionWeak[state][cls]);
612 if (clsRun != XX)
613 SetDeferredRun(pcls, cchRun, ich, clsRun);
614 }
615
616 /* RESOLVE NEUTRAL TYPES */
617
618 /* action values */
619 enum neutralactions
620 {
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 */
628 };
629
630 static int GetDeferredNeutrals(int action, int level)
631 {
632 action = (action >> 4) & 0xF;
633 if (action == (En >> 4))
634 return EmbeddingDirection(level);
635 else
636 return action;
637 }
638
639 static int GetResolvedNeutrals(int action)
640 {
641 action = action & 0xF;
642 if (action == In)
643 return 0;
644 else
645 return action;
646 }
647
648 /* state values */
649 enum resolvestates
650 {
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 */
658 } ;
659
660
661 /*------------------------------------------------------------------------
662 Notes:
663
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
666 as L.
667
668 This leads to the need for 'a' and 'na' states.
669 ------------------------------------------------------------------------*/
670
671 static const int actionNeutrals[][5] =
672 {
673 /* N, L, R, AN, EN = cls */
674 { In, 0, 0, 0, 0 }, /* r right */
675 { In, 0, 0, 0, L }, /* l left */
676
677 { In, En, Rn, Rn, Rn }, /* rn N preceded by right */
678 { In, Ln, En, En, LnL}, /* ln N preceded by left */
679
680 { In, 0, 0, 0, L }, /* a AN preceded by left */
681 { In, En, Rn, Rn, En }, /* na N preceded by a */
682 } ;
683
684 static const int stateNeutrals[][5] =
685 {
686 /* N, L, R, AN, EN */
687 { rn, l, r, r, r }, /* r right */
688 { ln, l, r, a, l }, /* l left */
689
690 { rn, l, r, r, r }, /* rn N preceded by right */
691 { ln, l, r, a, l }, /* ln N preceded by left */
692
693 { na, l, r, a, l }, /* a AN preceded by left */
694 { na, l, r, a, l }, /* na N preceded by la */
695 } ;
696
697 /*------------------------------------------------------------------------
698 Function: resolveNeutrals
699
700 Resolves the directionality of neutral character types.
701
702 Implements rules W7, N1 and N2 of the Unicode Bidi Algorithm.
703
704 Input: Array of embedding levels
705 Character count
706 Baselevel
707
708 In/Out: Array of directional classes
709
710 Note: On input only these directional classes are expected
711 R, L, N, AN, EN and BN
712
713 W8 resolves a number of ENs to L
714 ------------------------------------------------------------------------*/
715 static void resolveNeutrals(int baselevel, WORD *pcls, const WORD *plevel, int cch)
716 {
717 /* the state at the start of text depends on the base level */
718 int state = odd(baselevel) ? r : l;
719 int cls;
720
721 int cchRun = 0;
722 int level = baselevel;
723
724 int action, clsRun, clsNew;
725 int ich = 0;
726 for (; ich < cch; ich++)
727 {
728 /* ignore boundary neutrals */
729 if (pcls[ich] == BN)
730 {
731 /* include in the count for a deferred run */
732 if (cchRun)
733 cchRun++;
734
735 /* skip any further processing */
736 continue;
737 }
738
739 ASSERT(pcls[ich] < 5); /* "Only N, L, R, AN, EN are allowed" */
740 cls = pcls[ich];
741
742 action = actionNeutrals[state][cls];
743
744 /* resolve the directionality for deferred runs */
745 clsRun = GetDeferredNeutrals(action, level);
746 if (clsRun != N)
747 {
748 SetDeferredRun(pcls, cchRun, ich, clsRun);
749 cchRun = 0;
750 }
751
752 /* resolve the directionality class at the current location */
753 clsNew = GetResolvedNeutrals(action);
754 if (clsNew != N)
755 pcls[ich] = clsNew;
756
757 if (In & action)
758 cchRun++;
759
760 state = stateNeutrals[state][cls];
761 level = plevel[ich];
762 }
763
764 /* resolve any deferred runs */
765 cls = EmbeddingDirection(level); /* eor has type of current level */
766
767 /* resolve the directionality for deferred runs */
768 clsRun = GetDeferredNeutrals(actionNeutrals[state][cls], level);
769 if (clsRun != N)
770 SetDeferredRun(pcls, cchRun, ich, clsRun);
771 }
772
773 /* RESOLVE IMPLICIT */
774
775 /*------------------------------------------------------------------------
776 Function: resolveImplicit
777
778 Recursively resolves implicit embedding levels.
779 Implements rules I1 and I2 of the Unicode Bidirectional Algorithm.
780
781 Input: Array of direction classes
782 Character count
783 Base level
784
785 In/Out: Array of embedding levels
786
787 Note: levels may exceed 15 on output.
788 Accepted subset of direction classes
789 R, L, AN, EN
790 ------------------------------------------------------------------------*/
791 static const WORD addLevel[][4] =
792 {
793 /* L, R, AN, EN */
794 /* even */ { 0, 1, 2, 2, },
795 /* odd */ { 1, 0, 1, 1, }
796
797 };
798
799 static void resolveImplicit(const WORD * pcls, WORD *plevel, int cch)
800 {
801 int ich = 0;
802 for (; ich < cch; ich++)
803 {
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 */
807 if (pcls[ich] == BN)
808 {
809 continue;
810 }
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];
814 }
815 }
816
817 /* REORDER */
818 /*------------------------------------------------------------------------
819 Function: resolveLines
820
821 Breaks a paragraph into lines
822
823 Input: Character count
824 In/Out: Array of characters
825 Array of line break flags
826
827 Returns the count of characters on the first line
828
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)
835 {
836 /* skip characters not of type LS */
837 int ich = 0;
838 for(; ich < cch; ich++)
839 {
840 if (pszInput[ich] == (WCHAR)'\n' || (pbrk && pbrk[ich]))
841 {
842 ich++;
843 break;
844 }
845 }
846
847 return ich;
848 }
849
850 /*------------------------------------------------------------------------
851 Function: resolveWhiteSpace
852
853 Resolves levels for WS and S
854 Implements rule L1 of the Unicode bidi Algorithm.
855
856 Input: Base embedding level
857 Character count
858 Array of direction classes (for one line of text)
859
860 In/Out: Array of embedding levels (for one line of text)
861
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)
868 {
869 int cchrun = 0;
870 int oldlevel = baselevel;
871
872 int ich = 0;
873 for (; ich < cch; ich++)
874 {
875 switch(pcls[ich])
876 {
877 default:
878 cchrun = 0; /* any other character breaks the run */
879 break;
880 case WS:
881 cchrun++;
882 break;
883
884 case RLE:
885 case LRE:
886 case LRO:
887 case RLO:
888 case PDF:
889 case BN:
890 plevel[ich] = oldlevel;
891 cchrun++;
892 break;
893
894 case S:
895 case B:
896 /* reset levels for WS before eot */
897 SetDeferredRun(plevel, cchrun, ich, baselevel);
898 cchrun = 0;
899 plevel[ich] = baselevel;
900 break;
901 }
902 oldlevel = plevel[ich];
903 }
904 /* reset level before eot */
905 SetDeferredRun(plevel, cchrun, ich, baselevel);
906 }
907
908
909 /*------------------------------------------------------------------------
910 Functions: reorder/reorderLevel
911
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"
915
916 Implements rule L2 of the Unicode bidi Algorithm.
917
918 Input: Array of embedding levels
919 Character count
920 Flag enabling reversal (set to false by initial caller)
921
922 In/Out: Text to reorder
923
924 Note: levels may exceed 15 resp. 61 on input.
925
926 Rule L3 - reorder combining marks is not implemented here
927 Rule L4 - glyph mirroring is implemented as a display option below
928
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)
932 {
933 int ich = 0;
934
935 /* true as soon as first odd level encountered */
936 fReverse = fReverse || odd(level);
937
938 for (; ich < cch; ich++)
939 {
940 if (plevel[ich] < level)
941 {
942 break;
943 }
944 else if (plevel[ich] > level)
945 {
946 ich += reorderLevel(level + 1, pszText + ich, plevel + ich,
947 cch - ich, fReverse) - 1;
948 }
949 }
950 if (fReverse)
951 {
952 reverse(pszText, ich);
953 }
954 return ich;
955 }
956
957 static int reorder(int baselevel, LPWSTR pszText, const WORD* plevel, int cch)
958 {
959 int ich = 0;
960
961 while (ich < cch)
962 {
963 ich += reorderLevel(baselevel, pszText + ich, plevel + ich,
964 cch - ich, FALSE);
965 }
966 return ich;
967 }
968
969 /* DISPLAY OPTIONS */
970 /*-----------------------------------------------------------------------
971 Function: mirror
972
973 Crudely implements rule L4 of the Unicode Bidirectional Algorithm
974 Demonstrate mirrored brackets, braces and parens
975
976
977 Input: Array of levels
978 Count of characters
979
980 In/Out: Array of characters (should be array of glyph ids)
981
982 Note;
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)
987 {
988 static int warn_once;
989 int i;
990
991 for (i = 0; i < cch; ++i)
992 {
993 if (!odd(plevel[i]))
994 continue;
995 /* This needs the data from http://www.unicode.org/Public/UNIDATA/BidiMirroring.txt */
996 if (!warn_once++)
997 FIXME("stub: mirroring of characters not yet implemented\n");
998 break;
999 }
1000 }
1001
1002 /*------------------------------------------------------------------------
1003 Function: BidiLines
1004
1005 Implements the Line-by-Line phases of the Unicode Bidi Algorithm
1006
1007 Input: Count of characters
1008 flag whether to mirror
1009
1010 Inp/Out: Input text
1011 Array of character directions
1012 Array of levels
1013
1014 ------------------------------------------------------------------------*/
1015 static void BidiLines(int baselevel, LPWSTR pszOutLine, LPCWSTR pszLine, WORD * pclsLine,
1016 WORD * plevelLine, int cchPara, int fMirror, BOOL * pbrk)
1017 {
1018 int cchLine = 0;
1019
1020 do
1021 {
1022 /* break lines at LS */
1023 cchLine = resolveLines(pszLine, pbrk, cchPara);
1024
1025 /* resolve whitespace */
1026 resolveWhitespace(baselevel, pclsLine, plevelLine, cchLine);
1027
1028 if (pszOutLine)
1029 {
1030 if (fMirror)
1031 mirror(pszOutLine, plevelLine, cchLine);
1032
1033 /* reorder each line in place */
1034 reorder(baselevel, pszOutLine, plevelLine, cchLine);
1035 }
1036
1037 pszLine += cchLine;
1038 plevelLine += cchLine;
1039 pbrk += pbrk ? cchLine : 0;
1040 pclsLine += cchLine;
1041 cchPara -= cchLine;
1042
1043 } while (cchPara);
1044 }
1045
1046 /*************************************************************
1047 * BIDI_Reorder
1048 */
1049 BOOL BIDI_Reorder(
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 */
1057 )
1058 {
1059 WORD *levels;
1060 WORD *chartype;
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);
1065
1066 if (!(dwFlags & GCP_REORDER))
1067 {
1068 FIXME("Asked to reorder without reorder flag set\n");
1069 return FALSE;
1070 }
1071
1072 if (uCountOut < uCount)
1073 {
1074 FIXME("lpOutString too small\n");
1075 return FALSE;
1076 }
1077
1078 chartype = HeapAlloc(GetProcessHeap(), 0, uCount * 2 * sizeof(WORD));
1079 levels = chartype + uCount;
1080 if (!chartype)
1081 {
1082 WARN("Out of memory\n");
1083 return FALSE;
1084 }
1085
1086 if (lpOutString)
1087 memcpy(lpOutString, lpString, uCount * sizeof(WCHAR));
1088
1089 if (WINE_GCPW_FORCE_RTL == (dwWineGCP_Flags&WINE_GCPW_DIR_MASK))
1090 baselevel = 1;
1091
1092 done = 0;
1093 while (done < uCount)
1094 {
1095 unsigned j;
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)
1100 switch(chartype[j])
1101 {
1102 case B:
1103 case S:
1104 case WS:
1105 case ON: chartype[j] = N;
1106 default: continue;
1107 }
1108
1109 if ((dwWineGCP_Flags&WINE_GCPW_DIR_MASK) == WINE_GCPW_LOOSE_RTL)
1110 baselevel = 1;
1111 else if ((dwWineGCP_Flags&WINE_GCPW_DIR_MASK) == WINE_GCPW_LOOSE_LTR)
1112 baselevel = 0;
1113
1114 if (dwWineGCP_Flags & WINE_GCPW_LOOSE_MASK)
1115 {
1116 for (j = 0; j < i; ++j)
1117 if (chartype[j] == L)
1118 {
1119 baselevel = 0;
1120 break;
1121 }
1122 else if (chartype[j] == R || chartype[j] == AL)
1123 {
1124 baselevel = 1;
1125 break;
1126 }
1127 }
1128
1129 /* resolve explicit */
1130 resolveExplicit(baselevel, N, chartype, levels, i, 0);
1131
1132 /* resolve weak */
1133 resolveWeak(baselevel, chartype, levels, i);
1134
1135 /* resolve neutrals */
1136 resolveNeutrals(baselevel, chartype, levels, i);
1137
1138 /* resolveImplicit */
1139 resolveImplicit(chartype, levels, i);
1140
1141 /* assign directional types again, but for WS, S this time */
1142 classify(lpString + done, chartype, i);
1143
1144 BidiLines(baselevel, lpOutString ? lpOutString + done : NULL, lpString + done,
1145 chartype, levels, i, !(dwFlags & GCP_SYMSWAPOFF), 0);
1146
1147 if (lpOrder)
1148 {
1149 int k, lastgood;
1150 for (j = lastgood = 0; j < i; ++j)
1151 if (levels[j] != levels[lastgood])
1152 {
1153 --j;
1154 if (odd(levels[lastgood]))
1155 for (k = j; k >= lastgood; --k)
1156 lpOrder[done + k] = done + j - k;
1157 else
1158 for (k = lastgood; k <= j; ++k)
1159 lpOrder[done + k] = done + k;
1160 lastgood = ++j;
1161 }
1162 if (odd(levels[lastgood]))
1163 for (k = j - 1; k >= lastgood; --k)
1164 lpOrder[done + k] = done + j - 1 - k;
1165 else
1166 for (k = lastgood; k < j; ++k)
1167 lpOrder[done + k] = done + k;
1168 }
1169 done += i;
1170 }
1171
1172 HeapFree(GetProcessHeap(), 0, chartype);
1173 return TRUE;
1174 }
1175
This page was automatically generated by the
LXR engine.
Visit the LXR main site for more
information.