source: trunk/symtab/ls_symbol_table_util.h @ 3584

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

SymbolTable?: Integrated symbol table with the new IDISA architecture

File size: 7.5 KB
Line 
1/*
2 * ls_symbol_table_util.h
3 *
4 *  Created on: 27-May-2010
5 *      Author: ksherdy
6 */
7
8#ifndef LS_SYMBOL_TABLE_UTIL_H_
9#define LS_SYMBOL_TABLE_UTIL_H_
10
11#include "library_conversion.h"
12
13// ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- -----
14// Utility Functions
15
16// TODO - Replace lookup functions with template meta-programming computation.
17
18                         // 0,1,2,3,4,5,6,7,8
19static const int BINS[] = {-1,0,1,2,3,4,5,6,7};
20
21static inline int get_lgth_bin(size_t lgth) {
22        return BINS[lgth];
23}
24
25static const int SYMBOL_PACK_COUNT[] = {-1,16,8,4,4,2,2,2,2};
26static const int SYMBOL_BYTES[] = {0,1,2,4,4,8,8,8,8};
27static const int SYMBOL_PADDING_BYTES[] = {-1,0,0,1,0,3,2,1,0};
28
29#define bsf(x) __builtin_ctz(x)
30
31// ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- -----
32// Map symbol lengths to field widths at compile time, 1->8,2->16,{3,4}->32,{5,6,7,8}->64.
33template <int lgth>
34struct fw {
35        static int const value = fw<(lgth-1)/2+1>::value*2;
36};
37
38template <>
39struct fw<1> {
40        static int const value = 8;
41};
42
43// ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- -----
44// Map symbol lengths to next power of 2 at compile time, 1->1,2->2,{3,4}->4,{5,6,7,8}->8,...
45
46template <int lgth>
47struct bin {
48        static int const value = bin<(lgth-1)/2+1>::value*2;
49};
50
51template <>
52struct bin<1> {
53        static int const value = 1;
54};
55
56
57// ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- -----
58// Template Definitions
59
60// ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- -----
61// Convert
62
63template<size_t>
64inline uint64_t convert(const unsigned char * p);
65
66template<>
67inline uint64_t convert<8>(const unsigned char * p) { 
68        return * ((uint8_t *) p);       
69}
70
71template<>
72inline uint64_t convert<16>(const unsigned char * p) {
73        return * ((uint16_t *) p);     
74}
75
76template<>
77inline uint64_t convert<32>(const unsigned char * p) {
78        return * ((uint32_t *) p);
79}
80
81template<>
82inline uint64_t convert<64>(const unsigned char * p) {
83        return * ((uint64_t *) p); 
84}
85
86// ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- -----
87// Increment
88
89template <size_t L>
90inline SIMD_type inc(SIMD_type v);
91
92const SIMD_type inc_mask_8 = _mm_set_epi8(1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1);
93const SIMD_type inc_mask_16 = _mm_set_epi16(1,1,1,1,1,1,1,1);
94const SIMD_type inc_mask_32 = _mm_set_epi32(1,1,1,1);
95const SIMD_type inc_mask_64 = _mm_set_epi32(0,1,0,1);
96
97template <>
98inline SIMD_type inc<8>(SIMD_type v) {
99  return simd<8>::add(v, inc_mask_8);   
100}
101
102template <>
103inline SIMD_type inc<16>(SIMD_type v) {
104  return simd<16>::add(v, inc_mask_16); 
105}
106
107template <>
108inline SIMD_type inc<32>(SIMD_type v) { 
109  return simd<32>::add(v, inc_mask_32);
110}
111
112template <>
113inline SIMD_type inc<64>(SIMD_type v) {
114  return simd<64>::add(v, inc_mask_64);
115}
116
117// ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- -----
118// Set contents of 'fully packed' SIMD registers
119
120template<size_t>
121inline SIMD_type set(unsigned char * p[]);
122
123template<>
124inline SIMD_type set<8>(unsigned char *p[]) {
125
126        return _mm_set_epi8(    convert<8>(p[15]),convert<8>(p[14]),
127                                convert<8>(p[13]),convert<8>(p[12]),
128                                convert<8>(p[11]),convert<8>(p[10]),
129                                convert<8>(p[9]),convert<8>(p[8]),
130                                convert<8>(p[7]),convert<8>(p[6]),
131                                convert<8>(p[5]),convert<8>(p[4]),
132                                convert<8>(p[3]),convert<8>(p[2]),
133                                convert<8>(p[1]),convert<8>(p[0]));
134       
135}
136
137template<>
138inline SIMD_type set<16>(unsigned char *p[]) {
139
140        return _mm_set_epi16(convert<16>(p[7]),convert<16>(p[6]),
141                                convert<16>(p[5]),convert<16>(p[4]),
142                                convert<16>(p[3]),convert<16>(p[2]),
143                                convert<16>(p[1]),convert<16>(p[0]));
144}
145
146template<>
147inline SIMD_type set<32>(unsigned char *p[]) {
148
149        return _mm_set_epi32(convert<32>(p[3]),
150                                convert<32>(p[2]),
151                                convert<32>(p[1]),
152                                convert<32>(p[0]));
153}
154
155template<>
156inline SIMD_type set<64>(unsigned char *p[]) {
157        return _mm_set_epi64x(convert<64>(p[1]),
158                                convert<64>(p[0]));
159}
160
161// ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- -----
162// Set contents of 'partially packed' SIMD registers
163
164template<size_t>
165inline SIMD_type set(unsigned char * p[], size_t size);
166
167template<>
168inline SIMD_type set<8>(unsigned char * p[], size_t size) {     
169
170        unsigned char v[16];
171        size_t i=0;
172        for(i;i<size;i++) {
173                v[i] = *p[i];
174        }
175
176        for(i;i<16;i++) {
177                v[i] = -1;
178        }
179
180        return _mm_set_epi8(    v[15],v[14],
181                                v[13],v[12],
182                                v[11],v[10],
183                                v[9],v[8],
184                                v[7],v[6],
185                                v[5],v[4],
186                                v[3],v[2],
187                                v[1],v[0]);
188}
189
190template<>
191inline SIMD_type set<16>(unsigned char * p[], size_t size) {   
192 
193        uint16_t v[8];
194        size_t i=0;
195        for(i;i<size;i++) {
196                v[i] = convert<16>(p[i]);
197        }
198
199        for(i;i<8;i++) {
200                v[i] = -1;
201        }
202
203        return _mm_set_epi16(v[7],v[6],v[5],v[4],v[3],v[2],v[1],v[0]);
204
205/*
206  Contiguous array approach code sample.
207
208  return  simd_or(sisd_load_unaligned((SIMD_type *) &p[0]),
209          simd<128>::sll(simd<1>::constant<1>(), sisd_from_int(8 << size)));
210*/
211}
212
213template<>
214inline SIMD_type set<32>(unsigned char * p[], size_t size) {
215
216        uint32_t v[4];
217        size_t i=0;
218        for(i;i<size;i++) {
219                v[i] = convert<32>(p[i]);
220        }
221
222        for(i;i<4;i++) {
223                v[i] = -1;
224        }
225
226        return _mm_set_epi32(v[3],v[2],v[1],v[0]);
227}
228
229template<>
230inline SIMD_type set<64>(unsigned char * p[], size_t size) {   
231        return _mm_set_epi64x(-1LL, convert<64>(p[0]));
232}
233
234// ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- -----
235// Splatted Key Masks
236
237template <size_t L>
238inline SIMD_type key_mask_splat(const unsigned char * p);
239
240template <>
241inline SIMD_type key_mask_splat<8>(const unsigned char * p) {
242  uint8_t temp = convert<8>(p);
243  return mvmd<8>::splat<0>(sisd_load_unaligned((SIMD_type *) &temp));
244}
245
246template <>
247inline SIMD_type key_mask_splat<16>(const unsigned char * p) {
248  uint16_t temp = convert<16>(p);
249  return mvmd<16>::splat<0>(sisd_load_unaligned((SIMD_type *) &temp));
250}
251
252template <>
253inline SIMD_type key_mask_splat<32>(const unsigned char * p) {
254  uint32_t temp = convert<32>(p);
255  return mvmd<32>::splat<0>(sisd_load_unaligned((SIMD_type *) &temp));
256}
257
258template <>
259inline SIMD_type key_mask_splat<64>(const unsigned char * p) {
260  uint64_t temp = convert<64>(p);
261  return mvmd<64>::splat<0>(sisd_load_unaligned((SIMD_type *) &temp));
262}
263
264// ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- -----
265// _SIDD_UNIT_MASK to symbol mask
266
267// TODO - SSE 4.2 introduces architecture dependence into the length sorted symbol table sort algorithm.
268
269#ifdef USE_SSE_4_2
270
271// umask_2_smask shuffle masks
272
273// TODO - 16 bit comparison may be a better approach
274
275const SIMD_type umask_2_smask_2 = _mm_set_epi8(0x0E,0x0E,0x0C,0x0C,0x0A,0x0A,0x08,0x08,0x06,0x06,0x04,0x04,0x02,0x02,0x00,0x00);
276const SIMD_type umask_2_smask_4 = _mm_set_epi8(0x0C,0x0C,0x0C,0x0C,0x08,0x08,0x08,0x08,0x04,0x04,0x04,0x04,0x00,0x00,0x00,0x00);
277const SIMD_type umask_2_smask_8 = _mm_set_epi8(0x08,0x08,0x08,0x08,0x08,0x08,0x08,0x08,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00);
278
279template <size_t L>
280inline SIMD_type umask_2_smask(SIMD_type v);
281
282template <>
283inline SIMD_type umask_2_smask<8>(SIMD_type v) {
284  return v;
285}
286
287template <>
288inline SIMD_type umask_2_smask<16>(SIMD_type v) {
289  return simd<8>::shuffle(v,umask_2_smask_2);
290}
291
292template <>
293inline SIMD_type umask_2_smask<32>(SIMD_type v) {
294  return simd<8>::shuffle(v,umask_2_smask_4);
295}
296
297template <>
298inline SIMD_type umask_2_smask<64>(SIMD_type v) {
299  return simd<8>::shuffle(v,umask_2_smask_8);
300}
301
302#endif
303
304#endif /* LS_SYMBOL_TABLE_UTIL_H_ */
Note: See TracBrowser for help on using the repository browser.