rfc1978.txt

来自「RFC 的详细文档！」· 文本 代码 · 共 508 行 · 第 1/2 页

Network Working Group                                            D. Rand
Request for Comments: 1978                                        Novell
Category: Informational                                      August 1996


                   PPP Predictor Compression Protocol

Status of This Memo

   This memo provides information for the Internet community.  This memo
   does not specify an Internet standard of any kind.  Distribution of
   this memo is unlimited.

Abstract

   The Point-to-Point Protocol (PPP) [1] provides a standard method of
   encapsulating multiple protocol datagrams over point-to-point links.

   The PPP Compression Control Protocol [2] provides a method for
   transporting multi-protocol datagrams over PPP encapsulated links.

   This document describes the use of the Predictor data compression
   algorithm for compressing PPP encapsulated packets.

Table of Contents

     1.     Introduction ......................................    1
     2.     Licensing .........................................    2
     3.     Predictor Packets .................................    2
        3.1       Predictor theory ............................    2
        3.2       Encapsulation for Predictor type 1 ..........    7
        3.3       Encapsulation for Predictor type 2 ..........    8
     4.     Configuration Option Format .......................    9
     SECURITY CONSIDERATIONS ..................................    9
     REFERENCES ...............................................    9
     ACKNOWLEDGEMENTS .........................................    9
     CHAIR'S ADDRESS ..........................................    9
     AUTHOR'S ADDRESS .........................................    9

1.  Introduction

   Predictor is a high speed compression algorithm, available without
   license fees.  The compression ratio obtained using predictor is not
   as good as other compression algorithms, but it remains one of the
   fastest algorithms available.

   Note that although care has been taken to ensure that the following
   code does not infringe any patents, there is no assurance that it is



Rand                         Informational                      [Page 1]

RFC 1978                   Predictor Protocol                August 1996


   not covered by a patent.

2.  Licensing

   There are no license fees or costs associated with using the
   Predictor algorithm.

   Use the following code at your own risk.

3.  Predictor Packets

   Before any Predictor packets may be communicated, PPP must reach the
   Network-Layer Protocol phase, and the Compression Control Protocol
   must reach the Opened state.

   Exactly one Predictor datagram is encapsulated in the PPP Information
   field, where the PPP Protocol field indicates type hex 00FD
   (compressed datagram).

   The maximum length of the Predictor datagram transmitted over a PPP
   link is the same as the maximum length of the Information field of a
   PPP encapsulated packet.

   Prior to compression, the uncompressed data begins with the PPP
   Protocol number.  This value MAY be compressed when Protocol-Field-
   Compression is negotiated.

   PPP Link Control Protocol packets MUST NOT be send within compressed
   data.

3.1.  Predictor theory

   Predictor works by filling a guess table with values, based on the
   hash of the previous characters seen. Since we are either emitting
   the source data, or depending on the guess table, we add a flag bit
   for every byte of input, telling the decompressor if it should
   retrieve the byte from the compressed data stream, or the guess
   table. Blocking the input into groups of 8 characters means that we
   don't have to bit-insert the compressed output - a flag byte preceeds
   every 8 bytes of compressed data. Each bit of the flag byte
   corresponds to one byte of reconstructed data.

Take the source file:

000000    4141 4141 4141 410a  4141 4141 4141 410a    AAAAAAA.AAAAAAA.
000010    4141 4141 4141 410a  4141 4141 4141 410a    AAAAAAA.AAAAAAA.
000020    4142 4142 4142 410a  4241 4241 4241 420a    ABABABA.BABABAB.
000030    7878 7878 7878 780a                         xxxxxxx.



Rand                         Informational                      [Page 2]

RFC 1978                   Predictor Protocol                August 1996


Compressing the above data yields the following:

000000    6041 4141 4141 0a60  4141 4141 410a 6f41    `AAAAA.`AAAAA.oA
000010    0a6f 410a 4142 4142  4142 0a60 4241 4241    .oA.ABABAB.`BABA
000020    420a 6078 7878 7878  0a                     B.`xxxxx.

Reading the above data says:

flag = 0x60 - 2 bytes in this block were guessed correctly, 5 and 6.
     Reconstructed data is:    0 1 2 3 4 5 6 7
        File:                  A A A A A
        Guess table:                     A A
