Instruction Reduction
|
From: wthompso on 10 Feb 2005 14:22 Hello, Tanenbaum says in his Structured Computer Organization book that all instructions can be reduced to: 1. An addition operation 2. Check to see if a number is zero 3. Copy data from one memory location to another I was wondering if anyone can point me to a chart for instance, that shows such a reduction (I'm guessing mostly with regard to number one above). To further clarify, I guess, I can derive for instance, an xor operation with only using additions, etc. Of course, a program with such a primitive instruction set would be large (similar to coding in binary I guess). I'm actually doing research in program obfuscation/protection. Anyway, I'm a high-level programmer who occasionally ventures to the low-level in such cases. Thanks, --Willard
From: Scott A Crosby on 12 Feb 2005 02:50 On 10 Feb 2005 11:22:16 -0800, wthompso(a)cs.fsu.edu writes: > Hello, > > Tanenbaum says in his Structured Computer Organization book that all > instructions can be reduced to: > > 1. An addition operation > 2. Check to see if a number is zero > 3. Copy data from one memory location to another > > I was wondering if anyone can point me to a chart for instance, that > shows such a reduction (I'm guessing mostly with regard to number one > above). To further clarify, I guess, I can derive for instance, an xor > operation with only using additions, etc. Of course, a program with > such a primitive instruction set would be large (similar to coding in > binary I guess). This may be of interest: @article{121976, author = {P. A. Laplante}, title = {A novel single instruction computer architecture}, journal = {SIGARCH Comput. Archit. News}, volume = {18}, number = {4}, year = {1990}, issn = {0163-5964}, pages = {22--26}, doi = {http://doi.acm.org/10.1145/121973.121976}, publisher = {ACM Press}, } > I'm actually doing research in program obfuscation/protection. Anyway, > I'm a high-level programmer who occasionally ventures to the low-level > in such cases. This may also be of interest: @article{barak01impossibility, author = "Boaz Barak and Oded Goldreich and Rusell Impagliazzo and Steven Rudich and Amit Sahai and Salil Vadhan and Ke Yang", title = "On the (Im)possibility of Obfuscating Programs", year = "2001", } Scott
From: Anthony J Bybell on 13 Feb 2005 00:13 wthompso(a)cs.fsu.edu wrote in message news:<1108175839.973517.35720(a)z14g2000cwz.googlegroups.com>... > Ultimately, we assume that for mobile code the remote host can do > anything he wants with the code. The aim is to be able to reduce > *effective* tampering to *blind* tampering thus giving mobile code such > as mobile agents, greater survivability within an untrusted network. Read the pdf on the top of the page listed in the URL. There are some interesting observations there which save me a lot of typing as he's thinking along the same track I am: http://www.xenatera.com/bunnie/proj/anatak/xboxmod.html ....code signing (authentication) from a secure boot ROM all the way out is probably the only "really" secure method out there as the security is based on mathematical probability rather than obscurity. Otherwise, given enough time, if your device is interesting enough its hack will make the front page of Slashdot: there are a lot of clever people with a lot of free time on their hands out there. This goes without saying, but make sure that JTAG/I2C/etc is disabled on your remote host. =) -t
From: George Neuner on 13 Feb 2005 19:30 On 10 Feb 2005 11:22:16 -0800, wthompso(a)cs.fsu.edu wrote: >Hello, > >Tanenbaum says in his Structured Computer Organization book that all >instructions can be reduced to: > >1. An addition operation >2. Check to see if a number is zero >3. Copy data from one memory location to another > >I was wondering if anyone can point me to a chart for instance, that >shows such a reduction (I'm guessing mostly with regard to number one >above). To further clarify, I guess, I can derive for instance, an xor >operation with only using additions, etc. Of course, a program with >such a primitive instruction set would be large (similar to coding in >binary I guess). > Tanenbaum is probably correct ... I haven't given it enough thought. If you're interested in reading about a real computer with a sand simple instruction set, Lincoln Lab's TX-0 (tee-ex-zero) "tixo" computer had only 4 instructions: store, add, conditional branch, and a "trap" instruction that accessed system registers, performed I/O and a few other useful things based on the operand. There's some stuff about it online at: http://www.bitsavers.org/pdf/mit/tx-0/ and http://www.tixo.org/ I don't know of any ready references for the kind of code reduction and/or simplification you're interested in. Your best bet might be to find and look at some actual tixo code to see how real problems were attacked with the limited instruction set. There's not much "interesting" code at the above links, however, there are some MIT lab memos at bitsavers.org which talk about applications and code libraries being made available for the tixo. If you are able to locate the actual code for some of the more interesting ones (assembler, debugger, FP interpreter) I'm sure you could learn a lot by studying it. George -- for email reply remove "/" from address
From: del cecchi on 13 Feb 2005 19:56
"George Neuner" <gneuner2/@comcast.net> wrote in message news:a8ov01pue9fn68k7o4bt8a01hoef25ffmg(a)4ax.com... > On 10 Feb 2005 11:22:16 -0800, wthompso(a)cs.fsu.edu wrote: > > >Hello, > > > >Tanenbaum says in his Structured Computer Organization book that all > >instructions can be reduced to: > > > >1. An addition operation > >2. Check to see if a number is zero > >3. Copy data from one memory location to another > > > >I was wondering if anyone can point me to a chart for instance, that > >shows such a reduction (I'm guessing mostly with regard to number one > >above). To further clarify, I guess, I can derive for instance, an xor > >operation with only using additions, etc. Of course, a program with > >such a primitive instruction set would be large (similar to coding in > >binary I guess). > > > > Tanenbaum is probably correct ... I haven't given it enough thought. > > If you're interested in reading about a real computer with a sand > simple instruction set, Lincoln Lab's TX-0 (tee-ex-zero) "tixo" > computer had only 4 instructions: store, add, conditional branch, and > a "trap" instruction that accessed system registers, performed I/O and > a few other useful things based on the operand. There's some stuff > about it online at: > > http://www.bitsavers.org/pdf/mit/tx-0/ > and > http://www.tixo.org/ > > I don't know of any ready references for the kind of code reduction > and/or simplification you're interested in. Your best bet might be > to find and look at some actual tixo code to see how real problems > were attacked with the limited instruction set. > > There's not much "interesting" code at the above links, however, > there are some MIT lab memos at bitsavers.org which talk about > applications and code libraries being made available for the tixo. If > you are able to locate the actual code for some of the more > interesting ones (assembler, debugger, FP interpreter) I'm sure you > could learn a lot by studying it. > > George > -- > for email reply remove "/" from address Or you can google comp.arch archives. Look for "single instruction computer" or "minimal instruction set" and stuff like that. Couple years back, as I recall. I didn't pay much attention. del cecchi |