home *** CD-ROM | disk | FTP | other *** search
/ Internet Core Protocols / Oreilly-InternetCoreProtocols.iso / RFCs / rfc1978.txt < prev    next >
Encoding:
Text File  |  1999-10-14  |  17.5 KB  |  508 lines
  1.  
  2.  
  3.  
  4.  
  5.  
  6.  
  7. Network Working Group                                            D. Rand
  8. Request for Comments: 1978                                        Novell
  9. Category: Informational                                      August 1996
  10.  
  11.  
  12.                    PPP Predictor Compression Protocol
  13.  
  14. Status of This Memo
  15.  
  16.    This memo provides information for the Internet community.  This memo
  17.    does not specify an Internet standard of any kind.  Distribution of
  18.    this memo is unlimited.
  19.  
  20. Abstract
  21.  
  22.    The Point-to-Point Protocol (PPP) [1] provides a standard method of
  23.    encapsulating multiple protocol datagrams over point-to-point links.
  24.  
  25.    The PPP Compression Control Protocol [2] provides a method for
  26.    transporting multi-protocol datagrams over PPP encapsulated links.
  27.  
  28.    This document describes the use of the Predictor data compression
  29.    algorithm for compressing PPP encapsulated packets.
  30.  
  31. Table of Contents
  32.  
  33.      1.     Introduction ......................................    1
  34.      2.     Licensing .........................................    2
  35.      3.     Predictor Packets .................................    2
  36.         3.1       Predictor theory ............................    2
  37.         3.2       Encapsulation for Predictor type 1 ..........    7
  38.         3.3       Encapsulation for Predictor type 2 ..........    8
  39.      4.     Configuration Option Format .......................    9
  40.      SECURITY CONSIDERATIONS ..................................    9
  41.      REFERENCES ...............................................    9
  42.      ACKNOWLEDGEMENTS .........................................    9
  43.      CHAIR'S ADDRESS ..........................................    9
  44.      AUTHOR'S ADDRESS .........................................    9
  45.  
  46. 1.  Introduction
  47.  
  48.    Predictor is a high speed compression algorithm, available without
  49.    license fees.  The compression ratio obtained using predictor is not
  50.    as good as other compression algorithms, but it remains one of the
  51.    fastest algorithms available.
  52.  
  53.    Note that although care has been taken to ensure that the following
  54.    code does not infringe any patents, there is no assurance that it is
  55.  
  56.  
  57.  
  58. Rand                         Informational                      [Page 1]
  59.  
  60. RFC 1978                   Predictor Protocol                August 1996
  61.  
  62.  
  63.    not covered by a patent.
  64.  
  65. 2.  Licensing
  66.  
  67.    There are no license fees or costs associated with using the
  68.    Predictor algorithm.
  69.  
  70.    Use the following code at your own risk.
  71.  
  72. 3.  Predictor Packets
  73.  
  74.    Before any Predictor packets may be communicated, PPP must reach the
  75.    Network-Layer Protocol phase, and the Compression Control Protocol
  76.    must reach the Opened state.
  77.  
  78.    Exactly one Predictor datagram is encapsulated in the PPP Information
  79.    field, where the PPP Protocol field indicates type hex 00FD
  80.    (compressed datagram).
  81.  
  82.    The maximum length of the Predictor datagram transmitted over a PPP
  83.    link is the same as the maximum length of the Information field of a
  84.    PPP encapsulated packet.
  85.  
  86.    Prior to compression, the uncompressed data begins with the PPP
  87.    Protocol number.  This value MAY be compressed when Protocol-Field-
  88.    Compression is negotiated.
  89.  
  90.    PPP Link Control Protocol packets MUST NOT be send within compressed
  91.    data.
  92.  
  93. 3.1.  Predictor theory
  94.  
  95.    Predictor works by filling a guess table with values, based on the
  96.    hash of the previous characters seen. Since we are either emitting
  97.    the source data, or depending on the guess table, we add a flag bit
  98.    for every byte of input, telling the decompressor if it should
  99.    retrieve the byte from the compressed data stream, or the guess
  100.    table. Blocking the input into groups of 8 characters means that we
  101.    don't have to bit-insert the compressed output - a flag byte preceeds
  102.    every 8 bytes of compressed data. Each bit of the flag byte
  103.    corresponds to one byte of reconstructed data.
  104.  
  105. Take the source file:
  106.  
  107. 000000    4141 4141 4141 410a  4141 4141 4141 410a    AAAAAAA.AAAAAAA.
  108. 000010    4141 4141 4141 410a  4141 4141 4141 410a    AAAAAAA.AAAAAAA.
  109. 000020    4142 4142 4142 410a  4241 4241 4241 420a    ABABABA.BABABAB.
  110. 000030    7878 7878 7878 780a                         xxxxxxx.
  111.  
  112.  
  113.  
  114. Rand                         Informational                      [Page 2]
  115.  
  116. RFC 1978                   Predictor Protocol                August 1996
  117.  
  118.  
  119. Compressing the above data yields the following:
  120.  
  121. 000000    6041 4141 4141 0a60  4141 4141 410a 6f41    `AAAAA.`AAAAA.oA
  122. 000010    0a6f 410a 4142 4142  4142 0a60 4241 4241    .oA.ABABAB.`BABA
  123. 000020    420a 6078 7878 7878  0a                     B.`xxxxx.
  124.  
  125. Reading the above data says:
  126.  
  127. flag = 0x60 - 2 bytes in this block were guessed correctly, 5 and 6.
  128.      Reconstructed data is:    0 1 2 3 4 5 6 7
  129.         File:                  A A A A A
  130.         Guess table:                     A A
  131. flag = 0x60 - 2 bytes in this block were guessed correctly, 5 and 6.
  132.      Reconstructed data is:    0 1 2 3 4 5 6 7
  133.         File:                  A A A A A
  134.         Guess table:                     A A
  135. flag = 0x6f - 6 bytes in this block were guessed correctly, 0-3, 5 and 6.
  136.      Reconstructed data is:    0 1 2 3 4 5 6 7
  137.         File:                          A
  138.         Guess table:           A A A A   A A
  139. flag = 0x6f - 6 bytes in this block were guessed correctly, 0-3, 5 and 6.
  140.      Reconstructed data is:    0 1 2 3 4 5 6 7
  141.         File:                          A
  142.         Guess table:           A A A A   A A
  143. flag = 0x41 - 2 bytes in this block were guessed correctly, 0 and 6.
  144.      Reconstructed data is:    0 1 2 3 4 5 6 7
  145.         File:                    B A B A B
  146.         Guess table:           A           A
  147. flag = 0x60 - 2 bytes in this block were guessed correctly, 5 and 6.
  148.      Reconstructed data is:    0 1 2 3 4 5 6 7
  149.         File:                  B A B A B
  150.         Guess table:                     A B
  151. flag = 0x60 - 2 bytes in this block were guessed correctly, 5 and 6
  152.      Reconstructed data is:    0 1 2 3 4 5 6 7
  153.         File:                  x x x x x
  154.         Guess table:                     x x
  155.  
  156.    And now, on to the source - note that it has been modified to work
  157.    with a split block. If your data stream can't be split within a block
  158.    (e.g., compressing packets), then the code dealing with "final", and
  159.    the memcpy are not required.  You can detect this situation (or
  160.    errors, for that matter) by observing that the flag byte indicates
  161.    that more data is required from the compressed data stream, but you
  162.    are out of data (len in decompress is <= 0). It *is* ok if len == 0,
  163.    and flags indicate guess table usage.
  164.  
  165.    #include <stdio.h>
  166.    #ifdef __STDC__
  167.  
  168.  
  169.  
  170. Rand                         Informational                      [Page 3]
  171.  
  172. RFC 1978                   Predictor Protocol                August 1996
  173.  
  174.  
  175.    #include <stdlib.h>
  176.    #endif
  177.    #include <string.h>
  178.    /*
  179.     * pred.c -- Test program for Dave Rand's rendition of the
  180.     * predictor algorithm
  181.     * Updated by: iand@labtam.labtam.oz.au (Ian Donaldson)
  182.     * Updated by: Carsten Bormann <cabo@cs.tu-berlin.de>
  183.     * Original  : Dave Rand <dlr@bungi.com>/<dave_rand@novell.com>
  184.     */
  185.  
  186.    /* The following hash code is the heart of the algorithm:
  187.     * It builds a sliding hash sum of the previous 3-and-a-bit
  188.     * characters which will be used to index the guess table.
  189.     * A better hash function would result in additional compression,
  190.     * at the expense of time.
  191.     */
  192.    #define HASH(x) Hash = (Hash << 4) ^ (x)
  193.  
  194.    static unsigned short int Hash;
  195.    static unsigned char GuessTable[65536];
  196.  
  197.    static int
  198.    compress(source, dest, len)
  199.    unsigned char *source, *dest;
  200.    int len;
  201.    {
  202.        int i, bitmask;
  203.        unsigned char *flagdest, flags, *orgdest;
  204.  
  205.        orgdest = dest;
  206.        while (len) {
  207.            flagdest = dest++; flags = 0; /* All guess wrong initially */
  208.            for (bitmask=1, i=0; i < 8 && len; i++, bitmask <<= 1) {
  209.                if (GuessTable[Hash] == *source) {
  210.                    flags |= bitmask; /* Guess was right - don't output */
  211.                } else {
  212.                    GuessTable[Hash] = *source;
  213.                    *dest++ = *source; /* Guess wrong, output char */
  214.                }
  215.                HASH(*source++);len--;
  216.            }
  217.            *flagdest = flags;
  218.        }
  219.        return(dest - orgdest);
  220.    }
  221.  
  222.    static int
  223.  
  224.  
  225.  
  226. Rand                         Informational                      [Page 4]
  227.  
  228. RFC 1978                   Predictor Protocol                August 1996
  229.  
  230.  
  231.    decompress(source, dest, lenp, final)
  232.    unsigned char *source, *dest;
  233.    int *lenp, final;
  234.    {
  235.        int i, bitmask;
  236.        unsigned char flags, *orgdest;
  237.        int len = *lenp;
  238.        orgdest = dest;
  239.        while (len >= 9) {
  240.            flags = *source++;
  241.            for (i=0, bitmask = 1; i < 8; i++, bitmask <<= 1) {
  242.                if (flags & bitmask) {
  243.                    *dest = GuessTable[Hash];       /* Guess correct */
  244.                } else {
  245.                    GuessTable[Hash] = *source;     /* Guess wrong */
  246.                    *dest = *source++;          /* Read from source */
  247.                    len--;
  248.                }
  249.                HASH(*dest++);
  250.            }
  251.            len--;
  252.        }
  253.        while (final && len) {
  254.            flags = *source++;
  255.            len--;
  256.            for (i=0, bitmask = 1; i < 8; i++, bitmask <<= 1) {
  257.                if (flags & bitmask) {
  258.                    *dest = GuessTable[Hash];       /* Guess correct */
  259.                } else {
  260.                    if (!len)
  261.                        break;  /* we seem to be really done -- cabo */
  262.                    GuessTable[Hash] = *source;     /* Guess wrong */
  263.                    *dest = *source++;          /* Read from source */
  264.                    len--;
  265.                }
  266.                HASH(*dest++);
  267.            }
  268.        }
  269.        *lenp = len;
  270.        return(dest - orgdest);
  271.    }
  272.  
  273.    #define SIZ1 8192
  274.  
  275.    static void
  276.    compress_file(f) FILE *f; {
  277.        char bufp[SIZ1];
  278.        char bufc[SIZ1/8*9+9];
  279.  
  280.  
  281.  
  282. Rand                         Informational                      [Page 5]
  283.  
  284. RFC 1978                   Predictor Protocol                August 1996
  285.  
  286.  
  287.        int len1, len2;
  288.        while ((len1 = fread(bufp, 1, SIZ1, f)) > 0) {
  289.            len2 = compress((unsigned char *)bufp,
  290.            (unsigned char *)bufc, len1);
  291.            (void) fwrite(bufc, 1, len2, stdout);
  292.        }
  293.    }
  294.  
  295.    static void
  296.    decompress_file(f) FILE *f; {
  297.        char bufp[SIZ1+9];
  298.        char bufc[SIZ1*9+9];
  299.        int len1, len2, len3;
  300.  
  301.        len1 = 0;
  302.        while ((len3 = fread(bufp+len1, 1, SIZ1, f)) > 0) {
  303.            len1 += len3;
  304.            len3 = len1;
  305.            len2 = decompress((unsigned char *)bufp,
  306.            (unsigned char *)bufc, &len1, 0);
  307.            (void) fwrite(bufc, 1, len2, stdout);
  308.            (void) memcpy(bufp, bufp+len3-len1, len1);
  309.        }
  310.        len2 = decompress((unsigned char *)bufp,
  311.        (unsigned char *)bufc, &len1, 1);
  312.        (void) fwrite(bufc, 1, len2, stdout);
  313.    }
  314.  
  315.    int
  316.    main(ac, av)
  317.        int ac;
  318.        char** av;
  319.    {
  320.        char **p = av+1;
  321.        int dflag = 0;
  322.  
  323.        for (; --ac > 0; p++) {
  324.            if (!strcmp(*p, "-d"))
  325.                dflag = 1;
  326.            else if (!strcmp(*p, "-"))
  327.                (dflag?decompress_file:compress_file)(stdin);
  328.            else {
  329.                FILE *f = fopen(*p, "r");
  330.                if (!f) {
  331.                    perror(*p);
  332.                    exit(1);
  333.                }
  334.                (dflag?decompress_file:compress_file)(f);
  335.  
  336.  
  337.  
  338. Rand                         Informational                      [Page 6]
  339.  
  340. RFC 1978                   Predictor Protocol                August 1996
  341.  
  342.  
  343.                (void) fclose(f);
  344.            }
  345.        }
  346.        return(0);
  347.    }
  348.  
  349. 3.2.  Encapsulation for Predictor type 1
  350.  
  351.    The correct encapsulation for type 1 compression is the protocol
  352.    type, 1 bit indicating if the data is compressed or not, 15 bits of
  353.    the uncompressed data length in octets, compressed data, and
  354.    uncompressed CRC-16 of the two octets of unsigned length in network
  355.    byte order, followed by the original, uncompressed data packet.
  356.  
  357.     0                   1
  358.     0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5
  359.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  360.    | CCP Protocol Identifier       |
  361.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  362.    |*| Uncompressed length (octets)|   * is compressed flag
  363.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+   1 means data is compressed
  364.    | Compressed data...            |   0 means data is not compressed
  365.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  366.    | CRC - 16                      |
  367.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  368.  
  369.    The CCP Protocol Identifier that starts the packet is always 0xfd.
  370.    If PPP Protocol field compression has not be negotiated, it MUST be a
  371.    16-bit field.
  372.  
  373.    The Compressed data is the Protocol Identifier and the Info fields of
  374.    the original PPP packet described in [1], but not the Address,
  375.    Control, FCS, or Flag.  The CCP Protocol field MAY be compressed as
  376.    described in [1], regardless of whether the Protocol field of the CCP
  377.    Protocol Identifier is compressed or whether PPP Protocol field
  378.    compression has been negotiated.
  379.  
  380.    It is not required that any of the fields land on an even word
  381.    boundary - the compressed data may be of any length.  If during the
  382.    decode procedure, the CRC-16 does not match the decoded frame, it
  383.    means that the compress or decompress process has become
  384.    desyncronized.  This will happen as a result of a frame being lost in
  385.    transit if LAPB is not used.  In this case, a new configure-request
  386.    must be sent, and the CCP will drop out of the open state.  Upon
  387.    receipt of the configure-ack, the predictor tables are cleared to
  388.    zero, and compression can be resumed without data loss.
  389.  
  390.  
  391.  
  392.  
  393.  
  394. Rand                         Informational                      [Page 7]
  395.  
  396. RFC 1978                   Predictor Protocol                August 1996
  397.  
  398.  
  399. 3.3.  Encapsulation for Predictor type 2
  400.  
  401.    The correct encapsulation for type 2 compression is the protocol
  402.    type, followed by the data stream.  Within the data stream is the
  403.    current frame length (uncompressed), compressed data, and
  404.    uncompressed CRC-16 of the two octets of unsigned length in network
  405.    byte order, followed by the original, uncompressed data.  The data
  406.    stream may be broken at any convenient place for encapsulation
  407.    purposes.  With type 2 encapsulation, LAPB is almost essential for
  408.    correct delivery.
  409.  
  410.     0                   1
  411.     0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5
  412.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  413.    | CCP Protocol Identifier       |
  414.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  415.    |*| Uncompressed length (octets)|   * is compressed flag
  416.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+   1 means data is compressed
  417.    | Compressed data...            |   0 means data is not compressed
  418.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  419.    | CRC-16                        |
  420.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  421.    |*| Uncompressed length (octets)|   * is compressed flag
  422.    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  423.             ...
  424.  
  425.    The CCP Protocol Identifier that starts the packet is always 0xfd.
  426.    If PPP Protocol field compression has not be negotiated, it MUST be a
  427.    16-bit field.
  428.  
  429.    The Compressed data is the Protocol Identifier and the Info fields of
  430.    the original PPP packet described in [1], but not the Address,
  431.    Control, FCS, or Flag.  The CCP Protocol field MAY be compressed as
  432.    described in [1], regardless of whether the Protocol field of the CCP
  433.    Protocol Identifier is compressed or whether PPP Protocol field
  434.    compression
  435.  
  436.    It is not required that any field land on an even word boundary - the
  437.    compressed data may be of any length.  If during the decode
  438.    procedure, the CRC-16 does not match the decoded frame, it means that
  439.    the compress or decompress process has become desyncronized.  This
  440.    will happen as a result of a frame being lost in transit if LAPB is
  441.    not used.  In this case, a new configure-request must be sent, and
  442.    the CCP will drop out of the open state.  Upon receipt of the
  443.    configure-ack, the predictor tables are cleared to zero, and
  444.    compression can be resumed without data loss.
  445.  
  446.  
  447.  
  448.  
  449.  
  450. Rand                         Informational                      [Page 8]
  451.  
  452. RFC 1978                   Predictor Protocol                August 1996
  453.  
  454.  
  455. 4.  Configuration Option Format
  456.  
  457.    There are no options for Predictor type one or two.
  458.  
  459. Security Considerations
  460.  
  461.    Security issues are not discussed in this memo.
  462.  
  463. References
  464.  
  465.       [1]   Simpson, W., "The Point-to-Point Protocol", STD 51, RFC
  466.             1661, July 1994.
  467.  
  468.       [2]   Rand, D., "The PPP Compression Control Protocol (CCP)",
  469.             RFC 1962, June 1996.
  470.  
  471.       [3]   Rand, D., "PPP Reliable Transmission", RFC 1663,
  472.             July 1994.
  473.  
  474. Acknowledgments
  475.  
  476.    The predictor algorithm was originally implemented by Timo Raita, at
  477.    the ACM SIG Conference, New Orleans, 1987.
  478.  
  479.    Bill Simpson helped with the document formatting.
  480.  
  481. Chair's Address
  482.  
  483.    The working group can be contacted via the current chair:
  484.  
  485.    Karl Fox
  486.    Ascend Communications
  487.    3518 Riverside Drive, Suite 101
  488.    Columbus, Ohio 43221
  489.  
  490.    EMail: karl@ascend.com
  491.  
  492. Author's Address
  493.  
  494.    Questions about this memo can also be directed to:
  495.  
  496.    Dave Rand
  497.    Novell, Inc.
  498.    2180 Fortune Drive
  499.    San Jose, CA  95131
  500.  
  501.    +1 408 321-1259
  502.    EMail: dave_rand@novell.com
  503.  
  504.  
  505.  
  506. Rand                         Informational                      [Page 9]
  507.  
  508.