Ah, I never figured on doing something so, well, silly.
The way the addresses are stored is this:
1) nextXORPrev = next ^ prev;
In order to get one pointer out, you need to know both the other pointer and the XORed field. That is:
2) prev = nextXORPrev ^ next; // to get 'prev' I had to know everything on the right hand side
3) next = nextXORPrev ^ prev; // likewise, to get 'next' I had to know both 'prev' and 'nextXORPrev'
If you want to
change one of the pointers, you must first obtain the pointer you wish to keep (using either equation 2 or 3) and then recombine the new pointer and the one you wish to keep using equation 1.
You will also have to do some casting between pointer and integer types. Here is an example to help you out:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64
|
#include <stdio.h>
#include <string.h>
/* XORPtr() ------------------------------------------------------------------
*
* This little function makes it convenient to XORs two char pointers.
*/
char* XORPtr( char* a, char* b )
{
return (char*)(
(unsigned long)a ^ (unsigned long)b
);
}
/* printAB() -----------------------------------------------------------------
*
* This function prints the characters indexed by the XORed pointer.
*/
void printAB( char* ab, char* a )
{
char* b = XORPtr( ab, a );
printf( " *a = '%c'\n", *XORPtr( ab, b ) );
printf( " *b = '%c'\n\n", *XORPtr( ab, a ) );
}
/* main() --------------------------------------------------------------------
*/
int main()
{
/* Here's the stuff we will point to */
char abc[] = "ABC";
/* Here are our pointers */
char* a = abc;
char* b = abc + 1;
char* c = abc + 2;
/* And here is our combined pointer */
char *ab = XORPtr( a, b );
printf( "ab = a ^ b;\n\n" );
printf( "printAB( ab, a );\n" );
printAB( ab, a );
/* Notice that it does not matter which pointer you call 'a' or 'b' */
printf( "printAB( ab, b );\n" );
printAB( ab, b );
/* Now make ab = a ^ c. Pay close attention here,
* since we don't actually use 'a' in the calculation. */
ab = XORPtr( ab, b ); /* first: ab = a ^ NULL */
ab = XORPtr( ab, c ); /* second: ab = a ^ c */
printf( "\nab == a ^ c;\n\n" );
printf( "printAB( ab, a );\n" );
printAB( ab, a );
printf( "printAB( ab, c );\n" );
printAB( ab, c );
return 0;
}
| |
Make sure to compile and execute this program to see the outputs.
Hope this helps.
[edit] Oh yeah, two things:
1) You can have
nextXORPrev stored as a pointer type without any problems, just as in my example above
ab is stored as a char*.
2)
Do not mix pointer types into the same field. When XORing pointers, make sure that both pointers are identical in type. While you won't have any trouble on a PC, there exists hardware where pointers significantly differ in structure for different types. Don't ask me why. (I don't know -- crazy hardware designers.) Also, you cannot rely on that actually being a NULL on line 53, for more of the same reason -- there exists architectures where a NULL pointer is
not zero. Go figure. (Hence, don't try to extract a NULL, since it might not be.)
[edit 2] OK, one more thing.
Above I said that it does not matter which is
a and which is
b. I meant that in terms of using XOR. In your code, obviously, one must be
prev and the other must be
next. The point is that if you know one of the two, you can get the other out.
Phew. :-)