15

Is there a clever (ie: branchless) way to "compact" a hex number. Basically move all the 0s all to one side?

eg:

0x10302040 -> 0x13240000

or

0x10302040 -> 0x00001324

I looked on Bit Twiddling Hacks but didn't see anything.

It's for a SSE numerical pivoting algorithm. I need to remove any pivots that become 0. I can use _mm_cmpgt_ps to find good pivots, _mm_movemask_ps to convert that in to a mask, and then bit hacks to get something like the above. The hex value gets munged in to a mask for a _mm_shuffle_ps instruction to perform a permutation on the SSE 128 bit register.

9
  • 3
    The BMI2 instruction set does exactly what you want - but only for bits. Perhaps there's a way to hack it to work on groups of 4 bits.
    – Mysticial
    Jul 2, 2014 at 19:11
  • 2
    _pext_u32 with a mask of 0xf0f0f0f0 does this, if you want to do it with SSE you can of course shift/mask/recombine
    – harold
    Jul 2, 2014 at 19:12
  • @harold I think the problem here is that the OP doesn't know where the zeros will be. But you could generate that mask with a few bit hacks.
    – Mysticial
    Jul 2, 2014 at 19:16
  • 1
    I don't know where the 0s will be before hand, no. They're the result of some other SSE math. BMI2 is great, but I'd like to support older SSE hardware if I can. Writing branching code is possible, but there's a certain elegance to branchless code, so if that's an option all the better.
    – Jay Lemmon
    Jul 2, 2014 at 19:44
  • 4
    What should happen with 0x01200340? What good is this compacting if you can't extract the original number?
    – RedX
    Jul 2, 2014 at 19:59

5 Answers 5

7

To compute mask for _pext:

mask = arg;
mask |= (mask << 1) & 0xAAAAAAAA | (mask >> 1) & 0x55555555;
mask |= (mask << 2) & 0xCCCCCCCC | (mask >> 2) & 0x33333333;

First do bit-or on pairs of bits, then on quads. Masks prevent shifted values from overflowing to other digits.

After computing mask this way or harold's way (which is probably faster) you don't need the full power of _pext, so if targeted hardware doesn't support it you can replace it with this:

for(int i = 0; i < 7; i++) {
    stay_mask = mask & (~mask - 1);
    arg = arg & stay_mask | (arg >> 4) & ~stay_mask;
    mask = stay_mask | (mask >> 4);
}

Each iteration moves all nibbles one digit to the right if there is some space. stay_mask marks bits that are in their final positions. This uses somewhat less operations than Hacker's Delight solution, but might still benefit from branching.

0
3

Supposing we can use _pext_u32, the issue then is computing a mask that has an F for every nibble that isn't zero. I'm not sure what the best approach is, but you can compute the OR of the 4 bits of the nibble and then "spread" it back out to F's like this:

// calculate horizontal OR of every nibble
x |= x >> 1;
x |= x >> 2;
// clean up junk
x &= 0x11111111;
// spread
x *= 0xF;

Then use that as the mask of _pext_u32.

_pext_u32 can be emulated by this (taken from Hacker's Delight, figure 7.6)

unsigned compress(unsigned x, unsigned m) {
   unsigned mk, mp, mv, t; 
   int i; 

   x = x & m;           // Clear irrelevant bits. 
   mk = ~m << 1;        // We will count 0's to right. 

   for (i = 0; i < 5; i++) {
      mp = mk ^ (mk << 1);             // Parallel prefix. 
      mp = mp ^ (mp << 2); 
      mp = mp ^ (mp << 4); 
      mp = mp ^ (mp << 8); 
      mp = mp ^ (mp << 16); 
      mv = mp & m;                     // Bits to move. 
      m = m ^ mv | (mv >> (1 << i));   // Compress m. 
      t = x & mv; 
      x = x ^ t | (t >> (1 << i));     // Compress x. 
      mk = mk & ~mp; 
   } 
   return x; 
}

But that's a bit of a disaster. It's probably better to just resort to branching code then.

2
uint32_t fun(uint32_t val) {
  uint32_t retVal(0x00);
  uint32_t sa(28);

  for (int sb(28); sb >= 0; sb -= 4) {
    if (val & (0x0F << sb)) {
      retVal |= (0x0F << sb) << (sa - sb)
      sa -= 4;
    }
  } 

  return retVal;
}

I think this (or something similar) is what you're looking for. Eliminating the 0 nibbles within a number. I've not debugged it, and it would only works on one side atm.

5
  • 2
    I love your usage of variable names, now what are sa and sb used for? Jul 2, 2014 at 19:32
  • I'm on my lunch break so didn't spend much time on this. The sa is to keep track of how many bits you're shifting the nibble in the result. sb, is the number of bits you're shifting the mask in the value. Taking the difference of them gives you how many bits you need to shift to eliminate the 0's between the nibble you're checking and the nibble you're attempting to 'fill'.
    – Aumnayan
    Jul 2, 2014 at 19:36
  • 2
    Unfortunately, the OP wants a branchless and performant method. This is just the straight-forward approach which the OP probably already has.
    – Mysticial
    Jul 2, 2014 at 19:39
  • Bah, missed the branchless bit.
    – Aumnayan
    Jul 2, 2014 at 19:41
  • Yes, A for effort, but I'm specifically looking for something branchless.
    – Jay Lemmon
    Jul 2, 2014 at 19:45
2

If your processor supports conditional instruction execution, you may get a benefit from this algorithm:

uint32_t compact(uint32_t orig_value)
{
    uint32_t mask = 0xF0000000u;  // Mask for isolating a hex digit.
    uint32_t new_value = 0u;
    for (unsigned int i = 0; i < 8; ++i) // 8 hex digits
    {
      if (orig_value & mask == 0u)
      {
          orig_value = orig_value << 4; // Shift the original value by 1 digit
      }
      new_value |= orig_value & mask;
      mask = mask >> 4;  // next digit
    }
    return new_value;
}

This looks like a good candidate for loop unrolling.

The algorithm assumes that when the original value is shifted left, zeros are shifted in, filling in the "empty" bits.

Edit 1: On a processor that supports conditional execution of instructions, the shifting of the original value would be conditionally executed depending on the result of the ANDing of the original value and the mask. Thus no branching, only ignored instructions.

-2

I came up with the following solution. Please take a look, maybe it will help you.

#include <iostream>
#include <sstream>
#include <algorithm>

using namespace std;

class IsZero
{
public:
    bool operator ()(char c)
    {
        return '0' == c;
    }
};

int main()
{
    int a = 0x01020334; //IMPUT

    ostringstream my_sstream;

    my_sstream << hex << a;

    string str = my_sstream.str();
    int base_str_length = str.size();

    cout << "Input hex: " << str << endl;

    str.insert(remove_if(begin(str), end(str), IsZero()), count_if(begin(str), end(str), IsZero()), '0');
    str.replace(begin(str) + base_str_length, end(str), "");

    cout << "Processed hex: " << str << endl;

    return 0;
}

Output:

Input hex: 1020334
Processed hex: 1233400
1
  • The question looks to be asking for an algorithm that operates on numbers, not strings. Also, a branchless algorithm was preferred. The remove_if and count_if very likely have branches inside of them. Decompiling might be illuminating here.
    – chwarr
    Jul 4, 2014 at 9:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.