blob: a57f15d7b37009951e1a7d380b11048128181225 (
plain) (
blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
|
#pragma once
#include <util/generic/bitops.h>
#include <util/generic/typetraits.h>
#include <util/system/yassert.h>
template <typename TWord>
struct TBitSeqTraits {
static constexpr ui8 NumBits = CHAR_BIT * sizeof(TWord);
static constexpr TWord ModMask = static_cast<TWord>(NumBits - 1);
static constexpr TWord DivShift = MostSignificantBitCT(NumBits);
static inline TWord ElemMask(ui8 count) {
// NOTE: Shifting by the type's length is UB, so we need this workaround.
if (Y_LIKELY(count))
return TWord(-1) >> (NumBits - count);
return 0;
}
static inline TWord BitMask(ui8 pos) {
return TWord(1) << pos;
}
static size_t NumOfWords(size_t bits) {
return (bits + NumBits - 1) >> DivShift;
}
static bool Test(const TWord* data, ui64 pos, ui64 size) {
Y_ASSERT(pos < size);
return data[pos >> DivShift] & BitMask(pos & ModMask);
}
static TWord Get(const TWord* data, ui64 pos, ui8 width, TWord mask, ui64 size) {
if (!width)
return 0;
Y_ASSERT((pos + width) <= size);
size_t word = pos >> DivShift;
TWord shift1 = pos & ModMask;
TWord shift2 = NumBits - shift1;
TWord res = data[word] >> shift1 & mask;
if (shift2 < width) {
res |= data[word + 1] << shift2 & mask;
}
return res;
}
static_assert(std::is_unsigned<TWord>::value, "Expected std::is_unsigned<T>::value.");
static_assert((NumBits & (NumBits - 1)) == 0, "NumBits should be a power of 2.");
};
|
