// Copyright 2019 The Fuchsia Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#ifndef LIB_INSPECT_VMO_BLOCK_H_
#define LIB_INSPECT_VMO_BLOCK_H_

#include "limits.h"

#include <fbl/function.h>
#include <fbl/string.h>
#include <fbl/string_piece.h>

#include <type_traits>
#include <zircon/types.h>

namespace inspect {
namespace vmo {

enum class BlockType {
    kFree = 0,
    kReserved = 1,
    kHeader = 2,
    kObjectValue = 3,
    kIntValue = 4,
    kUintValue = 5,
    kDoubleValue = 6,
    kPropertyValue = 7,
    kExtent = 8,
    kName = 9,
    kTombstone = 10,
    kArrayValue = 11
};

enum class PropertyFormat {
    // The property is a UTF-8 string.
    kUtf8 = 0,

    // The property is a binary string of uint8_t.
    kBinary = 1
};

enum class ArrayFormat {
    // The array stores N raw values in N slots.
    kDefault = 0,

    // The array is a linear histogram with N buckets and N+4 slots, which are:
    // - param_floor_value
    // - param_step_size
    // - underflow_bucket
    // - ...N buckets...
    // - overflow_bucket
    kLinearHistogram = 1,

    // The array is an exponential histogram with N buckets and N+5 slots, which are:
    // - param_floor_value
    // - param_initial_step
    // - param_step_multiplier
    // - underflow_bucket
    // - ...N buckets...
    // - overflow_bucket
    kExponentialHistogram = 2
};

namespace internal {

using BlockOrder = uint32_t;
using BlockIndex = uint64_t;

// Returns the smallest order such that (kMinOrderSize << order) >= size.
// Size must be non-zero.
constexpr BlockOrder FitOrder(size_t size) {
    auto ret = 64 - __builtin_clzl(size - 1) - kMinOrderShift;
    return static_cast<BlockOrder>(ret);
}

// Structure of the block header and payload.
struct Block {
    union {
        uint64_t header;
        char header_data[8];
    };
    union {
        int64_t i64;
        uint64_t u64;
        double f64;
        char data[8];
    } payload;
};

static_assert(sizeof(Block) == 16, "Block header must be 16 bytes");
static_assert(sizeof(Block) == kMinOrderSize,
              "Minimum allocation size must exactly hold a block header");

// Describes the layout of a bit-field packed into a 64-bit word.
template <size_t begin, size_t end>
struct Field {
    static_assert(begin < sizeof(uint64_t) * 8, "begin is out of bounds");
    static_assert(end < sizeof(uint64_t) * 8, "end is out of bounds");
    static_assert(begin <= end, "begin must not be larger than end");
    static_assert(end - begin + 1 < 64, "must be a part of a word, not a whole word");

    static constexpr uint64_t kMask = (uint64_t(1) << (end - begin + 1)) - 1;

    template <typename T>
    static constexpr uint64_t Make(T value) {
        return static_cast<uint64_t>(value) << begin;
    }

    template <typename U>
    static constexpr U Get(uint64_t word) {
        return static_cast<U>((word >> (begin % 64)) & kMask);
    }

    static constexpr void Set(uint64_t* word, uint64_t value) {
        *word = (*word & ~(kMask << begin)) | (value << begin);
    }
};

// Describes the base fields present for all blocks.
struct BlockFields {
    using Order = Field<0, 3>;
    using Type = Field<4, 7>;
};

struct HeaderBlockFields : public BlockFields {
    using Version = Field<8, 31>;
    using MagicNumber = Field<32, 63>;
};

struct FreeBlockFields : public BlockFields {
    using NextFreeBlock = Field<8, 35>;
};

// Describes the fields common to all value blocks.
struct ValueBlockFields : public BlockFields {
    using ParentIndex = Field<8, 35>;
    using NameIndex = Field<36, 63>;
};

struct PropertyBlockPayload {
    using TotalLength = Field<0, 31>;
    using ExtentIndex = Field<32, 59>;
    using Flags = Field<60, 63>;
};

// Describes the fields for ARRAY_VALUE payloads.
struct ArrayBlockPayload {
    using EntryType = Field<0, 3>;
    using Flags = Field<4, 7>;
    using Count = Field<8, 15>;
};

struct ExtentBlockFields : public BlockFields {
    using NextExtentIndex = Field<8, 35>;
};

struct NameBlockFields : public BlockFields {
    using Length = Field<8, 19>;
};

constexpr BlockOrder GetOrder(const Block* block) {
    return BlockFields::Order::Get<BlockOrder>(block->header);
}

constexpr BlockType GetType(const Block* block) {
    return BlockFields::Type::Get<BlockType>(block->header);
}

constexpr size_t PayloadCapacity(BlockOrder order) {
    return OrderToSize(order) - sizeof(Block::header);
}

constexpr size_t ArrayCapacity(BlockOrder order) {
    return (OrderToSize(order) - sizeof(Block::header) - sizeof(Block::payload)) / sizeof(uint64_t);
}

constexpr size_t BlockSizeForPayload(size_t payload_size) {
    return fbl::max(payload_size + sizeof(Block::header), kMinOrderSize);
}

// For array types, get a pointer to a specific slot in the array.
// If the index is out of bounds, return nullptr.
template <typename T, typename BlockType>
constexpr T* GetArraySlot(BlockType* block, size_t index) {
    if (index > ArrayCapacity(GetOrder(block))) {
        return nullptr;
    }

    T* arr = reinterpret_cast<T*>(&block->payload);
    return arr + index + 1 /* skip inline payload */;
}

constexpr size_t kMaxPayloadSize = kMaxOrderSize - sizeof(Block::header);

} // namespace internal
} // namespace vmo
} // namespace inspect

#endif // LIB_INSPECT_VMO_BLOCK_H_