[ostree/wip/delta: 22/24] core: Add code to read/write "varints"

[Colin Walters <walters src gnome org>]

commit 75db71e6dcb0fe252f792e3f0e26f5e971604fd4
Author: Colin Walters <walters verbum org>
Date:   Thu Aug 15 09:03:21 2013 -0400

    core: Add code to read/write "varints"
    
    Adapted from Google protobufs.  For several cases, we want to support
    e.g. file sizes up to guint64, but paying the cost of 8 bytes for each
    number is too high.
    
    This will be used for static deltas.

 Makefile-libostree.am         |    2 +
 Makefile-tests.am             |   18 ++++-
 src/libostree/ostree-varint.c |  183 +++++++++++++++++++++++++++++++++++++++++
 src/libostree/ostree-varint.h |   34 ++++++++
 tests/test-varint.c           |   69 +++++++++++++++
 5 files changed, 304 insertions(+), 2 deletions(-)
---
diff --git a/Makefile-libostree.am b/Makefile-libostree.am
index 2e799f2..197aa8e 100644
--- a/Makefile-libostree.am
+++ b/Makefile-libostree.am
@@ -36,6 +36,8 @@ libostree_1_la_SOURCES = \
        src/libostree/ostree-checksum-input-stream.h \
        src/libostree/ostree-chain-input-stream.c \
        src/libostree/ostree-chain-input-stream.h \
+       src/libostree/ostree-varint.h \
+       src/libostree/ostree-varint.c \
        src/libostree/ostree-diff.c \
        src/libostree/ostree-mutable-tree.c \
        src/libostree/ostree-repo.c \
diff --git a/Makefile-tests.am b/Makefile-tests.am
index b3d5db1..90927cb 100644
--- a/Makefile-tests.am
+++ b/Makefile-tests.am
@@ -19,6 +19,8 @@
 
 
 if BUILDOPT_INSTALL_TESTS
+insttest_PROGRAMS = 
+
 insttestdir=$(pkglibexecdir)/installed-tests
 testfiles = test-basic \
        test-archive \
@@ -35,6 +37,9 @@ testfiles = test-basic \
        $(NULL)
 insttest_SCRIPTS = $(addprefix tests/,$(testfiles:=.sh))
 
+testmetadir = $(datadir)/installed-tests/$(PACKAGE)
+testmeta_DATA = $(testfiles:=.test)
+
 insttest_DATA = tests/archive-test.sh \
        tests/pull-test.sh \
        tests/libtest.sh \
@@ -47,7 +52,16 @@ insttest_DATA = tests/archive-test.sh \
         echo 'Output=TAP' >> $  tmp; \
         mv $  tmp $@)
 
-testmetadir = $(datadir)/installed-tests/$(PACKAGE)
-testmeta_DATA = $(testfiles:=.test)
+%.test: tests/%.c Makefile
+       $(AM_V_GEN) (echo '[Test]' > $  tmp; \
+        echo 'Exec=$(pkglibexecdir)/installed-tests/$(notdir $<)' >> $  tmp; \
+        echo 'Type=session' >> $  tmp; \
+        mv $  tmp $@)
+
+insttest_PROGRAMS = test-varint
+test_varint_SOURCES = src/libostree/ostree-varint.c tests/test-varint.c
+test_varint_CFLAGS = $(ostree_bin_shared_cflags) $(OT_INTERNAL_GIO_UNIX_CFLAGS)
+test_varint_LDADD = $(ostree_bin_shared_ldadd) $(OT_INTERNAL_GIO_UNIX_LIBS)
+testmeta_DATA += test-varint.test
 
 endif
