Re: CRC in Ada?

[jmatthews@nova.wright.edu (Dr. John B. Matthews)]

Thanks to everyone who responded to my query about performing a
Cyclic Redundancy Check (CRC) in Ada.

David L Brown supplied an economical implementation using a 256 byte
lookup table, which I've incorporated in the code below.

Several correspondents expressed concern about efficient ways of
accessing a file to calculate it's CRC. Although systems vary and
there's no substitute for profiling actual code, much empirical
evidence suggests that it's often faster to process large blocks off
data rather than one element at a time. The familiar trade-off
between time and space dictates how big a block to process.

As suggested by Robert Dewar and others, Ada.Stream.Stream_IO.Read
provides a convenient, efficient way to read blocks of arbirary
size. In particular, the Read procedure reports the index of the
last buffer element read, thus allowing an arbitrary buffer size.

John
----------------------------------------------------------------
John B. Matthews, M.D.
jmatthews@nova.wright.edu; john_matthews@ccmail.dayton.saic.com
"Whom the gods would destroy, they first invite to program in C"

------------------------------------------------------------------
--|
--| CRC: Calculate 16 bit Cyclic Redunancy Check
--|
--| Author: John B. Matthews, Wright State University
--| Last Modified: March 15, 1997
--|
------------------------------------------------------------------
-- build: gnatmake crc

with Ada.Command_Line;
with Ada.Streams.Stream_IO; use type Ada.Streams.Stream_Element;
with Ada.Text_IO;

procedure CRC is

   package CLI renames Ada.Command_Line;
   package Text_IO renames Ada.Text_IO;
   package Stream_IO renames Ada.Streams.Stream_IO;

   -- assumes System.Storage_Unit is 8 bits/byte.
   subtype Byte is Ada.Streams.Stream_Element;
   subtype Byte_Array is Ada.Streams.Stream_Element_Array;
   subtype Byte_Index is Ada.Streams.Stream_Element_Offset;
   type Word is mod 2 ** 16; for Word'Size use 16;
   type Word_Array is array (Byte) of Word;

   Data  : Byte_Array (1 .. 8192); -- an 8K buffer
   File  : Stream_IO.File_Type;
   Last  : Byte_Index;
   Table : Word_Array;
   Check : Word := 0;

   --
   -- Generate the lookup table. Adapted from an
   -- implementation by David L Brown, comp.lang.ada
   --
   procedure Generate (P : in Word := 16#8408#) is
      V : Word;
   begin
      for B in Byte loop
         V := Word (B);
         for I in 1 .. 8 loop
            if (V and 1) = 0 then
               V := V / 2;
            else
               V := (V / 2) xor P;
            end if;
         end loop;
         Table (B) := V;
      end loop;
   end Generate;

   --
   -- Update the CRC value to account for Data.
   -- Implemented by David L Brown, comp.lang.ada
   --
   procedure Update (CRC : in out Word; Data : in Byte_Array) is
   begin
      for I in Data'Range loop
         CRC := (CRC / 16#100#) xor Table (Byte (CRC) xor Data (I));
      end loop;
   end Update;

begin

   if CLI.Argument_Count > 0 then
      Generate; -- the table
      for I in 1 .. CLI.Argument_Count loop
   
         Stream_IO.Open (File, Stream_IO.In_File, CLI.Argument(I));
         while not Stream_IO.End_Of_File (File) loop
            Stream_IO.Read (File, Data, Last);
            Update (Check, Data (Data'First .. Last));
         end loop;
         Stream_IO.Close (File);
   
         Text_IO.Put_Line (CLI.Argument(I) & Word'Image (Check));
      end loop;

   else
      Text_IO.Put_Line ("Usage: crc <filename>");
   end if;

end CRC;