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 FZ_Type; use FZ_Type;
  22 
  23 
  24 package FZ_Barr is
  25    
  26    pragma Pure;
  27    
  28    -- Precomputed data for Barrett's Modular Reduction
  29    type Barretoid(ZXMLength       : Indices;
  30                   BarretoidLength : Indices) is
  31       record
  32          ZXM            : FZ(1 .. ZXMLength);       -- Zero-Extended Modulus
  33          J              : FZBit_Index;              -- Jm
  34          B              : FZ(1 .. BarretoidLength); -- The Barrettoid itself
  35          ZSlide         : FZBit_Index;              -- Amount to slide Z
  36          Degenerate     : WBool;                    -- Is it degenerate case?
  37       end record;
  38    
  39    
  40    -- Prepare the precomputed Barrettoid corresponding to a given Modulus
  41    procedure FZ_Make_Barrettoid(Modulus    : in  FZ;
  42                                 Result     : out Barretoid)
  43      with Pre => Result.B'Length = 2 * Modulus'Length and
  44      Result.ZXM'Length = Modulus'Length + 1;
  45    
  46    
  47    -- Reduce N using the given precomputed Barrettoid.
  48    procedure FZ_Barrett_Reduce(X          : in     FZ;
  49                                Bar        : in     Barretoid;
  50                                XReduced   : in out FZ);
  51    pragma Inline_Always(FZ_Barrett_Reduce);
  52    
  53 end FZ_Barr;