/*
  *  Extract RAR archives
  *
  *  Copyright (C) 2005 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.
  *
  */
 
 #include "libclamunrar/unrar.h"
 #include "libclamunrar/unrar15.h"
 #include <string.h>
 
 #define STARTL1  2
 static unsigned int dec_l1[]={0x8000,0xa000,0xc000,0xd000,0xe000,0xea00,
 			0xee00,0xf000,0xf200,0xf200,0xffff};
 static unsigned int pos_l1[]={0,0,0,2,3,5,7,11,16,20,24,32,32};
 
 #define STARTL2  3
 static unsigned int dec_l2[]={0xa000,0xc000,0xd000,0xe000,0xea00,0xee00,
 			0xf000,0xf200,0xf240,0xffff};
 static unsigned int pos_l2[]={0,0,0,0,5,7,9,13,18,22,26,34,36};
 
 #define STARTHF0  4
 static unsigned int dec_hf0[]={0x8000,0xc000,0xe000,0xf200,0xf200,0xf200,
 			0xf200,0xf200,0xffff};
 static unsigned int pos_hf0[]={0,0,0,0,0,8,16,24,33,33,33,33,33};
 
 
 #define STARTHF1  5
 static unsigned int dec_hf1[]={0x2000,0xc000,0xe000,0xf000,0xf200,0xf200,
 			0xf7e0,0xffff};
 static unsigned int pos_hf1[]={0,0,0,0,0,0,4,44,60,76,80,80,127};
 
 
 #define STARTHF2  5
 static unsigned int dec_hf2[]={0x1000,0x2400,0x8000,0xc000,0xfa00,0xffff,
 			0xffff,0xffff};
 static unsigned int pos_hf2[]={0,0,0,0,0,0,2,7,53,117,233,0,0};
 
 
 #define STARTHF3  6
 static unsigned int dec_hf3[]={0x800,0x2400,0xee00,0xfe80,0xffff,0xffff,
 			0xffff};
 static unsigned int pos_hf3[]={0,0,0,0,0,0,0,2,16,218,251,0,0};
 
 
 #define STARTHF4  8
 static unsigned int dec_hf4[]={0xff00,0xffff,0xffff,0xffff,0xffff,0xffff};
 static unsigned int pos_hf4[]={0,0,0,0,0,0,0,0,0,255,0,0,0};
 
 static void unpack_init_data15(int solid, unpack_data_t *unpack_data)
 {
 	if (!solid) {
 		unpack_data->avr_plcb = unpack_data->avr_ln1 = unpack_data->avr_ln2 =
 			unpack_data->avr_ln3 = unpack_data->num_huf =
 			unpack_data->buf60 = 0;
 		unpack_data->avr_plc = 0x3500;
 		unpack_data->max_dist3 = 0x2001;
 		unpack_data->nhfb = unpack_data->nlzb = 0x80;
 	}
 	
 	unpack_data->flags_cnt = 0;
 	unpack_data->flag_buf = 0;
 	unpack_data->st_mode = 0;
 	unpack_data->lcount = 0;
 	unpack_data->read_top = 0;
 }
 
 static void corr_huff(unpack_data_t *unpack_data, unsigned int *char_set,
 			unsigned int *num_to_place)
 {
 	int i, j;
 	
 	for (i=7 ; i >= 0 ; i--) {
 		for (j=0 ; j < 32 ; j++, char_set++) {
 			*char_set = (*char_set & ~0xff) | i;
 		}
 	}
 	memset(num_to_place, 0, sizeof(unpack_data->ntopl));
 	for (i=6 ; i >= 0 ; i--) {
 		num_to_place[i] = (7-i) * 32;
 	}
 }
 
 static void init_huff(unpack_data_t *unpack_data)
 {
 	unsigned int i;
 	
 	for (i=0 ; i<256 ; i++) {
 		unpack_data->place[i] = unpack_data->placea[i] = unpack_data->placeb[i] = i;
 		unpack_data->placec[i] = (~i+1) & 0xff;
 		unpack_data->chset[i] = unpack_data->chsetb[i] = i << 8;
 		unpack_data->chseta[i] = i;
 		unpack_data->chsetc[i] = ((~i+1) & 0xff) << 8;
 	}
 	memset(unpack_data->ntopl, 0, sizeof(unpack_data->ntopl));
 	memset(unpack_data->ntoplb, 0, sizeof(unpack_data->ntoplb));
 	memset(unpack_data->ntoplc, 0, sizeof(unpack_data->ntoplc));
 	corr_huff(unpack_data, unpack_data->chsetb, unpack_data->ntoplb);
 }
 
 static void copy_string15(unpack_data_t *unpack_data, unsigned int distance,
 				unsigned int length)
 {
 	unpack_data->dest_unp_size -= length;
 	while (length--) {
 		unpack_data->window[unpack_data->unp_ptr] =
 			unpack_data->window[(unpack_data->unp_ptr - distance) & MAXWINMASK];
 		unpack_data->unp_ptr = (unpack_data->unp_ptr + 1) & MAXWINMASK;
 	}
 }
 
 static unsigned int decode_num(unpack_data_t *unpack_data, int num, unsigned int start_pos,
 			unsigned int *dec_tab, unsigned int *pos_tab)
 {
 	int i;
 	
 	for (num&=0xfff0, i=0 ; dec_tab[i] <= num ; i++) {
 		start_pos++;
 	}
 	rar_addbits(unpack_data, start_pos);
 	return (((num-(i ? dec_tab[i-1]:0)) >> (16-start_pos)) + pos_tab[start_pos]);
 }
 
 static void huff_decode(unpack_data_t *unpack_data)
 {
 	unsigned int cur_byte, new_byte_place, length, distance, bit_field;
 	int byte_place;
 	
 	bit_field = rar_getbits(unpack_data);
 	
 	if (unpack_data->avr_plc > 0x75ff) {
 		byte_place = decode_num(unpack_data, bit_field,
 					STARTHF4, dec_hf4, pos_hf4);
 	} else if (unpack_data->avr_plc > 0x5dff) {
 		byte_place = decode_num(unpack_data, bit_field,
 					STARTHF3, dec_hf3, pos_hf3);
 	} else if (unpack_data->avr_plc > 0x35ff) {
 		byte_place = decode_num(unpack_data, bit_field,
 					STARTHF2, dec_hf2, pos_hf2);
 	} else if (unpack_data->avr_plc > 0x0dff) {
 		byte_place = decode_num(unpack_data, bit_field,
 					STARTHF1, dec_hf1, pos_hf1);
 	} else {
 		byte_place = decode_num(unpack_data, bit_field,
 					STARTHF0, dec_hf0, pos_hf0);
 	}
 	
 	byte_place &= 0xff;
 	if (unpack_data->st_mode) {
 		if (byte_place == 0 && bit_field > 0xfff) {
 			byte_place = 0x100;
 		}
 		if (--byte_place == -1) {
 			bit_field = rar_getbits(unpack_data);
 			rar_addbits(unpack_data, 1);
 			if (bit_field & 0x8000) {
 				unpack_data->num_huf = unpack_data->st_mode = 0;
 				return;
 			} else {
 				length = (bit_field & 0x4000) ? 4 : 3;
 				rar_addbits(unpack_data, 1);
 				distance = decode_num(unpack_data, rar_getbits(unpack_data),
 					STARTHF2, dec_hf2, pos_hf2);
 				distance = (distance << 5) | (rar_getbits(unpack_data) >> 11);
 				rar_addbits(unpack_data, 5);
 				copy_string15(unpack_data, distance, length);
 				return;
 			}
 		}
 	} else if (unpack_data->num_huf++ >= 16 && unpack_data->flags_cnt == 0) {
 		unpack_data->st_mode = 1;
 	}
 	unpack_data->avr_plc += byte_place;
 	unpack_data->avr_plc -= unpack_data->avr_plc >> 8;
 	unpack_data->nhfb += 16;
 	if (unpack_data->nhfb > 0xff) {
 		unpack_data->nhfb = 0x90;
 		unpack_data->nlzb >>= 1;
 	}
 	
 	unpack_data->window[unpack_data->unp_ptr++] = 

 			(unsigned char) (unpack_data->chset[byte_place & 0xff] >>8);

 	--unpack_data->dest_unp_size;
 	
 	while (1) {

 		cur_byte = unpack_data->chset[byte_place & 0xff];

 		new_byte_place = unpack_data->ntopl[cur_byte++ & 0xff]++;
 		if ((cur_byte & 0xff) > 0xa1) {
 			corr_huff(unpack_data, unpack_data->chset, unpack_data->ntopl);
 		} else {
 			break;
 		}
 	}
 	

 	unpack_data->chset[byte_place & 0xff] = unpack_data->chset[new_byte_place & 0xff];
 	unpack_data->chset[new_byte_place & 0xff] = cur_byte;

 }
 
 	
 	
 static void get_flag_buf(unpack_data_t *unpack_data)
 {
 	unsigned int flags, new_flags_place, flags_place;
 	
 	flags_place = decode_num(unpack_data, rar_getbits(unpack_data), STARTHF2,
 				dec_hf2, pos_hf2);
 	for (;;) {

 		flags = unpack_data->chsetc[flags_place & 0xff];

 		unpack_data->flag_buf = flags >> 8;
 		new_flags_place = unpack_data->ntoplc[flags++ & 0xff]++;
 		if ((flags & 0xff) != 0) {
 			break;
 		}
 		corr_huff(unpack_data, unpack_data->chsetc, unpack_data->ntoplc);
 	}

 	unpack_data->chsetc[flags_place & 0xff] = unpack_data->chsetc[new_flags_place & 0xff];
 	unpack_data->chsetc[new_flags_place & 0xff] = flags;

 }
 
 static void short_lz(unpack_data_t *unpack_data)
 {
 	static unsigned int short_len1[]={1,3,4,4,5,6,7,8,8,4,4,5,6,6,4,0};
 	static unsigned int short_xor1[]={0,0xa0,0xd0,0xe0,0xf0,0xf8,0xfc,0xfe,
 			0xff,0xc0,0x80,0x90,0x98,0x9c,0xb0};
 	static unsigned int short_len2[]={2,3,3,3,4,4,5,6,6,4,4,5,6,6,4,0};
 	static unsigned int short_xor2[]={0,0x40,0x60,0xa0,0xd0,0xe0,0xf0,0xf8,
 			0xfc,0xc0,0x80,0x90,0x98,0x9c,0xb0};
 
 	unsigned int length, save_length, last_distance, distance, bit_field;
 	int distance_place;
 	
 	unpack_data->num_huf = 0;
 	bit_field = rar_getbits(unpack_data);
 	if (unpack_data->lcount == 2) {
 		rar_addbits(unpack_data, 1);
 		if (bit_field >= 0x8000) {
 			copy_string15(unpack_data,
 				(unsigned int)unpack_data->last_dist,
 				unpack_data->last_length);
 			return;
 		}
 		bit_field <<= 1;
 		unpack_data->lcount = 0;
 	}
 	
 	bit_field >>= 8;
 	short_len1[1] = short_len2[3] = unpack_data->buf60+3;
 	if (unpack_data->avr_ln1 < 37) {
 		for (length=0 ;; length++) {
 			if (((bit_field^short_xor1[length]) &
 					(~(0xff>>short_len1[length]))) == 0) {
 				break;
 			}
 		}
 		rar_addbits(unpack_data, short_len1[length]);
 	} else {
 		for (length=0; ;length++) {
 				if (((bit_field^short_xor2[length]) &
 						(~(0xff>>short_len2[length]))) == 0) {
 					break;
 				}
 		}
 		rar_addbits(unpack_data, short_len2[length]);
 	}
 	
 	if (length >= 9) {
 		if (length == 9) {
 			unpack_data->lcount++;
 			copy_string15(unpack_data, (unsigned int) unpack_data->last_dist,
 				unpack_data->last_length);
 			return;
 		}
 		if (length == 14) {
 			unpack_data->lcount = 0;
 			length = decode_num(unpack_data, rar_getbits(unpack_data),
 					STARTL2, dec_l2, pos_l2) + 5;
 			distance = (rar_getbits(unpack_data) >> 1) | 0x8000;
 			rar_addbits(unpack_data, 15);
 			unpack_data->last_length = length;
 			unpack_data->last_dist = distance;
 			copy_string15(unpack_data, distance, length);
 			return;
 		}
 		
 		unpack_data->lcount = 0;
 		save_length = length;
 		distance = unpack_data->old_dist[(unpack_data->old_dist_ptr-(length-9)) & 3];
 		length = decode_num(unpack_data,
 				rar_getbits(unpack_data), STARTL1, dec_l1, pos_l1) + 2;
 		if (length == 0x101 && save_length == 10) {
 			unpack_data->buf60 ^= 1;
 			return;
 		}
 		if (distance > 256) {
 			length++;
 		}
 		if (distance >= unpack_data->max_dist3) {
 			length++;
 		}
 		
 		unpack_data->old_dist[unpack_data->old_dist_ptr++] = distance;
 		unpack_data->old_dist_ptr = unpack_data->old_dist_ptr & 3;
 		unpack_data->last_length = length;
 		unpack_data->last_dist = distance;
 		copy_string15(unpack_data, distance, length);
 		return;
 	}
 	
 	unpack_data->lcount = 0;
 	unpack_data->avr_ln1 += length;
 	unpack_data->avr_ln1 -= unpack_data->avr_ln1 >> 4;
 	
 	distance_place = decode_num(unpack_data, rar_getbits(unpack_data),
 					STARTHF2, dec_hf2, pos_hf2) & 0xff;

 	distance = unpack_data->chseta[distance_place & 0xff];

 	if (--distance_place != -1) {

 		unpack_data->placea[distance & 0xff]--;
 		last_distance = unpack_data->chseta[distance_place & 0xff];
 		unpack_data->placea[last_distance & 0xff]++;
 		unpack_data->chseta[(distance_place+1) & 0xff] = last_distance;
 		unpack_data->chseta[distance_place & 0xff] = distance;

 	}
 	length += 2;
 	unpack_data->old_dist[unpack_data->old_dist_ptr++] = ++distance;
 	unpack_data->old_dist_ptr = unpack_data->old_dist_ptr & 3;
 	unpack_data->last_length = length;
 	unpack_data->last_dist = distance;
 	copy_string15(unpack_data, distance, length);
 }
 
 static void long_lz(unpack_data_t *unpack_data)
 {
 	unsigned int length, distance, distance_place, new_distance_place;
 	unsigned int old_avr2, old_avr3, bit_field;
 	
 	unpack_data->num_huf = 0;
 	unpack_data->nlzb += 16;
 	
 	if (unpack_data->nlzb > 0xff) {
 		unpack_data->nlzb = 0x90;
 		unpack_data->nhfb >>= 1;
 	}
 	old_avr2 = unpack_data->avr_ln2;
 	
 	bit_field = rar_getbits(unpack_data);
 	if (unpack_data->avr_ln2 >= 122) {
 		length = decode_num(unpack_data, bit_field, STARTL2, dec_l2, pos_l2);
 	} else if (unpack_data->avr_ln2 >= 64) {
 		length = decode_num(unpack_data, bit_field, STARTL1, dec_l1, pos_l1);
 	} else if (bit_field < 0x100) {
 		length = bit_field;
 		rar_addbits(unpack_data, 16);
 	} else {
 		for (length=0 ; ((bit_field << length) & 0x8000)==0 ; length++) {
 			/* Empty loop */
 		}
 		rar_addbits(unpack_data, length+1);
 	}
 	
 	unpack_data->avr_ln2 += length;
 	unpack_data->avr_ln2 -= unpack_data->avr_ln2 >> 5;
 	
 	bit_field = rar_getbits(unpack_data);
 	if (unpack_data->avr_plcb > 0x28ff) {
 		distance_place = decode_num(unpack_data, bit_field, STARTHF2,
 					dec_hf2, pos_hf2);
 	} else if (unpack_data->avr_plcb > 0x6ff) {
 		distance_place = decode_num(unpack_data, bit_field, STARTHF1,
 					dec_hf1, pos_hf1);
 	} else {
 		distance_place = decode_num(unpack_data, bit_field, STARTHF0,
 					dec_hf0, pos_hf0);
 	}
 	
 	unpack_data->avr_plcb += distance_place;
 	unpack_data->avr_plcb -= unpack_data->avr_plcb >> 8;
 	for (;;) {
 		distance = unpack_data->chsetb[distance_place & 0xff];
 		new_distance_place = unpack_data->ntoplb[distance++ & 0xff]++;
 		if (!(distance & 0xff)) {
 			corr_huff(unpack_data, unpack_data->chsetb, unpack_data->ntoplb);
 		} else {
 			break;
 		}
 	}
 	

 	unpack_data->chsetb[distance_place & 0xff] = unpack_data->chsetb[new_distance_place & 0xff];
 	unpack_data->chsetb[new_distance_place & 0xff] = distance;

 	
 	distance = ((distance & 0xff00) | (rar_getbits(unpack_data) >> 8)) >> 1;
 	rar_addbits(unpack_data, 7);
 	
 	old_avr3 = unpack_data->avr_ln3;
 	if (length != 1 && length != 4) {
 		if (length==0 && distance <= unpack_data->max_dist3) {
 			unpack_data->avr_ln3++;
 			unpack_data->avr_ln3 -= unpack_data->avr_ln3 >> 8;
 		} else if (unpack_data->avr_ln3 > 0) {
 			unpack_data->avr_ln3--;
 		}
 	}
 	
 	length += 3;
 	
 	if (distance >= unpack_data->max_dist3) {
 		length++;
 	}
 	if (distance <= 256) {
 		length += 8;
 	}
 	if (old_avr3 > 0xb0 || (unpack_data->avr_plc >= 0x2a00 && old_avr2 < 0x40)) {
 		unpack_data->max_dist3 = 0x7f00;
 	} else {
 		unpack_data->max_dist3 = 0x2001;
 	}
 	unpack_data->old_dist[unpack_data->old_dist_ptr++] = distance;
 	unpack_data->old_dist_ptr = unpack_data->old_dist_ptr & 3;
 	unpack_data->last_length = length;
 	unpack_data->last_dist = distance;
 	copy_string15(unpack_data, distance, length);
 }
 
 int rar_unpack15(int fd, int solid, unpack_data_t *unpack_data)
 {
 	rar_unpack_init_data(solid, unpack_data);
 	unpack_init_data15(solid, unpack_data);
 	if (!rar_unp_read_buf(fd, unpack_data)) {
 		return FALSE;
 	}
 	if (!solid) {
 		init_huff(unpack_data);
 		unpack_data->unp_ptr = 0;
 	} else {
 		unpack_data->unp_ptr = unpack_data->wr_ptr;
 	}
 	--unpack_data->dest_unp_size;
 	
 	if (unpack_data->dest_unp_size >= 0) {
 		get_flag_buf(unpack_data);
 		unpack_data->flags_cnt = 8;
 	}
 	
 	while (unpack_data->dest_unp_size >= 0) {
 		unpack_data->unp_ptr &= MAXWINMASK;
 		
 		if (unpack_data->in_addr > unpack_data->read_top-30 &&
 				!rar_unp_read_buf(fd, unpack_data)) {
 			break;
 		}
 		
 		if (((unpack_data->wr_ptr - unpack_data->unp_ptr) & MAXWINMASK) < 270 &&
 				(unpack_data->wr_ptr != unpack_data->unp_ptr)) {
 			rar_unp_write_buf_old(unpack_data);
 		}
 		if (unpack_data->st_mode) {
 			huff_decode(unpack_data);
 			continue;
 		}
 		
 		if (--unpack_data->flags_cnt < 0) {
 			get_flag_buf(unpack_data);
 			unpack_data->flags_cnt = 7;
 		}
 		
 		if (unpack_data->flag_buf & 0x80) {
 			unpack_data->flag_buf <<= 1;
 			if (unpack_data->nlzb > unpack_data->nhfb) {
 				long_lz(unpack_data);
 			} else {
 				huff_decode(unpack_data);
 			}
 		} else {
 			unpack_data->flag_buf <<= 1;
 			if (--unpack_data->flags_cnt < 0) {
 				get_flag_buf(unpack_data);
 				unpack_data->flags_cnt = 7;
 			}
 			if (unpack_data->flag_buf & 0x80) {
 				unpack_data->flag_buf <<= 1;
 				if (unpack_data->nlzb > unpack_data->nhfb) {
 					huff_decode(unpack_data);
 				} else {
 					long_lz(unpack_data);
 				}
 			} else {
 				unpack_data->flag_buf <<= 1;
 				short_lz(unpack_data);
 			}
 		}
 	}
 	rar_unp_write_buf_old(unpack_data);
 	return TRUE;
 }