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>
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];
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;
480 const unsigned* r1 =
tmatrix[row];
481 unsigned* r_out = tmatrix_out[row];
496 const unsigned* r1 =
tmatrix[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;
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();
576 unsigned ibpc = pc_vector[row] & 7u;
577 unsigned n_row = pc_vector[row] >> 3u;
586 for (
unsigned i = 0; i < cols; ++i)
590 for (
unsigned i = 0; i < cols; ++i)
591 r1[i] = (value_type)(~0);
597 for (
unsigned i = 0; i < cols; ++i)
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;
686 &rstat[i].bit_count, &rstat[i].gap_count);
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>
720 const typename TM::value_type* row =
tmatrix.value[i];
723 if (row[j] != 0 && j > col)
742 template<
typename GT,
typename BT,
unsigned BLOCK_SIZE>
752 (((BLOCK_SIZE *
sizeof(
unsigned)) / (
sizeof(GT))) / (
sizeof(GT) * 8))>
763 const unsigned arr_size = BLOCK_SIZE *
sizeof(unsigned) /
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);
794 vect_bit_transpose<GT, tmatrix_type::n_rows, tmatrix_type::n_columns>
795 ((GT*)tmp_block, arr_size,
tmatrix_.value);
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);
865 #pragma warning( pop )