Pointer hashing

classic Classic list List threaded Threaded
7 messages Options
Reply | Threaded
Open this post in threaded view
|

Pointer hashing

Ryan Joseph
I’m trying to hash a pointer value and found some example of hash function but not sure about translations and the process in general.

1) Should I cast “pointer” as PtrUInt to get an integer from a pointer? I’m looking for the memory address I guess and casting seems to return a unique value. Btw, these functions are for a 32 bit integer but I’m building for 64 bit. How do I deal with that? Can I remove the upper 32bits which are typically not used.

2) I’m getting incompatible type errors on my translation. What did I do wrong there? The fact the function is 32 bit may be the problem?

unsigned int hash(unsigned int x) {
    x = ((x >> 16) ^ x) * 0x45d9f3b;
    x = ((x >> 16) ^ x) * 0x45d9f3b;
    x = (x >> 16) ^ x;
    return x;
}

function Hash (x: PtrUInt): PtrUInt;
begin
  x := (Power((x shr 16), x)) * $45d9f3b;
  x := (Power((x shr 16), x)) * $45d9f3b;
  x := Power((x shr 16), x);
  result := x;
end;

Thanks for any ideas you have.

Regards,
        Ryan Joseph

_______________________________________________
fpc-pascal maillist  -  [hidden email]
http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-pascal
Reply | Threaded
Open this post in threaded view
|

Re: Pointer hashing

noreply
On Sun, January 29, 2017 7:37 pm, Ryan Joseph wrote:
> I'm trying to hash a pointer value and found some example of hash
> function but not sure about translations and the process in general.
...

> x := (Power((x shr 16), x)) * $45d9f3b; x := Power((x shr 16), x);
result :=


The math unit, is something I've been meaning to try ... don't have much
experience with it.. but did you try the power operator?

It's **

  x := ((x shr 16) ** x) * $45d9f3b;

Above code please do not trust it, I have no experience with operator
overloading (or very little). I did not check to see what the function
does, is, etc.
_______________________________________________
fpc-pascal maillist  -  [hidden email]
http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-pascal
Reply | Threaded
Open this post in threaded view
|

Re: Pointer hashing

Marco van de Voort
In reply to this post by Ryan Joseph
In our previous episode, Ryan Joseph said:

>
> unsigned int hash(unsigned int x) {
>     x = ((x >> 16) ^ x) * 0x45d9f3b;
>     x = ((x >> 16) ^ x) * 0x45d9f3b;
>     x = (x >> 16) ^ x;
>     return x;
> }
>
> function Hash (x: PtrUInt): PtrUInt;
> begin
>   x := (Power((x shr 16), x)) * $45d9f3b;
>   x := (Power((x shr 16), x)) * $45d9f3b;
>   x := Power((x shr 16), x);
>   result := x;
> end;

- In C operator crypto lingo, ^ is xor, not exponentiation.
- the lower 3,4 bits of heap pointer are usually not used,
- for 64-bit you probably have to chage this and have more terms also with
- shr 32 and 48

_______________________________________________
fpc-pascal maillist  -  [hidden email]
http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-pascal
Reply | Threaded
Open this post in threaded view
|

Re: Pointer hashing

Karoly Balogh (Charlie/SGR)
In reply to this post by Ryan Joseph
Hi,

On Mon, 30 Jan 2017, Ryan Joseph wrote:

> I?m trying to hash a pointer value and found some example of hash
> function but not sure about translations and the process in general.
>
> 1) Should I cast ?pointer? as PtrUInt to get an integer from a pointer?
> I?m looking for the memory address I guess and casting seems to return a
> unique value. Btw, these functions are for a 32 bit integer but I?m
> building for 64 bit. How do I deal with that? Can I remove the upper
> 32bits which are typically not used.

This hash function doesn't deal with the upper 32bit, therefore it's
probably unsuitable to properly hash 64bit pointers. You need to find an
alternative hash function which does that, if you need 64bit. (Googling
reveals some relevant pages for a 64bit version, if you search that magic
hex number in there...)

