Поверните большой кусок памяти назад, быстро

Ответ 1

Там классический способ сделать это. Пусть say unsigned int - ваше 32-битное слово. Я использую C99, потому что ключевое слово restrict позволяет компилятору выполнять дополнительные оптимизации в этом критическом по скорости коде, который в противном случае был бы недоступен. Эти ключевые слова информируют компилятор о том, что "src" и "dest" не перекрываются. Это также предполагает, что вы копируете целое число слов, если вы этого не сделаете, то это только начало.

Я также не знаю, какие примитивы смещения бит/вращения быстро работают на ARM, а какие медленные. Это то, что нужно учитывать. Если вам нужна более высокая скорость, подумайте о разборке вывода из компилятора C и оттуда. Если вы используете GCC, попробуйте O2, O3 и Os, чтобы узнать, какая из них самая быстрая. Вы можете уменьшить количество киосков в трубопроводе, выполнив одновременно два слова.

Это использует 23 операции за слово, не считая загрузки и хранения. Однако эти 23 операции выполняются очень быстро, и никто из них не получает доступ к памяти. Я не знаю, будет ли таблица поиска быстрее или нет.

void
copy_rev(unsigned int *restrict dest,
         unsigned int const *restrict src,
         unsigned int n)
{
    unsigned int i, x;
    for (i = 0; i < n; ++i) {
        x = src[i];
        x = (x >> 16) | (x << 16);
        x = ((x >> 8) & 0x00ff00ffU) | ((x & 0x00ff00ffU) << 8);
        x = ((x >> 4) & 0x0f0f0f0fU) | ((x & 0x0f0f0f0fU) << 4);
        x = ((x >> 2) & 0x33333333U) | ((x & 0x33333333U) << 2);
        x = ((x >> 1) & 0x55555555U) | ((x & 0x555555555) << 1);
        dest[n-1-i] = x;
    }
}

Эта страница - отличная ссылка: http://graphics.stanford.edu/~seander/bithacks.html#BitReverseObvious

Заключительное примечание. Если посмотреть на ссылку сборки ARM, есть код операции "REV", который меняет порядок байтов в слове. Это приведет к бритью 7 операций за цикл с вышеуказанного кода.

Ответ 2

Самый быстрый способ, вероятно, сохранить обратную сторону всех возможных значений байтов в справочной таблице. В таблице потребуется всего 256 байт.

Ответ 3

Создайте таблицу поиска элементов из 256 элементов байтов, которые поменяются по битам из их индекса.

{0x00, 0x80, 0x40, 0xc0 и т.д.}

Затем повторите операцию по копированию массива с использованием каждого байта в качестве индекса в вашу таблицу поиска.

Если вы пишете язык ассемблера, набор инструкций x86 имеет инструкцию XLAT, которая выполняет только этот вид поиска. Хотя на современных процессорах он может быть не быстрее кода C.

Вы можете сделать это на месте, если вы перейдете с обоих концов к середине. Из-за эффектов кеша, вы можете быстрее найти swap в 16 байтовых блоках (при условии, что строка в 16 байт кэша).

Здесь базовый код (не включая оптимизацию строки кэша)

// bit reversing lookup table
typedef unsigned char BYTE;
extern const BYTE g_RevBits[256];

void ReverseBitsInPlace(BYTE * pb, int cb)
{
    int iter = cb/2;
    for (int ii = 0, jj = cb-1; ii < iter; ++ii, --jj)
    {
        BYTE b1 = g_RevBits[pb[ii]];
        pb[ii] = g_RevBits[pb[jj]];
        pb[jj] = b1;
    }

    if (cb & 1) // if the number of bytes was odd, swap the middle one in place
    {
       pb[cb/2] = g_RevBits[pb[cb/2]];
    }
}

// initialize the bit reversing lookup table using macros to make it less typing.
#define BITLINE(n) \
   0x0##n, 0x8##n, 0x4##n, 0xC##n, 0x2##n, 0xA##n, 0x6##n, 0xE##n,\
   0x1##n, 0x9##n, 0x5##n, 0xD##n, 0x3##n, 0xB##n, 0x7##n, 0xF##n,

const BYTE g_RevBits[256] = {
  BITLINE(0), BITLINE(8), BITLINE(4), BITLINE(C), 
  BITLINE(2), BITLINE(A), BITLINE(6), BITLINE(E), 
  BITLINE(1), BITLINE(9), BITLINE(5), BITLINE(D), 
  BITLINE(3), BITLINE(B), BITLINE(7), BITLINE(F), 
  };

Ответ 4

Сайт Bit Twiddling Hacks является хорошей отправной точкой для подобных проблем. Посмотрите здесь для быстрого разворота бит. Затем вам нужно применить его к каждому байту/слову блока памяти.

EDIT:

Вдохновленный Дитрихом Эппсом отвечая и глядя на набор инструкций ARM, есть код операции RBIT, который меняет биты, содержащиеся в регистр. Поэтому, если производительность имеет решающее значение, вы можете использовать некоторые ассемблерные коды.

Ответ 5

Прокрутите половину массива, преобразуйте и обменивайте байты.

for( int i = 0; i < arraySize / 2; i++ ) {
    char inverted1 = invert( array[i] );
    char inverted2 = invert( array[arraySize - i - 1] );
    array[i] = inverted2;
    array[arraySize - i - 1] = inverted1;
}

Для преобразования используйте предварительно вычисленную таблицу: массив из 2 ^CHAR_BIT (CHAR_BIT, скорее всего, будет 8) элементов, где в позиции "I" результат байта со значением "I" инверсии сохраняются. Это будет очень быстро - один проход - и используйте только 2 ^CHAR_BIT для таблицы.

Ответ 6

Похоже, что этот код занимает около 50 часов на бит для моего i7 XPS 8500. 7,6 секунды для миллиона переводов. Однопоточный. Он печатает некоторое искусство ASCI, основанное на шаблонах 1s и 0s. Я повернул pic налево на 180 градусов после изменения битового массива, используя графический редактор, и они выглядят идентично мне. Изображение с двойным обращением выходит так же, как и оригинал.

Что касается плюсов, это полное решение. Он меняет биты с обратной стороны битового массива на фронт, vs работает на ints/bytes и затем нуждается в замене ints/bytes в массиве.

Кроме того, это библиотека бит общего назначения, поэтому вы можете найти ее в будущем для решения других, более мирских проблем.

Это так же быстро, как принятый ответ? Я думаю, что это близко, но без использования кода для сравнения невозможно сказать. Не стесняйтесь вырезать и вставлять эту рабочую программу.

// Reverse BitsInBuff.cpp : Defines the entry point for the console application.
#include "stdafx.h"
#include "time.h"
#include "memory.h"
//
//  Manifest constants
#define  uchar unsigned char
#define  BUFF_BYTES 510 //400 supports a display of 80x40 bits
#define  DW 80  //  Display Width
// ----------------------------------------------------------------------------
uchar   mask_set[] = { 0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80 };
uchar   mask_clr[] = { 0xfe, 0xfd, 0xfb, 0xf7, 0xef, 0xdf, 0xbf, 0x7f };
//
// Function Prototypes
static void PrintIntBits(long x, int bits);
void    BitSet(uchar * BitArray, unsigned long BitNumber);
void    BitClr(uchar * BitArray, unsigned long BitNumber);
void    BitTog(uchar * BitArray, unsigned long BitNumber);
uchar   BitGet(uchar * BitArray, unsigned long BitNumber);
void    BitPut(uchar * BitArray, unsigned long BitNumber, uchar value);
//
uchar *ReverseBitsInArray(uchar *Buff, int BitKnt);
static void PrintIntBits(long x, int bits);
// -----------------------------------------------------------------------------
// Reverse the bit ordering in an array
uchar *ReverseBitsInArray(uchar *Buff, int BitKnt)  {
    unsigned long front=0, back = BitKnt-1;
    uchar temp;
    while( front<back ) {
        temp = BitGet(Buff, front);                 // copy front bit to temp before overwriting 
        BitPut(Buff, front, BitGet(Buff, back));    // copy back bit to front bit
        BitPut(Buff, back, temp);                   // copy saved value of front in temp to back of bit arra)
        front++;
        back--;
    }
    return Buff;
}
//  ---------------------------------------------------------------------------
//  ---------------------------------------------------------------------------
int _tmain(int argc, _TCHAR* argv[])    {
    int i, j, k, LoopKnt = 1000001;
    time_t start;
    uchar Buff[BUFF_BYTES];
    memset(Buff, 0, sizeof(Buff));
    //  make an ASCII art picture
    for(i=0, k=0; i<(sizeof(Buff)*8)/DW; i++)   {
        for(j=0; j<DW/2; j++)   {
            BitSet(Buff, (i*DW)+j+k);
        }
        k++;
    }
    //  print ASCII art picture
    for(i=0; i<sizeof(Buff); i++)   {
        if(!(i % 10)) printf("\n"); // print bits in blocks of 80
        PrintIntBits(Buff[i], 8);
    }
    i=LoopKnt;
    start = clock();
    while( i-- )    {
        ReverseBitsInArray((uchar *)Buff, BUFF_BYTES * 8);
    }
    //  print ASCII art pic flipped upside-down and rotated left
    printf("\nMilliseconds elapsed = %d", clock() - start);
    for(i=0; i<sizeof(Buff); i++)   {
        if(!(i % 10)) printf("\n"); // print bits in blocks of 80
        PrintIntBits(Buff[i], 8);
    }
    printf("\n\nBenchmark time for %d loops\n", LoopKnt);
    getchar();
    return 0;
}
// -----------------------------------------------------------------------------
//  Scaffolding...
static void PrintIntBits(long x, int bits)  {
    unsigned long long z=1;
    int i=0;
    z = z << (bits-1);
    for (; z > 0; z >>= 1)  {
        printf("%s", ((x & z) == z) ? "#" : ".");
    }
}
//  These routines do bit manipulations on a bit array of unsigned chars
//  ---------------------------------------------------------------------------
void BitSet(uchar *buff, unsigned long BitNumber)   {
    buff[BitNumber >> 3] |= mask_set[BitNumber & 7];
}
//  ---------------------------------------------------------------------------- 
void BitClr(uchar *buff, unsigned long BitNumber)   {
    buff[BitNumber >> 3] &= mask_clr[BitNumber & 7];
}
//  ---------------------------------------------------------------------------- 
void BitTog(uchar *buff, unsigned long BitNumber)   {
    buff[BitNumber >> 3] ^= mask_set[BitNumber & 7];
}
//  ---------------------------------------------------------------------------- 
uchar BitGet(uchar *buff, unsigned long BitNumber)  {
    return (uchar)  ((buff[BitNumber >> 3] >> (BitNumber & 7)) & 1);
}
//  ---------------------------------------------------------------------------- 
void BitPut(uchar *buff, unsigned long BitNumber, uchar value)  {
    if(value)   {   // if the bit at buff[BitNumber] is true.
        BitSet(buff, BitNumber);
    }   else    {
        BitClr(buff, BitNumber);
    }
}

