| 1 | // vint_small.hpp, created on 01.12.2008 by Sebastian Mies
|
---|
| 2 | // [The FreeBSD Licence]
|
---|
| 3 | //
|
---|
| 4 | // Copyright (c) 2008
|
---|
| 5 | // Sebastian Mies, Institute of Telematics, UniversitÀt Karlsruhe (TH)
|
---|
| 6 | // All rights reserved.
|
---|
| 7 | //
|
---|
| 8 | // Redistribution and use in source and binary forms, with or without
|
---|
| 9 | // modification, are permitted provided that the following conditions are
|
---|
| 10 | // met:
|
---|
| 11 | //
|
---|
| 12 | // * Redistributions of source code must retain the above copyright notice,
|
---|
| 13 | // this list of conditions and the following disclaimer.
|
---|
| 14 | // * Redistributions in binary form must reproduce the above copyright
|
---|
| 15 | // notice, this list of conditions and the following disclaimer in the
|
---|
| 16 | // documentation and/or other materials provided with the distribution.
|
---|
| 17 | // * Neither the name of the author nor the names of its contributors may be
|
---|
| 18 | // used to endorse or promote products derived from this software without
|
---|
| 19 | // specific prior written permission.
|
---|
| 20 | //
|
---|
| 21 | // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
|
---|
| 22 | // IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
|
---|
| 23 | // THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
|
---|
| 24 | // PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
|
---|
| 25 | // CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
|
---|
| 26 | // EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
|
---|
| 27 | // PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;
|
---|
| 28 | // OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
|
---|
| 29 | // WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
|
---|
| 30 | // OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
|
---|
| 31 | // ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
|
---|
| 32 | //
|
---|
| 33 |
|
---|
| 34 | #ifndef VINT_SMALL_HPP_
|
---|
| 35 | #define VINT_SMALL_HPP_
|
---|
| 36 |
|
---|
| 37 | #include<boost/mpl/if.hpp>
|
---|
| 38 | #include<boost/integer.hpp>
|
---|
| 39 |
|
---|
| 40 | #include "helper.hpp"
|
---|
| 41 | #include <cmath>
|
---|
| 42 |
|
---|
| 43 | #define NO_INT64
|
---|
| 44 |
|
---|
| 45 | using boost::mpl::if_;
|
---|
| 46 | using boost::mpl::bool_;
|
---|
| 47 |
|
---|
| 48 | namespace _vint {
|
---|
| 49 | namespace detail {
|
---|
| 50 | template<size_t l, bool s> class vint_small;
|
---|
| 51 | }} // namespace _vint::detail
|
---|
| 52 |
|
---|
| 53 | template<size_t l, bool s>
|
---|
| 54 | std::ostream& operator<<(std::ostream& os, const _vint::detail::vint_small<l, s>& v);
|
---|
| 55 |
|
---|
| 56 | namespace _vint {
|
---|
| 57 | namespace detail {
|
---|
| 58 |
|
---|
| 59 | /**
|
---|
| 60 | * This class implements a integer wrapper for native integer types
|
---|
| 61 | * and adapts it to integers which do not have a length divideable by
|
---|
| 62 | * a power of 2. In this case bits are masked out to mimic the behaviour
|
---|
| 63 | * of a real variable small integer.
|
---|
| 64 | *
|
---|
| 65 | * SIGNED values are currently unsupported!!!
|
---|
| 66 | *
|
---|
| 67 | * @autor Sebastian Mies
|
---|
| 68 | */
|
---|
| 69 | template<size_t __length = 0, bool __sign = false>
|
---|
| 70 | class vint_small {
|
---|
| 71 | friend std::ostream& operator<< <__length, __sign> (std::ostream&,
|
---|
| 72 | const vint_small<__length, __sign>&);
|
---|
| 73 | private:
|
---|
| 74 | /* selection of integer type (beware: nasty mpl stuff :) */
|
---|
| 75 | typedef
|
---|
| 76 | #ifndef NO_INT64
|
---|
| 77 | typename if_<
|
---|
| 78 | bool_<(__length> 32 && __length <= 64)>,
|
---|
| 79 | typename if_<bool_<__sign>, boost::int64_t, boost::uint64_t>::type,
|
---|
| 80 | #endif
|
---|
| 81 | #ifndef NO_INT32
|
---|
| 82 | typename if_<
|
---|
| 83 | bool_<(__length> 16 && __length <= 32)>,
|
---|
| 84 | typename if_<bool_<__sign>, boost::int32_t, boost::uint32_t>::type,
|
---|
| 85 | #endif
|
---|
| 86 | typename if_<
|
---|
| 87 | bool_<(__length> 8 && __length <= 16)>,
|
---|
| 88 | typename if_<bool_<__sign>, boost::int16_t, boost::uint16_t>::type,
|
---|
| 89 | typename if_<
|
---|
| 90 | bool_<(__length> 0 && __length <= 8)>,
|
---|
| 91 | typename if_<bool_<__sign>, boost::int8_t, boost::uint8_t>::type,
|
---|
| 92 | void
|
---|
| 93 | > ::type
|
---|
| 94 | #ifndef NO_INT32
|
---|
| 95 | > ::type
|
---|
| 96 | #endif
|
---|
| 97 | #ifndef NO_INT64
|
---|
| 98 | > ::type
|
---|
| 99 | #endif
|
---|
| 100 | > ::type type;
|
---|
| 101 |
|
---|
| 102 | /* THE actual value */
|
---|
| 103 | type value;
|
---|
| 104 |
|
---|
| 105 | /* this method trims an integer if neccessary */
|
---|
| 106 | finline void trim() {
|
---|
| 107 | value &= (((type)1) << __length) - 1;
|
---|
| 108 | }
|
---|
| 109 |
|
---|
| 110 | /* our internal small int */
|
---|
| 111 | typedef vint_small<__length,__sign> _self;
|
---|
| 112 | public:
|
---|
| 113 | finline vint_small() {
|
---|
| 114 | value = 0;
|
---|
| 115 | }
|
---|
| 116 |
|
---|
| 117 | finline vint_small( const type& value ) {
|
---|
| 118 | this->value = value;
|
---|
| 119 | trim();
|
---|
| 120 | }
|
---|
| 121 |
|
---|
| 122 | finline vint_small(const char* text, int base = 10) {
|
---|
| 123 | assign(std::string(text),base);
|
---|
| 124 | }
|
---|
| 125 |
|
---|
| 126 | //-- conversion -----------------------------------------------------------
|
---|
| 127 |
|
---|
| 128 | template<class T>
|
---|
| 129 | finline void convert_to( T& v, if_integral(T) ) const {
|
---|
| 130 | v = (T)value;
|
---|
| 131 | }
|
---|
| 132 |
|
---|
| 133 | finline std::string to_string(int base = 10,
|
---|
| 134 | int str_size = 0, char str_fill = '0') const {
|
---|
| 135 |
|
---|
| 136 | // convert to another base
|
---|
| 137 | std::string s = "\0";
|
---|
| 138 | int last_non_zero = 0;
|
---|
| 139 | int last = 0;
|
---|
| 140 | type _val = value;
|
---|
| 141 |
|
---|
| 142 | while (_val != 0) {
|
---|
| 143 | // divide by base
|
---|
| 144 | type rem = _val % base;
|
---|
| 145 | type _div = _val / base;
|
---|
| 146 |
|
---|
| 147 | // set char
|
---|
| 148 | s += (char) rem;
|
---|
| 149 | if (rem != 0) last_non_zero = last;
|
---|
| 150 | last++;
|
---|
| 151 |
|
---|
| 152 | // divided value as new
|
---|
| 153 | _val = _div;
|
---|
| 154 | }
|
---|
| 155 | last = last_non_zero + 1;
|
---|
| 156 |
|
---|
| 157 | // reverse
|
---|
| 158 | for (int i = 0; i < last / 2; i++) {
|
---|
| 159 | char dummy = s[i];
|
---|
| 160 | s[i] = s[last - i - 1];
|
---|
| 161 | s[last - i - 1] = (int) dummy;
|
---|
| 162 | }
|
---|
| 163 |
|
---|
| 164 | // convert string
|
---|
| 165 | s.resize(last);
|
---|
| 166 | for (int i = 0; i < last; i++)
|
---|
| 167 | s[i] = ("0123456789ABCDEF")[(int) s[i]];
|
---|
| 168 |
|
---|
| 169 | // add leading zeros
|
---|
| 170 | if (last < str_size) {
|
---|
| 171 | char zeros[str_size - last+1];
|
---|
| 172 | memset(zeros, str_fill, str_size - last);
|
---|
| 173 | zeros[str_size - last] = 0;
|
---|
| 174 | return std::string(zeros) + s;
|
---|
| 175 | } else {
|
---|
| 176 | return s;
|
---|
| 177 | }
|
---|
| 178 | }
|
---|
| 179 |
|
---|
| 180 | std::string to_debug_string(int base = 10,
|
---|
| 181 | int str_size = 0, char str_fill = '0') const {
|
---|
| 182 | std::ostringstream str;
|
---|
| 183 | str << "vint_small(static,";
|
---|
| 184 | str << "length=" << __length << ",";
|
---|
| 185 | str << "mem=" << sizeof(*this) << ",";
|
---|
| 186 | str << "val=" << to_string(base, str_size, str_fill) << ")";
|
---|
| 187 | return str.str();
|
---|
| 188 | }
|
---|
| 189 |
|
---|
| 190 | //-- sub integers ---------------------------------------------------------
|
---|
| 191 |
|
---|
| 192 | finline bool get_bit(size_t index) const {
|
---|
| 193 | return false;
|
---|
| 194 | }
|
---|
| 195 |
|
---|
| 196 | finline void set_bit(size_t index, bool v) {
|
---|
| 197 | }
|
---|
| 198 |
|
---|
| 199 | finline void set_subint(_self& v, size_t index) {
|
---|
| 200 | }
|
---|
| 201 |
|
---|
| 202 | finline void set_subint(uintmax_t v, size_t index) {
|
---|
| 203 | }
|
---|
| 204 |
|
---|
| 205 | finline _self get_subint(size_t index, size_t length) const {
|
---|
| 206 | }
|
---|
| 207 |
|
---|
| 208 | finline uintmax_t get_subint(size_t index) const {
|
---|
| 209 | return 0;
|
---|
| 210 | }
|
---|
| 211 |
|
---|
| 212 | //-- assignment -----------------------------------------------------------
|
---|
| 213 |
|
---|
| 214 | template<typename T>
|
---|
| 215 | finline void assign(const T& v, if_integral(T) ) {
|
---|
| 216 | value = v;
|
---|
| 217 | }
|
---|
| 218 |
|
---|
| 219 | finline void assign(const std::string& text, int base = 10) {
|
---|
| 220 | int x;
|
---|
| 221 | sscanf(text.c_str(), "%d", &x);
|
---|
| 222 | value = x;
|
---|
| 223 | }
|
---|
| 224 |
|
---|
| 225 | //-- compare operations ---------------------------------------------------
|
---|
| 226 |
|
---|
| 227 | finline int compare_to(const _self& v) const {
|
---|
| 228 | return (int)(value-v.value);
|
---|
| 229 | }
|
---|
| 230 |
|
---|
| 231 | template<class T>
|
---|
| 232 | finline int compare_to(const T& v, if_integral(T) ) const {
|
---|
| 233 | return (int)(value-v);
|
---|
| 234 | }
|
---|
| 235 |
|
---|
| 236 | //-- integer arithmetic ---------------------------------------------------
|
---|
| 237 |
|
---|
| 238 | // addition
|
---|
| 239 | template<class T>
|
---|
| 240 | finline void add(const T& rhs, if_integral(T) ) {
|
---|
| 241 | value += rhs; trim();
|
---|
| 242 | }
|
---|
| 243 |
|
---|
| 244 | finline void add(const _self& rhs) {
|
---|
| 245 | value += rhs.value; trim();
|
---|
| 246 | }
|
---|
| 247 |
|
---|
| 248 | // subtraction
|
---|
| 249 | template<class T>
|
---|
| 250 | finline void sub(const T& rhs, if_integral(T) ) {
|
---|
| 251 | value -= rhs; trim();
|
---|
| 252 | }
|
---|
| 253 |
|
---|
| 254 | finline void sub(const _self& rhs) {
|
---|
| 255 | value -= rhs.value; trim();
|
---|
| 256 | }
|
---|
| 257 |
|
---|
| 258 | // multiplication
|
---|
| 259 | template<class T>
|
---|
| 260 | finline void mul(const T& rhs, if_integral(T) ) {
|
---|
| 261 | value *= rhs; trim();
|
---|
| 262 | }
|
---|
| 263 |
|
---|
| 264 | finline void mul(const _self& rhs) {
|
---|
| 265 | value *= rhs.value; trim();
|
---|
| 266 | }
|
---|
| 267 |
|
---|
| 268 | finline void mul(_self& res_l, _self& res_h, _self& rhs) {
|
---|
| 269 | res_l.value = rhs.value * value;
|
---|
| 270 | res_h.value = (rhs.value >> __length) * value;
|
---|
| 271 | }
|
---|
| 272 |
|
---|
| 273 | // modulo
|
---|
| 274 | template<class T>
|
---|
| 275 | finline void mod(const T& rhs, if_integral(T) ) {
|
---|
| 276 | value %= rhs; trim();
|
---|
| 277 | }
|
---|
| 278 |
|
---|
| 279 | finline void mod( const _self& rhs ) {
|
---|
| 280 | value %= rhs.value; trim();
|
---|
| 281 | }
|
---|
| 282 |
|
---|
| 283 | finline void mod( _self& res, const _self& rhs ) {
|
---|
| 284 | res.value = value % rhs.value; res.trim();
|
---|
| 285 | }
|
---|
| 286 |
|
---|
| 287 | // exception to modulo
|
---|
| 288 | template<class T>
|
---|
| 289 | finline void mod( T& res, const T& rhs, if_integral(T) ) const {
|
---|
| 290 | res = value % rhs;
|
---|
| 291 | }
|
---|
| 292 |
|
---|
| 293 | // division
|
---|
| 294 | template<class T>
|
---|
| 295 | finline void div( const T& rhs, if_integral(T) ) {
|
---|
| 296 | value /= rhs; trim();
|
---|
| 297 | }
|
---|
| 298 |
|
---|
| 299 | finline void div( const _self& rhs ) {
|
---|
| 300 | value /= rhs.value; trim();
|
---|
| 301 | }
|
---|
| 302 |
|
---|
| 303 | finline void div( _self& res, const _self& rhs ) {
|
---|
| 304 | res.value = value / rhs.value; res.trim();
|
---|
| 305 | }
|
---|
| 306 |
|
---|
| 307 | // division with remainder
|
---|
| 308 | template<class T>
|
---|
| 309 | finline void divrem(_self& res_div, _self& res_rem, const T& rhs, if_integral(T)) {
|
---|
| 310 | res_div.value = value / rhs;
|
---|
| 311 | res_rem.value = value % rhs;
|
---|
| 312 | }
|
---|
| 313 |
|
---|
| 314 | finline void divrem(_self& res_rem, const _self& rhs) {
|
---|
| 315 | value = value / rhs.value;
|
---|
| 316 | res_rem.value = value % rhs.value;
|
---|
| 317 | }
|
---|
| 318 |
|
---|
| 319 | finline void divrem(_self& res_div, _self& res_rem, const _self& rhs) {
|
---|
| 320 | res_div.value = value / rhs.value;
|
---|
| 321 | res_rem.value = value % rhs.value;
|
---|
| 322 | }
|
---|
| 323 |
|
---|
| 324 | // exception to division with remainder
|
---|
| 325 | template<class T>
|
---|
| 326 | finline void divrem(_self& res_div, T& res_rem, const T& rhs, if_integral(T)) {
|
---|
| 327 | res_div.value = value / rhs;
|
---|
| 328 | res_rem = value % rhs;
|
---|
| 329 | }
|
---|
| 330 |
|
---|
| 331 | // logarithm to the base of 2
|
---|
| 332 | finline uintmax_t log2() const {
|
---|
| 333 | return ::log2(value);
|
---|
| 334 | }
|
---|
| 335 |
|
---|
| 336 | //-- logical bit operations -----------------------------------------------
|
---|
| 337 |
|
---|
| 338 | finline void or_ (const _self& rhs) {value |= rhs.value;}
|
---|
| 339 | finline void and_(const _self& rhs) {value &= rhs.value;}
|
---|
| 340 | finline void xor_(const _self& rhs) {value ^= rhs.value;}
|
---|
| 341 | finline void complement() {value = ~value; trim();}
|
---|
| 342 | finline void lshift(size_t steps) {value <<= steps; trim();}
|
---|
| 343 | finline void rshift(size_t steps) {value >>= steps; trim();}
|
---|
| 344 |
|
---|
| 345 | //-- integer dynamic ------------------------------------------------------
|
---|
| 346 |
|
---|
| 347 | // inline vint<0, __sign> normalized() const { return value.normalized(); }
|
---|
| 348 |
|
---|
| 349 | //-- general information --------------------------------------------------
|
---|
| 350 |
|
---|
| 351 | finline size_t length() const {return __length;}
|
---|
| 352 | finline void set_length(size_t length) {}
|
---|
| 353 | finline bool is_unspecified() {return false;}
|
---|
| 354 |
|
---|
| 355 | finline _self max() const {return ~(type)0;}
|
---|
| 356 | finline _self min() const {return (type)0;}
|
---|
| 357 | finline _self zero() const {return (type)0;}
|
---|
| 358 | };
|
---|
| 359 |
|
---|
| 360 | }} // namespace _vint::detail
|
---|
| 361 |
|
---|
| 362 | template<size_t l, bool s>
|
---|
| 363 | std::ostream& operator<<(std::ostream& os, const _vint::detail::vint_small<l, s>& v) {
|
---|
| 364 | return os << v.to_string();
|
---|
| 365 | }
|
---|
| 366 |
|
---|
| 367 | #endif /* VINT_SMALL_HPP_ */
|
---|