Source code
Revision control
Copy as Markdown
Other Tools
/***************************************************************************************************
Zyan Core Library (Zycore-C)
Original Author : Florian Bernd
* Permission is hereby granted, free of charge, to any person obtaining a copy
* of this software and associated documentation files (the "Software"), to deal
* in the Software without restriction, including without limitation the rights
* to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
* copies of the Software, and to permit persons to whom the Software is
* furnished to do so, subject to the following conditions:
*
* The above copyright notice and this permission notice shall be included in all
* copies or substantial portions of the Software.
*
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
* IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
* FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
* AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
* LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
* OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
* SOFTWARE.
***************************************************************************************************/
#include "zydis/Zycore/Bitset.h"
#include "zydis/Zycore/LibC.h"
/* ============================================================================================== */
/* Internal constants */
/* ============================================================================================== */
#define ZYAN_BITSET_GROWTH_FACTOR 2
#define ZYAN_BITSET_SHRINK_THRESHOLD 2
/* ============================================================================================== */
/* Internal macros */
/* ============================================================================================== */
/**
* Computes the smallest integer value not less than `x`.
*
* @param x The value.
*
* @return The smallest integer value not less than `x`.
*/
#define ZYAN_BITSET_CEIL(x) \
(((x) == ((ZyanU32)(x))) ? (ZyanU32)(x) : ((ZyanU32)(x)) + 1)
/**
* Converts bits to bytes.
*
* @param x The value in bits.
*
* @return The amount of bytes needed to fit `x` bits.
*/
#define ZYAN_BITSET_BITS_TO_BYTES(x) \
ZYAN_BITSET_CEIL((x) / 8)
/**
* Returns the offset of the given bit.
*
* @param index The bit index.
*
* @return The offset of the given bit.
*/
#define ZYAN_BITSET_BIT_OFFSET(index) \
(7 - ((index) % 8))
/* ============================================================================================== */
/* Internal functions */
/* ============================================================================================== */
/* ---------------------------------------------------------------------------------------------- */
/* Helper functions */
/* ---------------------------------------------------------------------------------------------- */
/**
* Initializes the given `vector` with `count` "zero"-bytes.
*
* @param vector A pointer to the `ZyanVector` instance.
* @param count The number of bytes.
*
* @return A zyan status code.
*/
static ZyanStatus ZyanBitsetInitVectorElements(ZyanVector* vector, ZyanUSize count)
{
ZYAN_ASSERT(vector);
static const ZyanU8 zero = 0;
for (ZyanUSize i = 0; i < count; ++i)
{
ZYAN_CHECK(ZyanVectorPushBack(vector, &zero));
}
return ZYAN_STATUS_SUCCESS;
}
/* ---------------------------------------------------------------------------------------------- */
/* Byte operations */
/* ---------------------------------------------------------------------------------------------- */
static ZyanStatus ZyanBitsetOperationAND(ZyanU8* b1, const ZyanU8* b2)
{
*b1 &= *b2;
return ZYAN_STATUS_SUCCESS;
}
static ZyanStatus ZyanBitsetOperationOR (ZyanU8* b1, const ZyanU8* b2)
{
*b1 |= *b2;
return ZYAN_STATUS_SUCCESS;
}
static ZyanStatus ZyanBitsetOperationXOR(ZyanU8* b1, const ZyanU8* b2)
{
*b1 ^= *b2;
return ZYAN_STATUS_SUCCESS;
}
/* ---------------------------------------------------------------------------------------------- */
/* ============================================================================================== */
/* Exported functions */
/* ============================================================================================== */
/* ---------------------------------------------------------------------------------------------- */
/* Constructor and destructor */
/* ---------------------------------------------------------------------------------------------- */
#ifndef ZYAN_NO_LIBC
ZyanStatus ZyanBitsetInit(ZyanBitset* bitset, ZyanUSize count)
{
return ZyanBitsetInitEx(bitset, count, ZyanAllocatorDefault(), ZYAN_BITSET_GROWTH_FACTOR,
ZYAN_BITSET_SHRINK_THRESHOLD);
}
#endif // ZYAN_NO_LIBC
ZyanStatus ZyanBitsetInitEx(ZyanBitset* bitset, ZyanUSize count, ZyanAllocator* allocator,
ZyanU8 growth_factor, ZyanU8 shrink_threshold)
{
if (!bitset)
{
return ZYAN_STATUS_INVALID_ARGUMENT;
}
const ZyanU32 bytes = ZYAN_BITSET_BITS_TO_BYTES(count);
bitset->size = count;
ZYAN_CHECK(ZyanVectorInitEx(&bitset->bits, sizeof(ZyanU8), bytes, ZYAN_NULL, allocator,
growth_factor, shrink_threshold));
ZYAN_CHECK(ZyanBitsetInitVectorElements(&bitset->bits, bytes));
return ZYAN_STATUS_SUCCESS;
}
ZyanStatus ZyanBitsetInitBuffer(ZyanBitset* bitset, ZyanUSize count, void* buffer,
ZyanUSize capacity)
{
if (!bitset)
{
return ZYAN_STATUS_INVALID_ARGUMENT;
}
const ZyanU32 bytes = ZYAN_BITSET_BITS_TO_BYTES(count);
if (capacity < bytes)
{
return ZYAN_STATUS_INSUFFICIENT_BUFFER_SIZE;
}
bitset->size = count;
ZYAN_CHECK(ZyanVectorInitCustomBuffer(&bitset->bits, sizeof(ZyanU8), buffer, capacity,
ZYAN_NULL));
ZYAN_CHECK(ZyanBitsetInitVectorElements(&bitset->bits, bytes));
return ZYAN_STATUS_SUCCESS;
}
ZyanStatus ZyanBitsetDestroy(ZyanBitset* bitset)
{
if (!bitset)
{
return ZYAN_STATUS_INVALID_ARGUMENT;
}
return ZyanVectorDestroy(&bitset->bits);
}
/* ---------------------------------------------------------------------------------------------- */
/* Logical operations */
/* ---------------------------------------------------------------------------------------------- */
ZyanStatus ZyanBitsetPerformByteOperation(ZyanBitset* destination, const ZyanBitset* source,
ZyanBitsetByteOperation operation)
{
if (!destination || !source || !operation)
{
return ZYAN_STATUS_INVALID_ARGUMENT;
}
ZyanUSize s1;
ZyanUSize s2;
ZYAN_CHECK(ZyanVectorGetSize(&destination->bits, &s1));
ZYAN_CHECK(ZyanVectorGetSize(&source->bits, &s2));
const ZyanUSize min = ZYAN_MIN(s1, s2);
for (ZyanUSize i = 0; i < min; ++i)
{
ZyanU8* v1;
const ZyanU8* v2;
ZYAN_CHECK(ZyanVectorGetPointerMutable(&destination->bits, i, (void**)&v1));
ZYAN_CHECK(ZyanVectorGetPointer(&source->bits, i, (const void**)&v2));
ZYAN_ASSERT(v1);
ZYAN_ASSERT(v2);
ZYAN_CHECK(operation(v1, v2));
}
return ZYAN_STATUS_SUCCESS;
}
ZyanStatus ZyanBitsetAND(ZyanBitset* destination, const ZyanBitset* source)
{
return ZyanBitsetPerformByteOperation(destination, source, ZyanBitsetOperationAND);
}
ZyanStatus ZyanBitsetOR (ZyanBitset* destination, const ZyanBitset* source)
{
return ZyanBitsetPerformByteOperation(destination, source, ZyanBitsetOperationOR );
}
ZyanStatus ZyanBitsetXOR(ZyanBitset* destination, const ZyanBitset* source)
{
return ZyanBitsetPerformByteOperation(destination, source, ZyanBitsetOperationXOR);
}
ZyanStatus ZyanBitsetFlip(ZyanBitset* bitset)
{
if (!bitset)
{
return ZYAN_STATUS_INVALID_ARGUMENT;
}
ZyanUSize size;
ZYAN_CHECK(ZyanVectorGetSize(&bitset->bits, &size));
for (ZyanUSize i = 0; i < size; ++i)
{
ZyanU8* value;
ZYAN_CHECK(ZyanVectorGetPointerMutable(&bitset->bits, i, (void**)&value));
*value = ~(*value);
}
return ZYAN_STATUS_SUCCESS;
}
/* ---------------------------------------------------------------------------------------------- */
/* Bit access */
/* ---------------------------------------------------------------------------------------------- */
ZyanStatus ZyanBitsetSet(ZyanBitset* bitset, ZyanUSize index)
{
if (!bitset)
{
return ZYAN_STATUS_INVALID_ARGUMENT;
}
if (index >= bitset->size)
{
return ZYAN_STATUS_OUT_OF_RANGE;
}
ZyanU8* value;
ZYAN_CHECK(ZyanVectorGetPointerMutable(&bitset->bits, index / 8, (void**)&value));
*value |= (1 << ZYAN_BITSET_BIT_OFFSET(index));
return ZYAN_STATUS_SUCCESS;
}
ZyanStatus ZyanBitsetReset(ZyanBitset* bitset, ZyanUSize index)
{
if (!bitset)
{
return ZYAN_STATUS_INVALID_ARGUMENT;
}
if (index >= bitset->size)
{
return ZYAN_STATUS_OUT_OF_RANGE;
}
ZyanU8* value;
ZYAN_CHECK(ZyanVectorGetPointerMutable(&bitset->bits, index / 8, (void**)&value));
*value &= ~(1 << ZYAN_BITSET_BIT_OFFSET(index));
return ZYAN_STATUS_SUCCESS;
}
ZyanStatus ZyanBitsetAssign(ZyanBitset* bitset, ZyanUSize index, ZyanBool value)
{
if (value)
{
return ZyanBitsetSet(bitset, index);
}
return ZyanBitsetReset(bitset, index);
}
ZyanStatus ZyanBitsetToggle(ZyanBitset* bitset, ZyanUSize index)
{
if (!bitset)
{
return ZYAN_STATUS_INVALID_ARGUMENT;
}
if (index >= bitset->size)
{
return ZYAN_STATUS_OUT_OF_RANGE;
}
ZyanU8* value;
ZYAN_CHECK(ZyanVectorGetPointerMutable(&bitset->bits, index / 8, (void**)&value));
*value ^= (1 << ZYAN_BITSET_BIT_OFFSET(index));
return ZYAN_STATUS_SUCCESS;
}
ZyanStatus ZyanBitsetTest(ZyanBitset* bitset, ZyanUSize index)
{
if (!bitset)
{
return ZYAN_STATUS_INVALID_ARGUMENT;
}
if (index >= bitset->size)
{
return ZYAN_STATUS_OUT_OF_RANGE;
}
const ZyanU8* value;
ZYAN_CHECK(ZyanVectorGetPointer(&bitset->bits, index / 8, (const void**)&value));
if ((*value & (1 << ZYAN_BITSET_BIT_OFFSET(index))) == 0)
{
return ZYAN_STATUS_FALSE;
}
return ZYAN_STATUS_TRUE;
}
ZyanStatus ZyanBitsetTestMSB(ZyanBitset* bitset)
{
if (!bitset)
{
return ZYAN_STATUS_INVALID_ARGUMENT;
}
return ZyanBitsetTest(bitset, bitset->size - 1);
}
ZyanStatus ZyanBitsetTestLSB(ZyanBitset* bitset)
{
return ZyanBitsetTest(bitset, 0);
}
/* ---------------------------------------------------------------------------------------------- */
ZyanStatus ZyanBitsetSetAll(ZyanBitset* bitset)
{
if (!bitset)
{
return ZYAN_STATUS_INVALID_ARGUMENT;
}
ZyanUSize size;
ZYAN_CHECK(ZyanVectorGetSize(&bitset->bits, &size));
for (ZyanUSize i = 0; i < size; ++i)
{
ZyanU8* value;
ZYAN_CHECK(ZyanVectorGetPointerMutable(&bitset->bits, i, (void**)&value));
*value = 0xFF;
}
return ZYAN_STATUS_SUCCESS;
}
ZyanStatus ZyanBitsetResetAll(ZyanBitset* bitset)
{
if (!bitset)
{
return ZYAN_STATUS_INVALID_ARGUMENT;
}
ZyanUSize size;
ZYAN_CHECK(ZyanVectorGetSize(&bitset->bits, &size));
for (ZyanUSize i = 0; i < size; ++i)
{
ZyanU8* value;
ZYAN_CHECK(ZyanVectorGetPointerMutable(&bitset->bits, i, (void**)&value));
*value = 0x00;
}
return ZYAN_STATUS_SUCCESS;
}
/* ---------------------------------------------------------------------------------------------- */
/* Size management */
/* ---------------------------------------------------------------------------------------------- */
ZyanStatus ZyanBitsetPush(ZyanBitset* bitset, ZyanBool value)
{
if (!bitset)
{
return ZYAN_STATUS_INVALID_ARGUMENT;
}
if ((bitset->size++ % 8) == 0)
{
static const ZyanU8 zero = 0;
ZYAN_CHECK(ZyanVectorPushBack(&bitset->bits, &zero));
}
return ZyanBitsetAssign(bitset, bitset->size - 1, value);
}
ZyanStatus ZyanBitsetPop(ZyanBitset* bitset)
{
if (!bitset)
{
return ZYAN_STATUS_INVALID_ARGUMENT;
}
if ((--bitset->size % 8) == 0)
{
return ZyanVectorPopBack(&bitset->bits);
}
return ZYAN_STATUS_SUCCESS;
}
ZyanStatus ZyanBitsetClear(ZyanBitset* bitset)
{
if (!bitset)
{
return ZYAN_STATUS_INVALID_ARGUMENT;
}
bitset->size = 0;
return ZyanVectorClear(&bitset->bits);
}
/* ---------------------------------------------------------------------------------------------- */
/* Memory management */
/* ---------------------------------------------------------------------------------------------- */
ZyanStatus ZyanBitsetReserve(ZyanBitset* bitset, ZyanUSize count)
{
return ZyanVectorReserve(&bitset->bits, ZYAN_BITSET_BITS_TO_BYTES(count));
}
ZyanStatus ZyanBitsetShrinkToFit(ZyanBitset* bitset)
{
return ZyanVectorShrinkToFit(&bitset->bits);
}
/* ---------------------------------------------------------------------------------------------- */
/* Information */
/* ---------------------------------------------------------------------------------------------- */
ZyanStatus ZyanBitsetGetSize(const ZyanBitset* bitset, ZyanUSize* size)
{
if (!bitset)
{
return ZYAN_STATUS_INVALID_ARGUMENT;
}
*size = bitset->size;
return ZYAN_STATUS_SUCCESS;
}
ZyanStatus ZyanBitsetGetCapacity(const ZyanBitset* bitset, ZyanUSize* capacity)
{
ZYAN_CHECK(ZyanBitsetGetCapacityBytes(bitset, capacity));
*capacity *= 8;
return ZYAN_STATUS_SUCCESS;
}
ZyanStatus ZyanBitsetGetSizeBytes(const ZyanBitset* bitset, ZyanUSize* size)
{
if (!bitset)
{
return ZYAN_STATUS_INVALID_ARGUMENT;
}
return ZyanVectorGetSize(&bitset->bits, size);
}
ZyanStatus ZyanBitsetGetCapacityBytes(const ZyanBitset* bitset, ZyanUSize* capacity)
{
if (!bitset)
{
return ZYAN_STATUS_INVALID_ARGUMENT;
}
return ZyanVectorGetCapacity(&bitset->bits, capacity);
}
/* ---------------------------------------------------------------------------------------------- */
ZyanStatus ZyanBitsetCount(const ZyanBitset* bitset, ZyanUSize* count)
{
if (!bitset || !count)
{
return ZYAN_STATUS_INVALID_ARGUMENT;
}
*count = 0;
ZyanUSize size;
ZYAN_CHECK(ZyanVectorGetSize(&bitset->bits, &size));
for (ZyanUSize i = 0; i < size; ++i)
{
ZyanU8* value;
ZYAN_CHECK(ZyanVectorGetPointer(&bitset->bits, i, (const void**)&value));
ZyanU8 popcnt = *value;
popcnt = (popcnt & 0x55) + ((popcnt >> 1) & 0x55);
popcnt = (popcnt & 0x33) + ((popcnt >> 2) & 0x33);
popcnt = (popcnt & 0x0F) + ((popcnt >> 4) & 0x0F);
*count += popcnt;
}
*count = ZYAN_MIN(*count, bitset->size);
return ZYAN_STATUS_SUCCESS;
}
ZyanStatus ZyanBitsetAll(const ZyanBitset* bitset)
{
if (!bitset)
{
return ZYAN_STATUS_INVALID_ARGUMENT;
}
ZyanUSize size;
ZYAN_CHECK(ZyanVectorGetSize(&bitset->bits, &size));
for (ZyanUSize i = 0; i < size; ++i)
{
ZyanU8* value;
ZYAN_CHECK(ZyanVectorGetPointer(&bitset->bits, i, (const void**)&value));
if (i < (size - 1))
{
if (*value != 0xFF)
{
return ZYAN_STATUS_FALSE;
}
} else
{
const ZyanU8 mask = ~(8 - (bitset->size % 8));
if ((*value & mask) != mask)
{
return ZYAN_STATUS_FALSE;
}
}
}
return ZYAN_STATUS_TRUE;
}
ZyanStatus ZyanBitsetAny(const ZyanBitset* bitset)
{
if (!bitset)
{
return ZYAN_STATUS_INVALID_ARGUMENT;
}
ZyanUSize size;
ZYAN_CHECK(ZyanVectorGetSize(&bitset->bits, &size));
for (ZyanUSize i = 0; i < size; ++i)
{
ZyanU8* value;
ZYAN_CHECK(ZyanVectorGetPointer(&bitset->bits, i, (const void**)&value));
if (i < (size - 1))
{
if (*value != 0x00)
{
return ZYAN_STATUS_TRUE;
}
} else
{
const ZyanU8 mask = ~(8 - (bitset->size % 8));
if ((*value & mask) != 0x00)
{
return ZYAN_STATUS_TRUE;
}
}
}
return ZYAN_STATUS_FALSE;
}
ZyanStatus ZyanBitsetNone(const ZyanBitset* bitset)
{
if (!bitset)
{
return ZYAN_STATUS_INVALID_ARGUMENT;
}
ZyanUSize size;
ZYAN_CHECK(ZyanVectorGetSize(&bitset->bits, &size));
for (ZyanUSize i = 0; i < size; ++i)
{
ZyanU8* value;
ZYAN_CHECK(ZyanVectorGetPointer(&bitset->bits, i, (const void**)&value));
if (i < (size - 1))
{
if (*value != 0x00)
{
return ZYAN_STATUS_FALSE;
}
} else
{
const ZyanU8 mask = ~(8 - (bitset->size % 8));
if ((*value & mask) != 0x00)
{
return ZYAN_STATUS_FALSE;
}
}
}
return ZYAN_STATUS_TRUE;
}
/* ---------------------------------------------------------------------------------------------- */
//ZyanStatus ZyanBitsetToU32(const ZyanBitset* bitset, ZyanU32* value)
//{
// if (!bitset)
// {
// return ZYAN_STATUS_INVALID_ARGUMENT;
// }
// if (bitset->size > 32)
// {
// return ZYAN_STATUS_INVALID_OPERATION;
// }
//
// // TODO:
//
// return ZYAN_STATUS_SUCCESS;
//}
//
//ZyanStatus ZyanBitsetToU64(const ZyanBitset* bitset, ZyanU64* value)
//{
// if (!bitset)
// {
// return ZYAN_STATUS_INVALID_ARGUMENT;
// }
// if (bitset->size > 64)
// {
// return ZYAN_STATUS_INVALID_OPERATION;
// }
//
// // TODO:
//
// return ZYAN_STATUS_SUCCESS;
//}
/* ---------------------------------------------------------------------------------------------- */
/* ============================================================================================== */