Why count the hash value in this way?

Why count the hash value in this way?

[lx]

hi all:
      In the function of link_path_walk() , it counts the hash value of the
compoent of the pathname.
Why "(prevhash + (c <<4) + (c >> 4))*11;"?

Thank you.



http://lxr.oss.org.cn/source/fs/namei.c?v=2.6.16#L779

809 <http://lxr.oss.org.cn/source/fs/namei.c?v=2.6.16#L809>
     c <http://lxr.oss.org.cn/ident?v=2.6.16;i=c> = *(const unsigned
char *)name <http://lxr.oss.org.cn/ident?v=2.6.16;i=name>;810
<http://lxr.oss.org.cn/source/fs/namei.c?v=2.6.16#L810> 811
<http://lxr.oss.org.cn/source/fs/namei.c?v=2.6.16#L811>
 hash <http://lxr.oss.org.cn/ident?v=2.6.16;i=hash> = init_name_hash
<http://lxr.oss.org.cn/ident?v=2.6.16;i=init_name_hash>();812
<http://lxr.oss.org.cn/source/fs/namei.c?v=2.6.16#L812>
 do {813 <http://lxr.oss.org.cn/source/fs/namei.c?v=2.6.16#L813>
                  name
<http://lxr.oss.org.cn/ident?v=2.6.16;i=name>++;814
<http://lxr.oss.org.cn/source/fs/namei.c?v=2.6.16#L814>
         hash <http://lxr.oss.org.cn/ident?v=2.6.16;i=hash> =
partial_name_hash
<http://lxr.oss.org.cn/ident?v=2.6.16;i=partial_name_hash>(c
<http://lxr.oss.org.cn/ident?v=2.6.16;i=c>, hash
<http://lxr.oss.org.cn/ident?v=2.6.16;i=hash>);815
<http://lxr.oss.org.cn/source/fs/namei.c?v=2.6.16#L815>
         c <http://lxr.oss.org.cn/ident?v=2.6.16;i=c> = *(const
unsigned char *)name <http://lxr.oss.org.cn/ident?v=2.6.16;i=name>;816
<http://lxr.oss.org.cn/source/fs/namei.c?v=2.6.16#L816>
 } while (c <http://lxr.oss.org.cn/ident?v=2.6.16;i=c> && (c
<http://lxr.oss.org.cn/ident?v=2.6.16;i=c> != *'/'*));817
<http://lxr.oss.org.cn/source/fs/namei.c?v=2.6.16#L817>
 this.len <http://lxr.oss.org.cn/ident?v=2.6.16;i=len> = name
<http://lxr.oss.org.cn/ident?v=2.6.16;i=name> - (const char *)
this.name <http://lxr.oss.org.cn/ident?v=2.6.16;i=name>;


*/* Name hashing routines. Initial hash value */*
 49 <http://lxr.oss.org.cn/source/include/linux/dcache.h?v=2.6.16#L49>
*/* Hash courtesy of the R5 hash in reiserfs modulo sign bits */*
 50 <http://lxr.oss.org.cn/source/include/linux/dcache.h?v=2.6.16#L50>
#define init_name_hash
<http://lxr.oss.org.cn/ident?v=2.6.16;i=init_name_hash>()
  0
 51 <http://lxr.oss.org.cn/source/include/linux/dcache.h?v=2.6.16#L51>
 52 <http://lxr.oss.org.cn/source/include/linux/dcache.h?v=2.6.16#L52>
*/* partial hash update function. Assume roughly 4 bits per character
*/*
 53 <http://lxr.oss.org.cn/source/include/linux/dcache.h?v=2.6.16#L53>
static inline unsigned long
 54 <http://lxr.oss.org.cn/source/include/linux/dcache.h?v=2.6.16#L54>
partial_name_hash
<http://lxr.oss.org.cn/ident?v=2.6.16;i=partial_name_hash>(unsigned
long c <http://lxr.oss.org.cn/ident?v=2.6.16;i=c>, unsigned long
prevhash)
 55 <http://lxr.oss.org.cn/source/include/linux/dcache.h?v=2.6.16#L55> {
 56 <http://lxr.oss.org.cn/source/include/linux/dcache.h?v=2.6.16#L56>
        return (prevhash + (c
<http://lxr.oss.org.cn/ident?v=2.6.16;i=c> << 4) + (c
<http://lxr.oss.org.cn/ident?v=2.6.16;i=c> >> 4)) * 11;
 57 <http://lxr.oss.org.cn/source/include/linux/dcache.h?v=2.6.16#L57> }
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.kernelnewbies.org/pipermail/kernelnewbies/attachments/20130804/93ca839e/attachment-0001.html 

Why count the hash value in this way?

[Jonathan Neuschäfer]

On Sun, Aug 04, 2013 at 05:38:55PM +0800, lx wrote:
> hi all:
>       In the function of link_path_walk() , it counts the hash value of the
> compoent of the pathname.
> Why "(prevhash + (c <<4) + (c >> 4))*11;"?


In the code you quoted it says:

  /* Hash courtesy of the R5 hash in reiserfs modulo sign bits */

A bit of googling led me to this[1] page, where it says:

     r5 - This hash is a modified version of rupasov hash. It is used by
     default and it is better to stick here until you have to support
     huge directories and unusual file-name patterns.

and:

     rupasov - This hash is invented by Yury Yu. Rupasov. It is fast and
     preserves locality, mapping lexicographically close file names to
     the close hash values. Never use it, as it has a high probability
     of hash collisions.

[1] https://reiser4.wiki.kernel.org/index.php/Mount


Reading the ReiserFS code and/or mailing lists might give you a clue
about how the R5 hash was designed.


HTH,
Jonathan Neusch?fer