------------------------------------------------------------------------------
--                                                                          --
--                         GNAT COMPILER COMPONENTS                         --
--                                                                          --
--                             E X P _ P A K D                              --
--                                                                          --
--                                 S p e c                                  --
--                                                                          --
--          Copyright (C) 1992-2019, Free Software Foundation, Inc.         --
--                                                                          --
-- GNAT is free software;  you can  redistribute it  and/or modify it under --
-- terms of the  GNU General Public License as published  by the Free Soft- --
-- ware  Foundation;  either version 3,  or (at your option) any later ver- --
-- sion.  GNAT is distributed in the hope that it will be useful, but WITH- --
-- OUT ANY WARRANTY;  without even the  implied warranty of MERCHANTABILITY --
-- or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License --
-- for  more details.  You should have  received  a copy of the GNU General --
-- Public License  distributed with GNAT; see file COPYING3.  If not, go to --
-- http://www.gnu.org/licenses for a complete copy of the license.          --
--                                                                          --
-- GNAT was originally developed  by the GNAT team at  New York University. --
-- Extensive contributions were provided by Ada Core Technologies Inc.      --
--                                                                          --
------------------------------------------------------------------------------

--  Expand routines for manipulation of packed arrays

with Rtsfind; use Rtsfind;
with Types;   use Types;

