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 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 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 43 CFX_LZWDecompressor::~CFX_LZWDecompressor() {} 44 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 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 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 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 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
