--  (C) Copyright 2000 by John Halleck, All Rights Reserved.
--  Generate the lookup table that PNG's CRC routine can use for faster
--  computation.
--  PNG's CRC.  It is defined by ISO 3309 [ISO-3309] or ITU-T V.42 [ITU-T-V42].
--  It uses the CRC polynomial:
--       x^32 + x^26 + x^23 + x^22 + x^16
--     + x^12 + x^11 + x^10 + x^8 + x^7 + x^5 + x^4 + x^2 + x^1 + x^0


with  Interfaces; use  Interfaces; -- We need bit rotate instructions.
with Ada.Text_IO; use Ada.Text_IO; -- And to write the output.

procedure PNG_CRC_Table_Generator is

   package Output_Integers is new Ada.Text_IO.Modular_IO (Unsigned_32);
   use Output_Integers;

   CRC_Polynomial : constant Unsigned_32 := 16#DB710641#;

   --  There are many C examples of this code around, and they include the
   --  magic constant EDB88320 without comment. This constant has my vote for
   --  obscure constant of the year.  It is not the CRC polynomical.
   --  Just because it bugs me to see it undocumented, here is the derivation.
   --  The CRC polynomial is stated in the standard to be::
   --  x^32+x^26+x^23+x^22+x^16+x^12+x^11+x^10+x^8+x^7+x^5+x^4+x^2+x+1
   --  If you set a bit for each non-zero x exponent, NUMBERING FROM THE LEFT,
   --  STARTING AT 1 (as hardware designers used to do in the old days before
   --  most current programmers were born) you'd get:
   --     1101 1011 0111 0001 0000 0110 0100 0001 (DB710641)
   --  This *IS* the CRC polynomial.
   --  But C programmers want to squeze the last cycle out of their
   --  code, so instead of XORing with this obvious constant, and then
   --  shifting, and setting the high order bit, they shift, and then XOR with
   --  a shifted constant with the high order bit set..
   --  So the C programmer needs the real CRC constant shifted right one bit
   --  with the high order bit set (since CRC's shift in one bits) so what they
   --  use is:
   --     1110 1101 1011 1000 1000 0011 0010 0000 (EDB88320)
   --  Which is the constant you find in the reference C code.

   --  Since this table generation is done ONCE PER CRC you implement, and
   --  the table generated is what is used in the final program, and not this
   --  code, I'll spend the extra 256 cycles and do this generation in the
   --  manner that has the clearest derivation, and clearest form for anyone
   --  who will be dealing with other 32 bit CRC's.


   type CRC_Array is array (Unsigned_8) of Unsigned_32;
   Table : CRC_Array;

   CRC : Unsigned_32;

   Output : File_Type;

begin

   --  Generate the actual table.
   for I in Table'Range loop
      CRC := Unsigned_32 (I);

      --  All the C reference code I've seen has a loop equivalent to:
      --
      --     for J in 1 .. 8 loop --  For each bit in the byte.
      --        if 0 /= (CRC and 1) then
      --           CRC := Shift_Right (CRC, 1) xor 16#EDB88320#;
      --        else
      --           CRC := Shift_Right (CRC, 1);
      --        end if;
      --     end loop;
      --
      --  But you can use a constant for the Polynomical that is
      --  obvious (DB710641, see above) if one does this the way
      --  that Hardware intended, by recoding it as:

      for J in 1 .. 8 loop -- For each bit in a byte...
         if 0 /= (CRC and 1) then
            CRC := Shift_Right (CRC xor CRC_Polynomial, 1) or 16#80000000#;
         else
            CRC := Shift_Right (CRC, 1);
         end if;
      end loop;

      Table (I) := CRC;
   end loop;

   -----------------------------------------------------------------------
   --  Now that we have the table that a table driven CRC will need, let's
   --  write the package that defines exactly that table...

   --  This is the actual file the unit goes in. How it relates to the unit
   --  name depends on what compiler you use.  (Too bad this isn't standardized
   Create (Output, Out_File, "png_crc_table.ads");

   --  Preamble:
   Put_Line (Output,
      "--  (C) Copyright 2000 by John Halleck, All Rights Reserved");
   Put_Line (Output,
      "--  This is the table that PNG_CRC can use for faster computation");
   Put_Line (Output,
      "--  *** THIS IS MECHANICALLY GENERATED CODE GENERATED BY");
   Put_Line (Output,
      "--  *** THE ROUTINE PNG_CRC_Table_Generator given the CRC polynomial:");

   --  Obviously, if you pick a different CRC polynomial, you'll have to change
   --  this line.
   Put_Line (Output,
      "--  x^32+x^26+x^23+x^22+x^16+x^12+x^11+x^10+x^8+x^7+x^5+x^4+x^2+x+1");

   New_Line (Output);

   Put_Line (Output,
      "with Interfaces; use Interfaces; -- We need Unsigned_8 and Unsigned_32"
   );
   New_Line (Output);

   --  Here, and at the line that puts out the end statement, is where the name
   --  of the actual table package goes.
   Put_Line (Output,
      "package PNG_CRC_Table is");
   Put_Line (Output,
      "   pragma Pure (PNG_CRC_Table);");


   New_Line (Output);

   Put_Line (Output,
      "   type CRC_Table is array (Unsigned_8) of Unsigned_32;");
   Put_Line (Output,
      "   Table : constant CRC_Table := (");

   --  Actual table.
   for I in 0 .. Unsigned_8 (255) loop
      if I mod 4 = 0 then
         Put (Output, "      ");
      end if;
      Put (Output, Item => Table (I), Width => 12, Base => 16);
      if I /= 255 then
         Put (Output, ",");
      end if;
      if I mod 4 = 3 then
         New_Line (Output);
      else
         Put (Output, " ");
      end if;
   end loop;

   --  Postamble:
   Put_Line (Output,
      "   );");
   New_Line (Output);
   Put_Line (Output,
      "end PNG_CRC_Table;");
   Close (Output);

end PNG_CRC_Table_Generator;