← Back to branch summary

~ubuntu-branches/ubuntu/trusty/bmagic/trusty-proposed

« back to all changes in this revision

Viewing changes to src/encoding.h

  • Committer: Bazaar Package Importer
  • Author(s): Roberto C. Sanchez
  • Date: 2009-10-30 18:48:35 UTC
  • mfrom: (4.1.4 sid)
  • Revision ID: james.westby@ubuntu.com-20091030184835-2tqroygiq2pevwij
Tags: 3.6.0-1
New upstream release

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/encoding.h
1
1
/*
2
 
Copyright(c) 2002-2005 Anatoliy Kuznetsov(anatoliy_kuznetsov at yahoo.com)
 
2
Copyright(c) 2002-2009 Anatoliy Kuznetsov(anatoliy_kuznetsov at yahoo.com)
3
3
 
4
4
 
5
5
Permission is hereby granted, free of charge, to any person 
30
30
#define ENCODING_H__INCLUDED__
31
31
 
32
32
#include <memory.h>
 
33
#include "bmutil.h"
33
34
 
34
35
namespace bm
35
36
{
36
37
 
 
38
 
37
39
// ----------------------------------------------------------------
38
40
/*!
39
41
   \brief Memory encoding.
44
46
class encoder
45
47
{
46
48
public:
 
49
    typedef unsigned char* position_type;
 
50
public:
47
51
    encoder(unsigned char* buf, unsigned size);
48
52
    void put_8(unsigned char c);
49
53
    void put_16(bm::short_t  s);
50
54
    void put_16(const bm::short_t* s, unsigned count);
51
55
    void put_32(bm::word_t  w);
52
56
    void put_32(const bm::word_t* w, unsigned count);
 
57
    void put_prefixed_array_32(unsigned char c, 
 
58
                               const bm::word_t* w, unsigned count);
 
59
    void put_prefixed_array_16(unsigned char c, 
 
60
                               const bm::short_t* s, unsigned count,
 
61
                               bool encode_count);
53
62
    unsigned size() const;
 
63
    unsigned char* get_pos() const;
 
64
    void set_pos(unsigned char* buf_pos);
54
65
private:
55
66
    unsigned char*  buf_;
56
67
    unsigned char*  start_;
122
133
};
123
134
 
124
135
 
 
136
/** 
 
137
    Byte based writer for un-aligned bit streaming 
 
138
 
 
139
    @sa encoder
 
140
*/
 
141
template<class TEncoder>
 
142
class bit_out
 
