“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.
- Chapter 1: Genesis.
- Chapter 2: Logical and Bitwise Operations.
- Chapter 3: Shifts.
You will need:
- All of the materials from Chapters 1 and 2.
ffa_ch3_shifts.vpatch(see here)ffa_ch3_shifts.vpatch.asciilifeform.sig- ffa_ch3_shifts.kv.vpatch
- ffa_ch3_shifts.kv.vpatch.asciilifeform.sig
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 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-----
Dear PeterL,
Thanks, this sig will live here now.
Yours,
-S
Dear BenVulpes,
Perma-hosted here.
Yours,
-S
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?
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
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?
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
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-----
Dear shinohai,
Was this your first-time reading of Ch. 1-3? If so, that was pretty fast.
Yours,
-S
>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.
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);
Dear jonsykkel,
Why do you think this is a bug?
Remember, you are looking at the initial (feed-in) carry in each case.
And in the left-shift case, it is deliberately expected in the high bit of the input word. I vaguely recall that this bothered previous readers also, see logs.
Edit: See also this mailbag response about these.
Yours,
-S
(if someones reading this)
http://logs.nosuchlabs.com/log/asciilifeform/2021-09-02#1056162