Re: [math-fun] History of swap/exch computer instructions ?
[another mailing list flub --Rich] Date: Wed, 14 Mar 2018 15:11:56 -0400 Subject: Re: [math-fun] History of swap/exch computer instructions ? From: wba <wbackerman@gmail.com> To: math-fun@mailman.xmission.com, William Ackerman <wba@alum.mit.edu> This reminds me of another famous swapping hack, often used by bit-bumming assembly language hackers (such as myself). You want to swap two things--memory, register, whatever, and you have XOR instructions. You need to have XOR instructions that go both ways: if swapping a register with memory, you need instructions that can XOR a register out to memory. The 360, and Intel, being monstrously CISC machines, have them. I used this hack many times in my youth. A -->XOR--> B // That is, set B = A^B B -->XOR--> A A -->XOR--> B The 360 had "block XOR" instructions ("XORM"? Can't be bothered to look it up.) You could XOR one long block of memory onto another. So you could use this hack to swap two blocks of memory, without any temporaries. -------- On 03/14/2018 12:05 PM, Adam P. Goucher wrote: Maybe the reason for lacking ROTATEF in modern instruction sets is that the n-ary rotation can be implemented using (n-1) SWAP instructions: rotatef i_1 i_2 i_3 ... i_n <==> swap i_1 i_2 swap i_2 i_3 ... swap i_{n-1} i_n Best wishes, Adam P. Goucher
On 14 Mar 2018 at 13:51, rcs@xmission.com wrote:
This reminds me of another famous swapping hack, often used by bit-bumming assembly language hackers (such as myself)..
A -->XOR--> B // That is, set B = A^B
B -->XOR--> A
A -->XOR--> B
There's a related hack those of us used on machines with more limited instruction sets: load a, xor b, and mask, xor b. which loads the bits in 'b' where there are zeroes in the mask. We iused that a lot on the PDP-1d timesharing system. But most notably, with some addition extended hacking you can use that trick to swap fields between two words. I used that in the IMP code to swap the source IMP address and destination IMP address in setting up the RFNM reply. It was a cute bit of code, because the IMP address was actually 9 bits -- six bits of IMP #, two bits of host and one bit of "fake host" The tricky part is that the fake host bits wasn't contiguous and so it was a cute bit of code to move the fields around all "on the fly", not using an intermediate storage location. I thought it was a beautiful bit of how one could abuse the XOR instruction... nobody else was willing to touch that bit of code... :o) /Bernie\ Bernie Cosell bernie@fantasyfarm.com -- Too many people; too few sheep --
If you don't have bitwise XOR, you can do the same thing with addition and subtraction, provided overflow is ignored and you always get the correct low-order bits of the result: A <- A + B B <- A - B A <- A - B // Note that B is now the original A Tom Bernie Cosell writes:
On 14 Mar 2018 at 13:51, rcs@xmission.com wrote:
This reminds me of another famous swapping hack, often used by bit-bumming assembly language hackers (such as myself)..
A -->XOR--> B // That is, set B = A^B
B -->XOR--> A
A -->XOR--> B
There's a related hack those of us used on machines with more limited instruction sets: load a, xor b, and mask, xor b. which loads the bits in 'b' where there are zeroes in the mask. We iused that a lot on the PDP-1d timesharing system.
But most notably, with some addition extended hacking you can use that trick to swap fields between two words. I used that in the IMP code to swap the source IMP address and destination IMP address in setting up the RFNM reply. It was a cute bit of code, because the IMP address was actually 9 bits -- six bits of IMP #, two bits of host and one bit of "fake host" The tricky part is that the fake host bits wasn't contiguous and so it was a cute bit of code to move the fields around all "on the fly", not using an intermediate storage location. I thought it was a beautiful bit of how one could abuse the XOR instruction... nobody else was willing to touch that bit of code... :o)
/Bernie\ Bernie Cosell bernie@fantasyfarm.com -- Too many people; too few sheep --
More generally, if you have functions f, g, and h such that g(f(a, b), b) = a and h(f(a, b), a) = b, then you can do: a <- f(a, b) b <- g(a, b) a <- h(a, b) // Note that b is now the original a In the case of XOR, f, g, and h are all the same. Tom Tom Karzes writes:
If you don't have bitwise XOR, you can do the same thing with addition and subtraction, provided overflow is ignored and you always get the correct low-order bits of the result:
A <- A + B B <- A - B A <- A - B // Note that B is now the original A
Tom
Bernie Cosell writes:
On 14 Mar 2018 at 13:51, rcs@xmission.com wrote:
This reminds me of another famous swapping hack, often used by bit-bumming assembly language hackers (such as myself)..
A -->XOR--> B // That is, set B = A^B
B -->XOR--> A
A -->XOR--> B
There's a related hack those of us used on machines with more limited instruction sets: load a, xor b, and mask, xor b. which loads the bits in 'b' where there are zeroes in the mask. We iused that a lot on the PDP-1d timesharing system.
But most notably, with some addition extended hacking you can use that trick to swap fields between two words. I used that in the IMP code to swap the source IMP address and destination IMP address in setting up the RFNM reply. It was a cute bit of code, because the IMP address was actually 9 bits -- six bits of IMP #, two bits of host and one bit of "fake host" The tricky part is that the fake host bits wasn't contiguous and so it was a cute bit of code to move the fields around all "on the fly", not using an intermediate storage location. I thought it was a beautiful bit of how one could abuse the XOR instruction... nobody else was willing to touch that bit of code... :o)
/Bernie\ Bernie Cosell bernie@fantasyfarm.com -- Too many people; too few sheep --
On 14 Mar 2018 at 17:59, Tom Karzes wrote:
If you don't have bitwise XOR, you can do the same thing with addition and subtraction, provided overflow is ignored and you always get the correct low-order bits of the result:
A <- A + B B <- A - B A <- A - B // Note that B is now the original A
That's true, but the xor-and-xor hack allows you to mess with arbitrary (and non adjacent) bits in the middle of the words. /B\ Bernie Cosell bernie@fantasyfarm.com -- Too many people; too few sheep --
participants (3)
-
Bernie Cosell -
rcs＠xmission.com -
Tom Karzes