← 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.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.h
 
1
// Compress/RangeCoder.h
 
2
 
 
3
#ifndef __COMPRESS_RANGE_CODER_H
 
4
#define __COMPRESS_RANGE_CODER_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