Changeset 1979

Timestamp:

03/27/12 20:19:26 (15 months ago)

Author:

ksherdy

Message:

Added arbitrary length symbol resolution support.

Location:

trunk/symbol_table/src

Files:

• Makefile (modified) (1 diff)
• buffer.hpp (added)
• hash_table.hpp (modified) (2 diffs)
• id_symbol_table.hpp (modified) (5 diffs)
• symbol_table.hpp (modified) (2 diffs)

trunk/symbol_table/src/Makefile

@@ -13 +13 @@
 endif
 
-all: basis_bits.hpp  byte_pool.hpp  hash_strms.hpp  hash_table.hpp  id_group_strms.hpp  id_symbol_table.hpp  main.cpp  Makefile  marker_strms.hpp  symbol_table.hpp  transpose.hpp
+all: basis_bits.hpp buffer.hpp byte_pool.hpp  hash_strms.hpp  hash_table.hpp  id_group_strms.hpp  id_symbol_table.hpp  main.cpp  Makefile  marker_strms.hpp  symbol_table.hpp  transpose.hpp
         $(CC) -o main main.cpp $(AFLAGS) -DID_SYMBOL_TABLE_TEMPLATE_HPP_DEBUG #-DHASH_TABLE_HPP_DEBUG -DBUFFER_PROFILING #
 

trunk/symbol_table/src/hash_table.hpp

@@ -124 +124 @@
         cout << "Idx: " << idx << ", ";
         cout << "GID: " << gid << ", ";
-        cout << "Val: '" << string((char *) &raw_bytes[idx],0,raw_byte_lgth) << "', ";
-        cout << "Bkt: " << bucket << endl;
+        cout << "Value: '" << string((char *) &raw_bytes[idx],0,raw_byte_lgth) << "', ";
+        cout << "Bucket: "      << bucket << endl;
 #endif
 
@@ -154 +154 @@
             while(crt != NULL) {
                 cout << "->"    << "(GID:" << crt->gid
-                                << ", Val:'" << string((char *)&crt->raw_bytes[0], crt->raw_bytes_lgth)
-                                << "', Len:" << crt->raw_bytes_lgth << ")";
+                                << ", Lgth:" << crt->raw_bytes_lgth
+                                << ", Value:'" << string((char *)&crt->raw_bytes[0], crt->raw_bytes_lgth) << "')";
                 crt = crt->next;
             }

trunk/symbol_table/src/id_symbol_table.hpp

@@ -15 +15 @@
 
 //#define ID_SYMBOL_TABLE_TEMPLATE_HPP_DEBUG
+#ifdef ID_SYMBOL_TABLE_TEMPLATE_HPP_DEBUG
+static void print_symbol_debug(const uint8_t buffer [], const uint32_t spos, const uint32_t epos, const uint32_t lgth) {
+    cout << "Symbol(";
+    cout << "Start: " << spos;
+    cout << ",End: " << epos;
+    cout << ",Lgth: " << lgth;
+    cout << ",Value:'" << string((char *)&(buffer[spos]), lgth);
+    cout << "')" << endl;
+}
+#endif
 
 #include "symbol_table.hpp"
 #include "hash_table.hpp"
+#include "buffer.hpp"
 #include "../lib/carryQ.hpp"
 #include "../lib/bitblock_iterator.hpp"
 #include "../lib/bitblock_scan.hpp"
