Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c > #70649 > unrolled thread

Re: What's the best hashing function?

Back to article view | Back to comp.lang.c

This discussion starts older than the indexed window; earlier articles aren't shown. The article labeled Started by below is the oldest one visible, not the original post.

Contents

  Re: What's the best hashing function? fir <profesor.fir@gmail.com> - 2015-09-16 09:35 -0700
    Re: What's the best hashing function? "D. Aaron Sawyer" <aaron@110.net> - 2015-09-16 14:22 -0300
      Re: What's the best hashing function? fir <profesor.fir@gmail.com> - 2015-09-16 10:59 -0700
        Re: What's the best hashing function? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-09-16 19:44 +0100
          Re: What's the best hashing function? fir <profesor.fir@gmail.com> - 2015-09-16 12:32 -0700
            Re: What's the best hashing function? Bartc <bc@freeuk.com> - 2015-09-16 20:40 +0100
              Re: What's the best hashing function? Keith Thompson <kst-u@mib.org> - 2015-09-16 13:11 -0700
              Re: What's the best hashing function? "James Harris" <james.harris.1@gmail.com> - 2015-09-16 21:16 +0100
                Re: What's the best hashing function? fir <profesor.fir@gmail.com> - 2015-09-16 13:47 -0700
                  Re: What's the best hashing function? fir <profesor.fir@gmail.com> - 2015-09-16 14:14 -0700
                Re: What's the best hashing function? Robert Wessel <robertwessel2@yahoo.com> - 2015-09-16 18:08 -0500
                  Re: What's the best hashing function? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-09-17 00:13 +0100
                  Re: What's the best hashing function? fir <profesor.fir@gmail.com> - 2015-09-20 01:13 -0700
            Re: What's the best hashing function? Malcolm McLean <malcolm.mclean5@btinternet.com> - 2015-09-16 13:10 -0700
            Re: What's the best hashing function? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-09-16 22:17 +0100
              Re: What's the best hashing function? fir <profesor.fir@gmail.com> - 2015-09-16 14:33 -0700
                Re: What's the best hashing function? fir <profesor.fir@gmail.com> - 2015-09-16 14:48 -0700
                  Re: What's the best hashing function? fir <profesor.fir@gmail.com> - 2015-09-16 14:58 -0700
                    Re: What's the best hashing function? Robert Wessel <robertwessel2@yahoo.com> - 2015-09-16 18:13 -0500
                    Re: What's the best hashing function? supercat@casperkitty.com - 2015-09-16 16:29 -0700
                    Re: What's the best hashing function? David Brown <david.brown@hesbynett.no> - 2015-09-17 10:17 +0200
                      Re: What's the best hashing function? Keith Thompson <kst-u@mib.org> - 2015-09-17 08:53 -0700
                      Re: What's the best hashing function? supercat@casperkitty.com - 2015-09-17 11:29 -0700
                        Re: What's the best hashing function? David Brown <david.brown@hesbynett.no> - 2015-09-18 10:07 +0200
                          Re: What's the best hashing function? Richard Heathfield <rjh@cpax.org.uk> - 2015-09-18 09:20 +0100
                          Re: What's the best hashing function? supercat@casperkitty.com - 2015-09-18 09:25 -0700
                            Re: What's the best hashing function? David Brown <david.brown@hesbynett.no> - 2015-09-18 19:45 +0200
                              Re: What's the best hashing function? supercat@casperkitty.com - 2015-09-18 11:47 -0700
                                Re: What's the best hashing function? David Brown <david.brown@hesbynett.no> - 2015-09-18 21:49 +0200
                                  Re: What's the best hashing function? supercat@casperkitty.com - 2015-09-18 14:50 -0700
                                    Re: What's the best hashing function? Malcolm McLean <malcolm.mclean5@btinternet.com> - 2015-09-19 00:23 -0700
                                    Re: What's the best hashing function? David Brown <david.brown@hesbynett.no> - 2015-09-19 11:13 +0200
                                      Re: What's the best hashing function? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-09-19 11:03 +0100
                                        Re: What's the best hashing function? David Brown <david.brown@hesbynett.no> - 2015-09-19 12:38 +0200
                                      Re: What's the best hashing function? supercat@casperkitty.com - 2015-09-21 11:29 -0700
                                        Re: What's the best hashing function? David Brown <david.brown@hesbynett.no> - 2015-09-22 10:23 +0200
                                          Re: What's the best hashing function? Malcolm McLean <malcolm.mclean5@btinternet.com> - 2015-09-22 02:31 -0700
                                            Re: What's the best hashing function? supercat@casperkitty.com - 2015-09-22 11:28 -0700
                                          Re: What's the best hashing function? supercat@casperkitty.com - 2015-09-22 11:18 -0700
                  Re: What's the best hashing function? David Brown <david.brown@hesbynett.no> - 2015-09-17 10:24 +0200
                    Re: What's the best hashing function? fir <profesor.fir@gmail.com> - 2015-09-17 01:48 -0700
                      Re: What's the best hashing function? fir <profesor.fir@gmail.com> - 2015-09-17 01:56 -0700
                      Re: What's the best hashing function? fir <profesor.fir@gmail.com> - 2015-09-17 02:09 -0700
              Re: What's the best hashing function? Keith Thompson <kst-u@mib.org> - 2015-09-16 14:49 -0700
                Re: What's the best hashing function? glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2015-09-16 21:56 +0000
                Re: What's the best hashing function? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-09-16 23:37 +0100
          Re: What's the best hashing function? supercat@casperkitty.com - 2015-09-16 13:02 -0700
            Re: What's the best hashing function? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-09-16 21:57 +0100
              Re: What's the best hashing function? supercat@casperkitty.com - 2015-09-16 14:16 -0700
            Re: What's the best hashing function? glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2015-09-16 21:57 +0000
              Re: What's the best hashing function? supercat@casperkitty.com - 2015-09-16 16:20 -0700