143
{
 
144
public:
 
145
    bit_out(TEncoder& dest)
 
146
        : dest_(dest), used_bits_(0), accum_(0)
 
147
    {}
 
148
 
 
149
    ~bit_out()
 
150
    {
 
151
        if (used_bits_)
 
152
            dest_.put_32(accum_);
 
153
    }
 
154
 
 
155
    void put_bit(unsigned value)
 
156
    {
 
157
        BM_ASSERT(value <= 1);
 
158
        accum_ |= (value << used_bits_);
 
159
        if (++used_bits_ == (sizeof(accum_) * 8))
 
160
            flush_accum();
 
161
    }
 
162
 
 
163
    void put_bits(unsigned value, unsigned count)
 
164
    {
 
165
        unsigned used = used_bits_;
 
166
        unsigned acc = accum_;
 
167
 
 
168
        {
 
169
            unsigned mask = ~0;
 
170
            mask >>= (sizeof(accum_) * 8) - count;
 
171
            value &= mask;
 
172
        }
 
173
        for (;count;)
 
174
        {  
 
175
            acc |= value << used;
 
176
 
 
177
            unsigned free_bits = (sizeof(accum_) * 8) - used;
 
178
            if (count <= free_bits)
 
179
            {
 
180
                used += count;
 
181
                break;
 
182
            }
 
183
            else
 
184
            {
 
185
                value >>= free_bits;
 
186
                count -= free_bits;
 
187
                dest_.put_32(acc);
 
188
                acc = used = 0;
 
189
                continue;
 
190
            }
 
191
        }
 
192
        used_bits_ = used;
 
193
        accum_ = acc;
 
194
    }
 
195
 
 
196
    void put_zero_bit()
 
197
    {
 
198
        if (++used_bits_ == (sizeof(accum_) * 8))
 
199
            flush_accum();        
 
200
    }
 
201
 
 
202
    void put_zero_bits(register unsigned count)
 
203
    {
 
204
        register unsigned used = used_bits_;
 
205
        unsigned free_bits = (sizeof(accum_) * 8) - used;
 
206
        if (count >= free_bits)
 
207
        {
 
208
            flush_accum();
 
209
            count -= free_bits;
 
210
            used = 0;
 
211
 
 
212
            for ( ;count >= sizeof(accum_) * 8; count -= sizeof(accum_) * 8)
 
213
            {
 
214
                dest_.put_32(0);
 
215
            }
 
216
            used += count; 
 
217
        }
 
218
        else
 
219
        {
 
220
            used += count;
 
221
        }
 
222
        accum_ |= (1 << used);
 
223
        if (++used == (sizeof(accum_) * 8))
 
224
            flush_accum();
 
225
        else
 
226
            used_bits_ = used;
 
227
    }
 
228
 
 
229
 
 
230
    void gamma(unsigned value)
 
231
    {
 
232
        BM_ASSERT(value);
 
233
 
 
234
        unsigned logv = 
 
235
        #if defined(BM_x86)
 
236
            bm::bsr_asm32(value);
 
237
        #else
 
238
            bm::ilog2_LUT(value);
 
239
        #endif
 
240
 
 
241
        // Put zeroes + 1 bit
 
242
 
 
243
        unsigned used = used_bits_;
 
244
        unsigned acc = accum_;
 
245
        const unsigned acc_bits = (sizeof(acc) * 8);
 
246
        unsigned free_bits = acc_bits - used;
 
247
 
 
248
        {
 
249
        unsigned count = logv;
 
250
        if (count >= free_bits)
 
251
        {
 
252
            dest_.put_32(acc);
 
253
            acc = used ^= used;
 
254
            count -= free_bits;
 
255
 
 
256
            for ( ;count >= acc_bits; count -= acc_bits)
 
257
            {
 
258
                dest_.put_32(0);
 
259
            }
 
260
            used += count; 
 
261
        }
 
262
        else
 
263
        {
 
264
            used += count;
 
265
        }
 
266
        acc |= (1 << used);
 
267
        if (++used == acc_bits)
 
268
        {
 
269
            dest_.put_32(acc);
 
270
            acc = used ^= used;
 
271
        }
 
272
        }
 
273
 
 
274
        // Put the value bits
 
275
        //
 
276
        {
 
277
            unsigned mask = (~0);
 
278
            mask >>= acc_bits - logv;
 
279
            value &= mask;
 
280
        }
 
281
        for (;logv;)
 
282
        {  
 
283
            acc |= value << used;
 
284
            free_bits = acc_bits - used;
 
285
            if (logv <= free_bits)
 
286
            {
 
287
                used += logv;
 
288
                break;
 
289
            }
 
290
            else
 
291
            {
 
292
                value >>= free_bits;
 
293
                logv -= free_bits;
 
294
                dest_.put_32(acc);
 
295
                acc = used ^= used;
 
296
                continue;
 
297
            }
 
298
        } // for
 
299
 
 
300
        used_bits_ = used;
 
301
        accum_ = acc;
 
302
    }
 
303
 
 
304
 
 
305
    void flush()
 
306
    {
 
307
        if (used_bits_)
 
308
            flush_accum();
 
309
    }
 
310
 
 
311
private:
 
312
    void flush_accum()
 
313
    {
 
314
        dest_.put_32(accum_);
 
315
        used_bits_ = accum_ = 0;
 
316
    }
 
317
private:
 
318
    bit_out(const bit_out&);
 
319
    bit_out& operator=(const bit_out&);
 
320
 
 
321
private:
 
322
    TEncoder&      dest_;      ///< Bit stream target
 
323
    unsigned       used_bits_; ///< Bits used in the accumulator
 
324
    unsigned       accum_;     ///< write bit accumulator 
 
325
};
 
326
 
 
327
 
 
328
/** 
 
329
    Byte based reader for un-aligned bit streaming 
 
330
 
 
331
    @sa encoder
 
332
*/
 
333
template<class TDecoder>
 
334
class bit_in
 
