source: trunk/lib/symtab/ls_symbol_table_util_bytes.h @ 1229

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

Reorganized SymbolTable? library

File size: 10.6 KB
Line 
1/*
2 * ls_symbol_table_util_bytes.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#define TEMPLATED_SIMD_LIB
12#include "lib/lib_simd.h"
13
14// ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- -----
15// Utility Functions
16
17// TODO - Replace lookup functions with compile time template meta-programming computations.
18
19          // BINS[i] for i= 0,1,2,3,4,5,6,7,8
20static const int BINS[] = {-1,0,1,2,3,4,5,6,7};
21
22static inline int get_lgth_bin(size_t lgth) {
23        return BINS[lgth];
24}
25
26static const int SYMBOL_PACK_COUNT[] = {-1,16,8,4,4,2,2,2,2};
27static const int SYMBOL_BYTES[] = {0,1,2,4,4,8,8,8,8};
28static const int SYMBOL_PADDING_BYTES[] = {-1,0,0,1,0,3,2,1,0};
29
30#ifdef USE_PACKED_SYMBOLS
31
32#define bsf(x) __builtin_ctz(x)
33
34// ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- -----
35// Map symbol lengths to field widths at compile time, 1->8,2->16,{3,4}->32,{5,6,7,8}->64.
36template <int lgth>
37struct fw {
38        static int const value = fw<(lgth-1)/2+1>::value*2;
39};
40
41template <>
42struct fw<1> {
43        static int const value = 8;
44};
45
46// ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- -----
47// Template Definitions
48
49// ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- -----
50// Convert
51
52template<size_t>
53inline uint64_t convert(const unsigned char * p);
54
55template<>
56inline uint64_t convert<1>(const unsigned char * p) { 
57        return * ((uint8_t *) p);       
58}
59
60template<>
61inline uint64_t convert<2>(const unsigned char * p) {
62        return * ((uint16_t *) p);     
63}
64
65template<>
66inline uint64_t convert<3>(const unsigned char * p) { // evaluates as a | b
67        return (* ((uint32_t *) p) | (0xFF << (3 * HIGH_BYTE_SHIFT)));                 
68}
69
70template<>
71inline uint64_t convert<4>(const unsigned char * p) {
72        return * ((uint32_t *) p);
73}
74
75template<>
76inline uint64_t convert<5>(const unsigned char * p) {
77        return (* ((uint64_t *) p) | (0xFFFFFFULL << (5 * HIGH_BYTE_SHIFT))); 
78}
79
80template<>
81inline uint64_t convert<6>(const unsigned char * p) {
82        return (* ((uint64_t *) p) | (0xFFFFULL << (6 * HIGH_BYTE_SHIFT))); 
83}
84
85template<>
86inline uint64_t convert<7>(const unsigned char * p) {
87        return (* ((uint64_t *) p) | (0xFFULL << (7 * HIGH_BYTE_SHIFT))); 
88}
89
90template<>
91inline uint64_t convert<8>(const unsigned char * p) {
92        return * ((uint64_t *) p); 
93}
94
95// ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- -----
96// Increment
97
98template <size_t L>
99inline SIMD_type inc(SIMD_type v);
100
101const SIMD_type inc_mask_8 = _mm_set_epi8(1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1);
102const SIMD_type inc_mask_16 = _mm_set_epi16(1,1,1,1,1,1,1,1);
103const SIMD_type inc_mask_32 = _mm_set_epi32(1,1,1,1);
104const SIMD_type inc_mask_64 = _mm_set_epi32(0,1,0,1);
105
106template <>
107inline SIMD_type inc<1>(SIMD_type v) {
108  return simd<fw<1>::value>::add(v, inc_mask_8);       
109}
110
111template <>
112inline SIMD_type inc<2>(SIMD_type v) {
113  return simd<fw<2>::value>::add(v, inc_mask_16);       
114}
115
116template <>
117inline SIMD_type inc<3>(SIMD_type v) {
118  return simd<fw<3>::value>::add(v, inc_mask_32);
119}
120
121template <>
122inline SIMD_type inc<4>(SIMD_type v) { 
123  return simd<fw<4>::value>::add(v, inc_mask_32);
124}
125
126template <>
127inline SIMD_type inc<5>(SIMD_type v) {
128  return simd<fw<5>::value>::add(v, inc_mask_64);
129}
130
131template <>
132inline SIMD_type inc<6>(SIMD_type v) {
133  return simd<fw<6>::value>::add(v, inc_mask_64);
134}
135
136template <>
137inline SIMD_type inc<7>(SIMD_type v) {
138  return simd<fw<7>::value>::add(v, inc_mask_64);
139}
140
141template <>
142inline SIMD_type inc<8>(SIMD_type v) {
143  return simd<fw<8>::value>::add(v, inc_mask_64);
144}
145
146// ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- -----
147// Set contents of 'fully packed' SIMD registers
148
149template<size_t>
150inline SIMD_type set(unsigned char * p[]);
151
152template<>
153inline SIMD_type set<1>(unsigned char *p[]) {
154
155        return _mm_set_epi8(    convert<1>(p[15]),convert<1>(p[14]),
156                                convert<1>(p[13]),convert<1>(p[12]),
157                                convert<1>(p[11]),convert<1>(p[10]),
158                                convert<1>(p[9]),convert<1>(p[8]),
159                                convert<1>(p[7]),convert<1>(p[6]),
160                                convert<1>(p[5]),convert<1>(p[4]),
161                                convert<1>(p[3]),convert<1>(p[2]),
162                                convert<1>(p[1]),convert<1>(p[0]));
163       
164}
165
166template<>
167inline SIMD_type set<2>(unsigned char *p[]) {
168
169        return _mm_set_epi16(convert<2>(p[7]),convert<2>(p[6]),
170                                convert<2>(p[5]),convert<2>(p[4]),
171                                convert<2>(p[3]),convert<2>(p[2]),
172                                convert<2>(p[1]),convert<2>(p[0]));
173}
174
175
176template<>
177inline SIMD_type set<3>(unsigned char *p[]) {
178
179        return _mm_set_epi32(convert<3>(p[3]),
180                             convert<3>(p[2]),
181                             convert<3>(p[1]),
182                             convert<3>(p[0]));
183}
184
185template<>
186inline SIMD_type set<4>(unsigned char *p[]) {
187
188        return _mm_set_epi32(convert<4>(p[3]),
189                                convert<4>(p[2]),
190                                convert<4>(p[1]),
191                                convert<4>(p[0]));
192}
193
194template<>
195inline SIMD_type set<5>(unsigned char *p[]) {
196
197        return _mm_set_epi64x(convert<5>(p[1]),
198                                convert<5>(p[0]));
199}
200
201template<>
202inline SIMD_type set<6>(unsigned char *p[]) {
203
204        return _mm_set_epi64x(convert<6>(p[1]),
205                                convert<6>(p[0]));
206}
207
208template<>
209inline SIMD_type set<7>(unsigned char *p[]) {
210
211        return _mm_set_epi64x(convert<7>(p[1]),
212                                convert<7>(p[0]));
213}
214
215template<>
216inline SIMD_type set<8>(unsigned char *p[]) {
217        return _mm_set_epi64x(convert<8>(p[1]),
218                                convert<8>(p[0]));
219}
220
221// ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- -----
222// Set contents of 'partially packed' SIMD registers
223
224template<size_t>
225inline SIMD_type set(unsigned char * p[], size_t size);
226
227template<>
228inline SIMD_type set<1>(unsigned char * p[], size_t size) {     
229
230        unsigned char v[16];
231        size_t i=0;
232        for(i;i<size;i++) {
233                v[i] = *p[i];
234        }
235
236        for(i;i<16;i++) {
237                v[i] = -1;
238        }
239
240        return _mm_set_epi8(    v[15],v[14],
241                                v[13],v[12],
242                                v[11],v[10],
243                                v[9],v[8],
244                                v[7],v[6],
245                                v[5],v[4],
246                                v[3],v[2],
247                                v[1],v[0]);
248}
249
250template<>
251inline SIMD_type set<2>(unsigned char * p[], size_t size) {     
252 
253        uint16_t v[8];
254        size_t i=0;
255        for(i;i<size;i++) {
256                v[i] = convert<2>(p[i]);
257        }
258
259        for(i;i<8;i++) {
260                v[i] = -1;
261        }
262
263        return _mm_set_epi16(v[7],v[6],v[5],v[4],v[3],v[2],v[1],v[0]);
264
265/*
266  Contiguous array approach code sample.
267
268  return  simd_or(sisd_load_unaligned((SIMD_type *) &p[0]),
269          simd<128>::sll(simd<1>::constant<1>(), sisd_from_int(8 << size)));
270*/
271}
272
273template<>
274inline SIMD_type set<3>(unsigned char * p[], size_t size) {
275
276        uint32_t v[4];
277        size_t i=0;
278        for(i;i<size;i++) {
279                v[i] = convert<3>(p[i]);
280        }
281
282        for(i;i<4;i++) {
283                v[i] = -1;
284        }
285
286        return _mm_set_epi32(v[3],v[2],v[1],v[0]);
287}
288
289template<>
290inline SIMD_type set<4>(unsigned char * p[], size_t size) {
291
292        uint32_t v[4];
293        size_t i=0;
294        for(i;i<size;i++) {
295                v[i] = convert<4>(p[i]);
296        }
297
298        for(i;i<4;i++) {
299                v[i] = -1;
300        }
301
302        return _mm_set_epi32(v[3],v[2],v[1],v[0]);
303}
304
305template<>
306inline SIMD_type set<5>(unsigned char * p[], size_t size) {     
307        return _mm_set_epi64x(-1LL, convert<5>(p[0]));
308}
309
310template<>
311inline SIMD_type set<6>(unsigned char * p[], size_t size) {     
312        return _mm_set_epi64x(-1LL, convert<6>(p[0]));
313}
314
315template<>
316inline SIMD_type set<7>(unsigned char * p[], size_t size) {     
317        return _mm_set_epi64x(-1LL, convert<7>(p[0]));
318}
319
320template<>
321inline SIMD_type set<8>(unsigned char * p[], size_t size) {     
322        return _mm_set_epi64x(-1LL, convert<8>(p[0]));
323}
324
325// ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- -----
326// Splatted Key Masks
327
328template <size_t L>
329inline SIMD_type key_mask_splat(const unsigned char * p);
330
331template <>
332inline SIMD_type key_mask_splat<1>(const unsigned char * p) {
333  uint8_t temp = convert<1>(p);
334  return simd<fw<1>::value>::splat(sisd_load_unaligned((SIMD_type *) &temp));
335}
336
337template <>
338inline SIMD_type key_mask_splat<2>(const unsigned char * p) {
339  uint16_t temp = convert<2>(p);
340  return simd<fw<2>::value>::splat(sisd_load_unaligned((SIMD_type *) &temp));
341}
342
343template <>
344inline SIMD_type key_mask_splat<3>(const unsigned char * p) {
345  uint32_t temp = convert<3>(p);
346  return simd<fw<3>::value>::splat(sisd_load_unaligned((SIMD_type *) &temp));
347}
348
349template <>
350inline SIMD_type key_mask_splat<4>(const unsigned char * p) {
351  uint32_t temp = convert<4>(p);
352  return simd<fw<4>::value>::splat(sisd_load_unaligned((SIMD_type *) &temp));
353}
354
355template <>
356inline SIMD_type key_mask_splat<5>(const unsigned char * p) { 
357  uint64_t temp = convert<5>(p);
358  return simd<fw<5>::value>::splat(sisd_load_unaligned((SIMD_type *) &temp));
359}
360
361template <>
362inline SIMD_type key_mask_splat<6>(const unsigned char * p) {
363  uint64_t temp = convert<6>(p);
364  return simd<fw<6>::value>::splat(sisd_load_unaligned((SIMD_type *) &temp));
365}
366
367template <>
368inline SIMD_type key_mask_splat<7>(const unsigned char * p) {
369  uint64_t temp = convert<7>(p);
370  return simd<fw<7>::value>::splat(sisd_load_unaligned((SIMD_type *) &temp));
371}
372
373template <>
374inline SIMD_type key_mask_splat<8>(const unsigned char * p) {
375  uint64_t temp = convert<8>(p);
376  return simd<fw<8>::value>::splat(sisd_load_unaligned((SIMD_type *) &temp));
377}
378
379// ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- -----
380// _SIDD_UNIT_MASK to symbol mask
381
382// TODO - SSE 4.2 introduces architecture dependence into the length sorted symbol table sort algorithm.
383
384#ifdef USE_SSE_4_2
385
386// umask_2_smask shuffle masks
387const 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);
388const 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);
389const 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);
390
391template <size_t L>
392inline SIMD_type umask_2_smask(SIMD_type v);
393
394template <>
395inline SIMD_type umask_2_smask<1>(SIMD_type v) {
396  return v;
397}
398
399// TODO - 16 bit comparison is a better approach
400template <>
401inline SIMD_type umask_2_smask<2>(SIMD_type v) {
402  return simd<8>::shuffle(v,umask_2_smask_2);
403}
404
405template <>
406inline SIMD_type umask_2_smask<3>(SIMD_type v) {
407  return simd<8>::shuffle(v,umask_2_smask_4);
408}
409
410template <>
411inline SIMD_type umask_2_smask<4>(SIMD_type v) {
412  return simd<8>::shuffle(v,umask_2_smask_4);
413}
414
415template <>
416inline SIMD_type umask_2_smask<5>(SIMD_type v) {
417  return simd<8>::shuffle(v,umask_2_smask_8);
418}
419
420template <>
421inline SIMD_type umask_2_smask<6>(SIMD_type v) {
422  return simd<8>::shuffle(v,umask_2_smask_8);
423}
424
425template <>
426inline SIMD_type umask_2_smask<7>(SIMD_type v) {
427  return simd<8>::shuffle(v,umask_2_smask_8);
428}
429
430template <>
431inline SIMD_type umask_2_smask<8>(SIMD_type v) {
432  return simd<8>::shuffle(v,umask_2_smask_8);
433}
434
435#endif
436
437#endif /* USE_PACKED_SYMBOLS */
438
439#ifdef USE_PARALLEL_TRIE
440
441#endif /* USE_PARALLEL_TRIE */
442
443
444#endif /* LS_SYMBOL_TABLE_UTIL_H_ */
Note: See TracBrowser for help on using the repository browser.