-
-/* NOTE: C++ template code and Pablo generated length groups must coincide. */
-
-template<class HASH_TABLE>
-IDISA_ALWAYS_INLINE void do_block(HASH_TABLE & h_table, BitBlock ends, uint8_t buffer [], const uint32_t lgth,
-                                  uint8_t h0 [], uint8_t h1 [], const uint32_t h_lgth, const uint32_t h_block_size) {
-
-    int32_t spos;
-    int32_t epos;
-    ForwardScanner<BitBlock, scanword_t> scanner(&ends);
-    scanner.scan_to_next();
-    epos = scanner.get_pos();
-    spos = (epos - lgth);
-
-    if((epos != -1) && (spos < 0)) { // block boundary case
-
-        assert(lgth<=BLOCK_SIZE); // segment boundary
-
-        uint8_t * lb_buffer = buffer - ((lgth / BLOCK_SIZE) + 1)*BLOCK_SIZE;
-        int32_t lb_spos = BLOCK_SIZE - ((-1*spos) & (BLOCK_SIZE-1));
-
-        uint8_t * lb_h0 = h0 - ((lgth / BLOCK_SIZE) + 1)*h_block_size;
-        uint8_t * lb_h1 = h1 - ((lgth / BLOCK_SIZE) + 1)*h_block_size;
-
-        h_table.lookup_or_insert(lb_buffer, lb_spos, lgth,
-                                 lb_h0, lb_h1, h_lgth);
-
-#ifdef ID_SYMBOL_TABLE_TEMPLATE_HPP_DEBUG
-        cout << "Symbol(";
-        cout << "End:" << epos;
-        cout << ",Start:" << lb_spos;
-        cout << ",Text:'" << string((char *)&(lb_buffer[lb_spos]), lgth);
-        cout << "')" << endl;
-#endif
-        epos = scanner.scan_to_next();
-        spos = (epos - lgth);
-
-    }
-
-    while(epos != -1) {
-
-        h_table.lookup_or_insert(buffer, spos, lgth,
-                                 h0, h1, h_lgth);
-
-#ifdef ID_SYMBOL_TABLE_TEMPLATE_HPP_DEBUG
-        cout << "Symbol(";
-        cout << "End:" << epos;
-        cout << ",Start:" << spos;
-        cout << ",Text:'" << string((char *)&(buffer[spos]), lgth);
-        cout << "')" << endl;
-#endif
-        epos = scanner.scan_to_next();
-        spos = (epos - lgth);
-
-    }
-}
+#include <cstdlib>
 
 template<class ALLOCATOR>
-class id_symbol_table : public symbol_table {
+class id_symbol_table:public symbol_table {
 public:
     id_symbol_table()/*:hash_table_1(256)*/{}
@@ -105 +61 @@
 
     // Groups & groups
-    void resolve(uint8_t buffer [], Groups groups [], BitBlock h0 [], BitBlock h1 [], uint32_t blocks, AoS_symbol symbol_ary [], const uint32_t symbols) {
+    void resolve(uint8_t buffer [], Groups groups [],  BitBlock starts [], BitBlock ends_gte_17 [],
+                 BitBlock h0 [], BitBlock h1 [], uint32_t blocks, AoS_symbol aos [], const uint32_t symbols) {
 
         for(uint32_t blk=0;blk<blocks;blk++) {
@@ -163 +120 @@
         }
         if(bitblock::any(groups[blk].ends_gte_17)) {
-        do_block<hash_table<identity_strategy_d, hash_strategy_d, ALLOCATOR> >(hash_table_gte_17, groups[blk].ends_gte_17, &buffer[blk*BLOCK_SIZE], 17, (uint8_t *)&h0[blk], (uint8_t *)&h1[blk], 17, BLOCK_SIZE/8);
-        }
-
-
-
-//      do_segment<hash_table<identity_strategy_d, hash_strategy_d, ALLOCATOR> >(hgte_17, starts, groups.ends_gte_17, segment_size);
-
-        }
-    }
-
-    // void resolve(uint8_t * segment, uint32_t segment_blocks, BitBlock * starts, BitBlock * ends, BitBlock * hash_values, SoA_symbol & symbols) {}
+        do_block<hash_table<identity_strategy_d, hash_strategy_d, ALLOCATOR> >(hash_table_gte_17, &starts[blk], &ends_gte_17[blk], &buffer[blk*BLOCK_SIZE], (uint8_t *)&h0[blk], (uint8_t *)&h1[blk], BLOCK_SIZE/8);
+        }
+
+        }
+    }
+
 private:
-
+    ///////////////////////////////////////////////////////////////////////////////
+    // Byte Space Hash
+    ///////////////////////////////////////////////////////////////////////////////
     hash_table<identity_strategy_t<uint8_t,1>, hash_strategy_t<1>, ALLOCATOR> hash_table_1;
     hash_table<identity_strategy_t<uint16_t,2>, hash_strategy_t<2>, ALLOCATOR> hash_table_2;
@@ -183 +137 @@
     hash_table<identity_strategy_t<uint32_t,6>, hash_strategy_t<6>, ALLOCATOR> hash_table_6;
     hash_table<identity_strategy_t<uint32_t,7>, hash_strategy_t<7>, ALLOCATOR> hash_table_7;
-
+    ///////////////////////////////////////////////////////////////////////////////
+    // Bit Space Hash
+    ///////////////////////////////////////////////////////////////////////////////
     hash_table<identity_strategy_t<uint64_t,8>, hash_strategy_t<8>, ALLOCATOR> hash_table_8;
     hash_table<identity_strategy_t<uint64_t,9>, hash_strategy_d, ALLOCATOR> hash_table_9;
