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

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

Consolidated s2k demos.

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/*
76struct Basis basis;
77*/
78
79// @ decl - Replaced with a set of C++ stream struct declarations.
80@decl
81
82// Transpostion (runtime support). Example only, defined in simd-lib/transpose.hpp.
83struct Transpose {
84
85  void do_block(char * byte_data, Basis_bits & basis_bits) {
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
94  void do_final_block(char * byte_data, Basis_bits & basis_bits, BitBlock & FEM_mask) {
95        BytePack * Byte = (BytePack *) byte_data;
96
97        s2p(Byte[0], Byte[1], Byte[2], Byte[3],
98            Byte[4], Byte[5], Byte[6], Byte[7],
99            basis_bits.bit_0, basis_bits.bit_1, basis_bits.bit_2, basis_bits.bit_3,
100            basis_bits.bit_4, basis_bits.bit_5, basis_bits.bit_6, basis_bits.bit_7);
101
102        basis_bits.bit_7 = simd_and(basis_bits.bit_7, FEM_mask);
103        basis_bits.bit_6 = simd_and(basis_bits.bit_6, FEM_mask);
104        basis_bits.bit_5 = simd_and(basis_bits.bit_5, FEM_mask);
105        basis_bits.bit_4 = simd_and(basis_bits.bit_4, FEM_mask);
106        basis_bits.bit_3 = simd_and(basis_bits.bit_3, FEM_mask);
107        basis_bits.bit_2 = simd_and(basis_bits.bit_2, FEM_mask);
108        basis_bits.bit_1 = simd_and(basis_bits.bit_1, FEM_mask);
109        basis_bits.bit_0 = simd_and(basis_bits.bit_0, FEM_mask);
110  }
111};
112
113struct Transpose transpose;
114// @ stream_stmts - Replaced with C++ stream functions declarations.
115@stream_stmts
116
117// Segment-at-a-time parameters.
118int bytes_read              = 0;
119int bytes_avail             = 0;  // wrt current segment
120int bytes_remaining         = 0;
121
122int copy_back_size          = 0;
123int copy_back_offset        = 0;
124
125int block_index             = 0; 
126int block_base              = 0; 
127
128//int segment_index           = 0; // segment index wrt current buffer  // unused
129//int segment_base            = 0; // segment offset wrt current buffer // unused
130
131int stream_base             = 0;
132
133int match_offset            = 0; // 0-based
134int line_start_offset       = 0; 
135int line_end_offset         = 0; 
136
137int line_final_start_offset = 0; 
138int line_final_end_offset   = 0;
139
140int main(int argc, char * argv[]) {
141   
142    char * infilename, * outfilename;
143    FILE * infile, * outfile;
144       
145    int opt_code;
146    int byte_offset             = 0;
147    int count_only_option       = 0;
148    int only_matching           = 0;
149    int print_version_option    = 0;
150   
151    while ((opt_code = getopt(argc, argv, "bcov?")) != -1) {
152        switch (opt_code) {
153        case 'b':
154            byte_offset = 1;
155            break;
156        case 'c':
157            count_only_option = 1;
158            printf("Not implemented.");
159            break;
160        case 'o':
161            only_matching = 1;
162            break;           
163        case 'v':
164            print_version_option = 1;
165            break;
166        case '?':
167            printf("Usage: %s [-c] [-v] <inputfile> [<outputfile>]\n", argv[0]);
168            exit(-1);
169            break;
170        default:
171            printf ("Invalid option: %c\n", opt_code);
172            printf("Usage: %s [-c] [-v] <inputfile> [<outputfile>]\n", argv[0]);
173            exit(-1);
174        }
175    }
176   
177  if (optind >= argc) {
178    printf ("Too few arguments\n");
179    printf("Usage: %s [-c] [-v] <regex> <inputfile> [<outputfile>]\n", argv[0]);
180    exit(-1);
181  }
182     
183  infilename = argv[optind++];
184  infile = fopen(infilename, "rb");
185  if (!infile) {
186      fprintf(stderr, "Error: cannot open %s.\n", infilename);
187      exit(-1);
188  }
189
190  if(optind >= argc) {
191      outfile = stdout;
192  } else {
193      outfilename = argv[optind++];
194      if (optind != argc) {
195          printf ("Too many arguments\n");
196          printf("Usage: %s [-c] [-v] <regex> <inputfile> [<outputfile>]\n", argv[0]);
197          exit(-1);
198      }
199      outfile = fopen(outfilename, "wb");
200      if (!outfile) {
201          fprintf(stderr, "Error: cannot open %s.\n", outfilename);
202          exit(-1);
203      }
204  }
205
206  if(print_version_option) {
207      fprintf(outfile, "grep static fixed-string parallel bit streams.: March 2014\n");
208  }
209
210  ATTRIBUTE_SIMD_ALIGN char buffer[SEGMENT_SIZE];
211  // Pablo transpose.do_block(), transpose.do_final_block()
212  // expect 'byte_data' and 'basis' names as input and output arguments.
213  char * byte_data = buffer;
214
215  // Scanners
216  BitStreamScanner<BitBlock, ScanWord, ScanWord, SEGMENT_BLOCKS> matches_scanner;
217  BitStreamScanner<BitBlock, ScanWord, ScanWord, SEGMENT_BLOCKS> line_starts_scanner;
218  BitStreamScanner<BitBlock, ScanWord, ScanWord, SEGMENT_BLOCKS> line_ends_scanner;
219
220  // Segment-at-a-time processing.
221  while(!feof(infile)) {
222    // Read Stream in SEGMENT_SIZE - strlen("needle") byte chunks.
223    bytes_read      = fread(buffer + copy_back_size, 1, SEGMENT_SIZE - copy_back_size, infile);
224    bytes_avail     = bytes_read + copy_back_size;
225    bytes_remaining = bytes_avail;
226   
227//    if(feof(infile))
228//        && (0 == bytes_remaining)) {
229//        if(infile) { fclose(infile); infile=NULL;}
230//        if(outfile) { fclose(outfile); outfile=NULL;}
231//        break;
232//    }
233   
234    if(ferror(infile)) { perror( "io error" ); exit(1); }
235
236    // Process full segment.
237   
238    //assert(("fread exceeded segment size.", bytes_avail <= SEGMENT_SIZE));
239   
240    if (bytes_remaining == SEGMENT_SIZE) { // (bytes_remaining >= SEGMENT_SIZE)
241   
242      block_base      = 0;     
243       
244      if(only_matching) { 
245        matches_scanner.init();
246      }
247     
248      if(!only_matching) {
249        line_starts_scanner.init();
250        line_ends_scanner.init();
251      }
252
253      for(block_index = 0;
254          block_index < SEGMENT_BLOCKS;
255          block_index++, block_base+=BLOCK_SIZE) {
256
257        byte_data = &buffer[block_base];
258       
259        //Compiled to 'do_block()' calls.
260        @block_stmts
261
262        if(only_matching) { 
263          matches_scanner.load_block(output.match_follows, block_index);
264        }
265
266        if(!only_matching) {
267            line_starts_scanner.load_block(output.line_starts, block_index);
268            line_ends_scanner.load_block(output.line_ends, block_index);
269        }
270      }
271   
272      if(only_matching) {
273        while(matches_scanner.has_next()) {
274          match_offset = matches_scanner.scan_to_next() - pattern_size;
275          if(byte_offset) {
276              int match_stream_offset = stream_base + match_offset;
277              fprintf(outfile, "%d:", match_stream_offset);
278          } 
279         
280          // KH: Lookahead.
281          fwrite(&buffer[match_offset], 1, pattern_size, outfile);
282         
283          //fprintf(outfile, "%s\n", fixed_pattern);
284          fprintf(outfile, "\n");
285        }
286       
287        copy_back_size      = pattern_size + 1;           
288        copy_back_offset    = bytes_avail - copy_back_size;           
289      }
290 
291      if(!only_matching) {
292
293        assert(("Line length exceeds segment size.", line_ends_scanner.has_next() && line_starts_scanner.has_next())); 
294         
295        //if(has_line_start) {
296            line_final_start_offset = line_starts_scanner.get_final_pos(); 
297        //}
298        //if(has_line_end) {
299            line_final_end_offset = line_ends_scanner.get_final_pos(); 
300        //}
301           
302        // if(!has_line_start && !has_line_end) {/* Set flag to buffer entire segment. */;}
303         
304        while(line_starts_scanner.has_next() && line_ends_scanner.has_next()) {
305             
306          line_start_offset  = line_starts_scanner.scan_to_next();
307          line_end_offset    = line_ends_scanner.scan_to_next();
308             
309          if(byte_offset) {
310            fprintf(outfile, "%d:", stream_base + line_start_offset);
311          } 
312             
313          fwrite(&buffer[line_start_offset], 1, line_end_offset - line_start_offset + 1, outfile);
314        }
315       
316        copy_back_offset   = (line_final_start_offset > line_final_end_offset) ? line_final_start_offset : (line_final_end_offset + 1) ;
317        copy_back_size     = bytes_avail - copy_back_offset;   
318
319        assert(("copy_back_offset", (copy_back_offset >= 0)));
320        assert(("copy_back_offset", (copy_back_offset <= bytes_avail)));           
321        assert(("copy_back_size", (copy_back_size >= 0)));
322        assert(("copy_back_size", (copy_back_size < SEGMENT_SIZE)));
323       
324      } 
325     
326      bytes_remaining -= SEGMENT_SIZE;
327    }
328   
329    // Process a partial segment.
330    if(bytes_remaining > 0) {
331               
332        block_index = 0;   
333        block_base  = 0;   
334       
335        if(only_matching) {
336          matches_scanner.init();
337        }
338       
339        if(!only_matching) {
340          line_starts_scanner.init();
341          line_ends_scanner.init();
342        }
343       
344        // Process full blocks.
345        while (bytes_remaining >= BLOCK_SIZE) {
346          byte_data = &buffer[block_base];
347         
348          // Compiler 'do_block()' calls.
349          @block_stmts
350   
351          if(only_matching) {
352            matches_scanner.load_block(output.match_follows, block_index);
353          }       
354         
355          if(!only_matching) {
356            line_starts_scanner.load_block(output.line_starts, block_index);
357            line_ends_scanner.load_block(output.line_ends, block_index);
358          }
359   
360          block_base += BLOCK_SIZE;
361          bytes_remaining -= BLOCK_SIZE;
362          block_index++;
363       }
364
365       // Process a partial final block. // KH: Not required.     
366       BitBlock EOF_mask = bitblock::srl(simd<1>::constant<1>(), convert(BLOCK_SIZE - bytes_remaining));   
367       byte_data = &buffer[block_base];
368         
369       // Compiler 'do_final_block()' calls.
370       @final_block_stmts
371       
372       if(only_matching) {
373          matches_scanner.load_block(output.match_follows & EOF_mask, block_index);
374       }
375         
376       if(!only_matching) {   
377         line_starts_scanner.load_block(output.line_starts & EOF_mask, block_index);
378         line_ends_scanner.load_block(output.line_ends & EOF_mask, block_index);           
379       }
380
381       if(only_matching) {
382          while(matches_scanner.has_next()) {
383            match_offset = matches_scanner.scan_to_next() - pattern_size;
384            if(byte_offset) {
385                int match_stream_offset = stream_base + match_offset;
386                fprintf(outfile, "%d:", match_stream_offset);
387            }
388           
389            // KH: Lookahead.
390            fwrite(&buffer[match_offset], 1, pattern_size, outfile);
391            fprintf(outfile, "\n");
392          }
393         
394          copy_back_size      = pattern_size + 1;           
395          copy_back_offset    = bytes_avail - copy_back_size;             
396        }
397     
398        if(!only_matching) {
399           
400            assert(("Line length exceeds segment size.", line_ends_scanner.has_next() && line_starts_scanner.has_next())); 
401                       
402            //if(has_line_start) {
403                line_final_start_offset = line_starts_scanner.get_final_pos(); 
404            //}
405            //if(has_line_end) {
406                line_final_end_offset = line_ends_scanner.get_final_pos(); 
407            //}
408               
409            // if(!has_line_start && !has_line_end) {/* Set flag to buffer entire segment. */;}
410   
411            while(line_starts_scanner.has_next() && line_ends_scanner.has_next()) {
412               
413                line_start_offset  = line_starts_scanner.scan_to_next();
414                line_end_offset    = line_ends_scanner.scan_to_next();
415               
416                if(byte_offset) {
417                    fprintf(outfile, "%d:", stream_base + line_start_offset);
418                } 
419               
420                fwrite(&buffer[line_start_offset], 1, line_end_offset - line_start_offset + 1, outfile);
421            }
422
423            copy_back_offset   = (line_final_start_offset > line_final_end_offset) ? line_final_start_offset : (line_final_end_offset + 1) ;
424            copy_back_size     = bytes_avail - copy_back_offset;
425           
426            assert(("copy_back_offset", (copy_back_offset >= 0)));
427            assert(("copy_back_offset", (copy_back_offset <= bytes_avail)));           
428            assert(("copy_back_size", (copy_back_size >= 0)));
429            assert(("copy_back_size", (copy_back_size < SEGMENT_SIZE)));
430           
431        }       
432    }
433   
434    if(DEBUG) {
435        printf("bytes_avail: %d\n", bytes_avail);
436        printf("bytes_remaining: %d\n", bytes_remaining);
437        printf("copy_back_offset: %d\n", copy_back_offset);
438        printf("copy_back_size: %d\n", copy_back_size);       
439        printf("final_line_starts_offset: %d\n", line_final_start_offset);
440        printf("final_line_ends_offset: %d\n", line_final_end_offset);
441    }
442   
443    memmove(&buffer[0], &buffer[copy_back_offset], copy_back_size);
444   
445    // pablo.ScanToFirst() must clear carry-in at the start of each segment
446    classifyBytes.clear();
447    match.clear();
448    matchLines.clear();
449   
450    stream_base += bytes_avail;
451    stream_base -= copy_back_size;
452
453  }
454
455  if(infile) { fclose(infile); infile=NULL;}
456  if(outfile) { fclose(outfile); outfile=NULL;}
457 
458  return 0;
459}
Note: See TracBrowser for help on using the repository browser.