Home | History | Annotate | Download | only in src 
      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 }