1 /*
2 * Extract RAR archives
3 *
4 * Modified for JtR, (c) magnum 2012. This code use a memory buffer instead
5 * of a file handle, and decrypts while reading. It does not store inflated
6 * data, it just CRC's it. Support for older RAR versions was stripped.
7 * Autoconf stuff was removed.
8 *
9 * Copyright (C) 2005-2006 trog@uncon.org
10 *
11 * This code is based on the work of Alexander L. Roshal (C)
12 *
13 * The unRAR sources may be used in any software to handle RAR
14 * archives without limitations free of charge, but cannot be used
15 * to re-create the RAR compression algorithm, which is proprietary.
16 * Distribution of modified unRAR sources in separate form or as a
17 * part of other software is permitted, provided that it is clearly
18 * stated in the documentation and source comments that the code may
19 * not be used to develop a RAR (WinRAR) compatible archiver.
20 */
21
22 #include "arch.h"
23
24 #include <stdio.h>
25 #include <string.h>
26 #include "aes.h"
27
28 #include "unrar.h"
29 #include "unrarppm.h"
30 #include "common.h"
31
32 #ifdef RAR_HIGH_DEBUG
33 #define rar_dbgmsg printf
34 #else
35 //static void rar_dbgmsg(const char* fmt,...){}
36 #endif
37
38 #define MAX_O 64
39
40 const unsigned int UNIT_SIZE=MAX(sizeof(struct ppm_context), sizeof(struct rar_mem_blk_tag));
41 const unsigned int FIXED_UNIT_SIZE=12;
42 const int INT_BITS=7, PERIOD_BITS=7, TOT_BITS=14;
43 const int INTERVAL=1 << 7, BIN_SCALE=1 << 14, MAX_FREQ=124;
44 const unsigned int TOP=1 << 24, BOT=1 << 15;
45
46 /************* Start of Allocator code block ********************/
sub_allocator_init(sub_allocator_t * sub_alloc)47 static void sub_allocator_init(sub_allocator_t *sub_alloc)
48 {
49 sub_alloc->sub_allocator_size = 0;
50 }
51
sub_allocator_insert_node(sub_allocator_t * sub_alloc,void * p,int indx)52 static void sub_allocator_insert_node(sub_allocator_t *sub_alloc, void *p, int indx)
53 {
54 ((struct rar_node *) p)->next = sub_alloc->free_list[indx].next;
55 sub_alloc->free_list[indx].next = (struct rar_node *) p;
56 }
57
sub_allocator_remove_node(sub_allocator_t * sub_alloc,int indx)58 static void *sub_allocator_remove_node(sub_allocator_t *sub_alloc, int indx)
59 {
60 struct rar_node *ret_val;
61
62 ret_val = sub_alloc->free_list[indx].next;
63 sub_alloc->free_list[indx].next = ret_val->next;
64 return ret_val;
65 }
66
sub_allocator_u2b(int nu)67 static int sub_allocator_u2b(int nu)
68 {
69 return UNIT_SIZE*nu;
70 }
71
sub_allocator_mbptr(rar_mem_blk_t * base_ptr,int items)72 static rar_mem_blk_t* sub_allocator_mbptr(rar_mem_blk_t* base_ptr, int items)
73 {
74 return ((rar_mem_blk_t*) (((unsigned char *)(base_ptr)) + sub_allocator_u2b(items) ));
75 }
76
sub_allocator_split_block(sub_allocator_t * sub_alloc,void * pv,int old_indx,int new_indx)77 static void sub_allocator_split_block(sub_allocator_t *sub_alloc, void *pv,
78 int old_indx, int new_indx)
79 {
80 int i, udiff;
81 unsigned char *p;
82
83 udiff = sub_alloc->indx2units[old_indx] - sub_alloc->indx2units[new_indx];
84 p = ((unsigned char *) pv) + sub_allocator_u2b(sub_alloc->indx2units[new_indx]);
85 if (sub_alloc->indx2units[i=sub_alloc->units2indx[udiff-1]] != udiff) {
86 sub_allocator_insert_node(sub_alloc, p, --i);
87 p += sub_allocator_u2b(i=sub_alloc->indx2units[i]);
88 udiff -= i;
89 }
90 sub_allocator_insert_node(sub_alloc, p, sub_alloc->units2indx[udiff-1]);
91 }
92
sub_allocator_get_allocated_memory(sub_allocator_t * sub_alloc)93 static long sub_allocator_get_allocated_memory(sub_allocator_t *sub_alloc)
94 {
95 return sub_alloc->sub_allocator_size;
96 }
97
sub_allocator_stop_sub_allocator(sub_allocator_t * sub_alloc)98 static void sub_allocator_stop_sub_allocator(sub_allocator_t *sub_alloc)
99 {
100 if (sub_alloc->sub_allocator_size) {
101 sub_alloc->sub_allocator_size = 0;
102 MEM_FREE(sub_alloc->heap_start);
103 }
104 }
105
sub_allocator_start_sub_allocator(sub_allocator_t * sub_alloc,int sa_size)106 static int sub_allocator_start_sub_allocator(sub_allocator_t *sub_alloc, int sa_size)
107 {
108 unsigned int t, alloc_size;
109
110 t = sa_size << 20;
111 if (sub_alloc->sub_allocator_size == t) {
112 return 1;
113 }
114 sub_allocator_stop_sub_allocator(sub_alloc);
115 if (t>138412020) {
116 //rar_dbgmsg("too much memory needed for uncompressing this file\n");
117 return 0;
118 }
119 alloc_size = t/FIXED_UNIT_SIZE*UNIT_SIZE+UNIT_SIZE;
120 #if defined(__sparc) || defined(sparc) || defined(__sparcv9)
121 /* Allow for aligned access requirements */
122 alloc_size += UNIT_SIZE;
123 #endif
124 if ((sub_alloc->heap_start = (unsigned char *) rar_malloc(alloc_size)) == NULL) {
125 //rar_dbgmsg("sub_alloc start failed\n");
126 return 0;
127 }
128 sub_alloc->heap_end = sub_alloc->heap_start + alloc_size - UNIT_SIZE;
129 sub_alloc->sub_allocator_size = t;
130 return 1;
131 }
132
sub_allocator_init_sub_allocator(sub_allocator_t * sub_alloc)133 static void sub_allocator_init_sub_allocator(sub_allocator_t *sub_alloc)
134 {
135 int i, k;
136 unsigned int size1, real_size1, size2, real_size2;
137
138 memset(sub_alloc->free_list, 0, sizeof(sub_alloc->free_list));
139 sub_alloc->ptext = sub_alloc->heap_start;
140
141 size2 = FIXED_UNIT_SIZE*(sub_alloc->sub_allocator_size/8/FIXED_UNIT_SIZE*7);
142 real_size2 = size2/FIXED_UNIT_SIZE*UNIT_SIZE;
143 size1 = sub_alloc->sub_allocator_size - size2;
144 real_size1 = size1/FIXED_UNIT_SIZE*UNIT_SIZE+size1%FIXED_UNIT_SIZE;
145 #if defined(__sparc) || defined(sparc) || defined(__sparcv9)
146 /* Allow for aligned access requirements */
147 if (size1%FIXED_UNIT_SIZE != 0) {
148 real_size1 += UNIT_SIZE - size1%FIXED_UNIT_SIZE;
149 }
150 #endif
151 sub_alloc->hi_unit = sub_alloc->heap_start + sub_alloc->sub_allocator_size;
152 sub_alloc->lo_unit = sub_alloc->units_start = sub_alloc->heap_start + real_size1;
153 sub_alloc->fake_units_start = sub_alloc->heap_start + size1;
154 sub_alloc->hi_unit = sub_alloc->lo_unit + real_size2;
155
156 for (i=0,k=1; i < N1 ; i++, k+=1) {
157 sub_alloc->indx2units[i] = k;
158 }
159 for (k++; i < N1+N2 ; i++, k+=2) {
160 sub_alloc->indx2units[i] = k;
161 }
162 for (k++; i < N1+N2+N3 ; i++, k+=3) {
163 sub_alloc->indx2units[i] = k;
164 }
165 for (k++; i < N1+N2+N3+N4 ; i++, k+=4) {
166 sub_alloc->indx2units[i] = k;
167 }
168
169 for (sub_alloc->glue_count=k=i=0; k < 128; k++) {
170 i += (sub_alloc->indx2units[i] < k+1);
171 sub_alloc->units2indx[k] = i;
172 }
173 }
174
rar_mem_blk_insertAt(rar_mem_blk_t * a,rar_mem_blk_t * p)175 static void rar_mem_blk_insertAt(rar_mem_blk_t *a, rar_mem_blk_t *p)
176 {
177 a->next = (a->prev=p)->next;
178 p->next = a->next->prev = a;
179 }
180
rar_mem_blk_remove(rar_mem_blk_t * a)181 static void rar_mem_blk_remove(rar_mem_blk_t *a)
182 {
183 a->prev->next = a->next;
184 a->next->prev = a->prev;
185 }
186
sub_allocator_glue_free_blocks(sub_allocator_t * sub_alloc)187 static void sub_allocator_glue_free_blocks(sub_allocator_t *sub_alloc)
188 {
189 rar_mem_blk_t s0, *p, *p1;
190 int i, k, sz;
191
192 if (sub_alloc->lo_unit != sub_alloc->hi_unit) {
193 *sub_alloc->lo_unit = 0;
194 }
195 for (i=0, s0.next=s0.prev=&s0; i < N_INDEXES; i++) {
196 while (sub_alloc->free_list[i].next) {
197 p = (rar_mem_blk_t *) sub_allocator_remove_node(sub_alloc, i);
198 rar_mem_blk_insertAt(p, &s0);
199 p->stamp = 0xFFFF;
200 p->nu = sub_alloc->indx2units[i];
201 }
202 }
203
204 for (p=s0.next ; p != &s0 ; p=p->next) {
205 while ((p1 = sub_allocator_mbptr(p,p->nu))->stamp == 0xFFFF &&
206 ((int)p->nu)+p1->nu < 0x10000) {
207 rar_mem_blk_remove(p1);
208 p->nu += p1->nu;
209 }
210 }
211
212 while ((p=s0.next) != &s0) {
213 for (rar_mem_blk_remove(p), sz=p->nu; sz > 128; sz-=128, p=sub_allocator_mbptr(p, 128)) {
214 sub_allocator_insert_node(sub_alloc, p, N_INDEXES-1);
215 }
216 if (sub_alloc->indx2units[i=sub_alloc->units2indx[sz-1]] != sz) {
217 k = sz-sub_alloc->indx2units[--i];
218 sub_allocator_insert_node(sub_alloc, sub_allocator_mbptr(p,sz-k), k-1);
219 }
220 sub_allocator_insert_node(sub_alloc, p, i);
221 }
222 }
223
sub_allocator_alloc_units_rare(sub_allocator_t * sub_alloc,int indx)224 static void *sub_allocator_alloc_units_rare(sub_allocator_t *sub_alloc, int indx)
225 {
226 int i, j;
227 void *ret_val;
228
229 if (!sub_alloc->glue_count) {
230 sub_alloc->glue_count = 255;
231 sub_allocator_glue_free_blocks(sub_alloc);
232 if (sub_alloc->free_list[indx].next) {
233 return sub_allocator_remove_node(sub_alloc, indx);
234 }
235 }
236 i=indx;
237 do {
238 if (++i == N_INDEXES) {
239 sub_alloc->glue_count--;
240 i = sub_allocator_u2b(sub_alloc->indx2units[indx]);
241 j = 12 * sub_alloc->indx2units[indx];
242 if (sub_alloc->fake_units_start - sub_alloc->ptext > j) {
243 sub_alloc->fake_units_start -= j;
244 sub_alloc->units_start -= i;
245 return sub_alloc->units_start;
246 }
247 return NULL;
248 }
249 } while ( !sub_alloc->free_list[i].next);
250 ret_val = sub_allocator_remove_node(sub_alloc, i);
251 sub_allocator_split_block(sub_alloc, ret_val, i, indx);
252 return ret_val;
253 }
254
sub_allocator_alloc_units(sub_allocator_t * sub_alloc,int nu)255 static void *sub_allocator_alloc_units(sub_allocator_t *sub_alloc, int nu)
256 {
257 int indx;
258 void *ret_val;
259
260 indx = sub_alloc->units2indx[nu-1];
261 if (sub_alloc->free_list[indx].next) {
262 return sub_allocator_remove_node(sub_alloc, indx);
263 }
264 ret_val = sub_alloc->lo_unit;
265 sub_alloc->lo_unit += sub_allocator_u2b(sub_alloc->indx2units[indx]);
266 if (sub_alloc->lo_unit <= sub_alloc->hi_unit) {
267 return ret_val;
268 }
269 sub_alloc->lo_unit -= sub_allocator_u2b(sub_alloc->indx2units[indx]);
270 return sub_allocator_alloc_units_rare(sub_alloc, indx);
271 }
272
sub_allocator_alloc_context(sub_allocator_t * sub_alloc)273 static void *sub_allocator_alloc_context(sub_allocator_t *sub_alloc)
274 {
275 if (sub_alloc->hi_unit != sub_alloc->lo_unit) {
276 return (sub_alloc->hi_unit -= UNIT_SIZE);
277 }
278 if (sub_alloc->free_list->next) {
279 return sub_allocator_remove_node(sub_alloc, 0);
280 }
281 return sub_allocator_alloc_units_rare(sub_alloc, 0);
282 }
283
sub_allocator_expand_units(sub_allocator_t * sub_alloc,void * old_ptr,int old_nu)284 static void *sub_allocator_expand_units(sub_allocator_t *sub_alloc, void *old_ptr, int old_nu)
285 {
286 int i0, i1;
287 void *ptr;
288
289 i0 = sub_alloc->units2indx[old_nu-1];
290 i1 = sub_alloc->units2indx[old_nu];
291 if (i0 == i1) {
292 return old_ptr;
293 }
294 ptr = sub_allocator_alloc_units(sub_alloc, old_nu+1);
295 if (ptr) {
296 memcpy(ptr, old_ptr, sub_allocator_u2b(old_nu));
297 sub_allocator_insert_node(sub_alloc, old_ptr, i0);
298 }
299 return ptr;
300 }
301
sub_allocator_shrink_units(sub_allocator_t * sub_alloc,void * old_ptr,int old_nu,int new_nu)302 static void *sub_allocator_shrink_units(sub_allocator_t *sub_alloc, void *old_ptr,
303 int old_nu, int new_nu)
304 {
305 int i0, i1;
306 void *ptr;
307
308 i0 = sub_alloc->units2indx[old_nu-1];
309 i1 = sub_alloc->units2indx[new_nu-1];
310 if (i0 == i1) {
311 return old_ptr;
312 }
313 if (sub_alloc->free_list[i1].next) {
314 ptr = sub_allocator_remove_node(sub_alloc, i1);
315 memcpy(ptr, old_ptr, sub_allocator_u2b(new_nu));
316 sub_allocator_insert_node(sub_alloc, old_ptr, i0);
317 return ptr;
318 } else {
319 sub_allocator_split_block(sub_alloc, old_ptr, i0, i1);
320 return old_ptr;
321 }
322 }
323
sub_allocator_free_units(sub_allocator_t * sub_alloc,void * ptr,int old_nu)324 static void sub_allocator_free_units(sub_allocator_t *sub_alloc, void *ptr, int old_nu)
325 {
326 sub_allocator_insert_node(sub_alloc, ptr, sub_alloc->units2indx[old_nu-1]);
327 }
328
329 /************** End of Allocator code block *********************/
330
331 /************** Start of Range Coder code block *********************/
range_coder_init_decoder(range_coder_t * coder,const unsigned char ** fd,unpack_data_t * unpack_data)332 static void range_coder_init_decoder(range_coder_t *coder, const unsigned char **fd,
333 unpack_data_t *unpack_data)
334 {
335 int i;
336 coder->low = coder->code = 0;
337 coder->range = (unsigned int) -1;
338
339 for (i=0; i < 4 ; i++) {
340 coder->code = (coder->code << 8) | rar_get_char(fd, unpack_data);
341 }
342 }
343
coder_get_current_count(range_coder_t * coder)344 static int coder_get_current_count(range_coder_t *coder)
345 {
346 return (coder->code - coder->low) / (coder->range /= coder->scale);
347 }
348
coder_get_current_shift_count(range_coder_t * coder,unsigned int shift)349 static unsigned int coder_get_current_shift_count(range_coder_t *coder, unsigned int shift)
350 {
351 return (coder->code - coder->low) / (coder->range >>= shift);
352 }
353
354 #define ARI_DEC_NORMALISE(fd, unpack_data, code, low, range) \
355 { \
356 while ((low^(low+range)) < TOP || (range < BOT && ((range=-low&(BOT-1)),1))) { \
357 code = (code << 8) | rar_get_char(fd, unpack_data); \
358 range <<= 8; \
359 low <<= 8; \
360 } \
361 }
362
coder_decode(range_coder_t * coder)363 static void coder_decode(range_coder_t *coder)
364 {
365 coder->low += coder->range * coder->low_count;
366 coder->range *= coder->high_count - coder->low_count;
367 }
368
369 /******(******** End of Range Coder code block ***********(**********/
370
see2_init(struct see2_context_tag * see2_cont,int init_val)371 static void see2_init(struct see2_context_tag *see2_cont, int init_val)
372 {
373 see2_cont->summ = init_val << (see2_cont->shift=PERIOD_BITS-4);
374 see2_cont->count = 4;
375 }
376
get_mean(struct see2_context_tag * see2_cont)377 static unsigned int get_mean(struct see2_context_tag *see2_cont)
378 {
379 unsigned int ret_val;
380
381 ret_val = see2_cont->summ >> see2_cont->shift;
382 see2_cont->summ -= ret_val;
383 return ret_val + (ret_val == 0);
384 }
385
update(struct see2_context_tag * see2_cont)386 static void update(struct see2_context_tag *see2_cont)
387 {
388 if (see2_cont->shift < PERIOD_BITS && --see2_cont->count == 0) {
389 see2_cont->summ += see2_cont->summ;
390 see2_cont->count = 3 << see2_cont->shift++;
391 }
392 }
393
restart_model_rare(ppm_data_t * ppm_data)394 static int restart_model_rare(ppm_data_t *ppm_data)
395 {
396 int i, k, m;
397 static const unsigned short init_bin_esc[] = {
398 0x3cdd, 0x1f3f, 0x59bf, 0x48f3, 0x64a1, 0x5abc, 0x6632, 0x6051
399 };
400 //rar_dbgmsg("in restart_model_rare\n");
401 memset(ppm_data->char_mask, 0, sizeof(ppm_data->char_mask));
402
403 sub_allocator_init_sub_allocator(&ppm_data->sub_alloc);
404
405 ppm_data->init_rl=-(ppm_data->max_order < 12 ? ppm_data->max_order:12)-1;
406 ppm_data->min_context = ppm_data->max_context =
407 (struct ppm_context *) sub_allocator_alloc_context(&ppm_data->sub_alloc);
408 if (!ppm_data->min_context) {
409 //rar_dbgmsg("unrar: restart_model_rare: sub_allocator_alloc_context failed\n");
410 return 0;
411 }
412 ppm_data->min_context->suffix = NULL;
413 ppm_data->order_fall = ppm_data->max_order;
414 ppm_data->min_context->con_ut.u.summ_freq = (ppm_data->min_context->num_stats=256)+1;
415 ppm_data->found_state = ppm_data->min_context->con_ut.u.stats=
416 (struct state_tag *)sub_allocator_alloc_units(&ppm_data->sub_alloc, 256/2);
417 if (!ppm_data->found_state) {
418 //rar_dbgmsg("unrar: restart_model_rare: sub_allocator_alloc_units failed\n");
419 return 0;
420 }
421 for (ppm_data->run_length = ppm_data->init_rl, ppm_data->prev_success=i=0; i < 256 ; i++) {
422 ppm_data->min_context->con_ut.u.stats[i].symbol = i;
423 ppm_data->min_context->con_ut.u.stats[i].freq = 1;
424 ppm_data->min_context->con_ut.u.stats[i].successor = NULL;
425 }
426
427 for (i=0 ; i < 128 ; i++) {
428 for (k=0 ; k < 8 ; k++) {
429 for (m=0 ; m < 64 ; m+=8) {
430 ppm_data->bin_summ[i][k+m]=BIN_SCALE-init_bin_esc[k]/(i+2);
431 }
432 }
433 }
434 for (i=0; i < 25; i++) {
435 for (k=0 ; k < 16 ; k++) {
436 see2_init(&ppm_data->see2cont[i][k], 5*i+10);
437 }
438 }
439
440 return 1;
441 }
442
start_model_rare(ppm_data_t * ppm_data,int max_order)443 static int start_model_rare(ppm_data_t *ppm_data, int max_order)
444 {
445 int i, k, m, step;
446
447 ppm_data->esc_count = 1;
448 ppm_data->max_order = max_order;
449
450 if (!restart_model_rare(ppm_data)) {
451 //rar_dbgmsg("unrar: start_model_rare: restart_model_rare failed\n");
452 return 0;
453 }
454
455 ppm_data->ns2bsindx[0] = 2*0;
456 ppm_data->ns2bsindx[1] = 2*1;
457
458 memset(ppm_data->ns2bsindx+2, 2*2, 9);
459 memset(ppm_data->ns2bsindx+11, 2*3, 256-11);
460
461 for (i=0 ; i < 3; i++) {
462 ppm_data->ns2indx[i] = i;
463 }
464 for (m=i, k=step=1; i < 256; i++) {
465 ppm_data->ns2indx[i]=m;
466 if (!--k) {
467 k = ++step;
468 m++;
469 }
470 }
471 memset(ppm_data->hb2flag, 0, 0x40);
472 memset(ppm_data->hb2flag+0x40, 0x08, 0x100-0x40);
473 ppm_data->dummy_sse2cont.shift = PERIOD_BITS;
474 return 1;
475 }
476
477
478 /* ****************** PPM Code ***************/
479
ppmd_swap(struct state_tag * p0,struct state_tag * p1)480 static void ppmd_swap(struct state_tag *p0, struct state_tag *p1)
481 {
482 struct state_tag tmp;
483
484 tmp = *p0;
485 *p0 = *p1;
486 *p1 = tmp;
487 }
488
rescale(ppm_data_t * ppm_data,struct ppm_context * context)489 static void rescale(ppm_data_t *ppm_data, struct ppm_context *context)
490 {
491 int old_ns, i, adder, esc_freq, n0, n1;
492 struct state_tag *p1, *p;
493
494 //rar_dbgmsg("in rescale\n");
495 old_ns = context->num_stats;
496 i = context->num_stats-1;
497
498 for (p=ppm_data->found_state ; p != context->con_ut.u.stats ; p--) {
499 ppmd_swap(&p[0], &p[-1]);
500 }
501 context->con_ut.u.stats->freq += 4;
502 context->con_ut.u.summ_freq += 4;
503 esc_freq = context->con_ut.u.summ_freq - p->freq;
504 adder = (ppm_data->order_fall != 0);
505 context->con_ut.u.summ_freq = (p->freq = (p->freq+adder) >> 1);
506 do {
507 esc_freq -= (++p)->freq;
508 context->con_ut.u.summ_freq += (p->freq = (p->freq + adder) >> 1);
509 if (p[0].freq > p[-1].freq) {
510 struct state_tag tmp = *(p1=p);
511 do {
512 p1[0] = p1[-1];
513 } while (--p1 != context->con_ut.u.stats && tmp.freq > p1[-1].freq);
514 *p1 = tmp;
515 }
516 } while (--i);
517
518 if (p->freq == 0) {
519 do {
520 i++;
521 } while ((--p)->freq == 0);
522 esc_freq += i;
523 if ((context->num_stats -= i) == 1) {
524 struct state_tag tmp = *context->con_ut.u.stats;
525 do {
526 tmp.freq -= (tmp.freq >> 1);
527 esc_freq >>= 1;
528 } while (esc_freq > 1);
529 sub_allocator_free_units(&ppm_data->sub_alloc,
530 context->con_ut.u.stats, (old_ns+1)>>1);
531 *(ppm_data->found_state=&context->con_ut.one_state)=tmp;
532 return;
533 }
534 }
535 context->con_ut.u.summ_freq += (esc_freq -= (esc_freq >> 1));
536 n0 = (old_ns+1) >> 1;
537 n1 = (context->num_stats+1) >> 1;
538 if (n0 != n1) {
539 context->con_ut.u.stats = (struct state_tag *) sub_allocator_shrink_units(&ppm_data->sub_alloc,
540 context->con_ut.u.stats, n0, n1);
541 }
542 ppm_data->found_state = context->con_ut.u.stats;
543 }
544
create_child(ppm_data_t * ppm_data,struct ppm_context * context,struct state_tag * pstats,struct state_tag * first_state)545 static struct ppm_context *create_child(ppm_data_t *ppm_data, struct ppm_context *context,
546 struct state_tag *pstats, struct state_tag *first_state)
547 {
548 struct ppm_context *pc;
549 //rar_dbgmsg("in create_child\n");
550 pc = (struct ppm_context *) sub_allocator_alloc_context(&ppm_data->sub_alloc);
551 if (pc) {
552 pc->num_stats = 1;
553 pc->con_ut.one_state = *first_state;
554 pc->suffix = context;
555 pstats->successor = pc;
556 }
557 return pc;
558 }
559
create_successors(ppm_data_t * ppm_data,int skip,struct state_tag * p1)560 static struct ppm_context *create_successors(ppm_data_t *ppm_data,
561 int skip, struct state_tag *p1)
562 {
563 struct state_tag up_state;
564 struct ppm_context *pc, *up_branch;
565 struct state_tag *p, *ps[MAX_O], **pps;
566 unsigned int cf, s0;
567
568 //rar_dbgmsg("in create_successors\n");
569 pc = ppm_data->min_context;
570 up_branch = ppm_data->found_state->successor;
571 pps = ps;
572
573 if (!skip) {
574 *pps++ = ppm_data->found_state;
575 if (!pc->suffix) {
576 goto NO_LOOP;
577 }
578 }
579 if (p1) {
580 p = p1;
581 pc = pc->suffix;
582 goto LOOP_ENTRY;
583 }
584 do {
585 pc = pc->suffix;
586 if (pc->num_stats != 1) {
587 if ((p=pc->con_ut.u.stats)->symbol != ppm_data->found_state->symbol) {
588 do {
589 p++;
590 } while (p->symbol != ppm_data->found_state->symbol);
591 }
592 } else {
593 p = &(pc->con_ut.one_state);
594 }
595 LOOP_ENTRY:
596 if (p->successor != up_branch) {
597 pc = p->successor;
598 break;
599 }
600 *pps++ = p;
601 } while (pc->suffix);
602 NO_LOOP:
603 if (pps == ps) {
604 return pc;
605 }
606 up_state.symbol= *(unsigned char *) up_branch;
607 up_state.successor = (struct ppm_context *) (((unsigned char *) up_branch)+1);
608 if (pc->num_stats != 1) {
609 if ((unsigned char *) pc <= ppm_data->sub_alloc.ptext) {
610 return NULL;
611 }
612 if ((p=pc->con_ut.u.stats)->symbol != up_state.symbol) {
613 do {
614 p++;
615 if ((void *)p > (void *) ppm_data->sub_alloc.heap_end) {
616 return NULL;
617 }
618 } while (p->symbol != up_state.symbol);
619 }
620 cf = p->freq - 1;
621 s0 = pc->con_ut.u.summ_freq - pc->num_stats - cf;
622 up_state.freq = 1 + ((2*cf <= s0)?(5*cf > s0):((2*cf+3*s0-1)/(2*s0)));
623 } else {
624 up_state.freq = pc->con_ut.one_state.freq;
625 }
626 do {
627 pc = create_child(ppm_data, pc, *--pps, &up_state);
628 if (!pc) {
629 //rar_dbgmsg("create_child failed\n");
630 return NULL;
631 }
632 } while (pps != ps);
633 return pc;
634 }
635
update_model(ppm_data_t * ppm_data)636 static int update_model(ppm_data_t *ppm_data)
637 {
638 struct state_tag fs, *p;
639 struct ppm_context *pc, *successor;
640 unsigned int ns1, ns, cf, sf, s0;
641
642 //rar_dbgmsg("in update_model\n");
643 fs = *ppm_data->found_state;
644 p = NULL;
645
646 if (fs.freq < MAX_FREQ/4 && (pc=ppm_data->min_context->suffix) != NULL) {
647 if (pc->num_stats != 1) {
648 if ((p=pc->con_ut.u.stats)->symbol != fs.symbol) {
649 do {
650 p++;
651 } while (p->symbol != fs.symbol);
652 if (p[0].freq >= p[-1].freq) {
653 ppmd_swap(&p[0], &p[-1]);
654 p--;
655 }
656 }
657 if (p->freq < MAX_FREQ-9) {
658 p->freq += 2;
659 pc->con_ut.u.summ_freq += 2;
660 }
661 } else {
662 p = &(pc->con_ut.one_state);
663 p->freq += (p->freq < 32);
664 }
665 }
666 if (!ppm_data->order_fall) {
667 ppm_data->min_context = ppm_data->max_context =
668 ppm_data->found_state->successor = create_successors(ppm_data, 1, p);
669 if (!ppm_data->min_context) {
670 goto RESTART_MODEL;
671 }
672 return 1;
673 }
674 *ppm_data->sub_alloc.ptext++ = fs.symbol;
675 successor = (struct ppm_context *) ppm_data->sub_alloc.ptext;
676 if (ppm_data->sub_alloc.ptext >= ppm_data->sub_alloc.fake_units_start) {
677 goto RESTART_MODEL;
678 }
679 if (fs.successor) {
680 if ((unsigned char *)fs.successor <= ppm_data->sub_alloc.ptext &&
681 (fs.successor = create_successors(ppm_data, 0, p)) == NULL) {
682 goto RESTART_MODEL;
683 }
684 if (!--ppm_data->order_fall) {
685 successor = fs.successor;
686 ppm_data->sub_alloc.ptext -= (ppm_data->max_context != ppm_data->min_context);
687 }
688 } else {
689 ppm_data->found_state->successor = successor;
690 fs.successor = ppm_data->min_context;
691 }
692 s0 = ppm_data->min_context->con_ut.u.summ_freq-(ns=ppm_data->min_context->num_stats)-(fs.freq-1);
693 for (pc=ppm_data->max_context; pc != ppm_data->min_context ; pc=pc->suffix) {
694 if ((ns1=pc->num_stats) != 1) {
695 if ((ns1 & 1) == 0) {
696 pc->con_ut.u.stats = (struct state_tag *)
697 sub_allocator_expand_units(&ppm_data->sub_alloc,
698 pc->con_ut.u.stats, ns1>>1);
699 if (!pc->con_ut.u.stats) {
700 goto RESTART_MODEL;
701 }
702 }
703 pc->con_ut.u.summ_freq += (2*ns1 < ns)+2*((4*ns1 <= ns) & (pc->con_ut.u.summ_freq <= 8*ns1));
704 } else {
705 p = (struct state_tag *) sub_allocator_alloc_units(&ppm_data->sub_alloc, 1);
706 if (!p) {
707 goto RESTART_MODEL;
708 }
709 *p = pc->con_ut.one_state;
710 pc->con_ut.u.stats = p;
711 if (p->freq < MAX_FREQ/4-1) {
712 p->freq += p->freq;
713 } else {
714 p->freq = MAX_FREQ - 4;
715 }
716 pc->con_ut.u.summ_freq = p->freq + ppm_data->init_esc + (ns > 3);
717 }
718 cf = 2*fs.freq*(pc->con_ut.u.summ_freq+6);
719 sf = s0 + pc->con_ut.u.summ_freq;
720 if (cf < 6*sf) {
721 cf = 1 + (cf > sf) + (cf >= 4*sf);
722 pc->con_ut.u.summ_freq += 3;
723 } else {
724 cf = 4 + (cf >= 9*sf) + (cf >= 12*sf) + (cf >= 15*sf);
725 pc->con_ut.u.summ_freq += cf;
726 }
727 p = pc->con_ut.u.stats + ns1;
728 p->successor = successor;
729 p->symbol = fs.symbol;
730 p->freq = cf;
731 pc->num_stats = ++ns1;
732 }
733 ppm_data->max_context = ppm_data->min_context = fs.successor;
734 return 1;
735
736 RESTART_MODEL:
737 if (!restart_model_rare(ppm_data)) {
738 //rar_dbgmsg("unrar: update_model: restart_model_rare: failed\n");
739 return 0;
740 }
741 ppm_data->esc_count = 0;
742 return 1;
743 }
744
update1(ppm_data_t * ppm_data,struct state_tag * p,struct ppm_context * context)745 static void update1(ppm_data_t *ppm_data, struct state_tag *p, struct ppm_context *context)
746 {
747 //rar_dbgmsg("in update1\n");
748 (ppm_data->found_state=p)->freq += 4;
749 context->con_ut.u.summ_freq += 4;
750 if (p[0].freq > p[-1].freq) {
751 ppmd_swap(&p[0], &p[-1]);
752 ppm_data->found_state = --p;
753 if (p->freq > MAX_FREQ) {
754 rescale(ppm_data, context);
755 }
756 }
757 }
758
ppm_decode_symbol1(ppm_data_t * ppm_data,struct ppm_context * context)759 static int ppm_decode_symbol1(ppm_data_t *ppm_data, struct ppm_context *context)
760 {
761 struct state_tag *p;
762 int i, hi_cnt, count;
763
764 //rar_dbgmsg("in ppm_decode_symbol1\n");
765 ppm_data->coder.scale = context->con_ut.u.summ_freq;
766 p = context->con_ut.u.stats;
767 count = coder_get_current_count(&ppm_data->coder);
768 if (count >= ppm_data->coder.scale) {
769 return 0;
770 }
771 if (count < (hi_cnt = p->freq)) {
772 ppm_data->prev_success = (2 * (ppm_data->coder.high_count=hi_cnt) >
773 ppm_data->coder.scale);
774 ppm_data->run_length += ppm_data->prev_success;
775 (ppm_data->found_state=p)->freq=(hi_cnt += 4);
776 context->con_ut.u.summ_freq += 4;
777 if (hi_cnt > MAX_FREQ) {
778 rescale(ppm_data, context);
779 }
780 ppm_data->coder.low_count = 0;
781 return 1;
782 } else if (ppm_data->found_state == NULL) {
783 return 0;
784 }
785 ppm_data->prev_success = 0;
786 i = context->num_stats-1;
787 while ((hi_cnt += (++p)->freq) <= count) {
788 if (--i == 0) {
789 ppm_data->hi_bits_flag = ppm_data->hb2flag[ppm_data->found_state->symbol];
790 ppm_data->coder.low_count = hi_cnt;
791 ppm_data->char_mask[p->symbol] = ppm_data->esc_count;
792 i = (ppm_data->num_masked=context->num_stats) - 1;
793 ppm_data->found_state = NULL;
794 do {
795 ppm_data->char_mask[(--p)->symbol] = ppm_data->esc_count;
796 } while (--i);
797 ppm_data->coder.high_count = ppm_data->coder.scale;
798 return 1;
799 }
800 }
801 ppm_data->coder.low_count = (ppm_data->coder.high_count = hi_cnt) - p->freq;
802 update1(ppm_data, p, context);
803 return 1;
804 }
805
806 static const unsigned char ExpEscape[16]={ 25,14, 9, 7, 5, 5, 4, 4, 4, 3, 3, 3, 2, 2, 2, 2 };
807 #define GET_MEAN(SUMM,SHIFT,ROUND) ((SUMM+(1 << (SHIFT-ROUND))) >> (SHIFT))
808
ppm_decode_bin_symbol(ppm_data_t * ppm_data,struct ppm_context * context)809 static void ppm_decode_bin_symbol(ppm_data_t *ppm_data, struct ppm_context *context)
810 {
811 struct state_tag *rs;
812 unsigned short *bs;
813
814 //rar_dbgmsg("in ppm_decode_bin_symbol\n");
815
816 rs = &context->con_ut.one_state;
817
818 ppm_data->hi_bits_flag = ppm_data->hb2flag[ppm_data->found_state->symbol];
819 bs = &ppm_data->bin_summ[rs->freq-1][ppm_data->prev_success +
820 ppm_data->ns2bsindx[context->suffix->num_stats-1] +
821 ppm_data->hi_bits_flag+2*ppm_data->hb2flag[rs->symbol] +
822 ((ppm_data->run_length >> 26) & 0x20)];
823 if (coder_get_current_shift_count(&ppm_data->coder, TOT_BITS) < *bs) {
824 ppm_data->found_state = rs;
825 rs->freq += (rs->freq < 128);
826 ppm_data->coder.low_count = 0;
827 ppm_data->coder.high_count = *bs;
828 *bs = (unsigned short) (*bs + INTERVAL - GET_MEAN(*bs, PERIOD_BITS, 2));
829 ppm_data->prev_success = 1;
830 ppm_data->run_length++;
831 } else {
832 ppm_data->coder.low_count = *bs;
833 *bs = (unsigned short) (*bs - GET_MEAN(*bs, PERIOD_BITS, 2));
834 ppm_data->coder.high_count = BIN_SCALE;
835 ppm_data->init_esc = ExpEscape[*bs >> 10];
836 ppm_data->num_masked = 1;
837 ppm_data->char_mask[rs->symbol] = ppm_data->esc_count;
838 ppm_data->prev_success = 0;
839 ppm_data->found_state = NULL;
840 }
841 }
842
update2(ppm_data_t * ppm_data,struct state_tag * p,struct ppm_context * context)843 static void update2(ppm_data_t *ppm_data, struct state_tag *p, struct ppm_context *context)
844 {
845 //rar_dbgmsg("in update2\n");
846 (ppm_data->found_state = p)->freq += 4;
847 context->con_ut.u.summ_freq += 4;
848 if (p->freq > MAX_FREQ) {
849 rescale(ppm_data, context);
850 }
851 ppm_data->esc_count++;
852 ppm_data->run_length = ppm_data->init_rl;
853 }
854
make_esc_freq(ppm_data_t * ppm_data,struct ppm_context * context,int diff)855 static struct see2_context_tag *make_esc_freq(ppm_data_t *ppm_data,
856 struct ppm_context *context, int diff)
857 {
858 struct see2_context_tag *psee2c;
859
860 if (context->num_stats != 256) {
861 psee2c = ppm_data->see2cont[ppm_data->ns2indx[diff-1]] +
862 (diff < context->suffix->num_stats-context->num_stats) +
863 2 * (context->con_ut.u.summ_freq < 11*context->num_stats)+4*
864 (ppm_data->num_masked > diff) + ppm_data->hi_bits_flag;
865 ppm_data->coder.scale = get_mean(psee2c);
866 } else {
867 psee2c = &ppm_data->dummy_sse2cont;
868 ppm_data->coder.scale = 1;
869 }
870 return psee2c;
871 }
872
ppm_decode_symbol2(ppm_data_t * ppm_data,struct ppm_context * context)873 static int ppm_decode_symbol2(ppm_data_t *ppm_data, struct ppm_context *context)
874 {
875 int count, hi_cnt, i;
876 struct see2_context_tag *psee2c;
877 struct state_tag *ps[256], **pps, *p;
878
879 //rar_dbgmsg("in ppm_decode_symbol2\n");
880 i = context->num_stats - ppm_data->num_masked;
881 psee2c = make_esc_freq(ppm_data, context, i);
882 pps = ps;
883 p = context->con_ut.u.stats - 1;
884 hi_cnt = 0;
885
886 do {
887 do {
888 p++;
889 } while (ppm_data->char_mask[p->symbol] == ppm_data->esc_count);
890 hi_cnt += p->freq;
891 *pps++ = p;
892 } while (--i);
893 ppm_data->coder.scale += hi_cnt;
894 count = coder_get_current_count(&ppm_data->coder);
895 if (count >= ppm_data->coder.scale) {
896 return 0;
897 }
898 p=*(pps=ps);
899 if (count < hi_cnt) {
900 hi_cnt = 0;
901 while ((hi_cnt += p->freq) <= count) {
902 p=*++pps;
903 }
904 ppm_data->coder.low_count = (ppm_data->coder.high_count=hi_cnt) - p->freq;
905 update(psee2c);
906 update2(ppm_data, p, context);
907 } else {
908 ppm_data->coder.low_count = hi_cnt;
909 ppm_data->coder.high_count = ppm_data->coder.scale;
910 i = context->num_stats - ppm_data->num_masked;
911 pps--;
912 do {
913 ppm_data->char_mask[(*++pps)->symbol] = ppm_data->esc_count;
914 } while (--i);
915 psee2c->summ += ppm_data->coder.scale;
916 ppm_data->num_masked = context->num_stats;
917 }
918 return 1;
919 }
920
clear_mask(ppm_data_t * ppm_data)921 static void clear_mask(ppm_data_t *ppm_data)
922 {
923 ppm_data->esc_count = 1;
924 memset(ppm_data->char_mask, 0, sizeof(ppm_data->char_mask));
925 }
926
ppm_constructor(ppm_data_t * ppm_data)927 void ppm_constructor(ppm_data_t *ppm_data)
928 {
929 sub_allocator_init(&ppm_data->sub_alloc);
930 ppm_data->min_context = NULL;
931 ppm_data->max_context = NULL;
932 }
933
ppm_destructor(ppm_data_t * ppm_data)934 void ppm_destructor(ppm_data_t *ppm_data)
935 {
936 sub_allocator_stop_sub_allocator(&ppm_data->sub_alloc);
937 }
938
ppm_cleanup(ppm_data_t * ppm_data)939 void ppm_cleanup(ppm_data_t *ppm_data)
940 {
941 sub_allocator_stop_sub_allocator(&ppm_data->sub_alloc);
942 sub_allocator_start_sub_allocator(&ppm_data->sub_alloc, 1);
943 start_model_rare(ppm_data, 2); // This line HANGS the compiler on sparc
944 }
945
ppm_decode_init(ppm_data_t * ppm_data,const unsigned char ** fd,unpack_data_t * unpack_data,int * EscChar)946 int ppm_decode_init(ppm_data_t *ppm_data, const unsigned char **fd, unpack_data_t *unpack_data, int *EscChar)
947 {
948 int max_order, Reset, MaxMB = 0;
949
950 max_order = rar_get_char(fd, unpack_data);
951 //rar_dbgmsg("ppm_decode_init max_order=%d\n", max_order);
952 Reset = (max_order & 0x20) ? 1 : 0;
953 //rar_dbgmsg("ppm_decode_init Reset=%d\n", Reset);
954 if (Reset) {
955 MaxMB = rar_get_char(fd, unpack_data);
956 //rar_dbgmsg("ppm_decode_init MaxMB=%d\n", MaxMB);
957 if (MaxMB > 128) {
958 //rar_dbgmsg("MaxMB > 128 MB (%d, 0x%02x) reject\n", MaxMB, MaxMB);
959 return 0;
960 }
961 } else {
962 if (sub_allocator_get_allocated_memory(&ppm_data->sub_alloc) == 0) {
963 return 0;
964 }
965 }
966 if (max_order & 0x40) {
967 *EscChar = rar_get_char(fd, unpack_data);
968 //rar_dbgmsg("ppm_decode_init EscChar=%d\n", *EscChar);
969 }
970 range_coder_init_decoder(&ppm_data->coder, fd, unpack_data);
971 if (Reset) {
972 max_order = (max_order & 0x1f) + 1;
973 if (max_order > 16) {
974 max_order = 16 + (max_order - 16) * 3;
975 }
976 if (max_order == 1) {
977 sub_allocator_stop_sub_allocator(&ppm_data->sub_alloc);
978 return 0;
979 }
980 if (!sub_allocator_start_sub_allocator(&ppm_data->sub_alloc, MaxMB+1)) {
981 sub_allocator_stop_sub_allocator(&ppm_data->sub_alloc);
982 return 0;
983 }
984 if (!start_model_rare(ppm_data, max_order)) { // This line HANGS the compiler on sparc
985 sub_allocator_stop_sub_allocator(&ppm_data->sub_alloc);
986 return 0;
987 }
988 }
989 //rar_dbgmsg("ppm_decode_init done: %d\n", ppm_data->min_context != NULL);
990 return (ppm_data->min_context != NULL);
991 }
992
ppm_decode_char(ppm_data_t * ppm_data,const unsigned char ** fd,unpack_data_t * unpack_data)993 int ppm_decode_char(ppm_data_t *ppm_data, const unsigned char **fd, unpack_data_t *unpack_data)
994 {
995 int symbol;
996
997 if ((unsigned char *) ppm_data->min_context <= ppm_data->sub_alloc.ptext ||
998 (unsigned char *)ppm_data->min_context > ppm_data->sub_alloc.heap_end) {
999 return -1;
1000 }
1001 if (ppm_data->min_context->num_stats != 1) {
1002 if ((unsigned char *) ppm_data->min_context->con_ut.u.stats <= ppm_data->sub_alloc.ptext ||
1003 (unsigned char *) ppm_data->min_context->con_ut.u.stats > ppm_data->sub_alloc.heap_end) {
1004 return -1;
1005 }
1006 if (!ppm_decode_symbol1(ppm_data, ppm_data->min_context)) {
1007 return -1;
1008 }
1009 } else {
1010 ppm_decode_bin_symbol(ppm_data, ppm_data->min_context);
1011 }
1012 coder_decode(&ppm_data->coder);
1013
1014 while (!ppm_data->found_state) {
1015 ARI_DEC_NORMALISE(fd, unpack_data, ppm_data->coder.code,
1016 ppm_data->coder.low, ppm_data->coder.range);
1017 do {
1018 ppm_data->order_fall++;
1019 ppm_data->min_context = ppm_data->min_context->suffix;
1020 if ((unsigned char *)ppm_data->min_context <= ppm_data->sub_alloc.ptext ||
1021 (unsigned char *)ppm_data->min_context >
1022 ppm_data->sub_alloc.heap_end) {
1023 return -1;
1024 }
1025 } while (ppm_data->min_context->num_stats == ppm_data->num_masked);
1026 if (!ppm_decode_symbol2(ppm_data, ppm_data->min_context)) {
1027 return -1;
1028 }
1029 coder_decode(&ppm_data->coder);
1030 }
1031
1032 symbol = ppm_data->found_state->symbol;
1033 if (!ppm_data->order_fall && (unsigned char *) ppm_data->found_state->successor > ppm_data->sub_alloc.ptext) {
1034 ppm_data->min_context = ppm_data->max_context = ppm_data->found_state->successor;
1035 } else {
1036
1037 if (!update_model(ppm_data)) { // This line HANGS the compiler on sparc
1038 //rar_dbgmsg("unrar: ppm_decode_char: update_model failed\n");
1039 return -1;
1040 }
1041
1042 if (ppm_data->esc_count == 0) {
1043 clear_mask(ppm_data);
1044 }
1045 }
1046 ARI_DEC_NORMALISE(fd, unpack_data, ppm_data->coder.code, ppm_data->coder.low, ppm_data->coder.range);
1047 return symbol;
1048 }
1049