ByteString.java

Go to the documentation of this file.

// Protocol Buffers - Google's data interchange format
// Copyright 2008 Google Inc.  All rights reserved.
// https://developers.google.com/protocol-buffers/
//
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions are
// met:
//
//     * Redistributions of source code must retain the above copyright
// notice, this list of conditions and the following disclaimer.
//     * Redistributions in binary form must reproduce the above
// copyright notice, this list of conditions and the following disclaimer
// in the documentation and/or other materials provided with the
// distribution.
//     * Neither the name of Google Inc. nor the names of its
// contributors may be used to endorse or promote products derived from
// this software without specific prior written permission.
//
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 
package com.google.protobuf;
 
import java.io.ByteArrayInputStream;
import java.io.ByteArrayOutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.InvalidObjectException;
import java.io.ObjectInputStream;
import java.io.OutputStream;
import java.io.Serializable;
import java.io.UnsupportedEncodingException;
import java.nio.ByteBuffer;
import java.nio.charset.Charset;
import java.nio.charset.UnsupportedCharsetException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.Iterator;
import java.util.List;
import java.util.NoSuchElementException;
 
public abstract class ByteString implements Iterable<Byte>, Serializable {
 
  static final int CONCATENATE_BY_COPY_SIZE = 128;
 
  static final int MIN_READ_FROM_CHUNK_SIZE = 0x100; // 256b
 
  static final int MAX_READ_FROM_CHUNK_SIZE = 0x2000; // 8k
 
  public static final ByteString EMPTY = new LiteralByteString(Internal.EMPTY_BYTE_ARRAY);
 
  private interface ByteArrayCopier {
    byte[] copyFrom(byte[] bytes, int offset, int size);
  }
 
  private static final class SystemByteArrayCopier implements ByteArrayCopier {
    @Override
    public byte[] copyFrom(byte[] bytes, int offset, int size) {
      byte[] copy = new byte[size];
      System.arraycopy(bytes, offset, copy, 0, size);
      return copy;
    }
  }
 
  private static final class ArraysByteArrayCopier implements ByteArrayCopier {
    @Override
    public byte[] copyFrom(byte[] bytes, int offset, int size) {
      return Arrays.copyOfRange(bytes, offset, offset + size);
    }
  }
 
  private static final ByteArrayCopier byteArrayCopier;
 
  static {
    byteArrayCopier =
        Android.isOnAndroidDevice() ? new SystemByteArrayCopier() : new ArraysByteArrayCopier();
  }
 
  private int hash = 0;
 
  // This constructor is here to prevent subclassing outside of this package,
  ByteString() {}
 
  public abstract byte byteAt(int index);
 
  abstract byte internalByteAt(int index);
 
  @Override
  public ByteIterator iterator() {
    return new AbstractByteIterator() {
      private int position = 0;
      private final int limit = size();
 
      @Override
      public boolean hasNext() {
        return position < limit;
      }
 
      @Override
      public byte nextByte() {
        int currentPos = position;
        if (currentPos >= limit) {
          throw new NoSuchElementException();
        }
        position = currentPos + 1;
        return internalByteAt(currentPos);
      }
    };
  }
 
  public interface ByteIterator extends Iterator<Byte> {
    byte nextByte();
  }
 
  abstract static class AbstractByteIterator implements ByteIterator {
    @Override
    public final Byte next() {
      // Boxing calls Byte.valueOf(byte), which does not instantiate.
      return nextByte();
    }
 
    @Override
    public final void remove() {
      throw new UnsupportedOperationException();
    }
  }
 
  public abstract int size();
 
  public final boolean isEmpty() {
    return size() == 0;
  }
 
  // =================================================================
  // Comparison
 
  private static final int UNSIGNED_BYTE_MASK = 0xFF;
 
  private static int toInt(byte value) {
    return value & UNSIGNED_BYTE_MASK;
  }
 
