#include <assert.h>
#include <errno.h>
#include <fcntl.h>
#include <inttypes.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/mman.h>
#include <sys/stat.h>
#include <unistd.h>

#include "common/grow.h"
#include "sfdo-icon/internal.h"

#define CHAIN_END (0xFFFFFFFF)

struct sfdo_icon_cache_image {
	const char *name; // Borrowed from data
	size_t name_len;
	int formats; // enum sfdo_icon_format
	size_t next_i; // -1 if last
};

struct sfdo_icon_cache_dir {
	const char *name; // Borrowed from data
	size_t name_len;
	size_t start_i, end_i;
};

struct sfdo_icon_cache {
	char *data; // mmap'ed
	size_t size;
	struct sfdo_icon_cache_dir *dirs;
	size_t n_dirs;
	struct sfdo_icon_cache_image *images;
};

struct sfdo_icon_cache_loader {
	struct sfdo_icon_cache *cache;
	struct sfdo_logger *logger;
};

static bool read_card16(struct sfdo_icon_cache_loader *loader, size_t offset, uint16_t *out) {
	if (offset > loader->cache->size - 2) {
		logger_write(loader->logger, SFDO_LOG_LEVEL_ERROR,
				"Failed to read CARD16: offset %zu is out of range", offset);
		return false;
	}
	const uint8_t *data = (uint8_t *)&loader->cache->data[offset];
	*out = (uint16_t)(((uint16_t)data[0] << 8) | ((uint16_t)data[1] << 0));
	return true;
}

static bool read_card32(struct sfdo_icon_cache_loader *loader, size_t offset, uint32_t *out) {
	if (offset > loader->cache->size - 4) {
		logger_write(loader->logger, SFDO_LOG_LEVEL_ERROR,
				"Failed to read CARD16: offset %zu is out of range", offset);
		return false;
	}
	const uint8_t *data = (uint8_t *)&loader->cache->data[offset];
	*out = (uint32_t)(((uint32_t)data[0] << 24) | ((uint32_t)data[1] << 16) |
			((uint32_t)data[2] << 8) | ((uint32_t)data[3] << 0));
	return true;
}

static bool read_str(
		struct sfdo_icon_cache_loader *loader, size_t offset, const char **out, size_t *out_len) {
	if (offset > loader->cache->size) {
		logger_write(loader->logger, SFDO_LOG_LEVEL_ERROR,
				"Failed to read a string: offset %zu is out of range", offset);
		return false;
	}

	size_t limit = loader->cache->size - offset;
	*out = &loader->cache->data[offset];
	*out_len = strnlen(*out, limit);

	if (*out_len >= limit) {
		logger_write(loader->logger, SFDO_LOG_LEVEL_ERROR,
				"Failed to read a string: no NUL terminator found");
		return false;
	}
	return true;
}

static bool ensure_no_loop(struct sfdo_icon_cache_loader *loader, uint32_t x0) {
	// Brent's cycle detection algorithm
	// https://maths-people.anu.edu.au/~brent/pd/rpb051i.pdf
	// u = 0, Q = 2

	uint32_t y = x0;
	uint32_t k = 0;
	for (uint32_t r = 2;; r *= 2) {
		uint32_t x = y;

		for (; k < r; k++) {
			if (y == CHAIN_END) {
				return true;
			} else if (!read_card32(loader, y, &y)) {
				return false;
			} else if (x == y) {
				// Loop
				logger_write(
						loader->logger, SFDO_LOG_LEVEL_ERROR, "Hash map bucket contains a loop");
				return false;
			}
		}
	}
}

static bool load_cache(struct sfdo_icon_cache_loader *loader) {
	uint16_t major, minor;
	if (!read_card16(loader, 0, &major) || !read_card16(loader, 2, &minor)) {
		return false;
	}

	if (major != 1 || minor != 0) {
		logger_write(loader->logger, SFDO_LOG_LEVEL_INFO, "Expected version 1.0, got %d.%d", major,
				minor);
		return false;
	}

	uint32_t hash_off, dir_list_off;
	if (!read_card32(loader, 4, &hash_off) || !read_card32(loader, 8, &dir_list_off)) {
		return false;
	}

	uint32_t n_dirs;
	if (!read_card32(loader, dir_list_off, &n_dirs)) {
		return false;
	}

	struct sfdo_icon_cache *cache = loader->cache;

	cache->n_dirs = n_dirs;
	cache->dirs = calloc(n_dirs, sizeof(*cache->dirs));
	if (cache->dirs == NULL) {
		logger_write_oom(loader->logger);
		return false;
	}

	for (uint32_t i = 0; i < n_dirs; i++) {
		uint32_t dir_off;
		if (!read_card32(loader, dir_list_off + 4 * (1 + i), &dir_off)) {
			return false;
		}

		struct sfdo_icon_cache_dir *dir = &cache->dirs[i];
		if (!read_str(loader, dir_off, &dir->name, &dir->name_len)) {
			return false;
		}
		dir->start_i = (size_t)-1;
	}

	size_t images_len = 0, images_cap = 0;

	uint32_t n_buckets;
	if (!read_card32(loader, hash_off, &n_buckets)) {
		return false;
	}
	for (uint32_t i = 0; i < n_buckets; i++) {
		uint32_t icon_off;
		if (!read_card32(loader, hash_off + 4 + 4 * i, &icon_off)) {
			return false;
		};

		if (!ensure_no_loop(loader, icon_off)) {
			return false;
		}

		while (icon_off != CHAIN_END) {
			uint32_t chain_off, name_off, image_list_off;
			if (!read_card32(loader, icon_off, &chain_off) ||
					!read_card32(loader, icon_off + 4, &name_off) ||
					!read_card32(loader, icon_off + 8, &image_list_off)) {
				return false;
			}

			const char *name;
			size_t name_len;
			if (!read_str(loader, name_off, &name, &name_len)) {
				return false;
			}

			uint32_t n_images;
			if (!read_card32(loader, image_list_off, &n_images)) {
				return false;
			}

			for (uint32_t j = 0; j < n_images; j++) {
				uint32_t image_off = image_list_off + 4 + 8 * j;
				uint16_t dir_i, flags;
				if (!read_card16(loader, image_off, &dir_i) ||
						!read_card16(loader, image_off + 2, &flags)) {
					return false;
				}

				if (dir_i >= n_dirs) {
					logger_write(loader->logger, SFDO_LOG_LEVEL_ERROR,
							"Directory index %" PRIu16 " is out of range", dir_i);
					return false;
				}

				if (!sfdo_grow(&cache->images, &images_cap, images_len, sizeof(*cache->images))) {
					logger_write_oom(loader->logger);
					return false;
				}

				struct sfdo_icon_cache_dir *dir = &cache->dirs[dir_i];
				if (dir->start_i == (size_t)-1) {
					dir->start_i = images_len;
				} else {
					cache->images[dir->end_i].next_i = images_len;
				}

				dir->end_i = images_len;
				struct sfdo_icon_cache_image *image = &cache->images[images_len++];

				image->name = name;
				image->name_len = name_len;

				image->formats = 0;
				if ((flags & 0x1) != 0) {
					image->formats |= SFDO_ICON_FORMAT_MASK_XPM;
				}
				if ((flags & 0x2) != 0) {
					image->formats |= SFDO_ICON_FORMAT_MASK_SVG;
				}
				if ((flags & 0x4) != 0) {
					image->formats |= SFDO_ICON_FORMAT_MASK_PNG;
				}

				image->next_i = (size_t)-1;
			}

			icon_off = chain_off;
		}
	}

	logger_write(loader->logger, SFDO_LOG_LEVEL_DEBUG, "Found %zu cached image(s)", images_len);
	return true;
}

