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.

90 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
  17. We are really grateful for your blog post. You will find a lot of approaches after visiting your post. Great work. Feel free to visit my website; 토토사이트

    ReplyDelete
  18. Great blog here! Additionally your website quite a bit up very fast! What web host are you the use of? Can I am getting your affiliate hyperlink on your host? Feel free to visit my website; 카지노사이트

    ReplyDelete
  19. Your style is very unique in comparison to other folks I have read stuff from. I appreciate you for posting when you have the opportunity, Guess I will just bookmark this page. Feel free to visit my website; 카지노사이트

    ReplyDelete
  20. Pretty great post. I just stumbled upon your weblog and wished to say that I have really enjoyed browsing your weblog posts. In any case I’ll be subscribing to your rss feed and I am hoping you write again very soon! Feel free to visit my website; 배트맨토토

    ReplyDelete
  21. Thanks for your post! Through your pen I found the problem up interesting! I believe there are many other people who are interested in them just like me! How long does it take to complete this article? I have read through other blogs, but they are cumbersome and confusing.
    happy wheels 스포츠중계

    ReplyDelete
  22. Completely awesome posting! Bunches of helpful data and motivation, both of which we all need!Relay welcome your work 스포츠토토

    ReplyDelete
  23. Well I truly enjoyed reading it. This subject offered by you is very helpful and accurate.
    카지노사이트

    ReplyDelete
  24. This is really helpful post and very informative there is no doubt about it.
    바카라사이트

    ReplyDelete
  25. Thanks for your post! Through your pen I found the problem up interesting! I believe there are many other people who are interested in them just like me! How long does it take to complete this article? I have read through other blogs, 바카라사이트
    but they are cumbersome and confusing.
    happy wheels

    ReplyDelete
  26. GREAT JOB! This blog presents a very valuable information. Keep up the good work! Visit our website too. 바카라사이트 Thanks!

    ReplyDelete
  27. Very nice article to understand the importance of social media marketing and its advantages for small business like me I will definitely plan social media marketing strategy for my cleaning business and will update regularly.
    토토사이트

    ReplyDelete
  28. Hi there! This is my first visit to your blog! We are a group of volunteers and starting a new project in a community in the same niche. 토토
    Your blog provided us useful information to work on. You have done a extraordinary job!

    ReplyDelete
  29. This is my first visit to your web journal! We are a group of volunteers and new activities in the same specialty. Website gave us helpful data to work. 야한동영상

    Please visit once. I leave my blog address below
    야설
    야한동영상

    ReplyDelete
  30. I like your post. It is good to see you verbalize from the heart and clarity on this important subject can be easily observe 일본야동

    Please visit once. I leave my blog address below
    한국야동
    일본야동

    ReplyDelete
  31. I really happy found this website eventually. Really informative and inoperative, Thanks for the post and effort! Please keep sharing more such blog. 한국야동닷컴

    Please visit once. I leave my blog address below
    국산야동
    한국야동닷컴

    ReplyDelete
  32. Really nice and interesting post. I was looking for this kind of information and enjoyed reading this one. 국산야동

    Please visit once. I leave my blog address below
    야설
    국산야동

    ReplyDelete
  33. Thanks for taking the time to discuss this, I feel strongly about it and love learning more on this topic. If possible, as you gain expertise, would you mind updating your blog with extra information? It is extremely helpful for me. 중국야동넷

    Please visit once. I leave my blog address below
    야설
    중국야동넷

    ReplyDelete
  34. Visit
    www.hp.com/go/wirelessprinting and open the door to the world of HP smart printing solutions.
    Visit ij.start.canon | ij.start canon and find out the best way to download Canon printer drivers.
    Once you are done with the driver setup via
    canon.com/ijsetup , you will have to insert a pile of pages into the printer tray for printing the documents.

    ReplyDelete
  35. I was able to find good info from your blog articles. 사설토토

    ReplyDelete
  36. I have been browsing online greater than three hours today, but I by no means discovered any interesting article like yours. 파워볼게임

    ReplyDelete
  37. As expected, I can only see articles that can grow. I ll let you know around me. 메이저사이트

    ReplyDelete
  38. I think the posts here are good, so I leave a comment. 먹튀검증업체

    ReplyDelete
  39. Thank you so much. Thank you for letting me know this blog. Thank you for your good comments. I wish you prosperity. 메이저사이트

    ReplyDelete
  40. Extremely overall quite fascinating post. I was searching for this sort of data and delighted in perusing this one. 메이저검증업체

    ReplyDelete
  41. Thank you for the information provided! Maintain the good performance of your site. You can also check my article 토토

    ReplyDelete
  42. This is very interesting! Great information and it is also very well written. I will bookmark and comeback soon 안전사이트

    ReplyDelete
  43. Great content, thanks for sharing.

    ReplyDelete
  44. การลงทุนระยาว ใช้เงินเก็บกับการลงทุนที่คุ้มค่า เชิญทางนี้ supremosystems เว็บไซต์ที่ได้รวบรวม สาระน่ารู้เกี่ยวกับการเงิน การบริหารการเงิน จัดการวางแผนการเงิน ธุรกิจอสังหาริมทรัพย์ และการลงทุนต่าง ๆ เเนะนำการออมเงินอย่างถูกวิธี เเละทริคในการเก็บเงินต่างๆที่จะช่วยสร้างการเงินของคุณให้เเข็งเเรง.

    ReplyDelete
  45. I think it's a website with a lot of good contents. I think I accumulate a lot of knowledge.
    Please come to my website and give me a lot of advice.
    It's my website.

    피망머니상

    ReplyDelete
  46. Great delivery. Outstanding arguments. Keep up the good work. 바둑이사이트넷

    ReplyDelete
  47. Either way keep up the excellent quality writing. 바카라사이트윈

    ReplyDelete
  48. ผ่านพ้นวิกฤติเศรษฐกิจที่ย้ำเเย่ได้ง่ายๆ ไปกับ supremosystems เว็บไซต์ของเราได้รวบรวมเอา สาระน่ารู้เกี่ยวกับการเงิน การบริหารการเงิน จัดการวางแผนการเงิน ธุรกิจอสังหาริมทรัพย์ และการลงทุนต่าง ๆ คลิกตรงนี้ ซึ่งจะช่วยให้การเงิน การลงทุนของคุณมีความมั่นคง เเละมีประสิทธิภาพสูง รับรองมีเงินเก็บ เเละใช้ตลอดอย่างเเน่นอน.

    ReplyDelete
  49. While looking for articles on these topics, I came across this article on the site here. As I read your article, I felt like an expert in this field. I have several articles on these topics posted on my site. Could you please visit my homepage? 메이저놀이터순위

    ReplyDelete
  50. Thanks for sharing this amazing article, it is very informative post good work keep it up.
    토토

    ReplyDelete
  51. It’s actually great and useful information. Thank you for sharing this useful information with us.
    온라인경마

    ReplyDelete
  52. Thanks for the information keep sharing such informative post keep suggesting such post.
    슬롯머신

    ReplyDelete
  53. Great post, beautiful weblog with great informational content. This is a really interesting and informative content. 스포츠토토

    ReplyDelete
  54. Thanks for sharing with us this important Content. I feel strongly about it and really enjoyed learning more about this topic. 바카라사이트

    ReplyDelete
  55. Hey, I simply hopped over in your web page by means of StumbleUpon. Not one thing I might in most cases learn, however I favored your feelings none the less. Thank you for making something price reading. 메이저토토사이트

    ReplyDelete