C/Ppmd7.c

   1 /* Ppmd7.c -- PPMdH codec\r
   2 2010-03-12 : Igor Pavlov : Public domain\r
   3 This code is based on PPMd var.H (2001): Dmitry Shkarin : Public domain */\r
   4 \r
   5 #include <memory.h>\r
   6 \r
   7 #include "Ppmd7.h"\r
   8 \r
   9 const Byte PPMD7_kExpEscape[16] = { 25, 14, 9, 7, 5, 5, 4, 4, 4, 3, 3, 3, 2, 2, 2, 2 };\r
  10 static const UInt16 kInitBinEsc[] = { 0x3CDD, 0x1F3F, 0x59BF, 0x48F3, 0x64A1, 0x5ABC, 0x6632, 0x6051};\r
  11 \r
  12 #define MAX_FREQ 124\r
  13 #define UNIT_SIZE 12\r
  14 \r
  15 #define U2B(nu) ((UInt32)(nu) * UNIT_SIZE)\r
  16 #define U2I(nu) (p->Units2Indx[(nu) - 1])\r
  17 #define I2U(indx) (p->Indx2Units[indx])\r
  18 \r
  19 #ifdef PPMD_32BIT\r
  20   #define REF(ptr) (ptr)\r
  21 #else\r
  22   #define REF(ptr) ((UInt32)((Byte *)(ptr) - (p)->Base))\r
  23 #endif\r
  24 \r
  25 #define STATS_REF(ptr) ((CPpmd_State_Ref)REF(ptr))\r
  26 \r
  27 #define CTX(ref) ((CPpmd7_Context *)Ppmd7_GetContext(p, ref))\r
  28 #define STATS(ctx) Ppmd7_GetStats(p, ctx)\r
  29 #define ONE_STATE(ctx) Ppmd7Context_OneState(ctx)\r
  30 #define SUFFIX(ctx) CTX((ctx)->Suffix)\r
  31 \r
  32 typedef CPpmd7_Context * CTX_PTR;\r
  33 \r
  34 struct CPpmd7_Node_;\r
  35 \r
  36 typedef\r
  37   #ifdef PPMD_32BIT\r
  38     struct CPpmd7_Node_ *\r
  39   #else\r
  40     UInt32\r
  41   #endif\r
  42   CPpmd7_Node_Ref;\r
  43 \r
  44 typedef struct CPpmd7_Node_\r
  45 {\r
  46   UInt16 Stamp; /* must be at offset 0 as CPpmd7_Context::NumStats. Stamp=0 means free */\r
  47   UInt16 NU;\r
  48   CPpmd7_Node_Ref Next; /* must be at offset >= 4 */\r
  49   CPpmd7_Node_Ref Prev;\r
  50 } CPpmd7_Node;\r
  51 \r
  52 #ifdef PPMD_32BIT\r
  53   #define NODE(ptr) (ptr)\r
  54 #else\r
  55   #define NODE(offs) ((CPpmd7_Node *)(p->Base + (offs)))\r
  56 #endif\r
  57 \r
  58 void Ppmd7_Construct(CPpmd7 *p)\r
  59 {\r
  60   unsigned i, k, m;\r
  61 \r
  62   p->Base = 0;\r
  63 \r
  64   for (i = 0, k = 0; i < PPMD_NUM_INDEXES; i++)\r
  65   {\r
  66     unsigned step = (i >= 12 ? 4 : (i >> 2) + 1);\r
  67     do { p->Units2Indx[k++] = (Byte)i; } while(--step);\r
  68     p->Indx2Units[i] = (Byte)k;\r
  69   }\r
  70 \r
  71   p->NS2BSIndx[0] = (0 << 1);\r
  72   p->NS2BSIndx[1] = (1 << 1);\r
  73   memset(p->NS2BSIndx + 2, (2 << 1), 9);\r
  74   memset(p->NS2BSIndx + 11, (3 << 1), 256 - 11);\r
  75 \r
  76   for (i = 0; i < 3; i++)\r
  77     p->NS2Indx[i] = (Byte)i;\r
  78   for (m = i, k = 1; i < 256; i++)\r
  79   {\r
  80     p->NS2Indx[i] = (Byte)m;\r
  81     if (--k == 0)\r
  82       k = (++m) - 2;\r
  83   }\r
  84 \r
  85   memset(p->HB2Flag, 0, 0x40);\r
  86   memset(p->HB2Flag + 0x40, 8, 0x100 - 0x40);\r
  87 }\r
  88 \r
  89 void Ppmd7_Free(CPpmd7 *p, ISzAlloc *alloc)\r
  90 {\r
  91   alloc->Free(alloc, p->Base);\r
  92   p->Size = 0;\r
  93   p->Base = 0;\r
  94 }\r
  95 \r
  96 Bool Ppmd7_Alloc(CPpmd7 *p, UInt32 size, ISzAlloc *alloc)\r
  97 {\r
  98   if (p->Base == 0 || p->Size != size)\r
  99   {\r
 100     Ppmd7_Free(p, alloc);\r
 101     p->AlignOffset =\r
 102       #ifdef PPMD_32BIT\r
 103         (4 - size) & 3;\r
 104       #else\r
 105         4 - (size & 3);\r
 106       #endif\r
 107     if ((p->Base = (Byte *)alloc->Alloc(alloc, p->AlignOffset + size\r
 108         #ifndef PPMD_32BIT\r
 109         + UNIT_SIZE\r
 110         #endif\r
 111         )) == 0)\r
 112       return False;\r
 113     p->Size = size;\r
 114   }\r
 115   return True;\r
 116 }\r
 117 \r
 118 static void InsertNode(CPpmd7 *p, void *node, unsigned indx)\r
 119 {\r
 120   *((CPpmd_Void_Ref *)node) = p->FreeList[indx];\r
 121   p->FreeList[indx] = REF(node);\r
 122 }\r
 123 \r
 124 static void *RemoveNode(CPpmd7 *p, unsigned indx)\r
 125 {\r
 126   CPpmd_Void_Ref *node = (CPpmd_Void_Ref *)Ppmd7_GetPtr(p, p->FreeList[indx]);\r
 127   p->FreeList[indx] = *node;\r
 128   return node;\r
 129 }\r
 130 \r
 131 static void SplitBlock(CPpmd7 *p, void *ptr, unsigned oldIndx, unsigned newIndx)\r
 132 {\r
 133   unsigned i, nu = I2U(oldIndx) - I2U(newIndx);\r
 134   ptr = (Byte *)ptr + U2B(I2U(newIndx));\r
 135   if (I2U(i = U2I(nu)) != nu)\r
 136   {\r
 137     unsigned k = I2U(--i);\r
 138     InsertNode(p, ((Byte *)ptr) + U2B(k), nu - k - 1);\r
 139   }\r
 140   InsertNode(p, ptr, i);\r
 141 }\r
 142 \r
 143 static void GlueFreeBlocks(CPpmd7 *p)\r
 144 {\r
 145   #ifdef PPMD_32BIT\r
 146   CPpmd7_Node headItem;\r
 147   CPpmd7_Node_Ref head = &headItem;\r
 148   #else\r
 149   CPpmd7_Node_Ref head = p->AlignOffset + p->Size;\r
 150   #endif\r
 151   \r
 152   CPpmd7_Node_Ref n = head;\r
 153   unsigned i;\r
 154 \r
 155   p->GlueCount = 255;\r
 156 \r
 157   /* create doubly-linked list of free blocks */\r
 158   for (i = 0; i < PPMD_NUM_INDEXES; i++)\r
 159   {\r
 160     UInt16 nu = I2U(i);\r
 161     CPpmd7_Node_Ref next = (CPpmd7_Node_Ref)p->FreeList[i];\r
 162     p->FreeList[i] = 0;\r
 163     while (next != 0)\r
 164     {\r
 165       CPpmd7_Node *node = NODE(next);\r
 166       node->Next = n;\r
 167       n = NODE(n)->Prev = next;\r
 168       next = *(const CPpmd7_Node_Ref *)node;\r
 169       node->Stamp = 0;\r
 170       node->NU = (UInt16)nu;\r
 171     }\r
 172   }\r
 173   NODE(head)->Stamp = 1;\r
 174   NODE(head)->Next = n;\r
 175   NODE(n)->Prev = head;\r
 176   if (p->LoUnit != p->HiUnit)\r
 177     ((CPpmd7_Node *)p->LoUnit)->Stamp = 1;\r
 178   \r
 179   /* Glue free blocks */\r
 180   while (n != head)\r
 181   {\r
 182     CPpmd7_Node *node = NODE(n);\r
 183     UInt32 nu = (UInt32)node->NU;\r
 184     for (;;)\r
 185     {\r
 186       CPpmd7_Node *node2 = NODE(n) + nu;\r
 187       nu += node2->NU;\r
 188       if (node2->Stamp != 0 || nu >= 0x10000)\r
 189         break;\r
 190       NODE(node2->Prev)->Next = node2->Next;\r
 191       NODE(node2->Next)->Prev = node2->Prev;\r
 192       node->NU = (UInt16)nu;\r
 193     }\r
 194     n = node->Next;\r
 195   }\r
 196   \r
 197   /* Fill lists of free blocks */\r
 198   for (n = NODE(head)->Next; n != head;)\r
 199   {\r
 200     CPpmd7_Node *node = NODE(n);\r
 201     unsigned nu;\r
 202     CPpmd7_Node_Ref next = node->Next;\r
 203     for (nu = node->NU; nu > 128; nu -= 128, node += 128)\r
 204       InsertNode(p, node, PPMD_NUM_INDEXES - 1);\r
 205     if (I2U(i = U2I(nu)) != nu)\r
 206     {\r
 207       unsigned k = I2U(--i);\r
 208       InsertNode(p, node + k, nu - k - 1);\r
 209     }\r
 210     InsertNode(p, node, i);\r
 211     n = next;\r
 212   }\r
 213 }\r
 214 \r
 215 static void *AllocUnitsRare(CPpmd7 *p, unsigned indx)\r
 216 {\r
 217   unsigned i;\r
 218   void *retVal;\r
 219   if (p->GlueCount == 0)\r
 220   {\r
 221     GlueFreeBlocks(p);\r
 222     if (p->FreeList[indx] != 0)\r
 223       return RemoveNode(p, indx);\r
 224   }\r
 225   i = indx;\r
 226   do\r
 227   {\r
 228     if (++i == PPMD_NUM_INDEXES)\r
 229     {\r
 230       UInt32 numBytes = U2B(I2U(indx));\r
 231       p->GlueCount--;\r
 232       return ((UInt32)(p->UnitsStart - p->Text) > numBytes) ? (p->UnitsStart -= numBytes) : (NULL);\r
 233     }\r
 234   }\r
 235   while (p->FreeList[i] == 0);\r
 236   retVal = RemoveNode(p, i);\r
 237   SplitBlock(p, retVal, i, indx);\r
 238   return retVal;\r
 239 }\r
 240 \r
 241 static void *AllocUnits(CPpmd7 *p, unsigned indx)\r
 242 {\r
 243   UInt32 numBytes;\r
 244   if (p->FreeList[indx] != 0)\r
 245     return RemoveNode(p, indx);\r
 246   numBytes = U2B(I2U(indx));\r
 247   if (numBytes <= (UInt32)(p->HiUnit - p->LoUnit))\r
 248   {\r
 249     void *retVal = p->LoUnit;\r
 250     p->LoUnit += numBytes;\r
 251     return retVal;\r
 252   }\r
 253   return AllocUnitsRare(p, indx);\r
 254 }\r
 255 \r
 256 #define MyMem12Cpy(dest, src, num) \\r
 257   { UInt32 *d = (UInt32 *)dest; const UInt32 *s = (const UInt32 *)src; UInt32 n = num; \\r
 258     do { d[0] = s[0]; d[1] = s[1]; d[2] = s[2]; s += 3; d += 3; } while(--n); }\r
 259 \r
 260 static void *ShrinkUnits(CPpmd7 *p, void *oldPtr, unsigned oldNU, unsigned newNU)\r
 261 {\r
 262   unsigned i0 = U2I(oldNU);\r
 263   unsigned i1 = U2I(newNU);\r
 264   if (i0 == i1)\r
 265     return oldPtr;\r
 266   if (p->FreeList[i1] != 0)\r
 267   {\r
 268     void *ptr = RemoveNode(p, i1);\r
 269     MyMem12Cpy(ptr, oldPtr, newNU);\r
 270     InsertNode(p, oldPtr, i0);\r
 271     return ptr;\r
 272   }\r
 273   SplitBlock(p, oldPtr, i0, i1);\r
 274   return oldPtr;\r
 275 }\r
 276 \r
 277 #define SUCCESSOR(p) ((CPpmd_Void_Ref)((p)->SuccessorLow | ((UInt32)(p)->SuccessorHigh << 16)))\r
 278 \r
 279 static void SetSuccessor(CPpmd_State *p, CPpmd_Void_Ref v)\r
 280 {\r
 281   (p)->SuccessorLow = (UInt16)((UInt32)(v) & 0xFFFF);\r
 282   (p)->SuccessorHigh = (UInt16)(((UInt32)(v) >> 16) & 0xFFFF);\r
 283 }\r
 284 \r
 285 static void RestartModel(CPpmd7 *p)\r
 286 {\r
 287   unsigned i, k, m;\r
 288 \r
 289   memset(p->FreeList, 0, sizeof(p->FreeList));\r
 290   p->Text = p->Base + p->AlignOffset;\r
 291   p->HiUnit = p->Text + p->Size;\r
 292   p->LoUnit = p->UnitsStart = p->HiUnit - p->Size / 8 / UNIT_SIZE * 7 * UNIT_SIZE;\r
 293   p->GlueCount = 0;\r
 294 \r
 295   p->OrderFall = p->MaxOrder;\r
 296   p->RunLength = p->InitRL = -(Int32)((p->MaxOrder < 12) ? p->MaxOrder : 12) - 1;\r
 297   p->PrevSuccess = 0;\r
 298 \r
 299   p->MinContext = p->MaxContext = (CTX_PTR)(p->HiUnit -= UNIT_SIZE); /* AllocContext(p); */\r
 300   p->MinContext->Suffix = 0;\r
 301   p->MinContext->NumStats = 256;\r
 302   p->MinContext->SummFreq = 256 + 1;\r
 303   p->FoundState = (CPpmd_State *)p->LoUnit; /* AllocUnits(p, PPMD_NUM_INDEXES - 1); */\r
 304   p->LoUnit += U2B(256 / 2);\r
 305   p->MinContext->Stats = REF(p->FoundState);\r
 306   for (i = 0; i < 256; i++)\r
 307   {\r
 308     CPpmd_State *s = &p->FoundState[i];\r
 309     s->Symbol = (Byte)i;\r
 310     s->Freq = 1;\r
 311     SetSuccessor(s, 0);\r
 312   }\r
 313 \r
 314   for (i = 0; i < 128; i++)\r
 315     for (k = 0; k < 8; k++)\r
 316     {\r
 317       UInt16 *dest = p->BinSumm[i] + k;\r
 318       UInt16 val = (UInt16)(PPMD_BIN_SCALE - kInitBinEsc[k] / (i + 2));\r
 319       for (m = 0; m < 64; m += 8)\r
 320         dest[m] = val;\r
 321     }\r
 322   \r
 323   for (i = 0; i < 25; i++)\r
 324     for (k = 0; k < 16; k++)\r
 325     {\r
 326       CPpmd_See *s = &p->See[i][k];\r
 327       s->Summ = (UInt16)((5 * i + 10) << (s->Shift = PPMD_PERIOD_BITS - 4));\r
 328       s->Count = 4;\r
 329     }\r
 330 }\r
 331 \r
 332 void Ppmd7_Init(CPpmd7 *p, unsigned maxOrder)\r
 333 {\r
 334   p->MaxOrder = maxOrder;\r
 335   RestartModel(p);\r
 336   p->DummySee.Shift = PPMD_PERIOD_BITS;\r
 337   p->DummySee.Summ = 0; /* unused */\r
 338   p->DummySee.Count = 64; /* unused */\r
 339 }\r
 340 \r
 341 static CTX_PTR CreateSuccessors(CPpmd7 *p, Bool skip)\r
 342 {\r
 343   CPpmd_State upState;\r
 344   CTX_PTR c = p->MinContext;\r
 345   CPpmd_Byte_Ref upBranch = (CPpmd_Byte_Ref)SUCCESSOR(p->FoundState);\r
 346   CPpmd_State *ps[PPMD7_MAX_ORDER];\r
 347   unsigned numPs = 0;\r
 348   \r
 349   if (!skip)\r
 350     ps[numPs++] = p->FoundState;\r
 351   \r
 352   while (c->Suffix)\r
 353   {\r
 354     CPpmd_Void_Ref successor;\r
 355     CPpmd_State *s;\r
 356     c = SUFFIX(c);\r
 357     if (c->NumStats != 1)\r
 358     {\r
 359       for (s = STATS(c); s->Symbol != p->FoundState->Symbol; s++);\r
 360     }\r
 361     else\r
 362       s = ONE_STATE(c);\r
 363     successor = SUCCESSOR(s);\r
 364     if (successor != upBranch)\r
 365     {\r
 366       c = CTX(successor);\r
 367       if (numPs == 0)\r
 368         return c;\r
 369       break;\r
 370     }\r
 371     ps[numPs++] = s;\r
 372   }\r
 373   \r
 374   upState.Symbol = *(const Byte *)Ppmd7_GetPtr(p, upBranch);\r
 375   SetSuccessor(&upState, upBranch + 1);\r
 376   \r
 377   if (c->NumStats == 1)\r
 378     upState.Freq = ONE_STATE(c)->Freq;\r
 379   else\r
 380   {\r
 381     UInt32 cf, s0;\r
 382     CPpmd_State *s;\r
 383     for (s = STATS(c); s->Symbol != upState.Symbol; s++);\r
 384     cf = s->Freq - 1;\r
 385     s0 = c->SummFreq - c->NumStats - cf;\r
 386     upState.Freq = (Byte)(1 + ((2 * cf <= s0) ? (5 * cf > s0) : ((2 * cf + 3 * s0 - 1) / (2 * s0))));\r
 387   }\r
 388 \r
 389   do\r
 390   {\r
 391     /* Create Child */\r
 392     CTX_PTR c1; /* = AllocContext(p); */\r
 393     if (p->HiUnit != p->LoUnit)\r
 394       c1 = (CTX_PTR)(p->HiUnit -= UNIT_SIZE);\r
 395     else if (p->FreeList[0] != 0)\r
 396       c1 = (CTX_PTR)RemoveNode(p, 0);\r
 397     else\r
 398     {\r
 399       c1 = (CTX_PTR)AllocUnitsRare(p, 0);\r
 400       if (!c1)\r
 401         return NULL;\r
 402     }\r
 403     c1->NumStats = 1;\r
 404     *ONE_STATE(c1) = upState;\r
 405     c1->Suffix = REF(c);\r
 406     SetSuccessor(ps[--numPs], REF(c1));\r
 407     c = c1;\r
 408   }\r
 409   while (numPs != 0);\r
 410   \r
 411   return c;\r
 412 }\r
 413 \r
 414 static void SwapStates(CPpmd_State *t1, CPpmd_State *t2)\r
 415 {\r
 416   CPpmd_State tmp = *t1;\r
 417   *t1 = *t2;\r
 418   *t2 = tmp;\r
 419 }\r
 420 \r
 421 static void UpdateModel(CPpmd7 *p)\r
 422 {\r
 423   CPpmd_Void_Ref successor, fSuccessor = SUCCESSOR(p->FoundState);\r
 424   CTX_PTR c;\r
 425   unsigned s0, ns;\r
 426   \r
 427   if (p->FoundState->Freq < MAX_FREQ / 4 && p->MinContext->Suffix != 0)\r
 428   {\r
 429     c = SUFFIX(p->MinContext);\r
 430     \r
 431     if (c->NumStats == 1)\r
 432     {\r
 433       CPpmd_State *s = ONE_STATE(c);\r
 434       if (s->Freq < 32)\r
 435         s->Freq++;\r
 436     }\r
 437     else\r
 438     {\r
 439       CPpmd_State *s = STATS(c);\r
 440       if (s->Symbol != p->FoundState->Symbol)\r
 441       {\r
 442         do { s++; } while (s->Symbol != p->FoundState->Symbol);\r
 443         if (s[0].Freq >= s[-1].Freq)\r
 444         {\r
 445           SwapStates(&s[0], &s[-1]);\r
 446           s--;\r
 447         }\r
 448       }\r
 449       if (s->Freq < MAX_FREQ - 9)\r
 450       {\r
 451         s->Freq += 2;\r
 452         c->SummFreq += 2;\r
 453       }\r
 454     }\r
 455   }\r
 456 \r
 457   if (p->OrderFall == 0)\r
 458   {\r
 459     p->MinContext = p->MaxContext = CreateSuccessors(p, True);\r
 460     if (p->MinContext == 0)\r
 461     {\r
 462       RestartModel(p);\r
 463       return;\r
 464     }\r
 465     SetSuccessor(p->FoundState, REF(p->MinContext));\r
 466     return;\r
 467   }\r
 468   \r
 469   *p->Text++ = p->FoundState->Symbol;\r
 470   successor = REF(p->Text);\r
 471   if (p->Text >= p->UnitsStart)\r
 472   {\r
 473     RestartModel(p);\r
 474     return;\r
 475   }\r
 476   \r
 477   if (fSuccessor)\r
 478   {\r
 479     if (fSuccessor <= successor)\r
 480     {\r
 481       CTX_PTR cs = CreateSuccessors(p, False);\r
 482       if (cs == NULL)\r
 483       {\r
 484         RestartModel(p);\r
 485         return;\r
 486       }\r
 487       fSuccessor = REF(cs);\r
 488     }\r
 489     if (--p->OrderFall == 0)\r
 490     {\r
 491       successor = fSuccessor;\r
 492       p->Text -= (p->MaxContext != p->MinContext);\r
 493     }\r
 494   }\r
 495   else\r
 496   {\r
 497     SetSuccessor(p->FoundState, successor);\r
 498     fSuccessor = REF(p->MinContext);\r
 499   }\r
 500   \r
 501   s0 = p->MinContext->SummFreq - (ns = p->MinContext->NumStats) - (p->FoundState->Freq - 1);\r
 502   \r
 503   for (c = p->MaxContext; c != p->MinContext; c = SUFFIX(c))\r
 504   {\r
 505     unsigned ns1;\r
 506     UInt32 cf, sf;\r
 507     if ((ns1 = c->NumStats) != 1)\r
 508     {\r
 509       if ((ns1 & 1) == 0)\r
 510       {\r
 511         /* Expand for one UNIT */\r
 512         unsigned oldNU = ns1 >> 1;\r
 513         unsigned i = U2I(oldNU);\r
 514         if (i != U2I(oldNU + 1))\r
 515         {\r
 516           void *ptr = AllocUnits(p, i + 1);\r
 517           void *oldPtr;\r
 518           if (!ptr)\r
 519           {\r
 520             RestartModel(p);\r
 521             return;\r
 522           }\r
 523           oldPtr = STATS(c);\r
 524           MyMem12Cpy(ptr, oldPtr, oldNU);\r
 525           InsertNode(p, oldPtr, i);\r
 526           c->Stats = STATS_REF(ptr);\r
 527         }\r
 528       }\r
 529       c->SummFreq = (UInt16)(c->SummFreq + (2 * ns1 < ns) + 2 * ((4 * ns1 <= ns) & (c->SummFreq <= 8 * ns1)));\r
 530     }\r
 531     else\r
 532     {\r
 533       CPpmd_State *s = (CPpmd_State*)AllocUnits(p, 0);\r
 534       if (!s)\r
 535       {\r
 536         RestartModel(p);\r
 537         return;\r
 538       }\r
 539       *s = *ONE_STATE(c);\r
 540       c->Stats = REF(s);\r
 541       if (s->Freq < MAX_FREQ / 4 - 1)\r
 542         s->Freq <<= 1;\r
 543       else\r
 544         s->Freq = MAX_FREQ - 4;\r
 545       c->SummFreq = (UInt16)(s->Freq + p->InitEsc + (ns > 3));\r
 546     }\r
 547     cf = 2 * (UInt32)p->FoundState->Freq * (c->SummFreq + 6);\r
 548     sf = (UInt32)s0 + c->SummFreq;\r
 549     if (cf < 6 * sf)\r
 550     {\r
 551       cf = 1 + (cf > sf) + (cf >= 4 * sf);\r
 552       c->SummFreq += 3;\r
 553     }\r
 554     else\r
 555     {\r
 556       cf = 4 + (cf >= 9 * sf) + (cf >= 12 * sf) + (cf >= 15 * sf);\r
 557       c->SummFreq = (UInt16)(c->SummFreq + cf);\r
 558     }\r
 559     {\r
 560       CPpmd_State *s = STATS(c) + ns1;\r
 561       SetSuccessor(s, successor);\r
 562       s->Symbol = p->FoundState->Symbol;\r
 563       s->Freq = (Byte)cf;\r
 564       c->NumStats = (UInt16)(ns1 + 1);\r
 565     }\r
 566   }\r
 567   p->MaxContext = p->MinContext = CTX(fSuccessor);\r
 568 }\r
 569   \r
 570 static void Rescale(CPpmd7 *p)\r
 571 {\r
 572   unsigned i, adder, sumFreq, escFreq;\r
 573   CPpmd_State *stats = STATS(p->MinContext);\r
 574   CPpmd_State *s = p->FoundState;\r
 575   {\r
 576     CPpmd_State tmp = *s;\r
 577     for (; s != stats; s--)\r
 578       s[0] = s[-1];\r
 579     *s = tmp;\r
 580   }\r
 581   escFreq = p->MinContext->SummFreq - s->Freq;\r
 582   s->Freq += 4;\r
 583   adder = (p->OrderFall != 0);\r
 584   s->Freq = (Byte)((s->Freq + adder) >> 1);\r
 585   sumFreq = s->Freq;\r
 586   \r
 587   i = p->MinContext->NumStats - 1;\r
 588   do\r
 589   {\r
 590     escFreq -= (++s)->Freq;\r
 591     s->Freq = (Byte)((s->Freq + adder) >> 1);\r
 592     sumFreq += s->Freq;\r
 593     if (s[0].Freq > s[-1].Freq)\r
 594     {\r
 595       CPpmd_State *s1 = s;\r
 596       CPpmd_State tmp = *s1;\r
 597       do\r
 598         s1[0] = s1[-1];\r
 599       while (--s1 != stats && tmp.Freq > s1[-1].Freq);\r
 600       *s1 = tmp;\r
 601     }\r
 602   }\r
 603   while (--i);\r
 604   \r
 605   if (s->Freq == 0)\r
 606   {\r
 607     unsigned numStats = p->MinContext->NumStats;\r
 608     unsigned n0, n1;\r
 609     do { i++; } while ((--s)->Freq == 0);\r
 610     escFreq += i;\r
 611     p->MinContext->NumStats = (UInt16)(p->MinContext->NumStats - i);\r
 612     if (p->MinContext->NumStats == 1)\r
 613     {\r
 614       CPpmd_State tmp = *stats;\r
 615       do\r
 616       {\r
 617         tmp.Freq = (Byte)(tmp.Freq - (tmp.Freq >> 1));\r
 618         escFreq >>= 1;\r
 619       }\r
 620       while (escFreq > 1);\r
 621       InsertNode(p, stats, U2I(((numStats + 1) >> 1)));\r
 622       *(p->FoundState = ONE_STATE(p->MinContext)) = tmp;\r
 623       return;\r
 624     }\r
 625     n0 = (numStats + 1) >> 1;\r
 626     n1 = (p->MinContext->NumStats + 1) >> 1;\r
 627     if (n0 != n1)\r
 628       p->MinContext->Stats = STATS_REF(ShrinkUnits(p, stats, n0, n1));\r
 629   }\r
 630   p->MinContext->SummFreq = (UInt16)(sumFreq + escFreq - (escFreq >> 1));\r
 631   p->FoundState = STATS(p->MinContext);\r
 632 }\r
 633 \r
 634 CPpmd_See *Ppmd7_MakeEscFreq(CPpmd7 *p, unsigned numMasked, UInt32 *escFreq)\r
 635 {\r
 636   CPpmd_See *see;\r
 637   unsigned nonMasked = p->MinContext->NumStats - numMasked;\r
 638   if (p->MinContext->NumStats != 256)\r
 639   {\r
 640     see = p->See[p->NS2Indx[nonMasked - 1]] +\r
 641         (nonMasked < (unsigned)SUFFIX(p->MinContext)->NumStats - p->MinContext->NumStats) +\r
 642         2 * (p->MinContext->SummFreq < 11 * p->MinContext->NumStats) +\r
 643         4 * (numMasked > nonMasked) +\r
 644         p->HiBitsFlag;\r
 645     {\r
 646       unsigned r = (see->Summ >> see->Shift);\r
 647       see->Summ = (UInt16)(see->Summ - r);\r
 648       *escFreq = r + (r == 0);\r
 649     }\r
 650   }\r
 651   else\r
 652   {\r
 653     see = &p->DummySee;\r
 654     *escFreq = 1;\r
 655   }\r
 656   return see;\r
 657 }\r
 658 \r
 659 static void NextContext(CPpmd7 *p)\r
 660 {\r
 661   CTX_PTR c = CTX(SUCCESSOR(p->FoundState));\r
 662   if (p->OrderFall == 0 && (Byte *)c > p->Text)\r
 663     p->MinContext = p->MaxContext = c;\r
 664   else\r
 665     UpdateModel(p);\r
 666 }\r
 667 \r
 668 void Ppmd7_Update1(CPpmd7 *p)\r
 669 {\r
 670   CPpmd_State *s = p->FoundState;\r
 671   s->Freq += 4;\r
 672   p->MinContext->SummFreq += 4;\r
 673   if (s[0].Freq > s[-1].Freq)\r
 674   {\r
 675     SwapStates(&s[0], &s[-1]);\r
 676     p->FoundState = --s;\r
 677     if (s->Freq > MAX_FREQ)\r
 678       Rescale(p);\r
 679   }\r
 680   NextContext(p);\r
 681 }\r
 682 \r
 683 void Ppmd7_Update1_0(CPpmd7 *p)\r
 684 {\r
 685   p->PrevSuccess = (2 * p->FoundState->Freq > p->MinContext->SummFreq);\r
 686   p->RunLength += p->PrevSuccess;\r
 687   p->MinContext->SummFreq += 4;\r
 688   if ((p->FoundState->Freq += 4) > MAX_FREQ)\r
 689     Rescale(p);\r
 690   NextContext(p);\r
 691 }\r
 692 \r
 693 void Ppmd7_UpdateBin(CPpmd7 *p)\r
 694 {\r
 695   p->FoundState->Freq = (Byte)(p->FoundState->Freq + (p->FoundState->Freq < 128 ? 1: 0));\r
 696   p->PrevSuccess = 1;\r
 697   p->RunLength++;\r
 698   NextContext(p);\r
 699 }\r
 700 \r
 701 void Ppmd7_Update2(CPpmd7 *p)\r
 702 {\r
 703   p->MinContext->SummFreq += 4;\r
 704   if ((p->FoundState->Freq += 4) > MAX_FREQ)\r
 705     Rescale(p);\r
 706   p->RunLength = p->InitRL;\r
 707   UpdateModel(p);\r
 708 }\r