[PATCH 1/1] applet_tables: make number of stored offsets depend on NUM_APPLETS

[Ron Yorston]

Modify the applet_tables build tool to adjust the trade off between
performance and bloat as the number of applets varies.

The runtime code is unchanged.

Signed-off-by: Ron Yorston <rmy at pobox.com>
---
 applets/applet_tables.c | 71 +++++++++++++++++++++++++++++++------------------
 1 file changed, 45 insertions(+), 26 deletions(-)

diff --git a/applets/applet_tables.c b/applets/applet_tables.c
index 48544f0..450cdac 100644
--- a/applets/applet_tables.c
+++ b/applets/applet_tables.c
@@ -58,38 +58,57 @@ static int str_isalnum_(const char *s)
 	return 1;
 }
 
-// Before linear search, narrow it down by looking at N "equidistant" names:
-// KNOWN_APPNAME_OFFSETS  cycles  code_size
-//                     0    9057
-//                     2    4604        +32
-//                     4    2407        +75
-//                     8    1342        +98
-//                    16     908       +130
-//                    32     884       +194
-// With 8, applet_nameofs[] table has 7 elements.
-#define KNOWN_APPNAME_OFFSETS 8
+// Before linear search, narrow it down to a block of APPNAME_BLOCK_SIZE names:
+//
+// block size       25              30              35              40
+//
+//  applets   cycles  bloat   cycles  bloat   cycles  bloat   cycles  bloat
+//    13      224.07     0    224.07     0    224.07     0    224.07     0
+//    28      462.83     0    462.83     0    462.83     0    462.83     0
+//    48      840.88     0    840.88     0    840.88     0    840.88     0
+//    72      703.86    57    703.86    57    703.86    57   1212.37     0
+//    96      678.07    90    678.07    90    941.25    57    941.25    57
+//   133      665.84   114    740.55    93    927.43    91    927.43    91
+//   172      745.96   118    829.50   114    951.37    93    951.37    93
+//   214      756.17   109    818.73   122    900.33   118   1028.08   114
+//   281      798.10   138    863.99   130    949.66   109   1062.82   122
+//   364      861.78   148    910.64   140   1016.15   132   1060.04   128
+//   494      937.61   168    970.37   139   1052.08   148   1125.15   140
+// The preprocessor symbol KNOWN_APPNAME_OFFSETS is exported to the
+// runtime code.  It's the size of the applet_nameofs array (plus one,
+// because we don't store the offset zero).
+#define APPNAME_BLOCK_SIZE 35
 
 int main(int argc, char **argv)
 {
 	int i, j;
-	int ofs, offset[KNOWN_APPNAME_OFFSETS], index[KNOWN_APPNAME_OFFSETS];
+	int ofs, *offset, *index, num_offsets;
 //	unsigned MAX_APPLET_NAME_LEN = 1;
 
 	qsort(applets, NUM_APPLETS, sizeof(applets[0]), cmp_name);
 
-	for (i = 0; i < KNOWN_APPNAME_OFFSETS; i++)
-		index[i] = i * NUM_APPLETS / KNOWN_APPNAME_OFFSETS;
-
-	ofs = 0;
-	for (i = 0; i < NUM_APPLETS; i++) {
-		for (j = 0; j < KNOWN_APPNAME_OFFSETS; j++)
-			if (i == index[j])
-				offset[j] = ofs;
-		ofs += strlen(applets[i].name) + 1;
+	num_offsets = NUM_APPLETS / APPNAME_BLOCK_SIZE;
+	if (num_offsets >= 2) {
+		offset = malloc(sizeof(offset)*num_offsets);
+		index = malloc(sizeof(index)*num_offsets);
+		if (offset == NULL || index == NULL)
+			return -1;
+
+		for (i = 0; i < num_offsets; i++)
+			index[i] = i * NUM_APPLETS / num_offsets;
+
+		ofs = 0;
+		for (i = 0; i < NUM_APPLETS; i++) {
+			for (j = 0; j < num_offsets; j++)
+				if (i == index[j])
+					offset[j] = ofs;
+			ofs += strlen(applets[i].name) + 1;
+		}
+		/* If the list of names is too long refuse to proceed */
+		if (ofs > 0xffff)
+			return 1;
 	}
-	/* If the list of names is too long refuse to proceed */
-	if (ofs > 0xffff)
-		return 1;
+
 	if (!argv[1])
 		return 1;
 
@@ -108,10 +127,10 @@ int main(int argc, char **argv)
 		printf("#define SINGLE_APPLET_MAIN %s_main\n", applets[0].main);
 	}
 
-	if (KNOWN_APPNAME_OFFSETS > 0 && NUM_APPLETS > 2*KNOWN_APPNAME_OFFSETS) {
-		printf("#define KNOWN_APPNAME_OFFSETS %u\n\n", KNOWN_APPNAME_OFFSETS);
+	if (num_offsets >= 2) {
+		printf("#define KNOWN_APPNAME_OFFSETS %u\n\n", num_offsets);
 		printf("const uint16_t applet_nameofs[] ALIGN2 = {\n");
-		for (i = 1; i < KNOWN_APPNAME_OFFSETS; i++)
+		for (i = 1; i < num_offsets; i++)
 			printf("%d,\n", offset[i]);
 		printf("};\n\n");
 	}
-- 
2.5.5