Changeset 3670


Ignore:
Timestamp:
Mar 9, 2014, 1:57:22 AM (5 years ago)
Author:
ksherdy
Message:

Added static contant member to the BitStreamScanner?. Clean up.

File:
1 edited

Legend:

Unmodified
Added
Removed
  • trunk/lib/bitblock_iterator.hpp

    r3392 r3670  
    1818        on bitblock type and scanword type.
    1919
     20    The 'scanfield_t' template parameter is equivalent to a 'scanword'
     21    in the conceptual model of scanning.
     22
    2023*/
    21 
    2224
    2325//
     
    4244
    4345        IDISA_ALWAYS_INLINE void init(const BitBlock *s) {
    44                 remaining._bitblock = *s;
    45                 mask = hsimd<FW>::signmask(simd_not(simd<FW>::eq(simd<1>::constant<0>(), remaining._bitblock)));
    46         }
     46        remaining._bitblock = *s;
     47        mask = hsimd<FW>::signmask(simd_not(simd<FW>::eq(simd<1>::constant<0>(), remaining._bitblock)));
     48    }
    4749
    4850        IDISA_ALWAYS_INLINE int has_next() {
    49                
    50                      return mask != 0;
    51         }
     51        return mask != 0;
     52    }
    5253
    5354        IDISA_ALWAYS_INLINE int scan_to_next() {
    54                
    55                      int item_pos = scan_forward_zeroes(mask);
    56                      uint32_t scan_item = remaining._FW[item_pos];
    57                      int bitpos = scan_forward_zeroes(scan_item);
    58                      scan_item = scan_item & (scan_item - 1);
    59                      remaining._FW[item_pos] = scan_item;
    60                      // We could recalculate the mask, but updating it is faster.
    61                      // Note that this update code compiles to a SETcc instruction.
    62                      mask = mask & (mask - ((scan_item == 0) ? 1 : 0));
    63                      int pos = item_pos * FW + bitpos;
    64                      return pos;
    65         }
    66         // It slows things down to store the position.
     55        int item_pos = scan_forward_zeroes(mask);
     56        uint32_t scan_item = remaining._FW[item_pos];
     57        int bitpos = scan_forward_zeroes(scan_item);
     58        scan_item = scan_item & (scan_item - 1);
     59        remaining._FW[item_pos] = scan_item;
     60        // We could recalculate the mask, but updating it is faster.
     61        // Note that this update code compiles to a SETcc instruction.
     62        mask = mask & (mask - ((scan_item == 0) ? 1 : 0));
     63        int pos = item_pos * FW + bitpos;
     64        return pos;
     65    }
     66
     67    // It slows things down to store the position.
    6768        //IDISA_ALWAYS_INLINE int32_t get_pos() { return pos;}
    6869private:
    6970        union {bitblock_t _bitblock;
    70                uint8_t _8[sizeof(bitblock_t)];
    71                uint32_t _32[sizeof(bitblock_t)/sizeof(uint32_t)];} remaining;
    72         scanblock_t mask;                       
     71           uint8_t _8[sizeof(bitblock_t)];
     72           uint32_t _32[sizeof(bitblock_t)/sizeof(uint32_t)];} remaining;
     73    scanblock_t mask;
    7374};
    7475#undef _FW
     
    9293
    9394    (3) load the blocks;
    94         for (i = 0; i++; i < n) {mybitblock = ...; s.load_block(mybitblock, i);}
     95    for (i = 0; i < n;  i++) {mybitblock = ...; s.load_block(mybitblock, i);}
    9596
    9697    (4) Iterative scan loop (generates each position exactly once.)
     
    9899*/
    99100
    100 template <class bitblock_t, class scanblock_t, class scanfield_t, int bitblock_count>
     101template <class bitblock_t, class scanblock_t, class scanfield_t,
     102          int bitblock_count = sizeof(scanblock_t) * 8 * sizeof(scanfield_t) / sizeof(bitblock_t)>
    101103class BitStreamScanner {
    102104public:
    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");
     105
     106    // static constants
     107    static const int max_bitblock_count = bitblock_count;
     108
     109    /* Make sure that the number of bits in the mask at least equals the number of scanblocks. */
     110    /* Requires flag -std=gnu++0x  */
     111    static_assert(sizeof(scanblock_t) * 8 >= bitblock_count * sizeof(bitblock_t)/sizeof(scanfield_t),
     112    "Too many bitblocks for a single scanword mask");
    108113       
    109 
    110114        BitStreamScanner() {}
    111115
     
    113117
    114118        IDISA_ALWAYS_INLINE void load_block(BitBlock b, int i) {
    115                 remaining._bitblock[i] = b;
    116                 BitBlock mask_i = simd_not(simd<sizeof(scanfield_t)*8>::eq(simd<1>::constant<0>(), b));
    117                 mask += ((scanblock_t) hsimd<sizeof(scanfield_t)*8>::signmask(mask_i)) << ((scanblock_t) i * (sizeof(bitblock_t)/sizeof(scanfield_t)));
    118         }
     119        remaining._bitblock[i] = b;
     120        BitBlock mask_i = simd_not(simd<sizeof(scanfield_t)*8>::eq(simd<1>::constant<0>(), b));
     121        mask += ((scanblock_t) hsimd<sizeof(scanfield_t)*8>::signmask(mask_i)) << ((scanblock_t) i * (sizeof(bitblock_t)/sizeof(scanfield_t)));
     122    }
    119123
    120124        IDISA_ALWAYS_INLINE bool has_next() {
    121                      return mask != 0;
    122         }
     125        return mask != 0;
     126    }
    123127
    124128        IDISA_ALWAYS_INLINE int scan_to_next() {
    125                      int item_pos = scan_forward_zeroes(mask);
    126                      scanfield_t scan_item = remaining._scanfield[item_pos];
    127                      int bitpos = scan_forward_zeroes(scan_item);
    128                      scan_item = scan_item & (scan_item - 1);
    129                      remaining._scanfield[item_pos] = scan_item;
    130                      mask = mask & (mask - ((scan_item == 0) ? 1 : 0));
    131                      int pos = item_pos * sizeof(scanfield_t) * 8 + bitpos;
    132                      return pos;
    133         }
     129        int item_pos = scan_forward_zeroes(mask);
     130        scanfield_t scan_item = remaining._scanfield[item_pos];
     131        int bitpos = scan_forward_zeroes(scan_item);
     132        scan_item = scan_item & (scan_item - 1);
     133        remaining._scanfield[item_pos] = scan_item;
     134        mask = mask & (mask - ((scan_item == 0) ? 1 : 0));
     135        int pos = item_pos * sizeof(scanfield_t) * 8 + bitpos;
     136        return pos;
     137    }
    134138
    135139        IDISA_ALWAYS_INLINE int get_final_pos() {
    136                      int item_pos = sizeof(scanblock_t) * 8 - scan_backward_zeroes((scanblock_t) mask) - 1;
    137                      scanfield_t scan_item = remaining._scanfield[item_pos];
    138                      int bitpos = sizeof(scanblock_t)  * 8 - scan_backward_zeroes((scanblock_t) scan_item) - 1;
    139                      int pos = item_pos * sizeof(scanfield_t) * 8 + bitpos;
    140                      return pos;
    141         }
     140        int item_pos = sizeof(scanblock_t) * 8 - scan_backward_zeroes((scanblock_t) mask) - 1;
     141        scanfield_t scan_item = remaining._scanfield[item_pos];
     142        int bitpos = sizeof(scanblock_t)  * 8 - scan_backward_zeroes((scanblock_t) scan_item) - 1;
     143        int pos = item_pos * sizeof(scanfield_t) * 8 + bitpos;
     144        return pos;
     145    }
    142146
    143147        IDISA_ALWAYS_INLINE void clear_from(int pos) {
    144                 int item_pos = pos / (sizeof(scanfield_t) * 8);
    145                 int bitpos = pos % (sizeof(scanfield_t) * 8);
    146                 remaining._scanfield[item_pos] &= ((((scanfield_t) 1) << bitpos) - 1);
    147                 item_pos += remaining._scanfield[item_pos] == 0 ? 0 : 1;
    148                 mask = mask & (((scanblock_t) 1) << item_pos) - 1;
    149                 for (int i = item_pos; i < bitblock_count * 2; i++) remaining._scanfield[i] = 0;
    150         }
     148        int item_pos = pos / (sizeof(scanfield_t) * 8);
     149        int bitpos = pos % (sizeof(scanfield_t) * 8);
     150        remaining._scanfield[item_pos] &= ((((scanfield_t) 1) << bitpos) - 1);
     151        item_pos += remaining._scanfield[item_pos] == 0 ? 0 : 1;
     152        mask = mask & (((scanblock_t) 1) << item_pos) - 1;
     153        for (int i = item_pos; i < bitblock_count * 2; i++) remaining._scanfield[i] = 0;
     154    }
    151155   
    152156        IDISA_ALWAYS_INLINE int count() {
     
    155159#define PARALLEL_COUNT
    156160#ifdef PARALLEL_COUNT
    157                 BitBlock sum8 = simd<1>::constant<0>();
    158                 for (int i = 0; i < bitblock_count/2; i++) {
    159                     BitBlock ct4 = simd<4>::add(simd<4>::popcount(remaining._bitblock[2*i]), simd<4>::popcount(remaining._bitblock[2*i+1]));
    160                     sum8 = simd<8>::add(sum8, simd<8>::add_hl(ct4));
    161                 }
    162                 if ((bitblock_count & 1) != 0) {  // Should be compiled out if bitblock_count is even.
    163                     sum8 = simd<8>::add(sum8, simd<8>::popcount(remaining._bitblock[bitblock_count]));
    164                 }
    165                 ct = mvmd<32>::extract<0>(simd<128>::add_hl(simd<64>::add_hl(simd<32>::add_hl(simd<16>::add_hl(sum8)))));
     161    BitBlock sum8 = simd<1>::constant<0>();
     162    for (int i = 0; i < bitblock_count/2; i++) {
     163        BitBlock ct4 = simd<4>::add(simd<4>::popcount(remaining._bitblock[2*i]), simd<4>::popcount(remaining._bitblock[2*i+1]));
     164        sum8 = simd<8>::add(sum8, simd<8>::add_hl(ct4));
     165    }
     166    if ((bitblock_count & 1) != 0) {  // Should be compiled out if bitblock_count is even.
     167        sum8 = simd<8>::add(sum8, simd<8>::popcount(remaining._bitblock[bitblock_count]));
     168    }
     169    ct = mvmd<32>::extract<0>(simd<128>::add_hl(simd<64>::add_hl(simd<32>::add_hl(simd<16>::add_hl(sum8)))));
    166170#endif
    167171#ifndef PARALLEL_COUNT
    168                 for (int i = 0; i < bitblock_count; i++) {
    169                     ct += bitblock::popcount(remaining._bitblock[i]);
    170                 }
     172    for (int i = 0; i < bitblock_count; i++) {
     173        ct += bitblock::popcount(remaining._bitblock[i]);
     174    }
    171175#endif
    172                 return ct;
    173         }
    174    
     176        return ct;
     177        }
    175178   
    176179private:
    177180        union {bitblock_t _bitblock[bitblock_count];
    178                scanfield_t _scanfield[bitblock_count * sizeof(bitblock_t)/sizeof(scanfield_t)];} remaining;
    179         scanblock_t mask;
    180 };
    181 
    182 
     181           scanfield_t _scanfield[bitblock_count * sizeof(bitblock_t)/sizeof(scanfield_t)];} remaining;
     182    scanblock_t mask;
     183};
    183184
    184185/*=============================================================================
    185186
    186    Deprecated:
    187 
    188         BitBlock iterator classes provide Standard Template Library (STL)
    189         Input iterator 'like' interface implementations as a programmer
    190         convenience and allow iterator classes to be used
    191         with STL Algorithms.
    192         Forward iterators can only step forward (++) marker-bit by marker-bit.
    193         Reverse iterators can only step backwards (--) marker-bit by marker-bit.
    194 
    195         BitStream iterator class provide an STL Input iterator interface to scan
    196         through an array of scanwords (stream) in the forward direction.
    197 
    198 
    199   Classes Descriptions:
    200 
    201         *       BitBlock Scanners
    202 
    203         Scanner - Scanner base class.
    204         ForwardScanner - Scans a bitblock of scanwords in the forward direction.
    205         ReverseScanner - Scans a bitblock of scanwords in the reverse direction.
    206 
    207         * BitBlock Iterators
    208 
    209   ForwardIterator template class wraps ForwardScanner.
    210        
    211         - Implements STL Input iterator interface.
    212         - Reads elements only once.     
    213   - '->' - Not implemented.
    214 
    215   ReverseIterator template class wraps ReverseScanner.
     187Classes Descriptions:
     188
     189    * BitBlock Scanners
     190
     191    Scanner - Scanner base class.
     192    ForwardScanner - Scans a BitBlock of ScanWords in the forward direction.
     193    ReverseScanner - Scans a bitblock of ScanWords in the reverse direction.
     194
     195    Deprecated (BitBlock iterators only)
     196
     197    * BitBlock Iterators
     198
     199    BitBlock iterator classes provide Standard Template Library (STL)
     200    Input iterator 'like' interface implementations as a programmer
     201    convenience and allow iterator classes to be used
     202    with STL Algorithms.
     203
     204    Forward iterators can only step forward (++) marker-bit by marker-bit.
     205    Reverse iterators can only step backwards (--) marker-bit by marker-bit.
     206
     207
     208    ForwardIterator template class wraps ForwardScanner.
     209
     210    - Implements STL Input iterator interface.
     211    - Reads elements only once.
     212    - '->' - Not implemented.
     213
     214    ReverseIterator template class wraps ReverseScanner.
    216215
    217216        - An STL 'like' iterator that implements prefix and postfix decrement operators.
    218217    Under STL, a reverse iterator implementation necessitates the implementation of
    219                 the STL bidirectional interface and hence scanning in both directions.
    220                 This functionality is not yet required and hence not implemented.
     218    the STL bidirectional interface and hence scanning in both directions.
     219    This functionality is not yet required and hence not implemented.
    221220        - Reads elements only once.
    222   - '->' - Not implemented.
     221    - '->' - Not implemented.
    223222
    224223        BitBlockForwardIterator - ForwardIterator derived specialization of ForwardIterator<BitBlock, Scanword>
    225 
    226224        BitBlockReverseIterator - ForwardIterator derived specialization of ReverseIterator<BitBlock, Scanword>
    227225
    228226        * BitStreamIterators
    229227
    230   BitStreamIterator class wraps ForwardScanner.
     228    BitStreamIterator class wraps ForwardScanner.
    231229        - Scans an array (stream) of scanwords in contiguous memory.
    232230        - Implements STL Input iterator interface.
    233231        - Reads elements only once.     
    234   - '->' - Not implemented.
     232    - '->' - Not implemented.
    235233        - May be more appropriately named ForwardBitStreamIterator.
    236234
    237235=============================================================================*/
     236
    238237//
    239238// Scanner Classes
     
    315314};
    316315
    317 
    318316template <class bitblock_t, class scanblock_t>
    319317class ReverseScanner: public Scanner<bitblock_t, scanblock_t> {
     
    368366};
    369367
    370 
    371368//
    372369// BitBlock Iterator Classses
     
    441438        BitBlockForwardIterator(BitBlock * s): ForwardIterator<BitBlock, ScanWord>(s){}
    442439};
    443 
    444440
    445441template<class bitblock_t, class scanblock_t>
     
    622618};
    623619
    624 
    625 
    626620#undef has_bit
    627621
    628 
    629622#endif // BITBLOCK_ITERATOR_H_
    630623
Note: See TracChangeset for help on using the changeset viewer.