Add libfonts_create_transcoding_table

Signed-off-by: Mattias Andrée <maandree@kth.se>

4 files changed, 210 insertions, 1 deletions

diff --git a/Makefile b/Makefile
index 7e967fd..c3dc40a 100644
--- a/Makefile
+++ b/Makefile
@@ -19,6 +19,7 @@ LIB_NAME = fonts
 PUBLIC_OBJ =\
 	libfonts_calculate_subpixel_order.o\
 	libfonts_char_is_in_subset.o\
+	libfonts_create_transcoding_table.o\
 	libfonts_deallocate_encoding.o\
 	libfonts_deallocate_encoding_mapping.o\
 	libfonts_deallocate_encoding_mapping_entry.o\
diff --git a/common.h b/common.h
index 1047e2f..fcafb53 100644
--- a/common.h
+++ b/common.h
@@ -7,6 +7,7 @@
 #include <limits.h>
 #include <pwd.h>
 #include <stdarg.h>
+#include <stddef.h>
 #include <stdint.h>
 #include <stdio.h>
 #include <stdlib.h>
diff --git a/libfonts.h b/libfonts.h
index 02a9fa0..7224c9a 100644
--- a/libfonts.h
+++ b/libfonts.h
@@ -13,6 +13,13 @@
 #define LIBFONTS_CONTEXT_VERSION 0
 
 /**
+ * Target character index used to signify that the
+ * source character index is invalid or has not
+ * mapping to the target encoding
+ */
+#define LIBFONTS_UNDEFINED_CHAR (UINT32_C(0xFFFFFFFF))
+
+/**
  * File name of file in font directories that is used
  * to create font aliases
  */