  private static final Comparator<ByteString> UNSIGNED_LEXICOGRAPHICAL_COMPARATOR =
      new Comparator<ByteString>() {
        @Override
        public int compare(ByteString former, ByteString latter) {
          ByteIterator formerBytes = former.iterator();
          ByteIterator latterBytes = latter.iterator();
 
          while (formerBytes.hasNext() && latterBytes.hasNext()) {
            // Note: This code was copied from com.google.common.primitives.UnsignedBytes#compare,
            // as Guava libraries cannot be used in the {@code com.google.protobuf} package.
            int result =
                Integer.compare(toInt(formerBytes.nextByte()), toInt(latterBytes.nextByte()));
            if (result != 0) {
              return result;
            }
          }
 
          return Integer.compare(former.size(), latter.size());
        }
      };
 
  public static Comparator<ByteString> unsignedLexicographicalComparator() {
    return UNSIGNED_LEXICOGRAPHICAL_COMPARATOR;
  }
 
  // =================================================================
  // ByteString -> substring
 
  public final ByteString substring(int beginIndex) {
    return substring(beginIndex, size());
  }
 
  public abstract ByteString substring(int beginIndex, int endIndex);
 
  public final boolean startsWith(ByteString prefix) {
    return size() >= prefix.size() && substring(0, prefix.size()).equals(prefix);
  }
 
  public final boolean endsWith(ByteString suffix) {
    return size() >= suffix.size() && substring(size() - suffix.size()).equals(suffix);
  }
 
  // =================================================================
  // byte[] -> ByteString
 
  public static ByteString copyFrom(byte[] bytes, int offset, int size) {
    checkRange(offset, offset + size, bytes.length);
    return new LiteralByteString(byteArrayCopier.copyFrom(bytes, offset, size));
  }
 
  public static ByteString copyFrom(byte[] bytes) {
    return copyFrom(bytes, 0, bytes.length);
  }
 
  static ByteString wrap(ByteBuffer buffer) {
    if (buffer.hasArray()) {
      final int offset = buffer.arrayOffset();
      return ByteString.wrap(buffer.array(), offset + buffer.position(), buffer.remaining());
    } else {
      return new NioByteString(buffer);
    }
  }
 
  static ByteString wrap(byte[] bytes) {
    // TODO(dweis): Return EMPTY when bytes are empty to reduce allocations?
    return new LiteralByteString(bytes);
  }
 
  static ByteString wrap(byte[] bytes, int offset, int length) {
    return new BoundedByteString(bytes, offset, length);
  }
 
  public static ByteString copyFrom(ByteBuffer bytes, int size) {
    checkRange(0, size, bytes.remaining());
    byte[] copy = new byte[size];
    bytes.get(copy);
    return new LiteralByteString(copy);
  }
 
  public static ByteString copyFrom(ByteBuffer bytes) {
    return copyFrom(bytes, bytes.remaining());
  }
 
  public static ByteString copyFrom(String text, String charsetName)
      throws UnsupportedEncodingException {
    return new LiteralByteString(text.getBytes(charsetName));
  }
 
  public static ByteString copyFrom(String text, Charset charset) {
    return new LiteralByteString(text.getBytes(charset));
  }
 
  public static ByteString copyFromUtf8(String text) {
    return new LiteralByteString(text.getBytes(Internal.UTF_8));
  }
 
  // =================================================================
  // InputStream -> ByteString
 
  public static ByteString readFrom(InputStream streamToDrain) throws IOException {
    return readFrom(streamToDrain, MIN_READ_FROM_CHUNK_SIZE, MAX_READ_FROM_CHUNK_SIZE);
  }
 
  public static ByteString readFrom(InputStream streamToDrain, int chunkSize) throws IOException {
    return readFrom(streamToDrain, chunkSize, chunkSize);
  }
 
  // Helper method that takes the chunk size range as a parameter.
  public static ByteString readFrom(InputStream streamToDrain, int minChunkSize, int maxChunkSize)
      throws IOException {
    Collection<ByteString> results = new ArrayList<ByteString>();
 
    // copy the inbound bytes into a list of chunks; the chunk size
    // grows exponentially to support both short and long streams.
    int chunkSize = minChunkSize;
    while (true) {
      ByteString chunk = readChunk(streamToDrain, chunkSize);
      if (chunk == null) {
        break;
      }
      results.add(chunk);
      chunkSize = Math.min(chunkSize * 2, maxChunkSize);
    }
 
    return ByteString.copyFrom(results);
  }
 
