1 /* Ppmd7Enc.c -- PPMdH Encoder
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 "Precomp.h"
6
7 #include "Ppmd7.h"
8
9 #define kTopValue (1 << 24)
10
Ppmd7z_RangeEnc_Init(CPpmd7z_RangeEnc * p)11 void Ppmd7z_RangeEnc_Init(CPpmd7z_RangeEnc *p)
12 {
13 p->Low = 0;
14 p->Range = 0xFFFFFFFF;
15 p->Cache = 0;
16 p->CacheSize = 1;
17 }
18
RangeEnc_ShiftLow(CPpmd7z_RangeEnc * p)19 static void RangeEnc_ShiftLow(CPpmd7z_RangeEnc *p)
20 {
21 if ((UInt32)p->Low < (UInt32)0xFF000000 || (unsigned)(p->Low >> 32) != 0)
22 {
23 Byte temp = p->Cache;
24 do
25 {
26 p->Stream->Write(p->Stream, (Byte)(temp + (Byte)(p->Low >> 32)));
27 temp = 0xFF;
28 }
29 while(--p->CacheSize != 0);
30 p->Cache = (Byte)((UInt32)p->Low >> 24);
31 }
32 p->CacheSize++;
33 p->Low = (UInt32)p->Low << 8;
34 }
35
RangeEnc_Encode(CPpmd7z_RangeEnc * p,UInt32 start,UInt32 size,UInt32 total)36 static void RangeEnc_Encode(CPpmd7z_RangeEnc *p, UInt32 start, UInt32 size, UInt32 total)
37 {
38 p->Low += start * (p->Range /= total);
39 p->Range *= size;
40 while (p->Range < kTopValue)
41 {
42 p->Range <<= 8;
43 RangeEnc_ShiftLow(p);
44 }
45 }
46
RangeEnc_EncodeBit_0(CPpmd7z_RangeEnc * p,UInt32 size0)47 static void RangeEnc_EncodeBit_0(CPpmd7z_RangeEnc *p, UInt32 size0)
48 {
49 p->Range = (p->Range >> 14) * size0;
50 while (p->Range < kTopValue)
51 {
52 p->Range <<= 8;
53 RangeEnc_ShiftLow(p);
54 }
55 }
56
RangeEnc_EncodeBit_1(CPpmd7z_RangeEnc * p,UInt32 size0)57 static void RangeEnc_EncodeBit_1(CPpmd7z_RangeEnc *p, UInt32 size0)
58 {
59 UInt32 newBound = (p->Range >> 14) * size0;
60 p->Low += newBound;
61 p->Range -= newBound;
62 while (p->Range < kTopValue)
63 {
64 p->Range <<= 8;
65 RangeEnc_ShiftLow(p);
66 }
67 }
68
Ppmd7z_RangeEnc_FlushData(CPpmd7z_RangeEnc * p)69 void Ppmd7z_RangeEnc_FlushData(CPpmd7z_RangeEnc *p)
70 {
71 unsigned i;
72 for (i = 0; i < 5; i++)
73 RangeEnc_ShiftLow(p);
74 }
75
76
77 #define MASK(sym) ((signed char *)charMask)[sym]
78
Ppmd7_EncodeSymbol(CPpmd7 * p,CPpmd7z_RangeEnc * rc,int symbol)79 void Ppmd7_EncodeSymbol(CPpmd7 *p, CPpmd7z_RangeEnc *rc, int symbol)
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 UInt32 sum;
86 unsigned i;
87 if (s->Symbol == symbol)
88 {
89 RangeEnc_Encode(rc, 0, s->Freq, p->MinContext->SummFreq);
90 p->FoundState = s;
91 Ppmd7_Update1_0(p);
92 return;
93 }
94 p->PrevSuccess = 0;
95 sum = s->Freq;
96 i = p->MinContext->NumStats - 1;
97 do
98 {
99 if ((++s)->Symbol == symbol)
100 {
101 RangeEnc_Encode(rc, sum, s->Freq, p->MinContext->SummFreq);
102 p->FoundState = s;
103 Ppmd7_Update1(p);
104 return;
105 }
106 sum += s->Freq;
107 }
108 while (--i);
109
110 p->HiBitsFlag = p->HB2Flag[p->FoundState->Symbol];
111 PPMD_SetAllBitsIn256Bytes(charMask);
112 MASK(s->Symbol) = 0;
113 i = p->MinContext->NumStats - 1;
114 do { MASK((--s)->Symbol) = 0; } while (--i);
115 RangeEnc_Encode(rc, sum, p->MinContext->SummFreq - sum, p->MinContext->SummFreq);
116 }
117 else
118 {
119 UInt16 *prob = Ppmd7_GetBinSumm(p);
120 CPpmd_State *s = Ppmd7Context_OneState(p->MinContext);
121 if (s->Symbol == symbol)
122 {
123 RangeEnc_EncodeBit_0(rc, *prob);
124 *prob = (UInt16)PPMD_UPDATE_PROB_0(*prob);
125 p->FoundState = s;
126 Ppmd7_UpdateBin(p);
127 return;
128 }
129 else
130 {
131 RangeEnc_EncodeBit_1(rc, *prob);
132 *prob = (UInt16)PPMD_UPDATE_PROB_1(*prob);
133 p->InitEsc = PPMD7_kExpEscape[*prob >> 10];
134 PPMD_SetAllBitsIn256Bytes(charMask);
135 MASK(s->Symbol) = 0;
136 p->PrevSuccess = 0;
137 }
138 }
139 for (;;)
140 {
141 UInt32 escFreq;
142 CPpmd_See *see;
143 CPpmd_State *s;
144 UInt32 sum;
145 unsigned i, numMasked = p->MinContext->NumStats;
146 do
147 {
148 p->OrderFall++;
149 if (!p->MinContext->Suffix)
150 return; /* EndMarker (symbol = -1) */
151 p->MinContext = Ppmd7_GetContext(p, p->MinContext->Suffix);
152 }
153 while (p->MinContext->NumStats == numMasked);
154
155 see = Ppmd7_MakeEscFreq(p, numMasked, &escFreq);
156 s = Ppmd7_GetStats(p, p->MinContext);
157 sum = 0;
158 i = p->MinContext->NumStats;
159 do
160 {
161 int cur = s->Symbol;
162 if (cur == symbol)
163 {
164 UInt32 low = sum;
165 CPpmd_State *s1 = s;
166 do
167 {
168 sum += (s->Freq & (int)(MASK(s->Symbol)));
169 s++;
170 }
171 while (--i);
172 RangeEnc_Encode(rc, low, s1->Freq, sum + escFreq);
173 Ppmd_See_Update(see);
174 p->FoundState = s1;
175 Ppmd7_Update2(p);
176 return;
177 }
178 sum += (s->Freq & (int)(MASK(cur)));
179 MASK(cur) = 0;
180 s++;
181 }
182 while (--i);
183
184 RangeEnc_Encode(rc, sum, escFreq, sum + escFreq);
185 see->Summ = (UInt16)(see->Summ + sum + escFreq);
186 }
187 }
188