Movatterモバイル変換
[0]ホーム
[RFC Home] [TEXT|PDF|HTML] [Tracker] [IPR] [Info page]
UNKNOWN
Updated by:228Network Working Group S. CrockerRequest for Comments #70 UCLA 15 October 70 A Note on PaddingThe padding on a message is a string of the form 10*. For Hosts withword lengths 16, 32, 48, etc., bits long, this string is necessarily inthe last word received from the Imp. For Hosts with word lengths whichare not a multiple of 16 (but which are at least 16 bits long), the 1bit will be in either the last word or the next to last word. Ofcourse if the 1 bit is in the next to last word, the last word is allzero.An unpleasant coding task is discovering the bit position of the 1 bitwithin its word. One obvious technique is to repeatedly test thelow-order bit, shifting the word right one bit position if thelow-order bit is zero. The following techniques are more pleasant.Isolating the Low-Order BitLet W be a non-zero word, where the word length is n. Then W is of theform x....x10....0 \__ __/\__ __/ V V n-k-1 kwhere 0<=k<nand the x's are arbitrary bits.Assuming two's complement arithmetic, W-1 = x....x01....1 _ _ -W = x....x10....0 _ _ _W = x....x01....1By using AND, OR and exclusive OR with various pairs of thesequantities, useful new forms are obtained.For example, [Page 1]
Network Working Group A Note on PaddingRFC 70W AND W-1 xx...x00....0 \__ __/\__ __/ V V n-k-1 kthus removing the low-order 1 bit;also W AND -W = 0....010....0 __ __/__ __/ V V n-k-1 kthus isolating the low-order bit.Below, we will focus solely on this last result; however, in aparticular application it may be advantageous to use a variation.Determining the Position of an Isolated BitThe two obvious techniques for finding the bit position of an isolatedbit are to shift repetitively with tests, as above, and to use floatingnormalization hardware. On the PDP-10, in particular, the JFFOinstruction is made to order*. On machines with hexadecimalnormalization, e.g. IBM 360's and XDS Sigma 7's, the normalizationhardware may not be very convenient. A different approach usesdivision and table look-up. kA word with a single bit on has an unsigned integer value of 2 for k0<=k<n. If we choose a p such that mod(2 ,p) is distinct for each0<=k<n, we can make a table of length p which gives the correspondence kbetween mod(2 ,p) and k. The remainder of this paper is concerned withthe selection of an appropriate divisor p for each word length n.*Some of the CDC machines have a "population count" instruction which kgives the number of bits in a word. Note the 2 -1 has exactly k bitson. [Page 2]
Network Working Group A Note on PaddingRFC 70Example Let n = 8 and p = 11 Then 0 mod(2, 11) = 1 1 mod(2, 11) = 2 2 mod(2, 11) = 4 3 mod(2, 11) = 8 4 mod(2, 11) = 5 5 mod(2, 11) = 10 6 mod(2, 11) = 9 7 mod(2, 11) = 7 This yields a table of the form remainder bit position 0 -- 1 0 2 1 3 -- 4 2 5 4 6 -- 7 7 8 3 9 6 10 5 [Page 3]
Network Working Group A Note on PaddingRFC 70Good DivisorsThe divisor p should be as small as possible in order to minimize thelength of the table. Since the divisor must generate n distinctremainders, the divisor will certainly need to be at least n. Aremainder of zero, however, can occur only if the divisor is a power of j2. If the divisor is a small power of 2, say 2for j < n-1, it willnot generate n distinct remainders; if the divisor is a larger power of n-1 n2, the correspondence table is either 2 or 2 in length. We canthus rule out zero as a remainder value, so the divisor must be atleast one more than the word length. This bound is in fact achievedfor some word lengths.Let R(p) be the number of distinct remainders p generates when dividedinto successively higher powers of 2. The distinct remainders all occurfor the R(p) lowest powers of 2. Only odd p are interesting and thefollowing table gives R(p) for odd p between 1 and 21. p R(p) p R(p) 1 1 13 12 3 2 15 4 5 4 17 8 7 3 19 18 9 6 21 6 11 10This table shows that 7, 15, 17 and 21 are useless divisors becausethere are smaller divisors which generate a larger number of distinctremainders. If we limit our attention to p such that p > p' =>R(p) > R(p'), we obtain the following table of useful divisors forp < 100. [Page 4]
Network Working Group A Note on PaddingRFC 70 p R(p) p R(p) 1 1 29 28 3 2 37 36 5 4 53 52 9 6 59 58 11 10 61 60 13 12 67 66 19 18 83 82 25 20Notice that 9 and 25 are useful divisors even though they generate only6 and 20 remainders, respectively.Determination of R(p)If p is odd, the remainders 0 mod(2 ,p) 1 mod(2 ,p) . . . twill be between 1 and p-1 inclusive. At some power of 2, say 2 , there k twill be a repeated remainder, so that for some k < t, 2 = 2 mod p. t+1 k+1Since 2 = 2 mod p t+2 k+2and 2 = 2 mod p . . . etc. 0 t-1all of the distinct remainders occur for 2 ...2 . Therefore, R(p)=t. [Page 5]
Network Working Group A Note on PaddingRFC 70Next we show that R(p) 2 = 1 mod p R(p) kWe already know that 2 = 2 mod pfor some 0<=k<R(p). Let j=R(p)-k so 0<j<=R(p). Then k+j k 2 = 2 mod p j k kor 2 *2 = 2 mod p j kor (2 -1)*2 = 0 mod p k jNow p does not divide 2 because p is odd, so p must divide 2 -1. Thus j 2 -1 = 0 mod p j 2 = 1 mod pSince j is greater than 0 by hypothesis and since ther is no k otherthan 0 less than R(p) such that k 0 2 = 2 mod p, R(p)we must have j=R(p), or 2 = 1 mod p. kWe have thus shown that for odd p, the remainders mod(2 ,p) are uniquefor k = 0, 1,..., R(p)-1 and then repeat exactly, beginning with R(p) 2 = 1 mod p.We now consider even p. Let q p = p'*2 , k k kwhere p' is odd. For k<q, mod(2 ,p) is clearly just 2 because 2 <p.For k>=q, k q k-q mod(2 ,p) = 2 *mod(2 ,p'). [Page 6]
Network Working Group A Note on PaddingRFC 70From this we can see that the sequence of remainders will have an q-1initial segment of 1, 2, ...2 of length q, and repeating segments oflength R(p'). Therefore, R(p) = q+R(p'). Since we normally expect R(p) ~ p,even p generally will not be useful.I don't know of a direct way of choosing a p for a given n, but theprevious table was generated from the following Fortran program rununder the SEX system at UCLA. 0 CALL IASSGN('OC ',56) 1 FORMAT(I3,I5) M=0 DO 100 K=1,100,2 K=1 L=0 20 L=L+1 N=MOD(2*N,K) IF(N.GT.1) GO TO 20 IF(L.LE.M) GO TO 100 M=L WRITE(56,1)K,L 100 CONTINUE STOP END Fortran program to computer useful divisorsIn the program, K takes on trial values of p, N takes on the values ofthe successive remainders, L counts up to R(p), and M remembers theprevious largest R(p). Execution is quite speedy. [Page 7]
Network Working Group A Note on PaddingRFC 70Results from Number TheoryThe quantity referred to above as R(p) is usually written Ord 2 and is pread "the order of 2 mod p". The maximum value of Ord 2 is given by pEuler's phi-function, sometimes called the totient. The totient of apositive integer p is the number of integers less than p which arerelatively prime to p. The totient is easy to compute from arepresentation of p as a product of primes: n n n Let p = p 1 * p 2 ... p k 1 2 kwhere the p are distinct primes. Then i k -1 k -1 k -1 phi(p) = (p - 1) * p 1 * (p - 1) * p 2 ... (p - 1) * p k 1 1 2 2 k kIf p is prime, the totient of p is simply phi(p) = p-1.If p is not prime, the totient is smaller.If a is relatively prime to p, then Euler's generalization of Fermat'stheorem states phi(m) a = 1 mod p.It is this theorem which places an upper bound Ord 2, because Ord 2 is p pthe smallest value such that Ord 2 2 p = 1 mod pMoreover it is always true that phi(p) is divisible by Ord 2. p [Page 8]
Network Working Group A Note on PaddingRFC 70AcknowledgementsBob Kahn read an early draft and made many comments which improved theexposition. Alex Hurwitz assured me that a search technique isnecessary to compute R(p), and supplied the names for the quantitiesand theorems I uncovered. [ This RFC was put into machine readable form for entry ] [ into the online RFC archives by Guillaume Lahaye and ] [ John Hewes 6/97 ] [Page 9]
[8]ページ先頭