dlvhex  2.5.0
vs10/bm/bmdbg.h
Go to the documentation of this file.
00001 #ifndef BMDBG__H__INCLUDED__
00002 #define BMDBG__H__INCLUDED__
00003 /*
00004 Copyright(c) 2002-2009 Anatoliy Kuznetsov(anatoliy_kuznetsov at yahoo.com)
00005 
00006 Permission is hereby granted, free of charge, to any person 
00007 obtaining a copy of this software and associated documentation 
00008 files (the "Software"), to deal in the Software without restriction, 
00009 including without limitation the rights to use, copy, modify, merge, 
00010 publish, distribute, sublicense, and/or sell copies of the Software, 
00011 and to permit persons to whom the Software is furnished to do so, 
00012 subject to the following conditions:
00013 
00014 The above copyright notice and this permission notice shall be included 
00015 in all copies or substantial portions of the Software.
00016 
00017 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 
00018 EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES 
00019 OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. 
00020 IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, 
00021 DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, 
00022 ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR 
00023 OTHER DEALINGS IN THE SOFTWARE.
00024 
00025 For more information please visit:  http://bmagic.sourceforge.net
00026 
00027 */
00028 
00029 // BitMagic debugging functions (internal header)
00030 #ifdef _MSC_VER
00031 #pragma warning( push )
00032 #pragma warning( disable : 4996)
00033 #endif
00034 
00035 #include <stdio.h>
00036 #include <stdlib.h>
00037 #include <cassert>
00038 #include <memory.h>
00039 #include <iostream>
00040 #include <fstream>
00041 #include <iomanip>
00042 #include <time.h>
00043 
00044 #include "bmdef.h"
00045 
00046 
00047 using namespace std;
00048 
00049 #ifdef _MSC_VER
00050 #pragma warning( push )
00051 #pragma warning( disable : 4311 4312 4127)
00052 #endif
00053 
00054 
00055 inline
00056 void PrintGap(const bm::gap_word_t* gap_buf)
00057 {
00058     unsigned len = (*gap_buf >> 3);
00059     cout << "[" << *gap_buf << " len=" << len << "] ";
00060     for (unsigned i = 0; i < len; ++i)
00061     {
00062         ++gap_buf;
00063         cout << *gap_buf << "; ";
00064     } 
00065     cout << endl;
00066 }
00067 
00068 inline
00069 void PrintDGap(const bm::gap_word_t* gap_buf, unsigned gap_len=0)
00070 {
00071     bm::gap_word_t h;
00072     memcpy(&h, gap_buf, sizeof(h));
00073 
00074     unsigned len = gap_len ? gap_len : (h >> 3);
00075     cout << "[" " len=" << len << "] ";
00076     unsigned i = gap_len ? 0 : 1;
00077     for (; i < len; ++i)
00078     {
00079         cout << gap_buf[i] << "; ";
00080     } 
00081     cout << endl;
00082 }
00083 
00084 inline unsigned int iLog2(unsigned int value)
00085 {
00086     unsigned int l = 0;
00087     while( (value >> l) > 1 ) ++l;
00088     return l;
00089 }
00090 
00091 inline
00092 unsigned PrintGammaCode(unsigned value)
00093 {
00094     unsigned bits = 0;
00095     // Elias gamma encode
00096     {
00097         unsigned l = iLog2(value);
00098         //cout << "log2=" << l << endl;
00099         for (unsigned i = 0; i < l; ++i)
00100         {
00101             cout << 0;
00102             ++bits;
00103         }
00104         cout << 1; ++bits;
00105         for (unsigned i = 0; i < l; ++i)
00106         {
00107             if (value & 1 << i) 
00108                 cout << 1;
00109             else
00110                 cout << 0;
00111             ++bits;
00112         }
00113     }
00114     return bits;
00115 }
00116 
00117 inline 
00118 void PrintDGapGamma(const bm::gap_word_t* gap_buf, unsigned gap_len=0)
00119 {
00120     unsigned total = 0;
00121     bm::gap_word_t h;
00122     memcpy(&h, gap_buf, sizeof(h));
00123     unsigned len = gap_len ? gap_len : (h >> 3);
00124     cout << "[" " len=" << len << "] ";
00125     unsigned i = gap_len ? 0 : 1;
00126     for (; i < len; ++i)
00127     {
00128         unsigned v = gap_buf[i];
00129 
00130         unsigned bits = PrintGammaCode(v+1);
00131         cout << "; ";
00132         total += bits;
00133     } 
00134     cout << "  gamma_bits=" << total << " src_bits =" << len * 16;
00135     cout << endl;
00136 
00137 }
00138 
00139 template<class TBV>
00140 void LoadBVector(const char* fname, TBV& bvector, unsigned* file_size=0)
00141 {
00142     ifstream bv_file (fname, ios::in | ios::binary);
00143     if (!bv_file.good())
00144     {
00145         cout << "Cannot open file: " << fname << endl;
00146         exit(1);
00147     }
00148     bv_file.seekg(0, ios_base::end);
00149     unsigned length = bv_file.tellg();
00150     if (length == 0)
00151     {
00152         cout << "Empty file:" << fname << endl;
00153         exit(1);
00154     }
00155     if (file_size)
00156         *file_size = length;
00157         
00158     bv_file.seekg(0, ios::beg);
00159     
00160     char* buffer = new char[length];
00161 
00162     bv_file.read(buffer, length);
00163     
00164     bm::deserialize(bvector, (unsigned char*)buffer);
00165     
00166     delete [] buffer;
00167 }
00168 
00169 template<class TBV>
00170 void SaveBVector(const char* fname, const TBV& bvector)
00171 {
00172     ofstream bfile (fname, ios::out | ios::binary);
00173     if (!bfile.good())
00174     {
00175         cout << "Cannot open file: " << fname << endl;
00176         exit(1);
00177     }
00178     typename TBV::statistics st1;
00179     bvector.calc_stat(&st1);
00180 
00181     unsigned char* blob = new unsigned char[st1.max_serialize_mem];
00182    unsigned blob_size = bm::serialize(bvector, blob);
00183 
00184 
00185     bfile.write((char*)blob, blob_size);
00186     bfile.close();
00187 
00188     delete [] blob;
00189 }
00190 
00191 inline
00192 void SaveBlob(const char* name_prefix, unsigned num, const char* ext,
00193               const unsigned char* blob, unsigned blob_size)
00194 {
00195     char fname[2048];
00196     sprintf(fname, "%s-%u.%s", name_prefix, num, ext);
00197     ofstream bfile (fname, ios::out | ios::binary);
00198     if (!bfile.good())
00199     {
00200         cout << "Cannot open file: " << fname << endl;
00201         exit(1);
00202     }
00203     bfile.write((char*)blob, blob_size);
00204     bfile.close();
00205 }
00206 
00207 
00208 template<typename V> 
00209 void PrintBinary(V val)
00210 {
00211     for (unsigned i = 0; i < sizeof(V)*8; i++)
00212     {
00213         cout << (unsigned)((val >> i) & 1);
00214         if (i == 15 && (sizeof(V)*8 > 16)) cout << "-";
00215     }
00216 //    cout << " :" << val;
00217 }
00218 
00219 inline 
00220 void PrintBits32(unsigned val)
00221 {
00222     PrintBinary(val);
00223 }
00224 
00225 void PrintDistanceMatrix(
00226    const unsigned distance[bm::set_block_plain_cnt][bm::set_block_plain_cnt])
00227 {
00228     for (unsigned i = 0; i < bm::set_block_plain_cnt; ++i)
00229     {
00230         const unsigned* row = distance[i];
00231         cout << i << ": ";
00232         for (unsigned j = i; j < bm::set_block_plain_cnt; ++j)
00233         {
00234             cout << setw(4) << setfill('0') << row[j] << " ";
00235         }
00236         cout << endl;
00237     }
00238 }
00239 
00240 template<typename TM>
00241 void PrintTMatrix(const TM& tmatrix, unsigned cols=0, bool binary = false)
00242 {
00243     unsigned columns = cols ? cols : tmatrix.cols();
00244     for (unsigned i = 0; i < tmatrix.rows(); ++i)
00245     {
00246         const typename TM::value_type* row = tmatrix.row(i);
00247         cout << i << ": ";
00248         if (i < 10) cout << " ";
00249         for (unsigned j = 0; j < columns; ++j)
00250         {
00251             if (!binary)
00252             {
00253                 cout << setw(4) << setfill('0') << row[j] << " ";
00254             }
00255             else
00256             {
00257                 PrintBinary(row[j]);
00258             }
00259         }
00260         cout << endl;
00261     }
00262 }
00263 
00267 inline
00268 unsigned BinStrLR(const char* str)
00269 {
00270     unsigned value = 0;
00271     unsigned bit_idx = 0;
00272     for (; *str; ++str)
00273     {
00274         switch(*str)
00275         {
00276         case '0': 
00277             ++bit_idx;
00278             break;
00279         case '1':
00280             value |= (1 << bit_idx);
00281             ++bit_idx;
00282             break;
00283         default:
00284             assert(0);
00285         }
00286         if (bit_idx == sizeof(unsigned) * 8) 
00287             break;
00288     }    
00289     return value;
00290 }
00291 
00292 template<class BV>
00293 void print_blocks_count(const BV& bv)
00294 {
00295     const unsigned sz = 128000;
00296     unsigned* bc_arr = new unsigned[sz];
00297     for(unsigned x = 0; x < sz; ++x) bc_arr[x] = 0;
00298 
00299 
00300     unsigned last_block = bv.count_blocks(bc_arr);
00301     unsigned sum = 0;
00302 
00303     for (unsigned i = 0; i <= last_block; ++i)
00304     {
00305         cout << i << ":";
00306 
00307         unsigned j = 0;
00308         for (; i <= last_block; ++i)
00309         {
00310             cout << setw(5) << setfill('0') << bc_arr[i] << " ";
00311             sum += bc_arr[i];
00312             if (++j == 10) break;
00313         }
00314         cout << " | " << sum << endl;
00315     }
00316     cout << "Total=" << sum << endl;
00317 
00318     delete [] bc_arr;
00319 }
00320 inline 
00321 void print_bc(unsigned i, unsigned count)
00322 {
00323     static unsigned sum = 0;
00324     static unsigned row_idx = 0;
00325     static unsigned prev = 0;
00326 
00327     if (i == 0) 
00328     {
00329         sum = row_idx = 0;
00330     }
00331     else
00332     {
00333         if (prev +1 < i)
00334             print_bc(prev+1, 0);
00335         prev = i;
00336     }
00337 
00338     if (row_idx == 0)
00339     {
00340         std::cout << i << ":";
00341     }
00342 
00343     std::cout << std::setw(5) << std::setfill('0') << count << " ";
00344     sum += count;
00345 
00346     ++row_idx;
00347     if (row_idx == 10)
00348     {
00349         row_idx = 0;
00350         std::cout << " | " << sum << std::endl;
00351     }
00352 }
00353 
00354 
00355 template<class BV>
00356 void print_stat(const BV& bv, unsigned blocks = 0)
00357 {
00358     const typename BV::blocks_manager_type& bman = bv.get_blocks_manager();
00359 
00360     bm::id_t count = 0;
00361     int printed = 0;
00362 
00363     int total_gap_eff = 0;
00364 
00365     if (!blocks)
00366     {
00367         blocks = bm::set_total_blocks;
00368     }
00369 
00370     unsigned nb;
00371     unsigned nb_prev = 0;
00372     for (nb = 0; nb < blocks; ++nb)
00373     {
00374         const bm::word_t* blk = bman.get_block(nb);
00375         if (blk == 0)
00376         {
00377            continue;
00378         }
00379 
00380         if (IS_FULL_BLOCK(blk))
00381         {
00382            if (bman.is_block_gap(nb)) // gap block
00383            {
00384                printf("[Alert!%i]", nb);
00385                assert(0);
00386            }
00387            
00388            unsigned start = nb; 
00389            for(unsigned i = nb+1; i < bm::set_total_blocks; ++i, ++nb)
00390            {
00391                blk = bman.get_block(nb);
00392                if (IS_FULL_BLOCK(blk))
00393                {
00394                  if (bman.is_block_gap(nb)) // gap block
00395                  {
00396                      printf("[Alert!%i]", nb);
00397                      assert(0);
00398                      --nb;
00399                      break;
00400                  }
00401 
00402                }
00403                else
00404                {
00405                   --nb;
00406                   break;
00407                }
00408            }
00409 
00410            printf("{F.%i:%i}",start, nb);
00411            ++printed;
00412         }
00413         else
00414         {
00415             if ((nb-1) != nb_prev)
00416             {
00417                 printf("..%i..", (int)nb-nb_prev);
00418             }
00419 
00420             if (bman.is_block_gap(nb)) // gap block
00421             {
00422                 unsigned bc = bm::gap_bit_count(BMGAP_PTR(blk));
00423                 /*unsigned sum = */bm::gap_control_sum(BMGAP_PTR(blk));
00424                 unsigned level = bm::gap_level(BMGAP_PTR(blk));
00425                 count += bc;
00426                unsigned len = bm::gap_length(BMGAP_PTR(blk))-1;
00427                unsigned raw_size=bc*2;
00428                unsigned cmr_len=len*2;
00429                int mem_eff = raw_size - cmr_len;
00430                total_gap_eff += mem_eff;
00431                
00432                unsigned i,j;
00433                bman.get_block_coord(nb, &i, &j);
00434                 printf(" [GAP %i(%i,%i)=%i:%i-L%i(%i)] ", nb, i, j, bc, level, len, mem_eff);
00435                 ++printed;
00436             }
00437             else // bitset
00438             {
00439                 const bm::word_t* blk_end = blk + bm::set_block_size;
00440                 unsigned bc = bm::bit_block_calc_count(blk, blk_end);
00441 
00442                 unsigned zw = 0;
00443                 for (unsigned i = 0; i < bm::set_block_size; ++i) 
00444                 {
00445                     zw += (blk[i] == 0);
00446                 }
00447 
00448                 count += bc;
00449                 printf(" (BIT %i=%i[%i]) ", nb, bc, zw);
00450                 ++printed;                
00451             }
00452         }
00453         if (printed == 10)
00454         {
00455             printed = 0;
00456             printf("\n");
00457         }
00458         nb_prev = nb;
00459     } // for nb
00460     printf("\n");
00461     printf("gap_efficiency=%i\n", total_gap_eff); 
00462 
00463 }
00464 
00465 #include "bmundef.h"
00466 
00467 
00468 #ifdef _MSC_VER
00469 #pragma warning( pop )
00470 #endif
00471 
00472 #endif