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