text: /*
   * Copyright (c) 2018-2021, Andreas Kling <kling@serenityos.org>
   *
   * SPDX-License-Identifier: BSD-2-Clause
   */
  
  #include <AK/Array.h>
  #include <AK/Debug.h>
  #include <AK/Math.h>
  #include <AK/Memory.h>
  #include <AK/MemoryStream.h>
  #include <AK/NonnullOwnPtrVector.h>
  #include <LibGfx/GIFLoader.h>
  #include <string.h>
  
  namespace Gfx {
  
  // Row strides and offsets for each interlace pass.
  static const int INTERLACE_ROW_STRIDES[] = { 8, 8, 4, 2 };
  static const int INTERLACE_ROW_OFFSETS[] = { 0, 4, 2, 1 };
  
  struct GIFImageDescriptor {
      u16 x { 0 };
      u16 y { 0 };
      u16 width { 0 };
      u16 height { 0 };
      bool use_global_color_map { true };
      bool interlaced { false };
      Color color_map[256];
      u8 lzw_min_code_size { 0 };
      Vector<u8> lzw_encoded_bytes;
  
      // Fields from optional graphic control extension block
      enum DisposalMethod : u8 {
          None = 0,
          InPlace = 1,
          RestoreBackground = 2,
          RestorePrevious = 3,
      };
      DisposalMethod disposal_method { None };
      u8 transparency_index { 0 };
      u16 duration { 0 };
      bool transparent { false };
      bool user_input { false };
  
      const IntRect rect() const
      {
          return { this->x, this->y, this->width, this->height };
      }
  };
  
  struct LogicalScreen {
      u16 width;
      u16 height;
      Color color_map[256];
  };
  
  struct GIFLoadingContext {
      enum State {
          NotDecoded = 0,
          FrameDescriptorsLoaded,
          FrameComplete,
      };
      State state { NotDecoded };
      enum ErrorState {
          NoError = 0,
          FailedToDecodeAllFrames,
          FailedToDecodeAnyFrame,
          FailedToLoadFrameDescriptors,
      };
      ErrorState error_state { NoError };
      const u8* data { nullptr };
      size_t data_size { 0 };
      LogicalScreen logical_screen {};
      u8 background_color_index { 0 };
      NonnullOwnPtrVector<GIFImageDescriptor> images {};
      size_t loops { 1 };
      RefPtr<Gfx::Bitmap> frame_buffer;
      size_t current_frame { 0 };
      RefPtr<Gfx::Bitmap> prev_frame_buffer;
  };
  
  enum class GIFFormat {
      GIF87a,
      GIF89a,
  };
  
  static Optional<GIFFormat> decode_gif_header(InputMemoryStream& stream)
  {
      static auto valid_header_87 = "GIF87a"sv;
      static auto valid_header_89 = "GIF89a"sv;
  
      Array<u8, 6> header;
      stream >> header;
  
      if (stream.handle_any_error())
          return {};
  
      if (header.span() == valid_header_87.bytes())
          return GIFFormat::GIF87a;
      if (header.span() == valid_header_89.bytes())
          return GIFFormat::GIF89a;
  
      return {};
  }
  
  class LZWDecoder {
  private:
      static constexpr int max_code_size = 12;
  
  public:
      explicit LZWDecoder(const Vector<u8>& lzw_bytes, u8 min_code_size)
          : m_lzw_bytes(lzw_bytes)
          , m_code_size(min_code_size)
          , m_original_code_size(min_code_size)
          , m_table_capacity(AK::exp2<u32>(min_code_size))
      {
          init_code_table();
      }
  
      u16 add_control_code()
      {
          const u16 control_code = m_code_table.size();
          m_code_table.append(Vector<u8> {});
          m_original_code_table.append(Vector<u8> {});
          if (m_code_table.size() >= m_table_capacity && m_code_size < max_code_size) {
  
              ++m_code_size;
              ++m_original_code_size;
              m_table_capacity *= 2;
          }
          return control_code;
      }
  
      void reset()
      {
          m_code_table.clear();
          m_code_table.extend(m_original_code_table);
          m_code_size = m_original_code_size;
          m_table_capacity = AK::exp2<u32>(m_code_size);
          m_output.clear();
      }
  
      Optional<u16> next_code()
      {
          size_t current_byte_index = m_current_bit_index / 8;
          if (current_byte_index >= m_lzw_bytes.size()) {
              return {};
          }
  
          // Extract the code bits using a 32-bit mask to cover the possibility that if
          // the current code size > 9 bits then the code can span 3 bytes.
          u8 current_bit_offset = m_current_bit_index % 8;
          u32 mask = (u32)(m_table_capacity - 1) << current_bit_offset;
  
          // Make a padded copy of the final bytes in the data to ensure we don't read past the end.
          if (current_byte_index + sizeof(mask) > m_lzw_bytes.size()) {
              u8 padded_last_bytes[sizeof(mask)] = { 0 };
              for (int i = 0; current_byte_index + i < m_lzw_bytes.size(); ++i) {
                  padded_last_bytes[i] = m_lzw_bytes[current_byte_index + i];
              }
              const u32* addr = (const u32*)&padded_last_bytes;
              m_current_code = (*addr & mask) >> current_bit_offset;
          } else {
              u32 tmp_word;
              memcpy(&tmp_word, &m_lzw_bytes.at(current_byte_index), sizeof(u32));
              m_current_code = (tmp_word & mask) >> current_bit_offset;
          }
  
          if (m_current_code > m_code_table.size()) {
              dbgln_if(GIF_DEBUG, "Corrupted LZW stream, invalid code: {} at bit index {}, code table size: {}",
                  m_current_code,
                  m_current_bit_index,
                  m_code_table.size());
              return {};
          } else if (m_current_code == m_code_table.size() && m_output.is_empty()) {
              dbgln_if(GIF_DEBUG, "Corrupted LZW stream, valid new code but output buffer is empty: {} at bit index {}, code table size: {}",
                  m_current_code,
                  m_current_bit_index,
                  m_code_table.size());
              return {};
          }
  
          m_current_bit_index += m_code_size;
  
          return m_current_code;
      }
  
      Vector<u8>& get_output()
      {
          VERIFY(m_current_code <= m_code_table.size());
          if (m_current_code < m_code_table.size()) {
              Vector<u8> new_entry = m_output;
              m_output = m_code_table.at(m_current_code);
              new_entry.append(m_output[0]);
              extend_code_table(new_entry);
          } else if (m_current_code == m_code_table.size()) {
              VERIFY(!m_output.is_empty());
              m_output.append(m_output[0]);
              extend_code_table(m_output);
          }
          return m_output;
      }
  
  private:
      void init_code_table()
      {
          m_code_table.ensure_capacity(m_table_capacity);
          for (u16 i = 0; i < m_table_capacity; ++i) {
              m_code_table.unchecked_append({ (u8)i });
          }
          m_original_code_table = m_code_table;
      }
  
      void extend_code_table(const Vector<u8>& entry)
      {
          if (entry.size() > 1 && m_code_table.size() < 4096) {
              m_code_table.append(entry);
              if (m_code_table.size() >= m_table_capacity && m_code_size < max_code_size) {
                  ++m_code_size;
                  m_table_capacity *= 2;
              }
          }
      }
  
      const Vector<u8>& m_lzw_bytes;
  
      int m_current_bit_index { 0 };
  
      Vector<Vector<u8>> m_code_table {};
      Vector<Vector<u8>> m_original_code_table {};
  
      u8 m_code_size { 0 };
      u8 m_original_code_size { 0 };
  
      u32 m_table_capacity { 0 };
  
      u16 m_current_code { 0 };
      Vector<u8> m_output {};
  };
  
  static void copy_frame_buffer(Bitmap& dest, const Bitmap& src)
  {
      VERIFY(dest.size_in_bytes() == src.size_in_bytes());
      memcpy(dest.scanline(0), src.scanline(0), dest.size_in_bytes());
  }
  
  static void clear_rect(Bitmap& bitmap, const IntRect& rect, Color color)
  {
      auto intersection_rect = rect.intersected(bitmap.rect());
      if (intersection_rect.is_empty())
          return;
  
      RGBA32* dst = bitmap.scanline(intersection_rect.top()) + intersection_rect.left();
      const size_t dst_skip = bitmap.pitch() / sizeof(RGBA32);
  
      for (int i = intersection_rect.height() - 1; i >= 0; --i) {
          fast_u32_fill(dst, color.value(), intersection_rect.width());
          dst += dst_skip;
      }
  }
  
  static bool decode_frame(GIFLoadingContext& context, size_t frame_index)
  {
      if (frame_index >= context.images.size()) {
          return false;
      }
  
      if (context.state >= GIFLoadingContext::State::FrameComplete && frame_index == context.current_frame) {
          return true;
      }
  
      size_t start_frame = context.current_frame + 1;
      if (context.state < GIFLoadingContext::State::FrameComplete) {
          start_frame = 0;
          {
              auto bitmap_or_error = Bitmap::try_create(BitmapFormat::BGRA8888, { context.logical_screen.width, context.logical_screen.height });
              if (bitmap_or_error.is_error())
                  return false;
              context.frame_buffer = bitmap_or_error.release_value_but_fixme_should_propagate_errors();
          }
          {
              auto bitmap_or_error = Bitmap::try_create(BitmapFormat::BGRA8888, { context.logical_screen.width, context.logical_screen.height });
              if (bitmap_or_error.is_error())
                  return false;
              context.prev_frame_buffer = bitmap_or_error.release_value_but_fixme_should_propagate_errors();
          }
      } else if (frame_index < context.current_frame) {
          start_frame = 0;
      }
  
      for (size_t i = start_frame; i <= frame_index; ++i) {
          auto& image = context.images.at(i);
  
          const auto previous_image_disposal_method = i > 0 ? context.images.at(i - 1).disposal_method : GIFImageDescriptor::DisposalMethod::None;
  
          if (i == 0) {
              context.frame_buffer->fill(Color::Transparent);
          } else if (i > 0 && image.disposal_method == GIFImageDescriptor::DisposalMethod::RestorePrevious
              && previous_image_disposal_method != GIFImageDescriptor::DisposalMethod::RestorePrevious) {
              // This marks the start of a run of frames that once disposed should be restored to the
              // previous underlying image contents. Therefore we make a copy of the current frame
              // buffer so that it can be restored later.
              copy_frame_buffer(*context.prev_frame_buffer, *context.frame_buffer);
          }
  
          if (previous_image_disposal_method == GIFImageDescriptor::DisposalMethod::RestoreBackground) {
              // Note: RestoreBackground could be interpreted either as restoring the underlying
              // background of the entire image (e.g. container element's background-color), or the
              // background color of the GIF itself. It appears that all major browsers and most other
              // GIF decoders adhere to the former interpretation, therefore we will do the same by
              // clearing the entire frame buffer to transparent.
              clear_rect(*context.frame_buffer, context.images.at(i - 1).rect(), Color::Transparent);
          } else if (i > 0 && previous_image_disposal_method == GIFImageDescriptor::DisposalMethod::RestorePrevious) {
              // Previous frame indicated that once disposed, it should be restored to *its* previous
              // underlying image contents, therefore we restore the saved previous frame buffer.
              copy_frame_buffer(*context.frame_buffer, *context.prev_frame_buffer);
          }
  
          if (image.lzw_min_code_size > 8)
              return false;
  
          LZWDecoder decoder(image.lzw_encoded_bytes, image.lzw_min_code_size);
  
          // Add GIF-specific control codes
          const int clear_code = decoder.add_control_code();
          const int end_of_information_code = decoder.add_control_code();
  
          const auto& color_map = image.use_global_color_map ? context.logical_screen.color_map : image.color_map;
  
          int pixel_index = 0;
          int row = 0;
          int interlace_pass = 0;
          while (true) {
              Optional<u16> code = decoder.next_code();
              if (!code.has_value()) {
                  dbgln_if(GIF_DEBUG, "Unexpectedly reached end of gif frame data");
                  return false;
              }
  
              if (code.value() == clear_code) {
                  decoder.reset();
                  continue;
              }
              if (code.value() == end_of_information_code)
                  break;
              if (!image.width)
                  continue;
  
              auto colors = decoder.get_output();
              for (const auto& color : colors) {
                  auto c = color_map[color];
  
                  int x = pixel_index % image.width + image.x;
                  int y = row + image.y;
  
                  if (context.frame_buffer->rect().contains(x, y) && (!image.transparent || color != image.transparency_index)) {
                      context.frame_buffer->set_pixel(x, y, c);
                  }
  
                  ++pixel_index;
                  if (pixel_index % image.width == 0) {
                      if (image.interlaced) {
                          if (interlace_pass < 4) {
                              if (row + INTERLACE_ROW_STRIDES[interlace_pass] >= image.height) {
                                  ++interlace_pass;
                                  if (interlace_pass < 4)
                                      row = INTERLACE_ROW_OFFSETS[interlace_pass];
                              } else {
                                  row += INTERLACE_ROW_STRIDES[interlace_pass];
                              }
                          }
                      } else {
                          ++row;
                      }
                  }
              }
          }
  
          context.current_frame = i;
          context.state = GIFLoadingContext::State::FrameComplete;
      }
  
      return true;
  }
  
  static bool load_gif_frame_descriptors(GIFLoadingContext& context)
  {
      if (context.data_size < 32)
          return false;
  
      InputMemoryStream stream { { context.data, context.data_size } };
  
      Optional<GIFFormat> format = decode_gif_header(stream);
      if (!format.has_value()) {
          return false;
      }
  
      LittleEndian<u16> value;
  
      stream >> value;
      context.logical_screen.width = value;
  
      stream >> value;
      context.logical_screen.height = value;
  
      if (stream.handle_any_error())
          return false;
  
      if (context.logical_screen.width > maximum_width_for_decoded_images || context.logical_screen.height > maximum_height_for_decoded_images) {
          dbgln("This GIF is too large for comfort: {}x{}", context.logical_screen.width, context.logical_screen.height);
          return false;
      }
  
      u8 gcm_info = 0;
      stream >> gcm_info;
  
      if (stream.handle_any_error())
          return false;
  
      stream >> context.background_color_index;
      if (stream.handle_any_error())
          return false;
  
      u8 pixel_aspect_ratio = 0;
      stream >> pixel_aspect_ratio;
      if (stream.handle_any_error())
          return false;
  
      u8 bits_per_pixel = (gcm_info & 7) + 1;
      int color_map_entry_count = 1;
      for (int i = 0; i < bits_per_pixel; ++i)
          color_map_entry_count *= 2;
  
      for (int i = 0; i < color_map_entry_count; ++i) {
          u8 r = 0;
          u8 g = 0;
          u8 b = 0;
          stream >> r >> g >> b;
          context.logical_screen.color_map[i] = { r, g, b };
      }
  
      if (stream.handle_any_error())
          return false;
  
      NonnullOwnPtr<GIFImageDescriptor> current_image = make<GIFImageDescriptor>();
      for (;;) {
          u8 sentinel = 0;
          stream >> sentinel;
  
          if (stream.handle_any_error())
              return false;
  
          if (sentinel == '!') {
              u8 extension_type = 0;
              stream >> extension_type;
              if (stream.handle_any_error())
                  return false;
  
              u8 sub_block_length = 0;
  
              Vector<u8> sub_block {};
              for (;;) {
                  stream >> sub_block_length;
  
                  if (stream.handle_any_error())
                      return false;
  
                  if (sub_block_length == 0)
                      break;
  
                  u8 dummy = 0;
                  for (u16 i = 0; i < sub_block_length; ++i) {
                      stream >> dummy;
                      sub_block.append(dummy);
                  }
  
                  if (stream.handle_any_error())
                      return false;
              }
  
              if (extension_type == 0xF9) {
                  if (sub_block.size() != 4) {
                      dbgln_if(GIF_DEBUG, "Unexpected graphic control size");
                      continue;
                  }
  
                  u8 disposal_method = (sub_block[0] & 0x1C) >> 2;
                  current_image->disposal_method = (GIFImageDescriptor::DisposalMethod)disposal_method;
  
                  u8 user_input = (sub_block[0] & 0x2) >> 1;
                  current_image->user_input = user_input == 1;
  
                  u8 transparent = sub_block[0] & 1;
                  current_image->transparent = transparent == 1;
  
                  u16 duration = sub_block[1] + ((u16)sub_block[2] << 8);
                  current_image->duration = duration;
  
                  current_image->transparency_index = sub_block[3];
              }
  
              if (extension_type == 0xFF) {
                  if (sub_block.size() != 14) {
                      dbgln_if(GIF_DEBUG, "Unexpected application extension size: {}", sub_block.size());
                      continue;
                  }
  
                  if (sub_block[11] != 1) {
                      dbgln_if(GIF_DEBUG, "Unexpected application extension format");
                      continue;
                  }
  
                  u16 loops = sub_block[12] + (sub_block[13] << 8);
                  context.loops = loops;
              }
  
              continue;
          }
  
          if (sentinel == ',') {
              context.images.append(move(current_image));
              auto& image = context.images.last();
  
              LittleEndian<u16> tmp;
  
              u8 packed_fields { 0 };
  
              stream >> tmp;
              image.x = tmp;
  
              stream >> tmp;
              image.y = tmp;
  
              stream >> tmp;
              image.width = tmp;
  
              stream >> tmp;
              image.height = tmp;
  
              stream >> packed_fields;
              if (stream.handle_any_error())
                  return false;
  
              image.use_global_color_map = !(packed_fields & 0x80);
              image.interlaced = (packed_fields & 0x40) != 0;
  
              if (!image.use_global_color_map) {
                  size_t local_color_table_size = AK::exp2<size_t>((packed_fields & 7) + 1);
  
                  for (size_t i = 0; i < local_color_table_size; ++i) {
                      u8 r = 0;
                      u8 g = 0;
                      u8 b = 0;
                      stream >> r >> g >> b;
                      image.color_map[i] = { r, g, b };
                  }
              }
  
              stream >> image.lzw_min_code_size;
              if (stream.handle_any_error())
                  return false;
  
              u8 lzw_encoded_bytes_expected = 0;
  
              for (;;) {
                  stream >> lzw_encoded_bytes_expected;
  
                  if (stream.handle_any_error())
                      return false;
  
                  if (lzw_encoded_bytes_expected == 0)
                      break;
  
                  Array<u8, 256> buffer;
                  stream >> buffer.span().trim(lzw_encoded_bytes_expected);
  
                  if (stream.handle_any_error())
                      return false;
  
                  for (int i = 0; i < lzw_encoded_bytes_expected; ++i) {
                      image.lzw_encoded_bytes.append(buffer[i]);
                  }
              }
  
              current_image = make<GIFImageDescriptor>();
              continue;
          }
  
          if (sentinel == ';') {
              break;
          }
  
          return false;
      }
  
      context.state = GIFLoadingContext::State::FrameDescriptorsLoaded;
      return true;
  }
  
  GIFImageDecoderPlugin::GIFImageDecoderPlugin(const u8* data, size_t size)
  {
      m_context = make<GIFLoadingContext>();
      m_context->data = data;
      m_context->data_size = size;
  }
  
  GIFImageDecoderPlugin::~GIFImageDecoderPlugin() { }
  
  IntSize GIFImageDecoderPlugin::size()
  {
      if (m_context->error_state == GIFLoadingContext::ErrorState::FailedToLoadFrameDescriptors) {
          return {};
      }
  
      if (m_context->state < GIFLoadingContext::State::FrameDescriptorsLoaded) {
          if (!load_gif_frame_descriptors(*m_context)) {
              m_context->error_state = GIFLoadingContext::ErrorState::FailedToLoadFrameDescriptors;
              return {};
          }
      }
  
      return { m_context->logical_screen.width, m_context->logical_screen.height };
  }
  
  void GIFImageDecoderPlugin::set_volatile()
  {
      if (m_context->frame_buffer) {
          m_context->frame_buffer->set_volatile();
      }
  }
  
  bool GIFImageDecoderPlugin::set_nonvolatile(bool& was_purged)
  {
      if (!m_context->frame_buffer)
          return false;
      return m_context->frame_buffer->set_nonvolatile(was_purged);
  }
  
  bool GIFImageDecoderPlugin::sniff()
  {
      InputMemoryStream stream { { m_context->data, m_context->data_size } };
      return decode_gif_header(stream).has_value();
  }
  
  bool GIFImageDecoderPlugin::is_animated()
  {
      if (m_context->error_state != GIFLoadingContext::ErrorState::NoError) {
          return false;
      }
  
      if (m_context->state < GIFLoadingContext::State::FrameDescriptorsLoaded) {
          if (!load_gif_frame_descriptors(*m_context)) {
              m_context->error_state = GIFLoadingContext::ErrorState::FailedToLoadFrameDescriptors;
              return false;
          }
      }
  
      return m_context->images.size() > 1;
  }
  
  size_t GIFImageDecoderPlugin::loop_count()
  {
      if (m_context->error_state != GIFLoadingContext::ErrorState::NoError) {
          return 0;
      }
  
      if (m_context->state < GIFLoadingContext::State::FrameDescriptorsLoaded) {
          if (!load_gif_frame_descriptors(*m_context)) {
              m_context->error_state = GIFLoadingContext::ErrorState::FailedToLoadFrameDescriptors;
              return 0;
          }
      }
  
      return m_context->loops;
  }
  
  size_t GIFImageDecoderPlugin::frame_count()
  {
      if (m_context->error_state != GIFLoadingContext::ErrorState::NoError) {
          return 1;
      }
  
      if (m_context->state < GIFLoadingContext::State::FrameDescriptorsLoaded) {
          if (!load_gif_frame_descriptors(*m_context)) {
              m_context->error_state = GIFLoadingContext::ErrorState::FailedToLoadFrameDescriptors;
              return 1;
          }
      }
  
      return m_context->images.size();
  }
  
  ErrorOr<ImageFrameDescriptor> GIFImageDecoderPlugin::frame(size_t index)
  {
      if (m_context->error_state >= GIFLoadingContext::ErrorState::FailedToDecodeAnyFrame) {
          return Error::from_string_literal("GIFImageDecoderPlugin: Decoding failed"sv);
      }
  
      if (m_context->state < GIFLoadingContext::State::FrameDescriptorsLoaded) {
          if (!load_gif_frame_descriptors(*m_context)) {
              m_context->error_state = GIFLoadingContext::ErrorState::FailedToLoadFrameDescriptors;
              return Error::from_string_literal("GIFImageDecoderPlugin: Decoding failed"sv);
          }
      }
  
      if (m_context->error_state == GIFLoadingContext::ErrorState::NoError && !decode_frame(*m_context, index)) {
          if (m_context->state < GIFLoadingContext::State::FrameComplete || !decode_frame(*m_context, 0)) {
              m_context->error_state = GIFLoadingContext::ErrorState::FailedToDecodeAnyFrame;
              return Error::from_string_literal("GIFImageDecoderPlugin: Decoding failed"sv);
          }
          m_context->error_state = GIFLoadingContext::ErrorState::FailedToDecodeAllFrames;
      }
  
      ImageFrameDescriptor frame {};
      frame.image = TRY(m_context->frame_buffer->clone());
      frame.duration = m_context->images.at(index).duration * 10;
  
      if (frame.duration <= 10) {
          frame.duration = 100;
      }
  
      return frame;
  }
  
  }
  