10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
pub const RangeDecoder = struct {
range: u32,
code: u32,
pub fn init(reader: *Reader) !RangeDecoder {
var counter: u64 = 0;
return initCounting(reader, &counter);
}
pub fn initCounting(reader: *Reader, n_read: *u64) !RangeDecoder {
const reserved = try reader.takeByte();
n_read.* += 1;
if (reserved != 0) return error.InvalidRangeCode;
const code = try reader.takeInt(u32, .big);
n_read.* += 4;
return .{
.range = 0xFFFF_FFFF,
.code = code,
};
}
pub fn isFinished(self: RangeDecoder) bool {
return self.code == 0;
}
fn normalize(self: *RangeDecoder, reader: *Reader, n_read: *u64) !void {
if (self.range < 0x0100_0000) {
self.range <<= 8;
self.code = (self.code << 8) ^ @as(u32, try reader.takeByte());
n_read.* += 1;
}
}
fn getBit(self: *RangeDecoder, reader: *Reader, n_read: *u64) !bool {
self.range >>= 1;
const bit = self.code >= self.range;
if (bit) self.code -= self.range;
try self.normalize(reader, n_read);
return bit;
}
pub fn get(self: *RangeDecoder, reader: *Reader, count: usize, n_read: *u64) !u32 {
var result: u32 = 0;
for (0..count) |_| {
result = (result << 1) ^ @intFromBool(try self.getBit(reader, n_read));
}
return result;
}
pub fn decodeBit(self: *RangeDecoder, reader: *Reader, prob: *u16, n_read: *u64) !bool {
const bound = (self.range >> 11) * prob.*;
if (self.code < bound) {
prob.* += (0x800 - prob.*) >> 5;
self.range = bound;
try self.normalize(reader, n_read);
return false;
} else {
prob.* -= prob.* >> 5;
self.code -= bound;
self.range -= bound;
try self.normalize(reader, n_read);
return true;
}
}
fn parseBitTree(
self: *RangeDecoder,
reader: *Reader,
num_bits: u5,
probs: []u16,
n_read: *u64,
) !u32 {
var tmp: u32 = 1;
var i: @TypeOf(num_bits) = 0;
while (i < num_bits) : (i += 1) {
const bit = try self.decodeBit(reader, &probs[tmp], n_read);
tmp = (tmp << 1) ^ @intFromBool(bit);
}
return tmp - (@as(u32, 1) << num_bits);
}
pub fn parseReverseBitTree(
self: *RangeDecoder,
reader: *Reader,
num_bits: u5,
probs: []u16,
offset: usize,
n_read: *u64,
) !u32 {
var result: u32 = 0;
var tmp: usize = 1;
var i: @TypeOf(num_bits) = 0;
while (i < num_bits) : (i += 1) {
const bit = @intFromBool(try self.decodeBit(reader, &probs[offset + tmp], n_read));
tmp = (tmp << 1) ^ bit;
result ^= @as(u32, bit) << i;
}
return result;
}
}
