Line data Source code
1 : /* This Source Code Form is subject to the terms of the Mozilla Public
2 : * License, v. 2.0. If a copy of the MPL was not distributed with this
3 : * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
4 :
5 : #include "RiceDeltaDecoder.h"
6 :
7 : namespace {
8 :
9 : ////////////////////////////////////////////////////////////////////////
10 : // BitBuffer is copied and modified from webrtc/base/bitbuffer.h
11 : //
12 :
13 : /*
14 : * Copyright 2015 The WebRTC Project Authors. All rights reserved.
15 : *
16 : * Use of this source code is governed by a BSD-style license
17 : * that can be found in the LICENSE file in the root of the source
18 : * tree (webrtc/base/bitbuffer.h/cc). An additional intellectual property
19 : * rights grant can be found in the file PATENTS. All contributing
20 : * project authors may be found in the AUTHORS file in the root of
21 : * the source tree.
22 : */
23 :
24 : class BitBuffer {
25 : public:
26 : BitBuffer(const uint8_t* bytes, size_t byte_count);
27 :
28 : // The remaining bits in the byte buffer.
29 : uint64_t RemainingBitCount() const;
30 :
31 : // Reads bit-sized values from the buffer. Returns false if there isn't enough
32 : // data left for the specified bit count..
33 : bool ReadBits(uint32_t* val, size_t bit_count);
34 :
35 : // Peeks bit-sized values from the buffer. Returns false if there isn't enough
36 : // data left for the specified number of bits. Doesn't move the current
37 : // offset.
38 : bool PeekBits(uint32_t* val, size_t bit_count);
39 :
40 : // Reads the exponential golomb encoded value at the current offset.
41 : // Exponential golomb values are encoded as:
42 : // 1) x = source val + 1
43 : // 2) In binary, write [countbits(x) - 1] 1s, then x
44 : // To decode, we count the number of leading 1 bits, read that many + 1 bits,
45 : // and increment the result by 1.
46 : // Returns false if there isn't enough data left for the specified type, or if
47 : // the value wouldn't fit in a uint32_t.
48 : bool ReadExponentialGolomb(uint32_t* val);
49 :
50 : // Moves current position |bit_count| bits forward. Returns false if
51 : // there aren't enough bits left in the buffer.
52 : bool ConsumeBits(size_t bit_count);
53 :
54 : protected:
55 : const uint8_t* const bytes_;
56 : // The total size of |bytes_|.
57 : size_t byte_count_;
58 : // The current offset, in bytes, from the start of |bytes_|.
59 : size_t byte_offset_;
60 : // The current offset, in bits, into the current byte.
61 : size_t bit_offset_;
62 : };
63 :
64 : } // end of unnamed namespace
65 :
66 : static void
67 0 : ReverseByte(uint8_t& b)
68 : {
69 0 : b = (b & 0xF0) >> 4 | (b & 0x0F) << 4;
70 0 : b = (b & 0xCC) >> 2 | (b & 0x33) << 2;
71 0 : b = (b & 0xAA) >> 1 | (b & 0x55) << 1;
72 0 : }
73 :
74 : namespace mozilla {
75 : namespace safebrowsing {
76 :
77 0 : RiceDeltaDecoder::RiceDeltaDecoder(uint8_t* aEncodedData,
78 0 : size_t aEncodedDataSize)
79 : : mEncodedData(aEncodedData)
80 0 : , mEncodedDataSize(aEncodedDataSize)
81 : {
82 0 : }
83 :
84 : bool
85 0 : RiceDeltaDecoder::Decode(uint32_t aRiceParameter,
86 : uint32_t aFirstValue,
87 : uint32_t aNumEntries,
88 : uint32_t* aDecodedData)
89 : {
90 : // Reverse each byte before reading bits from the byte buffer.
91 0 : for (size_t i = 0; i < mEncodedDataSize; i++) {
92 0 : ReverseByte(mEncodedData[i]);
93 : }
94 :
95 0 : BitBuffer bitBuffer(mEncodedData, mEncodedDataSize);
96 :
97 : // q = quotient
98 : // r = remainder
99 : // k = RICE parameter
100 0 : const uint32_t k = aRiceParameter;
101 0 : aDecodedData[0] = aFirstValue;
102 0 : for (uint32_t i = 0; i < aNumEntries; i++) {
103 : // Read the quotient of N.
104 : uint32_t q;
105 0 : if (!bitBuffer.ReadExponentialGolomb(&q)) {
106 0 : LOG(("Encoded data underflow!"));
107 0 : return false;
108 : }
109 :
110 : // Read the remainder of N, one bit at a time.
111 0 : uint32_t r = 0;
112 0 : for (uint32_t j = 0; j < k; j++) {
113 0 : uint32_t b = 0;
114 0 : if (!bitBuffer.ReadBits(&b, 1)) {
115 : // Insufficient bits. Just leave them as zeros.
116 0 : break;
117 : }
118 : // Add the bit to the right position so that it's in Little Endian order.
119 0 : r |= b << j;
120 : }
121 :
122 : // Caculate N from q,r,k.
123 0 : uint32_t N = (q << k) + r;
124 :
125 : // We start filling aDecodedData from [1].
126 0 : aDecodedData[i + 1] = N + aDecodedData[i];
127 : }
128 :
129 0 : return true;
130 : }
131 :
132 : } // end of namespace mozilla
133 : } // end of namespace safebrowsing
134 :
135 : namespace {
136 : //////////////////////////////////////////////////////////////////////////
137 : // The BitBuffer impl is copied and modified from webrtc/base/bitbuffer.cc
138 : //
139 :
140 : // Returns the lowest (right-most) |bit_count| bits in |byte|.
141 0 : uint8_t LowestBits(uint8_t byte, size_t bit_count) {
142 0 : return byte & ((1 << bit_count) - 1);
143 : }
144 :
145 : // Returns the highest (left-most) |bit_count| bits in |byte|, shifted to the
146 : // lowest bits (to the right).
147 0 : uint8_t HighestBits(uint8_t byte, size_t bit_count) {
148 0 : MOZ_ASSERT(bit_count < 8u);
149 0 : uint8_t shift = 8 - static_cast<uint8_t>(bit_count);
150 0 : uint8_t mask = 0xFF << shift;
151 0 : return (byte & mask) >> shift;
152 : }
153 :
154 0 : BitBuffer::BitBuffer(const uint8_t* bytes, size_t byte_count)
155 0 : : bytes_(bytes), byte_count_(byte_count), byte_offset_(), bit_offset_() {
156 0 : MOZ_ASSERT(static_cast<uint64_t>(byte_count_) <=
157 : std::numeric_limits<uint32_t>::max());
158 0 : }
159 :
160 0 : uint64_t BitBuffer::RemainingBitCount() const {
161 0 : return (static_cast<uint64_t>(byte_count_) - byte_offset_) * 8 - bit_offset_;
162 : }
163 :
164 0 : bool BitBuffer::PeekBits(uint32_t* val, size_t bit_count) {
165 0 : if (!val || bit_count > RemainingBitCount() || bit_count > 32) {
166 0 : return false;
167 : }
168 0 : const uint8_t* bytes = bytes_ + byte_offset_;
169 0 : size_t remaining_bits_in_current_byte = 8 - bit_offset_;
170 0 : uint32_t bits = LowestBits(*bytes++, remaining_bits_in_current_byte);
171 : // If we're reading fewer bits than what's left in the current byte, just
172 : // return the portion of this byte that we need.
173 0 : if (bit_count < remaining_bits_in_current_byte) {
174 0 : *val = HighestBits(bits, bit_offset_ + bit_count);
175 0 : return true;
176 : }
177 : // Otherwise, subtract what we've read from the bit count and read as many
178 : // full bytes as we can into bits.
179 0 : bit_count -= remaining_bits_in_current_byte;
180 0 : while (bit_count >= 8) {
181 0 : bits = (bits << 8) | *bytes++;
182 0 : bit_count -= 8;
183 : }
184 : // Whatever we have left is smaller than a byte, so grab just the bits we need
185 : // and shift them into the lowest bits.
186 0 : if (bit_count > 0) {
187 0 : bits <<= bit_count;
188 0 : bits |= HighestBits(*bytes, bit_count);
189 : }
190 0 : *val = bits;
191 0 : return true;
192 : }
193 :
194 0 : bool BitBuffer::ReadBits(uint32_t* val, size_t bit_count) {
195 0 : return PeekBits(val, bit_count) && ConsumeBits(bit_count);
196 : }
197 :
198 0 : bool BitBuffer::ConsumeBits(size_t bit_count) {
199 0 : if (bit_count > RemainingBitCount()) {
200 0 : return false;
201 : }
202 :
203 0 : byte_offset_ += (bit_offset_ + bit_count) / 8;
204 0 : bit_offset_ = (bit_offset_ + bit_count) % 8;
205 0 : return true;
206 : }
207 :
208 0 : bool BitBuffer::ReadExponentialGolomb(uint32_t* val) {
209 0 : if (!val) {
210 0 : return false;
211 : }
212 :
213 0 : *val = 0;
214 :
215 : // Count the number of leading 0 bits by peeking/consuming them one at a time.
216 0 : size_t one_bit_count = 0;
217 : uint32_t peeked_bit;
218 0 : while (PeekBits(&peeked_bit, 1) && peeked_bit == 1) {
219 0 : one_bit_count++;
220 0 : ConsumeBits(1);
221 : }
222 0 : if (!ConsumeBits(1)) {
223 0 : return false; // The stream is incorrectly terminated at '1'.
224 : }
225 :
226 0 : *val = one_bit_count;
227 0 : return true;
228 : }
229 : }
|
