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