source: proto/s2k/trunk/demo/grep/src/grep_segment_at_a_time.cpp @ 4019

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

Fix grep header test.

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