Skip to contentSkip to conversation

Use hfs case ordering - another try

PATCH In review Pavel Roskin 3 participants 9 messages Mar 9, 2009 – Mar 31, 2009

lore
Share & tools
lore
#0 lore raw

PATCH 1/1 Use hfs case ordering - another try

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.

hfs.c +240 -1
Index: fs/hfs.c
===================================================================
@@ -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.  */
Signature · 2 lines
Regards,
Pavel Roskin

#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;
}

#1 lore raw
Quoted 10 lines · Pavel Roskin

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.

Quoted 4 lines

ChangeLog:

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

Seems good to me. Thanks Pavel.

Signature · 5 lines
Robert Millan

  The DRM opt-in fallacy: "Your data belongs to us. We will decide when (and
  how) you may access your data; but nobody's threatening your freedom: we
  still allow you to remove your data and not access it at all."
#2 lore raw
In reply to Pavel Roskin

Hi Pavel,

Quoted 9 lines · Pavel Roskin

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.

Thanks for rescuing this fix!

Felix uploaded a new GRUB snapshot which should include this patch.

However, I'm having the same boot problems as before. I've installed the new version of GRUB to OF, and when I boot I get the known "initrd:
command not found" error.

Furthermore, the search command still appears to fail on at least Apple OF, and if it's in my boot commandlist, it'll set root to an invalid device, making the boot fail with "you need to load the kernel first".

Has anyone else had success with this patch in Debian or using SVN/Git code, on PPC?

Thanks,
Jordi

Signature · 3 lines
Jordi Mallach Pérez  --  Debian developer     http://www.debian.org/
[email protected]     [email protected]     http://www.sindominio.net/
GnuPG public key information available at http://oskuro.net/
#3 lore raw
Quoted 5 lines · Jordi Mallach

Thanks for rescuing this fix!

Felix uploaded a new GRUB snapshot which should include this patch.

However, I'm having the same boot problems as before.

Please realize that the hfs fix is just a part of what needs to be done.

For GRUB to be a drop-in replacement for yaboot (at least on Fedora), the installation script should be able to understand the layout where only few files are located on the true boot partition (in hfs format, perhaps not mounted), whereas most GRUB files and kernels are placed on a "second boot partition" in ext2 format mounted under /boot.

I know not everybody likes this, so the script should keep the ability to support layouts with one boot partition in hfs format.

The only machine I have to test it is a very slow G3 PowerMac, and I cannot spend much time on it. I don't want to change partitioning to satisfy the current grub-install.

Signature · 2 lines
Regards,
Pavel Roskin
#4 lore raw

Hi,

Quoted 7 lines · Pavel Roskin

Please realize that the hfs fix is just a part of what needs to be done.

For GRUB to be a drop-in replacement for yaboot (at least on Fedora), the installation script should be able to understand the layout where only few files are located on the true boot partition (in hfs format, perhaps not mounted), whereas most GRUB files and kernels are placed on a "second boot partition" in ext2 format mounted under /boot.

I agree that grub-install and the other tools should know more about /boot/grub being a separate partition in order to be able to mount it for a correct install. Not so much on the two boostrap partitions, my tiny one as generated by the Debian installer ages ago is good enough to hold a copy of GRUB and a "just in case" copy of yaboot. But of course, this could be an optional setup.

/dev/hda2 974K 697K 278K 72% /boot/grub

See Michel Dänzer's post I just forwarded. Besides what you pointed out, it seems there are other serious problems with the new HFS patch which make it fail as before.

Jordi

Signature · 3 lines
Jordi Mallach Pérez  --  Debian developer     http://www.debian.org/
[email protected]     [email protected]     http://www.sindominio.net/
GnuPG public key information available at http://oskuro.net/
#5 lore raw
Quoted 11 lines · Jordi Mallach

Hi,

Quoted 7 lines · Pavel Roskin

Please realize that the hfs fix is just a part of what needs to be done.

For GRUB to be a drop-in replacement for yaboot (at least on Fedora), the installation script should be able to understand the layout where only few files are located on the true boot partition (in hfs format, perhaps not mounted), whereas most GRUB files and kernels are placed on a "second boot partition" in ext2 format mounted under /boot.

Quoted 8 lines

I agree that grub-install and the other tools should know more about /boot/grub being a separate partition in order to be able to mount it for a correct install. Not so much on the two boostrap partitions, my tiny one as generated by the Debian installer ages ago is good enough to hold a copy of GRUB and a "just in case" copy of yaboot. But of course, this could be an optional setup.

/dev/hda2 974K 697K 278K 72% /boot/grub

It's OK for GRUB, but it's not big enough to hold kernels. Also, distributions may be reluctant to break the assumption that the kernels are located on a filesystem with POSIX access control and three kinds of timestamps.

