Note on Padding
RFC 70

Document Type RFC - Unknown (October 1970; No errata)
Updated by RFC 228
Last updated 2013-03-02
Stream Legacy
Formats plain text pdf html bibtex
Stream Legacy state (None)
Consensus Boilerplate Unknown
RFC Editor Note (None)
IESG IESG state RFC 70 (Unknown)
Telechat date
Responsible AD (None)
Send notices to (None)
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,

                                                                [Page 1]
Network Working Group      A Note on Padding                      RFC 70

            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.

                                                                [Page 2]
Network Working Group      A Note on Padding                      RFC 70

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

                                                                [Page 3]
Network Working Group      A Note on Padding                      RFC 70

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
Show full document text