1/* 2 * Copyright (c) 2015, 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 ******************************************************************************* 28 * Copyright (C) 2009-2014, International Business Machines Corporation and 29 * others. All Rights Reserved. 30 ******************************************************************************* 31 */ 32 33package sun.text.normalizer; 34 35import java.io.IOException; 36import java.nio.ByteBuffer; 37import java.nio.ByteOrder; 38import java.util.Iterator; 39import java.util.NoSuchElementException; 40 41 42/** 43 * This is the interface and common implementation of a Unicode Trie2. 44 * It is a kind of compressed table that maps from Unicode code points (0..0x10ffff) 45 * to 16- or 32-bit integer values. It works best when there are ranges of 46 * characters with the same value, which is generally the case with Unicode 47 * character properties. 48 * 49 * This is the second common version of a Unicode trie (hence the name Trie2). 50 * 51 */ 52abstract class Trie2 implements Iterable<Trie2.Range> { 53 54 /** 55 * Create a Trie2 from its serialized form. Inverse of utrie2_serialize(). 56 * 57 * Reads from the current position and leaves the buffer after the end of the trie. 58 * 59 * The serialized format is identical between ICU4C and ICU4J, so this function 60 * will work with serialized Trie2s from either. 61 * 62 * The actual type of the returned Trie2 will be either Trie2_16 or Trie2_32, depending 63 * on the width of the data. 64 * 65 * To obtain the width of the Trie2, check the actual class type of the returned Trie2. 66 * Or use the createFromSerialized() function of Trie2_16 or Trie2_32, which will 67 * return only Tries of their specific type/size. 68 * 69 * The serialized Trie2 on the stream may be in either little or big endian byte order. 70 * This allows using serialized Tries from ICU4C without needing to consider the 71 * byte order of the system that created them. 72 * 73 * @param bytes a byte buffer to the serialized form of a UTrie2. 74 * @return An unserialized Trie2, ready for use. 75 * @throws IllegalArgumentException if the stream does not contain a serialized Trie2. 76 * @throws IOException if a read error occurs in the buffer. 77 * 78 */ 79 public static Trie2 createFromSerialized(ByteBuffer bytes) throws IOException { 80 // From ICU4C utrie2_impl.h 81 // * Trie2 data structure in serialized form: 82 // * 83 // * UTrie2Header header; 84 // * uint16_t index[header.index2Length]; 85 // * uint16_t data[header.shiftedDataLength<<2]; -- or uint32_t data[...] 86 // * @internal 87 // */ 88 // typedef struct UTrie2Header { 89 // /** "Tri2" in big-endian US-ASCII (0x54726932) */ 90 // uint32_t signature; 91 92 // /** 93 // * options bit field: 94 // * 15.. 4 reserved (0) 95 // * 3.. 0 UTrie2ValueBits valueBits 96 // */ 97 // uint16_t options; 98 // 99 // /** UTRIE2_INDEX_1_OFFSET..UTRIE2_MAX_INDEX_LENGTH */ 100 // uint16_t indexLength; 101 // 102 // /** (UTRIE2_DATA_START_OFFSET..UTRIE2_MAX_DATA_LENGTH)>>UTRIE2_INDEX_SHIFT */ 103 // uint16_t shiftedDataLength; 104 // 105 // /** Null index and data blocks, not shifted. */ 106 // uint16_t index2NullOffset, dataNullOffset; 107 // 108 // /** 109 // * First code point of the single-value range ending with U+10ffff, 110 // * rounded up and then shifted right by UTRIE2_SHIFT_1. 111 // */ 112 // uint16_t shiftedHighStart; 113 // } UTrie2Header; 114 115 ByteOrder outerByteOrder = bytes.order(); 116 try { 117 UTrie2Header header = new UTrie2Header(); 118 119 /* check the signature */ 120 header.signature = bytes.getInt(); 121 switch (header.signature) { 122 case 0x54726932: 123 // The buffer is already set to the trie data byte order. 124 break; 125 case 0x32697254: 126 // Temporarily reverse the byte order. 127 boolean isBigEndian = outerByteOrder == ByteOrder.BIG_ENDIAN; 128 bytes.order(isBigEndian ? ByteOrder.LITTLE_ENDIAN : ByteOrder.BIG_ENDIAN); 129 header.signature = 0x54726932; 130 break; 131 default: 132 throw new IllegalArgumentException("Buffer does not contain a serialized UTrie2"); 133 } 134 135 header.options = bytes.getChar(); 136 header.indexLength = bytes.getChar(); 137 header.shiftedDataLength = bytes.getChar(); 138 header.index2NullOffset = bytes.getChar(); 139 header.dataNullOffset = bytes.getChar(); 140 header.shiftedHighStart = bytes.getChar(); 141 142 if ((header.options & UTRIE2_OPTIONS_VALUE_BITS_MASK) != 0) { 143 throw new IllegalArgumentException("UTrie2 serialized format error."); 144 } 145 146 Trie2 This; 147 This = new Trie2_16(); 148 This.header = header; 149 150 /* get the length values and offsets */ 151 This.indexLength = header.indexLength; 152 This.dataLength = header.shiftedDataLength << UTRIE2_INDEX_SHIFT; 153 This.index2NullOffset = header.index2NullOffset; 154 This.dataNullOffset = header.dataNullOffset; 155 This.highStart = header.shiftedHighStart << UTRIE2_SHIFT_1; 156 This.highValueIndex = This.dataLength - UTRIE2_DATA_GRANULARITY; 157 This.highValueIndex += This.indexLength; 158 159 // Allocate the Trie2 index array. If the data width is 16 bits, the array also 160 // includes the space for the data. 161 162 int indexArraySize = This.indexLength; 163 indexArraySize += This.dataLength; 164 This.index = new char[indexArraySize]; 165 166 /* Read in the index */ 167 int i; 168 for (i=0; i<This.indexLength; i++) { 169 This.index[i] = bytes.getChar(); 170 } 171 172 /* Read in the data. 16 bit data goes in the same array as the index. 173 * 32 bit data goes in its own separate data array. 174 */ 175 This.data16 = This.indexLength; 176 for (i=0; i<This.dataLength; i++) { 177 This.index[This.data16 + i] = bytes.getChar(); 178 } 179 180 This.data32 = null; 181 This.initialValue = This.index[This.dataNullOffset]; 182 This.errorValue = This.index[This.data16+UTRIE2_BAD_UTF8_DATA_OFFSET]; 183 184 return This; 185 } finally { 186 bytes.order(outerByteOrder); 187 } 188 } 189 190 /** 191 * Get the value for a code point as stored in the Trie2. 192 * 193 * @param codePoint the code point 194 * @return the value 195 */ 196 public abstract int get(int codePoint); 197 198 /** 199 * Get the trie value for a UTF-16 code unit. 200 * 201 * A Trie2 stores two distinct values for input in the lead surrogate 202 * range, one for lead surrogates, which is the value that will be 203 * returned by this function, and a second value that is returned 204 * by Trie2.get(). 205 * 206 * For code units outside of the lead surrogate range, this function 207 * returns the same result as Trie2.get(). 208 * 209 * This function, together with the alternate value for lead surrogates, 210 * makes possible very efficient processing of UTF-16 strings without 211 * first converting surrogate pairs to their corresponding 32 bit code point 212 * values. 213 * 214 * At build-time, enumerate the contents of the Trie2 to see if there 215 * is non-trivial (non-initialValue) data for any of the supplementary 216 * code points associated with a lead surrogate. 217 * If so, then set a special (application-specific) value for the 218 * lead surrogate code _unit_, with Trie2Writable.setForLeadSurrogateCodeUnit(). 219 * 220 * At runtime, use Trie2.getFromU16SingleLead(). If there is non-trivial 221 * data and the code unit is a lead surrogate, then check if a trail surrogate 222 * follows. If so, assemble the supplementary code point and look up its value 223 * with Trie2.get(); otherwise reset the lead 224 * surrogate's value or do a code point lookup for it. 225 * 226 * If there is only trivial data for lead and trail surrogates, then processing 227 * can often skip them. For example, in normalization or case mapping 228 * all characters that do not have any mappings are simply copied as is. 229 * 230 * @param c the code point or lead surrogate value. 231 * @return the value 232 */ 233 public abstract int getFromU16SingleLead(char c); 234 235 /** 236 * When iterating over the contents of a Trie2, Elements of this type are produced. 237 * The iterator will return one item for each contiguous range of codepoints having the same value. 238 * 239 * When iterating, the same Trie2EnumRange object will be reused and returned for each range. 240 * If you need to retain complete iteration results, clone each returned Trie2EnumRange, 241 * or save the range in some other way, before advancing to the next iteration step. 242 */ 243 public static class Range { 244 public int startCodePoint; 245 public int endCodePoint; // Inclusive. 246 public int value; 247 public boolean leadSurrogate; 248 249 public boolean equals(Object other) { 250 if (other == null || !(other.getClass().equals(getClass()))) { 251 return false; 252 } 253 Range tother = (Range)other; 254 return this.startCodePoint == tother.startCodePoint && 255 this.endCodePoint == tother.endCodePoint && 256 this.value == tother.value && 257 this.leadSurrogate == tother.leadSurrogate; 258 } 259 260 public int hashCode() { 261 int h = initHash(); 262 h = hashUChar32(h, startCodePoint); 263 h = hashUChar32(h, endCodePoint); 264 h = hashInt(h, value); 265 h = hashByte(h, leadSurrogate? 1: 0); 266 return h; 267 } 268 } 269 270 /** 271 * Create an iterator over the value ranges in this Trie2. 272 * Values from the Trie2 are not remapped or filtered, but are returned as they 273 * are stored in the Trie2. 274 * 275 * @return an Iterator 276 */ 277 public Iterator<Range> iterator() { 278 return iterator(defaultValueMapper); 279 } 280 281 private static ValueMapper defaultValueMapper = new ValueMapper() { 282 public int map(int in) { 283 return in; 284 } 285 }; 286 287 /** 288 * Create an iterator over the value ranges from this Trie2. 289 * Values from the Trie2 are passed through a caller-supplied remapping function, 290 * and it is the remapped values that determine the ranges that 291 * will be produced by the iterator. 292 * 293 * 294 * @param mapper provides a function to remap values obtained from the Trie2. 295 * @return an Iterator 296 */ 297 public Iterator<Range> iterator(ValueMapper mapper) { 298 return new Trie2Iterator(mapper); 299 } 300 301 /** 302 * When iterating over the contents of a Trie2, an instance of TrieValueMapper may 303 * be used to remap the values from the Trie2. The remapped values will be used 304 * both in determining the ranges of codepoints and as the value to be returned 305 * for each range. 306 * 307 * Example of use, with an anonymous subclass of TrieValueMapper: 308 * 309 * 310 * ValueMapper m = new ValueMapper() { 311 * int map(int in) {return in & 0x1f;}; 312 * } 313 * for (Iterator<Trie2EnumRange> iter = trie.iterator(m); i.hasNext(); ) { 314 * Trie2EnumRange r = i.next(); 315 * ... // Do something with the range r. 316 * } 317 * 318 */ 319 public interface ValueMapper { 320 public int map(int originalVal); 321 } 322 323 //-------------------------------------------------------------------------------- 324 // 325 // Below this point are internal implementation items. No further public API. 326 // 327 //-------------------------------------------------------------------------------- 328 329 /** 330 * Trie2 data structure in serialized form: 331 * 332 * UTrie2Header header; 333 * uint16_t index[header.index2Length]; 334 * uint16_t data[header.shiftedDataLength<<2]; -- or uint32_t data[...] 335 * 336 * For Java, this is read from the stream into an instance of UTrie2Header. 337 * (The C version just places a struct over the raw serialized data.) 338 * 339 * @internal 340 */ 341 static class UTrie2Header { 342 /** "Tri2" in big-endian US-ASCII (0x54726932) */ 343 int signature; 344 345 /** 346 * options bit field (uint16_t): 347 * 15.. 4 reserved (0) 348 * 3.. 0 UTrie2ValueBits valueBits 349 */ 350 int options; 351 352 /** UTRIE2_INDEX_1_OFFSET..UTRIE2_MAX_INDEX_LENGTH (uint16_t) */ 353 int indexLength; 354 355 /** (UTRIE2_DATA_START_OFFSET..UTRIE2_MAX_DATA_LENGTH)>>UTRIE2_INDEX_SHIFT (uint16_t) */ 356 int shiftedDataLength; 357 358 /** Null index and data blocks, not shifted. (uint16_t) */ 359 int index2NullOffset, dataNullOffset; 360 361 /** 362 * First code point of the single-value range ending with U+10ffff, 363 * rounded up and then shifted right by UTRIE2_SHIFT_1. (uint16_t) 364 */ 365 int shiftedHighStart; 366 } 367 368 // 369 // Data members of UTrie2. 370 // 371 UTrie2Header header; 372 char index[]; // Index array. Includes data for 16 bit Tries. 373 int data16; // Offset to data portion of the index array, if 16 bit data. 374 // zero if 32 bit data. 375 int data32[]; // NULL if 16b data is used via index 376 377 int indexLength; 378 int dataLength; 379 int index2NullOffset; // 0xffff if there is no dedicated index-2 null block 380 int initialValue; 381 382 /** Value returned for out-of-range code points and illegal UTF-8. */ 383 int errorValue; 384 385 /* Start of the last range which ends at U+10ffff, and its value. */ 386 int highStart; 387 int highValueIndex; 388 389 int dataNullOffset; 390 391 /** 392 * Trie2 constants, defining shift widths, index array lengths, etc. 393 * 394 * These are needed for the runtime macros but users can treat these as 395 * implementation details and skip to the actual public API further below. 396 */ 397 398 static final int UTRIE2_OPTIONS_VALUE_BITS_MASK=0x000f; 399 400 401 /** Shift size for getting the index-1 table offset. */ 402 static final int UTRIE2_SHIFT_1=6+5; 403 404 /** Shift size for getting the index-2 table offset. */ 405 static final int UTRIE2_SHIFT_2=5; 406 407 /** 408 * Difference between the two shift sizes, 409 * for getting an index-1 offset from an index-2 offset. 6=11-5 410 */ 411 static final int UTRIE2_SHIFT_1_2=UTRIE2_SHIFT_1-UTRIE2_SHIFT_2; 412 413 /** 414 * Number of index-1 entries for the BMP. 32=0x20 415 * This part of the index-1 table is omitted from the serialized form. 416 */ 417 static final int UTRIE2_OMITTED_BMP_INDEX_1_LENGTH=0x10000>>UTRIE2_SHIFT_1; 418 419 /** Number of entries in an index-2 block. 64=0x40 */ 420 static final int UTRIE2_INDEX_2_BLOCK_LENGTH=1<<UTRIE2_SHIFT_1_2; 421 422 /** Mask for getting the lower bits for the in-index-2-block offset. */ 423 static final int UTRIE2_INDEX_2_MASK=UTRIE2_INDEX_2_BLOCK_LENGTH-1; 424 425 /** Number of entries in a data block. 32=0x20 */ 426 static final int UTRIE2_DATA_BLOCK_LENGTH=1<<UTRIE2_SHIFT_2; 427 428 /** Mask for getting the lower bits for the in-data-block offset. */ 429 static final int UTRIE2_DATA_MASK=UTRIE2_DATA_BLOCK_LENGTH-1; 430 431 /** 432 * Shift size for shifting left the index array values. 433 * Increases possible data size with 16-bit index values at the cost 434 * of compactability. 435 * This requires data blocks to be aligned by UTRIE2_DATA_GRANULARITY. 436 */ 437 static final int UTRIE2_INDEX_SHIFT=2; 438 439 /** The alignment size of a data block. Also the granularity for compaction. */ 440 static final int UTRIE2_DATA_GRANULARITY=1<<UTRIE2_INDEX_SHIFT; 441 442 /** 443 * The part of the index-2 table for U+D800..U+DBFF stores values for 444 * lead surrogate code _units_ not code _points_. 445 * Values for lead surrogate code _points_ are indexed with this portion of the table. 446 * Length=32=0x20=0x400>>UTRIE2_SHIFT_2. (There are 1024=0x400 lead surrogates.) 447 */ 448 static final int UTRIE2_LSCP_INDEX_2_OFFSET=0x10000>>UTRIE2_SHIFT_2; 449 static final int UTRIE2_LSCP_INDEX_2_LENGTH=0x400>>UTRIE2_SHIFT_2; 450 451 /** Count the lengths of both BMP pieces. 2080=0x820 */ 452 static final int UTRIE2_INDEX_2_BMP_LENGTH=UTRIE2_LSCP_INDEX_2_OFFSET+UTRIE2_LSCP_INDEX_2_LENGTH; 453 454 /** 455 * The 2-byte UTF-8 version of the index-2 table follows at offset 2080=0x820. 456 * Length 32=0x20 for lead bytes C0..DF, regardless of UTRIE2_SHIFT_2. 457 */ 458 static final int UTRIE2_UTF8_2B_INDEX_2_OFFSET=UTRIE2_INDEX_2_BMP_LENGTH; 459 static final int UTRIE2_UTF8_2B_INDEX_2_LENGTH=0x800>>6; /* U+0800 is the first code point after 2-byte UTF-8 */ 460 461 /** 462 * The index-1 table, only used for supplementary code points, at offset 2112=0x840. 463 * Variable length, for code points up to highStart, where the last single-value range starts. 464 * Maximum length 512=0x200=0x100000>>UTRIE2_SHIFT_1. 465 * (For 0x100000 supplementary code points U+10000..U+10ffff.) 466 * 467 * The part of the index-2 table for supplementary code points starts 468 * after this index-1 table. 469 * 470 * Both the index-1 table and the following part of the index-2 table 471 * are omitted completely if there is only BMP data. 472 */ 473 static final int UTRIE2_INDEX_1_OFFSET=UTRIE2_UTF8_2B_INDEX_2_OFFSET+UTRIE2_UTF8_2B_INDEX_2_LENGTH; 474 475 /** 476 * The illegal-UTF-8 data block follows the ASCII block, at offset 128=0x80. 477 * Used with linear access for single bytes 0..0xbf for simple error handling. 478 * Length 64=0x40, not UTRIE2_DATA_BLOCK_LENGTH. 479 */ 480 static final int UTRIE2_BAD_UTF8_DATA_OFFSET=0x80; 481 482 /** 483 * Implementation class for an iterator over a Trie2. 484 * 485 * Iteration over a Trie2 first returns all of the ranges that are indexed by code points, 486 * then returns the special alternate values for the lead surrogates 487 * 488 * @internal 489 */ 490 class Trie2Iterator implements Iterator<Range> { 491 492 // The normal constructor that configures the iterator to cover the complete 493 // contents of the Trie2 494 Trie2Iterator(ValueMapper vm) { 495 mapper = vm; 496 nextStart = 0; 497 limitCP = 0x110000; 498 doLeadSurrogates = true; 499 } 500 501 /** 502 * The main next() function for Trie2 iterators 503 * 504 */ 505 public Range next() { 506 if (!hasNext()) { 507 throw new NoSuchElementException(); 508 } 509 if (nextStart >= limitCP) { 510 // Switch over from iterating normal code point values to 511 // doing the alternate lead-surrogate values. 512 doingCodePoints = false; 513 nextStart = 0xd800; 514 } 515 int endOfRange = 0; 516 int val = 0; 517 int mappedVal = 0; 518 519 if (doingCodePoints) { 520 // Iteration over code point values. 521 val = get(nextStart); 522 mappedVal = mapper.map(val); 523 endOfRange = rangeEnd(nextStart, limitCP, val); 524 // Loop once for each range in the Trie2 with the same raw (unmapped) value. 525 // Loop continues so long as the mapped values are the same. 526 for (;;) { 527 if (endOfRange >= limitCP-1) { 528 break; 529 } 530 val = get(endOfRange+1); 531 if (mapper.map(val) != mappedVal) { 532 break; 533 } 534 endOfRange = rangeEnd(endOfRange+1, limitCP, val); 535 } 536 } else { 537 // Iteration over the alternate lead surrogate values. 538 val = getFromU16SingleLead((char)nextStart); 539 mappedVal = mapper.map(val); 540 endOfRange = rangeEndLS((char)nextStart); 541 // Loop once for each range in the Trie2 with the same raw (unmapped) value. 542 // Loop continues so long as the mapped values are the same. 543 for (;;) { 544 if (endOfRange >= 0xdbff) { 545 break; 546 } 547 val = getFromU16SingleLead((char)(endOfRange+1)); 548 if (mapper.map(val) != mappedVal) { 549 break; 550 } 551 endOfRange = rangeEndLS((char)(endOfRange+1)); 552 } 553 } 554 returnValue.startCodePoint = nextStart; 555 returnValue.endCodePoint = endOfRange; 556 returnValue.value = mappedVal; 557 returnValue.leadSurrogate = !doingCodePoints; 558 nextStart = endOfRange+1; 559 return returnValue; 560 } 561 562 /** 563 * 564 */ 565 public boolean hasNext() { 566 return doingCodePoints && (doLeadSurrogates || nextStart < limitCP) || nextStart < 0xdc00; 567 } 568 569 private int rangeEndLS(char startingLS) { 570 if (startingLS >= 0xdbff) { 571 return 0xdbff; 572 } 573 574 int c; 575 int val = getFromU16SingleLead(startingLS); 576 for (c = startingLS+1; c <= 0x0dbff; c++) { 577 if (getFromU16SingleLead((char)c) != val) { 578 break; 579 } 580 } 581 return c-1; 582 } 583 584 // 585 // Iteration State Variables 586 // 587 private ValueMapper mapper; 588 private Range returnValue = new Range(); 589 // The starting code point for the next range to be returned. 590 private int nextStart; 591 // The upper limit for the last normal range to be returned. Normally 0x110000, but 592 // may be lower when iterating over the code points for a single lead surrogate. 593 private int limitCP; 594 595 // True while iterating over the the Trie2 values for code points. 596 // False while iterating over the alternate values for lead surrogates. 597 private boolean doingCodePoints = true; 598 599 // True if the iterator should iterate the special values for lead surrogates in 600 // addition to the normal values for code points. 601 private boolean doLeadSurrogates = true; 602 } 603 604 /** 605 * Find the last character in a contiguous range of characters with the 606 * same Trie2 value as the input character. 607 * 608 * @param c The character to begin with. 609 * @return The last contiguous character with the same value. 610 */ 611 int rangeEnd(int start, int limitp, int val) { 612 int c; 613 int limit = Math.min(highStart, limitp); 614 615 for (c = start+1; c < limit; c++) { 616 if (get(c) != val) { 617 break; 618 } 619 } 620 if (c >= highStart) { 621 c = limitp; 622 } 623 return c - 1; 624 } 625 626 627 // 628 // Hashing implementation functions. FNV hash. Respected public domain algorithm. 629 // 630 private static int initHash() { 631 return 0x811c9DC5; // unsigned 2166136261 632 } 633 634 private static int hashByte(int h, int b) { 635 h = h * 16777619; 636 h = h ^ b; 637 return h; 638 } 639 640 private static int hashUChar32(int h, int c) { 641 h = Trie2.hashByte(h, c & 255); 642 h = Trie2.hashByte(h, (c>>8) & 255); 643 h = Trie2.hashByte(h, c>>16); 644 return h; 645 } 646 647 private static int hashInt(int h, int i) { 648 h = Trie2.hashByte(h, i & 255); 649 h = Trie2.hashByte(h, (i>>8) & 255); 650 h = Trie2.hashByte(h, (i>>16) & 255); 651 h = Trie2.hashByte(h, (i>>24) & 255); 652 return h; 653 } 654 655} 656