1 // Copyright 2019 PDFium Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4 
5 #include "core/fxcodec/basic/basicmodule.h"
6 
7 #include <algorithm>
8 #include <utility>
9 
10 #include "core/fxcodec/scanlinedecoder.h"
11 #include "core/fxcrt/fx_safe_types.h"
12 #include "third_party/base/ptr_util.h"
13 
14 namespace fxcodec {
15 
16 namespace {
17 
18 class RLScanlineDecoder final : public ScanlineDecoder {
19  public:
20   RLScanlineDecoder();
21   ~RLScanlineDecoder() override;
22 
23   bool Create(pdfium::span<const uint8_t> src_buf,
24               int width,
25               int height,
26               int nComps,
27               int bpc);
28 
29   // ScanlineDecoder:
30   bool v_Rewind() override;
31   uint8_t* v_GetNextLine() override;
GetSrcOffset()32   uint32_t GetSrcOffset() override { return m_SrcOffset; }
33 
34  private:
35   bool CheckDestSize();
36   void GetNextOperator();
37   void UpdateOperator(uint8_t used_bytes);
38 
39   std::unique_ptr<uint8_t, FxFreeDeleter> m_pScanline;
40   pdfium::span<const uint8_t> m_SrcBuf;
41   size_t m_dwLineBytes = 0;
42   size_t m_SrcOffset = 0;
43   bool m_bEOD = false;
44   uint8_t m_Operator = 0;
45 };
46 
47 RLScanlineDecoder::RLScanlineDecoder() = default;
48 
49 RLScanlineDecoder::~RLScanlineDecoder() = default;
50 
CheckDestSize()51 bool RLScanlineDecoder::CheckDestSize() {
52   size_t i = 0;
53   uint32_t old_size = 0;
54   uint32_t dest_size = 0;
55   while (i < m_SrcBuf.size()) {
56     if (m_SrcBuf[i] < 128) {
57       old_size = dest_size;
58       dest_size += m_SrcBuf[i] + 1;
59       if (dest_size < old_size) {
60         return false;
61       }
62       i += m_SrcBuf[i] + 2;
63     } else if (m_SrcBuf[i] > 128) {
64       old_size = dest_size;
65       dest_size += 257 - m_SrcBuf[i];
66       if (dest_size < old_size) {
67         return false;
68       }
69       i += 2;
70     } else {
71       break;
72     }
73   }
74   if (((uint32_t)m_OrigWidth * m_nComps * m_bpc * m_OrigHeight + 7) / 8 >
75       dest_size) {
76     return false;
77   }
78   return true;
79 }
80 
Create(pdfium::span<const uint8_t> src_buf,int width,int height,int nComps,int bpc)81 bool RLScanlineDecoder::Create(pdfium::span<const uint8_t> src_buf,
82                                int width,
83                                int height,
84                                int nComps,
85                                int bpc) {
86   m_SrcBuf = src_buf;
87   m_OutputWidth = m_OrigWidth = width;
88   m_OutputHeight = m_OrigHeight = height;
89   m_nComps = nComps;
90   m_bpc = bpc;
91   // Aligning the pitch to 4 bytes requires an integer overflow check.
92   FX_SAFE_UINT32 pitch = width;
93   pitch *= nComps;
94   pitch *= bpc;
95   pitch += 31;
96   pitch /= 32;
97   pitch *= 4;
98   if (!pitch.IsValid()) {
99     return false;
100   }
101   m_Pitch = pitch.ValueOrDie();
102   // Overflow should already have been checked before this is called.
103   m_dwLineBytes = (static_cast<uint32_t>(width) * nComps * bpc + 7) / 8;
104   m_pScanline.reset(FX_Alloc(uint8_t, m_Pitch));
105   return CheckDestSize();
106 }
107 
v_Rewind()108 bool RLScanlineDecoder::v_Rewind() {
109   memset(m_pScanline.get(), 0, m_Pitch);
110   m_SrcOffset = 0;
111   m_bEOD = false;
112   m_Operator = 0;
113   return true;
114 }
115 
v_GetNextLine()116 uint8_t* RLScanlineDecoder::v_GetNextLine() {
117   if (m_SrcOffset == 0) {
118     GetNextOperator();
119   } else if (m_bEOD) {
120     return nullptr;
121   }
122   memset(m_pScanline.get(), 0, m_Pitch);
123   uint32_t col_pos = 0;
124   bool eol = false;
125   while (m_SrcOffset < m_SrcBuf.size() && !eol) {
126     if (m_Operator < 128) {
127       uint32_t copy_len = m_Operator + 1;
128       if (col_pos + copy_len >= m_dwLineBytes) {
129         copy_len = m_dwLineBytes - col_pos;
130         eol = true;
131       }
132       if (copy_len >= m_SrcBuf.size() - m_SrcOffset) {
133         copy_len = m_SrcBuf.size() - m_SrcOffset;
134         m_bEOD = true;
135       }
136       auto copy_span = m_SrcBuf.subspan(m_SrcOffset, copy_len);
137       memcpy(m_pScanline.get() + col_pos, copy_span.data(), copy_span.size());
138       col_pos += copy_len;
139       UpdateOperator((uint8_t)copy_len);
140     } else if (m_Operator > 128) {
141       int fill = 0;
142       if (m_SrcOffset - 1 < m_SrcBuf.size() - 1) {
143         fill = m_SrcBuf[m_SrcOffset];
144       }
145       uint32_t duplicate_len = 257 - m_Operator;
146       if (col_pos + duplicate_len >= m_dwLineBytes) {
147         duplicate_len = m_dwLineBytes - col_pos;
148         eol = true;
149       }
150       memset(m_pScanline.get() + col_pos, fill, duplicate_len);
151       col_pos += duplicate_len;
152       UpdateOperator((uint8_t)duplicate_len);
153     } else {
154       m_bEOD = true;
155       break;
156     }
157   }
158   return m_pScanline.get();
159 }
160 
GetNextOperator()161 void RLScanlineDecoder::GetNextOperator() {
162   if (m_SrcOffset >= m_SrcBuf.size()) {
163     m_Operator = 128;
164     return;
165   }
166   m_Operator = m_SrcBuf[m_SrcOffset];
167   m_SrcOffset++;
168 }
UpdateOperator(uint8_t used_bytes)169 void RLScanlineDecoder::UpdateOperator(uint8_t used_bytes) {
170   if (used_bytes == 0) {
171     return;
172   }
173   if (m_Operator < 128) {
174     ASSERT((uint32_t)m_Operator + 1 >= used_bytes);
175     if (used_bytes == m_Operator + 1) {
176       m_SrcOffset += used_bytes;
177       GetNextOperator();
178       return;
179     }
180     m_Operator -= used_bytes;
181     m_SrcOffset += used_bytes;
182     if (m_SrcOffset >= m_SrcBuf.size()) {
183       m_Operator = 128;
184     }
185     return;
186   }
187   uint8_t count = 257 - m_Operator;
188   ASSERT((uint32_t)count >= used_bytes);
189   if (used_bytes == count) {
190     m_SrcOffset++;
191     GetNextOperator();
192     return;
193   }
194   count -= used_bytes;
195   m_Operator = 257 - count;
196 }
197 
198 }  // namespace
199 
200 // static
CreateRunLengthDecoder(pdfium::span<const uint8_t> src_buf,int width,int height,int nComps,int bpc)201 std::unique_ptr<ScanlineDecoder> BasicModule::CreateRunLengthDecoder(
202     pdfium::span<const uint8_t> src_buf,
203     int width,
204     int height,
205     int nComps,
206     int bpc) {
207   auto pDecoder = pdfium::MakeUnique<RLScanlineDecoder>();
208   if (!pDecoder->Create(src_buf, width, height, nComps, bpc))
209     return nullptr;
210 
211   return std::move(pDecoder);
212 }
213 
214 // static
RunLengthEncode(pdfium::span<const uint8_t> src_span,std::unique_ptr<uint8_t,FxFreeDeleter> * dest_buf,uint32_t * dest_size)215 bool BasicModule::RunLengthEncode(
216     pdfium::span<const uint8_t> src_span,
217     std::unique_ptr<uint8_t, FxFreeDeleter>* dest_buf,
218     uint32_t* dest_size) {
219   // Check inputs
220   if (src_span.empty() || !dest_buf || !dest_size)
221     return false;
222 
223   // Edge case
224   if (src_span.size() == 1) {
225     *dest_size = 3;
226     dest_buf->reset(FX_Alloc(uint8_t, *dest_size));
227     auto dest_buf_span = pdfium::make_span(dest_buf->get(), *dest_size);
228     dest_buf_span[0] = 0;
229     dest_buf_span[1] = src_span[0];
230     dest_buf_span[2] = 128;
231     return true;
232   }
233 
234   // Worst case: 1 nonmatch, 2 match, 1 nonmatch, 2 match, etc. This becomes
235   // 4 output chars for every 3 input, plus up to 4 more for the 1-2 chars
236   // rounded off plus the terminating character.
237   FX_SAFE_SIZE_T estimated_size = src_span.size();
238   estimated_size += 2;
239   estimated_size /= 3;
240   estimated_size *= 4;
241   estimated_size += 1;
242   dest_buf->reset(FX_Alloc(uint8_t, estimated_size.ValueOrDie()));
243 
244   // Set up pointers.
245   uint8_t* out = dest_buf->get();
246   uint32_t run_start = 0;
247   uint32_t run_end = 1;
248   uint8_t x = src_span[run_start];
249   uint8_t y = src_span[run_end];
250   while (run_end < src_span.size()) {
251     size_t max_len = std::min<size_t>(128, src_span.size() - run_start);
252     while (x == y && (run_end - run_start < max_len - 1))
253       y = src_span[++run_end];
254 
255     // Reached end with matched run. Update variables to expected values.
256     if (x == y) {
257       run_end++;
258       if (run_end < src_span.size())
259         y = src_span[run_end];
260     }
261     if (run_end - run_start > 1) {  // Matched run but not at end of input.
262       out[0] = 257 - (run_end - run_start);
263       out[1] = x;
264       x = y;
265       run_start = run_end;
266       run_end++;
267       if (run_end < src_span.size())
268         y = src_span[run_end];
269       out += 2;
270       continue;
271     }
272     // Mismatched run
273     while (x != y && run_end <= run_start + max_len) {
274       out[run_end - run_start] = x;
275       x = y;
276       run_end++;
277       if (run_end == src_span.size()) {
278         if (run_end <= run_start + max_len) {
279           out[run_end - run_start] = x;
280           run_end++;
281         }
282         break;
283       }
284       y = src_span[run_end];
285     }
286     out[0] = run_end - run_start - 2;
287     out += run_end - run_start;
288     run_start = run_end - 1;
289   }
290   if (run_start < src_span.size()) {  // 1 leftover character
291     out[0] = 0;
292     out[1] = x;
293     out += 2;
294   }
295   *out = 128;
296   *dest_size = out + 1 - dest_buf->get();
297   return true;
298 }
299 
300 // static
A85Encode(pdfium::span<const uint8_t> src_span,std::unique_ptr<uint8_t,FxFreeDeleter> * dest_buf,uint32_t * dest_size)301 bool BasicModule::A85Encode(pdfium::span<const uint8_t> src_span,
302                             std::unique_ptr<uint8_t, FxFreeDeleter>* dest_buf,
303                             uint32_t* dest_size) {
304   // Check inputs.
305   if (!dest_buf || !dest_size)
306     return false;
307 
308   if (src_span.empty()) {
309     *dest_size = 0;
310     return false;
311   }
312 
313   // Worst case: 5 output for each 4 input (plus up to 4 from leftover), plus
314   // 2 character new lines each 75 output chars plus 2 termination chars. May
315   // have fewer if there are special "z" chars.
316   FX_SAFE_SIZE_T estimated_size = src_span.size();
317   estimated_size /= 4;
318   estimated_size *= 5;
319   estimated_size += 4;
320   estimated_size += src_span.size() / 30;
321   estimated_size += 2;
322   dest_buf->reset(FX_Alloc(uint8_t, estimated_size.ValueOrDie()));
323 
324   // Set up pointers.
325   uint8_t* out = dest_buf->get();
326   uint32_t pos = 0;
327   uint32_t line_length = 0;
328   while (src_span.size() >= 4 && pos < src_span.size() - 3) {
329     uint32_t val = ((uint32_t)(src_span[pos]) << 24) +
330                    ((uint32_t)(src_span[pos + 1]) << 16) +
331                    ((uint32_t)(src_span[pos + 2]) << 8) +
332                    (uint32_t)(src_span[pos + 3]);
333     pos += 4;
334     if (val == 0) {  // All zero special case
335       *out = 'z';
336       out++;
337       line_length++;
338     } else {  // Compute base 85 characters and add 33.
339       for (int i = 4; i >= 0; i--) {
340         out[i] = (uint8_t)(val % 85) + 33;
341         val = val / 85;
342       }
343       out += 5;
344       line_length += 5;
345     }
346     if (line_length >= 75) {  // Add a return.
347       *out++ = '\r';
348       *out++ = '\n';
349       line_length = 0;
350     }
351   }
352   if (pos < src_span.size()) {  // Leftover bytes
353     uint32_t val = 0;
354     int count = 0;
355     while (pos < src_span.size()) {
356       val += (uint32_t)(src_span[pos]) << (8 * (3 - count));
357       count++;
358       pos++;
359     }
360     for (int i = 4; i >= 0; i--) {
361       if (i <= count)
362         out[i] = (uint8_t)(val % 85) + 33;
363       val = val / 85;
364     }
365     out += count + 1;
366   }
367 
368   // Terminating characters.
369   out[0] = '~';
370   out[1] = '>';
371   out += 2;
372   *dest_size = out - dest_buf->get();
373   return true;
374 }
375 
376 }  // namespace fxcodec
377