Forum archive

possible bug in kzip with large files

krick at 2005-07-25 02:25
I was trying to rezip some zipfiles with kzip to make them smaller.

Everything was going fine until I tried to rezip the contents of this file...

http://3feetunder.com/files/primglex.zip

...using these settings...

kzip.exe /r /y /b128

I understand that kzip is slower than other zip tools but I let it run for nearly 2 days and it still hadn't finished. Other zip archives of similar size were finished much quicker and certainly didn't take days. I'm thinking that there must be a bug and it's stuck in a loop or something.

I compared the contents of other archives that I was able to rezip successfully and the only difference I can find is that primglex.zip contains files that are exactly 4.00 MB in size. Maybe there is a subtle bug that is triggered only when files are EXACTLY 4,194,304 bytes. I've seen similar bugs happen before in other programs.

I've skipped this particular archive for the moment and I'm moving on to other larger archives. If I find any others it gets stuck on, I'll post it here.

Awesoken at 2005-07-25 06:47

Yes, this is a bug in both KZIP and PNGOUT. In PNGOUT, you can press ESC to quit after the next pass (allowing it to continue). KZIP has no such feature (yet). I've seen this happen before but I've been too lazy to do anything about it. I can say for sure that it has nothing to do with the file size being an exact power of 2. My algorithm continues to do passes while it thinks the next pass will be smaller. Certain files make it fall into infinite loops. "pg1rom0l.ic6" happens to be one of them. All other files in your archive work fine. If you want to have fun, you can run KZIP in verbose mode (/v) and watch it repeating the same pass forever:

kzip /b128 /v test.zip pg1rom0l.ic6

...

Fileleng: 1964859 bytes - 336234.375 -> 1628624.625

Fileleng: 1651453 bytes -   6783.875 -> 1644669.125

Fileleng: 1640354 bytes -   2756.500 -> 1637597.500

Fileleng: 1634823 bytes -   1921.875 -> 1632901.125

Fileleng: 1631773 bytes -    539.625 -> 1631233.375

Fileleng: 1630891 bytes -    144.500 -> 1630746.500

Fileleng: 1630599 bytes -     41.250 -> 1630557.750

Fileleng: 1630526 bytes -     11.000 -> 1630515.000

Fileleng: 1630504 bytes -      1.500 -> 1630502.500

Fileleng: 1630501 bytes -      4.500 -> 1630496.500

Fileleng: 1630492 bytes -      0.750 -> 1630491.250

Fileleng: 1630488 bytes -      0.250 -> 1630487.750

Fileleng: 1630489 bytes -      0.500 -> 1630488.500

Fileleng: 1630489 bytes -      0.500 -> 1630488.500

Fileleng: 1630492 bytes -      1.500 -> 1630490.500

Fileleng: 1630486 bytes -      1.500 -> 1630484.500

Fileleng: 1630481 bytes -      0.250 -> 1630480.750

Fileleng: 1630478 bytes -      1.250 -> 1630476.750

Fileleng: 1630475 bytes -      0.250 -> 1630474.750

Fileleng: 1630475 bytes -      0.250 -> 1630474.750

Fileleng: 1630475 bytes -      0.250 -> 1630474.750

Fileleng: 1630475 bytes -      0.250 -> 1630474.750

Fileleng: 1630475 bytes -      0.250 -> 1630474.750

Fileleng: 1630475 bytes -      0.250 -> 1630474.750

...

krick at 2005-07-25 10:45
er... so... what are the chances of this bug getting fixed?

I hope you can fix it because I think KZIP is awesome. I used to think BJWFlate was the king, but KZIP has stolen the crown.

Would it help to have more files that cause it to exhibit this behaviour?
krick at 2005-07-26 14:04
I was also curious about the "Block split threshold" parameter.

