“Finite Field Arithmetic.” Chapter 13: "Width-Measure" and "Quiet Shifts."

Published on: Sunday November 25 2018

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_ch13_measure_and_qshifts.kv.vpatch.

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

Now compile ffacalc:

cd ffacalc
gprbuild

But do not run it quite yet.

First, the mail bag!

Reader diana_coman recently found an aesthetically-pleasing equivalence for Chapter 1's W_Borrow function:

Formerly, we had:

   -- 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;

And then diana_coman found that it can be reduced to a much prettier:

   -- 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;

Thank you, diana_coman, for this tidbit! And for reading and signing Chapter 1 and Chapter 2:

I would like to thank diana_coman (as I understand: a potential industrial user!) for her attentive reading, and wish her a happy time with the remaining material in FFA!

In this chapter, we will introduce three new operations on FZ integers. As hinted in Chapter 12B, they will be required for fast modular reduction, which we will meet with later on in the series. But first, we must walk through some older material.

The time has come to review the instruction set of ffacalc, as seen in Chapter 12B:

FFACalc Instruction Set (as seen in Chapter 12B)
Op Description # Ins # Outs Notes
Modes
( Enter Comment Mode 0 0 All further ops ignored until mode is exited; supports nesting
) Exit Comment Mode 0 0 Fatal if not in comment mode
[ Enter Quote Mode 0 0 All further ops are echoed verbatim until mode is exited; supports nesting
] Exit Quote Mode 0 0 Fatal if not in quote mode
{ Enter Conditional Branch 1 0 If input = 1, execute all ops until }; otherwise skip them; supports nesting
} Exit Conditional Branch 0 1 Produces 1 if branch being exited had been taken, otherwise produces 0
Stack Motion
" Dup 1 2 Put two copies of the input on stack
_ Drop 1 0 Discard the item on top of stack
' Swap 2 2 Exchange top and second item
` Over 2 3 Put copy of second item on stack
Constants
. Push Zero 0 1 Put a brand-new zero on stack
0..9, A..F, a..f Insert Hexadecimal Digit 1 1 Insert the given hexadecimal digit as the junior-most nibble into the top item
Predicates
= Equals 2 1 Put 1 on stack if the top and second items are bitwise-equal, otherwise 0
< Less-Than 2 1 Put 1 on stack if the second item is less than the top item
> Greater-Than 2 1 Put 1 on stack if the second item is greater than the top item
Bitwise
& Bitwise-AND 2 1 Compute bitwise-AND of the top and second item, put result on stack
| Bitwise-OR 2 1 Compute bitwise-OR of the top and second item, put result on stack
^ Bitwise-XOR 2 1 Compute bitwise-XOR of the top and second item, put result on stack
~ Bitwise-Complement 1 1 Compute 1s-complement negation of the top item on stack
U Bitwise-MUX 3 1 If top item's junior-most Word is nonzero, the second item will be the result; otherwise the third item will.
Arithmetic: Basic
- Subtract 2 1 Subtract top item from second item, put result on stack, and save borrow bit into Flag
+ Add 2 1 Add top and second item, put result on stack, and save carry bit into Flag
O Push Overflow Flag 0 1 Put Flag, the register containing carry or borrow from the most recent arithmetic op, on the stack
Arithmetic: Division
\ Divide with Remainder 2 2 Divide second item by top item, put quotient and then remainder on stack; division by zero is fatal
/ Divide without Remainder 2 1 Divide second item by top item, put only quotient on stack; division by zero is fatal
% Modulus 2 1 Divide second item by top item, put only remainder on stack; division by zero is fatal
Arithmetic: Multiplication
* Multiply 2 2 Multiply second item and top item, put the junior half of the result on stack, and then the senior half
S Square 1 2 Square the top item, put the junior half of the result on stack, and then the senior half
M Modular Multiplication 3 1 Multiply third item and second item, modulo the top item, put the result on stack (it necessarily fits in one FZ); division by zero is fatal
X Modular Exponentiation 3 1 Raise third item to the power of the second item, modulo the top item, put the result on stack (it necessarily fits in one FZ); division by zero is fatal
I/O
# Print FZ 1 0 Print top item to console, in hexadecimal representation
? Random 0 1 Fill a FZ from the active RNG and put on stack
Control
Z Zap 0 0 Reset ffacalc, clearing stack and all other state
Q Quit 0 0 Quit ffacalc, after printing stack contents

The attentive reader should not find any surprises in the above summary.

However, do not get too comfortable with this instruction set, for we are about to make a few quite substantial changes to it.

In particular, you have probably already guessed that the set of printable ASCII characters is not in fact large enough to cleanly represent all cryptographically-necessary operations on integers. And therefore we will be introducing a small number of prefixed ops:

ffa_calc.adb

      -- ...
 
      -- Prefixed Operators
      PrevC      : Character := ' ';
      HavePrefix : Boolean   := False;
 
      -- Clear the stack and set SP to bottom.
      procedure Zap is
      begin
         -- .................
         -- .................
 
         -- Clear prefix
         HavePrefix := False;
         PrevC      := ' ';
      end Zap;
 
      -- ...
 
      -- Denote that the given op is a prefix
      procedure IsPrefix is
      begin
         HavePrefix := True;
      end IsPrefix;
 
      -- ...
 
      -- Execute a Normal Op
      procedure Op_Normal(C : in Character) is
 
      -- ...
               --------------
               -- Prefixes --
               --------------
 
               -- 'Left...'    :
            when 'L' =>
               IsPrefix;
 
               -- 'Right...'   :
            when 'R' =>
               IsPrefix;
 
               -- 'Modular...' :
            when 'M' =>
               IsPrefix;
 
      -- Execute a Prefixed Op
      procedure Op_Prefixed(Prefix : in Character;
                            O      : in Character) is
      begin
 
         -- The Prefixed Op:
         case Prefix is
 
            ---------------------------------------------------------
            -- Left...
            when 'L' =>
 
               -- Which L-op?
               case O is
 
                  -- ... Shift  :
                  when 'S' =>
                     Want(2);
                     declare
                        -- Number of bit positions to shift by:
                        ShiftCount : FZBit_Index
                          := FZBit_Index(FFA_FZ_Get_Head(Stack(SP)));
                     begin
                        FFA_FZ_Quiet_ShiftLeft(N        => Stack(SP - 1),
                                               ShiftedN => Stack(SP - 1),
                                               Count    => ShiftCount);
                     end;
                     Drop;
 
                  -- ... Rotate :
                  when 'R' =>
                     E("Left-Rotate not yet defined!");
 
                  -- ... Unknown:
                  when others =>
                     E("Undefined Op: L" & O);
 
               end case;
            ---------------------------------------------------------
            -- Right...
            when 'R' =>
 
               -- Which R-op?
               case O is
 
                  -- ... Shift:
                  when 'S' =>
                     Want(2);
                     declare
                        -- Number of bit positions to shift by:
                        ShiftCount : FZBit_Index
                          := FZBit_Index(FFA_FZ_Get_Head(Stack(SP)));
                     begin
                        FFA_FZ_Quiet_ShiftRight(N        => Stack(SP - 1),
                                                ShiftedN => Stack(SP - 1),
                                                Count    => ShiftCount);
                     end;
                     Drop;
 
                  -- ... Rotate:
                  when 'R' =>
                     E("Right-Rotate not yet defined!");
 
                  -- ... Unknown:
                  when others =>
                     E("Undefined Op: R" & O);
 
               end case;
            ---------------------------------------------------------
            -- Modular...   
            when 'M' =>
 
               -- Which M-op?
               case O is
 
                  -- ... Multiplication :
                  when '*' =>
                     Want(3);
                     MustNotZero(Stack(SP));
                     FFA_FZ_Modular_Multiply(X       => Stack(SP - 2),
                                             Y       => Stack(SP - 1),
                                             Modulus => Stack(SP),
                                             Product => Stack(SP - 2));
                     Drop;
                     Drop;
 
                  -- ... Exponentiation :
                  when 'X' =>
                     Want(3);
                     MustNotZero(Stack(SP));
                     FFA_FZ_Modular_Exponentiate(Base     => Stack(SP - 2),
                                                 Exponent => Stack(SP - 1),
                                                 Modulus  => Stack(SP),
                                                 Result   => Stack(SP - 2));
                     Drop;
                     Drop;
 
                  -- ... Unknown:
                  when others =>
                     E("Undefined Op: M" & O);
 
               end case;
            ---------------------------------------------------------
            -- ... Unknown: (impossible per mechanics, but must handle case)
            when others =>
               E("Undefined Prefix: " & Prefix);
 
         end case;
 
      end Op_Prefixed;
 
 
      -- Process a Symbol
      procedure Op(C : in Character) is
      begin
         --- ..............
         --- ..............
 
            --- ... if in a prefixed op:
         elsif HavePrefix then
 
            -- Drop the prefix-op hammer, until another prefix-op cocks it
            HavePrefix := False;
 
            -- Dispatch this op, where prefix is the preceding character
            Op_Prefixed(Prefix => PrevC, O => C);
 
         else
            -- This is a Normal Op, so proceed with the normal rules.
            Op_Normal(C);
         end if;
 
      end Op;
 
 
      -- Current Character
      C : Character;
 
   begin
      -- Reset the Calculator      
      Zap;
      -- Process characters until EOF:
      loop
         if Read_Char(C) then
            -- Execute Op:
            Op(C);
            -- Advance Odometer
            Pos := Pos + 1;
            -- Save the op for use in prefixed ops
            PrevC := C;
         else
            Zap;
            Quit(0); -- if EOF, we're done
         end if;
      end loop;
   end;

The mechanism is quite simple -- certain operation codes now signify prefixes, which permit clean and readable names for certain commands which come in multiple flavours -- left vs right shifts, ordinary vs. modular arithmetic procedures, and so on.

Also note that, from this point on, the use of undefined printable ASCII characters is a fatal error in ffacalc:

ffa_calc.adb

            --- .......
               ---------------------------------------------------------
               -- Reserved Ops, i.e. ones we have not defined yet:   --
               ---------------------------------------------------------
            when '!' | '@' | '$' | ':' | ';' | ',' |
                 'G' | 'H' | 'I' | 'J' | 'K' | 'N' |
                 'P' | 'T' | 'V' | 'X' | 'Y' =>
 
               E("This Operator is not defined yet: " & C);
               ---------------------------------------------------------

Let's summarize the changes in this chapter with a new instruction set table:

FFACalc Instruction Set (as seen in Chapter 13)
Op Description # Ins # Outs Notes
Modes
( Enter Comment Mode 0 0 All further ops ignored until mode is exited; supports nesting
) Exit Comment Mode 0 0 Fatal if not in comment mode
[ Enter Quote Mode 0 0 All further ops are echoed verbatim until mode is exited; supports nesting
] Exit Quote Mode 0 0 Fatal if not in quote mode
{ Enter Conditional Branch 1 0 If input = 1, execute all ops until }; otherwise skip them; supports nesting
} Exit Conditional Branch 0 1 Produces 1 if branch being exited had been taken, otherwise produces 0
Stack Motion
" Dup 1 2 Put two copies of the input on stack
_ Drop 1 0 Discard the item on top of stack
' Swap 2 2 Exchange top and second item
` Over 2 3 Put copy of second item on stack
Constants
. Push Zero 0 1 Put a brand-new zero on stack
0..9, A..F, a..f Insert Hexadecimal Digit 1 1 Insert the given hexadecimal digit as the junior-most nibble into the top item
Predicates
= Equals 2 1 Put 1 on stack if the top and second items are bitwise-equal, otherwise 0
< Less-Than 2 1 Put 1 on stack if the second item is less than the top item
> Greater-Than 2 1 Put 1 on stack if the second item is greater than the top item
Bitwise
& Bitwise-AND 2 1 Compute bitwise-AND of the top and second item, put result on stack
| Bitwise-OR 2 1 Compute bitwise-OR of the top and second item, put result on stack
^ Bitwise-XOR 2 1 Compute bitwise-XOR of the top and second item, put result on stack
~ Bitwise-Complement 1 1 Compute 1s-complement negation of the top item on stack
U Bitwise-MUX 3 1 If top item's junior-most Word is nonzero, the second item will be the result; otherwise the third item will.
W Width-Measure 1 1 Find the position of the senior-most bit in the top item that equals 1 (or return 0 if there are none).
RS Right-Shift 2 1 Shift the second item right by the number of bits given in the top item modulo the FZ bitness.
LS Left-Shift 2 1 Shift the second item left by the number of bits given in the top item modulo the FZ bitness.
Arithmetic: Basic
- Subtract 2 1 Subtract top item from second item, put result on stack, and save borrow bit into Flag
+ Add 2 1 Add top and second item, put result on stack, and save carry bit into Flag
O Push Overflow Flag 0 1 Put Flag, the register containing carry or borrow from the most recent arithmetic op, on the stack
Arithmetic: Division
\ Divide with Remainder 2 2 Divide second item by top item, put quotient and then remainder on stack; division by zero is fatal
/ Divide without Remainder 2 1 Divide second item by top item, put only quotient on stack; division by zero is fatal
% Modulus 2 1 Divide second item by top item, put only remainder on stack; division by zero is fatal
Arithmetic: Multiplication
* Multiply 2 2 Multiply second item and top item, put the junior half of the result on stack, and then the senior half
S Square 1 2 Square the top item, put the junior half of the result on stack, and then the senior half
M* Modular Multiplication 3 1 Multiply third item and second item, modulo the top item, put the result on stack (it necessarily fits in one FZ); division by zero is fatal
MX Modular Exponentiation 3 1 Raise third item to the power of the second item, modulo the top item, put the result on stack (it necessarily fits in one FZ); division by zero is fatal
I/O
# Print FZ 1 0 Print top item to console, in hexadecimal representation
? Random 0 1 Fill a FZ from the active RNG and put on stack
Control
Z Zap 0 0 Reset ffacalc, clearing stack and all other state
Q Quit 0 0 Quit ffacalc, after printing stack contents
Not Yet Defined:
! Undefined 0 0 Prohibited
@ Undefined 0 0 Prohibited
$ Undefined 0 0 Prohibited
: Undefined 0 0 Prohibited
; Undefined 0 0 Prohibited
, Undefined 0 0 Prohibited
G Undefined 0 0 Prohibited
H Undefined 0 0 Prohibited
I Undefined 0 0 Prohibited
J Undefined 0 0 Prohibited
K Undefined 0 0 Prohibited
N Undefined 0 0 Prohibited
P Undefined 0 0 Prohibited
T Undefined 0 0 Prohibited
V Undefined 0 0 Prohibited
X Undefined 0 0 Prohibited (outside of MX)
Y Undefined 0 0 Prohibited