Ниже приведен список кодов для оптимизации с использованием нового буфера вместо замены байтов на место. Учитывая, что требуется только 2030: 4080 битСеть() s из-за теста if(), и около половины GetBit() и PutBits() устраняются путем исключения TEMP, я подозреваю, что время доступа к памяти - это большая фиксированная стоимость для эти виды операций, обеспечивая жесткий предел оптимизации.

Используя подход поиска и CONDITIONALLY, заменяя байты, а не биты, уменьшает в 8 раз количество обращений к памяти, а тестирование для 0 байта амортизируется через 8 бит, а не 1.

Используя эти два подхода, тестирование, чтобы проверить, является ли весь 8-разрядный char равным 0, прежде чем делать НИЧЕГО, включая поиск в таблице, и запись, скорее всего, будет самым быстрым возможным подходом, но потребует дополнительные 512 байт для нового массива бит назначения и 256 байтов для таблицы поиска. Однако выигрыш в производительности может быть довольно драматичным.

// -----------------------------------------------------------------------------
// Reverse the bit ordering in new array
uchar *ReverseBitsInNewArray(uchar *Dst, const uchar *Src, const int BitKnt)    {
    int front=0, back = BitKnt-1;
    memset(Dst, 0, BitKnt/BitsInByte);

    while( front < back )   {
        if(BitGet(Src, back--)) {   // memset() has already set all bits in Dst to 0, 
            BitSet(Dst, front);     // so only reset if Src bit is 1
        }
        front++;
    }
    return Dst;

Ответ 7

Чтобы отменить один байт x, вы можете обрабатывать бит по одному за раз:

unsigned char a = 0;
for (i = 0; i < 8; ++i) {
   a += (unsigned char)(((x >> i) & 1) << (7 - i));
}

Вы можете создать кэш этих результатов в массиве, чтобы вы могли быстро изменить байт, просто сделав один поиск вместо цикла.

Затем вам просто нужно отменить массив байтов, и когда вы напишете данные, примените приведенное выше сопоставление. Реверсирование байтового массива является хорошо документированной проблемой, например. здесь.

Ответ 8

Единое ядро?

Сколько памяти?

Является ли дисплей буферизированным в памяти и нажатым на устройство или является единственной копией пикселей в памяти экранов?

Ответ 9

Данные выводятся из системной памяти на драйвер ЖКД через 8-битный IO порт.

Поскольку вы будете писать на ЖК-дисплей по одному байт за раз, я думаю, что лучшая идея - выполнить разворот бит сразу при отправке данных на драйвер ЖКД, а не как отдельный предварительно пройти. Что-то вдоль этих строк должно быть быстрее любого другого ответа:

void send_to_LCD(uint8_t* data, int len, bool rotate) {
  if (rotate)
    for (int i=len-1; i>=0; i--)
      write(reverse(data[i]));
  else
    for (int i=0; i<len; i++)
      write(data[i]);
}

Где write() - функция, которая отправляет байт на драйвер LCD и reverse() один из однобайтовых методов разворота бит, описанных в других ответах.

Этот подход позволяет избежать необходимости хранить две копии видеоданных в плунжере, а также избегать обратного конвертирования read-invert-write. Также обратите внимание, что это простейшая реализация: она может быть тривиально адаптирована для загрузки, скажем, 4 байта за раз из памяти, если бы это привело к повышению производительности. Компилятор умного векторизации может быть даже способен сделать это для вас.