-
Notifications
You must be signed in to change notification settings - Fork 107
Expand file tree
/
Copy pathPpmDecompress.java
More file actions
99 lines (85 loc) · 3.3 KB
/
Copy pathPpmDecompress.java
File metadata and controls
99 lines (85 loc) · 3.3 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
/*
* Reference arithmetic coding
*
* Copyright (c) Project Nayuki
* MIT License. See readme file.
* https://www.nayuki.io/page/reference-arithmetic-coding
*/
import java.io.BufferedInputStream;
import java.io.BufferedOutputStream;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileOutputStream;
import java.io.IOException;
import java.io.OutputStream;
import java.util.Arrays;
/**
* Decompression application using prediction by partial matching (PPM) with arithmetic coding.
* <p>Usage: java PpmDecompress InputFile OutputFile</p>
* <p>This decompresses files generated by the "PpmCompress" application.</p>
*/
public final class PpmDecompress {
// Must be at least -1 and match PpmCompress. Warning: Exponential memory usage at O(257^n).
private static final int MODEL_ORDER = 3;
public static void main(String[] args) throws IOException {
// Handle command line arguments
if (args.length != 2) {
System.err.println("Usage: java PpmDecompress InputFile OutputFile");
System.exit(1);
return;
}
File inputFile = new File(args[0]);
File outputFile = new File(args[1]);
// Perform file decompression
try (BitInputStream in = new BitInputStream(new BufferedInputStream(new FileInputStream(inputFile)));
OutputStream out = new BufferedOutputStream(new FileOutputStream(outputFile))) {
decompress(in, out);
}
}
// To allow unit testing, this method is package-private instead of private.
static void decompress(BitInputStream in, OutputStream out) throws IOException {
// Set up decoder and model. In this PPM model, symbol 256 represents EOF;
// its frequency is 1 in the order -1 context but its frequency
// is 0 in all other contexts (which have non-negative order).
ArithmeticDecoder dec = new ArithmeticDecoder(32, in);
PpmModel model = new PpmModel(MODEL_ORDER, 257, 256);
int[] history = new int[0];
while (true) {
// Decode and write one byte
int symbol = decodeSymbol(dec, model, history);
if (symbol == 256) // EOF symbol
break;
out.write(symbol);
model.incrementContexts(history, symbol);
if (model.modelOrder >= 1) {
// Prepend current symbol, dropping oldest symbol if necessary
if (history.length < model.modelOrder)
history = Arrays.copyOf(history, history.length + 1);
System.arraycopy(history, 0, history, 1, history.length - 1);
history[0] = symbol;
}
}
}
private static int decodeSymbol(ArithmeticDecoder dec, PpmModel model, int[] history) throws IOException {
// Try to use highest order context that exists based on the history suffix. When symbol 256
// is consumed at a context at any non-negative order, it means "escape to the next lower order
// with non-empty context". When symbol 256 is consumed at the order -1 context, it means "EOF".
outer:
for (int order = history.length; order >= 0; order--) {
PpmModel.Context ctx = model.rootContext;
for (int i = 0; i < order; i++) {
if (ctx.subcontexts == null)
throw new AssertionError();
ctx = ctx.subcontexts[history[i]];
if (ctx == null)
continue outer;
}
int symbol = dec.read(ctx.frequencies);
if (symbol < 256)
return symbol;
// Else we read the context escape symbol, so continue decrementing the order
}
// Logic for order = -1
return dec.read(model.orderMinus1Freqs);
}
}