Add the extension packets

Introduce the subprotocol ("Einsof"), its prototype serialization and
parsing functions, and its first set of messages.

These messages are carriers of public-key authentication mechanism which
involves client request, server challenge, and client response. An
"ident" message is used to tell a compatible server that you support a
particular version of the subprotocol.

Note: the functions that handle encoding are very specialized.
They're not representative of how the wire format should be generally
handled, and were written this way because the first set of messages is
tiny and simple enough.

1 files changed, 140 insertions, 0 deletions

diff --git a/src/vli.c b/src/vli.c
new file mode 100644
index 0000000..98625e1
--- /dev/null
+++ b/src/vli.c
@@ -0,0 +1,140 @@
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+// Variable-length integer (VLI) implementation.
+// Derived from the MLIR bytecode variable-width integers.
+// https://mlir.llvm.org/docs/BytecodeFormat/#variable-width-integers
+//
+// Prefixed little-endian varint. Trailing zero bits of the first byte specify
+// how many additional bytes to read. Once read, the value is shifted right by
+// the number of bytes read to discard these length-encoding bits and restore
+// the original integer.
+//
+// xxxxxxx1                   <-> 0xxxxxxx
+// yyyyyyyy xxxxxx10          <-> 00yyyyyy yyxxxxxx
+// zzzzzzzz yyyyyyyy xxxxx100 <-> 000zzzzz zzzyyyyy yyyxxxxx
+// ...
+//
+// Considerably more efficient than continuation-bit variants like VLQ or
+// LEB128.
+//
+// Two bounded versions: 32 and 64 bits.
+//
+// Signed integers use zigzag encoding.
+
+#include "vli.h"
+
+// Prefer hardware/compiler intrinsics; fallback to de Bruijn sequence voodoo.
+static size_t count_trailing_zeros(uint32_t x)
+{
+#if defined(__clang__) || defined(__GNUC__)
+    return (size_t)__builtin_ctz(x);
+#elif defined(_MSC_VER)
+    unsigned long Index;
+    _BitScanForward(&Index, x);
+    return Index;
+#else
+    static const uint8_t seq[32] = {
+        0,  1,  28, 2,  29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4,  8,
+        31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6,  11, 5,  10, 9
+    };
+    return seq[((x & -x) * 0x77cb531) >> 27];
+#endif
+}
+
+size_t vli64_encode(uint8_t *p, uint64_t u)
+{
+    if ((u >> 7) == 0) {
+        p[0] = (uint8_t)(u << 1 | 0x1);
+        return 1;
+    }
+    uint64_t shift = u >> 7;
+    for (size_t bytes = 2; bytes < 9; ++bytes) {
+        if ((shift >>= 7) == 0) {
+            uint64_t encoded = (u << 1 | 0x1) << (bytes - 1);
+            memcpy(p, &encoded, bytes);
+            return bytes;
+        }
+    }
+    p[0] = 0;
+    memcpy(p + 1, &u, sizeof(u));
+    return 9;
+}
+
+size_t vli64_decode(uint8_t const *p, uint64_t *u)
+{
+    *u = p[0];
+    if (*u & 1) {
+        *u >>= 1;
+        return 1;
+    }
+    if (*u == 0) {
+        memcpy(u, p + 1, sizeof(*u));
+        return 1 + sizeof(*u);
+    }
+    size_t bytes = count_trailing_zeros((uint32_t)(*u));
+    memcpy((uint8_t *)u + 1, p + 1, bytes);
+    *u >>= (bytes + 1);
+    return 1 + bytes;
+}
+
+size_t vli64_encode_signed(uint8_t *p, int64_t i)
+{
+    return vli64_encode(p, (uint64_t)((i << 1) ^ (i >> 63)));
+}
+
+size_t vli64_decode_signed(uint8_t const *p, int64_t *i)
+{
+    size_t n     = vli64_decode(p, (uint64_t *)i);
+    uint64_t v   = (uint64_t)(*i);
+    *i           = (v >> 1) ^ -(v & 1);
+    return n;
+}
+
+size_t vli32_encode(uint8_t *p, uint32_t u)
+{
+    if ((u >> 7) == 0) {
+        p[0] = (uint8_t)(u << 1 | 0x1);
+        return 1;
+    }
+    uint32_t shift = u >> 7;
+    for (size_t bytes = 2; bytes < 5; ++bytes) {
+        if ((shift >>= 7) == 0) {
+            uint32_t encoded = (u << 1 | 0x1) << (bytes - 1);
+            memcpy(p, &encoded, bytes);
+            return bytes;
+        }
+    }
+    p[0] = 0;
+    memcpy(p + 1, &u, sizeof(u));
+    return 5;
+}
+
+size_t vli32_decode(uint8_t const *p, uint32_t *u)
+{
+    *u = p[0];
+    if (*u & 1) {
+        *u >>= 1;
+        return 1;
+    }
+    if ((*u & 0xf) == 0) {
+        memcpy(u, p + 1, sizeof(*u));
+        return 1 + sizeof(*u);
+    }
+    size_t bytes = count_trailing_zeros(*u);
+    memcpy((uint8_t *)u + 1, p + 1, bytes);
+    *u >>= (bytes + 1);
+    return 1 + bytes;
+}
+
+size_t vli32_encode_signed(uint8_t *p, int32_t i)
+{
+    return vli32_encode(p, (uint32_t)((i << 1) ^ (i >> 31)));
+}
+
+size_t vli32_decode_signed(uint8_t const *p, int32_t *i)
+{
+    size_t n     = vli32_decode(p, (uint32_t *)i);
+    uint32_t v   = (uint32_t)(*i);
+    *i           = (v >> 1) ^ -(v & 1);
+    return n;
+}