1 #ifndef BMTRANS__H__INCLUDED__ 2 #define BMTRANS__H__INCLUDED__ 26 #pragma warning( push ) 27 #pragma warning( disable : 4311 4312 4127) 39 template<
typename T,
unsigned ROWS,
unsigned COLS>
61 static unsigned rows() {
return ROWS; }
62 static unsigned cols() {
return COLS; }
64 const T*
row(
unsigned row_idx)
const 67 return value[row_idx];
69 T*
row(
unsigned row_idx)
72 return value[row_idx];
81 template<
typename T,
unsigned BPC>
85 unsigned get(
const T*, unsigned)
95 unsigned get(
const unsigned* arr,
unsigned j)
97 return (((arr[0] >> j) & 1) << 0) |
98 (((arr[1] >> j) & 1) << 1) |
99 (((arr[2] >> j) & 1) << 2) |
100 (((arr[3] >> j) & 1) << 3) |
101 (((arr[4] >> j) & 1) << 4) |
102 (((arr[5] >> j) & 1) << 5) |
103 (((arr[6] >> j) & 1) << 6) |
104 (((arr[7] >> j) & 1) << 7) |
105 (((arr[8] >> j) & 1) << 8) |
106 (((arr[9] >> j) & 1) << 9) |
107 (((arr[10]>> j) & 1) << 10)|
108 (((arr[11]>> j) & 1) << 11)|
109 (((arr[12]>> j) & 1) << 12)|
110 (((arr[13]>> j) & 1) << 13)|
111 (((arr[14]>> j) & 1) << 14)|
112 (((arr[15]>> j) & 1) << 15)|
113 (((arr[16]>> j) & 1) << 16)|
114 (((arr[17]>> j) & 1) << 17)|
115 (((arr[18]>> j) & 1) << 18)|
116 (((arr[19]>> j) & 1) << 19)|
117 (((arr[20]>> j) & 1) << 20)|
118 (((arr[21]>> j) & 1) << 21)|
119 (((arr[22]>> j) & 1) << 22)|
120 (((arr[23]>> j) & 1) << 23)|
121 (((arr[24]>> j) & 1) << 24)|
122 (((arr[25]>> j) & 1) << 25)|
123 (((arr[26]>> j) & 1) << 26)|
124 (((arr[27]>> j) & 1) << 27)|
125 (((arr[28]>> j) & 1) << 28)|
126 (((arr[29]>> j) & 1) << 29)|
127 (((arr[30]>> j) & 1) << 30)|
128 (((arr[31]>> j) & 1) << 31);
136 unsigned get(
const unsigned short* arr,
unsigned j)
138 return (((arr[0] >> j) & 1u) << 0u) |
139 (((arr[1] >> j) & 1u) << 1u) |
140 (((arr[2] >> j) & 1u) << 2u) |
141 (((arr[3] >> j) & 1u) << 3u) |
142 (((arr[4] >> j) & 1u) << 4u) |
143 (((arr[5] >> j) & 1u) << 5u) |
144 (((arr[6] >> j) & 1u) << 6u) |
145 (((arr[7] >> j) & 1u) << 7u) |
146 (((arr[8] >> j) & 1u) << 8u) |
147 (((arr[9] >> j) & 1u) << 9u) |
148 (((arr[10]>> j) & 1u) << 10u)|
149 (((arr[11]>> j) & 1u) << 11u)|
150 (((arr[12]>> j) & 1u) << 12u)|
151 (((arr[13]>> j) & 1u) << 13u)|
152 (((arr[14]>> j) & 1u) << 14u)|
153 (((arr[15]>> j) & 1u) << 15u);
162 unsigned get(
const unsigned char* arr,
unsigned j)
165 (((arr[0] >> j) & 1) << 0) |
166 (((arr[1] >> j) & 1) << 1) |
167 (((arr[2] >> j) & 1) << 2) |
168 (((arr[3] >> j) & 1) << 3) |
169 (((arr[4] >> j) & 1) << 4) |
170 (((arr[5] >> j) & 1) << 5) |
171 (((arr[6] >> j) & 1) << 6) |
172 (((arr[7] >> j) & 1) << 7));
181 template<
typename T,
unsigned BPC,
unsigned BPS>
185 T
get(
const T
tmatrix[BPC][BPS],
unsigned i,
unsigned j)
195 (((tmatrix[0][i] >> j) & 1) << 0) |
196 (((tmatrix[1][i] >> j) & 1) << 1) |
197 (((tmatrix[2][i] >> j) & 1) << 2) |
198 (((tmatrix[3][i] >> j) & 1) << 3) |
199 (((tmatrix[4][i] >> j) & 1) << 4) |
200 (((tmatrix[5][i] >> j) & 1) << 5) |
201 (((tmatrix[6][i] >> j) & 1) << 6) |
202 (((tmatrix[7][i] >> j) & 1) << 7);
208 (((tmatrix[8][i] >> j) & 1) << 8) |
209 (((tmatrix[9][i] >> j) & 1) << 9) |
210 (((tmatrix[10][i] >> j) & 1) << 10) |
211 (((tmatrix[11][i] >> j) & 1) << 11) |
212 (((tmatrix[12][i] >> j) & 1) << 12) |
213 (((tmatrix[13][i] >> j) & 1) << 13) |
214 (((tmatrix[14][i] >> j) & 1) << 14) |
215 (((tmatrix[15][i] >> j) & 1) << 15);
222 (((tmatrix[16][i] >> j) & 1) << 16) |
223 (((tmatrix[17][i] >> j) & 1) << 17) |
224 (((tmatrix[18][i] >> j) & 1) << 18) |
225 (((tmatrix[19][i] >> j) & 1) << 19) |
226 (((tmatrix[20][i] >> j) & 1) << 20) |
227 (((tmatrix[21][i] >> j) & 1) << 21) |
228 (((tmatrix[22][i] >> j) & 1) << 22) |
229 (((tmatrix[23][i] >> j) & 1) << 23) |
230 (((tmatrix[24][i] >> j) & 1) << 24) |
231 (((tmatrix[25][i] >> j) & 1) << 25) |
232 (((tmatrix[26][i] >> j) & 1) << 26) |
233 (((tmatrix[27][i] >> j) & 1) << 27) |
234 (((tmatrix[28][i] >> j) & 1) << 28) |
235 (((tmatrix[29][i] >> j) & 1) << 29) |
236 (((tmatrix[30][i] >> j) & 1) << 30) |
237 (((tmatrix[31][i] >> j) & 1) << 31);
256 template<
typename T,
unsigned BPC,
unsigned BPS>
264 for (
unsigned i = 0; i < arr_size;
268 for (
unsigned j = 0; j < BPC; ++j)
289 template<
typename T,
unsigned BPC,
unsigned BPS>
294 for (
unsigned i = 0; i < BPS; ++i)
296 for (
unsigned j = 0; j < BPC; ++j, ++col)
314 template<
typename T,
unsigned BPC,
unsigned BPS>
316 unsigned distance[BPC][BPC])
318 for (
unsigned i = 0; i < BPC; ++i)
325 for (
unsigned j = i + 1; j < BPC; ++j)
333 const T* r2_end = r2 + BPS;
342 }
while (r2 < r2_end);
344 distance[i][j] = count;
380 template<
typename T,
unsigned BPC,
unsigned BPS>
382 const unsigned distance[BPC][BPC],
383 unsigned char* pc_vector)
387 for (
unsigned i = 0; i < BPC; ++i)
390 unsigned row_bitcount = distance[i][i];
392 const unsigned total_possible_max =
sizeof(T)*8*BPS;
393 switch (row_bitcount)
398 case total_possible_max:
406 if (row_bitcount > total_possible_max/2)
415 unsigned rmin_idx = 0;
416 for (
unsigned j = i + 1; j < BPC; ++j)
418 unsigned d = distance[i][j];
423 pc = (
unsigned char)(ibpc_equiv | (j << 3));
426 rmin = d; rmin_idx = j;
430 if ((pc == 0) && rmin_idx && (rmin < row_bitcount))
432 pc = (
unsigned char)(ibpc_close | (rmin_idx << 3));
444 const unsigned char*
BMRESTRICT pc_vector_end,
452 unsigned ibpc = *pc_vector & 7;
453 ++(pc_vector_stat[ibpc]);
454 }
while (++pc_vector < pc_vector_end);
466 const unsigned char*
BMRESTRICT pc_vector_end,
473 unsigned ibpc = *pc_vector & 7;
474 unsigned n_row = *pc_vector >> 3;
481 unsigned* r_out = tmatrix_out[
row];
497 const unsigned* r2 =
tmatrix[n_row];
498 unsigned* r_out = tmatrix_out[
row];
501 r_out[i] = r1[i] ^ r2[i];
510 }
while (++pc_vector < pc_vector_end);
517 template<
class TMatrix>
519 const unsigned char* pc_vector,
520 const unsigned effective_cols)
524 typedef typename TMatrix::value_type
value_type;
526 const unsigned char* pc_vector_end = pc_vector + tmatrix.rows();
528 unsigned cols = effective_cols ? effective_cols : tmatrix.cols();
532 unsigned ibpc = *pc_vector & 7;
542 unsigned n_row = *pc_vector >> 3;
545 value_type* r1 = tmatrix.row(row);
546 const value_type* r2 = tmatrix.row(n_row);
547 for (
unsigned i = 0; i <
cols; ++i)
558 }
while (++pc_vector < pc_vector_end);
564 template<
class TMatrix>
566 const unsigned char* pc_vector,
567 const unsigned effective_cols)
571 typedef typename TMatrix::value_type
value_type;
573 unsigned cols = effective_cols ? effective_cols : tmatrix.cols();
574 for (
unsigned row = tmatrix.rows()-1u; 1; --
row)
576 unsigned ibpc = pc_vector[
row] & 7u;
577 unsigned n_row = pc_vector[
row] >> 3u;
579 value_type* r1 = tmatrix.row(
unsigned(
row));
586 for (
unsigned i = 0; i <
cols; ++i)
590 for (
unsigned i = 0; i <
cols; ++i)
591 r1[i] = (value_type)(~0);
596 const value_type* r2 = tmatrix.row(n_row);
597 for (
unsigned i = 0; i <
cols; ++i)
604 const value_type* r2 = tmatrix.row(n_row);
605 for (
unsigned i = 0; i <
cols; ++i)
626 template<
typename GT,
typename BT>
631 GT* dgap_buf = (GT*) block;
632 BT* block_end = block + block_size;
634 GT* dgap_end = gap_2_dgap<GT>(gap_buf, dgap_buf,
false);
635 GT* block_end2 = (GT*) block_end;
638 for ( ;dgap_end < block_end2; ++dgap_end)
655 template<
class TMatrix>
656 void compute_tmatrix_rstat(
const TMatrix&
tmatrix,
657 const unsigned char* pc_vector,
658 typename TMatrix::rstat* rstat,
659 unsigned effective_cols)
662 typedef typename TMatrix::value_type
value_type;
664 unsigned cols = effective_cols ? effective_cols : tmatrix.cols();
666 unsigned rows = tmatrix.rows();
668 for (
unsigned i = 0; i <
rows; ++i)
670 unsigned ibpc = pc_vector[i] & 7;
676 rstat[i].bit_count = rstat[i].gap_count = 0;
682 const value_type* r1 = tmatrix.row(i);
683 const value_type* r1_end = r1 +
cols;
688 const unsigned bitset_size = unsigned(
sizeof(value_type) * cols);
689 const unsigned total_possible_max_bits = unsigned(
sizeof(value_type)*8*cols);
693 total_possible_max_bits,
713 template<
typename TM>
718 for (
unsigned i = 0; i < tmatrix.rows(); ++i)
720 const typename TM::value_type*
row = tmatrix.value[i];
721 for (
unsigned j = 0; j < tmatrix.cols(); ++j)
723 if (row[j] != 0 && j > col)
742 template<
typename GT,
typename BT,
unsigned BLOCK_SIZE>
751 tmatrix<GT,
sizeof(GT)*8,
752 (((BLOCK_SIZE *
sizeof(
unsigned)) / (
sizeof(GT))) / (
sizeof(GT) * 8))>
763 const unsigned arr_size = BLOCK_SIZE *
sizeof(unsigned) /
sizeof(GT);
765 BM_ASSERT(
sizeof(tmatrix_.value) == tmatrix_type::n_columns *
766 tmatrix_type::n_rows *
sizeof(GT));
772 vect_bit_transpose<GT, tmatrix_type::n_rows, tmatrix_type::n_columns>
773 ((GT*)tmp_block, arr_size, tmatrix_.value);
788 ::memcpy(tmp_block, garr,
sizeof(GT)*garr_size);
790 const unsigned arr_size = BLOCK_SIZE *
sizeof(unsigned) /
sizeof(GT);
791 BM_ASSERT(
sizeof(tmatrix_.value) == tmatrix_type::n_columns *
792 tmatrix_type::n_rows *
sizeof(GT));
794 vect_bit_transpose<GT, tmatrix_type::n_rows, tmatrix_type::n_columns>
795 ((GT*)tmp_block, arr_size, tmatrix_.value);
805 tmatrix_type::n_rows, tmatrix_type::n_columns>
806 (tmatrix_.value, distance_);
810 tmatrix_type::n_rows, tmatrix_type::n_columns>
811 (distance_, pc_vector_);
814 pc_vector_ + tmatrix_type::n_rows,
836 BM_ASSERT(
sizeof(tmatrix_.value) == tmatrix_type::n_columns *
837 tmatrix_type::n_rows *
sizeof(GT));
840 GT* gap_tmp = (GT*)tmp_block;
843 vect_bit_trestore<GT, tmatrix_type::n_rows, tmatrix_type::n_columns>(tmatrix_.value, gap_tmp);
846 gap_tmp = (GT*)tmp_block;
847 dgap_2_gap<GT>(gap_tmp, gap_buf, gap_head);
854 unsigned distance_[tmatrix_type::n_rows][tmatrix_type::n_rows];
855 unsigned char pc_vector_[tmatrix_type::n_rows];
857 typename tmatrix_type::rstat rstat_vector_[tmatrix_type::n_rows];
865 #pragma warning( pop ) bm::id_t bit_block_count(const bm::word_t *block)
Bitcount for bit block.
void vect_bit_trestore(const T tmatrix[BPC][BPS], T *arr)
Restore bit array from the transposition matrix T - array type (any int) BPC - bit plain count BPS - ...
void transpose(const GT *BMRESTRICT garr, unsigned garr_size, BT *BMRESTRICT tmp_block)
Transpose array of shorts.
Bit-plain splicing of a GAP block.
void bit_iblock_reduce(const unsigned tmatrix[bm::set_block_plain_cnt][bm::set_block_plain_size], const unsigned char *BMRESTRICT pc_vector, const unsigned char *BMRESTRICT pc_vector_end, unsigned tmatrix_out[bm::set_block_plain_cnt][bm::set_block_plain_size])
Matrix reduction based on transformation pc vector.
void bit_iblock_pcv_stat(const unsigned char *BMRESTRICT pc_vector, const unsigned char *BMRESTRICT pc_vector_end, unsigned *BMRESTRICT pc_vector_stat)
Compute number of ibpc codes in pc_vector.
static unsigned get(const T *, unsigned)
const unsigned char ibpc_end
!< plain is close to plain M
const unsigned char ibpc_close
!< plain is equal to plain M
void vect_bit_transpose(const T *arr, unsigned arr_size, T tmatrix[BPC][BPS])
Generic bit-array transposition function T - array type (any int) BPC - bit plain count BPS - bit pla...
void transpose(const GT *BMRESTRICT gap_buf, BT *BMRESTRICT tmp_block)
Transpose GAP block through a temp.
tmatrix< GT, sizeof(GT) *8,(((BLOCK_SIZE *sizeof(unsigned))/(sizeof(GT)))/(sizeof(GT) *8))> tmatrix_type
cryptic calculation of equivalent size for the transpose matrix based on BLOCK_SIZE and sizeof(GT)(16...
void gap_2_bitblock(const GT *BMRESTRICT gap_buf, BT *BMRESTRICT block, unsigned block_size)
Copy GAP block body to bit block with DGap transformation.
const unsigned char ibpc_equiv
!< plain ALL ONE
void compute_distance_matrix()
Row characteristics for transposed matrix.
const unsigned char ibpc_all_zero
!< plain uncompressed
void bit_block_set(bm::word_t *BMRESTRICT dst, bm::word_t value)
Bitblock memset operation.
static T get(const T tmatrix[BPC][BPS], unsigned i, unsigned j)
const unsigned char ibpc_uncompr
void trestore(GT gap_head, GT *BMRESTRICT gap_buf, BT *BMRESTRICT tmp_block)
Restore GAP block from the transposed matrix.
bm::set_representation best_representation(unsigned bit_count, unsigned total_possible_bitcount, unsigned gap_count, unsigned block_size)
Choose best representation for a bit-block.
#define BM_INCWORD_BITCOUNT(cnt, w)
T * row(unsigned row_idx)
void tmatrix_reduce(TMatrix &tmatrix, const unsigned char *pc_vector, const unsigned effective_cols)
Transposed Matrix reduction based on transformation pc vector.
void tmatrix_restore(TMatrix &tmatrix, const unsigned char *pc_vector, const unsigned effective_cols)
Transposed Matrix restore based on transformation pc vector.
void bit_iblock_make_pcv(const unsigned distance[BPC][BPC], unsigned char *pc_vector)
!< ibpc limiter
unsigned find_effective_columns(const TM &tmatrix)
Compute t-matrix rows statistics used for compression.
const unsigned set_block_plain_cnt
const unsigned char ibpc_all_one
!< plain ALL ZERO
const unsigned set_block_plain_size
Mini-matrix for bit transposition purposes.
bm::set_representation best_rep
set_representation
set representation variants
void tmatrix_distance(const T tmatrix[BPC][BPS], unsigned distance[BPC][BPC])
Compute pairwise Row x Row Humming distances on plains(rows) of the transposed bit block...
const T * row(unsigned row_idx) const
T BM_VECT_ALIGN value [ROWS][COLS] BM_VECT_ALIGN_ATTR