← 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/bitpacking.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/bitpacking.cpp
 
1
/***************************************************************************
 
2
 *   Copyright (C) 2008-2009 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 "isfqt-internal.h"
 
22
#include "bitpacking.h"
 
23
 
 
24
#include <math.h>
 
25
 
 
26
#include <QDebug>
 
27
 
 
28
 
 
29
using namespace Isf::Compress;
 
30
 
 
31
 
 
32
 
 
33
/**
 
34
 * Get the most appropriate block size for the given data.
 
35
 *
 
36
 * @param data Data to analyze
 
37
 * @return Block size
 
38
 */
 
39
quint8 BitPackingAlgorithm::blockSize( const QList<qint64> &data )
 
40
{
 
41
  quint8 blockSize = 0;
 
42
  qint64 num;
 
43
 
 
44
  for( qint32 index = 0; index < data.size(); ++index )
 
45
  {
 
46
    num = data[ index ];
 
47
 
 
48
    if( num < 0 )
 
49
    {
 
50
      // We need the positive numbers: the +1 is for the sign bit
 
51
      num += - (num + 1);
 
52
    }
 
53
 
 
54
    // Shift right the value by blockSize bits until it becomes zero:
 
55
    // we need to detect the maximum bitwise size required to store
 
56
    // the numbers in the data array.
 
57
    num >>= blockSize;
 
58
    while( num )
 
59
    {
 
60
      ++blockSize;
 
61
      num >>= 1;
 
62
    }
 
63
  }
 
64
 
 
65
  // The sign bit always takes up a bit
 
66
  ++blockSize;
 
67
 
 
68
  return blockSize;
 
69
}
 
70
 
 
71
 
 
72
 
 
73
/**
 
74
 * Compress data with the Bit Packing algorithm.
 
75
 *
 
76
 * @param encodedData Byte array where to store the compressed data
 
77
 * @param blockSize Block size to use for compression
 
78
 * @param source List of values to compress
 
79
 * @return bool
 
80
 */
 
81
bool BitPackingAlgorithm::deflate( QByteArray &encodedData, quint8 blockSize, const QList<qint64> &source )
 
82
{
 
83
  if( blockSize > 64 )
 
84
  {
 
85
    qWarning() << "A block size of" << blockSize << "is too high!";
 
86
    blockSize = 64; // Fuck it :P
 
87
  }
 
88
 
 
89
  quint8 blockSizeLeft; // Remaining bits to encode of the current value
 
90
  quint8 freeBits = 8;  // Free bits of the current byte, in LSB order
 
91
  quint8 signMask = 1 << ( blockSize - 1 );  // Mask to add the sign bit
 
92
 
 
93
  quint8 byte = 0;          // Byte to add to the array
 
94
  qint64 currentValue;
 
95
 
 
96
  for( qint64 index = 0; index < source.count(); ++index )
 
97
  {
 
98
    currentValue = source[ index ];
 
99
 
 
100
    if( currentValue < 0 )
 
101
    {
 
102
      currentValue |= signMask;
 
103
    }
 
104
 
 
105
    blockSizeLeft = blockSize;
 
106
 
 
107
    if( freeBits >= blockSizeLeft )
 
108
    {
 
109
      freeBits -= blockSizeLeft;
 
110
      byte |= currentValue << freeBits;
 
111
 
 
112
      encodedData.append( byte );
 
113
 
 
114
      byte = 0;
 
115
      freeBits = 8;
 
116
    }
 
117
    else
 
118
    {
 
119
      // Fill the current byte
 
120
      quint64 mask = 0xFFFFFFFF >> ( 32 - blockSizeLeft );
 
121
      byte |= currentValue >> ( blockSizeLeft - freeBits );
 
122
 
 
123
      encodedData.append( byte );
 
124
 
 
125
      byte = 0;
 
126
      blockSizeLeft -= freeBits;
 
127
      mask >>= freeBits;
 
128
      currentValue &= mask;
 
129
 
 
130
      // Then fill all the next bytes required to encode the current value,
 
131
      // except the last one
 
132
      while( blockSizeLeft > 8 )
 
133
      {
 
134
        blockSizeLeft -= 8;
 
135
        encodedData.append( currentValue >> blockSizeLeft );
 
136
 
 
137
        mask >>= 8;
 
138
        currentValue &= mask;
 
139
      }
 
140
 
 
141
      // Finally, add the last byte
 
142
      freeBits = 8 - blockSizeLeft;
 
143
      encodedData.append( currentValue << freeBits );
 
144
    }
 
145
  }
 
146
 
 
147
  return true;
 
148
}
 
149
 
 
150
 
 
151
 
 
152
/**
 
153
 * Decompress data with the Bit Packing algorithm.
 
154
 *
 
155
 * @param source Data source where to read the compressed bytes
 
156
 * @param length Number of items to read
 
157
 * @param blockSize Block size to use for compression
 
158
 * @param decodedData List where to place decompressed values
 
159
 * @return bool
 
160
 */
 
161
bool BitPackingAlgorithm::inflate( DataSource &source, quint64 length, quint8 blockSize, QList<qint64> &decodedData )
 
162
{
 
163
  if( blockSize > 64 )
 
164
  {
 
165
    qWarning() << "A block size of" << blockSize << "is too high!";
 
166
    blockSize = 64; // Fuck it :P
 
167
  }
 
168
 
 
169
  if( source.atEnd() )
 
170
  {
 
171
    qWarning() << "Cannot inflate: no more bits available!";
 
172
    return true;
 
173
  }
 
174
 
 
175
  qint64  value;
 
176
  quint32 index    = 0;
 
177
  quint64 signMask = (quint64)( 0xFFFFFFFF * pow( 2, blockSize - 1 ) ) & 0xFFFFFFFF;
 
178
 
 
179
  while( index++ < length )
 
180
  {
 
181
    value = source.getBits( blockSize );
 
182
 
 
183
    // If the mask matches, the sign bit is set, so ORing value and mask will
 
184
    // set all leftmost bits to 1, making it a real 64bit signed integer
 
185
    if( value & signMask )
 
186
    {
 
187
      value |= signMask;
 
188
    }
 
189
 
 
190
    decodedData.append( value );
 
191
  }
 
192
 
 
193
  return true;
 
194
}
 
195
 
 
196