@@ -193 +149 @@
     hash_table<identity_strategy_t<uint64_t,15>, hash_strategy_d, ALLOCATOR> hash_table_15;
     hash_table<identity_strategy_t<BitBlock,16>, hash_strategy_d, ALLOCATOR> hash_table_16;
-
     hash_table<identity_strategy_d, hash_strategy_d, ALLOCATOR> hash_table_gte_17;
 
 };
 
+/* NOTE: C++ template code and Pablo generated length groups must coincide. */
+
+// Fixed Lengths - REVERSE SCAN LOGIC - Scan each BLOCK MSB to LSB (high to low memory address)
+template<class HASH_TABLE>
+IDISA_ALWAYS_INLINE void do_block(HASH_TABLE & h_table, BitBlock ends, uint8_t buffer [], const uint32_t lgth,
+                                  uint8_t h0 [], uint8_t h1 [], const uint32_t h_lgth, const uint32_t h_block_size) {
+
+    int32_t spos;
+    ReverseScanner<BitBlock, scanword_t> rscanner(&ends);
+
+    rscanner.scan_to_next();
+    spos = (rscanner.get_pos() - lgth);
+
+    while(!rscanner.is_done() && (spos >= 0)) {
+
+        h_table.lookup_or_insert(buffer, spos, lgth,
+                                 h0, h1, h_lgth);
+
+#ifdef ID_SYMBOL_TABLE_TEMPLATE_HPP_DEBUG
+        print_symbol_debug(buffer, spos, rscanner.get_pos(), lgth);
+#endif
+        rscanner.scan_to_next();
+        spos = (rscanner.get_pos() - lgth);
+    }
+
+    if(!rscanner.is_done() && (spos < 0)) { // block boundary case
+
+        assert(lgth <= (LOOKBACK_SIZE+BLOCK_SIZE)); // segment boundary
+        if(lgth > (LOOKBACK_SIZE+BLOCK_SIZE)) {
+            cerr << "Fatal Error.";
+            cerr << " Symbol length exceeds " << (LOOKBACK_SIZE+BLOCK_SIZE) << " bytes.";
+            cerr << " Symbol tail : ";
+            cerr << string((char *)&(buffer[rscanner.get_pos()-(LOOKBACK_SIZE+BLOCK_SIZE)]), LOOKBACK_SIZE+BLOCK_SIZE) << endl;
+            abort();
+        }
+
+        uint8_t * lb_buffer = buffer - ((lgth / BLOCK_SIZE) + 1)*BLOCK_SIZE;
+        int32_t lb_spos = BLOCK_SIZE - ((-1*spos) & (BLOCK_SIZE-1));
+
+        uint8_t * lb_h0 = h0 - ((lgth / BLOCK_SIZE) + 1)*h_block_size;
+        uint8_t * lb_h1 = h1 - ((lgth / BLOCK_SIZE) + 1)*h_block_size;
+
+        h_table.lookup_or_insert(lb_buffer, lb_spos, lgth,
+                                 lb_h0, lb_h1, h_lgth);
+
+#ifdef ID_SYMBOL_TABLE_TEMPLATE_HPP_DEBUG
+        print_symbol_debug(buffer, spos, rscanner.get_pos(), lgth);
+#endif
+
+    }
+}
+
+// Variable Lengths - REVERSE SCAN LOGIC - Scan each BLOCK MSB to LSB (high to low memory address)
+template<class HASH_TABLE>
+IDISA_ALWAYS_INLINE void do_block(HASH_TABLE & h_table, BitBlock starts [], BitBlock ends [], uint8_t buffer [],
+                                  uint8_t h0 [], uint8_t h1 [], const uint32_t h_block_size) {
+
+    uint32_t lgth;
+    ReverseScanner<BitBlock, scanword_t> ends_rscanner(ends);
+    ReverseScanner<BitBlock, scanword_t> starts_rscanner(starts);
+
+    ends_rscanner.scan_to_next();
+    starts_rscanner.scan_to_next();
+
+    while(!starts_rscanner.is_done() && (starts_rscanner.get_pos() > ends_rscanner.get_pos())) { // synchronize
+        starts_rscanner.scan_to_next();
+    }
+
+    while((!ends_rscanner.is_done()) && (!starts_rscanner.is_done())) {
+        lgth = ends_rscanner.get_pos() - starts_rscanner.get_pos();
+        h_table.lookup_or_insert(buffer, starts_rscanner.get_pos(), lgth, h0, h1, lgth);
+
+#ifdef ID_SYMBOL_TABLE_TEMPLATE_HPP_DEBUG
+    print_symbol_debug(buffer, starts_rscanner.get_pos(), ends_rscanner.get_pos(), lgth);
+#endif
+
+        ends_rscanner.scan_to_next();
+        starts_rscanner.scan_to_next();
+    }
+
+    if((!ends_rscanner.is_done()) && (starts_rscanner.is_done())) { // block boundary case, previous block
+
+        uint32_t lb_blk = 0;
+        while(1) {
+            starts_rscanner.init(--starts);
+            starts_rscanner.scan_to_next();
+
+            if(!starts_rscanner.is_done()) {
+                break;
+            }
+
+            if (lb_blk > LOOKBACK_BLOCKS) {
+                cerr << lb_blk << endl;
+                cerr << "Fatal Error.";
+                cerr << " Symbol length exceeds " << (LOOKBACK_SIZE+BLOCK_SIZE) << " bytes." << endl;
+                cerr << " Symbol tail : ";
+                cerr << string((char *)&(buffer[starts_rscanner.get_pos()-(LOOKBACK_SIZE+BLOCK_SIZE)]), LOOKBACK_SIZE+BLOCK_SIZE) << endl;
+                abort();
+            }
+            lb_blk++;
+        }
+
+        lgth = ends_rscanner.get_pos() + (BLOCK_SIZE - starts_rscanner.get_pos()) + lb_blk * BLOCK_SIZE;
+
+        uint8_t * lb_buffer = buffer - ((lgth / BLOCK_SIZE) + 1)*BLOCK_SIZE;
+        int32_t lb_spos = BLOCK_SIZE - ((-1*starts_rscanner.get_pos()) & (BLOCK_SIZE-1));
+
+        uint8_t * lb_h0 = h0 - ((lgth / BLOCK_SIZE) + 1)*h_block_size;
+        uint8_t * lb_h1 = h1 - ((lgth / BLOCK_SIZE) + 1)*h_block_size;
+
+        h_table.lookup_or_insert(lb_buffer, lb_spos, lgth, lb_h0, lb_h1, lgth);
+
+#ifdef ID_SYMBOL_TABLE_TEMPLATE_HPP_DEBUG
+        print_symbol_debug(lb_buffer, lb_spos, ends_rscanner.get_pos(), lgth);
+#endif
+
+    }
+}
+
+// Fixed Lengths - FORWARD SCAN LOGIC - Scan each BLOCK LSB to MSB (low to high memory address)
+//template<class HASH_TABLE>
+//IDISA_ALWAYS_INLINE void do_block(HASH_TABLE & h_table, BitBlock ends, uint8_t buffer [], const uint32_t lgth,
+//                                uint8_t h0 [], uint8_t h1 [], const uint32_t h_lgth, const uint32_t h_block_size) {
+
+//    int32_t spos;
+//    int32_t epos;
+//    ForwardScanner<BitBlock, scanword_t> fscanner(&ends);
+
+//    epos = fscanner.scan_to_next();
+//    spos = (epos - lgth);
+
+//    if((epos != -1) && (spos < 0)) { // block boundary case
+
+//      assert(lgth<=LOOKBACK_SIZE); // segment boundary
+
+//      uint8_t * lb_buffer = buffer - ((lgth / BLOCK_SIZE) + 1)*BLOCK_SIZE;
+//      int32_t lb_spos = BLOCK_SIZE - ((-1*spos) & (BLOCK_SIZE-1));
+
+//      uint8_t * lb_h0 = h0 - ((lgth / BLOCK_SIZE) + 1)*h_block_size;
+//      uint8_t * lb_h1 = h1 - ((lgth / BLOCK_SIZE) + 1)*h_block_size;
+
+//      h_table.lookup_or_insert(lb_buffer, lb_spos, lgth,
+//                               lb_h0, lb_h1, h_lgth);
+
+//#ifdef ID_SYMBOL_TABLE_TEMPLATE_HPP_DEBUG
+//      cout << "Symbol(";
+//      cout << "End:" << epos;
+//      cout << ",Start:" << lb_spos;
+//      cout << ",Text:'" << string((char *)&(lb_buffer[lb_spos]), lgth);
+//      cout << "')" << endl;
+//#endif
+//      epos = fscanner.scan_to_next();
+//      spos = (epos - lgth);
+
+//    }
+
+//    while(epos != -1) {
+
+//      h_table.lookup_or_insert(buffer, spos, lgth,
+//                               h0, h1, h_lgth);
+
+//#ifdef ID_SYMBOL_TABLE_TEMPLATE_HPP_DEBUG
+//      cout << "Symbol(";
+//      cout << "End:" << epos;
+//      cout << ",Start:" << spos;
+//      cout << ",Text:'" << string((char *)&(buffer[spos]), lgth);
+//      cout << "')" << endl;
+//#endif
+//      epos = fscanner.scan_to_next();
+//      spos = (epos - lgth);
+
+//    }
+//}
+
 #endif // ID_SYMBOL_TABLE_TEMPLATE_HPP
 
