summaryrefslogtreecommitdiff
path: root/Build/source/texk/web2c/mfluadir/otfcc/lib/bk/bkgraph.c
diff options
context:
space:
mode:
Diffstat (limited to 'Build/source/texk/web2c/mfluadir/otfcc/lib/bk/bkgraph.c')
-rw-r--r--Build/source/texk/web2c/mfluadir/otfcc/lib/bk/bkgraph.c410
1 files changed, 410 insertions, 0 deletions
diff --git a/Build/source/texk/web2c/mfluadir/otfcc/lib/bk/bkgraph.c b/Build/source/texk/web2c/mfluadir/otfcc/lib/bk/bkgraph.c
new file mode 100644
index 00000000000..2c4b1415a95
--- /dev/null
+++ b/Build/source/texk/web2c/mfluadir/otfcc/lib/bk/bkgraph.c
@@ -0,0 +1,410 @@
+#include "bkgraph.h"
+
+static bk_GraphNode *_bkgraph_grow(bk_Graph *f) {
+ if (f->free) {
+ f->length++;
+ f->free--;
+ } else {
+ f->length = f->length + 1;
+ f->free = (f->length >> 1) & 0xFFFFFF;
+ RESIZE(f->entries, f->length + f->free);
+ }
+ return &(f->entries[f->length - 1]);
+}
+
+static uint32_t dfs_insert_cells(bk_Block *b, bk_Graph *f, uint32_t *order) {
+ if (!b || b->_visitstate == VISIT_GRAY) return 0;
+ if (b->_visitstate == VISIT_BLACK) return b->_height;
+ b->_visitstate = VISIT_GRAY;
+ uint32_t height = 0;
+ for (uint32_t j = 0; j < b->length; j++) {
+ bk_Cell *cell = &(b->cells[j]);
+ if (bk_cellIsPointer(cell) && cell->p) {
+ uint32_t thatHeight = dfs_insert_cells(cell->p, f, order);
+ if (thatHeight + 1 > height) height = thatHeight + 1;
+ }
+ }
+ bk_GraphNode *e = _bkgraph_grow(f);
+ e->alias = 0;
+ e->block = b;
+ *order += 1;
+ e->order = *order;
+ e->height = b->_height = height;
+ b->_visitstate = VISIT_BLACK;
+ return height;
+}
+
+static int _by_height(const void *_a, const void *_b) {
+ const bk_GraphNode *a = _a;
+ const bk_GraphNode *b = _b;
+ return a->height == b->height ? a->order - b->order : b->height - a->height;
+}
+
+static int _by_order(const void *_a, const void *_b) {
+ const bk_GraphNode *a = _a;
+ const bk_GraphNode *b = _b;
+ return a->block && b->block && a->block->_visitstate != b->block->_visitstate // Visited first
+ ? b->block->_visitstate - a->block->_visitstate
+ : a->block && b->block && a->block->_depth != b->block->_depth // By depth
+ ? a->block->_depth - b->block->_depth
+ : b->order - a->order; // By order
+}
+
+bk_Graph *bk_newGraphFromRootBlock(bk_Block *b) {
+ bk_Graph *forest;
+ NEW(forest);
+ uint32_t tsOrder = 0;
+ dfs_insert_cells(b, forest, &tsOrder);
+ qsort(forest->entries, forest->length, sizeof(bk_GraphNode), _by_height);
+ for (uint32_t j = 0; j < forest->length; j++) {
+ forest->entries[j].block->_index = j;
+ forest->entries[j].alias = j;
+ }
+ return forest;
+}
+
+void bk_delete_Graph(bk_Graph *f) {
+ if (!f || !f->entries) return;
+ for (uint32_t j = 0; j < f->length; j++) {
+ bk_Block *b = f->entries[j].block;
+ if (b && b->cells) FREE(b->cells);
+ FREE(b);
+ }
+ FREE(f->entries);
+ FREE(f);
+}
+
+static uint32_t gethash(bk_Block *b) {
+ uint32_t h = 5381;
+ for (uint32_t j = 0; j < b->length; j++) {
+ h = ((h << 5) + h) + b->cells[j].t;
+ h = ((h << 5) + h);
+ switch (b->cells[j].t) {
+ case b8:
+ case b16:
+ case b32:
+ h += b->cells[j].z;
+ break;
+ case p16:
+ case p32:
+ case sp16:
+ case sp32:
+ if (b->cells[j].p) { h += b->cells[j].p->_index; }
+ break;
+ default:
+ break;
+ }
+ }
+ return h;
+}
+
+static bool compareblock(bk_Block *a, bk_Block *b) {
+ if (!a && !b) return true;
+ if (!a || !b) return false;
+ if (a->length != b->length) return false;
+ for (uint32_t j = 0; j < a->length; j++) {
+ if (a->cells[j].t != b->cells[j].t) return false;
+ switch (a->cells[j].t) {
+ case b8:
+ case b16:
+ case b32:
+ if (a->cells[j].z != b->cells[j].z) return false;
+ break;
+ case p16:
+ case p32:
+ case sp16:
+ case sp32:
+ if (a->cells[j].p != b->cells[j].p) return false;
+ break;
+ default:
+ break;
+ }
+ }
+ return true;
+}
+static bool compareEntry(bk_GraphNode *a, bk_GraphNode *b) {
+ if (a->hash != b->hash) return false;
+ return compareblock(a->block, b->block);
+}
+
+static void replaceptr(bk_Graph *f, bk_Block *b) {
+ for (uint32_t j = 0; j < b->length; j++) {
+ switch (b->cells[j].t) {
+ case p16:
+ case p32:
+ case sp16:
+ case sp32:
+ if (b->cells[j].p) {
+ uint32_t index = b->cells[j].p->_index;
+ while (f->entries[index].alias != index) {
+ index = f->entries[index].alias;
+ }
+ b->cells[j].p = f->entries[index].block;
+ }
+ break;
+ default:
+ break;
+ }
+ }
+}
+
+void bk_minimizeGraph(bk_Graph *f) {
+ uint32_t rear = (uint32_t)(f->length - 1);
+ while (rear > 0) {
+ uint32_t front = rear;
+ while (f->entries[front].height == f->entries[rear].height && front > 0) {
+ front--;
+ }
+ front++;
+ for (uint32_t j = front; j <= rear; j++) {
+ f->entries[j].hash = gethash(f->entries[j].block);
+ }
+ for (uint32_t j = front; j <= rear; j++) {
+ bk_GraphNode *a = &(f->entries[j]);
+ if (a->alias == j) {
+ for (uint32_t k = j + 1; k <= rear; k++) {
+ bk_GraphNode *b = &(f->entries[k]);
+ if (b->alias == k && compareEntry(a, b)) { b->alias = j; }
+ }
+ }
+ }
+ // replace pointers with aliased
+ for (uint32_t j = 0; j < front; j++) {
+ replaceptr(f, f->entries[j].block);
+ }
+ rear = front - 1;
+ }
+}
+
+static size_t otfcc_bkblock_size(bk_Block *b) {
+ size_t size = 0;
+ for (uint32_t j = 0; j < b->length; j++)
+ switch (b->cells[j].t) {
+ case b8:
+ size += 1;
+ break;
+ case b16:
+ case p16:
+ case sp16:
+ size += 2;
+ break;
+ case b32:
+ case p32:
+ case sp32:
+ size += 4;
+ break;
+ default:
+ break;
+ }
+ return size;
+}
+
+static uint32_t getoffset(size_t *offsets, bk_Block *ref, bk_Block *target, uint8_t bits) {
+ size_t offref = offsets[ref->_index];
+ size_t offtgt = offsets[target->_index];
+ /*
+ if (offtgt < offref || (offtgt - offref) >> bits) {
+ fprintf(stderr, "[otfcc-fea] Warning : Unable to fit offset %d into %d bits.\n",
+ (int32_t)(offtgt - offref), bits);
+ }
+ */
+ return (uint32_t)(offtgt - offref);
+}
+static int64_t getoffset_untangle(size_t *offsets, bk_Block *ref, bk_Block *target) {
+ size_t offref = offsets[ref->_index];
+ size_t offtgt = offsets[target->_index];
+ return (int64_t)(offtgt - offref);
+}
+static void escalate_sppointers(bk_Block *b, bk_Graph *f, uint32_t *order, uint32_t depth) {
+ if (!b) return;
+ for (uint32_t j = 0; j < b->length; j++) {
+ bk_Cell *cell = &(b->cells[j]);
+ if (bk_cellIsPointer(cell) && cell->p && cell->t >= sp16) {
+ escalate_sppointers(cell->p, f, order, depth);
+ }
+ }
+ b->_depth = depth;
+ *order += 1;
+ f->entries[b->_index].order = *order;
+}
+static void dfs_attract_cells(bk_Block *b, bk_Graph *f, uint32_t *order, uint32_t depth) {
+ if (!b) return;
+ if (b->_visitstate != VISIT_WHITE) {
+ if (b->_depth < depth) { b->_depth = depth; }
+ return;
+ }
+ b->_visitstate = VISIT_GRAY;
+ for (uint32_t j = b->length; j-- > 0;) {
+ bk_Cell *cell = &(b->cells[j]);
+ if (bk_cellIsPointer(cell) && cell->p) { dfs_attract_cells(cell->p, f, order, depth + 1); }
+ }
+ *order += 1;
+ f->entries[b->_index].order = *order;
+ escalate_sppointers(b, f, order, depth);
+ b->_visitstate = VISIT_BLACK;
+}
+
+static void attract_bkgraph(bk_Graph *f) {
+ // Clear the visit state of all blocks
+ for (uint32_t j = 0; j < f->length; j++) {
+ f->entries[j].block->_visitstate = VISIT_WHITE;
+ f->entries[j].order = 0;
+ f->entries[j].block->_index = j;
+ f->entries[j].block->_depth = 0;
+ }
+ uint32_t order = 0;
+ dfs_attract_cells(f->entries[0].block, f, &order, 0);
+ qsort(f->entries, f->length, sizeof(bk_GraphNode), _by_order);
+ for (uint32_t j = 0; j < f->length; j++) {
+ f->entries[j].block->_index = j;
+ }
+}
+
+static bool try_untabgle_block(bk_Graph *f, bk_Block *b, size_t *offsets, uint16_t passes) {
+ bool didCopy = false;
+ for (uint32_t j = 0; j < b->length; j++) {
+ switch (b->cells[j].t) {
+ case p16:
+ case sp16:
+ if (b->cells[j].p) {
+ int64_t offset = getoffset_untangle(offsets, b, b->cells[j].p);
+ if (offset < 0 || offset > 0xFFFF) {
+ bk_GraphNode *e = _bkgraph_grow(f);
+ e->order = 0;
+ e->alias = 0;
+ e->block = bk_new_Block(bkcopy, b->cells[j].p, bkover);
+ b->cells[j].t = sp16;
+ b->cells[j].p = e->block;
+ didCopy = true;
+ }
+ }
+ break;
+ default:
+ break;
+ }
+ }
+ return didCopy;
+}
+
+static bool try_untangle(bk_Graph *f, uint16_t passes) {
+ size_t *offsets;
+ NEW(offsets, f->length + 1);
+ offsets[0] = 0;
+ for (uint32_t j = 0; j < f->length; j++) {
+ if (f->entries[j].block->_visitstate == VISIT_BLACK) {
+ offsets[j + 1] = offsets[j] + otfcc_bkblock_size(f->entries[j].block);
+ } else {
+ offsets[j + 1] = offsets[j];
+ }
+ }
+ uint32_t totalBlocks = f->length;
+ bool didUntangle = false;
+ for (uint32_t j = 0; j < totalBlocks; j++) {
+ if (f->entries[j].block->_visitstate == VISIT_BLACK) {
+ bool didCopy = try_untabgle_block(f, f->entries[j].block, offsets, passes);
+ didUntangle = didUntangle || didCopy;
+ }
+ }
+ FREE(offsets);
+ return didUntangle;
+}
+
+static void otfcc_build_bkblock(caryll_Buffer *buf, bk_Block *b, size_t *offsets) {
+ for (uint32_t j = 0; j < b->length; j++) {
+ switch (b->cells[j].t) {
+ case b8:
+ bufwrite8(buf, b->cells[j].z);
+ break;
+ case b16:
+ bufwrite16b(buf, b->cells[j].z);
+ break;
+ case b32:
+ bufwrite32b(buf, b->cells[j].z);
+ break;
+ case p16:
+ case sp16:
+ if (b->cells[j].p) {
+ bufwrite16b(buf, getoffset(offsets, b, b->cells[j].p, 16));
+ } else {
+ bufwrite16b(buf, 0);
+ }
+ break;
+ case p32:
+ case sp32:
+ if (b->cells[j].p) {
+ bufwrite32b(buf, getoffset(offsets, b, b->cells[j].p, 32));
+ } else {
+ bufwrite32b(buf, 0);
+ }
+ break;
+ default:
+ break;
+ }
+ }
+}
+
+caryll_Buffer *bk_build_Graph(bk_Graph *f) {
+ caryll_Buffer *buf = bufnew();
+ size_t *offsets;
+ NEW(offsets, f->length + 1);
+
+ offsets[0] = 0;
+ for (uint32_t j = 0; j < f->length; j++) {
+ if (f->entries[j].block->_visitstate == VISIT_BLACK) {
+ offsets[j + 1] = offsets[j] + otfcc_bkblock_size(f->entries[j].block);
+ } else {
+ offsets[j + 1] = offsets[j];
+ }
+ }
+ for (uint32_t j = 0; j < f->length; j++) {
+ if (f->entries[j].block->_visitstate == VISIT_BLACK) {
+ otfcc_build_bkblock(buf, f->entries[j].block, offsets);
+ }
+ }
+ FREE(offsets);
+ return buf;
+}
+
+size_t bk_estimateSizeOfGraph(bk_Graph *f) {
+ size_t *offsets;
+ NEW(offsets, f->length + 1);
+
+ offsets[0] = 0;
+ for (uint32_t j = 0; j < f->length; j++) {
+ if (f->entries[j].block->_visitstate == VISIT_BLACK) {
+ offsets[j + 1] = offsets[j] + otfcc_bkblock_size(f->entries[j].block);
+ } else {
+ offsets[j + 1] = offsets[j];
+ }
+ }
+ size_t estimatedSize = offsets[f->length];
+ FREE(offsets);
+ return estimatedSize;
+}
+
+void bk_untangleGraph(/*BORROW*/ bk_Graph *f) {
+ uint16_t passes = 0;
+ bool tangled = false;
+ attract_bkgraph(f);
+ do {
+ tangled = try_untangle(f, passes);
+ if (tangled) { attract_bkgraph(f); }
+ passes++;
+ } while (tangled && passes < 16);
+}
+
+caryll_Buffer *bk_build_Block(/*MOVE*/ bk_Block *root) {
+ bk_Graph *f = bk_newGraphFromRootBlock(root);
+ bk_minimizeGraph(f);
+ bk_untangleGraph(f);
+ caryll_Buffer *buf = bk_build_Graph(f);
+ bk_delete_Graph(f);
+ return buf;
+}
+caryll_Buffer *bk_build_Block_noMinimize(/*MOVE*/ bk_Block *root) {
+ bk_Graph *f = bk_newGraphFromRootBlock(root);
+ bk_untangleGraph(f);
+ caryll_Buffer *buf = bk_build_Graph(f);
+ bk_delete_Graph(f);
+ return buf;
+}