dlvhex  2.5.0
vs12/bm/bmconst.h
Go to the documentation of this file.
00001 #ifndef BMCONST__H__INCLUDED__
00002 #define BMCONST__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 namespace bm
00030 {
00031 
00032 #if defined(_WIN32) || defined (_WIN64)
00033 
00034 typedef unsigned __int64 id64_t;
00035 
00036 #else
00037 
00038 typedef unsigned long long id64_t;
00039 
00040 #endif
00041 
00042 typedef unsigned int   id_t;
00043 typedef unsigned int   word_t;
00044 typedef unsigned short short_t;
00045 
00046 
00047 
00048 const unsigned id_max = 0xFFFFFFFF;
00049 
00050 // Data Block parameters
00051 
00052 const unsigned set_block_size  = 2048u;
00053 const unsigned set_block_shift = 16u;
00054 const unsigned set_block_mask  = 0xFFFFu;
00055 const unsigned set_blkblk_mask = 0xFFFFFFu;
00056 
00057 const unsigned set_block_plain_size = set_block_size / 32u;
00058 const unsigned set_block_plain_cnt = sizeof(bm::word_t) * 8u;
00059 
00060 // Word parameters
00061 
00062 const unsigned set_word_shift = 5u;
00063 const unsigned set_word_mask  = 0x1Fu;
00064 
00065 
00066 // GAP related parameters.
00067 
00068 typedef unsigned short gap_word_t;
00069 
00070 const unsigned gap_max_buff_len = 1280;
00071 const unsigned gap_length_threashold = set_block_size * 3; // should be 2-3 bits per word
00072 const unsigned gap_max_bits = 65536;
00073 const unsigned gap_equiv_len = 
00074    (sizeof(bm::word_t) * bm::set_block_size) / sizeof(gap_word_t);
00075 const unsigned gap_levels = 4;
00076 const unsigned gap_max_level = bm::gap_levels - 1;
00077 
00078 
00079 // Block Array parameters
00080 
00081 const unsigned set_array_size = 256u;
00082 const unsigned set_array_shift = 8u;
00083 const unsigned set_array_mask  = 0xFFu;
00084 const unsigned set_total_blocks = (bm::set_array_size * bm::set_array_size);
00085 
00086 const unsigned bits_in_block = bm::set_block_size * sizeof(bm::word_t) * 8;
00087 const unsigned bits_in_array = bm::bits_in_block * bm::set_array_size;
00088 
00089 
00090 #ifdef BM64OPT
00091 
00092 typedef id64_t  wordop_t;
00093 const id64_t    all_bits_mask = 0xffffffffffffffff;
00094 
00095 # define DECLARE_TEMP_BLOCK(x)  bm::id64_t x[bm::set_block_size / 2]; 
00096 const unsigned set_block_size_op  = bm::set_block_size / 2;
00097 
00098 
00099 #else
00100 
00101 typedef word_t wordop_t;
00102 const word_t all_bits_mask = 0xffffffff;
00103 
00104 # define DECLARE_TEMP_BLOCK(x)  unsigned x[bm::set_block_size]; 
00105 const unsigned set_block_size_op  = bm::set_block_size;
00106 
00107 #endif
00108 
00109 
00110 
00115 enum strategy
00116 {
00117     BM_BIT = 0, 
00118     BM_GAP = 1  
00119 };
00120 
00121 
00126 enum set_representation
00127 {
00128     set_bitset  = 0,  
00129     set_gap     = 1,  
00130     set_array1  = 2,  
00131     set_array0  = 3   
00132 };
00133 
00134 template<bool T> struct DeBruijn_bit_position
00135 {
00136     static const unsigned _multiply[32];
00137 };
00138 
00139 template<bool T>
00140 const unsigned DeBruijn_bit_position<T>::_multiply[32] = { 
00141   0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8, 
00142   31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
00143 };
00144 
00148 template<bool T> struct first_bit_table
00149 {
00150     static const char _idx[256];
00151 };
00152 
00153 template<bool T>
00154 const char first_bit_table<T>::_idx[256] = {
00155   -1, 0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3,
00156     4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
00157     5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
00158     5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
00159     6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
00160     6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
00161     6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
00162     6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
00163     7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
00164     7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
00165     7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
00166     7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
00167     7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
00168     7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
00169     7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
00170     7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
00171 };
00172 
00173 //---------------------------------------------------------------------
00174 
00180 template<bool T> struct bit_count_table 
00181 {
00182   static const unsigned char _count[256];
00183 };
00184 
00185 template<bool T>
00186 const unsigned char bit_count_table<T>::_count[256] = {
00187     0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
00188     1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
00189     1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
00190     2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
00191     1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
00192     2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
00193     2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
00194     3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8
00195 };
00196 
00197 
00198 } // namespace
00199 
00200 #endif
00201