[USP10]
[reactos.git] / reactos / dll / win32 / usp10 / bidi.c
1 /*
2 * Uniscribe BiDirectional handling
3 *
4 * Copyright 2003 Shachar Shemesh
5 * Copyright 2007 Maarten Lankhorst
6 * Copyright 2010 CodeWeavers, Aric Stewart
7 *
8 * This library is free software; you can redistribute it and/or
9 * modify it under the terms of the GNU Lesser General Public
10 * License as published by the Free Software Foundation; either
11 * version 2.1 of the License, or (at your option) any later version.
12 *
13 * This library is distributed in the hope that it will be useful,
14 * but WITHOUT ANY WARRANTY; without even the implied warranty of
15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
16 * Lesser General Public License for more details.
17 *
18 * You should have received a copy of the GNU Lesser General Public
19 * License along with this library; if not, write to the Free Software
20 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA
21 *
22 * Code derived from the modified reference implementation
23 * that was found in revision 17 of http://unicode.org/reports/tr9/
24 * "Unicode Standard Annex #9: THE BIDIRECTIONAL ALGORITHM"
25 *
26 * -- Copyright (C) 1999-2005, ASMUS, Inc.
27 *
28 * Permission is hereby granted, free of charge, to any person obtaining a
29 * copy of the Unicode data files and any associated documentation (the
30 * "Data Files") or Unicode software and any associated documentation (the
31 * "Software") to deal in the Data Files or Software without restriction,
32 * including without limitation the rights to use, copy, modify, merge,
33 * publish, distribute, and/or sell copies of the Data Files or Software,
34 * and to permit persons to whom the Data Files or Software are furnished
35 * to do so, provided that (a) the above copyright notice(s) and this
36 * permission notice appear with all copies of the Data Files or Software,
37 * (b) both the above copyright notice(s) and this permission notice appear
38 * in associated documentation, and (c) there is clear notice in each
39 * modified Data File or in the Software as well as in the documentation
40 * associated with the Data File(s) or Software that the data or software
41 * has been modified.
42 */
43
44 #include "usp10_internal.h"
45
46 WINE_DEFAULT_DEBUG_CHANNEL(bidi);
47
48 #define ASSERT(x) do { if (!(x)) FIXME("assert failed: %s\n", #x); } while(0)
49 #define MAX_LEVEL 61
50
51 /* HELPER FUNCTIONS AND DECLARATIONS */
52
53 /*------------------------------------------------------------------------
54 Bidirectional Character Types
55
56 as defined by the Unicode Bidirectional Algorithm Table 3-7.
57
58 Note:
59
60 The list of bidirectional character types here is not grouped the
61 same way as the table 3-7, since the numberic values for the types
62 are chosen to keep the state and action tables compact.
63 ------------------------------------------------------------------------*/
64 enum directions
65 {
66 /* input types */
67 /* ON MUST be zero, code relies on ON = N = 0 */
68 ON = 0, /* Other Neutral */
69 L, /* Left Letter */
70 R, /* Right Letter */
71 AN, /* Arabic Number */
72 EN, /* European Number */
73 AL, /* Arabic Letter (Right-to-left) */
74 NSM, /* Non-spacing Mark */
75 CS, /* Common Separator */
76 ES, /* European Separator */
77 ET, /* European Terminator (post/prefix e.g. $ and %) */
78
79 /* resolved types */
80 BN, /* Boundary neutral (type of RLE etc after explicit levels) */
81
82 /* input types, */
83 S, /* Segment Separator (TAB) // used only in L1 */
84 WS, /* White space // used only in L1 */
85 B, /* Paragraph Separator (aka as PS) */
86
87 /* types for explicit controls */
88 RLO, /* these are used only in X1-X9 */
89 RLE,
90 LRO,
91 LRE,
92 PDF,
93
94 /* resolved types, also resolved directions */
95 N = ON, /* alias, where ON, WS and S are treated the same */
96 };
97
98 /* HELPER FUNCTIONS */
99
100 /* Convert the libwine information to the direction enum */
101 static void classify(LPCWSTR lpString, WORD *chartype, DWORD uCount, const SCRIPT_CONTROL *c)
102 {
103 static const enum directions dir_map[16] =
104 {
105 L, /* unassigned defaults to L */
106 L,
107 R,
108 EN,
109 ES,
110 ET,
111 AN,
112 CS,
113 B,
114 S,
115 WS,
116 ON,
117 AL,
118 NSM,
119 BN,
120 PDF /* also LRE, LRO, RLE, RLO */
121 };
122
123 unsigned i;
124
125 for (i = 0; i < uCount; ++i)
126 {
127 chartype[i] = dir_map[get_char_typeW(lpString[i]) >> 12];
128 switch (chartype[i])
129 {
130 case ES:
131 if (!c->fLegacyBidiClass) break;
132 switch (lpString[i])
133 {
134 case '-':
135 case '+': chartype[i] = N; break;
136 case '/': chartype[i] = CS; break;
137 }
138 break;
139 case PDF:
140 switch (lpString[i])
141 {
142 case 0x202A: chartype[i] = LRE; break;
143 case 0x202B: chartype[i] = RLE; break;
144 case 0x202C: chartype[i] = PDF; break;
145 case 0x202D: chartype[i] = LRO; break;
146 case 0x202E: chartype[i] = RLO; break;
147 }
148 break;
149 }
150 }
151 }
152
153 /* Set a run of cval values at locations all prior to, but not including */
154 /* iStart, to the new value nval. */
155 static void SetDeferredRun(WORD *pval, int cval, int iStart, int nval)
156 {
157 int i = iStart - 1;
158 for (; i >= iStart - cval; i--)
159 {
160 pval[i] = nval;
161 }
162 }
163
164 /* RESOLVE EXPLICIT */
165
166 static WORD GreaterEven(int i)
167 {
168 return odd(i) ? i + 1 : i + 2;
169 }
170
171 static WORD GreaterOdd(int i)
172 {
173 return odd(i) ? i + 2 : i + 1;
174 }
175
176 static WORD EmbeddingDirection(int level)
177 {
178 return odd(level) ? R : L;
179 }
180
181 /*------------------------------------------------------------------------
182 Function: resolveExplicit
183
184 Recursively resolves explicit embedding levels and overrides.
185 Implements rules X1-X9, of the Unicode Bidirectional Algorithm.
186
187 Input: Base embedding level and direction
188 Character count
189
190 Output: Array of embedding levels
191
192 In/Out: Array of direction classes
193
194
195 Note: The function uses two simple counters to keep track of
196 matching explicit codes and PDF. Use the default argument for
197 the outermost call. The nesting counter counts the recursion
198 depth and not the embedding level.
199 ------------------------------------------------------------------------*/
200
201 static int resolveExplicit(int level, int dir, WORD *pcls, WORD *plevel, int cch, int nNest)
202 {
203 /* always called with a valid nesting level
204 nesting levels are != embedding levels */
205 int nLastValid = nNest;
206 int ich = 0;
207
208 /* check input values */
209 ASSERT(nNest >= 0 && level >= 0 && level <= MAX_LEVEL);
210
211 /* process the text */
212 for (; ich < cch; ich++)
213 {
214 WORD cls = pcls[ich];
215 switch (cls)
216 {
217 case LRO:
218 case LRE:
219 nNest++;
220 if (GreaterEven(level) <= MAX_LEVEL - (cls == LRO ? 2 : 0))
221 {
222 plevel[ich] = GreaterEven(level);
223 pcls[ich] = BN;
224 ich += resolveExplicit(plevel[ich], (cls == LRE ? N : L),
225 &pcls[ich+1], &plevel[ich+1],
226 cch - (ich+1), nNest);
227 nNest--;
228 continue;
229 }
230 cls = pcls[ich] = BN;
231 break;
232
233 case RLO:
234 case RLE:
235 nNest++;
236 if (GreaterOdd(level) <= MAX_LEVEL - (cls == RLO ? 2 : 0))
237 {
238 plevel[ich] = GreaterOdd(level);
239 pcls[ich] = BN;
240 ich += resolveExplicit(plevel[ich], (cls == RLE ? N : R),
241 &pcls[ich+1], &plevel[ich+1],
242 cch - (ich+1), nNest);
243 nNest--;
244 continue;
245 }
246 cls = pcls[ich] = BN;
247 break;
248
249 case PDF:
250 cls = pcls[ich] = BN;
251 if (nNest)
252 {
253 if (nLastValid < nNest)
254 {
255 nNest--;
256 }
257 else
258 {
259 cch = ich; /* break the loop, but complete body */
260 }
261 }
262 }
263
264 /* Apply the override */
265 if (dir != N)
266 {
267 cls = dir;
268 }
269 plevel[ich] = level;
270 if (pcls[ich] != BN)
271 pcls[ich] = cls;
272 }
273
274 return ich;
275 }
276
277 /* RESOLVE WEAK TYPES */
278
279 enum states /* possible states */
280 {
281 xa, /* Arabic letter */
282 xr, /* right letter */
283 xl, /* left letter */
284
285 ao, /* Arabic lett. foll by ON */
286 ro, /* right lett. foll by ON */
287 lo, /* left lett. foll by ON */
288
289 rt, /* ET following R */
290 lt, /* ET following L */
291
292 cn, /* EN, AN following AL */
293 ra, /* Arabic number foll R */
294 re, /* European number foll R */
295 la, /* Arabic number foll L */
296 le, /* European number foll L */
297
298 ac, /* CS following cn */
299 rc, /* CS following ra */
300 rs, /* CS,ES following re */
301 lc, /* CS following la */
302 ls, /* CS,ES following le */
303
304 ret, /* ET following re */
305 let, /* ET following le */
306 } ;
307
308 static const int stateWeak[][10] =
309 {
310 /* N, L, R, AN, EN, AL,NSM, CS, ES, ET */
311 /*xa*/ { ao, xl, xr, cn, cn, xa, xa, ao, ao, ao }, /* Arabic letter */
312 /*xr*/ { ro, xl, xr, ra, re, xa, xr, ro, ro, rt }, /* right letter */
313 /*xl*/ { lo, xl, xr, la, le, xa, xl, lo, lo, lt }, /* left letter */
314
315 /*ao*/ { ao, xl, xr, cn, cn, xa, ao, ao, ao, ao }, /* Arabic lett. foll by ON*/
316 /*ro*/ { ro, xl, xr, ra, re, xa, ro, ro, ro, rt }, /* right lett. foll by ON */
317 /*lo*/ { lo, xl, xr, la, le, xa, lo, lo, lo, lt }, /* left lett. foll by ON */
318
319 /*rt*/ { ro, xl, xr, ra, re, xa, rt, ro, ro, rt }, /* ET following R */
320 /*lt*/ { lo, xl, xr, la, le, xa, lt, lo, lo, lt }, /* ET following L */
321
322 /*cn*/ { ao, xl, xr, cn, cn, xa, cn, ac, ao, ao }, /* EN, AN following AL */
323 /*ra*/ { ro, xl, xr, ra, re, xa, ra, rc, ro, rt }, /* Arabic number foll R */
324 /*re*/ { ro, xl, xr, ra, re, xa, re, rs, rs,ret }, /* European number foll R */
325 /*la*/ { lo, xl, xr, la, le, xa, la, lc, lo, lt }, /* Arabic number foll L */
326 /*le*/ { lo, xl, xr, la, le, xa, le, ls, ls,let }, /* European number foll L */
327
328 /*ac*/ { ao, xl, xr, cn, cn, xa, ao, ao, ao, ao }, /* CS following cn */
329 /*rc*/ { ro, xl, xr, ra, re, xa, ro, ro, ro, rt }, /* CS following ra */
330 /*rs*/ { ro, xl, xr, ra, re, xa, ro, ro, ro, rt }, /* CS,ES following re */
331 /*lc*/ { lo, xl, xr, la, le, xa, lo, lo, lo, lt }, /* CS following la */
332 /*ls*/ { lo, xl, xr, la, le, xa, lo, lo, lo, lt }, /* CS,ES following le */
333
334 /*ret*/{ ro, xl, xr, ra, re, xa,ret, ro, ro,ret }, /* ET following re */
335 /*let*/{ lo, xl, xr, la, le, xa,let, lo, lo,let }, /* ET following le */
336 };
337
338 enum actions /* possible actions */
339 {
340 /* primitives */
341 IX = 0x100, /* increment */
342 XX = 0xF, /* no-op */
343
344 /* actions */
345 xxx = (XX << 4) + XX, /* no-op */
346 xIx = IX + xxx, /* increment run */
347 xxN = (XX << 4) + ON, /* set current to N */
348 xxE = (XX << 4) + EN, /* set current to EN */
349 xxA = (XX << 4) + AN, /* set current to AN */
350 xxR = (XX << 4) + R, /* set current to R */
351 xxL = (XX << 4) + L, /* set current to L */
352 Nxx = (ON << 4) + 0xF, /* set run to neutral */
353 Axx = (AN << 4) + 0xF, /* set run to AN */
354 ExE = (EN << 4) + EN, /* set run to EN, set current to EN */
355 NIx = (ON << 4) + 0xF + IX, /* set run to N, increment */
356 NxN = (ON << 4) + ON, /* set run to N, set current to N */
357 NxR = (ON << 4) + R, /* set run to N, set current to R */
358 NxE = (ON << 4) + EN, /* set run to N, set current to EN */
359
360 AxA = (AN << 4) + AN, /* set run to AN, set current to AN */
361 NxL = (ON << 4) + L, /* set run to N, set current to L */
362 LxL = (L << 4) + L, /* set run to L, set current to L */
363 } ;
364
365 static const int actionWeak[][10] =
366 {
367 /* N, L, R, AN, EN, AL, NSM, CS, ES, ET */
368 /*xa*/ { xxx, xxx, xxx, xxx, xxA, xxR, xxR, xxN, xxN, xxN }, /* Arabic letter */
369 /*xr*/ { xxx, xxx, xxx, xxx, xxE, xxR, xxR, xxN, xxN, xIx }, /* right letter */
370 /*xl*/ { xxx, xxx, xxx, xxx, xxL, xxR, xxL, xxN, xxN, xIx }, /* left letter */
371
372 /*ao*/ { xxx, xxx, xxx, xxx, xxA, xxR, xxN, xxN, xxN, xxN }, /* Arabic lett. foll by ON */
373 /*ro*/ { xxx, xxx, xxx, xxx, xxE, xxR, xxN, xxN, xxN, xIx }, /* right lett. foll by ON */
374 /*lo*/ { xxx, xxx, xxx, xxx, xxL, xxR, xxN, xxN, xxN, xIx }, /* left lett. foll by ON */
375
376 /*rt*/ { Nxx, Nxx, Nxx, Nxx, ExE, NxR, xIx, NxN, NxN, xIx }, /* ET following R */
377 /*lt*/ { Nxx, Nxx, Nxx, Nxx, LxL, NxR, xIx, NxN, NxN, xIx }, /* ET following L */
378
379 /*cn*/ { xxx, xxx, xxx, xxx, xxA, xxR, xxA, xIx, xxN, xxN }, /* EN, AN following AL */
380 /*ra*/ { xxx, xxx, xxx, xxx, xxE, xxR, xxA, xIx, xxN, xIx }, /* Arabic number foll R */
381 /*re*/ { xxx, xxx, xxx, xxx, xxE, xxR, xxE, xIx, xIx, xxE }, /* European number foll R */
382 /*la*/ { xxx, xxx, xxx, xxx, xxL, xxR, xxA, xIx, xxN, xIx }, /* Arabic number foll L */
383 /*le*/ { xxx, xxx, xxx, xxx, xxL, xxR, xxL, xIx, xIx, xxL }, /* European number foll L */
384
385 /*ac*/ { Nxx, Nxx, Nxx, Axx, AxA, NxR, NxN, NxN, NxN, NxN }, /* CS following cn */
386 /*rc*/ { Nxx, Nxx, Nxx, Axx, NxE, NxR, NxN, NxN, NxN, NIx }, /* CS following ra */
387 /*rs*/ { Nxx, Nxx, Nxx, Nxx, ExE, NxR, NxN, NxN, NxN, NIx }, /* CS,ES following re */
388 /*lc*/ { Nxx, Nxx, Nxx, Axx, NxL, NxR, NxN, NxN, NxN, NIx }, /* CS following la */
389 /*ls*/ { Nxx, Nxx, Nxx, Nxx, LxL, NxR, NxN, NxN, NxN, NIx }, /* CS,ES following le */
390
391 /*ret*/{ xxx, xxx, xxx, xxx, xxE, xxR, xxE, xxN, xxN, xxE }, /* ET following re */
392 /*let*/{ xxx, xxx, xxx, xxx, xxL, xxR, xxL, xxN, xxN, xxL }, /* ET following le */
393 };
394
395 static int GetDeferredType(int action)
396 {
397 return (action >> 4) & 0xF;
398 }
399
400 static int GetResolvedType(int action)
401 {
402 return action & 0xF;
403 }
404
405 /* Note on action table:
406
407 States can be of two kinds:
408 - Immediate Resolution State, where each input token
409 is resolved as soon as it is seen. These states have
410 only single action codes (xxN) or the no-op (xxx)
411 for static input tokens.
412 - Deferred Resolution State, where input tokens either
413 either extend the run (xIx) or resolve its Type (e.g. Nxx).
414
415 Input classes are of three kinds
416 - Static Input Token, where the class of the token remains
417 unchanged on output (AN, L, N, R)
418 - Replaced Input Token, where the class of the token is
419 always replaced on output (AL, BN, NSM, CS, ES, ET)
420 - Conditional Input Token, where the class of the token is
421 changed on output in some, but not all, cases (EN)
422
423 Where tokens are subject to change, a double action
424 (e.g. NxA, or NxN) is _required_ after deferred states,
425 resolving both the deferred state and changing the current token.
426 */
427
428 /*------------------------------------------------------------------------
429 Function: resolveWeak
430
431 Resolves the directionality of numeric and other weak character types
432
433 Implements rules X10 and W1-W6 of the Unicode Bidirectional Algorithm.
434
435 Input: Array of embedding levels
436 Character count
437
438 In/Out: Array of directional classes
439
440 Note: On input only these directional classes are expected
441 AL, HL, R, L, ON, BN, NSM, AN, EN, ES, ET, CS,
442 ------------------------------------------------------------------------*/
443 static void resolveWeak(int baselevel, WORD *pcls, WORD *plevel, int cch)
444 {
445 int state = odd(baselevel) ? xr : xl;
446 int cls;
447
448 int level = baselevel;
449 int action, clsRun, clsNew;
450 int cchRun = 0;
451 int ich = 0;
452
453 for (; ich < cch; ich++)
454 {
455 /* ignore boundary neutrals */
456 if (pcls[ich] == BN)
457 {
458 /* must flatten levels unless at a level change; */
459 plevel[ich] = level;
460
461 /* lookahead for level changes */
462 if (ich + 1 == cch && level != baselevel)
463 {
464 /* have to fixup last BN before end of the loop, since
465 * its fix-upped value will be needed below the assert */
466 pcls[ich] = EmbeddingDirection(level);
467 }
468 else if (ich + 1 < cch && level != plevel[ich+1] && pcls[ich+1] != BN)
469 {
470 /* fixup LAST BN in front / after a level run to make
471 * it act like the SOR/EOR in rule X10 */
472 int newlevel = plevel[ich+1];
473 if (level > newlevel) {
474 newlevel = level;
475 }
476 plevel[ich] = newlevel;
477
478 /* must match assigned level */
479 pcls[ich] = EmbeddingDirection(newlevel);
480 level = plevel[ich+1];
481 }
482 else
483 {
484 /* don't interrupt runs */
485 if (cchRun)
486 {
487 cchRun++;
488 }
489 continue;
490 }
491 }
492
493 ASSERT(pcls[ich] <= BN);
494 cls = pcls[ich];
495
496 action = actionWeak[state][cls];
497
498 /* resolve the directionality for deferred runs */
499 clsRun = GetDeferredType(action);
500 if (clsRun != XX)
501 {
502 SetDeferredRun(pcls, cchRun, ich, clsRun);
503 cchRun = 0;
504 }
505
506 /* resolve the directionality class at the current location */
507 clsNew = GetResolvedType(action);
508 if (clsNew != XX)
509 pcls[ich] = clsNew;
510
511 /* increment a deferred run */
512 if (IX & action)
513 cchRun++;
514
515 state = stateWeak[state][cls];
516 }
517
518 /* resolve any deferred runs
519 * use the direction of the current level to emulate PDF */
520 cls = EmbeddingDirection(level);
521
522 /* resolve the directionality for deferred runs */
523 clsRun = GetDeferredType(actionWeak[state][cls]);
524 if (clsRun != XX)
525 SetDeferredRun(pcls, cchRun, ich, clsRun);
526 }
527
528 /* RESOLVE NEUTRAL TYPES */
529
530 /* action values */
531 enum neutralactions
532 {
533 /* action to resolve previous input */
534 nL = L, /* resolve EN to L */
535 En = 3 << 4, /* resolve neutrals run to embedding level direction */
536 Rn = R << 4, /* resolve neutrals run to strong right */
537 Ln = L << 4, /* resolved neutrals run to strong left */
538 In = (1<<8), /* increment count of deferred neutrals */
539 LnL = (1<<4)+L, /* set run and EN to L */
540 };
541
542 static int GetDeferredNeutrals(int action, int level)
543 {
544 action = (action >> 4) & 0xF;
545 if (action == (En >> 4))
546 return EmbeddingDirection(level);
547 else
548 return action;
549 }
550
551 static int GetResolvedNeutrals(int action)
552 {
553 action = action & 0xF;
554 if (action == In)
555 return 0;
556 else
557 return action;
558 }
559
560 /* state values */
561 enum resolvestates
562 {
563 /* new temporary class */
564 r, /* R and characters resolved to R */
565 l, /* L and characters resolved to L */
566 rn, /* N preceded by right */
567 ln, /* N preceded by left */
568 a, /* AN preceded by left (the abbreviation 'la' is used up above) */
569 na, /* N preceded by a */
570 } ;
571
572
573 /*------------------------------------------------------------------------
574 Notes:
575
576 By rule W7, whenever a EN is 'dominated' by an L (including start of
577 run with embedding direction = L) it is resolved to, and further treated
578 as L.
579
580 This leads to the need for 'a' and 'na' states.
581 ------------------------------------------------------------------------*/
582
583 static const int actionNeutrals[][5] =
584 {
585 /* N, L, R, AN, EN = cls */
586 { In, 0, 0, 0, 0 }, /* r right */
587 { In, 0, 0, 0, L }, /* l left */
588
589 { In, En, Rn, Rn, Rn }, /* rn N preceded by right */
590 { In, Ln, En, En, LnL}, /* ln N preceded by left */
591
592 { In, 0, 0, 0, L }, /* a AN preceded by left */
593 { In, En, Rn, Rn, En }, /* na N preceded by a */
594 } ;
595
596 static const int stateNeutrals[][5] =
597 {
598 /* N, L, R, AN, EN */
599 { rn, l, r, r, r }, /* r right */
600 { ln, l, r, a, l }, /* l left */
601
602 { rn, l, r, r, r }, /* rn N preceded by right */
603 { ln, l, r, a, l }, /* ln N preceded by left */
604
605 { na, l, r, a, l }, /* a AN preceded by left */
606 { na, l, r, a, l }, /* na N preceded by la */
607 } ;
608
609 /*------------------------------------------------------------------------
610 Function: resolveNeutrals
611
612 Resolves the directionality of neutral character types.
613
614 Implements rules W7, N1 and N2 of the Unicode Bidi Algorithm.
615
616 Input: Array of embedding levels
617 Character count
618 Baselevel
619
620 In/Out: Array of directional classes
621
622 Note: On input only these directional classes are expected
623 R, L, N, AN, EN and BN
624
625 W8 resolves a number of ENs to L
626 ------------------------------------------------------------------------*/
627 static void resolveNeutrals(int baselevel, WORD *pcls, const WORD *plevel, int cch)
628 {
629 /* the state at the start of text depends on the base level */
630 int state = odd(baselevel) ? r : l;
631 int cls;
632
633 int cchRun = 0;
634 int level = baselevel;
635
636 int action, clsRun, clsNew;
637 int ich = 0;
638 for (; ich < cch; ich++)
639 {
640 /* ignore boundary neutrals */
641 if (pcls[ich] == BN)
642 {
643 /* include in the count for a deferred run */
644 if (cchRun)
645 cchRun++;
646
647 /* skip any further processing */
648 continue;
649 }
650
651 ASSERT(pcls[ich] < 5); /* "Only N, L, R, AN, EN are allowed" */
652 cls = pcls[ich];
653
654 action = actionNeutrals[state][cls];
655
656 /* resolve the directionality for deferred runs */
657 clsRun = GetDeferredNeutrals(action, level);
658 if (clsRun != N)
659 {
660 SetDeferredRun(pcls, cchRun, ich, clsRun);
661 cchRun = 0;
662 }
663
664 /* resolve the directionality class at the current location */
665 clsNew = GetResolvedNeutrals(action);
666 if (clsNew != N)
667 pcls[ich] = clsNew;
668
669 if (In & action)
670 cchRun++;
671
672 state = stateNeutrals[state][cls];
673 level = plevel[ich];
674 }
675
676 /* resolve any deferred runs */
677 cls = EmbeddingDirection(level); /* eor has type of current level */
678
679 /* resolve the directionality for deferred runs */
680 clsRun = GetDeferredNeutrals(actionNeutrals[state][cls], level);
681 if (clsRun != N)
682 SetDeferredRun(pcls, cchRun, ich, clsRun);
683 }
684
685 /* RESOLVE IMPLICIT */
686
687 /*------------------------------------------------------------------------
688 Function: resolveImplicit
689
690 Recursively resolves implicit embedding levels.
691 Implements rules I1 and I2 of the Unicode Bidirectional Algorithm.
692
693 Input: Array of direction classes
694 Character count
695 Base level
696
697 In/Out: Array of embedding levels
698
699 Note: levels may exceed 15 on output.
700 Accepted subset of direction classes
701 R, L, AN, EN
702 ------------------------------------------------------------------------*/
703 static const WORD addLevel[][4] =
704 {
705 /* L, R, AN, EN */
706 /* even */ { 0, 1, 2, 2, },
707 /* odd */ { 1, 0, 1, 1, }
708
709 };
710
711 static void resolveImplicit(const WORD * pcls, WORD *plevel, int cch)
712 {
713 int ich = 0;
714 for (; ich < cch; ich++)
715 {
716 /* cannot resolve bn here, since some bn were resolved to strong
717 * types in resolveWeak. To remove these we need the original
718 * types, which are available again in resolveWhiteSpace */
719 if (pcls[ich] == BN)
720 {
721 continue;
722 }
723 ASSERT(pcls[ich] > 0); /* "No Neutrals allowed to survive here." */
724 ASSERT(pcls[ich] < 5); /* "Out of range." */
725 plevel[ich] += addLevel[odd(plevel[ich])][pcls[ich] - 1];
726 }
727 }
728
729 /*************************************************************
730 * BIDI_DeterminLevels
731 */
732 BOOL BIDI_DetermineLevels(
733 LPCWSTR lpString, /* [in] The string for which information is to be returned */
734 INT uCount, /* [in] Number of WCHARs in string. */
735 const SCRIPT_STATE *s,
736 const SCRIPT_CONTROL *c,
737 WORD *lpOutLevels /* [out] final string levels */
738 )
739 {
740 WORD *chartype;
741 unsigned baselevel = 0;
742 INT j;
743 TRACE("%s, %d\n", debugstr_wn(lpString, uCount), uCount);
744
745 chartype = HeapAlloc(GetProcessHeap(), 0, uCount * sizeof(WORD));
746 if (!chartype)
747 {
748 WARN("Out of memory\n");
749 return FALSE;
750 }
751
752 baselevel = s->uBidiLevel;
753
754 classify(lpString, chartype, uCount, c);
755
756 for (j = 0; j < uCount; ++j)
757 switch(chartype[j])
758 {
759 case B:
760 case S:
761 case WS:
762 case ON: chartype[j] = N;
763 default: continue;
764 }
765
766 /* resolve explicit */
767 resolveExplicit(baselevel, N, chartype, lpOutLevels, uCount, 0);
768
769 /* resolve weak */
770 resolveWeak(baselevel, chartype, lpOutLevels, uCount);
771
772 /* resolve neutrals */
773 resolveNeutrals(baselevel, chartype, lpOutLevels, uCount);
774
775 /* resolveImplicit */
776 resolveImplicit(chartype, lpOutLevels, uCount);
777
778 HeapFree(GetProcessHeap(), 0, chartype);
779 return TRUE;
780 }
781
782 /* reverse cch indexes */
783 static void reverse(int *pidx, int cch)
784 {
785 int temp;
786 int ich = 0;
787 for (; ich < --cch; ich++)
788 {
789 temp = pidx[ich];
790 pidx[ich] = pidx[cch];
791 pidx[cch] = temp;
792 }
793 }
794
795
796 /*------------------------------------------------------------------------
797 Functions: reorder/reorderLevel
798
799 Recursively reorders the display string
800 "From the highest level down, reverse all characters at that level and
801 higher, down to the lowest odd level"
802
803 Implements rule L2 of the Unicode bidi Algorithm.
804
805 Input: Array of embedding levels
806 Character count
807 Flag enabling reversal (set to false by initial caller)
808
809 In/Out: Text to reorder
810
811 Note: levels may exceed 15 resp. 61 on input.
812
813 Rule L3 - reorder combining marks is not implemented here
814 Rule L4 - glyph mirroring is implemented as a display option below
815
816 Note: this should be applied a line at a time
817 -------------------------------------------------------------------------*/
818 int BIDI_ReorderV2lLevel(int level, int *pIndexs, const BYTE* plevel, int cch, BOOL fReverse)
819 {
820 int ich = 0;
821
822 /* true as soon as first odd level encountered */
823 fReverse = fReverse || odd(level);
824
825 for (; ich < cch; ich++)
826 {
827 if (plevel[ich] < level)
828 {
829 break;
830 }
831 else if (plevel[ich] > level)
832 {
833 ich += BIDI_ReorderV2lLevel(level + 1, pIndexs + ich, plevel + ich,
834 cch - ich, fReverse) - 1;
835 }
836 }
837 if (fReverse)
838 {
839 reverse(pIndexs, ich);
840 }
841 return ich;
842 }
843
844 /* Applies the reorder in reverse. Taking an already reordered string and returning the original */
845 int BIDI_ReorderL2vLevel(int level, int *pIndexs, const BYTE* plevel, int cch, BOOL fReverse)
846 {
847 int ich = 0;
848 int newlevel = -1;
849
850 /* true as soon as first odd level encountered */
851 fReverse = fReverse || odd(level);
852
853 for (; ich < cch; ich++)
854 {
855 if (plevel[ich] < level)
856 break;
857 else if (plevel[ich] > level)
858 newlevel = ich;
859 }
860 if (fReverse)
861 {
862 reverse(pIndexs, ich);
863 }
864
865 if (newlevel >= 0)
866 {
867 ich = 0;
868 for (; ich < cch; ich++)
869 if (plevel[ich] < level)
870 break;
871 else if (plevel[ich] > level)
872 ich += BIDI_ReorderL2vLevel(level + 1, pIndexs + ich, plevel + ich,
873 cch - ich, fReverse) - 1;
874 }
875
876 return ich;
877 }
878
879 BOOL BIDI_GetStrengths(LPCWSTR lpString, INT uCount, const SCRIPT_CONTROL *c,
880 WORD* lpStrength)
881 {
882 int i;
883 classify(lpString, lpStrength, uCount, c);
884
885 for ( i = 0; i < uCount; i++)
886 {
887 switch(lpStrength[i])
888 {
889 case L:
890 case LRE:
891 case LRO:
892 case R:
893 case AL:
894 case RLE:
895 case RLO:
896 lpStrength[i] = BIDI_STRONG;
897 break;
898 case PDF:
899 case EN:
900 case ES:
901 case ET:
902 case AN:
903 case CS:
904 case BN:
905 lpStrength[i] = BIDI_WEAK;
906 break;
907 case B:
908 case S:
909 case WS:
910 case ON:
911 default: /* Neutrals and NSM */
912 lpStrength[i] = BIDI_NEUTRAL;
913 }
914 }
915 return TRUE;
916 }