335
{
 
336
public:
 
337
    bit_in(TDecoder& decoder)
 
338
        : src_(decoder),
 
339
          used_bits_(sizeof(accum_) * 8),
 
340
          accum_(0)
 
341
    {
 
342
    }
 
343
 
 
344
    unsigned get_bit()
 
345
    {
 
346
        if (used_bits_ == (sizeof(accum_) * 8))
 
347
        {
 
348
            accum_ = src_.get_32();
 
349
            used_bits_ = 0;
 
350
        }
 
351
        ++used_bits_;
 
352
        unsigned acc = accum_ & 1;
 
353
        accum_ >>= 1;
 
354
        return acc;
 
355
    }
 
356
 
 
357
    unsigned eat_zero_bits()
 
358
    {
 
359
        if (used_bits_ == (sizeof(accum_) * 8))
 
360
        {
 
361
            accum_ = src_.get_32();
 
362
            used_bits_ = 0;
 
363
        }
 
364
 
 
365
        unsigned cnt = 0;
 
366
        unsigned acc;
 
367
        do 
 
368
        {
 
369
            acc = accum_ & 1;
 
370
            if (acc == 0)
 
371
            {
 
372
                ++cnt;
 
373
                accum_ = accum_ >> 1;
 
374
                if (++used_bits_ == (sizeof(accum_) * 8))
 
375
                {
 
376
                    accum_ = src_.get_32();
 
377
                    used_bits_ = 0;
 
378
                }
 
379
            }
 
380
            else
 
381
            {
 
382
                break;
 
383
            }
 
384
        } while (true);
 
385
        return cnt;
 
386
    }
 
387
 
 
388
 
 
389
private:
 
390
    bit_in(const bit_in&);
 
391
    bit_in& operator=(const bit_in&);
 
392
private:
 
393
    TDecoder&           src_;        ///< Source of bytes
 
394
    unsigned            used_bits_;  ///< Bits used in the accumulator
 
395
    unsigned            accum_;      ///< read bit accumulator
 
396
};
 
397
 
 
398
 
 
399
/**
 
400
    Functor for Elias Gamma encoding
 
401
*/
 
402
template<typename T, typename TBitIO>
 
403
class gamma_encoder
 
404
{
 
405
public:
 
406
    gamma_encoder(TBitIO& bout) : bout_(bout) 
 
407
    {}
 
408
        
 
409
    /**
 
410
        Encode word
 
411
    */
 
412
    BMFORCEINLINE
 
413
    void operator()(T value)
 
414
    {
 
415
        bout_.gamma(value);
 
416
    }
 
417
private:
 
418
    gamma_encoder(const gamma_encoder&);
 
419
    gamma_encoder& operator=(const gamma_encoder&);
 
420
private:
 
421
    TBitIO&  bout_;
 
422
};
 
423
 
125
424
 
126
425
// ----------------------------------------------------------------
127
426
// Implementation details. 
137
436
: buf_(buf), start_(buf), size_(size)
138
437
{
139
438
}
 
439
/*!
 
440
    \grief Encode 8-bit prefix + an array
 
441
*/
 
442
inline void encoder::put_prefixed_array_32(unsigned char c, 
 
443
                                           const bm::word_t* w, 
 
444
                                           unsigned count)
 
445
{
 
446
    put_8(c);
 
447
    put_32(w, count);
 
448
}
 
449
 
 
450
/*!
 
451
    \grief Encode 8-bit prefix + an array 
 
452
*/
 
453
inline void encoder::put_prefixed_array_16(unsigned char c, 
 
454
                                           const bm::short_t* s, 
 
455
                                           unsigned count,
 
456
                                           bool encode_count)
 
457
{
 
458
    put_8(c);
 
459
    if (encode_count)
 
460
        put_16((bm::short_t) count);
 
461
    put_16(s, count);
 
462
}
 
463
 
140
464
 
141
465
/*!
142
466
   \fn void encoder::put_8(unsigned char c) 
155
479
*/
156
480
BMFORCEINLINE void encoder::put_16(bm::short_t s)
157
481
{
 
482
#if (BM_UNALIGNED_ACCESS_OK == 1)
 
483
        *((bm::short_t*)buf_) = s;
 
484
        buf_ += sizeof(s);
 
485
#else
158
486
    *buf_++ = (unsigned char) s;
159
487
    s >>= 8;
160
488
    *buf_++ = (unsigned char) s;
 
489
#endif
161
490
}
162
491
 
163
492
/*!
165
494
*/
166
495
inline void encoder::put_16(const bm::short_t* s, unsigned count)
167
496
{
 
497
#if (BM_UNALIGNED_ACCESS_OK == 1)
 
498
    unsigned short* buf = (unsigned short*)buf_;
 
499
    const bm::short_t* s_end = s + count;
 
500
    do 
 
501
    {
 
502
                *buf++ = *s++;
 
503
    } while (s < s_end);
 
504
                
 
505
        buf_ = (unsigned char*)buf;
 
506
#else
168
507
    unsigned char* buf = buf_;
169
508
    const bm::short_t* s_end = s + count;
170
509
    do 
179
518
    } while (s < s_end);
180
519
    
181
520
    buf_ = (unsigned char*)buf;
 
521
#endif
182
522
}
183
523
 
184
524
 
191
531
    return (unsigned)(buf_ - start_);
192
532
}
193
533
 
 
534
/**
 
535
    \brief Get current memory stream position
 
536
*/
 
537
inline encoder::position_type encoder::get_pos() const
 
538
{
 
539
    return buf_;
 
540
}
 
