source: trunk/symbol_table/src/id_symbol_table.hpp @ 2034

Last change on this file since 2034 was 2034, checked in by nmedfort, 7 years ago

Some changes for the eventual ICXML inclusion; please test these Ken; differences were reported during testing but I may have run them incorrectly.

File size: 14.3 KB
Line 
1/*
2 * id_symbol_table.hpp
3 * Created on: 18-December-2011
4 * Author: Ken Herdy
5 *
6 * BitBlock type arguments must adhere to the 'full-block invariant'
7 * and mask partial block with null bytes.
8 *
9 * Number of length groups must coincide with the
10 * number compiler generated length groups.
11 *
12 */
13#ifndef ID_SYMBOL_TABLE_TEMPLATE_HPP
14#define ID_SYMBOL_TABLE_TEMPLATE_HPP
15
16#include "symbol_table.hpp"
17#include "buffer.hpp"
18#include "../lib/carryQ.hpp"
19#include "../lib/bitblock_iterator.hpp"
20#include "../lib/bitblock_scan.hpp"
21#include <cstdlib>
22
23#ifdef ID_SYMBOL_TABLE_TEMPLATE_HPP_DEBUG
24static void print_symbol_debug(gid_type gid, const uint8_t buffer [], const int32_t spos, const uint32_t epos, const uint32_t lgth) {
25        cout << "{Symbol:{";
26        cout << "GID:" << gid;
27        cout << ",Length:" << lgth;
28        cout << ",Value:'" << string((char *)&(buffer[spos]), lgth) << "'";
29        cout << ",Start:" << spos;
30        cout << ",End:" << epos;
31        cout << "}}" << endl;
32}
33#endif
34
35// TODO - Refactor as a single mixed symbol table class composed of Id, Div2, Log2 hash tables.
36template<class SYMBOL, class ALLOCATOR>
37class id_symbol_table: public symbol_table<SYMBOL> {
38public:
39        id_symbol_table()/*:hash_table_1(256)*/{}
40        ~id_symbol_table() {
41//      hash_table_1.print_table();
42//      hash_table_2.print_table();
43//      hash_table_3.print_table();
44//      hash_table_4.print_table();
45//      hash_table_5.print_table();
46//      hash_table_6.print_table();
47//      hash_table_7.print_table();
48//      hash_table_8.print_table();
49//      hash_table_9.print_table();
50//      hash_table_10.print_table();
51//      hash_table_11.print_table();
52//      hash_table_12.print_table();
53//      hash_table_13.print_table();
54//      hash_table_14.print_table();
55//      hash_table_15.print_table();
56//      hash_table_16.print_table();
57//      hash_table_gte_17.print_table();
58#ifdef HASH_TABLE_HPP_DEBUG
59        hash_table_1.print_diagnostics();
60        hash_table_2.print_diagnostics();
61        hash_table_3.print_diagnostics();
62        hash_table_4.print_diagnostics();
63        hash_table_5.print_diagnostics();
64        hash_table_6.print_diagnostics();
65        hash_table_7.print_diagnostics();
66        hash_table_8.print_diagnostics();
67
68        hash_table_9.print_diagnostics();
69        hash_table_10.print_diagnostics();
70        hash_table_11.print_diagnostics();
71        hash_table_12.print_diagnostics();
72        hash_table_13.print_diagnostics();
73        hash_table_14.print_diagnostics();
74        hash_table_15.print_diagnostics();
75        hash_table_16.print_diagnostics();
76        hash_table_gte_17.print_diagnostics();
77#endif
78        }
79
80        // Groups & groups
81        void resolve(uint8_t buffer [], Groups groups [],  BitBlock starts [], BitBlock ends_gte_17 [],
82                                 BitBlock h0 [], BitBlock h1 [], uint32_t blocks, SYMBOL & symbols) {
83
84                        for(uint32_t blk = 0; blk < blocks; blk++) {
85                                const uint32_t blk_offset = blk * BLOCKSIZE;
86                                resolve(blk_offset, &buffer[blk_offset], groups[blk], &starts[blk], &ends_gte_17[blk], h0[blk], h1[blk], symbols);
87                        }
88        }
89
90        // Groups & groups
91        IDISA_ALWAYS_INLINE
92        void resolve(uint32_t blk_offset, uint8_t buffer [], Groups groups,  BitBlock starts [], BitBlock ends_gte_17[],
93                                 BitBlock h0, BitBlock h1, SYMBOL & symbols) {
94
95                        ///////////////////////////////////////////////////////////////////////////////
96                        // Byte Space Hash
97                        ///////////////////////////////////////////////////////////////////////////////
98                        #define BYTE_HASH(LENGTH_GROUP, COMPARISON_TYPE) \
99                                if(bitblock::any(groups.ends_##LENGTH_GROUP)) { \
100                                        do_block<SYMBOL, hash_table <identity_strategy_t<COMPARISON_TYPE,LENGTH_GROUP>, hash_strategy_t<LENGTH_GROUP>, ALLOCATOR> > \
101                                                (blk_offset, \
102                                                 hash_table_##LENGTH_GROUP, \
103                                                 groups.ends_##LENGTH_GROUP, \
104                                                 buffer, LENGTH_GROUP, /* buffer, symbol length */ \
105                                                 buffer, buffer, bytes2bits(LENGTH_GROUP), BLOCK_SIZE, /* h0, h1, hash lgth (bits), hash block size (bits) */ \
106                                                 symbols, this->gid_factory, this->gid_data); \
107                                }
108
109                        BYTE_HASH(1, uint8_t);
110                        BYTE_HASH(2, uint16_t);
111                        BYTE_HASH(3, uint16_t);
112                        BYTE_HASH(4, uint32_t);
113                        BYTE_HASH(5, uint32_t);
114                        BYTE_HASH(6, uint32_t);
115                        BYTE_HASH(7, uint32_t);
116
117                        #undef BYTE_HASH
118
119                        ///////////////////////////////////////////////////////////////////////////////
120                        // Bit Space Hash
121                        ///////////////////////////////////////////////////////////////////////////////
122                        if(bitblock::any(groups.ends_8)) {
123                                do_block<SYMBOL, hash_table <identity_strategy_t<uint64_t,8>, hash_strategy_d, ALLOCATOR> >
124                                        (blk_offset,
125                                         hash_table_8,
126                                         groups.ends_8, buffer, 8,
127                                         (uint8_t *)&h0, (uint8_t *)&h1, 8, BLOCK_SIZE/8,
128                                         symbols, this->gid_factory, this->gid_data);
129                        }
130                        if(bitblock::any(groups.ends_9)) {
131                                do_block<SYMBOL, hash_table<identity_strategy_t<uint64_t,9>, hash_strategy_d, ALLOCATOR> >
132                                        (blk_offset,
133                                        hash_table_9,
134                                        groups.ends_9, buffer, 9,
135                                        (uint8_t *)&h0, (uint8_t *)&h1, 9, BLOCK_SIZE/8,
136                                        symbols, this->gid_factory, this->gid_data);
137                        }
138                        if(bitblock::any(groups.ends_10)) {
139                                do_block<SYMBOL, hash_table<identity_strategy_t<uint64_t,10>, hash_strategy_d, ALLOCATOR> >
140                                        (blk_offset,
141                                        hash_table_10,
142                                        groups.ends_10, buffer, 10,
143                                        (uint8_t *)&h0, (uint8_t *)&h1, 10, BLOCK_SIZE/8,
144                                        symbols, this->gid_factory, this->gid_data);
145                        }
146                        if(bitblock::any(groups.ends_11)) {
147                                do_block<SYMBOL, hash_table<identity_strategy_t<uint64_t,11>, hash_strategy_d, ALLOCATOR> >
148                                                (blk_offset,
149                                                hash_table_11,
150                                                groups.ends_11, buffer, 11,
151                                                (uint8_t *)&h0, (uint8_t *)&h1, 11, BLOCK_SIZE/8,
152                                                symbols, this->gid_factory, this->gid_data);
153                        }
154                        if(bitblock::any(groups.ends_12)) {
155                                do_block<SYMBOL, hash_table<identity_strategy_t<uint64_t,12>, hash_strategy_d, ALLOCATOR> >
156                                                (blk_offset,
157                                                hash_table_12,
158                                                groups.ends_12, buffer, 12,
159                                                (uint8_t *)&h0, (uint8_t *)&h1, 12, BLOCK_SIZE/8,
160                                                symbols, this->gid_factory, this->gid_data);
161                        }
162                        if(bitblock::any(groups.ends_13)) {
163                                do_block<SYMBOL, hash_table<identity_strategy_t<uint64_t,13>, hash_strategy_d, ALLOCATOR> >
164                                                (blk_offset,
165                                                hash_table_13,
166                                                groups.ends_13, buffer, 13,
167                                                (uint8_t *)&h0, (uint8_t *)&h1, 13, BLOCK_SIZE/8,
168                                                symbols, this->gid_factory, this->gid_data);
169                        }
170                        if(bitblock::any(groups.ends_14)) {
171                                do_block<SYMBOL, hash_table<identity_strategy_t<uint64_t,14>, hash_strategy_d, ALLOCATOR> >
172                                                (blk_offset,
173                                                hash_table_14,
174                                                groups.ends_14, buffer, 14,
175                                                (uint8_t *)&h0, (uint8_t *)&h1, 14, BLOCK_SIZE/8,
176                                                symbols, this->gid_factory, this->gid_data);
177                        }
178                        if(bitblock::any(groups.ends_15)) {
179                                do_block<SYMBOL, hash_table<identity_strategy_t<uint64_t,15>, hash_strategy_d, ALLOCATOR> >
180                                                (blk_offset,
181                                                hash_table_15,
182                                                groups.ends_15, buffer, 15,
183                                                (uint8_t *)&h0, (uint8_t *)&h1, 15, BLOCK_SIZE/8,
184                                                symbols, this->gid_factory, this->gid_data);
185                        }
186                        if(bitblock::any(groups.ends_16)) {
187                                do_block<SYMBOL, hash_table<identity_strategy_t<BitBlock,16>, hash_strategy_d, ALLOCATOR> >
188                                                (blk_offset,
189                                                hash_table_16,
190                                                groups.ends_16, buffer, 16,
191                                                (uint8_t *)&h0, (uint8_t *)&h1, 16, BLOCK_SIZE/8,
192                                                symbols, this->gid_factory, this->gid_data);
193                        }
194                        if(bitblock::any(groups.ends_gte_17)) {
195                                do_block<SYMBOL, hash_table<identity_strategy_d, hash_strategy_d, ALLOCATOR> >
196                                                (blk_offset,
197                                                 hash_table_gte_17,
198                                                 starts, ends_gte_17,
199                                                 buffer,
200                                                 (uint8_t *)&h0, (uint8_t *)&h1, 17, BLOCK_SIZE/8,
201                                                 symbols, this->gid_factory, this->gid_data);
202                        }
203        }
204
205private:
206        ///////////////////////////////////////////////////////////////////////////////
207        // Byte Space Hash
208        ///////////////////////////////////////////////////////////////////////////////
209        hash_table<identity_strategy_t<uint8_t,1>, hash_strategy_t<1>, ALLOCATOR> hash_table_1;
210        hash_table<identity_strategy_t<uint16_t,2>, hash_strategy_t<2>, ALLOCATOR> hash_table_2;
211        hash_table<identity_strategy_t<uint16_t,3>, hash_strategy_t<3>, ALLOCATOR> hash_table_3;
212        hash_table<identity_strategy_t<uint32_t,4>, hash_strategy_t<4>, ALLOCATOR> hash_table_4;
213        hash_table<identity_strategy_t<uint32_t,5>, hash_strategy_t<5>, ALLOCATOR> hash_table_5;
214        hash_table<identity_strategy_t<uint32_t,6>, hash_strategy_t<6>, ALLOCATOR> hash_table_6;
215        hash_table<identity_strategy_t<uint32_t,7>, hash_strategy_t<7>, ALLOCATOR> hash_table_7;
216        ///////////////////////////////////////////////////////////////////////////////
217        // Bit Space Hash
218        ///////////////////////////////////////////////////////////////////////////////
219        hash_table<identity_strategy_t<uint64_t,8>, hash_strategy_d, ALLOCATOR> hash_table_8;
220        hash_table<identity_strategy_t<uint64_t,9>, hash_strategy_d, ALLOCATOR> hash_table_9;
221        hash_table<identity_strategy_t<uint64_t,10>, hash_strategy_d, ALLOCATOR> hash_table_10;
222        hash_table<identity_strategy_t<uint64_t,11>, hash_strategy_d, ALLOCATOR> hash_table_11;
223        hash_table<identity_strategy_t<uint64_t,12>, hash_strategy_d, ALLOCATOR> hash_table_12;
224        hash_table<identity_strategy_t<uint64_t,13>, hash_strategy_d, ALLOCATOR> hash_table_13;
225        hash_table<identity_strategy_t<uint64_t,14>, hash_strategy_d, ALLOCATOR> hash_table_14;
226        hash_table<identity_strategy_t<uint64_t,15>, hash_strategy_d, ALLOCATOR> hash_table_15;
227        hash_table<identity_strategy_t<BitBlock,16>, hash_strategy_d, ALLOCATOR> hash_table_16;
228        hash_table<identity_strategy_d, hash_strategy_d, ALLOCATOR> hash_table_gte_17;
229};
230
231/* NOTE: C++ template code and Pablo generated length groups must coincide. */
232
233// Fixed Lengths - REVERSE SCAN LOGIC - Scan each BLOCK MSB to LSB
234template<class SYMBOL, class HASH_TABLE>
235void do_block(uint32_t blk_offset,
236                  HASH_TABLE & h_table,
237                  BitBlock ends,
238                  uint8_t buffer [], const uint32_t lgth,
239                  uint8_t h0 [], uint8_t h1 [], const uint32_t h_lgth, const uint32_t h_block_size,
240                  SYMBOL & symbols, GIDFactory & gid_factory, GIDData & gid_data) {
241
242                uint8_t * buffer_base = buffer;
243                uint8_t * h0_base = h0;
244                uint8_t * h1_base = h1;
245
246                gid_type gid;
247                int32_t epos;
248                int32_t spos;
249                uint32_t blk_count;
250
251        ReverseScanner<BitBlock, scanword_t> rscanner(&ends);
252
253        rscanner.scan_to_next();
254        epos = rscanner.get_pos();
255
256                while(!rscanner.is_done()) {
257
258                spos = epos - lgth;
259
260                        if(spos < 0) { // boundary case
261                                        spos = (BLOCK_SIZE - (-1 * spos)) & (BLOCK_SIZE - 1);
262                                        blk_count = (lgth/BLOCK_SIZE)+1;
263                                        buffer_base -= (BLOCK_SIZE * blk_count);
264                                        h0_base -= (h_block_size * blk_count);
265                                        h1_base -= (h_block_size * blk_count);
266                        }
267
268                        gid = h_table.lookup_or_insert(buffer_base, spos, lgth, h0_base, h1_base, h_lgth, gid_factory, gid_data); // WARNING: spos must be >= 0
269                        symbols.gids[blk_offset + epos - lgth] = gid;
270
271                        #ifdef ID_SYMBOL_TABLE_TEMPLATE_HPP_DEBUG
272                                print_symbol_debug(gid, buffer_base, spos, epos, lgth);
273                        #endif
274
275                        rscanner.scan_to_next();
276                epos = rscanner.get_pos();
277                }
278        }
279
280
281// Variable Lengths, reverse scanner logic
282// Precondition: A symbol end is marked iff a symbol start is marked within a buffer segment.
283template<class SYMBOL, class HASH_TABLE>
284void do_block(uint32_t blk_offset,
285                          HASH_TABLE & h_table,
286                          BitBlock starts [], BitBlock ends [],
287                          uint8_t buffer [],
288                          uint8_t h0 [], uint8_t h1 [], const uint32_t h_lgth, const uint32_t h_block_size,
289                          SYMBOL & symbols, GIDFactory & gid_factory, GIDData & gid_data) {
290
291
292
293        BitBlock * starts_base = starts;
294  uint8_t * buffer_base = buffer;
295        uint8_t * h0_base = h0;
296        uint8_t * h1_base = h1;
297
298        gid_type gid;
299        int32_t epos;
300        int32_t spos;
301        uint32_t lgth;
302        uint32_t blk_count = 0;
303
304        ReverseScanner<BitBlock, scanword_t> ends_rscanner(ends);
305        ReverseScanner<BitBlock, scanword_t> starts_rscanner(starts);
306
307        ends_rscanner.scan_to_next();
308        epos = ends_rscanner.get_pos();
309
310        while(!ends_rscanner.is_done()) {
311
312                starts_rscanner.move_to(epos);
313                starts_rscanner.scan_to_next();
314                spos = starts_rscanner.get_pos();
315                lgth = epos - spos;
316
317                while(starts_rscanner.is_done()) { // boundary case
318                          starts_base--;
319
320                        blk_count++;
321
322                        starts_rscanner.init(starts_base);
323                        starts_rscanner.scan_to_next();
324
325                        if(!starts_rscanner.is_done()) { // found start
326                                        lgth = epos + (BLOCK_SIZE - starts_rscanner.get_pos()) + (BLOCK_SIZE * (blk_count-1));
327                                        // spos = (BLOCK_SIZE - (-1 * spos)) & (BLOCK_SIZE - 1);
328
329                                        // buffer_base -= (BLOCK_SIZE * blk_count);
330                                        //spos = epos - lgth;
331                                        spos = starts_rscanner.get_pos();
332
333                                        buffer_base -= (BLOCK_SIZE * blk_count);
334                                        h0_base -= (h_block_size * blk_count);
335                                        h1_base -= (h_block_size * blk_count);
336                                        break;
337                        }
338
339                }
340
341                gid = h_table.lookup_or_insert(buffer_base, spos, lgth, h0_base, h1_base, h_lgth, gid_factory, gid_data); // WARNING: spos must be >= 0
342                symbols.gids[blk_offset + epos - lgth] = gid;
343
344                #ifdef ID_SYMBOL_TABLE_TEMPLATE_HPP_DEBUG
345                        //print_symbol_debug(gid, buffer, spos, epos, lgth);
346                        print_symbol_debug(gid, buffer_base, spos, epos, lgth);
347                #endif
348
349                ends_rscanner.scan_to_next();
350                epos = ends_rscanner.get_pos();
351        }
352}
353
354#endif // ID_SYMBOL_TABLE_TEMPLATE_HPP
355
356//
357/*
358void do_block(uint32_t blk_offset,
359                  HASH_TABLE & h_table,
360                  BitBlock ends,
361                  uint8_t buffer [], const uint32_t lgth,
362                  uint8_t h0 [], uint8_t h1 [], const uint32_t h_lgth, const uint32_t h_block_size,
363                  SYMBOL & symbols, GIDFactory & gid_factory, GIDData & gid_data) {
364
365        gid_type gid;
366        int32_t spos;
367        int32_t epos;
368        ForwardScanner<BitBlock, scanword_t> fscanner(&ends);
369
370        fscanner.scan_to_next();
371        epos = fscanner.get_pos();
372        spos = (epos - lgth);
373
374        if(!fscanner.is_done() && (spos < 0) ) { // block boundary case
375
376        ////////////////////////////////////////////////////////////////////
377        // Start - Review boundary logic
378        ////////////////////////////////////////////////////////////////////
379        uint8_t * lb_buffer = buffer - ((lgth / BLOCK_SIZE) + 1)*BLOCK_SIZE;
380        int32_t lb_spos = (BLOCK_SIZE - (-1*spos)) & (BLOCK_SIZE-1);
381
382        uint8_t * lb_h0 = h0 - ((lgth / BLOCK_SIZE) + 1)*h_block_size;
383        uint8_t * lb_h1 = h1 - ((lgth / BLOCK_SIZE) + 1)*h_block_size;
384
385        gid = h_table.lookup_or_insert(lb_buffer, lb_spos, lgth, lb_h0, lb_h1, h_lgth, gid_factory, gid_data);
386
387        symbols.gids[blk_offset + spos] = gid;
388        ////////////////////////////////////////////////////////////////////
389        // End
390        ////////////////////////////////////////////////////////////////////
391
392        #ifdef ID_SYMBOL_TABLE_TEMPLATE_HPP_DEBUG
393                        print_symbol_debug(gid, lb_buffer, lb_spos, epos, lgth);
394        #endif
395
396        fscanner.scan_to_next();
397        epos = fscanner.get_pos();
398        spos = (epos - lgth);
399
400        }
401
402        while(!fscanner.is_done()) {
403
404                gid = h_table.lookup_or_insert(buffer, spos, lgth, h0, h1, h_lgth, gid_factory, gid_data);
405                symbols.gids[blk_offset + spos] = gid;
406
407        #ifdef ID_SYMBOL_TABLE_TEMPLATE_HPP_DEBUG
408                print_symbol_debug(gid, buffer, spos, epos, lgth);
409        #endif
410
411                fscanner.scan_to_next();
412                epos = fscanner.get_pos();
413                spos = (epos - lgth);
414        }
415
416}
417*/
418
Note: See TracBrowser for help on using the repository browser.