quickstencil.c

#include <stdio.h>
#include <stdlib.h>

// This is a program for converting a binary image (little-endian)
// into a set of integers that indicate the position where the bit
// value changes.  It is much faster than going through bit-by-bit.

int main(int argc, char *argv[])
{
  static const int debruijn[32] =
  {
    0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8,
    31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
  };

  unsigned int state = 0;

  // loop through all the available words
  for (int i = 0; i < argc-1; i++)
  {
    unsigned int x = state ^ strtoul(argv[i+1], 0, 0);
    
    if (x != 0)
    {
      // gcc and clang will automatically optimize this to bwapl opcode
#ifdef WORDS_BIG_ENDIAN
      x = (x >> 24) | (x << 24) | ((x >> 8) & 0xff00u) | ((x << 8) & 0xff0000u);
#endif

      do
      {
        // isolate the lowest set bit
        unsigned int y = x & -x;
        // use a de Bruijn sequence to find out what bit is set
        int b = debruijn[(y * 0x077CB531u) >> 27];
        // set lower bits and invert 
        x = ~(x | (y - 1));
        // invert the state
        state = ~state;
        // add the current word offset
        b += 32*i;
        // output the result
        printf("%d ", b);
      }
      while (x);
    }
  }
  printf("\n");

  return 0;
}