Return to Answer

I try to give a very superficial answer for your question because I am quite sure that there are other treatments for this problem.

Mathematically, the function f(y) = y^(y >> 11) is invertible in the sense that the left-inversion, namely a function g so that y = g(f(y)) exists, because f is an injective function. However that does not mean we can easily find the inversion function because it may be uncomputable, namely in this case we cannot give an algorithm calculating g. Practically, there may exist some computable methods to "approximate" it (maybe abstract interpretation ?).

In a more strict case (but maybe more practical), if the value of y is stored in 4 bytes and the value of f(y) is stored in less than 4 bytes then the function is trivally not invertible because of the pigeon-hole principle. Moreover, the computation of an arbitrary sequence of instructions is not invertible in general because of the information-lost along the execution, to see that we can consider an example (in pseudo-assembly code)

f(y) = 
 mov eax, y
 xor eax, eax
 return eax

then f(y) is not invertible because the output is always 0 regardless of the input. However if we can store some "state values" (i.e. not only the output and the instruction sequence) along the execution of instructions then the inversion is possible, this idea has been proposed everywhere, e.g. in GDB Reverse Debugging or in this paper.

Edit: I got a mistake here because I thought ^ is an exponentation (so I doubt that the inversion is uncomputable in the general case) but in fact it is bitwise exclusive.

I try to give a very superficial answer for your question because I am quite sure that there are other treatments for this problem.

Mathematically, the function f(y) = y^(y >> 11) is invertible in the sense that the left-inversion, namely a function g so that y = g(f(y)) exists, because f is an injective function. However that does not mean we can easily find the inversion function because it may be uncomputable, namely in this case we cannot give an algorithm calculating g. Practically, there may exist some computable methods to "approximate" it (maybe abstract interpretation ?).

In a more strict case (but maybe more practical), if the value of y is stored in 4 bytes and the value of f(y) is stored in less than 4 bytes then the function is trivally not invertible because of the pigeon-hole principle. Moreover, the computation of an arbitrary sequence of instructions is not invertible in general because of the information-lost along the execution, to see that we can consider an example (in pseudo-assembly code)

f(y) = 
 mov eax, y
 xor eax, eax
 return eax

then f(y) is not invertible because the output is always 0 regardless of the input. However if we can store some "state values" (i.e. not only the output and the instruction sequence) along the execution of instructions then the inversion is possible, this idea has been proposed everywhere, e.g. in GDB Reverse Debugging or in this paper.

Edit: I got a mistake here because I thought ^ is an exponentation (so I doubt that the inversion is uncomputable in the general case) but in fact it is bitwise exclusive.

I try to give a very superficial answer for your question because I am quite sure that there are other treatments for this problem.

Mathematically, the function f(y) = y^(y >> 11) is invertible in the sense that the left-inversion, namely a function g so that y = g(f(y)) exists, because f is a monotonic function. However that does not mean we can easily find the inversion function because it may be uncomputable, namely in this case we cannot give an algorithm calculating g. Practically, there may exist some computable methods to "approximate" it (maybe abstract interpretation ?).

In a more strict case (but maybe more practical), if the value of y is stored in 4 bytes and the value of f(y) is stored in less than 4 bytes then the function is trivally not invertible because of the pigeon-hole principle. Moreover, the computation of an arbitrary sequence of instructions is not invertible in general because of the information-lost along the execution, to see that we can consider an example (in pseudo-assembly code)

f(y) = 
 mov eax, y
 xor eax, eax
 return eax

then f(y) is not invertible because the output is always 0 regardless of the input. However if we can store some "state values" (i.e. not only the output and the instruction sequence) along the execution of instructions then the inversion is possible, this idea has been proposed everywhere, e.g. in GDB Reverse Debugging or in this paper.

Edit: I got a mistake here because I thought ^ is an exponentation (so I doubt that the inversion is uncomputable in the general case) but in fact it is bitwise exclusive.

I try to give a very superficial answer for your question because I am quite sure that there are other treatments for this problem.

Mathematically, the function f(y) = y^(y >> 11) is invertible in the sense that the left-inversion, namely a function g so that y = g(f(y)) exists, because f is an injective function. However that does not mean we can easily find the inversion function because it may be uncomputable, namely in this case we cannot give an algorithm calculating g. Practically, there may exist some computable methods to "approximate" it (maybe abstract interpretation ?).

In a more strict case (but maybe more practical), if the value of y is stored in 4 bytes and the value of f(y) is stored in less than 4 bytes then the function is trivally not invertible because of the pigeon-hole principle. Moreover, the computation of an arbitrary sequence of instructions is not invertible in general because of the information-lost along the execution, to see that we can consider an example (in pseudo-assembly code)

f(y) = 
 mov eax, y
 xor eax, eax
 return eax

then f(y) is not invertible because the output is always 0 regardless of the input. However if we can store some "state values" (i.e. not only the output and the instruction sequence) along the execution of instructions then the inversion is possible, this idea has been proposed everywhere, e.g. in GDB Reverse Debugging or in this paper.

Edit: I got a mistake here because I thought ^ is an exponentation (so I doubt that the inversion is uncomputable in the general case) but in fact it is bitwise exclusive.

I try to give a very superficial answer for your question because I am quite sure that there are other treatments for this problem.

Mathematically, the function f(y) = y^(y >> 11) is invertible in the sense that the left-inversion, namely a function g so that y = g(f(y)) exists, because f is a monotonic function. However that does not mean we can easily find the inversion function because it may be uncomputable, namely in this case we cannot give an algorithm calculating g. Practically, there may exist some computable methods to "approximate" it (maybe abstract interpretation ?).

In a more strict case (but maybe more practical), if the value of y is stored in 4 bytes and the value of f(y) is stored in less than 4 bytes then the function is trivally not invertible because of the pigeon-hole principle. Moreover, the computation of an arbitrary sequence of instructions is not invertible in general because of the information-lost along the execution, to see that we can consider an example (in pseudo-assembly code)

f(y) = 
 mov eax, y
 xor eax, eax
 return eax

then f(y) is not invertible because the output is always 0 regardless of the input. However if we can store some "state values" (i.e. not only the output and the instruction sequence) along the execution of instructions then the inversion is possible, this idea has been proposed everywhere, e.g. in GDB Reverse Debugging or in this paper

I try to give a very superficial answer for your question because I am quite sure that there are other treatments for this problem.

Mathematically, the function f(y) = y^(y >> 11) is invertible in the sense that the left-inversion, namely a function g so that y = g(f(y)) exists, because f is a monotonic function. However that does not mean we can easily find the inversion function because it may be uncomputable, namely in this case we cannot give an algorithm calculating g. Practically, there may exist some computable methods to "approximate" it (maybe abstract interpretation ?).

In a more strict case (but maybe more practical), if the value of y is stored in 4 bytes and the value of f(y) is stored in less than 4 bytes then the function is trivally not invertible because of the pigeon-hole principle. Moreover, the computation of an arbitrary sequence of instructions is not invertible in general because of the information-lost along the execution, to see that we can consider an example (in pseudo-assembly code)

f(y) = 
 mov eax, y
 xor eax, eax
 return eax

then f(y) is not invertible because the output is always 0 regardless of the input. However if we can store some "state values" (i.e. not only the output and the instruction sequence) along the execution of instructions then the inversion is possible, this idea has been proposed everywhere, e.g. in GDB Reverse Debugging or in this paper.

Edit: I got a mistake here because I thought ^ is an exponentation (so I doubt that the inversion is uncomputable in the general case) but in fact it is bitwise exclusive.