00001 #ifndef BMSERIAL__H__INCLUDED__
00002 #define BMSERIAL__H__INCLUDED__
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036 #ifndef BM__H__INCLUDED__
00037 #define BM__H__INCLUDED__
00038
00039 #include "bm.h"
00040
00041 #endif
00042
00043 #ifdef _MSC_VER
00044 #pragma warning( disable : 4311 4312)
00045 #endif
00046
00047
00048
00049 #include "encoding.h"
00050 #include "bmdef.h"
00051 #include "bmfunc.h"
00052 #include "bmtrans.h"
00053 #include "bmalgo_impl.h"
00054 #include "bmutil.h"
00055
00056
00057
00058
00059 namespace bm
00060 {
00061
00062
00063
00064
00065
00066 const unsigned char set_block_end = 0;
00067 const unsigned char set_block_1zero = 1;
00068 const unsigned char set_block_1one = 2;
00069 const unsigned char set_block_8zero = 3;
00070 const unsigned char set_block_8one = 4;
00071 const unsigned char set_block_16zero = 5;
00072 const unsigned char set_block_16one = 6;
00073 const unsigned char set_block_32zero = 7;
00074 const unsigned char set_block_32one = 8;
00075 const unsigned char set_block_azero = 9;
00076 const unsigned char set_block_aone = 10;
00077 const unsigned char set_block_bit = 11;
00078 const unsigned char set_block_sgapbit = 12;
00079 const unsigned char set_block_sgapgap = 13;
00080 const unsigned char set_block_gap = 14;
00081 const unsigned char set_block_gapbit = 15;
00082 const unsigned char set_block_arrbit = 16;
00083 const unsigned char set_block_bit_interval = 17;
00084 const unsigned char set_block_arrgap = 18;
00085 const unsigned char set_block_bit_1bit = 19;
00086 const unsigned char set_block_gap_egamma = 20;
00087 const unsigned char set_block_arrgap_egamma = 21;
00088 const unsigned char set_block_bit_0runs = 22;
00089 const unsigned char set_block_arrgap_egamma_inv = 23;
00090 const unsigned char set_block_arrgap_inv = 24;
00091
00092
00093
00094
00095 enum serialization_header_mask {
00096 BM_HM_DEFAULT = 1,
00097 BM_HM_RESIZE = (1 << 1),
00098 BM_HM_ID_LIST = (1 << 2),
00099 BM_HM_NO_BO = (1 << 3),
00100 BM_HM_NO_GAPL = (1 << 4)
00101 };
00102
00103
00104
00105 #define SER_NEXT_GRP(enc, nb, B_1ZERO, B_8ZERO, B_16ZERO, B_32ZERO) \
00106 if (nb == 1) \
00107 enc.put_8(B_1ZERO); \
00108 else if (nb < 256) \
00109 { \
00110 enc.put_8(B_8ZERO); \
00111 enc.put_8((unsigned char)nb); \
00112 } \
00113 else if (nb < 65536) \
00114 { \
00115 enc.put_8(B_16ZERO); \
00116 enc.put_16((unsigned short)nb); \
00117 } \
00118 else \
00119 {\
00120 enc.put_8(B_32ZERO); \
00121 enc.put_32(nb); \
00122 }
00123
00124
00125 #define BM_SET_ONE_BLOCKS(x) \
00126 {\
00127 unsigned end_block = i + x; \
00128 for (;i < end_block; ++i) \
00129 bman.set_block_all_set(i); \
00130 } \
00131 --i
00132
00133
00134
00135
00136
00137
00138
00139
00140
00141
00142
00143
00144 template<class BV>
00145 class serializer
00146 {
00147 public:
00148 typedef typename BV::allocator_type allocator_type;
00149 typedef typename BV::blocks_manager_type blocks_manager_type;
00150 public:
00151 serializer(const allocator_type& alloc = allocator_type());
00152 ~serializer();
00153
00154
00155
00156
00157
00158
00159 void set_compression_level(unsigned clevel);
00160
00161
00162
00163
00164 unsigned get_compression_level() const;
00165
00166
00167
00168
00169
00170
00171
00172
00173
00174
00175
00176
00177
00178
00179
00180 unsigned serialize(const BV& bv,
00181 unsigned char* buf, unsigned buf_size);
00182
00183
00184
00185
00186
00187
00188
00189 void gap_length_serialization(bool value);
00190
00191
00192
00193
00194
00195 void byte_order_serialization(bool value);
00196
00197 protected:
00198
00199
00200
00201 void encode_header(const BV& bv, bm::encoder& enc);
00202
00203
00204
00205
00206 void encode_gap_block(bm::gap_word_t* gap_block, bm::encoder& enc);
00207
00208
00209
00210
00211 void gamma_gap_block(bm::gap_word_t* gap_block, bm::encoder& enc);
00212
00213
00214
00215
00216 void gamma_gap_array(const bm::gap_word_t* gap_block,
00217 unsigned arr_len,
00218 bm::encoder& enc,
00219 bool inverted = false);
00220
00221
00222
00223
00224 void encode_bit_interval(const bm::word_t* blk,
00225 bm::encoder& enc,
00226 unsigned size_control);
00227
00228 private:
00229 serializer(const serializer&);
00230 serializer& operator=(const serializer&);
00231
00232 private:
00233
00234 typedef bm::bit_out<bm::encoder> bit_out_type;
00235 typedef bm::gamma_encoder<bm::gap_word_t, bit_out_type> gamma_encoder_func;
00236
00237 private:
00238 allocator_type alloc_;
00239 bool gap_serial_;
00240 bool byte_order_serial_;
00241 bm::word_t* temp_block_;
00242 unsigned compression_level_;
00243 };
00244
00245
00246
00247
00248
00249 template<class DEC>
00250 class deseriaizer_base
00251 {
00252 public:
00253 typedef DEC decoder_type;
00254 protected:
00255 deseriaizer_base(){}
00256
00257
00258 void read_gap_block(decoder_type& decoder,
00259 unsigned block_type,
00260 bm::gap_word_t* dst_block,
00261 bm::gap_word_t& gap_head);
00262
00263
00264
00265
00266 unsigned read_id_list(decoder_type& decoder,
00267 unsigned block_type,
00268 bm::gap_word_t* dst_arr);
00269
00270 protected:
00271 bm::gap_word_t id_array_[bm::gap_equiv_len * 2];
00272 };
00273
00274
00275
00276
00277
00278 template<class BV, class DEC>
00279 class deserializer : protected deseriaizer_base<DEC>
00280 {
00281 public:
00282 typedef BV bvector_type;
00283 typedef typename deseriaizer_base<DEC>::decoder_type decoder_type;
00284
00285 public:
00286 deserializer() : temp_block_(0) {}
00287
00288 unsigned deserialize(bvector_type& bv,
00289 const unsigned char* buf,
00290 bm::word_t* temp_block);
00291 protected:
00292 typedef typename BV::blocks_manager_type blocks_manager_type;
00293 typedef typename BV::allocator_type allocator_type;
00294
00295 protected:
00296 void deserialize_gap(unsigned char btype, decoder_type& dec,
00297 bvector_type& bv, blocks_manager_type& bman,
00298 unsigned i,
00299 bm::word_t* blk);
00300 protected:
00301 bm::gap_word_t gap_temp_block_[bm::gap_equiv_len * 4];
00302 bm::word_t* temp_block_;
00303 };
00304
00305
00306
00307
00308
00309
00310
00311
00312 template<class BV, class SerialIterator>
00313 class iterator_deserializer
00314 {
00315 public:
00316 typedef BV bvector_type;
00317 typedef SerialIterator serial_iterator_type;
00318 public:
00319 static
00320 unsigned deserialize(bvector_type& bv,
00321 serial_iterator_type& sit,
00322 bm::word_t* temp_block,
00323 set_operation op = bm::set_OR);
00324
00325
00326
00327
00328 static
00329 void deserialize(bvector_type& bv_target,
00330 const bvector_type& bv_mask,
00331 serial_iterator_type& sit,
00332 bm::word_t* temp_block,
00333 set_operation op);
00334
00335 private:
00336 typedef typename BV::blocks_manager_type blocks_manager_type;
00337
00338
00339 static
00340 void load_id_list(bvector_type& bv,
00341 serial_iterator_type& sit,
00342 unsigned id_count,
00343 bool set_clear);
00344
00345
00346 static
00347 unsigned finalize_target_vector(blocks_manager_type& bman,
00348 set_operation op,
00349 unsigned bv_block_idx);
00350
00351
00352 static
00353 unsigned process_id_list(bvector_type& bv,
00354 serial_iterator_type& sit,
00355 set_operation op);
00356
00357
00358 };
00359
00360
00361
00362
00363
00364
00365
00366 template<class DEC>
00367 class serial_stream_iterator : protected deseriaizer_base<DEC>
00368 {
00369 public:
00370 typedef typename deseriaizer_base<DEC>::decoder_type decoder_type;
00371 public:
00372 serial_stream_iterator(const unsigned char* buf);
00373
00374
00375 unsigned bv_size() const { return bv_size_; }
00376
00377
00378 bool is_eof() const { return end_of_stream_; }
00379
00380
00381 void next();
00382
00383
00384 void skip_mono_blocks();
00385
00386
00387 unsigned get_bit_block(bm::word_t* dst_block,
00388 bm::word_t* tmp_block,
00389 set_operation op);
00390
00391
00392
00393 void get_gap_block(bm::gap_word_t* dst_block);
00394
00395
00396 unsigned dec_size() const { return decoder_.size(); }
00397
00398
00399 decoder_type& decoder() { return decoder_; }
00400
00401
00402
00403
00404 enum iterator_state
00405 {
00406 e_unknown = 0,
00407 e_list_ids,
00408 e_blocks,
00409 e_zero_blocks,
00410 e_one_blocks,
00411 e_bit_block,
00412 e_gap_block
00413
00414 };
00415
00416
00417 iterator_state state() const { return this->state_; }
00418
00419 iterator_state get_state() const { return this->state_; }
00420
00421 unsigned get_id_count() const { return this->id_cnt_; }
00422
00423
00424 bm::id_t get_id() const { return this->last_id_; }
00425
00426
00427 unsigned block_idx() const { return this->block_idx_; }
00428
00429 public:
00430
00431
00432 typedef
00433 unsigned (serial_stream_iterator<DEC>::*get_bit_func_type)
00434 (bm::word_t*,bm::word_t*);
00435
00436 unsigned
00437 get_bit_block_ASSIGN(bm::word_t* dst_block, bm::word_t* tmp_block);
00438 unsigned
00439 get_bit_block_OR (bm::word_t* dst_block, bm::word_t* tmp_block);
00440 unsigned
00441 get_bit_block_AND (bm::word_t* dst_block, bm::word_t* tmp_block);
00442 unsigned
00443 get_bit_block_SUB (bm::word_t* dst_block, bm::word_t* tmp_block);
00444 unsigned
00445 get_bit_block_XOR (bm::word_t* dst_block, bm::word_t* tmp_block);
00446 unsigned
00447 get_bit_block_COUNT (bm::word_t* dst_block, bm::word_t* tmp_block);
00448 unsigned
00449 get_bit_block_COUNT_AND(bm::word_t* dst_block, bm::word_t* tmp_block);
00450 unsigned
00451 get_bit_block_COUNT_OR(bm::word_t* dst_block, bm::word_t* tmp_block);
00452 unsigned
00453 get_bit_block_COUNT_XOR(bm::word_t* dst_block, bm::word_t* tmp_block);
00454 unsigned
00455 get_bit_block_COUNT_SUB_AB(bm::word_t* dst_block, bm::word_t* tmp_block);
00456 unsigned
00457 get_bit_block_COUNT_SUB_BA(bm::word_t* dst_block, bm::word_t* tmp_block);
00458 unsigned
00459 get_bit_block_COUNT_A(bm::word_t* dst_block, bm::word_t* tmp_block);
00460 unsigned
00461 get_bit_block_COUNT_B(bm::word_t* dst_block, bm::word_t* tmp_block)
00462 {
00463 return get_bit_block_COUNT(dst_block, tmp_block);
00464 }
00465
00466
00467
00468
00469 unsigned get_arr_bit(bm::word_t* dst_block,
00470 bool clear_target=true);
00471
00472
00473 unsigned get_block_type() const { return block_type_; }
00474
00475 unsigned get_bit();
00476
00477 protected:
00478 get_bit_func_type bit_func_table_[bm::set_END];
00479
00480 decoder_type decoder_;
00481 bool end_of_stream_;
00482 unsigned bv_size_;
00483 iterator_state state_;
00484 unsigned id_cnt_;
00485 bm::id_t last_id_;
00486 gap_word_t glevels_[bm::gap_levels];
00487
00488 unsigned block_type_;
00489 unsigned block_idx_;
00490 unsigned mono_block_cnt_;
00491
00492 gap_word_t gap_head_;
00493 };
00494
00495
00496
00497
00498
00499
00500
00501 template<class BV>
00502 class operation_deserializer
00503 {
00504 public:
00505 typedef BV bvector_type;
00506 public:
00507 static
00508 unsigned deserialize(bvector_type& bv,
00509 const unsigned char* buf,
00510 bm::word_t* temp_block,
00511 set_operation op = bm::set_OR);
00512 private:
00513
00514 static
00515 void deserialize(bvector_type& bv_target,
00516 const bvector_type& bv_mask,
00517 const unsigned char* buf,
00518 bm::word_t* temp_block,
00519 set_operation op);
00520
00521 private:
00522 typedef
00523 typename BV::blocks_manager_type blocks_manager_type;
00524 typedef
00525 serial_stream_iterator<bm::decoder> serial_stream_current;
00526 typedef
00527 serial_stream_iterator<bm::decoder_big_endian> serial_stream_be;
00528 typedef
00529 serial_stream_iterator<bm::decoder_little_endian> serial_stream_le;
00530
00531 };
00532
00533
00534
00535
00536
00537
00538
00539 template<class BV>
00540 serializer<BV>::serializer(const allocator_type& alloc)
00541 : alloc_(alloc),
00542 gap_serial_(false),
00543 byte_order_serial_(true),
00544 temp_block_(0),
00545 compression_level_(3)
00546 {
00547 temp_block_ = alloc_.alloc_bit_block();
00548 }
00549
00550 template<class BV>
00551 void serializer<BV>::set_compression_level(unsigned clevel)
00552 {
00553 compression_level_ = clevel;
00554 }
00555
00556 template<class BV>
00557 unsigned serializer<BV>::get_compression_level() const
00558 {
00559 return compression_level_;
00560 }
00561
00562 template<class BV>
00563 serializer<BV>::~serializer()
00564 {
00565 alloc_.free_bit_block(temp_block_);
00566 }
00567
00568
00569 template<class BV>
00570 void serializer<BV>::gap_length_serialization(bool value)
00571 {
00572 gap_serial_ = value;
00573 }
00574
00575 template<class BV>
00576 void serializer<BV>::byte_order_serialization(bool value)
00577 {
00578 byte_order_serial_ = value;
00579 }
00580
00581 template<class BV>
00582 void serializer<BV>::encode_header(const BV& bv, bm::encoder& enc)
00583 {
00584 const blocks_manager_type& bman = bv.get_blocks_manager();
00585
00586 unsigned char header_flag = 0;
00587 if (bv.size() == bm::id_max)
00588 header_flag |= BM_HM_DEFAULT;
00589 else
00590 header_flag |= BM_HM_RESIZE;
00591
00592 if (!byte_order_serial_)
00593 header_flag |= BM_HM_NO_BO;
00594
00595 if (!gap_serial_)
00596 header_flag |= BM_HM_NO_GAPL;
00597
00598 enc.put_8(header_flag);
00599
00600 if (byte_order_serial_)
00601 {
00602 ByteOrder bo = globals<true>::byte_order();
00603 enc.put_8((unsigned char)bo);
00604 }
00605
00606
00607 if (gap_serial_)
00608 {
00609 enc.put_16(bman.glen(), bm::gap_levels);
00610 }
00611
00612
00613 if (header_flag & BM_HM_RESIZE)
00614 {
00615 enc.put_32(bv.size());
00616 }
00617
00618 }
00619
00620 template<class BV>
00621 void serializer<BV>::gamma_gap_block(bm::gap_word_t* gap_block, bm::encoder& enc)
00622 {
00623 unsigned len = gap_length(gap_block);
00624
00625
00626 if (len > 6 && (compression_level_ > 3))
00627 {
00628 encoder::position_type enc_pos0 = enc.get_pos();
00629 {
00630 bit_out_type bout(enc);
00631 gamma_encoder_func gamma(bout);
00632
00633 enc.put_8(set_block_gap_egamma);
00634 enc.put_16(gap_block[0]);
00635
00636 for_each_dgap(gap_block, gamma);
00637 }
00638
00639
00640 encoder::position_type enc_pos1 = enc.get_pos();
00641 unsigned gamma_size = enc_pos1 - enc_pos0;
00642 if (gamma_size > (len-1)*sizeof(gap_word_t))
00643 {
00644 enc.set_pos(enc_pos0);
00645 }
00646 else
00647 {
00648 return;
00649 }
00650 }
00651
00652
00653 enc.put_8(set_block_gap);
00654 enc.put_16(gap_block, len-1);
00655 }
00656
00657 template<class BV>
00658 void serializer<BV>::gamma_gap_array(const bm::gap_word_t* gap_array,
00659 unsigned arr_len,
00660 bm::encoder& enc,
00661 bool inverted)
00662 {
00663 if (compression_level_ > 3 && arr_len > 25)
00664 {
00665 encoder::position_type enc_pos0 = enc.get_pos();
00666 {
00667 bit_out_type bout(enc);
00668
00669 enc.put_8(
00670 inverted ? set_block_arrgap_egamma_inv
00671 : set_block_arrgap_egamma);
00672
00673 bout.gamma(arr_len);
00674
00675 gap_word_t prev = gap_array[0];
00676 bout.gamma(prev + 1);
00677
00678 for (unsigned i = 1; i < arr_len; ++i)
00679 {
00680 gap_word_t curr = gap_array[i];
00681 bout.gamma(curr - prev);
00682 prev = curr;
00683 }
00684 }
00685
00686 encoder::position_type enc_pos1 = enc.get_pos();
00687 unsigned gamma_size = enc_pos1 - enc_pos0;
00688 if (gamma_size > (arr_len)*sizeof(gap_word_t))
00689 {
00690 enc.set_pos(enc_pos0);
00691 }
00692 else
00693 {
00694 return;
00695 }
00696 }
00697
00698
00699 enc.put_prefixed_array_16(inverted ? set_block_arrgap_inv : set_block_arrgap,
00700 gap_array, arr_len, true);
00701 }
00702
00703
00704 template<class BV>
00705 void serializer<BV>::encode_gap_block(bm::gap_word_t* gap_block, bm::encoder& enc)
00706 {
00707 if (compression_level_ > 2)
00708 {
00709 gap_word_t* gap_temp_block = (gap_word_t*) temp_block_;
00710 gap_word_t arr_len;
00711
00712 unsigned bc = gap_bit_count(gap_block);
00713 if (bc == 1)
00714 {
00715 arr_len = gap_convert_to_arr(gap_temp_block,
00716 gap_block,
00717 bm::gap_equiv_len-10);
00718 BM_ASSERT(arr_len == 1);
00719 enc.put_8(set_block_bit_1bit);
00720 enc.put_16(gap_temp_block[0]);
00721 return;
00722 }
00723
00724 unsigned len = gap_length(gap_block);
00725 bool invert, use_array;
00726 invert = use_array = false;
00727
00728 if (bc < len-1)
00729 {
00730 use_array = true;
00731 }
00732 else
00733 {
00734 unsigned inverted_bc = bm::gap_max_bits - bc;
00735 if (inverted_bc < len-1)
00736 {
00737 use_array = invert = true;
00738 }
00739 }
00740 if (use_array)
00741 {
00742 arr_len = gap_convert_to_arr(gap_temp_block,
00743 gap_block,
00744 bm::gap_equiv_len-10,
00745 invert);
00746 if (arr_len)
00747 {
00748 gamma_gap_array(gap_temp_block, arr_len, enc, invert);
00749 return;
00750 }
00751 }
00752 }
00753
00754 gamma_gap_block(gap_block, enc);
00755 }
00756
00757 template<class BV>
00758 void serializer<BV>::encode_bit_interval(const bm::word_t* blk,
00759 bm::encoder& enc,
00760 unsigned
00761 )
00762 {
00763 enc.put_8(set_block_bit_0runs);
00764 enc.put_8((blk[0]==0) ? 0 : 1);
00765
00766 unsigned i,j;
00767
00768 for (i = 0; i < bm::set_block_size; ++i)
00769 {
00770 if (blk[i] == 0)
00771 {
00772
00773 for (j = i+1; j < bm::set_block_size; ++j)
00774 {
00775 if (blk[j] != 0)
00776 break;
00777 }
00778 enc.put_16(j-i);
00779 i = j - 1;
00780 }
00781 else
00782 {
00783
00784 for (j = i+1; j < bm::set_block_size; ++j)
00785 {
00786 if (blk[j] == 0)
00787 {
00788
00789 if (((j+1 < bm::set_block_size) && blk[j+1]) ||
00790 ((j+2 < bm::set_block_size) && blk[j+2])
00791 )
00792 {
00793 ++j;
00794 continue;
00795 }
00796 break;
00797 }
00798 }
00799 enc.put_16(j-i);
00800
00801 BM_ASSERT(i < j);
00802 enc.put_32(blk + i, j - i);
00803 i = j - 1;
00804 }
00805 }
00806 }
00807
00808
00809 template<class BV>
00810 unsigned serializer<BV>::serialize(const BV& bv,
00811 unsigned char* buf, unsigned buf_size)
00812 {
00813 BM_ASSERT(temp_block_);
00814
00815 const blocks_manager_type& bman = bv.get_blocks_manager();
00816
00817 gap_word_t* gap_temp_block = (gap_word_t*) temp_block_;
00818
00819 bm::encoder enc(buf, buf_size);
00820 encode_header(bv, enc);
00821
00822 unsigned i,j;
00823
00824
00825
00826 for (i = 0; i < bm::set_total_blocks; ++i)
00827 {
00828 bm::word_t* blk = bman.get_block(i);
00829
00830
00831
00832 bool flag;
00833 flag = bman.is_block_zero(i, blk, false);
00834 if (flag)
00835 {
00836 zero_block:
00837 unsigned next_nb = bman.find_next_nz_block(i+1, false);
00838 if (next_nb == bm::set_total_blocks)
00839 {
00840 enc.put_8(set_block_azero);
00841 return enc.size();
00842 }
00843 unsigned nb = next_nb - i;
00844
00845 if (nb > 1 && nb < 128)
00846 {
00847
00848 unsigned char c = (1 << 7) | nb;
00849 enc.put_8(c);
00850 }
00851 else
00852 {
00853 SER_NEXT_GRP(enc, nb, set_block_1zero,
00854 set_block_8zero,
00855 set_block_16zero,
00856 set_block_32zero)
00857 }
00858 i = next_nb - 1;
00859 continue;
00860 }
00861 else
00862 {
00863 flag = bman.is_block_one(i, blk, false);
00864 if (flag)
00865 {
00866
00867 for(j = i+1; j < bm::set_total_blocks; ++j)
00868 {
00869 bm::word_t* blk_next = bman.get_block(j);
00870 if (flag != bman.is_block_one(j, blk_next, false))
00871 break;
00872 }
00873 if (j == bm::set_total_blocks)
00874 {
00875 enc.put_8(set_block_aone);
00876 break;
00877 }
00878 else
00879 {
00880 unsigned nb = j - i;
00881 SER_NEXT_GRP(enc, nb, set_block_1one,
00882 set_block_8one,
00883 set_block_16one,
00884 set_block_32one)
00885 }
00886 i = j - 1;
00887 continue;
00888 }
00889 }
00890
00891
00892
00893
00894 if (BM_IS_GAP(bman, blk, i))
00895 {
00896 gap_word_t* gblk = BMGAP_PTR(blk);
00897 encode_gap_block(gblk, enc);
00898 continue;
00899 }
00900
00901
00902
00903
00904 {
00905 if (compression_level_ <= 1)
00906 {
00907 enc.put_prefixed_array_32(set_block_bit, blk, bm::set_block_size);
00908 continue;
00909 }
00910
00911
00912 unsigned block_bc = 0;
00913 bm::id_t bit_gaps =
00914 bit_block_calc_count_change(blk, blk + bm::set_block_size,
00915 &block_bc);
00916 unsigned block_bc_inv = bm::gap_max_bits - block_bc;
00917 switch (block_bc)
00918 {
00919 case 1:
00920 {
00921 bm::id_t bit_idx = 0;
00922 bit_find_in_block(blk, bit_idx, &bit_idx);
00923 enc.put_8(set_block_bit_1bit); enc.put_16((short)bit_idx);
00924 continue;
00925 }
00926 case 0: goto zero_block;
00927 }
00928
00929
00930
00931
00932 unsigned arr_block_size = sizeof(gap_word_t) + (block_bc * sizeof(gap_word_t));
00933 unsigned arr_block_size_inv = sizeof(gap_word_t) + (block_bc_inv * sizeof(gap_word_t));
00934 unsigned gap_block_size = sizeof(gap_word_t) + ((bit_gaps+1) * sizeof(gap_word_t));
00935 unsigned interval_block_size;
00936 interval_block_size = bit_count_nonzero_size(blk, bm::set_block_size);
00937 bool inverted = false;
00938
00939 if (arr_block_size_inv < arr_block_size &&
00940 arr_block_size_inv < gap_block_size &&
00941 arr_block_size_inv < interval_block_size)
00942 {
00943 inverted = true;
00944 goto bit_as_array;
00945 }
00946
00947
00948 if ((interval_block_size > arr_block_size) ||
00949 (interval_block_size > gap_block_size))
00950 {
00951 if (gap_block_size < (bm::gap_equiv_len-64) &&
00952 gap_block_size < arr_block_size)
00953 {
00954 unsigned len = bit_convert_to_gap(gap_temp_block,
00955 blk,
00956 bm::gap_max_bits,
00957 bm::gap_equiv_len-64);
00958 if (len)
00959 {
00960 gamma_gap_block(gap_temp_block, enc);
00961 continue;
00962 }
00963 }
00964
00965 if (arr_block_size < ((bm::gap_equiv_len-64) * sizeof(gap_word_t)))
00966 {
00967 bit_as_array:
00968 gap_word_t arr_len;
00969 unsigned mask = inverted ? ~0 : 0;
00970 arr_len = bit_convert_to_arr(gap_temp_block,
00971 blk,
00972 bm::gap_max_bits,
00973 bm::gap_equiv_len-64,
00974 mask);
00975 if (arr_len)
00976 {
00977 gamma_gap_array(gap_temp_block, arr_len, enc, inverted);
00978 continue;
00979 }
00980
00981 }
00982
00983 enc.put_prefixed_array_32(set_block_bit, blk, bm::set_block_size);
00984 continue;
00985 }
00986
00987
00988 if (interval_block_size < arr_block_size &&
00989 interval_block_size < gap_block_size)
00990 {
00991 encode_bit_interval(blk, enc, interval_block_size);
00992 continue;
00993 }
00994
00995 if (gap_block_size < bm::gap_equiv_len &&
00996 gap_block_size < arr_block_size)
00997 {
00998 unsigned len = bit_convert_to_gap(gap_temp_block,
00999 blk,
01000 bm::gap_max_bits,
01001 bm::gap_equiv_len-64);
01002 if (len)
01003 {
01004 gamma_gap_block(gap_temp_block, enc);
01005 continue;
01006 }
01007 }
01008
01009
01010
01011 if (arr_block_size < bm::gap_equiv_len-64)
01012 {
01013 goto bit_as_array;
01014 }
01015
01016
01017 enc.put_prefixed_array_32(set_block_bit, blk, bm::set_block_size);
01018 continue;
01019 }
01020 }
01021
01022 enc.put_8(set_block_end);
01023
01024 unsigned encoded_size = enc.size();
01025 return encoded_size;
01026
01027 }
01028
01029
01030
01031
01032
01033 enum serialization_flags {
01034 BM_NO_BYTE_ORDER = 1,
01035 BM_NO_GAP_LENGTH = (1 << 1)
01036 };
01037
01038
01039
01040
01041
01042
01043
01044
01045
01046
01047
01048
01049
01050
01051
01052
01053
01054
01055
01056
01057
01058
01059
01060
01061
01062
01063
01064
01065
01066
01067
01068
01069
01070
01071
01072
01073
01074
01075
01076
01077
01078
01079 template<class BV>
01080 unsigned serialize(const BV& bv,
01081 unsigned char* buf,
01082 bm::word_t* temp_block,
01083 unsigned serialization_flags = 0)
01084 {
01085 bm::serializer<BV> bv_serial;
01086 if (serialization_flags & BM_NO_BYTE_ORDER)
01087 bv_serial.byte_order_serialization(false);
01088
01089 if (serialization_flags & BM_NO_GAP_LENGTH)
01090 bv_serial.gap_length_serialization(false);
01091 else
01092 bv_serial.gap_length_serialization(true);
01093
01094 bv_serial.set_compression_level(4);
01095
01096 return bv_serial.serialize(bv, buf, 0);
01097 }
01098
01099
01100
01101
01102
01103
01104
01105 template<class BV>
01106 unsigned serialize(BV& bv,
01107 unsigned char* buf,
01108 unsigned serialization_flags=0)
01109 {
01110 bm::serializer<BV> bv_serial;
01111 if (serialization_flags & BM_NO_BYTE_ORDER)
01112 bv_serial.byte_order_serialization(false);
01113
01114 if (serialization_flags & BM_NO_GAP_LENGTH)
01115 bv_serial.gap_length_serialization(false);
01116 else
01117 bv_serial.gap_length_serialization(true);
01118
01119 bv_serial.set_compression_level(4);
01120
01121 return bv_serial.serialize(bv, buf, 0);
01122 }
01123
01124
01125
01126
01127
01128
01129
01130
01131
01132
01133
01134
01135
01136
01137
01138
01139
01140
01141 template<class BV>
01142 unsigned deserialize(BV& bv,
01143 const unsigned char* buf,
01144 bm::word_t* temp_block=0)
01145 {
01146 ByteOrder bo_current = globals<true>::byte_order();
01147
01148 bm::decoder dec(buf);
01149 unsigned char header_flag = dec.get_8();
01150 ByteOrder bo = bo_current;
01151 if (!(header_flag & BM_HM_NO_BO))
01152 {
01153 bo = (bm::ByteOrder) dec.get_8();
01154 }
01155
01156 if (bo_current == bo)
01157 {
01158 deserializer<BV, bm::decoder> deserial;
01159 return deserial.deserialize(bv, buf, temp_block);
01160 }
01161 switch (bo_current)
01162 {
01163 case BigEndian:
01164 {
01165 deserializer<BV, bm::decoder_big_endian> deserial;
01166 return deserial.deserialize(bv, buf, temp_block);
01167 }
01168 case LittleEndian:
01169 {
01170 deserializer<BV, bm::decoder_little_endian> deserial;
01171 return deserial.deserialize(bv, buf, temp_block);
01172 }
01173 default:
01174 BM_ASSERT(0);
01175 };
01176 return 0;
01177 }
01178
01179 template<class DEC>
01180 unsigned deseriaizer_base<DEC>::read_id_list(decoder_type& decoder,
01181 unsigned block_type,
01182 bm::gap_word_t* dst_arr)
01183 {
01184 typedef bit_in<DEC> bit_in_type;
01185
01186 gap_word_t len = 0;
01187
01188 switch (block_type)
01189 {
01190 case set_block_bit_1bit:
01191 dst_arr[0] = decoder.get_16();
01192 len = 1;
01193 break;
01194 case set_block_arrgap:
01195 case set_block_arrgap_inv:
01196 len = decoder.get_16();
01197 decoder.get_16(dst_arr, len);
01198 break;
01199 case set_block_arrgap_egamma:
01200 case set_block_arrgap_egamma_inv:
01201 {
01202 bit_in_type bin(decoder);
01203 len = bin.gamma();
01204 gap_word_t prev = 0;
01205 for (gap_word_t k = 0; k < len; ++k)
01206 {
01207 gap_word_t bit_idx = bin.gamma();
01208 if (k == 0) --bit_idx;
01209 bit_idx += prev;
01210 prev = bit_idx;
01211 dst_arr[k] = bit_idx;
01212 }
01213 }
01214 break;
01215 default:
01216 BM_ASSERT(0);
01217 }
01218 return len;
01219 }
01220
01221
01222 template<class DEC>
01223 void deseriaizer_base<DEC>::read_gap_block(decoder_type& decoder,
01224 unsigned block_type,
01225 bm::gap_word_t* dst_block,
01226 bm::gap_word_t& gap_head)
01227 {
01228 typedef bit_in<DEC> bit_in_type;
01229
01230 switch (block_type)
01231 {
01232 case set_block_gap:
01233 {
01234 unsigned len = gap_length(&gap_head);
01235 --len;
01236 *dst_block = gap_head;
01237 decoder.get_16(dst_block+1, len - 1);
01238 dst_block[len] = gap_max_bits - 1;
01239 }
01240 break;
01241 case set_block_bit_1bit:
01242 {
01243 gap_set_all(dst_block, bm::gap_max_bits, 0);
01244 gap_word_t bit_idx = decoder.get_16();
01245 gap_add_value(dst_block, bit_idx);
01246 }
01247 break;
01248 case set_block_arrgap:
01249 case set_block_arrgap_inv:
01250 {
01251 gap_set_all(dst_block, bm::gap_max_bits, 0);
01252 gap_word_t len = decoder.get_16();
01253
01254 for (gap_word_t k = 0; k < len; ++k)
01255 {
01256 gap_word_t bit_idx = decoder.get_16();
01257 gap_add_value(dst_block, bit_idx);
01258 }
01259 }
01260 break;
01261 case set_block_arrgap_egamma:
01262 case set_block_arrgap_egamma_inv:
01263 {
01264 unsigned arr_len = read_id_list(decoder, block_type, id_array_);
01265 dst_block[0] = 0;
01266
01267 gap_set_array(dst_block, id_array_, arr_len);
01268 }
01269 break;
01270 case set_block_gap_egamma:
01271 {
01272 unsigned len = (gap_head >> 3);
01273 --len;
01274
01275 {
01276 *dst_block = gap_head;
01277 gap_word_t* gap_data_ptr = dst_block + 1;
01278
01279 bit_in_type bin(decoder);
01280 {
01281 gap_word_t v = bin.gamma();
01282 gap_word_t gap_sum = *gap_data_ptr = v - 1;
01283 for (unsigned i = 1; i < len; ++i)
01284 {
01285 v = bin.gamma();
01286 *(++gap_data_ptr) = gap_sum += v;
01287 }
01288 dst_block[len+1] = bm::gap_max_bits - 1;
01289 }
01290 }
01291
01292 }
01293 break;
01294 default:
01295 BM_ASSERT(0);
01296 }
01297
01298 if (block_type == set_block_arrgap_egamma_inv ||
01299 block_type == set_block_arrgap_inv)
01300 {
01301 gap_invert(dst_block);
01302 }
01303 }
01304
01305
01306 template<class BV, class DEC>
01307 void
01308 deserializer<BV, DEC>::deserialize_gap(unsigned char btype, decoder_type& dec,
01309 bvector_type& bv, blocks_manager_type& bman,
01310 unsigned i,
01311 bm::word_t* blk)
01312 {
01313 typedef bit_in<DEC> bit_in_type;
01314 gap_word_t gap_head;
01315
01316 switch (btype)
01317 {
01318 case set_block_gap:
01319 case set_block_gapbit:
01320 {
01321 gap_word_t gap_head =
01322 sizeof(gap_word_t) == 2 ? dec.get_16() : dec.get_32();
01323
01324 unsigned len = gap_length(&gap_head);
01325 int level = gap_calc_level(len, bman.glen());
01326 --len;
01327 if (level == -1)
01328 {
01329 *gap_temp_block_ = gap_head;
01330 dec.get_16(gap_temp_block_+1, len - 1);
01331 gap_temp_block_[len] = gap_max_bits - 1;
01332
01333 if (blk == 0)
01334 {
01335 blk = bman.get_allocator().alloc_bit_block();
01336 bman.set_block(i, blk);
01337 gap_convert_to_bitset(blk, gap_temp_block_);
01338 }
01339 else
01340 {
01341 gap_convert_to_bitset(temp_block_,
01342 gap_temp_block_);
01343 bv.combine_operation_with_block(i,
01344 temp_block_,
01345 0,
01346 BM_OR);
01347 }
01348 return;
01349 }
01350
01351 set_gap_level(&gap_head, level);
01352
01353 if (blk == 0)
01354 {
01355 gap_word_t* gap_blk =
01356 bman.get_allocator().alloc_gap_block(level, bman.glen());
01357 gap_word_t* gap_blk_ptr = BMGAP_PTR(gap_blk);
01358 *gap_blk_ptr = gap_head;
01359 set_gap_level(gap_blk_ptr, level);
01360 bman.set_block(i, (bm::word_t*)gap_blk);
01361 bman.set_block_gap(i);
01362 dec.get_16(gap_blk + 1, len - 1);
01363 gap_blk[len] = bm::gap_max_bits - 1;
01364 }
01365 else
01366 {
01367
01368 *gap_temp_block_ = gap_head;
01369 dec.get_16(gap_temp_block_ + 1, len - 1);
01370 gap_temp_block_[len] = bm::gap_max_bits - 1;
01371 break;
01372 }
01373 return;
01374 }
01375 case set_block_arrgap:
01376 case set_block_arrgap_egamma:
01377 {
01378 unsigned arr_len = read_id_list(dec, btype, this->id_array_);
01379
01380 gap_set_array(gap_temp_block_, this->id_array_, arr_len);
01381 break;
01382 }
01383 case set_block_gap_egamma:
01384 gap_head =
01385 sizeof(gap_word_t) == 2 ? dec.get_16() : dec.get_32();
01386 case set_block_arrgap_egamma_inv:
01387 case set_block_arrgap_inv:
01388 read_gap_block(dec, btype, gap_temp_block_, gap_head);
01389 break;
01390 default:
01391 BM_ASSERT(0);
01392 }
01393
01394 bv.combine_operation_with_block(i,
01395 (bm::word_t*)gap_temp_block_,
01396 1,
01397 BM_OR);
01398
01399 }
01400
01401
01402 template<class BV, class DEC>
01403 unsigned deserializer<BV, DEC>::deserialize(bvector_type& bv,
01404 const unsigned char* buf,
01405 bm::word_t* temp_block)
01406 {
01407 blocks_manager_type& bman = bv.get_blocks_manager();
01408
01409 bm::wordop_t* tmp_buf =
01410 temp_block ? (bm::wordop_t*) temp_block
01411 : (bm::wordop_t*)bman.check_allocate_tempblock();
01412
01413 temp_block_ = temp_block = (word_t*)tmp_buf;
01414 bm::strategy strat = bv.get_new_blocks_strat();
01415 bv.set_new_blocks_strat(BM_GAP);
01416
01417 decoder_type dec(buf);
01418
01419 BM_SET_MMX_GUARD
01420
01421
01422
01423 unsigned char header_flag = dec.get_8();
01424 if (!(header_flag & BM_HM_NO_BO))
01425 {
01426 dec.get_8();
01427 }
01428
01429 if (header_flag & BM_HM_ID_LIST)
01430 {
01431
01432 if (header_flag & BM_HM_RESIZE)
01433 {
01434 unsigned bv_size = dec.get_32();
01435 if (bv_size > bv.size())
01436 {
01437 bv.resize(bv_size);
01438 }
01439 }
01440
01441
01442 for (unsigned cnt = dec.get_32(); cnt; --cnt) {
01443 bm::id_t id = dec.get_32();
01444 bv.set(id);
01445 }
01446
01447 return dec.size()-1;
01448 }
01449
01450 unsigned i;
01451
01452 if (!(header_flag & BM_HM_NO_GAPL))
01453 {
01454 gap_word_t glevels[bm::gap_levels];
01455
01456 for (i = 0; i < bm::gap_levels; ++i)
01457 {
01458 glevels[i] = dec.get_16();
01459 }
01460 }
01461
01462 if (header_flag & (1 << 1))
01463 {
01464 unsigned bv_size = dec.get_32();
01465 if (bv_size > bv.size())
01466 {
01467 bv.resize(bv_size);
01468 }
01469 }
01470
01471 unsigned char btype;
01472 unsigned nb;
01473
01474 for (i = 0; i < bm::set_total_blocks; ++i)
01475 {
01476 btype = dec.get_8();
01477 bm::word_t* blk = bman.get_block(i);
01478
01479
01480 if (btype & (1 << 7))
01481 {
01482 nb = btype & ~(1 << 7);
01483 i += nb-1;
01484 continue;
01485 }
01486
01487 switch (btype)
01488 {
01489 case set_block_azero:
01490 case set_block_end:
01491 i = bm::set_total_blocks;
01492 break;
01493 case set_block_1zero:
01494 continue;
01495 case set_block_8zero:
01496 nb = dec.get_8();
01497 i += nb-1;
01498 continue;
01499 case set_block_16zero:
01500 nb = dec.get_16();
01501 i += nb-1;
01502 continue;
01503 case set_block_32zero:
01504 nb = dec.get_32();
01505 i += nb-1;
01506 continue;
01507 case set_block_aone:
01508 for (;i < bm::set_total_blocks; ++i)
01509 {
01510 bman.set_block_all_set(i);
01511 }
01512 break;
01513 case set_block_1one:
01514 bman.set_block_all_set(i);
01515 continue;
01516 case set_block_8one:
01517 BM_SET_ONE_BLOCKS(dec.get_8());
01518 continue;
01519 case set_block_16one:
01520 BM_SET_ONE_BLOCKS(dec.get_16());
01521 continue;
01522 case set_block_32one:
01523 BM_SET_ONE_BLOCKS(dec.get_32());
01524 continue;
01525 case set_block_bit:
01526 {
01527 if (blk == 0)
01528 {
01529 blk = bman.get_allocator().alloc_bit_block();
01530 bman.set_block(i, blk);
01531 dec.get_32(blk, bm::set_block_size);
01532 continue;
01533 }
01534
01535 dec.get_32(temp_block, bm::set_block_size);
01536 bv.combine_operation_with_block(i,
01537 temp_block,
01538 0, BM_OR);
01539
01540 continue;
01541 }
01542 case set_block_bit_1bit:
01543 {
01544 unsigned bit_idx = dec.get_16();
01545 bit_idx += i * bm::bits_in_block;
01546 bv.set_bit(bit_idx);
01547 continue;
01548 }
01549 case set_block_bit_0runs:
01550 {
01551
01552 bit_block_set(temp_block, 0);
01553
01554 unsigned char run_type = dec.get_8();
01555 for (unsigned j = 0; j < bm::set_block_size;run_type = !run_type)
01556 {
01557 unsigned run_length = dec.get_16();
01558 if (run_type)
01559 {
01560 unsigned run_end = j + run_length;
01561 for (;j < run_end; ++j)
01562 {
01563 BM_ASSERT(j < bm::set_block_size);
01564 temp_block[j] = dec.get_32();
01565 }
01566 }
01567 else
01568 {
01569 j += run_length;
01570 }
01571 }
01572
01573 bv.combine_operation_with_block(i,
01574 temp_block,
01575 0, BM_OR);
01576 continue;
01577 }
01578 case set_block_bit_interval:
01579 {
01580 unsigned head_idx, tail_idx;
01581 head_idx = dec.get_16();
01582 tail_idx = dec.get_16();
01583
01584 if (blk == 0)
01585 {
01586 blk = bman.get_allocator().alloc_bit_block();
01587 bman.set_block(i, blk);
01588 for (unsigned i = 0; i < head_idx; ++i)
01589 {
01590 blk[i] = 0;
01591 }
01592 dec.get_32(blk + head_idx, tail_idx - head_idx + 1);
01593 for (unsigned j = tail_idx + 1; j < bm::set_block_size; ++j)
01594 {
01595 blk[j] = 0;
01596 }
01597 continue;
01598 }
01599 bit_block_set(temp_block, 0);
01600 dec.get_32(temp_block + head_idx, tail_idx - head_idx + 1);
01601
01602 bv.combine_operation_with_block(i,
01603 temp_block,
01604 0, BM_OR);
01605 continue;
01606 }
01607 case set_block_gap:
01608 case set_block_gapbit:
01609 case set_block_arrgap:
01610 case set_block_gap_egamma:
01611 case set_block_arrgap_egamma:
01612 case set_block_arrgap_egamma_inv:
01613 case set_block_arrgap_inv:
01614 deserialize_gap(btype, dec, bv, bman, i, blk);
01615 continue;
01616 case set_block_arrbit:
01617 {
01618 gap_word_t len =
01619 sizeof(gap_word_t) == 2 ? dec.get_16() : dec.get_32();
01620
01621 if (bman.is_block_gap(i))
01622 {
01623
01624
01625
01626 blk = bman.convert_gap2bitset(i);
01627 }
01628 else
01629 {
01630 if (blk == 0)
01631 {
01632 blk = bman.get_allocator().alloc_bit_block();
01633 bit_block_set(blk, 0);
01634 bman.set_block(i, blk);
01635 }
01636 }
01637
01638
01639 for (unsigned k = 0; k < len; ++k)
01640 {
01641 gap_word_t bit_idx = dec.get_16();
01642 set_bit(blk, bit_idx);
01643 }
01644 continue;
01645 }
01646 default:
01647 BM_ASSERT(0);
01648 }
01649 }
01650
01651 bv.forget_count();
01652 bv.set_new_blocks_strat(strat);
01653
01654 return dec.size();
01655 }
01656
01657
01658
01659 template<class DEC>
01660 serial_stream_iterator<DEC>::serial_stream_iterator(const unsigned char* buf)
01661 : decoder_(buf),
01662 end_of_stream_(false),
01663 bv_size_(0),
01664 state_(e_unknown),
01665 id_cnt_(0),
01666 block_idx_(0),
01667 mono_block_cnt_(0)
01668 {
01669 ::memset(bit_func_table_, 0, sizeof(bit_func_table_));
01670
01671 bit_func_table_[bm::set_AND] =
01672 &serial_stream_iterator<DEC>::get_bit_block_AND;
01673 bit_func_table_[bm::set_ASSIGN] =
01674 &serial_stream_iterator<DEC>::get_bit_block_ASSIGN;
01675 bit_func_table_[bm::set_OR] =
01676 &serial_stream_iterator<DEC>::get_bit_block_OR;
01677 bit_func_table_[bm::set_SUB] =
01678 &serial_stream_iterator<DEC>::get_bit_block_SUB;
01679 bit_func_table_[bm::set_XOR] =
01680 &serial_stream_iterator<DEC>::get_bit_block_XOR;
01681 bit_func_table_[bm::set_COUNT] =
01682 &serial_stream_iterator<DEC>::get_bit_block_COUNT;
01683 bit_func_table_[bm::set_COUNT_AND] =
01684 &serial_stream_iterator<DEC>::get_bit_block_COUNT_AND;
01685 bit_func_table_[bm::set_COUNT_XOR] =
01686 &serial_stream_iterator<DEC>::get_bit_block_COUNT_XOR;
01687 bit_func_table_[bm::set_COUNT_OR] =
01688 &serial_stream_iterator<DEC>::get_bit_block_COUNT_OR;
01689 bit_func_table_[bm::set_COUNT_SUB_AB] =
01690 &serial_stream_iterator<DEC>::get_bit_block_COUNT_SUB_AB;
01691 bit_func_table_[bm::set_COUNT_SUB_BA] =
01692 &serial_stream_iterator<DEC>::get_bit_block_COUNT_SUB_BA;
01693 bit_func_table_[bm::set_COUNT_A] =
01694 &serial_stream_iterator<DEC>::get_bit_block_COUNT_A;
01695 bit_func_table_[bm::set_COUNT_B] =
01696 &serial_stream_iterator<DEC>::get_bit_block_COUNT;
01697
01698
01699
01700 unsigned char header_flag = decoder_.get_8();
01701 if (!(header_flag & BM_HM_NO_BO))
01702 {
01703 decoder_.get_8();
01704 }
01705
01706
01707
01708 if (header_flag & BM_HM_ID_LIST)
01709 {
01710
01711 if (header_flag & BM_HM_RESIZE)
01712 {
01713 bv_size_ = decoder_.get_32();
01714 }
01715
01716 state_ = e_list_ids;
01717 id_cnt_ = decoder_.get_32();
01718 next();
01719 }
01720 else
01721 {
01722 if (!(header_flag & BM_HM_NO_GAPL))
01723 {
01724 unsigned i;
01725
01726 for (i = 0; i < bm::gap_levels; ++i)
01727 {
01728 glevels_[i] = decoder_.get_16();
01729 }
01730 }
01731
01732 if (header_flag & (1 << 1))
01733 {
01734 bv_size_ = decoder_.get_32();
01735 }
01736 state_ = e_blocks;
01737 }
01738 }
01739
01740 template<class DEC>
01741 void serial_stream_iterator<DEC>::next()
01742 {
01743 if (is_eof())
01744 {
01745 ++block_idx_;
01746 return;
01747 }
01748
01749 switch (state_)
01750 {
01751 case e_list_ids:
01752
01753 if (id_cnt_ == 0)
01754 {
01755 end_of_stream_ = true;
01756 state_ = e_unknown;
01757 break;
01758 }
01759 last_id_ = decoder_.get_32();
01760 --id_cnt_;
01761 break;
01762
01763 case e_blocks:
01764 if (block_idx_ == bm::set_total_blocks)
01765 {
01766 end_of_stream_ = true;
01767 state_ = e_unknown;
01768 break;
01769 }
01770
01771 block_type_ = decoder_.get_8();
01772
01773
01774
01775 if (block_type_ & (1 << 7))
01776 {
01777 mono_block_cnt_ = (block_type_ & ~(1 << 7)) - 1;
01778 state_ = e_zero_blocks;
01779 break;
01780 }
01781
01782 switch (block_type_)
01783 {
01784 case set_block_azero:
01785 case set_block_end:
01786 end_of_stream_ = true; state_ = e_unknown;
01787 break;
01788 case set_block_1zero:
01789 state_ = e_zero_blocks;
01790 mono_block_cnt_ = 0;
01791 break;
01792 case set_block_8zero:
01793 state_ = e_zero_blocks;
01794 mono_block_cnt_ = decoder_.get_8()-1;
01795 break;
01796 case set_block_16zero:
01797 state_ = e_zero_blocks;
01798 mono_block_cnt_ = decoder_.get_16()-1;
01799 break;
01800 case set_block_32zero:
01801 state_ = e_zero_blocks;
01802 mono_block_cnt_ = decoder_.get_32()-1;
01803 break;
01804 case set_block_aone:
01805 state_ = e_one_blocks;
01806 mono_block_cnt_ = bm::set_total_blocks - block_idx_;
01807 break;
01808 case set_block_1one:
01809 state_ = e_one_blocks;
01810 mono_block_cnt_ = 0;
01811 break;
01812 case set_block_8one:
01813 state_ = e_one_blocks;
01814 mono_block_cnt_ = decoder_.get_8()-1;
01815 break;
01816 case set_block_16one:
01817 state_ = e_one_blocks;
01818 mono_block_cnt_ = decoder_.get_16()-1;
01819 break;
01820 case set_block_32one:
01821 state_ = e_one_blocks;
01822 mono_block_cnt_ = decoder_.get_32()-1;
01823 break;
01824
01825 case set_block_bit:
01826 case set_block_bit_interval:
01827 case set_block_bit_0runs:
01828 case set_block_arrbit:
01829 state_ = e_bit_block;
01830 break;
01831
01832 case set_block_gap:
01833 case set_block_gap_egamma:
01834 gap_head_ =
01835 sizeof(gap_word_t) == 2 ?
01836 decoder_.get_16() : decoder_.get_32();
01837 case set_block_arrgap:
01838 case set_block_arrgap_egamma:
01839 case set_block_arrgap_egamma_inv:
01840 case set_block_arrgap_inv:
01841 case set_block_bit_1bit:
01842 state_ = e_gap_block;
01843 break;
01844 case set_block_gapbit:
01845 state_ = e_gap_block;
01846 break;
01847
01848 default:
01849 BM_ASSERT(0);
01850 }
01851
01852 break;
01853
01854 case e_zero_blocks:
01855 case e_one_blocks:
01856 ++block_idx_;
01857 if (!mono_block_cnt_)
01858 {
01859 state_ = e_blocks;
01860 break;
01861 }
01862 --mono_block_cnt_;
01863 break;
01864
01865 case e_unknown:
01866 default:
01867 BM_ASSERT(0);
01868 }
01869 }
01870
01871 template<class DEC>
01872 void serial_stream_iterator<DEC>::skip_mono_blocks()
01873 {
01874 BM_ASSERT(state_ == e_zero_blocks || state_ == e_one_blocks);
01875 if (!mono_block_cnt_)
01876 {
01877 ++block_idx_;
01878 }
01879 else
01880 {
01881 block_idx_ += mono_block_cnt_+1;
01882 mono_block_cnt_ = 0;
01883 }
01884 state_ = e_blocks;
01885 }
01886
01887 template<class DEC>
01888 unsigned
01889 serial_stream_iterator<DEC>::get_bit_block_ASSIGN(
01890 bm::word_t* dst_block,
01891 bm::word_t* )
01892 {
01893 BM_ASSERT(this->state_ == e_bit_block);
01894 unsigned count = 0;
01895
01896 switch (this->block_type_)
01897 {
01898 case set_block_bit:
01899 decoder_.get_32(dst_block, bm::set_block_size);
01900 break;
01901 case set_block_bit_0runs:
01902 {
01903 if (dst_block)
01904 bit_block_set(dst_block, 0);
01905 unsigned char run_type = decoder_.get_8();
01906 for (unsigned j = 0; j < bm::set_block_size;run_type = !run_type)
01907 {
01908 unsigned run_length = decoder_.get_16();
01909 if (run_type)
01910 {
01911 decoder_.get_32(dst_block ? dst_block + j : dst_block, run_length);
01912 }
01913 j += run_length;
01914 }
01915 }
01916 break;
01917 case set_block_bit_interval:
01918 {
01919 unsigned head_idx = decoder_.get_16();
01920 unsigned tail_idx = decoder_.get_16();
01921 if (dst_block)
01922 {
01923 for (unsigned i = 0; i < head_idx; ++i)
01924 dst_block[i] = 0;
01925 decoder_.get_32(dst_block + head_idx,
01926 tail_idx - head_idx + 1);
01927 for (unsigned j = tail_idx + 1; j < bm::set_block_size; ++j)
01928 dst_block[j] = 0;
01929 }
01930 else
01931 {
01932 decoder_.seek((tail_idx - head_idx + 1) * 4);
01933 }
01934 }
01935 break;
01936 case set_block_arrbit:
01937 case set_block_bit_1bit:
01938 get_arr_bit(dst_block, true );
01939 break;
01940 case set_block_gapbit:
01941 BM_ASSERT(0);
01942 break;
01943 default:
01944 BM_ASSERT(0);
01945 }
01946 return count;
01947 }
01948
01949 template<class DEC>
01950 unsigned
01951 serial_stream_iterator<DEC>::get_bit_block_OR(bm::word_t* dst_block,
01952 bm::word_t* )
01953 {
01954 BM_ASSERT(this->state_ == e_bit_block);
01955 unsigned count = 0;
01956 switch (block_type_)
01957 {
01958 case set_block_bit:
01959 {
01960 bitblock_get_adapter ga(dst_block);
01961 bit_OR<bm::word_t> func;
01962 bitblock_store_adapter sa(dst_block);
01963
01964 bit_recomb(ga,
01965 decoder_,
01966 func,
01967 sa
01968 );
01969 }
01970 break;
01971 case set_block_bit_interval:
01972 {
01973 unsigned head_idx = decoder_.get_16();
01974 unsigned tail_idx = decoder_.get_16();
01975 for (unsigned i = head_idx; i <= tail_idx; ++i)
01976 dst_block[i] |= decoder_.get_32();
01977 }
01978 break;
01979 case set_block_bit_0runs:
01980 {
01981 unsigned char run_type = decoder_.get_8();
01982 for (unsigned j = 0; j < bm::set_block_size;run_type = !run_type)
01983 {
01984 unsigned run_length = decoder_.get_16();
01985 if (run_type)
01986 {
01987 unsigned run_end = j + run_length;
01988 for (;j < run_end; ++j)
01989 {
01990 BM_ASSERT(j < bm::set_block_size);
01991 dst_block[j] |= decoder_.get_32();
01992 }
01993 }
01994 else
01995 {
01996 j += run_length;
01997 }
01998 }
01999 }
02000 break;
02001 case set_block_bit_1bit:
02002 case set_block_arrbit:
02003 get_arr_bit(dst_block, false );
02004 break;
02005 default:
02006 BM_ASSERT(0);
02007 }
02008 return count;
02009 }
02010
02011 template<class DEC>
02012 unsigned
02013 serial_stream_iterator<DEC>::get_bit_block_AND(bm::word_t* dst_block,
02014 bm::word_t* tmp_block)
02015 {
02016 BM_ASSERT(this->state_ == e_bit_block);
02017 BM_ASSERT(dst_block != tmp_block);
02018
02019 unsigned count = 0;
02020 switch (block_type_)
02021 {
02022 case set_block_bit:
02023 for (unsigned i = 0; i < bm::set_block_size; i+=4)
02024 {
02025 dst_block[i] &= decoder_.get_32();
02026 dst_block[i+1] &= decoder_.get_32();
02027 dst_block[i+2] &= decoder_.get_32();
02028 dst_block[i+3] &= decoder_.get_32();
02029 }
02030 break;
02031 case set_block_bit_0runs:
02032 {
02033 unsigned char run_type = decoder_.get_8();
02034 for (unsigned j = 0; j < bm::set_block_size;run_type = !run_type)
02035 {
02036 unsigned run_length = decoder_.get_16();
02037 unsigned run_end = j + run_length;
02038 if (run_type)
02039 {
02040 for (;j < run_end; ++j)
02041 {
02042 BM_ASSERT(j < bm::set_block_size);
02043 dst_block[j] &= decoder_.get_32();
02044 }
02045 }
02046 else
02047 {
02048 for (;j < run_end; ++j)
02049 {
02050 BM_ASSERT(j < bm::set_block_size);
02051 dst_block[j] = 0;
02052 }
02053 }
02054 }
02055 }
02056 break;
02057 case set_block_bit_interval:
02058 {
02059 unsigned head_idx = decoder_.get_16();
02060 unsigned tail_idx = decoder_.get_16();
02061 unsigned i;
02062 for ( i = 0; i < head_idx; ++i)
02063 dst_block[i] = 0;
02064 for ( i = head_idx; i <= tail_idx; ++i)
02065 dst_block[i] &= decoder_.get_32();
02066 for ( i = tail_idx + 1; i < bm::set_block_size; ++i)
02067 dst_block[i] = 0;
02068 }
02069 break;
02070 case set_block_bit_1bit:
02071 case set_block_arrbit:
02072 get_arr_bit(tmp_block, true );
02073 if (dst_block)
02074 bit_block_and(dst_block, tmp_block);
02075 break;
02076 default:
02077 BM_ASSERT(0);
02078 }
02079 return count;
02080 }
02081
02082 template<class DEC>
02083 unsigned
02084 serial_stream_iterator<DEC>::get_bit_block_XOR(bm::word_t* dst_block,
02085 bm::word_t* tmp_block)
02086 {
02087 BM_ASSERT(this->state_ == e_bit_block);
02088 BM_ASSERT(dst_block != tmp_block);
02089
02090 unsigned count = 0;
02091 switch (block_type_)
02092 {
02093 case set_block_bit:
02094 for (unsigned i = 0; i < bm::set_block_size; ++i)
02095 dst_block[i] ^= decoder_.get_32();
02096 break;
02097 case set_block_bit_0runs:
02098 {
02099 unsigned char run_type = decoder_.get_8();
02100 for (unsigned j = 0; j < bm::set_block_size;run_type = !run_type)
02101 {
02102 unsigned run_length = decoder_.get_16();
02103 if (run_type)
02104 {
02105 unsigned run_end = j + run_length;
02106 for (;j < run_end; ++j)
02107 {
02108 BM_ASSERT(j < bm::set_block_size);
02109 dst_block[j] ^= decoder_.get_32();
02110 }
02111 }
02112 else
02113 {
02114 j += run_length;
02115 }
02116 }
02117 }
02118 break;
02119 case set_block_bit_interval:
02120 {
02121 unsigned head_idx = decoder_.get_16();
02122 unsigned tail_idx = decoder_.get_16();
02123 for (unsigned i = head_idx; i <= tail_idx; ++i)
02124 dst_block[i] ^= decoder_.get_32();
02125 }
02126 break;
02127 case set_block_bit_1bit:
02128
02129 case set_block_arrbit:
02130 get_arr_bit(tmp_block, true );
02131 if (dst_block)
02132 {
02133 bit_block_xor(dst_block, tmp_block);
02134 }
02135 break;
02136 default:
02137 BM_ASSERT(0);
02138 }
02139 return count;
02140 }
02141
02142 template<class DEC>
02143 unsigned
02144 serial_stream_iterator<DEC>::get_bit_block_SUB(bm::word_t* dst_block,
02145 bm::word_t* tmp_block)
02146 {
02147 BM_ASSERT(this->state_ == e_bit_block);
02148 BM_ASSERT(dst_block != tmp_block);
02149
02150 unsigned count = 0;
02151 switch (block_type_)
02152 {
02153 case set_block_bit:
02154 for (unsigned i = 0; i < bm::set_block_size; ++i)
02155 dst_block[i] &= ~decoder_.get_32();
02156 break;
02157 case set_block_bit_0runs:
02158 {
02159 unsigned char run_type = decoder_.get_8();
02160 for (unsigned j = 0; j < bm::set_block_size;run_type = !run_type)
02161 {
02162 unsigned run_length = decoder_.get_16();
02163 if (run_type)
02164 {
02165 unsigned run_end = j + run_length;
02166 for (;j < run_end; ++j)
02167 {
02168 BM_ASSERT(j < bm::set_block_size);
02169 dst_block[j] &= ~decoder_.get_32();
02170 }
02171 }
02172 else
02173 {
02174 j += run_length;
02175 }
02176 }
02177 }
02178 break;
02179 case set_block_bit_interval:
02180 {
02181 unsigned head_idx = decoder_.get_16();
02182 unsigned tail_idx = decoder_.get_16();
02183 for (unsigned i = head_idx; i <= tail_idx; ++i)
02184 dst_block[i] &= ~decoder_.get_32();
02185 }
02186 break;
02187 case set_block_bit_1bit:
02188
02189 case set_block_arrbit:
02190 get_arr_bit(tmp_block, true );
02191 if (dst_block)
02192 bit_block_sub(dst_block, tmp_block);
02193 break;
02194 default:
02195 BM_ASSERT(0);
02196 }
02197 return count;
02198 }
02199
02200
02201 template<class DEC>
02202 unsigned
02203 serial_stream_iterator<DEC>::get_bit_block_COUNT(bm::word_t* ,
02204 bm::word_t* )
02205 {
02206 BM_ASSERT(this->state_ == e_bit_block);
02207
02208 unsigned count = 0;
02209 switch (block_type_)
02210 {
02211 case set_block_bit:
02212 for (unsigned i = 0; i < bm::set_block_size; ++i)
02213 count += word_bitcount(decoder_.get_32());
02214 break;
02215 case set_block_bit_0runs:
02216 {
02217 unsigned count = 0;
02218 unsigned char run_type = decoder_.get_8();
02219 for (unsigned j = 0; j < bm::set_block_size;run_type = !run_type)
02220 {
02221 unsigned run_length = decoder_.get_16();
02222 if (run_type)
02223 {
02224 unsigned run_end = j + run_length;
02225 for (;j < run_end; ++j)
02226 {
02227 count += word_bitcount(decoder_.get_32());
02228 }
02229 }
02230 else
02231 {
02232 j += run_length;
02233 }
02234 }
02235 return count;
02236 }
02237 case set_block_bit_interval:
02238 {
02239 unsigned head_idx = decoder_.get_16();
02240 unsigned tail_idx = decoder_.get_16();
02241 for (unsigned i = head_idx; i <= tail_idx; ++i)
02242 count += word_bitcount(decoder_.get_32());
02243 }
02244 break;
02245 case set_block_arrbit:
02246 count += get_arr_bit(0);
02247 break;
02248 case set_block_bit_1bit:
02249 ++count;
02250 decoder_.get_16();
02251 break;
02252 default:
02253 BM_ASSERT(0);
02254 }
02255 return count;
02256 }
02257
02258 template<class DEC>
02259 unsigned
02260 serial_stream_iterator<DEC>::get_bit_block_COUNT_A(bm::word_t* dst_block,
02261 bm::word_t* )
02262 {
02263 BM_ASSERT(this->state_ == e_bit_block);
02264 unsigned count = 0;
02265 if (dst_block)
02266 {
02267
02268 count =
02269 bit_block_calc_count(dst_block,
02270 dst_block + bm::set_block_size);
02271 }
02272
02273 switch (block_type_)
02274 {
02275 case set_block_bit:
02276 decoder_.get_32(0, bm::set_block_size);
02277 break;
02278 case set_block_bit_0runs:
02279 {
02280 unsigned char run_type = decoder_.get_8();
02281 for (unsigned j = 0; j < bm::set_block_size;run_type = !run_type)
02282 {
02283 unsigned run_length = decoder_.get_16();
02284 if (run_type)
02285 {
02286 unsigned run_end = j + run_length;
02287 for (;j < run_end; ++j)
02288 {
02289 decoder_.get_32();
02290 }
02291 }
02292 else
02293 {
02294 j += run_length;
02295 }
02296 }
02297 }
02298 break;
02299
02300 case set_block_bit_interval:
02301 {
02302 unsigned head_idx = decoder_.get_16();
02303 unsigned tail_idx = decoder_.get_16();
02304 for (unsigned i = head_idx; i <= tail_idx; ++i)
02305 decoder_.get_32();
02306 }
02307 break;
02308 case set_block_arrbit:
02309 get_arr_bit(0);
02310 break;
02311 case set_block_bit_1bit:
02312 decoder_.get_16();
02313 break;
02314 default:
02315 BM_ASSERT(0);
02316 }
02317 return count;
02318 }
02319
02320
02321 template<class DEC>
02322 unsigned
02323 serial_stream_iterator<DEC>::get_bit_block_COUNT_AND(bm::word_t* dst_block,
02324 bm::word_t* tmp_block)
02325 {
02326 BM_ASSERT(this->state_ == e_bit_block);
02327 BM_ASSERT(dst_block);
02328
02329 unsigned count = 0;
02330 switch (block_type_)
02331 {
02332 case set_block_bit:
02333 for (unsigned i = 0; i < bm::set_block_size; ++i)
02334 count += word_bitcount(dst_block[i] & decoder_.get_32());
02335 break;
02336 case set_block_bit_0runs:
02337 {
02338 unsigned count = 0;
02339 unsigned char run_type = decoder_.get_8();
02340 for (unsigned j = 0; j < bm::set_block_size;run_type = !run_type)
02341 {
02342 unsigned run_length = decoder_.get_16();
02343 if (run_type)
02344 {
02345 unsigned run_end = j + run_length;
02346 for (;j < run_end; ++j)
02347 {
02348 count += word_bitcount(dst_block[j] & decoder_.get_32());
02349 }
02350 }
02351 else
02352 {
02353 j += run_length;
02354 }
02355 }
02356 return count;
02357 }
02358 case set_block_bit_interval:
02359 {
02360 unsigned head_idx = decoder_.get_16();
02361 unsigned tail_idx = decoder_.get_16();
02362 for (unsigned i = head_idx; i <= tail_idx; ++i)
02363 count += word_bitcount(dst_block[i] & decoder_.get_32());
02364 }
02365 break;
02366 case set_block_bit_1bit:
02367
02368 case set_block_arrbit:
02369 get_arr_bit(tmp_block, true );
02370 count +=
02371 bit_operation_and_count(dst_block, dst_block + bm::set_block_size,
02372 tmp_block);
02373 break;
02374 default:
02375 BM_ASSERT(0);
02376 }
02377 return count;
02378 }
02379
02380 template<class DEC>
02381 unsigned
02382 serial_stream_iterator<DEC>::get_bit_block_COUNT_OR(bm::word_t* dst_block,
02383 bm::word_t* tmp_block)
02384 {
02385 BM_ASSERT(this->state_ == e_bit_block);
02386 BM_ASSERT(dst_block);
02387
02388 bitblock_sum_adapter count_adapter;
02389 switch (block_type_)
02390 {
02391 case set_block_bit:
02392 {
02393 bitblock_get_adapter ga(dst_block);
02394 bit_COUNT_OR<bm::word_t> func;
02395
02396 bit_recomb(ga,
02397 decoder_,
02398 func,
02399 count_adapter
02400 );
02401 }
02402 break;
02403 case set_block_bit_0runs:
02404 {
02405 unsigned count = 0;
02406 unsigned char run_type = decoder_.get_8();
02407 for (unsigned j = 0; j < bm::set_block_size;run_type = !run_type)
02408 {
02409 unsigned run_length = decoder_.get_16();
02410 unsigned run_end = j + run_length;
02411 if (run_type)
02412 {
02413 for (;j < run_end; ++j)
02414 {
02415 BM_ASSERT(j < bm::set_block_size);
02416 count += word_bitcount(dst_block[j] | decoder_.get_32());
02417 }
02418 }
02419 else
02420 {
02421 for (;j < run_end; ++j)
02422 {
02423 BM_ASSERT(j < bm::set_block_size);
02424 count += word_bitcount(dst_block[j]);
02425 }
02426 }
02427 }
02428 return count;
02429 }
02430 case set_block_bit_interval:
02431 {
02432 unsigned head_idx = decoder_.get_16();
02433 unsigned tail_idx = decoder_.get_16();
02434 unsigned count = 0;
02435 unsigned i;
02436 for (i = 0; i < head_idx; ++i)
02437 count += word_bitcount(dst_block[i]);
02438 for (i = head_idx; i <= tail_idx; ++i)
02439 count += word_bitcount(dst_block[i] | decoder_.get_32());
02440 for (i = tail_idx + 1; i < bm::set_block_size; ++i)
02441 count += word_bitcount(dst_block[i]);
02442 return count;
02443 }
02444 case set_block_bit_1bit:
02445
02446 case set_block_arrbit:
02447 get_arr_bit(tmp_block, true );
02448 return
02449 bit_operation_or_count(dst_block,
02450 dst_block + bm::set_block_size,
02451 tmp_block);
02452 default:
02453 BM_ASSERT(0);
02454 }
02455 return count_adapter.sum();
02456 }
02457
02458 template<class DEC>
02459 unsigned
02460 serial_stream_iterator<DEC>::get_bit_block_COUNT_XOR(bm::word_t* dst_block,
02461 bm::word_t* tmp_block)
02462 {
02463 BM_ASSERT(this->state_ == e_bit_block);
02464 BM_ASSERT(dst_block);
02465
02466 bitblock_sum_adapter count_adapter;
02467 switch (block_type_)
02468 {
02469 case set_block_bit:
02470 {
02471 bitblock_get_adapter ga(dst_block);
02472 bit_COUNT_XOR<bm::word_t> func;
02473
02474 bit_recomb(ga,
02475 decoder_,
02476 func,
02477 count_adapter
02478 );
02479 }
02480 break;
02481 case set_block_bit_0runs:
02482 {
02483 unsigned count = 0;
02484 unsigned char run_type = decoder_.get_8();
02485 for (unsigned j = 0; j < bm::set_block_size;run_type = !run_type)
02486 {
02487 unsigned run_length = decoder_.get_16();
02488 unsigned run_end = j + run_length;
02489 if (run_type)
02490 {
02491 for (;j < run_end; ++j)
02492 {
02493 BM_ASSERT(j < bm::set_block_size);
02494 count += word_bitcount(dst_block[j] ^ decoder_.get_32());
02495 }
02496 }
02497 else
02498 {
02499 for (;j < run_end; ++j)
02500 {
02501 BM_ASSERT(j < bm::set_block_size);
02502 count += word_bitcount(dst_block[j]);
02503 }
02504 }
02505 }
02506 return count;
02507 }
02508 case set_block_bit_interval:
02509 {
02510 unsigned head_idx = decoder_.get_16();
02511 unsigned tail_idx = decoder_.get_16();
02512 unsigned count = 0;
02513 unsigned i;
02514 for (i = 0; i < head_idx; ++i)
02515 count += word_bitcount(dst_block[i]);
02516 for (i = head_idx; i <= tail_idx; ++i)
02517 count += word_bitcount(dst_block[i] ^ decoder_.get_32());
02518 for (i = tail_idx + 1; i < bm::set_block_size; ++i)
02519 count += word_bitcount(dst_block[i]);
02520 return count;
02521 }
02522 case set_block_bit_1bit:
02523
02524 case set_block_arrbit:
02525 get_arr_bit(tmp_block, true );
02526 return
02527 bit_operation_xor_count(dst_block,
02528 dst_block + bm::set_block_size,
02529 tmp_block);
02530 default:
02531 BM_ASSERT(0);
02532 }
02533 return count_adapter.sum();
02534 }
02535
02536 template<class DEC>
02537 unsigned
02538 serial_stream_iterator<DEC>::get_bit_block_COUNT_SUB_AB(bm::word_t* dst_block,
02539 bm::word_t* tmp_block)
02540 {
02541 BM_ASSERT(this->state_ == e_bit_block);
02542 BM_ASSERT(dst_block);
02543
02544 bitblock_sum_adapter count_adapter;
02545 switch (block_type_)
02546 {
02547 case set_block_bit:
02548 {
02549 bitblock_get_adapter ga(dst_block);
02550 bit_COUNT_SUB_AB<bm::word_t> func;
02551
02552 bit_recomb(ga,
02553 decoder_,
02554 func,
02555 count_adapter
02556 );
02557 }
02558 break;
02559 case set_block_bit_0runs:
02560 {
02561 unsigned count = 0;
02562 unsigned char run_type = decoder_.get_8();
02563 for (unsigned j = 0; j < bm::set_block_size;run_type = !run_type)
02564 {
02565 unsigned run_length = decoder_.get_16();
02566 unsigned run_end = j + run_length;
02567 if (run_type)
02568 {
02569 for (;j < run_end; ++j)
02570 {
02571 BM_ASSERT(j < bm::set_block_size);
02572 count += word_bitcount(dst_block[j] & ~decoder_.get_32());
02573 }
02574 }
02575 else
02576 {
02577 for (;j < run_end; ++j)
02578 {
02579 BM_ASSERT(j < bm::set_block_size);
02580 count += word_bitcount(dst_block[j]);
02581 }
02582 }
02583 }
02584 return count;
02585 }
02586 case set_block_bit_interval:
02587 {
02588 unsigned head_idx = decoder_.get_16();
02589 unsigned tail_idx = decoder_.get_16();
02590 unsigned count = 0;
02591 unsigned i;
02592 for (i = 0; i < head_idx; ++i)
02593 count += word_bitcount(dst_block[i]);
02594 for (i = head_idx; i <= tail_idx; ++i)
02595 count += word_bitcount(dst_block[i] & (~decoder_.get_32()));
02596 for (i = tail_idx + 1; i < bm::set_block_size; ++i)
02597 count += word_bitcount(dst_block[i]);
02598 return count;
02599 }
02600 break;
02601 case set_block_bit_1bit:
02602
02603 case set_block_arrbit:
02604 get_arr_bit(tmp_block, true );
02605 return
02606 bit_operation_sub_count(dst_block,
02607 dst_block + bm::set_block_size,
02608 tmp_block);
02609 default:
02610 BM_ASSERT(0);
02611 }
02612 return count_adapter.sum();
02613 }
02614
02615 template<class DEC>
02616 unsigned
02617 serial_stream_iterator<DEC>::get_bit_block_COUNT_SUB_BA(bm::word_t* dst_block,
02618 bm::word_t* tmp_block)
02619 {
02620 BM_ASSERT(this->state_ == e_bit_block);
02621 BM_ASSERT(dst_block);
02622
02623 bitblock_sum_adapter count_adapter;
02624 switch (block_type_)
02625 {
02626 case set_block_bit:
02627 {
02628 bitblock_get_adapter ga(dst_block);
02629 bit_COUNT_SUB_BA<bm::word_t> func;
02630
02631 bit_recomb(ga,
02632 decoder_,
02633 func,
02634 count_adapter
02635 );
02636 }
02637 break;
02638 case set_block_bit_0runs:
02639 {
02640 unsigned count = 0;
02641 unsigned char run_type = decoder_.get_8();
02642 for (unsigned j = 0; j < bm::set_block_size;run_type = !run_type)
02643 {
02644 unsigned run_length = decoder_.get_16();
02645 unsigned run_end = j + run_length;
02646 if (run_type)
02647 {
02648 for (;j < run_end; ++j)
02649 {
02650 BM_ASSERT(j < bm::set_block_size);
02651 count += word_bitcount(decoder_.get_32() & (~dst_block[j]));
02652 }
02653 }
02654 else
02655 {
02656 j += run_length;
02657 }
02658 }
02659 return count;
02660 }
02661
02662 case set_block_bit_interval:
02663 {
02664 unsigned head_idx = decoder_.get_16();
02665 unsigned tail_idx = decoder_.get_16();
02666 unsigned count = 0;
02667 unsigned i;
02668 for (i = head_idx; i <= tail_idx; ++i)
02669 count += word_bitcount(decoder_.get_32() & (~dst_block[i]));
02670 return count;
02671 }
02672 break;
02673 case set_block_bit_1bit:
02674
02675 case set_block_arrbit:
02676 get_arr_bit(tmp_block, true );
02677 return
02678 bit_operation_sub_count(tmp_block,
02679 tmp_block + bm::set_block_size,
02680 dst_block);
02681 default:
02682 BM_ASSERT(0);
02683 }
02684 return count_adapter.sum();
02685 }
02686
02687
02688
02689 template<class DEC>
02690 unsigned serial_stream_iterator<DEC>::get_arr_bit(bm::word_t* dst_block,
02691 bool clear_target)
02692 {
02693 BM_ASSERT(this->block_type_ == set_block_arrbit ||
02694 this->block_type_ == set_block_bit_1bit);
02695
02696 gap_word_t len = decoder_.get_16();
02697 if (dst_block)
02698 {
02699 if (clear_target)
02700 bit_block_set(dst_block, 0);
02701
02702 if (this->block_type_ == set_block_bit_1bit)
02703 {
02704
02705 set_bit(dst_block, len);
02706 return 1;
02707 }
02708
02709 for (unsigned k = 0; k < len; ++k)
02710 {
02711 gap_word_t bit_idx = decoder_.get_16();
02712 set_bit(dst_block, bit_idx);
02713 }
02714 }
02715 else
02716 {
02717 if (this->block_type_ == set_block_bit_1bit)
02718 {
02719 return 1;
02720 }
02721
02722 decoder_.seek(len * 2);
02723 }
02724 return len;
02725 }
02726
02727 template<class DEC>
02728 unsigned serial_stream_iterator<DEC>::get_bit()
02729 {
02730 BM_ASSERT(this->block_type_ == set_block_bit_1bit);
02731 ++(this->block_idx_);
02732 this->state_ = e_blocks;
02733
02734 return decoder_.get_16();
02735 }
02736
02737 template<class DEC>
02738 void
02739 serial_stream_iterator<DEC>::get_gap_block(bm::gap_word_t* dst_block)
02740 {
02741 BM_ASSERT(this->state_ == e_gap_block ||
02742 this->block_type_ == set_block_bit_1bit);
02743 BM_ASSERT(dst_block);
02744
02745 read_gap_block(this->decoder_,
02746 this->block_type_,
02747 dst_block,
02748 this->gap_head_);
02749
02750 ++(this->block_idx_);
02751 this->state_ = e_blocks;
02752 }
02753
02754
02755 template<class DEC>
02756 unsigned
02757 serial_stream_iterator<DEC>::get_bit_block(bm::word_t* dst_block,
02758 bm::word_t* tmp_block,
02759 set_operation op)
02760 {
02761 BM_ASSERT(this->state_ == e_bit_block);
02762 get_bit_func_type bit_func = bit_func_table_[op];
02763 BM_ASSERT(bit_func);
02764 unsigned cnt = ((*this).*(bit_func))(dst_block, tmp_block);
02765 this->state_ = e_blocks;
02766 ++(this->block_idx_);
02767 return cnt;
02768 }
02769
02770
02771
02772 template<class BV>
02773 unsigned operation_deserializer<BV>::deserialize(
02774 bvector_type& bv,
02775 const unsigned char* buf,
02776 bm::word_t* temp_block,
02777 set_operation op)
02778 {
02779 ByteOrder bo_current = globals<true>::byte_order();
02780
02781 bm::decoder dec(buf);
02782 unsigned char header_flag = dec.get_8();
02783 ByteOrder bo = bo_current;
02784 if (!(header_flag & BM_HM_NO_BO))
02785 {
02786 bo = (bm::ByteOrder) dec.get_8();
02787 }
02788
02789 blocks_manager_type& bman = bv.get_blocks_manager();
02790 bit_block_guard<blocks_manager_type> bg(bman);
02791 if (temp_block == 0)
02792 {
02793 temp_block = bg.allocate();
02794 }
02795
02796 if (bo_current == bo)
02797 {
02798 serial_stream_current ss(buf);
02799 return
02800 iterator_deserializer<BV, serial_stream_current>::
02801 deserialize(bv, ss, temp_block, op);
02802 }
02803 switch (bo_current)
02804 {
02805 case BigEndian:
02806 {
02807 serial_stream_be ss(buf);
02808 return
02809 iterator_deserializer<BV, serial_stream_be>::
02810 deserialize(bv, ss, temp_block, op);
02811 }
02812 case LittleEndian:
02813 {
02814 serial_stream_le ss(buf);
02815 return
02816 iterator_deserializer<BV, serial_stream_le>::
02817 deserialize(bv, ss, temp_block, op);
02818 }
02819 default:
02820 BM_ASSERT(0);
02821 };
02822 return 0;
02823 }
02824
02825
02826 template<class BV>
02827 void operation_deserializer<BV>::deserialize(
02828 bvector_type& bv_target,
02829 const bvector_type& bv_mask,
02830 const unsigned char* buf,
02831 bm::word_t* temp_block,
02832 set_operation op)
02833 {
02834 ByteOrder bo_current = globals<true>::byte_order();
02835
02836 bm::decoder dec(buf);
02837 unsigned char header_flag = dec.get_8();
02838 ByteOrder bo = bo_current;
02839 if (!(header_flag & BM_HM_NO_BO))
02840 {
02841 bo = (bm::ByteOrder) dec.get_8();
02842 }
02843
02844 blocks_manager_type& bman = bv_target.get_blocks_manager();
02845 bit_block_guard<blocks_manager_type> bg(bman);
02846 if (temp_block == 0)
02847 {
02848 temp_block = bg.allocate();
02849 }
02850
02851 if (bo_current == bo)
02852 {
02853 serial_stream_current ss(buf);
02854 iterator_deserializer<BV, serial_stream_current>::
02855 deserialize(bv_target, bv_mask, ss, temp_block, op);
02856 return;
02857 }
02858 switch (bo_current)
02859 {
02860 case BigEndian:
02861 {
02862 serial_stream_be ss(buf);
02863 iterator_deserializer<BV, serial_stream_be>::
02864 deserialize(bv_target, bv_mask, ss, temp_block, op);
02865 }
02866 case LittleEndian:
02867 {
02868 serial_stream_le ss(buf);
02869 iterator_deserializer<BV, serial_stream_le>::
02870 deserialize(bv_target, bv_mask, ss, temp_block, op);
02871 }
02872 default:
02873 BM_ASSERT(0);
02874 };
02875 }
02876
02877
02878 template<class BV, class SerialIterator>
02879 void iterator_deserializer<BV, SerialIterator>::load_id_list(
02880 bvector_type& bv,
02881 serial_iterator_type& sit,
02882 unsigned id_count,
02883 bool set_clear)
02884 {
02885 const unsigned win_size = 64;
02886 bm::id_t id_buffer[win_size+1];
02887
02888 if (set_clear)
02889 {
02890 for (unsigned i = 0; i <= id_count;)
02891 {
02892 unsigned j;
02893 for (j = 0; j < win_size && i <= id_count; ++j, ++i)
02894 {
02895 id_buffer[j] = sit.get_id();
02896 sit.next();
02897 }
02898 bm::combine_or(bv, id_buffer, id_buffer + j);
02899 }
02900 }
02901 else
02902 {
02903 for (unsigned i = 0; i <= id_count;)
02904 {
02905 unsigned j;
02906 for (j = 0; j < win_size && i <= id_count; ++j, ++i)
02907 {
02908 id_buffer[j] = sit.get_id();
02909 sit.next();
02910 }
02911 bm::combine_sub(bv, id_buffer, id_buffer + j);
02912 }
02913 }
02914 }
02915
02916 template<class BV, class SerialIterator>
02917 unsigned
02918 iterator_deserializer<BV, SerialIterator>::finalize_target_vector(
02919 blocks_manager_type& bman,
02920 set_operation op,
02921 unsigned bv_block_idx)
02922 {
02923 unsigned count = 0;
02924 switch (op)
02925 {
02926 case set_OR: case set_SUB: case set_XOR:
02927 case set_COUNT: case set_COUNT_B: case set_COUNT_AND:
02928 case set_COUNT_SUB_BA:
02929
02930 break;
02931 case set_AND: case set_ASSIGN:
02932
02933 {
02934 unsigned i, j;
02935 bman.get_block_coord(bv_block_idx, &i, &j);
02936 bm::word_t*** blk_root = bman.get_rootblock();
02937 unsigned effective_top_size =
02938 bman.effective_top_block_size();
02939 for (;i < effective_top_size; ++i)
02940 {
02941 bm::word_t** blk_blk = blk_root[i];
02942 if (blk_blk == 0)
02943 {
02944 bv_block_idx+=bm::set_array_size-j;
02945 j = 0;
02946 continue;
02947 }
02948 for (;j < bm::set_array_size; ++j, ++bv_block_idx)
02949 {
02950 if (blk_blk[j])
02951 bman.zero_block(bv_block_idx);
02952 }
02953 j = 0;
02954 }
02955
02956 }
02957 break;
02958 case set_COUNT_A: case set_COUNT_OR: case set_COUNT_XOR:
02959 case set_COUNT_SUB_AB:
02960
02961 {
02962 unsigned i, j;
02963 bman.get_block_coord(bv_block_idx, &i, &j);
02964 bm::word_t*** blk_root = bman.get_rootblock();
02965 unsigned effective_top_size =
02966 bman.effective_top_block_size();
02967 for (;i < effective_top_size; ++i)
02968 {
02969 bm::word_t** blk_blk = blk_root[i];
02970 if (blk_blk == 0)
02971 {
02972 bv_block_idx+=bm::set_array_size-j;
02973 j = 0;
02974 continue;
02975 }
02976 for (;j < bm::set_array_size; ++j, ++bv_block_idx)
02977 {
02978 if (blk_blk[j])
02979 count += bman.block_bitcount(blk_blk[j], bv_block_idx);
02980 }
02981 j = 0;
02982 }
02983
02984 }
02985 break;
02986 default:
02987 BM_ASSERT(0);
02988 }
02989 return count;
02990 }
02991
02992 template<class BV, class SerialIterator>
02993 unsigned
02994 iterator_deserializer<BV, SerialIterator>::process_id_list(
02995 bvector_type& bv,
02996 serial_iterator_type& sit,
02997 set_operation op)
02998 {
02999 unsigned count = 0;
03000 unsigned id_count = sit.get_id_count();
03001 bool set_clear = true;
03002 switch (op)
03003 {
03004 case set_AND:
03005 {
03006
03007 BV bv_tmp(BM_GAP);
03008 load_id_list(bv_tmp, sit, id_count, true);
03009 bv &= bv_tmp;
03010 }
03011 break;
03012 case set_ASSIGN:
03013 bv.clear(true);
03014
03015 case set_OR:
03016 set_clear = true;
03017
03018 case set_SUB:
03019 load_id_list(bv, sit, id_count, set_clear);
03020 break;
03021 case set_XOR:
03022 for (unsigned i = 0; i < id_count; ++i)
03023 {
03024 bm::id_t id = sit.get_id();
03025 bv[id] ^= true;
03026 sit.next();
03027 }
03028 break;
03029 case set_COUNT: case set_COUNT_B:
03030 for (unsigned i = 0; i < id_count; ++i)
03031 {
03032 sit.get_id();
03033 ++count;
03034 sit.next();
03035 }
03036 break;
03037 case set_COUNT_A:
03038 return bv.count();
03039 case set_COUNT_AND:
03040 for (unsigned i = 0; i < id_count; ++i)
03041 {
03042 bm::id_t id = sit.get_id();
03043 count += bv.get_bit(id);
03044 sit.next();
03045 }
03046 break;
03047 case set_COUNT_XOR:
03048 {
03049
03050 BV bv_tmp(BM_GAP);
03051 load_id_list(bv_tmp, sit, id_count, true);
03052 count += count_xor(bv, bv_tmp);
03053 }
03054 break;
03055 case set_COUNT_OR:
03056 {
03057
03058 BV bv_tmp(BM_GAP);
03059 load_id_list(bv_tmp, sit, id_count, true);
03060 count += count_or(bv, bv_tmp);
03061 }
03062 break;
03063 case set_COUNT_SUB_AB:
03064 {
03065
03066 BV bv_tmp(bv);
03067 load_id_list(bv_tmp, sit, id_count, false);
03068 count += bv_tmp.count();
03069 }
03070 break;
03071 default:
03072 BM_ASSERT(0);
03073 }
03074
03075 return count;
03076 }
03077
03078
03079 template<class BV, class SerialIterator>
03080 void iterator_deserializer<BV, SerialIterator>::deserialize(
03081 bvector_type& bv_target,
03082 const bvector_type& bv_mask,
03083 serial_iterator_type& sit,
03084 bm::word_t* temp_block,
03085 set_operation op)
03086 {
03087 BM_ASSERT(temp_block);
03088 BM_ASSERT(op == bm::set_AND ||
03089 op == bm::set_OR || op == bm::set_XOR || op == bm::set_SUB);
03090
03091 gap_word_t gap_temp_block[bm::gap_equiv_len*3];
03092 gap_temp_block[0] = 0;
03093
03094 bv_target.clear(true);
03095
03096 const blocks_manager_type& bman_mask = bv_mask.get_blocks_manager();
03097 blocks_manager_type& bman_target = bv_target.get_blocks_manager();
03098
03099 unsigned bv_size = sit.bv_size();
03100 if (bv_mask.size() > bv_size)
03101 {
03102 bv_size = bv_mask.size();
03103 }
03104 if (bv_target.size() < bv_size)
03105 {
03106 bv_target.resize(bv_size);
03107 }
03108
03109 unsigned top_blocks = bman_mask.effective_top_block_size();
03110
03111 BM_SET_MMX_GUARD
03112
03113 typename serial_iterator_type::iterator_state state;
03114 state = sit.get_state();
03115 if (state == serial_iterator_type::e_list_ids)
03116 {
03117 bv_target = bv_mask;
03118 process_id_list(bv_target, sit, op);
03119 return;
03120 }
03121
03122 unsigned bv_block_idx = 0;
03123 for (;1;)
03124 {
03125 bv_block_idx = sit.block_idx();
03126
03127 {
03128 unsigned tb_idx = bv_block_idx >> bm::set_array_shift;
03129 if (tb_idx > top_blocks)
03130 {
03131 if (op == bm::set_AND)
03132 break;
03133 if (sit.is_eof())
03134 break;
03135 }
03136 }
03137
03138 if (sit.is_eof())
03139 {
03140 if (op == bm::set_AND)
03141 break;
03142
03143 state = serial_iterator_type::e_zero_blocks;
03144 }
03145 else
03146 {
03147 state = sit.state();
03148 }
03149
03150 switch (state)
03151 {
03152 case serial_iterator_type::e_blocks:
03153 sit.next();
03154 continue;
03155 case serial_iterator_type::e_bit_block:
03156 {
03157 bm::set_operation sop = op;
03158 const bm::word_t* blk_mask = bman_mask.get_block(bv_block_idx);
03159 bm::word_t* blk_target = 0;
03160 if (!blk_mask)
03161 {
03162 switch (op)
03163 {
03164 case set_AND: case set_SUB:
03165
03166
03167 sop = set_ASSIGN;
03168 break;
03169 case set_OR: case set_XOR:
03170 blk_target = bman_target.make_bit_block(bv_block_idx);
03171 break;
03172 default:
03173 BM_ASSERT(0);
03174 }
03175 }
03176 else
03177 {
03178 int is_gap = BM_IS_GAP(bman_mask, blk_mask, bv_block_idx);
03179 blk_target = bman_target.copy_bit_block(bv_block_idx, blk_mask, is_gap);
03180 }
03181
03182
03183 sit.get_bit_block(blk_target, temp_block, sop);
03184 }
03185 break;
03186
03187 case serial_iterator_type::e_zero_blocks:
03188 {
03189 if (op == set_AND)
03190 {
03191 sit.skip_mono_blocks();
03192 break;
03193 }
03194 sit.next();
03195
03196 bman_target.copy_block(bv_block_idx, bman_mask);
03197 }
03198 break;
03199
03200 case serial_iterator_type::e_one_blocks:
03201 {
03202 BM_ASSERT(bv_block_idx == sit.block_idx());
03203 const bm::word_t* blk_mask = bman_mask.get_block(bv_block_idx);
03204 sit.next();
03205
03206 switch (op)
03207 {
03208 case set_OR:
03209 bman_target.set_block_all_set(bv_block_idx);
03210 break;
03211 case set_SUB:
03212 break;
03213 case set_AND:
03214 bman_target.copy_block(bv_block_idx, bman_mask);
03215 break;
03216 case set_XOR:
03217 if (blk_mask)
03218 {
03219 int is_gap = BM_IS_GAP(bman_mask, blk_mask, bv_block_idx);
03220 bm::word_t* blk_target =
03221 bman_target.copy_bit_block(bv_block_idx, blk_mask, is_gap);
03222 bit_block_xor(blk_target, FULL_BLOCK_ADDR);
03223 }
03224 else
03225 {
03226
03227 bman_target.set_block_all_set(bv_block_idx);
03228 }
03229 break;
03230 default:
03231 BM_ASSERT(0);
03232 }
03233
03234 }
03235 break;
03236
03237 case serial_iterator_type::e_gap_block:
03238 {
03239
03240 if (sit.get_block_type() == set_block_bit_1bit)
03241 {
03242 if (op == set_AND)
03243 {
03244 unsigned bit_idx = sit.get_bit();
03245 unsigned bn = (bv_block_idx << bm::set_block_shift) | bit_idx;
03246 bool bval_mask = bv_mask.test(bn);
03247 bv_target.set_bit(bn, bval_mask);
03248 break;
03249 }
03250 }
03251
03252 const bm::word_t* blk_mask = bman_mask.get_block(bv_block_idx);
03253
03254 sit.get_gap_block(gap_temp_block);
03255
03256
03257 unsigned len = gap_length(gap_temp_block);
03258 int level = gap_calc_level(len, bman_target.glen());
03259 --len;
03260
03261
03262 if (!blk_mask)
03263 {
03264 if (op == set_OR || op == set_XOR)
03265 {
03266 bman_target.set_gap_block(bv_block_idx, gap_temp_block, level);
03267 }
03268 }
03269 else
03270 {
03271
03272 bm::operation bop = bm::setop2op(op);
03273 bman_target.copy_block(bv_block_idx, bman_mask);
03274 bv_target.combine_operation_with_block(
03275 bv_block_idx,
03276 (bm::word_t*)gap_temp_block,
03277 1,
03278 bop);
03279 }
03280
03281 }
03282 break;
03283
03284 default:
03285 BM_ASSERT(0);
03286 }
03287
03288
03289 }
03290
03291 bv_target.forget_count();
03292 }
03293
03294
03295
03296 template<class BV, class SerialIterator>
03297 unsigned
03298 iterator_deserializer<BV, SerialIterator>::deserialize(
03299 bvector_type& bv,
03300 serial_iterator_type& sit,
03301 bm::word_t* temp_block,
03302 set_operation op)
03303 {
03304 BM_ASSERT(temp_block);
03305
03306 unsigned count = 0;
03307 gap_word_t gap_temp_block[bm::gap_equiv_len*3];
03308 gap_temp_block[0] = 0;
03309
03310 blocks_manager_type& bman = bv.get_blocks_manager();
03311
03312 bv.forget_count();
03313 if (sit.bv_size() && (sit.bv_size() > bv.size()))
03314 {
03315 bv.resize(sit.bv_size());
03316 }
03317
03318 BM_SET_MMX_GUARD
03319
03320 typename serial_iterator_type::iterator_state state;
03321 state = sit.get_state();
03322 if (state == serial_iterator_type::e_list_ids)
03323 {
03324 count = process_id_list(bv, sit, op);
03325 return count;
03326 }
03327
03328 unsigned bv_block_idx = 0;
03329
03330 for (;1;)
03331 {
03332 bm::set_operation sop = op;
03333 if (sit.is_eof())
03334 {
03335 count += finalize_target_vector(bman, op, bv_block_idx);
03336 return count;
03337 }
03338
03339 state = sit.state();
03340 switch (state)
03341 {
03342 case serial_iterator_type::e_blocks:
03343 sit.next();
03344 continue;
03345 case serial_iterator_type::e_bit_block:
03346 {
03347 BM_ASSERT(sit.block_idx() == bv_block_idx);
03348 bm::word_t* blk = bman.get_block(bv_block_idx);
03349
03350 if (!blk)
03351 {
03352 switch (op)
03353 {
03354 case set_AND: case set_SUB: case set_COUNT_AND:
03355 case set_COUNT_SUB_AB: case set_COUNT_A:
03356
03357
03358 sop = set_ASSIGN;
03359 break;
03360
03361 case set_OR: case set_XOR: case set_ASSIGN:
03362 blk = bman.make_bit_block(bv_block_idx);
03363 break;
03364
03365 case set_COUNT: case set_COUNT_XOR: case set_COUNT_OR:
03366 case set_COUNT_SUB_BA: case set_COUNT_B:
03367
03368 sop = set_COUNT;
03369 break;
03370
03371 case set_END:
03372 default:
03373 BM_ASSERT(0);
03374 }
03375 }
03376 else
03377 {
03378 int is_gap = BM_IS_GAP(bman, blk, bv_block_idx);
03379 if (is_gap || IS_FULL_BLOCK(blk))
03380 {
03381 if (IS_FULL_BLOCK(blk) && is_const_set_operation(op))
03382 {
03383 }
03384 else
03385 {
03386
03387
03388 blk = bman.deoptimize_block(bv_block_idx);
03389 }
03390 }
03391 }
03392
03393
03394 unsigned c = sit.get_bit_block(blk, temp_block, sop);
03395 count += c;
03396 }
03397 break;
03398
03399 case serial_iterator_type::e_zero_blocks:
03400 {
03401 BM_ASSERT(bv_block_idx == sit.block_idx());
03402 bm::word_t* blk = bman.get_block(bv_block_idx);
03403 sit.next();
03404
03405 if (blk)
03406 {
03407 switch (op)
03408 {
03409 case set_AND: case set_ASSIGN:
03410
03411 blk = bman.zero_block(bv_block_idx);
03412 break;
03413
03414 case set_SUB: case set_COUNT_AND: case set_OR:
03415 case set_XOR: case set_COUNT_SUB_BA: case set_COUNT_B:
03416
03417 break;
03418
03419 case set_COUNT_SUB_AB: case set_COUNT_A: case set_COUNT_OR:
03420 case set_COUNT: case set_COUNT_XOR:
03421
03422
03423
03424 {
03425 unsigned c = bman.block_bitcount(blk, bv_block_idx);
03426 count += c;
03427 }
03428 break;
03429 case set_END:
03430 default:
03431 BM_ASSERT(0);
03432 }
03433 }
03434 }
03435 break;
03436
03437 case serial_iterator_type::e_one_blocks:
03438 {
03439 BM_ASSERT(bv_block_idx == sit.block_idx());
03440 bm::word_t* blk = bman.get_block(bv_block_idx);
03441 sit.next();
03442
03443 switch (op)
03444 {
03445 case set_OR: case set_ASSIGN:
03446 bman.set_block_all_set(bv_block_idx);
03447 break;
03448 case set_COUNT_OR: case set_COUNT_B: case set_COUNT:
03449
03450 count += bm::bits_in_block;
03451 break;
03452 case set_SUB:
03453 blk = bman.zero_block(bv_block_idx);
03454 break;
03455 case set_COUNT_SUB_AB: case set_AND:
03456
03457 break;
03458 case set_COUNT_AND: case set_COUNT_A:
03459 count += bman.block_bitcount(blk, bv_block_idx);
03460 break;
03461 default:
03462 if (blk)
03463 {
03464 switch (op)
03465 {
03466 case set_XOR:
03467 blk = bman.deoptimize_block(bv_block_idx);
03468 bit_block_xor(blk, FULL_BLOCK_ADDR);
03469 break;
03470 case set_COUNT_XOR:
03471 {
03472 int is_gap = BM_IS_GAP(bman, blk, bv_block_idx);
03473 count +=
03474 combine_count_operation_with_block(
03475 blk,
03476 is_gap,
03477 FULL_BLOCK_ADDR,
03478 0,
03479 temp_block,
03480 bm::COUNT_XOR);
03481 }
03482 break;
03483 case set_COUNT_SUB_BA:
03484 {
03485 int is_gap = BM_IS_GAP(bman, blk, bv_block_idx);
03486 count +=
03487 combine_count_operation_with_block(
03488 blk,
03489 is_gap,
03490 FULL_BLOCK_ADDR,
03491 0,
03492 temp_block,
03493 bm::COUNT_SUB_BA);
03494 }
03495 break;
03496 default:
03497 BM_ASSERT(0);
03498 }
03499 }
03500 else
03501 {
03502 switch (op)
03503 {
03504 case set_XOR:
03505
03506 bman.set_block_all_set(bv_block_idx);
03507 break;
03508 case set_COUNT_XOR:
03509 count += bm::bits_in_block;
03510 break;
03511 case set_COUNT_SUB_BA:
03512
03513 count += bm::bits_in_block;
03514 break;
03515 default:
03516 break;
03517 }
03518 }
03519 }
03520
03521 }
03522 break;
03523
03524 case serial_iterator_type::e_gap_block:
03525 {
03526 BM_ASSERT(bv_block_idx == sit.block_idx());
03527 bm::word_t* blk = bman.get_block(bv_block_idx);
03528
03529 sit.get_gap_block(gap_temp_block);
03530
03531
03532 unsigned len = gap_length(gap_temp_block);
03533 int level = gap_calc_level(len, bman.glen());
03534 --len;
03535
03536 bool const_op = is_const_set_operation(op);
03537 if (const_op)
03538 {
03539 distance_metric metric = operation2metric(op);
03540 int is_gap = blk ? BM_IS_GAP(bman, blk, bv_block_idx) : 0;
03541 unsigned c =
03542 combine_count_operation_with_block(
03543 blk,
03544 is_gap,
03545 (bm::word_t*)gap_temp_block,
03546 1,
03547 temp_block,
03548 metric);
03549 count += c;
03550 }
03551 else
03552 {
03553 if ((sop == set_ASSIGN) && blk)
03554 {
03555 blk = bman.zero_block(bv_block_idx);
03556 sop = set_OR;
03557 }
03558 if (blk == 0)
03559 {
03560 switch (sop)
03561 {
03562 case set_AND: case set_SUB:
03563 break;
03564 case set_OR: case set_XOR: case set_ASSIGN:
03565 bman.set_gap_block(
03566 bv_block_idx, gap_temp_block, level);
03567 break;
03568 default:
03569 BM_ASSERT(0);
03570 }
03571 }
03572 else
03573 {
03574 bm::operation bop = bm::setop2op(op);
03575 if (level == -1)
03576 {
03577 gap_convert_to_bitset(temp_block, gap_temp_block);
03578 bv.combine_operation_with_block(bv_block_idx,
03579 temp_block,
03580 0,
03581 bop);
03582 }
03583 else
03584 {
03585 set_gap_level(gap_temp_block, level);
03586 bv.combine_operation_with_block(
03587 bv_block_idx,
03588 (bm::word_t*)gap_temp_block,
03589 1,
03590 bop);
03591 }
03592 }
03593 }
03594 }
03595 break;
03596
03597 default:
03598 BM_ASSERT(0);
03599 }
03600
03601 ++bv_block_idx;
03602
03603 }
03604
03605 return count;
03606 }
03607
03608
03609
03610
03611 }
03612
03613 #include "bmundef.h"
03614
03615 #ifdef _MSC_VER
03616 #pragma warning( default : 4311 4312)
03617 #endif
03618
03619
03620 #endif