[prev in list] [next in list] [prev in thread] [next in thread]
List: kde-kimageshop
Subject: A little experiment on compressint tile at saving time
From: Cyrille Berger <cberger () cberger ! net>
Date: 2010-03-16 21:13:35
Message-ID: 201003162213.35866.cberger () cberger ! net
[Download RAW message or body]
Hello,
I made a little experiment on saving for Krita, and instead of compressing the
whole file, what happen if only the tiles are compressed.
For comparison point, I made a 5 layers 9000x9000 images with gradient in the
Gimp:
* xcf : 85MB
* .kra with compressed tiles and no global compression: 67MB, saving time 1.6s
* .kra with uncompressed tiles and global compression: 28MB, saving time 28s
* .ora : 31MB
I do not have the time for .ora, but it was closed to 30s as well.
I also did experimentation with a multilayer image made with camera pictures:
* .kra with compressed tiles and no global compression: 88MB, saving time 2s
* .kra with uncompressed tiles and global compression: 56MB, saving time 20s
This is just for reference, we won't do any change for 2.2 on the way tiles
are saved, but I think it is worth it for 2.3, and would warrant further
investigation.
For the curious I have attached the (rough) patch I used for those
measurements (you would also need to disable global compression in
KoStoreZip).
--
Cyrille Berger
["compressedtiles.diff" (text/x-patch)]
Index: kis_tiled_data_manager.cc
===================================================================
--- kis_tiled_data_manager.cc (revision 1102761)
+++ kis_tiled_data_manager.cc (working copy)
@@ -110,7 +110,165 @@
memcpy(m_defaultPixel, defaultPixel, pixelSize());
}
+#define HASH_LOG 12
+#define HASH_SIZE (1<< HASH_LOG)
+#define HASH_MASK (HASH_SIZE-1)
+#define UPDATE_HASH(v,p) { v = *((quint16*)p); v ^= *((quint16*)(p+1))^(v>>(16-HASH_LOG)); }
+
+#define MAX_COPY 32
+#define MAX_LEN 264 /* 256 + 8 */
+#define MAX_DISTANCE 8192
+
+// Lossless compression using LZF algorithm, this is faster on modern CPU than
+// the original implementation in http://liblzf.plan9.de/
+static int lzff_compress(const void* input, int length, void* output, int maxout)
+{
+ Q_UNUSED(maxout);
+
+ const quint8* ip = (const quint8*) input;
+ const quint8* ip_limit = ip + length - MAX_COPY - 4;
+ quint8* op = (quint8*) output;
+
+ const quint8* htab[HASH_SIZE];
+ const quint8** hslot;
+ quint32 hval;
+
+ quint8* ref;
+ qint32 copy;
+ qint32 len;
+ qint32 distance;
+ quint8* anchor;
+
+ /* initializes hash table */
+ for (hslot = htab; hslot < htab + HASH_SIZE; hslot++)
+ *hslot = ip;
+
+ /* we start with literal copy */
+ copy = 0;
+ *op++ = MAX_COPY - 1;
+
+ /* main loop */
+ while (ip < ip_limit) {
+ /* find potential match */
+ UPDATE_HASH(hval, ip);
+ hslot = htab + (hval & HASH_MASK);
+ ref = (quint8*) * hslot;
+
+ /* update hash table */
+ *hslot = ip;
+
+ /* find itself? then it's no match */
+ if (ip == ref)
+ goto literal;
+
+ /* is this a match? check the first 2 bytes */
+ if (*((quint16*)ref) != *((quint16*)ip))
+ goto literal;
+
+ /* now check the 3rd byte */
+ if (ref[2] != ip[2])
+ goto literal;
+
+ /* calculate distance to the match */
+ distance = ip - ref;
+
+ /* skip if too far away */
+ if (distance >= MAX_DISTANCE)
+ goto literal;
+
+ /* here we have 3-byte matches */
+ anchor = (quint8*)ip;
+ len = 3;
+ ref += 3;
+ ip += 3;
+
+ /* now we have to check how long the match is */
+ if (ip < ip_limit - MAX_LEN) {
+ while (len < MAX_LEN - 8) {
+ /* unroll 8 times */
+ if (*ref++ != *ip++) break;
+ if (*ref++ != *ip++) break;
+ if (*ref++ != *ip++) break;
+ if (*ref++ != *ip++) break;
+ if (*ref++ != *ip++) break;
+ if (*ref++ != *ip++) break;
+ if (*ref++ != *ip++) break;
+ if (*ref++ != *ip++) break;
+ len += 8;
+ }
+ ip--;
+ }
+ len = ip - anchor;
+
+ /* just before the last non-matching byte */
+ ip = anchor + len;
+
+ /* if we have copied something, adjust the copy count */
+ if (copy) {
+ /* copy is biased, '0' means 1 byte copy */
+ anchor = anchor - copy - 1;
+ *(op - copy - 1) = copy - 1;
+ copy = 0;
+ } else
+ /* back, to overwrite the copy count */
+ op--;
+
+ /* length is biased, '1' means a match of 3 bytes */
+ len -= 2;
+
+ /* distance is also biased */
+ distance--;
+
+ /* encode the match */
+ if (len < 7)
+ *op++ = (len << 5) + (distance >> 8);
+ else {
+ *op++ = (7 << 5) + (distance >> 8);
+ *op++ = len - 7;
+ }
+ *op++ = (distance & 255);
+
+ /* assuming next will be literal copy */
+ *op++ = MAX_COPY - 1;
+
+ /* update the hash at match boundary */
+ --ip;
+ UPDATE_HASH(hval, ip);
+ htab[hval & HASH_MASK] = ip;
+ ip++;
+
+ continue;
+
+ literal:
+ *op++ = *ip++;
+ copy++;
+ if (copy >= MAX_COPY) {
+ copy = 0;
+ *op++ = MAX_COPY - 1;
+ }
+ }
+
+ /* left-over as literal copy */
+ ip_limit = (const quint8*)input + length;
+ while (ip < ip_limit) {
+ *op++ = *ip++;
+ copy++;
+ if (copy == MAX_COPY) {
+ copy = 0;
+ *op++ = MAX_COPY - 1;
+ }
+ }
+
+ /* if we have copied something, adjust the copy length */
+ if (copy)
+ *(op - copy - 1) = copy - 1;
+ else
+ op--;
+
+ return op - (quint8*)output;
+}
+
bool KisTiledDataManager::write(KoStore *store)
{
QReadLocker locker(&m_lock);
@@ -129,14 +287,41 @@
const qint32 tileDataSize = KisTileData::HEIGHT * KisTileData::WIDTH * pixelSize();
+ QByteArray output;
+ output.resize(tileDataSize + 4 + 1 + 1000);
+
while (tile = iter.tile()) {
tile->extent().getRect(&x, &y, &width, &height);
sprintf(str, "%d,%d,%d,%d\n", x, y, width, height);
store->write(str, strlen(str));
tile->lockForRead();
- store->write((char *)tile->data(), tileDataSize);
+
+ const void* const in_data = (const void*) tile->data();
+ unsigned int in_len = (unsigned int)tileDataSize;
+
+
+ // we use 4 bytes to store uncompressed length
+ // and 1 extra byte as flag (0=uncompressed, 1=compressed)
+ output[0] = in_len & 255;
+ output[1] = (in_len >> 8) & 255;
+ output[2] = (in_len >> 16) & 255;
+ output[3] = (in_len >> 24) & 255;
+ output[4] = 1;
+
+ unsigned int out_len = in_len - 1;
+ unsigned char* out_data = (unsigned char*) output.data() + 5;
+
+ unsigned int len = lzff_compress(in_data, in_len, out_data, out_len);
+ out_len = len;
+
+ if ((len > in_len) || (len == 0)) {
+ store->write((char*)tile->data(), tileDataSize);
+ } else {
+
+ store->write((char *)output.data(), out_len);
tile->unlock();
+ }
++iter;
}
_______________________________________________
kimageshop mailing list
kimageshop@kde.org
https://mail.kde.org/mailman/listinfo/kimageshop
[prev in list] [next in list] [prev in thread] [next in thread]
Configure |
About |
News |
Add a list |
Sponsored by KoreLogic