*This article is part of a series of hands-on tutorials introducing FFA, or the Finite Field Arithmetic library. FFA differs from the typical “Open Sores” abomination, in that — rather than trusting the author blindly with their lives — prospective users are expected to read and fully understand every single line. In exactly the same manner that you would understand and pack your own parachute. The reader will assemble and test a working FFA with his own hands, and at the same time grasp the purpose of each moving part therein.*

- Chapter 1: Genesis.
**Chapter 2: Logical and Bitwise Operations.**

You will need:

**All**of the materials from Chapter 1.- ffa_ch2_logicals.vpatch
- ffa_ch2_logicals.vpatch.asciilifeform.sig

Add the above *vpatch* and *seal* to your V-set, and *press* to *ffa_ch2_logicals.vpatch.*

Just as in Chapter 1, you will end up with two directories, *libffa* and *ffademo*, but this time with somewhat different contents. (If you are new to *V*, read the *vpatch* with your naked eye; you will notice that it is almost exactly the same thing as an ordinary Unix diff, and quite readable.)

Now compile the demo, just as in Chapter 1:

cd ffademo gprbuild

And, as before, **do not run it quite yet.**

First, let’s go through the “mail bag” from Chapter 1:

Reader Apeloyee observed that *“xor swap seems to me a rake, which would hit you if the swapped values happen to be stored in the same location.”*

-- Exchange A and B. procedure W_Swap(A : in out Word; B : in out Word) is begin A := A xor B; B := A xor B; A := A xor B; end W_Swap; pragma Inline_Always(W_Swap);

Naturally, it is possible to answer this *“Doctor, it hurts when I do that!”* with the proverbial *“So stop doing that.”* But “rakes” are not acceptable in safety-critical systems.

Reader Mircea Popescu proposed to insert a stern warning, e.g.

pragma Restrictions(No_Implicit_Heap_Allocations); -- Removing this may render the functioning of W_Swap and W_Mux dangerous, -- see http://btcbase.org/log/2017-12-02#1745513 discussion for details

Unfortunately, a dig through the GNAT docs revealed that there is apparently no reliable way to enforce a permanent guarantee that *W_Swap* will not be under any circumstances called on overlapping objects allocated *explicitly*; or used on pairs of variables made to refer to the same memory location via the *renames* construct.

Therefore *W_Swap* has been **removed**; this is reflected in the new vpatch; and *FZ_Swap*, introduced in this chapter, uses a temporary copy, as seen in kindergarten schoolbooks.

I would like to thank Apeloyee and Mircea Popescu for their careful reading; and ask all of my readers not to hesitate in pointing out potentially troublesome (or merely confusing) algorithms, typos, obvious mistakes, etc.

Now let’s proceed to some new material.

There are certain predicates we will need later for use on *Words*:

*w_pred.ads*:

with Words; use Words; package W_Pred is pragma Pure; -- Return 1 if N is equal to 0; otherwise return 0. function W_ZeroP(N : in Word) return WBool; -- Return 1 if N is unequal to 0; otherwise return 0. function W_NZeroP(N : in Word) return WBool; -- Return 1 if N is odd; otherwise return 0. function W_OddP(N : in Word) return WBool; -- Return 1 if A is equal to B ; otherwise return 0. function W_EqP(A : in Word; B : in Word) return WBool; end W_Pred;

*w_pred.adb*:

with Word_Ops; use Word_Ops; package body W_Pred is -- Return 1 if N is equal to 0; otherwise return 0. function W_ZeroP(N : in Word) return WBool is begin return W_Borrow(N, 1, N - 1); end W_ZeroP; pragma Inline_Always(W_ZeroP); -- Return 1 if N is unequal to 0; otherwise return 0. function W_NZeroP(N : in Word) return WBool is begin return 1 xor W_ZeroP(N); end W_NZeroP; pragma Inline_Always(W_NZeroP); -- Return 1 if N is odd; otherwise return 0. function W_OddP(N : in Word) return WBool is begin return 1 and N; end W_OddP; pragma Inline_Always(W_OddP); -- Return 1 if A is equal to B ; otherwise return 0. function W_EqP(A : in Word; B : in Word) return WBool is begin return W_ZeroP(A xor B); end W_EqP; pragma Inline_Always(W_EqP); end W_Pred;

Observe that conditional branches are avoided. *W_ZeroP* is the fundamental operation here; expand the equation on a sheet of paper, referring to the *W_Borrow* from Chapter 1 if you do not remember how the latter works.

