CODEWITHSUNDEEP
bitwise-operatorslogical-operatorsequation-solvingbitwise-xor
Fil
Fil

Reputation: 1844

Solving bitwise XOR and ADD equation

Naturally XOR can be used twice to get back the original value. What if the original value is part of the mask?

Encoding:

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

Assuming: starting value c[-1] = 0, ^ means bitwise XOR

In imperative C form:

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

How do I create a decode step that reverses this from e => c?

I've simplified/clarified (read: changed) the question given what I've learned from your answers! Using similar steps to DanL, starting with the original equation:

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]

???

Now, looking at the original encode - the first byte will always be zero (= c[i] ^ (c[i] + 0)). So yes, there must be a loss of one byte over the set.

Upvotes: 0

Views: 1535

Answers (1)

DanL
DanL

Reputation: 2024

In each iteration of the loop you are effectively calculating

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

If you wish to reverse the loop then given a c_i you need to calculate c_(i-1)

However as you said xoring twice gets you back to the original value and xor is a commutative operation so if you xor the above equation by e we then get

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

which simplifies to

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

then take away p from both sides to give you

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

Therefore in your "reversal" loop

you want the code

c = (c ^ e) - p

Edit: After seeing the revised question with code in context I don't believe this is possible as I believe the mix function is effectively mapping a len byte array onto a len-1 byte array.

I believe this because of the following argument:

Let the unmixed array be called unmixed and the mixed array after applying the mix function be called mixed

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

therefore mixed[0] = unmixed[0] ^ unmixed[0] = 0

so the first byte of the mixed array will always be 0.

The mix function doesn't increase or decrease the size of the array so we end up with a len byte array with the first element being 0.

We have therefore effectively mapped the space of len byte arrays onto len-1 byte arrays.

If this was perfectly reversible, we would be able to compress a n byte array to a n-1 byte array and then compress that n-1 byte array to a n - 2 byte array and so on.

If we use a one byte array as an example then we see mix just produces an array with a single element of 0, how do you know which of the 256 possible unmixed arrays it was before hand?

Upvotes: 1

Related Questions