Quoted 3 lines

See Michel Dänzer's post I just forwarded. Besides what you pointed out, it seems there are other serious problems with the new HFS patch which make it fail as before.

My bad. Fixed now. Thank you!

Signature · 2 lines
Regards,
Pavel Roskin
#6 lore raw
Quoted 7 lines · Pavel Roskin
Quoted 7 lines

I agree that grub-install and the other tools should know more about /boot/grub being a separate partition in order to be able to mount it for a correct install. Not so much on the two boostrap partitions, my tiny one as generated by the Debian installer ages ago is good enough to hold a copy of GRUB and a "just in case" copy of yaboot. But of course, this could be an optional setup.

Quoted 6 lines
Quoted 1 line

/dev/hda2 974K 697K 278K 72% /boot/grub

It's OK for GRUB, but it's not big enough to hold kernels. Also, distributions may be reluctant to break the assumption that the kernels are located on a filesystem with POSIX access control and three kinds of timestamps.

If you mean standard stuff people tend to boot (ie, Linux), every distribution out there installs them and expects them to be in /boot, not /boot/grub.

My /boot partition is in this case part of the bigger / partition, but if it was separate it'd be big enough to hold quite a few kernels and so on.

I really don't see what you mean here.

Quoted 4 lines
Quoted 3 lines

See Michel Dänzer's post I just forwarded. Besides what you pointed out, it seems there are other serious problems with the new HFS patch which make it fail as before.

My bad. Fixed now. Thank you!

Great! Thanks Michel and Pavel! I've give it a go soonish.

Jordi

Signature · 3 lines
Jordi Mallach Pérez  --  Debian developer     http://www.debian.org/
[email protected]     [email protected]     http://www.sindominio.net/
GnuPG public key information available at http://oskuro.net/
#7 lore raw

Quoting Jordi Mallach <[email protected]>:

Quoted 10 lines
Quoted 6 lines
Quoted 1 line

/dev/hda2 974K 697K 278K 72% /boot/grub

It's OK for GRUB, but it's not big enough to hold kernels. Also, distributions may be reluctant to break the assumption that the kernels are located on a filesystem with POSIX access control and three kinds of timestamps.

If you mean standard stuff people tend to boot (ie, Linux), every distribution out there installs them and expects them to be in /boot, not /boot/grub.

I'm sorry, I didn't realize your /boot/grub/ is on hfs and /boot is not. Never mind.

Signature · 2 lines
Regards,
Pavel Roskin
#8 lore raw
In reply to Jordi Mallach

Hi, I'm attaching Michel's reply to this post, as he isn't subscribed.

Quoted 10 lines · Jordi Mallach

However, I'm having the same boot problems as before. I've installed the new version of GRUB to OF, and when I boot I get the known "initrd:
command not found" error.

Furthermore, the search command still appears to fail on at least Apple OF, and if it's in my boot commandlist, it'll set root to an invalid device, making the boot fail with "you need to load the kernel first".

Has anyone else had success with this patch in Debian or using SVN/Git code, on PPC?

Signature · 3 lines
Jordi Mallach Pérez  --  Debian developer     http://www.debian.org/
[email protected]     [email protected]     http://www.sindominio.net/
GnuPG public key information available at http://oskuro.net/
Quoted 20 lines · Jordi Mallach
Quoted 9 lines · Pavel Roskin

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.

Thanks for rescuing this fix!

Felix uploaded a new GRUB snapshot which should include this patch.

However, I'm having the same boot problems as before. I've installed the new version of GRUB to OF, and when I boot I get the known "initrd:
command not found" error.

Quoted 6 lines

Furthermore, the search command still appears to fail on at least Apple OF, and if it's in my boot commandlist, it'll set root to an invalid device, making the boot fail with "you need to load the kernel first".

Has anyone else had success with this patch in Debian or using SVN/Git code, on PPC?

I didn't get around to trying Pavel's patch, but from your description it most likely didn't fix the problem properly. Do grub2 file access commands like hexdump or cat work for special filenames like _linux.mod?

Looking at Pavel's patch, one problem that jumps out immediately is that it doesn't handle the string lengths correctly. HFS strings aren't zero-terminated, so grub_hfs_cmp_catkeys() needs to make sure it only compares characters up to the length of min(k1->strlen, k2->strlen) and if they all match, return k1->strlen - k2->strlen.

I'm not sure that's what causes your problem though Jordi, but anyway, why wasn't I CC'd on the new patch? :(

Signature · 2 lines
Earthling Michel Dänzer           |                http://www.vmware.com
Libre software enthusiast         |          Debian, X and DRI developer