1 /* 2 * Copyright (c) 2009, Oracle and/or its affiliates. All rights reserved. 3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 4 * 5 * This code is free software; you can redistribute it and/or modify it 6 * under the terms of the GNU General Public License version 2 only, as 7 * published by the Free Software Foundation. Oracle designates this 8 * particular file as subject to the "Classpath" exception as provided 9 * by Oracle in the LICENSE file that accompanied this code. 10 * 11 * This code is distributed in the hope that it will be useful, but WITHOUT 12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 14 * version 2 for more details (a copy is included in the LICENSE file that 15 * accompanied this code). 16 * 17 * You should have received a copy of the GNU General Public License version 18 * 2 along with this work; if not, write to the Free Software Foundation, 19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 20 * 21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 22 * or visit www.oracle.com if you need additional information or have any 23 * questions. 24 */ 25 /* 26 ******************************************************************************* 27 * (C) Copyright IBM Corp. and others, 1996-2009 - All Rights Reserved * 28 * * 29 * The original version of this source code and documentation is copyrighted * 30 * and owned by IBM, These materials are provided under terms of a License * 31 * Agreement between IBM and Sun. This technology is protected by multiple * 32 * US and International patents. This notice and attribution to IBM may not * 33 * to removed. * 34 ******************************************************************************* 35 */ 36 /* Written by Simon Montagu, Matitiahu Allouche 37 * (ported from C code written by Markus W. Scherer) 38 */ 39 40 package sun.text.bidi; 41 42 import java.text.Bidi; 43 import java.util.Arrays; 44 45 public final class BidiLine { 46 47 /* 48 * General remarks about the functions in this file: 49 * 50 * These functions deal with the aspects of potentially mixed-directional 51 * text in a single paragraph or in a line of a single paragraph 52 * which has already been processed according to 53 * the Unicode 3.0 Bidi algorithm as defined in 54 * http://www.unicode.org/unicode/reports/tr9/ , version 13, 55 * also described in The Unicode Standard, Version 4.0.1 . 56 * 57 * This means that there is a Bidi object with a levels 58 * and a dirProps array. 59 * paraLevel and direction are also set. 60 * Only if the length of the text is zero, then levels==dirProps==NULL. 61 * 62 * The overall directionality of the paragraph 63 * or line is used to bypass the reordering steps if possible. 64 * Even purely RTL text does not need reordering there because 65 * the getLogical/VisualIndex() methods can compute the 66 * index on the fly in such a case. 67 * 68 * The implementation of the access to same-level-runs and of the reordering 69 * do attempt to provide better performance and less memory usage compared to 70 * a direct implementation of especially rule (L2) with an array of 71 * one (32-bit) integer per text character. 72 * 73 * Here, the levels array is scanned as soon as necessary, and a vector of 74 * same-level-runs is created. Reordering then is done on this vector. 75 * For each run of text positions that were resolved to the same level, 76 * only 8 bytes are stored: the first text position of the run and the visual 77 * position behind the run after reordering. 78 * One sign bit is used to hold the directionality of the run. 79 * This is inefficient if there are many very short runs. If the average run 80 * length is <2, then this uses more memory. 81 * 82 * In a further attempt to save memory, the levels array is never changed 83 * after all the resolution rules (Xn, Wn, Nn, In). 84 * Many methods have to consider the field trailingWSStart: 85 * if it is less than length, then there is an implicit trailing run 86 * at the paraLevel, 87 * which is not reflected in the levels array. 88 * This allows a line Bidi object to use the same levels array as 89 * its paragraph parent object. 90 * 91 * When a Bidi object is created for a line of a paragraph, then the 92 * paragraph's levels and dirProps arrays are reused by way of setting 93 * a pointer into them, not by copying. This again saves memory and forbids to 94 * change the now shared levels for (L1). 95 */ 96 97 /* handle trailing WS (L1) -------------------------------------------------- */ 98 99 /* 100 * setTrailingWSStart() sets the start index for a trailing 101 * run of WS in the line. This is necessary because we do not modify 102 * the paragraph's levels array that we just point into. 103 * Using trailingWSStart is another form of performing (L1). 104 * 105 * To make subsequent operations easier, we also include the run 106 * before the WS if it is at the paraLevel - we merge the two here. 107 * 108 * This method is called only from setLine(), so paraLevel is 109 * set correctly for the line even when contextual multiple paragraphs. 110 */ 111 112 static void setTrailingWSStart(BidiBase bidiBase) 113 { 114 byte[] dirProps = bidiBase.dirProps; 115 byte[] levels = bidiBase.levels; 116 int start = bidiBase.length; 117 byte paraLevel = bidiBase.paraLevel; 118 119 /* If the line is terminated by a block separator, all preceding WS etc... 120 are already set to paragraph level. 121 Setting trailingWSStart to pBidi->length will avoid changing the 122 level of B chars from 0 to paraLevel in getLevels when 123 orderParagraphsLTR==TRUE 124 */ 125 if (BidiBase.NoContextRTL(dirProps[start - 1]) == BidiBase.B) { 126 bidiBase.trailingWSStart = start; /* currently == bidiBase.length */ 127 return; 128 } 129 /* go backwards across all WS, BN, explicit codes */ 130 while (start > 0 && 131 (BidiBase.DirPropFlagNC(dirProps[start - 1]) & BidiBase.MASK_WS) != 0) { 132 --start; 133 } 134 135 /* if the WS run can be merged with the previous run then do so here */ 136 while (start > 0 && levels[start - 1] == paraLevel) { 137 --start; 138 } 139 140 bidiBase.trailingWSStart=start; 141 } 142 143 public static Bidi setLine(Bidi bidi, BidiBase paraBidi, 144 Bidi newBidi, BidiBase newBidiBase, 145 int start, int limit) { 146 int length; 147 148 BidiBase lineBidi = newBidiBase; 149 150 /* set the values in lineBidi from its paraBidi parent */ 151 /* class members are already initialized to 0 */ 152 // lineBidi.paraBidi = null; /* mark unfinished setLine */ 153 // lineBidi.flags = 0; 154 // lineBidi.controlCount = 0; 155 156 length = lineBidi.length = lineBidi.originalLength = 157 lineBidi.resultLength = limit - start; 158 159 lineBidi.text = new char[length]; 160 System.arraycopy(paraBidi.text, start, lineBidi.text, 0, length); 161 lineBidi.paraLevel = paraBidi.GetParaLevelAt(start); 162 lineBidi.paraCount = paraBidi.paraCount; 163 lineBidi.runs = new BidiRun[0]; 164 if (paraBidi.controlCount > 0) { 165 int j; 166 for (j = start; j < limit; j++) { 167 if (BidiBase.IsBidiControlChar(paraBidi.text[j])) { 168 lineBidi.controlCount++; 169 } 170 } 171 lineBidi.resultLength -= lineBidi.controlCount; 172 } 173 /* copy proper subset of DirProps */ 174 lineBidi.getDirPropsMemory(length); 175 lineBidi.dirProps = lineBidi.dirPropsMemory; 176 System.arraycopy(paraBidi.dirProps, start, lineBidi.dirProps, 0, 177 length); 178 /* copy proper subset of Levels */ 179 lineBidi.getLevelsMemory(length); 180 lineBidi.levels = lineBidi.levelsMemory; 181 System.arraycopy(paraBidi.levels, start, lineBidi.levels, 0, 182 length); 183 lineBidi.runCount = -1; 184 185 if (paraBidi.direction != BidiBase.MIXED) { 186 /* the parent is already trivial */ 187 lineBidi.direction = paraBidi.direction; 188 189 /* 190 * The parent's levels are all either 191 * implicitly or explicitly ==paraLevel; 192 * do the same here. 193 */ 194 if (paraBidi.trailingWSStart <= start) { 195 lineBidi.trailingWSStart = 0; 196 } else if (paraBidi.trailingWSStart < limit) { 197 lineBidi.trailingWSStart = paraBidi.trailingWSStart - start; 198 } else { 199 lineBidi.trailingWSStart = length; 200 } 201 } else { 202 byte[] levels = lineBidi.levels; 203 int i, trailingWSStart; 204 byte level; 205 206 setTrailingWSStart(lineBidi); 207 trailingWSStart = lineBidi.trailingWSStart; 208 209 /* recalculate lineBidi.direction */ 210 if (trailingWSStart == 0) { 211 /* all levels are at paraLevel */ 212 lineBidi.direction = (byte)(lineBidi.paraLevel & 1); 213 } else { 214 /* get the level of the first character */ 215 level = (byte)(levels[0] & 1); 216 217 /* if there is anything of a different level, then the line 218 is mixed */ 219 if (trailingWSStart < length && 220 (lineBidi.paraLevel & 1) != level) { 221 /* the trailing WS is at paraLevel, which differs from 222 levels[0] */ 223 lineBidi.direction = BidiBase.MIXED; 224 } else { 225 /* see if levels[1..trailingWSStart-1] have the same 226 direction as levels[0] and paraLevel */ 227 for (i = 1; ; i++) { 228 if (i == trailingWSStart) { 229 /* the direction values match those in level */ 230 lineBidi.direction = level; 231 break; 232 } else if ((levels[i] & 1) != level) { 233 lineBidi.direction = BidiBase.MIXED; 234 break; 235 } 236 } 237 } 238 } 239 240 switch(lineBidi.direction) { 241 case Bidi.DIRECTION_LEFT_TO_RIGHT: 242 /* make sure paraLevel is even */ 243 lineBidi.paraLevel = (byte) 244 ((lineBidi.paraLevel + 1) & ~1); 245 246 /* all levels are implicitly at paraLevel (important for 247 getLevels()) */ 248 lineBidi.trailingWSStart = 0; 249 break; 250 case Bidi.DIRECTION_RIGHT_TO_LEFT: 251 /* make sure paraLevel is odd */ 252 lineBidi.paraLevel |= 1; 253 254 /* all levels are implicitly at paraLevel (important for 255 getLevels()) */ 256 lineBidi.trailingWSStart = 0; 257 break; 258 default: 259 break; 260 } 261 } 262 263 newBidiBase.paraBidi = paraBidi; /* mark successful setLine */ 264 return newBidi; 265 } 266 267 static byte getLevelAt(BidiBase bidiBase, int charIndex) 268 { 269 /* return paraLevel if in the trailing WS run, otherwise the real level */ 270 if (bidiBase.direction != BidiBase.MIXED || charIndex >= bidiBase.trailingWSStart) { 271 return bidiBase.GetParaLevelAt(charIndex); 272 } else { 273 return bidiBase.levels[charIndex]; 274 } 275 } 276 277 static byte[] getLevels(BidiBase bidiBase) 278 { 279 int start = bidiBase.trailingWSStart; 280 int length = bidiBase.length; 281 282 if (start != length) { 283 /* the current levels array does not reflect the WS run */ 284 /* 285 * After the previous if(), we know that the levels array 286 * has an implicit trailing WS run and therefore does not fully 287 * reflect itself all the levels. 288 * This must be a Bidi object for a line, and 289 * we need to create a new levels array. 290 */ 291 /* bidiBase.paraLevel is ok even if contextual multiple paragraphs, 292 since bidiBase is a line object */ 293 Arrays.fill(bidiBase.levels, start, length, bidiBase.paraLevel); 294 295 /* this new levels array is set for the line and reflects the WS run */ 296 bidiBase.trailingWSStart = length; 297 } 298 if (length < bidiBase.levels.length) { 299 byte[] levels = new byte[length]; 300 System.arraycopy(bidiBase.levels, 0, levels, 0, length); 301 return levels; 302 } 303 return bidiBase.levels; 304 } 305 306 static BidiRun getLogicalRun(BidiBase bidiBase, int logicalPosition) 307 { 308 /* this is done based on runs rather than on levels since levels have 309 a special interpretation when REORDER_RUNS_ONLY 310 */ 311 BidiRun newRun = new BidiRun(), iRun; 312 getRuns(bidiBase); 313 int runCount = bidiBase.runCount; 314 int visualStart = 0, logicalLimit = 0; 315 iRun = bidiBase.runs[0]; 316 317 for (int i = 0; i < runCount; i++) { 318 iRun = bidiBase.runs[i]; 319 logicalLimit = iRun.start + iRun.limit - visualStart; 320 if ((logicalPosition >= iRun.start) && 321 (logicalPosition < logicalLimit)) { 322 break; 323 } 324 visualStart = iRun.limit; 325 } 326 newRun.start = iRun.start; 327 newRun.limit = logicalLimit; 328 newRun.level = iRun.level; 329 return newRun; 330 } 331 332 /* in trivial cases there is only one trivial run; called by getRuns() */ 333 private static void getSingleRun(BidiBase bidiBase, byte level) { 334 /* simple, single-run case */ 335 bidiBase.runs = bidiBase.simpleRuns; 336 bidiBase.runCount = 1; 337 338 /* fill and reorder the single run */ 339 bidiBase.runs[0] = new BidiRun(0, bidiBase.length, level); 340 } 341 342 /* reorder the runs array (L2) ---------------------------------------------- */ 343 344 /* 345 * Reorder the same-level runs in the runs array. 346 * Here, runCount>1 and maxLevel>=minLevel>=paraLevel. 347 * All the visualStart fields=logical start before reordering. 348 * The "odd" bits are not set yet. 349 * 350 * Reordering with this data structure lends itself to some handy shortcuts: 351 * 352 * Since each run is moved but not modified, and since at the initial maxLevel 353 * each sequence of same-level runs consists of only one run each, we 354 * don't need to do anything there and can predecrement maxLevel. 355 * In many simple cases, the reordering is thus done entirely in the 356 * index mapping. 357 * Also, reordering occurs only down to the lowest odd level that occurs, 358 * which is minLevel|1. However, if the lowest level itself is odd, then 359 * in the last reordering the sequence of the runs at this level or higher 360 * will be all runs, and we don't need the elaborate loop to search for them. 361 * This is covered by ++minLevel instead of minLevel|=1 followed 362 * by an extra reorder-all after the reorder-some loop. 363 * About a trailing WS run: 364 * Such a run would need special treatment because its level is not 365 * reflected in levels[] if this is not a paragraph object. 366 * Instead, all characters from trailingWSStart on are implicitly at 367 * paraLevel. 368 * However, for all maxLevel>paraLevel, this run will never be reordered 369 * and does not need to be taken into account. maxLevel==paraLevel is only reordered 370 * if minLevel==paraLevel is odd, which is done in the extra segment. 371 * This means that for the main reordering loop we don't need to consider 372 * this run and can --runCount. If it is later part of the all-runs 373 * reordering, then runCount is adjusted accordingly. 374 */ 375 private static void reorderLine(BidiBase bidiBase, byte minLevel, byte maxLevel) { 376 377 /* nothing to do? */ 378 if (maxLevel<=(minLevel|1)) { 379 return; 380 } 381 382 BidiRun[] runs; 383 BidiRun tempRun; 384 byte[] levels; 385 int firstRun, endRun, limitRun, runCount; 386 387 /* 388 * Reorder only down to the lowest odd level 389 * and reorder at an odd minLevel in a separate, simpler loop. 390 * See comments above for why minLevel is always incremented. 391 */ 392 ++minLevel; 393 394 runs = bidiBase.runs; 395 levels = bidiBase.levels; 396 runCount = bidiBase.runCount; 397 398 /* do not include the WS run at paraLevel<=old minLevel except in the simple loop */ 399 if (bidiBase.trailingWSStart < bidiBase.length) { 400 --runCount; 401 } 402 403 while (--maxLevel >= minLevel) { 404 firstRun = 0; 405 406 /* loop for all sequences of runs */ 407 for ( ; ; ) { 408 /* look for a sequence of runs that are all at >=maxLevel */ 409 /* look for the first run of such a sequence */ 410 while (firstRun < runCount && levels[runs[firstRun].start] < maxLevel) { 411 ++firstRun; 412 } 413 if (firstRun >= runCount) { 414 break; /* no more such runs */ 415 } 416 417 /* look for the limit run of such a sequence (the run behind it) */ 418 for (limitRun = firstRun; ++limitRun < runCount && 419 levels[runs[limitRun].start]>=maxLevel; ) {} 420 421 /* Swap the entire sequence of runs from firstRun to limitRun-1. */ 422 endRun = limitRun - 1; 423 while (firstRun < endRun) { 424 tempRun = runs[firstRun]; 425 runs[firstRun] = runs[endRun]; 426 runs[endRun] = tempRun; 427 ++firstRun; 428 --endRun; 429 } 430 431 if (limitRun == runCount) { 432 break; /* no more such runs */ 433 } else { 434 firstRun = limitRun + 1; 435 } 436 } 437 } 438 439 /* now do maxLevel==old minLevel (==odd!), see above */ 440 if ((minLevel & 1) == 0) { 441 firstRun = 0; 442 443 /* include the trailing WS run in this complete reordering */ 444 if (bidiBase.trailingWSStart == bidiBase.length) { 445 --runCount; 446 } 447 448 /* Swap the entire sequence of all runs. (endRun==runCount) */ 449 while (firstRun < runCount) { 450 tempRun = runs[firstRun]; 451 runs[firstRun] = runs[runCount]; 452 runs[runCount] = tempRun; 453 ++firstRun; 454 --runCount; 455 } 456 } 457 } 458 459 /* compute the runs array --------------------------------------------------- */ 460 461 static int getRunFromLogicalIndex(BidiBase bidiBase, int logicalIndex) { 462 BidiRun[] runs = bidiBase.runs; 463 int runCount = bidiBase.runCount, visualStart = 0, i, length, logicalStart; 464 465 for (i = 0; i < runCount; i++) { 466 length = runs[i].limit - visualStart; 467 logicalStart = runs[i].start; 468 if ((logicalIndex >= logicalStart) && (logicalIndex < (logicalStart+length))) { 469 return i; 470 } 471 visualStart += length; 472 } 473 /* we should never get here */ 474 throw new IllegalStateException("Internal ICU error in getRunFromLogicalIndex"); 475 } 476 477 /* 478 * Compute the runs array from the levels array. 479 * After getRuns() returns true, runCount is guaranteed to be >0 480 * and the runs are reordered. 481 * Odd-level runs have visualStart on their visual right edge and 482 * they progress visually to the left. 483 * If option OPTION_INSERT_MARKS is set, insertRemove will contain the 484 * sum of appropriate LRM/RLM_BEFORE/AFTER flags. 485 * If option OPTION_REMOVE_CONTROLS is set, insertRemove will contain the 486 * negative number of BiDi control characters within this run. 487 */ 488 static void getRuns(BidiBase bidiBase) { 489 /* 490 * This method returns immediately if the runs are already set. This 491 * includes the case of length==0 (handled in setPara).. 492 */ 493 if (bidiBase.runCount >= 0) { 494 return; 495 } 496 if (bidiBase.direction != BidiBase.MIXED) { 497 /* simple, single-run case - this covers length==0 */ 498 /* bidiBase.paraLevel is ok even for contextual multiple paragraphs */ 499 getSingleRun(bidiBase, bidiBase.paraLevel); 500 } else /* BidiBase.MIXED, length>0 */ { 501 /* mixed directionality */ 502 int length = bidiBase.length, limit; 503 byte[] levels = bidiBase.levels; 504 int i, runCount; 505 byte level = BidiBase.INTERNAL_LEVEL_DEFAULT_LTR; /* initialize with no valid level */ 506 /* 507 * If there are WS characters at the end of the line 508 * and the run preceding them has a level different from 509 * paraLevel, then they will form their own run at paraLevel (L1). 510 * Count them separately. 511 * We need some special treatment for this in order to not 512 * modify the levels array which a line Bidi object shares 513 * with its paragraph parent and its other line siblings. 514 * In other words, for the trailing WS, it may be 515 * levels[]!=paraLevel but we have to treat it like it were so. 516 */ 517 limit = bidiBase.trailingWSStart; 518 /* count the runs, there is at least one non-WS run, and limit>0 */ 519 runCount = 0; 520 for (i = 0; i < limit; ++i) { 521 /* increment runCount at the start of each run */ 522 if (levels[i] != level) { 523 ++runCount; 524 level = levels[i]; 525 } 526 } 527 528 /* 529 * We don't need to see if the last run can be merged with a trailing 530 * WS run because setTrailingWSStart() would have done that. 531 */ 532 if (runCount == 1 && limit == length) { 533 /* There is only one non-WS run and no trailing WS-run. */ 534 getSingleRun(bidiBase, levels[0]); 535 } else /* runCount>1 || limit<length */ { 536 /* allocate and set the runs */ 537 BidiRun[] runs; 538 int runIndex, start; 539 byte minLevel = BidiBase.MAX_EXPLICIT_LEVEL + 1; 540 byte maxLevel=0; 541 542 /* now, count a (non-mergeable) WS run */ 543 if (limit < length) { 544 ++runCount; 545 } 546 547 /* runCount > 1 */ 548 bidiBase.getRunsMemory(runCount); 549 runs = bidiBase.runsMemory; 550 551 /* set the runs */ 552 /* FOOD FOR THOUGHT: this could be optimized, e.g.: 553 * 464->444, 484->444, 575->555, 595->555 554 * However, that would take longer. Check also how it would 555 * interact with BiDi control removal and inserting Marks. 556 */ 557 runIndex = 0; 558 559 /* search for the run limits and initialize visualLimit values with the run lengths */ 560 i = 0; 561 do { 562 /* prepare this run */ 563 start = i; 564 level = levels[i]; 565 if (level < minLevel) { 566 minLevel = level; 567 } 568 if (level > maxLevel) { 569 maxLevel = level; 570 } 571 572 /* look for the run limit */ 573 while (++i < limit && levels[i] == level) {} 574 575 /* i is another run limit */ 576 runs[runIndex] = new BidiRun(start, i - start, level); 577 ++runIndex; 578 } while (i < limit); 579 580 if (limit < length) { 581 /* there is a separate WS run */ 582 runs[runIndex] = new BidiRun(limit, length - limit, bidiBase.paraLevel); 583 /* For the trailing WS run, bidiBase.paraLevel is ok even 584 if contextual multiple paragraphs. */ 585 if (bidiBase.paraLevel < minLevel) { 586 minLevel = bidiBase.paraLevel; 587 } 588 } 589 590 /* set the object fields */ 591 bidiBase.runs = runs; 592 bidiBase.runCount = runCount; 593 594 reorderLine(bidiBase, minLevel, maxLevel); 595 596 /* now add the direction flags and adjust the visualLimit's to be just that */ 597 /* this loop will also handle the trailing WS run */ 598 limit = 0; 599 for (i = 0; i < runCount; ++i) { 600 runs[i].level = levels[runs[i].start]; 601 limit = (runs[i].limit += limit); 602 } 603 604 /* Set the embedding level for the trailing WS run. */ 605 /* For a RTL paragraph, it will be the *first* run in visual order. */ 606 /* For the trailing WS run, bidiBase.paraLevel is ok even if 607 contextual multiple paragraphs. */ 608 if (runIndex < runCount) { 609 int trailingRun = ((bidiBase.paraLevel & 1) != 0)? 0 : runIndex; 610 runs[trailingRun].level = bidiBase.paraLevel; 611 } 612 } 613 } 614 615 /* handle insert LRM/RLM BEFORE/AFTER run */ 616 if (bidiBase.insertPoints.size > 0) { 617 BidiBase.Point point; 618 int runIndex, ip; 619 for (ip = 0; ip < bidiBase.insertPoints.size; ip++) { 620 point = bidiBase.insertPoints.points[ip]; 621 runIndex = getRunFromLogicalIndex(bidiBase, point.pos); 622 bidiBase.runs[runIndex].insertRemove |= point.flag; 623 } 624 } 625 626 /* handle remove BiDi control characters */ 627 if (bidiBase.controlCount > 0) { 628 int runIndex, ic; 629 char c; 630 for (ic = 0; ic < bidiBase.length; ic++) { 631 c = bidiBase.text[ic]; 632 if (BidiBase.IsBidiControlChar(c)) { 633 runIndex = getRunFromLogicalIndex(bidiBase, ic); 634 bidiBase.runs[runIndex].insertRemove--; 635 } 636 } 637 } 638 } 639 640 static int[] prepareReorder(byte[] levels, byte[] pMinLevel, byte[] pMaxLevel) 641 { 642 int start; 643 byte level, minLevel, maxLevel; 644 645 if (levels == null || levels.length <= 0) { 646 return null; 647 } 648 649 /* determine minLevel and maxLevel */ 650 minLevel = BidiBase.MAX_EXPLICIT_LEVEL + 1; 651 maxLevel = 0; 652 for (start = levels.length; start>0; ) { 653 level = levels[--start]; 654 if (level > BidiBase.MAX_EXPLICIT_LEVEL + 1) { 655 return null; 656 } 657 if (level < minLevel) { 658 minLevel = level; 659 } 660 if (level > maxLevel) { 661 maxLevel = level; 662 } 663 } 664 pMinLevel[0] = minLevel; 665 pMaxLevel[0] = maxLevel; 666 667 /* initialize the index map */ 668 int[] indexMap = new int[levels.length]; 669 for (start = levels.length; start > 0; ) { 670 --start; 671 indexMap[start] = start; 672 } 673 674 return indexMap; 675 } 676 677 static int[] reorderVisual(byte[] levels) 678 { 679 byte[] aMinLevel = new byte[1]; 680 byte[] aMaxLevel = new byte[1]; 681 int start, end, limit, temp; 682 byte minLevel, maxLevel; 683 684 int[] indexMap = prepareReorder(levels, aMinLevel, aMaxLevel); 685 if (indexMap == null) { 686 return null; 687 } 688 689 minLevel = aMinLevel[0]; 690 maxLevel = aMaxLevel[0]; 691 692 /* nothing to do? */ 693 if (minLevel == maxLevel && (minLevel & 1) == 0) { 694 return indexMap; 695 } 696 697 /* reorder only down to the lowest odd level */ 698 minLevel |= 1; 699 700 /* loop maxLevel..minLevel */ 701 do { 702 start = 0; 703 704 /* loop for all sequences of levels to reorder at the current maxLevel */ 705 for ( ; ; ) { 706 /* look for a sequence of levels that are all at >=maxLevel */ 707 /* look for the first index of such a sequence */ 708 while (start < levels.length && levels[start] < maxLevel) { 709 ++start; 710 } 711 if (start >= levels.length) { 712 break; /* no more such runs */ 713 } 714 715 /* look for the limit of such a sequence (the index behind it) */ 716 for (limit = start; ++limit < levels.length && levels[limit] >= maxLevel; ) {} 717 718 /* 719 * Swap the entire interval of indexes from start to limit-1. 720 * We don't need to swap the levels for the purpose of this 721 * algorithm: the sequence of levels that we look at does not 722 * move anyway. 723 */ 724 end = limit - 1; 725 while (start < end) { 726 temp = indexMap[start]; 727 indexMap[start] = indexMap[end]; 728 indexMap[end] = temp; 729 730 ++start; 731 --end; 732 } 733 734 if (limit == levels.length) { 735 break; /* no more such sequences */ 736 } else { 737 start = limit + 1; 738 } 739 } 740 } while (--maxLevel >= minLevel); 741 742 return indexMap; 743 } 744 745 static int[] getVisualMap(BidiBase bidiBase) 746 { 747 /* fill a visual-to-logical index map using the runs[] */ 748 BidiRun[] runs = bidiBase.runs; 749 int logicalStart, visualStart, visualLimit; 750 int allocLength = bidiBase.length > bidiBase.resultLength ? bidiBase.length 751 : bidiBase.resultLength; 752 int[] indexMap = new int[allocLength]; 753 754 visualStart = 0; 755 int idx = 0; 756 for (int j = 0; j < bidiBase.runCount; ++j) { 757 logicalStart = runs[j].start; 758 visualLimit = runs[j].limit; 759 if (runs[j].isEvenRun()) { 760 do { /* LTR */ 761 indexMap[idx++] = logicalStart++; 762 } while (++visualStart < visualLimit); 763 } else { 764 logicalStart += visualLimit - visualStart; /* logicalLimit */ 765 do { /* RTL */ 766 indexMap[idx++] = --logicalStart; 767 } while (++visualStart < visualLimit); 768 } 769 /* visualStart==visualLimit; */ 770 } 771 772 if (bidiBase.insertPoints.size > 0) { 773 int markFound = 0, runCount = bidiBase.runCount; 774 int insertRemove, i, j, k; 775 runs = bidiBase.runs; 776 /* count all inserted marks */ 777 for (i = 0; i < runCount; i++) { 778 insertRemove = runs[i].insertRemove; 779 if ((insertRemove & (BidiBase.LRM_BEFORE|BidiBase.RLM_BEFORE)) > 0) { 780 markFound++; 781 } 782 if ((insertRemove & (BidiBase.LRM_AFTER|BidiBase.RLM_AFTER)) > 0) { 783 markFound++; 784 } 785 } 786 /* move back indexes by number of preceding marks */ 787 k = bidiBase.resultLength; 788 for (i = runCount - 1; i >= 0 && markFound > 0; i--) { 789 insertRemove = runs[i].insertRemove; 790 if ((insertRemove & (BidiBase.LRM_AFTER|BidiBase.RLM_AFTER)) > 0) { 791 indexMap[--k] = BidiBase.MAP_NOWHERE; 792 markFound--; 793 } 794 visualStart = i > 0 ? runs[i-1].limit : 0; 795 for (j = runs[i].limit - 1; j >= visualStart && markFound > 0; j--) { 796 indexMap[--k] = indexMap[j]; 797 } 798 if ((insertRemove & (BidiBase.LRM_BEFORE|BidiBase.RLM_BEFORE)) > 0) { 799 indexMap[--k] = BidiBase.MAP_NOWHERE; 800 markFound--; 801 } 802 } 803 } 804 else if (bidiBase.controlCount > 0) { 805 int runCount = bidiBase.runCount, logicalEnd; 806 int insertRemove, length, i, j, k, m; 807 char uchar; 808 boolean evenRun; 809 runs = bidiBase.runs; 810 visualStart = 0; 811 /* move forward indexes by number of preceding controls */ 812 k = 0; 813 for (i = 0; i < runCount; i++, visualStart += length) { 814 length = runs[i].limit - visualStart; 815 insertRemove = runs[i].insertRemove; 816 /* if no control found yet, nothing to do in this run */ 817 if ((insertRemove == 0) && (k == visualStart)) { 818 k += length; 819 continue; 820 } 821 /* if no control in this run */ 822 if (insertRemove == 0) { 823 visualLimit = runs[i].limit; 824 for (j = visualStart; j < visualLimit; j++) { 825 indexMap[k++] = indexMap[j]; 826 } 827 continue; 828 } 829 logicalStart = runs[i].start; 830 evenRun = runs[i].isEvenRun(); 831 logicalEnd = logicalStart + length - 1; 832 for (j = 0; j < length; j++) { 833 m = evenRun ? logicalStart + j : logicalEnd - j; 834 uchar = bidiBase.text[m]; 835 if (!BidiBase.IsBidiControlChar(uchar)) { 836 indexMap[k++] = m; 837 } 838 } 839 } 840 } 841 if (allocLength == bidiBase.resultLength) { 842 return indexMap; 843 } 844 int[] newMap = new int[bidiBase.resultLength]; 845 System.arraycopy(indexMap, 0, newMap, 0, bidiBase.resultLength); 846 return newMap; 847 } 848 849 }