  private static ByteString readChunk(InputStream in, final int chunkSize) throws IOException {
    final byte[] buf = new byte[chunkSize];
    int bytesRead = 0;
    while (bytesRead < chunkSize) {
      final int count = in.read(buf, bytesRead, chunkSize - bytesRead);
      if (count == -1) {
        break;
      }
      bytesRead += count;
    }
 
    if (bytesRead == 0) {
      return null;
    }
 
    // Always make a copy since InputStream could steal a reference to buf.
    return ByteString.copyFrom(buf, 0, bytesRead);
  }
 
  // =================================================================
  // Multiple ByteStrings -> One ByteString
 
  public final ByteString concat(ByteString other) {
    if (Integer.MAX_VALUE - size() < other.size()) {
      throw new IllegalArgumentException(
          "ByteString would be too long: " + size() + "+" + other.size());
    }
 
    return RopeByteString.concatenate(this, other);
  }
 
  public static ByteString copyFrom(Iterable<ByteString> byteStrings) {
    // Determine the size;
    final int size;
    if (!(byteStrings instanceof Collection)) {
      int tempSize = 0;
      for (Iterator<ByteString> iter = byteStrings.iterator();
          iter.hasNext();
          iter.next(), ++tempSize) {}
      size = tempSize;
    } else {
      size = ((Collection<ByteString>) byteStrings).size();
    }
 
    if (size == 0) {
      return EMPTY;
    }
 
    return balancedConcat(byteStrings.iterator(), size);
  }
 
  // Internal function used by copyFrom(Iterable<ByteString>).
  // Create a balanced concatenation of the next "length" elements from the
  // iterable.
  private static ByteString balancedConcat(Iterator<ByteString> iterator, int length) {
    if (length < 1) {
      throw new IllegalArgumentException(String.format("length (%s) must be >= 1", length));
    }
    ByteString result;
    if (length == 1) {
      result = iterator.next();
    } else {
      int halfLength = length >>> 1;
      ByteString left = balancedConcat(iterator, halfLength);
      ByteString right = balancedConcat(iterator, length - halfLength);
      result = left.concat(right);
    }
    return result;
  }
 
  // =================================================================
  // ByteString -> byte[]
 
  public void copyTo(byte[] target, int offset) {
    copyTo(target, 0, offset, size());
  }
 
  @Deprecated
  public final void copyTo(byte[] target, int sourceOffset, int targetOffset, int numberToCopy) {
    checkRange(sourceOffset, sourceOffset + numberToCopy, size());
    checkRange(targetOffset, targetOffset + numberToCopy, target.length);
    if (numberToCopy > 0) {
      copyToInternal(target, sourceOffset, targetOffset, numberToCopy);
    }
  }
 
  protected abstract void copyToInternal(
      byte[] target, int sourceOffset, int targetOffset, int numberToCopy);
 
  public abstract void copyTo(ByteBuffer target);
 
  public final byte[] toByteArray() {
    final int size = size();
    if (size == 0) {
      return Internal.EMPTY_BYTE_ARRAY;
    }
    byte[] result = new byte[size];
    copyToInternal(result, 0, 0, size);
    return result;
  }
 
  public abstract void writeTo(OutputStream out) throws IOException;
 
  final void writeTo(OutputStream out, int sourceOffset, int numberToWrite) throws IOException {
    checkRange(sourceOffset, sourceOffset + numberToWrite, size());
    if (numberToWrite > 0) {
      writeToInternal(out, sourceOffset, numberToWrite);
    }
  }
 
  abstract void writeToInternal(OutputStream out, int sourceOffset, int numberToWrite)
      throws IOException;
 
  abstract void writeTo(ByteOutput byteOutput) throws IOException;
 
  abstract void writeToReverse(ByteOutput byteOutput) throws IOException;
 
  public abstract ByteBuffer asReadOnlyByteBuffer();
 
  public abstract List<ByteBuffer> asReadOnlyByteBufferList();
 
