FNV-1

FNV-1

[sbelmont700]

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;

Re: FNV-1

[Adam Beneschan]

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
 

Re: FNV-1

[Adam Beneschan]

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

Re: FNV-1

[sbelmont700]

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

Re: FNV-1

[Adam Beneschan]

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

Re: FNV-1

[Jeffrey Carter]

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

Re: FNV-1

[Georg Bauhaus]

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.