Решение побитового уравнения XOR и ADD

Question

Естественно, XOR можно использовать дважды, чтобы вернуть исходное значение. Что если исходное значение является частью маски?

Кодирование:

e[i] = c[i] ^ (c[i] + c[i-1])

Предполагая: начальное значение c[-1] = 0, ^ означает побитовое XOR

В императивной форме C:

void encode(byte *p, int len)
{
    byte prev = 0;
    for (auto i = 0; i < len; i++)
    {
        auto byt = p[i];
        p[i] = byt ^ (prev + byt);
        prev = byt;
    }
}

Как мне создать шаг декодирования, который меняет это с e => c?

Я упростил / уточнил (читай: изменил) вопрос с учетом того, что я узнал из твоих ответов! Используя шаги, аналогичные DanL, начиная с исходного уравнения:

e[i] = c[i] ^ (c[i] + c[i-1])

e[i] ^ c[i] = c[i] ^ (c[i] + c[i-1]) ^ c[i]
e[i] ^ c[i] = c[i] + c[i-1]
c[i] = e[i] ^ c[i] - c[i-1]
c[i] ^ c[i] = (e[i] ^ c[i] - c[i-1]) ^ c[i]
0 = e[i] ^ c[i] ^ c[i] - c[i-1] ^ c[i]
0 = e[i] - c[i-1] ^ c[i]
c[i-1] ^ c[i] = e[i]
c[i-1] ^ c[i] ^ c[i-1] = e[i] ^ c[i-1]
c[i] = e[i] ^ c[i-1]

???

Теперь посмотрим на исходную кодировку - первый байт всегда будет нулевым (= c[i] ^ (c[i] + 0)). Так что да, должна быть потеря одного байта за набор.

Answer 1

На каждой итерации цикла вы эффективно рассчитываете

c_i = e ^ ( p + c_(i-1) )

Если вы хотите повернуть цикл вспять, то с учетом c_i необходимо рассчитать c_(i-1)

Однако, как вы сказали, xoring дважды возвращает вас к исходному значению, а xor является коммутативной операцией, поэтому, если вы xor приведенного выше уравнения с помощью e, мы получим

c_i ^ e = e ^ ( p + c_(i-1) ) ^ e

что упрощает до

c_i ^ e = p + c_(i-1)

затем уберите р с обеих сторон, чтобы дать вам

(c_i ^ e) - p = c_(i-1)

Поэтому в вашем цикле "обращения"

ты хочешь код

c = (c ^ e) - p

Изменить: После просмотра пересмотренного вопроса с кодом в контексте, я не думаю, что это возможно, так как я считаю, что функция mix эффективно отображает массив байтов len в массив байтов len-1.

Я верю в это из-за следующего аргумента:

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

mixed[0] = unmixed[0] ^ (0 + unmixed[0])  //Remember prev = 0 initially

поэтому смешанный [0] = несмешанный [0] ^ несмешанный [0] = 0

поэтому первый байт смешанного массива всегда будет 0.

Функция mix не увеличивает и не уменьшает размер массива, поэтому мы получаем массив байтов len с первым элементом 0.

Поэтому мы эффективно сопоставили пространство массивов байтов len с массивами байтов len-1.

Если бы это было полностью обратимо, мы могли бы сжать массив байтов в массив из n-1 байтов, а затем сжать этот массив из n-1 байтов в массив из 2 байтов и так далее.

Если мы используем однобайтовый массив в качестве примера, то увидим, что mix просто создает массив с одним элементом 0, как вы узнаете, какой из 256 возможных несмешанных массивов был до этого?