كيفية إزالة تشذير البتات بكفاءة (عكس مورتون)

Question

هذا السؤال: كيفية إزالة تشذير البتات (UnMortonizing؟) لديه إجابة جيدة لاستخراج أحد نصفي رقم مورتون (البتات الفردية فقط)، لكنني بحاجة إلى حل يستخرج كلا الجزأين (البتات الفردية والبتات الزوجية) في أقل عدد ممكن من العمليات.

لاستخدامي، سأحتاج إلى أخذ عدد صحيح من 32 بت واستخراج اثنين من int من 16 بت، حيث يكون أحدهما هو البتات الزوجية والآخر هو البتات الفردية التي تم إزاحتها لليمين بمقدار 1 بت، على سبيل المثال.

input,  z: 11101101 01010111 11011011 01101110

output, x: 11100001 10110111 // odd bits shifted right by 1
        y: 10111111 11011010 // even bits

يبدو أن هناك الكثير من الحلول التي تستخدم الإزاحات والأقنعة ذات الأرقام السحرية لتوليد أرقام مورتون (أي:البتات المتداخلة)، على سبيل المثال. تداخل البتات بواسطة الأرقام السحرية الثنائية, ، لكنني لم أجد حتى الآن أي شيء للقيام بالعكس (أي.إزالة التشذير).

تحديث

بعد إعادة قراءة القسم من Hacker's Delight حول عمليات الخلط/الخلط المثالية، وجدت بعض الأمثلة المفيدة التي قمت بتعديلها على النحو التالي:

// morton1 - extract even bits

uint32_t morton1(uint32_t x)
{
    x = x & 0x55555555;
    x = (x | (x >> 1)) & 0x33333333;
    x = (x | (x >> 2)) & 0x0F0F0F0F;
    x = (x | (x >> 4)) & 0x00FF00FF;
    x = (x | (x >> 8)) & 0x0000FFFF;
    return x;
}

// morton2 - extract odd and even bits

void morton2(uint32_t *x, uint32_t *y, uint32_t z)
{
    *x = morton1(z);
    *y = morton1(z >> 1);
}

أعتقد أنه لا يزال من الممكن تحسين هذا الأمر، سواء في شكله العددي الحالي أو أيضًا من خلال الاستفادة من SIMD، لذلك ما زلت مهتمًا بحلول أفضل (سواء العددية أو SIMD).

Answer 1

إذا كان معالجك يتعامل مع 64 بت ints بكفاءة، فيمكنك الجمع بين العمليات ... giveacodicetagpre.

Answer 2

رمز Intel Haswell وحقائب وحدات المعالجة المركزية لاحقا.يمكنك استخدام مجموعة تعليمات BMI2 التي تحتوي على إرشادات PEXT و PDEP.يمكن استخدام هذه (من بين أشياء رائعة أخرى) لبناء وظائفك. giveacodicetagpre.

Answer 3

في حالة استخدام شخص ما رموز مورتون ثلاثية الأبعاد، لذلك يحتاج إلى قراءة بت واحد كل 3، و 64 بت هنا هي الوظيفة التي استخدمتها: giveacodicetagpre.

Answer 4

إذا كنت بحاجة إلى سرعة مما يمكنك استخدام البحث عن الجدول لتحويل بايت واحد مرة واحدة (جدول بايت أسرع ولكن كبير).يتم إجراء الإجراء تحت ديلفي IDE ولكن المجمع / Algorithem هو نفسه. giveacodicetagpre.

Answer 5

لم أكن أريد أن أقتصر على عدد صحيح ذي حجم ثابت وإنشاء قوائم بأوامر مماثلة مع ثوابت مضمنة، لذلك قمت بتطوير حل C++ 11 الذي يستخدم البرمجة الوصفية للقالب لإنشاء الوظائف والثوابت.رمز التجميع الذي تم إنشاؤه باستخدام -O3 يبدو ضيقًا قدر الإمكان دون استخدام مؤشر كتلة الجسم:

andl    $0x55555555, %eax
movl    %eax, %ecx
shrl    %ecx
orl     %eax, %ecx
andl    $0x33333333, %ecx
movl    %ecx, %eax
shrl    $2, %eax
orl     %ecx, %eax
andl    $0xF0F0F0F, %eax
movl    %eax, %ecx
shrl    $4, %ecx
orl     %eax, %ecx
movzbl  %cl, %esi
shrl    $8, %ecx
andl    $0xFF00, %ecx
orl     %ecx, %esi

ليرة تركية؛ د الريبو المصدر و عرض حي.

---

تطبيق

في الأساس كل خطوة في morton1 تعمل الدالة عن طريق النقل والإضافة إلى سلسلة من الثوابت التي تبدو كما يلي:

1. 0b0101010101010101 (البديل 1 و 0)
2. 0b0011001100110011 (البديل 2x1 و0)
3. 0b0000111100001111 (البديل 4x1 و0)
4. 0b0000000011111111 (البديل 8x1 و0)

لو أردنا أن نستخدم D الأبعاد، سيكون لدينا نمط مع D-1 صفر و 1 واحد.لذلك، لإنشاء هذه العناصر، يكفي إنشاء وحدات متتالية وتطبيق بعض وحدات البت أو:

/// @brief Generates 0b1...1 with @tparam n ones
template <class T, unsigned n>
using n_ones = std::integral_constant<T, (~static_cast<T>(0) >> (sizeof(T) * 8 - n))>;

/// @brief Performs `@tparam input | (@tparam input << @tparam width` @tparam repeat times.
template <class T, T input, unsigned width, unsigned repeat>
struct lshift_add :
    public lshift_add<T, lshift_add<T, input, width, 1>::value, width, repeat - 1> {
};
/// @brief Specialization for 1 repetition, just does the shift-and-add operation.
template <class T, T input, unsigned width>
struct lshift_add<T, input, width, 1> : public std::integral_constant<T,
    (input & n_ones<T, width>::value) | (input << (width < sizeof(T) * 8 ? width : 0))> {
};

الآن يمكننا إنشاء الثوابت في وقت الترجمة للأبعاد العشوائية بما يلي:

template <class T, unsigned step, unsigned dimensions = 2u>
using mask = lshift_add<T, n_ones<T, 1 << step>::value, dimensions * (1 << step), sizeof(T) * 8 / (2 << step)>;

وبنفس نوع التكرار، يمكننا إنشاء وظائف لكل خطوة من خطوات الخوارزمية x = (x | (x >> K)) & M:

template <class T, unsigned step, unsigned dimensions>
struct deinterleave {
    static T work(T input) {
        input = deinterleave<T, step - 1, dimensions>::work(input);
        return (input | (input >> ((dimensions - 1) * (1 << (step - 1))))) & mask<T, step, dimensions>::value;
    }
};
// Omitted specialization for step 0, where there is just a bitwise and

يبقى أن نجيب على السؤال "كم عدد الخطوات التي نحتاجها؟".وهذا يعتمد أيضًا على عدد الأبعاد.على العموم، k حساب الخطوات 2^k - 1 بتات الإخراج؛يتم تحديد الحد الأقصى لعدد البتات ذات المعنى لكل بعد بواسطة z = sizeof(T) * 8 / dimensions, لذلك يكفي أن تأخذ 1 + log_2 z خطوات.المشكلة الآن هي أننا بحاجة إلى هذا كما constexpr من أجل استخدامه كمعلمة القالب.أفضل طريقة وجدتها للتغلب على هذه المشكلة هي التحديد log2 عبر البرمجة الفوقية:

template <unsigned arg>
struct log2 : public std::integral_constant<unsigned, log2<(arg >> 1)>::value + 1> {};
template <>
struct log2<1u> : public std::integral_constant<unsigned, 0u> {};

/// @brief Helper constexpr which returns the number of steps needed to fully interleave a type @tparam T.
template <class T, unsigned dimensions>
using num_steps = std::integral_constant<unsigned, log2<sizeof(T) * 8 / dimensions>::value + 1>;

وأخيرًا، يمكننا إجراء مكالمة واحدة:

/// @brief Helper function which combines @see deinterleave and @see num_steps into a single call.
template <class T, unsigned dimensions>
T deinterleave_first(T n) {
    return deinterleave<T, num_steps<T, dimensions>::value - 1, dimensions>::work(n);
}