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;