1 // Copyright 2017 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/gif/lzw_decompressor.h"
8
9 #include <algorithm>
10 #include <memory>
11 #include <type_traits>
12 #include <utility>
13
14 #include "core/fxcrt/compiler_specific.h"
15 #include "core/fxcrt/fx_safe_types.h"
16 #include "core/fxcrt/numerics/safe_conversions.h"
17 #include "core/fxcrt/ptr_util.h"
18 #include "core/fxcrt/stl_util.h"
19
20 namespace fxcodec {
21
Create(uint8_t color_exp,uint8_t code_exp)22 std::unique_ptr<LZWDecompressor> LZWDecompressor::Create(uint8_t color_exp,
23 uint8_t code_exp) {
24 // |color_exp| generates 2^(n + 1) codes, where as the code_exp reserves 2^n.
25 // This is a quirk of the GIF spec.
26 if (code_exp > GIF_MAX_LZW_EXP || code_exp < color_exp + 1)
27 return nullptr;
28
29 // Private ctor.
30 return pdfium::WrapUnique(new LZWDecompressor(color_exp, code_exp));
31 }
32
LZWDecompressor(uint8_t color_exp,uint8_t code_exp)33 LZWDecompressor::LZWDecompressor(uint8_t color_exp, uint8_t code_exp)
34 : code_size_(code_exp),
35 code_color_end_(static_cast<uint16_t>(1 << (color_exp + 1))),
36 code_clear_(static_cast<uint16_t>(1 << code_exp)),
37 code_end_(static_cast<uint16_t>((1 << code_exp) + 1)) {
38 ClearTable();
39 }
40
41 LZWDecompressor::~LZWDecompressor() = default;
42
Decode(uint8_t * dest_buf,uint32_t * dest_size)43 LZWDecompressor::Status LZWDecompressor::Decode(uint8_t* dest_buf,
44 uint32_t* dest_size) {
45 if (!dest_buf || !dest_size) {
46 return Status::kError;
47 }
48
49 if (avail_input_.empty()) {
50 return Status::kUnfinished;
51 }
52
53 if (*dest_size == 0)
54 return Status::kInsufficientDestSize;
55
56 FX_SAFE_UINT32 i = 0;
57 if (decompressed_next_ != 0) {
58 size_t extracted_size =
59 ExtractData(UNSAFE_TODO(pdfium::make_span(dest_buf, *dest_size)));
60 if (decompressed_next_ != 0)
61 return Status::kInsufficientDestSize;
62
63 UNSAFE_TODO(dest_buf += extracted_size);
64 i += extracted_size;
65 }
66
67 while (i.ValueOrDie() <= *dest_size &&
68 (!avail_input_.empty() || bits_left_ >= code_size_cur_)) {
69 if (code_size_cur_ > GIF_MAX_LZW_EXP)
70 return Status::kError;
71
72 if (!avail_input_.empty()) {
73 if (bits_left_ > 31)
74 return Status::kError;
75
76 FX_SAFE_UINT32 safe_code = avail_input_.front();
77 safe_code <<= bits_left_;
78 safe_code |= code_store_;
79 if (!safe_code.IsValid())
80 return Status::kError;
81
82 code_store_ = safe_code.ValueOrDie();
83 avail_input_ = avail_input_.subspan(1u);
84 bits_left_ += 8;
85 }
86
87 while (bits_left_ >= code_size_cur_) {
88 uint16_t code =
89 static_cast<uint16_t>(code_store_) & ((1 << code_size_cur_) - 1);
90 code_store_ >>= code_size_cur_;
91 bits_left_ -= code_size_cur_;
92 if (code == code_clear_) {
93 ClearTable();
94 continue;
95 }
96 if (code == code_end_) {
97 *dest_size = i.ValueOrDie();
98 return Status::kSuccess;
99 }
100
101 if (code_old_ != static_cast<uint16_t>(-1)) {
102 if (code_next_ < GIF_MAX_LZW_CODE) {
103 if (code == code_next_) {
104 AddCode(code_old_, code_first_);
105 if (!DecodeString(code))
106 return Status::kError;
107 } else if (code > code_next_) {
108 return Status::kError;
109 } else {
110 if (!DecodeString(code))
111 return Status::kError;
112
113 uint8_t append_char = decompressed_[decompressed_next_ - 1];
114 AddCode(code_old_, append_char);
115 }
116 }
117 } else {
118 if (!DecodeString(code))
119 return Status::kError;
120 }
121
122 code_old_ = code;
123 size_t extracted_size = ExtractData(UNSAFE_TODO(
124 pdfium::make_span(dest_buf, (*dest_size - i).ValueOrDie())));
125 if (decompressed_next_ != 0) {
126 return Status::kInsufficientDestSize;
127 }
128 UNSAFE_TODO(dest_buf += extracted_size);
129 i += extracted_size;
130 }
131 }
132
133 if (!avail_input_.empty()) {
134 return Status::kError;
135 }
136 *dest_size = i.ValueOrDie();
137 return Status::kUnfinished;
138 }
139
ClearTable()140 void LZWDecompressor::ClearTable() {
141 code_size_cur_ = code_size_ + 1;
142 code_next_ = code_end_ + 1;
143 code_old_ = static_cast<uint16_t>(-1);
144 fxcrt::Fill(code_table_, CodeEntry{}); // Aggregate initialization.
145 static_assert(std::is_aggregate_v<CodeEntry>);
146 for (uint16_t i = 0; i < code_clear_; i++) {
147 code_table_[i].suffix = static_cast<uint8_t>(i);
148 }
149 decompressed_.resize(code_next_ - code_clear_ + 1);
150 decompressed_next_ = 0;
151 }
152
AddCode(uint16_t prefix_code,uint8_t append_char)153 void LZWDecompressor::AddCode(uint16_t prefix_code, uint8_t append_char) {
154 if (code_next_ == GIF_MAX_LZW_CODE)
155 return;
156
157 code_table_[code_next_].prefix = prefix_code;
158 code_table_[code_next_].suffix = append_char;
159 if (++code_next_ < GIF_MAX_LZW_CODE) {
160 if (code_next_ >> code_size_cur_)
161 code_size_cur_++;
162 }
163 }
164
DecodeString(uint16_t code)165 bool LZWDecompressor::DecodeString(uint16_t code) {
166 decompressed_.resize(code_next_ - code_clear_ + 1);
167 decompressed_next_ = 0;
168
169 while (code >= code_clear_ && code <= code_next_) {
170 if (code == code_table_[code].prefix ||
171 decompressed_next_ >= decompressed_.size())
172 return false;
173
174 decompressed_[decompressed_next_++] = code_table_[code].suffix;
175 code = code_table_[code].prefix;
176 }
177
178 if (code >= code_color_end_)
179 return false;
180
181 decompressed_[decompressed_next_++] = static_cast<uint8_t>(code);
182 code_first_ = static_cast<uint8_t>(code);
183 return true;
184 }
185
ExtractData(pdfium::span<uint8_t> dest_span)186 size_t LZWDecompressor::ExtractData(pdfium::span<uint8_t> dest_span) {
187 if (dest_span.empty()) {
188 return 0;
189 }
190 size_t copy_size = std::min(dest_span.size(), decompressed_next_);
191 UNSAFE_TODO(std::reverse_copy(
192 decompressed_.data() + decompressed_next_ - copy_size,
193 decompressed_.data() + decompressed_next_, dest_span.data()));
194 decompressed_next_ -= copy_size;
195 return copy_size;
196 }
197
198 } // namespace fxcodec
199