1344063Smm/* Ppmd8.c -- PPMdI codec 2344063Smm2016-05-21 : Igor Pavlov : Public domain 3344063SmmThis code is based on PPMd var.I (2002): Dmitry Shkarin : Public domain */ 4344063Smm 5344063Smm#include "archive_platform.h" 6344063Smm 7344063Smm#include <string.h> 8344063Smm 9344063Smm#include "archive_ppmd8_private.h" 10344063Smm 11344063Smmconst Byte PPMD8_kExpEscape[16] = { 25, 14, 9, 7, 5, 5, 4, 4, 4, 3, 3, 3, 2, 2, 2, 2 }; 12344063Smmstatic const UInt16 kInitBinEsc[] = { 0x3CDD, 0x1F3F, 0x59BF, 0x48F3, 0x64A1, 0x5ABC, 0x6632, 0x6051}; 13344063Smm 14344063Smm#define MAX_FREQ 124 15344063Smm#define UNIT_SIZE 12 16344063Smm 17344063Smm#define U2B(nu) ((UInt32)(nu) * UNIT_SIZE) 18344063Smm#define U2I(nu) (p->Units2Indx[(nu) - 1]) 19344063Smm#define I2U(indx) (p->Indx2Units[indx]) 20344063Smm 21344063Smm#ifdef PPMD_32BIT 22344063Smm #define REF(ptr) (ptr) 23344063Smm#else 24344063Smm #define REF(ptr) ((UInt32)((Byte *)(ptr) - (p)->Base)) 25344063Smm#endif 26344063Smm 27344063Smm#define STATS_REF(ptr) ((CPpmd_State_Ref)REF(ptr)) 28344063Smm 29344063Smm#define CTX(ref) ((CPpmd8_Context *)Ppmd8_GetContext(p, ref)) 30344063Smm#define STATS(ctx) Ppmd8_GetStats(p, ctx) 31344063Smm#define ONE_STATE(ctx) Ppmd8Context_OneState(ctx) 32344063Smm#define SUFFIX(ctx) CTX((ctx)->Suffix) 33344063Smm 34344063Smm#define kTop (1 << 24) 35344063Smm#define kBot (1 << 15) 36344063Smm 37344063Smmtypedef CPpmd8_Context * CTX_PTR; 38344063Smm 39344063Smmstruct CPpmd8_Node_; 40344063Smm 41344063Smmtypedef 42344063Smm #ifdef PPMD_32BIT 43344063Smm struct CPpmd8_Node_ * 44344063Smm #else 45344063Smm UInt32 46344063Smm #endif 47344063Smm CPpmd8_Node_Ref; 48344063Smm 49344063Smmtypedef struct CPpmd8_Node_ 50344063Smm{ 51344063Smm UInt32 Stamp; 52344063Smm CPpmd8_Node_Ref Next; 53344063Smm UInt32 NU; 54344063Smm} CPpmd8_Node; 55344063Smm 56344063Smm#ifdef PPMD_32BIT 57344063Smm #define NODE(ptr) (ptr) 58344063Smm#else 59344063Smm #define NODE(offs) ((CPpmd8_Node *)(p->Base + (offs))) 60344063Smm#endif 61344063Smm 62344063Smm#define EMPTY_NODE 0xFFFFFFFF 63344063Smm 64344063Smmvoid Ppmd8_Construct(CPpmd8 *p) 65344063Smm{ 66344063Smm unsigned i, k, m; 67344063Smm 68344063Smm p->Base = 0; 69344063Smm 70344063Smm for (i = 0, k = 0; i < PPMD_NUM_INDEXES; i++) 71344063Smm { 72344063Smm unsigned step = (i >= 12 ? 4 : (i >> 2) + 1); 73344063Smm do { p->Units2Indx[k++] = (Byte)i; } while (--step); 74344063Smm p->Indx2Units[i] = (Byte)k; 75344063Smm } 76344063Smm 77344063Smm p->NS2BSIndx[0] = (0 << 1); 78344063Smm p->NS2BSIndx[1] = (1 << 1); 79344063Smm memset(p->NS2BSIndx + 2, (2 << 1), 9); 80344063Smm memset(p->NS2BSIndx + 11, (3 << 1), 256 - 11); 81344063Smm 82344063Smm for (i = 0; i < 5; i++) 83344063Smm p->NS2Indx[i] = (Byte)i; 84344063Smm for (m = i, k = 1; i < 260; i++) 85344063Smm { 86344063Smm p->NS2Indx[i] = (Byte)m; 87344063Smm if (--k == 0) 88344063Smm k = (++m) - 4; 89344063Smm } 90344063Smm} 91344063Smm 92344063Smmvoid Ppmd8_Free(CPpmd8 *p) 93344063Smm{ 94344063Smm free(p->Base); 95344063Smm p->Size = 0; 96344063Smm p->Base = 0; 97344063Smm} 98344063Smm 99344063SmmBool Ppmd8_Alloc(CPpmd8 *p, UInt32 size) 100344063Smm{ 101344063Smm if (p->Base == 0 || p->Size != size) 102344063Smm { 103344063Smm Ppmd8_Free(p); 104344063Smm p->AlignOffset = 105344063Smm #ifdef PPMD_32BIT 106344063Smm (4 - size) & 3; 107344063Smm #else 108344063Smm 4 - (size & 3); 109344063Smm #endif 110344063Smm if ((p->Base = (Byte *)malloc(p->AlignOffset + size)) == 0) 111344063Smm return False; 112344063Smm p->Size = size; 113344063Smm } 114344063Smm return True; 115344063Smm} 116344063Smm 117344063Smmstatic void InsertNode(CPpmd8 *p, void *node, unsigned indx) 118344063Smm{ 119344063Smm ((CPpmd8_Node *)node)->Stamp = EMPTY_NODE; 120344063Smm ((CPpmd8_Node *)node)->Next = (CPpmd8_Node_Ref)p->FreeList[indx]; 121344063Smm ((CPpmd8_Node *)node)->NU = I2U(indx); 122344063Smm p->FreeList[indx] = REF(node); 123344063Smm p->Stamps[indx]++; 124344063Smm} 125344063Smm 126344063Smmstatic void *RemoveNode(CPpmd8 *p, unsigned indx) 127344063Smm{ 128344063Smm CPpmd8_Node *node = NODE((CPpmd8_Node_Ref)p->FreeList[indx]); 129344063Smm p->FreeList[indx] = node->Next; 130344063Smm p->Stamps[indx]--; 131344063Smm return node; 132344063Smm} 133344063Smm 134344063Smmstatic void SplitBlock(CPpmd8 *p, void *ptr, unsigned oldIndx, unsigned newIndx) 135344063Smm{ 136344063Smm unsigned i, nu = I2U(oldIndx) - I2U(newIndx); 137344063Smm ptr = (Byte *)ptr + U2B(I2U(newIndx)); 138344063Smm if (I2U(i = U2I(nu)) != nu) 139344063Smm { 140344063Smm unsigned k = I2U(--i); 141344063Smm InsertNode(p, ((Byte *)ptr) + U2B(k), nu - k - 1); 142344063Smm } 143344063Smm InsertNode(p, ptr, i); 144344063Smm} 145344063Smm 146344063Smmstatic void GlueFreeBlocks(CPpmd8 *p) 147344063Smm{ 148344063Smm CPpmd8_Node_Ref head = 0; 149344063Smm CPpmd8_Node_Ref *prev = &head; 150344063Smm unsigned i; 151344063Smm 152344063Smm p->GlueCount = 1 << 13; 153344063Smm memset(p->Stamps, 0, sizeof(p->Stamps)); 154344063Smm 155344063Smm /* Order-0 context is always at top UNIT, so we don't need guard NODE at the end. 156344063Smm All blocks up to p->LoUnit can be free, so we need guard NODE at LoUnit. */ 157344063Smm if (p->LoUnit != p->HiUnit) 158344063Smm ((CPpmd8_Node *)p->LoUnit)->Stamp = 0; 159344063Smm 160344063Smm /* Glue free blocks */ 161344063Smm for (i = 0; i < PPMD_NUM_INDEXES; i++) 162344063Smm { 163344063Smm CPpmd8_Node_Ref next = (CPpmd8_Node_Ref)p->FreeList[i]; 164344063Smm p->FreeList[i] = 0; 165344063Smm while (next != 0) 166344063Smm { 167344063Smm CPpmd8_Node *node = NODE(next); 168344063Smm if (node->NU != 0) 169344063Smm { 170344063Smm CPpmd8_Node *node2; 171344063Smm *prev = next; 172344063Smm prev = &(node->Next); 173344063Smm while ((node2 = node + node->NU)->Stamp == EMPTY_NODE) 174344063Smm { 175344063Smm node->NU += node2->NU; 176344063Smm node2->NU = 0; 177344063Smm } 178344063Smm } 179344063Smm next = node->Next; 180344063Smm } 181344063Smm } 182344063Smm *prev = 0; 183344063Smm 184344063Smm /* Fill lists of free blocks */ 185344063Smm while (head != 0) 186344063Smm { 187344063Smm CPpmd8_Node *node = NODE(head); 188344063Smm unsigned nu; 189344063Smm head = node->Next; 190344063Smm nu = node->NU; 191344063Smm if (nu == 0) 192344063Smm continue; 193344063Smm for (; nu > 128; nu -= 128, node += 128) 194344063Smm InsertNode(p, node, PPMD_NUM_INDEXES - 1); 195344063Smm if (I2U(i = U2I(nu)) != nu) 196344063Smm { 197344063Smm unsigned k = I2U(--i); 198344063Smm InsertNode(p, node + k, nu - k - 1); 199344063Smm } 200344063Smm InsertNode(p, node, i); 201344063Smm } 202344063Smm} 203344063Smm 204344063Smmstatic void *AllocUnitsRare(CPpmd8 *p, unsigned indx) 205344063Smm{ 206344063Smm unsigned i; 207344063Smm void *retVal; 208344063Smm if (p->GlueCount == 0) 209344063Smm { 210344063Smm GlueFreeBlocks(p); 211344063Smm if (p->FreeList[indx] != 0) 212344063Smm return RemoveNode(p, indx); 213344063Smm } 214344063Smm i = indx; 215344063Smm do 216344063Smm { 217344063Smm if (++i == PPMD_NUM_INDEXES) 218344063Smm { 219344063Smm UInt32 numBytes = U2B(I2U(indx)); 220344063Smm p->GlueCount--; 221344063Smm return ((UInt32)(p->UnitsStart - p->Text) > numBytes) ? (p->UnitsStart -= numBytes) : (NULL); 222344063Smm } 223344063Smm } 224344063Smm while (p->FreeList[i] == 0); 225344063Smm retVal = RemoveNode(p, i); 226344063Smm SplitBlock(p, retVal, i, indx); 227344063Smm return retVal; 228344063Smm} 229344063Smm 230344063Smmstatic void *AllocUnits(CPpmd8 *p, unsigned indx) 231344063Smm{ 232344063Smm UInt32 numBytes; 233344063Smm if (p->FreeList[indx] != 0) 234344063Smm return RemoveNode(p, indx); 235344063Smm numBytes = U2B(I2U(indx)); 236344063Smm if (numBytes <= (UInt32)(p->HiUnit - p->LoUnit)) 237344063Smm { 238344063Smm void *retVal = p->LoUnit; 239344063Smm p->LoUnit += numBytes; 240344063Smm return retVal; 241344063Smm } 242344063Smm return AllocUnitsRare(p, indx); 243344063Smm} 244344063Smm 245344063Smm#define MyMem12Cpy(dest, src, num) \ 246344063Smm { UInt32 *d = (UInt32 *)dest; const UInt32 *z = (const UInt32 *)src; UInt32 n = num; \ 247344063Smm do { d[0] = z[0]; d[1] = z[1]; d[2] = z[2]; z += 3; d += 3; } while (--n); } 248344063Smm 249344063Smmstatic void *ShrinkUnits(CPpmd8 *p, void *oldPtr, unsigned oldNU, unsigned newNU) 250344063Smm{ 251344063Smm unsigned i0 = U2I(oldNU); 252344063Smm unsigned i1 = U2I(newNU); 253344063Smm if (i0 == i1) 254344063Smm return oldPtr; 255344063Smm if (p->FreeList[i1] != 0) 256344063Smm { 257344063Smm void *ptr = RemoveNode(p, i1); 258344063Smm MyMem12Cpy(ptr, oldPtr, newNU); 259344063Smm InsertNode(p, oldPtr, i0); 260344063Smm return ptr; 261344063Smm } 262344063Smm SplitBlock(p, oldPtr, i0, i1); 263344063Smm return oldPtr; 264344063Smm} 265344063Smm 266344063Smmstatic void FreeUnits(CPpmd8 *p, void *ptr, unsigned nu) 267344063Smm{ 268344063Smm InsertNode(p, ptr, U2I(nu)); 269344063Smm} 270344063Smm 271344063Smmstatic void SpecialFreeUnit(CPpmd8 *p, void *ptr) 272344063Smm{ 273344063Smm if ((Byte *)ptr != p->UnitsStart) 274344063Smm InsertNode(p, ptr, 0); 275344063Smm else 276344063Smm { 277344063Smm #ifdef PPMD8_FREEZE_SUPPORT 278344063Smm *(UInt32 *)ptr = EMPTY_NODE; /* it's used for (Flags == 0xFF) check in RemoveBinContexts */ 279344063Smm #endif 280344063Smm p->UnitsStart += UNIT_SIZE; 281344063Smm } 282344063Smm} 283344063Smm 284344063Smmstatic void *MoveUnitsUp(CPpmd8 *p, void *oldPtr, unsigned nu) 285344063Smm{ 286344063Smm unsigned indx = U2I(nu); 287344063Smm void *ptr; 288344063Smm if ((Byte *)oldPtr > p->UnitsStart + 16 * 1024 || REF(oldPtr) > p->FreeList[indx]) 289344063Smm return oldPtr; 290344063Smm ptr = RemoveNode(p, indx); 291344063Smm MyMem12Cpy(ptr, oldPtr, nu); 292344063Smm if ((Byte*)oldPtr != p->UnitsStart) 293344063Smm InsertNode(p, oldPtr, indx); 294344063Smm else 295344063Smm p->UnitsStart += U2B(I2U(indx)); 296344063Smm return ptr; 297344063Smm} 298344063Smm 299344063Smmstatic void ExpandTextArea(CPpmd8 *p) 300344063Smm{ 301344063Smm UInt32 count[PPMD_NUM_INDEXES]; 302344063Smm unsigned i; 303344063Smm memset(count, 0, sizeof(count)); 304344063Smm if (p->LoUnit != p->HiUnit) 305344063Smm ((CPpmd8_Node *)p->LoUnit)->Stamp = 0; 306344063Smm 307344063Smm { 308344063Smm CPpmd8_Node *node = (CPpmd8_Node *)p->UnitsStart; 309344063Smm for (; node->Stamp == EMPTY_NODE; node += node->NU) 310344063Smm { 311344063Smm node->Stamp = 0; 312344063Smm count[U2I(node->NU)]++; 313344063Smm } 314344063Smm p->UnitsStart = (Byte *)node; 315344063Smm } 316344063Smm 317344063Smm for (i = 0; i < PPMD_NUM_INDEXES; i++) 318344063Smm { 319344063Smm CPpmd8_Node_Ref *next = (CPpmd8_Node_Ref *)&p->FreeList[i]; 320344063Smm while (count[i] != 0) 321344063Smm { 322344063Smm CPpmd8_Node *node = NODE(*next); 323344063Smm while (node->Stamp == 0) 324344063Smm { 325344063Smm *next = node->Next; 326344063Smm node = NODE(*next); 327344063Smm p->Stamps[i]--; 328344063Smm if (--count[i] == 0) 329344063Smm break; 330344063Smm } 331344063Smm next = &node->Next; 332344063Smm } 333344063Smm } 334344063Smm} 335344063Smm 336344063Smm#define SUCCESSOR(p) ((CPpmd_Void_Ref)((p)->SuccessorLow | ((UInt32)(p)->SuccessorHigh << 16))) 337344063Smm 338344063Smmstatic void SetSuccessor(CPpmd_State *p, CPpmd_Void_Ref v) 339344063Smm{ 340344063Smm (p)->SuccessorLow = (UInt16)((UInt32)(v) & 0xFFFF); 341344063Smm (p)->SuccessorHigh = (UInt16)(((UInt32)(v) >> 16) & 0xFFFF); 342344063Smm} 343344063Smm 344344063Smm#define RESET_TEXT(offs) { p->Text = p->Base + p->AlignOffset + (offs); } 345344063Smm 346344063Smmstatic void RestartModel(CPpmd8 *p) 347344063Smm{ 348344063Smm unsigned i, k, m, r; 349344063Smm 350344063Smm memset(p->FreeList, 0, sizeof(p->FreeList)); 351344063Smm memset(p->Stamps, 0, sizeof(p->Stamps)); 352344063Smm RESET_TEXT(0); 353344063Smm p->HiUnit = p->Text + p->Size; 354344063Smm p->LoUnit = p->UnitsStart = p->HiUnit - p->Size / 8 / UNIT_SIZE * 7 * UNIT_SIZE; 355344063Smm p->GlueCount = 0; 356344063Smm 357344063Smm p->OrderFall = p->MaxOrder; 358344063Smm p->RunLength = p->InitRL = -(Int32)((p->MaxOrder < 12) ? p->MaxOrder : 12) - 1; 359344063Smm p->PrevSuccess = 0; 360344063Smm 361344063Smm p->MinContext = p->MaxContext = (CTX_PTR)(p->HiUnit -= UNIT_SIZE); /* AllocContext(p); */ 362344063Smm p->MinContext->Suffix = 0; 363344063Smm p->MinContext->NumStats = 255; 364344063Smm p->MinContext->Flags = 0; 365344063Smm p->MinContext->SummFreq = 256 + 1; 366344063Smm p->FoundState = (CPpmd_State *)p->LoUnit; /* AllocUnits(p, PPMD_NUM_INDEXES - 1); */ 367344063Smm p->LoUnit += U2B(256 / 2); 368344063Smm p->MinContext->Stats = REF(p->FoundState); 369344063Smm for (i = 0; i < 256; i++) 370344063Smm { 371344063Smm CPpmd_State *s = &p->FoundState[i]; 372344063Smm s->Symbol = (Byte)i; 373344063Smm s->Freq = 1; 374344063Smm SetSuccessor(s, 0); 375344063Smm } 376344063Smm 377344063Smm for (i = m = 0; m < 25; m++) 378344063Smm { 379344063Smm while (p->NS2Indx[i] == m) 380344063Smm i++; 381344063Smm for (k = 0; k < 8; k++) 382344063Smm { 383344063Smm UInt16 val = (UInt16)(PPMD_BIN_SCALE - kInitBinEsc[k] / (i + 1)); 384344063Smm UInt16 *dest = p->BinSumm[m] + k; 385344063Smm for (r = 0; r < 64; r += 8) 386344063Smm dest[r] = val; 387344063Smm } 388344063Smm } 389344063Smm 390344063Smm for (i = m = 0; m < 24; m++) 391344063Smm { 392344063Smm while (p->NS2Indx[i + 3] == m + 3) 393344063Smm i++; 394344063Smm for (k = 0; k < 32; k++) 395344063Smm { 396344063Smm CPpmd_See *s = &p->See[m][k]; 397344063Smm s->Summ = (UInt16)((2 * i + 5) << (s->Shift = PPMD_PERIOD_BITS - 4)); 398344063Smm s->Count = 7; 399344063Smm } 400344063Smm } 401344063Smm} 402344063Smm 403344063Smmvoid Ppmd8_Init(CPpmd8 *p, unsigned maxOrder, unsigned restoreMethod) 404344063Smm{ 405344063Smm p->MaxOrder = maxOrder; 406344063Smm p->RestoreMethod = restoreMethod; 407344063Smm RestartModel(p); 408344063Smm p->DummySee.Shift = PPMD_PERIOD_BITS; 409344063Smm p->DummySee.Summ = 0; /* unused */ 410344063Smm p->DummySee.Count = 64; /* unused */ 411344063Smm} 412344063Smm 413344063Smmstatic void Refresh(CPpmd8 *p, CTX_PTR ctx, unsigned oldNU, unsigned scale) 414344063Smm{ 415344063Smm unsigned i = ctx->NumStats, escFreq, sumFreq, flags; 416344063Smm CPpmd_State *s = (CPpmd_State *)ShrinkUnits(p, STATS(ctx), oldNU, (i + 2) >> 1); 417344063Smm ctx->Stats = REF(s); 418344063Smm #ifdef PPMD8_FREEZE_SUPPORT 419344063Smm /* fixed over Shkarin's code. Fixed code is not compatible with original code for some files in FREEZE mode. */ 420344063Smm scale |= (ctx->SummFreq >= ((UInt32)1 << 15)); 421344063Smm #endif 422344063Smm flags = (ctx->Flags & (0x10 + 0x04 * scale)) + 0x08 * (s->Symbol >= 0x40); 423344063Smm escFreq = ctx->SummFreq - s->Freq; 424344063Smm sumFreq = (s->Freq = (Byte)((s->Freq + scale) >> scale)); 425344063Smm do 426344063Smm { 427344063Smm escFreq -= (++s)->Freq; 428344063Smm sumFreq += (s->Freq = (Byte)((s->Freq + scale) >> scale)); 429344063Smm flags |= 0x08 * (s->Symbol >= 0x40); 430344063Smm } 431344063Smm while (--i); 432344063Smm ctx->SummFreq = (UInt16)(sumFreq + ((escFreq + scale) >> scale)); 433344063Smm ctx->Flags = (Byte)flags; 434344063Smm} 435344063Smm 436344063Smmstatic void SwapStates(CPpmd_State *t1, CPpmd_State *t2) 437344063Smm{ 438344063Smm CPpmd_State tmp = *t1; 439344063Smm *t1 = *t2; 440344063Smm *t2 = tmp; 441344063Smm} 442344063Smm 443344063Smmstatic CPpmd_Void_Ref CutOff(CPpmd8 *p, CTX_PTR ctx, unsigned order) 444344063Smm{ 445344063Smm int i; 446344063Smm unsigned tmp; 447344063Smm CPpmd_State *s; 448344063Smm 449344063Smm if (!ctx->NumStats) 450344063Smm { 451344063Smm s = ONE_STATE(ctx); 452344063Smm if ((Byte *)Ppmd8_GetPtr(p, SUCCESSOR(s)) >= p->UnitsStart) 453344063Smm { 454344063Smm if (order < p->MaxOrder) 455344063Smm SetSuccessor(s, CutOff(p, CTX(SUCCESSOR(s)), order + 1)); 456344063Smm else 457344063Smm SetSuccessor(s, 0); 458344063Smm if (SUCCESSOR(s) || order <= 9) /* O_BOUND */ 459344063Smm return REF(ctx); 460344063Smm } 461344063Smm SpecialFreeUnit(p, ctx); 462344063Smm return 0; 463344063Smm } 464344063Smm 465344063Smm ctx->Stats = STATS_REF(MoveUnitsUp(p, STATS(ctx), tmp = ((unsigned)ctx->NumStats + 2) >> 1)); 466344063Smm 467344063Smm for (s = STATS(ctx) + (i = ctx->NumStats); s >= STATS(ctx); s--) 468344063Smm if ((Byte *)Ppmd8_GetPtr(p, SUCCESSOR(s)) < p->UnitsStart) 469344063Smm { 470344063Smm CPpmd_State *s2 = STATS(ctx) + (i--); 471344063Smm SetSuccessor(s, 0); 472344063Smm SwapStates(s, s2); 473344063Smm } 474344063Smm else if (order < p->MaxOrder) 475344063Smm SetSuccessor(s, CutOff(p, CTX(SUCCESSOR(s)), order + 1)); 476344063Smm else 477344063Smm SetSuccessor(s, 0); 478344063Smm 479344063Smm if (i != ctx->NumStats && order) 480344063Smm { 481344063Smm ctx->NumStats = (Byte)i; 482344063Smm s = STATS(ctx); 483344063Smm if (i < 0) 484344063Smm { 485344063Smm FreeUnits(p, s, tmp); 486344063Smm SpecialFreeUnit(p, ctx); 487344063Smm return 0; 488344063Smm } 489344063Smm if (i == 0) 490344063Smm { 491344063Smm ctx->Flags = (Byte)((ctx->Flags & 0x10) + 0x08 * (s->Symbol >= 0x40)); 492344063Smm *ONE_STATE(ctx) = *s; 493344063Smm FreeUnits(p, s, tmp); 494344063Smm /* 9.31: the code was fixed. It's was not BUG, if Freq <= MAX_FREQ = 124 */ 495344063Smm ONE_STATE(ctx)->Freq = (Byte)(((unsigned)ONE_STATE(ctx)->Freq + 11) >> 3); 496344063Smm } 497344063Smm else 498344063Smm Refresh(p, ctx, tmp, ctx->SummFreq > 16 * i); 499344063Smm } 500344063Smm return REF(ctx); 501344063Smm} 502344063Smm 503344063Smm#ifdef PPMD8_FREEZE_SUPPORT 504344063Smmstatic CPpmd_Void_Ref RemoveBinContexts(CPpmd8 *p, CTX_PTR ctx, unsigned order) 505344063Smm{ 506344063Smm CPpmd_State *s; 507344063Smm if (!ctx->NumStats) 508344063Smm { 509344063Smm s = ONE_STATE(ctx); 510344063Smm if ((Byte *)Ppmd8_GetPtr(p, SUCCESSOR(s)) >= p->UnitsStart && order < p->MaxOrder) 511344063Smm SetSuccessor(s, RemoveBinContexts(p, CTX(SUCCESSOR(s)), order + 1)); 512344063Smm else 513344063Smm SetSuccessor(s, 0); 514344063Smm /* Suffix context can be removed already, since different (high-order) 515344063Smm Successors may refer to same context. So we check Flags == 0xFF (Stamp == EMPTY_NODE) */ 516344063Smm if (!SUCCESSOR(s) && (!SUFFIX(ctx)->NumStats || SUFFIX(ctx)->Flags == 0xFF)) 517344063Smm { 518344063Smm FreeUnits(p, ctx, 1); 519344063Smm return 0; 520344063Smm } 521344063Smm else 522344063Smm return REF(ctx); 523344063Smm } 524344063Smm 525344063Smm for (s = STATS(ctx) + ctx->NumStats; s >= STATS(ctx); s--) 526344063Smm if ((Byte *)Ppmd8_GetPtr(p, SUCCESSOR(s)) >= p->UnitsStart && order < p->MaxOrder) 527344063Smm SetSuccessor(s, RemoveBinContexts(p, CTX(SUCCESSOR(s)), order + 1)); 528344063Smm else 529344063Smm SetSuccessor(s, 0); 530344063Smm 531344063Smm return REF(ctx); 532344063Smm} 533344063Smm#endif 534344063Smm 535344063Smmstatic UInt32 GetUsedMemory(const CPpmd8 *p) 536344063Smm{ 537344063Smm UInt32 v = 0; 538344063Smm unsigned i; 539344063Smm for (i = 0; i < PPMD_NUM_INDEXES; i++) 540344063Smm v += p->Stamps[i] * I2U(i); 541344063Smm return p->Size - (UInt32)(p->HiUnit - p->LoUnit) - (UInt32)(p->UnitsStart - p->Text) - U2B(v); 542344063Smm} 543344063Smm 544344063Smm#ifdef PPMD8_FREEZE_SUPPORT 545344063Smm #define RESTORE_MODEL(c1, fSuccessor) RestoreModel(p, c1, fSuccessor) 546344063Smm#else 547344063Smm #define RESTORE_MODEL(c1, fSuccessor) RestoreModel(p, c1) 548344063Smm#endif 549344063Smm 550344063Smmstatic void RestoreModel(CPpmd8 *p, CTX_PTR c1 551344063Smm #ifdef PPMD8_FREEZE_SUPPORT 552344063Smm , CTX_PTR fSuccessor 553344063Smm #endif 554344063Smm ) 555344063Smm{ 556344063Smm CTX_PTR c; 557344063Smm CPpmd_State *s; 558344063Smm RESET_TEXT(0); 559344063Smm for (c = p->MaxContext; c != c1; c = SUFFIX(c)) 560344063Smm if (--(c->NumStats) == 0) 561344063Smm { 562344063Smm s = STATS(c); 563344063Smm c->Flags = (Byte)((c->Flags & 0x10) + 0x08 * (s->Symbol >= 0x40)); 564344063Smm *ONE_STATE(c) = *s; 565344063Smm SpecialFreeUnit(p, s); 566344063Smm ONE_STATE(c)->Freq = (Byte)(((unsigned)ONE_STATE(c)->Freq + 11) >> 3); 567344063Smm } 568344063Smm else 569344063Smm Refresh(p, c, (c->NumStats+3) >> 1, 0); 570344063Smm 571344063Smm for (; c != p->MinContext; c = SUFFIX(c)) 572344063Smm if (!c->NumStats) 573344063Smm ONE_STATE(c)->Freq = (Byte)(ONE_STATE(c)->Freq - (ONE_STATE(c)->Freq >> 1)); 574344063Smm else if ((c->SummFreq += 4) > 128 + 4 * c->NumStats) 575344063Smm Refresh(p, c, (c->NumStats + 2) >> 1, 1); 576344063Smm 577344063Smm #ifdef PPMD8_FREEZE_SUPPORT 578344063Smm if (p->RestoreMethod > PPMD8_RESTORE_METHOD_FREEZE) 579344063Smm { 580344063Smm p->MaxContext = fSuccessor; 581344063Smm p->GlueCount += !(p->Stamps[1] & 1); 582344063Smm } 583344063Smm else if (p->RestoreMethod == PPMD8_RESTORE_METHOD_FREEZE) 584344063Smm { 585344063Smm while (p->MaxContext->Suffix) 586344063Smm p->MaxContext = SUFFIX(p->MaxContext); 587344063Smm RemoveBinContexts(p, p->MaxContext, 0); 588344063Smm p->RestoreMethod++; 589344063Smm p->GlueCount = 0; 590344063Smm p->OrderFall = p->MaxOrder; 591344063Smm } 592344063Smm else 593344063Smm #endif 594344063Smm if (p->RestoreMethod == PPMD8_RESTORE_METHOD_RESTART || GetUsedMemory(p) < (p->Size >> 1)) 595344063Smm RestartModel(p); 596344063Smm else 597344063Smm { 598344063Smm while (p->MaxContext->Suffix) 599344063Smm p->MaxContext = SUFFIX(p->MaxContext); 600344063Smm do 601344063Smm { 602344063Smm CutOff(p, p->MaxContext, 0); 603344063Smm ExpandTextArea(p); 604344063Smm } 605344063Smm while (GetUsedMemory(p) > 3 * (p->Size >> 2)); 606344063Smm p->GlueCount = 0; 607344063Smm p->OrderFall = p->MaxOrder; 608344063Smm } 609344063Smm} 610344063Smm 611344063Smmstatic CTX_PTR CreateSuccessors(CPpmd8 *p, Bool skip, CPpmd_State *s1, CTX_PTR c) 612344063Smm{ 613344063Smm CPpmd_State upState; 614344063Smm Byte flags; 615344063Smm CPpmd_Byte_Ref upBranch = (CPpmd_Byte_Ref)SUCCESSOR(p->FoundState); 616344063Smm /* fixed over Shkarin's code. Maybe it could work without + 1 too. */ 617344063Smm CPpmd_State *ps[PPMD8_MAX_ORDER + 1]; 618344063Smm unsigned numPs = 0; 619344063Smm 620344063Smm if (!skip) 621344063Smm ps[numPs++] = p->FoundState; 622344063Smm 623344063Smm while (c->Suffix) 624344063Smm { 625344063Smm CPpmd_Void_Ref successor; 626344063Smm CPpmd_State *s; 627344063Smm c = SUFFIX(c); 628344063Smm if (s1) 629344063Smm { 630344063Smm s = s1; 631344063Smm s1 = NULL; 632344063Smm } 633344063Smm else if (c->NumStats != 0) 634344063Smm { 635344063Smm for (s = STATS(c); s->Symbol != p->FoundState->Symbol; s++); 636344063Smm if (s->Freq < MAX_FREQ - 9) 637344063Smm { 638344063Smm s->Freq++; 639344063Smm c->SummFreq++; 640344063Smm } 641344063Smm } 642344063Smm else 643344063Smm { 644344063Smm s = ONE_STATE(c); 645344063Smm s->Freq = (Byte)(s->Freq + (!SUFFIX(c)->NumStats & (s->Freq < 24))); 646344063Smm } 647344063Smm successor = SUCCESSOR(s); 648344063Smm if (successor != upBranch) 649344063Smm { 650344063Smm c = CTX(successor); 651344063Smm if (numPs == 0) 652344063Smm return c; 653344063Smm break; 654344063Smm } 655344063Smm ps[numPs++] = s; 656344063Smm } 657344063Smm 658344063Smm upState.Symbol = *(const Byte *)Ppmd8_GetPtr(p, upBranch); 659344063Smm SetSuccessor(&upState, upBranch + 1); 660344063Smm flags = (Byte)(0x10 * (p->FoundState->Symbol >= 0x40) + 0x08 * (upState.Symbol >= 0x40)); 661344063Smm 662344063Smm if (c->NumStats == 0) 663344063Smm upState.Freq = ONE_STATE(c)->Freq; 664344063Smm else 665344063Smm { 666344063Smm UInt32 cf, s0; 667344063Smm CPpmd_State *s; 668344063Smm for (s = STATS(c); s->Symbol != upState.Symbol; s++); 669344063Smm cf = s->Freq - 1; 670344063Smm s0 = c->SummFreq - c->NumStats - cf; 671344063Smm upState.Freq = (Byte)(1 + ((2 * cf <= s0) ? (5 * cf > s0) : ((cf + 2 * s0 - 3) / s0))); 672344063Smm } 673344063Smm 674344063Smm do 675344063Smm { 676344063Smm /* Create Child */ 677344063Smm CTX_PTR c1; /* = AllocContext(p); */ 678344063Smm if (p->HiUnit != p->LoUnit) 679344063Smm c1 = (CTX_PTR)(p->HiUnit -= UNIT_SIZE); 680344063Smm else if (p->FreeList[0] != 0) 681344063Smm c1 = (CTX_PTR)RemoveNode(p, 0); 682344063Smm else 683344063Smm { 684344063Smm c1 = (CTX_PTR)AllocUnitsRare(p, 0); 685344063Smm if (!c1) 686344063Smm return NULL; 687344063Smm } 688344063Smm c1->NumStats = 0; 689344063Smm c1->Flags = flags; 690344063Smm *ONE_STATE(c1) = upState; 691344063Smm c1->Suffix = REF(c); 692344063Smm SetSuccessor(ps[--numPs], REF(c1)); 693344063Smm c = c1; 694344063Smm } 695344063Smm while (numPs != 0); 696344063Smm 697344063Smm return c; 698344063Smm} 699344063Smm 700344063Smmstatic CTX_PTR ReduceOrder(CPpmd8 *p, CPpmd_State *s1, CTX_PTR c) 701344063Smm{ 702344063Smm CPpmd_State *s = NULL; 703344063Smm CTX_PTR c1 = c; 704344063Smm CPpmd_Void_Ref upBranch = REF(p->Text); 705344063Smm 706344063Smm #ifdef PPMD8_FREEZE_SUPPORT 707344063Smm /* The BUG in Shkarin's code was fixed: ps could overflow in CUT_OFF mode. */ 708344063Smm CPpmd_State *ps[PPMD8_MAX_ORDER + 1]; 709344063Smm unsigned numPs = 0; 710344063Smm ps[numPs++] = p->FoundState; 711344063Smm #endif 712344063Smm 713344063Smm SetSuccessor(p->FoundState, upBranch); 714344063Smm p->OrderFall++; 715344063Smm 716344063Smm for (;;) 717344063Smm { 718344063Smm if (s1) 719344063Smm { 720344063Smm c = SUFFIX(c); 721344063Smm s = s1; 722344063Smm s1 = NULL; 723344063Smm } 724344063Smm else 725344063Smm { 726344063Smm if (!c->Suffix) 727344063Smm { 728344063Smm #ifdef PPMD8_FREEZE_SUPPORT 729344063Smm if (p->RestoreMethod > PPMD8_RESTORE_METHOD_FREEZE) 730344063Smm { 731344063Smm do { SetSuccessor(ps[--numPs], REF(c)); } while (numPs); 732344063Smm RESET_TEXT(1); 733344063Smm p->OrderFall = 1; 734344063Smm } 735344063Smm #endif 736344063Smm return c; 737344063Smm } 738344063Smm c = SUFFIX(c); 739344063Smm if (c->NumStats) 740344063Smm { 741344063Smm if ((s = STATS(c))->Symbol != p->FoundState->Symbol) 742344063Smm do { s++; } while (s->Symbol != p->FoundState->Symbol); 743344063Smm if (s->Freq < MAX_FREQ - 9) 744344063Smm { 745344063Smm s->Freq += 2; 746344063Smm c->SummFreq += 2; 747344063Smm } 748344063Smm } 749344063Smm else 750344063Smm { 751344063Smm s = ONE_STATE(c); 752344063Smm s->Freq = (Byte)(s->Freq + (s->Freq < 32)); 753344063Smm } 754344063Smm } 755344063Smm if (SUCCESSOR(s)) 756344063Smm break; 757344063Smm #ifdef PPMD8_FREEZE_SUPPORT 758344063Smm ps[numPs++] = s; 759344063Smm #endif 760344063Smm SetSuccessor(s, upBranch); 761344063Smm p->OrderFall++; 762344063Smm } 763344063Smm 764344063Smm #ifdef PPMD8_FREEZE_SUPPORT 765344063Smm if (p->RestoreMethod > PPMD8_RESTORE_METHOD_FREEZE) 766344063Smm { 767344063Smm c = CTX(SUCCESSOR(s)); 768344063Smm do { SetSuccessor(ps[--numPs], REF(c)); } while (numPs); 769344063Smm RESET_TEXT(1); 770344063Smm p->OrderFall = 1; 771344063Smm return c; 772344063Smm } 773344063Smm else 774344063Smm #endif 775344063Smm if (SUCCESSOR(s) <= upBranch) 776344063Smm { 777344063Smm CTX_PTR successor; 778344063Smm CPpmd_State *s2 = p->FoundState; 779344063Smm p->FoundState = s; 780344063Smm 781344063Smm successor = CreateSuccessors(p, False, NULL, c); 782344063Smm if (successor == NULL) 783344063Smm SetSuccessor(s, 0); 784344063Smm else 785344063Smm SetSuccessor(s, REF(successor)); 786344063Smm p->FoundState = s2; 787344063Smm } 788344063Smm 789344063Smm if (p->OrderFall == 1 && c1 == p->MaxContext) 790344063Smm { 791344063Smm SetSuccessor(p->FoundState, SUCCESSOR(s)); 792344063Smm p->Text--; 793344063Smm } 794344063Smm if (SUCCESSOR(s) == 0) 795344063Smm return NULL; 796344063Smm return CTX(SUCCESSOR(s)); 797344063Smm} 798344063Smm 799344063Smmstatic void UpdateModel(CPpmd8 *p) 800344063Smm{ 801344063Smm CPpmd_Void_Ref successor, fSuccessor = SUCCESSOR(p->FoundState); 802344063Smm CTX_PTR c; 803344063Smm unsigned s0, ns, fFreq = p->FoundState->Freq; 804344063Smm Byte flag, fSymbol = p->FoundState->Symbol; 805344063Smm CPpmd_State *s = NULL; 806344063Smm 807344063Smm if (p->FoundState->Freq < MAX_FREQ / 4 && p->MinContext->Suffix != 0) 808344063Smm { 809344063Smm c = SUFFIX(p->MinContext); 810344063Smm 811344063Smm if (c->NumStats == 0) 812344063Smm { 813344063Smm s = ONE_STATE(c); 814344063Smm if (s->Freq < 32) 815344063Smm s->Freq++; 816344063Smm } 817344063Smm else 818344063Smm { 819344063Smm s = STATS(c); 820344063Smm if (s->Symbol != p->FoundState->Symbol) 821344063Smm { 822344063Smm do { s++; } while (s->Symbol != p->FoundState->Symbol); 823344063Smm if (s[0].Freq >= s[-1].Freq) 824344063Smm { 825344063Smm SwapStates(&s[0], &s[-1]); 826344063Smm s--; 827344063Smm } 828344063Smm } 829344063Smm if (s->Freq < MAX_FREQ - 9) 830344063Smm { 831344063Smm s->Freq += 2; 832344063Smm c->SummFreq += 2; 833344063Smm } 834344063Smm } 835344063Smm } 836344063Smm 837344063Smm c = p->MaxContext; 838344063Smm if (p->OrderFall == 0 && fSuccessor) 839344063Smm { 840344063Smm CTX_PTR cs = CreateSuccessors(p, True, s, p->MinContext); 841344063Smm if (cs == 0) 842344063Smm { 843344063Smm SetSuccessor(p->FoundState, 0); 844344063Smm RESTORE_MODEL(c, CTX(fSuccessor)); 845344063Smm } 846344063Smm else 847344063Smm { 848344063Smm SetSuccessor(p->FoundState, REF(cs)); 849344063Smm p->MaxContext = cs; 850344063Smm } 851344063Smm return; 852344063Smm } 853344063Smm 854344063Smm *p->Text++ = p->FoundState->Symbol; 855344063Smm successor = REF(p->Text); 856344063Smm if (p->Text >= p->UnitsStart) 857344063Smm { 858344063Smm RESTORE_MODEL(c, CTX(fSuccessor)); /* check it */ 859344063Smm return; 860344063Smm } 861344063Smm 862344063Smm if (!fSuccessor) 863344063Smm { 864344063Smm CTX_PTR cs = ReduceOrder(p, s, p->MinContext); 865344063Smm if (cs == NULL) 866344063Smm { 867344063Smm RESTORE_MODEL(c, 0); 868344063Smm return; 869344063Smm } 870344063Smm fSuccessor = REF(cs); 871344063Smm } 872344063Smm else if ((Byte *)Ppmd8_GetPtr(p, fSuccessor) < p->UnitsStart) 873344063Smm { 874344063Smm CTX_PTR cs = CreateSuccessors(p, False, s, p->MinContext); 875344063Smm if (cs == NULL) 876344063Smm { 877344063Smm RESTORE_MODEL(c, 0); 878344063Smm return; 879344063Smm } 880344063Smm fSuccessor = REF(cs); 881344063Smm } 882344063Smm 883344063Smm if (--p->OrderFall == 0) 884344063Smm { 885344063Smm successor = fSuccessor; 886344063Smm p->Text -= (p->MaxContext != p->MinContext); 887344063Smm } 888344063Smm #ifdef PPMD8_FREEZE_SUPPORT 889344063Smm else if (p->RestoreMethod > PPMD8_RESTORE_METHOD_FREEZE) 890344063Smm { 891344063Smm successor = fSuccessor; 892344063Smm RESET_TEXT(0); 893344063Smm p->OrderFall = 0; 894344063Smm } 895344063Smm #endif 896344063Smm 897344063Smm s0 = p->MinContext->SummFreq - (ns = p->MinContext->NumStats) - fFreq; 898344063Smm flag = (Byte)(0x08 * (fSymbol >= 0x40)); 899344063Smm 900344063Smm for (; c != p->MinContext; c = SUFFIX(c)) 901344063Smm { 902344063Smm unsigned ns1; 903344063Smm UInt32 cf, sf; 904344063Smm if ((ns1 = c->NumStats) != 0) 905344063Smm { 906344063Smm if ((ns1 & 1) != 0) 907344063Smm { 908344063Smm /* Expand for one UNIT */ 909344063Smm unsigned oldNU = (ns1 + 1) >> 1; 910344063Smm unsigned i = U2I(oldNU); 911344063Smm if (i != U2I(oldNU + 1)) 912344063Smm { 913344063Smm void *ptr = AllocUnits(p, i + 1); 914344063Smm void *oldPtr; 915344063Smm if (!ptr) 916344063Smm { 917344063Smm RESTORE_MODEL(c, CTX(fSuccessor)); 918344063Smm return; 919344063Smm } 920344063Smm oldPtr = STATS(c); 921344063Smm MyMem12Cpy(ptr, oldPtr, oldNU); 922344063Smm InsertNode(p, oldPtr, i); 923344063Smm c->Stats = STATS_REF(ptr); 924344063Smm } 925344063Smm } 926344063Smm c->SummFreq = (UInt16)(c->SummFreq + (3 * ns1 + 1 < ns)); 927344063Smm } 928344063Smm else 929344063Smm { 930344063Smm CPpmd_State *s2 = (CPpmd_State*)AllocUnits(p, 0); 931344063Smm if (!s2) 932344063Smm { 933344063Smm RESTORE_MODEL(c, CTX(fSuccessor)); 934344063Smm return; 935344063Smm } 936344063Smm *s2 = *ONE_STATE(c); 937344063Smm c->Stats = REF(s2); 938344063Smm if (s2->Freq < MAX_FREQ / 4 - 1) 939344063Smm s2->Freq <<= 1; 940344063Smm else 941344063Smm s2->Freq = MAX_FREQ - 4; 942344063Smm c->SummFreq = (UInt16)(s2->Freq + p->InitEsc + (ns > 2)); 943344063Smm } 944344063Smm cf = 2 * fFreq * (c->SummFreq + 6); 945344063Smm sf = (UInt32)s0 + c->SummFreq; 946344063Smm if (cf < 6 * sf) 947344063Smm { 948344063Smm cf = 1 + (cf > sf) + (cf >= 4 * sf); 949344063Smm c->SummFreq += 4; 950344063Smm } 951344063Smm else 952344063Smm { 953344063Smm cf = 4 + (cf > 9 * sf) + (cf > 12 * sf) + (cf > 15 * sf); 954344063Smm c->SummFreq = (UInt16)(c->SummFreq + cf); 955344063Smm } 956344063Smm { 957344063Smm CPpmd_State *s2 = STATS(c) + ns1 + 1; 958344063Smm SetSuccessor(s2, successor); 959344063Smm s2->Symbol = fSymbol; 960344063Smm s2->Freq = (Byte)cf; 961344063Smm c->Flags |= flag; 962344063Smm c->NumStats = (Byte)(ns1 + 1); 963344063Smm } 964344063Smm } 965344063Smm p->MaxContext = p->MinContext = CTX(fSuccessor); 966344063Smm} 967344063Smm 968344063Smmstatic void Rescale(CPpmd8 *p) 969344063Smm{ 970344063Smm unsigned i, adder, sumFreq, escFreq; 971344063Smm CPpmd_State *stats = STATS(p->MinContext); 972344063Smm CPpmd_State *s = p->FoundState; 973344063Smm { 974344063Smm CPpmd_State tmp = *s; 975344063Smm for (; s != stats; s--) 976344063Smm s[0] = s[-1]; 977344063Smm *s = tmp; 978344063Smm } 979344063Smm escFreq = p->MinContext->SummFreq - s->Freq; 980344063Smm s->Freq += 4; 981344063Smm adder = (p->OrderFall != 0 982344063Smm #ifdef PPMD8_FREEZE_SUPPORT 983344063Smm || p->RestoreMethod > PPMD8_RESTORE_METHOD_FREEZE 984344063Smm #endif 985344063Smm ); 986344063Smm s->Freq = (Byte)((s->Freq + adder) >> 1); 987344063Smm sumFreq = s->Freq; 988344063Smm 989344063Smm i = p->MinContext->NumStats; 990344063Smm do 991344063Smm { 992344063Smm escFreq -= (++s)->Freq; 993344063Smm s->Freq = (Byte)((s->Freq + adder) >> 1); 994344063Smm sumFreq += s->Freq; 995344063Smm if (s[0].Freq > s[-1].Freq) 996344063Smm { 997344063Smm CPpmd_State *s1 = s; 998344063Smm CPpmd_State tmp = *s1; 999344063Smm do 1000344063Smm s1[0] = s1[-1]; 1001344063Smm while (--s1 != stats && tmp.Freq > s1[-1].Freq); 1002344063Smm *s1 = tmp; 1003344063Smm } 1004344063Smm } 1005344063Smm while (--i); 1006344063Smm 1007344063Smm if (s->Freq == 0) 1008344063Smm { 1009344063Smm unsigned numStats = p->MinContext->NumStats; 1010344063Smm unsigned n0, n1; 1011344063Smm do { i++; } while ((--s)->Freq == 0); 1012344063Smm escFreq += i; 1013344063Smm p->MinContext->NumStats = (Byte)(p->MinContext->NumStats - i); 1014344063Smm if (p->MinContext->NumStats == 0) 1015344063Smm { 1016344063Smm CPpmd_State tmp = *stats; 1017344063Smm tmp.Freq = (Byte)((2 * tmp.Freq + escFreq - 1) / escFreq); 1018344063Smm if (tmp.Freq > MAX_FREQ / 3) 1019344063Smm tmp.Freq = MAX_FREQ / 3; 1020344063Smm InsertNode(p, stats, U2I((numStats + 2) >> 1)); 1021344063Smm p->MinContext->Flags = (Byte)((p->MinContext->Flags & 0x10) + 0x08 * (tmp.Symbol >= 0x40)); 1022344063Smm *(p->FoundState = ONE_STATE(p->MinContext)) = tmp; 1023344063Smm return; 1024344063Smm } 1025344063Smm n0 = (numStats + 2) >> 1; 1026344063Smm n1 = (p->MinContext->NumStats + 2) >> 1; 1027344063Smm if (n0 != n1) 1028344063Smm p->MinContext->Stats = STATS_REF(ShrinkUnits(p, stats, n0, n1)); 1029344063Smm p->MinContext->Flags &= ~0x08; 1030344063Smm p->MinContext->Flags |= 0x08 * ((s = STATS(p->MinContext))->Symbol >= 0x40); 1031344063Smm i = p->MinContext->NumStats; 1032344063Smm do { p->MinContext->Flags |= 0x08*((++s)->Symbol >= 0x40); } while (--i); 1033344063Smm } 1034344063Smm p->MinContext->SummFreq = (UInt16)(sumFreq + escFreq - (escFreq >> 1)); 1035344063Smm p->MinContext->Flags |= 0x4; 1036344063Smm p->FoundState = STATS(p->MinContext); 1037344063Smm} 1038344063Smm 1039344063SmmCPpmd_See *Ppmd8_MakeEscFreq(CPpmd8 *p, unsigned numMasked1, UInt32 *escFreq) 1040344063Smm{ 1041344063Smm CPpmd_See *see; 1042344063Smm if (p->MinContext->NumStats != 0xFF) 1043344063Smm { 1044344063Smm see = p->See[(unsigned)p->NS2Indx[(unsigned)p->MinContext->NumStats + 2] - 3] + 1045344063Smm (p->MinContext->SummFreq > 11 * ((unsigned)p->MinContext->NumStats + 1)) + 1046344063Smm 2 * (unsigned)(2 * (unsigned)p->MinContext->NumStats < 1047344063Smm ((unsigned)SUFFIX(p->MinContext)->NumStats + numMasked1)) + 1048344063Smm p->MinContext->Flags; 1049344063Smm { 1050344063Smm unsigned r = (see->Summ >> see->Shift); 1051344063Smm see->Summ = (UInt16)(see->Summ - r); 1052344063Smm *escFreq = r + (r == 0); 1053344063Smm } 1054344063Smm } 1055344063Smm else 1056344063Smm { 1057344063Smm see = &p->DummySee; 1058344063Smm *escFreq = 1; 1059344063Smm } 1060344063Smm return see; 1061344063Smm} 1062344063Smm 1063344063Smmstatic void NextContext(CPpmd8 *p) 1064344063Smm{ 1065344063Smm CTX_PTR c = CTX(SUCCESSOR(p->FoundState)); 1066344063Smm if (p->OrderFall == 0 && (Byte *)c >= p->UnitsStart) 1067344063Smm p->MinContext = p->MaxContext = c; 1068344063Smm else 1069344063Smm { 1070344063Smm UpdateModel(p); 1071344063Smm p->MinContext = p->MaxContext; 1072344063Smm } 1073344063Smm} 1074344063Smm 1075344063Smmvoid Ppmd8_Update1(CPpmd8 *p) 1076344063Smm{ 1077344063Smm CPpmd_State *s = p->FoundState; 1078344063Smm s->Freq += 4; 1079344063Smm p->MinContext->SummFreq += 4; 1080344063Smm if (s[0].Freq > s[-1].Freq) 1081344063Smm { 1082344063Smm SwapStates(&s[0], &s[-1]); 1083344063Smm p->FoundState = --s; 1084344063Smm if (s->Freq > MAX_FREQ) 1085344063Smm Rescale(p); 1086344063Smm } 1087344063Smm NextContext(p); 1088344063Smm} 1089344063Smm 1090344063Smmvoid Ppmd8_Update1_0(CPpmd8 *p) 1091344063Smm{ 1092344063Smm p->PrevSuccess = (2 * p->FoundState->Freq >= p->MinContext->SummFreq); 1093344063Smm p->RunLength += p->PrevSuccess; 1094344063Smm p->MinContext->SummFreq += 4; 1095344063Smm if ((p->FoundState->Freq += 4) > MAX_FREQ) 1096344063Smm Rescale(p); 1097344063Smm NextContext(p); 1098344063Smm} 1099344063Smm 1100344063Smmvoid Ppmd8_UpdateBin(CPpmd8 *p) 1101344063Smm{ 1102344063Smm p->FoundState->Freq = (Byte)(p->FoundState->Freq + (p->FoundState->Freq < 196)); 1103344063Smm p->PrevSuccess = 1; 1104344063Smm p->RunLength++; 1105344063Smm NextContext(p); 1106344063Smm} 1107344063Smm 1108344063Smmvoid Ppmd8_Update2(CPpmd8 *p) 1109344063Smm{ 1110344063Smm p->MinContext->SummFreq += 4; 1111344063Smm if ((p->FoundState->Freq += 4) > MAX_FREQ) 1112344063Smm Rescale(p); 1113344063Smm p->RunLength = p->InitRL; 1114344063Smm UpdateModel(p); 1115344063Smm p->MinContext = p->MaxContext; 1116344063Smm} 1117344063Smm 1118344063Smm/* Ppmd8Dec.c -- PPMdI Decoder 1119344063Smm2010-04-16 : Igor Pavlov : Public domain 1120344063SmmThis code is based on: 1121344063Smm PPMd var.I (2002): Dmitry Shkarin : Public domain 1122344063Smm Carryless rangecoder (1999): Dmitry Subbotin : Public domain */ 1123344063Smm 1124344063SmmBool Ppmd8_RangeDec_Init(CPpmd8 *p) 1125344063Smm{ 1126344063Smm unsigned i; 1127344063Smm p->Low = 0; 1128344063Smm p->Range = 0xFFFFFFFF; 1129344063Smm p->Code = 0; 1130344063Smm for (i = 0; i < 4; i++) 1131344063Smm p->Code = (p->Code << 8) | p->Stream.In->Read(p->Stream.In); 1132344063Smm return (p->Code < 0xFFFFFFFF); 1133344063Smm} 1134344063Smm 1135344063Smmstatic UInt32 RangeDec_GetThreshold(CPpmd8 *p, UInt32 total) 1136344063Smm{ 1137344063Smm return p->Code / (p->Range /= total); 1138344063Smm} 1139344063Smm 1140344063Smmstatic void RangeDec_Decode(CPpmd8 *p, UInt32 start, UInt32 size) 1141344063Smm{ 1142344063Smm start *= p->Range; 1143344063Smm p->Low += start; 1144344063Smm p->Code -= start; 1145344063Smm p->Range *= size; 1146344063Smm 1147344063Smm while ((p->Low ^ (p->Low + p->Range)) < kTop || 1148344063Smm (p->Range < kBot && ((p->Range = (0 - p->Low) & (kBot - 1)), 1))) 1149344063Smm { 1150344063Smm p->Code = (p->Code << 8) | p->Stream.In->Read(p->Stream.In); 1151344063Smm p->Range <<= 8; 1152344063Smm p->Low <<= 8; 1153344063Smm } 1154344063Smm} 1155344063Smm 1156344063Smm#define MASK(sym) ((signed char *)charMask)[sym] 1157344063Smm 1158344063Smmint Ppmd8_DecodeSymbol(CPpmd8 *p) 1159344063Smm{ 1160344063Smm size_t charMask[256 / sizeof(size_t)]; 1161344063Smm if (p->MinContext->NumStats != 0) 1162344063Smm { 1163344063Smm CPpmd_State *s = Ppmd8_GetStats(p, p->MinContext); 1164344063Smm unsigned i; 1165344063Smm UInt32 count, hiCnt; 1166344063Smm if ((count = RangeDec_GetThreshold(p, p->MinContext->SummFreq)) < (hiCnt = s->Freq)) 1167344063Smm { 1168344063Smm Byte symbol; 1169344063Smm RangeDec_Decode(p, 0, s->Freq); 1170344063Smm p->FoundState = s; 1171344063Smm symbol = s->Symbol; 1172344063Smm Ppmd8_Update1_0(p); 1173344063Smm return symbol; 1174344063Smm } 1175344063Smm p->PrevSuccess = 0; 1176344063Smm i = p->MinContext->NumStats; 1177344063Smm do 1178344063Smm { 1179344063Smm if ((hiCnt += (++s)->Freq) > count) 1180344063Smm { 1181344063Smm Byte symbol; 1182344063Smm RangeDec_Decode(p, hiCnt - s->Freq, s->Freq); 1183344063Smm p->FoundState = s; 1184344063Smm symbol = s->Symbol; 1185344063Smm Ppmd8_Update1(p); 1186344063Smm return symbol; 1187344063Smm } 1188344063Smm } 1189344063Smm while (--i); 1190344063Smm if (count >= p->MinContext->SummFreq) 1191344063Smm return -2; 1192344063Smm RangeDec_Decode(p, hiCnt, p->MinContext->SummFreq - hiCnt); 1193344063Smm PPMD_SetAllBitsIn256Bytes(charMask); 1194344063Smm MASK(s->Symbol) = 0; 1195344063Smm i = p->MinContext->NumStats; 1196344063Smm do { MASK((--s)->Symbol) = 0; } while (--i); 1197344063Smm } 1198344063Smm else 1199344063Smm { 1200344063Smm UInt16 *prob = Ppmd8_GetBinSumm(p); 1201344063Smm if (((p->Code / (p->Range >>= 14)) < *prob)) 1202344063Smm { 1203344063Smm Byte symbol; 1204344063Smm RangeDec_Decode(p, 0, *prob); 1205344063Smm *prob = (UInt16)PPMD_UPDATE_PROB_0(*prob); 1206344063Smm symbol = (p->FoundState = Ppmd8Context_OneState(p->MinContext))->Symbol; 1207344063Smm Ppmd8_UpdateBin(p); 1208344063Smm return symbol; 1209344063Smm } 1210344063Smm RangeDec_Decode(p, *prob, (1 << 14) - *prob); 1211344063Smm *prob = (UInt16)PPMD_UPDATE_PROB_1(*prob); 1212344063Smm p->InitEsc = PPMD8_kExpEscape[*prob >> 10]; 1213344063Smm PPMD_SetAllBitsIn256Bytes(charMask); 1214344063Smm MASK(Ppmd8Context_OneState(p->MinContext)->Symbol) = 0; 1215344063Smm p->PrevSuccess = 0; 1216344063Smm } 1217344063Smm for (;;) 1218344063Smm { 1219344063Smm CPpmd_State *ps[256], *s; 1220344063Smm UInt32 freqSum, count, hiCnt; 1221344063Smm CPpmd_See *see; 1222344063Smm unsigned i, num, numMasked = p->MinContext->NumStats; 1223344063Smm do 1224344063Smm { 1225344063Smm p->OrderFall++; 1226344063Smm if (!p->MinContext->Suffix) 1227344063Smm return -1; 1228344063Smm p->MinContext = Ppmd8_GetContext(p, p->MinContext->Suffix); 1229344063Smm } 1230344063Smm while (p->MinContext->NumStats == numMasked); 1231344063Smm hiCnt = 0; 1232344063Smm s = Ppmd8_GetStats(p, p->MinContext); 1233344063Smm i = 0; 1234344063Smm num = p->MinContext->NumStats - numMasked; 1235344063Smm do 1236344063Smm { 1237344063Smm int k = (int)(MASK(s->Symbol)); 1238344063Smm hiCnt += (s->Freq & k); 1239344063Smm ps[i] = s++; 1240344063Smm i -= k; 1241344063Smm } 1242344063Smm while (i != num); 1243344063Smm 1244344063Smm see = Ppmd8_MakeEscFreq(p, numMasked, &freqSum); 1245344063Smm freqSum += hiCnt; 1246344063Smm count = RangeDec_GetThreshold(p, freqSum); 1247344063Smm 1248344063Smm if (count < hiCnt) 1249344063Smm { 1250344063Smm Byte symbol; 1251344063Smm CPpmd_State **pps = ps; 1252344063Smm for (hiCnt = 0; (hiCnt += (*pps)->Freq) <= count; pps++); 1253344063Smm s = *pps; 1254344063Smm RangeDec_Decode(p, hiCnt - s->Freq, s->Freq); 1255344063Smm Ppmd_See_Update(see); 1256344063Smm p->FoundState = s; 1257344063Smm symbol = s->Symbol; 1258344063Smm Ppmd8_Update2(p); 1259344063Smm return symbol; 1260344063Smm } 1261344063Smm if (count >= freqSum) 1262344063Smm return -2; 1263344063Smm RangeDec_Decode(p, hiCnt, freqSum - hiCnt); 1264344063Smm see->Summ = (UInt16)(see->Summ + freqSum); 1265344063Smm do { MASK(ps[--i]->Symbol) = 0; } while (i != 0); 1266344063Smm } 1267344063Smm} 1268344063Smm 1269344063Smm/* H->I changes: 1270344063Smm NS2Indx 1271344063Smm GlewCount, and Glue method 1272344063Smm BinSum 1273344063Smm See / EscFreq 1274344063Smm CreateSuccessors updates more suffix contexts 1275344063Smm UpdateModel consts. 1276344063Smm PrevSuccess Update 1277344063Smm*/ 1278344063Smm 1279344063Smmconst IPpmd8 __archive_ppmd8_functions = 1280344063Smm{ 1281344063Smm &Ppmd8_Construct, 1282344063Smm &Ppmd8_Alloc, 1283344063Smm &Ppmd8_Free, 1284344063Smm &Ppmd8_Init, 1285344063Smm &Ppmd8_RangeDec_Init, 1286344063Smm &Ppmd8_DecodeSymbol, 1287344063Smm}; 1288