source: trunk/symtab/ls_symbol_table_util_bytes.h @ 2136

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

SymbolTable?: commit some missing files

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