[project @ 2005-02-27 22:23:24 by bursa]

Trade memory for speed to reduce substitution table construction time.

svn path=/import/rufl/; revision=2454

5 files changed, 53 insertions, 72 deletions

diff --git a/makefile b/makefile
index ccca5b2..d15786e 100644
--- a/makefile
+++ b/makefile
@@ -14,7 +14,7 @@ CFLAGS = -std=c99 -O3 -W -Wall -Wundef -Wpointer-arith -Wcast-qual \
 LIBS = -L/home/riscos/env/lib -loslib
 
 SOURCE = rufl_init.c rufl_quit.c rufl_dump_state.c \
-	rufl_character_set_test.c rufl_substitution_lookup.c \
+	rufl_character_set_test.c \
 	rufl_paint.c rufl_glyph_map.c rufl_invalidate_cache.c
 
 all: rufl.o rufl_test,ff8 rufl_chars,ff8
diff --git a/rufl_dump_state.c b/rufl_dump_state.c
index 25e5781..81b7fb3 100644
--- a/rufl_dump_state.c
+++ b/rufl_dump_state.c
@@ -109,8 +109,8 @@ void rufl_dump_substitution_table(void)
 	u = 0;
 	while (u != 0x10000) {
 		t = u;
-		font = rufl_substitution_lookup(t);
-		while (u != 0x10000 && font == rufl_substitution_lookup(u))
+		font = rufl_substitution_table[t];
+		while (u != 0x10000 && font == rufl_substitution_table[u])
 			u++;
 		if (font != NOT_AVAILABLE)
 			printf("  %x-%x => %u \"%s\"\n", t, u - 1,
diff --git a/rufl_init.c b/rufl_init.c
index 99e95bf..792f9f2 100644
--- a/rufl_init.c
+++ b/rufl_init.c
@@ -23,7 +23,7 @@ char **rufl_family_list = 0;
 unsigned int rufl_family_list_entries = 0;
 unsigned int *rufl_family_map = 0;
 os_error *rufl_fm_error = 0;
-struct rufl_substitution_table *rufl_substitution_table = 0;
+unsigned short *rufl_substitution_table;
 struct rufl_cache_entry rufl_cache[rufl_CACHE_SIZE];
 int rufl_cache_time = 0;
 bool rufl_old_font_manager = false;
@@ -119,8 +119,8 @@ rufl_code rufl_init(void)
 	for (i = 0; i != rufl_font_list_entries; i++) {
 		if (rufl_font_list[i].charset) {
 			/* character set loaded from cache */
-			LOG("font %u \"%s\" from cache", i,
-					rufl_font_list[i].identifier);
+			/*LOG("font %u \"%s\" from cache", i,
+					rufl_font_list[i].identifier);*/
 			continue;
 		}
 		xhourglass_percentage(100 * i / rufl_font_list_entries);
@@ -225,7 +225,7 @@ rufl_code rufl_init_font_list(void)
 					rufl_fm_error->errmess);
 			return rufl_FONT_MANAGER_ERROR;
 		}
-		LOG("%u \"%s\"", rufl_font_list_entries - 1, identifier);
+		/*LOG("%u \"%s\"", rufl_font_list_entries - 1, identifier);*/
 
 		/* add family to list, if it is new */
 		dot = strchr(identifier, '.');
@@ -248,7 +248,7 @@ rufl_code rufl_init_font_list(void)
 		}
 
 		/* new family */
-		LOG("new family %u", rufl_family_list_entries);
+		/*LOG("new family %u", rufl_family_list_entries);*/
 		family_list = realloc(rufl_family_list,
 				sizeof rufl_family_list[0] *
 				(rufl_family_list_entries + 1));
@@ -307,8 +307,8 @@ rufl_code rufl_init_scan_font(unsigned int font_index)
 	font_f font;
 	font_scan_block block = { { 0, 0 }, { 0, 0 }, -1, { 0, 0, 0, 0 } };
 
-	LOG("font %u \"%s\"", font_index,
-			rufl_font_list[font_index].identifier);
+	/*LOG("font %u \"%s\"", font_index,
+			rufl_font_list[font_index].identifier);*/
 
 	charset = calloc(1, sizeof *charset);
 	if (!charset)
@@ -319,10 +319,12 @@ rufl_code rufl_init_scan_font(unsigned int font_index)
 
 	rufl_fm_error = xfont_find_font(font_name, 160, 160, 0, 0, &font, 0, 0);
 	if (rufl_fm_error) {
-		free(charset);
 		LOG("xfont_find_font(\"%s\"): 0x%x: %s", font_name,
 				rufl_fm_error->errnum, rufl_fm_error->errmess);
-		return rufl_FONT_MANAGER_ERROR;
+		for (u = 0; u != 256; u++)
+			charset->index[u] = BLOCK_EMPTY;
+		rufl_font_list[font_index].charset = charset;
+		return rufl_OK;
 	}
 
 	/* scan through all characters */
