* FNV-1
@ 2013-10-30 23:31 sbelmont700
2013-10-31 0:03 ` FNV-1 Adam Beneschan
2013-11-01 13:40 ` FNV-1 Georg Bauhaus
0 siblings, 2 replies; 7+ messages in thread
From: sbelmont700 @ 2013-10-30 23:31 UTC (permalink / raw)
Hi,
I did up the following implementation of the FNV1 and FNV1a hashes after needing a decent cross-platform, compiler-independent way to hash things (64-bit pointers, specifically), but it ought to be good for other things as well. I haven't done any extensive testing, but it seems to suit my needs; perhaps it will suit yours as well. Any suggestions are welcome, especially tips on better ways to use static expressions, or any cross-platform 'gotchas'. The code is public domain.
-sb
-- Fowler/Noll/Vo hash functions
with Ada.Containers;
package FNV is
-- FNV-1 Hash
generic
type T is private;
function FNV1 (Item : T) return Ada.Containers.Hash_Type;
-- FNV-1a Alternative Hash
generic
type T is private;
function FNV1a (Item : T) return Ada.Containers.Hash_Type;
end FNV;
pragma Assertion_Policy (Check);
with Ada.Storage_IO;
package body FNV is
subtype FNV_Hash_Type is Ada.Containers.Hash_Type;
use type FNV_Hash_Type;
-- Prime Values
Prime_32 : constant := 2**24 + 2**8 + 16#93#;
Prime_64 : constant := 2**40 + 2**8 + 16#b3#;
Prime_128 : constant := 2**88 + 2**8 + 16#3b#;
Prime_256 : constant := 2**168 + 2**8 + 16#63#;
Prime_512 : constant := 2**344 + 2**8 + 16#57#;
Prime_1024 : constant := 2**680 + 2**8 + 16#8d#;
subtype FNV_Prime_Type is FNV_Hash_Type range 1 .. FNV_Hash_Type'Last;
K_Prime : constant := (case FNV_Prime_Type'Size is
when 32 => Prime_32,
when 64 => Prime_64,
when 128 => Prime_128,
when 256 => Prime_256,
when 512 => Prime_512,
when 1024 => Prime_1024,
when others => 0);
Prime : constant FNV_Prime_Type := K_Prime;
-- Start Offset Values
Offset_32 : constant := 2166136261;
Offset_64 : constant := 14695981039346656037;
Offset_128 : constant := 144066263297769815596495629667062367629;
Offset_256 : constant := 100029257958052580907070968620625704837092796014241193945225284501741471925557;
Offset_512 : constant := 9659303129496669498009435400716310466090418745672637896108374329434462657994582932197716438449813051892206539805784495328239340083876191928701583869517785;
Offset_1024 : constant := 14197795064947621068722070641403218320880622795441933960878474914617582723252296732303717722150864096521202355549365628174669108571814760471015076148029755969804077320157692458563003215304957150157403644460363550505412711285966361610267868082893823963790439336411086884584107735010676915;
subtype FNV_Offset_Type is FNV_Hash_Type range 1 .. FNV_Hash_Type'Last;
K_Offset : constant := (case FNV_Offset_Type'Size is
when 32 => Offset_32,
when 64 => Offset_64,
when 128 => Offset_128,
when 256 => Offset_256,
when 512 => Offset_512,
when 1024 => Offset_1024,
when others => 0);
Offset : constant FNV_Offset_Type := K_Offset;
-----------------------------------------------------------------------------
-- FNV1 Hash Function
-----------------------------------------------------------------------------
function FNV1 (Item : T) return Ada.Containers.Hash_Type is
package Data_Buffers is new Ada.Storage_IO (Element_Type => T);
Buffer : Data_Buffers.Buffer_Type;
begin
Data_Buffers.Write (Buffer => Buffer,
Item => Item);
return Hash : FNV_Hash_Type := Offset do
for Byte of Buffer loop
Hash := Hash * Prime;
Hash := Hash xor FNV_Hash_Type(Byte);
end loop;
end return;
end FNV1;
-----------------------------------------------------------------------------
-- FNV1a Hash Function
-----------------------------------------------------------------------------
function FNV1a (Item : T) return Ada.Containers.Hash_Type is
package Data_Buffers is new Ada.Storage_IO (Element_Type => T);
Buffer : Data_Buffers.Buffer_Type;
begin
Data_Buffers.Write (Buffer => Buffer,
Item => Item);
return Hash : FNV_Hash_Type := Offset do
for Byte of Buffer loop
Hash := Hash xor FNV_Hash_Type(Byte);
Hash := Hash * Prime;
end loop;
end return;
end FNV1a;
end FNV;
^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: FNV-1
2013-10-30 23:31 FNV-1 sbelmont700
@ 2013-10-31 0:03 ` Adam Beneschan
2013-10-31 0:03 ` FNV-1 Adam Beneschan
2013-10-31 19:46 ` FNV-1 sbelmont700
2013-11-01 13:40 ` FNV-1 Georg Bauhaus
1 sibling, 2 replies; 7+ messages in thread
From: Adam Beneschan @ 2013-10-31 0:03 UTC (permalink / raw)
On Wednesday, October 30, 2013 4:31:39 PM UTC-7, sbelm...@gmail.com wrote:
> subtype FNV_Offset_Type is FNV_Hash_Type range 1 .. FNV_Hash_Type'Last;
> K_Offset : constant := (case FNV_Offset_Type'Size is
> when 32 => Offset_32,
> when 64 => Offset_64,
> when 128 => Offset_128,
> when 256 => Offset_256,
> when 512 => Offset_512,
> when 1024 => Offset_1024,
> when others => 0);
I'd worry about whether this is correct. The Implementation Advice in 13.3(55) says about 'Size:
"The Size (if not specified) of a static discrete or fixed point subtype should be the number of bits needed to represent each value belonging to the subtype using an unbiased representation, leaving space for a sign bit only if the subtype contains negative values."
Since FNV_Offset_Subtype doesn't have negative values, this would make it seem that FNV_Offset_Type'Size is more likely to be 31, 63, 127, etc., instead of 32, 64, 128, etc., if the Implementation Advice is followed. Or it could be something totally different depending on how FNV_Hash_Type'Last is defined. Those would play havoc with the definition of K_Offset. I'm not sure how to fix this portably.
-- Adam
^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: FNV-1
2013-10-31 0:03 ` FNV-1 Adam Beneschan
@ 2013-10-31 0:03 ` Adam Beneschan
2013-10-31 19:46 ` FNV-1 sbelmont700
1 sibling, 0 replies; 7+ messages in thread
From: Adam Beneschan @ 2013-10-31 0:03 UTC (permalink / raw)
On Wednesday, October 30, 2013 5:03:11 PM UTC-7, Adam Beneschan wrote:
> Since FNV_Offset_Subtype doesn't have negative values
of course I meant FNV_Offset_Type here.
-- Adam
^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: FNV-1
2013-10-31 0:03 ` FNV-1 Adam Beneschan
2013-10-31 0:03 ` FNV-1 Adam Beneschan
@ 2013-10-31 19:46 ` sbelmont700
2013-10-31 20:35 ` FNV-1 Adam Beneschan
1 sibling, 1 reply; 7+ messages in thread
From: sbelmont700 @ 2013-10-31 19:46 UTC (permalink / raw)
On Wednesday, October 30, 2013 8:03:11 PM UTC-4, Adam Beneschan wrote:
>
> Since FNV_Offset_Subtype doesn't have negative values, this would make it seem that FNV_Offset_Type'Size is more likely to be 31, 63, 127, etc., instead of 32, 64, 128, etc., if the Implementation Advice is followed. Or it could be something totally different depending on how FNV_Hash_Type'Last is defined. Those would play havoc with the definition of K_Offset. I'm not sure how to fix this portably.
>
I was considering this, but convinced myself that since everything is still a modulus type, the extra bit would be required for the entire range (i.e. if you need 32 bits to hold 0..2**32-1, then you still need all 32 bits for 1..2**32-1). I played around with a few different sizes, and GNAT seemed to give errors (and warnings) where needed, so I sort of let it lie. As long non-powers of two end up with errors and warnings, I guess that's the important part.
I also tried to do it using the actual 'Modulus, however, I ran into overflows for the larger numbers using 32-bit compilers, and couldn't figure out a slick way to do an lg statically.
Thank you for your response. I welcome any more suggestions or advice.
-sb
^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: FNV-1
2013-10-31 19:46 ` FNV-1 sbelmont700
@ 2013-10-31 20:35 ` Adam Beneschan
2013-10-31 22:00 ` FNV-1 Jeffrey Carter
0 siblings, 1 reply; 7+ messages in thread
From: Adam Beneschan @ 2013-10-31 20:35 UTC (permalink / raw)
On Thursday, October 31, 2013 12:46:06 PM UTC-7, sbelm...@gmail.com wrote:
> On Wednesday, October 30, 2013 8:03:11 PM UTC-4, Adam Beneschan wrote:
>
> >
>
> > Since FNV_Offset_Subtype doesn't have negative values, this would make it seem that FNV_Offset_Type'Size is more likely to be 31, 63, 127, etc., instead of 32, 64, 128, etc., if the Implementation Advice is followed. Or it could be something totally different depending on how FNV_Hash_Type'Last is defined. Those would play havoc with the definition of K_Offset. I'm not sure how to fix this portably.
>
> >
>
>
>
> I was considering this, but convinced myself that since everything is still a modulus type, the extra bit would be required for the entire range (i.e. if you need 32 bits to hold 0..2**32-1, then you still need all 32 bits for 1..2**32-1). I played around with a few different sizes, and GNAT seemed to give errors (and warnings) where needed, so I sort of let it lie. As long non-powers of two end up with errors and warnings, I guess that's the important part.
You're right, I missed that the base type is a modular type. (I've had lots of problems with 'Size of subtypes of signed integer types, which is why the code raised red flags with me ... but I forgot to check that. Sorry.)
-- Adam
^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: FNV-1
2013-10-31 20:35 ` FNV-1 Adam Beneschan
@ 2013-10-31 22:00 ` Jeffrey Carter
0 siblings, 0 replies; 7+ messages in thread
From: Jeffrey Carter @ 2013-10-31 22:00 UTC (permalink / raw)
On 10/31/2013 01:35 PM, Adam Beneschan wrote:
> On Thursday, October 31, 2013 12:46:06 PM UTC-7, sbelm...@gmail.com wrote:
>>
>> I was considering this, but convinced myself that since everything is still
>> a modulus type, the extra bit would be required for the entire range (i.e.
>> if you need 32 bits to hold 0..2**32-1, then you still need all 32 bits for
>> 1..2**32-1). I played around with a few different sizes, and GNAT seemed
>> to give errors (and warnings) where needed, so I sort of let it lie. As
>> long non-powers of two end up with errors and warnings, I guess that's the
>> important part.
>
> You're right, I missed that the base type is a modular type. (I've had lots
> of problems with 'Size of subtypes of signed integer types, which is why the
> code raised red flags with me ... but I forgot to check that. Sorry.)
I don't really see the point of these subtypes. They're not referenced once the
appropriate constant objects are defined. Possibly to cause an exception if the
"when others" branch is taken in one of the case expressions, but I'd think an
assertion would be clearer.
--
Jeff Carter
"[I]f we should ever separate, my little plum,
I want to give you one little bit of fatherly advice. ... Never
give a sucker an even break."
Poppy
97
^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: FNV-1
2013-10-30 23:31 FNV-1 sbelmont700
2013-10-31 0:03 ` FNV-1 Adam Beneschan
@ 2013-11-01 13:40 ` Georg Bauhaus
1 sibling, 0 replies; 7+ messages in thread
From: Georg Bauhaus @ 2013-11-01 13:40 UTC (permalink / raw)
On 31/10/13 00:31, sbelmont700@gmail.com wrote:
> Offset_512 : constant := 9659303129496669498009435400716310466090418745672637896108374329434462657994582932197716438449813051892206539805784495328239340083876191928701583869517785;
For cases where larger literals would hit parser limits,
or be in conflict with style guides, maybe some compiler
arithmetic prevents it, thus
Offset_512_Too : constant :=
96593031294966694980094354007163104660904187456726 * 10**(2*50 +4) +
37896108374329434462657994582932197716438449813051 * 10**(1*50 +4) +
892206539805784495328239340083876191928701583869517785;
private
Check : constant := Boolean'Pos -- compile time check
(case True is
when Offset_512 = Offset_512_Too => True,
when False => False);
The private part given as an example of assertions just when
they should be made compile time assertions.
^ permalink raw reply [flat|nested] 7+ messages in thread
end of thread, other threads:[~2013-11-01 13:40 UTC | newest]
Thread overview: 7+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2013-10-30 23:31 FNV-1 sbelmont700
2013-10-31 0:03 ` FNV-1 Adam Beneschan
2013-10-31 0:03 ` FNV-1 Adam Beneschan
2013-10-31 19:46 ` FNV-1 sbelmont700
2013-10-31 20:35 ` FNV-1 Adam Beneschan
2013-10-31 22:00 ` FNV-1 Jeffrey Carter
2013-11-01 13:40 ` FNV-1 Georg Bauhaus
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox