------------------------------------------------------------------------------
--                                                                          --
--                            Matreshka Project                             --
--                                                                          --
--         Localization, Internationalization, Globalization for Ada        --
--                                                                          --
--                        Runtime Library Component                         --
--                                                                          --
------------------------------------------------------------------------------
--                                                                          --
-- Copyright © 2010-2011, Vadim Godunko <vgodunko@gmail.com>                --
-- All rights reserved.                                                     --
--                                                                          --
-- Redistribution and use in source and binary forms, with or without       --
-- modification, are permitted provided that the following conditions       --
-- are met:                                                                 --
--                                                                          --
--  * Redistributions of source code must retain the above copyright        --
--    notice, this list of conditions and the following disclaimer.         --
--                                                                          --
--  * Redistributions in binary form must reproduce the above copyright     --
--    notice, this list of conditions and the following disclaimer in the   --
--    documentation and/or other materials provided with the distribution.  --
--                                                                          --
--  * Neither the name of the Vadim Godunko, IE nor the names of its        --
--    contributors may be used to endorse or promote products derived from  --
--    this software without specific prior written permission.              --
--                                                                          --
-- THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS      --
-- "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT        --
-- LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR    --
-- A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT     --
-- HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,   --
-- SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED --
-- TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR   --
-- PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF   --
-- LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING     --
-- NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS       --
-- SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.             --
--                                                                          --
------------------------------------------------------------------------------
--  $Revision: 1353 $ $Date: 2011-02-02 12:59:57 +0300 (Wed, 02 Feb 2011) $
------------------------------------------------------------------------------
with Ada.Unchecked_Conversion;
with Interfaces;
with System.Address_To_Access_Conversions;
with System.Storage_Elements;

with Matreshka.Internals.SIMD.Intel.SSE2;
with Matreshka.Internals.Strings.Constants;

package body Matreshka.Internals.Strings.Handlers.Generic_X86_SSE2 is

   use Interfaces;
   use Matreshka.Internals.SIMD.Intel;
   use Matreshka.Internals.SIMD.Intel.SSE2;
   use Matreshka.Internals.Strings.Constants;
   use Matreshka.Internals.Unicode;
   use Matreshka.Internals.Utf16;
   use type System.Storage_Elements.Storage_Offset;

   function ffs (A : Interfaces.Unsigned_32) return Interfaces.Unsigned_32;
   pragma Import (Intrinsic, ffs, "__builtin_ffs");

   package v8hi_Conversions is new System.Address_To_Access_Conversions (v8hi);
   use v8hi_Conversions;

   function To_Unsigned_32 is
     new Ada.Unchecked_Conversion
          (Interfaces.Integer_32, Interfaces.Unsigned_32);

   type v8hi_Unrestricted_Array is array (Utf16_String_Index) of v8hi;

   --------------------------
   -- Fill_Null_Terminator --
   --------------------------

   overriding procedure Fill_Null_Terminator
    (Self : X86_SSE2_String_Handler;
     Item : not null Shared_String_Access)
   is
      pragma Unreferenced (Self);

      pragma Suppress (Access_Check);
      --  Suppress not null check of Self which is generated by compiler; but
      --  not needed actually.
      pragma Suppress (Alignment_Check);
      --  Suppress alignment check of Value below which is generated because of
      --  bug in the GNAT GPL 2010 compiler.

      Value  : v8hi_Unrestricted_Array;
      for Value'Address use Item.Value'Address;
      Index  : constant Utf16_String_Index := Item.Unused / 8;
      Offset : constant Utf16_String_Index := Item.Unused mod 8;

   begin
      Value (Index) :=
        To_v8hi
         (mm_and_si128
           (To_v2di (Value (Index)),
            To_v2di (Terminator_Mask_x86_64 (Offset))));
   end Fill_Null_Terminator;

   -----------
   -- Index --
   -----------

   overriding function Index
    (Self : X86_SSE2_String_Handler;
     Item : Matreshka.Internals.Strings.Shared_String_Access;
     Code : Matreshka.Internals.Unicode.Code_Point)
       return Natural
   is
      Value  : v8hi_Unrestricted_Array;
      for Value'Address use Item.Value'Address;

      function Index_16 return Natural;

      --------------
      -- Index_16 --
      --------------

      function Index_16 return Natural is
         Pattern        : constant v8hi := (others => Integer_16 (Code));
         Last           : constant Utf16_String_Index := Item.Unused / 8;
         V              : v8hi;
         --  Value of current vector.
         Match          : v8hi;
         --  Result of matching current vector to pattern. Trailing out-of-data
         --  elements are excluded from this result (filled by zero).
         Surrogates     : v8hi;
         --  Marks of high surrogate code points to be excluded from index
         --  computation. Trailing out-of-data elements are also marked here
         --  (filled by one).
         Exclusion_Mask : Unsigned_32;
         --  Index computation exclusion mask. Every two bits represents one
         --  code unit to be excluded from index computation to skip high
         --  surrogates and trailing out-of-data code units.
         Match_Mask     : Unsigned_32;
         --  Pattern match mask.
         N              : Unsigned_32;
         --  Match code units exclusion mask.
         TM             : v2di;
         TN             : v2di;
         Index          : Natural := 1;

      begin
         if Last /= 0 then
            for J in 0 .. Last - 1 loop
               V := Value (J);

               --  Compute suggorage exclusion vector.

               Surrogates :=
                 To_v8hi
                  (mm_and_si128
                    (To_v2di (V), To_v2di (Surrogate_Kind_Mask_x86_64)));
               Surrogates :=
                 mm_cmpeq_epi16 (Surrogates, Masked_High_Surrogate_x86_64);

               --  Compute matching vector.

               Match := mm_cmpeq_epi16 (V, Pattern);

               --  Compute masks.

               Exclusion_Mask :=
                 To_Unsigned_32 (mm_movemask_epi8 (To_v16qi (Surrogates)));
               Match_Mask :=
                 To_Unsigned_32 (mm_movemask_epi8 (To_v16qi (Match)));

               N := ffs (Match_Mask);

               if N /= 0 then
                  N := 16#FFFF# * 2 ** Natural (N - 1);
               end if;

               Exclusion_Mask := Exclusion_Mask or N;

               if (Exclusion_Mask and 2#00000000_00000011#) = 0 then
                  Index := Index + 1;
               end if;

               if (Exclusion_Mask and 2#00000000_00001100#) = 0 then
                  Index := Index + 1;
               end if;

               if (Exclusion_Mask and 2#00000000_00110000#) = 0 then
                  Index := Index + 1;
               end if;

               if (Exclusion_Mask and 2#00000000_11000000#) = 0 then
                  Index := Index + 1;
               end if;

               if (Exclusion_Mask and 2#00000011_00000000#) = 0 then
                  Index := Index + 1;
               end if;

               if (Exclusion_Mask and 2#00001100_00000000#) = 0 then
                  Index := Index + 1;
               end if;

               if (Exclusion_Mask and 2#00110000_00000000#) = 0 then
                  Index := Index + 1;
               end if;

               if (Exclusion_Mask and 2#11000000_00000000#) = 0 then
                  Index := Index + 1;
               end if;

               if Match_Mask /= 0 then
                  return Index;
               end if;
            end loop;
         end if;

         V := Value (Last);

         --  Prepare masks to exclude trailing out-of-data code units.

         TM := To_v2di (Terminator_Mask_x86_64 (Item.Unused mod 8));
         TN := To_v2di (mm_cmpeq_epi16 (V, V));
         --  This operation constructs 'one' vector.
         TN := mm_andnot_si128 (TM, TN);

         --  Compute surrogates exclusion vector and exclude trailing
         --  out-of-data code units.

         Surrogates :=
           To_v8hi
            (mm_and_si128
              (To_v2di (V), To_v2di (Surrogate_Kind_Mask_x86_64)));
         Surrogates :=
           mm_cmpeq_epi16 (Surrogates, Masked_High_Surrogate_x86_64);
         Surrogates := To_v8hi (mm_or_si128 (To_v2di (Surrogates), TN));
         --  Exclude codes outside of actual data from counting.

         --  Compute match vector and exclude trailing out-of-data code units.

         Match := mm_cmpeq_epi16 (V, Pattern);
         Match := To_v8hi (mm_and_si128 (To_v2di (Match), TM));
         --  Hide matching codes outside of actual data.

         --  Compute masks.

         Exclusion_Mask :=
           To_Unsigned_32 (mm_movemask_epi8 (To_v16qi (Surrogates)));
         Match_Mask := To_Unsigned_32 (mm_movemask_epi8 (To_v16qi (Match)));

         N := ffs (Match_Mask);

         if N /= 0 then
            N := 16#FFFF# * 2 ** Natural (N - 1);
         end if;

         Exclusion_Mask := Exclusion_Mask or N;

         if (Exclusion_Mask and 2#00000000_00000011#) = 0 then
            Index := Index + 1;
         end if;

         if (Exclusion_Mask and 2#00000000_00001100#) = 0 then
            Index := Index + 1;
         end if;

         if (Exclusion_Mask and 2#00000000_00110000#) = 0 then
            Index := Index + 1;
         end if;

         if (Exclusion_Mask and 2#00000000_11000000#) = 0 then
            Index := Index + 1;
         end if;

         if (Exclusion_Mask and 2#00000011_00000000#) = 0 then
            Index := Index + 1;
         end if;

         if (Exclusion_Mask and 2#00001100_00000000#) = 0 then
            Index := Index + 1;
         end if;

         if (Exclusion_Mask and 2#00110000_00000000#) = 0 then
            Index := Index + 1;
         end if;

         if (Exclusion_Mask and 2#11000000_00000000#) = 0 then
            Index := Index + 1;
         end if;

         if Match_Mask /= 0 then
            return Index;
         end if;

         return 0;
      end Index_16;

   begin
      if Code <= 16#FFFF# then
         return Index_16;

      else
         return Base_String_Handler (Self).Index (Item, Code);
      end if;
   end Index;

   --------------
   -- Is_Equal --
   --------------

   overriding function Is_Equal
    (Self  : X86_SSE2_String_Handler;
     Left  : not null Shared_String_Access;
     Right : not null Shared_String_Access) return Boolean
   is
      pragma Unreferenced (Self);

      pragma Suppress (Access_Check);

   begin
      if Left = Right then
         return True;
      end if;

      if Left.Unused /= Right.Unused then
         return False;
      end if;

      declare
         LV : System.Address := Left.Value'Address;
         RV : System.Address := Right.Value'Address;
         J  : Utf16_String_Index := Left.Unused / 8;

      begin
         loop
            if mm_movemask_epi8
                (To_v16qi
                  (mm_cmpeq_epi16 (To_Pointer (LV).all, To_Pointer (RV).all)))
                 /= 16#0000_FFFF#
            then
               return False;
            end if;

            exit when J = 0;

            J := J - 1;
            LV := LV + 16;
            RV := RV + 16;
         end loop;
      end;

      return True;
   end Is_Equal;

   ----------------
   -- Is_Greater --
   ----------------

   overriding function Is_Greater
    (Self  : X86_SSE2_String_Handler;
     Left  : not null Shared_String_Access;
     Right : not null Shared_String_Access) return Boolean
   is
      pragma Unreferenced (Self);

      pragma Suppress (Access_Check);
      pragma Suppress (Index_Check);

   begin
      if Left = Right then
         return False;
      end if;

      declare
         Min   : constant Utf16_String_Index
           := Utf16_String_Index'Min (Left.Unused, Right.Unused);
         LV    : System.Address := Left.Value'Address;
         RV    : System.Address := Right.Value'Address;
         J     : Utf16_String_Index := 0;
         M     : Unsigned_32;
         Index : Utf16_String_Index;

      begin
         loop
            M :=
              To_Unsigned_32
               (mm_movemask_epi8
                 (To_v16qi
                   (mm_cmpeq_epi16
                     (To_Pointer (LV).all, To_Pointer (RV).all))));

            if M /= 16#0000_FFFF# then
               Index := J * 8 + Utf16_String_Index (ffs (not M) / 2);

               return Is_Greater (Left.Value (Index), Right.Value (Index));
            end if;

            exit when J = Min / 8;

            J := J + 1;
            LV := LV + 16;
            RV := RV + 16;
         end loop;
      end;

      return Left.Unused > Right.Unused;
   end Is_Greater;

   -------------------------
   -- Is_Greater_Or_Equal --
   -------------------------

   overriding function Is_Greater_Or_Equal
    (Self  : X86_SSE2_String_Handler;
     Left  : not null Shared_String_Access;
     Right : not null Shared_String_Access) return Boolean
   is
      pragma Unreferenced (Self);

      pragma Suppress (Access_Check);
      pragma Suppress (Index_Check);

   begin
      if Left = Right then
         return True;
      end if;

      declare
         Min   : constant Utf16_String_Index
           := Utf16_String_Index'Min (Left.Unused, Right.Unused);
         LV    : System.Address := Left.Value'Address;
         RV    : System.Address := Right.Value'Address;
         J     : Utf16_String_Index := 0;
         M     : Unsigned_32;
         Index : Utf16_String_Index;

      begin
         loop
            M :=
              To_Unsigned_32
               (mm_movemask_epi8
                 (To_v16qi
                   (mm_cmpeq_epi16
                     (To_Pointer (LV).all, To_Pointer (RV).all))));

            if M /= 16#0000_FFFF# then
               Index := J * 8 + Utf16_String_Index (ffs (not M) / 2);

               return Is_Greater (Left.Value (Index), Right.Value (Index));
            end if;

            exit when J = Min / 8;

            J := J + 1;
            LV := LV + 16;
            RV := RV + 16;
         end loop;
      end;

      return Left.Unused >= Right.Unused;
   end Is_Greater_Or_Equal;

   -------------
   -- Is_Less --
   -------------

   overriding function Is_Less
    (Self  : X86_SSE2_String_Handler;
     Left  : not null Shared_String_Access;
     Right : not null Shared_String_Access) return Boolean
   is
      pragma Unreferenced (Self);

      pragma Suppress (Access_Check);
      pragma Suppress (Index_Check);

   begin
      if Left = Right then
         return False;
      end if;

      declare
         Min   : constant Utf16_String_Index
           := Utf16_String_Index'Min (Left.Unused, Right.Unused);
         LV    : System.Address := Left.Value'Address;
         RV    : System.Address := Right.Value'Address;
         J     : Utf16_String_Index := 0;
         M     : Unsigned_32;
         Index : Utf16_String_Index;

      begin
         loop
            M :=
              To_Unsigned_32
               (mm_movemask_epi8
                 (To_v16qi
                   (mm_cmpeq_epi16
                     (To_Pointer (LV).all, To_Pointer (RV).all))));

            if M /= 16#0000_FFFF# then
               Index := J * 8 + Utf16_String_Index (ffs (not M) / 2);

               return Is_Less (Left.Value (Index), Right.Value (Index));
            end if;

            exit when J = Min / 8;

            J := J + 1;
            LV := LV + 16;
            RV := RV + 16;
         end loop;
      end;

      return Left.Unused < Right.Unused;
   end Is_Less;

   ----------------------
   -- Is_Less_Or_Equal --
   ----------------------

   overriding function Is_Less_Or_Equal
    (Self  : X86_SSE2_String_Handler;
     Left  : not null Shared_String_Access;
     Right : not null Shared_String_Access) return Boolean
   is
      pragma Unreferenced (Self);

      pragma Suppress (Access_Check);
      pragma Suppress (Index_Check);

   begin
      if Left = Right then
         return True;
      end if;

      declare
         Min   : constant Utf16_String_Index
           := Utf16_String_Index'Min (Left.Unused, Right.Unused);
         LV    : System.Address := Left.Value'Address;
         RV    : System.Address := Right.Value'Address;
         J     : Utf16_String_Index := 0;
         M     : Unsigned_32;
         Index : Utf16_String_Index;

      begin
         loop
            M :=
              To_Unsigned_32
               (mm_movemask_epi8
                 (To_v16qi
                   (mm_cmpeq_epi16
                     (To_Pointer (LV).all, To_Pointer (RV).all))));

            if M /= 16#0000_FFFF# then
               Index := J * 8 + Utf16_String_Index (ffs (not M) / 2);

               return Is_Less (Left.Value (Index), Right.Value (Index));
            end if;

            exit when J = Min / 8;

            J := J + 1;
            LV := LV + 16;
            RV := RV + 16;
         end loop;
      end;

      return Left.Unused <= Right.Unused;
   end Is_Less_Or_Equal;

end Matreshka.Internals.Strings.Handlers.Generic_X86_SSE2;
