don't click here

Twizzler Compression

Discussion in 'Engineering & Reverse Engineering' started by MarkeyJester, Oct 19, 2016.

  1. MarkeyJester

    MarkeyJester

    Original, No substitute Resident Jester
    2,192
    405
    63
    Japan
    Update V201610270058:

    • Made some speed improvements (Should be about 5-10% faster now)
    • Converted some long-word instructions to word (long-word isn't necessary here)
    --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- ---

    A while ago, I was toying with the idea of making a PC game, and needed a compression format. I didn't want to use open compression formats like PNG for graphics, since that makes the art liable for hacking. So I needed a compression format that compressed as good as (if not better than) PNG, but was also unknown to the majority of the public.

    I've since given up the project, but did succeed in writing a fairly decent compression algorithm, that in most cases, did compress better than PNG (though, this is difficult to measure since PNG comes with an uncompressed bloated header...). But I figured it'd be really cool to have a 68k decompressor so that the compression could be used in hacks/homebrews.

    --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- ---

    Twizzler

    [​IMG]

    Twizzler is an LZSS compression format, with a sliding window of $20000 bytes, fitted with two huffman trees (one for retrace (offset), one for copy (length)).

    Twizzler
    Twizzler Moduled
    68k Source

    Provided above are two compressor/decompressor programs and a 68k decompression algorithm source.

    To use the compressors/decompressors, simply pass the file you want to compress/decompress, as the first argument (for the n00bs of you out there, just drag and drop the file(s) onto the program's icon, windows will do the rest...), it compresses/decompresses depending on the extention name. If the extension is ".twiz" or ".twim", the programs will decompress them to a ".bin" file, if the extension is NOT ".twiz" or ".twim", it'll compress them.

    So why are there two compressors? One is "Moduled", the other is not:

    • "Twizzler" (or ".twiz") is for data that is decompressed to 68k RAM
    • "Twizzler Moduled" (or ".twim") is for data that is decompressed to VDP VRAM (for example, art data)
    In simple terms, if you want to compress art/graphic data, use "TwizMod.exe", otherwise, use "Twizzler.exe". A moduled version is necessary because the sliding window is $20000 bytes, that's so large, it doesn't even fit in 68k RAM which is in total $10000 bytes. And so, it has been reduced to $1000 bytes.

    The 68k source file has two algorithms, one is normal, the other is for "Moduled", here is example code on using the normal decompression routine:

    Code (Text):
    1.         lea (TwizzlerData).l,a0         ; load compressed data address
    2.         lea ($00FF0000).l,a1            ; load 68k RAM location we want to decompress to
    3.         jsr TwizDec                 ; decompress and dump
    And here is example code on using the "Moduled" decompression routine:

    Code (Text):
    1.  
    2.         lea (TwizzlerArt).l,a0          ; load compressed art data address
    3.         move.w  #$2000,d0               ; set VRAM address to decompress to (2000)
    4.         jsr TwimDec                 ; decompress and dump to VRAM
    --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- ---

    Is it worth using?

    There's honestly no reason for me to tell you whether it's worth it for your needs, that's down to you to decide, give it a trial and decide for yourself.

    One thing I can say, is that it compresses smaller than Kosinski (even when using the best kosinski compressor known to date), in all known tests bar a few. I wouldn't however say it's faster than Kosinski, that would likely be far from the truth, I have however, optimised the 68k code to be as fast as possible, without going way too overboard, but maybe someone else can make improvements on speed/size to their liking. This format is meant for size rather than speed, so keep that in mind.

    The compressors however, are EXTREMELY fast, I spent months on them learning some major optimisation techniques for C, what you might find is the program will simply "flicker" on the screen, so don't blink!! I've considered writing a KENS series of programs actually, all of them seems to be "somewhat" slow, not that it's a problem though considering the files we're dealing with here are small and insignificant, but umm... I donno, let me know your thoughts on that...

    That about wraps it up!

    Happy hacking folks~

    --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- ---

    A very special thanks to Natsumi and MainMemory for some heavy tests, and bug reporting.

    Some of the bugs, I would never have noticed until months later~
     
  2. winterhell

    winterhell

    Member
    1,165
    7
    18
    While you can make your content harder to modify, if you are using OpenGL or DirectX( 99.99% of games on steam) then its trivial to rip the textures and sprites.

    The compressor sounds interesting.
     
  3. rata

    rata

    Member
    689
    72
    28
    Argentina
    Trying to be useful somehow.
    So, it could be added to KENSC too, right? A drag and drop KENSCT would be a really cool thing to have. At this point I have to say I'm lost among all different compression formats, correct me if I'm wrong:

    Nemesis: smallest files but slow
    Kosinski: really fast, bigger files
    Comper: faster than ligth and pretty small files?
    Twizzler: small files and... not too slow decompression?
    Enigma: hidden creddits??
    Saxman: ???
     
  4. AURORA☆FIELDS

    AURORA☆FIELDS

    The cute one here Tech Member
    216
    24
    18
    Finland
    AMPS
    I would correct that Enigma is especially great for plane mappings because it actually allows you to adjust the result of the compression without changing the input file! This is incredibly useful for mappings that you may want to move around. Kosinski, especially after the work Flamewing put to it, can actually produce really small files, even smaller than Nemesis in most cases! And it is still ways faster than Nemesis. In fact, its bigger brother, Kosinski Moduled format, which splits up files to 0x1000 byte segments for on-the-fly decompression of large files, does worse in compression ration and speed than Kosinski. I've used this format for a few hacks now, and I can report it basically is at least 10x faster than Nemesis and still takes less space. Comper produces bigger files than Nemesis in general, but its very lightweight and fast, and I've used this for a few hacks to make them load ways faster than the original game (in fact so fast I have to give some arbitrary delays just to give everything enough time to load!)

    Aside from that, I am really excited to try out Twizzler in an actual hack. I like the format so far and how well it works (after ironing out those bugs :V). I am just not sure with that large codebase, and reported slower speeds, that this can be useful aside from things like chunk compression and block compression.
     
  5. Clownacy

    Clownacy

    Tech Member
    1,053
    581
    93
    I suppose a way to look at it is, Nemesis is Huffman, Kosinski, Saxman and Comper are LZSS, Twizzler is kind of both(?), and Enigma is run-length. Kosinski's the powerful one that compresses well; Comper's weak but fast; Saxman, no clue, I imagine it's kind of in the middle, but it does have a special feature to generate '0's from nothing. I believe Nemesis has a quirk where compressed data must be a multiple of 0x20, making it only useful for tiles (and a type of level mapping, in Sonic CD?), and it's in general the powerful. but extremely slow, one. I think I've compressed S1's zone art with Kosinski, and had worse results than with Nemesis. Heck, I think I got bad results from compressing the 16x16s with Kosinski instead of Enigma.
     
  6. AURORA☆FIELDS

    AURORA☆FIELDS

    The cute one here Tech Member
    216
    24
    18
    Finland
    AMPS
    So I decided to conduct a little experiment; compress all Sonic 1 nemesis art files to different formats. Here's the rundown (in bytes):
    Uncompressed - 357344
    Enigma - 282352
    Comper - 203592
    Nemesis - 167170
    Rocket - 165855
    Saxman - 164211
    Kosinski Moduled - 151338
    Kosinski - 144302
    Twizzler Moduled - 140658
    Twizzler - 139368
     
  7. MarkeyJester

    MarkeyJester

    Original, No substitute Resident Jester
    2,192
    405
    63
    Japan
    Oh yeah, no, I'm not worried about people "ripping" the textures out of the game (hell you could print screen the visuals and get em that way), my concern is "modifying" the graphics in the game...

    ...it doesn't matter though, the game isn't a thing anyway.

    My god, you know what? I am so sorry, I had completely forgotten to credit you & MainMemory for bug testing...

    *fixes*

    Nemesis' format is actually RLE, on the scale of nybbles rather than bytes or words or whatever (which makes sense considering the pixels of graphics are nybbles), it does have a huffman tree though, which contains the most occuring RLE instances (which should be arranged in order of "most reduce-able memory"). This format is definately designed specifically for the Mega Drive's tile art. But you are right, I too have noticed Nemesis to produce pretty good results at times. It depends on how often and how much you keep the same pixel colour next to each other. The more the art is dithered (especially vertical line dithering), the less likely it'll be able to compress, so when you swing more towards Vectorman's style of art, you're definately looking at poorer results.

    Go Twizzler!!
     
  8. rata

    rata

    Member
    689
    72
    28
    Argentina
    Trying to be useful somehow.
    So, for making a fast leading hack the winner team would be Twizzler + Comper for 'on the fly' loading, since they are the fastest ones and now we have Twizzler that compress like a son of a bitch too. That's a really sweet thing.

    Also, what do you mean with compressing mappings? Aren't they just some lines of dc.b? Or am I missing something else? Jeez, no doubt of why I still didn't make any progress on hacking...
     
  9. Clownacy

    Clownacy

    Tech Member
    1,053
    581
    93
    I thought Twizzler was established to be slow? The mappings I was talking about was the 16x16 "block" mappings used in level geometry. Sonic CD's a bit of an oddball in that it uses Nemesis compression for those. Sonic 1 used Engima, and I think 2 and 3K used Kosinski.
     
  10. kazblox

    kazblox

    Member
    178
    27
    28
    Diassemblies and decompilations.
    Twizzler's objective is size, so it would be obvious that it would be a bit slower than Kosinski.

    If you want to push fast compression speed to the limits, you might as well use a combination of Comper for art and Chameleon for level chunks.

    EDIT: Might as well also add Chameleon compression's affect on all Sonic 1 nemesis art files too.

    Chameleon - 151558


    Only 220 bytes larger than Kosinski Moduled. If this is Saxman's so-called saving grace of fast and small compression, then it should be praised everywhere. :v:
     
  11. Jeffery Mewtamer

    Jeffery Mewtamer

    Blind Bookworm Member
    1,878
    81
    28
    While compression time shouldn't matter since compression would be done on a modern PC rather than a Genesis, what kind of decompression times would we be looking at for those compressed S1 art sets ousing a Genesis as the decompression machine?
     
  12. rata

    rata

    Member
    689
    72
    28
    Argentina
    Trying to be useful somehow.
    Oh, now I readed it again and yes, Twizzler is not meant to be fast (the thing about compression speed confused me, hahaha). How's the decompressing speed against Nemesis then? Now we have it (Twiz) as the best compressor when size is all, so if is also faster (or equal) than Nemesis then it's an all win.
     
  13. MarkeyJester

    MarkeyJester

    Original, No substitute Resident Jester
    2,192
    405
    63
    Japan
    While I'd have no objections, I do declare that a name change would be in order. The term "KENS" outlives its purpose as more compression formats are added, the name would get rediculous, you'd end up with KENSCTRBLWRTZPSTZ....etc

    I'd suggest renaming and recompiling these formats into a new collection of sorts, like "Mega Drive Compressions Collection" (MDCC) or something, and catagories them all in some way (be it in order of speed, or size, or even "type" of compression), perhaps, some site dedicated to it, with a table of links that can be reordered by different catagories (fastest to slowest/biggest to smallest), along with detailed information about the format, it's pros/cons, cost, etc. I think us having an major open library of different compressions for the Mega Drive, would be very handy for those that are looking for a "specific type" of compression for a "specific need". If you're looking for the best compression that can decompress at a specific speed of your request (or faster), then you'd be able to find the right one immediately.

    I didn't say it was definately slow(er), I just said being fast(er) "would likely be far from the truth", I haven't actually tested for speed by comparison to other compressions, I'm just simply assuming based on the number of bit reads required. But as I also stated, I've used lots of optimisation techniques on the 68k side to help speed it up.

    I am confident it'll be faster than Nemesis, but, I guess what it really comes down to, is proof...

    ...what I'll do is run a test with multiple compressed files, I'll see how many frames/scanlines it takes for Twizzler to decompress by comparison to Nemesis, and I'll provide you with the speed difference in a percentage.

    --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- ---

    EDIT:

    OK, so here are the results of three different files:

    GHZ (full) art
    Code (Text):
    1. Nemesis                    2E frames and 0 scanlines (finished during V-blank)
    2. Twizzler Moduled           15 frames and 3D scanlines
    3.  
    4. (53% faster than Nemesis)
    SBZ art
    Code (Text):
    1. Nemesis                    28 frames and 16 scanlines
    2. Twizzler Moduled           14 frames and 1 scanline
    3.  
    4. (51% faster than Nemesis)
    Sonic's sprite art
    Code (Text):
    1. Nemesis                     51 frames and 2B scanlines
    2. Twizzler Moduled            24 frames and 0 scanlines (finished during V-blank)
    3.  
    4. (56% faster than Nemesis)
    In all cases here, Twizzler takes less than half the time to decompress the same art, and dump it into VRAM.

    Of course, do keep in mind that this is an unfair test in many ways. For one, I didn't use the optimised Nemesis routine (couldn't be bothered to look for the thread), so the normal stock routine from SEGA was used, likewise however, I didn't use the best compressor for it either, so that may have saved Nemesis some time. Secondly, this is only the "moduled" version of Twizzler being tested, the normal version would be much faster, probably 30% - 40% faster, Nemesis' RAM writing version would take roughly the same time as the VRAM version, just through the nature of the same routines being used.

    That just gives you a rough idea, if you want a more thorough and deeper test, you'd have to ask someone else willing.

    --- --- --- --- --- --- --- --- --- --- --- ---

    EDIT 2:

    I took the liberty of running a test against kosinski, this one is a fairer test though as I'm using the fastest/most optimised kosinski routine provided, and have compressed the data using the best kosinski compressor available.

    We're talking Non-moduled here though...

    GHZ chunks

    Code (Text):
    1. Kosinski           08 frames and A7 scanlines
    2. Twizzler           10 frames and 07 scanlines
    3.  
    4. (46% slower than Kosinski)
    LZ chunks

    Code (Text):
    1. Kosinksi           0A frames and 0 scanlines (finished during V-blank)
    2. Twizzler           13 frames and DF scanlines
    3.  
    4. (50% slower than Kosinski)
    MZ chunks

    Code (Text):
    1. Kosinski           07 frames and 41 scanlines
    2. Twizzler           0C frames and BB scanlines
    3.  
    4. (44% slower than Kosinski)
    But like I said, it's just a rough idea, and may not be 100% accurate (again, if you want a more thorough and deeper test, you'd have to ask someone else willing).

    I'll see if I can optimise the routine even further, I highly doubt I could beat that kind of speed, but I could at least do better than current.
     
  14. AURORA☆FIELDS

    AURORA☆FIELDS

    The cute one here Tech Member
    216
    24
    18
    Finland
    AMPS
    I really like this idea! I could probably poke FlameWing about this and maybe create a crude front-end for this, of course the hard data and stuff would be required to be made by someone else. What would be cool is that you could potentially just download the formats that you would need and the common dll's, etc. and drop into same directory to use formats you'd like. That would probably mean to make all these different formats to use the same structure as KENSC do right now, but I think it would be good for not only us but the whole MD scene.
     
  15. flamewing

    flamewing

    Emerald Hunter Tech Member
    1,161
    65
    28
    France
    Sonic Classic Heroes; Sonic 2 Special Stage Editor; Sonic 3&K Heroes (on hold)
    I will already be adding Kid Chameleon and Rocket Knight Adventure compression formats, I can add more. I have been toying with the idea of splitting my tools off from S2-SSEdit repository for some time anyway. I also have a few Kosinski tweaks which has faster decompression and (potentially) better compression ratio which I plan on releasing someday, it would be as good a time as any.

    Also, the main reasons KosM compresses worse are (1) it pads modules to start at a multiple of 16 bytes and (2) it restarts fresh at each module. I have a moduled Kosinski tweak which handles #1, and I have another tweak in mind (still unimplemented) to handle #2, for much better compression.
     
  16. Clownacy

    Clownacy

    Tech Member
    1,053
    581
    93
    I'm still on 32-bit Windows, so I can't run the moduled compressor. Any chance of another build, or a source release?
     
  17. TheLastWhiteFlame

    TheLastWhiteFlame

    Member
    13
    0
    0
    Earth
    S1 & S2 Restored
    I'm currently converting to 32-bit windows, so i can post a download link for the people who are on 32-bit and not 64-bit.