Changeset 3207 for trunk/lib


Ignore:
Timestamp:
May 28, 2013, 1:24:33 PM (6 years ago)
Author:
cameron
Message:

BitStreamScanner? template class for multiblock bitstream segments.

File:
1 edited

Legend:

Unmodified
Added
Removed
  • trunk/lib/bitblock_iterator.hpp

    r3189 r3207  
    7575#undef FW
    7676
     77
     78/*
     79    A scanner to successively generate the positions marked by 1 bits
     80    in a bit stream segment of bitblock_count bit blocks.
     81
     82    Usage:
     83
     84    (1) declaration, e.g.
     85        BitStreamScanner<BitBlock, uint32_t, u8int_t, 8> s;
     86        (There is considerable flexibility for using different
     87         scanblock sizes for the main mask, as well as the
     88         scan field sizes within each block.)
     89
     90    (2) initialization/reinitialization
     91        s.init();
     92
     93    (3) load the blocks;
     94        for (i = 0; i++; i < n) {mybitblock = ...; s.load_block(mybitblock, i);}
     95
     96    (4) Iterative scan loop (generates each position exactly once.)
     97        while (s.has_next()) { pos = s.scan_to_next(); ...   };
     98*/
     99
     100template <class bitblock_t, class scanblock_t, class scanfield_t, int bitblock_count>
     101class BitStreamScanner {
     102public:
     103        /* Make sure that the number of bits in the mask at least equals
     104           the number of scanblocks. */
     105        /* Requires flag -std=gnu++0x 
     106        static_assert(sizeof(scanblock_t) * 8 >= bitblock_count * sizeof(bitblock_t)/sizeof(scanfield_t),
     107                      "Too many bitblocks for a single scanword mask");
     108        */
     109
     110        BitStreamScanner() {}
     111
     112        IDISA_ALWAYS_INLINE void init() { mask = 0;}
     113
     114        IDISA_ALWAYS_INLINE void load_block(BitBlock b, int i) {
     115                remaining._bitblock[i] = b;
     116                BitBlock mask_i = simd<sizeof(scanfield_t)*8>::sub(simd<1>::constant<0>(), b);
     117                mask |= hsimd<sizeof(scanfield_t)*8>::signmask(mask_i) << (i * sizeof(bitblock_t)/sizeof(scanfield_t));
     118        }
     119
     120        IDISA_ALWAYS_INLINE bool has_next() {
     121               
     122                     return mask != 0;
     123        }
     124
     125        IDISA_ALWAYS_INLINE int scan_to_next() {
     126               
     127                     int item_pos = scan_forward_zeroes(mask);
     128                     scanfield_t scan_item = remaining._scanfield[item_pos];
     129                     int bitpos = scan_forward_zeroes(scan_item);
     130                     scan_item = scan_item & (scan_item - 1);
     131                     remaining._scanfield[item_pos] = scan_item;
     132                     mask = mask & (mask - ((scan_item == 0) ? 1 : 0));
     133                     int pos = item_pos * sizeof(scanfield_t) * 8 + bitpos;
     134                     return pos;
     135        }
     136
     137private:
     138        union {bitblock_t _bitblock[bitblock_count];
     139               scanfield_t _scanfield[bitblock_count * sizeof(bitblock_t)/sizeof(scanfield_t)];} remaining;
     140        scanblock_t mask;                       
     141};
     142
     143
     144
    77145/*=============================================================================
    78146
    79    Deperecated:
     147   Deprecated:
    80148
    81149        BitBlock iterator classes provide Standard Template Library (STL)
Note: See TracChangeset for help on using the changeset viewer.