Thursday, April 5, 2012

A minimal encoder for uncompressed PNGs

I've often wondered how hard it is to output a PNG file directly, without using a library or a standard tool like pnmtopng. (I'm not sure when you'd actually want to do this; maybe for a tiny embedded system with a web interface.)

I found that constructing a simple, uncompressed PNG does not require a whole lot of code, but there are some odd details I got wrong on the first try. Here's a crash course in writing a minimal PNG encoder. We'll use only a small subset of the PNG specification, but I'll link to the full spec so you can read more.

The example code is not too fast; it's written in Python and has tons of string copying everywhere. My goal was to express the idea clearly, and let you worry about coding it up in C for your embedded system or whatever. If you're careful, you can avoid ever copying the image data.

We will assume the raw image data is a Python byte string (non-Unicode), consisting of one byte each for red, green, and blue, for each pixel in English reading order. For reference, here is how we'd "encode" this data in the much simpler PPM format.

def to_ppm(width, height, data):
return 'P6\n%d %d\n255\n%s' % (width, height, data)

I lied when I said we'd use no libraries at all. I will import Python's standard struct module. I figured an exercise in converting integers to 4-byte big endian format would be excessively boring. Here's how we do it with struct.

import struct

def be32(n):
return struct.pack('>I', n)

A PNG file contains a sequence of data chunks, each with an associated length, type, and CRC checksum. The type is a 4-byte quantity which can be interpreted as four ASCII letters. We'll implement crc later.

def png_chunk(ty, data):
return be32(len(data)) + ty + data + be32(crc(ty + data))

The IHDR chunk, always the first chunk in a file, contains basic header information such as width and height. We will hardcode a color depth of 8 bits, color type 2 (RGB truecolor), and standard 0 values for the other fields.

def png_header(width, height):
return png_chunk('IHDR',
struct.pack('>IIBBBBB', width, height, 8, 2, 0, 0, 0))

The actual image data is stored in DEFLATE format, the same compression used by gzip and friends. Fortunately for our minimalist project, DEFLATE allows uncompressed blocks. Each one has a 5-byte header: the byte 0 (or 1 for the last block), followed by a 16-bit data length, and then the same length value with all of the bits flipped. Note that these are little-endian numbers, unlike the rest of PNG. Never assume a format is internally consistent!

MAX_DEFLATE = 0xffff
def deflate_block(data, last=False):
n = len(data)
assert n <= MAX_DEFLATE
return struct.pack('<BHH', bool(last), n, 0xffff ^ n) + data

Since a DEFLATE block can only hold 64 kB, we'll need to split our image data into multiple blocks. We will actually want a more general function to split a sequence into chunks of size n (allowing the last chunk to be smaller than n).

def pieces(seq, n):
return [seq[i:i+n] for i in xrange(0, len(seq), n)]

PNG wants the DEFLATE blocks to be encapsulated as a zlib data stream. For our purposes, this means we prefix a header of 78 01 hex, and suffix an Adler-32 checksum of the "decompressed" data. That's right, a self-contained PNG encoder needs to implement two different checksum algorithms.

def zlib_stream(data):
segments = pieces(data, MAX_DEFLATE)

blocks = ''.join(deflate_block(p) for p in segments[:-1])
blocks += deflate_block(segments[-1], last=True)

return '\x78\x01' + blocks + be32(adler32(data))

We're almost done, but there's one more wrinkle. PNG has a pre-compression filter step, which transforms a scanline of data at a time. A filter doesn't change the size of the image data, but is supposed to expose redundancies, leading to better compression. We aren't compressing anyway, so we choose the no-op filter. This means we prefix a zero byte to each scanline.

At last we can build the PNG file. It consists of the magic PNG signature, a header chunk, our zlib stream inside an IDAT chunk, and an empty IEND chunk to mark the end of the file.

def to_png(width, height, data):
lines = ''.join('\0'+p for p in pieces(data, 3*width))

return ('\x89PNG\r\n\x1a\n'
+ png_header(width, height)
+ png_chunk('IDAT', zlib_stream(lines))
+ png_chunk('IEND', ''))