  public final String toString(String charsetName) throws UnsupportedEncodingException {
    try {
      return toString(Charset.forName(charsetName));
    } catch (UnsupportedCharsetException e) {
      UnsupportedEncodingException exception = new UnsupportedEncodingException(charsetName);
      exception.initCause(e);
      throw exception;
    }
  }
 
  public final String toString(Charset charset) {
    return size() == 0 ? "" : toStringInternal(charset);
  }
 
  protected abstract String toStringInternal(Charset charset);
 
  // =================================================================
  // UTF-8 decoding
 
  public final String toStringUtf8() {
    return toString(Internal.UTF_8);
  }
 
  public abstract boolean isValidUtf8();
 
  protected abstract int partialIsValidUtf8(int state, int offset, int length);
 
  // =================================================================
  // equals() and hashCode()
 
  @Override
  public abstract boolean equals(Object o);
 
  abstract static class LeafByteString extends ByteString {
    @Override
    protected final int getTreeDepth() {
      return 0;
    }
 
    @Override
    protected final boolean isBalanced() {
      return true;
    }
 
    @Override
    void writeToReverse(ByteOutput byteOutput) throws IOException {
      writeTo(byteOutput);
    }
 
    abstract boolean equalsRange(ByteString other, int offset, int length);
  }
 
  @Override
  public final int hashCode() {
    int h = hash;
 
    if (h == 0) {
      int size = size();
      h = partialHash(size, 0, size);
      if (h == 0) {
        h = 1;
      }
      hash = h;
    }
    return h;
  }
 
  // =================================================================
  // Input stream
 
  public abstract InputStream newInput();
 
  public abstract CodedInputStream newCodedInput();
 
  // =================================================================
  // Output stream
 
  public static Output newOutput(int initialCapacity) {
    return new Output(initialCapacity);
  }
 
  public static Output newOutput() {
    return new Output(CONCATENATE_BY_COPY_SIZE);
  }
 
  public static final class Output extends OutputStream {
    // Implementation note.
    // The public methods of this class must be synchronized.  ByteStrings
    // are guaranteed to be immutable.  Without some sort of locking, it could
    // be possible for one thread to call toByteSring(), while another thread
    // is still modifying the underlying byte array.
 
    private static final byte[] EMPTY_BYTE_ARRAY = new byte[0];
    // argument passed by user, indicating initial capacity.
    private final int initialCapacity;
    // ByteStrings to be concatenated to create the result
    private final ArrayList<ByteString> flushedBuffers;
    // Total number of bytes in the ByteStrings of flushedBuffers
    private int flushedBuffersTotalBytes;
    // Current buffer to which we are writing
    private byte[] buffer;
    // Location in buffer[] to which we write the next byte.
    private int bufferPos;
 
    Output(int initialCapacity) {
      if (initialCapacity < 0) {
        throw new IllegalArgumentException("Buffer size < 0");
      }
      this.initialCapacity = initialCapacity;
      this.flushedBuffers = new ArrayList<ByteString>();
      this.buffer = new byte[initialCapacity];
    }
 
    @Override
    public synchronized void write(int b) {
      if (bufferPos == buffer.length) {
        flushFullBuffer(1);
      }
      buffer[bufferPos++] = (byte) b;
    }
 
    @Override
    public synchronized void write(byte[] b, int offset, int length) {
      if (length <= buffer.length - bufferPos) {
        // The bytes can fit into the current buffer.
        System.arraycopy(b, offset, buffer, bufferPos, length);
        bufferPos += length;
      } else {
        // Use up the current buffer
        int copySize = buffer.length - bufferPos;
        System.arraycopy(b, offset, buffer, bufferPos, copySize);
        offset += copySize;
        length -= copySize;
        // Flush the buffer, and get a new buffer at least big enough to cover
        // what we still need to output
        flushFullBuffer(length);
        System.arraycopy(b, offset, buffer, /* count= */ 0, length);
        bufferPos = length;
      }
    }
 
    public synchronized ByteString toByteString() {
      flushLastBuffer();
      return ByteString.copyFrom(flushedBuffers);
    }
 
    private byte[] copyArray(byte[] buffer, int length) {
      byte[] result = new byte[length];
      System.arraycopy(buffer, 0, result, 0, Math.min(buffer.length, length));
      return result;
    }
 