Page 1 of 3  [1] 2 3  Next page →

#70649 — Re: What's the best hashing function?

I encountered recently some example like
this, Though i not tested it

its in jave i dont know what >>> means 

/** Robert Jenkins' 96 bit Mix Function. */
private static int mix(int a, int b, int c) {
    a=a-b;  a=a-c;  a=a^(c >>> 13);
    b=b-c;  b=b-a;  b=b^(a << 8);
    c=c-a;  c=c-b;  c=c^(b >>> 13);
    a=a-b;  a=a-c;  a=a^(c >>> 12);
    b=b-c;  b=b-a;  b=b^(a << 16);
    c=c-a;  c=c-b;  c=c^(b >>> 5);
    a=a-b;  a=a-c;  a=a^(c >>> 3);
    b=b-c;  b=b-a;  b=b^(a << 10);
    c=c-a;  c=c-b;  c=c^(b >>> 15);
    return c;
}

[toc] | [next] | [standalone]

#70657

On 2015.09.16 13:35, fir wrote:
> I encountered recently some example like
> this, Though i not tested it
>
> its in jave i dont know what >>> means
>
> /** Robert Jenkins' 96 bit Mix Function. */
> private static int mix(int a, int b, int c) {
>      a=a-b;  a=a-c;  a=a^(c >>> 13);
>      b=b-c;  b=b-a;  b=b^(a << 8);
>      c=c-a;  c=c-b;  c=c^(b >>> 13);
>      a=a-b;  a=a-c;  a=a^(c >>> 12);
>      b=b-c;  b=b-a;  b=b^(a << 16);
>      c=c-a;  c=c-b;  c=c^(b >>> 5);
>      a=a-b;  a=a-c;  a=a^(c >>> 3);
>      b=b-c;  b=b-a;  b=b^(a << 10);
>      c=c-a;  c=c-b;  c=c^(b >>> 15);
>      return c;
> }
>

The '>>>' operator is an unsigned right shift (no sign bit propagation on shift).
E.g., (-3 >>> 1) or (for 32-bit int) (0xfffffffd >>> 1) results in
(0x7ffffffe) or (MAX_INT-1)

Compare with (-3 >> 1) or (0xfffffffd >> 1) which results in
(0xfffffffe) or (-2)

HTH,

[toc] | [prev] | [next] | [standalone]

#70668

W dniu środa, 16 września 2015 19:22:31 UTC+2 użytkownik D. Aaron Sawyer napisał:
> On 2015.09.16 13:35, fir wrote:
> > I encountered recently some example like
> > this, Though i not tested it
> >
> > its in jave i dont know what >>> means
> >
> > /** Robert Jenkins' 96 bit Mix Function. */
> > private static int mix(int a, int b, int c) {
> >      a=a-b;  a=a-c;  a=a^(c >>> 13);
> >      b=b-c;  b=b-a;  b=b^(a << 8);
> >      c=c-a;  c=c-b;  c=c^(b >>> 13);
> >      a=a-b;  a=a-c;  a=a^(c >>> 12);
> >      b=b-c;  b=b-a;  b=b^(a << 16);
> >      c=c-a;  c=c-b;  c=c^(b >>> 5);
> >      a=a-b;  a=a-c;  a=a^(c >>> 3);
> >      b=b-c;  b=b-a;  b=b^(a << 10);
> >      c=c-a;  c=c-b;  c=c^(b >>> 15);
> >      return c;
> > }
> >
> 
> The '>>>' operator is an unsigned right shift (no sign bit propagation on shift).
> E.g., (-3 >>> 1) or (for 32-bit int) (0xfffffffd >>> 1) results in
> (0x7ffffffe) or (MAX_INT-1)
> 
> Compare with (-3 >> 1) or (0xfffffffd >> 1) which results in
> (0xfffffffe) or (-2)
> 
alright, tnx

