How to reverse XOR-shift operations

Question

I have the following xor-shift encoder

char a[] = "text";
int b = strlen(a);
for (int c = 0; c < b; c++) {
    if (c > 0) a[c] ^= a[c-1];
    a[c] ^= a[c] >> 3;
    a[c] ^= a[c] >> 2;
    a[c] ^= a[c] >> 1;
    printf("%02x", (unsigned int)(a[c]));
}

I'd like to revert the hex output to the original string.

Is it even possible, considering that the shift would in some cases eliminate bits on the right side that can't be retrieved anymore? And if it is possible, how could the operations be reverted?

Answer 1

Yes, it's not that hard. Just map the xor-shit results back to their original values. Consider this function:

char f(char c) {
    c ^= c >> 3;
    c ^= c >> 2;
    c ^= c >> 1;
    return c;
}

You should be able to satisfy yourself that for every possible input value (from 0 to 127), there is a corresponding unique output. (Of course, if you change char to unsigned char, then the function will work on any 8-bit input.)

With this function, you can easily create an array to perform the reverse of this function:

char g(char c) {
    static char *map = NULL;
    if (!map) {
        map = malloc(128);
        for (int i=0; i<128; i++) map[f(i)] = i;
    }
    return map[c];
}

Then just write a function to read each character of a string in turn, apply this reverse function, and then XOR the result with the previous value:

char *decode(char *s, int len) {
    char *start = s, last = 0;
    while (len--) {
        char tmp = *s;
        *s = last ^ g(*s);
        last = tmp;
        s++;
    }
    return start;
}