Retired: ICDevs.org Bounty #12 - PNG Encoder/Decoder - $14,000

I will first simplify Rust lib image-rs/image-png and separate deflate related part.

Second, test NatLabs/deflate.mo lib according to result from Rust.

Third, handle the easiest case based on Rust implemention.

Then, consider chunk and other things to fit more complicated situation.

1 Like

Hey, I’ve had serious hardware failure the last couple of days but back online now. I’m getting started with chunk parsing and metadata decoding after I get dfx set up on my backup

Could you clarify what you’re looking for in the Rust lib and how it relates to our Motoko implementation?

For our purposes, the library is quite lacking in that it does not implement decoders. Also, keep in mind that Gzip != zlib. Nevertheless, the encoders are great to have for now.

Please take a peek at deflate.mo and let me know if you’ll be able to adapt it for decoding and a later zlib implementation. I’m finished with chunk/config decoding and will get onto palettes and pixels next. If you have any trouble with zlib we can also collaborate on it, since only encoding is missing from deflate and we have nothing for zlib yet.

I’ve implemented much of the spec directly but haven’t had a chance to properly test it yet. I’d like to deploy some testing suite. So far, I’ve written a simple frontend that was supposed to send files over the javascript candid interface, but it doesn’t seem like javascript can serialize to Candid’s vec uint8.
The precise specification of javascript-Candid mappings does not seem to be available right now (or has been moved).
Is there any preferred way to load file data into canisters?

Here’s some examples on how to upload data which can be a png:

From Node.js NFT Minting - Developer Docs.
Motoko - FileUpload

Under 2MB and you won’t have to worry about chunking if that makes things simpler to get working.

To do integration or E2E testing, I would recomend using Vitetest: Testing Your Canister With Vitest. Note you can also set the node compatibility flag for the generated declarations (in dfx.json of each Motoko canister you are testing) to simplify this process if you also set the test project’s package.json field "type": "module". This will make each .js file in the test project an ESM module which will be automatically compatible with what the declarations are generated with (import/export). Configuring Jest to do this is a bit more of a pain. On that note, if work for the bounty is still being split up, I’d be happy to take on setting up unit and/or e2e tests.

I’ve received no response from the others and the Zip bounty is incomplete and will thus proceed to implement a Zlib/DEFLATE decoder. After that’s done, the decoding part of this bounty will be complete. I hope encoding will go equally as well. I’ll post a repo up soon.

I’ve been adapting to motoko quite well up to this point but there are some uncertainties which have affected the implementation that I’d like to work out with you. The most prominent of those is one related
directly to the low-level nature of this task, and is the issue of memory addressing. As has been acknowledged in the documentation, Motoko does not provide direct memory pointers. What’s more, no method exists as either built-in or a standard library function of changing what memory an array refers to.
Although I have managed to disect the png stream with a base readBytes() method of my decoder so far, the task of Zlib decoding has been complicated considerably, so much so that I am unable to continue in the current architecture.
For example, in the function

func decode(b : [Nat8]) {
  ... parse the first two bytes ...
  ... Deflate.decode(..the rest..) ...
}

I would like to be able to copy b,
adjusted to begin 2 positions beyond the original, while being sure that the underlying memory is not copied. In fact, javascript’s slice() function, which does provide such guarantees, is exactly what the jspng library you cited in the body of this bounty uses.

1 Like

The above issue of course stems from the fact that all components of the library, as of now, assume that the entire buffer is available, and many accept byte arrays as arguments. This has been done for simplicity, so as to focus on the specification first, and later adjust the implementation to the task’s requirement of multistep processing. It could, of course, be alievated by defining decode as a method of a Deflate class (rather than module, as in the above example), which would inherit the offset in the input buffer from an enclosed object. That is, a base reader object would be accepted as argument of every function (or object constructor) that wants to access the source buffer, and its readBytes method called. This is in contrast to the current implementation where readBytes is a method of the PNG decoder itself.
Regardless, I am unsure whether that would make up for the lack of pointer arithmetic or any kind of reference adjustment, and hope a sufficient solution for Motoko exists.

The above leads me to the issue of working on incomplete input. Currently, the decode() and decodeConfig() methods of the PNG decoder accept arrays of bytes ([Nat8]. I am aware that Blob is preferred but, for simplicity, I rely on Nats for now). By adopting a scheme similar to that described above, namely of the decode() function accepting a reader object with a readBytes method, the decoder could be made to accept its input incrementally.
The library you cited, Pipelinify, does not seem to be documented. This prevents me from making any decision on the case. What I need of you is a reference to the documentation, if any, or a summary of the aspects involved. That is, I would like to learn how the design of the Pipelinify library was influenced by the structure of IC, and what requirements/special cases would need to be handled for the PNG decoder. As the bases of further discussion, I would like to learn why the approach of accepting a reader object (equivalent to Golang’s io.Reader interface) might be insufficient.

