4 ms·

The ancient Finnish predictor data compressor. Smallest compressor ever?

35 points by bugfix-66 4y ago

bugfix-66 4y ago
And the corresponding decompressor: https://bugfix-66.com/d548f3abf6faa823a829e4c770a8babca648a5fdcbf69f9a7ba385bb3199f8f0 https://bugfix-66.com/d548f3abf6faa823a829e4c770a8babca648a5... Does a simpler compressor/decompressor exist with comparable bits-per-byte performance?
- deleted 4y ago
  [deleted]
- JPLeRouzic 4y ago
  Is there some more info on this algorithm, who designed it, when, where? Is it related to: https://en.wikipedia.org/wiki/Prediction_by_partial_matching https://en.wikipedia.org/wiki/Prediction_by_partial_matching Or, considering the web site title, is there a bug in this algorithm? Thanks!
  - bugfix-66 4y ago
    This is a folk algorithm of unknown origin. All I know is the original author was probably a hacker from Finland and it was originally written in x86 assembly. This is my modernized implementation of his algorithm. As for solving the BUGFIX-66 puzzles, to fix the bug in the compressor, add to = append(to, 0) on the line after loc = len(to) The original code was not inserting a placeholder for every control byte. To fix the decompressor, add at++ on the line after ctrl := int(from[at]) The original code was not stepping past a control byte after loading it.
    - JPLeRouzic 4y ago
      Thank you!
    - asiekierka 4y ago
      Doe it literally check for the specific solution? Writing to = append(to, ctrl) which is functionally equivalent and, in my personal opinion, with clearer intent (ctrl = 0 at that point in the code), returns "incorrect". In fact, it seems that any placeholder value should work - as it is always overwritten by the final value of ctrl for a given set of bytes at the end; however, the checker rejects this.
      - bugfix-66 4y ago
        Your fix is wrong, so the site rejects it. Go doesn't do integer type conversions implicitly, to avoid the implicit-type-casting bugs endemic to C. Go (thankfully) doesn't allow an implicit conversion from int to byte. You must do the cast explicitly. So you would have to say to = append(to, byte(ctrl)) and that's correct. The site builds and executes the code you submit, and any correct solution is accepted.
  - CamperBob2 4y ago
    Seems like something that might have been written as an evolutionary step towards LZ77.
    - deleted 4y ago
      [deleted]
skybrian 4y ago
Fixing a bug in code like this isn’t the kind of problem that anyone should work on without tests. I guess you’re supposed to copy the code into your own environment and write tests?
- bugfix-66 4y ago
  No, a programmer should be able to read a small piece of code, understand the algorithm (especially given a summary in English), and understand what's wrong (a small, simple mistake). Some people will be better at this than others. Programming (algorithms, etc.) is not something everyone is equally good at. I wrote this puzzle after reading the x86 assembly original, which I believe was written in the 1980's. I never executed the original code, except in my mind, but I know how it works.
  - Mathnerd314 4y ago
    This is like saying you should be able multiply 4-digit numbers without a calculator. Is it possible? Yes. Is it something anybody uses outside of school? No. In practice it's a skill that's pretty much useless because using a calculator (or debugger in the case of OP) is both faster and easier. I myself got very good at mental arithmetic during math competitions, but 20 years later I find that I've forgotten most of the tricks because I never use it.
    - bugfix-66 4y ago
      You don't read code to understand it? You can't understand a small block of code without running it in a debugger? When you read code in a book, how do you understand it?
      - shirleyquirk 4y ago
        Hey friend, Humans are giving you feedback on your project. If your goal is for people to enjoy your cool thing, maybe listen?
zokier 4y ago
Just do a proper Show HN post if you want to push your thing on HN
- bugfix-66 4y ago
  The site is not finished yet, but each algorithm is interesting on its own. Look at my submission history: https://news.ycombinator.com/submitted?id=bugfix-66 https://news.ycombinator.com/submitted?id=bugfix-66 Really remarkable tiny algorithms like Martin Rem's almost-forgotten Union-Find, the tiny bitwise linear string search from approximate-grep, hash treaps, Quicksearch (the fastest sublinear string search in practice), a simple state-of-the-art arithmetic coder/decoder, space-filling curves, the Shortest Path Faster algorithm, etc. Next week I'll publish a fantastic generalization of bytewise integer encoding (like Varint or git's VLQ but better). I'll do a Show HN for the site itself some time next year.
  - ur-whale 4y ago
    Now do a real tiny, robust encryption algorithm.
    - bugfix-66 4y ago
      This was on the todo list: https://en.m.wikipedia.org/wiki/XXTEA https://en.m.wikipedia.org/wiki/XXTEA From one of the minds that brought you the Burrows-Wheeler transform. The problem is that the chosen plaintext attack is too cheap, so it's not interesting. But XXTEA is a historical curiosity like the Finnish predictor compressor, so maybe!
- imoreno 4y ago
  This is a good suggestion. The title makes it sound like an article about some lesser-known but interesting compression algorithm. Turns out it's a Go puzzle bank. Nothing wrong with that, but it would be less confusing to make that a bit more clear.
errantmind 4y ago
Definitely interesting as a puzzle, but personally I'd prefer a write-up on each of these novel algorithms, including what it is and how it works, with complete code. To each their own.

