1 // Copyright 2014 The PDFium Authors
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4
5 // Original code copyright 2014 Foxit Software Inc. http://www.foxitsoftware.com
6
7 #include "core/fxcodec/jbig2/JBig2_HuffmanTable.h"
8
9 #include <iterator>
10 #include <limits>
11
12 #include "core/fxcodec/jbig2/JBig2_BitStream.h"
13 #include "core/fxcodec/jbig2/JBig2_Context.h"
14 #include "core/fxcrt/check.h"
15 #include "core/fxcrt/compiler_specific.h"
16 #include "core/fxcrt/fx_safe_types.h"
17 #include "core/fxcrt/unowned_ptr_exclusion.h"
18
19 namespace {
20
21 struct JBig2TableLine {
22 uint8_t PREFLEN;
23 uint8_t RANDELEN;
24 int32_t RANGELOW;
25 };
26
27 struct HuffmanTable {
28 bool HTOOB;
29 UNOWNED_PTR_EXCLUSION const JBig2TableLine* lines;
30 size_t size;
31 };
32
33 constexpr JBig2TableLine kTableLine1[] = {{1, 4, 0},
34 {2, 8, 16},
35 {3, 16, 272},
36 {0, 32, -1},
37 {3, 32, 65808}};
38
39 constexpr JBig2TableLine kTableLine2[] = {{1, 0, 0}, {2, 0, 1}, {3, 0, 2},
40 {4, 3, 3}, {5, 6, 11}, {0, 32, -1},
41 {6, 32, 75}, {6, 0, 0}};
42
43 constexpr JBig2TableLine kTableLine3[] = {
44 {8, 8, -256}, {1, 0, 0}, {2, 0, 1}, {3, 0, 2}, {4, 3, 3},
45 {5, 6, 11}, {8, 32, -257}, {7, 32, 75}, {6, 0, 0}};
46
47 constexpr JBig2TableLine kTableLine4[] = {{1, 0, 1}, {2, 0, 2}, {3, 0, 3},
48 {4, 3, 4}, {5, 6, 12}, {0, 32, -1},
49 {5, 32, 76}};
50
51 constexpr JBig2TableLine kTableLine5[] = {{7, 8, -255}, {1, 0, 1}, {2, 0, 2},
52 {3, 0, 3}, {4, 3, 4}, {5, 6, 12},
53 {7, 32, -256}, {6, 32, 76}};
54
55 constexpr JBig2TableLine kTableLine6[] = {
56 {5, 10, -2048}, {4, 9, -1024}, {4, 8, -512}, {4, 7, -256}, {5, 6, -128},
57 {5, 5, -64}, {4, 5, -32}, {2, 7, 0}, {3, 7, 128}, {3, 8, 256},
58 {4, 9, 512}, {4, 10, 1024}, {6, 32, -2049}, {6, 32, 2048}};
59
60 constexpr JBig2TableLine kTableLine7[] = {
61 {4, 9, -1024}, {3, 8, -512}, {4, 7, -256}, {5, 6, -128}, {5, 5, -64},
62 {4, 5, -32}, {4, 5, 0}, {5, 5, 32}, {5, 6, 64}, {4, 7, 128},
63 {3, 8, 256}, {3, 9, 512}, {3, 10, 1024}, {5, 32, -1025}, {5, 32, 2048}};
64
65 constexpr JBig2TableLine kTableLine8[] = {
66 {8, 3, -15}, {9, 1, -7}, {8, 1, -5}, {9, 0, -3}, {7, 0, -2},
67 {4, 0, -1}, {2, 1, 0}, {5, 0, 2}, {6, 0, 3}, {3, 4, 4},
68 {6, 1, 20}, {4, 4, 22}, {4, 5, 38}, {5, 6, 70}, {5, 7, 134},
69 {6, 7, 262}, {7, 8, 390}, {6, 10, 646}, {9, 32, -16}, {9, 32, 1670},
70 {2, 0, 0}};
71
72 constexpr JBig2TableLine kTableLine9[] = {
73 {8, 4, -31}, {9, 2, -15}, {8, 2, -11}, {9, 1, -7}, {7, 1, -5},
74 {4, 1, -3}, {3, 1, -1}, {3, 1, 1}, {5, 1, 3}, {6, 1, 5},
75 {3, 5, 7}, {6, 2, 39}, {4, 5, 43}, {4, 6, 75}, {5, 7, 139},
76 {5, 8, 267}, {6, 8, 523}, {7, 9, 779}, {6, 11, 1291}, {9, 32, -32},
77 {9, 32, 3339}, {2, 0, 0}};
78
79 constexpr JBig2TableLine kTableLine10[] = {
80 {7, 4, -21}, {8, 0, -5}, {7, 0, -4}, {5, 0, -3}, {2, 2, -2},
81 {5, 0, 2}, {6, 0, 3}, {7, 0, 4}, {8, 0, 5}, {2, 6, 6},
82 {5, 5, 70}, {6, 5, 102}, {6, 6, 134}, {6, 7, 198}, {6, 8, 326},
83 {6, 9, 582}, {6, 10, 1094}, {7, 11, 2118}, {8, 32, -22}, {8, 32, 4166},
84 {2, 0, 0}};
85
86 constexpr JBig2TableLine kTableLine11[] = {
87 {1, 0, 1}, {2, 1, 2}, {4, 0, 4}, {4, 1, 5}, {5, 1, 7},
88 {5, 2, 9}, {6, 2, 13}, {7, 2, 17}, {7, 3, 21}, {7, 4, 29},
89 {7, 5, 45}, {7, 6, 77}, {0, 32, 0}, {7, 32, 141}};
90
91 constexpr JBig2TableLine kTableLine12[] = {
92 {1, 0, 1}, {2, 0, 2}, {3, 1, 3}, {5, 0, 5}, {5, 1, 6},
93 {6, 1, 8}, {7, 0, 10}, {7, 1, 11}, {7, 2, 13}, {7, 3, 17},
94 {7, 4, 25}, {8, 5, 41}, {0, 32, 0}, {8, 32, 73}};
95
96 constexpr JBig2TableLine kTableLine13[] = {
97 {1, 0, 1}, {3, 0, 2}, {4, 0, 3}, {5, 0, 4}, {4, 1, 5},
98 {3, 3, 7}, {6, 1, 15}, {6, 2, 17}, {6, 3, 21}, {6, 4, 29},
99 {6, 5, 45}, {7, 6, 77}, {0, 32, 0}, {7, 32, 141}};
100
101 constexpr JBig2TableLine kTableLine14[] = {{3, 0, -2}, {3, 0, -1}, {1, 0, 0},
102 {3, 0, 1}, {3, 0, 2}, {0, 32, -3},
103 {0, 32, 3}};
104
105 constexpr JBig2TableLine kTableLine15[] = {
106 {7, 4, -24}, {6, 2, -8}, {5, 1, -4}, {4, 0, -2}, {3, 0, -1},
107 {1, 0, 0}, {3, 0, 1}, {4, 0, 2}, {5, 1, 3}, {6, 2, 5},
108 {7, 4, 9}, {7, 32, -25}, {7, 32, 25}};
109
110 constexpr std::array<const HuffmanTable, 16> kHuffmanTables = {{
111 {false, nullptr, 0}, // Zero dummy to preserve indexing.
112 {false, kTableLine1, std::size(kTableLine1)},
113 {true, kTableLine2, std::size(kTableLine2)},
114 {true, kTableLine3, std::size(kTableLine3)},
115 {false, kTableLine4, std::size(kTableLine4)},
116 {false, kTableLine5, std::size(kTableLine5)},
117 {false, kTableLine6, std::size(kTableLine6)},
118 {false, kTableLine7, std::size(kTableLine7)},
119 {true, kTableLine8, std::size(kTableLine8)},
120 {true, kTableLine9, std::size(kTableLine9)},
121 {true, kTableLine10, std::size(kTableLine10)},
122 {false, kTableLine11, std::size(kTableLine11)},
123 {false, kTableLine12, std::size(kTableLine12)},
124 {false, kTableLine13, std::size(kTableLine13)},
125 {false, kTableLine14, std::size(kTableLine14)},
126 {false, kTableLine15, std::size(kTableLine15)},
127 }};
128
129 static_assert(CJBig2_HuffmanTable::kNumHuffmanTables ==
130 std::size(kHuffmanTables),
131 "kNumHuffmanTables must be equal to the size of kHuffmanTables");
132
133 } // namespace
134
CJBig2_HuffmanTable(size_t idx)135 CJBig2_HuffmanTable::CJBig2_HuffmanTable(size_t idx) {
136 DCHECK(idx > 0);
137 DCHECK(idx < kNumHuffmanTables);
138 const HuffmanTable& table = kHuffmanTables[idx];
139 HTOOB = table.HTOOB;
140 NTEMP = pdfium::checked_cast<uint32_t>(table.size);
141 m_bOK = ParseFromStandardTable(idx);
142 DCHECK(m_bOK);
143 }
144
CJBig2_HuffmanTable(CJBig2_BitStream * pStream)145 CJBig2_HuffmanTable::CJBig2_HuffmanTable(CJBig2_BitStream* pStream)
146 : HTOOB(false), NTEMP(0) {
147 m_bOK = ParseFromCodedBuffer(pStream);
148 }
149
150 CJBig2_HuffmanTable::~CJBig2_HuffmanTable() = default;
151
ParseFromStandardTable(size_t idx)152 bool CJBig2_HuffmanTable::ParseFromStandardTable(size_t idx) {
153 const JBig2TableLine* pTable = kHuffmanTables[idx].lines;
154 CODES.resize(NTEMP);
155 RANGELEN.resize(NTEMP);
156 RANGELOW.resize(NTEMP);
157 UNSAFE_TODO({
158 for (uint32_t i = 0; i < NTEMP; ++i) {
159 CODES[i].codelen = pTable[i].PREFLEN;
160 RANGELEN[i] = pTable[i].RANDELEN;
161 RANGELOW[i] = pTable[i].RANGELOW;
162 }
163 });
164 return CJBig2_Context::HuffmanAssignCode(CODES);
165 }
166
ParseFromCodedBuffer(CJBig2_BitStream * pStream)167 bool CJBig2_HuffmanTable::ParseFromCodedBuffer(CJBig2_BitStream* pStream) {
168 unsigned char cTemp;
169 if (pStream->read1Byte(&cTemp) == -1)
170 return false;
171
172 HTOOB = !!(cTemp & 0x01);
173 unsigned char HTPS = ((cTemp >> 1) & 0x07) + 1;
174 unsigned char HTRS = ((cTemp >> 4) & 0x07) + 1;
175 uint32_t HTLOW;
176 uint32_t HTHIGH;
177 if (pStream->readInteger(&HTLOW) == -1 ||
178 pStream->readInteger(&HTHIGH) == -1) {
179 return false;
180 }
181
182 const int low = static_cast<int>(HTLOW);
183 const int high = static_cast<int>(HTHIGH);
184 if (low > high)
185 return false;
186
187 ExtendBuffers(false);
188 FX_SAFE_INT32 cur_low = low;
189 do {
190 if ((pStream->readNBits(HTPS, &CODES[NTEMP].codelen) == -1) ||
191 (pStream->readNBits(HTRS, &RANGELEN[NTEMP]) == -1) ||
192 (static_cast<size_t>(RANGELEN[NTEMP]) >= 8 * sizeof(cur_low))) {
193 return false;
194 }
195 RANGELOW[NTEMP] = cur_low.ValueOrDie();
196
197 if (RANGELEN[NTEMP] >= 32)
198 return false;
199
200 cur_low += (1 << RANGELEN[NTEMP]);
201 if (!cur_low.IsValid())
202 return false;
203 ExtendBuffers(true);
204 } while (cur_low.ValueOrDie() < high);
205
206 if (pStream->readNBits(HTPS, &CODES[NTEMP].codelen) == -1)
207 return false;
208
209 RANGELEN[NTEMP] = 32;
210 if (low == std::numeric_limits<int>::min())
211 return false;
212
213 RANGELOW[NTEMP] = low - 1;
214 ExtendBuffers(true);
215
216 if (pStream->readNBits(HTPS, &CODES[NTEMP].codelen) == -1)
217 return false;
218
219 RANGELEN[NTEMP] = 32;
220 RANGELOW[NTEMP] = high;
221 ExtendBuffers(true);
222
223 if (HTOOB) {
224 if (pStream->readNBits(HTPS, &CODES[NTEMP].codelen) == -1)
225 return false;
226
227 ++NTEMP;
228 }
229
230 return CJBig2_Context::HuffmanAssignCode(
231 pdfium::make_span(CODES).first(NTEMP));
232 }
233
ExtendBuffers(bool increment)234 void CJBig2_HuffmanTable::ExtendBuffers(bool increment) {
235 if (increment)
236 ++NTEMP;
237
238 size_t size = CODES.size();
239 if (NTEMP < size)
240 return;
241
242 size += 16;
243 DCHECK(NTEMP < size);
244 CODES.resize(size);
245 RANGELEN.resize(size);
246 RANGELOW.resize(size);
247 }
248