Designing a Smaller File Format (s.gf)

March 13, 2025

Introduction

I've always been interested in how file formats like PNG, SVG, and WAV are designed and implemented. A few months ago, I finally decided to try and tackle creating a file format of my own. Going in to this, I had a few goals:

1. Create a file format that actually stores data (crazy, right?).
2. Attempt to optimize and shrink down these file sizes as much as possible.
3. Create a format that is smaller than PNG.

I thought the first two would be very easy to achieve, but I wasn't sure how to achieve that last goal. However, that was not my main concern at the beginning. First, I had to actually create a working file encoding and decoding system.

This article is not going to be a step-by-step tutorial. Instead, it's going to be a general write-up of my rationale and implementation of my file format, SGF (which stands for Simple Graphics Format). More specifics can be found on the official product page, but I did place a few restrictions on this format:

1. We have a maximum palette size of 256 colors. Why I picked this limit will make sense later on.
2. I have always preferred lossless file formats, so SGF is similarly lossless.
3. I would like the specifications to be fairly straightforward, so a simple plan of attack was used.

Environment

We're getting close to actually implementing this, but I wanted to briefly go over my development environment for this project.

First of all, I used Visual Studio Code as it's easily what I'm most comfortable using. For the same reason, I wrote all the code in Python, my best language. I have some plans to port it to C/C++, but that's a project for another day. Since I needed a way to load and save image files, I decided to use the Pillow library. Pillow's Image class comes with some helpful functions (such as getting the colors in an image), and allows us to represent an image as a series of pixels.

from PIL import Image
import numpy as np

# load an image
image = Image.open('file_path.png')

# get the size and pixel data
size = image.size
pixels = image.getdata()

# get the colors
colors = image.getcolors()

# convert pixels to a numpy array with 8-bit elements
pixels = np.array(pixels, dtype=np.uint8)

Since we're working with binary data, we also need a way to read, write, and store this data. Luckily, this is very easy to do in Python. In order to store a stream of binary data, we can use the bytearray object:

# store the current data stream
data = bytearray()

# open file in write mode (wb => write binary)
with open('file_name.sgf', 'wb') as file:
    # write the binary data
    file.write(data)

# pointer to store the current location
bp = 0
data = None

# open file in read mode (rb => read binary)
with open('file_name.sgf', 'rb') as file:
    data = file.read()

Then, to parse the binary data we can use the built-in struct module. I'd suggest reading the official documentation if you're curious, but you likely won't need to for this article. Also, in order to ease the process of development I created a helper function to parse the data:

def parse_bytes(format):
    nonlocal bp
    
    # decode
    out = struct.unpack(format, data[bp:bp+struct.calcsize(format)])
    bp += struct.calcsize(format)

    # if there's only 1 element, just return it
    if len(out) == 1:
        return out[0]
    # else, return all elements
    return out

This function takes in a format, and returns either a single value, or an array of values. You can see how to create a format string in the documentation, but for our purposes we will be using strings containing B and H which stand for unsigned bytes and unsigned shorts, respectively.

Version 1 - Simplicity

Version 1 starts very simply as it was a way to make sure I actually knew what I was doing. For this, I took the very naive approach of storing the color data of each pixel individually. Along with the color data, I also needed to store how big the image was, so I did that as well.

Implementation

In order to encode and decode an image, we only need to store the image size and the pixel data.

# ...initialize data

# store size
data += struct.pack('HH', size[0], size[1])

# store pixel data (provided through numpy arrays)
data += pixels.tobytes()

# ...write to file

# ...read data

# parse size
size = parse_bytes('HH')

# parse pixel data (again using numpy)
pixels = np.frombuffer(data, offset=bp, dtype=uint8)

# construct image
image = Image.frombytes(mode="RGBA", size=size, data=pixels)

The last line of the decoding step is one of the most important. It's also why we need to have the pixel data in the form of a numpy array. I won't get into the details, but the frombytes method requires an object that supports the __array_interface__ (which comes from numpy).

Benchmarks

At the end of each version, I'll go over where we stand in regards to our file size, and how it compares to the PNG equivalent. In the beginning, we will see our files are much larger than their PNG counterparts, but we'll slowly close this gap.

So far there's not really much to say. Besides the random.png image, the closest test image we have is still 10 times larger than its PNG counterpart.

Version 2 - Palettes

When looking to reduce the file size at this point, I thought about where redundant data might lie. For file formats, this is a very important thing to think about and is ultimately how we will reduce the size in each version. The first spot where I saw redundant data was how often we repeat the colors we use. Especially for a limited color palette, we can find ourselves using the same color over and over.

Instead of storing each of these colors as a unique 4-byte color value, what if we stored a pointer to this color value? This is the line of reasoning I used to get to this second version:

1. Find each unique color in the image and store them in a linear array (our palette).
2. For each color in the image, find the index of the color it uses, and store that instead of the raw color.

Image - Green Slime

Description

We can see in this image, we are using the following colors:

• Transparent: #00000000
• Green 1: ■ #b8ed92ff
• Green 2: ■ #86e65aff
• Green 3: ■ #6dd144ff
• Green 4: ■ #3ba126ff
• Green 5: ■ #173f0bff

That's only 6 unique colors! Having to only store a single instance of each color could have massive file size improvements!

