sint.h

伯克利做的SFTP安全文件传输协议

// sint.h
// scott's integer interface
// the idea here is to present a unified interface to big-integer
//   libraries, behind which any implementation can reside
// This file is in the public domain.

#ifndef __SINT_H
#define __SINT_H

#include "typ.h"        // bool

#include <iostream.h>   // istream, ostream

class Integer {
public:       // implementation .cc file needs access...
  void *impl;            // arbitrary implementation object

public:
  Integer();                     // initialized to 0
  Integer(Integer const &obj);   // initialized to obj
  Integer(long n);               // initialized to n
  Integer(char const *str, int radix);
    // init'd to value represented by null-terminated string of given radix
    // (radix is not given default value because if it had one, then
    // Integer(0) would be ambiguous, since 0 is valid as both char* and long)
  ~Integer();                    // frees associated storage

  // tests
    bool isZero() const;         // true when the value is 0
    bool isPositive() const;     // value > 0
    bool isNegative() const;     // value < 0
    int getSign() const;         // -1, 0, or +1

  // assignment
    Integer& operator= (Integer const &obj);
    Integer& operator= (long n);

  // conversions
    // to/from built-in C types (the 'to' conversions throw an
    // exception if the value doesn't fit (todo: what kind?))
      bool fitsInLong() const;
      long toLong() const;
      void fromLong(long n);

    // to/from external (char*) representations (which include null terminators)
      int toStringBytes(int radix = 10) const;
        // includes '-' (if necessary) and null terminator
        // allowed to overestimate (in particular, might always assume '-')
      void toString(char *str, int length, int radix = 10) const;
        // may throw (what?) if doesn't fit in 'length' bytes
      void fromString(char const *str, int radix = 10);
        // todo: how should this behave on malformed strings?

  // write decimal strings to ostreams (for convenience; sophisticated
  // output, or any input, should use the char* routines)
    void toOstream(ostream &os) const;
    friend ostream &operator<< (ostream &os, Integer const &obj)
      { obj.toOstream(os); return os; }

  // relational tests
    int compare(Integer const &obj) const;
    int compareToLong(long n) const;
      // returns <0, ==0, >0 if this<obj, this==obj, this>obj resp.
    #define RELOP(op)                                 \
      bool operator op (Integer const &obj) const     \
        { return compare(obj) op 0; }                 \
      bool operator op (long n) const                 \
        { return compareToLong(n) op 0; }
    RELOP(<);
    RELOP(<=);
    RELOP(>);
    RELOP(>=);
    RELOP(==);
    RELOP(!=);
    #undef RELOP

  // syntactic sugar for operator & function definitions
  #define ONEOP(name, arg1) \
    Integer name(Integer const &arg1) const /*user ;*/
  #define TWOOP(name, arg1, arg2) \
    Integer name(Integer const &arg1, Integer const &arg2) const /*user ;*/
  #define ONEFN(name, arg1) \
    friend Integer name(Integer const &arg1) /*user ;*/
  #define TWOFN(name, arg1, arg2) \
    friend Integer name(Integer const &arg1, Integer const &arg2) /*user ;*/

  // ordinary arithmetic
    // NOTE: I don't know what the best rounding policy for division is,
    //       or if this interface should try to support several.  So, I
    //       am not (as yet..) specifying the rounding behavior, except
    //       that positive numerator and denominator round towards 0.

    // one-symbol ops
      #define ARITHOP(op) ONEOP(operator op, obj)
      ARITHOP(+);
      ARITHOP(-);
      ARITHOP(*);
      ARITHOP(/);
      ARITHOP(%);    // mod
      #undef ARITHOP

    // two-symbol ops
      #define ARITHEQOP(op) \
        Integer &operator op (Integer const &obj) /*user ;*/
      ARITHEQOP(+=);
      ARITHEQOP(-=);
      ARITHEQOP(*=);
      ARITHEQOP(/=);
      ARITHEQOP(%=);
      #undef ARITHEQOP

    // named ops
      ONEOP(exp, exponent);
        // this^expoenent
        // (I don't overload the ^ operator because its precedence
        // and associativity are wrong)

      friend void divAndRemainder(
        Integer &quotient, Integer &remainder,
        Integer const &numer, Integer const &denom);
          // divide, returning quotient and remainder

      TWOFN(log, base, power);
        // floor(log (base 'base') of 'power')
        // where power >= 1 && base >= 2

      friend long log_long(long base, Integer const &power);
        // log, but with small base and result 

      ONEFN(abs, x);
        // returns |x|

      friend bool probablyPrime(Integer const &value, int iters = 25);
        // if returns true, value is prime with Pr >= 1 - (1/4)^iters
        //            false, value is definitely composite

  // byte- and bit-level operations; these operations (at least for now)
  // always assume the Integer in question is nonnegative
    int numBits() const;
      // minimum # of bits to represent 'this':
      //   0.numBits() == 1
      //   1.numBits() == 1
      //   2.numBits() == 2
      //   255.numBits() == 8
      //   256.numBits() == 9

    unsigned char leastSigByte() const;
      // value of least significant byte; equals 'this' % 256

    // (didn't define mostSigByte because defining it mathematically
    // is somewhat awkard, and it's of questionable value)

    Integer operator >> (unsigned bits) const;
    Integer& operator >>= (unsigned bits);
      // returns 'this' / 2^bits
    Integer operator << (unsigned bits) const;
    Integer& operator <<= (unsigned bits);
      // return 'this' * 2^bits

  // modular arithmetic
    // +, -, *, /
      TWOOP(plusMod, addend, modulus);          // += (mod)
      TWOOP(minusMod, minuend, modulus);        // -= (mod)
      TWOOP(timesMod, multiplicand, modulus);   // *= (mod)
      TWOOP(divMod, denom, modulus);
        // (*this * denom.inverseMod(modulus)) % modulus

    // other named fns
      TWOOP(expMod, exponent, modulus);
        // (this ^ exponent) % modulus
      ONEOP(inverseMod, modulus);
        // if x.inverseMod(y,m), then x.timesMod(y, m) == 1
        // (i.e., if y == x^-1 (mod m), then x*y (mod m) == 1)
        // returns 0 if the inverse does not exist (since 0
        // is never an inverse)

  // common number-theoretic functions
    // greatest common divisor of a and b
    TWOFN(gcd, a, b);

    // interface for passing random bits to Integer
    class RandomSource {
    public:
      virtual void getRandomBytes(unsigned char *dest, int numBytes)=0;
    };
    friend Integer random(RandomSource &src, Integer const &top);
      // return a random number in [0, top), uniformly distributed

  // extended euclidean algorithm
  friend void extendedEuclidean(Integer &d, Integer &x, Integer &y,
                                Integer const &a, Integer const &b);
    // returns g = gcd(a,b), and x,y such that
    // ax + by = d

  // don't pollute namespace
  #undef ONEOP
  #undef TWOOP
  #undef ONEFN
  #undef TWOFN
};


  // want:
  //   tests: zero, sign, etc
  //   conversions to/from:
  //     int, long, etc.
  //     char* (various radices)
  //   read/write:
  //     ostream, istream
  //     FILE* ?
  //   relational tests:
  //     <, <=, >, >=, ==, !=
  //   ordinary arithmetic:
  //     +, -, *, /, % (and +=, etc.)
  //     exponentiation
  //   modular arithmetic:
  //     +, -, *, / (and +=, etc.)
  //     exponentiation
  //     inverses
  //   functions:
  //     gcd
  //     random
  //   algorithms:
  //     extended euclidean algorithm


#endif // __SINT_H