struct sfdo_icon_cache *icon_cache_create(
		const char *path, time_t dir_mtime, struct sfdo_logger *logger) {
	int fd = open(path, O_RDONLY | O_CLOEXEC);
	if (fd < 0) {
		goto err_fd;
	}

	logger_write(logger, SFDO_LOG_LEVEL_DEBUG, "Found cache file %s", path);

	struct stat statbuf;
	if (fstat(fd, &statbuf) != 0 || !S_ISREG(statbuf.st_mode)) {
		logger_write(logger, SFDO_LOG_LEVEL_DEBUG, "Not a regular file");
		goto err_stat;
	}

	if (statbuf.st_mtime < dir_mtime) {
		logger_write(logger, SFDO_LOG_LEVEL_DEBUG, "Too old: file mtime %ld, dir mtime %ld",
				(long)statbuf.st_mtime, (long)dir_mtime);
		goto err_stat;
	}

	size_t size = (size_t)statbuf.st_size;
	char *data = mmap(NULL, size, PROT_READ, MAP_PRIVATE, fd, 0);
	close(fd);

	if (data == MAP_FAILED) {
		logger_write(
				logger, SFDO_LOG_LEVEL_ERROR, "Failed to mmap() %s: %s", path, strerror(errno));
		return NULL;
	}

	struct sfdo_icon_cache *cache = calloc(1, sizeof(*cache));
	if (cache == NULL) {
		logger_write_oom(logger);
		munmap(data, size);
		return NULL;
	}

	cache->data = data;
	cache->size = size;

	struct sfdo_icon_cache_loader loader = {
		.cache = cache,
		.logger = logger,
	};

	if (!load_cache(&loader)) {
		logger_write(logger, SFDO_LOG_LEVEL_ERROR, "Failed to load %s, ignoring", path);
		icon_cache_destroy(cache);
		return NULL;
	}

	return cache;

err_stat:
	close(fd);
err_fd:
	return NULL;
}

void icon_cache_destroy(struct sfdo_icon_cache *cache) {
	if (cache == NULL) {
		return;
	}

	munmap(cache->data, cache->size);
	free(cache->dirs);
	free(cache->images);
	free(cache);
}

bool icon_cache_scan_dir(struct sfdo_icon_cache *cache, struct sfdo_icon_scanner *scanner,
		const struct sfdo_string *basedir, const struct sfdo_icon_subdir *subdir) {
	struct sfdo_logger *logger = scanner->logger;

	assert(subdir != NULL);
	const char *subdir_data = subdir->path.data;

	struct sfdo_icon_cache_dir *dir = NULL;
	for (size_t i = 0; i < cache->n_dirs; i++) {
		struct sfdo_icon_cache_dir *curr = &cache->dirs[i];
		if (subdir->path.len == curr->name_len &&
				memcmp(subdir_data, curr->name, curr->name_len) == 0) {
			dir = curr;
			break;
		}
	}
	if (dir == NULL) {
		return true;
	}

	size_t n_images = 0;
	struct sfdo_icon_cache_image *image;
	for (size_t i = dir->start_i; i != (size_t)-1; i = image->next_i) {
		image = &cache->images[i];
		const char *name = icon_scanner_intern_name(scanner, image->name, image->name_len);
		if (name == NULL) {
			return false;
		}
		if (!icon_scanner_add_image(
					scanner, basedir, subdir, name, image->name_len, image->formats)) {
			return false;
		}
		++n_images;
	}
	logger_write(logger, SFDO_LOG_LEVEL_DEBUG, "Added %zu cached image(s) for %s in %s", n_images,
			subdir_data, basedir->data);

	return true;
}