------------------------------------------------------------------------------
------------------------------------------------------------------------------
-- This file is part of 'Finite Field Arithmetic', aka 'FFA'.               --
--                                                                          --
-- (C) 2018 Stanislav Datskovskiy ( www.loper-os.org )                      --
-- http://wot.deedbot.org/17215D118B7239507FAFED98B98228A001ABFFC7.html     --
--                                                                          --
-- You do not have, nor can you ever acquire the right to use, copy or      --
-- distribute this software ; Should you use this software for any purpose, --
-- or copy and distribute it to anyone or in any manner, you are breaking   --
-- the laws of whatever soi-disant jurisdiction, and you promise to         --
-- continue doing so for the indefinite future. In any case, please         --
-- always : read and understand any software ; verify any PGP signatures    --
-- that you use - for any purpose.                                          --
--                                                                          --
-- See also http://trilema.com/2015/a-new-software-licensing-paradigm .     --
------------------------------------------------------------------------------
------------------------------------------------------------------------------

with Words;    use Words;
with Word_Ops; use Word_Ops;
with W_Pred;   use W_Pred;
with W_Shifts; use W_Shifts;


package body FZ_Measr is
   
   -- Find the index of eldest nonzero bit ( 0 if none, or 1 .. FZBitness )
   function FZ_Measure(N : in FZ) return FZBit_Index is
      
      -- The result (default : 0, will remain 0 if N is in fact zero)
      Index     : Word := 0;
      
      -- The currently-examined Word, starting from the junior-most
      Ni        : Word;
      
      -- The most recently-seen nonzero Word, if indeed any exist
      W         : Word := 0;
      
      -- 1 if currently-examined Word is zero, otherwise 0
      NiZ       : WBool;
      
   begin
      
      -- Find, in constant time, eldest non-zero Word:
      for i in 0 .. Indices(N'Length - 1) loop
         Ni    := N(N'First + i);              -- Ni := current Word;
         NiZ   := W_ZeroP(Ni);                 -- ... is this Word = 0?
         Index := W_Mux(Word(i), Index, NiZ);  -- If NO, save the Index,
         W     := W_Mux(Ni,      W,     NiZ);  -- ... and save that Word.
      end loop;
      
      -- Set Index to be the bit-position of the eldest non-zero Word:
      Index := Shift_Left(Index, BitnessLog2); -- Index := Index * Bitness
      
      -- Find, in constant time, eldest non-zero bit in that Word:
      for b in 1 .. Bitness loop
         
         -- If W is non-zero, advance the Index...
         Index := Index + W_NZeroP(W);
         
         -- ... in either case, advance W:
         W     := Shift_Right(W, 1);
         
      end loop;
      
      -- If N = 0, result will be 0; otherwise: index of the eldest 1 bit.
      return FZBit_Index(Index);
      
   end FZ_Measure;
   
end FZ_Measr;