A.I.M.S algorithms


huffman.h
Go to the documentation of this file.
1 /* This software and supporting documentation are distributed by
2  * Institut Federatif de Recherche 49
3  * CEA/NeuroSpin, Batiment 145,
4  * 91191 Gif-sur-Yvette cedex
5  * France
6  *
7  * This software is governed by the CeCILL-B license under
8  * French law and abiding by the rules of distribution of free software.
9  * You can use, modify and/or redistribute the software under the
10  * terms of the CeCILL-B license as circulated by CEA, CNRS
11  * and INRIA at the following URL "http://www.cecill.info".
12  *
13  * As a counterpart to the access to the source code and rights to copy,
14  * modify and redistribute granted by the license, users are provided only
15  * with a limited warranty and the software's author, the holder of the
16  * economic rights, and the successive licensors have only limited
17  * liability.
18  *
19  * In this respect, the user's attention is drawn to the risks associated
20  * with loading, using, modifying and/or developing or reproducing the
21  * software by the user in light of its specific status of free software,
22  * that may mean that it is complicated to manipulate, and that also
23  * therefore means that it is reserved for developers and experienced
24  * professionals having in-depth computer knowledge. Users are therefore
25  * encouraged to load and test the software's suitability as regards their
26  * requirements in conditions enabling the security of their systems and/or
27  * data to be ensured and, more generally, to use and operate it in the
28  * same conditions as regards security.
29  *
30  * The fact that you are presently reading this means that you have had
31  * knowledge of the CeCILL-B license and that you accept its terms.
32  */
33 
34 
35 #ifndef AIMS_COMPRESSION_HUFFMAN_H
36 #define AIMS_COMPRESSION_HUFFMAN_H
37 
39 #include <aims/compression/lzhl.h>
40 #include <aims/def/general.h>
41 #include <aims/def/assert.h>
42 
43 
44 #define NHUFFSYMBOLS ( 256 + 16 + 2 )
45 
46 
47 //
48 // struct HuffStatTmpStruct
49 //
51 {
52  short i;
53  short n;
55  {
56  short tmp = x.n - n;
57  return tmp ? (tmp < 0): (x.i - i < 0);
58  }
59 };
60 
61 
62 //
63 // class HuffStat
64 //
66 {
67  public:
68  HuffStat();
69  ~HuffStat();
70 
71  short* stat;
72 
73  protected:
74  int _makeSortedTmp( HuffStatTmpStruct* );
75 };
76 
77 
78 //
79 // class LZHLEncoderStat
80 //
82 {
83  public:
85  ~LZHLEncoderStat();
86 
87  struct Symbol { short nBits; ushort code; };
88  int nextStat;
90 
91  void calcStat( int* groups );
92 
93  private:
94  static void _addGroup( int* groups, int group, int nBits );
95 };
96 
97 
98 //
99 // class LZHLEncoder
100 //
102 {
103  public:
104  LZHLEncoder( LZHLEncoderStat* stat, byte* dst );
105  ~LZHLEncoder();
106 
107  enum { maxMatchOver = 517, maxRaw = 64 };
108  static size_t calcMaxBuf( size_t rawSz );
109  size_t flush();
110  void putRaw( const byte* src, size_t sz );
111  void putMatch( const byte* src, size_t nRaw, size_t matchOver, size_t disp);
112 
113  private:
114  LZHLEncoderStat* _stat;
115  short* _sstat;
116  int& _nextStat;
117 
118  byte* _dst;
119  byte* _dstBegin;
120  uint _bits;
121  int _nBits;
122 
123  void _callStat();
124  void _put( ushort symbol );
125  void _put( ushort symbol, int codeBits, uint code );
126  void _putBits( int codeBits, uint code );
127 };
128 
129 
130 //
131 // class LZHLDecoderStat
132 //
134 {
135  public:
136  LZHLDecoderStat();
137  ~LZHLDecoderStat();
138 
139  struct Group { int nBits; int pos; };
140 
141  Group groupTable[ 16 ];
142 
143  short* symbolTable;
144 };
145 
146 
147 //----------------------------------------------------------------------
148 
149 inline
151  : _stat( stat ), _sstat( stat->stat ), _nextStat( stat->nextStat )
152 {
153  _dst = _dstBegin = dst;
154  _bits = 0;
155  _nBits = 0;
156 }
157 
158 
159 inline
161 {
162 }
163 
164 
165 inline
166 void LZHLEncoder::_putBits( int codeBits, uint code )
167 {
168  ASSERT( codeBits <= 16 );
169  _bits |= ( code << ( 32 - _nBits - codeBits ) );
170  _nBits += codeBits;
171  if ( _nBits >= 16 )
172  {
173  *_dst++ = (byte)( _bits >> 24 );
174  *_dst++ = (byte)( _bits >> 16 );
175  _nBits -= 16;
176  _bits <<= 16;
177  }
178 }
179 
180 
181 inline
182 void LZHLEncoder::_put( ushort symbol )
183 {
184  ASSERT( symbol < NHUFFSYMBOLS );
185  if ( --_nextStat <= 0 )
186  _callStat();
187 
188  ++_sstat[ symbol ];
189 
190  LZHLEncoderStat::Symbol* item = &_stat->symbolTable[ symbol ];
191  ASSERT( item->nBits >= 0 );
192 
193  _putBits( item->nBits, item->code );
194 }
195 
196 
197 inline
198 void LZHLEncoder::_put( ushort symbol, int codeBits, uint code )
199 {
200  ASSERT( symbol < NHUFFSYMBOLS );
201  ASSERT( codeBits <= 4 );
202  if ( --_nextStat <= 0 )
203  _callStat();
204 
205  ++_sstat[ symbol ];
206 
207  LZHLEncoderStat::Symbol* item = &_stat->symbolTable[ symbol ];
208  ASSERT( item->nBits >= 0 );
209 
210  int nBits = item->nBits;
211  _putBits( nBits + codeBits, ( item->code << codeBits ) | code );
212 }
213 
214 
215 #endif
~LZHLEncoder()
Definition: huffman.h:160
#define NHUFFSYMBOLS
Definition: huffman.h:44
short * stat
Definition: huffman.h:71
short * symbolTable
Definition: huffman.h:143
bool operator<(const HuffStatTmpStruct &x)
Definition: huffman.h:54
Symbol * symbolTable
Definition: huffman.h:89
unsigned int uint
LZHLEncoder(LZHLEncoderStat *stat, byte *dst)
Definition: huffman.h:150
uint8_t byte
#define AIMSALGO_API
#define ASSERT(EX)
unsigned short ushort