/*
 *  Extract RAR archives
 *
 *  Copyright (C) 2005-2006 trog@uncon.org
 *
 *  This code is based on the work of Alexander L. Roshal (C)
 *
 *  The unRAR sources may be used in any software to handle RAR
 *  archives without limitations free of charge, but cannot be used
 *  to re-create the RAR compression algorithm, which is proprietary.
 *  Distribution of modified unRAR sources in separate form or as a
 *  part of other software is permitted, provided that it is clearly
 *  stated in the documentation and source comments that the code may
 *  not be used to develop a RAR (WinRAR) compatible archiver.
 */

#if HAVE_CONFIG_H
#include "clamav-config.h"
#endif

#include <stdio.h>
#include <string.h>

#include "libclamunrar/unrar.h"
#include "libclamunrar/unrarppm.h"

#ifdef RAR_HIGH_DEBUG
#define rar_dbgmsg printf
#else
static void rar_dbgmsg(const char* fmt,...){}
#endif

#define MAX_O 64

const unsigned int UNIT_SIZE=MAX(sizeof(struct ppm_context), sizeof(struct rar_mem_blk_tag));
const unsigned int FIXED_UNIT_SIZE=12;
const int INT_BITS=7, PERIOD_BITS=7, TOT_BITS=14;
const int INTERVAL=1 << 7, BIN_SCALE=1 << 14, MAX_FREQ=124;
const unsigned int TOP=1 << 24, BOT=1 << 15;

/************* Start of Allocator code block ********************/
static void sub_allocator_init(sub_allocator_t *sub_alloc)
{
	sub_alloc->sub_allocator_size = 0;
}

static void sub_allocator_insert_node(sub_allocator_t *sub_alloc, void *p, int indx)
{
	((struct rar_node *) p)->next = sub_alloc->free_list[indx].next;
	sub_alloc->free_list[indx].next = (struct rar_node *) p;
}

static void *sub_allocator_remove_node(sub_allocator_t *sub_alloc, int indx)
{
	struct rar_node *ret_val;
	
	ret_val = sub_alloc->free_list[indx].next;
	sub_alloc->free_list[indx].next = ret_val->next;
	return ret_val;
}

static int sub_allocator_u2b(int nu)
{
	return UNIT_SIZE*nu;
}

static rar_mem_blk_t* sub_allocator_mbptr(rar_mem_blk_t* base_ptr, int items)
{
        return ((rar_mem_blk_t*) (((unsigned char *)(base_ptr)) + sub_allocator_u2b(items) ));
}

static void sub_allocator_split_block(sub_allocator_t *sub_alloc, void *pv,
				int old_indx, int new_indx)
{
	int i, udiff;
	uint8_t *p;
	
	udiff = sub_alloc->indx2units[old_indx] - sub_alloc->indx2units[new_indx];
	p = ((uint8_t *) pv) + sub_allocator_u2b(sub_alloc->indx2units[new_indx]);
	if (sub_alloc->indx2units[i=sub_alloc->units2indx[udiff-1]] != udiff) {
		sub_allocator_insert_node(sub_alloc, p, --i);
		p += sub_allocator_u2b(i=sub_alloc->indx2units[i]);
		udiff -= i;
	}
	sub_allocator_insert_node(sub_alloc, p, sub_alloc->units2indx[udiff-1]);
}

static long sub_allocator_get_allocated_memory(sub_allocator_t *sub_alloc)
{
	return sub_alloc->sub_allocator_size;
}

static void sub_allocator_stop_sub_allocator(sub_allocator_t *sub_alloc)
{
	if (sub_alloc->sub_allocator_size) {
		sub_alloc->sub_allocator_size = 0;
		free(sub_alloc->heap_start);
	}
}

static int sub_allocator_start_sub_allocator(sub_allocator_t *sub_alloc, int sa_size)
{
	unsigned int t, alloc_size;
	
	t = sa_size << 20;
	if (sub_alloc->sub_allocator_size == t) {
		return TRUE;
	}
	sub_allocator_stop_sub_allocator(sub_alloc);
	if (t>138412020) {
		rar_dbgmsg("too much memory needed for uncompressing this file\n");
		return FALSE;
	}
	alloc_size = t/FIXED_UNIT_SIZE*UNIT_SIZE+UNIT_SIZE;
#if defined(__sparc) || defined(sparc) || defined(__sparcv9)
	/* Allow for aligned access requirements */
	alloc_size += UNIT_SIZE;
#endif
	if ((sub_alloc->heap_start = (uint8_t *) malloc(alloc_size)) == NULL) {
		rar_dbgmsg("sub_alloc start failed\n");
		return FALSE;
	}
	sub_alloc->heap_end = sub_alloc->heap_start + alloc_size - UNIT_SIZE;
	sub_alloc->sub_allocator_size = t;
	return TRUE;
}

