← Back to branch summary

~ubuntu-branches/ubuntu/precise/p7zip/precise-updates

« back to all changes in this revision

Viewing changes to CPP/7zip/Compress/RangeCoder/RangeCoder.h

  • Committer: Bazaar Package Importer
  • Author(s): Mohammed Adnène Trojette
  • Date: 2009-02-14 20:12:27 UTC
  • mfrom: (1.1.11 upstream) (2.1.3 sid)
  • Revision ID: james.westby@ubuntu.com-20090214201227-go63qxm9ozfdma60
Tags: 4.65~dfsg.1-1
* New upstream release.
* Remove wx2.8 Build-Depends added by mistakes (7zG is not yet
  intended to be built).
* Use dh_clean without -k.

Show diffs side-by-side

added added

removed removed

Lines of Context:
CPP/7zip/Compress/RangeCoder/RangeCoder.h
1
 
// Compress/RangeCoder/RangeCoder.h
2
 
 
3
 
#ifndef __COMPRESS_RANGECODER_H
4
 
#define __COMPRESS_RANGECODER_H
5
 
 
6
 
#include "../../Common/InBuffer.h"
7
 
#include "../../Common/OutBuffer.h"
8
 
 
9
 
namespace NCompress {
10
 
namespace NRangeCoder {
11
 
 
12
 
const int kNumTopBits = 24;
13
 
const UInt32 kTopValue = (1 << kNumTopBits);
14
 
 
15
 
class CEncoder
16
 
{
17
 
  UInt32 _cacheSize;
18
 
  Byte _cache;
19
 
public:
20
 
  UInt64 Low;
21
 
  UInt32 Range;
22
 
  COutBuffer Stream;
23
 
  bool Create(UInt32 bufferSize) { return Stream.Create(bufferSize); }
24
 
 
25
 
  void SetStream(ISequentialOutStream *stream) { Stream.SetStream(stream); }
26
 
  void Init()
27
 
  {
28
 
    Stream.Init();
29
 
    Low = 0;
30
 
    Range = 0xFFFFFFFF;
31
 
    _cacheSize = 1;
32
 
    _cache = 0;
33
 
  }
34
 
 
35
 
  void FlushData()
36
 
  {
37
 
    // Low += 1; 
38
 
    for(int i = 0; i < 5; i++)
39
 
      ShiftLow();
40
 
  }
41
 
 
42
 
  HRESULT FlushStream() { return Stream.Flush();  }
43
 
 
44
 
  void ReleaseStream() { Stream.ReleaseStream(); }
45
 
 
46
 
  void Encode(UInt32 start, UInt32 size, UInt32 total)
47
 
  {
48
 
    Low += start * (Range /= total);
49
 
    Range *= size;
50
 
    while (Range < kTopValue)
51
 
    {
52
 
      Range <<= 8;
53
 
      ShiftLow();
54
 
    }
55
 
  }
56
 
 
57
 
  void ShiftLow()
58
 
  {
59
 
    if ((UInt32)Low < (UInt32)0xFF000000 || (int)(Low >> 32) != 0) 
60
 
    {
61
 
      Byte temp = _cache;
62
 
      do
63
 
      {
64
 
        Stream.WriteByte((Byte)(temp + (Byte)(Low >> 32)));
65
 
        temp = 0xFF;
66
 
      }
67
 
      while(--_cacheSize != 0);
68
 
      _cache = (Byte)((UInt32)Low >> 24);                      
69
 
    } 
70
 
    _cacheSize++;                               
71
 
    Low = (UInt32)Low << 8;                           
72
 
  }
73
 
  
74
 
  void EncodeDirectBits(UInt32 value, int numBits)
75
 
  {
76
 
    for (numBits--; numBits >= 0; numBits--)
77
 
    {
78
 
      Range >>= 1;
79
 
      Low += Range & (0 - ((value >> numBits) & 1));
80
 
      if (Range < kTopValue)
81
 
      {
82
 
        Range <<= 8;
83
 
        ShiftLow();
84
 
      }
85
 
    }
86
 
  }
87
 
 
88
 
  void EncodeBit(UInt32 size0, UInt32 numTotalBits, UInt32 symbol)
89
 
  {
90
 
    UInt32 newBound = (Range >> numTotalBits) * size0;
91
 
    if (symbol == 0)
92
 
      Range = newBound;
93
 
    else
94
 
    {
95
 
      Low += newBound;
96
 
      Range -= newBound;
97
 
    }
98
 
    while (Range < kTopValue)
99
 
    {
100
 
      Range <<= 8;
101
 
      ShiftLow();
102
 
    }
103
 
  }
104
 
 
105
 
  UInt64 GetProcessedSize() {  return Stream.GetProcessedSize() + _cacheSize + 4; }
106
 
};
107
 
 
108
 
class CDecoder
109
 
{
110
 
public:
111
 
  CInBuffer Stream;
112
 
  UInt32 Range;
113
 
  UInt32 Code;
114
 
  bool Create(UInt32 bufferSize) { return Stream.Create(bufferSize); }
115
 
 
116
 
  void Normalize()
117
 
  {
118
 
    while (Range < kTopValue)
119
 
    {
120
 
      Code = (Code << 8) | Stream.ReadByte();
121
 
      Range <<= 8;
122
 
    }
123
 
  }
124
 
  
125
 
  void SetStream(ISequentialInStream *stream) { Stream.SetStream(stream); }
126
 
  void Init()
127
 
  {
128
 
    Stream.Init();
129
 
    Code = 0;
130
 
    Range = 0xFFFFFFFF;
131
 
    for(int i = 0; i < 5; i++)
132
 
      Code = (Code << 8) | Stream.ReadByte();
133
 
  }
134
 
 
135
 
  void ReleaseStream() { Stream.ReleaseStream(); }
136
 
 
137
 
  UInt32 GetThreshold(UInt32 total)
138
 
  {
139
 
    return (Code) / ( Range /= total);
140
 
  }
141
 
 
142
 
  void Decode(UInt32 start, UInt32 size)
143
 
  {
144
 
    Code -= start * Range;
145
 
    Range *= size;
146
 
    Normalize();
147
 
  }
148
 
 
149
 
  UInt32 DecodeDirectBits(int numTotalBits)
150
 
  {
151
 
    UInt32 range = Range;
152
 
    UInt32 code = Code;        
153
 
    UInt32 result = 0;
154
 
    for (int i = numTotalBits; i != 0; i--)
155
 
    {
156
 
      range >>= 1;
157
 
      /*
158
 
      result <<= 1;
159
 
      if (code >= range)
160
 
      {
161
 
        code -= range;
162
 
        result |= 1;
163
 
      }
164
 
      */
165
 
      UInt32 t = (code - range) >> 31;
166
 
      code -= range & (t - 1);
167
 
      result = (result << 1) | (1 - t);
168
 
 
169
 
      if (range < kTopValue)
170
 
      {
171
 
        code = (code << 8) | Stream.ReadByte();
172
 
        range <<= 8; 
173
 
      }
174
 
    }
175
 
    Range = range;
176
 
    Code = code;
177
 
    return result;
178
 
  }
179
 
 
180
 
  UInt32 DecodeBit(UInt32 size0, UInt32 numTotalBits)
181
 
  {
182
 
    UInt32 newBound = (Range >> numTotalBits) * size0;
183
 
    UInt32 symbol;
184
 
    if (Code < newBound)
185
 
    {
186
 
      symbol = 0;
187
 
      Range = newBound;
188
 
    }
189
 
    else
190
 
    {
191
 
      symbol = 1;
192
 
      Code -= newBound;
193
 
      Range -= newBound;
194
 
    }
195
 
    Normalize();
196
 
    return symbol;
197
 
  }
198
 
 
199
 
  UInt64 GetProcessedSize() {return Stream.GetProcessedSize(); }
200
 
};
201
 
 
202
 
}}
203
 
 
204
 
#endif