    Request for Comments: 713                           Jack Haverty  (JFH@MIT-DMS)
    NIC #34739                                                             Apr 1976

    I. ABSTRACT

    A mechanism is defined for use by message servers in
    transferring data between hosts.  The mechanism, called the
    MSDTP, is defined in terms of a model of the process as a
    translation between two sets of items, the abstract entities
    such as 'strings' and 'integers', and the formats used to
    represent such data as a byte stream.

    A proposed organization of a general data transfer
    mechanism is described, and the manner in which the MSDTP
    would be used in that environment is presented.

                                    -1-

    II. REFERENCES

    Black, Edward H., "The DMS Message Composer", MIT Project
    MAC, Programming Technology Division Document
    SYS.16.02.

    Burchfiel, Jerry D., Leavitt, Elsie M., Shapiro, Sonya and
    Strollo, Theodore R., compilers, "Tenex Users' Guide",
    Bolt Beranek and Newman, Cambridge, Mass., May 1971,
    revised January 1975, Descriptive sections on the TENEX
    subsystems: MAlLER, p. 116-11; MAlLSTAT, p. 118-119;
    READMAIL, p. 137; and SNDMSG, p. 165-170.

    Haverty, Jack, "Communications System Overview", MIT Project
    MAC, Programming Technology Division Document
    SYS.16.00.

    Haverty, Jack, "Communications System Daemon Manual", MIT
    Project MAC, Programming Technology Division Document
    SYS.16.01.

    ISI Information Automation Project, "Military Message
    Processing System Design," Internal Project
    Documentation (Out of Print), Jan. 1975

    Message Services Committee, "Interim Report", Jan. 28, 1975

    Mooers, Charlotte D., "Mailsys Message System: Manual For
    Users", Bolt Beranek and Newman, Cambridge, Mass., June
    1975 (draft).

    Myer, Theodore H., "Notes On The BBN Mail System", Bolt
    Beranek and Newman, November 8, 1974.

    Myer, Theodore H., and Henderson, D. Austin, "Message
    Transmission Protocol", Network Working Group RFC 680,
    NIC 32116, April 30, 1975.

    Postel, Jon, "The PCPB8 Format", NSW Proposal, June 5, 1975

    Tugender, R., and D. R. Oestreicher, "Basic Functional
    Capabilities for a Military Message Processing
    Service," ISI?RR-74-23., May 1975

    Vezza, Al, "Message Services Committee Minority Report",
    Jan. 1975

                                       -2-

    III. OVERVIEW

    This document describes a mechanism developed for use
    by message servers communicating over an eight-bit
    byte-oriented network connection to move data structures and
    associated data-typing information.  It is presented here in
    the hope that it may be of use to other projects which need
    to transfer data structures between dissimilar hosts.

    A set of abstract entities called PRIMITIVE ITEMS is
    enumerated.  These are intended to include traditional data
    types of general utility, such as integers, strings, and
    arrays.

    A mechanism is defined for augmenting the set of
    abstract data entities handled, to allow the introduction of
    application-specific data, whose format and semantics are
    understood by the application programs involved, but which
    can be transmitted using common coding facilities.  An
    example might be a data structure called a 'file
    specification', or a 'date'.  Abstract data entities defined
    using this mechanism will be termed SEMANTIC ITEMS, since
    they are typically used to carry data having semantic
    content in the application involved.

    Semantic and primitive items are collectively referred
    to simply as ITEMS.

    The protocol next involves the definition of the format
    of the byte stream used to convey items from machine to
    machine.  These encodings are described in terms of OBJECTS,
    which are the physical byte streams transmitted.

    To complete the protocol, the rules for translating
    between objects and items are presented as each object is
    defined.

    An item is transmitted by being translated into an
    object which is transmitted over the connection as a stream
    of bytes to the receiver, and reconstructed there as an
    item.  The protocol mechanism may thus be viewed as a simple
    translator.  It enumerates a set of abstract entities, the
    items, which are known to programmers, a set of entities in
    byte-stream format, the objects, and the translation rules
    for conversion between the sets.  A site implementing the
    MSDTP would typically provide a facility to convert between
    objects and the local representation of the various items
    handled.  Applications using the MSDTP define their
    interactions using items, without regard to the actual
    formats in which such items are represented at various
    machines.  This permits programs to handle higher-level
    concepts such as a character string, without concern for its
    numerous representational formats.  Such detail is handled
    by the MSDTP.

                                    -3-

    Finally, a discussion of a general data transfer
    mechanism for communication between programs is presented,
    and the manner in which the particular byte-oriented
    protocol defined herein would be used in that environment is
    discussed.

    Terminology, as introduced, is defined and highlighted
    by capitalizing.

    IV. PRIMITIVE DATA ITEMS

    The primitive data items include a variety of
    traditional, well-understood types, such as integers and
    strings.  Primitive data items will be presented using
    mnemonic names preceded by the character pair "p-", to serve
    as a reminder that the named object is primitive.

    These items may be represented in various computer
    systems in whatever fashion their programmers desire.

    IV.1 -- Set Of Primitive Items

    The set of primitive items defined includes p-INT,
    p-STRING, p-STRUC, p-BITS, p-CHAR, p-BOOL, p-EMPTY, and
    p-XTRA.

    Since the protocol was developed primarily for use in
    message services, items such as p-FLOAT are not included
    since they were unnecessary.  Additional items may be easily
    added as necessary.

    A p-INT performs the traditional role of representing
    integer numbers.  A p-BITS (BIT Stream) item represents a
    bit stream.  The two possible p-BOOL (BOOLean) items are
    used to represent the logical values of *TRUE* and *FALSE*.
    The single p-EMPTY item is used to, for example, indicate
    that a given field of a message is empty.  It is provided to
    act as a place-holder, representing 'no data', and appears
    as *EMPTY*.

    The p-STRUC (STRUCture) item is used to group together
    a collection of items as a single value, maintaining the
    ordering of the elements, such as a p-STRUC of p-INTs.

    A p-CHAR is a single character.  The most common
    occurrence of character data, however, will be as p-STRINGs.
    A p-STRING should be considered to be a synonym for a
    p-STRUC containing only p-CHARs.  This concept is important
    for generality and consistency, especially when considering
    definitions of permissible operations on structures, such as
    extracting subsequences of elements, etc.

                                       -4-

    Four p-XTRA items, which can be transmitted in a single
    byte, are made available for higher level protocols to use
    when a frequently used datum is handled which can be
    represented just by its name.  An example would be an
    acknowledgment between two servers.  Using p-XTRAs to
    represent such data permits them to be handled in a single
    byte.  There are four possible p-XTRA items, termed *XTRA0*,
    *XTRA1*, *XTRA2*, and *XTRA3*.  These may be assigned
    meanings by user protocols as desired.

    IV.2 -- Printing Conventions

    The following printing conventions are introduced to
    facilitate discussion of the primitive items.

    When a specific instance of a primitive data item is
    presented, it will be shown in a traditional representation
    for that kind of data.  For example, p-INTs are shown as
    sequences of digits, e.g. 100, p-STRINGs, as sequences of
    characters enclosed in double-quote characters, for example
    "ABCDEF".

    As shown above, the two possible p-BOOL items are shown
    as *TRUE* or *FALSE*.  The object p-EMPTY appears as
    *EMPTY*.  A bit stream, i.e. p-BITS, appears as a stream of
    1s and 0s enclosed in asterisks, for example *100101001*.  A
    p-CHAR will be presented as the character enclosed in single
    quote characters, e.g., 'A'.

    P-STRUCs are printed as the representations of their
    elements, enclosed in parentheses, for example (1 2 3 4) or
    ("XYZ" "ABC" 1 2) or ((1 2 3) "A" "B"). Note that because
    p-STRINGs are simply a class of p-STRUCs assigned a special
    name and printing format for brevity and convenience, the
    items "ABC" and ('A' 'B' 'C') are identical, and the latter
    format should not be used.

    To present a generic p-STRUC, as in specifying formats
    of the contents of something, the items are presented as a
    mnemonic name, optionally followed by a colon and the
    permissible types of values for that datum.  When one of
    several items may appear as the value for some component,
    the permissible ones appear separated by vertical-bar
    characters.  For example, p-INT|p-STRING represents a single
    item, which may be either a p-INT or a p-STRING.

    To represent a succession of items, the Kleene star
    convention is used.  The specification p-INT[*] represents
    any number of p-INTs.  Similarly, p-INT[3,5] represents from
    3 to 5 p-INTs, while p-INT[*,5] specifies up to 5 and
    p-iNT[5,*] specifies at least 5 p-INTs.

                                       -5-

    For example, a p-STRUC which is used to carry names and
    numbers might be specified as follows.

    (name:p-STRING number:p-INT)

    In discussing items in general, when a specific data
    value is not intended, the name and types representation may
    be used, e.g., offset:p-INT to discuss an 'offset' which has
    a numeric value.

    V. SEMANTIC ITEM MECHANISM

    The semantic item mechanism provides a means for
    program designers to use a variety of application-specific
    data items.

    This mechanism is implemented using a special tagged
    structure to carry the data type information as well as the
    actual components of the particular semantic item.  For
    discussion purposes.  Such a special p-STRUC will be termed a
    p-EDT (Extended Data Type).

    When p-EDTs are transferred, their identity as a p-EDT
    is maintained.  So that an applications program receives the
    corresponding semantic item instead of a simple p-STRUC.  A
    p-EDT is identical to a p-STRUC in all other respects.

    V.1 -- Format of p-EDTs

    A prototypical p-EDT follows.  It is printed as if it
    were a normal p-STRUC.  Since p-EDTs are converted to
    semantic items for presentation to the user, a p-EDT will
    never be used except in this protocol definition.

    (type:p-INT|p-STRING version:p-INT com1:any
    com2:any ...)

    The first element, the 'type' is generally a p-INT, and
    is used to identify the particular type of semantic item.
    Types are assigned numeric codes in a controlled fashion.
    The type may alternatively be specified by a p-STRING, to
    permit development of new data types for possible later
    assignment of codes.  Each type has an equivalent p-STRING
    name.  These may be used interchangeably as 'type' elements,
    primarily to maintain upward compatibility.

    The second element of a p-EDT is always an p-INT, the
    'version', and specifies the exact format of the particular
    datum.  A semantic item may undergo several revisions of its
    internal structure.  Which would be evident through assigning
    different versions to each revision.

                                       -6-

    Successive components.  The 'com' elements, if any.
    carry the actual data of the semantic item.  As each
    semantic item is defined, conventions on permissible values
    and interpretation of these components are presented.  Such
    definitions may use any types of items to specify the format
    of the semantic item.  Use of lower level concepts, such as
    objects, in these definitions is prohibited.

    Semantic items will be printed as the mnemonic for the
    type involved, preceded by the character pair "s-", to
    signify that the data item is handled by this mechanism.

    V.2 -- Printing Conventions

    A semantic item is represented as if it were a p-STRUC
    containing only the components, if any, but preceded by the
    semantic type name and a # character.  The version number is
    assumed to be 1 if unspecified.  For later versions, the
    version number is attached to the type name, as in, for
    example, FILE-2 to represent version 2 of the FILE data
    type.

    For example, a semantic item called a 'file
    specification' might be defined, containing two components,
    a host number and pathname.  A specific instance of such an
    item might appear as #FILE(69 "DIRECTORY.NAME-OF-FILE"),
    while a generic s-FILE might be presented as the following.

    #FILE(host:p-INT|p-STRING pathname:p-STRING)

    the item, which may be either a p-INT or p-STRING, and
    'pathname' is the second component, which must be a
    p-STRING.  The full definition would present interpretation
    rules for these components.

    VI.  ENCODING OBJECTS

    This section presents the set of objects which are used
    to represent items as byte streams for inter-server
    transmission.  Objects will be presented using mnemonic
    type-names preceded by the character pair "b-", indicating
    their existence only as byte streams.

    All servers are required to be capable of decoding the
    entire set of objects.  Servers are not required to transmit
    certain objects which are available to improve channel
    efficiency.

                                   -7-

    The encodings are designed to facilitate programming
    and efficiency of the receiving decoder.  In all cases, the
    type and length in bytes of objects is supplied as the first
    information sent.  This characteristic is important for ease
    of implementation.  The type information permits a decoder to
    be constructed in a modular fashion.  The most important
    advantage of including size information is that the receiver
    always knows how many bytes it must read to discover what to
    do next, and knows when each object terminates.  This
    requirement avoids many potential problems with timing and
    synchronization of processes.

    Two varieties of objects are defined.  The first will
    be called ATOMIC, and includes objects used to efficiently
    encode the most common data.  The second variety is termed
    NON-ATOMIC, and is used to encode larger or less common
    items.

    In all cases, a data object begins with a single byte,
    which will be termed the TYPE-BYTE, a field of which
    contains the type code of the object.  The following bytes,
    if any, are interpreted according to the type involved.

    VI.1 -- Presentation Conventations

    In discussing formats of bytes, the following
    conventions will be employed.  The individual bits of a byte
    will be referenced by using capital letters from A to H,
    where A signifies the highest order bit, and H the lowest.
    The entire eight bit value, for example, could be referred
    to as ABCDEFGH.  Similarly, subfields of the byte will be
    identified by such sequences.  The CDEF field specifies the
    middle four bits of a byte.

    In referring to values of fields, binary format will be
    used, and small letters near the end of the alphabet will be
    used to identify particular bits for discussion.  For
    example, we might say that the BCD field of a byte contains
    a specifier for some type, and define its value to be
    BCD=11z.  In discussions of the specifier usage, we could
    refer to the cases where z=l and where z=0, as shorthand
    notation to identify BCD=111 and BCD=110, respectively.

    V1.2 -- Type-Byte Bit Assignment

    To assist in understanding the assignment of the
    various type-byte values, the table and graph below are
    included, showing representations of the eight bits.

                                   -8-

    OXXXXXXX -- CHAR7 (CHARacter, 7 bit)
    10XXXXXX -- SINTEGER (Small INTEGER)
    l10XXXXX -- NON-ATOM (NON-ATOMic objects)
    11100XXX -- LINTEGER (Large INTEGER)
    11101XXX -- reserved
    11110XXX -- SBITSTR (Short BIT STReam)
    111110XX -- XTRA (eXTRA single-byte objects)
    1111110X -- BOOL (BOOLean)
    11111110 -- EMPTY (EMPTY data item)
    11111111 -- PADDING (unused byte)

    In each case, the bits identified by X's are used to
    contain information specific to the type involved.  These
    are explained when each type is defined.

    An equivalent tree representation follows, for those
    who prefer it.
    start with high order bit
     |
     |
     |
     0-----0-----0-----0-----0-----0-----0-----0-----X
     |     |     |     |     |     |     |     |   PADDING
    0|    0|    0|    0|    0|    0|    0|    0|
     |     |     |     |     |     |     |     |
     X     |     X     |     X     |     X     X
    CHAR7  | NON-ATOM  |    BITS   |   BOOL   EMPTY
     (7)   |   (5)     |    (3)    |   (1)
           |        0| |           |
       SINTEGER        |          XTRA
          (6)          |           (2)
                   LINTEGER
                      (3)

            Type-Byte Bit Assignment Scheme

    This picture is interpreted by entering at the top, and
    taking the appropriate branch at each node to correspond to
    the next bit of the type-byte, as it is scanned from left to
    right.  When a type is assigned, the branch terminates with
    an "X' and the name of the type of the object, with the
    number of remaining bits in parentheses.  The individual
    object definitions specify how these bits are used for that
    particular type.

    V1.3 -- Atomic Objects

    Atomic objects are identified by specific patterns in a
    type-byte.  Receiving servers must be capable of recognizing

                                   -9-

    and handling all atomic types, since the size of the object
    is not explicitly present in a uniform fashion.

    ================================
    | Atomic Object: B-CHAR7       |
    ================================

    The b-CHAR7 (CHARacter 7 bit) object is introduced to
    handle transmission of characters, in 7-bit ASCII format.
    Since the vast majority of message-related data involves
    such objects, they are designed to be very efficient in
    transmission.  Other formats, such as eight bit values, can
    be introduced as non-atomic objects.  The format of a b-CHAR7
    follows:

    A=0 identifying the b-CHAR7 data type
    BCDEFGH=tuvwxyz containing the character
    code

    The tuvwxyz objects contain the ASCII code of the
    character.  For example, transmission of a "space' (ASCII
    code 32, 40 octal) would be accomplished by the following
    byte.

    00100000
    ABCDEFGH

    A=0 to identify this byte as a b-CHAR7.  The remaining
    bits contain the 7 bit code, octal 40, for space.

    A b-CHAR7 standing alone is presented as a p-CHAR.
    Such occurrences will probably be rare if they are used at
    all.  The most common use of b-CHAR7's is as elements of
    b-USTRUCs used to transmit p-STRINGS, as explained later.

    =============================
    | Atomic Object: B-SINTEGER |
    =============================

    The b-SINTEGER (Small INTEGER) object is used to
    transmit very small positive integers, of values up to 64.
    It always translates to an p-INT, and any p-INT between 0
    and 63 may be encoded as a b-SINTEGER for transmission.  The
    format of an b-SINTEGER follows.

    AB=10 identifying the object as a b-SINTEGER
    CDEFGH=uvwxyz containing the actual number

    For example, to transmit the integer 10 (12 octal), the
    following byte would be transmitted:

    10001010
    ABCDEFGH

                                   -10-

    AB=10 to specify a b-SINTEGER.  The remaining six bits
    contain the number 10 expressed in binary.

    =============================
    | Atomic Object: B-SINTEGER |
    =============================

    The b-SINTEGER (Large INTEGER) object is used to
    transmit p-INTs to any precision up to 64 bits.  It is
    always translated as a p-INT.  Sending servers are permitted
    to choose either b-SINTEGER or b-SINTEGER format for
    transmission of numbers, as appropriate.  When possible,
    b-SINTEGERs can be used for better channel efficiency.  The
    format of a b-SINTEGER follows:

    ABCDE=11100 specifying that this is a b-SINTEGER.
    FGH=xyz containing a count of number of bytes to follow.

    The xyz bits are interpreted as a number of bytes to
    follow which contain the actual binary code of the the
    integer in 2's complement format.  Since a zero-byte integer
    is disallowed, the pattern xyz=000 is interpreted as 1000,
    specifying that 8 bytes follow.  The number is transmitted
    with high-order bits first.  This format permits
    transmission of integers as large as 64 bits in magnitude.

    For example, if the number 4096 (10000 octal) is to be
    transmitted, the following sequence of bytes would be sent:

    11100010 00010000 00000000
    ABCDEFGH ---actual data---

    ABCDE=11100, identifying this as a b-LINTEGER, E=0,
    specifying a positive number, and FGH=010, specifying that 2
    bytes follow, containing the actual binary number.

    ============================
    | Atomic Object: B-SBITSTR |
    ============================

    The b-SBITSTR (Short BIT STReam) object is used to
    transmit a p-BITS of length 63 or less.  For longer bit
    streams, the non-atomic object b-LBITSTR may be used.  The
    format of a b-SBITSTR follows.

    ABCDE=11110 specifying the type as b-SBITSTR
    FGH=xyz specifying the number of bytes
    following.

                                   -11-

    The xyz value specifies the number of additional bytes
    to be read to obtain the bit stream values.  As in the case
    of b-SINTEGER, the value xyz=000 is interpreted as 1000,
    specifying that 8 bytes follow.

    To avoid requiring specification of exactly the number
    of bits contained, the following convention is used.  The
    first data byte is scanned from left to right until the
    first 1 bit is encountered.  The bit stream is defined to
    begin with the immediately following bit, and run through
    the last bit of the last byte read.  In other words, the bit
    stream is 'right-adjusted' in the collected bytes, with its
    left end delimited by the first "on' bit.

    For example, to send the bit stream *001010011* (9
    bits), the following bytes are transmitted.

    11110010 00000010 01010011
    ABCDEhij klmnopqr stuvwxyz

    The hij=010 value specifies that two bytes follow.  The
    q bit, which is the first 1 bit encountered, identifies the
    start of the bit stream as being the r bit.  The rstuvwxyz
    bits are the bit stream being handled.

    =========================
    | Atomic Object: b-BOOL |
    =========================

    The b-BOOL (BOOLean) object is used to transmit
    p-BOOLs.  The format of b-BOOL objects follows.

    ABCDEFG=1111110 specifying the type as
    b-BOOL
    H=z specifying the value

    The two possible translations of a b-BOOL are *FALSE*
    and *TRUE*.

    11111100 represents *FALSE*
    11111101 represents *TRUE*
    ABCDEFGz

    if z=0, the value is FALSE, otherwise TRUE.

    ========================================
    | Atomic Object: B-EMPTY |
    ========================================

    The b-EMPTY object type is used to transmit a 'null'
    object, i.e. an *EMPTY*.  The format of an b-EMPTY follows.

    ABCDEFGH=11111110 specifying *EMPTY*

                                    -12-

    =========================
    | Atomic Object: B-XTRA |
    =========================

    The b-XTRA objects are used to carry the four possible
    p-XTRA items, i.e., *XTRA0*, *XTRA1*, *XTRA2*, and *XTRA3*.
    These four items correspond to the binary coding of the
    remaining two bits after the b-XTRA type code bits.  The
    format of a b-XTRA follows.

    ABCDEF=111110 to specify the type b-XTRA
    GH=yz to identify the particular p-XTRA item
    carried

    The GH bits of the byte are decoded to produce a
    particular p-XTRA item, as follows.

    GH=00 -- *XTRA0*
    GH=01 -- *XTRA1*
    GH=10 -- *XTRA2*
    GH=11 -- *XTRA3*

    The b-XTRA object is included to provide the use of
    several single-byte data items to higher levels.  These
    items may be assigned by individual applications to improve
    the efficiency of transmission of several very frequent data
    items.  For example, the message services protocols will use
    these items to convey positive and negative acknowledgments,
    two very common items in every interaction.

    ========================================
    | Atomic Object: B-PADDING
    ========================================

    This object is anomalous, since it represents really no
    data at all.  Whenever it is encountered in a byte stream in
    a position where a type-byte is expected, it is completely
    ignored, and the succeeding byte examined instead.  Its
    purpose is to serve as a filler in byte streams, providing
    servers with an aid in handling internal problems related to
    their specific word lengths, etc.  The encoders may freely
    use this object to serve as padding when necessary.

    All b-PADDING data objects exist only within an encoded
    byte stream.  They never cause any data item whatsoever to
    be presented externally to the coder module.  The format of a
    b-PADDING follows.

    ABCDEFGH=11111111

    Note that this does not imply that all such 'null'
    bytes in a stream are to be ignored, since they could be
    encountered as a byte within some other type, such as
    b-LINTEGER.  Only bytes of this format which, by their
    position in the stream, appear as a 'type' byte are to be
    ignored.

                                    -13-

    VI.4 -- Non-Atomic Objects

    Non-atomic objects are are always transmitted preceded
    by both a single type byte and some small number of size
    byte(s).  The type byte identifies that the data object
    concerned is of a non-atomic type, as well as uniquely
    specifying the particular type involved.  All non-atomic
    objects have type byte values of the following form.

    ABC=110 specifying that the object is
    non-atomic
    DEFGH=vwxyz specifying the particular type
    of object

    The vwxyz value is used to specify one of 31 possible
    non-atomic types.  The value vwxyz=00000 is reserved for use
    in future expansion.

    In all non-atomic data objects, the byte(s) following
    the type-byte specify the number of bytes to follow which
    contain the data object.  In all cases, if the number of
    bytes specified are processed, the next byte to be seen
    should be another type-byte, the beginning of the next
    object in the stream.

    The number of bytes containing the object size
    information is variable.  These bytes will be termed the
    SIZE-BYTES.  The first byte encountered has the following
    format.

    A=s specifying the manner in which the size
    information is encoded
    BCDEFGH=tuvwxyz specifying the size, or
    number of bytes containing the size

    The tuvwxyz values supply a positive binary number.  If
    the s value is a one, the tuvwxyz value specifies the number
    of bytes to follow which should be read and concatenated as
    a binary number, which will then specify the size of the
    object.  These bytes will appear with high order bits first.
    Thus, if s=1, up to 128 bytes may follow, containing the
    count of the succeeding data bytes, which should certainly
    be sufficient.

    Since many non-atomic objects will be fairly short, the
    s=0 condition is used to indicate that the 7 bits contained
    in tuvwxyz specify the actual data byte count.  This permits

    objects of sizes up to 128 bytes to be specified using one
    size-information byte.  The case tuvwxyz=0000000 is
    interpreted as specifying 128 bytes.

    For example, a data object of some non-atomic type
    which requires 100 (144 octal) bytes to be transmitted would
    be sent as follows.

                                    -14-

    110XXXXX -- identifying a specific
    non-atomic object
    01100100 -- specifying that 100 bytes follow
    .
    .
    data -- the 100 data bytes
    .
    .

    Note that the size count does not include the
    size-specifier byte(s) themselves, but does include all
    succeeding bytes in the stream used to encode the object.

    A data object requiring 20000 (47040 octal) bytes would
    appear in the stream as follows.

    110XXXXX -- identifying a specific
    non-atomic object
    10000010 -- specifying that the next 2 bytes
    contain the stream length
    01001110 -- first byte of number 20000
    00100000 -- second byte
    .
    .
    data -- 20,000 bytes
    .
    .

    Interpretation of the contents of the 20000 bytes in
    the stream can be performed by a module which knows the
    specific format of the non-atomic type specified by DEFGH in
    the type-byte.

    The remainder of this section defines an initial set of
    non-atomic types, the format of their encoding, and the
    semantics of their interpretation.

    ================================
    | Non-atomic Object: B-LBITSTR |
    ================================

    The b-LBITSTR (Long BIT Stream) data type is introduced
    to transmit p-BITS which cannot be handled by a b-SBITSTR.
    A b-LBITSTR may be used to transmit short p-BITS as well.
    Its format follows.

                                    -15-

    11000001 size-bytes data-bytes
    ABCDEFGH

    ABC=110 identifies this as a non-atomic object.
    DEFGH=00001 specifies that it is a b-LBITSTR.  The standard
    sizing information specifies the number of succeeding bytes.
    Within the data-bytes, the first object encountered must
    decode to a p-INT.  This number conveys the length of the
    bit stream to follow.  The actual bit stream begins with the
    next byte, and is left-adjusted in the byte stream.  For
    example to encode *101010101010*, the following b-LBITSTR
    could be used, although a b-SBITSTR would be more compact.

    11000001 -- identifies a b-LBITSTR
    00000010 -- b-SINTEGER, to specify length
    10001100 -- size = 2
    10101010 -- first 8 data bits
    10100000 -- last 4 data bits

    ==============================
    | Non-atomic Object: B-STRUC |
    ==============================

    The b-STRUC (STRUCture) data type is used to transmit
    any p-STRUC.  The translation rules for converting a b-STRUC
    into a primitive item are presented following the discussion
    of b-REPEATs.  The b-STRUC format appears as follows.

    11000010 size-bytes data-bytes
    ABCDEFGH

    ABC=110 identifies this as a non-atomic type.
    DEFGH=00010 specifies that the object is a b-STRUC.  Within
    the data-bytes stream, objects simply follow in order.  This
    implies that the b-STRUC encoder and decoder modules can
    simply make use of recursive calls to a standard
    encoder/decoder for processing each element of the b-STRUC.

    Note that any type of object is permitted as an element of a
    b-STRUC, but the size information of the b-STRUC must
    include all bytes used to represent the elements.

    Containment of b-STRUCs within other b-STRUCs is
    permitted to any reasonable level.  That is, a b-STRUC may
    contain as an element another b-STRUC, which contains
    another b-STRUC, and so on.  All servers are requires to
    handle such containment to at least a minimum depth of
    three.

    Examples of encoded structures appear in a later
    section.

                                    -16-

    ============================
    | Non-atomic Object: B-EDT |
    ============================

    A b-EDT is the object used as the carrier for p-EDTs in
    transmission of semantic items.  It is functionally
    identical to a b-STRUC, but has a different type code to
    permit it to be identified and converted to a semantic item
    instead of a p-STRUC.  The format of a b-EDT follows.

    11000011 size-bytes data-bytes
    ABCDEFGH

    As with all non-atomic types, ABC=110 to identify this
    as such, and DEFGH=00011 to specify a b-EDT.  The objects in
    the data-bytes are decoded as for b-STRUCs.  However, the
    first object must decode to a p-iNT or p-STRING and the
    second to a p-INT, to conform to the format of p-EDTs.

    ===============================
    | Non-atomic Object: b-REPEAT |
    ===============================

    The b-REPEAT object is never translated directly into
    an item.  It is legal only as an component of an enclosing
    b-STRUC, b-USTRUC, b-EDT, or b-REPEAT.  A b-REPEAT is used to
    concisely specify a set of elements to be treated as if they
    appeared in the enclosing structure in place of the
    b-REPEAT.  This provides a mechanism for encoding a sequence
    of identical data items or patterns efficiently for
    transmission.

    A common example of this would be in transmission of
    text, where line images containing long sequences of spaces,
    or pages containing multiple carriage-return, line-feed
    pairs, are often encountered.  Such sequences could be
    encoded as an appropriate b-REPEAT to compact the data for
    transmission.  The format of a b-REPEAT is as follows.

    11000100   -- identifyIng the object as a
                    b-REPEAT
    size-bytes -- the standard non-atomic object
                    size information
    countspec  -- an object which translates to a p-INT
    .
    .
    data -- the objects which define the pattern
    .
    .

    The 'countspec' object must translate to an p-INT to
    specify the number of times that the following data pattern
    should be repeated in the object enclosing the b-REPEAT.

                                    -17-

    The remaining objects in the b-REPEAT constitute the
    data pattern which is to be repeated.  The decoding of the
    enclosing structure will be continued as if the data pattern
    objects appeared 'countspec' times in place of the b-REPEAT.
    Zero repeat counts are permitted, for generality.  They
    cause no objects to be simulated in the enclosing structure.

    An encoder does not have to use b-REPEATs at all, if
    simplicity of coding outweighs the benefits of data
    compression.  In message services, for example, an encoder
    might limIt itself to only compressing long text strings.  It
    is important for compatibility, however, to have the ability
    in the decoders to handle b-REPEATs.

    ===============================
    | Non-atomic Object: B-USTRUC |
    ===============================

    The b-USTRUC (Uniform Structure) object type is
    provided to enable servers to convey the fact that a p-STRUC
    being transferred contains items of only a single type.  The
    most common example would involve a b-USTRUC which
    translates to a p-STRUC of only p-CHARs, and hence may be
    considered to be a p-STRING.  Servers may use this
    information to assist them in decoding objects efficiently.
    No server is required to generate b-USTRUCs.

    The internal construction of a b-USTRUC is identical to
    that of a b-STRUC, except for the type-byte.  The format of a
    b-USTRUC follows.

    11000101 size-bytes data-bytes
    ABCDEFGH

    ABC=110 to identify a non-atomic object.  DEFGH=00101
    specifies the object as a b-USTRUC.

    ===============================
    | Non-atomic Object: B-STRING |
    ===============================

    The b-STRING object is included to permit explicit
    specification of a structure as a p-STRING.  This
    information will permit receiving servers to process the
    incoming structure more efficiently.  A b-STRING is
    formatted similarity to a b-USTRUC, except that its type-byte
    identifies the object as a b-STRI/NG.  The normal sizing
    information is followed by a stream of bytes which are
    interpreted as b-CHAR7s, Ignoring the high-order bit.  The
    format of a b-STRING follows.

    11000110 size-bytes data-bytes
    ABCDEFGH

    ABC=110 to identify a non-atomic object.  DEFGH=00110
    specifies the object as a b-STRING.

                                    -18-

    VI.5 -- Structure Translation Rules

    A b-STRUC is translated into a p-STRUC.  This is
    performed by translating each object of the b-STRUC Into its
    corresponding item, and saving it for inclusion In the
    p-STRUC being generated.  A b-USTRUC is handled similarly,
    but the coding programs may utilize the information that the
    resultant p-STRUC will contain items of uniform type.  The
    preferred method of coding p-STRINGS is to use b-USTRUCs.

    If all of the elements of the resultant p-STRUC are
    p-CHARs, it is presented to the user of the decoder as a
    p-STRING.  A p-STRING should be considered to be a synonym
    for a p-STRUC containing only characters.  It need not
    necessarily exist at particular sites which would present
    p-STRUCs of p-CHARs to their application programs

    The object b-REPEAT is handled in a special fashion
    when encountered as an element.  When this occurs, the data
    pattern of the b-REPEAT is translated into a sequence of
    items, and that sequence is repeated in the next higher
    level as many times as specified in the b-REPEAT.
    Therefore, b-REPEATS are legal only as elements of a
    surrounding b-STRUC, b-USTRUC, b-EDT, or b-REPEAT.

    In encoding a p-STRUC or p-STRING for transmission, a
    translator may use b-REPEATs as desired to effect data
    compression, but their use is not mandatory.  Similarly,
    b-STRINGS may be used, but are not mandatory.

    A b-EDT is translated into a p-EDT to identify it as a
    carrier for a semantic item.  Otherwise, it is treated
    identically to a b-STRUC.

    VI.6 -- Translation Summary

    The following table summarizes the possible
    translations between primitive items and objects.

    p-INT    <--> b-LINTEGER, b-SINTEGER
    p-STRING <--> b-STRING, b-STRUC, b-USTRUC
    p-STRUC  <--> b-STRING, b-STRUC, b-USTRUC
    p-BITS   <--> b=SBITSTR, b-LBITSTR
    p-CHAR   <--> b-CHAR7
    p-BOOL   <--> b-BOOL
    p-EMPTY  <--> b=EMPTY
    p-XTRA   <--> b-XTRA
    p-EDT    <--> b-EDT (all semantic items)
    -none-   <--> b-PADDING
    -none-   <--> b-REPEAT (only within structure)

    Note that all semantic items are represented as p-EDTs
    which always exist as b-EDTs in byte-stream format.

                                    -19-

    V1.7 -- Structure Coding Examples

    The following stream transmits a b-STRUC containing 3
    b-SINTEGERs, with values 1, 2, and 3, representing a p-STRUC
    containing three p-INTs, i.e. (1 2 3).

    11000010 -- b-STRUC
    00000011 -- size=3
    10000001 -- b-SINTEGER=1
    10000010 -- b-SINTEGER=2
    10000011 -- b-SINTEGER=3

    The next example represents a b-STRUC containing the
    characters X and Y, followed by the b-LINTEGER 10,
    representing a p-STRUC of 2 p-CHARs and a p-INT, i.e., ('X'
    'Y' 10).  Note that the p-INT prevents considering this a
    p-STRING.

    11000010 -- b-STRUC
    00000100 -- size=4
    01011000 -- b-CHAR7 'X'
    01011001 -- b-CHAR7 'Y'
    11100001 -- b-LINTEGER
    00001010 -- 10

    Note that a better way to send this p-STRUC would be to
    represent the integer as a b-SINTEGER, as shown below.

    11000010 -- b-STRUC
    00000011 -- size=3
    01011000 -- b-CHAR7 'X'
    01011001 -- b-CHAR7 'Y'
    10001010 -- b-SINTEGER=10

    The next example shows a b-STRUC of b-CHAR7s.  It is
    the translation of the b-STRING "HELLO".

    11000010 -- b-STRUC
    00000101 -- size=5
    01001000 -- b-CHAR7 'H'
    01000101 -- b-CHAR7 'E'
    01001100 -- b-CHAR7 'L'
    01001100 -- b-CHAR7 'L'
    01001111 -- b-CHAR7 'O'

    This datum could also be transmitted as a b-STRING.
    Note that the character bytes are not necessarily b-CHAR7s,
    since the high-order bit is ignored.

    11000110 -- b-STRING
    00000101 -- size=5
    01001000 -- 'H'
    01000101 -- 'E'
    01001100 -- 'L'
    01001100 -- 'L'
    01001111 -- 'O'

                                    -20-

    To encode a p-STRING containing 20 carriage-return
    line-feed pairs, the following b-STRUC containing a b-REPEAT
    could be used.

    11000010 -- b-STRUC
    00000101 -- size=5
    11000100 -- b-REPEAT
    00000011 -- size=3
    10010100 -- count, b-SINTEGER=20
    00001101 -- b-CHAR7, "CR'
    00001010 -- b-CHAR7, 'IF'

    To encode a p-STRUC of p-INTs, where the sequence
    contains a sequence of thirty 0's preceded by a single 1,
    the following b-STRUC could be used.

    11000010 -- b-STRUC
    00000110 -- size=6
    10000001 -- b-SINTEGER=1
    11000100 -- b-REPEAT
    00000010 -- size=2
    10011110 -- count, b-SINTEGER=30
    10000000 -- b-SINTEGER=0

    VII. A GENERAL DATA TRANSFER SCHEME

    This section considers a possible scheme for extending
    the concept of a data translator into an multi-purpose data
    transfer mechanism.

    The proposed environment would provide a set of
    primitive items, including those enumerated herein but
    extended as necessary to accommodate a variety of
    applications.  Communication between processes would be
    defined solely in terms of these items, and would
    specifically avoid any consideration of the actual formats
    in which the data is transferred.

    A repertoire of translators would be provided, one of
    which is the MSDTP machinery, for use in converting items to
    any of a number of transmission formats.  Borrowing a
    concept from radio terminology, each translator would be
    analogous to a different type of modulation scheme, to be
    used to transfer data through some communications medium.
    Such media could be an eight-bit byte-oriented connection,
    36-bit connection, etc.  and conceivably have other
    distinguishing features, such as bandwidth, cost, and delay.
    For each media which a site supports, it would provide its
    programmers with a module for performing the translations
    required.

                                    -21-

    Certain media or translators might not handle various
    items.  For example, the MSDTP does not handle items which
    might be termed p-FLOATs, p-COMPLEXs, p-ARRAY, and so on.  In
    addition, the efficiency of various media for transfer of
    specific items may differ drastically.  MSDTP, for example,
    transfers data frequently used in message handling very
    efficiently, but is relatively poor at transfer of very
    large or deep tree structures.

    Available at each site as a process or subroutine
    package wouLd be a module responsible for interfacing with
    its counterpart at the other end of the media.  These
    modules would use a protocol, not yet defined, to match
    their capabilities, and choose a particular media and
    translator, when more than one exists, for transfer of data
    items.

    Such a facility could totally insulate applications
    from need to consider encoding formats, machine differences,
    and so on, as well as eliminate duplication of effort in
    producing such facilities for every new project which
    requires them.  In addition, as new translators or media are
    introduced, they would become immediately available to
    existing users without reprogramming.

    Implementation of such a protocol should not be very
    difficult or time-consuming, since it need not be very
    sophisticated in choosing the most appropriate transfer
    mechanism in initial implementations.  The system is
    inherently upward-compatible and easily expandable.

                                    -22-