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;