001/*
002 * CDDL HEADER START
003 *
004 * The contents of this file are subject to the terms of the
005 * Common Development and Distribution License, Version 1.0 only
006 * (the "License").  You may not use this file except in compliance
007 * with the License.
008 *
009 * You can obtain a copy of the license at legal-notices/CDDLv1_0.txt
010 * or http://forgerock.org/license/CDDLv1.0.html.
011 * See the License for the specific language governing permissions
012 * and limitations under the License.
013 *
014 * When distributing Covered Code, include this CDDL HEADER in each
015 * file and include the License file at legal-notices/CDDLv1_0.txt.
016 * If applicable, add the following below this CDDL HEADER, with the
017 * fields enclosed by brackets "[]" replaced with your own identifying
018 * information:
019 *      Portions Copyright [yyyy] [name of copyright owner]
020 *
021 * CDDL HEADER END
022 *
023 *
024 *      Copyright 2009 Sun Microsystems, Inc.
025 *      Portions copyright 2011-2015 ForgeRock AS
026 */
027package org.forgerock.opendj.ldap;
028
029import java.io.DataInput;
030import java.io.EOFException;
031import java.io.IOException;
032import java.io.InputStream;
033import java.io.OutputStream;
034import java.io.UnsupportedEncodingException;
035import java.nio.ByteBuffer;
036import java.nio.CharBuffer;
037import java.nio.channels.WritableByteChannel;
038import java.nio.charset.Charset;
039import java.nio.charset.CharsetDecoder;
040
041import org.forgerock.util.Reject;
042
043/**
044 * A mutable sequence of bytes backed by a byte array.
045 */
046public final class ByteStringBuilder implements ByteSequence {
047
048    /**
049     * Maximum value that can be stored with a compacted representation.
050     */
051    public static final long COMPACTED_MAX_VALUE = 0xFFFFFFFFFFFFFFL;
052
053    /** Output stream implementation. */
054    private final class OutputStreamImpl extends OutputStream {
055        @Override
056        public void close() {
057            // Do nothing.
058        }
059
060        @Override
061        public void write(final byte[] bytes) {
062            append(bytes);
063        }
064
065        @Override
066        public void write(final byte[] bytes, final int i, final int i1) {
067            append(bytes, i, i1);
068        }
069
070        @Override
071        public void write(final int i) {
072            append((byte) (i & 0xFF));
073        }
074    }
075
076    /**
077     * A sub-sequence of the parent byte string builder. The sub-sequence will
078     * be robust against all updates to the byte string builder except for
079     * invocations of the method {@code clear()}.
080     */
081    private final class SubSequence implements ByteSequence {
082
083        /** The length of the sub-sequence. */
084        private final int subLength;
085
086        /** The offset of the sub-sequence. */
087        private final int subOffset;
088
089        /**
090         * Creates a new sub-sequence.
091         *
092         * @param offset
093         *            The offset of the sub-sequence.
094         * @param length
095         *            The length of the sub-sequence.
096         */
097        private SubSequence(final int offset, final int length) {
098            this.subOffset = offset;
099            this.subLength = length;
100        }
101
102        /** {@inheritDoc} */
103        @Override
104        public ByteSequenceReader asReader() {
105            return new ByteSequenceReader(this);
106        }
107
108        /** {@inheritDoc} */
109        @Override
110        public byte byteAt(final int index) {
111            if (index >= subLength || index < 0) {
112                throw new IndexOutOfBoundsException();
113            }
114
115            // Protect against reallocation: use builder's buffer.
116            return buffer[subOffset + index];
117        }
118
119        /** {@inheritDoc} */
120        @Override
121        public int compareTo(final byte[] b, final int offset, final int length) {
122            ByteString.checkArrayBounds(b, offset, length);
123
124            // Protect against reallocation: use builder's buffer.
125            return ByteString.compareTo(buffer, subOffset, subLength, b, offset, length);
126        }
127
128        /** {@inheritDoc} */
129        @Override
130        public int compareTo(final ByteSequence o) {
131            if (this == o) {
132                return 0;
133            }
134
135            // Protect against reallocation: use builder's buffer.
136            return -o.compareTo(buffer, subOffset, subLength);
137        }
138
139        /** {@inheritDoc} */
140        @Override
141        public byte[] copyTo(final byte[] b) {
142            copyTo(b, 0);
143            return b;
144        }
145
146        /** {@inheritDoc} */
147        @Override
148        public byte[] copyTo(final byte[] b, final int offset) {
149            if (offset < 0) {
150                throw new IndexOutOfBoundsException();
151            }
152
153            // Protect against reallocation: use builder's buffer.
154            System.arraycopy(buffer, subOffset, b, offset, Math.min(subLength, b.length - offset));
155            return b;
156        }
157
158        /** {@inheritDoc} */
159        @Override
160        public ByteBuffer copyTo(final ByteBuffer byteBuffer) {
161            byteBuffer.put(buffer, subOffset, subLength);
162            byteBuffer.flip();
163            return byteBuffer;
164        }
165
166        /** {@inheritDoc} */
167        @Override
168        public ByteStringBuilder copyTo(final ByteStringBuilder builder) {
169            // Protect against reallocation: use builder's buffer.
170            return builder.append(buffer, subOffset, subLength);
171        }
172
173        /** {@inheritDoc} */
174        @Override
175        public boolean copyTo(CharBuffer charBuffer, CharsetDecoder decoder) {
176            return ByteString.copyTo(ByteBuffer.wrap(buffer, subOffset, subLength), charBuffer, decoder);
177        }
178
179        /** {@inheritDoc} */
180        @Override
181        public OutputStream copyTo(final OutputStream stream) throws IOException {
182            // Protect against reallocation: use builder's buffer.
183            stream.write(buffer, subOffset, subLength);
184            return stream;
185        }
186
187        /** {@inheritDoc} */
188        @Override
189        public boolean equals(final byte[] b, final int offset, final int length) {
190            ByteString.checkArrayBounds(b, offset, length);
191
192            // Protect against reallocation: use builder's buffer.
193            return ByteString.equals(buffer, subOffset, subLength, b, offset, length);
194        }
195
196        /** {@inheritDoc} */
197        @Override
198        public boolean equals(final Object o) {
199            if (this == o) {
200                return true;
201            } else if (o instanceof ByteSequence) {
202                final ByteSequence other = (ByteSequence) o;
203
204                // Protect against reallocation: use builder's buffer.
205                return other.equals(buffer, subOffset, subLength);
206            } else {
207                return false;
208            }
209        }
210
211        /** {@inheritDoc} */
212        @Override
213        public int hashCode() {
214            // Protect against reallocation: use builder's buffer.
215            return ByteString.hashCode(buffer, subOffset, subLength);
216        }
217
218        @Override
219        public boolean isEmpty() {
220            return length == 0;
221        }
222
223        /** {@inheritDoc} */
224        @Override
225        public int length() {
226            return subLength;
227        }
228
229        /** {@inheritDoc} */
230        @Override
231        public ByteSequence subSequence(final int start, final int end) {
232            if (start < 0 || start > end || end > subLength) {
233                throw new IndexOutOfBoundsException();
234            }
235
236            return new SubSequence(subOffset + start, end - start);
237        }
238
239        /** {@inheritDoc} */
240        @Override
241        public boolean startsWith(ByteSequence prefix) {
242            if (prefix == null || prefix.length() > length) {
243                return false;
244            }
245            return prefix.equals(buffer, 0, prefix.length());
246        }
247
248        /** {@inheritDoc} */
249        @Override
250        public String toBase64String() {
251            return Base64.encode(this);
252        }
253
254        /** {@inheritDoc} */
255        @Override
256        public byte[] toByteArray() {
257            return copyTo(new byte[subLength]);
258        }
259
260        /** {@inheritDoc} */
261        @Override
262        public ByteString toByteString() {
263            // Protect against reallocation: use builder's buffer.
264            final byte[] b = new byte[subLength];
265            System.arraycopy(buffer, subOffset, b, 0, subLength);
266            return ByteString.wrap(b);
267        }
268
269        /** {@inheritDoc} */
270        @Override
271        public String toString() {
272            // Protect against reallocation: use builder's buffer.
273            return ByteString.toString(buffer, subOffset, subLength);
274        }
275    }
276
277    // These are package private so that compression and crypto
278    // functionality may directly access the fields.
279
280    /** The buffer where data is stored. */
281    byte[] buffer;
282
283    /** The number of bytes to expose from the buffer. */
284    int length;
285
286    /**
287     * The lazily allocated output stream view of this builder. Synchronization
288     * is not necessary because the stream is stateless and race conditions can
289     * be tolerated.
290     */
291    private OutputStreamImpl os;
292
293    /**
294     * Creates a new byte string builder with an initial capacity of 32 bytes.
295     */
296    public ByteStringBuilder() {
297        // Initially create a 32 byte buffer.
298        this(32);
299    }
300
301    /**
302     * Creates a new byte string builder with the specified initial capacity.
303     *
304     * @param capacity
305     *            The initial capacity.
306     * @throws IllegalArgumentException
307     *             If the {@code capacity} is negative.
308     */
309    public ByteStringBuilder(final int capacity) {
310        Reject.ifFalse(capacity >= 0, "capacity must be >= 0");
311        this.buffer = new byte[capacity];
312        this.length = 0;
313    }
314
315    /**
316     * Creates a new byte string builder with the content of the provided
317     * ByteSequence. Its capacity is set to the length of the provided
318     * ByteSequence.
319     *
320     * @param bs
321     *            The ByteSequence to copy
322     */
323    public ByteStringBuilder(final ByteSequence bs) {
324        this(bs.length());
325        bs.copyTo(this);
326    }
327
328    /**
329     * Appends the provided byte to this byte string builder.
330     *
331     * @param b
332     *            The byte to be appended to this byte string builder.
333     * @return This byte string builder.
334     */
335    public ByteStringBuilder append(final byte b) {
336        ensureAdditionalCapacity(1);
337        buffer[length++] = b;
338        return this;
339    }
340
341    /**
342     * Appends the provided byte array to this byte string builder.
343     * <p>
344     * An invocation of the form:
345     *
346     * <pre>
347     * src.append(bytes)
348     * </pre>
349     *
350     * Behaves in exactly the same way as the invocation:
351     *
352     * <pre>
353     * src.append(bytes, 0, bytes.length);
354     * </pre>
355     *
356     * @param bytes
357     *            The byte array to be appended to this byte string builder.
358     * @return This byte string builder.
359     */
360    public ByteStringBuilder append(final byte[] bytes) {
361        return append(bytes, 0, bytes.length);
362    }
363
364    /**
365     * Appends the provided byte array to this byte string builder.
366     *
367     * @param bytes
368     *            The byte array to be appended to this byte string builder.
369     * @param offset
370     *            The offset of the byte array to be used; must be non-negative
371     *            and no larger than {@code bytes.length} .
372     * @param length
373     *            The length of the byte array to be used; must be non-negative
374     *            and no larger than {@code bytes.length - offset}.
375     * @return This byte string builder.
376     * @throws IndexOutOfBoundsException
377     *             If {@code offset} is negative or if {@code length} is
378     *             negative or if {@code offset + length} is greater than
379     *             {@code bytes.length}.
380     */
381    public ByteStringBuilder append(final byte[] bytes, final int offset, final int length) {
382        ByteString.checkArrayBounds(bytes, offset, length);
383
384        if (length != 0) {
385            ensureAdditionalCapacity(length);
386            System.arraycopy(bytes, offset, buffer, this.length, length);
387            this.length += length;
388        }
389
390        return this;
391    }
392
393    /**
394     * Appends the provided {@code ByteBuffer} to this byte string builder.
395     *
396     * @param buffer
397     *            The byte buffer to be appended to this byte string builder.
398     * @param length
399     *            The number of bytes to be appended from {@code buffer}.
400     * @return This byte string builder.
401     * @throws IndexOutOfBoundsException
402     *             If {@code length} is less than zero or greater than
403     *             {@code buffer.remaining()}.
404     */
405    public ByteStringBuilder append(final ByteBuffer buffer, final int length) {
406        if (length < 0 || length > buffer.remaining()) {
407            throw new IndexOutOfBoundsException();
408        }
409
410        if (length != 0) {
411            ensureAdditionalCapacity(length);
412            buffer.get(this.buffer, this.length, length);
413            this.length += length;
414        }
415
416        return this;
417    }
418
419    /**
420     * Appends the provided {@link ByteSequence} to this byte string builder.
421     *
422     * @param bytes
423     *            The byte sequence to be appended to this byte string builder.
424     * @return This byte string builder.
425     */
426    public ByteStringBuilder append(final ByteSequence bytes) {
427        return bytes.copyTo(this);
428    }
429
430    /**
431     * Appends the provided {@link ByteSequenceReader} to this byte string
432     * builder.
433     *
434     * @param reader
435     *            The byte sequence reader to be appended to this byte string
436     *            builder.
437     * @param length
438     *            The number of bytes to be appended from {@code reader}.
439     * @return This byte string builder.
440     * @throws IndexOutOfBoundsException
441     *             If {@code length} is less than zero or greater than
442     *             {@code reader.remaining()}.
443     */
444    public ByteStringBuilder append(final ByteSequenceReader reader, final int length) {
445        if (length < 0 || length > reader.remaining()) {
446            throw new IndexOutOfBoundsException();
447        }
448
449        if (length != 0) {
450            ensureAdditionalCapacity(length);
451            reader.get(buffer, this.length, length);
452            this.length += length;
453        }
454
455        return this;
456    }
457
458    /**
459     * Appends the UTF-8 encoded bytes of the provided char array to this byte
460     * string builder.
461     *
462     * @param chars
463     *            The char array whose UTF-8 encoding is to be appended to this
464     *            byte string builder.
465     * @return This byte string builder.
466     */
467    public ByteStringBuilder append(final char[] chars) {
468        if (chars == null) {
469            return this;
470        }
471
472        // Assume that each char is 1 byte
473        final int len = chars.length;
474        ensureAdditionalCapacity(len);
475
476        for (int i = 0; i < len; i++) {
477            final char c = chars[i];
478            final byte b = (byte) (c & 0x0000007F);
479
480            if (c == b) {
481                buffer[this.length + i] = b;
482            } else {
483                // There is a multi-byte char. Defer to JDK.
484                final Charset utf8 = Charset.forName("UTF-8");
485                final ByteBuffer byteBuffer = utf8.encode(CharBuffer.wrap(chars));
486                final int remaining = byteBuffer.remaining();
487                ensureAdditionalCapacity(remaining - len);
488                byteBuffer.get(buffer, this.length, remaining);
489                this.length += remaining;
490                return this;
491            }
492        }
493
494        // The 1 byte char assumption was correct
495        this.length += len;
496        return this;
497    }
498
499    /**
500     * Appends the provided {@code DataInput} to this byte string
501     * builder.
502     *
503     * @param stream
504     *          The data input stream to be appended to this byte string
505     *          builder.
506     * @param length
507     *          The maximum number of bytes to be appended from {@code
508     *          input}.
509     * @throws IndexOutOfBoundsException
510     *           If {@code length} is less than zero.
511     * @throws EOFException
512     *           If this stream reaches the end before reading all the bytes.
513     * @throws IOException
514     *           If an I/O error occurs.
515     */
516    public void append(DataInput stream, int length) throws EOFException, IOException {
517        if (length < 0) {
518            throw new IndexOutOfBoundsException();
519        }
520
521        ensureAdditionalCapacity(length);
522        stream.readFully(buffer, this.length, length);
523        this.length += length;
524    }
525
526    /**
527     * Appends the provided {@code InputStream} to this byte string builder.
528     *
529     * @param stream
530     *            The input stream to be appended to this byte string builder.
531     * @param length
532     *            The maximum number of bytes to be appended from {@code buffer}
533     *            .
534     * @return The number of bytes read from the input stream, or {@code -1} if
535     *         the end of the input stream has been reached.
536     * @throws IndexOutOfBoundsException
537     *             If {@code length} is less than zero.
538     * @throws IOException
539     *             If an I/O error occurs.
540     */
541    public int append(final InputStream stream, final int length) throws IOException {
542        if (length < 0) {
543            throw new IndexOutOfBoundsException();
544        }
545
546        ensureAdditionalCapacity(length);
547        final int bytesRead = stream.read(buffer, this.length, length);
548        if (bytesRead > 0) {
549            this.length += bytesRead;
550        }
551
552        return bytesRead;
553    }
554
555    /**
556     * Appends the big-endian encoded bytes of the provided integer to this byte
557     * string builder.
558     *
559     * @param i
560     *            The integer whose big-endian encoding is to be appended to
561     *            this byte string builder.
562     * @return This byte string builder.
563     */
564    public ByteStringBuilder append(int i) {
565        ensureAdditionalCapacity(4);
566        for (int j = length + 3; j >= length; j--) {
567            buffer[j] = (byte) (i & 0xFF);
568            i >>>= 8;
569        }
570        length += 4;
571        return this;
572    }
573
574    /**
575     * Appends the big-endian encoded bytes of the provided long to this byte
576     * string builder.
577     *
578     * @param l
579     *            The long whose big-endian encoding is to be appended to this
580     *            byte string builder.
581     * @return This byte string builder.
582     */
583    public ByteStringBuilder append(long l) {
584        ensureAdditionalCapacity(8);
585        for (int i = length + 7; i >= length; i--) {
586            buffer[i] = (byte) (l & 0xFF);
587            l >>>= 8;
588        }
589        length += 8;
590        return this;
591    }
592
593    /**
594     * Appends the compact encoded bytes of the provided unsigned long to this byte
595     * string builder. This method allows to encode unsigned long up to 56 bits using
596     * fewer bytes (from 1 to 8) than append(long). The encoding has the important
597     * property that it preserves ordering, so it can be used for keys.
598     *
599     * @param value
600     *            The long whose compact encoding is to be appended to this
601     *            byte string builder.
602     * @return This byte string builder.
603     */
604    public ByteStringBuilder appendCompactUnsigned(long value) {
605        Reject.ifFalse(value >= 0, "value must be >= 0");
606
607        final int size = getEncodedSize(value);
608        ensureAdditionalCapacity(size);
609        switch (size) {
610        case 1:
611            buffer[length++] = (byte) value;
612            break;
613        case 2:
614            buffer[length++] = (byte) ((value >>> 8) | 0x80L);
615            buffer[length++] = l2b(value);
616            break;
617        case 3:
618            buffer[length++] = (byte) ((value >>> 16) | 0xc0L);
619            buffer[length++] = l2b(value >>> 8);
620            buffer[length++] = l2b(value);
621            break;
622        case 4:
623            buffer[length++] = (byte) ((value >>> 24) | 0xe0L);
624            buffer[length++] = l2b(value >>> 16);
625            buffer[length++] = l2b(value >>> 8);
626            buffer[length++] = l2b(value);
627            break;
628        case 5:
629            buffer[length++] = (byte) ((value >>> 32) | 0xf0L);
630            buffer[length++] = l2b(value >>> 24);
631            buffer[length++] = l2b(value >>> 16);
632            buffer[length++] = l2b(value >>> 8);
633            buffer[length++] = l2b(value);
634            break;
635        case 6:
636            buffer[length++] = (byte) ((value >>> 40) | 0xf8L);
637            buffer[length++] = l2b(value >>> 32);
638            buffer[length++] = l2b(value >>> 24);
639            buffer[length++] = l2b(value >>> 16);
640            buffer[length++] = l2b(value >>> 8);
641            buffer[length++] = l2b(value);
642            break;
643        case 7:
644            buffer[length++] = (byte) ((value >>> 48) | 0xfcL);
645            buffer[length++] = l2b(value >>> 40);
646            buffer[length++] = l2b(value >>> 32);
647            buffer[length++] = l2b(value >>> 24);
648            buffer[length++] = l2b(value >>> 16);
649            buffer[length++] = l2b(value >>> 8);
650            buffer[length++] = l2b(value);
651            break;
652        default:
653            buffer[length++] = (byte) 0xfe;
654            buffer[length++] = l2b(value >>> 48);
655            buffer[length++] = l2b(value >>> 40);
656            buffer[length++] = l2b(value >>> 32);
657            buffer[length++] = l2b(value >>> 24);
658            buffer[length++] = l2b(value >>> 16);
659            buffer[length++] = l2b(value >>> 8);
660            buffer[length++] = l2b(value);
661            break;
662        }
663        return this;
664    }
665
666    private static int getEncodedSize(long value) {
667        if (value < 0x80L) {
668            return 1;
669        } else if (value < 0x4000L) {
670            return 2;
671        } else if (value < 0x200000L) {
672            return 3;
673        } else if (value < 0x10000000L) {
674            return 4;
675        } else if (value < 0x800000000L) {
676            return 5;
677        } else if (value < 0x40000000000L) {
678            return 6;
679        } else if (value < 0x2000000000000L) {
680            return 7;
681        } else if (value < 0x100000000000000L) {
682            return 8;
683        } else {
684            throw new IllegalArgumentException("value out of range: " + value);
685        }
686    }
687
688    private static byte l2b(long value) {
689        return (byte) (value & 0xffL);
690    }
691
692    /**
693     * Appends the byte string representation of the provided object to this
694     * byte string builder. The object is converted to a byte string as follows:
695     * <ul>
696     * <li>if the object is an instance of {@code ByteSequence} then this method
697     * is equivalent to calling {@link #append(ByteSequence)}
698     * <li>if the object is a {@code byte[]} then this method is equivalent to
699     * calling {@link #append(byte[])}
700     * <li>if the object is a {@code char[]} then this method is equivalent to
701     * calling {@link #append(char[])}
702     * <li>for all other types of object this method is equivalent to calling
703     * {@link #append(String)} with the {@code toString()} representation of the
704     * provided object.
705     * </ul>
706     * <b>Note:</b> this method treats {@code Long} and {@code Integer} objects
707     * like any other type of {@code Object}. More specifically, the following
708     * invocations are not equivalent:
709     * <ul>
710     * <li>{@code append(0)} is not equivalent to {@code append((Object) 0)}
711     * <li>{@code append(0L)} is not equivalent to {@code append((Object) 0L)}
712     * </ul>
713     *
714     * @param o
715     *            The object to be appended to this byte string builder.
716     * @return This byte string builder.
717     */
718    public ByteStringBuilder append(final Object o) {
719        if (o == null) {
720            return this;
721        } else if (o instanceof ByteSequence) {
722            return append((ByteSequence) o);
723        } else if (o instanceof byte[]) {
724            return append((byte[]) o);
725        } else if (o instanceof char[]) {
726            return append((char[]) o);
727        } else {
728            return append(o.toString());
729        }
730    }
731
732    /**
733     * Appends the big-endian encoded bytes of the provided short to this byte
734     * string builder.
735     *
736     * @param i
737     *            The short whose big-endian encoding is to be appended to this
738     *            byte string builder.
739     * @return This byte string builder.
740     */
741    public ByteStringBuilder append(short i) {
742        ensureAdditionalCapacity(2);
743        for (int j = length + 1; j >= length; j--) {
744            buffer[j] = (byte) (i & 0xFF);
745            i >>>= 8;
746        }
747        length += 2;
748        return this;
749    }
750
751    /**
752     * Appends the UTF-8 encoded bytes of the provided string to this byte
753     * string builder.
754     *
755     * @param s
756     *            The string whose UTF-8 encoding is to be appended to this byte
757     *            string builder.
758     * @return This byte string builder.
759     */
760    public ByteStringBuilder append(final String s) {
761        if (s == null) {
762            return this;
763        }
764
765        // Assume that each char is 1 byte
766        final int len = s.length();
767        ensureAdditionalCapacity(len);
768
769        for (int i = 0; i < len; i++) {
770            final char c = s.charAt(i);
771            final byte b = (byte) (c & 0x0000007F);
772
773            if (c == b) {
774                buffer[this.length + i] = b;
775            } else {
776                // There is a multi-byte char. Defer to JDK
777                try {
778                    return append(s.getBytes("UTF-8"));
779                } catch (final UnsupportedEncodingException e) {
780                    // TODO: I18N
781                    throw new RuntimeException("Unable to encode String '" + s + "' to UTF-8 bytes", e);
782                }
783            }
784        }
785
786        // The 1 byte char assumption was correct
787        this.length += len;
788        return this;
789    }
790
791    /**
792     * Appends the ASN.1 BER length encoding representation of the provided
793     * integer to this byte string builder.
794     *
795     * @param length
796     *            The value to encode using the BER length encoding rules.
797     * @return This byte string builder.
798     */
799    public ByteStringBuilder appendBERLength(final int length) {
800        if ((length & 0x0000007F) == length) {
801            ensureAdditionalCapacity(1);
802
803            buffer[this.length++] = (byte) (length & 0xFF);
804        } else if ((length & 0x000000FF) == length) {
805            ensureAdditionalCapacity(2);
806
807            buffer[this.length++] = (byte) 0x81;
808            buffer[this.length++] = (byte) (length & 0xFF);
809        } else if ((length & 0x0000FFFF) == length) {
810            ensureAdditionalCapacity(3);
811
812            buffer[this.length++] = (byte) 0x82;
813            buffer[this.length++] = (byte) (length >> 8 & 0xFF);
814            buffer[this.length++] = (byte) (length & 0xFF);
815        } else if ((length & 0x00FFFFFF) == length) {
816            ensureAdditionalCapacity(4);
817
818            buffer[this.length++] = (byte) 0x83;
819            buffer[this.length++] = (byte) (length >> 16 & 0xFF);
820            buffer[this.length++] = (byte) (length >> 8 & 0xFF);
821            buffer[this.length++] = (byte) (length & 0xFF);
822        } else {
823            ensureAdditionalCapacity(5);
824
825            buffer[this.length++] = (byte) 0x84;
826            buffer[this.length++] = (byte) (length >> 24 & 0xFF);
827            buffer[this.length++] = (byte) (length >> 16 & 0xFF);
828            buffer[this.length++] = (byte) (length >> 8 & 0xFF);
829            buffer[this.length++] = (byte) (length & 0xFF);
830        }
831        return this;
832    }
833
834    /**
835     * Returns an {@link OutputStream} whose write operations append data to
836     * this byte string builder. The returned output stream will never throw an
837     * {@link IOException} and its {@link OutputStream#close() close} method
838     * does not do anything.
839     *
840     * @return An {@link OutputStream} whose write operations append data to
841     *         this byte string builder.
842     */
843    public OutputStream asOutputStream() {
844        if (os == null) {
845            os = new OutputStreamImpl();
846        }
847        return os;
848    }
849
850    /**
851     * Returns a {@link ByteSequenceReader} which can be used to incrementally
852     * read and decode data from this byte string builder.
853     * <p>
854     * <b>NOTE:</b> all concurrent updates to this byte string builder are
855     * supported with the exception of {@link #clear()}. Any invocations of
856     * {@link #clear()} must be accompanied by a subsequent call to
857     * {@code ByteSequenceReader.rewind()}.
858     *
859     * @return The {@link ByteSequenceReader} which can be used to incrementally
860     *         read and decode data from this byte string builder.
861     * @see #clear()
862     */
863    @Override
864    public ByteSequenceReader asReader() {
865        return new ByteSequenceReader(this);
866    }
867
868    /** {@inheritDoc} */
869    @Override
870    public byte byteAt(final int index) {
871        if (index >= length || index < 0) {
872            throw new IndexOutOfBoundsException();
873        }
874        return buffer[index];
875    }
876
877    /**
878     * Returns the current capacity of this byte string builder. The capacity
879     * may increase as more data is appended.
880     *
881     * @return The current capacity of this byte string builder.
882     */
883    public int capacity() {
884        return buffer.length;
885    }
886
887    /**
888     * Sets the length of this byte string builder to zero.
889     * <p>
890     * <b>NOTE:</b> if this method is called, then
891     * {@code ByteSequenceReader.rewind()} must also be called on any associated
892     * byte sequence readers in order for them to remain valid.
893     *
894     * @return This byte string builder.
895     * @see #asReader()
896     */
897    public ByteStringBuilder clear() {
898        length = 0;
899        return this;
900    }
901
902    /**
903     * Sets the length of this byte string builder to zero, and resets the
904     * capacity to the specified size if above provided threshold.
905     * <p>
906     * <b>NOTE:</b> if this method is called, then
907     * {@code ByteSequenceReader.rewind()} must also be called on any associated
908     * byte sequence readers in order for them to remain valid.
909     *
910     * @param thresholdCapacity
911     *             The threshold capacity triggering a truncate
912     * @param newCapacity
913     *            The new capacity.
914     * @return This byte string builder.
915     * @throws IllegalArgumentException
916     *             If the {@code newCapacity} is negative or the {@code newCapacity}
917     *             is bigger than the {@code thresholdCapacity}.
918     * @see #asReader()
919     */
920    public ByteStringBuilder clearAndTruncate(int thresholdCapacity, int newCapacity) {
921        if (newCapacity > thresholdCapacity) {
922            throw new IllegalArgumentException("new capacity '" + newCapacity
923                    + "' cannot be bigger than threshold capacity '" + thresholdCapacity + "'");
924        }
925        if (newCapacity < 0) {
926            throw new IllegalArgumentException("new capacity '" + newCapacity + "' cannot be negative.");
927        }
928        if (buffer.length > thresholdCapacity) {
929            // garbage collect excessively large buffers
930            buffer = new byte[newCapacity];
931        }
932        length = 0;
933        return this;
934    }
935
936    /** {@inheritDoc} */
937    @Override
938    public int compareTo(final byte[] bytes, final int offset, final int length) {
939        ByteString.checkArrayBounds(bytes, offset, length);
940        return ByteString.compareTo(this.buffer, 0, this.length, bytes, offset, length);
941    }
942
943    /** {@inheritDoc} */
944    @Override
945    public int compareTo(final ByteSequence o) {
946        if (this == o) {
947            return 0;
948        }
949        return -o.compareTo(buffer, 0, length);
950    }
951
952    /** {@inheritDoc} */
953    @Override
954    public byte[] copyTo(final byte[] bytes) {
955        copyTo(bytes, 0);
956        return bytes;
957    }
958
959    /** {@inheritDoc} */
960    @Override
961    public byte[] copyTo(final byte[] bytes, final int offset) {
962        if (offset < 0) {
963            throw new IndexOutOfBoundsException();
964        }
965        System.arraycopy(buffer, 0, bytes, offset, Math.min(length, bytes.length - offset));
966        return bytes;
967    }
968
969    /** {@inheritDoc} */
970    @Override
971    public ByteBuffer copyTo(final ByteBuffer byteBuffer) {
972        byteBuffer.put(buffer, 0, length);
973        byteBuffer.flip();
974        return byteBuffer;
975    }
976
977    /** {@inheritDoc} */
978    @Override
979    public ByteStringBuilder copyTo(final ByteStringBuilder builder) {
980        builder.append(buffer, 0, length);
981        return builder;
982    }
983
984    /** {@inheritDoc} */
985    @Override
986    public boolean copyTo(CharBuffer charBuffer, CharsetDecoder decoder) {
987        return ByteString.copyTo(ByteBuffer.wrap(buffer, 0, length), charBuffer, decoder);
988    }
989
990    /** {@inheritDoc} */
991    @Override
992    public OutputStream copyTo(final OutputStream stream) throws IOException {
993        stream.write(buffer, 0, length);
994        return stream;
995    }
996
997    /**
998     * Copies the entire contents of this byte string to the provided
999     * {@code WritableByteChannel}.
1000     *
1001     * @param channel
1002     *            The {@code WritableByteChannel} to copy to.
1003     * @return The number of bytes written, possibly zero
1004     * @throws IOException
1005     *             If some other I/O error occurs
1006     * @see WritableByteChannel#write(java.nio.ByteBuffer)
1007     */
1008    public int copyTo(WritableByteChannel channel) throws IOException {
1009        return channel.write(ByteBuffer.wrap(buffer, 0, length));
1010    }
1011
1012    /**
1013     * Ensures that the specified number of additional bytes will fit in this
1014     * byte string builder and resizes it if necessary.
1015     *
1016     * @param size
1017     *            The number of additional bytes.
1018     * @return This byte string builder.
1019     */
1020    public ByteStringBuilder ensureAdditionalCapacity(final int size) {
1021        final int newCount = this.length + size;
1022        if (newCount > buffer.length) {
1023            final byte[] newbuffer = new byte[Math.max(buffer.length << 1, newCount)];
1024            System.arraycopy(buffer, 0, newbuffer, 0, buffer.length);
1025            buffer = newbuffer;
1026        }
1027        return this;
1028    }
1029
1030    /** {@inheritDoc} */
1031    @Override
1032    public boolean equals(final byte[] bytes, final int offset, final int length) {
1033        ByteString.checkArrayBounds(bytes, offset, length);
1034        return ByteString.equals(this.buffer, 0, this.length, bytes, offset, length);
1035    }
1036
1037    /**
1038     * Indicates whether the provided object is equal to this byte string
1039     * builder. In order for it to be considered equal, the provided object must
1040     * be a byte sequence containing the same bytes in the same order.
1041     *
1042     * @param o
1043     *            The object for which to make the determination.
1044     * @return {@code true} if the provided object is a byte sequence whose
1045     *         content is equal to that of this byte string builder, or
1046     *         {@code false} if not.
1047     */
1048    @Override
1049    public boolean equals(final Object o) {
1050        if (this == o) {
1051            return true;
1052        } else if (o instanceof ByteSequence) {
1053            final ByteSequence other = (ByteSequence) o;
1054            return other.equals(buffer, 0, length);
1055        } else {
1056            return false;
1057        }
1058    }
1059
1060    /**
1061     * Returns the byte array that backs this byte string builder. Modifications
1062     * to this byte string builder's content may cause the returned array's
1063     * content to be modified, and vice versa.
1064     * <p>
1065     * Note that the length of the returned array is only guaranteed to be the
1066     * same as the length of this byte string builder immediately after a call
1067     * to {@link #trimToSize()}.
1068     * <p>
1069     * In addition, subsequent modifications to this byte string builder may
1070     * cause the backing byte array to be reallocated thus decoupling the
1071     * returned byte array from this byte string builder.
1072     *
1073     * @return The byte array that backs this byte string builder.
1074     */
1075    public byte[] getBackingArray() {
1076        return buffer;
1077    }
1078
1079    /**
1080     * Returns a hash code for this byte string builder. It will be the sum of
1081     * all of the bytes contained in the byte string builder.
1082     * <p>
1083     * <b>NOTE:</b> subsequent changes to this byte string builder will
1084     * invalidate the returned hash code.
1085     *
1086     * @return A hash code for this byte string builder.
1087     */
1088    @Override
1089    public int hashCode() {
1090        return ByteString.hashCode(buffer, 0, length);
1091    }
1092
1093    /** {@inheritDoc} */
1094    @Override
1095    public boolean isEmpty() {
1096        return length == 0;
1097    }
1098
1099    /** {@inheritDoc} */
1100    @Override
1101    public int length() {
1102        return length;
1103    }
1104
1105    /**
1106     * Sets the byte value at the specified index.
1107     * <p>
1108     * An index ranges from zero to {@code length() - 1}. The first byte value
1109     * of the sequence is at index zero, the next at index one, and so on, as
1110     * for array indexing.
1111     *
1112     * @param index
1113     *            The index of the byte to be set.
1114     * @param b
1115     *            The byte to set on this byte string builder.
1116     * @throws IndexOutOfBoundsException
1117     *             If the index argument is negative or not less than length().
1118     */
1119    public void setByte(final int index, final byte b) {
1120        if (index >= length || index < 0) {
1121            throw new IndexOutOfBoundsException();
1122        }
1123        buffer[index] = b;
1124    }
1125
1126    /**
1127     * Sets the length of this byte string builder.
1128     * <p>
1129     * If the <code>newLength</code> argument is less than the current length,
1130     * the length is changed to the specified length.
1131     * <p>
1132     * If the <code>newLength</code> argument is greater than or equal to the
1133     * current length, then the capacity is increased and sufficient null bytes
1134     * are appended so that length becomes the <code>newLength</code> argument.
1135     * <p>
1136     * The <code>newLength</code> argument must be greater than or equal to
1137     * <code>0</code>.
1138     *
1139     * @param newLength
1140     *            The new length.
1141     * @return This byte string builder.
1142     * @throws IndexOutOfBoundsException
1143     *             If the <code>newLength</code> argument is negative.
1144     */
1145    public ByteStringBuilder setLength(final int newLength) {
1146        if (newLength < 0) {
1147            throw new IndexOutOfBoundsException("Negative newLength: " + newLength);
1148        }
1149
1150        if (newLength > length) {
1151            ensureAdditionalCapacity(newLength - length);
1152
1153            // Pad with zeros.
1154            for (int i = length; i < newLength; i++) {
1155                buffer[i] = 0;
1156            }
1157        }
1158        length = newLength;
1159
1160        return this;
1161    }
1162
1163    /**
1164     * Returns a new byte sequence that is a subsequence of this byte sequence.
1165     * <p>
1166     * The subsequence starts with the byte value at the specified {@code start}
1167     * index and ends with the byte value at index {@code end - 1}. The length
1168     * (in bytes) of the returned sequence is {@code end - start}, so if
1169     * {@code start
1170     * == end} then an empty sequence is returned.
1171     * <p>
1172     * <b>NOTE:</b> the returned sub-sequence will be robust against all updates
1173     * to the byte string builder except for invocations of the method
1174     * {@link #clear()}. If a permanent immutable byte sequence is required then
1175     * callers should invoke {@code toByteString()} on the returned byte
1176     * sequence.
1177     *
1178     * @param start
1179     *            The start index, inclusive.
1180     * @param end
1181     *            The end index, exclusive.
1182     * @return The newly created byte subsequence.
1183     */
1184    @Override
1185    public ByteSequence subSequence(final int start, final int end) {
1186        if (start < 0 || start > end || end > length) {
1187            throw new IndexOutOfBoundsException();
1188        }
1189
1190        return new SubSequence(start, end - start);
1191    }
1192
1193    /** {@inheritDoc} */
1194    @Override
1195    public boolean startsWith(ByteSequence prefix) {
1196        if (prefix == null || prefix.length() > length) {
1197            return false;
1198        }
1199        return prefix.equals(buffer, 0, prefix.length());
1200    }
1201
1202    /** {@inheritDoc} */
1203    @Override
1204    public String toBase64String() {
1205        return Base64.encode(this);
1206    }
1207
1208    /** {@inheritDoc} */
1209    @Override
1210    public byte[] toByteArray() {
1211        return copyTo(new byte[length]);
1212    }
1213
1214    /**
1215     * Returns the {@link ByteString} representation of this byte string
1216     * builder. Subsequent changes to this byte string builder will not modify
1217     * the returned {@link ByteString}.
1218     *
1219     * @return The {@link ByteString} representation of this byte sequence.
1220     */
1221    @Override
1222    public ByteString toByteString() {
1223        final byte[] b = new byte[length];
1224        System.arraycopy(buffer, 0, b, 0, length);
1225        return ByteString.wrap(b);
1226    }
1227
1228    /** {@inheritDoc} */
1229    @Override
1230    public String toString() {
1231        return ByteString.toString(buffer, 0, length);
1232    }
1233
1234    /**
1235     * Attempts to reduce storage used for this byte string builder. If the
1236     * buffer is larger than necessary to hold its current sequence of bytes,
1237     * then it may be resized to become more space efficient.
1238     *
1239     * @return This byte string builder.
1240     */
1241    public ByteStringBuilder trimToSize() {
1242        if (buffer.length > length) {
1243            final byte[] newBuffer = new byte[length];
1244            System.arraycopy(buffer, 0, newBuffer, 0, length);
1245            buffer = newBuffer;
1246        }
1247        return this;
1248    }
1249}