w32tex
About: TeX Live provides a comprehensive TeX system including all the major TeX-related programs, macro packages, and fonts that are free software. Windows sources.
  Fossies Dox: w32tex-src.tar.xz  ("unofficial" and yet experimental doxygen-generated source code documentation)  

ubidiln.cpp
Go to the documentation of this file.
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
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
126 ubidi_setLine(const UBiDi *pParaBiDi,
128  UBiDi *pLineBiDi,
129  UErrorCode *pErrorCode) {
130  int32_t length;
131 
132  /* check the argument values */
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;
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 
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 
263 ubidi_getLevels(UBiDi *pBiDi, UErrorCode *pErrorCode) {
265 
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
305 ubidi_getLogicalRun(const UBiDi *pBiDi, int32_t logicalPosition,
306  int32_t *pLogicalLimit, UBiDiLevel *pLevel) {
308  int32_t runCount, visualStart, logicalLimit, logicalFirst, i;
309  Run iRun;
310 
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) {
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 
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 
364  int32_t *pLogicalStart, int32_t *pLength)
365 {
366  int32_t start;
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  }
388 }
389 
390 /* in trivial cases there is only one trivial run; called by ubidi_getRuns() */
391 static void
393  /* simple, single-run case */
394  pBiDi->runs=pBiDi->simpleRuns;
395  pBiDi->runCount=1;
396 
397  /* fill and reorder the single run */
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
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 
520 static int32_t getRunFromLogicalIndex(UBiDi *pBiDi, int32_t logicalIndex) {
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 */
534 }
535 
536 /*
537  * Compute the runs array from the levels array.
538  * After ubidi_getRuns() returns TRUE, runCount is guaranteed to be >0
539  * and the runs are reordered.
540  * Odd-level runs have visualStart on their visual right edge and
541  * they progress visually to the left.
542  * If option UBIDI_OPTION_INSERT_MARKS is set, insertRemove will contain the
543  * sum of appropriate LRM/RLM_BEFORE/AFTER flags.
544  * If option UBIDI_OPTION_REMOVE_CONTROLS is set, insertRemove will contain the
545  * negative number of BiDi control characters within this run.
546  */
549  /*
550  * This method returns immediately if the runs are already set. This
551  * includes the case of length==0 (handled in setPara)..
552  */
553  if (pBiDi->runCount>=0) {
554  return TRUE;
555  }
556 
557  if(pBiDi->direction!=UBIDI_MIXED) {
558  /* simple, single-run case - this covers length==0 */
559  /* pBiDi->paraLevel is ok even for contextual multiple paragraphs */
560  getSingleRun(pBiDi, pBiDi->paraLevel);
561  } else /* UBIDI_MIXED, length>0 */ {
562  /* mixed directionality */
563  int32_t length=pBiDi->length, limit;
564  UBiDiLevel *levels=pBiDi->levels;
565  int32_t i, runCount;
566  UBiDiLevel level=UBIDI_DEFAULT_LTR; /* initialize with no valid level */
567  /*
568  * If there are WS characters at the end of the line
569  * and the run preceding them has a level different from
570  * paraLevel, then they will form their own run at paraLevel (L1).
571  * Count them separately.
572  * We need some special treatment for this in order to not
573  * modify the levels array which a line UBiDi object shares
574  * with its paragraph parent and its other line siblings.
575  * In other words, for the trailing WS, it may be
576  * levels[]!=paraLevel but we have to treat it like it were so.
577  */
578  limit=pBiDi->trailingWSStart;
579  /* count the runs, there is at least one non-WS run, and limit>0 */
580  runCount=0;
581  for(i=0; i<limit; ++i) {
582  /* increment runCount at the start of each run */
583  if(levels[i]!=level) {
584  ++runCount;
585  level=levels[i];
586  }
587  }
588 
589  /*
590  * We don't need to see if the last run can be merged with a trailing
591  * WS run because setTrailingWSStart() would have done that.
592  */
593  if(runCount==1 && limit==length) {
594  /* There is only one non-WS run and no trailing WS-run. */
595  getSingleRun(pBiDi, levels[0]);
596  } else /* runCount>1 || limit<length */ {
597  /* allocate and set the runs */
598  Run *runs;
599  int32_t runIndex, start;
600  UBiDiLevel minLevel=UBIDI_MAX_EXPLICIT_LEVEL+1, maxLevel=0;
601 
602  /* now, count a (non-mergeable) WS run */
603  if(limit<length) {
604  ++runCount;
605  }
606 
607  /* runCount>1 */
608  if(getRunsMemory(pBiDi, runCount)) {
609  runs=pBiDi->runsMemory;
610  } else {
611  return FALSE;
612  }
613 
614  /* set the runs */
615  /* FOOD FOR THOUGHT: this could be optimized, e.g.:
616  * 464->444, 484->444, 575->555, 595->555
617  * However, that would take longer. Check also how it would
618  * interact with BiDi control removal and inserting Marks.
619  */
620  runIndex=0;
621 
622  /* search for the run limits and initialize visualLimit values with the run lengths */
623  i=0;
624  do {
625  /* prepare this run */
626  start=i;
627  level=levels[i];
628  if(level<minLevel) {
629  minLevel=level;
630  }
631  if(level>maxLevel) {
632  maxLevel=level;
633  }
634 
635  /* look for the run limit */
636  while(++i<limit && levels[i]==level) {}
637 
638  /* i is another run limit */
639  runs[runIndex].logicalStart=start;
640  runs[runIndex].visualLimit=i-start;
641  runs[runIndex].insertRemove=0;
642  ++runIndex;
643  } while(i<limit);
644 
645  if(limit<length) {
646  /* there is a separate WS run */
647  runs[runIndex].logicalStart=limit;
648  runs[runIndex].visualLimit=length-limit;
649  /* For the trailing WS run, pBiDi->paraLevel is ok even
650  if contextual multiple paragraphs. */
651  if(pBiDi->paraLevel<minLevel) {
652  minLevel=pBiDi->paraLevel;
653  }
654  }
655 
656  /* set the object fields */
657  pBiDi->runs=runs;
658  pBiDi->runCount=runCount;
659 
660  reorderLine(pBiDi, minLevel, maxLevel);
661 
662  /* now add the direction flags and adjust the visualLimit's to be just that */
663  /* this loop will also handle the trailing WS run */
664  limit=0;
665  for(i=0; i<runCount; ++i) {
666  ADD_ODD_BIT_FROM_LEVEL(runs[i].logicalStart, levels[runs[i].logicalStart]);
667  limit+=runs[i].visualLimit;
668  runs[i].visualLimit=limit;
669  }
670 
671  /* Set the "odd" bit for the trailing WS run. */
672  /* For a RTL paragraph, it will be the *first* run in visual order. */
673  /* For the trailing WS run, pBiDi->paraLevel is ok even if
674  contextual multiple paragraphs. */
675  if(runIndex<runCount) {
676  int32_t trailingRun = ((pBiDi->paraLevel & 1) != 0)? 0 : runIndex;
677 
678  ADD_ODD_BIT_FROM_LEVEL(runs[trailingRun].logicalStart, pBiDi->paraLevel);
679  }
680  }
681  }
682 
683  /* handle insert LRM/RLM BEFORE/AFTER run */
684  if(pBiDi->insertPoints.size>0) {
685  Point *point, *start=pBiDi->insertPoints.points,
686  *limit=start+pBiDi->insertPoints.size;
687  int32_t runIndex;
688  for(point=start; point<limit; point++) {
689  runIndex=getRunFromLogicalIndex(pBiDi, point->pos);
690  pBiDi->runs[runIndex].insertRemove|=point->flag;
691  }
692  }
693 
694  /* handle remove BiDi control characters */
695  if(pBiDi->controlCount>0) {
696  int32_t runIndex;
697  const UChar *start=pBiDi->text, *limit=start+pBiDi->length, *pu;
698  for(pu=start; pu<limit; pu++) {
699  if(IS_BIDI_CONTROL_CHAR(*pu)) {
700  runIndex=getRunFromLogicalIndex(pBiDi, (int32_t)(pu-start));
701  pBiDi->runs[runIndex].insertRemove--;
702  }
703  }
704  }
705 
706  return TRUE;
707 }
708 
709 static UBool
711  int32_t *indexMap,
712  UBiDiLevel *pMinLevel, UBiDiLevel *pMaxLevel) {
713  int32_t start;
714  UBiDiLevel level, minLevel, maxLevel;
715 
716  if(levels==NULL || length<=0) {
717  return FALSE;
718  }
719 
720  /* determine minLevel and maxLevel */
721  minLevel=UBIDI_MAX_EXPLICIT_LEVEL+1;
722  maxLevel=0;
723  for(start=length; start>0;) {
724  level=levels[--start];
726  return FALSE;
727  }
728  if(level<minLevel) {
729  minLevel=level;
730  }
731  if(level>maxLevel) {
732  maxLevel=level;
733  }
734  }
735  *pMinLevel=minLevel;
736  *pMaxLevel=maxLevel;
737 
738  /* initialize the index map */
739  for(start=length; start>0;) {
740  --start;
741  indexMap[start]=start;
742  }
743 
744  return TRUE;
745 }
746 
747 /* reorder a line based on a levels array (L2) ------------------------------ */
748 
749 U_CAPI void U_EXPORT2
751  int32_t start, limit, sumOfSosEos;
752  UBiDiLevel minLevel = 0, maxLevel = 0;
753 
754  if(indexMap==NULL || !prepareReorder(levels, length, indexMap, &minLevel, &maxLevel)) {
755  return;
756  }
757 
758  /* nothing to do? */
759  if(minLevel==maxLevel && (minLevel&1)==0) {
760  return;
761  }
762 
763  /* reorder only down to the lowest odd level */
764  minLevel|=1;
765 
766  /* loop maxLevel..minLevel */
767  do {
768  start=0;
769 
770  /* loop for all sequences of levels to reorder at the current maxLevel */
771  for(;;) {
772  /* look for a sequence of levels that are all at >=maxLevel */
773  /* look for the first index of such a sequence */
774  while(start<length && levels[start]<maxLevel) {
775  ++start;
776  }
777  if(start>=length) {
778  break; /* no more such sequences */
779  }
780 
781  /* look for the limit of such a sequence (the index behind it) */
782  for(limit=start; ++limit<length && levels[limit]>=maxLevel;) {}
783 
784  /*
785  * sos=start of sequence, eos=end of sequence
786  *
787  * The closed (inclusive) interval from sos to eos includes all the logical
788  * and visual indexes within this sequence. They are logically and
789  * visually contiguous and in the same range.
790  *
791  * For each run, the new visual index=sos+eos-old visual index;
792  * we pre-add sos+eos into sumOfSosEos ->
793  * new visual index=sumOfSosEos-old visual index;
794  */
795  sumOfSosEos=start+limit-1;
796 
797  /* reorder each index in the sequence */
798  do {
799  indexMap[start]=sumOfSosEos-indexMap[start];
800  } while(++start<limit);
801 
802  /* start==limit */
803  if(limit==length) {
804  break; /* no more such sequences */
805  } else {
806  start=limit+1;
807  }
808  }
809  } while(--maxLevel>=minLevel);
810 }
811 
812 U_CAPI void U_EXPORT2
815  UBiDiLevel minLevel = 0, maxLevel = 0;
816 
817  if(indexMap==NULL || !prepareReorder(levels, length, indexMap, &minLevel, &maxLevel)) {
818  return;
819  }
820 
821  /* nothing to do? */
822  if(minLevel==maxLevel && (minLevel&1)==0) {
823  return;
824  }
825 
826  /* reorder only down to the lowest odd level */
827  minLevel|=1;
828 
829  /* loop maxLevel..minLevel */
830  do {
831  start=0;
832 
833  /* loop for all sequences of levels to reorder at the current maxLevel */
834  for(;;) {
835  /* look for a sequence of levels that are all at >=maxLevel */
836  /* look for the first index of such a sequence */
837  while(start<length && levels[start]<maxLevel) {
838  ++start;
839  }
840  if(start>=length) {
841  break; /* no more such runs */
842  }
843 
844  /* look for the limit of such a sequence (the index behind it) */
845  for(limit=start; ++limit<length && levels[limit]>=maxLevel;) {}
846 
847  /*
848  * Swap the entire interval of indexes from start to limit-1.
849  * We don't need to swap the levels for the purpose of this
850  * algorithm: the sequence of levels that we look at does not
851  * move anyway.
852  */
853  end=limit-1;
854  while(start<end) {
855  temp=indexMap[start];
856  indexMap[start]=indexMap[end];
857  indexMap[end]=temp;
858 
859  ++start;
860  --end;
861  }
862 
863  if(limit==length) {
864  break; /* no more such sequences */
865  } else {
866  start=limit+1;
867  }
868  }
869  } while(--maxLevel>=minLevel);
870 }
871 
872 /* API functions for logical<->visual mapping ------------------------------- */
873 
875 ubidi_getVisualIndex(UBiDi *pBiDi, int32_t logicalIndex, UErrorCode *pErrorCode) {
876  int32_t visualIndex=UBIDI_MAP_NOWHERE;
877  RETURN_IF_NULL_OR_FAILING_ERRCODE(pErrorCode, -1);
878  RETURN_IF_NOT_VALID_PARA_OR_LINE(pBiDi, *pErrorCode, -1);
879  RETURN_IF_BAD_RANGE(logicalIndex, 0, pBiDi->length, *pErrorCode, -1);
880 
881  /* we can do the trivial cases without the runs array */
882  switch(pBiDi->direction) {
883  case UBIDI_LTR:
884  visualIndex=logicalIndex;
885  break;
886  case UBIDI_RTL:
887  visualIndex=pBiDi->length-logicalIndex-1;
888  break;
889  default:
890  if(!ubidi_getRuns(pBiDi, pErrorCode)) {
891  *pErrorCode=U_MEMORY_ALLOCATION_ERROR;
892  return -1;
893  } else {
894  Run *runs=pBiDi->runs;
895  int32_t i, visualStart=0, offset, length;
896 
897  /* linear search for the run, search on the visual runs */
898  for(i=0; i<pBiDi->runCount; ++i) {
899  length=runs[i].visualLimit-visualStart;
900  offset=logicalIndex-GET_INDEX(runs[i].logicalStart);
901  if(offset>=0 && offset<length) {
902  if(IS_EVEN_RUN(runs[i].logicalStart)) {
903  /* LTR */
904  visualIndex=visualStart+offset;
905  } else {
906  /* RTL */
907  visualIndex=visualStart+length-offset-1;
908  }
909  break; /* exit for loop */
910  }
911  visualStart+=length;
912  }
913  if(i>=pBiDi->runCount) {
914  return UBIDI_MAP_NOWHERE;
915  }
916  }
917  }
918 
919  if(pBiDi->insertPoints.size>0) {
920  /* add the number of added marks until the calculated visual index */
921  Run *runs=pBiDi->runs;
922  int32_t i, length, insertRemove;
923  int32_t visualStart=0, markFound=0;
924  for(i=0; ; i++, visualStart+=length) {
925  length=runs[i].visualLimit-visualStart;
926  insertRemove=runs[i].insertRemove;
927  if(insertRemove & (LRM_BEFORE|RLM_BEFORE)) {
928  markFound++;
929  }
930  /* is it the run containing the visual index? */
931  if(visualIndex<runs[i].visualLimit) {
932  return visualIndex+markFound;
933  }
934  if(insertRemove & (LRM_AFTER|RLM_AFTER)) {
935  markFound++;
936  }
937  }
938  }
939  else if(pBiDi->controlCount>0) {
940  /* subtract the number of controls until the calculated visual index */
941  Run *runs=pBiDi->runs;
942  int32_t i, j, start, limit, length, insertRemove;
943  int32_t visualStart=0, controlFound=0;
944  UChar uchar=pBiDi->text[logicalIndex];
945  /* is the logical index pointing to a control ? */
947  return UBIDI_MAP_NOWHERE;
948  }
949  /* loop on runs */
950  for(i=0; ; i++, visualStart+=length) {
951  length=runs[i].visualLimit-visualStart;
952  insertRemove=runs[i].insertRemove;
953  /* calculated visual index is beyond this run? */
954  if(visualIndex>=runs[i].visualLimit) {
955  controlFound-=insertRemove;
956  continue;
957  }
958  /* calculated visual index must be within current run */
959  if(insertRemove==0) {
960  return visualIndex-controlFound;
961  }
962  if(IS_EVEN_RUN(runs[i].logicalStart)) {
963  /* LTR: check from run start to logical index */
964  start=runs[i].logicalStart;
965  limit=logicalIndex;
966  } else {
967  /* RTL: check from logical index to run end */
968  start=logicalIndex+1;
969  limit=GET_INDEX(runs[i].logicalStart)+length;
970  }
971  for(j=start; j<limit; j++) {
972  uchar=pBiDi->text[j];
974  controlFound++;
975  }
976  }
977  return visualIndex-controlFound;
978  }
979  }
980 
981  return visualIndex;
982 }
983 
985 ubidi_getLogicalIndex(UBiDi *pBiDi, int32_t visualIndex, UErrorCode *pErrorCode) {
986  Run *runs;
987  int32_t i, runCount, start;
988  RETURN_IF_NULL_OR_FAILING_ERRCODE(pErrorCode, -1);
989  RETURN_IF_NOT_VALID_PARA_OR_LINE(pBiDi, *pErrorCode, -1);
990  RETURN_IF_BAD_RANGE(visualIndex, 0, pBiDi->resultLength, *pErrorCode, -1);
991  /* we can do the trivial cases without the runs array */
992  if(pBiDi->insertPoints.size==0 && pBiDi->controlCount==0) {
993  if(pBiDi->direction==UBIDI_LTR) {
994  return visualIndex;
995  }
996  else if(pBiDi->direction==UBIDI_RTL) {
997  return pBiDi->length-visualIndex-1;
998  }
999  }
1000  if(!ubidi_getRuns(pBiDi, pErrorCode)) {
1001  *pErrorCode=U_MEMORY_ALLOCATION_ERROR;
1002  return -1;
1003  }
1004 
1005  runs=pBiDi->runs;
1006  runCount=pBiDi->runCount;
1007  if(pBiDi->insertPoints.size>0) {
1008  /* handle inserted LRM/RLM */
1009  int32_t markFound=0, insertRemove;
1010  int32_t visualStart=0, length;
1011  runs=pBiDi->runs;
1012  /* subtract number of marks until visual index */
1013  for(i=0; ; i++, visualStart+=length) {
1014  length=runs[i].visualLimit-visualStart;
1015  insertRemove=runs[i].insertRemove;
1016  if(insertRemove&(LRM_BEFORE|RLM_BEFORE)) {
1017  if(visualIndex<=(visualStart+markFound)) {
1018  return UBIDI_MAP_NOWHERE;
1019  }
1020  markFound++;
1021  }
1022  /* is adjusted visual index within this run? */
1023  if(visualIndex<(runs[i].visualLimit+markFound)) {
1024  visualIndex-=markFound;
1025  break;
1026  }
1027  if(insertRemove&(LRM_AFTER|RLM_AFTER)) {
1028  if(visualIndex==(visualStart+length+markFound)) {
1029  return UBIDI_MAP_NOWHERE;
1030  }
1031  markFound++;
1032  }
1033  }
1034  }
1035  else if(pBiDi->controlCount>0) {
1036  /* handle removed BiDi control characters */
1037  int32_t controlFound=0, insertRemove, length;
1038  int32_t logicalStart, logicalEnd, visualStart=0, j, k;
1039  UChar uchar;
1040  UBool evenRun;
1041  /* add number of controls until visual index */
1042  for(i=0; ; i++, visualStart+=length) {
1043  length=runs[i].visualLimit-visualStart;
1044  insertRemove=runs[i].insertRemove;
1045  /* is adjusted visual index beyond current run? */
1046  if(visualIndex>=(runs[i].visualLimit-controlFound+insertRemove)) {
1047  controlFound-=insertRemove;
1048  continue;
1049  }
1050  /* adjusted visual index is within current run */
1051  if(insertRemove==0) {
1052  visualIndex+=controlFound;
1053  break;
1054  }
1055  /* count non-control chars until visualIndex */
1056  logicalStart=runs[i].logicalStart;
1057  evenRun=IS_EVEN_RUN(logicalStart);
1058  REMOVE_ODD_BIT(logicalStart);
1059  logicalEnd=logicalStart+length-1;
1060  for(j=0; j<length; j++) {
1061  k= evenRun ? logicalStart+j : logicalEnd-j;
1062  uchar=pBiDi->text[k];
1064  controlFound++;
1065  }
1066  if((visualIndex+controlFound)==(visualStart+j)) {
1067  break;
1068  }
1069  }
1070  visualIndex+=controlFound;
1071  break;
1072  }
1073  }
1074  /* handle all cases */
1075  if(runCount<=10) {
1076  /* linear search for the run */
1077  for(i=0; visualIndex>=runs[i].visualLimit; ++i) {}
1078  } else {
1079  /* binary search for the run */
1080  int32_t begin=0, limit=runCount;
1081 
1082  /* the middle if() is guaranteed to find the run, we don't need a loop limit */
1083  for(;;) {
1084  i=(begin+limit)/2;
1085  if(visualIndex>=runs[i].visualLimit) {
1086  begin=i+1;
1087  } else if(i==0 || visualIndex>=runs[i-1].visualLimit) {
1088  break;
1089  } else {
1090  limit=i;
1091  }
1092  }
1093  }
1094 
1095  start=runs[i].logicalStart;
1096  if(IS_EVEN_RUN(start)) {
1097  /* LTR */
1098  /* the offset in runs[i] is visualIndex-runs[i-1].visualLimit */
1099  if(i>0) {
1100  visualIndex-=runs[i-1].visualLimit;
1101  }
1102  return start+visualIndex;
1103  } else {
1104  /* RTL */
1105  return GET_INDEX(start)+runs[i].visualLimit-visualIndex-1;
1106  }
1107 }
1108 
1109 U_CAPI void U_EXPORT2
1110 ubidi_getLogicalMap(UBiDi *pBiDi, int32_t *indexMap, UErrorCode *pErrorCode) {
1112  /* ubidi_countRuns() checks for VALID_PARA_OR_LINE */
1113  ubidi_countRuns(pBiDi, pErrorCode);
1114  if(U_FAILURE(*pErrorCode)) {
1115  /* no op */
1116  } else if(indexMap==NULL) {
1117  *pErrorCode=U_ILLEGAL_ARGUMENT_ERROR;
1118  } else {
1119  /* fill a logical-to-visual index map using the runs[] */
1120  int32_t visualStart, visualLimit, i, j, k;
1121  int32_t logicalStart, logicalLimit;
1122  Run *runs=pBiDi->runs;
1123  if (pBiDi->length<=0) {
1124  return;
1125  }
1126  if (pBiDi->length>pBiDi->resultLength) {
1127  uprv_memset(indexMap, 0xFF, pBiDi->length*sizeof(int32_t));
1128  }
1129 
1130  visualStart=0;
1131  for(j=0; j<pBiDi->runCount; ++j) {
1132  logicalStart=GET_INDEX(runs[j].logicalStart);
1133  visualLimit=runs[j].visualLimit;
1134  if(IS_EVEN_RUN(runs[j].logicalStart)) {
1135  do { /* LTR */
1136  indexMap[logicalStart++]=visualStart++;
1137  } while(visualStart<visualLimit);
1138  } else {
1139  logicalStart+=visualLimit-visualStart; /* logicalLimit */
1140  do { /* RTL */
1141  indexMap[--logicalStart]=visualStart++;
1142  } while(visualStart<visualLimit);
1143  }
1144  /* visualStart==visualLimit; */
1145  }
1146 
1147  if(pBiDi->insertPoints.size>0) {
1148  int32_t markFound=0, runCount=pBiDi->runCount;
1149  int32_t length, insertRemove;
1150  visualStart=0;
1151  /* add number of marks found until each index */
1152  for(i=0; i<runCount; i++, visualStart+=length) {
1153  length=runs[i].visualLimit-visualStart;
1154  insertRemove=runs[i].insertRemove;
1155  if(insertRemove&(LRM_BEFORE|RLM_BEFORE)) {
1156  markFound++;
1157  }
1158  if(markFound>0) {
1159  logicalStart=GET_INDEX(runs[i].logicalStart);
1160  logicalLimit=logicalStart+length;
1161  for(j=logicalStart; j<logicalLimit; j++) {
1162  indexMap[j]+=markFound;
1163  }
1164  }
1165  if(insertRemove&(LRM_AFTER|RLM_AFTER)) {
1166  markFound++;
1167  }
1168  }
1169  }
1170  else if(pBiDi->controlCount>0) {
1171  int32_t controlFound=0, runCount=pBiDi->runCount;
1172  int32_t length, insertRemove;
1173  UBool evenRun;
1174  UChar uchar;
1175  visualStart=0;
1176  /* subtract number of controls found until each index */
1177  for(i=0; i<runCount; i++, visualStart+=length) {
1178  length=runs[i].visualLimit-visualStart;
1179  insertRemove=runs[i].insertRemove;
1180  /* no control found within previous runs nor within this run */
1181  if((controlFound-insertRemove)==0) {
1182  continue;
1183  }
1184  logicalStart=runs[i].logicalStart;
1185  evenRun=IS_EVEN_RUN(logicalStart);
1186  REMOVE_ODD_BIT(logicalStart);
1187  logicalLimit=logicalStart+length;
1188  /* if no control within this run */
1189  if(insertRemove==0) {
1190  for(j=logicalStart; j<logicalLimit; j++) {
1191  indexMap[j]-=controlFound;
1192  }
1193  continue;
1194  }
1195  for(j=0; j<length; j++) {
1196  k= evenRun ? logicalStart+j : logicalLimit-j-1;
1197  uchar=pBiDi->text[k];
1199  controlFound++;
1200  indexMap[k]=UBIDI_MAP_NOWHERE;
1201  continue;
1202  }
1203  indexMap[k]-=controlFound;
1204  }
1205  }
1206  }
1207  }
1208 }
1209 
1210 U_CAPI void U_EXPORT2
1211 ubidi_getVisualMap(UBiDi *pBiDi, int32_t *indexMap, UErrorCode *pErrorCode) {
1213  if(indexMap==NULL) {
1214  *pErrorCode=U_ILLEGAL_ARGUMENT_ERROR;
1215  return;
1216  }
1217  /* ubidi_countRuns() checks for VALID_PARA_OR_LINE */
1218  ubidi_countRuns(pBiDi, pErrorCode);
1219  if(U_SUCCESS(*pErrorCode)) {
1220  /* fill a visual-to-logical index map using the runs[] */
1221  Run *runs=pBiDi->runs, *runsLimit=runs+pBiDi->runCount;
1222  int32_t logicalStart, visualStart, visualLimit, *pi=indexMap;
1223 
1224  if (pBiDi->resultLength<=0) {
1225  return;
1226  }
1227  visualStart=0;
1228  for(; runs<runsLimit; ++runs) {
1229  logicalStart=runs->logicalStart;
1230  visualLimit=runs->visualLimit;
1231  if(IS_EVEN_RUN(logicalStart)) {
1232  do { /* LTR */
1233  *pi++ = logicalStart++;
1234  } while(++visualStart<visualLimit);
1235  } else {
1236  REMOVE_ODD_BIT(logicalStart);
1237  logicalStart+=visualLimit-visualStart; /* logicalLimit */
1238  do { /* RTL */
1239  *pi++ = --logicalStart;
1240  } while(++visualStart<visualLimit);
1241  }
1242  /* visualStart==visualLimit; */
1243  }
1244 
1245  if(pBiDi->insertPoints.size>0) {
1246  int32_t markFound=0, runCount=pBiDi->runCount;
1247  int32_t insertRemove, i, j, k;
1248  runs=pBiDi->runs;
1249  /* count all inserted marks */
1250  for(i=0; i<runCount; i++) {
1251  insertRemove=runs[i].insertRemove;
1252  if(insertRemove&(LRM_BEFORE|RLM_BEFORE)) {
1253  markFound++;
1254  }
1255  if(insertRemove&(LRM_AFTER|RLM_AFTER)) {
1256  markFound++;
1257  }
1258  }
1259  /* move back indexes by number of preceding marks */
1260  k=pBiDi->resultLength;
1261  for(i=runCount-1; i>=0 && markFound>0; i--) {
1262  insertRemove=runs[i].insertRemove;
1263  if(insertRemove&(LRM_AFTER|RLM_AFTER)) {
1264  indexMap[--k]= UBIDI_MAP_NOWHERE;
1265  markFound--;
1266  }
1267  visualStart= i>0 ? runs[i-1].visualLimit : 0;
1268  for(j=runs[i].visualLimit-1; j>=visualStart && markFound>0; j--) {
1269  indexMap[--k]=indexMap[j];
1270  }
1271  if(insertRemove&(LRM_BEFORE|RLM_BEFORE)) {
1272  indexMap[--k]= UBIDI_MAP_NOWHERE;
1273  markFound--;
1274  }
1275  }
1276  }
1277  else if(pBiDi->controlCount>0) {
1278  int32_t runCount=pBiDi->runCount, logicalEnd;
1279  int32_t insertRemove, length, i, j, k, m;
1280  UChar uchar;
1281  UBool evenRun;
1282  runs=pBiDi->runs;
1283  visualStart=0;
1284  /* move forward indexes by number of preceding controls */
1285  k=0;
1286  for(i=0; i<runCount; i++, visualStart+=length) {
1287  length=runs[i].visualLimit-visualStart;
1288  insertRemove=runs[i].insertRemove;
1289  /* if no control found yet, nothing to do in this run */
1290  if((insertRemove==0)&&(k==visualStart)) {
1291  k+=length;
1292  continue;
1293  }
1294  /* if no control in this run */
1295  if(insertRemove==0) {
1296  visualLimit=runs[i].visualLimit;
1297  for(j=visualStart; j<visualLimit; j++) {
1298  indexMap[k++]=indexMap[j];
1299  }
1300  continue;
1301  }
1302  logicalStart=runs[i].logicalStart;
1303  evenRun=IS_EVEN_RUN(logicalStart);
1304  REMOVE_ODD_BIT(logicalStart);
1305  logicalEnd=logicalStart+length-1;
1306  for(j=0; j<length; j++) {
1307  m= evenRun ? logicalStart+j : logicalEnd-j;
1308  uchar=pBiDi->text[m];
1309  if(!IS_BIDI_CONTROL_CHAR(uchar)) {
1310  indexMap[k++]=m;
1311  }
1312  }
1313  }
1314  }
1315  }
1316 }
1317 
1318 U_CAPI void U_EXPORT2
1319 ubidi_invertMap(const int32_t *srcMap, int32_t *destMap, int32_t length) {
1320  if(srcMap!=NULL && destMap!=NULL && length>0) {
1321  const int32_t *pi;
1322  int32_t destLength=-1, count=0;
1323  /* find highest value and count positive indexes in srcMap */
1324  pi=srcMap+length;
1325  while(pi>srcMap) {
1326  if(*--pi>destLength) {
1327  destLength=*pi;
1328  }
1329  if(*pi>=0) {
1330  count++;
1331  }
1332  }
1333  destLength++; /* add 1 for origin 0 */
1334  if(count<destLength) {
1335  /* we must fill unmatched destMap entries with -1 */
1336  uprv_memset(destMap, 0xFF, destLength*sizeof(int32_t));
1337  }
1338  pi=srcMap+length;
1339  while(length>0) {
1340  if(*--pi>=0) {
1341  destMap[*pi]=--length;
1342  } else {
1343  --length;
1344  }
1345  }
1346  }
1347 }
int level
Definition: afm2pl.c:1694
#define count(a)
Definition: aptex-macros.h:781
#define uprv_memcpy(dst, src, size)
Definition: cmemory.h:40
#define uprv_memset(buffer, mark, size)
Definition: cmemory.h:51
@ FALSE
Definition: dd.h:101
@ TRUE
Definition: dd.h:102
#define uchar
Definition: dd.h:84
char * temp
Definition: dvidvi.c:137
static FIELD_PTR begin
Definition: genind.c:37
unsigned char UChar
Definition: bzip2.c:163
unsigned char uchar
Definition: unzcrash.c:37
#define NULL
Definition: ftobjs.h:61
small capitals from c petite p scientific i
Definition: afcover.h:80
signed int int32_t
Definition: stdint.h:77
#define length(c)
Definition: ctangleboot.c:65
#define U_EXPORT2
Definition: platform.h:844
static double const pi
Definition: clipper.cpp:53
int k
Definition: otp-parser.c:70
#define B(x, y)
static int offset
Definition: ppmtogif.c:642
C API: Unicode string handling functions.
Point * points
Definition: ubidiimp.h:252
int32_t size
Definition: ubidiimp.h:249
Definition: ubidiimp.h:199
int32_t insertRemove
Definition: ubidiimp.h:202
int32_t visualLimit
Definition: ubidiimp.h:201
int32_t logicalStart
Definition: ubidiimp.h:200
int32_t originalLength
Definition: ubidiimp.h:269
UBiDiLevel * levelsMemory
Definition: ubidiimp.h:289
const UBiDi * pParaBiDi
Definition: ubidiimp.h:263
int32_t trailingWSStart
Definition: ubidiimp.h:346
uint32_t reorderingOptions
Definition: ubidiimp.h:315
int32_t runCount
Definition: ubidiimp.h:357
int32_t paraCount
Definition: ubidiimp.h:349
int32_t controlCount
Definition: ubidiimp.h:378
Run simpleRuns[1]
Definition: ubidiimp.h:361
Run * runsMemory
Definition: ubidiimp.h:292
int32_t resultLength
Definition: ubidiimp.h:282
Run * runs
Definition: ubidiimp.h:358
Flags flags
Definition: ubidiimp.h:339
UBiDiReorderingMode reorderingMode
Definition: ubidiimp.h:306
UBiDiDirection direction
Definition: ubidiimp.h:336
const UChar * text
Definition: ubidiimp.h:266
DirProp * dirProps
Definition: ubidiimp.h:299
InsertPoints insertPoints
Definition: ubidiimp.h:375
UBiDiLevel paraLevel
Definition: ubidiimp.h:321
int32_t length
Definition: ubidiimp.h:276
UBiDiLevel * levels
Definition: ubidiimp.h:300
Definition: mpost.c:238
int j
Definition: t4ht.c:1589
m
Definition: tex4ht.c:3990
#define UPRV_UNREACHABLE
Definition: uassert.h:48
C API: Bidi algorithm.
#define UBIDI_DEFAULT_LTR
Definition: ubidi.h:365
#define UBIDI_MAX_EXPLICIT_LEVEL
Definition: ubidi.h:401
UBiDiDirection
Definition: ubidi.h:428
@ UBIDI_LTR
Definition: ubidi.h:440
@ UBIDI_MIXED
Definition: ubidi.h:459
@ UBIDI_RTL
Definition: ubidi.h:452
#define UBIDI_MAP_NOWHERE
Definition: ubidi.h:422
@ UBIDI_REORDER_RUNS_ONLY
Definition: ubidi.h:718
uint8_t UBiDiLevel
Definition: ubidi.h:339
#define RETURN_IF_NULL_OR_FAILING_ERRCODE(pErrcode, retvalue)
Definition: ubidiimp.h:398
#define getLevelsMemory(pBiDi, length)
Definition: ubidiimp.h:451
#define IS_VALID_PARA_OR_LINE(x)
Definition: ubidiimp.h:386
#define RETURN_IF_NOT_VALID_PARA_OR_LINE(bidi, errcode, retvalue)
Definition: ubidiimp.h:407
#define ADD_ODD_BIT_FROM_LEVEL(x, level)
Definition: ubidiimp.h:210
@ RLM_AFTER
Definition: ubidiimp.h:147
@ RLM_BEFORE
Definition: ubidiimp.h:146
@ LRM_BEFORE
Definition: ubidiimp.h:144
@ LRM_AFTER
Definition: ubidiimp.h:145
#define getRunsMemory(pBiDi, length)
Definition: ubidiimp.h:455
#define GET_PARALEVEL(ubidi, index)
Definition: ubidiimp.h:128
#define RETURN_IF_BAD_RANGE(arg, start, limit, errcode, retvalue)
Definition: ubidiimp.h:413
#define RETURN_VOID_IF_NULL_OR_FAILING_ERRCODE(pErrcode)
Definition: ubidiimp.h:420
#define REMOVE_ODD_BIT(x)
Definition: ubidiimp.h:211
#define RETURN_VOID_IF_BAD_RANGE(arg, start, limit, errcode)
Definition: ubidiimp.h:435
#define RETURN_VOID_IF_NOT_VALID_PARA(bidi, errcode)
Definition: ubidiimp.h:423
uint8_t DirProp
Definition: ubidiimp.h:37
#define GET_INDEX(x)
Definition: ubidiimp.h:213
#define IS_BIDI_CONTROL_CHAR(c)
Definition: ubidiimp.h:238
#define IS_EVEN_RUN(x)
Definition: ubidiimp.h:216
#define MASK_WS
Definition: ubidiimp.h:102
#define DIRPROP_FLAG(dir)
Definition: ubidiimp.h:78
#define MAKE_INDEX_ODD_PAIR(index, level)
Definition: ubidiimp.h:209
#define GET_ODD_BIT(x)
Definition: ubidiimp.h:214
static void getSingleRun(UBiDi *pBiDi, UBiDiLevel level)
Definition: ubidiln.cpp:392
static void reorderLine(UBiDi *pBiDi, UBiDiLevel minLevel, UBiDiLevel maxLevel)
Definition: ubidiln.cpp:437
static UBool prepareReorder(const UBiDiLevel *levels, int32_t length, int32_t *indexMap, UBiDiLevel *pMinLevel, UBiDiLevel *pMaxLevel)
Definition: ubidiln.cpp:710
static void setTrailingWSStart(UBiDi *pBiDi)
Definition: ubidiln.cpp:92
static int32_t getRunFromLogicalIndex(UBiDi *pBiDi, int32_t logicalIndex)
Definition: ubidiln.cpp:520
C API: Unicode Properties.
int8_t UBool
Definition: umachine.h:269
#define U_CAPI
Definition: umachine.h:110
#define U_CFUNC
Definition: umachine.h:84
#define ubidi_getVisualIndex
Definition: urename.h:458
#define ubidi_getLevelAt
Definition: urename.h:438
#define ubidi_reorderVisual
Definition: urename.h:471
#define ubidi_setLine
Definition: urename.h:475
#define ubidi_getVisualMap
Definition: urename.h:459
#define ubidi_getLogicalMap
Definition: urename.h:441
#define ubidi_getRuns
Definition: urename.h:456
#define ubidi_getVisualRun
Definition: urename.h:460
#define ubidi_getLevels
Definition: urename.h:439
#define ubidi_getLogicalIndex
Definition: urename.h:440
#define ubidi_getParagraph
Definition: urename.h:450
#define ubidi_countRuns
Definition: urename.h:429
#define ubidi_reorderLogical
Definition: urename.h:470
#define ubidi_invertMap
Definition: urename.h:461
#define ubidi_getLogicalRun
Definition: urename.h:442
@ start
Definition: preamble.c:52
Basic definitions for ICU, for both C and C++ APIs.
UErrorCode
Definition: utypes.h:431
@ U_MEMORY_ALLOCATION_ERROR
Definition: utypes.h:473
@ U_ILLEGAL_ARGUMENT_ERROR
Definition: utypes.h:467
@ U_ZERO_ERROR
Definition: utypes.h:465
#define U_FAILURE(x)
Definition: utypes.h:735
#define U_SUCCESS(x)
Definition: utypes.h:730
#define errorCode
Definition: xmlparse.c:601
#define limit(x)
Definition: yuvsplittoppm.c:26
#define end(cp)
Definition: zic.c:71