Revision b5c43319c7bf98bf39593fde909d1379d12cbe21 authored by Alexander Nadel on 26 April 2022, 10:39:57 UTC, committed by Alexander Nadel on 26 April 2022, 10:39:57 UTC
1 parent 4006699
TableBitInfo.hpp
// Copyright(C) 2021 Intel Corporation
// SPDX - License - Identifier: MIT
#pragma once
#include <cstdint>
#include <array>
#include <bit>
using namespace std;
struct TBitInfo
{
uint64_t w0ReadMask;
uint64_t w1ReadMask;
uint8_t w0ReadShr;
constexpr uint64_t W0WriteMask() const
{
return ~w1ReadMask;
}
constexpr uint8_t W0WriteShl() const
{
return w0ReadShr;
}
constexpr uint64_t W1WriteMask() const
{
return w1ReadMask;
}
};
static constexpr uint64_t LsbMask(uint8_t b)
{
return b == 64 ? (uint64_t)-1 : ((uint64_t)1 << (uint64_t)b) - (uint64_t)1;
};
static_assert(LsbMask(1) == 1);
static_assert(LsbMask(2) == 3);
static_assert(LsbMask(3) == 7);
static_assert(LsbMask(10) == 1023);
static_assert(LsbMask(64) == (uint64_t)-1);
constexpr uint8_t MAX_BITS_NUM = 64;
// The goal of the compile-time-created array tableByBit is to enable writing and reading any number b of bits
// (b<=64 bits; it can be easily extended to 128 bits, if a uint128_t type is available),
// *without branching*, starting from any bit-number in a uint64_t* buffer
// An entry i-1 in tableByBit (whose simple syntax works only starting from C++17) corresponds to i bits
// The idea is to decompose the b-bit number into MSB part, which goes into 64-word-0, and the LSB part (if any), which goes into 64-word-1
// Information per b bits:
// For every initial bit number (from 1 to b):
// (a) A mask to extract the MSB's from word-0 (w0ReadMask)
// (b) Right-shift value to adjust the MSB's from word-0 (w0ReadShr)
// (c) A mask to extract the LSB's from word-1
// For an example, consider i+1=26
// tableByBit[25][52].w1ReadMask = (1 << (52+26-64))-1 = (1 << 14)-1
// tableByBit[25][52].w0ReadMask = ~((1 << 52) - 1)
// tableByBit[25][52].w0ReadShr = 52-(52+26-64=14)=38;
// See also the static_assert's after the table for more examples
constexpr array<array<TBitInfo, 64>, MAX_BITS_NUM> tableByBit = []
{
array<array<TBitInfo, 64>, MAX_BITS_NUM> byBitInfo = {};
for (uint8_t bitsInLit = 1; bitsInLit <= MAX_BITS_NUM; bitsInLit++)
{
for (uint8_t currBit = 0; currBit < MAX_BITS_NUM; ++currBit)
{
if (currBit + bitsInLit > 64)
{
const uint8_t lsbBits = currBit + bitsInLit - 64;
byBitInfo[bitsInLit - 1][currBit].w0ReadMask = ~LsbMask(currBit);
byBitInfo[bitsInLit - 1][currBit].w0ReadShr = currBit - lsbBits;
byBitInfo[bitsInLit - 1][currBit].w1ReadMask = LsbMask(lsbBits);
}
else
{
byBitInfo[bitsInLit - 1][currBit].w0ReadMask = LsbMask(bitsInLit) << currBit;
byBitInfo[bitsInLit - 1][currBit].w0ReadShr = currBit;
byBitInfo[bitsInLit - 1][currBit].w1ReadMask = 0;
}
}
}
return byBitInfo;
}();
// Some static asserts to assert correctness
// 1 bit
static_assert(tableByBit[1 - 1][0].w0ReadMask == 1);
static_assert(tableByBit[1 - 1][0].w0ReadShr == 0);
static_assert(tableByBit[1 - 1][0].w1ReadMask == 0);
static_assert(tableByBit[1 - 1][1].w0ReadMask == 2);
static_assert(tableByBit[1 - 1][1].w0ReadShr == 1);
static_assert(tableByBit[1 - 1][1].w1ReadMask == 0);
static_assert(tableByBit[1 - 1][2].w0ReadMask == 4);
static_assert(tableByBit[1 - 1][2].w0ReadShr == 2);
static_assert(tableByBit[1 - 1][2].w1ReadMask == 0);
static_assert(tableByBit[1 - 1][9].w0ReadMask == (uint64_t)1 << 9);
static_assert(tableByBit[1 - 1][9].w0ReadShr == 9);
static_assert(tableByBit[1 - 1][9].w1ReadMask == 0);
static_assert(tableByBit[1 - 1][63].w0ReadMask == (uint64_t)1 << 63);
static_assert(tableByBit[1 - 1][63].w0ReadShr == 63);
static_assert(tableByBit[1 - 1][63].w1ReadMask == 0);
// 2 bits
static_assert(tableByBit[2 - 1][0].w0ReadMask == 3);
static_assert(tableByBit[2 - 1][0].w0ReadShr == 0);
static_assert(tableByBit[2 - 1][0].w1ReadMask == 0);
static_assert(tableByBit[2 - 1][1].w0ReadMask == 3 << 1);
static_assert(tableByBit[2 - 1][1].w0ReadShr == 1);
static_assert(tableByBit[2 - 1][1].w1ReadMask == 0);
static_assert(tableByBit[2 - 1][2].w0ReadMask == 3 << 2);
static_assert(tableByBit[2 - 1][2].w0ReadShr == 2);
static_assert(tableByBit[2 - 1][2].w1ReadMask == 0);
static_assert(tableByBit[2 - 1][62].w0ReadMask == (uint64_t)3 << 62);
static_assert(tableByBit[2 - 1][62].w0ReadShr == 62);
static_assert(tableByBit[2 - 1][62].w1ReadMask == 0);
static_assert(tableByBit[2 - 1][63].w0ReadMask == (uint64_t)1 << 63);
static_assert(tableByBit[2 - 1][63].w0ReadShr == 62);
static_assert(tableByBit[2 - 1][63].w1ReadMask == 1);
// 26 bits
static_assert(tableByBit[26 - 1][52].w0ReadMask == ~(((uint64_t)1 << 52) - 1));
static_assert(tableByBit[26 - 1][52].w0ReadShr == 52 - (52 + 26 - 64));
static_assert(tableByBit[26 - 1][52].w1ReadMask == ((uint64_t)1 << (52 + 26 - 64)) - 1);
// 64 bits
static_assert(tableByBit[64 - 1][0].w0ReadMask == (uint64_t)-1);
static_assert(tableByBit[64 - 1][0].w0ReadShr == 0);
static_assert(tableByBit[64 - 1][0].w1ReadMask == 0);
static_assert(tableByBit[64 - 1][1].w0ReadMask == (uint64_t)-1 - 1);
static_assert(tableByBit[64 - 1][1].w0ReadShr == 0);
static_assert(tableByBit[64 - 1][1].w1ReadMask == 1);
static_assert(tableByBit[64 - 1][2].w0ReadMask == (uint64_t)-1 - 3);
static_assert(tableByBit[64 - 1][2].w0ReadShr == 0);
static_assert(tableByBit[64 - 1][2].w1ReadMask == 3);
static_assert(tableByBit[64 - 1][3].w0ReadMask == (uint64_t)-1 - 7);
static_assert(tableByBit[64 - 1][3].w0ReadShr == 0);
static_assert(tableByBit[64 - 1][3].w1ReadMask == 7);
static_assert(tableByBit[64 - 1][63].w0ReadMask == (uint64_t)1 << 63);
static_assert(tableByBit[64 - 1][63].w0ReadShr == 0);
static_assert(tableByBit[64 - 1][63].w1ReadMask == (uint64_t)-1 - ((uint64_t)1 << 63));
// The goal of the compile-time-created array tableByEntry is to enable writing and reading *elements* of b of bits
// (b<=64 bits; it can be trivially extended to 128 bits, if a uint128_t type is available),
// *without branching*, starting from any element in a uint64_t* buffer, representing a b-bit array
// The difference between tableByEntry and tableByBit is that the latter enables indexing by bit, while the former enables indexing by element number
// Hence, tableByEntry enables implementing b-bit arrays, while tableByBit enables working with a bit-indexed buffer, knowing the starting bit number and the bit width
// An entry i-1 in tableByEntry (whose simple syntax works only starting from C++17) corresponds to i bits
// The idea is similar to tableByBit: we decompose the b-bit number into MSB part, which goes into 64-word-0, and the LSB part (if any), which goes into 64-word-1
// Information per b bits:
// (1) Given an entry number in an b-bit array, it holds a mask M to get the starting bit-number in its entry in the uint64_t* buffer
// In an b-bit array, this information saves a costly multiplication operation (entry*b) to get the first bit number
// (2) For every initial bit number from 1 to b, the following information:
// (a) A mask to extract the MSB's from word-0 (w0ReadMask)
// (b) Right-shift value to adjust the MSB's from word-0 (w0ReadShr)
// (c) A mask to extract the LSB's from word-1
// For an example, consider i+1=26
// We have the following cycle of 32 possible entries, starting from 0:
// 0, 26, 52, 14, 40, 2, 28, 54, 16, 42, 4, 30, 56, 18, 44, 6, 32, 58, 20, 46, 8, 34, 60, 22, 48, 10, 36, 62, 24, 50, 12, 38
// Hence, we have tableByEntry[25].first = 31, while:
// tableByEntry[25].second[0] = tableByBit[25][0]
// tableByEntry[25].second[1] = tableByBit[25][26]
// tableByEntry[25].second[2] = tableByBit[25][52]
// tableByEntry[25].second[3] = tableByBit[25][14]
// ...............................................
// tableByEntry[25].second[31] = tableByBit[25][38]
constexpr array<pair<uint8_t, array<TBitInfo, 64>>, MAX_BITS_NUM> tableByEntry = []
{
array<pair<uint8_t, array<TBitInfo, 64>>, MAX_BITS_NUM> byEntryInfo = {};
for (uint8_t bitsInLit = 1; bitsInLit <= MAX_BITS_NUM; bitsInLit++)
{
// 0-initialization is the default
array<bool, MAX_BITS_NUM> isVisited({});
uint8_t currRem = 0;
for (uint8_t currBit = 0; !isVisited[currBit]; currBit = (currBit + bitsInLit) % 64, ++currRem)
{
isVisited[currBit] = true;
byEntryInfo[bitsInLit - 1].second[currRem].w0ReadMask = tableByBit[bitsInLit - 1][currBit].w0ReadMask;
byEntryInfo[bitsInLit - 1].second[currRem].w0ReadShr = tableByBit[bitsInLit - 1][currBit].w0ReadShr;
byEntryInfo[bitsInLit - 1].second[currRem].w1ReadMask = tableByBit[bitsInLit - 1][currBit].w1ReadMask;
}
// currRem must always be a power of 2 for our table to work
// This is what indeed happens: we static_assert it below for all possible values, but a mathematician should be able to prove it
byEntryInfo[bitsInLit - 1].first = currRem - 1;
}
return byEntryInfo;
}();
// Some static asserts to assert correctness
// In order for tableByEntry to work, all the cycles must be power of 2
static_assert(has_single_bit<uint8_t>(tableByEntry[0].first + 1));
static_assert(has_single_bit<uint8_t>(tableByEntry[1].first + 1));
static_assert(has_single_bit<uint8_t>(tableByEntry[2].first + 1));
static_assert(has_single_bit<uint8_t>(tableByEntry[3].first + 1));
static_assert(has_single_bit<uint8_t>(tableByEntry[4].first + 1));
static_assert(has_single_bit<uint8_t>(tableByEntry[5].first + 1));
static_assert(has_single_bit<uint8_t>(tableByEntry[6].first + 1));
static_assert(has_single_bit<uint8_t>(tableByEntry[7].first + 1));
static_assert(has_single_bit<uint8_t>(tableByEntry[8].first + 1));
static_assert(has_single_bit<uint8_t>(tableByEntry[9].first + 1));
static_assert(has_single_bit<uint8_t>(tableByEntry[10].first + 1));
static_assert(has_single_bit<uint8_t>(tableByEntry[11].first + 1));
static_assert(has_single_bit<uint8_t>(tableByEntry[12].first + 1));
static_assert(has_single_bit<uint8_t>(tableByEntry[13].first + 1));
static_assert(has_single_bit<uint8_t>(tableByEntry[14].first + 1));
static_assert(has_single_bit<uint8_t>(tableByEntry[15].first + 1));
static_assert(has_single_bit<uint8_t>(tableByEntry[16].first + 1));
static_assert(has_single_bit<uint8_t>(tableByEntry[17].first + 1));
static_assert(has_single_bit<uint8_t>(tableByEntry[18].first + 1));
static_assert(has_single_bit<uint8_t>(tableByEntry[19].first + 1));
static_assert(has_single_bit<uint8_t>(tableByEntry[20].first + 1));
static_assert(has_single_bit<uint8_t>(tableByEntry[21].first + 1));
static_assert(has_single_bit<uint8_t>(tableByEntry[22].first + 1));
static_assert(has_single_bit<uint8_t>(tableByEntry[23].first + 1));
static_assert(has_single_bit<uint8_t>(tableByEntry[24].first + 1));
static_assert(has_single_bit<uint8_t>(tableByEntry[25].first + 1));
static_assert(has_single_bit<uint8_t>(tableByEntry[26].first + 1));
static_assert(has_single_bit<uint8_t>(tableByEntry[27].first + 1));
static_assert(has_single_bit<uint8_t>(tableByEntry[28].first + 1));
static_assert(has_single_bit<uint8_t>(tableByEntry[29].first + 1));
static_assert(has_single_bit<uint8_t>(tableByEntry[30].first + 1));
static_assert(has_single_bit<uint8_t>(tableByEntry[31].first + 1));
static_assert(has_single_bit<uint8_t>(tableByEntry[32].first + 1));
static_assert(has_single_bit<uint8_t>(tableByEntry[33].first + 1));
static_assert(has_single_bit<uint8_t>(tableByEntry[34].first + 1));
static_assert(has_single_bit<uint8_t>(tableByEntry[35].first + 1));
static_assert(has_single_bit<uint8_t>(tableByEntry[36].first + 1));
static_assert(has_single_bit<uint8_t>(tableByEntry[37].first + 1));
static_assert(has_single_bit<uint8_t>(tableByEntry[38].first + 1));
static_assert(has_single_bit<uint8_t>(tableByEntry[39].first + 1));
static_assert(has_single_bit<uint8_t>(tableByEntry[40].first + 1));
static_assert(has_single_bit<uint8_t>(tableByEntry[41].first + 1));
static_assert(has_single_bit<uint8_t>(tableByEntry[42].first + 1));
static_assert(has_single_bit<uint8_t>(tableByEntry[43].first + 1));
static_assert(has_single_bit<uint8_t>(tableByEntry[44].first + 1));
static_assert(has_single_bit<uint8_t>(tableByEntry[45].first + 1));
static_assert(has_single_bit<uint8_t>(tableByEntry[46].first + 1));
static_assert(has_single_bit<uint8_t>(tableByEntry[47].first + 1));
static_assert(has_single_bit<uint8_t>(tableByEntry[48].first + 1));
static_assert(has_single_bit<uint8_t>(tableByEntry[49].first + 1));
static_assert(has_single_bit<uint8_t>(tableByEntry[50].first + 1));
static_assert(has_single_bit<uint8_t>(tableByEntry[51].first + 1));
static_assert(has_single_bit<uint8_t>(tableByEntry[52].first + 1));
static_assert(has_single_bit<uint8_t>(tableByEntry[53].first + 1));
static_assert(has_single_bit<uint8_t>(tableByEntry[54].first + 1));
static_assert(has_single_bit<uint8_t>(tableByEntry[55].first + 1));
static_assert(has_single_bit<uint8_t>(tableByEntry[56].first + 1));
static_assert(has_single_bit<uint8_t>(tableByEntry[57].first + 1));
static_assert(has_single_bit<uint8_t>(tableByEntry[58].first + 1));
static_assert(has_single_bit<uint8_t>(tableByEntry[59].first + 1));
static_assert(has_single_bit<uint8_t>(tableByEntry[60].first + 1));
static_assert(has_single_bit<uint8_t>(tableByEntry[61].first + 1));
static_assert(has_single_bit<uint8_t>(tableByEntry[62].first + 1));
static_assert(has_single_bit<uint8_t>(tableByEntry[63].first + 1));
// Asserting some of the hard-wired cycle values
static_assert(tableByEntry[1 - 1].first == 63);
static_assert(tableByEntry[2 - 1].first == 31);
static_assert(tableByEntry[26 - 1].first == 31);
// Asserting some of the corresponding entries between tableByEntry and tableByBit
static_assert(tableByEntry[26 - 1].second[0].w0ReadMask == tableByBit[26 - 1][0].w0ReadMask);
static_assert(tableByEntry[26 - 1].second[0].w0ReadShr == tableByBit[26 - 1][0].w0ReadShr);
static_assert(tableByEntry[26 - 1].second[0].w1ReadMask == tableByBit[26 - 1][0].w1ReadMask);
static_assert(tableByEntry[26 - 1].second[1].w0ReadMask == tableByBit[26 - 1][26].w0ReadMask);
static_assert(tableByEntry[26 - 1].second[1].w0ReadShr == tableByBit[26 - 1][26].w0ReadShr);
static_assert(tableByEntry[26 - 1].second[1].w1ReadMask == tableByBit[26 - 1][26].w1ReadMask);
static_assert(tableByEntry[26 - 1].second[2].w0ReadMask == tableByBit[26 - 1][52].w0ReadMask);
static_assert(tableByEntry[26 - 1].second[2].w0ReadShr == tableByBit[26 - 1][52].w0ReadShr);
static_assert(tableByEntry[26 - 1].second[2].w1ReadMask == tableByBit[26 - 1][52].w1ReadMask);
static_assert(tableByEntry[26 - 1].second[3].w0ReadMask == tableByBit[26 - 1][14].w0ReadMask);
static_assert(tableByEntry[26 - 1].second[3].w0ReadShr == tableByBit[26 - 1][14].w0ReadShr);
static_assert(tableByEntry[26 - 1].second[3].w1ReadMask == tableByBit[26 - 1][14].w1ReadMask);
static_assert(tableByEntry[26 - 1].second[31].w0ReadMask == tableByBit[26 - 1][38].w0ReadMask);
static_assert(tableByEntry[26 - 1].second[31].w0ReadShr == tableByBit[26 - 1][38].w0ReadShr);
static_assert(tableByEntry[26 - 1].second[31].w1ReadMask == tableByBit[26 - 1][38].w1ReadMask);
![swh spinner](/static/img/swh-spinner.gif)
Computing file changes ...