kiwi.h

#ifndef KIWI_H
#define KIWI_H

#include <assert.h>
#include <initializer_list>
#include <memory.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>

namespace kiwi {
  class String;
  class MemoryPool;

  class ByteBuffer {
  public:
    ByteBuffer();
    ByteBuffer(uint8_t *data, size_t size);
    ByteBuffer(const uint8_t *data, size_t size);
    ~ByteBuffer();
    ByteBuffer(const ByteBuffer &) = delete;
    ByteBuffer &operator = (const ByteBuffer &) = delete;

    uint8_t *data() const { return _data; }
    size_t size() const { return _size; }
    size_t index() const { return _index; }

    bool readByte(bool &result);
    bool readByte(uint8_t &result);
    bool readVarFloat(float &result);
    bool readVarUint(uint32_t &result);
    bool readVarInt(int32_t &result);
    bool readString(const char *&result);
    bool readString(String &result, MemoryPool &pool);
    bool readVarUint64(uint64_t &result);
    bool readVarInt64(int64_t &result);

    void writeByte(uint8_t value);
    void writeVarFloat(float value);
    void writeVarUint(uint32_t value);
    void writeVarInt(int32_t value);
    void writeString(const char *value);
    void writeVarUint64(uint64_t value);
    void writeVarInt64(int64_t value);

  private:
    void _growBy(size_t amount);

    enum { INITIAL_CAPACITY = 256 };
    uint8_t *_data = nullptr;
    size_t _size = 0;
    size_t _capacity = 0;
    size_t _index = 0;
    bool _ownsData = false;
    bool _isConst = false;
  };

  ////////////////////////////////////////////////////////////////////////////////

  class String {
  public:
    String() {}
    explicit String(const char *c_str) : _c_str(c_str) {}

    const char *c_str() const { return _c_str; }

  private:
    const char *_c_str = nullptr;
  };

  inline bool operator == (const String &a, const String &b) { return !strcmp(a.c_str(), b.c_str()); }
  inline bool operator != (const String &a, const String &b) { return !(a == b); }

  ////////////////////////////////////////////////////////////////////////////////

  template <typename T>
  class Array {
  public:
    Array() {}
    Array(T *data, uint32_t size) : _data(data), _size(size) {}

    T *data() { return _data; }
    T *begin() { return _data; }
    T *end() { return _data + _size; }
    uint32_t size() const { return _size; }
    T &operator [] (uint32_t index) { assert(index < _size); return _data[index]; }
    void set(const T *data, size_t size) { assert(size == _size); memcpy(_data, data, (size < _size ? size : _size) * sizeof(T)); }
    void set(const std::initializer_list<T> &data) { set(data.begin(), data.size()); }

    const T *data() const { return _data; }
    const T *begin() const { return _data; }
    const T *end() const { return _data + _size; }
    const T &operator [] (uint32_t index) const { assert(index < _size); return _data[index]; }

  private:
    T *_data = nullptr;
    uint32_t _size = 0;
  };

  ////////////////////////////////////////////////////////////////////////////////

  class MemoryPool {
  public:
    MemoryPool() {}
    ~MemoryPool() { clear(); }
    MemoryPool(const MemoryPool &) = delete;
    MemoryPool &operator = (const MemoryPool &) = delete;

    void clear();

    template <typename T>
    T *allocate(uint32_t count = 1);

    template <typename T>
    Array<T> array(uint32_t size) { return Array<T>(allocate<T>(size), size); }

    String string(const char *data, uint32_t count);
    String string(const char *c_str) { return string(c_str, strlen(c_str)); }

  private:
    enum { INITIAL_CAPACITY = 1 << 12 };

    struct Chunk {
      uint8_t *data = nullptr;
      uint32_t capacity = 0;
      uint32_t used = 0;
      Chunk *next = nullptr;
    };

    Chunk *_first = nullptr;
    Chunk *_last = nullptr;
  };

  ////////////////////////////////////////////////////////////////////////////////

  class BinarySchema {
  public:
    bool parse(ByteBuffer &bb);
    bool findDefinition(const char *definition, uint32_t &index) const;
    bool skipField(ByteBuffer &bb, uint32_t definition, uint32_t field) const;

