ALib C++ Library
Library Version: 2412 R0
Documentation generated by doxygen
Loading...
Searching...
No Matches
acalgos.inl
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_ALGOS
9#define HPP_ALIB_BITBUFFER_AC_V1_ALGOS 1
10#pragma once
11#if !defined(HPP_ALIB_MONOMEM_DETAIL_ARRAY_COMPRESSION_ALLOW)
12# error "ALib sources with ending '.inl' must not be included from outside."
13#endif
14
16
17namespace alib { namespace bitbuffer { namespace ac_v1 {
18
19
20/// Writes data compressed using class \alib{bitbuffer::ac_v1;HuffmanEncoder}.
21/// @tparam TI The integral type of the array to write.
22/// @param bw The bit writer to use.
23/// @param data The array to read the data from.
24template<typename TI>
26{
27 using TUI= typename std::make_unsigned<TI>::type;
28 if( !data.length() )
29 return;
30
31 HuffmanEncoder he( bw );
32
33 // count all occurrences of bytes
34 for(size_t i= 0; i < data.length(); ++i)
35 {
36 TUI val= data.get( i );
37 int bytes= sizeof(TUI);
38
39 // using a loop here (instead of "if constexpr..." because hd.read() is inlined
40 // (two times something similar below)
41 COUNTNEXT:
42 he.CountSymbol(uint8_t (val) );
43 if( --bytes )
44 {
46 val>>= 8;
48 goto COUNTNEXT;
49 }
50 }
51 // build huffman code
52 he.Generate();
53
54 // write out
55 for(size_t i= 0; i < data.length(); ++i)
56 {
57 TUI val= data.get( i );
58 ShiftOpRHS bits= bitsof(TUI) - 8;
59 while( bits >= 0 )
60 {
62 he.Write(uint8_t (val >> bits ) );
64
65 bits-= 8;
66 }
67 }
68}
69
70/// Reads data compressed using class \alib{bitbuffer::ac_v1;HuffmanDecoder}.
71/// @tparam TI The integral type of the array to read back.
72/// @param br The bit reader to use.
73/// @param data The array to read the data to.
74template<typename TI>
76{
77 using TUI= typename std::make_unsigned<TI>::type;
78 if( !data.length() )
79 return;
80 HuffmanDecoder hd( br );
81 hd.ReadTree();
82 for(size_t i= 0; i < data.length(); ++i)
83 {
84 TUI val= 0;
85 int bytes= sizeof(TUI);
86 READNEXT:
87 val|= hd.Read();
88 if( --bytes )
89 {
91 val<<= 8;
93 goto READNEXT;
94 }
95 data.set(i, val);
96 }
97}
98
99
100/// Writes array data by simply using the mechanics provided with class \alib{bitbuffer;BitWriter},
101/// which tries to shorten integrals on writing.
102/// @tparam TI The integral type of the array to write.
103/// @param bw The bit writer to use.
104/// @param data The array to read the data from.
105template<typename TI>
107{
108 for(size_t i= 0; i < data.length(); ++i)
109 {
110 bw.Write( data.get( i ) );
111 }
112}
113
114/// Reads data compressed using simply the mechanics provided with class \alib{bitbuffer;BitWriter}
115/// which tries to shorten integrals on writing.
116/// @tparam TI The integral type of the array to read back.
117/// @param br The bit reader to use.
118/// @param data The array to read the data to.
119template<typename TI>
121{
122 using TUI= typename std::make_unsigned<TI>::type;
123 for(size_t i= 0; i < data.length(); ++i)
124 data.set(i, br.Read<TUI>() );
125}
126
127/// Writes array data by writing only the difference to the minimum found value.
128/// @tparam TI The integral type of the array to write.
129/// @param bw The bit writer to use.
130/// @param data The array to read the data from.
131template<typename TI>
133{
134 using TUI= typename std::make_unsigned<TI>::type;
135
136 // calc min/max
137 data.calcMinMax();
138
139 // get bits needed
140 int bitCnt= lang::MSB0(TUI(data.max - data.min));
141
142 // write data
143 bw.Write<lang::Log2OfSize<TUI>() + 1>( bitCnt );
144 bw.Write( data.min );
145 if( !bitCnt )
146 return;
147
148 for(size_t i= 0; i < data.length(); ++i )
149 bw.Write( bitCnt, TUI( data.get(i) - data.min ) );
150}
151
152/// Reads data compressed with method \alib{bitbuffer::ac_v1;writeMinMax}.
153/// @tparam TI The integral type of the array to read back.
154/// @param br The bit reader to use.
155/// @param data The array to read the data to.
156template<typename TI>
158{
159 using TUI= typename std::make_unsigned<TI>::type;
160 auto bitCnt= br.Read<lang::Log2OfSize<TUI>() + 1>();
161 TUI min = br.Read<TUI>();
162
163 if( !bitCnt )
164 {
165 for(size_t i= 0; i < data.length(); ++i)
166 data.set(i, min );
167 return;
168 }
169 for(size_t i= 0; i < data.length(); ++i)
170 data.set(i, br.Read<TUI>( bitCnt ) + min );
171}
172
173/// Writes array data assuming it is sparsely set.
174/// @tparam TI The integral type of the array to write.
175/// @param bw The bit writer to use.
176/// @param data The array to read the data from.
177template<typename TI>
179{
180 if( !data.length() )
181 return;
182 using TUI= typename std::make_unsigned<TI>::type;
183 TUI first= data.get(0);
184 bw.Write(first);
185 for(size_t i= 1; i < data.length(); ++i)
186 {
187 TUI second= data.get(i);
188 if( second==first)
189 bw.Write<1>( 1) ;
190 else
191 {
192 bw.Write<1>( 0 );
193 bw.Write(second);
194 }
195 first= second;
196 }
197}
198
199/// Reads data compressed with method \alib{bitbuffer::ac_v1;writeSparse}.
200/// @tparam TI The integral type of the array to read back.
201/// @param br The bit reader to use.
202/// @param data The array to read the data to.
203template<typename TI>
205{
206 if( !data.length() )
207 return;
208 using TUI= typename std::make_unsigned<TI>::type;
209 auto prevVal= br.Read<TUI>();
210 data.set(0, prevVal);
211 for(size_t i= 1; i < data.length(); ++i)
212 data.set(i, prevVal= br.Read<1>() ? prevVal
213 : br.Read<TUI>() );
214}
215
216/// Writes array data assuming it is very sparsely set.
217/// @tparam TI The integral type of the array to write.
218/// @param bw The bit writer to use.
219/// @param data The array to read the data from.
220template<typename TI>
222{
223 using TUI= typename std::make_unsigned<TI>::type;
224 if( !data.length() )
225 return;
226
227 // calc min/max
228 data.calcMinMax();
229
230 // loop twice:
231 // 1st pass: calc longest repetition
232 // 2nd pass: write data
233 auto maxSegLen = (std::numeric_limits<size_t>::min)();
234 auto bitCntVal = 0;
235 auto bitCntRep = 0;
236 for( int pass= 0 ; pass < 2 ; ++ pass )
237 {
238 size_t segStart= 0;
239 TUI val = data.get(0);
240 TUI prevVal;
241 do
242 {
243 // find next segment [segStart - segEnd[
244 bool sparse;
245 size_t segEnd= segStart + 1;
246 prevVal= val;
247
248 // only one value left?
249 if( segEnd == data.length() )
250 {
251 sparse= false; // could also be set to true
252 }
253 else
254 {
255 val= data.get(segEnd);
256
257 sparse= (prevVal == val);
258
259 // find end
260 while( ( (prevVal == val) == sparse )
261 && ++segEnd < data.length())
262 {
263 prevVal= val;
264 val = data.get(segEnd);
265 }
266 if( !sparse ) // in diff mode, we have to go one back!
267 segEnd--;
268 }
269
270 // Pass 0: just note maximum segment length
271 if( pass== 0)
272 maxSegLen= (std::max)( maxSegLen, segEnd - segStart );
273 // Pass 1: write segment
274 else
275 {
276 // write
277 if( sparse )
278 { // write an extra 0 to indicate sparse mode
279 bw.Write( bitCntRep +1, (segEnd - segStart) << 1 );
280 bw.Write( bitCntVal , TUI(prevVal - data.min ) );
281 }
282 else
283 { // write an extra 1 to indicate non-sparse mode
284 bw.Write( bitCntRep +1, ((segEnd - segStart) << 1) | 1 );
285 for( size_t j= segStart; j < segEnd; ++j)
286 bw.Write( bitCntVal, TUI(data.get(j) - data.min ) );
287 }
288 }
289
290 // next segment
291 segStart= segEnd;
292 }
293 while( segStart < data.length() );
294
295 // pass 0 done: calc and write bits needed for value and repetition
296 if( pass == 0)
297 {
298 bitCntVal= lang::MSB0( TUI(data.max - data.min) );
299 bitCntRep= lang::MSB (maxSegLen);
300
302 bitCntRep
303 | bitCntVal << (lang::Log2OfSize<uint32_t>()+1) );
304 bw.Write( data.min );
305 }
306 } // 2 pass loop
307}
308
309/// Reads data compressed with method \alib{bitbuffer::ac_v1;writeVerySparse}.
310/// @tparam TI The integral type of the array to read back.
311/// @param br The bit reader to use.
312/// @param data The array to read the data to.
313template<typename TI>
315{
316 using TUI= typename std::make_unsigned<TI>::type;
317 if( !data.length() ) return;
318
319 auto bitCntRep = br.Read<lang::Log2OfSize<uint32_t>()+1 + lang::Log2OfSize<TUI>()+1>();
320 auto bitCntVal = bitCntRep >> (lang::Log2OfSize<uint32_t>() + 1);
321 bitCntRep&= lang::LowerMask<lang::Log2OfSize<uint32_t>() + 1, int>();
322
323 TUI minVal = br.Read<TUI>();
324
325 size_t segStart= 0;
326 while( segStart < data.length() )
327 {
328 size_t cntRep= br.Read<size_t>( bitCntRep + 1 );
329 size_t segEnd= segStart + (cntRep >> 1);
330 if( (cntRep & 1) == 0 ) // sparse
331 {
332 TUI val = br.Read<TUI>( bitCntVal ) + minVal;
333 for( size_t i= segStart ; i < segEnd ; ++i )
334 data.set(i, val);
335 }
336 else // different values
337 {
338 for( size_t i= segStart ; i < segEnd ; ++i )
339 data.set(i, br.Read<TUI>( bitCntVal ) + minVal);
340 }
341 segStart= segEnd;
342 }
343}
344
345/// Writes array data incrementally.
346/// @tparam TI The integral type of the array to write.
347/// @param bw The bit writer to use.
348/// @param data The array to read the data from.
349template<typename TI>
351{
352 if( !data.length() )
353 return;
354
355 using TUI= typename std::make_unsigned<TI>::type;
356
357 if( data.length() == 1 )
358 {
359 bw.Write(data.get(0));
360 return;
361 }
362
363 // calc min diff bits needed to write diff
364 data.calcMinMax();
365 auto bitCntPos= lang::MSB0(TUI( data.maxInc - data.minInc));
366 auto bitCntNeg= lang::MSB0(TUI( data.maxDec - data.minDec));
367
368 // write data
369 bw.Write<2 * (lang::Log2OfSize<TUI>() + 1)>( bitCntPos
370 | bitCntNeg << (lang::Log2OfSize<TUI>() + 1) );
371
372 bw.Write( data.minInc );
373 bw.Write( data.minDec );
374 TUI first= data.get(0);
375 bw.Write(first);
376 for(size_t i= 1; i < data.length(); ++i)
377 {
378 // send one bit indicating a positive (1) or negative (0) difference
379 // and then the difference as an unsigned value
380 TUI second= data.get(i);
381 if( second==first)
382 bw.Write( true );
383 else
384 {
385 bw.Write( false );
386 bool posNeg= second >= first;
387 bw.Write( posNeg );
388 bw.Write(posNeg ? bitCntPos : bitCntNeg,
389 posNeg ? TUI( second - first - data.minInc )
390 : TUI( first - second - data.minDec ) );
391 }
392 first= second;
393 }
394}
395
396/// Reads data compressed with \alib{bitbuffer::ac_v1;writeIncremental}.
397/// @tparam TI The integral type of the array to read back.
398/// @param br The bit reader to use.
399/// @param data The array to read the data to.
400template<typename TI>
402{
403 if( !data.length() )
404 return;
405
406 using TUI= typename std::make_unsigned<TI>::type;
407 if( data.length() == 1 )
408 {
409 data.set(0, br.Read<TUI>() );
410 return;
411 }
412
413 auto bitCntPos = br.Read<2 * (lang::Log2OfSize<TUI>()+1)>();
414 auto bitCntNeg = bitCntPos >> (lang::Log2OfSize<TUI>()+1);
415 bitCntPos&= lang::LowerMask<(lang::Log2OfSize<TUI>()+1), int>();
416 auto minDiffPos= br.Read<TUI>();
417 auto minDiffNeg= br.Read<TUI>();
418 auto prevVal = br.Read<TUI>();
419 data.set(0, prevVal);
420 for(size_t i= 1; i < data.length(); ++i)
421 {
422 TUI val;
423 if( br.Read<1>() )
424 val= prevVal;
425 else
426 {
427 bool posNeg= br.Read<1>();
428 TUI diff = br.Read<TUI>( posNeg ? bitCntPos : bitCntNeg );
429 val = posNeg ? TUI( prevVal + minDiffPos + diff )
430 : TUI( prevVal - minDiffNeg - diff );
431 }
432 data.set(i, prevVal= val);
433 }
434}
435
436
437
438}}} // namespace [alib::bitbuffer::ac_v1]
439
440#endif // HPP_ALIB_BITBUFFER_AC_V1_ALGOS
441
Reads bits from a BitBufferBase.
Writes bits into a BitBufferBase.
void Write(TIntegral value)
TUI minDec
Minimum decrease between two adjacent values.
Definition ac.hpp:100
TUI minInc
Minimum increase between two adjacent values.
Definition ac.hpp:99
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
ALIB_FORCE_INLINE TUI get(size_t idx) const
Definition ac.hpp:156
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
ALIB_API void Generate()
Generates the huffman encoding table and writes this information to the bit writer.
Definition huffman.cpp:96
ALIB_FORCE_INLINE void CountSymbol(uint8_t symbol)
Definition huffman.hpp:72
#define bitsof(type)
Definition bits.hpp:49
#define ALIB_WARNINGS_RESTORE
Definition alib.hpp:849
#define ALIB_WARNINGS_ALLOW_SHIFT_COUNT_OVERFLOW
Definition alib.hpp:795
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 TIntegral LowerMask()
constexpr int MSB0(TIntegral value)
constexpr int Log2OfSize()
constexpr int MSB(TIntegral value)
Definition alib.cpp:69
int ShiftOpRHS
Type alias in namespace alib.