static void sub_allocator_init_sub_allocator(sub_allocator_t *sub_alloc)
{
	int i, k;
	unsigned int size1, real_size1, size2, real_size2;

	memset(sub_alloc->free_list, 0, sizeof(sub_alloc->free_list));
	sub_alloc->ptext = sub_alloc->heap_start;
	
	size2 = FIXED_UNIT_SIZE*(sub_alloc->sub_allocator_size/8/FIXED_UNIT_SIZE*7);
	real_size2 = size2/FIXED_UNIT_SIZE*UNIT_SIZE;
	size1 = sub_alloc->sub_allocator_size - size2;
	real_size1 = size1/FIXED_UNIT_SIZE*UNIT_SIZE+size1%FIXED_UNIT_SIZE;
#if defined(__sparc) || defined(sparc) || defined(__sparcv9)
	/* Allow for aligned access requirements */
	if (size1%FIXED_UNIT_SIZE != 0) {
		real_size1 += UNIT_SIZE - size1%FIXED_UNIT_SIZE;
	}
#endif
	sub_alloc->hi_unit = sub_alloc->heap_start + sub_alloc->sub_allocator_size;
	sub_alloc->lo_unit = sub_alloc->units_start = sub_alloc->heap_start + real_size1;
	sub_alloc->fake_units_start = sub_alloc->heap_start + size1;
	sub_alloc->hi_unit = sub_alloc->lo_unit + real_size2;
	
	for (i=0,k=1; i < N1 ; i++, k+=1) {
		sub_alloc->indx2units[i] = k;
	}
	for (k++; i < N1+N2 ; i++, k+=2) {
		sub_alloc->indx2units[i] = k;
	}
	for (k++; i < N1+N2+N3 ; i++, k+=3) {
		sub_alloc->indx2units[i] = k;
	}
	for (k++; i < N1+N2+N3+N4 ; i++, k+=4) {
		sub_alloc->indx2units[i] = k;
	}
	
	for (sub_alloc->glue_count=k=i=0; k < 128; k++) {
		i += (sub_alloc->indx2units[i] < k+1);
		sub_alloc->units2indx[k] = i;
	}
}

static void rar_mem_blk_insertAt(rar_mem_blk_t *a, rar_mem_blk_t *p)
{
	a->next = (a->prev=p)->next;
	p->next = a->next->prev = a;
}

static void rar_mem_blk_remove(rar_mem_blk_t *a)
{
	a->prev->next = a->next;
	a->next->prev = a->prev;
}

static void sub_allocator_glue_free_blocks(sub_allocator_t *sub_alloc)
{
	rar_mem_blk_t s0, *p, *p1;
	int i, k, sz;
	
	if (sub_alloc->lo_unit != sub_alloc->hi_unit) {
		*sub_alloc->lo_unit = 0;
	}
	for (i=0, s0.next=s0.prev=&s0; i < N_INDEXES; i++) {
		while (sub_alloc->free_list[i].next) {
			p = (rar_mem_blk_t *) sub_allocator_remove_node(sub_alloc, i);
			rar_mem_blk_insertAt(p, &s0);
			p->stamp = 0xFFFF;
			p->nu = sub_alloc->indx2units[i];
		}
	}
	
	for (p=s0.next ; p != &s0 ; p=p->next) {
		while ((p1 = sub_allocator_mbptr(p,p->nu))->stamp == 0xFFFF &&
				((int)p->nu)+p1->nu < 0x10000) {
			rar_mem_blk_remove(p1);
			p->nu += p1->nu;
		}
	}
	
	while ((p=s0.next) != &s0) {
		for (rar_mem_blk_remove(p), sz=p->nu; sz > 128; sz-=128, p=sub_allocator_mbptr(p, 128)) {
			sub_allocator_insert_node(sub_alloc, p, N_INDEXES-1);
		}
		if (sub_alloc->indx2units[i=sub_alloc->units2indx[sz-1]] != sz) {
			k = sz-sub_alloc->indx2units[--i];
			sub_allocator_insert_node(sub_alloc, sub_allocator_mbptr(p,sz-k), k-1);
		}
		sub_allocator_insert_node(sub_alloc, p, i);
	}
}

static void *sub_allocator_alloc_units_rare(sub_allocator_t *sub_alloc, int indx)
{
	int i, j;
	void *ret_val;
	
	if (!sub_alloc->glue_count) {
		sub_alloc->glue_count = 255;
		sub_allocator_glue_free_blocks(sub_alloc);
		if (sub_alloc->free_list[indx].next) {
			return sub_allocator_remove_node(sub_alloc, indx);
		}
	}
	i=indx;
	do {
		if (++i == N_INDEXES) {
			sub_alloc->glue_count--;
			i = sub_allocator_u2b(sub_alloc->indx2units[indx]);
			j = 12 * sub_alloc->indx2units[indx];
			if (sub_alloc->fake_units_start - sub_alloc->ptext > j) {
				sub_alloc->fake_units_start -= j;
				sub_alloc->units_start -= i;
				return sub_alloc->units_start;
			}
			return NULL;
		}
	} while ( !sub_alloc->free_list[i].next);
	ret_val = sub_allocator_remove_node(sub_alloc, i);
	sub_allocator_split_block(sub_alloc, ret_val, i, indx);
	return ret_val;
}

