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

Last change on this file since 2026 was 2024, checked in by ksherdy, 8 years ago

Added test, diff, clean targets.

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