1 /* Ppmd7Dec.c -- PPMdH Decoder 2 2010-03-12 : Igor Pavlov : Public domain 3 This code is based on PPMd var.H (2001): Dmitry Shkarin : Public domain */ 4 5 #include "Ppmd7.h" 6 7 #define kTopValue (1 << 24) 8 9 Bool Ppmd7z_RangeDec_Init(CPpmd7z_RangeDec *p) 10 { 11 unsigned i; 12 p->Code = 0; 13 p->Range = 0xFFFFFFFF; 14 if (p->Stream->Read((void *)p->Stream) != 0) 15 return False; 16 for (i = 0; i < 4; i++) 17 p->Code = (p->Code << 8) | p->Stream->Read((void *)p->Stream); 18 return (p->Code < 0xFFFFFFFF); 19 } 20 21 static UInt32 Range_GetThreshold(void *pp, UInt32 total) 22 { 23 CPpmd7z_RangeDec *p = (CPpmd7z_RangeDec *)pp; 24 return (p->Code) / (p->Range /= total); 25 } 26 27 static void Range_Normalize(CPpmd7z_RangeDec *p) 28 { 29 if (p->Range < kTopValue) 30 { 31 p->Code = (p->Code << 8) | p->Stream->Read((void *)p->Stream); 32 p->Range <<= 8; 33 if (p->Range < kTopValue) 34 { 35 p->Code = (p->Code << 8) | p->Stream->Read((void *)p->Stream); 36 p->Range <<= 8; 37 } 38 } 39 } 40 41 static void Range_Decode(void *pp, UInt32 start, UInt32 size) 42 { 43 CPpmd7z_RangeDec *p = (CPpmd7z_RangeDec *)pp; 44 p->Code -= start * p->Range; 45 p->Range *= size; 46 Range_Normalize(p); 47 } 48 49 static UInt32 Range_DecodeBit(void *pp, UInt32 size0) 50 { 51 CPpmd7z_RangeDec *p = (CPpmd7z_RangeDec *)pp; 52 UInt32 newBound = (p->Range >> 14) * size0; 53 UInt32 symbol; 54 if (p->Code < newBound) 55 { 56 symbol = 0; 57 p->Range = newBound; 58 } 59 else 60 { 61 symbol = 1; 62 p->Code -= newBound; 63 p->Range -= newBound; 64 } 65 Range_Normalize(p); 66 return symbol; 67 } 68 69 void Ppmd7z_RangeDec_CreateVTable(CPpmd7z_RangeDec *p) 70 { 71 p->p.GetThreshold = Range_GetThreshold; 72 p->p.Decode = Range_Decode; 73 p->p.DecodeBit = Range_DecodeBit; 74 } 75 76 77 #define MASK(sym) ((signed char *)charMask)[sym] 78 79 int Ppmd7_DecodeSymbol(CPpmd7 *p, IPpmd7_RangeDec *rc) 80 { 81 size_t charMask[256 / sizeof(size_t)]; 82 if (p->MinContext->NumStats != 1) 83 { 84 CPpmd_State *s = Ppmd7_GetStats(p, p->MinContext); 85 unsigned i; 86 UInt32 count, hiCnt; 87 if ((count = rc->GetThreshold(rc, p->MinContext->SummFreq)) < (hiCnt = s->Freq)) 88 { 89 Byte symbol; 90 rc->Decode(rc, 0, s->Freq); 91 p->FoundState = s; 92 symbol = s->Symbol; 93 Ppmd7_Update1_0(p); 94 return symbol; 95 } 96 p->PrevSuccess = 0; 97 i = p->MinContext->NumStats - 1; 98 do 99 { 100 if ((hiCnt += (++s)->Freq) > count) 101 { 102 Byte symbol; 103 rc->Decode(rc, hiCnt - s->Freq, s->Freq); 104 p->FoundState = s; 105 symbol = s->Symbol; 106 Ppmd7_Update1(p); 107 return symbol; 108 } 109 } 110 while (--i); 111 if (count >= p->MinContext->SummFreq) 112 return -2; 113 p->HiBitsFlag = p->HB2Flag[p->FoundState->Symbol]; 114 rc->Decode(rc, hiCnt, p->MinContext->SummFreq - hiCnt); 115 PPMD_SetAllBitsIn256Bytes(charMask); 116 MASK(s->Symbol) = 0; 117 i = p->MinContext->NumStats - 1; 118 do { MASK((--s)->Symbol) = 0; } while (--i); 119 } 120 else 121 { 122 UInt16 *prob = Ppmd7_GetBinSumm(p); 123 if (rc->DecodeBit(rc, *prob) == 0) 124 { 125 Byte symbol; 126 *prob = (UInt16)PPMD_UPDATE_PROB_0(*prob); 127 symbol = (p->FoundState = Ppmd7Context_OneState(p->MinContext))->Symbol; 128 Ppmd7_UpdateBin(p); 129 return symbol; 130 } 131 *prob = (UInt16)PPMD_UPDATE_PROB_1(*prob); 132 p->InitEsc = PPMD7_kExpEscape[*prob >> 10]; 133 PPMD_SetAllBitsIn256Bytes(charMask); 134 MASK(Ppmd7Context_OneState(p->MinContext)->Symbol) = 0; 135 p->PrevSuccess = 0; 136 } 137 for (;;) 138 { 139 CPpmd_State *ps[256], *s; 140 UInt32 freqSum, count, hiCnt; 141 CPpmd_See *see; 142 unsigned i, num, numMasked = p->MinContext->NumStats; 143 do 144 { 145 p->OrderFall++; 146 if (!p->MinContext->Suffix) 147 return -1; 148 p->MinContext = Ppmd7_GetContext(p, p->MinContext->Suffix); 149 } 150 while (p->MinContext->NumStats == numMasked); 151 hiCnt = 0; 152 s = Ppmd7_GetStats(p, p->MinContext); 153 i = 0; 154 num = p->MinContext->NumStats - numMasked; 155 do 156 { 157 int k = (int)(MASK(s->Symbol)); 158 hiCnt += (s->Freq & k); 159 ps[i] = s++; 160 i -= k; 161 } 162 while (i != num); 163 164 see = Ppmd7_MakeEscFreq(p, numMasked, &freqSum); 165 freqSum += hiCnt; 166 count = rc->GetThreshold(rc, freqSum); 167 168 if (count < hiCnt) 169 { 170 Byte symbol; 171 CPpmd_State **pps = ps; 172 for (hiCnt = 0; (hiCnt += (*pps)->Freq) <= count; pps++); 173 s = *pps; 174 rc->Decode(rc, hiCnt - s->Freq, s->Freq); 175 Ppmd_See_Update(see); 176 p->FoundState = s; 177 symbol = s->Symbol; 178 Ppmd7_Update2(p); 179 return symbol; 180 } 181 if (count >= freqSum) 182 return -2; 183 rc->Decode(rc, hiCnt, freqSum - hiCnt); 184 see->Summ = (UInt16)(see->Summ + freqSum); 185 do { MASK(ps[--i]->Symbol) = 0; } while (i != 0); 186 } 187 } 188