static void *sub_allocator_alloc_units(sub_allocator_t *sub_alloc, int nu)
{
	int indx;
	void *ret_val;
	
	indx = sub_alloc->units2indx[nu-1];
	if (sub_alloc->free_list[indx].next) {
		return sub_allocator_remove_node(sub_alloc, indx);
	}
	ret_val = sub_alloc->lo_unit;
	sub_alloc->lo_unit += sub_allocator_u2b(sub_alloc->indx2units[indx]);
	if (sub_alloc->lo_unit <= sub_alloc->hi_unit) {
		return ret_val;
	}
	sub_alloc->lo_unit -= sub_allocator_u2b(sub_alloc->indx2units[indx]);
	return sub_allocator_alloc_units_rare(sub_alloc, indx);
}

static void *sub_allocator_alloc_context(sub_allocator_t *sub_alloc)
{
	if (sub_alloc->hi_unit != sub_alloc->lo_unit) {
		return (sub_alloc->hi_unit -= UNIT_SIZE);
	}
	if (sub_alloc->free_list->next) {
		return sub_allocator_remove_node(sub_alloc, 0);
	}
	return sub_allocator_alloc_units_rare(sub_alloc, 0);
}

static void *sub_allocator_expand_units(sub_allocator_t *sub_alloc, void *old_ptr, int old_nu)
{
	int i0, i1;
	void *ptr;
	
	i0 = sub_alloc->units2indx[old_nu-1];
	i1 = sub_alloc->units2indx[old_nu];
	if (i0 == i1) {
		return old_ptr;
	}
	ptr = sub_allocator_alloc_units(sub_alloc, old_nu+1);
	if (ptr) {
		memcpy(ptr, old_ptr, sub_allocator_u2b(old_nu));
		sub_allocator_insert_node(sub_alloc, old_ptr, i0);
	}
	return ptr;
}

static void *sub_allocator_shrink_units(sub_allocator_t *sub_alloc, void *old_ptr,
			int old_nu, int new_nu)
{
	int i0, i1;
	void *ptr;
	
	i0 = sub_alloc->units2indx[old_nu-1];
	i1 = sub_alloc->units2indx[new_nu-1];
	if (i0 == i1) {
		return old_ptr;
	}
	if (sub_alloc->free_list[i1].next) {
		ptr = sub_allocator_remove_node(sub_alloc, i1);
		memcpy(ptr, old_ptr, sub_allocator_u2b(new_nu));
		sub_allocator_insert_node(sub_alloc, old_ptr, i0);
		return ptr;
	} else {
		sub_allocator_split_block(sub_alloc, old_ptr, i0, i1);
		return old_ptr;
	}
}

static void  sub_allocator_free_units(sub_allocator_t *sub_alloc, void *ptr, int old_nu)
{
	sub_allocator_insert_node(sub_alloc, ptr, sub_alloc->units2indx[old_nu-1]);
}

/************** End of Allocator code block *********************/

/************** Start of Range Coder code block *********************/
static void range_coder_init_decoder(range_coder_t *coder, int fd,
			unpack_data_t *unpack_data)
{
	int i;
	coder->low = coder->code = 0;
	coder->range = (unsigned int) -1;
	
	for (i=0; i < 4 ; i++) {
		coder->code = (coder->code << 8) | rar_get_char(fd, unpack_data);
	}
}

static int coder_get_current_count(range_coder_t *coder)
{
	return (coder->code - coder->low) / (coder->range /= coder->scale);
}

static unsigned int  coder_get_current_shift_count(range_coder_t *coder, unsigned int shift)
{
	return (coder->code - coder->low) / (coder->range >>= shift);
}

#define ARI_DEC_NORMALISE(fd, unpack_data, code, low, range)					\
{												\
	while ((low^(low+range)) < TOP || (range < BOT && ((range=-low&(BOT-1)),1))) {		\
		code = (code << 8) | rar_get_char(fd, unpack_data);				\
		range <<= 8;									\
		low <<= 8;									\
	}											\
}

static void coder_decode(range_coder_t *coder)
{
	coder->low += coder->range * coder->low_count;
	coder->range *= coder->high_count - coder->low_count;
}

/******(******** End of Range Coder code block ***********(**********/

static void see2_init(struct see2_context_tag *see2_cont, int init_val)
{
	see2_cont->summ = init_val << (see2_cont->shift=PERIOD_BITS-4);
	see2_cont->count = 4;
}

static unsigned int get_mean(struct see2_context_tag *see2_cont)
{
	unsigned int ret_val;
	
	ret_val = see2_cont->summ >> see2_cont->shift;
	see2_cont->summ -= ret_val;
	return ret_val + (ret_val == 0);
}

static void update(struct see2_context_tag *see2_cont)
{
	if (see2_cont->shift < PERIOD_BITS && --see2_cont->count == 0) {
		see2_cont->summ += see2_cont->summ;
		see2_cont->count = 3 << see2_cont->shift++;
	}
}

