--Boundary-00=_/R/nLD78D9Ta3CH Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: 7bit 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 --Boundary-00=_/R/nLD78D9Ta3CH Content-Type: text/x-patch; charset="UTF-8"; name="compressedtiles.diff" Content-Transfer-Encoding: 7bit Content-Disposition: attachment; filename="compressedtiles.diff" 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; } --Boundary-00=_/R/nLD78D9Ta3CH Content-Type: text/plain; charset="us-ascii" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit Content-Disposition: inline _______________________________________________ kimageshop mailing list kimageshop@kde.org https://mail.kde.org/mailman/listinfo/kimageshop --Boundary-00=_/R/nLD78D9Ta3CH--