Now let’s discuss a few more fundamental operations on *FZ* integers:

*fz_basic.ads*:

with Words; use Words; with FZ_Type; use FZ_Type; package FZ_Basic is pragma Pure; -- N := 0 procedure FZ_Clear(N : out FZ); -- First word of N := Source procedure FZ_Set_Head(N : out FZ; Source : in Word); -- First word of N function FZ_Get_Head(N : in FZ) return Word; -- Exchange X and Y procedure FZ_Swap(X : in out FZ; Y : in out FZ); pragma Precondition(X'Length = Y'Length); -- Constant-time MUX: Sel = 0: Result := X; Sel = 1: Result := Y procedure FZ_Mux(X : in FZ; Y : in FZ; Result : out FZ; Sel : in WBool); pragma Precondition(X'Length = Y'Length and X'Length = Result'Length); end FZ_Basic;

We will go over these one at a time:

*fz_basic.adb*:

with Word_Ops; use Word_Ops; package body FZ_Basic is

The *FZ_Clear* operation illustrates the use of Ada’s array assignment construct. It simply sets a given *FZ* to zero.

-- N := 0 procedure FZ_Clear(N : out FZ) is begin N := (others => 0); end FZ_Clear; pragma Inline_Always(FZ_Clear);

The *FZ_Set_Head* operation changes only the *head*, or “youngest” *Word*, of a given *FZ*, to the given *Word* value.

