home *** CD-ROM | disk | FTP | other *** search
/ AmigActive 6 / AACD06.ISO / AACD / Programming / ICU / src / icu / source / common / ubidiln.c < prev    next >
Encoding:
C/C++ Source or Header  |  1999-10-19  |  33.9 KB  |  987 lines
  1. /*  
  2. *******************************************************************************
  3. *                                                                             *
  4. * COPYRIGHT:                                                                  *
  5. *   (C) Copyright International Business Machines Corporation, 1999           *
  6. *   Licensed Material - Program-Property of IBM - All Rights Reserved.        *
  7. *   US Government Users Restricted Rights - Use, duplication, or disclosure   *
  8. *   restricted by GSA ADP Schedule Contract with IBM Corp.                    *
  9. *                                                                             *
  10. *******************************************************************************
  11. *   file name:  ubidiln.c
  12. *   encoding:   US-ASCII
  13. *   tab size:   8 (not used)
  14. *   indentation:4
  15. *
  16. *   created on: 1999aug06
  17. *   created by: Markus W. Scherer
  18. */
  19.  
  20. /* set import/export definitions */
  21. #ifndef U_COMMON_IMPLEMENTATION
  22. #   define U_COMMON_IMPLEMENTATION
  23. #endif
  24.  
  25. #include "cmemory.h"
  26. #include "utypes.h"
  27. #include "ustring.h"
  28. #include "uchar.h"
  29. #include "ubidi.h"
  30. #include "ubidiimp.h"
  31.  
  32. /*
  33.  * General remarks about the functions in this file:
  34.  *
  35.  * These functions deal with the aspects of potentially mixed-directional
  36.  * text in a single paragraph or in a line of a single paragraph
  37.  * which has already been processed according to
  38.  * the Unicode 3.0 BiDi algorithm as defined in
  39.  * http://www.unicode.org/unicode/reports/tr9/ , version 5,
  40.  * also described in The Unicode Standard, Version 3.0 .
  41.  *
  42.  * This means that there is a UBiDi object with a levels
  43.  * and a dirProps array.
  44.  * paraLevel and direction are also set.
  45.  * Only if the length of the text is zero, then levels==dirProps==NULL.
  46.  *
  47.  * The overall directionality of the paragraph
  48.  * or line is used to bypass the reordering steps if possible.
  49.  * Even purely RTL text does not need reordering there because
  50.  * the ubidi_getLogical/VisualIndex() functions can compute the
  51.  * index on the fly in such a case.
  52.  *
  53.  * The implementation of the access to same-level-runs and of the reordering
  54.  * do attempt to provide better performance and less memory usage compared to
  55.  * a direct implementation of especially rule (L2) with an array of
  56.  * one (32-bit) integer per text character.
  57.  *
  58.  * Here, the levels array is scanned as soon as necessary, and a vector of
  59.  * same-level-runs is created. Reordering then is done on this vector.
  60.  * For each run of text positions that were resolved to the same level,
  61.  * only 8 bytes are stored: the first text position of the run and the visual
  62.  * position behind the run after reordering.
  63.  * One sign bit is used to hold the directionality of the run.
  64.  * This is inefficient if there are many very short runs. If the average run
  65.  * length is <2, then this uses more memory.
  66.  *
  67.  * In a further attempt to save memory, the levels array is never changed
  68.  * after all the resolution rules (Xn, Wn, Nn, In).
  69.  * Many functions have to consider the field trailingWSStart:
  70.  * if it is less than length, then there is an implicit trailing run
  71.  * at the paraLevel,
  72.  * which is not reflected in the levels array.
  73.  * This allows a line UBiDi object to use the same levels array as
  74.  * its paragraph parent object.
  75.  *
  76.  * When a UBiDi object is created for a line of a paragraph, then the
  77.  * paragraph's levels and dirProps arrays are reused by way of setting
  78.  * a pointer into them, not by copying. This again saves memory and forbids to
  79.  * change the now shared levels for (L1).
  80.  */
  81.  
  82. /* prototypes --------------------------------------------------------------- */
  83.  
  84. static void
  85. setTrailingWSStart(UBiDi *pBiDi);
  86.  
  87. static bool_t
  88. getRuns(UBiDi *pBiDi);
  89.  
  90. static void
  91. getSingleRun(UBiDi *pBiDi, UBiDiLevel level);
  92.  
  93. static void
  94. reorderLine(UBiDi *pBiDi, UBiDiLevel minLevel, UBiDiLevel maxLevel);
  95.  
  96. static bool_t
  97. prepareReorder(const UBiDiLevel *levels, UTextOffset length,
  98.                UTextOffset *indexMap,
  99.                UBiDiLevel *pMinLevel, UBiDiLevel *pMaxLevel);
  100.  
  101. /* ubidi_setLine ------------------------------------------------------------ */
  102.  
  103. U_CAPI void U_EXPORT2
  104. ubidi_setLine(const UBiDi *pParaBiDi,
  105.               UTextOffset start, UTextOffset limit,
  106.               UBiDi *pLineBiDi,
  107.               UErrorCode *pErrorCode) {
  108.     UTextOffset length;
  109.  
  110.     /* check the argument values */
  111.     if(pErrorCode==NULL || U_FAILURE(*pErrorCode)) {
  112.         return;
  113.     } else if(pParaBiDi==NULL || pLineBiDi==NULL) {
  114.         *pErrorCode=U_ILLEGAL_ARGUMENT_ERROR;
  115.         return;
  116.     } else if(start<0 || start>limit || limit>pParaBiDi->length) {
  117.         *pErrorCode=U_INDEX_OUTOFBOUNDS_ERROR;
  118.         return;
  119.     }
  120.  
  121.     /* set the values in pLineBiDi from its pParaBiDi parent */
  122.     length=pLineBiDi->length=limit-start;
  123.     pLineBiDi->paraLevel=pParaBiDi->paraLevel;
  124.  
  125.     pLineBiDi->runs=NULL;
  126.     pLineBiDi->flags=0;
  127.  
  128.     if(length>0) {
  129.         pLineBiDi->dirProps=pParaBiDi->dirProps+start;
  130.         pLineBiDi->levels=pParaBiDi->levels+start;
  131.         pLineBiDi->runCount=-1;
  132.  
  133.         if(pParaBiDi->direction!=UBIDI_MIXED) {
  134.             /* the parent is already trivial */
  135.             pLineBiDi->direction=pParaBiDi->direction;
  136.  
  137.             /*
  138.              * The parent's levels are all either
  139.              * implicitly or explicitly ==paraLevel;
  140.              * do the same here.
  141.              */
  142.             if(pParaBiDi->trailingWSStart<=start) {
  143.                 pLineBiDi->trailingWSStart=0;
  144.             } else if(pParaBiDi->trailingWSStart<limit) {
  145.                 pLineBiDi->trailingWSStart=pParaBiDi->trailingWSStart-start;
  146.             } else {
  147.                 pLineBiDi->trailingWSStart=length;
  148.             }
  149.         } else {
  150.             const UBiDiLevel *levels=pLineBiDi->levels;
  151.             UTextOffset i, trailingWSStart;
  152.             UBiDiLevel level;
  153.             Flags flags=0;
  154.  
  155.             setTrailingWSStart(pLineBiDi);
  156.             trailingWSStart=pLineBiDi->trailingWSStart;
  157.  
  158.             /* recalculate pLineBiDi->direction */
  159.             if(trailingWSStart==0) {
  160.                 /* all levels are at paraLevel */
  161.                 pLineBiDi->direction=(UBiDiDirection)(pLineBiDi->paraLevel&1);
  162.             } else {
  163.                 /* get the level of the first character */
  164.                 level=levels[0]&1;
  165.  
  166.                 /* if there is anything of a different level, then the line is mixed */
  167.                 if(trailingWSStart<length && (pLineBiDi->paraLevel&1)!=level) {
  168.                     /* the trailing WS is at paraLevel, which differs from levels[0] */
  169.                     pLineBiDi->direction=UBIDI_MIXED;
  170.                 } else {
  171.                     /* see if levels[1..trailingWSStart-1] have the same direction as levels[0] and paraLevel */
  172.                     i=1;
  173.                     for(;;) {
  174.                         if(i==trailingWSStart) {
  175.                             /* the direction values match those in level */
  176.                             pLineBiDi->direction=(UBiDiDirection)level;
  177.                             break;
  178.                         } else if((levels[i]&1)!=level) {
  179.                             pLineBiDi->direction=UBIDI_MIXED;
  180.                             break;
  181.                         }
  182.                         ++i;
  183.                     }
  184.                 }
  185.             }
  186.  
  187.             switch(pLineBiDi->direction) {
  188.             case UBIDI_LTR:
  189.                 /* make sure paraLevel is even */
  190.                 pLineBiDi->paraLevel=(pLineBiDi->paraLevel+1)&~1;
  191.  
  192.                 /* all levels are implicitly at paraLevel (important for ubidi_getLevels()) */
  193.                 pLineBiDi->trailingWSStart=0;
  194.                 break;
  195.             case UBIDI_RTL:
  196.                 /* make sure paraLevel is odd */
  197.                 pLineBiDi->paraLevel|=1;
  198.  
  199.                 /* all levels are implicitly at paraLevel (important for ubidi_getLevels()) */
  200.                 pLineBiDi->trailingWSStart=0;
  201.                 break;
  202.             default:
  203.                 break;
  204.             }
  205.         }
  206.     } else {
  207.         /* create an object for a zero-length line */
  208.         pLineBiDi->direction=pLineBiDi->paraLevel&1 ? UBIDI_RTL : UBIDI_LTR;
  209.         pLineBiDi->trailingWSStart=pLineBiDi->runCount=0;
  210.  
  211.         pLineBiDi->dirProps=NULL;
  212.         pLineBiDi->levels=NULL;
  213.     }
  214.     return;
  215. }
  216.  
  217. U_CAPI UBiDiLevel U_EXPORT2
  218. ubidi_getLevelAt(const UBiDi *pBiDi, UTextOffset charIndex) {
  219.     /* return paraLevel if in the trailing WS run, otherwise the real level */
  220.     if(pBiDi==NULL || charIndex<0 || pBiDi->length<=charIndex) {
  221.         return 0;
  222.     } else if(pBiDi->direction!=UBIDI_MIXED || charIndex>=pBiDi->trailingWSStart) {
  223.         return pBiDi->paraLevel;
  224.     } else {
  225.         return pBiDi->levels[charIndex];
  226.     }
  227. }
  228.  
  229. U_CAPI const UBiDiLevel * U_EXPORT2
  230. ubidi_getLevels(UBiDi *pBiDi, UErrorCode *pErrorCode) {
  231.     UTextOffset start, length;
  232.  
  233.     if(pErrorCode==NULL || U_FAILURE(*pErrorCode)) {
  234.         return NULL;
  235.     } else if(pBiDi==NULL || (length=pBiDi->length)<=0) {
  236.         *pErrorCode=U_ILLEGAL_ARGUMENT_ERROR;
  237.         return NULL;
  238.     }
  239.  
  240.     if((start=pBiDi->trailingWSStart)==length) {
  241.         /* the current levels array reflects the WS run */
  242.         return pBiDi->levels;
  243.     }
  244.  
  245.     /*
  246.      * After the previous if(), we know that the levels array
  247.      * has an implicit trailing WS run and therefore does not fully
  248.      * reflect itself all the levels.
  249.      * This must be a UBiDi object for a line, and
  250.      * we need to create a new levels array.
  251.      */
  252.  
  253.     if(getLevelsMemory(pBiDi, length)) {
  254.         UBiDiLevel *levels=pBiDi->levelsMemory;
  255.  
  256.         if(start>0 && levels!=pBiDi->levels) {
  257.             icu_memcpy(levels, pBiDi->levels, start);
  258.         }
  259.         icu_memset(levels+start, pBiDi->paraLevel, length-start);
  260.  
  261.         /* this new levels array is set for the line and reflects the WS run */
  262.         pBiDi->trailingWSStart=length;
  263.         return pBiDi->levels=levels;
  264.     } else {
  265.         /* out of memory */
  266.         *pErrorCode=U_MEMORY_ALLOCATION_ERROR;
  267.         return NULL;
  268.     }
  269. }
  270.  
  271. U_CAPI void U_EXPORT2
  272. ubidi_getLogicalRun(const UBiDi *pBiDi, UTextOffset logicalStart,
  273.                     UTextOffset *pLogicalLimit, UBiDiLevel *pLevel) {
  274.     UTextOffset length;
  275.  
  276.     if(pBiDi==NULL || logicalStart<0 || (length=pBiDi->length)<=logicalStart) {
  277.         return;
  278.     }
  279.  
  280.     if(pBiDi->direction!=UBIDI_MIXED || logicalStart>=pBiDi->trailingWSStart) {
  281.         if(pLogicalLimit!=NULL) {
  282.             *pLogicalLimit=length;
  283.         }
  284.         if(pLevel!=NULL) {
  285.             *pLevel=pBiDi->paraLevel;
  286.         }
  287.     } else {
  288.         UBiDiLevel *levels=pBiDi->levels;
  289.         UBiDiLevel level=levels[logicalStart];
  290.  
  291.         /* search for the end of the run */
  292.         length=pBiDi->trailingWSStart;
  293.         while(++logicalStart<length && level==levels[logicalStart]) {}
  294.  
  295.         if(pLogicalLimit!=NULL) {
  296.             *pLogicalLimit=logicalStart;
  297.         }
  298.         if(pLevel!=NULL) {
  299.             *pLevel=level;
  300.         }
  301.     }
  302. }
  303.  
  304. /* handle trailing WS (L1) -------------------------------------------------- */
  305.  
  306. /*
  307.  * setTrailingWSStart() sets the start index for a trailing
  308.  * run of WS in the line. This is necessary because we do not modify
  309.  * the paragraph's levels array that we just point into.
  310.  * Using trailingWSStart is another form of performing (L1).
  311.  *
  312.  * To make subsequent operations easier, we also include the run
  313.  * before the WS if it is at the paraLevel - we merge the two here.
  314.  */
  315. static void
  316. setTrailingWSStart(UBiDi *pBiDi) {
  317.     /* pBiDi->direction!=UBIDI_MIXED */
  318.  
  319.     const DirProp *dirProps=pBiDi->dirProps;
  320.     UBiDiLevel *levels=pBiDi->levels;
  321.     UTextOffset start=pBiDi->length;
  322.     UBiDiLevel paraLevel=pBiDi->paraLevel;
  323.  
  324.     /* go backwards across all WS, BN, explicit codes */
  325.     while(start>0 && DIRPROP_FLAG(dirProps[start-1])&MASK_WS) {
  326.         --start;
  327.     }
  328.  
  329.     /* if the WS run can be merged with the previous run then do so here */
  330.     while(start>0 && levels[start-1]==paraLevel) {
  331.         --start;
  332.     }
  333.  
  334.     pBiDi->trailingWSStart=start;
  335. }
  336.  
  337. /* runs API functions ------------------------------------------------------- */
  338.  
  339. U_CAPI UTextOffset U_EXPORT2
  340. ubidi_countRuns(UBiDi *pBiDi, UErrorCode *pErrorCode) {
  341.     if(pErrorCode==NULL || U_FAILURE(*pErrorCode)) {
  342.         return -1;
  343.     } else if(pBiDi==NULL || pBiDi->runCount<0 && !getRuns(pBiDi)) {
  344.         *pErrorCode=U_MEMORY_ALLOCATION_ERROR;
  345.         return -1;
  346.     } else {
  347.         return pBiDi->runCount;
  348.     }
  349. }
  350.  
  351. U_CAPI UBiDiDirection U_EXPORT2
  352. ubidi_getVisualRun(UBiDi *pBiDi, UTextOffset runIndex,
  353.                    UTextOffset *pLogicalStart, UTextOffset *pLength) {
  354.     if( pBiDi==NULL || runIndex<0 ||
  355.         pBiDi->runCount==-1 && !getRuns(pBiDi) ||
  356.         runIndex>=pBiDi->runCount
  357.     ) {
  358.         return 0;
  359.     } else {
  360.         UTextOffset start=pBiDi->runs[runIndex].logicalStart;
  361.         if(pLogicalStart!=NULL) {
  362.             *pLogicalStart=GET_INDEX(start);
  363.         }
  364.         if(pLength!=NULL) {
  365.             if(runIndex>0) {
  366.                 *pLength=pBiDi->runs[runIndex].visualLimit-
  367.                          pBiDi->runs[runIndex-1].visualLimit;
  368.             } else {
  369.                 *pLength=pBiDi->runs[0].visualLimit;
  370.             }
  371.         }
  372.         return (UBiDiDirection)GET_ODD_BIT(start);
  373.     }
  374. }
  375.  
  376. /* compute the runs array --------------------------------------------------- */
  377.  
  378. /*
  379.  * Compute the runs array from the levels array.
  380.  * After getRuns() returns TRUE, runCount is guaranteed to be >0
  381.  * and the runs are reordered.
  382.  * Odd-level runs have visualStart on their visual right edge and
  383.  * they progress visually to the left.
  384.  */
  385. static bool_t
  386. getRuns(UBiDi *pBiDi) {
  387.     if(pBiDi->direction!=UBIDI_MIXED) {
  388.         /* simple, single-run case - this covers length==0 */
  389.         getSingleRun(pBiDi, pBiDi->paraLevel);
  390.     } else /* UBIDI_MIXED, length>0 */ {
  391.         /* mixed directionality */
  392.         UTextOffset length=pBiDi->length, limit=length;
  393.  
  394.         /*
  395.          * If there are WS characters at the end of the line
  396.          * and the run preceding them has a level different from
  397.          * paraLevel, then they will form their own run at paraLevel (L1).
  398.          * Count them separately.
  399.          * We need some special treatment for this in order to not
  400.          * modify the levels array which a line UBiDi object shares
  401.          * with its paragraph parent and its other line siblings.
  402.          * In other words, for the trailing WS, it may be
  403.          * levels[]!=paraLevel but we have to treat it like it were so.
  404.          */
  405.         limit=pBiDi->trailingWSStart;
  406.         if(limit==0) {
  407.             /* there is only WS on this line */
  408.             getSingleRun(pBiDi, pBiDi->paraLevel);
  409.         } else {
  410.             UBiDiLevel *levels=pBiDi->levels;
  411.             UTextOffset i, runCount;
  412.             UBiDiLevel level=UBIDI_DEFAULT_LTR;   /* initialize with no valid level */
  413.  
  414.             /* count the runs, there is at least one non-WS run, and limit>0 */
  415.             runCount=0;
  416.             for(i=0; i<limit; ++i) {
  417.                 /* increment runCount at the start of each run */
  418.                 if(levels[i]!=level) {
  419.                     ++runCount;
  420.                     level=levels[i];
  421.                 }
  422.             }
  423.  
  424.             /*
  425.              * We don't need to see if the last run can be merged with a trailing
  426.              * WS run because setTrailingWSStart() would have done that.
  427.              */
  428.             if(runCount==1 && limit==length) {
  429.                 /* There is only one non-WS run and no trailing WS-run. */
  430.                 getSingleRun(pBiDi, levels[0]);
  431.             } else /* runCount>1 || limit<length */ {
  432.                 /* allocate and set the runs */
  433.                 Run *runs;
  434.                 UTextOffset runIndex, start;
  435.                 UBiDiLevel minLevel=UBIDI_MAX_EXPLICIT_LEVEL+1, maxLevel=0;
  436.  
  437.                 /* now, count a (non-mergable) WS run */
  438.                 if(limit<length) {
  439.                     ++runCount;
  440.                 }
  441.  
  442.                 /* runCount>1 */
  443.                 if(getRunsMemory(pBiDi, runCount)) {
  444.                     runs=pBiDi->runsMemory;
  445.                 } else {
  446.                     return FALSE;
  447.                 }
  448.  
  449.                 /* set the runs */
  450.                 /* this could be optimized, e.g.: 464->444, 484->444, 575->555, 595->555 */
  451.                 /* however, that would take longer and make other functions more complicated */
  452.                 runIndex=0;
  453.  
  454.                 /* search for the run ends */
  455.                 start=0;
  456.                 level=levels[0];
  457.                 if(level<minLevel) {
  458.                     minLevel=level;
  459.                 }
  460.                 if(level>maxLevel) {
  461.                     maxLevel=level;
  462.                 }
  463.  
  464.                 /* initialize visualLimit values with the run lengths */
  465.                 for(i=1; i<limit; ++i) {
  466.                     if(levels[i]!=level) {
  467.                         /* i is another run limit */
  468.                         runs[runIndex].logicalStart=start;
  469.                         runs[runIndex].visualLimit=i-start;
  470.                         start=i;
  471.  
  472.                         level=levels[i];
  473.                         if(level<minLevel) {
  474.                             minLevel=level;
  475.                         }
  476.                         if(level>maxLevel) {
  477.                             maxLevel=level;
  478.                         }
  479.                         ++runIndex;
  480.                     }
  481.                 }
  482.  
  483.                 /* finish the last run at i==limit */
  484.                 runs[runIndex].logicalStart=start;
  485.                 runs[runIndex].visualLimit=limit-start;
  486.                 ++runIndex;
  487.  
  488.                 if(limit<length) {
  489.                     /* there is a separate WS run */
  490.                     runs[runIndex].logicalStart=limit;
  491.                     runs[runIndex].visualLimit=length-limit;
  492.                     if(pBiDi->paraLevel<minLevel) {
  493.                         minLevel=pBiDi->paraLevel;
  494.                     }
  495.                 }
  496.  
  497.                 /* set the object fields */
  498.                 pBiDi->runs=runs;
  499.                 pBiDi->runCount=runCount;
  500.  
  501.                 reorderLine(pBiDi, minLevel, maxLevel);
  502.  
  503.                 /* now add the direction flags and adjust the visualLimit's to be just that */
  504.                 ADD_ODD_BIT_FROM_LEVEL(runs[0].logicalStart, levels[runs[0].logicalStart]);
  505.                 limit=runs[0].visualLimit;
  506.                 for(i=1; i<runIndex; ++i) {
  507.                     ADD_ODD_BIT_FROM_LEVEL(runs[i].logicalStart, levels[runs[i].logicalStart]);
  508.                     limit=runs[i].visualLimit+=limit;
  509.                 }
  510.  
  511.                 /* same for the trailing WS run */
  512.                 if(runIndex<runCount) {
  513.                     ADD_ODD_BIT_FROM_LEVEL(runs[i].logicalStart, pBiDi->paraLevel);
  514.                     runs[runIndex].visualLimit+=limit;
  515.                 }
  516.             }
  517.         }
  518.     }
  519.     return TRUE;
  520. }
  521.  
  522. /* in trivial cases there is only one trivial run; called by getRuns() */
  523. static void
  524. getSingleRun(UBiDi *pBiDi, UBiDiLevel level) {
  525.     /* simple, single-run case */
  526.     pBiDi->runs=pBiDi->simpleRuns;
  527.     pBiDi->runCount=1;
  528.  
  529.     /* fill and reorder the single run */
  530.     pBiDi->runs[0].logicalStart=MAKE_INDEX_ODD_PAIR(0, level);
  531.     pBiDi->runs[0].visualLimit=pBiDi->length;
  532. }
  533.  
  534. /* reorder the runs array (L2) ---------------------------------------------- */
  535.  
  536. /*
  537.  * Reorder the same-level runs in the runs array.
  538.  * Here, runCount>1 and maxLevel>=minLevel>=paraLevel.
  539.  * All the visualStart fields=logical start before reordering.
  540.  * The "odd" bits are not set yet.
  541.  *
  542.  * Reordering with this data structure lends itself to some handy shortcuts:
  543.  *
  544.  * Since each run is moved but not modified, and since at the initial maxLevel
  545.  * each sequence of same-level runs consists of only one run each, we
  546.  * don't need to do anything there and can predecrement maxLevel.
  547.  * In many simple cases, the reordering is thus done entirely in the
  548.  * index mapping.
  549.  * Also, reordering occurs only down to the lowest odd level that occurs,
  550.  * which is minLevel|1. However, if the lowest level itself is odd, then
  551.  * in the last reordering the sequence of the runs at this level or higher
  552.  * will be all runs, and we don't need the elaborate loop to search for them.
  553.  * This is covered by ++minLevel instead of minLevel|=1 followed
  554.  * by an extra reorder-all after the reorder-some loop.
  555.  * About a trailing WS run:
  556.  * Such a run would need special treatment because its level is not
  557.  * reflected in levels[] if this is not a paragraph object.
  558.  * Instead, all characters from trailingWSStart on are implicitly at
  559.  * paraLevel.
  560.  * However, for all maxLevel>paraLevel, this run will never be reordered
  561.  * and does not need to be taken into account. maxLevel==paraLevel is only reordered
  562.  * if minLevel==paraLevel is odd, which is done in the extra segment.
  563.  * This means that for the main reordering loop we don't need to consider
  564.  * this run and can --runCount. If it is later part of the all-runs
  565.  * reordering, then runCount is adjusted accordingly.
  566.  */
  567. static void
  568. reorderLine(UBiDi *pBiDi, UBiDiLevel minLevel, UBiDiLevel maxLevel) {
  569.     Run *runs;
  570.     UBiDiLevel *levels;
  571.     UTextOffset firstRun, endRun, limitRun, runCount,
  572.           temp, trailingWSStart=pBiDi->trailingWSStart;
  573.  
  574.     /* nothing to do? */
  575.     if(maxLevel<=(minLevel|1)) {
  576.         return;
  577.     }
  578.  
  579.     /*
  580.      * Reorder only down to the lowest odd level
  581.      * and reorder at an odd minLevel in a separate, simpler loop.
  582.      * See comments above for why minLevel is always incremented.
  583.      */
  584.     ++minLevel;
  585.  
  586.     runs=pBiDi->runs;
  587.     levels=pBiDi->levels;
  588.     runCount=pBiDi->runCount;
  589.  
  590.     /* do not include the WS run at paraLevel<=old minLevel except in the simple loop */
  591.     if(pBiDi->trailingWSStart<pBiDi->length) {
  592.         --runCount;
  593.     }
  594.  
  595.     while(--maxLevel>=minLevel) {
  596.         firstRun=0;
  597.  
  598.         /* loop for all sequences of runs */
  599.         for(;;) {
  600.             /* look for a sequence of runs that are all at >=maxLevel */
  601.             /* look for the first run of such a sequence */
  602.             while(firstRun<runCount && levels[runs[firstRun].logicalStart]<maxLevel) {
  603.                 ++firstRun;
  604.             }
  605.             if(firstRun>=runCount) {
  606.                 break;  /* no more such runs */
  607.             }
  608.  
  609.             /* look for the limit run of such a sequence (the run behind it) */
  610.             for(limitRun=firstRun; ++limitRun<runCount && levels[runs[limitRun].logicalStart]>=maxLevel;) {}
  611.  
  612.             /* Swap the entire sequence of runs from firstRun to limitRun-1. */
  613.             endRun=limitRun-1;
  614.             while(firstRun<endRun) {
  615.                 temp=runs[firstRun].logicalStart;
  616.                 runs[firstRun].logicalStart=runs[endRun].logicalStart;
  617.                 runs[endRun].logicalStart=temp;
  618.  
  619.                 temp=runs[firstRun].visualLimit;
  620.                 runs[firstRun].visualLimit=runs[endRun].visualLimit;
  621.                 runs[endRun].visualLimit=temp;
  622.  
  623.                 ++firstRun;
  624.                 --endRun;
  625.             }
  626.  
  627.             if(limitRun==runCount) {
  628.                 break;  /* no more such runs */
  629.             } else {
  630.                 firstRun=limitRun+1;
  631.             }
  632.         }
  633.     }
  634.  
  635.     /* now do maxLevel==old minLevel (==odd!), see above */
  636.     if(!(minLevel&1)) {
  637.         firstRun=0;
  638.  
  639.         /* include the trailing WS run in this complete reordering */
  640.         if(pBiDi->trailingWSStart==pBiDi->length) {
  641.             --runCount;
  642.         }
  643.  
  644.         /* Swap the entire sequence of all runs. (endRun==runCount) */
  645.         while(firstRun<runCount) {
  646.             temp=runs[firstRun].logicalStart;
  647.             runs[firstRun].logicalStart=runs[runCount].logicalStart;
  648.             runs[runCount].logicalStart=temp;
  649.  
  650.             temp=runs[firstRun].visualLimit;
  651.             runs[firstRun].visualLimit=runs[runCount].visualLimit;
  652.             runs[runCount].visualLimit=temp;
  653.  
  654.             ++firstRun;
  655.             --runCount;
  656.         }
  657.     }
  658. }
  659.  
  660. /* reorder a line based on a levels array (L2) ------------------------------ */
  661.  
  662. U_CAPI void U_EXPORT2
  663. ubidi_reorderLogical(const UBiDiLevel *levels, UTextOffset length, UTextOffset *indexMap) {
  664.     UTextOffset start, limit, sumOfSosEos;
  665.     UBiDiLevel minLevel, maxLevel;
  666.  
  667.     if(indexMap==NULL || !prepareReorder(levels, length, indexMap, &minLevel, &maxLevel)) {
  668.         return;
  669.     }
  670.  
  671.     /* nothing to do? */
  672.     if(minLevel==maxLevel && (minLevel&1)==0) {
  673.         return;
  674.     }
  675.  
  676.     /* reorder only down to the lowest odd level */
  677.     minLevel|=1;
  678.  
  679.     /* loop maxLevel..minLevel */
  680.     do {
  681.         start=0;
  682.  
  683.         /* loop for all sequences of levels to reorder at the current maxLevel */
  684.         for(;;) {
  685.             /* look for a sequence of levels that are all at >=maxLevel */
  686.             /* look for the first index of such a sequence */
  687.             while(start<length && levels[start]<maxLevel) {
  688.                 ++start;
  689.             }
  690.             if(start>=length) {
  691.                 break;  /* no more such sequences */
  692.             }
  693.  
  694.             /* look for the limit of such a sequence (the index behind it) */
  695.             for(limit=start; ++limit<length && levels[limit]>=maxLevel;) {}
  696.  
  697.             /*
  698.              * sos=start of sequence, eos=end of sequence
  699.              *
  700.              * The closed (inclusive) interval from sos to eos includes all the logical
  701.              * and visual indexes within this sequence. They are logically and
  702.              * visually contiguous and in the same range.
  703.              *
  704.              * For each run, the new visual index=sos+eos-old visual index;
  705.              * we pre-add sos+eos into sumOfSosEos ->
  706.              * new visual index=sumOfSosEos-old visual index;
  707.              */
  708.             sumOfSosEos=start+limit-1;
  709.  
  710.             /* reorder each index in the sequence */
  711.             do {
  712.                 indexMap[start]=sumOfSosEos-indexMap[start];
  713.             } while(++start<limit);
  714.  
  715.             /* start==limit */
  716.             if(limit==length) {
  717.                 break;  /* no more such sequences */
  718.             } else {
  719.                 start=limit+1;
  720.             }
  721.         }
  722.     } while(--maxLevel>=minLevel);
  723. }
  724.  
  725. U_CAPI void U_EXPORT2
  726. ubidi_reorderVisual(const UBiDiLevel *levels, UTextOffset length, UTextOffset *indexMap) {
  727.     UTextOffset start, end, limit, temp;
  728.     UBiDiLevel minLevel, maxLevel;
  729.  
  730.     if(indexMap==NULL || !prepareReorder(levels, length, indexMap, &minLevel, &maxLevel)) {
  731.         return;
  732.     }
  733.  
  734.     /* nothing to do? */
  735.     if(minLevel==maxLevel && (minLevel&1)==0) {
  736.         return;
  737.     }
  738.  
  739.     /* reorder only down to the lowest odd level */
  740.     minLevel|=1;
  741.  
  742.     /* loop maxLevel..minLevel */
  743.     do {
  744.         start=0;
  745.  
  746.         /* loop for all sequences of levels to reorder at the current maxLevel */
  747.         for(;;) {
  748.             /* look for a sequence of levels that are all at >=maxLevel */
  749.             /* look for the first index of such a sequence */
  750.             while(start<length && levels[start]<maxLevel) {
  751.                 ++start;
  752.             }
  753.             if(start>=length) {
  754.                 break;  /* no more such runs */
  755.             }
  756.  
  757.             /* look for the limit of such a sequence (the index behind it) */
  758.             for(limit=start; ++limit<length && levels[limit]>=maxLevel;) {}
  759.  
  760.             /*
  761.              * Swap the entire interval of indexes from start to limit-1.
  762.              * We don't need to swap the levels for the purpose of this
  763.              * algorithm: the sequence of levels that we look at does not
  764.              * move anyway.
  765.              */
  766.             end=limit-1;
  767.             while(start<end) {
  768.                 temp=indexMap[start];
  769.                 indexMap[start]=indexMap[end];
  770.                 indexMap[end]=temp;
  771.  
  772.                 ++start;
  773.                 --end;
  774.             }
  775.  
  776.             if(limit==length) {
  777.                 break;  /* no more such sequences */
  778.             } else {
  779.                 start=limit+1;
  780.             }
  781.         }
  782.     } while(--maxLevel>=minLevel);
  783. }
  784.  
  785. static bool_t
  786. prepareReorder(const UBiDiLevel *levels, UTextOffset length,
  787.                UTextOffset *indexMap,
  788.                UBiDiLevel *pMinLevel, UBiDiLevel *pMaxLevel) {
  789.     UTextOffset start;
  790.     UBiDiLevel level, minLevel, maxLevel;
  791.  
  792.     if(levels==NULL || length<=0) {
  793.         return FALSE;
  794.     }
  795.  
  796.     /* determine minLevel and maxLevel */
  797.     minLevel=UBIDI_MAX_EXPLICIT_LEVEL+1;
  798.     maxLevel=0;
  799.     for(start=length; start>0;) {
  800.         level=levels[--start];
  801.         if(level>UBIDI_MAX_EXPLICIT_LEVEL+1) {
  802.             return FALSE;
  803.         }
  804.         if(level<minLevel) {
  805.             minLevel=level;
  806.         }
  807.         if(level>maxLevel) {
  808.             maxLevel=level;
  809.         }
  810.     }
  811.     *pMinLevel=minLevel;
  812.     *pMaxLevel=maxLevel;
  813.  
  814.     /* initialize the index map */
  815.     for(start=length; start>0;) {
  816.         --start;
  817.         indexMap[start]=start;
  818.     }
  819.  
  820.     return TRUE;
  821. }
  822.  
  823. /* API functions for logical<->visual mapping ------------------------------- */
  824.  
  825. U_CAPI UTextOffset U_EXPORT2
  826. ubidi_getVisualIndex(UBiDi *pBiDi, UTextOffset logicalIndex, UErrorCode *pErrorCode) {
  827.     if(pErrorCode==NULL || U_FAILURE(*pErrorCode)) {
  828.         return 0;
  829.     } else if(pBiDi==NULL) {
  830.         *pErrorCode=U_ILLEGAL_ARGUMENT_ERROR;
  831.         return 0;
  832.     } else if(logicalIndex<0 || pBiDi->length<=logicalIndex) {
  833.         *pErrorCode=U_INDEX_OUTOFBOUNDS_ERROR;
  834.         return 0;
  835.     } else {
  836.         /* we can do the trivial cases without the runs array */
  837.         switch(pBiDi->direction) {
  838.         case UBIDI_LTR:
  839.             return logicalIndex;
  840.         case UBIDI_RTL:
  841.             return pBiDi->length-logicalIndex-1;
  842.         default:
  843.             if(pBiDi->runCount<0 && !getRuns(pBiDi)) {
  844.                 *pErrorCode=U_MEMORY_ALLOCATION_ERROR;
  845.                 return 0;
  846.             } else {
  847.                 Run *runs=pBiDi->runs;
  848.                 UTextOffset i, visualStart=0, offset, length;
  849.  
  850.                 /* linear search for the run, search on the visual runs */
  851.                 for(i=0;; ++i) {
  852.                     length=runs[i].visualLimit-visualStart;
  853.                     offset=logicalIndex-GET_INDEX(runs[i].logicalStart);
  854.                     if(offset>=0 && offset<length) {
  855.                         if(IS_EVEN_RUN(runs[i].logicalStart)) {
  856.                             /* LTR */
  857.                             return visualStart+offset;
  858.                         } else {
  859.                             /* RTL */
  860.                             return visualStart+length-offset-1;
  861.                         }
  862.                     }
  863.                     visualStart+=length;
  864.                 }
  865.             }
  866.         }
  867.     }
  868. }
  869.  
  870. U_CAPI UTextOffset U_EXPORT2
  871. ubidi_getLogicalIndex(UBiDi *pBiDi, UTextOffset visualIndex, UErrorCode *pErrorCode) {
  872.     if(pErrorCode==NULL || U_FAILURE(*pErrorCode)) {
  873.         return 0;
  874.     } else if(pBiDi==NULL) {
  875.         *pErrorCode=U_ILLEGAL_ARGUMENT_ERROR;
  876.         return 0;
  877.     } else if(visualIndex<0 || pBiDi->length<=visualIndex) {
  878.         *pErrorCode=U_INDEX_OUTOFBOUNDS_ERROR;
  879.         return 0;
  880.     } else {
  881.         /* we can do the trivial cases without the runs array */
  882.         switch(pBiDi->direction) {
  883.         case UBIDI_LTR:
  884.             return visualIndex;
  885.         case UBIDI_RTL:
  886.             return pBiDi->length-visualIndex-1;
  887.         default:
  888.             if(pBiDi->runCount<0 && !getRuns(pBiDi)) {
  889.                 *pErrorCode=U_MEMORY_ALLOCATION_ERROR;
  890.                 return 0;
  891.             } else {
  892.                 Run *runs=pBiDi->runs;
  893.                 UTextOffset i, runCount=pBiDi->runCount, start;
  894.  
  895.                 if(runCount<=10) {
  896.                     /* linear search for the run */
  897.                     for(i=0; visualIndex>=runs[i].visualLimit; ++i) {}
  898.                 } else {
  899.                     /* binary search for the run */
  900.                     UTextOffset start=0, limit=runCount;
  901.  
  902.                     /* the middle if() will guaranteed find the run, we don't need a loop limit */
  903.                     for(;;) {
  904.                         i=(start+limit)/2;
  905.                         if(visualIndex>=runs[i].visualLimit) {
  906.                             start=i+1;
  907.                         } else if(i==0 || visualIndex>=runs[i-1].visualLimit) {
  908.                             break;
  909.                         } else {
  910.                             limit=i;
  911.                         }
  912.                     }
  913.                 }
  914.  
  915.                 start=runs[i].logicalStart;
  916.                 if(IS_EVEN_RUN(start)) {
  917.                     /* LTR */
  918.                     /* the offset in runs[i] is visualIndex-runs[i-1].visualLimit */
  919.                     if(i>0) {
  920.                         visualIndex-=runs[i-1].visualLimit;
  921.                     }
  922.                     return GET_INDEX(start)+visualIndex;
  923.                 } else {
  924.                     /* RTL */
  925.                     return GET_INDEX(start)+runs[i].visualLimit-visualIndex-1;
  926.                 }
  927.             }
  928.         }
  929.     }
  930. }
  931.  
  932. U_CAPI void U_EXPORT2
  933. ubidi_getLogicalMap(UBiDi *pBiDi, UTextOffset *indexMap, UErrorCode *pErrorCode) {
  934.     UBiDiLevel *levels;
  935.  
  936.     /* ubidi_getLevels() checks all of its and our arguments */
  937.     if((levels=(UBiDiLevel *)ubidi_getLevels(pBiDi, pErrorCode))==NULL) {
  938.         /* no op */
  939.     } else if(indexMap==NULL) {
  940.         *pErrorCode=U_ILLEGAL_ARGUMENT_ERROR;
  941.     } else {
  942.         ubidi_reorderLogical(levels, pBiDi->length, indexMap);
  943.     }
  944. }
  945.  
  946. U_CAPI void U_EXPORT2
  947. ubidi_getVisualMap(UBiDi *pBiDi, UTextOffset *indexMap, UErrorCode *pErrorCode) {
  948.     /* ubidi_countRuns() checks all of its and our arguments */
  949.     if(ubidi_countRuns(pBiDi, pErrorCode)<=0) {
  950.         /* no op */
  951.     } else if(indexMap==NULL) {
  952.         *pErrorCode=U_ILLEGAL_ARGUMENT_ERROR;
  953.     } else {
  954.         /* fill a visual-to-logical index map using the runs[] */
  955.         Run *runs=pBiDi->runs, *runsLimit=runs+pBiDi->runCount;
  956.         UTextOffset logicalStart, visualStart, visualLimit;
  957.  
  958.         visualStart=0;
  959.         for(; runs<runsLimit; ++runs) {
  960.             logicalStart=runs->logicalStart;
  961.             visualLimit=runs->visualLimit;
  962.             if(IS_EVEN_RUN(logicalStart)) {
  963.                 do { /* LTR */
  964.                     *indexMap++ = logicalStart++;
  965.                 } while(++visualStart<visualLimit);
  966.             } else {
  967.                 REMOVE_ODD_BIT(logicalStart);
  968.                 logicalStart+=visualLimit-visualStart;  /* logicalLimit */
  969.                 do { /* RTL */
  970.                     *indexMap++ = --logicalStart;
  971.                 } while(++visualStart<visualLimit);
  972.             }
  973.             /* visualStart==visualLimit; */
  974.         }
  975.     }
  976. }
  977.  
  978. U_CAPI void U_EXPORT2
  979. ubidi_invertMap(const UTextOffset *srcMap, UTextOffset *destMap, UTextOffset length) {
  980.     if(srcMap!=NULL && destMap!=NULL) {
  981.         srcMap+=length;
  982.         while(length>0) {
  983.             destMap[*--srcMap]=--length;
  984.         }
  985.     }
  986. }
  987.