From: Terje Mathisen Newsgroups: alt.folklore.computers Subject: Re: RAD50 (was: Q: Why not (2^n)-bit?) Date: Wed, 23 Aug 2000 21:43:43 +0200 Organization: Hydro Lines: 34 Message-ID: <39A4296E.2EBADFF1@hda.hydro.com> References: <8n8mcb$ogt$1@yorikke.arb-phys.uni-dortmund.de> <39983350.2BF604F4@ev1.net> <39984D05.AB446489@elepar.com> <967014068snz@dsl.co.uk> NNTP-Posting-Host: iabrahmspc.nho.hydro.com Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit X-Mailer: Mozilla 4.75 [en] (Windows NT 5.0; U) X-Accept-Language: en Path: chonsp.franklin.ch!pfaff.ethz.ch!news-zh.switch.ch!news.nextra.ch!newsfeed1.online.no!newsfeed.online.no!hydro.com!not-for-mail Xref: chonsp.franklin.ch alt.folklore.computers:62476 Brian {Hamilton Kelly} wrote: > Moreover, whilst the thinking behind it might be considered as "using the > obvious multiply-by-40-and-add approach", the *implementation* most > definitely did not use those machine operations. IIRC, the conversion > algorithms within RSX-11M were each less than twenty lines of assembler, > and performed the whole conversion in far fewer cycles than even a single > multiply would have demanded. OK, now I'm interested! Doing the packing is quite easy, 40 = 8 * 5 = 8 * (4 + 1), i.e. x86 asm: ; Assume EAX, EBX and ECX holds the three letter values, as numbers from 0..39 lea eax,[eax+eax*4] ; EAX *= 5 lea eax,[ebx+eax*8] ; EAX = EAX*8 + EBX lea eax,[eax+eax*4] lea eax,[ecx+eax*8] ; result = EAX * 1600 + EBX * 40 + ECX On a 486 or later cpu, the code above would require about 7 cycles, due to address generation interlocks caused by the LEA opcode. A Pentium or later cpu might be faster with larger but parallel code. However, extracting the individual letters is quite a bit harder, esp. if even a reciprocal multiplication is off limits. How did they achieve this? Terje -- - Using self-discipline, see http://www.eiffel.com/discipline "almost all programming can be viewed as an exercise in caching" ###### From: jones@cs.uiowa.edu (Douglas W. Jones,201H MLH,3193350740,3193382879) Newsgroups: alt.folklore.computers Subject: Re: RAD50 (was: Q: Why not (2^n)-bit?) Date: 23 Aug 2000 20:45:01 GMT Organization: The University of Iowa Lines: 30 Message-ID: <8o1d4d$g2a$1@flood.weeg.uiowa.edu> References: <967014068snz@dsl.co.uk> NNTP-Posting-Host: pyrite.cs.uiowa.edu X-Trace: flood.weeg.uiowa.edu 967063501 16458 128.255.28.3 (23 Aug 2000 20:45:01 GMT) X-Complaints-To: usenet@news.uiowa.edu NNTP-Posting-Date: 23 Aug 2000 20:45:01 GMT Path: chonsp.franklin.ch!pfaff.ethz.ch!news-zh.switch.ch!newsfeed-zh.ip-plus.net!news.ip-plus.net!news.tesion.net!news.belwue.de!news.uni-stuttgart.de!uni-erlangen.de!newsfeeds.belnet.be!news.belnet.be!newsfeed.direct.ca!look.ca!logbridge.uoregon.edu!news.physics.uiowa.edu!news.uiowa.edu!not-for-mail Xref: chonsp.franklin.ch alt.folklore.computers:62499 From article <967014068snz@dsl.co.uk>, by bhk@dsl.co.uk (Brian {Hamilton Kelly}): > Moreover, whilst the thinking behind it might be considered as "using the > obvious multiply-by-40-and-add approach", the *implementation* most > definitely did not use those machine operations. IIRC, the conversion > algorithms within RSX-11M were each less than twenty lines of assembler, > and performed the whole conversion in far fewer cycles than even a single > multiply would have demanded. Two equivalent methods to multiply by 40 in C: A) X = 40 * Y; B) X = (Y + (Y << 2)) << 3; The second can be translated to the following sequence of PDP-11 instructions: MOV Y,R1 ASL R1 ASL R1 ADD Y,R1 ASL R1 ASL R1 ASL R1 MOV R1,X Doug Jones jones@cs.uiowa.edu ###### Message-ID: <39A4067A.58AEDBAE@trailing-edge.com> Date: Wed, 23 Aug 2000 17:14:34 -0400 From: Tim Shoppa Organization: Trailing Edge Technology X-Mailer: Mozilla 3.03Gold (X11; I; OpenVMS V7.2 AlphaServer 1200 5/533 4MB) MIME-Version: 1.0 Newsgroups: alt.folklore.computers Subject: Re: RAD50 (was: Q: Why not (2^n)-bit?) References: <8n8mcb$ogt$1@yorikke.arb-phys.uni-dortmund.de> <39983350.2BF604F4@ev1.net> <39984D05.AB446489@elepar.com> <967014068snz@dsl.co.uk> <39A4296E.2EBADFF1@hda.hydro.com> Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Lines: 98 NNTP-Posting-Host: 63.73.218.130 X-Trace: reader0.news.uu.net 967065275 18147 63.73.218.130 Path: chonsp.franklin.ch!pfaff.ethz.ch!news-zh.switch.ch!newsfeed-zh.ip-plus.net!news.ip-plus.net!news.tesion.net!news.belwue.de!news-stu1.dfn.de!news-koe1.dfn.de!news.ruhrgebiet.individual.net!news-fra.pop.de!ams.uu.net!ffx.uu.net!spool0.news.uu.net!reader0.news.uu.net!not-for-mail Xref: chonsp.franklin.ch alt.folklore.computers:62495 Terje Mathisen wrote: > However, extracting the individual letters is quite a bit harder, esp. > if even a reciprocal multiplication is off limits. How did they achieve > this? A very simple repeated subtraction. The source code is below; note that after doing argument checking, the actual work is done by just 23 instructions and a small (4 word) lookup table. .SBTTL $RD5AS - SYSLIB service rouitne ; ; $RD5AS - converts one word in RD50 format into ASCII ; ; CALLING SEQUENCE: CALL $RD5ASC ; ; INPUT PARAMETERS: ; ; R0 - input string ; R5 -> output area ; ; output - converted ASCII characters ; .PSECT SYS$I,I $RD5AS:: ; Entry point to one RAD50 word to ASCII ; cnversion routine MOV #3,R1 ; R1 = number of characters in one RAD50 word BR CNTN R50ASC:: ; Entry point to RAD50 to ASCII ; convertion ; rouitne MOV (R5)+,R4 ;R4(low byte) <- arg count CALL $NXVAL ; get 'icnt' # of characters to output BCS ERR ; If CS, error - 'icnt' wasn't supplied MOV R0,R1 ; R1 = # of chars to output CALL $NXADR ; get 'input' arg - address of input ; area BCS ERR ; If CS, error - "input' arg wasn't ; supplied MOV R0,R2 ; R2 -> input area CALL $NXADR ; Get 'output' arg - addres of output ; area BCS ERR ; If CS, error - 'output' wasn't ; supplied MOV R0,R5 ; R5 -> output area NXWRD: MOV (R2)+,R0 ; R0 = current input word CNTN: MOV #DIVTAB,R3 ; R3 -> division table 1$: TST -(R3) ; new word required yet? BEQ NXWRD ; yes MOV #-1,R4 ; initialize quotient reg CMP #174777,R0 ; RAD50 value too large? BLO 4$ ; yes - output question marks 3$: INC R4 ; divide by appropriate power of 50(8) SUB @R3,R0 BCC 3$ ADD @R3,R0 ; restore dividend TST R4 ; character is a blank? BEQ 5$ ; yes CMP #33,R4 ; dollar sign, period, or digit? BLO 6$ ; period or digit BEQ 7$ ; dollar sign 4$: ADD #40,R4 ; else alpha (A-Z) or question mark ; (see above) 5$: ADD #16,R4 ; 6$: ADD #11,R4 ; 7$: ADD #11,R4 ; 8$: MOVB R4,(R5)+ ; store converted character in output DEC R1 ; any more chars to produce? BNE 1$ ; yes RETURN ERR: TRAP $MSARG ; handle any missing argument in call RETURN .PSECT SYS$S,D .WORD 0 ;END-OF-TABLE FLAG .WORD 1 .WORD 50 .WORD 3100 DIVTAB= . ;RAD50 DIVISION TABLE .END Tim. (shoppa@trailing-edge.com) ###### Message-ID: <39A4FFBA.9627194@netinsight.se> From: Johnny Billquist Organization: Netinsight AB X-Mailer: Mozilla 4.5 [en] (X11; I; Linux 2.2.14 i686) X-Accept-Language: en MIME-Version: 1.0 Newsgroups: alt.folklore.computers Subject: Re: RAD50 (was: Q: Why not (2^n)-bit?) References: <8n8mcb$ogt$1@yorikke.arb-phys.uni-dortmund.de> <39983350.2BF604F4@ev1.net> <39984D05.AB446489@elepar.com> <967014068snz@dsl.co.uk> Content-Type: text/plain; charset=iso-8859-1 Content-Transfer-Encoding: 8bit Lines: 17 Date: Thu, 24 Aug 2000 10:58:03 GMT NNTP-Posting-Host: 194.16.221.33 X-Complaints-To: abuse@telia.com X-Trace: newsc.telia.net 967114683 194.16.221.33 (Thu, 24 Aug 2000 12:58:03 MET DST) NNTP-Posting-Date: Thu, 24 Aug 2000 12:58:03 MET DST Path: chonsp.franklin.ch!pfaff.ethz.ch!news-zh.switch.ch!news-ge.switch.ch!newsfeeds.belnet.be!news.belnet.be!news.tele.dk!128.39.3.166!uninett.no!newsfeed1.enitel.no!masternews.telia.net!newsc.telia.net.POSTED!not-for-mail Xref: chonsp.franklin.ch alt.folklore.computers:62475 Brian {Hamilton Kelly} wrote: > > (Actually, it wouldn't surprise me at all to hear that RAD50 was alive > and well and living in whatever O/S is still used on those bits of the > PDP-11 family that are still around: it was, after all, used in the > recognition of command-line verbs, like HELLO.) Of course it's still alive. RSX is still alive, after all... /Using it daily... -- Johnny Billquist | johnny.billquist@netinsight.net Net Insight AB | phone: +46 8 685 04 88 Västberga Allé 9 | fax: +46 8 685 04 20 Box 42093 | SE-126 30 STOCKHOLM, Sweden | http://www.netinsight.net ###### Message-ID: <39A513AD.2FFDFFAD@netinsight.se> From: Johnny Billquist Organization: Netinsight AB X-Mailer: Mozilla 4.5 [en] (X11; I; Linux 2.2.14 i686) X-Accept-Language: en MIME-Version: 1.0 Newsgroups: alt.folklore.computers Subject: Re: RAD50 (was: Q: Why not (2^n)-bit?) References: <967014068snz@dsl.co.uk> <8o1d4d$g2a$1@flood.weeg.uiowa.edu> Content-Type: text/plain; charset=iso-8859-1 Content-Transfer-Encoding: 8bit Lines: 48 Date: Thu, 24 Aug 2000 12:23:09 GMT NNTP-Posting-Host: 194.16.221.33 X-Complaints-To: abuse@telia.com X-Trace: newsc.telia.net 967119789 194.16.221.33 (Thu, 24 Aug 2000 14:23:09 MET DST) NNTP-Posting-Date: Thu, 24 Aug 2000 14:23:09 MET DST Path: chonsp.franklin.ch!pfaff.ethz.ch!news-zh.switch.ch!news-ge.switch.ch!news.maxwell.syr.edu!uninett.no!newsfeed1.enitel.no!masternews.telia.net!newsc.telia.net.POSTED!not-for-mail Xref: chonsp.franklin.ch alt.folklore.computers:62484 "Douglas W. Jones,201H MLH,3193350740,3193382879" wrote: > > From article <967014068snz@dsl.co.uk>, > by bhk@dsl.co.uk (Brian {Hamilton Kelly}): > > > Moreover, whilst the thinking behind it might be considered as "using the > > obvious multiply-by-40-and-add approach", the *implementation* most > > definitely did not use those machine operations. IIRC, the conversion > > algorithms within RSX-11M were each less than twenty lines of assembler, > > and performed the whole conversion in far fewer cycles than even a single > > multiply would have demanded. > > Two equivalent methods to multiply by 40 in C: > > A) X = 40 * Y; > > B) X = (Y + (Y << 2)) << 3; > > The second can be translated to the following sequence of PDP-11 > instructions: > > MOV Y,R1 > ASL R1 > ASL R1 > ADD Y,R1 > ASL R1 > ASL R1 > ASL R1 > MOV R1,X Or, if we want to be silly... MOV Y,X ASL X ASL X ADD Y,X ASL X ASL X ASL X Johnny -- Johnny Billquist | johnny.billquist@netinsight.net Net Insight AB | phone: +46 8 685 04 88 Västberga Allé 9 | fax: +46 8 685 04 20 Box 42093 | SE-126 30 STOCKHOLM, Sweden | http://www.netinsight.net