Вращение растрового изображения на 90 градусов

Ответ 1

v = (v & 0x000000000f0f0f0fUL) << 004 | (v & 0x00000000f0f0f0f0UL) << 040 |
    (v & 0xf0f0f0f000000000UL) >> 004 | (v & 0x0f0f0f0f00000000UL) >> 040;
v = (v & 0x0000333300003333UL) << 002 | (v & 0x0000cccc0000ccccUL) << 020 | 
    (v & 0xcccc0000cccc0000UL) >> 002 | (v & 0x3333000033330000UL) >> 020;
v = (v & 0x0055005500550055UL) << 001 | (v & 0x00aa00aa00aa00aaUL) << 010 | 
    (v & 0xaa00aa00aa00aa00UL) >> 001 | (v & 0x5500550055005500UL) >> 010;

Ответ 2

Без использования каких-либо справочных таблиц я не могу видеть намного лучше, чем обрабатывать каждый бит отдельно:

unsigned long r = 0;
for (int i = 0; i < 64; ++i) {
    r += ((x >> i) & 1) << (((i % 8) * 8) + (7 - i / 8));
}

Ответ 3

Существует эффективный способ выполнения разворота бит, используя операции сдвига O (log n). Если вы интерпретируете 64-битный UINT как массив бит 8x8, то бит-разворот соответствует вращению на 180 градусов.

Половина этих сдвигов эффективно выполняет горизонтальное отражение; другая половина выполняет вертикальное отражение. Чтобы получить поворот на 90 и 270 градусов, ортогональное (то есть вертикальное или горизонтальное) отражение может быть объединено с диагональным отражением, но последнее остается неудобным.

typedef unsigned long long uint64;

uint64 reflect_vert (uint64 value)
{
    value = ((value & 0xFFFFFFFF00000000ull) >> 32) | ((value & 0x00000000FFFFFFFFull) << 32);
    value = ((value & 0xFFFF0000FFFF0000ull) >> 16) | ((value & 0x0000FFFF0000FFFFull) << 16);
    value = ((value & 0xFF00FF00FF00FF00ull) >>  8) | ((value & 0x00FF00FF00FF00FFull) <<  8);
    return value;
}

uint64 reflect_horiz (uint64 value)
{
    value = ((value & 0xF0F0F0F0F0F0F0F0ull) >> 4) | ((value & 0x0F0F0F0F0F0F0F0Full) << 4);
    value = ((value & 0xCCCCCCCCCCCCCCCCull) >> 2) | ((value & 0x3333333333333333ull) << 2);
    value = ((value & 0xAAAAAAAAAAAAAAAAull) >> 1) | ((value & 0x5555555555555555ull) << 1);
    return value;
}

uint64 reflect_diag (uint64 value)
{
    uint64 new_value = value & 0x8040201008040201ull; // stationary bits
    new_value |= (value & 0x0100000000000000ull) >> 49;
    new_value |= (value & 0x0201000000000000ull) >> 42;
    new_value |= (value & 0x0402010000000000ull) >> 35;
    new_value |= (value & 0x0804020100000000ull) >> 28;
    new_value |= (value & 0x1008040201000000ull) >> 21;
    new_value |= (value & 0x2010080402010000ull) >> 14;
    new_value |= (value & 0x4020100804020100ull) >>  7;
    new_value |= (value & 0x0080402010080402ull) <<  7;
    new_value |= (value & 0x0000804020100804ull) << 14;
    new_value |= (value & 0x0000008040201008ull) << 21;
    new_value |= (value & 0x0000000080402010ull) << 28;
    new_value |= (value & 0x0000000000804020ull) << 35;
    new_value |= (value & 0x0000000000008040ull) << 42;
    new_value |= (value & 0x0000000000000080ull) << 49;
    return new_value;
}

uint64 rotate_90 (uint64 value)
{
    return reflect_diag (reflect_vert (value));
}

uint64 rotate_180 (uint64 value)
{
    return reflect_horiz (reflect_vert (value));
}

uint64 rotate_270 (uint64 value)
{
    return reflect_diag (reflect_horiz (value));
}

В приведенном выше коде функция reflect_diag() по-прежнему требует много сдвигов. Я подозреваю, что эту функцию можно реализовать с меньшим количеством сдвигов, но я еще не нашел способ сделать это.

Ответ 4

Если вы сделаете это быстро, вы не должны возражать против поисковых таблиц.

Я бы разбил 64-битные целые числа на N-разрядные куски и просмотрел N бит-фрагментов в таблице значений транспонирования, выбранной положением. Если вы выберете N = 1, вам нужно 64 поиска в таблицах двух слотов, что относительно медленно. Если вы выберете N = 64, вам понадобится одна таблица и один поиск, но таблица огромна: -}

