PROCEDURE GetSize(READONLY x : T) : CARDINAL =
  BEGIN
    RETURN NUMBER(x)-FirstPosition(x)
  END GetSize;


PROCEDURE LastPosition(READONLY x: T) : CARDINAL = 
  BEGIN
    RETURN LAST(x)
  END LastPosition;



PROCEDURE Assign(VAR z: T; READONLY z: T; s: SizeT) =
  (* Copies the "s" digits from "z" to "x". *)
  BEGIN
    WITH zp = FirstPosition(z) DO
      SUBARRAY(x^,zp,s):=SUBARRAY(z^,zp,s)
    END;
    SetSign(x,GetSign(z));
  END Assign;

PROCEDURE FillWithZero(z: T; p,s: CARDINAL) =
  (* set to zero "z[fp+p+1]" to "z[fp+p+s]" where "fp=FirstPosition(z)" *)
  VAR i : CARDINAL;
  BEGIN
    WITH
      fp = FirstPosition(z),
      lp = GetSize(z),
      ip = fp + p
    DO
      IF ip+s > lp THEN s:=lp-ip END;
      i:=ip+1;
      WHILE (i<=s) DO 
        z^[i]:=0;
        INC(i)
      END
    END
  END FillWithZero;

PROCEDURE Num_IsZero(num: T): BOOLEAN =
  VAR b : BOOLEAN:=TRUE;
      i : CARDINAL;
  BEGIN
    WITH
      nl= LAST(num^),
      np= FirstPosition(num)
    DO
      i:=nl;
      WHILE (i>=np) AND b DO 
        IF num[i] # 0 THEN b:=FALSE END;
        i:=i-1
      END;
      RETURN b
    END
  END Num_IsZero;

PROCEDURE DigitValueInBase(c: CHAR; base: BaseT:=10): CHAR =
(* Converts the char "c" to the char format used by MPN *)
  VAR rc : CHAR;
  BEGIN
    IF (c>='0') AND (c<='9') THEN 
      rc:=VAL(ORD(c)-ORD('0'),CHAR);
    ELSIF (c>='a') AND (c<='z') THEN 
      rc:=VAL(ORD(c)-ORD('a')+10,CHAR);
    ELSIF (c>='A') AND (c<='Z') THEN 
      rc:=VAL(ORD(c)-ORD('A')+10,CHAR);
    ELSE
      RETURN '\n'
    END;

    IF ORD(rc) < base THEN 
      RETURN rc
    ELSE
      RETURN '\n'
    END
  END DigitValueInBase;

PROCEDURE CountLeadingZerosInDigit(d : DigitT) : Ctypes.unsigned_long_int =
  (* counts the number of zero-bits from the most significant bit (msb) to 
     the the first non-zero bit in "d".  This is the number of steps "d" 
     needs to be shifted left to set the msb *)
  VAR numzeros : Ctypes.unsigned_long_int;
      tp       : DigitT;
  BEGIN
    WITH
      (* Rotate(x,n) returns "i" bit equals "(i-n) MOD Word.Size" *) 
      msb = Word.Rotate(1,Word.Size-1)
    DO
      numzeros:=0;
      tp := d;
      WHILE (Word.And(tp,msb) = 0) AND (numzeros < Word.Size)  DO 
        tp:=Word.LeftShift(tp,1);
        numzeros:=numzeros+1
      END;
    END;
    RETURN numzeros
  END CountLeadingZerosInDigit;
  
PROCEDURE CountTrailingZerosInDigit(d: DigitT) : Ctypes.unsigned_long_int =
  (* counts the number of zero-bits from the least significant bit (lsb) to 
     the the first non-zero bit in "d".  This is the number of steps "d" 
     needs to be shifted right to set the lsb *)
  VAR lsb,tp : DigitT;
      numzeros : Ctypes.unsigned_long_int;
  BEGIN
    (* based on the "count_trailing_zeros" defined on line 1393 of "longlong.h" *)
    lsb := 1;
    numzeros:=0;
    tp := d;
    WHILE (Word.And(tp,lsb) = 0) AND (numzeros < Word.Size)  DO 
      tp:=Word.RightShift(tp,1);
      numzeros:=numzeros+1
    END;

Wr.PutText(Stdio.stdout," =  "&Fmt.Unsigned(numzeros)&"\n");
Wr.Flush(Stdio.stdout);

    RETURN numzeros
  END CountTrailingZerosInDigit;

PROCEDURE CountLeastSignificantLimbZero(z: T) : Ctypes.unsigned_long_int = 
  (* counts the number of the least significant limb of "z" that are zero *)
  VAR i : Ctypes.unsigned_long_int;
  BEGIN
    WITH
      zl= LAST(z^),
      zp= FirstPosition(z)
    DO
      i:=zp;
      WHILE (i <= zl) AND (z^[i] = 0) DO 
        INC(i)
      END;
      IF i > zl THEN 
        RETURN(zl-zp+1)
      ELSE 
        RETURN(i-zp)
      END
    END
  END CountLeastSignificantLimbZero;

  
PROCEDURE NormalizeToGCD(z: T; VAR z_zero_limbs, z_zero_bits: Ctypes.unsigned_long_int) : T =
  (* puts "z" on the format required by "MPNat.GCD" that is an odd number;
     returns "z" in this format and puts in "z_zero_limbs" the number of 
     limbs of "z" that are zero and in "z_zero_bits" the number of zero-bits 
     in the least significant limb different of zero. So, the number returned 
     corresponds to "z" right shifted "z_zero_limbs * SIZEOF(limb) + z_zero_bits" 
     positions *)
  BEGIN
    z_zero_limbs := CountLeastSignificantLimbZero(z);
    z_zero_bits := CountTrailingZeros(z);
    
    WITH 
      zl = GetSize(z),
      zp = FirstPosition(z),
      rl = zl-z_zero_limbs
    DO 
      IF rl > 0 THEN 
        WITH 
          r = Create(rl)
        DO
          Assign(r,z,zp+z_zero_limbs,zl)
        END;
        RETURN r
      ELSE 
        RETURN DecDigit[0]
      END
    END;
  END NormalizeToGCD;

(* ----------- Procedures defined in the interface -------------- *)

PROCEDURE FirstPosition(READONLY x : T) : CARDINAL =
  BEGIN
    RETURN FIRST(x)+1
  END FirstPosition;

  
PROCEDURE IsZero(READONLY x : T) : BOOLEAN =
  BEGIN
    RETURN GetSign(x) = MP_ZERO;
  END IsZero;

PROCEDURE NumDigits(READONLY x : T) : SizeT =
  (* Returns the number of digits in "z", not considering leading 
     zeros. *)
  VAR s : CARDINAL; 
  BEGIN 
    IF IsZero(x) THEN 
      RETURN 1
    ELSE
      WITH xp=FirstPosition(x) DO
        s:=LastPosition(x);
        WHILE s >= xp AND x[s]=0 DO s:=s-1 END;
        RETURN s
      END
    END
  END NumDigits;

PROCEDURE CompAbs(READONLY x,y : T) : Sign =
  BEGIN
    RETURN Comp(Abs(x),Abs(y))
  END CompAbs;