Line data Source code
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
92 0 : setTrailingWSStart(UBiDi *pBiDi) {
93 : /* pBiDi->direction!=UBIDI_MIXED */
94 :
95 0 : const DirProp *dirProps=pBiDi->dirProps;
96 0 : UBiDiLevel *levels=pBiDi->levels;
97 0 : int32_t start=pBiDi->length;
98 0 : 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 0 : if(dirProps[start-1]==B) {
107 0 : pBiDi->trailingWSStart=start; /* currently == pBiDi->length */
108 0 : return;
109 : }
110 : /* go backwards across all WS, BN, explicit codes */
111 0 : while(start>0 && DIRPROP_FLAG(dirProps[start-1])&MASK_WS) {
112 0 : --start;
113 : }
114 :
115 : /* if the WS run can be merged with the previous run then do so here */
116 0 : while(start>0 && levels[start-1]==paraLevel) {
117 0 : --start;
118 : }
119 :
120 0 : pBiDi->trailingWSStart=start;
121 : }
122 :
123 : /* ubidi_setLine ------------------------------------------------------------ */
124 :
125 : U_CAPI void U_EXPORT2
126 0 : 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 0 : RETURN_VOID_IF_NULL_OR_FAILING_ERRCODE(pErrorCode);
134 0 : RETURN_VOID_IF_NOT_VALID_PARA(pParaBiDi, *pErrorCode);
135 0 : RETURN_VOID_IF_BAD_RANGE(start, 0, limit, *pErrorCode);
136 0 : RETURN_VOID_IF_BAD_RANGE(limit, 0, pParaBiDi->length+1, *pErrorCode);
137 0 : if(pLineBiDi==NULL) {
138 0 : *pErrorCode=U_ILLEGAL_ARGUMENT_ERROR;
139 0 : return;
140 : }
141 0 : if(ubidi_getParagraph(pParaBiDi, start, NULL, NULL, NULL, pErrorCode) !=
142 0 : ubidi_getParagraph(pParaBiDi, limit-1, NULL, NULL, NULL, pErrorCode)) {
143 : /* the line crosses a paragraph boundary */
144 0 : *pErrorCode=U_ILLEGAL_ARGUMENT_ERROR;
145 0 : return;
146 : }
147 :
148 : /* set the values in pLineBiDi from its pParaBiDi parent */
149 0 : pLineBiDi->pParaBiDi=NULL; /* mark unfinished setLine */
150 0 : pLineBiDi->text=pParaBiDi->text+start;
151 0 : length=pLineBiDi->length=limit-start;
152 0 : pLineBiDi->resultLength=pLineBiDi->originalLength=length;
153 0 : pLineBiDi->paraLevel=GET_PARALEVEL(pParaBiDi, start);
154 0 : pLineBiDi->paraCount=pParaBiDi->paraCount;
155 0 : pLineBiDi->runs=NULL;
156 0 : pLineBiDi->flags=0;
157 0 : pLineBiDi->reorderingMode=pParaBiDi->reorderingMode;
158 0 : pLineBiDi->reorderingOptions=pParaBiDi->reorderingOptions;
159 0 : pLineBiDi->controlCount=0;
160 0 : if(pParaBiDi->controlCount>0) {
161 : int32_t j;
162 0 : for(j=start; j<limit; j++) {
163 0 : if(IS_BIDI_CONTROL_CHAR(pParaBiDi->text[j])) {
164 0 : pLineBiDi->controlCount++;
165 : }
166 : }
167 0 : pLineBiDi->resultLength-=pLineBiDi->controlCount;
168 : }
169 :
170 0 : pLineBiDi->dirProps=pParaBiDi->dirProps+start;
171 0 : pLineBiDi->levels=pParaBiDi->levels+start;
172 0 : pLineBiDi->runCount=-1;
173 :
174 0 : if(pParaBiDi->direction!=UBIDI_MIXED) {
175 : /* the parent is already trivial */
176 0 : 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 0 : if(pParaBiDi->trailingWSStart<=start) {
184 0 : pLineBiDi->trailingWSStart=0;
185 0 : } else if(pParaBiDi->trailingWSStart<limit) {
186 0 : pLineBiDi->trailingWSStart=pParaBiDi->trailingWSStart-start;
187 : } else {
188 0 : pLineBiDi->trailingWSStart=length;
189 : }
190 : } else {
191 0 : const UBiDiLevel *levels=pLineBiDi->levels;
192 : int32_t i, trailingWSStart;
193 : UBiDiLevel level;
194 :
195 0 : setTrailingWSStart(pLineBiDi);
196 0 : trailingWSStart=pLineBiDi->trailingWSStart;
197 :
198 : /* recalculate pLineBiDi->direction */
199 0 : if(trailingWSStart==0) {
200 : /* all levels are at paraLevel */
201 0 : pLineBiDi->direction=(UBiDiDirection)(pLineBiDi->paraLevel&1);
202 : } else {
203 : /* get the level of the first character */
204 0 : level=(UBiDiLevel)(levels[0]&1);
205 :
206 : /* if there is anything of a different level, then the line is mixed */
207 0 : if(trailingWSStart<length && (pLineBiDi->paraLevel&1)!=level) {
208 : /* the trailing WS is at paraLevel, which differs from levels[0] */
209 0 : pLineBiDi->direction=UBIDI_MIXED;
210 : } else {
211 : /* see if levels[1..trailingWSStart-1] have the same direction as levels[0] and paraLevel */
212 0 : i=1;
213 : for(;;) {
214 0 : if(i==trailingWSStart) {
215 : /* the direction values match those in level */
216 0 : pLineBiDi->direction=(UBiDiDirection)level;
217 0 : break;
218 0 : } else if((levels[i]&1)!=level) {
219 0 : pLineBiDi->direction=UBIDI_MIXED;
220 0 : break;
221 : }
222 0 : ++i;
223 : }
224 : }
225 : }
226 :
227 0 : switch(pLineBiDi->direction) {
228 : case UBIDI_LTR:
229 : /* make sure paraLevel is even */
230 0 : pLineBiDi->paraLevel=(UBiDiLevel)((pLineBiDi->paraLevel+1)&~1);
231 :
232 : /* all levels are implicitly at paraLevel (important for ubidi_getLevels()) */
233 0 : pLineBiDi->trailingWSStart=0;
234 0 : break;
235 : case UBIDI_RTL:
236 : /* make sure paraLevel is odd */
237 0 : pLineBiDi->paraLevel|=1;
238 :
239 : /* all levels are implicitly at paraLevel (important for ubidi_getLevels()) */
240 0 : pLineBiDi->trailingWSStart=0;
241 0 : break;
242 : default:
243 0 : break;
244 : }
245 : }
246 0 : pLineBiDi->pParaBiDi=pParaBiDi; /* mark successful setLine */
247 0 : return;
248 : }
249 :
250 : U_CAPI UBiDiLevel U_EXPORT2
251 0 : ubidi_getLevelAt(const UBiDi *pBiDi, int32_t charIndex) {
252 : /* return paraLevel if in the trailing WS run, otherwise the real level */
253 0 : if(!IS_VALID_PARA_OR_LINE(pBiDi) || charIndex<0 || pBiDi->length<=charIndex) {
254 0 : return 0;
255 0 : } else if(pBiDi->direction!=UBIDI_MIXED || charIndex>=pBiDi->trailingWSStart) {
256 0 : return GET_PARALEVEL(pBiDi, charIndex);
257 : } else {
258 0 : return pBiDi->levels[charIndex];
259 : }
260 : }
261 :
262 : U_CAPI const UBiDiLevel * U_EXPORT2
263 0 : ubidi_getLevels(UBiDi *pBiDi, UErrorCode *pErrorCode) {
264 : int32_t start, length;
265 :
266 0 : RETURN_IF_NULL_OR_FAILING_ERRCODE(pErrorCode, NULL);
267 0 : RETURN_IF_NOT_VALID_PARA_OR_LINE(pBiDi, *pErrorCode, NULL);
268 0 : if((length=pBiDi->length)<=0) {
269 0 : *pErrorCode=U_ILLEGAL_ARGUMENT_ERROR;
270 0 : return NULL;
271 : }
272 0 : if((start=pBiDi->trailingWSStart)==length) {
273 : /* the current levels array reflects the WS run */
274 0 : 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 0 : if(getLevelsMemory(pBiDi, length)) {
285 0 : UBiDiLevel *levels=pBiDi->levelsMemory;
286 :
287 0 : if(start>0 && levels!=pBiDi->levels) {
288 0 : 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 0 : 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 0 : pBiDi->trailingWSStart=length;
296 0 : return pBiDi->levels=levels;
297 : } else {
298 : /* out of memory */
299 0 : *pErrorCode=U_MEMORY_ALLOCATION_ERROR;
300 0 : return NULL;
301 : }
302 : }
303 :
304 : U_CAPI void U_EXPORT2
305 0 : 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 0 : errorCode=U_ZERO_ERROR;
312 0 : RETURN_VOID_IF_BAD_RANGE(logicalPosition, 0, pBiDi->length, errorCode);
313 : /* ubidi_countRuns will check VALID_PARA_OR_LINE */
314 0 : runCount=ubidi_countRuns((UBiDi *)pBiDi, &errorCode);
315 0 : if(U_FAILURE(errorCode)) {
316 0 : 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 0 : visualStart=logicalLimit=0;
322 0 : iRun=pBiDi->runs[0];
323 :
324 0 : for(i=0; i<runCount; i++) {
325 0 : iRun = pBiDi->runs[i];
326 0 : logicalFirst=GET_INDEX(iRun.logicalStart);
327 0 : logicalLimit=logicalFirst+iRun.visualLimit-visualStart;
328 0 : if((logicalPosition>=logicalFirst) &&
329 : (logicalPosition<logicalLimit)) {
330 0 : break;
331 : }
332 0 : visualStart = iRun.visualLimit;
333 : }
334 0 : if(pLogicalLimit) {
335 0 : *pLogicalLimit=logicalLimit;
336 : }
337 0 : if(pLevel) {
338 0 : if(pBiDi->reorderingMode==UBIDI_REORDER_RUNS_ONLY) {
339 0 : *pLevel=(UBiDiLevel)GET_ODD_BIT(iRun.logicalStart);
340 : }
341 0 : else if(pBiDi->direction!=UBIDI_MIXED || logicalPosition>=pBiDi->trailingWSStart) {
342 0 : *pLevel=GET_PARALEVEL(pBiDi, logicalPosition);
343 : } else {
344 0 : *pLevel=pBiDi->levels[logicalPosition];
345 : }
346 : }
347 : }
348 :
349 : /* runs API functions ------------------------------------------------------- */
350 :
351 : U_CAPI int32_t U_EXPORT2
352 0 : ubidi_countRuns(UBiDi *pBiDi, UErrorCode *pErrorCode) {
353 0 : RETURN_IF_NULL_OR_FAILING_ERRCODE(pErrorCode, -1);
354 0 : RETURN_IF_NOT_VALID_PARA_OR_LINE(pBiDi, *pErrorCode, -1);
355 0 : ubidi_getRuns(pBiDi, pErrorCode);
356 0 : if(U_FAILURE(*pErrorCode)) {
357 0 : return -1;
358 : }
359 0 : return pBiDi->runCount;
360 : }
361 :
362 : U_CAPI UBiDiDirection U_EXPORT2
363 0 : ubidi_getVisualRun(UBiDi *pBiDi, int32_t runIndex,
364 : int32_t *pLogicalStart, int32_t *pLength)
365 : {
366 : int32_t start;
367 0 : UErrorCode errorCode = U_ZERO_ERROR;
368 0 : RETURN_IF_NOT_VALID_PARA_OR_LINE(pBiDi, errorCode, UBIDI_LTR);
369 0 : ubidi_getRuns(pBiDi, &errorCode);
370 0 : if(U_FAILURE(errorCode)) {
371 0 : return UBIDI_LTR;
372 : }
373 0 : RETURN_IF_BAD_RANGE(runIndex, 0, pBiDi->runCount, errorCode, UBIDI_LTR);
374 :
375 0 : start=pBiDi->runs[runIndex].logicalStart;
376 0 : if(pLogicalStart!=NULL) {
377 0 : *pLogicalStart=GET_INDEX(start);
378 : }
379 0 : if(pLength!=NULL) {
380 0 : if(runIndex>0) {
381 0 : *pLength=pBiDi->runs[runIndex].visualLimit-
382 0 : pBiDi->runs[runIndex-1].visualLimit;
383 : } else {
384 0 : *pLength=pBiDi->runs[0].visualLimit;
385 : }
386 : }
387 0 : 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
392 0 : getSingleRun(UBiDi *pBiDi, UBiDiLevel level) {
393 : /* simple, single-run case */
394 0 : pBiDi->runs=pBiDi->simpleRuns;
395 0 : pBiDi->runCount=1;
396 :
397 : /* fill and reorder the single run */
398 0 : pBiDi->runs[0].logicalStart=MAKE_INDEX_ODD_PAIR(0, level);
399 0 : pBiDi->runs[0].visualLimit=pBiDi->length;
400 0 : pBiDi->runs[0].insertRemove=0;
401 0 : }
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
437 0 : 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 0 : if(maxLevel<=(minLevel|1)) {
444 0 : 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 0 : ++minLevel;
453 :
454 0 : runs=pBiDi->runs;
455 0 : levels=pBiDi->levels;
456 0 : runCount=pBiDi->runCount;
457 :
458 : /* do not include the WS run at paraLevel<=old minLevel except in the simple loop */
459 0 : if(pBiDi->trailingWSStart<pBiDi->length) {
460 0 : --runCount;
461 : }
462 :
463 0 : while(--maxLevel>=minLevel) {
464 0 : firstRun=0;
465 :
466 : /* loop for all sequences of runs */
467 0 : for(;;) {
468 : /* look for a sequence of runs that are all at >=maxLevel */
469 : /* look for the first run of such a sequence */
470 0 : while(firstRun<runCount && levels[runs[firstRun].logicalStart]<maxLevel) {
471 0 : ++firstRun;
472 : }
473 0 : if(firstRun>=runCount) {
474 0 : break; /* no more such runs */
475 : }
476 :
477 : /* look for the limit run of such a sequence (the run behind it) */
478 0 : for(limitRun=firstRun; ++limitRun<runCount && levels[runs[limitRun].logicalStart]>=maxLevel;) {}
479 :
480 : /* Swap the entire sequence of runs from firstRun to limitRun-1. */
481 0 : endRun=limitRun-1;
482 0 : while(firstRun<endRun) {
483 0 : tempRun = runs[firstRun];
484 0 : runs[firstRun]=runs[endRun];
485 0 : runs[endRun]=tempRun;
486 0 : ++firstRun;
487 0 : --endRun;
488 : }
489 :
490 0 : if(limitRun==runCount) {
491 0 : break; /* no more such runs */
492 : } else {
493 0 : firstRun=limitRun+1;
494 : }
495 : }
496 : }
497 :
498 : /* now do maxLevel==old minLevel (==odd!), see above */
499 0 : if(!(minLevel&1)) {
500 0 : firstRun=0;
501 :
502 : /* include the trailing WS run in this complete reordering */
503 0 : if(pBiDi->trailingWSStart==pBiDi->length) {
504 0 : --runCount;
505 : }
506 :
507 : /* Swap the entire sequence of all runs. (endRun==runCount) */
508 0 : while(firstRun<runCount) {
509 0 : tempRun=runs[firstRun];
510 0 : runs[firstRun]=runs[runCount];
511 0 : runs[runCount]=tempRun;
512 0 : ++firstRun;
513 0 : --runCount;
514 : }
515 : }
516 : }
517 :
518 : /* compute the runs array --------------------------------------------------- */
519 :
520 0 : static int32_t getRunFromLogicalIndex(UBiDi *pBiDi, int32_t logicalIndex, UErrorCode *pErrorCode) {
521 0 : Run *runs=pBiDi->runs;
522 0 : int32_t runCount=pBiDi->runCount, visualStart=0, i, length, logicalStart;
523 :
524 0 : for(i=0; i<runCount; i++) {
525 0 : length=runs[i].visualLimit-visualStart;
526 0 : logicalStart=GET_INDEX(runs[i].logicalStart);
527 0 : if((logicalIndex>=logicalStart) && (logicalIndex<(logicalStart+length))) {
528 0 : return i;
529 : }
530 0 : visualStart+=length;
531 : }
532 : /* we should never get here */
533 0 : 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
550 0 : 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 0 : if (pBiDi->runCount>=0) {
556 0 : return TRUE;
557 : }
558 :
559 0 : 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 0 : getSingleRun(pBiDi, pBiDi->paraLevel);
563 : } else /* UBIDI_MIXED, length>0 */ {
564 : /* mixed directionality */
565 0 : int32_t length=pBiDi->length, limit;
566 0 : UBiDiLevel *levels=pBiDi->levels;
567 : int32_t i, runCount;
568 0 : 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 0 : limit=pBiDi->trailingWSStart;
581 : /* count the runs, there is at least one non-WS run, and limit>0 */
582 0 : runCount=0;
583 0 : for(i=0; i<limit; ++i) {
584 : /* increment runCount at the start of each run */
585 0 : if(levels[i]!=level) {
586 0 : ++runCount;
587 0 : 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 0 : if(runCount==1 && limit==length) {
596 : /* There is only one non-WS run and no trailing WS-run. */
597 0 : 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 0 : UBiDiLevel minLevel=UBIDI_MAX_EXPLICIT_LEVEL+1, maxLevel=0;
603 :
604 : /* now, count a (non-mergeable) WS run */
605 0 : if(limit<length) {
606 0 : ++runCount;
607 : }
608 :
609 : /* runCount>1 */
610 0 : if(getRunsMemory(pBiDi, runCount)) {
611 0 : runs=pBiDi->runsMemory;
612 : } else {
613 0 : 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 0 : runIndex=0;
623 :
624 : /* search for the run limits and initialize visualLimit values with the run lengths */
625 0 : i=0;
626 0 : do {
627 : /* prepare this run */
628 0 : start=i;
629 0 : level=levels[i];
630 0 : if(level<minLevel) {
631 0 : minLevel=level;
632 : }
633 0 : if(level>maxLevel) {
634 0 : maxLevel=level;
635 : }
636 :
637 : /* look for the run limit */
638 0 : while(++i<limit && levels[i]==level) {}
639 :
640 : /* i is another run limit */
641 0 : runs[runIndex].logicalStart=start;
642 0 : runs[runIndex].visualLimit=i-start;
643 0 : runs[runIndex].insertRemove=0;
644 0 : ++runIndex;
645 0 : } while(i<limit);
646 :
647 0 : if(limit<length) {
648 : /* there is a separate WS run */
649 0 : runs[runIndex].logicalStart=limit;
650 0 : runs[runIndex].visualLimit=length-limit;
651 : /* For the trailing WS run, pBiDi->paraLevel is ok even
652 : if contextual multiple paragraphs. */
653 0 : if(pBiDi->paraLevel<minLevel) {
654 0 : minLevel=pBiDi->paraLevel;
655 : }
656 : }
657 :
658 : /* set the object fields */
659 0 : pBiDi->runs=runs;
660 0 : pBiDi->runCount=runCount;
661 :
662 0 : 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 0 : limit=0;
667 0 : for(i=0; i<runCount; ++i) {
668 0 : ADD_ODD_BIT_FROM_LEVEL(runs[i].logicalStart, levels[runs[i].logicalStart]);
669 0 : limit+=runs[i].visualLimit;
670 0 : 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 0 : if(runIndex<runCount) {
678 0 : int32_t trailingRun = ((pBiDi->paraLevel & 1) != 0)? 0 : runIndex;
679 :
680 0 : ADD_ODD_BIT_FROM_LEVEL(runs[trailingRun].logicalStart, pBiDi->paraLevel);
681 : }
682 : }
683 : }
684 :
685 : /* handle insert LRM/RLM BEFORE/AFTER run */
686 0 : if(pBiDi->insertPoints.size>0) {
687 0 : Point *point, *start=pBiDi->insertPoints.points,
688 0 : *limit=start+pBiDi->insertPoints.size;
689 : int32_t runIndex;
690 0 : for(point=start; point<limit; point++) {
691 0 : runIndex=getRunFromLogicalIndex(pBiDi, point->pos, pErrorCode);
692 0 : pBiDi->runs[runIndex].insertRemove|=point->flag;
693 : }
694 : }
695 :
696 : /* handle remove BiDi control characters */
697 0 : if(pBiDi->controlCount>0) {
698 : int32_t runIndex;
699 0 : const UChar *start=pBiDi->text, *limit=start+pBiDi->length, *pu;
700 0 : for(pu=start; pu<limit; pu++) {
701 0 : if(IS_BIDI_CONTROL_CHAR(*pu)) {
702 0 : runIndex=getRunFromLogicalIndex(pBiDi, (int32_t)(pu-start), pErrorCode);
703 0 : pBiDi->runs[runIndex].insertRemove--;
704 : }
705 : }
706 : }
707 :
708 0 : return TRUE;
709 : }
710 :
711 : static UBool
712 0 : 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 0 : if(levels==NULL || length<=0) {
719 0 : return FALSE;
720 : }
721 :
722 : /* determine minLevel and maxLevel */
723 0 : minLevel=UBIDI_MAX_EXPLICIT_LEVEL+1;
724 0 : maxLevel=0;
725 0 : for(start=length; start>0;) {
726 0 : level=levels[--start];
727 0 : if(level>UBIDI_MAX_EXPLICIT_LEVEL+1) {
728 0 : return FALSE;
729 : }
730 0 : if(level<minLevel) {
731 0 : minLevel=level;
732 : }
733 0 : if(level>maxLevel) {
734 0 : maxLevel=level;
735 : }
736 : }
737 0 : *pMinLevel=minLevel;
738 0 : *pMaxLevel=maxLevel;
739 :
740 : /* initialize the index map */
741 0 : for(start=length; start>0;) {
742 0 : --start;
743 0 : indexMap[start]=start;
744 : }
745 :
746 0 : return TRUE;
747 : }
748 :
749 : /* reorder a line based on a levels array (L2) ------------------------------ */
750 :
751 : U_CAPI void U_EXPORT2
752 0 : ubidi_reorderLogical(const UBiDiLevel *levels, int32_t length, int32_t *indexMap) {
753 : int32_t start, limit, sumOfSosEos;
754 0 : UBiDiLevel minLevel = 0, maxLevel = 0;
755 :
756 0 : if(indexMap==NULL || !prepareReorder(levels, length, indexMap, &minLevel, &maxLevel)) {
757 0 : return;
758 : }
759 :
760 : /* nothing to do? */
761 0 : if(minLevel==maxLevel && (minLevel&1)==0) {
762 0 : return;
763 : }
764 :
765 : /* reorder only down to the lowest odd level */
766 0 : minLevel|=1;
767 :
768 : /* loop maxLevel..minLevel */
769 0 : do {
770 0 : start=0;
771 :
772 : /* loop for all sequences of levels to reorder at the current maxLevel */
773 0 : for(;;) {
774 : /* look for a sequence of levels that are all at >=maxLevel */
775 : /* look for the first index of such a sequence */
776 0 : while(start<length && levels[start]<maxLevel) {
777 0 : ++start;
778 : }
779 0 : if(start>=length) {
780 0 : break; /* no more such sequences */
781 : }
782 :
783 : /* look for the limit of such a sequence (the index behind it) */
784 0 : 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 0 : sumOfSosEos=start+limit-1;
798 :
799 : /* reorder each index in the sequence */
800 0 : do {
801 0 : indexMap[start]=sumOfSosEos-indexMap[start];
802 : } while(++start<limit);
803 :
804 : /* start==limit */
805 0 : if(limit==length) {
806 0 : break; /* no more such sequences */
807 : } else {
808 0 : start=limit+1;
809 : }
810 : }
811 0 : } while(--maxLevel>=minLevel);
812 : }
813 :
814 : U_CAPI void U_EXPORT2
815 0 : ubidi_reorderVisual(const UBiDiLevel *levels, int32_t length, int32_t *indexMap) {
816 : int32_t start, end, limit, temp;
817 0 : UBiDiLevel minLevel = 0, maxLevel = 0;
818 :
819 0 : if(indexMap==NULL || !prepareReorder(levels, length, indexMap, &minLevel, &maxLevel)) {
820 0 : return;
821 : }
822 :
823 : /* nothing to do? */
824 0 : if(minLevel==maxLevel && (minLevel&1)==0) {
825 0 : return;
826 : }
827 :
828 : /* reorder only down to the lowest odd level */
829 0 : minLevel|=1;
830 :
831 : /* loop maxLevel..minLevel */
832 0 : do {
833 0 : start=0;
834 :
835 : /* loop for all sequences of levels to reorder at the current maxLevel */
836 0 : for(;;) {
837 : /* look for a sequence of levels that are all at >=maxLevel */
838 : /* look for the first index of such a sequence */
839 0 : while(start<length && levels[start]<maxLevel) {
840 0 : ++start;
841 : }
842 0 : if(start>=length) {
843 0 : break; /* no more such runs */
844 : }
845 :
846 : /* look for the limit of such a sequence (the index behind it) */
847 0 : 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 0 : end=limit-1;
856 0 : while(start<end) {
857 0 : temp=indexMap[start];
858 0 : indexMap[start]=indexMap[end];
859 0 : indexMap[end]=temp;
860 :
861 0 : ++start;
862 0 : --end;
863 : }
864 :
865 0 : if(limit==length) {
866 0 : break; /* no more such sequences */
867 : } else {
868 0 : start=limit+1;
869 : }
870 : }
871 0 : } while(--maxLevel>=minLevel);
872 : }
873 :
874 : /* API functions for logical<->visual mapping ------------------------------- */
875 :
876 : U_CAPI int32_t U_EXPORT2
877 0 : ubidi_getVisualIndex(UBiDi *pBiDi, int32_t logicalIndex, UErrorCode *pErrorCode) {
878 0 : int32_t visualIndex=UBIDI_MAP_NOWHERE;
879 0 : RETURN_IF_NULL_OR_FAILING_ERRCODE(pErrorCode, -1);
880 0 : RETURN_IF_NOT_VALID_PARA_OR_LINE(pBiDi, *pErrorCode, -1);
881 0 : RETURN_IF_BAD_RANGE(logicalIndex, 0, pBiDi->length, *pErrorCode, -1);
882 :
883 : /* we can do the trivial cases without the runs array */
884 0 : switch(pBiDi->direction) {
885 : case UBIDI_LTR:
886 0 : visualIndex=logicalIndex;
887 0 : break;
888 : case UBIDI_RTL:
889 0 : visualIndex=pBiDi->length-logicalIndex-1;
890 0 : break;
891 : default:
892 0 : if(!ubidi_getRuns(pBiDi, pErrorCode)) {
893 0 : *pErrorCode=U_MEMORY_ALLOCATION_ERROR;
894 0 : return -1;
895 : } else {
896 0 : Run *runs=pBiDi->runs;
897 0 : int32_t i, visualStart=0, offset, length;
898 :
899 : /* linear search for the run, search on the visual runs */
900 0 : for(i=0; i<pBiDi->runCount; ++i) {
901 0 : length=runs[i].visualLimit-visualStart;
902 0 : offset=logicalIndex-GET_INDEX(runs[i].logicalStart);
903 0 : if(offset>=0 && offset<length) {
904 0 : if(IS_EVEN_RUN(runs[i].logicalStart)) {
905 : /* LTR */
906 0 : visualIndex=visualStart+offset;
907 : } else {
908 : /* RTL */
909 0 : visualIndex=visualStart+length-offset-1;
910 : }
911 0 : break; /* exit for loop */
912 : }
913 0 : visualStart+=length;
914 : }
915 0 : if(i>=pBiDi->runCount) {
916 0 : return UBIDI_MAP_NOWHERE;
917 : }
918 : }
919 : }
920 :
921 0 : if(pBiDi->insertPoints.size>0) {
922 : /* add the number of added marks until the calculated visual index */
923 0 : Run *runs=pBiDi->runs;
924 : int32_t i, length, insertRemove;
925 0 : int32_t visualStart=0, markFound=0;
926 0 : for(i=0; ; i++, visualStart+=length) {
927 0 : length=runs[i].visualLimit-visualStart;
928 0 : insertRemove=runs[i].insertRemove;
929 0 : if(insertRemove & (LRM_BEFORE|RLM_BEFORE)) {
930 0 : markFound++;
931 : }
932 : /* is it the run containing the visual index? */
933 0 : if(visualIndex<runs[i].visualLimit) {
934 0 : return visualIndex+markFound;
935 : }
936 0 : if(insertRemove & (LRM_AFTER|RLM_AFTER)) {
937 0 : markFound++;
938 : }
939 : }
940 : }
941 0 : else if(pBiDi->controlCount>0) {
942 : /* subtract the number of controls until the calculated visual index */
943 0 : Run *runs=pBiDi->runs;
944 : int32_t i, j, start, limit, length, insertRemove;
945 0 : int32_t visualStart=0, controlFound=0;
946 0 : UChar uchar=pBiDi->text[logicalIndex];
947 : /* is the logical index pointing to a control ? */
948 0 : if(IS_BIDI_CONTROL_CHAR(uchar)) {
949 0 : return UBIDI_MAP_NOWHERE;
950 : }
951 : /* loop on runs */
952 0 : for(i=0; ; i++, visualStart+=length) {
953 0 : length=runs[i].visualLimit-visualStart;
954 0 : insertRemove=runs[i].insertRemove;
955 : /* calculated visual index is beyond this run? */
956 0 : if(visualIndex>=runs[i].visualLimit) {
957 0 : controlFound-=insertRemove;
958 0 : continue;
959 : }
960 : /* calculated visual index must be within current run */
961 0 : if(insertRemove==0) {
962 0 : return visualIndex-controlFound;
963 : }
964 0 : if(IS_EVEN_RUN(runs[i].logicalStart)) {
965 : /* LTR: check from run start to logical index */
966 0 : start=runs[i].logicalStart;
967 0 : limit=logicalIndex;
968 : } else {
969 : /* RTL: check from logical index to run end */
970 0 : start=logicalIndex+1;
971 0 : limit=GET_INDEX(runs[i].logicalStart)+length;
972 : }
973 0 : for(j=start; j<limit; j++) {
974 0 : uchar=pBiDi->text[j];
975 0 : if(IS_BIDI_CONTROL_CHAR(uchar)) {
976 0 : controlFound++;
977 : }
978 : }
979 0 : return visualIndex-controlFound;
980 : }
981 : }
982 :
983 0 : return visualIndex;
984 : }
985 :
986 : U_CAPI int32_t U_EXPORT2
987 0 : ubidi_getLogicalIndex(UBiDi *pBiDi, int32_t visualIndex, UErrorCode *pErrorCode) {
988 : Run *runs;
989 : int32_t i, runCount, start;
990 0 : RETURN_IF_NULL_OR_FAILING_ERRCODE(pErrorCode, -1);
991 0 : RETURN_IF_NOT_VALID_PARA_OR_LINE(pBiDi, *pErrorCode, -1);
992 0 : RETURN_IF_BAD_RANGE(visualIndex, 0, pBiDi->resultLength, *pErrorCode, -1);
993 : /* we can do the trivial cases without the runs array */
994 0 : if(pBiDi->insertPoints.size==0 && pBiDi->controlCount==0) {
995 0 : if(pBiDi->direction==UBIDI_LTR) {
996 0 : return visualIndex;
997 : }
998 0 : else if(pBiDi->direction==UBIDI_RTL) {
999 0 : return pBiDi->length-visualIndex-1;
1000 : }
1001 : }
1002 0 : if(!ubidi_getRuns(pBiDi, pErrorCode)) {
1003 0 : *pErrorCode=U_MEMORY_ALLOCATION_ERROR;
1004 0 : return -1;
1005 : }
1006 :
1007 0 : runs=pBiDi->runs;
1008 0 : runCount=pBiDi->runCount;
1009 0 : if(pBiDi->insertPoints.size>0) {
1010 : /* handle inserted LRM/RLM */
1011 0 : int32_t markFound=0, insertRemove;
1012 0 : int32_t visualStart=0, length;
1013 0 : runs=pBiDi->runs;
1014 : /* subtract number of marks until visual index */
1015 0 : for(i=0; ; i++, visualStart+=length) {
1016 0 : length=runs[i].visualLimit-visualStart;
1017 0 : insertRemove=runs[i].insertRemove;
1018 0 : if(insertRemove&(LRM_BEFORE|RLM_BEFORE)) {
1019 0 : if(visualIndex<=(visualStart+markFound)) {
1020 0 : return UBIDI_MAP_NOWHERE;
1021 : }
1022 0 : markFound++;
1023 : }
1024 : /* is adjusted visual index within this run? */
1025 0 : if(visualIndex<(runs[i].visualLimit+markFound)) {
1026 0 : visualIndex-=markFound;
1027 0 : break;
1028 : }
1029 0 : if(insertRemove&(LRM_AFTER|RLM_AFTER)) {
1030 0 : if(visualIndex==(visualStart+length+markFound)) {
1031 0 : return UBIDI_MAP_NOWHERE;
1032 : }
1033 0 : markFound++;
1034 : }
1035 : }
1036 : }
1037 0 : else if(pBiDi->controlCount>0) {
1038 : /* handle removed BiDi control characters */
1039 0 : int32_t controlFound=0, insertRemove, length;
1040 0 : int32_t logicalStart, logicalEnd, visualStart=0, j, k;
1041 : UChar uchar;
1042 : UBool evenRun;
1043 : /* add number of controls until visual index */
1044 0 : for(i=0; ; i++, visualStart+=length) {
1045 0 : length=runs[i].visualLimit-visualStart;
1046 0 : insertRemove=runs[i].insertRemove;
1047 : /* is adjusted visual index beyond current run? */
1048 0 : if(visualIndex>=(runs[i].visualLimit-controlFound+insertRemove)) {
1049 0 : controlFound-=insertRemove;
1050 0 : continue;
1051 : }
1052 : /* adjusted visual index is within current run */
1053 0 : if(insertRemove==0) {
1054 0 : visualIndex+=controlFound;
1055 0 : break;
1056 : }
1057 : /* count non-control chars until visualIndex */
1058 0 : logicalStart=runs[i].logicalStart;
1059 0 : evenRun=IS_EVEN_RUN(logicalStart);
1060 0 : REMOVE_ODD_BIT(logicalStart);
1061 0 : logicalEnd=logicalStart+length-1;
1062 0 : for(j=0; j<length; j++) {
1063 0 : k= evenRun ? logicalStart+j : logicalEnd-j;
1064 0 : uchar=pBiDi->text[k];
1065 0 : if(IS_BIDI_CONTROL_CHAR(uchar)) {
1066 0 : controlFound++;
1067 : }
1068 0 : if((visualIndex+controlFound)==(visualStart+j)) {
1069 0 : break;
1070 : }
1071 : }
1072 0 : visualIndex+=controlFound;
1073 0 : break;
1074 : }
1075 : }
1076 : /* handle all cases */
1077 0 : if(runCount<=10) {
1078 : /* linear search for the run */
1079 0 : for(i=0; visualIndex>=runs[i].visualLimit; ++i) {}
1080 : } else {
1081 : /* binary search for the run */
1082 0 : 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 0 : i=(begin+limit)/2;
1087 0 : if(visualIndex>=runs[i].visualLimit) {
1088 0 : begin=i+1;
1089 0 : } else if(i==0 || visualIndex>=runs[i-1].visualLimit) {
1090 : break;
1091 : } else {
1092 0 : limit=i;
1093 : }
1094 : }
1095 : }
1096 :
1097 0 : start=runs[i].logicalStart;
1098 0 : if(IS_EVEN_RUN(start)) {
1099 : /* LTR */
1100 : /* the offset in runs[i] is visualIndex-runs[i-1].visualLimit */
1101 0 : if(i>0) {
1102 0 : visualIndex-=runs[i-1].visualLimit;
1103 : }
1104 0 : return start+visualIndex;
1105 : } else {
1106 : /* RTL */
1107 0 : return GET_INDEX(start)+runs[i].visualLimit-visualIndex-1;
1108 : }
1109 : }
1110 :
1111 : U_CAPI void U_EXPORT2
1112 0 : ubidi_getLogicalMap(UBiDi *pBiDi, int32_t *indexMap, UErrorCode *pErrorCode) {
1113 0 : RETURN_VOID_IF_NULL_OR_FAILING_ERRCODE(pErrorCode);
1114 : /* ubidi_countRuns() checks for VALID_PARA_OR_LINE */
1115 0 : ubidi_countRuns(pBiDi, pErrorCode);
1116 0 : if(U_FAILURE(*pErrorCode)) {
1117 : /* no op */
1118 0 : } else if(indexMap==NULL) {
1119 0 : *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 0 : Run *runs=pBiDi->runs;
1125 0 : if (pBiDi->length<=0) {
1126 0 : return;
1127 : }
1128 0 : if (pBiDi->length>pBiDi->resultLength) {
1129 0 : uprv_memset(indexMap, 0xFF, pBiDi->length*sizeof(int32_t));
1130 : }
1131 :
1132 0 : visualStart=0;
1133 0 : for(j=0; j<pBiDi->runCount; ++j) {
1134 0 : logicalStart=GET_INDEX(runs[j].logicalStart);
1135 0 : visualLimit=runs[j].visualLimit;
1136 0 : if(IS_EVEN_RUN(runs[j].logicalStart)) {
1137 0 : do { /* LTR */
1138 0 : indexMap[logicalStart++]=visualStart++;
1139 0 : } while(visualStart<visualLimit);
1140 : } else {
1141 0 : logicalStart+=visualLimit-visualStart; /* logicalLimit */
1142 0 : do { /* RTL */
1143 0 : indexMap[--logicalStart]=visualStart++;
1144 0 : } while(visualStart<visualLimit);
1145 : }
1146 : /* visualStart==visualLimit; */
1147 : }
1148 :
1149 0 : if(pBiDi->insertPoints.size>0) {
1150 0 : int32_t markFound=0, runCount=pBiDi->runCount;
1151 : int32_t length, insertRemove;
1152 0 : visualStart=0;
1153 : /* add number of marks found until each index */
1154 0 : for(i=0; i<runCount; i++, visualStart+=length) {
1155 0 : length=runs[i].visualLimit-visualStart;
1156 0 : insertRemove=runs[i].insertRemove;
1157 0 : if(insertRemove&(LRM_BEFORE|RLM_BEFORE)) {
1158 0 : markFound++;
1159 : }
1160 0 : if(markFound>0) {
1161 0 : logicalStart=GET_INDEX(runs[i].logicalStart);
1162 0 : logicalLimit=logicalStart+length;
1163 0 : for(j=logicalStart; j<logicalLimit; j++) {
1164 0 : indexMap[j]+=markFound;
1165 : }
1166 : }
1167 0 : if(insertRemove&(LRM_AFTER|RLM_AFTER)) {
1168 0 : markFound++;
1169 : }
1170 : }
1171 : }
1172 0 : else if(pBiDi->controlCount>0) {
1173 0 : int32_t controlFound=0, runCount=pBiDi->runCount;
1174 : int32_t length, insertRemove;
1175 : UBool evenRun;
1176 : UChar uchar;
1177 0 : visualStart=0;
1178 : /* subtract number of controls found until each index */
1179 0 : for(i=0; i<runCount; i++, visualStart+=length) {
1180 0 : length=runs[i].visualLimit-visualStart;
1181 0 : insertRemove=runs[i].insertRemove;
1182 : /* no control found within previous runs nor within this run */
1183 0 : if((controlFound-insertRemove)==0) {
1184 0 : continue;
1185 : }
1186 0 : logicalStart=runs[i].logicalStart;
1187 0 : evenRun=IS_EVEN_RUN(logicalStart);
1188 0 : REMOVE_ODD_BIT(logicalStart);
1189 0 : logicalLimit=logicalStart+length;
1190 : /* if no control within this run */
1191 0 : if(insertRemove==0) {
1192 0 : for(j=logicalStart; j<logicalLimit; j++) {
1193 0 : indexMap[j]-=controlFound;
1194 : }
1195 0 : continue;
1196 : }
1197 0 : for(j=0; j<length; j++) {
1198 0 : k= evenRun ? logicalStart+j : logicalLimit-j-1;
1199 0 : uchar=pBiDi->text[k];
1200 0 : if(IS_BIDI_CONTROL_CHAR(uchar)) {
1201 0 : controlFound++;
1202 0 : indexMap[k]=UBIDI_MAP_NOWHERE;
1203 0 : continue;
1204 : }
1205 0 : indexMap[k]-=controlFound;
1206 : }
1207 : }
1208 : }
1209 : }
1210 : }
1211 :
1212 : U_CAPI void U_EXPORT2
1213 0 : ubidi_getVisualMap(UBiDi *pBiDi, int32_t *indexMap, UErrorCode *pErrorCode) {
1214 0 : RETURN_VOID_IF_NULL_OR_FAILING_ERRCODE(pErrorCode);
1215 0 : if(indexMap==NULL) {
1216 0 : *pErrorCode=U_ILLEGAL_ARGUMENT_ERROR;
1217 0 : return;
1218 : }
1219 : /* ubidi_countRuns() checks for VALID_PARA_OR_LINE */
1220 0 : ubidi_countRuns(pBiDi, pErrorCode);
1221 0 : if(U_SUCCESS(*pErrorCode)) {
1222 : /* fill a visual-to-logical index map using the runs[] */
1223 0 : Run *runs=pBiDi->runs, *runsLimit=runs+pBiDi->runCount;
1224 0 : int32_t logicalStart, visualStart, visualLimit, *pi=indexMap;
1225 :
1226 0 : if (pBiDi->resultLength<=0) {
1227 0 : return;
1228 : }
1229 0 : visualStart=0;
1230 0 : for(; runs<runsLimit; ++runs) {
1231 0 : logicalStart=runs->logicalStart;
1232 0 : visualLimit=runs->visualLimit;
1233 0 : if(IS_EVEN_RUN(logicalStart)) {
1234 0 : do { /* LTR */
1235 0 : *pi++ = logicalStart++;
1236 : } while(++visualStart<visualLimit);
1237 : } else {
1238 0 : REMOVE_ODD_BIT(logicalStart);
1239 0 : logicalStart+=visualLimit-visualStart; /* logicalLimit */
1240 0 : do { /* RTL */
1241 0 : *pi++ = --logicalStart;
1242 : } while(++visualStart<visualLimit);
1243 : }
1244 : /* visualStart==visualLimit; */
1245 : }
1246 :
1247 0 : if(pBiDi->insertPoints.size>0) {
1248 0 : int32_t markFound=0, runCount=pBiDi->runCount;
1249 : int32_t insertRemove, i, j, k;
1250 0 : runs=pBiDi->runs;
1251 : /* count all inserted marks */
1252 0 : for(i=0; i<runCount; i++) {
1253 0 : insertRemove=runs[i].insertRemove;
1254 0 : if(insertRemove&(LRM_BEFORE|RLM_BEFORE)) {
1255 0 : markFound++;
1256 : }
1257 0 : if(insertRemove&(LRM_AFTER|RLM_AFTER)) {
1258 0 : markFound++;
1259 : }
1260 : }
1261 : /* move back indexes by number of preceding marks */
1262 0 : k=pBiDi->resultLength;
1263 0 : for(i=runCount-1; i>=0 && markFound>0; i--) {
1264 0 : insertRemove=runs[i].insertRemove;
1265 0 : if(insertRemove&(LRM_AFTER|RLM_AFTER)) {
1266 0 : indexMap[--k]= UBIDI_MAP_NOWHERE;
1267 0 : markFound--;
1268 : }
1269 0 : visualStart= i>0 ? runs[i-1].visualLimit : 0;
1270 0 : for(j=runs[i].visualLimit-1; j>=visualStart && markFound>0; j--) {
1271 0 : indexMap[--k]=indexMap[j];
1272 : }
1273 0 : if(insertRemove&(LRM_BEFORE|RLM_BEFORE)) {
1274 0 : indexMap[--k]= UBIDI_MAP_NOWHERE;
1275 0 : markFound--;
1276 : }
1277 : }
1278 : }
1279 0 : else if(pBiDi->controlCount>0) {
1280 0 : int32_t runCount=pBiDi->runCount, logicalEnd;
1281 : int32_t insertRemove, length, i, j, k, m;
1282 : UChar uchar;
1283 : UBool evenRun;
1284 0 : runs=pBiDi->runs;
1285 0 : visualStart=0;
1286 : /* move forward indexes by number of preceding controls */
1287 0 : k=0;
1288 0 : for(i=0; i<runCount; i++, visualStart+=length) {
1289 0 : length=runs[i].visualLimit-visualStart;
1290 0 : insertRemove=runs[i].insertRemove;
1291 : /* if no control found yet, nothing to do in this run */
1292 0 : if((insertRemove==0)&&(k==visualStart)) {
1293 0 : k+=length;
1294 0 : continue;
1295 : }
1296 : /* if no control in this run */
1297 0 : if(insertRemove==0) {
1298 0 : visualLimit=runs[i].visualLimit;
1299 0 : for(j=visualStart; j<visualLimit; j++) {
1300 0 : indexMap[k++]=indexMap[j];
1301 : }
1302 0 : continue;
1303 : }
1304 0 : logicalStart=runs[i].logicalStart;
1305 0 : evenRun=IS_EVEN_RUN(logicalStart);
1306 0 : REMOVE_ODD_BIT(logicalStart);
1307 0 : logicalEnd=logicalStart+length-1;
1308 0 : for(j=0; j<length; j++) {
1309 0 : m= evenRun ? logicalStart+j : logicalEnd-j;
1310 0 : uchar=pBiDi->text[m];
1311 0 : if(!IS_BIDI_CONTROL_CHAR(uchar)) {
1312 0 : indexMap[k++]=m;
1313 : }
1314 : }
1315 : }
1316 : }
1317 : }
1318 : }
1319 :
1320 : U_CAPI void U_EXPORT2
1321 0 : ubidi_invertMap(const int32_t *srcMap, int32_t *destMap, int32_t length) {
1322 0 : if(srcMap!=NULL && destMap!=NULL && length>0) {
1323 : const int32_t *pi;
1324 0 : int32_t destLength=-1, count=0;
1325 : /* find highest value and count positive indexes in srcMap */
1326 0 : pi=srcMap+length;
1327 0 : while(pi>srcMap) {
1328 0 : if(*--pi>destLength) {
1329 0 : destLength=*pi;
1330 : }
1331 0 : if(*pi>=0) {
1332 0 : count++;
1333 : }
1334 : }
1335 0 : destLength++; /* add 1 for origin 0 */
1336 0 : if(count<destLength) {
1337 : /* we must fill unmatched destMap entries with -1 */
1338 0 : uprv_memset(destMap, 0xFF, destLength*sizeof(int32_t));
1339 : }
1340 0 : pi=srcMap+length;
1341 0 : while(length>0) {
1342 0 : if(*--pi>=0) {
1343 0 : destMap[*pi]=--length;
1344 : } else {
1345 0 : --length;
1346 : }
1347 : }
1348 : }
1349 0 : }
|
