1# distutils: language = c++ 2# distutils: include_dirs = LIB_DIR_EWAH 3# distutils: extra_compile_args = CPP14_FLAG 4""" 5Wrapper for EWAH Bool Array: https://github.com/lemire/EWAHBoolArray 6 7 8 9""" 10 11 12import struct 13 14from cython.operator cimport dereference, preincrement 15from libc.stdlib cimport free, malloc, qsort 16from libcpp.algorithm cimport sort 17from libcpp.map cimport map as cmap 18 19import numpy as np 20 21cimport cython 22cimport numpy as np 23 24from yt.utilities.lib.geometry_utils cimport ( 25 morton_neighbors_coarse, 26 morton_neighbors_refined, 27) 28 29 30cdef extern from "<algorithm>" namespace "std" nogil: 31 Iter unique[Iter](Iter first, Iter last) 32 33cdef np.uint64_t FLAG = ~(<np.uint64_t>0) 34cdef np.uint64_t MAX_VECTOR_SIZE = <np.uint64_t>1e7 35 36ctypedef cmap[np.uint64_t, ewah_bool_array] ewahmap 37ctypedef cmap[np.uint64_t, ewah_bool_array].iterator ewahmap_it 38ctypedef pair[np.uint64_t, ewah_bool_array] ewahmap_p 39 40cdef class FileBitmasks: 41 42 def __cinit__(self, np.uint32_t nfiles): 43 cdef int i 44 self.nfiles = nfiles 45 self.ewah_keys = <ewah_bool_array **>malloc(nfiles*sizeof(ewah_bool_array*)) 46 self.ewah_refn = <ewah_bool_array **>malloc(nfiles*sizeof(ewah_bool_array*)) 47 self.ewah_coll = <ewah_map **>malloc(nfiles*sizeof(ewah_map*)) 48 for i in range(nfiles): 49 self.ewah_keys[i] = new ewah_bool_array() 50 self.ewah_refn[i] = new ewah_bool_array() 51 self.ewah_coll[i] = new ewah_map() 52 53 cdef void _reset(self): 54 cdef np.int32_t ifile 55 for ifile in range(self.nfiles): 56 self.ewah_keys[ifile].reset() 57 self.ewah_refn[ifile].reset() 58 self.ewah_coll[ifile].clear() 59 60 cdef bint _iseq(self, FileBitmasks solf): 61 cdef np.int32_t ifile 62 cdef ewah_bool_array* arr1 63 cdef ewah_bool_array* arr2 64 cdef ewahmap *map1 65 cdef ewahmap *map2 66 cdef ewahmap_p pair1, pair2 67 cdef ewahmap_it it_map1, it_map2 68 if self.nfiles != solf.nfiles: 69 return 0 70 for ifile in range(self.nfiles): 71 # Keys 72 arr1 = (<ewah_bool_array **> self.ewah_keys)[ifile] 73 arr2 = (<ewah_bool_array **> solf.ewah_keys)[ifile] 74 if arr1[0] != arr2[0]: 75 return 0 76 # Refn 77 arr1 = (<ewah_bool_array **> self.ewah_refn)[ifile] 78 arr2 = (<ewah_bool_array **> solf.ewah_refn)[ifile] 79 if arr1[0] != arr2[0]: 80 return 0 81 # Map 82 map1 = (<ewahmap **> self.ewah_coll)[ifile] 83 map2 = (<ewahmap **> solf.ewah_coll)[ifile] 84 for pair1 in map1[0]: 85 it_map2 = map2[0].find(pair1.first) 86 if it_map2 == map2[0].end(): 87 return 0 88 if pair1.second != dereference(it_map2).second: 89 return 0 90 for pair2 in map2[0]: 91 it_map1 = map1[0].find(pair2.first) 92 if it_map1 == map1[0].end(): 93 return 0 94 if pair2.second != dereference(it_map1).second: 95 return 0 96 # Match 97 return 1 98 99 def iseq(self, solf): 100 return self._iseq(solf) 101 102 cdef BoolArrayCollection _get_bitmask(self, np.uint32_t ifile): 103 cdef BoolArrayCollection out = BoolArrayCollection() 104 cdef ewah_bool_array **ewah_keys = <ewah_bool_array **>self.ewah_keys 105 cdef ewah_bool_array **ewah_refn = <ewah_bool_array **>self.ewah_refn 106 cdef ewah_map **ewah_coll = <ewah_map **>self.ewah_coll 107 # This version actually copies arrays, which can be costly 108 cdef ewah_bool_array *ewah_keys_out = <ewah_bool_array *>out.ewah_keys 109 cdef ewah_bool_array *ewah_refn_out = <ewah_bool_array *>out.ewah_refn 110 cdef ewah_map *ewah_coll_out = <ewah_map *>out.ewah_coll 111 ewah_keys_out[0] = ewah_keys[ifile][0] 112 ewah_refn_out[0] = ewah_refn[ifile][0] 113 ewah_coll_out[0] = ewah_coll[ifile][0] 114 # This version only copies pointers which can lead to deallocation of 115 # the source when the copy is deleted. 116 # out.ewah_keys = <void *>ewah_keys[ifile] 117 # out.ewah_refn = <void *>ewah_refn[ifile] 118 # out.ewah_coll = <void *>ewah_coll[ifile] 119 return out 120 121 cdef tuple _find_collisions(self, BoolArrayCollection coll, bint verbose = 0): 122 cdef tuple cc, cr 123 cc = self._find_collisions_coarse(coll, verbose) 124 cr = self._find_collisions_refined(coll, verbose) 125 return cc, cr 126 127 cdef tuple _find_collisions_coarse(self, BoolArrayCollection coll, bint 128 verbose = 0, file_list = None): 129 cdef np.int32_t ifile 130 cdef ewah_bool_array arr_two, arr_swap, arr_keys, arr_refn 131 cdef ewah_bool_array* iarr 132 cdef ewah_bool_array* coll_keys 133 cdef ewah_bool_array* coll_refn 134 coll_keys = (<ewah_bool_array*> coll.ewah_keys) 135 coll_refn = (<ewah_bool_array*> coll.ewah_refn) 136 if file_list is None: 137 file_list = range(self.nfiles) 138 for ifile in file_list: 139 iarr = (<ewah_bool_array **>self.ewah_keys)[ifile] 140 arr_keys.logicaland(iarr[0], arr_two) 141 arr_keys.logicalor(iarr[0], arr_swap) 142 arr_keys.swap(arr_swap) 143 arr_refn.logicalor(arr_two, arr_swap) 144 arr_refn.swap(arr_swap) 145 coll_keys[0].swap(arr_keys) 146 coll_refn[0].swap(arr_refn) 147 # Print 148 cdef int nc, nm 149 nc = coll_refn[0].numberOfOnes() 150 nm = coll_keys[0].numberOfOnes() 151 cdef tuple nout = (nc, nm) 152 if verbose == 1: 153 print("{: 10d}/{: 10d} collisions at coarse refinement. ({: 10.5f}%)".format(nc,nm,100.0*float(nc)/nm)) 154 return nout 155 156 cdef tuple _find_collisions_refined(self, BoolArrayCollection coll, bint verbose = 0): 157 cdef np.int32_t ifile 158 cdef ewah_bool_array iarr, arr_two, arr_swap 159 cdef ewah_bool_array* coll_refn 160 cdef cmap[np.uint64_t, ewah_bool_array] map_keys, map_refn 161 cdef cmap[np.uint64_t, ewah_bool_array]* coll_coll 162 cdef cmap[np.uint64_t, ewah_bool_array]* map_bitmask 163 coll_refn = <ewah_bool_array*> coll.ewah_refn 164 if coll_refn[0].numberOfOnes() == 0: 165 if verbose == 1: 166 print("{: 10d}/{: 10d} collisions at refined refinement. ({: 10.5f}%)".format(0,0,0)) 167 return (0,0) 168 coll_coll = <cmap[np.uint64_t, ewah_bool_array]*> coll.ewah_coll 169 for ifile in range(self.nfiles): 170 map_bitmask = (<cmap[np.uint64_t, ewah_bool_array]**> self.ewah_coll)[ifile] 171 for it_mi1 in map_bitmask[0]: 172 mi1 = it_mi1.first 173 iarr = it_mi1.second 174 map_keys[mi1].logicaland(iarr, arr_two) 175 map_keys[mi1].logicalor(iarr, arr_swap) 176 map_keys[mi1].swap(arr_swap) 177 map_refn[mi1].logicalor(arr_two, arr_swap) 178 map_refn[mi1].swap(arr_swap) 179 coll_coll[0] = map_refn 180 # Count 181 cdef int nc, nm 182 nc = 0 183 nm = 0 184 for it_mi1 in map_refn: 185 mi1 = it_mi1.first 186 iarr = it_mi1.second 187 nc += iarr.numberOfOnes() 188 iarr = map_keys[mi1] 189 nm += iarr.numberOfOnes() 190 cdef tuple nout = (nc, nm) 191 # Print 192 if verbose == 1: 193 if nm == 0: 194 print("{: 10d}/{: 10d} collisions at refined refinement. ({: 10.5f}%)".format(nc,nm,0.0)) 195 else: 196 print("{: 10d}/{: 10d} collisions at refined refinement. ({: 10.5f}%)".format(nc,nm,100.0*float(nc)/nm)) 197 return nout 198 199 cdef void _set(self, np.uint32_t ifile, np.uint64_t i1, np.uint64_t i2 = FLAG): 200 cdef ewah_bool_array *ewah_keys = (<ewah_bool_array **> self.ewah_keys)[ifile] 201 cdef ewah_bool_array *ewah_refn = (<ewah_bool_array **> self.ewah_refn)[ifile] 202 cdef ewah_map *ewah_coll = (<ewah_map **> self.ewah_coll)[ifile] 203 ewah_keys[0].set(i1) 204 if i2 != FLAG: 205 ewah_refn[0].set(i1) 206 ewah_coll[0][i1].set(i2) 207 208 cdef void _set_coarse(self, np.uint32_t ifile, np.uint64_t i1): 209 cdef ewah_bool_array *ewah_keys = (<ewah_bool_array **> self.ewah_keys)[ifile] 210 ewah_keys[0].set(i1) 211 212 cdef void _set_refined(self, np.uint32_t ifile, np.uint64_t i1, np.uint64_t i2): 213 cdef ewah_bool_array *ewah_refn = (<ewah_bool_array **> self.ewah_refn)[ifile] 214 cdef ewah_map *ewah_coll = (<ewah_map **> self.ewah_coll)[ifile] 215 ewah_refn[0].set(i1) 216 ewah_coll[0][i1].set(i2) 217 218 @cython.boundscheck(False) 219 @cython.wraparound(False) 220 @cython.cdivision(True) 221 @cython.initializedcheck(False) 222 cdef void _set_coarse_array(self, np.uint32_t ifile, np.uint8_t[:] arr): 223 cdef ewah_bool_array *ewah_keys = (<ewah_bool_array **> self.ewah_keys)[ifile] 224 cdef np.uint64_t i1 225 for i1 in range(arr.shape[0]): 226 if arr[i1] == 1: 227 ewah_keys[0].set(i1) 228 229 @cython.boundscheck(False) 230 @cython.wraparound(False) 231 @cython.cdivision(True) 232 @cython.initializedcheck(False) 233 cdef void _set_refined_array(self, np.uint32_t ifile, np.uint64_t i1, np.uint8_t[:] arr): 234 cdef ewah_bool_array *ewah_refn = (<ewah_bool_array **> self.ewah_refn)[ifile] 235 cdef ewah_map *ewah_coll = (<ewah_map **> self.ewah_coll)[ifile] 236 cdef np.uint64_t i2 237 for i2 in range(arr.shape[0]): 238 if arr[i2] == 1: 239 ewah_refn[0].set(i1) 240 ewah_coll[0][i1].set(i2) 241 242 @cython.boundscheck(False) 243 @cython.wraparound(False) 244 @cython.cdivision(True) 245 @cython.initializedcheck(False) 246 cdef void _set_refined_index_array(self, np.uint32_t ifile, np.int64_t nsub_mi, 247 np.ndarray[np.uint64_t, ndim=1] sub_mi1, 248 np.ndarray[np.uint64_t, ndim=1] sub_mi2): 249 cdef np.ndarray[np.int64_t, ndim=1] ind = np.lexsort((sub_mi2[:nsub_mi], 250 sub_mi1[:nsub_mi])) 251 cdef np.int64_t i, p 252 cdef BoolArrayCollection temp 253 if self._count_refined(ifile) == 0: 254 # Add to file bitmask in order 255 for i in range(nsub_mi): 256 p = ind[i] 257 self._set_refined(ifile, sub_mi1[p], sub_mi2[p]) 258 else: 259 # Add to dummy bitmask in order, then combine 260 temp = BoolArrayCollection() 261 for i in range(nsub_mi): 262 p = ind[i] 263 temp._set_coarse(sub_mi1[p]) 264 temp._set_refined(sub_mi1[p], sub_mi2[p]) 265 self._append(ifile, temp) 266 267 cdef void _set_map(self, np.uint32_t ifile, np.uint64_t i1, np.uint64_t i2): 268 cdef ewah_map *ewah_coll = (<ewah_map **> self.ewah_coll)[ifile] 269 ewah_coll[0][i1].set(i2) 270 271 cdef void _set_refn(self, np.uint32_t ifile, np.uint64_t i1): 272 cdef ewah_bool_array *ewah_refn = (<ewah_bool_array **> self.ewah_refn)[ifile] 273 ewah_refn[0].set(i1) 274 275 cdef bint _get(self, np.uint32_t ifile, np.uint64_t i1, np.uint64_t i2 = FLAG): 276 cdef ewah_bool_array *ewah_keys = (<ewah_bool_array **> self.ewah_keys)[ifile] 277 cdef ewah_bool_array *ewah_refn = (<ewah_bool_array **> self.ewah_refn)[ifile] 278 cdef ewah_map *ewah_coll = (<ewah_map **> self.ewah_coll)[ifile] 279 if (ewah_keys[0].get(i1) == 0): return 0 280 if (i2 == FLAG) or (ewah_refn[0].get(i1) == 0): 281 return 1 282 return ewah_coll[0][i1].get(i2) 283 284 cdef bint _get_coarse(self, np.uint32_t ifile, np.uint64_t i1): 285 cdef ewah_bool_array *ewah_keys = (<ewah_bool_array **> self.ewah_keys)[ifile] 286 return ewah_keys[0].get(i1) 287 288 @cython.boundscheck(False) 289 @cython.wraparound(False) 290 @cython.cdivision(True) 291 @cython.initializedcheck(False) 292 cdef void _get_coarse_array(self, np.uint32_t ifile, np.uint64_t imax, 293 np.uint8_t[:] arr) except *: 294 cdef ewah_bool_array *ewah_keys = (<ewah_bool_array **> self.ewah_keys)[ifile] 295 cdef ewah_bool_iterator *iter_set = new ewah_bool_iterator(ewah_keys[0].begin()) 296 cdef ewah_bool_iterator *iter_end = new ewah_bool_iterator(ewah_keys[0].end()) 297 cdef np.uint64_t iset 298 while iter_set[0] != iter_end[0]: 299 iset = dereference(iter_set[0]) 300 if iset >= imax: 301 raise IndexError("Index {} exceedes max {}.".format(iset, imax)) 302 arr[iset] = 1 303 preincrement(iter_set[0]) 304 305 cdef bint _isref(self, np.uint32_t ifile, np.uint64_t i): 306 cdef ewah_bool_array *ewah_refn = (<ewah_bool_array **> self.ewah_refn)[ifile] 307 return ewah_refn[0].get(i) 308 309 def count_coarse(self, ifile): 310 return self._count_coarse(ifile) 311 312 def count_total(self, ifile): 313 return self._count_total(ifile) 314 315 def count_refined(self, ifile): 316 return self._count_refined(ifile) 317 318 cdef np.uint64_t _count_coarse(self, np.uint32_t ifile): 319 return self._count_total(ifile) - self._count_refined(ifile) 320 321 cdef np.uint64_t _count_total(self, np.uint32_t ifile): 322 cdef ewah_bool_array *ewah_keys = (<ewah_bool_array **> self.ewah_keys)[ifile] 323 cdef np.uint64_t out = ewah_keys[0].numberOfOnes() 324 return out 325 326 cdef np.uint64_t _count_refined(self, np.uint32_t ifile): 327 cdef ewah_bool_array *ewah_refn = (<ewah_bool_array **> self.ewah_refn)[ifile] 328 cdef np.uint64_t out = ewah_refn[0].numberOfOnes() 329 return out 330 331 def append(self, np.uint32_t ifile, BoolArrayCollection solf): 332 if solf is None: return 333 self._append(ifile, solf) 334 335 cdef void _append(self, np.uint32_t ifile, BoolArrayCollection solf): 336 cdef ewah_bool_array *ewah_keys1 = (<ewah_bool_array **> self.ewah_keys)[ifile] 337 cdef ewah_bool_array *ewah_refn1 = (<ewah_bool_array **> self.ewah_refn)[ifile] 338 cdef ewah_map *ewah_coll1 = (<ewah_map **> self.ewah_coll)[ifile] 339 cdef ewah_bool_array *ewah_keys2 = <ewah_bool_array *> solf.ewah_keys 340 cdef ewah_bool_array *ewah_refn2 = <ewah_bool_array *> solf.ewah_refn 341 cdef ewahmap *ewah_coll2 = <ewahmap *> solf.ewah_coll 342 cdef ewahmap_it it_map1, it_map2 343 cdef ewah_bool_array swap, mi1_ewah1, mi1_ewah2 344 cdef np.uint64_t mi1 345 # Keys 346 ewah_keys1[0].logicalor(ewah_keys2[0], swap) 347 ewah_keys1[0].swap(swap) 348 # Refined 349 ewah_refn1[0].logicalor(ewah_refn2[0], swap) 350 ewah_refn1[0].swap(swap) 351 # Map 352 it_map2 = ewah_coll2[0].begin() 353 while it_map2 != ewah_coll2[0].end(): 354 mi1 = dereference(it_map2).first 355 mi1_ewah2 = dereference(it_map2).second 356 it_map1 = ewah_coll1[0].find(mi1) 357 if it_map1 == ewah_coll1[0].end(): 358 ewah_coll1[0][mi1] = mi1_ewah2 359 else: 360 mi1_ewah1 = dereference(it_map1).second 361 mi1_ewah1.logicalor(mi1_ewah2, swap) 362 mi1_ewah1.swap(swap) 363 preincrement(it_map2) 364 365 cdef bint _intersects(self, np.uint32_t ifile, BoolArrayCollection solf): 366 cdef ewah_bool_array *ewah_keys1 = (<ewah_bool_array **> self.ewah_keys)[ifile] 367 cdef ewah_bool_array *ewah_refn1 = (<ewah_bool_array **> self.ewah_refn)[ifile] 368 cdef ewah_map *ewah_coll1 = (<ewah_map **> self.ewah_coll)[ifile] 369 cdef ewah_bool_array *ewah_keys2 = <ewah_bool_array *> solf.ewah_keys 370 cdef ewah_bool_array *ewah_refn2 = <ewah_bool_array *> solf.ewah_refn 371 cdef ewahmap *ewah_coll2 = <ewahmap *> solf.ewah_coll 372 cdef ewahmap_it it_map1, it_map2 373 cdef ewah_bool_array mi1_ewah1, mi1_ewah2 374 cdef np.uint64_t mi1 375 cdef ewah_bool_array ewah_coar1, ewah_coar2 376 # No intersection 377 if ewah_keys1[0].intersects(ewah_keys2[0]) == 0: 378 return 0 379 # Intersection at coarse level 380 ewah_keys1[0].logicalxor(ewah_refn1[0],ewah_coar1) 381 ewah_keys2[0].logicalxor(ewah_refn2[0],ewah_coar2) 382 if ewah_coar1.intersects(ewah_keys2[0]) == 1: 383 return 1 384 if ewah_coar2.intersects(ewah_keys1[0]) == 1: 385 return 1 386 # Intersection at refined level 387 if ewah_refn1[0].intersects(ewah_refn2[0]) == 1: 388 it_map1 = ewah_coll1[0].begin() 389 while (it_map1 != ewah_coll1[0].end()): 390 mi1 = dereference(it_map1).first 391 it_map2 = ewah_coll2[0].find(mi1) 392 if it_map2 != ewah_coll2[0].end(): 393 mi1_ewah1 = dereference(it_map1).second 394 mi1_ewah2 = dereference(it_map2).second 395 if mi1_ewah1.intersects(mi1_ewah2): 396 return 1 397 preincrement(it_map1) 398 return 0 399 400 cdef void _logicalxor(self, np.uint32_t ifile, BoolArrayCollection solf, BoolArrayCollection out): 401 cdef ewah_bool_array *ewah_keys1 = (<ewah_bool_array **> self.ewah_keys)[ifile] 402 cdef ewah_bool_array *ewah_refn1 = (<ewah_bool_array **> self.ewah_refn)[ifile] 403 cdef ewah_map *ewah_coll1 = (<ewah_map **> self.ewah_coll)[ifile] 404 cdef ewah_bool_array *ewah_keys2 = <ewah_bool_array *> solf.ewah_keys 405 cdef ewah_bool_array *ewah_refn2 = <ewah_bool_array *> solf.ewah_refn 406 cdef ewahmap *ewah_coll2 = <ewahmap *> solf.ewah_coll 407 cdef ewah_bool_array *ewah_keys_out = <ewah_bool_array *> out.ewah_keys 408 cdef ewah_bool_array *ewah_refn_out = <ewah_bool_array *> out.ewah_refn 409 cdef ewah_map *ewah_coll_out = <ewah_map *> out.ewah_coll 410 cdef ewahmap_it it_map1, it_map2 411 cdef ewah_bool_array mi1_ewah1, mi1_ewah2, swap 412 cdef np.uint64_t mi1 413 # Keys 414 ewah_keys1[0].logicalxor(ewah_keys2[0],ewah_keys_out[0]) 415 # Refn 416 ewah_refn1[0].logicalxor(ewah_refn2[0],ewah_refn_out[0]) 417 # Coll 418 it_map1 = ewah_coll1[0].begin() 419 while (it_map1 != ewah_coll1[0].end()): 420 mi1 = dereference(it_map1).first 421 mi1_ewah1 = dereference(it_map1).second 422 it_map2 = ewah_coll2[0].find(mi1) 423 if it_map2 == ewah_coll2[0].end(): 424 ewah_coll_out[0][mi1] = mi1_ewah1 425 else: 426 mi1_ewah2 = dereference(it_map2).second 427 mi1_ewah1.logicalxor(mi1_ewah2, swap) 428 ewah_coll_out[0][mi1] = swap 429 preincrement(it_map1) 430 it_map2 = ewah_coll2[0].begin() 431 while (it_map2 != ewah_coll2[0].end()): 432 mi1 = dereference(it_map2).first 433 mi1_ewah2 = dereference(it_map2).second 434 it_map1 = ewah_coll1[0].find(mi1) 435 if it_map1 == ewah_coll1[0].end(): 436 ewah_coll_out[0][mi1] = mi1_ewah2 437 preincrement(it_map2) 438 439 def logicalxor(self, ifile, solf, out): 440 return self._logicalxor(ifile, solf, out) 441 442 cdef void _logicaland(self, np.uint32_t ifile, BoolArrayCollection solf, BoolArrayCollection out): 443 cdef ewah_bool_array *ewah_keys1 = (<ewah_bool_array **> self.ewah_keys)[ifile] 444 cdef ewah_bool_array *ewah_refn1 = (<ewah_bool_array **> self.ewah_refn)[ifile] 445 cdef ewah_map *ewah_coll1 = (<ewah_map **> self.ewah_coll)[ifile] 446 cdef ewah_bool_array *ewah_keys2 = <ewah_bool_array *> solf.ewah_keys 447 cdef ewah_bool_array *ewah_refn2 = <ewah_bool_array *> solf.ewah_refn 448 cdef ewahmap *ewah_coll2 = <ewahmap *> solf.ewah_coll 449 cdef ewah_bool_array *ewah_keys_out = <ewah_bool_array *> out.ewah_keys 450 cdef ewah_bool_array *ewah_refn_out = <ewah_bool_array *> out.ewah_refn 451 cdef ewah_map *ewah_coll_out = <ewah_map *> out.ewah_coll 452 cdef ewahmap_it it_map1, it_map2 453 cdef ewah_bool_array mi1_ewah1, mi1_ewah2, swap 454 cdef np.uint64_t mi1 455 # Keys 456 ewah_keys1[0].logicaland(ewah_keys2[0],ewah_keys_out[0]) 457 # Refn 458 ewah_refn1[0].logicaland(ewah_refn2[0],ewah_refn_out[0]) 459 # Coll 460 if ewah_refn_out[0].numberOfOnes() > 0: 461 it_map1 = ewah_coll1[0].begin() 462 while (it_map1 != ewah_coll1[0].end()): 463 mi1 = dereference(it_map1).first 464 it_map2 = ewah_coll2[0].find(mi1) 465 if it_map2 != ewah_coll2[0].end(): 466 mi1_ewah1 = dereference(it_map1).second 467 mi1_ewah2 = dereference(it_map2).second 468 mi1_ewah1.logicaland(mi1_ewah2, swap) 469 ewah_coll_out[0][mi1] = swap 470 preincrement(it_map1) 471 472 def logicaland(self, ifile, solf, out): 473 return self._logicaland(ifile, solf, out) 474 475 cdef void _select_contaminated(self, np.uint32_t ifile, 476 BoolArrayCollection mask, np.uint8_t[:] out, 477 np.uint8_t[:] secondary_files, 478 BoolArrayCollection mask2 = None): 479 # Fill mask at indices owned by this file that are also contaminated by 480 # other files. 481 cdef ewah_bool_array *ewah_refn = (<ewah_bool_array **> self.ewah_refn)[ifile] 482 cdef ewah_bool_array ewah_mask 483 cdef ewah_bool_array *ewah_mask1 484 cdef ewah_bool_array *ewah_mask2 485 cdef ewah_bool_array ewah_slct 486 cdef ewah_bool_array *ewah_file 487 cdef np.uint64_t iset 488 # Merge masks as necessary 489 if mask2 is None: 490 ewah_mask = (<ewah_bool_array *> mask.ewah_keys)[0] 491 else: 492 ewah_mask1 = <ewah_bool_array *> mask.ewah_keys 493 ewah_mask2 = <ewah_bool_array *> mask2.ewah_keys 494 ewah_mask1[0].logicalor(ewah_mask2[0],ewah_mask) 495 # Get just refined cells owned by this file 496 ewah_mask.logicaland(ewah_refn[0], ewah_slct) 497 # Set array values 498 cdef ewah_bool_iterator *iter_set = new ewah_bool_iterator(ewah_slct.begin()) 499 cdef ewah_bool_iterator *iter_end = new ewah_bool_iterator(ewah_slct.end()) 500 while iter_set[0] != iter_end[0]: 501 iset = dereference(iter_set[0]) 502 out[iset] = 1 503 preincrement(iter_set[0]) 504 # Find files that intersect this one 505 cdef np.uint32_t isfile 506 for isfile in range(self.nfiles): 507 if isfile == ifile: continue 508 ewah_file = (<ewah_bool_array **> self.ewah_keys)[isfile] 509 if ewah_slct.intersects(ewah_file[0]) == 1: 510 secondary_files[isfile] = 1 511 512 cdef void _select_uncontaminated(self, np.uint32_t ifile, 513 BoolArrayCollection mask, np.uint8_t[:] out, 514 BoolArrayCollection mask2 = None): 515 # Fill mask at indices that are owned by this file and no other. 516 cdef ewah_bool_array *ewah_keys = (<ewah_bool_array **> self.ewah_keys)[ifile] 517 cdef ewah_bool_array *ewah_refn = (<ewah_bool_array **> self.ewah_refn)[ifile] 518 cdef ewah_bool_array ewah_mask 519 cdef ewah_bool_array *ewah_mask1 520 cdef ewah_bool_array *ewah_mask2 521 cdef ewah_bool_array ewah_slct 522 cdef ewah_bool_array ewah_coar 523 cdef np.uint64_t iset 524 # Merge masks if necessary 525 if mask2 is None: 526 ewah_mask = (<ewah_bool_array *> mask.ewah_keys)[0] 527 else: 528 ewah_mask1 = <ewah_bool_array *> mask.ewah_keys 529 ewah_mask2 = <ewah_bool_array *> mask2.ewah_keys 530 ewah_mask1[0].logicalor(ewah_mask2[0],ewah_mask) 531 # Get coarse cells owned by this file 532 ewah_keys[0].logicalxor(ewah_refn[0],ewah_coar) 533 ewah_coar.logicaland(ewah_mask,ewah_slct) 534 # Set array elements 535 cdef ewah_bool_iterator *iter_set = new ewah_bool_iterator(ewah_slct.begin()) 536 cdef ewah_bool_iterator *iter_end = new ewah_bool_iterator(ewah_slct.end()) 537 while iter_set[0] != iter_end[0]: 538 iset = dereference(iter_set[0]) 539 out[iset] = 1 540 preincrement(iter_set[0]) 541 542 cdef bytes _dumps(self, np.uint32_t ifile): 543 # TODO: write word size 544 cdef sstream ss 545 cdef ewah_bool_array *ewah_keys = (<ewah_bool_array **> self.ewah_keys)[ifile] 546 cdef ewah_bool_array *ewah_refn = (<ewah_bool_array **> self.ewah_refn)[ifile] 547 cdef ewah_map *ewah_coll = (<ewah_map **> self.ewah_coll)[ifile] 548 cdef ewahmap_it it_map 549 cdef np.uint64_t nrefn, mi1 550 cdef ewah_bool_array mi1_ewah 551 # Write mi1 ewah & refinment ewah 552 ewah_keys[0].write(ss,1) 553 ewah_refn[0].write(ss,1) 554 # Number of refined bool arrays 555 nrefn = <np.uint64_t>(ewah_refn[0].numberOfOnes()) 556 ss.write(<const char *> &nrefn, sizeof(nrefn)) 557 # Loop over refined bool arrays 558 it_map = ewah_coll[0].begin() 559 while it_map != ewah_coll[0].end(): 560 mi1 = dereference(it_map).first 561 mi1_ewah = dereference(it_map).second 562 ss.write(<const char *> &mi1, sizeof(mi1)) 563 mi1_ewah.write(ss,1) 564 preincrement(it_map) 565 # Return type cast python bytes string 566 return <bytes>ss.str() 567 568 cdef bint _loads(self, np.uint32_t ifile, bytes s): 569 # TODO: write word size 570 cdef sstream ss 571 cdef ewah_bool_array *ewah_keys = (<ewah_bool_array **> self.ewah_keys)[ifile] 572 cdef ewah_bool_array *ewah_refn = (<ewah_bool_array **> self.ewah_refn)[ifile] 573 cdef ewah_map *ewah_coll = (<ewah_map **> self.ewah_coll)[ifile] 574 cdef np.uint64_t nrefn, mi1 575 nrefn = mi1 = 0 576 # Write string to string stream 577 if len(s) == 0: return 1 578 ss.write(s, len(s)) 579 # Read keys and refinement arrays 580 ewah_keys[0].read(ss,1) 581 if ss.eof(): return 1 582 ewah_refn[0].read(ss,1) 583 # Read and check number of refined cells 584 ss.read(<char *> (&nrefn), sizeof(nrefn)) 585 if nrefn != ewah_refn[0].numberOfOnes(): 586 raise Exception("Error in read. File indicates {} refinements, but bool array has {}.".format(nrefn,ewah_refn[0].numberOfOnes())) 587 # Loop over refined cells 588 for _ in range(nrefn): 589 ss.read(<char *> (&mi1), sizeof(mi1)) 590 if ss.eof(): return 1 591 ewah_coll[0][mi1].read(ss,1) 592 # or... 593 #mi1_ewah.read(ss,1) 594 #ewah_coll[0][mi1].swap(mi1_ewah) 595 return 1 596 597 cdef bint _check(self): 598 cdef np.uint32_t ifile 599 cdef ewah_bool_array *ewah_keys 600 cdef ewah_bool_array *ewah_refn 601 cdef ewah_bool_array tmp1, tmp2 602 cdef np.uint64_t nchk 603 cdef str msg 604 # Check individual files 605 for ifile in range(self.nfiles): 606 ewah_keys = (<ewah_bool_array **> self.ewah_keys)[ifile] 607 ewah_refn = (<ewah_bool_array **> self.ewah_refn)[ifile] 608 # Check that there are not any refn that are not keys 609 ewah_keys[0].logicalxor(ewah_refn[0], tmp1) 610 ewah_refn[0].logicaland(tmp1, tmp2) 611 nchk = tmp2.numberOfOnes() 612 if nchk > 0: 613 msg = "File {}: There are {} refined cells that are not set on coarse level.".format(ifile,nchk) 614 print(msg) 615 return 0 616 # raise Exception(msg) 617 return 1 618 619 def check(self): 620 return self._check() 621 622 def __dealloc__(self): 623 for ifile in range(self.nfiles): 624 del self.ewah_keys[ifile] 625 del self.ewah_refn[ifile] 626 del self.ewah_coll[ifile] 627 628 def print_info(self, ifile, prefix=''): 629 print("{}{: 8d} coarse, {: 8d} refined, {: 8d} total".format( 630 prefix, 631 self._count_coarse(ifile), 632 self._count_refined(ifile), 633 self._count_total(ifile))) 634 635cdef class BoolArrayCollection: 636 637 def __cinit__(self): 638 self.ewah_keys = new ewah_bool_array() 639 self.ewah_refn = new ewah_bool_array() 640 self.ewah_coar = new ewah_bool_array() 641 self.ewah_coll = new ewah_map() 642 643 cdef void _reset(self): 644 self.ewah_keys[0].reset() 645 self.ewah_refn[0].reset() 646 self.ewah_coar[0].reset() 647 self.ewah_coll[0].clear() 648 649 cdef int _richcmp(self, BoolArrayCollection solf, int op) except -1: 650 651 cdef ewah_bool_array *arr1 652 cdef ewah_bool_array *arr2 653 cdef ewahmap *map1 654 cdef ewahmap *map2 655 cdef ewahmap_it it_map1, it_map2 656 # == 657 if op == 2: 658 # Keys 659 arr1 = <ewah_bool_array *> self.ewah_keys 660 arr2 = <ewah_bool_array *> solf.ewah_keys 661 if arr1[0] != arr2[0]: 662 return 0 663 # Refn 664 arr1 = <ewah_bool_array *> self.ewah_refn 665 arr2 = <ewah_bool_array *> solf.ewah_refn 666 if arr1[0] != arr2[0]: 667 return 0 668 # Map 669 map1 = <ewahmap *> self.ewah_coll 670 map2 = <ewahmap *> solf.ewah_coll 671 it_map1 = map1[0].begin() 672 while (it_map1 != map1[0].end()): 673 it_map2 = map2[0].find(dereference(it_map1).first) 674 if it_map2 == map2[0].end(): 675 return 0 676 if dereference(it_map1).second != dereference(it_map2).second: 677 return 0 678 preincrement(it_map1) 679 it_map2 =map2[0].begin() 680 while (it_map2 != map2[0].end()): 681 it_map1 = map1[0].find(dereference(it_map2).first) 682 if it_map1 == map1[0].end(): 683 return 0 684 if dereference(it_map2).second != dereference(it_map1).second: 685 return 0 686 preincrement(it_map2) 687 # Match 688 return 1 689 # != 690 elif op == 3: 691 if self._richcmp(solf, 2) == 1: 692 return 0 693 return 1 694 else: 695 return -1 696 # options = ['<','<=','==','!=','>','>='] 697 # raise NotImplementedError("Operator {} is not yet implemented.".format(options[op])) 698 699 def __richcmp__(BoolArrayCollection self, BoolArrayCollection solf, int op): 700 if self._richcmp(solf, op) == 1: 701 return True 702 else: 703 return False 704 705 cdef void _set(self, np.uint64_t i1, np.uint64_t i2 = FLAG): 706 cdef ewah_bool_array *ewah_keys = <ewah_bool_array *> self.ewah_keys 707 cdef ewah_bool_array *ewah_refn = <ewah_bool_array *> self.ewah_refn 708 cdef ewah_map *ewah_coll = <ewah_map *> self.ewah_coll 709 ewah_keys[0].set(i1) 710 # Note the 0 here, for dereferencing 711 if i2 != FLAG: 712 ewah_refn[0].set(i1) 713 ewah_coll[0][i1].set(i2) 714 715 def set(self, i1, i2 = FLAG): 716 self._set(i1, i2) 717 718 @cython.boundscheck(False) 719 @cython.wraparound(False) 720 @cython.cdivision(True) 721 @cython.initializedcheck(False) 722 def set_from(self, np.uint64_t[:] ids): 723 cdef ewah_bool_array *ewah_keys = <ewah_bool_array *> self.ewah_keys 724 cdef np.uint64_t i 725 cdef np.uint64_t last = 0 726 for i in range(ids.shape[0]): 727 if ids[i] < last: 728 raise RuntimeError 729 self._set(ids[i]) 730 last = ids[i] 731 print("Set from %s array and ended up with %s bytes" % ( 732 ids.size, ewah_keys[0].sizeInBytes())) 733 734 cdef void _set_coarse(self, np.uint64_t i1): 735 cdef ewah_bool_array *ewah_keys = <ewah_bool_array *> self.ewah_keys 736 ewah_keys[0].set(i1) 737 738 def set_coarse(self, i1): 739 return self._set_coarse(i1) 740 741 cdef void _set_refined(self, np.uint64_t i1, np.uint64_t i2): 742 cdef ewah_bool_array *ewah_refn = <ewah_bool_array *> self.ewah_refn 743 cdef ewah_map *ewah_coll = <ewah_map *> self.ewah_coll 744 # Note the 0 here, for dereferencing 745 ewah_refn[0].set(i1) 746 ewah_coll[0][i1].set(i2) 747 748 @cython.boundscheck(False) 749 @cython.wraparound(False) 750 @cython.cdivision(True) 751 @cython.initializedcheck(False) 752 cdef void _set_coarse_array(self, np.uint8_t[:] arr): 753 cdef ewah_bool_array *ewah_keys = <ewah_bool_array *> self.ewah_keys 754 cdef np.uint64_t i1 755 for i1 in range(arr.shape[0]): 756 if arr[i1] == 1: 757 ewah_keys[0].set(i1) 758 # self._set_coarse(i1) 759 760 @cython.boundscheck(False) 761 @cython.wraparound(False) 762 @cython.cdivision(True) 763 @cython.initializedcheck(False) 764 cdef void _set_refined_array(self, np.uint64_t i1, np.uint8_t[:] arr): 765 cdef ewah_bool_array *ewah_refn = <ewah_bool_array *> self.ewah_refn 766 cdef ewah_map *ewah_coll = <ewah_map *> self.ewah_coll 767 cdef np.uint64_t i2 768 for i2 in range(arr.shape[0]): 769 if arr[i2] == 1: 770 ewah_refn[0].set(i1) 771 ewah_coll[0][i1].set(i2) 772 # self._set_refined(i1, i2) 773 774 def set_refined(self, i1, i2): 775 return self._set_refined(i1, i2) 776 777 cdef void _set_map(self, np.uint64_t i1, np.uint64_t i2): 778 cdef ewah_map *ewah_coll = <ewah_map *> self.ewah_coll 779 ewah_coll[0][i1].set(i2) 780 781 def set_map(self, i1, i2): 782 self._set_map(i1, i2) 783 784 cdef void _set_refn(self, np.uint64_t i1): 785 cdef ewah_bool_array *ewah_refn = <ewah_bool_array *> self.ewah_refn 786 ewah_refn[0].set(i1) 787 788 def set_refn(self, i1): 789 self._set_refn(i1) 790 791 cdef bint _get(self, np.uint64_t i1, np.uint64_t i2 = FLAG): 792 cdef ewah_bool_array *ewah_keys = <ewah_bool_array *> self.ewah_keys 793 cdef ewah_bool_array *ewah_refn = <ewah_bool_array *> self.ewah_refn 794 cdef ewah_map *ewah_coll = <ewah_map *> self.ewah_coll 795 # Note the 0 here, for dereferencing 796 if (ewah_keys[0].get(i1) == 0): return 0 797 if (ewah_refn[0].get(i1) == 0) or (i2 == FLAG): 798 return 1 799 return ewah_coll[0][i1].get(i2) 800 801 def get(self, i1, i2 = FLAG): 802 return self._get(i1, i2) 803 804 cdef bint _get_coarse(self, np.uint64_t i1): 805 cdef ewah_bool_array *ewah_keys = <ewah_bool_array *> self.ewah_keys 806 return ewah_keys[0].get(i1) 807 808 def get_coarse(self, i1): 809 return self._get_coarse(i1) 810 811 @cython.boundscheck(False) 812 @cython.wraparound(False) 813 @cython.cdivision(True) 814 @cython.initializedcheck(False) 815 cdef void _get_coarse_array(self, np.uint64_t imax, np.uint8_t[:] arr) except *: 816 cdef ewah_bool_array *ewah_keys = <ewah_bool_array *> self.ewah_keys 817 cdef ewah_bool_iterator *iter_set = new ewah_bool_iterator(ewah_keys[0].begin()) 818 cdef ewah_bool_iterator *iter_end = new ewah_bool_iterator(ewah_keys[0].end()) 819 cdef np.uint64_t iset 820 while iter_set[0] != iter_end[0]: 821 iset = dereference(iter_set[0]) 822 if iset >= imax: 823 raise IndexError("Index {} exceedes max {}.".format(iset, imax)) 824 arr[iset] = 1 825 preincrement(iter_set[0]) 826 827 def get_coarse_array(self, imax, arr): 828 return self._get_coarse_array(imax, arr) 829 830 cdef bint _contains(self, np.uint64_t i): 831 cdef ewah_bool_array *ewah_keys = <ewah_bool_array *> self.ewah_keys 832 return ewah_keys[0].get(i) 833 834 def contains(self, np.uint64_t i): 835 return self._contains(i) 836 837 cdef bint _isref(self, np.uint64_t i): 838 cdef ewah_bool_array *ewah_refn = <ewah_bool_array *> self.ewah_refn 839 return ewah_refn[0].get(i) 840 841 def isref(self, np.uint64_t i): 842 return self._isref(i) 843 844 cdef void _ewah_coarse(self): 845 cdef ewah_bool_array *ewah_keys = <ewah_bool_array *> self.ewah_keys 846 cdef ewah_bool_array *ewah_refn = <ewah_bool_array *> self.ewah_refn 847 cdef ewah_bool_array *ewah_coar = <ewah_bool_array *> self.ewah_coar 848 ewah_coar[0].reset() 849 ewah_keys[0].logicalxor(ewah_refn[0],ewah_coar[0]) 850 return 851 852 def ewah_coarse(self): 853 return self._ewah_coarse() 854 855 cdef np.uint64_t _count_total(self): 856 cdef ewah_bool_array *ewah_keys = <ewah_bool_array *> self.ewah_keys 857 cdef np.uint64_t out = ewah_keys.numberOfOnes() 858 return out 859 860 def count_total(self): 861 return self._count_total() 862 863 cdef np.uint64_t _count_refined(self): 864 cdef ewah_bool_array *ewah_refn = <ewah_bool_array *> self.ewah_refn 865 cdef np.uint64_t out = ewah_refn.numberOfOnes() 866 return out 867 868 def count_refined(self): 869 return self._count_refined() 870 871 cdef np.uint64_t _count_coarse(self): 872 self._ewah_coarse() 873 cdef ewah_bool_array *ewah_coar = <ewah_bool_array *> self.ewah_coar 874 cdef np.uint64_t out = ewah_coar.numberOfOnes() 875 return out 876 877 def count_coarse(self): 878 return self._count_coarse() 879 880 cdef void _logicalor(self, BoolArrayCollection solf, BoolArrayCollection out): 881 cdef ewah_bool_array *ewah_keys1 = self.ewah_keys 882 cdef ewah_bool_array *ewah_refn1 = self.ewah_refn 883 cdef ewahmap *ewah_coll1 = self.ewah_coll 884 cdef ewah_bool_array *ewah_keys2 = solf.ewah_keys 885 cdef ewah_bool_array *ewah_refn2 = solf.ewah_refn 886 cdef ewahmap *ewah_coll2 = solf.ewah_coll 887 cdef ewah_bool_array *ewah_keys3 = out.ewah_keys 888 cdef ewah_bool_array *ewah_refn3 = out.ewah_refn 889 cdef ewahmap *ewah_coll3 = out.ewah_coll 890 cdef ewahmap_it it_map1, it_map2 891 cdef ewah_bool_array mi1_ewah1, mi1_ewah2 892 cdef np.uint64_t mi1 893 # Keys 894 ewah_keys1[0].logicalor(ewah_keys2[0], ewah_keys3[0]) 895 # Refined 896 ewah_refn1[0].logicalor(ewah_refn2[0], ewah_refn3[0]) 897 # Map 898 it_map1 = ewah_coll1[0].begin() 899 while it_map1 != ewah_coll1[0].end(): 900 mi1 = dereference(it_map1).first 901 mi1_ewah1 = dereference(it_map1).second 902 ewah_coll3[0][mi1] = mi1_ewah1 903 preincrement(it_map1) 904 it_map2 = ewah_coll2[0].begin() 905 while it_map2 != ewah_coll2[0].end(): 906 mi1 = dereference(it_map2).first 907 mi1_ewah2 = dereference(it_map2).second 908 it_map1 = ewah_coll1[0].find(mi1) 909 if it_map1 != ewah_coll1[0].end(): 910 mi1_ewah1 = dereference(it_map1).second 911 mi1_ewah1.logicalor(mi1_ewah2, ewah_coll3[0][mi1]) 912 else: 913 ewah_coll3[0][mi1] = mi1_ewah2 914 preincrement(it_map2) 915 916 cdef void _append(self, BoolArrayCollection solf): 917 cdef ewah_bool_array *ewah_keys1 = <ewah_bool_array *> self.ewah_keys 918 cdef ewah_bool_array *ewah_refn1 = <ewah_bool_array *> self.ewah_refn 919 cdef ewahmap *ewah_coll1 = <ewahmap *> self.ewah_coll 920 cdef ewah_bool_array *ewah_keys2 = <ewah_bool_array *> solf.ewah_keys 921 cdef ewah_bool_array *ewah_refn2 = <ewah_bool_array *> solf.ewah_refn 922 cdef ewahmap *ewah_coll2 = <ewahmap *> solf.ewah_coll 923 cdef ewahmap_it it_map1, it_map2 924 cdef ewah_bool_array swap, mi1_ewah1, mi1_ewah2 925 cdef np.uint64_t mi1 926 # Keys 927 ewah_keys1[0].logicalor(ewah_keys2[0], swap) 928 ewah_keys1[0].swap(swap) 929 # Refined 930 ewah_refn1[0].logicalor(ewah_refn2[0], swap) 931 ewah_refn1[0].swap(swap) 932 # Map 933 it_map2 = ewah_coll2[0].begin() 934 while it_map2 != ewah_coll2[0].end(): 935 mi1 = dereference(it_map2).first 936 mi1_ewah2 = dereference(it_map2).second 937 it_map1 = ewah_coll1[0].find(mi1) 938 if it_map1 == ewah_coll1[0].end(): 939 ewah_coll1[0][mi1] = mi1_ewah2 940 else: 941 mi1_ewah1 = dereference(it_map1).second 942 mi1_ewah1.logicalor(mi1_ewah2, swap) 943 mi1_ewah1.swap(swap) 944 preincrement(it_map2) 945 946 def append(self, solf): 947 return self._append(solf) 948 949 cdef bint _intersects(self, BoolArrayCollection solf): 950 cdef ewah_bool_array *ewah_keys1 = <ewah_bool_array *> self.ewah_keys 951 cdef ewah_bool_array *ewah_refn1 = <ewah_bool_array *> self.ewah_refn 952 cdef ewahmap *ewah_coll1 = <ewahmap *> self.ewah_coll 953 cdef ewah_bool_array *ewah_keys2 = <ewah_bool_array *> solf.ewah_keys 954 cdef ewah_bool_array *ewah_refn2 = <ewah_bool_array *> solf.ewah_refn 955 cdef ewahmap *ewah_coll2 = <ewahmap *> solf.ewah_coll 956 cdef ewahmap_it it_map1, it_map2 957 cdef ewah_bool_array mi1_ewah1, mi1_ewah2 958 cdef np.uint64_t mi1 959 cdef ewah_bool_array ewah_coar1, ewah_coar2 960 # No intersection 961 if ewah_keys1[0].intersects(ewah_keys2[0]) == 0: 962 return 0 963 # Intersection at coarse level 964 ewah_keys1[0].logicalxor(ewah_refn1[0],ewah_coar1) 965 ewah_keys2[0].logicalxor(ewah_refn2[0],ewah_coar2) 966 if ewah_coar1.intersects(ewah_keys2[0]) == 1: 967 return 1 968 if ewah_coar2.intersects(ewah_keys1[0]) == 1: 969 return 1 970 # Intersection at refined level 971 if ewah_refn1[0].intersects(ewah_refn2[0]) == 1: 972 it_map1 = ewah_coll1[0].begin() 973 while (it_map1 != ewah_coll1[0].end()): 974 mi1 = dereference(it_map1).first 975 it_map2 = ewah_coll2[0].find(mi1) 976 if it_map2 != ewah_coll2[0].end(): 977 mi1_ewah1 = dereference(it_map1).second 978 mi1_ewah2 = dereference(it_map2).second 979 if mi1_ewah1.intersects(mi1_ewah2): 980 return 1 981 preincrement(it_map1) 982 return 0 983 984 cdef void _logicalxor(self, BoolArrayCollection solf, BoolArrayCollection out): 985 cdef ewah_bool_array *ewah_keys1 = <ewah_bool_array *> self.ewah_keys 986 cdef ewah_bool_array *ewah_refn1 = <ewah_bool_array *> self.ewah_refn 987 cdef ewah_map *ewah_coll1 = <ewah_map *> self.ewah_coll 988 cdef ewah_bool_array *ewah_keys2 = <ewah_bool_array *> solf.ewah_keys 989 cdef ewah_bool_array *ewah_refn2 = <ewah_bool_array *> solf.ewah_refn 990 cdef ewahmap *ewah_coll2 = <ewahmap *> solf.ewah_coll 991 cdef ewah_bool_array *ewah_keys_out = <ewah_bool_array *> out.ewah_keys 992 cdef ewah_bool_array *ewah_refn_out = <ewah_bool_array *> out.ewah_refn 993 cdef ewah_map *ewah_coll_out = <ewah_map *> out.ewah_coll 994 cdef ewahmap_it it_map1, it_map2 995 cdef ewah_bool_array mi1_ewah1, mi1_ewah2, swap 996 cdef np.uint64_t mi1 997 # Keys 998 ewah_keys1[0].logicalxor(ewah_keys2[0],ewah_keys_out[0]) 999 # Refn 1000 ewah_refn1[0].logicalxor(ewah_refn2[0],ewah_refn_out[0]) 1001 # Coll 1002 it_map1 = ewah_coll1[0].begin() 1003 while (it_map1 != ewah_coll1[0].end()): 1004 mi1 = dereference(it_map1).first 1005 mi1_ewah1 = dereference(it_map1).second 1006 it_map2 = ewah_coll2[0].find(mi1) 1007 if it_map2 == ewah_coll2[0].end(): 1008 ewah_coll_out[0][mi1] = mi1_ewah1 1009 else: 1010 mi1_ewah2 = dereference(it_map2).second 1011 mi1_ewah1.logicalxor(mi1_ewah2, swap) 1012 ewah_coll_out[0][mi1] = swap 1013 preincrement(it_map1) 1014 it_map2 = ewah_coll2[0].begin() 1015 while (it_map2 != ewah_coll2[0].end()): 1016 mi1 = dereference(it_map2).first 1017 mi1_ewah2 = dereference(it_map2).second 1018 it_map1 = ewah_coll1[0].find(mi1) 1019 if it_map1 == ewah_coll1[0].end(): 1020 ewah_coll_out[0][mi1] = mi1_ewah2 1021 preincrement(it_map2) 1022 1023 def logicalxor(self, solf, out): 1024 return self._logicalxor(solf, out) 1025 1026 cdef void _logicaland(self, BoolArrayCollection solf, BoolArrayCollection out): 1027 cdef ewah_bool_array *ewah_keys1 = <ewah_bool_array *> self.ewah_keys 1028 cdef ewah_bool_array *ewah_refn1 = <ewah_bool_array *> self.ewah_refn 1029 cdef ewah_map *ewah_coll1 = <ewah_map *> self.ewah_coll 1030 cdef ewah_bool_array *ewah_keys2 = <ewah_bool_array *> solf.ewah_keys 1031 cdef ewah_bool_array *ewah_refn2 = <ewah_bool_array *> solf.ewah_refn 1032 cdef ewahmap *ewah_coll2 = <ewahmap *> solf.ewah_coll 1033 cdef ewah_bool_array *ewah_keys_out = <ewah_bool_array *> out.ewah_keys 1034 cdef ewah_bool_array *ewah_refn_out = <ewah_bool_array *> out.ewah_refn 1035 cdef ewah_map *ewah_coll_out = <ewah_map *> out.ewah_coll 1036 cdef ewahmap_it it_map1, it_map2 1037 cdef ewah_bool_array mi1_ewah1, mi1_ewah2, swap 1038 cdef np.uint64_t mi1 1039 # Keys 1040 ewah_keys1[0].logicaland(ewah_keys2[0],ewah_keys_out[0]) 1041 # Refn 1042 ewah_refn1[0].logicaland(ewah_refn2[0],ewah_refn_out[0]) 1043 # Coll 1044 if ewah_refn_out[0].numberOfOnes() > 0: 1045 it_map1 = ewah_coll1[0].begin() 1046 while (it_map1 != ewah_coll1[0].end()): 1047 mi1 = dereference(it_map1).first 1048 mi1_ewah1 = dereference(it_map1).second 1049 it_map2 = ewah_coll2[0].find(mi1) 1050 if it_map2 != ewah_coll2[0].end(): 1051 mi1_ewah2 = dereference(it_map2).second 1052 mi1_ewah1.logicaland(mi1_ewah2, swap) 1053 ewah_coll_out[0][mi1] = swap 1054 preincrement(it_map1) 1055 1056 def logicaland(self, solf, out): 1057 return self._logicaland(solf, out) 1058 1059 cdef void _select_contaminated(self, BoolArrayCollection mask, np.uint8_t[:] out, 1060 BoolArrayCollection mask2 = None): 1061 cdef ewah_bool_array *ewah_refn = <ewah_bool_array *> self.ewah_refn 1062 cdef ewah_bool_array ewah_mask 1063 cdef ewah_bool_array *ewah_mask1 1064 cdef ewah_bool_array *ewah_mask2 1065 if mask2 is None: 1066 ewah_mask = (<ewah_bool_array *> mask.ewah_keys)[0] 1067 else: 1068 ewah_mask1 = <ewah_bool_array *> mask.ewah_keys 1069 ewah_mask2 = <ewah_bool_array *> mask2.ewah_keys 1070 ewah_mask1[0].logicalor(ewah_mask2[0],ewah_mask) 1071 cdef ewah_bool_array ewah_slct 1072 ewah_refn[0].logicaland(ewah_mask,ewah_slct) 1073 cdef np.uint64_t iset 1074 cdef ewah_bool_iterator *iter_set = new ewah_bool_iterator(ewah_slct.begin()) 1075 cdef ewah_bool_iterator *iter_end = new ewah_bool_iterator(ewah_slct.end()) 1076 while iter_set[0] != iter_end[0]: 1077 iset = dereference(iter_set[0]) 1078 out[iset] = 1 1079 preincrement(iter_set[0]) 1080 1081 cdef void _select_uncontaminated(self, BoolArrayCollection mask, np.uint8_t[:] out, 1082 BoolArrayCollection mask2 = None): 1083 cdef ewah_bool_array *ewah_keys = <ewah_bool_array *> self.ewah_keys 1084 cdef ewah_bool_array *ewah_refn = <ewah_bool_array *> self.ewah_refn 1085 cdef ewah_bool_array ewah_mask 1086 cdef ewah_bool_array *ewah_mask1 1087 cdef ewah_bool_array *ewah_mask2 1088 if mask2 is None: 1089 ewah_mask = (<ewah_bool_array *> mask.ewah_keys)[0] 1090 else: 1091 ewah_mask1 = <ewah_bool_array *> mask.ewah_keys 1092 ewah_mask2 = <ewah_bool_array *> mask2.ewah_keys 1093 ewah_mask1[0].logicalor(ewah_mask2[0],ewah_mask) 1094 cdef ewah_bool_array ewah_slct 1095 cdef ewah_bool_array ewah_coar 1096 ewah_keys[0].logicalxor(ewah_refn[0],ewah_coar) 1097 ewah_coar.logicaland(ewah_mask,ewah_slct) 1098 cdef np.uint64_t iset 1099 cdef ewah_bool_iterator *iter_set = new ewah_bool_iterator(ewah_slct.begin()) 1100 cdef ewah_bool_iterator *iter_end = new ewah_bool_iterator(ewah_slct.end()) 1101 while iter_set[0] != iter_end[0]: 1102 iset = dereference(iter_set[0]) 1103 out[iset] = 1 1104 preincrement(iter_set[0]) 1105 1106 cdef void _get_ghost_zones(self, int ngz, int order1, int order2, 1107 bint periodicity[3], BoolArrayCollection out_ewah, 1108 bint coarse_ghosts = 0): 1109 cdef ewah_bool_array *ewah_keys = <ewah_bool_array *> self.ewah_keys 1110 cdef ewah_bool_array *ewah_refn = <ewah_bool_array *> self.ewah_refn 1111 cdef ewahmap *ewah_coll = <ewahmap *> self.ewah_coll 1112 cdef ewah_bool_iterator *iter_set1 = new ewah_bool_iterator(ewah_keys.begin()) 1113 cdef ewah_bool_iterator *iter_end1 = new ewah_bool_iterator(ewah_keys.end()) 1114 cdef ewah_bool_iterator *iter_set2 1115 cdef ewah_bool_iterator *iter_end2 1116 cdef np.uint64_t max_index1 = <np.uint64_t>(1 << order1) 1117 cdef np.uint64_t max_index2 = <np.uint64_t>(1 << order2) 1118 cdef np.uint64_t nele1 = <np.uint64_t>(max_index1**3) 1119 cdef np.uint64_t nele2 = <np.uint64_t>(max_index2**3) 1120 cdef BoolArrayCollectionUncompressed temp_bool = BoolArrayCollectionUncompressed(nele1, nele2) 1121 cdef BoolArrayCollectionUncompressed out_bool = BoolArrayCollectionUncompressed(nele1, nele2) 1122 cdef np.uint64_t mi1, mi2, mi1_n, mi2_n 1123 cdef np.uint32_t ntot, i 1124 cdef void* pointers[7] 1125 pointers[0] = malloc( sizeof(np.int32_t) * (2*ngz+1)*3) 1126 pointers[1] = malloc( sizeof(np.uint64_t) * (2*ngz+1)*3) 1127 pointers[2] = malloc( sizeof(np.uint64_t) * (2*ngz+1)*3) 1128 pointers[3] = malloc( sizeof(np.uint64_t) * (2*ngz+1)**3) 1129 pointers[4] = malloc( sizeof(np.uint64_t) * (2*ngz+1)**3) 1130 pointers[5] = malloc( sizeof(np.uint8_t) * nele1) 1131 pointers[6] = malloc( sizeof(np.uint8_t) * nele2) 1132 cdef np.uint32_t[:,:] index = <np.uint32_t[:2*ngz+1,:3]> pointers[0] 1133 cdef np.uint64_t[:,:] ind1_n = <np.uint64_t[:2*ngz+1,:3]> pointers[1] 1134 cdef np.uint64_t[:,:] ind2_n = <np.uint64_t[:2*ngz+1,:3]> pointers[2] 1135 cdef np.uint64_t[:] neighbor_list1 = <np.uint64_t[:((2*ngz+1)**3)]> pointers[3] 1136 cdef np.uint64_t[:] neighbor_list2 = <np.uint64_t[:((2*ngz+1)**3)]> pointers[4] 1137 cdef np.uint8_t *bool_keys = <np.uint8_t *> pointers[5] 1138 cdef np.uint8_t *bool_coll = <np.uint8_t *> pointers[6] 1139 cdef SparseUnorderedRefinedBitmaskSet list_coll = SparseUnorderedRefinedBitmaskSet() 1140 for i in range(nele1): 1141 bool_keys[i] = 0 1142 while iter_set1[0] != iter_end1[0]: 1143 mi1 = dereference(iter_set1[0]) 1144 if (coarse_ghosts == 1) or (ewah_refn[0].get(mi1) == 0): 1145 # Coarse neighbors 1146 ntot = morton_neighbors_coarse(mi1, max_index1, periodicity, ngz, 1147 index, ind1_n, neighbor_list1) 1148 for i in range(ntot): 1149 mi1_n = neighbor_list1[i] 1150 if ewah_keys[0].get(mi1_n) == 0: 1151 bool_keys[mi1_n] = 1 1152 else: 1153 for i in range(nele2): 1154 bool_coll[i] = 0 1155 # Refined neighbors 1156 iter_set2 = new ewah_bool_iterator(ewah_coll[0][mi1].begin()) 1157 iter_end2 = new ewah_bool_iterator(ewah_coll[0][mi1].end()) 1158 while iter_set2[0] != iter_end2[0]: 1159 mi2 = dereference(iter_set2[0]) 1160 ntot = morton_neighbors_refined(mi1, mi2, 1161 max_index1, max_index2, 1162 periodicity, ngz, index, 1163 ind1_n, ind2_n, 1164 neighbor_list1, 1165 neighbor_list2) 1166 for i in range(ntot): 1167 mi1_n = neighbor_list1[i] 1168 mi2_n = neighbor_list2[i] 1169 if mi1_n == mi1: 1170 if ewah_coll[0][mi1].get(mi2_n) == 0: 1171 bool_keys[mi1_n] = 1 1172 bool_coll[mi2_n] = 1 1173 else: 1174 if ewah_refn[0].get(mi1_n) == 1: 1175 if ewah_coll[0][mi1_n].get(mi2_n) == 0: 1176 bool_keys[mi1_n] = 1 1177 list_coll._set(mi1_n, mi2_n) 1178 else: 1179 if ewah_keys[0].get(mi1_n) == 0: 1180 bool_keys[mi1_n] = 1 1181 preincrement(iter_set2[0]) 1182 # Add to running list 1183 temp_bool._set_refined_array_ptr(mi1, bool_coll) 1184 preincrement(iter_set1[0]) 1185 # Set keys 1186 out_bool._set_coarse_array_ptr(bool_keys) 1187 list_coll._fill_bool(out_bool) 1188 out_bool._append(temp_bool) 1189 out_bool._compress(out_ewah) 1190 # Free things 1191 for i in range(7): 1192 free(pointers[i]) 1193 1194 cdef bytes _dumps(self): 1195 # TODO: write word size 1196 cdef sstream ss 1197 cdef ewah_bool_array *ewah_keys = <ewah_bool_array *> self.ewah_keys 1198 cdef ewah_bool_array *ewah_refn = <ewah_bool_array *> self.ewah_refn 1199 cdef ewahmap *ewah_coll = <ewahmap *> self.ewah_coll 1200 cdef ewahmap_it it_map 1201 cdef np.uint64_t nrefn, mi1 1202 cdef ewah_bool_array mi1_ewah 1203 # Write mi1 ewah & refinment ewah 1204 ewah_keys[0].write(ss,1) 1205 ewah_refn[0].write(ss,1) 1206 # Number of refined bool arrays 1207 nrefn = <np.uint64_t>(ewah_refn[0].numberOfOnes()) 1208 ss.write(<const char *> &nrefn, sizeof(nrefn)) 1209 # Loop over refined bool arrays 1210 it_map = ewah_coll[0].begin() 1211 while it_map != ewah_coll[0].end(): 1212 mi1 = dereference(it_map).first 1213 mi1_ewah = dereference(it_map).second 1214 ss.write(<const char *> &mi1, sizeof(mi1)) 1215 mi1_ewah.write(ss,1) 1216 preincrement(it_map) 1217 # Return type cast python bytes string 1218 return <bytes>ss.str() 1219 1220 def dumps(self): 1221 return self._dumps() 1222 1223 cdef bint _loads(self, bytes s): 1224 # TODO: write word size 1225 cdef sstream ss 1226 cdef ewah_bool_array *ewah_keys = <ewah_bool_array *> self.ewah_keys 1227 cdef ewah_bool_array *ewah_refn = <ewah_bool_array *> self.ewah_refn 1228 cdef ewahmap *ewah_coll = <ewahmap *> self.ewah_coll 1229 cdef np.uint64_t nrefn, mi1 1230 nrefn = mi1 = 0 1231 # Write string to string stream 1232 if len(s) == 0: return 1 1233 ss.write(s, len(s)) 1234 # Read keys and refinement arrays 1235 if ss.eof(): return 1 1236 ewah_keys[0].read(ss,1) 1237 if ss.eof(): return 1 1238 ewah_refn[0].read(ss,1) 1239 # Read and check number of refined cells 1240 if ss.eof(): return 1 1241 ss.read(<char *> (&nrefn), sizeof(nrefn)) 1242 if nrefn != ewah_refn[0].numberOfOnes(): 1243 raise Exception("Error in read. File indicates {} refinements, but bool array has {}.".format(nrefn,ewah_refn[0].numberOfOnes())) 1244 # Loop over refined cells 1245 for _ in range(nrefn): 1246 ss.read(<char *> (&mi1), sizeof(mi1)) 1247 if ss.eof(): 1248 # A brief note about why we do this! 1249 # In previous versions of the EWAH code, which were more 1250 # susceptible to issues with differences in sizes of size_t 1251 # etc, the ewah_coll.read would use instance variables as 1252 # destinations; these were initialized to zero. In recent 1253 # versions, it uses (uninitialized) temporary variables. We 1254 # were passing in streams that were already at EOF - so the 1255 # uninitialized memory would not be written to, and it would 1256 # retain the previous values, which would invariably be really 1257 # really big! So we do a check for EOF here to make sure we're 1258 # not up to no good. 1259 break 1260 ewah_coll[0][mi1].read(ss,1) 1261 # or... 1262 #mi1_ewah.read(ss,1) 1263 #ewah_coll[0][mi1].swap(mi1_ewah) 1264 return 1 1265 1266 def loads(self, s): 1267 return self._loads(s) 1268 1269 def save(self, fname): 1270 cdef bytes serial_BAC 1271 f = open(fname,'wb') 1272 serial_BAC = self._dumps() 1273 f.write(struct.pack('Q',len(serial_BAC))) 1274 f.write(serial_BAC) 1275 f.close() 1276 1277 def load(self, fname): 1278 cdef np.uint64_t size_serial 1279 cdef bint flag_read 1280 f = open(fname,'rb') 1281 size_serial, = struct.unpack('Q',f.read(struct.calcsize('Q'))) 1282 flag_read = self._loads(f.read(size_serial)) 1283 f.close() 1284 return flag_read 1285 1286 cdef bint _check(self): 1287 cdef ewah_bool_array *ewah_keys = <ewah_bool_array *> self.ewah_keys 1288 cdef ewah_bool_array *ewah_refn = <ewah_bool_array *> self.ewah_refn 1289 cdef ewah_bool_array tmp1, tmp2 1290 cdef np.uint64_t nchk 1291 cdef str msg 1292 # Check that there are not any refn that are not keys 1293 ewah_keys[0].logicalxor(ewah_refn[0], tmp1) 1294 ewah_refn[0].logicaland(tmp1, tmp2) 1295 nchk = tmp2.numberOfOnes() 1296 if nchk > 0: 1297 msg = "There are {} refined cells that are not set on coarse level.".format(nchk) 1298 print(msg) 1299 return 0 1300 # raise Exception(msg) 1301 return 1 1302 1303 def __dealloc__(self): 1304 cdef ewah_bool_array *ewah_keys = <ewah_bool_array *> self.ewah_keys 1305 cdef ewah_bool_array *ewah_refn = <ewah_bool_array *> self.ewah_refn 1306 cdef ewah_bool_array *ewah_coar = <ewah_bool_array *> self.ewah_coar 1307 cdef ewah_map *ewah_coll = <ewah_map *> self.ewah_coll 1308 del ewah_keys 1309 del ewah_refn 1310 del ewah_coar 1311 del ewah_coll 1312 1313 def print_info(self, prefix=''): 1314 print("{}{: 8d} coarse, {: 8d} refined, {: 8d} total".format(prefix, 1315 self._count_coarse(), 1316 self._count_refined(), 1317 self._count_total())) 1318 1319cdef class BoolArrayCollectionUncompressed: 1320 1321 def __cinit__(self, np.uint64_t nele1, np.uint64_t nele2): 1322 self.nele1 = <int>nele1 1323 self.nele2 = <int>nele2 1324 self.ewah_coll = new ewah_map() 1325 cdef np.uint64_t i 1326 self.ewah_keys = <bitarrtype *>malloc(sizeof(bitarrtype)*nele1) 1327 self.ewah_refn = <bitarrtype *>malloc(sizeof(bitarrtype)*nele1) 1328 for i in range(nele1): 1329 self.ewah_keys[i] = 0 1330 self.ewah_refn[i] = 0 1331 1332 def reset(self): 1333 self.__dealloc__() 1334 self.__init__(self.nele1,self.nele2) 1335 1336 cdef void _compress(self, BoolArrayCollection solf): 1337 cdef np.uint64_t i 1338 cdef ewah_bool_array *ewah_keys = <ewah_bool_array *> solf.ewah_keys 1339 cdef ewah_bool_array *ewah_refn = <ewah_bool_array *> solf.ewah_refn 1340 cdef bitarrtype *bool_keys = <bitarrtype *> self.ewah_keys 1341 cdef bitarrtype *bool_refn = <bitarrtype *> self.ewah_refn 1342 for i in range(self.nele1): 1343 if bool_keys[i] == 1: 1344 ewah_keys[0].set(i) 1345 if bool_refn[i] == 1: 1346 ewah_refn[0].set(i) 1347 cdef ewah_map *ewah_coll1 = <ewah_map *> self.ewah_coll 1348 cdef ewah_map *ewah_coll2 = <ewah_map *> solf.ewah_coll 1349 ewah_coll2[0] = ewah_coll1[0] 1350 1351 cdef void _set(self, np.uint64_t i1, np.uint64_t i2 = FLAG): 1352 cdef bitarrtype *ewah_keys = <bitarrtype *> self.ewah_keys 1353 cdef bitarrtype *ewah_refn = <bitarrtype *> self.ewah_refn 1354 cdef ewah_map *ewah_coll = <ewah_map *> self.ewah_coll 1355 ewah_keys[i1] = 1 1356 # Note the 0 here, for dereferencing 1357 if i2 != FLAG: 1358 ewah_refn[i1] = 1 1359 ewah_coll[0][i1].set(i2) 1360 1361 cdef void _set_coarse(self, np.uint64_t i1): 1362 cdef bitarrtype *ewah_keys = <bitarrtype *> self.ewah_keys 1363 ewah_keys[i1] = 1 1364 1365 cdef void _set_refined(self, np.uint64_t i1, np.uint64_t i2): 1366 cdef bitarrtype *ewah_refn = <bitarrtype *> self.ewah_refn 1367 cdef ewah_map *ewah_coll = <ewah_map *> self.ewah_coll 1368 # Note the 0 here, for dereferencing 1369 ewah_refn[i1] = 1 1370 ewah_coll[0][i1].set(i2) 1371 1372 @cython.boundscheck(False) 1373 @cython.wraparound(False) 1374 @cython.cdivision(True) 1375 @cython.initializedcheck(False) 1376 cdef void _set_coarse_array(self, np.uint8_t[:] arr): 1377 cdef bitarrtype *ewah_keys = <bitarrtype *> self.ewah_keys 1378 cdef np.uint64_t i1 1379 for i1 in range(arr.shape[0]): 1380 if arr[i1] == 1: 1381 ewah_keys[i1] = 1 1382 1383 @cython.boundscheck(False) 1384 @cython.wraparound(False) 1385 @cython.cdivision(True) 1386 @cython.initializedcheck(False) 1387 cdef void _set_coarse_array_ptr(self, np.uint8_t *arr): 1388 # TODO: memcpy? 1389 cdef bitarrtype *ewah_keys = <bitarrtype *> self.ewah_keys 1390 cdef np.uint64_t i1 1391 for i1 in range(self.nele1): 1392 if arr[i1] == 1: 1393 ewah_keys[i1] = 1 1394 1395 @cython.boundscheck(False) 1396 @cython.wraparound(False) 1397 @cython.cdivision(True) 1398 @cython.initializedcheck(False) 1399 cdef void _set_refined_array(self, np.uint64_t i1, np.uint8_t[:] arr): 1400 cdef bitarrtype *ewah_refn = <bitarrtype *> self.ewah_refn 1401 cdef ewah_map *ewah_coll = <ewah_map *> self.ewah_coll 1402 cdef np.uint64_t i2 1403 for i2 in range(arr.shape[0]): 1404 if arr[i2] == 1: 1405 ewah_refn[i1] = 1 1406 ewah_coll[0][i1].set(i2) 1407 1408 @cython.boundscheck(False) 1409 @cython.wraparound(False) 1410 @cython.cdivision(True) 1411 @cython.initializedcheck(False) 1412 cdef void _set_refined_array_ptr(self, np.uint64_t i1, np.uint8_t *arr): 1413 cdef bitarrtype *ewah_refn = <bitarrtype *> self.ewah_refn 1414 cdef ewah_map *ewah_coll = <ewah_map *> self.ewah_coll 1415 cdef np.uint64_t i2 1416 cdef ewah_bool_array *barr = &ewah_coll[0][i1] 1417 for i2 in range(self.nele2): 1418 if arr[i2] == 1: 1419 ewah_refn[i1] = 1 1420 barr.set(i2) 1421 1422 cdef void _set_map(self, np.uint64_t i1, np.uint64_t i2): 1423 cdef ewah_map *ewah_coll = <ewah_map *> self.ewah_coll 1424 ewah_coll[0][i1].set(i2) 1425 1426 cdef void _set_refn(self, np.uint64_t i1): 1427 cdef bitarrtype *ewah_refn = <bitarrtype *> self.ewah_refn 1428 ewah_refn[i1] = 1 1429 1430 cdef bint _get(self, np.uint64_t i1, np.uint64_t i2 = FLAG): 1431 cdef bitarrtype *ewah_keys = <bitarrtype *> self.ewah_keys 1432 cdef bitarrtype *ewah_refn = <bitarrtype *> self.ewah_refn 1433 cdef ewah_map *ewah_coll = <ewah_map *> self.ewah_coll 1434 # Note the 0 here, for dereferencing 1435 if ewah_keys[i1] == 0: return 0 1436 if (ewah_refn[i1] == 0) or (i2 == FLAG): 1437 return 1 1438 return ewah_coll[0][i1].get(i2) 1439 1440 cdef bint _get_coarse(self, np.uint64_t i1): 1441 cdef bitarrtype *ewah_keys = <bitarrtype *> self.ewah_keys 1442 return <bint>ewah_keys[i1] 1443 # if (ewah_keys[i1] == 0): return 0 1444 # return 1 1445 1446 cdef bint _isref(self, np.uint64_t i): 1447 cdef bitarrtype *ewah_refn = <bitarrtype *> self.ewah_refn 1448 return <bint>ewah_refn[i] 1449 1450 cdef np.uint64_t _count_total(self): 1451 cdef bitarrtype *ewah_keys = <bitarrtype *> self.ewah_keys 1452 cdef np.uint64_t i 1453 cdef np.uint64_t out = 0 1454 for i in range(self.nele1): 1455 out += ewah_keys[i] 1456 return out 1457 1458 cdef np.uint64_t _count_refined(self): 1459 cdef bitarrtype *ewah_refn = <bitarrtype *> self.ewah_refn 1460 cdef np.uint64_t i 1461 cdef np.uint64_t out = 0 1462 for i in range(self.nele1): 1463 out += ewah_refn[i] 1464 return out 1465 1466 cdef void _append(self, BoolArrayCollectionUncompressed solf): 1467 cdef bitarrtype *ewah_keys1 = <bitarrtype *> self.ewah_keys 1468 cdef bitarrtype *ewah_refn1 = <bitarrtype *> self.ewah_refn 1469 cdef bitarrtype *ewah_keys2 = <bitarrtype *> solf.ewah_keys 1470 cdef bitarrtype *ewah_refn2 = <bitarrtype *> solf.ewah_refn 1471 cdef ewahmap *ewah_coll1 = <ewahmap *> self.ewah_coll 1472 cdef ewahmap *ewah_coll2 = <ewahmap *> solf.ewah_coll 1473 cdef ewahmap_it it_map1, it_map2 1474 cdef ewah_bool_array swap, mi1_ewah1, mi1_ewah2 1475 cdef np.uint64_t mi1 1476 # TODO: Check if nele1 is equal? 1477 # Keys 1478 for mi1 in range(solf.nele1): 1479 if ewah_keys2[mi1] == 1: 1480 ewah_keys1[mi1] = 1 1481 # Refined 1482 for mi1 in range(solf.nele1): 1483 if ewah_refn2[mi1] == 1: 1484 ewah_refn1[mi1] = 1 1485 # Map 1486 it_map2 = ewah_coll2[0].begin() 1487 while it_map2 != ewah_coll2[0].end(): 1488 mi1 = dereference(it_map2).first 1489 mi1_ewah2 = dereference(it_map2).second 1490 it_map1 = ewah_coll1[0].find(mi1) 1491 if it_map1 == ewah_coll1[0].end(): 1492 ewah_coll1[0][mi1] = mi1_ewah2 1493 else: 1494 mi1_ewah1 = dereference(it_map1).second 1495 mi1_ewah1.logicalor(mi1_ewah2, swap) 1496 mi1_ewah1.swap(swap) 1497 preincrement(it_map2) 1498 1499 cdef bint _intersects(self, BoolArrayCollectionUncompressed solf): 1500 cdef bitarrtype *ewah_keys1 = <bitarrtype *> self.ewah_keys 1501 cdef bitarrtype *ewah_refn1 = <bitarrtype *> self.ewah_refn 1502 cdef bitarrtype *ewah_keys2 = <bitarrtype *> solf.ewah_keys 1503 cdef bitarrtype *ewah_refn2 = <bitarrtype *> solf.ewah_refn 1504 cdef ewahmap *ewah_coll1 = <ewahmap *> self.ewah_coll 1505 cdef ewahmap *ewah_coll2 = <ewahmap *> solf.ewah_coll 1506 cdef ewahmap_it it_map1, it_map2 1507 cdef ewah_bool_array mi1_ewah1, mi1_ewah2 1508 cdef np.uint64_t mi1 1509 # No intersection 1510 for mi1 in range(self.nele1): 1511 if (ewah_keys1[mi1] == 1) and (ewah_keys2[mi1] == 1): 1512 break 1513 if (mi1 < self.nele1): 1514 return 0 1515 mi1 = self.nele1 # This is to get rid of a warning 1516 # Intersection at refined level 1517 for mi1 in range(self.nele1): 1518 if (ewah_refn1[mi1] == 1) and (ewah_refn2[mi1] == 1): 1519 it_map1 = ewah_coll1[0].begin() 1520 while (it_map1 != ewah_coll1[0].end()): 1521 mi1 = dereference(it_map1).first 1522 it_map2 = ewah_coll2[0].find(mi1) 1523 if it_map2 != ewah_coll2[0].end(): 1524 mi1_ewah1 = dereference(it_map1).second 1525 mi1_ewah2 = dereference(it_map2).second 1526 if mi1_ewah1.intersects(mi1_ewah2): 1527 return 1 1528 preincrement(it_map1) 1529 break 1530 # Intersection at coarse level or refined inside coarse 1531 if mi1 == self.nele1: 1532 return 1 1533 return 0 1534 1535 def __dealloc__(self): 1536 cdef bitarrtype *ewah_keys = <bitarrtype *> self.ewah_keys 1537 cdef bitarrtype *ewah_refn = <bitarrtype *> self.ewah_refn 1538 free(ewah_keys) 1539 free(ewah_refn) 1540 cdef ewah_map *ewah_coll = <ewah_map *> self.ewah_coll 1541 del ewah_coll 1542 1543 def print_info(self, prefix=''): 1544 cdef np.uint64_t nrefn = self._count_refined() 1545 cdef np.uint64_t nkeys = self._count_total() 1546 print("{}{: 8d} coarse, {: 8d} refined, {: 8d} total".format(prefix, 1547 nkeys - nrefn, 1548 nrefn, 1549 nkeys)) 1550 1551 1552 1553# Vector version 1554cdef class SparseUnorderedBitmaskVector: 1555 def __cinit__(self): 1556 self.total = 0 1557 1558 cdef void _set(self, np.uint64_t ind): 1559 self.entries.push_back(ind) 1560 self.total += 1 1561 1562 def set(self, ind): 1563 self._set(ind) 1564 1565 cdef void _fill(self, np.uint8_t[:] mask): 1566 cdef np.uint64_t i, ind 1567 for i in range(self.entries.size()): 1568 ind = self.entries[i] 1569 mask[ind] = 1 1570 1571 cdef void _fill_ewah(self, BoolArrayCollection mm): 1572 self._remove_duplicates() 1573 cdef np.uint64_t i, ind 1574 for i in range(self.entries.size()): 1575 ind = self.entries[i] 1576 mm._set_coarse(ind) 1577 1578 cdef void _fill_bool(self, BoolArrayCollectionUncompressed mm): 1579 self._remove_duplicates() 1580 cdef np.uint64_t i, ind 1581 for i in range(self.entries.size()): 1582 ind = self.entries[i] 1583 mm._set_coarse(ind) 1584 1585 cdef void _reset(self): 1586 self.entries.erase(self.entries.begin(), self.entries.end()) 1587 self.total = 0 1588 1589 cdef to_array(self): 1590 self._remove_duplicates() 1591 cdef np.ndarray[np.uint64_t, ndim=1] rv 1592 rv = np.empty(self.entries.size(), dtype='uint64') 1593 for i in range(self.entries.size()): 1594 rv[i] = self.entries[i] 1595 return rv 1596 1597 cdef void _remove_duplicates(self): 1598 cdef vector[np.uint64_t].iterator last 1599 sort(self.entries.begin(), self.entries.end()) 1600 last = unique(self.entries.begin(), self.entries.end()) 1601 self.entries.erase(last, self.entries.end()) 1602 1603 cdef void _prune(self): 1604 if self.total > MAX_VECTOR_SIZE: 1605 self._remove_duplicates() 1606 self.total = 0 1607 1608 def __dealloc__(self): 1609 self.entries.clear() 1610 1611# Set version 1612cdef class SparseUnorderedBitmaskSet: 1613 cdef void _set(self, np.uint64_t ind): 1614 self.entries.insert(ind) 1615 1616 def set(self, ind): 1617 self._set(ind) 1618 1619 cdef void _fill(self, np.uint8_t[:] mask): 1620 for it in self.entries: 1621 mask[it] = 1 1622 1623 cdef void _fill_ewah(self, BoolArrayCollection mm): 1624 for it in self.entries: 1625 mm._set_coarse(it) 1626 1627 cdef void _fill_bool(self, BoolArrayCollectionUncompressed mm): 1628 for it in self.entries: 1629 mm._set_coarse(it) 1630 1631 cdef void _reset(self): 1632 self.entries.clear() 1633 1634 cdef to_array(self): 1635 cdef np.uint64_t ind 1636 cdef np.ndarray[np.uint64_t, ndim=1] rv 1637 cdef cset[np.uint64_t].iterator it 1638 rv = np.empty(self.entries.size(), dtype='uint64') 1639 it = self.entries.begin() 1640 i = 0 1641 while it != self.entries.end(): 1642 ind = dereference(it) 1643 rv[i] = ind 1644 preincrement(it) 1645 i += 1 1646 return rv 1647 1648 def __dealloc__(self): 1649 self.entries.clear() 1650 1651# vector version 1652cdef class SparseUnorderedRefinedBitmaskVector: 1653 def __cinit__(self): 1654 self.total = 0 1655 1656 cdef void _set(self, np.uint64_t ind1, np.uint64_t ind2): 1657 cdef ind_pair ind 1658 ind.first = ind1 1659 ind.second = ind2 1660 self.entries.push_back(ind) 1661 self.total += 1 1662 1663 def set(self, ind1, ind2): 1664 self._set(ind1, ind2) 1665 1666 cdef void _fill(self, np.uint8_t[:] mask1, np.uint8_t[:] mask2): 1667 for it in self.entries: 1668 mask1[it.first] = mask2[it.second] = 1 1669 1670 cdef void _fill_ewah(self, BoolArrayCollection mm): 1671 self._remove_duplicates() 1672 for it in self.entries: 1673 mm._set_refined(it.first, it.second) 1674 1675 cdef void _fill_bool(self, BoolArrayCollectionUncompressed mm): 1676 self._remove_duplicates() 1677 for it in self.entries: 1678 mm._set_refined(it.first, it.second) 1679 1680 cdef void _reset(self): 1681 self.entries.erase(self.entries.begin(), self.entries.end()) 1682 self.total = 0 1683 1684 cdef to_array(self): 1685 cdef np.uint64_t i 1686 cdef np.ndarray[np.uint64_t, ndim=2] rv 1687 self._remove_duplicates() 1688 rv = np.empty((self.entries.size(),2),dtype='uint64') 1689 i = 0 1690 for it in self.entries: 1691 rv[i,0] = it.first 1692 rv[i,1] = it.second 1693 i += 1 1694 return rv 1695 1696 cdef void _remove_duplicates(self): 1697 cdef vector[ind_pair].iterator last 1698 sort(self.entries.begin(), self.entries.end()) 1699 last = unique(self.entries.begin(), self.entries.end()) 1700 self.entries.erase(last, self.entries.end()) 1701 # http://stackoverflow.com/questions/16970982/find-unique-rows-in-numpy-array 1702 # cdef np.ndarray[np.uint64_t, ndim=2] rv 1703 # cdef np.ndarray[np.uint64_t, ndim=2] rv_uni 1704 # cdef np.uint64_t m 1705 # cdef vector[np.uint64_t].iterator last1 1706 # cdef vector[np.uint64_t].iterator last2 1707 # # cdef np.ndarray[np.uint64_t, ndim=1] _ 1708 # cdef vector[np.uint64_t] *entries1 = <vector[np.uint64_t]*> self.entries1 1709 # cdef vector[np.uint64_t] *entries2 = <vector[np.uint64_t]*> self.entries2 1710 # rv = np.empty((entries1[0].size(),2),dtype='uint64') 1711 # for i in range(entries1[0].size()): 1712 # rv[i,0] = entries1[0][i] 1713 # rv[i,1] = entries2[0][i] 1714 # rv_uni = np.unique(np.ascontiguousarray(rv).view(np.dtype((np.void, rv.dtype.itemsize * rv.shape[1])))).view(rv.dtype).reshape(-1,rv.shape[1]) 1715 # last1 = entries1[0].begin() + rv_uni.shape[0] 1716 # last2 = entries2[0].begin() + rv_uni.shape[0] 1717 # for m in range(rv_uni.shape[0]): 1718 # entries1[0][m] = rv_uni[m,0] 1719 # entries2[0][m] = rv_uni[m,1] 1720 # entries1[0].erase(last1, entries1[0].end()) 1721 # entries2[0].erase(last2, entries2[0].end()) 1722 1723 cdef void _prune(self): 1724 if self.total > MAX_VECTOR_SIZE: 1725 self._remove_duplicates() 1726 self.total = 0 1727 1728 def __dealloc__(self): 1729 self.entries.clear() 1730 1731# Set version 1732cdef class SparseUnorderedRefinedBitmaskSet: 1733 cdef void _set(self, np.uint64_t ind1, np.uint64_t ind2): 1734 cdef ind_pair ind 1735 ind.first = ind1 1736 ind.second = ind2 1737 self.entries.insert(ind) 1738 1739 def set(self, ind1, ind2): 1740 self._set(ind1, ind2) 1741 1742 cdef void _fill(self, np.uint8_t[:] mask1, np.uint8_t[:] mask2): 1743 for p in self.entries: 1744 mask1[p.first] = mask2[p.second] = 1 1745 1746 cdef void _fill_ewah(self, BoolArrayCollection mm): 1747 for it in self.entries: 1748 mm._set_refined(it.first, it.second) 1749 1750 cdef void _fill_bool(self, BoolArrayCollectionUncompressed mm): 1751 for it in self.entries: 1752 mm._set_refined(it.first, it.second) 1753 1754 cdef void _reset(self): 1755 self.entries.clear() 1756 1757 cdef to_array(self): 1758 cdef np.uint64_t i 1759 cdef np.ndarray[np.uint64_t, ndim=2] rv 1760 rv = np.empty((self.entries.size(),2),dtype='uint64') 1761 i = 0 1762 for it in self.entries: 1763 rv[i,0] = it.first 1764 rv[i,1] = it.second 1765 i += 1 1766 return rv 1767 1768 def __dealloc__(self): 1769 self.entries.clear() 1770