FNV-1

[sbelmont700@gmail.com]

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;