#38428 - ymalik - Sun Mar 27, 2005 6:18 pm
Hello,
I have a binary file that I generated that consists of the unoptimized compressed tile set generated from gfx2gba on many 256x256 4 BPP images. Therefore, it is a large collection of binary 8-bit numbers. In order to describe the data, I have a meta file that is a large array with each element described by the following structure:
| Code: |
typedef struct OffsetLength
{
unsigned int offset;
unsigned short length;
} OffsetLength;
|
Here's what part of the meta file looks like:
| Code: |
const OffsetLength tile_offsets_lengths[] = {
{0, 0},
{0, 0},
{0, 0},
{0, 0},
{0, 0},
{0, 0},
{0, 0},
{0, 0},
{0, 0},
{0, 0},
{0, 0},
{0, 0},
// square (12, 0)
{0, 3913},
// square (13, 0)
{3913, 3908},
{0, 0},
...
|
Therefore, element 12 describes the beginning of the binary file, which is offset 0, has a length of 3913 bytes, and element 13 describes the next compressed data which is 3913 bytes from the beginning of the binary file and is 3908 bytes, etc. I want to decompress the data stored in my large binary file into EWRAM based on a index in the meta file. For example, I would want to decompress part of the binary file starting at 3913 bytes and that is 3908 bytes long. In GBATEK, I found the following under LZ77UnCompWram bios call:
| Code: |
r0 Source address, pointing to data as such:
Data header (32bit)
Bit 0-3 Reserved
Bit 4-7 Compressed type (must be 1 for LZ77)
Bit 8-31 Size of decompressed data
Repeat below. Each Flag Byte followed by eight Blocks.
Flag data (8bit)
Bit 0-7 Type Flags for next 8 Blocks, MSB first
Block Type 0 - Uncompressed - Copy 1 Byte from Source to Dest
Bit 0-7 One data byte to be copied to dest
Block Type 1 - Compressed - Copy N+3 Bytes from Dest-Disp-1 to Dest
Bit 0-3 Disp MSBs
Bit 4-7 Number of bytes to copy (minus 3)
Bit 8-15 Disp LSBs
r1 Destination address
|
I don't know how to use this. For example, how would you specify the source address? I'm assuming r0 will be a structure with bit fields for the parameter.
Thanks,
Yasir
#38436 - Mucca - Sun Mar 27, 2005 8:42 pm
You shouldn't have to worry about the details of the header as specified in GBATEK if the compression program spits the files out in the correct format. I havent used gfx2gba myself so Im not sure what exactly it does, but I did try out another program, the name has escaped me, it had a gui and could compress to a number of different formats, including LZ77 Vram safe... anyway it worked painlessly for me in conjuction with the system calls.
You do need to be careful with alignment. The system calls for decompression can only use a source address that is a multiple of 4, and if the file itself is not a multiple of four bytes in length when decompressed, the bios function will pad it. So a start offset of 3913 wont work. (At least, it shouldnt work, but who knows?).
#38449 - Miked0801 - Mon Mar 28, 2005 12:23 am
LZ77 decompression won't work if you skip into a stream. It needs all previously uncompressed data (to 4K back I believe) to work correctly. RLE will work this way as will Huffman due to how they compress.
#38454 - ymalik - Mon Mar 28, 2005 1:35 am
| Mucca wrote: |
You shouldn't have to worry about the details of the header as specified in GBATEK if the compression program spits the files out in the correct format. I havent used gfx2gba myself so Im not sure what exactly it does, but I did try out another program, the name has escaped me, it had a gui and could compress to a number of different formats, including LZ77 Vram safe... anyway it worked painlessly for me in conjuction with the system calls.
|
gfx2gba only says that it generates data that can be decompressed with the GBA. How would I specify the size of the data?
| Mucca wrote: |
| You do need to be careful with alignment. The system calls for decompression can only use a source address that is a multiple of 4, and if the file itself is not a multiple of four bytes in length when decompressed, the bios function will pad it. So a start offset of 3913 wont work. (At least, it shouldnt work, but who knows?). |
If I pad the first 3913 bytes of data with 3 zero's at the end, will everything be fine? The 3913 bytes of data decompresses into 32768 bytes. Will the decompressor, after padding, alter the final size of the unpacked data?
#38455 - ymalik - Mon Mar 28, 2005 1:38 am
| Miked0801 wrote: |
| LZ77 decompression won't work if you skip into a stream. It needs all previously uncompressed data (to 4K back I believe) to work correctly. RLE will work this way as will Huffman due to how they compress. |
The decompressor needs uncompressed data as well? I'll just move the pointer to the data by some number of bytes, and then the decompressor won't know the difference, right?
#38458 - DekuTree64 - Mon Mar 28, 2005 2:23 am
| ymalik wrote: |
| I'll just move the pointer to the data by some number of bytes, and then the decompressor won't know the difference, right? |
No, that's not how LZ77 works. All the data is compressed to begin with. It compresses by storing references to runs of data in the the most recently decompressed 4KB (or any other window size, depending on the specific implementation).
Say you have the sequence 123 in your file, and it occurs once every 100 bytes. Then the actual sequence is only stored once at the start of the file, and every next 123 is replaced with a reference to the 123 that came before it. Then for example, the 4th 123 depends on the 3rd, which depends on the 2nd, which depends on the 1st. Unless you decompress the first 3, you can't decompress the 4th.
I would recommend compressing the 256x256 blocks individually, or trying other compression algorithms (like the ones Mike mentioned).
_________________
___________
The best optimization is to do nothing at all.
Therefore a fully optimized program doesn't exist.
-Deku
#38461 - tepples - Mon Mar 28, 2005 3:01 am
| DekuTree64 wrote: |
| I would recommend compressing the 256x256 blocks individually |
Seconded. If you're familiar with PC data compression programs, consider that compressing individual 256x256 blocks is to compressing the whole map as .zip is to .tar.gz or as non-solid .rar archives are to solid .rar archives.
_________________
-- Where is he?
-- Who?
-- You know, the human.
-- I think he moved to Tilwick.
#38467 - ymalik - Mon Mar 28, 2005 4:12 am
| tepples wrote: |
| DekuTree64 wrote: | | I would recommend compressing the 256x256 blocks individually |
Seconded. If you're familiar with PC data compression programs, consider that compressing individual 256x256 blocks is to compressing the whole map as .zip is to .tar.gz or as non-solid .rar archives are to solid .rar archives. |
Well, I am (if I'm thinking of what you are thinking). Again, the larger image, which could be 20,000x20x000 pixels, is broken up into 256x256 images; each image is stored in a separate file, but only the images that have data are stored. You can think of the 256x256 images as squares of a large grid, and the grid is the large image. Each 256x256 4 BPP image is compressed seperately. Therefore, a file with all the compressed content is generated for each image file. If I have 1,000 256x256 images, I'll have 1,000 compressed tile set files. The files are in source code format. I then combine all the files into one file using a PHP script. The data is packed into binary data, obviously, before being outputted to the final large file. In order to know which part of the large binary file is what compressed image, I have the meta file described which is described in my first post. The entries that say (0, 0) indicate "grids" that have no data, and therefore there is no compressed image for them.
(You must have guessed by now this is relation to my scrolling massive image topic.)
With that mind, so I can just simply move over the pointer to data in the large binary file to indicate the beginning of the next compressed data. For example, if I have:
| Code: |
extern const unsigned char tiles[];
|
where the tiles array references the large binary file included using the .incbin command in an assembly file. Can I do this to access image (13, 0):
| Code: |
unsigned char temp_tiles = offset_lengths[13].offset + (unsigned char *) tiles;
|
Much thanks,
Yasir
#38515 - ymalik - Mon Mar 28, 2005 8:44 pm
Got the uncompression to work. I had append zeros at the end of the files that were not a multiple of 4 in size so I could have offsets that were multiple of 4s. gfx2gba indeed includes the necessary header information. I was also able to offset within the large tile file. For example, I could do:
| Code: |
temp_tiles = (u8 *) tiles + tile_offsets_lengths[curr_map].offset;
LZ77UnCompWram((void *) temp_tiles, (void *) tile_set_buf);
|
where tiles points to the large binary file with all the compressed files and curr_map is any map. Question though: will the padded zeros affect the size of the decompressed data? That is, will the decompressed data always be 32768 bytes and not overflow to another buffer? By the way, I could also uncompress to IWRAM; is this a bug in VBA?
Thanks,
Yasir
#38546 - tepples - Tue Mar 29, 2005 1:08 am
| ymalik wrote: |
| Question though: will the padded zeros affect the size of the decompressed data? |
No. The 4-byte header of the compressed data determines the output buffer size.
| Quote: |
| By the way, I could also uncompress to IWRAM |
Of course you can decompress, say, an 8 KB block of data to IWRAM.
| Quote: |
| is this a bug in VBA? |
The fact that you can overflow the stack with a decompression call is true of the GBA BIOS itself, and VBA emulates it bug-for-bug.
_________________
-- Where is he?
-- Who?
-- You know, the human.
-- I think he moved to Tilwick.
#38557 - ymalik - Tue Mar 29, 2005 2:33 am
How fast does decompression take compared to vdraw? The decompressed data is 32768 bytes.
#38629 - Miked0801 - Tue Mar 29, 2005 7:29 pm
No - you will not be able to decompress that quanity of data in a vblank period - you'll need to setup a buffering system and blast directly from that buffer when the decompression is complete. You'll need a similiar system soon for other parts of your project, so you might as well set it up now. :)
#38652 - ymalik - Tue Mar 29, 2005 11:50 pm
Yes, that's what I'm doing. I'm decompressing during vdraw, not vblank. I just wanted to know by how much my program will slow down because I'll probably miss many vblank periods.
#38704 - Miked0801 - Wed Mar 30, 2005 6:47 pm
I think you'll be alright. We decompress the leading edge of our scroll-buffers on the fly (custom huffman) and can run our games at 30Hz with everything else happening as well.