Быстрый способ «понизить масштаб» трехмерного индекса тензора

Question

Это немного крутой вопрос для C или C++. Я запускаю GCC 4.6.3 под Ubuntu 12.04.2.

У меня есть индекс p доступа к памяти для трехмерного тензора, имеет вид:

p = (i<<(2*N)) + (j<<N) + k 

Здесь 0 <= i,j,k < (1<<N) и N некоторое положительное целое число.

Теперь я хочу, чтобы вычислить «вниз масштабируется» индекс памяти доступа для i>>S, j>>S, k>>S с 0 < S < N, который был бы:

q = ((i>>S)<<(2*(N-S))) + ((j>>S)<<(N-S)) + (k>>S) 

Какой самый быстрый способ вычисления q из p (не зная i,j,k заранее) ? Можно предположить, что 0 < N <= 10 (т. Е. p - 32-битное целое число). Меня особенно интересовал бы быстрый подход для N=8 (т. Е. i,j,k - 8-битные целые числа). N и S являются константами времени компиляции.

Пример для N=8 и S=4:

unsigned int p = 240407; // this is (3<<16) + (171<<8) + 23; 
unsigned int q = 161; // this is (0<<8) + (10<<4) + 1 

Answer 1

прямолинейного способ, 8 операций (другие являются операциями по константам):

M = (1<<(N-S)) - 1;      // A mask with S lowest bits. 
q = ( ((p & (M<<(2*N+S))) >> (3*S)) // Mask 'i', shift to new position. 
    + ((p & (M<<( N+S))) >> (2*S)) // Likewise for 'j'. 
    + ((p & (M<<  S)) >> S)); // Likewise for 'k'. 

выглядит сложным, но на самом деле это не так, просто нелегко (по крайней мере, мне), чтобы все константы исправить.

Чтобы создать формулу с меньшим количеством операций, заметим, что смещение чисел на U бит влево совпадает с умножением на 1<<U. Таким образом, из-за размножения умножения умножение на ((1<<U1) + (1<<U2) + ...) такое же, как смещение влево на U1, U2, ... и добавление всего вместе.

Таким образом, мы могли бы попытаться замаскировать необходимые части из i, j и k, «сдвиг», чтобы они все правильные позиции по отношению друг к другу с одним умножением, а затем перенести результат вправо, к конечному пункту назначения. Это дает нам три операции для вычисления q от p.

К сожалению, существуют ограничения, особенно для случая, когда мы пытаемся получить все три одновременно. Когда мы добавляем числа вместе (косвенно, добавляя несколько множителей), мы должны убедиться, что биты могут быть установлены только в одном числе, иначе мы получим неправильный результат. Если мы пытаемся добавить (косвенно) три должным образом смещенными числа сразу, мы имеем следующее:

iiiii...........jjjjj...........kkkkk....... 
N-S  S  N-S  S  N-S 
.....jjjjj...........kkkkk................ 
N-S N-S  S  N-S 
..........kkkkk............... 
N-S N-S N-S 

Обратите внимание, что дальше налево во второй и третий номера являются биты i и j, но игнорировать их. Для этого предположим, что умножение работает как на x86: , умножая два типа. T дает номер типа T, с наименьшими битами фактического результата (равным результату, если нет переполнения).

Таким образом, чтобы убедиться, что k биты из третьих чисел не совпадают с j битами из первых, нам нужно, чтобы 3*(N-S) <= N, т.е. S >= 2*N/3, который для N = 8 ограничивает нас S >= 6 (всего один или два бита на компонент после сдвига , не знаю, используете ли вы эту низкую точность).

Однако, если S >= 2*N/3, мы можем использовать только три операции:

// Constant multiplier to perform three shifts at once. 
F = (1<<(32-3*N)) + (1<<(32-3*N+S)) + (1<<(32-3*N+2*S)); 
// Mask, shift/combine with multipler, right shift to destination. 
q = (((p & ((M<<(2*N+S)) + (M<<(N+S)) + (M<<S))) * F) 
    >> (32-3*(N-S))); 

Если ограничение для S является слишком строгим (что это вероятно), мы можем объединить первую и вторую формулу: вычислить i и k со вторым подходом, затем добавьте j из первой формулы. Здесь нам нужны, чтобы биты не перекрывались в следующих номерах:

iiiii...............kkkkk....... 
N-S S N-S S N-S 
..........kkkkk............... 
N-S N-S N-S 

I.e. 3*(N-S) <= 2*N, что дает S >= N/3, или, для N = 8 гораздо менее строгий S >= 3. Формула выглядит следующим образом:

// Constant multiplier to perform two shifts at once. 
F = (1<<(32-3*N)) + (1<<(32-3*N+2*S)); 
// Mask, shift/combine with multipler, right shift to destination 
// and then add 'j' from the straightforward formula. 
q = ((((p & ((M<<(2*N+S)) + (M<<S))) * F) >> (32-3*(N-S))) 
    + ((p & (M<<(N+S))) >> (2*S))); 

Эта формула работает для примера, где S = 4.

Является ли это более быстрым, чем простой подход, зависит от архитектуры. Кроме того, я понятия не имею, поддерживает ли C++ предполагаемое поведение переполнения умножения. Наконец, вам нужно удостовериться, что значения без знака и точно 32 бит для того, чтобы формулы работали.

Answer 2

ли это соответствовать вашим требованиям?

#include <cstdint> 
#include <iostream> 

uint32_t to_q_from_p(uint32_t p, uint32_t N, uint32_t S) 
{ 
    uint32_t mask = ~(~0 << N); 
    uint32_t k = p &mask; 
    uint32_t j = (p >> N)& mask; 
    uint32_t i = (p >> 2*N)&mask; 
    return ((i>>S)<<(2*(N-S))) + ((j>>S)<<(N-S)) + (k>>S);; 
} 

int main() 
{ 
    uint32_t p = 240407; 

    uint32_t q = to_q_from_p(p, 8, 4); 

    std::cout << q << '\n'; 

} 

если предположить, что N всегда 8 и целые числа мало младшему, то это может быть

uint32_t to_q_from_p(uint32_t p, uint32_t S) 
{ 
    auto ptr = reinterpret_cast<uint8_t*>(&p); 
    return ((ptr[2]>>S)<<(2*(8-S))) + ((ptr[1]>>S)<<(8-S)) + (ptr[0]>>S); 
} 

Answer 3

Если вы не заботиться о совместимости, для N = 8 можно получить I, J К так:

int p = .... 
unsigned char *bytes = (char *)&p; 

Теперь k является bytes[0], j является bytes[1] и i является bytes[2] (я нашел маленький конец ian на моей машине). Но я думаю, что лучший способ - это так. как то (мы имеем N_MASK = 2^N - 1)

int q; 
q = (p & N_MASK) >> S; 
p >>= N; 
q |= ((p & N_MASK) >> S) << S; 
p >>= N; 
q |= ((p & N_MASK) >> S) << 2*S;