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

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

Added support for segment-at-a-time processing. Match strings at follows position.

File size: 14.2 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 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; // wrt current segment
117int block_base              = 0; // ?
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    block_base      = 0;   
219   
220    //if(feof(infile)) { KH: No! OPC /*bytes_remaining--;*/ }
221    if(ferror(infile)) { perror( "io error" ); exit(1); }
222
223    // Process full segment.
224   
225    //assert(("fread exceeded segment size.", bytes_avail <= SEGMENT_SIZE));
226   
227    if (bytes_avail == SEGMENT_SIZE) { // (bytes_remaining >= SEGMENT_SIZE)
228     
229      if(only_matching) { 
230        match_scanner.init();
231      }
232     
233      if(!only_matching) {
234        line_starts_scanner.init();
235        line_ends_scanner.init();
236      }
237
238      for(block_index = 0;
239          block_index < SEGMENT_BLOCKS;
240          block_index++, block_base+=BLOCK_SIZE) {
241
242        byte_data = &buffer[block_base];
243       
244        //Compiled to 'do_block()' calls.
245        @block_stmts
246
247        if(only_matching) { 
248          match_scanner.load_block(output.matches, block_index);
249        }
250
251        if(!only_matching) {
252            line_starts_scanner.load_block(output.line_starts, block_index);
253            line_ends_scanner.load_block(output.line_ends, block_index);
254        }
255      }
256   
257      if(only_matching) {
258        while(match_scanner.has_next()) {
259          match_offset = match_scanner.scan_to_next() - pattern_size;
260          if(byte_offset) {
261              int match_stream_offset = stream_base + match_offset;
262              fprintf(outfile, "%d:", match_stream_offset);
263          } 
264         
265          // KH: Lookahead.
266          fwrite(&buffer[match_offset], 1, pattern_size, outfile);
267         
268          //fprintf(outfile, "%s\n", fixed_pattern);
269          fprintf(outfile, "\n");
270        }
271       
272        copy_back_size      = pattern_size;           
273        copy_back_offset    = bytes_avail - copy_back_size;           
274      }
275 
276      if(!only_matching) {
277
278        assert(("Line length exceeds segment size.", line_ends_scanner.has_next() && line_starts_scanner.has_next())); 
279         
280        //if(has_line_start) {
281            line_starts_final_offset = line_starts_scanner.get_final_pos(); 
282        //}
283        //if(has_line_end) {
284            line_ends_final_offset = line_ends_scanner.get_final_pos(); 
285        //}
286           
287        // if(!has_line_start && !has_line_end) {/* Set flag to buffer entire segment. */;}
288         
289        while(line_starts_scanner.has_next() && line_ends_scanner.has_next()) {
290             
291          line_start_offset  = line_starts_scanner.scan_to_next();
292          line_end_offset    = line_ends_scanner.scan_to_next();
293             
294          if(byte_offset) {
295            fprintf(outfile, "%d:", stream_base + line_start_offset);
296          } 
297             
298          fwrite(&buffer[line_start_offset], 1, line_end_offset - line_start_offset + 1, outfile);
299        }
300       
301        copy_back_offset   = (line_starts_final_offset > line_ends_final_offset) ? line_starts_final_offset : (line_ends_final_offset + 1) ;
302        copy_back_size     = bytes_avail - copy_back_offset;   
303
304      } 
305     
306      bytes_remaining -= SEGMENT_SIZE;
307    }
308   
309    // Process a partial segment.
310    if(bytes_remaining > 0) {
311
312        block_index = 0;   
313       
314        if(only_matching) {
315          match_scanner.init();
316        }
317       
318        if(!only_matching) {
319          line_starts_scanner.init();
320          line_ends_scanner.init();
321        }
322       
323        // Process full blocks.
324        while (bytes_remaining >= BLOCK_SIZE) {
325          byte_data = &buffer[block_base];
326         
327          // Compiler 'do_block()' calls.
328          @block_stmts
329   
330          if(only_matching) {
331            match_scanner.load_block(output.matches, block_index);
332          }       
333         
334          if(!only_matching) {
335            line_starts_scanner.load_block(output.line_starts, block_index);
336            line_ends_scanner.load_block(output.line_ends, block_index);
337          }
338   
339          block_base += BLOCK_SIZE;
340          bytes_remaining -= BLOCK_SIZE;
341          block_index++;
342       }
343
344       // Process a partial final block. // KH: Not required.     
345       BitBlock EOF_mask = bitblock::srl(simd<1>::constant<1>(), convert(BLOCK_SIZE - bytes_remaining));   
346       byte_data = &buffer[block_base];
347         
348       // Compiler 'do_final_block()' calls.
349       @final_block_stmts
350   
351       if(only_matching) {
352          match_scanner.load_block(output.matches & EOF_mask, block_index);
353       }
354         
355       if(!only_matching) {   
356         line_starts_scanner.load_block(output.line_starts & EOF_mask, block_index);
357         line_ends_scanner.load_block(output.line_ends & EOF_mask, block_index);           
358       }
359
360       if(only_matching) {
361          while(match_scanner.has_next()) {
362            match_offset = match_scanner.scan_to_next() - pattern_size;
363            if(byte_offset) {
364                int match_stream_offset = stream_base + match_offset;
365                fprintf(outfile, "%d:", match_stream_offset);
366            }
367           
368            // KH: Lookahead.
369            fwrite(&buffer[match_offset], 1, pattern_size, outfile);
370            //fprintf(outfile, "%s\n", fixed_pattern);
371            fprintf(outfile, "\n");
372          }
373         
374          copy_back_size      = pattern_size;           
375          copy_back_offset    = bytes_avail - copy_back_size;             
376        }
377     
378        if(!only_matching) {
379           
380            assert(("Line length exceeds segment size.", line_ends_scanner.has_next() && line_starts_scanner.has_next())); 
381                       
382            //if(has_line_start) {
383                line_starts_final_offset = line_starts_scanner.get_final_pos(); 
384            //}
385            //if(has_line_end) {
386                line_ends_final_offset = line_ends_scanner.get_final_pos(); 
387            //}
388               
389            // if(!has_line_start && !has_line_end) {/* Set flag to buffer entire segment. */;}
390   
391            while(line_starts_scanner.has_next() && line_ends_scanner.has_next()) {
392               
393                line_start_offset  = line_starts_scanner.scan_to_next();
394                line_end_offset    = line_ends_scanner.scan_to_next();
395               
396                if(byte_offset) {
397                    fprintf(outfile, "%d:", stream_base + line_start_offset);
398                } 
399               
400                fwrite(&buffer[line_start_offset], 1, line_end_offset - line_start_offset + 1, outfile);
401            }
402
403            copy_back_offset   = (line_starts_final_offset > line_ends_final_offset) ? line_starts_final_offset : (line_ends_final_offset + 1) ;
404            copy_back_size     = bytes_avail - copy_back_offset;
405        }       
406    }
407   
408    if(0) {
409        cout << "bytes_avail: " << bytes_avail << endl;
410        cout << "line_starts_final_offset: " << line_starts_final_offset << endl;
411        cout << "line_ends_final_offset: " << line_ends_final_offset << endl;
412        cout << "offset: " << copy_back_offset << ", " << "size: " << copy_back_size << endl;
413    }
414   
415    memmove(&buffer[0], &buffer[copy_back_offset], copy_back_size);
416   
417    // pablo.ScanToFirst() must clear carry-in at the start of each segment.
418    classifyBytes.clear();
419    match.clear();
420    matchLines.clear();
421   
422    stream_base += bytes_avail;
423    stream_base -= copy_back_size;
424  }
425
426  if(infile) { fclose(infile); }
427  if(outfile) { fclose(outfile); }
428 
429  return 0;
430}
Note: See TracBrowser for help on using the repository browser.