32f8609b89
It handles 0, and could generate better code for that. On Broadwell architecture, it translates to a single instruction (LZCNT). We're still on Westmere, so it translates to BSR with a conditional move. Also, drop unnecessary casts and bit arithmetic, which saves a few instructions. Move to header so that it's inlined in parsers.
71 lines
2.8 KiB
C++
71 lines
2.8 KiB
C++
/*
|
|
* Copyright 2017-present ScyllaDB
|
|
*/
|
|
|
|
/*
|
|
* SPDX-License-Identifier: LicenseRef-ScyllaDB-Source-Available-1.0
|
|
*/
|
|
|
|
//
|
|
// For reference, see https://github.com/apache/cassandra/blob/trunk/doc/native_protocol_v5.spec.
|
|
//
|
|
// Relevant excerpt:
|
|
//
|
|
// [unsigned vint] An unsigned variable length integer. A vint is encoded with the most significant byte (MSB) first.
|
|
// The most significant byte will contains the information about how many extra bytes need to be read
|
|
// as well as the most significant bits of the integer.
|
|
// The number of extra bytes to read is encoded as 1 bits on the left side.
|
|
// For example, if we need to read 2 more bytes the first byte will start with 110
|
|
// (e.g. 256 000 will be encoded on 3 bytes as [110]00011 11101000 00000000)
|
|
// If the encoded integer is 8 bytes long the vint will be encoded on 9 bytes and the first
|
|
// byte will be: 11111111
|
|
//
|
|
// [vint] A signed variable length integer. This is encoded using zig-zag encoding and then sent
|
|
// like an [unsigned vint]. Zig-zag encoding converts numbers as follows:
|
|
// 0 = 0, -1 = 1, 1 = 2, -2 = 3, 2 = 4, -3 = 5, 3 = 6 and so forth.
|
|
// The purpose is to send small negative values as small unsigned values, so that we save bytes on the wire.
|
|
// To encode a value n use "(n >> 31) ^ (n << 1)" for 32 bit values, and "(n >> 63) ^ (n << 1)"
|
|
// for 64 bit values where "^" is the xor operation, "<<" is the left shift operation and ">>" is
|
|
// the arithmetic right shift operation (highest-order bit is replicated).
|
|
// Decode with "(n >> 1) ^ -(n & 1)".
|
|
//
|
|
|
|
#pragma once
|
|
|
|
#include "bytes.hh"
|
|
|
|
#include <cstdint>
|
|
#include <bit>
|
|
|
|
using vint_size_type = bytes::size_type;
|
|
|
|
static constexpr size_t max_vint_length = 9;
|
|
|
|
struct unsigned_vint final {
|
|
using value_type = uint64_t;
|
|
|
|
static vint_size_type serialized_size(value_type) noexcept;
|
|
|
|
static vint_size_type serialize(value_type, bytes::iterator out);
|
|
|
|
static value_type deserialize(bytes_view v);
|
|
|
|
static vint_size_type serialized_size_from_first_byte(bytes::value_type first_byte) {
|
|
return 1 + std::countl_zero(static_cast<uint8_t>(~first_byte));
|
|
}
|
|
};
|
|
|
|
struct signed_vint final {
|
|
using value_type = int64_t;
|
|
|
|
static vint_size_type serialized_size(value_type) noexcept;
|
|
|
|
static vint_size_type serialize(value_type, bytes::iterator out);
|
|
|
|
static value_type deserialize(bytes_view v);
|
|
|
|
static vint_size_type serialized_size_from_first_byte(bytes::value_type first_byte) {
|
|
return unsigned_vint::serialized_size_from_first_byte(first_byte);
|
|
}
|
|
};
|