DeflOpt thread

[fred01]

I'm having trouble downloading files from your page.  It looks like your web server is sending a content type of "html" for "7z" files.  When I click on one of the download links, IE shows me the contents of the file instead of prompting me with the download dialog.  It's possible that there's a problem with IE on my end but I just wanted to check if anyone else is seeing the same thing.

It also confuses my Firefox v2. May be this is a limitation of the server that uses html for unknown content types?

[Zardalu]

When I click on one of the download links, IE shows me the contents of the file instead of prompting me with the download dialog...

Thanks. Fixed.

Ben Jos.

[Martin]

I think it’s better to use application/x-7z-compressed instead of unknown/nothing.

[Zardalu]

I think it’s better to use application/x-7z-compressed instead of unknown/nothing.

Thank you! Changed it.

Ben Jos.

[counting_pine]

Hi Ben Jos,
Do you have any idea why DeflOpt throws an error on this image?
http://img405.imageshack.us/my.php?image=colorspaceg6r5b5tf3.png

I get the message: "ERROR: End of input without encountering EOB!?!?!?."

[Zardalu]

Hi Ben Jos,
Do you have any idea why DeflOpt throws an error on this image?
http://img405.imageshack.us/my.php?image=colorspaceg6r5b5tf3.png

I get the message: "ERROR: End of input without encountering EOB!?!?!?."

Hmm... I'll look into it. Meanwhile, if you want to make it smaller, you still can:

Code:

C:\INTERNET\DOWNLOAD>pngout colorspaceg6r5b5tf3.png
 In:     685 bytes               colorspaceg6r5b5tf3.png /c2 /f5
Out:     672 bytes               colorspaceg6r5b5tf3.png /c2 /f5
Chg:     -13 bytes ( 98% of original)

C:\INTERNET\DOWNLOAD>deflopt color*.png

***                 DeflOpt V2.05                 ***
***       Built on Sat Mar 10 10:03:30 2007       ***
***  Copyright (C) 2003-2007 by Ben Jos Walbeehm  ***



"C:/INTERNET/DOWNLOAD/colorspaceg6r5b5tf3.png"
Number of bytes saved: 1 (672 --> 671)
File rewritten.


Number of files processed  :        1
Number of files rewritten  :        1
Total number of bytes saved:        1
19,501,792 cycles.

Thanks for letting me know! I'll post more when I find out more.

Ben Jos.

[Zardalu]

Hi Ben Jos,
Do you have any idea why DeflOpt throws an error on this image?
http://img405.imageshack.us/my.php?image=colorspaceg6r5b5tf3.png

I get the message: "ERROR: End of input without encountering EOB!?!?!?."

This is fixed in version 2.06, which I have just released. Thanks for reporting!

Ben Jos.

[counting_pine]

Thanks, it's working now.  Hope it wasn't too hard to track down.
Do you mind if I ask why it was happening?  Or would I need intimate knowledge of the program's inner workings to understand?

[Zardalu]

Thanks, it's working now.  Hope it wasn't too hard to track down.
Do you mind if I ask why it was happening?  Or would I need intimate knowledge of the program's inner workings to understand?

Deflated data consists of codes of varying lengths. These lengths can be anywhere from 1 to 15 bits. When parsing deflated data, you could do it by getting one bit at a time from the input until you have a valid code, then decode it, process it, and then repeat this for the next code and so on. This works nicely, but is very slow. So instead of getting one bit at a time, my parser actually looks at the next 15 bits and determines what the next code is from that. This can be implemented in a way that is much faster than the one-bit-at-a-time method.

My code has a buffer that contains bits that the parser has read, but not used yet. Whenever there are not enough bits in this buffer, it keeps reading one byte (8 bits) at a time from the input and adding those 8 bits to the buffer until there are enough bits in the buffer. An example: At the very start the buffer is empty and let's say the parser wants to look at the next 15 bits. So it reads one byte from the input and puts it in the buffer. Then there are 8 bits in the buffer. Still not enough, so it reads another byte and adds those bits to the buffer as well. Now there are 16 bits in the buffer. The parser looks at the first 15 bits and let's say it finds that the first code is 4 bits long. It would then process that code and discard those 4 bits from the buffer. So then the buffer contains 12 unused bits.

