------------------------------------------------------------------------------
------------------------------------------------------------------------------
-- This file is part of 'CRC32'                                             --
--                                                                          --
-- You do not have, nor can you ever acquire the right to use, copy or      --
-- distribute this software ; Should you use this software for any purpose, --
-- or copy and distribute it to anyone or in any manner, you are breaking   --
-- the laws of whatever soi-disant jurisdiction, and you promise to         --
-- continue doing so for the indefinite future. In any case, please         --
-- always : read and understand any software ; verify any PGP signatures    --
-- that you use - for any purpose.                                          --
--                                                                          --
-- See also http://trilema.com/2015/a-new-software-licensing-paradigm .     --
------------------------------------------------------------------------------
------------------------------------------------------------------------------

  -- CRC32 implementation
  -- S.MG, 2018
  
-- This implementation is based on bitwise operations (no table).
-- CRC32 is defined as a modulo 2 long division, these divisions can be
-- implemented as "long" divisions based on xor operations
-- (in the same way normal long divisions are based on subtractions).

-- The bits in a register (with bits R31 .. R0), are xored with the 
-- bits of the divisor.
-- The message is shifted into the register bit by bit at position r0
-- The register is shifted to make room for each message bit.
-- The bit that is shifted off the register (that was at r31) is used 
-- to determine if the xor operation is needed (if set then the xor 
-- operation is performed).
-- To be able to operate on each bit of the message, 32 zero bits are
-- appended.

-- The current implementation is an adapted version of the above algoritm 
-- and the adaptations may not always be obvious, below a short list of 
-- the adaptations;
-- (a) CRC32 has a reversed notion of the bit order in a byte (and integer)
--     the bits in each byte of the message are therefor shifted from 
--     the right (and not left as expected from the algorithm)
-- (b) At the end of the algorithm the bit order needs to be reversed. 
--     This step can be avoided by also shifting the register in a 
--     different direction and using a reversed divisor. 
--     (not implemented yet)
-- (c) Each message bit is shifted on the right side of the register and
--     step by step goes through to the right side of the register. Depending
--     on the bits before and the divisor it is xor-ed with a 1 or 0.
--     Per bit we have then this function; 
--       end-bit = message-bit xor d0 xor d1 xor .. xor d31
--     (where d0 .. d31 denote the bits of the divisor).
--     As an xor with 0 can always be added we can make this:
--       end-bit = message-bit xor d0 xor d1 xor .. xor d31 xor 0
--     Next, the xor operation is commutative,  
--     so the function can be rewritten as:
--        end_bit = 0 xor d0 xor d1 xor .. xor d31 xor message-bit
--     I.E. the message bit can be xor-ed with the register at the end
--     and then used to decide the next xor operation on the register.
--     (and shift the bit just used off the register)
--     Now, no appending of zero's is necessary and the initial value of
--     the register becomes a factor.
--     (CRC32 uses all ones, 16#ff_ff_ff_ff#)
-- (d) The implementation is constant time, no branching on the bits is
--     used 
--     (i.e. no if statements that depend on the value of the bits)

package body CRC32 is
  -- Implementation of CRC that uses mod 2 division
  function CRC ( S : in String ) return CRC32 is

    R    : CRC32              := 16#FF_FF_FF_FF#;

    begin

    for I in Integer range S'First .. S'Last loop
      declare
        C : CRC32 := Character'Pos (S (I));
      begin
        CRC_Step(C, R);
      end;
    end loop;

    R := Bits_Reverse(R);
    
    -- Xor the result as per spec
    R := R xor 16#FF_FF_FF_FF#;
    return R;
    
  end CRC;
  
  function CRC ( Data: in Octet_Array ) return CRC32 is

    R    : CRC32              := 16#FF_FF_FF_FF#;

    begin

    for I in Integer range Data'First .. Data'Last loop
      declare
        C : CRC32 := CRC32'Val( Data (I) );
      begin
        CRC_Step(C, R);
      end;
    end loop;

    R := Bits_Reverse(R);
    
    -- Xor the result as per spec
    R := R xor 16#FF_FF_FF_FF#;
    return R;
    
  end CRC;
  
  
  --function CRC( Data: in Octet_Array ) return CRC32;
  --end CRC;
  
  procedure CRC_Step(C : in out CRC32; R : in out CRC32) is
    D    : constant CRC32     := 16#04_C1_1D_B7#;
  begin
    for J in Integer range 1 .. 8 loop
      declare
        Bit31Set : CRC32 := 0;
        Bit1 : constant CRC32 := Rotate_Right(1 and C, 1);
      begin
        R := R xor Bit1;
        Bit31Set := Rotate_Left(Bit31 and R, 1);
        R := Shift_Left (R, 1);
        -- if the bit was set then bit31set == 1, else it is 0
        --   bit31set - 1 will do 1 -> 0 and 0 -> 16#ff_ff_ff_ff#
        -- not will then make the 
        --                       0 -> 16#ff_ff_ff_ff# 
        -- and the 16#ff_ff_ff_ff# -> 0.
        -- ie: (not (Bit31Set - 1)) does:
        --  1 --> 16#ff_ff_ff_ff#
        --  0 --> 0
        R := R xor ((not (Bit31Set - 1)) and D);
        
        -- Shift right as the bit order is reversed in CRC 32
        C := Shift_Right (C, 1);
        
      end;
    end loop;
  end CRC_Step;
  
  function Bits_Reverse(A : in CRC32) return CRC32 is
    R : CRC32 := 16#00_00_00_00#;
    B : CRC32 := A;
  begin
    for I in Integer range 1 .. 32 loop
      declare
        Bit : constant CRC32 := (1 and B);
      begin
        B := Shift_Right (B, 1);
        R := Shift_Left (R, 1);
        R := R or Bit;
      end;
    end loop;
    return R;
  end Bits_Reverse;
end CRC32;