← Back to branch summary

~ubuntu-branches/ubuntu/trusty/bmagic/trusty

« back to all changes in this revision

Viewing changes to src/bmtrans.h

  • Committer: Bazaar Package Importer
  • Author(s): Roberto C. Sanchez
  • Date: 2010-01-24 14:45:39 UTC
  • mfrom: (4.1.6 sid)
  • Revision ID: james.westby@ubuntu.com-20100124144539-4ipk5rt64dpp38hl
Tags: 3.6.3-1
* New upstream release
* debian/patches/config.guess.patch: drop obsolete patch
* Add ${misc:Depends} as requested by lintian

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/bmtrans.h
41
41
    
42
42
    T BM_ALIGN16 value[ROWS][COLS] BM_ALIGN16ATTR;
43
43
 
 
44
    enum params
 
45
    {
 
46
        n_rows = ROWS,
 
47
        n_columns = COLS
 
48
    };
 
49
 
 
50
 
 
51
    /// Row characteristics for transposed matrix
 
52
    struct rstat
 
53
    {
 
54
        unsigned               bit_count;
 
55
        unsigned               gap_count;
 
56
        bm::set_representation best_rep;
 
57
    };
 
58
 
44
59
    static unsigned rows() { return ROWS; }
45
60
    static unsigned cols() { return COLS; }
46
61
 
47
62
    const T* row(unsigned row_idx) const { return value[row_idx]; }
 
63
          T* row(unsigned row_idx)       { return value[row_idx]; }
48
64
};
49
65
 
50
66
 
359
375
                } while (r2 < r2_end);
360
376
            }
361
377
            distance[i][j] = count;
362
 
/*
363
 
            distance[i][j] = 
364
 
                bit_block_xor_count(
365
 
                    (bm::word_t*)r1, (bm::word_t*)r1_end, (bm::word_t*)(tmatrix[j]));
366
 
            if (count != distance[i][j])
367
 
                printf("BShit!");
368
 
*/
369
378
        } // for j
370
379
    } // for i
371
380
}
413
422
        unsigned char pc = ibpc_uncompr; 
414
423
        unsigned row_bitcount = distance[i][i];
415
424
        
 
425
        const unsigned total_possible_max = sizeof(T)*8*BPS;
416
426
        switch (row_bitcount)
417
427
        {
418
428
        case 0:
419
429
            pc_vector[i] = ibpc_all_zero; 
420
430
            continue;
421
 
        case sizeof(T)*8*BPS:
 
431
        case total_possible_max:
422
432
            pc_vector[i] = ibpc_all_one; 
423
433
            continue;
424
434
        }
425
435
        
 
436
        // Dense-populated set, leave it as is
 
437
        if (row_bitcount >  total_possible_max/2)
 
438
        {
 
439
            pc_vector[i] = ibpc_uncompr;
 
440
            continue;
 
441
        }
 
442
        
426
443
        // scan for the closest neighbor
427
444
        //
428
445
        unsigned rmin = ~0;
470
487
 
471
488
 
472
489
 
473
 
 
474
490
/**
475
491
    \brief Matrix reduction based on transformation pc vector
476
492
*/
487
503
    do 
