оптимизированный сдвиг байтового массива

Question

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

char* baLeftShift(const char* array, size_t size, signed int displacement,char* result)
{
    memcpy(result,array,size);
    short shiftBuffer = 0;
    char carryFlag = 0;
    char* byte;
    if(displacement > 0)
    {
        for(;displacement--;)
        {
            for(byte=&(result[size - 1]);((unsigned int)(byte))>=((unsigned int)(result));byte--)
            {
                shiftBuffer = *byte;
                shiftBuffer <<= 1;
                *byte = ((carryFlag) | ((char)(shiftBuffer)));
                carryFlag = ((char*)(&shiftBuffer))[1];
            }
        }
    }
    else
    {
        unsigned int offset = ((unsigned int)(result)) + size;
        displacement = -displacement;
        for(;displacement--;)
        {
            for(byte=(char*)result;((unsigned int)(byte)) < offset;byte++)
            {
                shiftBuffer = *byte;
                shiftBuffer <<= 7;
                *byte = ((carryFlag) | ((char*)(&shiftBuffer))[1]);
                carryFlag = ((char)(shiftBuffer));
            }
        }
    }
    return result;
}

Answer 1

Если я могу просто добавить к тому, что говорит @dwelch, вы можете попробовать это.

1. Просто переместите байты в их последние места. Затем у вас остается счетчик сдвигов, например 3, например, если каждый байт все еще должен быть сдвинут влево на 3 бита в следующий старший байт. (Предполагается, что на ваш взгляд байты расположены в порядке возрастания справа налево.)

2. Затем поверните каждый байт влево на 3. Таблица поиска может быть быстрее, чем индивидуальное выполнение фактического вращения. Затем в каждом байте 3 бита, которые должны быть сдвинуты, теперь находятся в правом конце байта.

3. Теперь создайте маску M, которая равна (1<<3)-1, то есть просто включены 3 младших разряда.

4. Теперь, по порядку, от старшего байта к младшему байту, сделайте следующее:

   c[i] ^= M & (c[i] ^ c[i-1])

Это скопирует биты в c[i] из c[i-1] под маской M.

Для последнего байта просто используйте 0 вместо c[i-1].

Для правильных сдвигов та же идея.

Answer 2

Это выглядит неэффективно, и, возможно, это то, на что ссылался Натан.

при условии, что в этом коде используется 8-битный символ, есть две вещи, которые нужно сделать, чтобы сначала переместить целые байты, например, если вашвходной массив равен 0x00,0x00,0x12,0x34, и вы сдвигаете влево на 8 битов, затем вы получаете 0x00 0x12 0x34 0x00, нет причин делать это в цикле 8 раз по одному биту за раз.поэтому начните со смещения целых символов в массиве на (смещение >> 3) местоположения и заполните пробелы, созданные нулями, своего рода для (ra = (смещение >> 3); ra> 3)] = array [ra];для (ра - = (смещения >> 3); ра> (7- (смещение & 7))).хороший компилятор будет предварительно вычислять (смещение >> 3), смещение & 7, 7- (смещение & 7), а у хорошего процессора будет достаточно регистров, чтобы сохранить все эти значения.Вы могли бы помочь компилятору, создав отдельные переменные для каждого из этих элементов, но в зависимости от компилятора и от того, как вы его используете, это может ухудшить ситуацию.

Суть в том, что код времени.выполните тысячу сдвигов в 1 бит, затем тысячу сдвигов в 2 бита и т. д., и т. д., а затем попробуйте другой алгоритм и рассчитайте его таким же образом и посмотрите, будут ли оптимизации иметь значение, лучше или хуже.Если вы заранее знаете, что этот код будет использоваться только для однократных или менее 8-битных сдвигов, соответственно скорректируйте тест синхронизации.

использование вами флага переноса подразумевает, что вы знаете, что многие процессоры имеют инструкции специальнодля объединения бесконечно длинных сдвигов с использованием стандартной длины регистра (для одного бита за раз), в основном, используйте переход через перенос.Который язык C не поддерживает напрямую.для объединения однобитовых сдвигов вы можете рассмотреть ассемблер и, вероятно, превзойти C-код.по крайней мере, сдвиги одного бита быстрее, чем может сделать C-код.Гибрид перемещения байтов тогда, если число битов для сдвига (смещение & 7) может быть меньше 4, используйте ассемблер, иначе используйте цикл C.снова тесты синхронизации покажут вам, где находятся оптимизации.

Answer 3

Моим первым предложением было бы устранить петли for вокруг смещения.Вы должны быть в состоянии сделать необходимые смены без петель for(;displacement--;).Для смещений, превышающих 7, все становится немного сложнее, потому что ваши границы внутреннего цикла изменятся, а смещение источника больше не равно 1. т.е. смещение вашего входного буфера становится magnitude / 8, а ваше смещение становится magnitude % 8.