-////////////////////////////////////////////////////////////////////////////////
-
-// Author: Andy Rushton
-// Copyright: (c) Southampton University 1999-2004
-// (c) Andy Rushton 2004-2009
-// License: BSD License, see ../docs/license.html
-
-// The integer is represented as a sequence of bytes. They are stored such that
-// element 0 is the lsB, which makes sense when seen as an integer offset but
-// is counter-intuitive when you think that a string is usually read from left
-// to right, 0 to size-1, in which case the lsB is on the *left*.
-
-// This solution is compatible with 32-bit and 64-bit machines with either
-// little-endian or big-endian representations of integers.
-
-// Problem: I'm using std::string, which is an array of char. However, char is
-// not well-defined - it could be signed or unsigned.
-
-// In fact, there's no requirement for a char to even be one byte - it can be
-// any size of one byte or more. However, it's just impossible to make any
-// progress with that naffness (thanks to the C non-standardisation committee)
-// and the practice is that char on every platform/compiler I've ever come
-// across is that char = byte.
-
-// The algorithms here use unsigned char to represent bit-patterns so I have to
-// be careful to type-cast from char to unsigned char a lot. I use a typedef to
-// make life easier.
-
-////////////////////////////////////////////////////////////////////////////////
-#include "inf.hpp"
-#include <ctype.h>
-////////////////////////////////////////////////////////////////////////////////
-
-namespace stlplus
-{
-
- ////////////////////////////////////////////////////////////////////////////////
- // choose a sensible C type for a byte
-
- typedef unsigned char byte;
-
- ////////////////////////////////////////////////////////////////////////////////
- // local functions
-
- // removes leading bytes that don't contribute to the value to create the minimum string representation
- static void reduce_string(std::string& data)
- {
- while(data.size() > 1 &&
- ((byte(data[data.size()-1]) == byte(0) && byte(data[data.size()-2]) < byte(128)) ||
- (byte(data[data.size()-1]) == byte(255) && byte(data[data.size()-2]) >= byte(128))))
- {
- data.erase(data.end()-1);
- }
- }
-
- // generic implementations of type conversions from integer type to internal representation
- // data: integer value for conversion
- // result: internal representation
-
- template <typename T>
- static void convert_from_signed(const T& data, std::string& result)
- {
- result.erase();
- bool lsb_first = little_endian();
- byte* address = (byte*)&data;
- for (size_t i = 0; i < sizeof(T); i++)
- {
- size_t offset = (lsb_first ? i : (sizeof(T) - i - 1));
- result.append(1,address[offset]);
- }
- reduce_string(result);
- }
-
- template <typename T>
- static void convert_from_unsigned(const T& data, std::string& result)
- {
- result.erase();
- bool lsb_first = little_endian();
- byte* address = (byte*)&data;
- for (size_t i = 0; i < sizeof(T); i++)
- {
- size_t offset = (lsb_first ? i : (sizeof(T) - i - 1));
- result.append(1,address[offset]);
- }
- // inf is signed - so there is a possible extra sign bit to add
- result.append(1,std::string::value_type(0));
- reduce_string(result);
- }
-
- // generic implementations of type conversions from internal representation to an integer type
- // data : string representation of integer
- // result: integer result of conversion
- // return: flag indicating success - false = overflow
-
- template <class T>
- bool convert_to_signed(const std::string& data, T& result)
- {
- bool lsb_first = little_endian();
- byte* address = (byte*)&result;
- for (size_t i = 0; i < sizeof(T); i++)
- {
- size_t offset = lsb_first ? i : (sizeof(T) - i - 1);
- if (i < data.size())
- address[offset] = byte(data[i]);
- else if (data.empty() || (byte(data[data.size()-1]) < byte(128)))
- address[offset] = byte(0);
- else
- address[offset] = byte(255);
- }
- return data.size() <= sizeof(T);
- }
-
- template <class T>
- bool convert_to_unsigned(const std::string& data, T& result)
- {
- bool lsb_first = little_endian();
- byte* address = (byte*)&result;
- for (size_t i = 0; i < sizeof(T); i++)
- {
- size_t offset = lsb_first ? i : (sizeof(T) - i - 1);
- if (i < data.size())
- address[offset] = byte(data[i]);
- else
- address[offset] = byte(0);
- }
- return data.size() <= sizeof(T);
- }
-
- ////////////////////////////////////////////////////////////////////////////////
- // Conversions to string
-
- static char to_char [] = "0123456789abcdefghijklmnopqrstuvwxyz";
- static int from_char [] =
- {
- -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
- -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
- -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
- 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, -1, -1, -1, -1, -1, -1,
- -1, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24,
- 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, -1, -1, -1, -1, -1,
- -1, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24,
- 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, -1, -1, -1, -1, -1,
- -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
- -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
- -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
- -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
- -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
- -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
- -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
- -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1
- };
-
- static void convert_to_string(const stlplus::inf& data, std::string& result, unsigned radix = 10)
- throw(std::invalid_argument)
- {
- // only support the C-style radixes plus 0b for binary
- if (radix != 2 && radix != 8 && radix != 10 && radix != 16)
- throw std::invalid_argument("invalid radix value");
- inf local_i = data;
- // untangle all the options
- bool binary = radix == 2;
- bool octal = radix == 8;
- bool hex = radix == 16;
- // the C representations for binary, octal and hex use 2's-complement representation
- // all other represenations use sign-magnitude
- if (hex || octal || binary)
- {
- // bit-pattern representation
- // this is the binary representation optionally shown in octal or hex
- // first generate the binary by masking the bits
- for (unsigned j = local_i.bits(); j--; )
- result += (local_i.bit(j) ? '1' : '0');
- // the result is now the full width of the type - e.g. int will give a 32-bit result
- // now interpret this as either binary, octal or hex and add the prefix
- if (binary)
- {
- // trim down to the smallest string that preserves the value
- while (true)
- {
- // do not trim to less than 1 bit (sign only)
- if (result.size() <= 1) break;
- // only trim if it doesn't change the sign and therefore the value
- if (result[0] != result[1]) break;
- result.erase(0,1);
- }
- // add the prefix
- result.insert((std::string::size_type)0, "0b");
- }
- else if (octal)
- {
- // the result is currently binary
- // trim down to the smallest string that preserves the value
- while (true)
- {
- // do not trim to less than 2 bits (sign plus 1-bit magnitude)
- if (result.size() <= 2) break;
- // only trim if it doesn't change the sign and therefore the value
- if (result[0] != result[1]) break;
- result.erase(0,1);
- }
- // also ensure that the binary is a multiple of 3 bits to make the conversion to octal easier
- while (result.size() % 3 != 0)
- result.insert((std::string::size_type)0, 1, result[0]);
- // now convert to octal
- std::string octal_result;
- for (unsigned i = 0; i < result.size()/3; i++)
- {
- // yuck - ugly or what?
- if (result[i*3] == '0')
- {
- if (result[i*3+1] == '0')
- {
- if (result[i*3+2] == '0')
- octal_result += '0';
- else
- octal_result += '1';
- }
- else
- {
- if (result[i*3+2] == '0')
- octal_result += '2';
- else
- octal_result += '3';
- }
- }
- else
- {
- if (result[i*3+1] == '0')
- {
- if (result[i*3+2] == '0')
- octal_result += '4';
- else
- octal_result += '5';
- }
- else
- {
- if (result[i*3+2] == '0')
- octal_result += '6';
- else
- octal_result += '7';
- }
- }
- }
- result = octal_result;
- // add the prefix
- result.insert((std::string::size_type)0, "0");
- }
- else
- {
- // similar to octal
- while (true)
- {
- // do not trim to less than 2 bits (sign plus 1-bit magnitude)
- if (result.size() <= 2) break;
- // only trim if it doesn't change the sign and therefore the value
- if (result[0] != result[1]) break;
- result.erase(0,1);
- }
- // pad to a multiple of 4 characters
- while (result.size() % 4 != 0)
- result.insert((std::string::size_type)0, 1, result[0]);
- // now convert to hex
- std::string hex_result;
- for (unsigned i = 0; i < result.size()/4; i++)
- {
- // yuck - ugly or what?
- if (result[i*4] == '0')
- {
- if (result[i*4+1] == '0')
- {
- if (result[i*4+2] == '0')
- {
- if (result[i*4+3] == '0')
- hex_result += '0';
- else
- hex_result += '1';
- }
- else
- {
- if (result[i*4+3] == '0')
- hex_result += '2';
- else
- hex_result += '3';
- }
- }
- else
- {
- if (result[i*4+2] == '0')
- {
- if (result[i*4+3] == '0')
- hex_result += '4';
- else
- hex_result += '5';
- }
- else
- {
- if (result[i*4+3] == '0')
- hex_result += '6';
- else
- hex_result += '7';
- }
- }
- }
- else
- {
- if (result[i*4+1] == '0')
- {
- if (result[i*4+2] == '0')
- {
- if (result[i*4+3] == '0')
- hex_result += '8';
- else
- hex_result += '9';
- }
- else
- {
- if (result[i*4+3] == '0')
- hex_result += 'a';
- else
- hex_result += 'b';
- }
- }
- else
- {
- if (result[i*4+2] == '0')
- {
- if (result[i*4+3] == '0')
- hex_result += 'c';
- else
- hex_result += 'd';
- }
- else
- {
- if (result[i*4+3] == '0')
- hex_result += 'e';
- else
- hex_result += 'f';
- }
- }
- }
- }
- result = hex_result;
- // add the prefix
- result.insert((std::string::size_type)0, "0x");
- }
- }
- else
- {
- // convert to sign-magnitude
- // the representation is:
- // [sign]magnitude
- bool negative = local_i.negative();
- local_i.abs();
- // create a representation of the magnitude by successive division
- inf inf_radix(radix);
- do
- {
- std::pair<inf,inf> divided = local_i.divide(inf_radix);
- unsigned remainder = divided.second.to_unsigned();
- char digit = to_char[remainder];
- result.insert((std::string::size_type)0, 1, digit);
- local_i = divided.first;
- }
- while(!local_i.zero());
- // add the prefixes
- // add a sign only for negative values
- if (negative)
- result.insert((std::string::size_type)0, 1, '-');
- }
- }
-
- ////////////////////////////////////////////////////////////////////////////////
- // Conversions FROM string
-
- void convert_from_string(const std::string& str, inf& result, unsigned radix = 10) throw(std::invalid_argument)
- {
- result = 0;
- // only support the C-style radixes plus 0b for binary
- // a radix of 0 means deduce the radix from the input - assume 10
- if (radix != 0 && radix != 2 && radix != 8 && radix != 10 && radix != 16)
- throw std::invalid_argument("invalid radix value");
- unsigned i = 0;
- // the radix passed as a parameter is just the default - it can be
- // overridden by the C prefix
- // Note: a leading zero is the C-style prefix for octal - I only make this
- // override the default when the default radix is not specified
- // first check for a C-style prefix
- bool c_style = false;
- if (i < str.size() && str[i] == '0')
- {
- // binary or hex
- if (i+1 < str.size() && tolower(str[i+1]) == 'x')
- {
- c_style = true;
- radix = 16;
- i += 2;
- }
- else if (i+1 < str.size() && tolower(str[i+1]) == 'b')
- {
- c_style = true;
- radix = 2;
- i += 2;
- }
- else if (radix == 0)
- {
- c_style = true;
- radix = 8;
- i += 1;
- }
- }
- if (radix == 0)
- radix = 10;
- if (c_style)
- {
- // the C style formats are bit patterns not integer values - these need
- // to be sign-extended to get the right value
- std::string binary;
- if (radix == 2)
- {
- for (unsigned j = i; j < str.size(); j++)
- {
- switch(str[j])
- {
- case '0':
- binary += '0';
- break;
- case '1':
- binary += '1';
- break;
- default:
- throw std::invalid_argument("invalid binary character in string " + str);
- }
- }
- }
- else if (radix == 8)
- {
- for (unsigned j = i; j < str.size(); j++)
- {
- switch(str[j])
- {
- case '0':
- binary += "000";
- break;
- case '1':
- binary += "001";
- break;
- case '2':
- binary += "010";
- break;
- case '3':
- binary += "011";
- break;
- case '4':
- binary += "100";
- break;
- case '5':
- binary += "101";
- break;
- case '6':
- binary += "110";
- break;
- case '7':
- binary += "111";
- break;
- default:
- throw std::invalid_argument("invalid octal character in string " + str);
- }
- }
- }
- else
- {
- for (unsigned j = i; j < str.size(); j++)
- {
- switch(tolower(str[j]))
- {
- case '0':
- binary += "0000";
- break;
- case '1':
- binary += "0001";
- break;
- case '2':
- binary += "0010";
- break;
- case '3':
- binary += "0011";
- break;
- case '4':
- binary += "0100";
- break;
- case '5':
- binary += "0101";
- break;
- case '6':
- binary += "0110";
- break;
- case '7':
- binary += "0111";
- break;
- case '8':
- binary += "1000";
- break;
- case '9':
- binary += "1001";
- break;
- case 'a':
- binary += "1010";
- break;
- case 'b':
- binary += "1011";
- break;
- case 'c':
- binary += "1100";
- break;
- case 'd':
- binary += "1101";
- break;
- case 'e':
- binary += "1110";
- break;
- case 'f':
- binary += "1111";
- break;
- default:
- throw std::invalid_argument("invalid hex character in string " + str);
- }
- }
- }
- // now convert the value
- result.resize(binary.size());
- for (unsigned j = 0; j < binary.size(); j++)
- result.preset(binary.size() - j - 1, binary[j] == '1');
- }
- else
- {
- // sign-magnitude representation
- // now scan for a sign and find whether this is a negative number
- bool negative = false;
- if (i < str.size())
- {
- switch (str[i])
- {
- case '-':
- negative = true;
- i++;
- break;
- case '+':
- i++;
- break;
- }
- }
- for (; i < str.size(); i++)
- {
- result *= inf(radix);
- unsigned char ascii = (unsigned char)str[i];
- int ch = from_char[ascii] ;
- if (ch == -1)
- throw std::invalid_argument("invalid decimal character in string " + str);
- result += inf(ch);
- }
- if (negative)
- result.negate();
- }
- }
-
- ////////////////////////////////////////////////////////////////////////////////
- // constructors - mostly implemented in terms of the assignment operators
-
- inf::inf(void)
- {
- // void constructor initialises to zero - represented as a single-byte value containing zero
- m_data.append(1,std::string::value_type(0));
- }
-
- inf::inf(short r)
- {
- operator=(r);
- }
-
- inf::inf(unsigned short r)
- {
- operator=(r);
- }
-
- inf::inf(int r)
- {
- operator=(r);
- }
-
- inf::inf(unsigned r)
- {
- operator=(r);
- }
-
- inf::inf(long r)
- {
- operator=(r);
- }
-
- inf::inf(unsigned long r)
- {
- operator=(r);
- }
-
- inf::inf (const std::string& r) throw(std::invalid_argument)
- {
- operator=(r);
- }
-
- inf::inf(const inf& r)
- {
-#ifdef __BORLANDC__
- // work round bug in Borland compiler - copy constructor fails if string
- // contains null characters, so do my own copy
- for (unsigned i = 0; i < r.m_data.size(); i++)
- m_data += r.m_data[i];
-#else
- m_data = r.m_data;
-#endif
- }
-
- ////////////////////////////////////////////////////////////////////////////////
-
- inf::~inf(void)
- {
- }
-
- ////////////////////////////////////////////////////////////////////////////////
- // assignments convert from iteger types to internal representation
-
- inf& inf::operator = (short r)
- {
- convert_from_signed(r, m_data);
- return *this;
- }
-
- inf& inf::operator = (unsigned short r)
- {
- convert_from_unsigned(r, m_data);
- return *this;
- }
-
- inf& inf::operator = (int r)
- {
- convert_from_signed(r, m_data);
- return *this;
- }
-
- inf& inf::operator = (unsigned r)
- {
- convert_from_unsigned(r, m_data);
- return *this;
- }
-
- inf& inf::operator = (long r)
- {
- convert_from_signed(r, m_data);
- return *this;
- }
-
- inf& inf::operator = (unsigned long r)
- {
- convert_from_unsigned(r, m_data);
- return *this;
- }
-
- inf& inf::operator = (const std::string& r) throw(std::invalid_argument)
- {
- convert_from_string(r, *this);
- return *this;
- }
-
- inf& inf::operator = (const inf& r)
- {
- m_data = r.m_data;
- return *this;
- }
-
- ////////////////////////////////////////////////////////////////////////////////
-
- short inf::to_short(bool truncate) const throw(std::overflow_error)
- {
- short result = 0;
- if (!convert_to_signed(m_data, result))
- if (!truncate)
- throw std::overflow_error("stlplus::inf::to_short");
- return result;
- }
-
- unsigned short inf::to_unsigned_short(bool truncate) const throw(std::overflow_error)
- {
- unsigned short result = 0;
- if (!convert_to_unsigned(m_data, result))
- if (!truncate)
- throw std::overflow_error("stlplus::inf::to_unsigned_short");
- return result;
- }
-
- int inf::to_int(bool truncate) const throw(std::overflow_error)
- {
- int result = 0;
- if (!convert_to_signed(m_data, result))
- if (!truncate)
- throw std::overflow_error("stlplus::inf::to_int");
- return result;
- }
-
- unsigned inf::to_unsigned(bool truncate) const throw(std::overflow_error)
- {
- unsigned result = 0;
- if (!convert_to_unsigned(m_data, result))
- if (!truncate)
- throw std::overflow_error("stlplus::inf::to_unsigned");
- return result;
- }
-
- long inf::to_long(bool truncate) const throw(std::overflow_error)
- {
- long result = 0;
- if (!convert_to_signed(m_data, result))
- if (!truncate)
- throw std::overflow_error("stlplus::inf::to_long");
- return result;
- }
-
- unsigned long inf::to_unsigned_long(bool truncate) const throw(std::overflow_error)
- {
- unsigned long result = 0;
- if (!convert_to_unsigned(m_data, result))
- if (!truncate)
- throw std::overflow_error("stlplus::inf::to_unsigned_long");
- return result;
- }
-
- ////////////////////////////////////////////////////////////////////////////////
- // resize the inf regardless of the data
-
- void inf::resize(unsigned bits)
- {
- if (bits == 0) bits = 1;
- unsigned bytes = (bits+7)/8;
- byte extend = negative() ? byte(255) : byte (0);
- while(bytes > m_data.size())
- m_data.append(1,extend);
- }
-
- // reduce the bit count to the minimum needed to preserve the value
-
- void inf::reduce(void)
- {
- reduce_string(m_data);
- }
-
- ////////////////////////////////////////////////////////////////////////////////
- // the number of significant bits in the number
-
- unsigned inf::bits (void) const
- {
- // The number of significant bits in the integer value - this is the number
- // of indexable bits less any redundant sign bits at the msb
- // This does not assume that the inf has been reduced to its minimum form
- unsigned result = indexable_bits();
- bool sign = bit(result-1);
- while (result > 1 && (sign == bit(result-2)))
- result--;
- return result;
- }
-
- unsigned inf::size(void) const
- {
- return bits();
- }
-
- unsigned inf::indexable_bits (void) const
- {
- return 8 * unsigned(m_data.size());
- }
-
- ////////////////////////////////////////////////////////////////////////////////
- // bitwise operations
-
- bool inf::bit (unsigned index) const throw(std::out_of_range)
- {
- if (index >= indexable_bits())
- throw std::out_of_range(std::string("stlplus::inf::bit"));
- // first split the offset into byte offset and bit offset
- unsigned byte_offset = index/8;
- unsigned bit_offset = index%8;
- return (byte(m_data[byte_offset]) & (byte(1) << bit_offset)) != 0;
- }
-
- bool inf::operator [] (unsigned index) const throw(std::out_of_range)
- {
- return bit(index);
- }
-
- void inf::set (unsigned index) throw(std::out_of_range)
- {
- if (index >= indexable_bits())
- throw std::out_of_range(std::string("stlplus::inf::set"));
- // first split the offset into byte offset and bit offset
- unsigned byte_offset = index/8;
- unsigned bit_offset = index%8;
- m_data[byte_offset] |= (byte(1) << bit_offset);
- }
-
- void inf::clear (unsigned index) throw(std::out_of_range)
- {
- if (index >= indexable_bits())
- throw std::out_of_range(std::string("stlplus::inf::clear"));
- // first split the offset into byte offset and bit offset
- unsigned byte_offset = index/8;
- unsigned bit_offset = index%8;
- m_data[byte_offset] &= (~(byte(1) << bit_offset));
- }
-
- void inf::preset (unsigned index, bool value) throw(std::out_of_range)
- {
- if (value)
- set(index);
- else
- clear(index);
- }
-
- inf inf::slice(unsigned low, unsigned high) const throw(std::out_of_range)
- {
- if (low >= indexable_bits())
- throw std::out_of_range(std::string("stlplus::inf::slice: low index"));
- if (high >= indexable_bits())
- throw std::out_of_range(std::string("stlplus::inf::slice: high index"));
- inf result;
- if (high >= low)
- {
- // create a result the right size and filled with sign bits
- std::string::size_type result_size = (high-low+1+7)/8;
- result.m_data.erase();
- byte extend = bit(high) ? byte(255) : byte (0);
- while (result.m_data.size() < result_size)
- result.m_data.append(1,extend);
- // now set the relevant bits
- for (unsigned i = low; i <= high; i++)
- result.preset(i-low, bit(i));
- }
- return result;
- }
-
- ////////////////////////////////////////////////////////////////////////////////
- // testing operations
-
- bool inf::negative (void) const
- {
- return bit(indexable_bits()-1);
- }
-
- bool inf::natural (void) const
- {
- return !negative();
- }
-
- bool inf::positive (void) const
- {
- return natural() && !zero();
- }
-
- bool inf::zero (void) const
- {
- for (std::string::size_type i = 0; i < m_data.size(); i++)
- if (m_data[i] != 0)
- return false;
- return true;
- }
-
- bool inf::non_zero (void) const
- {
- return !zero();
- }
-
- bool inf::operator ! (void) const
- {
- return zero();
- }
-
- ////////////////////////////////////////////////////////////////////////////////
- // comparison operators
-
- bool inf::operator == (const inf& r) const
- {
- // Two infs are equal if they are numerically equal, even if they are
- // different sizes (i.e. they could be non-reduced values).
- // This makes life a little more complicated than if I could assume that values were reduced.
- byte l_extend = negative() ? byte(255) : byte (0);
- byte r_extend = r.negative() ? byte(255) : byte (0);
- std::string::size_type bytes = maximum(m_data.size(),r.m_data.size());
- for (std::string::size_type i = bytes; i--; )
- {
- byte l_byte = (i < m_data.size() ? byte(m_data[i]) : l_extend);
- byte r_byte = (i < r.m_data.size() ? byte(r.m_data[i]) : r_extend);
- if (l_byte != r_byte)
- return false;
- }
- return true;
- }
-
- bool inf::operator != (const inf& r) const
- {
- return !operator==(r);
- }
-
- bool inf::operator < (const inf& r) const
- {
- // This could be implemented in terms of subtraction. However, it can be
- // simplified since there is no need to calculate the accurate difference,
- // just the direction of the difference. I compare from msB down and as
- // soon as a byte difference is found, that defines the ordering. The
- // problem is that in 2's-complement, all negative values are greater than
- // all natural values if you just do a straight unsigned comparison. I
- // handle this by doing a preliminary test for different signs.
-
- // For example, a 3-bit signed type has the coding:
- // 000 = 0
- // ...
- // 011 = 3
- // 100 = -4
- // ...
- // 111 = -1
-
- // So, for natural values, the ordering of the integer values is the
- // ordering of the bit patterns. Similarly, for negative values, the
- // ordering of the integer values is the ordering of the bit patterns
- // However, the bit patterns for the negative values are *greater than*
- // the natural values. This is a side-effect of the naffness of
- // 2's-complement representation
-
- // first handle the case of comparing two values with different signs
- bool l_sign = negative();
- bool r_sign = r.negative();
- if (l_sign != r_sign)
- {
- // one argument must be negative and the other natural
- // the left is less if it is the negative one
- return l_sign;
- }
- // the arguments are the same sign
- // so the ordering is a simple unsigned byte-by-byte comparison
- // However, this is complicated by the possibility that the values could be different lengths
- byte l_extend = l_sign ? byte(255) : byte (0);
- byte r_extend = r_sign ? byte(255) : byte (0);
- std::string::size_type bytes = maximum(m_data.size(),r.m_data.size());
- for (std::string::size_type i = bytes; i--; )
- {
- byte l_byte = (i < m_data.size() ? byte(m_data[i]) : l_extend);
- byte r_byte = (i < r.m_data.size() ? byte(r.m_data[i]) : r_extend);
- if (l_byte != r_byte)
- return l_byte < r_byte;
- }
- // if I get here, the two are equal, so that is not less-than
- return false;
- }
-
- bool inf::operator <= (const inf& r) const
- {
- return !(r < *this);
- }
-
- bool inf::operator > (const inf& r) const
- {
- return r < *this;
- }
-
- bool inf::operator >= (const inf& r) const
- {
- return !(*this < r);
- }
-
- ////////////////////////////////////////////////////////////////////////////////
- // logical operators
-
- inf& inf::invert (void)
- {
- for (std::string::size_type i = 0; i < m_data.size(); i++)
- m_data[i] = ~m_data[i];
- return *this;
- }
-
- inf inf::operator ~ (void) const
- {
- inf result(*this);
- result.invert();
- return result;
- }
-
- inf& inf::operator &= (const inf& r)
- {
- // bitwise AND is extended to the length of the largest argument
- byte l_extend = negative() ? byte(255) : byte (0);
- byte r_extend = r.negative() ? byte(255) : byte (0);
- std::string::size_type bytes = maximum(m_data.size(),r.m_data.size());
- for (std::string::size_type i = 0; i < bytes; i++)
- {
- byte l_byte = (i < m_data.size() ? byte(m_data[i]) : l_extend);
- byte r_byte = (i < r.m_data.size() ? byte(r.m_data[i]) : r_extend);
- byte result = l_byte & r_byte;
- if (i < m_data.size())
- m_data[i] = result;
- else
- m_data.append(1,result);
- }
- // now reduce the result
- reduce();
- return *this;
- }
-
- inf inf::operator & (const inf& r) const
- {
- inf result(*this);
- result &= r;
- return result;
- }
-
- inf& inf::operator |= (const inf& r)
- {
- // bitwise OR is extended to the length of the largest argument
- byte l_extend = negative() ? byte(255) : byte (0);
- byte r_extend = r.negative() ? byte(255) : byte (0);
- std::string::size_type bytes = maximum(m_data.size(),r.m_data.size());
- for (std::string::size_type i = 0; i < bytes; i++)
- {
- byte l_byte = (i < m_data.size() ? byte(m_data[i]) : l_extend);
- byte r_byte = (i < r.m_data.size() ? byte(r.m_data[i]) : r_extend);
- byte result = l_byte | r_byte;
- if (i < m_data.size())
- m_data[i] = result;
- else
- m_data.append(1,result);
- }
- // now reduce the result
- reduce();
- return *this;
- }
-
- inf inf::operator | (const inf& r) const
- {
- inf result(*this);
- result |= r;
- return result;
- }
-
- inf& inf::operator ^= (const inf& r)
- {
- // bitwise XOR is extended to the length of the largest argument
- byte l_extend = negative() ? byte(255) : byte (0);
- byte r_extend = r.negative() ? byte(255) : byte (0);
- std::string::size_type bytes = maximum(m_data.size(),r.m_data.size());
- for (std::string::size_type i = 0; i < bytes; i++)
- {
- byte l_byte = (i < m_data.size() ? byte(m_data[i]) : l_extend);
- byte r_byte = (i < r.m_data.size() ? byte(r.m_data[i]) : r_extend);
- byte result = l_byte ^ r_byte;
- if (i < m_data.size())
- m_data[i] = result;
- else
- m_data.append(1,result);
- }
- // now reduce the result
- reduce();
- return *this;
- }
-
- inf inf::operator ^ (const inf& r) const
- {
- inf result(*this);
- result ^= r;
- return result;
- }
-
- ////////////////////////////////////////////////////////////////////////////////
- // shift operators all preserve the value by increasing the word size
-
- inf& inf::operator <<= (unsigned shift)
- {
- // left shift is a shift towards the msb, with 0s being shifted in at the lsb
- // split this into a byte shift followed by a bit shift
-
- // first expand the value to be big enough for the result
- std::string::size_type new_size = (indexable_bits() + shift + 7) / 8;
- byte extend = negative() ? byte(255) : byte (0);
- while (m_data.size() < new_size)
- m_data.append(1,extend);
- // now do the byte shift
- unsigned byte_shift = shift/8;
- if (byte_shift > 0)
- {
- for (std::string::size_type b = new_size; b--; )
- m_data[b] = (b >= byte_shift) ? m_data[b-byte_shift] : byte(0);
- }
- // and finally the bit shift
- unsigned bit_shift = shift%8;
- if (bit_shift > 0)
- {
- for (std::string::size_type b = new_size; b--; )
- {
- byte current = byte(m_data[b]);
- byte previous = b > 0 ? m_data[b-1] : byte(0);
- m_data[b] = (current << bit_shift) | (previous >> (8 - bit_shift));
- }
- }
- // now reduce the result
- reduce();
- return *this;
- }
-
- inf inf::operator << (unsigned shift) const
- {
- inf result(*this);
- result <<= shift;
- return result;
- }
-
- inf& inf::operator >>= (unsigned shift)
- {
- // right shift is a shift towards the lsb, with sign bits being shifted in at the msb
- // split this into a byte shift followed by a bit shift
-
- // a byte of sign bits
- byte extend = negative() ? byte(255) : byte (0);
- // do the byte shift
- unsigned byte_shift = shift/8;
- if (byte_shift > 0)
- {
- for (std::string::size_type b = 0; b < m_data.size(); b++)
- m_data[b] = (b + byte_shift < m_data.size()) ? m_data[b+byte_shift] : extend;
- }
- // and finally the bit shift
- unsigned bit_shift = shift%8;
- if (bit_shift > 0)
- {
- for (std::string::size_type b = 0; b < m_data.size(); b++)
- {
- byte current = byte(m_data[b]);
- byte next = ((b+1) < m_data.size()) ? m_data[b+1] : extend;
- byte shifted = (current >> bit_shift) | (next << (8 - bit_shift));
- m_data[b] = shifted;
- }
- }
- // now reduce the result
- reduce();
- return *this;
- }
-
- inf inf::operator >> (unsigned shift) const
- {
- inf result(*this);
- result >>= shift;
- return result;
- }
-
- ////////////////////////////////////////////////////////////////////////////////
- // negation operators
-
- inf& inf::negate (void)
- {
- // do 2's-complement negation
- // equivalent to inversion plus one
- invert();
- operator += (inf(1));
- return *this;
- }
-
- inf inf::operator - (void) const
- {
- inf result(*this);
- result.negate();
- return result;
- }
-
- inf& inf::abs(void)
- {
- if (negative()) negate();
- return *this;
- }
-
- inf abs(const inf& i)
- {
- inf result = i;
- result.abs();
- return result;
- }
-
- ////////////////////////////////////////////////////////////////////////////////
- // addition operators
-
- inf& inf::operator += (const inf& r)
- {
- // do 2's-complement addition
- // Note that the addition can give a result that is larger than either argument
- byte carry = 0;
- std::string::size_type max_size = maximum(m_data.size(),r.m_data.size());
- byte l_extend = negative() ? byte(255) : byte (0);
- byte r_extend = r.negative() ? byte(255) : byte (0);
- for (std::string::size_type i = 0; i < max_size; i++)
- {
- byte l_byte = (i < m_data.size() ? byte(m_data[i]) : l_extend);
- byte r_byte = (i < r.m_data.size() ? byte(r.m_data[i]) : r_extend);
- // calculate the addition in a type that is bigger than a byte in order to catch the carry-out
- unsigned short result = ((unsigned short)(l_byte)) + ((unsigned short)(r_byte)) + carry;
- // now truncate the result to get the lsB
- if (i < m_data.size())
- m_data[i] = byte(result);
- else
- m_data.append(1,byte(result));
- // and capture the carry out by grabbing the second byte of the result
- carry = byte(result >> 8);
- }
- // if the result overflowed or underflowed, add an extra byte to catch it
- unsigned short result = ((unsigned short)(l_extend)) + ((unsigned short)(r_extend)) + carry;
- if (byte(result) != (negative() ? byte(255) : byte(0)))
- m_data.append(1,byte(result));
- // now reduce the result
- reduce();
- return *this;
- }
-
- inf inf::operator + (const inf& r) const
- {
- inf result(*this);
- result += r;
- return result;
- }
-
- ////////////////////////////////////////////////////////////////////////////////
- // subtraction operators
-
- inf& inf::operator -= (const inf& r)
- {
- // subtraction is defined in terms of negation and addition
- inf negated = -r;
- operator += (negated);
- return *this;
- }
-
- inf inf::operator - (const inf& r) const
- {
- inf result(*this);
- result -= r;
- return result;
- }
-
- ////////////////////////////////////////////////////////////////////////////////
- // multiplication operators
-
- inf& inf::operator *= (const inf& r)
- {
- // 2's complement multiplication
- // one day I'll do a more efficient version than this based on the underlying representation
- inf left(*this);
- inf right = r;
- // make the right value natural but preserve its sign for later
- bool right_negative = right.negative();
- right.abs();
- // implemented as a series of conditional additions
- operator = (0);
- // left.resize(right.bits() + left.bits() - 1);
- left <<= right.bits()-1;
- for (unsigned i = right.bits(); i--; )
- {
- if (right[i])
- operator += (left);
- left >>= 1;
- }
- if (right_negative)
- negate();
- // now reduce the result
- reduce();
- return *this;
- }
-
- inf inf::operator * (const inf& r) const
- {
- inf result(*this);
- result *= r;
- return result;
- }
-
- ////////////////////////////////////////////////////////////////////////////////
- // division and remainder operators
-
- std::pair<inf,inf> inf::divide(const inf& right) const throw(divide_by_zero)
- {
- if (right.zero())
- throw divide_by_zero("stlplus::inf::divide");
- inf numerator(*this);
- inf denominator = right;
- // make the numerator natural but preserve the sign for later
- bool numerator_negative = numerator.negative();
- numerator.abs();
- // same with the denominator
- bool denominator_negative = denominator.negative();
- denominator.abs();
- // the quotient and remainder will form the result
- // start with the quotiont zero and the remainder equal to the whole of the
- // numerator, then do trial subtraction from this
- inf quotient;
- inf remainder = numerator;
- // there's nothing more to do if the numerator is smaller than the denominator
- // but otherwise do the division
- if (numerator.bits() >= denominator.bits())
- {
- // make the quotient big enough to take the result
- quotient.resize(numerator.bits());
- // start with the numerator shifted to the far left
- unsigned shift = numerator.bits() - denominator.bits();
- denominator <<= shift;
- // do the division by repeated subtraction,
- for (unsigned i = shift+1; i--; )
- {
- if (remainder >= denominator)
- {
- remainder -= denominator;
- quotient.set(i);
- }
- denominator >>= 1;
- }
- }
- // now adjust the signs
- // x/(-y) == (-x)/y == -(x/y)
- if (numerator_negative != denominator_negative)
- quotient.negate();
- quotient.reduce();
- // x%(-y) == x%y and (-x)%y == -(x%y)
- if (numerator_negative)
- remainder.negate();
- remainder.reduce();
- return std::pair<inf,inf>(quotient,remainder);
- }
-
- inf& inf::operator /= (const inf& r) throw(divide_by_zero)
- {
- std::pair<inf,inf> result = divide(r);
- operator=(result.first);
- return *this;
- }
-
- inf inf::operator / (const inf& r) const throw(divide_by_zero)
- {
- std::pair<inf,inf> result = divide(r);
- return result.first;
- }
-
- inf& inf::operator %= (const inf& r) throw(divide_by_zero)
- {
- std::pair<inf,inf> result = divide(r);
- operator=(result.second);
- return *this;
- }
-
- inf inf::operator % (const inf& r) const throw(divide_by_zero)
- {
- std::pair<inf,inf> result = divide(r);
- return result.second;
- }
-
- ////////////////////////////////////////////////////////////////////////////////
- // prefix (void) and postfix (int) operators
-
- inf& inf::operator ++ (void)
- {
- operator += (inf(1));
- return *this;
- }
-
- inf inf::operator ++ (int)
- {
- inf old(*this);
- operator += (inf(1));
- return old;
- }
-
- inf& inf::operator -- (void)
- {
- operator -= (inf(1));
- return *this;
- }
-
- inf inf::operator -- (int)
- {
- inf old(*this);
- operator -= (inf(1));
- return old;
- }
-
- ////////////////////////////////////////////////////////////////////////////////
- // string representation and I/O routines
-
- std::string inf::to_string(unsigned radix) const
- throw(std::invalid_argument)
- {
- std::string result;
- convert_to_string(*this, result, radix);
- return result;
- }
-
- inf& inf::from_string(const std::string& value, unsigned radix)
- throw(std::invalid_argument)
- {
- convert_from_string(value, *this, radix);
- return *this;
- }
-
- std::ostream& operator << (std::ostream& str, const inf& i)
- {
- try
- {
- // get radix
- unsigned radix = 10;
- if (str.flags() & std::ios_base::oct)
- radix = 8;
- if (str.flags() & std::ios_base::hex)
- radix = 16;
- // the field width is handled by iostream, so I don't need to handle it as well
- // generate the string representation then print it
- str << i.to_string(radix);
- }
- catch(const std::invalid_argument)
- {
- str.setstate(std::ios_base::badbit);
- }
- return str;
- }
-
- std::istream& operator >> (std::istream& str, inf& i)
- {
- try
- {
- // get radix
- unsigned radix = 10;
- if (str.flags() & std::ios_base::oct)
- radix = 8;
- if (str.flags() & std::ios_base::hex)
- radix = 16;
- // now get the string image of the value
- std::string image;
- str >> image;
- // and convert to inf
- i.from_string(image, radix);
- }
- catch(const std::invalid_argument)
- {
- str.setstate(std::ios_base::badbit);
- }
- return str;
- }
-
- ////////////////////////////////////////////////////////////////////////////////
- // diagnostic dump
- // just convert to hex
-
- std::string inf::image_debug(void) const
- {
- // create this dump in the human-readable form, i.e. msB to the left
- std::string result = "0x";
- for (std::string::size_type i = m_data.size(); i--; )
- {
- byte current = m_data[i];
- byte msB = (current & byte(0xf0)) >> 4;
- result += to_char[msB];
- byte lsB = (current & byte(0x0f));
- result += to_char[lsB];
- }
- return result;
- }
-
- const std::string& inf::get_bytes(void) const
- {
- return m_data;
- }
-
- void inf::set_bytes(const std::string& data)
- {
- m_data = data;
- }
-
-} // end namespace stlplus
+////////////////////////////////////////////////////////////////////////////////\r
+\r
+// Author: Andy Rushton\r
+// Copyright: (c) Southampton University 1999-2004\r
+// (c) Andy Rushton 2004 onwards\r
+// License: BSD License, see ../docs/license.html\r
+\r
+// The integer is represented as a sequence of bytes. They are stored such that\r
+// element 0 is the lsB, which makes sense when seen as an integer offset but\r
+// is counter-intuitive when you think that a string is usually read from left\r
+// to right, 0 to size-1, in which case the lsB is on the *left*.\r
+\r
+// This solution is compatible with 32-bit and 64-bit machines with either\r
+// little-endian or big-endian representations of integers.\r
+\r
+// Problem: I'm using std::string, which is an array of char. However, char is\r
+// not well-defined - it could be signed or unsigned.\r
+\r
+// In fact, there's no requirement for a char to even be one byte - it can be\r
+// any size of one byte or more. However, it's just impossible to make any\r
+// progress with that naffness (thanks to the C non-standardisation committee)\r
+// and the practice is that char on every platform/compiler I've ever come\r
+// across is that char = byte.\r
+\r
+// The algorithms here use unsigned char to represent bit-patterns so I have to\r
+// be careful to type-cast from char to unsigned char a lot. I use a typedef to\r
+// make life easier.\r
+\r
+////////////////////////////////////////////////////////////////////////////////\r
+#include "inf.hpp"\r
+#include <ctype.h>\r
+////////////////////////////////////////////////////////////////////////////////\r
+\r
+namespace stlplus\r
+{\r
+\r
+ ////////////////////////////////////////////////////////////////////////////////\r
+ // choose a sensible C type for a byte\r
+\r
+ typedef unsigned char byte;\r
+\r
+ ////////////////////////////////////////////////////////////////////////////////\r
+ // local functions\r
+\r
+ // removes leading bytes that don't contribute to the value to create the minimum string representation\r
+ static void reduce_string(std::string& data)\r
+ {\r
+ while(data.size() > 1 && \r
+ ((byte(data[data.size()-1]) == byte(0) && byte(data[data.size()-2]) < byte(128)) ||\r
+ (byte(data[data.size()-1]) == byte(255) && byte(data[data.size()-2]) >= byte(128))))\r
+ {\r
+ data.erase(data.end()-1);\r
+ }\r
+ }\r
+\r
+ // generic implementations of type conversions from integer type to internal representation\r
+ // data: integer value for conversion\r
+ // result: internal representation\r
+\r
+ template <typename T>\r
+ static void convert_from_signed(const T& data, std::string& result)\r
+ {\r
+ result.erase();\r
+ bool lsb_first = little_endian();\r
+ byte* address = (byte*)&data;\r
+ for (size_t i = 0; i < sizeof(T); i++)\r
+ {\r
+ size_t offset = (lsb_first ? i : (sizeof(T) - i - 1));\r
+ result.append(1,address[offset]);\r
+ }\r
+ reduce_string(result);\r
+ }\r
+\r
+ template <typename T>\r
+ static void convert_from_unsigned(const T& data, std::string& result)\r
+ {\r
+ result.erase();\r
+ bool lsb_first = little_endian();\r
+ byte* address = (byte*)&data;\r
+ for (size_t i = 0; i < sizeof(T); i++)\r
+ {\r
+ size_t offset = (lsb_first ? i : (sizeof(T) - i - 1));\r
+ result.append(1,address[offset]);\r
+ }\r
+ // inf is signed - so there is a possible extra sign bit to add\r
+ result.append(1,std::string::value_type(0));\r
+ reduce_string(result);\r
+ }\r
+\r
+ // generic implementations of type conversions from internal representation to an integer type\r
+ // data : string representation of integer\r
+ // result: integer result of conversion\r
+ // return: flag indicating success - false = overflow\r
+\r
+ template <class T>\r
+ bool convert_to_signed(const std::string& data, T& result)\r
+ {\r
+ bool lsb_first = little_endian();\r
+ byte* address = (byte*)&result;\r
+ for (size_t i = 0; i < sizeof(T); i++)\r
+ {\r
+ size_t offset = lsb_first ? i : (sizeof(T) - i - 1);\r
+ if (i < data.size())\r
+ address[offset] = byte(data[i]);\r
+ else if (data.empty() || (byte(data[data.size()-1]) < byte(128)))\r
+ address[offset] = byte(0);\r
+ else\r
+ address[offset] = byte(255);\r
+ }\r
+ return data.size() <= sizeof(T);\r
+ }\r
+\r
+ template <class T>\r
+ bool convert_to_unsigned(const std::string& data, T& result)\r
+ {\r
+ bool lsb_first = little_endian();\r
+ byte* address = (byte*)&result;\r
+ for (size_t i = 0; i < sizeof(T); i++)\r
+ {\r
+ size_t offset = lsb_first ? i : (sizeof(T) - i - 1);\r
+ if (i < data.size())\r
+ address[offset] = byte(data[i]);\r
+ else\r
+ address[offset] = byte(0);\r
+ }\r
+ return data.size() <= sizeof(T);\r
+ }\r
+\r
+ ////////////////////////////////////////////////////////////////////////////////\r
+ // Conversions to string\r
+\r
+ static char to_char [] = "0123456789abcdefghijklmnopqrstuvwxyz";\r
+ static int from_char [] = \r
+ {\r
+ -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,\r
+ -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,\r
+ -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,\r
+ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, -1, -1, -1, -1, -1, -1,\r
+ -1, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24,\r
+ 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, -1, -1, -1, -1, -1,\r
+ -1, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24,\r
+ 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, -1, -1, -1, -1, -1,\r
+ -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,\r
+ -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,\r
+ -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,\r
+ -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,\r
+ -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,\r
+ -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,\r
+ -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,\r
+ -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1\r
+ };\r
+\r
+ static void convert_to_string(const stlplus::inf& data, std::string& result, unsigned radix = 10)\r
+ throw(std::invalid_argument)\r
+ {\r
+ // only support the C-style radixes plus 0b for binary\r
+ if (radix != 2 && radix != 8 && radix != 10 && radix != 16)\r
+ throw std::invalid_argument("invalid radix value");\r
+ inf local_i = data;\r
+ // untangle all the options\r
+ bool binary = radix == 2;\r
+ bool octal = radix == 8;\r
+ bool hex = radix == 16;\r
+ // the C representations for binary, octal and hex use 2's-complement representation\r
+ // all other represenations use sign-magnitude\r
+ if (hex || octal || binary)\r
+ {\r
+ // bit-pattern representation\r
+ // this is the binary representation optionally shown in octal or hex\r
+ // first generate the binary by masking the bits\r
+ for (unsigned j = local_i.bits(); j--; )\r
+ result += (local_i.bit(j) ? '1' : '0');\r
+ // the result is now the full width of the type - e.g. int will give a 32-bit result\r
+ // now interpret this as either binary, octal or hex and add the prefix\r
+ if (binary)\r
+ {\r
+ // trim down to the smallest string that preserves the value\r
+ while (true)\r
+ {\r
+ // do not trim to less than 1 bit (sign only)\r
+ if (result.size() <= 1) break;\r
+ // only trim if it doesn't change the sign and therefore the value\r
+ if (result[0] != result[1]) break;\r
+ result.erase(0,1);\r
+ }\r
+ // add the prefix\r
+ result.insert((std::string::size_type)0, "0b");\r
+ }\r
+ else if (octal)\r
+ {\r
+ // the result is currently binary\r
+ // trim down to the smallest string that preserves the value\r
+ while (true)\r
+ {\r
+ // do not trim to less than 2 bits (sign plus 1-bit magnitude)\r
+ if (result.size() <= 2) break;\r
+ // only trim if it doesn't change the sign and therefore the value\r
+ if (result[0] != result[1]) break;\r
+ result.erase(0,1);\r
+ }\r
+ // also ensure that the binary is a multiple of 3 bits to make the conversion to octal easier\r
+ while (result.size() % 3 != 0)\r
+ result.insert((std::string::size_type)0, 1, result[0]);\r
+ // now convert to octal\r
+ std::string octal_result;\r
+ for (unsigned i = 0; i < result.size()/3; i++)\r
+ {\r
+ // yuck - ugly or what?\r
+ if (result[i*3] == '0')\r
+ {\r
+ if (result[i*3+1] == '0')\r
+ {\r
+ if (result[i*3+2] == '0')\r
+ octal_result += '0';\r
+ else\r
+ octal_result += '1';\r
+ }\r
+ else\r
+ {\r
+ if (result[i*3+2] == '0')\r
+ octal_result += '2';\r
+ else\r
+ octal_result += '3';\r
+ }\r
+ }\r
+ else\r
+ {\r
+ if (result[i*3+1] == '0')\r
+ {\r
+ if (result[i*3+2] == '0')\r
+ octal_result += '4';\r
+ else\r
+ octal_result += '5';\r
+ }\r
+ else\r
+ {\r
+ if (result[i*3+2] == '0')\r
+ octal_result += '6';\r
+ else\r
+ octal_result += '7';\r
+ }\r
+ }\r
+ }\r
+ result = octal_result;\r
+ // add the prefix\r
+ result.insert((std::string::size_type)0, "0");\r
+ }\r
+ else\r
+ {\r
+ // similar to octal\r
+ while (true)\r
+ {\r
+ // do not trim to less than 2 bits (sign plus 1-bit magnitude)\r
+ if (result.size() <= 2) break;\r
+ // only trim if it doesn't change the sign and therefore the value\r
+ if (result[0] != result[1]) break;\r
+ result.erase(0,1);\r
+ }\r
+ // pad to a multiple of 4 characters\r
+ while (result.size() % 4 != 0)\r
+ result.insert((std::string::size_type)0, 1, result[0]);\r
+ // now convert to hex\r
+ std::string hex_result;\r
+ for (unsigned i = 0; i < result.size()/4; i++)\r
+ {\r
+ // yuck - ugly or what?\r
+ if (result[i*4] == '0')\r
+ {\r
+ if (result[i*4+1] == '0')\r
+ {\r
+ if (result[i*4+2] == '0')\r
+ {\r
+ if (result[i*4+3] == '0')\r
+ hex_result += '0';\r
+ else\r
+ hex_result += '1';\r
+ }\r
+ else\r
+ {\r
+ if (result[i*4+3] == '0')\r
+ hex_result += '2';\r
+ else\r
+ hex_result += '3';\r
+ }\r
+ }\r
+ else\r
+ {\r
+ if (result[i*4+2] == '0')\r
+ {\r
+ if (result[i*4+3] == '0')\r
+ hex_result += '4';\r
+ else\r
+ hex_result += '5';\r
+ }\r
+ else\r
+ {\r
+ if (result[i*4+3] == '0')\r
+ hex_result += '6';\r
+ else\r
+ hex_result += '7';\r
+ }\r
+ }\r
+ }\r
+ else\r
+ {\r
+ if (result[i*4+1] == '0')\r
+ {\r
+ if (result[i*4+2] == '0')\r
+ {\r
+ if (result[i*4+3] == '0')\r
+ hex_result += '8';\r
+ else\r
+ hex_result += '9';\r
+ }\r
+ else\r
+ {\r
+ if (result[i*4+3] == '0')\r
+ hex_result += 'a';\r
+ else\r
+ hex_result += 'b';\r
+ }\r
+ }\r
+ else\r
+ {\r
+ if (result[i*4+2] == '0')\r
+ {\r
+ if (result[i*4+3] == '0')\r
+ hex_result += 'c';\r
+ else\r
+ hex_result += 'd';\r
+ }\r
+ else\r
+ {\r
+ if (result[i*4+3] == '0')\r
+ hex_result += 'e';\r
+ else\r
+ hex_result += 'f';\r
+ }\r
+ }\r
+ }\r
+ }\r
+ result = hex_result;\r
+ // add the prefix\r
+ result.insert((std::string::size_type)0, "0x");\r
+ }\r
+ }\r
+ else\r
+ {\r
+ // convert to sign-magnitude\r
+ // the representation is:\r
+ // [sign]magnitude\r
+ bool negative = local_i.negative();\r
+ local_i.abs();\r
+ // create a representation of the magnitude by successive division\r
+ inf inf_radix(radix);\r
+ do\r
+ {\r
+ std::pair<inf,inf> divided = local_i.divide(inf_radix);\r
+ unsigned remainder = divided.second.to_unsigned();\r
+ char digit = to_char[remainder];\r
+ result.insert((std::string::size_type)0, 1, digit);\r
+ local_i = divided.first;\r
+ }\r
+ while(!local_i.zero());\r
+ // add the prefixes\r
+ // add a sign only for negative values\r
+ if (negative)\r
+ result.insert((std::string::size_type)0, 1, '-');\r
+ }\r
+ }\r
+\r
+ ////////////////////////////////////////////////////////////////////////////////\r
+ // Conversions FROM string\r
+\r
+ void convert_from_string(const std::string& str, inf& result, unsigned radix = 10) throw(std::invalid_argument)\r
+ {\r
+ result = 0;\r
+ // only support the C-style radixes plus 0b for binary\r
+ // a radix of 0 means deduce the radix from the input - assume 10\r
+ if (radix != 0 && radix != 2 && radix != 8 && radix != 10 && radix != 16)\r
+ throw std::invalid_argument("invalid radix value");\r
+ unsigned i = 0;\r
+ // the radix passed as a parameter is just the default - it can be\r
+ // overridden by the C prefix\r
+ // Note: a leading zero is the C-style prefix for octal - I only make this\r
+ // override the default when the default radix is not specified\r
+ // first check for a C-style prefix\r
+ bool c_style = false;\r
+ if (i < str.size() && str[i] == '0')\r
+ {\r
+ // binary or hex\r
+ if (i+1 < str.size() && tolower(str[i+1]) == 'x')\r
+ {\r
+ c_style = true;\r
+ radix = 16;\r
+ i += 2;\r
+ }\r
+ else if (i+1 < str.size() && tolower(str[i+1]) == 'b')\r
+ {\r
+ c_style = true;\r
+ radix = 2;\r
+ i += 2;\r
+ }\r
+ else if (radix == 0)\r
+ {\r
+ c_style = true;\r
+ radix = 8;\r
+ i += 1;\r
+ }\r
+ }\r
+ if (radix == 0)\r
+ radix = 10;\r
+ if (c_style)\r
+ {\r
+ // the C style formats are bit patterns not integer values - these need\r
+ // to be sign-extended to get the right value\r
+ std::string binary;\r
+ if (radix == 2)\r
+ {\r
+ for (unsigned j = i; j < str.size(); j++)\r
+ {\r
+ switch(str[j])\r
+ {\r
+ case '0':\r
+ binary += '0';\r
+ break;\r
+ case '1':\r
+ binary += '1';\r
+ break;\r
+ default:\r
+ throw std::invalid_argument("invalid binary character in string " + str);\r
+ }\r
+ }\r
+ }\r
+ else if (radix == 8)\r
+ {\r
+ for (unsigned j = i; j < str.size(); j++)\r
+ {\r
+ switch(str[j])\r
+ {\r
+ case '0':\r
+ binary += "000";\r
+ break;\r
+ case '1':\r
+ binary += "001";\r
+ break;\r
+ case '2':\r
+ binary += "010";\r
+ break;\r
+ case '3':\r
+ binary += "011";\r
+ break;\r
+ case '4':\r
+ binary += "100";\r
+ break;\r
+ case '5':\r
+ binary += "101";\r
+ break;\r
+ case '6':\r
+ binary += "110";\r
+ break;\r
+ case '7':\r
+ binary += "111";\r
+ break;\r
+ default:\r
+ throw std::invalid_argument("invalid octal character in string " + str);\r
+ }\r
+ }\r
+ }\r
+ else\r
+ {\r
+ for (unsigned j = i; j < str.size(); j++)\r
+ {\r
+ switch(tolower(str[j]))\r
+ {\r
+ case '0':\r
+ binary += "0000";\r
+ break;\r
+ case '1':\r
+ binary += "0001";\r
+ break;\r
+ case '2':\r
+ binary += "0010";\r
+ break;\r
+ case '3':\r
+ binary += "0011";\r
+ break;\r
+ case '4':\r
+ binary += "0100";\r
+ break;\r
+ case '5':\r
+ binary += "0101";\r
+ break;\r
+ case '6':\r
+ binary += "0110";\r
+ break;\r
+ case '7':\r
+ binary += "0111";\r
+ break;\r
+ case '8':\r
+ binary += "1000";\r
+ break;\r
+ case '9':\r
+ binary += "1001";\r
+ break;\r
+ case 'a':\r
+ binary += "1010";\r
+ break;\r
+ case 'b':\r
+ binary += "1011";\r
+ break;\r
+ case 'c':\r
+ binary += "1100";\r
+ break;\r
+ case 'd':\r
+ binary += "1101";\r
+ break;\r
+ case 'e':\r
+ binary += "1110";\r
+ break;\r
+ case 'f':\r
+ binary += "1111";\r
+ break;\r
+ default:\r
+ throw std::invalid_argument("invalid hex character in string " + str);\r
+ }\r
+ }\r
+ }\r
+ // now convert the value\r
+ result.resize(binary.size());\r
+ for (unsigned j = 0; j < binary.size(); j++)\r
+ result.preset(binary.size() - j - 1, binary[j] == '1');\r
+ }\r
+ else\r
+ {\r
+ // sign-magnitude representation\r
+ // now scan for a sign and find whether this is a negative number\r
+ bool negative = false;\r
+ if (i < str.size())\r
+ {\r
+ switch (str[i])\r
+ {\r
+ case '-':\r
+ negative = true;\r
+ i++;\r
+ break;\r
+ case '+':\r
+ i++;\r
+ break;\r
+ }\r
+ }\r
+ for (; i < str.size(); i++)\r
+ {\r
+ result *= inf(radix);\r
+ unsigned char ascii = (unsigned char)str[i];\r
+ int ch = from_char[ascii] ;\r
+ if (ch == -1)\r
+ throw std::invalid_argument("invalid decimal character in string " + str);\r
+ result += inf(ch);\r
+ }\r
+ if (negative)\r
+ result.negate();\r
+ }\r
+ }\r
+\r
+ ////////////////////////////////////////////////////////////////////////////////\r
+ // constructors - mostly implemented in terms of the assignment operators\r
+\r
+ inf::inf(void)\r
+ {\r
+ // void constructor initialises to zero - represented as a single-byte value containing zero\r
+ m_data.append(1,std::string::value_type(0));\r
+ }\r
+\r
+ inf::inf(short r)\r
+ {\r
+ operator=(r);\r
+ }\r
+\r
+ inf::inf(unsigned short r)\r
+ {\r
+ operator=(r);\r
+ }\r
+\r
+ inf::inf(int r)\r
+ {\r
+ operator=(r);\r
+ }\r
+\r
+ inf::inf(unsigned r)\r
+ {\r
+ operator=(r);\r
+ }\r
+\r
+ inf::inf(long r)\r
+ {\r
+ operator=(r);\r
+ }\r
+\r
+ inf::inf(unsigned long r)\r
+ {\r
+ operator=(r);\r
+ }\r
+\r
+ inf::inf (const std::string& r) throw(std::invalid_argument)\r
+ {\r
+ operator=(r);\r
+ }\r
+\r
+ inf::inf(const inf& r)\r
+ {\r
+#ifdef __BORLANDC__\r
+ // work round bug in Borland compiler - copy constructor fails if string\r
+ // contains null characters, so do my own copy\r
+ for (unsigned i = 0; i < r.m_data.size(); i++)\r
+ m_data += r.m_data[i];\r
+#else\r
+ m_data = r.m_data;\r
+#endif\r
+ }\r
+\r
+ ////////////////////////////////////////////////////////////////////////////////\r
+\r
+ inf::~inf(void)\r
+ {\r
+ }\r
+\r
+ ////////////////////////////////////////////////////////////////////////////////\r
+ // assignments convert from iteger types to internal representation\r
+\r
+ inf& inf::operator = (short r)\r
+ {\r
+ convert_from_signed(r, m_data);\r
+ return *this;\r
+ }\r
+\r
+ inf& inf::operator = (unsigned short r)\r
+ {\r
+ convert_from_unsigned(r, m_data);\r
+ return *this;\r
+ }\r
+\r
+ inf& inf::operator = (int r)\r
+ {\r
+ convert_from_signed(r, m_data);\r
+ return *this;\r
+ }\r
+\r
+ inf& inf::operator = (unsigned r)\r
+ {\r
+ convert_from_unsigned(r, m_data);\r
+ return *this;\r
+ }\r
+\r
+ inf& inf::operator = (long r)\r
+ {\r
+ convert_from_signed(r, m_data);\r
+ return *this;\r
+ }\r
+\r
+ inf& inf::operator = (unsigned long r)\r
+ {\r
+ convert_from_unsigned(r, m_data);\r
+ return *this;\r
+ }\r
+\r
+ inf& inf::operator = (const std::string& r) throw(std::invalid_argument)\r
+ {\r
+ convert_from_string(r, *this);\r
+ return *this;\r
+ }\r
+\r
+ inf& inf::operator = (const inf& r)\r
+ {\r
+ m_data = r.m_data;\r
+ return *this;\r
+ }\r
+\r
+ ////////////////////////////////////////////////////////////////////////////////\r
+\r
+ short inf::to_short(bool truncate) const throw(std::overflow_error)\r
+ {\r
+ short result = 0;\r
+ if (!convert_to_signed(m_data, result))\r
+ if (!truncate)\r
+ throw std::overflow_error("stlplus::inf::to_short");\r
+ return result;\r
+ }\r
+\r
+ unsigned short inf::to_unsigned_short(bool truncate) const throw(std::overflow_error)\r
+ {\r
+ unsigned short result = 0;\r
+ if (!convert_to_unsigned(m_data, result))\r
+ if (!truncate)\r
+ throw std::overflow_error("stlplus::inf::to_unsigned_short");\r
+ return result;\r
+ }\r
+\r
+ int inf::to_int(bool truncate) const throw(std::overflow_error)\r
+ {\r
+ int result = 0;\r
+ if (!convert_to_signed(m_data, result))\r
+ if (!truncate)\r
+ throw std::overflow_error("stlplus::inf::to_int");\r
+ return result;\r
+ }\r
+\r
+ unsigned inf::to_unsigned(bool truncate) const throw(std::overflow_error)\r
+ {\r
+ unsigned result = 0;\r
+ if (!convert_to_unsigned(m_data, result))\r
+ if (!truncate)\r
+ throw std::overflow_error("stlplus::inf::to_unsigned");\r
+ return result;\r
+ }\r
+\r
+ long inf::to_long(bool truncate) const throw(std::overflow_error)\r
+ {\r
+ long result = 0;\r
+ if (!convert_to_signed(m_data, result))\r
+ if (!truncate)\r
+ throw std::overflow_error("stlplus::inf::to_long");\r
+ return result;\r
+ }\r
+\r
+ unsigned long inf::to_unsigned_long(bool truncate) const throw(std::overflow_error)\r
+ {\r
+ unsigned long result = 0;\r
+ if (!convert_to_unsigned(m_data, result))\r
+ if (!truncate)\r
+ throw std::overflow_error("stlplus::inf::to_unsigned_long");\r
+ return result;\r
+ }\r
+\r
+ ////////////////////////////////////////////////////////////////////////////////\r
+ // resize the inf regardless of the data\r
+\r
+ void inf::resize(unsigned bits)\r
+ {\r
+ if (bits == 0) bits = 1;\r
+ unsigned bytes = (bits+7)/8;\r
+ byte extend = negative() ? byte(255) : byte (0);\r
+ while(bytes > m_data.size())\r
+ m_data.append(1,extend);\r
+ }\r
+\r
+ // reduce the bit count to the minimum needed to preserve the value\r
+\r
+ void inf::reduce(void)\r
+ {\r
+ reduce_string(m_data);\r
+ }\r
+\r
+ ////////////////////////////////////////////////////////////////////////////////\r
+ // the number of significant bits in the number\r
+\r
+ unsigned inf::bits (void) const\r
+ {\r
+ // The number of significant bits in the integer value - this is the number\r
+ // of indexable bits less any redundant sign bits at the msb\r
+ // This does not assume that the inf has been reduced to its minimum form\r
+ unsigned result = indexable_bits();\r
+ bool sign = bit(result-1);\r
+ while (result > 1 && (sign == bit(result-2)))\r
+ result--;\r
+ return result;\r
+ }\r
+\r
+ unsigned inf::size(void) const\r
+ {\r
+ return bits();\r
+ }\r
+\r
+ unsigned inf::indexable_bits (void) const\r
+ {\r
+ return 8 * unsigned(m_data.size());\r
+ }\r
+\r
+ ////////////////////////////////////////////////////////////////////////////////\r
+ // bitwise operations\r
+\r
+ bool inf::bit (unsigned index) const throw(std::out_of_range)\r
+ {\r
+ if (index >= indexable_bits())\r
+ throw std::out_of_range(std::string("stlplus::inf::bit"));\r
+ // first split the offset into byte offset and bit offset\r
+ unsigned byte_offset = index/8;\r
+ unsigned bit_offset = index%8;\r
+ return (byte(m_data[byte_offset]) & (byte(1) << bit_offset)) != 0;\r
+ }\r
+\r
+ bool inf::operator [] (unsigned index) const throw(std::out_of_range)\r
+ {\r
+ return bit(index);\r
+ }\r
+\r
+ void inf::set (unsigned index) throw(std::out_of_range)\r
+ {\r
+ if (index >= indexable_bits())\r
+ throw std::out_of_range(std::string("stlplus::inf::set"));\r
+ // first split the offset into byte offset and bit offset\r
+ unsigned byte_offset = index/8;\r
+ unsigned bit_offset = index%8;\r
+ m_data[byte_offset] |= (byte(1) << bit_offset);\r
+ }\r
+\r
+ void inf::clear (unsigned index) throw(std::out_of_range)\r
+ {\r
+ if (index >= indexable_bits())\r
+ throw std::out_of_range(std::string("stlplus::inf::clear"));\r
+ // first split the offset into byte offset and bit offset\r
+ unsigned byte_offset = index/8;\r
+ unsigned bit_offset = index%8;\r
+ m_data[byte_offset] &= (~(byte(1) << bit_offset));\r
+ }\r
+\r
+ void inf::preset (unsigned index, bool value) throw(std::out_of_range)\r
+ {\r
+ if (value)\r
+ set(index);\r
+ else\r
+ clear(index);\r
+ }\r
+\r
+ inf inf::slice(unsigned low, unsigned high) const throw(std::out_of_range)\r
+ {\r
+ if (low >= indexable_bits())\r
+ throw std::out_of_range(std::string("stlplus::inf::slice: low index"));\r
+ if (high >= indexable_bits())\r
+ throw std::out_of_range(std::string("stlplus::inf::slice: high index"));\r
+ inf result;\r
+ if (high >= low)\r
+ {\r
+ // create a result the right size and filled with sign bits\r
+ std::string::size_type result_size = (high-low+1+7)/8;\r
+ result.m_data.erase();\r
+ byte extend = bit(high) ? byte(255) : byte (0);\r
+ while (result.m_data.size() < result_size)\r
+ result.m_data.append(1,extend);\r
+ // now set the relevant bits\r
+ for (unsigned i = low; i <= high; i++)\r
+ result.preset(i-low, bit(i));\r
+ }\r
+ return result;\r
+ }\r
+\r
+ ////////////////////////////////////////////////////////////////////////////////\r
+ // testing operations\r
+\r
+ bool inf::negative (void) const\r
+ {\r
+ return bit(indexable_bits()-1);\r
+ }\r
+\r
+ bool inf::natural (void) const\r
+ {\r
+ return !negative();\r
+ }\r
+\r
+ bool inf::positive (void) const\r
+ {\r
+ return natural() && !zero();\r
+ }\r
+\r
+ bool inf::zero (void) const\r
+ {\r
+ for (std::string::size_type i = 0; i < m_data.size(); i++)\r
+ if (m_data[i] != 0)\r
+ return false;\r
+ return true;\r
+ }\r
+\r
+ bool inf::non_zero (void) const\r
+ {\r
+ return !zero();\r
+ }\r
+\r
+ bool inf::operator ! (void) const\r
+ {\r
+ return zero();\r
+ }\r
+\r
+ ////////////////////////////////////////////////////////////////////////////////\r
+ // comparison operators\r
+\r
+ bool inf::operator == (const inf& r) const\r
+ {\r
+ // Two infs are equal if they are numerically equal, even if they are\r
+ // different sizes (i.e. they could be non-reduced values).\r
+ // This makes life a little more complicated than if I could assume that values were reduced.\r
+ byte l_extend = negative() ? byte(255) : byte (0);\r
+ byte r_extend = r.negative() ? byte(255) : byte (0);\r
+ std::string::size_type bytes = maximum(m_data.size(),r.m_data.size());\r
+ for (std::string::size_type i = bytes; i--; )\r
+ {\r
+ byte l_byte = (i < m_data.size() ? byte(m_data[i]) : l_extend);\r
+ byte r_byte = (i < r.m_data.size() ? byte(r.m_data[i]) : r_extend);\r
+ if (l_byte != r_byte)\r
+ return false;\r
+ }\r
+ return true;\r
+ }\r
+\r
+ bool inf::operator != (const inf& r) const\r
+ {\r
+ return !operator==(r);\r
+ }\r
+\r
+ bool inf::operator < (const inf& r) const\r
+ {\r
+ // This could be implemented in terms of subtraction. However, it can be\r
+ // simplified since there is no need to calculate the accurate difference,\r
+ // just the direction of the difference. I compare from msB down and as\r
+ // soon as a byte difference is found, that defines the ordering. The\r
+ // problem is that in 2's-complement, all negative values are greater than\r
+ // all natural values if you just do a straight unsigned comparison. I\r
+ // handle this by doing a preliminary test for different signs.\r
+\r
+ // For example, a 3-bit signed type has the coding:\r
+ // 000 = 0\r
+ // ...\r
+ // 011 = 3\r
+ // 100 = -4\r
+ // ...\r
+ // 111 = -1\r
+\r
+ // So, for natural values, the ordering of the integer values is the\r
+ // ordering of the bit patterns. Similarly, for negative values, the\r
+ // ordering of the integer values is the ordering of the bit patterns\r
+ // However, the bit patterns for the negative values are *greater than*\r
+ // the natural values. This is a side-effect of the naffness of\r
+ // 2's-complement representation\r
+\r
+ // first handle the case of comparing two values with different signs\r
+ bool l_sign = negative();\r
+ bool r_sign = r.negative();\r
+ if (l_sign != r_sign)\r
+ {\r
+ // one argument must be negative and the other natural\r
+ // the left is less if it is the negative one\r
+ return l_sign;\r
+ }\r
+ // the arguments are the same sign\r
+ // so the ordering is a simple unsigned byte-by-byte comparison\r
+ // However, this is complicated by the possibility that the values could be different lengths\r
+ byte l_extend = l_sign ? byte(255) : byte (0);\r
+ byte r_extend = r_sign ? byte(255) : byte (0);\r
+ std::string::size_type bytes = maximum(m_data.size(),r.m_data.size());\r
+ for (std::string::size_type i = bytes; i--; )\r
+ {\r
+ byte l_byte = (i < m_data.size() ? byte(m_data[i]) : l_extend);\r
+ byte r_byte = (i < r.m_data.size() ? byte(r.m_data[i]) : r_extend);\r
+ if (l_byte != r_byte)\r
+ return l_byte < r_byte;\r
+ }\r
+ // if I get here, the two are equal, so that is not less-than\r
+ return false;\r
+ }\r
+\r
+ bool inf::operator <= (const inf& r) const\r
+ {\r
+ return !(r < *this);\r
+ }\r
+\r
+ bool inf::operator > (const inf& r) const\r
+ {\r
+ return r < *this;\r
+ }\r
+\r
+ bool inf::operator >= (const inf& r) const\r
+ {\r
+ return !(*this < r);\r
+ }\r
+\r
+ ////////////////////////////////////////////////////////////////////////////////\r
+ // logical operators\r
+\r
+ inf& inf::invert (void)\r
+ {\r
+ for (std::string::size_type i = 0; i < m_data.size(); i++)\r
+ m_data[i] = ~m_data[i];\r
+ return *this;\r
+ }\r
+\r
+ inf inf::operator ~ (void) const\r
+ {\r
+ inf result(*this);\r
+ result.invert();\r
+ return result;\r
+ }\r
+\r
+ inf& inf::operator &= (const inf& r)\r
+ {\r
+ // bitwise AND is extended to the length of the largest argument\r
+ byte l_extend = negative() ? byte(255) : byte (0);\r
+ byte r_extend = r.negative() ? byte(255) : byte (0);\r
+ std::string::size_type bytes = maximum(m_data.size(),r.m_data.size());\r
+ for (std::string::size_type i = 0; i < bytes; i++)\r
+ {\r
+ byte l_byte = (i < m_data.size() ? byte(m_data[i]) : l_extend);\r
+ byte r_byte = (i < r.m_data.size() ? byte(r.m_data[i]) : r_extend);\r
+ byte result = l_byte & r_byte;\r
+ if (i < m_data.size())\r
+ m_data[i] = result;\r
+ else\r
+ m_data.append(1,result);\r
+ }\r
+ // now reduce the result\r
+ reduce();\r
+ return *this;\r
+ }\r
+\r
+ inf inf::operator & (const inf& r) const\r
+ {\r
+ inf result(*this);\r
+ result &= r;\r
+ return result;\r
+ }\r
+\r
+ inf& inf::operator |= (const inf& r)\r
+ {\r
+ // bitwise OR is extended to the length of the largest argument\r
+ byte l_extend = negative() ? byte(255) : byte (0);\r
+ byte r_extend = r.negative() ? byte(255) : byte (0);\r
+ std::string::size_type bytes = maximum(m_data.size(),r.m_data.size());\r
+ for (std::string::size_type i = 0; i < bytes; i++)\r
+ {\r
+ byte l_byte = (i < m_data.size() ? byte(m_data[i]) : l_extend);\r
+ byte r_byte = (i < r.m_data.size() ? byte(r.m_data[i]) : r_extend);\r
+ byte result = l_byte | r_byte;\r
+ if (i < m_data.size())\r
+ m_data[i] = result;\r
+ else\r
+ m_data.append(1,result);\r
+ }\r
+ // now reduce the result\r
+ reduce();\r
+ return *this;\r
+ }\r
+\r
+ inf inf::operator | (const inf& r) const\r
+ {\r
+ inf result(*this);\r
+ result |= r;\r
+ return result;\r
+ }\r
+\r
+ inf& inf::operator ^= (const inf& r)\r
+ {\r
+ // bitwise XOR is extended to the length of the largest argument\r
+ byte l_extend = negative() ? byte(255) : byte (0);\r
+ byte r_extend = r.negative() ? byte(255) : byte (0);\r
+ std::string::size_type bytes = maximum(m_data.size(),r.m_data.size());\r
+ for (std::string::size_type i = 0; i < bytes; i++)\r
+ {\r
+ byte l_byte = (i < m_data.size() ? byte(m_data[i]) : l_extend);\r
+ byte r_byte = (i < r.m_data.size() ? byte(r.m_data[i]) : r_extend);\r
+ byte result = l_byte ^ r_byte;\r
+ if (i < m_data.size())\r
+ m_data[i] = result;\r
+ else\r
+ m_data.append(1,result);\r
+ }\r
+ // now reduce the result\r
+ reduce();\r
+ return *this;\r
+ }\r
+\r
+ inf inf::operator ^ (const inf& r) const\r
+ {\r
+ inf result(*this);\r
+ result ^= r;\r
+ return result;\r
+ }\r
+\r
+ ////////////////////////////////////////////////////////////////////////////////\r
+ // shift operators all preserve the value by increasing the word size\r
+\r
+ inf& inf::operator <<= (unsigned shift)\r
+ {\r
+ // left shift is a shift towards the msb, with 0s being shifted in at the lsb\r
+ // split this into a byte shift followed by a bit shift\r
+\r
+ // first expand the value to be big enough for the result\r
+ std::string::size_type new_size = (indexable_bits() + shift + 7) / 8;\r
+ byte extend = negative() ? byte(255) : byte (0);\r
+ while (m_data.size() < new_size)\r
+ m_data.append(1,extend);\r
+ // now do the byte shift\r
+ unsigned byte_shift = shift/8;\r
+ if (byte_shift > 0)\r
+ {\r
+ for (std::string::size_type b = new_size; b--; )\r
+ m_data[b] = (b >= byte_shift) ? m_data[b-byte_shift] : byte(0);\r
+ }\r
+ // and finally the bit shift\r
+ unsigned bit_shift = shift%8;\r
+ if (bit_shift > 0)\r
+ {\r
+ for (std::string::size_type b = new_size; b--; )\r
+ {\r
+ byte current = byte(m_data[b]);\r
+ byte previous = b > 0 ? m_data[b-1] : byte(0);\r
+ m_data[b] = (current << bit_shift) | (previous >> (8 - bit_shift));\r
+ }\r
+ }\r
+ // now reduce the result\r
+ reduce();\r
+ return *this;\r
+ }\r
+\r
+ inf inf::operator << (unsigned shift) const\r
+ {\r
+ inf result(*this);\r
+ result <<= shift;\r
+ return result;\r
+ }\r
+\r
+ inf& inf::operator >>= (unsigned shift)\r
+ {\r
+ // right shift is a shift towards the lsb, with sign bits being shifted in at the msb\r
+ // split this into a byte shift followed by a bit shift\r
+\r
+ // a byte of sign bits\r
+ byte extend = negative() ? byte(255) : byte (0);\r
+ // do the byte shift\r
+ unsigned byte_shift = shift/8;\r
+ if (byte_shift > 0)\r
+ {\r
+ for (std::string::size_type b = 0; b < m_data.size(); b++)\r
+ m_data[b] = (b + byte_shift < m_data.size()) ? m_data[b+byte_shift] : extend;\r
+ }\r
+ // and finally the bit shift\r
+ unsigned bit_shift = shift%8;\r
+ if (bit_shift > 0)\r
+ {\r
+ for (std::string::size_type b = 0; b < m_data.size(); b++)\r
+ {\r
+ byte current = byte(m_data[b]);\r
+ byte next = ((b+1) < m_data.size()) ? m_data[b+1] : extend;\r
+ byte shifted = (current >> bit_shift) | (next << (8 - bit_shift));\r
+ m_data[b] = shifted;\r
+ }\r
+ }\r
+ // now reduce the result\r
+ reduce();\r
+ return *this;\r
+ }\r
+\r
+ inf inf::operator >> (unsigned shift) const\r
+ {\r
+ inf result(*this);\r
+ result >>= shift;\r
+ return result;\r
+ }\r
+\r
+ ////////////////////////////////////////////////////////////////////////////////\r
+ // negation operators\r
+\r
+ inf& inf::negate (void)\r
+ {\r
+ // do 2's-complement negation\r
+ // equivalent to inversion plus one\r
+ invert();\r
+ operator += (inf(1));\r
+ return *this;\r
+ }\r
+\r
+ inf inf::operator - (void) const\r
+ {\r
+ inf result(*this);\r
+ result.negate();\r
+ return result;\r
+ }\r
+\r
+ inf& inf::abs(void)\r
+ {\r
+ if (negative()) negate();\r
+ return *this;\r
+ }\r
+\r
+ inf abs(const inf& i)\r
+ {\r
+ inf result = i;\r
+ result.abs();\r
+ return result;\r
+ }\r
+\r
+ ////////////////////////////////////////////////////////////////////////////////\r
+ // addition operators\r
+\r
+ inf& inf::operator += (const inf& r)\r
+ {\r
+ // do 2's-complement addition\r
+ // Note that the addition can give a result that is larger than either argument\r
+ byte carry = 0;\r
+ std::string::size_type max_size = maximum(m_data.size(),r.m_data.size());\r
+ byte l_extend = negative() ? byte(255) : byte (0);\r
+ byte r_extend = r.negative() ? byte(255) : byte (0);\r
+ for (std::string::size_type i = 0; i < max_size; i++)\r
+ {\r
+ byte l_byte = (i < m_data.size() ? byte(m_data[i]) : l_extend);\r
+ byte r_byte = (i < r.m_data.size() ? byte(r.m_data[i]) : r_extend);\r
+ // calculate the addition in a type that is bigger than a byte in order to catch the carry-out\r
+ unsigned short result = ((unsigned short)(l_byte)) + ((unsigned short)(r_byte)) + carry;\r
+ // now truncate the result to get the lsB\r
+ if (i < m_data.size())\r
+ m_data[i] = byte(result);\r
+ else\r
+ m_data.append(1,byte(result));\r
+ // and capture the carry out by grabbing the second byte of the result\r
+ carry = byte(result >> 8);\r
+ }\r
+ // if the result overflowed or underflowed, add an extra byte to catch it\r
+ unsigned short result = ((unsigned short)(l_extend)) + ((unsigned short)(r_extend)) + carry;\r
+ if (byte(result) != (negative() ? byte(255) : byte(0)))\r
+ m_data.append(1,byte(result));\r
+ // now reduce the result\r
+ reduce();\r
+ return *this;\r
+ }\r
+\r
+ inf inf::operator + (const inf& r) const\r
+ {\r
+ inf result(*this);\r
+ result += r;\r
+ return result;\r
+ }\r
+\r
+ ////////////////////////////////////////////////////////////////////////////////\r
+ // subtraction operators\r
+\r
+ inf& inf::operator -= (const inf& r)\r
+ {\r
+ // subtraction is defined in terms of negation and addition\r
+ inf negated = -r;\r
+ operator += (negated);\r
+ return *this;\r
+ }\r
+\r
+ inf inf::operator - (const inf& r) const\r
+ {\r
+ inf result(*this);\r
+ result -= r;\r
+ return result;\r
+ }\r
+\r
+ ////////////////////////////////////////////////////////////////////////////////\r
+ // multiplication operators\r
+\r
+ inf& inf::operator *= (const inf& r)\r
+ {\r
+ // 2's complement multiplication\r
+ // one day I'll do a more efficient version than this based on the underlying representation\r
+ inf left(*this);\r
+ inf right = r;\r
+ // make the right value natural but preserve its sign for later\r
+ bool right_negative = right.negative();\r
+ right.abs();\r
+ // implemented as a series of conditional additions\r
+ operator = (0);\r
+ // left.resize(right.bits() + left.bits() - 1);\r
+ left <<= right.bits()-1;\r
+ for (unsigned i = right.bits(); i--; )\r
+ {\r
+ if (right[i]) \r
+ operator += (left);\r
+ left >>= 1;\r
+ }\r
+ if (right_negative)\r
+ negate();\r
+ // now reduce the result\r
+ reduce();\r
+ return *this;\r
+ }\r
+\r
+ inf inf::operator * (const inf& r) const\r
+ {\r
+ inf result(*this);\r
+ result *= r;\r
+ return result;\r
+ }\r
+\r
+ ////////////////////////////////////////////////////////////////////////////////\r
+ // division and remainder operators\r
+\r
+ std::pair<inf,inf> inf::divide(const inf& right) const throw(divide_by_zero)\r
+ {\r
+ if (right.zero())\r
+ throw divide_by_zero("stlplus::inf::divide");\r
+ inf numerator(*this);\r
+ inf denominator = right;\r
+ // make the numerator natural but preserve the sign for later\r
+ bool numerator_negative = numerator.negative();\r
+ numerator.abs();\r
+ // same with the denominator\r
+ bool denominator_negative = denominator.negative();\r
+ denominator.abs();\r
+ // the quotient and remainder will form the result\r
+ // start with the quotiont zero and the remainder equal to the whole of the\r
+ // numerator, then do trial subtraction from this\r
+ inf quotient;\r
+ inf remainder = numerator;\r
+ // there's nothing more to do if the numerator is smaller than the denominator\r
+ // but otherwise do the division\r
+ if (numerator.bits() >= denominator.bits())\r
+ {\r
+ // make the quotient big enough to take the result\r
+ quotient.resize(numerator.bits());\r
+ // start with the numerator shifted to the far left\r
+ unsigned shift = numerator.bits() - denominator.bits();\r
+ denominator <<= shift;\r
+ // do the division by repeated subtraction, \r
+ for (unsigned i = shift+1; i--; )\r
+ {\r
+ if (remainder >= denominator)\r
+ {\r
+ remainder -= denominator;\r
+ quotient.set(i);\r
+ }\r
+ denominator >>= 1;\r
+ }\r
+ }\r
+ // now adjust the signs \r
+ // x/(-y) == (-x)/y == -(x/y)\r
+ if (numerator_negative != denominator_negative)\r
+ quotient.negate();\r
+ quotient.reduce();\r
+ // x%(-y) == x%y and (-x)%y == -(x%y)\r
+ if (numerator_negative)\r
+ remainder.negate();\r
+ remainder.reduce();\r
+ return std::pair<inf,inf>(quotient,remainder);\r
+ }\r
+\r
+ inf& inf::operator /= (const inf& r) throw(divide_by_zero)\r
+ {\r
+ std::pair<inf,inf> result = divide(r);\r
+ operator=(result.first);\r
+ return *this;\r
+ }\r
+\r
+ inf inf::operator / (const inf& r) const throw(divide_by_zero)\r
+ {\r
+ std::pair<inf,inf> result = divide(r);\r
+ return result.first;\r
+ }\r
+\r
+ inf& inf::operator %= (const inf& r) throw(divide_by_zero)\r
+ {\r
+ std::pair<inf,inf> result = divide(r);\r
+ operator=(result.second);\r
+ return *this;\r
+ }\r
+\r
+ inf inf::operator % (const inf& r) const throw(divide_by_zero)\r
+ {\r
+ std::pair<inf,inf> result = divide(r);\r
+ return result.second;\r
+ }\r
+\r
+ ////////////////////////////////////////////////////////////////////////////////\r
+ // prefix (void) and postfix (int) operators\r
+\r
+ inf& inf::operator ++ (void)\r
+ {\r
+ operator += (inf(1));\r
+ return *this;\r
+ }\r
+\r
+ inf inf::operator ++ (int)\r
+ {\r
+ inf old(*this);\r
+ operator += (inf(1));\r
+ return old;\r
+ }\r
+\r
+ inf& inf::operator -- (void)\r
+ {\r
+ operator -= (inf(1));\r
+ return *this;\r
+ }\r
+\r
+ inf inf::operator -- (int)\r
+ {\r
+ inf old(*this);\r
+ operator -= (inf(1));\r
+ return old;\r
+ }\r
+\r
+ ////////////////////////////////////////////////////////////////////////////////\r
+ // string representation and I/O routines\r
+\r
+ std::string inf::to_string(unsigned radix) const\r
+ throw(std::invalid_argument)\r
+ {\r
+ std::string result;\r
+ convert_to_string(*this, result, radix);\r
+ return result;\r
+ }\r
+\r
+ inf& inf::from_string(const std::string& value, unsigned radix)\r
+ throw(std::invalid_argument)\r
+ {\r
+ convert_from_string(value, *this, radix);\r
+ return *this;\r
+ }\r
+\r
+ std::ostream& operator << (std::ostream& str, const inf& i)\r
+ {\r
+ try\r
+ {\r
+ // get radix\r
+ unsigned radix = 10;\r
+ if (str.flags() & std::ios_base::oct)\r
+ radix = 8;\r
+ if (str.flags() & std::ios_base::hex)\r
+ radix = 16;\r
+ // the field width is handled by iostream, so I don't need to handle it as well\r
+ // generate the string representation then print it\r
+ str << i.to_string(radix);\r
+ }\r
+ catch(const std::invalid_argument)\r
+ {\r
+ str.setstate(std::ios_base::badbit);\r
+ }\r
+ return str;\r
+ }\r
+\r
+ std::istream& operator >> (std::istream& str, inf& i)\r
+ {\r
+ try\r
+ {\r
+ // get radix\r
+ unsigned radix = 10;\r
+ if (str.flags() & std::ios_base::oct)\r
+ radix = 8;\r
+ if (str.flags() & std::ios_base::hex)\r
+ radix = 16;\r
+ // now get the string image of the value\r
+ std::string image;\r
+ str >> image;\r
+ // and convert to inf\r
+ i.from_string(image, radix);\r
+ }\r
+ catch(const std::invalid_argument)\r
+ {\r
+ str.setstate(std::ios_base::badbit);\r
+ }\r
+ return str;\r
+ }\r
+\r
+ ////////////////////////////////////////////////////////////////////////////////\r
+ // diagnostic dump\r
+ // just convert to hex\r
+\r
+ std::string inf::image_debug(void) const\r
+ {\r
+ // create this dump in the human-readable form, i.e. msB to the left\r
+ std::string result = "0x";\r
+ for (std::string::size_type i = m_data.size(); i--; )\r
+ {\r
+ byte current = m_data[i];\r
+ byte msB = (current & byte(0xf0)) >> 4;\r
+ result += to_char[msB];\r
+ byte lsB = (current & byte(0x0f));\r
+ result += to_char[lsB];\r
+ }\r
+ return result;\r
+ }\r
+\r
+ const std::string& inf::get_bytes(void) const\r
+ {\r
+ return m_data;\r
+ }\r
+\r
+ void inf::set_bytes(const std::string& data)\r
+ {\r
+ m_data = data;\r
+ }\r
+\r
+} // end namespace stlplus\r
projects / chaz / yoink / blobdiff