Exactly Adam.

This technique was used by Data General to implement sequential disk files
in their RDOS operator system. They used one word of each disk block to
contain the xor'd disk address of the previous and next blocks in the chain.

Bob Ammerman
RAm Systems


----- Original Message -----
From: "M. Adam Davis" <adampic@UBASICS.COM>
To: <PICLIST@MITVMA.MIT.EDU>
Sent: Monday, March 18, 2002 5:16 AM
Subject: Re: [PIC]: xor tricks History


> Very interesting.
>
> It seems that you'd have to have a pointer to the current address, and
> the address of either the next item in the list or the previous item in
> the list.  The current item will contain the xor of the previous and
> next pointers, and since you know one of them you can get the other.
>
> What you are doing, in essence, is trading space (eliminating another
> pointer sized word in each data structure) for a smaller space (keeping
> another pointer size word in code) and code (since you now have to
> execute another instruction to get the other pointer.
>
> This has other interesting uses as well.  If you don't want to keep
> track of where you're at in the linked list, you can loop it, and zoom
> around in whatever direction you're pointed in.
>
> Inserting another item between two established items requires the same
> amount if work as well.  Very interesting.
>
> It would drive someone else crazy, trying to read the code and figure
> out what the heck the previous programmer was smoking...  ;-)
>
> -Adam
>
> Bob Ammerman wrote:
>
> >One of the neatest XOR tricks I ever saw was a way to build a
doubly-linked
> >list using only one pointer-sized word in each data structure.
> >
> >Anyone care to guess how it worked?
> >
> >
> >Bob Ammerman
> >RAm Systems
> >
> >--
> >http://www.piclist.com hint: PICList Posts must start with ONE topic:
> >[PIC]:,[SX]:,[AVR]: ->uP ONLY! [EE]:,[OT]: ->Other [BUY]:,[AD]: ->Ads
> >
> >
> >
> >
> >
>
> --
> http://www.piclist.com hint: PICList Posts must start with ONE topic:
> [PIC]:,[SX]:,[AVR]: ->uP ONLY! [EE]:,[OT]: ->Other [BUY]:,[AD]: ->Ads
>
>
>

--
http://www.piclist.com hint: PICList Posts must start with ONE topic:
[PIC]:,[SX]:,[AVR]: ->uP ONLY! [EE]:,[OT]: ->Other [BUY]:,[AD]: ->Ads