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
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
|
#import "XADARCCrushHandle.h"
#import "XADException.h"
@implementation XADARCCrushHandle
-(id)initWithHandle:(CSHandle *)handle
{
return [self initWithHandle:handle length:CSHandleMaxLength];
}
-(id)initWithHandle:(CSHandle *)handle length:(off_t)length
{
if((self=[super initWithHandle:handle length:length]))
{
lzw=AllocLZW(8192,1);
}
return self;
}
-(void)dealloc
{
FreeLZW(lzw);
[super dealloc];
}
-(void)resetByteStream
{
ClearLZWTable(lzw);
symbolsize=1;
nextsizebump=2;
useliteralbit=YES;
numrecentstrings=0;
ringindex=0;
memset(stringring,0,sizeof(stringring));
usageindex=0x101;
currbyte=0;
}
-(uint8_t)produceByteAtOffset:(off_t)pos
{
if(!currbyte)
{
// Read the next symbol. How depends on the mode we are operating in.
int symbol;
if(useliteralbit)
{
// Use codes prefixed by a bit that selects literal or string codes.
// Literals are always 8 bits, strings vary.
if(CSInputNextBitLE(input)) symbol=CSInputNextBitStringLE(input,symbolsize)+256;
else symbol=CSInputNextBitStringLE(input,8);
}
else
{
// Use same-length codes for both literals and strings.
// Due to an optimization quirk in the original decruncher,
// literals have their bits inverted.
symbol=CSInputNextBitStringLE(input,symbolsize);
if(symbol<0x100) symbol^=0xff;
}
// Code 0x100 is the EOF code.
if(symbol==0x100) CSByteStreamEOF(self);
// Walk through the LZW tree, and set the usage count of the current
// string and all its parents to 4. This is not necessary for literals,
// but we do it anyway for simplicity.
LZWTreeNode *nodes=LZWSymbols(lzw);
int marksymbol=symbol;
while(marksymbol>=0)
{
usage[marksymbol]=4;
marksymbol=nodes[marksymbol].parent;
}
// Adjust the count of recent strings versus literals.
// Use a ring buffer of length 500 as a window to keep track
// of how many strings have been encountered lately.
// First, decrease the count if a string leaves the window.
if(stringring[ringindex]) numrecentstrings--;
// The store the current type of symbol in the window, and
// increase the count if the current symbol is a string.
if(symbol<0x100)
{
stringring[ringindex]=NO;
}
else
{
stringring[ringindex]=YES;
numrecentstrings++;
}
// Move the window forward.
ringindex=(ringindex+1)%500;
// Check the number of strings. If there have been many literals
// lately, bit-prefixed codes should be used. If we need to change
// mode, re-calculate the point where we increase the code length.
BOOL manyliterals=numrecentstrings<375;
if(manyliterals!=useliteralbit)
{
useliteralbit=manyliterals;
nextsizebump=1<<symbolsize;
if(!useliteralbit) nextsizebump-=0x100;
}
// Update the LZW tree.
if(!LZWSymbolListFull(lzw))
{
// If there is space in the tree, just add a new string a usual.
if(NextLZWSymbol(lzw,symbol)==LZWInvalidCodeError) [XADException raiseDecrunchException];
// Set the usage count of the newly created entry.
usage[LZWSymbolCount(lzw)-1]=2;
}
else
{
// If the tree is full, find an less-used symbol, and replace it.
int minindex,minusage=INT_MAX;
int index=usageindex;
do
{
index++;
if(index==8192) index=0x101;
if(usage[index]<minusage)
{
minindex=index;
minusage=usage[index];
}
usage[index]--;
if(usage[index]==0) break;
}
while(index!=usageindex);
usageindex=index;
if(ReplaceLZWSymbol(lzw,minindex,symbol)==LZWInvalidCodeError) [XADException raiseDecrunchException];
// Set the usage count of the replaced entry.
usage[minindex]=2;
}
// Extract the data to output.
currbyte=LZWReverseOutputToBuffer(lzw,buffer);
// Check if we need to increase the code size. The point at which
// to increase varies depending on the coding mode.
if(LZWSymbolCount(lzw)-257>=nextsizebump)
{
symbolsize++;
nextsizebump=1<<symbolsize;
if(!useliteralbit) nextsizebump-=0x100;
}
}
return buffer[--currbyte];
}
@end
|