488
504
    {
489
505
        unsigned ibpc = *pc_vector & 7;
490
 
        unsigned n_row = (pc_vector[row] >> 3);
 
506
        unsigned n_row = *pc_vector >> 3;
491
507
        
492
508
        switch(ibpc)
493
509
        {
528
544
}
529
545
 
530
546
/**
 
547
    \brief Transposed Matrix reduction based on transformation pc vector
 
548
*/
 
549
template<class TMatrix>
 
550
void tmatrix_reduce(TMatrix& tmatrix, 
 
551
                    const unsigned char* pc_vector,
 
552
                    const unsigned       effective_cols)
 
553
{
 
554
    BM_ASSERT(pc_vector);
 
555
 
 
556
    typedef typename TMatrix::value_type value_type;
 
557
 
 
558
    const unsigned char* pc_vector_end = pc_vector + tmatrix.rows();
 
559
    unsigned row = 0;
 
560
    unsigned cols = effective_cols ? effective_cols : tmatrix.cols();
 
561
 
 
562
    do
 
563
    {
 
564
        unsigned ibpc = *pc_vector & 7;        
 
565
        switch(ibpc)
 
566
        {
 
567
        case bm::ibpc_uncompr:
 
568
        case bm::ibpc_all_zero:
 
569
        case bm::ibpc_all_one:
 
570
        case bm::ibpc_equiv:
 
571
            break;
 
572
        case bm::ibpc_close:
 
573
            {
 
574
            unsigned n_row = *pc_vector >> 3;
 
575
            BM_ASSERT(n_row > row);
 
576
 
 
577
            value_type* r1 = tmatrix.row(row);
 
578
            const value_type* r2 = tmatrix.row(n_row);
 
579
            for (unsigned i = 0; i < cols; ++i)
 
580
            {
 
581
                r1[i] ^= r2[i];
 
582
            } // for
 
583
            }
 
584
            break;
 
585
        default:
 
586
            BM_ASSERT(0);
 
587
            break;
 
588
        } // switch
 
589
        ++row;
 
590
    } while (++pc_vector < pc_vector_end);
 
591
}
 
592
 
 
593
/**
 
594
    \brief Transposed Matrix restore based on transformation pc vector
 
595
*/
 
596
template<class TMatrix>
 
597
void tmatrix_restore(TMatrix& tmatrix, 
 
598
                     const unsigned char* pc_vector,
 
599
                     const unsigned effective_cols)
 
600
{
 
601
    BM_ASSERT(pc_vector);
 
602
 
 
603
    typedef typename TMatrix::value_type value_type;
 
604
 
 
605
    unsigned cols = effective_cols ? effective_cols : tmatrix.cols();
 
606
    for (int row = tmatrix.rows()-1; row >= 0; --row)
 
607
    {
 
608
        unsigned ibpc = pc_vector[row] & 7;  
 
609
        int n_row = pc_vector[row] >> 3;
 
610
 
 
611
        value_type* r1 = tmatrix.row(row);
 
612
 
 
613
        switch(ibpc)
 
614
        {
 
615
        case bm::ibpc_uncompr:
 
616
            break;
 
617
        case bm::ibpc_all_zero:
 
618
            for (unsigned i = 0; i < cols; ++i)
 
619
                r1[i] = 0;
 
620
             break;
 
621
        case bm::ibpc_all_one:
 
622
            for (unsigned i = 0; i < cols; ++i)
 
623
                r1[i] = ~0;
 
624
            break;
 
625
        case bm::ibpc_equiv:
 
626
            {
 
627
            BM_ASSERT(n_row > row);
 
628
            const value_type* r2 = tmatrix.row(n_row);
 
629
            for (unsigned i = 0; i < cols; ++i)
 
630
                r1[i] = r2[i];
 
631
            }
 
632
            break;
 
633
        case bm::ibpc_close:
 
634
            {      
 
635
            BM_ASSERT(n_row > row);
 
636
            const value_type* r2 = tmatrix.row(n_row);
 
637
            for (unsigned i = 0; i < cols; ++i)
 
638
                r1[i] ^= r2[i];
 
639
            }
 
640
            break;
 
641
        default:
 
642
            BM_ASSERT(0);
 
643
            break;
 
644
        } // switch
 
645
    }  // for
 
646
 
 
647
}
 
648
 
 
649
 
 
650
 
 
651
/**
531
652
    \brief Copy GAP block body to bit block with DGap transformation 
532
653
    \internal
533
654
*/
550
671
}
551
672
 
552
673
/**
 
674
    @brief Compute t-matrix rows statistics used for compression
 
675
 
 
676
    @param tmatrix - transposed matrix
 
677
    @param pc_vector - row content vector
 
678
    @param rstat - output row vector
 
679
 
 
680
    @internal
 
681
*/
 
