• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 // © 2016 and later: Unicode, Inc. and others.
2 // License & terms of use: http://www.unicode.org/copyright.html
3 /*
4 ******************************************************************************
5 *
6 *   Copyright (C) 1999-2015, International Business Machines
7 *   Corporation and others.  All Rights Reserved.
8 *
9 ******************************************************************************
10 *   file name:  ubidiln.c
11 *   encoding:   UTF-8
12 *   tab size:   8 (not used)
13 *   indentation:4
14 *
15 *   created on: 1999aug06
16 *   created by: Markus W. Scherer, updated by Matitiahu Allouche
17 */
18 
19 #include "cmemory.h"
20 #include "unicode/utypes.h"
21 #include "unicode/ustring.h"
22 #include "unicode/uchar.h"
23 #include "unicode/ubidi.h"
24 #include "ubidiimp.h"
25 #include "uassert.h"
26 
27 /*
28  * General remarks about the functions in this file:
29  *
30  * These functions deal with the aspects of potentially mixed-directional
31  * text in a single paragraph or in a line of a single paragraph
32  * which has already been processed according to
33  * the Unicode 6.3 BiDi algorithm as defined in
34  * http://www.unicode.org/unicode/reports/tr9/ , version 28,
35  * also described in The Unicode Standard, Version 6.3.0 .
36  *
37  * This means that there is a UBiDi object with a levels
38  * and a dirProps array.
39  * paraLevel and direction are also set.
40  * Only if the length of the text is zero, then levels==dirProps==NULL.
41  *
42  * The overall directionality of the paragraph
43  * or line is used to bypass the reordering steps if possible.
44  * Even purely RTL text does not need reordering there because
45  * the ubidi_getLogical/VisualIndex() functions can compute the
46  * index on the fly in such a case.
47  *
48  * The implementation of the access to same-level-runs and of the reordering
49  * do attempt to provide better performance and less memory usage compared to
50  * a direct implementation of especially rule (L2) with an array of
51  * one (32-bit) integer per text character.
52  *
53  * Here, the levels array is scanned as soon as necessary, and a vector of
54  * same-level-runs is created. Reordering then is done on this vector.
55  * For each run of text positions that were resolved to the same level,
56  * only 8 bytes are stored: the first text position of the run and the visual
57  * position behind the run after reordering.
58  * One sign bit is used to hold the directionality of the run.
59  * This is inefficient if there are many very short runs. If the average run
60  * length is <2, then this uses more memory.
61  *
62  * In a further attempt to save memory, the levels array is never changed
63  * after all the resolution rules (Xn, Wn, Nn, In).
64  * Many functions have to consider the field trailingWSStart:
65  * if it is less than length, then there is an implicit trailing run
66  * at the paraLevel,
67  * which is not reflected in the levels array.
68  * This allows a line UBiDi object to use the same levels array as
69  * its paragraph parent object.
70  *
71  * When a UBiDi object is created for a line of a paragraph, then the
72  * paragraph's levels and dirProps arrays are reused by way of setting
73  * a pointer into them, not by copying. This again saves memory and forbids to
74  * change the now shared levels for (L1).
75  */
76 
77 /* handle trailing WS (L1) -------------------------------------------------- */
78 
79 /*
80  * setTrailingWSStart() sets the start index for a trailing
81  * run of WS in the line. This is necessary because we do not modify
82  * the paragraph's levels array that we just point into.
83  * Using trailingWSStart is another form of performing (L1).
84  *
85  * To make subsequent operations easier, we also include the run
86  * before the WS if it is at the paraLevel - we merge the two here.
87  *
88  * This function is called only from ubidi_setLine(), so pBiDi->paraLevel is
89  * set correctly for the line even when contextual multiple paragraphs.
90  */
91 static void
setTrailingWSStart(UBiDi * pBiDi)92 setTrailingWSStart(UBiDi *pBiDi) {
93     /* pBiDi->direction!=UBIDI_MIXED */
94 
95     const DirProp *dirProps=pBiDi->dirProps;
96     UBiDiLevel *levels=pBiDi->levels;
97     int32_t start=pBiDi->length;
98     UBiDiLevel paraLevel=pBiDi->paraLevel;
99 
100     /* If the line is terminated by a block separator, all preceding WS etc...
101        are already set to paragraph level.
102        Setting trailingWSStart to pBidi->length will avoid changing the
103        level of B chars from 0 to paraLevel in ubidi_getLevels when
104        orderParagraphsLTR==TRUE.
105      */
106     if(dirProps[start-1]==B) {
107         pBiDi->trailingWSStart=start;   /* currently == pBiDi->length */
108         return;
109     }
110     /* go backwards across all WS, BN, explicit codes */
111     while(start>0 && DIRPROP_FLAG(dirProps[start-1])&MASK_WS) {
112         --start;
113     }
114 
115     /* if the WS run can be merged with the previous run then do so here */
116     while(start>0 && levels[start-1]==paraLevel) {
117         --start;
118     }
119 
120     pBiDi->trailingWSStart=start;
121 }
122 
123 /* ubidi_setLine ------------------------------------------------------------ */
124 
125 U_CAPI void U_EXPORT2
ubidi_setLine(const UBiDi * pParaBiDi,int32_t start,int32_t limit,UBiDi * pLineBiDi,UErrorCode * pErrorCode)126 ubidi_setLine(const UBiDi *pParaBiDi,
127               int32_t start, int32_t limit,
128               UBiDi *pLineBiDi,
129               UErrorCode *pErrorCode) {
130     int32_t length;
131 
132     /* check the argument values */
133     RETURN_VOID_IF_NULL_OR_FAILING_ERRCODE(pErrorCode);
134     RETURN_VOID_IF_NOT_VALID_PARA(pParaBiDi, *pErrorCode);
135     RETURN_VOID_IF_BAD_RANGE(start, 0, limit, *pErrorCode);
136     RETURN_VOID_IF_BAD_RANGE(limit, 0, pParaBiDi->length+1, *pErrorCode);
137     if(pLineBiDi==NULL) {
138         *pErrorCode=U_ILLEGAL_ARGUMENT_ERROR;
139         return;
140     }
141     if(ubidi_getParagraph(pParaBiDi, start, NULL, NULL, NULL, pErrorCode) !=
142        ubidi_getParagraph(pParaBiDi, limit-1, NULL, NULL, NULL, pErrorCode)) {
143         /* the line crosses a paragraph boundary */
144         *pErrorCode=U_ILLEGAL_ARGUMENT_ERROR;
145         return;
146     }
147 
148     /* set the values in pLineBiDi from its pParaBiDi parent */
149     pLineBiDi->pParaBiDi=NULL;          /* mark unfinished setLine */
150     pLineBiDi->text=pParaBiDi->text+start;
151     length=pLineBiDi->length=limit-start;
152     pLineBiDi->resultLength=pLineBiDi->originalLength=length;
153     pLineBiDi->paraLevel=GET_PARALEVEL(pParaBiDi, start);
154     pLineBiDi->paraCount=pParaBiDi->paraCount;
155     pLineBiDi->runs=NULL;
156     pLineBiDi->flags=0;
157     pLineBiDi->reorderingMode=pParaBiDi->reorderingMode;
158     pLineBiDi->reorderingOptions=pParaBiDi->reorderingOptions;
159     pLineBiDi->controlCount=0;
160     if(pParaBiDi->controlCount>0) {
161         int32_t j;
162         for(j=start; j<limit; j++) {
163             if(IS_BIDI_CONTROL_CHAR(pParaBiDi->text[j])) {
164                 pLineBiDi->controlCount++;
165             }
166         }
167         pLineBiDi->resultLength-=pLineBiDi->controlCount;
168     }
169 
170     pLineBiDi->dirProps=pParaBiDi->dirProps+start;
171     pLineBiDi->levels=pParaBiDi->levels+start;
172     pLineBiDi->runCount=-1;
173 
174     if(pParaBiDi->direction!=UBIDI_MIXED) {
175         /* the parent is already trivial */
176         pLineBiDi->direction=pParaBiDi->direction;
177 
178         /*
179          * The parent's levels are all either
180          * implicitly or explicitly ==paraLevel;
181          * do the same here.
182          */
183         if(pParaBiDi->trailingWSStart<=start) {
184             pLineBiDi->trailingWSStart=0;
185         } else if(pParaBiDi->trailingWSStart<limit) {
186             pLineBiDi->trailingWSStart=pParaBiDi->trailingWSStart-start;
187         } else {
188             pLineBiDi->trailingWSStart=length;
189         }
190     } else {
191         const UBiDiLevel *levels=pLineBiDi->levels;
192         int32_t i, trailingWSStart;
193         UBiDiLevel level;
194 
195         setTrailingWSStart(pLineBiDi);
196         trailingWSStart=pLineBiDi->trailingWSStart;
197 
198         /* recalculate pLineBiDi->direction */
199         if(trailingWSStart==0) {
200             /* all levels are at paraLevel */
201             pLineBiDi->direction=(UBiDiDirection)(pLineBiDi->paraLevel&1);
202         } else {
203             /* get the level of the first character */
204             level=(UBiDiLevel)(levels[0]&1);
205 
206             /* if there is anything of a different level, then the line is mixed */
207             if(trailingWSStart<length && (pLineBiDi->paraLevel&1)!=level) {
208                 /* the trailing WS is at paraLevel, which differs from levels[0] */
209                 pLineBiDi->direction=UBIDI_MIXED;
210             } else {
211                 /* see if levels[1..trailingWSStart-1] have the same direction as levels[0] and paraLevel */
212                 i=1;
213                 for(;;) {
214                     if(i==trailingWSStart) {
215                         /* the direction values match those in level */
216                         pLineBiDi->direction=(UBiDiDirection)level;
217                         break;
218                     } else if((levels[i]&1)!=level) {
219                         pLineBiDi->direction=UBIDI_MIXED;
220                         break;
221                     }
222                     ++i;
223                 }
224             }
225         }
226 
227         switch(pLineBiDi->direction) {
228         case UBIDI_LTR:
229             /* make sure paraLevel is even */
230             pLineBiDi->paraLevel=(UBiDiLevel)((pLineBiDi->paraLevel+1)&~1);
231 
232             /* all levels are implicitly at paraLevel (important for ubidi_getLevels()) */
233             pLineBiDi->trailingWSStart=0;
234             break;
235         case UBIDI_RTL:
236             /* make sure paraLevel is odd */
237             pLineBiDi->paraLevel|=1;
238 
239             /* all levels are implicitly at paraLevel (important for ubidi_getLevels()) */
240             pLineBiDi->trailingWSStart=0;
241             break;
242         default:
243             break;
244         }
245     }
246     pLineBiDi->pParaBiDi=pParaBiDi;     /* mark successful setLine */
247     return;
248 }
249 
250 U_CAPI UBiDiLevel U_EXPORT2
ubidi_getLevelAt(const UBiDi * pBiDi,int32_t charIndex)251 ubidi_getLevelAt(const UBiDi *pBiDi, int32_t charIndex) {
252     /* return paraLevel if in the trailing WS run, otherwise the real level */
253     if(!IS_VALID_PARA_OR_LINE(pBiDi) || charIndex<0 || pBiDi->length<=charIndex) {
254         return 0;
255     } else if(pBiDi->direction!=UBIDI_MIXED || charIndex>=pBiDi->trailingWSStart) {
256         return GET_PARALEVEL(pBiDi, charIndex);
257     } else {
258         return pBiDi->levels[charIndex];
259     }
260 }
261 
262 U_CAPI const UBiDiLevel * U_EXPORT2
ubidi_getLevels(UBiDi * pBiDi,UErrorCode * pErrorCode)263 ubidi_getLevels(UBiDi *pBiDi, UErrorCode *pErrorCode) {
264     int32_t start, length;
265 
266     RETURN_IF_NULL_OR_FAILING_ERRCODE(pErrorCode, NULL);
267     RETURN_IF_NOT_VALID_PARA_OR_LINE(pBiDi, *pErrorCode, NULL);
268     if((length=pBiDi->length)<=0) {
269         *pErrorCode=U_ILLEGAL_ARGUMENT_ERROR;
270         return NULL;
271     }
272     if((start=pBiDi->trailingWSStart)==length) {
273         /* the current levels array reflects the WS run */
274         return pBiDi->levels;
275     }
276 
277     /*
278      * After the previous if(), we know that the levels array
279      * has an implicit trailing WS run and therefore does not fully
280      * reflect itself all the levels.
281      * This must be a UBiDi object for a line, and
282      * we need to create a new levels array.
283      */
284     if(getLevelsMemory(pBiDi, length)) {
285         UBiDiLevel *levels=pBiDi->levelsMemory;
286 
287         if(start>0 && levels!=pBiDi->levels) {
288             uprv_memcpy(levels, pBiDi->levels, start);
289         }
290         /* pBiDi->paraLevel is ok even if contextual multiple paragraphs,
291            since pBidi is a line object                                     */
292         uprv_memset(levels+start, pBiDi->paraLevel, length-start);
293 
294         /* this new levels array is set for the line and reflects the WS run */
295         pBiDi->trailingWSStart=length;
296         return pBiDi->levels=levels;
297     } else {
298         /* out of memory */
299         *pErrorCode=U_MEMORY_ALLOCATION_ERROR;
300         return NULL;
301     }
302 }
303 
304 U_CAPI void U_EXPORT2
ubidi_getLogicalRun(const UBiDi * pBiDi,int32_t logicalPosition,int32_t * pLogicalLimit,UBiDiLevel * pLevel)305 ubidi_getLogicalRun(const UBiDi *pBiDi, int32_t logicalPosition,
306                     int32_t *pLogicalLimit, UBiDiLevel *pLevel) {
307     UErrorCode errorCode;
308     int32_t runCount, visualStart, logicalLimit, logicalFirst, i;
309     Run iRun;
310 
311     errorCode=U_ZERO_ERROR;
312     RETURN_VOID_IF_BAD_RANGE(logicalPosition, 0, pBiDi->length, errorCode);
313     /* ubidi_countRuns will check VALID_PARA_OR_LINE */
314     runCount=ubidi_countRuns((UBiDi *)pBiDi, &errorCode);
315     if(U_FAILURE(errorCode)) {
316         return;
317     }
318     /* this is done based on runs rather than on levels since levels have
319        a special interpretation when UBIDI_REORDER_RUNS_ONLY
320      */
321     visualStart=logicalLimit=0;
322     iRun=pBiDi->runs[0];
323 
324     for(i=0; i<runCount; i++) {
325         iRun = pBiDi->runs[i];
326         logicalFirst=GET_INDEX(iRun.logicalStart);
327         logicalLimit=logicalFirst+iRun.visualLimit-visualStart;
328         if((logicalPosition>=logicalFirst) &&
329            (logicalPosition<logicalLimit)) {
330             break;
331         }
332         visualStart = iRun.visualLimit;
333     }
334     if(pLogicalLimit) {
335         *pLogicalLimit=logicalLimit;
336     }
337     if(pLevel) {
338         if(pBiDi->reorderingMode==UBIDI_REORDER_RUNS_ONLY) {
339             *pLevel=(UBiDiLevel)GET_ODD_BIT(iRun.logicalStart);
340         }
341         else if(pBiDi->direction!=UBIDI_MIXED || logicalPosition>=pBiDi->trailingWSStart) {
342             *pLevel=GET_PARALEVEL(pBiDi, logicalPosition);
343         } else {
344         *pLevel=pBiDi->levels[logicalPosition];
345         }
346     }
347 }
348 
349 /* runs API functions ------------------------------------------------------- */
350 
351 U_CAPI int32_t U_EXPORT2
ubidi_countRuns(UBiDi * pBiDi,UErrorCode * pErrorCode)352 ubidi_countRuns(UBiDi *pBiDi, UErrorCode *pErrorCode) {
353     RETURN_IF_NULL_OR_FAILING_ERRCODE(pErrorCode, -1);
354     RETURN_IF_NOT_VALID_PARA_OR_LINE(pBiDi, *pErrorCode, -1);
355     ubidi_getRuns(pBiDi, pErrorCode);
356     if(U_FAILURE(*pErrorCode)) {
357         return -1;
358     }
359     return pBiDi->runCount;
360 }
361 
362 U_CAPI UBiDiDirection U_EXPORT2
ubidi_getVisualRun(UBiDi * pBiDi,int32_t runIndex,int32_t * pLogicalStart,int32_t * pLength)363 ubidi_getVisualRun(UBiDi *pBiDi, int32_t runIndex,
364                    int32_t *pLogicalStart, int32_t *pLength)
365 {
366     int32_t start;
367     UErrorCode errorCode = U_ZERO_ERROR;
368     RETURN_IF_NOT_VALID_PARA_OR_LINE(pBiDi, errorCode, UBIDI_LTR);
369     ubidi_getRuns(pBiDi, &errorCode);
370     if(U_FAILURE(errorCode)) {
371         return UBIDI_LTR;
372     }
373     RETURN_IF_BAD_RANGE(runIndex, 0, pBiDi->runCount, errorCode, UBIDI_LTR);
374 
375     start=pBiDi->runs[runIndex].logicalStart;
376     if(pLogicalStart!=NULL) {
377         *pLogicalStart=GET_INDEX(start);
378     }
379     if(pLength!=NULL) {
380         if(runIndex>0) {
381             *pLength=pBiDi->runs[runIndex].visualLimit-
382                      pBiDi->runs[runIndex-1].visualLimit;
383         } else {
384             *pLength=pBiDi->runs[0].visualLimit;
385         }
386     }
387     return (UBiDiDirection)GET_ODD_BIT(start);
388 }
389 
390 /* in trivial cases there is only one trivial run; called by ubidi_getRuns() */
391 static void
getSingleRun(UBiDi * pBiDi,UBiDiLevel level)392 getSingleRun(UBiDi *pBiDi, UBiDiLevel level) {
393     /* simple, single-run case */
394     pBiDi->runs=pBiDi->simpleRuns;
395     pBiDi->runCount=1;
396 
397     /* fill and reorder the single run */
398     pBiDi->runs[0].logicalStart=MAKE_INDEX_ODD_PAIR(0, level);
399     pBiDi->runs[0].visualLimit=pBiDi->length;
400     pBiDi->runs[0].insertRemove=0;
401 }
402 
403 /* reorder the runs array (L2) ---------------------------------------------- */
404 
405 /*
406  * Reorder the same-level runs in the runs array.
407  * Here, runCount>1 and maxLevel>=minLevel>=paraLevel.
408  * All the visualStart fields=logical start before reordering.
409  * The "odd" bits are not set yet.
410  *
411  * Reordering with this data structure lends itself to some handy shortcuts:
412  *
413  * Since each run is moved but not modified, and since at the initial maxLevel
414  * each sequence of same-level runs consists of only one run each, we
415  * don't need to do anything there and can predecrement maxLevel.
416  * In many simple cases, the reordering is thus done entirely in the
417  * index mapping.
418  * Also, reordering occurs only down to the lowest odd level that occurs,
419  * which is minLevel|1. However, if the lowest level itself is odd, then
420  * in the last reordering the sequence of the runs at this level or higher
421  * will be all runs, and we don't need the elaborate loop to search for them.
422  * This is covered by ++minLevel instead of minLevel|=1 followed
423  * by an extra reorder-all after the reorder-some loop.
424  * About a trailing WS run:
425  * Such a run would need special treatment because its level is not
426  * reflected in levels[] if this is not a paragraph object.
427  * Instead, all characters from trailingWSStart on are implicitly at
428  * paraLevel.
429  * However, for all maxLevel>paraLevel, this run will never be reordered
430  * and does not need to be taken into account. maxLevel==paraLevel is only reordered
431  * if minLevel==paraLevel is odd, which is done in the extra segment.
432  * This means that for the main reordering loop we don't need to consider
433  * this run and can --runCount. If it is later part of the all-runs
434  * reordering, then runCount is adjusted accordingly.
435  */
436 static void
reorderLine(UBiDi * pBiDi,UBiDiLevel minLevel,UBiDiLevel maxLevel)437 reorderLine(UBiDi *pBiDi, UBiDiLevel minLevel, UBiDiLevel maxLevel) {
438     Run *runs, tempRun;
439     UBiDiLevel *levels;
440     int32_t firstRun, endRun, limitRun, runCount;
441 
442     /* nothing to do? */
443     if(maxLevel<=(minLevel|1)) {
444         return;
445     }
446 
447     /*
448      * Reorder only down to the lowest odd level
449      * and reorder at an odd minLevel in a separate, simpler loop.
450      * See comments above for why minLevel is always incremented.
451      */
452     ++minLevel;
453 
454     runs=pBiDi->runs;
455     levels=pBiDi->levels;
456     runCount=pBiDi->runCount;
457 
458     /* do not include the WS run at paraLevel<=old minLevel except in the simple loop */
459     if(pBiDi->trailingWSStart<pBiDi->length) {
460         --runCount;
461     }
462 
463     while(--maxLevel>=minLevel) {
464         firstRun=0;
465 
466         /* loop for all sequences of runs */
467         for(;;) {
468             /* look for a sequence of runs that are all at >=maxLevel */
469             /* look for the first run of such a sequence */
470             while(firstRun<runCount && levels[runs[firstRun].logicalStart]<maxLevel) {
471                 ++firstRun;
472             }
473             if(firstRun>=runCount) {
474                 break;  /* no more such runs */
475             }
476 
477             /* look for the limit run of such a sequence (the run behind it) */
478             for(limitRun=firstRun; ++limitRun<runCount && levels[runs[limitRun].logicalStart]>=maxLevel;) {}
479 
480             /* Swap the entire sequence of runs from firstRun to limitRun-1. */
481             endRun=limitRun-1;
482             while(firstRun<endRun) {
483                 tempRun = runs[firstRun];
484                 runs[firstRun]=runs[endRun];
485                 runs[endRun]=tempRun;
486                 ++firstRun;
487                 --endRun;
488             }
489 
490             if(limitRun==runCount) {
491                 break;  /* no more such runs */
492             } else {
493                 firstRun=limitRun+1;
494             }
495         }
496     }
497 
498     /* now do maxLevel==old minLevel (==odd!), see above */
499     if(!(minLevel&1)) {
500         firstRun=0;
501 
502         /* include the trailing WS run in this complete reordering */
503         if(pBiDi->trailingWSStart==pBiDi->length) {
504             --runCount;
505         }
506 
507         /* Swap the entire sequence of all runs. (endRun==runCount) */
508         while(firstRun<runCount) {
509             tempRun=runs[firstRun];
510             runs[firstRun]=runs[runCount];
511             runs[runCount]=tempRun;
512             ++firstRun;
513             --runCount;
514         }
515     }
516 }
517 
518 /* compute the runs array --------------------------------------------------- */
519 
getRunFromLogicalIndex(UBiDi * pBiDi,int32_t logicalIndex,UErrorCode * pErrorCode)520 static int32_t getRunFromLogicalIndex(UBiDi *pBiDi, int32_t logicalIndex, UErrorCode *pErrorCode) {
521     Run *runs=pBiDi->runs;
522     int32_t runCount=pBiDi->runCount, visualStart=0, i, length, logicalStart;
523 
524     for(i=0; i<runCount; i++) {
525         length=runs[i].visualLimit-visualStart;
526         logicalStart=GET_INDEX(runs[i].logicalStart);
527         if((logicalIndex>=logicalStart) && (logicalIndex<(logicalStart+length))) {
528             return i;
529         }
530         visualStart+=length;
531     }
532     /* we should never get here */
533     U_ASSERT(FALSE);
534     *pErrorCode = U_INVALID_STATE_ERROR;
535     return 0;
536 }
537 
538 /*
539  * Compute the runs array from the levels array.
540  * After ubidi_getRuns() returns TRUE, runCount is guaranteed to be >0
541  * and the runs are reordered.
542  * Odd-level runs have visualStart on their visual right edge and
543  * they progress visually to the left.
544  * If option UBIDI_OPTION_INSERT_MARKS is set, insertRemove will contain the
545  * sum of appropriate LRM/RLM_BEFORE/AFTER flags.
546  * If option UBIDI_OPTION_REMOVE_CONTROLS is set, insertRemove will contain the
547  * negative number of BiDi control characters within this run.
548  */
549 U_CFUNC UBool
ubidi_getRuns(UBiDi * pBiDi,UErrorCode * pErrorCode)550 ubidi_getRuns(UBiDi *pBiDi, UErrorCode *pErrorCode) {
551     /*
552      * This method returns immediately if the runs are already set. This
553      * includes the case of length==0 (handled in setPara)..
554      */
555     if (pBiDi->runCount>=0) {
556         return TRUE;
557     }
558 
559     if(pBiDi->direction!=UBIDI_MIXED) {
560         /* simple, single-run case - this covers length==0 */
561         /* pBiDi->paraLevel is ok even for contextual multiple paragraphs */
562         getSingleRun(pBiDi, pBiDi->paraLevel);
563     } else /* UBIDI_MIXED, length>0 */ {
564         /* mixed directionality */
565         int32_t length=pBiDi->length, limit;
566         UBiDiLevel *levels=pBiDi->levels;
567         int32_t i, runCount;
568         UBiDiLevel level=UBIDI_DEFAULT_LTR;   /* initialize with no valid level */
569         /*
570          * If there are WS characters at the end of the line
571          * and the run preceding them has a level different from
572          * paraLevel, then they will form their own run at paraLevel (L1).
573          * Count them separately.
574          * We need some special treatment for this in order to not
575          * modify the levels array which a line UBiDi object shares
576          * with its paragraph parent and its other line siblings.
577          * In other words, for the trailing WS, it may be
578          * levels[]!=paraLevel but we have to treat it like it were so.
579          */
580         limit=pBiDi->trailingWSStart;
581         /* count the runs, there is at least one non-WS run, and limit>0 */
582         runCount=0;
583         for(i=0; i<limit; ++i) {
584             /* increment runCount at the start of each run */
585             if(levels[i]!=level) {
586                 ++runCount;
587                 level=levels[i];
588             }
589         }
590 
591         /*
592          * We don't need to see if the last run can be merged with a trailing
593          * WS run because setTrailingWSStart() would have done that.
594          */
595         if(runCount==1 && limit==length) {
596             /* There is only one non-WS run and no trailing WS-run. */
597             getSingleRun(pBiDi, levels[0]);
598         } else /* runCount>1 || limit<length */ {
599             /* allocate and set the runs */
600             Run *runs;
601             int32_t runIndex, start;
602             UBiDiLevel minLevel=UBIDI_MAX_EXPLICIT_LEVEL+1, maxLevel=0;
603 
604             /* now, count a (non-mergeable) WS run */
605             if(limit<length) {
606                 ++runCount;
607             }
608 
609             /* runCount>1 */
610             if(getRunsMemory(pBiDi, runCount)) {
611                 runs=pBiDi->runsMemory;
612             } else {
613                 return FALSE;
614             }
615 
616             /* set the runs */
617             /* FOOD FOR THOUGHT: this could be optimized, e.g.:
618              * 464->444, 484->444, 575->555, 595->555
619              * However, that would take longer. Check also how it would
620              * interact with BiDi control removal and inserting Marks.
621              */
622             runIndex=0;
623 
624             /* search for the run limits and initialize visualLimit values with the run lengths */
625             i=0;
626             do {
627                 /* prepare this run */
628                 start=i;
629                 level=levels[i];
630                 if(level<minLevel) {
631                     minLevel=level;
632                 }
633                 if(level>maxLevel) {
634                     maxLevel=level;
635                 }
636 
637                 /* look for the run limit */
638                 while(++i<limit && levels[i]==level) {}
639 
640                 /* i is another run limit */
641                 runs[runIndex].logicalStart=start;
642                 runs[runIndex].visualLimit=i-start;
643                 runs[runIndex].insertRemove=0;
644                 ++runIndex;
645             } while(i<limit);
646 
647             if(limit<length) {
648                 /* there is a separate WS run */
649                 runs[runIndex].logicalStart=limit;
650                 runs[runIndex].visualLimit=length-limit;
651                 /* For the trailing WS run, pBiDi->paraLevel is ok even
652                    if contextual multiple paragraphs.                   */
653                 if(pBiDi->paraLevel<minLevel) {
654                     minLevel=pBiDi->paraLevel;
655                 }
656             }
657 
658             /* set the object fields */
659             pBiDi->runs=runs;
660             pBiDi->runCount=runCount;
661 
662             reorderLine(pBiDi, minLevel, maxLevel);
663 
664             /* now add the direction flags and adjust the visualLimit's to be just that */
665             /* this loop will also handle the trailing WS run */
666             limit=0;
667             for(i=0; i<runCount; ++i) {
668                 ADD_ODD_BIT_FROM_LEVEL(runs[i].logicalStart, levels[runs[i].logicalStart]);
669                 limit+=runs[i].visualLimit;
670                 runs[i].visualLimit=limit;
671             }
672 
673             /* Set the "odd" bit for the trailing WS run. */
674             /* For a RTL paragraph, it will be the *first* run in visual order. */
675             /* For the trailing WS run, pBiDi->paraLevel is ok even if
676                contextual multiple paragraphs.                          */
677             if(runIndex<runCount) {
678                 int32_t trailingRun = ((pBiDi->paraLevel & 1) != 0)? 0 : runIndex;
679 
680                 ADD_ODD_BIT_FROM_LEVEL(runs[trailingRun].logicalStart, pBiDi->paraLevel);
681             }
682         }
683     }
684 
685     /* handle insert LRM/RLM BEFORE/AFTER run */
686     if(pBiDi->insertPoints.size>0) {
687         Point *point, *start=pBiDi->insertPoints.points,
688                       *limit=start+pBiDi->insertPoints.size;
689         int32_t runIndex;
690         for(point=start; point<limit; point++) {
691             runIndex=getRunFromLogicalIndex(pBiDi, point->pos, pErrorCode);
692             pBiDi->runs[runIndex].insertRemove|=point->flag;
693         }
694     }
695 
696     /* handle remove BiDi control characters */
697     if(pBiDi->controlCount>0) {
698         int32_t runIndex;
699         const UChar *start=pBiDi->text, *limit=start+pBiDi->length, *pu;
700         for(pu=start; pu<limit; pu++) {
701             if(IS_BIDI_CONTROL_CHAR(*pu)) {
702                 runIndex=getRunFromLogicalIndex(pBiDi, (int32_t)(pu-start), pErrorCode);
703                 pBiDi->runs[runIndex].insertRemove--;
704             }
705         }
706     }
707 
708     return TRUE;
709 }
710 
711 static UBool
prepareReorder(const UBiDiLevel * levels,int32_t length,int32_t * indexMap,UBiDiLevel * pMinLevel,UBiDiLevel * pMaxLevel)712 prepareReorder(const UBiDiLevel *levels, int32_t length,
713                int32_t *indexMap,
714                UBiDiLevel *pMinLevel, UBiDiLevel *pMaxLevel) {
715     int32_t start;
716     UBiDiLevel level, minLevel, maxLevel;
717 
718     if(levels==NULL || length<=0) {
719         return FALSE;
720     }
721 
722     /* determine minLevel and maxLevel */
723     minLevel=UBIDI_MAX_EXPLICIT_LEVEL+1;
724     maxLevel=0;
725     for(start=length; start>0;) {
726         level=levels[--start];
727         if(level>UBIDI_MAX_EXPLICIT_LEVEL+1) {
728             return FALSE;
729         }
730         if(level<minLevel) {
731             minLevel=level;
732         }
733         if(level>maxLevel) {
734             maxLevel=level;
735         }
736     }
737     *pMinLevel=minLevel;
738     *pMaxLevel=maxLevel;
739 
740     /* initialize the index map */
741     for(start=length; start>0;) {
742         --start;
743         indexMap[start]=start;
744     }
745 
746     return TRUE;
747 }
748 
749 /* reorder a line based on a levels array (L2) ------------------------------ */
750 
751 U_CAPI void U_EXPORT2
ubidi_reorderLogical(const UBiDiLevel * levels,int32_t length,int32_t * indexMap)752 ubidi_reorderLogical(const UBiDiLevel *levels, int32_t length, int32_t *indexMap) {
753     int32_t start, limit, sumOfSosEos;
754     UBiDiLevel minLevel = 0, maxLevel = 0;
755 
756     if(indexMap==NULL || !prepareReorder(levels, length, indexMap, &minLevel, &maxLevel)) {
757         return;
758     }
759 
760     /* nothing to do? */
761     if(minLevel==maxLevel && (minLevel&1)==0) {
762         return;
763     }
764 
765     /* reorder only down to the lowest odd level */
766     minLevel|=1;
767 
768     /* loop maxLevel..minLevel */
769     do {
770         start=0;
771 
772         /* loop for all sequences of levels to reorder at the current maxLevel */
773         for(;;) {
774             /* look for a sequence of levels that are all at >=maxLevel */
775             /* look for the first index of such a sequence */
776             while(start<length && levels[start]<maxLevel) {
777                 ++start;
778             }
779             if(start>=length) {
780                 break;  /* no more such sequences */
781             }
782 
783             /* look for the limit of such a sequence (the index behind it) */
784             for(limit=start; ++limit<length && levels[limit]>=maxLevel;) {}
785 
786             /*
787              * sos=start of sequence, eos=end of sequence
788              *
789              * The closed (inclusive) interval from sos to eos includes all the logical
790              * and visual indexes within this sequence. They are logically and
791              * visually contiguous and in the same range.
792              *
793              * For each run, the new visual index=sos+eos-old visual index;
794              * we pre-add sos+eos into sumOfSosEos ->
795              * new visual index=sumOfSosEos-old visual index;
796              */
797             sumOfSosEos=start+limit-1;
798 
799             /* reorder each index in the sequence */
800             do {
801                 indexMap[start]=sumOfSosEos-indexMap[start];
802             } while(++start<limit);
803 
804             /* start==limit */
805             if(limit==length) {
806                 break;  /* no more such sequences */
807             } else {
808                 start=limit+1;
809             }
810         }
811     } while(--maxLevel>=minLevel);
812 }
813 
814 U_CAPI void U_EXPORT2
ubidi_reorderVisual(const UBiDiLevel * levels,int32_t length,int32_t * indexMap)815 ubidi_reorderVisual(const UBiDiLevel *levels, int32_t length, int32_t *indexMap) {
816     int32_t start, end, limit, temp;
817     UBiDiLevel minLevel = 0, maxLevel = 0;
818 
819     if(indexMap==NULL || !prepareReorder(levels, length, indexMap, &minLevel, &maxLevel)) {
820         return;
821     }
822 
823     /* nothing to do? */
824     if(minLevel==maxLevel && (minLevel&1)==0) {
825         return;
826     }
827 
828     /* reorder only down to the lowest odd level */
829     minLevel|=1;
830 
831     /* loop maxLevel..minLevel */
832     do {
833         start=0;
834 
835         /* loop for all sequences of levels to reorder at the current maxLevel */
836         for(;;) {
837             /* look for a sequence of levels that are all at >=maxLevel */
838             /* look for the first index of such a sequence */
839             while(start<length && levels[start]<maxLevel) {
840                 ++start;
841             }
842             if(start>=length) {
843                 break;  /* no more such runs */
844             }
845 
846             /* look for the limit of such a sequence (the index behind it) */
847             for(limit=start; ++limit<length && levels[limit]>=maxLevel;) {}
848 
849             /*
850              * Swap the entire interval of indexes from start to limit-1.
851              * We don't need to swap the levels for the purpose of this
852              * algorithm: the sequence of levels that we look at does not
853              * move anyway.
854              */
855             end=limit-1;
856             while(start<end) {
857                 temp=indexMap[start];
858                 indexMap[start]=indexMap[end];
859                 indexMap[end]=temp;
860 
861                 ++start;
862                 --end;
863             }
864 
865             if(limit==length) {
866                 break;  /* no more such sequences */
867             } else {
868                 start=limit+1;
869             }
870         }
871     } while(--maxLevel>=minLevel);
872 }
873 
874 /* API functions for logical<->visual mapping ------------------------------- */
875 
876 U_CAPI int32_t U_EXPORT2
ubidi_getVisualIndex(UBiDi * pBiDi,int32_t logicalIndex,UErrorCode * pErrorCode)877 ubidi_getVisualIndex(UBiDi *pBiDi, int32_t logicalIndex, UErrorCode *pErrorCode) {
878     int32_t visualIndex=UBIDI_MAP_NOWHERE;
879     RETURN_IF_NULL_OR_FAILING_ERRCODE(pErrorCode, -1);
880     RETURN_IF_NOT_VALID_PARA_OR_LINE(pBiDi, *pErrorCode, -1);
881     RETURN_IF_BAD_RANGE(logicalIndex, 0, pBiDi->length, *pErrorCode, -1);
882 
883     /* we can do the trivial cases without the runs array */
884     switch(pBiDi->direction) {
885     case UBIDI_LTR:
886         visualIndex=logicalIndex;
887         break;
888     case UBIDI_RTL:
889         visualIndex=pBiDi->length-logicalIndex-1;
890         break;
891     default:
892         if(!ubidi_getRuns(pBiDi, pErrorCode)) {
893             *pErrorCode=U_MEMORY_ALLOCATION_ERROR;
894             return -1;
895         } else {
896             Run *runs=pBiDi->runs;
897             int32_t i, visualStart=0, offset, length;
898 
899             /* linear search for the run, search on the visual runs */
900             for(i=0; i<pBiDi->runCount; ++i) {
901                 length=runs[i].visualLimit-visualStart;
902                 offset=logicalIndex-GET_INDEX(runs[i].logicalStart);
903                 if(offset>=0 && offset<length) {
904                     if(IS_EVEN_RUN(runs[i].logicalStart)) {
905                         /* LTR */
906                         visualIndex=visualStart+offset;
907                     } else {
908                         /* RTL */
909                         visualIndex=visualStart+length-offset-1;
910                     }
911                     break;          /* exit for loop */
912                 }
913                 visualStart+=length;
914             }
915             if(i>=pBiDi->runCount) {
916                 return UBIDI_MAP_NOWHERE;
917             }
918         }
919     }
920 
921     if(pBiDi->insertPoints.size>0) {
922         /* add the number of added marks until the calculated visual index */
923         Run *runs=pBiDi->runs;
924         int32_t i, length, insertRemove;
925         int32_t visualStart=0, markFound=0;
926         for(i=0; ; i++, visualStart+=length) {
927             length=runs[i].visualLimit-visualStart;
928             insertRemove=runs[i].insertRemove;
929             if(insertRemove & (LRM_BEFORE|RLM_BEFORE)) {
930                 markFound++;
931             }
932             /* is it the run containing the visual index? */
933             if(visualIndex<runs[i].visualLimit) {
934                 return visualIndex+markFound;
935             }
936             if(insertRemove & (LRM_AFTER|RLM_AFTER)) {
937                 markFound++;
938             }
939         }
940     }
941     else if(pBiDi->controlCount>0) {
942         /* subtract the number of controls until the calculated visual index */
943         Run *runs=pBiDi->runs;
944         int32_t i, j, start, limit, length, insertRemove;
945         int32_t visualStart=0, controlFound=0;
946         UChar uchar=pBiDi->text[logicalIndex];
947         /* is the logical index pointing to a control ? */
948         if(IS_BIDI_CONTROL_CHAR(uchar)) {
949             return UBIDI_MAP_NOWHERE;
950         }
951         /* loop on runs */
952         for(i=0; ; i++, visualStart+=length) {
953             length=runs[i].visualLimit-visualStart;
954             insertRemove=runs[i].insertRemove;
955             /* calculated visual index is beyond this run? */
956             if(visualIndex>=runs[i].visualLimit) {
957                 controlFound-=insertRemove;
958                 continue;
959             }
960             /* calculated visual index must be within current run */
961             if(insertRemove==0) {
962                 return visualIndex-controlFound;
963             }
964             if(IS_EVEN_RUN(runs[i].logicalStart)) {
965                 /* LTR: check from run start to logical index */
966                 start=runs[i].logicalStart;
967                 limit=logicalIndex;
968             } else {
969                 /* RTL: check from logical index to run end */
970                 start=logicalIndex+1;
971                 limit=GET_INDEX(runs[i].logicalStart)+length;
972             }
973             for(j=start; j<limit; j++) {
974                 uchar=pBiDi->text[j];
975                 if(IS_BIDI_CONTROL_CHAR(uchar)) {
976                     controlFound++;
977                 }
978             }
979             return visualIndex-controlFound;
980         }
981     }
982 
983     return visualIndex;
984 }
985 
986 U_CAPI int32_t U_EXPORT2
ubidi_getLogicalIndex(UBiDi * pBiDi,int32_t visualIndex,UErrorCode * pErrorCode)987 ubidi_getLogicalIndex(UBiDi *pBiDi, int32_t visualIndex, UErrorCode *pErrorCode) {
988     Run *runs;
989     int32_t i, runCount, start;
990     RETURN_IF_NULL_OR_FAILING_ERRCODE(pErrorCode, -1);
991     RETURN_IF_NOT_VALID_PARA_OR_LINE(pBiDi, *pErrorCode, -1);
992     RETURN_IF_BAD_RANGE(visualIndex, 0, pBiDi->resultLength, *pErrorCode, -1);
993     /* we can do the trivial cases without the runs array */
994     if(pBiDi->insertPoints.size==0 && pBiDi->controlCount==0) {
995         if(pBiDi->direction==UBIDI_LTR) {
996             return visualIndex;
997         }
998         else if(pBiDi->direction==UBIDI_RTL) {
999             return pBiDi->length-visualIndex-1;
1000         }
1001     }
1002     if(!ubidi_getRuns(pBiDi, pErrorCode)) {
1003         *pErrorCode=U_MEMORY_ALLOCATION_ERROR;
1004         return -1;
1005     }
1006 
1007     runs=pBiDi->runs;
1008     runCount=pBiDi->runCount;
1009     if(pBiDi->insertPoints.size>0) {
1010         /* handle inserted LRM/RLM */
1011         int32_t markFound=0, insertRemove;
1012         int32_t visualStart=0, length;
1013         runs=pBiDi->runs;
1014         /* subtract number of marks until visual index */
1015         for(i=0; ; i++, visualStart+=length) {
1016             length=runs[i].visualLimit-visualStart;
1017             insertRemove=runs[i].insertRemove;
1018             if(insertRemove&(LRM_BEFORE|RLM_BEFORE)) {
1019                 if(visualIndex<=(visualStart+markFound)) {
1020                     return UBIDI_MAP_NOWHERE;
1021                 }
1022                 markFound++;
1023             }
1024             /* is adjusted visual index within this run? */
1025             if(visualIndex<(runs[i].visualLimit+markFound)) {
1026                 visualIndex-=markFound;
1027                 break;
1028             }
1029             if(insertRemove&(LRM_AFTER|RLM_AFTER)) {
1030                 if(visualIndex==(visualStart+length+markFound)) {
1031                     return UBIDI_MAP_NOWHERE;
1032                 }
1033                 markFound++;
1034             }
1035         }
1036     }
1037     else if(pBiDi->controlCount>0) {
1038         /* handle removed BiDi control characters */
1039         int32_t controlFound=0, insertRemove, length;
1040         int32_t logicalStart, logicalEnd, visualStart=0, j, k;
1041         UChar uchar;
1042         UBool evenRun;
1043         /* add number of controls until visual index */
1044         for(i=0; ; i++, visualStart+=length) {
1045             length=runs[i].visualLimit-visualStart;
1046             insertRemove=runs[i].insertRemove;
1047             /* is adjusted visual index beyond current run? */
1048             if(visualIndex>=(runs[i].visualLimit-controlFound+insertRemove)) {
1049                 controlFound-=insertRemove;
1050                 continue;
1051             }
1052             /* adjusted visual index is within current run */
1053             if(insertRemove==0) {
1054                 visualIndex+=controlFound;
1055                 break;
1056             }
1057             /* count non-control chars until visualIndex */
1058             logicalStart=runs[i].logicalStart;
1059             evenRun=IS_EVEN_RUN(logicalStart);
1060             REMOVE_ODD_BIT(logicalStart);
1061             logicalEnd=logicalStart+length-1;
1062             for(j=0; j<length; j++) {
1063                 k= evenRun ? logicalStart+j : logicalEnd-j;
1064                 uchar=pBiDi->text[k];
1065                 if(IS_BIDI_CONTROL_CHAR(uchar)) {
1066                     controlFound++;
1067                 }
1068                 if((visualIndex+controlFound)==(visualStart+j)) {
1069                     break;
1070                 }
1071             }
1072             visualIndex+=controlFound;
1073             break;
1074         }
1075     }
1076     /* handle all cases */
1077     if(runCount<=10) {
1078         /* linear search for the run */
1079         for(i=0; visualIndex>=runs[i].visualLimit; ++i) {}
1080     } else {
1081         /* binary search for the run */
1082         int32_t begin=0, limit=runCount;
1083 
1084         /* the middle if() is guaranteed to find the run, we don't need a loop limit */
1085         for(;;) {
1086             i=(begin+limit)/2;
1087             if(visualIndex>=runs[i].visualLimit) {
1088                 begin=i+1;
1089             } else if(i==0 || visualIndex>=runs[i-1].visualLimit) {
1090                 break;
1091             } else {
1092                 limit=i;
1093             }
1094         }
1095     }
1096 
1097     start=runs[i].logicalStart;
1098     if(IS_EVEN_RUN(start)) {
1099         /* LTR */
1100         /* the offset in runs[i] is visualIndex-runs[i-1].visualLimit */
1101         if(i>0) {
1102             visualIndex-=runs[i-1].visualLimit;
1103         }
1104         return start+visualIndex;
1105     } else {
1106         /* RTL */
1107         return GET_INDEX(start)+runs[i].visualLimit-visualIndex-1;
1108     }
1109 }
1110 
1111 U_CAPI void U_EXPORT2
ubidi_getLogicalMap(UBiDi * pBiDi,int32_t * indexMap,UErrorCode * pErrorCode)1112 ubidi_getLogicalMap(UBiDi *pBiDi, int32_t *indexMap, UErrorCode *pErrorCode) {
1113     RETURN_VOID_IF_NULL_OR_FAILING_ERRCODE(pErrorCode);
1114     /* ubidi_countRuns() checks for VALID_PARA_OR_LINE */
1115     ubidi_countRuns(pBiDi, pErrorCode);
1116     if(U_FAILURE(*pErrorCode)) {
1117         /* no op */
1118     } else if(indexMap==NULL) {
1119         *pErrorCode=U_ILLEGAL_ARGUMENT_ERROR;
1120     } else {
1121         /* fill a logical-to-visual index map using the runs[] */
1122         int32_t visualStart, visualLimit, i, j, k;
1123         int32_t logicalStart, logicalLimit;
1124         Run *runs=pBiDi->runs;
1125         if (pBiDi->length<=0) {
1126             return;
1127         }
1128         if (pBiDi->length>pBiDi->resultLength) {
1129             uprv_memset(indexMap, 0xFF, pBiDi->length*sizeof(int32_t));
1130         }
1131 
1132         visualStart=0;
1133         for(j=0; j<pBiDi->runCount; ++j) {
1134             logicalStart=GET_INDEX(runs[j].logicalStart);
1135             visualLimit=runs[j].visualLimit;
1136             if(IS_EVEN_RUN(runs[j].logicalStart)) {
1137                 do { /* LTR */
1138                     indexMap[logicalStart++]=visualStart++;
1139                 } while(visualStart<visualLimit);
1140             } else {
1141                 logicalStart+=visualLimit-visualStart;  /* logicalLimit */
1142                 do { /* RTL */
1143                     indexMap[--logicalStart]=visualStart++;
1144                 } while(visualStart<visualLimit);
1145             }
1146             /* visualStart==visualLimit; */
1147         }
1148 
1149         if(pBiDi->insertPoints.size>0) {
1150             int32_t markFound=0, runCount=pBiDi->runCount;
1151             int32_t length, insertRemove;
1152             visualStart=0;
1153             /* add number of marks found until each index */
1154             for(i=0; i<runCount; i++, visualStart+=length) {
1155                 length=runs[i].visualLimit-visualStart;
1156                 insertRemove=runs[i].insertRemove;
1157                 if(insertRemove&(LRM_BEFORE|RLM_BEFORE)) {
1158                     markFound++;
1159                 }
1160                 if(markFound>0) {
1161                     logicalStart=GET_INDEX(runs[i].logicalStart);
1162                     logicalLimit=logicalStart+length;
1163                     for(j=logicalStart; j<logicalLimit; j++) {
1164                         indexMap[j]+=markFound;
1165                     }
1166                 }
1167                 if(insertRemove&(LRM_AFTER|RLM_AFTER)) {
1168                     markFound++;
1169                 }
1170             }
1171         }
1172         else if(pBiDi->controlCount>0) {
1173             int32_t controlFound=0, runCount=pBiDi->runCount;
1174             int32_t length, insertRemove;
1175             UBool evenRun;
1176             UChar uchar;
1177             visualStart=0;
1178             /* subtract number of controls found until each index */
1179             for(i=0; i<runCount; i++, visualStart+=length) {
1180                 length=runs[i].visualLimit-visualStart;
1181                 insertRemove=runs[i].insertRemove;
1182                 /* no control found within previous runs nor within this run */
1183                 if((controlFound-insertRemove)==0) {
1184                     continue;
1185                 }
1186                 logicalStart=runs[i].logicalStart;
1187                 evenRun=IS_EVEN_RUN(logicalStart);
1188                 REMOVE_ODD_BIT(logicalStart);
1189                 logicalLimit=logicalStart+length;
1190                 /* if no control within this run */
1191                 if(insertRemove==0) {
1192                     for(j=logicalStart; j<logicalLimit; j++) {
1193                         indexMap[j]-=controlFound;
1194                     }
1195                     continue;
1196                 }
1197                 for(j=0; j<length; j++) {
1198                     k= evenRun ? logicalStart+j : logicalLimit-j-1;
1199                     uchar=pBiDi->text[k];
1200                     if(IS_BIDI_CONTROL_CHAR(uchar)) {
1201                         controlFound++;
1202                         indexMap[k]=UBIDI_MAP_NOWHERE;
1203                         continue;
1204                     }
1205                     indexMap[k]-=controlFound;
1206                 }
1207             }
1208         }
1209     }
1210 }
1211 
1212 U_CAPI void U_EXPORT2
ubidi_getVisualMap(UBiDi * pBiDi,int32_t * indexMap,UErrorCode * pErrorCode)1213 ubidi_getVisualMap(UBiDi *pBiDi, int32_t *indexMap, UErrorCode *pErrorCode) {
1214     RETURN_VOID_IF_NULL_OR_FAILING_ERRCODE(pErrorCode);
1215     if(indexMap==NULL) {
1216         *pErrorCode=U_ILLEGAL_ARGUMENT_ERROR;
1217         return;
1218     }
1219     /* ubidi_countRuns() checks for VALID_PARA_OR_LINE */
1220     ubidi_countRuns(pBiDi, pErrorCode);
1221     if(U_SUCCESS(*pErrorCode)) {
1222         /* fill a visual-to-logical index map using the runs[] */
1223         Run *runs=pBiDi->runs, *runsLimit=runs+pBiDi->runCount;
1224         int32_t logicalStart, visualStart, visualLimit, *pi=indexMap;
1225 
1226         if (pBiDi->resultLength<=0) {
1227             return;
1228         }
1229         visualStart=0;
1230         for(; runs<runsLimit; ++runs) {
1231             logicalStart=runs->logicalStart;
1232             visualLimit=runs->visualLimit;
1233             if(IS_EVEN_RUN(logicalStart)) {
1234                 do { /* LTR */
1235                     *pi++ = logicalStart++;
1236                 } while(++visualStart<visualLimit);
1237             } else {
1238                 REMOVE_ODD_BIT(logicalStart);
1239                 logicalStart+=visualLimit-visualStart;  /* logicalLimit */
1240                 do { /* RTL */
1241                     *pi++ = --logicalStart;
1242                 } while(++visualStart<visualLimit);
1243             }
1244             /* visualStart==visualLimit; */
1245         }
1246 
1247         if(pBiDi->insertPoints.size>0) {
1248             int32_t markFound=0, runCount=pBiDi->runCount;
1249             int32_t insertRemove, i, j, k;
1250             runs=pBiDi->runs;
1251             /* count all inserted marks */
1252             for(i=0; i<runCount; i++) {
1253                 insertRemove=runs[i].insertRemove;
1254                 if(insertRemove&(LRM_BEFORE|RLM_BEFORE)) {
1255                     markFound++;
1256                 }
1257                 if(insertRemove&(LRM_AFTER|RLM_AFTER)) {
1258                     markFound++;
1259                 }
1260             }
1261             /* move back indexes by number of preceding marks */
1262             k=pBiDi->resultLength;
1263             for(i=runCount-1; i>=0 && markFound>0; i--) {
1264                 insertRemove=runs[i].insertRemove;
1265                 if(insertRemove&(LRM_AFTER|RLM_AFTER)) {
1266                     indexMap[--k]= UBIDI_MAP_NOWHERE;
1267                     markFound--;
1268                 }
1269                 visualStart= i>0 ? runs[i-1].visualLimit : 0;
1270                 for(j=runs[i].visualLimit-1; j>=visualStart && markFound>0; j--) {
1271                     indexMap[--k]=indexMap[j];
1272                 }
1273                 if(insertRemove&(LRM_BEFORE|RLM_BEFORE)) {
1274                     indexMap[--k]= UBIDI_MAP_NOWHERE;
1275                     markFound--;
1276                 }
1277             }
1278         }
1279         else if(pBiDi->controlCount>0) {
1280             int32_t runCount=pBiDi->runCount, logicalEnd;
1281             int32_t insertRemove, length, i, j, k, m;
1282             UChar uchar;
1283             UBool evenRun;
1284             runs=pBiDi->runs;
1285             visualStart=0;
1286             /* move forward indexes by number of preceding controls */
1287             k=0;
1288             for(i=0; i<runCount; i++, visualStart+=length) {
1289                 length=runs[i].visualLimit-visualStart;
1290                 insertRemove=runs[i].insertRemove;
1291                 /* if no control found yet, nothing to do in this run */
1292                 if((insertRemove==0)&&(k==visualStart)) {
1293                     k+=length;
1294                     continue;
1295                 }
1296                 /* if no control in this run */
1297                 if(insertRemove==0) {
1298                     visualLimit=runs[i].visualLimit;
1299                     for(j=visualStart; j<visualLimit; j++) {
1300                         indexMap[k++]=indexMap[j];
1301                     }
1302                     continue;
1303                 }
1304                 logicalStart=runs[i].logicalStart;
1305                 evenRun=IS_EVEN_RUN(logicalStart);
1306                 REMOVE_ODD_BIT(logicalStart);
1307                 logicalEnd=logicalStart+length-1;
1308                 for(j=0; j<length; j++) {
1309                     m= evenRun ? logicalStart+j : logicalEnd-j;
1310                     uchar=pBiDi->text[m];
1311                     if(!IS_BIDI_CONTROL_CHAR(uchar)) {
1312                         indexMap[k++]=m;
1313                     }
1314                 }
1315             }
1316         }
1317     }
1318 }
1319 
1320 U_CAPI void U_EXPORT2
ubidi_invertMap(const int32_t * srcMap,int32_t * destMap,int32_t length)1321 ubidi_invertMap(const int32_t *srcMap, int32_t *destMap, int32_t length) {
1322     if(srcMap!=NULL && destMap!=NULL && length>0) {
1323         const int32_t *pi;
1324         int32_t destLength=-1, count=0;
1325         /* find highest value and count positive indexes in srcMap */
1326         pi=srcMap+length;
1327         while(pi>srcMap) {
1328             if(*--pi>destLength) {
1329                 destLength=*pi;
1330             }
1331             if(*pi>=0) {
1332                 count++;
1333             }
1334         }
1335         destLength++;           /* add 1 for origin 0 */
1336         if(count<destLength) {
1337             /* we must fill unmatched destMap entries with -1 */
1338             uprv_memset(destMap, 0xFF, destLength*sizeof(int32_t));
1339         }
1340         pi=srcMap+length;
1341         while(length>0) {
1342             if(*--pi>=0) {
1343                 destMap[*pi]=--length;
1344             } else {
1345                 --length;
1346             }
1347         }
1348     }
1349 }
1350