<?php

/*
    Benchmark for http://www.tophatstuff.co.uk/?p=119

    Using a Paeth pre-compression filter as described by
    http://www.gnupdf.org/PNG_and_TIFF_Predictors_Filter#Filter_type_4:_Paeth
    http://www.w3.org/TR/PNG-Filters.html


  Test with:

  ./locality.php
  ./locality.php?XFIRST

*/



    define("WIDTH", 512);
    define("ITERATIONS", 3);



    function PaethPredictor($a, $b, $c)
    {

        // These apply to bytes.

        // 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) && ($pa <= $pc)) { return $a; }
        else if ($pb <= $pc) { return $b; }
        else { return $c; }
    }


    function TestOutput($data, $w, $h)
    {

        if (WIDTH < 8)
        {
            die("WIDTH must be at least 8");
        }

        printf("TestOutput:\n");

        for ($y = 0; $y < 8; $y++)
        {
            for ($x = 0; $x < 8; $x++)
            {
                $i = ($y * $w) + $x;

                echo str_pad($data[$i], 3, " ", STR_PAD_LEFT);
            }
            echo("<br />\n");
        }

        echo("<br /><br />\n\n");
    }



    function main()
    {


        /* --- SETUP --- */

        $w = $h = WIDTH;
        $size  = $w * $h;

        $orig = array();
        $orig = array_pad($orig, $size, 0);

        $filter = array();
        $filter = array_pad($filter, $size, 0);

        if (count($orig) != $size) { die("err orig is ".count($orig).
            " (want $size)"); }
        if (count($filter) != $size) { die("err filter"); }


        /* fill with numbers typical of an image */
        for ($i = 0; $i < $size; $i++)
        {
            $seq_length = rand() % 80;
            $seq_randomness = 1 + (rand() % 10);
            $seq_base = rand() % 10;

            for ($j = $i; ($j < $size) && ($j < ($i + $seq_length)); $j++)
            {
                $orig[$j] = $seq_base + (rand() % $seq_randomness);
            }
            $i = $j;
        }

        echo "Original:<br />\n";
        TestOutput($orig, $w, $h);


        /* --- MAIN --- */
        $start = MicroTime(TRUE);

        /* --- Precompression filter (this is what we are timing) --- */

        for ($i = 0; $i < ITERATIONS; $i++)
        {

            /* fill x=0 and y=0 rows */
            for ($y = 0; $y < $h; $y++)
            {
                $index = $y * $w;
                $filter[$index] = $orig[$index];
            }
            for ($x = 0; $x < $w; $x++)
            {
                $filter[$x] = $orig[$x];
            }

            /* start from 1,1 */
            if (isset($_GET['XFIRST']))
            {
                for ($x = 1; $x < $w; $x++)
                {
                    for ($y = 1; $y < $h; $y++)
                    {
                        // a = left, b = above, c = upper left
                        $index = ($y * $w) + $x;
                        $a = $index - 1;
                        $b = (($y-1) * $w) + $x;
                        $c = $b - 1;

                        $filter[$index] = $orig[$index] -
                            PaethPredictor($orig[$a], $filter[$b], $filter[$c]);
                    }
                }

            }
            else
            {
                for ($y = 1; $y < $h; $y++)
                {
                    for ($x = 1; $x < $w; $x++)
                    {
                        // a = left, b = above, c = upper left
                        $index = ($y * $w) + $x;
                        $a = $index - 1;
                        $b = (($y-1) * $w) + $x;
                        $c = $b - 1;

                        $filter[$index] = $orig[$index] -
                            PaethPredictor($orig[$a], $filter[$b], $filter[$c]);
                    }
                }
            }

        }

        $end = MicroTime(TRUE);

        echo "Filtered:<br />\n";
        TestOutput($filter, $w, $h);


        /* --- Verify by undoing the filter --- */

        for ($i = 0; $i < ITERATIONS; $i++)
        {

            /* start from 1,1 */
            for ($y = 1; $y < $h; $y++)
            {
                for ($x = 1; $x < $w; $x++)
                {
                    // a = left, b = above, c = upper left
                    $index = ($y * $w) + $x;
                    $a = $index - 1;
                    $b = (($y-1) * $w) + $x;
                    $c = $b - 1;

                    $orig[$index] = $filter[$index] +
                        PaethPredictor($orig[$a], $filter[$b], $filter[$c]);
                }
            }

        }

        echo "Unfilted: This should be back to the original!<br />\n";
        TestOutput($orig, $w, $h);



            echo("w=".$w.", wxh=".($w*$h).", ".($end-$start)." secs<br />\n");

            if (isset($_GET['XFIRST']))
            {
            echo "This should be the slow version! XFIRST is defined\n";
            }

        return 0;
    }

    main();


?>