This page is a mirror of Tepples' nesdev forum mirror (URL TBD).
Last updated on Oct-18-2019 Download

Tile encoder/decoder

Tile encoder/decoder
by on (#54230)
I'm releasing to the public the work I've done so far on the tile compressor based on the format used by Codemasters in some of their games (like Bee52 and Big Nose Freaks Out). Feel free to use it in projects that require CHR compression. Note that it works specifically with NES tiles, so it will hardly work well with other kinds of data.

Apparently, the compressed tiles aren't as compact as the folks at Codemasters were able to make them, and my encoder is to blame. The format has the potential to be even more compact than theirs (because it doesn't have a few redundant bits the original has), but my encoder can't find the optimal way to divide the tiles into groups, and the key for this compression scheme is organizing tiles in groups of lengths that result in better compression.

The source code is included, and if anyone wants to give a shot at modifying the compressor so that it divides the tiles better than it currently does, they are welcome to. As long as nothing about the format is changed, the decompressor will not need to be changed.

Download here.

Please let me know if you plan on using this, and please post here if you have suggestions on how to improve the encoder.

by on (#54232)
ooooo... I'm kind of a fan of compression stuff.

I might take a crack at touching up the compressor. Is the compression format included in the download?

*gets*


EDIT:

doh, no format outline in the package. Is the format documented anywhere? Or do I just have to decipher the source to figure it out?

EDIT2:

I dug up this post. Is this the same compression scheme?

http://nesdev.com/bbs/viewtopi ... 2&start=15

EDIT3:

Tepples' followup post clarified a lot of it for me (actually I was totally lost until he throw in that C-ish syntax -- that really made it easier to understand). But there are still some format details that are confusing me. Specificlaly, what bits in the stream represent what.

Here's what I understand:

First byte in the stream is the number of tiles to decode, after that:

Code:
1-bit to determine whether or not to rebuild the tables.
  1:  skip table rebuilding
  0:  rebuild table:
    4 groups of 2 bits follow (8 bits total).  These bits
      rebuild Table A.

1-bit to determine row repeat
  1:  repeat previous row (next bit is the table rebuild bit)
  0:  this row is not a repeat

<<if row is not a repeat>>
2-bits to determine the color, and the mode (mode is A[color])
  if the mode is 0, the same color is repeated for the whole row
  if the mode is nonzero:

    7 groups of 1-3 bits to determine the colors for the rest of the row
    (as per tepples outline in that other thread)


Do I understand this right? I have a few questions about this:

- I assume the tables can be changed mid-tile, correct? Just not mid-row.

- Can you change tables B,C, or D? I only see how you'd change table A from this. What determines the contents of B,C,D?

by on (#54236)
Hehe... Sorry I didn't explain the format, but I didn't expect anyone to mess with the format itself. While coding the compressor I tried to separate the encoding (turning the tiles into a stream of bits) from the parsing (deciding how long each block should be).

If you look at the source you can see that I tried a few different parsing functions, and those are kinda self explanatory (I hope!). The parsing functions can use whatever method they see fit to fill an array of block lengths, which later are used for actual encoding.

But since you are interested in the format, let's get to the questions! You almost got it. Here is the format with as much detail as I can think of:

Code:
.start a new block by building the decompression tables:

  .for each color (3 down to 0):

    .2 bits indicate how many colors can follow the current color.
     This value goes straight to table A, indexed by the current
     color.

    .if 1 or more colors can follow it, a color is specified in
     encoded form. Since there are only 3 possibilities, the colors
     are represented by the following codes: 0 (first possibility),
     10 (second possibility) and 11 (third possibility). Depending
     on the current color, the possibilities are different, because
     they don't include the current color (for example, the 3
     possible colors that can follow color 2 are 0, 1 or 3). The
     specified color is enough to find all of them: if only one
     color can follow the original one, the specified one is it. If
     it's 2 colors, the specified one is discarded and the 2 that
     are not it are used. If it's 3 colors, the other 2 are the
     ones that are not it. These colors go to tables B (first color
     that can follow the original), C (second) and D (third).

.decode the tiles that are part of the same block:

  .1 bit selects between repeating the previous row or decoding a
   new one (0 = new row, 1 = repeat previous row). It is possible
   to repeat the first row of the first tile of a block, and a row
   filled with color 0 is used in this case.

  .if the row is not a repeat:

    .2 bits specify the color of the first pixel. This color is
     then used as an index into table A so that we know how many
     colors can follow the current one.

    .if no color can follow the current one, the same color is
     repeated for the rest of the row.

    .if there are colors following the current one, 1 bit selects
     between repeating the previous pixel or reading a new one
     (0 = new pixel, 1 = repeat).

    .if the pixel is not a repeat, the next pixel depends on how
     many colors follow the current one. If only 1 can follow it,
     this is used (it's the color from table B). If 2 can follow
     it, 1 bit selects between them (0 = color from table B, 1 =
     color from table C). If 3 can follow it a value with 1 or 2
     bits select between the 3 possibilities (0 = from table B,
     10 = from table C, 11 = from table D).

    .after each pixel is draw, its color is used as an index into
     table A again so that the next pixel is processed the same way.

  .once the tile is complete, 1 bit selects between starting a new
   block or not (0 = no new block, 1 = new block).

I hope the above is clear enough, I'm having trouble organizing it any better than this.

Quote:
I assume the tables can be changed mid-tile, correct? Just not mid-row.

No, they can't. A compressed stream always starts with a new block (and the definition of new tables), and after each completed tile a bit will select between continuing the current block or ending it and starting a new one.

Quote:
Can you change tables B,C, or D? I only see how you'd change table A from this. What determines the contents of B,C,D?

These are changed whenever a color can be followed by colors that are not itself. The first possible color goes to table B, the second goes to table C and the third goes to table D. Naming them with single letters was not a very good choice, but back then I wasn't sure what to name them. In the decoder I named them ColorCount (A), NextColor0 (B), NextColor1 (C) and NextColor2 (D), I hope those make more sense.

by on (#54238)
This is great! I'm going to take a look at it in more detail at work tomorrow. Thanks for uploading this. I've been intrigued ever since you wrote that post a few months ago where you reverse engineered the Codemasters algorithm.

by on (#54239)
How does it compare to the Contra algorithm, or the Zelda Oracles algorithm?

by on (#54240)
Dwedit wrote:
How does it compare to the Contra algorithm, or the Zelda Oracles algorithm?

I don't know anything about those. If you have any links to information about them, I'd be interested.

I can tell you though that this compression scheme often compresses tiles to 60% of their size, sometimes more, sometimes less. It's one of the most efficient I have studied.

by on (#54242)
Okay I think I get it... but I have a few more questions I forgot to ask before, but I'll be able to answer them myself when I get home from work and take a look at the compressed and decompressed data you provided in that archive.

by on (#54243)
I'll call it CMM (Codemasters Markov) for this post.

Both Contra and Who's Cuter use variants of byte run-length encoding for their tiles. (LJ65 and my current project use the same thing for their nametables.) In essence, RLE has a short code for "repeat the previous byte". RLE also has a short code for 2-color tiles, such as those in text fonts: the bottom (blank) row of a glyph's first plane and the 9 blank rows of the font's second plane make up one run. CMM likewise has short codes for "repeat the previous row" and "group of tiles uses only two colors".

But CMM also shrinks the data even when you don't have identical rows because it has a short code for repeated pixels within a row. Each pixel that's the same color as its neighbor to the left takes only 1 bit, not 2. This is a strict gain in tiles with three colors and an amortized gain in tiles with four colors because repeats are more likely than those colors that have to be coded with 3 bpp.

If this codec works, multicarts can get bigger. Imagine Forbidden Five (though not Punch-Out!! obviously).

And no, it isn't limited to NES tiles; it would be trivial to make the decoder output in Game Boy, Virtual Boy/NGPC, or any other 2bpp tile format. I seem to remember Commodore 64 also using 2bpp tiles in its 160px-wide mode.

by on (#54244)
I don't know the Contra algorithm, I've only stepped through it a couple times, but didn't bother to decipher the format. It does not appear to be byte-aligned.


Zelda Oracles either uses an LZ based scheme, or its own special format which I call "16 bits and common byte".

"16 bits and common byte":
Read a 16 bit value, these will indicate whether to use the common byte, or to copy a byte.
If the value isn't zero (indicating that it has a common byte), read the common byte.
For each bit in the 16 bits, either output the common byte, or copy a byte.
Really simple. It was intended for level data but is also used for graphics for some reason.
You need at 3 instances of the common byte to break even.

"LZ" format:
You read a byte to indicate whether the next 8 things are literal bytes, or are LZ runs. You read another byte for the next 8 flags when you are out of bits.
For an LZ run, the distance is 5 bits, and the length is 3 bits. If the length is zero, it reads a byte to get an 8-bit length.
I think the game's "LZ format" has way too much overhead, of one bit per each byte!

by on (#54245)
Disch, if you need to ask anything, please do.

If anyone is wondering what are the differences between this format and the one by Codemasters, there are basically 2:

1. The original format used a bit to indicate that the first block was starting. I considered this redundant because before decompressing anything the first set of tables has to be built. This doesn't save much space, but why would I waste it, even if it's a single bit?

2. When defining the tables, no matter how many colors can follow the original one, I can always build the whole list from a single color. The original format needed an extra bit to select between the 2 remaining colors when 2 colors followed the original one, in addition to specifying the color that doesn't follow it.

Another difference, which has no effect on how compact the encoded data is, is that I use different codes for compressed colors, possibilities and such. The codes I picked seemed more appropriate to me, but the codes are the same size as before, so it really doesn't matter.

So, if the format is more compact, why aren't the encoded files? Because I'm not that good with math, and couldn't find an algorithm to divide the tiles into blocks of optimal lengths. I order words, I can't seem to select the best times to end a block and start another one. However, I took note of the block lengths used by Bee52 in the Codemasters logo tileset, hardcoded them to my compressor and the result was indeed smaller than the original data in the ROM (by only 4 bytes, but still). This proves that this format is more compact then theirs, once the optimal lengths are selected. Hopefully one day I (possibly with some help) will be able to make an algorithm that finds the best lengths.

by on (#54246)
tepples wrote:
And no, it isn't limited to NES tiles; it would be trivial to make the decoder output in Game Boy, Virtual Boy/NGPC, or any other 2bpp tile format.

I meant that the encoder and decoder I provided are specific to NES tiles, just in case someone decides to try with name table data, for example, which I'm pretty sure wouldn't work well. But sure, modifying it to work with other 2bpp tile formats should be trivial (the encoder would also have to be modified to interpret the input file correctly, but that's trivial too).

Dwedit, it appears that the other formats you mentioned are byte-oriented, and I believe that CMM (as tepples named it), being pixel-oriented, will almost certainly compress better. This is because byte oriented compression will only take advantage of vertical redundancy (seeing as a byte represents an entire row of a tile), while pixel-oriented schemes will also take advantage of horizontal redundancy.

The way I see CMM, it looks like they wanted something like RLE (they use a bit to repeat rows, which resembles the way RLE works), but they wanted to be able to repeat pixels within a row as well. However, since adding repetition flags to every pixel and row would cause a lot of expansion when there was no repetition, they came up with this crazy scheme of limiting the possibilities of colors that can be used, so that shorter codes could be used, and that would counterbalance the expansion caused by the excess of flags. I don't know if it was actually designed like that, but this is what it looks like to me.

by on (#54251)
Dwedit wrote:
Zelda Oracles either uses an LZ based scheme, or its own special format which I call "16 bits and common byte".

"16 bits and common byte":
Read a 16 bit value, these will indicate whether to use the common byte, or to copy a byte.
If the value isn't zero (indicating that it has a common byte), read the common byte.
For each bit in the 16 bits, either output the common byte, or copy a byte.
Really simple. It was intended for level data but is also used for graphics for some reason.
You need at 3 instances of the common byte to break even.

I call this RLZ. Just basically a bit mask for repeat byte/word/nibble/etc or literal fetch. 1bit RLE. I've a few versions of this. Some repeat a common/fixed value every so many bits (the size of the mask. I.e. next fixed value is fetched along with the bit mask) and some variations just repeat the last literal.

Quote:
"LZ" format:
You read a byte to indicate whether the next 8 things are literal bytes, or are LZ runs. You read another byte for the next 8 flags when you are out of bits.
For an LZ run, the distance is 5 bits, and the length is 3 bits. If the length is zero, it reads a byte to get an 8-bit length.
I think the game's "LZ format" has way too much overhead, of one bit per each byte!

Heh - LZSS with an extended/additional control code. 5bits is kind of a small window. But then again, the element size is smaller (2bit pixels).

by on (#54257)
Zelda oracles also supports another LZ format with longer distances and lengths.

by on (#54258)
But then LZ77 works a lot better on platforms that have random access to VRAM (like Game Boy with rendering off), a work RAM big enough to hold a fairly large history (like Game Boy with rendering on or Super NES), or both (like GBA or PC). Methods with a static dictionary (e.g. Huffman, word encoding) and methods with a small state (e.g. RLE, CMM) work better when you have to decompress directly to a parallel port.

by on (#54266)
Guys, I might have just found a way to make the files smaller than the Codemasters encoder did. I'm just making sure it works and that I did not screw up with the tests. I'll report back soon.

by on (#54269)
OK, it appears to be working great now! The compressor has been updated (download from the same location as before), and now it compresses better than Codemasters' compressor did (at least for the few tilesets I tried).

I did something tepples suggested me a few days ago: messing with the lengths of the blocks gradually, making them longer or shorter, merging blocks, things like that, and it worked great. After adjusting all the lengths a few times (the program only stops when the compression ratio stops improving), a pretty decent compression ratio is achieved. Compare it against other compressors/formats and draw your own conclusions.

I'm not sure if the compression ratio can be improved any further, but my guess is it can. I believe this is beyond my level of intelligence though, so I probably won't try it. I'm just glad I was able to make it slightly better than the scheme I was basing myself on.

Anyway, I hope that there are no bugs, but if you find anything just let me know. I hope this is useful for you guys that need some extra CHR compression. I'll probably use it in my projects from now own too.

by on (#54272)
I just tested it on the last real 8192 bank of CHR in Zelda 2. The output size was 5163 bytes, and it beat LZMA (5371 bytes).

by on (#54291)
Dwedit wrote:
The output size was 5163 bytes, and it beat LZMA (5371 bytes).

Yeah, that's expected, since LZMA is designed to work on arbitrary data and doesn't know the input consists of several bitmaps with dimensions of 8x8 pixels and color depth of 2 bpp.

The Codemasters codec is the best one I've seen used in NES games (I didn't check every single game, obviously). It seems that most other developers favored simplicity and settled for more modest compression ratios. I admire Codemasters for going this far in order to make better use of the ROM space they had. You know, this was not their first compression scheme, in older games they used a simpler one, and I think it's admirable that they continued to research better methods instead of sitting on their asses and just using what they already had.

Anyway, I'm not sure where to go from here. I'm more than satisfied with the compression ratio now, and I doubt I can improve it any further. I guess I'll try to make the decoder faster, even though I don't think speed is a big issue here... 2 seconds (I didn't time it, I'm just guessing) isn't such a long time to wait for the tiles to load. I don't want to sacrifice space though, so I'll only consider making it faster if I can do it without making it larger.

by on (#54301)
tokumaru wrote:
I guess I'll try to make the decoder faster, even though I don't think speed is a big issue here... 2 seconds (I didn't time it, I'm just guessing) isn't such a long time to wait for the tiles to load.

Two seconds to load 8 KiB? Four tiles a frame? Sounds like a Micronics game. Has anyone else watched the pattern tables during Ikari Warriors' opening sequence? Perhaps part of favoring simplicity comes from favoring speed.

by on (#54306)
My decompressor decoded the first 3 tiles of smb.bin correctly, but then it started screwing up.

After doing a bit of logging I found this to be my problem:

tokumaru wrote:
It is possible to repeat the first row of the first tile of a block, and a row filled with color 0 is used in this case.


I'm going to go out on limb here and say either:

- That's wrong
or
- That's not how smb.bin was encoded

The 4th tile in smb.bin starts a new block, and the first 4 rows of the 4th tilee are repeat rows. But if you look at SMB.chr the top 4 rows of the 4th tile are not zero filled.

Of course it could be that I'm misinterpretting.

Here's my ugly log that shows how I'm decoding. My apologies for the crudeness. Apparently I can't copy/paste from the terminal and photobucket seems to have blurred my png for some retarded reason:

http://i7.photobucket.com/albums/y282/D ... beelog.png

The row 6 and 7 at the top are the last 2 rows of the 3rd tile (they are decoded correctly)

Following that is the 4th tile. As you can see, after defining the tables, it opens with '1111' which is 4 zero'd rows.


Can you shed some light on this, tokumaru? I must be doing something wrong, right?

I'll upload my source if you want to peek, although it's pretty ugly.

by on (#54308)
Disch wrote:
tokumaru wrote:
It is possible to repeat the first row of the first tile of a block, and a row filled with color 0 is used in this case.


I'm going to go out on limb here and say either:

- That's wrong

I checked my decoder, and right after setting up all the tables it clears the row "buffer" (faking a row with all zeroes) and reads a bit to decide whether or not the next row is a repeat.

Quote:
or
- That's not how smb.bin was encoded

I just debugged the ROM that uses my decoder and I got the following statistics for the block that starts on the 4th tile:

color 3 is followed by 3 colors: 1, 0 and 2;
color 2 is followed by 2 colors: 0 and 3;
color 1 is followed by 3 colors: 3, 0 and 2;
color 0 is followed by 1 color: 2;

This is from the file encoded with the latest version of the encoder, but I just looked at your log and it seems you are using the file encoded with the old version. Well, if you switch to the new version the above is what you should get (there's a block starting at the 4th tile too, it just appears to have a different length).

Quote:
Following that is the 4th tile. As you can see, after defining the tables, it opens with '1111' which is 4 zero'd rows.

From your log it seems that you are decoding the tables wrong, which would completely screw the meaning of future bits. It seems to me that you are not reading a color from the file in case mode 3 is selected. You might have assumed a color is not necessary because it's obvious what the 3 colors are, but you do need to be given a color so that you know which of the 3 possibilities is the most frequent one, because it gets a shorter code than the others.

In mode 3, when pixels are drawn, the first possibility is given code 0, and the remaining two get codes 10 and 11. We want to make sure the shortest code goes to the most common color. The result wouldn't be as compact if we simply used the 3 possibilities in the same order every time.

Is that the problem? I'm almost certain it is, because I just checked and the first block never uses mode 3, which must be why you are getting it right.

EDIT: In case it isn't clear, the building of the tables works like this:

mode 0:
.no color is specified;

mode 1:
.the specified color goes to table B;

mode 2:
.the specified color isn't stored in any tables;
.the first color that isn't the specified color or the current one goes to table B;
.the second color that isn't the specified color or the current one goes to table C;

mode 3:
.the specified color goes to table B;
.the first color that isn't the specified color or the current one goes to table C;
.the second color that isn't the specified color or the current one goes to table D;

The only case where a color isn't specified is in mode 0.

by on (#54309)
tepples wrote:
Two seconds to load 8 KiB? Four tiles a frame?

I didn't time it. Just run the ROM yourself with FCEUXD's tile viewer open and you can have an idea of how long it takes to decode the first half of SMB's tileset (it's about as long as it takes for them to be displayed, although some of the time is spent setting up the name and attribute tables and other kinds of initialization). FXEUXD seems to lag a bit when it starts though, so I can't properly time it unless I use the NMI to count how many frames are needed until all the tiles are done.

Quote:
Has anyone else watched the pattern tables during Ikari Warriors' opening sequence?

Just did. It's kinda slow, I think my decoder is faster.

Quote:
Perhaps part of favoring simplicity comes from favoring speed.

I don't think speed is that important in this case. 1 or 2 seconds isn't enough time for a player to wonder if the game is still running, it's the standard time of a black screen between a fade out and a fade in, not a big deal.

I could probably make the decoder much faster if I read bits using inlined code rather than a subroutine (think about it: 12 cycles of jsr/rts for every bit adds up to almost 17 frames in a 5KB file). I could also code different sections for each mode rather than check the mode a few times to make decisions. However, that would at least double the size of the decoder, and I don't want it's size to be a big overhead.

Also, in many cases simplicity doesn't represent speed. There are many cases where the straightforward/simple solution is slow, and you have to think of tricks to make it all faster.

by on (#54313)
tokumaru wrote:
I don't think speed is that important in this case. 1 or 2 seconds isn't enough time for a player to wonder if the game is still running, it's the standard time of a black screen between a fade out and a fade in, not a big deal.

Which means the map decoder has to run that much faster if it caches much of the decompressed map in RAM.

by on (#54319)
OK tepples, I already told you I am thinking of ways to speed it up. You are welcome to contribute with any ideas you have.

Also, Map decoders, when realistically complex, should be able to do their job much faster than a tile decoder, seeing as they have to generate around 1KB of data, not 8KB.

In my game at least, I plan on decoding the tiles for a level while a black screen is displayed, but once that's done I'll display a title card for the level and draw the first screen column by column like when inside the game, so the time it takes to do it will not even count as "black screen time", there will be something to look at and music playing so it will not look frozen.

I don't remember anyone bitching at load times in NES games, not even about Ikari Warriors.

by on (#54323)
I hated the load time in Excitebike :), whenever you use the Load or Save command.

by on (#54324)
tokumaru wrote:
Is that the problem? I'm almost certain it is, because I just checked and the first block never uses mode 3, which must be why you are getting it right.


Yeah that's gotta be it. For some reason I skipped over that part. ^^

Thanks a million!

by on (#54334)
It's really great, I probably will use this for almost all of my CHR data. Only time I would want something faster is when the system first comes on, I might use RLE there because I hate how some games on cart don't start up right away.

I found one CHR file that was 1,200 bytes smaller with LZ77, but not surprisingly it was because most of the tiles were duplicated on the 2nd 4kB page. But yeah on that same file there was a 319 byte improvement between the last 2 versions of this compression, and that's more memory than the decompression code takes - that's really cool.


Dwedit wrote:
I hated the load time in Excitebike :), whenever you use the Load or Save command.

Yeah me too, it takes forever to access the NES tapedrive. :P

by on (#54336)
tokumaru wrote:
I don't remember anyone bitching at load times in NES games, not even about Ikari Warriors.

This is probably as close to bitching as an assume-good-faith environment allows:
In GDRI's article about Micronics, contributors wrote:
The Famicom/NES games listed below are characterized by a distinct lack of coding and design skill and are often plagued by problems such as jerky scrolling, sprite tearing, and load times.

In Wikipedia's article about Micronics, citing the GDRI article, contributors wrote:
The games also have long delays between changing screens, since the games transferred graphics to video memory at a much slower rate than usual.

I can accept four or five tiles per frame, as long as it can decompress to a transfer buffer in RAM (which I've been putting at $0100-$019F lately) so that I can 1. show a title card while stuff loads (even if only "WORLD 1-1" or "MARIO START!") and 2. swap tilesets within a level. Otherwise, I might have to rethink the design.

So you took out the first block's "load tables" bit. Have you looked into the frequency distribution of the block lengths? I guess I will when I get a chance.

by on (#54338)
tepples wrote:
I can accept four or five tiles per frame, as long as it can decompress to a transfer buffer in RAM (which I've been putting at $0100-$019F lately) so that I can 1. show a title card while stuff loads (even if only "WORLD 1-1" or "MARIO START!")

Well, when a tile is completed the X register is free, so I guess it could be used to write the tile to a buffer instead of directly to VRAM. I could also provide an additional function to be called during VBlank that transfers the tiles that are ready to VRAM.

The bad thing about making all of this configurable would making things even slower. I could, whenever a row is completed, decide between buffering it or writing it to VRAM, based on a parameter supplied by the programmer (could even be the carry flag: 0 = buffer, 1 = VRAM).

Then the programmer would be responsible for calling the routine that uploads the tiles to VRAM and frees space in the buffer.

Quote:
and 2. swap tilesets within a level. Otherwise, I might have to rethink the design.

I don't plan on using this during gameplay because it would be very slow. You'd have to limit the decoder to 1 or 2 tiles per frame in order to not slow everything else down. So in my game I plan on using uncompressed graphics for anything that is loaded during gameplay.

Do you think I should have the decoder accept another parameter specifying the maximum number of tiles it can decompress each time it's called? I would need 2 entry points, much like NSFs have a INIT and PLAY addresses. The equivalent of the PLAY address would have to be called every frame and would be responsible for decoding at most the specified number of tiles until all tiles were done.

Quote:
So you took out the first block's "load tables" bit.

Yeah. Not a huge saving by any means, but that bit was meaningless, so I took it out. I considered not allowing the repetition of the first row of the first tile of a block as well, but I think I should check how often the first tiles of blocks start with zeroed out rows.

Quote:
Have you looked into the frequency distribution of the block lengths? I guess I will when I get a chance.

Just a little bit out of curiosity, but I don't know if we can do anything useful with it.

by on (#54339)
OK, I'm considering modifying the decoder to work with rendering enabled or disabled, and the choice is left to the programmer. When decompressing with rendering enabled, the maximum number of tiles you want to decode per frame must be informed. Does that sound good?

by on (#54353)
tokumaru wrote:
The bad thing about making all of this configurable would making things even slower.

Not if it's decided at compile time.

Quote:
Quote:
Have you looked into the frequency distribution of the block lengths? I guess I will when I get a chance.

Just a little bit out of curiosity, but I don't know if we can do anything useful with it.

Currently, you're encoding the length of each block as a unary number: the number of 0s plus the following 1 gives the length. But unary is optimal for only one distribution: the geometric distribution with p=1/2. For different values of p, different Golomb codes become optimal. But if your distribution follows a power law, the universal codes become optimal.

by on (#54355)
tepples wrote:
Not if it's decided at compile time.

Could be, but it's easy to think of programs where both methods would be desirable. A programmer may want to load tiles while something is displayed on screen some times, or even during gameplay, but he will probably want tiles to load as quickly as possible when he's not displaying anything.

Quote:
Currently, you're encoding the length of each block as a unary number: the number of 0s plus the following 1 gives the length.

I see what you mean. Depending on the lengths it might be better to use a constant number of bits (or a variable number of them that favors shorter lengths) to represent them.

From what I've seen, blocks tend to be quite short (less than 5 or 6 tiles maybe), because the number of colors that follow each color grows pretty quickly with typical tiles, and there would be no advantage in using this format if all colors could be followed by 3 colors. There are a few exceptions, like when a long series of tiles use only 2 colors for example, in which case it's more compact to have a long block.

by on (#54361)
I'm having more troubles with that 4th tile. I'm guessing I'm still building the tables wrong:

Code:
1110  Mode[3]=3:1,0,2
1110  Mode[2]=3:1,0,3
1111  Mode[1]=3:3,0,2
1111  Mode[0]=3:3,1,2
0 - New Row
11  -- clr[0]=3
1  -- clr[1]=3
1  -- clr[2]=3
1  -- clr[3]=3
1  -- clr[4]=3
1  -- clr[5]=3
01  -- clr[6]=1
01  -- clr[7]=3
__ ROW 0:  33333313


The row should be 33333300 -- but I'm not seeing how that is supposed to happen.

by on (#54362)
Disch wrote:
Code:
1110  Mode[3]=3:1,0,2
1110  Mode[2]=3:1,0,3
1111  Mode[1]=3:3,0,2
1111  Mode[0]=3:3,1,2
0 - New Row
11  -- clr[0]=3
1  -- clr[1]=3
1  -- clr[2]=3
1  -- clr[3]=3
1  -- clr[4]=3
1  -- clr[5]=3
01  -- clr[6]=1
01  -- clr[7]=3
__ ROW 0:  33333313


The row should be 33333300 -- but I'm not seeing how that is supposed to happen.

You interpreted the last few bits incorrectly. When row 6 starts, a 0 indicates it's not a repeat, so you need to read a new color. Since the previous color (3) can be followed by 3 others, the possible codes for the new pixel are 0, 10 or 11. After you read the 1, for some reason you stopped and picked the wrong color. You should have read another bit in order to know whether to use the second possibility (code 10) or the third (code 11).

Since the next bit is 0, you have to use the second possibility, which is color 0 (Mode[3]=3:1,0,2). Then the next bit is one, indicating that you should repeat color 0, which results in 33333300.

EDIT: Are you by any chance using the codes tepples mentioned in that other thread? I'm using different codes. Whenever there are 2 possibilities I use 0 and 1, and whenever there are 3 possibilities I use 0, 10 and 11.

by on (#54363)
Yeah I was using tepples' thing as a reference.

So lemme get this straight:

1 = repeat clr
00 = table B
010 = table C
011 = table D

is that right??


EDIT:

success! After that change it works.

yay

Now I can work on a compressor (even though I'm super late. If only I had more than 2 hours a day to work on this).

I am confident I'll be able to achieve optimal compression, though ;D

by on (#54364)
Correct.

Quote:
I am confident I'll be able to achieve optimal compression, though ;D

Good luck!

by on (#54373)
tokumaru wrote:
OK, I'm considering modifying the decoder to work with rendering enabled or disabled, and the choice is left to the programmer. When decompressing with rendering enabled, the maximum number of tiles you want to decode per frame must be informed. Does that sound good?


That would be really cool, because there is nothing else available that does that. Paired with double-buffering, that could allow for some interesting animation possibilities by freeing up room for many more frames. Perhaps not in action games, but almost anywhere else.

by on (#54445)
There are 9 instances of ReadBit. You could make it half a macro and half a subroutine to save a 12-cycle jsr/rts pair for 7 of the 8 bits in a compressed byte. For a 4 KiB segment compressed to 2500 bytes, this saves 7 frames at the cost of 36 bytes. Given how much you're already saving over the original Codemasters code, this might be worth it.

FROM the following:
Code:
+ReadBit:

   ;read a bit from the stream and return it in the carry flag
   asl BitBuffer
   bne +Return
+   lda (InputStream), y
   iny
   bne +
   inc InputStream+1
+   rol
   sta BitBuffer

+Return:

   ;return
   rts

TO the following: (I'm not too familiar with asm6, so this is a sort of ca65/asm6 amalgamation)
Code:
.macro ReadBit
   .local Return
   asl BitBuffer
   bne +Return
   jsr +ReadByte
+Return
.endmacro

+ReadByte:
   lda (InputStream), y
   iny
   bne +
   inc InputStream+1
+   rol
   sta BitBuffer
   rts


On several other forums I used to be active on (pocketheaven, gbadev), there was seldom a new library release thread without constructive criticism about its license. From readme.txt:
Quote:
Feel free to use this in your projects if you'd like. You can also modify the compressor or the decompressor if you think you can improve them in any way. I just ask that you let me know if you make any improvements to these programs.

I take it that was supposed to be a request, much like the "giftware" license of the Allegro library. Or is it a requirement? It's OK if it's a requirement as long as one can fulfill it by just publishing the source code of the modified compressor or decompressor; in that case, it acts like a weak copyleft like the Classpath license, MPL, or LGPL.

(License discussion continues in another topic.)

by on (#54473)
I wonder if Disch was able to make a better encoder than mine.

Disch, are you planning on changing anything about the format or are you just gonna improve the block-finding logic?

If anyone has any ideas for improvements to the format itself, it would be better if we decided on a final format right away, so that we can improve encoders and decoders without breaking compatibility with the format.

I made few changes to the original format, because I knew they would for sure save some extra bits, but if anyone thinks more radical changes (such as specifying block lengths with something else than unary codes) would be improve the compression ratios, we should discuss them.

by on (#54480)
I've been unmotivated this weekend, so I didn't work much.

I don't plan on changing the format, no.

by on (#54504)
tepples wrote:
But then LZ77 works a lot better on platforms that have random access to VRAM (like Game Boy with rendering off), a work RAM big enough to hold a fairly large history (like Game Boy with rendering on or Super NES), or both (like GBA or PC). Methods with a static dictionary (e.g. Huffman, word encoding) and methods with a small state (e.g. RLE, CMM) work better when you have to decompress directly to a parallel port.


Actually, LZSS works just fine with port based destination when you setup the sliding window as a ring buffer. I do just this for PCE because the of the ram requirements of hucards (and even CD projects were it's all ram environment). I even have a decoder that will decode packed pixel to planar every so many bytes on the fly along with the ring buffer and port destination. 4bit packed pixel tiles compress much better than planar (composite planar like the snes), but not sure how much this applies to the NES planar format.

Pucrunch is what I use, with a smaller LZ window. The ring buffer is all handled on the decompressor side.

by on (#54506)
tomaitheous wrote:
tepples wrote:
But then LZ77 works a lot better on platforms that have [...] a work RAM big enough to hold a fairly large history[/b] (like Game Boy with rendering on or Super NES)

Actually, LZSS works just fine with port based destination when you setup the sliding window as a ring buffer.

The ring buffer would have to sit in "a work RAM big enough to hold a fairly large history". The NES has 2 KiB, and one-fourth of that is already spoken for (VRAM transfer buffer and stack at $0100-$01FF, and OAM transfer buffer at $0200-$02FF). Or do LZ77-based codecs still provide good compression even with a 256-byte window?

Quote:
4bit packed pixel tiles compress much better than planar (composite planar like the snes), but not sure how much this applies to the NES planar format.

Have you tried compressing 2-bit packed pixel tiles? That's what CMM does. Even on PCE and SNES, 2-bit tiles often show up in things like fonts.

by on (#54510)
tepples wrote:
tomaitheous wrote:
tepples wrote:
But then LZ77 works a lot better on platforms that have [...] a work RAM big enough to hold a fairly large history[/b] (like Game Boy with rendering on or Super NES)

Actually, LZSS works just fine with port based destination when you setup the sliding window as a ring buffer.

The ring buffer would have to sit in "a work RAM big enough to hold a fairly large history". The NES has 2 KiB, and one-fourth of that is already spoken for (VRAM transfer buffer and stack at $0100-$01FF, and OAM transfer buffer at $0200-$02FF). Or do LZ77-based codecs still provide good compression even with a 256-byte window?


I found doing a 512 byte window with Pucrunch to be not much different in size that say 1024 or even 8k LZ window. But then again, Pucrunch is more than just LZSS. LZ77 is too inefficient. Or do you mean LZSS (which is a slight modification to LZ77)? But also, I doubt I would do a NES project that didn't use the extra ram @ $6000.



Quote:
Quote:
4bit packed pixel tiles compress much better than planar (composite planar like the snes), but not sure how much this applies to the NES planar format.

Have you tried compressing 2-bit packed pixel tiles? That's what CMM does. Even on PCE and SNES, 2-bit tiles often show up in things like fonts.


Haven't tried it yet. For font stuff, I tend to do VWF setups. So the font stays in rom until I need to decompress a letter (usually RLZ compression in native planar format) to send off to vram.

by on (#54536)
tomaitheous wrote:
Or do you mean LZSS (which is a slight modification to LZ77)?

By "LZ77" I refer to the entire LZ77 family of codecs based on (start, length) references to history, including LZSS, LZO, Pucrunch, Deflate, and the like, not just the first proposal that strictly alternated matches and literal symbols. For example, the GBA and DS BIOS calls that decompress a format equivalent to LZSS have "LZ77" in the name. But if an LZSS format with a 512-byte history works, great.

by on (#54620)
BUMP: I finally got a chance to try this out.

To get the program to work on Ubuntu Karmic, I needed to add this at the top:
Code:
#include <sys/stat.h>
long filelength(int fileno) {
  struct stat st;
  if (fstat(fileno, &st) < 0) return -1;
  return st.st_size;
}

And there were still warnings:
Code:
compress.c: In function ‘readTiles’:
compress.c:85: warning: ignoring return value of ‘fread’, declared with attribute warn_unused_result
compress.c: In function ‘adjustLengths’:
compress.c:414: warning: ‘bestLength0’ may be used uninitialized in this function
compress.c:414: warning: ‘bestLength1’ may be used uninitialized in this function

"Please inform the source and destination files." isn't so clear. A help message more along the conventions of well-known developer tools would be "usage: compress INFILE.chr OUTFILE.cmm"

But I did manage to compress the 8192 bytes of my current project's CHR to 5337 bytes to give me an idea of what I could expect.

by on (#54728)
What can I say? I guess I'm not the type that releases user-friendly tools. For the record, I never intended to be, I just wanted to share something I though others could possibly find interesting.

To me it really feels like a waste of time putting a lot of effort into something like this while I could be working on my game. I'll probably stick to my game from now, if I want it to ever be released.

With tools it's hard to please everybody: one is worried about licenses, the other is bothered about speed, someone else wants it to run while rendering is on. This is probably why I hate coding tools for other people. With games it's easier, people just want to play them, or not play them.

BTW, I wouldn't worry about those warnings. I have no use for the value returned by fread, if the file suddenly becomes inaccessible as the encoder runs you probably have worse problems to worry about than not being able to compress your NES tiles, such as your hard disk frying. About the two variables, they are set inside a conditional block that always executes at least once, so your smart ass compiler can complain all it wants but the variables aren't used uninitialized.

by on (#54752)
In my opinion, user friendly isn't really necessary, as long as you're here to answer questions, which you appear to be. :)

This is a really cool compression scheme. I don't fully understand the method behind the tables but I can see what is happening enough to trust it to handle my graphics. I'll have to plan on implementing CHR-RAM now.

I think a buffering option would be great, although as you said, you have other things to work on.

tepples wrote:
Quote:
4bit packed pixel tiles compress much better than planar (composite planar like the snes), but not sure how much this applies to the NES planar format.

Have you tried compressing 2-bit packed pixel tiles? That's what CMM does. Even on PCE and SNES, 2-bit tiles often show up in things like fonts.

I was just thinking about this. Will this compressor handle these just as efficiently as other graphics, or could a modified routine improve speed/compression further? Theoretically, I mean - we don't usually need to load and unload fonts rapidly in the middle of a level.

by on (#54754)
1-bit tiles suck under this compression scheme.

by on (#54756)
A run of tiles with only 2 colors would get compressed with 1 bit to indicate the start of a run with new tables, 8 bits to set modes 1, 1, 0, 0, 2 to 4 bits to specify the colors, 8 bits per tile for repeats, and then 8 more bits for each row of pixels that isn't repeated. So you're right that 1-bit tiles get expanded by 12.5%. Perhaps the table definition needs an additional bit to say whether or not to use row repeating in a run.

But without arithmetic coding, is there a good way to encode 1-bit tiles at all?
What schemes have you seen in commercial NES/GB/SNES/GBA games to compress 1-bit tiles?

by on (#54766)
tepples wrote:
What schemes have you seen in commercial NES/GB/SNES/GBA games to compress 1-bit tiles?

The quadtree method I was experimenting with before this one worked on the individual planes of the tiles (i.e. 1-bit tiles). It was slightly worse than this scheme when used on generic tiles, and the decompressor was pretty complex/large.

by on (#55141)
So TileCount is hard-coded at compression time, and if I want to be able to load in smaller chunks I will need to compress each group individually and incbin them together, with a lookup table for each starting address?

It would be nice if the compressor could do this automatically: take an argument for the size of the groups, and begin output with a table of relative pointers to each group. It makes me wonder how much that might affect the compression ratio, though.

by on (#55145)
Well, I don't know how other people usually handle their graphics, but I usually don't have a single CHR file. I have separate files for each character, item, font, and so on. Depending on which tiles will be used at the same time I merge the files to create blocks of tiles that I can compress.

I don't know if implementing a feature like this is worth the trouble. If you have a large CHR file but want to encode it to separate blocks, doesn't that mean that there is a reason you think they shouldn't be packed together, which means it makes sense to have them in separate CHR files to begin with?

About the pointers, I wouldn't make that automatic because I like to have options. You can incbin a compressed block anywhere in your source under a label and you have it's address. However, you might want to handle them differently, you may want to have a bank index along with each pointer (in case you have graphics scattered across different program banks). You might not need a table at all, if you have just a couple of graphic blocks and the code to read from the small table would be larger than using immediate values.

I don't like to work with tools that are too specific and limit what you can do with them. As it is now I don't think it's hard at all to include the files by hand and build your own table of pointers. Like I said before (and you agreed! :wink:) I don't care too much for user friendliness, and this qualifies as it IMO. When I'm programming I just want the tools to be usable, the main project is the game, and that's where I'll put my efforts in order to make it a polished product.

by on (#55153)
Alright, that's fine. :) I know you have lots of other things to work on.

The only reason I asked was because of this:

Quote:
I don't like to work with tools that are too specific and limit what you can do with them.


When I first saw TileCount, I thought, oh cool, I can tell it to replace 16 tiles starting here. When I found out it was encoded as part of the compression it just seemed limiting to me.

My natural inclination is to want to be able to switch out any number of tiles at any location, considering that's the primary advantage of CHR-RAM. Whether you want to change the boss monster while keeping regular enemies around, or just change one type of ground tile, it seems useful to me. But I suppose that could just as easily stay uncompressed and be inserted like normal.

by on (#55166)
UncleSporky wrote:
My natural inclination is to want to be able to switch out any number of tiles at any location, considering that's the primary advantage of CHR-RAM.

I'm not sure I get what you mean here, but you can't just start decompressing from arbitrary positions in the stream, because of the "blocky" nature of the scheme. Are you saying you'd like to force the start of a new block at certain locations so that you could start decompressing from that point on?

Quote:
Whether you want to change the boss monster while keeping regular enemies around, or just change one type of ground tile, it seems useful to me.

To me, the natural way to do those things is to compress the basic tileset to a single file and put the boss and new ground tiles in different files. You decompress the basic tileset before the level starts, and later you "patch" the basic tileset with whatever you want, replacing whatever you want.

Quote:
But I suppose that could just as easily stay uncompressed and be inserted like normal.

I haven't coded a buffered version of the decompressor yet, so you can't really decompress with rendering on yet. In my own game I don't use compression for tiles that are changed during the level, because I want them to be updated as quickly as possible. I believe the original Sonic games are like this as well.

by on (#55170)
tokumaru wrote:
UncleSporky wrote:
My natural inclination is to want to be able to switch out any number of tiles at any location, considering that's the primary advantage of CHR-RAM.

I'm not sure I get what you mean here, but you can't just start decompressing from arbitrary positions in the stream, because of the "blocky" nature of the scheme. Are you saying you'd like to force the start of a new block at certain locations so that you could start decompressing from that point on?

Yes, that's what I've been saying. I figured that out about the blocky nature, and since I can't just load in as many as I want, I at least wanted the compressor to be able to stop and start a new segment at a specific length.

Right now it compresses as many tiles as it finds - in your example it's 256 tiles. I want to be able to tell it to compress 32 tiles at a time so that I can "patch in" more tiles, as you say.

Don't worry about it, I'll just make seperate chr files in 32 tile chunks and compress them individually.

by on (#55171)
UncleSporky wrote:
Don't worry about it, I'll just make seperate chr files in 32 tile chunks and compress them individually.

That shouldn't be a problem. Given that runs of the same tables are only a couple tiles long anyway, the only significant overhead of each compressed segment is 1 byte for the length of the segment and 2 bytes for the starting address in your directory.

by on (#55526)
I made a collection of CHRs ripped from demos and homebrews. I call it the NESdev Corpus. Here's the download link:

http://www.mediafire.com/?tdilw2ghk1g

It has nearly 250k of graphics data spread across 14 CHR files. Large (>8k) CHR files have been split into 8k chunks. It also includes a text file with the original file sizes and the sizes they've been compressed to using Tokumaru's latest CHR compressor. Hope this helps with testing.

by on (#58142)
SO..,thanks to this it's possible to compress tiles into very small KB size?
But..it is possible to DECOMPRESS tiles from ROM,edit it,compress it again,and finally,Put compressed tiles into rom?
I'm pretty interested sice I'm hacking GDG(GO Dizzy GO),Which is Codemasters game.

by on (#58159)
No, you can't use my application for hacking, at least not in a straightforward way. First because my format is slightly different than Codemasters'. And Codemasters used different compression algorithms, so the one used in GO Dizzy GO might not even be the same one as Bee52.

But if you're really up to the the task, you could debug the game and find the routine that decompresses tiles (not caring if it's the same one as Bee52 or not) and set up a breakpoint on calls to it, so that you can take note of where in the ROM the compressed graphics are and dump the tiles after they are decompressed.

Then you edit the tiles at will, and once you're done you can compress them with my application. Then you could replace the games decompression routine with mine (it's smaller than the one used in Bee52 at least) and replace the graphics with your own.

Not a simple task by any means, but unless there are tools specifically written for the games you hack you have to do this sort of old-school hardcore hacking.

by on (#58163)
As I didn't understand anything,I guess i'll drop the subject untill i learn more about NES,and 6502.
Re:
by on (#98729)
tokumaru wrote:
I didn't time it. Just run the ROM yourself with FCEUXD's tile viewer open and you can have an idea of how long it takes to decode the first half of SMB's tileset (it's about as long as it takes for them to be displayed, although some of the time is spent setting up the name and attribute tables and other kinds of initialization). FXEUXD seems to lag a bit when it starts though, so I can't properly time it unless I use the NMI to count how many frames are needed until all the tiles are done.

I timed it using NintendulatorDX (checking my options for tile compression in Streemerz). The "jsr Decompress" takes 1,194,448 cycles to decompress that 4KB worth of SMB tileset, that's approximately 40 frames (668 ms) on NTSC NES.
Re: Tile encoder/decoder
by on (#116661)
Hey tokumaru thanks for providing this. That's some impressive ratios.
Re:
by on (#116662)
tokumaru wrote:
Well, I don't know how other people usually handle their graphics, but I usually don't have a single CHR file. I have separate files for each character, item, font, and so on. Depending on which tiles will be used at the same time I merge the files to create blocks of tiles that I can compress.

I don't know if implementing a feature like this is worth the trouble. If you have a large CHR file but want to encode it to separate blocks, doesn't that mean that there is a reason you think they shouldn't be packed together, which means it makes sense to have them in separate CHR files to begin with?

About the pointers, I wouldn't make that automatic because I like to have options. You can incbin a compressed block anywhere in your source under a label and you have it's address. However, you might want to handle them differently, you may want to have a bank index along with each pointer (in case you have graphics scattered across different program banks). You might not need a table at all, if you have just a couple of graphic blocks and the code to read from the small table would be larger than using immediate values.

I don't like to work with tools that are too specific and limit what you can do with them. As it is now I don't think it's hard at all to include the files by hand and build your own table of pointers. Like I said before (and you agreed! :wink:) I don't care too much for user friendliness, and this qualifies as it IMO. When I'm programming I just want the tools to be usable, the main project is the game, and that's where I'll put my efforts in order to make it a polished product.


I think that the codec should support arbitrary numbers of tiles (if it doesn't already, correct me if I'm wrong). In a CHR RAM project stuff is going to be loaded in pieces not entire banks.
Re: Tile encoder/decoder
by on (#116664)
Then make "separate files for each character, item, font, and so on" like tokumaru recommended, and load multiple files into CHR RAM before the level starts.
Re: Tile encoder/decoder
by on (#116672)
tepples wrote:
Then make "separate files for each character, item, font, and so on" like tokumaru recommended, and load multiple files into CHR RAM before the level starts.


Yeah that's how I would do it - I guess I was just confused, for some reason I got the idea that the compressor expected 256 tiles exactly.
Re: Tile encoder/decoder
by on (#133538)
My test of tokumaru compression on tiles archives from battletoads:
table for unpacked, original packed, and tokumaru packed.
Re: Tile encoder/decoder
by on (#133541)
And the same thing in tab-separated values for people who happen not to have Microsoft Office installed:
Re: Tile encoder/decoder
by on (#133542)
tepples wrote:
And the same thing in tab-separated values for people who happen not to have Microsoft Office installed:

I've used spread32 , it's 1Mb size. :beer:
Re: Tile encoder/decoder
by on (#169865)
I rewrote a compressor / decompressor for this scheme from scratch.
Incidentally, it also compresses marginally better than Tokumaru's tool (due to better algorithm in finding block splitting points). The compression format is the same though.

It can be downloaded (C++ source) at: http://iki.fi/bisqwit/src/tokumaru-source.zip
Precompiled version for x86_64 Windows: http://iki.fi/bisqwit/src/tokumaru-w64.exe
Precompiled version for i386 Windows: http://iki.fi/bisqwit/src/tokumaru-w32.exe


It can be downloaded at: http://bisqwit.iki.fi/source/tokumaru.html
Re: Tile encoder/decoder
by on (#169871)
The C++ source link is 404 Not Found, and it is not listed on the page one level up. But through "access the directory list directly" I found it: tokumaru. with no extension.

The origin of this software must not be misrepresented

zlib license

What sort of speedup does use of threads typically give? Because in a large build, it might be wiser to default to one thread and use job-level parallelism, where make -j3 calls multiple tokumaru instances at once (along with multiple converters for other things).

And things like "%u tiles (%u bytes) decompressed into %u bytes\n" typically go to std::stderr, not std:stdout, so that they don't mix with the output even if quiet is disabled.
Re: Tile encoder/decoder
by on (#169874)
The source link has been fixed. I forgot to actually click submit to my edit to the post. Sorry about that.
Threads give a significant speedup when running at the highest optimization levels. The process is highly parallelizable. Threads can be explicitly disabled with a commandline option.

As for messages, I have typically a guideline where errors go into stderr and everything else goes into stdout. The exception is if the actual compressed output goes into stdout; then everything else goes into stderr. This version does not support compressing to stdout currently.

Yes, zlib license. Unless there is some other point in your quote? I so dislike contextless quotations. Implications. If you are trying to accuse that I am misrepresenting the author of the original software, my program is written entirely from scratch based on the algorithm documentation I collected yesterday, and even then I am providing a credited link to the code that I read. It is neither a modification nor a port of other software. This is the original software, even though what it seeks to accomplish is the same as Tokumaru's program.
Re: Tile encoder/decoder
by on (#169889)
How do you arrive at an algorithm that achieves the optimal split point or just optimal ways to apply compression in general? Is it a greedy algorithm? Are multiple arbitrary permutations performed and then compared?
Re: Tile encoder/decoder
by on (#169891)
IIRC, testing all possible length combinations of 2 consecutive blocks worked really well for me.
Re: Tile encoder/decoder
by on (#169896)
Bisqwit wrote:
Yes, zlib license. Unless there is some other point in your quote? I so dislike contextless quotations.

Just summarizing for the benefit of readers before they click through. I've seen a lot of projects on GitHub, for example, that make it hard to find the license info, with no top-level LICENSE or COPYING file and no license notice at the bottom of README.
Re: Tile encoder/decoder
by on (#169918)
Drag wrote:
How do you arrive at an algorithm that achieves the optimal split point or just optimal ways to apply compression in general? Is it a greedy algorithm? Are multiple arbitrary permutations performed and then compared?

The way I do it here is that I make a directed acyclic graph of all possible encode-lengths at all possible offsets, and then use Dijkstra's algorithm with a priority queue to find the shortest path through that graph. The path length is the number of bits generated for that particular arc.
This works very well since the splits are independent: When a block is split, no data from the previous block is carried over to the next block. It is also efficient because of the high granularity of block splits (every 16 bytes), and high likelihood of short splits being most efficient.
The compression level is just a cap on the encode-lengths to test. Without a cap, the performance would be O(n^2). With a cap, it becomes O(n*cap). In practice even short caps work really well.

By contrast, this approach would not work well with e.g. deflate, because the number of plausible block lengths is several orders of magnitudes higher.
Re: Tile encoder/decoder
by on (#169963)
Ah, interesting. So both methods explore all possible permutations, just with different scopes? The use of Dijkstra's algorithm is pretty clever, I overlook that a lot. Tokumaru's method (a greedy algorithm) is what I would've come up with.

This question is because several years ago, Disch was working on a compressor for a scheme like the one in Kirby's Adventure, where there's several different compression algorithms all working together, but a challenge was figuring out how to determine which permutation of compressed chunks yielded the best ratio. It's funny to see that challenge cropping up again in this encoder. :P
Re: Tile encoder/decoder
by on (#169965)
Drag wrote:
It's funny to see that challenge cropping up again in this encoder. :P

It occurs pretty often in the theme of compression. Pretty much every compressor that has two or more ways of encoding same things runs into this topic. It is also the first time that I use Dijkstra's algorithm in this context.
Re: Tile encoder/decoder
by on (#169969)
Drag wrote:
Tokumaru's method (a greedy algorithm) is what I would've come up with.

A strictly greedy algorithm would select the best length for the current block regardless of what comes next. It's been a long time, but if I'm not mistaken, I kept increasing the length of the current block until the compression ratio started to drop, and then I tested how well the next block compressed for all possible lengths of the first block, from the calculated maximum down to 1, and picked the best cimbination. Or something like that! :mrgreen:
Re: Tile encoder/decoder
by on (#170082)
Update: I added a CA65-compatible decompressor module and a test ROM.

Differences to Tokumaru's decompressor: At feature parity,
Code size is $EE bytes (2 bytes smaller) $D9 bytes (23 bytes smaller)
RAM usage is 19 bytes (13 bytes smaller)
Speed differences not measured.

I also added support for compressing and decompressing from/to stdin/stdout.
Download: http://bisqwit.iki.fi/source/tokumaru.html

If the compression format was changed a little, the decompressor could be made even smaller without sacrificing compression ratio.
Namely, inverting the meaning of the first color bit in the tile data, so that there will be fewer special cases in the decompression code.

EDIT: Yeah, I just went ahead and implemented that extension as an optional format (-e option). The decompressor is now $E7 bytes for extended format, $EC bytes for non-extended format.
EDIT 2: $DE and $E3 bytes now respectively.


Image

EDIT: Decided to make various settings user-adjustable.

Code:
;  USER-ADJUSTABLE SETTINGS

EXTENDED_FORMAT=1
; ^ Set to 1 if you compressed with -e.
;   Makes decompressor 5 bytes shorter with very minor speed impact.
;   If you compressed with -e3, set to 3. If with -e2, set to 2.
;   +2 makes decompresser 1 byte smaller, but consumes 2 more bytes of RAM.

FASTER=0
; ^ Set to 1 if you want faster code.
;   It will cause ReadBit to be inlined, and some other assorted changes.
;   Makes decompressor 37 bytes longer, but about 10 cycles faster per bit.

RAMBUFFER=1
; ^ Set to 1 if you can spare 7 more bytes of zero-page RAM.
;   Makes decompressor 6-7 bytes shorter, and 8-10 cycles faster per tile.
;   If FASTER=1, makes 5-6 bytes shorter, and 28-30 cycles faster per tile.

RAMTEMP=1
; ^ Set to 1 if you can spare 3 more bytes of zero-page RAM.
;   Makes decompressor 1-2 bytes longer, but 1.5 cycles faster per bit.

; SUMMARY -- SIZE PROFILE FOR DECOMPRESSOR:
;
;  EXTENDED_FORMAT FASTER RAMBUFFER RAMTEMP   CODE SIZE   RAM USE   STACK USE  RUNTIME
;                1      0         1       0   $0D4 (212)  19 bytes   5 bytes   1161959 cycles
;                1      0         1       1   $0D5 (213)  22 bytes   2 bytes   1144551 cycles
;                0      0         1       0   $0D9 (217)  19 bytes   5 bytes   1159744 cycles
;                1      0         0       0   $0DA (218)  12 bytes  12 bytes   1162215 cycles
;                0      0         1       1   $0DA (218)  22 bytes   2 bytes   1142336 cycles
;                1      0         0       1   $0DC (220)  15 bytes   9 bytes   1145319 cycles
;                0      0         0       0   $0DF (223)  12 bytes  12 bytes   1161792 cycles
;                0      0         0       1   $0E1 (225)  15 bytes   9 bytes   1144896 cycles
;                1      1         1       0   $0F9 (249)  19 bytes   5 bytes   981134 cycles
;                1      1         1       1   $0FA (250)  22 bytes   2 bytes   963726 cycles
;                1      1         0       0   $0FE (254)  12 bytes  12 bytes   968820 cycles
;                1      1         0       1   $100 (256)  15 bytes   9 bytes   965518 cycles
;                0      1         1       0   $102 (258)  19 bytes   5 bytes   970325 cycles
;                0      1         1       1   $103 (259)  22 bytes   2 bytes   952917 cycles
;                0      1         0       0   $107 (263)  12 bytes  12 bytes   962021 cycles
;                0      1         0       1   $109 (265)  15 bytes   9 bytes   954709 cycles
;
; END OF USER-ADJUSTABLE SETTINGS

The "runtime" column lists the number of cycles it took to decompress the first 4096 bytes ($1000) of the CHR-RAM data for the demo included with the program. Stack is the number of bytes it reserved from stack in addition to the function call frame; RAM and code size are automatically gathered from the linker statistics.

EDIT: Version 1.3.0 released. Updated the stats again. The decompressor got smaller, again.
Re: Tile encoder/decoder
by on (#170619)
For curiosity's sake, I compressed some chr files using jbigkit to see how it stacks up to Tokumaru compression.

Here are the compression ratios I got (uncompressed size / compressed size):
Code:
Tokumaru: 1.83
jbig85:   1.84
jbig:     2.04

And here are the files I tested: battlekid.chr geminim.chr gemventure.ch dpadhero.chr cmc80s.chr

Tokumaru compression is as good as jbig85, but slightly worse than fully-featured jbig. I don't think jbig is worth implementing on the NES though. It's much too complicated and requires too much RAM.
Re: Tile encoder/decoder
by on (#177817)
I wanted to try this compression but I cannot manage to compile it with mingw. I could try again with Linux, but nonetheless, there's still no reason I would not be allowed to compile this with mingw. Requiring C++14 which was only very recently imported in gcc is not the brightest idea, either.
Re: Tile encoder/decoder
by on (#177824)
What error do you get in MinGW? Do you know how to copy and paste the error from MinGW?
Re: Tile encoder/decoder
by on (#177846)
I get
Code:
tokumaru.cc:37:18: fatal error: omp.h: No such file or directory
 # include <omp.h>
                  ^
compilation terminated.
make: *** [tokumaru] Error 1


After commneting out those 3 lines in "tokumaru.cc":
Code:
#ifdef _OPENMP
# include <omp.h>
#endif


I get :
Code:
In file included from c:\mingw\lib\gcc\mingw32\4.9.3\include\c++\bits\stl_algo.h:59:0,
                 from c:\mingw\lib\gcc\mingw32\4.9.3\include\c++\algorithm:62,
                 from tokumaru.cc:30:
c:\mingw\lib\gcc\mingw32\4.9.3\include\c++\cstdlib:201:11: error: '::lldiv_t' has not been declared
   using ::lldiv_t;
           ^
c:\mingw\lib\gcc\mingw32\4.9.3\include\c++\cstdlib:207:11: error: '::_Exit' has not been declared
   using ::_Exit;
           ^
c:\mingw\lib\gcc\mingw32\4.9.3\include\c++\cstdlib:211:11: error: '::llabs' has not been declared
   using ::llabs;
           ^
c:\mingw\lib\gcc\mingw32\4.9.3\include\c++\cstdlib:213:10: error: 'lldiv_t' does not name a type
   inline lldiv_t
          ^
c:\mingw\lib\gcc\mingw32\4.9.3\include\c++\cstdlib:217:11: error: '::lldiv' has not been declared
   using ::lldiv;
           ^
c:\mingw\lib\gcc\mingw32\4.9.3\include\c++\cstdlib:228:11: error: '::atoll' has not been declared
   using ::atoll;
           ^
c:\mingw\lib\gcc\mingw32\4.9.3\include\c++\cstdlib:229:11: error: '::strtoll' has not been declared
   using ::strtoll;
           ^
c:\mingw\lib\gcc\mingw32\4.9.3\include\c++\cstdlib:230:11: error: '::strtoull' has not been declared
   using ::strtoull;
           ^
c:\mingw\lib\gcc\mingw32\4.9.3\include\c++\cstdlib:232:11: error: '::strtof' has not been declared
   using ::strtof;
           ^
c:\mingw\lib\gcc\mingw32\4.9.3\include\c++\cstdlib:233:11: error: '::strtold' has not been declared
   using ::strtold;
           ^
c:\mingw\lib\gcc\mingw32\4.9.3\include\c++\cstdlib:241:22: error: '__gnu_cxx::lldiv_t' has not been declared
   using ::__gnu_cxx::lldiv_t;
                      ^
c:\mingw\lib\gcc\mingw32\4.9.3\include\c++\cstdlib:243:22: error: '__gnu_cxx::_Exit' has not been declared
   using ::__gnu_cxx::_Exit;
                      ^
c:\mingw\lib\gcc\mingw32\4.9.3\include\c++\cstdlib:245:22: error: '__gnu_cxx::llabs' has not been declared
   using ::__gnu_cxx::llabs;
                      ^
c:\mingw\lib\gcc\mingw32\4.9.3\include\c++\cstdlib:246:22: error: '__gnu_cxx::div' has not been declared
   using ::__gnu_cxx::div;
                      ^
c:\mingw\lib\gcc\mingw32\4.9.3\include\c++\cstdlib:247:22: error: '__gnu_cxx::lldiv' has not been declared
   using ::__gnu_cxx::lldiv;
                      ^
c:\mingw\lib\gcc\mingw32\4.9.3\include\c++\cstdlib:249:22: error: '__gnu_cxx::atoll' has not been declared
   using ::__gnu_cxx::atoll;
                      ^
c:\mingw\lib\gcc\mingw32\4.9.3\include\c++\cstdlib:250:22: error: '__gnu_cxx::strtof' has not been declared
   using ::__gnu_cxx::strtof;
                      ^
c:\mingw\lib\gcc\mingw32\4.9.3\include\c++\cstdlib:251:22: error: '__gnu_cxx::strtoll' has not been declared
   using ::__gnu_cxx::strtoll;
                      ^
c:\mingw\lib\gcc\mingw32\4.9.3\include\c++\cstdlib:252:22: error: '__gnu_cxx::strtoull' has not been declared
   using ::__gnu_cxx::strtoull;
                      ^
c:\mingw\lib\gcc\mingw32\4.9.3\include\c++\cstdlib:253:22: error: '__gnu_cxx::strtold' has not been declared
   using ::__gnu_cxx::strtold;
                      ^
In file included from c:\mingw\include\wchar.h:208:0,
                 from c:\mingw\lib\gcc\mingw32\4.9.3\include\c++\cwchar:44,
                 from c:\mingw\lib\gcc\mingw32\4.9.3\include\c++\bits\postypes.h:40,
                 from c:\mingw\lib\gcc\mingw32\4.9.3\include\c++\bits\char_traits.h:40,
                 from c:\mingw\lib\gcc\mingw32\4.9.3\include\c++\string:40,
                 from c:\mingw\lib\gcc\mingw32\4.9.3\include\c++\random:40,
                 from c:\mingw\lib\gcc\mingw32\4.9.3\include\c++\bits\stl_algo.h:66,
                 from c:\mingw\lib\gcc\mingw32\4.9.3\include\c++\algorithm:62,
                 from tokumaru.cc:30:
c:\mingw\include\sys/stat.h:173:14: error: '_dev_t' does not name a type
 struct _stat __struct_stat_defined( _off_t, time_t );
              ^
c:\mingw\include\sys/stat.h:173:14: error: '_ino_t' does not name a type
 struct _stat __struct_stat_defined( _off_t, time_t );
              ^
c:\mingw\include\sys/stat.h:173:14: error: '_mode_t' does not name a type
 struct _stat __struct_stat_defined( _off_t, time_t );
              ^
c:\mingw\include\sys/stat.h:173:14: error: '_dev_t' does not name a type
 struct _stat __struct_stat_defined( _off_t, time_t );
              ^
c:\mingw\include\sys/stat.h:173:14: error: '_off_t' does not name a type
 struct _stat __struct_stat_defined( _off_t, time_t );
              ^
c:\mingw\include\sys/stat.h:173:14: error: 'time_t' does not name a type
 struct _stat __struct_stat_defined( _off_t, time_t );
              ^
c:\mingw\include\sys/stat.h:173:14: error: 'time_t' does not name a type
 struct _stat __struct_stat_defined( _off_t, time_t );
              ^
c:\mingw\include\sys/stat.h:173:14: error: 'time_t' does not name a type
 struct _stat __struct_stat_defined( _off_t, time_t );
              ^
c:\mingw\include\sys/stat.h:180:13: error: '_dev_t' does not name a type
 struct stat __struct_stat_defined( _off_t, time_t );
             ^
c:\mingw\include\sys/stat.h:180:13: error: '_ino_t' does not name a type
 struct stat __struct_stat_defined( _off_t, time_t );
             ^
c:\mingw\include\sys/stat.h:180:13: error: '_mode_t' does not name a type
 struct stat __struct_stat_defined( _off_t, time_t );
             ^
c:\mingw\include\sys/stat.h:180:13: error: '_dev_t' does not name a type
 struct stat __struct_stat_defined( _off_t, time_t );
             ^
c:\mingw\include\sys/stat.h:180:13: error: '_off_t' does not name a type
 struct stat __struct_stat_defined( _off_t, time_t );
             ^
c:\mingw\include\sys/stat.h:180:13: error: 'time_t' does not name a type
 struct stat __struct_stat_defined( _off_t, time_t );
             ^
c:\mingw\include\sys/stat.h:180:13: error: 'time_t' does not name a type
 struct stat __struct_stat_defined( _off_t, time_t );
             ^
c:\mingw\include\sys/stat.h:180:13: error: 'time_t' does not name a type
 struct stat __struct_stat_defined( _off_t, time_t );
             ^
c:\mingw\include\sys/stat.h:188:17: error: '_dev_t' does not name a type
 struct _stati64 __struct_stat_defined( __off64_t, time_t );
                 ^
c:\mingw\include\sys/stat.h:188:17: error: '_ino_t' does not name a type
 struct _stati64 __struct_stat_defined( __off64_t, time_t );
                 ^
c:\mingw\include\sys/stat.h:188:17: error: '_mode_t' does not name a type
 struct _stati64 __struct_stat_defined( __off64_t, time_t );
                 ^
c:\mingw\include\sys/stat.h:188:17: error: '_dev_t' does not name a type
 struct _stati64 __struct_stat_defined( __off64_t, time_t );
                 ^
c:\mingw\include\sys/stat.h:188:17: error: '__off64_t' does not name a type
 struct _stati64 __struct_stat_defined( __off64_t, time_t );
                 ^
c:\mingw\include\sys/stat.h:188:17: error: 'time_t' does not name a type
 struct _stati64 __struct_stat_defined( __off64_t, time_t );
                 ^
c:\mingw\include\sys/stat.h:188:17: error: 'time_t' does not name a type
 struct _stati64 __struct_stat_defined( __off64_t, time_t );
                 ^
c:\mingw\include\sys/stat.h:188:17: error: 'time_t' does not name a type
 struct _stati64 __struct_stat_defined( __off64_t, time_t );
                 ^
c:\mingw\include\sys/stat.h:195:17: error: '_dev_t' does not name a type
 struct __stat64 __struct_stat_defined( __off64_t, __time64_t );
                 ^
c:\mingw\include\sys/stat.h:195:17: error: '_ino_t' does not name a type
 struct __stat64 __struct_stat_defined( __off64_t, __time64_t );
                 ^
c:\mingw\include\sys/stat.h:195:17: error: '_mode_t' does not name a type
 struct __stat64 __struct_stat_defined( __off64_t, __time64_t );
                 ^
c:\mingw\include\sys/stat.h:195:17: error: '_dev_t' does not name a type
 struct __stat64 __struct_stat_defined( __off64_t, __time64_t );
                 ^
c:\mingw\include\sys/stat.h:195:17: error: '__off64_t' does not name a type
 struct __stat64 __struct_stat_defined( __off64_t, __time64_t );
                 ^
c:\mingw\include\sys/stat.h:195:17: error: '__time64_t' does not name a type
 struct __stat64 __struct_stat_defined( __off64_t, __time64_t );
                 ^
c:\mingw\include\sys/stat.h:195:17: error: '__time64_t' does not name a type
 struct __stat64 __struct_stat_defined( __off64_t, __time64_t );
                 ^
c:\mingw\include\sys/stat.h:195:17: error: '__time64_t' does not name a type
 struct __stat64 __struct_stat_defined( __off64_t, __time64_t );
                 ^
In file included from c:\mingw\include\wchar.h:233:0,
                 from c:\mingw\lib\gcc\mingw32\4.9.3\include\c++\cwchar:44,
                 from c:\mingw\lib\gcc\mingw32\4.9.3\include\c++\bits\postypes.h:40,
                 from c:\mingw\lib\gcc\mingw32\4.9.3\include\c++\bits\char_traits.h:40,
                 from c:\mingw\lib\gcc\mingw32\4.9.3\include\c++\string:40,
                 from c:\mingw\lib\gcc\mingw32\4.9.3\include\c++\random:40,
                 from c:\mingw\lib\gcc\mingw32\4.9.3\include\c++\bits\stl_algo.h:66,
                 from c:\mingw\lib\gcc\mingw32\4.9.3\include\c++\algorithm:62,
                 from tokumaru.cc:30:
c:\mingw\include\io.h:335:21: error: 'time_t' does not name a type
 struct _wfinddata_t __struct_finddata_t (time_t, _fsize_t);
                     ^
c:\mingw\include\io.h:335:21: error: 'time_t' does not name a type
 struct _wfinddata_t __struct_finddata_t (time_t, _fsize_t);
                     ^
c:\mingw\include\io.h:335:21: error: 'time_t' does not name a type
 struct _wfinddata_t __struct_finddata_t (time_t, _fsize_t);
                     ^
c:\mingw\include\io.h:336:24: error: 'time_t' does not name a type
 struct _wfinddatai64_t __struct_finddata_t (time_t, __int64);
                        ^
c:\mingw\include\io.h:336:24: error: 'time_t' does not name a type
 struct _wfinddatai64_t __struct_finddata_t (time_t, __int64);
                        ^
c:\mingw\include\io.h:336:24: error: 'time_t' does not name a type
 struct _wfinddatai64_t __struct_finddata_t (time_t, __int64);
                        ^
c:\mingw\include\io.h:362:24: error: '__time64_t' does not name a type
 struct __wfinddata64_t __struct_finddata_t (__time64_t, __int64);
                        ^
c:\mingw\include\io.h:362:24: error: '__time64_t' does not name a type
 struct __wfinddata64_t __struct_finddata_t (__time64_t, __int64);
                        ^
c:\mingw\include\io.h:362:24: error: '__time64_t' does not name a type
 struct __wfinddata64_t __struct_finddata_t (__time64_t, __int64);
                        ^
In file included from c:\mingw\lib\gcc\mingw32\4.9.3\include\c++\bits\postypes.h:40:0,
                 from c:\mingw\lib\gcc\mingw32\4.9.3\include\c++\bits\char_traits.h:40,
                 from c:\mingw\lib\gcc\mingw32\4.9.3\include\c++\string:40,
                 from c:\mingw\lib\gcc\mingw32\4.9.3\include\c++\random:40,
                 from c:\mingw\lib\gcc\mingw32\4.9.3\include\c++\bits\stl_algo.h:66,
                 from c:\mingw\lib\gcc\mingw32\4.9.3\include\c++\algorithm:62,
                 from tokumaru.cc:30:
c:\mingw\lib\gcc\mingw32\4.9.3\include\c++\cwchar:146:11: error: '::fwide' has not been declared
   using ::fwide;
           ^
c:\mingw\lib\gcc\mingw32\4.9.3\include\c++\cwchar:153:11: error: '::mbsinit' has not been declared
   using ::mbsinit;
           ^
c:\mingw\lib\gcc\mingw32\4.9.3\include\c++\cwchar:164:11: error: '::vfwscanf' has not been declared
   using ::vfwscanf;
           ^
c:\mingw\lib\gcc\mingw32\4.9.3\include\c++\cwchar:170:11: error: '::vswscanf' has not been declared
   using ::vswscanf;
           ^
c:\mingw\lib\gcc\mingw32\4.9.3\include\c++\cwchar:174:11: error: '::vwscanf' has not been declared
   using ::vwscanf;
           ^
c:\mingw\lib\gcc\mingw32\4.9.3\include\c++\cwchar:191:11: error: '::wcstof' has not been declared
   using ::wcstof;
           ^
c:\mingw\lib\gcc\mingw32\4.9.3\include\c++\cwchar:198:11: error: '::wmemcmp' has not been declared
   using ::wmemcmp;
           ^
c:\mingw\lib\gcc\mingw32\4.9.3\include\c++\cwchar:199:11: error: '::wmemcpy' has not been declared
   using ::wmemcpy;
           ^
c:\mingw\lib\gcc\mingw32\4.9.3\include\c++\cwchar:200:11: error: '::wmemmove' has not been declared
   using ::wmemmove;
           ^
c:\mingw\lib\gcc\mingw32\4.9.3\include\c++\cwchar:201:11: error: '::wmemset' has not been declared
   using ::wmemset;
           ^
c:\mingw\lib\gcc\mingw32\4.9.3\include\c++\cwchar:208:11: error: '::wmemchr' has not been declared
   using ::wmemchr;
           ^
c:\mingw\lib\gcc\mingw32\4.9.3\include\c++\cwchar: In function 'wchar_t* std::wmemchr(wchar_t*, wchar_t, std::size_t)':
c:\mingw\lib\gcc\mingw32\4.9.3\include\c++\cwchar:229:61: error: invalid conversion from 'const wchar_t*' to 'wchar_t*' [-fpermissive]
   { return wmemchr(const_cast<const wchar_t*>(__p), __c, __n); }
                                                             ^
c:\mingw\lib\gcc\mingw32\4.9.3\include\c++\cwchar:228:3: note: initializing argument 1 of 'wchar_t* std::wmemchr(wchar_t*, wchar_t, std::size_t)'
   wmemchr(wchar_t* __p, wchar_t __c, size_t __n)
   ^
c:\mingw\lib\gcc\mingw32\4.9.3\include\c++\cwchar: At global scope:
c:\mingw\lib\gcc\mingw32\4.9.3\include\c++\cwchar:248:11: error: '::wcstold' has not been declared
   using ::wcstold;
           ^
c:\mingw\lib\gcc\mingw32\4.9.3\include\c++\cwchar:257:11: error: '::wcstoll' has not been declared
   using ::wcstoll;
           ^
c:\mingw\lib\gcc\mingw32\4.9.3\include\c++\cwchar:258:11: error: '::wcstoull' has not been declared
   using ::wcstoull;
           ^
c:\mingw\lib\gcc\mingw32\4.9.3\include\c++\cwchar:264:22: error: '__gnu_cxx::wcstold' has not been declared
   using ::__gnu_cxx::wcstold;
                      ^
c:\mingw\lib\gcc\mingw32\4.9.3\include\c++\cwchar:265:22: error: '__gnu_cxx::wcstoll' has not been declared
   using ::__gnu_cxx::wcstoll;
                      ^
c:\mingw\lib\gcc\mingw32\4.9.3\include\c++\cwchar:266:22: error: '__gnu_cxx::wcstoull' has not been declared
   using ::__gnu_cxx::wcstoull;
                      ^
c:\mingw\lib\gcc\mingw32\4.9.3\include\c++\cwchar:280:14: error: 'std::wcstof' has not been declared
   using std::wcstof;
              ^
c:\mingw\lib\gcc\mingw32\4.9.3\include\c++\cwchar:283:14: error: 'std::vfwscanf' has not been declared
   using std::vfwscanf;
              ^
c:\mingw\lib\gcc\mingw32\4.9.3\include\c++\cwchar:286:14: error: 'std::vswscanf' has not been declared
   using std::vswscanf;
              ^
c:\mingw\lib\gcc\mingw32\4.9.3\include\c++\cwchar:289:14: error: 'std::vwscanf' has not been declared
   using std::vwscanf;
              ^
c:\mingw\lib\gcc\mingw32\4.9.3\include\c++\cwchar:293:14: error: 'std::wcstold' has not been declared
   using std::wcstold;
              ^
c:\mingw\lib\gcc\mingw32\4.9.3\include\c++\cwchar:294:14: error: 'std::wcstoll' has not been declared
   using std::wcstoll;
              ^
c:\mingw\lib\gcc\mingw32\4.9.3\include\c++\cwchar:295:14: error: 'std::wcstoull' has not been declared
   using std::wcstoull;
              ^
In file included from c:\mingw\lib\gcc\mingw32\4.9.3\include\c++\string:40:0,
                 from c:\mingw\lib\gcc\mingw32\4.9.3\include\c++\random:40,
                 from c:\mingw\lib\gcc\mingw32\4.9.3\include\c++\bits\stl_algo.h:66,
                 from c:\mingw\lib\gcc\mingw32\4.9.3\include\c++\algorithm:62,
                 from tokumaru.cc:30:
c:\mingw\lib\gcc\mingw32\4.9.3\include\c++\bits\char_traits.h: In static member function 'static int std::char_traits<wchar_t>::compare(const char_type*, const char_type*, std::size_t)':
c:\mingw\lib\gcc\mingw32\4.9.3\include\c++\bits\char_traits.h:330:39: error: 'wmemcmp' was not declared in this scope
       { return wmemcmp(__s1, __s2, __n); }
                                       ^
c:\mingw\lib\gcc\mingw32\4.9.3\include\c++\bits\char_traits.h: In static member function 'static const char_type* std::char_traits<wchar_t>::find(const char_type*, std::size_t, const char_type&)':
c:\mingw\lib\gcc\mingw32\4.9.3\include\c++\bits\char_traits.h:338:37: error: invalid conversion from 'const char_type* {aka const wchar_t*}' to 'wchar_t*' [-fpermissive]
       { return wmemchr(__s, __a, __n); }
                                     ^
In file included from c:\mingw\lib\gcc\mingw32\4.9.3\include\c++\bits\postypes.h:40:0,
                 from c:\mingw\lib\gcc\mingw32\4.9.3\include\c++\bits\char_traits.h:40,
                 from c:\mingw\lib\gcc\mingw32\4.9.3\include\c++\string:40,
                 from c:\mingw\lib\gcc\mingw32\4.9.3\include\c++\random:40,
                 from c:\mingw\lib\gcc\mingw32\4.9.3\include\c++\bits\stl_algo.h:66,
                 from c:\mingw\lib\gcc\mingw32\4.9.3\include\c++\algorithm:62,
                 from tokumaru.cc:30:
c:\mingw\lib\gcc\mingw32\4.9.3\include\c++\cwchar:228:3: note: initializing argument 1 of 'wchar_t* std::wmemchr(wchar_t*, wchar_t, std::size_t)'
   wmemchr(wchar_t* __p, wchar_t __c, size_t __n)
   ^
In file included from c:\mingw\lib\gcc\mingw32\4.9.3\include\c++\string:40:0,
                 from c:\mingw\lib\gcc\mingw32\4.9.3\include\c++\random:40,
                 from c:\mingw\lib\gcc\mingw32\4.9.3\include\c++\bits\stl_algo.h:66,
                 from c:\mingw\lib\gcc\mingw32\4.9.3\include\c++\algorithm:62,
                 from tokumaru.cc:30:
c:\mingw\lib\gcc\mingw32\4.9.3\include\c++\bits\char_traits.h: In static member function 'static std::char_traits<wchar_t>::char_type* std::char_traits<wchar_t>::move(std::char_traits<wchar_t>::char_type*, const char_type*, std::size_t)':
c:\mingw\lib\gcc\mingw32\4.9.3\include\c++\bits\char_traits.h:342:40: error: 'wmemmove' was not declared in this scope
       { return wmemmove(__s1, __s2, __n); }
                                        ^
c:\mingw\lib\gcc\mingw32\4.9.3\include\c++\bits\char_traits.h: In static member function 'static std::char_traits<wchar_t>::char_type* std::char_traits<wchar_t>::copy(std::char_traits<wchar_t>::char_type*, const char_type*, std::size_t)':
c:\mingw\lib\gcc\mingw32\4.9.3\include\c++\bits\char_traits.h:346:39: error: 'wmemcpy' was not declared in this scope
       { return wmemcpy(__s1, __s2, __n); }
                                       ^
c:\mingw\lib\gcc\mingw32\4.9.3\include\c++\bits\char_traits.h: In static member function 'static std::char_traits<wchar_t>::char_type* std::char_traits<wchar_t>::assign(std::char_traits<wchar_t>::char_type*, std::size_t, std::char_traits<wchar_t>::char_type)':
c:\mingw\lib\gcc\mingw32\4.9.3\include\c++\bits\char_traits.h:350:37: error: 'wmemset' was not declared in this scope
       { return wmemset(__s, __a, __n); }
                                     ^
In file included from c:\mingw\lib\gcc\mingw32\4.9.3\include\c++\ext\string_conversions.h:43:0,
                 from c:\mingw\lib\gcc\mingw32\4.9.3\include\c++\bits\basic_string.h:2849,
                 from c:\mingw\lib\gcc\mingw32\4.9.3\include\c++\string:52,
                 from c:\mingw\lib\gcc\mingw32\4.9.3\include\c++\random:40,
                 from c:\mingw\lib\gcc\mingw32\4.9.3\include\c++\bits\stl_algo.h:66,
                 from c:\mingw\lib\gcc\mingw32\4.9.3\include\c++\algorithm:62,
                 from tokumaru.cc:30:
c:\mingw\lib\gcc\mingw32\4.9.3\include\c++\cstdio: At global scope:
c:\mingw\lib\gcc\mingw32\4.9.3\include\c++\cstdio:175:11: error: '::snprintf' has not been declared
   using ::snprintf;
           ^
c:\mingw\lib\gcc\mingw32\4.9.3\include\c++\cstdio:176:11: error: '::vfscanf' has not been declared
   using ::vfscanf;
           ^
c:\mingw\lib\gcc\mingw32\4.9.3\include\c++\cstdio:177:11: error: '::vscanf' has not been declared
   using ::vscanf;
           ^
c:\mingw\lib\gcc\mingw32\4.9.3\include\c++\cstdio:178:11: error: '::vsnprintf' has not been declared
   using ::vsnprintf;
           ^
c:\mingw\lib\gcc\mingw32\4.9.3\include\c++\cstdio:179:11: error: '::vsscanf' has not been declared
   using ::vsscanf;
           ^
c:\mingw\lib\gcc\mingw32\4.9.3\include\c++\cstdio:185:22: error: '__gnu_cxx::snprintf' has not been declared
   using ::__gnu_cxx::snprintf;
                      ^
c:\mingw\lib\gcc\mingw32\4.9.3\include\c++\cstdio:186:22: error: '__gnu_cxx::vfscanf' has not been declared
   using ::__gnu_cxx::vfscanf;
                      ^
c:\mingw\lib\gcc\mingw32\4.9.3\include\c++\cstdio:187:22: error: '__gnu_cxx::vscanf' has not been declared
   using ::__gnu_cxx::vscanf;
                      ^
c:\mingw\lib\gcc\mingw32\4.9.3\include\c++\cstdio:188:22: error: '__gnu_cxx::vsnprintf' has not been declared
   using ::__gnu_cxx::vsnprintf;
                      ^
c:\mingw\lib\gcc\mingw32\4.9.3\include\c++\cstdio:189:22: error: '__gnu_cxx::vsscanf' has not been declared
   using ::__gnu_cxx::vsscanf;
                      ^
In file included from c:\mingw\lib\gcc\mingw32\4.9.3\include\c++\string:52:0,
                 from c:\mingw\lib\gcc\mingw32\4.9.3\include\c++\random:40,
                 from c:\mingw\lib\gcc\mingw32\4.9.3\include\c++\bits\stl_algo.h:66,
                 from c:\mingw\lib\gcc\mingw32\4.9.3\include\c++\algorithm:62,
                 from tokumaru.cc:30:
c:\mingw\lib\gcc\mingw32\4.9.3\include\c++\bits\basic_string.h: In function 'long long int std::stoll(const string&, std::size_t*, int)':
c:\mingw\lib\gcc\mingw32\4.9.3\include\c++\bits\basic_string.h:2873:31: error: 'strtoll' is not a member of 'std'
   { return __gnu_cxx::__stoa(&std::strtoll, "stoll", __str.c_str(),
                               ^
c:\mingw\lib\gcc\mingw32\4.9.3\include\c++\bits\basic_string.h: In function 'long long unsigned int std::stoull(const string&, std::size_t*, int)':
c:\mingw\lib\gcc\mingw32\4.9.3\include\c++\bits\basic_string.h:2878:31: error: 'strtoull' is not a member of 'std'
   { return __gnu_cxx::__stoa(&std::strtoull, "stoull", __str.c_str(),
                               ^
c:\mingw\lib\gcc\mingw32\4.9.3\include\c++\bits\basic_string.h: In function 'float std::stof(const string&, std::size_t*)':
c:\mingw\lib\gcc\mingw32\4.9.3\include\c++\bits\basic_string.h:2884:31: error: 'strtof' is not a member of 'std'
   { return __gnu_cxx::__stoa(&std::strtof, "stof", __str.c_str(), __idx); }
                               ^
c:\mingw\lib\gcc\mingw32\4.9.3\include\c++\bits\basic_string.h: In function 'long double std::stold(const string&, std::size_t*)':
c:\mingw\lib\gcc\mingw32\4.9.3\include\c++\bits\basic_string.h:2892:31: error: 'strtold' is not a member of 'std'
   { return __gnu_cxx::__stoa(&std::strtold, "stold", __str.c_str(), __idx); }
                               ^
c:\mingw\lib\gcc\mingw32\4.9.3\include\c++\bits\basic_string.h: In function 'std::string std::to_string(int)':
c:\mingw\lib\gcc\mingw32\4.9.3\include\c++\bits\basic_string.h:2899:45: error: 'vsnprintf' is not a member of 'std'
   { return __gnu_cxx::__to_xstring<string>(&std::vsnprintf, 4 * sizeof(int),
                                             ^
c:\mingw\lib\gcc\mingw32\4.9.3\include\c++\bits\basic_string.h: In function 'std::string std::to_string(unsigned int)':
c:\mingw\lib\gcc\mingw32\4.9.3\include\c++\bits\basic_string.h:2904:45: error: 'vsnprintf' is not a member of 'std'
   { return __gnu_cxx::__to_xstring<string>(&std::vsnprintf,
                                             ^
c:\mingw\lib\gcc\mingw32\4.9.3\include\c++\bits\basic_string.h: In function 'std::string std::to_string(long int)':
c:\mingw\lib\gcc\mingw32\4.9.3\include\c++\bits\basic_string.h:2910:45: error: 'vsnprintf' is not a member of 'std'
   { return __gnu_cxx::__to_xstring<string>(&std::vsnprintf, 4 * sizeof(long),
                                             ^
c:\mingw\lib\gcc\mingw32\4.9.3\include\c++\bits\basic_string.h: In function 'std::string std::to_string(long unsigned int)':
c:\mingw\lib\gcc\mingw32\4.9.3\include\c++\bits\basic_string.h:2915:45: error: 'vsnprintf' is not a member of 'std'
   { return __gnu_cxx::__to_xstring<string>(&std::vsnprintf,
                                             ^
c:\mingw\lib\gcc\mingw32\4.9.3\include\c++\bits\basic_string.h: In function 'std::string std::to_string(long long int)':
c:\mingw\lib\gcc\mingw32\4.9.3\include\c++\bits\basic_string.h:2921:45: error: 'vsnprintf' is not a member of 'std'
   { return __gnu_cxx::__to_xstring<string>(&std::vsnprintf,
                                             ^
c:\mingw\lib\gcc\mingw32\4.9.3\include\c++\bits\basic_string.h: In function 'std::string std::to_string(long long unsigned int)':
c:\mingw\lib\gcc\mingw32\4.9.3\include\c++\bits\basic_string.h:2927:45: error: 'vsnprintf' is not a member of 'std'
   { return __gnu_cxx::__to_xstring<string>(&std::vsnprintf,
                                             ^
c:\mingw\lib\gcc\mingw32\4.9.3\include\c++\bits\basic_string.h: In function 'std::string std::to_string(float)':
c:\mingw\lib\gcc\mingw32\4.9.3\include\c++\bits\basic_string.h:2936:45: error: 'vsnprintf' is not a member of 'std'
     return __gnu_cxx::__to_xstring<string>(&std::vsnprintf, __n,
                                             ^
c:\mingw\lib\gcc\mingw32\4.9.3\include\c++\bits\basic_string.h: In function 'std::string std::to_string(double)':
c:\mingw\lib\gcc\mingw32\4.9.3\include\c++\bits\basic_string.h:2945:45: error: 'vsnprintf' is not a member of 'std'
     return __gnu_cxx::__to_xstring<string>(&std::vsnprintf, __n,
                                             ^
c:\mingw\lib\gcc\mingw32\4.9.3\include\c++\bits\basic_string.h: In function 'std::string std::to_string(long double)':
c:\mingw\lib\gcc\mingw32\4.9.3\include\c++\bits\basic_string.h:2954:45: error: 'vsnprintf' is not a member of 'std'
     return __gnu_cxx::__to_xstring<string>(&std::vsnprintf, __n,
                                             ^
c:\mingw\lib\gcc\mingw32\4.9.3\include\c++\bits\basic_string.h: In function 'long long int std::stoll(const wstring&, std::size_t*, int)':
c:\mingw\lib\gcc\mingw32\4.9.3\include\c++\bits\basic_string.h:2976:31: error: 'wcstoll' is not a member of 'std'
   { return __gnu_cxx::__stoa(&std::wcstoll, "stoll", __str.c_str(),
                               ^
c:\mingw\lib\gcc\mingw32\4.9.3\include\c++\bits\basic_string.h: In function 'long long unsigned int std::stoull(const wstring&, std::size_t*, int)':
c:\mingw\lib\gcc\mingw32\4.9.3\include\c++\bits\basic_string.h:2981:31: error: 'wcstoull' is not a member of 'std'
   { return __gnu_cxx::__stoa(&std::wcstoull, "stoull", __str.c_str(),
                               ^
c:\mingw\lib\gcc\mingw32\4.9.3\include\c++\bits\basic_string.h: In function 'float std::stof(const wstring&, std::size_t*)':
c:\mingw\lib\gcc\mingw32\4.9.3\include\c++\bits\basic_string.h:2987:31: error: 'wcstof' is not a member of 'std'
   { return __gnu_cxx::__stoa(&std::wcstof, "stof", __str.c_str(), __idx); }
                               ^
c:\mingw\lib\gcc\mingw32\4.9.3\include\c++\bits\basic_string.h: In function 'long double std::stold(const wstring&, std::size_t*)':
c:\mingw\lib\gcc\mingw32\4.9.3\include\c++\bits\basic_string.h:2995:31: error: 'wcstold' is not a member of 'std'
   { return __gnu_cxx::__stoa(&std::wcstold, "stold", __str.c_str(), __idx); }
                               ^
tokumaru.cc: In function 'void CompressTilesWithBlockSplitting(const unsigned char*, unsigned int, F&&)':
tokumaru.cc:156:33: error: there are no arguments to 'omp_get_thread_num' that depend on a template parameter, so a declaration of 'omp_get_thread_num' must be available [-fpermissive]
         tn = omp_get_thread_num(); nt = omp_get_num_threads();
                                 ^
tokumaru.cc:156:33: note: (if you use '-fpermissive', G++ will accept your code, but allowing the use of an undeclared name is deprecated)
tokumaru.cc:156:61: error: there are no arguments to 'omp_get_num_threads' that depend on a template parameter, so a declaration of 'omp_get_num_threads' must be available [-fpermissive]
         tn = omp_get_thread_num(); nt = omp_get_num_threads();
                                                             ^
tokumaru.cc: In instantiation of 'void CompressTilesWithBlockSplitting(const unsigned char*, unsigned int, F&&) [with F = CompressTiles(const unsigned char*, unsigned int, F&&) [with F = main(int, char**)::<lambda(unsigned char)>]::<lambda(unsigned int, unsigned int)>&]':
tokumaru.cc:236:65:   required from 'void CompressTiles(const unsigned char*, unsigned int, F&&) [with F = main(int, char**)::<lambda(unsigned char)>]'
tokumaru.cc:419:96:   required from here
tokumaru.cc:156:33: error: 'omp_get_thread_num' was not declared in this scope
         tn = omp_get_thread_num(); nt = omp_get_num_threads();
                                 ^
tokumaru.cc:156:61: error: 'omp_get_num_threads' was not declared in this scope
         tn = omp_get_thread_num(); nt = omp_get_num_threads();
                                                             ^
tokumaru.cc:182:16: error: no matching function for call to 'CompressTilesWithBlockSplitting(const unsigned char*, unsigned int, F&&) [with F = CompressTiles(const unsigned char*, unsigned int, F&&) [with F = main(int, char**)::<lambda(unsigned char)>]::<lambda(unsigned int, unsigned int)>&]::Record::Record(<brace-enclosed initializer list>)'
     targets[0] = Record{0, ~0u, false};
                ^
tokumaru.cc:182:16: note: candidates are:
tokumaru.cc:175:12: note: constexpr CompressTilesWithBlockSplitting(const unsigned char*, unsigned int, F&&) [with F = CompressTiles(const unsigned char*, unsigned int, F&&) [with F = main(int, char**)::<lambda(unsigned char)>]::<lambda(unsigned int, unsigned int)>&]::Record::Record()
     struct Record { unsigned distance=~0u, previous=~0u; bool visited=false; };
            ^
tokumaru.cc:175:12: note:   candidate expects 0 arguments, 3 provided
tokumaru.cc:175:12: note: constexpr CompressTilesWithBlockSplitting(const unsigned char*, unsigned int, F&&) [with F = CompressTiles(const unsigned char*, unsigned int, F&&) [with F = main(int, char**)::<lambda(unsigned char)>]::<lambda(unsigned int, unsigned int)>&]::Record::Record(const CompressTilesWithBlockSplitting(const unsigned char*, unsigned int, F&&) [with F = CompressTiles(const unsigned char*, unsigned int, F&&) [with F = main(int, char**)::<lambda(unsigned char)>]::<lambda(unsigned int, unsigned int)>&]::Record&)
tokumaru.cc:175:12: note:   candidate expects 1 argument, 3 provided
tokumaru.cc:175:12: note: constexpr CompressTilesWithBlockSplitting(const unsigned char*, unsigned int, F&&) [with F = CompressTiles(const unsigned char*, unsigned int, F&&) [with F = main(int, char**)::<lambda(unsigned char)>]::<lambda(unsigned int, unsigned int)>&]::Record::Record(CompressTilesWithBlockSplitting(const unsigned char*, unsigned int, F&&) [with F = CompressTiles(const unsigned char*, unsigned int, F&&) [with F = main(int, char**)::<lambda(unsigned char)>]::<lambda(unsigned int, unsigned int)>&]::Record&&)
tokumaru.cc:175:12: note:   candidate expects 1 argument, 3 provided
tokumaru.cc: At global scope:
tokumaru.cc:69:13: error: 'void CompressWholeBlock(const unsigned char*, unsigned int, F&&, const unsigned char*) [with F = CompressTilesWithBlockSplitting(const unsigned char*, unsigned int, F&&) [with F = CompressTiles(const unsigned char*, unsigned int, F&&) [with F = main(int, char**)::<lambda(unsigned char)>]::<lambda(unsigned int, unsigned int)>&]::<lambda(unsigned int, unsigned int)>]', declared using local type 'CompressTilesWithBlockSplitting(const unsigned char*, unsigned int, F&&) [with F = CompressTiles(const unsigned char*, unsigned int, F&&) [with F = main(int, char**)::<lambda(unsigned char)>]::<lambda(unsigned int, unsigned int)>&]::<lambda(unsigned int, unsigned int)>', is used but never defined [-fpermissive]
 static void CompressWholeBlock(const unsigned char* tiles, unsigned numtiles, F&& PutBits,
             ^
In file included from c:\mingw\lib\gcc\mingw32\4.9.3\include\c++\queue:64:0,
                 from tokumaru.cc:34:
c:\mingw\lib\gcc\mingw32\4.9.3\include\c++\bits\stl_queue.h:411:7: error: 'std::priority_queue<_Tp, _Sequence, _Compare>::priority_queue(const _Compare&, _Sequence&&) [with _Tp = std::pair<unsigned int, unsigned int>; _Sequence = std::vector<std::pair<unsigned int, unsigned int> >; _Compare = CompressTilesWithBlockSplitting(const unsigned char*, unsigned int, F&&) [with F = CompressTiles(const unsigned char*, unsigned int, F&&) [with F = main(int, char**)::<lambda(unsigned char)>]::<lambda(unsigned int, unsigned int)>&]::Prioritize]', declared using local type 'const CompressTilesWithBlockSplitting(const unsigned char*, unsigned int, F&&) [with F = CompressTiles(const unsigned char*, unsigned int, F&&) [with F = main(int, char**)::<lambda(unsigned char)>]::<lambda(unsigned int, unsigned int)>&]::Prioritize', is used but never defined [-fpermissive]
       priority_queue(const _Compare& __x = _Compare(),
       ^
In file included from c:\mingw\lib\gcc\mingw32\4.9.3\include\c++\vector:64:0,
                 from c:\mingw\lib\gcc\mingw32\4.9.3\include\c++\bits\random.h:34,
                 from c:\mingw\lib\gcc\mingw32\4.9.3\include\c++\random:49,
                 from c:\mingw\lib\gcc\mingw32\4.9.3\include\c++\bits\stl_algo.h:66,
                 from c:\mingw\lib\gcc\mingw32\4.9.3\include\c++\algorithm:62,
                 from tokumaru.cc:30:
c:\mingw\lib\gcc\mingw32\4.9.3\include\c++\bits\stl_vector.h:779:7: error: 'std::vector<_Tp, _Alloc>::reference std::vector<_Tp, _Alloc>::operator[](std::vector<_Tp, _Alloc>::size_type) [with _Tp = CompressTilesWithBlockSplitting(const unsigned char*, unsigned int, F&&) [with F = CompressTiles(const unsigned char*, unsigned int, F&&) [with F = main(int, char**)::<lambda(unsigned char)>]::<lambda(unsigned int, unsigned int)>&]::Record; _Alloc = std::allocator<CompressTilesWithBlockSplitting(const unsigned char*, unsigned int, F&&) [with F = CompressTiles(const unsigned char*, unsigned int, F&&) [with F = main(int, char**)::<lambda(unsigned char)>]::<lambda(unsigned int, unsigned int)>&]::Record>; std::vector<_Tp, _Alloc>::reference = CompressTilesWithBlockSplitting(const unsigned char*, unsigned int, F&&) [with F = CompressTiles(const unsigned char*, unsigned int, F&&) [with F = main(int, char**)::<lambda(unsigned char)>]::<lambda(unsigned int, unsigned int)>&]::Record&; std::vector<_Tp, _Alloc>::size_type = unsigned int]', declared using local type '__gnu_cxx::__alloc_traits<std::allocator<CompressTilesWithBlockSplitting(const unsigned char*, unsigned int, F&&) [with F = CompressTiles(const unsigned char*, unsigned int, F&&) [with F = main(int, char**)::<lambda(unsigned char)>]::<lambda(unsigned int, unsigned int)>&]::Record> >::value_type {aka CompressTilesWithBlockSplitting(const unsigned char*, unsigned int, F&&) [with F = CompressTiles(const unsigned char*, unsigned int, F&&) [with F = main(int, char**)::<lambda(unsigned char)>]::<lambda(unsigned int, unsigned int)>&]::Record}', is used but never defined [-fpermissive]
       operator[](size_type __n) _GLIBCXX_NOEXCEPT
       ^
make: *** [tokumaru] Error 1



Incidentally, the error log is 2 times longer than the code to be cmpiled. :(
Re: Tile encoder/decoder
by on (#177849)
Looks like something is seriously wrong with your compiler setup. It shouldn't barf on #include <algorithm> whether the source needs C++14 or not.