]>
Dogcows Code - chaz/yoink/blob - inf.cpp
d70ab76453f40454f25043c39540ec2b6b3f15c6
1 ////////////////////////////////////////////////////////////////////////////////
3 // Author: Andy Rushton
4 // Copyright: (c) Southampton University 1999-2004
5 // (c) Andy Rushton 2004-2009
6 // License: BSD License, see ../docs/license.html
8 // The integer is represented as a sequence of bytes. They are stored such that
9 // element 0 is the lsB, which makes sense when seen as an integer offset but
10 // is counter-intuitive when you think that a string is usually read from left
11 // to right, 0 to size-1, in which case the lsB is on the *left*.
13 // This solution is compatible with 32-bit and 64-bit machines with either
14 // little-endian or big-endian representations of integers.
16 // Problem: I'm using std::string, which is an array of char. However, char is
17 // not well-defined - it could be signed or unsigned.
19 // In fact, there's no requirement for a char to even be one byte - it can be
20 // any size of one byte or more. However, it's just impossible to make any
21 // progress with that naffness (thanks to the C non-standardisation committee)
22 // and the practice is that char on every platform/compiler I've ever come
23 // across is that char = byte.
25 // The algorithms here use unsigned char to represent bit-patterns so I have to
26 // be careful to type-cast from char to unsigned char a lot. I use a typedef to
29 ////////////////////////////////////////////////////////////////////////////////
32 ////////////////////////////////////////////////////////////////////////////////
37 ////////////////////////////////////////////////////////////////////////////////
38 // choose a sensible C type for a byte
40 typedef unsigned char byte
;
42 ////////////////////////////////////////////////////////////////////////////////
45 // removes leading bytes that don't contribute to the value to create the minimum string representation
46 static void reduce_string(std::string
& data
)
48 while(data
.size() > 1 &&
49 ((byte(data
[data
.size()-1]) == byte(0) && byte(data
[data
.size()-2]) < byte(128)) ||
50 (byte(data
[data
.size()-1]) == byte(255) && byte(data
[data
.size()-2]) >= byte(128))))
52 data
.erase(data
.end()-1);
56 // generic implementations of type conversions from integer type to internal representation
57 // data: integer value for conversion
58 // result: internal representation
61 static void convert_from_signed(const T
& data
, std::string
& result
)
64 bool lsb_first
= little_endian();
65 byte
* address
= (byte
*)&data
;
66 for (size_t i
= 0; i
< sizeof(T
); i
++)
68 size_t offset
= (lsb_first
? i
: (sizeof(T
) - i
- 1));
69 result
.append(1,address
[offset
]);
71 reduce_string(result
);
75 static void convert_from_unsigned(const T
& data
, std::string
& result
)
78 bool lsb_first
= little_endian();
79 byte
* address
= (byte
*)&data
;
80 for (size_t i
= 0; i
< sizeof(T
); i
++)
82 size_t offset
= (lsb_first
? i
: (sizeof(T
) - i
- 1));
83 result
.append(1,address
[offset
]);
85 // inf is signed - so there is a possible extra sign bit to add
86 result
.append(1,std::string::value_type(0));
87 reduce_string(result
);
90 // generic implementations of type conversions from internal representation to an integer type
91 // data : string representation of integer
92 // result: integer result of conversion
93 // return: flag indicating success - false = overflow
96 bool convert_to_signed(const std::string
& data
, T
& result
)
98 bool lsb_first
= little_endian();
99 byte
* address
= (byte
*)&result
;
100 for (size_t i
= 0; i
< sizeof(T
); i
++)
102 size_t offset
= lsb_first
? i
: (sizeof(T
) - i
- 1);
104 address
[offset
] = byte(data
[i
]);
105 else if (data
.empty() || (byte(data
[data
.size()-1]) < byte(128)))
106 address
[offset
] = byte(0);
108 address
[offset
] = byte(255);
110 return data
.size() <= sizeof(T
);
114 bool convert_to_unsigned(const std::string
& data
, T
& result
)
116 bool lsb_first
= little_endian();
117 byte
* address
= (byte
*)&result
;
118 for (size_t i
= 0; i
< sizeof(T
); i
++)
120 size_t offset
= lsb_first
? i
: (sizeof(T
) - i
- 1);
122 address
[offset
] = byte(data
[i
]);
124 address
[offset
] = byte(0);
126 return data
.size() <= sizeof(T
);
129 ////////////////////////////////////////////////////////////////////////////////
130 // Conversions to string
132 static char to_char
[] = "0123456789abcdefghijklmnopqrstuvwxyz";
133 static int from_char
[] =
135 -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
136 -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
137 -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
138 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, -1, -1, -1, -1, -1, -1,
139 -1, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24,
140 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, -1, -1, -1, -1, -1,
141 -1, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24,
142 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, -1, -1, -1, -1, -1,
143 -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
144 -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
145 -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
146 -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
147 -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
148 -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
149 -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
150 -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1
153 static void convert_to_string(const stlplus::inf
& data
, std::string
& result
, unsigned radix
= 10)
154 throw(std::invalid_argument
)
156 // only support the C-style radixes plus 0b for binary
157 if (radix
!= 2 && radix
!= 8 && radix
!= 10 && radix
!= 16)
158 throw std::invalid_argument("invalid radix value");
160 // untangle all the options
161 bool binary
= radix
== 2;
162 bool octal
= radix
== 8;
163 bool hex
= radix
== 16;
164 // the C representations for binary, octal and hex use 2's-complement representation
165 // all other represenations use sign-magnitude
166 if (hex
|| octal
|| binary
)
168 // bit-pattern representation
169 // this is the binary representation optionally shown in octal or hex
170 // first generate the binary by masking the bits
171 for (unsigned j
= local_i
.bits(); j
--; )
172 result
+= (local_i
.bit(j
) ? '1' : '0');
173 // the result is now the full width of the type - e.g. int will give a 32-bit result
174 // now interpret this as either binary, octal or hex and add the prefix
177 // trim down to the smallest string that preserves the value
180 // do not trim to less than 1 bit (sign only)
181 if (result
.size() <= 1) break;
182 // only trim if it doesn't change the sign and therefore the value
183 if (result
[0] != result
[1]) break;
187 result
.insert((std::string::size_type
)0, "0b");
191 // the result is currently binary
192 // trim down to the smallest string that preserves the value
195 // do not trim to less than 2 bits (sign plus 1-bit magnitude)
196 if (result
.size() <= 2) break;
197 // only trim if it doesn't change the sign and therefore the value
198 if (result
[0] != result
[1]) break;
201 // also ensure that the binary is a multiple of 3 bits to make the conversion to octal easier
202 while (result
.size() % 3 != 0)
203 result
.insert((std::string::size_type
)0, 1, result
[0]);
204 // now convert to octal
205 std::string octal_result
;
206 for (unsigned i
= 0; i
< result
.size()/3; i
++)
208 // yuck - ugly or what?
209 if (result
[i
*3] == '0')
211 if (result
[i
*3+1] == '0')
213 if (result
[i
*3+2] == '0')
220 if (result
[i
*3+2] == '0')
228 if (result
[i
*3+1] == '0')
230 if (result
[i
*3+2] == '0')
237 if (result
[i
*3+2] == '0')
244 result
= octal_result
;
246 result
.insert((std::string::size_type
)0, "0");
253 // do not trim to less than 2 bits (sign plus 1-bit magnitude)
254 if (result
.size() <= 2) break;
255 // only trim if it doesn't change the sign and therefore the value
256 if (result
[0] != result
[1]) break;
259 // pad to a multiple of 4 characters
260 while (result
.size() % 4 != 0)
261 result
.insert((std::string::size_type
)0, 1, result
[0]);
262 // now convert to hex
263 std::string hex_result
;
264 for (unsigned i
= 0; i
< result
.size()/4; i
++)
266 // yuck - ugly or what?
267 if (result
[i
*4] == '0')
269 if (result
[i
*4+1] == '0')
271 if (result
[i
*4+2] == '0')
273 if (result
[i
*4+3] == '0')
280 if (result
[i
*4+3] == '0')
288 if (result
[i
*4+2] == '0')
290 if (result
[i
*4+3] == '0')
297 if (result
[i
*4+3] == '0')
306 if (result
[i
*4+1] == '0')
308 if (result
[i
*4+2] == '0')
310 if (result
[i
*4+3] == '0')
317 if (result
[i
*4+3] == '0')
325 if (result
[i
*4+2] == '0')
327 if (result
[i
*4+3] == '0')
334 if (result
[i
*4+3] == '0')
344 result
.insert((std::string::size_type
)0, "0x");
349 // convert to sign-magnitude
350 // the representation is:
352 bool negative
= local_i
.negative();
354 // create a representation of the magnitude by successive division
355 inf
inf_radix(radix
);
358 std::pair
<inf
,inf
> divided
= local_i
.divide(inf_radix
);
359 unsigned remainder
= divided
.second
.to_unsigned();
360 char digit
= to_char
[remainder
];
361 result
.insert((std::string::size_type
)0, 1, digit
);
362 local_i
= divided
.first
;
364 while(!local_i
.zero());
366 // add a sign only for negative values
368 result
.insert((std::string::size_type
)0, 1, '-');
372 ////////////////////////////////////////////////////////////////////////////////
373 // Conversions FROM string
375 void convert_from_string(const std::string
& str
, inf
& result
, unsigned radix
= 10) throw(std::invalid_argument
)
378 // only support the C-style radixes plus 0b for binary
379 // a radix of 0 means deduce the radix from the input - assume 10
380 if (radix
!= 0 && radix
!= 2 && radix
!= 8 && radix
!= 10 && radix
!= 16)
381 throw std::invalid_argument("invalid radix value");
383 // the radix passed as a parameter is just the default - it can be
384 // overridden by the C prefix
385 // Note: a leading zero is the C-style prefix for octal - I only make this
386 // override the default when the default radix is not specified
387 // first check for a C-style prefix
388 bool c_style
= false;
389 if (i
< str
.size() && str
[i
] == '0')
392 if (i
+1 < str
.size() && tolower(str
[i
+1]) == 'x')
398 else if (i
+1 < str
.size() && tolower(str
[i
+1]) == 'b')
415 // the C style formats are bit patterns not integer values - these need
416 // to be sign-extended to get the right value
420 for (unsigned j
= i
; j
< str
.size(); j
++)
431 throw std::invalid_argument("invalid binary character in string " + str
);
437 for (unsigned j
= i
; j
< str
.size(); j
++)
466 throw std::invalid_argument("invalid octal character in string " + str
);
472 for (unsigned j
= i
; j
< str
.size(); j
++)
474 switch(tolower(str
[j
]))
525 throw std::invalid_argument("invalid hex character in string " + str
);
529 // now convert the value
530 result
.resize(binary
.size());
531 for (unsigned j
= 0; j
< binary
.size(); j
++)
532 result
.preset(binary
.size() - j
- 1, binary
[j
] == '1');
536 // sign-magnitude representation
537 // now scan for a sign and find whether this is a negative number
538 bool negative
= false;
552 for (; i
< str
.size(); i
++)
554 result
*= inf(radix
);
555 unsigned char ascii
= (unsigned char)str
[i
];
556 int ch
= from_char
[ascii
] ;
558 throw std::invalid_argument("invalid decimal character in string " + str
);
566 ////////////////////////////////////////////////////////////////////////////////
567 // constructors - mostly implemented in terms of the assignment operators
571 // void constructor initialises to zero - represented as a single-byte value containing zero
572 m_data
.append(1,std::string::value_type(0));
580 inf::inf(unsigned short r
)
600 inf::inf(unsigned long r
)
605 inf::inf (const std::string
& r
) throw(std::invalid_argument
)
610 inf::inf(const inf
& r
)
613 // work round bug in Borland compiler - copy constructor fails if string
614 // contains null characters, so do my own copy
615 for (unsigned i
= 0; i
< r
.m_data
.size(); i
++)
616 m_data
+= r
.m_data
[i
];
622 ////////////////////////////////////////////////////////////////////////////////
628 ////////////////////////////////////////////////////////////////////////////////
629 // assignments convert from iteger types to internal representation
631 inf
& inf::operator = (short r
)
633 convert_from_signed(r
, m_data
);
637 inf
& inf::operator = (unsigned short r
)
639 convert_from_unsigned(r
, m_data
);
643 inf
& inf::operator = (int r
)
645 convert_from_signed(r
, m_data
);
649 inf
& inf::operator = (unsigned r
)
651 convert_from_unsigned(r
, m_data
);
655 inf
& inf::operator = (long r
)
657 convert_from_signed(r
, m_data
);
661 inf
& inf::operator = (unsigned long r
)
663 convert_from_unsigned(r
, m_data
);
667 inf
& inf::operator = (const std::string
& r
) throw(std::invalid_argument
)
669 convert_from_string(r
, *this);
673 inf
& inf::operator = (const inf
& r
)
679 ////////////////////////////////////////////////////////////////////////////////
681 short inf::to_short(bool truncate
) const throw(std::overflow_error
)
684 if (!convert_to_signed(m_data
, result
))
686 throw std::overflow_error("stlplus::inf::to_short");
690 unsigned short inf::to_unsigned_short(bool truncate
) const throw(std::overflow_error
)
692 unsigned short result
= 0;
693 if (!convert_to_unsigned(m_data
, result
))
695 throw std::overflow_error("stlplus::inf::to_unsigned_short");
699 int inf::to_int(bool truncate
) const throw(std::overflow_error
)
702 if (!convert_to_signed(m_data
, result
))
704 throw std::overflow_error("stlplus::inf::to_int");
708 unsigned inf::to_unsigned(bool truncate
) const throw(std::overflow_error
)
711 if (!convert_to_unsigned(m_data
, result
))
713 throw std::overflow_error("stlplus::inf::to_unsigned");
717 long inf::to_long(bool truncate
) const throw(std::overflow_error
)
720 if (!convert_to_signed(m_data
, result
))
722 throw std::overflow_error("stlplus::inf::to_long");
726 unsigned long inf::to_unsigned_long(bool truncate
) const throw(std::overflow_error
)
728 unsigned long result
= 0;
729 if (!convert_to_unsigned(m_data
, result
))
731 throw std::overflow_error("stlplus::inf::to_unsigned_long");
735 ////////////////////////////////////////////////////////////////////////////////
736 // resize the inf regardless of the data
738 void inf::resize(unsigned bits
)
740 if (bits
== 0) bits
= 1;
741 unsigned bytes
= (bits
+7)/8;
742 byte extend
= negative() ? byte(255) : byte (0);
743 while(bytes
> m_data
.size())
744 m_data
.append(1,extend
);
747 // reduce the bit count to the minimum needed to preserve the value
749 void inf::reduce(void)
751 reduce_string(m_data
);
754 ////////////////////////////////////////////////////////////////////////////////
755 // the number of significant bits in the number
757 unsigned inf::bits (void) const
759 // The number of significant bits in the integer value - this is the number
760 // of indexable bits less any redundant sign bits at the msb
761 // This does not assume that the inf has been reduced to its minimum form
762 unsigned result
= indexable_bits();
763 bool sign
= bit(result
-1);
764 while (result
> 1 && (sign
== bit(result
-2)))
769 unsigned inf::size(void) const
774 unsigned inf::indexable_bits (void) const
776 return 8 * unsigned(m_data
.size());
779 ////////////////////////////////////////////////////////////////////////////////
780 // bitwise operations
782 bool inf::bit (unsigned index
) const throw(std::out_of_range
)
784 if (index
>= indexable_bits())
785 throw std::out_of_range(std::string("stlplus::inf::bit"));
786 // first split the offset into byte offset and bit offset
787 unsigned byte_offset
= index
/8;
788 unsigned bit_offset
= index%8
;
789 return (byte(m_data
[byte_offset
]) & (byte(1) << bit_offset
)) != 0;
792 bool inf::operator [] (unsigned index
) const throw(std::out_of_range
)
797 void inf::set (unsigned index
) throw(std::out_of_range
)
799 if (index
>= indexable_bits())
800 throw std::out_of_range(std::string("stlplus::inf::set"));
801 // first split the offset into byte offset and bit offset
802 unsigned byte_offset
= index
/8;
803 unsigned bit_offset
= index%8
;
804 m_data
[byte_offset
] |= (byte(1) << bit_offset
);
807 void inf::clear (unsigned index
) throw(std::out_of_range
)
809 if (index
>= indexable_bits())
810 throw std::out_of_range(std::string("stlplus::inf::clear"));
811 // first split the offset into byte offset and bit offset
812 unsigned byte_offset
= index
/8;
813 unsigned bit_offset
= index%8
;
814 m_data
[byte_offset
] &= (~(byte(1) << bit_offset
));
817 void inf::preset (unsigned index
, bool value
) throw(std::out_of_range
)
825 inf
inf::slice(unsigned low
, unsigned high
) const throw(std::out_of_range
)
827 if (low
>= indexable_bits())
828 throw std::out_of_range(std::string("stlplus::inf::slice: low index"));
829 if (high
>= indexable_bits())
830 throw std::out_of_range(std::string("stlplus::inf::slice: high index"));
834 // create a result the right size and filled with sign bits
835 std::string::size_type result_size
= (high
-low
+1+7)/8;
836 result
.m_data
.erase();
837 byte extend
= bit(high
) ? byte(255) : byte (0);
838 while (result
.m_data
.size() < result_size
)
839 result
.m_data
.append(1,extend
);
840 // now set the relevant bits
841 for (unsigned i
= low
; i
<= high
; i
++)
842 result
.preset(i
-low
, bit(i
));
847 ////////////////////////////////////////////////////////////////////////////////
848 // testing operations
850 bool inf::negative (void) const
852 return bit(indexable_bits()-1);
855 bool inf::natural (void) const
860 bool inf::positive (void) const
862 return natural() && !zero();
865 bool inf::zero (void) const
867 for (std::string::size_type i
= 0; i
< m_data
.size(); i
++)
873 bool inf::non_zero (void) const
878 bool inf::operator ! (void) const
883 ////////////////////////////////////////////////////////////////////////////////
884 // comparison operators
886 bool inf::operator == (const inf
& r
) const
888 // Two infs are equal if they are numerically equal, even if they are
889 // different sizes (i.e. they could be non-reduced values).
890 // This makes life a little more complicated than if I could assume that values were reduced.
891 byte l_extend
= negative() ? byte(255) : byte (0);
892 byte r_extend
= r
.negative() ? byte(255) : byte (0);
893 std::string::size_type bytes
= maximum(m_data
.size(),r
.m_data
.size());
894 for (std::string::size_type i
= bytes
; i
--; )
896 byte l_byte
= (i
< m_data
.size() ? byte(m_data
[i
]) : l_extend
);
897 byte r_byte
= (i
< r
.m_data
.size() ? byte(r
.m_data
[i
]) : r_extend
);
898 if (l_byte
!= r_byte
)
904 bool inf::operator != (const inf
& r
) const
906 return !operator==(r
);
909 bool inf::operator < (const inf
& r
) const
911 // This could be implemented in terms of subtraction. However, it can be
912 // simplified since there is no need to calculate the accurate difference,
913 // just the direction of the difference. I compare from msB down and as
914 // soon as a byte difference is found, that defines the ordering. The
915 // problem is that in 2's-complement, all negative values are greater than
916 // all natural values if you just do a straight unsigned comparison. I
917 // handle this by doing a preliminary test for different signs.
919 // For example, a 3-bit signed type has the coding:
927 // So, for natural values, the ordering of the integer values is the
928 // ordering of the bit patterns. Similarly, for negative values, the
929 // ordering of the integer values is the ordering of the bit patterns
930 // However, the bit patterns for the negative values are *greater than*
931 // the natural values. This is a side-effect of the naffness of
932 // 2's-complement representation
934 // first handle the case of comparing two values with different signs
935 bool l_sign
= negative();
936 bool r_sign
= r
.negative();
937 if (l_sign
!= r_sign
)
939 // one argument must be negative and the other natural
940 // the left is less if it is the negative one
943 // the arguments are the same sign
944 // so the ordering is a simple unsigned byte-by-byte comparison
945 // However, this is complicated by the possibility that the values could be different lengths
946 byte l_extend
= l_sign
? byte(255) : byte (0);
947 byte r_extend
= r_sign
? byte(255) : byte (0);
948 std::string::size_type bytes
= maximum(m_data
.size(),r
.m_data
.size());
949 for (std::string::size_type i
= bytes
; i
--; )
951 byte l_byte
= (i
< m_data
.size() ? byte(m_data
[i
]) : l_extend
);
952 byte r_byte
= (i
< r
.m_data
.size() ? byte(r
.m_data
[i
]) : r_extend
);
953 if (l_byte
!= r_byte
)
954 return l_byte
< r_byte
;
956 // if I get here, the two are equal, so that is not less-than
960 bool inf::operator <= (const inf
& r
) const
965 bool inf::operator > (const inf
& r
) const
970 bool inf::operator >= (const inf
& r
) const
975 ////////////////////////////////////////////////////////////////////////////////
978 inf
& inf::invert (void)
980 for (std::string::size_type i
= 0; i
< m_data
.size(); i
++)
981 m_data
[i
] = ~m_data
[i
];
985 inf
inf::operator ~ (void) const
992 inf
& inf::operator &= (const inf
& r
)
994 // bitwise AND is extended to the length of the largest argument
995 byte l_extend
= negative() ? byte(255) : byte (0);
996 byte r_extend
= r
.negative() ? byte(255) : byte (0);
997 std::string::size_type bytes
= maximum(m_data
.size(),r
.m_data
.size());
998 for (std::string::size_type i
= 0; i
< bytes
; i
++)
1000 byte l_byte
= (i
< m_data
.size() ? byte(m_data
[i
]) : l_extend
);
1001 byte r_byte
= (i
< r
.m_data
.size() ? byte(r
.m_data
[i
]) : r_extend
);
1002 byte result
= l_byte
& r_byte
;
1003 if (i
< m_data
.size())
1006 m_data
.append(1,result
);
1008 // now reduce the result
1013 inf
inf::operator & (const inf
& r
) const
1020 inf
& inf::operator |= (const inf
& r
)
1022 // bitwise OR is extended to the length of the largest argument
1023 byte l_extend
= negative() ? byte(255) : byte (0);
1024 byte r_extend
= r
.negative() ? byte(255) : byte (0);
1025 std::string::size_type bytes
= maximum(m_data
.size(),r
.m_data
.size());
1026 for (std::string::size_type i
= 0; i
< bytes
; i
++)
1028 byte l_byte
= (i
< m_data
.size() ? byte(m_data
[i
]) : l_extend
);
1029 byte r_byte
= (i
< r
.m_data
.size() ? byte(r
.m_data
[i
]) : r_extend
);
1030 byte result
= l_byte
| r_byte
;
1031 if (i
< m_data
.size())
1034 m_data
.append(1,result
);
1036 // now reduce the result
1041 inf
inf::operator | (const inf
& r
) const
1048 inf
& inf::operator ^= (const inf
& r
)
1050 // bitwise XOR is extended to the length of the largest argument
1051 byte l_extend
= negative() ? byte(255) : byte (0);
1052 byte r_extend
= r
.negative() ? byte(255) : byte (0);
1053 std::string::size_type bytes
= maximum(m_data
.size(),r
.m_data
.size());
1054 for (std::string::size_type i
= 0; i
< bytes
; i
++)
1056 byte l_byte
= (i
< m_data
.size() ? byte(m_data
[i
]) : l_extend
);
1057 byte r_byte
= (i
< r
.m_data
.size() ? byte(r
.m_data
[i
]) : r_extend
);
1058 byte result
= l_byte
^ r_byte
;
1059 if (i
< m_data
.size())
1062 m_data
.append(1,result
);
1064 // now reduce the result
1069 inf
inf::operator ^ (const inf
& r
) const
1076 ////////////////////////////////////////////////////////////////////////////////
1077 // shift operators all preserve the value by increasing the word size
1079 inf
& inf::operator <<= (unsigned shift
)
1081 // left shift is a shift towards the msb, with 0s being shifted in at the lsb
1082 // split this into a byte shift followed by a bit shift
1084 // first expand the value to be big enough for the result
1085 std::string::size_type new_size
= (indexable_bits() + shift
+ 7) / 8;
1086 byte extend
= negative() ? byte(255) : byte (0);
1087 while (m_data
.size() < new_size
)
1088 m_data
.append(1,extend
);
1089 // now do the byte shift
1090 unsigned byte_shift
= shift
/8;
1093 for (std::string::size_type b
= new_size
; b
--; )
1094 m_data
[b
] = (b
>= byte_shift
) ? m_data
[b
-byte_shift
] : byte(0);
1096 // and finally the bit shift
1097 unsigned bit_shift
= shift%8
;
1100 for (std::string::size_type b
= new_size
; b
--; )
1102 byte current
= byte(m_data
[b
]);
1103 byte previous
= b
> 0 ? m_data
[b
-1] : byte(0);
1104 m_data
[b
] = (current
<< bit_shift
) | (previous
>> (8 - bit_shift
));
1107 // now reduce the result
1112 inf
inf::operator << (unsigned shift
) const
1119 inf
& inf::operator >>= (unsigned shift
)
1121 // right shift is a shift towards the lsb, with sign bits being shifted in at the msb
1122 // split this into a byte shift followed by a bit shift
1124 // a byte of sign bits
1125 byte extend
= negative() ? byte(255) : byte (0);
1126 // do the byte shift
1127 unsigned byte_shift
= shift
/8;
1130 for (std::string::size_type b
= 0; b
< m_data
.size(); b
++)
1131 m_data
[b
] = (b
+ byte_shift
< m_data
.size()) ? m_data
[b
+byte_shift
] : extend
;
1133 // and finally the bit shift
1134 unsigned bit_shift
= shift%8
;
1137 for (std::string::size_type b
= 0; b
< m_data
.size(); b
++)
1139 byte current
= byte(m_data
[b
]);
1140 byte next
= ((b
+1) < m_data
.size()) ? m_data
[b
+1] : extend
;
1141 byte shifted
= (current
>> bit_shift
) | (next
<< (8 - bit_shift
));
1142 m_data
[b
] = shifted
;
1145 // now reduce the result
1150 inf
inf::operator >> (unsigned shift
) const
1157 ////////////////////////////////////////////////////////////////////////////////
1158 // negation operators
1160 inf
& inf::negate (void)
1162 // do 2's-complement negation
1163 // equivalent to inversion plus one
1165 operator += (inf(1));
1169 inf
inf::operator - (void) const
1178 if (negative()) negate();
1182 inf
abs(const inf
& i
)
1189 ////////////////////////////////////////////////////////////////////////////////
1190 // addition operators
1192 inf
& inf::operator += (const inf
& r
)
1194 // do 2's-complement addition
1195 // Note that the addition can give a result that is larger than either argument
1197 std::string::size_type max_size
= maximum(m_data
.size(),r
.m_data
.size());
1198 byte l_extend
= negative() ? byte(255) : byte (0);
1199 byte r_extend
= r
.negative() ? byte(255) : byte (0);
1200 for (std::string::size_type i
= 0; i
< max_size
; i
++)
1202 byte l_byte
= (i
< m_data
.size() ? byte(m_data
[i
]) : l_extend
);
1203 byte r_byte
= (i
< r
.m_data
.size() ? byte(r
.m_data
[i
]) : r_extend
);
1204 // calculate the addition in a type that is bigger than a byte in order to catch the carry-out
1205 unsigned short result
= ((unsigned short)(l_byte
)) + ((unsigned short)(r_byte
)) + carry
;
1206 // now truncate the result to get the lsB
1207 if (i
< m_data
.size())
1208 m_data
[i
] = byte(result
);
1210 m_data
.append(1,byte(result
));
1211 // and capture the carry out by grabbing the second byte of the result
1212 carry
= byte(result
>> 8);
1214 // if the result overflowed or underflowed, add an extra byte to catch it
1215 unsigned short result
= ((unsigned short)(l_extend
)) + ((unsigned short)(r_extend
)) + carry
;
1216 if (byte(result
) != (negative() ? byte(255) : byte(0)))
1217 m_data
.append(1,byte(result
));
1218 // now reduce the result
1223 inf
inf::operator + (const inf
& r
) const
1230 ////////////////////////////////////////////////////////////////////////////////
1231 // subtraction operators
1233 inf
& inf::operator -= (const inf
& r
)
1235 // subtraction is defined in terms of negation and addition
1237 operator += (negated
);
1241 inf
inf::operator - (const inf
& r
) const
1248 ////////////////////////////////////////////////////////////////////////////////
1249 // multiplication operators
1251 inf
& inf::operator *= (const inf
& r
)
1253 // 2's complement multiplication
1254 // one day I'll do a more efficient version than this based on the underlying representation
1257 // make the right value natural but preserve its sign for later
1258 bool right_negative
= right
.negative();
1260 // implemented as a series of conditional additions
1262 // left.resize(right.bits() + left.bits() - 1);
1263 left
<<= right
.bits()-1;
1264 for (unsigned i
= right
.bits(); i
--; )
1272 // now reduce the result
1277 inf
inf::operator * (const inf
& r
) const
1284 ////////////////////////////////////////////////////////////////////////////////
1285 // division and remainder operators
1287 std::pair
<inf
,inf
> inf::divide(const inf
& right
) const throw(divide_by_zero
)
1290 throw divide_by_zero("stlplus::inf::divide");
1291 inf
numerator(*this);
1292 inf denominator
= right
;
1293 // make the numerator natural but preserve the sign for later
1294 bool numerator_negative
= numerator
.negative();
1296 // same with the denominator
1297 bool denominator_negative
= denominator
.negative();
1299 // the quotient and remainder will form the result
1300 // start with the quotiont zero and the remainder equal to the whole of the
1301 // numerator, then do trial subtraction from this
1303 inf remainder
= numerator
;
1304 // there's nothing more to do if the numerator is smaller than the denominator
1305 // but otherwise do the division
1306 if (numerator
.bits() >= denominator
.bits())
1308 // make the quotient big enough to take the result
1309 quotient
.resize(numerator
.bits());
1310 // start with the numerator shifted to the far left
1311 unsigned shift
= numerator
.bits() - denominator
.bits();
1312 denominator
<<= shift
;
1313 // do the division by repeated subtraction,
1314 for (unsigned i
= shift
+1; i
--; )
1316 if (remainder
>= denominator
)
1318 remainder
-= denominator
;
1324 // now adjust the signs
1325 // x/(-y) == (-x)/y == -(x/y)
1326 if (numerator_negative
!= denominator_negative
)
1329 // x%(-y) == x%y and (-x)%y == -(x%y)
1330 if (numerator_negative
)
1333 return std::pair
<inf
,inf
>(quotient
,remainder
);
1336 inf
& inf::operator /= (const inf
& r
) throw(divide_by_zero
)
1338 std::pair
<inf
,inf
> result
= divide(r
);
1339 operator=(result
.first
);
1343 inf
inf::operator / (const inf
& r
) const throw(divide_by_zero
)
1345 std::pair
<inf
,inf
> result
= divide(r
);
1346 return result
.first
;
1349 inf
& inf::operator %= (const inf
& r
) throw(divide_by_zero
)
1351 std::pair
<inf
,inf
> result
= divide(r
);
1352 operator=(result
.second
);
1356 inf
inf::operator % (const inf
& r
) const throw(divide_by_zero
)
1358 std::pair
<inf
,inf
> result
= divide(r
);
1359 return result
.second
;
1362 ////////////////////////////////////////////////////////////////////////////////
1363 // prefix (void) and postfix (int) operators
1365 inf
& inf::operator ++ (void)
1367 operator += (inf(1));
1371 inf
inf::operator ++ (int)
1374 operator += (inf(1));
1378 inf
& inf::operator -- (void)
1380 operator -= (inf(1));
1384 inf
inf::operator -- (int)
1387 operator -= (inf(1));
1391 ////////////////////////////////////////////////////////////////////////////////
1392 // string representation and I/O routines
1394 std::string
inf::to_string(unsigned radix
) const
1395 throw(std::invalid_argument
)
1398 convert_to_string(*this, result
, radix
);
1402 inf
& inf::from_string(const std::string
& value
, unsigned radix
)
1403 throw(std::invalid_argument
)
1405 convert_from_string(value
, *this, radix
);
1409 std::ostream
& operator << (std::ostream
& str
, const inf
& i
)
1414 unsigned radix
= 10;
1415 if (str
.flags() & std::ios_base::oct
)
1417 if (str
.flags() & std::ios_base::hex
)
1419 // the field width is handled by iostream, so I don't need to handle it as well
1420 // generate the string representation then print it
1421 str
<< i
.to_string(radix
);
1423 catch(const std::invalid_argument
)
1425 str
.setstate(std::ios_base::badbit
);
1430 std::istream
& operator >> (std::istream
& str
, inf
& i
)
1435 unsigned radix
= 10;
1436 if (str
.flags() & std::ios_base::oct
)
1438 if (str
.flags() & std::ios_base::hex
)
1440 // now get the string image of the value
1443 // and convert to inf
1444 i
.from_string(image
, radix
);
1446 catch(const std::invalid_argument
)
1448 str
.setstate(std::ios_base::badbit
);
1453 ////////////////////////////////////////////////////////////////////////////////
1455 // just convert to hex
1457 std::string
inf::image_debug(void) const
1459 // create this dump in the human-readable form, i.e. msB to the left
1460 std::string result
= "0x";
1461 for (std::string::size_type i
= m_data
.size(); i
--; )
1463 byte current
= m_data
[i
];
1464 byte msB
= (current
& byte(0xf0)) >> 4;
1465 result
+= to_char
[msB
];
1466 byte lsB
= (current
& byte(0x0f));
1467 result
+= to_char
[lsB
];
1472 const std::string
& inf::get_bytes(void) const
1477 void inf::set_bytes(const std::string
& data
)
1482 } // end namespace stlplus
This page took 0.102325 seconds and 3 git commands to generate.