Initial Contribution

1 files changed, 118 insertions, 0 deletions

diff --git a/varint.c b/varint.c
new file mode 100644
index 0000000..41f6c67
--- /dev/null
+++ b/varint.c
@@ -0,0 +1,118 @@
+/* Copyright (C) 2007-2008 The Android Open Source Project
+**
+** This software is licensed under the terms of the GNU General Public
+** License version 2, as published by the Free Software Foundation, and
+** may be copied, distributed, and modified under those terms.
+**
+** This program is distributed in the hope that it will be useful,
+** but WITHOUT ANY WARRANTY; without even the implied warranty of
+** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+** GNU General Public License for more details.
+*/
+#include <inttypes.h>
+#include "varint.h"
+
+// Define some constants for powers of two.
+static const int k2Exp6 = 64;
+static const uint32_t k2Exp7 = 128;
+static const int k2Exp13 = 8192;
+static const uint32_t k2Exp14 = 16384;
+static const int k2Exp20 = (1 * 1024 * 1024);
+static const uint32_t k2Exp21 = (2 * 1024 * 1024);
+static const int k2Exp27 = (128 * 1024 * 1024);
+static const uint32_t k2Exp28 = (256 * 1024 * 1024);
+static const uint64_t k2Exp35 = (32LL * 1024LL * 1024LL * 1024LL);
+static const uint64_t k2Exp42 = (4LL * 1024LL * 1024LL * 1024LL * 1024LL);
+
+// Encodes the 64-bit value "value" using the varint encoding.  The varint
+// encoding uses a prefix followed by some data bits.  The valid prefixes
+// and the number of data bits are given in the table below.
+//
+// Prefix     Bytes  Data bits
+// 0          1      7
+// 10         2      14
+// 110        3      21
+// 1110       4      28
+// 11110      5      35
+// 111110     6      42
+// 11111100   9      64
+// 11111101   reserved
+// 11111110   reserved
+// 11111111   reserved
+char *varint_encode(uint64_t value, char *buf) {
+  if (value < k2Exp7) {
+    *buf++ = value;
+  } else if (value < k2Exp14) {
+    *buf++ = (2 << 6) | (value >> 8);
+    *buf++ = value & 0xff;
+  } else if (value < k2Exp21) {
+    *buf++ = (6 << 5) | (value >> 16);
+    *buf++ = (value >> 8) & 0xff;
+    *buf++ = value & 0xff;
+  } else if (value < k2Exp28) {
+    *buf++ = (0xe << 4) | (value >> 24);
+    *buf++ = (value >> 16) & 0xff;
+    *buf++ = (value >> 8) & 0xff;
+    *buf++ = value & 0xff;
+  } else if (value < k2Exp35) {
+    *buf++ = (0x1e << 3) | (value >> 32);
+    *buf++ = (value >> 24) & 0xff;
+    *buf++ = (value >> 16) & 0xff;
+    *buf++ = (value >> 8) & 0xff;
+    *buf++ = value & 0xff;
+  } else if (value < k2Exp42) {
+    *buf++ = (0x3e << 2) | (value >> 40);
+    *buf++ = (value >> 32) & 0xff;
+    *buf++ = (value >> 24) & 0xff;
+    *buf++ = (value >> 16) & 0xff;
+    *buf++ = (value >> 8) & 0xff;
+    *buf++ = value & 0xff;
+  } else {
+    *buf++ = (0x7e << 1);
+    *buf++ = (value >> 56) & 0xff;
+    *buf++ = (value >> 48) & 0xff;
+    *buf++ = (value >> 40) & 0xff;
+    *buf++ = (value >> 32) & 0xff;
+    *buf++ = (value >> 24) & 0xff;
+    *buf++ = (value >> 16) & 0xff;
+    *buf++ = (value >> 8) & 0xff;
+    *buf++ = value & 0xff;
+  }
+  return buf;
+}
+
+// Encodes the 35-bit signed value "value" using the varint encoding.
+// The varint encoding uses a prefix followed by some data bits.  The
+// valid prefixes and the number of data bits is given in the table
+// below.
+//
+// Prefix     Bytes  Data bits
+// 0          1      7
+// 10         2      14
+// 110        3      21
+// 1110       4      28
+// 11110      5      35
+char *varint_encode_signed(int64_t value, char *buf) {
+  if (value < k2Exp6 && value >= -k2Exp6) {
+    *buf++ = value & 0x7f;
+  } else if (value < k2Exp13 && value >= -k2Exp13) {
+    *buf++ = (2 << 6) | ((value >> 8) & 0x3f);
+    *buf++ = value & 0xff;
+  } else if (value < k2Exp20 && value >= -k2Exp20) {
+    *buf++ = (6 << 5) | ((value >> 16) & 0x1f);
+    *buf++ = (value >> 8) & 0xff;
+    *buf++ = value & 0xff;
+  } else if (value < k2Exp27 && value >= -k2Exp27) {
+    *buf++ = (0xe << 4) | ((value >> 24) & 0xf);
+    *buf++ = (value >> 16) & 0xff;
+    *buf++ = (value >> 8) & 0xff;
+    *buf++ = value & 0xff;
+  } else {
+    *buf++ = (0x1e << 3);
+    *buf++ = (value >> 24) & 0xff;
+    *buf++ = (value >> 16) & 0xff;
+    *buf++ = (value >> 8) & 0xff;
+    *buf++ = value & 0xff;
+  }
+  return buf;
+}