Observe that the modular exponentiation command is now MX, and modular multiplication is now M*. This is a cleaner notation than what was given previously, and permits room for other modular variants of common arithmetic operations, as well as e.g. non-modular exponentiation (in a future chapter.)

Observe also that there are three new operations given: W, RS, and LS. The remainder of this chapter is devoted to illuminating these.

Let's begin with W, or Width-Measure:

ffa_calc.adb

            -- ...
               -- Find the position of eldest nonzero bit, if any exist
            when 'W' =>
               Want(1);
               declare
                  Measure : Word;
               begin
                  -- Find the measure ( 0 if no 1s, or 1 .. FZBitness )
                  Measure := FFA_FZ_Measure(Stack(SP));
                  -- Put on top of stack
                  FFA_FZ_Clear(Stack(SP));
                  FFA_FZ_Set_Head(Stack(SP), Measure);
               end;

So let's see how FFA_FZ_Measure works:

fz_measr.adb

   -- Find the index of eldest nonzero bit ( 0 if none, or 1 .. FZBitness )
   function FZ_Measure(N : in FZ) return Word is
 
      -- The result (default : 0, will remain 0 if N is in fact zero)
      Index     : Word := 0;
 
      -- The currently-examined Word, starting from the junior-most
      Ni        : Word;
 
      -- The most recently-seen nonzero Word, if indeed any exist
      W         : Word := 0;
 
      -- 1 if currently-examined Word is zero, otherwise 0
      NiZ       : WBool;
 
   begin
 
      -- Find, in constant time, eldest non-zero Word:
      for i in 0 .. Indices(N'Length - 1) loop
         Ni    := N(N'First + i);              -- Ni := current Word;
         NiZ   := W_ZeroP(Ni);                 -- ... is this Word = 0?
         Index := W_Mux(Word(i), Index, NiZ);  -- If NO, save the Index,
         W     := W_Mux(Ni,      W,     NiZ);  -- ... and save that Word.
      end loop;
 
      -- Set Index to be the bit-position of the eldest non-zero Word:
      Index := Shift_Left(Index, BitnessLog2); -- Index := Index * Bitness
 
      -- Find, in constant time, eldest non-zero bit in that Word:
      for b in 1 .. Bitness loop
         -- If W is non-zero, advance the Index...
         Index := W_Mux(Index + 1, Index, W_ZeroP(W));
         -- ... in either case, advance W:
         W     := Shift_Right(W, 1);
      end loop;
 
      -- If N = 0, result will be 0; otherwise: index of the eldest 1 bit.
      return Index;
 
   end FZ_Measure;

The key to grasping this FFA routine, just the same as others, is to think: "How would I do this as a constant-spacetime operation?" Chances are, you would come up with exactly the same algorithm, if you were to sit down with a clean sheet of paper and give it a try.

We want to find the eldest 1-bit of the input N (supposing any exist) by performing the same set of mechanical operations regardless of what the contents of N are.

First, we walk through all of the Words of N, from junior-most to senior-most, while saving the position of the highest Word we have found to be nonzero.

After this, we do the exact same thing for the individual bits in that Word (or, observe, those of a null Word, if no non-zero Words exist in N.)

In the end, we will have found a value Index, which represents the position of the highest bit in N that is equal to 1. If no such bits exist, Index will equal 0 -- and we do this without taking any branches or memory-accesses that depend on the contents of N.

Observe also that the process works not only in constant time, but also regardless of the particular array indexing frame of N -- this will come in handy when FZ_Measure is later used as an internal subcomponent of other FFA operations.

Play with W to get a sense of what it's good for, e.g.: 

$ echo ".W#" | ./bin/ffa_calc 256 32
0000000000000000000000000000000000000000000000000000000000000000
$ echo ".1W#" | ./bin/ffa_calc 256 32
0000000000000000000000000000000000000000000000000000000000000001
$ echo ".DEADF00DW#" | ./bin/ffa_calc 256 32
0000000000000000000000000000000000000000000000000000000000000020
$ echo ".~W#" | ./bin/ffa_calc 256 32
0000000000000000000000000000000000000000000000000000000000000100
$ echo ".~W#" | ./bin/ffa_calc 4096 32
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000001000

When you have satisfied yourself that you understand W, we can proceed to the remaining new operations, the Quiet Shifts:

ffa_calc.adb

            ---------------------------------------------------------
            -- Left...
            when 'L' =>
 
               -- Which L-op?
               case O is
 
                  -- ... Shift  :
                  when 'S' =>
                     Want(2);
                     declare
                        -- Number of bit positions to shift by:
                        ShiftCount : FZBit_Index
                          := FZBit_Index(FFA_FZ_Get_Head(Stack(SP)));
                     begin
                        FFA_FZ_Quiet_ShiftLeft(N        => Stack(SP - 1),
                                               ShiftedN => Stack(SP - 1),
                                               Count    => ShiftCount);
                     end;
                     Drop;
 
            -- ................
 
            ---------------------------------------------------------
            -- Right...
            when 'R' =>
 
               -- Which R-op?
               case O is
 
                  -- ... Shift:
                  when 'S' =>
                     Want(2);
                     declare
                        -- Number of bit positions to shift by:
                        ShiftCount : FZBit_Index
                          := FZBit_Index(FFA_FZ_Get_Head(Stack(SP)));
                     begin
                        FFA_FZ_Quiet_ShiftRight(N        => Stack(SP - 1),
                                                ShiftedN => Stack(SP - 1),
                                                Count    => ShiftCount);
                     end;
                     Drop;

Let's dig into the two new mechanisms: FFA_FZ_Quiet_ShiftLeft and FFA_FZ_Quiet_ShiftRight:

fz_qshft.adb

   -- Constant-time arbitrary Right-Shift.
   procedure FZ_Quiet_ShiftRight(N        : in     FZ;
                                 ShiftedN : in out FZ;
                                 Count    : in     FZBit_Index) is
 
      -- Total number of bit positions to shift by
      C     : constant Word     := Word(Count);
 
      -- Number of sub-Word bit positions to shift by
      Bits  : constant Natural  := Natural(C and (2**BitnessLog2 - 1));
 
      -- The Bitness of N's Length
      Wb    : constant Positive := FZ_Bitness_Log2(N);
 
      -- Number of whole-Word bitnesses to shift by
      Words : Word              := Shift_Right(C, BitnessLog2);
 
      -- Current 'shiftness level'
      S     : Indices           := 1;
 
   begin
 
      -- Subword shift first:
      if HaveBarrelShifter then
         -- If permitted, use iron shifter:
         FZ_ShiftRight(N, ShiftedN, Bits);
      else
         -- Otherwise, use the soft subword shifter:
         FZ_Quiet_ShiftRight_SubW_Soft(N, ShiftedN, Bits);
      end if;
 
      -- Then whole-Word shift:
      for i in 1 .. Wb loop
 
         declare
 
            -- Current bit of Words
            WordsBit : constant WBool := Words and 1;
 
         begin
 
            -- Shift at the current shiftness
            for i in ShiftedN'First        .. ShiftedN'Last - S loop
               ShiftedN(i) := W_Mux(ShiftedN(i), ShiftedN(i + S), WordsBit);
            end loop;
 
            -- Fill the emptiness
            for i in ShiftedN'Last - S + 1 .. ShiftedN'Last loop
               ShiftedN(i) := W_Mux(ShiftedN(i), 0,               WordsBit);
            end loop;
 
            -- Go to the next shiftness level
            S     := S * 2;
            Words := Shift_Right(Words, 1);
 
         end;
 
      end loop;
 
   end FZ_Quiet_ShiftRight;
 
 
   -- Constant-time arbitrary Left-Shift.
   procedure FZ_Quiet_ShiftLeft(N        : in     FZ;
                                ShiftedN : in out FZ;
                                Count    : in     FZBit_Index) is
 
      -- Total number of bit positions to shift by
      C     : constant Word     := Word(Count);
 
      -- Number of sub-Word bit positions to shift by
      Bits  : constant Natural  := Natural(C and (2**BitnessLog2 - 1));
 
      -- The Bitness of N's Length
      Wb    : constant Positive := FZ_Bitness_Log2(N);
 
      -- Number of whole-Word bitnesses to shift by
      Words : Word              := Shift_Right(C, BitnessLog2);
 
      -- Current 'shiftness level'
      S     : Indices           := 1;
 
   begin
 
      -- Subword shift first:
      if HaveBarrelShifter then
         -- If permitted, use iron shifter:
         FZ_ShiftLeft(N, ShiftedN, Bits);
      else
         -- Otherwise, use the soft subword shifter:
         FZ_Quiet_ShiftLeft_SubW_Soft(N, ShiftedN, Bits);
      end if;
 
      -- Then whole-Word shift:
      for i in 1 .. Wb loop
 
         declare
 
            -- Current bit of Words
            WordsBit : constant WBool := Words and 1;
 
         begin
 
            -- Shift at the current shiftness
            for i in reverse ShiftedN'First + S .. ShiftedN'Last loop
               ShiftedN(i) := W_Mux(ShiftedN(i), ShiftedN(i - S), WordsBit);
            end loop;
 
            -- Fill the emptiness
            for i in ShiftedN'First             .. ShiftedN'First + S - 1 loop
               ShiftedN(i) := W_Mux(ShiftedN(i), 0,               WordsBit);
            end loop;
 
            -- Go to the next shiftness level
            S     := S * 2;
            Words := Shift_Right(Words, 1);
 
         end;
 
      end loop;
 
   end FZ_Quiet_ShiftLeft;

The leitmotif here is exactly the same as in FZ_Measure: in either the left or right case, we find the amount of whole-Word motion and the amount of sub-Word motion; these feed into separate operations that perform the requisite amount of shifting in constant time.

The attentive reader will have noticed the presence of FZ_Bitness_Log2, a new routine. This is a simple mechanism to determine the "bitness" of the Word count of the FZ N:

fz_basic.adb

   -- Determine the Bitness of the given FZ's Length
   function FZ_Bitness_Log2(N : in FZ) return Positive is
      W : Bit_Count := N'Length;
      R : Positive  := 1;
   begin
      while W > 1 loop
         W := W / 2;
         R := R + 1;
      end loop;
      return R - 1;
   end FZ_Bitness_Log2;

And now it is time for... an exercise!

Chapter 13 Exercise #1:


Explain why the branching logic appearing in FZ_Bitness_Log2 does not compromise the constant-time operation of FZ_Quiet_ShiftLeft and FZ_Quiet_ShiftRight.

When you have solved the Exercise, we can move on to the other interesting components of the Quiet Shifts routines: FZ_Quiet_ShiftLeft_SubW_Soft and FZ_Quiet_ShiftRight_SubW_Soft.

On some particularly-sad machine architectures, there is no barrel shifter.

And therefore, FZ_ShiftRight and FZ_ShiftLeft will bleed, via a timing side-channel, the number of positions being shifted. This is absolutely prohibited in FFA, and therefore we must introduce a knob which toggles a set of optional "soft" fallback shifters:

iron.ads

   -- Whether we have a barrel shifter:
   HaveBarrelShifter : constant Boolean := True;

These being:

fz_qshft.adb

   -- Constant-time subword shift, for where there is no barrel shifter
   procedure FZ_Quiet_ShiftRight_SubW_Soft(N        : in FZ;
                                           ShiftedN : in out FZ;
                                           Count    : in WBit_Index) is
      Nw  : constant Word  := Word(Count);
      nC  : constant WBool := W_ZeroP(Nw); -- 'no carry' for Count == 0 case
      Ni  : Word := 0; -- Current word
      C   : Word := 0; -- Current carry
      S   : Positive;  -- Current shiftness level
      B   : Word;      -- Quantity of shift (bitwalked over)
      CB  : Word;      -- Quantity of carry counter-shift (bitwalked over)
      St  : Word;      -- Temporary word shift candidate
      Ct  : Word;      -- Temporary carry counter-shift candidate
   begin
      for i in reverse N'Range loop
         Ni          := N(i);
         ShiftedN(i) := C;
         C           := W_Mux(Ni, 0, nC);
         S           := 1;
         B           := Nw;
         CB          := Word(Bitness) - B;
         -- For each shift level (of the subword shiftvalue width) :
         for j in 1 .. BitnessLog2 loop
            -- Shift and mux the current word
            St := Shift_Right(Ni, S);
            Ni := W_Mux(Ni, St, B and 1);
            -- Shift and mux the current carry
            Ct := Shift_Left(C, S);
            C  := W_Mux(C,  Ct, CB and 1);
            -- Go to the next shiftness level
            S  := S * 2;
            B  := Shift_Right(B,  1);
            CB := Shift_Right(CB, 1);
         end loop;
         -- Slide in the carry from the previous shift
         ShiftedN(i) := ShiftedN(i) or Ni;
      end loop;
   end FZ_Quiet_ShiftRight_SubW_Soft;
 
 
   -- Constant-time subword shift, for where there is no barrel shifter
   procedure FZ_Quiet_ShiftLeft_SubW_Soft(N        : in FZ;
                                          ShiftedN : in out FZ;
                                          Count    : in WBit_Index) is
      Nw  : constant Word  := Word(Count);
      nC  : constant WBool := W_ZeroP(Nw); -- 'no carry' for Count == 0 case
      Ni  : Word := 0; -- Current word
      C   : Word := 0; -- Current carry
      S   : Positive;  -- Current shiftness level
      B   : Word;      -- Quantity of shift (bitwalked over)
      CB  : Word;      -- Quantity of carry counter-shift (bitwalked over)
      St  : Word;      -- Temporary word shift candidate
      Ct  : Word;      -- Temporary carry counter-shift candidate
   begin
      for i in N'Range loop
         Ni          := N(i);
         ShiftedN(i) := C;
         C           := W_Mux(Ni, 0, nC);
         S           := 1;
         B           := Nw;
         CB          := Word(Bitness) - B;
         -- For each shift level (of the subword shiftvalue width) :
         for j in 1 .. BitnessLog2 loop
            -- Shift and mux the current word
            St := Shift_Left(Ni, S);
            Ni := W_Mux(Ni, St, B and 1);
            -- Shift and mux the current carry
            Ct := Shift_Right(C, S);
            C  := W_Mux(C,  Ct, CB and 1);
            -- Go to the next shiftness level
            S  := S * 2;
            B  := Shift_Right(B,  1);
            CB := Shift_Right(CB, 1);
         end loop;
         -- Slide in the carry from the previous shift
         ShiftedN(i) := ShiftedN(i) or Ni;
      end loop;
   end FZ_Quiet_ShiftLeft_SubW_Soft;

However, note that HaveBarrelShifter is enabled by default in canonical FFA.

If you suspect that you are running FFA on iron which lacks a barrel shifter, you are responsible for determining whether this is so, and then, if the answer is yes, disabling the toggle: 

   -- Whether we have a barrel shifter:
   HaveBarrelShifter : constant Boolean := False;

... but in either case you must fully grasp how the fallback mechanism operates -- you never know when you will need it, and at any rate: one ought not to make battlefield use of cryptographic code without first having fitted it into your head!

And now, time for another exercise:

Chapter 13 Exercise #2:


Bit-rotation routines have not yet been given in FFA. Write a set of working right- and left- rotators of arbitrary integers as ffacalc tapes. Ensure that they Do The Right Thing if supplied with deltas which exceed the given FZ Bitness.

In Chapter 14, we will meet with a serious constructive use for FFA_FZ_Measure, FFA_FZ_Quiet_ShiftLeft and FFA_FZ_Quiet_ShiftRight. Stay tuned!

~To be continued!~
This entry was written by Stanislav , posted on Sunday November 25 2018 , filed under Ada, Bitcoin, Cold Air, Computation, Cryptography, FFA, Friends, Mathematics, ShouldersGiants, SoftwareArchaeology, 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:

123 xor 12 = ?

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!

« »