Re: [PATCH] reiserfscore/hashes.c

Re: [PATCH] reiserfscore/hashes.c

[Edward Shishkin]

On 11/06/2012 04:49 PM, Michael W. Bombardieri wrote:
> Hi Edward,
>
> I was browsing the git repository for reiserfs...
> https://git.kernel.org/?p=linux/kernel/git/jeffm/reiserfsprogs.git;a=summary
> This code is entirely new to me.
>
> I have a patch which simplifies the yura_hash function in
> reiserfscore/hashes.c. Here is what it does:
>
> 1. Remove temporary variable 'c'
> 2. Remove two nested loops which always set pow=1
>
> I tested this using the following code on i386 and amd64.
>
> int
> main(void)
> {
>      char *test[] = {
>          "a",
>          "bb",
>          "ccc",
>          "dddd",
>          "eeeee",
>          "ffffff",
>          "ggggggg",
>          "red leather",
>          "yellow leather",
>          NULL
>      };
>      size_t n;
>      int i;
>      u32 x;
>
>      for (i = 0; test[i] != NULL; i++) {
>          n = strlen(test[i]);
>          printf("input=\"%s\" len=%u ", test[i], n);
>          x = yura_hash(test[i], (int)n);
>          printf("hash=%lu\n", x);
>      }
>      return (0);
> }
>
> The results between my version and the original
> yura_hash are identical:
>
> input="a" len=1 hash=4084352
> input="bb" len=2 hash=4148480
> input="ccc" len=3 hash=4802688
> input="dddd" len=4 hash=11472896
> input="eeeee" len=5 hash=79455104
> input="ffffff" len=6 hash=772077312
> input="ggggggg" len=7 hash=3531332224
> input="red leather" len=11 hash=959593472
> input="yellow leather" len=14 hash=410631168
>
> I'm not sure if the yura_hash function is used
> heavily, or at all. I'm sending this patch in
> case you are interested to take a look.


Hello Michael,

Your changes look OK to me.

TBH, I don't like the fact that the pow is set to 1 by such tricky ways in
the mentioned nested loops: it might indicate mistakes in the original
code.

Generally I think that this hash is not heavily used: everyone uses either
r5, or tea hash, so...
A—Åked-by: Edward Shishkin <edward.shishkin@gmail.com>

Thanks,
Edward.
P.S. This is a git repository of Jeff Mahoney, the reiserfs maintainer, so
don't forget cc him ;)



> - Michael
>
>
> --- hashes.c	Tue Nov  6 23:21:09 2012
> +++ hashes_new.c	Tue Nov  6 23:26:26 2012
> @@ -175,37 +175,26 @@
>   
>   u32 yura_hash (const signed char *msg, int len)
>   {
> -    int j, pow;
> -    u32 a, c;
> -    int i;
> -
> -    for (pow=1,i=1; i < len; i++) pow = pow * 10;
> -
> -    if (len == 1)
> -	a = msg[0]-48;
> -    else
> -	a = (msg[0] - 48) * pow;
> -
> -    for (i=1; i < len; i++) {
> -	c = msg[i] - 48;
> -	for (pow=1,j=i; j < len-1; j++) pow = pow * 10;
> -	a = a + c * pow;
> -    }
> -
> -    for (; i < 40; i++) {
> -	c = '0' - 48;
> -	for (pow=1,j=i; j < len-1; j++) pow = pow * 10;
> -	a = a + c * pow;
> -    }
> -
> -    for (; i < 256; i++) {
> -	c = i;
> -	for (pow=1,j=i; j < len-1; j++) pow = pow * 10;
> -	a = a + c * pow;
> -    }
> -
> -    a = a << 7;
> -    return a;
> +	int i, j, pow;
> +	u32 a;
> +
> +	a = msg[0] - 48;
> +	if (len != 1) {
> +		for (i = 1, pow = 1; i < len; i++)
> +			pow *= 10;
> +		a *= pow;
> +	}
> +	for (i = 1; i < len; i++) {
> +		for (j = i, pow = 1; j < len - 1; j++)
> +			pow *= 10;
> +		a += pow * (msg[i] - 48);
> +	}
> +	for (; i < 40; i++)
> +		a += '0' - 48;
> +	for (; i < 256; i++)
> +		a += i;
> +	a <<= 7;
> +	return a;
>   }
>   
>   

--
To unsubscribe from this list: send the line "unsubscribe reiserfs-devel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: [PATCH] reiserfscore/hashes.c

[Michael W. Bombardieri]

