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

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

Corrected minor hash stream bug

File size: 12.5 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], &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[],
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                        #define BIT_HASH(LENGTH_GROUP, COMPARISON_TYPE) \
123                                if(bitblock::any(groups.ends_##LENGTH_GROUP)) { \
124                                        do_block<SYMBOL, hash_table <identity_strategy_t<COMPARISON_TYPE, LENGTH_GROUP>, hash_strategy_d, ALLOCATOR> > \
125                                                (blk_offset, \
126                                                 hash_table_##LENGTH_GROUP, \
127                                                 groups.ends_##LENGTH_GROUP, \
128                                                 buffer, LENGTH_GROUP, \
129                                                 (uint8_t *)h0, (uint8_t *)h1, LENGTH_GROUP, (BLOCK_SIZE / 8), \
130                                                 symbols, this->gid_factory, this->gid_data); \
131                                }
132
133                        BIT_HASH(8, uint64_t);
134                        BIT_HASH(9, uint64_t);
135                        BIT_HASH(10, uint64_t);
136                        BIT_HASH(11, uint64_t);
137                        BIT_HASH(12, uint64_t);
138                        BIT_HASH(13, uint64_t);
139                        BIT_HASH(14, uint64_t);
140                        BIT_HASH(15, uint64_t);
141                        BIT_HASH(16, BitBlock);
142
143                        #undef BIT_HASH
144
145                        if(bitblock::any(groups.ends_gte_17)) {
146                                do_block<SYMBOL, hash_table<identity_strategy_d, hash_strategy_d, ALLOCATOR> >
147                                                (blk_offset,
148                                                 hash_table_gte_17,
149                                                 starts, &groups.ends_gte_17,
150                                                 buffer,
151                                                 (uint8_t *)h0, (uint8_t *)h1, 17, BLOCK_SIZE/8,
152                                                 symbols, this->gid_factory, this->gid_data);
153                        }
154        }
155
156private:
157        ///////////////////////////////////////////////////////////////////////////////
158        // Byte Space Hash
159        ///////////////////////////////////////////////////////////////////////////////
160        hash_table<identity_strategy_t<uint8_t,1>, hash_strategy_t<1>, ALLOCATOR> hash_table_1;
161        hash_table<identity_strategy_t<uint16_t,2>, hash_strategy_t<2>, ALLOCATOR> hash_table_2;
162        hash_table<identity_strategy_t<uint16_t,3>, hash_strategy_t<3>, ALLOCATOR> hash_table_3;
163        hash_table<identity_strategy_t<uint32_t,4>, hash_strategy_t<4>, ALLOCATOR> hash_table_4;
164        hash_table<identity_strategy_t<uint32_t,5>, hash_strategy_t<5>, ALLOCATOR> hash_table_5;
165        hash_table<identity_strategy_t<uint32_t,6>, hash_strategy_t<6>, ALLOCATOR> hash_table_6;
166        hash_table<identity_strategy_t<uint32_t,7>, hash_strategy_t<7>, ALLOCATOR> hash_table_7;
167        ///////////////////////////////////////////////////////////////////////////////
168        // Bit Space Hash
169        ///////////////////////////////////////////////////////////////////////////////
170        hash_table<identity_strategy_t<uint64_t,8>, hash_strategy_d, ALLOCATOR> hash_table_8;
171        hash_table<identity_strategy_t<uint64_t,9>, hash_strategy_d, ALLOCATOR> hash_table_9;
172        hash_table<identity_strategy_t<uint64_t,10>, hash_strategy_d, ALLOCATOR> hash_table_10;
173        hash_table<identity_strategy_t<uint64_t,11>, hash_strategy_d, ALLOCATOR> hash_table_11;
174        hash_table<identity_strategy_t<uint64_t,12>, hash_strategy_d, ALLOCATOR> hash_table_12;
175        hash_table<identity_strategy_t<uint64_t,13>, hash_strategy_d, ALLOCATOR> hash_table_13;
176        hash_table<identity_strategy_t<uint64_t,14>, hash_strategy_d, ALLOCATOR> hash_table_14;
177        hash_table<identity_strategy_t<uint64_t,15>, hash_strategy_d, ALLOCATOR> hash_table_15;
178        hash_table<identity_strategy_t<BitBlock,16>, hash_strategy_d, ALLOCATOR> hash_table_16;
179        hash_table<identity_strategy_d, hash_strategy_d, ALLOCATOR> hash_table_gte_17;
180};
181
182/* NOTE: C++ template code and Pablo generated length groups must coincide. */
183
184// Fixed Lengths - REVERSE SCAN LOGIC - Scan each BLOCK MSB to LSB
185template<class SYMBOL, class HASH_TABLE>
186void do_block(uint32_t blk_offset,
187                  HASH_TABLE & h_table,
188                  BitBlock ends,
189                  uint8_t buffer [], const uint32_t lgth,
190                  uint8_t h0 [], uint8_t h1 [], const uint32_t h_lgth, const uint32_t h_block_size,
191                  SYMBOL & symbols, GIDFactory & gid_factory, GIDData & gid_data) {
192
193                uint8_t * buffer_base = buffer;
194                uint8_t * h0_base = h0;
195                uint8_t * h1_base = h1;
196
197                gid_type gid;
198                int32_t epos;
199                int32_t spos;
200                uint32_t blk_count;
201
202        ReverseScanner<BitBlock, scanword_t> rscanner(&ends);
203
204        rscanner.scan_to_next();
205        epos = rscanner.get_pos();
206
207                while(!rscanner.is_done()) {
208
209                spos = epos - lgth;
210
211                        if(spos < 0) { // boundary case
212                                        spos = (BLOCK_SIZE - (-1 * spos)) & (BLOCK_SIZE - 1);
213                                        blk_count = (lgth/BLOCK_SIZE)+1;
214                                        buffer_base -= (BLOCK_SIZE * blk_count);
215                                        h0_base -= (h_block_size * blk_count);
216                                        h1_base -= (h_block_size * blk_count);
217                        }
218
219                        assert (spos >= 0);
220
221                        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
222
223                        #ifdef ID_SYMBOL_STORE_SYMBOL_GIDS_AT_END_POSITION
224                        symbols.gids[blk_offset + epos] = gid;
225                        #else
226                        symbols.gids[blk_offset + epos - lgth] = gid;
227                        #endif
228
229                        #ifdef ID_SYMBOL_TABLE_TEMPLATE_HPP_DEBUG
230                                print_symbol_debug(gid, buffer_base, spos, epos, lgth);
231                        #endif
232
233                        rscanner.scan_to_next();
234                epos = rscanner.get_pos();
235                }
236        }
237
238
239// Variable Lengths, reverse scanner logic
240// Precondition: A symbol end is marked iff a symbol start is marked within a buffer segment.
241template<class SYMBOL, class HASH_TABLE>
242void do_block(uint32_t blk_offset,
243                          HASH_TABLE & h_table,
244                          BitBlock starts [], BitBlock ends [],
245                          uint8_t buffer [],
246                          uint8_t h0 [], uint8_t h1 [], const uint32_t h_lgth, const uint32_t h_block_size,
247                          SYMBOL & symbols, GIDFactory & gid_factory, GIDData & gid_data) {
248
249        BitBlock * starts_base = starts;
250        uint8_t * buffer_base = buffer;
251        uint8_t * h0_base = h0;
252        uint8_t * h1_base = h1;
253
254        gid_type gid;
255        int32_t epos;
256        int32_t spos;
257        uint32_t lgth;
258        uint32_t blk_count = 0;
259
260        ReverseScanner<BitBlock, scanword_t> ends_rscanner(ends);
261        ReverseScanner<BitBlock, scanword_t> starts_rscanner(starts);
262
263        ends_rscanner.scan_to_next();
264        epos = ends_rscanner.get_pos();
265
266        while(!ends_rscanner.is_done()) {
267
268                starts_rscanner.move_to(epos);
269                starts_rscanner.scan_to_next();
270                spos = starts_rscanner.get_pos();
271                lgth = epos - spos;
272
273                while(starts_rscanner.is_done()) { // boundary case
274                          starts_base--;
275
276                        blk_count++;
277
278                        starts_rscanner.init(starts_base);
279                        starts_rscanner.scan_to_next();
280
281                        if(!starts_rscanner.is_done()) { // found start
282                                        lgth = epos + (BLOCK_SIZE - starts_rscanner.get_pos()) + (BLOCK_SIZE * (blk_count-1));
283                                        // spos = (BLOCK_SIZE - (-1 * spos)) & (BLOCK_SIZE - 1);
284
285                                        // buffer_base -= (BLOCK_SIZE * blk_count);
286                                        //spos = epos - lgth;
287                                        spos = starts_rscanner.get_pos();
288
289                                        buffer_base -= (BLOCK_SIZE * blk_count);
290                                        h0_base -= (h_block_size * blk_count);
291                                        h1_base -= (h_block_size * blk_count);
292                                        break;
293                        }
294
295                }
296
297                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
298
299                #ifdef ID_SYMBOL_STORE_SYMBOL_GIDS_AT_END_POSITION
300                symbols.gids[blk_offset + epos] = gid;
301                #else
302                symbols.gids[blk_offset + epos - lgth] = gid;
303                #endif
304
305                #ifdef ID_SYMBOL_TABLE_TEMPLATE_HPP_DEBUG
306                        //print_symbol_debug(gid, buffer, spos, epos, lgth);
307                        print_symbol_debug(gid, buffer_base, spos, epos, lgth);
308                #endif
309
310                ends_rscanner.scan_to_next();
311                epos = ends_rscanner.get_pos();
312        }
313}
314
315#endif // ID_SYMBOL_TABLE_TEMPLATE_HPP
316
317//
318/*
319void do_block(uint32_t blk_offset,
320                  HASH_TABLE & h_table,
321                  BitBlock ends,
322                  uint8_t buffer [], const uint32_t lgth,
323                  uint8_t h0 [], uint8_t h1 [], const uint32_t h_lgth, const uint32_t h_block_size,
324                  SYMBOL & symbols, GIDFactory & gid_factory, GIDData & gid_data) {
325
326        gid_type gid;
327        int32_t spos;
328        int32_t epos;
329        ForwardScanner<BitBlock, scanword_t> fscanner(&ends);
330
331        fscanner.scan_to_next();
332        epos = fscanner.get_pos();
333        spos = (epos - lgth);
334
335        if(!fscanner.is_done() && (spos < 0) ) { // block boundary case
336
337        ////////////////////////////////////////////////////////////////////
338        // Start - Review boundary logic
339        ////////////////////////////////////////////////////////////////////
340        uint8_t * lb_buffer = buffer - ((lgth / BLOCK_SIZE) + 1)*BLOCK_SIZE;
341        int32_t lb_spos = (BLOCK_SIZE - (-1*spos)) & (BLOCK_SIZE-1);
342
343        uint8_t * lb_h0 = h0 - ((lgth / BLOCK_SIZE) + 1)*h_block_size;
344        uint8_t * lb_h1 = h1 - ((lgth / BLOCK_SIZE) + 1)*h_block_size;
345
346        gid = h_table.lookup_or_insert(lb_buffer, lb_spos, lgth, lb_h0, lb_h1, h_lgth, gid_factory, gid_data);
347
348        symbols.gids[blk_offset + spos] = gid;
349        ////////////////////////////////////////////////////////////////////
350        // End
351        ////////////////////////////////////////////////////////////////////
352
353        #ifdef ID_SYMBOL_TABLE_TEMPLATE_HPP_DEBUG
354                        print_symbol_debug(gid, lb_buffer, lb_spos, epos, lgth);
355        #endif
356
357        fscanner.scan_to_next();
358        epos = fscanner.get_pos();
359        spos = (epos - lgth);
360
361        }
362
363        while(!fscanner.is_done()) {
364
365                gid = h_table.lookup_or_insert(buffer, spos, lgth, h0, h1, h_lgth, gid_factory, gid_data);
366                symbols.gids[blk_offset + spos] = gid;
367
368        #ifdef ID_SYMBOL_TABLE_TEMPLATE_HPP_DEBUG
369                print_symbol_debug(gid, buffer, spos, epos, lgth);
370        #endif
371
372                fscanner.scan_to_next();
373                epos = fscanner.get_pos();
374                spos = (epos - lgth);
375        }
376
377}
378*/
379
Note: See TracBrowser for help on using the repository browser.