Program Listing for File NetworkitBinaryGraph.hpp¶

/*
 * NetworkitBinaryGraph.hpp
 *
 *      Author: Charmaine Ndolo <charmaine.ndolo@hu-berlin.de>
 */

#ifndef NETWORKIT_IO_NETWORKIT_BINARY_GRAPH_HPP_
#define NETWORKIT_IO_NETWORKIT_BINARY_GRAPH_HPP_

#include <cstddef>
#include <cstdint>

#include <tlx/define/likely.hpp>
#include <tlx/math/clz.hpp>
#include <tlx/math/ffs.hpp>

namespace NetworKit {
namespace nkbg {

struct Header {
    char magic[8];
    uint64_t checksum;
    uint64_t features;
    uint64_t nodes;
    uint64_t chunks;
    uint64_t offsetBaseData;
    uint64_t offsetAdjLists;
    uint64_t offsetAdjTranspose;
    uint64_t offsetWeightLists;
    uint64_t offsetWeightTranspose;
    uint64_t offsetAdjIdLists;
    uint64_t offsetAdjIdTranspose;
};

enum class WeightFormat : int { NONE = 0, VARINT = 1, SIGNED_VARINT = 2, DOUBLE = 3, FLOAT = 4 };

using WEIGHT_FORMAT = WeightFormat; // enum alias for backwards compatibility

static constexpr uint8_t DELETED_BIT = 0x1; // bit 0
static constexpr uint64_t DIR_MASK = 0x1;   // bit 0
static constexpr uint64_t WGHT_MASK = 0xE;  // bit 1-3
static constexpr uint64_t WGHT_SHIFT = 0x1;
static constexpr uint64_t INDEX_MASK = 0x10; // bit 4
static constexpr uint64_t INDEX_SHIFT = 0x4;

inline size_t varIntEncode(uint64_t value, uint8_t *buffer) noexcept {
    if (!value) {
        buffer[0] = 1;
        return 1;
    }

    int dataBytes;

    if (TLX_UNLIKELY(value >= (1llu << 56))) {
        // We have more than 56 bits of data, i.e. we need 8 data bytes.
        buffer[0] = 0;
        dataBytes = 8;

    } else {
        const auto bits = 64 - tlx::clz(value);
        dataBytes = static_cast<int>((bits - 1) / 7);

        // number of bytes is encode by the number of trailing zeros
        buffer[0] = static_cast<uint8_t>(1 << dataBytes);

        // put the 8 - (dataBytes - 1) least significant bits into the remainder of the buffer byte
        buffer[0] |= static_cast<uint8_t>(value << (dataBytes + 1));
        value >>= 7 - dataBytes;
    }

    for (int i = 0; i < dataBytes; i++) {
        buffer[i + 1] = static_cast<uint8_t>(value & 0xFF);
        value >>= 8;
    }

    return dataBytes + 1;
}

inline size_t varIntDecode(const uint8_t *data, uint64_t &value) noexcept {
    int n = 8;
    int bitsRecovered = 0;
    uint64_t decoded = 0;

    if (data[0]) {
        n = static_cast<int>(tlx::ffs(data[0]) - 1);
        decoded = data[0] >> (n + 1);
        bitsRecovered = 7 - n;
    }

    for (int i = 0; i < n; i++) {
        decoded |= static_cast<uint64_t>(data[i + 1]) << bitsRecovered;
        bitsRecovered += 8;
    }

    value = decoded;
    return n + 1;
}

inline uint64_t zigzagEncode(int64_t value) noexcept {
    return (static_cast<uint64_t>(value) << 1) ^ (int64_t(-1) * (value < 0));
}

inline int64_t zigzagDecode(uint64_t value) noexcept {
    return (value >> 1) ^ (-(value & 1));
}

} // namespace nkbg
} // namespace NetworKit

#endif // NETWORKIT_IO_NETWORKIT_BINARY_GRAPH_HPP_