@@ -1866,7 +1873,6 @@ struct libfonts_encoding {
 	 * List of coded translation mappings
 	 */
 	struct libfonts_encoding_mapping *mappings;
-	/* TODO add functions for creating tables in either direction */
 
 	/**
 	 * The number of elements in `.mappings`
@@ -1903,6 +1909,65 @@ struct libfonts_encoding {
 
 
 /**
+ * Lookup table for translating from one
+ * text encoding into another
+ */
+struct libfonts_transcoding_table {
+	/**
+	 * Source character indices lower than
+	 * this value should be rejected without
+	 * looking in `.table`
+	 */
+	uint32_t first_valid;
+
+	/**
+	 * Source character indices higher than
+	 * this value should be rejected without
+	 * looking in `.table`
+	 */
+	uint32_t last_valid;
+
+	/**
+	 * See `.table`
+	 */
+	uint32_t offset;
+
+	/**
+	 * See `.table`
+	 * 
+	 * If this value is 0, the source encoding uses one byte
+	 * per character, otherwise it uses two bytes per character
+	 */
+	uint32_t multiplier;
+
+	/**
+	 * For a source character index `i`, the target character index is
+	 * `.table[((i - .offset) >> 8) * .multiplier + ((i - .offset) & 0xFF)]`
+	 * (`LIBFONTS_LOOKUP_TRANSCODING_TABLE` performs this lookup);
+	 * however, if this value is `LIBFONTS_UNDEFINED_CHAR`, the
+	 * character has no mapping: either `i` is an invalid character
+	 * index in the source encoding, or the corresponding character
+	 * does not exist in the target encoding
+	 */
+	uint32_t table[];
+};
+
+
+/**
+ * Converts a source character index to a target character index
+ * via a transcoding table
+ *
+ * @param   TABLE:const struct libfonts_transcoding_table *  The transcoding table
+ * @param   I:uint32_t                                       The source character index
+ * @return  :uint32_t                                        The target character index, or
+ *                                                           `LIBFONTS_UNDEFINED_CHAR` if there is no mapping
+ */
+#define LIBFONTS_LOOKUP_TRANSCODING_TABLE(TABLE, I)\
+	((TABLE)->table[(((uint32_t)(I) - (TABLE)->offset) >> 8) * (TABLE)->multiplier +\
+	                (((uint32_t)(I) - (TABLE)->offset) & 0xFF)])
+
+
+/**
  * Structure that can be used to spoof the
  * environment the library is executed in,
  * as well as the print warnings from the
@@ -2158,6 +2223,24 @@ void libfonts_deallocate_encoding(struct libfonts_encoding *);
  */
 int libfonts_parse_encoding_line(struct libfonts_encoding **, int *, const char *, char **, struct libfonts_context *);
 
+/**
+ * Create a transcoding table
+ *
+ * @param   encoding  The source encoding
+ * @param   mapping   The index in `encoding->mappings` for the target encoding
+ * @return            Transcoding table, deallocatable with free(3), or `NULL` on failure
+ * 
+ * @throws  ENOMEM  Failed to allocate enough memory
+ * @throws  EINVAL  `encoding` is `NULL`
+ * @throws  EINVAL  `mapping` is equal to or greater than `encoding->nmappings`
+ * @throws  EINVAL  The contents of `encoding` is invalid
+ * @throws  EINVAL  One of the entries in the mapping has the
+ *                  `LIBFONTS_ENCODING_MAPPING_ENTRY_INDEX_TO_NAME` type
+ */
+struct libfonts_transcoding_table *libfonts_create_transcoding_table(const struct libfonts_encoding *, size_t);
+
+/* TODO add libfonts_create_reverse_transcoding_table */
+
 
 /**
  * Get the font a default font name aliases to
diff --git a/libfonts_create_transcoding_table.c b/libfonts_create_transcoding_table.c
new file mode 100644
index 0000000..ee75bf4
--- /dev/null
+++ b/libfonts_create_transcoding_table.c
@@ -0,0 +1,124 @@
+/* See LICENSE file for copyright and license details. */
+#include "common.h"
+#ifndef TEST
+
+
+static int
+set_range(uint32_t low, uint32_t high, uint32_t target, uint32_t target_inc, struct libfonts_transcoding_table *table)
+{
+	uint32_t i;
+
+	if (low < table->first_valid) {
+		if (target != LIBFONTS_UNDEFINED_CHAR)
+			return -1;
+		low = table->first_valid;
+	}
+
+	if (high > table->last_valid) {
+		if (target != LIBFONTS_UNDEFINED_CHAR)
+			return -1;
+		high = table->last_valid;
+	}
+
+	i = low;
+	do {
+		LIBFONTS_LOOKUP_TRANSCODING_TABLE(table, i) = target;
+		target += target_inc;
+	} while (i++ < high);
+
+	return 0;
+}
+
+struct libfonts_transcoding_table *
+libfonts_create_transcoding_table(const struct libfonts_encoding *encoding, size_t mapping)
+{
+	const struct libfonts_encoding_mapping *map;
+	size_t size, entry;
+	uint16_t size_rows, size_cols;
+	uint8_t first_row, first_col;
+	struct libfonts_transcoding_table *ret;
+	uint32_t i;
+	int r;
+
+	if (!encoding ||
+	    mapping > encoding->nmappings ||
+	    !encoding->mappings ||
+	    (encoding->mappings[mapping].nentries && !encoding->mappings[mapping].entries) ||
+	    !encoding->size_rows)
+		goto einvalid;
+
+	map = &encoding->mappings[mapping];
+	size_rows = encoding->size_rows;
+	size_cols = encoding->size_cols;
+	first_row = encoding->first_index_row;
+	first_col = encoding->first_index_col;
+
+#if SIZE_MAX <= UINT32_MAX
+	if ((size_t)size_rows - (size_t)first_row > SIZE_MAX / (size_cols ? (size_t)size_cols : 1))
+		goto enomem;
+#endif
+	size = ((size_t)size_rows - (size_t)first_row) * (size_cols ? (size_t)size_cols : 1);
+	if (size > (SIZE_MAX - offsetof(struct libfonts_transcoding_table, table)) / sizeof(uint32_t))
+		goto enomem;
+	ret = malloc(size * sizeof(uint32_t) + offsetof(struct libfonts_transcoding_table, table));
+	if (!ret)
+		goto enomem;
+
+	ret->first_valid = (uint32_t)first_row;
+	ret->last_valid = (uint32_t)size_rows - 1;
+	if (size_cols) {
+		ret->first_valid <<= 8;
+		ret->first_valid |= (uint32_t)first_col;
+		ret->last_valid <<= 8;
+		ret->last_valid |= (uint32_t)size_cols - 1;
+	}
+
+	ret->offset = encoding->size_cols ? (uint32_t)first_row << 8 : (uint32_t)first_col;
+	ret->multiplier = (uint32_t)size_cols;
+
+	for (i = ret->first_valid; i <= ret->last_valid; i++)
+		LIBFONTS_LOOKUP_TRANSCODING_TABLE(ret, i) = i;
+
+	for (entry = 0; entry < map->nentries; entry++) {
+		if (map->entries[entry].type == LIBFONTS_ENCODING_MAPPING_ENTRY_UNDEFINED_RANGE) {
+			set_range(map->entries[entry].undefined_range.low_source,
+			          map->entries[entry].undefined_range.high_source,
+			          LIBFONTS_UNDEFINED_CHAR, 0, ret);
+
+		} else if (map->entries[entry].type == LIBFONTS_ENCODING_MAPPING_ENTRY_REMAPPED_RANGE) {
+			r = set_range(map->entries[entry].remapped_range.low_source,
+			              map->entries[entry].remapped_range.high_source,
+			              map->entries[entry].remapped_range.low_target, 0, ret);
+			if (r)
+				goto invalid;
+
+		} else {
+			goto invalid;
+		}
+	}
+
+	return ret;
+
+enomem:
+	errno = ENOMEM;
+	return NULL;
+
+invalid:
+	free(ret);
+einvalid:
+	errno = EINVAL;
+	return NULL;
+}
+
+
+#else
+
+
+int
+main(void)
+{
+	return 0; /* XXX add test */
+}
+
+
+#endif