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