Ave1

To be specific:
"Finite Field Arithmetic." Chapter 1: Genesis.

Chapter 1 starts with a background on the FFA code and a list of the files you need to start out with. It contains a link to FSF GNAT, but a gnat like this will not work as either the ADA part is broken (gcc < 5) or the gcc itself is tampered with (gcc > 5). You will need a GNAT from adacore¹.

Next comes the unpacking and building description, following this part is straightforward.

For building the code, the gprbuild tool is used. This is a typical alternative build system, this one has superior support for ADA. I do not recommend it for anything else. If you do not trust this tool, it is not hard to write a makefile or a simple bash script based on the few command line parameters given in this script. Of the flags used, I still have one -fdump-scos² that seems unnecessary, apparently it creates coverage information.

After the description of the build we get this line;

Do not run the demo yet. (you read programs before running, don’t you?)

No, I do not!. I have not read gcc or this previously unknown 'gprbuild'. And those where unsigned!

The code starts with a file that did not readily fit in my head; restrict.adc. The only way to get to grips with this file was reading the gnat documentation and the ada reference manual. I made a list of all restrictions according to the GNAT documentation and then checked which where used. To summarise; everything that touches any tasking (ada term for multi-threading) is off limits, everything that does dynamic allocation is off limits, everything that depends on a clock is off limits (delay and Calendar), plus some more to make the code as static as possible. A lot of these pragmas are specific for GNAT. One, I could not find documentation for: "No_Fixed_IO". This is the list of restrictions available in GNAT but not used by FFA³.

No_Anonymous_Allocators         Max_Storage_At_Blocking
Max_Entry_Queue_Length          No_Access_Subprograms
No_Dependence                   No_Direct_Boolean_Operators
No_Exception_Handlers           No_Exceptions
No_Fixed_Point                  No_IO
No_Local_Allocators             No_Long_Long_Integers
No_Recursion                    No_Reentrancy
No_Specification_of_Aspect      No_Use_Of_Entity
No_Obsolescent_Features         SPARK_05
No_Implementation_Pragmas

The implementation is split up over different ADA modules, you can read the code on the site but make sure to study the copy created in the V-press.

The first module is defined in 'iron.ads', it is specified to be a Pure module, meaning the package will not have an internal state⁴. In 'iron.ads', we get to define the size of a word expressed as a number of bits per word, this is called MachineBitness. And a ByteBits, which is needed for communicating the ffa words as this will be on a per byte basis. Unfortunately, it also defines a MachineBitnessLog2, to be explained in another chapter⁵.

The next module words.ads.This is a fun paragraph, try to parse it

.. of FFA, the machine Word. A Word, from this point on, is simply a single machine word on your particular machine.

Or a little bit less self-referential; Word is the smallest unit used for the arithmetic in FFA, values of type Word can range from 0 (inclusive) up to 2 to power of the Bitness (exclusive). Remarkably, 'WBit_Index' is also defined here and maybe the bit is the smallest unit in FFA⁶

I could not determine the reason of this line; for Word'Size use Bitness;. The standard, does not help⁷.

The 'w_shifts.ads' is a module to include the shifts, ask yourself, why not use the pragma Provide_Shift_Operators?

The 'word_ops.ads' file is an irritating Ada necessity, all important information is in 'word_ops.adb'. This last file must be inspected in depth. The carry and borrow functions are brilliant inventions so pay close attention, some extra comments and hints are provided (although the "To derive the..." lines are not very useful, you should be able to get this information from reading the code.). Working these two functions out with a 2-bit word on a paper will help. Also, can you think of another constant time implementation for W_Carry or W_Borrow?

The W_Mux function will be used for all selections and it needs a lot of attention too. Ask yourself; "If WBool is defined as subtype WBool is Word range 0 .. 1;, what is the result of (Sel-1) if Sel is 0?", plus "In how many ways can Mux be defined?"

W_Mux and W_Swap are both unused in this chapter.

The module 'fz_type.ads'; "Gaze upon the combination of abstract mathematical concepts and low level bit fiddling, all in one small library!". Ask yourself; "Do we need Word_Index or Indices?⁸".

In 'fz_arith.ads', the Precondition pragma is used twice. An array Words with unspecified length is denoted by FZ, addition and subtraction are defined for values of FZ of equal length, hence preconditions are needed to check the lengths for all instantiations of these functions.

The code in 'fz_arith.adb', is not very complex but does close need attention⁹. Look at the summation, the sum is (A+B) + Carry, but the next carry is determined by just A, B and the Sum. Are we lucky this is correct?. The whole comment starting with The alert reader might ask why the iteration schemes differ... could have been avoided by making the FZ_Add iteration scheme follow the FZ_Sub scheme. This would increase the usefulness of FZ_Add.

I will skip commenting on the input/output and demo

The comments section is interesting, especially seeing how the only non-used function (W_Swap) gets all the attention

1. specifically 2015 or 2016, not earlier and also not later. [↩]
2. see GNAT User's Guide [↩]
3. Why not use No_Fixed_Point or No_Reentrancy? [↩]
4. Ada has a complex module system all kinds of silly rules. [↩]
5. I recommend to remove this, when you implement this promised chapter it will then quickly fail and you can see if it is explained. [↩]
6. This is another unexplained constant, probably "to be used later". So a good algorithm for understanding the FFA code would be to remove every statement / definition that is not used in the same defining chapter, to be added if and when needed. [↩]
7. First let's read the "Static Semantics", it mentions 2 situation where this matters, one is about packed records, I would set the size for a Word in packed records on a case by case basis. The other situation is for "untyped conversions" and these should never happen in FFA code. For fun, let's read "Implementation Advice", this is typical Ada language reference manual language. [↩]
8. This is a serious question, as each new type/subtype definition introduces an extra concept to be dealt with an understood. [↩]
9. For example; from the fact that this code compiles, we can conclude that Ada is case insensitive. [↩]

Tags: Review

This entry was posted on Friday, January 26th, 2018 at 14:26 and is filed under Ada, Review. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.