This works nicely until it gets to the end of the input. When it reaches the end of the input and wants to look at the next 15 bits, the input might not contain that many bits anymore. So when it cannot read a byte from the input anymore to be added to the buffer, it adds a dummy zero-byte to the buffer (so 8 zero-bits). It adds this dummy byte only once because otherwise, in case the deflated data is corrupt, keeping adding dummy bytes could result in an infinite loop. In the case of this particular PNG, this went wrong. I'll simplify the explanation of what actually happened here. What actually happened was a lot more rare but more complicated to explain. The simplified explanation still is very close to what actually happened:

Towards the end of parsing the deflated data, at some point, there were 6 unused bits left in the buffer and no more bytes in the input. The parser wanted to look at the next 15 bits, and since there were not enough bits in the buffer, and since it had just read the last byte of the input, it added a dummy zero-byte. So then there were 14 bits in the buffer. But it needed 15. It had already added a dummy zero-byte, so it would not add more. It then ended the parsing loop, saw that it had not encountered the final "End Of Block" code and exited with an error. In fact, the 6 unused bits that were initially left in the buffer exactly constituted that EOB code (so the deflated data was not corrupt), but the parser could never see it.

The fix was easy: Instead of adding ONLY ONE dummy zero-byte (8 zero-bits), it now adds ONLY ONE dummy zero-word (16 zero-bits) when it has reached the end of the input.

Ben Jos.

[counting_pine]

Thanks, that makes a lot of sense.  I've written some inflate code before and I'm aware of the problem, but my code was PNG specific, and I had 32 bits worth of checksum to parse at the end, so it wasn't something I had to work around.

I'm still intrigued about why this case was so rare.  Is it much more complicated?

[Its`about]

This programme is great, not only in that it can achieve close to what kzip does with -r in a fraction of the time (that is, after using kzip without -r), but that it works on gz too.

A feature request, if I may: Matroska container level support. Even after using Matroska, I still manage to compress it by another 2-4MB with kzip, which is annoying, in that I can't do that at the container level.

Another feature request would be native Linux support but, I think that'd be pushing my luck

[Zardalu]

This programme is great, not only in that it can achieve close to what kzip does with -r in a fraction of the time (that is, after using kzip without -r), but that it works on gz too.

A feature request, if I may: Matroska container level support. Even after using Matroska, I still manage to compress it by another 2-4MB with kzip, which is annoying, in that I can't do that at the container level.

Another feature request would be native Linux support but, I think that'd be pushing my luck

I think you misunderstood what DeflOpt does and does not do. DeflOpt is NOT an archiver like kzip. It can NOT do compression on its own. Rather, it grew from an archiver I wrote (called BJWFlate) many years ago. I found that there were a few optimisation algorithms that I used in BJWFlate that no other archivers used.

The easiest way to explain DeflOpt, maybe, is this: (1) Take one or more files. (2) Compress them with your favourite utility or set of utilities. (3) Run DeflOpt.

No matter which utility you use, DeflOpt can usually use the "hard work" that archivers did and improve on that. So you can use archiver A and compress it down to 20 kB. DeflOpt will usually be able to make it a few bytes smaller. Use archiver B (let's say it's Ken's kzip) and compress it down to 10 kB. DeflOpt will usually be able to make it a few bytes smaller.

So: DeflOpt is NOT an archiver. It simply takes the hard work done by other archivers and tries to improve on that. If you think that when utility A compresses something to 20 kB and kzip can do it in 10 kB and DeflOpt can make kzip's result 10 bytes smaller, yes that's true, but DeflOpt will NOT be able to take utility A's compression and make it even compete with what kzip can do "natively".

If you understood my explanation, you will now also understand why DeflOpt will never be able to help you on your Matroska request.

Your 3rd request: Yes, I could probably make DeflOpt versions for Linux, Mac, and other platforms. Or have someone else more knowledgeable with those platforms port my code. But only 1 or 2 people are interested. Not enough for me.

It reminds me of when I wrote a uudecoder back in early 90s (UU.COM). I got literally thousands of e-mails telling me that mine was the best and so on and that they would gladly pay for it, but it was free. Many people asking me for ports for Linux. I made it shareware for 5 dollars, shortly after that. All the thousands of people, where were they then? I think I got around 50 people who registered.

I'm not in this game to become rich and famous. On the other hand, my experience with UU.COM and one or two things before and after that have made me very reluctant to share my code.

Ben Jos.

[Zardalu]

I'm still intrigued about why this case was so rare.  Is it much more complicated?

Well, I don't always read 15 bits ahead, but rather, the number of bits of the longest code. In lots of cases, this will be 15 and in lots of cases, this number is also (obviously!) the length of the EOB code. In this particular case, that number was 6. No problem there. But it had two codes ahead of it both of length 1. That's what made it rare.

Ben Jos.

[Its`about]

