BitMagic-C++
bmtrans.h
Go to the documentation of this file.
1 #ifndef BMTRANS__H__INCLUDED__
2 #define BMTRANS__H__INCLUDED__
3 /*
4 Copyright(c) 2002-2017 Anatoliy Kuznetsov(anatoliy_kuznetsov at yahoo.com)
5 
6 Licensed under the Apache License, Version 2.0 (the "License");
7 you may not use this file except in compliance with the License.
8 You may obtain a copy of the License at
9 
10  http://www.apache.org/licenses/LICENSE-2.0
11 
12 Unless required by applicable law or agreed to in writing, software
13 distributed under the License is distributed on an "AS IS" BASIS,
14 WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
15 See the License for the specific language governing permissions and
16 limitations under the License.
17 
18 For more information please visit: http://bitmagic.io
19 */
20 
21 /*! \file bmtrans.h
22  \brief Utilities for bit transposition (internal) (experimental!)
23 */
24 
25 #ifdef _MSC_VER
26 #pragma warning( push )
27 #pragma warning( disable : 4311 4312 4127)
28 #endif
29 
30 #include "bmdef.h"
31 
32 namespace bm
33 {
34 
35 /**
36  Mini-matrix for bit transposition purposes
37  @internal
38 */
39 template<typename T, unsigned ROWS, unsigned COLS>
40 struct tmatrix
41 {
42  typedef T value_type;
43 
44  T BM_VECT_ALIGN value[ROWS][COLS] BM_VECT_ALIGN_ATTR;
45 
46  enum params
47  {
48  n_rows = ROWS,
49  n_columns = COLS
50  };
51 
52 
53  /// Row characteristics for transposed matrix
54  struct rstat
55  {
56  unsigned bit_count;
57  unsigned gap_count;
59  };
60 
61  static unsigned rows() { return ROWS; }
62  static unsigned cols() { return COLS; }
63 
64  const T* row(unsigned row_idx) const
65  {
66  BM_ASSERT(row_idx < ROWS);
67  return value[row_idx];
68  }
69  T* row(unsigned row_idx)
70  {
71  BM_ASSERT(row_idx < ROWS);
72  return value[row_idx];
73  }
74 };
75 
76 
77 /*!
78  Bit array grabber - template specitialization for various basic types
79  @internal
80 */
81 template<typename T, unsigned BPC>
83 {
84  static
85  unsigned get(const T*, unsigned)
86  {
87  BM_ASSERT(0); return 0;
88  }
89 };
90 
91 template<>
92 struct bit_grabber<unsigned, 32>
93 {
94  static
95  unsigned get(const unsigned* arr, unsigned j)
96  {
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);
129  }
130 };
131 
132 template<>
133 struct bit_grabber<unsigned short, 16>
134 {
135  static
136  unsigned get(const unsigned short* arr, unsigned j)
137  {
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);
154  }
155 };
156 
157 
158 template<>
159 struct bit_grabber<unsigned char, 8>
160 {
161  static
162  unsigned get(const unsigned char* arr, unsigned j)
163  {
164  return unsigned(
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));
173  }
174 };
175 
176 
177 /*!
178  Bit transpose matrix grabber - template specitialization for various basic types
179  @internal
180 */
181 template<typename T, unsigned BPC, unsigned BPS>
183 {
184  static
185  T get(const T tmatrix[BPC][BPS], unsigned i, unsigned j)
186  {
187  T w = 0;
188 
189  // Next code hopes that compiler will completely
190  // eliminate ifs (all conditions are known at compile time)
191  // ( typically C++ compilers are smart to do that)
192 
193  // 8-bit (minimum)
194  w |=
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);
203 
204  // 16-bit
205  if (BPC > 8)
206  {
207  w |=
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);
216  }
217 
218  // 32-bit
219  if (BPC > 16)
220  {
221  w |=
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);
238  }
239  return w;
240  }
241 };
242 
243 
244 
245 /**
246  Generic bit-array transposition function
247  T - array type (any int)
248  BPC - bit plain count
249  BPS - bit plain size
250 
251  \param arr - source array start
252  \param arr_size - source array size
253  \param tmatrix - destination bit matrix
254 
255 */
256 template<typename T, unsigned BPC, unsigned BPS>
257 void vect_bit_transpose(const T* arr,
258  unsigned arr_size,
259  T tmatrix[BPC][BPS])
260 {
261  BM_ASSERT(sizeof(T)*8 == BPC);
262 
263  unsigned col = 0;
264  for (unsigned i = 0; i < arr_size;
265  i+=BPC, arr+=BPC,
266  ++col)
267  {
268  for (unsigned j = 0; j < BPC; ++j)
269  {
270  unsigned w =
272  T* row = tmatrix[j];
273  row[col] = (T)w;
274  } // for j
275  } // for i
276 }
277 
278 
279 /**
280  Restore bit array from the transposition matrix
281  T - array type (any int)
282  BPC - bit plain count
283  BPS - bit plain size
284 
285  \param arr - dest array
286  \param tmatrix - source bit-slice matrix
287 
288 */
289 template<typename T, unsigned BPC, unsigned BPS>
290 void vect_bit_trestore(const T tmatrix[BPC][BPS],
291  T* arr)
292 {
293  unsigned col = 0;
294  for (unsigned i = 0; i < BPS; ++i)
295  {
296  for (unsigned j = 0; j < BPC; ++j, ++col)
297  {
298  arr[col] =
300  } // for j
301  } // for i
302 }
303 
304 
305 
306 /*!
307  \brief Compute pairwise Row x Row Humming distances on plains(rows) of
308  the transposed bit block
309  \param tmatrix - bit-block transposition matrix (bit-plains)
310  \param distance - pairwise NxN Humming distance matrix (diagonal is popcnt)
311 
312  @ingroup bitfunc
313 */
314 template<typename T, unsigned BPC, unsigned BPS>
315 void tmatrix_distance(const T tmatrix[BPC][BPS],
316  unsigned distance[BPC][BPC])
317 {
318  for (unsigned i = 0; i < BPC; ++i)
319  {
320  const T* r1 = tmatrix[i];
321 // const T* r1_end;// = r1 + BPS;
322  distance[i][i] =
324 
325  for (unsigned j = i + 1; j < BPC; ++j)
326  {
327  r1 = tmatrix[i];
328  //r1_end = r1 + BPS;
329  unsigned count = 0;
330 
331  {
332  const T* r2 = tmatrix[i];
333  const T* r2_end = r2 + BPS;
334  const bm::word_t* r3 = (bm::word_t*)(tmatrix[j]);
335  do {
336  BM_INCWORD_BITCOUNT(count, r2[0] ^ r3[0]);
337  BM_INCWORD_BITCOUNT(count, r2[1] ^ r3[1]);
338  BM_INCWORD_BITCOUNT(count, r2[2] ^ r3[2]);
339  BM_INCWORD_BITCOUNT(count, r2[3] ^ r3[3]);
340  r2 += 4;
341  r3 += 4;
342  } while (r2 < r2_end);
343  }
344  distance[i][j] = count;
345  } // for j
346  } // for i
347 }
348 
349 
350 
351 const unsigned char ibpc_uncompr = 0; ///!< plain uncompressed
352 const unsigned char ibpc_all_zero= 1; ///!< plain ALL ZERO
353 const unsigned char ibpc_all_one = 2; ///!< plain ALL ONE
354 const unsigned char ibpc_equiv = 3; ///!< plain is equal to plain M
355 const unsigned char ibpc_close = 4; ///!< plain is close to plain M
356 
357 const unsigned char ibpc_end = 8; ///!< ibpc limiter
358 
359 
360 /*!
361  \brief Make a compression descriptor vector for bit-plains
362 
363  \param distance - pairwise distance matrix
364  \param pc_vector - OUT compression descriptor vector
365  <pre>
366  pc_vector[] format:
367  each element (pc_vector[i]) describes the plain compression:
368  first 3 bits - compression code:
369  0 - plain uncompressed
370  1 - plain is ALL ZERO (000000...)
371  2 - plain is ALL ONE (111111...)
372  3 - plain is equal to another plain J (5 high bits (max 31))
373  4 - plain is close (but not equal) to plain J
374  next 5 bits - number of plain used as a XOR expression
375  ( compression codes: 3,4 )
376  </pre>
377 
378  @ingroup bitfunc
379 */
380 template<typename T, unsigned BPC, unsigned BPS>
382  const unsigned distance[BPC][BPC],
383  unsigned char* pc_vector)
384 {
385  BM_ASSERT(pc_vector);
386 
387  for (unsigned i = 0; i < BPC; ++i)
388  {
389  unsigned char pc = ibpc_uncompr;
390  unsigned row_bitcount = distance[i][i];
391 
392  const unsigned total_possible_max = sizeof(T)*8*BPS;
393  switch (row_bitcount)
394  {
395  case 0:
396  pc_vector[i] = ibpc_all_zero;
397  continue;
398  case total_possible_max:
399  pc_vector[i] = ibpc_all_one;
400  continue;
401  default:
402  break;
403  }
404 
405  // Dense-populated set, leave it as is
406  if (row_bitcount > total_possible_max/2)
407  {
408  pc_vector[i] = ibpc_uncompr;
409  continue;
410  }
411 
412  // scan for the closest neighbor
413  //
414  unsigned rmin = ~0u;
415  unsigned rmin_idx = 0;
416  for (unsigned j = i + 1; j < BPC; ++j)
417  {
418  unsigned d = distance[i][j];
419  if (d < rmin) // new minimum - closest plain
420  {
421  if (d == 0) // plain is complete duplicate of j
422  {
423  pc = (unsigned char)(ibpc_equiv | (j << 3));
424  break;
425  }
426  rmin = d; rmin_idx = j;
427  }
428  } // for j
429 
430  if ((pc == 0) && rmin_idx && (rmin < row_bitcount)) // neighbor found
431  {
432  pc = (unsigned char)(ibpc_close | (rmin_idx << 3));
433  }
434  pc_vector[i] = pc;
435  } // for i
436 }
437 
438 
439 /*!
440  \brief Compute number of ibpc codes in pc_vector
441 */
442 inline
443 void bit_iblock_pcv_stat(const unsigned char* BMRESTRICT pc_vector,
444  const unsigned char* BMRESTRICT pc_vector_end,
445  unsigned* BMRESTRICT pc_vector_stat
446  )
447 {
448  BM_ASSERT(pc_vector_stat);
449  // pc_vector_stat MUST be assigned to 0 before
450  do
451  {
452  unsigned ibpc = *pc_vector & 7;
453  ++(pc_vector_stat[ibpc]);
454  } while (++pc_vector < pc_vector_end);
455 }
456 
457 
458 
459 /**
460  \brief Matrix reduction based on transformation pc vector
461 */
462 inline
465  const unsigned char* BMRESTRICT pc_vector,
466  const unsigned char* BMRESTRICT pc_vector_end,
467  unsigned tmatrix_out[bm::set_block_plain_cnt][bm::set_block_plain_size])
468 {
469  ::memset(tmatrix_out, 0, bm::set_block_plain_cnt * sizeof(*tmatrix_out));
470  unsigned row = 0;
471  do
472  {
473  unsigned ibpc = *pc_vector & 7;
474  unsigned n_row = *pc_vector >> 3;
475 
476  switch(ibpc)
477  {
478  case bm::ibpc_uncompr:
479  {
480  const unsigned* r1 = tmatrix[row];
481  unsigned* r_out = tmatrix_out[row];
482  for (unsigned i = 0; i < bm::set_block_plain_size; ++i)
483  {
484  r_out[i] = r1[i];
485  }
486  }
487  break;
488  case bm::ibpc_all_zero:
489  break;
490  case bm::ibpc_all_one:
491  break;
492  case bm::ibpc_equiv:
493  break;
494  case bm::ibpc_close:
495  {
496  const unsigned* r1 = tmatrix[row];
497  const unsigned* r2 = tmatrix[n_row];
498  unsigned* r_out = tmatrix_out[row];
499  for (unsigned i = 0; i < bm::set_block_plain_size; ++i)
500  {
501  r_out[i] = r1[i] ^ r2[i];
502  } // for
503  }
504  break;
505  default:
506  BM_ASSERT(0);
507  break;
508  } // switch
509  ++row;
510  } while (++pc_vector < pc_vector_end);
511 
512 }
513 
514 /**
515  \brief Transposed Matrix reduction based on transformation pc vector
516 */
517 template<class TMatrix>
518 void tmatrix_reduce(TMatrix& tmatrix,
519  const unsigned char* pc_vector,
520  const unsigned effective_cols)
521 {
522  BM_ASSERT(pc_vector);
523 
524  typedef typename TMatrix::value_type value_type;
525 
526  const unsigned char* pc_vector_end = pc_vector + tmatrix.rows();
527  unsigned row = 0;
528  unsigned cols = effective_cols ? effective_cols : tmatrix.cols();
529 
530  do
531  {
532  unsigned ibpc = *pc_vector & 7;
533  switch(ibpc)
534  {
535  case bm::ibpc_uncompr:
536  case bm::ibpc_all_zero:
537  case bm::ibpc_all_one:
538  case bm::ibpc_equiv:
539  break;
540  case bm::ibpc_close:
541  {
542  unsigned n_row = *pc_vector >> 3;
543  BM_ASSERT(n_row > row);
544 
545  value_type* r1 = tmatrix.row(row);
546  const value_type* r2 = tmatrix.row(n_row);
547  for (unsigned i = 0; i < cols; ++i)
548  {
549  r1[i] ^= r2[i];
550  } // for
551  }
552  break;
553  default:
554  BM_ASSERT(0);
555  break;
556  } // switch
557  ++row;
558  } while (++pc_vector < pc_vector_end);
559 }
560 
561 /**
562  \brief Transposed Matrix restore based on transformation pc vector
563 */
564 template<class TMatrix>
565 void tmatrix_restore(TMatrix& tmatrix,
566  const unsigned char* pc_vector,
567  const unsigned effective_cols)
568 {
569  BM_ASSERT(pc_vector);
570 
571  typedef typename TMatrix::value_type value_type;
572 
573  unsigned cols = effective_cols ? effective_cols : tmatrix.cols();
574  for (unsigned row = tmatrix.rows()-1u; 1; --row)
575  {
576  unsigned ibpc = pc_vector[row] & 7u;
577  unsigned n_row = pc_vector[row] >> 3u;
578 
579  value_type* r1 = tmatrix.row(unsigned(row));
580 
581  switch(ibpc)
582  {
583  case bm::ibpc_uncompr:
584  break;
585  case bm::ibpc_all_zero:
586  for (unsigned i = 0; i < cols; ++i)
587  r1[i] = 0;
588  break;
589  case bm::ibpc_all_one:
590  for (unsigned i = 0; i < cols; ++i)
591  r1[i] = (value_type)(~0);
592  break;
593  case bm::ibpc_equiv:
594  {
595  BM_ASSERT(n_row > row);
596  const value_type* r2 = tmatrix.row(n_row);
597  for (unsigned i = 0; i < cols; ++i)
598  r1[i] = r2[i];
599  }
600  break;
601  case bm::ibpc_close:
602  {
603  BM_ASSERT(n_row > row);
604  const value_type* r2 = tmatrix.row(n_row);
605  for (unsigned i = 0; i < cols; ++i)
606  r1[i] ^= r2[i];
607  }
608  break;
609  default:
610  BM_ASSERT(0);
611  break;
612  } // switch
613 
614  if (row == 0)
615  break;
616  } // for
617 
618 }
619 
620 
621 
622 /**
623  \brief Copy GAP block body to bit block with DGap transformation
624  \internal
625 */
626 template<typename GT, typename BT>
627 void gap_2_bitblock(const GT* BMRESTRICT gap_buf,
628  BT* BMRESTRICT block,
629  unsigned block_size)
630 {
631  GT* dgap_buf = (GT*) block;
632  BT* block_end = block + block_size;
633 
634  GT* dgap_end = gap_2_dgap<GT>(gap_buf, dgap_buf, false);
635  GT* block_end2 = (GT*) block_end;
636 
637  // zero the tail memory
638  for ( ;dgap_end < block_end2; ++dgap_end)
639  {
640  *dgap_end = 0;
641  }
642 }
643 
644 /**
645  @brief Compute t-matrix rows statistics used for compression
646 
647  @param tmatrix - transposed matrix
648  @param pc_vector - row content vector
649  @param rstat - output row vector
650  @param effective_cols - effective columns
651 
652  @internal
653 */
654 #if 0
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)
660 {
661  BM_ASSERT(rstat);
662  typedef typename TMatrix::value_type value_type;
663 
664  unsigned cols = effective_cols ? effective_cols : tmatrix.cols();
665  //unsigned cols = tmatrix.cols();
666  unsigned rows = tmatrix.rows();
667 
668  for (unsigned i = 0; i < rows; ++i)
669  {
670  unsigned ibpc = pc_vector[i] & 7;
671  switch(ibpc)
672  {
673  case bm::ibpc_all_zero:
674  case bm::ibpc_all_one:
675  case bm::ibpc_equiv:
676  rstat[i].bit_count = rstat[i].gap_count = 0;
677  rstat[i].best_rep = bm::set_bitset;
678  break;
679  case bm::ibpc_uncompr:
680  case bm::ibpc_close:
681  {
682  const value_type* r1 = tmatrix.row(i);
683  const value_type* r1_end = r1 + cols;
684  // TODO: find how to deal with the potentially incorrect type-cast
685  bm::bit_count_change32((bm::word_t*)r1, (bm::word_t*)r1_end,
686  &rstat[i].bit_count, &rstat[i].gap_count);
687 
688  const unsigned bitset_size = unsigned(sizeof(value_type) * cols);
689  const unsigned total_possible_max_bits = unsigned(sizeof(value_type)*8*cols);
690 
691  rstat[i].best_rep =
692  bm::best_representation(rstat[i].bit_count,
693  total_possible_max_bits,
694  rstat[i].gap_count,
695  bitset_size);
696 
697  }
698  break;
699  default:
700  BM_ASSERT(0);
701  break;
702  } // switch
703 
704  } // for
705 }
706 #endif
707 
708 
709 /**
710  \brief Compute effective right column border of the t-matrix
711  \internal
712 */
713 template<typename TM>
714 unsigned find_effective_columns(const TM& tmatrix)
715 {
716  // TODO: need optimization in order not to scan the whole space
717  unsigned col = 1;
718  for (unsigned i = 0; i < tmatrix.rows(); ++i)
719  {
720  const typename TM::value_type* row = tmatrix.value[i];
721  for (unsigned j = 0; j < tmatrix.cols(); ++j)
722  {
723  if (row[j] != 0 && j > col)
724  {
725  col = j;
726  }
727  }
728  }
729  return col;
730 }
731 
732 
733 /**
734  \brief Bit-plain splicing of a GAP block
735 
736  GT - gap word type
737  BT - block word type
738  BLOCK_SIZE - bit block size in words (works as a transposition basis)
739 
740  @internal
741 */
742 template<typename GT, typename BT, unsigned BLOCK_SIZE>
744 {
745 public:
746  /// cryptic calculation of equivalent size for the transpose matrix
747  /// based on BLOCK_SIZE and sizeof(GT)(16)
748  ///
749  /// matrix[size_of_gap*8][(Size_block_in_bytes / size_of_gap) / number_of_planes)]
750  typedef
751  tmatrix<GT, sizeof(GT)*8,
752  (((BLOCK_SIZE * sizeof(unsigned)) / (sizeof(GT))) / (sizeof(GT) * 8))>
754 
755  gap_transpose_engine() : eff_cols_(0)
756  {}
757 
758  /// Transpose GAP block through a temp. block of aligned(!) memory
759  ///
760  void transpose(const GT* BMRESTRICT gap_buf,
761  BT* BMRESTRICT tmp_block)
762  {
763  const unsigned arr_size = BLOCK_SIZE * sizeof(unsigned) / sizeof(GT);
764 
765  BM_ASSERT(sizeof(tmatrix_.value) == tmatrix_type::n_columns *
766  tmatrix_type::n_rows * sizeof(GT));
767 
768  // load all GAP as D-GAP(but not head word) into aligned bit-block
769  gap_2_bitblock(gap_buf, tmp_block, BLOCK_SIZE);
770 
771  // transpose
772  vect_bit_transpose<GT, tmatrix_type::n_rows, tmatrix_type::n_columns>
773  ((GT*)tmp_block, arr_size, tmatrix_.value);
774 
775  // calculate number of non-zero columns
776  eff_cols_ = find_effective_columns(tmatrix_);
777  }
778 
779  /// Transpose array of shorts
780  ///
781  void transpose(const GT* BMRESTRICT garr,
782  unsigned garr_size,
783  BT* BMRESTRICT tmp_block)
784  {
785  BM_ASSERT(garr_size);
786 
787  bit_block_set(tmp_block, 0);
788  ::memcpy(tmp_block, garr, sizeof(GT)*garr_size);
789 
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));
793  // transpose
794  vect_bit_transpose<GT, tmatrix_type::n_rows, tmatrix_type::n_columns>
795  ((GT*)tmp_block, arr_size, tmatrix_.value);
796 
797  // calculate number of non-zero columns
798  eff_cols_ = find_effective_columns(tmatrix_);
799 
800  }
801 
803  {
805  tmatrix_type::n_rows, tmatrix_type::n_columns>
806  (tmatrix_.value, distance_);
807 
808  // make compression descriptor vector and statistics vector
809  bit_iblock_make_pcv<unsigned char,
810  tmatrix_type::n_rows, tmatrix_type::n_columns>
811  (distance_, pc_vector_);
812 
813  bit_iblock_pcv_stat(pc_vector_,
814  pc_vector_ + tmatrix_type::n_rows,
815  pc_vector_stat_);
816  }
817 
818  void reduce()
819  {
820  tmatrix_reduce(tmatrix_, pc_vector_, eff_cols_);
821  //compute_tmatrix_rstat(tmatrix_, pc_vector_, rstat_vector_, eff_cols_);
822  }
823 
824  void restore()
825  {
826  tmatrix_restore(tmatrix_, pc_vector_, eff_cols_);
827  }
828 
829 
830  /// Restore GAP block from the transposed matrix
831  ///
832  void trestore(GT gap_head,
833  GT* BMRESTRICT gap_buf,
834  BT* BMRESTRICT tmp_block)
835  {
836  BM_ASSERT(sizeof(tmatrix_.value) == tmatrix_type::n_columns *
837  tmatrix_type::n_rows * sizeof(GT));
838 
839  // restore into a temp buffer
840  GT* gap_tmp = (GT*)tmp_block;
841  //*gap_tmp++ = gap_head;
842 
843  vect_bit_trestore<GT, tmatrix_type::n_rows, tmatrix_type::n_columns>(tmatrix_.value, gap_tmp);
844 
845  // D-Gap to GAP block recalculation
846  gap_tmp = (GT*)tmp_block;
847  dgap_2_gap<GT>(gap_tmp, gap_buf, gap_head);
848  }
849 
850 public:
851 // GT gap_head_;
853  unsigned eff_cols_;
854  unsigned distance_[tmatrix_type::n_rows][tmatrix_type::n_rows];
855  unsigned char pc_vector_[tmatrix_type::n_rows];
856  unsigned pc_vector_stat_[bm::ibpc_end];
857  typename tmatrix_type::rstat rstat_vector_[tmatrix_type::n_rows];
858 };
859 
860 
861 } // namespace bm
862 
863 
864 #ifdef _MSC_VER
865 #pragma warning( pop )
866 #endif
867 
868 
869 #endif
bm::id_t bit_block_count(const bm::word_t *block)
Bitcount for bit block.
Definition: bmfunc.h:3972
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 - ...
Definition: bmtrans.h:290
#define BM_VECT_ALIGN
Definition: bmdef.h:346
unsigned gap_count
Definition: bmtrans.h:57
static unsigned cols()
Definition: bmtrans.h:62
void transpose(const GT *BMRESTRICT garr, unsigned garr_size, BT *BMRESTRICT tmp_block)
Transpose array of shorts.
Definition: bmtrans.h:781
Bit-plain splicing of a GAP block.
Definition: bmtrans.h:743
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.
Definition: bmtrans.h:463
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.
Definition: bmtrans.h:443
static unsigned get(const T *, unsigned)
Definition: bmtrans.h:85
Simple bitset.
Definition: bmconst.h:204
const unsigned char ibpc_end
!< plain is close to plain M
Definition: bmtrans.h:357
Definition: bm.h:76
static unsigned rows()
Definition: bmtrans.h:61
const unsigned char ibpc_close
!< plain is equal to plain M
Definition: bmtrans.h:355
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...
Definition: bmtrans.h:257
void transpose(const GT *BMRESTRICT gap_buf, BT *BMRESTRICT tmp_block)
Transpose GAP block through a temp.
Definition: bmtrans.h:760
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...
Definition: bmtrans.h:753
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.
Definition: bmtrans.h:627
unsigned int word_t
Definition: bmconst.h:38
const unsigned char ibpc_equiv
!< plain ALL ONE
Definition: bmtrans.h:354
void compute_distance_matrix()
Definition: bmtrans.h:802
Row characteristics for transposed matrix.
Definition: bmtrans.h:54
const unsigned char ibpc_all_zero
!< plain uncompressed
Definition: bmtrans.h:352
void bit_block_set(bm::word_t *BMRESTRICT dst, bm::word_t value)
Bitblock memset operation.
Definition: bmfunc.h:3492
static T get(const T tmatrix[BPC][BPS], unsigned i, unsigned j)
Definition: bmtrans.h:185
const unsigned char ibpc_uncompr
Definition: bmtrans.h:351
void trestore(GT gap_head, GT *BMRESTRICT gap_buf, BT *BMRESTRICT tmp_block)
Restore GAP block from the transposed matrix.
Definition: bmtrans.h:832
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.
Definition: bmfunc.h:6941
#define BM_INCWORD_BITCOUNT(cnt, w)
Definition: bmdef.h:373
T * row(unsigned row_idx)
Definition: bmtrans.h:69
tmatrix_type tmatrix_
Definition: bmtrans.h:852
unsigned bit_count
Definition: bmtrans.h:56
T value_type
Definition: bmtrans.h:42
void tmatrix_reduce(TMatrix &tmatrix, const unsigned char *pc_vector, const unsigned effective_cols)
Transposed Matrix reduction based on transformation pc vector.
Definition: bmtrans.h:518
Definitions(internal)
void tmatrix_restore(TMatrix &tmatrix, const unsigned char *pc_vector, const unsigned effective_cols)
Transposed Matrix restore based on transformation pc vector.
Definition: bmtrans.h:565
void bit_iblock_make_pcv(const unsigned distance[BPC][BPC], unsigned char *pc_vector)
!< ibpc limiter
Definition: bmtrans.h:381
unsigned find_effective_columns(const TM &tmatrix)
Compute t-matrix rows statistics used for compression.
Definition: bmtrans.h:714
const unsigned set_block_plain_cnt
Definition: bmconst.h:63
const unsigned char ibpc_all_one
!< plain ALL ZERO
Definition: bmtrans.h:353
#define BM_ASSERT
Definition: bmdef.h:117
const unsigned set_block_plain_size
Definition: bmconst.h:62
Mini-matrix for bit transposition purposes.
Definition: bmtrans.h:40
bm::set_representation best_rep
Definition: bmtrans.h:58
set_representation
set representation variants
Definition: bmconst.h:202
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...
Definition: bmtrans.h:315
const T * row(unsigned row_idx) const
Definition: bmtrans.h:64
T BM_VECT_ALIGN value [ROWS][COLS] BM_VECT_ALIGN_ATTR
Definition: bmtrans.h:44
#define BMRESTRICT
Definition: bmdef.h:180