← Back to branch summary

~ubuntu-branches/ubuntu/trusty/bmagic/trusty

« back to all changes in this revision

Viewing changes to src/bmsse2.h

  • Committer: Bazaar Package Importer
  • Author(s): Roberto C. Sanchez
  • Date: 2009-12-09 16:02:55 UTC
  • mfrom: (4.1.5 sid)
  • Revision ID: james.westby@ubuntu.com-20091209160255-hu2bnjrbncl92z5w
Tags: 3.6.1-1
New upstream release

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/bmsse2.h
 
1
#ifndef BMSSE2__H__INCLUDED__
 
2
#define BMSSE2__H__INCLUDED__
1
3
/*
2
4
Copyright(c) 2002-2009 Anatoliy Kuznetsov(anatoliy_kuznetsov at yahoo.com)
3
5
 
25
27
*/
26
28
 
27
29
 
28
 
#ifndef BMSSE2__H__INCLUDED__
29
 
#define BMSSE2__H__INCLUDED__
30
 
 
31
30
 
32
31
//    Header implements processor specific intrinsics declarations for SSE2
33
32
//    instruction set
34
33
#include<mmintrin.h>
35
34
#include<emmintrin.h>
36
35
 
 
36
#include "bmdef.h"
 
37
#include "bmsse_util.h"
37
38
 
38
39
 
39
40
namespace bm
44
45
 */
45
46
 
46
47
 
47
 
/*! 
48
 
  @brief SSE2 reinitialization guard class
49
 
 
50
 
  SSE2 requires to call _mm_empty() if we are intermixing
51
 
  MMX integer commands with floating point arithmetics.
52
 
  This class guards critical code fragments where SSE2 integer
53
 
  is used.
54
 
 
55
 
  @ingroup SSE2
56
 
 
57
 
*/
58
 
class sse2_empty_guard
59
 
{
60
 
public:
61
 
    BMFORCEINLINE sse2_empty_guard() 
62
 
    {
63
 
        _mm_empty();
64
 
    }
65
 
 
66
 
    BMFORCEINLINE ~sse2_empty_guard() 
67
 
    {
68
 
        _mm_empty();
69
 
    }
70
 
};
71
 
 
72
 
/*
73
 
# ifndef BM_SET_MMX_GUARD
74
 
#  define BM_SET_MMX_GUARD  sse2_empty_guard  bm_mmx_guard_;
75
 
# endif
76
 
*/
77
 
 
78
 
/*! 
79
 
    @brief XOR array elements to specified mask
80
 
    *dst = *src ^ mask
81
 
 
82
 
    @ingroup SSE2
83
 
*/
84
 
BMFORCEINLINE 
85
 
void sse2_xor_arr_2_mask(__m128i* BMRESTRICT dst, 
86
 
                         const __m128i* BMRESTRICT src, 
87
 
                         const __m128i* BMRESTRICT src_end,
88
 
                         bm::word_t mask)
89
 
{
90
 
     __m128i xmm2 = _mm_set_epi32(mask, mask, mask, mask);
91
 
     do
92
 
     {
93
 
        __m128i xmm1 = _mm_load_si128(src);
94
 
 
95
 
        xmm1 = _mm_xor_si128(xmm1, xmm2);
96
 
        _mm_store_si128(dst, xmm1);
97
 
        ++dst;
98
 
        ++src;
99
 
 
100
 
     } while (src < src_end);
101
 
}
102
 
 
103
 
/*! 
104
 
    @brief Inverts array elements and NOT them to specified mask
105
 
    *dst = ~*src & mask
106
 
 
107
 
    @ingroup SSE2
108
 
*/
109
 
BMFORCEINLINE 
110
 
void sse2_andnot_arr_2_mask(__m128i* BMRESTRICT dst, 
111
 
                            const __m128i* BMRESTRICT src, 
112
 
                            const __m128i* BMRESTRICT src_end,
113
 
                            bm::word_t mask)
114
 
