source: trunk/symbol_table/src/symbol_table.hpp @ 2274

Last change on this file since 2274 was 2274, checked in by ksherdy, 7 years ago

Updated svn:externals.

File size: 16.7 KB
Line 
1/*
2 * symbol_table.hpp
3 * Created on: 18-December-2011
4 * Author: Ken Herdy
5 *
6 * BLOCK_SIZE - Register bit width.
7 * Block - BLOCK_SIZE contiguous bytes.
8 * Segment - Array of blocks.
9 *
10 * Set of Parallel Data Segments i.e. data segments with values in 1-1.
11 *
12 *  raw data buffer
13 *  symbol starts markers
14 *  set of length groups follows markers G1, G2, ... , Gk
15 *
16 * for each block B in the set of parallel data segments
17 *   for each length group G in B
18 *     for each symbol marker follows position p in G
19 *        resolve symbol global identifier gid at p
20 *        write symbol gid at position p in gid output array
21 *
22 */
23#ifndef ID_SYMBOL_TABLE_TEMPLATE_HPP
24#define ID_SYMBOL_TABLE_TEMPLATE_HPP
25
26#include <simd-lib/buffer.hpp>
27#include <simd-lib/bitblock_iterator.hpp>
28#include <simd-lib/bitblock_scan.hpp>
29#include "strategy_types.hpp"
30#include "gid.hpp"
31#include "hash_table.hpp"
32#include <cstdlib>
33#include <vector>
34using namespace std;
35
36#ifdef ID_SYMBOL_TABLE_TEMPLATE_HPP_DEBUG
37static void print_symbol_debug(gid_type gid, const uint8_t buffer [], const int32_t spos, const uint32_t fpos, const uint32_t lgth) {
38        cout << "{Symbol:{";
39        cout << "GID:" << gid;
40        cout << ",Length:" << lgth;
41        cout << ",Value:'" << string((char *)&(buffer[spos]), lgth) << "'";
42        cout << ",Start:" << spos;
43        cout << ",Follows:" << fpos;
44        cout << "}}" << endl;
45}
46#endif
47
48///////////////////////////////////////////////////////////////////////////
49// do_block - reverse bit scans fixed length symbols and resolve GIDs.
50//
51// Precondition: For each symbol follow marker there exists a corresponding
52//               symbol start marker.
53///////////////////////////////////////////////////////////////////////////
54template<class GIDS, class HASH_TABLE>
55void do_block(uint32_t blk_offset,
56              HASH_TABLE & h_table,
57              BitBlock follows,
58              uint8_t buffer [], const uint32_t lgth,
59              uint8_t h0 [], uint8_t h1 [], const uint32_t h_block_size,
60              GIDS & gids, GIDFactory & gid_factory, GIDData & gid_data);
61
62///////////////////////////////////////////////////////////////////////////
63// do_block - reverse bit scans variable length symbols and resolve GIDs.
64//
65// Precondition: For each symbol follow marker there exists a corresponding
66//               symbol start marker.
67///////////////////////////////////////////////////////////////////////////
68template<class GIDS, class HASH_TABLE>
69void do_block(uint32_t blk_offset,
70              HASH_TABLE & h_table,
71              BitBlock starts [], BitBlock follows [],
72              uint8_t buffer [],
73              uint8_t h0 [], uint8_t h1 [], const uint32_t h_block_size,
74              GIDS & gids, GIDFactory & gid_factory, GIDData & gid_data);
75
76///////////////////////////////////////////////////////////////////////////
77// GID container - An array of gids.
78///////////////////////////////////////////////////////////////////////////
79template<uint32_t SIZE>
80class gid {
81public:
82    gid_type at[SIZE];
83    //vector<BitBlock> gids_idx;   // gids index
84};
85
86
87template<class GIDS, class ALLOCATOR>
88class symbol_table {
89public:
90        symbol_table()/*:hash_table_1(256)*/{}
91        ~symbol_table() {
92//      hash_table_x.print_table();
93#ifdef HASH_TABLE_HPP_DEBUG
94//      hash_table_x.print_diagnostics();
95#endif
96        }
97
98        void resolve(uint8_t buffer [], Groups groups [],  BitBlock starts [], BitBlock follows_0 [],
99                                 BitBlock h0 [], BitBlock h1 [], uint32_t segment_blocks, GIDS & gids) {
100
101                        for(uint32_t blk = 0; blk < segment_blocks; blk++) {
102                                const uint32_t blk_offset = blk * BLOCK_SIZE;
103                                resolve(blk_offset, &buffer[blk_offset], groups[blk], &starts[blk], &h0[blk], &h1[blk], gids);
104                        }
105        }
106
107        IDISA_ALWAYS_INLINE void resolve(uint32_t blk_offset, uint8_t buffer [], Groups & groups,  BitBlock starts[],
108                                 BitBlock * h0, BitBlock * h1, GIDS & gids) {
109
110                        ///////////////////////////////////////////////////////////////////////////////
111                        // Byte Space Hash (Fixed Length)
112                        ///////////////////////////////////////////////////////////////////////////////
113                        #define BYTE_HASH_FIXED(GROUP_STRATEGY, HASH_STRATEGY, LGTH) \
114                                if(bitblock::any(groups.follows_##LGTH)) { \
115                                        do_block<GIDS, GROUP_STRATEGY##_hash_table <LGTH, GROUP_STRATEGY, HASH_STRATEGY, ALLOCATOR> > \
116                                                (blk_offset, \
117                                                 hash_table_##LGTH, \
118                                                 groups.follows_##LGTH, \
119                                                 buffer, LGTH, /* buffer, symbol length */ \
120                                                 buffer, buffer, BLOCK_SIZE, /* h0, h1, hash block size (bits) */ \
121                                                 gids, this->gid_factory, this->gid_data); \
122                                }
123
124                        /////////////////////////////////////////////////////////////////////////////
125                        // Byte Space Variable Lengths (groups contain variable lengths)
126                        ///////////////////////////////////////////////////////////////////////////////
127                        #define BYTE_HASH_VARIABLE(GROUP_STRATEGY, HASH_STRATEGY, LGTH) \
128                                if(bitblock::any(groups.follows_##LGTH)) { \
129                                        do_block<GIDS, GROUP_STRATEGY##_hash_table <LGTH, GROUP_STRATEGY, HASH_STRATEGY, ALLOCATOR> > \
130                                                (blk_offset, \
131                                                 hash_table_##LGTH, \
132                                                 starts, \
133                                                 &groups.follows_##LGTH, \
134                                                 buffer, \
135                                                 buffer, buffer, BLOCK_SIZE, /* h0, h1, hash block size (bits) */ \
136                                                 gids, this->gid_factory, this->gid_data); \
137                                }
138
139
140                        ///////////////////////////////////////////////////////////////////////////////
141                        // Bit Space Hash (Fixed Length)
142                        ///////////////////////////////////////////////////////////////////////////////
143                        #define BIT_HASH_FIXED(GROUP_STRATEGY, HASH_STRATEGY, LGTH) \
144                                if(bitblock::any(groups.follows_##LGTH)) { \
145                                        do_block<GIDS, GROUP_STRATEGY##_hash_table <LGTH, GROUP_STRATEGY, HASH_STRATEGY, ALLOCATOR> > \
146                                                (blk_offset, \
147                                                 hash_table_##LGTH, \
148                                                 groups.follows_##LGTH, \
149                                                 buffer, LGTH, \
150                                                 (uint8_t *)h0, (uint8_t *)h1, (BLOCK_SIZE / 8), \
151                                                 gids, this->gid_factory, this->gid_data); \
152                                }
153
154                        /////////////////////////////////////////////////////////////////////////////
155                        // Byte Space Variable Lengths (groups contain variable lengths)
156                        ///////////////////////////////////////////////////////////////////////////////
157                        #define BIT_HASH_VARIABLE(GROUP_STRATEGY, HASH_STRATEGY, LGTH) \
158                                if(bitblock::any(groups.follows_##LGTH)) { \
159                                        do_block<GIDS, GROUP_STRATEGY##_hash_table <LGTH, GROUP_STRATEGY, HASH_STRATEGY, ALLOCATOR> > \
160                                                (blk_offset, \
161                                                 hash_table_##LGTH, \
162                                                 starts, \
163                                                 &groups.follows_##LGTH, \
164                                                 buffer, \
165                                                 (uint8_t *)h0, (uint8_t *)h1, (BLOCK_SIZE / 8), /* h0, h1, hash block size (bits) */ \
166                                                 gids, this->gid_factory, this->gid_data); \
167                                }
168
169                        ///////////////////////////////////////////////////////////////////////////////
170                        // WARNING: BYTE_HASH max 8 bytes under the shift XOR hash approach of hash.hpp
171                        //     ---> (id,7),(div2,6),(logbase2,4)
172                        ///////////////////////////////////////////////////////////////////////////////
173                        #ifdef ID_STRATEGY
174                            BYTE_HASH_FIXED(id,byte,1);
175                            BYTE_HASH_FIXED(id,byte,2);
176                            BYTE_HASH_FIXED(id,byte,3);
177                            BYTE_HASH_FIXED(id,byte,4);
178                            BYTE_HASH_FIXED(id,byte,5);
179                            BYTE_HASH_FIXED(id,byte,6);
180                            BYTE_HASH_FIXED(id,byte,7);
181                            BIT_HASH_FIXED(id,bit,8);
182                            BIT_HASH_FIXED(id,bit,9);
183                            BIT_HASH_FIXED(id,bit,10);
184                            BIT_HASH_FIXED(id,bit,11);
185                            BIT_HASH_FIXED(id,bit,12);
186                            BIT_HASH_FIXED(id,bit,13);
187                            BIT_HASH_FIXED(id,bit,14);
188                            BIT_HASH_FIXED(id,bit,15);
189                            BIT_HASH_FIXED(id,bit,16);
190                            BIT_HASH_VARIABLE(id,bit,0);
191                        #elif DIV2_STRATEGY
192                            BYTE_HASH_FIXED(div2,byte,2);
193                            BYTE_HASH_FIXED(div2,byte,4);
194                            BYTE_HASH_FIXED(div2,byte,6);
195                            BIT_HASH_FIXED(div2,bit,8);
196                            BIT_HASH_FIXED(div2,bit,10);
197                            BIT_HASH_FIXED(div2,bit,12);
198                            BIT_HASH_FIXED(div2,bit,14);
199                            BIT_HASH_FIXED(div2,bit,16);
200                            BIT_HASH_VARIABLE(id,bit,0);
201                        #elif LOGBASE2_STRATEGY
202                            BYTE_HASH_VARIABLE(logbase2,byte,1);
203                            BYTE_HASH_VARIABLE(logbase2,byte,2);
204                            BYTE_HASH_VARIABLE(logbase2,byte,4);
205                            BIT_HASH_VARIABLE(logbase2,bit,8);
206                            BIT_HASH_VARIABLE(logbase2,bit,16);
207                            BIT_HASH_VARIABLE(id,bit,0);
208                        #elif DIV2_LOGBASE2_STRATEGY
209                            BYTE_HASH_FIXED(div2,byte,2);
210                            BYTE_HASH_FIXED(div2,byte,4);
211                            BYTE_HASH_FIXED(div2,byte,6);
212                            BIT_HASH_FIXED(div2,bit,8);
213                            BIT_HASH_VARIABLE(logbase2,bit,16);
214                            BIT_HASH_VARIABLE(id,bit,0);
215                        #elif BIT_BYTE_STRATEGY
216                            BYTE_HASH_VARIABLE(bit_byte,byte,7);
217                            BIT_HASH_VARIABLE(bit_byte,bit,0);
218                        #endif
219
220                        #undef BYTE_HASH_FIXED
221                        #undef BYTE_HASH_VARIABLE
222                        #undef BIT_HASH_FIXED
223                        #undef BIT_HASH_VARIABLE
224
225        }
226
227        IDISA_ALWAYS_INLINE uint8_t * get_raw_data(uint32_t idx) const { return gid_data.get_raw_bytes(idx); }
228        IDISA_ALWAYS_INLINE uint32_t get_lgth(uint32_t idx) const { return gid_data.get_bytes_lgth(idx); }
229        IDISA_ALWAYS_INLINE gid_type get_max_gid() const { return gid_data.max(); }
230
231private:
232        GIDFactory gid_factory;
233        GIDData gid_data;
234
235        ///////////////////////////////////////////////////////////////////////////////
236        // Grouping strategy hash table members.
237        ///////////////////////////////////////////////////////////////////////////////
238        #ifdef ID_STRATEGY
239            id_hash_table<1, id, byte, ALLOCATOR> hash_table_1;
240            id_hash_table<2, id, byte, ALLOCATOR> hash_table_2;
241            id_hash_table<3, id, byte, ALLOCATOR> hash_table_3;
242            id_hash_table<4, id, byte, ALLOCATOR> hash_table_4;
243            id_hash_table<5, id, byte, ALLOCATOR> hash_table_5;
244            id_hash_table<6, id, byte, ALLOCATOR> hash_table_6;
245            id_hash_table<7, id, byte, ALLOCATOR> hash_table_7;
246            id_hash_table<8, id, bit, ALLOCATOR> hash_table_8;
247            id_hash_table<9, id, bit, ALLOCATOR> hash_table_9;
248            id_hash_table<10, id, bit, ALLOCATOR> hash_table_10;
249            id_hash_table<11, id, bit, ALLOCATOR> hash_table_11;
250            id_hash_table<12, id, bit, ALLOCATOR> hash_table_12;
251            id_hash_table<13, id, bit, ALLOCATOR> hash_table_13;
252            id_hash_table<14, id, bit, ALLOCATOR> hash_table_14;
253            id_hash_table<15, id, bit, ALLOCATOR> hash_table_15;
254            id_hash_table<16, id, bit, ALLOCATOR> hash_table_16;
255            id_hash_table<0, id, bit, ALLOCATOR> hash_table_0;
256        #elif DIV2_STRATEGY
257            div2_hash_table<2, div2, byte, ALLOCATOR> hash_table_2;
258            div2_hash_table<4, div2, byte, ALLOCATOR> hash_table_4;
259            div2_hash_table<6, div2, byte, ALLOCATOR> hash_table_6;
260            div2_hash_table<8, div2, bit, ALLOCATOR> hash_table_8;
261            div2_hash_table<10, div2, bit, ALLOCATOR> hash_table_10;
262            div2_hash_table<12, div2, bit, ALLOCATOR> hash_table_12;
263            div2_hash_table<14, div2, bit, ALLOCATOR> hash_table_14;
264            div2_hash_table<16, div2, bit, ALLOCATOR> hash_table_16;
265            id_hash_table<0, id, bit, ALLOCATOR> hash_table_0;
266        #elif LOGBASE2_STRATEGY
267            logbase2_hash_table<1, logbase2, byte, ALLOCATOR> hash_table_1;
268            logbase2_hash_table<2, logbase2, byte, ALLOCATOR> hash_table_2;
269            logbase2_hash_table<4, logbase2, byte, ALLOCATOR> hash_table_4;
270            logbase2_hash_table<8, logbase2, bit, ALLOCATOR> hash_table_8;
271            logbase2_hash_table<16, logbase2, bit, ALLOCATOR> hash_table_16;
272            id_hash_table<0, id, bit, ALLOCATOR> hash_table_0;
273        #elif DIV2_LOGBASE2_STRATEGY
274            div2_hash_table<2, div2, byte, ALLOCATOR> hash_table_2;
275            div2_hash_table<4, div2, byte, ALLOCATOR> hash_table_4;
276            div2_hash_table<6, div2, byte, ALLOCATOR> hash_table_6;
277            div2_hash_table<8, div2, bit, ALLOCATOR> hash_table_8;
278            logbase2_hash_table<16, logbase2, bit, ALLOCATOR> hash_table_16;
279            id_hash_table<0, id, bit, ALLOCATOR> hash_table_0;
280        #elif BIT_BYTE_STRATEGY
281            bit_byte_hash_table<7, bit_byte, byte, ALLOCATOR> hash_table_7;
282            bit_byte_hash_table<0, bit_byte, bit, ALLOCATOR> hash_table_0;
283        #else
284            #error "Length group strategy not specified. #define ID_STRATEGY|DIV2_STRATEGY|LOGBASE2_STRATEGY|DIV2_LOGBASE2_STRATEGY|BIT_BYTE_STRATEGY"
285        #endif
286
287};
288
289template<class GIDS, class HASH_TABLE>
290void do_block(uint32_t blk_offset,
291                  HASH_TABLE & h_table,
292                  BitBlock follows,
293                  uint8_t buffer [], const uint32_t lgth,
294                  uint8_t h0 [], uint8_t h1 [], const uint32_t h_block_size,
295                  GIDS & gids, GIDFactory & gid_factory, GIDData & gid_data) {
296
297                uint8_t * buffer_base = buffer;
298                uint8_t * h0_base = h0;
299                uint8_t * h1_base = h1;
300
301                gid_type gid;
302                int32_t fpos;
303                int32_t spos;
304                uint32_t blk_count;
305
306        ReverseScanner<BitBlock, scanword_t> rscanner(&follows);
307
308        rscanner.scan_to_next();
309        fpos = rscanner.get_pos();
310
311                while(!rscanner.is_done()) {
312
313                spos = fpos - lgth;
314
315                        if(spos < 0) { // boundary case
316                                        #ifdef ID_SYMBOL_TABLE_TEMPLATE_HPP_DEBUG
317                                            cout << "Boundary Case: ";
318                                        #endif
319
320                                        spos = (BLOCK_SIZE - (-1 * spos)) & (BLOCK_SIZE - 1);
321                                        blk_count = (lgth/BLOCK_SIZE)+1;
322                                        buffer_base -= (BLOCK_SIZE * blk_count);
323                                        h0_base -= (h_block_size * blk_count);
324                                        h1_base -= (h_block_size * blk_count);
325                        }
326
327                        gid = h_table.lookup_or_insert(buffer_base, spos, lgth, h0_base, h1_base, gid_factory, gid_data); // WARNING: spos must be >= 0
328
329                        #ifdef INDEX_AT_STARTS
330                            gids.at[blk_offset + fpos - gid_data.get_bytes_lgth(gid)] = gid;
331                        #else
332                            gids.at[blk_offset + fpos] = gid;
333                        #endif
334
335                        #ifdef ID_SYMBOL_TABLE_TEMPLATE_HPP_DEBUG
336                                print_symbol_debug(gid, buffer_base, spos, fpos, gid_data.get_bytes_lgth(gid));
337                        #endif
338
339                        rscanner.scan_to_next();
340                        fpos = rscanner.get_pos();
341                }
342        }
343
344template<class GIDS, class HASH_TABLE>
345void do_block(uint32_t blk_offset,
346                          HASH_TABLE & h_table,
347                          BitBlock starts [], BitBlock follows [],
348                          uint8_t buffer [],
349                          uint8_t h0 [], uint8_t h1 [], const uint32_t h_block_size,
350                          GIDS & gids, GIDFactory & gid_factory, GIDData & gid_data) {
351
352        BitBlock * starts_base = starts;
353        uint8_t * buffer_base = buffer;
354        uint8_t * h0_base = h0;
355        uint8_t * h1_base = h1;
356
357        gid_type gid;
358        int32_t fpos;
359        int32_t spos;
360        uint32_t lgth;
361        uint32_t blk_count = 0;
362
363        ReverseScanner<BitBlock, scanword_t> follows_rscanner(follows);
364        ReverseScanner<BitBlock, scanword_t> starts_rscanner(starts);
365
366        follows_rscanner.scan_to_next();
367        fpos = follows_rscanner.get_pos();
368
369        while(!follows_rscanner.is_done()) {
370
371                starts_rscanner.move_to(fpos);
372                starts_rscanner.scan_to_next();
373                spos = starts_rscanner.get_pos();
374                lgth = fpos - spos;
375
376                while(starts_rscanner.is_done()) { // boundary case
377                        #ifdef ID_SYMBOL_TABLE_TEMPLATE_HPP_DEBUG
378                            cout << "Boundary Case: ";
379                        #endif
380
381                        starts_base--;
382
383                        blk_count++;
384
385                        starts_rscanner.init(starts_base);
386                        starts_rscanner.scan_to_next();
387
388                        if(!starts_rscanner.is_done()) { // found start
389                                        lgth = fpos + (BLOCK_SIZE - starts_rscanner.get_pos()) + (BLOCK_SIZE * (blk_count-1));
390                                        spos = starts_rscanner.get_pos();
391                                        buffer_base -= (BLOCK_SIZE * blk_count);
392                                        h0_base -= (h_block_size * blk_count);
393                                        h1_base -= (h_block_size * blk_count);
394                                        break;
395                        }
396
397                }
398
399                gid = h_table.lookup_or_insert(buffer_base, spos, lgth, h0_base, h1_base, gid_factory, gid_data);
400
401                #ifdef INDEX_AT_STARTS
402                    gids.at[blk_offset + fpos - lgth] = gid;
403                #else // INDEX_AT_FOLLOWS
404                    gids.at[blk_offset + fpos] = gid;
405                #endif
406
407                #ifdef ID_SYMBOL_TABLE_TEMPLATE_HPP_DEBUG
408                        print_symbol_debug(gid, buffer_base, spos, fpos, gid_data.get_bytes_lgth(gid));
409                #endif
410
411                follows_rscanner.scan_to_next();
412                fpos = follows_rscanner.get_pos();
413        }
414}
415
416#endif // ID_SYMBOL_TABLE_TEMPLATE_HPP
417
418/* // Forward Scan
419void do_block(uint32_t blk_offset,
420                  HASH_TABLE & h_table,
421                  BitBlock follows,
422                  uint8_t buffer [], const uint32_t lgth,
423                  uint8_t h0 [], uint8_t h1 [], const uint32_t h_lgth, const uint32_t h_block_size,
424                  SYMBOL & symbols, GIDFactory & gid_factory, GIDData & gid_data) {
425
426        gid_type gid;
427        int32_t spos;
428        int32_t fpos;
429        ForwardScanner<BitBlock, scanword_t> fscanner(&follows);
430
431        fscanner.scan_to_next();
432        fpos = fscanner.get_pos();
433        spos = (fpos - lgth);
434
435        if(!fscanner.is_done() && (spos < 0) ) { // block boundary case
436
437        ////////////////////////////////////////////////////////////////////
438        // Start - Review boundary logic
439        ////////////////////////////////////////////////////////////////////
440        uint8_t * lb_buffer = buffer - ((lgth / BLOCK_SIZE) + 1)*BLOCK_SIZE;
441        int32_t lb_spos = (BLOCK_SIZE - (-1*spos)) & (BLOCK_SIZE-1);
442
443        uint8_t * lb_h0 = h0 - ((lgth / BLOCK_SIZE) + 1)*h_block_size;
444        uint8_t * lb_h1 = h1 - ((lgth / BLOCK_SIZE) + 1)*h_block_size;
445
446        gid = h_table.lookup_or_insert(lb_buffer, lb_spos, lgth, lb_h0, lb_h1, h_lgth, gid_factory, gid_data);
447
448        symbols.gids[blk_offset + spos] = gid;
449        ////////////////////////////////////////////////////////////////////
450        // End
451        ////////////////////////////////////////////////////////////////////
452
453        #ifdef ID_SYMBOL_TABLE_TEMPLATE_HPP_DEBUG
454                        print_symbol_debug(gid, lb_buffer, lb_spos, fpos, lgth);
455        #endif
456
457        fscanner.scan_to_next();
458        fpos = fscanner.get_pos();
459        spos = (fpos - lgth);
460
461        }
462
463        while(!fscanner.is_done()) {
464
465                gid = h_table.lookup_or_insert(buffer, spos, lgth, h0, h1, h_lgth, gid_factory, gid_data);
466                symbols.gids[blk_offset + spos] = gid;
467
468        #ifdef ID_SYMBOL_TABLE_TEMPLATE_HPP_DEBUG
469                print_symbol_debug(gid, buffer, spos, fpos, lgth);
470        #endif
471
472                fscanner.scan_to_next();
473                fpos = fscanner.get_pos();
474                spos = (fpos - lgth);
475        }
476
477}
478*/
479
Note: See TracBrowser for help on using the repository browser.