SDSL: Succinct Data Structure Library
A C++ template library for succinct data structures
 All Classes Namespaces Files Functions Variables Typedefs Friends
Static Public Member Functions | Static Public Attributes
sdsl::bit_magic Class Reference

A helper class for bitwise tricks on 64 bit words. More...

#include <bitmagic.hpp>

List of all members.

Static Public Member Functions

static void generate_first_pos_of_excess_val ()
static void generate_last_pos_of_excess_val ()
static void generate_very_near_find_open ()
static void generate_very_near_enclose ()
static uint64_t b1Cnt (uint64_t x)
 Counts the number of 1-bits in the 64bit integer x.
static uint32_t b1Cnt32 (uint32_t x)
 Counts the number of 1-bits in the 32bit integer x.
static uint32_t b1CntNaive (uint64_t x)
 Naive implementation of the b1Cnt function.
static uint32_t b11Cnt (uint64_t x, uint64_t &c)
 Count the number of consecutive and distinct 11 in the 64bit integer x.
static uint32_t b11CntS (uint64_t x, uint64_t &c)
static uint32_t b11CntS (uint64_t x)
static uint32_t b11Cnt (uint64_t x)
 Count the number of consecutive and distinct 11 in the 64bit integer x.
static uint32_t b11CntNaive (uint64_t x)
 Naive implementation of the b11Cnt function.
static uint32_t eB11Cnt (uint64_t x)
 Count 11 bit pairs starting at even positions in the 64bit integer x.
static uint32_t b10Cnt (uint64_t x, uint64_t &c)
 Count 10 bit pairs in the word x.
static uint32_t b01Cnt (uint64_t x, uint64_t &c)
 Count 01 bit pairs in the word x.
static uint32_t b10CntNaive (uint64_t x, uint64_t &c)
static uint64_t b10Map (uint64_t x, uint64_t c=0)
 Map all 10 bit pairs to 01 or 1 if c=1 and the lsb=0. All other pairs are mapped to 00.
static uint64_t b01Map (uint64_t x, uint64_t c=1)
 Map all 01 bit pairs to 01 of 1 if c=1 and the lsb=0. All other pairs are mapped to 00.
static uint32_t i1BP (uint64_t x, uint32_t i)
 Calculate the position of the i-th rightmost 1 bit in the 64bit integer x.
static uint32_t i1BP2 (uint64_t x, uint32_t i)
static uint32_t j1BP (uint64_t x, uint32_t j)
 i1BP implementation proposed by Vigna.
static uint32_t k1BP (uint64_t x, uint32_t j)
 i1BP implementation using SSE4.2.
static uint32_t i1BPNaive (uint64_t x, uint32_t i)
 Naive implementation of i1BP.
static uint32_t l1BP (uint64_t x)
 Calculates the position of the leftmost 1-bit in the 64bit integer x if it exists.
static uint32_t l1BPNaive (uint64_t x)
 Naive implementation of l1BP.
static uint32_t r1BP (uint64_t x)
 Calculates the position of the rightmost 1-bit in the 64bit integer x if it exists.
static uint32_t r1BPNaive (uint64_t x)
 Naive implementation of r1BP.
static uint32_t i11BP (uint64_t x, uint32_t i, uint32_t c=0)
 Calcluates the position of the i-th rightmost 11-bit-pattern which terminates a fibonacci coded integer in x.
static uint32_t i11BPNaive (uint64_t x, uint32_t i)
 Naive implementation of i11BP.
static uint64_t all11BPs (uint64_t x, bool &c)
static uint32_t eI11BP (uint64_t x, uint32_t i)
 Calculates the position of the i-th rightmost 11-bit-pattern which terminates a Ternary coded integer in x.
static uint32_t l11BP (uint64_t x)
 Calculates the position of the leftmost 11-bit-pattern which terminates a fibonacci coded integer in x.
static void write_int (uint64_t *word, uint64_t x, const uint8_t offset=0, const uint8_t len=64)
 TODO: Documentation for this function.
static void write_int_and_move (uint64_t *&word, uint64_t x, uint8_t &offset, const uint8_t len)
 TODO: Documentation for this function.
static uint64_t read_int (const uint64_t *word, uint8_t offset=0, const uint8_t len=64)
 TODO: Documentation for this function.
static uint64_t read_int_and_move (const uint64_t *&word, uint8_t &offset, const uint8_t len=64)
 TODO: Documentation for this function.
static uint64_t readUnaryInt (const uint64_t *word, uint8_t offset=0)
 TODO: Documentation for this function.