    public void writeTo(OutputStream out) throws IOException {
      ByteString[] cachedFlushBuffers;
      byte[] cachedBuffer;
      int cachedBufferPos;
      synchronized (this) {
        // Copy the information we need into local variables so as to hold
        // the lock for as short a time as possible.
        cachedFlushBuffers = flushedBuffers.toArray(new ByteString[flushedBuffers.size()]);
        cachedBuffer = buffer;
        cachedBufferPos = bufferPos;
      }
      for (ByteString byteString : cachedFlushBuffers) {
        byteString.writeTo(out);
      }
 
      out.write(copyArray(cachedBuffer, cachedBufferPos));
    }
 
    public synchronized int size() {
      return flushedBuffersTotalBytes + bufferPos;
    }
 
    public synchronized void reset() {
      flushedBuffers.clear();
      flushedBuffersTotalBytes = 0;
      bufferPos = 0;
    }
 
    @Override
    public String toString() {
      return String.format(
          "<ByteString.Output@%s size=%d>",
          Integer.toHexString(System.identityHashCode(this)), size());
    }
 
    private void flushFullBuffer(int minSize) {
      flushedBuffers.add(new LiteralByteString(buffer));
      flushedBuffersTotalBytes += buffer.length;
      // We want to increase our total capacity by 50%, but as a minimum,
      // the new buffer should also at least be >= minSize and
      // >= initial Capacity.
      int newSize = Math.max(initialCapacity, Math.max(minSize, flushedBuffersTotalBytes >>> 1));
      buffer = new byte[newSize];
      bufferPos = 0;
    }
 
    private void flushLastBuffer() {
      if (bufferPos < buffer.length) {
        if (bufferPos > 0) {
          byte[] bufferCopy = copyArray(buffer, bufferPos);
          flushedBuffers.add(new LiteralByteString(bufferCopy));
        }
        // We reuse this buffer for further writes.
      } else {
        // Buffer is completely full.  Huzzah.
        flushedBuffers.add(new LiteralByteString(buffer));
        // 99% of the time, we're not going to use this OutputStream again.
        // We set buffer to an empty byte stream so that we're handling this
        // case without wasting space.  In the rare case that more writes
        // *do* occur, this empty buffer will be flushed and an appropriately
        // sized new buffer will be created.
        buffer = EMPTY_BYTE_ARRAY;
      }
      flushedBuffersTotalBytes += bufferPos;
      bufferPos = 0;
    }
  }
 
  static CodedBuilder newCodedBuilder(int size) {
    return new CodedBuilder(size);
  }
 
  static final class CodedBuilder {
    private final CodedOutputStream output;
    private final byte[] buffer;
 
    private CodedBuilder(int size) {
      buffer = new byte[size];
      output = CodedOutputStream.newInstance(buffer);
    }
 
    public ByteString build() {
      output.checkNoSpaceLeft();
 
      // We can be confident that the CodedOutputStream will not modify the
      // underlying bytes anymore because it already wrote all of them.  So,
      // no need to make a copy.
      return new LiteralByteString(buffer);
    }
 
    public CodedOutputStream getCodedOutput() {
      return output;
    }
  }
 
  // =================================================================
  // Methods {@link RopeByteString} needs on instances, which aren't part of the
  // public API.
 
  protected abstract int getTreeDepth();
 
  protected abstract boolean isBalanced();
 
  protected final int peekCachedHashCode() {
    return hash;
  }
 
  protected abstract int partialHash(int h, int offset, int length);
 
  static void checkIndex(int index, int size) {
    if ((index | (size - (index + 1))) < 0) {
      if (index < 0) {
        throw new ArrayIndexOutOfBoundsException("Index < 0: " + index);
      }
      throw new ArrayIndexOutOfBoundsException("Index > length: " + index + ", " + size);
    }
  }
 
  static int checkRange(int startIndex, int endIndex, int size) {
    final int length = endIndex - startIndex;
    if ((startIndex | endIndex | length | (size - endIndex)) < 0) {
      if (startIndex < 0) {
        throw new IndexOutOfBoundsException("Beginning index: " + startIndex + " < 0");
      }
      if (endIndex < startIndex) {
        throw new IndexOutOfBoundsException(
            "Beginning index larger than ending index: " + startIndex + ", " + endIndex);
      }
      // endIndex >= size
      throw new IndexOutOfBoundsException("End index: " + endIndex + " >= " + size);
    }
    return length;
  }
 
