# Copyright(C) TAKASUGI Shinji (ts@sf.airnet.ne.jp)

package gifinput;

sub bitstream_init
{  $byte_offset = 0;
   $bit_offset = 0;
   undef @bitstream_buffer;
}

sub bitstream_read
{  my($bit_width, $data, $current_offset, $read_bits);

   $bit_width = $_[0];
   return 0 if ($bit_width > 32 || $bit_width == 0);

   $current_offset = $byte_offset;
   $data = $bitstream_buffer[$current_offset++] >> $bit_offset;
   $read_bits = 8 - $bit_offset;

   while ($read_bits < $bit_width)
   {  $data |= $bitstream_buffer[$current_offset++] << $read_bits;
      $read_bits += 8;
   }

   $bit_offset += $bit_width;
   $byte_offset += int($bit_offset / 8);
   $bit_offset %= 8;

   $data & ((2 << ($bit_width - 1)) - 1);
}

sub bitstream_remain
{  (@bitstream_buffer - $byte_offset) * 8 - $bit_offset;
}

sub bitstream_remove
{  if ($byte_offset > 0)
   {  splice(@bitstream_buffer, 0, $byte_offset);
      $byte_offset = 0;
   }
}

sub bitstream_set
{  push(@bitstream_buffer, unpack('C*', $_[0]));
}

sub gif_init
{  &bitstream_init();
   undef $pixels;
   $palette = [];
   undef $pixel_offset;
   undef @gif_code_table;
   undef $cx;
   undef $cy;
   undef $color_bits;
   undef $root_bits;
   undef $colors;
   undef $transparent;
   undef $flush_code;
   undef $terminate_code;
   undef $current_bit_width;
   undef $next_code;

   &gif_read_header(@_);
}

sub gif_read_header
{  my($file, $buffer, @unpacked_bytes, @rgb, $index);

   $file = $_[0];
   read($file, $buffer, 13);

   return 0 if ($buffer !~ /^GIF\d\d[A-Za-z]/);

   @unpacked_bytes = unpack('x6C5', $buffer);

   $cx = $unpacked_bytes[0] + ($unpacked_bytes[1] << 8);
   $cy = $unpacked_bytes[2] + ($unpacked_bytes[3] << 8);
   $color_bits = ($unpacked_bytes[4] & 7) + 1;

   $colors = 1 << $color_bits;
   read($file, $buffer, $colors * 3);
   @rgb = unpack('C*', $buffer);

   $#$palette = $colors - 1;
   for ($index = 0; $index < $colors; $index++)
   {  $palette->[$index] =
	  ($rgb[$index * 3] << 16) + ($rgb[$index * 3 + 1] << 8) + $rgb[$index * 3 + 2];
   }

   1;
}

sub gif_read_chunk
{  my($file, $buffer) = $_[0];
   read($file, $buffer, ord(getc($file)));
   $buffer;
}

sub gif_remove_interlace
{  my(@lines, $y, $y_source);
   $#lines = $cy - 1;

   for ($y = 0; $y < $cy; $y += 8)
   {  $lines[$y_source++] = $y;
   }

   for ($y = 4; $y < $cy; $y += 8)
   {  $lines[$y_source++] = $y;
   }

   for ($y = 2; $y < $cy; $y += 4)
   {  $lines[$y_source++] = $y;
   }

   for ($y = 1; $y < $cy; $y += 2)
   {  $lines[$y_source++] = $y;
   }

   $y = 0;
   while ($y < $cy)
   {  while (($y_source = $lines[$y]) != $y)
      {  my($offset1, $offset2, $line);
	 $offset1 = $cx * $y;
	 $offset2 = $cx * $y_source;
	 $line = substr($pixels, $offset1, $cx);
	 substr($pixels, $offset1, $cx) = substr($pixels, $offset2, $cx);
	 substr($pixels, $offset2, $cx) = $line;

	 $lines[$y] = $lines[$y_source];
	 $lines[$y_source] = $y_source;
      }

      $y++;
   }
}