static uint64_t readUnaryIntAndMove (const uint64_t *&word, uint8_t &offset)
 TODO: Documentation for this function.
static void move_right (const uint64_t *&word, uint8_t &offset, const uint8_t len)
 Move the bit pointer consisting of a uint64_t pointer and an offset len positions to the right.
static void move_left (const uint64_t *&word, uint8_t &offset, const uint8_t len)
 Move the bit pointer consisting of a uint64_t pointer and an offset len positions to the left.
static uint64_t next (const uint64_t *word, uint64_t idx)
 Get the first one bit in the intervall $[idx..\infty )$.
static uint64_t prev (const uint64_t *word, uint64_t idx)
 Get the one bit with the greatest position in the intervall $[0..idx]$.
static uint16_t max_excess (uint64_t x, uint16_t &b1Cnt)
static uint16_t max_excess2 (uint64_t x, uint16_t &b1Cnt)
static uint16_t max_excess3 (uint64_t x, uint16_t &b1Cnt)
static void max_byte_excesses (uint64_t w, uint64_t &max_byte_excesses, uint64_t &byte_prefix_sums_x_2)
static void max_byte_excesses2 (uint64_t w, uint64_t &max_byte_excesses, uint64_t &byte_prefix_sums_x_2)
static void min_max_byte_excesses (uint64_t max2, uint64_t &min_byte_excesses, uint64_t &max_byte_excesses, uint64_t &byte_prefix_sums_x_2)
static uint8_t first_excess_position (uint64_t w, uint8_t excess_val, uint64_t &byte_prefix_sums_x_2)
static uint8_t first_excess_position_naive (uint64_t w, uint8_t excess_val, uint64_t &byte_prefix_sums_x_2)
static uint8_t last_excess_position (uint64_t w, uint8_t excess_val, uint64_t &byte_prefix_sums_x_2)
static uint8_t last_excess_position_naive (uint64_t w, uint8_t excess_val, uint64_t &byte_prefix_sums_x_2)
static uint8_t find_open (uint64_t w, uint8_t close_parenthesis_index)
static uint8_t find_open_naive (uint64_t w, uint8_t close_parenthesis_index)
static uint8_t find_enclose (uint64_t w, uint8_t open_parenthesis_index)
static uint8_t find_enclose_naive (uint64_t w, uint8_t open_parenthesis_index)

Static Public Attributes

static const int64_t All1Mask = -1LL
 64bit mask with all bits set to 1.
static const uint64_t DeBruijn64 = 0x0218A392CD3D5DBFULL
 This constant represents a de Bruijn sequence B(k,n) for k=2 and n=6.
static const uint32_t DeBruijn64ToIndex [64]
 This table maps a 6-bit subsequence S[idx...idx+5] of constant DeBruijn64 to idx.
static const uint64_t Fib [92]
 Array containing fibonacci numbers less than $2^64$.
static const uint8_t B1CntBytes [256]
 Array containing the popcnts for all 2^8 possible byte values.
static const uint32_t L1BP [256]
 Array containing precomputed values for the leftmost 1-bit in a 8bit integer.
static const uint64_t Li1Mask [65]
 An array with entry i containing a 64bit integer with the last i bits set.
static const uint64_t Li0Mask [65]
 An array with entry i containing a 64bit integer with the last i bits not set.
static const uint8_t lookupr1BP [256]
static const uint8_t Select256 [256 *8]
 An array with precomputed select queries on a 8-bit integer.
static const uint64_t PsOverflow [65]
static const uint32_t powerOf3 [9]
static const uint8_t max_excess_8bit [256]
static const uint64_t _8_x_the_byte [65]
 Contains 64 bit constants. Constant i is equal to 8 bytes each set to i.
static const uint8_t cover0 [1]
static const uint8_t cover1 [2]
static const uint8_t cover2 [3]
static const uint8_t cover3 [4]
static const uint8_t cover4 [5]
static const uint8_t cover5 [7]
static const uint8_t cover6 [9]
static const uint8_t cover7 [13]
static const uint8_t cover8 [20]
static const uint8_t * covers [9]
static const uint32_t cover_sizes [9]
static const uint8_t first_pos_of_excess_val [256 *9]
static const uint8_t last_pos_of_excess_val [256 *17]
static const uint8_t very_near_find_open [256]
 Precomputed answers for find_open for blocks of 8 bit preceding the closing parenthesis.
static const uint8_t very_near_enclose [256]

