Post by walker7 on Mar 23, 2008 1:28:22 GMT -5
What would be the best way to store certain kinds of compressed data? In video games, graphics are usually compressed, music is sometimes compressed (e.g. Sonic 2, the final version), and text is sometimes compressed.
For tile maps, one obvious solution is RLE. Runs of more of three of more of the same byte can be reduced to three bytes, in a format similar to the RLE compression for levels on Sonic the Hedgehog for the Game Gear.
For example, "02 05 04 04 05" becomes 02 05 04 04 04 04 04 04 04 04. The red bytes are read as-is, because the byte following them is different. The blue bytes are identical, so this indicates that the next byte (in green) tells how many times to repeat, minus 3, so 0x00 would be three times, 0x01 is four times, up to 0xFF, which is 258 times. The orange bytes are the uncompressed bytes. This way, you can use all 256 possible values for a byte.
If the bitmap is composed of only values where the difference between the highest and lowest value is less than 128, you can just set the most significant bit (MSB) to enable compression on that byte, and the next byte's value, plus 2, is the run length. (e.g. "04 83 02" would become 04 03 03 03 03.)
But one thing that is more difficult to implement is text compression. One example would be Huffman coding, where there is a binary tree that you would use to decode the text. Morse Code is a similar concept.
For more on binary trees and Huffman encoding, go to en.wikipedia.org/wiki/Huffman_encoding. The question is, what is the best way to implement Huffman encoding into an assembly program?
Now, suppose you would want to compress a long binary string, for example: 0011111000011010000111000000000111000000001111111111111111111111 (that is 64 bits, or 8 bytes). The best kind of compression would probably be LZ77 (or any variation thereof). Which variant would be best in this case, and what would be the best way to implement it?
For tile maps, one obvious solution is RLE. Runs of more of three of more of the same byte can be reduced to three bytes, in a format similar to the RLE compression for levels on Sonic the Hedgehog for the Game Gear.
For example, "02 05 04 04 05" becomes 02 05 04 04 04 04 04 04 04 04. The red bytes are read as-is, because the byte following them is different. The blue bytes are identical, so this indicates that the next byte (in green) tells how many times to repeat, minus 3, so 0x00 would be three times, 0x01 is four times, up to 0xFF, which is 258 times. The orange bytes are the uncompressed bytes. This way, you can use all 256 possible values for a byte.
If the bitmap is composed of only values where the difference between the highest and lowest value is less than 128, you can just set the most significant bit (MSB) to enable compression on that byte, and the next byte's value, plus 2, is the run length. (e.g. "04 83 02" would become 04 03 03 03 03.)
But one thing that is more difficult to implement is text compression. One example would be Huffman coding, where there is a binary tree that you would use to decode the text. Morse Code is a similar concept.
For more on binary trees and Huffman encoding, go to en.wikipedia.org/wiki/Huffman_encoding. The question is, what is the best way to implement Huffman encoding into an assembly program?
Now, suppose you would want to compress a long binary string, for example: 0011111000011010000111000000000111000000001111111111111111111111 (that is 64 bits, or 8 bytes). The best kind of compression would probably be LZ77 (or any variation thereof). Which variant would be best in this case, and what would be the best way to implement it?