# gifWriter
# Outputs efficient GIF images. Supports LZW compression, transparency, and usage
# of fewer than 256 colours. Not optimised: is quite slow.

# Caution! Usage and redistribution of this module may be illegal in countries recognising
# the Unisys LZW patent. This sucks. Other than this restriction you can consider this
# public domain code.

# Module contains one function, save, with following arguments:
#   f -- filename or file object (only write() support required, no seeking)
#   data -- list or other iterable object returning integer colour numbers for image data
#   size -- tuple (width, height), size of image
#   palette -- list of tuples (red, green, blue) of integer 0-255 colour values
#   transparency -- colour number to make transparent or None (default None)
#   interlace -- boolean, true if image is to be interlaced (default false)

# Example usage, given a PIL image 'im' with mode 'P':

# palette= []
# for i in range(0, len(im.palette.data), 3):
#   palette.append(tuple(map(ord, im.palette.data[i:i+3])))
# gifWriter.save('D:\\blob.gif', im.getdata(), im.size, palette, None, 0)

# Note! PIL, at least version 1.0, has an issue where palettes do not seem to be
# attached to newly-converted-to-'P'-mode images. If you used ADAPTIVE mode to
# quantise the image so you don't have the palette, the only way I know of to get
# it is to image.save and load it back in. :-(

gifError= 'gifError'

_b16= lambda n: chr(n&0xFF)+chr((n>>8)&0xFF)
[false, true]= range(2)

# As per the GIF specification, there are three levels of encoding between the input
# pixel colour numbers and the output file. These are represented by three Python
# objects which are piped together:

# Pixel colour numbers -> _lzwCompressor ->
# code word bits -> _bytePacker ->
# packed bytes -> _blockChunker ->
# blocks of max 255 bytes -> output file

# _lzwCompressor
# Pipe stream of symbols (of bps bits) to stream of variable length code words.
# Clear dictionary when it is full (for compatibility with old GIF decoders)

_bpsMIN= 2
_bpcMAX= 12

class _lzwCompressor:
  def __init__(self, output, bps):
    self.output= output
    self.bps= max(bps, _bpsMIN)
    self.bpc= self.bps+1
    self.queue= []
    self.clear()
  def clear(self):
    self.output(2**self.bps, self.bpc)
    self.bpc= self.bps+1
    self.cnext= (2**self.bps)+2
    self.dictionary= {}
    for i in range(2**self.bps):
      self.dictionary[(i,)]= i

  def write(self, value):
    key= tuple(self.queue+[value])
    if self.dictionary.has_key(key):
      self.queue.append(value)
    else:
      self.output(self.dictionary[tuple(self.queue)], self.bpc)
      self.queue= [value]
      if self.cnext>=2**self.bpc:
        if self.bpc>=_bpcMAX:
          self.clear()
        else:
          self.bpc= self.bpc+1
      self.dictionary[key]= self.cnext
      self.cnext= self.cnext+1

  def close(self):
    if self.queue!='':
      self.output(self.dictionary[tuple(self.queue)], self.bpc)
    self.output(2**self.bps+1, self.bpc)

# _bytePacker
# Pipe stream of arbitrary length bits into bytes

class _bytePacker:
  def __init__(self, output):
    self.output= output
    self.queue= self.bits= 0
  def write(self, value, bits):
    self.queue= self.queue+(value<<self.bits)
    self.bits= self.bits+bits
    while self.bits>=8:
      self.output(chr(self.queue&0xFF))
      self.queue= self.queue>>8
      self.bits= self.bits-8
  def close(self):
    self.output(chr(self.queue))
    self.queue= self.bits= 0

# _blockChunker
# Pipe stream of bytes into blocks of not more than 255 characters

class _blockChunker:
  def __init__(self, output):
    self.output= output
    self.queue= ''
  def write(self, value):
    self.queue= self.queue+value
    while len(self.queue)>=255:
      self.output(chr(255))
      self.output(self.queue[:255])
      self.queue= self.queue[255:]
  def close(self):
    if len(self.queue)>0:
      self.output(chr(len(self.queue)))
      self.output(self.queue)
      self.queue= ''
    self.output(chr(0))

# Main save function

def save(f, data, (width, height), palette, transparency= None, interlace= false):

# f can be a filename or a file object

  if type(f)==type('string'):
    f= open(f, 'wb')
    save(f, data, (width, height), palette, transparency, interlace)
    f.close()
    return

# check there's enough data for size

  if len(data)<width*height:
    raise gifError, 'Not enough data was passed to match the given image size'

# pad palette out to 2**n entries

  if palette==None:
    raise gifError, 'No palette was passed'
  cpp= len(palette)
  bpp=1
  while cpp>2:
    bpp= bpp+1
    cpp= cpp/2
  if bpp>8:
    raise gifError, 'More than 256 colours required to store image'
  palette= palette+[(0, 0, 0)]*((2**bpp)-len(palette))

# write global header

  f.write(['GIF87a', 'GIF89a'][transparency!=None])
  f.write(_b16(width))
  f.write(_b16(height))
  f.write(chr(0xF0+bpp-1))
  f.write(chr(0)*2)

# write global palette

  for (r, g, b) in palette:
    f.write(chr(r)+chr(g)+chr(b))

# write graphic control extension block if transparency is required

  if transparency!=None:
    f.write(chr(0x21)+chr(0xF9)+chr(0x04))
    f.write(chr(0x01)+chr(0x00)+chr(0x00))
    f.write(chr(transparency)+chr(0x00))

# write image descriptor

  f.write(chr(0x2C))
  f.write(_b16(0))
  f.write(_b16(0))
  f.write(_b16(width))
  f.write(_b16(height))
  f.write(chr([0, 0x40][interlace]))

  f.write(chr(max(_bpsMIN, bpp)))

# set up encoding pipes

  chunk= _blockChunker(f.write)
  pack= _bytePacker(chunk.write)
  compress= _lzwCompressor(pack.write, bpp)

# process lines of input data, either from start to end or interlaced

  for (start, step) in [ [(0, 1)], [(0, 8), (4, 8), (2, 4), (1, 2)] ][interlace]:
    for y in xrange(start, height, step):
      for x in xrange(width):
        compress.write(data[y*width+x])

# flush all buffers, write terminating byte and finish

  compress.close()
  pack.close()
  chunk.close()
  f.write(chr(0x3B))