debruijn.hh

Go to the documentation of this file.

/*
    @@@@@@@@  @@           @@@@@@   @@@@@@@@ @@
   /@@/////  /@@          @@////@@ @@////// /@@
   /@@       /@@  @@@@@  @@    // /@@       /@@
   /@@@@@@@  /@@ @@///@@/@@       /@@@@@@@@@/@@
   /@@////   /@@/@@@@@@@/@@       ////////@@/@@
   /@@       /@@/@@//// //@@    @@       /@@/@@
   /@@       @@@//@@@@@@ //@@@@@@  @@@@@@@@ /@@
   //       ///  //////   //////  ////////  //

   Copyright (c) 2016, Triad National Security, LLC
   All rights reserved.
                                                                              */
#pragma once

#include <cstddef>
#include <cstdint>

namespace flecsi {
namespace util {

//----------------------------------------------------------------------------//
//----------------------------------------------------------------------------//

class debruijn32_t
{

  // de Bruijn sequence
  //            binary: 0000 0111 0111 1100 1011 0101 0011 0001
  //               hex:    0    7    7    c    b    5    3    1
  static constexpr uint32_t seq_ = 0x077cb531;

  // Lookup table. Note that this depends on the specific de Bruijn
  // sequence that is being used.
  static constexpr uint32_t index_[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};

public:
  //--------------------------------------------------------------------------//
  //--------------------------------------------------------------------------//

  static constexpr uint32_t index(const uint32_t b) {
    // 1. &  Two's-complement to isolate the right-most set bit
    // 2. *  Shift and truncate the sequence by the isolated bit index
    // 3. >> Shift off all but the high log_2(32) bits to get the lookup index
    // 4. [] return the index from the lookup table
#if defined(_MSC_VER)
#pragma warning(push)
#pragma warning(disable : 4146) // unary minus operator applied to unsigned
                                // type, result still unsigned
#endif
    return index_[(b & -b) * seq_ >> 27];
#if defined(_MSC_VER)
#pragma warning(pop)
#endif
  } // index

}; // debruijn32_t

} // namespace util
} // namespace flecsi