BigIntegerUtils.hh

   1 /*
   2 * Matt McCutchen's Big Integer Library
   3 * http://mysite.verizon.net/mccutchen/bigint/
   4 */
   5
   6 #ifndef BIGINTEGERUTILS
   7 #define BIGINTEGERUTILS
   8
   9 #include "BigInteger.hh"
  10 #include <string>
  11 #include <iostream>
  12
  13 /*
  14 * This file includes:
  15 * (1) `std::string <=> BigUnsigned/BigInteger' conversion routines easier than `BigUnsignedInABase'
  16 * (2) << and >> operators for BigUnsigned/BigInteger, std::istream/std::ostream
  17 */
  18
  19 // Conversion routines.  Base 10 only.
  20 std::string easyBUtoString(const BigUnsigned &x);
  21 std::string easyBItoString(const BigInteger &x);
  22 BigUnsigned easyStringToBU(const std::string &s);
  23 BigInteger easyStringToBI(const std::string &s);
  24
  25 // Creates a BigInteger from data such as `char's; read below for details.
  26 template <class T>
  27 BigInteger easyDataToBI(const T* data, BigInteger::Index length, BigInteger::Sign sign);
  28
  29 // Outputs x to os, obeying the flags `dec', `hex', `bin', and `showbase'.
  30 std::ostream &operator <<(std::ostream &os, const BigUnsigned &x);
  31
  32 // Outputs x to os, obeying the flags `dec', `hex', `bin', and `showbase'.
  33 // My somewhat arbitrary policy: a negative sign comes before a base indicator (like -0xFF).
  34 std::ostream &operator <<(std::ostream &os, const BigInteger &x);
  35
  36 /*
  37 * =================================
  38 * BELOW THIS POINT are template definitions; above are declarations.  See `NumberlikeArray.hh'.
  39 */
  40
  41 /*
  42 * Converts binary data to a BigInteger.
  43 * Pass an array `data', its length, and the desired sign.
  44 *
  45 * Elements of `data' may be of any type `T' that has the following
  46 * two properties (this includes almost all integral types):
  47 *
  48 * (1) `sizeof(T)' correctly gives the amount of binary data in one
  49 * value of `T' and is a factor of `sizeof(Blk)'.
  50 *
  51 * (2) When a value of `T' is casted to a `Blk', the low bytes of
  52 * the result contain the desired binary data.
  53 */
  54 template <class T>
  55 BigInteger easyDataToBI(const T* data, BigInteger::Index length, BigInteger::Sign sign) {
  56         // really ceiling(numBytes / sizeof(BigInteger::Blk))
  57         unsigned int pieceSizeInBits = 8 * sizeof(T);
  58         unsigned int piecesPerBlock = sizeof(BigInteger::Blk) / sizeof(T);
  59         unsigned int numBlocks = (length + piecesPerBlock - 1) / piecesPerBlock;
  60
  61         // Allocate our block array
  62         BigInteger::Blk *blocks = new BigInteger::Blk[numBlocks];
  63
  64         BigInteger::Index blockNum, pieceNum, pieceNumHere;
  65
  66         // Convert
  67         for (blockNum = 0, pieceNum = 0; blockNum < numBlocks; blockNum++) {
  68                 BigInteger::Blk curBlock = 0;
  69                 for (pieceNumHere = 0; pieceNumHere < piecesPerBlock && pieceNum < length;
  70                         pieceNumHere++, pieceNum++)
  71                         curBlock |= (BigInteger::Blk(data[pieceNum]) << (pieceSizeInBits * pieceNumHere));
  72                 blocks[blockNum] = curBlock;
  73         }
  74
  75         // Create the BigInteger.
  76         BigInteger x(blocks, numBlocks, sign);
  77
  78         delete blocks;
  79         return x;
  80 }
  81
  82 #endif