1 /*
2  * Copyright 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.EOFException;
19 import java.io.IOException;
20 import java.io.InputStream;
21 import java.io.ObjectInputStream;
22 import java.io.ObjectOutputStream;
23 import java.io.OutputStream;
24 import java.io.Serializable;
25 import java.lang.reflect.Field;
26 import java.nio.ByteBuffer;
27 import java.nio.charset.Charset;
28 import java.security.InvalidKeyException;
29 import java.security.MessageDigest;
30 import java.security.NoSuchAlgorithmException;
31 import java.util.Arrays;
32 import javax.annotation.Nullable;
33 import javax.crypto.Mac;
34 import javax.crypto.spec.SecretKeySpec;
35
36 import static okio.Util.arrayRangeEquals;
37 import static okio.Util.checkOffsetAndCount;
38
39 /**
40  * An immutable sequence of bytes.
41  *
42  * <p>Byte strings compare lexicographically as a sequence of <strong>unsigned</strong> bytes. That
43  * is, the byte string {@code ff} sorts after {@code 00}. This is counter to the sort order of the
44  * corresponding bytes, where {@code -1} sorts before {@code 0}.
45  *
46  * <p><strong>Full disclosure:</strong> this class provides untrusted input and output streams with
47  * raw access to the underlying byte array. A hostile stream implementation could keep a reference
48  * to the mutable byte string, violating the immutable guarantee of this class. For this reason a
49  * byte string's immutability guarantee cannot be relied upon for security in applets and other
50  * environments that run both trusted and untrusted code in the same process.
51  */
52 public class ByteString implements Serializable, Comparable<ByteString> {
53   static final char[] HEX_DIGITS =
54       { '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'a', 'b', 'c', 'd', 'e', 'f' };
55   private static final long serialVersionUID = 1L;
56
57   /** A singleton empty {@code ByteString}. */
58   public static final ByteString EMPTY = ByteString.of();
59
60   final byte[] data;
61   transient int hashCode; // Lazily computed; 0 if unknown.
62   transient String utf8; // Lazily computed.
63
64   ByteString(byte[] data) {
65     this.data = data; // Trusted internal constructor doesn't clone data.
66   }
67
68   /**
69    * Returns a new byte string containing a clone of the bytes of {@code data}.
70    */
71   public static ByteString of(byte... data) {
72     if (data == null) throw new IllegalArgumentException("data == null");
73     return new ByteString(data.clone());
74   }
75
76   /**
77    * Returns a new byte string containing a copy of {@code byteCount} bytes of {@code data} starting
78    * at {@code offset}.
79    */
80   public static ByteString of(byte[] data, int offset, int byteCount) {
81     if (data == null) throw new IllegalArgumentException("data == null");
82     checkOffsetAndCount(data.length, offset, byteCount);
83
84     byte[] copy = new byte[byteCount];
85     System.arraycopy(data, offset, copy, 0, byteCount);
86     return new ByteString(copy);
87   }
88
89   public static ByteString of(ByteBuffer data) {
90     if (data == null) throw new IllegalArgumentException("data == null");
91
92     byte[] copy = new byte[data.remaining()];
93     data.get(copy);
94     return new ByteString(copy);
95   }
96
97   /** Returns a new byte string containing the {@code UTF-8} bytes of {@code s}. */
98   public static ByteString encodeUtf8(String s) {
99     if (s == null) throw new IllegalArgumentException("s == null");
100     ByteString byteString = new ByteString(s.getBytes(Util.UTF_8));
101     byteString.utf8 = s;
102     return byteString;
103   }
104
105   /** Returns a new byte string containing the {@code charset}-encoded bytes of {@code s}. */
106   public static ByteString encodeString(String s, Charset charset) {
107     if (s == null) throw new IllegalArgumentException("s == null");
108     if (charset == null) throw new IllegalArgumentException("charset == null");
109     return new ByteString(s.getBytes(charset));
110   }
111
112   /** Constructs a new {@code String} by decoding the bytes as {@code UTF-8}. */
113   public String utf8() {
114     String result = utf8;
115     // We don't care if we double-allocate in racy code.
116     return result != null ? result : (utf8 = new String(data, Util.UTF_8));
117   }
118
119   /** Constructs a new {@code String} by decoding the bytes using {@code charset}. */
120   public String string(Charset charset) {
121     if (charset == null) throw new IllegalArgumentException("charset == null");
122     return new String(data, charset);
123   }
124
125   /**
126    * Returns this byte string encoded as <a
127    * href="http://www.ietf.org/rfc/rfc2045.txt">Base64</a>. In violation of the
128    * RFC, the returned string does not wrap lines at 76 columns.
129    */
130   public String base64() {
131     return Base64.encode(data);
132   }
133
134   /** Returns the 128-bit MD5 hash of this byte string. */
135   public ByteString md5() {
136     return digest("MD5");
137   }
138
139   /** Returns the 160-bit SHA-1 hash of this byte string. */
140   public ByteString sha1() {
141     return digest("SHA-1");
142   }
143
144   /** Returns the 256-bit SHA-256 hash of this byte string. */
145   public ByteString sha256() {
146     return digest("SHA-256");
147   }
148
149   /** Returns the 512-bit SHA-512 hash of this byte string. */
150   public ByteString sha512() {
151     return digest("SHA-512");
152   }
153
154   private ByteString digest(String algorithm) {
155     try {
156       return ByteString.of(MessageDigest.getInstance(algorithm).digest(data));
157     } catch (NoSuchAlgorithmException e) {
158       throw new AssertionError(e);
159     }
160   }
161
162   /** Returns the 160-bit SHA-1 HMAC of this byte string. */
163   public ByteString hmacSha1(ByteString key) {
164     return hmac("HmacSHA1", key);
165   }
166
167   /** Returns the 256-bit SHA-256 HMAC of this byte string. */
168   public ByteString hmacSha256(ByteString key) {
169     return hmac("HmacSHA256", key);
170   }
171
172   /** Returns the 512-bit SHA-512 HMAC of this byte string. */
173   public ByteString hmacSha512(ByteString key) {
174     return hmac("HmacSHA512", key);
175   }
176
177   private ByteString hmac(String algorithm, ByteString key) {
178     try {
179       Mac mac = Mac.getInstance(algorithm);
180       mac.init(new SecretKeySpec(key.toByteArray(), algorithm));
181       return ByteString.of(mac.doFinal(data));
182     } catch (NoSuchAlgorithmException e) {
183       throw new AssertionError(e);
184     } catch (InvalidKeyException e) {
185       throw new IllegalArgumentException(e);
186     }
187   }
188
189   /**
190    * Returns this byte string encoded as <a href="http://www.ietf.org/rfc/rfc4648.txt">URL-safe
191    * Base64</a>.
192    */
193   public String base64Url() {
194     return Base64.encodeUrl(data);
195   }
196
197   /**
198    * Decodes the Base64-encoded bytes and returns their value as a byte string.
199    * Returns null if {@code base64} is not a Base64-encoded sequence of bytes.
200    */
201   public static @Nullable ByteString decodeBase64(String base64) {
202     if (base64 == null) throw new IllegalArgumentException("base64 == null");
203     byte[] decoded = Base64.decode(base64);
204     return decoded != null ? new ByteString(decoded) : null;
205   }
206
207   /** Returns this byte string encoded in hexadecimal. */
208   public String hex() {
209     char[] result = new char[data.length * 2];
210     int c = 0;
211     for (byte b : data) {
212       result[c++] = HEX_DIGITS[(b >> 4) & 0xf];
213       result[c++] = HEX_DIGITS[b & 0xf];
214     }
215     return new String(result);
216   }
217
218   /** Decodes the hex-encoded bytes and returns their value a byte string. */
219   public static ByteString decodeHex(String hex) {
220     if (hex == null) throw new IllegalArgumentException("hex == null");
221     if (hex.length() % 2 != 0) throw new IllegalArgumentException("Unexpected hex string: " + hex);
222
223     byte[] result = new byte[hex.length() / 2];
224     for (int i = 0; i < result.length; i++) {
225       int d1 = decodeHexDigit(hex.charAt(i * 2)) << 4;
226       int d2 = decodeHexDigit(hex.charAt(i * 2 + 1));
227       result[i] = (byte) (d1 + d2);
228     }
229     return of(result);
230   }
231
232   private static int decodeHexDigit(char c) {
233     if (c >= '0' && c <= '9') return c - '0';
234     if (c >= 'a' && c <= 'f') return c - 'a' + 10;
235     if (c >= 'A' && c <= 'F') return c - 'A' + 10;
236     throw new IllegalArgumentException("Unexpected hex digit: " + c);
237   }
238
239   /**
240    * Reads {@code count} bytes from {@code in} and returns the result.
241    *
242    * @throws java.io.EOFException if {@code in} has fewer than {@code count}
243    *     bytes to read.
244    */
245   public static ByteString read(InputStream in, int byteCount) throws IOException {
246     if (in == null) throw new IllegalArgumentException("in == null");
247     if (byteCount < 0) throw new IllegalArgumentException("byteCount < 0: " + byteCount);
248
249     byte[] result = new byte[byteCount];
250     for (int offset = 0, read; offset < byteCount; offset += read) {
251       read = in.read(result, offset, byteCount - offset);
252       if (read == -1) throw new EOFException();
253     }
254     return new ByteString(result);
255   }
256
257   /**
258    * Returns a byte string equal to this byte string, but with the bytes 'A'
259    * through 'Z' replaced with the corresponding byte in 'a' through 'z'.
260    * Returns this byte string if it contains no bytes in 'A' through 'Z'.
261    */
262   public ByteString toAsciiLowercase() {
263     // Search for an uppercase character. If we don't find one, return this.
264     for (int i = 0; i < data.length; i++) {
265       byte c = data[i];
266       if (c < 'A' || c > 'Z') continue;
267
268       // If we reach this point, this string is not not lowercase. Create and
269       // return a new byte string.
270       byte[] lowercase = data.clone();
271       lowercase[i++] = (byte) (c - ('A' - 'a'));
272       for (; i < lowercase.length; i++) {
273         c = lowercase[i];
274         if (c < 'A' || c > 'Z') continue;
275         lowercase[i] = (byte) (c - ('A' - 'a'));
276       }
277       return new ByteString(lowercase);
278     }
279     return this;
280   }
281
282   /**
283    * Returns a byte string equal to this byte string, but with the bytes 'a'
284    * through 'z' replaced with the corresponding byte in 'A' through 'Z'.
285    * Returns this byte string if it contains no bytes in 'a' through 'z'.
286    */
287   public ByteString toAsciiUppercase() {
288     // Search for an lowercase character. If we don't find one, return this.
289     for (int i = 0; i < data.length; i++) {
290       byte c = data[i];
291       if (c < 'a' || c > 'z') continue;
292
293       // If we reach this point, this string is not not uppercase. Create and
294       // return a new byte string.
295       byte[] lowercase = data.clone();
296       lowercase[i++] = (byte) (c - ('a' - 'A'));
297       for (; i < lowercase.length; i++) {
298         c = lowercase[i];
299         if (c < 'a' || c > 'z') continue;
300         lowercase[i] = (byte) (c - ('a' - 'A'));
301       }
302       return new ByteString(lowercase);
303     }
304     return this;
305   }
306
307   /**
308    * Returns a byte string that is a substring of this byte string, beginning at the specified
309    * index until the end of this string. Returns this byte string if {@code beginIndex} is 0.
310    */
311   public ByteString substring(int beginIndex) {
312     return substring(beginIndex, data.length);
313   }
314
315   /**
316    * Returns a byte string that is a substring of this byte string, beginning at the specified
317    * {@code beginIndex} and ends at the specified {@code endIndex}. Returns this byte string if
318    * {@code beginIndex} is 0 and {@code endIndex} is the length of this byte string.
319    */
320   public ByteString substring(int beginIndex, int endIndex) {
321     if (beginIndex < 0) throw new IllegalArgumentException("beginIndex < 0");
322     if (endIndex > data.length) {
323       throw new IllegalArgumentException("endIndex > length(" + data.length + ")");
324     }
325
326     int subLen = endIndex - beginIndex;
327     if (subLen < 0) throw new IllegalArgumentException("endIndex < beginIndex");
328
329     if ((beginIndex == 0) && (endIndex == data.length)) {
330       return this;
331     }
332
333     byte[] copy = new byte[subLen];
334     System.arraycopy(data, beginIndex, copy, 0, subLen);
335     return new ByteString(copy);
336   }
337
338   /** Returns the byte at {@code pos}. */
339   public byte getByte(int pos) {
340     return data[pos];
341   }
342
343   /**
344    * Returns the number of bytes in this ByteString.
345    */
346   public int size() {
347     return data.length;
348   }
349
350   /**
351    * Returns a byte array containing a copy of the bytes in this {@code ByteString}.
352    */
353   public byte[] toByteArray() {
354     return data.clone();
355   }
356
357   /** Returns the bytes of this string without a defensive copy. Do not mutate! */
358   byte[] internalArray() {
359     return data;
360   }
361
362   /**
363    * Returns a {@code ByteBuffer} view of the bytes in this {@code ByteString}.
364    */
365   public ByteBuffer asByteBuffer() {
366     return ByteBuffer.wrap(data).asReadOnlyBuffer();
367   }
368
369   /** Writes the contents of this byte string to {@code out}. */
370   public void write(OutputStream out) throws IOException {
371     if (out == null) throw new IllegalArgumentException("out == null");
372     out.write(data);
373   }
374
375   /** Writes the contents of this byte string to {@code buffer}. */
376   void write(Buffer buffer) {
377     buffer.write(data, 0, data.length);
378   }
379
380   /**
381    * Returns true if the bytes of this in {@code [offset..offset+byteCount)} equal the bytes of
382    * {@code other} in {@code [otherOffset..otherOffset+byteCount)}. Returns false if either range is
383    * out of bounds.
384    */
385   public boolean rangeEquals(int offset, ByteString other, int otherOffset, int byteCount) {
386     return other.rangeEquals(otherOffset, this.data, offset, byteCount);
387   }
388
389   /**
390    * Returns true if the bytes of this in {@code [offset..offset+byteCount)} equal the bytes of
391    * {@code other} in {@code [otherOffset..otherOffset+byteCount)}. Returns false if either range is
392    * out of bounds.
393    */
394   public boolean rangeEquals(int offset, byte[] other, int otherOffset, int byteCount) {
395     return offset >= 0 && offset <= data.length - byteCount
396         && otherOffset >= 0 && otherOffset <= other.length - byteCount
397         && arrayRangeEquals(data, offset, other, otherOffset, byteCount);
398   }
399
400   public final boolean startsWith(ByteString prefix) {
401     return rangeEquals(0, prefix, 0, prefix.size());
402   }
403
404   public final boolean startsWith(byte[] prefix) {
405     return rangeEquals(0, prefix, 0, prefix.length);
406   }
407
408   public final boolean endsWith(ByteString suffix) {
409     return rangeEquals(size() - suffix.size(), suffix, 0, suffix.size());
410   }
411
412   public final boolean endsWith(byte[] suffix) {
413     return rangeEquals(size() - suffix.length, suffix, 0, suffix.length);
414   }
415
416   public final int indexOf(ByteString other) {
417     return indexOf(other.internalArray(), 0);
418   }
419
420   public final int indexOf(ByteString other, int fromIndex) {
421     return indexOf(other.internalArray(), fromIndex);
422   }
423
424   public final int indexOf(byte[] other) {
425     return indexOf(other, 0);
426   }
427
428   public int indexOf(byte[] other, int fromIndex) {
429     fromIndex = Math.max(fromIndex, 0);
430     for (int i = fromIndex, limit = data.length - other.length; i <= limit; i++) {
431       if (arrayRangeEquals(data, i, other, 0, other.length)) {
432         return i;
433       }
434     }
435     return -1;
436   }
437
438   public final int lastIndexOf(ByteString other) {
439     return lastIndexOf(other.internalArray(), size());
440   }
441
442   public final int lastIndexOf(ByteString other, int fromIndex) {
443     return lastIndexOf(other.internalArray(), fromIndex);
444   }
445
446   public final int lastIndexOf(byte[] other) {
447     return lastIndexOf(other, size());
448   }
449
450   public int lastIndexOf(byte[] other, int fromIndex) {
451     fromIndex = Math.min(fromIndex, data.length - other.length);
452     for (int i = fromIndex; i >= 0; i--) {
453       if (arrayRangeEquals(data, i, other, 0, other.length)) {
454         return i;
455       }
456     }
457     return -1;
458   }
459
460   @Override public boolean equals(Object o) {
461     if (o == this) return true;
462     return o instanceof ByteString
463         && ((ByteString) o).size() == data.length
464         && ((ByteString) o).rangeEquals(0, data, 0, data.length);
465   }
466
467   @Override public int hashCode() {
468     int result = hashCode;
469     return result != 0 ? result : (hashCode = Arrays.hashCode(data));
470   }
471
472   @Override public int compareTo(ByteString byteString) {
473     int sizeA = size();
474     int sizeB = byteString.size();
475     for (int i = 0, size = Math.min(sizeA, sizeB); i < size; i++) {
476       int byteA = getByte(i) & 0xff;
477       int byteB = byteString.getByte(i) & 0xff;
478       if (byteA == byteB) continue;
479       return byteA < byteB ? -1 : 1;
480     }
481     if (sizeA == sizeB) return 0;
482     return sizeA < sizeB ? -1 : 1;
483   }
484
485   /**
486    * Returns a human-readable string that describes the contents of this byte string. Typically this
487    * is a string like {@code [text=Hello]} or {@code [hex=0000ffff]}.
488    */
489   @Override public String toString() {
490     if (data.length == 0) {
491       return "[size=0]";
492     }
493
494     String text = utf8();
495     int i = codePointIndexToCharIndex(text, 64);
496
497     if (i == -1) {
498       return data.length <= 64
499           ? "[hex=" + hex() + "]"
500           : "[size=" + data.length + " hex=" + substring(0, 64).hex() + "…]";
501     }
502
503     String safeText = text.substring(0, i)
504         .replace("\\", "\\\\")
505         .replace("\n", "\\n")
506         .replace("\r", "\\r");
507     return i < text.length()
508         ? "[size=" + data.length + " text=" + safeText + "…]"
509         : "[text=" + safeText + "]";
510   }
511
512   static int codePointIndexToCharIndex(String s, int codePointCount) {
513     for (int i = 0, j = 0, length = s.length(), c; i < length; i += Character.charCount(c)) {
514       if (j == codePointCount) {
515         return i;
516       }
517       c = s.codePointAt(i);
518       if ((Character.isISOControl(c) && c != '\n' && c != '\r')
519           || c == Buffer.REPLACEMENT_CHARACTER) {
520         return -1;
521       }
522       j++;
523     }
524     return s.length();
525   }
526
527   private void readObject(ObjectInputStream in) throws IOException {
528     int dataLength = in.readInt();
529     ByteString byteString = ByteString.read(in, dataLength);
530     try {
531       Field field = ByteString.class.getDeclaredField("data");
532       field.setAccessible(true);
533       field.set(this, byteString.data);
534     } catch (NoSuchFieldException e) {
535       throw new AssertionError();
536     } catch (IllegalAccessException e) {
537       throw new AssertionError();
538     }
539   }
540
541   private void writeObject(ObjectOutputStream out) throws IOException {
542     out.writeInt(data.length);
543     out.write(data);
544   }
545 }
546