Finite Field Arithmetic

word_ops.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 W_Shifts; use W_Shifts;
  21 
  22 -- Fundamental Operations on Words:
  23 package body Word_Ops is
  24    
  25    -- Ada (like C) does not (portably) tell us over/underflow from arithmetic.
  26    -- And there existed in the past, and apparently exist today, CPUs made
  27    -- by idiots and wreckers (e.g. 'RISC-V') that do not have flags at all!
  28    
  29    -- However, for multi-word addition, subtraction, the inner loop of
  30    -- Comba's multiplication, and for a handful of other ops, we need it!
  31    
  32    -- So we derive the Carry or Borrow at the 'eldest' binary position.
  33    -- See the elementary proof (base case: 1 bit) further below:
  34    
  35    -- Find the Carry, from an addition where it is known that A + B == S:
  36    function W_Carry(A : in Word; B : in Word; S : in Word)
  37                    return WBool is
  38    begin
  39       return WBool(Shift_Right((A and B) or ((A or B) and (not S)),
  40                                Bitness - 1));
  41    end W_Carry;
  42    
  43    
  44    -- Find the Borrow, from a subtraction where it is known that A - B == D:
  45    function W_Borrow(A : in Word; B : in Word; D : in Word)
  46                     return WBool is
  47    begin
  48       return WBool(Shift_Right((B and D) or ((B or D) and (not A)),
  49                                Bitness - 1));
  50    end W_Borrow;
  51    
  52    -- A+B+C is the output bit of 1-bit adder; C is carry-in;
  53    -- A-B-C is the output bit of 1-bit subber; C is borrow-in.
  54    -- Observe that A+B+C is equal to A-B-C for all A,B,C !
  55    --  +-+-+-+-----+--------------+-----+----------------+
  56    --  |           | 'Carry' out: |     | 'Borrow' out:  |
  57    --  +-+-+-+-----+--------------+-----+----------------+
  58    --  | | | |     |(a and b) or  |     |(b and (A-B-C)) |
  59    --  |A|B|C|A+B+C| ((a or b) and|A-B-C|      or        |
  60    --  | | | |     |    ~(A+B+C)) |     |((b or (A-B-C)) |
  61    --  | | | |     |              |     |  and ~a)       |
  62    --  +-+-+-+-----+--------------+-----+----------------+
  63    --  |0|0|0|  0  |      0       |  0  |       0        |
  64    --  +-+-+-+-----+--------------+-----+----------------+
  65    --  |1|0|0|  1  |      0       |  1  |       0        |
  66    --  +-+-+-+-----+--------------+-----+----------------+
  67    --  |0|1|0|  1  |      0       |  1  |       1        |
  68    --  +-+-+-+-----+--------------+-----+----------------+
  69    --  |1|1|0|  0  |      1       |  0  |       0        |
  70    --  +-+-+-+-----+--------------+-----+----------------+
  71    --  |0|0|1|  1  |      0       |  1  |       1        |
  72    --  +-+-+-+-----+--------------+-----+----------------+
  73    --  |1|0|1|  0  |      1       |  0  |       0        |
  74    --  +-+-+-+-----+--------------+-----+----------------+
  75    --  |0|1|1|  0  |      1       |  0  |       1        |
  76    --  +-+-+-+-----+--------------+-----+----------------+
  77    --  |1|1|1|  1  |      1       |  1  |       1        |
  78    --  +-+-+-+-----+--------------+-----+----------------+
  79    -- This base case extends to any N bit register, since
  80    -- both equations depend ~strictly~ on A, B, and C.
  81    
  82    -- Without any branching: if Sel == 0, return A; if Sel == 1, return B.
  83    function W_Mux(A : in Word; B : in Word; Sel : in WBool) return Word is
  84    begin
  85       return B xor ((Sel - 1) and (A xor B));
  86    end W_Mux;
  87    
  88 end Word_Ops;