1 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */ 2 /* 3 * Main authors: 4 * Christian Schulte <schulte@gecode.org> 5 * 6 * Copyright: 7 * Christian Schulte, 2005 8 * 9 * This file is part of Gecode, the generic constraint 10 * development environment: 11 * http://www.gecode.org 12 * 13 * Permission is hereby granted, free of charge, to any person obtaining 14 * a copy of this software and associated documentation files (the 15 * "Software"), to deal in the Software without restriction, including 16 * without limitation the rights to use, copy, modify, merge, publish, 17 * distribute, sublicense, and/or sell copies of the Software, and to 18 * permit persons to whom the Software is furnished to do so, subject to 19 * the following conditions: 20 * 21 * The above copyright notice and this permission notice shall be 22 * included in all copies or substantial portions of the Software. 23 * 24 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 25 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 26 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 27 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE 28 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION 29 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION 30 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. 31 * 32 */ 33 34 namespace Gecode { namespace Int { 35 36 inline bool valid(int n)37 Limits::valid(int n) { 38 return ((n >= min) && (n <= max)); 39 } 40 inline bool valid(long long int n)41 Limits::valid(long long int n) { 42 return ((n >= min) && (n <= max)); 43 } 44 45 inline void check(int n,const char * l)46 Limits::check(int n, const char* l) { 47 if ((n < min) || (n > max)) 48 throw OutOfLimits(l); 49 } 50 inline void check(long long int n,const char * l)51 Limits::check(long long int n, const char* l) { 52 if ((n < min) || (n > max)) 53 throw OutOfLimits(l); 54 } 55 56 inline void positive(int n,const char * l)57 Limits::positive(int n, const char* l) { 58 if ((n <= 0) || (n > max)) 59 throw OutOfLimits(l); 60 } 61 inline void positive(long long int n,const char * l)62 Limits::positive(long long int n, const char* l) { 63 if ((n <= 0.0) || (n > max)) 64 throw OutOfLimits(l); 65 } 66 67 inline void nonnegative(int n,const char * l)68 Limits::nonnegative(int n, const char* l) { 69 if ((n < 0) || (n > max)) 70 throw OutOfLimits(l); 71 } 72 inline void nonnegative(long long int n,const char * l)73 Limits::nonnegative(long long int n, const char* l) { 74 if ((n < 0.0) || (n > max)) 75 throw OutOfLimits(l); 76 } 77 78 forceinline bool overflow_add(int n,int m)79 Limits::overflow_add(int n, int m) { 80 long long int nm = 81 static_cast<long long int>(n) + static_cast<long long int>(m); 82 return (nm > INT_MAX) || (nm < INT_MIN+1); 83 } 84 forceinline bool overflow_add(long long int n,long long int m)85 Limits::overflow_add(long long int n, long long int m) { 86 if (m < 0) 87 return n < LLONG_MIN + 1 - m; 88 else 89 return n > LLONG_MAX - m; 90 } 91 92 forceinline bool overflow_sub(int n,int m)93 Limits::overflow_sub(int n, int m) { 94 long long int nm = 95 static_cast<long long int>(n) - static_cast<long long int>(m); 96 return (nm > INT_MAX) || (nm < INT_MIN+1); 97 } 98 forceinline bool overflow_sub(long long int n,long long int m)99 Limits::overflow_sub(long long int n, long long int m) { 100 if (m < 0) 101 return n > LLONG_MAX + m; 102 else 103 return n < LLONG_MIN + 1 + m; 104 } 105 106 inline bool overflow_mul(int n,int m)107 Limits::overflow_mul(int n, int m) { 108 long long int nm = 109 static_cast<long long int>(n) * static_cast<long long int>(m); 110 return (nm > INT_MAX) || (nm < INT_MIN+1); 111 } 112 113 inline bool overflow_mul(long long int n,long long int m)114 Limits::overflow_mul(long long int n, long long int m) { 115 // Check whether we can at least change the sign 116 if ((n == LLONG_MIN) || (m == LLONG_MIN)) 117 return false; 118 119 unsigned long long int un = 120 static_cast<unsigned long long int>(n < 0 ? -n : n); 121 unsigned long long int um = 122 static_cast<unsigned long long int>(m < 0 ? -m : m); 123 124 const unsigned int k = CHAR_BIT * sizeof(int); 125 126 unsigned long long int un_hi = un >> k; 127 unsigned long long int un_lo = un & ((1ULL << k) - 1ULL); 128 unsigned long long int um_hi = um >> k; 129 unsigned long long int um_lo = um & ((1ULL << k) - 1ULL); 130 131 // This would mean that there is something larger than 2^64 132 if ((un_hi != 0ULL) && (um_hi != 0ULL)) 133 return true; 134 135 unsigned long long int unm_hi = 0ULL; 136 137 // Now, either un_hi or m_hi can be different from zero 138 if (un_hi != 0ULL) 139 unm_hi = un_hi * um_lo; 140 else if (um_hi != 0ULL) 141 unm_hi = um_hi * un_lo; 142 else 143 return false; 144 145 // Again, something larger than 2^64 146 if ((unm_hi >> k) != 0ULL) 147 return true; 148 unm_hi <<= k; 149 150 unsigned long long int unm_lo = un_lo * um_lo; 151 152 return unm_hi > static_cast<unsigned long long int>(LLONG_MAX) - unm_lo; 153 } 154 155 }} 156 157 // STATISTICS: int-var 158