1 files changed, 286 insertions, 0 deletions
diff --git a/src/main/java/com/google/devtools/build/lib/util/VarInt.java b/src/main/java/com/google/devtools/build/lib/util/VarInt.java
new file mode 100644
index 0000000000..fd5daab4d4
--- /dev/null
+++ b/src/main/java/com/google/devtools/build/lib/util/VarInt.java
@@ -0,0 +1,286 @@
+// Copyright 2014 Google Inc. All rights reserved.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//    http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+package com.google.devtools.build.lib.util;
+
+import java.io.IOException;
+import java.io.InputStream;
+import java.io.OutputStream;
+import java.nio.ByteBuffer;
+
+/**
+ * Common methods to encode and decode varints and varlongs into ByteBuffers and
+ * arrays.
+ */
+public class VarInt {
+
+  /**
+   * Maximum encoded size of 32-bit positive integers (in bytes)
+   */
+  public static final int MAX_VARINT_SIZE = 5;
+
+  /**
+   * maximum encoded size of 64-bit longs, and negative 32-bit ints (in bytes)
+   */
+  public static final int MAX_VARLONG_SIZE = 10;
+
+  private VarInt() { }
+
+  /** Returns the encoding size in bytes of its input value.
+   * @param i the integer to be measured
+   * @return the encoding size in bytes of its input value
+   */
+  public static int varIntSize(int i) {
+    int result = 0;
+    do {
+      result++;
+      i >>>= 7;
+    } while (i != 0);
+    return result;
+  }
+
+  /**
+   * Reads a varint  from src, places its values into the first element of
+   * dst and returns the offset in to src of the first byte after the varint.
+   *
+   * @param src source buffer to retrieve from
+   * @param offset offset within src
+   * @param dst the resulting int value
+   * @return the updated offset after reading the varint
+   */
+  public static int getVarInt(byte[] src, int offset, int[] dst) {
+    int result = 0;
+    int shift = 0;
+    int b;
+    do {
+      if (shift >= 32) {
+        // Out of range
+        throw new IndexOutOfBoundsException("varint too long");
+      }
+      // Get 7 bits from next byte
+      b = src[offset++];
+      result |= (b & 0x7F) << shift;
+      shift += 7;
+    } while ((b & 0x80) != 0);
+    dst[0] = result;
+    return offset;
+  }
+
+  /**
+   * Encodes an integer in a variable-length encoding, 7 bits per byte, into a
+   * destination byte[], following the protocol buffer convention.
+   *
+   * @param v the int value to write to sink
+   * @param sink the sink buffer to write to
+   * @param offset the offset within sink to begin writing
+   * @return the updated offset after writing the varint
+   */
+  public static int putVarInt(int v, byte[] sink, int offset) {
+    do {
+      // Encode next 7 bits + terminator bit
+      int bits = v & 0x7F;
+      v >>>= 7;
+      byte b = (byte) (bits + ((v != 0) ? 0x80 : 0));
+      sink[offset++] = b;
+    } while (v != 0);
+    return offset;
+  }
+
+  /**
+   * Reads a varint from the current position of the given ByteBuffer and
+   * returns the decoded value as 32 bit integer.
+   *
+   * <p>The position of the buffer is advanced to the first byte after the
+   * decoded varint.
+   *
+   * @param src the ByteBuffer to get the var int from
+   * @return The integer value of the decoded varint
+   */
+  public static int getVarInt(ByteBuffer src) {
+    int tmp;
+    if ((tmp = src.get()) >= 0) {
+      return tmp;
+    }
+    int result = tmp & 0x7f;
+    if ((tmp = src.get()) >= 0) {
+      result |= tmp << 7;
+    } else {
+      result |= (tmp & 0x7f) << 7;
+      if ((tmp = src.get()) >= 0) {
+        result |= tmp << 14;
+      } else {
+        result |= (tmp & 0x7f) << 14;
+        if ((tmp = src.get()) >= 0) {
+          result |= tmp << 21;
+        } else {
+          result |= (tmp & 0x7f) << 21;
+          result |= (tmp = src.get()) << 28;
+          while (tmp < 0) {
+            // We get into this loop only in the case of overflow.
+            // By doing this, we can call getVarInt() instead of
+            // getVarLong() when we only need an int.
+            tmp = src.get();
+          }
+        }
+      }
+    }
+    return result;
+  }
+
+  /**
+   * Encodes an integer in a variable-length encoding, 7 bits per byte, to a
+   * ByteBuffer sink.
+   * @param v the value to encode
+   * @param sink the ByteBuffer to add the encoded value
+   */
+  public static void putVarInt(int v, ByteBuffer sink) {
+    while (true) {
+      int bits = v & 0x7f;
+      v >>>= 7;
+      if (v == 0) {
+        sink.put((byte) bits);
+        return;
+      }
+      sink.put((byte) (bits | 0x80));
+    }
+  }
+
+  /**
+   * Reads a varint from the given InputStream and returns the decoded value
+   * as an int.
+   *
+   * @param inputStream the InputStream to read from
+   */
+  public static int getVarInt(InputStream inputStream) throws IOException {
+    int result = 0;
+    int shift = 0;
+    int b;
+    do {
+      if (shift >= 32) {
+        // Out of range
+        throw new IndexOutOfBoundsException("varint too long");
+      }
+      // Get 7 bits from next byte
+      b = inputStream.read();
+      result |= (b & 0x7F) << shift;
+      shift += 7;
+    } while ((b & 0x80) != 0);
+    return result;
+  }
+
+  /**
+   * Encodes an integer in a variable-length encoding, 7 bits per byte, and
+   * writes it to the given OutputStream.
+   *
+   * @param v the value to encode
+   * @param outputStream the OutputStream to write to
+   */
+  public static void putVarInt(int v, OutputStream outputStream) throws IOException {
+    byte[] bytes = new byte[varIntSize(v)];
+    putVarInt(v, bytes, 0);
+    outputStream.write(bytes);
+  }
+
+  /**
+   * Returns the encoding size in bytes of its input value.
+   *
+   * @param v the long to be measured
+   * @return the encoding size in bytes of a given long value.
+   */
+  public static int varLongSize(long v) {
+    int result = 0;
+    do {
+      result++;
+      v >>>= 7;
+    } while (v != 0);
+    return result;
+  }
+
+  /**
+   * Reads an up to 64 bit long varint from the current position of the
+   * given ByteBuffer and returns the decoded value as long.
+   *
+   * <p>The position of the buffer is advanced to the first byte after the
+   * decoded varint.
+   *
+   * @param src the ByteBuffer to get the var int from
+   * @return The integer value of the decoded long varint
+   */
+  public static long getVarLong(ByteBuffer src) {
+    long tmp;
+    if ((tmp = src.get()) >= 0) {
+      return tmp;
+    }
+    long result = tmp & 0x7f;
+    if ((tmp = src.get()) >= 0) {
+      result |= tmp << 7;
+    } else {
+      result |= (tmp & 0x7f) << 7;
+      if ((tmp = src.get()) >= 0) {
+        result |= tmp << 14;
+      } else {
+        result |= (tmp & 0x7f) << 14;
+        if ((tmp = src.get()) >= 0) {
+          result |= tmp << 21;
+        } else {
+          result |= (tmp & 0x7f) << 21;
+          if ((tmp = src.get()) >= 0) {
+            result |= tmp << 28;
+          } else {
+            result |= (tmp & 0x7f) << 28;
+            if ((tmp = src.get()) >= 0) {
+              result |= tmp << 35;
+            } else {
+              result |= (tmp & 0x7f) << 35;
+              if ((tmp = src.get()) >= 0) {
+                result |= tmp << 42;
+              } else {
+                result |= (tmp & 0x7f) << 42;
+                if ((tmp = src.get()) >= 0) {
+                  result |= tmp << 49;
+                } else {
+                  result |= (tmp & 0x7f) << 49;
+                  if ((tmp = src.get()) >= 0) {
+                    result |= tmp << 56;
+                  } else {
+                    result |= (tmp & 0x7f) << 56;
+                    result |= ((long) src.get()) << 63;
+                  }
+                }
+              }
+            }
+          }
+        }
+      }
+    }
+    return result;
+  }
+
+  /**
+   * Encodes a long integer in a variable-length encoding, 7 bits per byte, to a
+   * ByteBuffer sink.
+   * @param v the value to encode
+   * @param sink the ByteBuffer to add the encoded value
+   */
+  public static void putVarLong(long v, ByteBuffer sink) {
+    while (true) {
+      int bits = ((int) v) & 0x7f;
+      v >>>= 7;
+      if (v == 0) {
+        sink.put((byte) bits);
+        return;
+      }
+      sink.put((byte) (bits | 0x80));
+    }
+  }
+}