Ossasepia

November 24, 2018

Proposed Change to W_Borrow (FFA)

Filed under: Coding — Diana Coman @ 8:32 p.m.

After more than half a year since last time I really looked at it, FFA (Finite Field Arithmetic) finally made its way back up on my list of tasks. Given the rather large break I took on this and the regrind of the original vpatches1, I've carved time out to re-start from the very beginning, as if I had never seen it before. So far, I went in detail through Chapter 1 and Chapter 2 and I am satisfied that I know them to the extent that I could re-write them (I actually did, even though by bits and pieces as I went). So I've updated the files on my Reference Code Shelf with the new .vpatches (using Keccak checksums) and my signatures for them. I'll link them here as well, for easy reference:

The break I took from FFA turns out to have been for the better in at least one way - it is actually easier for me to read the code now, mainly because of all the stuff I've been doing during this "break", of course2. Anyway, with Ada itself a bit more in the background rather than foreground for me, I had more time to actually explore those sort of things that popped out to me this time like the last time under the heading "I've checked it and it's correct so I can sign it but it still seems to be perhaps a bit less clear than it could be." Specifically, I'm talking of the expression introduced in Chapter 1 in the W_Borrow function for obtaining the borrow bit based on the two operands and the borrow bit from a previous operation (see word_ops.adb):

   -- Find the Borrow, from a subtraction where it is known that A - B == D:
   function W_Borrow(A : in Word; B : in Word; D : in Word)
                    return WBool is
   begin
      return WBool(Shift_Right( ( (not A) and B) or ( ( (not A) or B) and D),
                               Bitness - 1) );
   end W_Borrow;
   pragma Inline_Always(W_Borrow);

For comparison, have a look at the W_Carry function in the same word_ops.adb:

   -- Find the Carry, from an addition where it is known that A + B == S:
   function W_Carry(A : in Word; B : in Word; S : in Word)
                   return WBool is
   begin
      return WBool(Shift_Right( (A and B) or ( (A or B) and (not S) ),
                               Bitness - 1) );
   end W_Carry;

I don't know about you, but I can actually follow the boolean expression in W_Carry while at the same time I find that the W_Borrow thing pokes me in the eye repeatedly and I have a hell of a time to picture exactly wtf it says. Making the truth table for it and following the thing revealed that the result is indeed the intended one so I'm satisfied that the expression is correct. However, I still think that there is actually a simpler way to write the same thing, in a manner that even looks similar to the one in W_Carry, namely:

   -- Find the Borrow, from a subtraction where it is known that A - B == D:
   function W_Borrow(A : in Word; B : in Word; D : in Word)
                    return WBool is
   begin
      return WBool(Shift_Right( (B and D) or ( (B or D) and (not A) ),
                               Bitness - 1) );
   end W_Borrow;

To make sure that the new expression does indeed the same thing as the original one, I did both the truth tables and the actual transformation from one to another via Boolean algebra. I'll leave the truth tables as exercise for the interested reader but here's my working for transforming the original expression into mine:

  ( (not A) and B) or ( ( (not A) or B) and D) =

= ( (not A) and B) or ( (not A) and D) or (B and D)

= ( (not A) and (B or D) ) or (B and D)

= (B and D) or ( (not A) and (B or D) )

Given the above, I'm quite satisfied that the two expressions are equivalent and as a result I guess it is a matter of preference whether one chooses my version or Stanislav's. Unless there is some other reason that escapes me for using the original expression there, I find mine easier to understand and so preferable. Note that mine makes sense simply read as it is: there will be a borrow bit if either there are already 2 bits to take away from A (i.e. B and D) or otherwise if there is only one but A is 0. At any rate, since the W_Borrow function is present in the latest Chapter of FFA (12B) precisely as it was introduced in Chapter 1, I made a .vpatch on top of Chapter 12B with my proposed change to W_Borrow:

Note that I've added the corresponding line in the MANIFEST file but I followed the format described by Trinque in the V Manifest specification i.e. including the author name while Stanislav seems to have either forgotten that bit or preferred to not include it.

As a result of Stanislav's blog missing any sort of working comments currently, I wasn't able to simply add all this as a comment to his own Chapter 1 post, where I think it actually belongs. So I'm publishing it here as a post instead and I guess I'll host any further discussion on it too so feel free to leave a comment below.


  1. The regrinds are due to changing the checksums from SHA to Keccak; the content stays the same. However, one needs to read the new vpatches again before one can sign them in any meaningful way. 

  2. All the additional experience I gained with Ada shows when reading code and the difference is apparently large enough to be quite obvious - even hard to ignore basically. 

4 Comments »

  1. Since we're on the subj, I must add also that -- in principle -- separate subtraction logic is unnecessary -- subtract is equivalent to addition-of-a-complement. But it is slightly faster and more readable to have it, hence why I did.

    Your sub eqn. is not only easier on eye but 1 op shorter than the old, I'ma roll it into ch. 13 and link to this piece in the mail-from-readers. ( and yes comment box still broken, and fixing it is a whole project, I gotta port MP's spam filtration system, or even his entire WP thing, but at the very least the former, to make comments work again. )

    Comment by Stanislav Datskovskiy — November 24, 2018 @ 10:46 p.m.

  2. I agree that it's better to have the subtract in there as such even though it's true (and worth saying it, yes) that one could simply do with addition only as you point out, yes.

    Re comments - change is always a pain and certainly eating up some time but I'd say in this case the time is rather right - there are already several guides on setting mp-wp and it really doesn't take all that much. Perhaps you have some other specific bits and pieces that you'd need to port over but at least the blog itself should be done in a couple of hours at most I'd think.

    Comment by Diana Coman — November 25, 2018 @ 1:06 p.m.

  3. Will leave permalink here FTR to where the item in this article was eaten: http://www.loper-os.org/?p=2822

    Comment by Stanislav Datskovskiy — November 29, 2018 @ 10:58 p.m.

  4. Cheers!

    Comment by Diana Coman — November 30, 2018 @ 2:09 p.m.

RSS feed for comments on this post. TrackBack URL

Leave a comment

Theme and content by Diana Coman