ALib C++ Library
Library Version: 2412 R0
Documentation generated by doxygen
Loading...
Searching...
No Matches
ac.hpp
Go to the documentation of this file.
1//==================================================================================================
2/// \file
3/// This header file is part of module \alib_bitbuffer of the \aliblong.
4///
5/// \emoji :copyright: 2013-2024 A-Worx GmbH, Germany.
6/// Published under \ref mainpage_license "Boost Software License".
7//==================================================================================================
8#ifndef HPP_ALIB_BITBUFFER_AC_V1
9#define HPP_ALIB_BITBUFFER_AC_V1
10#pragma once
11#include "alib/alib.hpp"
12ALIB_ASSERT_MODULE(BITBUFFER)
14#include "alib/bitbuffer/bitbuffer.hpp"
18#if ALIB_TIME
19# include "alib/time/ticks.hpp"
20#endif
21
22namespace alib { namespace bitbuffer {
23
24/// This sub-namespace of \alib_bitbuffer provides algorithms to compress integral arrays.
25/// Classes \alib{bitbuffer;ac_v1::ArrayCompressor} and \alib{bitbuffer;ac_v1::HuffmanEncoder} implement
26/// some data formats defined on bit-streams, which, in future versions of \alib, may be changed.
27/// With such future changes, theses classes will be published in a next enumerated namespace,
28/// parallel to this one.<br>
29/// This approach will allow software to read existing datasets from files (explicitly using
30/// older versions of the classes by selecting them via the namespace) and convert the data to the
31/// new binary format.
32///
33/// Type aliases \ref alib::ArrayCompressor, \ref alib::HuffmanEncoder and
34/// \ref alib::HuffmanDecoder will always refer to the latest version.
35///
36/// \note Currently, there is no other version of the class available.
37namespace ac_v1 {
38
39
40/// This class provides several algorithms to compress arrays of integral data and encode them
41/// in \alib{bitbuffer;BitBuffer} objects.
42/// Besides a standard \https{Huffman compression,en.wikipedia.org/wiki/Huffman_coding}, different
43/// simple approaches are "tested" and the best compression algorithm is then chosen.
44/// The general assumption of the approaches (besides the <em>Huffman coding</em>) is that the
45/// data contains "signal data", which is either
46/// - sparsely filled,
47/// - has incremental values, or
48/// - has just values of a certain smaller range.
49/// Also, combinations of these attributes are matched. Such data is often found in real-world
50/// applications and may be compressed much better than the generic \e Huffman approach may achieve.
52{
53 public:
54 static constexpr int NumberOfAlgorithms= 6; ///< The number of algorithms implemented.
55
56 /// Helper-class that allows access the array data. The design goal for introducing
57 /// this class (instead of providing array references in the interface methods) is
58 /// to allow a minimum of flexibility in respect to the data provision, while not using
59 /// callback functions (or virtual methods) to access each single array element.<p>
60 /// The approach implemented here, allows the array value to be a single attribute
61 /// residing in an array of structs.
62 /// For this, besides a base pointer to the first value and the length of the array,
63 /// the distance between two values within the array of structs (or classes) has
64 /// to be given.
65 ///
66 /// By nature, to do this, basic pointer manipulation is needed, which imposes the need
67 /// using <c>char*</c> values internally, which are cast back to the source type
68 /// with setters/getters.<br>
69 /// Consequently, templated constructors are given, which accept array types to
70 /// restrict such pointer conversion within the type.
71 ///
72 /// \note
73 /// In the case an application uses a more complex data scheme for storing array
74 /// data to be compressed, which are not accessible with this simple mechanism,
75 /// such data has to be written into temporary arrays before compression.
76 ///
77 /// Besides this, this accessor type, provides a transparent inline conversion of
78 /// signed integer values to its unsigned counterparts by performing
79 /// <em>"zig zag encoding"</em>.
80 ///
81 /// \tparam TIntegral The integral array type.
82 template <typename TIntegral>
83 class Array
84 {
85 public:
86 /// The unsigned version of template type \c TIntegral.
87 using TUI = typename std::make_unsigned<TIntegral>::type;
88
89 private:
90 char* firstVal; ///< Pointer to the first array value
91 size_t distance; ///< The distance in memory between two array values
92 size_t len; ///< The length of the array
93
94 public:
95 TUI min; ///< Maximum value (when zig-zag encoded)
96 TUI max; ///< Maximum value (when zig-zag encoded)
97 TUI maxInc; ///< Maximum increase between two adjacent values.
98 TUI maxDec; ///< Maximum decrease between two adjacent values.
99 TUI minInc; ///< Minimum increase between two adjacent values.
100 TUI minDec; ///< Minimum decrease between two adjacent values.
101
102 #if !DOXYGEN && ALIB_DEBUG_ARRAY_COMPRESSION
103 bool dbgIsCheckRead= false;
104 #endif
105
106 public:
107 /// This constructor may (and must only) be used when the data is stored in simple
108 /// arrays, hence when the data is not nested in an array of structs.
109 /// @param arrayStart Pointer to the first value of the array.
110 /// @param length The length of the array
111 Array( const TIntegral* arrayStart, size_t length )
112 : len(length)
113 {
114 firstVal= const_cast<char*>(
115 reinterpret_cast<const char*>(arrayStart) );
116 distance= sizeof(TUI);
117
118 // set min > max to indicate that this was not calculated, yet.
119 min= (std::numeric_limits<TUI>::max)();
120 max= (std::numeric_limits<TUI>::min)();
121 }
122
123 /// This constructor takes the first and the second array value as pointers.
124 /// The second is used to "assume" (!) the distance in memory between each value.
125 /// \attention If the assumption of such basic memory layout is wrong,
126 /// array values have to be copied to a temporary memory that satisfies
127 /// this rule.
128 /// @param firstValue Pointer to the first value of the array.
129 /// @param secondValue Pointer to the second value of the array
130 /// @param length The length of the array
131 Array( const TIntegral& firstValue, const TIntegral& secondValue, size_t length )
132 : len(length)
133 {
134 firstVal= const_cast<char*>(
135 reinterpret_cast<const char*>(&firstValue) );
136 distance= size_t( reinterpret_cast<const char*>(&secondValue)
137 - reinterpret_cast<const char*>(&firstValue)) ;
138
139 // set min > max to indicate that this was not calculated, yet.
140 min= (std::numeric_limits<TUI>::max)();
141 max= (std::numeric_limits<TUI>::min)();
142 }
143
144 public:
145 /// Returns the constant array length, given on construction.
146 /// @return The length of the array to compress/decompress
148 {
149 return len;
150 }
151
152 /// Returns the value at the given index as an unsigned integer value (for arrays of
153 /// signed values, zig-zag encoding is performed)
154 /// @param idx The index of the value in the array to retrieve.
155 /// @return An unsigned representation of the value at the given \p index.
156 ALIB_FORCE_INLINE TUI get(size_t idx) const
157 {
158 ALIB_ASSERT_ERROR( idx < len, "BITBUFFER/AC", "Array compression: Index out of bounds" )
159
161 if constexpr ( std::is_unsigned<TIntegral>::value )
162 return *(reinterpret_cast<TUI*>(firstVal + idx * distance));
163 else
164 {
165 TIntegral val= *(reinterpret_cast<TIntegral*>(firstVal + idx * distance));
166 return val >= 0 ? TUI( val << 1 )
167 : TUI( ((-val - 1) << 1) | 1 );
168 }
170 }
171
172 /// Writes the given value at the given idx as an unsigned integer value (for arrays
173 /// of signed values, zig-zag encoding is performed)
174 /// @param idx The index of the value in the array to set.
175 /// @param value The value to set.
177 void set(size_t idx, TUI value)
178 {
180 #if ALIB_DEBUG_ARRAY_COMPRESSION
181 TUI oldVal= 0;
182 if( dbgIsCheckRead )
183 oldVal= *reinterpret_cast<TUI*>(firstVal + idx * distance );
184 #endif
185
186 ALIB_ASSERT_ERROR( idx < len, "BITBUFFER/AC", "Array compression: Index out of bounds" )
187
188 if constexpr ( std::is_unsigned<TIntegral>::value )
189 *(reinterpret_cast<TIntegral*>(firstVal + idx * distance))= TIntegral(value);
190 else
191 {
192 *(reinterpret_cast<TIntegral*>(firstVal + idx * distance)) =
193 (value & 1) == 0 ? TIntegral( value >> 1)
194 : -( TIntegral( value >> 1) + 1 );
195 }
196
197 #if ALIB_DEBUG_ARRAY_COMPRESSION
198 if( dbgIsCheckRead )
199 ALIB_ASSERT_ERROR( oldVal== *(reinterpret_cast<TUI*>(firstVal + idx * distance )),
200 "BITBUFFER/AC", "Error reading back compressed array data" )
201 #endif
203 }
204
205 /// Loops over the data and stores minimum and maximum values as well as minimum
206 /// and maximum value distances.
208 {
209 // already done?
210 if( max >= min )
211 return;
212
213 maxInc= 0;
214 maxDec= 0;
215
216 // zero-length array
217 if( !len )
218 {
219 minInc= 0;
220 minDec= 0;
221 return;
222 }
223 maxInc= 0;
224 maxDec= 0;
225 minInc= (std::numeric_limits<TUI>::max)();
226 minDec= (std::numeric_limits<TUI>::max)();
227
228 TUI prevVal= get(0);
229 min= (std::min)( min, prevVal );
230 max= (std::max)( max, prevVal );
231
232 for(size_t i= 1; i < len; ++i)
233 {
234 TUI val= get(i);
235 min= (std::min)( min, val );
236 max= (std::max)( max, val );
237
238 if(val >= prevVal)
239 {
240 minInc= (std::min)( minInc, TUI( val - prevVal) );
241 maxInc= (std::max)( maxInc, TUI( val - prevVal) );
242 }
243 else
244 {
245 minDec= (std::min)( minDec, TUI( prevVal - val) );
246 maxDec= (std::max)( maxDec, TUI( prevVal - val) );
247 }
248
249 prevVal= val;
250 }
251
252 // correct minDec, if no negative distance was found.
253 if( maxDec == 0 )
254 minDec = 0;
255 }
256 }; // internal class Array
257
258
259 /// This enumeration denotes the different algorithms provided for compression.
260 /// This enum is defined to be \ref alib_enums_arithmetic "bitwise".
261 /// \note
262 /// With the inclusion of at least one
263 /// \ref alib_manual_modules_dependencies "\"ALib Camp\"" in the \alibdist, this
264 /// enum is furthermore \ref alib_basecamp_resources_details_data "resourced" and values
265 /// are appendable to class \alib{strings;TAString<TChar>;AString} and logable with \alox.
266 enum class Algorithm
267 {
268 /// No compression method selected.
269 NONE = 0,
270
271 /// All compression methods selected.
272 ALL = (1<< NumberOfAlgorithms) - 1,
273
274 /// Stores the data as integer values, which includes a simple sort of possible
275 /// compression as documented with
276 /// \alib{bitbuffer;BitWriter::Write<TIntegral>(TIntegral)}.
277 Uncompressed = 1,
278
279 /// Stores the differences between the minimum and maximum value found.
280 MinMax = 2,
281
282 /// Writes '1' if next value is equal to previous, '0' plus next value otherwise.
283 Sparse = 4,
284
285 /// Writes the number of following equal or non equal values.
286 VerySparse = 8,
287
288 /// Only distances of the values are written.
289 Incremental = 16,
290
291 /// Huffman encoding (byte based).
292 Huffman = 32,
293
294 END_OF_ENUM = 64,
295 };
296
297 /// Statistic struct to collect information about the performance of different array
298 /// compression approaches.
299 /// \note While other \alib module provide similar information only in debug compilations of
300 /// the library, the optional mechanics to collect statistics on array compression
301 /// (based on this struct) are likewise included in the release version.
303 {
304 #if ALIB_TIME
305 /// The overall compression time of each algorithm.
306 Ticks::Duration writeTimes [NumberOfAlgorithms] ={};
307
308 /// The overall decompression time of each algorithm.
309 Ticks::Duration readTimes [NumberOfAlgorithms] ={};
310
311 /// The number of measured decompression runs of each algorithm.
313 #endif
314
315 /// A counter for the number of times each algorithm was chosen for compression by
316 /// providing the shortest encoding. The values sum up to field #ctdCompressions.
318
319 /// For each algorithm, the sum of resulting bytes of all compressions performed.
321
322 /// For each algorithm, the sum of resulting bytes of those compressions where the
323 /// corresponding algorithm performed best. The values sum up to the overall
324 /// effective compression length.
326
327 /// For each algorithm, the sum of original bytes of those compressions where the
328 /// corresponding algorithm performed best. The values sum up to the overall
329 /// uncompressed size given with sumUncompressed.
331
332 /// The overall given array data to compress.
334
335 /// The number of executed compressions.
337
338
339 /// Adds another statistic object to this one.
340 /// @param other The statistics to add to this one.
341 /// @return A reference to this object.
343 {
344 for( int algoNo= 0; algoNo < NumberOfAlgorithms ; ++algoNo )
345 {
347 #if ALIB_TIME
348 writeTimes [algoNo]+= other.writeTimes [algoNo];
349 readTimes [algoNo]+= other.readTimes [algoNo];
350 ctdReads [algoNo]+= other.ctdReads [algoNo];
351 #endif
352 ctdWins [algoNo]+= other.ctdWins [algoNo];
353 sumCompressed [algoNo]+= other.sumCompressed [algoNo];
354 sumCompressedWon [algoNo]+= other.sumCompressedWon [algoNo];
355 sumUnCompressedWon[algoNo]+= other.sumUnCompressedWon[algoNo];
357 }
360 return *this;
361 }
362
363
364 #if ALIB_CAMP
365 /// Writes compression statistics to the given string buffer.
366 /// \par Availability
367 /// This method is included only if module \alib_basecamp is included in the
368 /// \alibdist.
369 ///
370 /// @param result A string buffer to collect the dump results.
371 /// @param headline A headline to integrate into the result table.
372 /// @param printTotals Determines if a summary line with summed up values should be
373 /// written.
375 void Print( AString& result, const String& headline, bool printTotals);
376 #endif
377 };
378
379
380 /// Deleted default constructor (this class cannot be created)
381 ArrayCompressor() = delete;
382
383
384// clang 14.0.6 (as of today 221216) falsely reports:
385// "warning: '@tparam' command used in a comment that is not attached to a template declaration
386#if !DOXYGEN
388#endif
389 /// Compresses the given array and writes the data into the given bit writer.
390 /// Each algorithm included in parameter \p algorithmsToTry are executed and finally that
391 /// one with the best compression result is chosen. Before the usage data, some bits that
392 /// determine the chosen algorithm are written, to enable method #Decompress
393 /// to deserialize the data.
394 ///
395 /// To gain efficiency, the number of probed algorithms can be narrowed by setting a
396 /// corresponding mask in \p algorithmsToTry. However, in many use case scenarios, the
397 /// execution time is a less critical design factor than the compression factor reached.
398 /// The decompression speed is solely dependent on the algorithm finally chosen, not on
399 /// the number of algorithms tested on compression.
400 ///
401 /// \attention
402 /// If only one algorithm is specified in parameter \p algorithmsToTry, then no
403 /// meta-information about the algorithm chosen is written. Consequently, when reading
404 /// back the data using #Decompress, the same single algorithm has to be provided.
405 ///
406 /// @tparam TValue The integral type of array data to compress.
407 /// @param bitWriter A bit writer to compress the data to.
408 /// @param data The array to compress.
409 /// @param algorithmsToTry The set of algorithms to be tried on compression for best
410 /// efficiency.<br>
411 /// Defaults to \ref Algorithm::ALL.
412 /// @param statistics Pointer a struct to collect statistics for the efficiency of array
413 /// compression related to given user data. If set, methods #Compress and
414 /// #Decompress will measure execution performance and compression rates
415 /// for each algorithm. With that, a software may collect information about
416 /// which algorithm is most efficient for typical datasets found and
417 /// a programmer may, based on such heuristics decide to exclude certain
418 /// algorithms not efficient in a use case.
419 /// @return A pair of value containing the resulting size in bits and the algorithm
420 /// chosen.
421
422 template <typename TValue>
423 static
424 std::pair<size_t, Algorithm> Compress ( BitWriter& bitWriter,
425 Array<TValue>& data,
426 Algorithm algorithmsToTry = Algorithm::ALL,
427 Statistics* statistics = nullptr
428 );
429
430
431 /// Decompresses an integral array from the given bit reader, which previously was encoded
432 /// with methods #Compress.
433 /// The integral data type has to be the same as with encoding.
434 /// \attention
435 /// If compression was performed with specifying only one algorithm in parameter
436 /// \p algorithmsToTry, then the same algorithm has to be exclusively set on decompression,
437 /// because in this case no meta-information about the compression algorithm is stored
438 /// in the bit stream.
439 /// @tparam TValue The integral type of array data to decompress.
440 /// @param bitReader A bit reader to read the data from.
441 /// @param data The array to decompress data to.
442 /// @param algorithm The algorithm to use for read back. Must only be given, in case
443 /// that compression was performed using a single algorithm of choice.
444 /// Defaults to \ref Algorithm::ALL.
445 /// @param statistics An optional statistics record to store the measured de-compression
446 /// time. See method #Compress for more information.
447 template <typename TValue>
448 static
449 void Decompress( BitReader& bitReader,
450 Array<TValue>& data,
451 Algorithm algorithm = Algorithm::ALL,
452 Statistics* statistics = nullptr);
453
455
456}; // class ArrayCompressor
457
458}}} // namespace [alib::bitbuffer::ac_v1]
459
463 alib::bitbuffer::ac_v1::ArrayCompressor::Algorithm::END_OF_ENUM )
464
465#define HPP_ALIB_MONOMEM_DETAIL_ARRAY_COMPRESSION_ALLOW
466#pragma once
468#undef HPP_ALIB_MONOMEM_DETAIL_ARRAY_COMPRESSION_ALLOW
469
470
471
472namespace alib { namespace bitbuffer { namespace ac_v1 {
473
475template <typename TValue>
476std::pair<size_t, ArrayCompressor::Algorithm> ArrayCompressor::Compress(
477 BitWriter& bw,
478 Array<TValue>& data,
479 Algorithm algorithmsToTry,
480 Statistics* statistics )
481{
482 ALIB_ASSERT_ERROR( data.length() * bitsof(TValue) < bw.RemainingSize(), "BITBUFFER/AC",
483 "BitBuffer is smaller than uncompressed data."
484 " No buffer overflow checks are performed during compression." )
485 ALIB_ASSERT_WARNING( data.length() * bitsof(TValue) * 2 < bw.RemainingSize(), "BITBUFFER/AC",
486 "BitBuffer remaining size should be twice as large as uncompressed data."
487 " No buffer overflow checks are performed during compression." )
488
489 auto initialBufferState= bw.GetIndex();
490 auto initialBufferFill = bw.Usage();
491 int multipleAlgorithms= CountElements(algorithmsToTry) > 1;
492 ALIB_ASSERT_ERROR(UnderlyingIntegral(algorithmsToTry) != 0, "BITBUFFER/AC", "No algorithms to check given" )
493
494 auto bestAlgo = ArrayCompressor::Algorithm::NONE;
495 auto bestAlgoNo= (std::numeric_limits<int>::max)();
496 auto lastAlgo = ArrayCompressor::Algorithm::NONE;
497 auto leastBits = (std::numeric_limits<size_t>::max)();
498
499 bool isFirstAlgo = true;
500 int algoNo= -1;
501 for( auto algo : enums::EnumIterator<ArrayCompressor::Algorithm>() )
502 {
503 algoNo++;
504
505 // included in write (test)?
506 if ( !HasBits(algorithmsToTry, algo ) )
507 continue;
508 if(!isFirstAlgo)
509 {
510 bw.Reset(initialBufferState);
511 }
512 isFirstAlgo= false;
513
514 // write algo number
515 if( multipleAlgorithms )
516 bw.Write<3>( algoNo );
517 #if ALIB_TIME
518 Ticks tm;
519 #endif
521 switch( lastAlgo= algo )
522 {
523 case Algorithm::Uncompressed: writeUncompressed(bw, data); break;
524 case Algorithm::MinMax: writeMinMax (bw, data); break;
525 case Algorithm::Sparse: writeSparse (bw, data); break;
526 case Algorithm::VerySparse: writeVerySparse (bw, data); break;
527 case Algorithm::Incremental: writeIncremental (bw, data); break;
528 case Algorithm::Huffman: writeHuffman (bw, data); break;
529 default: ALIB_ERROR("BITBUFFER/AC", "Internal error: Unknown compression algorithm number read") break;
530 }
532 auto bufferFill= bw.Usage();
533
534 if( statistics )
535 {
536 ALIB_WARNINGS_ALLOW_UNSAFE_BUFFER_USAGE
537 #if ALIB_TIME
538 statistics->writeTimes [algoNo]+= tm.Age();
539 #endif
540 statistics->sumCompressed[algoNo]+= (bufferFill - initialBufferFill)/8;
541 ALIB_WARNINGS_RESTORE
542 }
543
544 ALIB_ASSERT_ERROR( bufferFill > initialBufferFill, "BITBUFFER/AC", "Array compression: Nothing written")
545 if( leastBits > bufferFill - initialBufferFill )
546 {
547 leastBits= bufferFill - initialBufferFill;
548 bestAlgo = algo;
549 bestAlgoNo= algoNo;
550 }
551
552 // DEBUG-Test: Read back values right away and check for equal data
553 #if ALIB_DEBUG_ARRAY_COMPRESSION
554 {
555 bw.Flush();
556 BitReader br(bw.GetBuffer(), initialBufferState);
557 if( multipleAlgorithms )
558 {
559 auto readBackAlgo= Algorithm( 1 << br.Read<3>() );
560 ALIB_ASSERT_ERROR( readBackAlgo == algo, "BITBUFFER/AC",
561 "Wrong algorithm id was read back. This must never happen." )
562 }
563
564 data.dbgIsCheckRead= true;
565
567 switch( algo )
568 {
569 case Algorithm::Uncompressed: readUncompressed(br, data ); break;
570 case Algorithm::MinMax: readMinMax (br, data ); break;
571 case Algorithm::Sparse: readSparse (br, data ); break;
572 case Algorithm::VerySparse: readVerySparse (br, data ); break;
573 case Algorithm::Incremental: readIncremental (br, data ); break;
574 case Algorithm::Huffman: readHuffman (br, data ); break;
575 default: ALIB_ERROR("Internal error: Unknown compression algorithm number read") break;
576 }
578
579 data.dbgIsCheckRead= false;
580 }
581 #endif
582
583 if( !multipleAlgorithms )
584 break;
585 } // loop over algorithms
586
587 if( statistics )
588 {
590 statistics->ctdCompressions++;
591 statistics->sumUncompressed+= data.length() * sizeof(TValue);
592 statistics->ctdWins [bestAlgoNo]++;
593 statistics->sumCompressedWon [bestAlgoNo]+= leastBits/8;
594 statistics->sumUnCompressedWon[bestAlgoNo]+= data.length() * sizeof(TValue);
596 }
597
598
599 // write with best algorithm found (if this was not the last one anyhow)
600 if( multipleAlgorithms && (bestAlgo != lastAlgo) )
601 {
602 bw.Reset( initialBufferState );
603 bw.Write<3>( bestAlgoNo );
605 switch( bestAlgo )
606 {
607 case Algorithm::Uncompressed: writeUncompressed(bw, data); break;
608 case Algorithm::MinMax: writeMinMax (bw, data); break;
609 case Algorithm::Sparse: writeSparse (bw, data); break;
610 case Algorithm::VerySparse: writeVerySparse (bw, data); break;
611 case Algorithm::Incremental: writeIncremental (bw, data); break;
612 case Algorithm::Huffman: writeHuffman (bw, data); break;
613 default: ALIB_ERROR("BITBUFFER/AC", "Internal error: Unknown compression algorithm number read") break;
614 }
616 }
617
618 bw.Flush();
619 return std::make_pair( leastBits, bestAlgo );
620}
621
622template <typename TValue>
624 Array<TValue>& data,
625 Algorithm algorithmsToTry,
626 Statistics* statistics )
627{
628 ALIB_ASSERT_ERROR(UnderlyingIntegral(algorithmsToTry) != 0, "BITBUFFER/AC",
629 "No algorithms to check given" )
630 bool multipleAlgorithms= CountElements(algorithmsToTry) > 1;
631
632#if ALIB_TIME
633 Ticks tm;
634#endif
635 auto algo= multipleAlgorithms ? Algorithm( 1 << br.Read<3>() )
636 : algorithmsToTry;
638 switch( algo )
639 {
640 case Algorithm::Uncompressed: readUncompressed(br, data ); break;
641 case Algorithm::MinMax: readMinMax (br, data ); break;
642 case Algorithm::Sparse: readSparse (br, data ); break;
643 case Algorithm::VerySparse: readVerySparse (br, data ); break;
644 case Algorithm::Incremental: readIncremental (br, data ); break;
645 case Algorithm::Huffman: readHuffman (br, data ); break;
646 default: ALIB_ERROR("Internal error: Unknown compression algorithm number read") break;
647 }
649
650 if( statistics )
651 {
653 #if ALIB_TIME
654 auto algoNo= ToSequentialEnumeration( algo );
655 statistics->readTimes[algoNo]+= tm.Age();
656 statistics->ctdReads [algoNo]++;
657 #endif
659 }
660}
661
663
664}}} // namespace [alib::bitbuffer::ac_v1]
665
666#endif // HPP_ALIB_BITBUFFER_AC_V1
667
Reads bits from a BitBufferBase.
Writes bits into a BitBufferBase.
typename std::make_unsigned< TIntegral >::type TUI
The unsigned version of template type TIntegral.
Definition ac.hpp:87
TUI minDec
Minimum decrease between two adjacent values.
Definition ac.hpp:100
TUI minInc
Minimum increase between two adjacent values.
Definition ac.hpp:99
Array(const TIntegral &firstValue, const TIntegral &secondValue, size_t length)
Definition ac.hpp:131
TUI maxInc
Maximum increase between two adjacent values.
Definition ac.hpp:97
TUI maxDec
Maximum decrease between two adjacent values.
Definition ac.hpp:98
ALIB_FORCE_INLINE size_t length() const
Definition ac.hpp:147
size_t distance
The distance in memory between two array values.
Definition ac.hpp:91
size_t len
The length of the array.
Definition ac.hpp:92
ALIB_FORCE_INLINE TUI get(size_t idx) const
Definition ac.hpp:156
char * firstVal
Pointer to the first array value.
Definition ac.hpp:90
Array(const TIntegral *arrayStart, size_t length)
Definition ac.hpp:111
TUI min
Maximum value (when zig-zag encoded)
Definition ac.hpp:95
TUI max
Maximum value (when zig-zag encoded)
Definition ac.hpp:96
ALIB_FORCE_INLINE void set(size_t idx, TUI value)
Definition ac.hpp:177
static std::pair< size_t, Algorithm > Compress(BitWriter &bitWriter, Array< TValue > &data, Algorithm algorithmsToTry=Algorithm::ALL, Statistics *statistics=nullptr)
ArrayCompressor()=delete
Deleted default constructor (this class cannot be created)
static constexpr int NumberOfAlgorithms
The number of algorithms implemented.
Definition ac.hpp:54
@ 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.
static void Decompress(BitReader &bitReader, Array< TValue > &data, Algorithm algorithm=Algorithm::ALL, Statistics *statistics=nullptr)
#define bitsof(type)
Definition bits.hpp:49
#define ALIB_ASSERT_MODULE(modulename)
Definition alib.hpp:223
#define ALIB_ENUMS_MAKE_BITWISE(TEnum)
Definition bitwise.hpp:109
#define ALIB_WARNINGS_RESTORE
Definition alib.hpp:849
#define ALIB_FORCE_INLINE
Definition alib.hpp:650
#define ALIB_ENUMS_ASSIGN_RECORD(TEnum, TRecord)
Definition records.hpp:712
#define ALIB_API
Definition alib.hpp:639
#define ALIB_ENUMS_MAKE_ITERABLE(TEnum, StopElement)
Definition iterable.hpp:100
#define ALIB_ERROR(...)
Definition alib.hpp:1267
#define ALIB_WARNINGS_IGNORE_DOCS
Definition alib.hpp:832
#define ALIB_WARNINGS_ALLOW_SPARSE_ENUM_SWITCH
Definition alib.hpp:785
#define ALIB_ASSERT_ERROR(cond,...)
Definition alib.hpp:1271
#define ALIB_WARNINGS_ALLOW_UNSAFE_BUFFER_USAGE
Definition alib.hpp:760
#define ALIB_ASSERT_WARNING(cond,...)
Definition alib.hpp:1272
#define ALIB_TIME
Definition alib.hpp:214
void writeHuffman(BitWriter &bw, ArrayCompressor::Array< TI > &data)
Definition acalgos.inl:25
void readSparse(BitReader &br, ArrayCompressor::Array< TI > &data)
Definition acalgos.inl:204
void writeSparse(BitWriter &bw, ArrayCompressor::Array< TI > &data)
Definition acalgos.inl:178
void readUncompressed(BitReader &br, ArrayCompressor::Array< TI > &data)
Definition acalgos.inl:120
void readIncremental(BitReader &br, ArrayCompressor::Array< TI > &data)
Definition acalgos.inl:401
void writeIncremental(BitWriter &bw, ArrayCompressor::Array< TI > &data)
Definition acalgos.inl:350
void readVerySparse(BitReader &br, ArrayCompressor::Array< TI > &data)
Definition acalgos.inl:314
void readMinMax(BitReader &br, ArrayCompressor::Array< TI > &data)
Definition acalgos.inl:157
void writeUncompressed(BitWriter &bw, ArrayCompressor::Array< TI > &data)
Definition acalgos.inl:106
void writeMinMax(BitWriter &bw, ArrayCompressor::Array< TI > &data)
Definition acalgos.inl:132
void writeVerySparse(BitWriter &bw, ArrayCompressor::Array< TI > &data)
Definition acalgos.inl:221
void readHuffman(BitReader &br, ArrayCompressor::Array< TI > &data)
Definition acalgos.inl:75
constexpr std::underlying_type< TEnum >::type UnderlyingIntegral(TEnum element) noexcept
Definition alib.cpp:69
bitbuffer::BitWriter BitWriter
Type alias in namespace alib.
time::Ticks Ticks
Type alias in namespace alib.
Definition ticks.hpp:115
bitbuffer::BitReader BitReader
Type alias in namespace alib.
enums::EnumIterator< TEnum, TEnableIf > EnumIterator
Type alias in namespace alib.
Definition iterable.hpp:462
bitbuffer::BitBuffer BitBuffer
Type alias in namespace alib.
int ctdReads[NumberOfAlgorithms]
The number of measured decompression runs of each algorithm.
Definition ac.hpp:312
Ticks::Duration writeTimes[NumberOfAlgorithms]
The overall compression time of each algorithm.
Definition ac.hpp:306
size_t sumCompressed[NumberOfAlgorithms]
For each algorithm, the sum of resulting bytes of all compressions performed.
Definition ac.hpp:320
size_t sumUncompressed
The overall given array data to compress.
Definition ac.hpp:333
Statistics & operator+=(const Statistics &other)
Definition ac.hpp:342
ALIB_API void Print(AString &result, const String &headline, bool printTotals)
Definition ac.cpp:21
Ticks::Duration readTimes[NumberOfAlgorithms]
The overall decompression time of each algorithm.
Definition ac.hpp:309
size_t sumCompressedWon[NumberOfAlgorithms]
Definition ac.hpp:325
size_t sumUnCompressedWon[NumberOfAlgorithms]
Definition ac.hpp:330
int ctdCompressions
The number of executed compressions.
Definition ac.hpp:336