File indexing completed on 2025-02-02 04:26:02
0001 /* Copyright 2015 the unarr project authors (see AUTHORS file). 0002 License: LGPLv3 */ 0003 0004 /* adapted from https://code.google.com/p/theunarchiver/source/browse/XADMaster/XADRAR30Handle.m */ 0005 /* adapted from https://code.google.com/p/theunarchiver/source/browse/XADMaster/XADRAR20Handle.m */ 0006 0007 #include "rar.h" 0008 0009 static void *gSzAlloc_Alloc(void *self, size_t size) { (void)self; return malloc(size); } 0010 static void gSzAlloc_Free(void *self, void *ptr) { (void)self; free(ptr); } 0011 static ISzAlloc gSzAlloc = { gSzAlloc_Alloc, gSzAlloc_Free }; 0012 0013 static bool br_fill(ar_archive_rar *rar, int bits) 0014 { 0015 uint8_t bytes[8]; 0016 int count, i; 0017 /* read as many bits as possible */ 0018 count = (64 - rar->uncomp.br.available) / 8; 0019 if (rar->progress.data_left < (size_t)count) 0020 count = (int)rar->progress.data_left; 0021 0022 if (bits > rar->uncomp.br.available + 8 * count || ar_read(rar->super.stream, bytes, count) != (size_t)count) { 0023 if (!rar->uncomp.br.at_eof) { 0024 warn("Unexpected EOF during decompression (truncated file?)"); 0025 rar->uncomp.br.at_eof = true; 0026 } 0027 return false; 0028 } 0029 rar->progress.data_left -= count; 0030 for (i = 0; i < count; i++) { 0031 rar->uncomp.br.bits = (rar->uncomp.br.bits << 8) | bytes[i]; 0032 } 0033 rar->uncomp.br.available += 8 * count; 0034 return true; 0035 } 0036 0037 static inline bool br_check(ar_archive_rar *rar, int bits) 0038 { 0039 return bits <= rar->uncomp.br.available || br_fill(rar, bits); 0040 } 0041 0042 static inline uint64_t br_bits(ar_archive_rar *rar, int bits) 0043 { 0044 return (rar->uncomp.br.bits >> (rar->uncomp.br.available -= bits)) & (((uint64_t)1 << bits) - 1); 0045 } 0046 0047 static Byte ByteIn_Read(void *p) 0048 { 0049 struct ByteReader *self = p; 0050 return br_check(self->rar, 8) ? (Byte)br_bits(self->rar, 8) : 0xFF; 0051 } 0052 0053 static void ByteIn_CreateVTable(struct ByteReader *br, ar_archive_rar *rar) 0054 { 0055 br->super.Read = ByteIn_Read; 0056 br->rar = rar; 0057 } 0058 0059 /* Ppmd7 range decoder differs between 7z and RAR */ 0060 static void PpmdRAR_RangeDec_Init(struct CPpmdRAR_RangeDec *p) 0061 { 0062 int i; 0063 p->Code = 0; 0064 p->Low = 0; 0065 p->Range = 0xFFFFFFFF; 0066 for (i = 0; i < 4; i++) { 0067 p->Code = (p->Code << 8) | p->Stream->Read(p->Stream); 0068 } 0069 } 0070 0071 static UInt32 Range_GetThreshold(void *p, UInt32 total) 0072 { 0073 struct CPpmdRAR_RangeDec *self = p; 0074 return self->Code / (self->Range /= total); 0075 } 0076 0077 static void Range_Decode_RAR(void *p, UInt32 start, UInt32 size) 0078 { 0079 struct CPpmdRAR_RangeDec *self = p; 0080 self->Low += start * self->Range; 0081 self->Code -= start * self->Range; 0082 self->Range *= size; 0083 for (;;) { 0084 if ((self->Low ^ (self->Low + self->Range)) >= (1 << 24)) { 0085 if (self->Range >= (1 << 15)) 0086 break; 0087 self->Range = ((uint32_t)(-(int32_t)self->Low)) & ((1 << 15) - 1); 0088 } 0089 self->Code = (self->Code << 8) | self->Stream->Read(self->Stream); 0090 self->Range <<= 8; 0091 self->Low <<= 8; 0092 } 0093 } 0094 0095 static UInt32 Range_DecodeBit_RAR(void *p, UInt32 size0) 0096 { 0097 UInt32 value = Range_GetThreshold(p, PPMD_BIN_SCALE); 0098 UInt32 bit = value < size0 ? 0 : 1; 0099 if (!bit) 0100 Range_Decode_RAR(p, 0, size0); 0101 else 0102 Range_Decode_RAR(p, size0, PPMD_BIN_SCALE - size0); 0103 return bit; 0104 } 0105 0106 static void PpmdRAR_RangeDec_CreateVTable(struct CPpmdRAR_RangeDec *p, IByteIn *stream) 0107 { 0108 p->super.GetThreshold = Range_GetThreshold; 0109 p->super.Decode = Range_Decode_RAR; 0110 p->super.DecodeBit = Range_DecodeBit_RAR; 0111 p->Stream = stream; 0112 } 0113 0114 static bool rar_init_uncompress(struct ar_archive_rar_uncomp *uncomp, uint8_t version) 0115 { 0116 /* per XADRARParser.m @handleForSolidStreamWithObject these versions are identical */ 0117 if (version == 29 || version == 36) 0118 version = 3; 0119 else if (version == 20 || version == 26) 0120 version = 2; 0121 else { 0122 warn("Unsupported compression version: %d", version); 0123 return false; 0124 } 0125 if (uncomp->version) { 0126 if (uncomp->version != version) { 0127 warn("Compression version mismatch: %d != %d", version, uncomp->version); 0128 return false; 0129 } 0130 return true; 0131 } 0132 memset(uncomp, 0, sizeof(*uncomp)); 0133 uncomp->start_new_table = true; 0134 if (!lzss_initialize(&uncomp->lzss, LZSS_WINDOW_SIZE)) { 0135 warn("OOM during decompression"); 0136 return false; 0137 } 0138 if (version == 3) { 0139 uncomp->state.v3.ppmd_escape = 2; 0140 uncomp->state.v3.filters.filterstart = SIZE_MAX; 0141 } 0142 uncomp->version = version; 0143 return true; 0144 } 0145 0146 static void rar_free_codes(struct ar_archive_rar_uncomp *uncomp); 0147 0148 void rar_clear_uncompress(struct ar_archive_rar_uncomp *uncomp) 0149 { 0150 if (!uncomp->version) 0151 return; 0152 rar_free_codes(uncomp); 0153 lzss_cleanup(&uncomp->lzss); 0154 if (uncomp->version == 3) { 0155 Ppmd7_Free(&uncomp->state.v3.ppmd7_context, &gSzAlloc); 0156 rar_clear_filters(&uncomp->state.v3.filters); 0157 } 0158 uncomp->version = 0; 0159 } 0160 0161 static int rar_read_next_symbol(ar_archive_rar *rar, struct huffman_code *code) 0162 { 0163 int node = 0; 0164 0165 if (!code->table && !rar_make_table(code)) 0166 return -1; 0167 0168 /* performance optimization */ 0169 if (code->tablesize <= rar->uncomp.br.available) { 0170 uint16_t bits = (uint16_t)br_bits(rar, code->tablesize); 0171 int length = code->table[bits].length; 0172 int value = code->table[bits].value; 0173 0174 if (length < 0) { 0175 warn("Invalid data in bitstream"); /* invalid prefix code in bitstream */ 0176 return -1; 0177 } 0178 if (length <= code->tablesize) { 0179 /* Skip only length bits */ 0180 rar->uncomp.br.available += code->tablesize - length; 0181 return value; 0182 } 0183 0184 node = value; 0185 } 0186 0187 while (!rar_is_leaf_node(code, node)) { 0188 uint8_t bit; 0189 if (!br_check(rar, 1)) 0190 return -1; 0191 bit = (uint8_t)br_bits(rar, 1); 0192 if (code->tree[node].branches[bit] < 0) { 0193 warn("Invalid data in bitstream"); /* invalid prefix code in bitstream */ 0194 return -1; 0195 } 0196 node = code->tree[node].branches[bit]; 0197 } 0198 0199 return code->tree[node].branches[0]; 0200 } 0201 0202 /***** RAR version 2 decompression *****/ 0203 0204 static void rar_free_codes_v2(struct ar_archive_rar_uncomp_v2 *uncomp_v2) 0205 { 0206 int i; 0207 rar_free_code(&uncomp_v2->maincode); 0208 rar_free_code(&uncomp_v2->offsetcode); 0209 rar_free_code(&uncomp_v2->lengthcode); 0210 for (i = 0; i < 4; i++) 0211 rar_free_code(&uncomp_v2->audiocode[i]); 0212 } 0213 0214 static bool rar_parse_codes_v2(ar_archive_rar *rar) 0215 { 0216 struct ar_archive_rar_uncomp_v2 *uncomp_v2 = &rar->uncomp.state.v2; 0217 struct huffman_code precode; 0218 uint8_t prelengths[19]; 0219 uint16_t i, count; 0220 int j, val, n; 0221 bool ok = false; 0222 0223 rar_free_codes_v2(uncomp_v2); 0224 0225 if (!br_check(rar, 2)) 0226 return false; 0227 uncomp_v2->audioblock = br_bits(rar, 1) != 0; 0228 if (!br_bits(rar, 1)) 0229 memset(uncomp_v2->lengthtable, 0, sizeof(uncomp_v2->lengthtable)); 0230 0231 if (uncomp_v2->audioblock) { 0232 if (!br_check(rar, 2)) 0233 return false; 0234 uncomp_v2->numchannels = (uint8_t)br_bits(rar, 2) + 1; 0235 count = uncomp_v2->numchannels * 257; 0236 if (uncomp_v2->channel > uncomp_v2->numchannels) 0237 uncomp_v2->channel = 0; 0238 } 0239 else 0240 count = MAINCODE_SIZE_20 + OFFSETCODE_SIZE_20 + LENGTHCODE_SIZE_20; 0241 0242 for (i = 0; i < 19; i++) { 0243 if (!br_check(rar, 4)) 0244 return false; 0245 prelengths[i] = (uint8_t)br_bits(rar, 4); 0246 } 0247 0248 memset(&precode, 0, sizeof(precode)); 0249 if (!rar_create_code(&precode, prelengths, 19)) 0250 goto PrecodeError; 0251 for (i = 0; i < count; ) { 0252 val = rar_read_next_symbol(rar, &precode); 0253 if (val < 0) 0254 goto PrecodeError; 0255 if (val < 16) { 0256 uncomp_v2->lengthtable[i] = (uncomp_v2->lengthtable[i] + val) & 0x0F; 0257 i++; 0258 } 0259 else if (val == 16) { 0260 if (i == 0) { 0261 warn("Invalid data in bitstream"); 0262 goto PrecodeError; 0263 } 0264 if (!br_check(rar, 2)) 0265 goto PrecodeError; 0266 n = (uint8_t)br_bits(rar, 2) + 3; 0267 for (j = 0; j < n && i < count; i++, j++) { 0268 uncomp_v2->lengthtable[i] = uncomp_v2->lengthtable[i - 1]; 0269 } 0270 } 0271 else { 0272 if (val == 17) { 0273 if (!br_check(rar, 3)) 0274 goto PrecodeError; 0275 n = (uint8_t)br_bits(rar, 3) + 3; 0276 } 0277 else { 0278 if (!br_check(rar, 7)) 0279 goto PrecodeError; 0280 n = (uint8_t)br_bits(rar, 7) + 11; 0281 } 0282 for (j = 0; j < n && i < count; i++, j++) { 0283 uncomp_v2->lengthtable[i] = 0; 0284 } 0285 } 0286 } 0287 ok = true; 0288 PrecodeError: 0289 rar_free_code(&precode); 0290 if (!ok) 0291 return false; 0292 0293 if (uncomp_v2->audioblock) { 0294 for (i = 0; i < uncomp_v2->numchannels; i++) { 0295 if (!rar_create_code(&uncomp_v2->audiocode[i], uncomp_v2->lengthtable + i * 257, 257)) 0296 return false; 0297 } 0298 } 0299 else { 0300 if (!rar_create_code(&uncomp_v2->maincode, uncomp_v2->lengthtable, MAINCODE_SIZE_20)) 0301 return false; 0302 if (!rar_create_code(&uncomp_v2->offsetcode, uncomp_v2->lengthtable + MAINCODE_SIZE_20, OFFSETCODE_SIZE_20)) 0303 return false; 0304 if (!rar_create_code(&uncomp_v2->lengthcode, uncomp_v2->lengthtable + MAINCODE_SIZE_20 + OFFSETCODE_SIZE_20, LENGTHCODE_SIZE_20)) 0305 return false; 0306 } 0307 0308 rar->uncomp.start_new_table = false; 0309 return true; 0310 } 0311 0312 static uint8_t rar_decode_audio(struct AudioState *state, int8_t *channeldelta, int8_t delta) 0313 { 0314 uint8_t predbyte, byte; 0315 int prederror; 0316 0317 state->delta[3] = state->delta[2]; 0318 state->delta[2] = state->delta[1]; 0319 state->delta[1] = state->lastdelta - state->delta[0]; 0320 state->delta[0] = state->lastdelta; 0321 0322 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; 0323 byte = (predbyte - delta) & 0xFF; 0324 0325 prederror = delta << 3; 0326 state->error[0] += abs(prederror); 0327 state->error[1] += abs(prederror - state->delta[0]); state->error[2] += abs(prederror + state->delta[0]); 0328 state->error[3] += abs(prederror - state->delta[1]); state->error[4] += abs(prederror + state->delta[1]); 0329 state->error[5] += abs(prederror - state->delta[2]); state->error[6] += abs(prederror + state->delta[2]); 0330 state->error[7] += abs(prederror - state->delta[3]); state->error[8] += abs(prederror + state->delta[3]); 0331 state->error[9] += abs(prederror - *channeldelta); state->error[10] += abs(prederror + *channeldelta); 0332 0333 *channeldelta = state->lastdelta = (int8_t)(byte - state->lastbyte); 0334 state->lastbyte = byte; 0335 0336 if (!(++state->count & 0x1F)) { 0337 uint8_t i, idx = 0; 0338 for (i = 1; i < 11; i++) { 0339 if (state->error[i] < state->error[idx]) 0340 idx = i; 0341 } 0342 memset(state->error, 0, sizeof(state->error)); 0343 0344 switch (idx) { 0345 case 1: if (state->weight[0] >= -16) state->weight[0]--; break; 0346 case 2: if (state->weight[0] < 16) state->weight[0]++; break; 0347 case 3: if (state->weight[1] >= -16) state->weight[1]--; break; 0348 case 4: if (state->weight[1] < 16) state->weight[1]++; break; 0349 case 5: if (state->weight[2] >= -16) state->weight[2]--; break; 0350 case 6: if (state->weight[2] < 16) state->weight[2]++; break; 0351 case 7: if (state->weight[3] >= -16) state->weight[3]--; break; 0352 case 8: if (state->weight[3] < 16) state->weight[3]++; break; 0353 case 9: if (state->weight[4] >= -16) state->weight[4]--; break; 0354 case 10: if (state->weight[4] < 16) state->weight[4]++; break; 0355 } 0356 } 0357 0358 return byte; 0359 } 0360 0361 int64_t rar_expand_v2(ar_archive_rar *rar, int64_t end) 0362 { 0363 static const uint8_t lengthbases[] = 0364 { 0, 1, 2, 3, 4, 5, 6, 0365 7, 8, 10, 12, 14, 16, 20, 0366 24, 28, 32, 40, 48, 56, 64, 0367 80, 96, 112, 128, 160, 192, 224 }; 0368 static const uint8_t lengthbits[] = 0369 { 0, 0, 0, 0, 0, 0, 0, 0370 0, 1, 1, 1, 1, 2, 2, 0371 2, 2, 3, 3, 3, 3, 4, 0372 4, 4, 4, 5, 5, 5, 5 }; 0373 static const int32_t offsetbases[] = 0374 { 0, 1, 2, 3, 4, 6, 0375 8, 12, 16, 24, 32, 48, 0376 64, 96, 128, 192, 256, 384, 0377 512, 768, 1024, 1536, 2048, 3072, 0378 4096, 6144, 8192, 12288, 16384, 24576, 0379 32768, 49152, 65536, 98304, 131072, 196608, 0380 262144, 327680, 393216, 458752, 524288, 589824, 0381 655360, 720896, 786432, 851968, 917504, 983040 }; 0382 static const uint8_t offsetbits[] = 0383 { 0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 0384 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10, 0385 11, 11, 12, 12, 13, 13, 14, 14, 15, 15, 16, 16, 0386 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16 }; 0387 static const uint8_t shortbases[] = 0388 { 0, 4, 8, 16, 32, 64, 128, 192 }; 0389 static const uint8_t shortbits[] = 0390 { 2, 2, 3, 4, 5, 6, 6, 6 }; 0391 0392 struct ar_archive_rar_uncomp_v2 *uncomp_v2 = &rar->uncomp.state.v2; 0393 LZSS *lzss = &rar->uncomp.lzss; 0394 int symbol, offs, len; 0395 0396 if ((uint64_t)end > rar->super.entry_size_uncompressed + rar->solid.size_total) 0397 end = rar->super.entry_size_uncompressed + rar->solid.size_total; 0398 0399 for (;;) { 0400 if (lzss_position(lzss) >= end) 0401 return end; 0402 0403 if (uncomp_v2->audioblock) { 0404 uint8_t byte; 0405 symbol = rar_read_next_symbol(rar, &uncomp_v2->audiocode[uncomp_v2->channel]); 0406 if (symbol < 0) 0407 return -1; 0408 if (symbol == 256) { 0409 rar->uncomp.start_new_table = true; 0410 return lzss_position(lzss); 0411 } 0412 byte = rar_decode_audio(&uncomp_v2->audiostate[uncomp_v2->channel], &uncomp_v2->channeldelta, (int8_t)(uint8_t)symbol); 0413 uncomp_v2->channel++; 0414 if (uncomp_v2->channel == uncomp_v2->numchannels) 0415 uncomp_v2->channel = 0; 0416 lzss_emit_literal(lzss, byte); 0417 continue; 0418 } 0419 0420 symbol = rar_read_next_symbol(rar, &uncomp_v2->maincode); 0421 if (symbol < 0) 0422 return -1; 0423 if (symbol < 256) { 0424 lzss_emit_literal(lzss, (uint8_t)symbol); 0425 continue; 0426 } 0427 if (symbol == 256) { 0428 offs = uncomp_v2->lastoffset; 0429 len = uncomp_v2->lastlength; 0430 } 0431 else if (symbol <= 260) { 0432 int idx = symbol - 256; 0433 int lensymbol = rar_read_next_symbol(rar, &uncomp_v2->lengthcode); 0434 offs = uncomp_v2->oldoffset[(uncomp_v2->oldoffsetindex - idx) & 0x03]; 0435 if (lensymbol < 0 || lensymbol > (int)(sizeof(lengthbases) / sizeof(lengthbases[0])) || lensymbol > (int)(sizeof(lengthbits) / sizeof(lengthbits[0]))) { 0436 warn("Invalid data in bitstream"); 0437 return -1; 0438 } 0439 len = lengthbases[lensymbol] + 2; 0440 if (lengthbits[lensymbol] > 0) { 0441 if (!br_check(rar, lengthbits[lensymbol])) 0442 return -1; 0443 len += (uint8_t)br_bits(rar, lengthbits[lensymbol]); 0444 } 0445 if (offs >= 0x40000) 0446 len++; 0447 if (offs >= 0x2000) 0448 len++; 0449 if (offs >= 0x101) 0450 len++; 0451 } 0452 else if (symbol <= 268) { 0453 int idx = symbol - 261; 0454 offs = shortbases[idx] + 1; 0455 if (shortbits[idx] > 0) { 0456 if (!br_check(rar, shortbits[idx])) 0457 return -1; 0458 offs += (uint8_t)br_bits(rar, shortbits[idx]); 0459 } 0460 len = 2; 0461 } 0462 else if (symbol == 269) { 0463 rar->uncomp.start_new_table = true; 0464 return lzss_position(lzss); 0465 } 0466 else { 0467 int idx = symbol - 270; 0468 int offssymbol; 0469 if (idx > (int)(sizeof(lengthbases) / sizeof(lengthbases[0])) || idx > (int)(sizeof(lengthbits) / sizeof(lengthbits[0]))) { 0470 warn("Invalid data in bitstream"); 0471 return -1; 0472 } 0473 len = lengthbases[idx] + 3; 0474 if (lengthbits[idx] > 0) { 0475 if (!br_check(rar, lengthbits[idx])) 0476 return -1; 0477 len += (uint8_t)br_bits(rar, lengthbits[idx]); 0478 } 0479 offssymbol = rar_read_next_symbol(rar, &uncomp_v2->offsetcode); 0480 if (offssymbol < 0 || offssymbol > (int)(sizeof(offsetbases) / sizeof(offsetbases[0])) || offssymbol > (int)(sizeof(offsetbits) / sizeof(offsetbits[0]))) { 0481 warn("Invalid data in bitstream"); 0482 return -1; 0483 } 0484 offs = offsetbases[offssymbol] + 1; 0485 if (offsetbits[offssymbol] > 0) { 0486 if (!br_check(rar, offsetbits[offssymbol])) 0487 return -1; 0488 offs += (int)br_bits(rar, offsetbits[offssymbol]); 0489 } 0490 if (offs >= 0x40000) 0491 len++; 0492 if (offs >= 0x2000) 0493 len++; 0494 } 0495 0496 uncomp_v2->lastoffset = uncomp_v2->oldoffset[uncomp_v2->oldoffsetindex++ & 0x03] = offs; 0497 uncomp_v2->lastlength = len; 0498 0499 lzss_emit_match(lzss, offs, len); 0500 } 0501 } 0502 0503 /***** RAR version 3 decompression *****/ 0504 0505 static void rar_free_codes(struct ar_archive_rar_uncomp *uncomp) 0506 { 0507 struct ar_archive_rar_uncomp_v3 *uncomp_v3 = &uncomp->state.v3; 0508 0509 if (uncomp->version == 2) { 0510 rar_free_codes_v2(&uncomp->state.v2); 0511 return; 0512 } 0513 0514 rar_free_code(&uncomp_v3->maincode); 0515 rar_free_code(&uncomp_v3->offsetcode); 0516 rar_free_code(&uncomp_v3->lowoffsetcode); 0517 rar_free_code(&uncomp_v3->lengthcode); 0518 } 0519 0520 static bool rar_parse_codes(ar_archive_rar *rar) 0521 { 0522 struct ar_archive_rar_uncomp_v3 *uncomp_v3 = &rar->uncomp.state.v3; 0523 0524 if (rar->uncomp.version == 2) 0525 return rar_parse_codes_v2(rar); 0526 0527 rar_free_codes(&rar->uncomp); 0528 0529 br_clear_leftover_bits(&rar->uncomp); 0530 0531 if (!br_check(rar, 1)) 0532 return false; 0533 uncomp_v3->is_ppmd_block = br_bits(rar, 1) != 0; 0534 if (uncomp_v3->is_ppmd_block) { 0535 uint8_t ppmd_flags; 0536 uint32_t max_alloc = 0; 0537 0538 if (!br_check(rar, 7)) 0539 return false; 0540 ppmd_flags = (uint8_t)br_bits(rar, 7); 0541 if ((ppmd_flags & 0x20)) { 0542 if (!br_check(rar, 8)) 0543 return false; 0544 max_alloc = ((uint8_t)br_bits(rar, 8) + 1) << 20; 0545 } 0546 if ((ppmd_flags & 0x40)) { 0547 if (!br_check(rar, 8)) 0548 return false; 0549 uncomp_v3->ppmd_escape = (uint8_t)br_bits(rar, 8); 0550 } 0551 if ((ppmd_flags & 0x20)) { 0552 uint32_t maxorder = (ppmd_flags & 0x1F) + 1; 0553 if (maxorder == 1) 0554 return false; 0555 if (maxorder > 16) 0556 maxorder = 16 + (maxorder - 16) * 3; 0557 0558 Ppmd7_Free(&uncomp_v3->ppmd7_context, &gSzAlloc); 0559 Ppmd7_Construct(&uncomp_v3->ppmd7_context); 0560 if (!Ppmd7_Alloc(&uncomp_v3->ppmd7_context, max_alloc, &gSzAlloc)) { 0561 warn("OOM during decompression"); 0562 return false; 0563 } 0564 ByteIn_CreateVTable(&uncomp_v3->bytein, rar); 0565 PpmdRAR_RangeDec_CreateVTable(&uncomp_v3->range_dec, &uncomp_v3->bytein.super); 0566 PpmdRAR_RangeDec_Init(&uncomp_v3->range_dec); 0567 Ppmd7_Init(&uncomp_v3->ppmd7_context, maxorder); 0568 } 0569 else { 0570 if (!Ppmd7_WasAllocated(&uncomp_v3->ppmd7_context)) { 0571 warn("Invalid data in bitstream"); /* invalid PPMd sequence */ 0572 return false; 0573 } 0574 PpmdRAR_RangeDec_Init(&uncomp_v3->range_dec); 0575 } 0576 } 0577 else { 0578 struct huffman_code precode; 0579 uint8_t bitlengths[20]; 0580 uint8_t zerocount; 0581 int i, j, val, n; 0582 bool ok = false; 0583 0584 if (!br_check(rar, 1)) 0585 return false; 0586 if (!br_bits(rar, 1)) 0587 memset(uncomp_v3->lengthtable, 0, sizeof(uncomp_v3->lengthtable)); 0588 memset(&bitlengths, 0, sizeof(bitlengths)); 0589 for (i = 0; i < sizeof(bitlengths); i++) { 0590 if (!br_check(rar, 4)) 0591 return false; 0592 bitlengths[i] = (uint8_t)br_bits(rar, 4); 0593 if (bitlengths[i] == 0x0F) { 0594 if (!br_check(rar, 4)) 0595 return false; 0596 zerocount = (uint8_t)br_bits(rar, 4); 0597 if (zerocount) { 0598 for (j = 0; j < zerocount + 2 && i < sizeof(bitlengths); j++) { 0599 bitlengths[i++] = 0; 0600 } 0601 i--; 0602 } 0603 } 0604 } 0605 0606 memset(&precode, 0, sizeof(precode)); 0607 if (!rar_create_code(&precode, bitlengths, sizeof(bitlengths))) 0608 goto PrecodeError; 0609 for (i = 0; i < HUFFMAN_TABLE_SIZE; ) { 0610 val = rar_read_next_symbol(rar, &precode); 0611 if (val < 0) 0612 goto PrecodeError; 0613 if (val < 16) { 0614 uncomp_v3->lengthtable[i] = (uncomp_v3->lengthtable[i] + val) & 0x0F; 0615 i++; 0616 } 0617 else if (val < 18) { 0618 if (i == 0) { 0619 warn("Invalid data in bitstream"); 0620 goto PrecodeError; 0621 } 0622 if (val == 16) { 0623 if (!br_check(rar, 3)) 0624 goto PrecodeError; 0625 n = (uint8_t)br_bits(rar, 3) + 3; 0626 } 0627 else { 0628 if (!br_check(rar, 7)) 0629 goto PrecodeError; 0630 n = (uint8_t)br_bits(rar, 7) + 11; 0631 } 0632 for (j = 0; j < n && i < HUFFMAN_TABLE_SIZE; i++, j++) { 0633 uncomp_v3->lengthtable[i] = uncomp_v3->lengthtable[i - 1]; 0634 } 0635 } 0636 else { 0637 if (val == 18) { 0638 if (!br_check(rar, 3)) 0639 goto PrecodeError; 0640 n = (uint8_t)br_bits(rar, 3) + 3; 0641 } 0642 else { 0643 if (!br_check(rar, 7)) 0644 goto PrecodeError; 0645 n = (uint8_t)br_bits(rar, 7) + 11; 0646 } 0647 for (j = 0; j < n && i < HUFFMAN_TABLE_SIZE; i++, j++) { 0648 uncomp_v3->lengthtable[i] = 0; 0649 } 0650 } 0651 } 0652 ok = true; 0653 PrecodeError: 0654 rar_free_code(&precode); 0655 if (!ok) 0656 return false; 0657 0658 if (!rar_create_code(&uncomp_v3->maincode, uncomp_v3->lengthtable, MAINCODE_SIZE)) 0659 return false; 0660 if (!rar_create_code(&uncomp_v3->offsetcode, uncomp_v3->lengthtable + MAINCODE_SIZE, OFFSETCODE_SIZE)) 0661 return false; 0662 if (!rar_create_code(&uncomp_v3->lowoffsetcode, uncomp_v3->lengthtable + MAINCODE_SIZE + OFFSETCODE_SIZE, LOWOFFSETCODE_SIZE)) 0663 return false; 0664 if (!rar_create_code(&uncomp_v3->lengthcode, uncomp_v3->lengthtable + MAINCODE_SIZE + OFFSETCODE_SIZE + LOWOFFSETCODE_SIZE, LENGTHCODE_SIZE)) 0665 return false; 0666 } 0667 0668 rar->uncomp.start_new_table = false; 0669 return true; 0670 } 0671 0672 static bool rar_read_filter(ar_archive_rar *rar, bool (* decode_byte)(ar_archive_rar *rar, uint8_t *byte), int64_t *end) 0673 { 0674 uint8_t flags, val, *code; 0675 uint16_t length, i; 0676 0677 if (!decode_byte(rar, &flags)) 0678 return false; 0679 length = (flags & 0x07) + 1; 0680 if (length == 7) { 0681 if (!decode_byte(rar, &val)) 0682 return false; 0683 length = val + 7; 0684 } 0685 else if (length == 8) { 0686 if (!decode_byte(rar, &val)) 0687 return false; 0688 length = val << 8; 0689 if (!decode_byte(rar, &val)) 0690 return false; 0691 length |= val; 0692 } 0693 0694 code = malloc(length); 0695 if (!code) { 0696 warn("OOM during decompression"); 0697 return false; 0698 } 0699 for (i = 0; i < length; i++) { 0700 if (!decode_byte(rar, &code[i])) { 0701 free(code); 0702 return false; 0703 } 0704 } 0705 if (!rar_parse_filter(rar, code, length, flags)) { 0706 free(code); 0707 return false; 0708 } 0709 free(code); 0710 0711 if (rar->uncomp.state.v3.filters.filterstart < (size_t)*end) 0712 *end = rar->uncomp.state.v3.filters.filterstart; 0713 0714 return true; 0715 } 0716 0717 static inline bool rar_decode_ppmd7_symbol(struct ar_archive_rar_uncomp_v3 *uncomp_v3, Byte *symbol) 0718 { 0719 int value = Ppmd7_DecodeSymbol(&uncomp_v3->ppmd7_context, &uncomp_v3->range_dec.super); 0720 if (value < 0) { 0721 warn("Invalid data in bitstream"); /* invalid PPMd symbol */ 0722 return false; 0723 } 0724 *symbol = (Byte)value; 0725 return true; 0726 } 0727 0728 static bool rar_decode_byte(ar_archive_rar *rar, uint8_t *byte) 0729 { 0730 if (!br_check(rar, 8)) 0731 return false; 0732 *byte = (uint8_t)br_bits(rar, 8); 0733 return true; 0734 } 0735 0736 static bool rar_decode_ppmd7_byte(ar_archive_rar *rar, uint8_t *byte) 0737 { 0738 return rar_decode_ppmd7_symbol(&rar->uncomp.state.v3, byte); 0739 } 0740 0741 static bool rar_handle_ppmd_sequence(ar_archive_rar *rar, int64_t *end) 0742 { 0743 struct ar_archive_rar_uncomp_v3 *uncomp_v3 = &rar->uncomp.state.v3; 0744 LZSS *lzss = &rar->uncomp.lzss; 0745 Byte sym, code, length; 0746 int lzss_offset; 0747 0748 if (!rar_decode_ppmd7_symbol(uncomp_v3, &sym)) 0749 return false; 0750 if (sym != uncomp_v3->ppmd_escape) { 0751 lzss_emit_literal(lzss, sym); 0752 return true; 0753 } 0754 0755 if (!rar_decode_ppmd7_symbol(uncomp_v3, &code)) 0756 return false; 0757 switch (code) { 0758 case 0: 0759 return rar_parse_codes(rar); 0760 0761 case 2: 0762 rar->uncomp.start_new_table = true; 0763 return true; 0764 0765 case 3: 0766 return rar_read_filter(rar, rar_decode_ppmd7_byte, end); 0767 0768 case 4: 0769 if (!rar_decode_ppmd7_symbol(uncomp_v3, &code)) 0770 return false; 0771 lzss_offset = code << 16; 0772 if (!rar_decode_ppmd7_symbol(uncomp_v3, &code)) 0773 return false; 0774 lzss_offset |= code << 8; 0775 if (!rar_decode_ppmd7_symbol(uncomp_v3, &code)) 0776 return false; 0777 lzss_offset |= code; 0778 if (!rar_decode_ppmd7_symbol(uncomp_v3, &length)) 0779 return false; 0780 lzss_emit_match(lzss, lzss_offset + 2, length + 32); 0781 return true; 0782 0783 case 5: 0784 if (!rar_decode_ppmd7_symbol(uncomp_v3, &length)) 0785 return false; 0786 lzss_emit_match(lzss, 1, length + 4); 0787 return true; 0788 0789 default: 0790 lzss_emit_literal(lzss, sym); 0791 return true; 0792 } 0793 } 0794 0795 int64_t rar_expand(ar_archive_rar *rar, int64_t end) 0796 { 0797 static const uint8_t lengthbases[] = 0798 { 0, 1, 2, 3, 4, 5, 6, 0799 7, 8, 10, 12, 14, 16, 20, 0800 24, 28, 32, 40, 48, 56, 64, 0801 80, 96, 112, 128, 160, 192, 224 }; 0802 static const uint8_t lengthbits[] = 0803 { 0, 0, 0, 0, 0, 0, 0, 0804 0, 1, 1, 1, 1, 2, 2, 0805 2, 2, 3, 3, 3, 3, 4, 0806 4, 4, 4, 5, 5, 5, 5 }; 0807 static const int32_t offsetbases[] = 0808 { 0, 1, 2, 3, 4, 6, 0809 8, 12, 16, 24, 32, 48, 0810 64, 96, 128, 192, 256, 384, 0811 512, 768, 1024, 1536, 2048, 3072, 0812 4096, 6144, 8192, 12288, 16384, 24576, 0813 32768, 49152, 65536, 98304, 131072, 196608, 0814 262144, 327680, 393216, 458752, 524288, 589824, 0815 655360, 720896, 786432, 851968, 917504, 983040, 0816 1048576, 1310720, 1572864, 1835008, 2097152, 2359296, 0817 2621440, 2883584, 3145728, 3407872, 3670016, 3932160 }; 0818 static const uint8_t offsetbits[] = 0819 { 0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 0820 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10, 0821 11, 11, 12, 12, 13, 13, 14, 14, 15, 15, 16, 16, 0822 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 0823 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18 }; 0824 static const uint8_t shortbases[] = 0825 { 0, 4, 8, 16, 32, 64, 128, 192 }; 0826 static const uint8_t shortbits[] = 0827 { 2, 2, 3, 4, 5, 6, 6, 6 }; 0828 0829 struct ar_archive_rar_uncomp_v3 *uncomp_v3 = &rar->uncomp.state.v3; 0830 LZSS *lzss = &rar->uncomp.lzss; 0831 int symbol, offs, len, i; 0832 0833 if (rar->uncomp.version == 2) 0834 return rar_expand_v2(rar, end); 0835 0836 for (;;) { 0837 if (lzss_position(lzss) >= end) 0838 return end; 0839 0840 if (uncomp_v3->is_ppmd_block) { 0841 if (!rar_handle_ppmd_sequence(rar, &end)) 0842 return -1; 0843 if (rar->uncomp.start_new_table) 0844 return lzss_position(lzss); 0845 continue; 0846 } 0847 0848 symbol = rar_read_next_symbol(rar, &uncomp_v3->maincode); 0849 if (symbol < 0) 0850 return -1; 0851 if (symbol < 256) { 0852 lzss_emit_literal(lzss, (uint8_t)symbol); 0853 continue; 0854 } 0855 if (symbol == 256) { 0856 if (!br_check(rar, 1)) 0857 return -1; 0858 if (!br_bits(rar, 1)) { 0859 if (!br_check(rar, 1)) 0860 return -1; 0861 rar->uncomp.start_new_table = br_bits(rar, 1) != 0; 0862 return lzss_position(lzss); 0863 } 0864 if (!rar_parse_codes(rar)) 0865 return -1; 0866 continue; 0867 } 0868 if (symbol == 257) { 0869 if (!rar_read_filter(rar, rar_decode_byte, &end)) 0870 return -1; 0871 continue; 0872 } 0873 if (symbol == 258) { 0874 if (uncomp_v3->lastlength == 0) 0875 continue; 0876 offs = uncomp_v3->lastoffset; 0877 len = uncomp_v3->lastlength; 0878 } 0879 else if (symbol <= 262) { 0880 int idx = symbol - 259; 0881 int lensymbol = rar_read_next_symbol(rar, &uncomp_v3->lengthcode); 0882 offs = uncomp_v3->oldoffset[idx]; 0883 if (lensymbol < 0 || lensymbol > (int)(sizeof(lengthbases) / sizeof(lengthbases[0])) || lensymbol > (int)(sizeof(lengthbits) / sizeof(lengthbits[0]))) { 0884 warn("Invalid data in bitstream"); 0885 return -1; 0886 } 0887 len = lengthbases[lensymbol] + 2; 0888 if (lengthbits[lensymbol] > 0) { 0889 if (!br_check(rar, lengthbits[lensymbol])) 0890 return -1; 0891 len += (uint8_t)br_bits(rar, lengthbits[lensymbol]); 0892 } 0893 for (i = idx; i > 0; i--) 0894 uncomp_v3->oldoffset[i] = uncomp_v3->oldoffset[i - 1]; 0895 uncomp_v3->oldoffset[0] = offs; 0896 } 0897 else if (symbol <= 270) { 0898 int idx = symbol - 263; 0899 offs = shortbases[idx] + 1; 0900 if (shortbits[idx] > 0) { 0901 if (!br_check(rar, shortbits[idx])) 0902 return -1; 0903 offs += (uint8_t)br_bits(rar, shortbits[idx]); 0904 } 0905 len = 2; 0906 for (i = 3; i > 0; i--) 0907 uncomp_v3->oldoffset[i] = uncomp_v3->oldoffset[i - 1]; 0908 uncomp_v3->oldoffset[0] = offs; 0909 } 0910 else { 0911 int idx = symbol - 271; 0912 int offssymbol; 0913 if (idx > (int)(sizeof(lengthbases) / sizeof(lengthbases[0])) || idx > (int)(sizeof(lengthbits) / sizeof(lengthbits[0]))) { 0914 warn("Invalid data in bitstream"); 0915 return -1; 0916 } 0917 len = lengthbases[idx] + 3; 0918 if (lengthbits[idx] > 0) { 0919 if (!br_check(rar, lengthbits[idx])) 0920 return -1; 0921 len += (uint8_t)br_bits(rar, lengthbits[idx]); 0922 } 0923 offssymbol = rar_read_next_symbol(rar, &uncomp_v3->offsetcode); 0924 if (offssymbol < 0 || offssymbol > (int)(sizeof(offsetbases) / sizeof(offsetbases[0])) || offssymbol > (int)(sizeof(offsetbits) / sizeof(offsetbits[0]))) { 0925 warn("Invalid data in bitstream"); 0926 return -1; 0927 } 0928 offs = offsetbases[offssymbol] + 1; 0929 if (offsetbits[offssymbol] > 0) { 0930 if (offssymbol > 9) { 0931 if (offsetbits[offssymbol] > 4) { 0932 if (!br_check(rar, offsetbits[offssymbol] - 4)) 0933 return -1; 0934 offs += (int)br_bits(rar, offsetbits[offssymbol] - 4) << 4; 0935 } 0936 if (uncomp_v3->numlowoffsetrepeats > 0) { 0937 uncomp_v3->numlowoffsetrepeats--; 0938 offs += uncomp_v3->lastlowoffset; 0939 } 0940 else { 0941 int lowoffsetsymbol = rar_read_next_symbol(rar, &uncomp_v3->lowoffsetcode); 0942 if (lowoffsetsymbol < 0) 0943 return -1; 0944 if (lowoffsetsymbol == 16) { 0945 uncomp_v3->numlowoffsetrepeats = 15; 0946 offs += uncomp_v3->lastlowoffset; 0947 } 0948 else { 0949 offs += lowoffsetsymbol; 0950 uncomp_v3->lastlowoffset = lowoffsetsymbol; 0951 } 0952 } 0953 } 0954 else { 0955 if (!br_check(rar, offsetbits[offssymbol])) 0956 return -1; 0957 offs += (int)br_bits(rar, offsetbits[offssymbol]); 0958 } 0959 } 0960 0961 if (offs >= 0x40000) 0962 len++; 0963 if (offs >= 0x2000) 0964 len++; 0965 0966 for (i = 3; i > 0; i--) 0967 uncomp_v3->oldoffset[i] = uncomp_v3->oldoffset[i - 1]; 0968 uncomp_v3->oldoffset[0] = offs; 0969 } 0970 0971 uncomp_v3->lastoffset = offs; 0972 uncomp_v3->lastlength = len; 0973 0974 lzss_emit_match(lzss, offs, len); 0975 } 0976 } 0977 0978 bool rar_uncompress_part(ar_archive_rar *rar, void *buffer, size_t buffer_size) 0979 { 0980 struct ar_archive_rar_uncomp *uncomp = &rar->uncomp; 0981 struct ar_archive_rar_uncomp_v3 *uncomp_v3 = NULL; 0982 size_t end; 0983 0984 if (!rar_init_uncompress(uncomp, rar->entry.version)) 0985 return false; 0986 if (uncomp->version == 3) 0987 uncomp_v3 = &uncomp->state.v3; 0988 0989 for (;;) { 0990 if (uncomp_v3 && uncomp_v3->filters.bytes_ready > 0) { 0991 size_t count = smin(uncomp_v3->filters.bytes_ready, buffer_size); 0992 memcpy(buffer, uncomp_v3->filters.bytes, count); 0993 uncomp_v3->filters.bytes_ready -= count; 0994 uncomp_v3->filters.bytes += count; 0995 rar->progress.bytes_done += count; 0996 buffer_size -= count; 0997 buffer = (uint8_t *)buffer + count; 0998 if (rar->progress.bytes_done == rar->super.entry_size_uncompressed) 0999 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 }