Evince
Evince is a document viewer capable of displaying multiple and single page document formats like PDF and Postscript.
 All Data Structures Files Functions Variables Typedefs Enumerations Enumerator Macros Pages
uncompress-rar.c
Go to the documentation of this file.
1 /* Copyright 2015 the unarr project authors (see AUTHORS file).
2  License: LGPLv3 */
3 
4 /* adapted from https://code.google.com/p/theunarchiver/source/browse/XADMaster/XADRAR30Handle.m */
5 /* adapted from https://code.google.com/p/theunarchiver/source/browse/XADMaster/XADRAR20Handle.m */
6 
7 #include "rar.h"
8 
9 static void *gSzAlloc_Alloc(ISzAllocPtr p, size_t size) { return malloc(size); }
10 static void gSzAlloc_Free(ISzAllocPtr p, void *ptr) { free(ptr); }
11 static ISzAlloc gSzAlloc = { gSzAlloc_Alloc, gSzAlloc_Free };
12 
13 static bool br_fill(ar_archive_rar *rar, int bits)
14 {
15  uint8_t bytes[8];
16  int count, i;
17  /* read as many bits as possible */
18  count = (64 - rar->uncomp.br.available) / 8;
19  if (rar->progress.data_left < (size_t)count)
20  count = (int)rar->progress.data_left;
21 
22  if (bits > rar->uncomp.br.available + 8 * count || ar_read(rar->super.stream, bytes, count) != (size_t)count) {
23  if (!rar->uncomp.br.at_eof) {
24  warn("Unexpected EOF during decompression (truncated file?)");
25  rar->uncomp.br.at_eof = true;
26  }
27  return false;
28  }
29  rar->progress.data_left -= count;
30  for (i = 0; i < count; i++) {
31  rar->uncomp.br.bits = (rar->uncomp.br.bits << 8) | bytes[i];
32  }
33  rar->uncomp.br.available += 8 * count;
34  return true;
35 }
36 
37 static inline bool br_check(ar_archive_rar *rar, int bits)
38 {
39  return bits <= rar->uncomp.br.available || br_fill(rar, bits);
40 }
41 
42 static inline uint64_t br_bits(ar_archive_rar *rar, int bits)
43 {
44  return (rar->uncomp.br.bits >> (rar->uncomp.br.available -= bits)) & (((uint64_t)1 << bits) - 1);
45 }
46 
47 static Byte ByteIn_Read(const IByteIn *p)
48 {
49  struct ByteReader *self = (struct ByteReader *) p;
50  return br_check(self->rar, 8) ? (Byte)br_bits(self->rar, 8) : 0xFF;
51 }
52 
53 static void ByteIn_CreateVTable(struct ByteReader *br, ar_archive_rar *rar)
54 {
55  br->super.Read = ByteIn_Read;
56  br->rar = rar;
57 }
58 
59 /* Ppmd7 range decoder differs between 7z and RAR */
60 static void PpmdRAR_RangeDec_Init(struct CPpmdRAR_RangeDec *p)
61 {
62  int i;
63  p->Code = 0;
64  p->Low = 0;
65  p->Range = 0xFFFFFFFF;
66  for (i = 0; i < 4; i++) {
67  p->Code = (p->Code << 8) | p->Stream->Read(p->Stream);
68  }
69 }
70 
71 static UInt32 Range_GetThreshold(const IPpmd7_RangeDec *p, UInt32 total)
72 {
73  struct CPpmdRAR_RangeDec *self = (struct CPpmdRAR_RangeDec *) p;
74  return self->Code / (self->Range /= total);
75 }
76 
77 static void Range_Decode_RAR(const IPpmd7_RangeDec *p, UInt32 start, UInt32 size)
78 {
79  struct CPpmdRAR_RangeDec *self = (struct CPpmdRAR_RangeDec *) p;
80  self->Low += start * self->Range;
81  self->Code -= start * self->Range;
82  self->Range *= size;
83  for (;;) {
84  if ((self->Low ^ (self->Low + self->Range)) >= (1 << 24)) {
85  if (self->Range >= (1 << 15))
86  break;
87  self->Range = ((uint32_t)(-(int32_t)self->Low)) & ((1 << 15) - 1);
88  }
89  self->Code = (self->Code << 8) | self->Stream->Read(self->Stream);
90  self->Range <<= 8;
91  self->Low <<= 8;
92  }
93 }
94 
95 static UInt32 Range_DecodeBit_RAR(const IPpmd7_RangeDec *p, UInt32 size0)
96 {
97  UInt32 value = Range_GetThreshold(p, PPMD_BIN_SCALE);
98  UInt32 bit = value < size0 ? 0 : 1;
99  if (!bit)
100  Range_Decode_RAR(p, 0, size0);
101  else
102  Range_Decode_RAR(p, size0, PPMD_BIN_SCALE - size0);
103  return bit;
104 }
105 
106 static void PpmdRAR_RangeDec_CreateVTable(struct CPpmdRAR_RangeDec *p, IByteIn *stream)
107 {
108  p->super.GetThreshold = Range_GetThreshold;
109  p->super.Decode = Range_Decode_RAR;
110  p->super.DecodeBit = Range_DecodeBit_RAR;
111  p->Stream = stream;
112 }
113 
114 static bool rar_init_uncompress(struct ar_archive_rar_uncomp *uncomp, uint8_t version)
115 {
116  /* per XADRARParser.m @handleForSolidStreamWithObject these versions are identical */
117  if (version == 29 || version == 36)
118  version = 3;
119  else if (version == 20 || version == 26)
120  version = 2;
121  else {
122  warn("Unsupported compression version: %d", version);
123  return false;
124  }
125  if (uncomp->version) {
126  if (uncomp->version != version) {
127  warn("Compression version mismatch: %d != %d", version, uncomp->version);
128  return false;
129  }
130  return true;
131  }
132  memset(uncomp, 0, sizeof(*uncomp));
133  uncomp->start_new_table = true;
134  if (!lzss_initialize(&uncomp->lzss, LZSS_WINDOW_SIZE)) {
135  warn("OOM during decompression");
136  return false;
137  }
138  if (version == 3) {
139  uncomp->state.v3.ppmd_escape = 2;
140  uncomp->state.v3.filters.filterstart = SIZE_MAX;
141  }
142  uncomp->version = version;
143  return true;
144 }
145 
146 static void rar_free_codes(struct ar_archive_rar_uncomp *uncomp);
147 
148 void rar_clear_uncompress(struct ar_archive_rar_uncomp *uncomp)
149 {
150  if (!uncomp->version)
151  return;
152  rar_free_codes(uncomp);
153  lzss_cleanup(&uncomp->lzss);
154  if (uncomp->version == 3) {
155  Ppmd7_Free(&uncomp->state.v3.ppmd7_context, &gSzAlloc);
156  rar_clear_filters(&uncomp->state.v3.filters);
157  }
158  uncomp->version = 0;
159 }
160 
161 static int rar_read_next_symbol(ar_archive_rar *rar, struct huffman_code *code)
162 {
163  int node = 0;
164 
165  if (!code->table && !rar_make_table(code))
166  return -1;
167 
168  /* performance optimization */
169  if (code->tablesize <= rar->uncomp.br.available) {
170  uint16_t bits = (uint16_t)br_bits(rar, code->tablesize);
171  int length = code->table[bits].length;
172  int value = code->table[bits].value;
173 
174  if (length < 0) {
175  warn("Invalid data in bitstream"); /* invalid prefix code in bitstream */
176  return -1;
177  }
178  if (length <= code->tablesize) {
179  /* Skip only length bits */
180  rar->uncomp.br.available += code->tablesize - length;
181  return value;
182  }
183 
184  node = value;
185  }
186 
187  while (!rar_is_leaf_node(code, node)) {
188  uint8_t bit;
189  if (!br_check(rar, 1))
190  return -1;
191  bit = (uint8_t)br_bits(rar, 1);
192  if (code->tree[node].branches[bit] < 0) {
193  warn("Invalid data in bitstream"); /* invalid prefix code in bitstream */
194  return -1;
195  }
196  node = code->tree[node].branches[bit];
197  }
198 
199  return code->tree[node].branches[0];
200 }
201 
202 /***** RAR version 2 decompression *****/
203 
204 static void rar_free_codes_v2(struct ar_archive_rar_uncomp_v2 *uncomp_v2)
205 {
206  int i;
207  rar_free_code(&uncomp_v2->maincode);
208  rar_free_code(&uncomp_v2->offsetcode);
209  rar_free_code(&uncomp_v2->lengthcode);
210  for (i = 0; i < 4; i++)
211  rar_free_code(&uncomp_v2->audiocode[i]);
212 }
213 
214 static bool rar_parse_codes_v2(ar_archive_rar *rar)
215 {
216  struct ar_archive_rar_uncomp_v2 *uncomp_v2 = &rar->uncomp.state.v2;
217  struct huffman_code precode;
218  uint8_t prelengths[19];
219  uint16_t i, count;
220  int j, val, n;
221  bool ok = false;
222 
223  rar_free_codes_v2(uncomp_v2);
224 
225  if (!br_check(rar, 2))
226  return false;
227  uncomp_v2->audioblock = br_bits(rar, 1) != 0;
228  if (!br_bits(rar, 1))
229  memset(uncomp_v2->lengthtable, 0, sizeof(uncomp_v2->lengthtable));
230 
231  if (uncomp_v2->audioblock) {
232  if (!br_check(rar, 2))
233  return false;
234  uncomp_v2->numchannels = (uint8_t)br_bits(rar, 2) + 1;
235  count = uncomp_v2->numchannels * 257;
236  if (uncomp_v2->channel > uncomp_v2->numchannels)
237  uncomp_v2->channel = 0;
238  }
239  else
240  count = MAINCODE_SIZE_20 + OFFSETCODE_SIZE_20 + LENGTHCODE_SIZE_20;
241 
242  for (i = 0; i < 19; i++) {
243  if (!br_check(rar, 4))
244  return false;
245  prelengths[i] = (uint8_t)br_bits(rar, 4);
246  }
247 
248  memset(&precode, 0, sizeof(precode));
249  if (!rar_create_code(&precode, prelengths, 19))
250  goto PrecodeError;
251  for (i = 0; i < count; ) {
252  val = rar_read_next_symbol(rar, &precode);
253  if (val < 0)
254  goto PrecodeError;
255  if (val < 16) {
256  uncomp_v2->lengthtable[i] = (uncomp_v2->lengthtable[i] + val) & 0x0F;
257  i++;
258  }
259  else if (val == 16) {
260  if (i == 0) {
261  warn("Invalid data in bitstream");
262  goto PrecodeError;
263  }
264  if (!br_check(rar, 2))
265  goto PrecodeError;
266  n = (uint8_t)br_bits(rar, 2) + 3;
267  for (j = 0; j < n && i < count; i++, j++) {
268  uncomp_v2->lengthtable[i] = uncomp_v2->lengthtable[i - 1];
269  }
270  }
271  else {
272  if (val == 17) {
273  if (!br_check(rar, 3))
274  goto PrecodeError;
275  n = (uint8_t)br_bits(rar, 3) + 3;
276  }
277  else {
278  if (!br_check(rar, 7))
279  goto PrecodeError;
280  n = (uint8_t)br_bits(rar, 7) + 11;
281  }
282  for (j = 0; j < n && i < count; i++, j++) {
283  uncomp_v2->lengthtable[i] = 0;
284  }
285  }
286  }
287  ok = true;
288 PrecodeError:
289  rar_free_code(&precode);
290  if (!ok)
291  return false;
292 
293  if (uncomp_v2->audioblock) {
294  for (i = 0; i < uncomp_v2->numchannels; i++) {
295  if (!rar_create_code(&uncomp_v2->audiocode[i], uncomp_v2->lengthtable + i * 257, 257))
296  return false;
297  }
298  }
299  else {
300  if (!rar_create_code(&uncomp_v2->maincode, uncomp_v2->lengthtable, MAINCODE_SIZE_20))
301  return false;
302  if (!rar_create_code(&uncomp_v2->offsetcode, uncomp_v2->lengthtable + MAINCODE_SIZE_20, OFFSETCODE_SIZE_20))
303  return false;
304  if (!rar_create_code(&uncomp_v2->lengthcode, uncomp_v2->lengthtable + MAINCODE_SIZE_20 + OFFSETCODE_SIZE_20, LENGTHCODE_SIZE_20))
305  return false;
306  }
307 
308  rar->uncomp.start_new_table = false;
309  return true;
310 }
311 
312 static uint8_t rar_decode_audio(struct AudioState *state, int8_t *channeldelta, int8_t delta)
313 {
314  uint8_t predbyte, byte;
315  int prederror;
316 
317  state->delta[3] = state->delta[2];
318  state->delta[2] = state->delta[1];
319  state->delta[1] = state->lastdelta - state->delta[0];
320  state->delta[0] = state->lastdelta;
321 
322  predbyte = ((8 * state->lastbyte + state->weight[0] * state->delta[0] + state->weight[1] * state->delta[1] + state->weight[2] * state->delta[2] + state->weight[3] * state->delta[3] + state->weight[4] * *channeldelta) >> 3) & 0xFF;
323  byte = (predbyte - delta) & 0xFF;
324 
325  prederror = delta << 3;
326  state->error[0] += abs(prederror);
327  state->error[1] += abs(prederror - state->delta[0]); state->error[2] += abs(prederror + state->delta[0]);
328  state->error[3] += abs(prederror - state->delta[1]); state->error[4] += abs(prederror + state->delta[1]);
329  state->error[5] += abs(prederror - state->delta[2]); state->error[6] += abs(prederror + state->delta[2]);
330  state->error[7] += abs(prederror - state->delta[3]); state->error[8] += abs(prederror + state->delta[3]);
331  state->error[9] += abs(prederror - *channeldelta); state->error[10] += abs(prederror + *channeldelta);
332 
333  *channeldelta = state->lastdelta = (int8_t)(byte - state->lastbyte);
334  state->lastbyte = byte;
335 
336  if (!(++state->count & 0x1F)) {
337  uint8_t i, idx = 0;
338  for (i = 1; i < 11; i++) {
339  if (state->error[i] < state->error[idx])
340  idx = i;
341  }
342  memset(state->error, 0, sizeof(state->error));
343 
344  switch (idx) {
345  case 1: if (state->weight[0] >= -16) state->weight[0]--; break;
346  case 2: if (state->weight[0] < 16) state->weight[0]++; break;
347  case 3: if (state->weight[1] >= -16) state->weight[1]--; break;
348  case 4: if (state->weight[1] < 16) state->weight[1]++; break;
349  case 5: if (state->weight[2] >= -16) state->weight[2]--; break;
350  case 6: if (state->weight[2] < 16) state->weight[2]++; break;
351  case 7: if (state->weight[3] >= -16) state->weight[3]--; break;
352  case 8: if (state->weight[3] < 16) state->weight[3]++; break;
353  case 9: if (state->weight[4] >= -16) state->weight[4]--; break;
354  case 10: if (state->weight[4] < 16) state->weight[4]++; break;
355  }
356  }
357 
358  return byte;
359 }
360 
361 static int64_t rar_expand_v2(ar_archive_rar *rar, int64_t end)
362 {
363  static const uint8_t lengthbases[] =
364  { 0, 1, 2, 3, 4, 5, 6,
365  7, 8, 10, 12, 14, 16, 20,
366  24, 28, 32, 40, 48, 56, 64,
367  80, 96, 112, 128, 160, 192, 224 };
368  static const uint8_t lengthbits[] =
369  { 0, 0, 0, 0, 0, 0, 0,
370  0, 1, 1, 1, 1, 2, 2,
371  2, 2, 3, 3, 3, 3, 4,
372  4, 4, 4, 5, 5, 5, 5 };
373  static const int32_t offsetbases[] =
374  { 0, 1, 2, 3, 4, 6,
375  8, 12, 16, 24, 32, 48,
376  64, 96, 128, 192, 256, 384,
377  512, 768, 1024, 1536, 2048, 3072,
378  4096, 6144, 8192, 12288, 16384, 24576,
379  32768, 49152, 65536, 98304, 131072, 196608,
380  262144, 327680, 393216, 458752, 524288, 589824,
381  655360, 720896, 786432, 851968, 917504, 983040 };
382  static const uint8_t offsetbits[] =
383  { 0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4,
384  5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10,
385  11, 11, 12, 12, 13, 13, 14, 14, 15, 15, 16, 16,
386  16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16 };
387  static const uint8_t shortbases[] =
388  { 0, 4, 8, 16, 32, 64, 128, 192 };
389  static const uint8_t shortbits[] =
390  { 2, 2, 3, 4, 5, 6, 6, 6 };
391 
392  struct ar_archive_rar_uncomp_v2 *uncomp_v2 = &rar->uncomp.state.v2;
393  LZSS *lzss = &rar->uncomp.lzss;
394  int symbol, offs, len;
395 
396  if ((uint64_t)end > rar->super.entry_size_uncompressed + rar->solid.size_total)
397  end = rar->super.entry_size_uncompressed + rar->solid.size_total;
398 
399  for (;;) {
400  if (lzss_position(lzss) >= end)
401  return end;
402 
403  if (uncomp_v2->audioblock) {
404  uint8_t byte;
405  symbol = rar_read_next_symbol(rar, &uncomp_v2->audiocode[uncomp_v2->channel]);
406  if (symbol < 0)
407  return -1;
408  if (symbol == 256) {
409  rar->uncomp.start_new_table = true;
410  return lzss_position(lzss);
411  }
412  byte = rar_decode_audio(&uncomp_v2->audiostate[uncomp_v2->channel], &uncomp_v2->channeldelta, (int8_t)(uint8_t)symbol);
413  uncomp_v2->channel++;
414  if (uncomp_v2->channel == uncomp_v2->numchannels)
415  uncomp_v2->channel = 0;
416  lzss_emit_literal(lzss, byte);
417  continue;
418  }
419 
420  symbol = rar_read_next_symbol(rar, &uncomp_v2->maincode);
421  if (symbol < 0)
422  return -1;
423  if (symbol < 256) {
424  lzss_emit_literal(lzss, (uint8_t)symbol);
425  continue;
426  }
427  if (symbol == 256) {
428  offs = uncomp_v2->lastoffset;
429  len = uncomp_v2->lastlength;
430  }
431  else if (symbol <= 260) {
432  int idx = symbol - 256;
433  int lensymbol = rar_read_next_symbol(rar, &uncomp_v2->lengthcode);
434  offs = uncomp_v2->oldoffset[(uncomp_v2->oldoffsetindex - idx) & 0x03];
435  if (lensymbol < 0 || lensymbol > (int)(sizeof(lengthbases) / sizeof(lengthbases[0])) || lensymbol > (int)(sizeof(lengthbits) / sizeof(lengthbits[0]))) {
436  warn("Invalid data in bitstream");
437  return -1;
438  }
439  len = lengthbases[lensymbol] + 2;
440  if (lengthbits[lensymbol] > 0) {
441  if (!br_check(rar, lengthbits[lensymbol]))
442  return -1;
443  len += (uint8_t)br_bits(rar, lengthbits[lensymbol]);
444  }
445  if (offs >= 0x40000)
446  len++;
447  if (offs >= 0x2000)
448  len++;
449  if (offs >= 0x101)
450  len++;
451  }
452  else if (symbol <= 268) {
453  int idx = symbol - 261;
454  offs = shortbases[idx] + 1;
455  if (shortbits[idx] > 0) {
456  if (!br_check(rar, shortbits[idx]))
457  return -1;
458  offs += (uint8_t)br_bits(rar, shortbits[idx]);
459  }
460  len = 2;
461  }
462  else if (symbol == 269) {
463  rar->uncomp.start_new_table = true;
464  return lzss_position(lzss);
465  }
466  else {
467  int idx = symbol - 270;
468  int offssymbol;
469  if (idx > (int)(sizeof(lengthbases) / sizeof(lengthbases[0])) || idx > (int)(sizeof(lengthbits) / sizeof(lengthbits[0]))) {
470  warn("Invalid data in bitstream");
471  return -1;
472  }
473  len = lengthbases[idx] + 3;
474  if (lengthbits[idx] > 0) {
475  if (!br_check(rar, lengthbits[idx]))
476  return -1;
477  len += (uint8_t)br_bits(rar, lengthbits[idx]);
478  }
479  offssymbol = rar_read_next_symbol(rar, &uncomp_v2->offsetcode);
480  if (offssymbol < 0 || offssymbol > (int)(sizeof(offsetbases) / sizeof(offsetbases[0])) || offssymbol > (int)(sizeof(offsetbits) / sizeof(offsetbits[0]))) {
481  warn("Invalid data in bitstream");
482  return -1;
483  }
484  offs = offsetbases[offssymbol] + 1;
485  if (offsetbits[offssymbol] > 0) {
486  if (!br_check(rar, offsetbits[offssymbol]))
487  return -1;
488  offs += (int)br_bits(rar, offsetbits[offssymbol]);
489  }
490  if (offs >= 0x40000)
491  len++;
492  if (offs >= 0x2000)
493  len++;
494  }
495 
496  uncomp_v2->lastoffset = uncomp_v2->oldoffset[uncomp_v2->oldoffsetindex++ & 0x03] = offs;
497  uncomp_v2->lastlength = len;
498 
499  lzss_emit_match(lzss, offs, len);
500  }
501 }
502 
503 /***** RAR version 3 decompression *****/
504 
505 static void rar_free_codes(struct ar_archive_rar_uncomp *uncomp)
506 {
507  struct ar_archive_rar_uncomp_v3 *uncomp_v3 = &uncomp->state.v3;
508 
509  if (uncomp->version == 2) {
510  rar_free_codes_v2(&uncomp->state.v2);
511  return;
512  }
513 
514  rar_free_code(&uncomp_v3->maincode);
515  rar_free_code(&uncomp_v3->offsetcode);
516  rar_free_code(&uncomp_v3->lowoffsetcode);
517  rar_free_code(&uncomp_v3->lengthcode);
518 }
519 
520 static bool rar_parse_codes(ar_archive_rar *rar)
521 {
522  struct ar_archive_rar_uncomp_v3 *uncomp_v3 = &rar->uncomp.state.v3;
523 
524  if (rar->uncomp.version == 2)
525  return rar_parse_codes_v2(rar);
526 
527  rar_free_codes(&rar->uncomp);
528 
529  br_clear_leftover_bits(&rar->uncomp);
530 
531  if (!br_check(rar, 1))
532  return false;
533  uncomp_v3->is_ppmd_block = br_bits(rar, 1) != 0;
534  if (uncomp_v3->is_ppmd_block) {
535  uint8_t ppmd_flags;
536  uint32_t max_alloc = 0;
537 
538  if (!br_check(rar, 7))
539  return false;
540  ppmd_flags = (uint8_t)br_bits(rar, 7);
541  if ((ppmd_flags & 0x20)) {
542  if (!br_check(rar, 8))
543  return false;
544  max_alloc = ((uint8_t)br_bits(rar, 8) + 1) << 20;
545  }
546  if ((ppmd_flags & 0x40)) {
547  if (!br_check(rar, 8))
548  return false;
549  uncomp_v3->ppmd_escape = (uint8_t)br_bits(rar, 8);
550  }
551  if ((ppmd_flags & 0x20)) {
552  uint32_t maxorder = (ppmd_flags & 0x1F) + 1;
553  if (maxorder == 1)
554  return false;
555  if (maxorder > 16)
556  maxorder = 16 + (maxorder - 16) * 3;
557 
558  Ppmd7_Free(&uncomp_v3->ppmd7_context, &gSzAlloc);
559  Ppmd7_Construct(&uncomp_v3->ppmd7_context);
560  if (!Ppmd7_Alloc(&uncomp_v3->ppmd7_context, max_alloc, &gSzAlloc)) {
561  warn("OOM during decompression");
562  return false;
563  }
564  ByteIn_CreateVTable(&uncomp_v3->bytein, rar);
565  PpmdRAR_RangeDec_CreateVTable(&uncomp_v3->range_dec, &uncomp_v3->bytein.super);
566  PpmdRAR_RangeDec_Init(&uncomp_v3->range_dec);
567  Ppmd7_Init(&uncomp_v3->ppmd7_context, maxorder);
568  }
569  else {
570  if (!Ppmd7_WasAllocated(&uncomp_v3->ppmd7_context)) {
571  warn("Invalid data in bitstream"); /* invalid PPMd sequence */
572  return false;
573  }
574  PpmdRAR_RangeDec_Init(&uncomp_v3->range_dec);
575  }
576  }
577  else {
578  struct huffman_code precode;
579  uint8_t bitlengths[20];
580  uint8_t zerocount;
581  int i, j, val, n;
582  bool ok = false;
583 
584  if (!br_check(rar, 1))
585  return false;
586  if (!br_bits(rar, 1))
587  memset(uncomp_v3->lengthtable, 0, sizeof(uncomp_v3->lengthtable));
588  memset(&bitlengths, 0, sizeof(bitlengths));
589  for (i = 0; i < sizeof(bitlengths); i++) {
590  if (!br_check(rar, 4))
591  return false;
592  bitlengths[i] = (uint8_t)br_bits(rar, 4);
593  if (bitlengths[i] == 0x0F) {
594  if (!br_check(rar, 4))
595  return false;
596  zerocount = (uint8_t)br_bits(rar, 4);
597  if (zerocount) {
598  for (j = 0; j < zerocount + 2 && i < sizeof(bitlengths); j++) {
599  bitlengths[i++] = 0;
600  }
601  i--;
602  }
603  }
604  }
605 
606  memset(&precode, 0, sizeof(precode));
607  if (!rar_create_code(&precode, bitlengths, sizeof(bitlengths)))
608  goto PrecodeError;
609  for (i = 0; i < HUFFMAN_TABLE_SIZE; ) {
610  val = rar_read_next_symbol(rar, &precode);
611  if (val < 0)
612  goto PrecodeError;
613  if (val < 16) {
614  uncomp_v3->lengthtable[i] = (uncomp_v3->lengthtable[i] + val) & 0x0F;
615  i++;
616  }
617  else if (val < 18) {
618  if (i == 0) {
619  warn("Invalid data in bitstream");
620  goto PrecodeError;
621  }
622  if (val == 16) {
623  if (!br_check(rar, 3))
624  goto PrecodeError;
625  n = (uint8_t)br_bits(rar, 3) + 3;
626  }
627  else {
628  if (!br_check(rar, 7))
629  goto PrecodeError;
630  n = (uint8_t)br_bits(rar, 7) + 11;
631  }
632  for (j = 0; j < n && i < HUFFMAN_TABLE_SIZE; i++, j++) {
633  uncomp_v3->lengthtable[i] = uncomp_v3->lengthtable[i - 1];
634  }
635  }
636  else {
637  if (val == 18) {
638  if (!br_check(rar, 3))
639  goto PrecodeError;
640  n = (uint8_t)br_bits(rar, 3) + 3;
641  }
642  else {
643  if (!br_check(rar, 7))
644  goto PrecodeError;
645  n = (uint8_t)br_bits(rar, 7) + 11;
646  }
647  for (j = 0; j < n && i < HUFFMAN_TABLE_SIZE; i++, j++) {
648  uncomp_v3->lengthtable[i] = 0;
649  }
650  }
651  }
652  ok = true;
653 PrecodeError:
654  rar_free_code(&precode);
655  if (!ok)
656  return false;
657 
658  if (!rar_create_code(&uncomp_v3->maincode, uncomp_v3->lengthtable, MAINCODE_SIZE))
659  return false;
660  if (!rar_create_code(&uncomp_v3->offsetcode, uncomp_v3->lengthtable + MAINCODE_SIZE, OFFSETCODE_SIZE))
661  return false;
662  if (!rar_create_code(&uncomp_v3->lowoffsetcode, uncomp_v3->lengthtable + MAINCODE_SIZE + OFFSETCODE_SIZE, LOWOFFSETCODE_SIZE))
663  return false;
664  if (!rar_create_code(&uncomp_v3->lengthcode, uncomp_v3->lengthtable + MAINCODE_SIZE + OFFSETCODE_SIZE + LOWOFFSETCODE_SIZE, LENGTHCODE_SIZE))
665  return false;
666  }
667 
668  rar->uncomp.start_new_table = false;
669  return true;
670 }
671 
672 static bool rar_read_filter(ar_archive_rar *rar, bool (* decode_byte)(ar_archive_rar *rar, uint8_t *byte), int64_t *end)
673 {
674  uint8_t flags, val, *code;
675  uint16_t length, i;
676 
677  if (!decode_byte(rar, &flags))
678  return false;
679  length = (flags & 0x07) + 1;
680  if (length == 7) {
681  if (!decode_byte(rar, &val))
682  return false;
683  length = val + 7;
684  }
685  else if (length == 8) {
686  if (!decode_byte(rar, &val))
687  return false;
688  length = val << 8;
689  if (!decode_byte(rar, &val))
690  return false;
691  length |= val;
692  }
693 
694  code = malloc(length);
695  if (!code) {
696  warn("OOM during decompression");
697  return false;
698  }
699  for (i = 0; i < length; i++) {
700  if (!decode_byte(rar, &code[i])) {
701  free(code);
702  return false;
703  }
704  }
705  if (!rar_parse_filter(rar, code, length, flags)) {
706  free(code);
707  return false;
708  }
709  free(code);
710 
711  if (rar->uncomp.state.v3.filters.filterstart < (size_t)*end)
712  *end = rar->uncomp.state.v3.filters.filterstart;
713 
714  return true;
715 }
716 
717 static inline bool rar_decode_ppmd7_symbol(struct ar_archive_rar_uncomp_v3 *uncomp_v3, Byte *symbol)
718 {
719  int value = Ppmd7_DecodeSymbol(&uncomp_v3->ppmd7_context, &uncomp_v3->range_dec.super);
720  if (value < 0) {
721  warn("Invalid data in bitstream"); /* invalid PPMd symbol */
722  return false;
723  }
724  *symbol = (Byte)value;
725  return true;
726 }
727 
728 static bool rar_decode_byte(ar_archive_rar *rar, uint8_t *byte)
729 {
730  if (!br_check(rar, 8))
731  return false;
732  *byte = (uint8_t)br_bits(rar, 8);
733  return true;
734 }
735 
736 static bool rar_decode_ppmd7_byte(ar_archive_rar *rar, uint8_t *byte)
737 {
738  return rar_decode_ppmd7_symbol(&rar->uncomp.state.v3, byte);
739 }
740 
741 static bool rar_handle_ppmd_sequence(ar_archive_rar *rar, int64_t *end)
742 {
743  struct ar_archive_rar_uncomp_v3 *uncomp_v3 = &rar->uncomp.state.v3;
744  LZSS *lzss = &rar->uncomp.lzss;
745  Byte sym, code, length;
746  int lzss_offset;
747 
748  if (!rar_decode_ppmd7_symbol(uncomp_v3, &sym))
749  return false;
750  if (sym != uncomp_v3->ppmd_escape) {
751  lzss_emit_literal(lzss, sym);
752  return true;
753  }
754 
755  if (!rar_decode_ppmd7_symbol(uncomp_v3, &code))
756  return false;
757  switch (code) {
758  case 0:
759  return rar_parse_codes(rar);
760 
761  case 2:
762  rar->uncomp.start_new_table = true;
763  return true;
764 
765  case 3:
766  return rar_read_filter(rar, rar_decode_ppmd7_byte, end);
767 
768  case 4:
769  if (!rar_decode_ppmd7_symbol(uncomp_v3, &code))
770  return false;
771  lzss_offset = code << 16;
772  if (!rar_decode_ppmd7_symbol(uncomp_v3, &code))
773  return false;
774  lzss_offset |= code << 8;
775  if (!rar_decode_ppmd7_symbol(uncomp_v3, &code))
776  return false;
777  lzss_offset |= code;
778  if (!rar_decode_ppmd7_symbol(uncomp_v3, &length))
779  return false;
780  lzss_emit_match(lzss, lzss_offset + 2, length + 32);
781  return true;
782 
783  case 5:
784  if (!rar_decode_ppmd7_symbol(uncomp_v3, &length))
785  return false;
786  lzss_emit_match(lzss, 1, length + 4);
787  return true;
788 
789  default:
790  lzss_emit_literal(lzss, sym);
791  return true;
792  }
793 }
794 
795 int64_t rar_expand(ar_archive_rar *rar, int64_t end)
796 {
797  static const uint8_t lengthbases[] =
798  { 0, 1, 2, 3, 4, 5, 6,
799  7, 8, 10, 12, 14, 16, 20,
800  24, 28, 32, 40, 48, 56, 64,
801  80, 96, 112, 128, 160, 192, 224 };
802  static const uint8_t lengthbits[] =
803  { 0, 0, 0, 0, 0, 0, 0,
804  0, 1, 1, 1, 1, 2, 2,
805  2, 2, 3, 3, 3, 3, 4,
806  4, 4, 4, 5, 5, 5, 5 };
807  static const int32_t offsetbases[] =
808  { 0, 1, 2, 3, 4, 6,
809  8, 12, 16, 24, 32, 48,
810  64, 96, 128, 192, 256, 384,
811  512, 768, 1024, 1536, 2048, 3072,
812  4096, 6144, 8192, 12288, 16384, 24576,
813  32768, 49152, 65536, 98304, 131072, 196608,
814  262144, 327680, 393216, 458752, 524288, 589824,
815  655360, 720896, 786432, 851968, 917504, 983040,
816  1048576, 1310720, 1572864, 1835008, 2097152, 2359296,
817  2621440, 2883584, 3145728, 3407872, 3670016, 3932160 };
818  static const uint8_t offsetbits[] =
819  { 0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4,
820  5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10,
821  11, 11, 12, 12, 13, 13, 14, 14, 15, 15, 16, 16,
822  16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16,
823  18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18 };
824  static const uint8_t shortbases[] =
825  { 0, 4, 8, 16, 32, 64, 128, 192 };
826  static const uint8_t shortbits[] =
827  { 2, 2, 3, 4, 5, 6, 6, 6 };
828 
829  struct ar_archive_rar_uncomp_v3 *uncomp_v3 = &rar->uncomp.state.v3;
830  LZSS *lzss = &rar->uncomp.lzss;
831  int symbol, offs, len, i;
832 
833  if (rar->uncomp.version == 2)
834  return rar_expand_v2(rar, end);
835 
836  for (;;) {
837  if (lzss_position(lzss) >= end)
838  return end;
839 
840  if (uncomp_v3->is_ppmd_block) {
841  if (!rar_handle_ppmd_sequence(rar, &end))
842  return -1;
843  if (rar->uncomp.start_new_table)
844  return lzss_position(lzss);
845  continue;
846  }
847 
848  symbol = rar_read_next_symbol(rar, &uncomp_v3->maincode);
849  if (symbol < 0)
850  return -1;
851  if (symbol < 256) {
852  lzss_emit_literal(lzss, (uint8_t)symbol);
853  continue;
854  }
855  if (symbol == 256) {
856  if (!br_check(rar, 1))
857  return -1;
858  if (!br_bits(rar, 1)) {
859  if (!br_check(rar, 1))
860  return -1;
861  rar->uncomp.start_new_table = br_bits(rar, 1) != 0;
862  return lzss_position(lzss);
863  }
864  if (!rar_parse_codes(rar))
865  return -1;
866  continue;
867  }
868  if (symbol == 257) {
869  if (!rar_read_filter(rar, rar_decode_byte, &end))
870  return -1;
871  continue;
872  }
873  if (symbol == 258) {
874  if (uncomp_v3->lastlength == 0)
875  continue;
876  offs = uncomp_v3->lastoffset;
877  len = uncomp_v3->lastlength;
878  }
879  else if (symbol <= 262) {
880  int idx = symbol - 259;
881  int lensymbol = rar_read_next_symbol(rar, &uncomp_v3->lengthcode);
882  offs = uncomp_v3->oldoffset[idx];
883  if (lensymbol < 0 || lensymbol > (int)(sizeof(lengthbases) / sizeof(lengthbases[0])) || lensymbol > (int)(sizeof(lengthbits) / sizeof(lengthbits[0]))) {
884  warn("Invalid data in bitstream");
885  return -1;
886  }
887  len = lengthbases[lensymbol] + 2;
888  if (lengthbits[lensymbol] > 0) {
889  if (!br_check(rar, lengthbits[lensymbol]))
890  return -1;
891  len += (uint8_t)br_bits(rar, lengthbits[lensymbol]);
892  }
893  for (i = idx; i > 0; i--)
894  uncomp_v3->oldoffset[i] = uncomp_v3->oldoffset[i - 1];
895  uncomp_v3->oldoffset[0] = offs;
896  }
897  else if (symbol <= 270) {
898  int idx = symbol - 263;
899  offs = shortbases[idx] + 1;
900  if (shortbits[idx] > 0) {
901  if (!br_check(rar, shortbits[idx]))
902  return -1;
903  offs += (uint8_t)br_bits(rar, shortbits[idx]);
904  }
905  len = 2;
906  for (i = 3; i > 0; i--)
907  uncomp_v3->oldoffset[i] = uncomp_v3->oldoffset[i - 1];
908  uncomp_v3->oldoffset[0] = offs;
909  }
910  else {
911  int idx = symbol - 271;
912  int offssymbol;
913  if (idx > (int)(sizeof(lengthbases) / sizeof(lengthbases[0])) || idx > (int)(sizeof(lengthbits) / sizeof(lengthbits[0]))) {
914  warn("Invalid data in bitstream");
915  return -1;
916  }
917  len = lengthbases[idx] + 3;
918  if (lengthbits[idx] > 0) {
919  if (!br_check(rar, lengthbits[idx]))
920  return -1;
921  len += (uint8_t)br_bits(rar, lengthbits[idx]);
922  }
923  offssymbol = rar_read_next_symbol(rar, &uncomp_v3->offsetcode);
924  if (offssymbol < 0 || offssymbol > (int)(sizeof(offsetbases) / sizeof(offsetbases[0])) || offssymbol > (int)(sizeof(offsetbits) / sizeof(offsetbits[0]))) {
925  warn("Invalid data in bitstream");
926  return -1;
927  }
928  offs = offsetbases[offssymbol] + 1;
929  if (offsetbits[offssymbol] > 0) {
930  if (offssymbol > 9) {
931  if (offsetbits[offssymbol] > 4) {
932  if (!br_check(rar, offsetbits[offssymbol] - 4))
933  return -1;
934  offs += (int)br_bits(rar, offsetbits[offssymbol] - 4) << 4;
935  }
936  if (uncomp_v3->numlowoffsetrepeats > 0) {
937  uncomp_v3->numlowoffsetrepeats--;
938  offs += uncomp_v3->lastlowoffset;
939  }
940  else {
941  int lowoffsetsymbol = rar_read_next_symbol(rar, &uncomp_v3->lowoffsetcode);
942  if (lowoffsetsymbol < 0)
943  return -1;
944  if (lowoffsetsymbol == 16) {
945  uncomp_v3->numlowoffsetrepeats = 15;
946  offs += uncomp_v3->lastlowoffset;
947  }
948  else {
949  offs += lowoffsetsymbol;
950  uncomp_v3->lastlowoffset = lowoffsetsymbol;
951  }
952  }
953  }
954  else {
955  if (!br_check(rar, offsetbits[offssymbol]))
956  return -1;
957  offs += (int)br_bits(rar, offsetbits[offssymbol]);
958  }
959  }
960 
961  if (offs >= 0x40000)
962  len++;
963  if (offs >= 0x2000)
964  len++;
965 
966  for (i = 3; i > 0; i--)
967  uncomp_v3->oldoffset[i] = uncomp_v3->oldoffset[i - 1];
968  uncomp_v3->oldoffset[0] = offs;
969  }
970 
971  uncomp_v3->lastoffset = offs;
972  uncomp_v3->lastlength = len;
973 
974  lzss_emit_match(lzss, offs, len);
975  }
976 }
977 
978 bool rar_uncompress_part(ar_archive_rar *rar, void *buffer, size_t buffer_size)
979 {
980  struct ar_archive_rar_uncomp *uncomp = &rar->uncomp;
981  struct ar_archive_rar_uncomp_v3 *uncomp_v3 = NULL;
982  size_t end;
983 
984  if (!rar_init_uncompress(uncomp, rar->entry.version))
985  return false;
986  if (uncomp->version == 3)
987  uncomp_v3 = &uncomp->state.v3;
988 
989  for (;;) {
990  if (uncomp_v3 && uncomp_v3->filters.bytes_ready > 0) {
991  size_t count = smin(uncomp_v3->filters.bytes_ready, buffer_size);
992  memcpy(buffer, uncomp_v3->filters.bytes, count);
993  uncomp_v3->filters.bytes_ready -= count;
994  uncomp_v3->filters.bytes += count;
995  rar->progress.bytes_done += count;
996  buffer_size -= count;
997  buffer = (uint8_t *)buffer + count;
998  if (rar->progress.bytes_done == rar->super.entry_size_uncompressed)
999  goto FinishBlock;
1000  }
1001  else if (uncomp->bytes_ready > 0) {
1002  int count = (int)smin(uncomp->bytes_ready, buffer_size);
1003  lzss_copy_bytes_from_window(&uncomp->lzss, buffer, rar->progress.bytes_done + rar->solid.size_total, count);
1004  uncomp->bytes_ready -= count;
1005  rar->progress.bytes_done += count;
1006  buffer_size -= count;
1007  buffer = (uint8_t *)buffer + count;
1008  }
1009  if (buffer_size == 0)
1010  return true;
1011 
1012  if (uncomp->br.at_eof)
1013  return false;
1014 
1015  if (uncomp_v3 && uncomp_v3->filters.lastend == uncomp_v3->filters.filterstart) {
1016  if (!rar_run_filters(rar))
1017  return false;
1018  continue;
1019  }
1020 
1021 FinishBlock:
1022  if (uncomp->start_new_table && !rar_parse_codes(rar))
1023  return false;
1024 
1025  end = rar->progress.bytes_done + rar->solid.size_total + LZSS_WINDOW_SIZE - LZSS_OVERFLOW_SIZE;
1026  if (uncomp_v3 && uncomp_v3->filters.filterstart < end)
1027  end = uncomp_v3->filters.filterstart;
1028  end = (size_t)rar_expand(rar, end);
1029  if (end == (size_t)-1 || end < rar->progress.bytes_done + rar->solid.size_total)
1030  return false;
1031  uncomp->bytes_ready = end - rar->progress.bytes_done - rar->solid.size_total;
1032  if (uncomp_v3)
1033  uncomp_v3->filters.lastend = end;
1034 
1035  if (uncomp_v3 && uncomp_v3->is_ppmd_block && uncomp->start_new_table)
1036  goto FinishBlock;
1037  }
1038 }