INTERNET-DRAFT A. Costanzo draft-costanzo-lzju90-mime-01.txt AKC Computer Services Corp. Expires: March 8th, 1999 September 3, 1998 Definition of the LZJU90 MIME Content Transfer Encoding Type 1. Status of this Memo This document is an Internet-Draft. Internet-Drafts are working docu- ments of the Internet Engineering Task Force (IETF), its areas, and its working groups. Note that other groups may also distribute working documents as Internet-Drafts. Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress." To learn the current status of any Internet-Draft, please check the "1id-abstracts.txt" listing contained in the Internet- Drafts Shadow Directories on ftp.is.co.za (Africa), nic.nordu.net (Europe), munnari.oz.au (Pacific Rim), ftp.ietf.org (US East Coast, or ftp.isi.edu (US West Coast). Distribution of this memo is unlimited. 2. Abstract This memo defines a new transfer encoding type for MIME, namely LZJU90. LZJU90 specifies a section consisting of an encoded binary or text object. The encoding provides both compression and representation in a text format. The keywords "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY" and "OPTIONAL" in this document are to be interpreted as described in RFC 2119. 3. Introduction The Multipurpose Internet Message Extensions (MIME) define a facility whereby messages may use a specific transfer encoding scheme to survive the process of transport through various mail delivery systems and transport agents. This Draft specifies and defines the LZJU90 transfer encoding for MIME compliant mail systems. This transfer encoding was first defined in RFC 1505 [1]. Costanzo [Page 1] EXPIRES IN SIX MONTHS September 3, 1998 LZJU90 specifies a section consisting of an encoded binary or text object. The encoding (defined below) provides both compression and representation in a text format. This encoding is advantageous and superior over other encoding schemes in that the resulting object is compressed, usually much smaller than an object using a transfer encoding of some other type. The resulting compressed object, is in the character set ISO-10646-UTF-8. [2] [3] 3. Definition of the LZJU90 Compressed Encoding LZJU90 is an encoding for a binary or text object to be sent in an Internet mail message. The encoding provides both compression and representation in a text format that will successfully survive transmission through the many different mailers and gateways that comprise the Internet and connected mail networks. 3.1 Overview The encoding first compresses the binary object, using a modified LZ77 algorithm, called LZJU90. It then encodes each 6 bits of the output of the compression as a text character, using a character set chosen to survive any translations between codes, such as ASCII to EBCDIC. The 64 six-bit strings 000000 through 111111 are represented by the characters "+", "-", "0" to "9", "A" to "Z", and "a" to "z". The output text begins with a line identifying the encoding. This is for visual reference only, the content transfer encoding header identifies the section to the user program. It also names the object that was encoded, usually by a file name. The format of this line is: * LZJU90 <name> where <name> is optional. For example: * LZJU90 foobar This is followed by the compressed and encoded data, broken into lines where convenient. It is recommended that lines be broken about every 76 characters length. The decoder must accept lines with 1 to 1000 characters on each line. After this, there is one final line that gives the number of bytes in the original data and a CRC of the original data. This should match the byte count and CRC found during decompression. This line has the format: * <count> <CRC> Costanzo [Page 2] EXPIRES IN SIX MONTHS September 3, 1998 where <count> is a decimal number, and CRC is 8 hexadecimal digits. For example: * 4128076 5AC2D50E The count used in encoding the object. This numeral is the total number of lines, including the start and end lines that begin with *. 3.2 Specification of the LZJU90 compression The Lempel-Ziv-Storer-Szymanski model of mixing pointers and literal characters is used in the compression algorithm. Repeat occurrences of strings of octets are replaced by pointers to the earlier occurrence. The data compression is defined by the decoding algorithm. Any encoder that emits symbols which cause the decoder to produce the original input is defined to be valid. There are many possible strategies for the maximal-string matching that the encoder does, section 3.2.2 gives an example of one such algorithm. Regardless of which algorithm is used, and what tradeoffs are made between compression ratio and execution speed or space, the result can always be decoded by the simple decoder. The compressed data consists of a mixture of unencoded literal characters and copy pointers which point to an earlier occurrence of the string to be encoded. Compressed data contains two types of codewords: LITERAL pass the literal directly to the uncompressed output. COPY length, offset go back offset characters in the output and copy length characters forward to the current position. To distinguish between codewords, the copy length is used. A copy length of zero indicates that the following codeword is a literal codeword. A copy length greater than zero indicates that the following codeword is a copy codeword. To improve copy length encoding, a threshold value of 2 has been subtracted from the original copy length for copy codewords, because the minimum copy length is 3 in this compression scheme. Costanzo [Page 3] EXPIRES IN SIX MONTHS September 3, 1998 The maximum offset value is set at 32255. Larger offsets offer extremely low improvements in compression (less than 1 percent, typically). No special encoding is done on the LITERAL characters. However, unary encoding is used for the copy length and copy offset values to improve compression. A start-step-stop unary code is used. A (start, step, stop) unary code of the integers is defined as follows: The Nth codeword has N ones followed by a zero followed by a field of size START + (N * STEP). If the field width is equal to STOP then the preceding zero can be omitted. The integers are laid out sequentially through these codewords. For example, (0, 1, 4) would look like: Codeword Range 0 0 10x 1-2 110xx 3-6 1110xxx 7-14 1111xxxx 15-30 Following are the actual values used for copy length and copy offset: The copy length is encoded with a (0, 1, 7) code leading to a maximum copy length of 256 by including the THRESHOLD value of 2. Codeword Range 0 0 10x 3-4 110xx 5-8 1110xxx 9-16 11110xxxx 17-32 111110xxxxx 33-64 1111110xxxxxx 65-128 1111111xxxxxxx 129-256 The copy offset is encoded with a (9, 1, 14) code leading to a maximum copy offset of 32255. Offset 0 is reserved as an end of compressed data flag. Codeword Range 0xxxxxxxxx 0-511 10xxxxxxxxxx 512-1535 110xxxxxxxxxxx 1536-3583 1110xxxxxxxxxxxx 3485-7679 11110xxxxxxxxxxxxx 7680-15871 11111xxxxxxxxxxxxxx 15872-32255 Costanzo [Page 4] EXPIRES IN SIX MONTHS September 3, 1998 The 0 has been chosen to signal the start of the field for ease of encoding. (The bit generator can simply encode one more bit than is significant in the binary representation of the excess.) The stop values are useful in the encoding to prevent out of range values for the lengths and offsets, as well as shortening some codes by one bit. The worst case compression using this scheme is a 1/8 increase in size of the encoded data. (One zero bit followed by 8 character bits). After the character encoding, the worst case ratio is 3/2 to the original data. The minimum copy length of 3 has been chosen because the worst case copy length and offset is 3 bits (3) and 19 bits (32255) for a total of 22 bits to encode a 3 character string (24 bits). 3.2.1 Sample Decoder As mentioned previously, the compression is defined by the decoder. Any encoder that produced output that is correctly decoded is by definition correct. The following is an implementation of the decoder, written more for clarity and as much portability as possible, rather than for maximum speed. When optimized for a specific environment, it will run significantly faster. /* LZJU 90 Decoding program */ /* Written By Robert Jung and Robert Ullmann, 1990 and 1991. */ /* This code is NOT COPYRIGHT, not protected. It is in the true Public Domain. */ #include <stdio.h> #include <string.h> typedef unsigned char uchar; typedef unsigned int uint; #define N 32255 #define THRESHOLD 3 #define STRTP 9 #define STEPP 1 #define STOPP 14 #define STRTL 0 #define STEPL 1 #define STOPL 7 Costanzo [Page 5] EXPIRES IN SIX MONTHS September 3, 1998 static FILE *in; static FILE *out; static int getbuf; static int getlen; static long in_count; static long out_count; static long crc; static long crctable[256]; static uchar xxcodes[] = "+-0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ\ abcdefghijklmnopqrstuvwxyz"; static uchar ddcodes[256]; static uchar text[N]; #define CRCPOLY 0xEDB88320 #define CRC_MASK 0xFFFFFFFF #define UPDATE_CRC(crc, c) \ crc = crctable[((uchar)(crc) ^ (uchar)(c)) & 0xFF] \ ^ (crc >> 8) #define START_RECD "* LZJU90" void MakeCrctable() /* Initialize CRC-32 table */ { uint i, j; long r; for (i = 0; i <= 255; i++) { r = i; for (j = 8; j > 0; j--) { if (r & 1) r = (r >> 1) ^ CRCPOLY; else r >>= 1; } crctable[i] = r; } } int GetXX() /* Get xxcode and translate */ { int c; do { if ((c = fgetc(in)) == EOF) c = 0; } while (c == '\n'); in_count++; return ddcodes[c]; } Costanzo [Page 6] EXPIRES IN SIX MONTHS September 3, 1998 int GetBit() /* Get one bit from input buffer */ { int c; while (getlen <= 0) { c = GetXX(); getbuf |= c << (10-getlen); getlen += 6; } c = (getbuf & 0x8000) != 0; getbuf <<= 1; getbuf &= 0xFFFF; getlen--; return(c); } int GetBits(int len) /* Get len bits */ { int c; while (getlen <= 10) { c = GetXX(); getbuf |= c << (10-getlen); getlen += 6; } if (getlen < len) { c = (uint)getbuf >> (16-len); getbuf = GetXX(); c |= getbuf >> (6+getlen-len); getbuf <<= (10+len-getlen); getbuf &= 0xFFFF; getlen -= len - 6; } else { c = (uint)getbuf >> (16-len); getbuf <<= len; getbuf &= 0xFFFF; getlen -= len; } return(c); } int DecodePosition() /* Decode offset position pointer */ { int c; int width; int plus; int pwr; plus = 0; pwr = 1 << STRTP; for (width = STRTP; width < STOPP; width += STEPP) { c = GetBit(); if (c == 0) Costanzo [Page 7] EXPIRES IN SIX MONTHS September 3, 1998 break; plus += pwr; pwr <<= 1; } if (width != 0) c = GetBits(width); c += plus; return(c); } int DecodeLength() /* Decode code length */ { int c; int width; int plus; int pwr; plus = 0; pwr = 1 << STRTL; for (width = STRTL; width < STOPL; width += STEPL) { c = GetBit(); if (c == 0) break; plus += pwr; pwr <<= 1; } if (width != 0) c = GetBits(width); c += plus; return(c); } void InitCodes() /* Initialize decode table */ { int i; for (i = 0; i < 256; i++) ddcodes[i] = 0; for (i = 0; i < 64; i++) ddcodes[xxcodes[i]] = i; return; } main(int ac, char **av) /* main program */ { int r; int j, k; int c; int pos; char buf[80]; char name[3]; long num, bytes; Costanzo [Page 8] EXPIRES IN SIX MONTHS September 3, 1998 if (ac < 3) { fprintf(stderr, "usage: judecode in out\n"); return(1); } in = fopen(av[1], "r"); if (!in){ fprintf(stderr, "Can't open %s\n", av[1]); return(1); } out = fopen(av[2], "wb"); if (!out) { fprintf(stderr, "Can't open %s\n", av[2]); fclose(in); return(1); } while (1) { if (fgets(buf, sizeof(buf), in) == NULL) { fprintf(stderr, "Unexpected EOF\n"); return(1); } if (strncmp(buf, START_RECD, strlen(START_RECD)) == 0) break; } in_count = 0; out_count = 0; getbuf = 0; getlen = 0; InitCodes(); MakeCrctable(); crc = CRC_MASK; r = 0; while (feof(in) == 0) { c = DecodeLength(); if (c == 0) { c = GetBits(8); UPDATE_CRC(crc, c); out_count++; text[r] = c; fputc(c, out); if (++r >= N) r = 0; } Costanzo [Page 9] EXPIRES IN SIX MONTHS September 3, 1998 else { pos = DecodePosition(); if (pos == 0) break; pos--; j = c + THRESHOLD - 1; pos = r - pos - 1; if (pos < 0) pos += N; for (k = 0; k < j; k++) { c = text[pos]; text[r] = c; UPDATE_CRC(crc, c); out_count++; fputc(c, out); if (++r >= N) r = 0; if (++pos >= N) pos = 0; } } } fgetc(in); /* skip newline */ if (fscanf(in, "* %ld %lX", &bytes, &num) != 2) { fprintf(stderr, "CRC record not found\n"); return(1); } else if (crc != num) { fprintf(stderr, "CRC error, expected %lX, found %lX\n", crc, num); return(1); } else if (bytes != out_count) { fprintf(stderr, "File size error, expected %lu, found %lu\n", bytes, out_count); return(1); } else fprintf(stderr, "File decoded to %lu bytes correctly\n", out_count); Costanzo [Page 10]
EXPIRES IN SIX MONTHS September 3, 1998 fclose(in); fclose(out); return(0); } 3.2.2 An Example of an Encoder Many algorithms are possible for the encoder, with different tradeoffs between speed, size, and complexity. The following is an example program which is fairly efficient; more sophisticated implementations will run much faster, and produce somewhat better compression. This example also shows that the encoder need not use the entire window available. Not using the full window costs a small amount of compression, but can greatly increase the speed of some algorithms. /* LZJU 90 Encoding program */ /* Written By Robert Jung and Robert Ullmann, 1990 and 1991. */ /* This code is NOT COPYRIGHT, not protected. It is in the true Public Domain. */ #include <stdio.h> typedef unsigned char uchar; typedef unsigned int uint; #define N 24000 /* Size of window buffer */ #define F 256 /* Size of look-ahead buffer */ #define THRESHOLD 3 #define K 16384 /* Size of hash table */ #define STRTP 9 #define STEPP 1 #define STOPP 14 #define STRTL 0 #define STEPL 1 #define STOPL 7 #define CHARSLINE 78 static FILE *in; static FILE *out; static int putlen; static int putbuf; static int char_ct; static long in_count; static long out_count; Costanzo [Page 11]
EXPIRES IN SIX MONTHS September 3, 1998 static long crc; static long crctable[256]; static uchar xxcodes[] = "+-0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ\ abcdefghijklmnopqrstuvwxyz"; uchar window_text[N + F + 1]; /* text contains window, plus 1st F of window again (for comparisons) */ uint hash_table[K]; /* table of pointers into the text */ #define CRCPOLY 0xEDB88320 #define CRC_MASK 0xFFFFFFFF #define UPDATE_CRC(crc, c) \ crc = crctable[((uchar)(crc) ^ (uchar)(c)) & 0xFF] \ ^ (crc >> 8) void MakeCrctable() /* Initialize CRC-32 table */ { uint i, j; long r; for (i = 0; i <= 255; i++) { r = i; for (j = 8; j > 0; j--) { if (r & 1) r = (r >> 1) ^ CRCPOLY; else r >>= 1; } crctable[i] = r; } } void PutXX(int c) /* Translate and put xxcode */ { c = xxcodes[c & 0x3F]; if (++char_ct > CHARSLINE) { char_ct = 1; fputc('\n', out); } fputc(c, out); out_count++; } Costanzo [Page 12]
EXPIRES IN SIX MONTHS September 3, 1998 void PutBits(int c, int len) /* Put rightmost "len" bits of "c" */ { c <<= 16 - len; c &= 0xFFFF; putbuf |= (uint) c >> putlen; c <<= 16 - putlen; c &= 0xFFFF; putlen += len; while (putlen >= 6) { PutXX(putbuf >> 10); putlen -= 6; putbuf <<= 6; putbuf &= 0xFFFF; putbuf |= (uint) c >> 10; c = 0; } } void EncodePosition(int ch) /* Encode offset position pointer */ { int width; int prefix; int pwr; pwr = 1 << STRTP; for (width = STRTP; ch >= pwr; width += STEPP, pwr <<= 1) ch -= pwr; if ((prefix = width - STRTP) != 0) PutBits(0xffff, prefix); if (width < STOPP) width++; /* else if (width > STOPP) abort(); do nothing */ PutBits(ch, width); } void EncodeLength(int ch) /* Encode code length */ { int width; int prefix; int pwr; pwr = 1 << STRTL; for (width = STRTL; ch >= pwr; width += STEPL, pwr <<= 1) ch -= pwr; if ((prefix = width - STRTL) != 0) PutBits(0xffff, prefix); if (width < STOPL) width++; /* else if (width > STOPL) abort(); do nothing */ PutBits(ch, width); } Costanzo [Page 13]
EXPIRES IN SIX MONTHS September 3, 1998 main(int ac, char **av) /* main program */ { uint r, s, i, c; uchar *p, *rp; int match_position; int match_length; int len; uint hash, h; if (ac < 3) { fprintf(stderr, "usage: juencode in out\n"); return(1); } in = fopen(av[1], "rb"); if (!in) { fprintf(stderr, "Can't open %s\n", av[1]); return(1); } out = fopen(av[2], "w"); if (!out) { fprintf(stderr, "Can't open %s\n", av[2]); fclose(in); return(1); } char_ct = 0; in_count = 0; out_count = 0; putbuf = 0; putlen = 0; hash = 0; MakeCrctable(); crc = CRC_MASK; fprintf(out, "* LZJU90 %s\n", av[1]); /* The hash table inititialization is somewhat arbitrary */ for (i = 0; i < K; i++) hash_table[i] = i % N; r = 0; s = 0; /* Fill lookahead buffer */ for (len = 0; len < F && (c = fgetc(in)) != EOF; len++) { UPDATE_CRC(crc, c); in_count++; window_text[s++] = c; } Costanzo [Page 14]
EXPIRES IN SIX MONTHS September 3, 1998 while (len > 0) { /* look for match in window at hash position */ h = ((((window_text[r] << 5) ^ window_text[r+1]) << 5) ^ window_text[r+2]); p = window_text + hash_table[h % K]; rp = window_text + r; for (i = 0, match_length = 0; i < F; i++) { if (*p++ != *rp++) break; match_length++; } match_position = r - hash_table[h % K]; if (match_position <= 0) match_position += N; if (match_position > N - F - 2) match_length = 0; if (match_position > in_count - len - 2) match_length = 0; /* ! :-) */ if (match_length > len) match_length = len; if (match_length < THRESHOLD) { EncodeLength(0); PutBits(window_text[r], 8); match_length = 1; } else { EncodeLength(match_length - THRESHOLD + 1); EncodePosition(match_position); } for (i = 0; i < match_length && (c = fgetc(in)) != EOF; i++) { UPDATE_CRC(crc, c); in_count++; window_text[s] = c; if (s < F - 1) window_text [s + N] = c; if (++s > N - 1) s = 0; hash = ((hash << 5) ^ window_text[r]); if (r > 1) hash_table[hash % K] = r - 2; if (++r > N - 1) r = 0; } while (i++ < match_length) { if (++s > N - 1) s = 0; hash = ((hash << 5) ^ window_text[r]); if (r > 1) hash_table[hash % K] = r - 2; if (++r > N - 1 ) r = 0; len--; } } Costanzo [Page 15]
EXPIRES IN SIX MONTHS September 3, 1998 /* end compression indicator */ EncodeLength(1); EncodePosition(0); PutBits(0, 7); fprintf(out, "\n* %lu %08lX\n", in_count, crc); fprintf(stderr, "Encoded %lu bytes to %lu symbols\n", in_count, out_count); fclose(in); fclose(out); return(0); } 3.3.1 Example of a MIME LZJU90 Compressed Object The following is an example of a MIME LZJU90 compressed object. Content-Type: text/plain; charset="utf-8" Content-Transfer-Encoding: LZJU90 * LZJU90 example 8-mBtWA7WBVZ3dEBtnCNdU2WkE4owW+l4kkaApW+o4Ir0k33Ao4IE4kk bYtk1XY618NnCQl+OHQ61d+J8FZBVVCVdClZ2-LUI0v+I4EraItasHbG VVg7c8tdk2lCBtr3U86FZANVCdnAcUCNcAcbCMUCdicx0+u4wEETHcRM 7tZ2-6Btr268-Eh3cUAlmBth2-IUo3As42laIE2Ao4Yq4G-cHHT-wCEU 6tjBtnAci-I++ * 190 081E2601 4. Security Consideration The security (or lack) is responsibility of the application domain controlling the decoder of the LZJU90 object. 5. References [1] Costanzo, A. Robinson, D. and R. Ullmann, "Encoding Header Field for Internet Messages", RFC 1505, AKC Consulting, Prime Computer, Inc., August 1993. [2] International Organization for Standardization, Information Technology -- Universal Coded Character Set (UCS). ISO/IEC 10646-1:1993, June 1993. [3] International Organization for Standardization, Information Technology -- Universal Coded Character Set (UCS). ISO/IEC 10646-1: 1993/AMD.2: 1996 (E) Costanzo [Page 16]
EXPIRES IN SIX MONTHS September 3, 1998 6. Acknowledgments The author would like to thank Robert Jung, David Robinson and Robert Ullmann for their past contributions to this work. 7. Author's Address Al Costanzo AKC Computer Services Corp. P.O. Box 4031 Roselle Park, NJ 07204-0531 Phone: +1 908 298 9000 Email: AL@AKC.COM Costanzo [Page 17]