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
33 package sun.text.normalizer;
34
35 import java.io.IOException;
36 import java.nio.ByteBuffer;
37 import java.nio.ByteOrder;
38 import java.util.Iterator;
39 import 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 */
52 abstract 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 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 }