Detailed Description

A helper class for bitwise tricks on 64 bit words.

bit_magic is a helper class for bitwise tricks and techniques. For the basic tricks and techiques we refer to Donald E. Knuth's "The Art of Computer Programming", Volume 4A, Chapter 7.1.3 and the informative website of Sean E. Anderson about the topic: http://www-graphics.stanford.edu/~seander/bithacks.html .

We have added new functions like: b11Cnt and i11BP.

All members of this class are static variables or methods. This class cannot be instantiated.

Author:
Simon Gog

Member Function Documentation

uint32_t sdsl::bit_magic::b01Cnt ( uint64_t  x,
uint64_t &  c 
) [inline, static]

Count 01 bit pairs in the word x.

Parameters:
x64bit integer to count the 01 bit pairs.
cCarry equals msb of the previous 64bit integer.
uint32_t sdsl::bit_magic::b10Cnt ( uint64_t  x,
uint64_t &  c 
) [inline, static]

Count 10 bit pairs in the word x.

Parameters:
x64bit integer to count the 10 bit pairs.
cCarry equals msb of the previous 64bit integer.
uint32_t sdsl::bit_magic::b11Cnt ( uint64_t  x,
uint64_t &  c 
) [inline, static]

Count the number of consecutive and distinct 11 in the 64bit integer x.

Parameters:
x64bit integer to count the terminating sequence 11 of a fibonacci code.
cCarry equals msb of the previous 64bit integer.
uint32_t sdsl::bit_magic::b11Cnt ( uint64_t  x) [inline, static]

Count the number of consecutive and distinct 11 in the 64bit integer x.

Parameters:
x64bit integer to count the terminating sequence 11 of a fibonacci code.
uint64_t sdsl::bit_magic::b1Cnt ( uint64_t  x) [inline, static]

Counts the number of 1-bits in the 64bit integer x.

This function is also known as sideway addition in literature. E.g. see Donald E. Knuth, "The Art of Computer Programming", Volume 4A.

Parameters:
x64bit integer to count the bits.
Returns:
The number of 1-bits in x.
uint32_t sdsl::bit_magic::b1Cnt32 ( uint32_t  x) [inline, static]

Counts the number of 1-bits in the 32bit integer x.

This function is a variant of the method b1Cnt. If 32bit multiplication is fast, this method beats the b1Cnt. for 32bit integers.

Parameters:
x64bit integer to count the bits.
Returns:
The number of 1-bits in x.
uint8_t sdsl::bit_magic::first_excess_position ( uint64_t  w,
uint8_t  excess_val,
uint64_t &  byte_prefix_sums_x_2 
) [inline, static]

Calculates the minimal position where a specific excess_val is reached.

Parameters:
wThe 64 bit word representing a parentheses sequence.
excess_valThe excess value which should be reached. $0<excess\_val \leq 64 $.
byte_prefix_sums_x_2Contains for each byte i of w the number of ones the the byte + the number of ones in the previous bytes in w.
Returns:
The minimal index where a the excess value equals excess_val or 64 if there is no such index.
See also:
first_excess_position_naive
uint8_t sdsl::bit_magic::first_excess_position_naive ( uint64_t  w,
uint8_t  excess_val,
uint64_t &  byte_prefix_sums_x_2 
) [inline, static]

Naive implementation of first_excess_position

See also:
first_excess_position
uint32_t sdsl::bit_magic::i11BP ( uint64_t  x,
uint32_t  i,
uint32_t  c = 0 
) [inline, static]

Calcluates the position of the i-th rightmost 11-bit-pattern which terminates a fibonacci coded integer in x.

Parameters:
x64 bit integer.
iIndex of 11-bit-pattern. $i \in [1..b11Cnt(x)]$
cCarry bit from word before
Returns:
The position (in 1..63) of the i-th 11-bit-pattern which terminates a fibonacci coded integer in x if x contains at least i 11-bit-patterns and a undefined value otherwise.
See also:
b11Cnt, l11BP, i1BP
uint32_t sdsl::bit_magic::i1BP ( uint64_t  x,
uint32_t  i 
) [inline, static]

Calculate the position of the i-th rightmost 1 bit in the 64bit integer x.

Parameters:
x64bit integer.
iArgument i must be in the range $[1..b1Cnt(x)]$.
Precondition:
Argument i must be in the range $[1..b1Cnt(x)]$.
See also:
l1BP, r1BP
uint32_t sdsl::bit_magic::j1BP ( uint64_t  x,
uint32_t  j 
) [inline, static]