682
template<class TMatrix>
 
683
void compute_tmatrix_rstat(const TMatrix& tmatrix, 
 
684
                           const unsigned char* pc_vector,
 
685
                           typename TMatrix::rstat* rstat,
 
686
                           unsigned effective_cols)
 
687
{
 
688
    BM_ASSERT(rstat);
 
689
    typedef typename TMatrix::value_type value_type;
 
690
 
 
691
    unsigned cols = effective_cols ? effective_cols : tmatrix.cols();
 
692
    //unsigned cols = tmatrix.cols();
 
693
    unsigned rows = tmatrix.rows();
 
694
 
 
695
    for (unsigned i = 0; i < rows; ++i)
 
696
    {
 
697
        unsigned ibpc = pc_vector[i] & 7;        
 
698
        switch(ibpc)
 
699
        {
 
700
        case bm::ibpc_all_zero:
 
701
        case bm::ibpc_all_one:
 
702
        case bm::ibpc_equiv:
 
703
            rstat[i].bit_count = rstat[i].gap_count = 0;
 
704
            rstat[i].best_rep = bm::set_bitset;
 
705
            break;
 
706
        case bm::ibpc_uncompr:
 
707
        case bm::ibpc_close:
 
708
            {
 
709
            const value_type* r1 = tmatrix.row(i);
 
710
            const value_type* r1_end = r1 + cols;
 
711
            // TODO: find how to deal with the potentially incorrect type-cast
 
712
            bm::bit_count_change32((bm::word_t*)r1, (bm::word_t*)r1_end, 
 
713
                                    &rstat[i].bit_count, &rstat[i].gap_count);
 
714
 
 
715
            const unsigned bitset_size = sizeof(value_type) * cols;
 
716
            const unsigned total_possible_max_bits = sizeof(value_type)*8*cols;
 
717
 
 
718
            rstat[i].best_rep = 
 
719
                bm::best_representation(rstat[i].bit_count,
 
720
                                        total_possible_max_bits,
 
721
                                        rstat[i].gap_count,
 
722
                                        bitset_size);
 
723
 
 
724
            }
 
725
            break;
 
726
        default:
 
727
            BM_ASSERT(0);
 
728
            break;
 
729
        } // switch
 
730
 
 
731
    } // for 
 
732
}
 
733
 
 
734
 
 
735
 
 
736
/**
553
737
    \brief Compute effective right column border of the t-matrix
554
738
    \internal
555
739
*/
572
756
    return col;
573
757
}
574
758
 
 
759
 
