Add pallete in header

[Niphiil]

Add pallete in header. It should enlarge minimal file by 244 bytes( shrinking original header to 12 bytes make full header a nice 256 bytes).
The best compression results can be obtained if you use a palette obtained not from the first 61 colors, whose hash was not in the palette, but from the most frequent uncompressed colors (which could not be encoded by increments or lengths of the sequence). This can be done by a two-pass algorithm, where in the first pass the algorithm does not use QOI_OP_INDEX, but counts every QOI_OP_RGBA and QOI_OP_RGB that it produces. After the first pass, we have a histogram of uncompressed colors, 61 of the most common colors form a table. In the second pass, we write the file from the results of the first pass, but replace the unpacked colors with their corresponding QOI_OP_INDEX values.
This will probably slow down the encoder few times, but it will still be a lot faster than PNG. But it may allow increasing the compression ratio and speed up decoder. Perhaps this is a reasonable compromise, since decoding and storage are more frequent situations in the image lifecycle.
That modification can work with old onepass algorithm and also speed up decoding.

P.S. Additional modification can be made for the two-pass coding algorithm (I'm not sure that it will improve compression much, need testing). If we make QOI_OP_INDEX not put a pixel into the output directly, but only change the state, then you need any other entry to insert a new pixel into the output stream. This, followed by QOI_OP_DIFF or QOI_OP_LUMA, can virtually enlarge the color table, and this can be used when creating the table. On some images this may improve compression. But it will probably work worse for images with few colors. It should also slow things down, but not too much for large images compared to the basic two-pass algorithm.

[nigeltao]

This will probably slow down the encoder few times, but it will still be a lot faster than PNG. But it may allow increasing the compression ratio and speed up decoder.

If you're essentially replacing QOI_OP_INDEX (i.e. an LRU-ish dynamic cache) with QOI_OP_PALETTE (i.e. a static cache), you might also make compression worse because some of the previous QOI_OP_INDEX ops (1 byte) might now need to be a different op (more bytes).

It might still be a net win, but like the "combined INDEX + LUMA/DIFF op" ideas, I'd want to see actual numbers. If it's a 1.05x slow-down but a 2x improvement in compression size, then that's great. If it's a 10x slow-down and a 1.01x improvement in compression size, that's not so great.

Another thing is that, currently, the encoder only needs O(1) memory, other than the source pixels. Computing a histogram of uncompressed colors could take an extra O(N) memory, where N is the number of pixels. That's possibly acceptable (if the compression improvements are large enough), but I'd want that to be a concious trade-off.