package Exp_Pakd is

   -------------------------------------
   -- Implementation of Packed Arrays --
   -------------------------------------

   --  When a packed array (sub)type is frozen, we create a corresponding
   --  type that will be used to hold the bits of the packed value, and store
   --  the entity for this type in the Packed_Array_Impl_Type field of the
   --  E_Array_Type or E_Array_Subtype entity for the packed array.

   --  This packed array type has the name xxxPn, where xxx is the name
   --  of the packed type, and n is the component size. The expanded
   --  declaration declares a type that is one of the following:

   --    For an unconstrained array with component size 1,2,4 or any other
   --    odd component size. These are the cases in which we do not need
   --    to align the underlying array.

   --      type xxxPn is new Packed_Bytes1;

   --    For an unconstrained array with component size that is divisible
   --    by 2, but not divisible by 4 (other than 2 itself). These are the
   --    cases in which we can generate better code if the underlying array
   --    is 2-byte aligned (see System.Pack_14 in file s-pack14 for example).

   --      type xxxPn is new Packed_Bytes2;

   --    For an unconstrained array with component size that is divisible
   --    by 4, other than powers of 2 (which either come under the 1,2,4
   --    exception above, or are not packed at all). These are cases where
   --    we can generate better code if the underlying array is 4-byte
   --    aligned (see System.Pack_20 in file s-pack20 for example).

   --      type xxxPn is new Packed_Bytes4;

   --    For a constrained array with a static index type where the number
   --    of bits does not exceed the size of Unsigned:

   --      type xxxPn is new Unsigned range 0 .. 2 ** nbits - 1;

   --    For a constrained array with a static index type where the number
   --    of bits is greater than the size of Unsigned, but does not exceed
   --    the size of Long_Long_Unsigned:

   --       type xxxPn is new Long_Long_Unsigned range 0 .. 2 ** nbits - 1;

   --    For all other constrained arrays, we use one of

   --       type xxxPn is new Packed_Bytes1 (0 .. m);
   --       type xxxPn is new Packed_Bytes2 (0 .. m);
   --       type xxxPn is new Packed_Bytes4 (0 .. m);

   --    where m is calculated (from the length of the original packed array)
   --    to hold the required number of bits, and the choice of the particular
   --    Packed_Bytes{1,2,4} type is made on the basis of alignment needs as
   --    described above for the unconstrained case.

   --  When a variable of packed array type is allocated, gigi will allocate
   --  the amount of space indicated by the corresponding packed array type.
   --  However, we do NOT attempt to rewrite the types of any references or
   --  to retype the variable itself, since this would cause all kinds of
   --  semantic problems in the front end (remember that expansion proceeds
   --  at the same time as analysis).

   --  For an indexed reference to a packed array, we simply convert the
   --  reference to the appropriate equivalent reference to the object
   --  of the packed array type (using unchecked conversion).

   --  In some cases (for internally generated types, and for the subtypes
   --  for record fields that depend on a discriminant), the corresponding
   --  packed type cannot be easily generated in advance. In these cases,
   --  we generate the required subtype on the fly at the reference point.

   --  For the modular case, any unused bits are initialized to zero, and
   --  all operations maintain these bits as zero (where necessary all
   --  unchecked conversions from corresponding array values require
   --  these bits to be clear, which is done automatically by gigi).

   --  For the array cases, there can be unused bits in the last byte, and
   --  these are neither initialized, nor treated specially in operations
   --  (i.e. it is allowable for these bits to be clobbered, e.g. by not).

   ---------------------------
   -- Endian Considerations --
   ---------------------------

   --  The standard does not specify the way in which bits are numbered in
   --  a packed array. There are two reasonable rules for deciding this:

   --    Store the first bit at right end (low order) word. This means
   --    that the scaled subscript can be used directly as a left shift
   --    count (if we put bit 0 at the left end, then we need an extra
   --    subtract to compute the shift count).

   --    Layout the bits so that if the packed boolean array is overlaid on
   --    a record, using unchecked conversion, then bit 0 of the array is
   --    the same as the bit numbered bit 0 in a record representation
   --    clause applying to the record. For example:

   --       type Rec is record
   --          C : Bits4;
   --          D : Bits7;
   --          E : Bits5;
   --       end record;

   --       for Rec use record
   --          C at 0 range  0  .. 3;
   --          D at 0 range  4 .. 10;
   --          E at 0 range 11 .. 15;
   --       end record;

   --       type P16 is array (0 .. 15) of Boolean;
   --       pragma Pack (P16);

   --    Now if we use unchecked conversion to convert a value of the record
   --    type to the packed array type, according to this second criterion,
   --    we would expect field D to occupy bits 4..10 of the Boolean array.

   --  Although not required, this correspondence seems a highly desirable
   --  property, and is one that GNAT decides to guarantee. For a little
   --  endian machine, we can also meet the first requirement, but for a
   --  big endian machine, it will be necessary to store the first bit of
   --  a Boolean array in the left end (most significant) bit of the word.
   --  This may cost an extra instruction on some machines, but we consider
   --  that a worthwhile price to pay for the consistency.

   --  One more important point arises in the case where we have a constrained
   --  subtype of an unconstrained array. Take the case of 20 bits. For the
   --  unconstrained representation, we would use an array of bytes:

   --     Little-endian case
   --       8-7-6-5-4-3-2-1  16-15-14-13-12-11-10-9  x-x-x-x-20-19-18-17

   --     Big-endian case
   --       1-2-3-4-5-6-7-8  9-10-11-12-13-14-15-16  17-18-19-20-x-x-x-x

   --   For the constrained case, we use a 20-bit modular value, but in
   --   general this value may well be stored in 32 bits. Let's look at
   --   what it looks like:

   --     Little-endian case

   --       x-x-x-x-x-x-x-x-x-x-x-x-20-19-18-17-...-10-9-8-7-6-5-4-3-2-1

   --         which stored in memory looks like

   --       8-7-...-2-1  16-15-...-10-9  x-x-x-x-20-19-18-17  x-x-x-x-x-x-x

   --   An important rule is that the constrained and unconstrained cases
   --   must have the same bit representation in memory, since we will often
   --   convert from one to the other (e.g. when calling a procedure whose
   --   formal is unconstrained). As we see, that criterion is met for the
   --   little-endian case above. Now let's look at the big-endian case:

   --     Big-endian case

   --       x-x-x-x-x-x-x-x-x-x-x-x-1-2-3-4-5-6-7-8-9-10-...-17-18-19-20

   --         which stored in memory looks like

   --       x-x-x-x-x-x-x-x  x-x-x-x-1-2-3-4  5-6-...11-12  13-14-...-19-20

   --   That won't do, the representation value in memory is NOT the same in
   --   the constrained and unconstrained case. The solution is to store the
   --   modular value left-justified:

   --       1-2-3-4-5-6-7-8-9-10-...-17-18-19-20-x-x-x-x-x-x-x-x-x-x-x

   --         which stored in memory looks like

   --       1-2-...-7-8  9-10-...15-16  17-18-19-20-x-x-x-x  x-x-x-x-x-x-x-x

   --   and now, we do indeed have the same representation for the memory
   --   version in the constrained and unconstrained cases.

   ----------------------------------------------
   -- Entity Tables for Packed Access Routines --
   ----------------------------------------------

   --  For the cases of component size = 3,5-7,9-15,17-31,33-63 we call library
   --  routines. These tables provide the entity for the proper routine. They
   --  are exposed in the spec to allow checking for the presence of the needed
   --  routine when an array is subject to pragma Pack.

   type E_Array is array (Int range 01 .. 63) of RE_Id;

   --  Array of Bits_nn entities. Note that we do not use library routines
   --  for the 8-bit and 16-bit cases, but we still fill in the table, using
   --  entries from System.Unsigned, because we also use this table for
   --  certain special unchecked conversions in the big-endian case.

   Bits_Id : constant E_Array :=
     (01 => RE_Bits_1,
      02 => RE_Bits_2,
      03 => RE_Bits_03,
      04 => RE_Bits_4,
      05 => RE_Bits_05,
      06 => RE_Bits_06,
      07 => RE_Bits_07,
      08 => RE_Unsigned_8,
      09 => RE_Bits_09,
      10 => RE_Bits_10,
      11 => RE_Bits_11,
      12 => RE_Bits_12,
      13 => RE_Bits_13,
      14 => RE_Bits_14,
      15 => RE_Bits_15,
      16 => RE_Unsigned_16,
      17 => RE_Bits_17,
      18 => RE_Bits_18,
      19 => RE_Bits_19,
      20 => RE_Bits_20,
      21 => RE_Bits_21,
      22 => RE_Bits_22,
      23 => RE_Bits_23,
      24 => RE_Bits_24,
      25 => RE_Bits_25,
      26 => RE_Bits_26,
      27 => RE_Bits_27,
      28 => RE_Bits_28,
      29 => RE_Bits_29,
      30 => RE_Bits_30,
      31 => RE_Bits_31,
      32 => RE_Unsigned_32,
      33 => RE_Bits_33,
      34 => RE_Bits_34,
      35 => RE_Bits_35,
      36 => RE_Bits_36,
      37 => RE_Bits_37,
      38 => RE_Bits_38,
      39 => RE_Bits_39,
      40 => RE_Bits_40,
      41 => RE_Bits_41,
      42 => RE_Bits_42,
      43 => RE_Bits_43,
      44 => RE_Bits_44,
      45 => RE_Bits_45,
      46 => RE_Bits_46,
      47 => RE_Bits_47,
      48 => RE_Bits_48,
      49 => RE_Bits_49,
      50 => RE_Bits_50,
      51 => RE_Bits_51,
      52 => RE_Bits_52,
      53 => RE_Bits_53,
      54 => RE_Bits_54,
      55 => RE_Bits_55,
      56 => RE_Bits_56,
      57 => RE_Bits_57,
      58 => RE_Bits_58,
      59 => RE_Bits_59,
      60 => RE_Bits_60,
      61 => RE_Bits_61,
      62 => RE_Bits_62,
      63 => RE_Bits_63);

   --  Array of Get routine entities. These are used to obtain an element from
   --  a packed array. The N'th entry is used to obtain elements from a packed
   --  array whose component size is N. RE_Null is used as a null entry, for
   --  the cases where a library routine is not used.

   Get_Id : constant E_Array :=
     (01 => RE_Null,
      02 => RE_Null,
      03 => RE_Get_03,
      04 => RE_Null,
      05 => RE_Get_05,
      06 => RE_Get_06,
      07 => RE_Get_07,
      08 => RE_Null,
      09 => RE_Get_09,
      10 => RE_Get_10,
      11 => RE_Get_11,
      12 => RE_Get_12,
      13 => RE_Get_13,
      14 => RE_Get_14,
      15 => RE_Get_15,
      16 => RE_Null,
      17 => RE_Get_17,
      18 => RE_Get_18,
      19 => RE_Get_19,
      20 => RE_Get_20,
      21 => RE_Get_21,
      22 => RE_Get_22,
      23 => RE_Get_23,
      24 => RE_Get_24,
      25 => RE_Get_25,
      26 => RE_Get_26,
      27 => RE_Get_27,
      28 => RE_Get_28,
      29 => RE_Get_29,
      30 => RE_Get_30,
      31 => RE_Get_31,
      32 => RE_Null,
      33 => RE_Get_33,
      34 => RE_Get_34,
      35 => RE_Get_35,
      36 => RE_Get_36,
      37 => RE_Get_37,
      38 => RE_Get_38,
      39 => RE_Get_39,
      40 => RE_Get_40,
      41 => RE_Get_41,
      42 => RE_Get_42,
      43 => RE_Get_43,
      44 => RE_Get_44,
      45 => RE_Get_45,
      46 => RE_Get_46,
      47 => RE_Get_47,
      48 => RE_Get_48,
      49 => RE_Get_49,
      50 => RE_Get_50,
      51 => RE_Get_51,
      52 => RE_Get_52,
      53 => RE_Get_53,
      54 => RE_Get_54,
      55 => RE_Get_55,
      56 => RE_Get_56,
      57 => RE_Get_57,
      58 => RE_Get_58,
      59 => RE_Get_59,
      60 => RE_Get_60,
      61 => RE_Get_61,
      62 => RE_Get_62,
      63 => RE_Get_63);

   --  Array of Get routine entities to be used in the case where the packed
   --  array is itself a component of a packed structure, and therefore may not
   --  be fully aligned. This only affects the even sizes, since for the odd
   --  sizes, we do not get any fixed alignment in any case.

   GetU_Id : constant E_Array :=
     (01 => RE_Null,
      02 => RE_Null,
      03 => RE_Get_03,
      04 => RE_Null,
      05 => RE_Get_05,
      06 => RE_GetU_06,
      07 => RE_Get_07,
      08 => RE_Null,
      09 => RE_Get_09,
      10 => RE_GetU_10,
      11 => RE_Get_11,
      12 => RE_GetU_12,
      13 => RE_Get_13,
      14 => RE_GetU_14,
      15 => RE_Get_15,
      16 => RE_Null,
      17 => RE_Get_17,
      18 => RE_GetU_18,
      19 => RE_Get_19,
      20 => RE_GetU_20,
      21 => RE_Get_21,
      22 => RE_GetU_22,
      23 => RE_Get_23,
      24 => RE_GetU_24,
      25 => RE_Get_25,
      26 => RE_GetU_26,
      27 => RE_Get_27,
      28 => RE_GetU_28,
      29 => RE_Get_29,
      30 => RE_GetU_30,
      31 => RE_Get_31,
      32 => RE_Null,
      33 => RE_Get_33,
      34 => RE_GetU_34,
      35 => RE_Get_35,
      36 => RE_GetU_36,
      37 => RE_Get_37,
      38 => RE_GetU_38,
      39 => RE_Get_39,
      40 => RE_GetU_40,
      41 => RE_Get_41,
      42 => RE_GetU_42,
      43 => RE_Get_43,
      44 => RE_GetU_44,
      45 => RE_Get_45,
      46 => RE_GetU_46,
      47 => RE_Get_47,
      48 => RE_GetU_48,
      49 => RE_Get_49,
      50 => RE_GetU_50,
      51 => RE_Get_51,
      52 => RE_GetU_52,
      53 => RE_Get_53,
      54 => RE_GetU_54,
      55 => RE_Get_55,
      56 => RE_GetU_56,
      57 => RE_Get_57,
      58 => RE_GetU_58,
      59 => RE_Get_59,
      60 => RE_GetU_60,
      61 => RE_Get_61,
      62 => RE_GetU_62,
      63 => RE_Get_63);

   --  Array of Set routine entities. These are used to assign an element of a
   --  packed array. The N'th entry is used to assign elements for a packed
   --  array whose component size is N. RE_Null is used as a null entry, for
   --  the cases where a library routine is not used.

   Set_Id : constant E_Array :=
     (01 => RE_Null,
      02 => RE_Null,
      03 => RE_Set_03,
      04 => RE_Null,
      05 => RE_Set_05,
      06 => RE_Set_06,
      07 => RE_Set_07,
      08 => RE_Null,
      09 => RE_Set_09,
      10 => RE_Set_10,
      11 => RE_Set_11,
      12 => RE_Set_12,
      13 => RE_Set_13,
      14 => RE_Set_14,
      15 => RE_Set_15,
      16 => RE_Null,
      17 => RE_Set_17,
      18 => RE_Set_18,
      19 => RE_Set_19,
      20 => RE_Set_20,
      21 => RE_Set_21,
      22 => RE_Set_22,
      23 => RE_Set_23,
      24 => RE_Set_24,
      25 => RE_Set_25,
      26 => RE_Set_26,
      27 => RE_Set_27,
      28 => RE_Set_28,
      29 => RE_Set_29,
      30 => RE_Set_30,
      31 => RE_Set_31,
      32 => RE_Null,
      33 => RE_Set_33,
      34 => RE_Set_34,
      35 => RE_Set_35,
      36 => RE_Set_36,
      37 => RE_Set_37,
      38 => RE_Set_38,
      39 => RE_Set_39,
      40 => RE_Set_40,
      41 => RE_Set_41,
      42 => RE_Set_42,
      43 => RE_Set_43,
      44 => RE_Set_44,
      45 => RE_Set_45,
      46 => RE_Set_46,
      47 => RE_Set_47,
      48 => RE_Set_48,
      49 => RE_Set_49,
      50 => RE_Set_50,
      51 => RE_Set_51,
      52 => RE_Set_52,
      53 => RE_Set_53,
      54 => RE_Set_54,
      55 => RE_Set_55,
      56 => RE_Set_56,
      57 => RE_Set_57,
      58 => RE_Set_58,
      59 => RE_Set_59,
      60 => RE_Set_60,
      61 => RE_Set_61,
      62 => RE_Set_62,
      63 => RE_Set_63);

   --  Array of Set routine entities to be used in the case where the packed
   --  array is itself a component of a packed structure, and therefore may not
   --  be fully aligned. This only affects the even sizes, since for the odd
   --  sizes, we do not get any fixed alignment in any case.

   SetU_Id : constant E_Array :=
     (01 => RE_Null,
      02 => RE_Null,
      03 => RE_Set_03,
      04 => RE_Null,
      05 => RE_Set_05,
      06 => RE_SetU_06,
      07 => RE_Set_07,
      08 => RE_Null,
      09 => RE_Set_09,
      10 => RE_SetU_10,
      11 => RE_Set_11,
      12 => RE_SetU_12,
      13 => RE_Set_13,
      14 => RE_SetU_14,
      15 => RE_Set_15,
      16 => RE_Null,
      17 => RE_Set_17,
      18 => RE_SetU_18,
      19 => RE_Set_19,
      20 => RE_SetU_20,
      21 => RE_Set_21,
      22 => RE_SetU_22,
      23 => RE_Set_23,
      24 => RE_SetU_24,
      25 => RE_Set_25,
      26 => RE_SetU_26,
      27 => RE_Set_27,
      28 => RE_SetU_28,
      29 => RE_Set_29,
      30 => RE_SetU_30,
      31 => RE_Set_31,
      32 => RE_Null,
      33 => RE_Set_33,
      34 => RE_SetU_34,
      35 => RE_Set_35,
      36 => RE_SetU_36,
      37 => RE_Set_37,
      38 => RE_SetU_38,
      39 => RE_Set_39,
      40 => RE_SetU_40,
      41 => RE_Set_41,
      42 => RE_SetU_42,
      43 => RE_Set_43,
      44 => RE_SetU_44,
      45 => RE_Set_45,
      46 => RE_SetU_46,
      47 => RE_Set_47,
      48 => RE_SetU_48,
      49 => RE_Set_49,
      50 => RE_SetU_50,
      51 => RE_Set_51,
      52 => RE_SetU_52,
      53 => RE_Set_53,
      54 => RE_SetU_54,
      55 => RE_Set_55,
      56 => RE_SetU_56,
      57 => RE_Set_57,
      58 => RE_SetU_58,
      59 => RE_Set_59,
      60 => RE_SetU_60,
      61 => RE_Set_61,
      62 => RE_SetU_62,
      63 => RE_Set_63);

   -----------------
   -- Subprograms --
   -----------------

   procedure Create_Packed_Array_Impl_Type (Typ  : Entity_Id);
   --  Typ is a array type or subtype to which pragma Pack applies. If the
   --  Packed_Array_Impl_Type field of Typ is already set, then the call has
   --  no effect, otherwise a suitable type or subtype is created and stored in
   --  the Packed_Array_Impl_Type field of Typ. This created type is an Itype
   --  so that Gigi will simply elaborate and freeze the type on first use
   --  (which is typically the definition of the corresponding array type).
   --
   --  Note: although this routine is included in the expander package for
   --  packed types, it is actually called unconditionally from Freeze,
   --  whether or not expansion (and code generation) is enabled. We do this
   --  since we want gigi to be able to properly compute type characteristics
   --  (for the Data Decomposition Annex of ASIS, and possible other future
   --  uses) even if code generation is not active. Strictly this means that
   --  this procedure is not part of the expander, but it seems appropriate
   --  to keep it together with the other expansion routines that have to do
   --  with packed array types.

   procedure Expand_Packed_Boolean_Operator (N : Node_Id);
   --  N is an N_Op_And, N_Op_Or or N_Op_Xor node whose operand type is a
   --  packed boolean array. This routine expands the appropriate operations
   --  to carry out the logical operation on the packed arrays. It handles
   --  both the modular and array representation cases.

   procedure Expand_Packed_Element_Reference (N : Node_Id);
   --  N is an N_Indexed_Component node whose prefix is a packed array. In
   --  the bit packed case, this routine can only be used for the expression
   --  evaluation case, not the assignment case, since the result is not a
   --  variable. See Expand_Bit_Packed_Element_Set for how the assignment case
   --  is handled in the bit packed case. For the enumeration case, the result
   --  of this call is always a variable, so the call can be used for both the
   --  expression evaluation and assignment cases.

   procedure Expand_Bit_Packed_Element_Set (N : Node_Id);
   --  N is an N_Assignment_Statement node whose name is an indexed
   --  component of a bit-packed array. This procedure rewrites the entire
   --  assignment statement with appropriate code to set the referenced
   --  bits of the packed array type object. Note that this procedure is
   --  used only for the bit-packed case, not for the enumeration case.

   procedure Expand_Packed_Eq (N : Node_Id);
   --  N is an N_Op_Eq node where the operands are packed arrays whose
   --  representation is an array-of-bytes type (the case where a modular
   --  type is used for the representation does not require any special
   --  handling, because in the modular case, unused bits are zeroes.

   procedure Expand_Packed_Not (N : Node_Id);
   --  N is an N_Op_Not node where the operand is packed array of Boolean
   --  in standard representation (i.e. component size is one bit). This
   --  procedure expands the corresponding not operation. Note that the
   --  non-standard representation case is handled by using a loop through
   --  elements generated by the normal non-packed circuitry.

   function Involves_Packed_Array_Reference (N : Node_Id) return Boolean;
   --  N is the node for a name. This function returns true if the name
   --  involves a packed array reference. A node involves a packed array
   --  reference if it is itself an indexed component referring to a bit-
   --  packed array, or it is a selected component whose prefix involves
   --  a packed array reference.

   procedure Expand_Packed_Address_Reference (N : Node_Id);
   --  The node N is an attribute reference for the 'Address reference, where
   --  the prefix involves a packed array reference. This routine expands the
   --  necessary code for performing the address reference in this case.

   procedure Expand_Packed_Bit_Reference (N : Node_Id);
   --  The node N is an attribute reference for the 'Bit reference, where the
   --  prefix involves a packed array reference. This routine expands the
   --  necessary code for performing the bit reference in this case.

end Exp_Pakd;