static int restart_model_rare(ppm_data_t *ppm_data)
{
	int i, k, m;
	static const uint16_t init_bin_esc[] = {
		0x3cdd, 0x1f3f, 0x59bf, 0x48f3, 0x64a1, 0x5abc, 0x6632, 0x6051
	};
	rar_dbgmsg("in restart_model_rare\n");
	memset(ppm_data->char_mask, 0, sizeof(ppm_data->char_mask));
	
	sub_allocator_init_sub_allocator(&ppm_data->sub_alloc);
	
	ppm_data->init_rl=-(ppm_data->max_order < 12 ? ppm_data->max_order:12)-1;
	ppm_data->min_context = ppm_data->max_context =
		(struct ppm_context *) sub_allocator_alloc_context(&ppm_data->sub_alloc);
	if(!ppm_data->min_context) {
	    rar_dbgmsg("unrar: restart_model_rare: sub_allocator_alloc_context failed\n"); /* FIXME: cli_errmsg */
	    return FALSE;
	}
	ppm_data->min_context->suffix = NULL;
	ppm_data->order_fall = ppm_data->max_order;
	ppm_data->min_context->con_ut.u.summ_freq = (ppm_data->min_context->num_stats=256)+1;
	ppm_data->found_state = ppm_data->min_context->con_ut.u.stats=
		(struct state_tag *)sub_allocator_alloc_units(&ppm_data->sub_alloc, 256/2);
	if(!ppm_data->found_state) {
	    rar_dbgmsg("unrar: restart_model_rare: sub_allocator_alloc_units failed\n"); /* FIXME: cli_errmsg */
	    return FALSE;
	}
	for (ppm_data->run_length = ppm_data->init_rl, ppm_data->prev_success=i=0; i < 256 ; i++) {
		ppm_data->min_context->con_ut.u.stats[i].symbol = i;
		ppm_data->min_context->con_ut.u.stats[i].freq = 1;
		ppm_data->min_context->con_ut.u.stats[i].successor = NULL;
	}
	
	for (i=0 ; i < 128 ; i++) {
		for (k=0 ; k < 8 ; k++) {
			for (m=0 ; m < 64 ; m+=8) {
				ppm_data->bin_summ[i][k+m]=BIN_SCALE-init_bin_esc[k]/(i+2);
			}
		}
	}
	for (i=0; i < 25; i++) {
		for (k=0 ; k < 16 ; k++) {
			see2_init(&ppm_data->see2cont[i][k], 5*i+10);
		}
	}

	return TRUE;
}
	
static int start_model_rare(ppm_data_t *ppm_data, int max_order)
{
	int i, k, m, step;
	
	ppm_data->esc_count = 1;
	ppm_data->max_order = max_order;
	
	if (!restart_model_rare(ppm_data)) {
	    rar_dbgmsg("unrar: start_model_rare: restart_model_rare failed\n");
	    return FALSE;
	}
	
	ppm_data->ns2bsindx[0] = 2*0;
	ppm_data->ns2bsindx[1] = 2*1;
	
	memset(ppm_data->ns2bsindx+2, 2*2, 9);
	memset(ppm_data->ns2bsindx+11, 2*3, 256-11);
	
	for (i=0 ; i < 3; i++) {
		ppm_data->ns2indx[i] = i;
	}
	for (m=i, k=step=1; i < 256; i++) {
		ppm_data->ns2indx[i]=m;
		if (!--k) {
			k = ++step;
			m++;
		}
	}
	memset(ppm_data->hb2flag, 0, 0x40);
	memset(ppm_data->hb2flag+0x40, 0x08, 0x100-0x40);
	ppm_data->dummy_sse2cont.shift = PERIOD_BITS;
	return TRUE;
}

	
/* ****************** PPM Code ***************/

static void ppmd_swap(struct state_tag *p0, struct state_tag *p1)
{
	struct state_tag tmp;
	
	tmp = *p0;
	*p0 = *p1;
	*p1 = tmp;
}

static void rescale(ppm_data_t *ppm_data, struct ppm_context *context)
{
	int old_ns, i, adder, esc_freq, n0, n1;
	struct state_tag *p1, *p;
	
	rar_dbgmsg("in rescale\n");
	old_ns = context->num_stats;
	i = context->num_stats-1;
	
	for (p=ppm_data->found_state ; p != context->con_ut.u.stats ; p--) {
		ppmd_swap(&p[0], &p[-1]);
	}
	context->con_ut.u.stats->freq += 4;
	context->con_ut.u.summ_freq += 4;
	esc_freq = context->con_ut.u.summ_freq - p->freq;
	adder = (ppm_data->order_fall != 0);
	context->con_ut.u.summ_freq = (p->freq = (p->freq+adder) >> 1);
	do {
		esc_freq -= (++p)->freq;
		context->con_ut.u.summ_freq += (p->freq = (p->freq + adder) >> 1);
		if (p[0].freq > p[-1].freq) {
			struct state_tag tmp = *(p1=p);
			do {
				p1[0] = p1[-1];
			} while (--p1 != context->con_ut.u.stats && tmp.freq > p1[-1].freq);
			*p1 = tmp;
		}
	} while (--i);
	
	if (p->freq == 0) {
		do {
			i++;
		} while ((--p)->freq == 0);
		esc_freq += i;
		if ((context->num_stats -= i) == 1) {
			struct state_tag tmp = *context->con_ut.u.stats;
			do {
				tmp.freq -= (tmp.freq >> 1);
				esc_freq >>= 1;
			} while (esc_freq > 1);
			sub_allocator_free_units(&ppm_data->sub_alloc,
					context->con_ut.u.stats, (old_ns+1)>>1);
			*(ppm_data->found_state=&context->con_ut.one_state)=tmp;
			return;
		}
	}
	context->con_ut.u.summ_freq += (esc_freq -= (esc_freq >> 1));
	n0 = (old_ns+1) >> 1;
	n1 = (context->num_stats+1) >> 1;
	if (n0 != n1) {
		context->con_ut.u.stats = (struct state_tag *) sub_allocator_shrink_units(&ppm_data->sub_alloc,
						context->con_ut.u.stats, n0, n1);
	}
	ppm_data->found_state = context->con_ut.u.stats;
}

