source: proto/parabix2/src/LineColTracker.h @ 846

Last change on this file since 846 was 846, checked in by cameron, 9 years ago

Update LineColTracker? with newline buffering

File size: 3.8 KB
Line 
1/*  Parallel Bitwise Tracking of Line Number/Column Number
2    Copyright (C) 2010, 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
8#define MAX_COUNTER_BITS 24
9
10static inline void bitwise_half_add(BitBlock x, BitBlock y, BitBlock &sum, BitBlock &carry){
11  sum = simd_xor(x,y);
12  carry = simd_and(x,y);
13}
14
15static inline void bitwise_full_add(BitBlock x, BitBlock y, BitBlock z, BitBlock &sum, BitBlock &carry){
16  BitBlock sum1, carry1;
17  bitwise_half_add(x, y, sum1, carry1);
18  sum = simd_xor(z, sum1);
19  carry = simd_or(carry1, simd_and(sum1, z));
20}
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#ifdef NEWLINE_BUFFERING
34    BitBlock newline_strm[BUFFER_SIZE/BLOCK_SIZE];
35    int newline_strm_lgth;
36#endif
37    int newline_counts;
38};
39
40LineColTracker::LineColTracker(){
41  blocks_after_last_newline_block = 0;
42  last_block_with_newline = simd_const_1(1);
43  newline_counts = 0;
44#ifdef NEWLINE_BUFFERING
45  newline_strm_lgth = 0;
46#endif
47}
48
49inline void LineColTracker::StoreNewlines(BitBlock newline){
50  cur_newline = newline;
51}
52
53inline void LineColTracker::AdvanceBlock(){
54#ifdef NEWLINE_BUFFERING
55  newline_strm[newline_strm_lgth] = cur_newline;
56  newline_strm_lgth++;
57#endif
58
59#ifndef NEWLINE_BUFFERING
60  if(bitblock_has_bit(cur_newline)){
61    newline_counts += bitblock_bit_count(cur_newline);
62    last_block_with_newline = cur_newline;
63    blocks_after_last_newline_block = 0;
64  }
65  else
66    blocks_after_last_newline_block++;
67#endif
68}
69
70
71void LineColTracker::get_Line_and_Column(int pos_in_block, int & line, int & column) {
72#ifdef NEWLINE_BUFFERING
73  Advance_buffer();
74#endif
75
76
77  cur_newline = simd_andc(cur_newline, sisd_sfl(simd_const_1(1),sisd_from_int(pos_in_block)));
78  if(bitblock_has_bit(cur_newline))
79    column = pos_in_block - (BLOCK_SIZE-count_backward_zeroes(cur_newline))+1;
80  else
81    column = BLOCK_SIZE*blocks_after_last_newline_block +
82             count_backward_zeroes(last_block_with_newline) + pos_in_block+1;
83
84 
85  if(bitblock_has_bit(cur_newline))
86    line = newline_counts + bitblock_bit_count(cur_newline) + 1;
87  else
88    line = newline_counts + 1;
89
90}
91
92void LineColTracker::Advance_buffer() {
93#ifdef NEWLINE_BUFFERING
94  BitBlock s1, s2, c1, c2, c3, t0, t1, t2, carry;
95  int i, j;
96  int last_blk = newline_strm_lgth - 1;
97  /* in case we find no newlines within the buffer, the
98     number of blocks after the last newline grows by the
99     full block count. */
100  blocks_after_last_newline_block += newline_strm_lgth; 
101  for (i = last_blk; i >= 0; i--) {
102    if (bitblock_has_bit(newline_strm[i])) {
103      last_block_with_newline = newline_strm[i];
104      blocks_after_last_newline_block = last_blk - i;
105      break;
106    }
107  }
108  last_blk = i; /* No newlines after this block. */
109  j = 0;
110  /* Process 7 blocks of the newline stream at a time. */
111  for (j = 0; j + 6 <= last_blk; j += 7) {
112    bitwise_full_add(newline_strm[j], newline_strm[j+1], newline_strm[j+2], s1, c1);
113    bitwise_full_add(newline_strm[j+3], newline_strm[j+4], newline_strm[j+5], s2, c2);
114    bitwise_full_add(s1, s2, newline_strm[j+6], t0, c3);  /* t0 is bit0 of 7 block sum */
115    bitwise_full_add(c1, c2, c3, t1, t2); /*t1 and t2 are bits 1 and 2  of 7 block sum. */
116    newline_counts += bitblock_bit_count(t0);
117    newline_counts += 2 * bitblock_bit_count(t1);
118    newline_counts += 4 * bitblock_bit_count(t2);
119  }
120  for (; j <= last_blk; j++) {
121    newline_counts += bitblock_bit_count(newline_strm[j]);
122  }
123  newline_strm_lgth = 0;
124#endif
125}
126
127
Note: See TracBrowser for help on using the repository browser.