blob: 12b30fc93f87bf10b259045879cf8063520b5ee2 [file] [log] [blame]
// Copyright 2017 PDFium Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
// Original code copyright 2014 Foxit Software Inc. http://www.foxitsoftware.com
#include "core/fxcodec/gif/lzw_decompressor.h"
#include <algorithm>
#include <cstring>
#include <memory>
#include <utility>
#include "core/fxcrt/fx_safe_types.h"
#include "third_party/base/numerics/safe_math.h"
#include "third_party/base/ptr_util.h"
namespace fxcodec {
std::unique_ptr<LZWDecompressor> LZWDecompressor::Create(uint8_t color_exp,
uint8_t code_exp) {
// |color_exp| generates 2^(n + 1) codes, where as the code_exp reserves 2^n.
// This is a quirk of the GIF spec.
if (code_exp > GIF_MAX_LZW_EXP || code_exp < color_exp + 1)
return nullptr;
// Private ctor.
return pdfium::WrapUnique(new LZWDecompressor(color_exp, code_exp));
}
LZWDecompressor::LZWDecompressor(uint8_t color_exp, uint8_t code_exp)
: code_size_(code_exp),
code_color_end_(static_cast<uint16_t>(1 << (color_exp + 1))),
code_clear_(static_cast<uint16_t>(1 << code_exp)),
code_end_(static_cast<uint16_t>((1 << code_exp) + 1)) {}
LZWDecompressor::~LZWDecompressor() = default;
LZWDecompressor::Status LZWDecompressor::Decode(const uint8_t* src_buf,
uint32_t src_size,
uint8_t* dest_buf,
uint32_t* dest_size) {
if (!src_buf || src_size == 0 || !dest_buf || !dest_size)
return Status::kError;
if (*dest_size == 0)
return Status::kInsufficientDestSize;
next_in_ = src_buf;
avail_in_ = src_size;
ClearTable();
uint32_t i = 0;
if (decompressed_next_ != 0) {
uint32_t extracted_size = ExtractData(dest_buf, *dest_size);
if (decompressed_next_ != 0)
return Status::kInsufficientDestSize;
dest_buf += extracted_size;
i += extracted_size;
}
while (i <= *dest_size && (avail_in_ > 0 || bits_left_ >= code_size_cur_)) {
if (code_size_cur_ > GIF_MAX_LZW_EXP)
return Status::kError;
if (avail_in_ > 0) {
if (bits_left_ > 31)
return Status::kError;
FX_SAFE_UINT32 safe_code = *next_in_++;
safe_code <<= bits_left_;
safe_code |= code_store_;
if (!safe_code.IsValid())
return Status::kError;
code_store_ = safe_code.ValueOrDie();
--avail_in_;
bits_left_ += 8;
}
while (bits_left_ >= code_size_cur_) {
uint16_t code =
static_cast<uint16_t>(code_store_) & ((1 << code_size_cur_) - 1);
code_store_ >>= code_size_cur_;
bits_left_ -= code_size_cur_;
if (code == code_clear_) {
ClearTable();
continue;
}
if (code == code_end_) {
*dest_size = i;
return Status::kSuccess;
}
if (code_old_ != static_cast<uint16_t>(-1)) {
if (code_next_ < GIF_MAX_LZW_CODE) {
if (code == code_next_) {
AddCode(code_old_, code_first_);
if (!DecodeString(code))
return Status::kError;
} else if (code > code_next_) {
return Status::kError;
} else {
if (!DecodeString(code))
return Status::kError;
uint8_t append_char = decompressed_[decompressed_next_ - 1];
AddCode(code_old_, append_char);
}
}
} else {
if (!DecodeString(code))
return Status::kError;
}
code_old_ = code;
uint32_t extracted_size = ExtractData(dest_buf, *dest_size - i);
if (decompressed_next_ != 0)
return Status::kInsufficientDestSize;
dest_buf += extracted_size;
i += extracted_size;
}
}
if (avail_in_ != 0)
return Status::kError;
*dest_size = i;
return Status::kUnfinished;
}
void LZWDecompressor::ClearTable() {
code_size_cur_ = code_size_ + 1;
code_next_ = code_end_ + 1;
code_old_ = static_cast<uint16_t>(-1);
memset(code_table_, 0, sizeof(code_table_));
for (uint16_t i = 0; i < code_clear_; i++)
code_table_[i].suffix = static_cast<uint8_t>(i);
decompressed_.resize(code_next_ - code_clear_ + 1);
decompressed_next_ = 0;
}
void LZWDecompressor::AddCode(uint16_t prefix_code, uint8_t append_char) {
if (code_next_ == GIF_MAX_LZW_CODE)
return;
code_table_[code_next_].prefix = prefix_code;
code_table_[code_next_].suffix = append_char;
if (++code_next_ < GIF_MAX_LZW_CODE) {
if (code_next_ >> code_size_cur_)
code_size_cur_++;
}
}
bool LZWDecompressor::DecodeString(uint16_t code) {
decompressed_.resize(code_next_ - code_clear_ + 1);
decompressed_next_ = 0;
while (code >= code_clear_ && code <= code_next_) {
if (code == code_table_[code].prefix ||
decompressed_next_ >= decompressed_.size())
return false;
decompressed_[decompressed_next_++] = code_table_[code].suffix;
code = code_table_[code].prefix;
}
if (code >= code_color_end_)
return false;
decompressed_[decompressed_next_++] = static_cast<uint8_t>(code);
code_first_ = static_cast<uint8_t>(code);
return true;
}
uint32_t LZWDecompressor::ExtractData(uint8_t* dest_buf, uint32_t dest_size) {
if (dest_size == 0)
return 0;
uint32_t copy_size = dest_size <= decompressed_next_
? dest_size
: static_cast<uint32_t>(decompressed_next_);
std::reverse_copy(decompressed_.data() + decompressed_next_ - copy_size,
decompressed_.data() + decompressed_next_, dest_buf);
decompressed_next_ -= copy_size;
return copy_size;
}
} // namespace fxcodec