home *** CD-ROM | disk | FTP | other *** search
/ The Hacker's Encyclopedia 1998 / hackers_encyclopedia.iso / rfc / 1 / rfc0401.txt < prev    next >
Encoding:
Text File  |  2003-06-11  |  3.8 KB  |  113 lines
  1.  
  2.  
  3.  
  4.  
  5.  
  6.  
  7. Network Working Group                                 Jim Hansen
  8. Request for Comment #401                              Center for Advanced
  9. NIC #11923                                              Computation
  10. Category:  D.6                                        University of Illinois
  11. Updates:  RFC #387                                    October 23, 1972
  12. Obsoletes: None
  13.  
  14.  
  15.                Conversion of NGP-0 Coordinates to Device
  16.                -----------------------------------------
  17.                           Specific Coordinates
  18.                           --------------------
  19.  
  20. Conversion of NGP-0 coordinates to floating point PDP-10 coordinates
  21. was discussed in RFC #387.  In general, however, it is undesirable to
  22. convert NGP coordinates to floating point coordinates because real
  23. devices require integer addressing.  To this end, a means is described
  24. to convert NGP coordi- nates to integer coordinates in the range zero
  25. to M, where M is the maximum address of the device screen on a machine
  26. using 2's complement arithmetic.  It would not, however, be difficult
  27. to modify this algorithm to operate on machines using one's complement
  28. or sign-magnitude arithmetic.
  29.  
  30. First consider the NGP coordinate format:
  31.  
  32.                    +--+-----------+
  33.                    |  |   n       |
  34.                    +--+-----------+
  35.                     s ^  FRACTION
  36.                     i
  37.                     g
  38.                     n
  39.  
  40. Where the sign occupies the most significant bit of the coordinate
  41. followed by bits of numerical information (initial implementation of
  42. NGP requires N=15).  Negative numbers are represented by 2's
  43. complement.  Conversion to device coordinates is accomplished by:
  44.  
  45.                     D = S * f + S
  46.  
  47. Where D =>integer device coordinate
  48.       S =>scaling factor (typically M/2)
  49.       f =>NGP fractional coordinate
  50.  
  51. Let us rewrite this as:
  52.  
  53.                             n     n
  54.                     D = S*(2 *f)/2 +S
  55.  
  56.  
  57.  
  58.                                                                 [Page 1]
  59.  
  60. Now factor S into two terms:
  61.  
  62.                             I
  63.                     S= Q * 2
  64.  
  65. Where Q is an odd integer and I is an integer.
  66.  
  67. When:                        I   n     n
  68.                     D = Q * 2 *(2 *f)/2  +S
  69.  
  70.                              I-n   n
  71.                       = Q * 2   *(2 *f)  +S
  72.              n
  73. The factor (2 *f) is represented in 2's complement form simply by
  74. extending the sign bit of f into the upper portion of the computer
  75. word, If Q = 1 (as it would be with many devices), it can be ignored.
  76. If Q >< 1, we may console ourselves that an integer multiply is faster
  77. on most machines than a floating point multiply.  In fact, on a
  78. PDP-10, this multiply can usually be performed with no access to
  79. memory since Q is usually small.
  80.  
  81.                           I-n
  82. We are now left with the 2    factor.  This can be accomplished with an
  83. arithmetic shift left by (I-n) or an arithmetic shift right by (n-I)
  84. as is appropriate.  The offset factor, S, may now be added using an
  85. integer add.
  86.  
  87. The procedure for converting NGP coordinates to integer device
  88. coordinates is then:
  89.  
  90.                1.   move coordinate to a register and extend sign
  91.                2.   integer multiply by Q (if necessary)
  92.                3.   arithmetic shift left by (I-n)
  93.                4.   integer add S
  94.  
  95.  
  96. This procedure would generally be much faster than:
  97.  
  98.                1.   move coordinate to register and extend sign
  99.                2.   float fractional coordinate
  100.                3.   floating point multiply
  101.                4.   floating point add
  102.                5.   conversion to fixed point
  103.  
  104.        [ This RFC was put into machine readable form for entry ]
  105.        [ into the online RFC archives by BBN Corp. under the   ]
  106.        [ direction of Alex McKenzie.                      1/97 ]
  107.  
  108.  
  109.  
  110.  
  111.                                                                 [Page 2]
  112.  
  113.