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

package gifoutput;

sub bitstream_init
{  undef $remain_data;
   undef $remain_bits;
   undef $current_buffer;
   undef @bitstream_buffer;
}

sub bitstream_write
{  my($data, $bit_width) = @_;

   return 0 if ($bit_width > 32);
   return 1 if ($bit_width == 0);

   $data &= (2 << ($bit_width - 1)) - 1;
   $remain_data |= ($data << $remain_bits);
   $data = int($data / (2 ** (32 - $remain_bits)));

   $remain_bits += $bit_width;

   while ($remain_bits >= 8)
   {  $current_buffer .= chr($remain_data & 0xff);
      if (length($current_buffer) >= 255)
      {  push(@bitstream_buffer, $current_buffer);
	 undef $current_buffer;
      }

      $remain_data = int($remain_data / 256) | ($data << 24);
      $data = int($data / 256);
      $remain_bits -= 8;
   }

   1;
}

sub bitstream_flush
{  if ($remain_bits)
   {  $current_buffer .= chr($remain_data & 0xff);

      if (length($current_buffer) == 255)
      {  push(@bitstream_buffer, $current_buffer);
	 undef $current_buffer;
      }

      $remain_data = 0;
      $remain_bits = 0;
   }

   if ($current_buffer ne '')
   {  push(@bitstream_buffer, $current_buffer);
      undef $current_buffer;
   }
}

sub hashlist_init
{  my($colors, $root_bits) = @_;
   my($index);

   undef %gif_code_hash;
   for ($index = 0; $index < $colors; $index++)
   {  $gif_code_hash{'', $index} = ['', $index, $index];
   }

   $current_bit_width = $root_bits + 1;
   $next_code = $terminate_code + 1;
   $previous_bytes = '';
}

sub hashlist_add
{  my($header, $char) = @_;
   $gif_code_hash{$header, $char} = [$header, $char, $next_code++];
}

sub gif_write_byte
{  my($char, $max_bits) = @_;
   $char += 0;

   my($hash) = $gif_code_hash{$previous_bytes, $char};

   if ($hash ne '')
   {  $previous_bytes = $hash;
   }
   else
   {  &bitstream_write($previous_bytes->[2], $current_bit_width);

      $current_bit_width++ if ($next_code == (1 << $current_bit_width));

      if ($current_bit_width > $max_bits
	  || ($current_bit_width == 12 && $next_code == 0xfff))
      {  bitstream_write($flush_code, $current_bit_width);
	 &hashlist_init($colors, $root_bits);
      }
      else
      {  &hashlist_add($previous_bytes, $char);
      }

      $previous_bytes = $gif_code_hash{'', $char};
   }
}

sub power_2_ceil
{  my($number, $power) = $_[0];

   while ($number > 2 ** $power)
   {  $power++;
   }

   return $power;
}

sub gif_set_interlace
{  my($cx, $cy, $pixels) = @_;
   my(@lines, $y, $y_dest);
   $#lines = $cy - 1;

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

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

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

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

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

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

      $y++;
   }

   $pixels;
}

sub gif_write
{  my($file, $cx, $cy, $pixels, $palette, $transparent, $interlace) = @_;

   $colors = @$palette;
   $color_bits = &power_2_ceil($colors);
   $color_bits = 1 if ($color_bits < 1);
   $root_bits = ($color_bits == 1 ? 2 : $color_bits);

   $flush_code = 1 << $root_bits;
   $terminate_code = $flush_code + 1;

   &gif_write_header($file, $cx, $cy, $palette, $color_bits, $transparent);
   &gif_write_pixels($file, $cx, $cy, $pixels, $interlace);
}

sub gif_write_header
{  my($file, $cx, $cy, $palette, $color_bits, $transparent) = @_;
   my($index, $rgb);

   print $file 'GIF89a', pack('vvCCC', $cx, $cy,
			      0x80 | (($color_bits - 1) << 4) | ($color_bits - 1),
			      0, 0);

   for ($index = 0; $index < 2 ** $color_bits; $index++)
   {  $rgb = $palette->[$index];
      print $file pack('C3', $rgb >> 16, ($rgb >> 8) & 0xff, $rgb & 0xff);
   }

   if (defined($transparent))
   {  print $file pack('C8', 0x21, 0xf9, 4, 1, 0, 0, $transparent, 0);
   }
}

sub gif_write_pixels
{  my($file, $cx, $cy, $pixels, $interlace) = @_;
   $pixels = &gif_set_interlace($cx, $cy, $pixels) if $interlace;

   print $file pack('CvvvvCC', 0x2c, 0, 0, $cx, $cy,
		    $interlace ? 0x40 : 0, $root_bits);

   &bitstream_init();
   &hashlist_init($colors, $root_bits);

   &bitstream_write($flush_code, $current_bit_width);

   my($index, $x, $y) = 0;
   &gif_write_byte(ord($1), 12) while ($pixels =~ /(.)/gs);

   if ($previous_bytes ne '')
   {  &bitstream_write($previous_bytes->[2], $current_bit_width);
   }

   &bitstream_write($terminate_code, $current_bit_width);
   &bitstream_flush();

   foreach (@bitstream_buffer)
   {  print $file chr(length($_)), $_;
   }

   print $file pack('CC', 0, 0x3b);
}

1;