Is there an upper limit on this value?
Awesoken at 2005-07-27 02:43
The block split threshold is a double floating point variable, so there really isn't a limit. While the upper limit is in theory infinity, usually anything above 5000 will result in no split blocks. You can enable verbose mode (/v) to see how many blocks were actually created. FYI: /b0 is an alias for /b999999...
counting_pine at 2005-07-31 02:20
How does your deflate algorithm decide when to not do another pass? Would it be sufficient to check whether two consecutive passes generate the same Huffman tables?
Anonymous at 2005-08-02 22:46
I found another archive with the same problem.
One of the files is hanging when I try to rezip using

kzip.exe /r /y /b128

Here's a link to the archive if you want it for testing...

http://3feetunder.com/files/rockn.zip

Maybe if I can find enough of these files, we can figure out some sort of commonality that triggers the bug.
Awesoken at 2005-08-03 03:26
I fixed the infinite pass bugs in PNGOUT and KZIP today. Thanks to everyone who sent me test files - they were very helpful!

As a bonus, I made PNGOUT and KZIP always save the smallest pass. Sometimes, a previous pass is smaller than the last pass (because the Huffman table itself varies in size). The bad news is these files will now require an extra pass. The good news is the result will always be smaller if this pass is necessary.

Next, we need JonoF to re-compile the Linux / Mac ports : )

counting_pine at 2005-08-03 08:27

Cool, I've tested the files with kzip /b128 and it now manages both of them. I haven't tested PNGOUT because I don't have a PNG file that triggers the bug, but I assume it works OK.
I can't get PNGOUT or KZIP to always save the smallest pass though. One file I tested gave me the result:

 Input size:  110641 bytes, 256 colors, bitdepth:8



Block boundaries: 15407,23c0c,2fc28,45101,494c7,68a08,83abd,9466a,a5696



Output size:  126465 bytes -  15243.375 ->  111221.625

Output size:  111057 bytes -    196.375 ->  110860.625

Output size:  110716 bytes -     19.375 ->  110696.625

Output size:  110681 bytes -     10.125 ->  110670.875

Output size:  110638 bytes -      5.500 ->  110632.500

Output size:  110642 bytes -      0.875 ->  110641.125

Output size:  110645 bytes

Took 31.758 sec.



Unable to compress further: copying original file

Awesoken at 2005-08-03 09:35
Ah... I think I know why that's happening. Would you mind sending me a URL to that image? : )
counting_pine at 2005-08-03 10:27
Here's the image in question (108KB).
If you run pngout /v on it, the smallest pass is 10 bytes smaller than the final pass, which is the biggest difference I've seen.
I posted my results from running PNGOUT with the /kp switch, so the same thing will happen if you decompress the IDAT into a file and then kzip it.
Awesoken at 2005-08-03 14:11
Ok, fixed. PNGOUT and KZIP should now save the smallest pass.

BTW, nice image : ) My guess is "(x,y)e=exp(1);(y/e-x)%(x/e+y)" although the spectrum colors are slightly off.
counting_pine at 2005-08-04 05:21
Yes, it works in both KZIP and PNGOUT now (although in this case, since it doesn't save any bytes, the final pass is unnecessary:).
Awesoken said
My guess is "(x,y)e=exp(1);(y/e-x)%(x/e+y)" although the spectrum colors are slightly off.
Thought you might recognise it :)
I think that's the gist of it... Let me see if I can find the code...
```
(x,y,t)

if(t+1==glob[0])

{

s=glob[1];

c=glob[2];

}

else

{

s=sin(t*PI);c=cos(t*PI);

glob[0]=t+1;glob[1]=s;glob[2]=c;

}

x2=x*c+y*s;

y2=y*c-x*s;

if(y2) return x2%y2;

return 0;
```
I think it was just a simple experiment, trying to cache a couple of functions of t. The spectrum was probably off because it was an older version of EvalDraw (hence the "globs"). I can't remember for the life of me why I have a screenshot of it...
krick at 2005-08-04 12:43
Awesoken said
Thanks to everyone who sent me test files - they were very helpful!
No, thank YOU for spending your valuable time time fixing the bug.
I'm sure that I speak for KZIP fans everywhere when I say thank you.
callmeace at 2005-08-16 22:37
Thanks from me too Ken, it's been a pleasure to use some of your excellent utilities, with my favourite being KZip :)