Finite Field Arithmetic

fz_measr.adb


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