← Back to branch summary

~ubuntu-branches/ubuntu/lucid/kmess/lucid

« back to all changes in this revision

Viewing changes to contrib/isf-qt/src/data/algorithms/huffman.cpp

  • Committer: Bazaar Package Importer
  • Author(s): Mark Purcell
  • Date: 2009-12-05 21:19:26 UTC
  • mfrom: (1.1.7 upstream) (0.1.8 sid)
  • Revision ID: james.westby@ubuntu.com-20091205211926-r26u8j38kysf6o2p
Tags: 2.0.2-1
https://launchpad.net/bugs/485640
* New upstream release 
  - Fixes friendly names (LP: #485640)
* Update Homepage: http://kmess.org
* Add Build-Depends: libphonon-dev | libqt4-phonon-dev (ubuntu friendly)
* kmess.1 fix lintian:hyphen-used-as-minus-sign

Show diffs side-by-side

added added

removed removed

Lines of Context:
contrib/isf-qt/src/data/algorithms/huffman.cpp
 
1
/***************************************************************************
 
2
 *   Copyright (C) 2008 by Valerio Pilo                                    *
 
3
 *   valerio@kmess.org                                                     *
 
4
 *                                                                         *
 
5
 *   This program is free software; you can redistribute it and/or modify  *
 
6
 *   it under the terms of the GNU Lesser General Public License as        *
 
7
 *   published by the Free Software Foundation; either version 2.1 of the  *
 
8
 *   License, or (at your option) any later version.                       *
 
9
 *                                                                         *
 
10
 *   This program is distributed in the hope that it will be useful,       *
 
11
 *   but WITHOUT ANY WARRANTY; without even the implied warranty of        *
 
12
 *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the         *
 
13
 *   GNU General Public License for more details.                          *
 
14
 *                                                                         *
 
15
 *   You should have received a copy of the GNU Lesser General Public      *
 
16
 *   License along with this program; if not, write to the                 *
 
17
 *   Free Software Foundation, Inc.,                                       *
 
18
 *   59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.             *
 
19
 ***************************************************************************/
 
20
 
 
21
#include "huffman.h"
 
22
 
 
23
#include "isfqt-internal.h"
 
24
 
 
25
#include <math.h>
 
26
 
 
27
 
 
28
#define HUFFMAN_BASES_NUM   8
 
29
#define HUFFMAN_BASE_SIZE  11
 
30
 
 
31
 
 
32
using namespace Isf::Compress;
 
33
 
 
34
 
 
35
/// Bit amounts.
 
36
const int bitAmounts_[HUFFMAN_BASES_NUM][HUFFMAN_BASE_SIZE] =
 
37
{
 
38
    {0, 1, 2,  4,  6,  8, 12, 16, 24, 32, -1},
 
39
    {0, 1, 1,  2,  4,  8, 12, 16, 24, 32, -1},
 
40
    {0, 1, 1,  1,  2,  4,  8, 14, 22, 32, -1},
 
41
    {0, 2, 2,  3,  5,  8, 12, 16, 24, 32, -1},
 
42
    {0, 3, 4,  5,  8, 12, 16, 24, 32, -1, -1},
 
43
    {0, 4, 6,  8, 12, 16, 24, 32, -1, -1, -1},
 
44
    {0, 6, 8, 12, 16, 24, 32, -1, -1, -1, -1},
 
45
    {0, 7, 8, 12, 16, 24, 32, -1, -1, -1, -1},
 
46
};
 
47
 
 
48
 
 
49
/// Huffman codec value bases.
 
50
const int huffmanBases_[HUFFMAN_BASES_NUM][HUFFMAN_BASE_SIZE] =
 
51
{
 
52
    {0, 1,  2,   4,   12,    44,     172,    2220,   34988, 8423596, -1},
 
53
    {0, 1,  2,   3,    5,    13,     141,    2189,   34957, 8423565, -1},
 
54
    {0, 1,  2,   3,    4,     6,      14,     142,    8334, 2105486, -1},
 
55
    {0, 1,  3,   5,    9,    25,     153,    2201,   34969, 8423577, -1},
 
56
    {0, 1,  5,  13,   29,   157,    2205,   34973, 8423581,      -1, -1},
 
57
    {0, 1,  9,  41,  169,  2217,   34985, 8423593,      -1,      -1, -1},
 
58
    {0, 1, 33, 161, 2209, 34977, 8423585,      -1,      -1,      -1, -1},
 
59
    {0, 1, 65, 193, 2241, 35009, 8423617,      -1,      -1,      -1, -1},
 
60
};
 
61
 
 
62
 
 
63
 
 
64
/**
 
65
 * Get the most appropriate index for the given data.
 
66
 *
 
67
 * @param data Data to analyze
 
68
 * @return index value
 
69
 */
 
70
quint8 HuffmanAlgorithm::index( const QList<qint64> &data )
 
71
{
 
72
  quint8 index = 0;
 
73
 
 
74
  // TODO: Find out what the Huffman index algorithm is
 
75
  Q_UNUSED( data )
 
76
  index = 2;
 
77
 
 
78
  return index;
 
79
}
 
80
 
 
81
 
 
82
 
 
83
/**
 
84
 * Compress data with the Huffman algorithm.
 
85
 *
 
86
 * @param encodedData Byte array where to store the compressed data
 
87
 * @param index Index to use for compression
 
88
 * @param source List of values to compress
 
89
 * @return bool
 
90
 */
 
91
bool HuffmanAlgorithm::deflate( QByteArray &encodedData, quint8 index, const QList<qint64> &source )
 
92
{
 
93
  DataSource output( encodedData );
 
94
  output.skipToNextByte();
 
95
 
 
96
  foreach( quint64 value, source )
 
97
  {
 
98
    if( ! deflateValue( output, index, value ) )
 
99
    {
 
100
#ifdef ISFQT_DEBUG
 
101
      qDebug() << "Deflating failure for value:" << value;
 
102
#endif
 
103
      return false;
 
104
    }
 
105
  }
 
106
 
 
107
  // Flush any leftover bit to the byte array
 
108
  output.flush();
 
109
 
 
110
  encodedData = output.data();
 
111
  return true;
 
112
}
 
113
 
 
114
 
 
115
 
 
116
/**
 
117
 * Compress a single value with the Huffman algorithm.
 
118
 *
 
119
 * @param output Data source where to store the compressed value
 
120
 * @param index Index to use for compression
 
121
 * @param value Value to compress
 
122
 * @return bool
 
123
 */
 
124
bool HuffmanAlgorithm::deflateValue( DataSource &output, quint8 index, qint64 value )
 
125
{
 
126
  qint64 temp = value;
 
127
  quint8 requiredBits = 0;
 
128
  QBitArray valueBits;
 
129
 
 
130
  // Fill in a bitAmounts local vector
 
131
  QVector<int> bitAmounts;
 
132
  for( int i = 0; i < HUFFMAN_BASE_SIZE; ++i )
 
133
  {
 
134
    if( bitAmounts_[ index ][ i ] == -1 )
 
135
    {
 
136
      break;
 
137
    }
 
138
 
 
139
    bitAmounts.append( bitAmounts_[ index ][ i ] );
 
140
  }
 
141
 
 
142
  // Find the number of bits needed to store this value
 
143
  while( temp )
 
144
  {
 
145
    temp /= 2;
 
146
    ++requiredBits;
 
147
  }
 
148
 
 
149
  while( ! bitAmounts.count( requiredBits ) )
 
150
  {
 
151
    ++requiredBits;
 
152
  }
 
153
 
 
154
  qint64 offset = ( value < 0 ) ? -value : +value;
 
155
 
 
156
  quint8 prefixLength;
 
157
  for( prefixLength = 1;
 
158
        ( prefixLength < HUFFMAN_BASE_SIZE ) && ( offset >= huffmanBases_[ index ][ prefixLength ] ); prefixLength++ )
 
159
  {
 
160
    // Empty loop on purpose
 
161
  }
 
162
 
 
163
 
 
164
  // Write prefixLength 1s to the stream, then a 0
 
165
  QBitArray bits( prefixLength );
 
166
  bits.fill( true );
 
167
  bits.clearBit( bits.size() - 1 );
 
168
 
 
169
  // Write the number using the minimum possible number of bits
 
170
  qint32 size = bitAmounts_[ index ][ prefixLength - 1 ];
 
171
  qint64 mask = ( 1 << ( size - 1 ) ) - 1;
 
172
 
 
173
  valueBits.resize( size );
 
174
  offset = ( offset - huffmanBases_[ index ][ prefixLength - 1 ] ) & mask;
 
175
  offset <<= 1;
 
176
  offset |= ( value < 0 ) ? 1 : 0;
 
177
 
 
178
  // Copy the resulting offset
 
179
  for( qint64 i = 0; i < size; ++i )
 
180
  {
 
181
    valueBits.setBit( i, offset & ( 1 << ( size - i - 1 ) ) );
 
182
  }
 
183
 
 
184
  // Add the bits to the data source
 
185
  output.append( bits );
 
186
  output.append( valueBits );
 
187
 
 
188
  return true;
 
189
}
 
190
 
 
191
 
 
192
 
 
193
/**
 
194
 * Decompress data with the Huffman algorithm.
 
195
 *
 
196
 * @param source Data source where to read the compressed bytes
 
197
 * @param length Number of items to read
 
198
 * @param index Index to use for compression
 
199
 * @param decodedData List where to place decompressed values
 
200
 * @return bool
 
201
 */
 
202
bool HuffmanAlgorithm::inflate( DataSource &source, quint64 length, quint8 index, QList<qint64> &decodedData )
 
203
{
 
204
  QVector<int> huffmanBases;
 
205
  QVector<int> bitAmounts( HUFFMAN_BASE_SIZE );
 
206
 
 
207
  // Initialize the bit amounts vector
 
208
  memcpy( bitAmounts.data(), bitAmounts_[ index ], sizeof(int)*HUFFMAN_BASE_SIZE );
 
209
 
 
210
  int base = 1;
 
211
  huffmanBases.append( 0 );
 
212
 
 
213
  // Fill up the huffman bases vector
 
214
  for( quint8 i = 0; i < bitAmounts.size(); ++i )
 
215
  {
 
216
    int value = bitAmounts[ i ];
 
217
 
 
218
    // The bit amounts sequence ends in -1
 
219
    if( value == -1 )
 
220
    {
 
221
      bitAmounts.resize( i );
 
222
      break;
 
223
    }
 
224
 
 
225
    if( value == 0 )
 
226
    {
 
227
      continue;
 
228
    }
 
229
 
 
230
    huffmanBases.append( base );
 
231
    base += pow( 2, value - 1 );
 
232
  }
 
233
 
 
234
 
 
235
  quint32 count = 0;
 
236
  qint64 value = 0;
 
237
  bool bit;
 
238
 
 
239
  while( (uint)decodedData.length() < length )
 
240
  {
 
241
    bit = source.getBit();
 
242
 
 
243
    if( bit )
 
244
    {
 
245
      count++;
 
246
      continue;
 
247
    }
 
248
 
 
249
    if( count == 0 )
 
250
    {
 
251
      value = 0;
 
252
    }
 
253
    else if( count < (uint)bitAmounts.size() )
 
254
    {
 
255
      quint64 offset = source.getBits( bitAmounts[ count ] );
 
256
      bool sign = offset & 0x1;
 
257
      offset /= 2;
 
258
      value = huffmanBases[ count ] + offset;
 
259
      value *= ( sign ? -1 : +1 );
 
260
    }
 
261
    else if( count == (uint)bitAmounts.size() )
 
262
    {
 
263
      // TODO: Implement 64-bit data decompression :)
 
264
#ifdef ISFQT_DEBUG
 
265
      qDebug() << "Unsupported 64-bit value found!";
 
266
#endif
 
267
      value = 0;
 
268
    }
 
269
    else
 
270
    {
 
271
#ifdef ISFQT_DEBUG
 
272
      qDebug() << "Decompression error!";
 
273
#endif
 
274
      value = 0;
 
275
    }
 
276
 
 
277
    decodedData.append( value );
 
278
    count = 0;
 
279
  }
 
280
 
 
281
  return true;
 
282
}
 
283
 
 
284