i1BP implementation proposed by Vigna.

See also:
i1BP
uint32_t sdsl::bit_magic::k1BP ( uint64_t  x,
uint32_t  j 
) [inline, static]

i1BP implementation using SSE4.2.

See also:
i1BP
uint32_t sdsl::bit_magic::l11BP ( uint64_t  x) [inline, static]

Calculates the position of the leftmost 11-bit-pattern which terminates a fibonacci coded integer in x.

Parameters:
x64 bit integer.
Returns:
The position (in 1..63) of the leftmost 1 of the leftmost 11-bit-pattern which terminates a fibonacci coded integer in x if x contains a 11-bit-pattern and 0 otherwise.
See also:
b11Cnt, i11BP
uint32_t sdsl::bit_magic::l1BP ( uint64_t  x) [inline, static]

Calculates the position of the leftmost 1-bit in the 64bit integer x if it exists.

Parameters:
x64 bit integer.
Returns:
The position (in 0..63) of the leftmost 1-bit in the 64bit integer x if x>0 and 0 if x equals 0.
See also:
i1BP, r1BP
void sdsl::bit_magic::max_byte_excesses ( uint64_t  w,
uint64_t &  max_byte_excesses,
uint64_t &  byte_prefix_sums_x_2 
) [inline, static]

Calculates the maximal excess values for the eight byte prefixes of a 64 bit word.

Parameters:
wThe 64 bit word representing a parentheses sequence.
max_byte_excessesThe i th byte contains the maximal excess value that ..... TODO: description
byte_prefix_sums_x_264bit word that contains the doubled prefix sums of the 8 bytes.
void sdsl::bit_magic::move_left ( const uint64_t *&  word,
uint8_t &  offset,
const uint8_t  len 
) [inline, static]

Move the bit pointer consisting of a uint64_t pointer and an offset len positions to the left.

Parameters:
word64-bit word part of the bit pointer
offsetOffset part of the bit pointer
lenPosition to move to the left. $ len \in [0..64] $
See also:
move_right
void sdsl::bit_magic::move_right ( const uint64_t *&  word,
uint8_t &  offset,
const uint8_t  len 
) [inline, static]

Move the bit pointer consisting of a uint64_t pointer and an offset len positions to the right.

Parameters:
word64-bit word part of the bit pointer
offsetOffset part of the bit pointer
lenPosition to move to the right. $ len \in [0..64] $
See also:
move_left
uint32_t sdsl::bit_magic::r1BP ( uint64_t  x) [inline, static]

Calculates the position of the rightmost 1-bit in the 64bit integer x if it exists.

This method is e.g. used in the getUnaryBit method.

Parameters:
x64 bit integer.
Returns:
The position (in 0..63) of the rightmost 1-bit in the 64bit integer x if x>0 and 0 if x equals 0.
See also:
i1BP, l1BP

Member Data Documentation

const uint64_t sdsl::bit_magic::DeBruijn64 = 0x0218A392CD3D5DBFULL [static]

This constant represents a de Bruijn sequence B(k,n) for k=2 and n=6.

Details for de Bruijn sequences see http://en.wikipedia.org/wiki/De_bruijn_sequence DeBruijn64 is used in combination with the array DeBruijn64ToIndex.

const uint32_t sdsl::bit_magic::DeBruijn64ToIndex[64] [static]

This table maps a 6-bit subsequence S[idx...idx+5] of constant DeBruijn64 to idx.

See also:
DeBruijn64
const uint32_t sdsl::bit_magic::L1BP[256] [static]

Array containing precomputed values for the leftmost 1-bit in a 8bit integer.

See also:
l1BP
const uint8_t sdsl::bit_magic::Select256[256 *8] [static]

An array with precomputed select queries on a 8-bit integer.

Entry at idx = 256*j + i equals the position of the (j+1)-th leftmost 1 bit in the integer i. Positions lie in the range $[0..7]$.

const uint8_t sdsl::bit_magic::very_near_find_open[256] [static]

Precomputed answers for find_open for blocks of 8 bit preceding the closing parenthesis.

If there is no matching opening parenthesis within these 8 bits 0 is returned otherwise the distance i $i\in \{1,3,5,7\}$ from the index of the closing parenthesis to the matching opening parenthesis is returned.

The documentation for this class was generated from the following file:
Generated on Mon Aug 13 2012 15:23:28 for SDSL: Succinct Data Structure Library by   doxygen 1.8.0