Eternity2 Solver

From Hamsterworks Wiki!

Jump to: navigation, search

This FPGA Project was completed in February 2014.

The Eternity II puzzle (http://en.wikipedia.org/wiki/Eternity_II_puzzle) is commercial pattern matching puzzle that was marketed in 2007, with the prize of a $1,000,000 for the first correct solution received before the end of 2010.

Although a lot of people worked on it, nobody ever claimed the prize. I did explore the puzzle for quite a long while using various techniques. and always thought that this style of problem was not very well suited to FPGA, as the feedback between what tiles can be placed on the board and what tiles are available to go in the next square is very tight and minimises the opportunities for fine grained parallel execution - it is easier just to start a second instance of the software running on a different CPU core.

In addition, the official puzzle has 'clues' that require a given tile placed close to the centre of the board, giving awkward constraints that require special handling.

Contents

My approach

However, it recently occurred to me that if you approach the problem in a special way a lot of the 'special cases' disappear. These special ways are:

  • No clues pieces are allowed - however these can be less efficiently implemented as edge-level constraints.
  • The edges are treated as pattern 0 - I don't distinguish between corners, edges and centre tiles.
  • Only a left to right, top to bottom fill order is used.

This ensures that all tile selections operations are constrained by the patterns at the top and right edges. The far right-hand pattern is implemented by rejecting any candidate tiles which do not have pattern 0 on the right-hand edge. Ditto for the bottom-most edge.

If anybody is interested in following up on this, send me an email because there is quite a bit to pre-processing the tile set and optimizing resource usage. There is also some tricks to setting the project up so that each thread is working on a different sub-tree of the search space.


Performance

It takes 199 seconds for a single thread running on the FPGA to do what takes a single 3.5 GHz Intel i7 core 34 seconds to compute, using an very optimised program.

That makes a Spartan 6 LX9 where it can run 8 threads equivalent to about a Core i7 core.

Source

solver.vhd

Here's the source for the solver.

----------------------------------------------------------------------------------
-- Engineer: Mike Field <hamster@snap.net.nz>
-- 
-- Module Name: Solver - Behavioral 
--
-- Description: VHDL backtracker for solving Eternity II-like tiling puzzles
--
----------------------------------------------------------------------------------
library IEEE;
use IEEE.STD_LOGIC_1164.ALL;
use IEEE.NUMERIC_STD.ALL;

entity solver is

    Generic ( index_bits   : natural;
              pattern_bits : natural;
              tile_bits    : natural;
              threads_active  : std_logic_vector(3 downto 0));
    Port ( clk : in  STD_LOGIC;
           busy        : out  STD_LOGIC;
           
           bus_offer_in    : IN std_logic;
           data_enable_in  : IN  std_logic;
		     data_in         : IN  std_logic_vector(7 downto 0);
      
           bus_offer_out   : OUT std_logic := '0';
		     data_enable_out : OUT std_logic := '0';
		     data_out        : OUT std_logic_vector(7 downto 0) := (others => '0');
           
           tile_lookup_addr : out STD_LOGIC_VECTOR(pattern_bits*2+index_bits-1 DOWNTO 0);
           tile_lookup_data : in  STD_LOGIC_VECTOR(pattern_bits*2+tile_bits-1 DOWNTO 0)
           
        );
end solver;

architecture Behavioral of solver is

   constant x_max   : unsigned(3 downto 0) := to_unsigned(15,4);
   constant y_max   : unsigned(3 downto 0) := to_unsigned(15,4);
   constant x_limit : unsigned(3 downto 0) := to_unsigned(15,4);
   constant y_limit : unsigned(3 downto 0) := to_unsigned(15,4);

	COMPONENT dual_port_ram
   Generic(addr_width : natural;
           data_width : natural;
           ram_type   : string := "block");
   PORT(
		clk          : IN  std_logic;
		write_addr   : IN  std_logic_vector(addr_width-1 downto 0);
		write_enable : IN  std_logic;
		write_d      : IN  std_logic_vector(data_width-1 downto 0);
		read_addr    : IN  std_logic_vector(addr_width-1 downto 0);          
		read_d       : OUT std_logic_vector(data_width-1 downto 0)
		);
	END COMPONENT;
      

   --------------------------------------------------------------------------
   -- signals to look up and break out the next tile to be used at this level
   --------------------------------------------------------------------------
   signal tile_sequence        : STD_LOGIC_VECTOR(tile_bits-1 DOWNTO 0);
   signal tile_pattern_right   : STD_LOGIC_VECTOR(pattern_bits-1 DOWNTO 0);
   signal tile_pattern_bottom  : STD_LOGIC_VECTOR(pattern_bits-1 DOWNTO 0);
   constant END_OF_LIST        : STD_LOGIC_VECTOR(pattern_bits-1 DOWNTO 0) := (others =>'1');
   constant EDGE_BORDER        : STD_LOGIC_VECTOR(pattern_bits-1 DOWNTO 0) := (others =>'0');

   type stage0_rec is record
      skip            : std_logic_vector(7 downto 0);
      instance        : std_logic_vector(1 downto 0);
      active          : std_logic;
      dumping         : std_logic;
      pattern_left    : std_logic_vector(pattern_bits-1 downto 0);
      lookup_index    : unsigned(index_bits-1 downto 0);
      cell_index      : unsigned(7 downto 0);
      stack_pointer   : unsigned(7 downto 0);
      data_enable     : std_logic;
      data            : std_logic_vector(tile_bits-1 downto 0);
   end record;
   
   type stage1_rec is record
      skip            : std_logic_vector(7 downto 0);
      instance        : std_logic_vector(1 downto 0);
      active          : std_logic;
      dumping         : std_logic;
      pattern_left    : std_logic_vector(pattern_bits-1 downto 0);
      lookup_index    : unsigned(index_bits-1 downto 0);
      cell_index      : unsigned(7 downto 0);
      stack_pointer   : unsigned(7 downto 0);
   end record;   

   type stage2_rec is record
      skip             : std_logic_vector(7 downto 0);
      instance         : std_logic_vector(1 downto 0);
      active           : std_logic;
      dumping          : std_logic;
      pattern_left     : std_logic_vector(pattern_bits-1 downto 0);
      lookup_index     : unsigned(index_bits-1 downto 0);
      cell_index       : unsigned(7 downto 0);
      stack_pointer    : unsigned(7 downto 0);
      candidate_tile   : std_logic_vector(tile_bits-1 downto 0);
      candidate_right  : std_logic_vector(pattern_bits-1 downto 0);
      candidate_bottom : std_logic_vector(pattern_bits-1 downto 0);
   end record;
   
   type action_enum is (action_advance, action_place, action_backtrack,action_idle);   
   type stage3_rec is record
      skip             : std_logic_vector(7 downto 0);
      instance         : std_logic_vector(1 downto 0);
      active           : std_logic;
      dumping          : std_logic;
      pattern_left     : std_logic_vector(pattern_bits-1 downto 0);
      lookup_index     : unsigned(index_bits-1 downto 0);
      cell_index       : unsigned(7 downto 0);
      stack_pointer    : unsigned(7 downto 0);
      action           : action_enum;
      candidate_tile   : std_logic_vector(tile_bits-1 downto 0);
      candidate_right  : std_logic_vector(pattern_bits-1 downto 0);
      candidate_bottom : std_logic_vector(pattern_bits-1 downto 0);
      bus_offer_out    : std_logic;
      data_enable      : std_logic;
   end record;

   ------------------------------------------------------
   -- Signals used to to keep track of of the patterns on
   -- the top and bottom of the cells
   ------------------------------------------------------
   signal tb_write_addr   : STD_LOGIC_VECTOR(2+8-1 DOWNTO 0);
   signal tb_write_enable : STD_LOGIC := '0';
   signal tb_write_data   : STD_LOGIC_VECTOR(pattern_bits-1 DOWNTO 0);
   signal tb_read_addr    : STD_LOGIC_VECTOR(2+8-1 DOWNTO 0);
   signal tb_read_data    : STD_LOGIC_VECTOR(pattern_bits-1 DOWNTO 0);


   signal placed_write_addr   : std_logic_vector(2+tile_bits-1 downto 0);
   signal placed_write_enable : std_logic;
   signal placed_write_d      : std_logic_vector(0 downto 0);
   signal placed_read_addr    : std_logic_vector(2+tile_bits-1 downto 0);
   signal placed_read_d       : std_logic_vector(0 downto 0);

   signal stack_write_addr    : std_logic_vector(2+8-1 downto 0) := (others => '0');
   signal stack_write_enable  : std_logic := '0';
   signal stack_write_data    : std_logic_vector(index_bits+pattern_bits+tile_bits-1 downto 0) := (others => '0');
   signal stack_read_addr     : std_logic_vector(2+8-1 downto 0) := (others => '0');
   signal stack_read_data     : std_logic_vector(index_bits+pattern_bits+tile_bits-1 downto 0) := (others => '0');

   signal stage0 : stage0_rec := ("00000000","11",threads_active(3),'0',(others=>'0'),to_unsigned(0,index_bits), to_unsigned(0,8), to_unsigned(0,8),'0',(others=>'0'));
   signal stage1 : stage1_rec := ("00000000","10",threads_active(2),'0',(others=>'0'),to_unsigned(0,index_bits), to_unsigned(0,8), to_unsigned(0,8));
   signal stage2 : stage2_rec := ("00000000","01",threads_active(1),'0',(others=>'0'),to_unsigned(0,index_bits), to_unsigned(0,8), to_unsigned(0,8),(others=>'0'),(others=>'0'),(others=>'0'));
   signal stage3 : stage3_rec := ("00000000","00",threads_active(0),'0',(others=>'0'),to_unsigned(0,index_bits), to_unsigned(0,8), to_unsigned(0,8),action_idle,(others=>'0'),(others=>'0'),(others=>'0'),'0','0');

   signal next_stage0 : stage0_rec;
   signal next_stage1 : stage1_rec;
   signal next_stage2 : stage2_rec;
   signal next_stage3 : stage3_rec;

   
begin
   busy            <= stage0.active OR stage1.active OR stage2.active OR stage3.active;
   data_enable_out <= stage0.data_enable;
   bus_offer_out   <= stage3.bus_offer_out;
   data_out(tile_bits-1 downto 0) <= stage0.data;
   
   

   ------------------------------------------------------
   -- Break out the data from the tile information lookup
   ------------------------------------------------------
   tile_sequence       <= tile_lookup_data(tile_bits-1 downto  0);
   tile_pattern_right  <= tile_lookup_data(tile_bits+pattern_bits-1 downto  tile_bits);
   tile_pattern_bottom <= tile_lookup_data(tile_bits+pattern_bits*2-1 downto tile_bits+pattern_bits);
 
the_stack : dual_port_ram
  GENERIC MAP (
      data_width => index_bits+pattern_bits+tile_bits,
      addr_width => 8+2,
      ram_type   => "block"
  ) PORT MAP (
    clk  => clk,
    write_enable => stack_write_enable,
    write_addr   => stack_write_addr,
    write_d      => stack_write_data,
    read_addr    => stack_read_addr,
    read_d       => stack_read_data
  );
 
placed : dual_port_ram
  GENERIC MAP (
      data_width => 1,
      addr_width => 2+8,
      ram_type   => "block"
  ) PORT MAP (
    clk  => clk,
    write_addr   => placed_write_addr,
    write_enable => placed_write_enable,
    write_d      => placed_write_d,
    read_addr    => placed_read_addr,
    read_d       => placed_read_d
  );
  
top_bottom_edges : dual_port_ram
   GENERIC MAP (
      data_width => pattern_bits,
      addr_width => 2+8,
      ram_type   => "block"
   ) PORT MAP (
    clk  => clk, 
    write_enable => tb_write_enable, 
    write_addr   => tb_write_addr, 
    write_d      => tb_write_data,
    read_addr    => tb_read_addr,
    read_d       => tb_read_data
  );

   
process(stage0, tb_read_data)
   ------------------------------------------------
   -- Finishing: Looking up the top and bottom patterns
   --
   -- Starting : Looking up a matching tile
   --
   -- Status : Ready for testing   
   ---------------------------------------------------
   begin
      -- set up memory accesses
--      tile_addra(12 downto 4) <= std_logic_vector(unsigned(stage0.pattern_left & "0000") + unsigned("00" & stage0.pattern_left & "00") + unsigned("0000"& tb_read_data));
      tile_lookup_addr((pattern_bits*2+index_bits)-1 downto index_bits) <= stage0.pattern_left & tb_read_data;
      tile_lookup_addr(index_bits-1 downto 0)  <= std_logic_vector(stage0.lookup_index);

      -- build state for next stage
      next_stage1.skip           <= stage0.skip;
      next_stage1.instance       <= stage0.instance;
      next_stage1.active         <= stage0.active;
      next_stage1.dumping        <= stage0.dumping;
      next_stage1.pattern_left   <= stage0.pattern_left;
      next_stage1.lookup_index   <= stage0.lookup_index;
      next_stage1.cell_index     <= stage0.cell_index;
      next_stage1.stack_pointer  <= stage0.stack_pointer;
   end process;

process(stage1,tile_sequence, tile_pattern_right, tile_pattern_bottom)
   ------------------------------------------------
   -- Finishing : Looking up a matching tile 
   --
   -- Starting  : Looking to see if it is placed
   --
   -- Status : Ready for testing   
   ---------------------------------------------------
   begin
      -- set up memory accesses
      placed_read_addr <= std_logic_vector(stage1.instance) & tile_sequence;

      -- build state for next stage
      next_stage2.skip             <= stage1.skip;
      next_stage2.instance         <= stage1.instance;
      next_stage2.active           <= stage1.active;
      next_stage2.dumping          <= stage1.dumping;
      next_stage2.pattern_left     <= stage1.pattern_left;
      next_stage2.lookup_index     <= stage1.lookup_index;
      next_stage2.cell_index       <= stage1.cell_index;
      next_stage2.stack_pointer    <= stage1.stack_pointer;
      next_stage2.candidate_tile   <= tile_sequence;
      next_stage2.candidate_right  <= tile_pattern_right;
      next_stage2.candidate_bottom <= tile_pattern_bottom;
   end process;

process(stage2, placed_read_d )
   ------------------------------------------------
   -- Finishing : Looking to see if it is placed
   --
   -- Starting : Deciding what to do
   ---------------------------------------------------
   begin
      stack_read_addr <= std_logic_vector(stage2.instance) & std_logic_vector(stage2.stack_pointer-1);

      -- build state for next stage
      next_stage3.skip             <= "0" & stage2.skip(stage3.skip'high downto 1);
      next_stage3.instance         <= stage2.instance;
      next_stage3.active           <= stage2.active;
      next_stage3.dumping          <= stage2.dumping;
      next_stage3.pattern_left     <= stage2.pattern_left;
      next_stage3.lookup_index     <= stage2.lookup_index;
      next_stage3.cell_index       <= stage2.cell_index;
      next_stage3.stack_pointer    <= stage2.stack_pointer;
      next_stage3.candidate_tile   <= stage2.candidate_tile;
      next_stage3.candidate_right  <= stage2.candidate_right;
      next_stage3.candidate_bottom <= stage2.candidate_bottom;
      next_stage3.bus_offer_out    <= bus_offer_in;
      next_stage3.data_enable      <= '0';
               
      if stage2.active = '0' then
         next_stage3.action <= action_idle;
         if stage2.dumping = '1' then
            if (x_max = "1111" and y_max = "1111" and stage2.stack_pointer = 0) or
               ((x_max /= "1111" or y_max /= "1111") and stage2.stack_pointer = (x_max+1)*(y_max+1))  then
               next_stage3.action  <= action_backtrack;
               next_stage3.dumping <= '0';
               next_stage3.active  <= '1';
            end if;
            next_stage3.data_enable <= '1';
         end if;
      elsif stage2.candidate_right = END_OF_LIST and stage2.candidate_bottom = END_OF_LIST then
         -----------------------------------------------------------------
         -- Have we run to the end of our options for the current level?
         -- And are we completely finished (backtracking at level 0?)
         -----------------------------------------------------------------
         next_stage3.action <= action_backtrack;
         if stage2.cell_index = 0 then
            next_stage3.active <= '0';
         end if;
      elsif stage2.candidate_bottom = EDGE_BORDER and stage2.cell_index(7 downto 4) /= y_limit then
         -- Are we looking at putting an edge on the bottom where one shouldn't be
         next_stage3.action <= action_advance;
      elsif stage2.candidate_right  = EDGE_BORDER and stage2.cell_index(3 downto 0) /= x_limit then
         -- Are we looking at putting an edge on the right where one shouldn't be
         next_stage3.action <= action_advance;
      elsif stage2.candidate_bottom /= EDGE_BORDER and stage2.cell_index(7 downto 4) = y_limit then
         -- Do we need to be at putting an edge on the bottom
         next_stage3.action <= action_advance;
      elsif stage2.candidate_right  /= EDGE_BORDER and stage2.cell_index(3 downto 0) = x_limit then
         -- Do we need to putting an edge on the right?
         next_stage3.action <= action_advance;
      elsif  placed_read_d = "0" and stage2.skip(0) = '0' then
         -----------------------------------------------------------------
         -- The tile we are trying to place is valid, and there are tiles 
         -- to test at the next level down, and the tile wasn't in use, 
         -- So now successfully placed!
         -- 
         -- The settings of "skip" are how the four different cores can be
         -- set to run different configurations
         -----------------------------------------------------------------
         next_stage3.action <= action_place;
         if stage2.cell_index(7 downto 4) = y_max and stage2.cell_index(3 downto 0) = x_max then
               if bus_offer_in = '1' then
                  next_stage3.bus_offer_out <= '0';
                  next_stage3.dumping       <= '1';
               else
                  next_stage3.action <= action_idle;
               end if;
               next_stage3.bus_offer_out <= '0';
               stack_read_addr           <= std_logic_vector(stage2.instance) & "00000000";
         end if;
      else
         ------------------------------------------------
         -- Move on to the next tile at the current level
         ------------------------------------------------
         next_stage3.action <= action_advance;
      end if;

   end process;

process(stage3,stack_read_data)
   begin
      -- set up memory accesses
      tb_read_addr     <= stage3.instance & std_logic_vector(stage3.cell_index);
      stack_write_addr <= std_logic_vector(stage3.instance) & std_logic_vector(stage3.stack_pointer);
      

      -- build state for next stage
      next_stage0.skip          <= stage3.skip;
      next_stage0.instance      <= stage3.instance;
      next_stage0.active        <= stage3.active;
      next_stage0.pattern_left  <= stage3.pattern_left;
      next_stage0.lookup_index  <= stage3.lookup_index;
      next_stage0.cell_index    <= stage3.cell_index;
      next_stage0.stack_pointer <= stage3.stack_pointer;
      next_stage0.dumping       <= stage3.dumping;
      next_stage0.data_enable   <= stage3.dumping AND NOT stage3.active;
      if stage3.data_enable = '1' then 
         next_stage0.data          <= stack_read_data(tile_bits-1 downto 0);
         next_stage0.data_enable   <= '1';
      else
         next_stage0.data          <= data_in;
         next_stage0.data_enable   <= data_enable_in;
      end if;

      -- Are we dumping the stack?
      if stage3.dumping = '1' then
         next_stage0.stack_pointer   <= stage3.stack_pointer + 1;
      end if;

      tb_write_enable     <= '0';
      tb_write_addr       <= stage3.instance & std_logic_vector(stage3.cell_index+16);
      tb_write_data       <= stage3.candidate_bottom;

      stack_write_enable  <= '0';
      stack_write_data    <= std_logic_vector(stage3.lookup_index+1) & stage3.pattern_left & stage3.candidate_tile;
      stack_write_addr    <= stage3.instance & std_logic_vector(stage3.stack_pointer);

      placed_write_enable <= '0';
      placed_write_addr   <= stage3.instance & stage3.candidate_tile; 
      placed_write_d      <= "0";
            
      case stage3.action is
         when action_advance   =>
            next_stage0.lookup_index     <= stage3.lookup_index+1;
            
         when action_place     =>
            if stage3.cell_index(3 downto 0) = x_max then  
               next_stage0.cell_index   <= stage3.cell_index + 16 - x_max;   
               next_stage0.pattern_left <= (others => '0');
               tb_read_addr     <= stage3.instance & std_logic_vector(stage3.cell_index + 16 - x_max);
            else  
               next_stage0.cell_index   <= stage3.cell_index + 1;
               next_stage0.pattern_left <= stage3.candidate_right;
               tb_read_addr     <= stage3.instance & std_logic_vector(stage3.cell_index+1);
            end if;
            placed_write_enable <= '1';
            placed_write_d      <= "1";
            tb_write_enable     <= '1';

            if stage3.dumping = '1' and stage3.active = '1' then
               next_stage0.active  <= '0';
               next_stage0.stack_pointer <= "00000001";
            else
               next_stage0.stack_pointer <= stage3.stack_pointer+1; 
            end if;
            stack_write_enable        <= '1';
            next_stage0.lookup_index  <= (others => '0');
         when action_backtrack =>
            if stage3.cell_index(3 downto 0) = 0 then
               next_stage0.cell_index     <= stage3.cell_index - 16 + x_max; 
               tb_read_addr               <= stage3.instance & std_logic_vector(stage3.cell_index - 16 + x_max);
            else
               next_stage0.cell_index     <= stage3.cell_index - 1;
               tb_read_addr               <= stage3.instance & std_logic_vector(stage3.cell_index - 1);
            end if;
            next_stage0.lookup_index  <= unsigned(stack_read_data(index_bits+pattern_bits+tile_bits-1 downto pattern_bits+tile_bits));
            next_stage0.pattern_left  <= stack_read_data(pattern_bits+tile_bits-1 downto tile_bits);            
            next_stage0.stack_pointer <= stage3.stack_pointer-1;
            placed_write_addr         <= stage3.instance & stack_read_data(tile_bits-1 downto 0); 
            placed_write_enable       <= '1';
            placed_write_d            <= "0";

         when others =>  -- action_idle;
            next_stage0.cell_index <= stage3.cell_index;
      end case;
   end process;
   
process(clk)
   begin
      if rising_edge(clk) then
         stage1 <= next_stage1;
         stage2 <= next_stage2;
         stage3 <= next_stage3;
         stage0 <= next_stage0;
      end if;
   end process;
end Behavioral;

dual_port_men.vhd

This module is used to implement three smaller memories needed for each solver core.

----------------------------------------------------------------------------------
-- Engineer: Mike Field <hamster@hamsterworks.co.nz>
-- 
-- Description: A module that infers  simple dual-port RAM
--
----------------------------------------------------------------------------------
library IEEE;
use IEEE.STD_LOGIC_1164.ALL;
use IEEE.NUMERIC_STD.ALL;

entity dual_port_ram is
   Generic(addr_width : natural;
           data_width : natural;
           ram_type   : string := "block");
    Port ( clk          : in  STD_LOGIC;
           write_addr   : in  STD_LOGIC_VECTOR (addr_width-1 downto 0);
           write_enable : in  STD_LOGIC;
           write_d      : in  STD_LOGIC_VECTOR(data_width-1 downto 0);
           read_addr    : in  STD_LOGIC_VECTOR(addr_width-1 downto 0);
           read_d       : out STD_LOGIC_VECTOR(data_width-1 downto 0));
end dual_port_ram;

architecture Behavioral of dual_port_ram is
   type ram_t is array (0 to 1023) of std_logic_vector(data_width-1 downto 0);

   signal ram : ram_t := (others => (others =>'0'));
   attribute ram_style: string;
   attribute ram_style of ram : signal is ram_type;

begin

process(clk)
   begin
      if rising_edge(clk) then
         if write_enable = '1' then 
            ram(to_integer(unsigned(write_addr))) <= write_d;
         end if;
      end if;
   end process;

process(clk)
   begin
      if rising_edge(clk) then
         read_d <= ram(to_integer(unsigned(read_addr)));
      end if;
   end process;

end Behavioral;

tiles2.vhd

And here is the source for a 4x4 puzzle - it is out date, but there is no way I'm going to post the full 8k lines required for the benchmark - just send me an email!

----------------------------------------------------------------------------------
-- Engineer: Mike Field <hamster@snap.net.nz>
-- 
-- Module Name:    tiles2 - Behavioral 
-- Description: Table for a 4x4 puzzle with 10 colours
--
----------------------------------------------------------------------------------
library IEEE;
use IEEE.STD_LOGIC_1164.ALL;

entity tiles2 is
    Port ( clka  : in  STD_LOGIC;
           addra : in  STD_LOGIC_VECTOR (12 downto 0);
           douta : out  STD_LOGIC_VECTOR (19 downto 0));
end tiles2;

architecture Behavioral of tiles2 is

begin

process(clka)
   begin
      if(rising_edge(clka)) then
         case addra(11 downto 0) is
            when x"000" => douta <= x"08A00";
            when x"001" => douta <= x"14501";
            when x"002" => douta <= x"10302";
            when x"003" => douta <= x"10803";
            when x"010" => douta <= x"0A908";
            when x"020" => douta <= x"10106";
            when x"021" => douta <= x"06907";
            when x"030" => douta <= x"00802";
            when x"040" => douta <= x"0280A";
            when x"041" => douta <= x"1470B";
            when x"050" => douta <= x"00A01";
            when x"080" => douta <= x"00803";
            when x"081" => douta <= x"08704";
            when x"082" => douta <= x"04209";
            when x"0A0" => douta <= x"00400";
            when x"0A1" => douta <= x"04605";
            when x"140" => douta <= x"1040A";
            when x"180" => douta <= x"0470D";
            when x"1C0" => douta <= x"04006";
            when x"1D0" => douta <= x"00508";
            when x"280" => douta <= x"0CA05";
            when x"281" => douta <= x"04809";
            when x"290" => douta <= x"00806";
            when x"291" => douta <= x"0E40D";
            when x"2A0" => douta <= x"10009";
            when x"310" => douta <= x"00307";
            when x"3C0" => douta <= x"12207";
            when x"440" => douta <= x"00002";
            when x"500" => douta <= x"14000";
            when x"501" => douta <= x"0E804";
            when x"560" => douta <= x"0C90C";
            when x"561" => douta <= x"0E80F";
            when x"570" => douta <= x"00A0B";
            when x"571" => douta <= x"0220D";
            when x"572" => douta <= x"0E90E";
            when x"580" => douta <= x"0010A";
            when x"640" => douta <= x"12108";
            when x"6E0" => douta <= x"00001";
            when x"7A0" => douta <= x"14005";
            when x"7C0" => douta <= x"1260C";
            when x"800" => douta <= x"0870F";
            when x"810" => douta <= x"0860C";
            when x"8E0" => douta <= x"0810D";
            when x"900" => douta <= x"10004";
            when x"901" => douta <= x"1270E";
            when x"902" => douta <= x"1060F";
            when x"950" => douta <= x"0870E";
            when x"960" => douta <= x"0800B";
            when x"A00" => douta <= x"06002";
            when x"A01" => douta <= x"10003";
            when x"A02" => douta <= x"02206";
            when x"A10" => douta <= x"0800A";
            when x"A20" => douta <= x"00209";
            when x"A70" => douta <= x"00404";
            when x"A71" => douta <= x"0C40F";
            when x"A80" => douta <= x"00003";
            when x"B70" => douta <= x"04007";
            when x"B90" => douta <= x"02008";
            when x"BA0" => douta <= x"0C40C";
            when x"BB0" => douta <= x"0E40E";
            when x"C80" => douta <= x"0A001";
            when x"C81" => douta <= x"0E40B";
            when x"CC0" => douta <= x"00000";
            when x"CE0" => douta <= x"00205";
            when others => douta <= x"FFFFF";
         end case;
      end if;
   end process;
end Behavioral;

Personal tools