raw
eucrypt_crc32_div...    1 ------------------------------------------------------------------------------
eucrypt_crc32_div...    2 ------------------------------------------------------------------------------
eucrypt_crc32_div...    3 -- This file is part of 'CRC32'                                             --
eucrypt_crc32_div...    4 --                                                                          --
eucrypt_crc32_div...    5 -- You do not have, nor can you ever acquire the right to use, copy or      --
eucrypt_crc32_div...    6 -- distribute this software ; Should you use this software for any purpose, --
eucrypt_crc32_div...    7 -- or copy and distribute it to anyone or in any manner, you are breaking   --
eucrypt_crc32_div...    8 -- the laws of whatever soi-disant jurisdiction, and you promise to         --
eucrypt_crc32_div...    9 -- continue doing so for the indefinite future. In any case, please         --
eucrypt_crc32_div...   10 -- always : read and understand any software ; verify any PGP signatures    --
eucrypt_crc32_div...   11 -- that you use - for any purpose.                                          --
eucrypt_crc32_div...   12 --                                                                          --
eucrypt_crc32_div...   13 -- See also http://trilema.com/2015/a-new-software-licensing-paradigm .     --
eucrypt_crc32_div...   14 ------------------------------------------------------------------------------
eucrypt_crc32_div...   15 ------------------------------------------------------------------------------
eucrypt_crc32_div...   16 
eucrypt_crc32_div...   17   -- CRC32 implementation
eucrypt_crc32_div...   18   -- S.MG, 2018
eucrypt_crc32_div...   19   
eucrypt_crc32_div...   20 -- This implementation is based on bitwise operations (no table).
eucrypt_crc32_div...   21 -- CRC32 is defined as a modulo 2 long division, these divisions can be
eucrypt_crc32_div...   22 -- implemented as "long" divisions based on xor operations
eucrypt_crc32_div...   23 -- (in the same way normal long divisions are based on subtractions).
eucrypt_crc32_div...   24 
eucrypt_crc32_div...   25 -- The bits in a register (with bits R31 .. R0), are xored with the 
eucrypt_crc32_div...   26 -- bits of the divisor.
eucrypt_crc32_div...   27 -- The message is shifted into the register bit by bit at position r0
eucrypt_crc32_div...   28 -- The register is shifted to make room for each message bit.
eucrypt_crc32_div...   29 -- The bit that is shifted off the register (that was at r31) is used 
eucrypt_crc32_div...   30 -- to determine if the xor operation is needed (if set then the xor 
eucrypt_crc32_div...   31 -- operation is performed).
eucrypt_crc32_div...   32 -- To be able to operate on each bit of the message, 32 zero bits are
eucrypt_crc32_div...   33 -- appended.
eucrypt_crc32_div...   34 
eucrypt_crc32_div...   35 -- The current implementation is an adapted version of the above algoritm 
eucrypt_crc32_div...   36 -- and the adaptations may not always be obvious, below a short list of 
eucrypt_crc32_div...   37 -- the adaptations;
eucrypt_crc32_div...   38 -- (a) CRC32 has a reversed notion of the bit order in a byte (and integer)
eucrypt_crc32_div...   39 --     the bits in each byte of the message are therefor shifted from 
eucrypt_crc32_div...   40 --     the right (and not left as expected from the algorithm)
eucrypt_crc32_div...   41 -- (b) At the end of the algorithm the bit order needs to be reversed. 
eucrypt_crc32_div...   42 --     This step can be avoided by also shifting the register in a 
eucrypt_crc32_div...   43 --     different direction and using a reversed divisor. 
eucrypt_crc32_div...   44 --     (not implemented yet)
eucrypt_crc32_div...   45 -- (c) Each message bit is shifted on the right side of the register and
eucrypt_crc32_div...   46 --     step by step goes through to the right side of the register. Depending
eucrypt_crc32_div...   47 --     on the bits before and the divisor it is xor-ed with a 1 or 0.
eucrypt_crc32_div...   48 --     Per bit we have then this function; 
eucrypt_crc32_div...   49 --       end-bit = message-bit xor d0 xor d1 xor .. xor d31
eucrypt_crc32_div...   50 --     (where d0 .. d31 denote the bits of the divisor).
eucrypt_crc32_div...   51 --     As an xor with 0 can always be added we can make this:
eucrypt_crc32_div...   52 --       end-bit = message-bit xor d0 xor d1 xor .. xor d31 xor 0
eucrypt_crc32_div...   53 --     Next, the xor operation is commutative,  
eucrypt_crc32_div...   54 --     so the function can be rewritten as:
eucrypt_crc32_div...   55 --        end_bit = 0 xor d0 xor d1 xor .. xor d31 xor message-bit
eucrypt_crc32_div...   56 --     I.E. the message bit can be xor-ed with the register at the end
eucrypt_crc32_div...   57 --     and then used to decide the next xor operation on the register.
eucrypt_crc32_div...   58 --     (and shift the bit just used off the register)
eucrypt_crc32_div...   59 --     Now, no appending of zero's is necessary and the initial value of
eucrypt_crc32_div...   60 --     the register becomes a factor.
eucrypt_crc32_div...   61 --     (CRC32 uses all ones, 16#ff_ff_ff_ff#)
eucrypt_crc32_div...   62 -- (d) The implementation is constant time, no branching on the bits is
eucrypt_crc32_div...   63 --     used 
eucrypt_crc32_div...   64 --     (i.e. no if statements that depend on the value of the bits)
eucrypt_crc32_div...   65 
eucrypt_crc32_div...   66 package body CRC32 is
eucrypt_crc32_div...   67   -- Implementation of CRC that uses mod 2 division
eucrypt_crc32_div...   68   function CRC ( S : in String ) return CRC32 is
eucrypt_crc32_div...   69 
eucrypt_crc32_div...   70     R    : CRC32              := 16#FF_FF_FF_FF#;
eucrypt_crc32_div...   71 
eucrypt_crc32_div...   72     begin
eucrypt_crc32_div...   73 
eucrypt_crc32_div...   74     for I in Integer range S'First .. S'Last loop
eucrypt_crc32_div...   75       declare
eucrypt_crc32_div...   76         C : CRC32 := Character'Pos (S (I));
eucrypt_crc32_div...   77       begin
eucrypt_crc32_div...   78         CRC_Step(C, R);
eucrypt_crc32_div...   79       end;
eucrypt_crc32_div...   80     end loop;
eucrypt_crc32_div...   81 
eucrypt_crc32_div...   82     R := Bits_Reverse(R);
eucrypt_crc32_div...   83     
eucrypt_crc32_div...   84     -- Xor the result as per spec
eucrypt_crc32_div...   85     R := R xor 16#FF_FF_FF_FF#;
eucrypt_crc32_div...   86     return R;
eucrypt_crc32_div...   87     
eucrypt_crc32_div...   88   end CRC;
eucrypt_crc32_div...   89   
eucrypt_crc32_div...   90   function CRC ( Data: in Octet_Array ) return CRC32 is
eucrypt_crc32_div...   91 
eucrypt_crc32_div...   92     R    : CRC32              := 16#FF_FF_FF_FF#;
eucrypt_crc32_div...   93 
eucrypt_crc32_div...   94     begin
eucrypt_crc32_div...   95 
eucrypt_crc32_div...   96     for I in Integer range Data'First .. Data'Last loop
eucrypt_crc32_div...   97       declare
eucrypt_crc32_div...   98         C : CRC32 := CRC32'Val( Data (I) );
eucrypt_crc32_div...   99       begin
eucrypt_crc32_div...  100         CRC_Step(C, R);
eucrypt_crc32_div...  101       end;
eucrypt_crc32_div...  102     end loop;
eucrypt_crc32_div...  103 
eucrypt_crc32_div...  104     R := Bits_Reverse(R);
eucrypt_crc32_div...  105     
eucrypt_crc32_div...  106     -- Xor the result as per spec
eucrypt_crc32_div...  107     R := R xor 16#FF_FF_FF_FF#;
eucrypt_crc32_div...  108     return R;
eucrypt_crc32_div...  109     
eucrypt_crc32_div...  110   end CRC;
eucrypt_crc32_div...  111   
eucrypt_crc32_div...  112   
eucrypt_crc32_div...  113   --function CRC( Data: in Octet_Array ) return CRC32;
eucrypt_crc32_div...  114   --end CRC;
eucrypt_crc32_div...  115   
eucrypt_crc32_div...  116   procedure CRC_Step(C : in out CRC32; R : in out CRC32) is
eucrypt_crc32_div...  117     D    : constant CRC32     := 16#04_C1_1D_B7#;
eucrypt_crc32_div...  118   begin
eucrypt_crc32_div...  119     for J in Integer range 1 .. 8 loop
eucrypt_crc32_div...  120       declare
eucrypt_crc32_div...  121         Bit31Set : CRC32 := 0;
eucrypt_crc32_div...  122         Bit1 : constant CRC32 := Rotate_Right(1 and C, 1);
eucrypt_crc32_div...  123       begin
eucrypt_crc32_div...  124         R := R xor Bit1;
eucrypt_crc32_div...  125         Bit31Set := Rotate_Left(Bit31 and R, 1);
eucrypt_crc32_div...  126         R := Shift_Left (R, 1);
eucrypt_crc32_div...  127         -- if the bit was set then bit31set == 1, else it is 0
eucrypt_crc32_div...  128         --   bit31set - 1 will do 1 -> 0 and 0 -> 16#ff_ff_ff_ff#
eucrypt_crc32_div...  129         -- not will then make the 
eucrypt_crc32_div...  130         --                       0 -> 16#ff_ff_ff_ff# 
eucrypt_crc32_div...  131         -- and the 16#ff_ff_ff_ff# -> 0.
eucrypt_crc32_div...  132         -- ie: (not (Bit31Set - 1)) does:
eucrypt_crc32_div...  133         --  1 --> 16#ff_ff_ff_ff#
eucrypt_crc32_div...  134         --  0 --> 0
eucrypt_crc32_div...  135         R := R xor ((not (Bit31Set - 1)) and D);
eucrypt_crc32_div...  136         
eucrypt_crc32_div...  137         -- Shift right as the bit order is reversed in CRC 32
eucrypt_crc32_div...  138         C := Shift_Right (C, 1);
eucrypt_crc32_div...  139         
eucrypt_crc32_div...  140       end;
eucrypt_crc32_div...  141     end loop;
eucrypt_crc32_div...  142   end CRC_Step;
eucrypt_crc32_div...  143   
eucrypt_crc32_div...  144   function Bits_Reverse(A : in CRC32) return CRC32 is
eucrypt_crc32_div...  145     R : CRC32 := 16#00_00_00_00#;
eucrypt_crc32_div...  146     B : CRC32 := A;
eucrypt_crc32_div...  147   begin
eucrypt_crc32_div...  148     for I in Integer range 1 .. 32 loop
eucrypt_crc32_div...  149       declare
eucrypt_crc32_div...  150         Bit : constant CRC32 := (1 and B);
eucrypt_crc32_div...  151       begin
eucrypt_crc32_div...  152         B := Shift_Right (B, 1);
eucrypt_crc32_div...  153         R := Shift_Left (R, 1);
eucrypt_crc32_div...  154         R := R or Bit;
eucrypt_crc32_div...  155       end;
eucrypt_crc32_div...  156     end loop;
eucrypt_crc32_div...  157     return R;
eucrypt_crc32_div...  158   end Bits_Reverse;
eucrypt_crc32_div...  159 end CRC32;
eucrypt_crc32_div...  160