-- First word of N := Source procedure FZ_Set_Head(N : out FZ; Source : in Word) is begin N(N'First) := Source; end FZ_Set_Head; pragma Inline_Always(FZ_Set_Head);

*FZ_Get_Head* returns the “youngest” (lowest, bottom-most) word of an *FZ*.

-- First word of N function FZ_Get_Head(N : in FZ) return Word is begin return N(N'First); end FZ_Get_Head; pragma Inline_Always(FZ_Get_Head);

This is the Swap operation, as discussed previously in the “mail bag” section of this article.

-- Exchange X and Y procedure FZ_Swap(X : in out FZ; Y : in out FZ) is T : FZ(X'Range) := X; begin T := X; X := Y; Y := T; end FZ_Swap; pragma Inline_Always(FZ_Swap);

It is absolutely vital to understand exactly how and why *FZ_Mux* works. This operation takes two *FZ* inputs, X and Y, and a *WBool* selector, Sel; it assigns X to the Result if Sel equals 0; alternatively, Y if Sel equals 1. Refer to the *W_Mux* material in Chapter 1 to understand how this is done. The Mux operation is a fundamental building block of constant-time (i.e. *branch-free*) arithmetic as seen in FFA.

-- Constant-time MUX: Sel = 0: Result := X; Sel = 1: Result := Y procedure FZ_Mux(X : in FZ; Y : in FZ; Result : out FZ; Sel : in WBool) is begin for i in X'Range loop Result(i) := W_Mux(X(i), Y(i), Sel); end loop; end FZ_Mux; pragma Inline_Always(FZ_Mux); end FZ_Basic;

Now let’s introduce some unary predicate operators that work on *FZ* integers:

*fz_pred.ads*:

with Words; use Words; with FZ_Type; use FZ_Type; package FZ_Pred is pragma Pure; -- 1 iff N == 0 (branch-free); else 0 function FZ_ZeroP(N : in FZ) return WBool; -- 1 iff N is odd function FZ_OddP(N : in FZ) return WBool; end FZ_Pred;

*fz_pred.adb*:

with W_Pred; use W_Pred; package body FZ_Pred is -- 1 iff N == 0 (branch-free); else 0 function FZ_ZeroP(N : in FZ) return WBool is A : WBool := 1; begin for i in N'Range loop A := A and W_ZeroP(N(i)); end loop; return A; end FZ_ZeroP; pragma Inline_Always(FZ_ZeroP); -- 1 iff N is odd function FZ_OddP(N : in FZ) return WBool is begin return W_OddP(N(N'First)); end FZ_OddP; pragma Inline_Always(FZ_OddP); end FZ_Pred;

As before, draw this on a sheet of paper if the mechanism does not immediately stand up in front of your mind’s eye.

Now for some binary comparison predicates on *FZ*:

*fz_cmp.ads*:

with Words; use Words; with FZ_Type; use FZ_Type; package FZ_Cmp is pragma Pure; -- 1 iff X == Y (branch-free); else 0 function FZ_EqP(X : in FZ; Y: in FZ) return WBool; pragma Precondition(X'Length = Y'Length); -- 1 iff X < Y (branch-free); else 0 function FZ_LessThanP(X : in FZ; Y : in FZ) return WBool; pragma Precondition(X'Length = Y'Length); -- 1 iff X > Y (branch-free); else 0 function FZ_GreaterThanP(X : in FZ; Y : in FZ) return WBool; pragma Precondition(X'Length = Y'Length); end FZ_Cmp;

*fz_cmp.adb*:

with W_Pred; use W_Pred; with FZ_Arith; use FZ_Arith; package body FZ_Cmp is -- 1 iff X == Y (branch-free); else 0 function FZ_EqP(X : in FZ; Y : in FZ) return WBool is A : WBool := 1; begin for i in X'Range loop A := A and W_EqP(X(i), Y(i)); end loop; return A; end FZ_EqP; pragma Inline_Always(FZ_EqP); -- 1 iff X < Y (branch-free); else 0 function FZ_LessThanP(X : in FZ; Y : in FZ) return WBool is Scratch : FZ(X'Range); Borrow : WBool := 0; begin FZ_Sub(X, Y, Scratch, Borrow); return Borrow; end FZ_LessThanP; pragma Inline_Always(FZ_LessThanP); -- 1 iff X > Y (branch-free); else 0 function FZ_GreaterThanP(X : in FZ; Y: in FZ) return WBool is Scratch : FZ(X'Range); Borrow : WBool := 0; begin FZ_Sub(Y, X, Scratch, Borrow); return Borrow; end FZ_GreaterThanP; pragma Inline_Always(FZ_GreaterThanP); end FZ_Cmp;

Here we make use of *W_EqP* from earlier in this chapter.

Observe that these work in exactly the same way as a commonplace CPU’s ALU does. Refer to the material in Chapter 1 concerning branch-free subtraction.

Now for some bitwise operators on *FZ* integers:

*fz_bitop.ads*:

with FZ_Type; use FZ_Type; with Words; use Words; package FZ_BitOp is pragma Pure; -- Result := X & Y procedure FZ_And(X : in FZ; Y : in FZ; Result : out FZ); pragma Precondition(X'Length = Y'Length and X'Length = Result'Length); -- N := N & W, W is a word procedure FZ_And_W(N : in out FZ; W : in Word); -- Result := X | Y procedure FZ_Or(X : in FZ; Y : in FZ; Result : out FZ); pragma Precondition(X'Length = Y'Length and X'Length = Result'Length); -- N := N | W, W is a word procedure FZ_Or_W(N : in out FZ; W : in Word); -- Result := X ^ Y procedure FZ_Xor(X : in FZ; Y : in FZ; Result : out FZ); pragma Precondition(X'Length = Y'Length and X'Length = Result'Length); -- N := N ^ W, W is a word procedure FZ_Xor_W(N : in out FZ; W : in Word); -- NotN := ~N procedure FZ_Neg(N : in FZ; NotN : out FZ); pragma Precondition(N'Length = NotN'Length); end FZ_BitOp;

*fz_bitop.adb*:

package body FZ_BitOp is -- Result := X & Y procedure FZ_And(X : in FZ; Y : in FZ; Result : out FZ) is begin for i in X'Range loop Result(i) := X(i) and Y(i); end loop; end FZ_And; pragma Inline_Always(FZ_And); -- N := N & W, W is a word procedure FZ_And_W(N : in out FZ; W : in Word) is begin N(N'First) := N(N'First) and W; end FZ_And_W; pragma Inline_Always(FZ_And_W); -- Result := X | Y procedure FZ_Or(X : in FZ; Y : in FZ; Result : out FZ) is begin for i in X'Range loop Result(i) := X(i) or Y(i); end loop; end FZ_Or; pragma Inline_Always(FZ_Or); -- N := N | W, W is a word procedure FZ_Or_W(N : in out FZ; W : in Word) is begin N(N'First) := N(N'First) or W; end FZ_Or_W; pragma Inline_Always(FZ_Or_W); -- Result := X ^ Y procedure FZ_Xor(X : in FZ; Y : in FZ; Result : out FZ) is begin for i in X'Range loop Result(i) := X(i) xor Y(i); end loop; end FZ_Xor; pragma Inline_Always(FZ_Xor); -- N := N ^ W, W is a word procedure FZ_Xor_W(N : in out FZ; W : in Word) is begin N(N'First) := N(N'First) xor W; end FZ_Xor_W; pragma Inline_Always(FZ_Xor_W); -- NotN := ~N procedure FZ_Neg(N : in FZ; NotN : out FZ) is begin for i in N'Range loop NotN(i) := not N(i); end loop; end FZ_Neg; pragma Inline_Always(FZ_Neg); end FZ_BitOp;

None of these make use of any kind of “cleverness”.

All but the unary *FZ_Neg* operator are defined both for pairs of *FZ* integers and also for an *FZ* and *Word* pairing; in the latter case, the operation is performed against the “head” of the *FZ*.

Now, let’s make a demo for the routines in this Chapter:

*demo_ch2.ads*:

package Demo_Ch2 is procedure Demo_Word_Preds; procedure Demo_FZ_Basics; procedure Demo_FZ_Various_Ops; end Demo_Ch2;

*demo_ch2.adb*:

-- From Ada: with Ada.Text_IO; use Ada.Text_IO; -- From FFA: with Words; use Words; with FZ_Type; use FZ_Type; with FZ_Arith; use FZ_Arith; -- FFA Ch. 2 with W_Pred; use W_Pred; with FZ_Basic; use FZ_Basic; with FZ_Pred; use FZ_Pred; with FZ_BitOp; use FZ_BitOp; with FZ_Cmp; use FZ_Cmp; -- From the Demo: with FFA_IO; use FFA_IO; package body Demo_Ch2 is procedure Demo_Word_Preds is begin Put_Line("~~~ Ch. 2 : Word Predicates ~~~"); New_Line; Put_Line("W_ZeroP(0) :"); Dump(W_ZeroP(0)); New_Line; New_Line; Put_Line("W_ZeroP(1) :"); Dump(W_ZeroP(1)); New_Line; New_Line; Put_Line("W_NZeroP(1) :"); Dump(W_NZeroP(1)); New_Line; New_Line; Put_Line("W_OddP(3) :"); Dump(W_OddP(3)); New_Line; New_Line; Put_Line("W_EqP(1, 1) :"); Dump(W_EqP(1, 1)); New_Line; New_Line; Put_Line("W_EqP(1, 0) :"); Dump(W_EqP(1, 0)); New_Line; New_Line; end Demo_Word_Preds; procedure Demo_FZ_Basics is X : FZ(1 .. 4) := ( 0, 0, 0, 0); -- Shorthand for 'maxint' Y : FZ(1 .. 4) := (-1, -1, -1, -1); Z : FZ(1 .. 4) := ( 0, 0, 0, 0); -- Flag. F : WBool := 0; begin Put_Line("~~~ Ch. 2 : FZ Basics ~~~"); New_Line; Put_Line("X ="); Dump(X); New_Line; New_Line; Put_Line("Y ="); Dump(Y); New_Line; New_Line; Put_Line("FZ_ZeroP(X) :"); Dump(FZ_ZeroP(X)); New_Line; New_Line; Put_Line("FZ_ZeroP(Y) :"); Dump(FZ_ZeroP(Y)); New_Line; New_Line; FZ_Swap(X, Y); Put_Line("After FZ_Swap(X, Y) :"); Put_Line("X ="); Dump(X); New_Line; New_Line; Put_Line("Y ="); Dump(Y); New_Line; New_Line; F := 0; FZ_Mux(X, Y, Z, F); Put_Line("After F := 0 , FZ_Mux(X, Y, Z, F) : "); Put_Line("Z ="); Dump(Z); New_Line; New_Line; F := 1; FZ_Mux(X, Y, Z, F); Put_Line("After F := 1 , FZ_Mux(X, Y, Z, F) : "); Put_Line("Z ="); Dump(Z); New_Line; New_Line; end Demo_FZ_Basics; procedure Demo_FZ_Various_Ops is X : FZ(1 .. 4) := ( 16#083e16f27091f65f#, 16#74c01a9c3ce54f80#, 16#9fd0913737c3fcbe#, 16#fa55f3f5459a9e79# ); Y : FZ(1 .. 4) := ( 16#d16b9d65bf3991d0#, 16#8a509a858786b366#, 16#d39d23682728f4f8#, 16#6c571dbc646bf513# ); Z : FZ(1 .. 4) := ( 0, 0, 0, 0 ); begin Put_Line("~~~ Ch. 2 : FZ Bit Ops ~~~"); New_Line; New_Line; Put_Line("X ="); Dump(X); New_Line; New_Line; Put_Line("Y ="); Dump(Y); New_Line; New_Line; FZ_Neg(X, Z); Put_Line("After FZ_Neg(X, Z):"); Put_Line("Z ="); Dump(Z); New_Line; New_Line; FZ_And(X, Y, Z); Put_Line("After FZ_And(X, Y, Z) :"); Put_Line("Z ="); Dump(Z); New_Line; New_Line; FZ_Or(X, Y, Z); Put_Line("After FZ_Or(X, Y, Z) :"); Put_Line("Z ="); Dump(Z); New_Line; New_Line; FZ_Xor(X, Y, Z); Put_Line("After FZ_Xor(X, Y, Z) :"); Put_Line("Z ="); Dump(Z); New_Line; New_Line; Put_Line("FZ_EqP(X, X) :"); Dump(FZ_EqP(X, X)); New_Line; New_Line; Put_Line("FZ_EqP(X, Y) :"); Dump(FZ_EqP(X, Y)); New_Line; New_Line; Put_Line("FZ_LessThanP(X, Y) :"); Dump(FZ_LessThanP(X, Y)); New_Line; New_Line; Put_Line("FZ_LessThanP(Y, X) :"); Dump(FZ_LessThanP(Y, X)); New_Line; New_Line; Put_Line("FZ_GreaterThanP(X, Y) :"); Dump(FZ_GreaterThanP(X, Y)); New_Line; New_Line; Put_Line("FZ_GreaterThanP(Y, X) :"); Dump(FZ_GreaterThanP(Y, X)); New_Line; New_Line; end Demo_FZ_Various_Ops; end Demo_Ch2;

*ffa_demo.adb*:

with Demo_Ch1; use Demo_Ch1; with Demo_Ch2; use Demo_Ch2; procedure FFA_Demo is begin -- Ch. 1 Demo_Add_Sub; -- Ch. 2 Demo_Word_Preds; Demo_FZ_Basics; Demo_FZ_Various_Ops; end FFA_Demo;

Finally, let’s run it:

./bin/ffa_demo

And this is what you should see:

~~~ Ch. 1 : Add, Sub ~~~ X = 0000000000000000000000000000000000000000000000000000000000000000 Y = 0000000000000000000000000000000000000000000000000000000000005555 X + Y = 0000000000000000000000000000000000000000000000000000000000005555 C = 0 X - Y = FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFAAAB C = 1 ~~~ Ch. 2 : Word Predicates ~~~ W_ZeroP(0) : 0000000000000001 W_ZeroP(1) : 0000000000000000 W_NZeroP(1) : 0000000000000001 W_OddP(3) : 0000000000000001 W_EqP(1, 1) : 0000000000000001 W_EqP(1, 0) : 0000000000000000 ~~~ Ch. 2 : FZ Basics ~~~ X = 0000000000000000000000000000000000000000000000000000000000000000 Y = FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF FZ_ZeroP(X) : 0000000000000001 FZ_ZeroP(Y) : 0000000000000000 After FZ_Swap(X, Y) : X = FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF Y = 0000000000000000000000000000000000000000000000000000000000000000 After F := 0 , FZ_Mux(X, Y, Z, F) : Z = FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF After F := 1 , FZ_Mux(X, Y, Z, F) : Z = 0000000000000000000000000000000000000000000000000000000000000000 ~~~ Ch. 2 : FZ Bit Ops ~~~ X = FA55F3F5459A9E799FD0913737C3FCBE74C01A9C3CE54F80083E16F27091F65F Y = 6C571DBC646BF513D39D23682728F4F88A509A858786B366D16B9D65BF3991D0 After FZ_Neg(X, Z): Z = 05AA0C0ABA656186602F6EC8C83C03418B3FE563C31AB07FF7C1E90D8F6E09A0 After FZ_And(X, Y, Z) : Z = 685511B4440A9411939001202700F4B800401A8404840300002A146030119050 After FZ_Or(X, Y, Z) : Z = FE57FFFD65FBFF7BDFDDB37F37EBFCFEFED09A9DBFE7FFE6D97F9FF7FFB9F7DF After FZ_Xor(X, Y, Z) : Z = 9602EE4921F16B6A4C4DB25F10EB0846FE908019BB63FCE6D9558B97CFA8678F FZ_EqP(X, X) : 0000000000000001 FZ_EqP(X, Y) : 0000000000000000 FZ_LessThanP(X, Y) : 0000000000000000 FZ_LessThanP(Y, X) : 0000000000000001 FZ_GreaterThanP(X, Y) : 0000000000000001 FZ_GreaterThanP(Y, X) : 0000000000000000

*~To be continued!~*