source: trunk/symtab/pbgs_utilities.h @ 4004

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

SymbolTable?: use non-alphabets as general delimiter

File size: 6.9 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
123template<>
124inline bool div_equal_compare<3>(const unsigned char * key, const unsigned char * symbol) {
125    return ((* ((uint32_t *) key)) ==
126                                ((* ((uint32_t *) symbol)) & (0xFFFFFF << LOW_BYTE_SHIFT))); // s4int32()
127}
128
129template<>
130inline bool div_equal_compare<5>(const unsigned char * key, const unsigned char * symbol) {
131    return ((* ((uint64_t *) key)) ==
132                        ((* ((uint64_t *) symbol)) & (0xFFFFFFFFFFULL << (3 * LOW_BYTE_SHIFT)))); // s8int64()
133}
134
135template<>
136inline bool div_equal_compare<6>(const unsigned char * key, const unsigned char * symbol) {
137    return ((* ((uint64_t *) key)) ==
138                        ((* ((uint64_t *) symbol)) & (0xFFFFFFFFFFFFULL << (2 * LOW_BYTE_SHIFT)))); // s8int64()
139}
140
141template<>
142inline bool div_equal_compare<7>(const unsigned char * key, const unsigned char * symbol) {
143    return ((* ((uint64_t *) key)) ==
144                        ((* ((uint64_t *) symbol)) & (0xFFFFFFFFFFFFFFULL << LOW_BYTE_SHIFT))); // s8int64()
145}
146
147
148// flip bit at position L
149template <size_t L>
150        inline int flipBit(const int value);
151
152template <> inline int flipBit<2>(const int value)
153{
154    return value ^ 0x2;
155}
156
157template <> inline int flipBit<4>(const int value)
158{
159    return value ^ 0x8;
160}
161
162template <> inline int flipBit<6>(const int value)
163{
164    return value ^ 0x20;
165}
166
167template <> inline int flipBit<8>(const int value)
168{
169    return value ^ 0x80;
170}
171
172template <> inline int flipBit<10>(const int value)
173{
174    return value ^ 0x200;
175}
176
177template <> inline int flipBit<12>(const int value)
178{
179    return value ^ 0x800;
180}
181
182template <> inline int flipBit<14>(const int value)
183{
184    return value ^ 0x2000;
185}
186
187template <> inline int flipBit<16>(const int value)
188{
189    return value ^ 0x8000;
190}
191
192// Returns a mask for L bits
193// eg. mask<3> returns 0x7 (0000...00111)
194template <size_t L>
195        inline unsigned int maskBit()
196{
197    return ~(~0 << L);
198}
199
200//                           0     1     2    3     4    5    6    7
201static char XMLdelimiters[] = {' ', '\0', '\0', ';', '\0', '=', '>', '/'};
202
203static inline bool isXMLDelimiter(const char c)
204{
205    return c == XMLdelimiters[(unsigned int) c & 0x7];
206}
207
208static inline bool isGeneralDelimiter(const char c)
209{
210    return !(('A' <= c && c <= 'Z') || ('a' <= c && c <= 'z'));
211}
212
213#endif /* PBGS_DIV_UTILITIES_H_ */
Note: See TracBrowser for help on using the repository browser.