Sux
Namespaces | Classes | Functions | Variables
sux Namespace Reference

Namespaces

 bits
 
 function
 
 util
 

Classes

class  Rank
 
class  Select
 
class  SelectZero
 

Typedefs

using auint64_t = std::uint64_t __attribute__((__may_alias__))
 
using auint32_t = std::uint32_t __attribute__((__may_alias__))
 
using auint16_t = std::uint16_t __attribute__((__may_alias__))
 
using auint8_t = std::uint8_t __attribute__((__may_alias__))
 

Functions

constexpr size_t ceil_log2_plus1 (size_t n)
 
int ceil_log2 (const uint64_t x)
 
constexpr uint64_t round_pow2 (uint64_t v)
 
int rho (uint64_t word)
 
int lambda (uint64_t word)
 
int lambda_safe (uint64_t word)
 
uint64_t clear_rho (uint64_t word)
 
uint64_t mask_rho (uint64_t word)
 
uint64_t mask_lambda (uint64_t word)
 
uint64_t compact_bitmask (size_t count, size_t pos)
 
uint64_t bitextract (const uint64_t *word, int from, int length)
 
uint64_t byteread (const void *const word, int length)
 
void bytewrite (void *const word, int length, uint64_t val)
 
void bytewrite_inc (void *const word, uint64_t inc)
 
uint64_t bitread (const void *const word, int from, int length)
 
void bitwrite (void *word, int from, int length, uint64_t val)
 
void bitwrite_inc (void *const word, int from, int length, uint64_t inc)
 
int nu (uint64_t word)
 
uint64_t mround (uint64_t number, uint64_t multiple)
 
size_t updroot (size_t j, size_t n)
 
uint64_t select64 (uint64_t x, uint64_t k)
 
bool is_big_endian (void)
 
bool is_little_endian (void)
 
template<class T >
std::enable_if< std::is_integral< T >::value, T >::type swap_endian (T value)
 
template<class T >
hton (T value)
 
template<class T >
ntoh (T value)
 
template<class T >
ltoh (T value)
 
template<class T >
htol (T value)
 

Variables

constexpr uint8_t kSelectInByte [2048]
 

Typedef Documentation

◆ auint16_t

using sux::auint16_t = typedef std::uint16_t __attribute__((__may_alias__))

◆ auint32_t

using sux::auint32_t = typedef std::uint32_t __attribute__((__may_alias__))

◆ auint64_t

using sux::auint64_t = typedef std::uint64_t __attribute__((__may_alias__))

Aliased unsigned integers

Strict aliasing rule: it's illegal to access the same memory location with data of different types. If you have two pointers T* and a U*, the compiler can assume they are not pointing the same data. Accessing such a data invokes undefined behavior.

GCC may_alias attribute is basically the opposite of the C restrict keyword: it prevents the compiler to make strict aliasing assumptions. With these aliased types is now valid to access aliased pointers. [1]

[1] https://gcc.gnu.org/onlinedocs/gcc-8.2.0/gcc/Common-Type-Attributes.html

◆ auint8_t

using sux::auint8_t = typedef std::uint8_t __attribute__((__may_alias__))

Function Documentation

◆ bitextract()

uint64_t sux::bitextract ( const uint64_t *  word,
int  from,
int  length 
)
inline

Extract consecutives bits in a word.

Parameters
wordbinary word.
fromstarting index (up to 63).
lengthlength of the word (up to 64).

Extracts from word the bits in the range [from, from + length) and returns them in the least significant bits of the result.

◆ bitread()

uint64_t sux::bitread ( const void *const  word,
int  from,
int  length 
)
inline

◆ bitwrite()

void sux::bitwrite ( void *  word,
int  from,
int  length,
uint64_t  val 
)
inline

◆ bitwrite_inc()

void sux::bitwrite_inc ( void *const  word,
int  from,
int  length,
uint64_t  inc 
)
inline

◆ byteread()

uint64_t sux::byteread ( const void *const  word,
int  length 
)
inline

◆ bytewrite()

void sux::bytewrite ( void *const  word,
int  length,
uint64_t  val 
)
inline

◆ bytewrite_inc()

void sux::bytewrite_inc ( void *const  word,
uint64_t  inc 
)
inline

◆ ceil_log2()

int sux::ceil_log2 ( const uint64_t  x)
inline

log2 rounded up.

◆ ceil_log2_plus1()

constexpr size_t sux::ceil_log2_plus1 ( size_t  n)
constexpr

Static (i.e. computed in compile time) 1 + log2 rounded up.

◆ clear_rho()

