|
ferencd@0
|
1 #ifndef FPAQ0
|
|
ferencd@0
|
2 #define FPAQ0
|
|
ferencd@0
|
3
|
|
ferencd@0
|
4 #include <vector>
|
|
ferencd@0
|
5 #include <string>
|
|
ferencd@0
|
6 #include <stdint.h>
|
|
ferencd@0
|
7
|
|
ferencd@0
|
8 #include <string.h>
|
|
ferencd@0
|
9
|
|
ferencd@0
|
10 class Archive
|
|
ferencd@0
|
11 {
|
|
ferencd@0
|
12 public:
|
|
ferencd@0
|
13
|
|
ferencd@0
|
14 Archive(const std::vector<unsigned char>& s) : content(s.begin(), s.end()), it(content.begin()) {}
|
|
ferencd@0
|
15 Archive() : content(), it(content.begin()) {}
|
|
ferencd@0
|
16
|
|
ferencd@0
|
17 int getc() const
|
|
ferencd@0
|
18 {
|
|
ferencd@0
|
19 if(it == content.end())
|
|
ferencd@0
|
20 {
|
|
ferencd@0
|
21 return EOF;
|
|
ferencd@0
|
22 }
|
|
ferencd@0
|
23 int v = static_cast<int> (*it);
|
|
ferencd@0
|
24 ++ it;
|
|
ferencd@0
|
25 return v;
|
|
ferencd@0
|
26 }
|
|
ferencd@0
|
27
|
|
ferencd@0
|
28 void putc(char c)
|
|
ferencd@0
|
29 {
|
|
ferencd@0
|
30 content.push_back(c);
|
|
ferencd@0
|
31 }
|
|
ferencd@0
|
32
|
|
ferencd@0
|
33 std::vector<unsigned char> data() const
|
|
ferencd@0
|
34 {
|
|
ferencd@0
|
35 return content;
|
|
ferencd@0
|
36 }
|
|
ferencd@0
|
37
|
|
ferencd@0
|
38 private:
|
|
ferencd@0
|
39 std::vector<unsigned char> content; // Compressed data file
|
|
ferencd@0
|
40 mutable std::vector<unsigned char>::iterator it;
|
|
ferencd@0
|
41 };
|
|
ferencd@0
|
42
|
|
ferencd@0
|
43 //////////////////////////// Predictor /////////////////////////
|
|
ferencd@0
|
44
|
|
ferencd@0
|
45 /* A Predictor estimates the probability that the next bit of
|
|
ferencd@0
|
46 uncompressed data is 1. Methods:
|
|
ferencd@0
|
47 p() returns P(1) as a 12 bit number (0-4095).
|
|
ferencd@0
|
48 update(y) trains the predictor with the actual bit (0 or 1).
|
|
ferencd@0
|
49 */
|
|
ferencd@0
|
50
|
|
ferencd@0
|
51 class Predictor
|
|
ferencd@0
|
52 {
|
|
ferencd@0
|
53 int cxt; // Context: last 0-8 bits with a leading 1
|
|
ferencd@0
|
54 int ct[512][2]; // 0 and 1 counts in context cxt
|
|
ferencd@0
|
55 public:
|
|
ferencd@0
|
56 Predictor(): cxt(1)
|
|
ferencd@0
|
57 {
|
|
ferencd@0
|
58 memset(ct, 0, sizeof(ct));
|
|
ferencd@0
|
59 }
|
|
ferencd@0
|
60
|
|
ferencd@0
|
61 // Assume a stationary order 0 stream of 9-bit symbols
|
|
ferencd@0
|
62 int p() const;
|
|
ferencd@0
|
63
|
|
ferencd@0
|
64 void update(int y);
|
|
ferencd@0
|
65 };
|
|
ferencd@0
|
66
|
|
ferencd@0
|
67
|
|
ferencd@0
|
68 //////////////////////////// Encoder ////////////////////////////
|
|
ferencd@0
|
69
|
|
ferencd@0
|
70 /* An Encoder does arithmetic encoding. Methods:
|
|
ferencd@0
|
71 Encoder(COMPRESS, f) creates encoder for compression to archive f, which
|
|
ferencd@0
|
72 must be open past any header for writing in binary mode
|
|
ferencd@0
|
73 Encoder(DECOMPRESS, f) creates encoder for decompression from archive f,
|
|
ferencd@0
|
74 which must be open past any header for reading in binary mode
|
|
ferencd@0
|
75 encode(bit) in COMPRESS mode compresses bit to file f.
|
|
ferencd@0
|
76 decode() in DECOMPRESS mode returns the next decompressed bit from file f.
|
|
ferencd@0
|
77 flush() should be called when there is no more to compress.
|
|
ferencd@0
|
78 */
|
|
ferencd@0
|
79
|
|
ferencd@0
|
80 typedef enum {COMPRESS, DECOMPRESS} Mode;
|
|
ferencd@0
|
81 class Encoder
|
|
ferencd@0
|
82 {
|
|
ferencd@0
|
83 public:
|
|
ferencd@0
|
84 Encoder(Mode m, Archive& archive);
|
|
ferencd@0
|
85 void encode(int y); // Compress bit y
|
|
ferencd@0
|
86 int decode(); // Uncompress and return bit y
|
|
ferencd@0
|
87 void flush(); // Call when done compressing
|
|
ferencd@0
|
88 private:
|
|
ferencd@0
|
89 Predictor predictor;
|
|
ferencd@0
|
90 const Mode mode; // Compress or decompress?
|
|
ferencd@0
|
91 Archive& archive;
|
|
ferencd@0
|
92 uint32_t x1, x2; // Range, initially [0, 1), scaled by 2^32
|
|
ferencd@0
|
93 uint32_t x; // Last 4 input bytes of archive.
|
|
ferencd@0
|
94 };
|
|
ferencd@0
|
95
|
|
ferencd@0
|
96 std::vector<unsigned char> compress(const std::string& s);
|
|
ferencd@0
|
97
|
|
ferencd@0
|
98 std::string decompress(const std::vector<unsigned char>& v);
|
|
ferencd@0
|
99
|
|
ferencd@0
|
100 #endif // FPAQ0
|
|
ferencd@0
|
101
|
