~ This is part of the EuCrypt series. Start with Introducing EuCrypt. ~
The communication protocol for Eulora uses CRC32 as checksum for its packages and so I found myself looking in disbelief at the fact that GNAT imposes the use of Streams for something as simple as calculating the checksum of anything at all, no matter how small no matter what use, no matter what you might need or want or indeed find useful, no matter what. No matter! As usual, the forum quickly pointed me in the right direction - thank you ave1! - namely looking under the hood of course, in this case GNAT's own hood, the Systems.CRC32 package. Still, this package makes a whole dance of eating one single character at a time since it is written precisely to support the stream monstrosity on top rather than to support the user with what they might indeed need. Happily though, CRC32 is a very simple thing and absolutely easy to lift and package into 52 lines of code in the .adb file + 130 in the .ads file so 182 all in total1, comments and two types of input (string or raw array of octets) included. And since a CRC32 implementation is anyway likely to be useful outside of Eulora's communication protocol too, I'm adding it as a .vpatch on the EuCrypt tree where it seems to fit best at the moment. It's a lib on its own as "CRC32" when compiled via its own crc32.gpr or otherwise part of the aggregate EuCrypt project if you'd rather compile all of EuCrypt via its eucrypt.gpr.
My CRC32 lib uses the 0x04C11DB7 generator polynomial and a lookup table with pre-calculated values for faster execution. As Stanislav points out, implementing the actual division and living with the slow-down incurred is not a huge problem but at least for now I did not bother with it. The CRC32 lib provides as output 32 bits of checksum for either a string or an array of octets. At the moment at least I really don't see the need for anything more complicated than this - even the string-input method is more for the convenience of other/later uses than anything else. For my own current work on Eulora's protocol I expect to use CRC32 on arrays of octets directly.
The .vpatch adding CRC32 to EuCrypt and my signature for it are as usual on my Reference Code Shelf with additional links here for your convenience:
Specifically: 52 lines is the count of crc32.adb that does the work. The .ads file brings in another 130 lines that are mostly the lookup table with pre-calculated values. The .gpr file has another 61 lines and the restrict.adc another 80 lines. ↩
Comments feed: RSS 2.0
Nice work!
Thanks!
Hi Diana,
Nice implementation, easy to read!
I implemented a version that does the division (I use the same CRC32 type). This turned out to be a nice exercise; the message bits, as specificied for CRC32, have a reversed bit order (the xor at the start and end gave me some problems in the first implementation).
I do like the tricks that can be played with the shifts and the xors to get to the table implementation!
-- Function to calculate the a 32 bit CRC number. function crc32_of_string (message : in String) return CRC32 is A : CRC32 := 16#00_00_00_00#; R : CRC32 := 16#00_00_00_00#; D : constant CRC32 := 16#04_C1_1D_B7#; Zero : constant Character := Character'Val (0); -- Extend the string with 0 characters, needed to get all message bits -- into the division S : String := message & Zero & Zero & Zero & Zero; -- The Shift_Left instruction does not return the bit that was shifted -- We need a mask for this last bit -- Bits are counted from right to left, starting at 0 Bit31 : constant CRC32 := 16#80_00_00_00#; Bit1 : constant CRC32 := 16#01#; -- These functions need to be imported to get to the shift operators. -- (Specific for GNAT) function Shift_Left (Value : CRC32; Amount : Natural) return CRC32; pragma Import (Intrinsic, Shift_Left); function Shift_Right (Value : CRC32; Amount : Natural) return CRC32; pragma Import (Intrinsic, Shift_Right); begin -- Xor with 16#FF, the first 4 characters, same as a not for I in Integer range S'First .. S'First + 3 loop declare C : CRC32 := Character'Pos (S (I)); begin S (I) := Character'Val ((not C) and 16#FF#); end; end loop; -- The division, shift bits from the message unto the register -- If the left most bit on the register is 1 do an xor with the divisor for I in Integer range S'First .. S'Last loop declare C : CRC32 := Character'Pos (S (I)); begin for J in Integer range 1 .. 8 loop declare Bit31Set : constant Boolean := (Bit31 and A) = Bit31; BitSet : constant Boolean := (Bit1 and C) = Bit1; begin A := Shift_Left (A, 1); -- Shift right as the bit order is reversed in CRC 32 C := Shift_Right (C, 1); if BitSet then A := A or Bit1; end if; if Bit31Set then A := A xor D; end if; end; end loop; end; end loop; -- Reverse the bits in the result for I in Integer range 1 .. 32 loop declare Bit31Set : constant Boolean := (Bit31 and A) = Bit31; begin A := Shift_Left (A, 1); R := Shift_Right (R, 1); if Bit31Set then R := R or Bit31; end if; end; end loop; -- xor the result as per spec R := R xor 16#FF_FF_FF_FF#; return R; end crc32_of_string;Nice work ave1! Would you make it a .vpatch on top of the Eucrypt tree? I really think it should be in there as alternative, I don't see any reason why not. After all, user can choose which patches to press and/or whether to keep/use the whole or only parts of it.
No problem, as patch with a signature (OK, small problem as apparently the string concatenation triggered a restriction);
http://ave1.org/code/eucrypt/eucrypt_crc32_div.vpatch.ave1.sig
http://ave1.org/code/eucrypt/eucrypt_crc32_div.vpatch
Thank you! The eucrypt_crc32_divtronic.vpatch works great as alternative press path and I've signed it + mirrored it on my shelf: http://ossasepia.com/reference-code-shelf/#selection-429.0-443.46
[...] directly CRC32 to calculate the checksums as and when needed. The CRC32 is the previously published table-lookup CRC32 implementation from EuCrypt, now integrated into SMG Comms and slightly adapted to use the Octets type in [...]