1 /* Ppmd.h -- PPMD codec common code 2 2021-04-13 : Igor Pavlov : Public domain 3 This code is based on PPMd var.H (2001): Dmitry Shkarin : Public domain */ 4 5 #ifndef __PPMD_H 6 #define __PPMD_H 7 8 #include "CpuArch.h" 9 10 EXTERN_C_BEGIN 11 12 #if defined(MY_CPU_SIZEOF_POINTER) && (MY_CPU_SIZEOF_POINTER == 4) 13 /* 14 PPMD code always uses 32-bit internal fields in PPMD structures to store internal references in main block. 15 if (PPMD_32BIT is defined), the PPMD code stores internal pointers to 32-bit reference fields. 16 if (PPMD_32BIT is NOT defined), the PPMD code stores internal UInt32 offsets to reference fields. 17 if (pointer size is 64-bit), then (PPMD_32BIT) mode is not allowed, 18 if (pointer size is 32-bit), then (PPMD_32BIT) mode is optional, 19 and it's allowed to disable PPMD_32BIT mode even if pointer is 32-bit. 20 PPMD code works slightly faster in (PPMD_32BIT) mode. 21 */ 22 #define PPMD_32BIT 23 #endif 24 25 #define PPMD_INT_BITS 7 26 #define PPMD_PERIOD_BITS 7 27 #define PPMD_BIN_SCALE (1 << (PPMD_INT_BITS + PPMD_PERIOD_BITS)) 28 29 #define PPMD_GET_MEAN_SPEC(summ, shift, round) (((summ) + (1 << ((shift) - (round)))) >> (shift)) 30 #define PPMD_GET_MEAN(summ) PPMD_GET_MEAN_SPEC((summ), PPMD_PERIOD_BITS, 2) 31 #define PPMD_UPDATE_PROB_0(prob) ((prob) + (1 << PPMD_INT_BITS) - PPMD_GET_MEAN(prob)) 32 #define PPMD_UPDATE_PROB_1(prob) ((prob) - PPMD_GET_MEAN(prob)) 33 34 #define PPMD_N1 4 35 #define PPMD_N2 4 36 #define PPMD_N3 4 37 #define PPMD_N4 ((128 + 3 - 1 * PPMD_N1 - 2 * PPMD_N2 - 3 * PPMD_N3) / 4) 38 #define PPMD_NUM_INDEXES (PPMD_N1 + PPMD_N2 + PPMD_N3 + PPMD_N4) 39 40 MY_CPU_pragma_pack_push_1 41 /* Most compilers works OK here even without #pragma pack(push, 1), but some GCC compilers need it. */ 42 43 /* SEE-contexts for PPM-contexts with masked symbols */ 44 typedef struct 45 { 46 UInt16 Summ; /* Freq */ 47 Byte Shift; /* Speed of Freq change; low Shift is for fast change */ 48 Byte Count; /* Count to next change of Shift */ 49 } CPpmd_See; 50 51 #define Ppmd_See_Update(p) if ((p)->Shift < PPMD_PERIOD_BITS && --(p)->Count == 0) \ 52 { (p)->Summ = (UInt16)((p)->Summ << 1); (p)->Count = (Byte)(3 << (p)->Shift++); } 53 54 55 typedef struct 56 { 57 Byte Symbol; 58 Byte Freq; 59 UInt16 Successor_0; 60 UInt16 Successor_1; 61 } CPpmd_State; 62 63 typedef struct CPpmd_State2_ 64 { 65 Byte Symbol; 66 Byte Freq; 67 } CPpmd_State2; 68 69 typedef struct CPpmd_State4_ 70 { 71 UInt16 Successor_0; 72 UInt16 Successor_1; 73 } CPpmd_State4; 74 75 MY_CPU_pragma_pop 76 77 /* 78 PPMD code can write full CPpmd_State structure data to CPpmd*_Context 79 at (byte offset = 2) instead of some fields of original CPpmd*_Context structure. 80 81 If we use pointers to different types, but that point to shared 82 memory space, we can have aliasing problem (strict aliasing). 83 84 XLC compiler in -O2 mode can change the order of memory write instructions 85 in relation to read instructions, if we have use pointers to different types. 86 87 To solve that aliasing problem we use combined CPpmd*_Context structure 88 with unions that contain the fields from both structures: 89 the original CPpmd*_Context and CPpmd_State. 90 So we can access the fields from both structures via one pointer, 91 and the compiler doesn't change the order of write instructions 92 in relation to read instructions. 93 94 If we don't use memory write instructions to shared memory in 95 some local code, and we use only reading instructions (read only), 96 then probably it's safe to use pointers to different types for reading. 97 */ 98 99 100 101 #ifdef PPMD_32BIT 102 103 #define Ppmd_Ref_Type(type) type * 104 #define Ppmd_GetRef(p, ptr) (ptr) 105 #define Ppmd_GetPtr(p, ptr) (ptr) 106 #define Ppmd_GetPtr_Type(p, ptr, note_type) (ptr) 107 108 #else 109 110 #define Ppmd_Ref_Type(type) UInt32 111 #define Ppmd_GetRef(p, ptr) ((UInt32)((Byte *)(ptr) - (p)->Base)) 112 #define Ppmd_GetPtr(p, offs) ((void *)((p)->Base + (offs))) 113 #define Ppmd_GetPtr_Type(p, offs, type) ((type *)Ppmd_GetPtr(p, offs)) 114 115 #endif // PPMD_32BIT 116 117 118 typedef Ppmd_Ref_Type(CPpmd_State) CPpmd_State_Ref; 119 typedef Ppmd_Ref_Type(void) CPpmd_Void_Ref; 120 typedef Ppmd_Ref_Type(Byte) CPpmd_Byte_Ref; 121 122 123 /* 124 #ifdef MY_CPU_LE_UNALIGN 125 // the unaligned 32-bit access latency can be too large, if the data is not in L1 cache. 126 #define Ppmd_GET_SUCCESSOR(p) ((CPpmd_Void_Ref)*(const UInt32 *)(const void *)&(p)->Successor_0) 127 #define Ppmd_SET_SUCCESSOR(p, v) *(UInt32 *)(void *)(void *)&(p)->Successor_0 = (UInt32)(v) 128 129 #else 130 */ 131 132 /* 133 We can write 16-bit halves to 32-bit (Successor) field in any selected order. 134 But the native order is more consistent way. 135 So we use the native order, if LE/BE order can be detected here at compile time. 136 */ 137 138 #ifdef MY_CPU_BE 139 140 #define Ppmd_GET_SUCCESSOR(p) \ 141 ( (CPpmd_Void_Ref) (((UInt32)(p)->Successor_0 << 16) | (p)->Successor_1) ) 142 143 #define Ppmd_SET_SUCCESSOR(p, v) { \ 144 (p)->Successor_0 = (UInt16)(((UInt32)(v) >> 16) /* & 0xFFFF */); \ 145 (p)->Successor_1 = (UInt16)((UInt32)(v) /* & 0xFFFF */); } 146 147 #else 148 149 #define Ppmd_GET_SUCCESSOR(p) \ 150 ( (CPpmd_Void_Ref) ((p)->Successor_0 | ((UInt32)(p)->Successor_1 << 16)) ) 151 152 #define Ppmd_SET_SUCCESSOR(p, v) { \ 153 (p)->Successor_0 = (UInt16)((UInt32)(v) /* & 0xFFFF */); \ 154 (p)->Successor_1 = (UInt16)(((UInt32)(v) >> 16) /* & 0xFFFF */); } 155 156 #endif 157 158 // #endif 159 160 161 #define PPMD_SetAllBitsIn256Bytes(p) \ 162 { size_t z; for (z = 0; z < 256 / sizeof(p[0]); z += 8) { \ 163 p[z+7] = p[z+6] = p[z+5] = p[z+4] = p[z+3] = p[z+2] = p[z+1] = p[z+0] = ~(size_t)0; }} 164 165 EXTERN_C_END 166 167 #endif 168