{
115
 
     __m128i xmm2 = _mm_set_epi32(mask, mask, mask, mask);
116
 
     do
117
 
     {
118
 
        //_mm_prefetch((const char*)(src)+1024, _MM_HINT_NTA);
119
 
        //_mm_prefetch((const char*)(src)+1088, _MM_HINT_NTA);
120
 
 
121
 
        __m128i xmm1 = _mm_load_si128(src);
122
 
 
123
 
        xmm1 = _mm_andnot_si128(xmm1, xmm2); // xmm1 = (~xmm1) & xmm2 
124
 
        _mm_store_si128(dst, xmm1);
125
 
        ++dst;
126
 
        ++src;
127
 
 
128
 
     } while (src < src_end);
129
 
}
130
 
 
131
 
/*! 
132
 
    @brief AND array elements against another array
133
 
    *dst &= *src
134
 
 
135
 
    @ingroup SSE2
136
 
*/
137
 
BMFORCEINLINE 
138
 
void sse2_and_arr(__m128i* BMRESTRICT dst, 
139
 
                  const __m128i* BMRESTRICT src, 
140
 
                  const __m128i* BMRESTRICT src_end)
141
 
{
142
 
    __m128i xmm1, xmm2;
143
 
    do
144
 
    {
145
 
        _mm_prefetch((const char*)(src)+512,  _MM_HINT_NTA);
146
 
    
147
 
        xmm1 = _mm_load_si128(src++);
148
 
        xmm2 = _mm_load_si128(dst);
149
 
        xmm1 = _mm_and_si128(xmm1, xmm2);
150
 
        _mm_store_si128(dst++, xmm1);
151
 
        
152
 
        xmm1 = _mm_load_si128(src++);
153
 
        xmm2 = _mm_load_si128(dst);
154
 
        xmm1 = _mm_and_si128(xmm1, xmm2);
155
 
        _mm_store_si128(dst++, xmm1);
156
 
 
157
 
        xmm1 = _mm_load_si128(src++);
158
 
        xmm2 = _mm_load_si128(dst);
159
 
        xmm1 = _mm_and_si128(xmm1, xmm2);
160
 
        _mm_store_si128(dst++, xmm1);
161
 
 
162
 
        xmm1 = _mm_load_si128(src++);
163
 
        xmm2 = _mm_load_si128(dst);
164
 
        xmm1 = _mm_and_si128(xmm1, xmm2);
165
 
        _mm_store_si128(dst++, xmm1);
166
 
 
167
 
    } while (src < src_end);
168
 
 
169
 
}
170
 
 
171
 
 
172
 
 
173
 
/*! 
174
 
    @brief OR array elements against another array
175
 
    *dst |= *src
176
 
 
177
 
    @ingroup SSE2
178
 
*/
179
 
BMFORCEINLINE 
180
 
void sse2_or_arr(__m128i* BMRESTRICT dst, 
181
 
                 const __m128i* BMRESTRICT src, 
182
 
                 const __m128i* BMRESTRICT src_end)
183
 
{
184
 
    __m128i xmm1, xmm2;
185
 
    do
186
 
    {
187
 
        _mm_prefetch((const char*)(src)+512,  _MM_HINT_NTA);
188
 
    
189
 
        xmm1 = _mm_load_si128(src++);
190
 
        xmm2 = _mm_load_si128(dst);
191
 
        xmm1 = _mm_or_si128(xmm1, xmm2);
192
 
        _mm_store_si128(dst++, xmm1);
193
 
        
194
 
        xmm1 = _mm_load_si128(src++);
195
 
        xmm2 = _mm_load_si128(dst);
196
 
        xmm1 = _mm_or_si128(xmm1, xmm2);
197
 
        _mm_store_si128(dst++, xmm1);
198
 
 
199
 
        xmm1 = _mm_load_si128(src++);
200
 
        xmm2 = _mm_load_si128(dst);
201
 
        xmm1 = _mm_or_si128(xmm1, xmm2);
202
 
        _mm_store_si128(dst++, xmm1);
203
 
 
204
 
        xmm1 = _mm_load_si128(src++);
205
 
        xmm2 = _mm_load_si128(dst);
206
 
        xmm1 = _mm_or_si128(xmm1, xmm2);
207
 
        _mm_store_si128(dst++, xmm1);
208
 
 
209
 
    } while (src < src_end);
210
 
}
211
 
 
212
 
/*! 
213
 
    @brief OR array elements against another array
214
 
    *dst |= *src
215
 
 
216
 
    @ingroup SSE2
217
 
*/
218
 