On Tue, Nov 06, 2012 at 08:47:27PM +0100, Edward Shishkin wrote:
> Hello Michael,
> 
> Your changes look OK to me.
> 
> TBH, I don't like the fact that the pow is set to 1 by such tricky ways in
> the mentioned nested loops: it might indicate mistakes in the original
> code.

I agree. Something doesn't look right about the nested loops
not being entered. This could well point to the code being
incorrect. IMHO, the developer would not bother adding the
loops if he didn't want them to be used.

> Generally I think that this hash is not heavily used: everyone uses either
> r5, or tea hash, so...

I suppose this would raise the question, is it worth patching
yura_hash() or is it better to scrap the function altogether
if the two other hash functions are sufficient?

> A??ked-by: Edward Shishkin <edward.shishkin@gmail.com>
> 
> Thanks,
> Edward.
> P.S. This is a git repository of Jeff Mahoney, the reiserfs maintainer, so
> don't forget cc him ;)
> 
> 
> 
> >- Michael
> >
> >
> >--- hashes.c	Tue Nov  6 23:21:09 2012
> >+++ hashes_new.c	Tue Nov  6 23:26:26 2012
> >@@ -175,37 +175,26 @@
> >  u32 yura_hash (const signed char *msg, int len)
> >  {
> >-    int j, pow;
> >-    u32 a, c;
> >-    int i;
> >-
> >-    for (pow=1,i=1; i < len; i++) pow = pow * 10;
> >-
> >-    if (len == 1)
> >-	a = msg[0]-48;
> >-    else
> >-	a = (msg[0] - 48) * pow;
> >-
> >-    for (i=1; i < len; i++) {
> >-	c = msg[i] - 48;
> >-	for (pow=1,j=i; j < len-1; j++) pow = pow * 10;
> >-	a = a + c * pow;
> >-    }
> >-
> >-    for (; i < 40; i++) {
> >-	c = '0' - 48;
> >-	for (pow=1,j=i; j < len-1; j++) pow = pow * 10;
> >-	a = a + c * pow;
> >-    }
> >-
> >-    for (; i < 256; i++) {
> >-	c = i;
> >-	for (pow=1,j=i; j < len-1; j++) pow = pow * 10;
> >-	a = a + c * pow;
> >-    }
> >-
> >-    a = a << 7;
> >-    return a;
> >+	int i, j, pow;
> >+	u32 a;
> >+
> >+	a = msg[0] - 48;
> >+	if (len != 1) {
> >+		for (i = 1, pow = 1; i < len; i++)
> >+			pow *= 10;
> >+		a *= pow;
> >+	}
> >+	for (i = 1; i < len; i++) {
> >+		for (j = i, pow = 1; j < len - 1; j++)
> >+			pow *= 10;
> >+		a += pow * (msg[i] - 48);
> >+	}
> >+	for (; i < 40; i++)
> >+		a += '0' - 48;
> >+	for (; i < 256; i++)
> >+		a += i;
> >+	a <<= 7;
> >+	return a;
> >  }
> 

Re: [PATCH] reiserfscore/hashes.c

[Edward Shishkin]

On 11/07/2012 01:37 AM, Michael W. Bombardieri wrote:
> On Tue, Nov 06, 2012 at 08:47:27PM +0100, Edward Shishkin wrote:
>> Hello Michael,
>>
>> Your changes look OK to me.
>>
>> TBH, I don't like the fact that the pow is set to 1 by such tricky ways in
>> the mentioned nested loops: it might indicate mistakes in the original
>> code.
> I agree. Something doesn't look right about the nested loops
> not being entered. This could well point to the code being
> incorrect. IMHO, the developer would not bother adding the
> loops if he didn't want them to be used.
>
>> Generally I think that this hash is not heavily used: everyone uses either
>> r5, or tea hash, so...
> I suppose this would raise the question, is it worth patching
> yura_hash() or is it better to scrap the function altogether
> if the two other hash functions are sufficient?


We can not scrap this, as it will break backward compatibility:
a number of people must be use it. We can only recommend,
or not recommend something..

I suggest to patch this, so it will be clear what is going on here.
You might want also to prepare similar patch for the kernel and
send it to Jeff.

Thanks,
Edward.


