我想知道是否有支持任意位置位操作的高性能 C/C++ 库？
例如：
int BitCompare(const void* src, size_t srcOffsetInBits, const void* dst, size_t dstOffsetInBits, size_t sizeInBits);
比较[srcOffsetInBits, srcOffsetInBits + sizeInBits - 1]src 和[dstOffsetInBits, dstOffsetInBits + sizeInBits - 1]dst 中的位的函数，这些位被认为是 little-endian 无符号整数。假定所有缓冲区都足够大。
bool BitEqual(...);
void BitMove(...); // src and dst can overlap.
void BitCopy(...); // src and dst cannot overlap.
所有操作都应该只修改正在操作的位，而所有其他位都应该保留。
我做了一些尝试来实现 BitCompare。
static uint8_t mask8l1[9] = {
0x00, 0x01, 0x03, 0x07, 0x0F, 0x1F, 0x3F, 0x7F, 0xFF
};
static uint8_t mask8l0[9] = {
0xFF, 0xFE, 0xFC, 0xF8, 0xF0, 0xE0, 0xC0, 0x80, 0x00
};
// Offset-less compare.
int BitCompare8(const void* src, const void* dst, size_t sizeInBits)/*{{{*/
{
const uint8_t* _src = static_cast<const uint8_t*>(src);
const uint8_t* _dst = static_cast<const uint8_t*>(dst);
size_t sizeInUint8s = sizeInBits >> 3;
size_t sizeRemaining = sizeInBits & 0x07;
// MSB ---> LSB
// : bits-to-compare :
// ----------------------------------------- ---------------------
// | : sizeRemaining | | ... | |
// ----------------------------------------- ---------------------
// @_src + sizeInUint8s @_src
//
// ----------------------------------------- ---------------------
// | : sizeRemaining | | ... | |
// ----------------------------------------- ---------------------
// @_dst + sizeInUint8s @_dst
_src += sizeInUint8s;
_dst += sizeInUint8s;
// Compare the MSB sizeRemaining bits first.
if (sizeRemaining)
{
// : sizeRemaining :
// ----------------------
// | : s |
// ----------------------
// @_src
// : sizeRemaining :
// ----------------------
// | : d |
// ----------------------
// @_dst
uint8_t s = *_src & mask8l1[sizeRemaining];
uint8_t d = *_dst & mask8l1[sizeRemaining];
if (s < d)
{
return -1;
}
else if (d < s)
{
return 1;
}
}
// Then compare the LSB uint8s.
while (sizeInUint8s)
{
// ----------------------
// | s |
// ----------------------
// @_src - 1
// ---------------------
// | d |
// ---------------------
// @_dst - 1
uint8_t s = *--_src;
uint8_t d = *--_dst;
if (s < d)
{
return -1;
}
else if (d < s)
{
return 1;
}
--sizeInUint8s;
}
return 0;
}/*}}}*/
// Source-side offset compare.
int BitCompare8(const void* src, size_t offsetInBits, /*{{{*/
const void* dst, size_t sizeInBits)
{
const uint8_t* _src = static_cast<const uint8_t*>(src);
const uint8_t* _dst = static_cast<const uint8_t*>(dst);
_src += offsetInBits >> 3;
offsetInBits &= 0x07;
if (!offsetInBits)
{
return BitCompare8(_src, _dst, sizeInBits);
}
size_t sizeInUint8s = sizeInBits >> 3;
size_t sizeRemaining = sizeInBits & 0x07;
// MSB ---> LSB
// : bits-to-compare :
// : sizeRemaining : :
// ----------------------------------------- ---------------------
// | | : offsetInBits | ... | : offsetInBits |
// ----------------------------------------- ---------------------
// @_src + sizeInUint8s @_src
//
// ----------------------------------------- ---------------------
// | : sizeRemaining | | ... | |
// ----------------------------------------- ---------------------
// @_dst + sizeInUint8s @_dst
_src += sizeInUint8s;
_dst += sizeInUint8s;
// Move the MSB sizeRemaining bits first.
if (sizeRemaining)
{
if (sizeRemaining + offsetInBits <= 8)
{
// : sizeRemaining :
// ----------------------------------
// | : s : offsetInBits |
// ----------------------------------
// @_src
// : sizeRemaining :
// ----------------------------------
// | : d |
// ----------------------------------
// @_dst
uint8_t s = (*_src >> offsetInBits) & mask8l1[sizeRemaining];
uint8_t d = *_dst & mask8l1[sizeRemaining];
if (s < d)
{
return -1;
}
else if (d < s)
{
return 1;
}
}
else // if (sizeRemaining + offsetInBits > 8)
{
// : sizeRemaining :
// -------------------------------------------------------------------
// | : a | b : offsetInBits |
// -------------------------------------------------------------------
// @_src + 1 @_src
//
// : sizeRemaining :
// ----------------------------------
// | : a : b |
// ----------------------------------
// : : @_dst
// : offsetInBits :
//
// a = sizeRemaining - (8 - offsetInBits)
// b = 8 - offsetInBits
//
// Note: offsetInBits > 8 - sizeRemaining > 0
// a < 8
uint8_t a = (*(_src + 1) << (8 - offsetInBits))
& mask8l1[sizeRemaining];
uint8_t b = *_src >> offsetInBits;
uint8_t s = a | b;
uint8_t d = *_dst & mask8l1[sizeRemaining];
if (s < d)
{
return -1;
}
else if (d < s)
{
return 1;
}
}
}
// Then move the LSB uint8s.
while (sizeInUint8s)
{
// : offsetInBits :
// -----------------------------------------
// | : a | b : offsetInBits |
// -----------------------------------------
// @_src @_src - 1
// : offsetInBits :
// ---------------------
// | a : b |
// ---------------------
// @_dst - 1
//
uint8_t a = *_src << (8 - offsetInBits);
uint8_t b = *--_src >> offsetInBits;
uint8_t s = a | b;
uint8_t d = *--_dst;
if (s < d)
{
return -1;
}
else if (d < s)
{
return 1;
}
--sizeInUint8s;
}
return 0;
}/*}}}*/
// Destination-side offset compare.
int BitCompare8(const void* src, /*{{{*/
const void* dst, size_t offsetInBits,
size_t sizeInBits)
{
return -BitCompare8(dst, offsetInBits, src, sizeInBits);
}/*}}}*/
// Generic compare.
int BitCompare8(const void* src, size_t srcOffsetInBits, /*{{{*/
const void* dst, size_t dstOffsetInBits,
size_t sizeInBits)
{
const uint8_t* _src = static_cast<const uint8_t*>(src);
const uint8_t* _dst = static_cast<const uint8_t*>(dst);
_src += srcOffsetInBits >> 3;
srcOffsetInBits &= 0x07;
if (!srcOffsetInBits)
{
return -BitCompare8(_dst, dstOffsetInBits, _src, sizeInBits);
}
_dst += dstOffsetInBits >> 3;
dstOffsetInBits &= 0x07;
if (!dstOffsetInBits)
{
return BitCompare8(_src, srcOffsetInBits, _dst, sizeInBits);
}
size_t sizeInUint8s = sizeInBits >> 3;
size_t sizeRemaining = sizeInBits & 0x07;
// MSB ---> LSB
// : bits-to-compare :
// : sizeRemaining : :
// ----------------------------------------------- ------------------------
// | | : srcOffsetInBits | ... | : srcOffsetInBits |
// ----------------------------------------------- ------------------------
// @_src + sizeInUint8s @_src
//
// : sizeRemaining :
// ----------------------------------------------- ------------------------
// | | : dstOffsetInBits | ... | : dstOffsetInBits |
// ----------------------------------------------- ------------------------
// @_dst + sizeInUint8s @_dst
if (srcOffsetInBits <= dstOffsetInBits)
{
// : sizeRemaining :
// -----------------------------------------------
// | | : srcOffsetInBits |
// -----------------------------------------------
// @_src
//
// : sizeRemaining :
// -----------------------------------------------
// | | : dstOffsetInBits |
// -----------------------------------------------
// @_dst
if (!sizeInUint8s)
{
if (sizeRemaining + dstOffsetInBits <= 8)
{
// : sizeRemaining :
// -----------------------------------------------
// | : s : srcOffsetInBits |
// -----------------------------------------------
// @_src
//
// : sizeRemaining :
// -----------------------------------------------
// | : d : dstOffsetInBits |
// -----------------------------------------------
// @_dst
// There're only sizeRemaining bits to compare.
uint8_t s = (*_src >> srcOffsetInBits)
& mask8l1[sizeRemaining];
uint8_t d = (*_dst >> dstOffsetInBits)
& mask8l1[sizeRemaining];
if (s < d)
{
return -1;
}
else if (d < s)
{
return 1;
}
}
else // if (sizeRemaining + dstOffsetInBits > 8)
{
// : sizeRemaining :
// -------------------------------------------------
// | : a | b : srcOffsetInBits |
// -------------------------------------------------
// @_src
//
// : sizeRemaining :
// -------------------------------------------------
// | : a | b : dstOffsetInBits |
// -------------------------------------------------
// @_dst + 1 @_dst
uint8_t a = *_src++ >> srcOffsetInBits;
uint8_t b = (*_src << (8 - srcOffsetInBits))
& mask8l1[sizeRemaining];
uint8_t s = a | b;
a = *_dst++ >> dstOffsetInBits;
b = (*_dst << (8 - dstOffsetInBits))
& mask8l1[sizeRemaining];
uint8_t d = a | b;
if (s < d)
{
return -1;
}
else if (d < s)
{
return 1;
}
}
return 0;
}
// There're more than (8 - dstOffsetInBits) bits to compare.
// Compare MSB bits first.
// <- MSB bits to compare ->:
// :---:>(8 - dstOffsetInBits)
// : sizeRemaining :
// -------------------------------------------------
// | : | : s : srcOffsetInBits |
// -------------------------------------------------
// @_src
//
// <- MSB bits to compare ->:
// : sizeRemaining :
// -------------------------------------------------
// | : | d : dstOffsetInBits |
// -------------------------------------------------
// @_dst + 1 @_dst
int result = BitCompare8(
_src, srcOffsetInBits + (8 - dstOffsetInBits),
_dst + 1, sizeInBits - (8 - dstOffsetInBits));
if (result)
{
return result;
}
// Then compare LSB (8 - dstOffsetInBits) bits.
uint8_t s = (*_src >> srcOffsetInBits) & mask8m0[dstOffsetInBits];
uint8_t d = *_dst++ >> dstOffsetInBits;
if (s < d)
{
return -1;
}
else if (d < s)
{
return 1;
}
}
else // if (dstOffsetInBits < srcOffsetInBits)
{
// : sizeRemaining :
// -----------------------------------------------
// | | : srcOffsetInBits |
// -----------------------------------------------
// @_src
//
// : sizeRemaining :
// -----------------------------------------------
// | | : dstOffsetInBits |
// -----------------------------------------------
// @_dst
if (!sizeInUint8s)
{
if (sizeRemaining + srcOffsetInBits <= 8)
{
// : sizeRemaining :
// -----------------------------------------------
// | : s : srcOffsetInBits |
// -----------------------------------------------
// @_src
//
// : sizeRemaining :
// -----------------------------------------------
// | : d : dstOffsetInBits |
// -----------------------------------------------
// @_dst
// There're only sizeRemaining bits to compare.
uint8_t s = (*_src >> srcOffsetInBits)
& mask8l1[sizeRemaining];
uint8_t d = (*_dst >> dstOffsetInBits)
& mask8l1[sizeRemaining];
if (s < d)
{
return -1;
}
else if (d < s)
{
return 1;
}
}
else // if (sizeRemaining + srcOffsetInBits > 8)
{
// : sizeRemaining :
// -------------------------------------------------
// | : a | b : srcOffsetInBits |
// -------------------------------------------------
// @_src + 1 @_src
//
// : sizeRemaining :
// -------------------------------------------------
// | : a | b : dstOffsetInBits |
// -------------------------------------------------
// @_dst + 1 @_dst
uint8_t a = *_src++ >> srcOffsetInBits;
uint8_t b = (*_src << (8 - srcOffsetInBits))
& mask8l1[sizeRemaining];
uint8_t s = a | b;
a = *_dst++ >> dstOffsetInBits;
b = (*_dst << (8 - dstOffsetInBits))
& mask8l1[sizeRemaining];
uint8_t d = a | b;
if (s < d)
{
return -1;
}
else if (d < s)
{
return 1;
}
}
return 0;
}
// There're more than (8 - srcOffsetInBits) bits to compare.
// Compare MSB bits first.
//
// <- MSB bits to compare ->:
// : sizeRemaining :
// -------------------------------------------------
// | : | s : srcOffsetInBits |
// -------------------------------------------------
// @_src + 1 @_src
//
// <- MSB bits to compare ->:
// :---:>(8 - srcOffsetInBits)
// : sizeRemaining :
// -------------------------------------------------
// | : | : d : dstOffsetInBits |
// -------------------------------------------------
// @_dst + 1 @_dst
int result = BitCompare8(
_dst, dstOffsetInBits + (8 - srcOffsetInBits),
_src + 1, sizeInBits - (8 - srcOffsetInBits));
if (result)
{
return result;
}
// Then compare LSB (8 - srcOffsetInBits) bits.
uint8_t s = *_src++ >> srcOffsetInBits;
uint8_t d = (*_dst >> dstOffsetInBits) & mask8m0[srcOffsetInBits];
if (s < d)
{
return -1;
}
else if (d < s)
{
return 1;
}
}
return 0;
}/*}}}*/