How to make an optimal permutation of array elements with XOR indices?

Question

C++ / C#

Hello.
There is an array of data read from a file. When writing to a file, the elements in this array are rearranged by XORing the array index and a random 8-bit value. Accordingly, in order to restore the original array, after subtracting, you need to do this permutation again. Now I am reading 512 bytes, so I just do something like this (I read the data into a temporary buffer, then transfer it to the main one with the required index):

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]
    }
}

The size of the read block needs to be increased (at least up to 6 KB), I feel greedy to keep such a temporary buffer, so I want to read directly into the main one, then rearrange the elements from it in parts to the temporary buffer, then return it back with the correct indices. However, I don't like that it takes 2 copies per element (from the main buffer to the temporary buffer and vice versa). Theoretically, this can probably be implemented with a temporary variable - so for 2 elements you get 3 copies and iterations will be 2 times less ... but I don’t have the mind to come up with a cycle. Maybe you will advise something?

Answer 1

Since we xor all indices with the same cryptor number, then the repetitions between i and i ^ cryptor will be enclosed in equal segments, moreover, the size of this segment will always be the nearest power of 2 from cryptor from above, and the repetitions themselves will be distributed in different halves of these segments, the length of the halves, respectively, is nearest to the cryptor by a degree of 2 from below.
Well, we must not forget that there is an extreme case when cryptor is equal to 0, in which there will be no permutations at all

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;
        }
    }
}