BMFORCEINLINE 
219
 
void sse2_xor_arr(__m128i* BMRESTRICT dst, 
220
 
                  const __m128i* BMRESTRICT src, 
221
 
                  const __m128i* BMRESTRICT src_end)
222
 
{
223
 
    __m128i xmm1, xmm2;
224
 
    do
225
 
    {
226
 
        _mm_prefetch((const char*)(src)+512,  _MM_HINT_NTA);
227
 
    
228
 
        xmm1 = _mm_load_si128(src++);
229
 
        xmm2 = _mm_load_si128(dst);
230
 
        xmm1 = _mm_xor_si128(xmm1, xmm2);
231
 
        _mm_store_si128(dst++, xmm1);
232
 
        
233
 
        xmm1 = _mm_load_si128(src++);
234
 
        xmm2 = _mm_load_si128(dst);
235
 
        xmm1 = _mm_xor_si128(xmm1, xmm2);
236
 
        _mm_store_si128(dst++, xmm1);
237
 
 
238
 
        xmm1 = _mm_load_si128(src++);
239
 
        xmm2 = _mm_load_si128(dst);
240
 
        xmm1 = _mm_xor_si128(xmm1, xmm2);
241
 
        _mm_store_si128(dst++, xmm1);
242
 
 
243
 
        xmm1 = _mm_load_si128(src++);
244
 
        xmm2 = _mm_load_si128(dst);
245
 
        xmm1 = _mm_xor_si128(xmm1, xmm2);
246
 
        _mm_store_si128(dst++, xmm1);
247
 
 
248
 
    } while (src < src_end);
249
 
}
250
 
 
251
 
 
252
 
/*! 
253
 
    @brief AND-NOT (SUB) array elements against another array
254
 
    *dst &= ~*src
255
 
 
256
 
    @ingroup SSE2
257
 
*/
258
 
BMFORCEINLINE 
259
 
void sse2_sub_arr(__m128i* BMRESTRICT dst, 
260
 
                 const __m128i* BMRESTRICT src, 
261
 
                 const __m128i* BMRESTRICT src_end)
262
 
{
263
 
    __m128i xmm1, xmm2;
264
 
    do
265
 
    {
266
 
        _mm_prefetch((const char*)(src)+512,  _MM_HINT_NTA);
267
 
    
268
 
        xmm1 = _mm_load_si128(src++);
269
 
        xmm2 = _mm_load_si128(dst);
270
 
        xmm1 = _mm_andnot_si128(xmm1, xmm2);
271
 
        _mm_store_si128(dst++, xmm1);
272
 
        
273
 
        xmm1 = _mm_load_si128(src++);
274
 
        xmm2 = _mm_load_si128(dst);
275
 
        xmm1 = _mm_andnot_si128(xmm1, xmm2);
276
 
        _mm_store_si128(dst++, xmm1);
277
 
 
278
 
        xmm1 = _mm_load_si128(src++);
279
 
        xmm2 = _mm_load_si128(dst);
280
 
        xmm1 = _mm_andnot_si128(xmm1, xmm2);
281
 
        _mm_store_si128(dst++, xmm1);
282
 
 
283
 
        xmm1 = _mm_load_si128(src++);
284
 
        xmm2 = _mm_load_si128(dst);
285
 
        xmm1 = _mm_andnot_si128(xmm1, xmm2);
286
 
        _mm_store_si128(dst++, xmm1);
287
 
 
288
 
    } while (src < src_end);    
289
 
}
290
 
 
291
 
/*! 
292
 
    @brief SSE2 block memset
293
 
    *dst = value
294
 
 
295
 
    @ingroup SSE2
296
 
*/
297
 
 
298
 
BMFORCEINLINE 
299
 
void sse2_set_block(__m128i* BMRESTRICT dst, 
300
 
                    __m128i* BMRESTRICT dst_end, 
301
 
                    bm::word_t value)
302
 
