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

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

Added grep s2k target.

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