-- © 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;
This page is http://www.cc.utah.edu/~nahaj/ada/crc/png_crc_table_generator.adb.html
© Copyright 2000 by John Halleck, All Rights Reserved.
This snapshot was last modified on August 11th, 2000
And the underlying file was last modified on August 5th, 2000