btw, this c >> operator is signed or unsigned (in c language) ?

[toc] | [prev] | [next] | [standalone]

#70674

fir <profesor.fir@gmail.com> writes:

> W dniu środa, 16 września 2015 19:22:31 UTC+2 użytkownik D. Aaron Sawyer napisał:
>> On 2015.09.16 13:35, fir wrote:
>> > I encountered recently some example like
>> > this, Though i not tested it
>> >
>> > its in jave i dont know what >>> means
>> >
>> > /** Robert Jenkins' 96 bit Mix Function. */
>> > private static int mix(int a, int b, int c) {
>> >      a=a-b;  a=a-c;  a=a^(c >>> 13);
>> >      b=b-c;  b=b-a;  b=b^(a << 8);
>> >      c=c-a;  c=c-b;  c=c^(b >>> 13);
>> >      a=a-b;  a=a-c;  a=a^(c >>> 12);
>> >      b=b-c;  b=b-a;  b=b^(a << 16);
>> >      c=c-a;  c=c-b;  c=c^(b >>> 5);
>> >      a=a-b;  a=a-c;  a=a^(c >>> 3);
>> >      b=b-c;  b=b-a;  b=b^(a << 10);
>> >      c=c-a;  c=c-b;  c=c^(b >>> 15);
>> >      return c;
>> > }
>> >
>> 
>> The '>>>' operator is an unsigned right shift (no sign bit
>> propagation on shift).
>> E.g., (-3 >>> 1) or (for 32-bit int) (0xfffffffd >>> 1) results in
>> (0x7ffffffe) or (MAX_INT-1)
>> 
>> Compare with (-3 >> 1) or (0xfffffffd >> 1) which results in
>> (0xfffffffe) or (-2)
>> 
> alright, tnx
>
> btw, this c >> operator is signed or unsigned (in c language) ?

Both, but c >> n is only defined (by C) for non-negative values of c.
When c is negative, c >> n is implementation defined (most likely it
will be whatever the hardware does).

If you are planning to translate the Java above into portable C, you
should also know that the arithmetic operations might have undefined
results due to overflow.  If it were down to me, I'd just re-write it to
use undefined types, at least internally.  If you need to have a signed
result (you probably don't -- that's most likely a hang-over from the
time when Java did not have unsigned types) you can avoid undefined
behaviour that stems from the conversion by using a union.  That has
it's own issues, of course, but they are likely to be rarer than a trap
on overflow.

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#70683

W dniu środa, 16 września 2015 20:44:21 UTC+2 użytkownik Ben Bacarisse napisał:
> fir <profesor.fir@gmail.com> writes:
> 
> > W dniu środa, 16 września 2015 19:22:31 UTC+2 użytkownik D. Aaron Sawyer napisał:
> >> On 2015.09.16 13:35, fir wrote:
> >> > I encountered recently some example like
> >> > this, Though i not tested it
> >> >
> >> > its in jave i dont know what >>> means
> >> >
> >> > /** Robert Jenkins' 96 bit Mix Function. */
> >> > private static int mix(int a, int b, int c) {
> >> >      a=a-b;  a=a-c;  a=a^(c >>> 13);
> >> >      b=b-c;  b=b-a;  b=b^(a << 8);
> >> >      c=c-a;  c=c-b;  c=c^(b >>> 13);
> >> >      a=a-b;  a=a-c;  a=a^(c >>> 12);
> >> >      b=b-c;  b=b-a;  b=b^(a << 16);
> >> >      c=c-a;  c=c-b;  c=c^(b >>> 5);
> >> >      a=a-b;  a=a-c;  a=a^(c >>> 3);
> >> >      b=b-c;  b=b-a;  b=b^(a << 10);
> >> >      c=c-a;  c=c-b;  c=c^(b >>> 15);
> >> >      return c;
> >> > }
> >> >
> >> 
> >> The '>>>' operator is an unsigned right shift (no sign bit
> >> propagation on shift).
> >> E.g., (-3 >>> 1) or (for 32-bit int) (0xfffffffd >>> 1) results in
> >> (0x7ffffffe) or (MAX_INT-1)
> >> 
> >> Compare with (-3 >> 1) or (0xfffffffd >> 1) which results in
> >> (0xfffffffe) or (-2)
> >> 
> > alright, tnx
> >
> > btw, this c >> operator is signed or unsigned (in c language) ?
> 
> Both, but c >> n is only defined (by C) for non-negative values of c.
> When c is negative, c >> n is implementation defined (most likely it
> will be whatever the hardware does).
> 
> If you are planning to translate the Java above into portable C, you
> should also know that the arithmetic operations might have undefined
> results due to overflow.  If it were down to me, I'd just re-write it to
> use undefined types, at least internally.  If you need to have a signed
> result (you probably don't -- that's most likely a hang-over from the
> time when Java did not have unsigned types) you can avoid undefined
> behaviour that stems from the conversion by using a union.  That has
> it's own issues, of course, but they are likely to be rarer than a trap
> on overflow.
> 
so in short it means it is inpossible to revrite it to c? (i dont think so it is easily convertable to unsigned one in java side - seem sthat it is impossible to port it tio c then)

