“Finite Field Arithmetic.” Chapter 19: Peh Tuning and Demo Tapes.

Published on: Saturday June 01 2019

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 vpatches and seals to your V-set, and press to ffa_ch19_peh_tuning_and_demos.kv.vpatch.

You should end up with the same directory structure as previously.

As of Chapter 19, the versions of Peh and FFA are 250 and 253, respectively.

The demo tapes from Chapter 18C have been added to the Peh v-set and are henceforth available under the subdirectory demos.

Now compile Peh:

cd ffacalc
gprbuild

But do not run it quite yet.

First, the mail bag!

Reader PeterL observed that the declare block in:

fz_divis.adb:

   -- Modulus. Permits the asymmetric Dividend and Divisor in FZ_Mod_Exp.
   procedure FZ_Mod(Dividend  : in FZ;
                    Divisor   : in FZ;
                    Remainder : out FZ) is
 
      -- ......................................
      -- ......................................
 
      -- Performs Restoring Division on a given segment of Dividend:Divisor
      procedure Slice(Index : Dividend_Index;
                      Cut   : Divisor_Cuts) is
      begin
 
         declare
 
            -- Borrow, from comparator
            C   : WBool;
 
            -- Left-Shift Overflow
            LsO : WBool;
 
            -- Current cut of Remainder register
            Rs  : FZ renames R(1 .. Cut);
 
            -- Current cut of Divisor
            Ds  : FZ renames Divisor(1 .. Cut);
 
            -- Current word of Dividend, starting from the highest
            W   : Word  := Dividend(Dividend'Last + 1 - Index);
 
         begin
 
            -- For each bit in the current Dividend word:
            for b in 1 .. Bitness loop
 
               -- Send top bit of current Dividend word to the bottom of W
               W := Rotate_Left(W, 1);
 
               -- Advance Rs, shifting in the current Dividend bit
               FZ_ShiftLeft_O_I(N => Rs, ShiftedN => Rs, Count => 1,
                                OF_In => W and 1,
                                Overflow => LsO);
 
               -- Subtract Divisor-Cut from R-Cut; Underflow goes into C
               FZ_Sub(X => Rs, Y => Ds, Difference => Rs, Underflow => C);
 
               -- If C=1, subtraction underflowed, and we must undo it:
               FZ_Add_Gated(X => Rs, Y => Ds, Sum => Rs,
                            Gate => C and W_Not(LsO));
 
            end loop;
 
         end;
 
      end Slice;
 
      -- ......................................
      -- ......................................

... is redundant. It has been removed as of this Chapter. As this removal has no effect on the built binary, the FFA version number is unchanged.

Thank you, reader PeterL!

Now, let's eat the meat of this Chapter.

Before we can proceed with what was promised at the conclusion of Chapter 18, we will offer some simplification of the Peh moving parts, and fix a small but potentially dangerous flaw in the semantics of the Overflow Flag. Let's start with the former.

Recall where in Chapter 18, we have the reader modality controls:

ffa_calc.adb:

   -- Start a Peh Machine with the given Dimensions and Tape; return a Verdict.
   function Peh_Machine(Dimensions : in Peh_Dimensions;
                        Tape       : in Peh_Tapes;
                        RNG        : in RNG_Device) return Peh_Verdicts is
 
   ............
   ............
 
      -- Whether we are currently inside a Proposed Subroutine Name:
      SubNameMode   : Boolean      := False;
 
      -- Whether we are currently inside a Proposed Subroutine Body:
      SubBodyMode   : Boolean      := False;
 
   ............
 
      -- Prefixed Operators
      PrevC         : Character    := ' ';
      HavePrefix    : Boolean      := False;
 
   ............

... and the resulting somewhat gnarly-looking tower of "if-then" ?

As of the present Chapter, these have been replaced with:

ffa_calc.adb:

   -- Start a Peh Machine with the given Dimensions and Tape; return a Verdict.
   function Peh_Machine(Dimensions : in Peh_Dimensions;
                        Tape       : in Peh_Tapes;
                        RNG        : in RNG_Device) return Peh_Verdicts is
 
   ............
   ............
 
      -- The possible Modes of the reader:
      type Modes is (Normal, SubName, SubBody, PrefixOp);
 
      -- Currently-active reader Mode:
      Mode          : Modes        := Normal;
 
   ............
 
      -- Prefixed Operators
      PrevC         : Character    := ' ';
 
   ............

... and consequently, Op is now a much more readable item:

ffa_calc.adb:

      -- All Peh Symbols begin their processing here :
      procedure Op(C : in Character) is
      begin
 
         -- See whether we are inside a 'Block' :
 
         -- ... in a Comment block:
         if CommLevel > 0 then
            case C is
               when ')' =>  -- Drop a nesting level:
                  CommLevel := CommLevel - 1;
               when '(' =>  -- Add a nesting level:
                  CommLevel := CommLevel + 1;
               when others =>
                  null; -- Other symbols have no effect at all
            end case;
 
            -- ... in a Quote block:
         elsif QuoteLevel > 0 then
            case C is
               when ']' =>   -- Drop a nesting level:
                  QuoteLevel := QuoteLevel - 1;
               when '[' =>   -- Add a nesting level:
                  QuoteLevel := QuoteLevel + 1;
               when others =>
                  null; -- Other symbols have no effect on the level
            end case;
 
            -- If we aren't the mode-exiting ']', print current symbol:
            if QuoteLevel > 0 then
               Write_Char(C);
            end if;
 
            --- ... in a ~taken~ Conditional branch:
         elsif CondLevel > 0 then
            case C is
               when '}' =>   -- Drop a nesting level:
                  CondLevel := CondLevel - 1;
 
                  -- If we exited the Conditional as a result,
                  -- we push a 1 to trigger the possible 'else' clause:
                  if CondLevel = 0 then
                     Push;
                     FFA_WBool_To_FZ(1, Stack(SP));
                  end if;
 
               when '{' =>   -- Add a nesting level:
                  CondLevel := CondLevel + 1;
 
               when others =>
                  null; -- Other symbols have no effect on the level
            end case;
 
         else
            --- ... we are not inside a 'Block' :
 
            case Mode is
 
               --- ... a character in a proposed Subroutine Name:
               when SubName =>
                  SubName_Symbol(C);
 
               --- ... a character in a proposed Subroutine Body:
               when SubBody =>
                  SubBody_Symbol(C);
 
               --- ... the second character of a Prefixed Op:
               when PrefixOp =>
                  -- Drop prefix-op hammer, until another prefix-op cocks it:
                  Mode := Normal;
 
                  -- Dispatch this op, where prefix is the preceding character
                  Op_Prefixed(Prefix => PrevC, O => C);
 
               -- This is a Normal Op...
               when Normal =>
                  -- ... so proceed with the normal rules:
                  Op_Normal(C);
 
                  -- Save the current Symbol as a possible prefix:
                  PrevC := C;
 
            end case;
 
         end if;
      end Op;