{
303
 
    __m128i xmm0 = _mm_set_epi32 (value, value, value, value);
304
 
    do
305
 
    {            
306
 
        _mm_store_si128(dst, xmm0);
307
 
/*        
308
 
        _mm_store_si128(dst+1, xmm0);
309
 
        _mm_store_si128(dst+2, xmm0);
310
 
        _mm_store_si128(dst+3, xmm0);
311
 
 
312
 
        _mm_store_si128(dst+4, xmm0);
313
 
        _mm_store_si128(dst+5, xmm0);
314
 
        _mm_store_si128(dst+6, xmm0);
315
 
        _mm_store_si128(dst+7, xmm0);
316
 
 
317
 
        dst += 8;
318
 
*/        
319
 
    } while (++dst < dst_end);
320
 
    
321
 
    _mm_sfence();
322
 
}
323
 
 
324
 
/*! 
325
 
    @brief SSE2 block copy
326
 
    *dst = *src
327
 
 
328
 
    @ingroup SSE2
329
 
*/
330
 
BMFORCEINLINE 
331
 
void sse2_copy_block(__m128i* BMRESTRICT dst, 
332
 
                     const __m128i* BMRESTRICT src, 
333
 
                     const __m128i* BMRESTRICT src_end)
334
 
{
335
 
    __m128i xmm0, xmm1, xmm2, xmm3;
336
 
    do
337
 
    {
338
 
        _mm_prefetch((const char*)(src)+512,  _MM_HINT_NTA);
339
 
    
340
 
        xmm0 = _mm_load_si128(src+0);
341
 
        xmm1 = _mm_load_si128(src+1);
342
 
        xmm2 = _mm_load_si128(src+2);
343
 
        xmm3 = _mm_load_si128(src+3);
344
 
        
345
 
        _mm_store_si128(dst+0, xmm0);
346
 
        _mm_store_si128(dst+1, xmm1);
347
 
        _mm_store_si128(dst+2, xmm2);
348
 
        _mm_store_si128(dst+3, xmm3);
349
 
        
350
 
        xmm0 = _mm_load_si128(src+4);
351
 
        xmm1 = _mm_load_si128(src+5);
352
 
        xmm2 = _mm_load_si128(src+6);
353
 
        xmm3 = _mm_load_si128(src+7);
354
 
        
355
 
        _mm_store_si128(dst+4, xmm0);
356
 
        _mm_store_si128(dst+5, xmm1);
357
 
        _mm_store_si128(dst+6, xmm2);
358
 
        _mm_store_si128(dst+7, xmm3);
359
 
        
360
 
        src += 8;
361
 
        dst += 8;
362
 
        
363
 
    } while (src < src_end);    
364
 
}
365
 
 
366
 
 
367
 
/*! 
368
 
    @brief Invert array elements
369
 
    *dst = ~*dst
370
 
    or
371
 
    *dst ^= *dst 
372
 
 
373
 
    @ingroup SSE2
374
 
*/
375
 
BMFORCEINLINE 
376
 
void sse2_invert_arr(bm::word_t* first, bm::word_t* last)
377
 
{
378
 
    __m128i xmm1 = _mm_set_epi32(0xFFFFFFFF, 0xFFFFFFFF, 
379
 
                                 0xFFFFFFFF, 0xFFFFFFFF);
380
 
    __m128i* wrd_ptr = (__m128i*)first;
381
 
 
382
 
    do 
383
 
    {
384
 
        _mm_prefetch((const char*)(wrd_ptr)+512,  _MM_HINT_NTA);
385
 
        
386
 
        __m128i xmm0 = _mm_load_si128(wrd_ptr);
387
 
        xmm0 = _mm_xor_si128(xmm0, xmm1);
388
 
        _mm_store_si128(wrd_ptr, xmm0);
389
 
        ++wrd_ptr;
390
 
    } while (wrd_ptr < (__m128i*)last);
391
 
}
 
48
 
 
49
 
 
50
 
 
51
 
392
52
 
393
53
 
394
54
 
470
130
    return tcnt[0] + tcnt[1] + tcnt[2] + tcnt[3];
471
131
}
472
132
 
473
 
BMFORCEINLINE 
474
 
__m128i sse2_and(__m128i a, __m128i b)
475
 
{
476
 
    return _mm_and_si128(a, b);
477
 
}
478
 
 
479
 
BMFORCEINLINE 
480
 
__m128i sse2_or(__m128i a, __m128i b)
481
 
