Import libarchive-3.0.4.
[dragonfly.git] / contrib / libarchive / libarchive / archive_ppmd7.c
1 /* Ppmd7.c -- PPMdH codec
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 "archive_platform.h"
6
7 #include <memory.h>
8
9 #include "archive_ppmd7_private.h"
10
11 #ifdef PPMD_32BIT
12   #define Ppmd7_GetPtr(p, ptr) (ptr)
13   #define Ppmd7_GetContext(p, ptr) (ptr)
14   #define Ppmd7_GetStats(p, ctx) ((ctx)->Stats)
15 #else
16   #define Ppmd7_GetPtr(p, offs) ((void *)((p)->Base + (offs)))
17   #define Ppmd7_GetContext(p, offs) ((CPpmd7_Context *)Ppmd7_GetPtr((p), (offs)))
18   #define Ppmd7_GetStats(p, ctx) ((CPpmd_State *)Ppmd7_GetPtr((p), ((ctx)->Stats)))
19 #endif
20
21 #define Ppmd7_GetBinSumm(p) \
22     &p->BinSumm[Ppmd7Context_OneState(p->MinContext)->Freq - 1][p->PrevSuccess + \
23     p->NS2BSIndx[Ppmd7_GetContext(p, p->MinContext->Suffix)->NumStats - 1] + \
24     (p->HiBitsFlag = p->HB2Flag[p->FoundState->Symbol]) + \
25     2 * p->HB2Flag[Ppmd7Context_OneState(p->MinContext)->Symbol] + \
26     ((p->RunLength >> 26) & 0x20)]
27
28 #define kTopValue (1 << 24)
29 #define MAX_FREQ 124
30 #define UNIT_SIZE 12
31
32 #define U2B(nu) ((UInt32)(nu) * UNIT_SIZE)
33 #define U2I(nu) (p->Units2Indx[(nu) - 1])
34 #define I2U(indx) (p->Indx2Units[indx])
35
36 #ifdef PPMD_32BIT
37   #define REF(ptr) (ptr)
38 #else
39   #define REF(ptr) ((UInt32)((Byte *)(ptr) - (p)->Base))
40 #endif
41
42 #define STATS_REF(ptr) ((CPpmd_State_Ref)REF(ptr))
43
44 #define CTX(ref) ((CPpmd7_Context *)Ppmd7_GetContext(p, ref))
45 #define STATS(ctx) Ppmd7_GetStats(p, ctx)
46 #define ONE_STATE(ctx) Ppmd7Context_OneState(ctx)
47 #define SUFFIX(ctx) CTX((ctx)->Suffix)
48
49 static const UInt16 kInitBinEsc[] = { 0x3CDD, 0x1F3F, 0x59BF, 0x48F3, 0x64A1, 0x5ABC, 0x6632, 0x6051};
50 static const Byte PPMD7_kExpEscape[16] = { 25, 14, 9, 7, 5, 5, 4, 4, 4, 3, 3, 3, 2, 2, 2, 2 };
51
52 typedef CPpmd7_Context * CTX_PTR;
53
54 struct CPpmd7_Node_;
55
56 typedef
57   #ifdef PPMD_32BIT
58     struct CPpmd7_Node_ *
59   #else
60     UInt32
61   #endif
62   CPpmd7_Node_Ref;
63
64 typedef struct CPpmd7_Node_
65 {
66   UInt16 Stamp; /* must be at offset 0 as CPpmd7_Context::NumStats. Stamp=0 means free */
67   UInt16 NU;
68   CPpmd7_Node_Ref Next; /* must be at offset >= 4 */
69   CPpmd7_Node_Ref Prev;
70 } CPpmd7_Node;
71
72 #ifdef PPMD_32BIT
73   #define NODE(ptr) (ptr)
74 #else
75   #define NODE(offs) ((CPpmd7_Node *)(p->Base + (offs)))
76 #endif
77
78 static void Ppmd7_Update1(CPpmd7 *p);
79 static void Ppmd7_Update1_0(CPpmd7 *p);
80 static void Ppmd7_Update2(CPpmd7 *p);
81 static void Ppmd7_UpdateBin(CPpmd7 *p);
82 static CPpmd_See *Ppmd7_MakeEscFreq(CPpmd7 *p, unsigned numMasked,
83                                     UInt32 *scale);
84
85 /* ----------- Base ----------- */
86
87 static void Ppmd7_Construct(CPpmd7 *p)
88 {
89   unsigned i, k, m;
90
91   p->Base = 0;
92
93   for (i = 0, k = 0; i < PPMD_NUM_INDEXES; i++)
94   {
95     unsigned step = (i >= 12 ? 4 : (i >> 2) + 1);
96     do { p->Units2Indx[k++] = (Byte)i; } while(--step);
97     p->Indx2Units[i] = (Byte)k;
98   }
99
100   p->NS2BSIndx[0] = (0 << 1);
101   p->NS2BSIndx[1] = (1 << 1);
102   memset(p->NS2BSIndx + 2, (2 << 1), 9);
103   memset(p->NS2BSIndx + 11, (3 << 1), 256 - 11);
104
105   for (i = 0; i < 3; i++)
106     p->NS2Indx[i] = (Byte)i;
107   for (m = i, k = 1; i < 256; i++)
108   {
109     p->NS2Indx[i] = (Byte)m;
110     if (--k == 0)
111       k = (++m) - 2;
112   }
113
114   memset(p->HB2Flag, 0, 0x40);
115   memset(p->HB2Flag + 0x40, 8, 0x100 - 0x40);
116 }
117
118 static void Ppmd7_Free(CPpmd7 *p, ISzAlloc *alloc)
119 {
120   alloc->Free(alloc, p->Base);
121   p->Size = 0;
122   p->Base = 0;
123 }
124
125 static Bool Ppmd7_Alloc(CPpmd7 *p, UInt32 size, ISzAlloc *alloc)
126 {
127   if (p->Base == 0 || p->Size != size)
128   {
129     Ppmd7_Free(p, alloc);
130     p->AlignOffset =
131       #ifdef PPMD_32BIT
132         (4 - size) & 3;
133       #else
134         4 - (size & 3);
135       #endif
136     if ((p->Base = (Byte *)alloc->Alloc(alloc, p->AlignOffset + size
137         #ifndef PPMD_32BIT
138         + UNIT_SIZE
139         #endif
140         )) == 0)
141       return False;
142     p->Size = size;
143   }
144   return True;
145 }
146
147 static void InsertNode(CPpmd7 *p, void *node, unsigned indx)
148 {
149   *((CPpmd_Void_Ref *)node) = p->FreeList[indx];
150   p->FreeList[indx] = REF(node);
151 }
152
153 static void *RemoveNode(CPpmd7 *p, unsigned indx)
154 {
155   CPpmd_Void_Ref *node = (CPpmd_Void_Ref *)Ppmd7_GetPtr(p, p->FreeList[indx]);
156   p->FreeList[indx] = *node;
157   return node;
158 }
159
160 static void SplitBlock(CPpmd7 *p, void *ptr, unsigned oldIndx, unsigned newIndx)
161 {
162   unsigned i, nu = I2U(oldIndx) - I2U(newIndx);
163   ptr = (Byte *)ptr + U2B(I2U(newIndx));
164   if (I2U(i = U2I(nu)) != nu)
165   {
166     unsigned k = I2U(--i);
167     InsertNode(p, ((Byte *)ptr) + U2B(k), nu - k - 1);
168   }
169   InsertNode(p, ptr, i);
170 }
171
172 static void GlueFreeBlocks(CPpmd7 *p)
173 {
174   #ifdef PPMD_32BIT
175   CPpmd7_Node headItem;
176   CPpmd7_Node_Ref head = &headItem;
177   #else
178   CPpmd7_Node_Ref head = p->AlignOffset + p->Size;
179   #endif
180   
181   CPpmd7_Node_Ref n = head;
182   unsigned i;
183
184   p->GlueCount = 255;
185
186   /* create doubly-linked list of free blocks */
187   for (i = 0; i < PPMD_NUM_INDEXES; i++)
188   {
189     UInt16 nu = I2U(i);
190     CPpmd7_Node_Ref next = (CPpmd7_Node_Ref)p->FreeList[i];
191     p->FreeList[i] = 0;
192     while (next != 0)
193     {
194       CPpmd7_Node *node = NODE(next);
195       node->Next = n;
196       n = NODE(n)->Prev = next;
197       next = *(const CPpmd7_Node_Ref *)node;
198       node->Stamp = 0;
199       node->NU = (UInt16)nu;
200     }
201   }
202   NODE(head)->Stamp = 1;
203   NODE(head)->Next = n;
204   NODE(n)->Prev = head;
205   if (p->LoUnit != p->HiUnit)
206     ((CPpmd7_Node *)p->LoUnit)->Stamp = 1;
207   
208   /* Glue free blocks */
209   while (n != head)
210   {
211     CPpmd7_Node *node = NODE(n);
212     UInt32 nu = (UInt32)node->NU;
213     for (;;)
214     {
215       CPpmd7_Node *node2 = NODE(n) + nu;
216       nu += node2->NU;
217       if (node2->Stamp != 0 || nu >= 0x10000)
218         break;
219       NODE(node2->Prev)->Next = node2->Next;
220       NODE(node2->Next)->Prev = node2->Prev;
221       node->NU = (UInt16)nu;
222     }
223     n = node->Next;
224   }
225   
226   /* Fill lists of free blocks */
227   for (n = NODE(head)->Next; n != head;)
228   {
229     CPpmd7_Node *node = NODE(n);
230     unsigned nu;
231     CPpmd7_Node_Ref next = node->Next;
232     for (nu = node->NU; nu > 128; nu -= 128, node += 128)
233       InsertNode(p, node, PPMD_NUM_INDEXES - 1);
234     if (I2U(i = U2I(nu)) != nu)
235     {
236       unsigned k = I2U(--i);
237       InsertNode(p, node + k, nu - k - 1);
238     }
239     InsertNode(p, node, i);
240     n = next;
241   }
242 }
243
244 static void *AllocUnitsRare(CPpmd7 *p, unsigned indx)
245 {
246   unsigned i;
247   void *retVal;
248   if (p->GlueCount == 0)
249   {
250     GlueFreeBlocks(p);
251     if (p->FreeList[indx] != 0)
252       return RemoveNode(p, indx);
253   }
254   i = indx;
255   do
256   {
257     if (++i == PPMD_NUM_INDEXES)
258     {
259       UInt32 numBytes = U2B(I2U(indx));
260       p->GlueCount--;
261       return ((UInt32)(p->UnitsStart - p->Text) > numBytes) ? (p->UnitsStart -= numBytes) : (NULL);
262     }
263   }
264   while (p->FreeList[i] == 0);
265   retVal = RemoveNode(p, i);
266   SplitBlock(p, retVal, i, indx);
267   return retVal;
268 }
269
270 static void *AllocUnits(CPpmd7 *p, unsigned indx)
271 {
272   UInt32 numBytes;
273   if (p->FreeList[indx] != 0)
274     return RemoveNode(p, indx);
275   numBytes = U2B(I2U(indx));
276   if (numBytes <= (UInt32)(p->HiUnit - p->LoUnit))
277   {
278     void *retVal = p->LoUnit;
279     p->LoUnit += numBytes;
280     return retVal;
281   }
282   return AllocUnitsRare(p, indx);
283 }
284
285 #define MyMem12Cpy(dest, src, num) \
286   { UInt32 *d = (UInt32 *)dest; const UInt32 *s = (const UInt32 *)src; UInt32 n = num; \
287     do { d[0] = s[0]; d[1] = s[1]; d[2] = s[2]; s += 3; d += 3; } while(--n); }
288
289 static void *ShrinkUnits(CPpmd7 *p, void *oldPtr, unsigned oldNU, unsigned newNU)
290 {
291   unsigned i0 = U2I(oldNU);
292   unsigned i1 = U2I(newNU);
293   if (i0 == i1)
294     return oldPtr;
295   if (p->FreeList[i1] != 0)
296   {
297     void *ptr = RemoveNode(p, i1);
298     MyMem12Cpy(ptr, oldPtr, newNU);
299     InsertNode(p, oldPtr, i0);
300     return ptr;
301   }
302   SplitBlock(p, oldPtr, i0, i1);
303   return oldPtr;
304 }
305
306 #define SUCCESSOR(p) ((CPpmd_Void_Ref)((p)->SuccessorLow | ((UInt32)(p)->SuccessorHigh << 16)))
307
308 static void SetSuccessor(CPpmd_State *p, CPpmd_Void_Ref v)
309 {
310   (p)->SuccessorLow = (UInt16)((UInt32)(v) & 0xFFFF);
311   (p)->SuccessorHigh = (UInt16)(((UInt32)(v) >> 16) & 0xFFFF);
312 }
313
314 static void RestartModel(CPpmd7 *p)
315 {
316   unsigned i, k, m;
317
318   memset(p->FreeList, 0, sizeof(p->FreeList));
319   p->Text = p->Base + p->AlignOffset;
320   p->HiUnit = p->Text + p->Size;
321   p->LoUnit = p->UnitsStart = p->HiUnit - p->Size / 8 / UNIT_SIZE * 7 * UNIT_SIZE;
322   p->GlueCount = 0;
323
324   p->OrderFall = p->MaxOrder;
325   p->RunLength = p->InitRL = -(Int32)((p->MaxOrder < 12) ? p->MaxOrder : 12) - 1;
326   p->PrevSuccess = 0;
327
328   p->MinContext = p->MaxContext = (CTX_PTR)(p->HiUnit -= UNIT_SIZE); /* AllocContext(p); */
329   p->MinContext->Suffix = 0;
330   p->MinContext->NumStats = 256;
331   p->MinContext->SummFreq = 256 + 1;
332   p->FoundState = (CPpmd_State *)p->LoUnit; /* AllocUnits(p, PPMD_NUM_INDEXES - 1); */
333   p->LoUnit += U2B(256 / 2);
334   p->MinContext->Stats = REF(p->FoundState);
335   for (i = 0; i < 256; i++)
336   {
337     CPpmd_State *s = &p->FoundState[i];
338     s->Symbol = (Byte)i;
339     s->Freq = 1;
340     SetSuccessor(s, 0);
341   }
342
343   for (i = 0; i < 128; i++)
344     for (k = 0; k < 8; k++)
345     {
346       UInt16 *dest = p->BinSumm[i] + k;
347       UInt16 val = (UInt16)(PPMD_BIN_SCALE - kInitBinEsc[k] / (i + 2));
348       for (m = 0; m < 64; m += 8)
349         dest[m] = val;
350     }
351   
352   for (i = 0; i < 25; i++)
353     for (k = 0; k < 16; k++)
354     {
355       CPpmd_See *s = &p->See[i][k];
356       s->Summ = (UInt16)((5 * i + 10) << (s->Shift = PPMD_PERIOD_BITS - 4));
357       s->Count = 4;
358     }
359 }
360
361 static void Ppmd7_Init(CPpmd7 *p, unsigned maxOrder)
362 {
363   p->MaxOrder = maxOrder;
364   RestartModel(p);
365   p->DummySee.Shift = PPMD_PERIOD_BITS;
366   p->DummySee.Summ = 0; /* unused */
367   p->DummySee.Count = 64; /* unused */
368 }
369
370 static CTX_PTR CreateSuccessors(CPpmd7 *p, Bool skip)
371 {
372   CPpmd_State upState;
373   CTX_PTR c = p->MinContext;
374   CPpmd_Byte_Ref upBranch = (CPpmd_Byte_Ref)SUCCESSOR(p->FoundState);
375   CPpmd_State *ps[PPMD7_MAX_ORDER];
376   unsigned numPs = 0;
377   
378   if (!skip)
379     ps[numPs++] = p->FoundState;
380   
381   while (c->Suffix)
382   {
383     CPpmd_Void_Ref successor;
384     CPpmd_State *s;
385     c = SUFFIX(c);
386     if (c->NumStats != 1)
387     {
388       for (s = STATS(c); s->Symbol != p->FoundState->Symbol; s++);
389     }
390     else
391       s = ONE_STATE(c);
392     successor = SUCCESSOR(s);
393     if (successor != upBranch)
394     {
395       c = CTX(successor);
396       if (numPs == 0)
397         return c;
398       break;
399     }
400     ps[numPs++] = s;
401   }
402   
403   upState.Symbol = *(const Byte *)Ppmd7_GetPtr(p, upBranch);
404   SetSuccessor(&upState, upBranch + 1);
405   
406   if (c->NumStats == 1)
407     upState.Freq = ONE_STATE(c)->Freq;
408   else
409   {
410     UInt32 cf, s0;
411     CPpmd_State *s;
412     for (s = STATS(c); s->Symbol != upState.Symbol; s++);
413     cf = s->Freq - 1;
414     s0 = c->SummFreq - c->NumStats - cf;
415     upState.Freq = (Byte)(1 + ((2 * cf <= s0) ? (5 * cf > s0) : ((2 * cf + 3 * s0 - 1) / (2 * s0))));
416   }
417
418   while (numPs != 0)
419   {
420     /* Create Child */
421     CTX_PTR c1; /* = AllocContext(p); */
422     if (p->HiUnit != p->LoUnit)
423       c1 = (CTX_PTR)(p->HiUnit -= UNIT_SIZE);
424     else if (p->FreeList[0] != 0)
425       c1 = (CTX_PTR)RemoveNode(p, 0);
426     else
427     {
428       c1 = (CTX_PTR)AllocUnitsRare(p, 0);
429       if (!c1)
430         return NULL;
431     }
432     c1->NumStats = 1;
433     *ONE_STATE(c1) = upState;
434     c1->Suffix = REF(c);
435     SetSuccessor(ps[--numPs], REF(c1));
436     c = c1;
437   }
438   
439   return c;
440 }
441
442 static void SwapStates(CPpmd_State *t1, CPpmd_State *t2)
443 {
444   CPpmd_State tmp = *t1;
445   *t1 = *t2;
446   *t2 = tmp;
447 }
448
449 static void UpdateModel(CPpmd7 *p)
450 {
451   CPpmd_Void_Ref successor, fSuccessor = SUCCESSOR(p->FoundState);
452   CTX_PTR c;
453   unsigned s0, ns;
454   
455   if (p->FoundState->Freq < MAX_FREQ / 4 && p->MinContext->Suffix != 0)
456   {
457     c = SUFFIX(p->MinContext);
458     
459     if (c->NumStats == 1)
460     {
461       CPpmd_State *s = ONE_STATE(c);
462       if (s->Freq < 32)
463         s->Freq++;
464     }
465     else
466     {
467       CPpmd_State *s = STATS(c);
468       if (s->Symbol != p->FoundState->Symbol)
469       {
470         do { s++; } while (s->Symbol != p->FoundState->Symbol);
471         if (s[0].Freq >= s[-1].Freq)
472         {
473           SwapStates(&s[0], &s[-1]);
474           s--;
475         }
476       }
477       if (s->Freq < MAX_FREQ - 9)
478       {
479         s->Freq += 2;
480         c->SummFreq += 2;
481       }
482     }
483   }
484
485   if (p->OrderFall == 0)
486   {
487     p->MinContext = p->MaxContext = CreateSuccessors(p, True);
488     if (p->MinContext == 0)
489     {
490       RestartModel(p);
491       return;
492     }
493     SetSuccessor(p->FoundState, REF(p->MinContext));
494     return;
495   }
496   
497   *p->Text++ = p->FoundState->Symbol;
498   successor = REF(p->Text);
499   if (p->Text >= p->UnitsStart)
500   {
501     RestartModel(p);
502     return;
503   }
504   
505   if (fSuccessor)
506   {
507     if (fSuccessor <= successor)
508     {
509       CTX_PTR cs = CreateSuccessors(p, False);
510       if (cs == NULL)
511       {
512         RestartModel(p);
513         return;
514       }
515       fSuccessor = REF(cs);
516     }
517     if (--p->OrderFall == 0)
518     {
519       successor = fSuccessor;
520       p->Text -= (p->MaxContext != p->MinContext);
521     }
522   }
523   else
524   {
525     SetSuccessor(p->FoundState, successor);
526     fSuccessor = REF(p->MinContext);
527   }
528   
529   s0 = p->MinContext->SummFreq - (ns = p->MinContext->NumStats) - (p->FoundState->Freq - 1);
530   
531   for (c = p->MaxContext; c != p->MinContext; c = SUFFIX(c))
532   {
533     unsigned ns1;
534     UInt32 cf, sf;
535     if ((ns1 = c->NumStats) != 1)
536     {
537       if ((ns1 & 1) == 0)
538       {
539         /* Expand for one UNIT */
540         unsigned oldNU = ns1 >> 1;
541         unsigned i = U2I(oldNU);
542         if (i != U2I(oldNU + 1))
543         {
544           void *ptr = AllocUnits(p, i + 1);
545           void *oldPtr;
546           if (!ptr)
547           {
548             RestartModel(p);
549             return;
550           }
551           oldPtr = STATS(c);
552           MyMem12Cpy(ptr, oldPtr, oldNU);
553           InsertNode(p, oldPtr, i);
554           c->Stats = STATS_REF(ptr);
555         }
556       }
557       c->SummFreq = (UInt16)(c->SummFreq + (2 * ns1 < ns) + 2 * ((4 * ns1 <= ns) & (c->SummFreq <= 8 * ns1)));
558     }
559     else
560     {
561       CPpmd_State *s = (CPpmd_State*)AllocUnits(p, 0);
562       if (!s)
563       {
564         RestartModel(p);
565         return;
566       }
567       *s = *ONE_STATE(c);
568       c->Stats = REF(s);
569       if (s->Freq < MAX_FREQ / 4 - 1)
570         s->Freq <<= 1;
571       else
572         s->Freq = MAX_FREQ - 4;
573       c->SummFreq = (UInt16)(s->Freq + p->InitEsc + (ns > 3));
574     }
575     cf = 2 * (UInt32)p->FoundState->Freq * (c->SummFreq + 6);
576     sf = (UInt32)s0 + c->SummFreq;
577     if (cf < 6 * sf)
578     {
579       cf = 1 + (cf > sf) + (cf >= 4 * sf);
580       c->SummFreq += 3;
581     }
582     else
583     {
584       cf = 4 + (cf >= 9 * sf) + (cf >= 12 * sf) + (cf >= 15 * sf);
585       c->SummFreq = (UInt16)(c->SummFreq + cf);
586     }
587     {
588       CPpmd_State *s = STATS(c) + ns1;
589       SetSuccessor(s, successor);
590       s->Symbol = p->FoundState->Symbol;
591       s->Freq = (Byte)cf;
592       c->NumStats = (UInt16)(ns1 + 1);
593     }
594   }
595   p->MaxContext = p->MinContext = CTX(fSuccessor);
596 }
597   
598 static void Rescale(CPpmd7 *p)
599 {
600   unsigned i, adder, sumFreq, escFreq;
601   CPpmd_State *stats = STATS(p->MinContext);
602   CPpmd_State *s = p->FoundState;
603   {
604     CPpmd_State tmp = *s;
605     for (; s != stats; s--)
606       s[0] = s[-1];
607     *s = tmp;
608   }
609   escFreq = p->MinContext->SummFreq - s->Freq;
610   s->Freq += 4;
611   adder = (p->OrderFall != 0);
612   s->Freq = (Byte)((s->Freq + adder) >> 1);
613   sumFreq = s->Freq;
614   
615   i = p->MinContext->NumStats - 1;
616   do
617   {
618     escFreq -= (++s)->Freq;
619     s->Freq = (Byte)((s->Freq + adder) >> 1);
620     sumFreq += s->Freq;
621     if (s[0].Freq > s[-1].Freq)
622     {
623       CPpmd_State *s1 = s;
624       CPpmd_State tmp = *s1;
625       do
626         s1[0] = s1[-1];
627       while (--s1 != stats && tmp.Freq > s1[-1].Freq);
628       *s1 = tmp;
629     }
630   }
631   while (--i);
632   
633   if (s->Freq == 0)
634   {
635     unsigned numStats = p->MinContext->NumStats;
636     unsigned n0, n1;
637     do { i++; } while ((--s)->Freq == 0);
638     escFreq += i;
639     p->MinContext->NumStats = (UInt16)(p->MinContext->NumStats - i);
640     if (p->MinContext->NumStats == 1)
641     {
642       CPpmd_State tmp = *stats;
643       do
644       {
645         tmp.Freq = (Byte)(tmp.Freq - (tmp.Freq >> 1));
646         escFreq >>= 1;
647       }
648       while (escFreq > 1);
649       InsertNode(p, stats, U2I(((numStats + 1) >> 1)));
650       *(p->FoundState = ONE_STATE(p->MinContext)) = tmp;
651       return;
652     }
653     n0 = (numStats + 1) >> 1;
654     n1 = (p->MinContext->NumStats + 1) >> 1;
655     if (n0 != n1)
656       p->MinContext->Stats = STATS_REF(ShrinkUnits(p, stats, n0, n1));
657   }
658   p->MinContext->SummFreq = (UInt16)(sumFreq + escFreq - (escFreq >> 1));
659   p->FoundState = STATS(p->MinContext);
660 }
661
662 static CPpmd_See *Ppmd7_MakeEscFreq(CPpmd7 *p, unsigned numMasked, UInt32 *escFreq)
663 {
664   CPpmd_See *see;
665   unsigned nonMasked = p->MinContext->NumStats - numMasked;
666   if (p->MinContext->NumStats != 256)
667   {
668     see = p->See[p->NS2Indx[nonMasked - 1]] +
669         (nonMasked < (unsigned)SUFFIX(p->MinContext)->NumStats - p->MinContext->NumStats) +
670         2 * (p->MinContext->SummFreq < 11 * p->MinContext->NumStats) +
671         4 * (numMasked > nonMasked) +
672         p->HiBitsFlag;
673     {
674       unsigned r = (see->Summ >> see->Shift);
675       see->Summ = (UInt16)(see->Summ - r);
676       *escFreq = r + (r == 0);
677     }
678   }
679   else
680   {
681     see = &p->DummySee;
682     *escFreq = 1;
683   }
684   return see;
685 }
686
687 static void NextContext(CPpmd7 *p)
688 {
689   CTX_PTR c = CTX(SUCCESSOR(p->FoundState));
690   if (p->OrderFall == 0 && (Byte *)c > p->Text)
691     p->MinContext = p->MaxContext = c;
692   else
693     UpdateModel(p);
694 }
695
696 static void Ppmd7_Update1(CPpmd7 *p)
697 {
698   CPpmd_State *s = p->FoundState;
699   s->Freq += 4;
700   p->MinContext->SummFreq += 4;
701   if (s[0].Freq > s[-1].Freq)
702   {
703     SwapStates(&s[0], &s[-1]);
704     p->FoundState = --s;
705     if (s->Freq > MAX_FREQ)
706       Rescale(p);
707   }
708   NextContext(p);
709 }
710
711 static void Ppmd7_Update1_0(CPpmd7 *p)
712 {
713   p->PrevSuccess = (2 * p->FoundState->Freq > p->MinContext->SummFreq);
714   p->RunLength += p->PrevSuccess;
715   p->MinContext->SummFreq += 4;
716   if ((p->FoundState->Freq += 4) > MAX_FREQ)
717     Rescale(p);
718   NextContext(p);
719 }
720
721 static void Ppmd7_UpdateBin(CPpmd7 *p)
722 {
723   p->FoundState->Freq = (Byte)(p->FoundState->Freq + (p->FoundState->Freq < 128 ? 1: 0));
724   p->PrevSuccess = 1;
725   p->RunLength++;
726   NextContext(p);
727 }
728
729 static void Ppmd7_Update2(CPpmd7 *p)
730 {
731   p->MinContext->SummFreq += 4;
732   if ((p->FoundState->Freq += 4) > MAX_FREQ)
733     Rescale(p);
734   p->RunLength = p->InitRL;
735   UpdateModel(p);
736 }
737
738 /* ---------- Decode ---------- */
739
740 static Bool Ppmd_RangeDec_Init(CPpmd7z_RangeDec *p)
741 {
742   unsigned i;
743   p->Low = p->Bottom = 0;
744   p->Range = 0xFFFFFFFF;
745   for (i = 0; i < 4; i++)
746     p->Code = (p->Code << 8) | p->Stream->Read((void *)p->Stream);
747   return (p->Code < 0xFFFFFFFF);
748 }
749
750 static Bool Ppmd7z_RangeDec_Init(CPpmd7z_RangeDec *p)
751 {
752   if (p->Stream->Read((void *)p->Stream) != 0)
753     return False;
754   return Ppmd_RangeDec_Init(p);
755 }
756
757 static Bool PpmdRAR_RangeDec_Init(CPpmd7z_RangeDec *p)
758 {
759   if (!Ppmd_RangeDec_Init(p))
760     return False;
761   p->Bottom = 0x8000;
762   return True;
763 }
764
765 static UInt32 Range_GetThreshold(void *pp, UInt32 total)
766 {
767   CPpmd7z_RangeDec *p = (CPpmd7z_RangeDec *)pp;
768   return (p->Code - p->Low) / (p->Range /= total);
769 }
770
771 static void Range_Normalize(CPpmd7z_RangeDec *p)
772 {
773   while (1)
774   {
775     if((p->Low ^ (p->Low + p->Range)) >= kTopValue)
776     {
777       if(p->Range >= p->Bottom)
778         break;
779       else
780         p->Range = ((uint32_t)(-(int32_t)p->Low)) & (p->Bottom - 1);
781     }
782     p->Code = (p->Code << 8) | p->Stream->Read((void *)p->Stream);
783     p->Range <<= 8;
784     p->Low <<= 8;
785   }
786 }
787
788 static void Range_Decode_7z(void *pp, UInt32 start, UInt32 size)
789 {
790   CPpmd7z_RangeDec *p = (CPpmd7z_RangeDec *)pp;
791   p->Code -= start * p->Range;
792   p->Range *= size;
793   Range_Normalize(p);
794 }
795
796 static void Range_Decode_RAR(void *pp, UInt32 start, UInt32 size)
797 {
798   CPpmd7z_RangeDec *p = (CPpmd7z_RangeDec *)pp;
799   p->Low += start * p->Range;
800   p->Range *= size;
801   Range_Normalize(p);
802 }
803
804 static UInt32 Range_DecodeBit_7z(void *pp, UInt32 size0)
805 {
806   CPpmd7z_RangeDec *p = (CPpmd7z_RangeDec *)pp;
807   UInt32 newBound = (p->Range >> 14) * size0;
808   UInt32 symbol;
809   if (p->Code < newBound)
810   {
811     symbol = 0;
812     p->Range = newBound;
813   }
814   else
815   {
816     symbol = 1;
817     p->Code -= newBound;
818     p->Range -= newBound;
819   }
820   Range_Normalize(p);
821   return symbol;
822 }
823
824 static UInt32 Range_DecodeBit_RAR(void *pp, UInt32 size0)
825 {
826   CPpmd7z_RangeDec *p = (CPpmd7z_RangeDec *)pp;
827   UInt32 bit, value = p->p.GetThreshold(p, PPMD_BIN_SCALE);
828   if(value < size0)
829   {
830     bit = 0;
831     p->p.Decode(p, 0, size0);
832   }
833   else
834   {
835     bit = 1;
836     p->p.Decode(p, size0, PPMD_BIN_SCALE - size0);
837   }
838   return bit;
839 }
840
841 static void Ppmd7z_RangeDec_CreateVTable(CPpmd7z_RangeDec *p)
842 {
843   p->p.GetThreshold = Range_GetThreshold;
844   p->p.Decode = Range_Decode_7z;
845   p->p.DecodeBit = Range_DecodeBit_7z;
846 }
847
848 static void PpmdRAR_RangeDec_CreateVTable(CPpmd7z_RangeDec *p)
849 {
850   p->p.GetThreshold = Range_GetThreshold;
851   p->p.Decode = Range_Decode_RAR;
852   p->p.DecodeBit = Range_DecodeBit_RAR;
853 }
854
855 #define MASK(sym) ((signed char *)charMask)[sym]
856
857 static int Ppmd7_DecodeSymbol(CPpmd7 *p, IPpmd7_RangeDec *rc)
858 {
859   size_t charMask[256 / sizeof(size_t)];
860   if (p->MinContext->NumStats != 1)
861   {
862     CPpmd_State *s = Ppmd7_GetStats(p, p->MinContext);
863     unsigned i;
864     UInt32 count, hiCnt;
865     if ((count = rc->GetThreshold(rc, p->MinContext->SummFreq)) < (hiCnt = s->Freq))
866     {
867       Byte symbol;
868       rc->Decode(rc, 0, s->Freq);
869       p->FoundState = s;
870       symbol = s->Symbol;
871       Ppmd7_Update1_0(p);
872       return symbol;
873     }
874     p->PrevSuccess = 0;
875     i = p->MinContext->NumStats - 1;
876     do
877     {
878       if ((hiCnt += (++s)->Freq) > count)
879       {
880         Byte symbol;
881         rc->Decode(rc, hiCnt - s->Freq, s->Freq);
882         p->FoundState = s;
883         symbol = s->Symbol;
884         Ppmd7_Update1(p);
885         return symbol;
886       }
887     }
888     while (--i);
889     if (count >= p->MinContext->SummFreq)
890       return -2;
891     p->HiBitsFlag = p->HB2Flag[p->FoundState->Symbol];
892     rc->Decode(rc, hiCnt, p->MinContext->SummFreq - hiCnt);
893     PPMD_SetAllBitsIn256Bytes(charMask);
894     MASK(s->Symbol) = 0;
895     i = p->MinContext->NumStats - 1;
896     do { MASK((--s)->Symbol) = 0; } while (--i);
897   }
898   else
899   {
900     UInt16 *prob = Ppmd7_GetBinSumm(p);
901     if (rc->DecodeBit(rc, *prob) == 0)
902     {
903       Byte symbol;
904       *prob = (UInt16)PPMD_UPDATE_PROB_0(*prob);
905       symbol = (p->FoundState = Ppmd7Context_OneState(p->MinContext))->Symbol;
906       Ppmd7_UpdateBin(p);
907       return symbol;
908     }
909     *prob = (UInt16)PPMD_UPDATE_PROB_1(*prob);
910     p->InitEsc = PPMD7_kExpEscape[*prob >> 10];
911     PPMD_SetAllBitsIn256Bytes(charMask);
912     MASK(Ppmd7Context_OneState(p->MinContext)->Symbol) = 0;
913     p->PrevSuccess = 0;
914   }
915   for (;;)
916   {
917     CPpmd_State *ps[256], *s;
918     UInt32 freqSum, count, hiCnt;
919     CPpmd_See *see;
920     unsigned i, num, numMasked = p->MinContext->NumStats;
921     do
922     {
923       p->OrderFall++;
924       if (!p->MinContext->Suffix)
925         return -1;
926       p->MinContext = Ppmd7_GetContext(p, p->MinContext->Suffix);
927     }
928     while (p->MinContext->NumStats == numMasked);
929     hiCnt = 0;
930     s = Ppmd7_GetStats(p, p->MinContext);
931     i = 0;
932     num = p->MinContext->NumStats - numMasked;
933     do
934     {
935       int k = (int)(MASK(s->Symbol));
936       hiCnt += (s->Freq & k);
937       ps[i] = s++;
938       i -= k;
939     }
940     while (i != num);
941
942     see = Ppmd7_MakeEscFreq(p, numMasked, &freqSum);
943     freqSum += hiCnt;
944     count = rc->GetThreshold(rc, freqSum);
945
946     if (count < hiCnt)
947     {
948       Byte symbol;
949       CPpmd_State **pps = ps;
950       for (hiCnt = 0; (hiCnt += (*pps)->Freq) <= count; pps++);
951       s = *pps;
952       rc->Decode(rc, hiCnt - s->Freq, s->Freq);
953       Ppmd_See_Update(see);
954       p->FoundState = s;
955       symbol = s->Symbol;
956       Ppmd7_Update2(p);
957       return symbol;
958     }
959     if (count >= freqSum)
960       return -2;
961     rc->Decode(rc, hiCnt, freqSum - hiCnt);
962     see->Summ = (UInt16)(see->Summ + freqSum);
963     do { MASK(ps[--i]->Symbol) = 0; } while (i != 0);
964   }
965 }
966
967 /* ---------- Encode ---------- Ppmd7Enc.c */
968
969 #define kTopValue (1 << 24)
970
971 static void Ppmd7z_RangeEnc_Init(CPpmd7z_RangeEnc *p)
972 {
973   p->Low = 0;
974   p->Range = 0xFFFFFFFF;
975   p->Cache = 0;
976   p->CacheSize = 1;
977 }
978
979 static void RangeEnc_ShiftLow(CPpmd7z_RangeEnc *p)
980 {
981   if ((UInt32)p->Low < (UInt32)0xFF000000 || (unsigned)(p->Low >> 32) != 0)
982   {
983     Byte temp = p->Cache;
984     do
985     {
986       p->Stream->Write(p->Stream, (Byte)(temp + (Byte)(p->Low >> 32)));
987       temp = 0xFF;
988     }
989     while(--p->CacheSize != 0);
990     p->Cache = (Byte)((UInt32)p->Low >> 24);
991   }
992   p->CacheSize++;
993   p->Low = (UInt32)p->Low << 8;
994 }
995
996 static void RangeEnc_Encode(CPpmd7z_RangeEnc *p, UInt32 start, UInt32 size, UInt32 total)
997 {
998   p->Low += start * (p->Range /= total);
999   p->Range *= size;
1000   while (p->Range < kTopValue)
1001   {
1002     p->Range <<= 8;
1003     RangeEnc_ShiftLow(p);
1004   }
1005 }
1006
1007 static void RangeEnc_EncodeBit_0(CPpmd7z_RangeEnc *p, UInt32 size0)
1008 {
1009   p->Range = (p->Range >> 14) * size0;
1010   while (p->Range < kTopValue)
1011   {
1012     p->Range <<= 8;
1013     RangeEnc_ShiftLow(p);
1014   }
1015 }
1016
1017 static void RangeEnc_EncodeBit_1(CPpmd7z_RangeEnc *p, UInt32 size0)
1018 {
1019   UInt32 newBound = (p->Range >> 14) * size0;
1020   p->Low += newBound;
1021   p->Range -= newBound;
1022   while (p->Range < kTopValue)
1023   {
1024     p->Range <<= 8;
1025     RangeEnc_ShiftLow(p);
1026   }
1027 }
1028
1029 static void Ppmd7z_RangeEnc_FlushData(CPpmd7z_RangeEnc *p)
1030 {
1031   unsigned i;
1032   for (i = 0; i < 5; i++)
1033     RangeEnc_ShiftLow(p);
1034 }
1035
1036
1037 #define MASK(sym) ((signed char *)charMask)[sym]
1038
1039 static void Ppmd7_EncodeSymbol(CPpmd7 *p, CPpmd7z_RangeEnc *rc, int symbol)
1040 {
1041   size_t charMask[256 / sizeof(size_t)];
1042   if (p->MinContext->NumStats != 1)
1043   {
1044     CPpmd_State *s = Ppmd7_GetStats(p, p->MinContext);
1045     UInt32 sum;
1046     unsigned i;
1047     if (s->Symbol == symbol)
1048     {
1049       RangeEnc_Encode(rc, 0, s->Freq, p->MinContext->SummFreq);
1050       p->FoundState = s;
1051       Ppmd7_Update1_0(p);
1052       return;
1053     }
1054     p->PrevSuccess = 0;
1055     sum = s->Freq;
1056     i = p->MinContext->NumStats - 1;
1057     do
1058     {
1059       if ((++s)->Symbol == symbol)
1060       {
1061         RangeEnc_Encode(rc, sum, s->Freq, p->MinContext->SummFreq);
1062         p->FoundState = s;
1063         Ppmd7_Update1(p);
1064         return;
1065       }
1066       sum += s->Freq;
1067     }
1068     while (--i);
1069     
1070     p->HiBitsFlag = p->HB2Flag[p->FoundState->Symbol];
1071     PPMD_SetAllBitsIn256Bytes(charMask);
1072     MASK(s->Symbol) = 0;
1073     i = p->MinContext->NumStats - 1;
1074     do { MASK((--s)->Symbol) = 0; } while (--i);
1075     RangeEnc_Encode(rc, sum, p->MinContext->SummFreq - sum, p->MinContext->SummFreq);
1076   }
1077   else
1078   {
1079     UInt16 *prob = Ppmd7_GetBinSumm(p);
1080     CPpmd_State *s = Ppmd7Context_OneState(p->MinContext);
1081     if (s->Symbol == symbol)
1082     {
1083       RangeEnc_EncodeBit_0(rc, *prob);
1084       *prob = (UInt16)PPMD_UPDATE_PROB_0(*prob);
1085       p->FoundState = s;
1086       Ppmd7_UpdateBin(p);
1087       return;
1088     }
1089     else
1090     {
1091       RangeEnc_EncodeBit_1(rc, *prob);
1092       *prob = (UInt16)PPMD_UPDATE_PROB_1(*prob);
1093       p->InitEsc = PPMD7_kExpEscape[*prob >> 10];
1094       PPMD_SetAllBitsIn256Bytes(charMask);
1095       MASK(s->Symbol) = 0;
1096       p->PrevSuccess = 0;
1097     }
1098   }
1099   for (;;)
1100   {
1101     UInt32 escFreq;
1102     CPpmd_See *see;
1103     CPpmd_State *s;
1104     UInt32 sum;
1105     unsigned i, numMasked = p->MinContext->NumStats;
1106     do
1107     {
1108       p->OrderFall++;
1109       if (!p->MinContext->Suffix)
1110         return; /* EndMarker (symbol = -1) */
1111       p->MinContext = Ppmd7_GetContext(p, p->MinContext->Suffix);
1112     }
1113     while (p->MinContext->NumStats == numMasked);
1114     
1115     see = Ppmd7_MakeEscFreq(p, numMasked, &escFreq);
1116     s = Ppmd7_GetStats(p, p->MinContext);
1117     sum = 0;
1118     i = p->MinContext->NumStats;
1119     do
1120     {
1121       int cur = s->Symbol;
1122       if (cur == symbol)
1123       {
1124         UInt32 low = sum;
1125         CPpmd_State *s1 = s;
1126         do
1127         {
1128           sum += (s->Freq & (int)(MASK(s->Symbol)));
1129           s++;
1130         }
1131         while (--i);
1132         RangeEnc_Encode(rc, low, s1->Freq, sum + escFreq);
1133         Ppmd_See_Update(see);
1134         p->FoundState = s1;
1135         Ppmd7_Update2(p);
1136         return;
1137       }
1138       sum += (s->Freq & (int)(MASK(cur)));
1139       MASK(cur) = 0;
1140       s++;
1141     }
1142     while (--i);
1143     
1144     RangeEnc_Encode(rc, sum, escFreq, sum + escFreq);
1145     see->Summ = (UInt16)(see->Summ + sum + escFreq);
1146   }
1147 }
1148
1149 const IPpmd7 __archive_ppmd7_functions =
1150 {
1151   &Ppmd7_Construct,
1152   &Ppmd7_Alloc,
1153   &Ppmd7_Free,
1154   &Ppmd7_Init,
1155   &Ppmd7z_RangeDec_CreateVTable,
1156   &PpmdRAR_RangeDec_CreateVTable,
1157   &Ppmd7z_RangeDec_Init,
1158   &PpmdRAR_RangeDec_Init,
1159   &Ppmd7_DecodeSymbol,
1160   &Ppmd7z_RangeEnc_Init,
1161   &Ppmd7z_RangeEnc_FlushData,
1162   &Ppmd7_EncodeSymbol
1163 };