RGBGFX produces different sized palettes with -Z flag

[ElectroDeoxys]

We found a situation where RGBGFX generates more palettes than needed if -Z is used. Here's the image:

Running rgbgfx like so will produce a .pal file with 3 palettes, as expected:
rgbgfx -P gloom.png

However, running with -Z, then 4 palettes are generated instead:
rgbgfx -P -Z gloom.png

Moreover, by changing a pixel in one of the 8x8 squares (so that the square has 4 colours instead of 3), pictured here:

Then running the same command will generate the expected 3 palettes:
rgbgfx -P -Z gloom_fixed.png

The version used here is rgbgfx v1.0.0-9-gd961c697.

(Sprite was done by Cataclyptic)

[Rangi42]

Interesting bug! Thank you for the detailed report. I can reproduce this with the latest rgbgfx 1.0.1:

$ rgbgfx -vvvv -p gloom.pal gloom.png
rgbgfx v1.0.1
Options:
        Bit depth: 2bpp
        Maximum 8 palettes
        Palettes contain 4 colors
        Automatic palette generation
        Maximum 65535 tiles in bank 0, and 0 in bank 1
        Input image: gloom.png
        Output palettes: gloom.pal
Ready for conversion
Using libpng 1.6.43
Reading tiles...
Reading PNG file "gloom.png"
PNG header signature is OK
PNG image: 64x48 pixels, 8bpp RGB, not interlaced
No embedded PNG palette
Image colors: [ #3b1d14ff, #74841aff, #c25723ff, #ff9a40ff, #475576ff, #875991ff, #d9c6a3ff, #8ea4c7ff, ]
Image contains 3 color sets
[ $0867, $1158, $227f, $3948, ]
[ $0867, $0e0e, $227f, $531b, ]
[ $0867, $3948, $4970, $6291, ]
Paginating palettes using "overload-and-remove" strategy...
Assigning overflowing color set 0 to palette 0
Adding new palette (2) for overflowing color set 1
{ [0] 0867, 1158, 227f, 3948, } (volume = 4)
{ [2] 0867, 3948, 4970, 6291, } (volume = 4)
{ [1] 0867, 0e0e, 227f, 531b, } (volume = 4)
3 palettes before decanting
3 palettes after decanting on palettes
3 palettes after decanting on "components"
3 palettes after decanting on color sets
{ [0] 0867, 1158, 227f, 3948, } (volume = 4)
{ [2] 0867, 3948, 4970, 6291, } (volume = 4)
{ [1] 0867, 0e0e, 227f, 531b, } (volume = 4)
Color set mappings: (3 palettes)
0 -> 0
1 -> 2
2 -> 1
Too many colors for grayscale sorting (8 > 4)
Sorting palettes by luminance...
{ 227f, 1158, 3948, 0867, }
{ 6291, 4970, 3948, 0867, }
{ 531b, 227f, 0e0e, 0867, }

$ rgbgfx -vvvv -p gloom_Z.pal -Z gloom.png
rgbgfx v1.0.1
Options:
        Visit image in column-major order
        Bit depth: 2bpp
        Maximum 8 palettes
        Palettes contain 4 colors
        Automatic palette generation
        Maximum 65535 tiles in bank 0, and 0 in bank 1
        Input image: gloom.png
        Output palettes: gloom_Z.pal
Ready for conversion
Using libpng 1.6.43
Reading tiles...
Reading PNG file "gloom.png"
PNG header signature is OK
PNG image: 64x48 pixels, 8bpp RGB, not interlaced
No embedded PNG palette
Image colors: [ #3b1d14ff, #74841aff, #c25723ff, #ff9a40ff, #475576ff, #875991ff, #d9c6a3ff, #8ea4c7ff, ]
Image contains 5 color sets
[ $0867, $1158, $227f, $3948, ]
[ $0867, $0e0e, $227f, $531b, ]
[ $0867, $227f, $3948, ]
[ $0867, $3948, $4970, $6291, ]
[ $0867, $227f, $531b, ]
Paginating palettes using "overload-and-remove" strategy...
Assigning overflowing color set 1 to palette 1
Adding new palette (3) for overflowing color set 0
{ [4] 0867, 227f, 531b, [2] 0867, 227f, 3948, } (volume = 4)
{ [1] 0867, 0e0e, 227f, 531b, } (volume = 4)
{ [3] 0867, 3948, 4970, 6291, } (volume = 4)
{ [0] 0867, 1158, 227f, 3948, } (volume = 4)
4 palettes before decanting
4 palettes after decanting on palettes
4 palettes after decanting on "components"
4 palettes after decanting on color sets
{ [4] 0867, 227f, 531b, [2] 0867, 227f, 3948, } (volume = 4)
{ [1] 0867, 0e0e, 227f, 531b, } (volume = 4)
{ [3] 0867, 3948, 4970, 6291, } (volume = 4)
{ [0] 0867, 1158, 227f, 3948, } (volume = 4)
Color set mappings: (4 palettes)
0 -> 3
1 -> 1
2 -> 0
3 -> 2
4 -> 0
Too many colors for grayscale sorting (8 > 4)
Sorting palettes by luminance...
{ 531b, 227f, 3948, 0867, }
{ 531b, 227f, 0e0e, 0867, }
{ 6291, 4970, 3948, 0867, }
{ 227f, 1158, 3948, 0867, }

[Rangi42]

Also can confirm that changing the pixel at (32, 5) from brown #3B1D14 to green #74841A makes the discrepancy go away:

$ rgbgfx -vvvv -p gloom_fixed.pal gloom_fixed.png
rgbgfx v1.0.1
Options:
        Bit depth: 2bpp
        Maximum 8 palettes
        Palettes contain 4 colors
        Automatic palette generation
        Maximum 65535 tiles in bank 0, and 0 in bank 1
        Input image: gloom_fixed.png
        Output palettes: gloom_fixed.pal
Ready for conversion
Using libpng 1.6.43
Reading tiles...
Reading PNG file "gloom_fixed.png"
PNG header signature is OK
PNG image: 64x48 pixels, 8bpp RGB, not interlaced
No embedded PNG palette
Image colors: [ #3b1d14ff, #74841aff, #c25723ff, #ff9a40ff, #475576ff, #875991ff, #d9c6a3ff, #8ea4c7ff, ]
Image contains 3 color sets
[ $0867, $1158, $227f, $3948, ]
[ $0867, $0e0e, $227f, $531b, ]
[ $0867, $3948, $4970, $6291, ]
Paginating palettes using "overload-and-remove" strategy...
Assigning overflowing color set 0 to palette 0
Adding new palette (2) for overflowing color set 1
{ [0] 0867, 1158, 227f, 3948, } (volume = 4)
{ [2] 0867, 3948, 4970, 6291, } (volume = 4)
{ [1] 0867, 0e0e, 227f, 531b, } (volume = 4)
3 palettes before decanting
3 palettes after decanting on palettes
3 palettes after decanting on "components"
3 palettes after decanting on color sets
{ [0] 0867, 1158, 227f, 3948, } (volume = 4)
{ [2] 0867, 3948, 4970, 6291, } (volume = 4)
{ [1] 0867, 0e0e, 227f, 531b, } (volume = 4)
Color set mappings: (3 palettes)
0 -> 0
1 -> 2
2 -> 1
Too many colors for grayscale sorting (8 > 4)
Sorting palettes by luminance...
{ 227f, 1158, 3948, 0867, }
{ 6291, 4970, 3948, 0867, }
{ 531b, 227f, 0e0e, 0867, }

$ rgbgfx -vvvv -p gloom_fixed_Z.pal -Z gloom_fixed.png
rgbgfx v1.0.1
Options:
        Visit image in column-major order
        Bit depth: 2bpp
        Maximum 8 palettes
        Palettes contain 4 colors
        Automatic palette generation
        Maximum 65535 tiles in bank 0, and 0 in bank 1
        Input image: gloom_fixed.png
        Output palettes: gloom_fixed_Z.pal
Ready for conversion
Using libpng 1.6.43
Reading tiles...
Reading PNG file "gloom_fixed.png"
PNG header signature is OK
PNG image: 64x48 pixels, 8bpp RGB, not interlaced
No embedded PNG palette
Image colors: [ #3b1d14ff, #74841aff, #c25723ff, #ff9a40ff, #475576ff, #875991ff, #d9c6a3ff, #8ea4c7ff, ]
Image contains 4 color sets
[ $0867, $1158, $227f, $3948, ]
[ $0867, $0e0e, $227f, $531b, ]
[ $0867, $227f, $3948, ]
[ $0867, $3948, $4970, $6291, ]
Paginating palettes using "overload-and-remove" strategy...
Assigning overflowing color set 1 to palette 1
Adding new palette (2) for overflowing color set 3
{ [2] 0867, 227f, 3948, [0] 0867, 1158, 227f, 3948, } (volume = 4)
{ [1] 0867, 0e0e, 227f, 531b, } (volume = 4)
{ [3] 0867, 3948, 4970, 6291, } (volume = 4)
3 palettes before decanting
3 palettes after decanting on palettes
3 palettes after decanting on "components"
3 palettes after decanting on color sets
{ [2] 0867, 227f, 3948, [0] 0867, 1158, 227f, 3948, } (volume = 4)
{ [1] 0867, 0e0e, 227f, 531b, } (volume = 4)
{ [3] 0867, 3948, 4970, 6291, } (volume = 4)
Color set mappings: (3 palettes)
0 -> 0
1 -> 1
2 -> 0
3 -> 2
Too many colors for grayscale sorting (8 > 4)
Sorting palettes by luminance...
{ 227f, 1158, 3948, 0867, }
{ 531b, 227f, 0e0e, 0867, }
{ 6291, 4970, 3948, 0867, }

(The palettes still end up in a different order, but that makes more sense since palette order is just an artifact of the order in which color sets were encountered+processed, we don't do any sorting for them.)

[Rangi42]

Note that explicitly specifying the same palette with -c gbc:gloom.pal works whether or not -Z is passed.

[Rangi42]

With some extra debugging output (which ought to be part of higher verbosity levels anyway):

$ ./rgbgfx -P gloom.png
- tile (0, 0) adds color set #0: [$0867, $1158, ]
- tile (16, 0) overrides color set #0: [$0867, $1158, ] becomes [$0867, $1158, $227f, ]
- tile (32, 0) adds color set #1: [$0867, $227f, $531b, ]
- tile (48, 16) overrides color set #1: [$0867, $227f, $531b, ] becomes [$0867, $0e0e, $227f, $531b, ]
- tile (16, 24) adds color set #2: [$0867, $3948, $6291, ]
- tile (40, 24) overrides color set #0: [$0867, $1158, $227f, ] becomes [$0867, $1158, $227f, $3948, ]
- tile (24, 32) overrides color set #2: [$0867, $3948, $6291, ] becomes [$0867, $3948, $4970, $6291, ]
$ ./rgbgfx -P -Z gloom.png
- tile (0, 0) adds color set #0: [$0867, $1158, ]
- tile (0, 16) overrides color set #0: [$0867, $1158, ] becomes [$0867, $1158, $227f, ]
- tile (0, 32) adds color set #1: [$0867, $0e0e, $227f, ]
- tile (8, 32) adds color set #2: [$0867, $227f, $3948, ]
- tile (16, 24) adds color set #3: [$0867, $3948, $6291, ]
- tile (24, 32) overrides color set #3: [$0867, $3948, $6291, ] becomes [$0867, $3948, $4970, $6291, ]
- tile (32, 0) adds color set #4: [$0867, $227f, $531b, ]
- tile (32, 40) overrides color set #1: [$0867, $0e0e, $227f, ] becomes [$0867, $0e0e, $227f, $531b, ]
- tile (40, 24) overrides color set #0: [$0867, $1158, $227f, ] becomes [$0867, $1158, $227f, $3948, ]

• Tile (0, 0) has {brown + orange}, and adds a new color set #0.
• Tile (8, 0) has the same colors as tile (0, 0).
• Tile (16, 0) has {brown + orange + yellow}, which is a superset of color set #0, so it overrides that color set.
• Tile (32, 0) has {brown + yellow + white}, and adds a new color set rgbasm flakiness on OpenBSD #1.
  • This is interesting. It could have merged with color set #0 to form {brown + orange + yellow + white}. But maybe "overriding" has to be a strict superset, not just partial overlap. We'll see.
• ...more tiles are using subsets of the two existing color sets...
• Tile (48, 16) has {brown + green + white}. It overrides color set rgbasm flakiness on OpenBSD #1, which becomes {brown + green + yellow + white}.
  • This is also interesting. For consistency with tile (32, 0), it should have added a new color set rgblib delete is broken on OpenBSD #2. Or if this is the correct behavior, tile (32, 0) should not have added its own color set.

The discrepancy in behavior apparently involves the ColorSet::compare method.

[Rangi42]

The rsgbgfx Rust port increases my confidence that the issue here is ColorSet::compare misbehaving. {brown + green + white} is not a superset of {brown + yellow + white}, so it should not be overriding that color set -- that's "merging", not overriding, and that's supposed to come later in the algorithm.

[Rangi42]

So far https://github.com/Rangi42/rgbds/tree/color-sets reimplements ColorSet::compare correctly, which does make tile (48, 16) add its own color set #2 instead of incorrectly overriding #1. However, the generated palettes are still different when -Z is specified, so something else is wrong too.

$ ./rgbgfx -vvvv -p gloom.pal gloom.png
rgbgfx v1.0.1-4-gd0530250-dirty
Options:
        Bit depth: 2bpp
        Maximum 8 palettes
        Palettes contain 4 colors
        Automatic palette generation
        Maximum 65535 tiles in bank 0, and 0 in bank 1
        Input image: gloom.png
        Output palettes: gloom.pal
Ready for conversion
Using libpng 1.6.43
Reading tiles...
Reading PNG file "gloom.png"
PNG header signature is OK
PNG image: 64x48 pixels, 8bpp RGB, not interlaced
No embedded PNG palette
Image colors: [ #3b1d14ff, #74841aff, #c25723ff, #ff9a40ff, #475576ff, #875991ff, #d9c6a3ff, #8ea4c7ff, ]
- tile (0, 0) adds color set #0: [$0867, $1158, ]
- tile (16, 0) overrides color set #0: [$0867, $1158, ] becomes [$0867, $1158, $227f, ]
- tile (32, 0) adds color set #1: [$0867, $227f, $531b, ]
- tile (48, 16) adds color set #2: [$0867, $0e0e, $227f, $531b, ]
- tile (16, 24) adds color set #3: [$0867, $3948, $6291, ]
- tile (40, 24) overrides color set #0: [$0867, $1158, $227f, ] becomes [$0867, $1158, $227f, $3948, ]
- tile (24, 32) adds color set #4: [$0867, $3948, $4970, $6291, ]
Image contains 5 color sets
[ $0867, $1158, $227f, $3948, ]
[ $0867, $227f, $531b, ]
[ $0867, $0e0e, $227f, $531b, ]
[ $0867, $3948, $6291, ]
[ $0867, $3948, $4970, $6291, ]
Paginating palettes using "overload-and-remove" strategy...
Assigning overflowing color set 0 to palette 0
Assigning overflowing color set 2 to palette 1
Assigning overflowing color set 1 to palette 1
Assigning overflowing color set 3 to palette 2
{ [0] 0867, 1158, 227f, 3948, } (volume = 4)
{ [2] 0867, 0e0e, 227f, 531b, [1] 0867, 227f, 531b, } (volume = 4)
{ [4] 0867, 3948, 4970, 6291, [3] 0867, 3948, 6291, } (volume = 4)
3 palettes before decanting
3 palettes after decanting on palettes
3 palettes after decanting on "components"
3 palettes after decanting on color sets
{ [0] 0867, 1158, 227f, 3948, } (volume = 4)
{ [2] 0867, 0e0e, 227f, 531b, [1] 0867, 227f, 531b, } (volume = 4)
{ [4] 0867, 3948, 4970, 6291, [3] 0867, 3948, 6291, } (volume = 4)
Color set mappings: (3 palettes)
0 -> 0
1 -> 1
2 -> 1
3 -> 2
4 -> 2
Too many colors for grayscale sorting (8 > 4)
Sorting palettes by luminance...
{ 227f, 1158, 3948, 0867, }
{ 531b, 227f, 0e0e, 0867, }
{ 6291, 4970, 3948, 0867, }

$ ./rgbgfx -vvvv -p gloom_Z.pal -Z gloom.png
rgbgfx v1.0.1-4-gd0530250-dirty
Options:
        Visit image in column-major order
        Bit depth: 2bpp
        Maximum 8 palettes
        Palettes contain 4 colors
        Automatic palette generation
        Maximum 65535 tiles in bank 0, and 0 in bank 1
        Input image: gloom.png
        Output palettes: gloom_Z.pal
Ready for conversion
Using libpng 1.6.43
Reading tiles...
Reading PNG file "gloom.png"
PNG header signature is OK
PNG image: 64x48 pixels, 8bpp RGB, not interlaced
No embedded PNG palette
Image colors: [ #3b1d14ff, #74841aff, #c25723ff, #ff9a40ff, #475576ff, #875991ff, #d9c6a3ff, #8ea4c7ff, ]
- tile (0, 0) adds color set #0: [$0867, $1158, ]
- tile (0, 16) overrides color set #0: [$0867, $1158, ] becomes [$0867, $1158, $227f, ]
- tile (0, 32) adds color set #1: [$0867, $0e0e, $227f, ]
- tile (8, 32) adds color set #2: [$0867, $227f, $3948, ]
- tile (16, 24) adds color set #3: [$0867, $3948, $6291, ]
- tile (24, 32) adds color set #4: [$0867, $3948, $4970, $6291, ]
- tile (32, 0) adds color set #5: [$0867, $227f, $531b, ]
- tile (32, 40) overrides color set #1: [$0867, $0e0e, $227f, ] becomes [$0867, $0e0e, $227f, $531b, ]
- tile (40, 24) overrides color set #0: [$0867, $1158, $227f, ] becomes [$0867, $1158, $227f, $3948, ]
Image contains 6 color sets
[ $0867, $1158, $227f, $3948, ]
[ $0867, $0e0e, $227f, $531b, ]
[ $0867, $227f, $3948, ]
[ $0867, $3948, $6291, ]
[ $0867, $3948, $4970, $6291, ]
[ $0867, $227f, $531b, ]
Paginating palettes using "overload-and-remove" strategy...
Assigning overflowing color set 1 to palette 2
Adding new palette (3) for overflowing color set 0
{ [5] 0867, 227f, 531b, [2] 0867, 227f, 3948, } (volume = 4)
{ [4] 0867, 3948, 4970, 6291, [3] 0867, 3948, 6291, } (volume = 4)
{ [1] 0867, 0e0e, 227f, 531b, } (volume = 4)
{ [0] 0867, 1158, 227f, 3948, } (volume = 4)
4 palettes before decanting
4 palettes after decanting on palettes
4 palettes after decanting on "components"
4 palettes after decanting on color sets
{ [5] 0867, 227f, 531b, [2] 0867, 227f, 3948, } (volume = 4)
{ [4] 0867, 3948, 4970, 6291, [3] 0867, 3948, 6291, } (volume = 4)
{ [1] 0867, 0e0e, 227f, 531b, } (volume = 4)
{ [0] 0867, 1158, 227f, 3948, } (volume = 4)
Color set mappings: (4 palettes)
0 -> 3
1 -> 2
2 -> 0
3 -> 1
4 -> 1
5 -> 0
Too many colors for grayscale sorting (8 > 4)
Sorting palettes by luminance...
{ 531b, 227f, 3948, 0867, }
{ 6291, 4970, 3948, 0867, }
{ 531b, 227f, 0e0e, 0867, }
{ 227f, 1158, 3948, 0867, }

[Rangi42]

rsgbgfx at least does not have this problem, so I can keep looking into it to figure out the total cause here.

[ISSOtm]

Since colour set subsetting is performed as a greedy operation, I'm not surprised it's order-sensitive. Possibly rsgbgfx has different orders of operations, and that happens to work out here but would break on other images?

[Rangi42]

I am surprised it's order-sensitive, because "is a subset" defines an equivalence class of color sets, so iterating over them in any order should build the same collection of non-equivalent color sets. (Maybe the order of that collection matters? Should it?)

[ISSOtm]

Oh, right, it shouldn't change which colour sets we end up with, only which ones they are “subsetted into” ([{A}, {A, B}, {A, C}], 1 could end up in 2 or 3). The plot thickens.

[Rangi42]

With similar println! debug statements added to rsgbgfx:

$ ../rsgbds/target/debug/rgbgfx -p gloom.pal gloom.png
- tile (0, 0) adds color set #0: [$0867, $1158]
- tile (16, 0) overrides color set #0: [$0867, $1158] becomes [$0867, $1158, $227f]
- tile (32, 0) adds color set #1: [$0867, $227f, $531b]
- tile (48, 16) overrides color set #1: [$0867, $227f, $531b] becomes [$0867, $0e0e, $227f, $531b]
- tile (16, 24) adds color set #2: [$0867, $3948, $6291]
- tile (40, 24) overrides color set #0: [$0867, $1158, $227f] becomes [$0867, $1158, $227f, $3948]
- tile (24, 32) overrides color set #2: [$0867, $3948, $6291] becomes [$0867, $3948, $4970, $6291]
$ ../rsgbds/target/debug/rgbgfx -p gloom_Z.pal -Z gloom.png
- tile (0, 0) adds color set #0: [$0867, $1158]
- tile (0, 16) overrides color set #0: [$0867, $1158] becomes [$0867, $1158, $227f]
- tile (0, 32) adds color set #1: [$0867, $0e0e, $227f]
- tile (8, 32) adds color set #2: [$0867, $227f, $3948]
- tile (16, 24) adds color set #3: [$0867, $3948, $6291]
- tile (24, 32) overrides color set #3: [$0867, $3948, $6291] becomes [$0867, $3948, $4970, $6291]
- tile (32, 0) adds color set #4: [$0867, $227f, $531b]
- tile (32, 40) overrides color set #1: [$0867, $0e0e, $227f] becomes [$0867, $0e0e, $227f, $531b]
- tile (40, 24) overrides color set #0: [$0867, $1158, $227f] becomes [$0867, $1158, $227f, $3948]

Which highlights the problem: I didn't actually get the compare logic right yet. Tile (48, 16) uses all three colors from tile (32, 0) plus a fourth, so it should override that color set, not add its own.

[Rangi42]

I fixed compare for real this time, and now the color sets are built exactly the same as Rust does. But the problem persists, so yes, it has something to do with the color set merging logic, after the color sets have been generated. (I think that implementing "Remove any other color sets that we are also a strict superset of" would also fix this, but Rust doesn't do that, and it already doesn't have this issue.)