Re: hfs patch (Re: State of GRUB on PowerPC)
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." ___ Grub-devel mailing list [email protected] http://lists.gnu.org/mailman/listinfo/grub-devel
Re: hfs patch (Re: State of GRUB on PowerPC)
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." ___ Grub-devel mailing list [email protected] http://lists.gnu.org/mailman/listinfo/grub-devel
Re: hfs patch (Re: State of GRUB on PowerPC)
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 ___ Grub-devel mailing list [email protected] http://lists.gnu.org/mailman/listinfo/grub-devel
Re: hfs patch (Re: State of GRUB on PowerPC)
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."
___
Grub-devel mailing list
[email protected]
http://lists.gnu.org/mailman/listinfo/grub-devel
Re: hfs patch (Re: State of GRUB on PowerPC)
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 ___ Grub-devel mailing list [email protected] http://lists.gnu.org/mailman/listinfo/grub-devel
Re: hfs patch (Re: State of GRUB on PowerPC)
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/ [email protected] [email protected] http://www.sindominio.net/ GnuPG public key information available at http://oskuro.net/ signature.asc Description: Digital signature ___ Grub-devel mailing list [email protected] http://lists.gnu.org/mailman/listinfo/grub-devel
Re: hfs patch (Re: State of GRUB on PowerPC)
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/ [email protected] [email protected] http://www.sindominio.net/ GnuPG public key information available at http://oskuro.net/ ___ Grub-devel mailing list [email protected] http://lists.gnu.org/mailman/listinfo/grub-devel
Re: hfs patch (Re: State of GRUB on PowerPC)
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 :
> >
> > >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
___
Grub-devel mailing list
[email protected]
http://lists.gnu.org/mailman/listinfo/grub-devel
Re: hfs patch (Re: State of GRUB on PowerPC)
On Sat, 2009-02-07 at 23:38 -0500, Pavel Roskin wrote:
> Quoting 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?
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.0 +0100
+++ grub2-1.96+20081201/ChangeLog 2009-02-09 16:59:30.0 +0100
@@ -0,0 +1,7 @@
+2009-01-29 Michel Dänzer
+
+* 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.0 +0100
+++ grub2-1.96+20081201/fs/hfs.c2009-02-09 17:06:35.0 +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
Re: hfs patch (Re: State of GRUB on PowerPC)
On Sat, Feb 07, 2009 at 11:38:36PM -0500, Pavel Roskin wrote:
> Quoting 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?
>
> 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."
___
Grub-devel mailing list
[email protected]
http://lists.gnu.org/mailman/listinfo/grub-devel
Re: hfs patch (Re: State of GRUB on PowerPC)
Quoting 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?
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
___
Grub-devel mailing list
[email protected]
http://lists.gnu.org/mailman/listinfo/grub-devel
