File : word_ops.adb
1 ------------------------------------------------------------------------------
2 ------------------------------------------------------------------------------
3 -- This file is part of 'Finite Field Arithmetic', aka 'FFA'. --
4 -- --
5 -- (C) 2017 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(((not A) and B) or (((not A) or B) and D),
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 | |(~a and b) or |
59 -- |A|B|C|A+B+C| ((a or b) and|A-B-C| ((~a or b) and |
60 -- | | | | | ~(A+B+C)) | | (A-B-C)) |
61 -- +-+-+-+-----+--------------+-----+----------------+
62 -- |0|0|0| 0 | 0 | 0 | 0 |
63 -- +-+-+-+-----+--------------+-----+----------------+
64 -- |1|0|0| 1 | 0 | 1 | 0 |
65 -- +-+-+-+-----+--------------+-----+----------------+
66 -- |0|1|0| 1 | 0 | 1 | 1 |
67 -- +-+-+-+-----+--------------+-----+----------------+
68 -- |1|1|0| 0 | 1 | 0 | 0 |
69 -- +-+-+-+-----+--------------+-----+----------------+
70 -- |0|0|1| 1 | 0 | 1 | 1 |
71 -- +-+-+-+-----+--------------+-----+----------------+
72 -- |1|0|1| 0 | 1 | 0 | 0 |
73 -- +-+-+-+-----+--------------+-----+----------------+
74 -- |0|1|1| 0 | 1 | 0 | 1 |
75 -- +-+-+-+-----+--------------+-----+----------------+
76 -- |1|1|1| 1 | 1 | 1 | 1 |
77 -- +-+-+-+-----+--------------+-----+----------------+
78 -- This base case extends to any N bit register, since
79 -- both equations depend ~strictly~ on A, B, and C.
80
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;