class LzssCodec {

	public static void compress(OutputStream dst, InputStream src) throws IOException {
		/* Encoding state, mostly trees but some current match stuff */
		EncodeState sp;

		int i, c, len, r, s, lastMatchLength;
		ByteBuffer codeBuf = ByteBuffer.allocate(17);
		byte mask;

		/* initialize trees */
		sp = new EncodeState();

		/*
		 * code_buf[1..16] saves eight units of code, and code_buf[0] works as
		 * eight flags, "1" representing that the unit is an unencoded letter (1
		 * byte), "" a position-and-length pair (2 bytes). Thus, either units
		 * require at most 16 bytes of code.
		 */
		codeBuf.put((byte) 0);
		mask = 1;

		/* Clear the buffer with any character that will appear often. */
		s = 0;
		r = N - F;

		/* Read F bytes into the last F bytes of the buffer */
		for (len = 0; len < F; len++) {
			int b = src.read();
			if (b == -1) {
				break;
			}
			sp.textBuf.put(r + len, (byte) b);
		}
		if (len == 0) {
			return; /* text of size zero */
		}
		/*
		 * Insert the F strings, each of which begins with one or more 'space'
		 * characters. Note the order in which these strings are inserted. This
		 * way degenerate trees will be less likely to occur.
		 */
		for (i = 1; i <= F; i++) {
			sp.insertNode(r - i);
		}

		/*
		 * Finally, insert the whole string just read. The global variables
		 * match_length and match_position are set.
		 */
		sp.insertNode(r);
		do {
			/* match_length may be spuriously long near the end of text. */
			if (sp.matchLength > len) {
				sp.matchLength = len;
			}
			if (sp.matchLength <= THRESHOLD) {
				sp.matchLength = 1; /* Not long enough match. Send one byte. */
				codeBuf.put(0, (byte) (codeBuf.get(0) | mask));
				codeBuf.put(sp.textBuf.get(r));
			}
			else {
				/* Send position and length pair. Note match_length > THRESHOLD. */
				codeBuf.put((byte) sp.matchPosition);
				codeBuf.put((byte) //
				(/**/((sp.matchPosition >> 4) & 0xF0) //
					| (sp.matchLength - (THRESHOLD + 1))/**/) //
				);
			}
			if ((mask <<= 1) == 0) { /* Shift mask left one bit. */
				/* Send at most 8 units of code together */
				dst.write(codeBuf.array(), 0, codeBuf.position());
				codeBuf.clear();
				codeBuf.put((byte) 0);
				mask = 1;
			}
			lastMatchLength = sp.matchLength;
			for (i = 0; i < lastMatchLength; i++) {
				c = src.read();
				if (c == -1) {
					break;
				}
				sp.deleteNode(s); /* Delete old strings and */
				sp.textBuf.put(s, (byte) c); /* read new bytes */

				/**
				 * If the position is near the end of the buffer, extend the
				 * buffer to make string comparison easier.
				 */
				if (s < F - 1) {
					sp.textBuf.put(s + N, (byte) c);
				}

				/* Since this is a ring buffer, increment the position module N. */
				s = (s + 1) & (N - 1);
				r = (r + 1) & (N - 1);

				/* Register the string in text_buf[r..r+F-1] */
				sp.insertNode(r);
			}
			while (i++ < lastMatchLength) {
				sp.deleteNode(s);

				/* After the end of text, no need to read, */
				s = (s + 1) & (N - 1);
				r = (r + 1) & (N - 1);
				/* but buffer may not be empty. */
				if (--len != 0) {
					sp.insertNode(r);
				}
			}
		}
		while (len > 0); /* until length of string to be processed is zero */

		if (codeBuf.position() > 1) { /* Send remaining code. */
			dst.write(codeBuf.array(), 0, codeBuf.position());
		}

		dst.flush();
	}

}