source: trunk/symbol_table/src/lsst.hpp @ 2349

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

Removed #include.

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