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 <= pb AND pa <= pc then return a
else if pb <= 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.
