source: proto/parabix2/util/LineColTracker.hpp @ 4183

Last change on this file since 4183 was 2280, checked in by ksherdy, 7 years ago

Updated include path and Makefile.

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
8#include "../lib/simd-lib/bitblock.hpp"
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 BITWISE_NEWLINE_COUNTER_BITS 3
23
24class LineColTracker{
25  public:
26    LineColTracker();
27    inline void AdvanceBlock();
28    inline void StoreNewlines(BitBlock newline);
29    void get_Line_and_Column(int pos_in_block, int & line, int & column);
30  private:
31    int blocks_after_last_newline_block;
32    BitBlock last_block_with_newline;
33    BitBlock cur_newline;
34
35    uint64_t newline_counts;
36    BitBlock bitwise_counts[BITWISE_NEWLINE_COUNTER_BITS];
37};
38
39LineColTracker::LineColTracker(){
40  blocks_after_last_newline_block = 0;
41  last_block_with_newline = simd<1>::constant<1>();
42  newline_counts = 0;
43  for (int i = 0; i < BITWISE_NEWLINE_COUNTER_BITS; i++) bitwise_counts[i] = simd<1>::constant<0>();
44}
45
46inline void LineColTracker::StoreNewlines(BitBlock newline){
47  cur_newline = newline;
48}
49
50inline void LineColTracker::AdvanceBlock(){
51  BitBlock carry;
52  if (bitblock::any(cur_newline)){
53    last_block_with_newline = cur_newline;
54    blocks_after_last_newline_block = 0;
55    carry = cur_newline;
56    for (int i = 0; i < BITWISE_NEWLINE_COUNTER_BITS; i++) {
57      bitwise_half_add(bitwise_counts[i], carry, bitwise_counts[i], carry);
58    }
59    if (bitblock::any(carry)){
60      for (int i = 0; i < BITWISE_NEWLINE_COUNTER_BITS; i++) {
61        newline_counts += bitblock::popcount(bitwise_counts[i]) << i;
62        bitwise_counts[i]  = simd<1>::constant<0>();
63      }
64      newline_counts += bitblock::popcount(carry) << BITWISE_NEWLINE_COUNTER_BITS;
65    }
66  }
67  else
68    blocks_after_last_newline_block++;
69}
70
71
72void LineColTracker::get_Line_and_Column(int pos_in_block, int & line, int & column) {
73
74  cur_newline = simd_andc(cur_newline, bitblock::sll(simd<1>::constant<1>(), mvmd<BLOCK_SIZE>::fill(pos_in_block)));
75  if (bitblock::any(cur_newline))
76    column = pos_in_block - (BLOCK_SIZE-count_reverse_zeroes(cur_newline))+1;
77  else
78    column = BLOCK_SIZE*blocks_after_last_newline_block +
79             count_reverse_zeroes(last_block_with_newline) + pos_in_block+1;
80
81 
82  if (bitblock::any(cur_newline))
83    line = newline_counts + bitblock::popcount(cur_newline) + 1;
84  else
85    line = newline_counts + 1;
86
87}
88
Note: See TracBrowser for help on using the repository browser.