575
760
/**
576
761
    \brief Bit-plain splicing of a GAP block
577
762
    
594
779
                (((BLOCK_SIZE * sizeof(unsigned)) / (sizeof(GT))) / (sizeof(GT) * 8))>
595
780
                tmatrix_type;
596
781
                
597
 
    gap_transpose_engine() 
 
782
    gap_transpose_engine() : eff_cols_(0)
598
783
    {}            
599
784
    
600
785
    /// Transpose GAP block through a temp. block of aligned(!) memory
602
787
    void transpose(const GT* BMRESTRICT gap_buf, 
603
788
                         BT* BMRESTRICT tmp_block)
604
789
    {
605
 
        const unsigned plain_count = sizeof(GT)*8;
606
 
        const unsigned block_size = BLOCK_SIZE * sizeof(unsigned);
607
 
        const unsigned plain_size = block_size / (sizeof(GT) * plain_count);
608
790
        const unsigned arr_size = BLOCK_SIZE * sizeof(unsigned) / sizeof(GT);
609
791
 
610
 
        BM_ASSERT(sizeof(tmatrix_.value) == plain_size * plain_count * sizeof(GT));
 
792
        BM_ASSERT(sizeof(tmatrix_.value) == tmatrix_type::n_columns * 
 
793
                                            tmatrix_type::n_rows * sizeof(GT));
611
794
                
612
795
        // load all GAP as D-GAP(but not head word) into aligned bit-block
613
796
        gap_2_bitblock(gap_buf, tmp_block, BLOCK_SIZE);
614
797
        
615
798
        // transpose
616
 
        vect_bit_transpose<GT, plain_count, plain_size>
 
799
        vect_bit_transpose<GT, tmatrix_type::n_rows, tmatrix_type::n_columns>
617
800
                           ((GT*)tmp_block, arr_size, tmatrix_.value);
618
801
 
619
802
        // calculate number of non-zero columns
620
 
        eff_cols_ = find_effective_columns(tmatrix_);
621
 
        
622
 
    }
 
803
        eff_cols_ = find_effective_columns(tmatrix_);        
 
804
    }
 
805
 
 
806
    void compute_distance_matrix()
 
807
    {
 
808
        tmatrix_distance<typename tmatrix_type::value_type, 
 
809
                         tmatrix_type::n_rows, tmatrix_type::n_columns>
 
810
                         (tmatrix_.value, distance_);
 
811
 
 
812
        // make compression descriptor vector and statistics vector
 
813
        bit_iblock_make_pcv<unsigned char, 
 
814
                            tmatrix_type::n_rows, tmatrix_type::n_columns>
 
815
                            (distance_, pc_vector_);
 
816
 
 
817
        bit_iblock_pcv_stat(pc_vector_, 
 
818
                            pc_vector_ + tmatrix_type::n_rows, 
 
819
                            pc_vector_stat_);
 
820
    }
 
821
 
 
822
    void reduce()
 
823
    {
 
824
        tmatrix_reduce(tmatrix_, pc_vector_, eff_cols_);
 
825
        compute_tmatrix_rstat(tmatrix_, pc_vector_, rstat_vector_, eff_cols_);
 
826
    }
 
827
 
 
828
    void restore()
 
829
    {
 
830
        tmatrix_restore(tmatrix_, pc_vector_, eff_cols_);
 
831
    }
 
832
    
623
833
    
624
834
    /// Restore GAP block from the transposed matrix
625
835
    ///
627
837
                  GT* BMRESTRICT gap_buf, 
628
838
                  BT* BMRESTRICT tmp_block)
629
839
    {
630
 
        const unsigned plain_count = sizeof(GT)*8;
631
 
        const unsigned block_size = BLOCK_SIZE * sizeof(unsigned);
632
 
        const unsigned plain_size = block_size / (sizeof(GT) * plain_count);
633
 
 
634
 
        BM_ASSERT(sizeof(tmatrix_.value) == plain_size * plain_count * sizeof(GT));
 
840
        BM_ASSERT(sizeof(tmatrix_.value) == tmatrix_type::n_columns * 
 
841
                                            tmatrix_type::n_rows * sizeof(GT));
635
842
  
636
843
        // restore into a temp buffer
637
844
        GT* gap_tmp = (GT*)tmp_block;
638
845
        //*gap_tmp++ = gap_head;
639
846
       
640
 
        vect_bit_trestore<GT, plain_count, plain_size>(tmatrix_.value, gap_tmp);
 
847
        vect_bit_trestore<GT, tmatrix_type::n_rows, tmatrix_type::n_columns>(tmatrix_.value, gap_tmp);
641
848
        
642
849
        // D-Gap to GAP block recalculation
643
850
        gap_tmp = (GT*)tmp_block;
646
853
    
647
854
public:
648
855
//    GT            gap_head_;
649
 
    tmatrix_type  tmatrix_;    
650
 
    unsigned      eff_cols_;
 
856
    tmatrix_type                  tmatrix_;    
 
857
    unsigned                      eff_cols_;
 
858
    unsigned                      distance_[tmatrix_type::n_rows][tmatrix_type::n_rows];
 
859
    unsigned char                 pc_vector_[tmatrix_type::n_rows];
 
860
    unsigned                      pc_vector_stat_[bm::ibpc_end];
 
861
    typename tmatrix_type::rstat  rstat_vector_[tmatrix_type::n_rows];
651
862
};
652
863
 
653
864