“Finite Field Arithmetic.” Chapter 3: Shifts.

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_ch3_shifts.kv.vpatch.

Just like before, you will end up with two directories, libffa and ffademo.

Now compile the demo, just as in Chapters 1 and 2:

cd ffademo
gprbuild

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


First, let's go through the "mail bag" from Chapter 2:

Reader Apeloyee observed : "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."

   -- 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);

He's quite right, and henceforth the FFA ones-complement operator will be called FZ_Not.

Reader Diana Coman noticed the duplicate assignment to T in FZ_Swap:

   -- 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);

The renaming of the ones-complement operator, and the removal of the redundant assignment to T in FZ_Swap appear in this Chapter's vpatch.

I would like to thank Apeloyee and Diana Coman 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 new material: shift operators for FZ integers :

fz_shift.ads:

 
with Words;   use Words;
with FZ_Type; use FZ_Type;
 
 
package FZ_Shift is
 
   pragma Pure;
 
   --------------------------------------------------------------
   -- Shift Right
   --------------------------------------------------------------
 
   -- ShiftedN := N >> Count (with Overflow Input and Output)
   procedure FZ_ShiftRight_O_I(N        : in  FZ;
                               ShiftedN : out FZ;
                               Count    : in  WBit_Index;
                               Overflow : out Word;
                               OF_in    : in  Word);
   pragma Precondition(N'Length = ShiftedN'Length);
 
   -- ShiftedN := N >> Count (with Overflow Output only)
   procedure FZ_ShiftRight_O(N        : in  FZ;
                             ShiftedN : out FZ;
                             Count    : in  WBit_Index;
                             Overflow : out Word);
   pragma Precondition(N'Length = ShiftedN'Length);
 
   -- ShiftedN := N >> Count (no Overflow output or input)
   procedure FZ_ShiftRight(N        : in  FZ;
                           ShiftedN : out FZ;
                           Count    : in  WBit_Index);
   pragma Precondition(N'Length = ShiftedN'Length);
 
   --------------------------------------------------------------
   -- Shift Left
   --------------------------------------------------------------
 
   -- ShiftedN := N < < Count (with Overflow Input and Output)
   procedure FZ_ShiftLeft_O_I(N        : in  FZ;
                              ShiftedN : out FZ;
                              Count    : in  WBit_Index;
                              Overflow : out Word;
                              OF_in    : in  Word);
   pragma Precondition(N'Length = ShiftedN'Length);
 
   -- ShiftedN := N << Count (with Overflow Output only)
   procedure FZ_ShiftLeft_O(N        : in  FZ;
                            ShiftedN : out FZ;
                            Count    : in  WBit_Index;
                            Overflow : out Word);
   pragma Precondition(N'Length = ShiftedN'Length);
 
   -- ShiftedN := N << Count (no Overflow output or input)
   procedure FZ_ShiftLeft(N        : in  FZ;
                          ShiftedN : out FZ;
                          Count    : in  WBit_Index);
   pragma Precondition(N'Length = ShiftedN'Length);
 
end FZ_Shift;

The basic building blocks for shifts are FZ_ShiftRight_O_I and FZ_ShiftLeft_O_I. The other operators shown are simply shorthand notation for discarding the ability to take the overflow from, or place incoming shifted-in bits into, one of these operations. This convention is followed in order to avoid littering FFA and user code with declarations for unused variables and the pragma Unreferenced(...) statements to go with them.

Note that the overflow inputs and outputs are Words, rather than WBools. The reason for this will become apparent shortly.

Observe that, thus far, it is only possible to shift an FZ by a WBit_Index quantity. Recall from words.ads in Chapter 1:

   -- When we must refer to individual bit positions of a machine word:
   subtype WBit_Index is Natural range 0 .. Bitness - 1;

This means that, in the 64-bit example code provided, left- and right- shifts from 0 to 63 binary positions are permissible.

In a later chapter we will see arbitrary (i.e. up to the full width of an FZ) constant-time shifting algorithms. However for most of FFA's functionality, these are not necessary, so there is no need to introduce them to the reader quite yet.

Let's proceed to the essential moving parts of the Right and Left subword shifts:

fz_shift.adb:

with W_Shifts; use W_Shifts;
 
 
package body FZ_Shift is
 
   -- ShiftedN := N >> Count (with Overflow Input and Output)
   procedure FZ_ShiftRight_O_I(N        : in  FZ;
                               ShiftedN : out FZ;
                               Count    : in  WBit_Index;
                               Overflow : out Word;
                               OF_in    : in  Word) is
      Ni    : Word;
      Carry : Word := OF_in;
   begin
      for i in reverse N'Range loop
         Ni := N(i);
         ShiftedN(i) := Shift_Right(Ni, Count) or Carry;
         Carry := Shift_Left(Ni, Bitness - Count);
      end loop;
      Overflow := Carry;
   end FZ_ShiftRight_O_I;
   pragma Inline_Always(FZ_ShiftRight_O_I);

Shifting a FZ integer to the right by Count binary places, is done in the following way. We walk the Words comprising the FZ from highest to lowest (hence the reverse in the looping operator.)

Inside the loop, we make a temporary copy of the current word N(i), Ni. Then we shift Ni by the requested number of binary places, Count; and bitwise-OR the current Carry into its high bits. This Carry is equal to OF_in initially (typically zero, if nothing is being shifted in). The result of the OR is saved to ShiftedN(i) -- we have obtained the current Word of the final output.

For every Word after the first one operated on, Carry consists of that previous Word's "dropped" bits, shifted left so as to end up OR-ed into the upper end of the next Word. The Carry obtained from the last Word's shifting is written to Overflow.

Observe that it is entirely legal to call FZ_ShiftRight_O_I "in-place", i.e. with the input and output locations being the same FZ.

Now we'll define an operator that wraps the above, but does not require bits being "shifted in" to be provided:

   -- ShiftedN := N >> Count (with Overflow Output only)
   procedure FZ_ShiftRight_O(N        : in  FZ;
                             ShiftedN : out FZ;
                             Count    : in  WBit_Index;
                             Overflow : out Word) is
   begin
      FZ_ShiftRight_O_I(N, ShiftedN, Count, Overflow, 0);
   end FZ_ShiftRight_O;
   pragma Inline_Always(FZ_ShiftRight_O);

And here is one that gives neither Overflow output nor demands shifted-in input:

   -- ShiftedN := N >> Count (no Overflow output or input)
   procedure FZ_ShiftRight(N        : in  FZ;
                           ShiftedN : out FZ;
                           Count    : in  WBit_Index) is
      Overflow : Word;
      pragma Unreferenced(Overflow);
   begin
      FZ_ShiftRight_O_I(N, ShiftedN, Count, Overflow, 0);
   end FZ_ShiftRight;
   pragma Inline_Always(FZ_ShiftRight);

The process of shifting a FZ integer to the left by Count binary places, is exactly analogous to the right-shift, with one exception: we begin with the lowest Word in the FZ, and proceed "up" :

   -- ShiftedN := N < < Count (with Overflow Input and Output)
   procedure FZ_ShiftLeft_O_I(N        : in  FZ;
                              ShiftedN : out FZ;
                              Count    : in  WBit_Index;
                              Overflow : out Word;
                              OF_in    : in  Word) is
      Ni    : Word;
      Carry : Word := OF_in;
   begin
      for i in N'Range loop
         Ni := N(i);
         ShiftedN(i) := Shift_Left(Ni, Count) or Carry;
         Carry := Shift_Right(Ni, Bitness - Count);
      end loop;
      Overflow := Carry;
   end FZ_ShiftLeft_O_I;
   pragma Inline_Always(FZ_ShiftLeft_O_I);

It is very much a "mirror image" of the FZ_ShiftRight_O_I algorithm.

Now for the "wrappers", in exactly the same spirit as earlier:

   -- ShiftedN := N < < Count (with Overflow Output only)
   procedure FZ_ShiftLeft_O(N        : in  FZ;
                            ShiftedN : out FZ;
                            Count    : in  WBit_Index;
                            Overflow : out Word) is
   begin
      FZ_ShiftLeft_O_I(N, ShiftedN, Count, Overflow, 0);
   end FZ_ShiftLeft_O;
   pragma Inline_Always(FZ_ShiftLeft_O);
 
 
   -- ShiftedN := N << Count (no Overflow output or input)
   procedure FZ_ShiftLeft(N        : in  FZ;
                          ShiftedN : out FZ;
                          Count    : in  WBit_Index) is
      Overflow : Word;
      pragma Unreferenced(Overflow);
   begin
      FZ_ShiftLeft_O_I(N, ShiftedN, Count, Overflow, 0);
   end FZ_ShiftLeft;
   pragma Inline_Always(FZ_ShiftLeft);
 
