With the static huffman table, the decompressed output is very similar from what you'd get with this algorithm:
loop:
chance to exit
chance to output a random byte
chance to repeat some previous bytes
If decompression succeeds, the chance that 95% of the output can disassemble is not very different from random noise, except sometimes it'll get lucky and repeat a valid opcode 120 times so maybe it's slightly higher.
But the chance that 100% can disassemble gets more complicated. It's two factors multiplied together, the chance decompression succeeds, and then the chance that the output can disassemble.
If decompression is successful, the output will have a lot fewer random bytes than 128. The repetitions have some impact, but less impact. So the chance that the output disassembles should be higher than the chance 128 random bytes disassemble.
With DEFLATE in particular, decompression fails 95+% of the time, so the overall odds of decompress+decode suck.
This is partially mitigated by DEFLATE exiting early a lot of the time, but only partially.
If you made a DEFLATE-like decompressor that crashes less and exits early more often, it would win by a mile.
If you made a DEFLATE-like decompressor that crashes rarely but doesn't exit early, it would likely be able to win the 100% decoding test. Some of the random bytes go into the output, some get used up on less dangerous actions than outputting random bytes, overall success rate goes up.
In common anecdotal experience with disassembling code, it is very common for data areas interspersed with code (like string literals) to disaassemble to instructions, momentarily causing the human to be puzzled: what is this repetition of five "or" instructions doing here referencing registers that would never be arguments?
The reason is that the opcode encoding is very dense, and has no redundancy against detecting bad encodings, and usually no relationship to neighboring words.
By that I mean that some four byte chunk (say) treated as an opcode word is treated that way regardless of what came before or what comes after. If it looks like an opcode with a four-byte immediate operand, then the disassembly will pull in that operand (which can be any bit combination) and skip another four bytes. Nothing in the operand will indicate "this is a bad instruction overall".
But look, it almost looks as if the Static Huffman (a simpler encoding of compression with fewer decoding errors) almost bears out a certain aspect of the friend's intuition, in the following way:
* only 4.4% of the random data disassembles.
* only 4.0% of the random data decodes as Static Huffman.
BUT:
* 1.2% of the data decompresses and disassembles.
Relative to the 4.0% decompression, 1.2% is 30%.
In other words, 30% of successfully decompressed material also disassembles.
That's something that could benefit from an explanation.
Why is that, evidently, the conditional probability of a good disassemble, given a successful Static Huffman expansion, much higher than the probability of a disassemble from random data?
There's an important number that's missing here, which is how many of the 128 bytes were consumed in that test.
With 40 million "success" and 570 "end of stream", I think that implies that out of a billion tests it read all 128 bytes less than a thousand times.
As a rough estimate off the static huffman tables, each symbol gives you about an 80% chance of outputting a byte, 18% chance of crashing, 1% chance of repeating some bytes, and 1% chance of ending decompression. As it gets longer the odds tilt a few percent more toward repeating instead of crashing. But on average it's going to use quite few of the 128 bytes of input, outputting them in a slightly shuffled way plus some repetitions.
How it should probably work is like a tokenizer. Recognize the longest prefix of the remaining input that can Huffman-decode. Remove that input, and repeat.
Even that won't find the maximal amount of decoding that is possible; for that you have to slide through the input bit by bit and try decoding at every bit position.
However, it seems fair because you wouldn't disassemble that way. If you disassemble some bytes successfully, you skip past those and keep going.
Another interesting thing… random data has a high likely hood of disassembling into random instructions, but there’s a low probability that such instructions (particularly sequences of such instructions) are valid semantically.
For example, there’s a very high chance a single random instruction would page fault.
If you want to generate random instructions and have them execute, you have to write a tiny debugger, intercept the page faults, fix up the program’s virtual memory map, then re-run the instruction to make it work.
This means that even though high entropy data has a good chance of producing valid instructions, it doesn’t have a high chance of producing valid instruction sequences.
Code that actually does something will have much much lower entropy.
That is interesting…even though random data is syntactically valid as instructions, it’s almost certainly invalid semantically.
Why the AI disclosure? Is it just for the author to make sure the readers know they are AI-skeptic and use the opportunity to link to another article, or would there be something wrong with the proof had AI been used to help write the code?
(By help I mean just help, not write an entire sloppy article.)
Hey, I wrote this! There are a couple of reasons that I included the disclosure.
The main one is to set reader expectations that any errors are entirely my own, and that I spent time reviewing the details of the work. The disclosure seemed to me a concise way to do that -- my intention was not any form of anti-AI virtue signaling.
The other reason is that I may use AI for some of my future work, and as a reader, I would prefer a disclosure about that. So I figured if I'm going to disclose using it, I might as well disclose not using it.
I linked to other thoughts on AI just in case others are interested in what I have to say. I don't stand to gain anything from what I write, and I don't even have analytics to tell me more people are viewing it.
All in all, I was just trying to be transparent, and share my work.
That's nice to hear. For me personally, I don't really care what tools the author uses to write the article, as long as the author takes responsibility! Yes, that means I'll blame you for everything I see in the article :P
Your actor analogy in your other post about AI doesn't really work when it comes to using LLMs for coding, at least. LLMs are pretty good at writing working code, especially given suitable guidance. An actor wouldn't be able fake their way through that.
It's like "pesticide use disclosure: our blueberries are 'no spray'; but we are not insinuating there is anything wrong with pesticides."
:)
I like it!
But, here it does serve a purpose beyond hinting at the author's ideological stance.
Nowadays, a lot of readers will wonder how much of your work is AI assisted. Their eyes will be drawn to the AI Use Disclosure, which will answer their question.
With the static huffman table, the decompressed output is very similar from what you'd get with this algorithm:
If decompression succeeds, the chance that 95% of the output can disassemble is not very different from random noise, except sometimes it'll get lucky and repeat a valid opcode 120 times so maybe it's slightly higher.But the chance that 100% can disassemble gets more complicated. It's two factors multiplied together, the chance decompression succeeds, and then the chance that the output can disassemble.
If decompression is successful, the output will have a lot fewer random bytes than 128. The repetitions have some impact, but less impact. So the chance that the output disassembles should be higher than the chance 128 random bytes disassemble.
With DEFLATE in particular, decompression fails 95+% of the time, so the overall odds of decompress+decode suck.
This is partially mitigated by DEFLATE exiting early a lot of the time, but only partially.
If you made a DEFLATE-like decompressor that crashes less and exits early more often, it would win by a mile.
If you made a DEFLATE-like decompressor that crashes rarely but doesn't exit early, it would likely be able to win the 100% decoding test. Some of the random bytes go into the output, some get used up on less dangerous actions than outputting random bytes, overall success rate goes up.
In common anecdotal experience with disassembling code, it is very common for data areas interspersed with code (like string literals) to disaassemble to instructions, momentarily causing the human to be puzzled: what is this repetition of five "or" instructions doing here referencing registers that would never be arguments?
The reason is that the opcode encoding is very dense, and has no redundancy against detecting bad encodings, and usually no relationship to neighboring words.
By that I mean that some four byte chunk (say) treated as an opcode word is treated that way regardless of what came before or what comes after. If it looks like an opcode with a four-byte immediate operand, then the disassembly will pull in that operand (which can be any bit combination) and skip another four bytes. Nothing in the operand will indicate "this is a bad instruction overall".
Every reverse engineer learns very quickly that "add [rax], al" has the machine code representation "00 00".
Or "add [bx+si], al" for those from an earlier era.
But look, it almost looks as if the Static Huffman (a simpler encoding of compression with fewer decoding errors) almost bears out a certain aspect of the friend's intuition, in the following way:
* only 4.4% of the random data disassembles.
* only 4.0% of the random data decodes as Static Huffman.
BUT:
* 1.2% of the data decompresses and disassembles.
Relative to the 4.0% decompression, 1.2% is 30%.
In other words, 30% of successfully decompressed material also disassembles.
That's something that could benefit from an explanation.
Why is that, evidently, the conditional probability of a good disassemble, given a successful Static Huffman expansion, much higher than the probability of a disassemble from random data?
There's an important number that's missing here, which is how many of the 128 bytes were consumed in that test.
With 40 million "success" and 570 "end of stream", I think that implies that out of a billion tests it read all 128 bytes less than a thousand times.
As a rough estimate off the static huffman tables, each symbol gives you about an 80% chance of outputting a byte, 18% chance of crashing, 1% chance of repeating some bytes, and 1% chance of ending decompression. As it gets longer the odds tilt a few percent more toward repeating instead of crashing. But on average it's going to use quite few of the 128 bytes of input, outputting them in a slightly shuffled way plus some repetitions.
How it should probably work is like a tokenizer. Recognize the longest prefix of the remaining input that can Huffman-decode. Remove that input, and repeat.
Even that won't find the maximal amount of decoding that is possible; for that you have to slide through the input bit by bit and try decoding at every bit position.
However, it seems fair because you wouldn't disassemble that way. If you disassemble some bytes successfully, you skip past those and keep going.
Another interesting thing… random data has a high likely hood of disassembling into random instructions, but there’s a low probability that such instructions (particularly sequences of such instructions) are valid semantically.
For example, there’s a very high chance a single random instruction would page fault.
If you want to generate random instructions and have them execute, you have to write a tiny debugger, intercept the page faults, fix up the program’s virtual memory map, then re-run the instruction to make it work.
This means that even though high entropy data has a good chance of producing valid instructions, it doesn’t have a high chance of producing valid instruction sequences.
Code that actually does something will have much much lower entropy.
That is interesting…even though random data is syntactically valid as instructions, it’s almost certainly invalid semantically.
Why the AI disclosure? Is it just for the author to make sure the readers know they are AI-skeptic and use the opportunity to link to another article, or would there be something wrong with the proof had AI been used to help write the code?
(By help I mean just help, not write an entire sloppy article.)
Hey, I wrote this! There are a couple of reasons that I included the disclosure.
The main one is to set reader expectations that any errors are entirely my own, and that I spent time reviewing the details of the work. The disclosure seemed to me a concise way to do that -- my intention was not any form of anti-AI virtue signaling.
The other reason is that I may use AI for some of my future work, and as a reader, I would prefer a disclosure about that. So I figured if I'm going to disclose using it, I might as well disclose not using it.
I linked to other thoughts on AI just in case others are interested in what I have to say. I don't stand to gain anything from what I write, and I don't even have analytics to tell me more people are viewing it.
All in all, I was just trying to be transparent, and share my work.
That's nice to hear. For me personally, I don't really care what tools the author uses to write the article, as long as the author takes responsibility! Yes, that means I'll blame you for everything I see in the article :P
Your actor analogy in your other post about AI doesn't really work when it comes to using LLMs for coding, at least. LLMs are pretty good at writing working code, especially given suitable guidance. An actor wouldn't be able fake their way through that.
It's like "pesticide use disclosure: our blueberries are 'no spray'; but we are not insinuating there is anything wrong with pesticides."
:)
I like it!
But, here it does serve a purpose beyond hinting at the author's ideological stance.
Nowadays, a lot of readers will wonder how much of your work is AI assisted. Their eyes will be drawn to the AI Use Disclosure, which will answer their question.
I believe this is the third or fourth posting of this article in the last week.
Yep: https://news.ycombinator.com/from?site=jstrieb.github.io