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

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

Use bitblock::sll, srl

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/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 4
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
36    uint64_t newline_counts;
37    BitBlock bitwise_counts[BITWISE_NEWLINE_COUNTER_BITS];
38};
39
40LineColTracker::LineColTracker(){
41  blocks_after_last_newline_block = 0;
42  last_block_with_newline = mvmd<1>::fill(1);
43  newline_counts = 0;
44  for (int i = 0; i < BITWISE_NEWLINE_COUNTER_BITS; i++) bitwise_counts[i] = mvmd<1>::fill(0);
45}
46
47inline void LineColTracker::StoreNewlines(BitBlock newline){
48  cur_newline = newline;
49}
50
51inline void LineColTracker::AdvanceBlock(){
52  BitBlock carry;
53  if (bitblock::any(cur_newline)){
54    last_block_with_newline = cur_newline;
55    blocks_after_last_newline_block = 0;
56    carry = cur_newline;
57    for (int i = 0; i < BITWISE_NEWLINE_COUNTER_BITS; i++) {
58      bitwise_half_add(bitwise_counts[i], carry, bitwise_counts[i], carry);
59    }
60    if (bitblock::any(carry)){
61      for (int i = 0; i < BITWISE_NEWLINE_COUNTER_BITS; i++) {
62        newline_counts += bitblock::popcount(bitwise_counts[i]) << i;
63        bitwise_counts[i]  = mvmd<1>::fill(0);
64      }
65      newline_counts += bitblock::popcount(carry) << BITWISE_NEWLINE_COUNTER_BITS;
66    }
67  }
68  else
69    blocks_after_last_newline_block++;
70}
71
72
73void LineColTracker::get_Line_and_Column(int pos_in_block, int & line, int & column) {
74
75  cur_newline = simd_andc(cur_newline, bitblock::sll(mvmd<1>::fill(1), mvmd<BLOCK_SIZE>::fill(pos_in_block)));
76  if (bitblock::any(cur_newline))
77    column = pos_in_block - (BLOCK_SIZE-count_backward_zeroes(cur_newline))+1;
78  else
79    column = BLOCK_SIZE*blocks_after_last_newline_block +
80             count_backward_zeroes(last_block_with_newline) + pos_in_block+1;
81
82 
83  if (bitblock::any(cur_newline))
84    line = newline_counts + bitblock::popcount(cur_newline) + 1;
85  else
86    line = newline_counts + 1;
87
88}
89
90void LineColTracker::Advance_buffer() {
91}
92
93
Note: See TracBrowser for help on using the repository browser.