source: proto/parabix2/src/LineColTracker_multithreads.h @ 1496

Last change on this file since 1496 was 1057, checked in by lindanl, 8 years ago

multithreads

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
22#define NEWLINE_BUFFERING
23
24class LineColTracker{
25  public:
26    LineColTracker();
27    inline void AdvanceBlock();
28    inline void StoreNewlines(BitBlock newline);
29    inline void Advance_buffer();
30    void get_Line_and_Column(int pos_in_block, int & line, int & column);
31  private:
32    int blocks_after_last_newline_block;
33    BitBlock last_block_with_newline;
34    BitBlock cur_newline;
35#ifdef NEWLINE_BUFFERING
36    BitBlock newline_strm[SEGMENT_SIZE/BLOCK_SIZE];
37    int newline_strm_lgth;
38#endif
39    int newline_counts;
40};
41
42LineColTracker::LineColTracker(){
43  blocks_after_last_newline_block = 0;
44  last_block_with_newline = simd_const_1(1);
45  newline_counts = 0;
46#ifdef NEWLINE_BUFFERING
47  newline_strm_lgth = 0;
48#endif
49}
50
51inline void LineColTracker::StoreNewlines(BitBlock newline){
52  cur_newline = newline;
53}
54
55inline void LineColTracker::AdvanceBlock(){
56#ifdef NEWLINE_BUFFERING
57  newline_strm[newline_strm_lgth] = cur_newline;
58  newline_strm_lgth++;
59#endif
60
61#ifndef NEWLINE_BUFFERING
62  if(bitblock_has_bit(cur_newline)){
63    newline_counts += bitblock_bit_count(cur_newline);
64    last_block_with_newline = cur_newline;
65    blocks_after_last_newline_block = 0;
66  }
67  else
68    blocks_after_last_newline_block++;
69#endif
70}
71
72
73void LineColTracker::get_Line_and_Column(int pos_in_block, int & line, int & column) {
74#ifdef NEWLINE_BUFFERING
75  Advance_buffer();
76#endif
77
78
79  cur_newline = simd_andc(cur_newline, sisd_sfl(simd_const_1(1),sisd_from_int(pos_in_block)));
80  if(bitblock_has_bit(cur_newline))
81    column = pos_in_block - (BLOCK_SIZE-count_backward_zeroes(cur_newline))+1;
82  else
83    column = BLOCK_SIZE*blocks_after_last_newline_block +
84             count_backward_zeroes(last_block_with_newline) + pos_in_block+1;
85
86 
87  if(bitblock_has_bit(cur_newline))
88    line = newline_counts + bitblock_bit_count(cur_newline) + 1;
89  else
90    line = newline_counts + 1;
91
92}
93
94void LineColTracker::Advance_buffer() {
95#ifdef NEWLINE_BUFFERING
96  BitBlock s1, s2, c1, c2, c3, t0, t1, t2, carry;
97  int i, j;
98  int last_blk = newline_strm_lgth - 1;
99  /* in case we find no newlines within the buffer, the
100     number of blocks after the last newline grows by the
101     full block count. */
102  blocks_after_last_newline_block += newline_strm_lgth; 
103  for (i = last_blk; i >= 0; i--) {
104    if (bitblock_has_bit(newline_strm[i])) {
105      last_block_with_newline = newline_strm[i];
106      blocks_after_last_newline_block = last_blk - i;
107      break;
108    }
109  }
110  last_blk = i; /* No newlines after this block. */
111  j = 0;
112  /* Process 7 blocks of the newline stream at a time. */
113  for (j = 0; j + 6 <= last_blk; j += 7) {
114    bitwise_full_add(newline_strm[j], newline_strm[j+1], newline_strm[j+2], s1, c1);
115    bitwise_full_add(newline_strm[j+3], newline_strm[j+4], newline_strm[j+5], s2, c2);
116    bitwise_full_add(s1, s2, newline_strm[j+6], t0, c3);  /* t0 is bit0 of 7 block sum */
117    bitwise_full_add(c1, c2, c3, t1, t2); /*t1 and t2 are bits 1 and 2  of 7 block sum. */
118    newline_counts += bitblock_bit_count(t0);
119    newline_counts += 2 * bitblock_bit_count(t1);
120    newline_counts += 4 * bitblock_bit_count(t2);
121  }
122  for (; j <= last_blk; j++) {
123    newline_counts += bitblock_bit_count(newline_strm[j]);
124  }
125  newline_strm_lgth = 0;
126#endif
127}
128
129
Note: See TracBrowser for help on using the repository browser.