source: proto/RE/demo/grep_template_segment.cpp @ 3738

Last change on this file since 3738 was 3738, checked in by ksherdy, 4 years ago

Added tests. Added -b -o grep flags.

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