source: proto/SymbolTable/dictionary_pbgs_log_template.cpp @ 1684

Last change on this file since 1684 was 1684, checked in by vla24, 8 years ago

SymbolTable?: updated templates implementation to use BitBlockForwardIterator?. Fixed block boundary case handling for div2 grouping strategy.

File size: 14.1 KB
Line 
1#define USE_MASK_COMPARE    //Comparison using masking technique.
2
3#include "../symtab_global.h"
4#include <pbgs_log_symbol_table.h>
5
6#ifdef BUFFER_PROFILING
7        BOM_Table * parser_timer;
8
9#elif CODE_CLOCKER
10        #define NUM_EVENTS 1
11        int Events[NUM_EVENTS] = {PAPI_TOT_CYC};
12        //int Events[NUM_EVENTS] = {PAPI_L2_DCM};
13        //int Events[NUM_EVENTS] = {PAPI_TOT_CYC, PAPI_BR_MSP};
14        int cal_size = 20;
15        CC * parser_timer = new CC(Events,NUM_EVENTS,cal_size);
16#else
17        void * parser_timer;
18#endif
19
20int block_base=0;
21int buffer_base=0;
22int buffer_last;
23char * source;
24BitBlock EOF_mask = simd<1>::constant<1>();
25BitBlock elem_starts;
26int previous_block_last_elem_start;
27BytePack hashvalues[2];
28
29vector <int> gids;
30PBGSLogSymbolTable pbgs_symbol_table;
31
32@global
33
34static inline void s2p_do_block(BytePack U8[], Basis_bits & basis_bits);
35static inline void s2p_do_final_block(BytePack U8[], Basis_bits & basis_bits, BitBlock EOF_mask);
36static inline void postprocess_do_block(Dictionary& dictionary, Hash_data hash_data);
37
38void do_process(FILE *infile, FILE *outfile);
39
40template <int L> static inline void validate_block_length_grouping(BitBlockForwardIterator & start, int block_base);
41
42static inline int ScanBackwardPos(BitBlock * block, int pos);
43static inline int compute_hash_value (int lgth, int start);
44template <int L> static inline int ElemEnd_grouping(int pos, int length);
45template <int L> static inline int StreamScanLengthGrouping(ScanBlock * stream, int blk_count);
46
47int main(int argc, char * argv[]) {
48        char * infilename, * outfilename;
49        FILE *infile, *outfile;
50        struct stat fileinfo;
51
52        if (argc < 2) {
53                printf("Usage: %s <filename> [<outputfile>]\n", argv[0]);
54                exit(-1);
55        }
56
57        infilename = argv[1];
58        stat(infilename, &fileinfo);
59        infile = fopen(infilename, "rb");
60        if (!infile) {
61                fprintf(stderr, "Error: cannot open %s for input.\n", infilename);
62                exit(-1);
63        }
64
65        if (argc < 3) outfile = stdout;
66        else {
67                outfilename = argv[2];
68                outfile = fopen(outfilename, "wb");
69                if (!outfile) {
70                        fprintf(stderr, "Error: cannot open %s for writing.\n", outfilename);
71                        exit(-1);
72                }
73        }
74
75//      PERF_SEC_BIND(1);
76
77        PERF_SEC_INIT(parser_timer);
78
79        do_process(infile, outfile);
80
81        PERF_SEC_DUMP(parser_timer);
82
83        PERF_SEC_DESTROY(parser_timer);
84
85        fclose(infile);
86        fclose(outfile);
87
88        return(0);
89}
90
91/* s2p Definitions */
92static inline void s2p_do_block(BytePack U8[], Basis_bits & basis_bits) {
93  s2p(U8[0], U8[1], U8[2], U8[3], U8[4], U8[5], U8[6], U8[7],
94        basis_bits.bit_0, basis_bits.bit_1, basis_bits.bit_2, basis_bits.bit_3, basis_bits.bit_4, basis_bits.bit_5, basis_bits.bit_6, basis_bits.bit_7);
95}
96
97static inline void s2p_do_final_block(BytePack U8[], Basis_bits & basis_bits, BitBlock EOF_mask) {
98  s2p_do_block(U8, basis_bits);
99  basis_bits.bit_0 = simd_and(basis_bits.bit_0, EOF_mask);
100  basis_bits.bit_1 = simd_and(basis_bits.bit_1, EOF_mask);
101  basis_bits.bit_2 = simd_and(basis_bits.bit_2, EOF_mask);
102  basis_bits.bit_3 = simd_and(basis_bits.bit_3, EOF_mask);
103  basis_bits.bit_4 = simd_and(basis_bits.bit_4, EOF_mask);
104  basis_bits.bit_5 = simd_and(basis_bits.bit_5, EOF_mask);
105  basis_bits.bit_6 = simd_and(basis_bits.bit_6, EOF_mask);
106  basis_bits.bit_7 = simd_and(basis_bits.bit_7, EOF_mask);
107}
108
109
110static inline int ScanBackwardPos(BitBlock * block, int pos)
111{
112    BitBlock s = block[0];
113    BitBlock temp = simd_and( s, simd_not(simd<128>::sll(simd<2>::constant<3>(), convert(pos))) );
114
115    if (bitblock_has_bit(temp))
116    {
117        // sizeof (BitBlock)*8 - cbzl( s & ~(~0 << pos)) - 1;
118        return sizeof(BitBlock)*8 - count_reverse_zeroes (temp) - 1;
119    }
120    else
121    {
122        //handle boundary case
123#if DEBUG
124        printf ("%s | block boundary case, return %i\n", __FUNCTION__, previous_block_last_elem_start - 1);
125#endif
126        return previous_block_last_elem_start - 1;
127    }
128}
129
130static inline int compute_hash_value (int lgth, int start)
131{
132    unsigned int offset_bit = start + 128;
133    uint64_t stream = *((uint64_t*)(((uint32_t*)hashvalues)+(offset_bit>>5)));
134    return stream >> (offset_bit & 0x1F) & ~(~0 << lgth);
135}
136
137template <int L>
138static inline int ElemEnd_grouping(int pos, int length) {
139    return 0;
140}
141
142// length = 1
143template <>
144inline int ElemEnd_grouping<1>(int pos, int length) {
145    int start = block_base + pos - length;
146    int hashvalue = compute_hash_value(length, start - block_base);
147    int gid = pbgs_symbol_table.Lookup_or_Insert_Name_1(source + start, hashvalue);
148    gids.push_back(gid);
149#if DEBUG
150    int L = length;
151    int end = start - L;
152    char* symbol = new char[L+1];
153    strncpy ( symbol, source + start, L );
154    symbol[L] ='\0';
155    printf ("%s | start: %i[%i] | end: %i[%i] | gid: %i | hashvalue: %i | symbol: %s\n", __FUNCTION__, start, start-buffer_base, end, end-buffer_base, gid, hashvalue, symbol );
156    delete symbol; symbol = 0;
157#endif
158    return 0;
159}
160
161// length = 2
162template <>
163inline int ElemEnd_grouping<2>(int pos, int length) {
164    int start = block_base + pos - length;
165    int hashvalue = compute_hash_value(length, start - block_base);
166    int gid = pbgs_symbol_table.Lookup_or_Insert_Name_2(source + start, hashvalue);
167    gids.push_back(gid);
168#if DEBUG
169    int L = 2;
170    int end = start - L;
171    char* symbol = new char[L+1];
172    strncpy ( symbol, source + start, L );
173    symbol[L] ='\0';
174    printf ("%s | start: %i[%i] | end: %i[%i] | gid: %i | hashvalue: %i | symbol: %s\n", __FUNCTION__, start, start-buffer_base, end, end-buffer_base, gid, hashvalue, symbol );
175    delete symbol; symbol = 0;
176#endif
177    return 0;
178}
179
180
181// length in [3,4]
182template <>
183inline int ElemEnd_grouping<4>(int pos, int L) {
184    int start = pos + block_base;
185    int hashvalue = compute_hash_value(L, pos);
186    int gid = pbgs_symbol_table.Lookup_or_Insert_Name_4(source + start, hashvalue, L);
187    gids.push_back(gid);
188#if DEBUG
189    int end = start + L;
190    char* symbol = new char[L+1];
191    strncpy ( symbol, source + start, L );
192    symbol[L] ='\0';
193    printf ("%s | start: %i[%i] | end: %i[%i] | gid: %i | hashvalue: %i | symbol: %s\n", __FUNCTION__, start, start-buffer_base, end, end-buffer_base, gid, hashvalue, symbol );
194    delete symbol; symbol = 0;
195#endif
196    return 0;
197}
198
199// length in [5,8]
200template <>
201inline int ElemEnd_grouping<8>(int pos,  int L) {
202    int start = pos + block_base;
203    int hashvalue = compute_hash_value(L, pos);
204    int gid = pbgs_symbol_table.Lookup_or_Insert_Name_8(source + start, hashvalue, L);
205    gids.push_back(gid);
206#if DEBUG
207    int end = start + L;
208    char* symbol = new char[L+1];
209    strncpy ( symbol, source + start, L );
210    symbol[L] ='\0';
211    printf ("%s | start: %i[%i] | end: %i[%i] | gid: %i | hashvalue: %i | symbol: %s\n", __FUNCTION__, start, start-buffer_base, end, end-buffer_base, gid, hashvalue, symbol );
212    delete symbol; symbol = 0;
213#endif
214    return 0;
215}
216
217// length in [9,16]
218template <>
219inline int ElemEnd_grouping<16>(int pos, int L) {
220    int start = pos + block_base;
221    int hashvalue = compute_hash_value(L, pos);
222    int gid = pbgs_symbol_table.Lookup_or_Insert_Name_16(source + start, hashvalue, L);
223    gids.push_back(gid);
224#if DEBUG
225    int end = start + L;
226    char* symbol = new char[L+1];
227    strncpy ( symbol, source + start, L );
228    symbol[L] ='\0';
229    printf ("%s | start: %i[%i] | end: %i[%i] | gid: %i | hashvalue: %i | symbol: %s\n", __FUNCTION__, start, start-buffer_base, end, end-buffer_base, gid, hashvalue, symbol );
230    delete symbol; symbol = 0;
231#endif
232    return 0;
233}
234
235// length > 16
236template <>
237inline int ElemEnd_grouping<17>(int pos, int lgth) {
238    int start = pos + block_base;
239    int hashvalue = compute_hash_value(lgth, start - block_base);
240    int gid = 0;
241
242//    if (lgth < 32)
243//    {
244//      gid = pbgs_symbol_table.Lookup_or_Insert_Name_32(source + start, hashvalue, lgth);
245//    }
246//    else
247    {
248        gid = pbgs_symbol_table.Lookup_or_Insert_Name(source + start, hashvalue, lgth);
249    }
250    gids.push_back(gid);
251#if DEBUG
252    char* symbol = new char[lgth+1];
253    strncpy ( symbol, source + start, lgth );
254    symbol[lgth] ='\0';
255    printf ("%s | start: %i[%i] | lgth: %i | hashvalue: %i | gid: %i | symbol: %s\n", __FUNCTION__, start, start - block_base, lgth, hashvalue, gid, symbol);
256#endif
257    return 0;
258}
259
260// L = 4, pass in bitstream for symbols length [3,4]
261// L = 8, pass in bitstream for symbols length [5,8]
262// L = 16, pass in bitstream for symbols length [9,16]
263// L = 17, pass in bitstream for symbols length longer than 16
264template <int L>
265static inline void validate_block_length_grouping(BitBlockForwardIterator & start, int block_base) {
266
267    BitBlockForwardIterator end;
268    int end_pos, start_pos, length;
269
270    while(start != end) {
271        end_pos = /*block_base + */*start;
272        start_pos = ScanBackwardPos (&elem_starts, end_pos);
273        length = end_pos - start_pos;
274        ElemEnd_grouping<L>(start_pos, length);
275        start++;
276    }
277}
278
279// pass in bitstream for symbols length 1
280template <>
281inline void validate_block_length_grouping<1>(BitBlockForwardIterator & start, int block_base) {
282
283    BitBlockForwardIterator end;
284    int end_pos, start_pos, length;
285
286    while(start != end) {
287        end_pos = /*block_base + */*start;
288        start_pos = ScanBackwardPos (&elem_starts, end_pos);
289        length = end_pos - start_pos;
290        ElemEnd_grouping<1>(end_pos, 1);
291        start++;
292    }
293}
294
295// pass in bitstream for symbols length 2
296template <>
297inline void validate_block_length_grouping<2>(BitBlockForwardIterator & start, int block_base) {
298
299    BitBlockForwardIterator end;
300    int end_pos, start_pos, length;
301
302    while(start != end) {
303        end_pos = /*block_base + */*start;
304        start_pos = ScanBackwardPos (&elem_starts, end_pos);
305        length = end_pos - start_pos;
306        ElemEnd_grouping<2>(end_pos, 2);
307        start++;
308    }
309}
310
311static inline void postprocess_do_block(Dictionary& dictionary, Hash_data hash_data){
312
313    elem_starts = dictionary.Word_starts;
314    hashvalues[1] = hash_data.Hash_value;
315
316    if ( bitblock_has_bit(dictionary.Word_ends_1) )
317    {
318        BitBlockForwardIterator iter_length_grouping_1(&dictionary.Word_ends_1);
319        validate_block_length_grouping<1>(iter_length_grouping_1, block_base);
320    }
321
322    if ( bitblock_has_bit(dictionary.Word_ends_2) )
323    {
324        BitBlockForwardIterator iter_length_grouping_2(&dictionary.Word_ends_2);
325        validate_block_length_grouping<2>(iter_length_grouping_2, block_base);
326    }
327
328    if ( bitblock_has_bit(dictionary.Word_ends_3_to_4) )
329    {
330        BitBlockForwardIterator iter_length_grouping_4(&dictionary.Word_ends_3_to_4);
331        validate_block_length_grouping<4>(iter_length_grouping_4, block_base);
332    }
333
334    if ( bitblock_has_bit(dictionary.Word_ends_5_to_8) )
335    {
336        BitBlockForwardIterator iter_length_grouping_8(&dictionary.Word_ends_5_to_8);
337        validate_block_length_grouping<8>(iter_length_grouping_8, block_base);
338    }
339
340    if ( bitblock_has_bit(dictionary.Word_ends_9_to_16) )
341    {
342        BitBlockForwardIterator iter_length_grouping_16(&dictionary.Word_ends_9_to_16);
343        validate_block_length_grouping<16>(iter_length_grouping_16, block_base);
344    }
345
346    if ( bitblock_has_bit(dictionary.Word_ends_17_and_longer) )
347    {
348        BitBlockForwardIterator iter_length_grouping_remaining(&dictionary.Word_ends_17_and_longer);
349        validate_block_length_grouping<17>(iter_length_grouping_remaining, block_base);
350    }
351
352    // Store the last starting position in case we hit boundary case
353    previous_block_last_elem_start = - count_reverse_zeroes (elem_starts);
354
355    //copy current hash value data as previous one.
356    memmove (&hashvalues[0], &hashvalues[1], 16);
357}
358
359static inline void print_GIDS()
360{
361    int span_count = gids.size();
362    for(int i=0;i<span_count;i++) {
363             cout << gids[i] << " ";
364    }
365    cout << endl;
366}
367
368void do_process(FILE *infile, FILE *outfile) {
369
370@decl
371
372  int buf_pos = 0;
373  int block_pos = 0;
374  int errpos = 0;
375  int chars_avail = 0;
376  int check_pos = 0;
377  int chars_read = 0;
378  BytePack buf[(BUFFER_SIZE+BLOCK_SIZE+OVERLAP_BUFSIZE*2)/sizeof(SIMD_type)];
379
380  char * srcbuf = ((char *) buf) + OVERLAP_BUFSIZE;
381  buffer_base = buf_pos;
382  source = srcbuf;
383
384  chars_read = fread((void *)srcbuf, 1, BUFFER_SIZE + OVERLAP_BUFSIZE, infile);
385  chars_avail = chars_read;
386  if (chars_avail > BUFFER_SIZE) chars_avail = BUFFER_SIZE;
387
388  Entity_Info * e = new Entity_Info;
389  e->AnalyzeSignature((unsigned char *)srcbuf);
390
391  if (e->content_start != 0) {
392        memmove(&srcbuf[0], &srcbuf[e->content_start], chars_read - e->content_start);
393        buf_pos = e->content_start;
394        buffer_base = buf_pos;
395        if (chars_avail == BUFFER_SIZE) {
396                chars_read = chars_read - e->content_start +
397                             fread(&srcbuf[chars_read-e->content_start], 1, e->content_start, infile);
398                chars_avail = chars_read;
399                if (chars_avail > BUFFER_SIZE) chars_avail = BUFFER_SIZE;
400        }
401        else {
402          chars_read -=e->content_start;
403          chars_avail -=e->content_start;
404        }
405  }
406
407@stream_stmts
408
409/* Full Buffers */
410
411    while (chars_avail == BUFFER_SIZE) {
412      PERF_SEC_START(parser_timer);
413      for (int blk = 0; blk < SEGMENT_BLOCKS; blk++) {
414          block_base = blk*BLOCK_SIZE;
415          s2p_do_block((BytePack *) &srcbuf[block_base], basis_bits);
416          @block_stmts
417          postprocess_do_block(dictionary, hash_data);
418      }
419      PERF_SEC_END(parser_timer, chars_avail);
420           
421      int bytes_left = chars_read - chars_avail;
422      memmove(buf, &srcbuf[BUFFER_SIZE - OVERLAP_BUFSIZE], bytes_left + OVERLAP_BUFSIZE);
423      chars_read = fread(&srcbuf[bytes_left],1, BUFFER_SIZE + OVERLAP_BUFSIZE - bytes_left, infile) + bytes_left;
424      chars_avail = chars_read;
425      if (chars_avail > BUFFER_SIZE) chars_avail = BUFFER_SIZE;
426      buf_pos += chars_avail;
427      buffer_base = buf_pos;
428    }
429/* Final Partial Buffer */
430    PERF_SEC_START(parser_timer);
431
432    block_pos = 0;
433    int remaining = chars_avail;
434/* Full Blocks */
435    while (remaining >= BLOCK_SIZE) {
436          block_base = block_pos;
437          s2p_do_block((BytePack *) &srcbuf[block_pos], basis_bits);
438          @block_stmts
439          postprocess_do_block(dictionary, hash_data);
440          block_pos += BLOCK_SIZE;
441          remaining -= BLOCK_SIZE;
442    }
443    block_base = block_pos;
444    if (remaining > 0 || @any_carry) {
445          EOF_mask = bitblock::srl(simd<1>::constant<1>(), convert(BLOCK_SIZE-remaining));
446          s2p_do_final_block((BytePack *) &srcbuf[block_pos], basis_bits, EOF_mask);
447          @final_block_stmts
448          postprocess_do_block(dictionary, hash_data);
449    }
450    buf_pos += chars_avail;
451    buffer_base = buf_pos;
452
453    PERF_SEC_END(parser_timer, chars_avail);
454
455#if DEBUG
456//    print_GIDS();
457    pbgs_symbol_table.Print_Symbol_Table_Distribution();
458#endif
459}
Note: See TracBrowser for help on using the repository browser.