Embedded palettes can be mis-sorted if some palettes share colors

[Rangi42]

Here's an example test.png:

Its eight-color indexed PLTE defines two GBC palettes:

% pngcheck -p test.png
File: test.png (159 bytes)
  PLTE chunk: 8 palette entries
    0:  (255,255,255) = (0xff,0xff,0xff)
    1:  (255,222,  0) = (0xff,0xde,0x00)
    2:  (  0, 33,255) = (0x00,0x21,0xff)
    3:  (  0,  0,  0) = (0x00,0x00,0x00)
    4:  (255,255,255) = (0xff,0xff,0xff)
    5:  (255,222,  0) = (0xff,0xde,0x00)
    6:  (181,  0,255) = (0xb5,0x00,0xff)
    7:  (  0,  0,  0) = (0x00,0x00,0x00)
OK: test.png (16x8, 8-bit palette, non-interlaced, -24.2%).

These should stay sorted as-is when converting. However, the second palette's last two colors, black and purple, are swapped:

% rgbgfx -o test.2bpp -p test.pal -q test.palmap test.png
% xxd test.pal                                           
00000000: ff7f 7f03 807c 0000 ff7f 7f03 0000 167c  .....|.........|

The problem is that each 4-color GBC palette is sorted by finding its colors in the PNG's whole indexed palette. So if an earlier GBC palette shares some of the colors, those colors will get sorted before others in this palette, even if this palette has those colors later.

What we want:

% xxd test.pal                                             
00000000: ff7f 7f03 807c 0000 ff7f 7f03 167c 0000  .....|.......|..

[aaaaaa123456789]

It sounds to me like this is a resut of "embedded" meaning two different things: (1) form palettes out of the colors in this file, preserving their order (in which case having duplicates makes no sense, as you'd want to mix and match anyway) and (2) take these colors into groups of four and use those as palettes directly.

I think one of them should be renamed, because both are valid, and you're bound to find edge cases that are handled incorrectly if you try to handle both under the same umbrella.

[Rangi42]

I'm not aware of anyone ever needing, expecting, or trying to use meaning (1) there.

The pret projects, and probably a good number of others, only use four colors anyway, so this issue doesn't come up.

When people are using more than 4 colors in a PLTE, either they care about the order of colors within each GBC palette or not. If they don't care, then the PR for this issue won't break anything for them -- note how it still searches the whole PLTE color set, just starting at the current GBC palette offset.

Note this warning in rgbgfx(1):

If the order of colors in the palettes is important to you, for example because you want to use palette swaps, please use -c to specify the palette explicitly.

People using -p without -c don't expect any particular ordering, so if #1703 changes the ordering then it's okay.

[Rangi42]

...okay, so I completely hallucinated rgbgfx's support for multi-GBC-pal indexed palettes:

If pal_spec is the case-insensitive word embedded, then the first four colors of the input PNG's embedded palette are used. It is an error if the PNG is not indexed, or if colors other than these 4 are used.

So this isn't really an issue, and #1703 should only be reverse-outputting indexed PLTEs when there are four colors.

Maybe rgbgfx 2.0 will implement #1067 and this will become a concern, but not until then.