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.

6 files changed, 267 insertions, 0 deletions

diff --git a/src/aoapplication.h b/src/aoapplication.h
index 3773f16..6fc41d9 100644
--- a/src/aoapplication.h
+++ b/src/aoapplication.h
@@ -4,6 +4,7 @@
 #include "datatypes.h"
 #include "demoserver.h"
 #include "discord_rich_presence.h"
+#include "ext_packet.h"
 #include "serverdata.h"
 #include "widgets/aooptionsdialog.h"
 
diff --git a/src/ext_packet.cpp b/src/ext_packet.cpp
new file mode 100644
index 0000000..76ac492
--- /dev/null
+++ b/src/ext_packet.cpp
@@ -0,0 +1,53 @@
+#include "ext_packet.h"
+
+extern "C"
+{
+#include "vli.h"
+}
+
+QByteArray serializeIdent(const Ident &m)
+{
+  QByteArray msg;
+  msg.reserve(3);
+  msg.append((char)ExMsgType::ident);
+  msg.append('\0');
+  msg.append(m.version);
+  return msg;
+}
+
+QByteArray serializeAuthRequest(const AuthRequest &m)
+{
+  QByteArray msg;
+  const QByteArray username = m.username.toUtf8();
+  uint8_t method[sizeof(quint32) + 1];
+  uint8_t ulen[sizeof(quint32) + 1];
+  size_t method_n = vli32_encode(method, (quint32)m.method);
+  size_t ulen_n = vli32_encode(ulen, username.size());
+  msg.reserve(2 + ulen_n + username.size() + method_n);
+  msg.append((char)ExMsgType::auth_request);
+  msg.append('\0');
+  msg.append((const char *)ulen, ulen_n);
+  msg.append(username, username.size());
+  msg.append((const char *)method, method_n);
+  return msg;
+}
+
+QByteArray serializeAuthResponse(const AuthResponse &m)
+{
+  QByteArray msg;
+  msg.reserve(2 + m.response.size());
+  msg.append((char)ExMsgType::auth_response);
+  msg.append('\0');
+  msg.append(m.response);
+  return msg;
+}
+
+bool parseAuthChallenge(QByteArrayView in, AuthChallenge &out)
+{
+  if (in.size() < 1 + 32)
+  {
+    return false;
+  }
+  out.challenge = QByteArray(in.constData() + 1, 32);
+  return true;
+}
diff --git a/src/ext_packet.h b/src/ext_packet.h
new file mode 100644
index 0000000..c6c77c4
--- /dev/null
+++ b/src/ext_packet.h
@@ -0,0 +1,53 @@
+#pragma once
+
+#include <QByteArray>
+#include <QString>
+
+enum class ExMsgType : quint8
+{
+  ident = 1,
+  auth_request = 2,
+  auth_challenge = 3,
+  auth_response = 4
+};
+
+struct ExMessage
+{
+  ExMsgType type;
+  QByteArray body;
+};
+
+enum class AuthMethod
+{
+  certificate = 1,
+  password = 2,
+};
+
+struct Ident
+{
+  quint8 version;
+};
+
+struct AuthRequest
+{
+  QString username;
+  AuthMethod method;
+  // Will be replaced if passwords are implemented.
+  QByteArray credentials;
+};
+
+struct AuthChallenge
+{
+  QByteArray challenge;
+};
+
+struct AuthResponse
+{
+  QByteArray response;
+};
+
+QByteArray serializeIdent(const Ident &m);
+QByteArray serializeAuthRequest(const AuthRequest &m);
+QByteArray serializeAuthResponse(const AuthResponse &m);
+
+bool parseAuthChallenge(QByteArrayView in, AuthChallenge &out);
diff --git a/src/network/websocketconnection.h b/src/network/websocketconnection.h
index 9df9a49..9d9f7d0 100644
--- a/src/network/websocketconnection.h
+++ b/src/network/websocketconnection.h
@@ -1,6 +1,7 @@
 #pragma once
 
 #include "aopacket.h"
+#include "ext_packet.h"
 #include "serverinfo.h"
 
 #include <QObject>
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;
+}
diff --git a/src/vli.h b/src/vli.h
new file mode 100644
index 0000000..97e066a
--- /dev/null
+++ b/src/vli.h
@@ -0,0 +1,19 @@
+#ifndef EXT_VLI_H
+#define EXT_VLI_H
+
+#include <stdint.h>
+#include <string.h>
+
+size_t vli64_encode(uint8_t *p, uint64_t u);
+size_t vli64_decode(uint8_t const *p, uint64_t *u);
+
+size_t vli64_encode_signed(uint8_t *p, int64_t i);
+size_t vli64_decode_signed(uint8_t const *p, int64_t *i);
+
+size_t vli32_encode(uint8_t *p, uint32_t u);
+size_t vli32_decode(uint8_t const *p, uint32_t *u);
+
+size_t vli32_encode_signed(uint8_t *p, int32_t i);
+size_t vli32_decode_signed(uint8_t const *p, int32_t *i);
+
+#endif /* EXT_VLI_H */