541
 
 
542
/**
 
543
    \brief Set current memory stream position
 
544
*/
 
545
inline void encoder::set_pos(encoder::position_type buf_pos)
 
546
{
 
547
    buf_ = buf_pos;
 
548
}
 
549
 
 
550
 
194
551
/*!
195
552
   \fn void encoder::put_32(bm::word_t w)
196
553
   \brief Puts 32 bits word into encoding buffer.
198
555
*/
199
556
BMFORCEINLINE void encoder::put_32(bm::word_t w)
200
557
{
 
558
#if (BM_UNALIGNED_ACCESS_OK == 1)
 
559
        *((bm::word_t*) buf_) = w;
 
560
        buf_ += sizeof(w);
 
561
#else
201
562
    *buf_++ = (unsigned char) w;
202
563
    *buf_++ = (unsigned char) (w >> 8);
203
564
    *buf_++ = (unsigned char) (w >> 16);
204
565
    *buf_++ = (unsigned char) (w >> 24);
 
566
#endif
205
567
}
206
568
 
207
569
/*!
210
572
inline 
211
573
void encoder::put_32(const bm::word_t* w, unsigned count)
212
574
{
 
575
#if (BM_UNALIGNED_ACCESS_OK == 1)
 
576
        bm::word_t* buf = (bm::word_t*)buf_;
 
577
    const bm::word_t* w_end = w + count;
 
578
    do 
 
579
    {
 
580
                *buf++ = *w++;
 
581
    } while (w < w_end);
 
582
    
 
583
    buf_ = (unsigned char*)buf;
 
584
#else
213
585
    unsigned char* buf = buf_;
214
586
    const bm::word_t* w_end = w + count;
215
587
    do 
227
599
    } while (w < w_end);
228
600
    
229
601
    buf_ = (unsigned char*)buf;
 
602
#endif
230
603
}
231
604
 
232
605
 
248
621
*/
249
622
BMFORCEINLINE bm::short_t decoder::get_16() 
250
623
{
 
624
#if (BM_UNALIGNED_ACCESS_OK == 1)
 
625
        bm::short_t a = *((bm::short_t*)buf_);
 
626
#else
251
627
    bm::short_t a = (bm::short_t)(buf_[0] + ((bm::short_t)buf_[1] << 8));
252
 
    buf_ += sizeof(a);
 
628
#endif
 
629
        buf_ += sizeof(a);
253
630
    return a;
254
631
}
255
632
 
259
636
*/
260
637
BMFORCEINLINE bm::word_t decoder::get_32() 
261
638
{
262
 
    bm::word_t a = buf_[0]+ ((unsigned)buf_[1] << 8) +
 
639
#if (BM_UNALIGNED_ACCESS_OK == 1)
 
640
        bm::word_t a = *((bm::word_t*)buf_);
 
641
#else
 
642
        bm::word_t a = buf_[0]+ ((unsigned)buf_[1] << 8) +
263
643
                   ((unsigned)buf_[2] << 16) + ((unsigned)buf_[3] << 24);
 
644
#endif
264
645
    buf_+=sizeof(a);
265
646
    return a;
266
647
}
279
660
        seek(count * 4);
280
661
        return;
281
662
    }
 
663
#if (BM_UNALIGNED_ACCESS_OK == 1)
 
664
        const bm::word_t* buf = (bm::word_t*)buf_;
 
665
    const bm::word_t* w_end = w + count;
 
666
    do 
 
667
    {
 
668
        *w++ = *buf++;
 
669
    } while (w < w_end);
 
670
#else
282
671
    const unsigned char* buf = buf_;
283
672
    const bm::word_t* w_end = w + count;
284
673
    do 
288
677
        *w++ = a;
289
678
        buf += sizeof(a);
290
679
    } while (w < w_end);
 
680
#endif
291
681
    buf_ = (unsigned char*)buf;
292
682
}
293
683
 
304
694
        seek(count * 2);
305
695
        return;
306
696
    }
307
 
 
 
697
#if (BM_UNALIGNED_ACCESS_OK == 1)
 
698
        const bm::short_t* buf = (bm::short_t*)buf_;
 
699
    const bm::short_t* s_end = s + count;
 
700
    do 
 
701
    {
 
702
        *s++ = *buf++;
 
703
    } while (s < s_end);
 
704
#else
308
705
    const unsigned char* buf = buf_;
309
706
    const bm::short_t* s_end = s + count;
310
707
    do 
313
710
        *s++ = a;
314
711
        buf += sizeof(a);
315
712
    } while (s < s_end);
 
713
#endif
316
714
    buf_ = (unsigned char*)buf;
317
715
}
318
716