2
******************************************************************************
4
* Copyright (C) 1999-2001, International Business Machines
5
* Corporation and others. All Rights Reserved.
7
******************************************************************************
10
* tab size: 8 (not used)
13
* created on: 1999jul27
14
* created by: Markus W. Scherer
17
/* set import/export definitions */
18
#ifndef U_COMMON_IMPLEMENTATION
19
# define U_COMMON_IMPLEMENTATION
23
#include "unicode/utypes.h"
24
#include "unicode/ustring.h"
25
#include "unicode/uchar.h"
26
#include "unicode/ubidi.h"
30
* General implementation notes:
32
* Throughout the implementation, there are comments like (W2) that refer to
33
* rules of the BiDi algorithm in its version 5, in this example to the second
34
* rule of the resolution of weak types.
36
* For handling surrogate pairs, where two UChar's form one "abstract" (or UTF-32)
37
* character according to UTF-16, the second UChar gets the directional property of
38
* the entire character assigned, while the first one gets a BN, a boundary
39
* neutral, type, which is ignored by most of the algorithm according to
40
* rule (X9) and the implementation suggestions of the BiDi algorithm.
42
* Later, adjustWSLevels() will set the level for each BN to that of the
43
* following character (UChar), which results in surrogate pairs getting the
44
* same level on each of their surrogates.
46
* In a UTF-8 implementation, the same thing could be done: the last byte of
47
* a multi-byte sequence would get the "real" property, while all previous
48
* bytes of that sequence would get BN.
50
* It is not possible to assign all those parts of a character the same real
51
* property because this would fail in the resolution of weak types with rules
52
* that look at immediately surrounding types.
54
* As a related topic, this implementation does not remove Boundary Neutral
55
* types from the input, but ignores them whereever this is relevant.
56
* For example, the loop for the resolution of the weak types reads
57
* types until it finds a non-BN.
58
* Also, explicit embedding codes are neither changed into BN nor removed.
59
* They are only treated the same way real BNs are.
60
* As stated before, adjustWSLevels() takes care of them at the end.
61
* For the purpose of conformance, the levels of all these codes
64
* Note that this implementation never modifies the dirProps
65
* after the initial setup.
68
* In this implementation, the resolution of weak types (Wn),
69
* neutrals (Nn), and the assignment of the resolved level (In)
70
* are all done in one single loop, in resolveImplicitLevels().
71
* Changes of dirProp values are done on the fly, without writing
72
* them back to the dirProps array.
75
* This implementation contains code that allows to bypass steps of the
76
* algorithm that are not needed on the specific paragraph
77
* in order to speed up the most common cases considerably,
78
* like text that is entirely LTR, or RTL text without numbers.
80
* Most of this is done by setting a bit for each directional property
81
* in a flags variable and later checking for whether there are
82
* any LTR characters or any RTL characters, or both, whether
83
* there are any explicit embedding codes, etc.
85
* If the (Xn) steps are performed, then the flags are re-evaluated,
86
* because they will then not contain the embedding codes any more
87
* and will be adjusted for override codes, so that subsequently
88
* more bypassing may be possible than what the initial flags suggested.
90
* If the text is not mixed-directional, then the
91
* algorithm steps for the weak type resolution are not performed,
92
* and all levels are set to the paragraph level.
94
* If there are no explicit embedding codes, then the (Xn) steps
97
* If embedding levels are supplied as a parameter, then all
98
* explicit embedding codes are ignored, and the (Xn) steps
101
* White Space types could get the level of the run they belong to,
102
* and are checked with a test of (flags&MASK_EMBEDDING) to
103
* consider if the paragraph direction should be considered in
104
* the flags variable.
106
* If there are no White Space types in the paragraph, then
107
* (L1) is not necessary in adjustWSLevels().
110
/* prototypes --------------------------------------------------------------- */
113
getDirProps(UBiDi *pBiDi, const UChar *text);
115
static UBiDiDirection
116
resolveExplicitLevels(UBiDi *pBiDi);
118
static UBiDiDirection
119
checkExplicitLevels(UBiDi *pBiDi, UErrorCode *pErrorCode);
121
static UBiDiDirection
122
directionFromFlags(Flags flags);
125
resolveImplicitLevels(UBiDi *pBiDi,
126
UTextOffset start, UTextOffset limit,
127
DirProp sor, DirProp eor);
130
adjustWSLevels(UBiDi *pBiDi);
132
/* to avoid some conditional statements, use tiny constant arrays */
133
static const Flags flagLR[2]={ DIRPROP_FLAG(L), DIRPROP_FLAG(R) };
134
static const Flags flagE[2]={ DIRPROP_FLAG(LRE), DIRPROP_FLAG(RLE) };
135
static const Flags flagO[2]={ DIRPROP_FLAG(LRO), DIRPROP_FLAG(RLO) };
137
#define DIRPROP_FLAG_LR(level) flagLR[(level)&1]
138
#define DIRPROP_FLAG_E(level) flagE[(level)&1]
139
#define DIRPROP_FLAG_O(level) flagO[(level)&1]
141
/* UBiDi object management -------------------------------------------------- */
143
U_CAPI UBiDi * U_EXPORT2
146
UErrorCode errorCode=U_ZERO_ERROR;
147
return ubidi_openSized(0, 0, &errorCode);
150
U_CAPI UBiDi * U_EXPORT2
151
ubidi_openSized(UTextOffset maxLength, UTextOffset maxRunCount, UErrorCode *pErrorCode) {
154
/* check the argument values */
155
if(pErrorCode==NULL || U_FAILURE(*pErrorCode)) {
157
} else if(maxLength<0 || maxRunCount<0) {
158
*pErrorCode=U_ILLEGAL_ARGUMENT_ERROR;
159
return NULL; /* invalid arguments */
162
/* allocate memory for the object */
163
pBiDi=(UBiDi *)uprv_malloc(sizeof(UBiDi));
165
*pErrorCode=U_MEMORY_ALLOCATION_ERROR;
169
/* reset the object, all pointers NULL, all flags FALSE, all sizes 0 */
170
uprv_memset(pBiDi, 0, sizeof(UBiDi));
172
/* allocate memory for arrays as requested */
174
if( !getInitialDirPropsMemory(pBiDi, maxLength) ||
175
!getInitialLevelsMemory(pBiDi, maxLength)
177
*pErrorCode=U_MEMORY_ALLOCATION_ERROR;
180
pBiDi->mayAllocateText=TRUE;
185
/* use simpleRuns[] */
186
pBiDi->runsSize=sizeof(Run);
187
} else if(!getInitialRunsMemory(pBiDi, maxRunCount)) {
188
*pErrorCode=U_MEMORY_ALLOCATION_ERROR;
191
pBiDi->mayAllocateRuns=TRUE;
194
if(U_SUCCESS(*pErrorCode)) {
203
* We are allowed to allocate memory if memory==NULL or
204
* mayAllocate==TRUE for each array that we need.
205
* We also try to grow and shrink memory as needed if we
208
* Assume sizeNeeded>0.
209
* If *pMemory!=NULL, then assume *pSize>0.
211
* ### this realloc() may unnecessarily copy the old data,
212
* which we know we don't need any more;
213
* is this the best way to do this??
216
ubidi_getMemory(void **pMemory, UTextOffset *pSize, UBool mayAllocate, UTextOffset sizeNeeded) {
217
/* check for existing memory */
219
/* we need to allocate memory */
220
if(mayAllocate && (*pMemory=uprv_malloc(sizeNeeded))!=NULL) {
227
/* there is some memory, is it enough or too much? */
228
if(sizeNeeded>*pSize && !mayAllocate) {
229
/* not enough memory, and we must not allocate */
231
} else if(sizeNeeded!=*pSize && mayAllocate) {
232
/* we may try to grow or shrink */
235
if((memory=uprv_realloc(*pMemory, sizeNeeded))!=NULL) {
240
/* we failed to grow */
244
/* we have at least enough memory and must not allocate */
250
U_CAPI void U_EXPORT2
251
ubidi_close(UBiDi *pBiDi) {
253
if(pBiDi->dirPropsMemory!=NULL) {
254
uprv_free(pBiDi->dirPropsMemory);
256
if(pBiDi->levelsMemory!=NULL) {
257
uprv_free(pBiDi->levelsMemory);
259
if(pBiDi->runsMemory!=NULL) {
260
uprv_free(pBiDi->runsMemory);
266
/* set to approximate "inverse BiDi" ---------------------------------------- */
268
U_CAPI void U_EXPORT2
269
ubidi_setInverse(UBiDi *pBiDi, UBool isInverse) {
271
pBiDi->isInverse=isInverse;
275
U_CAPI UBool U_EXPORT2
276
ubidi_isInverse(UBiDi *pBiDi) {
278
return pBiDi->isInverse;
284
/* ubidi_setPara ------------------------------------------------------------ */
286
U_CAPI void U_EXPORT2
287
ubidi_setPara(UBiDi *pBiDi, const UChar *text, UTextOffset length,
288
UBiDiLevel paraLevel, UBiDiLevel *embeddingLevels,
289
UErrorCode *pErrorCode) {
290
UBiDiDirection direction;
292
/* check the argument values */
293
if(pErrorCode==NULL || U_FAILURE(*pErrorCode)) {
295
} else if(pBiDi==NULL || text==NULL ||
296
((UBIDI_MAX_EXPLICIT_LEVEL<paraLevel) && !IS_DEFAULT_LEVEL(paraLevel)) ||
299
*pErrorCode=U_ILLEGAL_ARGUMENT_ERROR;
304
length=u_strlen(text);
307
/* initialize the UBiDi structure */
309
pBiDi->length=length;
310
pBiDi->paraLevel=paraLevel;
311
pBiDi->direction=UBIDI_LTR;
312
pBiDi->trailingWSStart=length; /* the levels[] will reflect the WS run */
314
pBiDi->dirProps=NULL;
320
* For an empty paragraph, create a UBiDi object with the paraLevel and
321
* the flags and the direction set but without allocating zero-length arrays.
322
* There is nothing more to do.
324
if(IS_DEFAULT_LEVEL(paraLevel)) {
328
pBiDi->flags=DIRPROP_FLAG(R);
329
pBiDi->direction=UBIDI_RTL;
331
pBiDi->flags=DIRPROP_FLAG(L);
332
pBiDi->direction=UBIDI_LTR;
342
* Get the directional properties,
343
* the flags bit-set, and
344
* determine the partagraph level if necessary.
346
if(getDirPropsMemory(pBiDi, length)) {
347
pBiDi->dirProps=pBiDi->dirPropsMemory;
348
getDirProps(pBiDi, text);
350
*pErrorCode=U_MEMORY_ALLOCATION_ERROR;
354
/* are explicit levels specified? */
355
if(embeddingLevels==NULL) {
356
/* no: determine explicit levels according to the (Xn) rules */\
357
if(getLevelsMemory(pBiDi, length)) {
358
pBiDi->levels=pBiDi->levelsMemory;
359
direction=resolveExplicitLevels(pBiDi);
361
*pErrorCode=U_MEMORY_ALLOCATION_ERROR;
365
/* set BN for all explicit codes, check that all levels are paraLevel..UBIDI_MAX_EXPLICIT_LEVEL */
366
pBiDi->levels=embeddingLevels;
367
direction=checkExplicitLevels(pBiDi, pErrorCode);
368
if(U_FAILURE(*pErrorCode)) {
374
* The steps after (X9) in the UBiDi algorithm are performed only if
375
* the paragraph text has mixed directionality!
377
pBiDi->direction=direction;
380
/* make sure paraLevel is even */
381
pBiDi->paraLevel=(UBiDiLevel)((pBiDi->paraLevel+1)&~1);
383
/* all levels are implicitly at paraLevel (important for ubidi_getLevels()) */
384
pBiDi->trailingWSStart=0;
387
/* make sure paraLevel is odd */
390
/* all levels are implicitly at paraLevel (important for ubidi_getLevels()) */
391
pBiDi->trailingWSStart=0;
395
* If there are no external levels specified and there
396
* are no significant explicit level codes in the text,
397
* then we can treat the entire paragraph as one run.
398
* Otherwise, we need to perform the following rules on runs of
399
* the text with the same embedding levels. (X10)
400
* "Significant" explicit level codes are ones that actually
401
* affect non-BN characters.
402
* Examples for "insignificant" ones are empty embeddings
403
* LRE-PDF, LRE-RLE-PDF-PDF, etc.
405
if(embeddingLevels==NULL && !(pBiDi->flags&DIRPROP_FLAG_MULTI_RUNS)) {
406
resolveImplicitLevels(pBiDi, 0, length,
407
GET_LR_FROM_LEVEL(pBiDi->paraLevel),
408
GET_LR_FROM_LEVEL(pBiDi->paraLevel));
410
/* sor, eor: start and end types of same-level-run */
411
UBiDiLevel *levels=pBiDi->levels;
412
UTextOffset start, limit=0;
413
UBiDiLevel level, nextLevel;
416
/* determine the first sor and set eor to it because of the loop body (sor=eor there) */
417
level=pBiDi->paraLevel;
419
if(level<nextLevel) {
420
eor=GET_LR_FROM_LEVEL(nextLevel);
422
eor=GET_LR_FROM_LEVEL(level);
426
/* determine start and limit of the run (end points just behind the run) */
428
/* the values for this run's start are the same as for the previous run's end */
433
/* search for the limit of this run */
434
while(++limit<length && levels[limit]==level) {}
436
/* get the correct level of the next run */
438
nextLevel=levels[limit];
440
nextLevel=pBiDi->paraLevel;
443
/* determine eor from max(level, nextLevel); sor is last run's eor */
444
if((level&~UBIDI_LEVEL_OVERRIDE)<(nextLevel&~UBIDI_LEVEL_OVERRIDE)) {
445
eor=GET_LR_FROM_LEVEL(nextLevel);
447
eor=GET_LR_FROM_LEVEL(level);
450
/* if the run consists of overridden directional types, then there
451
are no implicit types to be resolved */
452
if(!(level&UBIDI_LEVEL_OVERRIDE)) {
453
resolveImplicitLevels(pBiDi, start, limit, sor, eor);
455
/* remove the UBIDI_LEVEL_OVERRIDE flags */
457
levels[start++]&=~UBIDI_LEVEL_OVERRIDE;
458
} while(start<limit);
460
} while(limit<length);
463
/* reset the embedding levels for some non-graphic characters (L1), (X9) */
464
adjustWSLevels(pBiDi);
466
/* for "inverse BiDi", ubidi_getRuns() modifies the levels of numeric runs following RTL runs */
467
if(pBiDi->isInverse) {
468
if(!ubidi_getRuns(pBiDi)) {
469
*pErrorCode=U_MEMORY_ALLOCATION_ERROR;
477
/* perform (P2)..(P3) ------------------------------------------------------- */
480
* Get the directional properties for the text,
481
* calculate the flags bit-set, and
482
* determine the partagraph level if necessary.
485
getDirProps(UBiDi *pBiDi, const UChar *text) {
486
DirProp *dirProps=pBiDi->dirPropsMemory; /* pBiDi->dirProps is const */
488
UTextOffset i=0, i0, i1, length=pBiDi->length;
489
Flags flags=0; /* collect all directionalities in the text */
493
if(IS_DEFAULT_LEVEL(pBiDi->paraLevel)) {
494
/* determine the paragraph level (P2..P3) */
496
i0=i; /* index of first code unit */
497
UTF_NEXT_CHAR(text, i, length, uchar);
498
i1=i-1; /* index of last code unit, gets the directional property */
499
flags|=DIRPROP_FLAG(dirProps[i1]=dirProp=u_charDirection(uchar));
500
if(i1>i0) { /* set previous code units' properties to BN */
501
flags|=DIRPROP_FLAG(BN);
510
} else if(dirProp==R || dirProp==AL) {
513
} else if(i>=length) {
515
* see comment in ubidi.h:
516
* the DEFAULT_XXX values are designed so that
517
* their bit 0 alone yields the intended default
525
/* get the rest of the directional properties and the flags bits */
527
i0=i; /* index of first code unit */
528
UTF_NEXT_CHAR(text, i, length, uchar);
529
i1=i-1; /* index of last code unit, gets the directional property */
530
flags|=DIRPROP_FLAG(dirProps[i1]=dirProp=u_charDirection(uchar));
531
if(i1>i0) { /* set previous code units' properties to BN */
532
flags|=DIRPROP_FLAG(BN);
538
if(flags&MASK_EMBEDDING) {
539
flags|=DIRPROP_FLAG_LR(pBiDi->paraLevel);
545
/* perform (X1)..(X9) ------------------------------------------------------- */
548
* Resolve the explicit levels as specified by explicit embedding codes.
549
* Recalculate the flags to have them reflect the real properties
550
* after taking the explicit embeddings into account.
552
* The BiDi algorithm is designed to result in the same behavior whether embedding
553
* levels are externally specified (from "styled text", supposedly the preferred
554
* method) or set by explicit embedding codes (LRx, RLx, PDF) in the plain text.
555
* That is why (X9) instructs to remove all explicit codes (and BN).
556
* However, in a real implementation, this removal of these codes and their index
557
* positions in the plain text is undesirable since it would result in
558
* reallocated, reindexed text.
559
* Instead, this implementation leaves the codes in there and just ignores them
560
* in the subsequent processing.
561
* In order to get the same reordering behavior, positions with a BN or an
562
* explicit embedding code just get the same level assigned as the last "real"
565
* Some implementations, not this one, then overwrite some of these
566
* directionality properties at "real" same-level-run boundaries by
567
* L or R codes so that the resolution of weak types can be performed on the
568
* entire paragraph at once instead of having to parse it once more and
569
* perform that resolution on same-level-runs.
570
* This limits the scope of the implicit rules in effectively
571
* the same way as the run limits.
573
* Instead, this implementation does not modify these codes.
574
* On one hand, the paragraph has to be scanned for same-level-runs, but
575
* on the other hand, this saves another loop to reset these codes,
576
* or saves making and modifying a copy of dirProps[].
579
* Note that (Pn) and (Xn) changed significantly from version 4 of the BiDi algorithm.
582
* Handling the stack of explicit levels (Xn):
584
* With the BiDi stack of explicit levels,
585
* as pushed with each LRE, RLE, LRO, and RLO and popped with each PDF,
586
* the explicit level must never exceed UBIDI_MAX_EXPLICIT_LEVEL==61.
588
* In order to have a correct push-pop semantics even in the case of overflows,
589
* there are two overflow counters:
590
* - countOver60 is incremented with each LRx at level 60
591
* - from level 60, one RLx increases the level to 61
592
* - countOver61 is incremented with each LRx and RLx at level 61
594
* Popping levels with PDF must work in the opposite order so that level 61
595
* is correct at the correct point. Underflows (too many PDFs) must be checked.
597
* This implementation assumes that UBIDI_MAX_EXPLICIT_LEVEL is odd.
600
static UBiDiDirection
601
resolveExplicitLevels(UBiDi *pBiDi) {
602
const DirProp *dirProps=pBiDi->dirProps;
603
UBiDiLevel *levels=pBiDi->levels;
605
UTextOffset i=0, length=pBiDi->length;
606
Flags flags=pBiDi->flags; /* collect all directionalities in the text */
608
UBiDiLevel level=pBiDi->paraLevel;
610
UBiDiDirection direction;
612
/* determine if the text is mixed-directional or single-directional */
613
direction=directionFromFlags(flags);
615
/* we may not need to resolve any explicit levels */
616
if(direction!=UBIDI_MIXED) {
617
/* not mixed directionality: levels don't matter - trailingWSStart will be 0 */
618
} else if(!(flags&MASK_EXPLICIT) || pBiDi->isInverse) {
619
/* mixed, but all characters are at the same embedding level */
620
/* or we are in "inverse BiDi" */
621
/* set all levels to the paragraph level */
622
for(i=0; i<length; ++i) {
626
/* continue to perform (Xn) */
628
/* (X1) level is set for all codes, embeddingLevel keeps track of the push/pop operations */
629
/* both variables may carry the UBIDI_LEVEL_OVERRIDE flag to indicate the override status */
630
UBiDiLevel embeddingLevel=level, newLevel, stackTop=0;
632
UBiDiLevel stack[UBIDI_MAX_EXPLICIT_LEVEL]; /* we never push anything >=UBIDI_MAX_EXPLICIT_LEVEL */
633
uint32_t countOver60=0, countOver61=0; /* count overflows of explicit levels */
635
/* recalculate the flags */
638
/* since we assume that this is a single paragraph, we ignore (X8) */
639
for(i=0; i<length; ++i) {
645
newLevel=(UBiDiLevel)((embeddingLevel+2)&~(UBIDI_LEVEL_OVERRIDE|1)); /* least greater even level */
646
if(newLevel<=UBIDI_MAX_EXPLICIT_LEVEL) {
647
stack[stackTop]=embeddingLevel;
649
embeddingLevel=newLevel;
651
embeddingLevel|=UBIDI_LEVEL_OVERRIDE;
653
embeddingLevel&=~UBIDI_LEVEL_OVERRIDE;
655
} else if((embeddingLevel&~UBIDI_LEVEL_OVERRIDE)==UBIDI_MAX_EXPLICIT_LEVEL) {
657
} else /* (embeddingLevel&~UBIDI_LEVEL_OVERRIDE)==UBIDI_MAX_EXPLICIT_LEVEL-1 */ {
660
flags|=DIRPROP_FLAG(BN);
665
newLevel=(UBiDiLevel)(((embeddingLevel&~UBIDI_LEVEL_OVERRIDE)+1)|1); /* least greater odd level */
666
if(newLevel<=UBIDI_MAX_EXPLICIT_LEVEL) {
667
stack[stackTop]=embeddingLevel;
669
embeddingLevel=newLevel;
671
embeddingLevel|=UBIDI_LEVEL_OVERRIDE;
673
embeddingLevel&=~UBIDI_LEVEL_OVERRIDE;
678
flags|=DIRPROP_FLAG(BN);
682
/* handle all the overflow cases first */
685
} else if(countOver60>0 && (embeddingLevel&~UBIDI_LEVEL_OVERRIDE)!=UBIDI_MAX_EXPLICIT_LEVEL) {
686
/* handle LRx overflows from level 60 */
688
} else if(stackTop>0) {
689
/* this is the pop operation; it also pops level 61 while countOver60>0 */
691
embeddingLevel=stack[stackTop];
692
/* } else { (underflow) */
694
flags|=DIRPROP_FLAG(BN);
698
* We do not really expect to see a paragraph separator (B),
699
* but we should do something reasonable with it,
700
* especially at the end of the text.
703
countOver60=countOver61=0;
704
embeddingLevel=level=pBiDi->paraLevel;
705
flags|=DIRPROP_FLAG(B);
708
/* BN, LRE, RLE, and PDF are supposed to be removed (X9) */
709
/* they will get their levels set correctly in adjustWSLevels() */
710
flags|=DIRPROP_FLAG(BN);
713
/* all other types get the "real" level */
714
if(level!=embeddingLevel) {
715
level=embeddingLevel;
716
if(level&UBIDI_LEVEL_OVERRIDE) {
717
flags|=DIRPROP_FLAG_O(level)|DIRPROP_FLAG_MULTI_RUNS;
719
flags|=DIRPROP_FLAG_E(level)|DIRPROP_FLAG_MULTI_RUNS;
722
if(!(level&UBIDI_LEVEL_OVERRIDE)) {
723
flags|=DIRPROP_FLAG(dirProp);
729
* We need to set reasonable levels even on BN codes and
730
* explicit codes because we will later look at same-level runs (X10).
734
if(flags&MASK_EMBEDDING) {
735
flags|=DIRPROP_FLAG_LR(pBiDi->paraLevel);
738
/* subsequently, ignore the explicit codes and BN (X9) */
740
/* again, determine if the text is mixed-directional or single-directional */
742
direction=directionFromFlags(flags);
748
* Use a pre-specified embedding levels array:
750
* Adjust the directional properties for overrides (->LEVEL_OVERRIDE),
751
* ignore all explicit codes (X9),
752
* and check all the preset levels.
754
* Recalculate the flags to have them reflect the real properties
755
* after taking the explicit embeddings into account.
757
static UBiDiDirection
758
checkExplicitLevels(UBiDi *pBiDi, UErrorCode *pErrorCode) {
759
const DirProp *dirProps=pBiDi->dirProps;
760
UBiDiLevel *levels=pBiDi->levels;
762
UTextOffset i, length=pBiDi->length;
763
Flags flags=0; /* collect all directionalities in the text */
764
UBiDiLevel level, paraLevel=pBiDi->paraLevel;
766
for(i=0; i<length; ++i) {
768
if(level&UBIDI_LEVEL_OVERRIDE) {
769
/* keep the override flag in levels[i] but adjust the flags */
770
level&=~UBIDI_LEVEL_OVERRIDE; /* make the range check below simpler */
771
flags|=DIRPROP_FLAG_O(level);
774
flags|=DIRPROP_FLAG_E(level)|DIRPROP_FLAG(dirProps[i]);
776
if(level<paraLevel || UBIDI_MAX_EXPLICIT_LEVEL<level) {
777
/* level out of bounds */
778
*pErrorCode=U_ILLEGAL_ARGUMENT_ERROR;
782
if(flags&MASK_EMBEDDING) {
783
flags|=DIRPROP_FLAG_LR(pBiDi->paraLevel);
786
/* determine if the text is mixed-directional or single-directional */
788
return directionFromFlags(flags);
791
/* determine if the text is mixed-directional or single-directional */
792
static UBiDiDirection
793
directionFromFlags(Flags flags) {
794
/* if the text contains AN and neutrals, then some neutrals may become RTL */
795
if(!(flags&MASK_RTL || ((flags&DIRPROP_FLAG(AN)) && (flags&MASK_POSSIBLE_N)))) {
797
} else if(!(flags&MASK_LTR)) {
804
/* perform rules (Wn), (Nn), and (In) on a run of the text ------------------ */
807
* This implementation of the (Wn) rules applies all rules in one pass.
808
* In order to do so, it needs a look-ahead of typically 1 character
809
* (except for W5: sequences of ET) and keeps track of changes
810
* in a rule Wp that affect a later Wq (p<q).
812
* historyOfEN is a variable-saver: it contains 4 boolean states;
813
* a bit in it set to 1 means:
814
* bit 0: the current code is an EN after W2
815
* bit 1: the current code is an EN after W4
816
* bit 2: the previous code was an EN after W2
817
* bit 3: the previous code was an EN after W4
818
* In other words, b0..1 have transitions of EN in the current iteration,
819
* while b2..3 have the transitions of EN in the previous iteration.
820
* A simple historyOfEN<<=2 suffices for the propagation.
822
* The (Nn) and (In) rules are also performed in that same single loop,
823
* but effectively one iteration behind for white space.
825
* Since all implicit rules are performed in one step, it is not necessary
826
* to actually store the intermediate directional properties in dirProps[].
830
#define EN_AFTER_W2 1
831
#define EN_AFTER_W4 2
833
#define PREV_EN_AFTER_W2 4
834
#define PREV_EN_AFTER_W4 8
837
resolveImplicitLevels(UBiDi *pBiDi,
838
UTextOffset start, UTextOffset limit,
839
DirProp sor, DirProp eor) {
840
const DirProp *dirProps=pBiDi->dirProps;
841
UBiDiLevel *levels=pBiDi->levels;
843
UTextOffset i, next, neutralStart=-1;
844
DirProp prevDirProp, dirProp, nextDirProp, lastStrong, beforeNeutral=L;
845
UBiDiLevel numberLevel;
848
/* initialize: current at sor, next at start (it is start<limit) */
850
dirProp=lastStrong=sor;
851
nextDirProp=dirProps[next];
854
if(pBiDi->isInverse) {
856
* For "inverse BiDi", we set the levels of numbers just like for
857
* regular L characters, plus a flag that ubidi_getRuns() will use
858
* to set a similar flag on the corresponding output run.
860
numberLevel=levels[start];
865
/* normal BiDi: least greater even level */
866
numberLevel=(UBiDiLevel)((levels[start]+2)&~1);
870
* In all steps of this implementation, BN and explicit embedding codes
871
* must be treated as if they didn't exist (X9).
872
* They will get levels set before a non-neutral character, and remain
873
* undefined before a neutral one, but adjustWSLevels() will take care
876
while(DIRPROP_FLAG(nextDirProp)&MASK_BN_EXPLICIT) {
878
nextDirProp=dirProps[next];
886
* Note: at the end of this file, there is a prototype
887
* of a version of this function that uses a statetable
888
* at the core of this state machine.
889
* If you make changes to this state machine,
890
* please update that prototype as well.
893
/* loop for entire run */
901
nextDirProp=dirProps[next];
906
} while(DIRPROP_FLAG(nextDirProp)&MASK_BN_EXPLICIT);
907
historyOfEN<<=EN_SHIFT;
923
/* we have to set historyOfEN correctly */
932
/* this EN stays after (W2) and (W4) - at least before (W7) */
937
if( historyOfEN&PREV_EN_AFTER_W2 && /* previous was EN before (W4) */
938
nextDirProp==EN && lastStrong!=AL /* next is EN and (W2) won't make it AN */
947
historyOfEN|=EN_AFTER_W4;
954
if( historyOfEN&PREV_EN_AFTER_W2 && /* previous was EN before (W4) */
955
nextDirProp==EN && lastStrong!=AL /* next is EN and (W2) won't make it AN */
964
historyOfEN|=EN_AFTER_W4;
965
} else if(prevDirProp==AN && /* previous was AN */
966
(nextDirProp==AN || /* next is AN */
967
(nextDirProp==EN && lastStrong==AL)) /* or (W2) will make it one */
977
/* get sequence of ET; advance only next, not current, previous or historyOfEN */
979
while(DIRPROP_FLAG(nextDirProp)&MASK_ET_NSM_BN /* (W1), (X9) */) {
981
nextDirProp=dirProps[next];
989
/* now process the sequence of ET like a single ET */
990
if((historyOfEN&PREV_EN_AFTER_W4) || /* previous was EN before (W5) */
991
(nextDirProp==EN && lastStrong!=AL) /* next is EN and (W2) won't make it AN */
1005
/* apply the result of (W1), (W5)..(W7) to the entire sequence of ET */
1009
dirProp=prevDirProp;
1010
/* set historyOfEN back to prevDirProp's historyOfEN */
1011
historyOfEN>>=EN_SHIFT;
1013
* Technically, this should be done before the switch() in the form
1014
* if(nextDirProp==NSM) {
1015
* dirProps[next]=nextDirProp=dirProp;
1018
* - effectively one iteration ahead.
1019
* However, whether the next dirProp is NSM or is equal to the current dirProp
1020
* does not change the outcome of any condition in (W2)..(W7).
1027
/* here, it is always [prev,this,next]dirProp!=BN; it may be next>i+1 */
1029
/* perform (Nn) - here, only L, R, EN, AN, and neutrals are left */
1030
/* for "inverse BiDi", treat neutrals like L */
1031
/* this is one iteration late for the neutrals */
1032
if(DIRPROP_FLAG(dirProp)&MASK_N) {
1033
if(neutralStart<0) {
1034
/* start of a sequence of neutrals */
1036
beforeNeutral=prevDirProp;
1038
} else /* not a neutral, can be only one of { L, R, EN, AN } */ {
1040
* Note that all levels[] values are still the same at this
1041
* point because this function is called for an entire
1043
* Therefore, we need to read only one actual level.
1045
UBiDiLevel level=levels[i];
1047
if(neutralStart>=0) {
1049
/* end of a sequence of neutrals (dirProp is "afterNeutral") */
1050
if(!(pBiDi->isInverse)) {
1051
if(beforeNeutral==L) {
1053
final=0; /* make all neutrals L (N1) */
1055
final=level; /* make all neutrals "e" (N2) */
1057
} else /* beforeNeutral is one of { R, EN, AN } */ {
1059
final=level; /* make all neutrals "e" (N2) */
1061
final=1; /* make all neutrals R (N1) */
1065
/* "inverse BiDi": collapse [before]dirProps L, EN, AN into L */
1066
if(beforeNeutral!=R) {
1068
final=0; /* make all neutrals L (N1) */
1070
final=level; /* make all neutrals "e" (N2) */
1072
} else /* beforeNeutral is one of { R, EN, AN } */ {
1074
final=level; /* make all neutrals "e" (N2) */
1076
final=1; /* make all neutrals R (N1) */
1080
/* perform (In) on the sequence of neutrals */
1081
if((level^final)&1) {
1082
/* do something only if we need to _change_ the level */
1084
++levels[neutralStart];
1085
} while(++neutralStart<i);
1090
/* perform (In) on the non-neutral character */
1092
* in the cases of (W5), processing a sequence of ET,
1093
* and of (X9), skipping BN,
1094
* there may be multiple characters from i to <next
1095
* that all get (virtually) the same dirProp and (really) the same level
1101
i=next; /* we keep the levels */
1103
} else if(dirProp==R) {
1107
i=next; /* we keep the levels */
1109
} else /* EN or AN */ {
1110
/* this level depends on whether we do "inverse BiDi" */
1114
/* apply the new level to the sequence, if necessary */
1121
/* perform (Nn) - here,
1122
the character after the the neutrals is eor, which is either L or R */
1123
/* this is one iteration late for the neutrals */
1124
if(neutralStart>=0) {
1126
* Note that all levels[] values are still the same at this
1127
* point because this function is called for an entire
1129
* Therefore, we need to read only one actual level.
1131
UBiDiLevel level=levels[neutralStart], final;
1133
/* end of a sequence of neutrals (eor is "afterNeutral") */
1134
if(!(pBiDi->isInverse)) {
1135
if(beforeNeutral==L) {
1137
final=0; /* make all neutrals L (N1) */
1139
final=level; /* make all neutrals "e" (N2) */
1141
} else /* beforeNeutral is one of { R, EN, AN } */ {
1143
final=level; /* make all neutrals "e" (N2) */
1145
final=1; /* make all neutrals R (N1) */
1149
/* "inverse BiDi": collapse [before]dirProps L, EN, AN into L */
1150
if(beforeNeutral!=R) {
1152
final=0; /* make all neutrals L (N1) */
1154
final=level; /* make all neutrals "e" (N2) */
1156
} else /* beforeNeutral is one of { R, EN, AN } */ {
1158
final=level; /* make all neutrals "e" (N2) */
1160
final=1; /* make all neutrals R (N1) */
1164
/* perform (In) on the sequence of neutrals */
1165
if((level^final)&1) {
1166
/* do something only if we need to _change_ the level */
1168
++levels[neutralStart];
1169
} while(++neutralStart<limit);
1174
/* perform (L1) and (X9) ---------------------------------------------------- */
1177
* Reset the embedding levels for some non-graphic characters (L1).
1178
* This function also sets appropriate levels for BN, and
1179
* explicit embedding types that are supposed to have been removed
1180
* from the paragraph in (X9).
1183
adjustWSLevels(UBiDi *pBiDi) {
1184
const DirProp *dirProps=pBiDi->dirProps;
1185
UBiDiLevel *levels=pBiDi->levels;
1188
if(pBiDi->flags&MASK_WS) {
1189
UBiDiLevel paraLevel=pBiDi->paraLevel;
1192
i=pBiDi->trailingWSStart;
1194
/* reset a sequence of WS/BN before eop and B/S to the paragraph paraLevel */
1195
while(i>0 && DIRPROP_FLAG(dirProps[--i])&MASK_WS) {
1196
levels[i]=paraLevel;
1199
/* reset BN to the next character's paraLevel until B/S, which restarts above loop */
1200
/* here, i+1 is guaranteed to be <length */
1202
flag=DIRPROP_FLAG(dirProps[--i]);
1203
if(flag&MASK_BN_EXPLICIT) {
1204
levels[i]=levels[i+1];
1205
} else if(flag&MASK_B_S) {
1206
levels[i]=paraLevel;
1214
/* -------------------------------------------------------------------------- */
1216
U_CAPI UBiDiDirection U_EXPORT2
1217
ubidi_getDirection(const UBiDi *pBiDi) {
1219
return pBiDi->direction;
1225
U_CAPI const UChar * U_EXPORT2
1226
ubidi_getText(const UBiDi *pBiDi) {
1234
U_CAPI UTextOffset U_EXPORT2
1235
ubidi_getLength(const UBiDi *pBiDi) {
1237
return pBiDi->length;
1243
U_CAPI UBiDiLevel U_EXPORT2
1244
ubidi_getParaLevel(const UBiDi *pBiDi) {
1246
return pBiDi->paraLevel;
1252
/* statetable prototype ----------------------------------------------------- */
1255
* This is here for possible future
1256
* performance work and is not compiled right now.
1261
* This is a piece of code that could be part of ubidi.c/resolveImplicitLevels().
1262
* It replaces in the (Wn) state machine the switch()-if()-cascade with
1263
* just a few if()s and a state table.
1266
/* use the state table only for the following dirProp's */
1267
#define MASK_W_TABLE (FLAG(L)|FLAG(R)|FLAG(AL)|FLAG(EN)|FLAG(ES)|FLAG(CS)|FLAG(ET)|FLAG(AN))
1272
* 0..1 historyOfEN - 2b
1273
* 2 prevDirProp==AN - 1b
1274
* 3..4 lastStrong, one of { L, R, AL, none } - 2b
1275
* 5..7 dirProp, one of { L, R, AL, EN, ES, CS, ET, AN } - 3b
1276
* 8..9 nextDirProp, one of { EN, AN, other }
1278
* total: 10b=1024 states
1280
enum { _L, _R, _AL, _EN, _ES, _CS, _ET, _AN, _OTHER }; /* lastStrong, dirProp */
1281
enum { __EN, __AN, __OTHER }; /* nextDirProp */
1283
#define LAST_STRONG_SHIFT 3
1284
#define DIR_PROP_SHIFT 5
1285
#define NEXT_DIR_PROP_SHIFT 8
1287
/* masks after shifting */
1288
#define LAST_STRONG_MASK 3
1289
#define DIR_PROP_MASK 7
1290
#define STATE_MASK 0x1f
1292
/* convert dirProp into _dirProp (above enum) */
1293
static DirProp inputDirProp[dirPropCount]={ _X<<DIR_PROP_SHIFT, ... };
1295
/* convert dirProp into __dirProp (above enum) */
1296
static DirProp inputNextDirProp[dirPropCount]={ __X<<NEXT_DIR_PROP_SHIFT, ... };
1301
* dirProp, one of { L, R, EN, AN, ON } - 3b
1303
* 0..1 historyOfEN - 2b
1304
* 2 prevDirProp==AN - 1b
1305
* 3..4 lastStrong, one of { L, R, AL, none } - 2b
1306
* 5..7 new dirProp, one of { L, R, EN, AN, ON }
1308
* total: 8 bits=1 byte per state
1310
enum { ___L, ___R, ___EN, ___AN, ___ON, ___count };
1312
/* convert ___dirProp into dirProp (above enum) */
1313
static DirProp outputDirProp[___count]={ X, ... };
1316
static uint8_t wnTable[1024]={ /* calculate with switch()-if()-cascade */ };
1319
resolveImplicitLevels(BiDi *pBiDi,
1320
Index start, Index end,
1321
DirProp sor, DirProp eor) {
1325
/* remove variable lastStrong */
1327
/* set initial state (set lastStrong, the rest is 0) */
1328
state= sor==L ? 0 : _R<<LAST_STRONG_SHIFT;
1332
prevDirProp=dirProp;
1333
dirProp=nextDirProp;
1337
nextDirProp=dirProps[next];
1342
} while(FLAG(nextDirProp)&MASK_BN_EXPLICIT);
1345
/* ### This may be more efficient with a switch(dirProp). */
1346
if(FLAG(dirProp)&MASK_W_TABLE) {
1349
inputDirProp[dirProp]|
1350
inputNextDirProp[nextDirProp]
1352
dirProp=outputDirProp[state>>DIR_PROP_SHIFT];
1354
} else if(dirProp==ET) {
1355
/* get sequence of ET; advance only next, not current, previous or historyOfEN */
1356
while(next<limit && FLAG(nextDirProp)&MASK_ET_NSM_BN /* (W1), (X9) */) {
1358
nextDirProp=dirProps[next];
1367
_ET<<DIR_PROP_SHIFT|
1368
inputNextDirProp[nextDirProp]
1370
dirProp=outputDirProp[state>>DIR_PROP_SHIFT];
1373
/* apply the result of (W1), (W5)..(W7) to the entire sequence of ET */
1374
} else if(dirProp==NSM) {
1376
dirProp=prevDirProp;
1377
/* keep prevDirProp's EN and AN states! */
1378
} else /* other */ {
1379
/* set EN and AN states to 0 */
1380
state&=LAST_STRONG_MASK<<LAST_STRONG_SHIFT;
1383
/* perform (Nn) and (In) as usual */
1385
/* perform (Nn) and (In) as usual */
added
removed
source/common/ubidi.c
