Re: State of GRUB on PowerPC

Re: State of GRUB on PowerPC

[Michel Dänzer]

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


I was able to reproduce Jordi's findings on my PowerBook G4. (Well,
except device.map seems to get generated correctly and the search
command seems to work for me, maybe this is due to differences between
our OF device trees or something like that)

After some printf-style debugging over the weekend, the failure to load
some modules indeed turns out to be an hfs.mod bug: the problem is that
strncasecmp() doesn't match the HFS B-tree sort order, which in
particular breaks lookup of files with an underscore in their name. The
first attached patch fixes this using a lookup table from Linux
fs/hfs/string.c.

The failure to auto-load some modules like search was also caused by
this, the auto-loading process aborts after failing to load a module. It
might be better to continue auto-loading other modules anyway.


BTW, I also need the second attached patch to be able to boot my
self-built 32 bit kernels configured to support 2GB lowmem.
elf->ehdr.ehdr32.e_entry ends up as 0x70000000.


P.S. Please reconsider automatically rejecting posts from
non-subscribers. I co-moderate half a dozen mailing lists, only costs me
a couple of minutes a day thanks to a nice tool called 'listadmin'.

I probably won't be subscribed to this list for long, please keep me
CC'd on followups.

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

[-- Attachment #2: grub2-hfs.diff --]
[-- Type: text/x-patch, Size: 2716 bytes --]

--- grub2-1.96+20081201.orig/fs/hfs.c	2008-01-23 21:21:18.000000000 +0100
+++ grub2-1.96+20081201/fs/hfs.c	2009-01-26 15:23:08.000000000 +0100
@@ -391,6 +391,34 @@ grub_hfs_mount (grub_disk_t disk)
 }
 
 
