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 >
T	hton (T value)
template<class T >
T	ntoh (T value)
template<class T >
T	ltoh (T value)
template<class T >
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

word	binary word.
from	starting index (up to 63).
length	length 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

word	binary word.

compact_bitmask()

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

inline

Generate a compact bitmask.

Parameters

count	quantity of set bit.
pos	starting 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

(

T

value

)

Host endianness to little endian converter

Parameters

value

integral value

hton()

template<class T >

T sux::hton

(

T

value

)

Host to network endianness converter

Parameters

value

integral 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

word	binary 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

word	binary 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

(

T

value

)

Little endian to host endianness converter

Parameters

value

integral value

mask_lambda()

uint64_t sux::mask_lambda ( uint64_t  word )

inline

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

Parameters

word	Binary 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

word	Binary 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

number	value to round up.
multiple	power of two to which you want to round number.

ntoh()

template<class T >

T sux::ntoh

(

T

value

)

Network to host endianness converter

Parameters

value

integral value

nu()

int sux::nu ( uint64_t  word )

inline

Count the number of 1-bits in a word.

Parameters

word	binary word.

rho()

int sux::rho ( uint64_t  word )

inline

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

Parameters

word	binary 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

v	value 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

x	64-bit word.
k	0-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

(

T

value

)

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

Parameters

value

integral 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

j	index of a node.
n	size of the Fenwick tree.

Variable Documentation

kSelectInByte

constexpr uint8_t sux::kSelectInByte[2048]

constexpr