1 /* Ppmd.h -- PPMD codec common code 2 2023-03-05 : Igor Pavlov : Public domain 3 This code is based on PPMd var.H (2001): Dmitry Shkarin : Public domain */ 4 5 #ifndef ZIP7_INC_PPMD_H 6 #define ZIP7_INC_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) \ 52 { if ((p)->Shift < PPMD_PERIOD_BITS && --(p)->Count == 0) \ 53 { (p)->Summ = (UInt16)((p)->Summ << 1); \ 54 (p)->Count = (Byte)(3 << (p)->Shift++); }} 55 56 57 typedef struct 58 { 59 Byte Symbol; 60 Byte Freq; 61 UInt16 Successor_0; 62 UInt16 Successor_1; 63 } CPpmd_State; 64 65 typedef struct CPpmd_State2_ 66 { 67 Byte Symbol; 68 Byte Freq; 69 } CPpmd_State2; 70 71 typedef struct CPpmd_State4_ 72 { 73 UInt16 Successor_0; 74 UInt16 Successor_1; 75 } CPpmd_State4; 76 77 MY_CPU_pragma_pop 78 79 /* 80 PPMD code can write full CPpmd_State structure data to CPpmd*_Context 81 at (byte offset = 2) instead of some fields of original CPpmd*_Context structure. 82 83 If we use pointers to different types, but that point to shared 84 memory space, we can have aliasing problem (strict aliasing). 85 86 XLC compiler in -O2 mode can change the order of memory write instructions 87 in relation to read instructions, if we have use pointers to different types. 88 89 To solve that aliasing problem we use combined CPpmd*_Context structure 90 with unions that contain the fields from both structures: 91 the original CPpmd*_Context and CPpmd_State. 92 So we can access the fields from both structures via one pointer, 93 and the compiler doesn't change the order of write instructions 94 in relation to read instructions. 95 96 If we don't use memory write instructions to shared memory in 97 some local code, and we use only reading instructions (read only), 98 then probably it's safe to use pointers to different types for reading. 99 */ 100 101 102 103 #ifdef PPMD_32BIT 104 105 #define Ppmd_Ref_Type(type) type * 106 #define Ppmd_GetRef(p, ptr) (ptr) 107 #define Ppmd_GetPtr(p, ptr) (ptr) 108 #define Ppmd_GetPtr_Type(p, ptr, note_type) (ptr) 109 110 #else 111 112 #define Ppmd_Ref_Type(type) UInt32 113 #define Ppmd_GetRef(p, ptr) ((UInt32)((Byte *)(ptr) - (p)->Base)) 114 #define Ppmd_GetPtr(p, offs) ((void *)((p)->Base + (offs))) 115 #define Ppmd_GetPtr_Type(p, offs, type) ((type *)Ppmd_GetPtr(p, offs)) 116 117 #endif // PPMD_32BIT 118 119 120 typedef Ppmd_Ref_Type(CPpmd_State) CPpmd_State_Ref; 121 typedef Ppmd_Ref_Type(void) CPpmd_Void_Ref; 122 typedef Ppmd_Ref_Type(Byte) CPpmd_Byte_Ref; 123 124 125 /* 126 #ifdef MY_CPU_LE_UNALIGN 127 // the unaligned 32-bit access latency can be too large, if the data is not in L1 cache. 128 #define Ppmd_GET_SUCCESSOR(p) ((CPpmd_Void_Ref)*(const UInt32 *)(const void *)&(p)->Successor_0) 129 #define Ppmd_SET_SUCCESSOR(p, v) *(UInt32 *)(void *)(void *)&(p)->Successor_0 = (UInt32)(v) 130 131 #else 132 */ 133 134 /* 135 We can write 16-bit halves to 32-bit (Successor) field in any selected order. 136 But the native order is more consistent way. 137 So we use the native order, if LE/BE order can be detected here at compile time. 138 */ 139 140 #ifdef MY_CPU_BE 141 142 #define Ppmd_GET_SUCCESSOR(p) \ 143 ( (CPpmd_Void_Ref) (((UInt32)(p)->Successor_0 << 16) | (p)->Successor_1) ) 144 145 #define Ppmd_SET_SUCCESSOR(p, v) { \ 146 (p)->Successor_0 = (UInt16)(((UInt32)(v) >> 16) /* & 0xFFFF */); \ 147 (p)->Successor_1 = (UInt16)((UInt32)(v) /* & 0xFFFF */); } 148 149 #else 150 151 #define Ppmd_GET_SUCCESSOR(p) \ 152 ( (CPpmd_Void_Ref) ((p)->Successor_0 | ((UInt32)(p)->Successor_1 << 16)) ) 153 154 #define Ppmd_SET_SUCCESSOR(p, v) { \ 155 (p)->Successor_0 = (UInt16)((UInt32)(v) /* & 0xFFFF */); \ 156 (p)->Successor_1 = (UInt16)(((UInt32)(v) >> 16) /* & 0xFFFF */); } 157 158 #endif 159 160 // #endif 161 162 163 #define PPMD_SetAllBitsIn256Bytes(p) \ 164 { size_t z; for (z = 0; z < 256 / sizeof(p[0]); z += 8) { \ 165 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; }} 166 167 EXTERN_C_END 168 169 #endif 170