diff options
-rw-r--r-- | core/fxcodec/gif/cfx_lzwdecompressor.cpp | 63 | ||||
-rw-r--r-- | core/fxcodec/gif/cfx_lzwdecompressor.h | 14 | ||||
-rw-r--r-- | core/fxcodec/gif/cfx_lzwdecompressor_unittest.cpp | 186 |
3 files changed, 177 insertions, 86 deletions
diff --git a/core/fxcodec/gif/cfx_lzwdecompressor.cpp b/core/fxcodec/gif/cfx_lzwdecompressor.cpp index 27e36b12e9..1ee7b5a217 100644 --- a/core/fxcodec/gif/cfx_lzwdecompressor.cpp +++ b/core/fxcodec/gif/cfx_lzwdecompressor.cpp @@ -18,7 +18,9 @@ std::unique_ptr<CFX_LZWDecompressor> CFX_LZWDecompressor::Create( uint8_t color_exp, uint8_t code_exp) { - if (code_exp > GIF_MAX_LZW_EXP || code_exp + 1 < color_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; return std::unique_ptr<CFX_LZWDecompressor>( new CFX_LZWDecompressor(color_exp, code_exp)); @@ -27,12 +29,11 @@ std::unique_ptr<CFX_LZWDecompressor> CFX_LZWDecompressor::Create( CFX_LZWDecompressor::CFX_LZWDecompressor(uint8_t color_exp, uint8_t code_exp) : code_size_(code_exp), code_size_cur_(0), - code_color_end_(static_cast<uint16_t>(2 << color_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)), code_next_(0), code_first_(0), - stack_size_(0), code_old_(0), next_in_(nullptr), avail_in_(0), @@ -57,17 +58,13 @@ CFX_GifDecodeStatus CFX_LZWDecompressor::Decode(uint8_t* src_buf, ClearTable(); uint32_t i = 0; - if (stack_size_ != 0) { - if (*des_size < stack_size_) { - memcpy(des_buf, &stack_[GIF_MAX_LZW_CODE - stack_size_], *des_size); - stack_size_ -= static_cast<uint16_t>(*des_size); + if (decompressed_next_ != 0) { + uint32_t extracted_size = ExtractData(des_buf, *des_size); + if (decompressed_next_ != 0) return CFX_GifDecodeStatus::InsufficientDestSize; - } - memcpy(des_buf, &stack_[GIF_MAX_LZW_CODE - stack_size_], stack_size_); - des_buf += stack_size_; - i += stack_size_; - stack_size_ = 0; + des_buf += extracted_size; + i += extracted_size; } while (i <= *des_size && (avail_in_ > 0 || bits_left_ >= code_size_cur_)) { @@ -115,7 +112,7 @@ CFX_GifDecodeStatus CFX_LZWDecompressor::Decode(uint8_t* src_buf, if (!DecodeString(code)) return CFX_GifDecodeStatus::Error; - uint8_t append_char = stack_[GIF_MAX_LZW_CODE - stack_size_]; + uint8_t append_char = decompressed_[decompressed_next_ - 1]; AddCode(code_old_, append_char); } } @@ -125,16 +122,12 @@ CFX_GifDecodeStatus CFX_LZWDecompressor::Decode(uint8_t* src_buf, } code_old_ = code; - if (i + stack_size_ > *des_size) { - memcpy(des_buf, &stack_[GIF_MAX_LZW_CODE - stack_size_], *des_size - i); - stack_size_ -= static_cast<uint16_t>(*des_size - i); + uint32_t extracted_size = ExtractData(des_buf, *des_size - i); + if (decompressed_next_ != 0) return CFX_GifDecodeStatus::InsufficientDestSize; - } - memcpy(des_buf, &stack_[GIF_MAX_LZW_CODE - stack_size_], stack_size_); - des_buf += stack_size_; - i += stack_size_; - stack_size_ = 0; + des_buf += extracted_size; + i += extracted_size; } } @@ -150,9 +143,10 @@ void CFX_LZWDecompressor::ClearTable() { code_next_ = code_end_ + 1; code_old_ = static_cast<uint16_t>(-1); memset(code_table_, 0, sizeof(code_table_)); - memset(stack_, 0, sizeof(stack_)); 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 CFX_LZWDecompressor::AddCode(uint16_t prefix_code, uint8_t append_char) { @@ -168,18 +162,35 @@ void CFX_LZWDecompressor::AddCode(uint16_t prefix_code, uint8_t append_char) { } bool CFX_LZWDecompressor::DecodeString(uint16_t code) { - stack_size_ = 0; + decompressed_.resize(code_next_ - code_clear_ + 1); + decompressed_next_ = 0; + while (code >= code_clear_ && code <= code_next_) { - if (code == code_table_[code].prefix || stack_size_ == GIF_MAX_LZW_CODE - 1) + if (code == code_table_[code].prefix || + decompressed_next_ >= decompressed_.size()) return false; - stack_[GIF_MAX_LZW_CODE - 1 - stack_size_++] = code_table_[code].suffix; + decompressed_[decompressed_next_++] = code_table_[code].suffix; code = code_table_[code].prefix; } + if (code >= code_color_end_) return false; - stack_[GIF_MAX_LZW_CODE - 1 - stack_size_++] = static_cast<uint8_t>(code); + decompressed_[decompressed_next_++] = static_cast<uint8_t>(code); code_first_ = static_cast<uint8_t>(code); return true; } + +uint32_t CFX_LZWDecompressor::ExtractData(uint8_t* des_buf, uint32_t des_size) { + if (des_size == 0) + return 0; + + uint32_t copy_size = des_size <= decompressed_next_ + ? des_size + : static_cast<uint32_t>(decompressed_next_); + std::reverse_copy(decompressed_.data() + decompressed_next_ - copy_size, + decompressed_.data() + decompressed_next_, des_buf); + decompressed_next_ -= copy_size; + return copy_size; +} diff --git a/core/fxcodec/gif/cfx_lzwdecompressor.h b/core/fxcodec/gif/cfx_lzwdecompressor.h index 10c0a566d7..717c055973 100644 --- a/core/fxcodec/gif/cfx_lzwdecompressor.h +++ b/core/fxcodec/gif/cfx_lzwdecompressor.h @@ -29,11 +29,21 @@ class CFX_LZWDecompressor { uint8_t* des_buf, uint32_t* des_size); + // Used by unittests, should not be called in production code. + uint32_t ExtractDataForTest(uint8_t* des_buf, uint32_t des_size) { + return ExtractData(des_buf, des_size); + } + + std::vector<uint8_t>* DecompressedForTest() { return &decompressed_; } + + size_t* DecompressedNextForTest() { return &decompressed_next_; } + private: CFX_LZWDecompressor(uint8_t color_exp, uint8_t code_exp); void ClearTable(); void AddCode(uint16_t prefix_code, uint8_t append_char); bool DecodeString(uint16_t code); + uint32_t ExtractData(uint8_t* des_buf, uint32_t des_size); uint8_t code_size_; uint8_t code_size_cur_; @@ -42,8 +52,8 @@ class CFX_LZWDecompressor { uint16_t code_end_; uint16_t code_next_; uint8_t code_first_; - uint8_t stack_[GIF_MAX_LZW_CODE]; - size_t stack_size_; + std::vector<uint8_t> decompressed_; + size_t decompressed_next_; CodeEntry code_table_[GIF_MAX_LZW_CODE]; uint16_t code_old_; uint8_t* next_in_; diff --git a/core/fxcodec/gif/cfx_lzwdecompressor_unittest.cpp b/core/fxcodec/gif/cfx_lzwdecompressor_unittest.cpp index cc3ce6367d..0d0906eb10 100644 --- a/core/fxcodec/gif/cfx_lzwdecompressor_unittest.cpp +++ b/core/fxcodec/gif/cfx_lzwdecompressor_unittest.cpp @@ -8,16 +8,79 @@ #include "testing/gtest/include/gtest/gtest.h" TEST(CFX_LZWDecompressor, CreateBadParams) { - EXPECT_EQ(nullptr, CFX_LZWDecompressor::Create(0x10, 0x2)); - EXPECT_EQ(nullptr, CFX_LZWDecompressor::Create(0x4, 0x0F)); + EXPECT_EQ(nullptr, CFX_LZWDecompressor::Create(0x10, 0x02)); + EXPECT_EQ(nullptr, CFX_LZWDecompressor::Create(0x04, 0x0F)); + EXPECT_EQ(nullptr, CFX_LZWDecompressor::Create(0x02, 0x02)); +} + +TEST(CFX_LZWDecompressor, ExtractData) { + uint8_t palette_exp = 0x1; + uint8_t code_exp = 0x2; + auto decompressor = CFX_LZWDecompressor::Create(palette_exp, code_exp); + ASSERT_NE(nullptr, decompressor); + + // Check that 0 length extract does nothing + { + std::vector<uint8_t>* decompressed = decompressor->DecompressedForTest(); + *decompressed = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}; + *(decompressor->DecompressedNextForTest()) = decompressed->size(); + uint8_t des_buf[20]; + memset(des_buf, static_cast<uint8_t>(-1), sizeof(des_buf)); + + EXPECT_EQ(0u, decompressor->ExtractDataForTest(des_buf, 0)); + for (size_t i = 0; i < FX_ArraySize(des_buf); ++i) + EXPECT_EQ(static_cast<uint8_t>(-1), des_buf[i]); + + EXPECT_EQ(10u, *(decompressor->DecompressedNextForTest())); + for (size_t i = 0; i < *(decompressor->DecompressedNextForTest()); ++i) + EXPECT_EQ(i, decompressed->operator[](i)); + } + + // Check that less than decompressed size only gets the expected number + { + std::vector<uint8_t>* decompressed = decompressor->DecompressedForTest(); + *decompressed = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}; + *(decompressor->DecompressedNextForTest()) = decompressed->size(); + uint8_t des_buf[20]; + memset(des_buf, static_cast<uint8_t>(-1), sizeof(des_buf)); + + EXPECT_EQ(5u, decompressor->ExtractDataForTest(des_buf, 5)); + size_t i = 0; + for (; i < 5; ++i) + EXPECT_EQ(9 - i, des_buf[i]); + for (; i < FX_ArraySize(des_buf); ++i) + EXPECT_EQ(static_cast<uint8_t>(-1), des_buf[i]); + + EXPECT_EQ(5u, *(decompressor->DecompressedNextForTest())); + for (i = 0; i < *(decompressor->DecompressedNextForTest()); ++i) + EXPECT_EQ(i, decompressed->operator[](i)); + } + + // Check that greater than decompressed size depletes the decompressor + { + std::vector<uint8_t>* decompressed = decompressor->DecompressedForTest(); + *decompressed = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}; + *(decompressor->DecompressedNextForTest()) = decompressed->size(); + uint8_t des_buf[20]; + memset(des_buf, static_cast<uint8_t>(-1), sizeof(des_buf)); + + EXPECT_EQ(10u, + decompressor->ExtractDataForTest(des_buf, FX_ArraySize(des_buf))); + size_t i = 0; + for (; i < 10; ++i) + EXPECT_EQ(9 - i, des_buf[i]); + for (; i < FX_ArraySize(des_buf); ++i) + EXPECT_EQ(static_cast<uint8_t>(-1), des_buf[i]); + + EXPECT_EQ(0u, *(decompressor->DecompressedNextForTest())); + } } TEST(CFX_LZWDecompressor, DecodeBadParams) { uint8_t palette_exp = 0x0; uint8_t code_exp = 0x2; - - auto decoder = CFX_LZWDecompressor::Create(palette_exp, code_exp); - ASSERT_NE(nullptr, decoder); + auto decompressor = CFX_LZWDecompressor::Create(palette_exp, code_exp); + ASSERT_NE(nullptr, decompressor); uint8_t image_data[10]; uint32_t image_size = FX_ArraySize(image_data); @@ -25,36 +88,40 @@ TEST(CFX_LZWDecompressor, DecodeBadParams) { uint8_t output_data[10]; uint32_t output_size = FX_ArraySize(output_data); + EXPECT_EQ( + CFX_GifDecodeStatus::Error, + decompressor->Decode(nullptr, image_size, output_data, &output_size)); EXPECT_EQ(CFX_GifDecodeStatus::Error, - decoder->Decode(nullptr, image_size, output_data, &output_size)); + decompressor->Decode(image_data, 0, output_data, &output_size)); + EXPECT_EQ( + CFX_GifDecodeStatus::Error, + decompressor->Decode(image_data, image_size, nullptr, &output_size)); EXPECT_EQ(CFX_GifDecodeStatus::Error, - decoder->Decode(image_data, 0, output_data, &output_size)); - EXPECT_EQ(CFX_GifDecodeStatus::Error, - decoder->Decode(image_data, image_size, nullptr, &output_size)); - EXPECT_EQ(CFX_GifDecodeStatus::Error, - decoder->Decode(image_data, image_size, output_data, nullptr)); + decompressor->Decode(image_data, image_size, output_data, nullptr)); output_size = 0; - EXPECT_EQ(CFX_GifDecodeStatus::InsufficientDestSize, - decoder->Decode(image_data, image_size, output_data, &output_size)); + EXPECT_EQ( + CFX_GifDecodeStatus::InsufficientDestSize, + decompressor->Decode(image_data, image_size, output_data, &output_size)); } TEST(CFX_LZWDecompressor, Decode1x1SingleColour) { uint8_t palette_exp = 0x0; uint8_t code_exp = 0x2; - - auto decoder = CFX_LZWDecompressor::Create(palette_exp, code_exp); - ASSERT_NE(nullptr, decoder); + auto decompressor = CFX_LZWDecompressor::Create(palette_exp, code_exp); + ASSERT_NE(nullptr, decompressor); uint8_t image_data[] = {0x44, 0x01}; uint32_t image_size = FX_ArraySize(image_data); - uint8_t output_data[1]; + uint8_t expected_data[] = {0x00}; + uint8_t output_data[FX_ArraySize(expected_data)]; + memset(output_data, 0, sizeof(output_data)); uint32_t output_size = FX_ArraySize(output_data); - EXPECT_EQ(CFX_GifDecodeStatus::Success, - decoder->Decode(image_data, image_size, output_data, &output_size)); - uint8_t expected_data[] = {0x00}; + EXPECT_EQ( + CFX_GifDecodeStatus::Success, + decompressor->Decode(image_data, image_size, output_data, &output_size)); EXPECT_EQ(FX_ArraySize(output_data), output_size); EXPECT_TRUE(0 == memcmp(expected_data, output_data, sizeof(expected_data))); @@ -63,29 +130,30 @@ TEST(CFX_LZWDecompressor, Decode1x1SingleColour) { TEST(CFX_LZWDecompressor, Decode10x10SingleColour) { uint8_t palette_exp = 0x0; uint8_t code_exp = 0x2; - - auto decoder = CFX_LZWDecompressor::Create(palette_exp, code_exp); - ASSERT_NE(nullptr, decoder); + auto decompressor = CFX_LZWDecompressor::Create(palette_exp, code_exp); + ASSERT_NE(nullptr, decompressor); uint8_t image_data[] = {0x84, 0x8F, 0xA9, 0xCB, 0xED, 0x0F, 0x63, 0x2B}; uint32_t image_size = FX_ArraySize(image_data); - uint8_t output_data[100]; + uint8_t expected_data[] = { + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00}; + uint8_t output_data[FX_ArraySize(expected_data)]; memset(output_data, 0, sizeof(output_data)); uint32_t output_size = FX_ArraySize(output_data); - EXPECT_EQ(CFX_GifDecodeStatus::Success, - decoder->Decode(image_data, image_size, output_data, &output_size)); - uint8_t expected_data[] = { - 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, - 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, - 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, - 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, - 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, - 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, - 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, - 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, - 0x00, 0x00, 0x00, 0x00}; + EXPECT_EQ( + CFX_GifDecodeStatus::Success, + decompressor->Decode(image_data, image_size, output_data, &output_size)); EXPECT_EQ(FX_ArraySize(output_data), output_size); EXPECT_TRUE(0 == memcmp(expected_data, output_data, sizeof(expected_data))); @@ -94,31 +162,33 @@ TEST(CFX_LZWDecompressor, Decode10x10SingleColour) { TEST(CFX_LZWDecompressor, Decode10x10MultipleColour) { uint8_t palette_exp = 0x1; uint8_t code_exp = 0x2; - - auto decoder = CFX_LZWDecompressor::Create(palette_exp, code_exp); - ASSERT_NE(nullptr, decoder); + auto decompressor = CFX_LZWDecompressor::Create(palette_exp, code_exp); + ASSERT_NE(nullptr, decompressor); uint8_t image_data[] = {0x8C, 0x2D, 0x99, 0x87, 0x2A, 0x1C, 0xDC, 0x33, 0xA0, 0x02, 0x75, 0xEC, 0x95, 0xFA, 0xA8, 0xDE, 0x60, 0x8C, 0x04, 0x91, 0x4C, 0x01}; uint32_t image_size = FX_ArraySize(image_data); - uint8_t output_data[100]; + uint8_t expected_data[] = { + 0x01, 0x01, 0x01, 0x01, 0x01, 0x02, 0x02, 0x02, 0x02, 0x02, + 0x01, 0x01, 0x01, 0x01, 0x01, 0x02, 0x02, 0x02, 0x02, 0x02, + 0x01, 0x01, 0x01, 0x01, 0x01, 0x02, 0x02, 0x02, 0x02, 0x02, + 0x01, 0x01, 0x01, 0x00, 0x00, 0x00, 0x00, 0x02, 0x02, 0x02, + 0x01, 0x01, 0x01, 0x00, 0x00, 0x00, 0x00, 0x02, 0x02, 0x02, + 0x02, 0x02, 0x02, 0x00, 0x00, 0x00, 0x00, 0x01, 0x01, 0x01, + 0x02, 0x02, 0x02, 0x00, 0x00, 0x00, 0x00, 0x01, 0x01, 0x01, + 0x02, 0x02, 0x02, 0x02, 0x02, 0x01, 0x01, 0x01, 0x01, 0x01, + 0x02, 0x02, 0x02, 0x02, 0x02, 0x01, 0x01, 0x01, 0x01, 0x01, + 0x02, 0x02, 0x02, 0x02, 0x02, 0x01, 0x01, 0x01, 0x01, 0x01}; + + uint8_t output_data[FX_ArraySize(expected_data)]; memset(output_data, 0, sizeof(output_data)); uint32_t output_size = FX_ArraySize(output_data); - EXPECT_EQ(CFX_GifDecodeStatus::Success, - decoder->Decode(image_data, image_size, output_data, &output_size)); - uint8_t expected_data[] = { - 0x01, 0x01, 0x01, 0x01, 0x01, 0x02, 0x02, 0x02, 0x02, 0x02, 0x01, 0x01, - 0x01, 0x01, 0x01, 0x02, 0x02, 0x02, 0x02, 0x02, 0x01, 0x01, 0x01, 0x01, - 0x01, 0x02, 0x02, 0x02, 0x02, 0x02, 0x01, 0x01, 0x01, 0x00, 0x00, 0x00, - 0x00, 0x02, 0x02, 0x02, 0x01, 0x01, 0x01, 0x00, 0x00, 0x00, 0x00, 0x02, - 0x02, 0x02, 0x02, 0x02, 0x02, 0x00, 0x00, 0x00, 0x00, 0x01, 0x01, 0x01, - 0x02, 0x02, 0x02, 0x00, 0x00, 0x00, 0x00, 0x01, 0x01, 0x01, 0x02, 0x02, - 0x02, 0x02, 0x02, 0x01, 0x01, 0x01, 0x01, 0x01, 0x02, 0x02, 0x02, 0x02, - 0x02, 0x01, 0x01, 0x01, 0x01, 0x01, 0x02, 0x02, 0x02, 0x02, 0x02, 0x01, - 0x01, 0x01, 0x01, 0x01}; + EXPECT_EQ( + CFX_GifDecodeStatus::Success, + decompressor->Decode(image_data, image_size, output_data, &output_size)); EXPECT_EQ(FX_ArraySize(output_data), output_size); EXPECT_TRUE(0 == memcmp(expected_data, output_data, sizeof(expected_data))); @@ -128,9 +198,8 @@ TEST(CFX_LZWDecompressor, HandleColourCodeOutOfPalette) { uint8_t palette_exp = 0x2; // Image uses 10 colours, so the palette exp // should be 3, 2^(3+1) = 16 colours. uint8_t code_exp = 0x4; - - auto decoder = CFX_LZWDecompressor::Create(palette_exp, code_exp); - ASSERT_NE(nullptr, decoder); + auto decompressor = CFX_LZWDecompressor::Create(palette_exp, code_exp); + ASSERT_NE(nullptr, decompressor); uint8_t image_data[] = {0x30, 0xC9, 0x49, 0x81, 0xBD, 0x78, 0xE8, 0xCD, 0x89, 0xFF, 0x60, 0x20, 0x8E, 0xE4, 0x61, 0x9E, @@ -138,10 +207,11 @@ TEST(CFX_LZWDecompressor, HandleColourCodeOutOfPalette) { 0xCF, 0x74, 0x61, 0xDF, 0x78, 0x04}; uint32_t image_size = FX_ArraySize(image_data); - uint8_t output_data[100]; + uint8_t output_data[100]; // The uncompressed data is for a 10x10 image memset(output_data, 0, sizeof(output_data)); uint32_t output_size = FX_ArraySize(output_data); - EXPECT_EQ(CFX_GifDecodeStatus::Error, - decoder->Decode(image_data, image_size, output_data, &output_size)); + EXPECT_EQ( + CFX_GifDecodeStatus::Error, + decompressor->Decode(image_data, image_size, output_data, &output_size)); } |