{
482
 
    return _mm_or_si128(a, b);
483
 
}
484
 
 
485
 
 
486
 
BMFORCEINLINE 
487
 
__m128i sse2_xor(__m128i a, __m128i b)
488
 
{
489
 
    return _mm_xor_si128(a, b);
490
 
}
491
 
 
492
 
BMFORCEINLINE 
493
 
__m128i sse2_sub(__m128i a, __m128i b)
494
 
{
495
 
    return _mm_andnot_si128(b, a);
496
 
}
497
133
 
498
134
 
499
135
template<class Func>
604
240
#define VECT_SET_BLOCK(dst, dst_end, value) \
605
241
    sse2_set_block((__m128i*) dst, (__m128i*) (dst_end), (value))
606
242
 
 
243
 
 
244
 
 
245
 
 
246
 
 
247
inline
 
248
bm::id_t sse2_bit_block_calc_count_change(const __m128i* BMRESTRICT block,
 
249
                                          const __m128i* BMRESTRICT block_end,
 
250
                                               unsigned* BMRESTRICT bit_count)
 
251
{
 
252
   const unsigned mu1 = 0x55555555;
 
253
   const unsigned mu2 = 0x33333333;
 
254
   const unsigned mu3 = 0x0F0F0F0F;
 
255
   const unsigned mu4 = 0x0000003F;
 
256
 
 
257
   // Loading masks
 
258
   __m128i m1 = _mm_set_epi32 (mu1, mu1, mu1, mu1);
 
259
   __m128i m2 = _mm_set_epi32 (mu2, mu2, mu2, mu2);
 
260
   __m128i m3 = _mm_set_epi32 (mu3, mu3, mu3, mu3);
 
261
   __m128i m4 = _mm_set_epi32 (mu4, mu4, mu4, mu4);
 
262
   __m128i mcnt, ccnt;
 
263
   mcnt = _mm_xor_si128(m1, m1); // bit_cnt = 0
 
264
   ccnt = _mm_xor_si128(m1, m1); // change_cnt = 0
 
265
 
 
266
   __m128i tmp1, tmp2;
 
267
 
 
268
   int count = (block_end - block)*4; //0;//1;
 
269
 
 
270
   bm::word_t  w, w0, w_prev;//, w_l;
 
271
   const int w_shift = sizeof(w) * 8 - 1;
 
272
   bool first_word = true;
 
273
 
 
274
   // first word
 
275
   {
 
276
       const bm::word_t* blk = (const bm::word_t*) block;
 
277
       w = w0 = blk[0];
 
278
       w ^= (w >> 1);
 
279
       BM_INCWORD_BITCOUNT(count, w);
 
280
       count -= (w_prev = (w0 >> w_shift)); // negative value correction
 
281
   }
 
282
 
 
283
   bm::id_t BM_ALIGN16 tcnt[4] BM_ALIGN16ATTR;
 
284
 
 
285
   do
 
286
   {
 
287
       // compute bit-count
 
288
       // ---------------------------------------------------------------------
 
289
       {
 
290
       __m128i b = _mm_load_si128(block);
 
291
 
 
292
       // w ^(w >> 1)
 
293
       tmp1 = _mm_srli_epi32(b, 1);       // tmp1 = b >> 1
 
294
       tmp2 = _mm_xor_si128(b, tmp1);     // tmp2 = tmp1 ^ b;
 
295
       _mm_store_si128((__m128i*)tcnt, tmp2);
 
296
       
 
297
 
 
298
       // compare with zero
 
299
       // SSE4: _mm_test_all_zero()
 
300
       {
 
301
           // b = (b & 0x55555555) + (b >> 1 & 0x55555555);
 
302
           //tmp1 = _mm_srli_epi32(b, 1);                    // tmp1 = (b >> 1 & 0x55555555)
 
303
           tmp1 = _mm_and_si128(tmp1, m1);
 
304
           tmp2 = _mm_and_si128(b, m1);                    // tmp2 = (b & 0x55555555)
 
305
           b    = _mm_add_epi32(tmp1, tmp2);               //  b = tmp1 + tmp2
 
306
 
 
307
           // b = (b & 0x33333333) + (b >> 2 & 0x33333333);
 
308
           tmp1 = _mm_srli_epi32(b, 2);                    // (b >> 2 & 0x33333333)
 
309
           tmp1 = _mm_and_si128(tmp1, m2);
 
310
           tmp2 = _mm_and_si128(b, m2);                    // (b & 0x33333333)
 
311
           b    = _mm_add_epi32(tmp1, tmp2);               // b = tmp1 + tmp2
 
312
 
 
313
           // b = (b + (b >> 4)) & 0x0F0F0F0F;
 
314
           tmp1 = _mm_srli_epi32(b, 4);                    // tmp1 = b >> 4
 
315
           b = _mm_add_epi32(b, tmp1);                     // b = b + (b >> 4)
 
316
           b = _mm_and_si128(b, m3);                       //& 0x0F0F0F0F
 
317
 
 
318
           // b = b + (b >> 8);
 
319
           tmp1 = _mm_srli_epi32 (b, 8);                   // tmp1 = b >> 8
 
320
           b = _mm_add_epi32(b, tmp1);                     // b = b + (b >> 8)
 
321
 
 
322
           // b = (b + (b >> 16)) & 0x0000003F;
 
323
           tmp1 = _mm_srli_epi32 (b, 16);                  // b >> 16
 
324
           b = _mm_add_epi32(b, tmp1);                     // b + (b >> 16)
 
325
           b = _mm_and_si128(b, m4);                       // (b >> 16) & 0x0000003F;
 
326
 
 
327
           mcnt = _mm_add_epi32(mcnt, b);                  // mcnt += b
 
328
       }
 
329
 
 
330
       }
 
331
       // ---------------------------------------------------------------------
 
332
       {
 
333
           //__m128i b = _mm_load_si128(block);
 
334
           // TODO: SSE4...
 
335
           //w = _mm_extract_epi32(b, i);               
 
336
 
 
337
           const bm::word_t* BMRESTRICT blk = (const bm::word_t*) block;
 
338
 
 
339
           if (first_word)
 
340
           {
 
341
               first_word = false;
 
342
           }
 
343
           else
 
344
           {
 
345
               if ((w0=blk[0]))
 
346
               {
 
347
                   BM_INCWORD_BITCOUNT(count, tcnt[0]);
 
348
                   count -= !(w_prev ^ (w0 & 1));
 
349
                   count -= w_prev = (w0 >> w_shift);
 
350
               }
 
351
               else
 
352
               {
 
353
                   count -= !w_prev; w_prev ^= w_prev;
 
354
               }  
 
355
           }
 
356
           if ((w0=blk[1]))
 
357
           {
 
358
               BM_INCWORD_BITCOUNT(count, tcnt[1]);
 
359
               count -= !(w_prev ^ (w0 & 1));
 
360
               count -= w_prev = (w0 >> w_shift);                    
 
361
           }
 
362
           else
 
363
           {
 
364
               count -= !w_prev; w_prev ^= w_prev;
 
365
           }    
 
366
           if ((w0=blk[2]))
 
367
           {
 
368
               BM_INCWORD_BITCOUNT(count, tcnt[2]);
 
369
               count -= !(w_prev ^ (w0 & 1));
 
370
               count -= w_prev = (w0 >> w_shift);                    
 
371
           }
 
372
           else
 
373
           {
 
374
               count -= !w_prev; w_prev ^= w_prev;
 
375
           }      
 
376
           if ((w0=blk[3]))
 
377
           {
 
378
               BM_INCWORD_BITCOUNT(count, tcnt[3]);
 
379
               count -= !(w_prev ^ (w0 & 1));
 
380
               count -= w_prev = (w0 >> w_shift);                    
 
381
           }
 
382
           else
 
383
           {
 
384
               count -= !w_prev; w_prev ^= w_prev;
 
385
           }               
 
386
       }
 
387
   } while (++block < block_end);
 
388
 
 
389
   _mm_store_si128((__m128i*)tcnt, mcnt);
 
390
   *bit_count = tcnt[0] + tcnt[1] + tcnt[2] + tcnt[3];
 
391
 
 
392
   return count;
 
393
}
 
394
 
607
395
} // namespace
608
396
 
 
397
 
 
398
 
 
399
 
609
400
#endif