“Finite Field Arithmetic.” Chapter 2: Logical and Bitwise Operations.

Published on: Friday December 08 2017

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.

You will need:

Add the above vpatch and seal to your V-set, and press to ffa_ch2_logicals.kv.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://logs.nosuchlabs.com/ilog/trilema/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!~
This entry was written by Stanislav , posted on Friday December 08 2017 , filed under Ada, Bitcoin, Cold Air, Computation, Cryptography, FFA, Friends, Mathematics, NonLoper, ShouldersGiants, SoftwareSucks . Bookmark the permalink . Post a comment below or leave a trackback: Trackback URL.

12 Responses to ““Finite Field Arithmetic.” Chapter 2: Logical and Bitwise Operations.”

  • apeloyee says:
    December 10, 2017 at 6:15 am

    A bit odd to see FZ_Neg to be named, unlike other SIMD bit operations, differently from the corresponding Ada operation on words. I personally would expect that "Neg" is arithmetic negation, since other operations aren't named FZ_Conj or FZ_Disj...

    Reply
  • PeterL says:
    December 23, 2017 at 8:07 am

    And I signed this one: fa_ch2_logicals.vpatch.peterl.sig

    -----BEGIN PGP SIGNATURE-----
    Version: GnuPG v1

    iQIcBAABAgAGBQJaNUD9AAoJELTi4Nystj0l/boP/2FEj22/fxVMQarj5zawgzRc
    20L8as38S+TeErxXzbbva7fdZDTIGxCHlACSg1VGj7qK8ZNEf+oBqtN6SnR7M2ys
    n+RkQEeOmX85YH/b6duCKv1kpqsd+XSukps6KcrE6fOZzm47H68rlH9VlUw/iGav
    CV//SlfGQilF5PgKiBkGB3srSk2D3yhAyvds5FuwcQT80L4jjLaWsOxwI8/WK4HV
    W9wU1tMbD/Qmy/qafPGmFd7GskizLHz7LNO/JhdnqlhI+slXjg61E3grfu7VwdB7
    0Kh6a34UjeL5dhoEiRBLj8yVS1ds5Q8JISI+VhaXff0a5L2RrYVgHsxc6r1McFSe
    WHOA+6lgwXZCcC634vCIkwn1+qiQ4zI+oX+EkTY+AEjMYooBixTRh5G3cyjmLlfO
    NSgQi6+LdHf7NZRAyQ2dSZca6uWczURLMbrGxYmYZ5dpj7dx9GzQ7ipj0uWvUvp6
    zADX+8DIv4lkP+Wyqrzc7l3LmJxYse6+bf0xW29FlpiOv3XFzpAuNfO385HtNBUX
    QaEn8TkDpDUfAqo2pR8qoTzIOuuwP6Nm40Q+ag9it8j8Y7NLZqX5V482zcLEDKGx
    MMr3fDVBg52cCIILjjuS+YluFMfcSnlWAQ5UITf15tDByqoclky+xRogdbz2iWAi
    YgvWahPTXNo7Z8dGeZyM
    =Ef2C
    -----END PGP SIGNATURE-----

    Reply
  • spyked says:
    January 4, 2018 at 10:13 am

    Dear Stan,

    I have a (somewhat offtopic) curiosity regarding Ada's restrictions used in FFA, and I couldn't find any specific answers in the Ada documentation. For example the FZ_Swap implementation above instantiates an array (T) whose size depends on the input, so the size of T can vary between calls to FZ_Swap. Why doesn't this require a secondary stack?

    I am asking because I have been wrestling with passing strings as arguments for Adalisp, and I gave up due to the secondary stack restriction. I understand there is a difference in the way Ada handles arrays and (unconstrained) strings, but I haven't been able to figure it out. Any ideas?

    Reply
    • Stanislav says:
      January 4, 2018 at 10:32 am

      Dear spyked,

      When we use a dynamically-sized array, like T and similar items, inside a procedure, it gets placed on the primary stack, by simply winding the stack frame forward. Exactly like how inner blocks in the C language work.

      But when unconstrained strings and other unconstrained arrays get returned as values, this requires copying. They get thrown onto the secondary stack. For detail, see e.g. this article.

      Yours,
      -S

      Reply
  • Benjamin Vulpes says:
    January 11, 2018 at 1:38 am

    Here's the missing sig. A+++ good reread, would and will reread again.

    -----BEGIN PGP SIGNATURE-----

    iQIcBAABCgAGBQJaVwY4AAoJEPAbzAMu8lJHIdkP/1oTnfAT0hZhcJxSVClVUT67
    QpC3lg0ayVmcmrGlRny5siXFJys3bUEnFBL9cYsImtVrWDL06jkzsyxrHeTrFvHj
    1B2T+hF5QBaGjpJQycYaWd9tyX1jhBeADKe54Ahg5nw2xr1CTaJvAhJwp0dzO+0D
    2u5xg4Hof1IqEqGCDobDGXpzPPVTYmH0yqFWJFw0njm4slud+8d3NEcdDrFvFpN9
    clRbD3nSDuTrrwsIGJSuDehLuQ5b5S2gM8vRlEwXh5sYjOCreKI90sca3B+Ts4st
    IhNZZGSOEpmzaNsCIpgaywlNO/PYoN1jePlKlfmEo2kzwADp7c0dDeSISUAVVzNp
    t1RYRp42yKsGB1TMWJRws7cJ4wSesvFVf4dW6yFDeX0773L+8GeR2JsBPGj3hlRp
    PucO0NMpL7FLCDWt1RkhNO3atnEWZJlwnnpOBqJhPrlPp0jIgp/50Ms1eILPVkVi
    a6gyRSkjU0g5xKHkp2pii9c8jzqulbxN6VwjTlTRSjGMVcbz0vIDhDIQKxOg1xZh
    +J+voqNXlBLcBdppdjAP2uhGL6mP2cnYxywK9dVUJEAkroADDQEMKaO795BxNfMi
    AeoxTucjnJzgfAfx2FEW8h1AP1rm2EjbEVgXXuuX611SZzHwGMGOOhf2Rle0SOmJ
    52CqN98IEc9M7vj+bNRe
    =YFnS
    -----END PGP SIGNATURE-----

    Reply
  • ave1 says:
    February 12, 2018 at 7:22 am

    Dear Stanislav,

    I highly appreciate your series and I finally finished reading this chapter. Please find my notes here.

    Cheers,

    Arjen
    Reply

    Reply
  • shinohai says:
    November 16, 2019 at 2:43 pm

    My signature for Ch.2, also posted to my site in same place as stated in previous comment.

    -----BEGIN PGP SIGNATURE-----

    iQIzBAABCgAdFiEEJg+le85nelwEv2C6SnWIPMGx00wFAl3QUMkACgkQSnWIPMGx
    00xN4g//f+6ArvUd4N2jqQ0YGBI1WhILDjYbtxZbL6YISd2I3iGttvsBEApmoFhw
    QOZzUquxaWMOUMUvpi/qkyL7qrmOoTa10/RzKDrPUFXxGGY4MX6BqG6jrhHv3Vaz
    Rxb9cbGr12Kz6p0aw2PxMzxvNPn1X+4/oy3buL8t/GfJeBq0GevqnH1GbItLhgmX
    MojlamiFp/0OS401kMpP4PURDeXgr40acM9JRakm6hEZfUuSaCd+nJgQfIO0bPJZ
    Y+zYvZhmQx7XMtBXgFyLp7hR+WyEUVHs6z45fWZxEN8c8qO8TyUvhfNIaeEHoPbX
    KXceSudyGT7Znz4M6KlYepSTfcxRkC3YuNKFqOYDuJngaUr19JVjjzJVxT53kJW2
    VRxrdgiBMx/Jrg5ELcL7n+RYgJW+vxV3bS8mjJgmA/mxlJcgH8R3UFqiaBrgiSt/
    NHKbk8qGgB05IurrIRNbFKowcJNO++w4ZIfh+59R9LhcgdpCURf158QSYt6rv8vB
    D3CBjwGWiDWp/ntj1K7bbsnd/z6oxaSoiic02YrSDRBjq1Cg40eIeBwdXRUJ1W9t
    /jno3uXglIhAf/IcZvxfRgl2fS2BoE4A8B6K88OkWvRYPFQxQ2d8xF5xsZzmgCY7
    tHvbMjCPSWbYvrKPnqKkFKX5YvSHj5DPbCh3pke7QZYWCe+ms90=
    =2btv
    -----END PGP SIGNATURE-----

    Reply
  • shinohai says:
    November 17, 2019 at 3:49 pm

    Updated sig for ffa_ch2_logicals.kv.vpatch:

    -----BEGIN PGP SIGNATURE-----

    iQIzBAABCgAdFiEEJg+le85nelwEv2C6SnWIPMGx00wFAl3Rr4sACgkQSnWIPMGx
    00zREw/8C/b83rtC1BxmxvVZGCwd93TPFdAB5ZfgAyGiqRk0i3QohDnRU/NzY7Bz
    AP0yQjT5g13LvhD0Ni8hV1XMC7WNSgEGm6h/gSAY4xM6QpkjiVdsy8mU2R2sMxJz
    rvLq1cbK7+OXutKmJArL/UtidoH0hQjQTpWobto+hJGrbaWdegNHkpjNIbLha/ra
    K+r7a00cn7k9ZEGhoCOvjp52rhCAQJgfdM9m8kOJSsz9MfhIAAUQFL1v6SOyNOgQ
    Rzajn+fhkgvZs/BH9oCObFM4OGra58+Jn6faMbnZnMCsfZdpuW2T7JfcrY/RAoKI
    uatnedPxEKIX0zmMBf7XVHphvf2wZodTUsEWLV8RN9Vfyq5S5S/mpAaK0sZfOqlV
    rnCrRxqd2k2I00F4u3WwDEDMELawie7Wn1XUDdIwm5YHtyh/MqHoCF95qMsJ9Gdk
    IF8IL9zmB9SIZdrq28HinA0f6JZw5/JwdA6aiuDOv3kZn+CuQBX0Pwh31yS/uejz
    9niXrZver8CS7lULSh4X2snkVLDDLdumOc0EcoeccVGum+uDXUxoCAJiJbMV3szW
    MW+wcgvoY35U7OkEkULwXTUu+Uo+uxFO7gu12QlH/qSEb/9CHqv4+ucwTfeYpoB+
    q8YlByOz1lN33+x6IGTa/Rf/ug0AjAv6szza9JrqwaHcJoyvKG4=
    =NQV3
    -----END PGP SIGNATURE-----

    Reply

Leave a Reply

XHTML: You can use these tags: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong> <pre lang="" line="" escaped="" highlight="">


MANDATORY: Please prove that you are human:

86 xor 96 = ?

What is the serial baud rate of the FG device ?


Answer the riddle correctly before clicking "Submit", or comment will NOT appear! Not in moderation queue, NOWHERE!

« »