shithub: rgbds

--- a/CMakeLists.txt

+++ b/CMakeLists.txt

@@ -10,7 +10,7 @@

 cmake_minimum_required(VERSION 3.9 FATAL_ERROR)

 project(rgbds

-        LANGUAGES C)

+        LANGUAGES C CXX)

 # get real path of source and binary directories

 get_filename_component(srcdir "${CMAKE_SOURCE_DIR}" REALPATH)

@@ -45,14 +45,14 @@

     # A non-zero optimization level is desired in debug mode, but allow overriding it nonetheless

     # TODO: this overrides anything previously set... that's a bit sloppy!

     set(CMAKE_C_FLAGS_DEBUG "-g -Og -fno-omit-frame-pointer -fno-optimize-sibling-calls" CACHE STRING "" FORCE)

+    set(CMAKE_CXX_FLAGS_DEBUG "-g -Og -fno-omit-frame-pointer -fno-optimize-sibling-calls" CACHE STRING "" FORCE)

   endif()

   if(MORE_WARNINGS)

     add_compile_options(-Werror -Wextra

                         -Walloc-zero -Wcast-align -Wcast-qual -Wduplicated-branches -Wduplicated-cond

-                        -Wfloat-equal -Wlogical-op -Wnested-externs -Wnull-dereference

-                        -Wold-style-definition -Wshift-overflow=2 -Wstrict-overflow=5

-                        -Wstrict-prototypes -Wstringop-overflow=4 -Wundef -Wuninitialized -Wunused

+                        -Wfloat-equal -Wlogical-op -Wnull-dereference -Wshift-overflow=2

+                        -Wstringop-overflow=4 -Wstrict-overflow=5 -Wundef -Wuninitialized -Wunused

                         -Wshadow # TODO: -Wshadow=compatible-local ?

                         -Wformat=2 -Wformat-overflow=2 -Wformat-truncation=1

                         -Wno-format-nonliteral # We have a couple of "dynamic" prints

--- a/Makefile

+++ b/Makefile

@@ -7,7 +7,7 @@

 .SUFFIXES:

-.SUFFIXES: .h .y .c .o

+.SUFFIXES: .h .y .c .cpp .o

 # User-defined variables

@@ -34,10 +34,13 @@

 # Overridable CFLAGS

 CFLAGS		?= -O3 -flto -DNDEBUG

+CXXFLAGS	?= -O3 -flto -DNDEBUG

 # Non-overridable CFLAGS

 # _ISOC11_SOURCE is required on certain platforms to get C11 on top of the C99-based POSIX 2008

 REALCFLAGS	:= ${CFLAGS} ${WARNFLAGS} -std=gnu11 -I include \

 		   -D_POSIX_C_SOURCE=200809L -D_ISOC11_SOURCE

+REALCXXFLAGS	:= ${CXXFLAGS} ${WARNFLAGS} -std=c++17 -I include \

+		   -D_POSIX_C_SOURCE=200809L -fno-exceptions -fno-rtti

 # Overridable LDFLAGS

 LDFLAGS		?=

 # Non-overridable LDFLAGS

@@ -102,9 +105,11 @@

 	src/error.o

 rgbgfx_obj := \

-	src/gfx/gb.o \

+	src/gfx/convert.o \

 	src/gfx/main.o \

-	src/gfx/makepng.o \

+	src/gfx/pal_packing.o \

+	src/gfx/pal_sorting.o \

+	src/gfx/proto_palette.o \

 	src/extern/getopt.o \

 	src/error.o

@@ -118,7 +123,7 @@

 	$Q${CC} ${REALLDFLAGS} -o $@ ${rgbfix_obj} ${REALCFLAGS} src/version.c

 rgbgfx: ${rgbgfx_obj}

-	$Q${CC} ${REALLDFLAGS} ${PNGLDFLAGS} -o $@ ${rgbgfx_obj} ${REALCFLAGS} src/version.c ${PNGLDLIBS}

+	$Q${CXX} ${REALLDFLAGS} ${PNGLDFLAGS} -o $@ ${rgbgfx_obj} ${REALCXXFLAGS} src/version.c ${PNGLDLIBS}

 # Rules to process files

@@ -145,8 +150,11 @@

 	${BISON} $$DEFS -d ${YFLAGS} -o $@ $<

 .c.o:

-	$Q${CC} ${REALCFLAGS} ${PNGCFLAGS} -c -o $@ $<

+	$Q${CC} ${REALCFLAGS} -c -o $@ $<

+.cpp.o:

+	$Q${CXX} ${REALCXXFLAGS} ${PNGCFLAGS} -c -o $@ $<

 # Target used to remove all files generated by other Makefile targets

 clean:

@@ -214,11 +222,9 @@

 develop:

 	$Qenv ${MAKE} WARNFLAGS="-Werror -Wextra \

 		-Walloc-zero -Wcast-align -Wcast-qual -Wduplicated-branches -Wduplicated-cond \

-		-Wfloat-equal -Wlogical-op -Wnested-externs -Wold-style-definition \

-		-Wshift-overflow=2 \

-		-Wstrict-overflow=5 -Wstrict-prototypes -Wundef -Wuninitialized -Wunused \

+		-Wfloat-equal -Wlogical-op -Wnull-dereference -Wshift-overflow=2 \

+		-Wstringop-overflow=4 -Wstrict-overflow=5 -Wundef -Wuninitialized -Wunused \

 		-Wshadow \

-		-Wnull-dereference -Wstringop-overflow=4 \

 		-Wformat=2 -Wformat-overflow=2 -Wformat-truncation=1 \

 		-Wno-format-nonliteral \

 		-Wno-type-limits -Wno-tautological-constant-out-of-range-compare \

@@ -229,7 +235,8 @@

 		-fsanitize=signed-integer-overflow -fsanitize=bounds \

 		-fsanitize=object-size -fsanitize=bool -fsanitize=enum \

 		-fsanitize=alignment -fsanitize=null -fsanitize=address" \

-		CFLAGS="-ggdb3 -Og -fno-omit-frame-pointer -fno-optimize-sibling-calls"

+		CFLAGS="-ggdb3 -Og -fno-omit-frame-pointer -fno-optimize-sibling-calls" \

+		CXXFLAGS="-ggdb3 -Og -fno-omit-frame-pointer -fno-optimize-sibling-calls"

 # Targets for the project maintainer to easily create Windows exes.

 # This is not for Windows users!

--- a/README.rst

+++ b/README.rst

@@ -129,3 +129,11 @@

 - 2018, codebase relicensed under the MIT license.

 - 2020, repository is moved to the `gbdev <https://github.com/gbdev>`__ organisation. The `rgbds.gbdev.io <https://rgbds.gbdev.io>`__ website serving documentation and downloads is created.

+4. Acknowledgements

+-------------------

+RGBGFX generates palettes using algorithms found in the paper

+`"Algorithms for the Pagination Problem, a Bin Packing with Overlapping Items" <http://arxiv.org/abs/1605.00558>`__

+(`GitHub <https://github.com/pagination-problem/pagination>`__, MIT license),

+by Aristide Grange, Imed Kacem, and Sébastien Martin.

--- /dev/null

+++ b/include/defaultinitalloc.hpp

@@ -1,0 +1,38 @@

+/**

+ * Allocator adaptor that interposes construct() calls to convert value-initialization

+ * (which is what you get with e.g. `vector::resize`) into default-initialization (which does not

+ * zero out non-class types).

+ * From https://stackoverflow.com/questions/21028299/is-this-behavior-of-vectorresizesize-type-n-under-c11-and-boost-container/21028912#21028912

+ */

+#ifndef DEFAULT_INIT_ALLOC_H

+#define DEFAULT_INIT_ALLOC_H

+#include <memory>

+#include <vector>

+template<typename T, typename A = std::allocator<T>>

+class default_init_allocator : public A {

+	using a_t = std::allocator_traits<A>;

+public:

+	template<typename U>

+	struct rebind {

+		using other = default_init_allocator<U, typename a_t::template rebind_alloc<U>>;

+	};

+	using A::A; // Inherit the allocator's constructors

+	template<typename U>

+	void construct(U * ptr) noexcept(std::is_nothrow_default_constructible_v<U>) {

+		::new(static_cast<void *>(ptr)) U;

+	}

+	template<typename U, typename... Args>

+	void construct(U * ptr, Args && ... args) {

+		a_t::construct(static_cast<A &>(*this), ptr, std::forward<Args>(args)...);

+	}

+};

+template<typename T>

+using DefaultInitVec = std::vector<T, default_init_allocator<T>>;

+#endif

--- a/include/error.h

+++ b/include/error.h

@@ -12,10 +12,18 @@

 #include "helpers.h"

 #include "platform.h"

+#ifdef __cplusplus

+extern "C" {

+#endif

 void warn(char const NONNULL(fmt), ...) format_(printf, 1, 2);

 void warnx(char const NONNULL(fmt), ...) format_(printf, 1, 2);

 _Noreturn void err(char const NONNULL(fmt), ...) format_(printf, 1, 2);

 _Noreturn void errx(char const NONNULL(fmt), ...) format_(printf, 1, 2);

+#ifdef __cplusplus

+}

+#endif

 #endif /* RGBDS_ERROR_H */

--- a/include/extern/getopt.h

+++ b/include/extern/getopt.h

@@ -26,6 +26,10 @@

 #ifndef RGBDS_EXTERN_GETOPT_H

 #define RGBDS_EXTERN_GETOPT_H

+#ifdef __cplusplus

+extern "C" {

+#endif

 extern char *musl_optarg;

 extern int musl_optind, musl_opterr, musl_optopt, musl_optreset;

@@ -42,5 +46,9 @@

 #define no_argument        0

 #define required_argument  1

 #define optional_argument  2

+#ifdef __cplusplus

+} // extern "C"

+#endif

 #endif

--- /dev/null

+++ b/include/gfx/convert.hpp

@@ -1,0 +1,14 @@

+/*

+ * This file is part of RGBDS.

+ *

+ * Copyright (c) 2022, Eldred Habert and RGBDS contributors.

+ *

+ * SPDX-License-Identifier: MIT

+ */

+#ifndef RGBDS_GFX_CONVERT_HPP

+#define RGBDS_GFX_CONVERT_HPP

+void process();

+#endif /* RGBDS_GFX_CONVERT_HPP */

--- a/include/gfx/main.h

+++ /dev/null

@@ -1,91 +1,0 @@

-/*

- * This file is part of RGBDS.

- *

- * Copyright (c) 2013-2018, stag019 and RGBDS contributors.

- *

- * SPDX-License-Identifier: MIT

- */

-#ifndef RGBDS_GFX_MAIN_H

-#define RGBDS_GFX_MAIN_H

-#include <png.h>

-#include <stdbool.h>

-#include <stdint.h>

-#include "error.h"

-struct Options {

-	bool debug;

-	bool verbose;

-	bool hardfix;

-	bool fix;

-	bool horizontal;

-	bool mirror;

-	bool unique;

-	bool colorcurve;

-	unsigned int trim;

-	char *tilemapfile;

-	bool tilemapout;

-	char *attrmapfile;

-	bool attrmapout;

-	char *palfile;

-	bool palout;

-	char *outfile;

-	char *infile;

-};

-struct RGBColor {

-	uint8_t red;

-	uint8_t green;

-	uint8_t blue;

-};

-struct ImageOptions {

-	bool horizontal;

-	unsigned int trim;

-	char *tilemapfile;

-	bool tilemapout;

-	char *attrmapfile;

-	bool attrmapout;

-	char *palfile;

-	bool palout;

-};

-struct PNGImage {

-	png_struct *png;

-	png_info *info;

-	png_byte **data;

-	int width;

-	int height;

-	png_byte depth;

-	png_byte type;

-};

-struct RawIndexedImage {

-	uint8_t **data;

-	struct RGBColor *palette;

-	int num_colors;

-	unsigned int width;

-	unsigned int height;

-};

-struct GBImage {

-	uint8_t *data;

-	int size;

-	bool horizontal;

-	int trim;

-};

-struct Mapfile {

-	uint8_t *data;

-	int size;

-};

-extern int depth, colors;

-#include "gfx/makepng.h"

-#include "gfx/gb.h"

-#endif /* RGBDS_GFX_MAIN_H */

--- /dev/null

+++ b/include/gfx/main.hpp

@@ -1,0 +1,59 @@

+/*

+ * This file is part of RGBDS.

+ *

+ * Copyright (c) 2022, Eldred Habert and RGBDS contributors.

+ *

+ * SPDX-License-Identifier: MIT

+ */

+#ifndef RGBDS_GFX_MAIN_HPP

+#define RGBDS_GFX_MAIN_HPP

+#include <array>

+#include <filesystem>

+#include <stdint.h>

+#include "helpers.h"

+struct Options {

+	bool beVerbose = false; // -v

+	bool fixInput = false; // -f

+	bool columnMajor = false; // -h; whether to output the tilemap in columns instead of rows

+	bool allowMirroring = false; // -m

+	bool allowDedup = false; // -u

+	bool useColorCurve = false; // -C

+	uint8_t bitDepth = 2; // -d

+	uint64_t trim = 0; // -x

+	uint8_t nbPalettes = 8; // TODO

+	uint8_t nbColorsPerPal = 0; // TODO; 0 means "auto" = 1 << bitDepth;

+	std::array<uint8_t, 2> baseTileIDs{0, 0}; // TODO

+	std::array<uint16_t, 2> maxNbTiles{384, 0}; // TODO

+	std::filesystem::path tilemap{}; // -t, -T

+	std::filesystem::path attrmap{}; // -a, -A

+	std::filesystem::path palettes{}; // -p, -P

+	std::filesystem::path output{}; // -o

+	std::filesystem::path input{}; // positional arg

+	format_(printf, 2, 3) void verbosePrint(char const *fmt, ...) const;

+};

+extern Options options;

+void warning(char const *fmt, ...);

+void error(char const *fmt, ...);

+[[noreturn]] void fatal(char const *fmt, ...);

+struct Palette {

+	// An array of 4 GBC-native (RGB555) colors

+	std::array<uint16_t, 4> colors{UINT16_MAX, UINT16_MAX, UINT16_MAX, UINT16_MAX};

+	void addColor(uint16_t color);

+	uint8_t indexOf(uint16_t color) const;

+	decltype(colors)::iterator begin();

+	decltype(colors)::iterator end();

+	decltype(colors)::const_iterator begin() const;

+	decltype(colors)::const_iterator end() const;

+};

+#endif /* RGBDS_GFX_MAIN_HPP */

--- /dev/null

+++ b/include/gfx/pal_packing.hpp

@@ -1,0 +1,32 @@

+/*

+ * This file is part of RGBDS.

+ *

+ * Copyright (c) 2022, Eldred Habert and RGBDS contributors.

+ *

+ * SPDX-License-Identifier: MIT

+ */

+#ifndef RGBDS_GFX_PAL_PACKING_HPP

+#define RGBDS_GFX_PAL_PACKING_HPP

+#include <tuple>

+#include <vector>

+#include "defaultinitalloc.hpp"

+#include "gfx/main.hpp"

+class Palette;

+class ProtoPalette;

+namespace packing {

+/**

+ * Returns which palette each proto-palette maps to, and how many palettes are necessary

+ */

+std::tuple<DefaultInitVec<size_t>, size_t>

+	overloadAndRemove(std::vector<ProtoPalette> const &protoPalettes);

+}

+#endif /* RGBDS_GFX_PAL_PACKING_HPP */

--- /dev/null

+++ b/include/gfx/pal_sorting.hpp

@@ -1,0 +1,26 @@

+/*

+ * This file is part of RGBDS.

+ *

+ * Copyright (c) 2022, Eldred Habert and RGBDS contributors.

+ *

+ * SPDX-License-Identifier: MIT

+ */

+#ifndef RGBDS_GFX_PAL_SORTING_HPP

+#define RGBDS_GFX_PAL_SORTING_HPP

+#include <png.h>

+#include <vector>

+class Palette;

+namespace sorting {

+void indexed(std::vector<Palette> &palettes, int palSize, png_color const *palRGB,

+             png_byte *palAlpha);

+void grayscale(std::vector<Palette> &palettes);

+void rgb(std::vector<Palette> &palettes);

+}

+#endif /* RGBDS_GFX_PAL_SORTING_HPP */

--- /dev/null

+++ b/include/gfx/proto_palette.hpp

@@ -1,0 +1,44 @@

+/*

+ * This file is part of RGBDS.

+ *

+ * Copyright (c) 2022, Eldred Habert and RGBDS contributors.

+ *

+ * SPDX-License-Identifier: MIT

+ */

+#ifndef RGBDS_GFX_PROTO_PALETTE_HPP

+#define RGBDS_GFX_PROTO_PALETTE_HPP

+#include <algorithm>

+#include <array>

+#include <stddef.h>

+#include <stdint.h>

+class ProtoPalette {

+	// Up to 4 colors, sorted, and where SIZE_MAX means the slot is empty

+	// (OK because it's not a valid color index)

+	std::array<uint16_t, 4> _colorIndices{UINT16_MAX, UINT16_MAX, UINT16_MAX, UINT16_MAX};

+public:

+	/**

+	 * Adds the specified color to the set

+	 * Returns false if the set is full

+	 */

+	bool add(uint16_t color);

+	enum ComparisonResult {

+		NEITHER,

+		WE_BIGGER,

+		THEY_BIGGER = -1,

+	};

+	ComparisonResult compare(ProtoPalette const &other) const;

+	ProtoPalette &operator=(ProtoPalette const &other);

+	size_t size() const;

+	decltype(_colorIndices)::const_iterator begin() const;

+	decltype(_colorIndices)::const_iterator end() const;

+};

+#endif /* RGBDS_GFX_PROTO_PALETTE_HPP */

--- a/include/version.h

+++ b/include/version.h

@@ -9,10 +9,18 @@

 #ifndef EXTERN_VERSION_H

 #define EXTERN_VERSION_H

+#ifdef __cplusplus

+extern "C" {

+#endif

 #define PACKAGE_VERSION_MAJOR 0

 #define PACKAGE_VERSION_MINOR 5

 #define PACKAGE_VERSION_PATCH 2

 char const *get_package_version_string(void);

+#ifdef __cplusplus

+}

+#endif

 #endif /* EXTERN_VERSION_H */

--- a/man/rgbgfx.1

+++ b/man/rgbgfx.1

@@ -25,23 +25,7 @@

 .Sh DESCRIPTION

The

.Nm

-program converts PNG images into the Nintendo Game Boy's planar tile format.

-.Pp

-The resulting colors and their palette indices are determined differently depending on the input PNG file:

-.Bl -dash -width Ds

-.It

-If the file has an embedded palette, that palette's color and order are used.

-.It

-If not, and the image only contains shades of gray, rgbgfx maps them to the indices appropriate for each shade.

-Any undetermined indices are set to respective default shades of gray.

-For example: if the bit depth is 2 and the image contains light gray and black, they become the second and fourth colors, and the first and third colors get set to default white and dark gray.

-If the image has multiple shades that map to the same index, the palette is instead determined as if the image had color.

-.It

-If the image has color (or the grayscale method failed), the colors are sorted from lightest to darkest.

-.El

-.Pp

-The input image may not contain more colors than the selected bit depth allows.

-Transparent pixels are set to palette index 0.

+program converts PNG images into data suitable

 .Sh ARGUMENTS

 Note that options can be abbreviated as long as the abbreviation is unambiguous:

 .Fl Fl verb

@@ -117,30 +101,60 @@

 .It Fl v , Fl Fl verbose

 Verbose.

 Print errors when the command line parameters and the parameters in the PNG file don't match.

-.It Fl x Ar tiles , Fl Fl trim-end Ar tiles

+.It Fl x Ar amount , Fl Fl trim-end Ar amount

 Trim the end of the output file by this many tiles.

+.Pq TODO: tiles, or tilemap?

.El

+.Sh PALETTE GENERATION

+.Nm

+must decide in which order to place colors in the palettes, but the input PNG usually lacks any indications.

+A lot of the time, the order does not matter; however, sometimes it does, and

+.Nm

+attempts to account for those cases.

+.Bl -bullet -offset indent

+.It

+First, if the image contains

+.Em any

+transparent pixel, color #0 of

+.Em all

+palettes will be allocated to it.

+If palettes were explicitly specified using

+.Fl TODO ,

+then they will specify color #1 onwards.

+.Pq If you do not want this, ask your image editor to remove the alpha channel.

+.It

+If the PNG file internally contains a palette (often dubbed an

+.Dq indexed

+PNG), then colors in each output palette will be sorted according to their order in the PNG's palette.

+Any unused entries will be ignored, and only the first entry is considered if there any duplicates.

+.Pq If you want a given color to appear more than once in a palette, you should specify the palettes explicitly instead using Fl TODO .

+.It

+Otherwise, if the PNG only contains shades of gray, they will be categorized into 4

+.Dq bins

+.Pq white, light gray, dark gray, and black in this order ,

+and the palette is set to these four bins.

+(TODO: how does this interact with 1bpp? With more than 1 palette?)

+If more than one grey ends up in the same bin, the RGB method below is used instead.

+.It

+If none of the above apply, colors are sorted from lightest to darkest.

+(This is what the old documentation claimed, but the definition of luminance that was used wasn't quite right.

+It is kept for compatibility.)

+.El

+.Pp

+Note that the

+.Dq indexed

+behavior depends on an internal detail of how the PNG is saved.

+Since few image editors (such as GIMP) expose that detail, this behavior is only kept for compatibility and should be considered deprecated; if the order of colors in the palettes is important to you, please use

+.Fl TODO

+to specify the palette explicitly.

+.Sh OUTPUT FILES

+.Ss Palette data

+Palette data is output like a dump of GBC palette memory: the output is a binary file.

+Each color is written as GBC-native little-endian RGB555 (that is, the first byte contains the red and the lower 3 bits of green).

+There is no padding between colors, nor between palettes; however, empty colors in the palettes are filled as 0xFF bytes.

 .Sh EXAMPLES

-The following will take a PNG file with a bit depth of 1, 2, or 8, and output planar 2bpp data:

+The following will only validate the PNG [...] but output nothing:

.Pp

-.D1 $ rgbgfx -o out.2bpp in.png

-.Pp

-The following creates a planar 2bpp file with only unique tiles, and its tilemap

-.Pa out.tilemap :

-.Pp

-.D1 $ rgbgfx -T -u -o out.2bpp in.png

-.Pp

-The following creates a planar 2bpp file with only unique tiles

-.Pa accounting for tile mirroring

-and its associated tilemap

-.Pa out.tilemap

-and attrmap

-.Pa out.attrmap :

-.Pp

-.D1 $ rgbgfx -A -T -m -o out.2bpp in.png

-.Pp

-The following will do nothing:

-.Pp

 .D1 $ rgbgfx in.png

 .Sh BUGS

 Please report bugs on

@@ -153,8 +167,10 @@

 .Xr gbz80 7

 .Sh HISTORY

.Nm

-was created by

+was originally created by

 .An stag019

 to be included in RGBDS.

-It is now maintained by a number of contributors at

+It was later rewritten by

+.An ISSOtm ,

+and is now maintained by a number of contributors at

 .Lk https://github.com/gbdev/rgbds .

--- a/src/CMakeLists.txt

+++ b/src/CMakeLists.txt

@@ -70,9 +70,13 @@

 set(rgbgfx_src

-    "gfx/gb.c"

-    "gfx/main.c"

-    "gfx/makepng.c"

+    "gfx/convert.cpp"

+    "gfx/main.cpp"

+    "gfx/pal_packing.cpp"

+    "gfx/pal_sorting.cpp"

+    "gfx/proto_palette.cpp"

+    "extern/getopt.c"

+    "error.c"

 set(rgblink_src

@@ -96,6 +100,8 @@

   install(TARGETS rgb${PROG} RUNTIME DESTINATION bin)

 endforeach()

+set_target_properties(rgbgfx PROPERTIES CXX_STANDARD 17 CXX_STANDARD_REQUIRED True)

 if(LIBPNG_FOUND) # pkg-config

   target_include_directories(rgbgfx PRIVATE ${LIBPNG_INCLUDE_DIRS})

--- /dev/null

+++ b/src/gfx/convert.cpp

@@ -1,0 +1,869 @@

+/*

+ * This file is part of RGBDS.

+ *

+ * Copyright (c) 2022, Eldred Habert and RGBDS contributors.

+ *

+ * SPDX-License-Identifier: MIT

+ */

+#include "gfx/convert.hpp"

+#include <algorithm>

+#include <assert.h>

+#include <errno.h>

+#include <fstream>

+#include <inttypes.h>

+#include <memory>

+#include <optional>

+#include <png.h>

+#include <setjmp.h>

+#include <string.h>

+#include <tuple>

+#include <unordered_set>

+#include <utility>

+#include <vector>

+#include "defaultinitalloc.hpp"

+#include "helpers.h"

+#include "gfx/main.hpp"

+#include "gfx/pal_packing.hpp"

+#include "gfx/pal_sorting.hpp"

+#include "gfx/proto_palette.hpp"

+struct Rgba {

+	uint8_t red;

+	uint8_t green;

+	uint8_t blue;

+	uint8_t alpha;

+	Rgba(uint8_t r, uint8_t g, uint8_t b, uint8_t a) : red(r), green(g), blue(b), alpha(a) {}

+	Rgba(uint32_t rgba) : red(rgba), green(rgba >> 8), blue(rgba >> 16), alpha(rgba >> 24) {}

+	operator uint32_t() const {

+		auto shl = [](uint8_t val, unsigned shift) { return static_cast<uint32_t>(val) << shift; };

+		return shl(red, 0) | shl(green, 8) | shl(blue, 16) | shl(alpha, 24);

+	}

+	bool operator!=(Rgba const &other) const {

+		return static_cast<uint32_t>(*this) != static_cast<uint32_t>(other);

+	}

+	bool isGray() const { return red == green && green == blue; }

+	/**

+	 * CGB colors are RGB555, so we use bit 15 to signify that the color is transparent instead

+	 * Since the rest of the bits don't matter then, we return 0x8000 exactly.

+	 */

+	static constexpr uint16_t transparent = 0b1'00000'00000'00000;

+	static constexpr uint8_t transparency_threshold = 5; // TODO: adjust this

+	/**

+	 * Computes the equivalent CGB color, respects the color curve depending on options

+	 */

+	uint16_t cgbColor() const {

+		if (alpha < transparency_threshold)

+			return transparent;

+		if (options.useColorCurve) {

+			assert(!"TODO");

+		} else {

+			return (red >> 3) | (green >> 3) << 5 | (blue >> 3) << 10;

+		}

+	}

+};

+class ImagePalette {

+	// Use as many slots as there are CGB colors (plus transparency)

+	std::array<std::optional<Rgba>, 0x8001> _colors;

+public:

+	ImagePalette() = default;

+	void registerColor(Rgba const &rgba) {

+		decltype(_colors)::value_type &slot = _colors[rgba.cgbColor()];

+		if (!slot.has_value()) {

+			slot.emplace(rgba);

+		} else if (*slot != rgba) {

+			warning("Different colors melded together"); // TODO: indicate position

+		}

+	}

+	size_t size() const { return _colors.size(); }

+	auto begin() const { return _colors.begin(); }

+	auto end() const { return _colors.end(); }

+};

+class Png {

+	std::filesystem::path const &path;

+	std::filebuf file{};

+	png_structp png = nullptr;

+	png_infop info = nullptr;

+	// These are cached for speed

+	uint32_t width, height;

+	DefaultInitVec<uint16_t> pixels;

+	ImagePalette colors;

+	int colorType;

+	int nbColors;

+	png_colorp embeddedPal = nullptr;

+	png_bytep transparencyPal = nullptr;

+	bool isGrayOnly = true;

+	[[noreturn]] static void handleError(png_structp png, char const *msg) {

+		struct Png *self = reinterpret_cast<Png *>(png_get_error_ptr(png));

+		fatal("Error reading input image (\"%s\"): %s", self->path.c_str(), msg);

+	}

+	static void handleWarning(png_structp png, char const *msg) {

+		struct Png *self = reinterpret_cast<Png *>(png_get_error_ptr(png));

+		warning("In input image (\"%s\"): %s", self->path.c_str(), msg);

+	}

+	static void readData(png_structp png, png_bytep data, size_t length) {

+		struct Png *self = reinterpret_cast<Png *>(png_get_io_ptr(png));

+		std::streamsize expectedLen = length;

+		std::streamsize nbBytesRead = self->file.sgetn(reinterpret_cast<char *>(data), expectedLen);

+		if (nbBytesRead != expectedLen) {

+			fatal("Error reading input image (\"%s\"): file too short (expected at least %zd more "

+			      "bytes after reading %lld)",

+			      self->path.c_str(), length - nbBytesRead,

+			      self->file.pubseekoff(0, std::ios_base::cur));

+		}

+	}

+public:

+	ImagePalette const &getColors() const { return colors; }

+	int getColorType() const { return colorType; }

+	std::tuple<int, png_const_colorp, png_bytep> getEmbeddedPal() const {

+		return {nbColors, embeddedPal, transparencyPal};

+	}

+	uint32_t getWidth() const { return width; }

+	uint32_t getHeight() const { return height; }

+	uint16_t &pixel(uint32_t x, uint32_t y) { return pixels[y * width + x]; }

+	uint16_t const &pixel(uint32_t x, uint32_t y) const { return pixels[y * width + x]; }

+	bool hasNonGray() const { return !isGrayOnly; }

+	/**

+	 * Reads a PNG and notes all of its colors

+	 *

+	 * This code is more complicated than strictly necessary, but that's because of the API

+	 * being used: the "high-level" interface doesn't provide all the transformations we need,

+	 * so we use the "lower-level" one instead.

+	 * We also use that occasion to only read the PNG one line at a time, since we store all of

+	 * the pixel data in `pixels`, which saves on memory allocations.

+	 */

+	explicit Png(std::filesystem::path const &filePath) : path(filePath), colors() {

+		if (file.open(path, std::ios_base::in | std::ios_base::binary) == nullptr) {

+			fatal("Failed to open input image (\"%s\"): %s", path.c_str(), strerror(errno));

+		}

+		options.verbosePrint("Opened input file\n");

+		std::array<unsigned char, 8> pngHeader;

+		if (file.sgetn(reinterpret_cast<char *>(pngHeader.data()), pngHeader.size())

+		        != static_cast<std::streamsize>(pngHeader.size()) // Not enough bytes?

+		    || png_sig_cmp(pngHeader.data(), 0, pngHeader.size()) != 0) {

+			fatal("Input file (\"%s\") is not a PNG image!", path.c_str());

+		}

+		options.verbosePrint("PNG header signature is OK\n");

+		png = png_create_read_struct(PNG_LIBPNG_VER_STRING, (png_voidp)this, handleError,

+		                             handleWarning);

+		if (!png) {

+			fatal("Failed to allocate PNG structure: %s", strerror(errno));

+		}

+		info = png_create_info_struct(png);

+		if (!info) {

+			png_destroy_read_struct(&png, nullptr, nullptr);

+			fatal("Failed to allocate PNG info structure: %s", strerror(errno));

+		}

+		png_set_read_fn(png, this, readData);

+		png_set_sig_bytes(png, pngHeader.size());

+		// TODO: png_set_crc_action(png, PNG_CRC_ERROR_QUIT, PNG_CRC_WARN_DISCARD);

+		// Skipping chunks we don't use should improve performance

+		// TODO: png_set_keep_unknown_chunks(png, ...);

+		// Process all chunks up to but not including the image data

+		png_read_info(png, info);

+		int bitDepth, interlaceType; //, compressionType, filterMethod;

+		png_get_IHDR(png, info, &width, &height, &bitDepth, &colorType, &interlaceType, nullptr,

+		             nullptr);

+		if (width % 8 != 0)

+			fatal("Image width (%" PRIu32 " pixels) is not a multiple of 8!", width);

+		if (height % 8 != 0)

+			fatal("Image height (%" PRIu32 " pixels) is not a multiple of 8!", height);

+		// TODO: use an allocator that doesn't zero on init to save potentially a lot of perf

+		// https://stackoverflow.com/questions/21028299/is-this-behavior-of-vectorresizesize-type-n-under-c11-and-boost-container/21028912#21028912

+		pixels.resize(static_cast<size_t>(width) * static_cast<size_t>(height));

+		auto colorTypeName = [this]() {

+			switch (colorType) {

+			case PNG_COLOR_TYPE_GRAY:

+				return "grayscale";

+			case PNG_COLOR_TYPE_GRAY_ALPHA:

+				return "grayscale + alpha";

+			case PNG_COLOR_TYPE_PALETTE:

+				return "palette";

+			case PNG_COLOR_TYPE_RGB:

+				return "RGB";

+			case PNG_COLOR_TYPE_RGB_ALPHA:

+				return "RGB + alpha";

+			default:

+				fatal("Unknown color type %d", colorType);

+			}

+		};

+		auto interlaceTypeName = [&interlaceType]() {

+			switch (interlaceType) {

+			case PNG_INTERLACE_NONE:

+				return "not interlaced";

+			case PNG_INTERLACE_ADAM7:

+				return "interlaced (Adam7)";

+			default:

+				fatal("Unknown interlace type %d", interlaceType);

+			}

+		};

+		options.verbosePrint("Input image: %" PRIu32 "x%" PRIu32 " pixels, %dbpp %s, %s\n", height,

+		                     width, bitDepth, colorTypeName(), interlaceTypeName());

+		if (png_get_PLTE(png, info, &embeddedPal, &nbColors) != 0) {

+			int nbTransparentEntries;

+			if (png_get_tRNS(png, info, &transparencyPal, &nbTransparentEntries, nullptr)) {

+				assert(nbTransparentEntries == nbColors);

+			}

+			options.verbosePrint("Embedded palette has %d colors: [", nbColors);

+			for (int i = 0; i < nbColors; ++i) {

+				auto const &color = embeddedPal[i];

+				options.verbosePrint("#%02x%02x%02x%s", color.red, color.green, color.blue,

+				                     i != nbColors - 1 ? ", " : "]\n");

+			}

+		} else {

+			options.verbosePrint("No embedded palette\n");

+		}

+		// Set up transformations; to turn everything into RGBA888

+		// TODO: it's not necessary to uniformize the pixel data (in theory), and not doing

+		// so *might* improve performance, and should reduce memory usage.

+		// Convert grayscale to RGB

+		switch (colorType & ~PNG_COLOR_MASK_ALPHA) {

+		case PNG_COLOR_TYPE_GRAY:

+			png_set_gray_to_rgb(png); // This also converts tRNS to alpha

+			break;

+		case PNG_COLOR_TYPE_PALETTE:

+			png_set_palette_to_rgb(png);

+			break;

+		}

+		// If we read a tRNS chunk, convert it to alpha

+		if (png_get_valid(png, info, PNG_INFO_tRNS))

+			png_set_tRNS_to_alpha(png);

+		// Otherwise, if we lack an alpha channel, default to full opacity

+		else if (!(colorType & PNG_COLOR_MASK_ALPHA))

+			png_set_add_alpha(png, 0xFFFF, PNG_FILLER_AFTER);

+		// Scale 16bpp back to 8 (we don't need all of that precision anyway)

+		if (bitDepth == 16)

+			png_set_scale_16(png);

+		else if (bitDepth < 8)

+			png_set_packing(png);

+		// Set interlace handling (MUST be done before `png_read_update_info`)

+		int nbPasses = png_set_interlace_handling(png);

+		// Update `info` with the transformations

+		png_read_update_info(png, info);

+		// These shouldn't have changed

+		assert(png_get_image_width(png, info) == width);

+		assert(png_get_image_height(png, info) == height);

+		// These should have changed, however

+		assert(png_get_color_type(png, info) == PNG_COLOR_TYPE_RGBA);

+		assert(png_get_bit_depth(png, info) == 8);

+		// Now that metadata has been read, we can process the image data

+		std::vector<png_byte> row(png_get_rowbytes(png, info));

+		if (interlaceType == PNG_INTERLACE_NONE) {

+			for (png_uint_32 y = 0; y < height; ++y) {

+				png_read_row(png, row.data(), nullptr);

+				for (png_uint_32 x = 0; x < width; ++x) {

+					Rgba rgba(row[x * 4], row[x * 4 + 1], row[x * 4 + 2], row[x * 4 + 3]);

+					colors.registerColor(rgba);

+					pixel(x, y) = rgba.cgbColor();

+					isGrayOnly &= rgba.isGray();

+				}

+			}

+		} else {

+			// For interlace to work properly, we must read the image `nbPasses` times

+			for (int pass = 0; pass < nbPasses; ++pass) {

+				// The interlacing pass must be skipped if its width or height is reported as zero

+				if (PNG_PASS_COLS(width, pass) == 0 || PNG_PASS_ROWS(height, pass) == 0) {

+					continue;

+				}

+				png_uint_32 xStep = 1u << PNG_PASS_COL_SHIFT(pass);

+				png_uint_32 yStep = 1u << PNG_PASS_ROW_SHIFT(pass);

+				for (png_uint_32 y = PNG_PASS_START_ROW(pass); y < height; y += yStep) {

+					png_bytep ptr = row.data();

+					png_read_row(png, ptr, nullptr);

+					for (png_uint_32 x = PNG_PASS_START_COL(pass); x < width; x += xStep) {

+						Rgba rgba(ptr[0], ptr[1], ptr[2], ptr[3]);

+						colors.registerColor(rgba);

+						pixel(x, y) = rgba.cgbColor();

+						isGrayOnly &= rgba.isGray();

+						ptr += 4;

+					}

+				}

+			}

+		}

+		png_read_end(png,

+		             nullptr); // We don't care about chunks after the image data (comments, etc.)

+	}

+	~Png() { png_destroy_read_struct(&png, &info, nullptr); }

+	class TilesVisitor {

+		Png const &_png;

+		bool const _columnMajor;

+		uint32_t const _width, _height;

+		uint32_t const _limit = _columnMajor ? _height : _width;

+	public:

+		TilesVisitor(Png const &png, bool columnMajor, uint32_t width, uint32_t height)

+			: _png(png), _columnMajor(columnMajor), _width(width), _height(height) {}

+		class Tile {

+			Png const &_png;

+			uint32_t const _x, _y;

+		public:

+			Tile(Png const &png, uint32_t x, uint32_t y) : _png(png), _x(x), _y(y) {}

+			uint16_t pixel(uint32_t xOfs, uint32_t yOfs) const {

+				return _png.pixel(_x + xOfs, _y + yOfs);

+			}

+		};

+	private:

+		struct iterator {

+			TilesVisitor const &parent;

+			uint32_t const limit;

+			uint32_t x, y;

+		public:

+			std::pair<uint32_t, uint32_t> coords() const { return {x, y}; }

+			Tile operator*() const { return {parent._png, x, y}; }

+			iterator &operator++() {

+				auto [major, minor] = parent._columnMajor ? std::tie(y, x) : std::tie(x, y);

+				major += 8;

+				if (major == limit) {

+					minor += 8;

+					major = 0;

+				}

+				return *this;

+			}

+			bool operator!=(iterator const &rhs) const {

+				return coords() != rhs.coords(); // Compare the returned coord pairs

+			}

+		};

+	public:

+		iterator begin() const { return {*this, _width, 0, 0}; }

+		iterator end() const {

+			iterator it{*this, _width, _width - 8, _height - 8}; // Last valid one

+			return ++it; // Now one-past-last

+		}

+	};

+public:

+	TilesVisitor visitAsTiles(bool columnMajor) const {

+		return {*this, columnMajor, width, height};

+	}

+};

+class RawTiles {

+public:

+	/**

+	 * A tile which only contains indices into the image's global palette

+	 */

+	class RawTile {

+		std::array<std::array<size_t, 8>, 8> _pixelIndices{};

+	public:

+		// Not super clean, but it's closer to matrix notation

+		size_t &operator()(size_t x, size_t y) { return _pixelIndices[y][x]; }

+	};

+private:

+	std::vector<RawTile> _tiles;

+public:

+	/**

+	 * Creates a new raw tile, and returns a reference to it so it can be filled in

+	 */

+	RawTile &newTile() {

+		_tiles.emplace_back();

+		return _tiles.back();

+	}

+};

+struct AttrmapEntry {

+	size_t protoPaletteID;

+	uint16_t tileID;

+	bool yFlip;

+	bool xFlip;

+};

+static void outputPalettes(std::vector<Palette> const &palettes) {

+	std::filebuf output;

+	output.open(options.palettes, std::ios_base::out | std::ios_base::binary);

+	for (Palette const &palette : palettes) {

+		for (uint16_t color : palette) {

+			output.sputc(color & 0xFF);

+			output.sputc(color >> 8);

+		}

+	}

+}

+namespace unoptimized {

+// TODO: this is very redundant with `TileData`; try merging both?

+static void outputTileData(Png const &png, DefaultInitVec<AttrmapEntry> const &attrmap,

+                           std::vector<Palette> const &palettes,

+                           DefaultInitVec<size_t> const &mappings) {

+	std::filebuf output;

+	output.open(options.tilemap, std::ios_base::out | std::ios_base::binary);

+	auto iter = attrmap.begin();

+	for (auto tile : png.visitAsTiles(options.columnMajor)) {

+		Palette const &palette = palettes[mappings[iter->protoPaletteID]];

+		for (uint32_t y = 0; y < 8; ++y) {

+			uint16_t row = 0;

+			for (uint32_t x = 0; x < 8; ++x) {

+				row <<= 1;

+				uint8_t index = palette.indexOf(tile.pixel(x, y));

+				if (index & 1) {

+					row |= 0x001;

+				}

+				if (index & 2) {

+					row |= 0x100;

+				}

+			}

+			output.sputc(row & 0xFF);

+			output.sputc(row >> 8);

+		}

+		++iter;

+	}

+	assert(iter == attrmap.end());

+}

+static void outputMaps(Png const &png, DefaultInitVec<AttrmapEntry> const &attrmap,

+                       DefaultInitVec<size_t> const &mappings) {

+	std::optional<std::filebuf> tilemapOutput, attrmapOutput;

+	if (!options.tilemap.empty()) {

+		tilemapOutput.emplace();

+		tilemapOutput->open(options.tilemap, std::ios_base::out | std::ios_base::binary);

+	}

+	if (!options.attrmap.empty()) {

+		attrmapOutput.emplace();

+		attrmapOutput->open(options.attrmap, std::ios_base::out | std::ios_base::binary);

+	}

+	uint8_t tileID = 0;

+	uint8_t bank = 0;

+	auto iter = attrmap.begin();

+	for ([[maybe_unused]] auto tile : png.visitAsTiles(options.columnMajor)) {

+		if (tileID == options.maxNbTiles[bank]) {

+			assert(bank == 0);

+			bank = 1;

+			tileID = 0;

+		}

+		if (tilemapOutput.has_value()) {

+			tilemapOutput->sputc(tileID + options.baseTileIDs[bank]);

+		}

+		if (attrmapOutput.has_value()) {

+			uint8_t palID = mappings[iter->protoPaletteID] & 7;

+			attrmapOutput->sputc(palID | bank << 3); // The other flags are all 0

+			++iter;

+		}

+		++tileID;

+	}

+}

+} // namespace unoptimized

+static uint8_t flip(uint8_t byte) {

+	// To flip all the bits, we'll flip both nibbles, then each nibble half, etc.

+	byte = (byte & 0x0F) << 4 | (byte & 0xF0) >> 4;

+	byte = (byte & 0x33) << 2 | (byte & 0xCC) >> 2;

+	byte = (byte & 0x55) << 1 | (byte & 0xAA) >> 1;

+	return byte;

+}

+class TileData {

+	// TODO: might want to switch to `std::byte` instead?

+	std::array<uint8_t, 16> _data;

+	// The hash is a bit lax: it's the XOR of all lines, and every other nibble is identical

+	// if horizontal mirroring is in effect. It should still be a reasonable tie-breaker in

+	// non-pathological cases.

+	uint16_t _hash;

+public:

+	mutable size_t tileID;

+	TileData(Png::TilesVisitor::Tile const &tile, Palette const &palette) : _hash(0) {

+		for (uint32_t y = 0; y < 8; ++y) {

+			uint16_t bitplanes = 0;

+			for (uint32_t x = 0; x < 8; ++x) {

+				bitplanes <<= 1;

+				uint8_t index = palette.indexOf(tile.pixel(x, y));

+				if (index & 1) {

+					bitplanes |= 1;

+				}

+				if (index & 2) {

+					bitplanes |= 0x100;

+				}

+			}

+			_data[y * 2] = bitplanes & 0xFF;

+			_data[y * 2 + 1] = bitplanes >> 8;

+			// Update the hash

+			_hash ^= bitplanes;

+			if (options.allowMirroring) {

+				// Count the line itself as mirrorred; vertical mirroring is

+				// already taken care of because the symmetric line will be XOR'd

+				// the same way. (...which is a problem, but probably benign.)

+				_hash ^= flip(bitplanes >> 8) << 8 | flip(bitplanes & 0xFF);

+			}

+		}

+	}

+	auto const &data() const { return _data; }

+	uint16_t hash() const { return _hash; }

+	enum MatchType {

+		NOPE,

+		EXACT,

+		HFLIP,

+		VFLIP,

+		VHFLIP,

+	};

+	MatchType tryMatching(TileData const &other) const {

+		if (std::equal(_data.begin(), _data.end(), other._data.begin()))

+			return MatchType::EXACT;

+		if (options.allowMirroring) {

+			// TODO

+		}

+		return MatchType::NOPE;

+	}

+	friend bool operator==(TileData const &lhs, TileData const &rhs) {

+		return lhs.tryMatching(rhs) != MatchType::NOPE;

+	}

+};

+template<>

+struct std::hash<TileData> {

+	std::size_t operator()(TileData const &tile) const { return tile.hash(); }

+};

+namespace optimized {

+struct UniqueTiles {

+	std::unordered_set<TileData> tileset;

+	std::vector<TileData const *> tiles;

+	UniqueTiles() = default;

+	// Copies are likely to break pointers, so we really don't want those.

+	// Copy elision should be relied on to be more sure that refs won't be invalidated, too!

+	UniqueTiles(UniqueTiles const &) = delete;

+	UniqueTiles(UniqueTiles &&) = default;

+	/**

+	 * Adds a tile to the collection, and returns its ID

+	 */

+	std::tuple<uint16_t, TileData::MatchType> addTile(Png::TilesVisitor::Tile const &tile,

+	                                                  Palette const &palette) {

+		TileData newTile(tile, palette);

+		auto [tileData, inserted] = tileset.insert(newTile);

+		TileData::MatchType matchType = TileData::EXACT;

+		if (inserted) {

+			// Give the new tile the next available unique ID

+			tileData->tileID = tiles.size();

+			// Pointers are never invalidated!

+			tiles.emplace_back(&*tileData);

+		} else {

+			matchType = tileData->tryMatching(newTile);

+		}

+		return {tileData->tileID, matchType};

+	}

+	auto size() const { return tiles.size(); }

+	auto begin() const { return tiles.begin(); }

+	auto end() const { return tiles.end(); }

+};

+static UniqueTiles dedupTiles(Png const &png, DefaultInitVec<AttrmapEntry> &attrmap,

+                              std::vector<Palette> const &palettes,

+                              DefaultInitVec<size_t> const &mappings) {

+	// Iterate throughout the image, generating tile data as we go

+	// (We don't need the full tile data to be able to dedup tiles, but we don't lose anything

+	// by caching the full tile data anyway, so we might as well.)

+	UniqueTiles tiles;

+	auto iter = attrmap.begin();

+	for (auto tile : png.visitAsTiles(options.columnMajor)) {

+		auto [tileID, matchType] = tiles.addTile(tile, palettes[mappings[iter->protoPaletteID]]);

+		iter->xFlip = matchType == TileData::HFLIP || matchType == TileData::VHFLIP;

+		iter->yFlip = matchType == TileData::VFLIP || matchType == TileData::VHFLIP;

+		assert(tileID < 1 << 10);

+		iter->tileID = tileID;

+		++iter;

+	}

+	assert(iter == attrmap.end());

+	return tiles; // Copy elision should prevent the contained `unordered_set` from being

+	              // re-constructed

+}

+static void outputTileData(UniqueTiles const &tiles) {

+	std::filebuf output;

+	output.open(options.output, std::ios_base::out | std::ios_base::binary);

+	uint16_t tileID = 0;

+	for (TileData const *tile : tiles) {

+		assert(tile->tileID == tileID);

+		++tileID;

+		output.sputn(reinterpret_cast<char const *>(tile->data().data()), tile->data().size());

+	}

+}

+static void outputTilemap(DefaultInitVec<AttrmapEntry> const &attrmap) {

+	std::filebuf output;

+	output.open(options.tilemap, std::ios_base::out | std::ios_base::binary);

+	assert(options.baseTileIDs[0] == 0 && options.baseTileIDs[1] == 0); // TODO: deal with offset

+	for (AttrmapEntry const &entry : attrmap) {

+		output.sputc(entry.tileID & 0xFF);

+	}

+}

+static void outputAttrmap(DefaultInitVec<AttrmapEntry> const &attrmap,

+                          DefaultInitVec<size_t> const &mappings) {

+	std::filebuf output;

+	output.open(options.attrmap, std::ios_base::out | std::ios_base::binary);

+	assert(options.baseTileIDs[0] == 0 && options.baseTileIDs[1] == 0); // TODO: deal with offset

+	for (AttrmapEntry const &entry : attrmap) {

+		uint8_t attr = entry.xFlip << 5 | entry.yFlip << 6;

+		attr |= (entry.tileID >= options.maxNbTiles[0]) << 3;

+		attr |= mappings[entry.protoPaletteID] & 7;

+		output.sputc(attr);

+	}

+}

+} // namespace optimized

+void process() {

+	options.verbosePrint("Using libpng %s\n", png_get_libpng_ver(nullptr));

+	options.verbosePrint("Reading tiles...\n");

+	Png png(options.input);

+	ImagePalette const &colors = png.getColors();

+	// Now, we have all the image's colors in `colors`

+	// The next step is to order the palette

+	if (options.beVerbose) {

+		options.verbosePrint("Image colors: [ ");

+		size_t i = 0;

+		for (auto const &slot : colors) {

+			if (!slot.has_value()) {

+				continue;

+			}

+			options.verbosePrint("#%02x%02x%02x%02x%s", slot->red, slot->green, slot->blue,

+			                     slot->alpha, i != colors.size() - 1 ? ", " : "");

+			++i;

+		}

+		options.verbosePrint("]\n");

+	}

+	// Now, iterate through the tiles, generating proto-palettes as we go

+	// We do this unconditionally because this performs the image validation (which we want to

+	// perform even if no output is requested), and because it's necessary to generate any

+	// output (with the exception of an un-duplicated tilemap, but that's an acceptable loss.)

+	std::vector<ProtoPalette> protoPalettes;

+	DefaultInitVec<AttrmapEntry> attrmap{};

+	for (auto tile : png.visitAsTiles(options.columnMajor)) {

+		ProtoPalette tileColors;

+		AttrmapEntry &attrs = attrmap.emplace_back();

+		for (uint32_t y = 0; y < 8; ++y) {

+			for (uint32_t x = 0; x < 8; ++x) {

+				tileColors.add(tile.pixel(x, y));

+			}

+		}

+		// Insert the palette, making sure to avoid overlaps

+		// TODO: if inserting (0, 1), (0, 2), and then (0, 1, 2), we might have a problem!

+		for (size_t i = 0; i < protoPalettes.size(); ++i) {

+			switch (tileColors.compare(protoPalettes[i])) {

+			case ProtoPalette::WE_BIGGER:

+				protoPalettes[i] = tileColors; // Override them

+				[[fallthrough]];

+			case ProtoPalette::THEY_BIGGER:

+				// Do nothing, they already contain us

+				attrs.protoPaletteID = i;

+				goto contained;

+			case ProtoPalette::NEITHER:

+				break; // Keep going

+			}

+		}

+		attrs.protoPaletteID = protoPalettes.size();

+		protoPalettes.push_back(tileColors);

+contained:;

+	}

+	options.verbosePrint("Image contains %zu proto-palette%s\n", protoPalettes.size(),

+	                     protoPalettes.size() != 1 ? "s" : "");

+	// Sort the proto-palettes by size, which improves the packing algorithm's efficiency

+	// TODO: try keeping the palettes stored while inserting them instead, might perform better

+	std::sort(

+		protoPalettes.begin(), protoPalettes.end(),

+		[](ProtoPalette const &lhs, ProtoPalette const &rhs) { return lhs.size() < rhs.size(); });

+	// Run a "pagination" problem solver

+	// TODO: allow picking one of several solvers?

+	auto [mappings, nbPalettes] = packing::overloadAndRemove(protoPalettes);

+	assert(mappings.size() == protoPalettes.size());

+	if (options.beVerbose) {

+		options.verbosePrint("Proto-palette mappings: (%zu palettes)\n", nbPalettes);

+		for (size_t i = 0; i < mappings.size(); ++i) {

+			options.verbosePrint("%zu -> %zu\n", i, mappings[i]);

+		}

+	}

+	// TODO: optionally, "decant" the result

+	// Generate the actual palettes from the mappings

+	std::vector<Palette> palettes(nbPalettes);

+	for (size_t protoPalID = 0; protoPalID < mappings.size(); ++protoPalID) {

+		auto &pal = palettes[mappings[protoPalID]];

+		for (uint16_t color : protoPalettes[protoPalID]) {

+			pal.addColor(color);

+		}

+	}

+	// "Sort" colors in the generated palettes, see the man page for the flowchart

+	auto [palSize, palRGB, palAlpha] = png.getEmbeddedPal();

+	if (palRGB) {

+		sorting::indexed(palettes, palSize, palRGB, palAlpha);

+	} else if (png.hasNonGray()) {

+		sorting::rgb(palettes);

+	} else {

+		sorting::grayscale(palettes);

+	}

+	if (options.beVerbose) {

+		for (auto &&palette : palettes) {

+			options.verbosePrint("{ ");

+			for (uint16_t colorIndex : palette) {

+				options.verbosePrint("%04" PRIx16 ", ", colorIndex);

+			}

+			options.verbosePrint("}\n");

+		}

+	}

+	if (!options.palettes.empty()) {

+		outputPalettes(palettes);

+	}

+	// If deduplication is not happening, we just need to output the tile data and/or maps as-is

+	if (!options.allowDedup) {

+		uint32_t const nbTilesH = png.getHeight() / 8, nbTilesW = png.getWidth() / 8;

+		// Check the tile count

+		if (nbTilesW * nbTilesH > options.maxNbTiles[0] + options.maxNbTiles[1]) {

+			fatal("Image contains %" PRIu32 " tiles, exceeding the limit of %" PRIu16 " + %" PRIu16,

+			      nbTilesW * nbTilesH, options.maxNbTiles[0], options.maxNbTiles[1]);

+		}

+		if (!options.output.empty()) {

+			options.verbosePrint("Generating unoptimized tile data...\n");

+			unoptimized::outputTileData(png, attrmap, palettes, mappings);

+		}

+		if (!options.tilemap.empty() || !options.attrmap.empty()) {

+			options.verbosePrint("Generating unoptimized tilemap and/or attrmap...\n");

+			unoptimized::outputMaps(png, attrmap, mappings);

+		}

+	} else {

+		// All of these require the deduplication process to be performed to be output

+		options.verbosePrint("Deduplicating tiles...\n");

+		optimized::UniqueTiles tiles = optimized::dedupTiles(png, attrmap, palettes, mappings);

+		if (tiles.size() > options.maxNbTiles[0] + options.maxNbTiles[1]) {

+			fatal("Image contains %zu tiles, exceeding the limit of %" PRIu16 " + %" PRIu16,

+			      tiles.size(), options.maxNbTiles[0], options.maxNbTiles[1]);

+		}

+		if (!options.output.empty()) {

+			options.verbosePrint("Generating optimized tile data...\n");

+			optimized::outputTileData(tiles);

+		}

+		if (!options.tilemap.empty()) {

+			options.verbosePrint("Generating optimized tilemap...\n");

+			optimized::outputTilemap(attrmap);

+		}

+		if (!options.attrmap.empty()) {

+			options.verbosePrint("Generating optimized attrmap...\n");

+			optimized::outputAttrmap(attrmap, mappings);

+		}

+	}

+}

--- a/src/gfx/gb.c

+++ /dev/null

@@ -1,385 +1,0 @@

-/*

- * This file is part of RGBDS.

- *

- * Copyright (c) 2013-2018, stag019 and RGBDS contributors.

- *

- * SPDX-License-Identifier: MIT

- */

-#include <stdint.h>

-#include <stdio.h>

-#include <stdlib.h>

-#include "gfx/gb.h"

-void transpose_tiles(struct GBImage *gb, int width)

-{

-	uint8_t *newdata;

-	int i;

-	int newbyte;

-	newdata = calloc(gb->size, 1);

-	if (!newdata)

-		err("%s: Failed to allocate memory for new data", __func__);

-	for (i = 0; i < gb->size; i++) {

-		newbyte = i / (8 * depth) * width * 8 * depth;

-		newbyte = newbyte % gb->size

-			+ 8 * depth * (newbyte / gb->size)

-			+ i % (8 * depth);

-		newdata[newbyte] = gb->data[i];

-	}

-	free(gb->data);

-	gb->data = newdata;

-}

-void raw_to_gb(const struct RawIndexedImage *raw_image, struct GBImage *gb)

-{

-	uint8_t index;

-	for (unsigned int y = 0; y < raw_image->height; y++) {

-		for (unsigned int x = 0; x < raw_image->width; x++) {

-			index = raw_image->data[y][x];

-			index &= (1 << depth) - 1;

-			unsigned int byte = y * depth

-				+ x / 8 * raw_image->height / 8 * 8 * depth;

-			gb->data[byte] |= (index & 1) << (7 - x % 8);

-			if (depth == 2) {

-				gb->data[byte + 1] |=

-					(index >> 1) << (7 - x % 8);

-			}

-		}

-	}

-	if (!gb->horizontal)

-		transpose_tiles(gb, raw_image->width / 8);

-}

-void output_file(const struct Options *opts, const struct GBImage *gb)

-{

-	FILE *f;

-	f = fopen(opts->outfile, "wb");

-	if (!f)

-		err("%s: Opening output file '%s' failed", __func__,

-		    opts->outfile);

-	fwrite(gb->data, 1, gb->size - gb->trim * 8 * depth, f);

-	fclose(f);

-}

-int get_tile_index(uint8_t *tile, uint8_t **tiles, int num_tiles, int tile_size)

-{

-	int i, j;

-	for (i = 0; i < num_tiles; i++) {

-		for (j = 0; j < tile_size; j++) {

-			if (tile[j] != tiles[i][j])

-				break;

-		}

-		if (j >= tile_size)

-			return i;

-	}

-	return -1;

-}

-uint8_t reverse_bits(uint8_t b)

-{

-	uint8_t rev = 0;

-	rev |= (b & 0x80) >> 7;

-	rev |= (b & 0x40) >> 5;

-	rev |= (b & 0x20) >> 3;

-	rev |= (b & 0x10) >> 1;

-	rev |= (b & 0x08) << 1;

-	rev |= (b & 0x04) << 3;

-	rev |= (b & 0x02) << 5;

-	rev |= (b & 0x01) << 7;

-	return rev;

-}

-void xflip(uint8_t *tile, uint8_t *tile_xflip, int tile_size)

-{

-	int i;

-	for (i = 0; i < tile_size; i++)

-		tile_xflip[i] = reverse_bits(tile[i]);

-}

-void yflip(uint8_t *tile, uint8_t *tile_yflip, int tile_size)

-{

-	int i;

-	for (i = 0; i < tile_size; i++)

-		tile_yflip[i] = tile[(tile_size - i - 1) ^ (depth - 1)];

-}

-/*

- * get_mirrored_tile_index looks for `tile` in tile array `tiles`, also

- * checking x-, y-, and xy-mirrored versions of `tile`. If one is found,

- * `*flags` is set according to the type of mirroring and the index of the

- * matched tile is returned. If no match is found, -1 is returned.

- */

-int get_mirrored_tile_index(uint8_t *tile, uint8_t **tiles, int num_tiles,

-			    int tile_size, int *flags)

-{

-	int index;

-	uint8_t *tile_xflip;

-	uint8_t *tile_yflip;

-	index = get_tile_index(tile, tiles, num_tiles, tile_size);

-	if (index >= 0) {

-		*flags = 0;

-		return index;

-	}

-	tile_yflip = malloc(tile_size);

-	if (!tile_yflip)

-		err("%s: Failed to allocate memory for Y flip of tile",

-		    __func__);

-	yflip(tile, tile_yflip, tile_size);

-	index = get_tile_index(tile_yflip, tiles, num_tiles, tile_size);

-	if (index >= 0) {

-		*flags = YFLIP;

-		free(tile_yflip);

-		return index;

-	}

-	tile_xflip = malloc(tile_size);

-	if (!tile_xflip)

-		err("%s: Failed to allocate memory for X flip of tile",

-		    __func__);

-	xflip(tile, tile_xflip, tile_size);

-	index = get_tile_index(tile_xflip, tiles, num_tiles, tile_size);

-	if (index >= 0) {

-		*flags = XFLIP;

-		free(tile_yflip);

-		free(tile_xflip);

-		return index;

-	}

-	yflip(tile_xflip, tile_yflip, tile_size);

-	index = get_tile_index(tile_yflip, tiles, num_tiles, tile_size);

-	if (index >= 0)

-		*flags = XFLIP | YFLIP;

-	free(tile_yflip);

-	free(tile_xflip);

-	return index;

-}

-void create_mapfiles(const struct Options *opts, struct GBImage *gb,

-		     struct Mapfile *tilemap, struct Mapfile *attrmap)

-{

-	int i, j;

-	int gb_i;

-	int tile_size;

-	int max_tiles;

-	int num_tiles;

-	int index;

-	int flags;

-	int gb_size;

-	uint8_t *tile;

-	uint8_t **tiles;

-	tile_size = sizeof(*tile) * depth * 8;

-	gb_size = gb->size - (gb->trim * tile_size);

-	max_tiles = gb_size / tile_size;

-	/* If the input image doesn't fill the last tile, increase the count. */

-	if (gb_size > max_tiles * tile_size)

-		max_tiles++;

-	tiles = calloc(max_tiles, sizeof(*tiles));

-	if (!tiles)

-		err("%s: Failed to allocate memory for tiles", __func__);

-	num_tiles = 0;

-	if (*opts->tilemapfile) {

-		tilemap->data = calloc(max_tiles, sizeof(*tilemap->data));

-		if (!tilemap->data)

-			err("%s: Failed to allocate memory for tilemap data",

-			    __func__);

-		tilemap->size = 0;

-	}

-	if (*opts->attrmapfile) {

-		attrmap->data = calloc(max_tiles, sizeof(*attrmap->data));

-		if (!attrmap->data)

-			err("%s: Failed to allocate memory for attrmap data",

-			    __func__);

-		attrmap->size = 0;

-	}

-	gb_i = 0;

-	while (gb_i < gb_size) {

-		flags = 0;

-		tile = malloc(tile_size);

-		if (!tile)

-			err("%s: Failed to allocate memory for tile",

-			    __func__);

-		/*

-		 * If the input image doesn't fill the last tile,

-		 * `gb_i` will reach `gb_size`.

-		 */

-		for (i = 0; i < tile_size && gb_i < gb_size; i++) {

-			tile[i] = gb->data[gb_i];

-			gb_i++;

-		}

-		if (opts->unique) {

-			if (opts->mirror) {

-				index = get_mirrored_tile_index(tile, tiles,

-								num_tiles,

-								tile_size,

-								&flags);

-			} else {

-				index = get_tile_index(tile, tiles, num_tiles,

-						       tile_size);

-			}

-			if (index < 0) {

-				index = num_tiles;

-				tiles[num_tiles] = tile;

-				num_tiles++;

-			} else {

-				free(tile);

-			}

-		} else {

-			index = num_tiles;

-			tiles[num_tiles] = tile;

-			num_tiles++;

-		}

-		if (*opts->tilemapfile) {

-			tilemap->data[tilemap->size] = index;

-			tilemap->size++;

-		}

-		if (*opts->attrmapfile) {

-			attrmap->data[attrmap->size] = flags;

-			attrmap->size++;

-		}

-	}

-	if (opts->unique) {

-		free(gb->data);

-		gb->data = malloc(tile_size * num_tiles);

-		if (!gb->data)

-			err("%s: Failed to allocate memory for tile data",

-			    __func__);

-		for (i = 0; i < num_tiles; i++) {

-			tile = tiles[i];

-			for (j = 0; j < tile_size; j++)

-				gb->data[i * tile_size + j] = tile[j];

-		}

-		gb->size = i * tile_size;

-	}

-	for (i = 0; i < num_tiles; i++)

-		free(tiles[i]);

-	free(tiles);

-}

-void output_tilemap_file(const struct Options *opts,

-			 const struct Mapfile *tilemap)

-{

-	FILE *f;

-	f = fopen(opts->tilemapfile, "wb");

-	if (!f)

-		err("%s: Opening tilemap file '%s' failed", __func__,

-		    opts->tilemapfile);

-	fwrite(tilemap->data, 1, tilemap->size, f);

-	fclose(f);

-	if (opts->tilemapout)

-		free(opts->tilemapfile);

-}

-void output_attrmap_file(const struct Options *opts,

-			 const struct Mapfile *attrmap)

-{

-	FILE *f;

-	f = fopen(opts->attrmapfile, "wb");

-	if (!f)

-		err("%s: Opening attrmap file '%s' failed", __func__,

-		    opts->attrmapfile);

-	fwrite(attrmap->data, 1, attrmap->size, f);

-	fclose(f);

-	if (opts->attrmapout)

-		free(opts->attrmapfile);

-}

-/*

- * based on the Gaussian-like curve used by SameBoy since commit

- * 65dd02cc52f531dbbd3a7e6014e99d5b24e71a4c (Oct 2017)

- * with ties resolved by comparing the difference of the squares.

- */

-static int reverse_curve[] = {

-	0,  0,  1,  1,  2,  2,  3,  3,  3,  3,  4,  4,  4,  4,  4,  4,

-	5,  5,  5,  5,  5,  5,  6,  6,  6,  6,  6,  6,  6,  6,  7,  7,

-	7,  7,  7,  7,  7,  7,  7,  8,  8,  8,  8,  8,  8,  8,  8,  8,

-	9,  9,  9,  9,  9,  9,  9,  9,  9,  9,  10, 10, 10, 10, 10, 10,

-	10, 10, 10, 10, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11,

-	12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 13, 13, 13, 13,

-	13, 13, 13, 13, 13, 13, 13, 13, 14, 14, 14, 14, 14, 14, 14, 14,

-	14, 14, 14, 14, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15,

-	16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 17, 17, 17,

-	17, 17, 17, 17, 17, 17, 17, 17, 17, 18, 18, 18, 18, 18, 18, 18,

-	18, 18, 18, 18, 18, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19,

-	19, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 21, 21, 21, 21,

-	21, 21, 21, 21, 21, 21, 21, 22, 22, 22, 22, 22, 22, 22, 22, 22,

-	22, 23, 23, 23, 23, 23, 23, 23, 23, 23, 24, 24, 24, 24, 24, 24,

-	24, 24, 25, 25, 25, 25, 25, 25, 25, 25, 26, 26, 26, 26, 26, 26,

-	26, 27, 27, 27, 27, 27, 28, 28, 28, 28, 29, 29, 29, 30, 30, 31,

-};

-void output_palette_file(const struct Options *opts,

-			 const struct RawIndexedImage *raw_image)

-{

-	FILE *f;

-	int i, color;

-	uint8_t cur_bytes[2];

-	f = fopen(opts->palfile, "wb");

-	if (!f)

-		err("%s: Opening palette file '%s' failed", __func__,

-		    opts->palfile);

-	for (i = 0; i < raw_image->num_colors; i++) {

-		int r = raw_image->palette[i].red;

-		int g = raw_image->palette[i].green;

-		int b = raw_image->palette[i].blue;

-		if (opts->colorcurve) {

-			g = (g * 4 - b) / 3;

-			if (g < 0)

-				g = 0;

-			r = reverse_curve[r];

-			g = reverse_curve[g];

-			b = reverse_curve[b];

-		} else {

-			r >>= 3;

-			g >>= 3;

-			b >>= 3;

-		}

-		color = b << 10 | g << 5 | r;

-		cur_bytes[0] = color & 0xFF;

-		cur_bytes[1] = color >> 8;

-		fwrite(cur_bytes, 2, 1, f);

-	}

-	fclose(f);

-	if (opts->palout)

-		free(opts->palfile);

-}

--- a/src/gfx/main.c

+++ /dev/null

@@ -1,358 +1,0 @@

-/*

- * This file is part of RGBDS.

- *

- * Copyright (c) 2013-2018, stag019 and RGBDS contributors.

- *

- * SPDX-License-Identifier: MIT

- */

-#include <png.h>

-#include <stdlib.h>

-#include <string.h>

-#include "gfx/main.h"

-#include "extern/getopt.h"

-#include "version.h"

-int depth, colors;

-/* Short options */

-static char const *optstring = "Aa:CDd:Ffhmo:Pp:Tt:uVvx:";

-/*

- * Equivalent long options

- * Please keep in the same order as short opts

- *

- * Also, make sure long opts don't create ambiguity:

- * A long opt's name should start with the same letter as its short opt,

- * except if it doesn't create any ambiguity (`verbose` versus `version`).

- * This is because long opt matching, even to a single char, is prioritized

- * over short opt matching

- */

-static struct option const longopts[] = {

-	{ "output-attr-map", no_argument,       NULL, 'A' },

-	{ "attr-map",        required_argument, NULL, 'a' },

-	{ "color-curve",     no_argument,       NULL, 'C' },

-	{ "debug",           no_argument,       NULL, 'D' },

-	{ "depth",           required_argument, NULL, 'd' },

-	{ "fix",             no_argument,       NULL, 'f' },

-	{ "fix-and-save",    no_argument,       NULL, 'F' },

-	{ "horizontal",      no_argument,       NULL, 'h' },

-	{ "mirror-tiles",    no_argument,       NULL, 'm' },

-	{ "output",          required_argument, NULL, 'o' },

-	{ "output-palette",  no_argument,       NULL, 'P' },

-	{ "palette",         required_argument, NULL, 'p' },

-	{ "output-tilemap",  no_argument,       NULL, 'T' },

-	{ "tilemap",         required_argument, NULL, 't' },

-	{ "unique-tiles",    no_argument,       NULL, 'u' },

-	{ "version",         no_argument,       NULL, 'V' },

-	{ "verbose",         no_argument,       NULL, 'v' },

-	{ "trim-end",        required_argument, NULL, 'x' },

-	{ NULL,              no_argument,       NULL, 0   }

-};

-static void print_usage(void)

-{

-	fputs(

-"Usage: rgbgfx [-CDhmuVv] [-f | -F] [-a <attr_map> | -A] [-d <depth>]\n"

-"              [-o <out_file>] [-p <pal_file> | -P] [-t <tile_map> | -T]\n"

-"              [-x <tiles>] <file>\n"

-"Useful options:\n"

-"    -f, --fix                 make the input image an indexed PNG\n"

-"    -m, --mirror-tiles        optimize out mirrored tiles\n"

-"    -o, --output <path>       set the output binary file\n"

-"    -t, --tilemap <path>      set the output tilemap file\n"

-"    -u, --unique-tiles        optimize out identical tiles\n"

-"    -V, --version             print RGBGFX version and exit\n"

-"\n"

-"For help, use `man rgbgfx' or go to https://rgbds.gbdev.io/docs/\n",

-	      stderr);

-	exit(1);

-}

-int main(int argc, char *argv[])

-{

-	int ch, size;

-	struct Options opts = {0};

-	struct ImageOptions png_options = {0};

-	struct RawIndexedImage *raw_image;

-	struct GBImage gb = {0};

-	struct Mapfile tilemap = {0};

-	struct Mapfile attrmap = {0};

-	char *ext;

-	opts.tilemapfile = "";

-	opts.attrmapfile = "";

-	opts.palfile = "";

-	opts.outfile = "";

-	depth = 2;

-	while ((ch = musl_getopt_long_only(argc, argv, optstring, longopts,

-					   NULL)) != -1) {

-		switch (ch) {

-		case 'A':

-			opts.attrmapout = true;

-			break;

-		case 'a':

-			opts.attrmapfile = musl_optarg;

-			break;

-		case 'C':

-			opts.colorcurve = true;

-			break;

-		case 'D':

-			opts.debug = true;

-			break;

-		case 'd':

-			depth = strtoul(musl_optarg, NULL, 0);

-			break;

-		case 'F':

-			opts.hardfix = true;

-			/* fallthrough */

-		case 'f':

-			opts.fix = true;

-			break;

-		case 'h':

-			opts.horizontal = true;

-			break;

-		case 'm':

-			opts.mirror = true;

-			opts.unique = true;

-			break;

-		case 'o':

-			opts.outfile = musl_optarg;

-			break;

-		case 'P':

-			opts.palout = true;

-			break;

-		case 'p':

-			opts.palfile = musl_optarg;

-			break;

-		case 'T':

-			opts.tilemapout = true;

-			break;

-		case 't':

-			opts.tilemapfile = musl_optarg;

-			break;

-		case 'u':

-			opts.unique = true;

-			break;

-		case 'V':

-			printf("rgbgfx %s\n", get_package_version_string());

-			exit(0);

-		case 'v':

-			opts.verbose = true;

-			break;

-		case 'x':

-			opts.trim = strtoul(musl_optarg, NULL, 0);

-			break;

-		default:

-			print_usage();

-			/* NOTREACHED */

-		}

-	}

-	argc -= musl_optind;

-	argv += musl_optind;

-	if (argc == 0) {

-		fputs("FATAL: no input files\n", stderr);

-		print_usage();

-	}

-#define WARN_MISMATCH(property) \

-	warnx("The PNG's " property \

-	      " setting doesn't match the one defined on the command line")

-	opts.infile = argv[argc - 1];

-	if (depth != 1 && depth != 2)

-		errx("Depth option must be either 1 or 2.");

-	colors = 1 << depth;

-	raw_image = input_png_file(&opts, &png_options);

-	png_options.tilemapfile = "";

-	png_options.attrmapfile = "";

-	png_options.palfile = "";

-	if (png_options.horizontal != opts.horizontal) {

-		if (opts.verbose)

-			WARN_MISMATCH("horizontal");

-		if (opts.hardfix)

-			png_options.horizontal = opts.horizontal;

-	}

-	if (png_options.horizontal)

-		opts.horizontal = png_options.horizontal;

-	if (png_options.trim != opts.trim) {

-		if (opts.verbose)

-			WARN_MISMATCH("trim");

-		if (opts.hardfix)

-			png_options.trim = opts.trim;

-	}

-	if (png_options.trim)

-		opts.trim = png_options.trim;

-	if (raw_image->width % 8) {

-		errx("Input PNG file %s not sized correctly. The image's width must be a multiple of 8.",

-		     opts.infile);

-	}

-	if (raw_image->width / 8 > 1 && raw_image->height % 8) {

-		errx("Input PNG file %s not sized correctly. If the image is more than 1 tile wide, its height must be a multiple of 8.",

-		     opts.infile);

-	}

-	if (opts.trim &&

-	    opts.trim > (raw_image->width / 8) * (raw_image->height / 8) - 1) {

-		errx("Trim (%d) for input raw_image file '%s' too large (max: %u)",

-		     opts.trim, opts.infile,

-		     (raw_image->width / 8) * (raw_image->height / 8) - 1);

-	}

-	if (strcmp(png_options.tilemapfile, opts.tilemapfile) != 0) {

-		if (opts.verbose)

-			WARN_MISMATCH("tilemap file");

-		if (opts.hardfix)

-			png_options.tilemapfile = opts.tilemapfile;

-	}

-	if (!*opts.tilemapfile)

-		opts.tilemapfile = png_options.tilemapfile;

-	if (png_options.tilemapout != opts.tilemapout) {

-		if (opts.verbose)

-			WARN_MISMATCH("tilemap file");

-		if (opts.hardfix)

-			png_options.tilemapout = opts.tilemapout;

-	}

-	if (png_options.tilemapout)

-		opts.tilemapout = png_options.tilemapout;

-	if (strcmp(png_options.attrmapfile, opts.attrmapfile) != 0) {

-		if (opts.verbose)

-			WARN_MISMATCH("attrmap file");

-		if (opts.hardfix)

-			png_options.attrmapfile = opts.attrmapfile;

-	}

-	if (!*opts.attrmapfile)

-		opts.attrmapfile = png_options.attrmapfile;

-	if (png_options.attrmapout != opts.attrmapout) {

-		if (opts.verbose)

-			WARN_MISMATCH("attrmap file");

-		if (opts.hardfix)

-			png_options.attrmapout = opts.attrmapout;

-	}

-	if (png_options.attrmapout)

-		opts.attrmapout = png_options.attrmapout;

-	if (strcmp(png_options.palfile, opts.palfile) != 0) {

-		if (opts.verbose)

-			WARN_MISMATCH("palette file");

-		if (opts.hardfix)

-			png_options.palfile = opts.palfile;

-	}

-	if (!*opts.palfile)

-		opts.palfile = png_options.palfile;

-	if (png_options.palout != opts.palout) {

-		if (opts.verbose)

-			WARN_MISMATCH("palette file");

-		if (opts.hardfix)

-			png_options.palout = opts.palout;

-	}

-#undef WARN_MISMATCH

-	if (png_options.palout)

-		opts.palout = png_options.palout;

-	if (!*opts.tilemapfile && opts.tilemapout) {

-		ext = strrchr(opts.infile, '.');

-		if (ext != NULL) {

-			size = ext - opts.infile + 9;

-			opts.tilemapfile = malloc(size);

-			strncpy(opts.tilemapfile, opts.infile, size);

-			*strrchr(opts.tilemapfile, '.') = '\0';

-			strcat(opts.tilemapfile, ".tilemap");

-		} else {

-			opts.tilemapfile = malloc(strlen(opts.infile) + 9);

-			strcpy(opts.tilemapfile, opts.infile);

-			strcat(opts.tilemapfile, ".tilemap");

-		}

-	}

-	if (!*opts.attrmapfile && opts.attrmapout) {

-		ext = strrchr(opts.infile, '.');

-		if (ext != NULL) {

-			size = ext - opts.infile + 9;

-			opts.attrmapfile = malloc(size);

-			strncpy(opts.attrmapfile, opts.infile, size);

-			*strrchr(opts.attrmapfile, '.') = '\0';

-			strcat(opts.attrmapfile, ".attrmap");

-		} else {

-			opts.attrmapfile = malloc(strlen(opts.infile) + 9);

-			strcpy(opts.attrmapfile, opts.infile);

-			strcat(opts.attrmapfile, ".attrmap");

-		}

-	}

-	if (!*opts.palfile && opts.palout) {

-		ext = strrchr(opts.infile, '.');

-		if (ext != NULL) {

-			size = ext - opts.infile + 5;

-			opts.palfile = malloc(size);

-			strncpy(opts.palfile, opts.infile, size);

-			*strrchr(opts.palfile, '.') = '\0';

-			strcat(opts.palfile, ".pal");

-		} else {

-			opts.palfile = malloc(strlen(opts.infile) + 5);

-			strcpy(opts.palfile, opts.infile);

-			strcat(opts.palfile, ".pal");

-		}

-	}

-	gb.size = raw_image->width * raw_image->height * depth / 8;

-	gb.data = calloc(gb.size, 1);

-	gb.trim = opts.trim;

-	gb.horizontal = opts.horizontal;

-	if (*opts.outfile || *opts.tilemapfile || *opts.attrmapfile) {

-		raw_to_gb(raw_image, &gb);

-		create_mapfiles(&opts, &gb, &tilemap, &attrmap);

-	}

-	if (*opts.outfile)

-		output_file(&opts, &gb);

-	if (*opts.tilemapfile)

-		output_tilemap_file(&opts, &tilemap);

-	if (*opts.attrmapfile)

-		output_attrmap_file(&opts, &attrmap);

-	if (*opts.palfile)

-		output_palette_file(&opts, raw_image);

-	if (opts.fix || opts.debug)

-		output_png_file(&opts, &png_options, raw_image);

-	destroy_raw_image(&raw_image);

-	free(gb.data);

-	return 0;

-}

--- /dev/null

+++ b/src/gfx/main.cpp

@@ -1,0 +1,321 @@

+/*

+ * This file is part of RGBDS.

+ *

+ * Copyright (c) 2022, Eldred Habert and RGBDS contributors.

+ *

+ * SPDX-License-Identifier: MIT

+ */

+#include "gfx/main.hpp"

+#include <algorithm>

+#include <assert.h>

+#include <charconv>

+#include <filesystem>

+#include <inttypes.h>

+#include <limits>

+#include <stdarg.h>

+#include <stdint.h>

+#include <stdio.h>

+#include <stdlib.h>

+#include <string.h>

+#include "extern/getopt.h"

+#include "version.h"

+#include "gfx/convert.hpp"

+Options options;

+static uintmax_t nbErrors;

+void warning(char const *fmt, ...) {

+	va_list ap;

+	fputs("warning: ", stderr);

+	va_start(ap, fmt);

+	vfprintf(stderr, fmt, ap);

+	va_end(ap);

+	putc('\n', stderr);

+}

+void error(char const *fmt, ...) {

+	va_list ap;

+	fputs("error: ", stderr);

+	va_start(ap, fmt);

+	vfprintf(stderr, fmt, ap);

+	va_end(ap);

+	putc('\n', stderr);

+	if (nbErrors != std::numeric_limits<decltype(nbErrors)>::max())

+		nbErrors++;

+}

+[[noreturn]] void fatal(char const *fmt, ...) {

+	va_list ap;

+	fputs("FATAL: ", stderr);

+	va_start(ap, fmt);

+	vfprintf(stderr, fmt, ap);

+	va_end(ap);

+	putc('\n', stderr);

+	if (nbErrors != std::numeric_limits<decltype(nbErrors)>::max())

+		nbErrors++;

+	fprintf(stderr, "Conversion aborted after %ju error%s\n", nbErrors, nbErrors == 1 ? "" : "s");

+	exit(1);

+}

+void Options::verbosePrint(char const *fmt, ...) const {

+	if (beVerbose) {

+		va_list ap;

+		va_start(ap, fmt);

+		vfprintf(stderr, fmt, ap);

+		va_end(ap);

+	}

+}

+// Short options

+static char const *optstring = "Aa:CDd:Ffhmo:Pp:Tt:uVvx:";

+/*

+ * Equivalent long options

+ * Please keep in the same order as short opts

+ *

+ * Also, make sure long opts don't create ambiguity:

+ * A long opt's name should start with the same letter as its short opt,

+ * except if it doesn't create any ambiguity (`verbose` versus `version`).

+ * This is because long opt matching, even to a single char, is prioritized

+ * over short opt matching

+ */

+static struct option const longopts[] = {

+	{"output-attr-map", no_argument,       NULL, 'A'},

+	{"attr-map",        required_argument, NULL, 'a'},

+	{"color-curve",     no_argument,       NULL, 'C'},

+	{"debug",           no_argument,       NULL, 'D'},

+	{"depth",           required_argument, NULL, 'd'},

+	{"fix",             no_argument,       NULL, 'f'},

+	{"fix-and-save",    no_argument,       NULL, 'F'},

+	{"horizontal",      no_argument,       NULL, 'h'},

+	{"mirror-tiles",    no_argument,       NULL, 'm'},

+	{"output",          required_argument, NULL, 'o'},

+	{"output-palette",  no_argument,       NULL, 'P'},

+	{"palette",         required_argument, NULL, 'p'},

+	{"output-tilemap",  no_argument,       NULL, 'T'},

+	{"tilemap",         required_argument, NULL, 't'},

+	{"unique-tiles",    no_argument,       NULL, 'u'},

+	{"version",         no_argument,       NULL, 'V'},

+	{"verbose",         no_argument,       NULL, 'v'},

+	{"trim-end",        required_argument, NULL, 'x'},

+	{NULL,              no_argument,       NULL, 0  }

+};

+static void print_usage(void) {

+	fputs("Usage: rgbgfx [-CDhmuVv] [-f | -F] [-a <attr_map> | -A] [-d <depth>]\n"

+	      "	      [-o <out_file>] [-p <pal_file> | -P] [-t <tile_map> | -T]\n"

+	      "	      [-x <tiles>] <file>\n"

+	      "Useful options:\n"

+	      "    -f, --fix		 make the input image an indexed PNG\n"

+	      "    -m, --mirror-tiles	optimize out mirrored tiles\n"

+	      "    -o, --output <path>       set the output binary file\n"

+	      "    -t, --tilemap <path>      set the output tilemap file\n"

+	      "    -u, --unique-tiles	optimize out identical tiles\n"

+	      "    -V, --version	     print RGBGFX version and exit\n"

+	      "\n"

+	      "For help, use `man rgbgfx' or go to https://rgbds.gbdev.io/docs/\n",

+	      stderr);

+	exit(1);

+}

+void fputsv(std::string_view const &view, FILE *f) {

+	if (view.data()) {

+		fwrite(view.data(), sizeof(char), view.size(), f);

+	}

+}

+int main(int argc, char *argv[]) {

+	int opt;

+	bool autoAttrmap = false, autoTilemap = false, autoPalettes = false;

+	auto parseDecimalArg = [&opt](auto &out) {

+		char const *end = &musl_optarg[strlen(musl_optarg)];

+		// `options.bitDepth` is not modified if the parse fails entirely

+		auto result = std::from_chars(musl_optarg, end, out, 10);

+		if (result.ec == std::errc::result_out_of_range) {

+			error("Argument to option '%c' (\"%s\") is out of range", opt, musl_optarg);

+			return false;

+		} else if (result.ptr != end) {

+			error("Invalid argument to option '%c' (\"%s\")", opt, musl_optarg);

+			return false;

+		}

+		return true;

+	};

+	while ((opt = musl_getopt_long_only(argc, argv, optstring, longopts, nullptr)) != -1) {

+		switch (opt) {

+		case 'A':

+			autoAttrmap = true;

+			break;

+		case 'a':

+			autoAttrmap = false;

+			options.attrmap = musl_optarg;

+			break;

+		case 'C':

+			options.useColorCurve = true;

+			break;

+		case 'd':

+			if (parseDecimalArg(options.bitDepth) && options.bitDepth != 1

+			    && options.bitDepth != 2) {

+				error("Bit depth must be 1 or 2, not %" PRIu8 "");

+				options.bitDepth = 2;

+			}

+			break;

+		case 'f':

+			options.fixInput = true;

+			break;

+		case 'h':

+			warning("`-h` is deprecated, use `-???` instead");

+			[[fallthrough]];

+		case '?': // TODO

+			options.columnMajor = true;

+			break;

+		case 'm':

+			options.allowMirroring = true;

+			[[fallthrough]]; // Imply `-u`

+		case 'u':

+			options.allowDedup = true;

+			break;

+		case 'o':

+			options.output = musl_optarg;

+			break;

+		case 'P':

+			autoPalettes = true;

+			break;

+		case 'p':

+			autoPalettes = false;

+			options.palettes = musl_optarg;

+			break;

+		case 'T':

+			autoTilemap = true;

+			break;

+		case 't':

+			autoTilemap = false;

+			options.tilemap = musl_optarg;

+			break;

+		case 'V':

+			printf("rgbgfx %s\n", get_package_version_string());

+			exit(0);

+		case 'v':

+			options.beVerbose = true;

+			break;

+		case 'x':

+			parseDecimalArg(options.trim);

+			break;

+		case 'D':

+		case 'F':

+			warning("Ignoring option '%c'", musl_optopt);

+			break;

+		default:

+			print_usage();

+			exit(1);

+		}

+	}

+	if (options.nbColorsPerPal == 0) {

+		options.nbColorsPerPal = 1 << options.bitDepth;

+	} else if (options.nbColorsPerPal > 1u << options.bitDepth) {

+		error("%" PRIu8 "bpp palettes can only contain %u colors, not %" PRIu8, options.bitDepth,

+		      1u << options.bitDepth, options.nbColorsPerPal);

+	}

+	if (musl_optind == argc) {

+		fputs("FATAL: No input image specified\n", stderr);

+		print_usage();

+		exit(1);

+	} else if (argc - musl_optind != 1) {

+		fprintf(stderr, "FATAL: %d input images were specified instead of 1\n", argc - musl_optind);

+		print_usage();

+		exit(1);

+	}

+	options.input = argv[argc - 1];

+	auto autoOutPath = [](bool autoOptEnabled, std::filesystem::path &path, char const *extension) {

+		if (autoOptEnabled) {

+			path = options.input;

+			path.replace_extension(extension);

+		}

+	};

+	autoOutPath(autoAttrmap, options.attrmap, ".attrmap");

+	autoOutPath(autoTilemap, options.tilemap, ".tilemap");

+	autoOutPath(autoPalettes, options.palettes, ".pal");

+	if (options.beVerbose) {

+		fprintf(stderr, "rgbgfx %s\n", get_package_version_string());

+		fputs("Options:\n", stderr);

+		if (options.fixInput)

+			fputs("\tConvert input to indexed\n", stderr);

+		if (options.columnMajor)

+			fputs("\tOutput {tile,attr}map in column-major order\n", stderr);

+		if (options.allowMirroring)

+			fputs("\tAllow mirroring tiles\n", stderr);

+		if (options.allowDedup)

+			fputs("\tAllow deduplicating tiles\n", stderr);

+		if (options.useColorCurve)

+			fputs("\tUse color curve\n", stderr);

+		fprintf(stderr, "\tBit depth: %" PRIu8 "bpp\n", options.bitDepth);

+		fprintf(stderr, "\tTrim the last %" PRIu64 " tiles\n", options.trim);

+		fprintf(stderr, "\tBase tile IDs: [%" PRIu8 ", %" PRIu8 "]\n", options.baseTileIDs[0],

+		        options.baseTileIDs[1]);

+		fprintf(stderr, "\tMax number of tiles: [%" PRIu16 ", %" PRIu16 "]\n",

+		        options.maxNbTiles[0], options.maxNbTiles[1]);

+		auto printPath = [](char const *name, std::filesystem::path const &path) {

+			if (!path.empty()) {

+				fprintf(stderr, "\t%s: %s\n", name, path.c_str());

+			}

+		};

+		printPath("Input image", options.input);

+		printPath("Output tile data", options.output);

+		printPath("Output tilemap", options.tilemap);

+		printPath("Output attrmap", options.attrmap);

+		printPath("Output palettes", options.palettes);

+		fputs("Ready.\n", stderr);

+	}

+	process();

+	return 0;

+}

+void Palette::addColor(uint16_t color) {

+	for (size_t i = 0; true; ++i) {

+		assert(i < colors.size()); // The packing should guarantee this

+		if (colors[i] == color) { // The color is already present

+			break;

+		} else if (colors[i] == UINT16_MAX) { // Empty slot

+			colors[i] = color;

+			break;

+		}

+	}

+}

+uint8_t Palette::indexOf(uint16_t color) const {

+	return std::distance(colors.begin(), std::find(colors.begin(), colors.end(), color));

+}

+auto Palette::begin() -> decltype(colors)::iterator {

+	return colors.begin();

+}

+auto Palette::end() -> decltype(colors)::iterator {

+	return std::find(colors.begin(), colors.end(), UINT16_MAX);

+}

+auto Palette::begin() const -> decltype(colors)::const_iterator {

+	return colors.begin();

+}

+auto Palette::end() const -> decltype(colors)::const_iterator {

+	return std::find(colors.begin(), colors.end(), UINT16_MAX);

+}

--- a/src/gfx/makepng.c

+++ /dev/null

@@ -1,806 +1,0 @@

-/*

- * This file is part of RGBDS.

- *

- * Copyright (c) 2013-2018, stag019 and RGBDS contributors.

- *

- * SPDX-License-Identifier: MIT

- */

-#include <png.h>

-#include <stdio.h>

-#include <stdlib.h>

-#include <string.h>

-#include "gfx/makepng.h"

-static void initialize_png(struct PNGImage *img, FILE * f);

-static struct RawIndexedImage *indexed_png_to_raw(struct PNGImage *img);

-static struct RawIndexedImage *grayscale_png_to_raw(struct PNGImage *img);

-static struct RawIndexedImage *truecolor_png_to_raw(struct PNGImage *img);

-static void get_text(const struct PNGImage *img,

-		     struct ImageOptions *png_options);

-static void set_text(const struct PNGImage *img,

-		     const struct ImageOptions *png_options);

-static void free_png_data(const struct PNGImage *png);

-struct RawIndexedImage *input_png_file(const struct Options *opts,

-				       struct ImageOptions *png_options)

-{

-	struct PNGImage img;

-	struct RawIndexedImage *raw_image;

-	FILE *f;

-	f = fopen(opts->infile, "rb");

-	if (!f)

-		err("Opening input png file '%s' failed", opts->infile);

-	initialize_png(&img, f);

-	if (img.depth != depth) {

-		if (opts->verbose) {

-			warnx("Image bit depth is not %d (is %d).",

-			      depth, img.depth);

-		}

-	}

-	switch (img.type) {

-	case PNG_COLOR_TYPE_PALETTE:

-		raw_image = indexed_png_to_raw(&img); break;

-	case PNG_COLOR_TYPE_GRAY:

-	case PNG_COLOR_TYPE_GRAY_ALPHA:

-		raw_image = grayscale_png_to_raw(&img); break;

-	case PNG_COLOR_TYPE_RGB:

-	case PNG_COLOR_TYPE_RGB_ALPHA:

-		raw_image = truecolor_png_to_raw(&img); break;

-	default:

-		/* Shouldn't happen, but might as well handle just in case. */

-		errx("Input PNG file is of invalid color type.");

-	}

-	get_text(&img, png_options);

-	png_destroy_read_struct(&img.png, &img.info, NULL);

-	fclose(f);

-	free_png_data(&img);

-	return raw_image;

-}

-void output_png_file(const struct Options *opts,

-		     const struct ImageOptions *png_options,

-		     const struct RawIndexedImage *raw_image)

-{

-	FILE *f;

-	char *outfile;

-	struct PNGImage img;

-	png_color *png_palette;

-	int i;

-	/*

-	 * TODO: Variable outfile is for debugging purposes. Eventually,

-	 * opts.infile will be used directly.

-	 */

-	if (opts->debug) {

-		outfile = malloc(strlen(opts->infile) + 5);

-		if (!outfile)

-			err("%s: Failed to allocate memory for outfile",

-			    __func__);

-		strcpy(outfile, opts->infile);

-		strcat(outfile, ".out");

-	} else {

-		outfile = opts->infile;

-	}

-	f = fopen(outfile, "wb");

-	if (!f)

-		err("Opening output png file '%s' failed", outfile);

-	if (opts->debug)

-		free(outfile);

-	img.png = png_create_write_struct(PNG_LIBPNG_VER_STRING,

-					  NULL, NULL, NULL);

-	if (!img.png)

-		errx("Creating png structure failed");

-	img.info = png_create_info_struct(img.png);

-	if (!img.info)

-		errx("Creating png info structure failed");

-	if (setjmp(png_jmpbuf(img.png)))

-		exit(1);

-	png_init_io(img.png, f);

-	png_set_IHDR(img.png, img.info, raw_image->width, raw_image->height,

-		     8, PNG_COLOR_TYPE_PALETTE, PNG_INTERLACE_NONE,

-		     PNG_COMPRESSION_TYPE_DEFAULT, PNG_FILTER_TYPE_DEFAULT);

-	png_palette = malloc(sizeof(*png_palette) * raw_image->num_colors);

-	if (!png_palette)

-		err("%s: Failed to allocate memory for PNG palette",

-		    __func__);

-	for (i = 0; i < raw_image->num_colors; i++) {

-		png_palette[i].red   = raw_image->palette[i].red;

-		png_palette[i].green = raw_image->palette[i].green;

-		png_palette[i].blue  = raw_image->palette[i].blue;

-	}

-	png_set_PLTE(img.png, img.info, png_palette, raw_image->num_colors);

-	free(png_palette);

-	if (opts->fix)

-		set_text(&img, png_options);

-	png_write_info(img.png, img.info);

-	png_write_image(img.png, (png_byte **) raw_image->data);

-	png_write_end(img.png, NULL);

-	png_destroy_write_struct(&img.png, &img.info);

-	fclose(f);

-}

-void destroy_raw_image(struct RawIndexedImage **raw_image_ptr_ptr)

-{

-	struct RawIndexedImage *raw_image = *raw_image_ptr_ptr;

-	for (unsigned int y = 0; y < raw_image->height; y++)

-		free(raw_image->data[y]);

-	free(raw_image->data);

-	free(raw_image->palette);

-	free(raw_image);

-	*raw_image_ptr_ptr = NULL;

-}

-static void initialize_png(struct PNGImage *img, FILE *f)

-{

-	img->png = png_create_read_struct(PNG_LIBPNG_VER_STRING,

-					  NULL, NULL, NULL);

-	if (!img->png)

-		errx("Creating png structure failed");

-	img->info = png_create_info_struct(img->png);

-	if (!img->info)

-		errx("Creating png info structure failed");

-	if (setjmp(png_jmpbuf(img->png)))

-		exit(1);

-	png_init_io(img->png, f);

-	png_read_info(img->png, img->info);

-	img->width  = png_get_image_width(img->png, img->info);

-	img->height = png_get_image_height(img->png, img->info);

-	img->depth  = png_get_bit_depth(img->png, img->info);

-	img->type   = png_get_color_type(img->png, img->info);

-}

-static void read_png(struct PNGImage *img);

-static struct RawIndexedImage *create_raw_image(int width, int height,

-						int num_colors);

-static void set_raw_image_palette(struct RawIndexedImage *raw_image,

-				  png_color const *palette, int num_colors);

-static struct RawIndexedImage *indexed_png_to_raw(struct PNGImage *img)

-{

-	struct RawIndexedImage *raw_image;

-	png_color *palette;

-	int colors_in_PLTE;

-	int colors_in_new_palette;

-	png_byte *trans_alpha;

-	int num_trans;

-	png_color_16 *trans_color;

-	png_color *original_palette;

-	uint8_t *old_to_new_palette;

-	int i, x, y;

-	if (img->depth < 8)

-		png_set_packing(img->png);

-	png_get_PLTE(img->png, img->info, &palette, &colors_in_PLTE);

-	raw_image = create_raw_image(img->width, img->height, colors);

-	/*

-	 * Transparent palette entries are removed, and the palette is

-	 * collapsed. Transparent pixels are then replaced with palette index 0.

-	 * This way, an indexed PNG can contain transparent pixels in *addition*

-	 * to 4 normal colors.

-	 */

-	if (png_get_tRNS(img->png, img->info, &trans_alpha, &num_trans,

-			 &trans_color)) {

-		original_palette = palette;

-		palette = malloc(sizeof(*palette) * colors_in_PLTE);

-		if (!palette)

-			err("%s: Failed to allocate memory for palette",

-			    __func__);

-		colors_in_new_palette = 0;

-		old_to_new_palette = malloc(sizeof(*old_to_new_palette)

-					    * colors_in_PLTE);

-		if (!old_to_new_palette)

-			err("%s: Failed to allocate memory for new palette",

-			    __func__);

-		for (i = 0; i < num_trans; i++) {

-			if (trans_alpha[i] == 0) {

-				old_to_new_palette[i] = 0;

-			} else {

-				old_to_new_palette[i] = colors_in_new_palette;

-				palette[colors_in_new_palette++] =

-					original_palette[i];

-			}

-		}

-		for (i = num_trans; i < colors_in_PLTE; i++) {

-			old_to_new_palette[i] = colors_in_new_palette;

-			palette[colors_in_new_palette++] = original_palette[i];

-		}

-		if (colors_in_new_palette != colors_in_PLTE) {

-			palette = realloc(palette,

-					  sizeof(*palette) *

-					  colors_in_new_palette);

-			if (!palette)

-				err("%s: Failed to allocate memory for palette",

-				    __func__);

-		}

-		/*

-		 * Setting and validating palette before reading

-		 * allows us to error out *before* doing the data

-		 * transformation if the palette is too long.

-		 */

-		set_raw_image_palette(raw_image, palette,

-				      colors_in_new_palette);

-		read_png(img);

-		for (y = 0; y < img->height; y++) {

-			for (x = 0; x < img->width; x++) {

-				raw_image->data[y][x] =

-					old_to_new_palette[img->data[y][x]];

-			}

-		}

-		free(palette);

-		free(old_to_new_palette);

-	} else {

-		set_raw_image_palette(raw_image, palette, colors_in_PLTE);

-		read_png(img);

-		for (y = 0; y < img->height; y++) {

-			for (x = 0; x < img->width; x++)

-				raw_image->data[y][x] = img->data[y][x];

-		}

-	}

-	return raw_image;

-}

-static struct RawIndexedImage *grayscale_png_to_raw(struct PNGImage *img)

-{

-	if (img->depth < 8)

-		png_set_expand_gray_1_2_4_to_8(img->png);

-	png_set_gray_to_rgb(img->png);

-	return truecolor_png_to_raw(img);

-}

-static void rgba_png_palette(struct PNGImage *img,

-			     png_color **palette_ptr_ptr, int *num_colors);

-static struct RawIndexedImage

-	*processed_rgba_png_to_raw(const struct PNGImage *img,

-				   png_color const *palette,

-				   int colors_in_palette);

-static struct RawIndexedImage *truecolor_png_to_raw(struct PNGImage *img)

-{

-	struct RawIndexedImage *raw_image;

-	png_color *palette;

-	int colors_in_palette;

-	if (img->depth == 16) {

-#if PNG_LIBPNG_VER >= 10504

-		png_set_scale_16(img->png);

-#else

-		png_set_strip_16(img->png);

-#endif

-	}

-	if (!(img->type & PNG_COLOR_MASK_ALPHA)) {

-		if (png_get_valid(img->png, img->info, PNG_INFO_tRNS))

-			png_set_tRNS_to_alpha(img->png);

-		else

-			png_set_add_alpha(img->png, 0xFF, PNG_FILLER_AFTER);

-	}

-	read_png(img);

-	rgba_png_palette(img, &palette, &colors_in_palette);

-	raw_image = processed_rgba_png_to_raw(img, palette, colors_in_palette);

-	free(palette);

-	return raw_image;

-}

-static void rgba_PLTE_palette(struct PNGImage *img,

-			      png_color **palette_ptr_ptr, int *num_colors);

-static void rgba_build_palette(struct PNGImage *img,

-			       png_color **palette_ptr_ptr, int *num_colors);

-static void rgba_png_palette(struct PNGImage *img,

-			     png_color **palette_ptr_ptr, int *num_colors)

-{

-	if (png_get_valid(img->png, img->info, PNG_INFO_PLTE))

-		rgba_PLTE_palette(img, palette_ptr_ptr, num_colors);

-	else

-		rgba_build_palette(img, palette_ptr_ptr, num_colors);

-}

-static void rgba_PLTE_palette(struct PNGImage *img,

-			      png_color **palette_ptr_ptr, int *num_colors)

-{

-	png_get_PLTE(img->png, img->info, palette_ptr_ptr, num_colors);

-	/*

-	 * Lets us free the palette manually instead of leaving it to libpng,

-	 * which lets us handle a PLTE and a built palette the same way.

-	 */

-	png_data_freer(img->png, img->info,

-		       PNG_USER_WILL_FREE_DATA, PNG_FREE_PLTE);

-}

-static void update_built_palette(png_color *palette,

-				 png_color const *pixel_color, png_byte alpha,

-				 int *num_colors, bool *only_grayscale);

-static int fit_grayscale_palette(png_color *palette, int *num_colors);

-static void order_color_palette(png_color *palette, int num_colors);

-static void rgba_build_palette(struct PNGImage *img,

-			       png_color **palette_ptr_ptr, int *num_colors)

-{

-	png_color *palette;

-	int y, value_index;

-	png_color cur_pixel_color;

-	png_byte cur_alpha;

-	bool only_grayscale = true;

-	/*

-	 * By filling the palette up with black by default, if the image

-	 * doesn't have enough colors, the palette gets padded with black.

-	 */

-	*palette_ptr_ptr = calloc(colors, sizeof(**palette_ptr_ptr));

-	if (!*palette_ptr_ptr)

-		err("%s: Failed to allocate memory for palette", __func__);

-	palette = *palette_ptr_ptr;

-	*num_colors = 0;

-	for (y = 0; y < img->height; y++) {

-		value_index = 0;

-		while (value_index < img->width * 4) {

-			cur_pixel_color.red   = img->data[y][value_index++];

-			cur_pixel_color.green = img->data[y][value_index++];

-			cur_pixel_color.blue  = img->data[y][value_index++];

-			cur_alpha = img->data[y][value_index++];

-			update_built_palette(palette, &cur_pixel_color,

-					     cur_alpha,

-					     num_colors, &only_grayscale);

-		}

-	}

-	/* In order not to count 100% transparent images as grayscale. */

-	only_grayscale = *num_colors ? only_grayscale : false;

-	if (!only_grayscale || !fit_grayscale_palette(palette, num_colors))

-		order_color_palette(palette, *num_colors);

-}

-static void update_built_palette(png_color *palette,

-				 png_color const *pixel_color, png_byte alpha,

-				 int *num_colors, bool *only_grayscale)

-{

-	bool color_exists;

-	png_color cur_palette_color;

-	int i;

-	/*

-	 * Transparent pixels don't count toward the palette,

-	 * as they'll be replaced with color #0 later.

-	 */

-	if (alpha == 0)

-		return;

-	if (*only_grayscale && !(pixel_color->red == pixel_color->green &&

-				 pixel_color->red == pixel_color->blue)) {

-		*only_grayscale = false;

-	}

-	color_exists = false;

-	for (i = 0; i < *num_colors; i++) {

-		cur_palette_color = palette[i];

-		if (pixel_color->red   == cur_palette_color.red   &&

-		    pixel_color->green == cur_palette_color.green &&

-		    pixel_color->blue  == cur_palette_color.blue) {

-			color_exists = true;

-			break;

-		}

-	}

-	if (!color_exists) {

-		if (*num_colors == colors) {

-			errx("Too many colors in input PNG file to fit into a %d-bit palette (max %d).",

-			     depth, colors);

-		}

-		palette[*num_colors] = *pixel_color;

-		(*num_colors)++;

-	}

-}

-static int fit_grayscale_palette(png_color *palette, int *num_colors)

-{

-	int interval = 256 / colors;

-	png_color *fitted_palette = malloc(sizeof(*fitted_palette) * colors);

-	bool *set_indices = calloc(colors, sizeof(*set_indices));

-	int i, shade_index;

-	if (!fitted_palette)

-		err("%s: Failed to allocate memory for palette", __func__);

-	if (!set_indices)

-		err("%s: Failed to allocate memory for indices", __func__);

-	fitted_palette[0].red   = 0xFF;

-	fitted_palette[0].green = 0xFF;

-	fitted_palette[0].blue  = 0xFF;

-	fitted_palette[colors - 1].red   = 0;

-	fitted_palette[colors - 1].green = 0;

-	fitted_palette[colors - 1].blue  = 0;

-	if (colors == 4) {

-		fitted_palette[1].red   = 0xA9;

-		fitted_palette[1].green = 0xA9;

-		fitted_palette[1].blue  = 0xA9;

-		fitted_palette[2].red   = 0x55;

-		fitted_palette[2].green = 0x55;

-		fitted_palette[2].blue  = 0x55;

-	}

-	for (i = 0; i < *num_colors; i++) {

-		shade_index = colors - 1 - palette[i].red / interval;

-		if (set_indices[shade_index]) {

-			free(fitted_palette);

-			free(set_indices);

-			return false;

-		}

-		fitted_palette[shade_index] = palette[i];

-		set_indices[shade_index] = true;

-	}

-	for (i = 0; i < colors; i++)

-		palette[i] = fitted_palette[i];

-	*num_colors = colors;

-	free(fitted_palette);

-	free(set_indices);

-	return true;

-}

-/* A combined struct is needed to sort csolors in order of luminance. */

-struct ColorWithLuminance {

-	png_color color;

-	int luminance;

-};

-static int compare_luminance(void const *a, void const *b)

-{

-	const struct ColorWithLuminance *x, *y;

-	x = (const struct ColorWithLuminance *)a;

-	y = (const struct ColorWithLuminance *)b;

-	return y->luminance - x->luminance;

-}

-static void order_color_palette(png_color *palette, int num_colors)

-{

-	int i;

-	struct ColorWithLuminance *palette_with_luminance =

-		malloc(sizeof(*palette_with_luminance) * num_colors);

-	if (!palette_with_luminance)

-		err("%s: Failed to allocate memory for palette", __func__);

-	for (i = 0; i < num_colors; i++) {

-		/*

-		 * Normally this would be done with floats, but since it's only

-		 * used for comparison, we might as well use integer math.

-		 */

-		palette_with_luminance[i].color = palette[i];

-		palette_with_luminance[i].luminance = 2126 * palette[i].red   +

-						      7152 * palette[i].green +

-						       722 * palette[i].blue;

-	}

-	qsort(palette_with_luminance, num_colors,

-	      sizeof(*palette_with_luminance), compare_luminance);

-	for (i = 0; i < num_colors; i++)

-		palette[i] = palette_with_luminance[i].color;

-	free(palette_with_luminance);

-}

-static void put_raw_image_pixel(struct RawIndexedImage *raw_image,

-				const struct PNGImage *img,

-				int *value_index, int x, int y,

-				png_color const *palette,

-				int colors_in_palette);

-static struct RawIndexedImage

-	*processed_rgba_png_to_raw(const struct PNGImage *img,

-				   png_color const *palette,

-				   int colors_in_palette)

-{

-	struct RawIndexedImage *raw_image;

-	int x, y, value_index;

-	raw_image = create_raw_image(img->width, img->height, colors);

-	set_raw_image_palette(raw_image, palette, colors_in_palette);

-	for (y = 0; y < img->height; y++) {

-		x = raw_image->width - 1;

-		value_index = img->width * 4 - 1;

-		while (x >= 0) {

-			put_raw_image_pixel(raw_image, img,

-					    &value_index, x, y,

-					    palette, colors_in_palette);

-			x--;

-		}

-	}

-	return raw_image;

-}

-static uint8_t palette_index_of(png_color const *palette,

-				int num_colors, png_color const *color);

-static void put_raw_image_pixel(struct RawIndexedImage *raw_image,

-				const struct PNGImage *img,

-				int *value_index, int x, int y,

-				png_color const *palette,

-				int colors_in_palette)

-{

-	png_color pixel_color;

-	png_byte alpha;

-	alpha = img->data[y][*value_index];

-	if (alpha == 0) {

-		raw_image->data[y][x] = 0;

-		*value_index -= 4;

-	} else {

-		(*value_index)--;

-		pixel_color.blue  = img->data[y][(*value_index)--];

-		pixel_color.green = img->data[y][(*value_index)--];

-		pixel_color.red   = img->data[y][(*value_index)--];

-		raw_image->data[y][x] = palette_index_of(palette,

-							 colors_in_palette,

-							 &pixel_color);

-	}

-}

-static uint8_t palette_index_of(png_color const *palette,

-				int num_colors, png_color const *color)

-{

-	uint8_t i;

-	for (i = 0; i < num_colors; i++) {

-		if (palette[i].red   == color->red   &&

-		    palette[i].green == color->green &&

-		    palette[i].blue  == color->blue) {

-			return i;

-		}

-	}

-	errx("The input PNG file contains colors that don't appear in its embedded palette.");

-}

-static void read_png(struct PNGImage *img)

-{

-	int y;

-	png_read_update_info(img->png, img->info);

-	img->data = malloc(sizeof(*img->data) * img->height);

-	if (!img->data)

-		err("%s: Failed to allocate memory for image data",

-		    __func__);

-	for (y = 0; y < img->height; y++) {

-		img->data[y] = malloc(png_get_rowbytes(img->png, img->info));

-		if (!img->data[y])

-			err("%s: Failed to allocate memory for image data",

-			    __func__);

-	}

-	png_read_image(img->png, img->data);

-	png_read_end(img->png, img->info);

-}

-static struct RawIndexedImage *create_raw_image(int width, int height,

-						int num_colors)

-{

-	struct RawIndexedImage *raw_image;

-	int y;

-	raw_image = malloc(sizeof(*raw_image));

-	if (!raw_image)

-		err("%s: Failed to allocate memory for raw image",

-		    __func__);

-	raw_image->width = width;

-	raw_image->height = height;

-	raw_image->num_colors = num_colors;

-	raw_image->palette = malloc(sizeof(*raw_image->palette) * num_colors);

-	if (!raw_image->palette)

-		err("%s: Failed to allocate memory for raw image palette",

-		    __func__);

-	raw_image->data = malloc(sizeof(*raw_image->data) * height);

-	if (!raw_image->data)

-		err("%s: Failed to allocate memory for raw image data",

-		    __func__);

-	for (y = 0; y < height; y++) {

-		raw_image->data[y] = malloc(sizeof(*raw_image->data[y])

-					    * width);

-		if (!raw_image->data[y])

-			err("%s: Failed to allocate memory for raw image data",

-			    __func__);

-	}

-	return raw_image;

-}

-static void set_raw_image_palette(struct RawIndexedImage *raw_image,

-				  png_color const *palette, int num_colors)

-{

-	int i;

-	if (num_colors > raw_image->num_colors) {

-		errx("Too many colors in input PNG file's palette to fit into a %d-bit palette (%d in input palette, max %d).",

-		     raw_image->num_colors >> 1,

-		     num_colors, raw_image->num_colors);

-	}

-	for (i = 0; i < num_colors; i++) {

-		raw_image->palette[i].red   = palette[i].red;

-		raw_image->palette[i].green = palette[i].green;

-		raw_image->palette[i].blue  = palette[i].blue;

-	}

-	for (i = num_colors; i < raw_image->num_colors; i++) {

-		raw_image->palette[i].red   = 0;

-		raw_image->palette[i].green = 0;

-		raw_image->palette[i].blue  = 0;

-	}

-}

-static void get_text(const struct PNGImage *img,

-		     struct ImageOptions *png_options)

-{

-	png_text *text;

-	int i, numtxts, numremoved;

-	png_get_text(img->png, img->info, &text, &numtxts);

-	for (i = 0; i < numtxts; i++) {

-		if (strcmp(text[i].key, "h") == 0 && !*text[i].text) {

-			png_options->horizontal = true;

-			png_free_data(img->png, img->info, PNG_FREE_TEXT, i);

-		} else if (strcmp(text[i].key, "x") == 0) {

-			png_options->trim = strtoul(text[i].text, NULL, 0);

-			png_free_data(img->png, img->info, PNG_FREE_TEXT, i);

-		} else if (strcmp(text[i].key, "t") == 0) {

-			png_options->tilemapfile = text[i].text;

-			png_free_data(img->png, img->info, PNG_FREE_TEXT, i);

-		} else if (strcmp(text[i].key, "T") == 0 && !*text[i].text) {

-			png_options->tilemapout = true;

-			png_free_data(img->png, img->info, PNG_FREE_TEXT, i);

-		} else if (strcmp(text[i].key, "a") == 0) {

-			png_options->attrmapfile = text[i].text;

-			png_free_data(img->png, img->info, PNG_FREE_TEXT, i);

-		} else if (strcmp(text[i].key, "A") == 0 && !*text[i].text) {

-			png_options->attrmapout = true;

-			png_free_data(img->png, img->info, PNG_FREE_TEXT, i);

-		} else if (strcmp(text[i].key, "p") == 0) {

-			png_options->palfile = text[i].text;

-			png_free_data(img->png, img->info, PNG_FREE_TEXT, i);

-		} else if (strcmp(text[i].key, "P") == 0 && !*text[i].text) {

-			png_options->palout = true;

-			png_free_data(img->png, img->info, PNG_FREE_TEXT, i);

-		}

-	}

-	/*

-	 * TODO: Remove this and simply change the warning function not to warn

-	 * instead.

-	 */

-	for (i = 0, numremoved = 0; i < numtxts; i++) {

-		if (text[i].key == NULL)

-			numremoved++;

-		text[i].key = text[i + numremoved].key;

-		text[i].text = text[i + numremoved].text;

-		text[i].compression = text[i + numremoved].compression;

-	}

-	png_set_text(img->png, img->info, text, numtxts - numremoved);

-}

-static void set_text(const struct PNGImage *img,

-		     const struct ImageOptions *png_options)

-{

-	png_text *text;

-	char buffer[3];

-	text = malloc(sizeof(*text));

-	if (!text)

-		err("%s: Failed to allocate memory for PNG text",

-		    __func__);

-	if (png_options->horizontal) {

-		text[0].key = "h";

-		text[0].text = "";

-		text[0].compression = PNG_TEXT_COMPRESSION_NONE;

-		png_set_text(img->png, img->info, text, 1);

-	}

-	if (png_options->trim) {

-		text[0].key = "x";

-		snprintf(buffer, 3, "%d", png_options->trim);

-		text[0].text = buffer;

-		text[0].compression = PNG_TEXT_COMPRESSION_NONE;

-		png_set_text(img->png, img->info, text, 1);

-	}

-	if (*png_options->tilemapfile) {

-		text[0].key = "t";

-		text[0].text = "";

-		text[0].compression = PNG_TEXT_COMPRESSION_NONE;

-		png_set_text(img->png, img->info, text, 1);

-	}

-	if (png_options->tilemapout) {

-		text[0].key = "T";

-		text[0].text = "";

-		text[0].compression = PNG_TEXT_COMPRESSION_NONE;

-		png_set_text(img->png, img->info, text, 1);

-	}

-	if (*png_options->attrmapfile) {

-		text[0].key = "a";

-		text[0].text = "";

-		text[0].compression = PNG_TEXT_COMPRESSION_NONE;

-		png_set_text(img->png, img->info, text, 1);

-	}

-	if (png_options->attrmapout) {

-		text[0].key = "A";

-		text[0].text = "";

-		text[0].compression = PNG_TEXT_COMPRESSION_NONE;

-		png_set_text(img->png, img->info, text, 1);

-	}

-	if (*png_options->palfile) {

-		text[0].key = "p";

-		text[0].text = "";

-		text[0].compression = PNG_TEXT_COMPRESSION_NONE;

-		png_set_text(img->png, img->info, text, 1);

-	}

-	if (png_options->palout) {

-		text[0].key = "P";

-		text[0].text = "";

-		text[0].compression = PNG_TEXT_COMPRESSION_NONE;

-		png_set_text(img->png, img->info, text, 1);

-	}

-	free(text);

-}

-static void free_png_data(const struct PNGImage *img)

-{

-	int y;

-	for (y = 0; y < img->height; y++)

-		free(img->data[y]);

-	free(img->data);

-}

--- /dev/null

+++ b/src/gfx/pal_packing.cpp

@@ -1,0 +1,359 @@

+/*

+ * This file is part of RGBDS.

+ *

+ * Copyright (c) 2022, Eldred Habert and RGBDS contributors.

+ *

+ * SPDX-License-Identifier: MIT

+ */

+#include "gfx/pal_packing.hpp"

+#include <assert.h>

+#include <bitset>

+#include <inttypes.h>

+#include <numeric>

+#include <optional>

+#include <queue>

+#include <tuple>

+#include <type_traits>

+#include <unordered_set>

+#include <vector>

+#include "gfx/main.hpp"

+#include "gfx/proto_palette.hpp"

+using std::swap;

+namespace packing {

+// The solvers here are picked from the paper at http://arxiv.org/abs/1605.00558:

+// "Algorithms for the Pagination Problem, a Bin Packing with Overlapping Items"

+// Their formulation of the problem consists in packing "tiles" into "pages"; here is a

+// correspondence table for our application of it:

+// Paper | RGBGFX

+// ------+-------

+//  Tile | Proto-palette

+//  Page | Palette

+/**

+ * A reference to a proto-palette, and attached attributes for sorting purposes

+ */

+struct ProtoPalAttrs {

+	size_t const palIndex;

+	/**

+	 * Pages from which we are banned (to prevent infinite loops)

+	 * This is dynamic because we wish not to hard-cap the amount of palettes

+	 */

+	std::vector<bool> bannedPages;

+	ProtoPalAttrs(size_t index) : palIndex(index) {}

+	bool isBannedFrom(size_t index) const {

+		return index < bannedPages.size() && bannedPages[index];

+	}

+	void banFrom(size_t index) {

+		if (bannedPages.size() <= index) {

+			bannedPages.resize(index + 1);

+		}

+		bannedPages[index] = true;

+	}

+};

+/**

+ * A collection of proto-palettes assigned to a palette

+ * Does not contain the actual color indices because we need to be able to remove elements

+ */

+class AssignedProtos {

+	// We leave room for emptied slots to avoid copying the structs around on removal

+	std::vector<std::optional<ProtoPalAttrs>> _assigned;

+	// For resolving proto-palette indices

+	std::vector<ProtoPalette> const &_protoPals;

+public:

+	template<typename... Ts>

+	AssignedProtos(decltype(_protoPals) protoPals, Ts &&...elems)

+		: _assigned{std::forward<Ts>(elems)...}, _protoPals{protoPals} {}

+private:

+	template<typename Inner, template<typename> typename Constness>

+	class Iter {

+	public:

+		friend class AssignedProtos;

+		// For `iterator_traits`

+		using difference_type = typename std::iterator_traits<Inner>::difference_type;

+		using value_type = ProtoPalAttrs;

+		using pointer = Constness<value_type> *;

+		using reference = Constness<value_type> &;

+		using iterator_category = std::input_iterator_tag;

+	private:

+		Constness<decltype(_assigned)> *_array = nullptr;

+		Inner _iter{};

+		Iter(decltype(_array) array, decltype(_iter) &&iter) : _array(array), _iter(iter) {

+			skipEmpty();

+		}

+		void skipEmpty() {

+			while (_iter != _array->end() && !(*_iter).has_value()) {

+				++_iter;

+			}

+		}

+	public:

+		Iter() = default;

+		bool operator==(Iter const &other) const { return _iter == other._iter; }

+		bool operator!=(Iter const &other) const { return !(*this == other); }

+		Iter &operator++() {

+			++_iter;

+			skipEmpty();

+			return *this;

+		}

+		Iter operator++(int) {

+			Iter it = *this;

+			++(*this);

+			return it;

+		}

+		reference operator*() const {

+			assert((*_iter).has_value());

+			return **_iter;

+		}

+		pointer operator->() const {

+			return &(**this); // Invokes the operator above, not quite a no-op!

+		}

+		friend void swap(Iter &lhs, Iter &rhs) {

+			swap(lhs._array, rhs._array);

+			swap(lhs._iter, rhs._iter);

+		}

+	};

+public:

+	using iterator = Iter<decltype(_assigned)::iterator, std::remove_const_t>;

+	iterator begin() { return iterator{&_assigned, _assigned.begin()}; }

+	iterator end() { return iterator{&_assigned, _assigned.end()}; }

+	using const_iterator = Iter<decltype(_assigned)::const_iterator, std::add_const_t>;

+	const_iterator begin() const { return const_iterator{&_assigned, _assigned.begin()}; }

+	const_iterator end() const { return const_iterator{&_assigned, _assigned.end()}; }

+	/**

+	 * Assigns a new ProtoPalAttrs in a free slot, assuming there is one

+	 * Args are passed to the `ProtoPalAttrs`'s constructor

+	 */

+	template<typename... Ts>

+	auto assign(Ts &&...args) {

+		auto freeSlot = std::find_if_not(

+			_assigned.begin(), _assigned.end(),

+			[](std::optional<ProtoPalAttrs> const &slot) { return slot.has_value(); });

+		if (freeSlot == _assigned.end()) { // We are full, use a new slot

+			_assigned.emplace_back(std::forward<Ts>(args)...);

+		} else { // Reuse a free slot

+			(*freeSlot).emplace(std::forward<Ts>(args)...);

+		}

+		return freeSlot;

+	}

+	void remove(iterator const &iter) {

+		(*iter._iter).reset(); // This time, we want to access the `optional` itself

+	}

+	void clear() { _assigned.clear(); }

+	/**

+	 * Computes the "relative size" of a proto-palette on this palette

+	 */

+	double relSizeOf(ProtoPalette const &protoPal) const {

+		return std::transform_reduce(

+			protoPal.begin(), protoPal.end(), .0, std::plus<>(), [this](uint16_t color) {

+				// NOTE: The paper and the associated code disagree on this: the code has

+			    // this `1 +`, whereas the paper does not; its lack causes a division by 0

+			    // if the symbol is not found anywhere, so I'm assuming the paper is wrong.

+				return 1.

+			           / (1

+			              + std::count_if(

+							  begin(), end(), [this, &color](ProtoPalAttrs const &attrs) {

+								  ProtoPalette const &pal = _protoPals[attrs.palIndex];

+								  return std::find(pal.begin(), pal.end(), color) != pal.end();

+							  }));

+			});

+	}

+private:

+	std::unordered_set<uint16_t> &uniqueColors() const {

+		// We check for *distinct* colors by stuffing them into a `set`; this should be

+		// faster than "back-checking" on every element (O(n²))

+		//

+		// TODO: calc84maniac suggested another approach; try implementing it, see if it

+		// performs better:

+		// > So basically you make a priority queue that takes iterators into each of your sets

+		// (paired with end iterators so you'll know where to stop), and the comparator tests the

+		// values pointed to by each iterator > Then each iteration you pop from the queue,

+		// optionally add one to your count, increment the iterator and push it back into the queue

+		// if it didn't reach the end > and you do this until the priority queue is empty

+		static std::unordered_set<uint16_t> colors;

+		colors.clear();

+		for (ProtoPalAttrs const &attrs : *this) {

+			for (uint16_t color : _protoPals[attrs.palIndex]) {

+				colors.insert(color);

+			}

+		}

+		return colors;

+	}

+public:

+	/**

+	 * Returns the number of distinct colors

+	 */

+	size_t volume() const { return uniqueColors().size(); }

+	bool canFit(ProtoPalette const &protoPal) const {

+		auto &colors = uniqueColors();

+		for (uint16_t color : protoPal) {

+			colors.insert(color);

+		}

+		return colors.size() <= 4;

+	}

+};

+std::tuple<DefaultInitVec<size_t>, size_t>

+	overloadAndRemove(std::vector<ProtoPalette> const &protoPalettes) {

+	options.verbosePrint("Paginating palettes using \"overload-and-remove\" strategy...\n");

+	struct Iota {

+		using value_type = size_t;

+		using difference_type = size_t;

+		using pointer = value_type const *;

+		using reference = value_type const &;

+		using iterator_category = std::input_iterator_tag;

+		// Use aggregate init etc.

+		value_type i;

+		bool operator!=(Iota const &other) { return i != other.i; }

+		reference operator*() const { return i; }

+		pointer operator->() const { return &i; }

+		Iota operator++() {

+			++i;

+			return *this;

+		}

+		Iota operator++(int) {

+			Iota copy = *this;

+			++i;

+			return copy;

+		}

+	};

+	// Begin with all proto-palettes queued up for insertion

+	std::queue queue(std::deque<ProtoPalAttrs>(Iota{0}, Iota{protoPalettes.size()}));

+	// Begin with no pages

+	std::vector<AssignedProtos> assignments{};

+	for (; !queue.empty(); queue.pop()) {

+		ProtoPalAttrs const &attrs = queue.front(); // Valid until the `queue.pop()`

+		ProtoPalette const &protoPal = protoPalettes[attrs.palIndex];

+		size_t bestPalIndex = assignments.size();

+		// We're looking for a palette where the proto-palette's relative size is less than

+		// its actual size; so only overwrite the "not found" index on meeting that criterion

+		double bestRelSize = protoPal.size();

+		for (size_t i = 0; i < assignments.size(); ++i) {

+			// Skip the page if this one is banned from it

+			if (attrs.isBannedFrom(i)) {

+				continue;

+			}

+			options.verbosePrint("%zu: Rel size: %f (size = %zu)\n", i,

+			                     assignments[i].relSizeOf(protoPal), protoPal.size());

+			if (assignments[i].relSizeOf(protoPal) < bestRelSize) {

+				bestPalIndex = i;

+			}

+		}

+		if (bestPalIndex == assignments.size()) {

+			// Found nowhere to put it, create a new page containing just that one

+			assignments.emplace_back(protoPalettes, std::move(attrs));

+		} else {

+			auto &bestPal = assignments[bestPalIndex];

+			// Add the color to that palette

+			bestPal.assign(std::move(attrs));

+			// If this overloads the palette, get it back to normal (if possible)

+			while (bestPal.volume() > 4) {

+				options.verbosePrint("Palette %zu is overloaded! (%zu > 4)\n", bestPalIndex,

+				                     bestPal.volume());

+				// Look for a proto-pal minimizing "efficiency" (size / rel_size)

+				auto efficiency = [&bestPal](ProtoPalette const &pal) {

+					return pal.size() / bestPal.relSizeOf(pal);

+				};

+				auto [minEfficiencyIter, maxEfficiencyIter] =

+					std::minmax_element(bestPal.begin(), bestPal.end(),

+				                        [&efficiency, &protoPalettes](ProtoPalAttrs const &lhs,

+				                                                      ProtoPalAttrs const &rhs) {

+											return efficiency(protoPalettes[lhs.palIndex])

+					                               < efficiency(protoPalettes[rhs.palIndex]);

+										});

+				// All efficiencies are identical iff min equals max

+				// TODO: maybe not ideal to re-compute these two?

+				// TODO: yikes for float comparison! I *think* this threshold is OK?

+				if (efficiency(protoPalettes[maxEfficiencyIter->palIndex])

+				        - efficiency(protoPalettes[minEfficiencyIter->palIndex])

+				    < .001) {

+					break;

+				}

+				// Remove the proto-pal with minimal efficiency

+				queue.emplace(std::move(*minEfficiencyIter));

+				queue.back().banFrom(bestPalIndex); // Ban it from this palette

+				bestPal.remove(minEfficiencyIter);

+			}

+		}

+	}

+	// Deal with palettes still overloaded, by emptying them

+	for (AssignedProtos &pal : assignments) {

+		if (pal.volume() > 4) {

+			for (ProtoPalAttrs &attrs : pal) {

+				queue.emplace(std::move(attrs));

+			}

+			pal.clear();

+		}

+	}

+	// Place back any proto-palettes now in the queue via first-fit

+	while (!queue.empty()) {

+		ProtoPalAttrs const &attrs = queue.front();

+		ProtoPalette const &protoPal = protoPalettes[attrs.palIndex];

+		auto iter =

+			std::find_if(assignments.begin(), assignments.end(),

+		                 [&protoPal](AssignedProtos const &pal) { return pal.canFit(protoPal); });

+		if (iter == assignments.end()) { // No such page, create a new one

+			options.verbosePrint("Adding new palette for overflow\n");

+			assignments.emplace_back(protoPalettes, std::move(attrs));

+		} else {

+			options.verbosePrint("Assigning overflow to palette %zu\n", iter - assignments.begin());

+			iter->assign(std::move(attrs));

+		}

+		queue.pop();

+	}

+	// Deal with any empty palettes left over from the "un-overloading" step

+	// TODO (can there be any?)

+	if (options.beVerbose) {

+		for (auto &&assignment : assignments) {

+			options.verbosePrint("{ ");

+			for (auto &&attrs : assignment) {

+				for (auto &&colorIndex : protoPalettes[attrs.palIndex]) {

+					options.verbosePrint("%04" PRIx16 ", ", colorIndex);

+				}

+			}

+			options.verbosePrint("} (%zu)\n", assignment.volume());

+		}

+	}

+	DefaultInitVec<size_t> mappings(protoPalettes.size());

+	for (size_t i = 0; i < assignments.size(); ++i) {

+		for (ProtoPalAttrs const &attrs : assignments[i]) {

+			mappings[attrs.palIndex] = i;

+		}

+	}

+	return {mappings, assignments.size()};

+}

+} // namespace packing

--- /dev/null

+++ b/src/gfx/pal_sorting.cpp

@@ -1,0 +1,64 @@

+#include "gfx/pal_sorting.hpp"

+#include <algorithm>

+#include <png.h>

+#include <vector>

+#include "helpers.h"

+#include "gfx/main.hpp"

+namespace sorting {

+void indexed(std::vector<Palette> &palettes, int palSize, png_color const *palRGB,

+             png_byte *palAlpha) {

+	options.verbosePrint("Sorting palettes using embedded palette...\n");

+	for (Palette &pal : palettes) {

+		std::sort(pal.begin(), pal.end(), [&](uint16_t lhs, uint16_t rhs) {

+			// Iterate through the PNG's palette, looking for either of the two

+			for (int i = 0; i < palSize; ++i) {

+				if (palAlpha && palAlpha[i])

+					continue;

+				auto const &c = palRGB[i];

+				uint16_t cgbColor = c.red >> 3 | (c.green >> 3) << 5 | (c.blue >> 3) << 10;

+				// Return whether lhs < rhs

+				if (cgbColor == rhs) {

+					return false;

+				}

+				if (cgbColor == lhs) {

+					return true;

+				}

+			}

+			unreachable_(); // This should not be possible

+		});

+	}

+}

+void grayscale(std::vector<Palette> &palettes) {

+	options.verbosePrint("Sorting grayscale-only palettes...\n");

+	for (Palette &pal : palettes) {

+		(void)pal; // TODO

+	}

+}

+static unsigned int legacyLuminance(uint16_t color) {

+	uint8_t red = color & 0b11111;

+	uint8_t green = color >> 5 & 0b11111;

+	uint8_t blue = color >> 10;

+	return 2126 * red + 7152 * green + 722 * blue;

+}

+void rgb(std::vector<Palette> &palettes) {

+	options.verbosePrint("Sorting palettes by \"\"\"luminance\"\"\"...\n");

+	for (Palette &pal : palettes) {

+		std::sort(pal.begin(), pal.end(), [](uint16_t lhs, uint16_t rhs) {

+			return legacyLuminance(lhs) < legacyLuminance(rhs);

+		});

+	}

+}

+} // namespace sorting

--- /dev/null

+++ b/src/gfx/proto_palette.cpp

@@ -1,0 +1,79 @@

+/*

+ * This file is part of RGBDS.

+ *

+ * Copyright (c) 2022, Eldred Habert and RGBDS contributors.

+ *

+ * SPDX-License-Identifier: MIT

+ */

+#include "gfx/proto_palette.hpp"

+#include <algorithm>

+#include <array>

+#include <stddef.h>

+#include <stdint.h>

+bool ProtoPalette::add(uint16_t color) {

+	size_t i = 0;

+	// Seek the first slot greater than our color

+	// (A linear search is better because we don't store the array size,

+	// and there are very few slots anyway)

+	while (_colorIndices[i] < color) {

+		++i;

+		if (i == _colorIndices.size())

+			return false; // EOF

+	}

+	// If we found ourselves, great!

+	if (_colorIndices[i] == color)

+		return true;

+	// Swap entries until the end

+	while (_colorIndices[i] != UINT16_MAX) {

+		std::swap(_colorIndices[i], color);

+		++i;

+		if (i == _colorIndices.size())

+			return false; // Oh well

+	}

+	// Write that last one into the new slot

+	_colorIndices[i] = color;

+	return true;

+}

+ProtoPalette::ComparisonResult ProtoPalette::compare(ProtoPalette const &other) const {

+	auto ours = _colorIndices.begin(), theirs = other._colorIndices.begin();

+	bool weBigger = true, theyBigger = true;

+	while (ours != _colorIndices.end() && theirs != other._colorIndices.end()) {

+		if (*ours == *theirs) {

+			++ours;

+			++theirs;

+		} else if (*ours < *theirs) {

+			++ours;

+			theyBigger = false;

+		} else {

+			++theirs;

+			weBigger = false;

+		}

+	}

+	weBigger &= ours == _colorIndices.end();

+	theyBigger &= theirs == other._colorIndices.end();

+	return theyBigger ? THEY_BIGGER : (weBigger ? WE_BIGGER : NEITHER);

+}

+ProtoPalette &ProtoPalette::operator=(ProtoPalette const &other) {

+	_colorIndices = other._colorIndices;

+	return *this;

+}

+size_t ProtoPalette::size() const {

+	return std::distance(begin(), end());

+}

+auto ProtoPalette::begin() const -> decltype(_colorIndices)::const_iterator {

+	return _colorIndices.begin();

+}

+auto ProtoPalette::end() const -> decltype(_colorIndices)::const_iterator {

+	return std::find(_colorIndices.begin(), _colorIndices.end(), UINT16_MAX);

+}

--

⑨