An update on the previous version.
The produced gcc compiler builds static executables and no dynamically linked executables.
For detailed instructions in how to run the script see the readme-2018-06-01.txt.
The code of PGPy1 sucks.
A good indication of the quality of a Python package is the 'requirements.txt' file, reproduced here;
cryptography>=1.1 enum34 pyasn1 six>=1.9.0 singledispatch
The cryptography package will need to be reviewed separately. A quick view at the PYPI package index for cryptography is already good for some lulz2. The enum34 brings the Python 3 enumeration type to Python 2. Only one object is used from the package pyasn1 and the functionality provided in this object could all have been implemented in an hour in PGPy. If you see six as a requirement, you know you are in trouble. The six package is for when an package author wants to program in Python 2 but also wants to make it's3 program work in Python 3 without any conversion. So six indicates that you will be reading code that is not Python 2 and will use the from future import print_function, the from future import division and more. Any author writing packages requiring six can be safely negrated. The singledistpatch package is again something from Python 34. Based on these requirements alone, I conclude that PGPy sucks.
Next, the types.py file in the pgpy directory. The code in this file failed to run on my systems and so triggered this review. The first class definition therein is an Armorable class. Clearly the authors did not know it is forbidden to define any -able class in Python. The Armorable class contains the full implementation of converting objects into armored5 text and vice versa. This is a mistake, as -able stands for Capable of being ..., the being in that fragment will need to be implemented by something else. If something is drinkable it usually does not drink itself, but is has properties that make it drinkable to someone. And which of it's many properties make it drinkable is determined by the drinker not by the drunk. Based on this class alone, I conclude that PGPy sucks.
Two classes in types.py are defined with a meta class (the Armorable and the MetaDispatchable). The whole metaclass mess is defined in PEP-3119. Go and read it if you want to waste your time. The definition of MetaDispatchable provides for an extra complex and custom object-orientation. Remember, we are reviewing a package to handle PGP code. Another strike against PGPy and I will not bore you with more.
A script is floating around to convert TMSR key format (e,n,comment) to a PGP key for digesting in phuctor. This script did not work on the machines I tried it on. Of course, the script is fine, it's PGPY that is broken. I could not get it to install. As I'm programming in python for a living and have all kinds of stupid in me, I decided to try and fix the pgpy code that failed to install. An hour was so spent and some material gathered for a future blog post, but not any working code1.
After that I decided to spent another hour making an alternative that uses only standard python modules. I read RFC 4880 a month ago, this left me with headache back then. The thing is unreadable. So to make this script, I made extensive use of the search function in my browser and only read those lines that helped in writing the script.
The script;
import struct
import time
import sys
import base64
import math
# some format strings for the struct module
# these are used to encode integers and shorts to arrays of bytes
# '>' stands for big-endian as this is what is used in the PGP format
openpgp_publickey_format = ">BIB"
mpi_format = ">H"
packet_length_format = ">I"
crc_format = ">I"
# determine the index of the highest bit set to 1 in a number
def count_bits(B):
R = 0
i = 0
while B > 0:
i += 1
if B & 0x1:
R = i
B >>= 1
return R
# Convert a number to an array of bytes
# The bytes in the array are stored in big-endian order.
# The most significant byte is stored as the first item
# in the array
def number_to_bytes(B):
R = []
bits = 0
while B > 0xff:
bits += 8
R.append(B & 0xff)
B >>= 8
R.append(B)
bits += count_bits(B)
return bits, ''.join(map(chr, reversed(R)))
# An MPI is a byte array that starts with a two byte
# length header. The length is given in bits.
def number_to_mpi(B):
C, A = number_to_bytes(B)
return struct.pack(mpi_format, C) + A
# A PGP public key header consists of a byte "4",
# an integer (4 bytes) to denote the timestamp
# and a byte "1" (RSA).
def public_key_header(T):
return struct.pack(openpgp_publickey_format, 4, T, 1)
# A public key packet is the public key header
# plus 2 MPI numbers, the RSA modulus (N) and
# the RSA exponent (e).
def public_key_packet(t, n, e):
return ''.join((public_key_header(t), number_to_mpi(n), number_to_mpi(e),))
# A comment or userid packet is a string encoded as utf-8
def userid_packet(s):
return s.encode('utf8')
# The PGP format is a stream of "packets".
# Each packet has a header. This header consists of a tag
# and a length field. The tag has flags to determine if it is a
# "new" or "old" packet.
# The only supported encoding in this scriptis "new".
def encode_packet(packet_bytes, tag = 6):
# 0x80, 8th bit always set, 7th bit set --> new packet
h = 0x80 | 0x40
# 0-5 bits -> the tag
h |= tag
# convert the integer to a byte
header = chr(h)
# dude, this is totally how you may save 2 or 3 bytes with minimal complexity
l = len(packet_bytes)
if l < 192:
header += chr(l)
elif l < 8384:
l -= 192
o1 = l >> 0xff
o2 = l & 0xff
header += chr(o1 + 192) + chr(o2)
else:
header += chr(0xff) + struct.pack(packet_length_format, l)
return header + packet_bytes
# When you encode binary data as an ascii text with base64
# this data becomes fragile. So a CRC code is needed to
# fix this.
def crc24(s):
R = 0xB704CE
for char in s:
B = ord(char)
R ^= B << 16
for i in range(8):
R <<= 1;
if R & 0x1000000:
R ^= 0x1864CFB
return R & 0xFFFFFF
# Create a public key for consumption by Phuctor.
# The public key needs to contain 2 packets
# one for the key data (n, e)
# one for the comment
# It must be in the armor / ascii format.
def enarmored_public_key(n, e, comment, t):
R = []
# the header
R.append("-----BEGIN PGP PUBLIC KEY BLOCK-----")
R.append("")
# the packets in bytes
A = encode_packet(public_key_packet(t, n, e), 6)
A += encode_packet(userid_packet(comment), 13)
# the packets in base64 encoding with line length max 76
s=base64.b64encode(A)
i = 0
while i < len(s):
R.append(s[i:i+76])
i += 76
# the CRC
R.append("="+base64.b64encode(struct.pack(crc_format, crc24(A))[1:]))
# the footer
R.append("")
R.append("-----END PGP PUBLIC KEY BLOCK-----")
return 'n'.join(R)
# read a file with comma separated lines
# each line is in the TMSR format: e,n,comment
if __name__ == "__main__":
ser = 1
for x in sys.stdin:
x = x.strip()
# ignore empty lines
if len(x) == 0 or x.startswith('#'):
continue
# the comment may contain comma's so split on the first 2
e,n,comment = x.split(',', 2)
t0 = int(time.time())
with open("{0}.txt".format(ser), "wb") as stream:
stream.write(enarmored_public_key(int(n), int(e), comment, t0))
ser += 1
And the patch itself with signature;
An update on the previous version.
The produced gcc compiler builds static executables and no dynamically linked executables1.
For detailed instructions in how to run the script see the readme-2018-05-28.txt.
Updated!, the 2018-05-28 file contained a broken patch
New version!
An update on the previous version.
The previous version needed git for getting the source of libelf-compat, this was ripped out1.
The previous version cleaned and reused the build directory for different stages, this was changed to use a separate build directory for each stage and no more cleanup. Last, the script now builds with parallel make options, further speeding up the build process2.
An update on the previous version. I thought that version already supported ARM 64-bit processors1, but unfortunately it did not.
So another debug cycle ensued. As it turned out the code that is used to generate aarch64 instructions had a wrong #ifdef line. Once this bug was fixed, the next bug cropped up and with a mean time between a possible fix and the correct fix taking days, the whole exercise took weeks2. After a week or so, the cross-compiler seemed to work. Next, I wanted to compile a native compiler for the target platform with the help of the cross-compiler. Again, time was spent, and fortunately a compiler could be build and after some more work3 it can build the FFA code on aarch64 systems.
Some small things are left to do; the scripts can do with some clean-up and the native compilers are not tarred to a file, finally, I want to try little-endian ppc.
Update:The native compilers do not contain the gprbuild tool, this is still on the todo list.
The Ada language and the C language have a very different concept of strings and characters. I'll try to follow Ossasepia and use the term octet for an 8 bit integer and use char for C and Character for Ada. In Ada the Character is defined as an enumerated type ranging from the Ada.Characters.Latin_1.NUL (Character'Val (0)) character to the Ada.Characters.Latin_1.LC_Y_Diaeresis (Character'Val (255)) character. This range is exactly the same as the range of all valid octets and so characters can be stored as octets. As characters are supposed to represent another domain as natural numbers these need to be converted back and forth through the Character'Val and Character'Ord functions. In C all is a lot more muddier and a char can either be seen as an 8 bit integer or as a symbol for a language, it all depends on the context. So far for context, now to address the cause, how to convert arrays of characters between C and Ada1. I consider the Char_Ptr support from the ada standard library out of bounds2, this investigation is based on the 'char_array' type from the Ada package `Interfaces.C. First, the code;
The code defines 5 different methods to interact with strings between C and Ada;
First, to define the procedures (please also read the calling conventions section of the GNAT documentation):
with Interfaces.C; use Interfaces.C;
package C_Array is
-- The basic method, call C using a pointer and a count
procedure C_Fill_1(CH : in out char_array; Count : Integer);
pragma Import(C, C_Fill_1, "c_fill_1");
-- Same method as 'C_Fill_1', but the C function will call Ada.
procedure C_Fill_2(CH : in out char_array; Count : Integer);
pragma Import(C, C_Fill_2, "c_fill_2");
-- Same method as 'C_Fill_1', but the C function will call Ada using Ada calling conventions
procedure C_Fill_3(CH : in out char_array; Count : Integer);
pragma Import(C, C_Fill_3, "c_fill_3");
-- Call to C using Ada calling conventions
procedure C_Fill_4(CH : in out char_array);
pragma Import(Ada, C_Fill_4, "c_fill_4");
-- Same method as 'C_Fill_1', the C function will call Ada using an unconstrained array and a count.
procedure C_Fill_5(CH : in out char_array; Count : Integer);
pragma Import(C, C_Fill_5, "c_fill_5");
-- For method 2, the C function will make a call to a function with a constrained array parameter
subtype constrained_char_array is char_array(0 .. 100);
procedure ADA_Fill_2(CH : in out constrained_char_array);
pragma Export(C, ADA_Fill_2, "ada_fill_2");
-- For method 3, the C function will make a call to Ada usinging Ada calling conventions.
procedure ADA_Fill_3(CH : in out char_array);
pragma Export(Ada, ADA_Fill_3, "ada_fill_3");
-- For method 5, the C function will make a call to a function with a unconstrained array parameter
subtype constrained_char_array is char_array(0 .. 100);
procedure ADA_Fill_5(CH : in out char_array; Count: Integer);
pragma Export(C, ADA_Fill_5, "ada_fill_5");
end C_Array;
Next, the more interesting bit, the C functions;
#include <stdint.h>
#include <stdio.h>
typedef struct B {
size_t LB0;
size_t UB0;
} B_t;
typedef struct U {
char * P_ARRAY;
B_t * P_BOUNDS;
} U_t;
void ada_fill_2(char * buffer);
void ada_fill_3(U_t array, int count);
void ada_fill_5(char * buffer, int count);
void c_fill_1(char * buffer, int count) {
int i;
printf("c_fill_1; buffer = %p, count = %dn", buffer, count);
for(i = 0; i < count; i++) {
buffer[i] = '1';
}
}
void c_fill_2(char * buffer, int count) {
printf("c_fill_2; buffer = %p, count = %dn", buffer, count);
ada_fill_2(buffer);
}
void c_fill_3(char * buffer, int count) {
B_t b;
U_t a;
b.LB0 = 0;
b.UB0 = count;
a.P_ARRAY = buffer;
a.P_BOUNDS = &b;
printf("c_fill_3; buffer = %p, count = %dn", buffer, count);
ada_fill_3(a, count);
}
void c_fill_4(U_t array) {
int i = 0;
char * buffer = array.P_ARRAY;
printf("c_fill_4; buffer = %p, count = %dn", array.P_ARRAY, array.P_BOUNDS->UB0 - array.P_BOUNDS->LB0);
for(i = array.P_BOUNDS->LB0; i <= array.P_BOUNDS->UB0; i++) {
buffer[i] = '4';
}
}
void c_fill_5(char * buffer, int count) {
printf("c_fill_5; buffer = %p, count = %dn", buffer, count);
ada_fill_5(buffer, count);
}
The first 2 functions are simple. Because the array is constrained in Ada there is no need for the count parameter, however the actual length of the array in C must always be the same as the one in Ada. Next the two methods that took the most time to figure out. I could not find any useful description of the so called Ada Calling Convention. No such convention seems to be specified, and every ada implementation is free to implement this as they see fit. The C code will be tight to GNAT when using this method and maybe even specific versions of GNAT. The Ada calling convention for arrays is implemented in the interface between the GNAT frontend and the GCC backend3. In the interface, the GNAT code tree is converted into a GCC code tree, and most of these functions are recursive and try to get information from different parts of both trees. In short, reading this code is not that easy, but from the code I could determine that unconstrained arrays are send as a structure with two fields, one field is a pointer to the start of the array, and the other is a pointer to a structure having again two fields. This last structure has a field for the lower bound and one for the upper bound of the array. The exact layout of the structure was a bit harder to determine so an extra flag for the compiler was needed -fdump-tree-original4. From that dump, I could determine the structure5. The C function is not more secure with this structure, but the Ada implementation will be. Finally, we finish with the more usual way of calling an Ada function with an unconstrained character_array and a count variable.
For reference, the Ada implementation. Note that for the fifth case we cannot use the upper bound of the array. This upper bound is undefined (and in practice will be the maximum value of the given range type).
with Ada.Text_IO; use Ada.Text_IO;
with Ada.Integer_Text_IO; use Ada.Integer_Text_IO;
with Ada.Long_Integer_Text_IO; use Ada.Long_Integer_Text_IO;
package body C_Array is
-- We have a statically defined length so the range will be fine.
-- The call in C code to this procedure must use a buffer with at least the constrained range.
procedure ADA_Fill_2(CH : in out constrained_char_array) is
begin
Put("ada_fill_2;");
Put(" lb=" & size_t'Image(CH'First));
Put(" ub=" & size_t'Image(CH'Last));
New_line;
for I in CH'Range loop
CH(I) := To_C('2');
end loop;
end Ada_Fill_2;
-- The call in the C code needs to send an Ada array.
procedure ADA_Fill_3(CH : in out char_array) is
begin
Put("ada_fill_3;");
Put(" lb=" & size_t'Image(CH'First));
Put(" ub=" & size_t'Image(CH'Last));
New_line;
for I in CH'Range loop
CH(I) := To_C('3');
end loop;
end Ada_Fill_3;
-- For calls from C without a constained type or ada array, an extra count parameter is needed.
procedure ADA_Fill_5(CH : in out char_array; Count: Integer) is
begin
Put("ada_fill_5; count="); Put(Count);
Put(" lb=" & size_t'Image(CH'First));
Put(" ub=" & size_t'Image(CH'Last));
New_line;
-- the Range cannot be used, the 'Last index is wrong.
for I in ch'First .. size_t(Count) loop
CH(I) := To_C('5');
end loop;
end Ada_Fill_5;
end C_Array;
The code includes a simple main program that calls all five functions;
with C_Array; use C_Array;
with Ada.Text_IO; use Ada.Text_IO;
with Ada.Integer_Text_IO; use Ada.Integer_Text_IO;
with Interfaces.C; use Interfaces.C;
procedure Array_Main is
work_array : char_array(0 .. 100);
output_string : String(1 .. 101) := (others => ' ');
C : Integer := 0;
begin
Put("start");
New_Line;
C_fill_1(work_array,100);
To_Ada(work_array, output_string, C, False);
Put("c_fill_1 output ="); Put(output_string);
New_Line;
C_fill_2(work_array,100);
To_Ada(work_array, output_string, C, False);
Put("c_fill_2 output ="); Put(output_string);
New_Line;
C_fill_3(work_array,100);
To_Ada(work_array, output_string, C, False);
Put("c_fill_4 output ="); Put(output_string);
New_Line;
C_fill_4(work_array);
To_Ada(work_array, output_string, C, False);
Put("c_fill_4 output ="); Put(output_string);
New_Line;
C_fill_5(work_array,100);
To_Ada(work_array, output_string, C, False);
Put("c_fill_5 output ="); Put(output_string);
New_Line;
end;
The output will be;
start c_fill_1; buffer = 0x7ffdf87fd910, count = 100 c_fill_1 output =1111111111111111111111111111... c_fill_2; buffer = 0x7ffdf87fd910, count = 100 ada_fill_2; lb= 0 ub= 100 c_fill_2 output =2222222222222222222222222222... c_fill_3; buffer = 0x7ffdf87fd910, count = 100 ada_fill_3; lb= 0 ub= 100 c_fill_4 output =3333333333333333333333333333... c_fill_4; buffer = 0x7ffdf87fd910, count = 100 c_fill_4 output =4444444444444444444444444444... c_fill_5; buffer = 0x7ffdf87fd910, count = 100 ada_fill_5; count= 100 lb= 0 ub= 18446744073709551615 c_fill_5 output =5555555555555555555555555555...
A random remark; it is not a good idea to call To_Ada on the unconstrained array from method 56. First, To_Ada is not more efficient than a character by character conversion, in fact it is implemented as such. Second, To_Ada will use the Last parameter of the `character_array and that parameter is set to the maximum value of size_t (Ada will check on this bound but a segmentation fault will happen first). Either copy the character_array to a constrained character array first, or write a custom conversion function.
Another random remark; the Ada standard library can be studied with the Ada 2012 LRM and understood better with the GNAT source code. It helps to have a cross-referenced, browser readable version of the GNAT source code at hand (there is one in the GNAT Book, but that one is incomplete). To make such a version do:
0) Make a directory and go to it
mkdir ada-html
cd ada-html
1) Find the gnat runtime library
(i.e. the directory containing adainclude and adalib)
It should be in the gnat install directory,
as the lib/gcc/<machine>/<gcc version>/ directory
For AdaCore 2016, (linux 64bit) this directory can set with:
RT_DIR = $(dirname `which gnatmake`)/../lib/gcc/x86_64-pc-linux-gnu/4.9.4
2) Copy the source files from adainclude:
cp $RT_DIR/adainclude/*.ad* .
3) Copy the ali files from adalib (needed for cross references):
cp $RT_DIR/adalib/*.ali .
4) Make the html files with the `gnathtml.pl` script:
gnathtml.pl -f -D *.ad*
5) Go to the 'html' directory and look (open index.htm in a browser):
cd html
ls
Executables written in ADA and compiled with GNAT, include a portion of the GNAT runtime library, the C library and some start-up/shut-down code. The total sum of extra code bytes added to any statically compiled executable can easily become 2 megabytes. Most of this code will never be called. Good luck to you, if you want to read the decoded assembly lines of such an executable. As the same luck would have it, the GNAT system includes the possibility to compile code with a custom runtime library and GCC itself can use different C libraries.
The gnat compilers can use alternate GNAT runtimes. The most common use of such alternate runtimes is for embedded systems with little or no OS. A guide to building such an embedded runtime system can be found here12. This guide provided the basis for the runtime described here.
A minimal runtime can be found in the following vpatch;
The vpatch needs to be pressed, and the code can be build with gprbuild.
All optional code has been removed from the gpr project file3.
library project Gnat_Runtime is
for Languages use ("Ada");
for Source_Dirs use ("adainclude");
for Object_Dir use "obj";
for Library_Kind use "static";
for Library_Name use "gnat";
for Library_Dir use "adalib";
package Builder is
for Default_Switches ("Ada") use (
"-x",
"-gnatg", "-gnatyN",
"-gnatec=" & Gnat_Runtime'Project_Dir & "restrict.adc");
end Builder;
package Compiler is
for Default_Switches ("Ada") use (
"-O2",
"-ffunction-sections",
"-fdata-sections");
end Compiler;
end Gnat_Runtime;
If you inspect the pressed directory, you can see that a GNAT runtime is a directory with two subdirectories adainclude and adalib. The adainclude directory needs to contain the ada library files, the adalib needs to contain the libgnat.a and the .ali files. The obj directory is for intermediary build products and can be safely deleted after a build. Notice that the two sub-directories adainclude and adalib are all that is needed for a GNAT runtime.
. ├── adainclude │ ├── ada.ads -- The Ada package (Pure, empty, just the root) │ ├── a-inteio.adb -- Ada.Integer_Text_IO (for Put function of an Integer) │ ├── a-inteio.ads -- Ada.Integer_Text_IO │ ├── a-textio.adb -- Ada.Text_IO (a few functions (Put, New_Line) for standard output) │ ├── a-textio.ads -- Ada.Text_IO │ ├── interfac.ads -- For interaction with C │ ├── last_chance_handler.adb -- No exception handling, so a last_chance_handler is needed │ ├── last_chance_handler.ads -- │ ├── s-elaall.adb -- Elaboration code, see file for explanation │ ├── s-elaall.ads -- │ ├── s-parame.adb -- Parameters for the C interface, needed by the last_chance_handler │ ├── s-parame.ads -- │ └── system.ads -- The configuration of the runtime ├── adalib -- Output directory, will contain libgnat.a │ └── README -- Placeholder ├── gnat_runtime.gpr -- The gprbuild project file ├── obj -- Output directory for intermediate results │ └── README -- Placeholder ├── README -- Very small explanation └── restrict.adc -- Restrictions
The "system.ads" file is paramount in configuring any GNAT runtime library. This file is well documented in AdaCore's configurable runtime documentation. That document describes the AdaCore Pro code, it is also valid for the GPL version4. The system.ads file is also the file to put restrictions in, these restrictions will be valid for the runtime code and all code compiled with the runtime.
The "last_chance_handler.ads|adb" files are necessary as the default exception handling mechanism is not included in this runtime (and the "s-parame.ads|adb" are needed for the last_chance_handler). The handler function needs to eat C strings, so some very ugly Ada code is needed here5.
I've written two very basic examples to test this runtime6, one to test the size of the generated executable and one to test if the error handling still works as expected. These examples can be found in the following patch:
The examples can be build with the project file in the examples subdirectory. The examples work with the default runtime and the zfp runtime. To build with the zfp runtime do gprbuild --RTS=../. The example can be build with a glibc based gnat (GNAT AdaCore 2016) and a musl based gnat (using the MUSL build instructions), a small table;
| C Library | GNAT Runtime | Executable Size (Kbytes) | Stripped Size (Kbytes) | Comments |
|---|---|---|---|---|
| GNU | default | 1226 | 851 | |
| GNU | zfp | 962 | 738 |
|
| MUSL | default | 669 | 122 |
|
| MUSL | zfp | 60 | 54 |
|
As it turns out, if only a limited set of the Ada library is employed, the default GNAT runtime does not add that much extra code to an executable.
Next, the '"constraint/constraint.adb"' file. The code in this file is designed to trigger a constraint error. For every constraint error the code should end up in the last_change_handler function. This is easily tested by running the constraint binary10.
I've been investing a lot of time1 into The Republic and it's products to date. And now it seems to be dead in the water.
Reading the logs, reading trilema.com, researching the FFA code, all these activities have helped to eradicate some of the cockroaches in my mind. A big step, setting up this blog, has been a victory. Sloppy thinking simply presents itself once layed down in written sentences, if not immediately then after a re-read or after comments by Stanislav. Also, not all thoughts can be put to paper, how is that2? So all this time has not been wasted.
But with the most probable demise of the BingoBoingo ISP, the whole republic is on very shaky footing.
Last Friday (or Saturday morning), Mircea Popescu correctly pulled the plug. Of the various reactions to be expected, we got none. Well, one!, Stanislav wanted to maybe take the business, but luckily he retreated3 45.
In the mean time Mircea Popescu has fired off a number of put downs in BingoBoingos' direction, in what feels to me to be an attempt to get same BingoBoingo of his ass. Unfortunately only self lamenting comments have been coming back6. Let's assume you want to stay in Uruguay, probably under another lords directions. You would want to show off that you can get busy7. Start working on a few issues;
- Make a list of what has been done, was is to be done and was is being done8.
- The rack contains one server so test and publish speeds for upload and download, sustained and peak etc.
- Go online and figure out the import tariffs, yes on somethings you may need to play ball with the local government9.
- Make a list of the local costs / delivery time for some of the parts and publish this10.
- Read up on tax law in Uruguay, especially VAT etc, make some post about to show your understanding.
- And think about this, once back, was the 1 BTC a loan? how would you pay this off? Or will this be a write-off on Mircea Popescus' side?. Simply the cost of doing business, or something.
As for the lords, "and now?", currently there is a rack11, there is a willing boy on the ground12, there is a bank-account, there is an office. A company is almost to be had for a given amount of coin13. I had every faith in being a client of an ISP business that is run / financed in some form by Mircea Popescu14, as he is committed to go for the long run. So, I hope the Lords will get of their asses.
To be specific: "Finite Field Arithmetic." Chapter 2: Logical and Bitwise Operations.
The first section contains a short (re-)introduction and a list of additional files to download. With these files, the code can be updated and build again. This section is easy to follow and finish.
Next a short exposition on the early feedback on chapter 1, with the conclusion that W_Swap is now removed.
A definition of four predicate functions on Word types is given first. These are all very minimal and well designed. I could construct an alternative version of W_NZeroP, but it was so much more ugly than the published version. My stance on removing all unused functions is quickly becoming unattainable, clearly a general purpose library is being build and not a RSA specific one1. A retreat is in order, from now on everything dubious will be removed. Where dubious is an arbitrarily defined quality.
Next up, are 5 basic functions on the FZ type.
As FZ_Clear "illustrates the use of Ada's array assignment", we'll need to investigate it's consequences. We do not have to worry that this statement can be dependent on the array contents. We do have to worry about optimizations the compiler might perform (the famous memset removal in gcc). Let's try to create a small example with the FZ_Clear procedure2. First, a patch on the chapter 2 code:
The inline_always pragma has been moved from the 'fz_basics.adb' to 'fz_basics.ads' in this patch.
The somewhat interesting code is in 'clear_mod.adb'.
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 FZ_Basic; use FZ_Basic;
with FFA_IO; use FFA_IO;
package body Clear_Mod is
procedure Clear_Procedure is
Z : FZ (0 .. 128);
begin
FZ_Set_Head (Z, 20);
FZ_Clear (Z);
Put_Line ("--- cleared: ---");
Dump (Z);
New_Line;
FZ_Set_Head (Z, 22);
Z (2) := 16#DEAD#;
Z (3) := 16#FAAF#;
Z (4) := 16#1001#;
Z (100) := 16#0110#;
Z (128) := 16#F1F1#;
Dump (Z);
New_Line;
FZ_Clear (Z);
end Clear_Procedure;
procedure Print_Procedure is
Z : FZ (0 .. 256);
Y : FZ (0 .. 132);
begin
--Dump(Z);
New_Line;
Dump (Y);
Put_Line ("--- <<<< ---");
New_Line;
end Print_Procedure;
end Clear_Mod;
In clear_procedure we change a FZ, it is cleared, it's state is dumped on the terminal, some interesting words are put in the FZ and finally the FZ is cleared again. This last action is just to be sure that no information will be left on the stack after this procedure finishes. Without inlining, this function works perfectly3. With inlining, the code is different, the compiler will determine that the final clear is useless and remove it.
c/ffa/fzclear/bin/clear: file format elf64-x86-64 Disassembly of section .text: 0000000000401530 <clear_mod__clear_procedure>: 401530: 55 push %rbp 401531: 48 89 e5 mov %rsp,%rbp 401534: 53 push %rbx 401535: 48 81 ec 38 14 00 00 sub $0x1438,%rsp 40153c: 48 83 0c 24 00 orq $0x0,(%rsp) 401541: 48 81 c4 20 10 00 00 add $0x1020,%rsp 401548: ba 14 00 00 00 mov $0x14,%edx 40154d: be 30 c8 49 00 mov $0x49c830,%esi 401552: 48 8d 9d e0 fb ff ff lea -0x420(%rbp),%rbx 401559: 48 89 df mov %rbx,%rdi 40155c: e8 ef 00 00 00 callq 401650 <fz_basic__fz_set_head> 401561: 31 c0 xor %eax,%eax 401563: 48 89 df mov %rbx,%rdi 401566: b9 81 00 00 00 mov $0x81,%ecx 40156b: f3 48 ab rep stos %rax,%es:(%rdi) 40156e: be 38 c8 49 00 mov $0x49c838,%esi 401573: bf 20 c8 49 00 mov $0x49c820,%edi 401578: e8 f3 2e 00 00 callq 404470 <ada__text_io__put_line__2> 40157d: 48 89 df mov %rbx,%rdi 401580: be 30 c8 49 00 mov $0x49c830,%esi 401585: e8 d6 fd ff ff callq 401360 <ffa_io__dump__2> 40158a: bf 01 00 00 00 mov $0x1,%edi 40158f: e8 bc 2a 00 00 callq 404050 <ada__text_io__new_line__2> 401594: ba 16 00 00 00 mov $0x16,%edx 401599: 48 89 df mov %rbx,%rdi 40159c: be 30 c8 49 00 mov $0x49c830,%esi 4015a1: e8 aa 00 00 00 callq 401650 <fz_basic__fz_set_head> 4015a6: 48 89 df mov %rbx,%rdi 4015a9: be 30 c8 49 00 mov $0x49c830,%esi 4015ae: 48 c7 85 f0 fb ff ff movq $0xdead,-0x410(%rbp) 4015b5: ad de 00 00 4015b9: 48 c7 85 f8 fb ff ff movq $0xfaaf,-0x408(%rbp) 4015c0: af fa 00 00 4015c4: 48 c7 85 00 fc ff ff movq $0x1001,-0x400(%rbp) 4015cb: 01 10 00 00 4015cf: 48 c7 85 00 ff ff ff movq $0x110,-0x100(%rbp) 4015d6: 10 01 00 00 4015da: 48 c7 45 e0 f1 f1 00 movq $0xf1f1,-0x20(%rbp) 4015e1: 00 4015e2: e8 79 fd ff ff callq 401360 <ffa_io__dump__2> 4015e7: bf 01 00 00 00 mov $0x1,%edi 4015ec: e8 5f 2a 00 00 callq 404050 <ada__text_io__new_line__2> 4015f1: 48 81 c4 18 04 00 00 add $0x418,%rsp 4015f8: 5b pop %rbx 4015f9: 5d pop %rbp 4015fa: c3 retq 4015fb: 0f 1f 44 00 00 nopl 0x0(%rax,%rax,1)
Another fortunate side-effect of reading the FFA chapters, is that I now have a good opportunity to learn x86 assembly language4. The final FZ_Clear implementation is removed from the procedure, so it follows that the values should be still on the stack and it may be possible to read these. And that is why the clear_mod.ads module also contains Print_Procedure, with some padding FZ and a FZ to capture the stack. On my local gnat installation (the gnat 2016 binary from adacore), the dump of Y shows the contents of the local variable Z from Print_Procedure. This is probably not what you would expect, the best option to me seems to make sure that FZ_Clear is never inlined. Unfortunately, I've not found a pragma Never_Inline.
With FZ_Get_Head and FZ_Set_Head we get some confusion of terminology, suddenly we are talking about a head or first or youngest word of an FZ. And it becomes clearer that the words in an FZ have an order and we are missing an exact definition of FZ outside of the code itself. Here is one attempt to do so, an FZ is a number5 between 0 and 2 to a given power. This power is determined by the number of words in a FZ multiplied by the number of bits in a word (the bitness). An FZ can be seen as the summation over the array of words that make up the FZ where each word is multiplied by 2 to the power of the bitness times the position of that word in the array. For the math to be a correct, we define the first word in the array to have position 06. As for a visual representation, when the words (and the bytes inside the words) are written from left to right, the tail or last or oldest word is written first and the head or first or youngest is written last. Although the FZ_Get_Head and FZ_Set_Head procedures triggered a nice train of thought, I would remove these.
The best is left for last in this module, FZ_Mux is indeed crucial. It's implementation in terms of W_Mux is trivial, so if you understand W_Mux all is well. I found one alternative for this function, but it is wasteful compared to this one. Image if you define a 2d array with as many rows as there are words in X and each row having two columns. Put each word in X in the first column of the corresponding row in the 2d array. Put each word in Y in the second column. Now the result can be formed by iterating over the array and accessing the element from the right column. Unfortunately, this hypothetical code based on a 2d array, accesses memory ever so slightly differently based on the Sel bit, and thus might leak information.
Next up, two unary predicate operators on the FZ type are introduced. The FP_ZeroP procedure can be used to determine if every word in the FZ has the value 0. The FP_OddP can be used to check if the last bit of the head word is set, and here FZ_Get_Head is not used in the implementation.
Three binary predicate operators are defined in fz_cmd.adb. The FZ_EqP procedure follows the pattern first seen in FP_ZeroP. The FZ_LessThanP and FZ_GreaterThanP are implemented in terms of the subtraction operator. The result is determined by the borrow. Now, you just have to determine if the order of the arguments for the FZ_Sub call is correct.
With a set of 7 bitwise operators, the introduction of the ffa library in chapter 2 is finished. In fz_bitop.ads, binary operators are defined for two FZ operands, and separately for one FZ with one Word operand. These last versions work on the head word of an FZ, and we'll just have to see if there is any use for these procedures. Another remark, although these procedures could have been implemented in terms of the FZ_Get_Head / FZ_Set_Head procedures, again they have not. A final remark on the same procedures is that these modify the first input FZ operand where the full FZ procedures fill a third operand7.
We skip the demo and finish for the day, on to the next chapter!.