>
>> A??ked-by: Edward Shishkin <edward.shishkin@gmail.com>
>>
>> Thanks,
>> Edward.
>> P.S. This is a git repository of Jeff Mahoney, the reiserfs maintainer, so
>> don't forget cc him ;)
>>
>>
>>
>>> - Michael
>>>
>>>
>>> --- hashes.c	Tue Nov  6 23:21:09 2012
>>> +++ hashes_new.c	Tue Nov  6 23:26:26 2012
>>> @@ -175,37 +175,26 @@
>>>   u32 yura_hash (const signed char *msg, int len)
>>>   {
>>> -    int j, pow;
>>> -    u32 a, c;
>>> -    int i;
>>> -
>>> -    for (pow=1,i=1; i < len; i++) pow = pow * 10;
>>> -
>>> -    if (len == 1)
>>> -	a = msg[0]-48;
>>> -    else
>>> -	a = (msg[0] - 48) * pow;
>>> -
>>> -    for (i=1; i < len; i++) {
>>> -	c = msg[i] - 48;
>>> -	for (pow=1,j=i; j < len-1; j++) pow = pow * 10;
>>> -	a = a + c * pow;
>>> -    }
>>> -
>>> -    for (; i < 40; i++) {
>>> -	c = '0' - 48;
>>> -	for (pow=1,j=i; j < len-1; j++) pow = pow * 10;
>>> -	a = a + c * pow;
>>> -    }
>>> -
>>> -    for (; i < 256; i++) {
>>> -	c = i;
>>> -	for (pow=1,j=i; j < len-1; j++) pow = pow * 10;
>>> -	a = a + c * pow;
>>> -    }
>>> -
>>> -    a = a << 7;
>>> -    return a;
>>> +	int i, j, pow;
>>> +	u32 a;
>>> +
>>> +	a = msg[0] - 48;
>>> +	if (len != 1) {
>>> +		for (i = 1, pow = 1; i < len; i++)
>>> +			pow *= 10;
>>> +		a *= pow;
>>> +	}
>>> +	for (i = 1; i < len; i++) {
>>> +		for (j = i, pow = 1; j < len - 1; j++)
>>> +			pow *= 10;
>>> +		a += pow * (msg[i] - 48);
>>> +	}
>>> +	for (; i < 40; i++)
>>> +		a += '0' - 48;
>>> +	for (; i < 256; i++)
>>> +		a += i;
>>> +	a <<= 7;
>>> +	return a;
>>>   }

Re: [PATCH] reiserfscore/hashes.c

[Jeff Mahoney]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain; charset="windows-1252", Size: 4990 bytes --]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On 11/6/12 2:47 PM, Edward Shishkin wrote:
> On 11/06/2012 04:49 PM, Michael W. Bombardieri wrote:
>> Hi Edward,
>> 
>> I was browsing the git repository for reiserfs... 
>> https://git.kernel.org/?p=linux/kernel/git/jeffm/reiserfsprogs.git;a=summary
>>
>>
>> 
This code is entirely new to me.
>> 
>> I have a patch which simplifies the yura_hash function in 
>> reiserfscore/hashes.c. Here is what it does:

Hi Michael -

Can you send the patch directly to me (or the list) so I can just git
am it? It should have a subject like [PATCH] reiserfscore: clarify
yura_hash or something.

- -Jeff