This programme is great, not only in that it can achieve close to what kzip does with -r in a fraction of the time (that is, after using kzip without -r), but that it works on gz too.

A feature request, if I may: Matroska container level support. Even after using Matroska, I still manage to compress it by another 2-4MB with kzip, which is annoying, in that I can't do that at the container level.

Another feature request would be native Linux support but, I think that'd be pushing my luck

I think you misunderstood what DeflOpt does and does not do. DeflOpt is NOT an archiver like kzip. It can NOT do compression on its own. Rather, it grew from an archiver I wrote (called BJWFlate) many years ago. I found that there were a few optimisation algorithms that I used in BJWFlate that no other archivers used.

The easiest way to explain DeflOpt, maybe, is this: (1) Take one or more files. (2) Compress them with your favourite utility or set of utilities. (3) Run DeflOpt.

No matter which utility you use, DeflOpt can usually use the "hard work" that archivers did and improve on that. So you can use archiver A and compress it down to 20 kB. DeflOpt will usually be able to make it a few bytes smaller. Use archiver B (let's say it's Ken's kzip) and compress it down to 10 kB. DeflOpt will usually be able to make it a few bytes smaller.

So: DeflOpt is NOT an archiver. It simply takes the hard work done by other archivers and tries to improve on that. If you think that when utility A compresses something to 20 kB and kzip can do it in 10 kB and DeflOpt can make kzip's result 10 bytes smaller, yes that's true, but DeflOpt will NOT be able to take utility A's compression and make it even compete with what kzip can do "natively".

If you understood my explanation, you will now also understand why DeflOpt will never be able to help you on your Matroska request.

Ben Jos.

I think you've misunderstood yourself I'm asking you to add support for optimising container level compression. Mkvtoolsnix uses zlib to compress matroska files at the container level (Matroska supports Deflate, LZO and bzip2, but players can only read Deflate at the moment), but the compression isn't exactly very good. I'm saying that I can draw this conclusion from having used kzip to further compress the files at the archive level. I want greater compression at the container level.

Edit: As for it only achieving a few bytes, I regularly get 1-2KiB shaved off PNGs with DeflOpt.

[Zardalu]

Ah, yes. I did some reading on Matroska and I indeed misunderstood. I guess I didn't understand the use of the word "container". In fact, a PNG file would be a container then too. It contains several chunks ("elements") and some of those may or may not be Deflated. In the case of PNG files, the chunks/elements that could (but not necessarily do) contain Deflated data are iCCP, iDAT, iTXt, and zTXt. And, on that same abstraction level, ZIP files are containers as well.

But I think that my original statement still holds. Yes, even if I extended DeflOpt to do .mkv (or .mks and .mka) files as well, I would ONLY be trying to improve upon zlib... not upon the several superior Deflate programs.

OK... here are my thoughts right now: (1) I HATE to write parsers. Parsers are just programs to follow a specification. There really is not much "innovation/challenge/talent" involved. "Everyone" can parse a file. Even more so since there are so many libraries available. They're like "cook book recipes". Which brings me to point 2: (2) If you take a look at Ken's code for just about ANY program he has written, you'll see that he pretty much never uses 3rd party libraries; he writes everything from scratch. I am very much the same way. I do not want to include the Matroska library or zlib or any library in my code. (If you want to really nitpick, you could say that both Ken and I still rely on the Microsoft Run-Time library...).

I can see how DeflOpt could make Matroska files smaller, but I would have to study the Matroska file format specification first, write a parser for it. After having dealt with ZIP and PNG files, I'd rather write something more generic, something I have outlined some ideas about before: A tool that could convert any file using the Deflate format into the format most used (ZIP), then use tools such as ZipMax and zipmix to optimise them (with DeflOpt as a final step), then use the "inverse" of the tool to convert that file back into the original format. A tool like that could be written such that it would only rely on "script language" to indicate which "meta-fields" need to be modified. So a plug-in architechure.

Just think about it: Having a tool like that, converting the Deflated parts of Matroska files to regular ZIP format is a LOT better because then you could use ZipMax/zipmix to use hundreds of settings/programs to optimise the compression.

I guess the bottom line is that, yes, I could add Matroska support to DeflOpt, but it requires more work at this point than I am willing to put my very limited free time into...

Ben Jos.