-/*
-template<class SYMBOL, class ALLOCATOR>
-class div2: public symbol_table_strategy<SYMBOL, ALLOCATOR> {
-
-public:
-    div2() {}
-    ~div2() {}
-
-    void resolve(BitBlock * buffer, BitBlock * starts, BitBlock * ends, BitBlock * hash_basis_0, BitBlock * hash_basis_1, uint32_t segment_size, AoS_symbol * symbol_ary, const uint32_t symbol_ary_size) {
-        cout << "div2 Strategy" << endl;
-    }
-    //void resolve(uint8_t * segment, uint32_t segment_blocks, BitBlock * starts, BitBlock * ends, SoA_symbol & symbols);
-};
-*/
-/*
-template<class SYMBOL, class ALLOCATOR>
-class log2: public symbol_table_strategy<SYMBOL, ALLOCATOR> {
-
-public:
-    log2() {}
-    ~log2() {}
-
-    void resolve(BitBlock * buffer, BitBlock * starts, BitBlock * ends, BitBlock * hash_basis_0, BitBlock * hash_basis_1, uint32_t segment_size, AoS_symbol * symbol_ary, const uint32_t symbol_ary_size) {
-        cout << "log2 Strategy" << endl;
-    }
-    //void resolve(uint8_t * segment, uint32_t segment_blocks, BitBlock * starts, BitBlock * ends, SoA_symbol & symbols);
-};
-*/
-
+

