- Main Page
- Modules
- Namespaces
- Data Structures
- Files
- Examples

- File List
- Globals

# 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
    00111 /*!
    00112    @brief Block allocation strategies.
    00113    @ingroup bvector
    00114 */
    00115 enum strategy
    00116 {
    00117     BM_BIT = 0, //!< No GAP compression strategy. All new blocks are bit blocks.
    00118     BM_GAP = 1  //!< GAP compression is ON.
    00119 };
    00120
    00121
    00122 /*!
    00123     @brief set representation variants
    00124     @internal
    00125 */
    00126 enum set_representation
    00127 {
    00128     set_bitset  = 0,  //!< Simple bitset
    00129     set_gap     = 1,  //!< GAP-RLE compression
    00130     set_array1  = 2,  //!< array of set 1 values
    00131     set_array0  = 3   //!< array of 0 values
    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
    00145 /** Structure keeps index of first right 1 bit for every byte.
    00146     @ingroup bitfunc
    00147 */
    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
    00175 /** Structure to aid in counting bits
    00176     table contains count of bits in 0-255 diapason of numbers
    00177
    00178    @ingroup bitfunc
    00179 */
    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