  private:
    enum {
      TYPE_BOOL = -1,
      TYPE_BYTE = -2,
      TYPE_INT = -3,
      TYPE_UINT = -4,
      TYPE_FLOAT = -5,
      TYPE_STRING = -6,
      TYPE_INT64 = -7,
      TYPE_UINT64 = -8,
    };

    struct Field {
      String name;
      int32_t type = 0;
      bool isArray = false;
      uint32_t value = 0;
    };

    enum {
      KIND_ENUM = 0,
      KIND_STRUCT = 1,
      KIND_MESSAGE = 2,
    };

    struct Definition {
      String name;
      uint8_t kind = 0;
      Array<Field> fields;
    };

    bool _skipField(ByteBuffer &bb, const Field &field) const;

    MemoryPool _pool;
    Array<Definition> _definitions;
  };
}

#endif
#ifdef IMPLEMENT_KIWI_H
#ifndef IMPLEMENT_KIWI_H_
#define IMPLEMENT_KIWI_H_

  kiwi::ByteBuffer::ByteBuffer() : _data(new uint8_t[INITIAL_CAPACITY]), _capacity(INITIAL_CAPACITY), _ownsData(true) {
  }

  kiwi::ByteBuffer::ByteBuffer(uint8_t *data, size_t size) : _data(data), _size(size), _capacity(size) {
  }

  kiwi::ByteBuffer::ByteBuffer(const uint8_t *data, size_t size) : _data(const_cast<uint8_t *>(data)), _size(size), _capacity(size), _isConst(true) {
    (void)_isConst;
  }

  kiwi::ByteBuffer::~ByteBuffer() {
    if (_ownsData) {
      delete [] _data;
    }
  }

  bool kiwi::ByteBuffer::readByte(bool &result) {
    uint8_t value;
    if (!readByte(value)) {
      result = false;
      return false;
    }

    result = value;
    return true;
  }

  bool kiwi::ByteBuffer::readByte(uint8_t &result) {
    if (_index >= _size) {
      result = 0;
      return false;
    }

    result = _data[_index];
    _index++;
    return true;
  }

  bool kiwi::ByteBuffer::readVarFloat(float &result) {
    uint8_t first;
    if (!readByte(first)) {
      return false;
    }

    // Optimization: use a single byte to store zero
    if (first == 0) {
      result = 0;
      return true;
    }

    // Endian-independent 32-bit read
    if (_index + 3 > _size) {
      result = 0;
      return false;
    }
    uint32_t bits = first | (_data[_index] << 8) | (_data[_index + 1] << 16) | (_data[_index + 2] << 24);
    _index += 3;

    // Move the exponent back into place
    bits = (bits << 23) | (bits >> 9);

    // Reinterpret as a floating-point number
    memcpy(&result, &bits, 4);
    return true;
  }

  bool kiwi::ByteBuffer::readVarUint(uint32_t &result) {
    uint8_t shift = 0;
    uint8_t byte;
    result = 0;

    do {
      if (!readByte(byte)) {
        return false;
      }

      result |= (byte & 127) << shift;
      shift += 7;
    } while (byte & 128 && shift < 35);

    return true;
  }

  bool kiwi::ByteBuffer::readVarInt(int32_t &result) {
    uint32_t value;
    if (!readVarUint(value)) {
      result = 0;
      return false;
    }

    result = value & 1 ? ~(value >> 1) : value >> 1;
    return true;
  }

  bool kiwi::ByteBuffer::readString(const char *&result) {
    result = reinterpret_cast<const char *>(_data) + _index;

    do {
      if (_index >= _size) return false;
    } while (_data[_index++] != '\0');

    return true;
  }

  bool kiwi::ByteBuffer::readString(String &result, MemoryPool &pool) {
    uint32_t size = 0;
    result = String();

    do {
      if (_index >= _size) return false;
    } while (_data[_index + size++] != '\0');

    result = pool.string(reinterpret_cast<char *>(_data + _index), size - 1);
    _index += size;
    return true;
  }

  bool kiwi::ByteBuffer::readVarUint64(uint64_t &result) {
    uint8_t shift = 0;
    uint8_t byte;
    result = 0;

    while (true) {
      if (!readByte(byte)) {
        return false;
      }
      if (!(byte & 128) || shift >= 56) {
        break;
      }
      result |= (uint64_t)(byte & 127) << shift;
      shift += 7;
    }

    result |= (uint64_t)(byte) << shift;
    return true;
  }

  bool kiwi::ByteBuffer::readVarInt64(int64_t &result) {
    uint64_t value;
    if (!readVarUint64(value)) {
      result = 0;
      return false;
    }

    result = value & 1 ? ~(value >> 1) : value >> 1;
    return true;
  }

  void kiwi::ByteBuffer::writeByte(uint8_t value) {
    assert(!_isConst);
    size_t index = _size;
    _growBy(1);
    _data[index] = value;
  }

  void kiwi::ByteBuffer::writeVarFloat(float value) {
    assert(!_isConst);

    // Reinterpret as an integer
    uint32_t bits;
    memcpy(&bits, &value, 4);

    // Move the exponent to the first 8 bits
    bits = (bits >> 23) | (bits << 9);

    // Optimization: use a single byte to store zero and denormals (check for an exponent of 0)
    if ((bits & 255) == 0) {
      writeByte(0);
      return;
    }

    // Endian-independent 32-bit write
    size_t index = _size;
    _growBy(4);
    _data[index] = bits;
    _data[index + 1] = bits >> 8;
    _data[index + 2] = bits >> 16;
    _data[index + 3] = bits >> 24;
  }

  void kiwi::ByteBuffer::writeVarUint(uint32_t value) {
    assert(!_isConst);
    do {
      uint8_t byte = value & 127;
      value >>= 7;
      writeByte(value ? byte | 128 : byte);
    } while (value);
  }

  void kiwi::ByteBuffer::writeVarInt(int32_t value) {
    assert(!_isConst);
    writeVarUint((value << 1) ^ (value >> 31));
  }

  void kiwi::ByteBuffer::writeVarUint64(uint64_t value) {
    assert(!_isConst);
    for (int i = 0; value > 127 && i < 8; i++) {
      writeByte((value & 127) | 128);
      value >>= 7;
    }
    writeByte(value);
  }

  void kiwi::ByteBuffer::writeVarInt64(int64_t value) {
    assert(!_isConst);
    writeVarUint64((value << 1) ^ (value >> 63));
  }

  void kiwi::ByteBuffer::writeString(const char *value) {
    assert(!_isConst);
    uint32_t count = strlen(value) + 1;
    size_t index = _size;
    _growBy(count);
    memcpy(_data + index, value, count);
  }

  void kiwi::ByteBuffer::_growBy(size_t amount) {
    assert(!_isConst);

    if (_size + amount > _capacity) {
      size_t capacity = (_size + amount) * 2;
      uint8_t *data = new uint8_t[capacity];
      memcpy(data, _data, _size);

      if (_ownsData) {
        delete [] _data;
      }

      _data = data;
      _capacity = capacity;
      _ownsData = true;
    }

    _size += amount;
  }

  ////////////////////////////////////////////////////////////////////////////////

  void kiwi::MemoryPool::clear() {
    for (Chunk *chunk = _first, *next; chunk; chunk = next) {
      next = chunk->next;
      delete [] chunk->data;
      delete chunk;
    }

    _first = _last = nullptr;
  }

  template <typename T>
  T *kiwi::MemoryPool::allocate(uint32_t count) {
    Chunk *chunk = _last;
    uint32_t size = count * sizeof(T);
    uint32_t index = (chunk ? chunk->used : 0) + alignof(T) - 1;
    index -= index % alignof(T);

    if (chunk && index + size >= index && index + size <= chunk->capacity) {
      chunk->used = index + size;
      return reinterpret_cast<T *>(chunk->data + index);
    }

    chunk = new Chunk;
    chunk->capacity = size > INITIAL_CAPACITY ? size : INITIAL_CAPACITY;
    chunk->data = new uint8_t[chunk->capacity](); // "()" means zero-initialized
    chunk->used = size;

    if (_last) _last->next = chunk;
    else _first = chunk;
    _last = chunk;

    return reinterpret_cast<T *>(chunk->data);
  }

  kiwi::String kiwi::MemoryPool::string(const char *text, uint32_t count) {
    char *c_str = allocate<char>(count + 1);
    memcpy(c_str, text, count);
    return String(c_str);
  }

  ////////////////////////////////////////////////////////////////////////////////

  bool kiwi::BinarySchema::parse(ByteBuffer &bb) {
    uint32_t definitionCount = 0;

    _definitions = {};
    _pool.clear();

    if (!bb.readVarUint(definitionCount)) {
      return false;
    }

    _definitions = _pool.array<Definition>(definitionCount);

    for (auto &definition : _definitions) {
      uint32_t fieldCount = 0;

      if (!bb.readString(definition.name, _pool) ||
          !bb.readByte(definition.kind) ||
          !bb.readVarUint(fieldCount) ||
          (definition.kind != KIND_ENUM && definition.kind != KIND_STRUCT && definition.kind != KIND_MESSAGE)) {
        return false;
      }

      definition.fields = _pool.array<Field>(fieldCount);

      for (auto &field : definition.fields) {
        if (!bb.readString(field.name, _pool) ||
            !bb.readVarInt(field.type) ||
            !bb.readByte(field.isArray) ||
            !bb.readVarUint(field.value) ||
            field.type < TYPE_UINT64 ||
            field.type >= (int32_t)definitionCount) {
          return false;
        }
      }
    }

    return true;
  }

  bool kiwi::BinarySchema::findDefinition(const char *definition, uint32_t &index) const {
    for (uint32_t i = 0; i < _definitions.size(); i++) {
      auto &item = _definitions[i];
      if (item.name == String(definition)) {
        index = i;
        return true;
      }
    }

    // Ignore fields we're looking for in an old schema
    index = -1;
    return false;
  }

  bool kiwi::BinarySchema::skipField(ByteBuffer &bb, uint32_t definition, uint32_t field) const {
    if (definition < _definitions.size()) {
      for (auto &item : _definitions[definition].fields) {
        if (item.value == field) {
          return _skipField(bb, item);
        }
      }
    }

    return false;
  }

  bool kiwi::BinarySchema::_skipField(ByteBuffer &bb, const Field &field) const {
    uint32_t count = 1;

    if (field.isArray && !bb.readVarUint(count)) {
      return false;
    }

    while (count-- > 0) {
      switch (field.type) {
        case TYPE_BOOL:
        case TYPE_BYTE: {
          uint8_t dummy = 0;
          if (!bb.readByte(dummy)) return false;
          break;
        }

        case TYPE_INT:
        case TYPE_UINT: {
          uint32_t dummy = 0;
          if (!bb.readVarUint(dummy)) return false;
          break;
        }

        case TYPE_FLOAT: {
          float dummy = 0;
          if (!bb.readVarFloat(dummy)) return false;
          break;
        }

        case TYPE_STRING: {
          uint8_t value = 0;
          do {
            if (!bb.readByte(value)) return false;
          } while (value);
          break;
        }

        case TYPE_INT64:
        case TYPE_UINT64: {
          uint64_t dummy = 0;
          if (!bb.readVarUint64(dummy)) return false;
          break;
        }

        default: {
          assert(field.type >= 0 && (uint32_t)field.type < _definitions.size());
          auto &definition = _definitions[field.type];

          switch (definition.kind) {
            case KIND_ENUM: {
              uint32_t dummy;
              if (!bb.readVarUint(dummy)) return false;
              break;
            }

            case KIND_STRUCT: {
              for (auto &item : definition.fields) {
                if (!_skipField(bb, item)) return false;
              }
              break;
            }

            case KIND_MESSAGE: {
              uint32_t id = 0;
              while (true) {
                if (!bb.readVarUint(id)) return false;
                if (!id) break;
                if (!skipField(bb, field.type, id)) return false;
              }
              break;
            }

            default: {
              assert(false);
              break;
            }
          }
        }
      }
    }

    return true;
  }

#endif
#endif