sub gif_read
{  my($file, $char, $buffer, @unpacked_bytes, $flushed, $interlace) = $_[0];

   return [] if !&gif_init($file);

   $pixels = "\x00" x ($cx * $cy);

   while (($char = getc($file)) ne '')
   {  $char = ord($char);

      if ($char == 0x3b)
      {  &gif_remove_interlace() if $interlace;
	 return [$cx, $cy, $pixels, $palette, $transparent];
      }
      elsif ($char == 0x21)
      {  if (($char = ord(getc($file))) == 0xf9)
	 {  read($file, $buffer, 6);
	    @unpacked_bytes = unpack('C6', $buffer);
	    return [] if ($unpacked_bytes[0] != 4 || $unpacked_bytes[5] != 0);

	    if ($unpacked_bytes[1] & 1)
	    {  $transparent = $unpacked_bytes[4];
	    }
	 }
         else
	 {  while (&gif_read_chunk($file) ne '')
	    {
	    }
	 }
      }
      elsif ($char == 0x2c)
      {  my($gif_code_old, $flags);

	 read($file, $buffer, 9);
	 $flags = unpack('x8C', $buffer);

	 return [] if ($flags & 0x80);
	 $interlace = 1 if ($flags & 0x40);

	 $root_bits = ord(getc($file));
	 $flush_code = 1 << $root_bits;
	 $terminate_code = $flush_code + 1;

	 &gif_create_code_array();
	 $flushed = 1;

	 while (($buffer = &gif_read_chunk($file)) ne '')
	 {  &bitstream_remove();
	    &bitstream_set($buffer);

	    while (&bitstream_remain() >= $current_bit_width)
	    {  my($code) = &bitstream_read($current_bit_width);

	       if ($code == $flush_code)
	       {  if (!$flushed)
		  {  &gif_create_code_array();
		     $flushed = 1;
		  }
	       }
	       elsif ($code == $terminate_code)
	       {  &gif_remove_interlace() if $interlace;
		  return [$cx, $cy, $pixels, $palette, $transparent];
	       }
	       else
	       {  my($gif_code) = $gif_code_table[$code];

		  if ($flushed)
		  {  return [] if ($gif_code->[1] > 1);

		     vec($pixels, $pixel_offset++, 8) = $gif_code->[2];
		     $flushed = 0;
		  }
		  elsif ($code < $next_code)
		  {  my($gif_code_2) = $gif_code;

		     do
		     {  vec($pixels, $pixel_offset + $gif_code_2->[1] - 1, 8) = $gif_code_2->[2];
		     } while (($gif_code_2 = $gif_code_2->[0]) ne '');

		     $gif_code_table[$next_code++] =
			 [$gif_code_old, $gif_code_old->[1] + 1, vec($pixels, $pixel_offset, 8)];

		     $pixel_offset += $gif_code->[1];
		  }
		  else
		  {  my($gif_code_2) = $gif_code_old;

		     do
		     {  vec($pixels, $pixel_offset + $gif_code_2->[1] - 1, 8) = $gif_code_2->[2];
		     } while (($gif_code_2 = $gif_code_2->[0]) ne '');

		     $char = vec($pixels, $pixel_offset, 8);
		     $pixel_offset += $gif_code_old->[1];
		     vec($pixels, $pixel_offset++, 8) = $char;

		     $gif_code = [$gif_code_old, $gif_code_old->[1] + 1, $char];
		     $gif_code_table[$next_code++] = $gif_code;
		  }

		  $gif_code_old = $gif_code;

		  if ($current_bit_width < 12
		      && ($next_code & ($next_code - 1)) == 0)
		  {  $current_bit_width++;
		  }
	       }
	    }
	 }
      }
      else
      {  return [];
      }
   }

   [];
}

sub gif_create_code_array
{  my($index);

   $current_bit_width = $root_bits + 1;
   $next_code = $terminate_code + 1;

   for ($index = 0; $index < $colors; $index++)
   {  $gif_code_table[$index] = ['', 1, $index];
   }
}

1;