source: trunk/lib/symtab/equal_compare.h @ 1387

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

Symbol Table: Implemented division by 2 grouping strategy

File size: 4.3 KB
Line 
1/*
2 *      equal_compare.h
3 *
4 *      Created on: 8-August-2011
5 *      Author: Vera Lukman
6 *
7 *      Length specific comparison functions using a C++ function object or a C++ function template approach for Parallel Bitstream-Based Length Sorting identity and log grouping strategy.
8 */
9
10#ifndef EQUAL_COMPARE_H_
11#define EQUAL_COMPARE_H_
12
13#define TEMPLATED_SIMD_LIB
14
15//#define USE_MASK_COMPARE    //Comparison using masking technique.
16                            //This technique only applies for USE_LOG_SORT
17#include "../lib_simd.h"
18#include <string.h>
19#include "ls_symbol_table_compare.h"
20
21#define DEBUG_EQUAL_COMPARE 0
22
23// ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- -----
24// Equivalent symbol-at-a-time comparison methods implemented using C++ function templates.
25
26#if defined (USE_IDENTITY_SORT)
27//Use equal_compare<L> for L in [1,16]
28//Use equal_compare_32<L> for L in [17,32]
29
30template <size_t L>
31inline bool equal_compare(const unsigned char * key, const unsigned char * symbol) {
32        return compare<L>(key, symbol);
33}
34
35template<>
36inline bool 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 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 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 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#endif // #if defined (USE_IDENTITY_SORT)
59
60#if defined (USE_LOG_SORT)
61inline bool equal_compare_1(const unsigned char * key, const unsigned char * symbol) {
62    return compare<1>(key, symbol);
63}
64
65inline bool equal_compare_2(const unsigned char * key, const unsigned char * symbol) {
66    return compare<2>(key, symbol);
67}
68
69#ifdef USE_MASK_COMPARE
70inline bool equal_compare_4(const unsigned char * key, const unsigned char * symbol, int symbol_lgth) {
71    return ((* ((uint32_t *) key)) ==
72            ((* ((uint32_t *) symbol)) & ((0xFFFFFF | (3-symbol_lgth)) << ((4-symbol_lgth) * LOW_BYTE_SHIFT)) ));
73}
74#endif //USE_MASK_COMPARE
75
76template<class T>
77inline bool equal_compare(const unsigned char * key, const unsigned char * symbol, const unsigned int key_lgth, int symbol_lgth);
78
79// if key_lgth, symbol_lgth in [3,4], T = uint16_t
80// if key_lgth, symbol_lgth in [5,8], T = uint32_t
81// if key_lgth, symbol_lgth in [9,16], T = uint64_t
82// if key_lgth, symbol_lgth in [17,32], T = SIMD_type
83template<class T>
84inline bool equal_compare(const unsigned char * key, const unsigned char * symbol, const unsigned int key_lgth, int symbol_lgth)
85{
86#if DEBUG_EQUAL_COMPARE
87    int constant = sizeof(T);
88    T* s1 = (T*) symbol;
89    T* k1 = (T*) key;
90    T* s2 = (T*) (symbol + symbol_lgth - constant);
91    T* k2 = (T*) (key + key_lgth - constant);
92
93    return !((*s1 ^ *k1) | (*s2 ^ *k2));
94#else
95    return !((*((T*) symbol) ^ *((T*) key)) |
96             (*((T*) (symbol + symbol_lgth - sizeof(T))) ^ *((T*) (key + key_lgth - sizeof(T)))));
97#endif
98}
99
100template<>
101inline bool equal_compare<SIMD_type>(const unsigned char * key, const unsigned char * symbol, const unsigned int key_lgth, int symbol_lgth) {
102#if DEBUG_EQUAL_COMPARE
103    SIMD_type* s1 = (SIMD_type*) symbol;
104    SIMD_type* k1 = (SIMD_type*) key;
105    SIMD_type* s2 = (SIMD_type*) (symbol + symbol_lgth - 16);
106    SIMD_type* k2 = (SIMD_type*) (key + key_lgth - 16);
107
108    SIMD_type result = simd<64>::eq(simd_or( simd_xor(*s1,*k1), simd_xor(*s2, *k2) ),
109                                    simd<1>::constant<0>());
110    SIMD_type* res = &result;
111    return *((bool*)res);
112#else
113    SIMD_type result = simd<64>::eq(simd_or( simd_xor(*((SIMD_type*) symbol),*((SIMD_type*) key)),
114                                             simd_xor(*((SIMD_type*) (symbol + symbol_lgth - 16)), *((SIMD_type*) (key + key_lgth - 16))) ),
115                                    simd<1>::constant<0>());
116    return *((bool*)(&result));
117#endif
118}
119
120#endif //#if defined (USE_LOG_SORT)
121
122#endif /* EQUAL_COMPARE_H_ */
Note: See TracBrowser for help on using the repository browser.