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.

110 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. يسعدنا تقديم كافة خدمات نقل العفش والشحن الدولى الى من السعودية الى الاردن من السعودية الى الامارات شحن من جدة للاردن تنظيف منازل وخزانات ورش مبيدات ومكافحة حشرات شحن دولى من الرياض للامارات
    اضغط على الخدمة لتصل الى موقعنا
    نقل عفش من جدة الى الاردن
    شركة نقل عفش من جدة الى الاردن
    شحن الاثاث من جدة الى الاردن
    شركات نقل العفش من جدة للاردن
    اجراءات نقل العفش للاردن
    شحن من جدة الى عمان
    شركات النقل البرى من جدة الى الاردن
    شحن اثاث من السعودية الى الاردن
    اجراءات نقل الاثاث من السعودية الى الاردن
    شحن من جده للاردن
    اسعار شحن الاثاث من السعودية الى الاردن
    رش مبيدات ومكافحة حشرات بجدة
    شركة تنظيف خزانات بجدة
    شركة تنظيف منازل بجدة

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

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

    ReplyDelete

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

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

    ReplyDelete
  11. 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
  12. 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
  13. 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
  14. 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
  15. Completely awesome posting! Bunches of helpful data and motivation, both of which we all need!Relay welcome your work 스포츠토토

    ReplyDelete
  16. 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
  17. GREAT JOB! This blog presents a very valuable information. Keep up the good work! Visit our website too. 바카라사이트 Thanks!

    ReplyDelete
  18. 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
  19. 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
  20. 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
  21. 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
  22. I was able to find good info from your blog articles. 사설토토

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

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

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

    ReplyDelete
  26. Great content, thanks for sharing.

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

    ReplyDelete
  28. 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
  29. Great delivery. Outstanding arguments. Keep up the good work. 바둑이사이트넷

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

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

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

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

    ReplyDelete
  34. I enjoy it. I come back again. This blog is a really useful blog. 먹튀폴리스

    ReplyDelete
  35. Hi, you look like you' I want to join you. I hope we can do it together next time.

    ReplyDelete
  36. Your story touched me a lot. Looking forward to more updates. 해외사이트

    ReplyDelete
  37. This blog is very useful to me. I can see new problems in your article. 토토사이트

    ReplyDelete
  38. You also know how to make people rally behind it, obviously from the responses.

    ReplyDelete
  39. I’d have to check with you here. Which is not something I usually do!

    ReplyDelete
  40. Your style is very unique. Appreciate you for posting Valuable tips

    ReplyDelete
  41. Wow, happy to see this awesome post. Thanks for sharing a great information

    ReplyDelete
  42. Great post! We will be linking to this great post on our website. Keep up the great writing.

    ReplyDelete
  43. Nice post. I learn something totally new and challenging on blogs, Its great.

    ReplyDelete
  44. I must say that this is a great post.

    ReplyDelete
  45. Really I am impressed from this post.

    ReplyDelete
  46. I am happy to find this post very useful for me, as it contains lot of information.

    ReplyDelete

  47. I am thankful for the article post. Looking forward to visit more.

    ReplyDelete
  48. Thank for information, I am extremely impressed you write style.

    ReplyDelete

  49. I want to to thank you for this good read!! I definitely enjoyed every little bit of it.

    ReplyDelete
  50. Thanks for sharing this piece of information. I really enjoyed it. keep up the good work.

    ReplyDelete
  51. "I would like to thanks' for the efforts you have put in writing this blog.

    ReplyDelete
  52. this is the best way to share the great article with everyone one, so that everyone can able to utilize this information

    ReplyDelete
  53. I was impressed by your writing. Your writing is impressive. I want to write like you

    ReplyDelete
  54. Big thumbs up for making such wonderful blog page!

    ReplyDelete
  55. I have learned lot of things from it regarding blogging. thanks.

    ReplyDelete
  56. I’m really glad I have found this information.

    ReplyDelete
  57. Thanks for keeping this web site, I’ll be visiting it.

    ReplyDelete
  58. I enjoyed reading the entire post. This article post is fantastic. Thank you so much for the article. Cool.

    ReplyDelete
  59. I enjoyed this just as much as what you did right here. Thanks a lot, Really Cool.

    ReplyDelete
  60. WOW, this is just what I needed. I arrived here after looking for cheap quest bars.

    ReplyDelete
  61. You must use these strategies on your own site if you want to get the most out of this article.

    ReplyDelete

  62. Ahaa, its nice discussion about this paragraph at this place at this blog, I have read all that, so now me also commenting here.

    ReplyDelete

  63. A big thank you for your blog.Really looking forward to read more. Want more

    ReplyDelete

  64. Your blog got me to learn a lot, thanks for sharing, nice article

    ReplyDelete


  65. Perfect just what I was looking for!

    ReplyDelete
  66. "Thanks for share amazing content. Very interesting keep posting.

    ReplyDelete
  67. "Much thanks to you for setting aside an ideal opportunity to distribute this data extremely valuable!
    "

    ReplyDelete

  68. This is so much hilarious blog, Anyways thanks for posting ideas.

    ReplyDelete

  69. I truly like your way of blogging. I bookmarked it to my bookmark website list.

    ReplyDelete

  70. please share i understand this is off subject but I just had to ask.

    ReplyDelete

  71. Everything is quite open and very clear reason of troubles

    ReplyDelete

  72. We are really grateful for your blog post for giving a lot of information

    ReplyDelete
  73. Hi my friend! I wish to say that this article is awesome, great written and come with almost all important infos. I would like to peer extra posts like this .

    ReplyDelete
  74. I love the efforts you have put in this, thanks for all the great blog posts. You should take part in a contest for probably the greatest blogs on the web. I will suggest this web site!

    ReplyDelete
  75. great job, dude You've written a fantastic piece that will be very helpful to readers. Please keep doing more for people in need.

    ReplyDelete
  76. Your contribution to our knowledge is invaluable, and I appreciate you sharing it with us.

    ReplyDelete
  77. something that is remarkable and should be learned. Thank you for providing this great information

    ReplyDelete
  78. I must say you have written a great article.

    ReplyDelete
  79. Its an amazing website, I really enjoy reading your articles.

    ReplyDelete
  80. Such an amazing and helpful post. I really really love it.

    ReplyDelete
  81. Extremely decent blog and articles.

    ReplyDelete
  82. Much obliged to you and sitting tight for your new post

    ReplyDelete
  83. It’s really a great and helpful piece of information.

    ReplyDelete