Actually, a PNG file may contain any number of IDAT chunks. The zlib stream is given by the concatenation of their contents. It might be convenient to emit one IDAT chunk per DEFLATE block. But the IDAT boundaries really can occur anywhere, even halfway through the zlib checksum. This flexibility is convenient for encoders, and a hassle for decoders. For example, one of many historical PNG bugs in Internet Explorer is triggered by empty IDAT chunks.

Here are those checksum algorithms we need. My CRC function follows the approach of code fragment 5 from Wikipedia. For better performance you would want to precompute a lookup table, as suggested by the PNG spec.

def crc(data):
c = 0xffffffff
for x in data:
c ^= ord(x)
for k in xrange(8):
v = 0xedb88320 if c & 1 else 0
c = v ^ (c >> 1)
return c ^ 0xffffffff

def adler32(data):
s1, s2 = 1, 0
for x in data:
s1 = (s1 + ord(x)) % 65521
s2 = (s2 + s1) % 65521
return (s2 << 16) + s1

Now we can test this code. We'll generate a grid of red-green-yellow gradients, and write it in both PPM and PNG formats.

w, h = 500, 300
img = ''
for y in xrange(h):
for x in xrange(w):
img += chr(x % 256) + chr(y % 256) + '\0'

open('out.ppm', 'wb').write(to_ppm(w, h, img))
open('out.png', 'wb').write(to_png(w, h, img))

Then we can verify that the two files contain identical image data.

$ pngtopnm out.png | sha1sum - out.ppm
e19c1229221c608b2a45a4488f9959403b8630a0  -
e19c1229221c608b2a45a4488f9959403b8630a0  out.ppm

That's it! As usual, the code is on GitHub. You can also read what others have written on similar subjects here, here, here, or here.

