source: proto/s2k/demo/needle/needle_template.cpp @ 3674

Last change on this file since 3674 was 3674, checked in by ksherdy, 5 years ago

Updated needle_template.cpp in preparation for s2k graph implementation.

File size: 8.9 KB
Line 
1/**
2 * 'Needle-in-a-haystack' parallel string search C++ template.
3 *
4 * Author:   Ken Herdy
5 *
6 * Usage:    needle <filename>
7 *
8 * Description:   
9 *
10 * Searches the input file for occurences of the search string 'needle'.
11 * Prints a listing of matched occurences of the search string.
12 * Each matched occurence is printed on a separated line
13 * and is formatted as 'offset:needle', where needle is the search
14 * string and offset is the zero-index offset of the first character
15 * of each match.
16 *
17 * For example, given an input file containing three occurences of 'needle'
18 * at zero-indexed offsets 47,107, and 189, the 'Needle-in-a-haystack'
19 * application writes the following results to standard output.
20 *
21 * 47:needle
22 * 107:needle
23 * 189:needle
24 *
25 * The 'Needle-in-a-haystack' C++ template file.
26 *
27 * 1. Reads the input text stream from file.
28 * 2. Implements a buffer-at-a-time processing model that processes source
29 *    text as:
30 *    (i) one or more full segments, and then
31 *    (ii) zero or one partial segments, and then
32 *    (iii) zero or one partial blocks.
33 * 3. Marks all matches in bit-space.
34 * 4. Iterates over the matches.all mark stream in byte-space, printing
35 *    the position of each match of the fixed-string 'needle'.
36 *
37 * The C++ Template Segment-at-a-time Processing Model.
38 *
39 * 1. Implements a segment-at-a-time with copyback strategy to handle
40 *    matches that cross segment boundaries.
41 * 2. Leverages BitStreamScanner segment-at-a-time, multi-level
42 *    index (filter) in which only blocks that contain matches are
43 *    scanned.
44 *
45 * Note: The behaviour of the 'needle' \LangName{} program  is equivalent
46 * to the grep utility command:
47 * 'grep needle filename --only-matching --byte-offset'
48 * given input that does not contain line breaks.
49 *
50 * -o, --only-matching
51 * Print only the matched (non-empty) parts of a matching line, with each
52 * such part on a separate output line.
53 *
54 * -b, --byte-offset
55 * Print the 0-based byte offset within the input file before each line of
56 * output. If -o  * (--only-matching) is specified, print the offset of
57 * the matching part itself.
58 *
59 **/
60
61// Platform independent runtime support libraries and C++ libraries.
62#include <simd-lib/bitblock.hpp>
63#include <simd-lib/carryQ.hpp>
64#include <simd-lib/pabloSupport.hpp>
65#include <simd-lib/bitblock_iterator.hpp>
66#include <stdio.h>
67#include <stdlib.h>
68#include <simd-lib/s2p.hpp>
69
70// Fixed search string.
71const char * fixed_pattern  = "needle";
72const int pattern_size      = strlen(fixed_pattern);
73
74// Platform dependent definitions. // Example only, defined in simd-lib/builtins.hpp.
75typedef __m128i BitBlock;
76typedef BitBlock BytePack;
77typedef uint32_t ScanWord;
78
79// Segment-at-a-time buffered stream processing parameters.
80const int SCANBLOCK_SIZE   = sizeof(ScanWord) * 8;
81const int SCANFIELD_SIZE   = sizeof(ScanWord) * 8;
82// const int BLOCK_SIZE       =  sizeof(BitBlock) * 8;                       
83const int SEGMENT_BLOCKS   = SCANBLOCK_SIZE * SCANFIELD_SIZE / BLOCK_SIZE;
84const int SEGMENT_SIZE     = SEGMENT_BLOCKS * BLOCK_SIZE;
85const int CACHE_SIZE       = 32768;         
86const int BUFFER_SEGMENTS  = CACHE_SIZE / SEGMENT_SIZE;
87const int BUFFER_SIZE      = BUFFER_SEGMENTS * SEGMENT_SIZE;
88
89BitBlock file_extent_mask(int size); 
90
91// Transpostion runtime support
92struct Basis {
93  BitBlock b7;
94  BitBlock b6;
95  BitBlock b5;
96  BitBlock b4;
97  BitBlock b3;
98  BitBlock b2;
99  BitBlock b1;
100  BitBlock b0;
101};
102
103// @ global - Parameter replaced with C++ translation of stream structs
104//            and struct functions definitions
105@global
106
107struct Basis basis;
108// @ decl - Replaced with a set of C++ stream struct declarations.
109@decl
110
111// Transpostion (runtime support). Example only, defined in simd-lib/transpose.hpp.
112struct Transpose {
113       
114  void do_block(char * byte_data, Basis & basis) {
115        BytePack * Byte = (BytePack *) byte_data;
116
117        s2p(Byte[0], Byte[1], Byte[2], Byte[3], 
118            Byte[4], Byte[5], Byte[6], Byte[7],
119            basis.b0, basis.b1, basis.b2, basis.b3, 
120            basis.b4, basis.b5, basis.b6, basis.b7);
121  } 
122
123  void do_final_block(char * byte_data, Basis & basis, BitBlock & EOF_mask) {
124        BytePack * Byte = (BytePack *) byte_data;
125
126        s2p(Byte[0], Byte[1], Byte[2], Byte[3], 
127            Byte[4], Byte[5], Byte[6], Byte[7],
128            basis.b0, basis.b1, basis.b2, basis.b3, 
129            basis.b4, basis.b5, basis.b6, basis.b7);
130
131        basis.b7 = simd_and(basis.b7, EOF_mask);
132        basis.b6 = simd_and(basis.b6, EOF_mask); 
133        basis.b5 = simd_and(basis.b5, EOF_mask); 
134        basis.b4 = simd_and(basis.b4, EOF_mask); 
135        basis.b3 = simd_and(basis.b3, EOF_mask); 
136        basis.b2 = simd_and(basis.b2, EOF_mask); 
137        basis.b1 = simd_and(basis.b1, EOF_mask); 
138        basis.b0 = simd_and(basis.b0, EOF_mask);
139  }
140};
141
142struct Transpose transpose;
143// @ stream_stmts - Replaced with C++ stream functions declarations.
144@stream_stmts
145
146// Segment-at-a-time bufferd processing parameters.
147int bytes_read              = 0;
148int bytes_avail             = 0;
149
150int copy_back_size          = 0;
151int copy_back_index         = 0;
152
153int block_index             = 0; // block index wrt current segment
154int block_base              = 0; // byte offset wrt current segment
155
156int segment_index           = 0; // segment index wrt current buffer  // unused
157int segment_base            = 0; // segment offset wrt current buffer // unused
158
159int final_segment_size      = 0; // size of final segment within a buffer
160
161int stream_base             = 0;
162int match_pos               = 0;
163
164int main(int argc, char * argv[]) {
165  if ((2 > argc) || (2 < argc)) { 
166      printf("Usage: %s <filename>\n", argv[0]); exit(-1);   
167  } 
168 
169  char * infilename = argv[argc-1]; 
170  FILE * istream;
171  if((istream = fopen(infilename, "rb")) == NULL ) { 
172      printf("fopen error"); exit( 1 );
173  } 
174
175  ATTRIBUTE_SIMD_ALIGN char buffer[BUFFER_SIZE];
176  // Pablo transpose.do_block(), transpose.do_final_block()
177  // expect 'byte_data' and 'basis' names as input and output arguments.
178  char * byte_data = buffer; 
179
180  // Marker stream iterator.
181  BitStreamScanner<BitBlock, ScanWord, ScanWord, SEGMENT_BLOCKS> scanner;
182 
183  // Segment-at-a-time processing.
184  while(!feof(istream)) { 
185    // Read Stream in BUFFER_SIZE - strlen("needle") byte chunks.
186    bytes_read  = fread(buffer + copy_back_size, 1, 
187                        BUFFER_SIZE - copy_back_size, istream);
188    bytes_avail = bytes_read + copy_back_size;
189
190    if(feof(istream)) { bytes_avail--; }
191    if(ferror(istream)) { perror( "io error" ); exit(1); }
192 
193    // Process full segments.
194    block_base      = 0;
195//    segment_base    = 0;
196//    segment_index   = 0;
197
198    while (bytes_avail >= SEGMENT_SIZE) {
199      scanner.init();
200     
201      for(block_index = 0;
202          block_index < SEGMENT_BLOCKS;
203          block_index++, block_base+=BLOCK_SIZE) {
204         
205        byte_data = &buffer[block_base]; 
206        //Replaced with C++ stream function 'do_block()' calls.
207        @block_stmts
208                         
209        scanner.load_block(matches.all, block_index);
210      }
211
212      while(scanner.has_next()) {
213        match_pos = scanner.scan_to_next()
214                       + stream_base - pattern_size + 1;
215        printf("%d:%s\n", match_pos, fixed_pattern);
216      }
217
218//      segment_index++;
219//      segment_base = segment_index * SEGMENT_SIZE;
220//      stream_base  = segment_base;
221      stream_base += SEGMENT_SIZE;
222      bytes_avail -= SEGMENT_SIZE;     
223    }   
224   
225    // Process the final partial segment full blocks.
226    block_index = 0;
227    final_segment_size = bytes_avail;
228    scanner.init();
229
230    // Process full blocks.
231    while (bytes_avail >= BLOCK_SIZE) {
232      byte_data = &buffer[block_base]; 
233      //Replaced with C++ stream function 'do_block()' calls.
234      @block_stmts
235
236      scanner.load_block(matches.all, block_index);
237     
238      block_base += BLOCK_SIZE;
239      bytes_avail -= BLOCK_SIZE;
240      block_index++;
241    }
242
243    // Process the final partial block.
244    if(bytes_avail > 0) {
245      BitBlock EOF_mask = file_extent_mask(bytes_avail);
246      byte_data = &buffer[block_base]; 
247      //Replaced with C++ stream function 'do_final_block()' calls.
248      @final_block_stmts
249     
250      scanner.load_block(matches.all, block_index);
251    }
252
253    while(scanner.has_next()) {
254      match_pos = scanner.scan_to_next()
255                     + stream_base - pattern_size + 1;
256                     
257      printf("%d:%s\n", match_pos, fixed_pattern);
258    }
259
260    stream_base += final_segment_size;
261   
262    // Copy strlen("needle") - 1 bytes at the segment boundary to handle
263    // partial matches of the "needle" at segment boundaries.
264    copy_back_size     = pattern_size - 1;
265    copy_back_index    = block_base + bytes_avail - copy_back_size;
266    memmove(&buffer[0], &buffer[copy_back_index], copy_back_size);
267
268    stream_base -= copy_back_size;
269  }
270
271  fclose(istream);
272  return 0; 
273}
274
275BitBlock file_extent_mask(int size) {
276  return bitblock::srl(simd<1>::constant<1>(), convert(BLOCK_SIZE-size));
277}
Note: See TracBrowser for help on using the repository browser.