>> 1. Remove temporary variable 'c' 2. Remove two nested loops which
>> always set pow=1
>> 
>> I tested this using the following code on i386 and amd64.
>> 
>> int main(void) { char *test[] = { "a", "bb", "ccc", "dddd", 
>> "eeeee", "ffffff", "ggggggg", "red leather", "yellow leather", 
>> NULL }; size_t n; int i; u32 x;
>> 
>> for (i = 0; test[i] != NULL; i++) { n = strlen(test[i]); 
>> printf("input=\"%s\" len=%u ", test[i], n); x =
>> yura_hash(test[i], (int)n); printf("hash=%lu\n", x); } return
>> (0); }
>> 
>> The results between my version and the original yura_hash are
>> identical:
>> 
>> input="a" len=1 hash=4084352 input="bb" len=2 hash=4148480 
>> input="ccc" len=3 hash=4802688 input="dddd" len=4 hash=11472896 
>> input="eeeee" len=5 hash=79455104 input="ffffff" len=6
>> hash=772077312 input="ggggggg" len=7 hash=3531332224 input="red
>> leather" len=11 hash=959593472 input="yellow leather" len=14
>> hash=410631168
>> 
>> I'm not sure if the yura_hash function is used heavily, or at
>> all. I'm sending this patch in case you are interested to take a
>> look.
> 
> 
> Hello Michael,
> 
> Your changes look OK to me.
> 
> TBH, I don't like the fact that the pow is set to 1 by such tricky
> ways in the mentioned nested loops: it might indicate mistakes in
> the original code.
> 
> Generally I think that this hash is not heavily used: everyone uses
> either r5, or tea hash, so... Aсked-by: Edward Shishkin
> <edward.shishkin@gmail.com>
> 
> Thanks, Edward. P.S. This is a git repository of Jeff Mahoney, the
> reiserfs maintainer, so don't forget cc him ;)
> 
> 
> 
>> - Michael
>> 
>> 
>> --- hashes.c    Tue Nov  6 23:21:09 2012 +++ hashes_new.c    Tue
>> Nov  6 23:26:26 2012 @@ -175,37 +175,26 @@ u32 yura_hash (const
>> signed char *msg, int len) { -    int j, pow; -    u32 a, c; -
>> int i; - -    for (pow=1,i=1; i < len; i++) pow = pow * 10; - -
>> if (len == 1) -    a = msg[0]-48; -    else -    a = (msg[0] -
>> 48) * pow; - -    for (i=1; i < len; i++) { -    c = msg[i] -
>> 48; -    for (pow=1,j=i; j < len-1; j++) pow = pow * 10; -    a =
>> a + c * pow; -    } - -    for (; i < 40; i++) { -    c = '0' -
>> 48; -    for (pow=1,j=i; j < len-1; j++) pow = pow * 10; -    a =
>> a + c * pow; -    } - -    for (; i < 256; i++) { -    c = i; -
>> for (pow=1,j=i; j < len-1; j++) pow = pow * 10; -    a = a + c *
>> pow; -    } - -    a = a << 7; -    return a; +    int i, j,
>> pow; +    u32 a; + +    a = msg[0] - 48; +    if (len != 1) { +
>> for (i = 1, pow = 1; i < len; i++) +            pow *= 10; +
>> a *= pow; +    } +    for (i = 1; i < len; i++) { +        for (j
>> = i, pow = 1; j < len - 1; j++) +            pow *= 10; +
>> a += pow * (msg[i] - 48); +    } +    for (; i < 40; i++) +
>> a += '0' - 48; +    for (; i < 256; i++) +        a += i; +    a
>> <<= 7; +    return a; }
>> 
> 
> -- To unsubscribe from this list: send the line "unsubscribe 
> reiserfs-devel" in the body of a message to
> majordomo@vger.kernel.org More majordomo info at
> http://vger.kernel.org/majordomo-info.html


- -- 
Jeff Mahoney
SUSE Labs
-----BEGIN PGP SIGNATURE-----
Version: GnuPG/MacGPG2 v2.0.18 (Darwin)
Comment: GPGTools - http://gpgtools.org
Comment: Using GnuPG with Mozilla - http://www.enigmail.net/

iQIcBAEBAgAGBQJQpCtsAAoJEB57S2MheeWyonwP/iFfh06TBivRigIsKui1lEsR
Qu440GPB96WBr6TGSCcEgRb9GirVy0yPx/lNTmpyi2m27hn2RivMEgy6r8uVx+4K
S7+FRaZ7ysKhmrcX44KBsoIvvDqKIFaOpaTpGWlPK5kfYnRZJ47y0hSWyQgL1C2x
Bx2iiGo06wvUIv/tCSKcL95+wWHBYHbd7ouxZ3zZU4orrP40rtxjSxNJoa3PUrhE
gNUZfnksQjlYWu5voNbbyR2RXfx5DCZrbag/Wjkr0/VaFv+SDi1vWKaFuYHA4K60
VfsJdJ08xqkPRczCNE+KrqhobDM6hDDisnSek1fWQF3nOLnrF+Gz6FsvhZ2WKkrj
sLHP304B+Apcx1S8+exaq58Yap0k24WwCQ8brT6CobgSBcwNph0OhC7FdHVnmvtg
0VqGc6KVQMcWw6x7ktuXpN5zm7RilFDzdSCL2Np/a0ohsVKYB+LACmeMn01rOjrt
hMZ44Ac+b0WdomwCVvp38f7P2TBLckpglWwyUVwaK0fcPi0Tv5bznKC4wXYiMIVu
uuoDxHBLt1AFUoQB3ND4/PfCHHzThJreVpROd3U50lgJBkIRm6+E5PSUKyixZOjO
DRGqhaSHV8Hf4vs3x9I3VSQog94cBTwscg/cnCQZZ4KBNVSffA8DdC4f5AkSazZg
TZPsbMbSPKhaIICEmoJ7
=p/We
-----END PGP SIGNATURE-----
--
To unsubscribe from this list: send the line "unsubscribe reiserfs-devel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html