Speed up the case-insensitive lookups.

3 files changed, 127 insertions, 12 deletions

diff --git a/ChangeLog b/ChangeLog
index daf970c..48234ea 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,5 +1,12 @@
 2003-01-07  Bruno Haible  <bruno@clisp.org>
 
+	* src/output.cc (USE_DOWNCASE_TABLE): New macro.
+	(output_upperlower_table): New function.
+	(output_upperlower_strcmp, output_upperlower_strncmp,
+	output_upperlower_memcmp): Emit gperf_downcase array accesses.
+	(Output::output): Call output_upperlower_table.
+	* tests/permutc2.exp: Update.
+
 	* src/keyword-list.icc (KeywordExt_List::rest): Use a portable cast.
 	(Only in GCC a cast of an lvalue is an lvalue.)
 
diff --git a/src/output.cc b/src/output.cc
index 484d583..3a23647 100644
--- a/src/output.cc
+++ b/src/output.cc
@@ -230,6 +230,42 @@ Output::output_constants (struct Output_Constants& style) const
 
 /* ------------------------------------------------------------------------- */
 
+/* We use a downcase table because when called repeatedly, the code
+       gperf_downcase[c]
+   is faster than
+       if (c >= 'A' && c <= 'Z')
+         c += 'a' - 'A';
+ */
+#define USE_DOWNCASE_TABLE 1
+
+#if USE_DOWNCASE_TABLE
+
+/* Output gperf's ASCII-downcase table.  */
+
+static void
+output_upperlower_table ()
+{
+  unsigned int c;
+
+  printf ("#ifndef GPERF_DOWNCASE\n"
+          "#define GPERF_DOWNCASE 1\n"
+          "static unsigned char gperf_downcase[256] =\n"
+          "  {");
+  for (c = 0; c < 256; c++)
+    {
+      if ((c % 15) == 0)
+        printf ("\n   ");
+      printf (" %3d", c >= 'A' && c <= 'Z' ? c + 'a' - 'A' : c);
+      if (c < 255)
+        printf (",");
+    }
+  printf ("\n"
+          "  };\n"
+          "#endif\n\n");
+}
+
+#endif
+
 /* Output gperf's ASCII-case insensitive strcmp replacement.  */
 
 static void
@@ -250,6 +286,18 @@ output_upperlower_strcmp ()
           option[ANSIC] | option[CPLUSPLUS] ?
                "(register const char *s1, register const char *s2)\n" :
           "");
+  #if USE_DOWNCASE_TABLE
+  printf ("{\n"
+          "  for (;;)\n"
+          "    {\n"
+          "      unsigned char c1 = gperf_downcase[(unsigned char)*s1++];\n"
+          "      unsigned char c2 = gperf_downcase[(unsigned char)*s2++];\n"
+          "      if (c1 != 0 && c1 == c2)\n"
+          "        continue;\n"
+          "      return (int)c1 - (int)c2;\n"
+          "    }\n"
+          "}\n");
+  #else
   printf ("{\n"
           "  for (;;)\n"
           "    {\n"
@@ -263,8 +311,9 @@ output_upperlower_strcmp ()
           "        continue;\n"
           "      return (int)c1 - (int)c2;\n"
           "    }\n"
-          "}\n"
-          "#endif\n\n");
+          "}\n");
+  #endif
+  printf ("#endif\n\n");
 }
 
 /* Output gperf's ASCII-case insensitive strncmp replacement.  */
@@ -289,6 +338,22 @@ output_upperlower_strncmp ()
           option[ANSIC] | option[CPLUSPLUS] ?
                "(register const char *s1, register const char *s2, register unsigned int n)\n" :
           "");
+  #if USE_DOWNCASE_TABLE
+  printf ("{\n"
+          "  for (; n > 0;)\n"
+          "    {\n"
+          "      unsigned char c1 = gperf_downcase[(unsigned char)*s1++];\n"
+          "      unsigned char c2 = gperf_downcase[(unsigned char)*s2++];\n"
+          "      if (c1 != 0 && c1 == c2)\n"
+          "        {\n"
+          "          n--;\n"
+          "          continue;\n"
+          "        }\n"
+          "      return (int)c1 - (int)c2;\n"
+          "    }\n"
+          "  return 0;\n"
+          "}\n");
+  #else
   printf ("{\n"
           "  for (; n > 0;)\n"
           "    {\n"
@@ -306,8 +371,9 @@ output_upperlower_strncmp ()
           "      return (int)c1 - (int)c2;\n"
           "    }\n"
           "  return 0;\n"
-          "}\n"
-          "#endif\n\n");
+          "}\n");
+  #endif
+  printf ("#endif\n\n");
 }
 
 /* Output gperf's ASCII-case insensitive memcmp replacement.  */
