Hi, to those who like that kind of exercise, I was asked to "“use modular types to implement the calculation of cyclic redundancy checks”. I didn’t know what it was so I checked it out:
Sender Side (Generation of Encoded Data from Data and Generator Polynomial (or Key)):
The binary data is first augmented by adding k-1 zeros in the end of the data
Use modulo-2 binary division to divide binary data by the key and store remainder of division.
Append the remainder at the end of the data to form the encoded data and send the same
I thought I would do as if receiving a message from the network, a file or stream, containing the remainder then the message. But I want to make it independent of the size of the message (say, a String). I can get the number of bits needed for a particular remainder value with Integer(Float’Ceiling(log2 x)), but how to know that for the biggest remainder possible, for a given key and given size of message ? For a k bits divisor and a m bits message, am I right that the highest possible remainder needs m-k bits at minima ?
Then I’ll view the encoded message into a bit array, check the validity (by the way, why does (remainder & message) mod divisor always equals to 0 ?), then from the encoded message’s size, deduce the number of bits of the remainder, and convert the rest into a string of the right size. I hope i wasn’t too unclear. Math-wise I’m flying by the seat of my pants here. And the other other questions are so much worse:
Implement Euler’s method using access-to-subprogram types.
I’ve never done a single differential equations In my life. Is it advised to skip this kind of thing for now ?
Why do you torture yourself on New Year’s Eve?
Regarding CRC see
it explains the algorithm in details and gives a numeric example and a snippet of code in ugly Python.
And finally look at GNAT.CRC32 which has the exercise ready.
Because as a proper geek, my life is miserable and my computer the closest thing I have to a partner, what can I say ?!
Oh. I get it now. Of course a n-bit divisor would produce a n-1 bits remainder. And either I send the remainder and (message + remainder) to extract the message, in case I do the division without padding, or I divide with the padding, send just that remainder appended and just remove the last n-1 bits to get the message. Ok, thanks.
You tell if I’m in the right track. I’m not interested in already available solution, I wanna get it right myself. Normally I would have converted the message to a modular type of same number of bits then do the modulo operation, but the message is a 80-letters long String. I can’t make a 80 octets-long signed or unsigned integer type !
First off, convert divisor and message in arrays of bits.
To do what the division as done below, I must know the number of significant digits of the divisor, which is to say the position of the last non-zero bit of higher weight, relative to the unit bit / bit of lowest weight. I could iterate over the array but I am not sure if array (1) will be the highest weight bit, or lowest. It seems to behave intuitively array (1) = lowest bit of first character but I want something portable.
This must lead you the conclusion that you do not need the whole string in order to calculate remainder. You can update the remainder by processing chunks of of the string one by one. In your case the chunk is a single character or a stream element or four of them to make it 32-bit long. You must pad the string at the end with zero octets and that is all.
Like this ? It compiles and works, in the sense that all type lenght and range are respected. No complaints about differing sizes during conversions either.
But normally, you pad the whole thing with zero then take the remainder, and append it to the message’s bits. I did not understand what you want me to do with the padding part. When do I pad what, only the final bit array, or each chunk of string ? Sorry to be dense, what’s obvious to you usually isn’t for me
package CRC is
Divisor : constant := 106548;
subtype Message is String(1..80);
type Bit_array is array (Positive range 1..<>) of Boolean with Pack;
subtype Encoded_Bit_array is Bit_array (1..Message'Length*8+16);
function Encode (M: Message) return Encoded_Bit_array;
end CRC;
package body CRC is
subtype Message_chunk is String (1..4);
subtype Message_Bit_array is Bit_array (1..8*Message'Length);
type Temporary_Result is mod 2**32;
function Convert is new Ada.Unchecked_Conversion (Message_chunk, Temporary_Result);
subtype Message_Chunk_array is Bit_array (1..4*8);
function Convert is new Ada.Unchecked_Conversion (Message_Chunk_array, Temporary_Result);
function Encode (M: Message) return Encoded_Bit_array is
type SumType is mod 2**16;
Sum : Natural := 0;
function Convert is new Ada.Unchecked_Conversion (Message, Message_Bit_array);
subtype octets_chunk is Bit_array (1..16);
function Convert is new Ada.Unchecked_Conversion (Sumtype, octets_chunk);
begin
for I in 1..Message'Length/4 loop
Sum := @ + Temporary_Result'Pos(Convert (M (4*(I-1)+1..4*I))) mod Divisor;
end loop;
return Convert (M) & Convert (Sumtype(Sum mod Divisor));
end Encode;
end CRC;
Ok, but the message is 80 character long, so it’s not an issue.
So, let’s say the string is 80 characters. I divide it in 20 slices, and convert them in as many 32-bit unsigned integers. I add the remainder of each 20 divisions, then take the remainder of that sum.
Then I convert the original message into a 80*8 bit array, convert the remainder sum in a bit array too, and append it to the message. Is that it ?
Are there useless things in my code ?
?!
