Paeth-transform arrays One of the key parts of PNG's compression algorithm is the Paeth transformation, which transforms the image in a way that makes it compress better (usually). In this challenge, your task is to write a program to compute a Paeth transformation. The operation of a Paeth transformation is described below.

The Paeth Transformation

The Paeth transformation subtracts from each member X of a 2-dimensional array a predictor. The predictor is that element of the array member to the left (A), top (B), and top-left (C) of X whose value has the least difference to A + B - C.

┼─┼─┼
│C│B│
┼─┼─┼
│A│X│
┼─┼─┼


If one of A, B, or C, would be out of bounds, its value is replaced by 0. Here is pseudocode from the PNG specification outlining how this predictor is computed:

function PaethPredictor (a, b, c)
begin
     ; a = left, b = above, c = upper left
     p := a + b - c        ; initial estimate
     pa := abs(p - a)      ; distances to a, b, c
     pb := abs(p - b)
     pc := abs(p - c)
     ; return nearest of a,b,c,
     ; breaking ties in order a,b,c.
     if pa &lt;= pb AND pa &lt;= pc then return a
     else if pb &lt;= pc then return b
     else return c
end


For this challenge, the array members are natural numbers in the range from 0 to 255. If the Paeth transformation results in a value outside of that range, it shall be reduced modulo 256 to a value in that range.

Input and Output

The input is two integers x and y in the range from 2 to 1023 denoting width and height of the matrix to transform and an array of x × y elements. The input is formatted as decimal numbers separated by one blank character terminated with a linefeed. Here is what this input could look like:

2 3 4 5 6 7 8 9


This would represent a 2 by 3 matrix with the entries:

4 5
6 7
8 9


The output shall have the same format as the input with the relaxiation that the numbers may be separated by an arbitrary non-zero amount of whitespace characters (space, horizontal or vertical tab, line or form feed) and be terminated by an arbitrary amount of whitespace characters.

Input shall be received from stdin, output shall go to stdout. If this is not possible, choose a different way of receiving input and writing output that is not hard-coding the input.

The behaviour of your program when presented with invalid input is not part of this challenge.

Judging and Reference Implementation

An ANSI C program is provided to generate sample input, solve instances and verify solutions. Call the program with g to generate input, with s to solve an input instance and with v to verify the correctness of a solution.

If you think the reference implementation is faulty, please let me know so I can correct it as soon as possible.

Example input and output

By popular request.

10 5 166 156 108 96 63 227 122 99 117 135 125 46 169 247 116 55 151 1 232 114 214 254 6 127 217 88 206 102 252 237 75 250 202 145 86 198 172 84 68 114 58 228 66 224 186 217 210 108 11 179


representing the array

166 156 108  96  63 227 122  99 117 135
125  46 169 247 116  55 151   1 232 114
214 254   6 127 217  88 206 102 252 237
 75 250 202 145  86 198 172  84  68 114
 58 228  66 224 186 217 210 108  11 179


is transformed into

166 246 208 244 223 164 151 233  18  18
215 177 123  78 125  84  96 135 231 138
 89 129   8 121 101 228  55 101  20 123
117 175 196 199 125 112 222 238  72  46
239 234 120 158  41  19  12  24 183 111


which is encoded as

10 5 166 246 208 244 223 164 151 233 18 18 215 177 123 78 125 84 96 135 231 138 89 129 8 121 101 228 55 101 20 123 117 175 196 199 125 112 222 238 72 46 239 234 120 158 41 19 12 24 183 111


Winning Condition

For this challenge, write a program that generates correct Paeth transformation of the input and writes them out. This is code-golf, the program with the least amount of characters in its source code wins. Please try to attach an explanation and a readable version of your code to your submission so others can see what it does.
J - 77 char

Taking an approach that looks different from FUZxxl's answer but is actually very similar.

1!:2&amp;4":2({.,|.@{.,@(256|$-0(0{[/:+`-/|@-])"1@|:(-#:1 2 3)|.!.0$)}.)0".1!:1]3


Some comments on the interesting bits.


1!:2&amp;4": (...) 0".1!:1]3 - If J wasn't terrible about I/O and parsing, this could be refactored as to use &amp;.".&amp;.stdin'', to save 3 chars. But it is so we can't. Rest in peace, precious characters.
2 ({.,|.@{.,@( ... stuff using $ ... )}.) - This disassembles the input and reassembles the output. We use $ both as a reference to the input in stuff using $, and as an operation we need to perform on the input before running the stuff on it.
0( blah )"1@|: - Yes, that's a dyadic Transpose: we regroup the three rotation results as the innermost array axis, so that the Paeth logic can apply on each set separately with "1.
0{[/:+`-/|@-] - The Paeth logic: sort a,b,c by the magnitudes of (p minus each of a,b,c), and take the first.