source: proto/parabix2/src/LineColTracker.hpp @ 1534

Last change on this file since 1534 was 1534, checked in by cameron, 8 years ago

Initial LineColTracker? with IDISA ops

File size: 2.8 KB
Line 
1/*  Parallel Bitwise Tracking of Line Number/Column Number
2    Copyright (C) 2010, 2011, Dan Lin and Robert D. Cameron
3    Licensed to the public under the Open Software License 3.0.
4    Licensed to International Characters Inc.
5       under the Academic Free License version 3.0.
6*/
7
8static inline void bitwise_half_add(BitBlock x, BitBlock y, BitBlock &sum, BitBlock &carry){
9  sum = simd_xor(x,y);
10  carry = simd_and(x,y);
11}
12
13static inline void bitwise_full_add(BitBlock x, BitBlock y, BitBlock z, BitBlock &sum, BitBlock &carry){
14  BitBlock sum1, carry1;
15  bitwise_half_add(x, y, sum1, carry1);
16  sum = simd_xor(z, sum1);
17  carry = simd_or(carry1, simd_and(sum1, z));
18}
19
20#define BITWISE_NEWLINE_COUNTER_BITS 4
21
22class LineColTracker{
23  public:
24    LineColTracker();
25    inline void AdvanceBlock();
26    inline void StoreNewlines(BitBlock newline);
27    inline void Advance_buffer();
28    void get_Line_and_Column(int pos_in_block, int & line, int & column);
29  private:
30    int blocks_after_last_newline_block;
31    BitBlock last_block_with_newline;
32    BitBlock cur_newline;
33
34    int newline_counts;
35    BitBlock bitwise_counts[BITWISE_NEWLINE_COUNTER_BITS];
36};
37
38LineColTracker::LineColTracker(){
39  blocks_after_last_newline_block = 0;
40  last_block_with_newline = mvmd<1>::fill(1);
41  newline_counts = 0;
42  for (int i = 0; i < BITWISE_NEWLINE_COUNTER_BITS; i++) bitwise_counts[i] = mvmd<1>::fill(0);
43}
44
45inline void LineColTracker::StoreNewlines(BitBlock newline){
46  cur_newline = newline;
47}
48
49inline void LineColTracker::AdvanceBlock(){
50  BitBlock carry;
51  if (bitblock::any(cur_newline)){
52    last_block_with_newline = cur_newline;
53    blocks_after_last_newline_block = 0;
54    carry = cur_newline;
55    for (int i = 0; i < BITWISE_NEWLINE_COUNTER_BITS; i++) {
56      bitwise_half_add(bitwise_counts[i], carry, bitwise_counts[i], carry);
57    }
58    if (bitblock::any(carry)){
59      for (int i = 0; i < BITWISE_NEWLINE_COUNTER_BITS; i++) {
60        newline_counts += simd<BLOCKSIZE>::popcount(bitwise_counts[i]) << i;
61        bitwise_counts[i]  = mvmd<1>::fill(0);
62      }
63      newline_counts += simd<BLOCKSIZE>::popcount(carry) << BITWISE_NEWLINE_COUNTER_BITS;
64    }
65  }
66  else
67    blocks_after_last_newline_block++;
68}
69
70
71void LineColTracker::get_Line_and_Column(int pos_in_block, int & line, int & column) {
72
73  cur_newline = simd_andc(cur_newline, simd<BLOCKSIZE>::sll(mvmd<1>::fill(1), mvmd<BLOCKSIZE>::fill(pos_in_block)));
74  if (bitblock::any(cur_newline))
75    column = pos_in_block - (BLOCK_SIZE-count_backward_zeroes(cur_newline))+1;
76  else
77    column = BLOCK_SIZE*blocks_after_last_newline_block +
78             count_backward_zeroes(last_block_with_newline) + pos_in_block+1;
79
80 
81  if (bitblock::any(cur_newline))
82    line = newline_counts + simd<BLOCKSIZE>::popcount(cur_newline) + 1;
83  else
84    line = newline_counts + 1;
85
86}
87
88void LineColTracker::Advance_buffer() {
89}
90
91
Note: See TracBrowser for help on using the repository browser.