Note on Padding
How to find the end-of-message padding bit in a machine word with a few logical operations and a lookup table.
Crocker, S.D., "Note on Padding", RFC 70, DOI 10.17487/RFC0070, October 1970, <https://www.rfc-editor.org/info/rfc70>.
@misc{rfc70,
series = {Request for Comments},
number = 70,
howpublished = {RFC 70},
publisher = {RFC Editor},
doi = {10.17487/RFC0070},
url = {https://www.rfc-editor.org/info/rfc70},
author = {S.D. Crocker},
title = {{Note on Padding}},
pagetotal = 9,
year = 1970,
month = oct,
} RFC text
Contents
Network Working Group S. Crocker
Request for Comments #70 UCLA
15 October 70
A Note on Padding
The padding on a message is a string of the form 10*. For Hosts with
word lengths 16, 32, 48, etc., bits long, this string is necessarily in
the last word received from the Imp. For Hosts with word lengths which
are not a multiple of 16 (but which are at least 16 bits long), the 1
bit will be in either the last word or the next to last word. Of
course if the 1 bit is in the next to last word, the last word is all
zero.
An unpleasant coding task is discovering the bit position of the 1 bit
within its word. One obvious technique is to repeatedly test the
low-order bit, shifting the word right one bit position if the
low-order bit is zero. The following techniques are more pleasant.
Isolating the Low-Order Bit
Let W be a non-zero word, where the word length is n. Then W is of the
form
x....x10....0
\__ __/\__ __/
V V
n-k-1 k
where 0<=k<n
and the x's are arbitrary bits.
Assuming two's complement arithmetic,
W-1 = x....x01....1
_ _
-W = x....x10....0
_ _ _
W = x....x01....1
By using AND, OR and exclusive OR with various pairs of these
quantities, useful new forms are obtained.
For example,
W AND W-1 xx...x00....0
\__ __/\__ __/
V V
n-k-1 k
thus removing the low-order 1 bit;
also W AND -W = 0....010....0
__ __/__ __/
V V
n-k-1 k
thus isolating the low-order bit.
Below, we will focus solely on this last result; however, in a
particular application it may be advantageous to use a variation.
Determining the Position of an Isolated Bit
The two obvious techniques for finding the bit position of an isolated
bit are to shift repetitively with tests, as above, and to use floating
normalization hardware. On the PDP-10, in particular, the JFFO
instruction is made to order*. On machines with hexadecimal
normalization, e.g. IBM 360's and XDS Sigma 7's, the normalization
hardware may not be very convenient. A different approach uses
division and table look-up.
k
A word with a single bit on has an unsigned integer value of 2 for
k
0<=k<n. If we choose a p such that mod(2 ,p) is distinct for each
0<=k<n, we can make a table of length p which gives the correspondence
k
between mod(2 ,p) and k. The remainder of this paper is concerned with
the selection of an appropriate divisor p for each word length n.
*Some of the CDC machines have a "population count" instruction which
k
gives the number of bits in a word. Note the 2 -1 has exactly k bits
on.
Example
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
Good Divisors
The divisor p should be as small as possible in order to minimize the
length of the table. Since the divisor must generate n distinct
remainders, the divisor will certainly need to be at least n. A
remainder of zero, however, can occur only if the divisor is a power of
j
2. If the divisor is a small power of 2, say 2 for j < n-1, it will
not generate n distinct remainders; if the divisor is a larger power of
n-1 n
2, the correspondence table is either 2 or 2 in length. We can
thus rule out zero as a remainder value, so the divisor must be at
least one more than the word length. This bound is in fact achieved
for some word lengths.
Let R(p) be the number of distinct remainders p generates when divided
into successively higher powers of 2. The distinct remainders all occur
for the R(p) lowest powers of 2. Only odd p are interesting and the
following 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 10
This table shows that 7, 15, 17 and 21 are useless divisors because
there are smaller divisors which generate a larger number of distinct
remainders. If we limit our attention to p such that p > p' =>
R(p) > R(p'), we obtain the following table of useful divisors for
p < 100.
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 20
Notice that 9 and 25 are useful divisors even though they generate only
6 and 20 remainders, respectively.
Determination of R(p)
If p is odd, the remainders
0
mod(2 ,p)
1
mod(2 ,p)
.
.
.
t
will be between 1 and p-1 inclusive. At some power of 2, say 2 , there
k t
will be a repeated remainder, so that for some k < t, 2 = 2 mod p.
t+1 k+1
Since 2 = 2 mod p
t+2 k+2
and 2 = 2 mod p
.
.
.
etc.
0 t-1
all of the distinct remainders occur for 2 ...2 . Therefore, R(p)=t.
Next we show that
R(p)
2 = 1 mod p
R(p) k
We already know that 2 = 2 mod p
for 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 k
or 2 *2 = 2 mod p
j k
or (2 -1)*2 = 0 mod p
k j
Now 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 p
Since j is greater than 0 by hypothesis and since ther is no k other
than 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.
k
We have thus shown that for odd p, the remainders mod(2 ,p) are unique
for 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 k
where 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').
From this we can see that the sequence of remainders will have an
q-1
initial segment of 1, 2, ...2 of length q, and repeating segments of
length 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 the
previous table was generated from the following Fortran program run
under 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 divisors
In the program, K takes on trial values of p, N takes on the values of
the successive remainders, L counts up to R(p), and M remembers the
previous largest R(p). Execution is quite speedy.
Results from Number Theory
The quantity referred to above as R(p) is usually written Ord 2 and is
p
read "the order of 2 mod p". The maximum value of Ord 2 is given by
p
Euler's phi-function, sometimes called the totient. The totient of a
positive integer p is the number of integers less than p which are
relatively prime to p. The totient is easy to compute from a
representation of p as a product of primes:
n n n
Let p = p 1 * p 2 ... p k
1 2 k
where 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 k
If 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's
theorem states
phi(m)
a = 1 mod p.
It is this theorem which places an upper bound Ord 2, because Ord 2 is
p p
the smallest value such that
Ord 2
2 p = 1 mod p
Moreover it is always true that phi(p) is divisible by Ord 2.
p
Acknowledgements
Bob Kahn read an early draft and made many comments which improved the
exposition. Alex Hurwitz assured me that a search technique is
necessary to compute R(p), and supplied the names for the quantities
and 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 ]
AI ELI5
On this page
§1The Padding Problem
In this note Steve Crocker explains that the padding on a message is a string of the form 10*, that is, a 1 followed by zero or more 0 bits. For hosts with word lengths of 16, 32, 48 and so on, the padding is necessarily in the last word received from the IMP. For hosts with other word lengths of at least 16 bits, the 1 bit is in either the last word or the next to last word, and in the second case the last word is all zero.
The unpleasant part is finding the bit position of that 1 within its word. The obvious approach is to test the low-order bit repeatedly and shift right while it is zero. The note offers more pleasant techniques.
Messages end with a 1 and then blank space. The hard part is finding where that last 1 sits.
§2Isolating the Bit and Finding Its Position
Assuming two's complement arithmetic, a nonzero word W ends in a 1 followed by k zeros. Then W AND W-1 removes the low-order 1 bit, and W AND -W isolates it, leaving a word with a single bit set.
To get that bit's position, the obvious options are shifting with tests or floating normalization hardware, such as the JFFO instruction on the PDP-10. Hexadecimal normalization, as on IBM 360 and XDS Sigma 7 machines, may not be convenient. The note instead divides: a word with a single bit on has the value 2^k, so if the divisor p makes 2^k mod p distinct for every k below the word length n, a table of length p maps each remainder to a bit position.
First you cover up everything except the last switch. Then a quick arithmetic trick tells you which switch it was, using a small cheat sheet.
§3A Worked Example
For a word length of n = 8 and a divisor of p = 11, the values of 2^k mod 11 for k from 0 to 7 are 1, 2, 4, 8, 5, 10, 9 and 7. These give a lookup table of length 11 from remainder to bit position, in which remainders 0, 3 and 6 never occur.
For eight switches, dividing by 11 gives a different leftover for each switch. The leftover points to the switch number in the cheat sheet.
| Remainder | Bit position |
|---|---|
| 0 | -- |
| 1 | 0 |
| 2 | 1 |
| 3 | -- |
| 4 | 2 |
| 5 | 4 |
| 6 | -- |
| 7 | 7 |
| 8 | 3 |
| 9 | 6 |
| 10 | 5 |
§4Choosing a Good Divisor
The divisor should be as small as possible to keep the table short. It must produce at least n distinct remainders, and zero cannot be a useful remainder, so p must be at least one more than the word length. This bound is reached for some word lengths. Writing R(p) for the number of distinct remainders p produces, the note tabulates it for odd p up to 21, and shows that 7, 15, 17 and 21 are useless because smaller divisors generate more distinct remainders.
The list of useful divisors below 100 is 1, 3, 5, 9, 11, 13, 19, 25, 29, 37, 53, 59, 61, 67 and 83. The note also proves facts about R(p), says even divisors are generally not useful, gives a Fortran program, run on the SEX system at UCLA, that generated the table, and ends with number theory about the order of 2 modulo p and Euler's totient.
You want the smallest dividing number that still gives every switch its own leftover, so the cheat sheet stays short.