I’ll give a bit of background on pipelinify. Unfortunately, documentation has been on my todo list for over a year and doesn’t look like it will surface any time soon.

I was working with images. I was using the browser to convert pngs to bitmaps and then pushing the entire bitmap into the IC and then processing each pixel to do things like blur, greyscale, and resize. I had to adapt all algos to block-based and I was storing all data in 2MB chunks.

We didn’t really even have heartbeat in motoko at that point I don’t think, so the process had to be run by calling an update call over and over until the process finished. This would be massively simplified with the timers API we have now.

Pipelinify basically lets you 1. Create a workspace, 2. Push data into that workspace in chunks, 3 ask a canister to process that data in a loop until it is done. 5. reports the status 6. deliver the resulting content in chunks.

The key was having data in ready to access workspaces where I could view and manipulate the bits without having to copy massive streams of data. Then I had to adapt the processing functions to operate on those arrays instead of streams.

So, Pipelinify is a tiny protocol for abstracting the pecularities of IO from IC applications. After a second thought, I see that it is basically a CSP concurrency model (isn’t it?). The requests/responses would correspond to send and receive operation on named channels (from the peek I took at the source, I remember that Pipelinify connections have IDs). The encode_result() would then correspond to a channel receive.

The approach I suggested. that of reader objects, is an appropriate one for the inter-component (decompressor<->decoder<->…) input propagation. The top-level (chunk) decoder would share its reader with the compressor that need later be called, ensuring that the position in the byte array is maintained (which was what I worried about earlier, due to the lack of reference modification in Motoko – a modified pointer to the array can’t be passed to the decompressor).

At this stage of development, I believe such scheme would also suffice for the top level decode function.
Input would be consumed by the decoder at the rate that it is produced by a reader, and the complete pixmap returned completely once, as the return result of a single function.

Later, when we have a complete spec compliant implementation, I will adjust the interface to one that yields results in chunks, be it with Pipelinify or a custom solution.

As far as Pipelinify is concerned, I should get familiar with the *Request and *Response types next, which should clear some things out.

For now, the interface of the decoder changes from

decode(b : [Nat8]) : PNG

to

decode(r : Reader) : PNG

where

type Reader = {
  read(n : Nat) : Blob;
};

Still, the lack of any way to adjust what references (arrays in our case) point to is a major obstacle. Surprisingly, even javascript provides a ‘shallow-copy’ slice() operation. I’m not sure of the performance implications of interfaces (through subtyping), in the style of the Readers mentioned above, so any reassurance about the characteristics of the implementation of subtyping in motoko would be welcome.

On another note, I recall that a bounty was also placed at Pipelinify documentation and refinements. As the current bounty is leading me onto Pipelinify, I could, by passage, do some work on that case.
For now, the Regexp bounty, for which I submitted a week ago, is still not closed. I would apprieciate if you could put some attention to it such that we can proceed further.

Awesome bounty. Very useful post and bounty.

I had a meeting with dfinity today and we should be in the next round of payouts. When I get the payment I’ll submit closeout votes to the board at that price and then pay out as they are improved.

Also check your DMs for more pipelinify info.

Everything is looking good at this point and I’ll try to share the repo with you tomorrow. I got started with the Zlib/Deflate decoder today. I have a general interface for pixel data access (with pixel channel descriptors and all) in mind and will lay some stubs for the encoder soon. The repo you shared illustrated how image manipulation in motoko might look like and gave some valueable insight to what your expectations might be, on top of the obvious of illustrating how pipelining might be set up. I’d say we’re a good bit over half-way done, and I have a good general idea of how my current codebase could be adjusted for pipelining.

1 Like

I wanted to get zlib/deflate working properly before I share it with you, but faced some serious obstacles. Overall, I’ve spent the last 4 full working days on the issue and am certain that work can continue smoothly now. I will take a one day break and get it all wired up right after. Then, we’ll finally have acess to raw pixels.

On the topic of deflate issues (zlib was trivial and was working the day of the last message), here are two quotes from the official documentation:

[…] the code length code lengths (really).

[…] code length code lengths (you come up with a better name!)


What can I say. Huffman codes encoded with Huffman codes (themselves encoded with a prefix code, run-length encoded) are real fun.

I have one more issue with Motoko’s type system not liking some things the spec requires but I’m sure it won’t be as bad. I’ll reprot back if I need anything.

Oh my…that sounds annoying. Thanks for the amazing work and pushing through it!