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

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

Refactor arbitrary length symbol resolution.

File size: 16.6 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                        uint32_t blk_offset;
85
86                        for(uint32_t blk=0;blk<blocks;blk++) {
87
88                                blk_offset = blk * BLOCKSIZE;
89                                ///////////////////////////////////////////////////////////////////////////////
90                                // Byte Space Hash
91                                ///////////////////////////////////////////////////////////////////////////////
92                                if(bitblock::any(groups[blk].ends_1)) {
93                                        do_block<SYMBOL, hash_table <identity_strategy_t<uint8_t,1>, hash_strategy_t<1>, ALLOCATOR> >
94                                                (blk_offset,
95                                                 hash_table_1,
96                                                 groups[blk].ends_1,
97                                                 &buffer[blk_offset], 1,                                                  /* buffer, symbol length */
98                                                 &buffer[blk_offset], &buffer[blk_offset], bytes2bits(1), BLOCK_SIZE, /* h0, h1, hash lgth (bits), hash block size (bits) */
99                                                 symbols, this->gid_factory, this->gid_data);
100                                }
101                                if(bitblock::any(groups[blk].ends_2)) {
102                                                do_block<SYMBOL, hash_table <identity_strategy_t<uint16_t,2>, hash_strategy_t<2>, ALLOCATOR> >
103                                                        (blk_offset,
104                                                         hash_table_2,
105                                                         groups[blk].ends_2,
106                                                         &buffer[blk_offset], 2,
107                                                         &buffer[blk_offset], &buffer[blk_offset], bytes2bits(2), BLOCK_SIZE,
108                                                         symbols, this->gid_factory, this->gid_data);
109                                }
110                                if(bitblock::any(groups[blk].ends_3)) {
111                                                do_block<SYMBOL, hash_table <identity_strategy_t<uint16_t,3>, hash_strategy_t<3>, ALLOCATOR> >
112                                                        (blk_offset,
113                                                         hash_table_3,
114                                                         groups[blk].ends_3,
115                                                         &buffer[blk_offset], 3,
116                                                         &buffer[blk_offset], &buffer[blk_offset], bytes2bits(3), BLOCK_SIZE,
117                                                         symbols, this->gid_factory, this->gid_data);
118                                }
119                                if(bitblock::any(groups[blk].ends_4)) {
120                                                do_block<SYMBOL, hash_table <identity_strategy_t<uint32_t,4>, hash_strategy_t<4>, ALLOCATOR> >
121                                                        (blk_offset,
122                                                         hash_table_4,
123                                                         groups[blk].ends_4,
124                                                         &buffer[blk_offset], 4,
125                                                         &buffer[blk_offset], &buffer[blk_offset], bytes2bits(4), BLOCK_SIZE,
126                                                         symbols, this->gid_factory, this->gid_data);
127                                }
128                                if(bitblock::any(groups[blk].ends_5)) {
129                                                do_block<SYMBOL, hash_table <identity_strategy_t<uint32_t,5>, hash_strategy_t<5>, ALLOCATOR> >
130                                                        (blk_offset,
131                                                         hash_table_5,
132                                                         groups[blk].ends_5,
133                                                         &buffer[blk_offset], 5,
134                                                         &buffer[blk_offset], &buffer[blk_offset], bytes2bits(5), BLOCK_SIZE,
135                                                         symbols, this->gid_factory, this->gid_data);
136                                }
137                                if(bitblock::any(groups[blk].ends_6)) {
138                                                do_block<SYMBOL, hash_table <identity_strategy_t<uint32_t,6>, hash_strategy_t<6>, ALLOCATOR> >
139                                                        (blk_offset,
140                                                         hash_table_6,
141                                                         groups[blk].ends_6,
142                                                         &buffer[blk_offset], 6,
143                                                         &buffer[blk_offset], &buffer[blk_offset], bytes2bits(6), BLOCK_SIZE,
144                                                         symbols, this->gid_factory, this->gid_data);
145                                }
146                                if(bitblock::any(groups[blk].ends_7)) {
147                                                do_block<SYMBOL, hash_table <identity_strategy_t<uint32_t,7>, hash_strategy_t<7>, ALLOCATOR> >
148                                                        (blk_offset,
149                                                         hash_table_7,
150                                                         groups[blk].ends_7,
151                                                         &buffer[blk_offset], 7,
152                                                         &buffer[blk_offset], &buffer[blk_offset], bytes2bits(7), BLOCK_SIZE,
153                                                         symbols, this->gid_factory, this->gid_data);
154                                }
155                                ///////////////////////////////////////////////////////////////////////////////
156                                // Bit Space Hash
157                                ///////////////////////////////////////////////////////////////////////////////
158                                if(bitblock::any(groups[blk].ends_8)) {
159                                                do_block<SYMBOL, hash_table <identity_strategy_t<uint64_t,8>, hash_strategy_d, ALLOCATOR> >
160                                                        (blk_offset,
161                                                         hash_table_8,
162                                                         groups[blk].ends_8, &buffer[blk_offset], 8,
163                                                         (uint8_t *)&h0[blk], (uint8_t *)&h1[blk], 8, BLOCK_SIZE/8,
164                                                         symbols, this->gid_factory, this->gid_data);
165                                }
166                                if(bitblock::any(groups[blk].ends_9)) {
167                                        do_block<SYMBOL, hash_table<identity_strategy_t<uint64_t,9>, hash_strategy_d, ALLOCATOR> >
168                                                (blk_offset,
169                                                hash_table_9,
170                                                groups[blk].ends_9, &buffer[blk_offset], 9,
171                                                (uint8_t *)&h0[blk], (uint8_t *)&h1[blk], 9, BLOCK_SIZE/8,
172                                                symbols, this->gid_factory, this->gid_data);
173                                }
174                                if(bitblock::any(groups[blk].ends_10)) {
175                                        do_block<SYMBOL, hash_table<identity_strategy_t<uint64_t,10>, hash_strategy_d, ALLOCATOR> >
176                                                (blk_offset,
177                                                hash_table_10,
178                                                groups[blk].ends_10, &buffer[blk_offset], 10,
179                                                (uint8_t *)&h0[blk], (uint8_t *)&h1[blk], 10, BLOCK_SIZE/8,
180                                                symbols, this->gid_factory, this->gid_data);
181                                }
182                                if(bitblock::any(groups[blk].ends_11)) {
183                                        do_block<SYMBOL, hash_table<identity_strategy_t<uint64_t,11>, hash_strategy_d, ALLOCATOR> >
184                                                        (blk_offset,
185                                                        hash_table_11,
186                                                        groups[blk].ends_11, &buffer[blk_offset], 11,
187                                                        (uint8_t *)&h0[blk], (uint8_t *)&h1[blk], 11, BLOCK_SIZE/8,
188                                                        symbols, this->gid_factory, this->gid_data);
189                                }
190                                if(bitblock::any(groups[blk].ends_12)) {
191                                        do_block<SYMBOL, hash_table<identity_strategy_t<uint64_t,12>, hash_strategy_d, ALLOCATOR> >
192                                                        (blk_offset,
193                                                        hash_table_12,
194                                                        groups[blk].ends_12, &buffer[blk_offset], 12,
195                                                        (uint8_t *)&h0[blk], (uint8_t *)&h1[blk], 12, BLOCK_SIZE/8,
196                                                        symbols, this->gid_factory, this->gid_data);
197                                }
198                                if(bitblock::any(groups[blk].ends_13)) {
199                                        do_block<SYMBOL, hash_table<identity_strategy_t<uint64_t,13>, hash_strategy_d, ALLOCATOR> >
200                                                        (blk_offset,
201                                                        hash_table_13,
202                                                        groups[blk].ends_13, &buffer[blk_offset], 13,
203                                                        (uint8_t *)&h0[blk], (uint8_t *)&h1[blk], 13, BLOCK_SIZE/8,
204                                                        symbols, this->gid_factory, this->gid_data);
205                                }
206                                if(bitblock::any(groups[blk].ends_14)) {
207                                        do_block<SYMBOL, hash_table<identity_strategy_t<uint64_t,14>, hash_strategy_d, ALLOCATOR> >
208                                                        (blk_offset,
209                                                        hash_table_14,
210                                                        groups[blk].ends_14, &buffer[blk_offset], 14,
211                                                        (uint8_t *)&h0[blk], (uint8_t *)&h1[blk], 14, BLOCK_SIZE/8,
212                                                        symbols, this->gid_factory, this->gid_data);
213                                }
214                                if(bitblock::any(groups[blk].ends_15)) {
215                                        do_block<SYMBOL, hash_table<identity_strategy_t<uint64_t,15>, hash_strategy_d, ALLOCATOR> >
216                                                        (blk_offset,
217                                                        hash_table_15,
218                                                        groups[blk].ends_15, &buffer[blk_offset], 15,
219                                                        (uint8_t *)&h0[blk], (uint8_t *)&h1[blk], 15, BLOCK_SIZE/8,
220                                                        symbols, this->gid_factory, this->gid_data);
221                                }
222                                if(bitblock::any(groups[blk].ends_16)) {
223                                        do_block<SYMBOL, hash_table<identity_strategy_t<BitBlock,16>, hash_strategy_d, ALLOCATOR> >
224                                                        (blk_offset,
225                                                        hash_table_16,
226                                                        groups[blk].ends_16, &buffer[blk_offset], 16,
227                                                        (uint8_t *)&h0[blk], (uint8_t *)&h1[blk], 16, BLOCK_SIZE/8,
228                                                        symbols, this->gid_factory, this->gid_data);
229                                }
230                                if(bitblock::any(groups[blk].ends_gte_17)) {
231                                        do_block<SYMBOL, hash_table<identity_strategy_d, hash_strategy_d, ALLOCATOR> >
232                                                        (blk_offset,
233                                                         hash_table_gte_17,
234                                                         &starts[blk], &ends_gte_17[blk],
235                                                         &buffer[blk_offset],
236                                                         (uint8_t *)&h0[blk], (uint8_t *)&h1[blk], 17, BLOCK_SIZE/8,
237                                                         symbols, this->gid_factory, this->gid_data);
238                                }
239                        }
240    }
241
242private:
243    ///////////////////////////////////////////////////////////////////////////////
244    // Byte Space Hash
245    ///////////////////////////////////////////////////////////////////////////////
246    hash_table<identity_strategy_t<uint8_t,1>, hash_strategy_t<1>, ALLOCATOR> hash_table_1;
247    hash_table<identity_strategy_t<uint16_t,2>, hash_strategy_t<2>, ALLOCATOR> hash_table_2;
248    hash_table<identity_strategy_t<uint16_t,3>, hash_strategy_t<3>, ALLOCATOR> hash_table_3;
249    hash_table<identity_strategy_t<uint32_t,4>, hash_strategy_t<4>, ALLOCATOR> hash_table_4;
250    hash_table<identity_strategy_t<uint32_t,5>, hash_strategy_t<5>, ALLOCATOR> hash_table_5;
251    hash_table<identity_strategy_t<uint32_t,6>, hash_strategy_t<6>, ALLOCATOR> hash_table_6;
252    hash_table<identity_strategy_t<uint32_t,7>, hash_strategy_t<7>, ALLOCATOR> hash_table_7;
253    ///////////////////////////////////////////////////////////////////////////////
254    // Bit Space Hash
255    ///////////////////////////////////////////////////////////////////////////////
256    hash_table<identity_strategy_t<uint64_t,8>, hash_strategy_d, ALLOCATOR> hash_table_8;
257    hash_table<identity_strategy_t<uint64_t,9>, hash_strategy_d, ALLOCATOR> hash_table_9;
258    hash_table<identity_strategy_t<uint64_t,10>, hash_strategy_d, ALLOCATOR> hash_table_10;
259    hash_table<identity_strategy_t<uint64_t,11>, hash_strategy_d, ALLOCATOR> hash_table_11;
260    hash_table<identity_strategy_t<uint64_t,12>, hash_strategy_d, ALLOCATOR> hash_table_12;
261    hash_table<identity_strategy_t<uint64_t,13>, hash_strategy_d, ALLOCATOR> hash_table_13;
262    hash_table<identity_strategy_t<uint64_t,14>, hash_strategy_d, ALLOCATOR> hash_table_14;
263    hash_table<identity_strategy_t<uint64_t,15>, hash_strategy_d, ALLOCATOR> hash_table_15;
264    hash_table<identity_strategy_t<BitBlock,16>, hash_strategy_d, ALLOCATOR> hash_table_16;
265    hash_table<identity_strategy_d, hash_strategy_d, ALLOCATOR> hash_table_gte_17;
266};
267
268/* NOTE: C++ template code and Pablo generated length groups must coincide. */
269
270// Fixed Lengths - REVERSE SCAN LOGIC - Scan each BLOCK MSB to LSB
271template<class SYMBOL, class HASH_TABLE>
272void do_block(uint32_t blk_offset,
273              HASH_TABLE & h_table,
274              BitBlock ends,
275              uint8_t buffer [], const uint32_t lgth,
276              uint8_t h0 [], uint8_t h1 [], const uint32_t h_lgth, const uint32_t h_block_size,
277              SYMBOL & symbols, GIDFactory & gid_factory, GIDData & gid_data) {
278
279                uint8_t * buffer_base = buffer;
280                uint8_t * h0_base = h0;
281                uint8_t * h1_base = h1;
282
283                gid_type gid;
284                int32_t epos;
285                int32_t spos;
286                uint32_t blk_count;
287
288    ReverseScanner<BitBlock, scanword_t> rscanner(&ends);
289
290    rscanner.scan_to_next();
291    epos = rscanner.get_pos();
292
293                while(!rscanner.is_done()) { 
294
295        spos = epos - lgth;
296
297                        if(spos < 0) { // boundary case
298                                        spos = (BLOCK_SIZE - (-1 * spos)) & (BLOCK_SIZE - 1);
299                                        blk_count = (lgth/BLOCK_SIZE)+1;               
300                                        buffer_base -= (BLOCK_SIZE * blk_count);       
301                                        h0_base -= (h_block_size * blk_count);
302                                        h1_base -= (h_block_size * blk_count);
303                        }
304
305                        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
306                        symbols.gids[blk_offset + epos - lgth] = gid;
307
308                        #ifdef ID_SYMBOL_TABLE_TEMPLATE_HPP_DEBUG
309                                print_symbol_debug(gid, buffer_base, spos, epos, lgth);
310                        #endif
311
312                        rscanner.scan_to_next();
313                epos = rscanner.get_pos();
314                }
315        }
316
317
318// Variable Lengths, reverse scanner logic
319// Precondition: A symbol end is marked iff a symbol start is marked within a buffer segment.
320template<class SYMBOL, class HASH_TABLE>
321void do_block(uint32_t blk_offset,
322                          HASH_TABLE & h_table,
323                          BitBlock starts [], BitBlock ends [],
324                          uint8_t buffer [],
325                          uint8_t h0 [], uint8_t h1 [], const uint32_t h_lgth, const uint32_t h_block_size,
326                          SYMBOL & symbols, GIDFactory & gid_factory, GIDData & gid_data) {
327
328
329
330        BitBlock * starts_base = starts;
331  uint8_t * buffer_base = buffer;
332        uint8_t * h0_base = h0;
333        uint8_t * h1_base = h1;
334
335        gid_type gid;
336        int32_t epos;
337        int32_t spos;
338        uint32_t lgth;
339        uint32_t blk_count = 0;
340
341        ReverseScanner<BitBlock, scanword_t> ends_rscanner(ends);
342        ReverseScanner<BitBlock, scanword_t> starts_rscanner(starts);
343
344        ends_rscanner.scan_to_next();
345        epos = ends_rscanner.get_pos();
346
347        while(!ends_rscanner.is_done()) {
348               
349                starts_rscanner.move_to(epos);
350                starts_rscanner.scan_to_next();
351                spos = starts_rscanner.get_pos();
352                lgth = epos - spos;
353
354                while(starts_rscanner.is_done()) { // boundary case
355                          starts_base--;
356
357                    blk_count++;
358
359                    starts_rscanner.init(starts_base);
360                    starts_rscanner.scan_to_next();
361
362                    if(!starts_rscanner.is_done()) { // found start
363                                        lgth = epos + (BLOCK_SIZE - starts_rscanner.get_pos()) + (BLOCK_SIZE * (blk_count-1));
364                                        // spos = (BLOCK_SIZE - (-1 * spos)) & (BLOCK_SIZE - 1);
365
366                                        // buffer_base -= (BLOCK_SIZE * blk_count);     
367                                        //spos = epos - lgth;
368                                        spos = starts_rscanner.get_pos();
369
370                                        buffer_base -= (BLOCK_SIZE * blk_count);
371                                        h0_base -= (h_block_size * blk_count);
372                                        h1_base -= (h_block_size * blk_count);
373                                        break;
374                    }
375
376                }
377
378                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
379                symbols.gids[blk_offset + epos - lgth] = gid;
380
381                #ifdef ID_SYMBOL_TABLE_TEMPLATE_HPP_DEBUG
382                        //print_symbol_debug(gid, buffer, spos, epos, lgth);
383                        print_symbol_debug(gid, buffer_base, spos, epos, lgth);
384                #endif
385
386                ends_rscanner.scan_to_next();
387                epos = ends_rscanner.get_pos();
388        }
389}
390
391#endif // ID_SYMBOL_TABLE_TEMPLATE_HPP
392
393//
394/*
395void do_block(uint32_t blk_offset,
396              HASH_TABLE & h_table,
397              BitBlock ends,
398              uint8_t buffer [], const uint32_t lgth,
399              uint8_t h0 [], uint8_t h1 [], const uint32_t h_lgth, const uint32_t h_block_size,
400              SYMBOL & symbols, GIDFactory & gid_factory, GIDData & gid_data) {
401
402    gid_type gid;
403    int32_t spos;
404    int32_t epos;
405    ForwardScanner<BitBlock, scanword_t> fscanner(&ends);
406
407    fscanner.scan_to_next();
408    epos = fscanner.get_pos();
409    spos = (epos - lgth);
410
411        if(!fscanner.is_done() && (spos < 0) ) { // block boundary case
412
413        ////////////////////////////////////////////////////////////////////
414        // Start - Review boundary logic
415        ////////////////////////////////////////////////////////////////////
416        uint8_t * lb_buffer = buffer - ((lgth / BLOCK_SIZE) + 1)*BLOCK_SIZE;
417        int32_t lb_spos = (BLOCK_SIZE - (-1*spos)) & (BLOCK_SIZE-1);
418
419        uint8_t * lb_h0 = h0 - ((lgth / BLOCK_SIZE) + 1)*h_block_size;
420        uint8_t * lb_h1 = h1 - ((lgth / BLOCK_SIZE) + 1)*h_block_size;
421
422        gid = h_table.lookup_or_insert(lb_buffer, lb_spos, lgth, lb_h0, lb_h1, h_lgth, gid_factory, gid_data);
423
424        symbols.gids[blk_offset + spos] = gid;
425        ////////////////////////////////////////////////////////////////////
426        // End
427        ////////////////////////////////////////////////////////////////////
428
429        #ifdef ID_SYMBOL_TABLE_TEMPLATE_HPP_DEBUG
430                        print_symbol_debug(gid, lb_buffer, lb_spos, epos, lgth);
431        #endif
432
433        fscanner.scan_to_next();
434        epos = fscanner.get_pos();
435        spos = (epos - lgth);
436
437    }
438
439        while(!fscanner.is_done()) {
440
441                gid = h_table.lookup_or_insert(buffer, spos, lgth, h0, h1, h_lgth, gid_factory, gid_data);
442                symbols.gids[blk_offset + spos] = gid;
443
444        #ifdef ID_SYMBOL_TABLE_TEMPLATE_HPP_DEBUG
445                print_symbol_debug(gid, buffer, spos, epos, lgth);
446        #endif
447
448                fscanner.scan_to_next();
449                epos = fscanner.get_pos();
450                spos = (epos - lgth);
451    }
452
453}
454*/
455
Note: See TracBrowser for help on using the repository browser.