if/else statement in SSE intrinsics

Question

I am trying to optimize a small piece of code with SSE intrinsics (I am a complete beginner on the topic), but I am a little stuck on the use of conditionals.

My original code is:

unsigned long c;
unsigned long constant = 0x12345678;
unsigned long table[256];
int n, k;

for( n = 0; n < 256; n++ )
{
  c = n;
  for( k = 0; k < 8; k++ )
    {
      if( c & 1 ) c = constant ^ (c >> 1);
      else c >>= 1;
    }
  table[n] = c;
}

The goal of this code is to compute a crc table (the constant can be any polynomial, it doesn't play a role here),

I suppose my optimized code would be something like:

__m128 x;
__m128 y;
__m128 *table;

x = _mm_set_ps(3, 2, 1, 0);
y = _mm_set_ps(3, 2, 1, 0);
//offset for incrementation
offset = _mm_set1_ps(4);

for( n = 0; n < 64; n++ )
{
    y = x;
    for( k = 0; k < 8; k++ )
    {
        //if do something with y
        //else do something with y
    }
    table[n] = y;
    x = _mm_add_epi32 (x, offset);
}

I have no idea how to go through the if-else statement, but I suspect there is a clever trick. Has anybody an idea on how to do that?

(Aside from this, my optimization is probably quite poor - any advice or correction on it would be treated with the greatest sympathy)

Sigmund

If the loops are not very huge then you should try to keep outer loop smaller than inner loops. This will cause lesser initializations of inner loops (i.e. it should be n < 8 and k < 64) – Proverbs

The for statement uses semicolons, not commas, to separate its components. – Offing

@Fred, oops, mistake when I copied into the editor, corrected. Thanks. – Sigmund

Couldn't you just have used the traditional method known as "copy-and-paste" instead of re-typing the code yourself? The stack overflow editor does support Ctrl+V, you know ;) – Offing

This copy-paste thing sounds like a high-end technology, it's probably not very reliable. I will use it when the early adopters will have tested it thoroughly. – Sigmund

Answer 1

You can get rid of the if/else entirely. Back in the days when I produced MMX assembly code, that was a common programming activity. Let me start with a series of transformations on the "false" statement:

c >>= 1;

c = c >> 1;

c = 0 ^ (c >> 1);

Why did I introduce the exclusive-or? Because exclusive-or is also found in the "true" statement:

c = constant ^ (c >> 1);

Note the similarity? In the "true" part, we xor with a constant, and in the false part, we xor with zero.

Now I'm going to show you a series of transformations on the entire if/else statement:

if (c & 1)
    c = constant ^ (c >> 1);          // same as before
else
    c =        0 ^ (c >> 1);          // just different layout

if (c & 1)
    c =  constant      ^ (c >> 1);
else
    c = (constant & 0) ^ (c >> 1);    // 0 == x & 0

if (c & 1)
    c = (constant & -1) ^ (c >> 1);   // x == x & -1
else
    c = (constant &  0) ^ (c >> 1);

Now the two branches only differ in the second argument to the binary-and, which can be calculated trivially from the condition itself, thus enabling us to get rid of the if/else:

c = (constant & -(c & 1)) ^ (c >> 1);

Disclaimer: This solution only works on a two's complement architecture where -1 means "all bits set".

Offing

Answer 2

The idea in SSE is to build both results and then blend the results together.

E.g. :

__m128i mask = ...; // some way to build mask[n] = 0x1
__m128i constant = ...;

__m128i tmp_c = _mm_xor_si128( _mm_srli_epis32( c, 1 ), constant );
__m128i tmp_c2 = _mm_srli_epis32( c, 1 );

__m128i v = _mm_cmpeq_epi32( c, mask );
tmp_c = _mm_and_epi32( tmp_c, mask );
tmp_c2 = _mm_andnot_si128( mask, tmp_c2 );
c = _mm_or_si128( tmp_c, tmp_c2 );
// or in sse4_1
c = _mm_blendv_epi8( tmp_c, tmp_c2, mask );

Note beside, this is not complete code, only to demonstrate the principle.

Maritzamariupol

Answer 3

The first step in efficiently computing CRC is using a wider basic unit than the bit. See here for an example of how to do this byte per byte.

Hirudin