now that seems some flaw of c, very sad
(seems to repair it c should have those java operators to (or mora all this rors shrs etc, at least maybe as a intrinsics if not operators)

[toc] | [prev] | [next] | [standalone]

#70685

On 16/09/2015 20:32, fir wrote:
> W dniu środa, 16 września 2015 20:44:21 UTC+2 użytkownik Ben Bacarisse napisał:
>> fir <profesor.fir@gmail.com> writes:

>>>>>       a=a-b;  a=a-c;  a=a^(c >>> 13);

>>>> The '>>>' operator is an unsigned right shift (no sign bit

> so in short it means it is inpossible to revrite it to c? (i dont think so it is easily convertable to unsigned one in java side - seem sthat it is impossible to port it tio c then)

If a >>> b means unsigned right shift, then I guess it's equivalent to 
(unsigned)a >> (unsigned)b.

-- 
Bartc

[toc] | [prev] | [next] | [standalone]

#70693

Bartc <bc@freeuk.com> writes:
[...]
> If a >>> b means unsigned right shift, then I guess it's equivalent to 
> (unsigned)a >> (unsigned)b.

Or to a >> b if a and b are defined as unsigned (which they probably
should be).

-- 
Keith Thompson (The_Other_Keith) kst-u@mib.org  <http://www.ghoti.net/~kst>
Working, but not speaking, for JetHead Development, Inc.
"We must do something.  This is something.  Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"

[toc] | [prev] | [next] | [standalone]

#70697

"Bartc" <bc@freeuk.com> wrote in message 
news:mtcgf4$ki6$1@dont-email.me...

...

> If a >>> b means unsigned right shift, then I guess it's equivalent to 
> (unsigned)a >> (unsigned)b.

Do you need the (unsigned) before b? Surely that side needs to be 
non-negative anyway. If it's not then the program has bigger 
concerns...!

Also, I haven't been following this thread so this may have been 
discussed but I thought C's >> was only well defined on unsigned 
integers. There may be better terms but I mean that a right shift of 
negative signed numbers may have implementation-defined behaviour 
(because representations differ).

James

[toc] | [prev] | [next] | [standalone]

#70706

W dniu środa, 16 września 2015 22:16:29 UTC+2 użytkownik James Harris napisał:
> "Bartc" <bc@freeuk.com> wrote in message 
> news:mtcgf4$ki6$1@dont-email.me...
> 
> ...
> 
> > If a >>> b means unsigned right shift, then I guess it's equivalent to 
> > (unsigned)a >> (unsigned)b.
> 
> Do you need the (unsigned) before b? Surely that side needs to be 
> non-negative anyway. If it's not then the program has bigger 
> concerns...!
> 
> Also, I haven't been following this thread so this may have been 
> discussed but I thought C's >> was only well defined on unsigned 
> integers. There may be better terms but I mean that a right shift of 
> negative signed numbers may have implementation-defined behaviour 
> (because representations differ).
> 
> James

anyway speaking of this function this probably is just needed to efective inter-mix involved values a lot (this suggest that substraction can do some orthogonal mix to this shifts resulting in at all convoluted mix -- i dont know the theory but i vaguelly suspect so 9as a hypotesis).. if so that would mean (maybe) that rolls and rors (with no inserting bits would be maybe yet better
(still not sure though)
- probably no java nor c provides this rors and rols too 

[toc] | [prev] | [next] | [standalone]

#70717

W dniu środa, 16 września 2015 22:47:29 UTC+2 użytkownik fir napisał:
> W dniu środa, 16 września 2015 22:16:29 UTC+2 użytkownik James Harris napisał:
> > "Bartc" <bc@freeuk.com> wrote in message 
> > news:mtcgf4$ki6$1@dont-email.me...
> > 
> > ...
> > 
> > > If a >>> b means unsigned right shift, then I guess it's equivalent to 
> > > (unsigned)a >> (unsigned)b.
> > 
> > Do you need the (unsigned) before b? Surely that side needs to be 
> > non-negative anyway. If it's not then the program has bigger 
> > concerns...!
> > 
> > Also, I haven't been following this thread so this may have been 
> > discussed but I thought C's >> was only well defined on unsigned 
> > integers. There may be better terms but I mean that a right shift of 
> > negative signed numbers may have implementation-defined behaviour 
> > (because representations differ).
> > 
> > James
> 
> anyway speaking of this function this probably is just needed to efective inter-mix involved values a lot (this suggest that substraction can do some orthogonal mix to this shifts resulting in at all convoluted mix -- i dont know the theory but i vaguelly suspect so 9as a hypotesis).. if so that would mean (maybe) that rolls and rors (with no inserting bits would be maybe yet better
> (still not sure though)
> - probably no java nor c provides this rors and rols too

small theory on "how to mix bits most uniformly" would be needed (if they need to be mixed to the gray uniform state not the
dark and white smuges - but probably gray
would fit better

[toc] | [prev] | [next] | [standalone]

#70745

On Wed, 16 Sep 2015 21:16:20 +0100, "James Harris"
<james.harris.1@gmail.com> wrote:

>"Bartc" <bc@freeuk.com> wrote in message 
>news:mtcgf4$ki6$1@dont-email.me...
>
>...
>
>> If a >>> b means unsigned right shift, then I guess it's equivalent to 
>> (unsigned)a >> (unsigned)b.
>
>Do you need the (unsigned) before b? Surely that side needs to be 
>non-negative anyway. If it's not then the program has bigger 
>concerns...!
>
>Also, I haven't been following this thread so this may have been 
>discussed but I thought C's >> was only well defined on unsigned 
>integers. There may be better terms but I mean that a right shift of 
>negative signed numbers may have implementation-defined behaviour 
>(because representations differ).


C's shifts are well defined for signed left operands containing
positive values (or zero), and for all values of the left operand when
the operands are unsigned.  They're also only defined for values of
the right operand between 1 and the size in bits less one.

[toc] | [prev] | [next] | [standalone]

#70746

Robert Wessel <robertwessel2@yahoo.com> writes:

> On Wed, 16 Sep 2015 21:16:20 +0100, "James Harris"
> <james.harris.1@gmail.com> wrote:
>
>>"Bartc" <bc@freeuk.com> wrote in message 
>>news:mtcgf4$ki6$1@dont-email.me...
>>
>>...
>>
>>> If a >>> b means unsigned right shift, then I guess it's equivalent to 
>>> (unsigned)a >> (unsigned)b.
>>
>>Do you need the (unsigned) before b? Surely that side needs to be 
>>non-negative anyway. If it's not then the program has bigger 
>>concerns...!
>>
>>Also, I haven't been following this thread so this may have been 
>>discussed but I thought C's >> was only well defined on unsigned 
>>integers. There may be better terms but I mean that a right shift of 
>>negative signed numbers may have implementation-defined behaviour 
>>(because representations differ).
>
>
> C's shifts are well defined for signed left operands containing
> positive values (or zero), and for all values of the left operand when
> the operands are unsigned.  They're also only defined for values of
> the right operand between 1 and the size in bits less one.

s/1/0/

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#70970

W dniu czwartek, 17 września 2015 01:08:28 UTC+2 użytkownik robert...@yahoo.com napisał:
> On Wed, 16 Sep 2015 21:16:20 +0100, "James Harris"
> <james.harris.1@gmail.com> wrote:
> 
> >"Bartc" <bc@freeuk.com> wrote in message 
> >news:mtcgf4$ki6$1@dont-email.me...
> >
> >...
> >
> >> If a >>> b means unsigned right shift, then I guess it's equivalent to 
> >> (unsigned)a >> (unsigned)b.
> >
> >Do you need the (unsigned) before b? Surely that side needs to be 
> >non-negative anyway. If it's not then the program has bigger 
> >concerns...!
> >
> >Also, I haven't been following this thread so this may have been 
> >discussed but I thought C's >> was only well defined on unsigned 
> >integers. There may be better terms but I mean that a right shift of 
> >negative signed numbers may have implementation-defined behaviour 
> >(because representations differ).
> 
> 
> C's shifts are well defined for signed left operands containing
> positive values (or zero), and for all values of the left operand when
> the operands are unsigned.  They're also only defined for values of
> the right operand between 1 and the size in bits less one.

well after consideration it seems to me 
that -4 >> 1 should yeild -2 (as it seems
in gcc, and as someone said like it should resemble division) thus it seems it should be filled with 1 (it wouldnt need new operator as operator could be chosen by signed/unsigned type)

though if -1 is 1111 1111 then -1>>1 is still 1111 1111 so what with that? - it 
seems that U2 is not compatible with such
dividing-shifts

it overall seems that in th world of signed computer numbers full zeros and full ones are both special meanings - it seems that
full ones (I mean the opposite zero value - in u2 its 1000 0000 but maybe it should be more like 1111 1111) shouldnt be treatet as a just -128 as this is assymetric etc, it should be probably treated as a special value who has maybe even many properties 
like +-OvERFloW, +-inf, (-0 too?)

now i think there is a flaw in signed mapping of int

0xxx xxxx
1xxx xxxx

positive 0-127 are obvious but definition of negatives seem be at least three possible

-3 =>

1) 1000 0011
2) 1111 1100  [2]
3) 1111 1101 (U2)

maybe only u2 is compatible with a block of ellectronics that can be used to do add/subb arithmetic on unsigned values - well if so maybe it is still best option - and my temp idea of [2] with double zero 0000 0000, 1111 1111 is more flawed {though its some xchange for properties its hard to compare without deeper investigation]
anyway im flawed is still treating this special anti-zero value as a just -128

[toc] | [prev] | [next] | [standalone]

#70692

On Wednesday, September 16, 2015 at 8:32:30 PM UTC+1, fir wrote:
> W dniu środa, 16 września 2015 20:44:21 UTC+2 użytkownik Ben Bacarisse napisał:
> > fir <profesor.fir@gmail.com> writes:
> > 
> > > W dniu środa, 16 września 2015 19:22:31 UTC+2 użytkownik D. Aaron Sawyer napisał:
> > >> On 2015.09.16 13:35, fir wrote:
> > >> > I encountered recently some example like
> > >> > this, Though i not tested it
> > >> >
> > >> > its in jave i dont know what >>> means
> > >> >
> > >> > /** Robert Jenkins' 96 bit Mix Function. */
> > >> > private static int mix(int a, int b, int c) {
> > >> >      a=a-b;  a=a-c;  a=a^(c >>> 13);
> > >> >      b=b-c;  b=b-a;  b=b^(a << 8);
> > >> >      c=c-a;  c=c-b;  c=c^(b >>> 13);
> > >> >      a=a-b;  a=a-c;  a=a^(c >>> 12);
> > >> >      b=b-c;  b=b-a;  b=b^(a << 16);
> > >> >      c=c-a;  c=c-b;  c=c^(b >>> 5);
> > >> >      a=a-b;  a=a-c;  a=a^(c >>> 3);
> > >> >      b=b-c;  b=b-a;  b=b^(a << 10);
> > >> >      c=c-a;  c=c-b;  c=c^(b >>> 15);
> > >> >      return c;
> > >> > }
> > >> >
> > >> 
> > >> The '>>>' operator is an unsigned right shift (no sign bit
> > >> propagation on shift).
> > >> E.g., (-3 >>> 1) or (for 32-bit int) (0xfffffffd >>> 1) results in
> > >> (0x7ffffffe) or (MAX_INT-1)
> > >> 
> > >> Compare with (-3 >> 1) or (0xfffffffd >> 1) which results in
> > >> (0xfffffffe) or (-2)
> > >> 
> > > alright, tnx
> > >
> > > btw, this c >> operator is signed or unsigned (in c language) ?
> > 
> > Both, but c >> n is only defined (by C) for non-negative values of c.
> > When c is negative, c >> n is implementation defined (most likely it
> > will be whatever the hardware does).
> > 
> > If you are planning to translate the Java above into portable C, you
> > should also know that the arithmetic operations might have undefined
> > results due to overflow.  If it were down to me, I'd just re-write it to
> > use undefined types, at least internally.  If you need to have a signed
> > result (you probably don't -- that's most likely a hang-over from the
> > time when Java did not have unsigned types) you can avoid undefined
> > behaviour that stems from the conversion by using a union.  That has
> > it's own issues, of course, but they are likely to be rarer than a trap
> > on overflow.
> > 
> so in short it means it is inpossible to revrite it to c? (i dont 
> think so it is easily convertable to unsigned one in java side - 
> seem sthat it is impossible to port it tio c then)
> 
No, you find the top bit. Then you use the logical operators to set 
the new bits to either zero or sign-extend.
It's a fiddle, but not undoable.

[toc] | [prev] | [next] | [standalone]

#70719

fir <profesor.fir@gmail.com> writes:
<snip>
>> >> On 2015.09.16 13:35, fir wrote:
>> >> > I encountered recently some example like
>> >> > this, Though i not tested it
>> >> >
>> >> > its in jave i dont know what >>> means
>> >> >
>> >> > /** Robert Jenkins' 96 bit Mix Function. */
>> >> > private static int mix(int a, int b, int c) {
>> >> >      a=a-b;  a=a-c;  a=a^(c >>> 13);
>> >> >      b=b-c;  b=b-a;  b=b^(a << 8);
>> >> >      c=c-a;  c=c-b;  c=c^(b >>> 13);
>> >> >      a=a-b;  a=a-c;  a=a^(c >>> 12);
>> >> >      b=b-c;  b=b-a;  b=b^(a << 16);
>> >> >      c=c-a;  c=c-b;  c=c^(b >>> 5);
>> >> >      a=a-b;  a=a-c;  a=a^(c >>> 3);
>> >> >      b=b-c;  b=b-a;  b=b^(a << 10);
>> >> >      c=c-a;  c=c-b;  c=c^(b >>> 15);
>> >> >      return c;
>> >> > }
<snip>
> so in short it means it is inpossible to revrite it to c?

No, that's not it at all.  It should be obvious that a C re-write is
possible.  The only question is how much effort do you want to put in to
make the code have *exactly* the same semantics on *every* conforming C
implementation.  The answer is none, because, ironically, the original
Jenkins hash function was written C.  The Java re-write has been forced
to use signed integers (presumably it's old Java) and has therefore has
altered the semantics (though probably not at the bit-level).  Anyway,
just use the original C version.

Or even use one of the newer hash function he's designed like:
http://www.burtleburtle.net/bob/hash/spooky.html

<snip>
-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#70722

W dniu środa, 16 września 2015 23:17:24 UTC+2 użytkownik Ben Bacarisse napisał:
> fir <profesor.fir@gmail.com> writes:
> <snip>
> >> >> On 2015.09.16 13:35, fir wrote:
> >> >> > I encountered recently some example like
> >> >> > this, Though i not tested it
> >> >> >
> >> >> > its in jave i dont know what >>> means
> >> >> >
> >> >> > /** Robert Jenkins' 96 bit Mix Function. */
> >> >> > private static int mix(int a, int b, int c) {
> >> >> >      a=a-b;  a=a-c;  a=a^(c >>> 13);
> >> >> >      b=b-c;  b=b-a;  b=b^(a << 8);
> >> >> >      c=c-a;  c=c-b;  c=c^(b >>> 13);
> >> >> >      a=a-b;  a=a-c;  a=a^(c >>> 12);
> >> >> >      b=b-c;  b=b-a;  b=b^(a << 16);
> >> >> >      c=c-a;  c=c-b;  c=c^(b >>> 5);
> >> >> >      a=a-b;  a=a-c;  a=a^(c >>> 3);
> >> >> >      b=b-c;  b=b-a;  b=b^(a << 10);
> >> >> >      c=c-a;  c=c-b;  c=c^(b >>> 15);
> >> >> >      return c;
> >> >> > }
> <snip>
> > so in short it means it is inpossible to revrite it to c?
> 
> No, that's not it at all.  It should be obvious that a C re-write is
> possible.  The only question is how much effort do you want to put in to
> make the code have *exactly* the same semantics on *every* conforming C
> implementation.  The answer is none, because, ironically, the original
> Jenkins hash function was written C.  The Java re-write has been forced
> to use signed integers (presumably it's old Java) and has therefore has
> altered the semantics (though probably not at the bit-level).  Anyway,
> just use the original C version.
> 
> Or even use one of the newer hash function he's designed like:
> http://www.burtleburtle.net/bob/hash/spooky.html
> 

aa-h, okay
though if this particular example has its easy correspondent doesnt probably neccessary mean that all code that uses signed or unsigned shifts on negative integers can be revritten (and thats a bit worry - they should gave at least all those intrinsics in gcc if x86 supports it (and x86 afaik supports a wide wariety of shifts)

I vote for gcc intrinsics for all the x86 usable assembly to use (intrinsics should be probably standard term in c, as its great usability (not necessary 'portab;e' 9avaliable on all c targets, but as a platform dependant parts of stdlib or something (who said stdlib must be all portable) ) **

(** it all untill ev some more organisation will be done, as im not great fan of clib at all, but intrinsics are at least extreamly usable 'patch' for platforms (or seems so))

[toc] | [prev] | [next] | [standalone]

#70726

W dniu środa, 16 września 2015 23:33:49 UTC+2 użytkownik fir napisał:
> W dniu środa, 16 września 2015 23:17:24 UTC+2 użytkownik Ben Bacarisse napisał:
> > fir <profesor.fir@gmail.com> writes:
> > <snip>
> > >> >> On 2015.09.16 13:35, fir wrote:
> > >> >> > I encountered recently some example like
> > >> >> > this, Though i not tested it
> > >> >> >
> > >> >> > its in jave i dont know what >>> means
> > >> >> >
> > >> >> > /** Robert Jenkins' 96 bit Mix Function. */
> > >> >> > private static int mix(int a, int b, int c) {
> > >> >> >      a=a-b;  a=a-c;  a=a^(c >>> 13);
> > >> >> >      b=b-c;  b=b-a;  b=b^(a << 8);
> > >> >> >      c=c-a;  c=c-b;  c=c^(b >>> 13);
> > >> >> >      a=a-b;  a=a-c;  a=a^(c >>> 12);
> > >> >> >      b=b-c;  b=b-a;  b=b^(a << 16);
> > >> >> >      c=c-a;  c=c-b;  c=c^(b >>> 5);
> > >> >> >      a=a-b;  a=a-c;  a=a^(c >>> 3);
> > >> >> >      b=b-c;  b=b-a;  b=b^(a << 10);
> > >> >> >      c=c-a;  c=c-b;  c=c^(b >>> 15);
> > >> >> >      return c;
> > >> >> > }
> > <snip>
> > > so in short it means it is inpossible to revrite it to c?
> > 
> > No, that's not it at all.  It should be obvious that a C re-write is
> > possible.  The only question is how much effort do you want to put in to
> > make the code have *exactly* the same semantics on *every* conforming C
> > implementation.  The answer is none, because, ironically, the original
> > Jenkins hash function was written C.  The Java re-write has been forced
> > to use signed integers (presumably it's old Java) and has therefore has
> > altered the semantics (though probably not at the bit-level).  Anyway,
> > just use the original C version.
> > 
> > Or even use one of the newer hash function he's designed like:
> > http://www.burtleburtle.net/bob/hash/spooky.html
> > 
> 
> aa-h, okay
> though if this particular example has its easy correspondent doesnt probably neccessary mean that all code that uses signed or unsigned shifts on negative integers can be revritten (and thats a bit worry - they should gave at least all those intrinsics in gcc if x86 supports it (and x86 afaik supports a wide wariety of shifts)
> 
> I vote for gcc intrinsics for all the x86 usable assembly to use (intrinsics should be probably standard term in c, as its great usability (not necessary 'portab;e' 9avaliable on all c targets, but as a platform dependant parts of stdlib or something (who said stdlib must be all portable) ) **
> 
> (** it all untill ev some more organisation will be done, as im not great fan of clib at all, but intrinsics are at least extreamly usable 'patch' for platforms (or seems so))

this is word on c standard (that maybe those people who care much about standard should be interested maybe on this topic) ->

it is okay that c is designed to work on so wide variety of platforms and thus has so many undefined parts ((though c has also iirc some undefined parts that are not justified by different platform behaviours 
- those maybe should be just defined))

but if so c should also probably standarize
some platform dependant parts by some groups of platforms 9it seems so), for example if 
the talk is x86 platform or alike, there is need of standarisation those outa-core-standard parts across gcc-vs-clang or what else; becouse if no it is practically silly
(behaviours that could be agreed/coordinated
on platforms are not..

- this leads admittedly to some c variants, like c-x86 c-something other , but better that than nothing (probably))

[toc] | [prev] | [next] | [standalone]

#70731

W dniu środa, 16 września 2015 23:48:38 UTC+2 użytkownik fir napisał:
>((though c has also iirc some undefined parts that are not justified by different platform behaviours 
> - those maybe should be just defined))
> 

small example on this above here is a question if this famous undefined behaviour

foo(a(), b(), c());

has a sense (good reason) to be undefined?
I doubt if this is undefined becouse of varance of platforms, if so what is a reason?

probably it shopuld be just defined in strightforward way: a() is called, b(0 is called, c() is called - then foo() is called

[toc] | [prev] | [next] | [standalone]

#70747

On Wed, 16 Sep 2015 14:58:20 -0700 (PDT), fir <profesor.fir@gmail.com>
wrote:

>W dniu ?roda, 16 wrze?nia 2015 23:48:38 UTC+2 u?ytkownik fir napisa?:
>>((though c has also iirc some undefined parts that are not justified by different platform behaviours 
>> - those maybe should be just defined))
>> 
>
>small example on this above here is a question if this famous undefined behaviour
>
>foo(a(), b(), c());
>
>has a sense (good reason) to be undefined?
>I doubt if this is undefined becouse of varance of platforms, if so what is a reason?
>
>probably it shopuld be just defined in strightforward way: a() is called, b(0 is called, c() is called - then foo() is called


For a simple compiler, on a target with a grow-down stack, it's
usually easiest for the compiler to call c/b/a.

But this, like many of the decisions in the C standard, were
influenced by existing practice at the time the standard was written -
at which time compilers were doing it every which way (and they still
are).  A standard that basically breaks most of the existing compilers
would have been much less likely to be accepted.

In the case of Java, these things were (mostly) defined ahead of time.

[toc] | [prev] | [next] | [standalone]

#70754

On Wednesday, September 16, 2015 at 4:58:34 PM UTC-5, fir wrote:
> small example on this above here is a question if this famous undefined behaviour
> 
> foo(a(), b(), c());
> 
> has a sense (good reason) to be undefined?

The behavior of that function is defined as calling a, b, and c in some
arbitrary order, and then calling foo with the values returned by those
functions.  The sequence is Unspecified, but there is no Undefined
Behavior.

The reason the sequence is unspecified is, among other things, to allow for
the possibility that one of the functions (foo, a, b, or c) might benefit
from something that gets left in a register by earlier code.  There
is no requirement that a compiler document the order in which it calls the
functions, nor even that it be in any way consistent.  For example, given:

    x=23;
    for (i=0; i<6; i++)
      y=foo(a(x), b(), c(y));

a compiler might unroll the loop in such a way that the first interation
calls a(x) first, taking advantage of the fact that "x" was left in a
register by "x=23", but subsequent iterations call "c(y)" first, taking
advantage of the fact that y was left in a register by the previous call
to "foo".  Code which cares about the order in which a(), b(), and c() are
called should specify that by using separate statements to invoke them and
copy the results to temporary variables.

[toc] | [prev] | [next] | [standalone]

Page 1 of 3  [1] 2 3  Next page →

Back to top | Article view | comp.lang.c

csiph-web