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