@@ -607,55 +609,51 @@ int rufl_unicode_map_cmp(const void *z1, const void *z2)
 
 rufl_code rufl_init_substitution_table(void)
 {
-	unsigned int block_count = 0;
+	unsigned char z;
 	unsigned int i;
-	unsigned int last_used = 0;
+	unsigned int block, byte, bit;
 	unsigned int u;
-	struct rufl_substitution_table *substitution_table2;
+	unsigned int index;
+	const struct rufl_character_set *charset;
 
-	rufl_substitution_table = malloc(sizeof *rufl_substitution_table);
+	rufl_substitution_table = malloc(65536 *
+			sizeof rufl_substitution_table[0]);
 	if (!rufl_substitution_table)
 		return rufl_OUT_OF_MEMORY;
 
-	/* scan through all characters */
-	for (u = 0; u != 0x10000; u++) {
-		rufl_substitution_table->block[last_used][u & 255] =
-				NOT_AVAILABLE;
-		for (i = 0; i != rufl_font_list_entries; i++) {
-			if (rufl_character_set_test(rufl_font_list[i].charset,
-					u)) {
-				rufl_substitution_table->block[last_used]
-						[u & 255] = i;
-				block_count++;
-				break;
-			}
-		}
+	for (u = 0; u != 0x10000; u++)
+		rufl_substitution_table[u] = NOT_AVAILABLE;
 
-		if ((u + 1) % 256 == 0) {
-			/* end of block */
-			if (block_count == 0) {
-				rufl_substitution_table->index[u >> 8] =
-						BLOCK_NONE_AVAILABLE;
-			} else {
-				rufl_substitution_table->index[u >> 8] =
-						last_used;
-				last_used++;
-				if (last_used == 255)
-					/* too many characters */
-					break;
+	for (i = 0; i != rufl_font_list_entries; i++) {
+		charset = rufl_font_list[i].charset;
+		for (block = 0; block != 256; block++) {
+			if (charset->index[block] == BLOCK_EMPTY)
+				continue;
+			if (charset->index[block] == BLOCK_FULL) {
+				for (u = block << 8; u != (block << 8) + 256;
+						u++) {
+					if (rufl_substitution_table[u] ==
+							NOT_AVAILABLE)
+						rufl_substitution_table[u] = i;
+				}
+				continue;
+			}
+			index = charset->index[block];
+			for (byte = 0; byte != 32; byte++) {
+				z = charset->block[index][byte];
+				if (z == 0)
+					continue;
+				u = (block << 8) | (byte << 3);
+				for (bit = 0; bit != 8; bit++, u++) {
+					if (rufl_substitution_table[u] ==
+							NOT_AVAILABLE &&
+							z & (1 << bit))
+						rufl_substitution_table[u] = i;
+				}
 			}
-			block_count = 0;
 		}
 	}
 
-	/* shrink-wrap */
-	substitution_table2 = realloc(rufl_substitution_table,
-			offsetof(struct rufl_substitution_table, block) +
-			sizeof (short) * 256 * last_used);
-	if (!substitution_table2)
-		return rufl_OUT_OF_MEMORY;
-	rufl_substitution_table = substitution_table2;
-
 	return rufl_OK;
 }
 
diff --git a/rufl_internal.h b/rufl_internal.h
index 490554a..021694b 100644
--- a/rufl_internal.h
+++ b/rufl_internal.h
@@ -76,26 +76,10 @@ extern unsigned int rufl_font_list_entries;
 extern unsigned int *rufl_family_map;
 
 
-/** Map from characters to a font which includes them. A typical machine might
- * have characters from 30 blocks, giving 15616 bytes. */
-struct rufl_substitution_table {
-	/** Index table. Each entry represents a block of 256 characters, so
-	 * i[k] refers to characters [256*k, 256*(k+1)). The value is either
-	 * BLOCK_NONE_AVAILABLE or an offset into the block table. */
-	unsigned char index[256];
-	/** None of the characters in the block are available in any font. */
-#	define BLOCK_NONE_AVAILABLE 255
-
-	/** Block table. Each entry is a map from the characters in the block
-	 * to a font number which includes it, or NOT_AVAILABLE. */
-	unsigned short block[255][256];
-	/** No font contains this character. */
-#	define NOT_AVAILABLE 65535
-};
-
-
+/** No font contains this character. */
+#define NOT_AVAILABLE 65535
 /** Font substitution table. */
-extern struct rufl_substitution_table *rufl_substitution_table;
+extern unsigned short *rufl_substitution_table;
 
 
 /** Number of slots in recent-use cache. This is the maximum number of RISC OS
@@ -128,7 +112,6 @@ extern bool rufl_old_font_manager;
 
 bool rufl_character_set_test(struct rufl_character_set *charset,
 		unsigned int c);
-unsigned int rufl_substitution_lookup(unsigned int c);
 
 
 #define rufl_utf8_read(s, l, u)						       \
diff --git a/rufl_paint.c b/rufl_paint.c
index 8c39637..ffafb1b 100644
--- a/rufl_paint.c
+++ b/rufl_paint.c
@@ -164,7 +164,7 @@ rufl_code rufl_process(rufl_action action,
 	if (rufl_character_set_test(charset, u))
 		font1 = font;
 	else
-		font1 = rufl_substitution_lookup(u);
+		font1 = rufl_substitution_table[u];
 	do {
 		s[0] = u;
 		offset_map[0] = offset_u;
@@ -179,7 +179,7 @@ rufl_code rufl_process(rufl_action action,
 			if (rufl_character_set_test(charset, u))
 				font1 = font;
 			else
-				font1 = rufl_substitution_lookup(u);
+				font1 = rufl_substitution_table[u];
 			if (font1 == font0)
 				n++;
 		}