1f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com#include "Bitvec.h" 2f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com#include <vector> 3f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com#include <assert.h> 4f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 5f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com// handle xnor 6f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 7f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.comtypedef std::vector<uint32_t> slice; 8f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.comtypedef std::vector<slice> slice_vec; 9f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 10f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.comint countbits ( slice & v ) 11f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com{ 12f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com int c = 0; 13f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 14f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com for(size_t i = 0; i < v.size(); i++) 15f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com { 16f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com int d = countbits(v[i]); 17f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 18f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com c += d; 19f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com } 20f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 21f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com return c; 22f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com} 23f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 24f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.comint countxor ( slice & a, slice & b ) 25f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com{ 26f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com assert(a.size() == b.size()); 27f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 28f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com int c = 0; 29f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 30f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com for(size_t i = 0; i < a.size(); i++) 31f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com { 32f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com int d = countbits(a[i] ^ b[i]); 33f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 34f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com c += d; 35f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com } 36f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 37f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com return c; 38f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com} 39f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 40f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.comvoid xoreq ( slice & a, slice & b ) 41f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com{ 42f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com assert(a.size() == b.size()); 43f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 44f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com for(size_t i = 0; i < a.size(); i++) 45f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com { 46f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com a[i] ^= b[i]; 47f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com } 48f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com} 49f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 50f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com//----------------------------------------------------------------------------- 51f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com// Bitslice a hash set 52f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 53f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.comtemplate< typename hashtype > 54f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.comvoid Bitslice ( std::vector<hashtype> & hashes, slice_vec & slices ) 55f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com{ 56f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com const int hashbytes = sizeof(hashtype); 57f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com const int hashbits = hashbytes * 8; 58f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com const int slicelen = ((int)hashes.size() + 31) / 32; 59f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 60f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com slices.clear(); 61f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com slices.resize(hashbits); 62f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 63f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com for(int i = 0; i < (int)slices.size(); i++) 64f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com { 65f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com slices[i].resize(slicelen,0); 66f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com } 67f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 68f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com for(int j = 0; j < hashbits; j++) 69f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com { 70f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com void * sliceblob = &(slices[j][0]); 71f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 72f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com for(int i = 0; i < (int)hashes.size(); i++) 73f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com { 74f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com int b = getbit(hashes[i],j); 75f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 76f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com setbit(sliceblob,slicelen*4,i,b); 77f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com } 78f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com } 79f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com} 80f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 81f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.comvoid FactorSlices ( slice_vec & slices ) 82f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com{ 83f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com std::vector<int> counts(slices.size(),0); 84f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 85f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com for(size_t i = 0; i < slices.size(); i++) 86f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com { 87f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com counts[i] = countbits(slices[i]); 88f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com } 89f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 90f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com bool changed = true; 91f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 92f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com while(changed) 93f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com { 94f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com int bestA = -1; 95f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com int bestB = -1; 96f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 97f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com for(int j = 0; j < (int)slices.size()-1; j++) 98f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com { 99f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com for(int i = j+1; i < (int)slices.size(); i++) 100f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com { 101f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com int d = countxor(slices[i],slices[j]); 102f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 103f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com if((d < counts[i]) && (d < counts[j])) 104f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com { 105f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com if(counts[i] < counts[j]) 106f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com { 107f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com bestA = j; 108f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com bestB = i; 109f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com } 110f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com } 111f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com else if(d < counts[i]) 112f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com { 113f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com //bestA = 114f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com } 115f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com } 116f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com } 117f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com } 118f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com} 119f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 120f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 121f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.comvoid foo ( void ) 122f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com{ 123f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com slice a; 124f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com slice_vec b; 125f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 126f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com Bitslice(a,b); 127f67ce942f6432ceb7ced0c3d12370b6376c05c09tanjent@gmail.com}