 So, for a little project I needed to compress a bit of data, and @cancel and I made up a spec that should be possible to implemented on small systems without too much headaches. I wrote a bit of documentation for it, and I was wondering if anyone wanted to put the docs to the test and see if they could write a toy implementation in a language of their choice. It'd help me see if there's things missing in the docs. http://wiki.xxiivv.com/site/ulz_format So, think of it as a little puzzle. 42 comments
@neauoire @cancel A couple of things that are tripping me : Example: an offset of 0 means go back by 1 bytes into the history. And the pointer is the at the end of the dictionary buffer yep. I'll add a bit about the negative increment to the offset to the docs! thanks for pointing it out @neauoire @cancel one potential issue I see which may not be an issue is syncronisation. if my “read” alignment is 1 byte, and for whatever reason the read pointer ends up on the second byte of a cpy2 instruction, (perhaps due to input file corruption) it won’t necessarily be obvious that byte is not a lit, cpy1 or the first byte of a cpy2 instruction. it is my understanding that dysyncing is a potential risk of variable byte encodings @zens @cancel is your issue that it's not resilient to data corruption? In the wider system implementation we have a checksum. Do you think would be enough? @neauoire @cancel it’s more that those leading bits remind me of the leading bits of utf-8, why utf-8 was designed that way- and that if this were following the utf-8 pattern, cpy2 would have 110 as the leading bits for both of its bytes. I am not saying you should do that, but have a look at why utf-8 did it that way. (from memory, line transmission corruption can either take out a few characters as long as sync is maintained… or the entire rest of your file if it is not)
[DATA EXPUNGED]
  @neauoire @cancel I've made a little implementation in Go : https://github.com/max22-/ulz-go @maxime_andre @cancel ah! that trips many people, how would you explain this so others aren't tripped by it? Thanks to everyone who answered my puzzle and wrote experimental implementations of our little LZ scheme! You've helped us improved the documentation and see how portable of an algorithm it is across multiple languages! @nicolagi nono it's all good :) I've since added a longer example to the repo(as to not clog the documentatio) It's good, I wanted to have a way to benchmark CPY2 as well! @dichotomiker @cancel Here's the encoder and decoder so you can try with an example of your own to see where it fails. @neauoire @dichotomiker you should put a note that the encoder in uxn-utils is unsafe and the one from Uxn32 should be used for real software @cancel @dichotomiker sure, would you like to make a standalone file in the repo that I can link people to? @cancel I mean with build instructions and main(), so people can build it without too much fussing with it as a library. @neauoire nice :) The reason I haven't made an example standalone program in C for it in the Uxn32 repo is that none of the Uxn32 code currently uses the C standard library, and doing a cross-platform cmd line program that does file operations would require to suddenly switch to using it. Not the end of the world but… well maybe I'll do it eventually. @cancel ah! I didn't know that. Good to know, yeah I'll bring the ref implementation and make a README for it! @neauoire sorry, I didn't document how to use the streaming decompressor yet. (Having to swap hard drives to work on Uxn32 is turning out to be pretty inconvenient...)  Have you considered including 'magic-bytes' with your ULZ file format? ... The usage of it would be — If someone doesn't know what the file-name is, they could still determine the type of the file. ... It could be something as simple as the first by 7 bytes of the file format being: 55 4C 5A 2F 31 0D 0A Which, if interpreted as ASCII or Unicode UTF-8 would be: "ULZ/1\r\n" ... Here are magic bytes for other file formats: https://en.wikipedia.org/wiki/List_of_file_signatures . |
Gregory's Server
@neauoire @cancel trying my hand at a C# version of this!