flag = 0x60 - 2 bytes in this block were guessed correctly, 5 and 6.
     Reconstructed data is:    0 1 2 3 4 5 6 7
        File:                  A A A A A
        Guess table:                     A A
flag = 0x6f - 6 bytes in this block were guessed correctly, 0-3, 5 and 6.
     Reconstructed data is:    0 1 2 3 4 5 6 7
        File:                          A
        Guess table:           A A A A   A A
flag = 0x6f - 6 bytes in this block were guessed correctly, 0-3, 5 and 6.
     Reconstructed data is:    0 1 2 3 4 5 6 7
        File:                          A
        Guess table:           A A A A   A A
flag = 0x41 - 2 bytes in this block were guessed correctly, 0 and 6.
     Reconstructed data is:    0 1 2 3 4 5 6 7
        File:                    B A B A B
        Guess table:           A           A
flag = 0x60 - 2 bytes in this block were guessed correctly, 5 and 6.
     Reconstructed data is:    0 1 2 3 4 5 6 7
        File:                  B A B A B
        Guess table:                     A B
flag = 0x60 - 2 bytes in this block were guessed correctly, 5 and 6
     Reconstructed data is:    0 1 2 3 4 5 6 7
        File:                  x x x x x
        Guess table:                     x x

   And now, on to the source - note that it has been modified to work
   with a split block. If your data stream can't be split within a block
   (e.g., compressing packets), then the code dealing with "final", and
   the memcpy are not required.  You can detect this situation (or
   errors, for that matter) by observing that the flag byte indicates
   that more data is required from the compressed data stream, but you
   are out of data (len in decompress is <= 0). It *is* ok if len == 0,
   and flags indicate guess table usage.

   #include <stdio.h>
   #ifdef __STDC__



Rand                         Informational                      [Page 3]

RFC 1978                   Predictor Protocol                August 1996


   #include <stdlib.h>
   #endif
   #include <string.h>
   /*
    * pred.c -- Test program for Dave Rand's rendition of the
    * predictor algorithm
    * Updated by: [e-mail] (Ian Donaldson)
    * Updated by: Carsten Bormann <[e-mail]>
    * Original  : Dave Rand <[e-mail]>/<[e-mail]>
    */

   /* The following hash code is the heart of the algorithm:
    * It builds a sliding hash sum of the previous 3-and-a-bit
    * characters which will be used to index the guess table.
    * A better hash function would result in additional compression,
    * at the expense of time.
    */
   #define HASH(x) Hash = (Hash << 4) ^ (x)

   static unsigned short int Hash;
   static unsigned char GuessTable[65536];

   static int
   compress(source, dest, len)
   unsigned char *source, *dest;
   int len;
   {
       int i, bitmask;
       unsigned char *flagdest, flags, *orgdest;

       orgdest = dest;
       while (len) {
           flagdest = dest++; flags = 0; /* All guess wrong initially */
           for (bitmask=1, i=0; i < 8 && len; i++, bitmask <<= 1) {
               if (GuessTable[Hash] == *source) {
                   flags |= bitmask; /* Guess was right - don't output */
               } else {
                   GuessTable[Hash] = *source;
                   *dest++ = *source; /* Guess wrong, output char */
               }
               HASH(*source++);len--;
           }
           *flagdest = flags;
       }
       return(dest - orgdest);
   }

   static int



Rand                         Informational                      [Page 4]

RFC 1978                   Predictor Protocol                August 1996


   decompress(source, dest, lenp, final)
   unsigned char *source, *dest;
   int *lenp, final;
   {
       int i, bitmask;
       unsigned char flags, *orgdest;
       int len = *lenp;
       orgdest = dest;
       while (len >= 9) {
           flags = *source++;
           for (i=0, bitmask = 1; i < 8; i++, bitmask <<= 1) {
               if (flags & bitmask) {
                   *dest = GuessTable[Hash];       /* Guess correct */
               } else {
                   GuessTable[Hash] = *source;     /* Guess wrong */
                   *dest = *source++;          /* Read from source */
                   len--;
               }
               HASH(*dest++);
           }
           len--;
       }
       while (final && len) {
           flags = *source++;