4 ms·

Minlzma – Minimal LZMA Project

49 points by MikusR 6y ago

nayuki 6y ago
In a similar spirit, I wrote a simple decompressor for DEFLATE. Here is around 500 lines of Python code: https://github.com/nayuki/Simple-DEFLATE-decompressor/tree/master/python https://github.com/nayuki/Simple-DEFLATE-decompressor/tree/m... DEFLATE is a ubiquitous compression format that is used in ZIP, GZIP, PNG, Git, and more. It is decades old and much less space-efficient than LZMA.
- cxr 6y ago
  This is great. I poked around your site, too, and just subscribed to your feed. You have a really great style, and I like the charter you establish in your GitHub profile. Please keep doing what you're doing.
asveikau 6y ago
> The entire input stream must be available (multi-call/streaming mode are not supported) > The entire output buffer must be allocated with a fixed size -- however, callers are able to query the required size I have not seen a compression library ask for this before. Chunk-at-a-time is not supported? Whole file in RAM? So no-go for memory constrained environments or large files? This is from the Windows Internals guy? His reputation is pretty good, maybe I am missing something here. Edit: The code also keeps the input buffer in a global variable. Weird. I am going to guess he has a very specific use case in mind for this library, like a bootloader or something, where memory management and multiple files are not as important because you decode once and throw out everything shortly after.
- badsectoracula 6y ago
  One use case that came immediately to my mind is virtual texturing (think megatextures like in id Tech 5) or virtual geometry (...which in current hardware can be implemented via virtual texturing). The texture pages can take a TON of disk space so compressing those is important. But you can load (or mmap) the entirety of each page and you know beforehand how big each page will be in memory. (though all that assumes LZMA decompression is fast enough)
- zmodem 6y ago
  Not supporting streaming decompression simplifies the implementation a lot, which seems to fit well with the project's goals (hwzip does this too: https://www.hanshq.net/zip.html https://www.hanshq.net/zip.html). It should still work with large files on systems where they can be memory mapped.
LeoPanthera 6y ago
Worth reminding ourselves that the xz container format is awful. Actually, a lot of people don't realise that xz is a container, and not the compression format. https://www.nongnu.org/lzip/xz_inadequate.html https://www.nongnu.org/lzip/xz_inadequate.html
- asveikau 6y ago
  Been a while since I read this, but at the time I recall thinking... Some of the comments on corruption and CRCs seem less relevant in a world where the block layer does better. For example if you store xz files on ZFS.
  - Zardoz84 6y ago
    and if you are downloading it from some place on Internet?
    - asveikau 6y ago
      Then I suppose the best they can hope for are hardware packet checksums, tcp checksums, in some cases TLS will also flag corruption in transit, then it's on them to have a sane storage layer underneath. But for the specific scenario cited of historical archivists and preservation, I think it's reasonable to say "run zfs or a similar solution and closely monitor/replace the disks over time". That sounds more likely to work than building resilience into the equivalent of .zip and hoping those tools will recover such an error.
- jl6 6y ago
  This is a polemic written by the author of a competing tool. You can tell xz isn’t so bad by the complete absence of any real world report of xz causing issues.
  - saagarjha 6y ago
    The only experience I have had with xz is uncompressing Apple’s Xcode archives. All I know about that is that it takes forever to do some sort of useless “signature verification”.
phoe-krk 6y ago
It's good that this happened! The original LZMA sources from Peter Pavlov are highly condensed and unreadable; they contain little to no comments and are hard to understand, and therefore reverse engineer.
- juskrey 6y ago
  Oh man, in my times "reverse engineer" was something about restoring functionality from compiled compressed (with some homebrew compressor) encrypted obfuscated binary executable, which could possibly actively resist to in-memory debugging.
  - phoe-krk 6y ago
    Here I used it in context of heavily optimized, little commented and very dense source code, which has some resemblance to the "encrypted obfuscated binary" that you mention.
    - juskrey 6y ago
      Okok, I agree - my old skills in all of that often help with modern, especially business software, a lot.
