ref: 3f70372308167399b4e6fd6bfef9d93bc93221fb
dir: /src/gfx/process.cpp/
/*
* This file is part of RGBDS.
*
* Copyright (c) 2022, Eldred Habert and RGBDS contributors.
*
* SPDX-License-Identifier: MIT
*/
#include "gfx/process.hpp"
#include <algorithm>
#include <assert.h>
#include <cinttypes>
#include <climits>
#include <cstdio>
#include <errno.h>
#include <fstream>
#include <memory>
#include <optional>
#include <png.h>
#include <setjmp.h>
#include <stdint.h>
#include <string.h>
#include <tuple>
#include <unordered_set>
#include <utility>
#include <vector>
#include "defaultinitalloc.hpp"
#include "helpers.h"
#include "itertools.hpp"
#include "gfx/main.hpp"
#include "gfx/pal_packing.hpp"
#include "gfx/pal_sorting.hpp"
#include "gfx/proto_palette.hpp"
class ImagePalette {
// Use as many slots as there are CGB colors (plus transparency)
std::array<std::optional<Rgba>, 0x8001> _colors;
public:
ImagePalette() = default;
/**
* Registers a color in the palette.
* If the newly inserted color "conflicts" with another one (different color, but same CGB
* color), then the other color is returned. Otherwise, `nullptr` is returned.
*/
[[nodiscard]] Rgba const *registerColor(Rgba const &rgba) {
decltype(_colors)::value_type &slot = _colors[rgba.cgbColor()];
if (rgba.cgbColor() == Rgba::transparent) {
options.hasTransparentPixels = true;
}
if (!slot.has_value()) {
slot.emplace(rgba);
} else if (*slot != rgba) {
assert(slot->cgbColor() != UINT16_MAX);
return &*slot;
}
return nullptr;
}
size_t size() const {
return std::count_if(_colors.begin(), _colors.end(),
[](decltype(_colors)::value_type const &slot) {
return slot.has_value() && !slot->isTransparent();
});
}
decltype(_colors) const &raw() const { return _colors; }
auto begin() const { return _colors.begin(); }
auto end() const { return _colors.end(); }
};
class Png {
std::string const &path;
std::filebuf file{};
png_structp png = nullptr;
png_infop info = nullptr;
// These are cached for speed
uint32_t width, height;
DefaultInitVec<Rgba> pixels;
ImagePalette colors;
int colorType;
int nbColors;
png_colorp embeddedPal = nullptr;
png_bytep transparencyPal = nullptr;
[[noreturn]] static void handleError(png_structp png, char const *msg) {
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) {
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) {
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; }
Rgba &pixel(uint32_t x, uint32_t y) { return pixels[y * width + x]; }
Rgba const &pixel(uint32_t x, uint32_t y) const { return pixels[y * width + x]; }
bool isSuitableForGrayscale() const {
// Check that all of the grays don't fall into the same "bin"
if (colors.size() > options.maxOpaqueColors()) { // Apply the Pigeonhole Principle
options.verbosePrint(Options::VERB_DEBUG,
"Too many colors for grayscale sorting (%zu > %" PRIu8 ")\n",
colors.size(), options.maxOpaqueColors());
return false;
}
uint8_t bins = 0;
for (auto const &color : colors) {
if (color->isTransparent()) {
continue;
}
if (!color->isGray()) {
options.verbosePrint(Options::VERB_DEBUG,
"Found non-gray color #%08x, not using grayscale sorting\n",
color->toCSS());
return false;
}
uint8_t mask = 1 << color->grayIndex();
if (bins & mask) { // Two in the same bin!
options.verbosePrint(
Options::VERB_DEBUG,
"Color #%08x conflicts with another one, not using grayscale sorting\n",
color->toCSS());
return false;
}
bins |= mask;
}
return true;
}
/**
* 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::string 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(Options::VERB_LOG_ACT, "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(Options::VERB_INTERM, "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 (options.inputSlice.width == 0 && width % 8 != 0) {
fatal("Image width (%" PRIu32 " pixels) is not a multiple of 8!", width);
}
if (options.inputSlice.height == 0 && height % 8 != 0) {
fatal("Image height (%" PRIu32 " pixels) is not a multiple of 8!", height);
}
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(Options::VERB_INTERM,
"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(Options::VERB_INTERM, "Embedded palette has %d colors: [",
nbColors);
for (int i = 0; i < nbColors; ++i) {
auto const &color = embeddedPal[i];
options.verbosePrint(
Options::VERB_INTERM, "#%02x%02x%02x%02x%s", color.red, color.green, color.blue,
transparencyPal ? transparencyPal[i] : 0xFF, i != nbColors - 1 ? ", " : "]\n");
}
} else {
options.verbosePrint(Options::VERB_INTERM, "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 (png_get_valid(png, info, PNG_INFO_tRNS)) {
// If we read a tRNS chunk, convert it to alpha
png_set_tRNS_to_alpha(png);
} else if (!(colorType & PNG_COLOR_MASK_ALPHA)) {
// Otherwise, if we lack an alpha channel, default to full opacity
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);
}
// Do NOT call `png_set_interlace_handling`. We want to expand the rows ourselves.
// 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
size_t nbRowBytes = png_get_rowbytes(png, info);
assert(nbRowBytes != 0);
DefaultInitVec<png_byte> row(nbRowBytes);
// Holds known-conflicting color pairs to avoid warning about them twice.
// We don't need to worry about transitivity, as ImagePalette slots are immutable once
// assigned, and conflicts always occur between that and another color.
// For the same reason, we don't need to worry about order, either.
std::vector<std::tuple<uint32_t, uint32_t>> conflicts;
// Holds colors whose alpha value is ambiguous
std::vector<uint32_t> indeterminates;
// Assign a color to the given position, and register it in the image palette as well
auto assignColor = [this, &conflicts, &indeterminates](png_uint_32 x, png_uint_32 y,
Rgba &&color) {
if (!color.isTransparent() && !color.isOpaque()) {
uint32_t css = color.toCSS();
if (std::find(indeterminates.begin(), indeterminates.end(), css)
== indeterminates.end()) {
error("Color #%08x is neither transparent (alpha < %u) nor opaque (alpha >= "
"%u) [first seen at x: %" PRIu32 ", y: %" PRIu32 "]",
css, Rgba::transparency_threshold, Rgba::opacity_threshold, x, y);
indeterminates.push_back(css);
}
} else if (Rgba const *other = colors.registerColor(color); other) {
std::tuple conflicting{color.toCSS(), other->toCSS()};
// Do not report combinations twice
if (std::find(conflicts.begin(), conflicts.end(), conflicting) == conflicts.end()) {
warning("Fusing colors #%08x and #%08x into Game Boy color $%04x [first seen "
"at x: %" PRIu32 ", y: %" PRIu32 "]",
std::get<0>(conflicting), std::get<1>(conflicting), color.cgbColor(), x,
y);
// Do not report this combination again
conflicts.emplace_back(conflicting);
}
}
pixel(x, y) = color;
};
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) {
assignColor(x, y,
Rgba(row[x * 4], row[x * 4 + 1], row[x * 4 + 2], row[x * 4 + 3]));
}
}
} else {
assert(interlaceType == PNG_INTERLACE_ADAM7);
// For interlace to work properly, we must read the image `nbPasses` times
for (int pass = 0; pass < PNG_INTERLACE_ADAM7_PASSES; ++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) {
assignColor(x, y, Rgba(ptr[0], ptr[1], ptr[2], ptr[3]));
ptr += 4;
}
}
}
}
// We don't care about chunks after the image data (comments, etc.)
png_read_end(png, nullptr);
}
~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;
public:
uint32_t const x, y;
Tile(Png const &png, uint32_t x_, uint32_t y_) : _png(png), x(x_), y(y_) {}
Rgba 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;
std::pair<uint32_t, uint32_t> coords() const {
return {x + options.inputSlice.left, y + options.inputSlice.top};
}
Tile operator*() const {
return {parent._png, x + options.inputSlice.left, y + options.inputSlice.top};
}
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;
}
friend bool operator==(iterator const &lhs, iterator const &rhs) {
return lhs.coords() == rhs.coords(); // Compare the returned coord pairs
}
friend bool operator!=(iterator const &lhs, iterator const &rhs) {
return lhs.coords() != rhs.coords(); // Compare the returned coord pairs
}
};
public:
iterator begin() const { return {*this, _limit, 0, 0}; }
iterator end() const {
iterator it{*this, _limit, _width - 8, _height - 8}; // Last valid one...
return ++it; // ...now one-past-last!
}
};
public:
TilesVisitor visitAsTiles(bool columnMajor) const {
return {*this, columnMajor, options.inputSlice.width ? options.inputSlice.width * 8 : width,
options.inputSlice.height ? options.inputSlice.height * 8 : height};
}
};
class RawTiles {
/**
* 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 {
/**
* This field can either be a proto-palette ID, or `transparent` to indicate that the
* corresponding tile is fully transparent. If you are looking to get the palette ID for this
* attrmap entry while correctly handling the above, use `getPalID`.
*/
size_t protoPaletteID; // Only this field is used when outputting "unoptimized" data
uint8_t tileID; // This is the ID as it will be output to the tilemap
bool bank;
bool yFlip;
bool xFlip;
static constexpr decltype(protoPaletteID) transparent = SIZE_MAX;
size_t getPalID(DefaultInitVec<size_t> const &mappings) const {
return protoPaletteID == transparent ? 0 : mappings[protoPaletteID];
}
};
static std::tuple<DefaultInitVec<size_t>, std::vector<Palette>>
generatePalettes(std::vector<ProtoPalette> const &protoPalettes, Png const &png) {
// 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.verbosity >= Options::VERB_INTERM) {
fprintf(stderr, "Proto-palette mappings: (%zu palette%s)\n", nbPalettes,
nbPalettes != 1 ? "s" : "");
for (size_t i = 0; i < mappings.size(); ++i) {
fprintf(stderr, "%zu -> %zu\n", i, mappings[i]);
}
}
std::vector<Palette> palettes(nbPalettes);
// If the image contains at least one transparent pixel, force transparency in the first slot of
// all palettes
if (options.hasTransparentPixels) {
for (Palette &pal : palettes) {
pal.colors[0] = Rgba::transparent;
}
}
// Generate the actual palettes from the mappings
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 [embPalSize, embPalRGB, embPalAlpha] = png.getEmbeddedPal();
if (embPalRGB != nullptr) {
sorting::indexed(palettes, embPalSize, embPalRGB, embPalAlpha);
} else if (png.isSuitableForGrayscale()) {
sorting::grayscale(palettes, png.getColors().raw());
} else {
sorting::rgb(palettes);
}
return {mappings, palettes};
}
static std::tuple<DefaultInitVec<size_t>, std::vector<Palette>>
makePalsAsSpecified(std::vector<ProtoPalette> const &protoPalettes, Png const &png) {
if (options.palSpecType == Options::EMBEDDED) {
// Generate a palette spec from the first few colors in the embedded palette
auto [embPalSize, embPalRGB, embPalAlpha] = png.getEmbeddedPal();
if (embPalRGB == nullptr) {
fatal("`-c embedded` was given, but the PNG does not have an embedded palette!");
}
// Fill in the palette spec
options.palSpec.emplace_back(); // A single palette, with `#00000000`s (transparent)
assert(options.palSpec.size() == 1);
if (embPalSize > options.maxOpaqueColors()) { // Ignore extraneous colors if they are unused
embPalSize = options.maxOpaqueColors();
}
for (int i = 0; i < embPalSize; ++i) {
options.palSpec[0][i] = Rgba(embPalRGB[i].red, embPalRGB[i].green, embPalRGB[i].blue,
embPalAlpha ? embPalAlpha[i] : 0xFF);
}
}
// Convert the palette spec to actual palettes
std::vector<Palette> palettes(options.palSpec.size());
for (auto [spec, pal] : zip(options.palSpec, palettes)) {
for (size_t i = 0; i < options.nbColorsPerPal && spec[i].isOpaque(); ++i) {
pal[i] = spec[i].cgbColor();
}
}
auto listColors = [](auto const &list) {
static char buf[sizeof(", $XXXX, $XXXX, $XXXX, $XXXX")];
char *ptr = buf;
for (uint16_t cgbColor : list) {
sprintf(ptr, ", $%04x", cgbColor);
ptr += 7;
}
return &buf[2];
};
// Iterate through proto-palettes, and try mapping them to the specified palettes
DefaultInitVec<size_t> mappings(protoPalettes.size());
bool bad = false;
for (size_t i = 0; i < protoPalettes.size(); ++i) {
ProtoPalette const &protoPal = protoPalettes[i];
// Find the palette...
auto iter = std::find_if(palettes.begin(), palettes.end(), [&protoPal](Palette const &pal) {
// ...which contains all colors in this proto-pal
return std::all_of(protoPal.begin(), protoPal.end(), [&pal](uint16_t color) {
return std::find(pal.begin(), pal.end(), color) != pal.end();
});
});
if (iter == palettes.end()) {
assert(!protoPal.empty());
error("Could not fit tile colors [%s] in specified palettes", listColors(protoPal));
bad = true;
}
mappings[i] = iter - palettes.begin(); // Bogus value, but whatever
}
if (bad) {
fprintf(stderr, "note: The following palette%s specified:\n",
palettes.size() == 1 ? " was" : "s were");
for (Palette const &pal : palettes) {
fprintf(stderr, " [%s]\n", listColors(pal));
}
giveUp();
}
return {mappings, palettes};
}
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 (uint8_t i = 0; i < options.nbColorsPerPal; ++i) {
uint16_t color = palette.colors[i]; // Will return `UINT16_MAX` for unused slots
output.sputc(color & 0xFF);
output.sputc(color >> 8);
}
}
}
class TileData {
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:
// This is an index within the "global" pool; no bank info is encoded here
// It's marked as `mutable` so that it can be modified even on a `const` object;
// this is necessary because the `set` in which it's inserted refuses any modification for fear
// of altering the element's hash, but the tile ID is not part of it.
mutable uint16_t tileID;
static uint16_t rowBitplanes(Png::TilesVisitor::Tile const &tile, Palette const &palette,
uint32_t y) {
uint16_t row = 0;
for (uint32_t x = 0; x < 8; ++x) {
row <<= 1;
uint8_t index = palette.indexOf(tile.pixel(x, y).cgbColor());
assert(index < palette.size()); // The color should be in the palette
if (index & 1) {
row |= 1;
}
if (index & 2) {
row |= 0x100;
}
}
return row;
}
TileData(Png::TilesVisitor::Tile const &tile, Palette const &palette) : _hash(0) {
size_t writeIndex = 0;
for (uint32_t y = 0; y < 8; ++y) {
uint16_t bitplanes = rowBitplanes(tile, palette, y);
_data[writeIndex++] = bitplanes & 0xFF;
if (options.bitDepth == 2) {
_data[writeIndex++] = 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 ^= flipTable[bitplanes >> 8] << 8 | flipTable[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 {
// Check for strict equality first, as that can typically be optimized, and it allows
// hoisting the mirroring check out of the loop
if (_data == other._data) {
return MatchType::EXACT;
}
if (!options.allowMirroring) {
return MatchType::NOPE;
}
// Check if we have horizontal mirroring, which scans the array forward again
if (std::equal(_data.begin(), _data.end(), other._data.begin(),
[](uint8_t lhs, uint8_t rhs) { return lhs == flipTable[rhs]; })) {
return MatchType::HFLIP;
}
// Check if we have vertical or vertical+horizontal mirroring, for which we have to read
// bitplane *pairs* backwards
bool hasVFlip = true, hasVHFlip = true;
for (uint8_t i = 0; i < _data.size(); ++i) {
// Flip the bottom bit to get the corresponding row's bitplane 0/1
// (This works because the array size is even)
uint8_t lhs = _data[i], rhs = other._data[(15 - i) ^ 1];
if (lhs != rhs) {
hasVFlip = false;
}
if (lhs != flipTable[rhs]) {
hasVHFlip = false;
}
if (!hasVFlip && !hasVHFlip) {
return MatchType::NOPE; // If both have been eliminated, all hope is lost!
}
}
// If we have both (i.e. we have symmetry), default to vflip only
assert(hasVFlip || hasVHFlip);
return hasVFlip ? MatchType::VFLIP : MatchType::VHFLIP;
}
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 unoptimized {
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.output, std::ios_base::out | std::ios_base::binary);
uint64_t remainingTiles = (png.getWidth() / 8) * (png.getHeight() / 8);
if (remainingTiles <= options.trim) {
return;
}
remainingTiles -= options.trim;
for (auto [tile, attr] : zip(png.visitAsTiles(options.columnMajor), attrmap)) {
// If the tile is fully transparent, default to palette 0
Palette const &palette = palettes[attr.getPalID(mappings)];
for (uint32_t y = 0; y < 8; ++y) {
uint16_t bitplanes = TileData::rowBitplanes(tile, palette, y);
output.sputc(bitplanes & 0xFF);
if (options.bitDepth == 2) {
output.sputc(bitplanes >> 8);
}
}
--remainingTiles;
if (remainingTiles == 0) {
break;
}
}
assert(remainingTiles == 0);
}
static void outputMaps(DefaultInitVec<AttrmapEntry> const &attrmap,
DefaultInitVec<size_t> const &mappings) {
std::optional<std::filebuf> tilemapOutput, attrmapOutput, palmapOutput;
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);
}
if (!options.palmap.empty()) {
palmapOutput.emplace();
palmapOutput->open(options.palmap, std::ios_base::out | std::ios_base::binary);
}
uint8_t tileID = 0;
uint8_t bank = 0;
for (auto attr : attrmap) {
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 = attr.getPalID(mappings) & 7;
attrmapOutput->sputc(palID | bank << 3); // The other flags are all 0
}
if (palmapOutput.has_value()) {
palmapOutput->sputc(attr.getPalID(mappings));
}
++tileID;
}
}
} // namespace unoptimized
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 = static_cast<uint16_t>(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(); }
};
/**
* Generate tile data while deduplicating unique tiles (via mirroring if enabled)
* Additionally, while we have the info handy, convert from the 16-bit "global" tile IDs to
* 8-bit tile IDs + the bank bit; this will save the work when we output the data later (potentially
* twice)
*/
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;
for (auto [tile, attr] : zip(png.visitAsTiles(options.columnMajor), attrmap)) {
auto [tileID, matchType] = tiles.addTile(tile, palettes[mappings[attr.protoPaletteID]]);
attr.xFlip = matchType == TileData::HFLIP || matchType == TileData::VHFLIP;
attr.yFlip = matchType == TileData::VFLIP || matchType == TileData::VHFLIP;
attr.bank = tileID >= options.maxNbTiles[0];
attr.tileID =
(attr.bank ? tileID - options.maxNbTiles[0] : tileID) + options.baseTileIDs[attr.bank];
}
// Copy elision should prevent the contained `unordered_set` from being re-constructed
return tiles;
}
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 (auto iter = tiles.begin(), end = tiles.end() - options.trim; iter != end; ++iter) {
TileData const *tile = *iter;
assert(tile->tileID == tileID);
++tileID;
output.sputn(reinterpret_cast<char const *>(tile->data().data()), options.bitDepth * 8);
}
}
static void outputTilemap(DefaultInitVec<AttrmapEntry> const &attrmap) {
std::filebuf output;
output.open(options.tilemap, std::ios_base::out | std::ios_base::binary);
for (AttrmapEntry const &entry : attrmap) {
output.sputc(entry.tileID); // The tile ID has already been converted
}
}
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);
for (AttrmapEntry const &entry : attrmap) {
uint8_t attr = entry.xFlip << 5 | entry.yFlip << 6;
attr |= entry.bank << 3;
attr |= entry.getPalID(mappings) & 7;
output.sputc(attr);
}
}
static void outputPalmap(DefaultInitVec<AttrmapEntry> const &attrmap,
DefaultInitVec<size_t> const &mappings) {
std::filebuf output;
output.open(options.attrmap, std::ios_base::out | std::ios_base::binary);
for (AttrmapEntry const &entry : attrmap) {
output.sputc(entry.getPalID(mappings));
}
}
} // namespace optimized
void process() {
options.verbosePrint(Options::VERB_CFG, "Using libpng %s\n", png_get_libpng_ver(nullptr));
options.verbosePrint(Options::VERB_LOG_ACT, "Reading tiles...\n");
Png png(options.input); // This also sets `hasTransparentPixels` as a side effect
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.verbosity >= Options::VERB_INTERM) {
fputs("Image colors: [ ", stderr);
for (auto const &slot : colors) {
if (!slot.has_value()) {
continue;
}
fprintf(stderr, "#%08x, ", slot->toCSS());
}
fputs("]\n", stderr);
}
// 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) {
Rgba color = tile.pixel(x, y);
if (!color.isTransparent()) { // Do not count transparency in for packing
tileColors.add(color.cgbColor());
}
}
}
if (tileColors.empty()) {
// "Empty" proto-palettes screw with the packing process, so discard those
attrs.protoPaletteID = AttrmapEntry::transparent;
continue;
}
// Insert the proto-palette, making sure to avoid overlaps
for (size_t n = 0; n < protoPalettes.size(); ++n) {
switch (tileColors.compare(protoPalettes[n])) {
case ProtoPalette::WE_BIGGER:
protoPalettes[n] = tileColors; // Override them
// Remove any other proto-palettes that we encompass
// (Example [(0, 1), (0, 2)], inserting (0, 1, 2))
/* The following code does its job, except that references to the removed
* proto-palettes are not updated, causing issues.
* TODO: overlap might not be detrimental to the packing algorithm.
* Investigation is necessary, especially if pathological cases are found.
for (size_t i = protoPalettes.size(); --i != n;) {
if (tileColors.compare(protoPalettes[i]) == ProtoPalette::WE_BIGGER) {
protoPalettes.erase(protoPalettes.begin() + i);
}
}
*/
[[fallthrough]];
case ProtoPalette::THEY_BIGGER:
// Do nothing, they already contain us
attrs.protoPaletteID = n;
goto contained;
case ProtoPalette::NEITHER:
break; // Keep going
}
}
if (tileColors.size() > options.maxOpaqueColors()) {
fatal("Tile at (%" PRIu32 ", %" PRIu32 ") has %zu opaque colors, more than %" PRIu8 "!",
tile.x, tile.y, tileColors.size(), options.maxOpaqueColors());
}
attrs.protoPaletteID = protoPalettes.size();
if (protoPalettes.size() == AttrmapEntry::transparent) { // Check for overflow
fatal("Reached %zu proto-palettes... sorry, this image is too much for me to handle :(",
AttrmapEntry::transparent);
}
protoPalettes.push_back(tileColors);
contained:;
}
options.verbosePrint(Options::VERB_INTERM, "Image contains %zu proto-palette%s\n",
protoPalettes.size(), protoPalettes.size() != 1 ? "s" : "");
if (options.verbosity >= Options::VERB_INTERM) {
for (auto const &protoPal : protoPalettes) {
fputs("[ ", stderr);
for (uint16_t color : protoPal) {
fprintf(stderr, "$%04x, ", color);
}
fputs("]\n", stderr);
}
}
auto [mappings, palettes] = options.palSpecType == Options::NO_SPEC
? generatePalettes(protoPalettes, png)
: makePalsAsSpecified(protoPalettes, png);
if (options.verbosity >= Options::VERB_INTERM) {
for (auto &&palette : palettes) {
fputs("{ ", stderr);
for (uint16_t colorIndex : palette) {
fprintf(stderr, "%04" PRIx16 ", ", colorIndex);
}
fputs("}\n", stderr);
}
}
if (palettes.size() > options.nbPalettes) {
// If the palette generation is wrong, other (dependee) operations are likely to be
// nonsensical, so fatal-error outright
fatal("Generated %zu palettes, over the maximum of %" PRIu8, palettes.size(),
options.nbPalettes);
}
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(Options::VERB_LOG_ACT, "Generating unoptimized tile data...\n");
unoptimized::outputTileData(png, attrmap, palettes, mappings);
}
if (!options.tilemap.empty() || !options.attrmap.empty() || !options.palmap.empty()) {
options.verbosePrint(
Options::VERB_LOG_ACT,
"Generating unoptimized tilemap and/or attrmap and/or palmap...\n");
unoptimized::outputMaps(attrmap, mappings);
}
} else {
// All of these require the deduplication process to be performed to be output
options.verbosePrint(Options::VERB_LOG_ACT, "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(Options::VERB_LOG_ACT, "Generating optimized tile data...\n");
optimized::outputTileData(tiles);
}
if (!options.tilemap.empty()) {
options.verbosePrint(Options::VERB_LOG_ACT, "Generating optimized tilemap...\n");
optimized::outputTilemap(attrmap);
}
if (!options.attrmap.empty()) {
options.verbosePrint(Options::VERB_LOG_ACT, "Generating optimized attrmap...\n");
optimized::outputAttrmap(attrmap, mappings);
}
if (!options.palmap.empty()) {
options.verbosePrint(Options::VERB_LOG_ACT, "Generating optimized palmap...\n");
optimized::outputPalmap(attrmap, mappings);
}
}
}