@@ -332,6 +398,22 @@ output_upperlower_memcmp ()
           option[ANSIC] | option[CPLUSPLUS] ?
                "(register const char *s1, register const char *s2, register unsigned int n)\n" :
           "");
+  #if USE_DOWNCASE_TABLE
+  printf ("{\n"
+          "  for (; n > 0;)\n"
+          "    {\n"
+          "      unsigned char c1 = gperf_downcase[(unsigned char)*s1++];\n"
+          "      unsigned char c2 = gperf_downcase[(unsigned char)*s2++];\n"
+          "      if (c1 == c2)\n"
+          "        {\n"
+          "          n--;\n"
+          "          continue;\n"
+          "        }\n"
+          "      return (int)c1 - (int)c2;\n"
+          "    }\n"
+          "  return 0;\n"
+          "}\n");
+  #else
   printf ("{\n"
           "  for (; n > 0;)\n"
           "    {\n"
@@ -349,8 +431,9 @@ output_upperlower_memcmp ()
           "      return (int)c1 - (int)c2;\n"
           "    }\n"
           "  return 0;\n"
-          "}\n"
-          "#endif\n\n");
+          "}\n");
+  #endif
+  printf ("#endif\n\n");
 }
 
 /* ------------------------------------------------------------------------- */
@@ -1903,6 +1986,10 @@ Output::output ()
 
   if (option[UPPERLOWER])
     {
+      #if USE_DOWNCASE_TABLE
+      output_upperlower_table ();
+      #endif
+
       if (option[LENTABLE])
         output_upperlower_memcmp ();
       else
diff --git a/tests/permutc2.exp b/tests/permutc2.exp
index 30eb911..749d87e 100644
--- a/tests/permutc2.exp
+++ b/tests/permutc2.exp
@@ -13,6 +13,31 @@
 #define MAX_HASH_VALUE 9
 /* maximum key range = 8, duplicates = 0 */
 
+#ifndef GPERF_DOWNCASE
+#define GPERF_DOWNCASE 1
+static unsigned char gperf_downcase[256] =
+  {
+      0,   1,   2,   3,   4,   5,   6,   7,   8,   9,  10,  11,  12,  13,  14,
+     15,  16,  17,  18,  19,  20,  21,  22,  23,  24,  25,  26,  27,  28,  29,
+     30,  31,  32,  33,  34,  35,  36,  37,  38,  39,  40,  41,  42,  43,  44,
+     45,  46,  47,  48,  49,  50,  51,  52,  53,  54,  55,  56,  57,  58,  59,
+     60,  61,  62,  63,  64,  97,  98,  99, 100, 101, 102, 103, 104, 105, 106,
+    107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121,
+    122,  91,  92,  93,  94,  95,  96,  97,  98,  99, 100, 101, 102, 103, 104,
+    105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119,
+    120, 121, 122, 123, 124, 125, 126, 127, 128, 129, 130, 131, 132, 133, 134,
+    135, 136, 137, 138, 139, 140, 141, 142, 143, 144, 145, 146, 147, 148, 149,
+    150, 151, 152, 153, 154, 155, 156, 157, 158, 159, 160, 161, 162, 163, 164,
+    165, 166, 167, 168, 169, 170, 171, 172, 173, 174, 175, 176, 177, 178, 179,
+    180, 181, 182, 183, 184, 185, 186, 187, 188, 189, 190, 191, 192, 193, 194,
+    195, 196, 197, 198, 199, 200, 201, 202, 203, 204, 205, 206, 207, 208, 209,
+    210, 211, 212, 213, 214, 215, 216, 217, 218, 219, 220, 221, 222, 223, 224,
+    225, 226, 227, 228, 229, 230, 231, 232, 233, 234, 235, 236, 237, 238, 239,
+    240, 241, 242, 243, 244, 245, 246, 247, 248, 249, 250, 251, 252, 253, 254,
+    255
+  };
+#endif
+
 #ifndef GPERF_CASE_STRCMP
 #define GPERF_CASE_STRCMP 1
 static int
@@ -22,12 +47,8 @@ gperf_case_strcmp (s1, s2)
 {
   for (;;)
     {
-      unsigned char c1 = *s1++;
-      unsigned char c2 = *s2++;
-      if (c1 >= 'A' && c1 <= 'Z')
-        c1 += 'a' - 'A';
-      if (c2 >= 'A' && c2 <= 'Z')
-        c2 += 'a' - 'A';
+      unsigned char c1 = gperf_downcase[(unsigned char)*s1++];
+      unsigned char c2 = gperf_downcase[(unsigned char)*s2++];
       if (c1 != 0 && c1 == c2)
         continue;
       return (int)c1 - (int)c2;