BitMagic-C++
bmtrans.h
Go to the documentation of this file.
1#ifndef BMTRANS__H__INCLUDED__
2#define BMTRANS__H__INCLUDED__
3/*
4Copyright(c) 2002-2017 Anatoliy Kuznetsov(anatoliy_kuznetsov at yahoo.com)
5
6Licensed under the Apache License, Version 2.0 (the "License");
7you may not use this file except in compliance with the License.
8You may obtain a copy of the License at
9
10 http://www.apache.org/licenses/LICENSE-2.0
11
12Unless required by applicable law or agreed to in writing, software
13distributed under the License is distributed on an "AS IS" BASIS,
14WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
15See the License for the specific language governing permissions and
16limitations under the License.
17
18For 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
32namespace bm
33{
34
35/**
36 Mini-matrix for bit transposition purposes
37 @internal
38*/
39template<typename T, unsigned ROWS, unsigned COLS>
40struct 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*/
81template<typename T, unsigned BPC>
83{
84 static
85 unsigned get(const T*, unsigned)
86 {
87 BM_ASSERT(0); return 0;
88 }
89};
90
91template<>
92struct 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
132template<>
133struct 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
158template<>
159struct 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*/
181template<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*/
256template<typename T, unsigned BPC, unsigned BPS>
257void 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*/
289template<typename T, unsigned BPC, unsigned BPS>
290void 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*/
314template<typename T, unsigned BPC, unsigned BPS>
315void 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
351const unsigned char ibpc_uncompr = 0; ///!< plain uncompressed
352const unsigned char ibpc_all_zero= 1; ///!< plain ALL ZERO
353const unsigned char ibpc_all_one = 2; ///!< plain ALL ONE
354const unsigned char ibpc_equiv = 3; ///!< plain is equal to plain M
355const unsigned char ibpc_close = 4; ///!< plain is close to plain M
356
357const 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*/
380template<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*/
442inline
443void 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*/
462inline
465 const unsigned char* BMRESTRICT pc_vector,
466 const unsigned char* BMRESTRICT pc_vector_end,
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;
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*/
517template<class TMatrix>
518void 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:
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*/
564template<class 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;
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*/
626template<typename GT, typename BT>
627void 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#if 0
645/**
646 @brief Compute t-matrix rows statistics used for compression
647
648 @param tmatrix - transposed matrix
649 @param pc_vector - row content vector
650 @param rstat - output row vector
651 @param effective_cols - effective columns
652
653 @internal
654*/
655template<class TMatrix>
656void 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 {
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*/
713template<typename TM>
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*/
742template<typename GT, typename BT, unsigned BLOCK_SIZE>
744{
745public:
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
752 static_cast<unsigned>(((BLOCK_SIZE * sizeof(unsigned)) / (sizeof(GT)))
753 / (sizeof(GT) * 8))>
755
758
759 /// Transpose GAP block through a temp. block of aligned(!) memory
760 ///
761 void transpose(const GT* BMRESTRICT gap_buf,
762 BT* BMRESTRICT tmp_block)
763 {
764 const unsigned arr_size = BLOCK_SIZE * sizeof(unsigned) / sizeof(GT);
765
766 BM_ASSERT(sizeof(tmatrix_.value) == tmatrix_type::n_columns *
767 tmatrix_type::n_rows * sizeof(GT));
768
769 // load all GAP as D-GAP(but not head word) into aligned bit-block
770 gap_2_bitblock(gap_buf, tmp_block, BLOCK_SIZE);
771
772 // transpose
774 ((GT*)tmp_block, arr_size, tmatrix_.value);
775
776 // calculate number of non-zero columns
778 }
779
780 /// Transpose array of shorts
781 ///
782 void transpose(const GT* BMRESTRICT garr,
783 unsigned garr_size,
784 BT* BMRESTRICT tmp_block)
785 {
786 BM_ASSERT(garr_size);
787
788 bit_block_set(tmp_block, 0);
789 ::memcpy(tmp_block, garr, sizeof(GT)*garr_size);
790
791 const unsigned arr_size = BLOCK_SIZE * sizeof(unsigned) / sizeof(GT);
792 BM_ASSERT(sizeof(tmatrix_.value) == tmatrix_type::n_columns *
793 tmatrix_type::n_rows * sizeof(GT));
794 // transpose
796 ((GT*)tmp_block, arr_size, tmatrix_.value);
797
798 // calculate number of non-zero columns
800
801 }
802
804 {
807 (tmatrix_.value, distance_);
808
809 // make compression descriptor vector and statistics vector
810 bit_iblock_make_pcv<unsigned char,
813
817 }
818
819 void reduce()
820 {
822 //compute_tmatrix_rstat(tmatrix_, pc_vector_, rstat_vector_, eff_cols_);
823 }
824
829
830
831 /// Restore GAP block from the transposed matrix
832 ///
833 void trestore(GT gap_head,
834 GT* BMRESTRICT gap_buf,
835 BT* BMRESTRICT tmp_block)
836 {
837 BM_ASSERT(sizeof(tmatrix_.value) == tmatrix_type::n_columns *
838 tmatrix_type::n_rows * sizeof(GT));
839
840 // restore into a temp buffer
841 GT* gap_tmp = (GT*)tmp_block;
842 //*gap_tmp++ = gap_head;
843
845
846 // D-Gap to GAP block recalculation
847 gap_tmp = (GT*)tmp_block;
848 dgap_2_gap<GT>(gap_tmp, gap_buf, gap_head);
849 }
850
851public:
852// GT gap_head_;
854 unsigned eff_cols_;
858 typename tmatrix_type::rstat rstat_vector_[tmatrix_type::n_rows];
859};
860
861
862} // namespace bm
863
864
865#ifdef _MSC_VER
866#pragma warning( pop )
867#endif
868
869
870#endif
Definitions(internal)
#define BMRESTRICT
Definition bmdef.h:193
#define BM_ASSERT
Definition bmdef.h:130
#define BM_VECT_ALIGN
Definition bmdef.h:359
Bit-plain splicing of a GAP block.
Definition bmtrans.h:744
void transpose(const GT *BMRESTRICT garr, unsigned garr_size, BT *BMRESTRICT tmp_block)
Transpose array of shorts.
Definition bmtrans.h:782
unsigned pc_vector_stat_[bm::ibpc_end]
Definition bmtrans.h:857
void trestore(GT gap_head, GT *BMRESTRICT gap_buf, BT *BMRESTRICT tmp_block)
Restore GAP block from the transposed matrix.
Definition bmtrans.h:833
unsigned char pc_vector_[tmatrix_type::n_rows]
Definition bmtrans.h:856
tmatrix_type tmatrix_
Definition bmtrans.h:853
void transpose(const GT *BMRESTRICT gap_buf, BT *BMRESTRICT tmp_block)
Transpose GAP block through a temp.
Definition bmtrans.h:761
tmatrix_type::rstat rstat_vector_[tmatrix_type::n_rows]
Definition bmtrans.h:858
unsigned distance_[tmatrix_type::n_rows][tmatrix_type::n_rows]
Definition bmtrans.h:855
bm::id_t bit_block_count(const bm::word_t *block) BMNOEXCEPT
Bitcount for bit block.
Definition bmfunc.h:4379
bm::set_representation best_representation(unsigned bit_count, unsigned total_possible_bitcount, unsigned gap_count, unsigned block_size) BMNOEXCEPT
Choose best representation for a bit-block.
Definition bmfunc.h:7785
#define BM_INCWORD_BITCOUNT(cnt, w)
Definition bmdef.h:386
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
void bit_block_set(bm::word_t *BMRESTRICT dst, bm::word_t value) BMNOEXCEPT
Bitblock memset operation.
Definition bmfunc.h:3841
void bit_iblock_make_pcv(const unsigned distance[BPC][BPC], unsigned char *pc_vector)
!< ibpc limiter
Definition bmtrans.h:381
Definition bm.h:77
unsigned int word_t
Definition bmconst.h:38
T * gap_2_dgap(const T *BMRESTRICT gap_buf, T *BMRESTRICT dgap_buf, bool copy_head=true) BMNOEXCEPT
Convert GAP buffer into D-GAP buffer.
Definition bmfunc.h:2188
const unsigned set_block_plain_cnt
Definition bmconst.h:63
const unsigned set_block_plain_size
Definition bmconst.h:62
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
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
set_representation
set representation variants
Definition bmconst.h:202
@ set_bitset
Simple bitset.
Definition bmconst.h:203
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
unsigned find_effective_columns(const TM &tmatrix)
Compute effective right column border of the t-matrix.
Definition bmtrans.h:714
const unsigned char ibpc_equiv
!< plain ALL ONE
Definition bmtrans.h:354
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 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 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
const unsigned char ibpc_close
!< plain is equal to plain M
Definition bmtrans.h:355
const unsigned char ibpc_all_one
!< plain ALL ZERO
Definition bmtrans.h:353
const unsigned char ibpc_all_zero
!< plain uncompressed
Definition bmtrans.h:352
void dgap_2_gap(const T *BMRESTRICT dgap_buf, T *BMRESTRICT gap_buf, T gap_header=0) BMNOEXCEPT
Convert D-GAP buffer into GAP buffer.
Definition bmfunc.h:2214
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
const unsigned char ibpc_uncompr
Definition bmtrans.h:351
const unsigned char ibpc_end
!< plain is close to plain M
Definition bmtrans.h:357
static unsigned get(const unsigned *arr, unsigned j)
Definition bmtrans.h:95
static unsigned get(const unsigned char *arr, unsigned j)
Definition bmtrans.h:162
static unsigned get(const unsigned short *arr, unsigned j)
Definition bmtrans.h:136
static unsigned get(const T *, unsigned)
Definition bmtrans.h:85
static T get(const T tmatrix[BPC][BPS], unsigned i, unsigned j)
Definition bmtrans.h:185
Row characteristics for transposed matrix.
Definition bmtrans.h:55
unsigned gap_count
Definition bmtrans.h:57
unsigned bit_count
Definition bmtrans.h:56
bm::set_representation best_rep
Definition bmtrans.h:58
Mini-matrix for bit transposition purposes.
Definition bmtrans.h:41
static unsigned cols()
Definition bmtrans.h:62
T * row(unsigned row_idx)
Definition bmtrans.h:69
const T * row(unsigned row_idx) const
Definition bmtrans.h:64
static unsigned rows()
Definition bmtrans.h:61
T BM_VECT_ALIGN value[ROWS][COLS] BM_VECT_ALIGN_ATTR
Definition bmtrans.h:44