35 points by bugfix-66 4y ago

And the corresponding decompressor: https://bugfix-66.com/d548f3abf6faa823a829e4c770a8babca648a5fdcbf69f9a7ba385bb3199f8f0 https://bugfix-66.com/d548f3abf6faa823a829e4c770a8babca648a5... Does a simpler compressor/decompressor exist with comparable bits-per-byte performance?

deleted 4y ago
[deleted]
JPLeRouzic 4y ago
Is there some more info on this algorithm, who designed it, when, where? Is it related to: https://en.wikipedia.org/wiki/Prediction_by_partial_matching https://en.wikipedia.org/wiki/Prediction_by_partial_matching Or, considering the web site title, is there a bug in this algorithm? Thanks!
- bugfix-66 4y ago
  This is a folk algorithm of unknown origin. All I know is the original author was probably a hacker from Finland and it was originally written in x86 assembly. This is my modernized implementation of his algorithm. As for solving the BUGFIX-66 puzzles, to fix the bug in the compressor, add to = append(to, 0) on the line after loc = len(to) The original code was not inserting a placeholder for every control byte. To fix the decompressor, add at++ on the line after ctrl := int(from[at]) The original code was not stepping past a control byte after loading it.
  - JPLeRouzic 4y ago
    Thank you!
  - asiekierka 4y ago
    Doe it literally check for the specific solution? Writing to = append(to, ctrl) which is functionally equivalent and, in my personal opinion, with clearer intent (ctrl = 0 at that point in the code), returns "incorrect". In fact, it seems that any placeholder value should work - as it is always overwritten by the final value of ctrl for a given set of bytes at the end; however, the checker rejects this.
    - bugfix-66 4y ago
      Your fix is wrong, so the site rejects it. Go doesn't do integer type conversions implicitly, to avoid the implicit-type-casting bugs endemic to C. Go (thankfully) doesn't allow an implicit conversion from int to byte. You must do the cast explicitly. So you would have to say to = append(to, byte(ctrl)) and that's correct. The site builds and executes the code you submit, and any correct solution is accepted.
- CamperBob2 4y ago
  Seems like something that might have been written as an evolutionary step towards LZ77.
  - deleted 4y ago
    [deleted]

skybrian 4y ago

Fixing a bug in code like this isn’t the kind of problem that anyone should work on without tests. I guess you’re supposed to copy the code into your own environment and write tests?

bugfix-66 4y ago
No, a programmer should be able to read a small piece of code, understand the algorithm (especially given a summary in English), and understand what's wrong (a small, simple mistake). Some people will be better at this than others. Programming (algorithms, etc.) is not something everyone is equally good at. I wrote this puzzle after reading the x86 assembly original, which I believe was written in the 1980's. I never executed the original code, except in my mind, but I know how it works.
- Mathnerd314 4y ago
  This is like saying you should be able multiply 4-digit numbers without a calculator. Is it possible? Yes. Is it something anybody uses outside of school? No. In practice it's a skill that's pretty much useless because using a calculator (or debugger in the case of OP) is both faster and easier. I myself got very good at mental arithmetic during math competitions, but 20 years later I find that I've forgotten most of the tricks because I never use it.
  - bugfix-66 4y ago
    You don't read code to understand it? You can't understand a small block of code without running it in a debugger? When you read code in a book, how do you understand it?
    - shirleyquirk 4y ago
      Hey friend, Humans are giving you feedback on your project. If your goal is for people to enjoy your cool thing, maybe listen?

zokier 4y ago

Just do a proper Show HN post if you want to push your thing on HN

bugfix-66 4y ago
The site is not finished yet, but each algorithm is interesting on its own. Look at my submission history: https://news.ycombinator.com/submitted?id=bugfix-66 https://news.ycombinator.com/submitted?id=bugfix-66 Really remarkable tiny algorithms like Martin Rem's almost-forgotten Union-Find, the tiny bitwise linear string search from approximate-grep, hash treaps, Quicksearch (the fastest sublinear string search in practice), a simple state-of-the-art arithmetic coder/decoder, space-filling curves, the Shortest Path Faster algorithm, etc. Next week I'll publish a fantastic generalization of bytewise integer encoding (like Varint or git's VLQ but better). I'll do a Show HN for the site itself some time next year.
- ur-whale 4y ago
  Now do a real tiny, robust encryption algorithm.
  - bugfix-66 4y ago
    This was on the todo list: https://en.m.wikipedia.org/wiki/XXTEA https://en.m.wikipedia.org/wiki/XXTEA From one of the minds that brought you the Burrows-Wheeler transform. The problem is that the chosen plaintext attack is too cheap, so it's not interesting. But XXTEA is a historical curiosity like the Finnish predictor compressor, so maybe!
imoreno 4y ago
This is a good suggestion. The title makes it sound like an article about some lesser-known but interesting compression algorithm. Turns out it's a Go puzzle bank. Nothing wrong with that, but it would be less confusing to make that a bit more clear.

errantmind 4y ago

Definitely interesting as a puzzle, but personally I'd prefer a write-up on each of these novel algorithms, including what it is and how it works, with complete code. To each their own.