summaryrefslogtreecommitdiff
path: root/doc/rfc/rfc1977.txt
diff options
context:
space:
mode:
Diffstat (limited to 'doc/rfc/rfc1977.txt')
-rw-r--r--doc/rfc/rfc1977.txt1403
1 files changed, 1403 insertions, 0 deletions
diff --git a/doc/rfc/rfc1977.txt b/doc/rfc/rfc1977.txt
new file mode 100644
index 0000000..a39cb69
--- /dev/null
+++ b/doc/rfc/rfc1977.txt
@@ -0,0 +1,1403 @@
+
+
+
+
+
+
+Network Working Group V. Schryver
+Request for Comments: 1977 August 1996
+Category: Informational
+
+
+ PPP BSD 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 for
+ transporting multi-protocol datagrams over point-to-point links.
+
+ The PPP Compression Control Protocol [2] provides a method to
+ negotiate and utilize compression protocols over PPP encapsulated
+ links.
+
+ This document describes the use of the Unix Compress compression
+ protocol for compressing PPP encapsulated packets.
+
+Table of Contents
+
+ 1. Introduction .................................... 1
+ 1.1 Licensing ................................. 2
+ 2. BSD Compress Packets ............................ 2
+ 2.1 Packet Format ............................. 5
+ 3. Configuration Option Format ..................... 6
+ APPENDICES ............................................. 7
+ A. BSD Compress Algorithm .......................... 7
+ SECURITY CONSIDERATIONS ................................ 24
+ REFERENCES ............................................. 24
+ ACKNOWLEDGEMENTS ....................................... 24
+ CHAIR'S ADDRESS ........................................ 25
+ AUTHOR'S ADDRESS ....................................... 25
+
+1. Introduction
+
+ UNIX compress as embodied in the freely and widely distributed BSD
+ source has the following features:
+
+ - dynamic table clearing when compression becomes less
+ effective.
+
+
+
+
+Schryver Informational [Page 1]
+
+RFC 1977 PPP BSD Compress August 1996
+
+
+ - automatic turning off of compression when the overall result
+ is not smaller than the input.
+
+ - dynamic choice of code width within predetermined limits.
+
+ - heavily used for many years in networks, on modem and other
+ point-to-point links to transfer netnews.
+
+ - an effective code width requires less than 64KBytes of memory
+ on both sender and receive.
+
+1.1. Licensing
+
+ BSD Unix compress command source is widely and freely available, with
+ no additional license for many computer vendors. The included source
+ code is based on the BSD compress command source and carries only the
+ copyright of The Regents of the University of California. Use the
+ code entirely at your own risk. It has no warranties or
+ indemnifications of any sort. Note that there are patents on LZW.
+
+2. BSD Compress Packets
+
+ Before any BSD Compress packets may be communicated, PPP must reach
+ the Network-Layer Protocol phase, and the CCP Control Protocol must
+ reach the Opened state.
+
+ Exactly one BSD Compress datagram is encapsulated in the PPP
+ Information field, where the PPP Protocol field contains 0xFD or
+ 0xFB. 0xFD is used when the PPP multilink protocol is not used or
+ "above" multilink. 0xFB is used "below" multilink, to compress
+ independently on individual links of a multilink bundle.
+
+ The maximum length of the BSD Compress datagram transmitted over a
+ PPP link is the same as the maximum length of the Information field
+ of a PPP encapsulated packet.
+
+ Only packets with PPP Protocol numbers in the range 0x0000 to 0x3FFF
+ and neither 0xFD nor 0xFB are compressed. Other PPP packets are
+ always sent uncompressed. Control packets are infrequent and should
+ not be compressed for robustness.
+
+ Padding
+
+ BSD Compress packets require the previous negotiation of the
+ Self-Describing-Padding Configuration Option [3] if padding is
+ added to packets. If no padding is added, than Self-Describing-
+ Padding is not required.
+
+
+
+
+Schryver Informational [Page 2]
+
+RFC 1977 PPP BSD Compress August 1996
+
+
+ Reliability and Sequencing
+
+ BSD Compress requires the packets to be delivered in sequence. It
+ relies on Reset-Request and Reset-Ack CCP packets or on
+ renegotiation of the Compression Control Protocol [2] to indicate
+ loss of synchronization between the transmitter and receiver. The
+ HDLC FCS detects corrupted packets and the normal mechanisms
+ discard them. Missing or out of order packets are detected by the
+ sequence number in each packet. The packet sequence number ought
+ to be checked before decoding the packet.
+
+ Instead of transmitting a Reset-Request packet when detecting a
+ decompression error, the receiver MAY momentary force CCP to drop
+ out of the Opened state by transmitting a new CCP Configure-
+ Request. This method is more expensive than using Reset-Requests.
+
+ When the receiver first encounters an unexpected sequence number
+ it SHOULD send a Reset-Request CCP packet as defined in the
+ Compression Control Protocol. When the transmitter sends the
+ Reset-Ack or when the receiver receives a Reset-ACK, they must
+ reset the sequence number to zero, clear the compression
+ dictionary, and resume sending and receiving compressed packets.
+ The receiver MUST discard all compressed packets after detecting
+ an error and until it receives a Reset-Ack. This strategy can be
+ thought of as abandoning the transmission of one "file" and
+ starting the transmission of a new "file."
+
+ The transmitter must clear its compression dictionary and respond
+ with a Reset-Ack each time it receives a Reset-Request, because it
+ cannot know if previous Reset-Acks reached the receiver. The
+ receiver MUST clear its compression dictionary each time it
+ receives a Reset-Ack, because the transmitter will have cleared
+ its compression dictionary.
+
+ When the link is busy, one decompression error is usually followed
+ by several more before the Reset-Ack can be received. It is
+ undesirable to transmit Reset-Requests more frequently than the
+ round-trip-time of the link, because redundant Reset-Requests
+ cause unnecessary compression dictionary clearing. The receiver
+ MAY transmit an additional Reset-Request each time it receives a
+ compressed or uncompressed packet until it finally receives a
+ Reset-Ack, but the receiver ought not transmit another Reset-
+ Request until the Reset-Ack for the previous one is late. The
+ receiver MUST transmit enough Reset-Request packets to ensure that
+ the transmitter receives at least one. For example, the receiver
+ might choose to not transmit another Reset-Request until after one
+ second (or, of course, a Reset-Ack has been received and
+ decompression resumed).
+
+
+
+Schryver Informational [Page 3]
+
+RFC 1977 PPP BSD Compress August 1996
+
+
+ Data Expansion
+
+ When significant data expansion is detected, the PPP packet MUST
+ be sent without compression. Packets that would expand by fewer
+ than 3 bytes SHOULD be sent without compression, but MAY be sent
+ compressed provided the result does not exceed the MTU of the
+ link. This makes moot standards document exegesises about exactly
+ which bytes, such as the Protocol fields, count toward expansion.
+
+ When a packet is received with PPP Protocol numbers in the range
+ 0x0000 to 0x3FFF, (except, of course, 0xFD and 0xFB) it is assumed
+ that the packet would have caused expansion. The packet is
+ locally compressed to update the compression history.
+
+ Sending incompressible packets in their native encapsulation
+ avoids maximum transmission unit complications. If uncompressed
+ packets could be larger than their native form, then it would be
+ necessary for the upper layers of an implementation to treat the
+ PPP link as if it had a smaller MTU, to ensure that compressed
+ incompressible packets are never larger than the negotiated PPP
+ MTU.
+
+ Using native encapsulation for incompressible packets complicates
+ the implementation. The transmitter and the receiver must start
+ putting information into the compression dictionary starting with
+ the same packets, without relying upon seeing a compressed packet
+ for synchronization. The first few packets after clearing the
+ dictionary are usually incompressible, and so are likely to sent
+ in their native encapsulation, just like packets before
+ compression is turned on. If CCP or LCP packets are handled
+ separately from Network-Layer packets (e.g. a "daemon" for control
+ packets and "kernel code" for data packets), care must be taken to
+ ensure that the transmitter synchronizes clearing the dictionary
+ with the transmission of the configure-ACK or Reset-Ack that
+ starts compression, and the receiver must similarly ensure that
+ its dictionary is cleared before it processes the next packet.
+
+ A difficulty caused by sending data that would expand uncompressed
+ is that the receiver must adaptively clear its dictionary at
+ precisely the same times as the sender. In the classic BSD
+ compression code, the dictionary clearing is signaled by the
+ reserved code 256. Because data that would expend is sent without
+ compression, there is no reliable way for the sender to signal
+ explicitly when it has cleared its dictionary. This difficulty is
+ resolved by specifying the parameters that control the dictionary
+ clearing, and having both sender and receiver clear their
+ dictionaries at the same times.
+
+
+
+
+Schryver Informational [Page 4]
+
+RFC 1977 PPP BSD Compress August 1996
+
+
+2.1. Packet Format
+
+ A summary of the BSD Compress packet format is shown below.
+
+ The fields are transmitted from left to right.
+
+ 0 1 2 3
+ 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
+ | PPP Protocol | Sequence
+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
+ | Data ...
+ +-+-+-+-+-+-+-+-+
+
+
+ PPP Protocol
+
+ The PPP Protocol field is described in the Point-to-Point Protocol
+ Encapsulation [1].
+
+ When the BSD Compress compression protocol is successfully
+ negotiated by the PPP Compression Control Protocol [2], the value
+ of the protocol field is 0xFD or 0xFB. This value MAY be
+ compressed when Protocol-Field-Compression is negotiated.
+
+ Sequence
+
+ The sequence number is sent most significant octet first. It
+ starts at 0 when the dictionary is cleared, and is incremented by
+ 1 after each packet, including uncompressed packets. The sequence
+ number after 65535 is zero. In other words, the sequence number
+ "wraps" in the usual way.
+
+ The sequence number ensures that lost or out of order packets do
+ not cause the compression databases of the peers to become
+ unsynchronized. When an unexpected sequence number is
+ encountered, the dictionaries must be resynchronized with a CCP
+ Reset-Request or Configure-Request. The packet sequence number
+ can be checked before a compressed packet is decoded.
+
+ Data
+
+ The compressed PPP encapsulated packet, consisting of the Protocol
+ and Data fields of the original, uncompressed packet follows.
+
+ The Protocol field compression MUST be applied to the protocol
+ field in the original packet before the sequence number is
+ computed or the entire packet is compressed, regardless of whether
+
+
+
+Schryver Informational [Page 5]
+
+RFC 1977 PPP BSD Compress August 1996
+
+
+ the PPP protocol field compression has been negotiated. Thus, if
+ the original protocol number was less than 0x100, it must be
+ compressed to a single byte.
+
+ The format of the compressed data is more precisely described by
+ the example code in the "BSD Compress Algorithm" appendix.
+
+3. Configuration Option Format
+
+
+ Description
+
+ The CCP BSD Compress Configuration Option negotiates the use of
+ BSD Compress on the link. By default or ultimate disagreement, no
+ compression is used.
+
+ A summary of the BSD Compress Configuration Option format is shown
+ below. The fields are transmitted from left to right.
+
+ 0 1 2
+ 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3
+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
+ | Type | Length | Vers| Dict |
+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
+
+
+ Type
+
+ 21 or 0x15 for BSD compress.
+
+ Length
+
+ 3
+
+ Vers
+
+ Must be the binary number 001.
+
+ Dict
+
+ The size in bits of the largest code used. It can range from 9 to
+ 16. A common choice is 12. The code included below can support
+ code sizes from 9 to 15.
+
+ It is convenient to treat the byte containing the Vers and Dict
+ fields as a single field with legal values ranging from 0x29 to
+ 0x30.
+
+
+
+
+Schryver Informational [Page 6]
+
+RFC 1977 PPP BSD Compress August 1996
+
+
+ Note that the peer receiving compressed data must use the same
+ code size as the peer sending data. It is not practical for the
+ receiver to use a larger dictionary or code size, because both
+ dictionaries must be cleared at the same time, even when the data
+ is not compressible, so that uncompressed packets are being sent,
+ and so the receiver cannot receive LZW "CLEAR" codes.
+
+ When a received Configure-Request specifies a smaller dictionary
+ than the local preference, it is often best to accept it instead
+ of using a Configure-Nak to ask the peer to specify a larger
+ dictionary.
+
+A. BSD Compress Algorithm
+
+ This code is the core of a commercial workstation implementation. It
+ was derived by transliterating the 4.*BSD compress command. It is
+ unlikely to be of direct use in any system that does not have the
+ same mixture of mbufs and STREAMS buffers. It may need to be retuned
+ for CPU's other than RISC's with many registers and certain
+ addressing modes. However, the code is the most accurate and
+ unambiguous way of defining the changes to the BSD compress source
+ required to apply it to a stream instead of a file.
+
+ Note that it assumes a "short" contains 16 bits and an "int" contains
+ at least 32 bits. Where it would matter if more than 32 bits were in
+ an "int" or "long," __uint32_t is used instead.
+
+/* Because this code is derived from the 4.3BSD compress source:
+ *
+ *
+ * Copyright (c) 1985, 1986 The Regents of the University of California.
+ * All rights reserved.
+ *
+ * This code is derived from software contributed to Berkeley by
+ * James A. Woods, derived from original work by Spencer Thomas
+ * and Joseph Orost.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in
+ * the documentation and/or other materials provided with the
+ * distribution.
+ * 3. All advertising materials mentioning features or use of this
+ * software must display the following acknowledgement:
+
+
+
+Schryver Informational [Page 7]
+
+RFC 1977 PPP BSD Compress August 1996
+
+
+ * This product includes software developed by the University of
+ * California, Berkeley and its contributors.
+ * 4. Neither the name of the University nor the names of its
+ * contributors may be used to endorse or promote products derived
+ * from this software without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS''
+ * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
+ * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
+ * PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS
+ * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+ * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+ * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+ * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+ * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+
+/* ***************** */
+
+struct bsd_db {
+ int totlen; /* length of this structure */
+ u_int hsize; /* size of the hash table */
+ u_char hshift; /* used in hash function */
+ u_char n_bits; /* current bits/code */
+ u_char debug;
+ u_char unit;
+ u_short mru;
+ u_short seqno; /* # of last byte of packet */
+ u_int maxmaxcode; /* largest valid code */
+ u_int max_ent; /* largest code in use */
+ u_int in_count; /* uncompressed bytes */
+ u_int bytes_out; /* compressed bytes */
+ u_int ratio; /* recent compression ratio */
+ u_int checkpoint; /* when to next check ratio */
+ int clear_count; /* times dictionary cleared */
+ int incomp_count; /* incompressible packets */
+ int decomp_count; /* packets decompressed */
+ int overshoot; /* excess decompression buf */
+ int undershoot; /* insufficient decomp. buf */
+ u_short *lens; /* array of lengths of codes */
+ struct bsd_dict {
+ union { /* hash value */
+ __uint32_t fcode;
+ struct {
+#ifdef BSD_LITTLE_ENDIAN
+
+
+
+Schryver Informational [Page 8]
+
+RFC 1977 PPP BSD Compress August 1996
+
+
+ u_short prefix; /* preceding code */
+ u_char suffix; /* last character of new code */
+ u_char pad;
+#else
+ u_char pad;
+ u_char suffix; /* last character of new code */
+ u_short prefix; /* preceding code */
+#endif
+ } hs;
+ } f;
+ u_short codem1; /* output of hash table -1 */
+ u_short cptr; /* map code to hash table */
+ } dict[1];
+};
+#define BSD_OVHD (2+2) /* overhead/packet */
+#define MIN_BSD_BITS 9
+#define MAX_BSD_BITS 15 /* implementation limit */
+#define BSD_VERS 1 /* when shifted */
+#ifdef _KERNEL
+extern struct bsd_db *pf_bsd_init(struct bsd_db*, int, int, int);
+extern int pf_bsd_comp(struct bsd_db*,u_char*,int,struct mbuf*,int);
+extern mblk_t* pf_bsd_decomp(struct bsd_db*, mblk_t*);
+extern void pf_bsd_incomp(struct bsd_db*, mblk_t*, u_int);
+#endif
+
+
+/* ***************** */
+/* PPP "BSD compress" compression
+ * The differences between this compression and the classic BSD LZW
+ * source are obvious from the requirement that the classic code worked
+ * with files while this handles arbitrarily long streams that
+ * are broken into packets. They are:
+ *
+ * When the code size expands, a block of junk is not emitted by
+ * the compressor and not expected by the decompressor.
+ *
+ * New codes are not necessarily assigned every time an old
+ * code is output by the compressor. This is because a packet
+ * end forces a code to be emitted, but does not imply that a
+ * new sequence has been seen.
+ *
+ * The compression ratio is checked at the first end of a packet
+ * after the appropriate gap. Besides simplifying and speeding
+ * things up, this makes it more likely that the transmitter
+ * and receiver will agree when the dictionary is cleared when
+ * compression is not going well.
+ */
+
+
+
+
+Schryver Informational [Page 9]
+
+RFC 1977 PPP BSD Compress August 1996
+
+
+/*
+ * the next two codes should not be changed lightly, as they must not
+ * lie within the contiguous general code space.
+ */
+#define CLEAR 256 /* table clear output code */
+#define FIRST 257 /* first free entry */
+#define LAST 255
+
+#define BSD_INIT_BITS MIN_BSD_BITS
+
+#define MAXCODE(b) ((1 << (b)) - 1)
+#define BADCODEM1 MAXCODE(MAX_BSD_BITS);
+
+#define BSD_HASH(prefix,suffix,hshift) ((((__uint32_t)(suffix)) \
+ << (hshift)) \
+ ^ (__uint32_t)(prefix))
+#define BSD_KEY(prefix,suffix) ((((__uint32_t)(suffix)) << 16) \
+ + (__uint32_t)(prefix))
+
+#define CHECK_GAP 10000 /* Ratio check interval */
+
+#define RATIO_SCALE_LOG 8
+#define RATIO_SCALE (1<<RATIO_SCALE_LOG)
+#define RATIO_MAX (0x7fffffff>>RATIO_SCALE_LOG)
+
+/* clear the dictionary
+ */
+static void
+pf_bsd_clear(struct bsd_db *db)
+{
+ db->clear_count++;
+ db->max_ent = FIRST-1;
+ db->n_bits = BSD_INIT_BITS;
+ db->ratio = 0;
+ db->bytes_out = 0;
+ db->in_count = 0;
+ db->incomp_count = 0;
+ db->decomp_count = 0;
+ db->overshoot = 0;
+ db->undershoot = 0;
+ db->checkpoint = CHECK_GAP;
+}
+
+
+/* If the dictionary is full, then see if it is time to reset it.
+ *
+ * Compute the compression ratio using fixed-point arithmetic
+ * with 8 fractional bits.
+
+
+
+Schryver Informational [Page 10]
+
+RFC 1977 PPP BSD Compress August 1996
+
+
+ *
+ * Since we have an infinite stream instead of a single file,
+ * watch only the local compression ratio.
+ *
+ * Since both peers must reset the dictionary at the same time even in
+ * the absence of CLEAR codes (while packets are incompressible), they
+ * must compute the same ratio.
+ */
+static int /* 1=output CLEAR */
+pf_bsd_check(struct bsd_db *db)
+{
+ register u_int new_ratio;
+
+ if (db->in_count >= db->checkpoint) {
+ /* age the ratio by limiting the size of the counts */
+ if (db->in_count >= RATIO_MAX
+ || db->bytes_out >= RATIO_MAX) {
+ db->in_count -= db->in_count/4;
+ db->bytes_out -= db->bytes_out/4;
+ }
+
+ db->checkpoint = db->in_count + CHECK_GAP;
+
+ if (db->max_ent >= db->maxmaxcode) {
+ /* Reset the dictionary only if the ratio is
+ * worse, or if it looks as if it has been
+ * poisoned by incompressible data.
+ *
+ * This does not overflow, because
+ * db->in_count <= RATIO_MAX.
+ */
+ new_ratio = db->in_count<<RATIO_SCALE_LOG;
+ if (db->bytes_out != 0)
+ new_ratio /= db->bytes_out;
+
+ if (new_ratio < db->ratio
+ || new_ratio < 1*RATIO_SCALE) {
+ pf_bsd_clear(db);
+ return 1;
+ }
+ db->ratio = new_ratio;
+ }
+ }
+ return 0;
+}
+
+
+/* Initialize the database.
+
+
+
+Schryver Informational [Page 11]
+
+RFC 1977 PPP BSD Compress August 1996
+
+
+ */
+struct bsd_db *
+pf_bsd_init(struct bsd_db *db, /* initialize this database */
+ int unit, /* for debugging */
+ int bits, /* size of LZW code word */
+ int mru) /* MRU for input, 0 for output*/
+{
+ register int i;
+ register u_short *lens;
+ register u_int newlen, hsize, hshift, maxmaxcode;
+
+ switch (bits) {
+ case 9: /* needs 82152 for both comp &*/
+ case 10: /* needs 84144 decomp*/
+ case 11: /* needs 88240 */
+ case 12: /* needs 96432 */
+ hsize = 5003;
+ hshift = 4;
+ break;
+ case 13: /* needs 176784 */
+ hsize = 9001;
+ hshift = 5;
+ break;
+ case 14: /* needs 353744 */
+ hsize = 18013;
+ hshift = 6;
+ break;
+ case 15: /* needs 691440 */
+ hsize = 35023;
+ hshift = 7;
+ break;
+ case 16: /* needs 1366160--far too much*/
+ /* hsize = 69001; */ /* and 69001 is too big for */
+ /* hshift = 8; */ /* cptr in struct bsd_db */
+ /* break; */
+ default:
+ if (db) {
+ if (db->lens)
+ kern_free(db->lens);
+ kern_free(db);
+ }
+ return 0;
+ }
+ maxmaxcode = MAXCODE(bits);
+ newlen = sizeof(*db) + (hsize-1)*(sizeof(db->dict[0]));
+
+ if (db) {
+ lens = db->lens;
+
+
+
+Schryver Informational [Page 12]
+
+RFC 1977 PPP BSD Compress August 1996
+
+
+ if (db->totlen != newlen) {
+ if (lens)
+ kern_free(lens);
+ kern_free(db);
+ db = 0;
+ }
+ }
+ if (!db) {
+ db = (struct bsd_db*)kern_malloc(newlen);
+ if (!db)
+ return 0;
+ if (mru == 0) {
+ lens = 0;
+ } else {
+ lens = (u_short*)kern_malloc((maxmaxcode+1)
+ * sizeof(*lens));
+ if (!lens) {
+ kern_free(db);
+ return 0;
+ }
+ i = LAST+1;
+ while (i != 0)
+ lens[--i] = 1;
+ }
+ i = hsize;
+ while (i != 0) {
+ db->dict[--i].codem1 = BADCODEM1;
+ db->dict[i].cptr = 0;
+ }
+ }
+
+ bzero(db,sizeof(*db)-sizeof(db->dict));
+ db->lens = lens;
+ db->unit = unit;
+ db->mru = mru;
+ db->hsize = hsize;
+ db->hshift = hshift;
+ db->maxmaxcode = maxmaxcode;
+ db->clear_count = -1;
+
+ pf_bsd_clear(db);
+
+ return db;
+}
+
+
+/* compress a packet
+ * Assume the protocol is known to be >= 0x21 and < 0xff.
+
+
+
+Schryver Informational [Page 13]
+
+RFC 1977 PPP BSD Compress August 1996
+
+
+ * One change from the BSD compress command is that when the
+ * code size expands, we do not output a bunch of padding.
+ */
+int /* new slen */
+pf_bsd_comp(struct bsd_db *db,
+ u_char *cp_buf, /* compress into here */
+ int proto, /* this original PPP protocol */
+ struct mbuf *m, /* from here */
+ int slen)
+{
+ register int hshift = db->hshift;
+ register u_int max_ent = db->max_ent;
+ register u_int n_bits = db->n_bits;
+ register u_int bitno = 32;
+ register __uint32_t accum = 0;
+ register struct bsd_dict *dictp;
+ register __uint32_t fcode;
+ register u_char c;
+ register int hval, disp, ent;
+ register u_char *rptr, *wptr;
+ struct mbuf *n;
+
+#define OUTPUT(ent) { \
+ bitno -= n_bits; \
+ accum |= ((ent) << bitno); \
+ do { \
+ *wptr++ = accum>>24; \
+ accum <<= 8; \
+ bitno += 8; \
+ } while (bitno <= 24); \
+ }
+
+
+ /* start with the protocol byte */
+ ent = proto;
+ db->in_count++;
+
+ /* install sequence number */
+ cp_buf[0] = db->seqno>>8;
+ cp_buf[1] = db->seqno;
+ db->seqno++;
+
+ wptr = &cp_buf[2];
+ slen = m->m_len;
+ db->in_count += slen;
+ rptr = mtod(m, u_char*);
+ n = m->m_next;
+ for (;;) {
+
+
+
+Schryver Informational [Page 14]
+
+RFC 1977 PPP BSD Compress August 1996
+
+
+ if (slen == 0) {
+ if (!n)
+ break;
+ slen = n->m_len;
+ rptr = mtod(n, u_char*);
+ n = n->m_next;
+ if (!slen)
+ continue; /* handle 0-length buffers*/
+ db->in_count += slen;
+ }
+
+ slen--;
+ c = *rptr++;
+ fcode = BSD_KEY(ent,c);
+ hval = BSD_HASH(ent,c,hshift);
+ dictp = &db->dict[hval];
+
+ /* Validate and then check the entry. */
+ if (dictp->codem1 >= max_ent)
+ goto nomatch;
+ if (dictp->f.fcode == fcode) {
+ ent = dictp->codem1+1;
+ continue; /* found (prefix,suffix) */
+ }
+
+ /* continue probing until a match or invalid entry */
+ disp = (hval == 0) ? 1 : hval;
+ do {
+ hval += disp;
+ if (hval >= db->hsize)
+ hval -= db->hsize;
+ dictp = &db->dict[hval];
+ if (dictp->codem1 >= max_ent)
+ goto nomatch;
+ } while (dictp->f.fcode != fcode);
+ ent = dictp->codem1+1; /* found (prefix,suffix) */
+ continue;
+
+nomatch:
+ OUTPUT(ent); /* output the prefix */
+
+ /* code -> hashtable */
+ if (max_ent < db->maxmaxcode) {
+ struct bsd_dict *dictp2;
+ /* expand code size if needed */
+ if (max_ent >= MAXCODE(n_bits))
+ db->n_bits = ++n_bits;
+
+
+
+
+Schryver Informational [Page 15]
+
+RFC 1977 PPP BSD Compress August 1996
+
+
+ /* Invalidate old hash table entry using
+ * this code, and then take it over.
+ */
+ dictp2 = &db->dict[max_ent+1];
+ if (db->dict[dictp2->cptr].codem1 == max_ent)
+ db->dict[dictp2->cptr].codem1=BADCODEM1;
+ dictp2->cptr = hval;
+ dictp->codem1 = max_ent;
+ dictp->f.fcode = fcode;
+
+ db->max_ent = ++max_ent;
+ }
+ ent = c;
+ }
+
+ OUTPUT(ent); /* output the last code */
+ db->bytes_out += (wptr-&cp_buf[2] /* count complete bytes */
+ + (32-bitno+7)/8);
+
+ if (pf_bsd_check(db))
+ OUTPUT(CLEAR); /* do not count the CLEAR */
+
+ /* Pad dribble bits of last code with ones.
+ * Do not emit a completely useless byte of ones.
+ */
+ if (bitno != 32)
+ *wptr++ = (accum | (0xff << (bitno-8))) >> 24;
+
+ /* Increase code size if we would have without the packet
+ * boundary and as the decompressor will.
+ */
+ if (max_ent >= MAXCODE(n_bits)
+ && max_ent < db->maxmaxcode)
+ db->n_bits++;
+
+ return (wptr - cp_buf);
+#undef OUTPUT
+}
+
+
+/* Update the "BSD Compress" dictionary on the receiver for
+ * incompressible data by pretending to compress the incoming data.
+ */
+void
+pf_bsd_incomp(struct bsd_db *db,
+ mblk_t *dmsg,
+ u_int ent) /* start with protocol byte */
+{
+
+
+
+Schryver Informational [Page 16]
+
+RFC 1977 PPP BSD Compress August 1996
+
+
+ register u_int hshift = db->hshift;
+ register u_int max_ent = db->max_ent;
+ register u_int n_bits = db->n_bits;
+ register struct bsd_dict *dictp;
+ register __uint32_t fcode;
+ register u_char c;
+ register int hval, disp;
+ register int slen;
+ register u_int bitno = 7;
+ register u_char *rptr;
+
+ db->incomp_count++;
+
+ db->in_count++; /* count protocol as 1 byte */
+ db->seqno++;
+ rptr = dmsg->b_rptr+PPP_BUF_HEAD_INFO;
+ for (;;) {
+ slen = dmsg->b_wptr - rptr;
+ if (slen == 0) {
+ dmsg = dmsg->b_cont;
+ if (!dmsg)
+ break;
+ rptr = dmsg->b_rptr;
+ continue; /* skip zero-length buffers */
+ }
+ db->in_count += slen;
+
+ do {
+ c = *rptr++;
+ fcode = BSD_KEY(ent,c);
+ hval = BSD_HASH(ent,c,hshift);
+ dictp = &db->dict[hval];
+
+ /* validate and then check the entry */
+ if (dictp->codem1 >= max_ent)
+ goto nomatch;
+ if (dictp->f.fcode == fcode) {
+ ent = dictp->codem1+1;
+ continue; /* found (prefix,suffix) */
+ }
+
+ /* continue until match or invalid entry */
+ disp = (hval == 0) ? 1 : hval;
+ do {
+ hval += disp;
+ if (hval >= db->hsize)
+ hval -= db->hsize;
+ dictp = &db->dict[hval];
+
+
+
+Schryver Informational [Page 17]
+
+RFC 1977 PPP BSD Compress August 1996
+
+
+ if (dictp->codem1 >= max_ent)
+ goto nomatch;
+ } while (dictp->f.fcode != fcode);
+ ent = dictp->codem1+1;
+ continue; /* found (prefix,suffix) */
+
+nomatch: /* output (count) the prefix */
+ bitno += n_bits;
+
+ /* code -> hashtable */
+ if (max_ent < db->maxmaxcode) {
+ struct bsd_dict *dictp2;
+ /* expand code size if needed */
+ if (max_ent >= MAXCODE(n_bits))
+ db->n_bits = ++n_bits;
+ /* Invalidate previous hash table entry
+ * assigned this code, and then take it over
+ */
+ dictp2 = &db->dict[max_ent+1];
+ if (db->dict[dictp2->cptr].codem1==max_ent)
+ db->dict[dictp2->cptr].codem1=BADCODEM1;
+ dictp2->cptr = hval;
+ dictp->codem1 = max_ent;
+ dictp->f.fcode = fcode;
+
+ db->max_ent = ++max_ent;
+ db->lens[max_ent] = db->lens[ent]+1;
+ }
+ ent = c;
+ } while (--slen != 0);
+ }
+ bitno += n_bits; /* output (count) last code */
+ db->bytes_out += bitno/8;
+
+ (void)pf_bsd_check(db);
+
+ /* Increase code size if we would have without the packet
+ * boundary and as the decompressor will.
+ */
+ if (max_ent >= MAXCODE(n_bits)
+ && max_ent < db->maxmaxcode)
+ db->n_bits++;
+}
+
+
+/* Decompress "BSD Compress"
+ */
+mblk_t* /* 0=failed, so zap CCP */
+
+
+
+Schryver Informational [Page 18]
+
+RFC 1977 PPP BSD Compress August 1996
+
+
+pf_bsd_decomp(struct bsd_db *db,
+ mblk_t *cmsg)
+{
+ register u_int max_ent = db->max_ent;
+ register __uint32_t accum = 0;
+ register u_int bitno = 32; /* 1st valid bit in accum */
+ register u_int n_bits = db->n_bits;
+ register u_int tgtbitno = 32-n_bits; /* bitno when accum full */
+ register struct bsd_dict *dictp;
+ register int explen, i;
+ register u_int incode, oldcode, finchar;
+ register u_char *p, *rptr, *rptr9, *wptr0, *wptr;
+ mblk_t *dmsg, *dmsg1, *bp;
+
+ db->decomp_count++;
+ rptr = cmsg->b_rptr;
+ ASSERT(cmsg->b_wptr >= rptr+PPP_BUF_MIN);
+ ASSERT(PPP_BUF_ALIGN(rptr));
+ rptr += PPP_BUF_MIN;
+
+ /* get the sequence number */
+ i = 0;
+ explen = 2;
+ do {
+ while (rptr >= cmsg->b_wptr) {
+ bp = cmsg;
+ cmsg = cmsg->b_cont;
+ freeb(bp);
+ if (!cmsg) {
+ if (db->debug)
+ printf("bsd_decomp%d: missing"
+ " %d header bytes\n",
+ db->unit, explen);
+ return 0;
+ }
+ rptr = cmsg->b_rptr;
+ }
+ i = (i << 8) + *rptr++;
+ } while (--explen != 0);
+ if (i != db->seqno++) {
+ freemsg(cmsg);
+ if (db->debug)
+ printf("bsd_decomp%d: bad sequence number 0x%x"
+ " instead of 0x%x\n",
+ db->unit, i, db->seqno-1);
+ return 0;
+ }
+
+
+
+
+Schryver Informational [Page 19]
+
+RFC 1977 PPP BSD Compress August 1996
+
+
+ /* Guess how much memory we will need. Assume this packet was
+ * compressed by at least 1.5X regardless of the recent ratio.
+ */
+ if (db->ratio > (RATIO_SCALE*3)/2)
+ explen = (msgdsize(cmsg)*db->ratio)/RATIO_SCALE;
+ else
+ explen = (msgdsize(cmsg)*3)/2;
+ if (explen > db->mru)
+ explen = db->mru;
+
+ dmsg = dmsg1 = allocb(explen+PPP_BUF_HEAD_INFO, BPRI_HI);
+ if (!dmsg1) {
+ freemsg(cmsg);
+ return 0;
+ }
+
+ wptr = dmsg1->b_wptr;
+
+ ((struct ppp_buf*)wptr)->type = BEEP_FRAME;
+ /* the protocol field must be compressed */
+ ((struct ppp_buf*)wptr)->proto = 0;
+ wptr += PPP_BUF_HEAD_PROTO+1;
+
+ rptr9 = cmsg->b_wptr;
+ db->bytes_out += rptr9-rptr;
+ wptr0 = wptr;
+ explen = dmsg1->b_datap->db_lim - wptr;
+ oldcode = CLEAR;
+ for (;;) {
+ if (rptr >= rptr9) {
+ bp = cmsg;
+ cmsg = cmsg->b_cont;
+ freeb(bp);
+ if (!cmsg) /* quit at end of message */
+ break;
+ rptr = cmsg->b_rptr;
+ rptr9 = cmsg->b_wptr;
+ db->bytes_out += rptr9-rptr;
+ continue; /* handle 0-length buffers */
+ }
+
+ /* Accumulate bytes until we have a complete code.
+ * Then get the next code, relying on the 32-bit,
+ * unsigned accum to mask the result.
+ */
+ bitno -= 8;
+ accum |= *rptr++ << bitno;
+ if (tgtbitno < bitno)
+
+
+
+Schryver Informational [Page 20]
+
+RFC 1977 PPP BSD Compress August 1996
+
+
+ continue;
+ incode = accum >> tgtbitno;
+ accum <<= n_bits;
+ bitno += n_bits;
+
+ if (incode == CLEAR) {
+ /* The dictionary must only be cleared at
+ * the end of a packet. But there could be an
+ * empty message block at the end.
+ */
+ if (rptr != rptr9
+ || cmsg->b_cont != 0) {
+ cmsg->b_rptr = rptr;
+ i = msgdsize(cmsg);
+ if (i != 0) {
+ freemsg(dmsg);
+ freemsg(cmsg);
+ if (db->debug)
+ printf("bsd_decomp%d: "
+ "bad CLEAR\n",
+ db->unit);
+ return 0;
+ }
+ }
+ pf_bsd_clear(db);
+ freemsg(cmsg);
+ wptr0 = wptr;
+ break;
+ }
+
+ /* Special case for KwKwK string. */
+ if (incode > max_ent) {
+ if (incode > max_ent+2
+ || incode > db->maxmaxcode
+ || oldcode == CLEAR) {
+ freemsg(dmsg);
+ freemsg(cmsg);
+ if (db->debug)
+ printf("bsd_decomp%d: bad code %x\n",
+ db->unit, incode);
+ return 0;
+ }
+ i = db->lens[oldcode];
+ /* do not write past end of buf */
+ explen -= i+1;
+ if (explen < 0) {
+ db->undershoot -= explen;
+ db->in_count += wptr-wptr0;
+
+
+
+Schryver Informational [Page 21]
+
+RFC 1977 PPP BSD Compress August 1996
+
+
+ dmsg1->b_wptr = wptr;
+ CK_WPTR(dmsg1);
+ explen = MAX(64,i+1);
+ bp = allocb(explen, BPRI_HI);
+ if (!bp) {
+ freemsg(cmsg);
+ freemsg(dmsg);
+ return 0;
+ }
+ dmsg1->b_cont = bp;
+ dmsg1 = bp;
+ wptr0 = wptr = dmsg1->b_wptr;
+ explen=dmsg1->b_datap->db_lim-wptr-(i+1);
+ }
+ p = (wptr += i);
+ *wptr++ = finchar;
+ finchar = oldcode;
+ } else {
+ i = db->lens[finchar = incode];
+ explen -= i;
+ if (explen < 0) {
+ db->undershoot -= explen;
+ db->in_count += wptr-wptr0;
+ dmsg1->b_wptr = wptr;
+ CK_WPTR(dmsg1);
+ explen = MAX(64,i);
+ bp = allocb(explen, BPRI_HI);
+ if (!bp) {
+ freemsg(dmsg);
+ freemsg(cmsg);
+ return 0;
+ }
+ dmsg1->b_cont = bp;
+ dmsg1 = bp;
+ wptr0 = wptr = dmsg1->b_wptr;
+ explen = dmsg1->b_datap->db_lim-wptr-i;
+ }
+ p = (wptr += i);
+ }
+
+ /* decode code and install in decompressed buffer */
+ while (finchar > LAST) {
+ dictp = &db->dict[db->dict[finchar].cptr];
+ *--p = dictp->f.hs.suffix;
+ finchar = dictp->f.hs.prefix;
+ }
+ *--p = finchar;
+
+
+
+
+Schryver Informational [Page 22]
+
+RFC 1977 PPP BSD Compress August 1996
+
+
+ /* If not first code in a packet, and
+ * if not out of code space, then allocate a new code.
+ *
+ * Keep the hash table correct so it can be used
+ * with uncompressed packets.
+ */
+ if (oldcode != CLEAR
+ && max_ent < db->maxmaxcode) {
+ struct bsd_dict *dictp2;
+ __uint32_t fcode;
+ int hval, disp;
+
+ fcode = BSD_KEY(oldcode,finchar);
+ hval = BSD_HASH(oldcode,finchar,db->hshift);
+ dictp = &db->dict[hval];
+ /* look for a free hash table entry */
+ if (dictp->codem1 < max_ent) {
+ disp = (hval == 0) ? 1 : hval;
+ do {
+ hval += disp;
+ if (hval >= db->hsize)
+ hval -= db->hsize;
+ dictp = &db->dict[hval];
+ } while (dictp->codem1 < max_ent);
+ }
+
+ /* Invalidate previous hash table entry
+ * assigned this code, and then take it over
+ */
+ dictp2 = &db->dict[max_ent+1];
+ if (db->dict[dictp2->cptr].codem1 == max_ent) {
+ db->dict[dictp2->cptr].codem1=BADCODEM1;
+ }
+ dictp2->cptr = hval;
+ dictp->codem1 = max_ent;
+ dictp->f.fcode = fcode;
+
+ db->max_ent = ++max_ent;
+ db->lens[max_ent] = db->lens[oldcode]+1;
+
+ /* Expand code size if needed.
+ */
+ if (max_ent >= MAXCODE(n_bits)
+ && max_ent < db->maxmaxcode) {
+ db->n_bits = ++n_bits;
+ tgtbitno = 32-n_bits;
+ }
+ }
+
+
+
+Schryver Informational [Page 23]
+
+RFC 1977 PPP BSD Compress August 1996
+
+
+ oldcode = incode;
+ }
+
+ db->in_count += wptr-wptr0;
+ dmsg1->b_wptr = wptr;
+ CK_WPTR(dmsg1);
+
+ db->overshoot += explen;
+
+ /* Keep the checkpoint right so that incompressible packets
+ * clear the dictionary at the right times.
+ */
+ if (pf_bsd_check(db)
+ && db->debug) {
+ printf("bsd_decomp%d: peer should have "
+ "cleared dictionary\n", db->unit);
+ }
+
+ return dmsg;
+}
+
+Security Considerations
+
+ Security issues are not discussed in this memo.
+
+References
+
+ [1] Simpson, W., "The Point-to-Point Protocol (PPP)", STD 51,
+ RFC 1661, July 1994.
+
+ [2] Rand, D., "The PPP Compression Control Protocol (CCP)", RFC
+ 1962, June 1996.
+
+ [3] Simpson, W., "PPP LCP Extensions", RFC 1570, January 1994.
+
+ [4] Simpson, W., "PPP in HDLC-like Framing", STD 51, RFC 1662,
+ July 1994.
+
+Acknowledgments
+
+ William Simpson provided and supported the very valuable idea of not
+ using any additional header bytes for incompressible packets.
+
+
+
+
+
+
+
+
+
+Schryver Informational [Page 24]
+
+RFC 1977 PPP BSD Compress August 1996
+
+
+Chair's Address
+
+ The working group can be contacted via the current chair:
+
+ Karl Fox
+ Ascend Communications
+ 3518 Riverside Drive, Suite 101
+ Columbus, Ohio 43221
+
+ EMail: karl@ascend.com
+
+Author's Address
+
+ Questions about this memo can also be directed to:
+
+ Vernon Schryver
+ 2482 Lee Hill Drive
+ Boulder, Colorado 80302
+
+ EMail: vjs@rhyolite.com
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+Schryver Informational [Page 25]
+