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 <string.h>
10
11 #include <algorithm>
12 #include <memory>
13 #include <utility>
14
15 #include "core/fxcrt/fx_safe_types.h"
16 #include "third_party/base/memory/ptr_util.h"
17 #include "third_party/base/numerics/safe_math.h"
18
19 namespace fxcodec {
20
Create(uint8_t color_exp,uint8_t code_exp)21 std::unique_ptr<LZWDecompressor> LZWDecompressor::Create(uint8_t color_exp,
22 uint8_t code_exp) {
23 // |color_exp| generates 2^(n + 1) codes, where as the code_exp reserves 2^n.
24 // This is a quirk of the GIF spec.
25 if (code_exp > GIF_MAX_LZW_EXP || code_exp < color_exp + 1)
26 return nullptr;
27
28 // Private ctor.
29 return pdfium::WrapUnique(new LZWDecompressor(color_exp, code_exp));
30 }
31
LZWDecompressor(uint8_t color_exp,uint8_t code_exp)32 LZWDecompressor::LZWDecompressor(uint8_t color_exp, uint8_t code_exp)
33 : code_size_(code_exp),
34 code_color_end_(static_cast<uint16_t>(1 << (color_exp + 1))),
35 code_clear_(static_cast<uint16_t>(1 << code_exp)),
36 code_end_(static_cast<uint16_t>((1 << code_exp) + 1)) {
37 ClearTable();
38 }
39
40 LZWDecompressor::~LZWDecompressor() = default;
41
SetSource(const uint8_t * src_buf,uint32_t src_size)42 void LZWDecompressor::SetSource(const uint8_t* src_buf, uint32_t src_size) {
43 next_in_ = src_buf;
44 avail_in_ = src_size;
45 }
46
Decode(uint8_t * dest_buf,uint32_t * dest_size)47 LZWDecompressor::Status LZWDecompressor::Decode(uint8_t* dest_buf,
48 uint32_t* dest_size) {
49 if (!next_in_ || !dest_buf || !dest_size)
50 return Status::kError;
51
52 if (avail_in_ == 0)
53 return Status::kUnfinished;
54
55 if (*dest_size == 0)
56 return Status::kInsufficientDestSize;
57
58 uint32_t i = 0;
59 if (decompressed_next_ != 0) {
60 uint32_t extracted_size = ExtractData(dest_buf, *dest_size);
61 if (decompressed_next_ != 0)
62 return Status::kInsufficientDestSize;
63
64 dest_buf += extracted_size;
65 i += extracted_size;
66 }
67
68 while (i <= *dest_size && (avail_in_ > 0 || bits_left_ >= code_size_cur_)) {
69 if (code_size_cur_ > GIF_MAX_LZW_EXP)
70 return Status::kError;
71
72 if (avail_in_ > 0) {
73 if (bits_left_ > 31)
74 return Status::kError;
75
76 FX_SAFE_UINT32 safe_code = *next_in_++;
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_in_;
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;
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 uint32_t extracted_size = ExtractData(dest_buf, *dest_size - i);
124 if (decompressed_next_ != 0)
125 return Status::kInsufficientDestSize;
126
127 dest_buf += extracted_size;
128 i += extracted_size;
129 }
130 }
131
132 if (avail_in_ != 0)
133 return Status::kError;
134
135 *dest_size = i;
136 return Status::kUnfinished;
137 }
138
ClearTable()139 void LZWDecompressor::ClearTable() {
140 code_size_cur_ = code_size_ + 1;
141 code_next_ = code_end_ + 1;
142 code_old_ = static_cast<uint16_t>(-1);
143 memset(code_table_, 0, sizeof(code_table_));
144 for (uint16_t i = 0; i < code_clear_; i++)
145 code_table_[i].suffix = static_cast<uint8_t>(i);
146 decompressed_.resize(code_next_ - code_clear_ + 1);
147 decompressed_next_ = 0;
148 }
149
AddCode(uint16_t prefix_code,uint8_t append_char)150 void LZWDecompressor::AddCode(uint16_t prefix_code, uint8_t append_char) {
151 if (code_next_ == GIF_MAX_LZW_CODE)
152 return;
153
154 code_table_[code_next_].prefix = prefix_code;
155 code_table_[code_next_].suffix = append_char;
156 if (++code_next_ < GIF_MAX_LZW_CODE) {
157 if (code_next_ >> code_size_cur_)
158 code_size_cur_++;
159 }
160 }
161
DecodeString(uint16_t code)162 bool LZWDecompressor::DecodeString(uint16_t code) {
163 decompressed_.resize(code_next_ - code_clear_ + 1);
164 decompressed_next_ = 0;
165
166 while (code >= code_clear_ && code <= code_next_) {
167 if (code == code_table_[code].prefix ||
168 decompressed_next_ >= decompressed_.size())
169 return false;
170
171 decompressed_[decompressed_next_++] = code_table_[code].suffix;
172 code = code_table_[code].prefix;
173 }
174
175 if (code >= code_color_end_)
176 return false;
177
178 decompressed_[decompressed_next_++] = static_cast<uint8_t>(code);
179 code_first_ = static_cast<uint8_t>(code);
180 return true;
181 }
182
ExtractData(uint8_t * dest_buf,uint32_t dest_size)183 uint32_t LZWDecompressor::ExtractData(uint8_t* dest_buf, uint32_t dest_size) {
184 if (dest_size == 0)
185 return 0;
186
187 uint32_t copy_size = dest_size <= decompressed_next_
188 ? dest_size
189 : static_cast<uint32_t>(decompressed_next_);
190 std::reverse_copy(decompressed_.data() + decompressed_next_ - copy_size,
191 decompressed_.data() + decompressed_next_, dest_buf);
192 decompressed_next_ -= copy_size;
193 return copy_size;
194 }
195
196 } // namespace fxcodec
197