diff --git a/src/libostree/ostree-varint.c b/src/libostree/ostree-varint.c
new file mode 100644
index 0000000..04ef6b8
--- /dev/null
+++ b/src/libostree/ostree-varint.c
@@ -0,0 +1,183 @@
+/* -*- mode: C; c-file-style: "gnu"; indent-tabs-mode: nil; -*-
+ *
+ * Copyright (C) 2013 Colin Walters <walters verbum org>
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2 of the License, or (at your option) any later version.
+ *
+ * This library 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
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library; if not, write to the
+ * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
+ * Boston, MA 02111-1307, USA.
+ */
+
+/* Significant code derived from protobuf: */
+
+/*
+ * Protocol Buffers - Google's data interchange format
+ * Copyright 2008 Google Inc.  All rights reserved.
+ * http: *code.google.com/p/protobuf/
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions are
+ * met:
+ *
+ *     * Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ *     * Redistributions in binary form must reproduce the above
+ * copyright notice, this list of conditions and the following disclaimer
+ * in the documentation and/or other materials provided with the
+ * distribution.
+ *     * Neither the name of Google Inc. nor the names of its
+ * contributors may be used to endorse or promote products derived from
+ * this software without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+ * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+ * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+ * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
+ * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+ * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+ * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+ * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+ * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+*/
+
+#include "config.h"
+
+#include "ostree-varint.h"
+
+static const int max_varint_bytes = 10;
+
+/**
+ * _ostree_read_varuint64:
+ * @buf: (array length=buflen): Byte buffer
+ * @buflen: Length of bytes in @buf
+ * @bytes_read: (out): Number of bytes read
+ *
+ * Returns: An unsigned 64 bit integer value
+ */
+guint64
+_ostree_read_varuint64 (const guint8   *buf,
+                        gsize           buflen,
+                        gsize          *bytes_read)
+{
+  guint64 result = 0;
+  int count = 0;
+  guint8 b;
+  
+  /* Adapted from CodedInputStream::ReadVarint64Slow */
+
+  do
+    {
+      if (count == max_varint_bytes)
+        return FALSE;
+      if (buflen == 0)
+        return FALSE;
+
+      b = *buf;
+      result |= ((guint64)(b & 0x7F)) << (7 * count);
+      buf++;
+      buflen--;
+      ++count;
+  } while (b & 0x80);
+
+  *bytes_read = count;
+
+  return result;
+}
+
+/**
+ * _ostree_write_varuint64:
+ * @buf: Target buffer (will contain binary data)
+ * @n: Integer to encode
+ *
+ * Append a varint-encoded version of @n to @buf.
+ */
+void
+_ostree_write_varuint64 (GString *buf, guint64 n)
+{
+  /* Splitting into 32-bit pieces gives better performance on 32-bit
+   * processors. */
+  guint32 part0 = (guint32)n;
+  guint32 part1 = (guint32)(n >> 28);
+  guint32 part2 = (guint32)(n >> 56);
+  guint8 target[10];
+  int i;
+  int size;
+
+  /*
+   * Here we can't really optimize for small numbers, since the value is
+   * split into three parts.  Cheking for numbers < 128, for instance,
+   * would require three comparisons, since you'd have to make sure part1
+   * and part2 are zero.  However, if the caller is using 64-bit integers,
+   * it is likely that they expect the numbers to often be very large, so
+   * we probably don't want to optimize for small numbers anyway.  Thus,
+   * we end up with a hardcoded binary search tree...
+   */
+  if (part2 == 0) {
+    if (part1 == 0) {
+      if (part0 < (1 << 14)) {
+        if (part0 < (1 << 7)) {
+          size = 1; goto size1;
+        } else {
+          size = 2; goto size2;
+        }
+      } else {
+        if (part0 < (1 << 21)) {
+          size = 3; goto size3;
+        } else {
+          size = 4; goto size4;
+        }
+      }
+    } else {
+      if (part1 < (1 << 14)) {
+        if (part1 < (1 << 7)) {
+          size = 5; goto size5;
+        } else {
+          size = 6; goto size6;
+        }
+      } else {
+        if (part1 < (1 << 21)) {
+          size = 7; goto size7;
+        } else {
+          size = 8; goto size8;
+        }
+      }
+    }
+  } else {
+    if (part2 < (1 << 7)) {
+      size = 9; goto size9;
+    } else {
+      size = 10; goto size10;
+    }
+  }
+
+  g_assert_not_reached ();
+
+  size10: target[9] = (guint8)((part2 >>  7) | 0x80);
+  size9 : target[8] = (guint8)((part2      ) | 0x80);
+  size8 : target[7] = (guint8)((part1 >> 21) | 0x80);
+  size7 : target[6] = (guint8)((part1 >> 14) | 0x80);
+  size6 : target[5] = (guint8)((part1 >>  7) | 0x80);
+  size5 : target[4] = (guint8)((part1      ) | 0x80);
+  size4 : target[3] = (guint8)((part0 >> 21) | 0x80);
+  size3 : target[2] = (guint8)((part0 >> 14) | 0x80);
+  size2 : target[1] = (guint8)((part0 >>  7) | 0x80);
+  size1 : target[0] = (guint8)((part0      ) | 0x80);
+
+  target[size-1] &= 0x7F;
+
+  for (i = 0; i < size; i++)
+    g_string_append_c (buf, target[i]);
+}
+
diff --git a/src/libostree/ostree-varint.h b/src/libostree/ostree-varint.h
new file mode 100644
index 0000000..1a47d4d
--- /dev/null
+++ b/src/libostree/ostree-varint.h
@@ -0,0 +1,34 @@
+/* -*- mode: C; c-file-style: "gnu"; indent-tabs-mode: nil; -*-
+ *
+ * Copyright (C) 2013 Colin Walters <walters verbum org>
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2 of the License, or (at your option) any later version.
+ *
+ * This library 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
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library; if not, write to the
+ * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
+ * Boston, MA 02111-1307, USA.
+ */
+
+#pragma once
+
+#include <gio/gio.h>
+
+G_BEGIN_DECLS
+
+guint64 _ostree_read_varuint64 (const guint8   *buf,
+                                gsize           buflen,
+                                gsize          *bytes_read);
+
+void _ostree_write_varuint64 (GString *buf, guint64 n);
+
+G_END_DECLS
+
diff --git a/tests/test-varint.c b/tests/test-varint.c
new file mode 100644
index 0000000..9fbc7f3
--- /dev/null
+++ b/tests/test-varint.c
@@ -0,0 +1,69 @@
+/* -*- mode: C; c-file-style: "gnu"; indent-tabs-mode: nil; -*-
+ *
+ * Copyright (C) 2013 Colin Walters <walters verbum org>
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2 of the License, or (at your option) any later version.
+ *
+ * This library 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
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library; if not, write to the
+ * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
+ * Boston, MA 02111-1307, USA.
+ */
+
+#include "config.h"
+
+#include "libgsystem.h"
+
+#include "ostree-varint.h"
+
+static void
+check_one_roundtrip (guint64    val)
+{
+  GString *buf = g_string_new (NULL);
+  guint64 newval;
+  gsize bytes_read;
+
+  _ostree_write_varuint64 (buf, val);
+  if (g_test_verbose ())
+    {
+      gs_unref_variant GVariant *v = g_variant_new_from_data (G_VARIANT_TYPE ("ay"), buf->str, buf->len, 
TRUE, NULL, NULL);
+      gs_free char *data = g_variant_print (v, FALSE);
+      g_test_message ("%" G_GUINT64_FORMAT " -> %s", val, data);
+    }
+  newval = _ostree_read_varuint64 ((guint8*)buf->str, buf->len, &bytes_read);
+  g_assert_cmpint (bytes_read, <=, 10);
+  g_assert_cmpint (val, ==, newval);
+}
+
+static void
+test_roundtrips (void)
+{
+  const guint64 test_inputs[] = { 0, 1, 0x6F, 0xA0, 0xFF, 0xF0F0, 0xCAFE,
+                                  0xCAFEBABE, G_MAXUINT64, G_MAXUINT64-1,
+                                  G_MAXUINT64 / 2};
+  guint i;
+
+  for (i = 0; i < G_N_ELEMENTS (test_inputs); i++)
+    check_one_roundtrip (test_inputs[i]);
+}
+
+int
+main (int argc, char **argv)
+{
+
+  g_setenv ("GIO_USE_VFS", "local", TRUE);
+
+  g_test_init (&argc, &argv, NULL);
+
+  g_test_add_func ("/ostree/varint", test_roundtrips);
+
+  return g_test_run ();
+}