> 2) I?m getting incompatible type errors on my translation. What did I do
> wrong there? The fact the function is 32 bit may be the problem?
>
> unsigned int hash(unsigned int x) {
>     x = ((x >> 16) ^ x) * 0x45d9f3b;
>     x = ((x >> 16) ^ x) * 0x45d9f3b;
>     x = (x >> 16) ^ x;
>     return x;
> }
>
> function Hash (x: PtrUInt): PtrUInt;
> begin
>   x := (Power((x shr 16), x)) * $45d9f3b;
>   x := (Power((x shr 16), x)) * $45d9f3b;
>   x := Power((x shr 16), x);
>   result := x;
> end;
>
> Thanks for any ideas you have.

The "^" operator in C simply doesn't translate to "Power" in Pascal. It's
"exclusive or", a.k.a. xor. So that line in C translates to:

x:=((x shr 16) xor x) * $45d9f3b;

Furthermore the Power() function in Math unit seems to deal with Floats
and returns Float, where your type errors might come. But since you don't
need Power() there anyway, that should be an easy fix...

Charlie
_______________________________________________
fpc-pascal maillist  -  [hidden email]
http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-pascal
Reply | Threaded
Open this post in threaded view
|

Re: Pointer hashing

José Mejuto
In reply to this post by Ryan Joseph
El 30/01/2017 a las 3:37, Ryan Joseph escribió:
> I’m trying to hash a pointer value and found some example of hash function but not sure about translations and the process in general.
>

Hello,

After addressing the ^ conversion showed by other people I have a
question. Why you need to hash a pointer ? Hashing a value is
interesting to reduce its compare time (taking collisions into account)
and/or verify message integrity, and hashing a pointer does not meet
none of this goals as it is process wide unique (no collisions) and its
size is the fastest compare operation (most architectures).

--

_______________________________________________
fpc-pascal maillist  -  [hidden email]
http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-pascal
Reply | Threaded
Open this post in threaded view
|

Re: Pointer hashing

Ryan Joseph
Thanks for answering guys. Yes José is right, hashing the pointer wasn’t even a good solution so I used another hash. I had the pointers stored in another data type and I wanted to quickly test for the their entry in the table but I found another way.

> On Jan 30, 2017, at 4:28 PM, José Mejuto <[hidden email]> wrote:
>
> Hello,
>
> After addressing the ^ conversion showed by other people I have a question. Why you need to hash a pointer ? Hashing a value is interesting to reduce its compare time (taking collisions into account) and/or verify message integrity, and hashing a pointer does not meet none of this goals as it is process wide unique (no collisions) and its size is the fastest compare operation (most architectures).

Regards,
        Ryan Joseph

_______________________________________________
fpc-pascal maillist  -  [hidden email]
http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-pascal
Reply | Threaded
Open this post in threaded view
|

Re: Pointer hashing

Mark Morgan Lloyd-5
On 31/01/17 15:30, Ryan Joseph wrote:
> Thanks for answering guys. Yes José is right, hashing the pointer wasn’t even a good solution so I used another hash. I had the pointers stored in another data type and I wanted to quickly test for the their entry in the table but I found another way.
>> On Jan 30, 2017, at 4:28 PM, José Mejuto <[hidden email]> wrote:> > Hello,> > After addressing the ^ conversion showed by other people I have a question. Why you need to hash a pointer ? Hashing a value is interesting to reduce its compare time (taking collisions into account) and/or verify message integrity, and hashing a pointer does not meet none of this goals as it is process wide unique (no collisions) and its size is the fastest compare operation (most architectures).
> Regards, Ryan Joseph

I've hashed some of the fields in a jmp_buf together so that I could do
a quick check that a LongJmp() was being used with a sane parameter.

There's an occasional report in e.g. the Debian mailing lists where a
project is resisting being ported to 64-bit architectures because the
authors have mangled pointers in a size-specific way.

Historically, there's been cases where two pointers in a list node were
xored together to save space, but it's difficult to defend that practice
these days unless the payload is very small.

--
Mark Morgan Lloyd
markMLl .AT. telemetry.co .DOT. uk

[Opinions above are the author's, not those of his employers or colleagues]
_______________________________________________
fpc-pascal maillist  -  [hidden email]
http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-pascal