From a3c6774f211ee765f910df76837548bdadd4e959 Mon Sep 17 00:00:00 2001 From: dec05eba Date: Mon, 15 Nov 2021 08:20:13 +0100 Subject: Add dynamic font atlas creation (not finished) --- src/graphics/font_char_map.c | 214 +++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 214 insertions(+) create mode 100644 src/graphics/font_char_map.c (limited to 'src/graphics/font_char_map.c') diff --git a/src/graphics/font_char_map.c b/src/graphics/font_char_map.c new file mode 100644 index 0000000..abaa56a --- /dev/null +++ b/src/graphics/font_char_map.c @@ -0,0 +1,214 @@ +#include "../../include/mgl/graphics/font_char_map.h" +#include + +/* TODO: Optimize % to & */ + +/* Optimized div by sizeof(mgl_font_char_entry*) */ +#if INTPTR_MAX == INT64_MAX +#define CAP_NUM_ENTRIES(cap) ((cap) >> 3) +#elif INTPTR_MAX == INT32_MAX +#define CAP_NUM_ENTRIES(cap) ((cap) >> 2) +#else +#error Unsupported system. Only systems where a pointer is 32-bits or 64-bits are supported. +#endif + +static size_t align_to(size_t value, size_t align) { + const size_t is_aligned = (value & (align - 1)); + if(is_aligned == 0) { + return value; + } else { + return (value & ~(align - 1)) + align; + } +} + +static void mgl_font_char_entry_deinit(mgl_font_char_entry *self) { + mgl_font_char_entry *next = self->next; + while(next) { + mgl_font_char_entry *next_next = next->next; + free(next); + next = next_next; + } +} + +static void mgl_font_char_map_insert_entry(mgl_font_char_map *self, size_t index, uint32_t key, const mgl_font_glyph *value, mgl_font_char_entry *entry) { + entry->key = key; + entry->value = *value; + entry->next = self->entries[index]; + self->entries[index] = entry; +} + +static void mgl_font_char_map_reorder_nodes(mgl_font_char_map *self, size_t prev_capacity) { + for(size_t i = 0; i < CAP_NUM_ENTRIES(prev_capacity); ++i) { + mgl_font_char_entry *entry = self->entries[i]; + if(!entry) + continue; + + mgl_font_char_entry *prev_entry = NULL; + while(entry) { + const uint32_t hash = entry->key; + const size_t index = hash % CAP_NUM_ENTRIES(self->capacity); + mgl_font_char_entry *next_entry = entry->next; /* store next here so the next insert below doesn't cause an infinite loop */ + + if(index != i) { + /* Remove entry by replacing this entry with the next entry */ + if(prev_entry) + prev_entry->next = next_entry; + else + self->entries[i] = next_entry; + + /* Insert the entry at the new index */ + mgl_font_char_map_insert_entry(self, index, entry->key, &entry->value, entry); + } else { + prev_entry = entry; + } + + entry = next_entry; + } + } +} + +static int mgl_font_char_map_ensure_capacity(mgl_font_char_map *self, size_t target_capacity) { + if(self->capacity >= target_capacity) + return 0; + + size_t capacity = self->capacity; + if(capacity == 0) + capacity = 8; + + while(capacity < target_capacity) { + capacity = capacity + (capacity >> 1); /* *= 1.5 = 1 + 0.5 */ + } + + capacity = align_to(capacity, sizeof(mgl_font_char_entry*)); + void *new_data = realloc(self->entries, capacity); + if(!new_data) + return -1; + + const size_t prev_capacity = self->capacity; + self->entries = new_data; + self->capacity = capacity; + + for(size_t i = CAP_NUM_ENTRIES(prev_capacity); i < CAP_NUM_ENTRIES(self->capacity); ++i) { + self->entries[i] = NULL; + } + + mgl_font_char_map_reorder_nodes(self, prev_capacity); + return 0; +} + +void mgl_font_char_map_init(mgl_font_char_map *self) { + self->entries = NULL; + self->size = 0; + self->capacity = 0; +} + +void mgl_font_char_map_deinit(mgl_font_char_map *self) { + if(self->entries) { + for(size_t i = 0; i < CAP_NUM_ENTRIES(self->capacity); ++i) { + if(self->entries[i]) { + mgl_font_char_entry_deinit(self->entries[i]); + free(self->entries[i]); + } + } + free(self->entries); + self->entries = NULL; + } + self->size = 0; + self->capacity = 0; +} + +int mgl_font_char_map_insert(mgl_font_char_map *self, uint32_t key, const mgl_font_glyph *value, mgl_font_char_entry **inserted_entry) { + if(mgl_font_char_map_ensure_capacity(self, (self->size + 1) * sizeof(mgl_font_char_entry*)) != 0) + return -1; + + ++self->size; + const uint32_t hash = key; + const size_t index = hash % CAP_NUM_ENTRIES(self->capacity); + + mgl_font_char_entry *entry = malloc(sizeof(mgl_font_char_entry)); + if(!entry) + return -1; + + mgl_font_char_map_insert_entry(self, index, key, value, entry); + entry->render_offset = (mgl_vec2i){ 0, 0 }; + entry->rendered = false; + if(inserted_entry) + *inserted_entry = entry; + + return 0; +} + +mgl_font_char_entry* mgl_font_char_map_get(const mgl_font_char_map *self, uint32_t key) { + if(self->capacity == 0) + return NULL; + + const uint32_t hash = key; + const size_t index = hash % CAP_NUM_ENTRIES(self->capacity); + + mgl_font_char_entry *entry = self->entries[index]; + while(entry) { + if(entry->key == key) + return entry; + entry = entry->next; + } + + return NULL; +} + +void mgl_font_char_map_clear_rendered(mgl_font_char_map *self) { + if(!self->entries) + return; + + for(size_t i = 0; i < CAP_NUM_ENTRIES(self->capacity); ++i) { + mgl_font_char_entry *entry = self->entries[i]; + if(!entry) + continue; + + while(entry) { + entry->rendered = false; + entry = entry->next; + } + } +} + +mgl_font_char_iterator mgl_font_char_map_begin(mgl_font_char_map *self) { + mgl_font_char_iterator it; + it.char_map = self; + it.index = 0; + it.value = NULL; + + if(!self->entries) + return it; + + for(size_t i = 0; i < CAP_NUM_ENTRIES(self->capacity); ++i) { + mgl_font_char_entry *entry = self->entries[i]; + if(entry) { + it.index = i; + it.value = entry; + break; + } + } + + return it; +} + +void mgl_font_char_iterator_next(mgl_font_char_iterator *self) { + if(!self->value) + return; + + if(self->value->next) { + self->value = self->value->next; + return; + } + + for(size_t i = self->index + 1; i < CAP_NUM_ENTRIES(self->char_map->capacity); ++i) { + mgl_font_char_entry *entry = self->char_map->entries[i]; + if(entry) { + self->index = i; + self->value = entry; + return; + } + } + + self->value = NULL; +} -- cgit v1.2.3