I'm trying to write a gif encoder by writing the raw bytes to a file. I've been following the documentation here and the Wikipedia page for GIFs. My code works for some small examples but I don't know why it fails for slightly larger images. My guess is that perhaps I have an implementation error with my LZW compression algorithm but I have no clue where it could be.
Note: The encoder is intended for a rather specific purpose so some of the code is just writing constants to the file because it won't be used outside of that scenario (unless the error is in the header section).
My writer:
class GifWriter(object):
def __init__(self, output):
self.out = open(output, 'wb')
def writeHeader(self, width, height, bpp=4):
self.bpp = max(min(bpp,8),1)
self.out.write(b'GIF89a')
self.out.write(width.to_bytes(2,byteorder='little'))
self.out.write(height.to_bytes(2,byteorder='little'))
b = 0xf0 + (self.bpp-1)
self.out.write(b.to_bytes(1,byteorder='big'))
self.out.write(b'\x00\x00')
def writeApplicationExtensionLoop(self, loopCount=0):
self.out.write(b'\x21\xFF\x0B')
self.out.write(b'\x4E\x45\x54\x53\x43\x41\x50\x45\x32\x2E\x30')
self.out.write(b'\x03\x01\x00\x00')
self.out.write(b'\x00')
# rgbIntArr = [r0, g0, b0, r1, g1, b1, ...]
# 0 <= r*,g*,b* <= 255
def writePalette(self, rgbIntArr):
palette = np.empty((len(rgbIntArr)//3,3))
i = 0
for c in rgbIntArr:
self.out.write(c.to_bytes(1,byteorder='big'))
palette[i//3][i%3] = c
i+=1
self.paletteTree = scipy.spatial.KDTree(palette,copy_data=True)
# image.shape = (w,h,3)
def writeImage(self, image, delay):
image = image[:,:,0:3]
#Graphics Control Extension
self.out.write(b'\x21\xF9\x04')
self.out.write(b'\x00') #Packed Fields
self.out.write(delay.to_bytes(2,byteorder='little')) #Delay time (1/100)
self.out.write(b'\x00') #Transparent Color Index (not used)
self.out.write(b'\x00') #Terminator
#Image Descriptor
self.out.write(b'\x2C') #Seperator
self.out.write(b'\x00\x00\x00\x00') #Top Left Corner
self.out.write(image.shape[1].to_bytes(2,byteorder='little')) #Width
self.out.write(image.shape[0].to_bytes(2,byteorder='little')) #Height
self.out.write(b'\x00') #Packed Fields
#Image Data
self.out.write(self.bpp.to_bytes(1,byteorder='big')) #LZW Minimum Code Size
maxLen = 1
currCode = 2**self.bpp+2
dict = {}
for i in range(16):
dict[chr(i)] = i
dict[chr(2**self.bpp+1)] = 2**self.bpp
dict[chr(2**self.bpp+2)] = 2**self.bpp+1
dataStr = chr(2**self.bpp+1) + "".join([chr(item) for item in self.paletteTree.query(image)[1].flatten()]) + chr(2**self.bpp+2)
ind = 0
bufferInd = 0
buffer = bytearray(255)
acc = 0x0
accInd = 0
while ind < len(dataStr):
for j in range(maxLen,0,-1):
if ind+j <= len(dataStr) and dataStr[ind:ind+j] in dict and currCode < 2**12:
acc += dict[dataStr[ind:ind+j]] << accInd
accInd += (currCode-1).bit_length()
out.append(dict[dataStr[ind:ind+j]])
if accInd > 7:
buffer[bufferInd] = acc & 0xff
acc = acc >> 8
accInd -= 8
bufferInd += 1
if bufferInd == 255:
bufferInd = 0
self.out.write(b'\xff')
self.out.write(buffer)
if not dataStr[ind:ind+j+1] in dict and ind != 0 and ind != len(dataStr)-1:
dict[dataStr[ind:ind+j+1]] = currCode
currCode += 1
maxLen = j+1
ind += j
if accInd > 0:
buffer[bufferInd] = acc & 0xff
bufferInd += 1
if bufferInd > 0:
self.out.write(bufferInd.to_bytes(1,byteorder='big'))
self.out.write(buffer[:bufferInd])
self.out.write(b'\x00')
def close(self):
self.out.write(b'\x3B')
self.out.close()
Usage:
import numpy as np
## Example 1
gif = GifWriter('e1.gif')
gif.writeHeader(3,5)
colors = [0x00,0x00,0x00,0xff,0xff,0xff]
a = np.empty((42))
a[0::3] = np.linspace(255,0,15)[:-1]
a[1::3] = np.linspace(255,0,15)[:-1]
a[2::3] = 0
for b in a.tolist():
colors.append(int(b))
gif.writePalette(colors)
gif.writeApplicationExtensionLoop()
data = np.asarray([[[0x00,0x00,0x00],[0xff,0xff,0xff],[0xff,0xff,0xff]] , [[0xff,0xff,0xff],[0x00,0x00,0x00],[0xff,0xff,0xff]] , [[0xff,0xff,0x00],[0xdd,0xdd,0x00],[0xbb,0xbb,0x00]] , [[0x99,0x99,0x00],[0x77,0x77,0x00],[0x55,0x55,0x00]] , [[0x33,0x33,0x00],[0x11,0x11,0x00],[0x00,0x00,0x00]]])
gif.writeImage(data,100)
gif.close();
## Example 2
N = 5
gif = GifWriter('e2.gif')
gif.writeHeader(N,N)
colors = [0x00,0x00,0x00,0xff,0xff,0xff]
a = np.empty((42))
a[0::3] = np.linspace(255,0,15)[:-1]
a[1::3] = np.linspace(255,0,15)[:-1]
a[2::3] = 0
for b in a.tolist():
colors.append(int(b))
gif.writePalette(colors)
gif.writeApplicationExtensionLoop()
data = np.empty((N,N,3))
data[:,:,0] = (np.flip(np.linspace(0,1,N))*np.ones((N,1)))*255
data[:,:,1] = (np.flip(np.linspace(0,1,N))*np.ones((N,1)))*255
data[:,:,2] = 0
data = data.astype(int)
gif.writeImage(data,100)
gif.close();
Example 1 from above correctly outputs the gif file Example 1. But Example 2 is incorrect as it outputs Example 2 Output when it should look like Example 2 Intended
Here is the hexdump if it is useful
Example 1:
00 01 02 03 04 05 06 07 08 09 0A 0B 0C 0D 0E 0F
00000000 47 49 46 38 39 61 03 00 05 00 F3 00 00 00 00 00 GIF89a....ó.....
00000010 FF FF FF FF FF 00 EC EC 00 DA DA 00 C8 C8 00 B6 ......ìì.ÚÚ.ÈÈ.¶
00000020 B6 00 A3 A3 00 91 91 00 7F 7F 00 6D 6D 00 5B 5B ¶.££..⌂⌂.mm.[[
00000030 00 48 48 00 36 36 00 24 24 00 12 12 00 21 FF 0B .HH.66.$$....!..
00000040 4E 45 54 53 43 41 50 45 32 2E 30 03 01 00 00 00 NETSCAPE2.0.....
00000050 21 F9 04 00 64 00 00 00 2C 00 00 00 00 03 00 05 !ù..d...,.......
00000060 00 00 04 0A 10 84 09 82 20 06 A5 D5 1E 88 00 3B ...... .¥Õ..;
Example 2:
00 01 02 03 04 05 06 07 08 09 0A 0B 0C 0D 0E 0F
00000000 47 49 46 38 39 61 05 00 05 00 F3 00 00 00 00 00 GIF89a....ó.....
00000010 FF FF FF FF FF 00 EC EC 00 DA DA 00 C8 C8 00 B6 ......ìì.ÚÚ.ÈÈ.¶
00000020 B6 00 A3 A3 00 91 91 00 7F 7F 00 6D 6D 00 5B 5B ¶.££..⌂⌂.mm.[[
00000030 00 48 48 00 36 36 00 24 24 00 12 12 00 21 FF 0B .HH.66.$$....!..
00000040 4E 45 54 53 43 41 50 45 32 2E 30 03 01 00 00 00 NETSCAPE2.0.....
00000050 21 F9 04 00 64 00 00 00 2C 00 00 00 00 05 00 05 !ù..d...,.......
00000060 00 00 04 0C 50 98 D4 80 4C 55 CC 66 0D 05 B7 46 ....PÔLUÌf..·F
00000070 00 3B .;