N = 8 кажется хорошим компромиссом. Вам понадобится 8 таблиц из 256 записей. Код должен выглядеть примерно так:

// value to transpose is in v, a long
long r; // result
r != byte0transpose[(v>>56)&0xFF];
r != byte1transpose[(v>>48)&0xFF];
r != byte2transpose[(v>>40)&0xFF];
r != byte3transpose[(v>>32)&0xFF];
r != byte4transpose[(v>>24)&0xFF];
r != byte5transpose[(v>>16)&0xFF];
r != byte6transpose[(v>>08)&0xFF];
r != byte7transpose[(v>>00)&0xFF];

Каждая таблица содержит предварительно вычисленные значения, которые "распространяют" смежные биты на входе через 64-битный транспонированный результат. В идеале вы должны вычислить это значение в автономном режиме и просто инициализируйте записи таблицы.

Если вам не нужна скорость, тогда стандартный массив транспонирует алгоритмы будут работать; просто индексируйте 64-разрядный бит, как если бы это был бит-массив.

У меня есть тайное подозрение, что можно было бы вычислить транспонирование, используя бит типа twiddling.

Ответ 5

Чтобы расширить мой комментарий к Ирау, вы можете использовать:

#define ROT_BIT_0(X)    X, (X)|0x1UL
#define ROT_BIT_1(X)    ROT_BIT_0(X), ROT_BIT_0((X) | 0x100UL)
#define ROT_BIT_2(X)    ROT_BIT_1(X), ROT_BIT_1((X) | 0x10000UL)
#define ROT_BIT_3(X)    ROT_BIT_2(X), ROT_BIT_2((X) | 0x1000000UL)
#define ROT_BIT_4(X)    ROT_BIT_3(X), ROT_BIT_3((X) | 0x100000000UL)
#define ROT_BIT_5(X)    ROT_BIT_4(X), ROT_BIT_4((X) | 0x10000000000UL)
#define ROT_BIT_6(X)    ROT_BIT_5(X), ROT_BIT_5((X) | 0x1000000000000UL)
#define ROT_BIT_7(X)    ROT_BIT_6(X), ROT_BIT_6((X) | 0x100000000000000UL)

static unsigned long rot90[256] = { ROT_BIT_7(0) };

unsigned long rotate90(unsigned long v)
{
    unsigned long r = 0;
    r |= rot90[(v>>56) & 0xff];
    r |= rot90[(v>>48) & 0xff] << 1;
    r |= rot90[(v>>40) & 0xff] << 2;
    r |= rot90[(v>>32) & 0xff] << 3;
    r |= rot90[(v>>24) & 0xff] << 4;
    r |= rot90[(v>>16) & 0xff] << 5;
    r |= rot90[(v>>8) & 0xff] << 6;
    r |= rot90[v & 0xff] << 7;
    return r;
}

Это зависит от "unsigned long", равного 64 битам, и, конечно, биты находятся в строчном порядке, при этом msb является верхним правым, что, кажется, имеет место в этом вопросе....

Ответ 6

Это довольно просто с использованием IA32 SIMD, там есть удобный код операции для извлечения каждого восьмого бита из 64-битного значения (это было написано с помощью DevStudio 2005):

char
  source [8] = {0, 0, 0, 0, 0, 0, 0, 0xd0},
  dest [8];

__asm
{
  mov ch,3
  movq xmm0,qword ptr [source]
Rotate2:
  lea edi,dest
  mov cl,8
Rotate1:
  pmovmskb eax,xmm0
  psllq xmm0,1
  stosb
  dec cl
  jnz Rotate1
  movq xmm0,qword ptr [dest]
  dec ch
  jnz Rotate2
}

Он поворачивает данные три раза (-270 градусов), так как +90 немного сложнее (нужно немного подумать)

Ответ 7

Если вы посмотрите на это как на двумерный массив, то у вас есть решение no? Просто сделайте строки новыми столбцами. Первая строка - последний столбец, второй - последний и т.д.

По крайней мере визуально это выглядит как ваше решение.

Ответ 8

возможно что-то подобное

for(int i = 0; i < 8; i++)
{
    for(int j = 0; j < 8; j++)
    {
        new_image[j*8+8-i] = image[i*8+j];
    }
}

Ответ 9

Если допустимый цикл с питанием if, формула для бит достаточно проста:

8>>Column - Row - 1

Столбец и строка индексируются 0.

Это дает вам следующее отображение:

 7 15 23 31 39 47 55 63
 6 14 22 ...
 5 ...
 4 ...
 3 ...
 2 ...
 1 ...
 0  8 16 24 32 40 48 54