summaryrefslogtreecommitdiff
path: root/jrrtilevq.h
diff options
context:
space:
mode:
Diffstat (limited to 'jrrtilevq.h')
-rw-r--r--jrrtilevq.h758
1 files changed, 758 insertions, 0 deletions
diff --git a/jrrtilevq.h b/jrrtilevq.h
new file mode 100644
index 0000000..1d65a7f
--- /dev/null
+++ b/jrrtilevq.h
@@ -0,0 +1,758 @@
+#ifndef INCLUDE_JRRTILEVQ_H
+#define INCLUDE_JRRTILEVQ_H
+
+#include <stddef.h>
+#include <limits.h>
+#include <float.h>
+#include <stdarg.h>
+#include <stdint.h> // C99
+#include <stdbool.h> // C99
+//#include <iso646.h> // don't use this
+//#include <stdalign.h> // C11
+//#include <stdnoreturn.h> // C11
+
+struct jrrtilevq_tilemap {
+ unsigned int map_w;
+ unsigned int map_h;
+ unsigned int tile_w;
+ unsigned int tile_h;
+ unsigned int n_tiles;
+ unsigned int tiles_cap;
+ void *mem;
+};
+
+int jrrtilevq(uint8_t* image, unsigned int width, unsigned int height, unsigned int tile_w, unsigned int tile_h, unsigned int target_n_tiles, unsigned int allowed_flips);
+
+int jrrtilevq_make_tilemap(struct jrrtilevq_tilemap* tilemap, const uint8_t* image, unsigned int width, unsigned int height, unsigned int tile_w, unsigned int tile_h, unsigned int allowed_transforms);
+
+int jrrtilevq_render_image(uint8_t* image, unsigned int width, unsigned int height, struct jrrtilevq_tilemap tilemap);
+
+void jrrtilevq_free(struct jrrtilevq_tilemap* tilemap);
+
+int jrrtilevq_pad_image(uint8_t** image, unsigned int *width, unsigned int *height, unsigned int tile_w, unsigned int tile_h, int offset_x, int offset_y);
+
+int jrrtilevq_normalize_flip(uint8_t *tile, unsigned int w, unsigned int h, unsigned int allowed_transforms);
+
+#ifdef JRRTILEVQ_IMPLEMENTATION
+
+
+#ifndef JRRTILEVQ_HASH_FUNCTION
+// http://www.isthe.com/chongo/tech/comp/fnv/index.html
+static uint64_t jrrtilevq_fnv1a(const void* data, size_t len)
+{
+ uint64_t hash = 0xcbf29ce484222325;
+ for (size_t i = 0; i < len; ++i) {
+ hash ^= ((const uint8_t*)data)[i];
+ hash *= 0x00000100000001B3;
+ }
+ return hash;
+}
+#define JRRTILEVQ_HASH_FUNCTION jrrtilevq_fnv1a
+#endif
+
+#include <stdlib.h> // malloc, free
+#include <string.h> // memcpy, memcmp
+
+int jrrtilevq_pad_image(uint8_t** image, unsigned int *width, unsigned int *height, unsigned int tile_w, unsigned int tile_h, int offset_x, int offset_y)
+{
+// if (!image || !(*image) || !width || !(*width) || !height || !(*height) || !tile_w || !tile_h)
+// return -1;
+ if (!image || !(*image))
+ return 1;
+
+ int old_width = *width;
+ int old_height = *height;
+ int left_pad = (offset_x < 0) ? (offset_x % tile_w) + tile_w : offset_x % tile_w;
+ int top_pad = (offset_y < 0) ? (offset_y % tile_h) + tile_h : offset_y % tile_h;
+ int new_width = old_width + left_pad;
+ int new_height = old_height + top_pad;
+ new_width = ((new_width + tile_w - 1) / tile_w) * tile_w;
+ new_height = ((new_height + tile_h - 1) / tile_h) * tile_h;
+
+ if ((old_width == new_width) && (old_height == new_height))
+ return 0;
+
+ uint8_t* new_image = calloc(new_width * new_height, sizeof(uint32_t));
+ if (!new_image)
+ return 1;
+
+ uint32_t* src = (uint32_t*)(*image);
+ uint32_t* dst = (uint32_t*)new_image;
+ for (int y = top_pad; y < top_pad + old_height; ++y) {
+ memcpy(dst + (y * new_width) + left_pad, src, old_width * sizeof(uint32_t));
+ src += old_width;
+ }
+
+ free(*image);
+ *image = new_image;
+ *width = new_width;
+ *height = new_height;
+ return 0;
+}
+
+static int jrrtilevq_mem_size(struct jrrtilevq_tilemap tilemap)
+{
+ // palette is limited to 255 colors and the don't care color,
+ // becasue the algorithm is not well suited for true-color images.
+ int palette_size = sizeof(uint32_t) * 256;
+ int map_size = tilemap.map_w * tilemap.map_h * sizeof(uint64_t);
+ int map_attr_size = tilemap.map_w * tilemap.map_h * sizeof(uint8_t);
+ int tiles_size = tilemap.tile_w * tilemap.tile_h * tilemap.tiles_cap;
+ int counts_size = tilemap.tiles_cap * sizeof(int);
+ return palette_size + map_size + map_attr_size + tiles_size + counts_size;
+}
+
+void jrrtilevq_free(struct jrrtilevq_tilemap* tilemap)
+{
+ if(!tilemap)
+ return;
+ free(tilemap->mem);
+ memset(tilemap, 0x00, sizeof(*tilemap));
+}
+
+static uint64_t jrrtilevq_hashtable_add(struct jrrtilevq_tilemap* tilemap, const uint8_t* tile_buf, int n)
+{
+ if (!tilemap)
+ return 0;
+
+ int tile_size = tilemap->tile_w * tilemap->tile_h;
+ uint64_t tile_hash = JRRTILEVQ_HASH_FUNCTION(tile_buf, tile_size);
+
+ uint32_t* palette = (uint32_t*)(tilemap->mem);
+ uint64_t* map = (uint64_t*)(palette + 256);
+ uint8_t* map_attr = (uint8_t*)(map + (tilemap->map_w * tilemap->map_h));
+ uint8_t* tiles = (uint8_t*)(map_attr + (tilemap->map_w * tilemap->map_h));
+ unsigned int* counts = (unsigned int*)(tiles + (tilemap->tiles_cap * tile_size));
+
+ int tile_slot = tile_hash % tilemap->tiles_cap;
+ while (counts[tile_slot] && memcmp(tiles + (tile_slot * tile_size), tile_buf, tile_size)) {
+ tile_slot = (tile_slot + 1) % tilemap->tiles_cap;
+ }
+ if (!counts[tile_slot]) {
+ memcpy(tiles + (tile_slot * tile_size), tile_buf, tile_size);
+ tilemap->n_tiles += 1;
+ }
+ counts[tile_slot] += n;
+
+ return tile_hash;
+}
+
+static unsigned int jrrtilevq_hashtable_remove(struct jrrtilevq_tilemap* tilemap, const uint8_t* tile_buf)
+{
+ if (!tilemap)
+ return 0;
+
+ int tile_size = tilemap->tile_w * tilemap->tile_h;
+
+ uint32_t* palette = (uint32_t*)(tilemap->mem);
+ uint64_t* map = (uint64_t*)(palette + 256);
+ uint8_t* map_attr = (uint8_t*)(map + (tilemap->map_w * tilemap->map_h));
+ uint8_t* tiles = (uint8_t*)(map_attr + (tilemap->map_w * tilemap->map_h));
+ unsigned int* counts = (unsigned int*)(tiles + (tilemap->tiles_cap * tile_size));
+
+ uint64_t tile_hash = JRRTILEVQ_HASH_FUNCTION(tile_buf, tile_size);
+ unsigned int tile_slot = tile_hash % tilemap->tiles_cap;
+ while (counts[tile_slot] && memcmp(tiles + (tile_slot * tile_size), tile_buf, tile_size)) {
+ tile_slot = (tile_slot + 1) % tilemap->tiles_cap;
+ }
+
+ unsigned int amount_removed = counts[tile_slot];
+ if (!amount_removed)
+ return 0;
+
+ unsigned int removed_slot = tile_slot;
+ unsigned int new_slot;
+
+ counts[removed_slot] = 0;
+ while (1) {
+ tile_slot = (tile_slot + 1) % tilemap->tiles_cap;
+ if (!counts[tile_slot])
+ break;
+ tile_hash = JRRTILEVQ_HASH_FUNCTION(tiles + (tile_slot * tile_size), tile_size);
+ new_slot = tile_hash % tilemap->tiles_cap;
+ if ( (removed_slot <= tile_slot)
+ ? ((removed_slot < new_slot) && (new_slot <= tile_slot))
+ : ((removed_slot < new_slot) || (new_slot <= tile_slot))
+ ) {
+ continue;
+ }
+ memcpy(tiles + (removed_slot * tile_size), tiles + (tile_slot * tile_size), tile_size);
+ counts[removed_slot] = counts[tile_slot];
+ removed_slot = tile_slot;
+ counts[removed_slot] = 0;
+ }
+
+ --(tilemap->n_tiles);
+
+ return amount_removed;
+}
+
+static void jrrtilevq_resize_hashtable(struct jrrtilevq_tilemap* tilemap, int new_tiles_cap)
+{
+ if (!tilemap)
+ return;
+
+ struct jrrtilevq_tilemap new_tilemap;
+ int tile_size = tilemap->tile_w * tilemap->tile_h;
+
+ new_tilemap.map_w = tilemap->map_w;
+ new_tilemap.map_h = tilemap->map_h;
+ new_tilemap.tile_w = tilemap->tile_w;
+ new_tilemap.tile_h = tilemap->tile_h;
+ new_tilemap.n_tiles = 0;
+ new_tilemap.tiles_cap = new_tiles_cap;
+
+ size_t new_mem_size = jrrtilevq_mem_size(new_tilemap);
+ new_tilemap.mem = calloc(new_mem_size, sizeof(uint8_t));
+ if (!new_tilemap.mem)
+ return;
+
+ uint32_t* palette = (uint32_t*)(tilemap->mem);
+ uint64_t* map = (uint64_t*)(palette + 256);
+ uint8_t* map_attr = (uint8_t*)(map + (tilemap->map_w * tilemap->map_h));
+ uint8_t* tiles = (uint8_t*)(map_attr + (tilemap->map_w * tilemap->map_h));
+ unsigned int* counts = (unsigned int*)(tiles + (tilemap->tiles_cap * tile_size));
+
+ size_t pal_and_map_size = (256 * sizeof(uint32_t)) + (tilemap->map_w * tilemap->map_h * sizeof(uint64_t));
+
+ memcpy(new_tilemap.mem, tilemap->mem, pal_and_map_size);
+
+ //uint32_t* new_palette = (uint32_t*)(new_tilemap.mem);
+ //uint64_t* new_map = (uint64_t*)(new_palette + 256);
+ //uint8_t* new_map_attr = (uint8_t*)(map + (new_tilemap.map_w * new_tilemap.map_h));
+ //uint8_t* new_tiles = (uint8_t*)(new_map_attr + (new_tilemap.map_w * new_tilemap.map_h));
+ //int* new_counts = (unsigned int*)(new_tiles + (new_tilemap.tiles_cap * tile_size));
+
+ unsigned int slot;
+ for (slot = 0; slot < tilemap->tiles_cap; ++slot) {
+ if (counts[slot]) {
+ jrrtilevq_hashtable_add(&new_tilemap, tiles + (slot * tile_size), counts[slot]);
+ }
+ }
+
+ free(tilemap->mem);
+ tilemap->mem = new_tilemap.mem;
+ tilemap->n_tiles = new_tilemap.n_tiles;
+ tilemap->tiles_cap = new_tilemap.tiles_cap;
+}
+
+
+static void jrrtilevq_map_search_and_replace(struct jrrtilevq_tilemap* tilemap, uint64_t tile_m_hash, uint64_t tile_a_hash, uint64_t tile_b_hash, unsigned int t_a, unsigned int t_b)
+{
+ if (!tilemap)
+ return;
+ unsigned int map_w = tilemap->map_w;
+ unsigned int map_h = tilemap->map_h;
+
+ //int tile_size = tilemap->tile_w * tilemap->tile_h;
+
+ uint32_t* palette = (uint32_t*)(tilemap->mem);
+ uint64_t* map = (uint64_t*)(palette + 256);
+ uint8_t* map_attr = (uint8_t*)(map + (tilemap->map_w * tilemap->map_h));
+ //uint8_t* tiles = (uint8_t*)(map_attr + (tilemap->map_w * tilemap->map_h));
+ //unsigned int* counts = (unsigned int*)(tiles + (tilemap->tiles_cap * tile_size));
+
+ unsigned int tx, ty, temp;
+ for (ty = 0; ty < map_h; ++ty) {
+ for (tx = 0; tx < map_w; ++tx) {
+ if (map[ty * map_w + tx] == tile_a_hash) {
+ map[ty * map_w + tx] = tile_m_hash;
+ temp = map_attr[ty * map_w + tx];
+ if (temp & 4) {
+ // if source was transposed,
+ // then applying horizontal flips behaves
+ // like vertical flips and vice versa
+ temp ^= ((t_a & 1) << 1) | ((t_a & 2) >> 1) | (t_a & 4);
+ } else {
+ temp ^= t_a;
+ }
+ map_attr[ty * map_w + tx] = temp;
+ } else if (map[ty * map_w + tx] == tile_b_hash) {
+ map[ty * map_w + tx] = tile_m_hash;
+ temp = map_attr[ty * map_w + tx];
+ if (temp & 4) {
+ temp ^= ((t_b & 1) << 1) | ((t_b & 2) >> 1) | (t_b & 4);
+ } else {
+ temp ^= t_b;
+ }
+ map_attr[ty * map_w + tx] = temp;
+ }
+ }
+ }
+}
+
+
+static unsigned int jrrtilevq_tile_coords(unsigned int x, unsigned int y, unsigned int w, unsigned int h, unsigned int t, bool in_transform)
+{
+ unsigned int temp;
+ if ((in_transform) && (t & 4)) {
+ temp = x;
+ x = y;
+ y = temp;
+ }
+ if (t & 1)
+ x = w - x - 1;
+ if (t & 2)
+ y = h - y - 1;
+ if ((!in_transform) && (t & 4)) {
+ temp = x;
+ x = y;
+ y = temp;
+ }
+ return y * w + x;
+}
+
+// modifies tile, and returns the type of flip used.
+int jrrtilevq_normalize_flip(uint8_t *tile, unsigned int w, unsigned int h, unsigned int allowed_transforms)
+{
+ if (!tile || !w || !h)
+ return 0;
+ unsigned int x, y, i, i2, t, p, min_index;
+ unsigned int canidate_transforms = allowed_transforms | 1;
+ if (allowed_transforms == 1)
+ return 0;
+ uint8_t tile_copy[w*h];
+ memcpy(tile_copy, tile, w*h);
+ for (y = 0; y < h; ++y) {
+ for (x = 0; x < w; ++x) {
+ min_index = 256;
+ p = 0;
+ for (t = 0; t < 8; ++t) {
+ if (canidate_transforms & (1<<t)) {
+ i = jrrtilevq_tile_coords(x, y, w, h, t, 1);
+ if (tile_copy[i] < min_index)
+ min_index = tile_copy[i];
+ ++p;
+ }
+ }
+ if (p <= 1)
+ goto found_transform;
+ for (t = 0; t < 8; ++t) {
+ if (canidate_transforms & (1<<t)) {
+ i = jrrtilevq_tile_coords(x, y, w, h, t, 1);
+ if (min_index < tile_copy[i])
+ canidate_transforms &= ~(1<<t);
+ }
+ }
+ }
+ }
+found_transform:
+ for (t = 0; t < 8; ++t) {
+ if (canidate_transforms & (1<<t))
+ break;
+ }
+ for (y = 0; y < h; ++y) {
+ for (x = 0; x < w; ++x) {
+ i = y * w + x;
+ i2 = jrrtilevq_tile_coords(x, y, w, h, t, 1);
+ tile[i] = tile_copy[i2];
+ }
+ }
+ return t;
+}
+
+static unsigned int jrrtilevq_minimum_changed_pixels(const uint8_t *tile_a, const uint8_t *tile_b, unsigned int w, unsigned int h, unsigned int counts_a, unsigned int counts_b, unsigned int* t_a, unsigned int* t_b, unsigned int allowed_transforms)
+{
+ unsigned int x, y, i1, i2, t1, t2;
+ unsigned int count = 0;
+ allowed_transforms |= 1;
+ unsigned int minimum_count = UINT_MAX;
+ unsigned int min_t_a = 0;
+ unsigned int min_t_b = 0;
+ for (t1 = 0; t1 < 8; ++t1) {
+ if (!(1<<t1 & allowed_transforms))
+ continue;
+ for (t2 = 0; t2 < 8; ++t2) {
+ if (!(1<<t2 & allowed_transforms))
+ continue;
+ count = 0;
+ for (y = 0; y < h; ++y) {
+ for (x = 0; x < w; ++x) {
+ i1 = jrrtilevq_tile_coords(x, y, w, h, t1, 1);
+ i2 = jrrtilevq_tile_coords(x, y, w, h, t2, 1);
+ if ((tile_a[i1] == tile_b[i2]) || !tile_a[i1] || !tile_b[i2])
+ continue;
+ if (tile_a[i1] != 0xff)
+ count += counts_a;
+ if (tile_b[i2] != 0xff)
+ count += counts_b;
+ }
+ }
+ if (count < minimum_count) {
+ minimum_count = count;
+ min_t_a = t1;
+ min_t_b = t2;
+ }
+ }
+ }
+/* if ((minimum_count <=10) && ((min_t_a == 5) || (min_t_b == 5) || (min_t_a == 6) || (min_t_b == 6))) {
+ for (y = 0; y < h; ++y) {
+ for (x = 0; x < w; ++x) {
+ printf("%02x ", tile_a[y * w + x]);
+ }
+ printf(" ");
+ for (x = 0; x < w; ++x) {
+ printf("%02x ", tile_b[y * w + x]);
+ }
+ printf("\n");
+ }
+ printf("t_a: %d, t_b: %d, counts_a: %d, counts_b: %d, minimum_count: %d\n", min_t_a, min_t_b, counts_a, counts_b, minimum_count);
+ for (y = 0; y < h; ++y) {
+ for (x = 0; x < w; ++x) {
+ i1 = jrrtilevq_tile_coords(x, y, w, h, min_t_a, 1);
+ printf("%02x ", tile_a[i1]);
+ }
+ printf(" ");
+ for (x = 0; x < w; ++x) {
+ i2 = jrrtilevq_tile_coords(x, y, w, h, min_t_b, 1);
+ printf("%02x ", tile_b[i2]);
+ }
+ printf(" ");
+ for (x = 0; x < w; ++x) {
+ i1 = jrrtilevq_tile_coords(x, y, w, h, min_t_a, 1);
+ i2 = jrrtilevq_tile_coords(x, y, w, h, min_t_b, 1);
+ if (tile_a[i1] != tile_b[i2])
+ printf("xx ");
+ else
+ printf(".. ");
+ }
+ printf("\n");
+ }
+ getchar();
+ }*/
+ *t_a = min_t_a;
+ *t_b = min_t_b;
+ return minimum_count;
+}
+
+
+// Convert a randomized 64 bit int to a double in the range 0.0 <= x < 1.0
+// Idea stolen from https://github.com/mattiasgustavsson/libs/blob/main/rnd.h
+static double float_from_u64(uint64_t value)
+{
+ uint64_t exponent = 0x3ff;
+ uint64_t mantissa = value >> 12;
+ uint64_t result = ( exponent << 52 ) | mantissa;
+ double fresult;
+ memcpy(&fresult, &result, sizeof(double));
+ return fresult - 1.0;
+}
+
+static void jrrtilevq_make_diff_tile(uint8_t* merged_tile, const uint8_t* tile_a, const uint8_t* tile_b, unsigned int w, unsigned int h, unsigned int t_a, unsigned int t_b, double bias)
+{
+ unsigned int x, y, i1, i2, c;
+ uint64_t rand = JRRTILEVQ_HASH_FUNCTION(tile_a, w*h);
+ rand ^= JRRTILEVQ_HASH_FUNCTION(tile_b, w*h);
+ rand |= 1;
+ for (y = 0; y < h; ++y) {
+ for (x = 0; x < w; ++x) {
+ i1 = jrrtilevq_tile_coords(x, y, w, h, t_a, 1);
+ i2 = jrrtilevq_tile_coords(x, y, w, h, t_b, 1);
+ // if either index is 0 then take the other index
+ // if both are not 0 and also not equal then set the merge flag 0xff.
+ c = tile_a[i1];
+ //if (tile_a[i1] != tile_b[i2])
+ // c = 0xff;
+ if (tile_a[i1] != tile_b[i2]) {
+ //printf("%f\n", float_from_u64(rand));
+ if (float_from_u64(rand) < bias)
+ c = tile_a[i1];
+ else
+ c = tile_b[i2];
+ // random generator is xorshift64
+ rand ^= rand << 13;
+ rand ^= rand >> 7;
+ rand ^= rand << 17;
+ }
+ if (!tile_a[i1])
+ c = tile_b[i2];
+ if (!tile_b[i2])
+ c = tile_a[i1];
+ merged_tile[y * w + x] = c;
+ }
+ }
+}
+
+
+int jrrtilevq_make_tilemap(struct jrrtilevq_tilemap* tilemap, const uint8_t* image, unsigned int width, unsigned int height, unsigned int tile_w, unsigned int tile_h, unsigned int allowed_transforms)
+{
+ if (!tilemap || !image)
+ return 1;
+
+ struct jrrtilevq_tilemap tm = {0};
+
+ uint8_t tile_buf[tile_w * tile_h];
+
+ unsigned int map_w = width / tile_w;
+ unsigned int map_h = height / tile_h;
+ unsigned int tiles_cap = 1024;
+
+ tm.map_w = map_w;
+ tm.map_h = map_h;
+ tm.tile_w = tile_w;
+ tm.tile_h = tile_h;
+ tm.tiles_cap = tiles_cap;
+ size_t mem_size = jrrtilevq_mem_size(tm);
+
+ tm.mem = calloc(mem_size, sizeof(uint8_t));
+ if (!tm.mem)
+ return 1;
+
+ uint32_t* palette = (uint32_t*)(tm.mem);
+ uint64_t* map = (uint64_t*)(palette + 256);
+ uint8_t* map_attr = (uint8_t*)(map + (map_w * map_h));
+ //uint8_t* tiles = (uint8_t*)(map_attr + (map_w * map_h));
+ //int* counts = (unsigned int*)(tiles + tiles_cap);
+
+ unsigned int ty, tx, y, x, pal_index, pal_used, tansform;
+ uint32_t pixel;
+ uint64_t tile_hash;
+ pal_used = 1; // reserve don't care color
+ palette[0] = 0xffff00ff;
+ palette[255] = 0xff0000ff;
+ for (ty = 0; ty < map_h; ++ty) {
+ for (tx = 0; tx < map_w; ++tx) {
+ for (y = 0; y < tile_h; ++y) {
+ for (x = 0; x < tile_w; ++x) {
+ pixel = ((uint32_t*)(image))[(ty * (tile_h * map_w * tile_w)) + (y * (map_w * tile_w)) + (tx * tile_w) + x];
+ pal_index = 0;
+ if ((pixel & 0xff000000) >= 0x80000000) {
+ for (pal_index = 0; pal_index < pal_used; ++pal_index) {
+ if(pixel == palette[pal_index]) {
+ break;
+ }
+ }
+ if (pal_index == pal_used) {
+ if (pal_used >= 255) {
+ // abort if there's more then 255 indexes.
+ // the 255'th index is more internal marking
+ free(tm.mem);
+ return 1;
+ }
+ palette[pal_index] = pixel;
+ ++pal_used;
+ }
+ }
+ tile_buf[y * tile_w + x] = pal_index;
+ }
+ }
+ tansform = jrrtilevq_normalize_flip(tile_buf, tile_w, tile_h, allowed_transforms);
+ tile_hash = jrrtilevq_hashtable_add(&tm, tile_buf, 1);
+ map[ty * map_w + tx] = tile_hash;
+ map_attr[ty * map_w + tx] = tansform;
+ //printf("%d", tansform);
+ if ((tm.n_tiles * 5) > (tm.tiles_cap * 4)) {
+ // resize the hash table when >%80 full
+ jrrtilevq_resize_hashtable(&tm, tm.tiles_cap * 2);
+ palette = (uint32_t*)(tm.mem);
+ map = (uint64_t*)(palette + 256);
+ map_attr = (uint8_t*)(map + (map_w * map_h));
+ }
+ }
+ //printf("\n");
+ }
+
+ memcpy(tilemap, &tm, sizeof(tm));
+ return 0;
+}
+
+int jrrtilevq_render_image(uint8_t* image, unsigned int width, unsigned int height, struct jrrtilevq_tilemap tilemap)
+{
+ if ((!image) || (width < (tilemap.map_w * tilemap.tile_w)) || (height < (tilemap.map_h * tilemap.tile_h)))
+ return 1;
+
+ memset(image, 0x00, width * height * sizeof(uint32_t));
+
+ int tile_size = tilemap.tile_w * tilemap.tile_h;
+
+ uint32_t* palette = (uint32_t*)(tilemap.mem);
+ uint64_t* map = (uint64_t*)(palette + 256);
+ uint8_t* map_attr = (uint8_t*)(map + (tilemap.map_w * tilemap.map_h));
+ uint8_t* tiles = (uint8_t*)(map_attr + (tilemap.map_w * tilemap.map_h));
+ unsigned int* counts = (unsigned int*)(tiles + (tilemap.tiles_cap * tile_size));
+
+ int map_w = tilemap.map_w;
+ int map_h = tilemap.map_h;
+ int tile_w = tilemap.tile_w;
+ int tile_h = tilemap.tile_h;
+ int tiles_cap = tilemap.tiles_cap;
+
+ int tx, ty, x, y, i, pal_index, t;
+ uint32_t pixel;
+ int tile_slot;
+ uint64_t tile_entry, tile_hash;
+ for (ty = 0; ty < map_h; ++ty) {
+ for (tx = 0; tx < map_w; ++tx) {
+ tile_entry = map[ty * map_w + tx];
+ tile_slot = tile_entry % tiles_cap;
+ tile_hash = JRRTILEVQ_HASH_FUNCTION(tiles + (tile_slot * tile_size), tile_size);
+ while ((tile_hash != tile_entry) && counts[tile_slot]) {
+ tile_slot = (tile_slot + 1) % tiles_cap;
+ tile_hash = JRRTILEVQ_HASH_FUNCTION(tiles + (tile_slot * tile_size), tile_size);
+ }
+ if (!counts[tile_slot]) {
+ pixel = 0xffff00ff;
+ for (y = 0; y < tile_h; ++y) {
+ for (x = 0; x < tile_w; ++x) {
+ ((uint32_t*)(image))[(ty * (tile_h * width)) + (y * width) + (tx * tile_w) + x] = pixel;
+ }
+ }
+ continue;
+ }
+ t = map_attr[ty * map_w + tx];
+ for (y = 0; y < tile_h; ++y) {
+ for (x = 0; x < tile_w; ++x) {
+ i = jrrtilevq_tile_coords(x, y, tile_w, tile_h, t, 0);
+ pal_index = tiles[(tile_slot * tile_size) + i];
+ pixel = palette[pal_index];
+ //if ((i < 4) || (i == tile_w))
+ // pixel = 0xff00ff00;
+ ((uint32_t*)(image))[(ty * (tile_h * width)) + (y * width) + (tx * tile_w) + x] = pixel;
+ }
+ }
+ }
+ }
+
+ return 0;
+}
+
+/*#include <stdio.h>
+void debug_render_and_wait(struct jrrtilevq_tilemap tilemap)
+{
+ static int frame_no = 0;
+ char filename_buffer[256];
+
+ printf("map_w: %d, map_h: %d, tile_w: %d, tile_h: %d\n", tilemap.map_w, tilemap.map_h, tilemap.tile_w, tilemap.tile_h);
+
+ unsigned int image_width = tilemap.map_w * tilemap.tile_w;
+ unsigned int image_height = tilemap.map_h * tilemap.tile_h;
+ uint8_t* image = malloc(image_width * image_height * sizeof(uint32_t));
+ jrrtilevq_render_image(image, image_width, image_height, tilemap);
+ snprintf(filename_buffer, 256, "__debug_frames/%04d.png", frame_no);
+
+ lodepng_encode32_file(filename_buffer, image, image_width, image_height);
+ free(image);
+ printf("cap: %d, n: %d\n", tilemap.tiles_cap, tilemap.n_tiles);
+ ++frame_no;
+ getchar();
+}*/
+
+
+int jrrtilevq(uint8_t* image, unsigned int width, unsigned int height, unsigned int tile_w, unsigned int tile_h, unsigned int target_n_tiles, unsigned int allowed_transforms)
+{
+ struct jrrtilevq_tilemap tilemap;
+
+ if (tile_w != tile_h)
+ allowed_transforms &= 0x0f; // disable matrix translation if not square.
+ allowed_transforms |= 1; // always allow identity of course.
+
+ //printf("allowed_transforms: %d\n", allowed_transforms);
+
+ if(jrrtilevq_make_tilemap(&tilemap, image, width, height, tile_w, tile_h, allowed_transforms))
+ return 1;
+
+ int tile_size = tile_w * tile_h;
+ uint8_t tile_a_buf[tile_size];
+ uint8_t tile_b_buf[tile_size];
+ uint8_t tile_m_buf[tile_size];
+
+ uint32_t* palette = (uint32_t*)(tilemap.mem);
+ uint64_t* map = (uint64_t*)(palette + 256);
+ uint8_t* map_attr = (uint8_t*)(map + (tilemap.map_w * tilemap.map_h));
+ uint8_t* tiles = (uint8_t*)(map_attr + (tilemap.map_w * tilemap.map_h));
+ unsigned int* counts = (unsigned int*)(tiles + (tilemap.tiles_cap * tile_size));
+
+ unsigned int d;
+ unsigned int d_threshold = 2;
+ unsigned int t_a, t_b;
+
+// int max_count = 0;
+ unsigned int last_changed_slot = 0;
+/* for (unsigned int slot = 0; slot < tilemap.tiles_cap; ++slot) {
+ // find the "background tile" so that most of the dont care pixels
+ // will match to it.
+ if (!counts[slot])
+ continue;
+ if (max_count < counts[slot]) {
+ max_count = counts[slot];
+ last_changed_slot = slot;
+ }
+ }
+ printf("max_count: %d, last_changed_slot %d\n", max_count, last_changed_slot);*/
+
+ unsigned int d_min = UINT_MAX;
+
+ //debug_render_and_wait(tilemap);
+
+ while (target_n_tiles < tilemap.n_tiles) {
+ //printf("Current number of tiles: %d\n", tilemap.n_tiles);
+reset_pass:
+ d_min = UINT_MAX;
+ for (unsigned int slot_a_count = 0; slot_a_count < tilemap.tiles_cap; ++slot_a_count) {
+ unsigned int slot_a = (slot_a_count + last_changed_slot) % tilemap.tiles_cap;
+ if (!counts[slot_a])
+ continue;
+ for (unsigned int slot_b_count = slot_a_count+1; slot_b_count < tilemap.tiles_cap; ++slot_b_count) {
+ unsigned int slot_b = (slot_b_count + last_changed_slot) % tilemap.tiles_cap;
+ if (!counts[slot_b])
+ continue;
+ if ((counts[slot_a] > d_threshold) && (counts[slot_b] > d_threshold))
+ continue;
+ d = jrrtilevq_minimum_changed_pixels(tiles + (slot_a * tile_size), tiles + (slot_b * tile_size), tile_w, tile_h, counts[slot_a], counts[slot_b], &t_a, &t_b, allowed_transforms);
+ //d *= counts[slot_a] + counts[slot_b];
+ if (d < d_min)
+ d_min = d;
+ if (d <= d_threshold) {
+ //printf("slot_a: %d, slot_b: %d, d: %d, d_min: %d, d_threshold: %d, t_a: %d, t_b: %d, counts[a]: %d, counts[b]: %d\n", slot_a, slot_b, d, d_min, d_threshold, t_a, t_b, counts[slot_a], counts[slot_b]);
+ memcpy(tile_a_buf, tiles + (slot_a * tile_size), tile_size);
+ memcpy(tile_b_buf, tiles + (slot_b * tile_size), tile_size);
+ uint64_t tile_a_hash = JRRTILEVQ_HASH_FUNCTION(tile_a_buf, tile_size);
+ uint64_t tile_b_hash = JRRTILEVQ_HASH_FUNCTION(tile_b_buf, tile_size);
+ double bias = (double)counts[slot_b] / (double)(counts[slot_a] + counts[slot_b]);
+ jrrtilevq_make_diff_tile(tile_m_buf, tile_a_buf, tile_b_buf, tile_w, tile_h, t_a, t_b, bias);
+ unsigned int t_n = jrrtilevq_normalize_flip(tile_m_buf, tile_w, tile_h, allowed_transforms);
+ if (t_a & 4) {
+ t_a ^= ((t_n & 1) << 1) | ((t_n & 2) >> 1) | (t_n & 4);
+ } else {
+ t_a ^= t_n;
+ }
+ if (t_b & 4) {
+ t_b ^= ((t_n & 1) << 1) | ((t_n & 2) >> 1) | (t_n & 4);
+ } else {
+ t_b ^= t_n;
+ }
+ unsigned int tile_m_count = 0;
+ tile_m_count += jrrtilevq_hashtable_remove(&tilemap, tile_a_buf);
+ tile_m_count += jrrtilevq_hashtable_remove(&tilemap, tile_b_buf);
+ uint64_t tile_m_hash = jrrtilevq_hashtable_add(&tilemap, tile_m_buf, tile_m_count);
+
+ jrrtilevq_map_search_and_replace(&tilemap, tile_m_hash, tile_a_hash, tile_b_hash, t_a, t_b);
+
+ palette = (uint32_t*)(tilemap.mem);
+ map = (uint64_t*)(palette + 256);
+ map_attr = (uint8_t*)(map + (tilemap.map_w * tilemap.map_h));
+ tiles = (uint8_t*)(map_attr + (tilemap.map_w * tilemap.map_h));
+ counts = (unsigned int*)(tiles + (tilemap.tiles_cap * tile_size));
+
+ //debug_render_and_wait(tilemap);
+
+ // slot_a has been removed, so break out of the slot_b loop
+ // to continue.
+ if (tilemap.n_tiles <= target_n_tiles)
+ goto done;
+ last_changed_slot = slot_a;
+ goto reset_pass;
+ }
+ }
+ }
+ d_threshold = d_min;
+ }
+done:
+
+ jrrtilevq_render_image(image, width, height, tilemap);
+ jrrtilevq_free(&tilemap);
+ return 0;
+}
+
+#endif // JRRTILEVQ_IMPLEMENTATION
+#endif // INCLUDE_JRRTILEVQ_H