[PATCH] Use hfs case ordering - another try

[Pavel Roskin <proski@gnu.org>]

[-- Attachment #1: Type: text/plain, Size: 6228 bytes --]

Hello!

It's a shame the discussion about hfs got nowhere.  I've made another
patch.  I didn't look at the Linux hfs sources or at any previous
patches.  I took the case ordering table from hfsutils 3.2.6, which is
licensed under GPL v2 or newer.  Then I ran the table through a simple
program to make it more readable (attached for reference).  The values
in the table have been normalized to avoid gaps.  Values for equal
characters are initialized on the same line for readability.

ChangeLog:

	* fs/hfs.c (grub_hfs_strncasecmp): New function.
	(grub_hfs_cmp_catkeys): Use HFS specific string comparison.

Index: fs/hfs.c
===================================================================
--- fs/hfs.c	(revision 2022)
+++ fs/hfs.c	(working copy)
@@ -390,7 +390,246 @@
   return 0;
 }
 
+/* Case insensitive string comparison using HFS character ordering */
+static int
+grub_hfs_strncasecmp (const unsigned char *s1, const unsigned char *s2,
+		      grub_size_t n)
+{
+  /* Taken from hfsutils 3.2.6 and converted to a readable form */
+  static const unsigned char hfs_charorder[256] = {
+    [0x00] = 0,
+    [0x01] = 1,
+    [0x02] = 2,
+    [0x03] = 3,
+    [0x04] = 4,
+    [0x05] = 5,
+    [0x06] = 6,
+    [0x07] = 7,
+    [0x08] = 8,
+    [0x09] = 9,
+    [0x0A] = 10,
+    [0x0B] = 11,
+    [0x0C] = 12,
+    [0x0D] = 13,
+    [0x0E] = 14,
+    [0x0F] = 15,
+    [0x10] = 16,
+    [0x11] = 17,
+    [0x12] = 18,
+    [0x13] = 19,
+    [0x14] = 20,
+    [0x15] = 21,
+    [0x16] = 22,
+    [0x17] = 23,
+    [0x18] = 24,
+    [0x19] = 25,
+    [0x1A] = 26,
+    [0x1B] = 27,
+    [0x1C] = 28,
+    [0x1D] = 29,
+    [0x1E] = 30,
+    [0x1F] = 31,
+    [' '] = 32,		[0xCA] = 32,
+    ['!'] = 33,
+    ['"'] = 34,
+    [0xD2] = 35,
+    [0xD3] = 36,
+    [0xC7] = 37,
+    [0xC8] = 38,
+    ['#'] = 39,
+    ['$'] = 40,
+    ['%'] = 41,
+    ['&'] = 42,
+    ['\''] = 43,
+    [0xD4] = 44,
+    [0xD5] = 45,
+    ['('] = 46,
+    [')'] = 47,
+    ['*'] = 48,
+    ['+'] = 49,
+    [','] = 50,
+    ['-'] = 51,
+    ['.'] = 52,
+    ['/'] = 53,
+    ['0'] = 54,
+    ['1'] = 55,
+    ['2'] = 56,
+    ['3'] = 57,
+    ['4'] = 58,
+    ['5'] = 59,
+    ['6'] = 60,
+    ['7'] = 61,
+    ['8'] = 62,
+    ['9'] = 63,
+    [':'] = 64,
+    [';'] = 65,
+    ['<'] = 66,
+    ['='] = 67,
+    ['>'] = 68,
+    ['?'] = 69,
+    ['@'] = 70,
+    ['A'] = 71,		['a'] = 71,
+    [0x88] = 72,	[0xCB] = 72,
+    [0x80] = 73,	[0x8A] = 73,
+    [0x8B] = 74,	[0xCC] = 74,
+    [0x81] = 75,	[0x8C] = 75,
+    [0xAE] = 76,	[0xBE] = 76,
+    ['`'] = 77,
+    [0x87] = 78,
+    [0x89] = 79,
+    [0xBB] = 80,
+    ['B'] = 81,		['b'] = 81,
+    ['C'] = 82,		['c'] = 82,
+    [0x82] = 83,	[0x8D] = 83,
+    ['D'] = 84,		['d'] = 84,
+    ['E'] = 85,		['e'] = 85,
+    [0x83] = 86,	[0x8E] = 86,
+    [0x8F] = 87,
+    [0x90] = 88,
+    [0x91] = 89,
+    ['F'] = 90,		['f'] = 90,
+    ['G'] = 91,		['g'] = 91,
+    ['H'] = 92,		['h'] = 92,
+    ['I'] = 93,		['i'] = 93,
+    [0x92] = 94,
+    [0x93] = 95,
+    [0x94] = 96,
+    [0x95] = 97,
+    ['J'] = 98,		['j'] = 98,
+    ['K'] = 99,		['k'] = 99,
+    ['L'] = 100,	['l'] = 100,
+    ['M'] = 101,	['m'] = 101,
+    ['N'] = 102,	['n'] = 102,
+    [0x84] = 103,	[0x96] = 103,
+    ['O'] = 104,	['o'] = 104,
+    [0x85] = 105,	[0x9A] = 105,
+    [0x9B] = 106,	[0xCD] = 106,
+    [0xAF] = 107,	[0xBF] = 107,
+    [0xCE] = 108,	[0xCF] = 108,
+    [0x97] = 109,
+    [0x98] = 110,
+    [0x99] = 111,
+    [0xBC] = 112,
+    ['P'] = 113,	['p'] = 113,
+    ['Q'] = 114,	['q'] = 114,
+    ['R'] = 115,	['r'] = 115,
+    ['S'] = 116,	['s'] = 116,
+    [0xA7] = 117,
+    ['T'] = 118,	['t'] = 118,
+    ['U'] = 119,	['u'] = 119,
+    [0x86] = 120,	[0x9F] = 120,
+    [0x9C] = 121,
+    [0x9D] = 122,
+    [0x9E] = 123,
+    ['V'] = 124,	['v'] = 124,
+    ['W'] = 125,	['w'] = 125,
+    ['X'] = 126,	['x'] = 126,
+    ['Y'] = 127,	['y'] = 127,
+    [0xD8] = 128,
+    ['Z'] = 129,	['z'] = 129,
+    ['['] = 130,
+    ['\\'] = 131,
+    [']'] = 132,
+    ['^'] = 133,
+    ['_'] = 134,
+    ['{'] = 135,
+    ['|'] = 136,
+    ['}'] = 137,
+    ['~'] = 138,
+    [0x7F] = 139,
+    [0xA0] = 140,
+    [0xA1] = 141,
+    [0xA2] = 142,
+    [0xA3] = 143,
+    [0xA4] = 144,
+    [0xA5] = 145,
+    [0xA6] = 146,
+    [0xA8] = 147,
+    [0xA9] = 148,
+    [0xAA] = 149,
+    [0xAB] = 150,
+    [0xAC] = 151,
+    [0xAD] = 152,
+    [0xB0] = 153,
+    [0xB1] = 154,
+    [0xB2] = 155,
+    [0xB3] = 156,
+    [0xB4] = 157,
+    [0xB5] = 158,
+    [0xB6] = 159,
+    [0xB7] = 160,
+    [0xB8] = 161,
+    [0xB9] = 162,
+    [0xBA] = 163,
+    [0xBD] = 164,
+    [0xC0] = 165,
+    [0xC1] = 166,
+    [0xC2] = 167,
+    [0xC3] = 168,
+    [0xC4] = 169,
+    [0xC5] = 170,
+    [0xC6] = 171,
+    [0xC9] = 172,
+    [0xD0] = 173,
+    [0xD1] = 174,
+    [0xD6] = 175,
+    [0xD7] = 176,
+    [0xD9] = 177,
+    [0xDA] = 178,
+    [0xDB] = 179,
+    [0xDC] = 180,
+    [0xDD] = 181,
+    [0xDE] = 182,
+    [0xDF] = 183,
+    [0xE0] = 184,
+    [0xE1] = 185,
+    [0xE2] = 186,
+    [0xE3] = 187,
+    [0xE4] = 188,
+    [0xE5] = 189,
+    [0xE6] = 190,
+    [0xE7] = 191,
+    [0xE8] = 192,
+    [0xE9] = 193,
+    [0xEA] = 194,
+    [0xEB] = 195,
+    [0xEC] = 196,
+    [0xED] = 197,
+    [0xEE] = 198,
+    [0xEF] = 199,
+    [0xF0] = 200,
+    [0xF1] = 201,
+    [0xF2] = 202,
+    [0xF3] = 203,
+    [0xF4] = 204,
+    [0xF5] = 205,
+    [0xF6] = 206,
+    [0xF7] = 207,
+    [0xF8] = 208,
+    [0xF9] = 209,
+    [0xFA] = 210,
+    [0xFB] = 211,
+    [0xFC] = 212,
+    [0xFD] = 213,
+    [0xFE] = 214,
+    [0xFF] = 215,
+  };
 
+  if (n == 0)
+    return 0;
+
+  while (*s1 && *s2 && --n)
+    {
+      if (hfs_charorder[*s1] != hfs_charorder[*s2])
+	break;
+
+      s1++;
+      s2++;
+    }
+
+  return (int) hfs_charorder[*s1] - (int) hfs_charorder[*s2];
+}
+
 /* Compare the K1 and K2 catalog file keys.  */
 static int
 grub_hfs_cmp_catkeys (struct grub_hfs_catalog_key *k1,
@@ -402,7 +641,7 @@
   if (cmp != 0)
     return cmp;
   
-  cmp = grub_strncasecmp ((char *) (k1->str), (char *) (k2->str), k1->strlen);
+  cmp = grub_hfs_strncasecmp (k1->str, k2->str, k1->strlen);
   
   /* This is required because the compared strings are not of equal
      length.  */


-- 
Regards,
Pavel Roskin

[-- Attachment #2: hfsnormalize.c --]
[-- Type: text/x-csrc, Size: 2194 bytes --]

#include <stdio.h>

static const unsigned char hfs_charorder[256] = {
  0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07,
  0x08, 0x09, 0x0a, 0x0b, 0x0c, 0x0d, 0x0e, 0x0f,
  0x10, 0x11, 0x12, 0x13, 0x14, 0x15, 0x16, 0x17,
  0x18, 0x19, 0x1a, 0x1b, 0x1c, 0x1d, 0x1e, 0x1f,

  0x20, 0x22, 0x23, 0x28, 0x29, 0x2a, 0x2b, 0x2c,
  0x2f, 0x30, 0x31, 0x32, 0x33, 0x34, 0x35, 0x36,
  0x37, 0x38, 0x39, 0x3a, 0x3b, 0x3c, 0x3d, 0x3e,
  0x3f, 0x40, 0x41, 0x42, 0x43, 0x44, 0x45, 0x46,

  0x47, 0x48, 0x58, 0x5a, 0x5e, 0x60, 0x67, 0x69,
  0x6b, 0x6d, 0x73, 0x75, 0x77, 0x79, 0x7b, 0x7f,
  0x8d, 0x8f, 0x91, 0x93, 0x96, 0x98, 0x9f, 0xa1,
  0xa3, 0xa5, 0xa8, 0xaa, 0xab, 0xac, 0xad, 0xae,

  0x54, 0x48, 0x58, 0x5a, 0x5e, 0x60, 0x67, 0x69,
  0x6b, 0x6d, 0x73, 0x75, 0x77, 0x79, 0x7b, 0x7f,
  0x8d, 0x8f, 0x91, 0x93, 0x96, 0x98, 0x9f, 0xa1,
  0xa3, 0xa5, 0xa8, 0xaf, 0xb0, 0xb1, 0xb2, 0xb3,

  0x4c, 0x50, 0x5c, 0x62, 0x7d, 0x81, 0x9a, 0x55,
  0x4a, 0x56, 0x4c, 0x4e, 0x50, 0x5c, 0x62, 0x64,
  0x65, 0x66, 0x6f, 0x70, 0x71, 0x72, 0x7d, 0x89,
  0x8a, 0x8b, 0x81, 0x83, 0x9c, 0x9d, 0x9e, 0x9a,

  0xb4, 0xb5, 0xb6, 0xb7, 0xb8, 0xb9, 0xba, 0x95,
  0xbb, 0xbc, 0xbd, 0xbe, 0xbf, 0xc0, 0x52, 0x85,
  0xc1, 0xc2, 0xc3, 0xc4, 0xc5, 0xc6, 0xc7, 0xc8,
  0xc9, 0xca, 0xcb, 0x57, 0x8c, 0xcc, 0x52, 0x85,

  0xcd, 0xce, 0xcf, 0xd0, 0xd1, 0xd2, 0xd3, 0x26,
  0x27, 0xd4, 0x20, 0x4a, 0x4e, 0x83, 0x87, 0x87,
  0xd5, 0xd6, 0x24, 0x25, 0x2d, 0x2e, 0xd7, 0xd8,
  0xa7, 0xd9, 0xda, 0xdb, 0xdc, 0xdd, 0xde, 0xdf,

  0xe0, 0xe1, 0xe2, 0xe3, 0xe4, 0xe5, 0xe6, 0xe7,
  0xe8, 0xe9, 0xea, 0xeb, 0xec, 0xed, 0xee, 0xef,
  0xf0, 0xf1, 0xf2, 0xf3, 0xf4, 0xf5, 0xf6, 0xf7,
  0xf8, 0xf9, 0xfa, 0xfb, 0xfc, 0xfd, 0xfe, 0xff
};

int
main ()
{
  int val;
  int i;
  int nval = -1;
  int used;

  for (val = 0; val < 256; val++)
    {
      used = 0;
      for (i = 0; i < 256; i++)
	{
	  if (hfs_charorder[i] == val)
	    {
	      if (!used)
		{
		  used = 1;
		  nval++;
		  printf ("\n");
		}
	      if (i == '\'' || i == '\\')
		printf ("\t['\\%c'] = %d,", i, nval);
	      else if (i >= 32 && i <= 126)
		printf ("\t['%c'] = %d,", i, nval);
	      else
		printf ("\t[0x%02X] = %d,", i, nval);
	    }
	}
    }
  printf ("\n");
  return 0;
}