1231200Smm/* Ppmd7.c -- PPMdH codec 2231200Smm2010-03-12 : Igor Pavlov : Public domain 3231200SmmThis code is based on PPMd var.H (2001): Dmitry Shkarin : Public domain */ 4231200Smm 5231200Smm#include "archive_platform.h" 6231200Smm 7368707Smm#include <stdlib.h> 8231200Smm 9231200Smm#include "archive_ppmd7_private.h" 10231200Smm 11231200Smm#ifdef PPMD_32BIT 12231200Smm #define Ppmd7_GetPtr(p, ptr) (ptr) 13231200Smm #define Ppmd7_GetContext(p, ptr) (ptr) 14231200Smm #define Ppmd7_GetStats(p, ctx) ((ctx)->Stats) 15231200Smm#else 16231200Smm #define Ppmd7_GetPtr(p, offs) ((void *)((p)->Base + (offs))) 17231200Smm #define Ppmd7_GetContext(p, offs) ((CPpmd7_Context *)Ppmd7_GetPtr((p), (offs))) 18231200Smm #define Ppmd7_GetStats(p, ctx) ((CPpmd_State *)Ppmd7_GetPtr((p), ((ctx)->Stats))) 19231200Smm#endif 20231200Smm 21231200Smm#define Ppmd7_GetBinSumm(p) \ 22231200Smm &p->BinSumm[Ppmd7Context_OneState(p->MinContext)->Freq - 1][p->PrevSuccess + \ 23231200Smm p->NS2BSIndx[Ppmd7_GetContext(p, p->MinContext->Suffix)->NumStats - 1] + \ 24231200Smm (p->HiBitsFlag = p->HB2Flag[p->FoundState->Symbol]) + \ 25231200Smm 2 * p->HB2Flag[Ppmd7Context_OneState(p->MinContext)->Symbol] + \ 26231200Smm ((p->RunLength >> 26) & 0x20)] 27231200Smm 28231200Smm#define kTopValue (1 << 24) 29231200Smm#define MAX_FREQ 124 30231200Smm#define UNIT_SIZE 12 31231200Smm 32231200Smm#define U2B(nu) ((UInt32)(nu) * UNIT_SIZE) 33231200Smm#define U2I(nu) (p->Units2Indx[(nu) - 1]) 34231200Smm#define I2U(indx) (p->Indx2Units[indx]) 35231200Smm 36231200Smm#ifdef PPMD_32BIT 37231200Smm #define REF(ptr) (ptr) 38231200Smm#else 39231200Smm #define REF(ptr) ((UInt32)((Byte *)(ptr) - (p)->Base)) 40231200Smm#endif 41231200Smm 42231200Smm#define STATS_REF(ptr) ((CPpmd_State_Ref)REF(ptr)) 43231200Smm 44231200Smm#define CTX(ref) ((CPpmd7_Context *)Ppmd7_GetContext(p, ref)) 45231200Smm#define STATS(ctx) Ppmd7_GetStats(p, ctx) 46231200Smm#define ONE_STATE(ctx) Ppmd7Context_OneState(ctx) 47231200Smm#define SUFFIX(ctx) CTX((ctx)->Suffix) 48231200Smm 49231200Smmstatic const UInt16 kInitBinEsc[] = { 0x3CDD, 0x1F3F, 0x59BF, 0x48F3, 0x64A1, 0x5ABC, 0x6632, 0x6051}; 50231200Smmstatic const Byte PPMD7_kExpEscape[16] = { 25, 14, 9, 7, 5, 5, 4, 4, 4, 3, 3, 3, 2, 2, 2, 2 }; 51231200Smm 52231200Smmtypedef CPpmd7_Context * CTX_PTR; 53231200Smm 54231200Smmstruct CPpmd7_Node_; 55231200Smm 56231200Smmtypedef 57231200Smm #ifdef PPMD_32BIT 58231200Smm struct CPpmd7_Node_ * 59231200Smm #else 60231200Smm UInt32 61231200Smm #endif 62231200Smm CPpmd7_Node_Ref; 63231200Smm 64231200Smmtypedef struct CPpmd7_Node_ 65231200Smm{ 66231200Smm UInt16 Stamp; /* must be at offset 0 as CPpmd7_Context::NumStats. Stamp=0 means free */ 67231200Smm UInt16 NU; 68231200Smm CPpmd7_Node_Ref Next; /* must be at offset >= 4 */ 69231200Smm CPpmd7_Node_Ref Prev; 70231200Smm} CPpmd7_Node; 71231200Smm 72231200Smm#ifdef PPMD_32BIT 73231200Smm #define NODE(ptr) (ptr) 74231200Smm#else 75231200Smm #define NODE(offs) ((CPpmd7_Node *)(p->Base + (offs))) 76231200Smm#endif 77231200Smm 78231200Smmstatic void Ppmd7_Update1(CPpmd7 *p); 79231200Smmstatic void Ppmd7_Update1_0(CPpmd7 *p); 80231200Smmstatic void Ppmd7_Update2(CPpmd7 *p); 81231200Smmstatic void Ppmd7_UpdateBin(CPpmd7 *p); 82231200Smmstatic CPpmd_See *Ppmd7_MakeEscFreq(CPpmd7 *p, unsigned numMasked, 83231200Smm UInt32 *scale); 84231200Smm 85231200Smm/* ----------- Base ----------- */ 86231200Smm 87231200Smmstatic void Ppmd7_Construct(CPpmd7 *p) 88231200Smm{ 89231200Smm unsigned i, k, m; 90231200Smm 91231200Smm p->Base = 0; 92231200Smm 93231200Smm for (i = 0, k = 0; i < PPMD_NUM_INDEXES; i++) 94231200Smm { 95231200Smm unsigned step = (i >= 12 ? 4 : (i >> 2) + 1); 96231200Smm do { p->Units2Indx[k++] = (Byte)i; } while(--step); 97231200Smm p->Indx2Units[i] = (Byte)k; 98231200Smm } 99231200Smm 100231200Smm p->NS2BSIndx[0] = (0 << 1); 101231200Smm p->NS2BSIndx[1] = (1 << 1); 102231200Smm memset(p->NS2BSIndx + 2, (2 << 1), 9); 103231200Smm memset(p->NS2BSIndx + 11, (3 << 1), 256 - 11); 104231200Smm 105231200Smm for (i = 0; i < 3; i++) 106231200Smm p->NS2Indx[i] = (Byte)i; 107231200Smm for (m = i, k = 1; i < 256; i++) 108231200Smm { 109231200Smm p->NS2Indx[i] = (Byte)m; 110231200Smm if (--k == 0) 111231200Smm k = (++m) - 2; 112231200Smm } 113231200Smm 114231200Smm memset(p->HB2Flag, 0, 0x40); 115231200Smm memset(p->HB2Flag + 0x40, 8, 0x100 - 0x40); 116231200Smm} 117231200Smm 118328827Smmstatic void Ppmd7_Free(CPpmd7 *p) 119231200Smm{ 120328827Smm free(p->Base); 121231200Smm p->Size = 0; 122231200Smm p->Base = 0; 123231200Smm} 124231200Smm 125328827Smmstatic Bool Ppmd7_Alloc(CPpmd7 *p, UInt32 size) 126231200Smm{ 127231200Smm if (p->Base == 0 || p->Size != size) 128231200Smm { 129302075Smm /* RestartModel() below assumes that p->Size >= UNIT_SIZE 130302075Smm (see the calculation of m->MinContext). */ 131302075Smm if (size < UNIT_SIZE) { 132302075Smm return False; 133302075Smm } 134328827Smm Ppmd7_Free(p); 135231200Smm p->AlignOffset = 136231200Smm #ifdef PPMD_32BIT 137231200Smm (4 - size) & 3; 138231200Smm #else 139231200Smm 4 - (size & 3); 140231200Smm #endif 141328827Smm if ((p->Base = (Byte *)malloc(p->AlignOffset + size 142231200Smm #ifndef PPMD_32BIT 143231200Smm + UNIT_SIZE 144231200Smm #endif 145231200Smm )) == 0) 146231200Smm return False; 147231200Smm p->Size = size; 148231200Smm } 149231200Smm return True; 150231200Smm} 151231200Smm 152231200Smmstatic void InsertNode(CPpmd7 *p, void *node, unsigned indx) 153231200Smm{ 154231200Smm *((CPpmd_Void_Ref *)node) = p->FreeList[indx]; 155231200Smm p->FreeList[indx] = REF(node); 156231200Smm} 157231200Smm 158231200Smmstatic void *RemoveNode(CPpmd7 *p, unsigned indx) 159231200Smm{ 160231200Smm CPpmd_Void_Ref *node = (CPpmd_Void_Ref *)Ppmd7_GetPtr(p, p->FreeList[indx]); 161231200Smm p->FreeList[indx] = *node; 162231200Smm return node; 163231200Smm} 164231200Smm 165231200Smmstatic void SplitBlock(CPpmd7 *p, void *ptr, unsigned oldIndx, unsigned newIndx) 166231200Smm{ 167231200Smm unsigned i, nu = I2U(oldIndx) - I2U(newIndx); 168231200Smm ptr = (Byte *)ptr + U2B(I2U(newIndx)); 169231200Smm if (I2U(i = U2I(nu)) != nu) 170231200Smm { 171231200Smm unsigned k = I2U(--i); 172231200Smm InsertNode(p, ((Byte *)ptr) + U2B(k), nu - k - 1); 173231200Smm } 174231200Smm InsertNode(p, ptr, i); 175231200Smm} 176231200Smm 177231200Smmstatic void GlueFreeBlocks(CPpmd7 *p) 178231200Smm{ 179231200Smm #ifdef PPMD_32BIT 180231200Smm CPpmd7_Node headItem; 181231200Smm CPpmd7_Node_Ref head = &headItem; 182231200Smm #else 183231200Smm CPpmd7_Node_Ref head = p->AlignOffset + p->Size; 184231200Smm #endif 185231200Smm 186231200Smm CPpmd7_Node_Ref n = head; 187231200Smm unsigned i; 188231200Smm 189231200Smm p->GlueCount = 255; 190231200Smm 191231200Smm /* create doubly-linked list of free blocks */ 192231200Smm for (i = 0; i < PPMD_NUM_INDEXES; i++) 193231200Smm { 194231200Smm UInt16 nu = I2U(i); 195231200Smm CPpmd7_Node_Ref next = (CPpmd7_Node_Ref)p->FreeList[i]; 196231200Smm p->FreeList[i] = 0; 197231200Smm while (next != 0) 198231200Smm { 199231200Smm CPpmd7_Node *node = NODE(next); 200231200Smm node->Next = n; 201231200Smm n = NODE(n)->Prev = next; 202231200Smm next = *(const CPpmd7_Node_Ref *)node; 203231200Smm node->Stamp = 0; 204231200Smm node->NU = (UInt16)nu; 205231200Smm } 206231200Smm } 207231200Smm NODE(head)->Stamp = 1; 208231200Smm NODE(head)->Next = n; 209231200Smm NODE(n)->Prev = head; 210231200Smm if (p->LoUnit != p->HiUnit) 211231200Smm ((CPpmd7_Node *)p->LoUnit)->Stamp = 1; 212231200Smm 213231200Smm /* Glue free blocks */ 214231200Smm while (n != head) 215231200Smm { 216231200Smm CPpmd7_Node *node = NODE(n); 217231200Smm UInt32 nu = (UInt32)node->NU; 218231200Smm for (;;) 219231200Smm { 220231200Smm CPpmd7_Node *node2 = NODE(n) + nu; 221231200Smm nu += node2->NU; 222231200Smm if (node2->Stamp != 0 || nu >= 0x10000) 223231200Smm break; 224231200Smm NODE(node2->Prev)->Next = node2->Next; 225231200Smm NODE(node2->Next)->Prev = node2->Prev; 226231200Smm node->NU = (UInt16)nu; 227231200Smm } 228231200Smm n = node->Next; 229231200Smm } 230231200Smm 231231200Smm /* Fill lists of free blocks */ 232231200Smm for (n = NODE(head)->Next; n != head;) 233231200Smm { 234231200Smm CPpmd7_Node *node = NODE(n); 235231200Smm unsigned nu; 236231200Smm CPpmd7_Node_Ref next = node->Next; 237231200Smm for (nu = node->NU; nu > 128; nu -= 128, node += 128) 238231200Smm InsertNode(p, node, PPMD_NUM_INDEXES - 1); 239231200Smm if (I2U(i = U2I(nu)) != nu) 240231200Smm { 241231200Smm unsigned k = I2U(--i); 242231200Smm InsertNode(p, node + k, nu - k - 1); 243231200Smm } 244231200Smm InsertNode(p, node, i); 245231200Smm n = next; 246231200Smm } 247231200Smm} 248231200Smm 249231200Smmstatic void *AllocUnitsRare(CPpmd7 *p, unsigned indx) 250231200Smm{ 251231200Smm unsigned i; 252231200Smm void *retVal; 253231200Smm if (p->GlueCount == 0) 254231200Smm { 255231200Smm GlueFreeBlocks(p); 256231200Smm if (p->FreeList[indx] != 0) 257231200Smm return RemoveNode(p, indx); 258231200Smm } 259231200Smm i = indx; 260231200Smm do 261231200Smm { 262231200Smm if (++i == PPMD_NUM_INDEXES) 263231200Smm { 264231200Smm UInt32 numBytes = U2B(I2U(indx)); 265231200Smm p->GlueCount--; 266231200Smm return ((UInt32)(p->UnitsStart - p->Text) > numBytes) ? (p->UnitsStart -= numBytes) : (NULL); 267231200Smm } 268231200Smm } 269231200Smm while (p->FreeList[i] == 0); 270231200Smm retVal = RemoveNode(p, i); 271231200Smm SplitBlock(p, retVal, i, indx); 272231200Smm return retVal; 273231200Smm} 274231200Smm 275231200Smmstatic void *AllocUnits(CPpmd7 *p, unsigned indx) 276231200Smm{ 277231200Smm UInt32 numBytes; 278231200Smm if (p->FreeList[indx] != 0) 279231200Smm return RemoveNode(p, indx); 280231200Smm numBytes = U2B(I2U(indx)); 281231200Smm if (numBytes <= (UInt32)(p->HiUnit - p->LoUnit)) 282231200Smm { 283231200Smm void *retVal = p->LoUnit; 284231200Smm p->LoUnit += numBytes; 285231200Smm return retVal; 286231200Smm } 287231200Smm return AllocUnitsRare(p, indx); 288231200Smm} 289231200Smm 290231200Smm#define MyMem12Cpy(dest, src, num) \ 291231200Smm { UInt32 *d = (UInt32 *)dest; const UInt32 *s = (const UInt32 *)src; UInt32 n = num; \ 292231200Smm do { d[0] = s[0]; d[1] = s[1]; d[2] = s[2]; s += 3; d += 3; } while(--n); } 293231200Smm 294231200Smmstatic void *ShrinkUnits(CPpmd7 *p, void *oldPtr, unsigned oldNU, unsigned newNU) 295231200Smm{ 296231200Smm unsigned i0 = U2I(oldNU); 297231200Smm unsigned i1 = U2I(newNU); 298231200Smm if (i0 == i1) 299231200Smm return oldPtr; 300231200Smm if (p->FreeList[i1] != 0) 301231200Smm { 302231200Smm void *ptr = RemoveNode(p, i1); 303231200Smm MyMem12Cpy(ptr, oldPtr, newNU); 304231200Smm InsertNode(p, oldPtr, i0); 305231200Smm return ptr; 306231200Smm } 307231200Smm SplitBlock(p, oldPtr, i0, i1); 308231200Smm return oldPtr; 309231200Smm} 310231200Smm 311231200Smm#define SUCCESSOR(p) ((CPpmd_Void_Ref)((p)->SuccessorLow | ((UInt32)(p)->SuccessorHigh << 16))) 312231200Smm 313231200Smmstatic void SetSuccessor(CPpmd_State *p, CPpmd_Void_Ref v) 314231200Smm{ 315231200Smm (p)->SuccessorLow = (UInt16)((UInt32)(v) & 0xFFFF); 316231200Smm (p)->SuccessorHigh = (UInt16)(((UInt32)(v) >> 16) & 0xFFFF); 317231200Smm} 318231200Smm 319231200Smmstatic void RestartModel(CPpmd7 *p) 320231200Smm{ 321231200Smm unsigned i, k, m; 322231200Smm 323231200Smm memset(p->FreeList, 0, sizeof(p->FreeList)); 324231200Smm p->Text = p->Base + p->AlignOffset; 325231200Smm p->HiUnit = p->Text + p->Size; 326231200Smm p->LoUnit = p->UnitsStart = p->HiUnit - p->Size / 8 / UNIT_SIZE * 7 * UNIT_SIZE; 327231200Smm p->GlueCount = 0; 328231200Smm 329231200Smm p->OrderFall = p->MaxOrder; 330231200Smm p->RunLength = p->InitRL = -(Int32)((p->MaxOrder < 12) ? p->MaxOrder : 12) - 1; 331231200Smm p->PrevSuccess = 0; 332231200Smm 333231200Smm p->MinContext = p->MaxContext = (CTX_PTR)(p->HiUnit -= UNIT_SIZE); /* AllocContext(p); */ 334231200Smm p->MinContext->Suffix = 0; 335231200Smm p->MinContext->NumStats = 256; 336231200Smm p->MinContext->SummFreq = 256 + 1; 337231200Smm p->FoundState = (CPpmd_State *)p->LoUnit; /* AllocUnits(p, PPMD_NUM_INDEXES - 1); */ 338231200Smm p->LoUnit += U2B(256 / 2); 339231200Smm p->MinContext->Stats = REF(p->FoundState); 340231200Smm for (i = 0; i < 256; i++) 341231200Smm { 342231200Smm CPpmd_State *s = &p->FoundState[i]; 343231200Smm s->Symbol = (Byte)i; 344231200Smm s->Freq = 1; 345231200Smm SetSuccessor(s, 0); 346231200Smm } 347231200Smm 348231200Smm for (i = 0; i < 128; i++) 349231200Smm for (k = 0; k < 8; k++) 350231200Smm { 351231200Smm UInt16 *dest = p->BinSumm[i] + k; 352231200Smm UInt16 val = (UInt16)(PPMD_BIN_SCALE - kInitBinEsc[k] / (i + 2)); 353231200Smm for (m = 0; m < 64; m += 8) 354231200Smm dest[m] = val; 355231200Smm } 356231200Smm 357231200Smm for (i = 0; i < 25; i++) 358231200Smm for (k = 0; k < 16; k++) 359231200Smm { 360231200Smm CPpmd_See *s = &p->See[i][k]; 361231200Smm s->Summ = (UInt16)((5 * i + 10) << (s->Shift = PPMD_PERIOD_BITS - 4)); 362231200Smm s->Count = 4; 363231200Smm } 364231200Smm} 365231200Smm 366231200Smmstatic void Ppmd7_Init(CPpmd7 *p, unsigned maxOrder) 367231200Smm{ 368231200Smm p->MaxOrder = maxOrder; 369231200Smm RestartModel(p); 370231200Smm p->DummySee.Shift = PPMD_PERIOD_BITS; 371231200Smm p->DummySee.Summ = 0; /* unused */ 372231200Smm p->DummySee.Count = 64; /* unused */ 373231200Smm} 374231200Smm 375231200Smmstatic CTX_PTR CreateSuccessors(CPpmd7 *p, Bool skip) 376231200Smm{ 377231200Smm CPpmd_State upState; 378231200Smm CTX_PTR c = p->MinContext; 379231200Smm CPpmd_Byte_Ref upBranch = (CPpmd_Byte_Ref)SUCCESSOR(p->FoundState); 380231200Smm CPpmd_State *ps[PPMD7_MAX_ORDER]; 381231200Smm unsigned numPs = 0; 382231200Smm 383231200Smm if (!skip) 384231200Smm ps[numPs++] = p->FoundState; 385231200Smm 386231200Smm while (c->Suffix) 387231200Smm { 388231200Smm CPpmd_Void_Ref successor; 389231200Smm CPpmd_State *s; 390231200Smm c = SUFFIX(c); 391231200Smm if (c->NumStats != 1) 392231200Smm { 393231200Smm for (s = STATS(c); s->Symbol != p->FoundState->Symbol; s++); 394231200Smm } 395231200Smm else 396231200Smm s = ONE_STATE(c); 397231200Smm successor = SUCCESSOR(s); 398231200Smm if (successor != upBranch) 399231200Smm { 400231200Smm c = CTX(successor); 401231200Smm if (numPs == 0) 402231200Smm return c; 403231200Smm break; 404231200Smm } 405231200Smm ps[numPs++] = s; 406231200Smm } 407231200Smm 408231200Smm upState.Symbol = *(const Byte *)Ppmd7_GetPtr(p, upBranch); 409231200Smm SetSuccessor(&upState, upBranch + 1); 410231200Smm 411231200Smm if (c->NumStats == 1) 412231200Smm upState.Freq = ONE_STATE(c)->Freq; 413231200Smm else 414231200Smm { 415231200Smm UInt32 cf, s0; 416231200Smm CPpmd_State *s; 417231200Smm for (s = STATS(c); s->Symbol != upState.Symbol; s++); 418231200Smm cf = s->Freq - 1; 419231200Smm s0 = c->SummFreq - c->NumStats - cf; 420231200Smm upState.Freq = (Byte)(1 + ((2 * cf <= s0) ? (5 * cf > s0) : ((2 * cf + 3 * s0 - 1) / (2 * s0)))); 421231200Smm } 422231200Smm 423238856Smm while (numPs != 0) 424231200Smm { 425231200Smm /* Create Child */ 426231200Smm CTX_PTR c1; /* = AllocContext(p); */ 427231200Smm if (p->HiUnit != p->LoUnit) 428231200Smm c1 = (CTX_PTR)(p->HiUnit -= UNIT_SIZE); 429231200Smm else if (p->FreeList[0] != 0) 430231200Smm c1 = (CTX_PTR)RemoveNode(p, 0); 431231200Smm else 432231200Smm { 433231200Smm c1 = (CTX_PTR)AllocUnitsRare(p, 0); 434231200Smm if (!c1) 435231200Smm return NULL; 436231200Smm } 437231200Smm c1->NumStats = 1; 438231200Smm *ONE_STATE(c1) = upState; 439231200Smm c1->Suffix = REF(c); 440231200Smm SetSuccessor(ps[--numPs], REF(c1)); 441231200Smm c = c1; 442231200Smm } 443231200Smm 444231200Smm return c; 445231200Smm} 446231200Smm 447231200Smmstatic void SwapStates(CPpmd_State *t1, CPpmd_State *t2) 448231200Smm{ 449231200Smm CPpmd_State tmp = *t1; 450231200Smm *t1 = *t2; 451231200Smm *t2 = tmp; 452231200Smm} 453231200Smm 454231200Smmstatic void UpdateModel(CPpmd7 *p) 455231200Smm{ 456231200Smm CPpmd_Void_Ref successor, fSuccessor = SUCCESSOR(p->FoundState); 457231200Smm CTX_PTR c; 458231200Smm unsigned s0, ns; 459231200Smm 460231200Smm if (p->FoundState->Freq < MAX_FREQ / 4 && p->MinContext->Suffix != 0) 461231200Smm { 462231200Smm c = SUFFIX(p->MinContext); 463231200Smm 464231200Smm if (c->NumStats == 1) 465231200Smm { 466231200Smm CPpmd_State *s = ONE_STATE(c); 467231200Smm if (s->Freq < 32) 468231200Smm s->Freq++; 469231200Smm } 470231200Smm else 471231200Smm { 472231200Smm CPpmd_State *s = STATS(c); 473231200Smm if (s->Symbol != p->FoundState->Symbol) 474231200Smm { 475231200Smm do { s++; } while (s->Symbol != p->FoundState->Symbol); 476231200Smm if (s[0].Freq >= s[-1].Freq) 477231200Smm { 478231200Smm SwapStates(&s[0], &s[-1]); 479231200Smm s--; 480231200Smm } 481231200Smm } 482231200Smm if (s->Freq < MAX_FREQ - 9) 483231200Smm { 484231200Smm s->Freq += 2; 485231200Smm c->SummFreq += 2; 486231200Smm } 487231200Smm } 488231200Smm } 489231200Smm 490231200Smm if (p->OrderFall == 0) 491231200Smm { 492231200Smm p->MinContext = p->MaxContext = CreateSuccessors(p, True); 493231200Smm if (p->MinContext == 0) 494231200Smm { 495231200Smm RestartModel(p); 496231200Smm return; 497231200Smm } 498231200Smm SetSuccessor(p->FoundState, REF(p->MinContext)); 499231200Smm return; 500231200Smm } 501231200Smm 502231200Smm *p->Text++ = p->FoundState->Symbol; 503231200Smm successor = REF(p->Text); 504231200Smm if (p->Text >= p->UnitsStart) 505231200Smm { 506231200Smm RestartModel(p); 507231200Smm return; 508231200Smm } 509231200Smm 510231200Smm if (fSuccessor) 511231200Smm { 512231200Smm if (fSuccessor <= successor) 513231200Smm { 514231200Smm CTX_PTR cs = CreateSuccessors(p, False); 515231200Smm if (cs == NULL) 516231200Smm { 517231200Smm RestartModel(p); 518231200Smm return; 519231200Smm } 520231200Smm fSuccessor = REF(cs); 521231200Smm } 522231200Smm if (--p->OrderFall == 0) 523231200Smm { 524231200Smm successor = fSuccessor; 525231200Smm p->Text -= (p->MaxContext != p->MinContext); 526231200Smm } 527231200Smm } 528231200Smm else 529231200Smm { 530231200Smm SetSuccessor(p->FoundState, successor); 531231200Smm fSuccessor = REF(p->MinContext); 532231200Smm } 533231200Smm 534231200Smm s0 = p->MinContext->SummFreq - (ns = p->MinContext->NumStats) - (p->FoundState->Freq - 1); 535231200Smm 536231200Smm for (c = p->MaxContext; c != p->MinContext; c = SUFFIX(c)) 537231200Smm { 538231200Smm unsigned ns1; 539231200Smm UInt32 cf, sf; 540231200Smm if ((ns1 = c->NumStats) != 1) 541231200Smm { 542231200Smm if ((ns1 & 1) == 0) 543231200Smm { 544231200Smm /* Expand for one UNIT */ 545231200Smm unsigned oldNU = ns1 >> 1; 546231200Smm unsigned i = U2I(oldNU); 547231200Smm if (i != U2I(oldNU + 1)) 548231200Smm { 549231200Smm void *ptr = AllocUnits(p, i + 1); 550231200Smm void *oldPtr; 551231200Smm if (!ptr) 552231200Smm { 553231200Smm RestartModel(p); 554231200Smm return; 555231200Smm } 556231200Smm oldPtr = STATS(c); 557231200Smm MyMem12Cpy(ptr, oldPtr, oldNU); 558231200Smm InsertNode(p, oldPtr, i); 559231200Smm c->Stats = STATS_REF(ptr); 560231200Smm } 561231200Smm } 562231200Smm c->SummFreq = (UInt16)(c->SummFreq + (2 * ns1 < ns) + 2 * ((4 * ns1 <= ns) & (c->SummFreq <= 8 * ns1))); 563231200Smm } 564231200Smm else 565231200Smm { 566231200Smm CPpmd_State *s = (CPpmd_State*)AllocUnits(p, 0); 567231200Smm if (!s) 568231200Smm { 569231200Smm RestartModel(p); 570231200Smm return; 571231200Smm } 572231200Smm *s = *ONE_STATE(c); 573231200Smm c->Stats = REF(s); 574231200Smm if (s->Freq < MAX_FREQ / 4 - 1) 575231200Smm s->Freq <<= 1; 576231200Smm else 577231200Smm s->Freq = MAX_FREQ - 4; 578231200Smm c->SummFreq = (UInt16)(s->Freq + p->InitEsc + (ns > 3)); 579231200Smm } 580231200Smm cf = 2 * (UInt32)p->FoundState->Freq * (c->SummFreq + 6); 581231200Smm sf = (UInt32)s0 + c->SummFreq; 582231200Smm if (cf < 6 * sf) 583231200Smm { 584231200Smm cf = 1 + (cf > sf) + (cf >= 4 * sf); 585231200Smm c->SummFreq += 3; 586231200Smm } 587231200Smm else 588231200Smm { 589231200Smm cf = 4 + (cf >= 9 * sf) + (cf >= 12 * sf) + (cf >= 15 * sf); 590231200Smm c->SummFreq = (UInt16)(c->SummFreq + cf); 591231200Smm } 592231200Smm { 593231200Smm CPpmd_State *s = STATS(c) + ns1; 594231200Smm SetSuccessor(s, successor); 595231200Smm s->Symbol = p->FoundState->Symbol; 596231200Smm s->Freq = (Byte)cf; 597231200Smm c->NumStats = (UInt16)(ns1 + 1); 598231200Smm } 599231200Smm } 600231200Smm p->MaxContext = p->MinContext = CTX(fSuccessor); 601231200Smm} 602231200Smm 603231200Smmstatic void Rescale(CPpmd7 *p) 604231200Smm{ 605231200Smm unsigned i, adder, sumFreq, escFreq; 606231200Smm CPpmd_State *stats = STATS(p->MinContext); 607231200Smm CPpmd_State *s = p->FoundState; 608231200Smm { 609231200Smm CPpmd_State tmp = *s; 610231200Smm for (; s != stats; s--) 611231200Smm s[0] = s[-1]; 612231200Smm *s = tmp; 613231200Smm } 614231200Smm escFreq = p->MinContext->SummFreq - s->Freq; 615231200Smm s->Freq += 4; 616231200Smm adder = (p->OrderFall != 0); 617231200Smm s->Freq = (Byte)((s->Freq + adder) >> 1); 618231200Smm sumFreq = s->Freq; 619231200Smm 620231200Smm i = p->MinContext->NumStats - 1; 621231200Smm do 622231200Smm { 623231200Smm escFreq -= (++s)->Freq; 624231200Smm s->Freq = (Byte)((s->Freq + adder) >> 1); 625231200Smm sumFreq += s->Freq; 626231200Smm if (s[0].Freq > s[-1].Freq) 627231200Smm { 628231200Smm CPpmd_State *s1 = s; 629231200Smm CPpmd_State tmp = *s1; 630231200Smm do 631231200Smm s1[0] = s1[-1]; 632231200Smm while (--s1 != stats && tmp.Freq > s1[-1].Freq); 633231200Smm *s1 = tmp; 634231200Smm } 635231200Smm } 636231200Smm while (--i); 637231200Smm 638231200Smm if (s->Freq == 0) 639231200Smm { 640231200Smm unsigned numStats = p->MinContext->NumStats; 641231200Smm unsigned n0, n1; 642231200Smm do { i++; } while ((--s)->Freq == 0); 643231200Smm escFreq += i; 644231200Smm p->MinContext->NumStats = (UInt16)(p->MinContext->NumStats - i); 645231200Smm if (p->MinContext->NumStats == 1) 646231200Smm { 647231200Smm CPpmd_State tmp = *stats; 648231200Smm do 649231200Smm { 650231200Smm tmp.Freq = (Byte)(tmp.Freq - (tmp.Freq >> 1)); 651231200Smm escFreq >>= 1; 652231200Smm } 653231200Smm while (escFreq > 1); 654231200Smm InsertNode(p, stats, U2I(((numStats + 1) >> 1))); 655231200Smm *(p->FoundState = ONE_STATE(p->MinContext)) = tmp; 656231200Smm return; 657231200Smm } 658231200Smm n0 = (numStats + 1) >> 1; 659231200Smm n1 = (p->MinContext->NumStats + 1) >> 1; 660231200Smm if (n0 != n1) 661231200Smm p->MinContext->Stats = STATS_REF(ShrinkUnits(p, stats, n0, n1)); 662231200Smm } 663231200Smm p->MinContext->SummFreq = (UInt16)(sumFreq + escFreq - (escFreq >> 1)); 664231200Smm p->FoundState = STATS(p->MinContext); 665231200Smm} 666231200Smm 667231200Smmstatic CPpmd_See *Ppmd7_MakeEscFreq(CPpmd7 *p, unsigned numMasked, UInt32 *escFreq) 668231200Smm{ 669231200Smm CPpmd_See *see; 670231200Smm unsigned nonMasked = p->MinContext->NumStats - numMasked; 671231200Smm if (p->MinContext->NumStats != 256) 672231200Smm { 673231200Smm see = p->See[p->NS2Indx[nonMasked - 1]] + 674231200Smm (nonMasked < (unsigned)SUFFIX(p->MinContext)->NumStats - p->MinContext->NumStats) + 675231200Smm 2 * (p->MinContext->SummFreq < 11 * p->MinContext->NumStats) + 676231200Smm 4 * (numMasked > nonMasked) + 677231200Smm p->HiBitsFlag; 678231200Smm { 679231200Smm unsigned r = (see->Summ >> see->Shift); 680231200Smm see->Summ = (UInt16)(see->Summ - r); 681231200Smm *escFreq = r + (r == 0); 682231200Smm } 683231200Smm } 684231200Smm else 685231200Smm { 686231200Smm see = &p->DummySee; 687231200Smm *escFreq = 1; 688231200Smm } 689231200Smm return see; 690231200Smm} 691231200Smm 692231200Smmstatic void NextContext(CPpmd7 *p) 693231200Smm{ 694231200Smm CTX_PTR c = CTX(SUCCESSOR(p->FoundState)); 695231200Smm if (p->OrderFall == 0 && (Byte *)c > p->Text) 696231200Smm p->MinContext = p->MaxContext = c; 697231200Smm else 698231200Smm UpdateModel(p); 699231200Smm} 700231200Smm 701231200Smmstatic void Ppmd7_Update1(CPpmd7 *p) 702231200Smm{ 703231200Smm CPpmd_State *s = p->FoundState; 704231200Smm s->Freq += 4; 705231200Smm p->MinContext->SummFreq += 4; 706231200Smm if (s[0].Freq > s[-1].Freq) 707231200Smm { 708231200Smm SwapStates(&s[0], &s[-1]); 709231200Smm p->FoundState = --s; 710231200Smm if (s->Freq > MAX_FREQ) 711231200Smm Rescale(p); 712231200Smm } 713231200Smm NextContext(p); 714231200Smm} 715231200Smm 716231200Smmstatic void Ppmd7_Update1_0(CPpmd7 *p) 717231200Smm{ 718231200Smm p->PrevSuccess = (2 * p->FoundState->Freq > p->MinContext->SummFreq); 719231200Smm p->RunLength += p->PrevSuccess; 720231200Smm p->MinContext->SummFreq += 4; 721231200Smm if ((p->FoundState->Freq += 4) > MAX_FREQ) 722231200Smm Rescale(p); 723231200Smm NextContext(p); 724231200Smm} 725231200Smm 726231200Smmstatic void Ppmd7_UpdateBin(CPpmd7 *p) 727231200Smm{ 728231200Smm p->FoundState->Freq = (Byte)(p->FoundState->Freq + (p->FoundState->Freq < 128 ? 1: 0)); 729231200Smm p->PrevSuccess = 1; 730231200Smm p->RunLength++; 731231200Smm NextContext(p); 732231200Smm} 733231200Smm 734231200Smmstatic void Ppmd7_Update2(CPpmd7 *p) 735231200Smm{ 736231200Smm p->MinContext->SummFreq += 4; 737231200Smm if ((p->FoundState->Freq += 4) > MAX_FREQ) 738231200Smm Rescale(p); 739231200Smm p->RunLength = p->InitRL; 740231200Smm UpdateModel(p); 741231200Smm} 742231200Smm 743231200Smm/* ---------- Decode ---------- */ 744231200Smm 745231200Smmstatic Bool Ppmd_RangeDec_Init(CPpmd7z_RangeDec *p) 746231200Smm{ 747231200Smm unsigned i; 748231200Smm p->Low = p->Bottom = 0; 749231200Smm p->Range = 0xFFFFFFFF; 750231200Smm for (i = 0; i < 4; i++) 751231200Smm p->Code = (p->Code << 8) | p->Stream->Read((void *)p->Stream); 752231200Smm return (p->Code < 0xFFFFFFFF); 753231200Smm} 754231200Smm 755231200Smmstatic Bool Ppmd7z_RangeDec_Init(CPpmd7z_RangeDec *p) 756231200Smm{ 757231200Smm if (p->Stream->Read((void *)p->Stream) != 0) 758231200Smm return False; 759231200Smm return Ppmd_RangeDec_Init(p); 760231200Smm} 761231200Smm 762231200Smmstatic Bool PpmdRAR_RangeDec_Init(CPpmd7z_RangeDec *p) 763231200Smm{ 764231200Smm if (!Ppmd_RangeDec_Init(p)) 765231200Smm return False; 766231200Smm p->Bottom = 0x8000; 767231200Smm return True; 768231200Smm} 769231200Smm 770231200Smmstatic UInt32 Range_GetThreshold(void *pp, UInt32 total) 771231200Smm{ 772231200Smm CPpmd7z_RangeDec *p = (CPpmd7z_RangeDec *)pp; 773231200Smm return (p->Code - p->Low) / (p->Range /= total); 774231200Smm} 775231200Smm 776231200Smmstatic void Range_Normalize(CPpmd7z_RangeDec *p) 777231200Smm{ 778231200Smm while (1) 779231200Smm { 780231200Smm if((p->Low ^ (p->Low + p->Range)) >= kTopValue) 781231200Smm { 782231200Smm if(p->Range >= p->Bottom) 783231200Smm break; 784231200Smm else 785238856Smm p->Range = ((uint32_t)(-(int32_t)p->Low)) & (p->Bottom - 1); 786231200Smm } 787231200Smm p->Code = (p->Code << 8) | p->Stream->Read((void *)p->Stream); 788231200Smm p->Range <<= 8; 789231200Smm p->Low <<= 8; 790231200Smm } 791231200Smm} 792231200Smm 793231200Smmstatic void Range_Decode_7z(void *pp, UInt32 start, UInt32 size) 794231200Smm{ 795231200Smm CPpmd7z_RangeDec *p = (CPpmd7z_RangeDec *)pp; 796231200Smm p->Code -= start * p->Range; 797231200Smm p->Range *= size; 798231200Smm Range_Normalize(p); 799231200Smm} 800231200Smm 801231200Smmstatic void Range_Decode_RAR(void *pp, UInt32 start, UInt32 size) 802231200Smm{ 803231200Smm CPpmd7z_RangeDec *p = (CPpmd7z_RangeDec *)pp; 804231200Smm p->Low += start * p->Range; 805231200Smm p->Range *= size; 806231200Smm Range_Normalize(p); 807231200Smm} 808231200Smm 809231200Smmstatic UInt32 Range_DecodeBit_7z(void *pp, UInt32 size0) 810231200Smm{ 811231200Smm CPpmd7z_RangeDec *p = (CPpmd7z_RangeDec *)pp; 812231200Smm UInt32 newBound = (p->Range >> 14) * size0; 813231200Smm UInt32 symbol; 814231200Smm if (p->Code < newBound) 815231200Smm { 816231200Smm symbol = 0; 817231200Smm p->Range = newBound; 818231200Smm } 819231200Smm else 820231200Smm { 821231200Smm symbol = 1; 822231200Smm p->Code -= newBound; 823231200Smm p->Range -= newBound; 824231200Smm } 825231200Smm Range_Normalize(p); 826231200Smm return symbol; 827231200Smm} 828231200Smm 829231200Smmstatic UInt32 Range_DecodeBit_RAR(void *pp, UInt32 size0) 830231200Smm{ 831231200Smm CPpmd7z_RangeDec *p = (CPpmd7z_RangeDec *)pp; 832231200Smm UInt32 bit, value = p->p.GetThreshold(p, PPMD_BIN_SCALE); 833231200Smm if(value < size0) 834231200Smm { 835231200Smm bit = 0; 836231200Smm p->p.Decode(p, 0, size0); 837231200Smm } 838231200Smm else 839231200Smm { 840231200Smm bit = 1; 841231200Smm p->p.Decode(p, size0, PPMD_BIN_SCALE - size0); 842231200Smm } 843231200Smm return bit; 844231200Smm} 845231200Smm 846231200Smmstatic void Ppmd7z_RangeDec_CreateVTable(CPpmd7z_RangeDec *p) 847231200Smm{ 848231200Smm p->p.GetThreshold = Range_GetThreshold; 849231200Smm p->p.Decode = Range_Decode_7z; 850231200Smm p->p.DecodeBit = Range_DecodeBit_7z; 851231200Smm} 852231200Smm 853231200Smmstatic void PpmdRAR_RangeDec_CreateVTable(CPpmd7z_RangeDec *p) 854231200Smm{ 855231200Smm p->p.GetThreshold = Range_GetThreshold; 856231200Smm p->p.Decode = Range_Decode_RAR; 857231200Smm p->p.DecodeBit = Range_DecodeBit_RAR; 858231200Smm} 859231200Smm 860231200Smm#define MASK(sym) ((signed char *)charMask)[sym] 861231200Smm 862231200Smmstatic int Ppmd7_DecodeSymbol(CPpmd7 *p, IPpmd7_RangeDec *rc) 863231200Smm{ 864231200Smm size_t charMask[256 / sizeof(size_t)]; 865231200Smm if (p->MinContext->NumStats != 1) 866231200Smm { 867231200Smm CPpmd_State *s = Ppmd7_GetStats(p, p->MinContext); 868231200Smm unsigned i; 869231200Smm UInt32 count, hiCnt; 870231200Smm if ((count = rc->GetThreshold(rc, p->MinContext->SummFreq)) < (hiCnt = s->Freq)) 871231200Smm { 872231200Smm Byte symbol; 873231200Smm rc->Decode(rc, 0, s->Freq); 874231200Smm p->FoundState = s; 875231200Smm symbol = s->Symbol; 876231200Smm Ppmd7_Update1_0(p); 877231200Smm return symbol; 878231200Smm } 879231200Smm p->PrevSuccess = 0; 880231200Smm i = p->MinContext->NumStats - 1; 881231200Smm do 882231200Smm { 883231200Smm if ((hiCnt += (++s)->Freq) > count) 884231200Smm { 885231200Smm Byte symbol; 886231200Smm rc->Decode(rc, hiCnt - s->Freq, s->Freq); 887231200Smm p->FoundState = s; 888231200Smm symbol = s->Symbol; 889231200Smm Ppmd7_Update1(p); 890231200Smm return symbol; 891231200Smm } 892231200Smm } 893231200Smm while (--i); 894231200Smm if (count >= p->MinContext->SummFreq) 895231200Smm return -2; 896231200Smm p->HiBitsFlag = p->HB2Flag[p->FoundState->Symbol]; 897231200Smm rc->Decode(rc, hiCnt, p->MinContext->SummFreq - hiCnt); 898231200Smm PPMD_SetAllBitsIn256Bytes(charMask); 899231200Smm MASK(s->Symbol) = 0; 900231200Smm i = p->MinContext->NumStats - 1; 901231200Smm do { MASK((--s)->Symbol) = 0; } while (--i); 902231200Smm } 903231200Smm else 904231200Smm { 905231200Smm UInt16 *prob = Ppmd7_GetBinSumm(p); 906231200Smm if (rc->DecodeBit(rc, *prob) == 0) 907231200Smm { 908231200Smm Byte symbol; 909231200Smm *prob = (UInt16)PPMD_UPDATE_PROB_0(*prob); 910231200Smm symbol = (p->FoundState = Ppmd7Context_OneState(p->MinContext))->Symbol; 911231200Smm Ppmd7_UpdateBin(p); 912231200Smm return symbol; 913231200Smm } 914231200Smm *prob = (UInt16)PPMD_UPDATE_PROB_1(*prob); 915231200Smm p->InitEsc = PPMD7_kExpEscape[*prob >> 10]; 916231200Smm PPMD_SetAllBitsIn256Bytes(charMask); 917231200Smm MASK(Ppmd7Context_OneState(p->MinContext)->Symbol) = 0; 918231200Smm p->PrevSuccess = 0; 919231200Smm } 920231200Smm for (;;) 921231200Smm { 922231200Smm CPpmd_State *ps[256], *s; 923231200Smm UInt32 freqSum, count, hiCnt; 924231200Smm CPpmd_See *see; 925231200Smm unsigned i, num, numMasked = p->MinContext->NumStats; 926231200Smm do 927231200Smm { 928231200Smm p->OrderFall++; 929231200Smm if (!p->MinContext->Suffix) 930231200Smm return -1; 931231200Smm p->MinContext = Ppmd7_GetContext(p, p->MinContext->Suffix); 932231200Smm } 933231200Smm while (p->MinContext->NumStats == numMasked); 934231200Smm hiCnt = 0; 935231200Smm s = Ppmd7_GetStats(p, p->MinContext); 936231200Smm i = 0; 937231200Smm num = p->MinContext->NumStats - numMasked; 938231200Smm do 939231200Smm { 940231200Smm int k = (int)(MASK(s->Symbol)); 941231200Smm hiCnt += (s->Freq & k); 942231200Smm ps[i] = s++; 943231200Smm i -= k; 944231200Smm } 945231200Smm while (i != num); 946231200Smm 947231200Smm see = Ppmd7_MakeEscFreq(p, numMasked, &freqSum); 948231200Smm freqSum += hiCnt; 949231200Smm count = rc->GetThreshold(rc, freqSum); 950231200Smm 951231200Smm if (count < hiCnt) 952231200Smm { 953231200Smm Byte symbol; 954231200Smm CPpmd_State **pps = ps; 955231200Smm for (hiCnt = 0; (hiCnt += (*pps)->Freq) <= count; pps++); 956231200Smm s = *pps; 957231200Smm rc->Decode(rc, hiCnt - s->Freq, s->Freq); 958231200Smm Ppmd_See_Update(see); 959231200Smm p->FoundState = s; 960231200Smm symbol = s->Symbol; 961231200Smm Ppmd7_Update2(p); 962231200Smm return symbol; 963231200Smm } 964231200Smm if (count >= freqSum) 965231200Smm return -2; 966231200Smm rc->Decode(rc, hiCnt, freqSum - hiCnt); 967231200Smm see->Summ = (UInt16)(see->Summ + freqSum); 968231200Smm do { MASK(ps[--i]->Symbol) = 0; } while (i != 0); 969231200Smm } 970231200Smm} 971231200Smm 972231200Smm/* ---------- Encode ---------- Ppmd7Enc.c */ 973231200Smm 974231200Smm#define kTopValue (1 << 24) 975231200Smm 976231200Smmstatic void Ppmd7z_RangeEnc_Init(CPpmd7z_RangeEnc *p) 977231200Smm{ 978231200Smm p->Low = 0; 979231200Smm p->Range = 0xFFFFFFFF; 980231200Smm p->Cache = 0; 981231200Smm p->CacheSize = 1; 982231200Smm} 983231200Smm 984231200Smmstatic void RangeEnc_ShiftLow(CPpmd7z_RangeEnc *p) 985231200Smm{ 986231200Smm if ((UInt32)p->Low < (UInt32)0xFF000000 || (unsigned)(p->Low >> 32) != 0) 987231200Smm { 988231200Smm Byte temp = p->Cache; 989231200Smm do 990231200Smm { 991231200Smm p->Stream->Write(p->Stream, (Byte)(temp + (Byte)(p->Low >> 32))); 992231200Smm temp = 0xFF; 993231200Smm } 994231200Smm while(--p->CacheSize != 0); 995231200Smm p->Cache = (Byte)((UInt32)p->Low >> 24); 996231200Smm } 997231200Smm p->CacheSize++; 998248616Smm p->Low = ((UInt32)p->Low << 8) & 0xFFFFFFFF; 999231200Smm} 1000231200Smm 1001231200Smmstatic void RangeEnc_Encode(CPpmd7z_RangeEnc *p, UInt32 start, UInt32 size, UInt32 total) 1002231200Smm{ 1003358088Smm p->Low += (UInt64)start * (UInt64)(p->Range /= total); 1004231200Smm p->Range *= size; 1005231200Smm while (p->Range < kTopValue) 1006231200Smm { 1007231200Smm p->Range <<= 8; 1008231200Smm RangeEnc_ShiftLow(p); 1009231200Smm } 1010231200Smm} 1011231200Smm 1012231200Smmstatic void RangeEnc_EncodeBit_0(CPpmd7z_RangeEnc *p, UInt32 size0) 1013231200Smm{ 1014231200Smm p->Range = (p->Range >> 14) * size0; 1015231200Smm while (p->Range < kTopValue) 1016231200Smm { 1017231200Smm p->Range <<= 8; 1018231200Smm RangeEnc_ShiftLow(p); 1019231200Smm } 1020231200Smm} 1021231200Smm 1022231200Smmstatic void RangeEnc_EncodeBit_1(CPpmd7z_RangeEnc *p, UInt32 size0) 1023231200Smm{ 1024231200Smm UInt32 newBound = (p->Range >> 14) * size0; 1025231200Smm p->Low += newBound; 1026231200Smm p->Range -= newBound; 1027231200Smm while (p->Range < kTopValue) 1028231200Smm { 1029231200Smm p->Range <<= 8; 1030231200Smm RangeEnc_ShiftLow(p); 1031231200Smm } 1032231200Smm} 1033231200Smm 1034231200Smmstatic void Ppmd7z_RangeEnc_FlushData(CPpmd7z_RangeEnc *p) 1035231200Smm{ 1036231200Smm unsigned i; 1037231200Smm for (i = 0; i < 5; i++) 1038231200Smm RangeEnc_ShiftLow(p); 1039231200Smm} 1040231200Smm 1041231200Smm 1042231200Smm#define MASK(sym) ((signed char *)charMask)[sym] 1043231200Smm 1044231200Smmstatic void Ppmd7_EncodeSymbol(CPpmd7 *p, CPpmd7z_RangeEnc *rc, int symbol) 1045231200Smm{ 1046231200Smm size_t charMask[256 / sizeof(size_t)]; 1047231200Smm if (p->MinContext->NumStats != 1) 1048231200Smm { 1049231200Smm CPpmd_State *s = Ppmd7_GetStats(p, p->MinContext); 1050231200Smm UInt32 sum; 1051231200Smm unsigned i; 1052231200Smm if (s->Symbol == symbol) 1053231200Smm { 1054231200Smm RangeEnc_Encode(rc, 0, s->Freq, p->MinContext->SummFreq); 1055231200Smm p->FoundState = s; 1056231200Smm Ppmd7_Update1_0(p); 1057231200Smm return; 1058231200Smm } 1059231200Smm p->PrevSuccess = 0; 1060231200Smm sum = s->Freq; 1061231200Smm i = p->MinContext->NumStats - 1; 1062231200Smm do 1063231200Smm { 1064231200Smm if ((++s)->Symbol == symbol) 1065231200Smm { 1066231200Smm RangeEnc_Encode(rc, sum, s->Freq, p->MinContext->SummFreq); 1067231200Smm p->FoundState = s; 1068231200Smm Ppmd7_Update1(p); 1069231200Smm return; 1070231200Smm } 1071231200Smm sum += s->Freq; 1072231200Smm } 1073231200Smm while (--i); 1074231200Smm 1075231200Smm p->HiBitsFlag = p->HB2Flag[p->FoundState->Symbol]; 1076231200Smm PPMD_SetAllBitsIn256Bytes(charMask); 1077231200Smm MASK(s->Symbol) = 0; 1078231200Smm i = p->MinContext->NumStats - 1; 1079231200Smm do { MASK((--s)->Symbol) = 0; } while (--i); 1080231200Smm RangeEnc_Encode(rc, sum, p->MinContext->SummFreq - sum, p->MinContext->SummFreq); 1081231200Smm } 1082231200Smm else 1083231200Smm { 1084231200Smm UInt16 *prob = Ppmd7_GetBinSumm(p); 1085231200Smm CPpmd_State *s = Ppmd7Context_OneState(p->MinContext); 1086231200Smm if (s->Symbol == symbol) 1087231200Smm { 1088231200Smm RangeEnc_EncodeBit_0(rc, *prob); 1089231200Smm *prob = (UInt16)PPMD_UPDATE_PROB_0(*prob); 1090231200Smm p->FoundState = s; 1091231200Smm Ppmd7_UpdateBin(p); 1092231200Smm return; 1093231200Smm } 1094231200Smm else 1095231200Smm { 1096231200Smm RangeEnc_EncodeBit_1(rc, *prob); 1097231200Smm *prob = (UInt16)PPMD_UPDATE_PROB_1(*prob); 1098231200Smm p->InitEsc = PPMD7_kExpEscape[*prob >> 10]; 1099231200Smm PPMD_SetAllBitsIn256Bytes(charMask); 1100231200Smm MASK(s->Symbol) = 0; 1101231200Smm p->PrevSuccess = 0; 1102231200Smm } 1103231200Smm } 1104231200Smm for (;;) 1105231200Smm { 1106231200Smm UInt32 escFreq; 1107231200Smm CPpmd_See *see; 1108231200Smm CPpmd_State *s; 1109231200Smm UInt32 sum; 1110231200Smm unsigned i, numMasked = p->MinContext->NumStats; 1111231200Smm do 1112231200Smm { 1113231200Smm p->OrderFall++; 1114231200Smm if (!p->MinContext->Suffix) 1115231200Smm return; /* EndMarker (symbol = -1) */ 1116231200Smm p->MinContext = Ppmd7_GetContext(p, p->MinContext->Suffix); 1117231200Smm } 1118231200Smm while (p->MinContext->NumStats == numMasked); 1119231200Smm 1120231200Smm see = Ppmd7_MakeEscFreq(p, numMasked, &escFreq); 1121231200Smm s = Ppmd7_GetStats(p, p->MinContext); 1122231200Smm sum = 0; 1123231200Smm i = p->MinContext->NumStats; 1124231200Smm do 1125231200Smm { 1126231200Smm int cur = s->Symbol; 1127231200Smm if (cur == symbol) 1128231200Smm { 1129231200Smm UInt32 low = sum; 1130231200Smm CPpmd_State *s1 = s; 1131231200Smm do 1132231200Smm { 1133231200Smm sum += (s->Freq & (int)(MASK(s->Symbol))); 1134231200Smm s++; 1135231200Smm } 1136231200Smm while (--i); 1137231200Smm RangeEnc_Encode(rc, low, s1->Freq, sum + escFreq); 1138231200Smm Ppmd_See_Update(see); 1139231200Smm p->FoundState = s1; 1140231200Smm Ppmd7_Update2(p); 1141231200Smm return; 1142231200Smm } 1143231200Smm sum += (s->Freq & (int)(MASK(cur))); 1144231200Smm MASK(cur) = 0; 1145231200Smm s++; 1146231200Smm } 1147231200Smm while (--i); 1148231200Smm 1149231200Smm RangeEnc_Encode(rc, sum, escFreq, sum + escFreq); 1150231200Smm see->Summ = (UInt16)(see->Summ + sum + escFreq); 1151231200Smm } 1152231200Smm} 1153231200Smm 1154231200Smmconst IPpmd7 __archive_ppmd7_functions = 1155231200Smm{ 1156231200Smm &Ppmd7_Construct, 1157231200Smm &Ppmd7_Alloc, 1158231200Smm &Ppmd7_Free, 1159231200Smm &Ppmd7_Init, 1160231200Smm &Ppmd7z_RangeDec_CreateVTable, 1161231200Smm &PpmdRAR_RangeDec_CreateVTable, 1162231200Smm &Ppmd7z_RangeDec_Init, 1163231200Smm &PpmdRAR_RangeDec_Init, 1164231200Smm &Ppmd7_DecodeSymbol, 1165231200Smm &Ppmd7z_RangeEnc_Init, 1166231200Smm &Ppmd7z_RangeEnc_FlushData, 1167231200Smm &Ppmd7_EncodeSymbol 1168231200Smm}; 1169