1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/intl/icu/source/common/ubidiln.c Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,1351 @@
1.4 +/*
1.5 +******************************************************************************
1.6 +*
1.7 +* Copyright (C) 1999-2013, International Business Machines
1.8 +* Corporation and others. All Rights Reserved.
1.9 +*
1.10 +******************************************************************************
1.11 +* file name: ubidiln.c
1.12 +* encoding: US-ASCII
1.13 +* tab size: 8 (not used)
1.14 +* indentation:4
1.15 +*
1.16 +* created on: 1999aug06
1.17 +* created by: Markus W. Scherer, updated by Matitiahu Allouche
1.18 +*/
1.19 +
1.20 +#include "cmemory.h"
1.21 +#include "unicode/utypes.h"
1.22 +#include "unicode/ustring.h"
1.23 +#include "unicode/uchar.h"
1.24 +#include "unicode/ubidi.h"
1.25 +#include "ubidiimp.h"
1.26 +#include "uassert.h"
1.27 +
1.28 +#ifndef U_COMMON_IMPLEMENTATION
1.29 +#error U_COMMON_IMPLEMENTATION not set - must be set for all ICU source files in common/ - see http://userguide.icu-project.org/howtouseicu
1.30 +#endif
1.31 +
1.32 +/*
1.33 + * General remarks about the functions in this file:
1.34 + *
1.35 + * These functions deal with the aspects of potentially mixed-directional
1.36 + * text in a single paragraph or in a line of a single paragraph
1.37 + * which has already been processed according to
1.38 + * the Unicode 6.3 BiDi algorithm as defined in
1.39 + * http://www.unicode.org/unicode/reports/tr9/ , version 28,
1.40 + * also described in The Unicode Standard, Version 6.3.0 .
1.41 + *
1.42 + * This means that there is a UBiDi object with a levels
1.43 + * and a dirProps array.
1.44 + * paraLevel and direction are also set.
1.45 + * Only if the length of the text is zero, then levels==dirProps==NULL.
1.46 + *
1.47 + * The overall directionality of the paragraph
1.48 + * or line is used to bypass the reordering steps if possible.
1.49 + * Even purely RTL text does not need reordering there because
1.50 + * the ubidi_getLogical/VisualIndex() functions can compute the
1.51 + * index on the fly in such a case.
1.52 + *
1.53 + * The implementation of the access to same-level-runs and of the reordering
1.54 + * do attempt to provide better performance and less memory usage compared to
1.55 + * a direct implementation of especially rule (L2) with an array of
1.56 + * one (32-bit) integer per text character.
1.57 + *
1.58 + * Here, the levels array is scanned as soon as necessary, and a vector of
1.59 + * same-level-runs is created. Reordering then is done on this vector.
1.60 + * For each run of text positions that were resolved to the same level,
1.61 + * only 8 bytes are stored: the first text position of the run and the visual
1.62 + * position behind the run after reordering.
1.63 + * One sign bit is used to hold the directionality of the run.
1.64 + * This is inefficient if there are many very short runs. If the average run
1.65 + * length is <2, then this uses more memory.
1.66 + *
1.67 + * In a further attempt to save memory, the levels array is never changed
1.68 + * after all the resolution rules (Xn, Wn, Nn, In).
1.69 + * Many functions have to consider the field trailingWSStart:
1.70 + * if it is less than length, then there is an implicit trailing run
1.71 + * at the paraLevel,
1.72 + * which is not reflected in the levels array.
1.73 + * This allows a line UBiDi object to use the same levels array as
1.74 + * its paragraph parent object.
1.75 + *
1.76 + * When a UBiDi object is created for a line of a paragraph, then the
1.77 + * paragraph's levels and dirProps arrays are reused by way of setting
1.78 + * a pointer into them, not by copying. This again saves memory and forbids to
1.79 + * change the now shared levels for (L1).
1.80 + */
1.81 +
1.82 +/* handle trailing WS (L1) -------------------------------------------------- */
1.83 +
1.84 +/*
1.85 + * setTrailingWSStart() sets the start index for a trailing
1.86 + * run of WS in the line. This is necessary because we do not modify
1.87 + * the paragraph's levels array that we just point into.
1.88 + * Using trailingWSStart is another form of performing (L1).
1.89 + *
1.90 + * To make subsequent operations easier, we also include the run
1.91 + * before the WS if it is at the paraLevel - we merge the two here.
1.92 + *
1.93 + * This function is called only from ubidi_setLine(), so pBiDi->paraLevel is
1.94 + * set correctly for the line even when contextual multiple paragraphs.
1.95 + */
1.96 +static void
1.97 +setTrailingWSStart(UBiDi *pBiDi) {
1.98 + /* pBiDi->direction!=UBIDI_MIXED */
1.99 +
1.100 + const DirProp *dirProps=pBiDi->dirProps;
1.101 + UBiDiLevel *levels=pBiDi->levels;
1.102 + int32_t start=pBiDi->length;
1.103 + UBiDiLevel paraLevel=pBiDi->paraLevel;
1.104 +
1.105 + /* If the line is terminated by a block separator, all preceding WS etc...
1.106 + are already set to paragraph level.
1.107 + Setting trailingWSStart to pBidi->length will avoid changing the
1.108 + level of B chars from 0 to paraLevel in ubidi_getLevels when
1.109 + orderParagraphsLTR==TRUE.
1.110 + */
1.111 + if(dirProps[start-1]==B) {
1.112 + pBiDi->trailingWSStart=start; /* currently == pBiDi->length */
1.113 + return;
1.114 + }
1.115 + /* go backwards across all WS, BN, explicit codes */
1.116 + while(start>0 && DIRPROP_FLAG(PURE_DIRPROP(dirProps[start-1]))&MASK_WS) {
1.117 + --start;
1.118 + }
1.119 +
1.120 + /* if the WS run can be merged with the previous run then do so here */
1.121 + while(start>0 && levels[start-1]==paraLevel) {
1.122 + --start;
1.123 + }
1.124 +
1.125 + pBiDi->trailingWSStart=start;
1.126 +}
1.127 +
1.128 +/* ubidi_setLine ------------------------------------------------------------ */
1.129 +
1.130 +U_CAPI void U_EXPORT2
1.131 +ubidi_setLine(const UBiDi *pParaBiDi,
1.132 + int32_t start, int32_t limit,
1.133 + UBiDi *pLineBiDi,
1.134 + UErrorCode *pErrorCode) {
1.135 + int32_t length;
1.136 +
1.137 + /* check the argument values */
1.138 + RETURN_VOID_IF_NULL_OR_FAILING_ERRCODE(pErrorCode);
1.139 + RETURN_VOID_IF_NOT_VALID_PARA(pParaBiDi, *pErrorCode);
1.140 + RETURN_VOID_IF_BAD_RANGE(start, 0, limit, *pErrorCode);
1.141 + RETURN_VOID_IF_BAD_RANGE(limit, 0, pParaBiDi->length+1, *pErrorCode);
1.142 + if(pLineBiDi==NULL) {
1.143 + *pErrorCode=U_ILLEGAL_ARGUMENT_ERROR;
1.144 + return;
1.145 + }
1.146 + if(ubidi_getParagraph(pParaBiDi, start, NULL, NULL, NULL, pErrorCode) !=
1.147 + ubidi_getParagraph(pParaBiDi, limit-1, NULL, NULL, NULL, pErrorCode)) {
1.148 + /* the line crosses a paragraph boundary */
1.149 + *pErrorCode=U_ILLEGAL_ARGUMENT_ERROR;
1.150 + return;
1.151 + }
1.152 +
1.153 + /* set the values in pLineBiDi from its pParaBiDi parent */
1.154 + pLineBiDi->pParaBiDi=NULL; /* mark unfinished setLine */
1.155 + pLineBiDi->text=pParaBiDi->text+start;
1.156 + length=pLineBiDi->length=limit-start;
1.157 + pLineBiDi->resultLength=pLineBiDi->originalLength=length;
1.158 + pLineBiDi->paraLevel=GET_PARALEVEL(pParaBiDi, start);
1.159 + pLineBiDi->paraCount=pParaBiDi->paraCount;
1.160 + pLineBiDi->runs=NULL;
1.161 + pLineBiDi->flags=0;
1.162 + pLineBiDi->reorderingMode=pParaBiDi->reorderingMode;
1.163 + pLineBiDi->reorderingOptions=pParaBiDi->reorderingOptions;
1.164 + pLineBiDi->controlCount=0;
1.165 + if(pParaBiDi->controlCount>0) {
1.166 + int32_t j;
1.167 + for(j=start; j<limit; j++) {
1.168 + if(IS_BIDI_CONTROL_CHAR(pParaBiDi->text[j])) {
1.169 + pLineBiDi->controlCount++;
1.170 + }
1.171 + }
1.172 + pLineBiDi->resultLength-=pLineBiDi->controlCount;
1.173 + }
1.174 +
1.175 + pLineBiDi->dirProps=pParaBiDi->dirProps+start;
1.176 + pLineBiDi->levels=pParaBiDi->levels+start;
1.177 + pLineBiDi->runCount=-1;
1.178 +
1.179 + if(pParaBiDi->direction!=UBIDI_MIXED) {
1.180 + /* the parent is already trivial */
1.181 + pLineBiDi->direction=pParaBiDi->direction;
1.182 +
1.183 + /*
1.184 + * The parent's levels are all either
1.185 + * implicitly or explicitly ==paraLevel;
1.186 + * do the same here.
1.187 + */
1.188 + if(pParaBiDi->trailingWSStart<=start) {
1.189 + pLineBiDi->trailingWSStart=0;
1.190 + } else if(pParaBiDi->trailingWSStart<limit) {
1.191 + pLineBiDi->trailingWSStart=pParaBiDi->trailingWSStart-start;
1.192 + } else {
1.193 + pLineBiDi->trailingWSStart=length;
1.194 + }
1.195 + } else {
1.196 + const UBiDiLevel *levels=pLineBiDi->levels;
1.197 + int32_t i, trailingWSStart;
1.198 + UBiDiLevel level;
1.199 +
1.200 + setTrailingWSStart(pLineBiDi);
1.201 + trailingWSStart=pLineBiDi->trailingWSStart;
1.202 +
1.203 + /* recalculate pLineBiDi->direction */
1.204 + if(trailingWSStart==0) {
1.205 + /* all levels are at paraLevel */
1.206 + pLineBiDi->direction=(UBiDiDirection)(pLineBiDi->paraLevel&1);
1.207 + } else {
1.208 + /* get the level of the first character */
1.209 + level=(UBiDiLevel)(levels[0]&1);
1.210 +
1.211 + /* if there is anything of a different level, then the line is mixed */
1.212 + if(trailingWSStart<length && (pLineBiDi->paraLevel&1)!=level) {
1.213 + /* the trailing WS is at paraLevel, which differs from levels[0] */
1.214 + pLineBiDi->direction=UBIDI_MIXED;
1.215 + } else {
1.216 + /* see if levels[1..trailingWSStart-1] have the same direction as levels[0] and paraLevel */
1.217 + i=1;
1.218 + for(;;) {
1.219 + if(i==trailingWSStart) {
1.220 + /* the direction values match those in level */
1.221 + pLineBiDi->direction=(UBiDiDirection)level;
1.222 + break;
1.223 + } else if((levels[i]&1)!=level) {
1.224 + pLineBiDi->direction=UBIDI_MIXED;
1.225 + break;
1.226 + }
1.227 + ++i;
1.228 + }
1.229 + }
1.230 + }
1.231 +
1.232 + switch(pLineBiDi->direction) {
1.233 + case UBIDI_LTR:
1.234 + /* make sure paraLevel is even */
1.235 + pLineBiDi->paraLevel=(UBiDiLevel)((pLineBiDi->paraLevel+1)&~1);
1.236 +
1.237 + /* all levels are implicitly at paraLevel (important for ubidi_getLevels()) */
1.238 + pLineBiDi->trailingWSStart=0;
1.239 + break;
1.240 + case UBIDI_RTL:
1.241 + /* make sure paraLevel is odd */
1.242 + pLineBiDi->paraLevel|=1;
1.243 +
1.244 + /* all levels are implicitly at paraLevel (important for ubidi_getLevels()) */
1.245 + pLineBiDi->trailingWSStart=0;
1.246 + break;
1.247 + default:
1.248 + break;
1.249 + }
1.250 + }
1.251 + pLineBiDi->pParaBiDi=pParaBiDi; /* mark successful setLine */
1.252 + return;
1.253 +}
1.254 +
1.255 +U_CAPI UBiDiLevel U_EXPORT2
1.256 +ubidi_getLevelAt(const UBiDi *pBiDi, int32_t charIndex) {
1.257 + /* return paraLevel if in the trailing WS run, otherwise the real level */
1.258 + if(!IS_VALID_PARA_OR_LINE(pBiDi) || charIndex<0 || pBiDi->length<=charIndex) {
1.259 + return 0;
1.260 + } else if(pBiDi->direction!=UBIDI_MIXED || charIndex>=pBiDi->trailingWSStart) {
1.261 + return GET_PARALEVEL(pBiDi, charIndex);
1.262 + } else {
1.263 + return pBiDi->levels[charIndex];
1.264 + }
1.265 +}
1.266 +
1.267 +U_CAPI const UBiDiLevel * U_EXPORT2
1.268 +ubidi_getLevels(UBiDi *pBiDi, UErrorCode *pErrorCode) {
1.269 + int32_t start, length;
1.270 +
1.271 + RETURN_IF_NULL_OR_FAILING_ERRCODE(pErrorCode, NULL);
1.272 + RETURN_IF_NOT_VALID_PARA_OR_LINE(pBiDi, *pErrorCode, NULL);
1.273 + if((length=pBiDi->length)<=0) {
1.274 + *pErrorCode=U_ILLEGAL_ARGUMENT_ERROR;
1.275 + return NULL;
1.276 + }
1.277 + if((start=pBiDi->trailingWSStart)==length) {
1.278 + /* the current levels array reflects the WS run */
1.279 + return pBiDi->levels;
1.280 + }
1.281 +
1.282 + /*
1.283 + * After the previous if(), we know that the levels array
1.284 + * has an implicit trailing WS run and therefore does not fully
1.285 + * reflect itself all the levels.
1.286 + * This must be a UBiDi object for a line, and
1.287 + * we need to create a new levels array.
1.288 + */
1.289 + if(getLevelsMemory(pBiDi, length)) {
1.290 + UBiDiLevel *levels=pBiDi->levelsMemory;
1.291 +
1.292 + if(start>0 && levels!=pBiDi->levels) {
1.293 + uprv_memcpy(levels, pBiDi->levels, start);
1.294 + }
1.295 + /* pBiDi->paraLevel is ok even if contextual multiple paragraphs,
1.296 + since pBidi is a line object */
1.297 + uprv_memset(levels+start, pBiDi->paraLevel, length-start);
1.298 +
1.299 + /* this new levels array is set for the line and reflects the WS run */
1.300 + pBiDi->trailingWSStart=length;
1.301 + return pBiDi->levels=levels;
1.302 + } else {
1.303 + /* out of memory */
1.304 + *pErrorCode=U_MEMORY_ALLOCATION_ERROR;
1.305 + return NULL;
1.306 + }
1.307 +}
1.308 +
1.309 +U_CAPI void U_EXPORT2
1.310 +ubidi_getLogicalRun(const UBiDi *pBiDi, int32_t logicalPosition,
1.311 + int32_t *pLogicalLimit, UBiDiLevel *pLevel) {
1.312 + UErrorCode errorCode;
1.313 + int32_t runCount, visualStart, logicalLimit, logicalFirst, i;
1.314 + Run iRun;
1.315 +
1.316 + errorCode=U_ZERO_ERROR;
1.317 + RETURN_VOID_IF_BAD_RANGE(logicalPosition, 0, pBiDi->length, errorCode);
1.318 + /* ubidi_countRuns will check VALID_PARA_OR_LINE */
1.319 + runCount=ubidi_countRuns((UBiDi *)pBiDi, &errorCode);
1.320 + if(U_FAILURE(errorCode)) {
1.321 + return;
1.322 + }
1.323 + /* this is done based on runs rather than on levels since levels have
1.324 + a special interpretation when UBIDI_REORDER_RUNS_ONLY
1.325 + */
1.326 + visualStart=logicalLimit=0;
1.327 + iRun=pBiDi->runs[0];
1.328 +
1.329 + for(i=0; i<runCount; i++) {
1.330 + iRun = pBiDi->runs[i];
1.331 + logicalFirst=GET_INDEX(iRun.logicalStart);
1.332 + logicalLimit=logicalFirst+iRun.visualLimit-visualStart;
1.333 + if((logicalPosition>=logicalFirst) &&
1.334 + (logicalPosition<logicalLimit)) {
1.335 + break;
1.336 + }
1.337 + visualStart = iRun.visualLimit;
1.338 + }
1.339 + if(pLogicalLimit) {
1.340 + *pLogicalLimit=logicalLimit;
1.341 + }
1.342 + if(pLevel) {
1.343 + if(pBiDi->reorderingMode==UBIDI_REORDER_RUNS_ONLY) {
1.344 + *pLevel=(UBiDiLevel)GET_ODD_BIT(iRun.logicalStart);
1.345 + }
1.346 + else if(pBiDi->direction!=UBIDI_MIXED || logicalPosition>=pBiDi->trailingWSStart) {
1.347 + *pLevel=GET_PARALEVEL(pBiDi, logicalPosition);
1.348 + } else {
1.349 + *pLevel=pBiDi->levels[logicalPosition];
1.350 + }
1.351 + }
1.352 +}
1.353 +
1.354 +/* runs API functions ------------------------------------------------------- */
1.355 +
1.356 +U_CAPI int32_t U_EXPORT2
1.357 +ubidi_countRuns(UBiDi *pBiDi, UErrorCode *pErrorCode) {
1.358 + RETURN_IF_NULL_OR_FAILING_ERRCODE(pErrorCode, -1);
1.359 + RETURN_IF_NOT_VALID_PARA_OR_LINE(pBiDi, *pErrorCode, -1);
1.360 + ubidi_getRuns(pBiDi, pErrorCode);
1.361 + if(U_FAILURE(*pErrorCode)) {
1.362 + return -1;
1.363 + }
1.364 + return pBiDi->runCount;
1.365 +}
1.366 +
1.367 +U_CAPI UBiDiDirection U_EXPORT2
1.368 +ubidi_getVisualRun(UBiDi *pBiDi, int32_t runIndex,
1.369 + int32_t *pLogicalStart, int32_t *pLength)
1.370 +{
1.371 + int32_t start;
1.372 + UErrorCode errorCode = U_ZERO_ERROR;
1.373 + RETURN_IF_NOT_VALID_PARA_OR_LINE(pBiDi, errorCode, UBIDI_LTR);
1.374 + ubidi_getRuns(pBiDi, &errorCode);
1.375 + if(U_FAILURE(errorCode)) {
1.376 + return UBIDI_LTR;
1.377 + }
1.378 + RETURN_IF_BAD_RANGE(runIndex, 0, pBiDi->runCount, errorCode, UBIDI_LTR);
1.379 +
1.380 + start=pBiDi->runs[runIndex].logicalStart;
1.381 + if(pLogicalStart!=NULL) {
1.382 + *pLogicalStart=GET_INDEX(start);
1.383 + }
1.384 + if(pLength!=NULL) {
1.385 + if(runIndex>0) {
1.386 + *pLength=pBiDi->runs[runIndex].visualLimit-
1.387 + pBiDi->runs[runIndex-1].visualLimit;
1.388 + } else {
1.389 + *pLength=pBiDi->runs[0].visualLimit;
1.390 + }
1.391 + }
1.392 + return (UBiDiDirection)GET_ODD_BIT(start);
1.393 +}
1.394 +
1.395 +/* in trivial cases there is only one trivial run; called by ubidi_getRuns() */
1.396 +static void
1.397 +getSingleRun(UBiDi *pBiDi, UBiDiLevel level) {
1.398 + /* simple, single-run case */
1.399 + pBiDi->runs=pBiDi->simpleRuns;
1.400 + pBiDi->runCount=1;
1.401 +
1.402 + /* fill and reorder the single run */
1.403 + pBiDi->runs[0].logicalStart=MAKE_INDEX_ODD_PAIR(0, level);
1.404 + pBiDi->runs[0].visualLimit=pBiDi->length;
1.405 + pBiDi->runs[0].insertRemove=0;
1.406 +}
1.407 +
1.408 +/* reorder the runs array (L2) ---------------------------------------------- */
1.409 +
1.410 +/*
1.411 + * Reorder the same-level runs in the runs array.
1.412 + * Here, runCount>1 and maxLevel>=minLevel>=paraLevel.
1.413 + * All the visualStart fields=logical start before reordering.
1.414 + * The "odd" bits are not set yet.
1.415 + *
1.416 + * Reordering with this data structure lends itself to some handy shortcuts:
1.417 + *
1.418 + * Since each run is moved but not modified, and since at the initial maxLevel
1.419 + * each sequence of same-level runs consists of only one run each, we
1.420 + * don't need to do anything there and can predecrement maxLevel.
1.421 + * In many simple cases, the reordering is thus done entirely in the
1.422 + * index mapping.
1.423 + * Also, reordering occurs only down to the lowest odd level that occurs,
1.424 + * which is minLevel|1. However, if the lowest level itself is odd, then
1.425 + * in the last reordering the sequence of the runs at this level or higher
1.426 + * will be all runs, and we don't need the elaborate loop to search for them.
1.427 + * This is covered by ++minLevel instead of minLevel|=1 followed
1.428 + * by an extra reorder-all after the reorder-some loop.
1.429 + * About a trailing WS run:
1.430 + * Such a run would need special treatment because its level is not
1.431 + * reflected in levels[] if this is not a paragraph object.
1.432 + * Instead, all characters from trailingWSStart on are implicitly at
1.433 + * paraLevel.
1.434 + * However, for all maxLevel>paraLevel, this run will never be reordered
1.435 + * and does not need to be taken into account. maxLevel==paraLevel is only reordered
1.436 + * if minLevel==paraLevel is odd, which is done in the extra segment.
1.437 + * This means that for the main reordering loop we don't need to consider
1.438 + * this run and can --runCount. If it is later part of the all-runs
1.439 + * reordering, then runCount is adjusted accordingly.
1.440 + */
1.441 +static void
1.442 +reorderLine(UBiDi *pBiDi, UBiDiLevel minLevel, UBiDiLevel maxLevel) {
1.443 + Run *runs, tempRun;
1.444 + UBiDiLevel *levels;
1.445 + int32_t firstRun, endRun, limitRun, runCount;
1.446 +
1.447 + /* nothing to do? */
1.448 + if(maxLevel<=(minLevel|1)) {
1.449 + return;
1.450 + }
1.451 +
1.452 + /*
1.453 + * Reorder only down to the lowest odd level
1.454 + * and reorder at an odd minLevel in a separate, simpler loop.
1.455 + * See comments above for why minLevel is always incremented.
1.456 + */
1.457 + ++minLevel;
1.458 +
1.459 + runs=pBiDi->runs;
1.460 + levels=pBiDi->levels;
1.461 + runCount=pBiDi->runCount;
1.462 +
1.463 + /* do not include the WS run at paraLevel<=old minLevel except in the simple loop */
1.464 + if(pBiDi->trailingWSStart<pBiDi->length) {
1.465 + --runCount;
1.466 + }
1.467 +
1.468 + while(--maxLevel>=minLevel) {
1.469 + firstRun=0;
1.470 +
1.471 + /* loop for all sequences of runs */
1.472 + for(;;) {
1.473 + /* look for a sequence of runs that are all at >=maxLevel */
1.474 + /* look for the first run of such a sequence */
1.475 + while(firstRun<runCount && levels[runs[firstRun].logicalStart]<maxLevel) {
1.476 + ++firstRun;
1.477 + }
1.478 + if(firstRun>=runCount) {
1.479 + break; /* no more such runs */
1.480 + }
1.481 +
1.482 + /* look for the limit run of such a sequence (the run behind it) */
1.483 + for(limitRun=firstRun; ++limitRun<runCount && levels[runs[limitRun].logicalStart]>=maxLevel;) {}
1.484 +
1.485 + /* Swap the entire sequence of runs from firstRun to limitRun-1. */
1.486 + endRun=limitRun-1;
1.487 + while(firstRun<endRun) {
1.488 + tempRun = runs[firstRun];
1.489 + runs[firstRun]=runs[endRun];
1.490 + runs[endRun]=tempRun;
1.491 + ++firstRun;
1.492 + --endRun;
1.493 + }
1.494 +
1.495 + if(limitRun==runCount) {
1.496 + break; /* no more such runs */
1.497 + } else {
1.498 + firstRun=limitRun+1;
1.499 + }
1.500 + }
1.501 + }
1.502 +
1.503 + /* now do maxLevel==old minLevel (==odd!), see above */
1.504 + if(!(minLevel&1)) {
1.505 + firstRun=0;
1.506 +
1.507 + /* include the trailing WS run in this complete reordering */
1.508 + if(pBiDi->trailingWSStart==pBiDi->length) {
1.509 + --runCount;
1.510 + }
1.511 +
1.512 + /* Swap the entire sequence of all runs. (endRun==runCount) */
1.513 + while(firstRun<runCount) {
1.514 + tempRun=runs[firstRun];
1.515 + runs[firstRun]=runs[runCount];
1.516 + runs[runCount]=tempRun;
1.517 + ++firstRun;
1.518 + --runCount;
1.519 + }
1.520 + }
1.521 +}
1.522 +
1.523 +/* compute the runs array --------------------------------------------------- */
1.524 +
1.525 +static int32_t getRunFromLogicalIndex(UBiDi *pBiDi, int32_t logicalIndex, UErrorCode *pErrorCode) {
1.526 + Run *runs=pBiDi->runs;
1.527 + int32_t runCount=pBiDi->runCount, visualStart=0, i, length, logicalStart;
1.528 +
1.529 + for(i=0; i<runCount; i++) {
1.530 + length=runs[i].visualLimit-visualStart;
1.531 + logicalStart=GET_INDEX(runs[i].logicalStart);
1.532 + if((logicalIndex>=logicalStart) && (logicalIndex<(logicalStart+length))) {
1.533 + return i;
1.534 + }
1.535 + visualStart+=length;
1.536 + }
1.537 + /* we should never get here */
1.538 + U_ASSERT(FALSE);
1.539 + *pErrorCode = U_INVALID_STATE_ERROR;
1.540 + return 0;
1.541 +}
1.542 +
1.543 +/*
1.544 + * Compute the runs array from the levels array.
1.545 + * After ubidi_getRuns() returns TRUE, runCount is guaranteed to be >0
1.546 + * and the runs are reordered.
1.547 + * Odd-level runs have visualStart on their visual right edge and
1.548 + * they progress visually to the left.
1.549 + * If option UBIDI_OPTION_INSERT_MARKS is set, insertRemove will contain the
1.550 + * sum of appropriate LRM/RLM_BEFORE/AFTER flags.
1.551 + * If option UBIDI_OPTION_REMOVE_CONTROLS is set, insertRemove will contain the
1.552 + * negative number of BiDi control characters within this run.
1.553 + */
1.554 +U_CFUNC UBool
1.555 +ubidi_getRuns(UBiDi *pBiDi, UErrorCode *pErrorCode) {
1.556 + /*
1.557 + * This method returns immediately if the runs are already set. This
1.558 + * includes the case of length==0 (handled in setPara)..
1.559 + */
1.560 + if (pBiDi->runCount>=0) {
1.561 + return TRUE;
1.562 + }
1.563 +
1.564 + if(pBiDi->direction!=UBIDI_MIXED) {
1.565 + /* simple, single-run case - this covers length==0 */
1.566 + /* pBiDi->paraLevel is ok even for contextual multiple paragraphs */
1.567 + getSingleRun(pBiDi, pBiDi->paraLevel);
1.568 + } else /* UBIDI_MIXED, length>0 */ {
1.569 + /* mixed directionality */
1.570 + int32_t length=pBiDi->length, limit;
1.571 + UBiDiLevel *levels=pBiDi->levels;
1.572 + int32_t i, runCount;
1.573 + UBiDiLevel level=UBIDI_DEFAULT_LTR; /* initialize with no valid level */
1.574 + /*
1.575 + * If there are WS characters at the end of the line
1.576 + * and the run preceding them has a level different from
1.577 + * paraLevel, then they will form their own run at paraLevel (L1).
1.578 + * Count them separately.
1.579 + * We need some special treatment for this in order to not
1.580 + * modify the levels array which a line UBiDi object shares
1.581 + * with its paragraph parent and its other line siblings.
1.582 + * In other words, for the trailing WS, it may be
1.583 + * levels[]!=paraLevel but we have to treat it like it were so.
1.584 + */
1.585 + limit=pBiDi->trailingWSStart;
1.586 + /* count the runs, there is at least one non-WS run, and limit>0 */
1.587 + runCount=0;
1.588 + for(i=0; i<limit; ++i) {
1.589 + /* increment runCount at the start of each run */
1.590 + if(levels[i]!=level) {
1.591 + ++runCount;
1.592 + level=levels[i];
1.593 + }
1.594 + }
1.595 +
1.596 + /*
1.597 + * We don't need to see if the last run can be merged with a trailing
1.598 + * WS run because setTrailingWSStart() would have done that.
1.599 + */
1.600 + if(runCount==1 && limit==length) {
1.601 + /* There is only one non-WS run and no trailing WS-run. */
1.602 + getSingleRun(pBiDi, levels[0]);
1.603 + } else /* runCount>1 || limit<length */ {
1.604 + /* allocate and set the runs */
1.605 + Run *runs;
1.606 + int32_t runIndex, start;
1.607 + UBiDiLevel minLevel=UBIDI_MAX_EXPLICIT_LEVEL+1, maxLevel=0;
1.608 +
1.609 + /* now, count a (non-mergeable) WS run */
1.610 + if(limit<length) {
1.611 + ++runCount;
1.612 + }
1.613 +
1.614 + /* runCount>1 */
1.615 + if(getRunsMemory(pBiDi, runCount)) {
1.616 + runs=pBiDi->runsMemory;
1.617 + } else {
1.618 + return FALSE;
1.619 + }
1.620 +
1.621 + /* set the runs */
1.622 + /* FOOD FOR THOUGHT: this could be optimized, e.g.:
1.623 + * 464->444, 484->444, 575->555, 595->555
1.624 + * However, that would take longer. Check also how it would
1.625 + * interact with BiDi control removal and inserting Marks.
1.626 + */
1.627 + runIndex=0;
1.628 +
1.629 + /* search for the run limits and initialize visualLimit values with the run lengths */
1.630 + i=0;
1.631 + do {
1.632 + /* prepare this run */
1.633 + start=i;
1.634 + level=levels[i];
1.635 + if(level<minLevel) {
1.636 + minLevel=level;
1.637 + }
1.638 + if(level>maxLevel) {
1.639 + maxLevel=level;
1.640 + }
1.641 +
1.642 + /* look for the run limit */
1.643 + while(++i<limit && levels[i]==level) {}
1.644 +
1.645 + /* i is another run limit */
1.646 + runs[runIndex].logicalStart=start;
1.647 + runs[runIndex].visualLimit=i-start;
1.648 + runs[runIndex].insertRemove=0;
1.649 + ++runIndex;
1.650 + } while(i<limit);
1.651 +
1.652 + if(limit<length) {
1.653 + /* there is a separate WS run */
1.654 + runs[runIndex].logicalStart=limit;
1.655 + runs[runIndex].visualLimit=length-limit;
1.656 + /* For the trailing WS run, pBiDi->paraLevel is ok even
1.657 + if contextual multiple paragraphs. */
1.658 + if(pBiDi->paraLevel<minLevel) {
1.659 + minLevel=pBiDi->paraLevel;
1.660 + }
1.661 + }
1.662 +
1.663 + /* set the object fields */
1.664 + pBiDi->runs=runs;
1.665 + pBiDi->runCount=runCount;
1.666 +
1.667 + reorderLine(pBiDi, minLevel, maxLevel);
1.668 +
1.669 + /* now add the direction flags and adjust the visualLimit's to be just that */
1.670 + /* this loop will also handle the trailing WS run */
1.671 + limit=0;
1.672 + for(i=0; i<runCount; ++i) {
1.673 + ADD_ODD_BIT_FROM_LEVEL(runs[i].logicalStart, levels[runs[i].logicalStart]);
1.674 + limit+=runs[i].visualLimit;
1.675 + runs[i].visualLimit=limit;
1.676 + }
1.677 +
1.678 + /* Set the "odd" bit for the trailing WS run. */
1.679 + /* For a RTL paragraph, it will be the *first* run in visual order. */
1.680 + /* For the trailing WS run, pBiDi->paraLevel is ok even if
1.681 + contextual multiple paragraphs. */
1.682 + if(runIndex<runCount) {
1.683 + int32_t trailingRun = ((pBiDi->paraLevel & 1) != 0)? 0 : runIndex;
1.684 +
1.685 + ADD_ODD_BIT_FROM_LEVEL(runs[trailingRun].logicalStart, pBiDi->paraLevel);
1.686 + }
1.687 + }
1.688 + }
1.689 +
1.690 + /* handle insert LRM/RLM BEFORE/AFTER run */
1.691 + if(pBiDi->insertPoints.size>0) {
1.692 + Point *point, *start=pBiDi->insertPoints.points,
1.693 + *limit=start+pBiDi->insertPoints.size;
1.694 + int32_t runIndex;
1.695 + for(point=start; point<limit; point++) {
1.696 + runIndex=getRunFromLogicalIndex(pBiDi, point->pos, pErrorCode);
1.697 + pBiDi->runs[runIndex].insertRemove|=point->flag;
1.698 + }
1.699 + }
1.700 +
1.701 + /* handle remove BiDi control characters */
1.702 + if(pBiDi->controlCount>0) {
1.703 + int32_t runIndex;
1.704 + const UChar *start=pBiDi->text, *limit=start+pBiDi->length, *pu;
1.705 + for(pu=start; pu<limit; pu++) {
1.706 + if(IS_BIDI_CONTROL_CHAR(*pu)) {
1.707 + runIndex=getRunFromLogicalIndex(pBiDi, (int32_t)(pu-start), pErrorCode);
1.708 + pBiDi->runs[runIndex].insertRemove--;
1.709 + }
1.710 + }
1.711 + }
1.712 +
1.713 + return TRUE;
1.714 +}
1.715 +
1.716 +static UBool
1.717 +prepareReorder(const UBiDiLevel *levels, int32_t length,
1.718 + int32_t *indexMap,
1.719 + UBiDiLevel *pMinLevel, UBiDiLevel *pMaxLevel) {
1.720 + int32_t start;
1.721 + UBiDiLevel level, minLevel, maxLevel;
1.722 +
1.723 + if(levels==NULL || length<=0) {
1.724 + return FALSE;
1.725 + }
1.726 +
1.727 + /* determine minLevel and maxLevel */
1.728 + minLevel=UBIDI_MAX_EXPLICIT_LEVEL+1;
1.729 + maxLevel=0;
1.730 + for(start=length; start>0;) {
1.731 + level=levels[--start];
1.732 + if(level>UBIDI_MAX_EXPLICIT_LEVEL+1) {
1.733 + return FALSE;
1.734 + }
1.735 + if(level<minLevel) {
1.736 + minLevel=level;
1.737 + }
1.738 + if(level>maxLevel) {
1.739 + maxLevel=level;
1.740 + }
1.741 + }
1.742 + *pMinLevel=minLevel;
1.743 + *pMaxLevel=maxLevel;
1.744 +
1.745 + /* initialize the index map */
1.746 + for(start=length; start>0;) {
1.747 + --start;
1.748 + indexMap[start]=start;
1.749 + }
1.750 +
1.751 + return TRUE;
1.752 +}
1.753 +
1.754 +/* reorder a line based on a levels array (L2) ------------------------------ */
1.755 +
1.756 +U_CAPI void U_EXPORT2
1.757 +ubidi_reorderLogical(const UBiDiLevel *levels, int32_t length, int32_t *indexMap) {
1.758 + int32_t start, limit, sumOfSosEos;
1.759 + UBiDiLevel minLevel = 0, maxLevel = 0;
1.760 +
1.761 + if(indexMap==NULL || !prepareReorder(levels, length, indexMap, &minLevel, &maxLevel)) {
1.762 + return;
1.763 + }
1.764 +
1.765 + /* nothing to do? */
1.766 + if(minLevel==maxLevel && (minLevel&1)==0) {
1.767 + return;
1.768 + }
1.769 +
1.770 + /* reorder only down to the lowest odd level */
1.771 + minLevel|=1;
1.772 +
1.773 + /* loop maxLevel..minLevel */
1.774 + do {
1.775 + start=0;
1.776 +
1.777 + /* loop for all sequences of levels to reorder at the current maxLevel */
1.778 + for(;;) {
1.779 + /* look for a sequence of levels that are all at >=maxLevel */
1.780 + /* look for the first index of such a sequence */
1.781 + while(start<length && levels[start]<maxLevel) {
1.782 + ++start;
1.783 + }
1.784 + if(start>=length) {
1.785 + break; /* no more such sequences */
1.786 + }
1.787 +
1.788 + /* look for the limit of such a sequence (the index behind it) */
1.789 + for(limit=start; ++limit<length && levels[limit]>=maxLevel;) {}
1.790 +
1.791 + /*
1.792 + * sos=start of sequence, eos=end of sequence
1.793 + *
1.794 + * The closed (inclusive) interval from sos to eos includes all the logical
1.795 + * and visual indexes within this sequence. They are logically and
1.796 + * visually contiguous and in the same range.
1.797 + *
1.798 + * For each run, the new visual index=sos+eos-old visual index;
1.799 + * we pre-add sos+eos into sumOfSosEos ->
1.800 + * new visual index=sumOfSosEos-old visual index;
1.801 + */
1.802 + sumOfSosEos=start+limit-1;
1.803 +
1.804 + /* reorder each index in the sequence */
1.805 + do {
1.806 + indexMap[start]=sumOfSosEos-indexMap[start];
1.807 + } while(++start<limit);
1.808 +
1.809 + /* start==limit */
1.810 + if(limit==length) {
1.811 + break; /* no more such sequences */
1.812 + } else {
1.813 + start=limit+1;
1.814 + }
1.815 + }
1.816 + } while(--maxLevel>=minLevel);
1.817 +}
1.818 +
1.819 +U_CAPI void U_EXPORT2
1.820 +ubidi_reorderVisual(const UBiDiLevel *levels, int32_t length, int32_t *indexMap) {
1.821 + int32_t start, end, limit, temp;
1.822 + UBiDiLevel minLevel = 0, maxLevel = 0;
1.823 +
1.824 + if(indexMap==NULL || !prepareReorder(levels, length, indexMap, &minLevel, &maxLevel)) {
1.825 + return;
1.826 + }
1.827 +
1.828 + /* nothing to do? */
1.829 + if(minLevel==maxLevel && (minLevel&1)==0) {
1.830 + return;
1.831 + }
1.832 +
1.833 + /* reorder only down to the lowest odd level */
1.834 + minLevel|=1;
1.835 +
1.836 + /* loop maxLevel..minLevel */
1.837 + do {
1.838 + start=0;
1.839 +
1.840 + /* loop for all sequences of levels to reorder at the current maxLevel */
1.841 + for(;;) {
1.842 + /* look for a sequence of levels that are all at >=maxLevel */
1.843 + /* look for the first index of such a sequence */
1.844 + while(start<length && levels[start]<maxLevel) {
1.845 + ++start;
1.846 + }
1.847 + if(start>=length) {
1.848 + break; /* no more such runs */
1.849 + }
1.850 +
1.851 + /* look for the limit of such a sequence (the index behind it) */
1.852 + for(limit=start; ++limit<length && levels[limit]>=maxLevel;) {}
1.853 +
1.854 + /*
1.855 + * Swap the entire interval of indexes from start to limit-1.
1.856 + * We don't need to swap the levels for the purpose of this
1.857 + * algorithm: the sequence of levels that we look at does not
1.858 + * move anyway.
1.859 + */
1.860 + end=limit-1;
1.861 + while(start<end) {
1.862 + temp=indexMap[start];
1.863 + indexMap[start]=indexMap[end];
1.864 + indexMap[end]=temp;
1.865 +
1.866 + ++start;
1.867 + --end;
1.868 + }
1.869 +
1.870 + if(limit==length) {
1.871 + break; /* no more such sequences */
1.872 + } else {
1.873 + start=limit+1;
1.874 + }
1.875 + }
1.876 + } while(--maxLevel>=minLevel);
1.877 +}
1.878 +
1.879 +/* API functions for logical<->visual mapping ------------------------------- */
1.880 +
1.881 +U_CAPI int32_t U_EXPORT2
1.882 +ubidi_getVisualIndex(UBiDi *pBiDi, int32_t logicalIndex, UErrorCode *pErrorCode) {
1.883 + int32_t visualIndex=UBIDI_MAP_NOWHERE;
1.884 + RETURN_IF_NULL_OR_FAILING_ERRCODE(pErrorCode, -1);
1.885 + RETURN_IF_NOT_VALID_PARA_OR_LINE(pBiDi, *pErrorCode, -1);
1.886 + RETURN_IF_BAD_RANGE(logicalIndex, 0, pBiDi->length, *pErrorCode, -1);
1.887 +
1.888 + /* we can do the trivial cases without the runs array */
1.889 + switch(pBiDi->direction) {
1.890 + case UBIDI_LTR:
1.891 + visualIndex=logicalIndex;
1.892 + break;
1.893 + case UBIDI_RTL:
1.894 + visualIndex=pBiDi->length-logicalIndex-1;
1.895 + break;
1.896 + default:
1.897 + if(!ubidi_getRuns(pBiDi, pErrorCode)) {
1.898 + *pErrorCode=U_MEMORY_ALLOCATION_ERROR;
1.899 + return -1;
1.900 + } else {
1.901 + Run *runs=pBiDi->runs;
1.902 + int32_t i, visualStart=0, offset, length;
1.903 +
1.904 + /* linear search for the run, search on the visual runs */
1.905 + for(i=0; i<pBiDi->runCount; ++i) {
1.906 + length=runs[i].visualLimit-visualStart;
1.907 + offset=logicalIndex-GET_INDEX(runs[i].logicalStart);
1.908 + if(offset>=0 && offset<length) {
1.909 + if(IS_EVEN_RUN(runs[i].logicalStart)) {
1.910 + /* LTR */
1.911 + visualIndex=visualStart+offset;
1.912 + } else {
1.913 + /* RTL */
1.914 + visualIndex=visualStart+length-offset-1;
1.915 + }
1.916 + break; /* exit for loop */
1.917 + }
1.918 + visualStart+=length;
1.919 + }
1.920 + if(i>=pBiDi->runCount) {
1.921 + return UBIDI_MAP_NOWHERE;
1.922 + }
1.923 + }
1.924 + }
1.925 +
1.926 + if(pBiDi->insertPoints.size>0) {
1.927 + /* add the number of added marks until the calculated visual index */
1.928 + Run *runs=pBiDi->runs;
1.929 + int32_t i, length, insertRemove;
1.930 + int32_t visualStart=0, markFound=0;
1.931 + for(i=0; ; i++, visualStart+=length) {
1.932 + length=runs[i].visualLimit-visualStart;
1.933 + insertRemove=runs[i].insertRemove;
1.934 + if(insertRemove & (LRM_BEFORE|RLM_BEFORE)) {
1.935 + markFound++;
1.936 + }
1.937 + /* is it the run containing the visual index? */
1.938 + if(visualIndex<runs[i].visualLimit) {
1.939 + return visualIndex+markFound;
1.940 + }
1.941 + if(insertRemove & (LRM_AFTER|RLM_AFTER)) {
1.942 + markFound++;
1.943 + }
1.944 + }
1.945 + }
1.946 + else if(pBiDi->controlCount>0) {
1.947 + /* subtract the number of controls until the calculated visual index */
1.948 + Run *runs=pBiDi->runs;
1.949 + int32_t i, j, start, limit, length, insertRemove;
1.950 + int32_t visualStart=0, controlFound=0;
1.951 + UChar uchar=pBiDi->text[logicalIndex];
1.952 + /* is the logical index pointing to a control ? */
1.953 + if(IS_BIDI_CONTROL_CHAR(uchar)) {
1.954 + return UBIDI_MAP_NOWHERE;
1.955 + }
1.956 + /* loop on runs */
1.957 + for(i=0; ; i++, visualStart+=length) {
1.958 + length=runs[i].visualLimit-visualStart;
1.959 + insertRemove=runs[i].insertRemove;
1.960 + /* calculated visual index is beyond this run? */
1.961 + if(visualIndex>=runs[i].visualLimit) {
1.962 + controlFound-=insertRemove;
1.963 + continue;
1.964 + }
1.965 + /* calculated visual index must be within current run */
1.966 + if(insertRemove==0) {
1.967 + return visualIndex-controlFound;
1.968 + }
1.969 + if(IS_EVEN_RUN(runs[i].logicalStart)) {
1.970 + /* LTR: check from run start to logical index */
1.971 + start=runs[i].logicalStart;
1.972 + limit=logicalIndex;
1.973 + } else {
1.974 + /* RTL: check from logical index to run end */
1.975 + start=logicalIndex+1;
1.976 + limit=GET_INDEX(runs[i].logicalStart)+length;
1.977 + }
1.978 + for(j=start; j<limit; j++) {
1.979 + uchar=pBiDi->text[j];
1.980 + if(IS_BIDI_CONTROL_CHAR(uchar)) {
1.981 + controlFound++;
1.982 + }
1.983 + }
1.984 + return visualIndex-controlFound;
1.985 + }
1.986 + }
1.987 +
1.988 + return visualIndex;
1.989 +}
1.990 +
1.991 +U_CAPI int32_t U_EXPORT2
1.992 +ubidi_getLogicalIndex(UBiDi *pBiDi, int32_t visualIndex, UErrorCode *pErrorCode) {
1.993 + Run *runs;
1.994 + int32_t i, runCount, start;
1.995 + RETURN_IF_NULL_OR_FAILING_ERRCODE(pErrorCode, -1);
1.996 + RETURN_IF_NOT_VALID_PARA_OR_LINE(pBiDi, *pErrorCode, -1);
1.997 + RETURN_IF_BAD_RANGE(visualIndex, 0, pBiDi->resultLength, *pErrorCode, -1);
1.998 + /* we can do the trivial cases without the runs array */
1.999 + if(pBiDi->insertPoints.size==0 && pBiDi->controlCount==0) {
1.1000 + if(pBiDi->direction==UBIDI_LTR) {
1.1001 + return visualIndex;
1.1002 + }
1.1003 + else if(pBiDi->direction==UBIDI_RTL) {
1.1004 + return pBiDi->length-visualIndex-1;
1.1005 + }
1.1006 + }
1.1007 + if(!ubidi_getRuns(pBiDi, pErrorCode)) {
1.1008 + *pErrorCode=U_MEMORY_ALLOCATION_ERROR;
1.1009 + return -1;
1.1010 + }
1.1011 +
1.1012 + runs=pBiDi->runs;
1.1013 + runCount=pBiDi->runCount;
1.1014 + if(pBiDi->insertPoints.size>0) {
1.1015 + /* handle inserted LRM/RLM */
1.1016 + int32_t markFound=0, insertRemove;
1.1017 + int32_t visualStart=0, length;
1.1018 + runs=pBiDi->runs;
1.1019 + /* subtract number of marks until visual index */
1.1020 + for(i=0; ; i++, visualStart+=length) {
1.1021 + length=runs[i].visualLimit-visualStart;
1.1022 + insertRemove=runs[i].insertRemove;
1.1023 + if(insertRemove&(LRM_BEFORE|RLM_BEFORE)) {
1.1024 + if(visualIndex<=(visualStart+markFound)) {
1.1025 + return UBIDI_MAP_NOWHERE;
1.1026 + }
1.1027 + markFound++;
1.1028 + }
1.1029 + /* is adjusted visual index within this run? */
1.1030 + if(visualIndex<(runs[i].visualLimit+markFound)) {
1.1031 + visualIndex-=markFound;
1.1032 + break;
1.1033 + }
1.1034 + if(insertRemove&(LRM_AFTER|RLM_AFTER)) {
1.1035 + if(visualIndex==(visualStart+length+markFound)) {
1.1036 + return UBIDI_MAP_NOWHERE;
1.1037 + }
1.1038 + markFound++;
1.1039 + }
1.1040 + }
1.1041 + }
1.1042 + else if(pBiDi->controlCount>0) {
1.1043 + /* handle removed BiDi control characters */
1.1044 + int32_t controlFound=0, insertRemove, length;
1.1045 + int32_t logicalStart, logicalEnd, visualStart=0, j, k;
1.1046 + UChar uchar;
1.1047 + UBool evenRun;
1.1048 + /* add number of controls until visual index */
1.1049 + for(i=0; ; i++, visualStart+=length) {
1.1050 + length=runs[i].visualLimit-visualStart;
1.1051 + insertRemove=runs[i].insertRemove;
1.1052 + /* is adjusted visual index beyond current run? */
1.1053 + if(visualIndex>=(runs[i].visualLimit-controlFound+insertRemove)) {
1.1054 + controlFound-=insertRemove;
1.1055 + continue;
1.1056 + }
1.1057 + /* adjusted visual index is within current run */
1.1058 + if(insertRemove==0) {
1.1059 + visualIndex+=controlFound;
1.1060 + break;
1.1061 + }
1.1062 + /* count non-control chars until visualIndex */
1.1063 + logicalStart=runs[i].logicalStart;
1.1064 + evenRun=IS_EVEN_RUN(logicalStart);
1.1065 + REMOVE_ODD_BIT(logicalStart);
1.1066 + logicalEnd=logicalStart+length-1;
1.1067 + for(j=0; j<length; j++) {
1.1068 + k= evenRun ? logicalStart+j : logicalEnd-j;
1.1069 + uchar=pBiDi->text[k];
1.1070 + if(IS_BIDI_CONTROL_CHAR(uchar)) {
1.1071 + controlFound++;
1.1072 + }
1.1073 + if((visualIndex+controlFound)==(visualStart+j)) {
1.1074 + break;
1.1075 + }
1.1076 + }
1.1077 + visualIndex+=controlFound;
1.1078 + break;
1.1079 + }
1.1080 + }
1.1081 + /* handle all cases */
1.1082 + if(runCount<=10) {
1.1083 + /* linear search for the run */
1.1084 + for(i=0; visualIndex>=runs[i].visualLimit; ++i) {}
1.1085 + } else {
1.1086 + /* binary search for the run */
1.1087 + int32_t begin=0, limit=runCount;
1.1088 +
1.1089 + /* the middle if() is guaranteed to find the run, we don't need a loop limit */
1.1090 + for(;;) {
1.1091 + i=(begin+limit)/2;
1.1092 + if(visualIndex>=runs[i].visualLimit) {
1.1093 + begin=i+1;
1.1094 + } else if(i==0 || visualIndex>=runs[i-1].visualLimit) {
1.1095 + break;
1.1096 + } else {
1.1097 + limit=i;
1.1098 + }
1.1099 + }
1.1100 + }
1.1101 +
1.1102 + start=runs[i].logicalStart;
1.1103 + if(IS_EVEN_RUN(start)) {
1.1104 + /* LTR */
1.1105 + /* the offset in runs[i] is visualIndex-runs[i-1].visualLimit */
1.1106 + if(i>0) {
1.1107 + visualIndex-=runs[i-1].visualLimit;
1.1108 + }
1.1109 + return start+visualIndex;
1.1110 + } else {
1.1111 + /* RTL */
1.1112 + return GET_INDEX(start)+runs[i].visualLimit-visualIndex-1;
1.1113 + }
1.1114 +}
1.1115 +
1.1116 +U_CAPI void U_EXPORT2
1.1117 +ubidi_getLogicalMap(UBiDi *pBiDi, int32_t *indexMap, UErrorCode *pErrorCode) {
1.1118 + RETURN_VOID_IF_NULL_OR_FAILING_ERRCODE(pErrorCode);
1.1119 + /* ubidi_countRuns() checks for VALID_PARA_OR_LINE */
1.1120 + ubidi_countRuns(pBiDi, pErrorCode);
1.1121 + if(U_FAILURE(*pErrorCode)) {
1.1122 + /* no op */
1.1123 + } else if(indexMap==NULL) {
1.1124 + *pErrorCode=U_ILLEGAL_ARGUMENT_ERROR;
1.1125 + } else {
1.1126 + /* fill a logical-to-visual index map using the runs[] */
1.1127 + int32_t visualStart, visualLimit, i, j, k;
1.1128 + int32_t logicalStart, logicalLimit;
1.1129 + Run *runs=pBiDi->runs;
1.1130 + if (pBiDi->length<=0) {
1.1131 + return;
1.1132 + }
1.1133 + if (pBiDi->length>pBiDi->resultLength) {
1.1134 + uprv_memset(indexMap, 0xFF, pBiDi->length*sizeof(int32_t));
1.1135 + }
1.1136 +
1.1137 + visualStart=0;
1.1138 + for(j=0; j<pBiDi->runCount; ++j) {
1.1139 + logicalStart=GET_INDEX(runs[j].logicalStart);
1.1140 + visualLimit=runs[j].visualLimit;
1.1141 + if(IS_EVEN_RUN(runs[j].logicalStart)) {
1.1142 + do { /* LTR */
1.1143 + indexMap[logicalStart++]=visualStart++;
1.1144 + } while(visualStart<visualLimit);
1.1145 + } else {
1.1146 + logicalStart+=visualLimit-visualStart; /* logicalLimit */
1.1147 + do { /* RTL */
1.1148 + indexMap[--logicalStart]=visualStart++;
1.1149 + } while(visualStart<visualLimit);
1.1150 + }
1.1151 + /* visualStart==visualLimit; */
1.1152 + }
1.1153 +
1.1154 + if(pBiDi->insertPoints.size>0) {
1.1155 + int32_t markFound=0, runCount=pBiDi->runCount;
1.1156 + int32_t length, insertRemove;
1.1157 + visualStart=0;
1.1158 + /* add number of marks found until each index */
1.1159 + for(i=0; i<runCount; i++, visualStart+=length) {
1.1160 + length=runs[i].visualLimit-visualStart;
1.1161 + insertRemove=runs[i].insertRemove;
1.1162 + if(insertRemove&(LRM_BEFORE|RLM_BEFORE)) {
1.1163 + markFound++;
1.1164 + }
1.1165 + if(markFound>0) {
1.1166 + logicalStart=GET_INDEX(runs[i].logicalStart);
1.1167 + logicalLimit=logicalStart+length;
1.1168 + for(j=logicalStart; j<logicalLimit; j++) {
1.1169 + indexMap[j]+=markFound;
1.1170 + }
1.1171 + }
1.1172 + if(insertRemove&(LRM_AFTER|RLM_AFTER)) {
1.1173 + markFound++;
1.1174 + }
1.1175 + }
1.1176 + }
1.1177 + else if(pBiDi->controlCount>0) {
1.1178 + int32_t controlFound=0, runCount=pBiDi->runCount;
1.1179 + int32_t length, insertRemove;
1.1180 + UBool evenRun;
1.1181 + UChar uchar;
1.1182 + visualStart=0;
1.1183 + /* subtract number of controls found until each index */
1.1184 + for(i=0; i<runCount; i++, visualStart+=length) {
1.1185 + length=runs[i].visualLimit-visualStart;
1.1186 + insertRemove=runs[i].insertRemove;
1.1187 + /* no control found within previous runs nor within this run */
1.1188 + if((controlFound-insertRemove)==0) {
1.1189 + continue;
1.1190 + }
1.1191 + logicalStart=runs[i].logicalStart;
1.1192 + evenRun=IS_EVEN_RUN(logicalStart);
1.1193 + REMOVE_ODD_BIT(logicalStart);
1.1194 + logicalLimit=logicalStart+length;
1.1195 + /* if no control within this run */
1.1196 + if(insertRemove==0) {
1.1197 + for(j=logicalStart; j<logicalLimit; j++) {
1.1198 + indexMap[j]-=controlFound;
1.1199 + }
1.1200 + continue;
1.1201 + }
1.1202 + for(j=0; j<length; j++) {
1.1203 + k= evenRun ? logicalStart+j : logicalLimit-j-1;
1.1204 + uchar=pBiDi->text[k];
1.1205 + if(IS_BIDI_CONTROL_CHAR(uchar)) {
1.1206 + controlFound++;
1.1207 + indexMap[k]=UBIDI_MAP_NOWHERE;
1.1208 + continue;
1.1209 + }
1.1210 + indexMap[k]-=controlFound;
1.1211 + }
1.1212 + }
1.1213 + }
1.1214 + }
1.1215 +}
1.1216 +
1.1217 +U_CAPI void U_EXPORT2
1.1218 +ubidi_getVisualMap(UBiDi *pBiDi, int32_t *indexMap, UErrorCode *pErrorCode) {
1.1219 + RETURN_VOID_IF_NULL_OR_FAILING_ERRCODE(pErrorCode);
1.1220 + if(indexMap==NULL) {
1.1221 + *pErrorCode=U_ILLEGAL_ARGUMENT_ERROR;
1.1222 + return;
1.1223 + }
1.1224 + /* ubidi_countRuns() checks for VALID_PARA_OR_LINE */
1.1225 + ubidi_countRuns(pBiDi, pErrorCode);
1.1226 + if(U_SUCCESS(*pErrorCode)) {
1.1227 + /* fill a visual-to-logical index map using the runs[] */
1.1228 + Run *runs=pBiDi->runs, *runsLimit=runs+pBiDi->runCount;
1.1229 + int32_t logicalStart, visualStart, visualLimit, *pi=indexMap;
1.1230 +
1.1231 + if (pBiDi->resultLength<=0) {
1.1232 + return;
1.1233 + }
1.1234 + visualStart=0;
1.1235 + for(; runs<runsLimit; ++runs) {
1.1236 + logicalStart=runs->logicalStart;
1.1237 + visualLimit=runs->visualLimit;
1.1238 + if(IS_EVEN_RUN(logicalStart)) {
1.1239 + do { /* LTR */
1.1240 + *pi++ = logicalStart++;
1.1241 + } while(++visualStart<visualLimit);
1.1242 + } else {
1.1243 + REMOVE_ODD_BIT(logicalStart);
1.1244 + logicalStart+=visualLimit-visualStart; /* logicalLimit */
1.1245 + do { /* RTL */
1.1246 + *pi++ = --logicalStart;
1.1247 + } while(++visualStart<visualLimit);
1.1248 + }
1.1249 + /* visualStart==visualLimit; */
1.1250 + }
1.1251 +
1.1252 + if(pBiDi->insertPoints.size>0) {
1.1253 + int32_t markFound=0, runCount=pBiDi->runCount;
1.1254 + int32_t insertRemove, i, j, k;
1.1255 + runs=pBiDi->runs;
1.1256 + /* count all inserted marks */
1.1257 + for(i=0; i<runCount; i++) {
1.1258 + insertRemove=runs[i].insertRemove;
1.1259 + if(insertRemove&(LRM_BEFORE|RLM_BEFORE)) {
1.1260 + markFound++;
1.1261 + }
1.1262 + if(insertRemove&(LRM_AFTER|RLM_AFTER)) {
1.1263 + markFound++;
1.1264 + }
1.1265 + }
1.1266 + /* move back indexes by number of preceding marks */
1.1267 + k=pBiDi->resultLength;
1.1268 + for(i=runCount-1; i>=0 && markFound>0; i--) {
1.1269 + insertRemove=runs[i].insertRemove;
1.1270 + if(insertRemove&(LRM_AFTER|RLM_AFTER)) {
1.1271 + indexMap[--k]= UBIDI_MAP_NOWHERE;
1.1272 + markFound--;
1.1273 + }
1.1274 + visualStart= i>0 ? runs[i-1].visualLimit : 0;
1.1275 + for(j=runs[i].visualLimit-1; j>=visualStart && markFound>0; j--) {
1.1276 + indexMap[--k]=indexMap[j];
1.1277 + }
1.1278 + if(insertRemove&(LRM_BEFORE|RLM_BEFORE)) {
1.1279 + indexMap[--k]= UBIDI_MAP_NOWHERE;
1.1280 + markFound--;
1.1281 + }
1.1282 + }
1.1283 + }
1.1284 + else if(pBiDi->controlCount>0) {
1.1285 + int32_t runCount=pBiDi->runCount, logicalEnd;
1.1286 + int32_t insertRemove, length, i, j, k, m;
1.1287 + UChar uchar;
1.1288 + UBool evenRun;
1.1289 + runs=pBiDi->runs;
1.1290 + visualStart=0;
1.1291 + /* move forward indexes by number of preceding controls */
1.1292 + k=0;
1.1293 + for(i=0; i<runCount; i++, visualStart+=length) {
1.1294 + length=runs[i].visualLimit-visualStart;
1.1295 + insertRemove=runs[i].insertRemove;
1.1296 + /* if no control found yet, nothing to do in this run */
1.1297 + if((insertRemove==0)&&(k==visualStart)) {
1.1298 + k+=length;
1.1299 + continue;
1.1300 + }
1.1301 + /* if no control in this run */
1.1302 + if(insertRemove==0) {
1.1303 + visualLimit=runs[i].visualLimit;
1.1304 + for(j=visualStart; j<visualLimit; j++) {
1.1305 + indexMap[k++]=indexMap[j];
1.1306 + }
1.1307 + continue;
1.1308 + }
1.1309 + logicalStart=runs[i].logicalStart;
1.1310 + evenRun=IS_EVEN_RUN(logicalStart);
1.1311 + REMOVE_ODD_BIT(logicalStart);
1.1312 + logicalEnd=logicalStart+length-1;
1.1313 + for(j=0; j<length; j++) {
1.1314 + m= evenRun ? logicalStart+j : logicalEnd-j;
1.1315 + uchar=pBiDi->text[m];
1.1316 + if(!IS_BIDI_CONTROL_CHAR(uchar)) {
1.1317 + indexMap[k++]=m;
1.1318 + }
1.1319 + }
1.1320 + }
1.1321 + }
1.1322 + }
1.1323 +}
1.1324 +
1.1325 +U_CAPI void U_EXPORT2
1.1326 +ubidi_invertMap(const int32_t *srcMap, int32_t *destMap, int32_t length) {
1.1327 + if(srcMap!=NULL && destMap!=NULL && length>0) {
1.1328 + const int32_t *pi;
1.1329 + int32_t destLength=-1, count=0;
1.1330 + /* find highest value and count positive indexes in srcMap */
1.1331 + pi=srcMap+length;
1.1332 + while(pi>srcMap) {
1.1333 + if(*--pi>destLength) {
1.1334 + destLength=*pi;
1.1335 + }
1.1336 + if(*pi>=0) {
1.1337 + count++;
1.1338 + }
1.1339 + }
1.1340 + destLength++; /* add 1 for origin 0 */
1.1341 + if(count<destLength) {
1.1342 + /* we must fill unmatched destMap entries with -1 */
1.1343 + uprv_memset(destMap, 0xFF, destLength*sizeof(int32_t));
1.1344 + }
1.1345 + pi=srcMap+length;
1.1346 + while(length>0) {
1.1347 + if(*--pi>=0) {
1.1348 + destMap[*pi]=--length;
1.1349 + } else {
1.1350 + --length;
1.1351 + }
1.1352 + }
1.1353 + }
1.1354 +}