end FZ_Shift;

Just as in prior Chapters, I advise the reader to make abundant use of grid paper and pen, to properly fit the mechanics of the given algorithms into his head -- until they are as comfortably understood as a favourite armchair.


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

demo_ch3.ads:

package Demo_Ch3 is
 
   procedure Demo_Shifts;
 
end Demo_Ch3;

demo_ch3.adb:

-- From Ada:
with Ada.Text_IO; use Ada.Text_IO;
 
-- From FFA:
with Words;    use Words;
with FZ_Type;  use FZ_Type;
 
-- FFA Ch. 3
with FZ_Shift; use FZ_Shift;
 
-- From the Demo:
with FFA_IO;   use FFA_IO;
 
 
package body Demo_Ch3 is
 
   procedure Demo_Shifts is
 
      X : FZ(1 .. 4) := ( 16#083e16f27091f65f#,  16#74c01a9c3ce54f80#,
                          16#9fd0913737c3fcbe#,  16#fa55f3f5459a9e79# );
 
      Z : FZ(1 .. 4) := ( 0,  0,  0,  0 );
 
      -- Overflow
      O : Word := 0;
 
   begin
 
      Put_Line("~~~ Ch. 3 : Shifts ~~~");
      New_Line;
 
      Put_Line("X         =");
      Dump(X);
      New_Line;
      New_Line;
 
      -- Left Shifts:
 
      FZ_ShiftLeft_O(X, Z, 1, O);
      Put_Line("X < < 1    =");
      Dump(Z);
      New_Line;
      Put_Line("Overflow  = ");
      Dump(O);
      New_Line;
 
      FZ_ShiftLeft_O(X, Z, 13, O);
      Put_Line("X << 13   =");
      Dump(Z);
      New_Line;
      Put_Line("Overflow  = ");
      Dump(O);
      New_Line;
 
      FZ_ShiftLeft_O(X, Z, 40, O);
      Put_Line("X << 40   =");
      Dump(Z);
      New_Line;
      Put_Line("Overflow  = ");
      Dump(O);
      New_Line;
 
      -- Right Shifts:
 
      FZ_ShiftRight_O(X, Z, 1, O);
      Put_Line("X >> 1    =");
      Dump(Z);
      New_Line;
      Put_Line("Overflow  = ");
      Dump(O);
      New_Line;
 
      FZ_ShiftRight_O(X, Z, 13, O);
      Put_Line("X >> 13   =");
      Dump(Z);
      New_Line;
      Put_Line("Overflow  = ");
      Dump(O);
      New_Line;
 
      FZ_ShiftRight_O(X, Z, 40, O);
      Put_Line("X >> 40   =");
      Dump(Z);
      New_Line;
      Put_Line("Overflow  = ");
      Dump(O);
      New_Line;
 
   end Demo_Shifts;
 
end Demo_Ch3;

ffa_demo.adb:

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

Finally, let's run it:

./bin/ffa_demo

And this is what you should see:

~~~ ... Output from earlier Chapters snipped ... ~~~
~~~ ............................................ ~~~
 
~~~ Ch. 3 : Shifts ~~~
 
X         =
FA55F3F5459A9E799FD0913737C3FCBE74C01A9C3CE54F80083E16F27091F65F
 
X < < 1    =
F4ABE7EA8B353CF33FA1226E6F87F97CE980353879CA9F00107C2DE4E123ECBE
Overflow  = 
0000000000000001
X << 13   =
BE7EA8B353CF33FA1226E6F87F97CE980353879CA9F00107C2DE4E123ECBE000
Overflow  = 
0000000000001F4A
X << 40   =
9A9E799FD0913737C3FCBE74C01A9C3CE54F80083E16F27091F65F0000000000
Overflow  = 
000000FA55F3F545
X >> 1    =
7D2AF9FAA2CD4F3CCFE8489B9BE1FE5F3A600D4E1E72A7C0041F0B793848FB2F
Overflow  = 
8000000000000000
X >> 13   =
0007D2AF9FAA2CD4F3CCFE8489B9BE1FE5F3A600D4E1E72A7C0041F0B793848F
Overflow  = 
B2F8000000000000
X >> 40   =
0000000000FA55F3F5459A9E799FD0913737C3FCBE74C01A9C3CE54F80083E16
Overflow  = 
F27091F65F000000

~To be continued!~

This entry was written by Stanislav , posted on Friday December 15 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.

14 Responses to ““Finite Field Arithmetic.” Chapter 3: Shifts.”

  • PeterL says:

    This one looks good too, I am eagerly awaiting chapter 4.
    ffa_ch3_shifts.vpatch.peterl.sig

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

    iQIcBAABAgAGBQJaNUEcAAoJELTi4Nystj0luXwP/0gPTu5+4BcapKw8C4YSuucR
    P55gwuegC77KAN4VlLGQLnTdhw7lgLjmqUqscAXEdHLbe1C9PVSAIgM7vdUBa9SP
    lJUv8CUILtLpPFA6M+HpxzRfqCm6HKKdMo3C/LQa6jS0QM6qvO/34bba2vHY7iF9
    C7ZEXt4ZO79cosGPZoBt0yZ3e4MRKv6EHfjd1k0hont1BZ1akYsYJDGcD1OR/RVC
    yyrrS+YnRB8d8pdbgxzcU3U1M58KtTSVO22Kp0iPWAt2Jkvqcm2qJYIYvptU5YyI
    /k+ZgVoPt96MNQ2l0I43omLrFgo0gQtVuKSQugFsICteDnHdxdr0oRwLuVi27UIh
    kycAUmioz6jEBttYfMfOhr8e0bTerb95i/hJ8LQxcxkR4DEBxKTRj+PBDLSllCax
    GMTMkB1rktK6CidL2x0Oir2eu+ZTPTHdq0Hk/LyIm1tzeVvsM4nIiAw6/QLQUqs2
    W+Z0ozO9sO/kmhF+kG4IQWGtnwgW0fMihVfkl7Pzyj/gUc3dUcmdYoZzqJG+Eplt
    iNPBeVg68n8hdZ2TbxDYxxbAWQCIUdr6sK8kolZAYIjIIv8wj/KeWByfLKbsgC4x
    dNDdlpQBgp5cO+KmfSnL21QSMmdhtJ643vCOZ7B9z/1Cq+y+56DmRPlMmp2qkqsY
    ZFdtfkBrDoTKQyywYZhb
    =3PG8
    -----END PGP SIGNATURE-----

  • -----BEGIN PGP SIGNATURE-----
    
    iQIcBAABCgAGBQJaRb1tAAoJEPAbzAMu8lJHrzYP/2LEl0+sxWC58TiiAvVRpk52
    CF5ZNUCXwcRHIrIr3Mpj+ylXxVm6RwvdpcKvaBwkm8qSBOFYILzbiDPCK+qMy4dH
    sAJ8TrT6J58W+Sn8jkfl2+MLDZcNuOFkyOQlQ8ycSGElPbgXANcAfjAEXl6Bfu04
    OB2bePz2AL1MjrgLcPyxIVW+QExYVXNtlXzx+9rRokmHhaUDmLa8iktFV2fFaol2
    KjfKvvYMZThoL+CfZH6UYxrb3PkIDt9TBI2Tu4y+zy8iP4rwVNZwZCY3kmLLRlX3
    TWa/TonauTAUYJCRsc1QXy5ZkDKfOfXztVwBquRuqrdnS5nuJi0r6INmUeaEfYaW
    3AMy2LGsp2G4JBRAhQTYIuaAjXIOOmGS2WrK5+2k0JAmeTleFMyWFW8/x2xXS/LU
    /zyejy24RZrkCehUZ1TcakqhR5aa7EyIJxfMt9DRnWSO8lLE9i1HW85PhM8xgDep
    X92t0vhQ4KSCO/IReKnOKgfFYonIrAOJh2eBxBVT0siLnLB1G3ReW1o8Xo4IpcF9
    FiYXXcysuFnZ2jRe+dGRGCub4EG/QOPLsREWnq8dH8n31mpaHy2ikkHvD/XCNc7p
    85aEaIfPhD1nzlO49LRqXcEQvjzOMYSyuuhQ7mIe2VxLIurtBSi4i5gEROaUCMda
    FPKmFPJ0GUBL8SnYUbmz
    =1vfT
    -----END PGP SIGNATURE-----
    
  • PeterL says:

    Just a couple questions:

    Why doesn't FZ_ShiftLeft have a space in it, like Shift_Left?

    Do you need to have the temp variable Ni? Couldn't you just as well use N(i) for that?

    • Stanislav says:

      Dear PeterL,

      > Why doesn’t FZ_ShiftLeft have a space in it, like Shift_Left?

      No particular reason.

      > Do you need to have the temp variable Ni? Couldn’t you just as well use N(i) for that?

      Array references cost CPU cycles (not only per se, but potentially blow the cache.) IMHO they also add visual "mass".

      Yours,
      -S

      • PeterL says:

        Do you really save much by trading two array references for one array reference and two word references? I suppose one could empirically check the difference by building the two variants and measuring any difference in speed?

        • Stanislav says:

          Dear PeterL,

          Feel free to test.

          However, as noted earlier, cycle-shaving is not the only reason for the given form: clearly marking identical expressions with a constant makes for a more readable program.

          Yours,
          -S

  • shinohai says:

    ffa_ch3_shifts.kv.vpatch

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

    iQIzBAABCgAdFiEEJg+le85nelwEv2C6SnWIPMGx00wFAl3TFJ8ACgkQSnWIPMGx
    00zLcg/+PINGALVe0XjvBTanT7GqUbEpXEXxdyyfU4L1buLPpyhBZ2Q5PeXgJgMx
    pdgoDlu4XzmSNFmNECqUJRpmp1/7SOt5MZ76c9e1gaBtVG6g+i1Xh22TRN9sbAqM
    LR+BRCnShh/j8PyFlgdbxAOl/hGq3waO84TQDr+6FA7dGpCl2CUu1qtiuCBmUdl2
    KLx27HCNpnTu7lOAq4IgHguMWUa1TFB/kmJbVkMCY643NoIqKxSCA14s62vcd5s2
    G87JRH3Y8rpfBSVFUWqk+GNijMCHEtOdb+f4KCtrMS2S1U5ryczOrNYpqJeJM1Xm
    Jj4ER2l7OhNMo0EySdumTtWE2fFFHTujbMX/xuFZH83nfdqSr1ey6xUCEXiIisuX
    /HMU7JligZwrrket6y/phPLchNL/B0bPhqCB6DXbCTsXvpj0EQt9SspgK7tSOofk
    CvrL6BV4Tkt3Gd2a4y1Kn6ibASuDuFiIiRGX3bkSJKwgmVXznxpnkpOrqn3481pA
    T3jd6xAF6CZAqi9psC5VIimzt95jvKg0KIxWLYFsXGll5SnSu87E15ggI1R0fy77
    uoTI/pHjdoAQ7HhhYSDC7Th5JOxU3te1u/EPHhRxIaFGOpXe/mZIWp6vA91h68Ne
    afSnjjuonAh+rGJtNkSkjpupGJ4uea8UWDk2RpqZybeZ8t80JNk=
    =chMP
    -----END PGP SIGNATURE-----

    • Stanislav says:

      Dear shinohai,

      Was this your first-time reading of Ch. 1-3? If so, that was pretty fast.

      Yours,
      -S

      • shinohai says:

        >Was this your first-time reading of Ch. 1-3?

        No I had previously worked up to chapter 4 (with notes, etc.), just never bothered to post my sigs and such. Decided this fall-winter would be a perfect time to revisit. I expect the next chapters to continue at a bit slower pace since I haven't read past Ch. 4 in a thorough manner, and like to work out the calculations by hand and take notes as I go along.

  • jonsykkel says:

    theres a bug in both the O_I functions:
    Carry : Word := OF_in;
    supposed to be something like (in the case of right shift)
    Carry : Word := Shift_Left(OF_in, Bitness - Count);

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:

89 xor 102 = ?

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!