00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023 #include <ppl-config.h>
00024
00025 #include "Bit_Row.defs.hh"
00026 #include <cassert>
00027 #include <climits>
00028
00029 namespace PPL = Parma_Polyhedra_Library;
00030
00031 #define PPL_BITS_PER_GMP_LIMB (PPL_SIZEOF_MP_LIMB_T*CHAR_BIT)
00032
00033 #if !PPL_HAVE_DECL_FFS || PPL_SIZEOF_MP_LIMB_T != PPL_SIZEOF_INT
00034 unsigned int
00035 PPL::Bit_Row::first_one(mp_limb_t w) {
00036 unsigned int r = 0;
00037 w = w & -w;
00038 #if PPL_SIZEOF_MP_LIMB_T == 8
00039 if ((w & 0xffffffff) == 0) {
00040 w >>= 32;
00041 r += 32;
00042 }
00043 #elif PPL_SIZEOF_MP_LIMB_T != 4
00044 #error "Size of mp_limb_t not supported by Bit_Row::first_one(mp_limb_t w)."
00045 #endif
00046 if ((w & 0xffff) == 0) {
00047 w >>= 16;
00048 r += 16;
00049 }
00050 if ((w & 0xff) == 0) {
00051 w >>= 8;
00052 r += 8;
00053 }
00054 if (w & 0xf0)
00055 r += 4;
00056 if (w & 0xcc)
00057 r += 2;
00058 if (w & 0xaa)
00059 r += 1;
00060 return r;
00061 }
00062 #endif // !PPL_HAVE_DECL_FFS || PPL_SIZEOF_MP_LIMB_T != PPL_SIZEOF_INT
00063
00064 unsigned int
00065 PPL::Bit_Row::last_one(mp_limb_t w) {
00066 unsigned int r = 0;
00067 #if PPL_SIZEOF_MP_LIMB_T == 8
00068 if (w &
00069 #if PPL_SIZEOF_LONG == 8
00070 0xffffffff00000000
00071 #else
00072 0xffffffff00000000LL
00073 #endif
00074 ) {
00075 w >>= 32;
00076 r += 32;
00077 }
00078 #elif PPL_SIZEOF_MP_LIMB_T != 4
00079 #error "Size of mp_limb_t not supported by Bit_Row::last_one(mp_limb_t w)."
00080 #endif
00081 if (w & 0xffff0000) {
00082 w >>= 16;
00083 r += 16;
00084 }
00085 if (w & 0xff00) {
00086 w >>= 8;
00087 r += 8;
00088 }
00089 if (w & 0xf0) {
00090 w >>= 4;
00091 r += 4;
00092 }
00093 if (w & 0xc) {
00094 w >>= 2;
00095 r += 2;
00096 }
00097 if (w & 0x2)
00098 r += 1;
00099 return r;
00100 }
00101
00102 unsigned long
00103 PPL::Bit_Row::first() const {
00104 const mp_size_t vec_size = vec->_mp_size;
00105 assert(vec_size >= 0);
00106 mp_size_t li = 0;
00107 mp_srcptr p = vec->_mp_d;
00108 for (; li < vec_size; ++li, ++p) {
00109 const mp_limb_t limb = *p;
00110 if (limb != 0)
00111 return li*PPL_BITS_PER_GMP_LIMB + first_one(limb);
00112 }
00113 return ULONG_MAX;
00114 }
00115
00116 unsigned long
00117 PPL::Bit_Row::next(unsigned long position) const {
00118 ++position;
00119
00120
00121
00122
00123
00124
00125
00126
00127 mp_size_t li = position / PPL_BITS_PER_GMP_LIMB;
00128 const mp_size_t vec_size = vec->_mp_size;
00129 assert(vec_size >= 0);
00130 if (li >= vec_size)
00131 return ULONG_MAX;
00132
00133
00134 mp_srcptr p = vec->_mp_d + li;
00135
00136
00137 mp_limb_t limb = *p & (~(mp_limb_t) 0) << (position % PPL_BITS_PER_GMP_LIMB);
00138
00139 while (true) {
00140 if (limb != 0)
00141 return li*PPL_BITS_PER_GMP_LIMB + first_one(limb);
00142 ++li;
00143 if (li == vec_size)
00144 break;
00145 ++p;
00146 limb = *p;
00147 }
00148 return ULONG_MAX;
00149 }
00150
00151 unsigned long
00152 PPL::Bit_Row::last() const {
00153 mp_size_t li = vec->_mp_size;
00154 assert(li >= 0);
00155 if (li == 0)
00156 return ULONG_MAX;
00157 --li;
00158 const mp_srcptr p = vec->_mp_d + li;
00159 const mp_limb_t limb = *p;
00160 assert(limb != 0);
00161 return li*PPL_BITS_PER_GMP_LIMB + last_one(limb);
00162 }
00163
00164 unsigned long
00165 PPL::Bit_Row::prev(unsigned long position) const {
00166 if (position == 0)
00167 return ULONG_MAX;
00168
00169 --position;
00170
00171 const mp_size_t vec_size = vec->_mp_size;
00172 assert(vec_size > 0);
00173 mp_size_t li = position / PPL_BITS_PER_GMP_LIMB;
00174
00175 mp_limb_t limb;
00176 mp_srcptr p = vec->_mp_d;
00177
00178
00179 if (li >= vec_size) {
00180 li = vec_size - 1;
00181 p += li;
00182 limb = *p;
00183 }
00184 else {
00185 const mp_limb_t mask
00186 = (~(mp_limb_t) 0)
00187 >> (PPL_BITS_PER_GMP_LIMB - 1 - position % PPL_BITS_PER_GMP_LIMB);
00188 p += li;
00189 limb = *p & mask;
00190 }
00191
00192 while (true) {
00193 if (limb != 0)
00194 return li*PPL_BITS_PER_GMP_LIMB + last_one(limb);
00195 if (li == 0)
00196 break;
00197 --li;
00198 --p;
00199 limb = *p;
00200 }
00201 return ULONG_MAX;
00202 }
00203
00204 bool
00205 PPL::Bit_Row::operator[](const unsigned long k) const {
00206 const mp_size_t vec_size = vec->_mp_size;
00207 assert(vec_size >= 0);
00208
00209 unsigned long i = k / GMP_NUMB_BITS;
00210 if (i >= static_cast<unsigned long>(vec_size))
00211 return false;
00212
00213 mp_limb_t limb = *(vec->_mp_d + i);
00214 return (limb >> (k % GMP_NUMB_BITS)) & 1;
00215 }
00216
00218 int
00219 PPL::compare(const Bit_Row& x, const Bit_Row& y) {
00220 const mp_size_t x_size = x.vec->_mp_size;
00221 assert(x_size >= 0);
00222 const mp_size_t y_size = y.vec->_mp_size;
00223 assert(y_size >= 0);
00224 mp_size_t size = (x_size > y_size ? y_size : x_size);
00225 mp_srcptr xp = x.vec->_mp_d;
00226 mp_srcptr yp = y.vec->_mp_d;
00227 while (size > 0) {
00228 const mp_limb_t xl = *xp;
00229 const mp_limb_t yl = *yp;
00230 if (xl != yl) {
00231
00232 const mp_limb_t diff = xl ^ yl;
00233
00234 const mp_limb_t mask = diff & ~(diff-1);
00235 return (xl & mask) ? 1 : -1;
00236 }
00237 ++xp;
00238 ++yp;
00239 --size;
00240 }
00241 return x_size == y_size ? 0 : (x_size > y_size ? 1 : -1);
00242 }
00243
00245 bool
00246 PPL::subset_or_equal(const Bit_Row& x, const Bit_Row& y) {
00247 mp_size_t x_size = x.vec->_mp_size;
00248 assert(x_size >= 0);
00249 mp_size_t y_size = y.vec->_mp_size;
00250 assert(y_size >= 0);
00251 if (x_size > y_size)
00252 return false;
00253 mp_srcptr xp = x.vec->_mp_d;
00254 mp_srcptr yp = y.vec->_mp_d;
00255 while (x_size > 0) {
00256 if (*xp & ~*yp)
00257 return false;
00258 ++xp;
00259 ++yp;
00260 --x_size;
00261 }
00262 return true;
00263 }
00264
00266 bool
00267 PPL::subset_or_equal(const Bit_Row& x, const Bit_Row& y,
00268 bool& strict_subset) {
00269 mp_size_t x_size = x.vec->_mp_size;
00270 assert(x_size >= 0);
00271 mp_size_t y_size = y.vec->_mp_size;
00272 assert(y_size >= 0);
00273 if (x_size > y_size)
00274 return false;
00275 strict_subset = (x_size < y_size);
00276 mp_srcptr xp = x.vec->_mp_d;
00277 mp_srcptr yp = y.vec->_mp_d;
00278 while (x_size > 0) {
00279 const mp_limb_t xl = *xp;
00280 const mp_limb_t yl = *yp;
00281 if (xl & ~yl)
00282 return false;
00283 if (!strict_subset && xl != yl)
00284 strict_subset = true;
00285 ++xp;
00286 ++yp;
00287 --x_size;
00288 }
00289 return true;
00290 }
00291
00293 bool
00294 PPL::strict_subset(const Bit_Row& x, const Bit_Row& y) {
00295 mp_size_t x_size = x.vec->_mp_size;
00296 assert(x_size >= 0);
00297 mp_size_t y_size = y.vec->_mp_size;
00298 assert(y_size >= 0);
00299 if (x_size > y_size)
00300 return false;
00301 bool different = (x_size < y_size);
00302 mp_srcptr xp = x.vec->_mp_d;
00303 mp_srcptr yp = y.vec->_mp_d;
00304 while (x_size > 0) {
00305 const mp_limb_t xl = *xp;
00306 const mp_limb_t yl = *yp;
00307 if (xl & ~yl)
00308 return false;
00309 if (!different && xl != yl)
00310 different = true;
00311 ++xp;
00312 ++yp;
00313 --x_size;
00314 }
00315 return different;
00316 }
00317
00319 bool
00320 PPL::operator==(const Bit_Row& x, const Bit_Row& y) {
00321 const mp_size_t x_vec_size = x.vec->_mp_size;
00322 assert(x_vec_size >= 0);
00323 const mp_size_t y_vec_size = y.vec->_mp_size;
00324 assert(y_vec_size >= 0);
00325
00326 if (x_vec_size != y_vec_size)
00327 return false;
00328
00329 return mpn_cmp(x.vec->_mp_d, y.vec->_mp_d, x_vec_size) == 0;
00330 }
00331
00333 bool
00334 PPL::operator!=(const Bit_Row& x, const Bit_Row& y) {
00335 const mp_size_t x_vec_size = x.vec->_mp_size;
00336 assert(x_vec_size >= 0);
00337 const mp_size_t y_vec_size = y.vec->_mp_size;
00338 assert(y_vec_size >= 0);
00339
00340 if (x_vec_size != y_vec_size)
00341 return true;
00342
00343 return mpn_cmp(x.vec->_mp_d, y.vec->_mp_d, x_vec_size) != 0;
00344 }
00345
00346 bool
00347 PPL::Bit_Row::OK() const {
00348 const mp_size_t vec_size = vec->_mp_size;
00349 const mp_size_t vec_alloc = vec->_mp_alloc;
00350 return vec_size >= 0
00351 && vec_alloc >= vec_size
00352 && (vec_size == 0 || mpz_getlimbn(vec, vec_size-1) != 0);
00353 }