Browse Prior Art Database

Note on Padding (RFC0070)

IP.com Disclosure Number: IPCOM000003745D
Original Publication Date: 1970-Oct-15
Included in the Prior Art Database: 2000-Sep-13
Document File: 8 page(s) / 12K

Publishing Venue

Internet Society Requests For Comment (RFCs)

Related People

S.D. Crocker: AUTHOR

Abstract

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.

This text was extracted from a ASCII document.
This is the abbreviated version, containing approximately 22% 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

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,

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.

...