other-licenses/7zstub/src/7zip/Compress/RangeCoder/RangeCoderBitTree.h@97036ab72558 (annotated)
other-licenses/7zstub/src/7zip/Compress/RangeCoder/RangeCoderBitTree.h
Tue, 06 Jan 2015 21:39:09 +0100
- author
- Michael Schloh von Bennewitz <michael@schloh.com>
- date
- Tue, 06 Jan 2015 21:39:09 +0100
- branch
- TOR_BUG_9701
- changeset 8
- 97036ab72558
- permissions
- -rw-r--r--
Conditionally force memory storage according to privacy.thirdparty.isolate;
This solves Tor bug #9701, complying with disk avoidance documented in
https://www.torproject.org/projects/torbrowser/design/#disk-avoidance.
| michael@0 | 1 | // Compress/RangeCoder/RangeCoderBitTree.h |
| michael@0 | 2 | |
| michael@0 | 3 | #ifndef __COMPRESS_RANGECODER_BIT_TREE_H |
| michael@0 | 4 | #define __COMPRESS_RANGECODER_BIT_TREE_H |
| michael@0 | 5 | |
| michael@0 | 6 | #include "RangeCoderBit.h" |
| michael@0 | 7 | #include "RangeCoderOpt.h" |
| michael@0 | 8 | |
| michael@0 | 9 | namespace NCompress { |
| michael@0 | 10 | namespace NRangeCoder { |
| michael@0 | 11 | |
| michael@0 | 12 | template <int numMoveBits, int NumBitLevels> |
| michael@0 | 13 | class CBitTreeEncoder |
| michael@0 | 14 | { |
| michael@0 | 15 | CBitEncoder<numMoveBits> Models[1 << NumBitLevels]; |
| michael@0 | 16 | public: |
| michael@0 | 17 | void Init() |
| michael@0 | 18 | { |
| michael@0 | 19 | for(UInt32 i = 1; i < (1 << NumBitLevels); i++) |
| michael@0 | 20 | Models[i].Init(); |
| michael@0 | 21 | } |
| michael@0 | 22 | void Encode(CEncoder *rangeEncoder, UInt32 symbol) |
| michael@0 | 23 | { |
| michael@0 | 24 | UInt32 modelIndex = 1; |
| michael@0 | 25 | for (int bitIndex = NumBitLevels; bitIndex != 0 ;) |
| michael@0 | 26 | { |
| michael@0 | 27 | bitIndex--; |
| michael@0 | 28 | UInt32 bit = (symbol >> bitIndex) & 1; |
| michael@0 | 29 | Models[modelIndex].Encode(rangeEncoder, bit); |
| michael@0 | 30 | modelIndex = (modelIndex << 1) | bit; |
| michael@0 | 31 | } |
| michael@0 | 32 | }; |
| michael@0 | 33 | void ReverseEncode(CEncoder *rangeEncoder, UInt32 symbol) |
| michael@0 | 34 | { |
| michael@0 | 35 | UInt32 modelIndex = 1; |
| michael@0 | 36 | for (int i = 0; i < NumBitLevels; i++) |
| michael@0 | 37 | { |
| michael@0 | 38 | UInt32 bit = symbol & 1; |
| michael@0 | 39 | Models[modelIndex].Encode(rangeEncoder, bit); |
| michael@0 | 40 | modelIndex = (modelIndex << 1) | bit; |
| michael@0 | 41 | symbol >>= 1; |
| michael@0 | 42 | } |
| michael@0 | 43 | } |
| michael@0 | 44 | UInt32 GetPrice(UInt32 symbol) const |
| michael@0 | 45 | { |
| michael@0 | 46 | symbol |= (1 << NumBitLevels); |
| michael@0 | 47 | UInt32 price = 0; |
| michael@0 | 48 | while (symbol != 1) |
| michael@0 | 49 | { |
| michael@0 | 50 | price += Models[symbol >> 1].GetPrice(symbol & 1); |
| michael@0 | 51 | symbol >>= 1; |
| michael@0 | 52 | } |
| michael@0 | 53 | return price; |
| michael@0 | 54 | } |
| michael@0 | 55 | UInt32 ReverseGetPrice(UInt32 symbol) const |
| michael@0 | 56 | { |
| michael@0 | 57 | UInt32 price = 0; |
| michael@0 | 58 | UInt32 modelIndex = 1; |
| michael@0 | 59 | for (int i = NumBitLevels; i != 0; i--) |
| michael@0 | 60 | { |
| michael@0 | 61 | UInt32 bit = symbol & 1; |
| michael@0 | 62 | symbol >>= 1; |
| michael@0 | 63 | price += Models[modelIndex].GetPrice(bit); |
| michael@0 | 64 | modelIndex = (modelIndex << 1) | bit; |
| michael@0 | 65 | } |
| michael@0 | 66 | return price; |
| michael@0 | 67 | } |
| michael@0 | 68 | }; |
| michael@0 | 69 | |
| michael@0 | 70 | template <int numMoveBits, int NumBitLevels> |
| michael@0 | 71 | class CBitTreeDecoder |
| michael@0 | 72 | { |
| michael@0 | 73 | CBitDecoder<numMoveBits> Models[1 << NumBitLevels]; |
| michael@0 | 74 | public: |
| michael@0 | 75 | void Init() |
| michael@0 | 76 | { |
| michael@0 | 77 | for(UInt32 i = 1; i < (1 << NumBitLevels); i++) |
| michael@0 | 78 | Models[i].Init(); |
| michael@0 | 79 | } |
| michael@0 | 80 | UInt32 Decode(CDecoder *rangeDecoder) |
| michael@0 | 81 | { |
| michael@0 | 82 | UInt32 modelIndex = 1; |
| michael@0 | 83 | RC_INIT_VAR |
| michael@0 | 84 | for(int bitIndex = NumBitLevels; bitIndex != 0; bitIndex--) |
| michael@0 | 85 | { |
| michael@0 | 86 | // modelIndex = (modelIndex << 1) + Models[modelIndex].Decode(rangeDecoder); |
| michael@0 | 87 | RC_GETBIT(numMoveBits, Models[modelIndex].Prob, modelIndex) |
| michael@0 | 88 | } |
| michael@0 | 89 | RC_FLUSH_VAR |
| michael@0 | 90 | return modelIndex - (1 << NumBitLevels); |
| michael@0 | 91 | }; |
| michael@0 | 92 | UInt32 ReverseDecode(CDecoder *rangeDecoder) |
| michael@0 | 93 | { |
| michael@0 | 94 | UInt32 modelIndex = 1; |
| michael@0 | 95 | UInt32 symbol = 0; |
| michael@0 | 96 | RC_INIT_VAR |
| michael@0 | 97 | for(int bitIndex = 0; bitIndex < NumBitLevels; bitIndex++) |
| michael@0 | 98 | { |
| michael@0 | 99 | // UInt32 bit = Models[modelIndex].Decode(rangeDecoder); |
| michael@0 | 100 | // modelIndex <<= 1; |
| michael@0 | 101 | // modelIndex += bit; |
| michael@0 | 102 | // symbol |= (bit << bitIndex); |
| michael@0 | 103 | RC_GETBIT2(numMoveBits, Models[modelIndex].Prob, modelIndex, ; , symbol |= (1 << bitIndex)) |
| michael@0 | 104 | } |
| michael@0 | 105 | RC_FLUSH_VAR |
| michael@0 | 106 | return symbol; |
| michael@0 | 107 | } |
| michael@0 | 108 | }; |
| michael@0 | 109 | |
| michael@0 | 110 | template <int numMoveBits> |
| michael@0 | 111 | void ReverseBitTreeEncode(CBitEncoder<numMoveBits> *Models, |
| michael@0 | 112 | CEncoder *rangeEncoder, int NumBitLevels, UInt32 symbol) |
| michael@0 | 113 | { |
| michael@0 | 114 | UInt32 modelIndex = 1; |
| michael@0 | 115 | for (int i = 0; i < NumBitLevels; i++) |
| michael@0 | 116 | { |
| michael@0 | 117 | UInt32 bit = symbol & 1; |
| michael@0 | 118 | Models[modelIndex].Encode(rangeEncoder, bit); |
| michael@0 | 119 | modelIndex = (modelIndex << 1) | bit; |
| michael@0 | 120 | symbol >>= 1; |
| michael@0 | 121 | } |
| michael@0 | 122 | } |
| michael@0 | 123 | |
| michael@0 | 124 | template <int numMoveBits> |
| michael@0 | 125 | UInt32 ReverseBitTreeGetPrice(CBitEncoder<numMoveBits> *Models, |
| michael@0 | 126 | UInt32 NumBitLevels, UInt32 symbol) |
| michael@0 | 127 | { |
| michael@0 | 128 | UInt32 price = 0; |
| michael@0 | 129 | UInt32 modelIndex = 1; |
| michael@0 | 130 | for (int i = NumBitLevels; i != 0; i--) |
| michael@0 | 131 | { |
| michael@0 | 132 | UInt32 bit = symbol & 1; |
| michael@0 | 133 | symbol >>= 1; |
| michael@0 | 134 | price += Models[modelIndex].GetPrice(bit); |
| michael@0 | 135 | modelIndex = (modelIndex << 1) | bit; |
| michael@0 | 136 | } |
| michael@0 | 137 | return price; |
| michael@0 | 138 | } |
| michael@0 | 139 | |
| michael@0 | 140 | template <int numMoveBits> |
| michael@0 | 141 | UInt32 ReverseBitTreeDecode(CBitDecoder<numMoveBits> *Models, |
| michael@0 | 142 | CDecoder *rangeDecoder, int NumBitLevels) |
| michael@0 | 143 | { |
| michael@0 | 144 | UInt32 modelIndex = 1; |
| michael@0 | 145 | UInt32 symbol = 0; |
| michael@0 | 146 | RC_INIT_VAR |
| michael@0 | 147 | for(int bitIndex = 0; bitIndex < NumBitLevels; bitIndex++) |
| michael@0 | 148 | { |
| michael@0 | 149 | // UInt32 bit = Models[modelIndex].Decode(rangeDecoder); |
| michael@0 | 150 | // modelIndex <<= 1; |
| michael@0 | 151 | // modelIndex += bit; |
| michael@0 | 152 | // symbol |= (bit << bitIndex); |
| michael@0 | 153 | RC_GETBIT2(numMoveBits, Models[modelIndex].Prob, modelIndex, ; , symbol |= (1 << bitIndex)) |
| michael@0 | 154 | } |
| michael@0 | 155 | RC_FLUSH_VAR |
| michael@0 | 156 | return symbol; |
| michael@0 | 157 | } |
| michael@0 | 158 | |
| michael@0 | 159 | }} |
| michael@0 | 160 | |
| michael@0 | 161 | #endif |
