DEFINITION MODULE BigNum;

        (********************************************************)
        (*                                                      *)
        (*           Support for multibit integers              *)
        (*                                                      *)
        (*  Programmer:         P. Moylan                       *)
        (*  Started:            12 November 2017                *)
        (*  Last edited:        18 February 2025                *)
        (*  Status:             OK                              *)
        (*                                                      *)
        (********************************************************)



FROM SYSTEM IMPORT CARD8, CAST;

TYPE BN;    (* is private *)

(********************************************)
(*****              OUTPUT              *****)
(********************************************)

PROCEDURE ShowBNUsage;

    (* Reports how much memory is being used by Bignums.  *)

PROCEDURE WriteBignum (A: BN);

    (* Writes N in decimal to standard output. *)

(********************************************)
(***** CREATING AND DESTROYING A BIGNUM *****)
(********************************************)

PROCEDURE HexToBN (str: ARRAY OF CHAR): BN;

    (* Converts a hexadecimal string in BigEndian format to a Bignum.   *)
    (* Space characters, if present, are ignored.  This appears to      *)
    (* duplicate the function of FromHex below, but here I'm allowing   *)
    (* for the spaces.                                                  *)

PROCEDURE BinToBN (VAR (*IN*) bindata: ARRAY OF CARD8;  pos, N: CARDINAL): BN;

    (* Converts a string of N CARD8 values, starting at bindata[pos],   *)
    (* to a Bignum.  We assume bigendian order in bindata.              *)

PROCEDURE MakeBignum (N: INTEGER): BN;

    (* Converts integer to BN. *)

PROCEDURE Zero(): BN;

    (* Returns a BigNum with value zero.  *)

PROCEDURE Card (num: BN): CARDINAL;

    (* Converts BN to cardinal, saturating result if out of range. *)

PROCEDURE Int (num: BN): INTEGER;

    (* Converts BN to integer, saturating result if out of range. *)

PROCEDURE SingleWord (A: BN;  VAR (*OUT*) val: CARDINAL): BOOLEAN;

    (* Like Card: sets val to the low-order word of A, and  *)
    (* returns TRUE iff this is the complete value.         *)

PROCEDURE Discard (VAR (*INOUT*) num: BN);

    (* Deallocates the storage used by num. *)

PROCEDURE CopyBN (A: BN): BN;

    (* Returns a copy of A. *)

(********************************************)
(*****              SHIFTS              *****)
(********************************************)

PROCEDURE LSBN (VAR (*INOUT*) V: BN;  N: CARDINAL);

    (* Shifts V left by N binary digits. *)

PROCEDURE RSBN (VAR (*INOUT*) V: BN;  N: CARDINAL);

    (* Shifts V right by N binary digits. *)

(********************************************)
(*****            COMPARISONS           *****)
(********************************************)

PROCEDURE Sign (val: BN): INTEGER;

    (* Returns -1 if val < 0, 0 if val = 0, +1 if val > 0.  *)

PROCEDURE IsZero (val: BN): BOOLEAN;

    (* Returns TRUE iff val = 0 *)

PROCEDURE IsOdd (A: BN): BOOLEAN;

    (* Returns TRUE iff A is an odd number.  *)

PROCEDURE Eq (A: BN;  N: CARDINAL): BOOLEAN;

    (* Returns TRUE iff A = N *)

PROCEDURE Cmp (A, B: BN): INTEGER;

    (* Comparison.  Returns -1 if A < B, 0 if A = B, and +1 if A > B.  *)

(********************************************)
(*****             ARITHMETIC           *****)
(********************************************)

PROCEDURE LowWord (A: BN): CARDINAL;

    (* Returns the least significant word of the value of A. *)

PROCEDURE Negate (A: BN);

    (* Changes the sign of A.  *)

PROCEDURE SetLowBit (A: BN);

    (* Makes A odd by incrementing if necessary. *)

PROCEDURE SetHighBit (A: BN;  mask: CARDINAL);

    (* Modifies the most significant word in A by retaining the bits    *)
    (* in mask, and then setting the bit corresponding to the           *)
    (* leftmost bit of mask.  We assume that mask defines a contiguous  *)
    (* set of bits including the least significant bit, and that        *)
    (* mask is not zero.                                                *)

PROCEDURE HighBitSet (A: BN;  mask: CARDINAL): BOOLEAN;

    (* Returns TRUE iff the most significant bit of A is set, after     *)
    (* using mask to clear some high-order bits in the most significant *)
    (* word that should not be set.  The mask defines which bit is most *)
    (* significant.  We assume that mask defines a contiguous set of    *)
    (* bits including the least significant bit, and that mask <> 0.    *)

PROCEDURE Incr (A: BN);

    (* Increases the value of A by 1. *)

PROCEDURE Decr (A: BN);

    (* Reduces the value of A by 1. *)

PROCEDURE Sum (A, B: BN): BN;

    (* Returns A+B. *)

PROCEDURE Diff (A, B: BN): BN;

    (* Returns A-B. *)

PROCEDURE Prod (A,B: BN): BN;

    (* Returns A*B.  *)

PROCEDURE KaraProdU (A,B: BN): BN;

    (* Returns A*B (unsigned) using the Karatsuba algorithm.  *)

    (* NOTE: my timing tests so far that, up to a BigNum size of    *)
    (* 500 words (16000 bits), KaraProdU is about 40 times slower   *)
    (* than Prod. Although this algorithm is asymptotically         *)
    (* faster than tradition multiplication, this implementation    *)
    (* will not have an advantage until the numbers are very large. *)

PROCEDURE ModU (A, B: BN): BN;

    (* Returns A MOD B.  This is an unsigned operation, where we    *)
    (* assume that A and B are nonzero and positive.                *)

PROCEDURE Mod (A, B: BN): BN;

    (* Returns A MOD B, with signed numbers.  *)

PROCEDURE Kconst (nwords, mask: CARDINAL): BN;

    (* Returns the constant K used in unsigned division.  This is for   *)
    (* testing, and this procedure will probably be scrapped later.     *)

PROCEDURE ModCardU (A: BN;  C: CARDINAL): CARDINAL;

    (* Returns the remainder of A divided by C.  This is a direct copy  *)
    (* of DivideByCardU, below, except that we don't calculate the      *)
    (* quotient.  This is an unsigned operation.                        *)

PROCEDURE Divide (A, B: BN;  VAR (*OUT*) Q, R: BN);

    (* Divides A by B, returns quotient and remainder.  This might  *)
    (* need more work for negative A or B.                          *)

PROCEDURE DivideByCardU (A: BN;  C: CARDINAL;  VAR (*OUT*) Q: BN;
                              VAR (*OUT*) remainder: CARDINAL);

    (* Divides A by C, giving quotient Q and a remainder.   *)
    (* This is an unsigned operation.                       *)

PROCEDURE Double (A: BN);

    (* In-place multiplication by two.  *)

PROCEDURE Halve (A: BN);

    (* In-place division by two.  We round towards zero.  *)

(********************************************)
(*****  MISCELLANEOUS OTHER FUNCTIONS  ******)
(********************************************)

PROCEDURE NWords (A: BN): CARDINAL;

    (* Returns the number of words used to hold the value of A. *)

PROCEDURE BNtoBytes (V: BN;  VAR (*OUT*) result: ARRAY OF CARD8): CARDINAL;

    (* Converts a signed Bignum to an array of CARD8 values, in         *)
    (* BigEndian twos complement form.  An initial 0 or 0FFH is         *)
    (* inserted if needed to make the leading bit agree with the sign,  *)
    (* and of course a zero value becomes a single zero byte, but       *)
    (* otherwise there are no leading all-zero or all-one bytes.        *)
    (* The function result is the number of bytes in the result.        *)

PROCEDURE Nwords (A: BN): CARDINAL;

    (* Returns the number of words in A.  *)

PROCEDURE WordVal (A: BN;  j: CARDINAL): CARDINAL;

    (* Returns the jth word in the internal representation of A,    *)
    (* where j=0 means the least significant word.                  *)

PROCEDURE Nbytes (A: BN): CARDINAL;

    (* Returns the number of bytes that BNtoBytes would return.         *)

PROCEDURE BNtoBytesNLZ (V: BN;  VAR (*OUT*) result: ARRAY OF CARD8): CARDINAL;

    (* Like BNtoBytes, except that this is an unsigned operation, and   *)
    (* there is never a leading zero except in the special case where   *)
    (* V is zero.                                                       *)

PROCEDURE NbytesNLZ (A: BN): CARDINAL;

    (* Returns the number of bytes needed to express A as a byte string *)
    (* with no leading zeros. (Or 1 for the special case A = 0.)        *)

PROCEDURE BNtoBytesExact (V: BN;  N: CARDINAL;
                                    VAR (*OUT*) result: ARRAY OF CARD8);

    (* Like BNtoBytes, except that leading zeroes are inserted if       *)
    (* necessary to ensure that the result length is exactly N bytes.   *)

    (* There are no guarantees if the result doesn't fit.   *)

PROCEDURE Nbits (A: BN): CARDINAL;

    (* Returns the number of significant bits in A.  Equivalently,      *)
    (* returns an N such that A >= 2^(N-1) but A < 2^N.                 *)
    (* Special case: if A is zero we return 0.                          *)

PROCEDURE Digits (A: BN): CARDINAL;

    (* An estimate of the number of decimal digits in A.  Since we      *)
    (* don't calculate this precisely, we err if necessary on the high  *)
    (* side.  For negative A, we count the '-' as an extra "digit".     *)

PROCEDURE ModularPower (base, exponent, modulus: BN): BN;

    (* Calculates base^exponent MOD modulus.  We use the traditional    *)
    (* fast squaring method, but with modular reduction to stop the     *)
    (* intermediate results from getting too large.                     *)

PROCEDURE Rand (N: CARDINAL): BN;

    (* Produces a random N-word nonnegative number.  *)

(********************************************)
(***** CONVERSION FROM/TO ALPHANUMERIC ******)
(********************************************)

PROCEDURE FromHex (hexdata: ARRAY OF CHAR): BN;

    (* Converts hexadecimal string to BN. *)

PROCEDURE ToHex (A: BN;  VAR (*OUT*) buffer: ARRAY OF CHAR;  bufsize: CARDINAL);

    (* Puts A in buffer in hexadecimal. *)

PROCEDURE FromDecimal (decdata: ARRAY OF CHAR): BN;

    (* Converts decimal string to BN. *)

PROCEDURE ToDecimal (A: BN;  VAR (*OUT*) buffer: ARRAY OF CHAR;
                                            VAR (*INOUT*) pos: CARDINAL);

    (* Puts A at buffer[pos] in decimal, updates pos. *)

END BigNum.