SubName_Symbol and SubBody_Symbol do exactly what you would expect, from having read Chapter 18, with the obvious necessary changes in regards to the reader mode state variable. (See also line 1073, with regards to the prefix control.)

This is just about all of the treatment the subject deserves. The Peh version has been advanced to 250K, on account of this and the following change.

Now, let's proceed to the matter of the Overflow Flag.

Recall the discussion of the Cutout system in Chapter 18B.

In particular, the treatment of Registers in the Cutout mechanism :

  1. All Register-accessing opcodes (including Zaps and Debug Print) which execute inside either the Guarded or the Cutout segments, will make use exclusively of the segregated Cutout Register Set.
  2. All Register-accessing opcodes (including Zaps and Debug Print) which execute inside the Public segment, will make use exclusively of the Ordinary Register Set.

Observe that, in Chapter 18, the Overflow Flag -- unlike the registers -- was not included in the set of segregated state which prevents inadvertent flow of information between routines residing in the Cutout Tape segment and those in the rest of a Tape.

This flaw has been corrected as of this Chapter:

ffa_calc.adb:

   -- Start a Peh Machine with the given Dimensions and Tape; return a Verdict.
   function Peh_Machine(Dimensions : in Peh_Dimensions;
                        Tape       : in Peh_Tapes;
                        RNG        : in RNG_Device) return Peh_Verdicts is
 
   ............
   ............
 
      -- Carry/Borrow Flag set by certain arithmetical Ops:
      Flag          : WBool        := 0;
 
      -- 'Cutout'-segregated Carry/Borrow Flag:
      CO_Flag       : WBool        := 0;
 
   ............
 
      -- Zero the currently-active Overflow Flag:
      procedure Zap_Flag is
      begin
         if Use_CO_Registers then
            CO_Flag := 0;
         else
            Flag    := 0;
         end if;
      end Zap_Flag;
 
   ............
   ............
 
      -- Print a Debug Trace (used in 'QD') :
      procedure Print_Trace is
      begin
 
         ............
         ............
 
         -- Print active Overflow-Flag, then Ticks and IP:
 
         if Use_CO_Registers then
            Write_String("Flag (CO) :" & WBool'Image(CO_Flag));
         else
            Write_String("Flag      :" & WBool'Image(Flag));
         end if;
 
   ............
   ............
 
               ----------------
               -- Arithmetic --
               ----------------
 
               -- Subtract
            when '-' =>
               Want(2);
               FFA_FZ_Subtract(X          => Stack(SP - 1),
                               Y          => Stack(SP),
                               Difference => Stack(SP - 1),
                               Underflow  => F);
 
               -- If we are in the Cutout, write the CO_Flag instead of Flag:
               if Use_CO_Registers then
                  CO_Flag := FFA_Word_NZeroP(F);
               else
                  Flag    := FFA_Word_NZeroP(F);
               end if;
               Drop;
 
               -- Add
            when '+' =>
               Want(2);
               FFA_FZ_Add(X        => Stack(SP - 1),
                          Y        => Stack(SP),
                          Sum      => Stack(SP - 1),
                          Overflow => F);
 
               -- If we are in the Cutout, write the CO_Flag instead of Flag:
               if Use_CO_Registers then
                  CO_Flag := FFA_Word_NZeroP(F);
               else
                  Flag    := FFA_Word_NZeroP(F);
               end if;
               Drop;
 
            ............
            ............
            ............
 
               -- Put the Overflow flag on the stack
            when 'O' =>
               Push;
               -- If we are in the Cutout, read CO_Flag instead of Flag:
               if Use_CO_Registers then
                  FFA_WBool_To_FZ(CO_Flag, Stack(SP));
               else
                  FFA_WBool_To_FZ(Flag,    Stack(SP));
               end if;
 
            ............
            ............

The difference in semantics is easily illustrated via the following Peh Tape:

ch19_flag.peh:

(----------------------------------------------------------------------------)
(----------------------------------------------------------------------------)
(- Demo Tape for 'Peh'; illustrates change in Flag semantics in Chapter 19. -)
(-                                                                          -)
(- (C) 2019 Stanislav Datskovskiy ( www.loper-os.org )                      -)
(- http://wot.deedbot.org/17215D118B7239507FAFED98B98228A001ABFFC7.html     -)
(-                                                                          -)
(- You do not have, nor can you ever acquire the right to use, copy or      -)
(- distribute this software ; Should you use this software for any purpose, -)
(- or copy and distribute it to anyone or in any manner, you are breaking   -)
(- the laws of whatever soi-disant jurisdiction, and you promise to         -)
(- continue doing so for the indefinite future. In any case, please         -)
(- always : read and understand any software ; verify any PGP signatures    -)
(- that you use - for any purpose.                                          -)
(-                                                                          -)
(- See also http://trilema.com/2015/a-new-software-licensing-paradigm .     -)
(----------------------------------------------------------------------------)
(----------------------------------------------------------------------------)
 
(----------------------------------------------------------------------------)
 
( Begin the Cutout: )
LC
 
(----------------------------------------------------------------------------)
 
( This subroutine causes the Cutout-Active Overflow Flag to be Set : )
 
@Set-OF-In-Cutout@ ( Regs : none )
        .0 .1 - _
;
 
(----------------------------------------------------------------------------)
 
( This subroutine causes the Cutout-Active Overflow Flag to be Cleared : )
 
@Clear-OF-In-Cutout@ ( Regs : none )
        ZF
;
 
(----------------------------------------------------------------------------)
 
 
( This subroutine returns the Cutout-Active Overflow Flag : )
 
@Get-OF-In-Cutout@ ( Regs : none )
        O
;
 
(----------------------------------------------------------------------------)
 
( Terminate the Cutout : )
RC
 
(----------------------------------------------------------------------------)
 
( This subroutine causes the Ordinary Overflow Flag to be Set : )
 
@Set-OF-Ordinary@ ( Regs : none )
        .0 .1 - _
;
 
(----------------------------------------------------------------------------)
 
( This subroutine causes the Ordinary Overflow Flag to be Cleared : )
 
@Clear-OF-Ordinary@ ( Regs : none )
        ZF
;
 
(----------------------------------------------------------------------------)
 
( This subroutine returns the Ordinary Overflow Flag : )
 
@Get-OF-Ordinary@ ( Regs : none )
        O
;
 
(----------------------------------------------------------------------------)
 
( Display both Overflow Flags : )
@Show-Both-OF-Flags@ (Regs : none)
 
                [Ordinary OF = ]
                @Get-OF-Ordinary!
                {[1]}{[0]}_
 
                [ ]
 
                @Get-OF-In-Cutout!
                [Cutout's OF = ]
                {[1]}{[0]}_
                []
;
 
(----------------------------------------------------------------------------)
 
(------------------------------ Main Program : ------------------------------)
 
( Regs: none )
 
 
[Setting Ordinary OF:
]
@Set-OF-Ordinary!
 
@Show-Both-OF-Flags!
[
 
]
 
[Setting Cutout's OF:
]
@Set-OF-In-Cutout!
 
@Show-Both-OF-Flags!
[
 
]
 
 
( Clear the Flags : )
 
[Clearing Ordinary OF:
]
@Clear-OF-Ordinary!
 
@Show-Both-OF-Flags!
[
 
]
 
[Clearing Cutout's OF:
]
@Clear-OF-In-Cutout!
 
@Show-Both-OF-Flags!
[
 
]
 
 
( we're done:  )
QY
 
(--------------------------------~~The End~~---------------------------------)

This Tape is invoked as, e.g.: 

    cat ch19_flag.peh | ./ffa/ffacalc/bin/peh 256 32 10000 0

In Chapter 18, where there is only one Overflow Flag register, you will expect to see the following output: 

Setting Ordinary OF:
Ordinary OF = 1 Cutout's OF = 1
 
Setting Cutout's OF:
Ordinary OF = 1 Cutout's OF = 1
 
Clearing Ordinary OF:
Ordinary OF = 0 Cutout's OF = 0
 
Clearing Cutout's OF:
Ordinary OF = 0 Cutout's OF = 0

Whereas, as of this Chapter, where the flags are properly segregated, unsurprisingly: 

Setting Ordinary OF:
Ordinary OF = 1 Cutout's OF = 0
 
Setting Cutout's OF:
Ordinary OF = 1 Cutout's OF = 1
 
Clearing Ordinary OF:
Ordinary OF = 0 Cutout's OF = 1
 
Clearing Cutout's OF:
Ordinary OF = 0 Cutout's OF = 0


In Chapter 20, we will proceed with more interesting refinements to Peh.

~To be continued!~
This entry was written by Stanislav , posted on Saturday June 01 2019 , filed under Ada, Bitcoin, Cold Air, Computation, Cryptography, FFA, Friends, Mathematics, SoftwareSucks . Bookmark the permalink . Post a comment below or leave a trackback: Trackback URL.

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:

78 xor 6 = ?

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!

« »