src/third_party/protobuf/java/src/main/java/com/google/protobuf/Utf8.java

   1 // Protocol Buffers - Google's data interchange format
   2 // Copyright 2008 Google Inc.  All rights reserved.
   3 // http://code.google.com/p/protobuf/
   4 //
   5 // Redistribution and use in source and binary forms, with or without
   6 // modification, are permitted provided that the following conditions are
   7 // met:
   8 //
   9 //     * Redistributions of source code must retain the above copyright
  10 // notice, this list of conditions and the following disclaimer.
  11 //     * Redistributions in binary form must reproduce the above
  12 // copyright notice, this list of conditions and the following disclaimer
  13 // in the documentation and/or other materials provided with the
  14 // distribution.
  15 //     * Neither the name of Google Inc. nor the names of its
  16 // contributors may be used to endorse or promote products derived from
  17 // this software without specific prior written permission.
  18 //
  19 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  20 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  21 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  22 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  23 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  24 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  25 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  26 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  27 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  28 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  29 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  30
  31 package com.google.protobuf;
  32
  33 /**
  34  * A set of low-level, high-performance static utility methods related
  35  * to the UTF-8 character encoding.  This class has no dependencies
  36  * outside of the core JDK libraries.
  37  *
  38  * <p>There are several variants of UTF-8.  The one implemented by
  39  * this class is the restricted definition of UTF-8 introduced in
  40  * Unicode 3.1, which mandates the rejection of "overlong" byte
  41  * sequences as well as rejection of 3-byte surrogate codepoint byte
  42  * sequences.  Note that the UTF-8 decoder included in Oracle's JDK
  43  * has been modified to also reject "overlong" byte sequences, but (as
  44  * of 2011) still accepts 3-byte surrogate codepoint byte sequences.
  45  *
  46  * <p>The byte sequences considered valid by this class are exactly
  47  * those that can be roundtrip converted to Strings and back to bytes
  48  * using the UTF-8 charset, without loss: <pre> {@code
  49  * Arrays.equals(bytes, new String(bytes, "UTF-8").getBytes("UTF-8"))
  50  * }</pre>
  51  *
  52  * <p>See the Unicode Standard,</br>
  53  * Table 3-6. <em>UTF-8 Bit Distribution</em>,</br>
  54  * Table 3-7. <em>Well Formed UTF-8 Byte Sequences</em>.
  55  *
  56  * <p>This class supports decoding of partial byte sequences, so that the
  57  * bytes in a complete UTF-8 byte sequences can be stored in multiple
  58  * segments.  Methods typically return {@link #MALFORMED} if the partial
  59  * byte sequence is definitely not well-formed, {@link #COMPLETE} if it is
  60  * well-formed in the absence of additional input, or if the byte sequence
  61  * apparently terminated in the middle of a character, an opaque integer
  62  * "state" value containing enough information to decode the character when
  63  * passed to a subsequent invocation of a partial decoding method.
  64  *
  65  * @author martinrb@google.com (Martin Buchholz)
  66  */
  67 final class Utf8 {
  68   private Utf8() {}
  69
  70   /**
  71    * State value indicating that the byte sequence is well-formed and
  72    * complete (no further bytes are needed to complete a character).
  73    */
  74   public static final int COMPLETE = 0;
  75
  76   /**
  77    * State value indicating that the byte sequence is definitely not
  78    * well-formed.
  79    */
  80   public static final int MALFORMED = -1;
  81
  82   // Other state values include the partial bytes of the incomplete
  83   // character to be decoded in the simplest way: we pack the bytes
  84   // into the state int in little-endian order.  For example:
  85   //
  86   // int state = byte1 ^ (byte2 << 8) ^ (byte3 << 16);
  87   //
  88   // Such a state is unpacked thus (note the ~ operation for byte2 to
  89   // undo byte1's sign-extension bits):
  90   //
  91   // int byte1 = (byte) state;
  92   // int byte2 = (byte) ~(state >> 8);
  93   // int byte3 = (byte) (state >> 16);
  94   //
  95   // We cannot store a zero byte in the state because it would be
  96   // indistinguishable from the absence of a byte.  But we don't need
  97   // to, because partial bytes must always be negative.  When building
  98   // a state, we ensure that byte1 is negative and subsequent bytes
  99   // are valid trailing bytes.
 100
 101   /**
 102    * Returns {@code true} if the given byte array is a well-formed
 103    * UTF-8 byte sequence.
 104    *
 105    * <p>This is a convenience method, equivalent to a call to {@code
 106    * isValidUtf8(bytes, 0, bytes.length)}.
 107    */
 108   public static boolean isValidUtf8(byte[] bytes) {
 109     return isValidUtf8(bytes, 0, bytes.length);
 110   }
 111
 112   /**
 113    * Returns {@code true} if the given byte array slice is a
 114    * well-formed UTF-8 byte sequence.  The range of bytes to be
 115    * checked extends from index {@code index}, inclusive, to {@code
 116    * limit}, exclusive.
 117    *
 118    * <p>This is a convenience method, equivalent to {@code
 119    * partialIsValidUtf8(bytes, index, limit) == Utf8.COMPLETE}.
 120    */
 121   public static boolean isValidUtf8(byte[] bytes, int index, int limit) {
 122     return partialIsValidUtf8(bytes, index, limit) == COMPLETE;
 123   }
 124
 125   /**
 126    * Tells whether the given byte array slice is a well-formed,
 127    * malformed, or incomplete UTF-8 byte sequence.  The range of bytes
 128    * to be checked extends from index {@code index}, inclusive, to
 129    * {@code limit}, exclusive.
 130    *
 131    * @param state either {@link Utf8#COMPLETE} (if this is the initial decoding
 132    * operation) or the value returned from a call to a partial decoding method
 133    * for the previous bytes
 134    *
 135    * @return {@link #MALFORMED} if the partial byte sequence is
 136    * definitely not well-formed, {@link #COMPLETE} if it is well-formed
 137    * (no additional input needed), or if the byte sequence is
 138    * "incomplete", i.e. apparently terminated in the middle of a character,
 139    * an opaque integer "state" value containing enough information to
 140    * decode the character when passed to a subsequent invocation of a
 141    * partial decoding method.
 142    */
 143   public static int partialIsValidUtf8(
 144       int state, byte[] bytes, int index, int limit) {
 145     if (state != COMPLETE) {
 146       // The previous decoding operation was incomplete (or malformed).
 147       // We look for a well-formed sequence consisting of bytes from
 148       // the previous decoding operation (stored in state) together
 149       // with bytes from the array slice.
 150       //
 151       // We expect such "straddler characters" to be rare.
 152
 153       if (index >= limit) {  // No bytes? No progress.
 154         return state;
 155       }
 156       int byte1 = (byte) state;
 157       // byte1 is never ASCII.
 158       if (byte1 < (byte) 0xE0) {
 159         // two-byte form
 160
 161         // Simultaneously checks for illegal trailing-byte in
 162         // leading position and overlong 2-byte form.
 163         if (byte1 < (byte) 0xC2 ||
 164             // byte2 trailing-byte test
 165             bytes[index++] > (byte) 0xBF) {
 166           return MALFORMED;
 167         }
 168       } else if (byte1 < (byte) 0xF0) {
 169         // three-byte form
 170
 171         // Get byte2 from saved state or array
 172         int byte2 = (byte) ~(state >> 8);
 173         if (byte2 == 0) {
 174           byte2 = bytes[index++];
 175           if (index >= limit) {
 176             return incompleteStateFor(byte1, byte2);
 177           }
 178         }
 179         if (byte2 > (byte) 0xBF ||
 180             // overlong? 5 most significant bits must not all be zero
 181             (byte1 == (byte) 0xE0 && byte2 < (byte) 0xA0) ||
 182             // illegal surrogate codepoint?
 183             (byte1 == (byte) 0xED && byte2 >= (byte) 0xA0) ||
 184             // byte3 trailing-byte test
 185             bytes[index++] > (byte) 0xBF) {
 186           return MALFORMED;
 187         }
 188       } else {
 189         // four-byte form
 190
 191         // Get byte2 and byte3 from saved state or array
 192         int byte2 = (byte) ~(state >> 8);
 193         int byte3 = 0;
 194         if (byte2 == 0) {
 195           byte2 = bytes[index++];
 196           if (index >= limit) {
 197             return incompleteStateFor(byte1, byte2);
 198           }
 199         } else {
 200           byte3 = (byte) (state >> 16);
 201         }
 202         if (byte3 == 0) {
 203           byte3 = bytes[index++];
 204           if (index >= limit) {
 205             return incompleteStateFor(byte1, byte2, byte3);
 206           }
 207         }
 208
 209         // If we were called with state == MALFORMED, then byte1 is 0xFF,
 210         // which never occurs in well-formed UTF-8, and so we will return
 211         // MALFORMED again below.
 212
 213         if (byte2 > (byte) 0xBF ||
 214             // Check that 1 <= plane <= 16.  Tricky optimized form of:
 215             // if (byte1 > (byte) 0xF4 ||
 216             //     byte1 == (byte) 0xF0 && byte2 < (byte) 0x90 ||
 217             //     byte1 == (byte) 0xF4 && byte2 > (byte) 0x8F)
 218             (((byte1 << 28) + (byte2 - (byte) 0x90)) >> 30) != 0 ||
 219             // byte3 trailing-byte test
 220             byte3 > (byte) 0xBF ||
 221             // byte4 trailing-byte test
 222              bytes[index++] > (byte) 0xBF) {
 223           return MALFORMED;
 224         }
 225       }
 226     }
 227
 228     return partialIsValidUtf8(bytes, index, limit);
 229   }
 230
 231   /**
 232    * Tells whether the given byte array slice is a well-formed,
 233    * malformed, or incomplete UTF-8 byte sequence.  The range of bytes
 234    * to be checked extends from index {@code index}, inclusive, to
 235    * {@code limit}, exclusive.
 236    *
 237    * <p>This is a convenience method, equivalent to a call to {@code
 238    * partialIsValidUtf8(Utf8.COMPLETE, bytes, index, limit)}.
 239    *
 240    * @return {@link #MALFORMED} if the partial byte sequence is
 241    * definitely not well-formed, {@link #COMPLETE} if it is well-formed
 242    * (no additional input needed), or if the byte sequence is
 243    * "incomplete", i.e. apparently terminated in the middle of a character,
 244    * an opaque integer "state" value containing enough information to
 245    * decode the character when passed to a subsequent invocation of a
 246    * partial decoding method.
 247    */
 248   public static int partialIsValidUtf8(
 249       byte[] bytes, int index, int limit) {
 250     // Optimize for 100% ASCII.
 251     // Hotspot loves small simple top-level loops like this.
 252     while (index < limit && bytes[index] >= 0) {
 253       index++;
 254     }
 255
 256     return (index >= limit) ? COMPLETE :
 257         partialIsValidUtf8NonAscii(bytes, index, limit);
 258   }
 259
 260   private static int partialIsValidUtf8NonAscii(
 261       byte[] bytes, int index, int limit) {
 262     for (;;) {
 263       int byte1, byte2;
 264
 265       // Optimize for interior runs of ASCII bytes.
 266       do {
 267         if (index >= limit) {
 268           return COMPLETE;
 269         }
 270       } while ((byte1 = bytes[index++]) >= 0);
 271
 272       if (byte1 < (byte) 0xE0) {
 273         // two-byte form
 274
 275         if (index >= limit) {
 276           return byte1;
 277         }
 278
 279         // Simultaneously checks for illegal trailing-byte in
 280         // leading position and overlong 2-byte form.
 281         if (byte1 < (byte) 0xC2 ||
 282             bytes[index++] > (byte) 0xBF) {
 283           return MALFORMED;
 284         }
 285       } else if (byte1 < (byte) 0xF0) {
 286         // three-byte form
 287
 288         if (index >= limit - 1) { // incomplete sequence
 289           return incompleteStateFor(bytes, index, limit);
 290         }
 291         if ((byte2 = bytes[index++]) > (byte) 0xBF ||
 292             // overlong? 5 most significant bits must not all be zero
 293             (byte1 == (byte) 0xE0 && byte2 < (byte) 0xA0) ||
 294             // check for illegal surrogate codepoints
 295             (byte1 == (byte) 0xED && byte2 >= (byte) 0xA0) ||
 296             // byte3 trailing-byte test
 297             bytes[index++] > (byte) 0xBF) {
 298           return MALFORMED;
 299         }
 300       } else {
 301         // four-byte form
 302
 303         if (index >= limit - 2) {  // incomplete sequence
 304           return incompleteStateFor(bytes, index, limit);
 305         }
 306         if ((byte2 = bytes[index++]) > (byte) 0xBF ||
 307             // Check that 1 <= plane <= 16.  Tricky optimized form of:
 308             // if (byte1 > (byte) 0xF4 ||
 309             //     byte1 == (byte) 0xF0 && byte2 < (byte) 0x90 ||
 310             //     byte1 == (byte) 0xF4 && byte2 > (byte) 0x8F)
 311             (((byte1 << 28) + (byte2 - (byte) 0x90)) >> 30) != 0 ||
 312             // byte3 trailing-byte test
 313             bytes[index++] > (byte) 0xBF ||
 314             // byte4 trailing-byte test
 315             bytes[index++] > (byte) 0xBF) {
 316           return MALFORMED;
 317         }
 318       }
 319     }
 320   }
 321
 322   private static int incompleteStateFor(int byte1) {
 323     return (byte1 > (byte) 0xF4) ?
 324         MALFORMED : byte1;
 325   }
 326
 327   private static int incompleteStateFor(int byte1, int byte2) {
 328     return (byte1 > (byte) 0xF4 ||
 329             byte2 > (byte) 0xBF) ?
 330         MALFORMED : byte1 ^ (byte2 << 8);
 331   }
 332
 333   private static int incompleteStateFor(int byte1, int byte2, int byte3) {
 334     return (byte1 > (byte) 0xF4 ||
 335             byte2 > (byte) 0xBF ||
 336             byte3 > (byte) 0xBF) ?
 337         MALFORMED : byte1 ^ (byte2 << 8) ^ (byte3 << 16);
 338   }
 339
 340   private static int incompleteStateFor(byte[] bytes, int index, int limit) {
 341     int byte1 = bytes[index - 1];
 342     switch (limit - index) {
 343       case 0: return incompleteStateFor(byte1);
 344       case 1: return incompleteStateFor(byte1, bytes[index]);
 345       case 2: return incompleteStateFor(byte1, bytes[index], bytes[index + 1]);
 346       default: throw new AssertionError();
 347     }
 348   }
 349 }