uint64_t sux::clear_rho ( uint64_t  word)
inline

Set to 0 the least significant 1-bit in a word.

Parameters
wordbinary word.

◆ compact_bitmask()

uint64_t sux::compact_bitmask ( size_t  count,
size_t  pos 
)
inline

Generate a compact bitmask.

Parameters
countquantity of set bit.
posstarting position.

This fucntion returns a bitmask with count 1-bits: every bit from pos to pos+count is set to one. If pos is zero the bitmask has its count least significant bits setted to one.

◆ htol()

template<class T >
T sux::htol ( value)

Host endianness to little endian converter

Parameters
valueintegral value

◆ hton()

template<class T >
T sux::hton ( value)

Host to network endianness converter

Parameters
valueintegral value

◆ is_big_endian()

bool sux::is_big_endian ( void  )
inline

Check if the architecture is big endian

◆ is_little_endian()

bool sux::is_little_endian ( void  )
inline

Check if the architecture is little endian

◆ lambda()

int sux::lambda ( uint64_t  word)
inline

Find the index of the most significant 1-bit in a word.

Parameters
wordbinary word.

The Knuth's lambda function is the dual of the rho function.

The behavior in zero is undefined.

◆ lambda_safe()

int sux::lambda_safe ( uint64_t  word)
inline

Find the index of the most significant 1-bit in a word.

Parameters
wordbinary word.

The Knuth's lambda function is the dual of the rho function.

Returns -1 on input zero.

◆ ltoh()

template<class T >
T sux::ltoh ( value)

Little endian to host endianness converter

Parameters
valueintegral value

◆ mask_lambda()

uint64_t sux::mask_lambda ( uint64_t  word)
inline

Bitmask where only the most significant 1-bit is set.

Parameters
wordBinary word.

Undefined behavior when word is zero.

◆ mask_rho()

uint64_t sux::mask_rho ( uint64_t  word)
inline

Bitmask where only the least significant 1-bit is set.

Parameters
wordBinary word.

Compute 2^rho(word) for any word that is not zero.

◆ mround()

uint64_t sux::mround ( uint64_t  number,
uint64_t  multiple 
)
inline

Return a number rounded to the desired power of two multiple.

Parameters
numbervalue to round up.
multiplepower of two to which you want to round number.

◆ ntoh()

template<class T >
T sux::ntoh ( value)

Network to host endianness converter

Parameters
valueintegral value

◆ nu()

int sux::nu ( uint64_t  word)
inline

Count the number of 1-bits in a word.

Parameters
wordbinary word.

◆ rho()

int sux::rho ( uint64_t  word)
inline

Find the index of the least significant 1-bit in a word.

Parameters
wordbinary word.

The Knuth's ruler function returns the number of trailing 0-bits in word starting from the least significant position. It returns 0 when word is 2^0 and it returns 63 when it is 2^63.

The behavior in zero is undefined.

◆ round_pow2()

constexpr uint64_t sux::round_pow2 ( uint64_t  v)
constexpr

Static round up to the next highest power of two.

Parameters
vvalue to round up.

The algorithm is a well known bit hack [1].

[1] https://graphics.stanford.edu/~seander/bithacks.html#RoundUpPowerOf2

◆ select64()

uint64_t sux::select64 ( uint64_t  x,
uint64_t  k 
)
inline

Returns the index of the k-th 1-bit in the 64-bit word x.

Parameters
x64-bit word.
k0-based rank (k = 0 returns the position of the first 1-bit).

Uses the broadword selection algorithm by Vigna [1], improved by Gog and Petri [2] and Vigna [3]. Facebook's Folly implementation [4].

[1] Sebastiano Vigna. Broadword Implementation of Rank/Select Queries. WEA, 2008

[2] Simon Gog, Matthias Petri. Optimized succinct data structures for massive data. Softw. Pract. Exper., 2014

[3] Sebastiano Vigna. MG4J 5.2.1. http://mg4j.di.unimi.it/

[4] Facebook Folly library: https://github.com/facebook/folly

◆ swap_endian()

template<class T >
std::enable_if<std::is_integral<T>::value, T>::type sux::swap_endian ( value)

Transform from big-endian to little-endian and vice versa

Parameters
valueintegral value (sizeof 1, 2, 4 or 8 bytes)

◆ updroot()

size_t sux::updroot ( size_t  j,
size_t  n 
)
inline

Grandest grandparent parent of a node in the update tree.

Parameters
jindex of a node.
nsize of the Fenwick tree.

Variable Documentation

◆ kSelectInByte

constexpr uint8_t sux::kSelectInByte[2048]
constexpr