+/*
+ * unsigned char caseorder[]
+ *
+ * Defines the lexical ordering of characters on the Macintosh
+ *
+ * Composition of the 'casefold' and 'order' tables from ARDI's code
+ * with the entry for 0x20 changed to match that for 0xCA to remove
+ * special case for those two characters.
+ */
+static unsigned char caseorder[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,0x57,0x59,0x5D,0x5F,0x66,0x68,0x6A,0x6C,0x72,0x74,0x76,0x78,0x7A,0x7E,
+	0x8C,0x8E,0x90,0x92,0x95,0x97,0x9E,0xA0,0xA2,0xA4,0xA7,0xA9,0xAA,0xAB,0xAC,0xAD,
+	0x4E,0x48,0x57,0x59,0x5D,0x5F,0x66,0x68,0x6A,0x6C,0x72,0x74,0x76,0x78,0x7A,0x7E,
+	0x8C,0x8E,0x90,0x92,0x95,0x97,0x9E,0xA0,0xA2,0xA4,0xA7,0xAF,0xB0,0xB1,0xB2,0xB3,
+	0x4A,0x4C,0x5A,0x60,0x7B,0x7F,0x98,0x4F,0x49,0x51,0x4A,0x4B,0x4C,0x5A,0x60,0x63,
+	0x64,0x65,0x6E,0x6F,0x70,0x71,0x7B,0x84,0x85,0x86,0x7F,0x80,0x9A,0x9B,0x9C,0x98,
+	0xB4,0xB5,0xB6,0xB7,0xB8,0xB9,0xBA,0x94,0xBB,0xBC,0xBD,0xBE,0xBF,0xC0,0x4D,0x81,
+	0xC1,0xC2,0xC3,0xC4,0xC5,0xC6,0xC7,0xC8,0xC9,0xCA,0xCB,0x55,0x8A,0xCC,0x4D,0x81,
+	0xCD,0xCE,0xCF,0xD0,0xD1,0xD2,0xD3,0x26,0x27,0xD4,0x20,0x49,0x4B,0x80,0x82,0x82,
+	0xD5,0xD6,0x24,0x25,0x2D,0x2E,0xD7,0xD8,0xA6,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
+};
+
 /* Compare the K1 and K2 catalog file keys.  */
 static int
 grub_hfs_cmp_catkeys (struct grub_hfs_catalog_key *k1,
@@ -398,17 +426,19 @@ grub_hfs_cmp_catkeys (struct grub_hfs_ca
 {
   int cmp = (grub_be_to_cpu32 (k1->parent_dir)
 	     - grub_be_to_cpu32 (k2->parent_dir));
+  int i;
   
   if (cmp != 0)
     return cmp;
-  
-  cmp = grub_strncasecmp ((char *) (k1->str), (char *) (k2->str), k1->strlen);
-  
-  /* This is required because the compared strings are not of equal
-     length.  */
-  if (cmp == 0 && k1->strlen < k2->strlen)
-    return -1;
-  return cmp;
+
+  for (i = 0; i < k1->strlen && i < k2->strlen; i++) {
+    cmp = caseorder[k1->str[i]] - caseorder[k2->str[i]];
+
+    if (cmp != 0)
+      return cmp;
+  }
+
+  return k1->strlen - k2->strlen;
 }
 
 

[-- Attachment #3: grub2-ELF32_LOADMASK.diff --]
[-- Type: text/x-patch, Size: 568 bytes --]

diff -up -ru grub2-1.96+20081201.orig/loader/powerpc/ieee1275/linux.c grub2-1.96+20081201/loader/powerpc/ieee1275/linux.c
--- grub2-1.96+20081201.orig/loader/powerpc/ieee1275/linux.c	2007-07-22 01:32:33.000000000 +0200
+++ grub2-1.96+20081201/loader/powerpc/ieee1275/linux.c	2009-01-24 16:14:32.000000000 +0100
@@ -27,7 +27,7 @@
 #include <grub/ieee1275/ieee1275.h>
 #include <grub/machine/loader.h>
 
-#define ELF32_LOADMASK (0xc0000000UL)
+#define ELF32_LOADMASK (0xf0000000UL)
 #define ELF64_LOADMASK (0xc000000000000000ULL)
 
 static grub_dl_t my_mod;

Re: State of GRUB on PowerPC

[Vesa Jääskeläinen]

Michel Dänzer wrote:
> P.S. Please reconsider automatically rejecting posts from
> non-subscribers. I co-moderate half a dozen mailing lists, only costs me
> a couple of minutes a day thanks to a nice tool called 'listadmin'.

grub-devel is a subscriber only list.

Re: State of GRUB on PowerPC

[Michel Dänzer]

On Tue, 2009-01-27 at 18:54 +0200, Vesa Jääskeläinen wrote:
> Michel Dänzer wrote:
> > P.S. Please reconsider automatically rejecting posts from
> > non-subscribers. I co-moderate half a dozen mailing lists, only costs me
> > a couple of minutes a day thanks to a nice tool called 'listadmin'.
> 
> grub-devel is a subscriber only list.

I know... I'm talking about manually approving legitimiate posts from
non-subscribers (and discarding spam) rather than sending them a nice
'go away' welcome message... Anyway, just a suggestion.


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

Re: State of GRUB on PowerPC

[Pavel Roskin]

On Tue, 2009-01-27 at 08:19 +0100, Michel Dänzer wrote:
> I was able to reproduce Jordi's findings on my PowerBook G4. (Well,
> except device.map seems to get generated correctly and the search
> command seems to work for me, maybe this is due to differences between
> our OF device trees or something like that)
> 
> After some printf-style debugging over the weekend, the failure to load
> some modules indeed turns out to be an hfs.mod bug: the problem is that
> strncasecmp() doesn't match the HFS B-tree sort order, which in
> particular breaks lookup of files with an underscore in their name. The
> first attached patch fixes this using a lookup table from Linux
> fs/hfs/string.c.

Actually, the return value of grub_strncasecmp() was incorrect until
recently.  Maybe the current version would work for you?

I'm not against your patch, but I'd like to understand how important it
is for GRUB.

Please write a ChangeLog entry for the patch.

> The failure to auto-load some modules like search was also caused by
> this, the auto-loading process aborts after failing to load a module. It
> might be better to continue auto-loading other modules anyway.

Patches are welcome.  With explanations, please.

> BTW, I also need the second attached patch to be able to boot my
> self-built 32 bit kernels configured to support 2GB lowmem.
> elf->ehdr.ehdr32.e_entry ends up as 0x70000000.

Strange.  The original mask should ensure that elf->ehdr.ehdr32.e_entry
is less than 0x40000000.

-- 
Regards,
Pavel Roskin

Re: State of GRUB on PowerPC

[Michel Dänzer]

On Wed, 2009-01-28 at 21:57 -0500, Pavel Roskin wrote:
> On Tue, 2009-01-27 at 08:19 +0100, Michel Dänzer wrote:
> > I was able to reproduce Jordi's findings on my PowerBook G4. (Well,
> > except device.map seems to get generated correctly and the search
> > command seems to work for me, maybe this is due to differences between
> > our OF device trees or something like that)
> > 
> > After some printf-style debugging over the weekend, the failure to load
> > some modules indeed turns out to be an hfs.mod bug: the problem is that
> > strncasecmp() doesn't match the HFS B-tree sort order, which in
> > particular breaks lookup of files with an underscore in their name. The
> > first attached patch fixes this using a lookup table from Linux
> > fs/hfs/string.c.
> 
> Actually, the return value of grub_strncasecmp() was incorrect until
> recently.  Maybe the current version would work for you?

Unfortunately not; I verified with a simple program that the glibc
strncasecmp() also has a different order between underscore and
characters. The HFS sort order seems quite peculiar.

> I'm not against your patch, but I'd like to understand how important it
> is for GRUB.

The failure to look up some files on HFS filesystems makes it hard for
most PowerPC Mac Linux users to switch from yaboot to GRUB.

> Please write a ChangeLog entry for the patch.

How about this:

2009-01-29  Michel Dänzer  <michel@daenzer.net>

        * fs/hfs.c (grub_hfs_cmp_catkeys): Use lookup table for HFS
        B-tree sort order. Otherwise we fail to look up some files,
        e.g. with an underscore in the name, so e.g. the _linux module  
        can't be loaded from an HFS filesystem.


> > The failure to auto-load some modules like search was also caused by
> > this, the auto-loading process aborts after failing to load a module. It
> > might be better to continue auto-loading other modules anyway.
> 
> Patches are welcome.  With explanations, please.

Just tossing out an idea.


> > BTW, I also need the second attached patch to be able to boot my
> > self-built 32 bit kernels configured to support 2GB lowmem.
> > elf->ehdr.ehdr32.e_entry ends up as 0x70000000.
> 
> Strange.  The original mask should ensure that elf->ehdr.ehdr32.e_entry
> is less than 0x40000000.

Right, that's the problem. :) Apparently the kernel's early boot code
relies on it remaining unchanged.


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

hfs patch (Re: State of GRUB on PowerPC)

[Robert Millan]

On Tue, Jan 27, 2009 at 08:19:41AM +0100, Michel Dänzer wrote:
> +/*
> + * unsigned char caseorder[]
> + *
> + * Defines the lexical ordering of characters on the Macintosh
> + *
> + * Composition of the 'casefold' and 'order' tables from ARDI's code
> + * with the entry for 0x20 changed to match that for 0xCA to remove
> + * special case for those two characters.
> + */
> +static unsigned char caseorder[256] = {
> +	0x00,0x01,0x02,0x03,0x04,0x05,0x06,0x07,0x08,0x09,0x0A,0x0B,0x0C,0x0D,0x0E,0x0F,

Could you be more specific about what the table contents mean?

> +  for (i = 0; i < k1->strlen && i < k2->strlen; i++) {
> +    cmp = caseorder[k1->str[i]] - caseorder[k2->str[i]];

I think "a = (b != c)" would be more efficient (and also work).

Also please add a newline before operning braces ({).

Thanks!

-- 
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."

Re: hfs patch (Re: State of GRUB on PowerPC)

[Pavel Roskin]

Quoting Robert Millan <rmh@aybabtu.com>:

> On Tue, Jan 27, 2009 at 08:19:41AM +0100, Michel Dänzer wrote:
>> +/*
>> + * unsigned char caseorder[]
>> + *
>> + * Defines the lexical ordering of characters on the Macintosh
>> + *
>> + * Composition of the 'casefold' and 'order' tables from ARDI's code
>> + * with the entry for 0x20 changed to match that for 0xCA to remove
>> + * special case for those two characters.
>> + */
>> +static unsigned char caseorder[256] = {
>> +	0x00,0x01,0x02,0x03,0x04,0x05,0x06,0x07,0x08,0x09,0x0A,0x0B,0x0C,0x0D,0x0E,0x0F,
>
> Could you be more specific about what the table contents mean?

Michel may know better, but I think it's the order of characters.   
Those with the lower order go first in the sorted binary tree.  Those  
with the same order are equivalent on the filesystem level.  That is,  
"foo" can only be between "bar" and "quux" in the node tree.  "foo"  
and "Foo" are the same tree node and thus the same file.

>> +  for (i = 0; i < k1->strlen && i < k2->strlen; i++) {
>> +    cmp = caseorder[k1->str[i]] - caseorder[k2->str[i]];
>
> I think "a = (b != c)" would be more efficient (and also work).

I don't think so.

"The function strcasecmp() returns a positive integer if, disregarding  
case, string s1 is lexically greater than string s2; zero if, other  
than case the two strings are identical; and a negative integer if,  
disregarding case, string s1 is lexically less than string s2."

-- 
Regards,
Pavel Roskin

Re: hfs patch (Re: State of GRUB on PowerPC)

[Robert Millan]

On Sat, Feb 07, 2009 at 11:38:36PM -0500, Pavel Roskin wrote:
> Quoting Robert Millan <rmh@aybabtu.com>:
> 
> >On Tue, Jan 27, 2009 at 08:19:41AM +0100, Michel Dänzer wrote:
> >>+/*
> >>+ * unsigned char caseorder[]
> >>+ *
> >>+ * Defines the lexical ordering of characters on the Macintosh
> >>+ *
> >>+ * Composition of the 'casefold' and 'order' tables from ARDI's code
> >>+ * with the entry for 0x20 changed to match that for 0xCA to remove
> >>+ * special case for those two characters.
> >>+ */
> >>+static unsigned char caseorder[256] = {
> >>+ 
> >>0x00,0x01,0x02,0x03,0x04,0x05,0x06,0x07,0x08,0x09,0x0A,0x0B,0x0C,0x0D,0x0E,0x0F,
> >
> >Could you be more specific about what the table contents mean?
> 
> Michel may know better, but I think it's the order of characters.   
> Those with the lower order go first in the sorted binary tree.  Those  
> with the same order are equivalent on the filesystem level.  That is,  
> "foo" can only be between "bar" and "quux" in the node tree.  "foo"  
> and "Foo" are the same tree node and thus the same file.

I think what we need here is enough information so that someone can understand
what the table means and be able to modify it if need arised.  An undocumented
table just looks like a "blob" of binary data.

-- 
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."

Re: hfs patch (Re: State of GRUB on PowerPC)

[Michel Dänzer]

On Mon, 2009-02-09 at 15:19 +0100, Robert Millan wrote:
> On Sat, Feb 07, 2009 at 11:38:36PM -0500, Pavel Roskin wrote:
> > Quoting Robert Millan <rmh@aybabtu.com>:
> > 
> > >On Tue, Jan 27, 2009 at 08:19:41AM +0100, Michel Dänzer wrote:
> > >>+/*
> > >>+ * unsigned char caseorder[]
> > >>+ *
> > >>+ * Defines the lexical ordering of characters on the Macintosh
> > >>+ *
> > >>+ * Composition of the 'casefold' and 'order' tables from ARDI's code
> > >>+ * with the entry for 0x20 changed to match that for 0xCA to remove
> > >>+ * special case for those two characters.
> > >>+ */
> > >>+static unsigned char caseorder[256] = {
> > >>+ 
> > >>0x00,0x01,0x02,0x03,0x04,0x05,0x06,0x07,0x08,0x09,0x0A,0x0B,0x0C,0x0D,0x0E,0x0F,
> > >
> > >Could you be more specific about what the table contents mean?
> > 
> > Michel may know better, but I think it's the order of characters.   
> > Those with the lower order go first in the sorted binary tree.  Those  
> > with the same order are equivalent on the filesystem level.  That is,  
> > "foo" can only be between "bar" and "quux" in the node tree.  "foo"  
> > and "Foo" are the same tree node and thus the same file.
> 
> I think what we need here is enough information so that someone can understand
> what the table means

I'm not sure what more information I can provide. :(

> and be able to modify it if need arised.

I think that's very unlikely: the Linux kernel code this is copied from
hasn't changed at all since Linus started using Git for 2.6.12-rc,
possibly much longer.

> An undocumented table just looks like a "blob" of binary data.

I guess to some extent it could be considered that - it's a blob which
is needed to correctly interpret the blobs in an HFS filesystem.


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

Re: hfs patch (Re: State of GRUB on PowerPC)

[Michel Dänzer]

On Sat, 2009-02-07 at 23:38 -0500, Pavel Roskin wrote:
> Quoting Robert Millan <rmh@aybabtu.com>:
> 
> > On Tue, Jan 27, 2009 at 08:19:41AM +0100, Michel Dänzer wrote:
> >> +/*
> >> + * unsigned char caseorder[]
> >> + *
> >> + * Defines the lexical ordering of characters on the Macintosh
> >> + *
> >> + * Composition of the 'casefold' and 'order' tables from ARDI's code
> >> + * with the entry for 0x20 changed to match that for 0xCA to remove
> >> + * special case for those two characters.
> >> + */
> >> +static unsigned char caseorder[256] = {
> >> +	0x00,0x01,0x02,0x03,0x04,0x05,0x06,0x07,0x08,0x09,0x0A,0x0B,0x0C,0x0D,0x0E,0x0F,
> >
> > Could you be more specific about what the table contents mean?

BTW, let me point out again that this table including comment is a
verbatim copy from the Linux kernel fs/hfs/string.c . Sorry if I didn't
make this clear enough in my original post.

> Michel may know better, but I think it's the order of characters.   
> Those with the lower order go first in the sorted binary tree.  Those  
> with the same order are equivalent on the filesystem level.  That is,  
> "foo" can only be between "bar" and "quux" in the node tree.  "foo"  
> and "Foo" are the same tree node and thus the same file.

I think that's a nice summary, thanks.


> >> +  for (i = 0; i < k1->strlen && i < k2->strlen; i++) {
> >> +    cmp = caseorder[k1->str[i]] - caseorder[k2->str[i]];
> >
> > I think "a = (b != c)" would be more efficient (and also work).
> 
> I don't think so.

Yeah, definitely not. We have to use the same sort order as the HFS
on-disk trees, or we are unable to look up some files.


Below is a new patch with the opening { moved after newlines and the
ChangeLog entry included.


--- grub2-1.96+20081201.orig/ChangeLog	2008-11-29 22:05:59.000000000 +0100
+++ grub2-1.96+20081201/ChangeLog	2009-02-09 16:59:30.000000000 +0100
@@ -0,0 +1,7 @@
+2009-01-29  Michel Dänzer  <michel@daenzer.net>
+
+        * fs/hfs.c (grub_hfs_cmp_catkeys): Use lookup table for HFS
+        B-tree sort order. Otherwise we fail to look up some files,
+        e.g. with an underscore in the name, so e.g. the _linux module  
+        can't be loaded from an HFS filesystem.
+
--- grub2-1.96+20081201.orig/fs/hfs.c	2008-01-23 21:21:18.000000000 +0100
+++ grub2-1.96+20081201/fs/hfs.c	2009-02-09 17:06:35.000000000 +0100
@@ -391,6 +391,35 @@ grub_hfs_mount (grub_disk_t disk)
 }
 
 
+/*
+ * unsigned char caseorder[]
+ *
+ * Defines the lexical ordering of characters on the Macintosh
+ *
+ * Composition of the 'casefold' and 'order' tables from ARDI's code
+ * with the entry for 0x20 changed to match that for 0xCA to remove
+ * special case for those two characters.
+ */
+static unsigned char caseorder[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,0x57,0x59,0x5D,0x5F,0x66,0x68,0x6A,0x6C,0x72,0x74,0x76,0x78,0x7A,0x7E,
+	0x8C,0x8E,0x90,0x92,0x95,0x97,0x9E,0xA0,0xA2,0xA4,0xA7,0xA9,0xAA,0xAB,0xAC,0xAD,
+	0x4E,0x48,0x57,0x59,0x5D,0x5F,0x66,0x68,0x6A,0x6C,0x72,0x74,0x76,0x78,0x7A,0x7E,
+	0x8C,0x8E,0x90,0x92,0x95,0x97,0x9E,0xA0,0xA2,0xA4,0xA7,0xAF,0xB0,0xB1,0xB2,0xB3,
+	0x4A,0x4C,0x5A,0x60,0x7B,0x7F,0x98,0x4F,0x49,0x51,0x4A,0x4B,0x4C,0x5A,0x60,0x63,
+	0x64,0x65,0x6E,0x6F,0x70,0x71,0x7B,0x84,0x85,0x86,0x7F,0x80,0x9A,0x9B,0x9C,0x98,
+	0xB4,0xB5,0xB6,0xB7,0xB8,0xB9,0xBA,0x94,0xBB,0xBC,0xBD,0xBE,0xBF,0xC0,0x4D,0x81,
+	0xC1,0xC2,0xC3,0xC4,0xC5,0xC6,0xC7,0xC8,0xC9,0xCA,0xCB,0x55,0x8A,0xCC,0x4D,0x81,
+	0xCD,0xCE,0xCF,0xD0,0xD1,0xD2,0xD3,0x26,0x27,0xD4,0x20,0x49,0x4B,0x80,0x82,0x82,
+	0xD5,0xD6,0x24,0x25,0x2D,0x2E,0xD7,0xD8,0xA6,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
+};
+
 /* Compare the K1 and K2 catalog file keys.  */
 static int
 grub_hfs_cmp_catkeys (struct grub_hfs_catalog_key *k1,
@@ -398,17 +427,20 @@ grub_hfs_cmp_catkeys (struct grub_hfs_ca
 {
   int cmp = (grub_be_to_cpu32 (k1->parent_dir)
 	     - grub_be_to_cpu32 (k2->parent_dir));
+  int i;
   
   if (cmp != 0)
     return cmp;
-  
-  cmp = grub_strncasecmp ((char *) (k1->str), (char *) (k2->str), k1->strlen);
-  
-  /* This is required because the compared strings are not of equal
-     length.  */
-  if (cmp == 0 && k1->strlen < k2->strlen)
-    return -1;
-  return cmp;
+
+  for (i = 0; i < k1->strlen && i < k2->strlen; i++)
+  {
+    cmp = caseorder[k1->str[i]] - caseorder[k2->str[i]];
+
+    if (cmp != 0)
+      return cmp;
+  }
+
+  return k1->strlen - k2->strlen;
 }
 
 


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

Re: hfs patch (Re: State of GRUB on PowerPC)

[Jordi Mallach]

On Tue, Feb 10, 2009 at 10:54:55AM +0100, Michel Dänzer wrote:
> > > Could you be more specific about what the table contents mean?
> BTW, let me point out again that this table including comment is a
> verbatim copy from the Linux kernel fs/hfs/string.c . Sorry if I didn't
> make this clear enough in my original post.

Ugh, welcome our GPLv3 party. v2 members not invited. :/

Thanks for working on this, Michel!

-- 
Jordi Mallach Pérez  --  Debian developer     http://www.debian.org/
jordi@sindominio.net     jordi@debian.org     http://www.sindominio.net/
GnuPG public key information available at http://oskuro.net/

Re: hfs patch (Re: State of GRUB on PowerPC)

[Jordi Mallach]

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

On Tue, Feb 10, 2009 at 11:50:18AM +0100, Jordi Mallach wrote:
> > BTW, let me point out again that this table including comment is a
> > verbatim copy from the Linux kernel fs/hfs/string.c . Sorry if I didn't
> > make this clear enough in my original post.
> Ugh, welcome our GPLv3 party. v2 members not invited. :/
> Thanks for working on this, Michel!

Aparently hfsutils is GPLv2+ and might have a similar blob that we
can use.

-- 
Jordi Mallach Pérez  --  Debian developer     http://www.debian.org/
jordi@sindominio.net     jordi@debian.org     http://www.sindominio.net/
GnuPG public key information available at http://oskuro.net/

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 197 bytes --]

Re: hfs patch (Re: State of GRUB on PowerPC)

[Michel Dänzer]

On Tue, 2009-02-10 at 13:06 +0100, Jordi Mallach wrote:
> On Tue, Feb 10, 2009 at 11:50:18AM +0100, Jordi Mallach wrote:
> > > BTW, let me point out again that this table including comment is a
> > > verbatim copy from the Linux kernel fs/hfs/string.c . Sorry if I didn't
> > > make this clear enough in my original post.
> > Ugh, welcome our GPLv3 party. v2 members not invited. :/
> > Thanks for working on this, Michel!
> 
> Aparently hfsutils is GPLv2+ and might have a similar blob that we
> can use.

Right. Anyway, I think it should be clear now what the problem is and
how it can be fixed; I've already spent more time on this than I was
planning and will now unsubscribe from this list again.


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

Re: hfs patch (Re: State of GRUB on PowerPC)

[Robert Millan]

On Tue, Feb 10, 2009 at 11:50:18AM +0100, Jordi Mallach wrote:
> On Tue, Feb 10, 2009 at 10:54:55AM +0100, Michel Dänzer wrote:
> > > > Could you be more specific about what the table contents mean?
> > BTW, let me point out again that this table including comment is a
> > verbatim copy from the Linux kernel fs/hfs/string.c . Sorry if I didn't
> > make this clear enough in my original post.
> 
> Ugh, welcome our GPLv3 party. v2 members not invited. :/

Just to make it clear: I haven't said there's a problem with license
compatibility.  There *might* be, depending on the exact meaning of those
bytes, but it's unlikely.

-- 
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."

Re: hfs patch (Re: State of GRUB on PowerPC)

[Robert Millan]

On Tue, Feb 10, 2009 at 10:54:55AM +0100, Michel Dänzer wrote:
> > >> +static unsigned char caseorder[256] = {
> > >> +	0x00,0x01,0x02,0x03,0x04,0x05,0x06,0x07,0x08,0x09,0x0A,0x0B,0x0C,0x0D,0x0E,0x0F,
> > >
> > > Could you be more specific about what the table contents mean?
> 
> BTW, let me point out again that this table including comment is a
> verbatim copy from the Linux kernel fs/hfs/string.c . Sorry if I didn't
> make this clear enough in my original post.

Since it's probably not copyright-significant, it may not be a problem to
copy it from Linux sources.  However, it's also possible for a list of
numbers to be copyright significant, depending on their meaning (which
is linked to my other question below).

> > Michel may know better, but I think it's the order of characters.   
> > Those with the lower order go first in the sorted binary tree.  Those  
> > with the same order are equivalent on the filesystem level.  That is,  
> > "foo" can only be between "bar" and "quux" in the node tree.  "foo"  
> > and "Foo" are the same tree node and thus the same file.
> 
> I think that's a nice summary, thanks.

Ok. There's a pair of things that need to be cleaned up though.  If I
understand correctly, the definition of caseorder[i] is such that given too
distinct values of i, it can be used to sort them (if this is so, I think
it should be explicitly mentioned in the comment).

So if the table is basicaly storing values that enumerate something, why are
we using hex to represent them?  Hex gives the impression they're an opaque
sort of thing, like code, bitmasks or magic numbers.

The reference to "the Macintosh" is a bit confusing, it usually means a
computer, or an OS.  I assume it refers to HFS?

We'd also need to know what are these "'casefold' and 'order' tables from
ARDI's code", and what exactly means this is a "composition" of them.

-- 
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."

Re: hfs patch (Re: State of GRUB on PowerPC)

[Michel Dänzer]

On Tue, 2009-02-10 at 15:47 +0100, Robert Millan wrote:
> On Tue, Feb 10, 2009 at 10:54:55AM +0100, Michel Dänzer wrote:
> 
> > > Michel may know better, but I think it's the order of characters.   
> > > Those with the lower order go first in the sorted binary tree.  Those  
> > > with the same order are equivalent on the filesystem level.  That is,  
> > > "foo" can only be between "bar" and "quux" in the node tree.  "foo"  
> > > and "Foo" are the same tree node and thus the same file.
> > 
> > I think that's a nice summary, thanks.
> 
> Ok. There's a pair of things that need to be cleaned up though.  If I
> understand correctly, the definition of caseorder[i] is such that given too
> distinct values of i, it can be used to sort them (if this is so, I think
> it should be explicitly mentioned in the comment).

Yes, for a given filename character value i, caseorder[i] is the
corresponding B-tree sort order.

> So if the table is basicaly storing values that enumerate something, why are
> we using hex to represent them?  Hex gives the impression they're an opaque
> sort of thing, like code, bitmasks or magic numbers.

Your guess is as good as mine.

> The reference to "the Macintosh" is a bit confusing, it usually means a
> computer, or an OS.  I assume it refers to HFS?

Yes. I think HFS used to be 'the Macintosh filesystem' before OS X.

> We'd also need to know what are these "'casefold' and 'order' tables from
> ARDI's code", and what exactly means this is a "composition" of them.

Your guess is as good as mine.


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

Re: hfs patch (Re: State of GRUB on PowerPC)

[Robert Millan]

On Wed, Feb 11, 2009 at 10:24:57AM +0100, Michel Dänzer wrote:
> > So if the table is basicaly storing values that enumerate something, why are
> > we using hex to represent them?  Hex gives the impression they're an opaque
> > sort of thing, like code, bitmasks or magic numbers.
> 
> Your guess is as good as mine.
> [...]
> 
> > We'd also need to know what are these "'casefold' and 'order' tables from
> > ARDI's code", and what exactly means this is a "composition" of them.
> 
> Your guess is as good as mine.

My impression so far is that this is a confusing mess (which can probably
be fixed with a little effort), that this situation doesn't bother you at
all, and that you want to make it clear to us how all of this is irrelevant
to you.

-- 
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."