40 comments:

  1. Out of curiosity, why do you set the block size to 3*width? On the line:

    lines = ''.join('\0'+p for p in pieces(data, 3*width))

    ReplyDelete
  2. Ah, 3 bytes per pixel, and width pixels per line.

    Is it a requirement that each DEFLATE block contain a horizontal line of pixels? Or could you stuff all the pixels (% 64000) into a single DEFLATE block?

    ReplyDelete

  3. Thank you for sharing in this article
    I can learn a lot and could also be a reference
    I am happy to find your website and can join to comment

    Share and Klick Info Blokwalking. Hammer Of Thor
    => Jual Hammer Of Thor Di Bogor
    => Jual Hammer Of Thor Di Medan
    => Jual Hammer Of Thor Di Semarang
    => Jual Hammer Of Thor Di Bandung
    => Jual Hammer Of Thor Di Bandar Lampung
    Obat Good Man | Obat pembesar penis | Vimax Asli | Vimax Extender


    ReplyDelete
  4. Tiap jalma bisa mibanda(học toán cho trẻ mẫu giáo) alesan béda pikeun(toán cho trẻ 5-6 tuổi) hirup kahirupan maranéhanana sorangan.(toán cho bé 5 tuổi) Anjeun teu bisa conflate kabeh alesan ieu sami.

    ReplyDelete
  5. The content is tasteful, your authored subject matter stylish. Thank you for sharing! www.caramembuatwebsiteku.com

    ReplyDelete
  6. This comment has been removed by the author.

    ReplyDelete
  7. This is a topic that's close to my heart... Best wishes! Exactly where are your contact details though?
    donald trump net worth
    michael phelps net worth
    warren buffett net worth
    obama net worth

    ReplyDelete
  8. افضل شركات الشحن البرى والبحرى ونقل العفش داخل جميع مدن المملكة
    نقل عفش من جدة الى الاردن
    شركة نقل عفش من جدة الى الاردن
    شركات نقل العفش من جدة للاردن
    اجراءات نقل العفش للاردن
    شحن من جدة الى عمان
    شركات النقل البرى من جدة الى الاردن
    شحن اثاث من السعودية الى الاردن
    اجراءات نقل الاثاث من السعودية الى الاردن
    شحن من جده للاردن
    اسعار شحن الاثاث من السعودية الى الاردن
    نقل عفش من السعودية الى الاردن
    شركة شحن من السعودية الى الاردن
    نقل عفش من جدة الى الامارات
    شركة نقل عفش من جدة الى الامارات
    شركات نقل العفش من جدة للامارات
    اجراءات نقل العفش للامارات
    شحن من جدة الى دبى
    شركات النقل البرى من جدة الى الامارات
    شحن اثاث من السعودية الى الامارات
    شحن من جده للامارات
    اسعار شحن الاثاث من السعودية الى الامارات
    نقل عفش من السعودية الى الامارات
    شركة شحن من السعودية الى الامارات
    نقل عفش من الرياض الى الامارات
    شركة نقل عفش من الرياض الى الامارات
    شركات نقل العفش من الرياض للامارات
    اجراءات نقل العفش للامارات
    شحن من الرياض الى دبى

    ReplyDelete
  9. مكتب الشيماء للشحن يسعده تقديم خدمات الشحن البرى من السعودية الى مصر
    يمكنكم الضغط على الروابط التالية لمعرفة المزيد :
    نقل عفش من السعودية الى مصر
    شركة شحن عفش من السعودية لمصر
    نقل عفش من الرياض الى مصر
    شحن من السعودية الى مصر
    شحن من الرياض الى مصر
    مكتب شحن من السعودية لمصر
    دليل شركات الشحن من السعودية الى مصر
    اسعار الشحن من الرياض الى القاهره
    شركات شحن فى الرياض
    شركة شحن من السعودية لمصر
    اسعار شحن الاجهزة الكهربائية لمصر
    اسعار شحن الشاشات من السعودية لمصر
    اسعار الشحن من السعودية الى مصر dhl
    اسعار شحن الاثاث من السعودية الى مصر
    شركات الشحن من السعودية الى مصر
    الشيماء للشحن الى مصر
    شركة الشيماء للشحن البرى لمصر


    نقل عفش من السعودية الى مصر
    شركة شحن عفش من السعودية لمصر
    نقل عفش من الرياض الى مصر
    شحن من السعودية الى مصر
    شحن من الرياض الى مصر
    مكتب شحن من السعودية لمصر
    دليل شركات الشحن من السعودية الى مصر
    اسعار الشحن من الرياض الى القاهره
    شركات شحن فى الرياض
    شركة شحن من السعودية لمصر
    اسعار شحن الاجهزة الكهربائية لمصر

    ReplyDelete

  10. يسعدنا تقديم كافة خدمات نقل العفش والشحن الدولى الى من السعودية الى الاردن من السعودية الى الامارات شحن من جدة للاردن تنظيف منازل وخزانات ورش مبيدات ومكافحة حشرات شحن دولى من الرياض للامارات
    اضغط على الخدمة لتصل الى موقعنا
    نقل عفش من جدة الى الاردن
    شركة نقل عفش من جدة الى الاردن
    شحن الاثاث من جدة الى الاردن
    شركات نقل العفش من جدة للاردن
    اجراءات نقل العفش للاردن
    شحن من جدة الى عمان
    شركات النقل البرى من جدة الى الاردن
    شحن اثاث من السعودية الى الاردن
    اجراءات نقل الاثاث من السعودية الى الاردن
    شحن من جده للاردن
    اسعار شحن الاثاث من السعودية الى الاردن
    رش مبيدات ومكافحة حشرات بجدة
    شركة تنظيف خزانات بجدة
    شركة تنظيف منازل بجدة

    ==========================

    نقل عفش من الرياض الى الامارات
    شركة نقل عفش من الرياض الى الامارات
    شحن الاثاث من الرياض الى الامارات
    شركات نقل العفش من الرياض للامارات
    شركة شحن عفش من الرياض الي الامارات
    شحن من الرياض الى دبى
    شركة نقل عفش من الرياض الى دبي
    شحن اثاث من السعودية الى الامارات
    شركة شحن عفش من الرياض الى الامارات
    شركة شحن من الرياض الى الامارات
    شحن من الرياض للامارات
    افضل شركات نقل الاثاث الى الامارات
    نقل عفش من السعودية الى الامارات
    شركة شحن من السعودية الى الامارات

    ReplyDelete
  11. شركة السيف
    نقل عفش وتخزين اثاث وصيانة منزلية ونظافة داخل مدن السعودية وخارجها شحن دولى من السعودية الى الاردن الإمارات الكويت البحرين لبنان جده مكه الطائف الرياض الدمام

    نقل عفش من جد الى الاردن
    شركة نقل عفش من جدة الى الاردن
    نقل عفش من جدة الى الامارات
    شركة نقل عفش من جدة الى الامارات
    شركات نقل العفش من جدة للاردن
    اجراءات نقل العفش للاردن
    شحن من جدة الى عمان
    شركات النقل البرى من جدة الى الاردن
    شحن من جده للاردن
    شركة شحن من السعودية الى الاردن
    شركة شحن عفش من جدة الى الاردن
    نقل عفش من الرياض الى الامارات
    شركة نقل عفش من الرياض الى الامارات
    نقل عفش جدة
    افضل شركات نقل العفش بجدة
    ارخص شركات نقل العفش بجدة
    شركة نقل عفش جده ومكة
    نقل عفش جدة
    افضل شركات نقل العفش بجدة
    ارخص شركات نقل العفش بجدة
    نقل عفش مكة
    افضل شركات نقل العفش بمكه
    ارخص شركات نقل العفش بمكه
    نقل عفش جدة الحمدانية
    نقل عفش جدة السامر
    نقل عفش جدة ابحر الشمالية
    نقل عفش جدة ابحر الجنوبية
    ونيت نقل عفش بجدة
    دباب نقل عفش بجدة
    دينا نقل عفش بجده
    نقل عفش

    ReplyDelete

  12. اذا كنت تود الانتقال بصورة كاملة من السعودية للامارات فمن البديهى انك قد تحتاج الى شركة نقل عفش من جدة الى الامارات وهنا من داخل موقع مؤسسة الاحمدى الذى صممناه خصيصا لتقديم كافة خدمات الشحن الدولية

    نقل عفش من جدة الى الامارات - شركة نقل عفش من جدة الى الامارات - شحن الاثاث من جدة الى الامارات - شركات نقل العفش من جدة للامارات - شركات شحن من جدة للامارات - شحن من جدة الى دبى - شركات النقل البرى من جدة الى الامارات - شحن اثاث من السعودية الى الامارات - شحن من جده للامارات - اسعار شحن الاثاث من السعودية الى الامارات - افضل شركات نقل الاثاث الى الامارات - نقل عفش من السعودية الى الامارات - شركة شحن من السعودية الى الامارات - شركة شحن من جدة الى دبى - نقل عفش من الرياض الى الامارات - شركة نقل عفش من الرياض الى الامارات - شحن الاثاث من الرياض الى الامارات - شركات نقل العفش من الرياض للامارات - شركات شحن العفش من الرياض للامارات - شحن من الرياض الى دبى - شركات النقل البرى من الرياض الى الامارات - شحن اثاث من السعودية الى الامارات - افضل شركة تنظيف بالباحه - شركة تنظيف خزانات بالباحه

    ReplyDelete
  13. How to Fix Error Code 22 ? Mistake Code - 22 is shoiwing gadget is crippled blunder in Windows Server machine then this article may assist you with fixing this mistake.

    ReplyDelete

  14. BSER will announce Rajasthan Board 8th Result 2021 in the first week of June2021. More than 11 lakh students will be waiting for the 8th board. RBSE 8th Board Result 2021 Only students who appear for March 2021 will be able to access rajresults.nic.in 2021 Class 8 result.

    ReplyDelete
  15. Unique Information. I appreciate your efforts and your ideas. Keep sharing again.
    AOL Desktop Gold has a wide range of features with advanced technology inside. But sometimes, you may face AOL Desktop Gold Update Error. This is caused by an outdated web browser on your computer. To fix this error, you can contact our Quick Aid support team, we guarantee that our Quick Aid support team will be ready to assist you in whatever way possible.

    ReplyDelete
  16. One of useful information. Thanks for sharing with us. Keep sharing again.
    With professional electricians, Todd Peters Electric as a Redlands Electrician service provider has come to your doorstep with extreme electrical solutions. If you would like to hire an electrician, simply dial our toll-free number or visit our website.

    ReplyDelete