trunk/symbol_table/src/symbol_table.hpp

@@ -31 +31 @@
 class symbol_table {
 public:
-    // TODO - Update Interface
-    //void resolve(uint8_t * raw_buffer, Markers * markers, Groups * groups, const Hash * hash, uint32_t blocks, AoS_symbol * symbol_ary, const uint32_t symbol_ary_size);
-    //void resolve(uint8_t * segment, uint32_t segment_blocks, BitBlock * starts, BitBlock * ends, BitBlock * hash_values, SoA_symbol & symbols);
+    void resolve(uint8_t buffer [], Groups groups [],  BitBlock starts [], BitBlock ends_gte_17 [],
+                 BitBlock h0 [], BitBlock h1 [], uint32_t blocks, AoS_symbol aos [], const uint32_t symbols);
+
+    void resolve(uint8_t buffer [], Groups groups [],  BitBlock starts [], BitBlock ends_gte_17 [],
+                 BitBlock h0 [], BitBlock h1 [], uint32_t blocks, SoA_symbol & soa, const uint32_t symbols);
 
 protected:
@@ -40 +42 @@
 };
 
+template<class HASH_TABLE>
+IDISA_ALWAYS_INLINE void do_block(HASH_TABLE & h_table, BitBlock ends, uint8_t buffer [], const uint32_t lgth,
+                                  uint8_t h0 [], uint8_t h1 [], const uint32_t h_lgth, const uint32_t h_block_size);
+
+template<class HASH_TABLE>
+IDISA_ALWAYS_INLINE void do_block(HASH_TABLE & h_table, BitBlock starts [], BitBlock ends [], uint8_t buffer [],
+                                  uint8_t h0 [], uint8_t h1 [], const uint32_t h_block_size);
+
 #endif // SYMBOL_TABLE_HPP
 
+/*
+template<class SYMBOL, class ALLOCATOR>
+class div2: public symbol_table_strategy<SYMBOL, ALLOCATOR> {
 
+public:
+    div2() {}
+    ~div2() {}
 
+    void resolve(...) {
+        cout << "div2 Strategy" << endl;
+    }
+    //void resolve(uint8_t * segment, uint32_t segment_blocks, BitBlock * starts, BitBlock * ends, SoA_symbol & symbols);
+};
+*/
+
+/*
+template<class SYMBOL, class ALLOCATOR>
+class log2: public symbol_table_strategy<SYMBOL, ALLOCATOR> {
+
+public:
+    log2() {}
+    ~log2() {}
+
+    void resolve(...) {
+        cout << "log2 Strategy" << endl;
+    }
+    //void resolve(uint8_t * segment, uint32_t segment_blocks, BitBlock * starts, BitBlock * ends, SoA_symbol & symbols);
+};
+*/
+