src/util/varint.cpp - master - smychkov/SStorage

src/util/varint.cpp
74 строки3 KB
Андрей Смычков
feat: util varint, crc32c, murmur3, compression (snappy)
25 апр 2026, 09:00
25 апр 2026, 09:00a7cf584
#include "varint.hpp"

namespace sstorage {
namespace util {

//============================================================================
// Кодирование varint
//============================================================================
// Алгоритм: пока в числе остаются биты выше 7, пишем (младшие 7 бит | 0x80),
// сдвигаем на 7 вправо. Последний байт пишем без старшего бита.
void encodeVarint(uint64_t value, std::string& out) {
    while (value >= 0x80) {
        out.push_back(static_cast<char>((value & 0x7F) | 0x80));
        value >>= 7;
    }
    out.push_back(static_cast<char>(value & 0x7F));
}

//============================================================================
// Декодирование varint
//============================================================================
// Читаем байты пока встречается continuation bit (0x80).
// Собираем 7-битные группы в результирующее число.
// Защита от переполнения: максимум 10 байт (70 бит).
bool decodeVarint(const char* data, size_t len, uint64_t& value, size_t& consumed) {
    value = 0;
    consumed = 0;
    uint32_t shift = 0;
    for (size_t i = 0; i < len && i < kMaxVarintBytes; ++i) {
        uint8_t b = static_cast<uint8_t>(data[i]);
        // 10-й байт может использовать только 1 младший бит (итого 64 бита)
        if (i == kMaxVarintBytes - 1 && (b & 0xFE) != 0) {
            return false; // overflow
        }
        value |= static_cast<uint64_t>(b & 0x7F) << shift;
        if ((b & 0x80) == 0) {
            consumed = i + 1;
            return true;
        }
        shift += 7;
    }
    return false; // обрыв или слишком длинный varint
}

//============================================================================
// ZigZag + varint для signed
//============================================================================
void encodeVarintSigned(int64_t value, std::string& out) {
    encodeVarint(zigzagEncode(value), out);
}

bool decodeVarintSigned(const char* data, size_t len, int64_t& value, size_t& consumed) {
    uint64_t u;
    if (!decodeVarint(data, len, u, consumed)) {
        return false;
    }
    value = zigzagDecode(u);
    return true;
}

//============================================================================
// Длина кодирования
//============================================================================
size_t varintLength(uint64_t value) {
    size_t len = 1;
    while (value >= 0x80) {
        value >>= 7;
        ++len;
    }
    return len;
}

}
}