KDE 3.5 API Reference kviewshell
ZPCodec Class Reference
Performs ZP-Coder encoding and decoding. More...
#include <ZPCodec.h>
Classes | |
| struct | Table |
Public Member Functions | |
| void | newtable (ZPCodec::Table *table) |
| BitContext | state (float prob1) |
| ~ZPCodec () | |
ZPCodec.h | |
Files #"ZPCodec.h"# and #"ZPCodec.cpp"# implement a fast binary adaptive quasi-arithmetic coder named ZP-Coder. Because of its speed and convenience, the ZP-Coder is used in several parts of the DjVu reference library (See {BSByteStream.h}, {JB2Image.h}, {IW44Image.h}). The following comments avoid the theory (see the historical remarks for useful pointers) and concentrate on the user perspective on the ZP-Coder. { Introduction} --- Encoding consists of transforming a sequence of {message bits} into a sequence of {code bits}. Decoding consists of retrieving the message bits using only the code bits. We can make the code smaller than the message as soon as we can predict a message bit on the basis of a {coding context} composed of previously encoded or decoded bits. If the prediction is always correct, we do not even need to encode the message bit. If the prediction is totally unreliable, we need to generate one code bit in order to unambiguously specify the message bit. In other words, the more reliable the prediction, the more compression we get. The ZP-Coder handles prediction by means of {context variables} (see {BitContext}). There must be a context variable for each possible combination of context bits. Both the encoder and the decoder use same context variable for coding each message bit. For instance, we can code a binary image by successively coding all the pixels (the message bits) in row and column order. It is reasonable to assume that each pixel can be reasonably well predicted by looking at a few (say 10) neighboring pixels located above and to the left of the current pixel. Since these 10 pixels make 1024 combinations, we need 1024 context variables. Each pixel is encoded using the context variable corresponding to the values of the 10 neighboring pixels. Each pixel will be decoded by specifying the same context variable corresponding to the values of these 10 pixels. This is possible because these 10 pixels (located above and to the left) have already been decoded and therefore are known by the decoder program. The context variables are initially set to zero, which mean that we do not know yet how to predict the current message bit on the basis of the context bits. While coding the message bits, the ZP-Coder automatically estimates the frequencies of #0s and #1s coded using each context variable. These frequencies actually provide a prediction (the most probable bit value) and an estimation of the prediction reliability (how often the prediction was correct in the past). All this statistical information is stored into the context variable after coding each bit. In other words, the more we code bits within a particular context, the better the ZP-Coder adapts its prediction model, and the more compression we can obtain. All this adaptation works indeed because both the encoder program and the decoder program are always synchronized. Both the encoder and the decoder see the same message bits encoded (or decoded) with the same context variables. Both the encoder and the decoder apply the same rules to update the context variables and improve the predictors. Both the encoder and the decoder programs use the same predictors for any given message bit. The decoder could not work if this was not the case. Just before encoding a message bit, all the context variables in the encoder program contain certain values. Just before decoding this message bit, all the context variables in the decoder program must contain the same values as for the encoder program. This is guaranteed as long as each prediction only depends on already coded bits: {the coding context, on which the each prediction is based, must be composed of message bits which have already been coded. } { Usage} --- Once you know how to organize the predictions (i.e. which coding context to use, how many context variables to initialize, etc.), using the ZP-Coder is straightforward (see {ZPCodec Examples}): {itemize} The {encoder program} allocates context variables and initializes them to zero. It then constructs a {ZPCodec} object for encoding. For each message bit, the encoder program retrieves the context bits, selects a context variable on the basis of the context bits and calls member function {ZPCodec::encoder} with the message bit and a reference to the context variable. The {decoder program} allocates context variables and initializes them to zero. It then constructs a {ZPCodec} object for decoding. For each message bit, the decoder program retrieves the context bits, selects a context variable on the basis of the context bits and calls member function {ZPCodec::decoder} with a reference to the context variable. This function returns the message bit. {itemize} Functions encoder# and decoder# only require a few machine cycles to perform two essential tasks, namely {coding} and {context adaptation}. Function decoder# often returns after two arithmetic operations only. To make your program fast, you just need to feed message bits and context variables fast enough. { History} --- The ZP-Coder is similar in function and performance to the seminal Q-Coder (Pennebaker, Mitchell, Langdon, Arps, IBM J. Res Dev. 32, 1988). An improved version of the Q-Coder, named QM-Coder, has been described in certain parts of the JPEG standard. Unfortunate patent policies have made these coders very difficult to use in general purpose applications. The Z-Coder is constructed using a new approach based on an extension of the Golomb codes (Bottou, Howard, Bengio, IEEE DCC 98, 1998 [DjVu]{http://www.research.att.com/~leonb/DJVU/bottou-howard-bengio/} [PostScript]{http://www.research.att.com/~leonb/PS/bottou-howard-bengio.ps.gz}) This new approach does not infringe the QM-Coder patents. Unfortunately the Z-Coder is dangerously close to the patented Arithmetic MEL Coder. Therefore we wrote the ZP-Coder (pronounce Zee-Prime Coder) which we believe is clear of legal problems. Needless to say, AT&T has patents pending for both the Z-Coder and the ZP-Coder, licenced to LizardTech. The good news however is that we can grant a license to use the ZP-Coder in ``free software'' without further complication. See the Copyright for more information. Binary adaptive quasi-arithmetic coder.
| |
| int | decoder (void) |
| int | decoder (BitContext &ctx) |
| int | decoder_nolearn (BitContext &ctx) |
| void | encoder (int bit) |
| void | encoder (int bit, BitContext &ctx) |
| void | encoder_nolearn (int pix, BitContext &ctx) |
| int | IWdecoder (void) |
| void | IWencoder (const bool bit) |
Static Public Member Functions | |
| static GP< ZPCodec > | create (GP< ByteStream > gbs, const bool encoding, const bool djvucompat=false) |
Protected Member Functions | |
| int | decode_sub (BitContext &ctx, unsigned int z) |
| int | decode_sub_nolearn (int mps, unsigned int z) |
| int | decode_sub_simple (int mps, unsigned int z) |
| void | dinit (void) |
| void | eflush (void) |
| void | einit (void) |
| void | encode_lps (BitContext &ctx, unsigned int z) |
| void | encode_lps_nolearn (unsigned int z) |
| void | encode_lps_simple (unsigned int z) |
| void | encode_mps (BitContext &ctx, unsigned int z) |
| void | encode_mps_nolearn (unsigned int z) |
| void | encode_mps_simple (unsigned int z) |
| int | ffz (unsigned int x) |
| void | outbit (int bit) |
| void | preload (void) |
| void | zemit (int b) |
| ZPCodec (GP< ByteStream > gbs, const bool encoding, const bool djvucompat=false) | |
Protected Attributes | |
| unsigned int | a |
| ByteStream * | bs |
| unsigned int | buffer |
| unsigned char | byte |
| unsigned int | code |
| unsigned char | delay |
| BitContext | dn [256] |
| const bool | encoding |
| unsigned int | fence |
| char | ffzt [256] |
| GP< ByteStream > | gbs |
| unsigned int | m [256] |
| unsigned int | nrun |
| unsigned int | p [256] |
| unsigned char | scount |
| unsigned int | subend |
| BitContext | up [256] |
Detailed Description
Performs ZP-Coder encoding and decoding.A ZPCodec object must either constructed for encoding or for decoding. The ZPCodec object is connected with a {ByteStream} object specified at construction time. A ZPCodec object constructed for decoding reads code bits from the ByteStream and returns a message bit whenever function {decoder} is called. A ZPCodec constructed for encoding processes the message bits provided by function {encoder} and writes the corresponding code bits to ByteStream bs#.
You should never directly access a ByteStream object connected to a valid ZPCodec object. The most direct way to access the ByteStream object consists of using the "pass-thru" versions of functions {encoder} and {decoder}.
The ByteStream object can be accessed again after the destruction of the ZPCodec object. Note that the encoder always flushes its internal buffers and writes a few final code bytes when the ZPCodec object is destroyed. Note also that the decoder often reads a few bytes beyond the last code byte written by the encoder. This lag means that you must reposition the ByteStream after the destruction of the ZPCodec object and before re-using the ByteStream object (see {IFFByteStream}.)
Please note also that the decoder has no way to reliably indicate the end of the message bit sequence. The content of the message must be designed in a way which indicates when to stop decoding. Simple ways to achieve this consists of announcing the message length at the beginning (like a pascal style string), or of defining a termination code (like a null terminated string).
Definition at line 245 of file ZPCodec.h.
Constructor & Destructor Documentation
| ZPCodec::ZPCodec | ( | GP< ByteStream > | gbs, | |
| const bool | encoding, | |||
| const bool | djvucompat = false | |||
| ) | [protected] |
Definition at line 682 of file ZPCodec.cpp.
| ZPCodec::~ZPCodec | ( | ) |
Member Function Documentation
| GP< ZPCodec > ZPCodec::create | ( | GP< ByteStream > | gbs, | |
| const bool | encoding, | |||
| const bool | djvucompat = false | |||
| ) | [static] |
Constructs a ZP-Coder.
If argument encoding# is zero, the ZP-Coder object will read code bits from the ByteStream bs# and return a message bit whenever function decoder# is called. If flag encoding# is set the ZP-Coder object will process the message bits provided by function encoder# and write code bits to ByteStream bs#. Optional flag djvucompat# selects a slightly less efficient adaptation table which is used by the DjVu project. This is required in order to ensure the bitstream compatibility. You should not use this flag unless you want to decode JB2, IW44 or BZZ encoded data.
Definition at line 714 of file ZPCodec.cpp.
| int ZPCodec::decode_sub | ( | BitContext & | ctx, | |
| unsigned int | z | |||
| ) | [protected] |
Definition at line 805 of file ZPCodec.cpp.
| int ZPCodec::decode_sub_nolearn | ( | int | mps, | |
| unsigned int | z | |||
| ) | [protected] |
Definition at line 910 of file ZPCodec.cpp.
| int ZPCodec::decode_sub_simple | ( | int | mps, | |
| unsigned int | z | |||
| ) | [protected] |
Definition at line 866 of file ZPCodec.cpp.
| int ZPCodec::decoder | ( | void | ) | [inline] |
| int ZPCodec::decoder | ( | BitContext & | ctx | ) | [inline] |
| int ZPCodec::decoder_nolearn | ( | BitContext & | ctx | ) | [inline] |
| void ZPCodec::dinit | ( | void | ) | [protected] |
| void ZPCodec::eflush | ( | void | ) | [protected] |
Definition at line 1054 of file ZPCodec.cpp.
| void ZPCodec::einit | ( | void | ) | [protected] |
| void ZPCodec::encode_lps | ( | BitContext & | ctx, | |
| unsigned int | z | |||
| ) | [protected] |
Definition at line 1108 of file ZPCodec.cpp.
| void ZPCodec::encode_lps_nolearn | ( | unsigned int | z | ) | [protected] |
Definition at line 1192 of file ZPCodec.cpp.
| void ZPCodec::encode_lps_simple | ( | unsigned int | z | ) | [protected] |
Definition at line 1151 of file ZPCodec.cpp.
| void ZPCodec::encode_mps | ( | BitContext & | ctx, | |
| unsigned int | z | |||
| ) | [protected] |
Definition at line 1080 of file ZPCodec.cpp.
| void ZPCodec::encode_mps_nolearn | ( | unsigned int | z | ) | [protected] |
Definition at line 1168 of file ZPCodec.cpp.
| void ZPCodec::encode_mps_simple | ( | unsigned int | z | ) | [protected] |
Definition at line 1137 of file ZPCodec.cpp.
| void ZPCodec::encoder | ( | int | bit | ) | [inline] |
| void ZPCodec::encoder | ( | int | bit, | |
| BitContext & | ctx | |||
| ) | [inline] |
| void ZPCodec::encoder_nolearn | ( | int | pix, | |
| BitContext & | ctx | |||
| ) | [inline] |
| int ZPCodec::ffz | ( | unsigned int | x | ) | [inline, protected] |
Definition at line 775 of file ZPCodec.cpp.
| void ZPCodec::newtable | ( | ZPCodec::Table * | table | ) |
Definition at line 1229 of file ZPCodec.cpp.
| void ZPCodec::outbit | ( | int | bit | ) | [protected] |
Definition at line 987 of file ZPCodec.cpp.
| void ZPCodec::preload | ( | void | ) | [protected] |
Definition at line 758 of file ZPCodec.cpp.
| BitContext ZPCodec::state | ( | float | prob1 | ) |
Definition at line 1260 of file ZPCodec.cpp.
| void ZPCodec::zemit | ( | int | b | ) | [protected] |
Definition at line 1012 of file ZPCodec.cpp.
Member Data Documentation
unsigned int ZPCodec::a [protected] |
ByteStream* ZPCodec::bs [protected] |
unsigned int ZPCodec::buffer [protected] |
unsigned char ZPCodec::byte [protected] |
unsigned int ZPCodec::code [protected] |
unsigned char ZPCodec::delay [protected] |
BitContext ZPCodec::dn[256] [protected] |
const bool ZPCodec::encoding [protected] |
unsigned int ZPCodec::fence [protected] |
char ZPCodec::ffzt[256] [protected] |
GP<ByteStream> ZPCodec::gbs [protected] |
unsigned int ZPCodec::m[256] [protected] |
unsigned int ZPCodec::nrun [protected] |
unsigned int ZPCodec::p[256] [protected] |
unsigned char ZPCodec::scount [protected] |
unsigned int ZPCodec::subend [protected] |
BitContext ZPCodec::up[256] [protected] |
The documentation for this class was generated from the following files:
