Browse Prior Art Database

# Note on Padding (RFC0070)

IP.com Disclosure Number: IPCOM000003745D
Original Publication Date: 1970-Oct-01
Included in the Prior Art Database: 2019-Feb-11
Document File: 9 page(s) / 9K

## Publishing Venue

Internet Society Requests For Comment (RFCs)

## Related People

S.D. Crocker: AUTHOR

## Related Documents

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 38% of the total text.

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...