Debian Codegraph @

src/main/java/io/airlift/slice/SliceUtf8.java

raw
1 /*
2 * Licensed under the Apache License, Version 2.0 (the "License");
3 * you may not use this file except in compliance with the License.
4 * You may obtain a copy of the License at
5 *
6 * http://www.apache.org/licenses/LICENSE-2.0
7 *
8 * Unless required by applicable law or agreed to in writing, software
9 * distributed under the License is distributed on an "AS IS" BASIS,
10 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
11 * See the License for the specific language governing permissions and
12 * limitations under the License.
13 */
14 package io.airlift.slice;
15
16 import java.util.OptionalInt;
17
18 import static io.airlift.slice.Preconditions.checkArgument;
19 import static io.airlift.slice.Preconditions.checkPositionIndex;
20 import static io.airlift.slice.Preconditions.checkPositionIndexes;
21 import static java.lang.Character.MAX_CODE_POINT;
22 import static java.lang.Character.MAX_SURROGATE;
23 import static java.lang.Character.MIN_SURROGATE;
24 import static java.lang.Integer.toHexString;
25
26 /**
27 * Utility methods for UTF-8 encoded slices.
28 */
29 public final class SliceUtf8
30 {
31 private SliceUtf8() {}
32
33 private static final int REPLACEMENT_CODE_POINT = 0xFFFD;
34
35 private static final int TOP_MASK32 = 0x8080_8080;
36 private static final long TOP_MASK64 = 0x8080_8080_8080_8080L;
37
38 private static final int[] LOWER_CODE_POINTS;
39 private static final int[] UPPER_CODE_POINTS;
40 private static final boolean[] WHITESPACE_CODE_POINTS;
41
42 static {
43 LOWER_CODE_POINTS = new int[MAX_CODE_POINT + 1];
44 UPPER_CODE_POINTS = new int[MAX_CODE_POINT + 1];
45 WHITESPACE_CODE_POINTS = new boolean[MAX_CODE_POINT + 1];
46 for (int codePoint = 0; codePoint <= MAX_CODE_POINT; codePoint++) {
47 int type = Character.getType(codePoint);
48 if (type != Character.SURROGATE) {
49 LOWER_CODE_POINTS[codePoint] = Character.toLowerCase(codePoint);
50 UPPER_CODE_POINTS[codePoint] = Character.toUpperCase(codePoint);
51 WHITESPACE_CODE_POINTS[codePoint] = Character.isWhitespace(codePoint);
52 }
53 else {
54 LOWER_CODE_POINTS[codePoint] = REPLACEMENT_CODE_POINT;
55 UPPER_CODE_POINTS[codePoint] = REPLACEMENT_CODE_POINT;
56 WHITESPACE_CODE_POINTS[codePoint] = false;
57 }
58 }
59 }
60
61 /**
62 * Does the slice contain only 7-bit ASCII characters.
63 */
64 public static boolean isAscii(Slice utf8)
65 {
66 int length = utf8.length();
67 int offset = 0;
68
69 // Length rounded to 8 bytes
70 int length8 = length & 0x7FFF_FFF8;
71 for (; offset < length8; offset += 8) {
72 if ((utf8.getLongUnchecked(offset) & TOP_MASK64) != 0) {
73 return false;
74 }
75 }
76 // Enough bytes left for 32 bits?
77 if (offset + 4 < length) {
78 if ((utf8.getIntUnchecked(offset) & TOP_MASK32) != 0) {
79 return false;
80 }
81
82 offset += 4;
83 }
84 // Do the rest one by one
85 for (; offset < length; offset++) {
86 if ((utf8.getByteUnchecked(offset) & 0x80) != 0) {
87 return false;
88 }
89 }
90
91 return true;
92 }
93
94 /**
95 * Counts the code points within UTF-8 encoded slice.
96 * <p>
97 * Note: This method does not explicitly check for valid UTF-8, and may
98 * return incorrect results or throw an exception for invalid UTF-8.
99 */
100 public static int countCodePoints(Slice utf8)
101 {
102 return countCodePoints(utf8, 0, utf8.length());
103 }
104
105 /**
106 * Counts the code points within UTF-8 encoded slice up to {@code length}.
107 * <p>
108 * Note: This method does not explicitly check for valid UTF-8, and may
109 * return incorrect results or throw an exception for invalid UTF-8.
110 */
111 public static int countCodePoints(Slice utf8, int offset, int length)
112 {
113 checkPositionIndexes(offset, offset + length, utf8.length());
114
115 // Quick exit if empty string
116 if (length == 0) {
117 return 0;
118 }
119
120 int continuationBytesCount = 0;
121 // Length rounded to 8 bytes
122 int length8 = length & 0x7FFF_FFF8;
123 for (; offset < length8; offset += 8) {
124 // Count bytes which are NOT the start of a code point
125 continuationBytesCount += countContinuationBytes(utf8.getLongUnchecked(offset));
126 }
127 // Enough bytes left for 32 bits?
128 if (offset + 4 < length) {
129 // Count bytes which are NOT the start of a code point
130 continuationBytesCount += countContinuationBytes(utf8.getIntUnchecked(offset));
131
132 offset += 4;
133 }
134 // Do the rest one by one
135 for (; offset < length; offset++) {
136 // Count bytes which are NOT the start of a code point
137 continuationBytesCount += countContinuationBytes(utf8.getByteUnchecked(offset));
138 }
139
140 assert continuationBytesCount <= length;
141 return length - continuationBytesCount;
142 }
143
144 /**
145 * Gets the substring starting at {@code codePointStart} and extending for
146 * {@code codePointLength} code points.
147 * <p>
148 * Note: This method does not explicitly check for valid UTF-8, and may
149 * return incorrect results or throw an exception for invalid UTF-8.
150 */
151 public static Slice substring(Slice utf8, int codePointStart, int codePointLength)
152 {
153 checkArgument(codePointStart >= 0, "codePointStart is negative");
154 checkArgument(codePointLength >= 0, "codePointLength is negative");
155
156 int indexStart = offsetOfCodePoint(utf8, codePointStart);
157 if (indexStart < 0) {
158 throw new IllegalArgumentException("UTF-8 does not contain " + codePointStart + " code points");
159 }
160 if (codePointLength == 0) {
161 return Slices.EMPTY_SLICE;
162 }
163 int indexEnd = offsetOfCodePoint(utf8, indexStart, codePointLength - 1);
164 if (indexEnd < 0) {
165 throw new IllegalArgumentException("UTF-8 does not contain " + (codePointStart + codePointLength) + " code points");
166 }
167 indexEnd += lengthOfCodePoint(utf8, indexEnd);
168 if (indexEnd > utf8.length()) {
169 throw new InvalidUtf8Exception("UTF-8 is not well formed");
170 }
171 return utf8.slice(indexStart, indexEnd - indexStart);
172 }
173
174 /**
175 * Reverses the slice code point by code point.
176 * <p>
177 * Note: Invalid UTF-8 sequences are copied directly to the output.
178 */
179 public static Slice reverse(Slice utf8)
180 {
181 int length = utf8.length();
182 Slice reverse = Slices.allocate(length);
183
184 int forwardPosition = 0;
185 int reversePosition = length;
186 while (forwardPosition < length) {
187 int codePointLength = lengthOfCodePointSafe(utf8, forwardPosition);
188
189 // backup the reverse pointer
190 reversePosition -= codePointLength;
191 if (reversePosition < 0) {
192 // this should not happen
193 throw new InvalidUtf8Exception("UTF-8 is not well formed");
194 }
195 // copy the character
196 copyUtf8SequenceUnsafe(utf8, forwardPosition, reverse, reversePosition, codePointLength);
197
198 forwardPosition += codePointLength;
199 }
200 return reverse;
201 }
202
203 /**
204 * Converts slice to upper case code point by code point. This method does
205 * not perform perform locale-sensitive, context-sensitive, or one-to-many
206 * mappings required for some languages. Specifically, this will return
207 * incorrect results for Lithuanian, Turkish, and Azeri.
208 * <p>
209 * Note: Invalid UTF-8 sequences are copied directly to the output.
210 */
211 public static Slice toUpperCase(Slice utf8)
212 {
213 return translateCodePoints(utf8, UPPER_CODE_POINTS);
214 }
215
216 /**
217 * Converts slice to lower case code point by code point. This method does
218 * not perform perform locale-sensitive, context-sensitive, or one-to-many
219 * mappings required for some languages. Specifically, this will return
220 * incorrect results for Lithuanian, Turkish, and Azeri.
221 * <p>
222 * Note: Invalid UTF-8 sequences are copied directly to the output.
223 */
224 public static Slice toLowerCase(Slice utf8)
225 {
226 return translateCodePoints(utf8, LOWER_CODE_POINTS);
227 }
228
229 private static Slice translateCodePoints(Slice utf8, int[] codePointTranslationMap)
230 {
231 int length = utf8.length();
232 Slice newUtf8 = Slices.allocate(length);
233
234 int position = 0;
235 int upperPosition = 0;
236 while (position < length) {
237 int codePoint = tryGetCodePointAt(utf8, position);
238 if (codePoint >= 0) {
239 int upperCodePoint = codePointTranslationMap[codePoint];
240
241 // grow slice if necessary
242 int nextUpperPosition = upperPosition + lengthOfCodePoint(upperCodePoint);
243 if (nextUpperPosition > length) {
244 newUtf8 = Slices.ensureSize(newUtf8, nextUpperPosition);
245 }
246
247 // write new byte
248 setCodePointAt(upperCodePoint, newUtf8, upperPosition);
249
250 position += lengthOfCodePoint(codePoint);
251 upperPosition = nextUpperPosition;
252 }
253 else {
254 int skipLength = -codePoint;
255
256 // grow slice if necessary
257 int nextUpperPosition = upperPosition + skipLength;
258 if (nextUpperPosition > length) {
259 newUtf8 = Slices.ensureSize(newUtf8, nextUpperPosition);
260 }
261
262 copyUtf8SequenceUnsafe(utf8, position, newUtf8, upperPosition, skipLength);
263 position += skipLength;
264 upperPosition = nextUpperPosition;
265 }
266 }
267 return newUtf8.slice(0, upperPosition);
268 }
269
270 private static void copyUtf8SequenceUnsafe(Slice source, int sourcePosition, Slice destination, int destinationPosition, int length)
271 {
272 switch (length) {
273 case 1:
274 destination.setByteUnchecked(destinationPosition, source.getByteUnchecked(sourcePosition));
275 break;
276 case 2:
277 destination.setShortUnchecked(destinationPosition, source.getShortUnchecked(sourcePosition));
278 break;
279 case 3:
280 destination.setShortUnchecked(destinationPosition, source.getShortUnchecked(sourcePosition));
281 destination.setByteUnchecked(destinationPosition + 2, source.getByteUnchecked(sourcePosition + 2));
282 break;
283 case 4:
284 destination.setIntUnchecked(destinationPosition, source.getIntUnchecked(sourcePosition));
285 break;
286 case 5:
287 destination.setIntUnchecked(destinationPosition, source.getIntUnchecked(sourcePosition));
288 destination.setByteUnchecked(destinationPosition + 4, source.getByteUnchecked(sourcePosition + 4));
289 break;
290 case 6:
291 destination.setIntUnchecked(destinationPosition, source.getIntUnchecked(sourcePosition));
292 destination.setShortUnchecked(destinationPosition + 4, source.getShortUnchecked(sourcePosition + 4));
293 break;
294 default:
295 throw new IllegalStateException("Invalid code point length " + length);
296 }
297 }
298
299 /**
300 * Removes all white space characters from the left string of the string.
301 * <p>
302 * Note: Invalid UTF-8 sequences are not trimmed.
303 */
304 public static Slice leftTrim(Slice utf8)
305 {
306 int length = utf8.length();
307
308 int position = firstNonWhitespacePosition(utf8);
309 return utf8.slice(position, length - position);
310 }
311
312 private static int firstNonWhitespacePosition(Slice utf8)
313 {
314 int length = utf8.length();
315
316 int position = 0;
317 while (position < length) {
318 int codePoint = tryGetCodePointAt(utf8, position);
319 if (codePoint < 0) {
320 break;
321 }
322 if (!WHITESPACE_CODE_POINTS[codePoint]) {
323 break;
324 }
325 position += lengthOfCodePoint(codePoint);
326 }
327 return position;
328 }
329
330 /**
331 * Removes all white space characters from the right side of the string.
332 * <p>
333 * Note: Invalid UTF-8 sequences are not trimmed.
334 */
335 public static Slice rightTrim(Slice utf8)
336 {
337 int position = lastNonWhitespacePosition(utf8, 0);
338 return utf8.slice(0, position);
339 }
340
341 private static int lastNonWhitespacePosition(Slice utf8, int minPosition)
342 {
343 int length = utf8.length();
344
345 int position = length;
346 while (minPosition < position) {
347 // decode the code point before position if possible
348 int codePoint;
349 byte unsignedByte = utf8.getByte(position - 1);
350 if (!isContinuationByte(unsignedByte)) {
351 codePoint = unsignedByte & 0xFF;
352 }
353 else if (minPosition <= position -2 && !isContinuationByte(utf8.getByte(position - 2))) {
354 codePoint = tryGetCodePointAt(utf8, position - 2);
355 }
356 else if (minPosition <= position -3 && !isContinuationByte(utf8.getByte(position - 3))) {
357 codePoint = tryGetCodePointAt(utf8, position - 3);
358 }
359 else if (minPosition <= position -4 && !isContinuationByte(utf8.getByte(position - 4))) {
360 codePoint = tryGetCodePointAt(utf8, position - 4);
361 }
362 else {
363 break;
364 }
365
366 if (codePoint < 0 || !WHITESPACE_CODE_POINTS[codePoint]) {
367 break;
368 }
369 position -= lengthOfCodePoint(codePoint);
370 }
371 return position;
372 }
373
374 /**
375 * Removes all white space characters from the left and right side of the string.
376 * <p>
377 * Note: Invalid UTF-8 sequences are not trimmed.
378 */
379 public static Slice trim(Slice utf8)
380 {
381 int start = firstNonWhitespacePosition(utf8);
382 int end = lastNonWhitespacePosition(utf8, start);
383 return utf8.slice(start, end - start);
384 }
385
386 public static Slice fixInvalidUtf8(Slice slice)
387 {
388 return fixInvalidUtf8(slice, OptionalInt.of(REPLACEMENT_CODE_POINT));
389 }
390
391 public static Slice fixInvalidUtf8(Slice slice, OptionalInt replacementCodePoint)
392 {
393 if (isAscii(slice)) {
394 return slice;
395 }
396
397 int replacementCodePointValue = -1;
398 int replacementCodePointLength = 0;
399 if (replacementCodePoint.isPresent()) {
400 replacementCodePointValue = replacementCodePoint.getAsInt();
401 replacementCodePointLength = lengthOfCodePoint(replacementCodePointValue);
402 }
403
404 int length = slice.length();
405 Slice utf8 = Slices.allocate(length);
406
407 int dataPosition = 0;
408 int utf8Position = 0;
409 while (dataPosition < length) {
410 int codePoint = tryGetCodePointAt(slice, dataPosition);
411 int codePointLength;
412 if (codePoint >= 0) {
413 codePointLength = lengthOfCodePoint(codePoint);
414 dataPosition += codePointLength;
415 }
416 else {
417 // negative number carries the number of invalid bytes
418 dataPosition += (-codePoint);
419 if (replacementCodePointValue < 0) {
420 continue;
421 }
422 codePoint = replacementCodePointValue;
423 codePointLength = replacementCodePointLength;
424 }
425 utf8 = Slices.ensureSize(utf8, utf8Position + codePointLength);
426 utf8Position += setCodePointAt(codePoint, utf8, utf8Position);
427 }
428 return utf8.slice(0, utf8Position);
429 }
430
431 /**
432 * Tries to get the UTF-8 encoded code point at the {@code position}. A positive
433 * return value means the UTF-8 sequence at the position is valid, and the result
434 * is the code point. A negative return value means the UTF-8 sequence at the
435 * position is invalid, and the length of the invalid sequence is the absolute
436 * value of the result.
437 * @return the code point or negative the number of bytes in the invalid UTF-8 sequence.
438 */
439 public static int tryGetCodePointAt(Slice utf8, int position)
440 {
441 //
442 // Process first byte
443 byte firstByte = utf8.getByte(position);
444
445 int length = lengthOfCodePointFromStartByteSafe(firstByte);
446 if (length < 0) {
447 return length;
448 }
449
450 if (length == 1) {
451 // normal ASCII
452 // 0xxx_xxxx
453 return firstByte;
454 }
455
456 //
457 // Process second byte
458 if (position + 1 >= utf8.length()) {
459 return -1;
460 }
461
462 byte secondByte = utf8.getByteUnchecked(position + 1);
463 if (!isContinuationByte(secondByte)) {
464 return -1;
465 }
466
467 if (length == 2) {
468 // 110x_xxxx 10xx_xxxx
469 return ((firstByte & 0b0001_1111) << 6) |
470 (secondByte & 0b0011_1111);
471 }
472
473 //
474 // Process third byte
475 if (position + 2 >= utf8.length()) {
476 return -2;
477 }
478
479 byte thirdByte = utf8.getByteUnchecked(position + 2);
480 if (!isContinuationByte(thirdByte)) {
481 return -2;
482 }
483
484 if (length == 3) {
485 // 1110_xxxx 10xx_xxxx 10xx_xxxx
486 int codePoint = ((firstByte & 0b0000_1111) << 12) |
487 ((secondByte & 0b0011_1111) << 6) |
488 (thirdByte & 0b0011_1111);
489
490 // surrogates are invalid
491 if (MIN_SURROGATE <= codePoint && codePoint <= MAX_SURROGATE) {
492 return -3;
493 }
494 return codePoint;
495 }
496
497 //
498 // Process forth byte
499 if (position + 3 >= utf8.length()) {
500 return -3;
501 }
502
503 byte forthByte = utf8.getByteUnchecked(position + 3);
504 if (!isContinuationByte(forthByte)) {
505 return -3;
506 }
507
508 if (length == 4) {
509 // 1111_0xxx 10xx_xxxx 10xx_xxxx 10xx_xxxx
510 int codePoint = ((firstByte & 0b0000_0111) << 18) |
511 ((secondByte & 0b0011_1111) << 12) |
512 ((thirdByte & 0b0011_1111) << 6) |
513 (forthByte & 0b0011_1111);
514 // 4 byte code points have a limited valid range
515 if (codePoint < 0x11_0000) {
516 return codePoint;
517 }
518 return -4;
519 }
520
521 //
522 // Process fifth byte
523 if (position + 4 >= utf8.length()) {
524 return -4;
525 }
526
527 byte fifthByte = utf8.getByteUnchecked(position + 4);
528 if (!isContinuationByte(fifthByte)) {
529 return -4;
530 }
531
532 if (length == 5) {
533 // Per RFC3629, UTF-8 is limited to 4 bytes, so more bytes are illegal
534 return -5;
535 }
536
537 //
538 // Process sixth byte
539 if (position + 5 >= utf8.length()) {
540 return -5;
541 }
542
543 byte sixthByte = utf8.getByteUnchecked(position + 5);
544 if (!isContinuationByte(sixthByte)) {
545 return -5;
546 }
547
548 if (length == 6) {
549 // Per RFC3629, UTF-8 is limited to 4 bytes, so more bytes are illegal
550 return -6;
551 }
552
553 // for longer sequence, which can't happen
554 return -1;
555 }
556
557 static int lengthOfCodePointFromStartByteSafe(byte startByte)
558 {
559 int unsignedStartByte = startByte & 0xFF;
560 if (unsignedStartByte < 0b1000_0000) {
561 // normal ASCII
562 // 0xxx_xxxx
563 return 1;
564 }
565 if (unsignedStartByte < 0b1100_0000) {
566 // illegal bytes
567 // 10xx_xxxx
568 return -1;
569 }
570 if (unsignedStartByte < 0b1110_0000) {
571 // 110x_xxxx 10xx_xxxx
572 return 2;
573 }
574 if (unsignedStartByte < 0b1111_0000) {
575 // 1110_xxxx 10xx_xxxx 10xx_xxxx
576 return 3;
577 }
578 if (unsignedStartByte < 0b1111_1000) {
579 // 1111_0xxx 10xx_xxxx 10xx_xxxx 10xx_xxxx
580 return 4;
581 }
582 if (unsignedStartByte < 0b1111_1100) {
583 // 1111_10xx 10xx_xxxx 10xx_xxxx 10xx_xxxx 10xx_xxxx
584 return 5;
585 }
586 if (unsignedStartByte < 0b1111_1110) {
587 // 1111_110x 10xx_xxxx 10xx_xxxx 10xx_xxxx 10xx_xxxx 10xx_xxxx
588 return 6;
589 }
590 return -1;
591 }
592
593 /**
594 * Finds the index of the first byte of the code point at a position, or
595 * {@code -1} if the position is not withing the slice.
596 * <p>
597 * Note: This method does not explicitly check for valid UTF-8, and may
598 * return incorrect results or throw an exception for invalid UTF-8.
599 */
600 public static int offsetOfCodePoint(Slice utf8, int codePointCount)
601 {
602 return offsetOfCodePoint(utf8, 0, codePointCount);
603 }
604
605 /**
606 * Starting from {@code position} bytes in {@code utf8}, finds the
607 * index of the first byte of the code point {@code codePointCount}
608 * in the slice. If the slice does not contain
609 * {@code codePointCount} code points after {@code position}, {@code -1}
610 * is returned.
611 * <p>
612 * Note: This method does not explicitly check for valid UTF-8, and may
613 * return incorrect results or throw an exception for invalid UTF-8.
614 */
615 public static int offsetOfCodePoint(Slice utf8, int position, int codePointCount)
616 {
617 checkPositionIndex(position, utf8.length());
618 checkArgument(codePointCount >= 0, "codePointPosition is negative");
619
620 // Quick exit if we are sure that the position is after the end
621 if (utf8.length() - position <= codePointCount) {
622 return -1;
623 }
624 if (codePointCount == 0) {
625 return position;
626 }
627
628 int correctIndex = codePointCount + position;
629 // Length rounded to 8 bytes
630 int length8 = utf8.length() & 0x7FFF_FFF8;
631 // While we have enough bytes left and we need at least 8 characters process 8 bytes at once
632 while (position < length8 && correctIndex >= position + 8) {
633 // Count bytes which are NOT the start of a code point
634 correctIndex += countContinuationBytes(utf8.getLongUnchecked(position));
635
636 position += 8;
637 }
638 // Length rounded to 4 bytes
639 int length4 = utf8.length() & 0x7FFF_FFFC;
640 // While we have enough bytes left and we need at least 4 characters process 4 bytes at once
641 while (position < length4 && correctIndex >= position + 4) {
642 // Count bytes which are NOT the start of a code point
643 correctIndex += countContinuationBytes(utf8.getIntUnchecked(position));
644
645 position += 4;
646 }
647 // Do the rest one by one, always check the last byte to find the end of the code point
648 while (position < utf8.length()) {
649 // Count bytes which are NOT the start of a code point
650 correctIndex += countContinuationBytes(utf8.getByteUnchecked(position));
651 if (position == correctIndex) {
652 break;
653 }
654
655 position++;
656 }
657
658 if (position == correctIndex && correctIndex < utf8.length()) {
659 return correctIndex;
660 }
661 return -1;
662 }
663
664 /**
665 * Gets the UTF-8 sequence length of the code point at {@code position}.
666 * <p>
667 * Note: This method does not explicitly check for valid UTF-8, and may
668 * return incorrect results or throw an exception for invalid UTF-8.
669 */
670 public static int lengthOfCodePoint(Slice utf8, int position)
671 {
672 return lengthOfCodePointFromStartByte(utf8.getByte(position));
673 }
674
675 /**
676 * Gets the UTF-8 sequence length of the code point at {@code position}.
677 * <p>
678 * Truncated UTF-8 sequences, 5 and 6 byte sequences, and invalid code points
679 * are handled by this method without throwing an exception.
680 */
681 public static int lengthOfCodePointSafe(Slice utf8, int position)
682 {
683 int length = lengthOfCodePointFromStartByteSafe(utf8.getByte(position));
684 if (length < 0) {
685 return -length;
686 }
687
688 if (length == 1 || position + 1 >= utf8.length() || !isContinuationByte(utf8.getByteUnchecked(position + 1))) {
689 return 1;
690 }
691
692 if (length == 2 || position + 2 >= utf8.length() || !isContinuationByte(utf8.getByteUnchecked(position + 2))) {
693 return 2;
694 }
695
696 if (length == 3 || position + 3 >= utf8.length() || !isContinuationByte(utf8.getByteUnchecked(position + 3))) {
697 return 3;
698 }
699
700 if (length == 4 || position + 4 >= utf8.length() || !isContinuationByte(utf8.getByteUnchecked(position + 4))) {
701 return 4;
702 }
703
704 if (length == 5 || position + 5 >= utf8.length() || !isContinuationByte(utf8.getByteUnchecked(position + 5))) {
705 return 5;
706 }
707
708 if (length == 6) {
709 return 6;
710 }
711
712 return 1;
713 }
714
715 /**
716 * Gets the UTF-8 sequence length of the code point.
717 *
718 * @throws InvalidCodePointException if code point is not within a valid range
719 */
720 public static int lengthOfCodePoint(int codePoint)
721 {
722 if (codePoint < 0) {
723 throw new InvalidCodePointException(codePoint);
724 }
725 if (codePoint < 0x80) {
726 // normal ASCII
727 // 0xxx_xxxx
728 return 1;
729 }
730 if (codePoint < 0x800) {
731 return 2;
732 }
733 if (codePoint < 0x1_0000) {
734 return 3;
735 }
736 if (codePoint < 0x11_0000) {
737 return 4;
738 }
739 // Per RFC3629, UTF-8 is limited to 4 bytes, so more bytes are illegal
740 throw new InvalidCodePointException(codePoint);
741 }
742
743 /**
744 * Gets the UTF-8 sequence length using the sequence start byte.
745 * <p>
746 * Note: This method does not explicitly check for valid UTF-8, and may
747 * return incorrect results or throw an exception for invalid UTF-8.
748 */
749 public static int lengthOfCodePointFromStartByte(byte startByte)
750 {
751 int unsignedStartByte = startByte & 0xFF;
752 if (unsignedStartByte < 0x80) {
753 // normal ASCII
754 // 0xxx_xxxx
755 return 1;
756 }
757 if (unsignedStartByte < 0xc0) {
758 // illegal bytes
759 // 10xx_xxxx
760 throw new InvalidUtf8Exception("Illegal start 0x" + toHexString(unsignedStartByte).toUpperCase() + " of code point");
761 }
762 if (unsignedStartByte < 0xe0) {
763 // 110x_xxxx 10xx_xxxx
764 return 2;
765 }
766 if (unsignedStartByte < 0xf0) {
767 // 1110_xxxx 10xx_xxxx 10xx_xxxx
768 return 3;
769 }
770 if (unsignedStartByte < 0xf8) {
771 // 1111_0xxx 10xx_xxxx 10xx_xxxx 10xx_xxxx
772 return 4;
773 }
774 // Per RFC3629, UTF-8 is limited to 4 bytes, so more bytes are illegal
775 throw new InvalidUtf8Exception("Illegal start 0x" + toHexString(unsignedStartByte).toUpperCase() + " of code point");
776 }
777
778 /**
779 * Gets the UTF-8 encoded code point at the {@code position}.
780 * <p>
781 * Note: This method does not explicitly check for valid UTF-8, and may
782 * return incorrect results or throw an exception for invalid UTF-8.
783 */
784 public static int getCodePointAt(Slice utf8, int position)
785 {
786 int unsignedStartByte = utf8.getByte(position) & 0xFF;
787 if (unsignedStartByte < 0x80) {
788 // normal ASCII
789 // 0xxx_xxxx
790 return unsignedStartByte;
791 }
792 if (unsignedStartByte < 0xc0) {
793 // illegal bytes
794 // 10xx_xxxx
795 throw new InvalidUtf8Exception("Illegal start 0x" + toHexString(unsignedStartByte).toUpperCase() + " of code point");
796 }
797 if (unsignedStartByte < 0xe0) {
798 // 110x_xxxx 10xx_xxxx
799 if (position + 1 >= utf8.length()) {
800 throw new InvalidUtf8Exception("UTF-8 sequence truncated");
801 }
802 return ((unsignedStartByte & 0b0001_1111) << 6) |
803 (utf8.getByte(position + 1) & 0b0011_1111);
804 }
805 if (unsignedStartByte < 0xf0) {
806 // 1110_xxxx 10xx_xxxx 10xx_xxxx
807 if (position + 2 >= utf8.length()) {
808 throw new InvalidUtf8Exception("UTF-8 sequence truncated");
809 }
810 return ((unsignedStartByte & 0b0000_1111) << 12) |
811 ((utf8.getByteUnchecked(position + 1) & 0b0011_1111) << 6) |
812 (utf8.getByteUnchecked(position + 2) & 0b0011_1111);
813 }
814 if (unsignedStartByte < 0xf8) {
815 // 1111_0xxx 10xx_xxxx 10xx_xxxx 10xx_xxxx
816 if (position + 3 >= utf8.length()) {
817 throw new InvalidUtf8Exception("UTF-8 sequence truncated");
818 }
819 return ((unsignedStartByte & 0b0000_0111) << 18) |
820 ((utf8.getByteUnchecked(position + 1) & 0b0011_1111) << 12) |
821 ((utf8.getByteUnchecked(position + 2) & 0b0011_1111) << 6) |
822 (utf8.getByteUnchecked(position + 3) & 0b0011_1111);
823 }
824 // Per RFC3629, UTF-8 is limited to 4 bytes, so more bytes are illegal
825 throw new InvalidUtf8Exception("Illegal start 0x" + toHexString(unsignedStartByte).toUpperCase() + " of code point");
826 }
827
828 /**
829 * Gets the UTF-8 encoded code point before the {@code position}.
830 * <p>
831 * Note: This method does not explicitly check for valid UTF-8, and may
832 * return incorrect results or throw an exception for invalid UTF-8.
833 */
834 public static int getCodePointBefore(Slice utf8, int position)
835 {
836 byte unsignedByte = utf8.getByte(position - 1);
837 if (!isContinuationByte(unsignedByte)) {
838 return unsignedByte & 0xFF;
839 }
840 if (!isContinuationByte(utf8.getByte(position - 2))) {
841 return getCodePointAt(utf8, position - 2);
842 }
843 if (!isContinuationByte(utf8.getByte(position - 3))) {
844 return getCodePointAt(utf8, position - 3);
845 }
846 if (!isContinuationByte(utf8.getByte(position - 4))) {
847 return getCodePointAt(utf8, position - 4);
848 }
849
850 // Per RFC3629, UTF-8 is limited to 4 bytes, so more bytes are illegal
851 throw new InvalidUtf8Exception("UTF-8 is not well formed");
852 }
853
854 private static boolean isContinuationByte(byte b)
855 {
856 return (b & 0b1100_0000) == 0b1000_0000;
857 }
858
859 /**
860 * Convert the code point to UTF-8.
861 * <p>
862 *
863 * @throws InvalidCodePointException if code point is not within a valid range
864 */
865 public static Slice codePointToUtf8(int codePoint)
866 {
867 Slice utf8 = Slices.allocate(lengthOfCodePoint(codePoint));
868 setCodePointAt(codePoint, utf8, 0);
869 return utf8;
870 }
871
872 /**
873 * Sets the UTF-8 sequence for code point at the {@code position}.
874 *
875 * @throws InvalidCodePointException if code point is not within a valid range
876 */
877 public static int setCodePointAt(int codePoint, Slice utf8, int position)
878 {
879 if (codePoint < 0) {
880 throw new InvalidCodePointException(codePoint);
881 }
882 if (codePoint < 0x80) {
883 // normal ASCII
884 // 0xxx_xxxx
885 utf8.setByte(position, codePoint);
886 return 1;
887 }
888 if (codePoint < 0x800) {
889 // 110x_xxxx 10xx_xxxx
890 utf8.setByte(position, 0b1100_0000 | (codePoint >>> 6));
891 utf8.setByte(position + 1, 0b1000_0000 | (codePoint & 0b0011_1111));
892 return 2;
893 }
894 if (MIN_SURROGATE <= codePoint && codePoint <= MAX_SURROGATE) {
895 throw new InvalidCodePointException(codePoint);
896 }
897 if (codePoint < 0x1_0000) {
898 // 1110_xxxx 10xx_xxxx 10xx_xxxx
899 utf8.setByte(position, 0b1110_0000 | ((codePoint >>> 12) & 0b0000_1111));
900 utf8.setByte(position + 1, 0b1000_0000 | ((codePoint >>> 6) & 0b0011_1111));
901 utf8.setByte(position + 2, 0b1000_0000 | (codePoint & 0b0011_1111));
902 return 3;
903 }
904 if (codePoint < 0x11_0000) {
905 // 1111_0xxx 10xx_xxxx 10xx_xxxx 10xx_xxxx
906 utf8.setByte(position, 0b1111_0000 | ((codePoint >>> 18) & 0b0000_0111));
907 utf8.setByte(position + 1, 0b1000_0000 | ((codePoint >>> 12) & 0b0011_1111));
908 utf8.setByte(position + 2, 0b1000_0000 | ((codePoint >>> 6) & 0b0011_1111));
909 utf8.setByte(position + 3, 0b1000_0000 | (codePoint & 0b0011_1111));
910 return 4;
911 }
912 // Per RFC3629, UTF-8 is limited to 4 bytes, so more bytes are illegal
913 throw new InvalidCodePointException(codePoint);
914 }
915
916 private static int countContinuationBytes(byte i8)
917 {
918 // see below
919 int value = i8 & 0xff;
920 return (value >>> 7) & (~value >>> 6);
921 }
922
923 private static int countContinuationBytes(int i32)
924 {
925 // see below
926 i32 = ((i32 & TOP_MASK32) >>> 1) & (~i32);
927 return Integer.bitCount(i32);
928 }
929
930 private static int countContinuationBytes(long i64)
931 {
932 // Count the number of bytes that match 0b10xx_xxxx as follows:
933 // 1. Mask off the 8th bit of every byte and shift it into the 7th position.
934 // 2. Then invert the bytes, which turns the 0 in the 7th bit to a one.
935 // 3. And together the restults of step 1 and 2, giving us a one in the 7th
936 // position if the byte matched.
937 // 4. Count the number of bits in the result, which is the number of bytes
938 // that matched.
939 i64 = ((i64 & TOP_MASK64) >>> 1) & (~i64);
940 return Long.bitCount(i64);
941 }
942 }