  @Override
  public final String toString() {
    return String.format(
        "<ByteString@%s size=%d>", Integer.toHexString(System.identityHashCode(this)), size());
  }
 
  // Keep this class private to avoid deadlocks in classloading across threads as ByteString's
  // static initializer loads LiteralByteString and another thread loads LiteralByteString.
  private static class LiteralByteString extends ByteString.LeafByteString {
    private static final long serialVersionUID = 1L;
 
    protected final byte[] bytes;
 
    LiteralByteString(byte[] bytes) {
      if (bytes == null) {
        throw new NullPointerException();
      }
      this.bytes = bytes;
    }
 
    @Override
    public byte byteAt(int index) {
      // Unlike most methods in this class, this one is a direct implementation
      // ignoring the potential offset because we need to do range-checking in the
      // substring case anyway.
      return bytes[index];
    }
 
    @Override
    byte internalByteAt(int index) {
      return bytes[index];
    }
 
    @Override
    public int size() {
      return bytes.length;
    }
 
    // =================================================================
    // ByteString -> substring
 
    @Override
    public final ByteString substring(int beginIndex, int endIndex) {
      final int length = checkRange(beginIndex, endIndex, size());
 
      if (length == 0) {
        return ByteString.EMPTY;
      }
 
      return new BoundedByteString(bytes, getOffsetIntoBytes() + beginIndex, length);
    }
 
    // =================================================================
    // ByteString -> byte[]
 
    @Override
    protected void copyToInternal(
        byte[] target, int sourceOffset, int targetOffset, int numberToCopy) {
      // Optimized form, not for subclasses, since we don't call
      // getOffsetIntoBytes() or check the 'numberToCopy' parameter.
      // TODO(nathanmittler): Is not calling getOffsetIntoBytes really saving that much?
      System.arraycopy(bytes, sourceOffset, target, targetOffset, numberToCopy);
    }
 
    @Override
    public final void copyTo(ByteBuffer target) {
      target.put(bytes, getOffsetIntoBytes(), size()); // Copies bytes
    }
 
    @Override
    public final ByteBuffer asReadOnlyByteBuffer() {
      return ByteBuffer.wrap(bytes, getOffsetIntoBytes(), size()).asReadOnlyBuffer();
    }
 
    @Override
    public final List<ByteBuffer> asReadOnlyByteBufferList() {
      return Collections.singletonList(asReadOnlyByteBuffer());
    }
 
    @Override
    public final void writeTo(OutputStream outputStream) throws IOException {
      outputStream.write(toByteArray());
    }
 
    @Override
    final void writeToInternal(OutputStream outputStream, int sourceOffset, int numberToWrite)
        throws IOException {
      outputStream.write(bytes, getOffsetIntoBytes() + sourceOffset, numberToWrite);
    }
 
    @Override
    final void writeTo(ByteOutput output) throws IOException {
      output.writeLazy(bytes, getOffsetIntoBytes(), size());
    }
 
    @Override
    protected final String toStringInternal(Charset charset) {
      return new String(bytes, getOffsetIntoBytes(), size(), charset);
    }
 
    // =================================================================
    // UTF-8 decoding
 
    @Override
    public final boolean isValidUtf8() {
      int offset = getOffsetIntoBytes();
      return Utf8.isValidUtf8(bytes, offset, offset + size());
    }
 
    @Override
    protected final int partialIsValidUtf8(int state, int offset, int length) {
      int index = getOffsetIntoBytes() + offset;
      return Utf8.partialIsValidUtf8(state, bytes, index, index + length);
    }
 
    // =================================================================
    // equals() and hashCode()
 
