1 /*
2  * Copyright (C) 2014 Square, Inc.
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  *      http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16 package okio;
17
18 import java.io.Closeable;
19 import java.io.EOFException;
20 import java.io.IOException;
21 import java.io.InputStream;
22 import java.io.OutputStream;
23 import java.nio.ByteBuffer;
24 import java.nio.channels.ByteChannel;
25 import java.nio.charset.Charset;
26 import java.security.InvalidKeyException;
27 import java.security.MessageDigest;
28 import java.security.NoSuchAlgorithmException;
29 import java.util.ArrayList;
30 import java.util.Collections;
31 import java.util.List;
32 import javax.annotation.Nullable;
33 import javax.crypto.Mac;
34 import javax.crypto.spec.SecretKeySpec;
35
36 import static okio.Util.checkOffsetAndCount;
37 import static okio.Util.reverseBytesLong;
38
39 /**
40  * A collection of bytes in memory.
41  *
42  * <p><strong>Moving data from one buffer to another is fast.</strong> Instead
43  * of copying bytes from one place in memory to another, this class just changes
44  * ownership of the underlying byte arrays.
45  *
46  * <p><strong>This buffer grows with your data.</strong> Just like ArrayList,
47  * each buffer starts small. It consumes only the memory it needs to.
48  *
49  * <p><strong>This buffer pools its byte arrays.</strong> When you allocate a
50  * byte array in Java, the runtime must zero-fill the requested array before
51  * returning it to you. Even if you're going to write over that space anyway.
52  * This class avoids zero-fill and GC churn by pooling byte arrays.
53  */
54 public final class Buffer implements BufferedSource, BufferedSink, Cloneable, ByteChannel {
55   private static final byte[] DIGITS =
56       { '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'a', 'b', 'c', 'd', 'e', 'f' };
57   static final int REPLACEMENT_CHARACTER = '\ufffd';
58
59   @Nullable Segment head;
60   long size;
61
62   public Buffer() {
63   }
64
65   /** Returns the number of bytes currently in this buffer. */
66   public final long size() {
67     return size;
68   }
69
70   @Override public Buffer buffer() {
71     return this;
72   }
73
74   @Override public Buffer getBuffer() {
75     return this;
76   }
77
78   @Override public OutputStream outputStream() {
79     return new OutputStream() {
80       @Override public void write(int b) {
81         writeByte((byte) b);
82       }
83
84       @Override public void write(byte[] data, int offset, int byteCount) {
85         Buffer.this.write(data, offset, byteCount);
86       }
87
88       @Override public void flush() {
89       }
90
91       @Override public void close() {
92       }
93
94       @Override public String toString() {
95         return Buffer.this + ".outputStream()";
96       }
97     };
98   }
99
100   @Override public Buffer emitCompleteSegments() {
101     return this; // Nowhere to emit to!
102   }
103
104   @Override public BufferedSink emit() {
105     return this; // Nowhere to emit to!
106   }
107
108   @Override public boolean exhausted() {
109     return size == 0;
110   }
111
112   @Override public void require(long byteCount) throws EOFException {
113     if (size < byteCount) throw new EOFException();
114   }
115
116   @Override public boolean request(long byteCount) {
117     return size >= byteCount;
118   }
119
120   @Override public BufferedSource peek() {
121     return Okio.buffer(new PeekSource(this));
122   }
123
124   @Override public InputStream inputStream() {
125     return new InputStream() {
126       @Override public int read() {
127         if (size > 0) return readByte() & 0xff;
128         return -1;
129       }
130
131       @Override public int read(byte[] sink, int offset, int byteCount) {
132         return Buffer.this.read(sink, offset, byteCount);
133       }
134
135       @Override public int available() {
136         return (int) Math.min(size, Integer.MAX_VALUE);
137       }
138
139       @Override public void close() {
140       }
141
142       @Override public String toString() {
143         return Buffer.this + ".inputStream()";
144       }
145     };
146   }
147
148   /** Copy the contents of this to {@code out}. */
149   public final Buffer copyTo(OutputStream out) throws IOException {
150     return copyTo(out, 0, size);
151   }
152
153   /**
154    * Copy {@code byteCount} bytes from this, starting at {@code offset}, to
155    * {@code out}.
156    */
157   public final Buffer copyTo(OutputStream out, long offset, long byteCount) throws IOException {
158     if (out == null) throw new IllegalArgumentException("out == null");
159     checkOffsetAndCount(size, offset, byteCount);
160     if (byteCount == 0) return this;
161
162     // Skip segments that we aren't copying from.
163     Segment s = head;
164     for (; offset >= (s.limit - s.pos); s = s.next) {
165       offset -= (s.limit - s.pos);
166     }
167
168     // Copy from one segment at a time.
169     for (; byteCount > 0; s = s.next) {
170       int pos = (int) (s.pos + offset);
171       int toCopy = (int) Math.min(s.limit - pos, byteCount);
172       out.write(s.data, pos, toCopy);
173       byteCount -= toCopy;
174       offset = 0;
175     }
176
177     return this;
178   }
179
180   /** Copy {@code byteCount} bytes from this, starting at {@code offset}, to {@code out}. */
181   public final Buffer copyTo(Buffer out, long offset, long byteCount) {
182     if (out == null) throw new IllegalArgumentException("out == null");
183     checkOffsetAndCount(size, offset, byteCount);
184     if (byteCount == 0) return this;
185
186     out.size += byteCount;
187
188     // Skip segments that we aren't copying from.
189     Segment s = head;
190     for (; offset >= (s.limit - s.pos); s = s.next) {
191       offset -= (s.limit - s.pos);
192     }
193
194     // Copy one segment at a time.
195     for (; byteCount > 0; s = s.next) {
196       Segment copy = s.sharedCopy();
197       copy.pos += offset;
198       copy.limit = Math.min(copy.pos + (int) byteCount, copy.limit);
199       if (out.head == null) {
200         out.head = copy.next = copy.prev = copy;
201       } else {
202         out.head.prev.push(copy);
203       }
204       byteCount -= copy.limit - copy.pos;
205       offset = 0;
206     }
207
208     return this;
209   }
210
211   /** Write the contents of this to {@code out}. */
212   public final Buffer writeTo(OutputStream out) throws IOException {
213     return writeTo(out, size);
214   }
215
216   /** Write {@code byteCount} bytes from this to {@code out}. */
217   public final Buffer writeTo(OutputStream out, long byteCount) throws IOException {
218     if (out == null) throw new IllegalArgumentException("out == null");
219     checkOffsetAndCount(size, 0, byteCount);
220
221     Segment s = head;
222     while (byteCount > 0) {
223       int toCopy = (int) Math.min(byteCount, s.limit - s.pos);
224       out.write(s.data, s.pos, toCopy);
225
226       s.pos += toCopy;
227       size -= toCopy;
228       byteCount -= toCopy;
229
230       if (s.pos == s.limit) {
231         Segment toRecycle = s;
232         head = s = toRecycle.pop();
233         SegmentPool.recycle(toRecycle);
234       }
235     }
236
237     return this;
238   }
239
240   /** Read and exhaust bytes from {@code in} to this. */
241   public final Buffer readFrom(InputStream in) throws IOException {
242     readFrom(in, Long.MAX_VALUE, true);
243     return this;
244   }
245
246   /** Read {@code byteCount} bytes from {@code in} to this. */
247   public final Buffer readFrom(InputStream in, long byteCount) throws IOException {
248     if (byteCount < 0) throw new IllegalArgumentException("byteCount < 0: " + byteCount);
249     readFrom(in, byteCount, false);
250     return this;
251   }
252
253   private void readFrom(InputStream in, long byteCount, boolean forever) throws IOException {
254     if (in == null) throw new IllegalArgumentException("in == null");
255     while (byteCount > 0 || forever) {
256       Segment tail = writableSegment(1);
257       int maxToCopy = (int) Math.min(byteCount, Segment.SIZE - tail.limit);
258       int bytesRead = in.read(tail.data, tail.limit, maxToCopy);
259       if (bytesRead == -1) {
260         if (forever) return;
261         throw new EOFException();
262       }
263       tail.limit += bytesRead;
264       size += bytesRead;
265       byteCount -= bytesRead;
266     }
267   }
268
269   /**
270    * Returns the number of bytes in segments that are not writable. This is the
271    * number of bytes that can be flushed immediately to an underlying sink
272    * without harming throughput.
273    */
274   public final long completeSegmentByteCount() {
275     long result = size;
276     if (result == 0) return 0;
277
278     // Omit the tail if it's still writable.
279     Segment tail = head.prev;
280     if (tail.limit < Segment.SIZE && tail.owner) {
281       result -= tail.limit - tail.pos;
282     }
283
284     return result;
285   }
286
287   @Override public byte readByte() {
288     if (size == 0) throw new IllegalStateException("size == 0");
289
290     Segment segment = head;
291     int pos = segment.pos;
292     int limit = segment.limit;
293
294     byte[] data = segment.data;
295     byte b = data[pos++];
296     size -= 1;
297
298     if (pos == limit) {
299       head = segment.pop();
300       SegmentPool.recycle(segment);
301     } else {
302       segment.pos = pos;
303     }
304
305     return b;
306   }
307
308   /** Returns the byte at {@code pos}. */
309   public final byte getByte(long pos) {
310     checkOffsetAndCount(size, pos, 1);
311     if (size - pos > pos) {
312       for (Segment s = head; true; s = s.next) {
313         int segmentByteCount = s.limit - s.pos;
314         if (pos < segmentByteCount) return s.data[s.pos + (int) pos];
315         pos -= segmentByteCount;
316       }
317     } else {
318       pos -= size;
319       for (Segment s = head.prev; true; s = s.prev) {
320         pos += s.limit - s.pos;
321         if (pos >= 0) return s.data[s.pos + (int) pos];
322       }
323     }
324   }
325
326   @Override public short readShort() {
327     if (size < 2) throw new IllegalStateException("size < 2: " + size);
328
329     Segment segment = head;
330     int pos = segment.pos;
331     int limit = segment.limit;
332
333     // If the short is split across multiple segments, delegate to readByte().
334     if (limit - pos < 2) {
335       int s = (readByte() & 0xff) << 8
336           |   (readByte() & 0xff);
337       return (short) s;
338     }
339
340     byte[] data = segment.data;
341     int s = (data[pos++] & 0xff) << 8
342         |   (data[pos++] & 0xff);
343     size -= 2;
344
345     if (pos == limit) {
346       head = segment.pop();
347       SegmentPool.recycle(segment);
348     } else {
349       segment.pos = pos;
350     }
351
352     return (short) s;
353   }
354
355   @Override public int readInt() {
356     if (size < 4) throw new IllegalStateException("size < 4: " + size);
357
358     Segment segment = head;
359     int pos = segment.pos;
360     int limit = segment.limit;
361
362     // If the int is split across multiple segments, delegate to readByte().
363     if (limit - pos < 4) {
364       return (readByte() & 0xff) << 24
365           |  (readByte() & 0xff) << 16
366           |  (readByte() & 0xff) <<  8
367           |  (readByte() & 0xff);
368     }
369
370     byte[] data = segment.data;
371     int i = (data[pos++] & 0xff) << 24
372         |   (data[pos++] & 0xff) << 16
373         |   (data[pos++] & 0xff) <<  8
374         |   (data[pos++] & 0xff);
375     size -= 4;
376
377     if (pos == limit) {
378       head = segment.pop();
379       SegmentPool.recycle(segment);
380     } else {
381       segment.pos = pos;
382     }
383
384     return i;
385   }
386
387   @Override public long readLong() {
388     if (size < 8) throw new IllegalStateException("size < 8: " + size);
389
390     Segment segment = head;
391     int pos = segment.pos;
392     int limit = segment.limit;
393
394     // If the long is split across multiple segments, delegate to readInt().
395     if (limit - pos < 8) {
396       return (readInt() & 0xffffffffL) << 32
397           |  (readInt() & 0xffffffffL);
398     }
399
400     byte[] data = segment.data;
401     long v = (data[pos++] & 0xffL) << 56
402         |    (data[pos++] & 0xffL) << 48
403         |    (data[pos++] & 0xffL) << 40
404         |    (data[pos++] & 0xffL) << 32
405         |    (data[pos++] & 0xffL) << 24
406         |    (data[pos++] & 0xffL) << 16
407         |    (data[pos++] & 0xffL) <<  8
408         |    (data[pos++] & 0xffL);
409     size -= 8;
410
411     if (pos == limit) {
412       head = segment.pop();
413       SegmentPool.recycle(segment);
414     } else {
415       segment.pos = pos;
416     }
417
418     return v;
419   }
420
421   @Override public short readShortLe() {
422     return Util.reverseBytesShort(readShort());
423   }
424
425   @Override public int readIntLe() {
426     return Util.reverseBytesInt(readInt());
427   }
428
429   @Override public long readLongLe() {
430     return Util.reverseBytesLong(readLong());
431   }
432
433   @Override public long readDecimalLong() {
434     if (size == 0) throw new IllegalStateException("size == 0");
435
436     // This value is always built negatively in order to accommodate Long.MIN_VALUE.
437     long value = 0;
438     int seen = 0;
439     boolean negative = false;
440     boolean done = false;
441
442     long overflowZone = Long.MIN_VALUE / 10;
443     long overflowDigit = (Long.MIN_VALUE % 10) + 1;
444
445     do {
446       Segment segment = head;
447
448       byte[] data = segment.data;
449       int pos = segment.pos;
450       int limit = segment.limit;
451
452       for (; pos < limit; pos++, seen++) {
453         byte b = data[pos];
454         if (b >= '0' && b <= '9') {
455           int digit = '0' - b;
456
457           // Detect when the digit would cause an overflow.
458           if (value < overflowZone || value == overflowZone && digit < overflowDigit) {
459             Buffer buffer = new Buffer().writeDecimalLong(value).writeByte(b);
460             if (!negative) buffer.readByte(); // Skip negative sign.
461             throw new NumberFormatException("Number too large: " + buffer.readUtf8());
462           }
463           value *= 10;
464           value += digit;
465         } else if (b == '-' && seen == 0) {
466           negative = true;
467           overflowDigit -= 1;
468         } else {
469           if (seen == 0) {
470             throw new NumberFormatException(
471                 "Expected leading [0-9] or '-' character but was 0x" + Integer.toHexString(b));
472           }
473           // Set a flag to stop iteration. We still need to run through segment updating below.
474           done = true;
475           break;
476         }
477       }
478
479       if (pos == limit) {
480         head = segment.pop();
481         SegmentPool.recycle(segment);
482       } else {
483         segment.pos = pos;
484       }
485     } while (!done && head != null);
486
487     size -= seen;
488     return negative ? value : -value;
489   }
490
491   @Override public long readHexadecimalUnsignedLong() {
492     if (size == 0) throw new IllegalStateException("size == 0");
493
494     long value = 0;
495     int seen = 0;
496     boolean done = false;
497
498     do {
499       Segment segment = head;
500
501       byte[] data = segment.data;
502       int pos = segment.pos;
503       int limit = segment.limit;
504
505       for (; pos < limit; pos++, seen++) {
506         int digit;
507
508         byte b = data[pos];
509         if (b >= '0' && b <= '9') {
510           digit = b - '0';
511         } else if (b >= 'a' && b <= 'f') {
512           digit = b - 'a' + 10;
513         } else if (b >= 'A' && b <= 'F') {
514           digit = b - 'A' + 10; // We never write uppercase, but we support reading it.
515         } else {
516           if (seen == 0) {
517             throw new NumberFormatException(
518                 "Expected leading [0-9a-fA-F] character but was 0x" + Integer.toHexString(b));
519           }
520           // Set a flag to stop iteration. We still need to run through segment updating below.
521           done = true;
522           break;
523         }
524
525         // Detect when the shift will overflow.
526         if ((value & 0xf000000000000000L) != 0) {
527           Buffer buffer = new Buffer().writeHexadecimalUnsignedLong(value).writeByte(b);
528           throw new NumberFormatException("Number too large: " + buffer.readUtf8());
529         }
530
531         value <<= 4;
532         value |= digit;
533       }
534
535       if (pos == limit) {
536         head = segment.pop();
537         SegmentPool.recycle(segment);
538       } else {
539         segment.pos = pos;
540       }
541     } while (!done && head != null);
542
543     size -= seen;
544     return value;
545   }
546
547   @Override public ByteString readByteString() {
548     return new ByteString(readByteArray());
549   }
550
551   @Override public ByteString readByteString(long byteCount) throws EOFException {
552     return new ByteString(readByteArray(byteCount));
553   }
554
555   @Override public int select(Options options) {
556     int index = selectPrefix(options, false);
557     if (index == -1) return -1;
558
559     // If the prefix match actually matched a full byte string, consume it and return it.
560     int selectedSize = options.byteStrings[index].size();
561     try {
562       skip(selectedSize);
563     } catch (EOFException e) {
564       throw new AssertionError();
565     }
566     return index;
567   }
568
569   /**
570    * Returns the index of a value in options that is a prefix of this buffer. Returns -1 if no value
571    * is found. This method does two simultaneous iterations: it iterates the trie and it iterates
572    * this buffer. It returns when it reaches a result in the trie, when it mismatches in the trie,
573    * and when the buffer is exhausted.
574    *
575    * @param selectTruncated true to return -2 if a possible result is present but truncated. For
576    *     example, this will return -2 if the buffer contains [ab] and the options are [abc, abd].
577    *     Note that this is made complicated by the fact that options are listed in preference order,
578    *     and one option may be a prefix of another. For example, this returns -2 if the buffer
579    *     contains [ab] and the options are [abc, a].
580    */
581   int selectPrefix(Options options, boolean selectTruncated) {
582     Segment head = this.head;
583     if (head == null) {
584       if (selectTruncated) return -2; // A result is present but truncated.
585       return options.indexOf(ByteString.EMPTY);
586     }
587
588     Segment s = head;
589     byte[] data = head.data;
590     int pos = head.pos;
591     int limit = head.limit;
592
593     int[] trie = options.trie;
594     int triePos = 0;
595
596     int prefixIndex = -1;
597
598     navigateTrie:
599     while (true) {
600       int scanOrSelect = trie[triePos++];
601
602       int possiblePrefixIndex = trie[triePos++];
603       if (possiblePrefixIndex != -1) {
604         prefixIndex = possiblePrefixIndex;
605       }
606
607       int nextStep;
608
609       if (s == null) {
610         break;
611       } else if (scanOrSelect < 0) {
612         // Scan: take multiple bytes from the buffer and the trie, looking for any mismatch.
613         int scanByteCount = -1 * scanOrSelect;
614         int trieLimit = triePos + scanByteCount;
615         while (true) {
616           int b = data[pos++] & 0xff;
617           if (b != trie[triePos++]) return prefixIndex; // Fail 'cause we found a mismatch.
618           boolean scanComplete = (triePos == trieLimit);
619
620           // Advance to the next buffer segment if this one is exhausted.
621           if (pos == limit) {
622             s = s.next;
623             pos = s.pos;
624             data = s.data;
625             limit = s.limit;
626             if (s == head) {
627               if (!scanComplete) break navigateTrie; // We were exhausted before the scan completed.
628               s = null; // We were exhausted at the end of the scan.
629             }
630           }
631
632           if (scanComplete) {
633             nextStep = trie[triePos];
634             break;
635           }
636         }
637       } else {
638         // Select: take one byte from the buffer and find a match in the trie.
639         int selectChoiceCount = scanOrSelect;
640         int b = data[pos++] & 0xff;
641         int selectLimit = triePos + selectChoiceCount;
642         while (true) {
643           if (triePos == selectLimit) return prefixIndex; // Fail 'cause we didn't find a match.
644
645           if (b == trie[triePos]) {
646             nextStep = trie[triePos + selectChoiceCount];
647             break;
648           }
649
650           triePos++;
651         }
652
653         // Advance to the next buffer segment if this one is exhausted.
654         if (pos == limit) {
655           s = s.next;
656           pos = s.pos;
657           data = s.data;
658           limit = s.limit;
659           if (s == head) {
660             s = null; // No more segments! The next trie node will be our last.
661           }
662         }
663       }
664
665       if (nextStep >= 0) return nextStep; // Found a matching option.
666       triePos = -nextStep; // Found another node to continue the search.
667     }
668
669     // We break out of the loop above when we've exhausted the buffer without exhausting the trie.
670     if (selectTruncated) return -2; // The buffer is a prefix of at least one option.
671     return prefixIndex; // Return any matches we encountered while searching for a deeper match.
672   }
673
674   @Override public void readFully(Buffer sink, long byteCount) throws EOFException {
675     if (size < byteCount) {
676       sink.write(this, size); // Exhaust ourselves.
677       throw new EOFException();
678     }
679     sink.write(this, byteCount);
680   }
681
682   @Override public long readAll(Sink sink) throws IOException {
683     long byteCount = size;
684     if (byteCount > 0) {
685       sink.write(this, byteCount);
686     }
687     return byteCount;
688   }
689
690   @Override public String readUtf8() {
691     try {
692       return readString(size, Util.UTF_8);
693     } catch (EOFException e) {
694       throw new AssertionError(e);
695     }
696   }
697
698   @Override public String readUtf8(long byteCount) throws EOFException {
699     return readString(byteCount, Util.UTF_8);
700   }
701
702   @Override public String readString(Charset charset) {
703     try {
704       return readString(size, charset);
705     } catch (EOFException e) {
706       throw new AssertionError(e);
707     }
708   }
709
710   @Override public String readString(long byteCount, Charset charset) throws EOFException {
711     checkOffsetAndCount(size, 0, byteCount);
712     if (charset == null) throw new IllegalArgumentException("charset == null");
713     if (byteCount > Integer.MAX_VALUE) {
714       throw new IllegalArgumentException("byteCount > Integer.MAX_VALUE: " + byteCount);
715     }
716     if (byteCount == 0) return "";
717
718     Segment s = head;
719     if (s.pos + byteCount > s.limit) {
720       // If the string spans multiple segments, delegate to readBytes().
721       return new String(readByteArray(byteCount), charset);
722     }
723
724     String result = new String(s.data, s.pos, (int) byteCount, charset);
725     s.pos += byteCount;
726     size -= byteCount;
727
728     if (s.pos == s.limit) {
729       head = s.pop();
730       SegmentPool.recycle(s);
731     }
732
733     return result;
734   }
735
736   @Override public @Nullable String readUtf8Line() throws EOFException {
737     long newline = indexOf((byte) '\n');
738
739     if (newline == -1) {
740       return size != 0 ? readUtf8(size) : null;
741     }
742
743     return readUtf8Line(newline);
744   }
745
746   @Override public String readUtf8LineStrict() throws EOFException {
747     return readUtf8LineStrict(Long.MAX_VALUE);
748   }
749
750   @Override public String readUtf8LineStrict(long limit) throws EOFException {
751     if (limit < 0) throw new IllegalArgumentException("limit < 0: " + limit);
752     long scanLength = limit == Long.MAX_VALUE ? Long.MAX_VALUE : limit + 1;
753     long newline = indexOf((byte) '\n', 0, scanLength);
754     if (newline != -1) return readUtf8Line(newline);
755     if (scanLength < size()
756         && getByte(scanLength - 1) == '\r' && getByte(scanLength) == '\n') {
757       return readUtf8Line(scanLength); // The line was 'limit' UTF-8 bytes followed by \r\n.
758     }
759     Buffer data = new Buffer();
760     copyTo(data, 0, Math.min(32, size()));
761     throw new EOFException("\\n not found: limit=" + Math.min(size(), limit)
762         + " content=" + data.readByteString().hex() + '…');
763   }
764
765   String readUtf8Line(long newline) throws EOFException {
766     if (newline > 0 && getByte(newline - 1) == '\r') {
767       // Read everything until '\r\n', then skip the '\r\n'.
768       String result = readUtf8((newline - 1));
769       skip(2);
770       return result;
771
772     } else {
773       // Read everything until '\n', then skip the '\n'.
774       String result = readUtf8(newline);
775       skip(1);
776       return result;
777     }
778   }
779
780   @Override public int readUtf8CodePoint() throws EOFException {
781     if (size == 0) throw new EOFException();
782
783     byte b0 = getByte(0);
784     int codePoint;
785     int byteCount;
786     int min;
787
788     if ((b0 & 0x80) == 0) {
789       // 0xxxxxxx.
790       codePoint = b0 & 0x7f;
791       byteCount = 1; // 7 bits (ASCII).
792       min = 0x0;
793
794     } else if ((b0 & 0xe0) == 0xc0) {
795       // 0x110xxxxx
796       codePoint = b0 & 0x1f;
797       byteCount = 2; // 11 bits (5 + 6).
798       min = 0x80;
799
800     } else if ((b0 & 0xf0) == 0xe0) {
801       // 0x1110xxxx
802       codePoint = b0 & 0x0f;
803       byteCount = 3; // 16 bits (4 + 6 + 6).
804       min = 0x800;
805
806     } else if ((b0 & 0xf8) == 0xf0) {
807       // 0x11110xxx
808       codePoint = b0 & 0x07;
809       byteCount = 4; // 21 bits (3 + 6 + 6 + 6).
810       min = 0x10000;
811
812     } else {
813       // We expected the first byte of a code point but got something else.
814       skip(1);
815       return REPLACEMENT_CHARACTER;
816     }
817
818     if (size < byteCount) {
819       throw new EOFException("size < " + byteCount + ": " + size
820           + " (to read code point prefixed 0x" + Integer.toHexString(b0) + ")");
821     }
822
823     // Read the continuation bytes. If we encounter a non-continuation byte, the sequence consumed
824     // thus far is truncated and is decoded as the replacement character. That non-continuation byte
825     // is left in the stream for processing by the next call to readUtf8CodePoint().
826     for (int i = 1; i < byteCount; i++) {
827       byte b = getByte(i);
828       if ((b & 0xc0) == 0x80) {
829         // 0x10xxxxxx
830         codePoint <<= 6;
831         codePoint |= b & 0x3f;
832       } else {
833         skip(i);
834         return REPLACEMENT_CHARACTER;
835       }
836     }
837
838     skip(byteCount);
839
840     if (codePoint > 0x10ffff) {
841       return REPLACEMENT_CHARACTER; // Reject code points larger than the Unicode maximum.
842     }
843
844     if (codePoint >= 0xd800 && codePoint <= 0xdfff) {
845       return REPLACEMENT_CHARACTER; // Reject partial surrogates.
846     }
847
848     if (codePoint < min) {
849       return REPLACEMENT_CHARACTER; // Reject overlong code points.
850     }
851
852     return codePoint;
853   }
854
855   @Override public byte[] readByteArray() {
856     try {
857       return readByteArray(size);
858     } catch (EOFException e) {
859       throw new AssertionError(e);
860     }
861   }
862
863   @Override public byte[] readByteArray(long byteCount) throws EOFException {
864     checkOffsetAndCount(size, 0, byteCount);
865     if (byteCount > Integer.MAX_VALUE) {
866       throw new IllegalArgumentException("byteCount > Integer.MAX_VALUE: " + byteCount);
867     }
868
869     byte[] result = new byte[(int) byteCount];
870     readFully(result);
871     return result;
872   }
873
874   @Override public int read(byte[] sink) {
875     return read(sink, 0, sink.length);
876   }
877
878   @Override public void readFully(byte[] sink) throws EOFException {
879     int offset = 0;
880     while (offset < sink.length) {
881       int read = read(sink, offset, sink.length - offset);
882       if (read == -1) throw new EOFException();
883       offset += read;
884     }
885   }
886
887   @Override public int read(byte[] sink, int offset, int byteCount) {
888     checkOffsetAndCount(sink.length, offset, byteCount);
889
890     Segment s = head;
891     if (s == null) return -1;
892     int toCopy = Math.min(byteCount, s.limit - s.pos);
893     System.arraycopy(s.data, s.pos, sink, offset, toCopy);
894
895     s.pos += toCopy;
896     size -= toCopy;
897
898     if (s.pos == s.limit) {
899       head = s.pop();
900       SegmentPool.recycle(s);
901     }
902
903     return toCopy;
904   }
905
906   @Override public int read(ByteBuffer sink) throws IOException {
907     Segment s = head;
908     if (s == null) return -1;
909
910     int toCopy = Math.min(sink.remaining(), s.limit - s.pos);
911     sink.put(s.data, s.pos, toCopy);
912
913     s.pos += toCopy;
914     size -= toCopy;
915
916     if (s.pos == s.limit) {
917       head = s.pop();
918       SegmentPool.recycle(s);
919     }
920
921     return toCopy;
922   }
923
924   /**
925    * Discards all bytes in this buffer. Calling this method when you're done
926    * with a buffer will return its segments to the pool.
927    */
928   public final void clear() {
929     try {
930       skip(size);
931     } catch (EOFException e) {
932       throw new AssertionError(e);
933     }
934   }
935
936   /** Discards {@code byteCount} bytes from the head of this buffer. */
937   @Override public void skip(long byteCount) throws EOFException {
938     while (byteCount > 0) {
939       if (head == null) throw new EOFException();
940
941       int toSkip = (int) Math.min(byteCount, head.limit - head.pos);
942       size -= toSkip;
943       byteCount -= toSkip;
944       head.pos += toSkip;
945
946       if (head.pos == head.limit) {
947         Segment toRecycle = head;
948         head = toRecycle.pop();
949         SegmentPool.recycle(toRecycle);
950       }
951     }
952   }
953
954   @Override public Buffer write(ByteString byteString) {
955     if (byteString == null) throw new IllegalArgumentException("byteString == null");
956     byteString.write(this);
957     return this;
958   }
959
960   @Override public Buffer writeUtf8(String string) {
961     return writeUtf8(string, 0, string.length());
962   }
963
964   @Override public Buffer writeUtf8(String string, int beginIndex, int endIndex) {
965     if (string == null) throw new IllegalArgumentException("string == null");
966     if (beginIndex < 0) throw new IllegalArgumentException("beginIndex < 0: " + beginIndex);
967     if (endIndex < beginIndex) {
968       throw new IllegalArgumentException("endIndex < beginIndex: " + endIndex + " < " + beginIndex);
969     }
970     if (endIndex > string.length()) {
971       throw new IllegalArgumentException(
972           "endIndex > string.length: " + endIndex + " > " + string.length());
973     }
974
975     // Transcode a UTF-16 Java String to UTF-8 bytes.
976     for (int i = beginIndex; i < endIndex;) {
977       int c = string.charAt(i);
978
979       if (c < 0x80) {
980         Segment tail = writableSegment(1);
981         byte[] data = tail.data;
982         int segmentOffset = tail.limit - i;
983         int runLimit = Math.min(endIndex, Segment.SIZE - segmentOffset);
984
985         // Emit a 7-bit character with 1 byte.
986         data[segmentOffset + i++] = (byte) c; // 0xxxxxxx
987
988         // Fast-path contiguous runs of ASCII characters. This is ugly, but yields a ~4x performance
989         // improvement over independent calls to writeByte().
990         while (i < runLimit) {
991           c = string.charAt(i);
992           if (c >= 0x80) break;
993           data[segmentOffset + i++] = (byte) c; // 0xxxxxxx
994         }
995
996         int runSize = i + segmentOffset - tail.limit; // Equivalent to i - (previous i).
997         tail.limit += runSize;
998         size += runSize;
999
1000       } else if (c < 0x800) {
1001         // Emit a 11-bit character with 2 bytes.
1002         writeByte(c >>  6        | 0xc0); // 110xxxxx
1003         writeByte(c       & 0x3f | 0x80); // 10xxxxxx
1004         i++;
1005
1006       } else if (c < 0xd800 || c > 0xdfff) {
1007         // Emit a 16-bit character with 3 bytes.
1008         writeByte(c >> 12        | 0xe0); // 1110xxxx
1009         writeByte(c >>  6 & 0x3f | 0x80); // 10xxxxxx
1010         writeByte(c       & 0x3f | 0x80); // 10xxxxxx
1011         i++;
1012
1013       } else {
1014         // c is a surrogate. Make sure it is a high surrogate & that its successor is a low
1015         // surrogate. If not, the UTF-16 is invalid, in which case we emit a replacement character.
1016         int low = i + 1 < endIndex ? string.charAt(i + 1) : 0;
1017         if (c > 0xdbff || low < 0xdc00 || low > 0xdfff) {
1018           writeByte('?');
1019           i++;
1020           continue;
1021         }
1022
1023         // UTF-16 high surrogate: 110110xxxxxxxxxx (10 bits)
1024         // UTF-16 low surrogate:  110111yyyyyyyyyy (10 bits)
1025         // Unicode code point:    00010000000000000000 + xxxxxxxxxxyyyyyyyyyy (21 bits)
1026         int codePoint = 0x010000 + ((c & ~0xd800) << 10 | low & ~0xdc00);
1027
1028         // Emit a 21-bit character with 4 bytes.
1029         writeByte(codePoint >> 18        | 0xf0); // 11110xxx
1030         writeByte(codePoint >> 12 & 0x3f | 0x80); // 10xxxxxx
1031         writeByte(codePoint >>  6 & 0x3f | 0x80); // 10xxyyyy
1032         writeByte(codePoint       & 0x3f | 0x80); // 10yyyyyy
1033         i += 2;
1034       }
1035     }
1036
1037     return this;
1038   }
1039
1040   @Override public Buffer writeUtf8CodePoint(int codePoint) {
1041     if (codePoint < 0x80) {
1042       // Emit a 7-bit code point with 1 byte.
1043       writeByte(codePoint);
1044
1045     } else if (codePoint < 0x800) {
1046       // Emit a 11-bit code point with 2 bytes.
1047       writeByte(codePoint >>  6        | 0xc0); // 110xxxxx
1048       writeByte(codePoint       & 0x3f | 0x80); // 10xxxxxx
1049
1050     } else if (codePoint < 0x10000) {
1051       if (codePoint >= 0xd800 && codePoint <= 0xdfff) {
1052         // Emit a replacement character for a partial surrogate.
1053         writeByte('?');
1054       } else {
1055         // Emit a 16-bit code point with 3 bytes.
1056         writeByte(codePoint >> 12        | 0xe0); // 1110xxxx
1057         writeByte(codePoint >>  6 & 0x3f | 0x80); // 10xxxxxx
1058         writeByte(codePoint       & 0x3f | 0x80); // 10xxxxxx
1059       }
1060
1061     } else if (codePoint <= 0x10ffff) {
1062       // Emit a 21-bit code point with 4 bytes.
1063       writeByte(codePoint >> 18        | 0xf0); // 11110xxx
1064       writeByte(codePoint >> 12 & 0x3f | 0x80); // 10xxxxxx
1065       writeByte(codePoint >>  6 & 0x3f | 0x80); // 10xxxxxx
1066       writeByte(codePoint       & 0x3f | 0x80); // 10xxxxxx
1067
1068     } else {
1069       throw new IllegalArgumentException(
1070           "Unexpected code point: " + Integer.toHexString(codePoint));
1071     }
1072
1073     return this;
1074   }
1075
1076   @Override public Buffer writeString(String string, Charset charset) {
1077     return writeString(string, 0, string.length(), charset);
1078   }
1079
1080   @Override
1081   public Buffer writeString(String string, int beginIndex, int endIndex, Charset charset) {
1082     if (string == null) throw new IllegalArgumentException("string == null");
1083     if (beginIndex < 0) throw new IllegalAccessError("beginIndex < 0: " + beginIndex);
1084     if (endIndex < beginIndex) {
1085       throw new IllegalArgumentException("endIndex < beginIndex: " + endIndex + " < " + beginIndex);
1086     }
1087     if (endIndex > string.length()) {
1088       throw new IllegalArgumentException(
1089           "endIndex > string.length: " + endIndex + " > " + string.length());
1090     }
1091     if (charset == null) throw new IllegalArgumentException("charset == null");
1092     if (charset.equals(Util.UTF_8)) return writeUtf8(string, beginIndex, endIndex);
1093     byte[] data = string.substring(beginIndex, endIndex).getBytes(charset);
1094     return write(data, 0, data.length);
1095   }
1096
1097   @Override public Buffer write(byte[] source) {
1098     if (source == null) throw new IllegalArgumentException("source == null");
1099     return write(source, 0, source.length);
1100   }
1101
1102   @Override public Buffer write(byte[] source, int offset, int byteCount) {
1103     if (source == null) throw new IllegalArgumentException("source == null");
1104     checkOffsetAndCount(source.length, offset, byteCount);
1105
1106     int limit = offset + byteCount;
1107     while (offset < limit) {
1108       Segment tail = writableSegment(1);
1109
1110       int toCopy = Math.min(limit - offset, Segment.SIZE - tail.limit);
1111       System.arraycopy(source, offset, tail.data, tail.limit, toCopy);
1112
1113       offset += toCopy;
1114       tail.limit += toCopy;
1115     }
1116
1117     size += byteCount;
1118     return this;
1119   }
1120
1121   @Override public int write(ByteBuffer source) throws IOException {
1122     if (source == null) throw new IllegalArgumentException("source == null");
1123
1124     int byteCount = source.remaining();
1125     int remaining = byteCount;
1126     while (remaining > 0) {
1127       Segment tail = writableSegment(1);
1128
1129       int toCopy = Math.min(remaining, Segment.SIZE - tail.limit);
1130       source.get(tail.data, tail.limit, toCopy);
1131
1132       remaining -= toCopy;
1133       tail.limit += toCopy;
1134     }
1135
1136     size += byteCount;
1137     return byteCount;
1138   }
1139
1140   @Override public long writeAll(Source source) throws IOException {
1141     if (source == null) throw new IllegalArgumentException("source == null");
1142     long totalBytesRead = 0;
1143     for (long readCount; (readCount = source.read(this, Segment.SIZE)) != -1; ) {
1144       totalBytesRead += readCount;
1145     }
1146     return totalBytesRead;
1147   }
1148
1149   @Override public BufferedSink write(Source source, long byteCount) throws IOException {
1150     while (byteCount > 0) {
1151       long read = source.read(this, byteCount);
1152       if (read == -1) throw new EOFException();
1153       byteCount -= read;
1154     }
1155     return this;
1156   }
1157
1158   @Override public Buffer writeByte(int b) {
1159     Segment tail = writableSegment(1);
1160     tail.data[tail.limit++] = (byte) b;
1161     size += 1;
1162     return this;
1163   }
1164
1165   @Override public Buffer writeShort(int s) {
1166     Segment tail = writableSegment(2);
1167     byte[] data = tail.data;
1168     int limit = tail.limit;
1169     data[limit++] = (byte) ((s >>> 8) & 0xff);
1170     data[limit++] = (byte)  (s        & 0xff);
1171     tail.limit = limit;
1172     size += 2;
1173     return this;
1174   }
1175
1176   @Override public Buffer writeShortLe(int s) {
1177     return writeShort(Util.reverseBytesShort((short) s));
1178   }
1179
1180   @Override public Buffer writeInt(int i) {
1181     Segment tail = writableSegment(4);
1182     byte[] data = tail.data;
1183     int limit = tail.limit;
1184     data[limit++] = (byte) ((i >>> 24) & 0xff);
1185     data[limit++] = (byte) ((i >>> 16) & 0xff);
1186     data[limit++] = (byte) ((i >>>  8) & 0xff);
1187     data[limit++] = (byte)  (i         & 0xff);
1188     tail.limit = limit;
1189     size += 4;
1190     return this;
1191   }
1192
1193   @Override public Buffer writeIntLe(int i) {
1194     return writeInt(Util.reverseBytesInt(i));
1195   }
1196
1197   @Override public Buffer writeLong(long v) {
1198     Segment tail = writableSegment(8);
1199     byte[] data = tail.data;
1200     int limit = tail.limit;
1201     data[limit++] = (byte) ((v >>> 56L) & 0xff);
1202     data[limit++] = (byte) ((v >>> 48L) & 0xff);
1203     data[limit++] = (byte) ((v >>> 40L) & 0xff);
1204     data[limit++] = (byte) ((v >>> 32L) & 0xff);
1205     data[limit++] = (byte) ((v >>> 24L) & 0xff);
1206     data[limit++] = (byte) ((v >>> 16L) & 0xff);
1207     data[limit++] = (byte) ((v >>>  8L) & 0xff);
1208     data[limit++] = (byte)  (v          & 0xff);
1209     tail.limit = limit;
1210     size += 8;
1211     return this;
1212   }
1213
1214   @Override public Buffer writeLongLe(long v) {
1215     return writeLong(reverseBytesLong(v));
1216   }
1217
1218   @Override public Buffer writeDecimalLong(long v) {
1219     if (v == 0) {
1220       // Both a shortcut and required since the following code can't handle zero.
1221       return writeByte('0');
1222     }
1223
1224     boolean negative = false;
1225     if (v < 0) {
1226       v = -v;
1227       if (v < 0) { // Only true for Long.MIN_VALUE.
1228         return writeUtf8("-9223372036854775808");
1229       }
1230       negative = true;
1231     }
1232
1233     // Binary search for character width which favors matching lower numbers.
1234     int width = //
1235           v < 100000000L
1236         ? v < 10000L
1237         ? v < 100L
1238         ? v < 10L ? 1 : 2
1239         : v < 1000L ? 3 : 4
1240         : v < 1000000L
1241         ? v < 100000L ? 5 : 6
1242         : v < 10000000L ? 7 : 8
1243         : v < 1000000000000L
1244         ? v < 10000000000L
1245         ? v < 1000000000L ? 9 : 10
1246         : v < 100000000000L ? 11 : 12
1247         : v < 1000000000000000L
1248         ? v < 10000000000000L ? 13
1249         : v < 100000000000000L ? 14 : 15
1250         : v < 100000000000000000L
1251         ? v < 10000000000000000L ? 16 : 17
1252         : v < 1000000000000000000L ? 18 : 19;
1253     if (negative) {
1254       ++width;
1255     }
1256
1257     Segment tail = writableSegment(width);
1258     byte[] data = tail.data;
1259     int pos = tail.limit + width; // We write backwards from right to left.
1260     while (v != 0) {
1261       int digit = (int) (v % 10);
1262       data[--pos] = DIGITS[digit];
1263       v /= 10;
1264     }
1265     if (negative) {
1266       data[--pos] = '-';
1267     }
1268
1269     tail.limit += width;
1270     this.size += width;
1271     return this;
1272   }
1273
1274   @Override public Buffer writeHexadecimalUnsignedLong(long v) {
1275     if (v == 0) {
1276       // Both a shortcut and required since the following code can't handle zero.
1277       return writeByte('0');
1278     }
1279
1280     int width = Long.numberOfTrailingZeros(Long.highestOneBit(v)) / 4 + 1;
1281
1282     Segment tail = writableSegment(width);
1283     byte[] data = tail.data;
1284     for (int pos = tail.limit + width - 1, start = tail.limit; pos >= start; pos--) {
1285       data[pos] = DIGITS[(int) (v & 0xF)];
1286       v >>>= 4;
1287     }
1288     tail.limit += width;
1289     size += width;
1290     return this;
1291   }
1292
1293   /**
1294    * Returns a tail segment that we can write at least {@code minimumCapacity}
1295    * bytes to, creating it if necessary.
1296    */
1297   Segment writableSegment(int minimumCapacity) {
1298     if (minimumCapacity < 1 || minimumCapacity > Segment.SIZE) throw new IllegalArgumentException();
1299
1300     if (head == null) {
1301       head = SegmentPool.take(); // Acquire a first segment.
1302       return head.next = head.prev = head;
1303     }
1304
1305     Segment tail = head.prev;
1306     if (tail.limit + minimumCapacity > Segment.SIZE || !tail.owner) {
1307       tail = tail.push(SegmentPool.take()); // Append a new empty segment to fill up.
1308     }
1309     return tail;
1310   }
1311
1312   @Override public void write(Buffer source, long byteCount) {
1313     // Move bytes from the head of the source buffer to the tail of this buffer
1314     // while balancing two conflicting goals: don't waste CPU and don't waste
1315     // memory.
1316     //
1317     //
1318     // Don't waste CPU (ie. don't copy data around).
1319     //
1320     // Copying large amounts of data is expensive. Instead, we prefer to
1321     // reassign entire segments from one buffer to the other.
1322     //
1323     //
1324     // Don't waste memory.
1325     //
1326     // As an invariant, adjacent pairs of segments in a buffer should be at
1327     // least 50% full, except for the head segment and the tail segment.
1328     //
1329     // The head segment cannot maintain the invariant because the application is
1330     // consuming bytes from this segment, decreasing its level.
1331     //
1332     // The tail segment cannot maintain the invariant because the application is
1333     // producing bytes, which may require new nearly-empty tail segments to be
1334     // appended.
1335     //
1336     //
1337     // Moving segments between buffers
1338     //
1339     // When writing one buffer to another, we prefer to reassign entire segments
1340     // over copying bytes into their most compact form. Suppose we have a buffer
1341     // with these segment levels [91%, 61%]. If we append a buffer with a
1342     // single [72%] segment, that yields [91%, 61%, 72%]. No bytes are copied.
1343     //
1344     // Or suppose we have a buffer with these segment levels: [100%, 2%], and we
1345     // want to append it to a buffer with these segment levels [99%, 3%]. This
1346     // operation will yield the following segments: [100%, 2%, 99%, 3%]. That
1347     // is, we do not spend time copying bytes around to achieve more efficient
1348     // memory use like [100%, 100%, 4%].
1349     //
1350     // When combining buffers, we will compact adjacent buffers when their
1351     // combined level doesn't exceed 100%. For example, when we start with
1352     // [100%, 40%] and append [30%, 80%], the result is [100%, 70%, 80%].
1353     //
1354     //
1355     // Splitting segments
1356     //
1357     // Occasionally we write only part of a source buffer to a sink buffer. For
1358     // example, given a sink [51%, 91%], we may want to write the first 30% of
1359     // a source [92%, 82%] to it. To simplify, we first transform the source to
1360     // an equivalent buffer [30%, 62%, 82%] and then move the head segment,
1361     // yielding sink [51%, 91%, 30%] and source [62%, 82%].
1362
1363     if (source == null) throw new IllegalArgumentException("source == null");
1364     if (source == this) throw new IllegalArgumentException("source == this");
1365     checkOffsetAndCount(source.size, 0, byteCount);
1366
1367     while (byteCount > 0) {
1368       // Is a prefix of the source's head segment all that we need to move?
1369       if (byteCount < (source.head.limit - source.head.pos)) {
1370         Segment tail = head != null ? head.prev : null;
1371         if (tail != null && tail.owner
1372             && (byteCount + tail.limit - (tail.shared ? 0 : tail.pos) <= Segment.SIZE)) {
1373           // Our existing segments are sufficient. Move bytes from source's head to our tail.
1374           source.head.writeTo(tail, (int) byteCount);
1375           source.size -= byteCount;
1376           size += byteCount;
1377           return;
1378         } else {
1379           // We're going to need another segment. Split the source's head
1380           // segment in two, then move the first of those two to this buffer.
1381           source.head = source.head.split((int) byteCount);
1382         }
1383       }
1384
1385       // Remove the source's head segment and append it to our tail.
1386       Segment segmentToMove = source.head;
1387       long movedByteCount = segmentToMove.limit - segmentToMove.pos;
1388       source.head = segmentToMove.pop();
1389       if (head == null) {
1390         head = segmentToMove;
1391         head.next = head.prev = head;
1392       } else {
1393         Segment tail = head.prev;
1394         tail = tail.push(segmentToMove);
1395         tail.compact();
1396       }
1397       source.size -= movedByteCount;
1398       size += movedByteCount;
1399       byteCount -= movedByteCount;
1400     }
1401   }
1402
1403   @Override public long read(Buffer sink, long byteCount) {
1404     if (sink == null) throw new IllegalArgumentException("sink == null");
1405     if (byteCount < 0) throw new IllegalArgumentException("byteCount < 0: " + byteCount);
1406     if (size == 0) return -1L;
1407     if (byteCount > size) byteCount = size;
1408     sink.write(this, byteCount);
1409     return byteCount;
1410   }
1411
1412   @Override public long indexOf(byte b) {
1413     return indexOf(b, 0, Long.MAX_VALUE);
1414   }
1415
1416   /**
1417    * Returns the index of {@code b} in this at or beyond {@code fromIndex}, or
1418    * -1 if this buffer does not contain {@code b} in that range.
1419    */
1420   @Override public long indexOf(byte b, long fromIndex) {
1421     return indexOf(b, fromIndex, Long.MAX_VALUE);
1422   }
1423
1424   @Override public long indexOf(byte b, long fromIndex, long toIndex) {
1425     if (fromIndex < 0 || toIndex < fromIndex) {
1426       throw new IllegalArgumentException(
1427           String.format("size=%s fromIndex=%s toIndex=%s", size, fromIndex, toIndex));
1428     }
1429
1430     if (toIndex > size) toIndex = size;
1431     if (fromIndex == toIndex) return -1L;
1432
1433     Segment s;
1434     long offset;
1435
1436     // TODO(jwilson): extract this to a shared helper method when can do so without allocating.
1437     findSegmentAndOffset: {
1438       // Pick the first segment to scan. This is the first segment with offset <= fromIndex.
1439       s = head;
1440       if (s == null) {
1441         // No segments to scan!
1442         return -1L;
1443       } else if (size - fromIndex < fromIndex) {
1444         // We're scanning in the back half of this buffer. Find the segment starting at the back.
1445         offset = size;
1446         while (offset > fromIndex) {
1447           s = s.prev;
1448           offset -= (s.limit - s.pos);
1449         }
1450       } else {
1451         // We're scanning in the front half of this buffer. Find the segment starting at the front.
1452         offset = 0L;
1453         for (long nextOffset; (nextOffset = offset + (s.limit - s.pos)) < fromIndex; ) {
1454           s = s.next;
1455           offset = nextOffset;
1456         }
1457       }
1458     }
1459
1460     // Scan through the segments, searching for b.
1461     while (offset < toIndex) {
1462       byte[] data = s.data;
1463       int limit = (int) Math.min(s.limit, s.pos + toIndex - offset);
1464       int pos = (int) (s.pos + fromIndex - offset);
1465       for (; pos < limit; pos++) {
1466         if (data[pos] == b) {
1467           return pos - s.pos + offset;
1468         }
1469       }
1470
1471       // Not in this segment. Try the next one.
1472       offset += (s.limit - s.pos);
1473       fromIndex = offset;
1474       s = s.next;
1475     }
1476
1477     return -1L;
1478   }
1479
1480   @Override public long indexOf(ByteString bytes) throws IOException {
1481     return indexOf(bytes, 0);
1482   }
1483
1484   @Override public long indexOf(ByteString bytes, long fromIndex) throws IOException {
1485     if (bytes.size() == 0) throw new IllegalArgumentException("bytes is empty");
1486     if (fromIndex < 0) throw new IllegalArgumentException("fromIndex < 0");
1487
1488     Segment s;
1489     long offset;
1490
1491     // TODO(jwilson): extract this to a shared helper method when can do so without allocating.
1492     findSegmentAndOffset: {
1493       // Pick the first segment to scan. This is the first segment with offset <= fromIndex.
1494       s = head;
1495       if (s == null) {
1496         // No segments to scan!
1497         return -1L;
1498       } else if (size - fromIndex < fromIndex) {
1499         // We're scanning in the back half of this buffer. Find the segment starting at the back.
1500         offset = size;
1501         while (offset > fromIndex) {
1502           s = s.prev;
1503           offset -= (s.limit - s.pos);
1504         }
1505       } else {
1506         // We're scanning in the front half of this buffer. Find the segment starting at the front.
1507         offset = 0L;
1508         for (long nextOffset; (nextOffset = offset + (s.limit - s.pos)) < fromIndex; ) {
1509           s = s.next;
1510           offset = nextOffset;
1511         }
1512       }
1513     }
1514
1515     // Scan through the segments, searching for the lead byte. Each time that is found, delegate to
1516     // rangeEquals() to check for a complete match.
1517     byte b0 = bytes.getByte(0);
1518     int bytesSize = bytes.size();
1519     long resultLimit = size - bytesSize + 1;
1520     while (offset < resultLimit) {
1521       // Scan through the current segment.
1522       byte[] data = s.data;
1523       int segmentLimit = (int) Math.min(s.limit, s.pos + resultLimit - offset);
1524       for (int pos = (int) (s.pos + fromIndex - offset); pos < segmentLimit; pos++) {
1525         if (data[pos] == b0 && rangeEquals(s, pos + 1, bytes, 1, bytesSize)) {
1526           return pos - s.pos + offset;
1527         }
1528       }
1529
1530       // Not in this segment. Try the next one.
1531       offset += (s.limit - s.pos);
1532       fromIndex = offset;
1533       s = s.next;
1534     }
1535
1536     return -1L;
1537   }
1538
1539   @Override public long indexOfElement(ByteString targetBytes) {
1540     return indexOfElement(targetBytes, 0);
1541   }
1542
1543   @Override public long indexOfElement(ByteString targetBytes, long fromIndex) {
1544     if (fromIndex < 0) throw new IllegalArgumentException("fromIndex < 0");
1545
1546     Segment s;
1547     long offset;
1548
1549     // TODO(jwilson): extract this to a shared helper method when can do so without allocating.
1550     findSegmentAndOffset: {
1551       // Pick the first segment to scan. This is the first segment with offset <= fromIndex.
1552       s = head;
1553       if (s == null) {
1554         // No segments to scan!
1555         return -1L;
1556       } else if (size - fromIndex < fromIndex) {
1557         // We're scanning in the back half of this buffer. Find the segment starting at the back.
1558         offset = size;
1559         while (offset > fromIndex) {
1560           s = s.prev;
1561           offset -= (s.limit - s.pos);
1562         }
1563       } else {
1564         // We're scanning in the front half of this buffer. Find the segment starting at the front.
1565         offset = 0L;
1566         for (long nextOffset; (nextOffset = offset + (s.limit - s.pos)) < fromIndex; ) {
1567           s = s.next;
1568           offset = nextOffset;
1569         }
1570       }
1571     }
1572
1573     // Special case searching for one of two bytes. This is a common case for tools like Moshi,
1574     // which search for pairs of chars like `\r` and `\n` or {@code `"` and `\`. The impact of this
1575     // optimization is a ~5x speedup for this case without a substantial cost to other cases.
1576     if (targetBytes.size() == 2) {
1577       // Scan through the segments, searching for either of the two bytes.
1578       byte b0 = targetBytes.getByte(0);
1579       byte b1 = targetBytes.getByte(1);
1580       while (offset < size) {
1581         byte[] data = s.data;
1582         for (int pos = (int) (s.pos + fromIndex - offset), limit = s.limit; pos < limit; pos++) {
1583           int b = data[pos];
1584           if (b == b0 || b == b1) {
1585             return pos - s.pos + offset;
1586           }
1587         }
1588
1589         // Not in this segment. Try the next one.
1590         offset += (s.limit - s.pos);
1591         fromIndex = offset;
1592         s = s.next;
1593       }
1594     } else {
1595       // Scan through the segments, searching for a byte that's also in the array.
1596       byte[] targetByteArray = targetBytes.internalArray();
1597       while (offset < size) {
1598         byte[] data = s.data;
1599         for (int pos = (int) (s.pos + fromIndex - offset), limit = s.limit; pos < limit; pos++) {
1600           int b = data[pos];
1601           for (byte t : targetByteArray) {
1602             if (b == t) return pos - s.pos + offset;
1603           }
1604         }
1605
1606         // Not in this segment. Try the next one.
1607         offset += (s.limit - s.pos);
1608         fromIndex = offset;
1609         s = s.next;
1610       }
1611     }
1612
1613     return -1L;
1614   }
1615
1616   @Override public boolean rangeEquals(long offset, ByteString bytes) {
1617     return rangeEquals(offset, bytes, 0, bytes.size());
1618   }
1619
1620   @Override public boolean rangeEquals(
1621       long offset, ByteString bytes, int bytesOffset, int byteCount) {
1622     if (offset < 0
1623         || bytesOffset < 0
1624         || byteCount < 0
1625         || size - offset < byteCount
1626         || bytes.size() - bytesOffset < byteCount) {
1627       return false;
1628     }
1629     for (int i = 0; i < byteCount; i++) {
1630       if (getByte(offset + i) != bytes.getByte(bytesOffset + i)) {
1631         return false;
1632       }
1633     }
1634     return true;
1635   }
1636
1637   /**
1638    * Returns true if the range within this buffer starting at {@code segmentPos} in {@code segment}
1639    * is equal to {@code bytes[bytesOffset..bytesLimit)}.
1640    */
1641   private boolean rangeEquals(
1642       Segment segment, int segmentPos, ByteString bytes, int bytesOffset, int bytesLimit) {
1643     int segmentLimit = segment.limit;
1644     byte[] data = segment.data;
1645
1646     for (int i = bytesOffset; i < bytesLimit; ) {
1647       if (segmentPos == segmentLimit) {
1648         segment = segment.next;
1649         data = segment.data;
1650         segmentPos = segment.pos;
1651         segmentLimit = segment.limit;
1652       }
1653
1654       if (data[segmentPos] != bytes.getByte(i)) {
1655         return false;
1656       }
1657
1658       segmentPos++;
1659       i++;
1660     }
1661
1662     return true;
1663   }
1664
1665   @Override public void flush() {
1666   }
1667
1668   @Override public boolean isOpen() {
1669     return true;
1670   }
1671
1672   @Override public void close() {
1673   }
1674
1675   @Override public Timeout timeout() {
1676     return Timeout.NONE;
1677   }
1678
1679   /** For testing. This returns the sizes of the segments in this buffer. */
1680   List<Integer> segmentSizes() {
1681     if (head == null) return Collections.emptyList();
1682     List<Integer> result = new ArrayList<>();
1683     result.add(head.limit - head.pos);
1684     for (Segment s = head.next; s != head; s = s.next) {
1685       result.add(s.limit - s.pos);
1686     }
1687     return result;
1688   }
1689
1690   /** Returns the 128-bit MD5 hash of this buffer. */
1691   public final ByteString md5() {
1692     return digest("MD5");
1693   }
1694
1695   /** Returns the 160-bit SHA-1 hash of this buffer. */
1696   public final ByteString sha1() {
1697     return digest("SHA-1");
1698   }
1699
1700   /** Returns the 256-bit SHA-256 hash of this buffer. */
1701   public final ByteString sha256() {
1702     return digest("SHA-256");
1703   }
1704
1705   /** Returns the 512-bit SHA-512 hash of this buffer. */
1706   public final ByteString sha512() {
1707       return digest("SHA-512");
1708   }
1709
1710   private ByteString digest(String algorithm) {
1711     try {
1712       MessageDigest messageDigest = MessageDigest.getInstance(algorithm);
1713       if (head != null) {
1714         messageDigest.update(head.data, head.pos, head.limit - head.pos);
1715         for (Segment s = head.next; s != head; s = s.next) {
1716           messageDigest.update(s.data, s.pos, s.limit - s.pos);
1717         }
1718       }
1719       return ByteString.of(messageDigest.digest());
1720     } catch (NoSuchAlgorithmException e) {
1721       throw new AssertionError();
1722     }
1723   }
1724
1725   /** Returns the 160-bit SHA-1 HMAC of this buffer. */
1726   public final ByteString hmacSha1(ByteString key) {
1727     return hmac("HmacSHA1", key);
1728   }
1729
1730   /** Returns the 256-bit SHA-256 HMAC of this buffer. */
1731   public final ByteString hmacSha256(ByteString key) {
1732     return hmac("HmacSHA256", key);
1733   }
1734
1735   /** Returns the 512-bit SHA-512 HMAC of this buffer. */
1736   public final ByteString hmacSha512(ByteString key) {
1737       return hmac("HmacSHA512", key);
1738   }
1739
1740   private ByteString hmac(String algorithm, ByteString key) {
1741     try {
1742       Mac mac = Mac.getInstance(algorithm);
1743       mac.init(new SecretKeySpec(key.toByteArray(), algorithm));
1744       if (head != null) {
1745         mac.update(head.data, head.pos, head.limit - head.pos);
1746         for (Segment s = head.next; s != head; s = s.next) {
1747           mac.update(s.data, s.pos, s.limit - s.pos);
1748         }
1749       }
1750       return ByteString.of(mac.doFinal());
1751     } catch (NoSuchAlgorithmException e) {
1752       throw new AssertionError();
1753     } catch (InvalidKeyException e) {
1754       throw new IllegalArgumentException(e);
1755     }
1756   }
1757
1758   @Override public boolean equals(Object o) {
1759     if (this == o) return true;
1760     if (!(o instanceof Buffer)) return false;
1761     Buffer that = (Buffer) o;
1762     if (size != that.size) return false;
1763     if (size == 0) return true; // Both buffers are empty.
1764
1765     Segment sa = this.head;
1766     Segment sb = that.head;
1767     int posA = sa.pos;
1768     int posB = sb.pos;
1769
1770     for (long pos = 0, count; pos < size; pos += count) {
1771       count = Math.min(sa.limit - posA, sb.limit - posB);
1772
1773       for (int i = 0; i < count; i++) {
1774         if (sa.data[posA++] != sb.data[posB++]) return false;
1775       }
1776
1777       if (posA == sa.limit) {
1778         sa = sa.next;
1779         posA = sa.pos;
1780       }
1781
1782       if (posB == sb.limit) {
1783         sb = sb.next;
1784         posB = sb.pos;
1785       }
1786     }
1787
1788     return true;
1789   }
1790
1791   @Override public int hashCode() {
1792     Segment s = head;
1793     if (s == null) return 0;
1794     int result = 1;
1795     do {
1796       for (int pos = s.pos, limit = s.limit; pos < limit; pos++) {
1797         result = 31 * result + s.data[pos];
1798       }
1799       s = s.next;
1800     } while (s != head);
1801     return result;
1802   }
1803
1804   /**
1805    * Returns a human-readable string that describes the contents of this buffer. Typically this
1806    * is a string like {@code [text=Hello]} or {@code [hex=0000ffff]}.
1807    */
1808   @Override public String toString() {
1809     return snapshot().toString();
1810   }
1811
1812   /** Returns a deep copy of this buffer. */
1813   @Override public Buffer clone() {
1814     Buffer result = new Buffer();
1815     if (size == 0) return result;
1816
1817     result.head = head.sharedCopy();
1818     result.head.next = result.head.prev = result.head;
1819     for (Segment s = head.next; s != head; s = s.next) {
1820       result.head.prev.push(s.sharedCopy());
1821     }
1822     result.size = size;
1823     return result;
1824   }
1825
1826   /** Returns an immutable copy of this buffer as a byte string. */
1827   public final ByteString snapshot() {
1828     if (size > Integer.MAX_VALUE) {
1829       throw new IllegalArgumentException("size > Integer.MAX_VALUE: " + size);
1830     }
1831     return snapshot((int) size);
1832   }
1833
1834   /**
1835    * Returns an immutable copy of the first {@code byteCount} bytes of this buffer as a byte string.
1836    */
1837   public final ByteString snapshot(int byteCount) {
1838     if (byteCount == 0) return ByteString.EMPTY;
1839     return new SegmentedByteString(this, byteCount);
1840   }
1841
1842   public final UnsafeCursor readUnsafe() {
1843     return readUnsafe(new UnsafeCursor());
1844   }
1845
1846   public final UnsafeCursor readUnsafe(UnsafeCursor unsafeCursor) {
1847     if (unsafeCursor.buffer != null) {
1848       throw new IllegalStateException("already attached to a buffer");
1849     }
1850
1851     unsafeCursor.buffer = this;
1852     unsafeCursor.readWrite = false;
1853     return unsafeCursor;
1854   }
1855
1856   public final UnsafeCursor readAndWriteUnsafe() {
1857     return readAndWriteUnsafe(new UnsafeCursor());
1858   }
1859
1860   public final UnsafeCursor readAndWriteUnsafe(UnsafeCursor unsafeCursor) {
1861     if (unsafeCursor.buffer != null) {
1862       throw new IllegalStateException("already attached to a buffer");
1863     }
1864
1865     unsafeCursor.buffer = this;
1866     unsafeCursor.readWrite = true;
1867     return unsafeCursor;
1868   }
1869
1870   /**
1871    * A handle to the underlying data in a buffer. This handle is unsafe because it does not enforce
1872    * its own invariants. Instead, it assumes a careful user who has studied Okio's implementation
1873    * details and their consequences.
1874    *
1875    * <h3>Buffer Internals</h3>
1876    *
1877    * <p>Most code should use {@code Buffer} as a black box: a class that holds 0 or more bytes of
1878    * data with efficient APIs to append data to the end and to consume data from the front. Usually
1879    * this is also the most efficient way to use buffers because it allows Okio to employ several
1880    * optimizations, including:
1881    *
1882    * <ul>
1883    *   <li><strong>Fast Allocation:</strong> Buffers use a shared pool of memory that is not
1884    *       zero-filled before use.
1885    *   <li><strong>Fast Resize:</strong> A buffer's capacity can change without copying its
1886    *       contents.
1887    *   <li><strong>Fast Move:</strong> Memory ownership can be reassigned from one buffer to
1888    *       another.
1889    *   <li><strong>Fast Copy:</strong> Multiple buffers can share the same underlying memory.
1890    *   <li><strong>Fast Encoding and Decoding:</strong> Common operations like UTF-8 encoding and
1891    *       decimal decoding do not require intermediate objects to be allocated.
1892    * </ul>
1893    *
1894    * <p>These optimizations all leverage the way Okio stores data internally. Okio Buffers are
1895    * implemented using a doubly-linked list of segments. Each segment is a contiguous range within a
1896    * 8 KiB {@code byte[]}. Each segment has two indexes, {@code start}, the offset of the first
1897    * byte of the array containing application data, and {@code end}, the offset of the first byte
1898    * beyond {@code start} whose data is undefined.
1899    *
1900    * <p>New buffers are empty and have no segments:
1901    *
1902    * <pre>   {@code
1903    *
1904    *   Buffer buffer = new Buffer();
1905    * }</pre>
1906    *
1907    * We append 7 bytes of data to the end of our empty buffer. Internally, the buffer allocates a
1908    * segment and writes its new data there. The lone segment has an 8 KiB byte array but only 7
1909    * bytes of data:
1910    *
1911    * <pre>   {@code
1912    *
1913    *   buffer.writeUtf8("sealion");
1914    *
1915    *   // [ 's', 'e', 'a', 'l', 'i', 'o', 'n', '?', '?', '?', ...]
1916    *   //    ^                                  ^
1917    *   // start = 0                          end = 7
1918    * }</pre>
1919    *
1920    * When we read 4 bytes of data from the buffer, it finds its first segment and returns that data
1921    * to us. As bytes are read the data is consumed. The segment tracks this by adjusting its
1922    * internal indices.
1923    *
1924    * <pre>   {@code
1925    *
1926    *   buffer.readUtf8(4); // "seal"
1927    *
1928    *   // [ 's', 'e', 'a', 'l', 'i', 'o', 'n', '?', '?', '?', ...]
1929    *   //                        ^              ^
1930    *   //                     start = 4      end = 7
1931    * }</pre>
1932    *
1933    * As we write data into a buffer we fill up its internal segments. When a write doesn't fit into
1934    * a buffer's last segment, additional segments are allocated and appended to the linked list of
1935    * segments. Each segment has its own start and end indexes tracking where the user's data begins
1936    * and ends.
1937    *
1938    * <pre>   {@code
1939    *
1940    *   Buffer xoxo = new Buffer();
1941    *   xoxo.writeUtf8(Strings.repeat("xo", 5_000));
1942    *
1943    *   // [ 'x', 'o', 'x', 'o', 'x', 'o', 'x', 'o', ..., 'x', 'o', 'x', 'o']
1944    *   //    ^                                                               ^
1945    *   // start = 0                                                      end = 8192
1946    *   //
1947    *   // [ 'x', 'o', 'x', 'o', ..., 'x', 'o', 'x', 'o', '?', '?', '?', ...]
1948    *   //    ^                                            ^
1949    *   // start = 0                                   end = 1808
1950    * }</pre>
1951    *
1952    * The start index is always <strong>inclusive</strong> and the end index is always
1953    * <strong>exclusive</strong>. The data preceding the start index is undefined, and the data
1954    * at and following the end index is undefined.
1955    *
1956    * <p>After the last byte of a segment has been read, that segment may be returned to an internal
1957    * segment pool. In addition to reducing the need to do garbage collection, segment pooling also
1958    * saves the JVM from needing to zero-fill byte arrays. Okio doesn't need to zero-fill its arrays
1959    * because it always writes memory before it reads it. But if you look at a segment in a debugger
1960    * you may see its effects. In this example, one of the "xoxo" segments above is reused in an
1961    * unrelated buffer:
1962    *
1963    * <pre>   {@code
1964    *
1965    *   Buffer abc = new Buffer();
1966    *   abc.writeUtf8("abc");
1967    *
1968    *   // [ 'a', 'b', 'c', 'o', 'x', 'o', 'x', 'o', ...]
1969    *   //    ^              ^
1970    *   // start = 0     end = 3
1971    * }</pre>
1972    *
1973    * There is an optimization in {@code Buffer.clone()} and other methods that allows two segments
1974    * to share the same underlying byte array. Clones can't write to the shared byte array; instead
1975    * they allocate a new (private) segment early.
1976    *
1977    * <pre>   {@code
1978    *
1979    *   Buffer nana = new Buffer();
1980    *   nana.writeUtf8(Strings.repeat("na", 2_500));
1981    *   nana.readUtf8(2); // "na"
1982    *
1983    *   // [ 'n', 'a', 'n', 'a', ..., 'n', 'a', 'n', 'a', '?', '?', '?', ...]
1984    *   //              ^                                  ^
1985    *   //           start = 0                         end = 5000
1986    *
1987    *   nana2 = nana.clone();
1988    *   nana2.writeUtf8("batman");
1989    *
1990    *   // [ 'n', 'a', 'n', 'a', ..., 'n', 'a', 'n', 'a', '?', '?', '?', ...]
1991    *   //              ^                                  ^
1992    *   //           start = 0                         end = 5000
1993    *   //
1994    *   // [ 'b', 'a', 't', 'm', 'a', 'n', '?', '?', '?', ...]
1995    *   //    ^                             ^
1996    *   //  start = 0                    end = 7
1997    * }</pre>
1998    *
1999    * Segments are not shared when the shared region is small (ie. less than 1 KiB). This is intended
2000    * to prevent fragmentation in sharing-heavy use cases.
2001    *
2002    * <h3>Unsafe Cursor API</h3>
2003    *
2004    * <p>This class exposes privileged access to the internal byte arrays of a buffer. A cursor
2005    * either references the data of a single segment, it is before the first segment ({@code
2006    * offset == -1}), or it is after the last segment ({@code offset == buffer.size}).
2007    *
2008    * <p>Call {@link #seek} to move the cursor to the segment that contains a specified offset. After
2009    * seeking, {@link #data} references the segment's internal byte array, {@link #start} is the
2010    * segment's start and {@link #end} is its end.
2011    *
2012    * <p>Call {@link #next} to advance the cursor to the next segment. This returns -1 if there are
2013    * no further segments in the buffer.
2014    *
2015    * <p>Use {@link Buffer#readUnsafe} to create a cursor to read buffer data and {@link
2016    * Buffer#readAndWriteUnsafe} to create a cursor to read and write buffer data. In either case,
2017    * always call {@link #close} when done with a cursor. This is convenient with Java 7's
2018    * try-with-resources syntax. In this example we read all of the bytes in a buffer into a byte
2019    * array:
2020    *
2021    * <pre>   {@code
2022    *
2023    *   byte[] bufferBytes = new byte[(int) buffer.size()];
2024    *
2025    *   try (UnsafeCursor cursor = buffer.readUnsafe()) {
2026    *     while (cursor.next() != -1) {
2027    *       System.arraycopy(cursor.data, cursor.start,
2028    *           bufferBytes, (int) cursor.offset, cursor.end - cursor.start);
2029    *     }
2030    *   }
2031    * }</pre>
2032    *
2033    * <p>Change the capacity of a buffer with {@link #resizeBuffer}. This is only permitted for
2034    * read+write cursors. The buffer's size always changes from the end: shrinking it removes bytes
2035    * from the end; growing it adds capacity to the end.
2036    *
2037    * <h3>Warnings</h3>
2038    *
2039    * <p>Most application developers should avoid this API. Those that must use this API should
2040    * respect these warnings.
2041    *
2042    * <p><strong>Don't mutate a cursor.</strong> This class has public, non-final fields because that
2043    * is convenient for low-level I/O frameworks. Never assign values to these fields; instead use
2044    * the cursor API to adjust these.
2045    *
2046    * <p><strong>Never mutate {@code data} unless you have read+write access.</strong> You are on the
2047    * honor system to never write the buffer in read-only mode. Read-only mode may be more efficient
2048    * than read+write mode because it does not need to make private copies of shared segments.
2049    *
2050    * <p><strong>Only access data in {@code [start..end)}.</strong> Other data in the byte array
2051    * is undefined! It may contain private or sensitive data from other parts of your process.
2052    *
2053    * <p><strong>Always fill the new capacity when you grow a buffer.</strong> New capacity is not
2054    * zero-filled and may contain data from other parts of your process. Avoid leaking this
2055    * information by always writing something to the newly-allocated capacity. Do not assume that
2056    * new capacity will be filled with {@code 0}; it will not be.
2057    *
2058    * <p><strong>Do not access a buffer while is being accessed by a cursor.</strong> Even simple
2059    * read-only operations like {@link Buffer#clone} are unsafe because they mark segments as shared.
2060    *
2061    * <p><strong>Do not hard-code the segment size in your application.</strong> It is possible that
2062    * segment sizes will change with advances in hardware. Future versions of Okio may even have
2063    * heterogeneous segment sizes.
2064    *
2065    * <p>These warnings are intended to help you to use this API safely. It's here for developers
2066    * that need absolutely the most throughput. Since that's you, here's one final performance tip.
2067    * You can reuse instances of this class if you like. Use the overloads of {@link #readUnsafe} and
2068    * {@link #readAndWriteUnsafe} that take a cursor and close it after use.
2069    */
2070   public static final class UnsafeCursor implements Closeable {
2071     public Buffer buffer;
2072     public boolean readWrite;
2073
2074     private Segment segment;
2075     public long offset = -1L;
2076     public byte[] data;
2077     public int start = -1;
2078     public int end = -1;
2079
2080     /**
2081      * Seeks to the next range of bytes, advancing the offset by {@code end - start}. Returns the
2082      * size of the readable range (at least 1), or -1 if we have reached the end of the buffer and
2083      * there are no more bytes to read.
2084      */
2085     public final int next() {
2086       if (offset == buffer.size) throw new IllegalStateException();
2087       if (offset == -1L) return seek(0L);
2088       return seek(offset + (end - start));
2089     }
2090
2091     /**
2092      * Reposition the cursor so that the data at {@code offset} is readable at {@code data[start]}.
2093      * Returns the number of bytes readable in {@code data} (at least 1), or -1 if there are no data
2094      * to read.
2095      */
2096     public final int seek(long offset) {
2097       if (offset < -1 || offset > buffer.size) {
2098         throw new ArrayIndexOutOfBoundsException(
2099             String.format("offset=%s > size=%s", offset, buffer.size));
2100       }
2101
2102       if (offset == -1 || offset == buffer.size) {
2103         this.segment = null;
2104         this.offset = offset;
2105         this.data = null;
2106         this.start = -1;
2107         this.end = -1;
2108         return -1;
2109       }
2110
2111       // Navigate to the segment that contains `offset`. Start from our current segment if possible.
2112       long min = 0L;
2113       long max = buffer.size;
2114       Segment head = buffer.head;
2115       Segment tail = buffer.head;
2116       if (this.segment != null) {
2117         long segmentOffset = this.offset - (this.start - this.segment.pos);
2118         if (segmentOffset > offset) {
2119           // Set the cursor segment to be the 'end'
2120           max = segmentOffset;
2121           tail = this.segment;
2122         } else {
2123           // Set the cursor segment to be the 'beginning'
2124           min = segmentOffset;
2125           head = this.segment;
2126         }
2127       }
2128
2129       Segment next;
2130       long nextOffset;
2131       if (max - offset > offset - min) {
2132         // Start at the 'beginning' and search forwards
2133         next = head;
2134         nextOffset = min;
2135         while (offset >= nextOffset + (next.limit - next.pos)) {
2136           nextOffset += (next.limit - next.pos);
2137           next = next.next;
2138         }
2139       } else {
2140         // Start at the 'end' and search backwards
2141         next = tail;
2142         nextOffset = max;
2143         while (nextOffset > offset) {
2144           next = next.prev;
2145           nextOffset -= (next.limit - next.pos);
2146         }
2147       }
2148
2149       // If we're going to write and our segment is shared, swap it for a read-write one.
2150       if (readWrite && next.shared) {
2151         Segment unsharedNext = next.unsharedCopy();
2152         if (buffer.head == next) {
2153           buffer.head = unsharedNext;
2154         }
2155         next = next.push(unsharedNext);
2156         next.prev.pop();
2157       }
2158
2159       // Update this cursor to the requested offset within the found segment.
2160       this.segment = next;
2161       this.offset = offset;
2162       this.data = next.data;
2163       this.start = next.pos + (int) (offset - nextOffset);
2164       this.end = next.limit;
2165       return end - start;
2166     }
2167
2168     /**
2169      * Change the size of the buffer so that it equals {@code newSize} by either adding new
2170      * capacity at the end or truncating the buffer at the end. Newly added capacity may span
2171      * multiple segments.
2172      *
2173      * <p>As a side-effect this cursor will {@link #seek seek}. If the buffer is being enlarged it
2174      * will move {@link #offset} to the first byte of newly-added capacity. This is the size of the
2175      * buffer prior to the {@code resizeBuffer()} call. If the buffer is being shrunk it will move
2176      * {@link #offset} to the end of the buffer.
2177      *
2178      * <p>Warning: it is the caller’s responsibility to write new data to every byte of the
2179      * newly-allocated capacity. Failure to do so may cause serious security problems as the data
2180      * in the returned buffers is not zero filled. Buffers may contain dirty pooled segments that
2181      * hold very sensitive data from other parts of the current process.
2182      *
2183      * @return the previous size of the buffer.
2184      */
2185     public final long resizeBuffer(long newSize) {
2186       if (buffer == null) {
2187         throw new IllegalStateException("not attached to a buffer");
2188       }
2189       if (!readWrite) {
2190         throw new IllegalStateException("resizeBuffer() only permitted for read/write buffers");
2191       }
2192
2193       long oldSize = buffer.size;
2194       if (newSize <= oldSize) {
2195         if (newSize < 0) {
2196           throw new IllegalArgumentException("newSize < 0: " + newSize);
2197         }
2198         // Shrink the buffer by either shrinking segments or removing them.
2199         for (long bytesToSubtract = oldSize - newSize; bytesToSubtract > 0; ) {
2200           Segment tail = buffer.head.prev;
2201           int tailSize = tail.limit - tail.pos;
2202           if (tailSize <= bytesToSubtract) {
2203             buffer.head = tail.pop();
2204             SegmentPool.recycle(tail);
2205             bytesToSubtract -= tailSize;
2206           } else {
2207             tail.limit -= bytesToSubtract;
2208             break;
2209           }
2210         }
2211         // Seek to the end.
2212         this.segment = null;
2213         this.offset = newSize;
2214         this.data = null;
2215         this.start = -1;
2216         this.end = -1;
2217       } else if (newSize > oldSize) {
2218         // Enlarge the buffer by either enlarging segments or adding them.
2219         boolean needsToSeek = true;
2220         for (long bytesToAdd = newSize - oldSize; bytesToAdd > 0; ) {
2221           Segment tail = buffer.writableSegment(1);
2222           int segmentBytesToAdd = (int) Math.min(bytesToAdd, Segment.SIZE - tail.limit);
2223           tail.limit += segmentBytesToAdd;
2224           bytesToAdd -= segmentBytesToAdd;
2225
2226           // If this is the first segment we're adding, seek to it.
2227           if (needsToSeek) {
2228             this.segment = tail;
2229             this.offset = oldSize;
2230             this.data = tail.data;
2231             this.start = tail.limit - segmentBytesToAdd;
2232             this.end = tail.limit;
2233             needsToSeek = false;
2234           }
2235         }
2236       }
2237
2238       buffer.size = newSize;
2239
2240       return oldSize;
2241     }
2242
2243     /**
2244      * Grow the buffer by adding a <strong>contiguous range</strong> of capacity in a single
2245      * segment. This adds at least {@code minByteCount} bytes but may add up to a full segment of
2246      * additional capacity.
2247      *
2248      * <p>As a side-effect this cursor will {@link #seek seek}. It will move {@link #offset} to the
2249      * first byte of newly-added capacity. This is the size of the buffer prior to the {@code
2250      * expandBuffer()} call.
2251      *
2252      * <p>If {@code minByteCount} bytes are available in the buffer's current tail segment that will
2253      * be used; otherwise another segment will be allocated and appended. In either case this
2254      * returns the number of bytes of capacity added to this buffer.
2255      *
2256      * <p>Warning: it is the caller’s responsibility to either write new data to every byte of the
2257      * newly-allocated capacity, or to {@link #resizeBuffer shrink} the buffer to the data written.
2258      * Failure to do so may cause serious security problems as the data in the returned buffers is
2259      * not zero filled. Buffers may contain dirty pooled segments that hold very sensitive data from
2260      * other parts of the current process.
2261      *
2262      * @param minByteCount the size of the contiguous capacity. Must be positive and not greater
2263      *     than the capacity size of a single segment (8 KiB).
2264      * @return the number of bytes expanded by. Not less than {@code minByteCount}.
2265      */
2266     public final long expandBuffer(int minByteCount) {
2267       if (minByteCount <= 0) {
2268         throw new IllegalArgumentException("minByteCount <= 0: " + minByteCount);
2269       }
2270       if (minByteCount > Segment.SIZE) {
2271         throw new IllegalArgumentException("minByteCount > Segment.SIZE: " + minByteCount);
2272       }
2273       if (buffer == null) {
2274         throw new IllegalStateException("not attached to a buffer");
2275       }
2276       if (!readWrite) {
2277         throw new IllegalStateException("expandBuffer() only permitted for read/write buffers");
2278       }
2279
2280       long oldSize = buffer.size;
2281       Segment tail = buffer.writableSegment(minByteCount);
2282       int result = Segment.SIZE - tail.limit;
2283       tail.limit = Segment.SIZE;
2284       buffer.size = oldSize + result;
2285
2286       // Seek to the old size.
2287       this.segment = tail;
2288       this.offset = oldSize;
2289       this.data = tail.data;
2290       this.start = Segment.SIZE - result;
2291       this.end = Segment.SIZE;
2292
2293       return result;
2294     }
2295
2296     @Override public void close() {
2297       // TODO(jwilson): use edit counts or other information to track unexpected changes?
2298       if (buffer == null) {
2299         throw new IllegalStateException("not attached to a buffer");
2300       }
2301
2302       buffer = null;
2303       segment = null;
2304       offset = -1L;
2305       data = null;
2306       start = -1;
2307       end = -1;
2308     }
2309   }
2310 }
2311