source: trunk/lib/symtab/pbgs_utilities.h @ 1518

Last change on this file since 1518 was 1518, checked in by vla24, 8 years ago

SymbolTable?: hash table implementation for paralel bitstream based length sorting (PBGS) now auto-resizes. Fixed flipBit function used by Div2 grouping strategy

File size: 6.4 KB
Line 
1/*
2 *      Created on: 25-August-2011
3 *      Author: Vera Lukman
4 *
5 *      Utility functions for Parallel Bitstream-Based Length Sorting Symbol Table.
6 *      This file includes:
7 *      - Length specific comparison functions using a C++ function object or a C++ function template approach.
8 *      - Flipping the last bit of a hashvalue
9 *
10 *      For identity grouping strategy, use id_div_equal_compare<L>
11 *      For log grouping strategy, use log_div_equal_compare<L> or overlap_compare. USE_MASK_COMPARE uses log_div_equal_compare<4> for L = 3 or 4
12 *      For div grouping strategy, use div_div_equal_compare<L>
13 */
14
15#ifndef PBGS_UTILITIES_H_
16#define PBGS_UTILITIES_H_
17#define USE_FUNCTION_TEMPLATES //Used in ls_symbol_table_compare.h
18//#define USE_MASK_COMPARE    //Comparison using masking technique.
19                              //This technique only applies for USE_LOG_SORT
20
21#include "library_conversion.h"
22#include "ls_symbol_table_compare.h"
23#define DEBUG_EQUAL_COMPARE 0
24
25// ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- -----
26// Equivalent symbol-at-a-time comparison methods implemented using C++ function templates.
27
28/*********************IDENTITY GROUPING COMPARISON*******************************/
29
30template <size_t L>
31inline bool id_equal_compare(const unsigned char * key, const unsigned char * symbol) {
32        return compare<L>(key, symbol);
33}
34
35template<>
36inline bool id_equal_compare<3>(const unsigned char * key, const unsigned char * symbol) {
37    return ((* ((uint32_t *) key)) ==
38                                ((* ((uint32_t *) symbol)) & (0xFFFFFF << LOW_BYTE_SHIFT))); // s4int32()
39}
40
41template<>
42inline bool id_equal_compare<5>(const unsigned char * key, const unsigned char * symbol) {
43    return ((* ((uint64_t *) key)) ==
44                        ((* ((uint64_t *) symbol)) & (0xFFFFFFFFFFULL << (3 * LOW_BYTE_SHIFT)))); // s8int64()
45}
46
47template<>
48inline bool id_equal_compare<6>(const unsigned char * key, const unsigned char * symbol) {
49    return ((* ((uint64_t *) key)) ==
50                        ((* ((uint64_t *) symbol)) & (0xFFFFFFFFFFFFULL << (2 * LOW_BYTE_SHIFT)))); // s8int64()
51}
52
53template<>
54inline bool id_equal_compare<7>(const unsigned char * key, const unsigned char * symbol) {
55    return ((* ((uint64_t *) key)) ==
56                        ((* ((uint64_t *) symbol)) & (0xFFFFFFFFFFFFFFULL << LOW_BYTE_SHIFT))); // s8int64()
57}
58
59/************************LOG GROUPING COMPARISON*******************************/
60inline bool log_equal_compare_1(const unsigned char * key, const unsigned char * symbol) {
61    return compare<1>(key, symbol);
62}
63
64inline bool log_equal_compare_2(const unsigned char * key, const unsigned char * symbol) {
65    return compare<2>(key, symbol);
66}
67
68inline bool log_equal_compare_4(const unsigned char * key, const unsigned char * symbol, int symbol_lgth) {
69    return ((* ((uint32_t *) key)) ==
70            ((* ((uint32_t *) symbol)) & ((0xFFFFFF | (3-symbol_lgth)) << ((4-symbol_lgth) * LOW_BYTE_SHIFT)) ));
71}
72
73template<class T>
74inline bool overlap_compare(const unsigned char * key, const unsigned char * symbol, const unsigned int key_lgth, int symbol_lgth);
75
76// if key_lgth, symbol_lgth in [3,4], T = uint16_t
77// if key_lgth, symbol_lgth in [5,8], T = uint32_t
78// if key_lgth, symbol_lgth in [9,16], T = uint64_t
79// if key_lgth, symbol_lgth in [17,32], T = SIMD_type
80template<class T>
81inline bool overlap_compare(const unsigned char * key, const unsigned char * symbol, const unsigned int key_lgth, int symbol_lgth)
82{
83#if DEBUG_EQUAL_COMPARE
84    int constant = sizeof(T);
85    T* s1 = (T*) symbol;
86    T* k1 = (T*) key;
87    T* s2 = (T*) (symbol + symbol_lgth - constant);
88    T* k2 = (T*) (key + key_lgth - constant);
89
90    return !((*s1 ^ *k1) | (*s2 ^ *k2));
91#else
92    return !((*((T*) symbol) ^ *((T*) key)) |
93             (*((T*) (symbol + symbol_lgth - sizeof(T))) ^ *((T*) (key + key_lgth - sizeof(T)))));
94#endif
95}
96
97template<>
98inline bool overlap_compare<SIMD_type>(const unsigned char * key, const unsigned char * symbol, const unsigned int key_lgth, int symbol_lgth) {
99#if DEBUG_EQUAL_COMPARE
100    SIMD_type* s1 = (SIMD_type*) symbol;
101    SIMD_type* k1 = (SIMD_type*) key;
102    SIMD_type* s2 = (SIMD_type*) (symbol + symbol_lgth - 16);
103    SIMD_type* k2 = (SIMD_type*) (key + key_lgth - 16);
104
105    SIMD_type result = simd<64>::eq(simd_or( simd_xor(*s1,*k1), simd_xor(*s2, *k2) ),
106                                    simd<1>::constant<0>());
107    SIMD_type* res = &result;
108    return *((bool*)res);
109#else
110    SIMD_type result = simd<64>::eq(simd_or( simd_xor(*((SIMD_type*) symbol),*((SIMD_type*) key)),
111                                             simd_xor(*((SIMD_type*) (symbol + symbol_lgth - 16)), *((SIMD_type*) (key + key_lgth - 16))) ),
112                                    simd<1>::constant<0>());
113    return *((bool*)(&result));
114#endif
115}
116
117/*********************DIVISION GROUPING COMPARISON*******************************/
118template <size_t L>
119inline bool div_equal_compare(const unsigned char * key, const unsigned char * symbol) {
120        return compare<L>(key, symbol);
121}
122
123
124//template<>
125//inline bool div_equal_compare<3>(const unsigned char * key, const unsigned char * symbol) {
126//    return ((* ((uint32_t *) key)) ==
127//                              ((* ((uint32_t *) symbol)) & (0xFFFFFF << LOW_BYTE_SHIFT))); // s4int32()
128//}
129
130//template<>
131//inline bool div_equal_compare<5>(const unsigned char * key, const unsigned char * symbol) {
132//    return ((* ((uint64_t *) key)) ==
133//                      ((* ((uint64_t *) symbol)) & (0xFFFFFFFFFFULL << (3 * LOW_BYTE_SHIFT)))); // s8int64()
134//}
135
136//template<>
137//inline bool div_equal_compare<6>(const unsigned char * key, const unsigned char * symbol) {
138//    return ((* ((uint64_t *) key)) ==
139//                      ((* ((uint64_t *) symbol)) & (0xFFFFFFFFFFFFULL << (2 * LOW_BYTE_SHIFT)))); // s8int64()
140//}
141
142//template<>
143//inline bool div_equal_compare<7>(const unsigned char * key, const unsigned char * symbol) {
144//    return ((* ((uint64_t *) key)) ==
145//                      ((* ((uint64_t *) symbol)) & (0xFFFFFFFFFFFFFFULL << LOW_BYTE_SHIFT))); // s8int64()
146//}
147
148
149// flip bit at position L
150template <size_t L>
151        inline int flipBit(const int value);
152
153template <> inline int flipBit<2>(const int value)
154{
155    return value ^ 0x2;
156}
157
158template <> inline int flipBit<4>(const int value)
159{
160    return value ^ 0x8;
161}
162
163template <> inline int flipBit<6>(const int value)
164{
165    return value ^ 0x20;
166}
167
168template <> inline int flipBit<8>(const int value)
169{
170    return value ^ 0x80;
171}
172
173template <> inline int flipBit<10>(const int value)
174{
175    return value ^ 0x200;
176}
177
178template <> inline int flipBit<12>(const int value)
179{
180    return value ^ 0x800;
181}
182
183template <> inline int flipBit<14>(const int value)
184{
185    return value ^ 0x2000;
186}
187
188template <> inline int flipBit<16>(const int value)
189{
190    return value ^ 0x8000;
191}
192#endif /* PBGS_DIV_UTILITIES_H_ */
Note: See TracBrowser for help on using the repository browser.