Как сделать оптимальную перестановку элементов массива с XORом индексов?

Question

[VlLight]

Здравствуйте.
Есть массив данных, вычитываемый из файла. При записи в файл в этом массиве переставляются элементы путём XOR'а индекса массива и случайного 8-битного значения. Соответственно, чтобы восстановить исходный массив, после вычитывания нужно сделать эту перестановку ещё раз. Сейчас вычитываю по 512 байт, поэтому делаю просто что-то вроде такого (читаю данные во временный буфер, потом переношу в основной с требуемым индексом):

uint8_t main_buffer[512];
uint8_t temp_buffer[512];
uint8_t cryptor;

cryptor = readCryptor();

while(readNext512Bytes(temp_buffer))
{
    for (uint16_t i = 0; i < 512; i++)
    {
        main_buffer[i] = temp_buffer[i ^ cryptor]
    }
}

Размер считываемого блока нужно увеличить (как минимум, до 6 Кб), держать такой временный буфер мне жабодушно, поэтому хочу читать сразу в основной, потом частями из него переставлять элементы во временный буфер, потом возвращать обратно с правильными индексами. Однако, мне не нравится, что на каждый элемент уходит 2 копирования (из основного буфера во временный и обратно). Теоретически, вероятно, это можно реализовать с временной переменной - так на 2 элемента получится 3 копирования и итераций будет в 2 раза меньше... но у меня не хватает ума придумать цикл. Может быть посоветуете что-нибудь?

Answer 1

[Дмитрий Беляев]

Так как все индексы мы xor'им с одним и тем же числом cryptor то повторы между i и i ^ cryptor будут заключены в равных отрезках, притом размер этого отрезка всегда будет ближайшей от cryptor степенью 2 сверху, а сами повторы будут распределены в разных половинах данных отрезков, длина половинок соответственно ближайшая от cryptor степенью 2 снизу.
Ну и нужно не забывать, что есть крайний случай, когда cryptor равен 0, при котором перестановок вообще не будет

uint8_t main_buffer[512];
uint8_t cryptor;

cryptor = readCryptor();

if(cryptor != 0)
{
    // вычислим ближайшую к cryptor степень 2 снизу
    uint8_t pow2 = 0x80;
    while((pow2 & cryptor) == 0) pow2 >>= 1;

    while(readNext512Bytes(main_buffer))
    {
        // один большой цикл заменим на 2 маленьких
        // k будет считать отрезки
        // i будет считать позицию внутри отрезка
        for(uint16_t k = 0; k < 512; k += pow2 << 1) for(uint8_t i = 0; i < pow2; i++)
        {
            uint8_t tmp;
            tmp = main_buffer[i + k];
            main_buffer[i + k] = main_buffer[(i + k) ^ cryptor];
            main_buffer[(i + k) ^ cryptor] = tmp;
        }
    }
}

Comments

[VlLight]

Это гениально! Спасибо.