static struct ppm_context *create_child(ppm_data_t *ppm_data, struct ppm_context *context,
				struct state_tag *pstats, struct state_tag *first_state)
{
	struct ppm_context *pc;
	rar_dbgmsg("in create_child\n");
	pc = (struct ppm_context *) sub_allocator_alloc_context(&ppm_data->sub_alloc);
	if (pc) {
		pc->num_stats = 1;
		pc->con_ut.one_state = *first_state;
		pc->suffix = context;
		pstats->successor = pc;
	}
	return pc;
}

static struct ppm_context *create_successors(ppm_data_t *ppm_data,
			int skip, struct state_tag *p1)
{
	struct state_tag up_state;
	struct ppm_context *pc, *up_branch;
	struct state_tag *p, *ps[MAX_O], **pps;
	unsigned int cf, s0;
	
	rar_dbgmsg("in create_successors\n");
	pc = ppm_data->min_context;
	up_branch = ppm_data->found_state->successor;
	pps = ps;
	
	if (!skip) {
		*pps++ = ppm_data->found_state;
		if (!pc->suffix) {
			goto NO_LOOP;
		}
	}
	if (p1) {
		p = p1;
		pc = pc->suffix;
		goto LOOP_ENTRY;
	}
	do {
		pc = pc->suffix;
		if (pc->num_stats != 1) {
			if ((p=pc->con_ut.u.stats)->symbol != ppm_data->found_state->symbol) {
				do {
					p++;
				} while (p->symbol != ppm_data->found_state->symbol);
			}
		} else {
			p = &(pc->con_ut.one_state);
		}
LOOP_ENTRY:
		if (p->successor != up_branch) {
			pc = p->successor;
			break;
		}
		*pps++ = p;
	} while (pc->suffix);
NO_LOOP:
	if (pps == ps) {
		return pc;
	}
	up_state.symbol= *(uint8_t *) up_branch;
	up_state.successor = (struct ppm_context *) (((uint8_t *) up_branch)+1);
	if (pc->num_stats != 1) {
		if ((uint8_t *) pc <= ppm_data->sub_alloc.ptext) {
			return NULL;
		}
		if ((p=pc->con_ut.u.stats)->symbol != up_state.symbol) {
			do {
				p++;
				if ((void *)p > (void *) ppm_data->sub_alloc.heap_end) {
					return NULL;
				}
			} while (p->symbol != up_state.symbol);
		}
		cf = p->freq - 1;
		s0 = pc->con_ut.u.summ_freq - pc->num_stats - cf;
		up_state.freq = 1 + ((2*cf <= s0)?(5*cf > s0):((2*cf+3*s0-1)/(2*s0)));
	} else {
		up_state.freq = pc->con_ut.one_state.freq;
	}
	do {
		pc = create_child(ppm_data, pc, *--pps, &up_state);
		if (!pc) {
			rar_dbgmsg("create_child failed\n");
			return NULL;
		}
	} while (pps != ps);
	return pc;
}

static int update_model(ppm_data_t *ppm_data)
{
	struct state_tag fs, *p;
	struct ppm_context *pc, *successor;
	unsigned int ns1, ns, cf, sf, s0;

	rar_dbgmsg("in update_model\n");
	fs = *ppm_data->found_state;
	p = NULL;

	if (fs.freq < MAX_FREQ/4 && (pc=ppm_data->min_context->suffix) != NULL) {
		if (pc->num_stats != 1) {
			if ((p=pc->con_ut.u.stats)->symbol != fs.symbol) {
				do {
					p++;
				} while (p->symbol != fs.symbol);
				if (p[0].freq >= p[-1].freq) {
					ppmd_swap(&p[0], &p[-1]);
					p--;
				}
			}
			if (p->freq < MAX_FREQ-9) {
				p->freq += 2;
				pc->con_ut.u.summ_freq += 2;
			}
		} else {
			p = &(pc->con_ut.one_state);
			p->freq += (p->freq < 32);
		}
	}
	if (!ppm_data->order_fall) {
		ppm_data->min_context = ppm_data->max_context =
			ppm_data->found_state->successor = create_successors(ppm_data, TRUE, p);
		if (!ppm_data->min_context) {
			goto RESTART_MODEL;
		}
		return TRUE;
	}
	*ppm_data->sub_alloc.ptext++ = fs.symbol;
	successor = (struct ppm_context *) ppm_data->sub_alloc.ptext;
	if (ppm_data->sub_alloc.ptext >= ppm_data->sub_alloc.fake_units_start) {
		goto RESTART_MODEL;
	}
	if (fs.successor) {
		if ((uint8_t *)fs.successor <= ppm_data->sub_alloc.ptext &&
				(fs.successor = create_successors(ppm_data, FALSE, p)) == NULL) {
			goto RESTART_MODEL;
		}
		if (!--ppm_data->order_fall) {
			successor = fs.successor;
			ppm_data->sub_alloc.ptext -= (ppm_data->max_context != ppm_data->min_context);
		}
	} else {
		ppm_data->found_state->successor = successor;
		fs.successor = ppm_data->min_context;
	}
	s0 = ppm_data->min_context->con_ut.u.summ_freq-(ns=ppm_data->min_context->num_stats)-(fs.freq-1);
	for (pc=ppm_data->max_context; pc != ppm_data->min_context ; pc=pc->suffix) {
		if ((ns1=pc->num_stats) != 1) {
			if ((ns1 & 1) == 0) {
				pc->con_ut.u.stats = (struct state_tag *)
					sub_allocator_expand_units(&ppm_data->sub_alloc,
								pc->con_ut.u.stats, ns1>>1);
				if (!pc->con_ut.u.stats) {
					goto RESTART_MODEL;
				}
			}
			pc->con_ut.u.summ_freq += (2*ns1 < ns)+2*((4*ns1 <= ns) & (pc->con_ut.u.summ_freq <= 8*ns1));
		} else {
			p = (struct state_tag *) sub_allocator_alloc_units(&ppm_data->sub_alloc, 1);
			if (!p) {
				goto RESTART_MODEL;
			}
			*p = pc->con_ut.one_state;
			pc->con_ut.u.stats = p;
			if (p->freq < MAX_FREQ/4-1) {
				p->freq += p->freq;
			} else {
				p->freq = MAX_FREQ - 4;
			}
			pc->con_ut.u.summ_freq = p->freq + ppm_data->init_esc + (ns > 3);
		}
		cf = 2*fs.freq*(pc->con_ut.u.summ_freq+6);
		sf = s0 + pc->con_ut.u.summ_freq;
		if (cf < 6*sf) {
			cf = 1 + (cf > sf) + (cf >= 4*sf);
			pc->con_ut.u.summ_freq += 3;
		} else {
			cf = 4 + (cf >= 9*sf) + (cf >= 12*sf) + (cf >= 15*sf);
			pc->con_ut.u.summ_freq += cf;
		}
		p = pc->con_ut.u.stats + ns1;
		p->successor = successor;
		p->symbol = fs.symbol;
		p->freq = cf;
		pc->num_stats = ++ns1;
	}
	ppm_data->max_context = ppm_data->min_context = fs.successor;
	return TRUE;
	
RESTART_MODEL:
	if (!restart_model_rare(ppm_data)) {
	    rar_dbgmsg("unrar: update_model: restart_model_rare: failed\n");
	    return FALSE;
	}
	ppm_data->esc_count = 0;
	return TRUE;
}

static void update1(ppm_data_t *ppm_data, struct state_tag *p, struct ppm_context *context)
{
	rar_dbgmsg("in update1\n");
	(ppm_data->found_state=p)->freq += 4;
	context->con_ut.u.summ_freq += 4;
	if (p[0].freq > p[-1].freq) {
		ppmd_swap(&p[0], &p[-1]);
		ppm_data->found_state = --p;
		if (p->freq > MAX_FREQ) {
			rescale(ppm_data, context);
		}
	}
}

static int ppm_decode_symbol1(ppm_data_t *ppm_data, struct ppm_context *context)
{
	struct state_tag *p;
	int i, hi_cnt, count;
	
	rar_dbgmsg("in ppm_decode_symbol1\n");
	ppm_data->coder.scale = context->con_ut.u.summ_freq;
	p = context->con_ut.u.stats;
	count = coder_get_current_count(&ppm_data->coder);
	if (count >= ppm_data->coder.scale) {
		return FALSE;
	}
	if (count < (hi_cnt = p->freq)) {
		ppm_data->prev_success = (2 * (ppm_data->coder.high_count=hi_cnt) >
						ppm_data->coder.scale);
		ppm_data->run_length += ppm_data->prev_success;
		(ppm_data->found_state=p)->freq=(hi_cnt += 4);
		context->con_ut.u.summ_freq += 4;
		if (hi_cnt > MAX_FREQ) {
			rescale(ppm_data, context);
		}
		ppm_data->coder.low_count = 0;
		return TRUE;
	} else if (ppm_data->found_state == NULL) {
		return FALSE;
	}
	ppm_data->prev_success = 0;
	i = context->num_stats-1;
	while ((hi_cnt += (++p)->freq) <= count) {
		if (--i == 0) {
			ppm_data->hi_bits_flag = ppm_data->hb2flag[ppm_data->found_state->symbol];
			ppm_data->coder.low_count = hi_cnt;
			ppm_data->char_mask[p->symbol] = ppm_data->esc_count;
			i = (ppm_data->num_masked=context->num_stats) - 1;
			ppm_data->found_state = NULL;
			do {
				ppm_data->char_mask[(--p)->symbol] = ppm_data->esc_count;
			} while (--i);
			ppm_data->coder.high_count = ppm_data->coder.scale;
			return TRUE;
		}
	}
	ppm_data->coder.low_count = (ppm_data->coder.high_count = hi_cnt) - p->freq;
	update1(ppm_data, p, context);
	return TRUE;
}

static const uint8_t ExpEscape[16]={ 25,14, 9, 7, 5, 5, 4, 4, 4, 3, 3, 3, 2, 2, 2, 2 };
#define GET_MEAN(SUMM,SHIFT,ROUND) ((SUMM+(1 << (SHIFT-ROUND))) >> (SHIFT))

static void ppm_decode_bin_symbol(ppm_data_t *ppm_data, struct ppm_context *context)
{
	struct state_tag *rs;
	uint16_t *bs;
	
	rar_dbgmsg("in ppm_decode_bin_symbol\n");
	
	rs = &context->con_ut.one_state;
	
	ppm_data->hi_bits_flag = ppm_data->hb2flag[ppm_data->found_state->symbol];
	bs = &ppm_data->bin_summ[rs->freq-1][ppm_data->prev_success +
		ppm_data->ns2bsindx[context->suffix->num_stats-1] +
		ppm_data->hi_bits_flag+2*ppm_data->hb2flag[rs->symbol] +
		((ppm_data->run_length >> 26) & 0x20)];
	if (coder_get_current_shift_count(&ppm_data->coder, TOT_BITS) < *bs) {
		ppm_data->found_state = rs;
		rs->freq += (rs->freq < 128);
		ppm_data->coder.low_count = 0;
		ppm_data->coder.high_count = *bs;
		*bs = (uint16_t) (*bs + INTERVAL - GET_MEAN(*bs, PERIOD_BITS, 2));
		ppm_data->prev_success = 1;
		ppm_data->run_length++;
	} else {
		ppm_data->coder.low_count = *bs;
		*bs = (uint16_t) (*bs - GET_MEAN(*bs, PERIOD_BITS, 2));
		ppm_data->coder.high_count = BIN_SCALE;
		ppm_data->init_esc = ExpEscape[*bs >> 10];
		ppm_data->num_masked = 1;
		ppm_data->char_mask[rs->symbol] = ppm_data->esc_count;
		ppm_data->prev_success = 0;
		ppm_data->found_state = NULL;
	}
}

static void update2(ppm_data_t *ppm_data, struct state_tag *p, struct ppm_context *context)
{
	rar_dbgmsg("in update2\n");
	(ppm_data->found_state = p)->freq += 4;
	context->con_ut.u.summ_freq += 4;
	if (p->freq > MAX_FREQ) {
		rescale(ppm_data, context);
	}
	ppm_data->esc_count++;
	ppm_data->run_length = ppm_data->init_rl;
}

static struct see2_context_tag *make_esc_freq(ppm_data_t *ppm_data,
			struct ppm_context *context, int diff)
{
	struct see2_context_tag *psee2c;
	
	if (context->num_stats != 256) {
		psee2c = ppm_data->see2cont[ppm_data->ns2indx[diff-1]] +
			(diff < context->suffix->num_stats-context->num_stats) +
			2 * (context->con_ut.u.summ_freq < 11*context->num_stats)+4*
			(ppm_data->num_masked > diff) +	ppm_data->hi_bits_flag;
		ppm_data->coder.scale = get_mean(psee2c);
	} else {
		psee2c = &ppm_data->dummy_sse2cont;
		ppm_data->coder.scale = 1;
	}
	return psee2c;
}

static int ppm_decode_symbol2(ppm_data_t *ppm_data, struct ppm_context *context)
{
	int count, hi_cnt, i;
	struct see2_context_tag *psee2c;
	struct state_tag *ps[256], **pps, *p;
	
	rar_dbgmsg("in ppm_decode_symbol2\n");
	i = context->num_stats - ppm_data->num_masked;
	psee2c = make_esc_freq(ppm_data, context, i);
	pps = ps;
	p = context->con_ut.u.stats - 1;
	hi_cnt = 0;
	
	do {
		do {
			p++;
		} while (ppm_data->char_mask[p->symbol] == ppm_data->esc_count);
		hi_cnt += p->freq;
		*pps++ = p;
	} while (--i);
	ppm_data->coder.scale += hi_cnt;
	count = coder_get_current_count(&ppm_data->coder);
	if (count >= ppm_data->coder.scale) {
		return FALSE;
	}
	p=*(pps=ps);
	if (count < hi_cnt) {
		hi_cnt = 0;
		while ((hi_cnt += p->freq) <= count) {
			p=*++pps;
		}
		ppm_data->coder.low_count = (ppm_data->coder.high_count=hi_cnt) - p->freq;
		update(psee2c);
		update2(ppm_data, p, context);
	} else {
		ppm_data->coder.low_count = hi_cnt;
		ppm_data->coder.high_count = ppm_data->coder.scale;
		i = context->num_stats - ppm_data->num_masked;
		pps--;
		do {
			ppm_data->char_mask[(*++pps)->symbol] = ppm_data->esc_count;
		} while (--i);
		psee2c->summ += ppm_data->coder.scale;
		ppm_data->num_masked = context->num_stats;
	}
	return TRUE;
}

static void clear_mask(ppm_data_t *ppm_data)
{
	ppm_data->esc_count = 1;
	memset(ppm_data->char_mask, 0, sizeof(ppm_data->char_mask));
}

void ppm_constructor(ppm_data_t *ppm_data)
{
	sub_allocator_init(&ppm_data->sub_alloc);
	ppm_data->min_context = NULL;
	ppm_data->max_context = NULL;
}

void ppm_destructor(ppm_data_t *ppm_data)
{
	sub_allocator_stop_sub_allocator(&ppm_data->sub_alloc);
}

void ppm_cleanup(ppm_data_t *ppm_data)
{
	sub_allocator_stop_sub_allocator(&ppm_data->sub_alloc);
	sub_allocator_start_sub_allocator(&ppm_data->sub_alloc, 1);
	start_model_rare(ppm_data, 2);
}

int ppm_decode_init(ppm_data_t *ppm_data, int fd, unpack_data_t *unpack_data, int *EscChar)
{
	int max_order, Reset, MaxMB;
	
	max_order = rar_get_char(fd, unpack_data);
	rar_dbgmsg("ppm_decode_init max_order=%d\n", max_order);
	Reset = (max_order & 0x20) ? 1 : 0;
	rar_dbgmsg("ppm_decode_init Reset=%d\n", Reset);
	if (Reset) {
		MaxMB = rar_get_char(fd, unpack_data);
		rar_dbgmsg("ppm_decode_init MaxMB=%d\n", MaxMB);
	} else {
		if (sub_allocator_get_allocated_memory(&ppm_data->sub_alloc) == 0) {
			return FALSE;
		}
	}
	if (max_order & 0x40) {
		*EscChar = rar_get_char(fd, unpack_data);
		rar_dbgmsg("ppm_decode_init EscChar=%d\n", *EscChar);
	}
	range_coder_init_decoder(&ppm_data->coder, fd, unpack_data);
	if (Reset) {
		max_order = (max_order & 0x1f) + 1;
		if (max_order > 16) {
			max_order = 16 + (max_order - 16) * 3;
		}
		if (max_order == 1) {
			sub_allocator_stop_sub_allocator(&ppm_data->sub_alloc);
			return FALSE;
		}
		if(!sub_allocator_start_sub_allocator(&ppm_data->sub_alloc, MaxMB+1)) {
		    sub_allocator_stop_sub_allocator(&ppm_data->sub_alloc);
		    return FALSE;
		}
		if (!start_model_rare(ppm_data, max_order)) {
		    sub_allocator_stop_sub_allocator(&ppm_data->sub_alloc);
		    return FALSE;
		}
	}
	rar_dbgmsg("ppm_decode_init done: %d\n", ppm_data->min_context != NULL);
	return (ppm_data->min_context != NULL);
}

int ppm_decode_char(ppm_data_t *ppm_data, int fd, unpack_data_t *unpack_data)
{
	int symbol;

	if ((uint8_t *) ppm_data->min_context <= ppm_data->sub_alloc.ptext ||
			(uint8_t *)ppm_data->min_context > ppm_data->sub_alloc.heap_end) {
		return -1;
	}
	if (ppm_data->min_context->num_stats != 1) {
		if ((uint8_t *) ppm_data->min_context->con_ut.u.stats <= ppm_data->sub_alloc.ptext ||
			(uint8_t *) ppm_data->min_context->con_ut.u.stats > ppm_data->sub_alloc.heap_end) {
			return -1;
		}
		if (!ppm_decode_symbol1(ppm_data, ppm_data->min_context)) {
			return -1;
		}
	} else {
		ppm_decode_bin_symbol(ppm_data, ppm_data->min_context);
	}
	coder_decode(&ppm_data->coder);
	
	while (!ppm_data->found_state) {
		ARI_DEC_NORMALISE(fd, unpack_data, ppm_data->coder.code, 
				ppm_data->coder.low, ppm_data->coder.range);
		do {
			ppm_data->order_fall++;
			ppm_data->min_context = ppm_data->min_context->suffix;
			if ((uint8_t *)ppm_data->min_context <= ppm_data->sub_alloc.ptext ||
					(uint8_t *)ppm_data->min_context >
					ppm_data->sub_alloc.heap_end) {
				return -1;
			}
		} while (ppm_data->min_context->num_stats == ppm_data->num_masked);
		if (!ppm_decode_symbol2(ppm_data, ppm_data->min_context)) {
			return -1;
		}
		coder_decode(&ppm_data->coder);
	}
	
	symbol = ppm_data->found_state->symbol;
	if (!ppm_data->order_fall && (uint8_t *) ppm_data->found_state->successor > ppm_data->sub_alloc.ptext) {
		ppm_data->min_context = ppm_data->max_context = ppm_data->found_state->successor;
	} else {
		if(!update_model(ppm_data)) {
		    rar_dbgmsg("unrar: ppm_decode_char: update_model failed\n");
		    return -1;
		}

		if (ppm_data->esc_count == 0) {
			clear_mask(ppm_data);
		}
	}
	ARI_DEC_NORMALISE(fd, unpack_data, ppm_data->coder.code, ppm_data->coder.low,
				ppm_data->coder.range);
	return symbol;
}