home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / alt / folklore / computer / 16680 < prev    next >
Encoding:
Internet Message Format  |  1992-11-23  |  5.0 KB
  1. Path: sparky!uunet!zaphod.mps.ohio-state.edu!cis.ohio-state.edu!rutgers!news.columbia.edu!watsun.cc.columbia.edu!lasner
  2. From: lasner@watsun.cc.columbia.edu (Charles Lasner)
  3. Newsgroups: alt.folklore.computers
  4. Subject: Re: Sync Three Times...
  5. Message-ID: <1992Nov23.194532.5315@news.columbia.edu>
  6. Date: 23 Nov 92 19:45:32 GMT
  7. References: <Bxypzx.L4p@NeoSoft.com> <1eis4rINNfni@uniwa.uwa.edu.au> <STEVEV.92Nov22235456@miser.uoregon.edu>
  8. Sender: usenet@news.columbia.edu (The Network News)
  9. Reply-To: lasner@watsun.cc.columbia.edu (Charles Lasner)
  10. Organization: Columbia University
  11. Lines: 90
  12. Nntp-Posting-Host: watsun.cc.columbia.edu
  13.  
  14. In article <STEVEV.92Nov22235456@miser.uoregon.edu> stevev@miser.uoregon.edu (Steve VanDevender) writes:
  15. >
  16. >You can get by with just a carry flag in a processor using
  17. >two's-complement arithmetic.  You can test if a number is
  18. >non-zero by adding a word of all ones -- if true, the carry flag
  19. >will be set.  cjl can undoubtedly describe many other tricks,
  20. >including his favorite method of testing for a value in a given
  21. >range using only one conditional branch, which uses only a test
  22. >of the carry flag (of course, this makes it easy to do on a
  23. >PDP-8).
  24.  
  25. On the PDP-8, just test if a numer is non-zero by testing for AC not=0
  26. (SNA).  Straightforward.  But, yes, if that didn't exist, you could set
  27. the carry flag (called the Link on the PDP-8) to a known state, and when
  28. you add an all-ones word to the AC, the carry would flip unless it was
  29. all zeroes to begin with.
  30.  
  31. As to the other "trick", yes, this is a method that is general-purpose to
  32. any machine, and doesn't depend on any excess precision trick, etc.  For
  33. any N-bit register, you can test for whether any possible value (between
  34. 0 and 2^(N-1) unsigned) is in a range, as long as the range of legal
  35. values is itself 2^(N-1)-1 or smaller.  Only the main arithmetic register
  36. is involved, assuming there is add from memory avaiilable.  Here's a PDP-8
  37. version to segregate out 12-bit values that could be in the range 0000 to
  38. 4095 decimal (it's a 12-bit machine) that happen to fall into the range
  39. of 0060 through 0067 octal, or are the ASCII digits "0" thorugh "7".
  40.  
  41.     *200        /Set a usual origin for a stand-alone program
  42.  
  43. START,    CLA        /Clean up the accumulator, although start key does it
  44.     TAD    CHAR    /Get the test contents that could be anything
  45.     TAD    (-70)    /Add on -(upper limit of legal values+1)
  46.     CLL        /Clear the carry flag now; the -8 won't auto-do it
  47.     TAD    (10)    /Add on (count of values in desired range)
  48.     SNL        /Skip if carry set
  49.     JMP    NOTDIG    /Go elsewhere if it flunks the test
  50.  
  51. /    Ac now contains 0000 through 0007, corresponding to "0" through "7"
  52.  
  53. Note that we even got a nice "frill" in that the residue of the position
  54. within the table is left in the accumulator.
  55.  
  56. In a "real" program, the initial CLA to clear the accumulator wouldn't exist
  57. because the PDP-8 store instruction DCA stores into memory and clears the AC
  58. afterwards.  Also, all skip conditions can be optionally micro-coded to
  59. also clear the AC as well.  For example, if the residue wasn't needed,
  60. then the SNL could be replaced with SNL CLA which skips if the Link bit is
  61. set, then clears the AC.
  62.  
  63. Moreover, if the test value is stored with the -70 offset applied, as in
  64. some sort of numerical input routine, then CHAR would already contain
  65. the test value -70.  Note that TAD is two's complement add, and that PDP-8
  66. convention really is that the previous AC contents is usually 0000, thus
  67. the TAD CHAR would effectively be a load operation.
  68.  
  69. The only overhead is the need for the CLL instruction because the -8 doesn't
  70. automatically reset the carry flag, and we need it in some known state
  71. at the point of the test.  Also, note that if the TAD CHAR and the TAD (-70)
  72. are carried out separately, then this CLL is needed after the adding of the
  73. two together, because for some values, this might flip the carry at that
  74. point, so a routine entry state for the carry isn't good enough.
  75.  
  76. So, the smallest practical code would be
  77.  
  78.     TAD    CHARM70        /Get the pre-subtracted test value
  79.     CLL            /Clear the Link now
  80.     TAD    (10)        /Add on the test range
  81.     SNL            /Skip if carry flipped
  82.     JMP    NOTDIG        /Where to go on bad cases
  83.  
  84. /    Fall through when one of the desired values is found.
  85.  
  86. Note that the entire routine takes 6 machine cycles assuming the test succeeds
  87. and 7 if it fails. (TAD is two cycle - one to fetch and one to address the
  88. memory location.)
  89.  
  90. We can even trim down one more cycle - On PDP-8/e, the MQ register is
  91. always implemented, and it's recommended to be used as a fast temporary.
  92. Thus, the test value-70 would likely be stored in the MQ register as a global
  93. parameter if there was much testing involved.  (When you write code for the
  94. entire product line, you have to avoid these extensions, because the MQ
  95. isn't available at all on the 8/l, and is only optional on 8, LINC-8, and 8/i
  96. and -12.)  Thus, the first TAD CHARM70 can be replaced with the one-cycle
  97. MQA which transfers the MQ -> AC.  Moreover, it can be microcoded in one
  98. cycle as CLA MQA to ensure the AC load is certain.
  99.  
  100. So, the fastest version is 5 instructions and 5 machine cycles if it
  101. succeeds, and 6 if it fails.
  102.  
  103. cjl
  104.