deps/lzma-16.04/C/Ppmd7.c

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