Hello,
I've found somewhat interesting bug.
Steps to reproduce
1) take http://nishi.dreamhosters.com/u/fpaq0p.cpp
(the file attached)
2) note this line:
// Assume a stationary order 0 stream of 9-bit symbols
3) remove '\r'
cp fpaq0p.cpp fpaq0p.copy.cpp
tr -d '\015' < fpaq0p.copy.cpp > fpaq0p.cpp
4) now run indent like this
indent -linux fpaq0p.cpp
5) result, after the mentioned line:
// Assume a stationary order 0 stream of 9-bit symbols int P()
const {
return (p[cxt]);
} void update(int y) {
The beginning of function P() become a part of the comment.
Sincerely,
Eugene.
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define assert()
typedef unsigned long U32; // 32 bit type
#define PSCALE 4096
//////////////////////////// Predictor /////////////////////////
struct Predictor {
private:
int cxt; // Context: last 0-8 bits with a leading 1
unsigned short p[512]; // Probability of 1
public:
Predictor():cxt(1) {
for (int i = 0; i < 512; i++)
p[i] = PSCALE / 2;
}
// Assume a stationary order 0 stream of 9-bit symbols int P() const {
return (p[cxt]);
} void update(int y) {
if (y) {
p[cxt] += ((PSCALE - p[cxt]) >> 5);
} else {
p[cxt] -= (p[cxt] >> 5);
}
if ((cxt += (cxt + y)) >= 512)
cxt = 1;
}
};
//////////////////////////// Encoder ////////////////////////////
/* An Encoder does arithmetic encoding. Methods:
Encoder(COMPRESS, f) creates encoder for compression to archive f, which
must be open past any header for writing in binary mode
Encoder(DECOMPRESS, f) creates encoder for decompression from archive f,
which must be open past any header for reading in binary mode
encode(bit) in COMPRESS mode compresses bit to file f.
decode() in DECOMPRESS mode returns the next decompressed bit from file f.
flush() should be called when there is no more to compress.
*/
typedef enum { COMPRESS, DECOMPRESS } Mode;
class Encoder {
private:
Predictor predictor;
const Mode mode; // Compress or decompress?
FILE *archive; // Compressed data file
U32 x1, x2; // Range, initially [0, 1), scaled by 2^32
U32 x; // Last 4 input bytes of archive.
public:
Encoder(Mode m, FILE * f);
void encode(int y); // Compress bit y
int decode(); // Uncompress and return bit y
void flush(); // Call when done compressing
};
// Constructor
Encoder::Encoder(Mode m, FILE * f):predictor(), mode(m), archive(f), x1(0),
x2(0xffffffff), x(0)
{
// In DECOMPRESS mode, initialize x to the first 4 bytes of the archive
if (mode == DECOMPRESS) {
for (int i = 0; i < 4; ++i) {
int c = getc(archive);
if (c == EOF)
c = 0;
x = (x << 8) + c;
}
}
}
/* encode(y) -- Encode bit y by splitting the range [x1, x2] in proportion
to P(1) and P(0) as given by the predictor and narrowing to the appropriate
subrange. Output leading bytes of the range as they become known. */
inline void Encoder::encode(int y)
{
// Update the range
const U32 xmid = x1 + ((x2 - x1) >> 12) * predictor.P();
assert(xmid >= x1 && xmid < x2);
if (y)
x2 = xmid;
else
x1 = xmid + 1;
predictor.update(y);
// Shift equal MSB's out
while (((x1 ^ x2) & 0xff000000) == 0) {
putc(x2 >> 24, archive);
x1 <<= 8;
x2 = (x2 << 8) + 255;
}
}
/* Decode one bit from the archive, splitting [x1, x2] as in the encoder
and returning 1 or 0 depending on which subrange the archive point x is in.
*/
inline int Encoder::decode()
{
// Update the range
const U32 xmid = x1 + ((x2 - x1) >> 12) * predictor.P();
assert(xmid >= x1 && xmid < x2);
int y = 0;
if (x <= xmid) {
y = 1;
x2 = xmid;
} else
x1 = xmid + 1;
predictor.update(y);
// Shift equal MSB's out
while (((x1 ^ x2) & 0xff000000) == 0) {
x1 <<= 8;
x2 = (x2 << 8) + 255;
int c = getc(archive);
if (c == EOF)
c = 0;
x = (x << 8) + c;
}
return y;
}
// Should be called when there is no more to compress
void Encoder::flush()
{
if (mode == COMPRESS)
putc(x2 >> 24, archive); // First unequal byte
}
//////////////////////////// main ////////////////////////////
int main(int argc, char **argv)
{
// Chech arguments: fpaq0 c/d input output
if (argc != 4 || (argv[1][0] != 'c' && argv[1][0] != 'd')) {
printf("To compress: fpaq0p c input output\n"
"To decompress: fpaq0p d input output\n");
exit(1);
}
// Start timer
clock_t start = clock();
// Open files
FILE *in = fopen(argv[2], "rb");
if (!in)
perror(argv[2]), exit(1);
FILE *out = fopen(argv[3], "wb");
if (!out)
perror(argv[3]), exit(1);
int c;
// Compress
if (argv[1][0] == 'c') {
Encoder e(COMPRESS, out);
while ((c = getc(in)) != EOF) {
e.encode(0);
for (int i = 7; i >= 0; --i)
e.encode((c >> i) & 1);
}
e.encode(1); // EOF code
e.flush();
}
// Decompress
else {
Encoder e(DECOMPRESS, in);
while (!e.decode()) {
int c = 1;
while (c < 256)
c += c + e.decode();
putc(c - 256, out);
}
}
// Print results
printf("%s (%ld bytes) -> %s (%ld bytes) in %1.2f s.\n",
argv[2], ftell(in), argv[3], ftell(out),
((double)clock() - start) / CLOCKS_PER_SEC);
return 0;
}
