CoCalc provides the best real-time collaborative environment for Jupyter Notebooks, LaTeX documents, and SageMath, scalable from individual users to large groups and classes!
CoCalc provides the best real-time collaborative environment for Jupyter Notebooks, LaTeX documents, and SageMath, scalable from individual users to large groups and classes!
Path: blob/master/Core/FileSystems/tlzrc.cpp
Views: 1401
1// tlzrc.c: LZRC decodeer2// based on benhur's code, rewrite by tpu34// Copyright (c) 2012- PPSSPP Project.56// This program is free software: you can redistribute it and/or modify7// it under the terms of the GNU General Public License as published by8// the Free Software Foundation, version 2.0 or later versions.910// This program is distributed in the hope that it will be useful,11// but WITHOUT ANY WARRANTY; without even the implied warranty of12// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the13// GNU General Public License 2.0 for more details.1415// A copy of the GPL 2.0 should have been included with the program.16// If not, see http://www.gnu.org/licenses/1718// Official git repository and contact information can be found at19// https://github.com/hrydgard/ppsspp and http://www.ppsspp.org/.2021#include <stdio.h>22#include <stdlib.h>23#include <string.h>2425#include "Common/Common.h"26#include "Common/Log.h"2728/*************************************************************/2930typedef unsigned int u32;31typedef unsigned short u16;32typedef unsigned char u8;3334/*************************************************************/3536typedef struct{3738// input stream39u8 *input;40int in_ptr;41int in_len;4243// output stream44u8 *output;45int out_ptr;46int out_len;4748// range decode49u32 range;50u32 code;51u32 out_code;52u8 lc;5354u8 bm_literal[8][256];55u8 bm_dist_bits[8][39];56u8 bm_dist[18][8];57u8 bm_match[8][8];58u8 bm_len[8][31];59}LZRC_DECODE;6061/*************************************************************/6263static u8 rc_getbyte(LZRC_DECODE *rc)64{65if(rc->in_ptr == rc->in_len){66_dbg_assert_msg_(false, "LZRC: End of input!");67}6869return rc->input[rc->in_ptr++];70}7172static void rc_putbyte(LZRC_DECODE *rc, u8 byte)73{74if(rc->out_ptr == rc->out_len){75_dbg_assert_msg_(false, "LZRC: Output overflow!");76}7778rc->output[rc->out_ptr++] = byte;79}8081static void rc_init(LZRC_DECODE *rc, void *out, int out_len, void *in, int in_len)82{83rc->input = (u8*)in;84rc->in_len = in_len;85rc->in_ptr = 0;8687rc->output = (u8*)out;88rc->out_len = out_len;89rc->out_ptr = 0;9091rc->range = 0xffffffff;92rc->lc = rc_getbyte(rc);93rc->code = (rc_getbyte(rc)<<24) |94(rc_getbyte(rc)<<16) |95(rc_getbyte(rc)<< 8) |96(rc_getbyte(rc)<< 0) ;97rc->out_code = 0xffffffff;9899memset(rc->bm_literal, 0x80, 2048);100memset(rc->bm_dist_bits, 0x80, 312);101memset(rc->bm_dist, 0x80, 144);102memset(rc->bm_match, 0x80, 64);103memset(rc->bm_len, 0x80, 248);104105}106107108109/*************************************************************/110111/* range decode */112113static void normalize(LZRC_DECODE *rc)114{115if(rc->range<0x01000000){116rc->range <<= 8;117rc->code = (rc->code<<8)+rc->input[rc->in_ptr];118rc->in_ptr++;119}120}121122/* Decode a bit */123static int rc_bit(LZRC_DECODE *rc, u8 *prob)124{125u32 bound;126127normalize(rc);128129bound = (rc->range>>8)*(*prob);130*prob -= *prob>>3;131132if(rc->code < bound){133rc->range = bound;134*prob += 31;135return 1;136}else{137rc->code -= bound;138rc->range -= bound;139return 0;140}141}142143/* Decode a bittree starting from MSB */144static int rc_bittree(LZRC_DECODE *rc, u8 *probs, int limit)145{146int number = 1;147148do{149number = (number<<1)+rc_bit(rc, probs+number);150}while(number<limit);151152return number;153}154155156/*157* decode a number158*159* a number are divide into three part:160* MSB 2bits161* direct bits (don't use probability modle)162* LSB 3bits163*/164static int rc_number(LZRC_DECODE *rc, u8 *prob, int n)165{166int i, number = 1;167168if(n>3){169number = (number<<1)+rc_bit(rc, prob+3);170if(n>4){171number = (number<<1)+rc_bit(rc, prob+3);172if(n>5){173// direct bits174normalize(rc);175176for(i=0; i<n-5; i++){177rc->range >>= 1;178number <<= 1;179if (rc->code < rc->range){180number += 1;181}else{182rc->code -= rc->range;183}184}185}186}187}188189if(n>0){190number = (number<<1)+rc_bit(rc, prob);191if(n>1){192number = (number<<1)+rc_bit(rc, prob+1);193if(n>2){194number = (number<<1)+rc_bit(rc, prob+2);195}196}197}198199return number;200}201202203int lzrc_decompress(void *out, int out_len, void *in, int in_len)204{205LZRC_DECODE rc;206int match_step, rc_state, len_state, dist_state;207int i, bit, byte, last_byte;208int match_len, len_bits;209int match_dist, dist_bits, limit;210u8 *match_src;211int round = -1;212213rc_init(&rc, out, out_len, in, in_len);214215if(rc.lc&0x80){216/* plain text */217memcpy(rc.output, rc.input+5, rc.code);218return rc.code;219}220221rc_state = 0;222last_byte = 0;223224225while (1) {226round += 1;227match_step = 0;228229bit = rc_bit(&rc, &rc.bm_match[rc_state][match_step]);230if (bit==0) {231/* 0 -> raw char */232if(rc_state>0)233rc_state -= 1;234235byte = rc_bittree(&rc, &rc.bm_literal[((last_byte>>rc.lc)&0x07)][0], 0x100);236byte -= 0x100;237238rc_putbyte(&rc, byte);239} else {240/* 1 -> a match */241242/* find bits of match length */243len_bits = 0;244for(i=0; i<7; i++){245match_step += 1;246bit = rc_bit(&rc, &rc.bm_match[rc_state][match_step]);247if(bit==0)248break;249len_bits += 1;250}251252/* find match length */253if(len_bits==0){254match_len = 1;255}else{256len_state = ((len_bits-1)<<2)+((rc.out_ptr<<(len_bits-1))&0x03);257match_len = rc_number(&rc, &rc.bm_len[rc_state][len_state], len_bits);258if (match_len == 0xFF){259//end of stream260return rc.out_ptr;261}262}263264/* find number of bits of match distance */265dist_state = 0;266limit = 8;267if(match_len>2){268dist_state += 7;269limit = 44;270}271dist_bits = rc_bittree(&rc, &rc.bm_dist_bits[len_bits][dist_state], limit);272dist_bits -= limit;273274/* find match distance */275if(dist_bits>0){276match_dist = rc_number(&rc, &rc.bm_dist[dist_bits][0], dist_bits);277} else {278match_dist = 1;279}280281/* copy match bytes */282if(match_dist>rc.out_ptr || match_dist<0){283printf("match_dist out of range! %08x\n", match_dist);284return -1;285}286match_src = rc.output+rc.out_ptr-match_dist;287for(i=0; i<match_len+1; i++){288rc_putbyte(&rc, *match_src++);289}290rc_state = 6+((rc.out_ptr+1)&1);291}292last_byte = rc.output[rc.out_ptr-1];293}294}295296297