source: proto/s2k/trunk/demo/grep/grep_template_segment.cpp @ 3758

Last change on this file since 3758 was 3758, checked in by ksherdy, 6 years ago

Added grep s2k target.

File size: 15.3 KB
Line 
1/**
2 * grep static fixed string search C++ template.
3 *
4 * Author:   Ken Herdy
5 *
6 * Usage: ./grep <infile> [-o outfile]
7 *
8 * Description: Segment-at-a-time template. Implements a line-at-a-time copyback processing model.
9 *
10 * '_offset' => 0-based byte offsets
11 * '_pos'    => 1-based bytes offsets
12 *
13 * Future Work:
14 *
15 * a. Lookahead.
16 * b. Support multiple segments a.k.a. buffer-at-a-time.
17 * c. Compile in s2k. <--
18 * d. s2k iterators for (start, follow) in (starts_stream, follows_stream) do { }
19 *
20 * Segment-at-a-time Processing Issues:
21 *
22 * 1. Start-of-stream or equivalently start-of-segment clear()...
23 *    The ScanTo and EOF_mask processing ensure a 'fence post' at the
24 *    end of each segment as well as at the end of file.
25 *
26 * 'grep.py' and 'grep_template.cpp' are tightly coupled on a number of variables:
27 *
28 * 1. Tranpose.do_block expects 'byte_data' and 'basis_bits'.
29 * 2. All StreamFunction.do_final_block methods expect 'EOF_mask'.
30 * 3. Sequential iterators (scanners) expect 'output.matches'.
31 * 4. Sequential iterators (scanners) expect 'lex.LF'.
32 *
33 **/
34
35#define DEBUG 0
36
37// Platform independent runtime support libraries and C++ libraries.
38#include <simd-lib/bitblock.hpp>
39#include <simd-lib/carryQ.hpp>
40#include <simd-lib/pabloSupport.hpp>
41#include <simd-lib/bitblock_iterator.hpp>
42#include <stdio.h>
43#include <stdlib.h>
44#include <simd-lib/s2p.hpp>
45
46// C++
47#include <string>
48#include <iostream>
49using namespace std;
50
51// Fixed pattern.
52const char * fixed_pattern  = "apple";
53const int pattern_size      = strlen(fixed_pattern);
54
55// Platform dependent definitions. // Example only, defined in simd-lib/builtins.hpp.
56typedef __m128i BitBlock;
57typedef BitBlock BytePack;
58typedef uint32_t ScanWord;
59
60// Segment-at-a-time buffered stream processing parameters.
61const int SCANBLOCK_SIZE   = sizeof(ScanWord) * 8;
62const int SCANFIELD_SIZE   = sizeof(ScanWord) * 8;
63// const int BLOCK_SIZE       =  sizeof(BitBlock) * 8;
64const int SEGMENT_BLOCKS   = SCANBLOCK_SIZE * SCANFIELD_SIZE / BLOCK_SIZE;
65const int SEGMENT_SIZE     = SEGMENT_BLOCKS * BLOCK_SIZE;
66
67//const int CACHE_SIZE       = 32768;
68//const int BUFFER_SEGMENTS  = CACHE_SIZE / SEGMENT_SIZE;
69//const int BUFFER_SIZE      = BUFFER_SEGMENTS * SEGMENT_SIZE; // SEGMENT_SIZE; //
70
71// @ global - Parameter replaced with C++ translation of stream structs
72//            and struct functions definitions
73@global
74
75// @ decl - Replaced with a set of C++ stream struct declarations.
76@decl
77
78// Transpostion (runtime support). Example only, defined in simd-lib/transpose.hpp.
79struct Transpose {
80
81  void do_block(char * byte_data, Basis_bits & basis_bits) {
82        BytePack * Byte = (BytePack *) byte_data;
83
84        s2p(Byte[0], Byte[1], Byte[2], Byte[3],
85            Byte[4], Byte[5], Byte[6], Byte[7],
86            basis_bits.bit_0, basis_bits.bit_1, basis_bits.bit_2, basis_bits.bit_3,
87            basis_bits.bit_4, basis_bits.bit_5, basis_bits.bit_6, basis_bits.bit_7);
88  }
89
90  void do_final_block(char * byte_data, Basis_bits & basis_bits, BitBlock & FEM_mask) {
91        BytePack * Byte = (BytePack *) byte_data;
92
93        s2p(Byte[0], Byte[1], Byte[2], Byte[3],
94            Byte[4], Byte[5], Byte[6], Byte[7],
95            basis_bits.bit_0, basis_bits.bit_1, basis_bits.bit_2, basis_bits.bit_3,
96            basis_bits.bit_4, basis_bits.bit_5, basis_bits.bit_6, basis_bits.bit_7);
97
98        basis_bits.bit_7 = simd_and(basis_bits.bit_7, FEM_mask);
99        basis_bits.bit_6 = simd_and(basis_bits.bit_6, FEM_mask);
100        basis_bits.bit_5 = simd_and(basis_bits.bit_5, FEM_mask);
101        basis_bits.bit_4 = simd_and(basis_bits.bit_4, FEM_mask);
102        basis_bits.bit_3 = simd_and(basis_bits.bit_3, FEM_mask);
103        basis_bits.bit_2 = simd_and(basis_bits.bit_2, FEM_mask);
104        basis_bits.bit_1 = simd_and(basis_bits.bit_1, FEM_mask);
105        basis_bits.bit_0 = simd_and(basis_bits.bit_0, FEM_mask);
106  }
107};
108
109struct Transpose transpose;
110// @ stream_stmts - Replaced with C++ stream functions declarations.
111@stream_stmts
112
113// Segment-at-a-time parameters.
114int bytes_read              = 0;
115int bytes_avail             = 0;  // wrt current segment
116int bytes_remaining         = 0;
117
118int copy_back_size          = 0;
119int copy_back_offset        = 0;
120
121int block_index             = 0; 
122int block_base              = 0; 
123
124//int segment_index           = 0; // segment index wrt current buffer  // unused
125//int segment_base            = 0; // segment offset wrt current buffer // unused
126
127int stream_base             = 0;
128
129int match_offset            = 0; // 0-based
130int line_start_offset       = 0; 
131int line_end_offset         = 0; 
132
133int line_final_start_offset = 0; 
134int line_final_end_offset   = 0;
135
136int main(int argc, char * argv[]) {
137   
138    char * infilename, * outfilename;
139    FILE * infile, * outfile;
140       
141    int opt_code;
142    int byte_offset             = 0;
143    int count_only_option       = 0;
144    int only_matching           = 0;
145    int print_version_option    = 0;
146   
147    while ((opt_code = getopt(argc, argv, "bcov?")) != -1) {
148        switch (opt_code) {
149        case 'b':
150            byte_offset = 1;
151            break;
152        case 'c':
153            count_only_option = 1;
154            printf("Not implemented.");
155            break;
156        case 'o':
157            only_matching = 1;
158            break;           
159        case 'v':
160            print_version_option = 1;
161            break;
162        case '?':
163            printf("Usage: %s [-c] [-v] <inputfile> [<outputfile>]\n", argv[0]);
164            exit(-1);
165            break;
166        default:
167            printf ("Invalid option: %c\n", opt_code);
168            printf("Usage: %s [-c] [-v] <inputfile> [<outputfile>]\n", argv[0]);
169            exit(-1);
170        }
171    }
172   
173  if (optind >= argc) {
174    printf ("Too few arguments\n");
175    printf("Usage: %s [-c] [-v] <regex> <inputfile> [<outputfile>]\n", argv[0]);
176    exit(-1);
177  }
178     
179  infilename = argv[optind++];
180  infile = fopen(infilename, "rb");
181  if (!infile) {
182      fprintf(stderr, "Error: cannot open %s.\n", infilename);
183      exit(-1);
184  }
185
186  if(optind >= argc) {
187      outfile = stdout;
188  } else {
189      outfilename = argv[optind++];
190      if (optind != argc) {
191          printf ("Too many arguments\n");
192          printf("Usage: %s [-c] [-v] <regex> <inputfile> [<outputfile>]\n", argv[0]);
193          exit(-1);
194      }
195      outfile = fopen(outfilename, "wb");
196      if (!outfile) {
197          fprintf(stderr, "Error: cannot open %s.\n", outfilename);
198          exit(-1);
199      }
200  }
201
202  if(print_version_option) {
203      fprintf(outfile, "grep static fixed-string parallel bit streams.: March 2014\n");
204  }
205
206  ATTRIBUTE_SIMD_ALIGN char buffer[SEGMENT_SIZE];
207  // Pablo transpose.do_block(), transpose.do_final_block()
208  // expect 'byte_data' and 'basis' names as input and output arguments.
209  char * byte_data = buffer;
210
211  // Scanners
212  BitStreamScanner<BitBlock, ScanWord, ScanWord, SEGMENT_BLOCKS> matches_scanner;
213  BitStreamScanner<BitBlock, ScanWord, ScanWord, SEGMENT_BLOCKS> line_starts_scanner;
214  BitStreamScanner<BitBlock, ScanWord, ScanWord, SEGMENT_BLOCKS> line_ends_scanner;
215
216  // Segment-at-a-time processing.
217  while(!feof(infile)) {
218    // Read Stream in SEGMENT_SIZE - strlen("needle") byte chunks.
219    bytes_read      = fread(buffer + copy_back_size, 1, SEGMENT_SIZE - copy_back_size, infile);
220    bytes_avail     = bytes_read + copy_back_size;
221    bytes_remaining = bytes_avail;
222   
223//    if(feof(infile))
224//        && (0 == bytes_remaining)) {
225//        if(infile) { fclose(infile); infile=NULL;}
226//        if(outfile) { fclose(outfile); outfile=NULL;}
227//        break;
228//    }
229   
230    if(ferror(infile)) { perror( "io error" ); exit(1); }
231
232    // Process full segment.
233   
234    //assert(("fread exceeded segment size.", bytes_avail <= SEGMENT_SIZE));
235   
236    if (bytes_remaining == SEGMENT_SIZE) { // (bytes_remaining >= SEGMENT_SIZE)
237   
238      block_base      = 0;     
239       
240      if(only_matching) { 
241        matches_scanner.init();
242      }
243     
244      if(!only_matching) {
245        line_starts_scanner.init();
246        line_ends_scanner.init();
247      }
248
249      for(block_index = 0;
250          block_index < SEGMENT_BLOCKS;
251          block_index++, block_base+=BLOCK_SIZE) {
252
253        byte_data = &buffer[block_base];
254       
255        //Compiled to 'do_block()' calls.
256        @block_stmts
257
258        if(only_matching) { 
259          matches_scanner.load_block(output.match_follows, block_index);
260        }
261
262        if(!only_matching) {
263            line_starts_scanner.load_block(output.line_starts, block_index);
264            line_ends_scanner.load_block(output.line_ends, block_index);
265        }
266      }
267   
268      if(only_matching) {
269        while(matches_scanner.has_next()) {
270          match_offset = matches_scanner.scan_to_next() - pattern_size;
271          if(byte_offset) {
272              int match_stream_offset = stream_base + match_offset;
273              fprintf(outfile, "%d:", match_stream_offset);
274          } 
275         
276          // KH: Lookahead.
277          fwrite(&buffer[match_offset], 1, pattern_size, outfile);
278         
279          //fprintf(outfile, "%s\n", fixed_pattern);
280          fprintf(outfile, "\n");
281        }
282       
283        copy_back_size      = pattern_size + 1;           
284        copy_back_offset    = bytes_avail - copy_back_size;           
285      }
286 
287      if(!only_matching) {
288
289        assert(("Line length exceeds segment size.", line_ends_scanner.has_next() && line_starts_scanner.has_next())); 
290         
291        //if(has_line_start) {
292            line_final_start_offset = line_starts_scanner.get_final_pos(); 
293        //}
294        //if(has_line_end) {
295            line_final_end_offset = line_ends_scanner.get_final_pos(); 
296        //}
297           
298        // if(!has_line_start && !has_line_end) {/* Set flag to buffer entire segment. */;}
299         
300        while(line_starts_scanner.has_next() && line_ends_scanner.has_next()) {
301             
302          line_start_offset  = line_starts_scanner.scan_to_next();
303          line_end_offset    = line_ends_scanner.scan_to_next();
304             
305          if(byte_offset) {
306            fprintf(outfile, "%d:", stream_base + line_start_offset);
307          } 
308             
309          fwrite(&buffer[line_start_offset], 1, line_end_offset - line_start_offset + 1, outfile);
310        }
311       
312        copy_back_offset   = (line_final_start_offset > line_final_end_offset) ? line_final_start_offset : (line_final_end_offset + 1) ;
313        copy_back_size     = bytes_avail - copy_back_offset;   
314
315        assert(("copy_back_offset", (copy_back_offset >= 0)));
316        assert(("copy_back_offset", (copy_back_offset <= bytes_avail)));           
317        assert(("copy_back_size", (copy_back_size >= 0)));
318        assert(("copy_back_size", (copy_back_size < SEGMENT_SIZE)));
319       
320      } 
321     
322      bytes_remaining -= SEGMENT_SIZE;
323    }
324   
325    // Process a partial segment.
326    if(bytes_remaining > 0) {
327               
328        block_index = 0;   
329        block_base  = 0;   
330       
331        if(only_matching) {
332          matches_scanner.init();
333        }
334       
335        if(!only_matching) {
336          line_starts_scanner.init();
337          line_ends_scanner.init();
338        }
339       
340        // Process full blocks.
341        while (bytes_remaining >= BLOCK_SIZE) {
342          byte_data = &buffer[block_base];
343         
344          // Compiler 'do_block()' calls.
345          @block_stmts
346   
347          if(only_matching) {
348            matches_scanner.load_block(output.match_follows, block_index);
349          }       
350         
351          if(!only_matching) {
352            line_starts_scanner.load_block(output.line_starts, block_index);
353            line_ends_scanner.load_block(output.line_ends, block_index);
354          }
355   
356          block_base += BLOCK_SIZE;
357          bytes_remaining -= BLOCK_SIZE;
358          block_index++;
359       }
360
361       // Process a partial final block. // KH: Not required.     
362       BitBlock EOF_mask = bitblock::srl(simd<1>::constant<1>(), convert(BLOCK_SIZE - bytes_remaining));   
363       byte_data = &buffer[block_base];
364         
365       // Compiler 'do_final_block()' calls.
366       @final_block_stmts
367       
368       if(only_matching) {
369          matches_scanner.load_block(output.match_follows & EOF_mask, block_index);
370       }
371         
372       if(!only_matching) {   
373         line_starts_scanner.load_block(output.line_starts & EOF_mask, block_index);
374         line_ends_scanner.load_block(output.line_ends & EOF_mask, block_index);           
375       }
376
377       if(only_matching) {
378          while(matches_scanner.has_next()) {
379            match_offset = matches_scanner.scan_to_next() - pattern_size;
380            if(byte_offset) {
381                int match_stream_offset = stream_base + match_offset;
382                fprintf(outfile, "%d:", match_stream_offset);
383            }
384           
385            // KH: Lookahead.
386            fwrite(&buffer[match_offset], 1, pattern_size, outfile);
387            fprintf(outfile, "\n");
388          }
389         
390          copy_back_size      = pattern_size + 1;           
391          copy_back_offset    = bytes_avail - copy_back_size;             
392        }
393     
394        if(!only_matching) {
395           
396            assert(("Line length exceeds segment size.", line_ends_scanner.has_next() && line_starts_scanner.has_next())); 
397                       
398            //if(has_line_start) {
399                line_final_start_offset = line_starts_scanner.get_final_pos(); 
400            //}
401            //if(has_line_end) {
402                line_final_end_offset = line_ends_scanner.get_final_pos(); 
403            //}
404               
405            // if(!has_line_start && !has_line_end) {/* Set flag to buffer entire segment. */;}
406   
407            while(line_starts_scanner.has_next() && line_ends_scanner.has_next()) {
408               
409                line_start_offset  = line_starts_scanner.scan_to_next();
410                line_end_offset    = line_ends_scanner.scan_to_next();
411               
412                if(byte_offset) {
413                    fprintf(outfile, "%d:", stream_base + line_start_offset);
414                } 
415               
416                fwrite(&buffer[line_start_offset], 1, line_end_offset - line_start_offset + 1, outfile);
417            }
418
419            copy_back_offset   = (line_final_start_offset > line_final_end_offset) ? line_final_start_offset : (line_final_end_offset + 1) ;
420            copy_back_size     = bytes_avail - copy_back_offset;
421           
422            assert(("copy_back_offset", (copy_back_offset >= 0)));
423            assert(("copy_back_offset", (copy_back_offset <= bytes_avail)));           
424            assert(("copy_back_size", (copy_back_size >= 0)));
425            assert(("copy_back_size", (copy_back_size < SEGMENT_SIZE)));
426           
427        }       
428    }
429   
430    if(DEBUG) {
431        printf("bytes_avail: %d\n", bytes_avail);
432        printf("bytes_remaining: %d\n", bytes_remaining);
433        printf("copy_back_offset: %d\n", copy_back_offset);
434        printf("copy_back_size: %d\n", copy_back_size);       
435        printf("final_line_starts_offset: %d\n", line_final_start_offset);
436        printf("final_line_ends_offset: %d\n", line_final_end_offset);
437    }
438   
439    memmove(&buffer[0], &buffer[copy_back_offset], copy_back_size);
440   
441    // pablo.ScanToFirst() must clear carry-in at the start of each segment
442    classifyBytes.clear();
443    match.clear();
444    matchLines.clear();
445   
446    stream_base += bytes_avail;
447    stream_base -= copy_back_size;
448
449  }
450
451  if(infile) { fclose(infile); infile=NULL;}
452  if(outfile) { fclose(outfile); outfile=NULL;}
453 
454  return 0;
455}
Note: See TracBrowser for help on using the repository browser.