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