    @Override
    public final boolean equals(Object other) {
      if (other == this) {
        return true;
      }
      if (!(other instanceof ByteString)) {
        return false;
      }
 
      if (size() != ((ByteString) other).size()) {
        return false;
      }
      if (size() == 0) {
        return true;
      }
 
      if (other instanceof LiteralByteString) {
        LiteralByteString otherAsLiteral = (LiteralByteString) other;
        // If we know the hash codes and they are not equal, we know the byte
        // strings are not equal.
        int thisHash = peekCachedHashCode();
        int thatHash = otherAsLiteral.peekCachedHashCode();
        if (thisHash != 0 && thatHash != 0 && thisHash != thatHash) {
          return false;
        }
 
        return equalsRange((LiteralByteString) other, 0, size());
      } else {
        // RopeByteString and NioByteString.
        return other.equals(this);
      }
    }
 
    @Override
    final boolean equalsRange(ByteString other, int offset, int length) {
      if (length > other.size()) {
        throw new IllegalArgumentException("Length too large: " + length + size());
      }
      if (offset + length > other.size()) {
        throw new IllegalArgumentException(
            "Ran off end of other: " + offset + ", " + length + ", " + other.size());
      }
 
      if (other instanceof LiteralByteString) {
        LiteralByteString lbsOther = (LiteralByteString) other;
        byte[] thisBytes = bytes;
        byte[] otherBytes = lbsOther.bytes;
        int thisLimit = getOffsetIntoBytes() + length;
        for (int thisIndex = getOffsetIntoBytes(),
                otherIndex = lbsOther.getOffsetIntoBytes() + offset;
            (thisIndex < thisLimit);
            ++thisIndex, ++otherIndex) {
          if (thisBytes[thisIndex] != otherBytes[otherIndex]) {
            return false;
          }
        }
        return true;
      }
 
      return other.substring(offset, offset + length).equals(substring(0, length));
    }
 
    @Override
    protected final int partialHash(int h, int offset, int length) {
      return Internal.partialHash(h, bytes, getOffsetIntoBytes() + offset, length);
    }
 
    // =================================================================
    // Input stream
 
    @Override
    public final InputStream newInput() {
      return new ByteArrayInputStream(bytes, getOffsetIntoBytes(), size()); // No copy
    }
 
    @Override
    public final CodedInputStream newCodedInput() {
      // We trust CodedInputStream not to modify the bytes, or to give anyone
      // else access to them.
      return CodedInputStream.newInstance(
          bytes, getOffsetIntoBytes(), size(), /* bufferIsImmutable= */ true);
    }
 
    // =================================================================
    // Internal methods
 
    protected int getOffsetIntoBytes() {
      return 0;
    }
  }
 
  // Keep this class private to avoid deadlocks in classloading across threads as ByteString's
  // static initializer loads LiteralByteString and another thread loads BoundedByteString.
  private static final class BoundedByteString extends LiteralByteString {
 
    private final int bytesOffset;
    private final int bytesLength;
 
    BoundedByteString(byte[] bytes, int offset, int length) {
      super(bytes);
      checkRange(offset, offset + length, bytes.length);
 
      this.bytesOffset = offset;
      this.bytesLength = length;
    }
 
    @Override
    public byte byteAt(int index) {
      // We must check the index ourselves as we cannot rely on Java array index
      // checking for substrings.
      checkIndex(index, size());
      return bytes[bytesOffset + index];
    }
 
    @Override
    byte internalByteAt(int index) {
      return bytes[bytesOffset + index];
    }
 
    @Override
    public int size() {
      return bytesLength;
    }
 
    @Override
    protected int getOffsetIntoBytes() {
      return bytesOffset;
    }
 
    // =================================================================
    // ByteString -> byte[]
 
    @Override
    protected void copyToInternal(
        byte[] target, int sourceOffset, int targetOffset, int numberToCopy) {
      System.arraycopy(
          bytes, getOffsetIntoBytes() + sourceOffset, target, targetOffset, numberToCopy);
    }
 
    // =================================================================
    // Serializable
 
    private static final long serialVersionUID = 1L;
 
    Object writeReplace() {
      return ByteString.wrap(toByteArray());
    }
 
    private void readObject(@SuppressWarnings("unused") ObjectInputStream in) throws IOException {
      throw new InvalidObjectException(
          "BoundedByteStream instances are not to be serialized directly");
    }
  }
}