Menu
▾
▴
[KMess-commits] SF.net SVN: kmess:[5379] trunk/kmess/contrib/isf-qt
|
From: <it_...@us...> - 2009-08-29 22:36:31
|
Revision: 5379
http://kmess.svn.sourceforge.net/kmess/?rev=5379&view=rev
Author: it_amroth
Date: 2009-08-29 22:36:22 +0000 (Sat, 29 Aug 2009)
Log Message:
-----------
isf-qt:
* Rewritten the algorithm detection methods.
* Changed the names of some internal data classes, and improved their namespaces.
* Added a maximum drawing size check, to avoid errors from resulting in 80k by 70k pixel wide
drawings.
Modified Paths:
--------------
trunk/kmess/contrib/isf-qt/ChangeLog
trunk/kmess/contrib/isf-qt/src/CMakeLists.txt
trunk/kmess/contrib/isf-qt/src/data/compression.cpp
trunk/kmess/contrib/isf-qt/src/data/compression.h
trunk/kmess/contrib/isf-qt/src/data/huffman.cpp
trunk/kmess/contrib/isf-qt/src/data/huffman.h
trunk/kmess/contrib/isf-qt/src/isfqtdrawing.cpp
trunk/kmess/contrib/isf-qt/src/tagswriter.cpp
Added Paths:
-----------
trunk/kmess/contrib/isf-qt/src/data/bitpacking.cpp
trunk/kmess/contrib/isf-qt/src/data/bitpacking.h
trunk/kmess/contrib/isf-qt/src/data/deltatransform.cpp
trunk/kmess/contrib/isf-qt/src/data/deltatransform.h
trunk/kmess/contrib/isf-qt/tests/signature.isf
Removed Paths:
-------------
trunk/kmess/contrib/isf-qt/src/data/gorilla.cpp
trunk/kmess/contrib/isf-qt/src/data/gorilla.h
Modified: trunk/kmess/contrib/isf-qt/ChangeLog
===================================================================
--- trunk/kmess/contrib/isf-qt/ChangeLog 2009-08-29 20:49:14 UTC (rev 5378)
+++ trunk/kmess/contrib/isf-qt/ChangeLog 2009-08-29 22:36:22 UTC (rev 5379)
@@ -1,4 +1,10 @@
+2009-08-30 (Valerio)
+ * Rewritten the algorithm detection methods.
+ * Changed the names of some internal data classes, and improved their namespaces.
+ * Added a maximum drawing size check, to avoid errors from resulting in 80k by 70k pixel wide
+ drawings.
+
2009-08-29 (Valerio)
* Fixed skipping unknown custom tags contents.
* Changed more method names to adhere to Qt's method naming style.
Modified: trunk/kmess/contrib/isf-qt/src/CMakeLists.txt
===================================================================
--- trunk/kmess/contrib/isf-qt/src/CMakeLists.txt 2009-08-29 20:49:14 UTC (rev 5378)
+++ trunk/kmess/contrib/isf-qt/src/CMakeLists.txt 2009-08-29 22:36:22 UTC (rev 5379)
@@ -3,7 +3,8 @@
SET( ISFQT_SOURCES
data/compression.cpp
- data/gorilla.cpp
+ data/deltatransform.cpp
+ data/bitpacking.cpp
data/huffman.cpp
data/datasource.cpp
data/multibytecoding.cpp
Copied: trunk/kmess/contrib/isf-qt/src/data/bitpacking.cpp (from rev 5377, trunk/kmess/contrib/isf-qt/src/data/gorilla.cpp)
===================================================================
--- trunk/kmess/contrib/isf-qt/src/data/bitpacking.cpp (rev 0)
+++ trunk/kmess/contrib/isf-qt/src/data/bitpacking.cpp 2009-08-29 22:36:22 UTC (rev 5379)
@@ -0,0 +1,176 @@
+/***************************************************************************
+ * Copyright (C) 2008-2009 by Valerio Pilo *
+ * va...@km... *
+ * *
+ * This program is free software; you can redistribute it and/or modify *
+ * it under the terms of the GNU Lesser General Public License as *
+ * published by the Free Software Foundation; either version 2.1 of the *
+ * License, or (at your option) any later version. *
+ * *
+ * This program is distributed in the hope that it will be useful, *
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of *
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the *
+ * GNU General Public License for more details. *
+ * *
+ * You should have received a copy of the GNU Lesser General Public *
+ * License along with this program; if not, write to the *
+ * Free Software Foundation, Inc., *
+ * 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. *
+ ***************************************************************************/
+
+#include "isfqt-internal.h"
+#include "bitpacking.h"
+
+#include <math.h>
+
+#include <QDebug>
+
+
+using namespace Isf::Compress;
+
+
+
+// Get the most appropriate block size for the given data
+quint8 BitPackingAlgorithm::blockSize( const QList<qint64> &data )
+{
+ quint8 blockSize = 0;
+ qint64 num;
+
+ for( qint32 index = 0; index < data.size(); ++index )
+ {
+ num = data[ index ];
+
+ if( num < 0 )
+ {
+ // We need the positive numbers: the +1 is for the sign bit
+ num += - (num + 1);
+ }
+
+ // Shift right the value by blockSize bits until it becomes zero:
+ // we need to detect the maximum bitwise size required to store
+ // the numbers in the data array.
+ num >>= blockSize;
+ while( num )
+ {
+ ++blockSize;
+ num >>= 1;
+ }
+ }
+
+ // The sign bit always takes up a bit
+ ++blockSize;
+
+ return blockSize;
+}
+
+
+
+// Compress data
+bool BitPackingAlgorithm::deflate( QByteArray &encodedData, quint8 blockSize, const QList<qint64> &source )
+{
+ if( blockSize > 64 )
+ {
+ qWarning() << "A block size of" << blockSize << "is too high!";
+ blockSize = 64; // Fuck it :P
+ }
+
+ quint8 blockSizeLeft; // Remaining bits to encode of the current value
+ quint8 freeBits = 8; // Free bits of the current byte, in LSB order
+ quint8 signMask = 1 << ( blockSize - 1 ); // Mask to add the sign bit
+
+ quint8 byte = 0; // Byte to add to the array
+ qint64 currentValue;
+
+ for( qint64 index = 0; index < source.count(); ++index )
+ {
+ currentValue = source[ index ];
+
+ if( currentValue < 0 )
+ {
+ currentValue |= signMask;
+ }
+
+ blockSizeLeft = blockSize;
+
+ if( freeBits >= blockSizeLeft )
+ {
+ freeBits -= blockSizeLeft;
+ byte |= currentValue << freeBits;
+
+ encodedData.append( byte );
+
+ byte = 0;
+ freeBits = 8;
+ }
+ else
+ {
+ // Fill the current byte
+ quint64 mask = 0xFFFFFFFF >> ( 32 - blockSizeLeft );
+ byte |= currentValue >> ( blockSizeLeft - freeBits );
+
+ encodedData.append( byte );
+
+ byte = 0;
+ blockSizeLeft -= freeBits;
+ mask >>= freeBits;
+ currentValue &= mask;
+
+ // Then fill all the next bytes required to encode the current value,
+ // except the last one
+ while( blockSizeLeft > 8 )
+ {
+ blockSizeLeft -= 8;
+ encodedData.append( currentValue >> blockSizeLeft );
+
+ mask >>= 8;
+ currentValue &= mask;
+ }
+
+ // Finally, add the last byte
+ freeBits = 8 - blockSizeLeft;
+ encodedData.append( currentValue << freeBits );
+ }
+ }
+
+ return true;
+}
+
+
+
+// Decompress data
+bool BitPackingAlgorithm::inflate( DataSource &source, quint64 length, quint8 blockSize, QList<qint64> &decodedData )
+{
+ if( blockSize > 64 )
+ {
+ qWarning() << "A block size of" << blockSize << "is too high!";
+ blockSize = 64; // Fuck it :P
+ }
+
+ if( source.atEnd() )
+ {
+ qWarning() << "Cannot inflate: no more bits available!";
+ return true;
+ }
+
+ qint64 value;
+ quint32 index = 0;
+ quint64 signMask = (quint64)( 0xFFFFFFFF * pow( 2, blockSize - 1 ) ) & 0xFFFFFFFF;
+
+ while( index++ < length )
+ {
+ value = source.getBits( blockSize );
+
+ // If the mask matches, the sign bit is set, so ORing value and mask will
+ // set all leftmost bits to 1, making it a real 64bit signed integer
+ if( value & signMask )
+ {
+ value |= signMask;
+ }
+
+ decodedData.append( value );
+ }
+
+ return true;
+}
+
+
Copied: trunk/kmess/contrib/isf-qt/src/data/bitpacking.h (from rev 5377, trunk/kmess/contrib/isf-qt/src/data/gorilla.h)
===================================================================
--- trunk/kmess/contrib/isf-qt/src/data/bitpacking.h (rev 0)
+++ trunk/kmess/contrib/isf-qt/src/data/bitpacking.h 2009-08-29 22:36:22 UTC (rev 5379)
@@ -0,0 +1,48 @@
+/***************************************************************************
+ * Copyright (C) 2008 by Valerio Pilo *
+ * va...@km... *
+ * *
+ * This program is free software; you can redistribute it and/or modify *
+ * it under the terms of the GNU Lesser General Public License as *
+ * published by the Free Software Foundation; either version 2.1 of the *
+ * License, or (at your option) any later version. *
+ * *
+ * This program is distributed in the hope that it will be useful, *
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of *
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the *
+ * GNU General Public License for more details. *
+ * *
+ * You should have received a copy of the GNU Lesser General Public *
+ * License along with this program; if not, write to the *
+ * Free Software Foundation, Inc., *
+ * 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. *
+ ***************************************************************************/
+
+#ifndef ISFCOMPRESSION_BITPACKING_H
+#define ISFCOMPRESSION_BITPACKING_H
+
+#include "datasource.h"
+
+
+
+namespace Isf
+{
+ namespace Compress
+ {
+ namespace BitPackingAlgorithm
+ {
+
+ /// Get the most appropriate block size for the given data
+ quint8 blockSize( const QList<qint64> &data );
+ /// Compress data
+ bool deflate( QByteArray &encodedData, quint8 blockSize, const QList<qint64> &source );
+ /// Decompress data
+ bool inflate( DataSource &source, quint64 length, quint8 blockSize, QList<qint64> &decodedData );
+
+ }
+ }
+}
+
+
+
+#endif
Modified: trunk/kmess/contrib/isf-qt/src/data/compression.cpp
===================================================================
--- trunk/kmess/contrib/isf-qt/src/data/compression.cpp 2009-08-29 20:49:14 UTC (rev 5378)
+++ trunk/kmess/contrib/isf-qt/src/data/compression.cpp 2009-08-29 22:36:22 UTC (rev 5379)
@@ -21,154 +21,351 @@
#include "compression.h"
#include "isfqt-internal.h"
-#include "gorilla.h"
+#include "bitpacking.h"
#include "huffman.h"
+#include "deltatransform.h"
+using namespace Isf;
-namespace Isf
+
+
+// Decompress packet data autodetecting the algorithm to use
+bool Compress::inflatePacketData( DataSource &source, quint64 length, QList<qint64> &decodedData )
{
- namespace Compress
+ if( source.atEnd() )
{
+#ifdef ISFQT_DEBUG
+ qWarning() << "Source was at end!";
+#endif
+ return false;
+ }
+ bool result;
+ uchar byte = source.getByte();
+ qint16 algorithm = ( byte & AlgorithmMask );
+ quint8 algorithmData = 0;
+ // Detect which algorithm to use
- // Decompress data autodetecting the algorithm to use
- bool inflate( DataSource &source, quint64 length, QList<qint64> &decodedData )
+ // Use the "best compression" algorithm
+ if( ( algorithm & BestCompression ) == BestCompression )
+ {
+ /* TODO: Not implemented yet. We don't know how ISF actually works here.
+ * According to the specs, both bit packing and Huffman may be used; but
+ * where are the rest of the bits stored? In the next byte?
+ * We need an ISF stream with such a characteristic to be sure.
+ */
+ qWarning() << "Unknown decompression method!";
+ qDebug() << "[Information - type: best, byte:" << QString::number( source.getByte(), 16 ) << "hex]";
+ return false;
+ }
+ // Use the "default compression" algorithm, which is Huffman
+ else if( ( algorithm & DefaultCompression ) == DefaultCompression
+ || ( algorithm & Huffman ) == Huffman )
+ {
+ algorithm = Huffman;
+ algorithmData = ( HuffmanMask & byte );
+ }
+ // According to the specs, the only other algorithm for packet data
+ // is generic bit packing.
+ else if( algorithm == BitPacking )
+ {
+ algorithm = BitPacking;
+ algorithmData = ( BitPackingMask & byte );
+ }
+ else
+ {
+ // Unknown algorithm. Throw an error below.
+ algorithm = -1;
+ }
+
+ // Apply the inflation algorithm
+
+ switch( algorithm )
+ {
+ case BitPacking:
{
- if( source.atEnd() )
- {
-#ifdef ISFQT_DEBUG
- qWarning() << "Source was at end!";
+ // Detect if the data is encoded with delta-delta transformation
+ bool requiresDeltaDeltaTransform = ( BitPackingTransformMask & byte );
+ algorithmData ^= BitPackingTransformMask;
+
+#ifdef ISFQT_DEBUG_VERBOSE
+ qDebug() << "- Inflating" << length << "items using the Bit Packing algorithm and a block size of" << algorithmData;
#endif
- return false;
- }
- bool result;
- uchar byte = source.getByte();
- uchar algorithm = ( byte & MaskByte );
- uchar needsTransform = ( byte & TransformationFlag );
- quint8 blockSize = ( byte & BlockSizeFlag );
+ result = BitPackingAlgorithm::inflate( source, length, algorithmData, decodedData );
- if( blockSize == 0 )
+ if( result && requiresDeltaDeltaTransform )
{
-#ifdef ISFQT_DEBUG
- qWarning() << "Block size invalid, was reset to 32";
-#endif
- blockSize = 32;
+ result = Delta::inverseTransform( decodedData );
}
+ break;
+ }
+ case Huffman:
+ {
+#ifdef ISFQT_DEBUG_VERBOSE
+ qDebug() << "- Inflating" << length << "items using the Huffman algorithm and index" << algorithmData;
+#endif
+ result = HuffmanAlgorithm::inflate( source, length, algorithmData, decodedData );
- switch( algorithm )
+ // Always delta-inverse-transform data compressed with Huffman
+ if( result )
{
- case Gorilla:
- if( needsTransform )
- {
-#ifdef ISFQT_DEBUG
- qWarning() << "Gorilla transformation is required, aborting!";
-#endif
- return false;
- }
+ result = Delta::inverseTransform( decodedData );
+ }
+ break;
+ }
+ default:
+ qWarning() << "Unknown decompression method!";
+ qDebug() << "[Information - type: unknown, byte:" << QString::number( byte, 16 ) << "hex]";
+
+ // Go back to the previous read position
+ source.seekRelative( -1 );
+
+ break;
+ }
+
+ // Discard any partially read bytes
+ if( ! source.atEnd() )
+ {
+ source.skipToNextByte();
+ }
+
+ return result;
+}
+
+
+
+// Compress packet data autodetecting the algorithm to use
+bool Compress::deflatePacketData( QByteArray &encodedData, const QList<qint64> &source )
+{
+ bool result;
+
+ // TODO Is this really how to detect the algorithm to use?
+ int algorithm;
+ if( source.count() == 1 )
+ {
+ algorithm = BitPacking;
+ }
+ else
+ {
+ algorithm = Huffman;
+ }
+
+
+ switch( algorithm )
+ {
+ case BitPacking:
+ {
+ quint8 blockSize = BitPackingAlgorithm::blockSize( source );
+
+ // Write the data encoding algorithm and block size
+ encodedData.append( blockSize | BitPacking );
+
#ifdef ISFQT_DEBUG_VERBOSE
- qDebug() << "- Inflating" << length << "items using the Gorilla algorithm and a block size of" << blockSize;
+ qDebug() << "- Deflating" << source.count() << "items using the bit packing algorithm and a block size of" << blockSize;
#endif
- result = inflateGorilla( source, length, blockSize, decodedData );
- break;
+ // Deflate the data
+ result = BitPackingAlgorithm::deflate( encodedData, blockSize, source );
+ break;
+ }
- case Huffman:
+
+ case Huffman:
+ {
+ quint8 index = HuffmanAlgorithm::index( source );
+
+ // Write the data encoding algorithm and index
+ encodedData.append( index | Huffman );
+
#ifdef ISFQT_DEBUG_VERBOSE
- qDebug() << "- Inflating" << length << "items using the Huffman algorithm and index" << blockSize;
+ qDebug() << "- Deflating" << source.count() << "items using the Huffman algorithm and index" << index;
#endif
- result = inflateHuffman( source, length, blockSize, decodedData );
- break;
- default:
-#ifdef ISFQT_DEBUG
- qDebug() << "Decoding algorithm not recognized! (byte:" << QString::number( algorithm, 2 ) << ")";
-#endif
- // Go back to the previous read position
- source.seekRelative( -1 );
- return false;
- }
+ // Deflate the data
+ QList<qint64> list( source );
+ result = Delta::transform( list );
- // Discard any partially read bytes
- if( ! source.atEnd() )
+ if( result )
{
- source.skipToNextByte();
+ result = HuffmanAlgorithm::deflate( encodedData, index, list );
}
-
- return result;
+ break;
}
+ default:
+#ifdef ISFQT_DEBUG
+ qDebug() << "Encoding algorithm not implemented! (algorithm:" << QString::number( algorithm, 16 ) << ")";
+#endif
+ break;
+ }
- // Compress data autodetecting the algorithm to use
- bool deflate( QByteArray &encodedData, const QList<qint64> &source, DataType dataType )
- {
- bool result;
+ return result;
+}
- // TODO Is this really how to detect the algorithm to use?
- Algorithm algorithm;
- if( source.count() == 1 )
- {
- algorithm = Gorilla;
- }
- else
- {
- algorithm = Huffman;
- }
- switch( algorithm )
- {
- case Gorilla:
- {
- quint8 blockSize = getBlockSizeGorilla( source );
+// Decompress property data autodetecting the algorithm to use
+bool Compress::inflatePropertyData( DataSource &source, quint64 length, QList<qint64> &decodedData )
+{
+ if( source.atEnd() )
+ {
+#ifdef ISFQT_DEBUG
+ qWarning() << "Source was at end!";
+#endif
+ return false;
+ }
- // Write the data encoding algorithm and block size
- encodedData.append( blockSize | Gorilla );
+ bool result;
+ uchar byte = source.getByte();
+ qint16 algorithm = ( byte & AlgorithmMask );
+ quint8 algorithmData = 0;
+ // Detect which algorithm to use
+
+ // Use the "default compression" algorithm
+ if( ( algorithm & DefaultCompression ) == DefaultCompression )
+ {
+ /* TODO: Not implemented yet. We don't know how ISF actually works here.
+ * According to the specs, any of the 3 bit packing techniques may be used;
+ * but where are the rest of the bits stored? In the next byte?
+ * We need an ISF stream with such a characteristic to be sure.
+ */
+ qWarning() << "Unknown decompression method!";
+ qDebug() << "[Information - type: default, byte:" << QString::number( source.getByte(), 16 ) << "hex]";
+ return false;
+ }
+ // Use the "best compression" algorithm, which is Huffman
+ else if( ( algorithm & BestCompression ) == BestCompression
+ || ( algorithm & Huffman ) == Huffman )
+ {
+ algorithm = Huffman;
+ algorithmData = ( HuffmanMask & byte );
+ }
+ else if( ( algorithm & LimpelZiv ) == LimpelZiv )
+ {
+ algorithm = LimpelZiv;
+ }
+ else if( ( algorithm & BitPackingByte ) == BitPackingByte )
+ {
+ algorithm = BitPackingByte;
+ algorithmData = ( BitPackingByteMask & byte );
+ }
+ else if( ( algorithm & BitPackingWord ) == BitPackingWord )
+ {
+ algorithm = BitPackingWord;
+ algorithmData = ( BitPackingWordMask & byte );
+ }
+ else if( ( algorithm & BitPackingLong ) == BitPackingLong )
+ {
+ algorithm = BitPackingLong;
+ algorithmData = ( BitPackingLongMask & byte );
+ }
+ else
+ {
+ // Unknown algorithm. Throw an error below.
+ algorithm = -1;
+ }
+
+ // Apply the deflation algorithm
+
+ switch( algorithm )
+ {
+ case BitPackingByte:
+ {
#ifdef ISFQT_DEBUG_VERBOSE
- qDebug() << "- Deflating" << source.count() << "items using the Gorilla algorithm and a block size of" << blockSize;
+ qDebug() << "- Inflating" << length << "items using the Bit Packing Byte algorithm and a block size of" << algorithmData;
#endif
- // Deflate the data
- result = deflateGorilla( encodedData, blockSize, source );
- break;
- }
+ qWarning() << "Stream data is compressed with non implemented algorithm!";
+ qDebug() << "[Information - algorithm: Bit Packing Byte]";
+ return false;
+ }
+ case BitPackingWord:
+ {
+#ifdef ISFQT_DEBUG_VERBOSE
+ qDebug() << "- Inflating" << length << "items using the Bit Packing Word algorithm and a block size of" << algorithmData;
+#endif
- case Huffman:
- {
- quint8 index = getIndexHuffman( source );
+ qWarning() << "Stream data is compressed with non implemented algorithm!";
+ qDebug() << "[Information - algorithm: Bit Packing Word]";
+ return false;
+ }
- // Write the data encoding algorithm and index
- encodedData.append( index | Huffman );
+ case BitPackingLong:
+ {
+#ifdef ISFQT_DEBUG_VERBOSE
+ qDebug() << "- Inflating" << length << "items using the Bit Packing Long algorithm and a block size of" << algorithmData;
+#endif
+ qWarning() << "Stream data is compressed with non implemented algorithm!";
+ qDebug() << "[Information - algorithm: Bit Packing Long]";
+ return false;
+ }
+
+ case LimpelZiv:
+ {
#ifdef ISFQT_DEBUG_VERBOSE
- qDebug() << "- Deflating" << source.count() << "items using the Huffman algorithm and index" << index;
+ qDebug() << "- Inflating" << length << "items using the Limpel-Ziv algorithm and a block size of" << algorithmData;
#endif
- // Deflate the data
- result = deflateHuffman( encodedData, index, source );
- break;
- }
+ qWarning() << "Stream data is compressed with non implemented algorithm!";
+ qDebug() << "[Information - algorithm: Limpel-Ziv]";
+ return false;
+ }
+ case Huffman:
+ {
+#ifdef ISFQT_DEBUG_VERBOSE
+ qDebug() << "- Inflating" << length << "items using the Huffman algorithm and index" << algorithmData;
+#endif
+ result = HuffmanAlgorithm::inflate( source, length, algorithmData, decodedData );
- default:
-#ifdef ISFQT_DEBUG
- qDebug() << "Encoding algorithm not implemented! (data type:" << dataType
- << ", algorithm:" << QString::number( algorithm, 16 ) << ")";
-#endif
- break;
+ // Always delta-inverse-transform data compressed with Huffman
+ if( result )
+ {
+ result = Delta::inverseTransform( decodedData );
}
-
- return result;
+ break;
}
+ default:
+ qWarning() << "Unknown decompression method!";
+ qDebug() << "[Information - type: unknown, byte:" << QString::number( byte, 16 ) << "hex]";
+ // Go back to the previous read position
+ source.seekRelative( -1 );
+ break;
}
-};
+
+ // Discard any partially read bytes
+ if( ! source.atEnd() )
+ {
+ source.skipToNextByte();
+ }
+
+ return result;
+}
+
+
+
+// Compress property data autodetecting the algorithm to use
+bool Compress::deflatePropertyData( QByteArray &encodedData, const QList<qint64> &source )
+{
+ bool result = false;
+
+ // TODO Everything here.
+
+ qWarning() << "Property data saving is not implemented at the moment!";
+
+ return result;
+}
+
+
Modified: trunk/kmess/contrib/isf-qt/src/data/compression.h
===================================================================
--- trunk/kmess/contrib/isf-qt/src/data/compression.h 2009-08-29 20:49:14 UTC (rev 5378)
+++ trunk/kmess/contrib/isf-qt/src/data/compression.h 2009-08-29 22:36:22 UTC (rev 5379)
@@ -27,50 +27,88 @@
namespace Isf
{
- /**
- * Available compression and decompressions algorithms
- */
- enum Algorithm
+ namespace Compress
{
- MaskByte = 0xC0 /// Mask byte used to identify the used algorithm
- , Huffman = 0x80 /// Adaptive Huffman compression
- , Gorilla = 0x00 /// Gorilla compression
- };
+ /**
+ * Algorithm extra data masks.
+ *
+ * These masks are used to obtain the least significant bits which
+ * are useful for the specific algorithm. If an algo takes no
+ * useful bits, the mask is 0.
+ */
+ enum AlgorithmMasks
+ {
+ AlgorithmMask = 0xF0 /// Mask used to identify the algorithms
+ , BitPackingMask = 0x3F /// Mask for bit packing of arbitrary-sized integers
+ , BitPackingTransformMask = 0x20 /// Mask for delta-delta transformed bit packed data
+ , HuffmanMask = 0x3F /// Mask for Huffman
+ , BitPackingLongMask = 0x3F /// Mask for bit packing of 32bit signed integers
+ , BitPackingWordMask = 0x1F /// Mask for bit packing of 16bit unsigned integers
+ , BitPackingByteMask = 0x1F /// Mask for bit packing of 8bit unsigned integers
+ , LimpelZivMask = 0x00 /// Mask for Limpel-Ziv
+ , BestCompressionMask = 0x00 /// Mask for the best compression algo
+ , DefaultCompressionMask = 0x00 /// Mask for the default compression algo
+ };
+ /**
+ * Compression and decompressions algorithms.
+ *
+ * Bit assignment table for packets (strokes):
+ * ---------------------------
+ * | Algorithm | 7 6 5 4 3 2 1 0 (Bit assignment) |
+ * Bit packing 0 0 D D D D D D
+ * Huffman 1 0 D D D D D D
+ * Default compression 1 1 0 0 X X X X
+ * Best compression 1 1 1 1 X X X X
+ *
+ * Bit assignment table for properties (tags):
+ * ---------------------------
+ * | Algorithm | 7 6 5 4 3 2 1 0 (Bit assignment) |
+ * Bit packing of bytes 0 0 0 D D D D D
+ * Bit packing of words 0 0 1 D D D D D
+ * Bit packing of longs 0 1 D D D D D D
+ * Limpel-Ziv 1 0 1 0 X X X X
+ * Default compression 1 1 0 0 X X X X
+ * Best compression 1 1 1 1 X X X X
+ *
+ * D = Algorithm-specific data
+ * X = Ignored bit
+ *
+ * We use the two most significant bits to identify the algorithms,
+ * because they are guaranteed to not contain algorithm data.
+ *
+ * Also, note that these tables are not identical to the ones in the
+ * specs: we changed them because they differ from our factual
+ * observations (in the specs Huffman is missing, for example).
+ */
+ enum CommonDataAlgorithms
+ {
+ BestCompression = 0xF0 /// Best compression algorithm
+ , DefaultCompression = 0xC0 /// Default compression algorithm (Huffman)
+ , Huffman = 0x80 /// Huffman encoding
+ };
+ enum PacketDataAlgorithms
+ {
+ BitPacking = 0x00 /// Bit packing
+ };
+ enum PropertyDataAlgorithms
+ {
+ LimpelZiv = 0xA0 /// Limpel-Ziv compressionrs
+ , BitPackingLong = 0x40 /// Bit packing of 32bit signed integers
+ , BitPackingWord = 0x20 /// Bit packing of 16bit unsigned integers
+ , BitPackingByte = 0x00 /// Bit packing of 8bit unsigned integers
+ };
+ /// Decompress packet data autodetecting the algorithm to use
+ bool inflatePacketData( DataSource &source, quint64 length, QList<qint64> &decodedData );
+ /// Compress packet data autodetecting the algorithm to use
+ bool deflatePacketData( QByteArray &destination, const QList<qint64> &decodedData );
- /// Mask byte used to identify the used algorithm
- enum Flags
- {
- BlockSizeFlag = 0x1F /// Find the block size of a packet
- , TransformationFlag = 0x20 /// Gorilla compressed data requires an extra transformation
- };
+ /// Decompress property data autodetecting the algorithm to use
+ bool inflatePropertyData( DataSource &source, quint64 length, QList<qint64> &decodedData );
+ /// Compress property data autodetecting the algorithm to use
+ bool deflatePropertyData( QByteArray &destination, const QList<qint64> &decodedData );
-
-
- /**
- * Types of storable data.
- *
- * These enum values are given to deflate() to compress different
- * kinds of data with the right algorithm.
- */
- enum DataType
- {
- Points /// We need to deflate points data
- , Properties /// We need to deflate packet properties
- };
-
-
-
- /**
- * Methods to compression and decompress ISF images
- */
- namespace Compress
- {
- /// Decompress data autodetecting the algorithm to use
- bool inflate( DataSource &source, quint64 length, QList<qint64> &decodedData );
- /// Compress data autodetecting the algorithm to use
- bool deflate( QByteArray &destination, const QList<qint64> &decodedData, DataType dataType );
}
}
Added: trunk/kmess/contrib/isf-qt/src/data/deltatransform.cpp
===================================================================
--- trunk/kmess/contrib/isf-qt/src/data/deltatransform.cpp (rev 0)
+++ trunk/kmess/contrib/isf-qt/src/data/deltatransform.cpp 2009-08-29 22:36:22 UTC (rev 5379)
@@ -0,0 +1,68 @@
+/***************************************************************************
+ * Copyright (C) 2008 by Valerio Pilo *
+ * va...@km... *
+ * *
+ * This program is free software; you can redistribute it and/or modify *
+ * it under the terms of the GNU Lesser General Public License as *
+ * published by the Free Software Foundation; either version 2.1 of the *
+ * License, or (at your option) any later version. *
+ * *
+ * This program is distributed in the hope that it will be useful, *
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of *
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the *
+ * GNU General Public License for more details. *
+ * *
+ * You should have received a copy of the GNU Lesser General Public *
+ * License along with this program; if not, write to the *
+ * Free Software Foundation, Inc., *
+ * 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. *
+ ***************************************************************************/
+
+#include "deltatransform.h"
+
+
+using namespace Isf::Compress;
+
+
+
+// Perform delta-delta transformation on data to deflate
+bool Delta::transform( QList<qint64> &data )
+{
+ qint64 currentDelta = 0;
+ qint64 previousDelta = 0;
+
+ for( qint64 index = 0; index < data.size(); ++index )
+ {
+ qint64 delta = data[ index ] - previousDelta;
+
+ previousDelta = currentDelta;
+ currentDelta = previousDelta;
+
+ data[ index ] = delta;
+ }
+
+ return true;
+}
+
+
+
+// Perform delta-delta inverse transformation on inflated data
+bool Delta::inverseTransform( QList<qint64> &data )
+{
+ qint64 currentDelta = 0;
+ qint64 previousDelta = 0;
+
+ for( qint64 index = 0; index < data.size(); ++index )
+ {
+ qint64 delta = ( currentDelta * 2 ) - previousDelta + data[ index ];
+
+ previousDelta = currentDelta;
+ currentDelta = delta;
+
+ data[ index ] = delta;
+ }
+
+ return true;
+}
+
+
Added: trunk/kmess/contrib/isf-qt/src/data/deltatransform.h
===================================================================
--- trunk/kmess/contrib/isf-qt/src/data/deltatransform.h (rev 0)
+++ trunk/kmess/contrib/isf-qt/src/data/deltatransform.h 2009-08-29 22:36:22 UTC (rev 5379)
@@ -0,0 +1,45 @@
+/***************************************************************************
+ * Copyright (C) 2008 by Valerio Pilo *
+ * va...@km... *
+ * *
+ * This program is free software; you can redistribute it and/or modify *
+ * it under the terms of the GNU Lesser General Public License as *
+ * published by the Free Software Foundation; either version 2.1 of the *
+ * License, or (at your option) any later version. *
+ * *
+ * This program is distributed in the hope that it will be useful, *
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of *
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the *
+ * GNU General Public License for more details. *
+ * *
+ * You should have received a copy of the GNU Lesser General Public *
+ * License along with this program; if not, write to the *
+ * Free Software Foundation, Inc., *
+ * 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. *
+ ***************************************************************************/
+
+#ifndef ISF_COMPRESS_DELTATRANSFORM_H
+#define ISF_COMPRESS_DELTATRANSFORM_H
+
+#include <QList>
+
+
+namespace Isf
+{
+ namespace Compress
+ {
+ namespace Delta
+ {
+
+ /// Perform delta-delta transformation on data to deflate
+ bool transform( QList<qint64> &data );
+ /// Perform delta-delta inverse transformation on inflated data
+ bool inverseTransform( QList<qint64> &data );
+
+ }
+ }
+}
+
+
+
+#endif
Deleted: trunk/kmess/contrib/isf-qt/src/data/gorilla.cpp
===================================================================
--- trunk/kmess/contrib/isf-qt/src/data/gorilla.cpp 2009-08-29 20:49:14 UTC (rev 5378)
+++ trunk/kmess/contrib/isf-qt/src/data/gorilla.cpp 2009-08-29 22:36:22 UTC (rev 5379)
@@ -1,182 +0,0 @@
-/***************************************************************************
- * Copyright (C) 2008-2009 by Valerio Pilo *
- * va...@km... *
- * *
- * This program is free software; you can redistribute it and/or modify *
- * it under the terms of the GNU Lesser General Public License as *
- * published by the Free Software Foundation; either version 2.1 of the *
- * License, or (at your option) any later version. *
- * *
- * This program is distributed in the hope that it will be useful, *
- * but WITHOUT ANY WARRANTY; without even the implied warranty of *
- * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the *
- * GNU General Public License for more details. *
- * *
- * You should have received a copy of the GNU Lesser General Public *
- * License along with this program; if not, write to the *
- * Free Software Foundation, Inc., *
- * 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. *
- ***************************************************************************/
-
-#include "isfqt-internal.h"
-#include "gorilla.h"
-
-#include <math.h>
-
-#include <QDebug>
-
-
-
-namespace Isf
-{
- namespace Compress
- {
-
-
-
- // Analyze the data to find the correct block size
- quint8 getBlockSizeGorilla( const QList<qint64> &data )
- {
- quint8 blockSize = 0;
- qint64 num;
-
- for( qint32 index = 0; index < data.size(); ++index )
- {
- num = data[ index ];
-
- if( num < 0 )
- {
- // We need the positive numbers: the +1 is for the sign bit
- num += - (num + 1);
- }
-
- // Shift right the value by blockSize bits until it becomes zero:
- // we need to detect the maximum bitwise size required to store
- // the numbers in the data array.
- num >>= blockSize;
- while( num )
- {
- ++blockSize;
- num >>= 1;
- }
- }
-
- // The sign bit always takes up a bit
- ++blockSize;
-
- return blockSize;
- }
-
-
-
- // Compress data using the Gorilla algorithm
- bool deflateGorilla( QByteArray &encodedData, quint8 blockSize, const QList<qint64> &source )
- {
- if( blockSize > 64 )
- {
- qWarning() << "A block size of" << blockSize << "is too high!";
- blockSize = 64; // Fuck it :P
- }
-
- quint8 blockSizeLeft; // Remaining bits to encode of the current value
- quint8 freeBits = 8; // Free bits of the current byte, in LSB order
- quint8 signMask = 1 << ( blockSize - 1 ); // Mask to add the sign bit
-
- quint8 byte = 0; // Byte to add to the array
- qint64 currentValue;
-
- for( qint64 index = 0; index < source.count(); ++index )
- {
- currentValue = source[ index ];
-
- if( currentValue < 0 )
- {
- currentValue |= signMask;
- }
-
- blockSizeLeft = blockSize;
-
- if( freeBits >= blockSizeLeft )
- {
- freeBits -= blockSizeLeft;
- byte |= currentValue << freeBits;
-
- encodedData.append( byte );
-
- byte = 0;
- freeBits = 8;
- }
- else
- {
- // Fill the current byte
- quint64 mask = 0xFFFFFFFF >> ( 32 - blockSizeLeft );
- byte |= currentValue >> ( blockSizeLeft - freeBits );
-
- encodedData.append( byte );
-
- byte = 0;
- blockSizeLeft -= freeBits;
- mask >>= freeBits;
- currentValue &= mask;
-
- // Then fill all the next bytes required to encode the current value,
- // except the last one
- while( blockSizeLeft > 8 )
- {
- blockSizeLeft -= 8;
- encodedData.append( currentValue >> blockSizeLeft );
-
- mask >>= 8;
- currentValue &= mask;
- }
-
- // Finally, add the last byte
- freeBits = 8 - blockSizeLeft;
- encodedData.append( currentValue << freeBits );
- }
- }
-
- return true;
- }
-
-
-
- // Decompress data using the Gorilla algorithm
- bool inflateGorilla( DataSource &source, quint64 length, quint8 blockSize, QList<qint64> &decodedData )
- {
- if( blockSize > 64 )
- {
- qWarning() << "A block size of" << blockSize << "is too high!";
- blockSize = 64; // Fuck it :P
- }
-
- if( source.atEnd() )
- {
- qWarning() << "Cannot inflate: no more bits available!";
- return true;
- }
-
- qint64 value;
- quint32 index = 0;
- quint64 signMask = (quint64)( 0xFFFFFFFF * pow( 2, blockSize - 1 ) ) & 0xFFFFFFFF;
-
- while( index++ < length )
- {
- value = source.getBits( blockSize );
-
- // If the mask matches, the sign bit is set, so ORing value and mask will
- // set all leftmost bits to 1, making it a real 64bit signed integer
- if( value & signMask )
- {
- value |= signMask;
- }
-
- decodedData.append( value );
- }
-
- return true;
- }
-
-
- }
-};
Deleted: trunk/kmess/contrib/isf-qt/src/data/gorilla.h
===================================================================
--- trunk/kmess/contrib/isf-qt/src/data/gorilla.h 2009-08-29 20:49:14 UTC (rev 5378)
+++ trunk/kmess/contrib/isf-qt/src/data/gorilla.h 2009-08-29 22:36:22 UTC (rev 5379)
@@ -1,43 +0,0 @@
-/***************************************************************************
- * Copyright (C) 2008 by Valerio Pilo *
- * va...@km... *
- * *
- * This program is free software; you can redistribute it and/or modify *
- * it under the terms of the GNU Lesser General Public License as *
- * published by the Free Software Foundation; either version 2.1 of the *
- * License, or (at your option) any later version. *
- * *
- * This program is distributed in the hope that it will be useful, *
- * but WITHOUT ANY WARRANTY; without even the implied warranty of *
- * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the *
- * GNU General Public License for more details. *
- * *
- * You should have received a copy of the GNU Lesser General Public *
- * License along with this program; if not, write to the *
- * Free Software Foundation, Inc., *
- * 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. *
- ***************************************************************************/
-
-#ifndef ISFCOMPRESSION_GORILLA_H
-#define ISFCOMPRESSION_GORILLA_H
-
-#include "datasource.h"
-
-
-
-namespace Isf
-{
- namespace Compress
- {
- /// Analyze the data to find the correct block size
- quint8 getBlockSizeGorilla( const QList<qint64> &data );
- /// Compress data using the Gorilla algorithm
- bool deflateGorilla( QByteArray &encodedData, quint8 blockSize, const QList<qint64> &source );
- /// Decompress data using the Gorilla algorithm
- bool inflateGorilla( DataSource &source, quint64 length, quint8 blockSize, QList<qint64> &decodedData );
- }
-}
-
-
-
-#endif
Modified: trunk/kmess/contrib/isf-qt/src/data/huffman.cpp
===================================================================
--- trunk/kmess/contrib/isf-qt/src/data/huffman.cpp 2009-08-29 20:49:14 UTC (rev 5378)
+++ trunk/kmess/contrib/isf-qt/src/data/huffman.cpp 2009-08-29 22:36:22 UTC (rev 5379)
@@ -29,258 +29,226 @@
#define HUFFMAN_BASE_SIZE 11
+using namespace Isf::Compress;
-namespace Isf
+
+const int bitAmounts_[HUFFMAN_BASES_NUM][HUFFMAN_BASE_SIZE] =
{
- namespace Compress
- {
- const int bitAmounts_[HUFFMAN_BASES_NUM][HUFFMAN_BASE_SIZE] =
- {
- {0, 1, 2, 4, 6, 8, 12, 16, 24, 32, -1},
- {0, 1, 1, 2, 4, 8, 12, 16, 24, 32, -1},
- {0, 1, 1, 1, 2, 4, 8, 14, 22, 32, -1},
- {0, 2, 2, 3, 5, 8, 12, 16, 24, 32, -1},
- {0, 3, 4, 5, 8, 12, 16, 24, 32, -1, -1},
- {0, 4, 6, 8, 12, 16, 24, 32, -1, -1, -1},
- {0, 6, 8, 12, 16, 24, 32, -1, -1, -1, -1},
- {0, 7, 8, 12, 16, 24, 32, -1, -1, -1, -1},
- };
+ {0, 1, 2, 4, 6, 8, 12, 16, 24, 32, -1},
+ {0, 1, 1, 2, 4, 8, 12, 16, 24, 32, -1},
+ {0, 1, 1, 1, 2, 4, 8, 14, 22, 32, -1},
+ {0, 2, 2, 3, 5, 8, 12, 16, 24, 32, -1},
+ {0, 3, 4, 5, 8, 12, 16, 24, 32, -1, -1},
+ {0, 4, 6, 8, 12, 16, 24, 32, -1, -1, -1},
+ {0, 6, 8, 12, 16, 24, 32, -1, -1, -1, -1},
+ {0, 7, 8, 12, 16, 24, 32, -1, -1, -1, -1},
+};
- const int huffmanBases_[HUFFMAN_BASES_NUM][HUFFMAN_BASE_SIZE] =
- {
- {0, 1, 2, 4, 12, 44, 172, 2220, 34988, 8423596, -1},
- {0, 1, 2, 3, 5, 13, 141, 2189, 34957, 8423565, -1},
- {0, 1, 2, 3, 4, 6, 14, 142, 8334, 2105486, -1},
- {0, 1, 3, 5, 9, 25, 153, 2201, 34969, 8423577, -1},
- {0, 1, 5, 13, 29, 157, 2205, 34973, 8423581, -1, -1},
- {0, 1, 9, 41, 169, 2217, 34985, 8423593, -1, -1, -1},
- {0, 1, 33, 161, 2209, 34977, 8423585, -1, -1, -1, -1},
- {0, 1, 65, 193, 2241, 35009, 8423617, -1, -1, -1, -1},
- };
+const int huffmanBases_[HUFFMAN_BASES_NUM][HUFFMAN_BASE_SIZE] =
+{
+ {0, 1, 2, 4, 12, 44, 172, 2220, 34988, 8423596, -1},
+ {0, 1, 2, 3, 5, 13, 141, 2189, 34957, 8423565, -1},
+ {0, 1, 2, 3, 4, 6, 14, 142, 8334, 2105486, -1},
+ {0, 1, 3, 5, 9, 25, 153, 2201, 34969, 8423577, -1},
+ {0, 1, 5, 13, 29, 157, 2205, 34973, 8423581, -1, -1},
+ {0, 1, 9, 41, 169, 2217, 34985, 8423593, -1, -1, -1},
+ {0, 1, 33, 161, 2209, 34977, 8423585, -1, -1, -1, -1},
+ {0, 1, 65, 193, 2241, 35009, 8423617, -1, -1, -1, -1},
+};
- // Analyze the data to find the most appropriate index
- quint8 getIndexHuffman( const QList<qint64> &data )
- {
- quint8 index = 0;
+// Get the most appropriate index for the given data
+quint8 HuffmanAlgorithm::index( const QList<qint64> &data )
+{
+ quint8 index = 0;
- // TODO: Find out what the Huffman index algorithm is
- Q_UNUSED( data )
- index = 2;
+ // TODO: Find out what the Huffman index algorithm is
+ Q_UNUSED( data )
+ index = 2;
- return index;
- }
+ return index;
+}
- // Compress data using the Adaptive-Huffman algorithm
- bool deflateHuffman( QByteArray &encodedData, quint8 index, const QList<qint64> &source )
- {
- DataSource output( encodedData );
- output.skipToNextByte();
+// Compress data
+bool HuffmanAlgorithm::deflate( QByteArray &encodedData, quint8 index, const QList<qint64> &source )
+{
+ DataSource output( encodedData );
+ output.skipToNextByte();
- int previousDelta = 0, currentDelta = 0;
- for( int pos = 0; pos < source.size(); ++pos )
- {
- if( pos == 0 )
- {
- currentDelta = source[ pos ];
- }
- else
- {
- currentDelta = source[ pos ] - source[ pos - 1 ];
- }
-
- if( ! deflateHuffmanValue( output, index, currentDelta - previousDelta ) )
- {
+ foreach( quint64 value, source )
+ {
+ if( ! deflateValue( output, index, value ) )
+ {
#ifdef ISFQT_DEBUG
- qDebug() << "Deflating failure for value:" << source[ pos ] << "- delta" << ( currentDelta - previousDelta );
+ qDebug() << "Deflating failure for value:" << value;
#endif
- return false;
- }
+ return false;
+ }
+ }
- previousDelta = currentDelta;
- }
+ // Flush any leftover bit to the byte array
+ output.flush();
- // Flush any leftover bit to the byte array
- output.flush();
+ encodedData = output.data();
+ return true;
+}
- encodedData = output.data();
- return true;
- }
+// Compress a single value using the Adaptive-Huffman algorithm
+bool HuffmanAlgorithm::deflateValue( DataSource &output, quint8 index, qint64 value )
+{
+ qint64 temp = value;
+ quint8 requiredBits = 0;
+ QBitArray valueBits;
- // Compress a single value using the Adaptive-Huffman algorithm
- bool deflateHuffmanValue( DataSource &output, quint8 index, qint64 value )
+ // Fill in a bitAmounts local vector
+ QVector<int> bitAmounts;
+ for( int i = 0; i < HUFFMAN_BASE_SIZE; ++i )
+ {
+ if( bitAmounts_[ index ][ i ] == -1 )
{
- qint64 temp = value;
- quint8 requiredBits = 0;
- QBitArray valueBits;
+ break;
+ }
- // Fill in a bitAmounts local vector
- QVector<int> bitAmounts;
- for( int i = 0; i < HUFFMAN_BASE_SIZE; ++i )
- {
- if( bitAmounts_[ index ][ i ] == -1 )
- {
- break;
- }
+ bitAmounts.append( bitAmounts_[ index ][ i ] );
+ }
- bitAmounts.append( bitAmounts_[ index ][ i ] );
- }
+ // Find the number of bits needed to store this value
+ while( temp )
+ {
+ temp /= 2;
+ ++requiredBits;
+ }
- // Find the number of bits needed to store this value
- while( temp )
- {
- temp /= 2;
- ++requiredBits;
- }
+ while( ! bitAmounts.count( requiredBits ) )
+ {
+ ++requiredBits;
+ }
- while( ! bitAmounts.count( requiredBits ) )
- {
- ++requiredBits;
- }
+ qint64 offset = ( value < 0 ) ? -value : +value;
- qint64 offset = ( value < 0 ) ? -value : +value;
+ quint8 prefixLength;
+ for( prefixLength = 1;
+ ( prefixLength < HUFFMAN_BASE_SIZE ) && ( offset >= huffmanBases_[ index ][ prefixLength ] ); prefixLength++ )
+ {
+ // Empty loop on purpose
+ }
- quint8 prefixLength;
- for( prefixLength = 1;
- ( prefixLength < HUFFMAN_BASE_SIZE ) && ( offset >= huffmanBases_[ index ][ prefixLength ] ); prefixLength++ )
- {
- // Empty loop on purpose
- }
+ // Write prefixLength 1s to the stream, then a 0
+ QBitArray bits( prefixLength );
+ bits.fill( true );
+ bits.clearBit( bits.size() - 1 );
-// quint8 lengthIndex = bitAmounts.indexOf( requiredBits );
+ // Write the number using the minimum possible number of bits
+ qint32 size = bitAmounts_[ index ][ prefixLength - 1 ];
+ qint64 mask = ( 1 << ( size - 1 ) ) - 1;
- // Write prefixLength 1s to the stream, then a 0
- QBitArray bits( prefixLength );
- bits.fill( true );
- bits.clearBit( bits.size() - 1 );
+ valueBits.resize( size );
+ offset = ( offset - huffmanBases_[ index ][ prefixLength - 1 ] ) & mask;
+ offset <<= 1;
+ offset |= ( value < 0 ) ? 1 : 0;
- // Write the number using the minimum possible number of bits
- qint32 size = bitAmounts_[ index ][ prefixLength - 1 ];
- qint64 mask = ( 1 << ( size - 1 ) ) - 1;
+ // Copy the resulting offset
+ for( qint64 i = 0; i < size; ++i )
+ {
+ valueBits.setBit( i, offset & ( 1 << ( size - i - 1 ) ) );
+ }
- valueBits.resize( size );
- offset = ( offset - huffmanBases_[ index ][ prefixLength - 1 ] ) & mask;
- offset <<= 1;
- offset |= ( value < 0 ) ? 1 : 0;
+ // Add the bits to the data source
+ output.append( bits );
+ output.append( valueBits );
- // Copy the resulting offset
- for( qint64 i = 0; i < size; ++i )
- {
- valueBits.setBit( i, offset & ( 1 << ( size - i - 1 ) ) );
- }
+ return true;
+}
- // Add the bits to the data source
- output.append( bits );
- output.append( valueBits );
- return true;
- }
+// Decompress data
+bool HuffmanAlgorithm::inflate( DataSource &source, quint64 length, quint8 index, QList<qint64> &decodedData )
+{
+ QVector<int> huffmanBases;
+ QVector<int> bitAmounts( HUFFMAN_BASE_SIZE );
+ // Initialize the bit amounts vector
+ memcpy( bitAmounts.data(), bitAmounts_[ index ], sizeof(int)*HUFFMAN_BASE_SIZE );
- // Decompress data using the Huffman algorithm
- bool inflateHuffman( DataSource &source, quint64 length, quint8 index, QList<qint64> &decodedData )
- {
- QVector<int> huffmanBases;
- QVector<int> bitAmounts( HUFFMAN_BASE_SIZE );
+ int base = 1;
+ huffmanBases.append( 0 );
- // Initialize the bit amounts vector
- memcpy( bitAmounts.data(), bitAmounts_[ index ], sizeof(int)*HUFFMAN_BASE_SIZE );
+ // Fill up the huffman bases vector
+ for( quint8 i = 0; i < bitAmounts.size(); ++i )
+ {
+ int value = bitAmounts[ i ];
- int base = 1;
- huffmanBases.append( 0 );
+ // The bit amounts sequence ends in -1
+ if( value == -1 )
+ {
+ bitAmounts.resize( i );
+ break;
+ }
- // Fill up the huffman bases vector
- for( quint8 i = 0; i < bitAmounts.size(); ++i )
- {
- int value = bitAmounts[ i ];
+ if( value == 0 )
+ {
+ continue;
+ }
- // The bit amounts sequence ends in -1
- if( value == -1 )
- {
- bitAmounts.resize( i );
- break;
- }
+ huffmanBases.append( base );
+ base += pow( 2, value - 1 );
+ }
- if( value == 0 )
- {
- continue;
- }
- huffmanBases.append( base );
- base += pow( 2, value - 1 );
- }
+ quint32 count = 0;
+ qint64 value = 0;
+ bool bit;
+ while( (uint)decodedData.length() < length )
+ {
+ bit = source.getBit();
- quint32 count = 0;
- qint64 value = 0;
- bool bit;
+ if( bit )
+ {
+ count++;
+ continue;
+ }
- while( (uint)decodedData.length() < length )
- {
- bit = source.getBit();
-
- if( bit )
- {
- count++;
- continue;
- }
-
- if( count == 0 )
- {
- value = 0;
- }
- else if( count < (uint)bitAmounts.size() )
- {
- quint64 offset = source.getBits( bitAmounts[ count ] );
- bool sign = offset & 0x1;
- offset /= 2;
- value = huffmanBases[ count ] + offset;
- value *= ( sign ? -1 : +1 );
- }
- else if( count == (uint)bitAmounts.size() )
- {
- // TODO: Implement 64-bit data decompression :)
+ if( count == 0 )
+ {
+ value = 0;
+ }
+ else if( count < (uint)bitAmounts.size() )
+ {
+ quint64 offset = source.getBits( bitAmounts[ count ] );
+ bool sign = offset & 0x1;
+ offset /= 2;
+ value = huffmanBases[ count ] + offset;
+ value *= ( sign ? -1 : +1 );
+ }
+ else if( count == (uint)bitAmounts.size() )
+ {
+ // TODO: Implement 64-bit data decompression :)
#ifdef ISFQT_DEBUG
- qDebug() << "Unsupported 64-bit value found!";
+ qDebug() << "Unsupported 64-bit value found!";
#endif
- value = 0;
- }
- else
- {
+ value = 0;
+ }
+ else
+ {
#ifdef ISFQT_DEBUG
- qDebug() << "Decompression error!";
+ qDebug() << "Decompression error!";
#endif
- value = 0;
- }
-
- decodedData.append( value );
- count = 0;
- }
-
- // Perform the delta-delta inverse transformation on the values
- int previousDelta = 0, currentDelta = 0;
- for( int i = 0; i < decodedData.size(); ++i )
- {
- int delta = ( currentDelta * 2 ) - previousDelta + decodedData[ i ];
- previousDelta = currentDelta;
- currentDelta = delta;
-
- decodedData[ i ] = delta;
- }
-
- return true;
+ value = 0;
}
-
+ decodedData.append( value );
+ count = 0;
}
+ return true;
+}
-};
Modified: trunk/kmess/contrib/isf-qt/src/data/huffman.h
===================================================================
--- trunk/kmess/contrib/isf-qt/src/data/huffman.h 2009-08-29 20:49:14 UTC (rev 5378)
+++ trunk/kmess/contrib/isf-qt/src/data/huffman.h 2009-08-29 22:36:22 UTC (rev 5379)
@@ -29,17 +29,22 @@
{
namespace Compress
{
- /// Compress data using the Huffman algorithm
- bool deflateHuffman( QByteArray &encodedData, quint8 index, const QList<qint64> &source );
- /// Decompress data using the Huffman algorithm
- bool inflateHuffman( DataSource &source, quint64 length, quint8 index, QList<qint64> &decodedData );
- /// Analyze the data to find the most appropriate index
- quint8 getIndexHuffman( const QList<qint64> &data );
+ namespace HuffmanAlgorithm
+ {
- // Internal use methods
+ /// Compress data
+ bool deflate( QByteArray &encodedData, quint8 index, const QList<qint64> &source );
+ /// Decompress data
+ bool inflate( DataSource &source, quint64 length, quint8 index, QList<qint64> &decodedData );
+ /// Get the most appropriate index for the given data
+ quint8 index( const QList<qint64> &data );
- /// Compress a single value using the Adaptive-Huffman algorithm
- bool deflateHuffmanValue( DataSource &output, quint8 index, qint64 value );
+ // Internal use methods
+
+ // Compress a single value using the Adaptive-Huffman algorithm
+ bool deflateValue( DataSource &output, quint8 index, qint64 value );
+
+ }
}
}
Modified: trunk/kmess/contrib/isf-qt/src/isfqtdrawing.cpp
===================================================================
--- trunk/kmess/contrib/isf-qt/src/isfqtdrawing.cpp 2009-08-29 20:49:14 UTC (rev 5378)
+++ trunk/kmess/contrib/isf-qt/src/isfqtdrawing.cpp 2009-08-29 22:36:22 UTC (rev 5379)
@@ -420,6 +420,14 @@
QSize size_ = size();
+ if( size_.width() > 2000 || size_.height() > 2000 )
+ {
+ qWarning() << "Cannot render a drawing so big!";
+ qDebug() << "[Information - Size:" << size_ << "pixels]";
+
+ return QPixmap();
+ }
+
QPixmap pixmap( size_ );
pixmap.fill( backgroundColor );
QPainter painter( &pixmap );
Modified: trunk/kmess/contrib/isf-qt/src/tagswriter.cpp
===================================================================
--- trunk/kmess/contrib/isf-qt/src/tagswriter.cpp 2009-08-29 20:49:14 UTC (rev 5378)
+++ trunk/kmess/contrib/isf-qt/src/tagswriter.cpp 2009-08-29 22:36:22 UTC (rev 5379)
@@ -372,7 +372,7 @@
transformTag = TAG_TRANSFORM;
blockData.append( encodeFloat( trans->m11() * HiMetricToPixel ) );
blockData.append( encodeFloat( .0f ) );
- blockData.append( encodeFloat( .0f ) );
+ blockData.append( encodeFloat( .0f ) );
blockData.append( encodeFloat( trans->m22() * HiMetricToPixel ) );
blockData.append( encodeFloat( trans->dx () / trans->m11() ) );
blockData.append( encodeFloat( trans->dy () / trans->m22() ) );
@@ -514,8 +514,8 @@
yPoints.append( point.position.y() );
}
- deflate( blockData, xPoints, Points );
- deflate( blockData, yPoints, Points );
+ deflatePacketData( blockData, xPoints );
+ deflatePacketData( blockData, yPoints );
// The stroke is made by tag, then payload size, then number of points, then
// the compressed points data
Added: trunk/kmess/contrib/isf-qt/tests/signature.isf
===================================================================
(Binary files differ)
Property changes on: trunk/kmess/contrib/isf-qt/tests/signature.isf
___________________________________________________________________
Added: svn:mime-type
+ application/octet-stream
This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.
|