raw
ffa_ch13_measure_...    1 ------------------------------------------------------------------------------
ffa_ch13_measure_...    2 ------------------------------------------------------------------------------
ffa_ch13_measure_...    3 -- This file is part of 'Finite Field Arithmetic', aka 'FFA'.               --
ffa_ch13_measure_...    4 --                                                                          --
ffa_ch15_gcd.kv         5 -- (C) 2019 Stanislav Datskovskiy ( www.loper-os.org )                      --
ffa_ch13_measure_...    6 -- http://wot.deedbot.org/17215D118B7239507FAFED98B98228A001ABFFC7.html     --
ffa_ch13_measure_...    7 --                                                                          --
ffa_ch13_measure_...    8 -- You do not have, nor can you ever acquire the right to use, copy or      --
ffa_ch13_measure_...    9 -- distribute this software ; Should you use this software for any purpose, --
ffa_ch13_measure_...   10 -- or copy and distribute it to anyone or in any manner, you are breaking   --
ffa_ch13_measure_...   11 -- the laws of whatever soi-disant jurisdiction, and you promise to         --
ffa_ch13_measure_...   12 -- continue doing so for the indefinite future. In any case, please         --
ffa_ch13_measure_...   13 -- always : read and understand any software ; verify any PGP signatures    --
ffa_ch13_measure_...   14 -- that you use - for any purpose.                                          --
ffa_ch13_measure_...   15 --                                                                          --
ffa_ch13_measure_...   16 -- See also http://trilema.com/2015/a-new-software-licensing-paradigm .     --
ffa_ch13_measure_...   17 ------------------------------------------------------------------------------
ffa_ch13_measure_...   18 ------------------------------------------------------------------------------
ffa_ch13_measure_...   19 
ffa_ch14_barrett.kv    20 with Words;    use Words;
ffa_ch13_measure_...   21 with Word_Ops; use Word_Ops;
ffa_ch13_measure_...   22 with W_Pred;   use W_Pred;
ffa_ch13_measure_...   23 with W_Shifts; use W_Shifts;
ffa_ch13_measure_...   24 
ffa_ch13_measure_...   25 
ffa_ch13_measure_...   26 package body FZ_Measr is
ffa_ch13_measure_...   27    
ffa_ch13_measure_...   28    -- Find the index of eldest nonzero bit ( 0 if none, or 1 .. FZBitness )
ffa_ch14_barrett.kv    29    function FZ_Measure(N : in FZ) return FZBit_Index is
ffa_ch13_measure_...   30       
ffa_ch13_measure_...   31       -- The result (default : 0, will remain 0 if N is in fact zero)
ffa_ch13_measure_...   32       Index     : Word := 0;
ffa_ch13_measure_...   33       
ffa_ch13_measure_...   34       -- The currently-examined Word, starting from the junior-most
ffa_ch13_measure_...   35       Ni        : Word;
ffa_ch13_measure_...   36       
ffa_ch13_measure_...   37       -- The most recently-seen nonzero Word, if indeed any exist
ffa_ch13_measure_...   38       W         : Word := 0;
ffa_ch13_measure_...   39       
ffa_ch13_measure_...   40       -- 1 if currently-examined Word is zero, otherwise 0
ffa_ch13_measure_...   41       NiZ       : WBool;
ffa_ch13_measure_...   42       
ffa_ch13_measure_...   43    begin
ffa_ch13_measure_...   44       
ffa_ch13_measure_...   45       -- Find, in constant time, eldest non-zero Word:
ffa_ch13_measure_...   46       for i in 0 .. Indices(N'Length - 1) loop
ffa_ch13_measure_...   47          Ni    := N(N'First + i);              -- Ni := current Word;
ffa_ch13_measure_...   48          NiZ   := W_ZeroP(Ni);                 -- ... is this Word = 0?
ffa_ch13_measure_...   49          Index := W_Mux(Word(i), Index, NiZ);  -- If NO, save the Index,
ffa_ch13_measure_...   50          W     := W_Mux(Ni,      W,     NiZ);  -- ... and save that Word.
ffa_ch13_measure_...   51       end loop;
ffa_ch13_measure_...   52       
ffa_ch13_measure_...   53       -- Set Index to be the bit-position of the eldest non-zero Word:
ffa_ch13_measure_...   54       Index := Shift_Left(Index, BitnessLog2); -- Index := Index * Bitness
ffa_ch13_measure_...   55       
ffa_ch13_measure_...   56       -- Find, in constant time, eldest non-zero bit in that Word:
ffa_ch13_measure_...   57       for b in 1 .. Bitness loop
ffa_ch14_barrett.kv    58          
ffa_ch13_measure_...   59          -- If W is non-zero, advance the Index...
ffa_ch14_barrett.kv    60          Index := Index + W_NZeroP(W);
ffa_ch14_barrett.kv    61          
ffa_ch13_measure_...   62          -- ... in either case, advance W:
ffa_ch13_measure_...   63          W     := Shift_Right(W, 1);
ffa_ch14_barrett.kv    64          
ffa_ch13_measure_...   65       end loop;
ffa_ch13_measure_...   66       
ffa_ch13_measure_...   67       -- If N = 0, result will be 0; otherwise: index of the eldest 1 bit.
ffa_ch14_barrett.kv    68       return FZBit_Index(Index);
ffa_ch13_measure_...   69       
ffa_ch13_measure_...   70    end FZ_Measure;
ffa_ch13_measure_...   71    
ffa_ch13_measure_...   72 end FZ_Measr;