encoding.h
Go to the documentation of this file.
#ifndef BMENCODING_H__INCLUDED__
#define BMENCODING_H__INCLUDED__
/*
Copyright(c) 2002-2017 Anatoliy Kuznetsov(anatoliy_kuznetsov at yahoo.com)
Licensed under the Apache License, Version 2.0 (the "License");
you may not use this file except in compliance with the License.
You may obtain a copy of the License at
http://www.apache.org/licenses/LICENSE-2.0
Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and
limitations under the License.
For more information please visit: http://bitmagic.io
*/
/*! \file encoding.h
\brief Encoding utilities for serialization (internal)
*/
#include <memory.h>
#include "bmutil.h"
#ifdef _MSC_VER
#pragma warning (push)
#pragma warning (disable : 4702)
#endif
namespace bm
{
// ----------------------------------------------------------------
/*!
\brief Memory encoding.
Class for encoding data into memory.
Class handles aligment issues with the integer data types.
\ingroup gammacode
*/
class encoder
{
public:
typedef unsigned char* position_type;
public:
encoder(unsigned char* buf, size_t size) BMNOEXCEPT;
void put_8(unsigned char c) BMNOEXCEPT;
void put_16(bm::short_t s) BMNOEXCEPT;
void put_16(const bm::short_t* s, unsigned count) BMNOEXCEPT;
void put_24(bm::word_t w) BMNOEXCEPT;
void put_32(bm::word_t w) BMNOEXCEPT;
void put_32(const bm::word_t* w, unsigned count) BMNOEXCEPT;
void put_48(bm::id64_t w) BMNOEXCEPT;
void put_64(bm::id64_t w) BMNOEXCEPT;
void put_h64(bm::id64_t w) BMNOEXCEPT;
void put_8_16_32(unsigned w,
unsigned char c8, unsigned char c16, unsigned char c32) BMNOEXCEPT;
void put_prefixed_array_32(unsigned char c,
const bm::word_t* w, unsigned count) BMNOEXCEPT;
void put_prefixed_array_16(unsigned char c,
const bm::short_t* s, unsigned count,
bool encode_count) BMNOEXCEPT;
void memcpy(const unsigned char* src, size_t count) BMNOEXCEPT;
size_t size() const BMNOEXCEPT;
unsigned char* get_pos() const BMNOEXCEPT;
void set_pos(unsigned char* buf_pos) BMNOEXCEPT;
private:
unsigned char* buf_;
unsigned char* start_;
size_t size_;
};
// ----------------------------------------------------------------
/**
Base class for all decoding functionality
\ingroup gammacode
*/
class decoder_base
{
public:
decoder_base(const unsigned char* buf) BMNOEXCEPT { buf_ = start_ = buf; }
/// Reads character from the decoding buffer.
unsigned char get_8() BMNOEXCEPT { return *buf_++; }
/// Returns size of the current decoding stream.
size_t size() const BMNOEXCEPT { return size_t(buf_ - start_); }
/// change current position
void seek(int delta) BMNOEXCEPT { buf_ += delta; }
/// read bytes from the decode buffer
void memcpy(unsigned char* dst, size_t count) BMNOEXCEPT;
/// Return current buffer pointer
const unsigned char* get_pos() const BMNOEXCEPT { return buf_; }
/// Set current buffer pointer
void set_pos(const unsigned char* pos) BMNOEXCEPT { buf_ = pos; }
/// Read h-64-bit
bm::id64_t get_h64() BMNOEXCEPT;
protected:
const unsigned char* buf_;
const unsigned char* start_;
};
// ----------------------------------------------------------------
/**
Class for decoding data from memory buffer.
Properly handles aligment issues with integer data types.
\ingroup gammacode
*/
class decoder : public decoder_base
{
public:
decoder(const unsigned char* buf) BMNOEXCEPT;
bm::short_t get_16() BMNOEXCEPT;
bm::word_t get_24() BMNOEXCEPT;
bm::word_t get_32() BMNOEXCEPT;
bm::id64_t get_48() BMNOEXCEPT;
bm::id64_t get_64() BMNOEXCEPT;
void get_32(bm::word_t* w, unsigned count) BMNOEXCEPT;
bool get_32_OR(bm::word_t* w, unsigned count) BMNOEXCEPT;
void get_32_AND(bm::word_t* w, unsigned count) BMNOEXCEPT;
void get_16(bm::short_t* s, unsigned count) BMNOEXCEPT;
};
// ----------------------------------------------------------------
/**
Class for decoding data from memory buffer.
Properly handles aligment issues with integer data types.
Converts data to big endian architecture
(presumed it was encoded as little endian)
\ingroup gammacode
*/
typedef decoder decoder_big_endian;
// ----------------------------------------------------------------
/**
Class for decoding data from memory buffer.
Properly handles aligment issues with integer data types.
Converts data to little endian architecture
(presumed it was encoded as big endian)
\ingroup gammacode
*/
class decoder_little_endian : public decoder_base
{
public:
decoder_little_endian(const unsigned char* buf);
bm::short_t get_16();
bm::word_t get_24();
bm::word_t get_32();
bm::id64_t get_48();
bm::id64_t get_64();
void get_32(bm::word_t* w, unsigned count);
bool get_32_OR(bm::word_t* w, unsigned count);
void get_32_AND(bm::word_t* w, unsigned count);
void get_16(bm::short_t* s, unsigned count);
};
/**
Byte based writer for un-aligned bit streaming
@ingroup gammacode
@sa encoder
*/
template<class TEncoder>
class bit_out
{
public:
bit_out(TEncoder& dest)
: dest_(dest), used_bits_(0), accum_(0)
{}
~bit_out() { flush(); }
/// issue single bit into encode bit-stream
void put_bit(unsigned value) BMNOEXCEPT;
/// issue count bits out of value
void put_bits(unsigned value, unsigned count) BMNOEXCEPT;
/// issue 0 into output stream
void put_zero_bit() BMNOEXCEPT;
/// issue specified number of 0s
void put_zero_bits(unsigned count) BMNOEXCEPT;
/// Elias Gamma encode the specified value
void gamma(unsigned value) BMNOEXCEPT;
/// Binary Interpolative array decode
void bic_encode_u16(const bm::gap_word_t* arr, unsigned sz,
bm::gap_word_t lo, bm::gap_word_t hi) BMNOEXCEPT
{
bic_encode_u16_cm(arr, sz, lo, hi);
}
/// Binary Interpolative encoding (array of 16-bit ints)
void bic_encode_u16_rg(const bm::gap_word_t* arr, unsigned sz,
bm::gap_word_t lo,
bm::gap_word_t hi) BMNOEXCEPT;
/// Binary Interpolative encoding (array of 16-bit ints)
/// cm - "center-minimal"
void bic_encode_u16_cm(const bm::gap_word_t* arr, unsigned sz,
bm::gap_word_t lo,
bm::gap_word_t hi) BMNOEXCEPT;
/// Binary Interpolative encoding (array of 32-bit ints)
/// cm - "center-minimal"
void bic_encode_u32_cm(const bm::word_t* arr, unsigned sz,
bm::word_t lo, bm::word_t hi) BMNOEXCEPT;
/// Flush the incomplete 32-bit accumulator word
void flush() BMNOEXCEPT { if (used_bits_) flush_accum(); }
private:
void flush_accum() BMNOEXCEPT
{
dest_.put_32(accum_);
used_bits_ = accum_ = 0;
}
private:
bit_out(const bit_out&);
bit_out& operator=(const bit_out&);
private:
TEncoder& dest_; ///< Bit stream target
unsigned used_bits_; ///< Bits used in the accumulator
unsigned accum_; ///< write bit accumulator
};
/**
Byte based reader for un-aligned bit streaming
@ingroup gammacode
@sa encoder
*/
template<class TDecoder>
class bit_in
{
public:
bit_in(TDecoder& decoder) BMNOEXCEPT
: src_(decoder),
used_bits_(unsigned(sizeof(accum_) * 8)),
accum_(0)
{}
/// decode unsigned value using Elias Gamma coding
unsigned gamma() BMNOEXCEPT;
/// read number of bits out of the stream
unsigned get_bits(unsigned count) BMNOEXCEPT;
/// read 1 bit
unsigned get_bit() BMNOEXCEPT;
/// Binary Interpolative array decode
void bic_decode_u16(bm::gap_word_t* arr, unsigned sz,
bm::gap_word_t lo, bm::gap_word_t hi) BMNOEXCEPT
{
if (sz)
bic_decode_u16_cm(arr, sz, lo, hi);
}
void bic_decode_u16_bitset(bm::word_t* block, unsigned sz,
bm::gap_word_t lo, bm::gap_word_t hi) BMNOEXCEPT
{
if (sz)
bic_decode_u16_cm_bitset(block, sz, lo, hi);
}
void bic_decode_u16_dry(unsigned sz,
bm::gap_word_t lo, bm::gap_word_t hi) BMNOEXCEPT
{
if (sz)
bic_decode_u16_cm_dry(sz, lo, hi);
}
/// Binary Interpolative array decode
void bic_decode_u16_rg(bm::gap_word_t* arr, unsigned sz,
bm::gap_word_t lo, bm::gap_word_t hi) BMNOEXCEPT;
/// Binary Interpolative array decode
void bic_decode_u16_cm(bm::gap_word_t* arr, unsigned sz,
bm::gap_word_t lo, bm::gap_word_t hi) BMNOEXCEPT;
/// Binary Interpolative array decode (32-bit)
void bic_decode_u32_cm(bm::word_t* arr, unsigned sz,
bm::word_t lo, bm::word_t hi) BMNOEXCEPT;
/// Binary Interpolative array decode into bitset (32-bit based)
void bic_decode_u16_rg_bitset(bm::word_t* block, unsigned sz,
bm::gap_word_t lo, bm::gap_word_t hi) BMNOEXCEPT;
/// Binary Interpolative array decode into /dev/null
void bic_decode_u16_rg_dry(unsigned sz,
bm::gap_word_t lo, bm::gap_word_t hi) BMNOEXCEPT;
/// Binary Interpolative array decode into bitset (32-bit based)
void bic_decode_u16_cm_bitset(bm::word_t* block, unsigned sz,
bm::gap_word_t lo,
bm::gap_word_t hi) BMNOEXCEPT;
/// Binary Interpolative array decode into /dev/null
void bic_decode_u16_cm_dry(unsigned sz,
bm::gap_word_t lo, bm::gap_word_t hi) BMNOEXCEPT;
private:
bit_in(const bit_in&);
bit_in& operator=(const bit_in&);
private:
TDecoder& src_; ///< Source of bytes
unsigned used_bits_; ///< Bits used in the accumulator
unsigned accum_; ///< read bit accumulator
};
/**
Functor for Elias Gamma encoding
@ingroup gammacode
*/
template<typename T, typename TBitIO>
class gamma_encoder
{
public:
gamma_encoder(TBitIO& bout) : bout_(bout)
{}
/** Encode word */
void operator()(T value) { bout_.gamma(value); }
private:
gamma_encoder(const gamma_encoder&);
gamma_encoder& operator=(const gamma_encoder&);
private:
TBitIO& bout_;
};
/**
Elias Gamma decoder
@ingroup gammacode
*/
template<typename T, typename TBitIO>
class gamma_decoder
{
public:
gamma_decoder(TBitIO& bin) : bin_(bin) {}
/**
Start encoding sequence
*/
void start() {}
/**
Stop decoding sequence
*/
void stop() {}
/**
Decode word
*/
T operator()(void) { return (T)bin_.gamma(); }
private:
gamma_decoder(const gamma_decoder&);
gamma_decoder& operator=(const gamma_decoder&);
private:
TBitIO& bin_;
};
// ----------------------------------------------------------------
// Implementation details.
// ----------------------------------------------------------------
/*!
\fn encoder::encoder(unsigned char* buf, unsigned size)
\brief Construction.
\param buf - memory buffer pointer.
\param size - size of the buffer
*/
inline encoder::encoder(unsigned char* buf, size_t a_size) BMNOEXCEPT
: buf_(buf), start_(buf)
{
size_ = a_size;
}
/*!
\brief Encode 8-bit prefix + an array
*/
inline void encoder::put_prefixed_array_32(unsigned char c,
const bm::word_t* w,
unsigned count) BMNOEXCEPT
{
put_8(c);
put_32(w, count);
}
/*!
\brief Encode 8-bit prefix + an array
*/
inline void encoder::put_prefixed_array_16(unsigned char c,
const bm::short_t* s,
unsigned count,
bool encode_count) BMNOEXCEPT
{
put_8(c);
if (encode_count)
put_16((bm::short_t) count);
put_16(s, count);
}
/*!
\fn void encoder::put_8(unsigned char c)
\brief Puts one character into the encoding buffer.
\param c - character to encode
*/
BMFORCEINLINE void encoder::put_8(unsigned char c) BMNOEXCEPT
{
*buf_++ = c;
}
/*!
\fn encoder::put_16(bm::short_t s)
\brief Puts short word (16 bits) into the encoding buffer.
\param s - short word to encode
*/
BMFORCEINLINE void encoder::put_16(bm::short_t s) BMNOEXCEPT
{
#if (BM_UNALIGNED_ACCESS_OK == 1)
::memcpy(buf_, &s, sizeof(bm::short_t)); // optimizer takes care of it
buf_ += sizeof(bm::short_t);
#else
*buf_++ = (unsigned char) s;
s >>= 8;
*buf_++ = (unsigned char) s;
#endif
}
/*!
\brief Method puts array of short words (16 bits) into the encoding buffer.
*/
inline void encoder::put_16(const bm::short_t* s, unsigned count) BMNOEXCEPT
{
BM_ASSERT(count);
#if (BM_UNALIGNED_ACCESS_OK == 1)
::memcpy(buf_, s, sizeof(bm::short_t)*count);
buf_ += sizeof(bm::short_t) * count;
#else
unsigned char* buf = buf_;
const bm::short_t* s_end = s + count;
do
{
bm::short_t w16 = *s++;
unsigned char a = (unsigned char) w16;
unsigned char b = (unsigned char) (w16 >> 8);
*buf++ = a;
*buf++ = b;
} while (s < s_end);
buf_ = (unsigned char*)buf;
#endif
}
/*!
\brief but gat plus value based on its VBR evaluation
*/
inline
void encoder::put_8_16_32(unsigned w,
unsigned char c8,
unsigned char c16,
unsigned char c32) BMNOEXCEPT
{
if (w < 256)
{
put_8(c8);
put_8((unsigned char)w);
}
else
{
if (w < 65536)
{
put_8(c16);
put_16((unsigned short) w);
}
else
{
put_8(c32);
put_32(w);
}
}
}
/*!
\brief copy bytes into target buffer or just rewind if src is NULL
*/
inline
void encoder::memcpy(const unsigned char* src, size_t count) BMNOEXCEPT
{
BM_ASSERT((buf_ + count) < (start_ + size_));
if (src)
::memcpy(buf_, src, count);
buf_ += count;
}
/*!
\fn unsigned encoder::size() const
\brief Returns size of the current encoding stream.
*/
inline size_t encoder::size() const BMNOEXCEPT
{
return size_t(buf_ - start_);
}
/**
\brief Get current memory stream position
*/
inline encoder::position_type encoder::get_pos() const BMNOEXCEPT
{
return buf_;
}
/**
\brief Set current memory stream position
*/
inline void encoder::set_pos(encoder::position_type buf_pos) BMNOEXCEPT
{
buf_ = buf_pos;
}
/*!
\fn void encoder::put_24(bm::word_t w)
\brief Puts 24 bits word into encoding buffer.
\param w - word to encode.
*/
inline void encoder::put_24(bm::word_t w) BMNOEXCEPT
{
BM_ASSERT((w & ~(0xFFFFFFU)) == 0);
buf_[0] = (unsigned char)w;
buf_[1] = (unsigned char)(w >> 8);
buf_[2] = (unsigned char)(w >> 16);
buf_ += 3;
}
/*!
\fn void encoder::put_32(bm::word_t w)
\brief Puts 32 bits word into encoding buffer.
\param w - word to encode.
*/
inline void encoder::put_32(bm::word_t w) BMNOEXCEPT
{
#if (BM_UNALIGNED_ACCESS_OK == 1)
::memcpy(buf_, &w, sizeof(bm::word_t));
buf_ += sizeof(bm::word_t);
#else
*buf_++ = (unsigned char) w;
*buf_++ = (unsigned char) (w >> 8);
*buf_++ = (unsigned char) (w >> 16);
*buf_++ = (unsigned char) (w >> 24);
#endif
}
/*!
\fn void encoder::put_48(bm::id64_t w)
\brief Puts 48 bits word into encoding buffer.
\param w - word to encode.
*/
inline void encoder::put_48(bm::id64_t w) BMNOEXCEPT
{
BM_ASSERT((w & ~(0xFFFFFFFFFFFFUL)) == 0);
*buf_++ = (unsigned char)w;
*buf_++ = (unsigned char)(w >> 8);
*buf_++ = (unsigned char)(w >> 16);
*buf_++ = (unsigned char)(w >> 24);
*buf_++ = (unsigned char)(w >> 32);
*buf_++ = (unsigned char)(w >> 40);
}
/*!
\fn void encoder::put_64(bm::id64_t w)
\brief Puts 64 bits word into encoding buffer.
\param w - word to encode.
*/
inline void encoder::put_64(bm::id64_t w) BMNOEXCEPT
{
#if (BM_UNALIGNED_ACCESS_OK == 1)
::memcpy(buf_, &w, sizeof(bm::id64_t));
buf_ += sizeof(bm::id64_t);
#else
*buf_++ = (unsigned char) w;
*buf_++ = (unsigned char) (w >> 8);
*buf_++ = (unsigned char) (w >> 16);
*buf_++ = (unsigned char) (w >> 24);
*buf_++ = (unsigned char) (w >> 32);
*buf_++ = (unsigned char) (w >> 40);
*buf_++ = (unsigned char) (w >> 48);
*buf_++ = (unsigned char) (w >> 56);
#endif
}
/*!
\fn void encoder::put_h64(bm::id64_t w)
\brief Puts 64 bits word into encoding buffer with h-compression
\param w - word to encode.
*/
inline void encoder::put_h64(bm::id64_t w) BMNOEXCEPT
{
unsigned h_mask = bm::compute_h64_mask(w);
put_8((unsigned char) h_mask);
for (unsigned i = 0; w && (i < 8); ++i, w >>= 8)
{
if ((unsigned char) w)
put_8((unsigned char) w);
} // for i
}
/*!
\brief Encodes array of 32-bit words
*/
inline void encoder::put_32(const bm::word_t* w, unsigned count) BMNOEXCEPT
{
#if (BM_UNALIGNED_ACCESS_OK == 1)
// use memcpy() because compilers now understand it as an idiom and inline
::memcpy(buf_, w, sizeof(bm::word_t) * count);
buf_ += sizeof(bm::word_t) * count;
#else
unsigned char* buf = buf_;
const bm::word_t* w_end = w + count;
do
{
bm::word_t w32 = *w++;
unsigned char a = (unsigned char) w32;
unsigned char b = (unsigned char) (w32 >> 8);
unsigned char c = (unsigned char) (w32 >> 16);
unsigned char d = (unsigned char) (w32 >> 24);
*buf++ = a;
*buf++ = b;
*buf++ = c;
*buf++ = d;
} while (w < w_end);
buf_ = (unsigned char*)buf;
#endif
}
// ---------------------------------------------------------------------
/*!
Load bytes from the decode buffer
*/
inline
void decoder_base::memcpy(unsigned char* dst, size_t count) BMNOEXCEPT
{
if (dst)
::memcpy(dst, buf_, count);
buf_ += count;
}
/*!
\fn bm::id64_t decoder_base::get_h64()
\brief Reads 64-bit word from the decoding buffer.
*/
inline
bm::id64_t decoder_base::get_h64() BMNOEXCEPT
{
bm::id64_t w = 0;
unsigned h_mask = (unsigned char) *buf_++;
for (unsigned i = 0; h_mask && (i < 8); ++i)
{
if (h_mask & (1u<<i))
{
h_mask &= ~(1u<<i);
unsigned char a = (unsigned char) *buf_++;
w |= (bm::id64_t(a) << (i*8));
}
} // for i
return w;
}
/*!
\fn decoder::decoder(const unsigned char* buf)
\brief Construction
\param buf - pointer to the decoding memory.
*/
inline decoder::decoder(const unsigned char* buf) BMNOEXCEPT
: decoder_base(buf)
{
}
/*!
\fn bm::short_t decoder::get_16()
\brief Reads 16-bit word from the decoding buffer.
*/
BMFORCEINLINE bm::short_t decoder::get_16() BMNOEXCEPT
{
#if (BM_UNALIGNED_ACCESS_OK == 1)
bm::short_t a;
::memcpy(&a, buf_, sizeof(bm::short_t));
#else
bm::short_t a = (bm::short_t)(buf_[0] + ((bm::short_t)buf_[1] << 8));
#endif
buf_ += sizeof(a);
return a;
}
/*!
\fn bm::word_t decoder::get_24()
\brief Reads 32-bit word from the decoding buffer.
*/
inline bm::word_t decoder::get_24() BMNOEXCEPT
{
bm::word_t a = buf_[0] + ((unsigned)buf_[1] << 8) +
((unsigned)buf_[2] << 16);
buf_ += 3;
return a;
}
/*!
\fn bm::word_t decoder::get_32()
\brief Reads 32-bit word from the decoding buffer.
*/
BMFORCEINLINE bm::word_t decoder::get_32() BMNOEXCEPT
{
#if (BM_UNALIGNED_ACCESS_OK == 1)
bm::word_t a;
::memcpy(&a, buf_, sizeof(bm::word_t));
#else
bm::word_t a = buf_[0]+ ((unsigned)buf_[1] << 8) +
((unsigned)buf_[2] << 16) + ((unsigned)buf_[3] << 24);
#endif
buf_+=sizeof(a);
return a;
}
/*!
\fn bm::word_t decoder::get_48()
\brief Reads 64-bit word from the decoding buffer.
*/
inline
bm::id64_t decoder::get_48() BMNOEXCEPT
{
bm::id64_t a = buf_[0] +
((bm::id64_t)buf_[1] << 8) +
((bm::id64_t)buf_[2] << 16) +
((bm::id64_t)buf_[3] << 24) +
((bm::id64_t)buf_[4] << 32) +
((bm::id64_t)buf_[5] << 40);
buf_ += 6;
return a;
}
/*!
\fn bm::id64_t decoder::get_64()
\brief Reads 64-bit word from the decoding buffer.
*/
inline
bm::id64_t decoder::get_64() BMNOEXCEPT
{
#if (BM_UNALIGNED_ACCESS_OK == 1)
bm::id64_t a;
::memcpy(&a, buf_, sizeof(bm::id64_t));
#else
bm::id64_t a = buf_[0]+
((bm::id64_t)buf_[1] << 8) +
((bm::id64_t)buf_[2] << 16) +
((bm::id64_t)buf_[3] << 24) +
((bm::id64_t)buf_[4] << 32) +
((bm::id64_t)buf_[5] << 40) +
((bm::id64_t)buf_[6] << 48) +
((bm::id64_t)buf_[7] << 56);
#endif
buf_ += sizeof(a);
return a;
}
/*!
\fn void decoder::get_32(bm::word_t* w, unsigned count)
\brief Reads block of 32-bit words from the decoding buffer.
\param w - pointer on memory block to read into.
\param count - size of memory block in words.
*/
inline void decoder::get_32(bm::word_t* w, unsigned count) BMNOEXCEPT
{
if (!w)
{
seek(int(count * sizeof(bm::word_t)));
return;
}
#if (BM_UNALIGNED_ACCESS_OK == 1)
::memcpy(w, buf_, count * sizeof(bm::word_t));
seek(int(count * sizeof(bm::word_t)));
return;
#else
const unsigned char* buf = buf_;
const bm::word_t* w_end = w + count;
do
{
bm::word_t a = buf[0]+ ((unsigned)buf[1] << 8) +
((unsigned)buf[2] << 16) + ((unsigned)buf[3] << 24);
*w++ = a;
buf += sizeof(a);
} while (w < w_end);
buf_ = (unsigned char*)buf;
#endif
}
/*!
\brief Reads block of 32-bit words from the decoding buffer and ORs
to the destination
\param w - pointer on memory block to read into
\param count - should match bm::set_block_size
*/
inline
bool decoder::get_32_OR(bm::word_t* w, unsigned count) BMNOEXCEPT
{
if (!w)
{
seek(int(count * sizeof(bm::word_t)));
return false;
}
#if defined(BMAVX2OPT)
__m256i* buf_start = (__m256i*)buf_;
seek(int(count * sizeof(bm::word_t)));
__m256i* buf_end = (__m256i*)buf_;
return bm::avx2_or_arr_unal((__m256i*)w, buf_start, buf_end);
#elif defined(BMSSE42OPT) || defined(BMSSE2OPT)
__m128i* buf_start = (__m128i*)buf_;
seek(int(count * sizeof(bm::word_t)));
__m128i* buf_end = (__m128i*)buf_;
return bm::sse2_or_arr_unal((__m128i*)w, buf_start, buf_end);
#else
bm::word_t acc = 0;
const bm::word_t not_acc = acc = ~acc;
for (unsigned i = 0; i < count; i+=4)
{
acc &= (w[i+0] |= get_32());
acc &= (w[i+1] |= get_32());
acc &= (w[i+2] |= get_32());
acc &= (w[i+3] |= get_32());
}
return acc == not_acc;
#endif
}
/*!
\brief Reads block of 32-bit words from the decoding buffer and ANDs
to the destination
\param w - pointer on memory block to read into
\param count - should match bm::set_block_size
*/
inline
void decoder::get_32_AND(bm::word_t* w, unsigned count) BMNOEXCEPT
{
if (!w)
{
seek(int(count * sizeof(bm::word_t)));
return;
}
#if defined(BMAVX2OPT)
__m256i* buf_start = (__m256i*)buf_;
seek(int(count * sizeof(bm::word_t)));
__m256i* buf_end = (__m256i*)buf_;
bm::avx2_and_arr_unal((__m256i*)w, buf_start, buf_end);
#elif defined(BMSSE42OPT) || defined(BMSSE2OPT)
__m128i* buf_start = (__m128i*)buf_;
seek(int(count * sizeof(bm::word_t)));
__m128i* buf_end = (__m128i*)buf_;
bm::sse2_and_arr_unal((__m128i*)w, buf_start, buf_end);
#else
for (unsigned i = 0; i < count; i+=4)
{
w[i+0] &= get_32();
w[i+1] &= get_32();
w[i+2] &= get_32();
w[i+3] &= get_32();
}
#endif
}
/*!
\fn void decoder::get_16(bm::short_t* s, unsigned count)
\brief Reads block of 32-bit words from the decoding buffer.
\param s - pointer on memory block to read into.
\param count - size of memory block in words.
*/
inline void decoder::get_16(bm::short_t* s, unsigned count) BMNOEXCEPT
{
BM_ASSERT(count);
if (!s)
{
seek(int(count * sizeof(bm::short_t)));
return;
}
#if (BM_UNALIGNED_ACCESS_OK == 1)
::memcpy(s, buf_, sizeof(bm::short_t) * count);
buf_ += sizeof(bm::short_t) * count;
#else
const unsigned char* buf = buf_;
const bm::short_t* s_end = s + count;
do
{
bm::short_t a = (bm::short_t)(buf[0] + ((bm::short_t)buf[1] << 8));
*s++ = a;
buf += sizeof(a);
} while (s < s_end);
buf_ = (unsigned char*)buf;
#endif
}
// ---------------------------------------------------------------------
inline decoder_little_endian::decoder_little_endian(const unsigned char* buf)
: decoder_base(buf)
{
}
inline
bm::short_t decoder_little_endian::get_16()
{
bm::short_t v1 = bm::short_t(buf_[0]);
bm::short_t v2 = bm::short_t(buf_[1]);
bm::short_t a = bm::short_t((v1 << 8) + v2);
buf_ += sizeof(a);
return a;
}
inline bm::word_t decoder_little_endian::get_24()
{
// TODO: validate if this is a correct for cross endian opts
bm::word_t a = buf_[0] + ((unsigned)buf_[1] << 8) +
((unsigned)buf_[2] << 16);
buf_ += 3;
return a;
}
inline
bm::word_t decoder_little_endian::get_32()
{
bm::word_t a = ((unsigned)buf_[0] << 24)+ ((unsigned)buf_[1] << 16) +
((unsigned)buf_[2] << 8) + ((unsigned)buf_[3]);
buf_+=sizeof(a);
return a;
}
inline
bm::id64_t decoder_little_endian::get_48()
{
bm::id64_t a = buf_[0] +
((bm::id64_t)buf_[1] << 8) +
((bm::id64_t)buf_[2] << 16) +
((bm::id64_t)buf_[3] << 24) +
((bm::id64_t)buf_[4] << 32) +
((bm::id64_t)buf_[5] << 40);
buf_ += 6;
return a;
}
inline
bm::id64_t decoder_little_endian::get_64()
{
bm::id64_t a = buf_[0]+
((bm::id64_t)buf_[1] << 56) +
((bm::id64_t)buf_[2] << 48) +
((bm::id64_t)buf_[3] << 40) +
((bm::id64_t)buf_[4] << 32) +
((bm::id64_t)buf_[5] << 24) +
((bm::id64_t)buf_[6] << 16) +
((bm::id64_t)buf_[7] << 8);
buf_+=sizeof(a);
return a;
}
inline
void decoder_little_endian::get_32(bm::word_t* w, unsigned count)
{
if (!w)
{
seek(int(count * sizeof(bm::word_t)));
return;
}
const unsigned char* buf = buf_;
const bm::word_t* w_end = w + count;
do
{
bm::word_t a = ((unsigned)buf[0] << 24)+ ((unsigned)buf[1] << 16) +
((unsigned)buf[2] << 8) + ((unsigned)buf[3]);
*w++ = a;
buf += sizeof(a);
} while (w < w_end);
buf_ = (unsigned char*)buf;
}
inline
bool decoder_little_endian::get_32_OR(bm::word_t* w, unsigned count)
{
if (!w)
{
seek(int(count * sizeof(bm::word_t)));
return false;
}
bm::word_t acc = 0;
const bm::word_t not_acc = acc = ~acc;
for (unsigned i = 0; i < count; i+=4)
{
acc &= (w[i+0] |= get_32());
acc &= (w[i+1] |= get_32());
acc &= (w[i+2] |= get_32());
acc &= (w[i+3] |= get_32());
}
return acc == not_acc;
}
inline
void decoder_little_endian::get_32_AND(bm::word_t* w, unsigned count)
{
for (unsigned i = 0; i < count; i+=4)
{
w[i+0] &= get_32();
w[i+1] &= get_32();
w[i+2] &= get_32();
w[i+3] &= get_32();
}
}
inline
void decoder_little_endian::get_16(bm::short_t* s, unsigned count)
{
if (!s)
{
seek(int(count * sizeof(bm::short_t)));
return;
}
const unsigned char* buf = buf_;
const bm::short_t* s_end = s + count;
do
{
bm::short_t v1 = bm::short_t(buf_[0]);
bm::short_t v2 = bm::short_t(buf_[1]);
bm::short_t a = bm::short_t((v1 << 8) + v2);
*s++ = a;
buf += sizeof(a);
} while (s < s_end);
buf_ = (unsigned char*)buf;
}
// ----------------------------------------------------------------------
//
template<typename TEncoder>
void bit_out<TEncoder>::put_bit(unsigned value) BMNOEXCEPT
{
BM_ASSERT(value <= 1);
accum_ |= (value << used_bits_);
if (++used_bits_ == (sizeof(accum_) * 8))
flush_accum();
}
// ----------------------------------------------------------------------
template<typename TEncoder>
void bit_out<TEncoder>::put_bits(unsigned value, unsigned count) BMNOEXCEPT
{
unsigned used = used_bits_;
unsigned acc = accum_;
{
unsigned mask = ~0u;
mask >>= (sizeof(accum_) * 8) - count;
value &= mask;
}
for (;count;)
{
unsigned free_bits = unsigned(sizeof(accum_) * 8) - used;
BM_ASSERT(free_bits);
acc |= value << used;
if (count <= free_bits)
{
used += count;
break;
}
else
{
value >>= free_bits;
count -= free_bits;
dest_.put_32(acc);
acc = used = 0;
continue;
}
}
if (used == (sizeof(accum_) * 8))
{
dest_.put_32(acc);
acc = used = 0;
}
used_bits_ = used;
accum_ = acc;
}
// ----------------------------------------------------------------------
template<typename TEncoder>
void bit_out<TEncoder>::put_zero_bit() BMNOEXCEPT
{
if (++used_bits_ == (sizeof(accum_) * 8))
flush_accum();
}
// ----------------------------------------------------------------------
template<typename TEncoder>
void bit_out<TEncoder>::put_zero_bits(unsigned count) BMNOEXCEPT
{
unsigned used = used_bits_;
unsigned free_bits = (sizeof(accum_) * 8) - used;
if (count >= free_bits)
{
flush_accum();
count -= free_bits;
used = 0;
for ( ;count >= sizeof(accum_) * 8; count -= sizeof(accum_) * 8)
{
dest_.put_32(0);
}
used += count;
}
else
{
used += count;
}
accum_ |= (1u << used);
if (++used == (sizeof(accum_) * 8))
flush_accum();
else
used_bits_ = used;
}
// ----------------------------------------------------------------------
template<typename TEncoder>
void bit_out<TEncoder>::gamma(unsigned value) BMNOEXCEPT
{
BM_ASSERT(value);
unsigned logv = bm::bit_scan_reverse32(value);
// Put zeroes + 1 bit
unsigned used = used_bits_;
unsigned acc = accum_;
const unsigned acc_bits = (sizeof(acc) * 8);
unsigned free_bits = acc_bits - used;
{
unsigned count = logv;
if (count >= free_bits)
{
dest_.put_32(acc);
acc = used ^= used;
count -= free_bits;
for ( ;count >= acc_bits; count -= acc_bits)
{
dest_.put_32(0);
}
used += count;
}
else
{
used += count;
}
acc |= (1 << used);
if (++used == acc_bits)
{
dest_.put_32(acc);
acc = used ^= used;
}
}
// Put the value bits
//
{
unsigned mask = (~0u);
mask >>= acc_bits - logv;
value &= mask;
}
for (;logv;)
{
acc |= value << used;
free_bits = acc_bits - used;
if (logv <= free_bits)
{
used += logv;
break;
}
else
{
value >>= free_bits;
logv -= free_bits;
dest_.put_32(acc);
acc = used ^= used;
continue;
}
} // for
used_bits_ = used;
accum_ = acc;
}
// ----------------------------------------------------------------------
template<typename TEncoder>
void bit_out<TEncoder>::bic_encode_u16_rg(
const bm::gap_word_t* arr,
unsigned sz,
bm::gap_word_t lo, bm::gap_word_t hi) BMNOEXCEPT
{
for (;sz;)
{
BM_ASSERT(lo <= hi);
unsigned mid_idx = sz >> 1;
bm::gap_word_t val = arr[mid_idx];
// write the interpolated value
// write(x, r) where x=(arr[mid] - lo - mid) r=(hi - lo - sz + 1);
{
unsigned r = hi - lo - sz + 1;
if (r)
{
unsigned value = val - lo - mid_idx;
unsigned logv = bm::bit_scan_reverse32(r);
put_bits(value, logv+1);
}
}
bic_encode_u16_rg(arr, mid_idx, lo, gap_word_t(val-1));
// tail recursion
// bic_encode_u16(arr + mid_idx + 1, sz - mid_idx - 1, gap_word_t(val+1), hi);
arr += mid_idx + 1;
sz -= mid_idx + 1;
lo = gap_word_t(val + 1);
} // for sz
}
// ----------------------------------------------------------------------
template<typename TEncoder>
void bit_out<TEncoder>::bic_encode_u32_cm(const bm::word_t* arr,
unsigned sz,
bm::word_t lo,
bm::word_t hi) BMNOEXCEPT
{
for (;sz;)
{
BM_ASSERT(lo <= hi);
unsigned mid_idx = sz >> 1;
bm::word_t val = arr[mid_idx];
// write the interpolated value
// write(x, r) where x=(arr[mid] - lo - mid) r=(hi - lo - sz + 1);
{
unsigned r = hi - lo - sz + 1;
if (r)
{
unsigned value = val - lo - mid_idx;
unsigned n = r + 1;
unsigned logv = bm::bit_scan_reverse32(n);
unsigned c = (unsigned)(1ull << (logv + 1)) - n;
int64_t half_c = c >> 1; // c / 2;
int64_t half_r = r >> 1; // r / 2;
int64_t lo1 = half_r - half_c;
int64_t hi1 = half_r + half_c + 1;
lo1 -= (n & 1);
logv += (value <= lo1 || value >= hi1);
put_bits(value, logv);
}
}
bic_encode_u32_cm(arr, mid_idx, lo, val-1);
// tail recursive call:
// bic_encode_u32_cm(arr + mid_idx + 1, sz - mid_idx - 1, val+1, hi);
arr += mid_idx + 1;
sz -= mid_idx + 1;
lo = val + 1;
} // for sz
}
// ----------------------------------------------------------------------
#if 0
/**
Shuffle structure for BIC
@internal
*/
template<unsigned N>
struct bic_encode_stack_u16
{
bm::gap_word_t val_[N];
bm::gap_word_t mid_[N];
bm::gap_word_t lo_[N];
bm::gap_word_t r_[N];
unsigned stack_size_ = 0;
void bic_shuffle(const bm::gap_word_t* arr,
bm::gap_word_t sz, bm::gap_word_t lo, bm::gap_word_t hi)
{
for (;sz;)
{
BM_ASSERT(lo <= hi);
bm::gap_word_t mid_idx = sz >> 1;
bm::gap_word_t val = arr[mid_idx];
unsigned r = hi - lo - sz + 1;
if (r)
{
unsigned s = stack_size_++;
r_[s] = (bm::gap_word_t)r;
val_[s] = val;
mid_[s] = mid_idx;
lo_[s] = lo;
}
bic_shuffle(arr, mid_idx, lo, bm::gap_word_t(val-1));
// tail recursive call:
// bic_shuffle(arr + mid_idx + 1, sz - mid_idx - 1, val+1, hi);
arr += mid_idx + 1;
sz -= mid_idx + 1;
lo = bm::gap_word_t(val + 1);
} // for sz
}
};
template<typename TEncoder>
void bit_out<TEncoder>::bic_encode_u16_cm(const bm::gap_word_t* arr,
unsigned sz_i,
bm::gap_word_t lo_i,
bm::gap_word_t hi_i) BMNOEXCEPT
{
BM_ASSERT(sz_i <= 65535);
bic_encode_stack_u16<bm::bie_cut_off> u16_stack;
// BIC re-ordering
u16_stack.bic_shuffle(arr, bm::gap_word_t(sz_i), lo_i, hi_i);
BM_ASSERT(sz_i == u16_stack.stack_size_);
for (unsigned i = 0; i < sz_i; ++i)
{
bm::gap_word_t val = u16_stack.val_[i];
bm::gap_word_t mid_idx = u16_stack.mid_[i];
bm::gap_word_t lo = u16_stack.lo_[i];
unsigned r = u16_stack.r_[i];
unsigned value = val - lo - mid_idx;
unsigned n = r + 1;
unsigned logv = bm::bit_scan_reverse32(n);
unsigned c = (unsigned)(1ull << (logv + 1)) - n;
int64_t half_c = c >> 1; // c / 2;
int64_t half_r = r >> 1; // r / 2;
int64_t lo1 = half_r - half_c;
int64_t hi1 = half_r + half_c + 1;
lo1 -= (n & 1);
logv += (value <= lo1 || value >= hi1);
put_bits(value, logv);
} // for i
}
#endif
template<typename TEncoder>
void bit_out<TEncoder>::bic_encode_u16_cm(const bm::gap_word_t* arr,
unsigned sz,
bm::gap_word_t lo,
bm::gap_word_t hi) BMNOEXCEPT
{
for (;sz;)
{
BM_ASSERT(lo <= hi);
unsigned mid_idx = sz >> 1;
bm::gap_word_t val = arr[mid_idx];
// write the interpolated value
// write(x, r) where x=(arr[mid] - lo - mid) r=(hi - lo - sz + 1);
{
unsigned r = hi - lo - sz + 1;
if (r)
{
unsigned value = val - lo - mid_idx;
unsigned n = r + 1;
unsigned logv = bm::bit_scan_reverse32(n);
unsigned c = (unsigned)(1ull << (logv + 1)) - n;
unsigned half_c = c >> 1; // c / 2;
unsigned half_r = r >> 1; // r / 2;
int64_t lo1 = (int64_t(half_r) - half_c - (n & 1u));
unsigned hi1 = (half_r + half_c);
logv += (value <= lo1 || value > hi1);
put_bits(value, logv);
}
}
bic_encode_u16_cm(arr, mid_idx, lo, bm::gap_word_t(val-1));
// tail recursive call:
// bic_encode_u32_cm(arr + mid_idx + 1, sz - mid_idx - 1, val+1, hi);
arr += ++mid_idx;
sz -= mid_idx;
lo = bm::gap_word_t(val + 1);
} // for sz
}
// ----------------------------------------------------------------------
//
// ----------------------------------------------------------------------
template<class TDecoder>
void bit_in<TDecoder>::bic_decode_u16_rg(bm::gap_word_t* arr, unsigned sz,
bm::gap_word_t lo,
bm::gap_word_t hi) BMNOEXCEPT
{
BM_ASSERT(sz);
do // for (;sz;)
{
BM_ASSERT(lo <= hi);
unsigned val;
// read the value
{
unsigned r = hi - lo - sz + 1;
if (r)
{
unsigned logv = bm::bit_scan_reverse32(r) + 1;
val = get_bits(logv);
BM_ASSERT(val <= r);
}
else
{
val = 0;
}
}
unsigned mid_idx = sz >> 1;
val += lo + mid_idx;
BM_ASSERT(val < 65536);
BM_ASSERT(mid_idx < 65536);
arr[mid_idx] = bm::gap_word_t(val);
if (sz <= 1)
return;
bic_decode_u16_rg(arr, mid_idx, lo, bm::gap_word_t(val - 1));
arr += mid_idx + 1;
sz -= mid_idx + 1;
lo = bm::gap_word_t(val + 1);
} while (sz); // for sz
}
// ----------------------------------------------------------------------
template<class TDecoder>
void bit_in<TDecoder>::bic_decode_u32_cm(bm::word_t* arr, unsigned sz,
bm::word_t lo,
bm::word_t hi) BMNOEXCEPT
{
BM_ASSERT(sz);
do
{
BM_ASSERT(lo <= hi);
// read the interpolated value
// x = read(r)+ lo + mid, where r = (hi - lo - sz + 1);
unsigned val = hi - lo - sz + 1;
if (val)
{
unsigned logv = bm::bit_scan_reverse32(val+1);
unsigned c = unsigned((1ull << (logv + 1)) - val - 1);
int64_t half_c = c >> 1;
int64_t half_r = val >> 1;
int64_t lo1 = half_r - half_c - ((val + 1) & 1);
int64_t hi1 = half_r + half_c + 1;
val = get_bits(logv);
if (val <= lo1 || val >= hi1)
val += (get_bit() << logv);
}
unsigned mid_idx = sz >> 1;
val += lo + mid_idx;
arr[mid_idx] = val;
if (sz <= 1)
return;
bic_decode_u32_cm(arr, mid_idx, lo, val-1);
// tail recursive call:
// bic_decode_u32_cm(arr + mid_idx + 1, sz - mid_idx - 1, val + 1, hi);
arr += ++mid_idx;
sz -= mid_idx;
lo = val + 1;
} while (sz);// for sz
}
// ----------------------------------------------------------------------
template<class TDecoder>
void bit_in<TDecoder>::bic_decode_u16_cm(bm::gap_word_t* arr, unsigned sz,
bm::gap_word_t lo,
bm::gap_word_t hi) BMNOEXCEPT
{
BM_ASSERT(sz);
do
{
BM_ASSERT(lo <= hi);
// read the interpolated value
// x = read(r)+ lo + mid, where r = (hi - lo - sz + 1);
unsigned val = hi - lo - sz + 1;
if (val)
{
unsigned logv = bm::bit_scan_reverse32(val+1);
unsigned c = unsigned((1ull << (logv + 1)) - val - 1);
int64_t half_c = c >> 1; // c / 2;
int64_t half_r = val >> 1; // r / 2;
int64_t lo1 = half_r - half_c - ((val + 1) & 1);
int64_t hi1 = half_r + half_c + 1;
val = get_bits(logv);
if (val <= lo1 || val >= hi1)
val += (get_bit() << logv);
}
unsigned mid_idx = sz >> 1;
val += lo + mid_idx;
arr[mid_idx] = bm::gap_word_t(val);
if (sz <= 1)
return;
bic_decode_u16_cm(arr, mid_idx, lo, bm::gap_word_t(val-1));
// tail recursive call:
// bic_decode_u16_cm(arr + mid_idx + 1, sz - mid_idx - 1, val + 1, hi);
arr += ++mid_idx;
sz -= mid_idx;
lo = bm::gap_word_t(val + 1);
} while (sz);// for sz
}
// ----------------------------------------------------------------------
template<class TDecoder>
void bit_in<TDecoder>::bic_decode_u16_cm_bitset(bm::word_t* block, unsigned sz,
bm::gap_word_t lo,
bm::gap_word_t hi) BMNOEXCEPT
{
BM_ASSERT(sz);
do
{
BM_ASSERT(lo <= hi);
// read the interpolated value
// x = read(r)+ lo + mid, where r = (hi - lo - sz + 1);
unsigned val = hi - lo - sz + 1;
if (val)
{
unsigned logv = bm::bit_scan_reverse32(val+1);
unsigned c = unsigned((1ull << (logv + 1)) - val - 1);
int64_t half_c = c >> 1; // c / 2;
int64_t half_r = val >> 1; // r / 2;
int64_t lo1 = half_r - half_c - ((val + 1) & 1);
int64_t hi1 = half_r + half_c + 1;
val = get_bits(logv);
if (val <= lo1 || val >= hi1)
val += (get_bit() << logv);
}
unsigned mid_idx = sz >> 1;
val += lo + mid_idx;
// set bit in the target block
{
unsigned nword = (val >> bm::set_word_shift);
block[nword] |= (1u << (val & bm::set_word_mask));
}
if (sz <= 1)
return;
bic_decode_u16_cm_bitset(block, mid_idx, lo, bm::gap_word_t(val-1));
// tail recursive call:
// bic_decode_u32_cm(block, sz - mid_idx - 1, val + 1, hi);
sz -= ++mid_idx;
lo = bm::gap_word_t(val + 1);
} while (sz);
}
// ----------------------------------------------------------------------
template<class TDecoder>
void bit_in<TDecoder>::bic_decode_u16_cm_dry(unsigned sz,
bm::gap_word_t lo,
bm::gap_word_t hi) BMNOEXCEPT
{
BM_ASSERT(sz);
do
{
BM_ASSERT(lo <= hi);
unsigned val;
// read the interpolated value
// x = read(r)+ lo + mid, where r = (hi - lo - sz + 1);
{
unsigned r = hi - lo - sz + 1;
if (r)
{
unsigned logv = bm::bit_scan_reverse32(r+1);
unsigned c = unsigned((1ull << (logv + 1)) - r - 1);
int64_t half_c = c >> 1; // c / 2;
int64_t half_r = r >> 1; // r / 2;
int64_t lo1 = half_r - half_c - ((r + 1) & 1);
int64_t hi1 = half_r + half_c + 1;
r = get_bits(logv);
if (r <= lo1 || r >= hi1)
r += (get_bit() << logv);
}
val = r;
}
unsigned mid_idx = sz >> 1;
val += lo + mid_idx;
if (sz <= 1)
return;
bic_decode_u16_cm_dry(mid_idx, lo, bm::gap_word_t(val-1));
// tail recursive call:
// bic_decode_u32_cm_dry(sz - mid_idx - 1, val + 1, hi);
sz -= mid_idx + 1;
lo = bm::gap_word_t(val + 1);
} while (sz); // for sz
}
// ----------------------------------------------------------------------
template<class TDecoder>
void bit_in<TDecoder>::bic_decode_u16_rg_bitset(bm::word_t* block, unsigned sz,
bm::gap_word_t lo,
bm::gap_word_t hi) BMNOEXCEPT
{
BM_ASSERT(sz);
do //for (;sz;)
{
BM_ASSERT(lo <= hi);
unsigned val;
// read the value
{
unsigned r = hi - lo - sz + 1;
if (r)
{
unsigned logv = bm::bit_scan_reverse32(r) + 1;
val = get_bits(logv);
BM_ASSERT(val <= r);
}
else
{
val = 0;
}
}
unsigned mid_idx = sz >> 1;
val += lo + mid_idx;
BM_ASSERT(val < 65536);
BM_ASSERT(mid_idx < 65536);
// set bit in the target block
{
unsigned nword = (val >> bm::set_word_shift);
block[nword] |= (1u << (val & bm::set_word_mask));
}
if (sz == 1)
return;
bic_decode_u16_rg_bitset(block, mid_idx, lo, bm::gap_word_t(val - 1));
// tail recursion of:
//bic_decode_u16_bitset(block, sz - mid_idx - 1, bm::gap_word_t(val + 1), hi);
sz -= mid_idx + 1;
lo = bm::gap_word_t(val + 1);
} while(sz); // for sz
}
// ----------------------------------------------------------------------
template<class TDecoder>
void bit_in<TDecoder>::bic_decode_u16_rg_dry(unsigned sz,
bm::gap_word_t lo,
bm::gap_word_t hi) BMNOEXCEPT
{
for (;sz;)
{
BM_ASSERT(lo <= hi);
unsigned val;
// read the value
{
unsigned r = hi - lo - sz + 1;
if (r)
{
unsigned logv = bm::bit_scan_reverse32(r) + 1;
val = get_bits(logv);
BM_ASSERT(val <= r);
}
else
{
val = 0;
}
}
unsigned mid_idx = sz >> 1;
val += lo + mid_idx;
BM_ASSERT(val < 65536);
BM_ASSERT(mid_idx < 65536);
if (sz == 1)
return;
bic_decode_u16_rg_dry(mid_idx, lo, bm::gap_word_t(val - 1));
sz -= mid_idx + 1;
lo = bm::gap_word_t(val + 1);
} // for sz
}
// ----------------------------------------------------------------------
template<class TDecoder>
unsigned bit_in<TDecoder>::gamma() BMNOEXCEPT
{
unsigned acc = accum_;
unsigned used = used_bits_;
if (used == (sizeof(acc) * 8))
{
acc = src_.get_32();
used ^= used;
}
unsigned zero_bits = 0;
while (true)
{
if (acc == 0)
{
zero_bits = unsigned(zero_bits +(sizeof(acc) * 8) - used);
used = 0;
acc = src_.get_32();
continue;
}
unsigned first_bit_idx =
#if defined(BM_x86) && (defined(__GNUG__) || defined(_MSC_VER)) && !(defined(__arm64__) || defined(__arm__))
bm::bsf_asm32(acc);
#else
bm::bit_scan_fwd(acc);
#endif
acc >>= first_bit_idx;
zero_bits += first_bit_idx;
used += first_bit_idx;
break;
} // while
// eat the border bit
//
if (used == (sizeof(acc) * 8))
{
acc = src_.get_32();
used = 1;
}
else
{
++used;
}
acc >>= 1;
// get the value
unsigned current;
unsigned free_bits = unsigned((sizeof(acc) * 8) - used);
if (zero_bits <= free_bits)
{
take_accum:
current =
(acc & block_set_table<true>::_left[zero_bits]) | (1 << zero_bits);
acc >>= zero_bits;
used += zero_bits;
goto ret;
}
if (used == (sizeof(acc) * 8))
{
acc = src_.get_32();
used ^= used;
goto take_accum;
}
// take the part
current = acc;
// read the next word
acc = src_.get_32();
used = zero_bits - free_bits;
current |=
((acc & block_set_table<true>::_left[used]) << free_bits) |
(1 << zero_bits);
acc >>= used;
ret:
accum_ = acc;
used_bits_ = used;
return current;
}
// ----------------------------------------------------------------------
template<class TDecoder>
unsigned bit_in<TDecoder>::get_bits(unsigned count) BMNOEXCEPT
{
BM_ASSERT(count);
const unsigned maskFF = ~0u;
unsigned acc = accum_;
unsigned used = used_bits_;
unsigned value = 0;
unsigned free_bits = unsigned((sizeof(acc) * 8) - used);
if (count <= free_bits)
{
take_accum:
value = acc & (maskFF >> (32 - count));
acc >>= count;
used += count;
goto ret;
}
if (used == (sizeof(acc) * 8))
{
acc = src_.get_32();
used = 0;
goto take_accum;
}
value = acc;
acc = src_.get_32();
used = count - free_bits;
value |= ((acc & (maskFF >> (32 - used))) << free_bits);
acc >>= used;
ret:
accum_ = acc;
used_bits_ = used;
return value;
}
// ----------------------------------------------------------------------
template<class TDecoder>
unsigned bit_in<TDecoder>::get_bit() BMNOEXCEPT
{
const unsigned mask = (~0u) >> (32 - 1); // 100000...
unsigned value = accum_ & mask;
if (unsigned free_bits = unsigned(32u - used_bits_); free_bits)
{
accum_ >>= 1; ++used_bits_;
}
else
{
BM_ASSERT(used_bits_ == (sizeof(accum_) * 8));
unsigned a = src_.get_32();
value = a & mask;
used_bits_ = 1;
accum_ = (a >> 1);
}
return value;
}
// ----------------------------------------------------------------------
} // namespace bm
#ifdef _MSC_VER
#pragma warning(pop)
#endif
#endif
BMNOEXCEPT
#define BMNOEXCEPT
Definition bmdef.h:82
BMFORCEINLINE
#define BMFORCEINLINE
Definition bmdef.h:213
BM_ASSERT
#define BM_ASSERT
Definition bmdef.h:139
bmutil.h
Bit manipulation primitives (internal).
bm::bit_in::gamma
unsigned gamma() BMNOEXCEPT
decode unsigned value using Elias Gamma coding
Definition encoding.h:1792
bm::bit_in< DEC >::bic_decode_u16
void bic_decode_u16(bm::gap_word_t *arr, unsigned sz, bm::gap_word_t lo, bm::gap_word_t hi) BMNOEXCEPT
Definition encoding.h:275
bm::bit_in< DEC >::bic_decode_u16_cm
void bic_decode_u16_cm(bm::gap_word_t *arr, unsigned sz, bm::gap_word_t lo, bm::gap_word_t hi) BMNOEXCEPT
bm::bit_in::bic_decode_u16_bitset
void bic_decode_u16_bitset(bm::word_t *block, unsigned sz, bm::gap_word_t lo, bm::gap_word_t hi) BMNOEXCEPT
Definition encoding.h:282
bm::bit_in< DEC >::get_bit
unsigned get_bit() BMNOEXCEPT
bm::bit_in< DEC >::bic_decode_u16_cm_dry
void bic_decode_u16_cm_dry(unsigned sz, bm::gap_word_t lo, bm::gap_word_t hi) BMNOEXCEPT
bm::bit_in::bit_in
bit_in(TDecoder &decoder) BMNOEXCEPT
Definition encoding.h:259
bm::bit_in::bic_decode_u32_cm
void bic_decode_u32_cm(bm::word_t *arr, unsigned sz, bm::word_t lo, bm::word_t hi) BMNOEXCEPT
Binary Interpolative array decode (32-bit).
Definition encoding.h:1516
bm::bit_in::bic_decode_u16_rg
void bic_decode_u16_rg(bm::gap_word_t *arr, unsigned sz, bm::gap_word_t lo, bm::gap_word_t hi) BMNOEXCEPT
Binary Interpolative array decode.
Definition encoding.h:1472
bm::bit_in::bic_decode_u16_dry
void bic_decode_u16_dry(unsigned sz, bm::gap_word_t lo, bm::gap_word_t hi) BMNOEXCEPT
Definition encoding.h:288
bm::bit_in::bic_decode_u16_rg_dry
void bic_decode_u16_rg_dry(unsigned sz, bm::gap_word_t lo, bm::gap_word_t hi) BMNOEXCEPT
Binary Interpolative array decode into /dev/null.
Definition encoding.h:1751
bm::bit_in< DEC >::get_bits
unsigned get_bits(unsigned count) BMNOEXCEPT
bm::bit_in< DEC >::bic_decode_u16_cm_bitset
void bic_decode_u16_cm_bitset(bm::word_t *block, unsigned sz, bm::gap_word_t lo, bm::gap_word_t hi) BMNOEXCEPT
bm::bit_in::bic_decode_u16_rg_bitset
void bic_decode_u16_rg_bitset(bm::word_t *block, unsigned sz, bm::gap_word_t lo, bm::gap_word_t hi) BMNOEXCEPT
Binary Interpolative array decode into bitset (32-bit based).
Definition encoding.h:1703
bm::bit_out::~bit_out
~bit_out()
Definition encoding.h:189
bm::bit_out::bic_encode_u16_rg
void bic_encode_u16_rg(const bm::gap_word_t *arr, unsigned sz, bm::gap_word_t lo, bm::gap_word_t hi) BMNOEXCEPT
Binary Interpolative encoding (array of 16-bit ints).
Definition encoding.h:1259
bm::bit_out< bm::encoder >::flush
void flush() BMNOEXCEPT
Definition encoding.h:230
bm::bit_out::bit_out
bit_out(TEncoder &dest)
Definition encoding.h:185
bm::bit_out< bm::encoder >::put_zero_bits
void put_zero_bits(unsigned count) BMNOEXCEPT
bm::bit_out::bic_encode_u32_cm
void bic_encode_u32_cm(const bm::word_t *arr, unsigned sz, bm::word_t lo, bm::word_t hi) BMNOEXCEPT
Binary Interpolative encoding (array of 32-bit ints) cm - "center-minimal".
Definition encoding.h:1294
bm::bit_out::put_bit
void put_bit(unsigned value) BMNOEXCEPT
issue single bit into encode bit-stream
Definition encoding.h:1095
bm::bit_out::put_bits
void put_bits(unsigned value, unsigned count) BMNOEXCEPT
issue count bits out of value
Definition encoding.h:1106
bm::bit_out< bm::encoder >::gamma
void gamma(unsigned value) BMNOEXCEPT
bm::bit_out::put_zero_bit
void put_zero_bit() BMNOEXCEPT
issue 0 into output stream
Definition encoding.h:1148
bm::bit_out< bm::encoder >::bic_encode_u16_cm
void bic_encode_u16_cm(const bm::gap_word_t *arr, unsigned sz, bm::gap_word_t lo, bm::gap_word_t hi) BMNOEXCEPT
bm::bit_out< bm::encoder >::bic_encode_u16
void bic_encode_u16(const bm::gap_word_t *arr, unsigned sz, bm::gap_word_t lo, bm::gap_word_t hi) BMNOEXCEPT
Definition encoding.h:207
bm::decoder_base::start_
const unsigned char * start_
Definition encoding.h:115
bm::decoder_base::decoder_base
decoder_base(const unsigned char *buf) BMNOEXCEPT
Definition encoding.h:90
bm::decoder_base::buf_
const unsigned char * buf_
Definition encoding.h:114
bm::decoder_base::get_h64
bm::id64_t get_h64() BMNOEXCEPT
Read h-64-bit.
Definition encoding.h:691
bm::decoder_base::get_pos
const unsigned char * get_pos() const BMNOEXCEPT
Return current buffer pointer.
Definition encoding.h:105
bm::decoder_base::seek
void seek(int delta) BMNOEXCEPT
change current position
Definition encoding.h:99
bm::decoder_base::size
size_t size() const BMNOEXCEPT
Returns size of the current decoding stream.
Definition encoding.h:96
bm::decoder_base::get_8
unsigned char get_8() BMNOEXCEPT
Reads character from the decoding buffer.
Definition encoding.h:93
bm::decoder_base::memcpy
void memcpy(unsigned char *dst, size_t count) BMNOEXCEPT
read bytes from the decode buffer
Definition encoding.h:679
bm::decoder_base::set_pos
void set_pos(const unsigned char *pos) BMNOEXCEPT
Set current buffer pointer.
Definition encoding.h:108
bm::decoder_little_endian::decoder_little_endian
decoder_little_endian(const unsigned char *buf)
Definition encoding.h:952
bm::decoder_little_endian::get_32
bm::word_t get_32()
Definition encoding.h:977
bm::decoder_little_endian::get_16
bm::short_t get_16()
Definition encoding.h:958
bm::decoder_little_endian::get_32_OR
bool get_32_OR(bm::word_t *w, unsigned count)
Definition encoding.h:1035
bm::decoder_little_endian::get_24
bm::word_t get_24()
Definition encoding.h:967
bm::decoder_little_endian::get_48
bm::id64_t get_48()
Definition encoding.h:986
bm::decoder_little_endian::get_64
bm::id64_t get_64()
Definition encoding.h:999
bm::decoder_little_endian::get_32_AND
void get_32_AND(bm::word_t *w, unsigned count)
Definition encoding.h:1057
bm::decoder
Class for decoding data from memory buffer.
Definition encoding.h:126
bm::decoder::get_32
bm::word_t get_32() BMNOEXCEPT
Reads 32-bit word from the decoding buffer.
Definition encoding.h:751
bm::decoder::get_24
bm::word_t get_24() BMNOEXCEPT
Reads 32-bit word from the decoding buffer.
Definition encoding.h:738
bm::decoder::get_32_OR
bool get_32_OR(bm::word_t *w, unsigned count) BMNOEXCEPT
Reads block of 32-bit words from the decoding buffer and ORs to the destination.
Definition encoding.h:844
bm::decoder::get_64
bm::id64_t get_64() BMNOEXCEPT
Reads 64-bit word from the decoding buffer.
Definition encoding.h:786
bm::decoder::get_32_AND
void get_32_AND(bm::word_t *w, unsigned count) BMNOEXCEPT
Reads block of 32-bit words from the decoding buffer and ANDs to the destination.
Definition encoding.h:885
bm::decoder::get_16
bm::short_t get_16() BMNOEXCEPT
Reads 16-bit word from the decoding buffer.
Definition encoding.h:722
bm::decoder::decoder
decoder(const unsigned char *buf) BMNOEXCEPT
Construction.
Definition encoding.h:713
bm::decoder::get_48
bm::id64_t get_48() BMNOEXCEPT
Reads 64-bit word from the decoding buffer.
Definition encoding.h:769
bm::encoder::position_type
unsigned char * position_type
Definition encoding.h:52
bm::encoder::size
size_t size() const BMNOEXCEPT
Returns size of the current encoding stream.
Definition encoding.h:529
bm::encoder::put_48
void put_48(bm::id64_t w) BMNOEXCEPT
Puts 48 bits word into encoding buffer.
Definition encoding.h:589
bm::encoder::get_pos
unsigned char * get_pos() const BMNOEXCEPT
Get current memory stream position.
Definition encoding.h:537
bm::encoder::put_64
void put_64(bm::id64_t w) BMNOEXCEPT
Puts 64 bits word into encoding buffer.
Definition encoding.h:606
bm::encoder::encoder
encoder(unsigned char *buf, size_t size) BMNOEXCEPT
Construction.
Definition encoding.h:398
bm::encoder::put_8
void put_8(unsigned char c) BMNOEXCEPT
Puts one character into the encoding buffer.
Definition encoding.h:434
bm::encoder::set_pos
void set_pos(unsigned char *buf_pos) BMNOEXCEPT
Set current memory stream position.
Definition encoding.h:545
bm::encoder::put_prefixed_array_16
void put_prefixed_array_16(unsigned char c, const bm::short_t *s, unsigned count, bool encode_count) BMNOEXCEPT
Encode 8-bit prefix + an array.
Definition encoding.h:417
bm::encoder::put_h64
void put_h64(bm::id64_t w) BMNOEXCEPT
Puts 64 bits word into encoding buffer with h-compression.
Definition encoding.h:628
bm::encoder::memcpy
void memcpy(const unsigned char *src, size_t count) BMNOEXCEPT
copy bytes into target buffer or just rewind if src is NULL
Definition encoding.h:516
bm::encoder::put_32
void put_32(bm::word_t w) BMNOEXCEPT
Puts 32 bits word into encoding buffer.
Definition encoding.h:571
bm::encoder::put_24
void put_24(bm::word_t w) BMNOEXCEPT
Puts 24 bits word into encoding buffer.
Definition encoding.h:555
bm::encoder::put_16
void put_16(bm::short_t s) BMNOEXCEPT
Puts short word (16 bits) into the encoding buffer.
Definition encoding.h:444
bm::encoder::put_prefixed_array_32
void put_prefixed_array_32(unsigned char c, const bm::word_t *w, unsigned count) BMNOEXCEPT
Encode 8-bit prefix + an array.
Definition encoding.h:406
bm::encoder::put_8_16_32
void put_8_16_32(unsigned w, unsigned char c8, unsigned char c16, unsigned char c32) BMNOEXCEPT
but gat plus value based on its VBR evaluation
Definition encoding.h:487
bm::gamma_decoder
Elias Gamma decoder.
Definition encoding.h:362
bm::gamma_decoder::stop
void stop()
Stop decoding sequence.
Definition encoding.h:374
bm::gamma_decoder::start
void start()
Start encoding sequence.
Definition encoding.h:369
bm::gamma_decoder::operator()
T operator()(void)
Decode word.
Definition encoding.h:379
bm::gamma_decoder::gamma_decoder
gamma_decoder(TBitIO &bin)
Definition encoding.h:364
bm::gamma_encoder
Functor for Elias Gamma encoding.
Definition encoding.h:341
bm::gamma_encoder::gamma_encoder
gamma_encoder(TBitIO &bout)
Definition encoding.h:343
bm::gamma_encoder::operator()
void operator()(T value)
Encode word.
Definition encoding.h:347
bm::avx2_or_arr_unal
bool avx2_or_arr_unal(__m256i *BMRESTRICT dst, const __m256i *BMRESTRICT src, const __m256i *BMRESTRICT src_end)
OR array elements against another unaligned array dst |= *src.
Definition bmavx2.h:888
bm::avx2_and_arr_unal
unsigned avx2_and_arr_unal(__m256i *BMRESTRICT dst, const __m256i *BMRESTRICT src, const __m256i *BMRESTRICT src_end)
AND array elements against another array (unaligned) dst &= *src.
Definition bmavx2.h:777
bm::sse2_or_arr_unal
bool sse2_or_arr_unal(__m128i *BMRESTRICT dst, const __m128i *BMRESTRICT src, const __m128i *BMRESTRICT src_end) BMNOEXCEPT
OR array elements against another array (unaligned) dst |= *src.
Definition bmsse_util.h:426
bm::sse2_and_arr_unal
unsigned sse2_and_arr_unal(__m128i *BMRESTRICT dst, const __m128i *BMRESTRICT src, const __m128i *BMRESTRICT src_end) BMNOEXCEPT
AND array elements against another array (unaligned) dst &= *src.
Definition bmsse_util.h:259
bm::decoder_big_endian
decoder decoder_big_endian
Class for decoding data from memory buffer.
Definition encoding.h:148
bm
Definition bm.h:78
bm::word_t
unsigned int word_t
Definition bmconst.h:39
bm::compute_h64_mask
unsigned compute_h64_mask(unsigned long long w) BMNOEXCEPT
Сompute mask of bytes presense in 64-bit word.
Definition bmutil.h:556
bm::bit_scan_fwd
BMFORCEINLINE T bit_scan_fwd(T v) BMNOEXCEPT
Definition bmutil.h:297
bm::bit_scan_reverse32
BMFORCEINLINE unsigned bit_scan_reverse32(unsigned w) BMNOEXCEPT
Definition bmutil.h:304
bm::set_word_shift
const unsigned set_word_shift
Definition bmconst.h:72
bm::id64_t
unsigned long long int id64_t
Definition bmconst.h:35
bm::gap_word_t
unsigned short gap_word_t
Definition bmconst.h:78
bm::set_word_mask
const unsigned set_word_mask
Definition bmconst.h:73
bm::short_t
unsigned short short_t
Definition bmconst.h:40
bm::block_set_table::_left
static const unsigned _left[32]
Definition bmconst.h:365