Mercurial > thymian

comparison 3rdparty/compressor/fpaq0.cpp @ 0:a4671277546c tip

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
created the repository for the thymian project
author ferencd
date Tue, 17 Aug 2021 11:19:54 +0200
parents
children
comparison
equal deleted inserted replaced
-1:000000000000 0:a4671277546c
1 // fpaq0 - Stationary order 0 file compressor.
2 // (C) 2004, Matt Mahoney under GPL, http://www.gnu.org/licenses/gpl.txt
3 // To compile: g++ -O fpaq0.cpp
4
5 #include <cstdio>
6 #include <cstdlib>
7 #include <cstring>
8 #include <ctime>
9 #include <cassert>
10 #include <iostream>
11 #include "fpaq0.h"
12
13 using namespace std;
14
15
16 // Constructor
17 Encoder::Encoder(Mode m, Archive &parchive): predictor(), mode(m), archive(parchive), x1(0),
18 x2(0xffffffff), x(0)
19 {
20
21 // In DECOMPRESS mode, initialize x to the first 4 bytes of the archive
22 if (mode==DECOMPRESS)
23 {
24 for (int i=0; i<4; ++i)
25 {
26 int c = archive.getc();
27 if (c==EOF) c=0;
28 x=(x<<8)+(c&0xff);
29 }
30 }
31 }
32
33 /* encode(y) -- Encode bit y by splitting the range [x1, x2] in proportion
34 to P(1) and P(0) as given by the predictor and narrowing to the appropriate
35 subrange. Output leading bytes of the range as they become known. */
36
37 inline void Encoder::encode(int y)
38 {
39
40 // Update the range
41 const uint32_t xmid = x1 + ((x2-x1) >> 12) * predictor.p();
42 assert(xmid >= x1 && xmid < x2);
43 if (y)
44 x2=xmid;
45 else
46 x1=xmid+1;
47 predictor.update(y);
48
49 // Shift equal MSB's out
50 while ( ((x1^x2) & 0xff000000) == 0)
51 {
52 archive.putc(x2>>24);
53 x1 <<= 8;
54 x2 = (x2<<8) + 255;
55 }
56 }
57
58 /* Decode one bit from the archive, splitting [x1, x2] as in the encoder
59 and returning 1 or 0 depending on which subrange the archive point x is in.
60 */
61 inline int Encoder::decode()
62 {
63
64 // Update the range
65 const uint32_t xmid = x1 + ((x2-x1) >> 12) * predictor.p();
66 assert(xmid >= x1 && xmid < x2);
67 int y=0;
68 if (x<=xmid)
69 {
70 y=1;
71 x2=xmid;
72 }
73 else
74 x1=xmid+1;
75 predictor.update(y);
76
77 // Shift equal MSB's out
78 while (((x1^x2)&0xff000000)==0)
79 {
80 x1 <<= 8;
81 x2=(x2<<8)+255;
82 int c = archive.getc();
83 if (c==EOF) c=0;
84 x = (x<<8) + c;
85 }
86 return y;
87 }
88
89 // Should be called when there is no more to compress
90 void Encoder::flush()
91 {
92
93 // In COMPRESS mode, write out the remaining bytes of x, x1 < x < x2
94 if (mode==COMPRESS)
95 {
96 while (((x1^x2)&0xff000000)==0)
97 {
98 archive.putc(x2>>24);
99 x1 <<= 8;
100 x2 = (x2<<8) + 255;
101 }
102 archive.putc(x2>>24); // First unequal byte
103 }
104 }
105
106 std::vector<unsigned char> compress(const std::string& s)
107 {
108 Archive a;
109 Encoder e(COMPRESS, a);
110 char c = 0;
111 size_t idx = 0;
112 while ( idx < s.length() )
113 {
114 c = s[idx];
115 e.encode(0);
116 for (int i=7; i>=0; --i)
117 {
118 e.encode((c>>i)&1);
119 }
120 idx ++;
121 }
122 e.encode(1); // EOF code
123 e.flush();
124
125 return a.data();
126 }
127
128 std::string decompress(const std::vector<unsigned char>& v)
129 {
130 Archive a(v);
131 std::string result;
132 Encoder e(DECOMPRESS, a);
133 while (!e.decode())
134 {
135 int c=1;
136 while (c<256)
137 c += c + e.decode();
138
139 char temp[2] = {0};
140 temp[0] = c - 256;
141
142 result += temp;
143 }
144 return result;
145 }
146
147 int Predictor::p() const
148 {
149 return 4096*(ct[cxt][1]+1)/(ct[cxt][0]+ct[cxt][1]+2);
150 }
151
152 void Predictor::update(int y)
153 {
154 if (++ct[cxt][y] > 65534)
155 {
156 ct[cxt][0] >>= 1;
157 ct[cxt][1] >>= 1;
158 }
159 if ((cxt+=cxt+y) >= 512)
160 cxt=1;
161 }