Since we stored every color we used in the image, we can reduce the space each pixel uses to just 1 byte each. However, this does come with a drawback. As mentioned in the beginning, the SGF file format has a limited color palette size. Since we cut each index to just 1 byte, we can have at most 256 unique indexes - which is where the 256-color palette comes from. For my use case, this doesn't affect much because most of the time I don't get anywhere near 256 unique colors.

Implementation

This version changes how we will encode and decode colors, since we can't just push the color values into one big list. Instead, we need to do a little more work before we can actually read and write the color values.

# note: getcolors actually returns: [# of pixels using the color, color]
# so we will need to isolate just the color
colors = [color[1] for color in image.getcolors()

# store how many colors are in the palette
data += struct.pack('B', len(colors))
# store each color using numpy
data += np.array(colors, dtype=uint8).tobytes()

# convert the colors list into a palette dictionary
palette = {colors[i]: i for i in range(len(colors))}

# we use a list since we don't need tobytes
pixels = list(image.getdata())

for pixel in pixels:
    # append each palette index
    data += palette[pixel]

# ...parse the size

color_count = parse_bytes('B')

palette = []

# load the palette
for i in range(color_count):
    palette.append(parse_bytes('BBBB'))

# for each pixel, retrieve the color from the index
pixels = []
pixel_count = size[0] * size[1]

for i in range(pixel_count):
    pixels.append(palette[parse_bytes('B')])

# ...build the image

Once we have all the pixels parsed, we can then build the image in the same way as before!

Benchmarks

Looking at the results, we can see that we have cut our file sizes to 25% of their original size! Thinking about the changes we've made, this makes a lot of sense. We cut down each pixel from 4 bytes to just 1 byte - the same 25% reduction. It turns out that storing the color palette is negligible in most cases (at least in my test images). However, we're still a good ways away from being equal to the PNG sizes.

Version 3 - Stacking

Now that we have some easier optimizations out of the way, we can start to think a little more about how this format will be used specifically. For me, I would likely use it for game sprites and general pixel art images. Typically, game sprites will have a lot of empty space surrounding the main sprite.

Image - Green Slime (Empty Space)

Image - Green Slime (Filled Space)

And this doesn't even have to be empty space! With my style, and with a lot of pixel art in general, a lot of neighboring pixels are also the same colors. If we could group, or stack, these lines of pixels, then we could really reduce the amount of space we use on average. For now, primarily due to ease of implementation, we will look at horizontal lines of pixels. When we find a stretch of pixels that use the same color, we can group them into one chunk of information, instead of a bunch of individual indexes.

Implementation

It's at this point is where the encoding and decoding process gets a little more complicated. For encoding, we need to keep track of how many consecutive pixels we see. For decoding, we need to make sure we repeat each pixel the correct amount of time.

previous = None
reps = 0

for pixel in pixels:
    if previous != palette[pixel]:
        # add previous chain (if it exists)
        if previous != None:
            data += struct.pack('BB', reps, previous)
        reps = 1
    else:
        # Start a new line of repetition
        if reps >= 255:
            data += struct.pack('BB', reps, previous)
            reps = 0
        reps += 1

# add the final chain
data += struct.pack('BB', reps, previous)

# previous version
for i in range(pixel_count):
    # ...

# new version
i = 0
while i < pixel_count:
    # ...

i = 0

while i < pixel_count:
    reps, index = parse_bytes('BB')
    
    # add the color 'reps' times
    pixels += [palette[index] for _ in range(reps)]
    
    i += reps

# ...build the image

The reason we need to cap the repetitions at 256 is the same reason we needed to cap the palette size: we want to store the value in a single byte. We could increase how much space we give the repetition value, but that would likely just cause the overall file size to increase since most images won't reach 256 repetitions to begin with.

Benchmarks

Overall, it turns out that this optimization reduces our file size to 25% of the previous version's size. I don't have a rationale this time, and the results will likely depend heavily on the test images used. Regardless, this is another massive reduction! And if we look at the data, we can see that in some test images, we have a result that ends up smaller than the equivalent PNG! This is very exciting, but there one more tweak before I'll call it quits.

Version 4 - Compression

This version is more like a cherry on top rather than anything major. Most file formats will use compression algorithms to get their file sizes as small as they can. In my original implementation, I thought that this would be considered “cheating” since I didn't know that the PNG format uses the DEFLATE algorithm. However, I'm well aware of this fact now and feel no guilt towards using compression for SGF.

While PNG uses the DEFLATE algorithm, we will be using the GZIP algorithm. GZIP is based off the DEFLATE algorithm, so we're on a pretty even playing field.

Implementation

As mentioned before, this requires less effort and is more of an extra little addition. All we need to do is import Python's built-in gzip module:

import gzip

with open('file_name.sgf', 'wb') as file:
    file.write(gzip.compress(data))

with gzip.open('file_name.sgf', 'rb') as file:
    data = file.read()

Benchmarks

Despite this being a seemingly simple addition, it has massive changes in our resulting file sizes. So much so that most of our files are now smaller than their PNG equivalents! When I started this project, I did not expect to get to this point, and it still surprises me to see that I ended up at this point.

Conclusion

Overall, I'm very happy with how this project went. I ended up being able to shave off much more data than I originally imagined. As I continue to develop the Simple Suite, I want everything to mesh as well as possible. I'm planning on developing various different tools, and I can see this file format being used in a few of them. Until then though, SGF will remain as an example of how effective optimization can be.