68 template <
typename TIntegral>
73 using TUI =
typename std::make_unsigned<TIntegral>::type;
88 #if !DOXYGEN && ALIB_DEBUG_ARRAY_COMPRESSION
89 bool dbgIsCheckRead=
false;
100 reinterpret_cast<const char*
>(arrayStart) );
104 min= (std::numeric_limits<TUI>::max)();
105 max= (std::numeric_limits<TUI>::min)();
116 Array(
const TIntegral& firstValue,
const TIntegral& secondValue,
size_t length )
120 reinterpret_cast<const char*
>(&firstValue) );
121 distance= size_t(
reinterpret_cast<const char*
>(&secondValue)
122 -
reinterpret_cast<const char*
>(&firstValue)) ;
125 min= (std::numeric_limits<TUI>::max)();
126 max= (std::numeric_limits<TUI>::min)();
144 if constexpr ( std::is_unsigned<TIntegral>::value )
149 return val >= 0 ?
TUI( val << 1 )
150 :
TUI( ((-val - 1) << 1) | 1 );
160 #if ALIB_DEBUG_ARRAY_COMPRESSION
168 if constexpr ( std::is_unsigned<TIntegral>::value )
169 *(
reinterpret_cast<TIntegral*
>(
firstVal + idx *
distance))= TIntegral(value);
173 (value & 1) == 0 ? TIntegral( value >> 1)
174 : -( TIntegral( value >> 1) + 1 );
177 #if ALIB_DEBUG_ARRAY_COMPRESSION
180 "BITBUFFER/AC",
"Error reading back compressed array data" )
204 minInc= (std::numeric_limits<TUI>::max)();
205 minDec= (std::numeric_limits<TUI>::max)();
208 min= (std::min)(
min, prevVal );
209 max= (std::max)(
max, prevVal );
211 for(
size_t i= 1; i <
len; ++i)
214 min= (std::min)(
min, val );
215 max= (std::max)(
max, val );
396 template <
typename TValue>
421 template <
typename TValue>
442#include "alib/bitbuffer/ac_v1/acalgos.inl.inl"
449template <
typename TValue>
453 Algorithm algorithmsToTry,
454 Statistics* statistics )
457 "BitBuffer is smaller than uncompressed data."
458 " No buffer overflow checks are performed during compression." )
460 "BitBuffer remaining size should be twice as large as uncompressed data."
461 " No buffer overflow checks are performed during compression." )
463 auto initialBufferState= bw.GetIndex();
464 auto initialBufferFill = bw.Usage();
465 int multipleAlgorithms= CountElements(algorithmsToTry) > 1;
466 ALIB_ASSERT_ERROR(
int(algorithmsToTry) != 0,
"BITBUFFER/AC",
"No algorithms to check given" )
469 auto bestAlgoNo= (std::numeric_limits<
int>::max)();
471 auto leastBits = (std::numeric_limits<
size_t>::max)();
473 bool isFirstAlgo = true;
480 if ( !HasBits(algorithmsToTry, algo ) )
484 bw.Reset(initialBufferState);
489 if( multipleAlgorithms )
490 bw.Write<3>( algoNo );
493 switch( lastAlgo= algo )
495 case Algorithm::Uncompressed: writeUncompressed(bw, data); break;
496 case Algorithm::MinMax: writeMinMax (bw, data); break;
497 case Algorithm::Sparse: writeSparse (bw, data); break;
498 case Algorithm::VerySparse: writeVerySparse (bw, data); break;
499 case Algorithm::Incremental: writeIncremental (bw, data); break;
500 case Algorithm::Huffman: writeHuffman (bw, data); break;
501 default: ALIB_ERROR(
"BITBUFFER/AC",
502 "Internal error: Unknown compression algorithm number read") break;
505 auto bufferFill= bw.Usage();
509 statistics->writeTimes [algoNo]+= tm.Age();
510 statistics->sumCompressed[algoNo]+= (bufferFill - initialBufferFill)/8;
514 "Array compression: Nothing written")
515 if( leastBits > bufferFill - initialBufferFill )
517 leastBits= bufferFill - initialBufferFill;
523 #if ALIB_DEBUG_ARRAY_COMPRESSION
526 BitReader br(bw.GetBuffer(), initialBufferState);
527 if( multipleAlgorithms )
529 auto readBackAlgo=
Algorithm( 1 << br.Read<3>() );
531 "Wrong algorithm id was read back. This must never happen." )
534 data.dbgIsCheckRead=
true;
546 "Internal error: Unknown compression algorithm number read")
551 data.dbgIsCheckRead= false;
555 if( !multipleAlgorithms )
561 statistics->ctdCompressions++;
562 statistics->sumUncompressed+= data.length() *
sizeof(TValue);
563 statistics->ctdWins [bestAlgoNo]++;
564 statistics->sumCompressedWon [bestAlgoNo]+= leastBits/8;
565 statistics->sumUnCompressedWon[bestAlgoNo]+= data.length() *
sizeof(TValue);
570 if( multipleAlgorithms && (bestAlgo != lastAlgo) )
572 bw.Reset( initialBufferState );
573 bw.Write<3>( bestAlgoNo );
583 default:
ALIB_ERROR(
"BITBUFFER/AC",
"Internal error: Unknown compression "
584 "algorithm number read") break;
590 return std::make_pair( leastBits, bestAlgo );
593template <typename TValue>
600 "No algorithms to check given" )
601 bool multipleAlgorithms= CountElements(algorithmsToTry) > 1;
604 auto algo= multipleAlgorithms ?
Algorithm( 1 << br.Read<3>() )
615 default:
ALIB_ERROR(
"BITBUFFER",
"Internal error: Unknown compression "
616 "algorithm number read") break;
623 statistics->readTimes[algoNo]+= tm.Age();
624 statistics->ctdReads [algoNo]++;
Reads bits from a BitBufferBase.
Writes bits into a BitBufferBase.
TUI maxDec
Maximum decrease between two adjacent values.
size_t distance
The distance in memory between two array values.
char * firstVal
Pointer to the first array value.
TUI max
Maximum value (when zig-zag encoded)
void set(size_t idx, TUI value)
TUI maxInc
Maximum increase between two adjacent values.
TUI min
Maximum value (when zig-zag encoded)
TUI minInc
Minimum increase between two adjacent values.
Array(const TIntegral &firstValue, const TIntegral &secondValue, size_t length)
TUI get(size_t idx) const
size_t len
The length of the array.
TUI minDec
Minimum decrease between two adjacent values.
Array(const TIntegral *arrayStart, size_t length)
typename std::make_unsigned< TIntegral >::type TUI
The unsigned version of template type TIntegral.
ArrayCompressor()=delete
Deleted default constructor (this class cannot be created)
static std::pair< size_t, Algorithm > Compress(BitWriter &bitWriter, Array< TValue > &data, Algorithm algorithmsToTry=Algorithm::ALL, Statistics *statistics=nullptr)
static void Decompress(BitReader &bitReader, Array< TValue > &data, Algorithm algorithm=Algorithm::ALL, Statistics *statistics=nullptr)
static constexpr int NumberOfAlgorithms
The number of algorithms implemented.
@ Huffman
Huffman encoding (byte based).
@ Incremental
Only distances of the values are written.
@ ALL
All compression methods selected.
@ Sparse
Writes '1' if next value is equal to previous, '0' plus next value otherwise.
@ MinMax
Stores the differences between the minimum and maximum value found.
@ VerySparse
Writes the number of following equal or non equal values.
@ NONE
No compression method selected.
#define ALIB_ENUMS_MAKE_BITWISE(TEnum)
#define ALIB_WARNINGS_RESTORE
#define ALIB_ENUMS_ASSIGN_RECORD(TEnum, TRecord)
#define ALIB_ASSERT_WARNING(cond, domain,...)
#define ALIB_ENUMS_MAKE_ITERABLE(TEnum, StopElement)
#define ALIB_ERROR(domain,...)
#define ALIB_WARNINGS_IGNORE_DOCS
#define ALIB_WARNINGS_ALLOW_SPARSE_ENUM_SWITCH
#define ALIB_ASSERT_ERROR(cond, domain,...)
void writeHuffman(BitWriter &bw, ArrayCompressor::Array< TI > &data)
void writeVerySparse(BitWriter &bw, ArrayCompressor::Array< TI > &data)
void readHuffman(BitReader &br, ArrayCompressor::Array< TI > &data)
void readSparse(BitReader &br, ArrayCompressor::Array< TI > &data)
void writeUncompressed(BitWriter &bw, ArrayCompressor::Array< TI > &data)
void readMinMax(BitReader &br, ArrayCompressor::Array< TI > &data)
void writeIncremental(BitWriter &bw, ArrayCompressor::Array< TI > &data)
void readVerySparse(BitReader &br, ArrayCompressor::Array< TI > &data)
void readUncompressed(BitReader &br, ArrayCompressor::Array< TI > &data)
void readIncremental(BitReader &br, ArrayCompressor::Array< TI > &data)
void writeSparse(BitWriter &bw, ArrayCompressor::Array< TI > &data)
void writeMinMax(BitWriter &bw, ArrayCompressor::Array< TI > &data)
constexpr std::underlying_type< TEnum >::type ToSequentialEnumeration(TEnum element)
bitbuffer::BitReader BitReader
Type alias in namespace alib.
strings::TAString< character, lang::HeapAllocator > AString
Type alias in namespace alib.
enumops::EnumIterator< TEnum > EnumIterator
Type alias in namespace alib.
strings::TString< character > String
Type alias in namespace alib.
time::Ticks Ticks
Type alias in namespace alib.
bitbuffer::BitWriter BitWriter
Type alias in namespace alib.
int ctdCompressions
The number of executed compressions.
size_t sumUnCompressedWon[NumberOfAlgorithms]
size_t sumCompressed[NumberOfAlgorithms]
For each algorithm, the sum of resulting bytes of all compressions performed.
int ctdWins[NumberOfAlgorithms]
Ticks::Duration readTimes[NumberOfAlgorithms]
The overall decompression time of each algorithm.
size_t sumCompressedWon[NumberOfAlgorithms]
int ctdReads[NumberOfAlgorithms]
The number of measured decompression runs of each algorithm.
Statistics & operator+=(const Statistics &other)
ALIB_DLL void Print(AString &result, const String &headline, bool printTotals)
size_t sumUncompressed
The overall given array data to compress.
Ticks::Duration writeTimes[NumberOfAlgorithms]
The overall compression time of each algorithm.