jankotek 6y ago
Interesting. What sort of testing you do? How is performance compared to original version?

49 points by MikusR 6y ago

In a similar spirit, I wrote a simple decompressor for DEFLATE. Here is around 500 lines of Python code: https://github.com/nayuki/Simple-DEFLATE-decompressor/tree/master/python https://github.com/nayuki/Simple-DEFLATE-decompressor/tree/m... DEFLATE is a ubiquitous compression format that is used in ZIP, GZIP, PNG, Git, and more. It is decades old and much less space-efficient than LZMA.

cxr 6y ago
This is great. I poked around your site, too, and just subscribed to your feed. You have a really great style, and I like the charter you establish in your GitHub profile. Please keep doing what you're doing.

asveikau 6y ago

> The entire input stream must be available (multi-call/streaming mode are not supported) > The entire output buffer must be allocated with a fixed size -- however, callers are able to query the required size I have not seen a compression library ask for this before. Chunk-at-a-time is not supported? Whole file in RAM? So no-go for memory constrained environments or large files? This is from the Windows Internals guy? His reputation is pretty good, maybe I am missing something here. Edit: The code also keeps the input buffer in a global variable. Weird. I am going to guess he has a very specific use case in mind for this library, like a bootloader or something, where memory management and multiple files are not as important because you decode once and throw out everything shortly after.

badsectoracula 6y ago
One use case that came immediately to my mind is virtual texturing (think megatextures like in id Tech 5) or virtual geometry (...which in current hardware can be implemented via virtual texturing). The texture pages can take a TON of disk space so compressing those is important. But you can load (or mmap) the entirety of each page and you know beforehand how big each page will be in memory. (though all that assumes LZMA decompression is fast enough)
zmodem 6y ago
Not supporting streaming decompression simplifies the implementation a lot, which seems to fit well with the project's goals (hwzip does this too: https://www.hanshq.net/zip.html https://www.hanshq.net/zip.html). It should still work with large files on systems where they can be memory mapped.

LeoPanthera 6y ago

Worth reminding ourselves that the xz container format is awful. Actually, a lot of people don't realise that xz is a container, and not the compression format. https://www.nongnu.org/lzip/xz_inadequate.html https://www.nongnu.org/lzip/xz_inadequate.html

asveikau 6y ago
Been a while since I read this, but at the time I recall thinking... Some of the comments on corruption and CRCs seem less relevant in a world where the block layer does better. For example if you store xz files on ZFS.
- Zardoz84 6y ago
  and if you are downloading it from some place on Internet?
  - asveikau 6y ago
    Then I suppose the best they can hope for are hardware packet checksums, tcp checksums, in some cases TLS will also flag corruption in transit, then it's on them to have a sane storage layer underneath. But for the specific scenario cited of historical archivists and preservation, I think it's reasonable to say "run zfs or a similar solution and closely monitor/replace the disks over time". That sounds more likely to work than building resilience into the equivalent of .zip and hoping those tools will recover such an error.
jl6 6y ago
This is a polemic written by the author of a competing tool. You can tell xz isn’t so bad by the complete absence of any real world report of xz causing issues.
- saagarjha 6y ago
  The only experience I have had with xz is uncompressing Apple’s Xcode archives. All I know about that is that it takes forever to do some sort of useless “signature verification”.

phoe-krk 6y ago

It's good that this happened! The original LZMA sources from Peter Pavlov are highly condensed and unreadable; they contain little to no comments and are hard to understand, and therefore reverse engineer.

juskrey 6y ago
Oh man, in my times "reverse engineer" was something about restoring functionality from compiled compressed (with some homebrew compressor) encrypted obfuscated binary executable, which could possibly actively resist to in-memory debugging.
- phoe-krk 6y ago
  Here I used it in context of heavily optimized, little commented and very dense source code, which has some resemblance to the "encrypted obfuscated binary" that you mention.
  - juskrey 6y ago
    Okok, I agree - my old skills in all of that often help with modern, especially business software, a lot.

jankotek 6y ago

Interesting. What sort of testing you do? How is performance compared to original version?