The Tor Browser: js/src/parjs-benchmarks/liquid-resize.js@129ffea94266 (annotated)

js/src/parjs-benchmarks/liquid-resize.js@129ffea94266 (annotated)

js/src/parjs-benchmarks/liquid-resize.js

Sat, 03 Jan 2015 20:18:00 +0100

author: Michael Schloh von Bennewitz <michael@schloh.com>
date: Sat, 03 Jan 2015 20:18:00 +0100
branch: TOR_BUG_3246
changeset 7: 129ffea94266
permissions: -rw-r--r--

Conditionally enable double key logic according to:
private browsing mode or privacy.thirdparty.isolate preference and
implement in GetCookieStringCommon and FindCookie where it counts...
With some reservations of how to convince FindCookie users to test
condition and pass a nullptr when disabling double key logic.

 // -*- mode: js2; indent-tabs-mode: nil; -*-
 // Adapted from
 //
 // https://github.com/RiverTrail/RiverTrail/blob/master/examples/liquid-resize/resize-compute-dp.js
 //
 // which in turn is based on an algorithm from the paper below (which
 // also appeared in ACM SIGGRAPH 2007):
 // Shai Avidan and Ariel Shamir. 2007. Seam carving for content-aware image resizing.
 // ACM Trans. Graph. 26, 3, Article 10 (July 2007).
 // DOI=10.1145/1276377.1276390 http://doi.acm.org/10.1145/1276377.1276390
 ///////////////////////////////////////////////////////////////////////////
 // Inputs
 function buildArray(width, height, func) {
   var length = width * height;
   var array = new Array(length);
   var index = 0;
   for (var y = 0; y < height; y++) {
     for (var x = 0; x < width; x++) {
       array[index++] = func(y, x);
     }
   }
   return array;
 }
 function parImage(seqImage, width, height) {
   return new ParallelArray([height, width], function (y, x) {
     return seqImage[y*width + x];
   });
 }
 var tinyImage =
   buildArray(20, 5, function(y, x) {
     var ret;
     if (6 <= x && x < 8 && 0 <= y && y < 4)
       ret = ".";
     else if ((x-15)*(x-15)+(y-1)*(y-1) < 2)
       ret = "^";
     else if ((x-20)*(x-20)+(y-3)*(y-3) < 2)
       ret = "%";
     else if ((x-1)*(x-1)+(y-3)*(y-3) < 2)
       ret = "@";
     else
       ret = " ";
     return ret.charCodeAt(0) - 32;
   });
 var SmallImageWidth = 60;
 var SmallImageHeight = 15;
 var SmallImage =
   buildArray(SmallImageWidth, SmallImageHeight, function(y, x) {
     var ret;
     if (6 <= x && x < 8 && 0 <= y && y < 7)
       ret = ".";
     else if ((x-15)*(x-15)+(y-1)*(y-1) < 2)
       ret = "^";
     else if ((x-40)*(x-40)+(y-6)*(y-6) < 6)
       ret = "%";
     else if ((x-1)*(x-1)+(y-12)*(y-12) < 2)
       ret = "@";
     else
       ret = " ";
     return ret.charCodeAt(0) - 32;
   });
 var SmallImagePar = parImage(SmallImage,
                              SmallImageWidth,
                              SmallImageHeight);
 var bigImage =
   buildArray(200, 70, function(y, x) {
     var ret;
     if (4 <= x && x < 7 && 10 <= y && y < 40)
       ret = ".";
     else if ((x-150)*(x-150)+(y-13)*(y-13) < 70)
       ret = "^";
     else if ((x-201)*(x-201)+(y-33)*(y-33) < 200)
       ret = "%";
     else if ((x-15)*(x-15)+(y-3)*(y-3) < 7)
       ret = "@";
     else
       ret = " ";
     return ret.charCodeAt(0) - 32;
   });
 // randomImage: Nat Nat Nat Nat -> RectArray
 function randomImage(w, h, sparsity, variety) {
   return buildArray(w, h, function (x,y) {
     if (Math.random() > 1/sparsity)
       return 0;
     else
       return 1+Math.random()*variety|0;
   });
 }
 // stripedImage: Nat Nat -> RectArray
 function stripedImage(w, h) {
   return buildArray(w, h, function (y, x) {
     return (Math.abs(x%100-y%100) < 10) ? 32 : 0;
   });
 }
 var massiveImage =
   buildArray(70, 10000, function(y, x) (Math.abs(x%100-y%100) < 10) ? 32 : 0);
 function printImage(array, width, height) {
   print("Width", width, "Height", height);
   for (var y = 0; y < height; y++) {
     var line = "";
     for (var x = 0; x < width; x++) {
       var c = array[y*width + x];
       line += String.fromCharCode(c + 32);
     }
     print(line);
   }
 }
 ///////////////////////////////////////////////////////////////////////////
 // Common
 var SobelX = [[-1.0,  0.0,  1.0],
               [-2.0,  0.0,  2.0],
               [-1.0,  0.0,  1.0]];
 var SobelY = [[ 1.0,  2.0,  1.0],
               [ 0.0,  0.0,  0.0],
               [-1.0, -2.0, -1.0]];
 // computeEnergy: Array -> RectArray
 //
 // (The return type is forced upon us, for now at least, until we add
 // appropriate API to ParallelArray; there's a dependency from each
 // row upon its predecessor, but the contents of each row could be
 // computed in parallel.)
 function computeEnergy(source, width, height) {
   var energy = new Array(width * height);
   energy[0] = 0;
   for (var y = 0; y < height; y++) {
     for (var x = 0; x < width; x++) {
       var e = source[y*width + x];
       if (y >= 1) {
         var p = energy[(y-1)*width + x];
         if (x > 0) {
           p = Math.min(p, energy[(y-1)*width + x-1]);
         }
         if (x < (width - 1)) {
           p = Math.min(p, energy[(y-1)*width + x+1]);
         }
         e += p;
       }
       energy[y*width + x] = e;
     }
   }
   return energy;
 }
 // findPath: RectArray -> Array
 // (This is inherently sequential.)
 function findPath(energy, width, height)
 {
   var path = new Array(height);
   var y = height - 1;
   var minPos = 0;
   var minEnergy = energy[y*width + minPos];
   for (var x = 1; x < width; x++) {
     if (energy[y+width + x] < minEnergy) {
       minEnergy = energy[y*width + x];
       minPos = x;
     }
   }
   path[y] = minPos;
   for (y = height - 2; y >= 0; y--) {
     minEnergy = energy[y*width + minPos];
     // var line = energy[y]
     var p = minPos;
     if (p >= 1 && energy[y*width + p-1] < minEnergy) {
       minPos = p-1; minEnergy = energy[y*width + p-1];
     }
     if (p < width - 1 && energy[y*width + p+1] < minEnergy) {
       minPos = p+1; minEnergy = energy[y*width + p+1];
     }
     path[y] = minPos;
   }
   return path;
 }
 ///////////////////////////////////////////////////////////////////////////
 // Sequential
 function transposeSeq(array, width, height) {
   return buildArray(height, width, function(y, x) {
     return array[x*width + y];
   });
 }
 // detectEdgesSeq: Array Nat Nat -> Array
 function detectEdgesSeq(data, width, height) {
   var data1 = new Array(width * height);
   for (var y = 0; y < height; y++) {
     for (var x = 0; x < width; x++) {
       var total = compute(y, x);
       data1[y*width + x] = total | 0;
     }
   }
   return data1;
   function compute(y, x) {
     var totalX = 0;
     var totalY = 0;
     var offYMin = (y == 0 ? 0 : -1);
     var offYMax = (y == height - 1 ? 0 : 1);
     var offXMin = (x == 0 ? 0 : -1);
     var offXMax = (x == width - 1 ? 0 : 1);
     for (var offY = offYMin; offY <= offYMax; offY++) {
       for (var offX = offXMin; offX <= offXMax; offX++) {
         var e = data[(y + offY) * width + x + offX];
         totalX += e * SobelX[offY + 1][offX + 1];
         totalY += e * SobelY[offY + 1][offX + 1];
       }
     }
     return (Math.abs(totalX) + Math.abs(totalY))/8.0 | 0;
   }
 }
 function cutPathHorizontallyBWSeq(array, width, height, path) {
   return buildArray(width-1, height, function (y, x) {
     if (x < path[y]-1)
       return array[y*width + x];
     if (x == path[y]-1)
       return (array[y*width + x] + array[y*width + x+1]) / 2 | 0;
     else
       return array[y*width + x+1];
   });
 }
 function cutPathVerticallyBWSeq(array, width, height, path) {
   return buildArray(width, height-1, function (y, x) {
     if (y < path[x]-1)
       return array[y*width + x];
     if (y == path[x]-1)
       return (array[y*width + x] + array[(y+1)*width + x]) / 2 | 0;
     else
       return array[(y+1)*width + x];
   });
 }
 function cutHorizontalSeamBWSeq(array, width, height)
 {
   var edges = detectEdgesSeq(array, width, height);
   var energy = computeEnergy(edges, width, height);
   var path = findPath(energy, width, height);
   edges = null; // no longer live
   return cutPathHorizontallyBWSeq(array, width, height, path);
 }
 function cutVerticalSeamBWSeq(array, width, height)
 {
   var arrayT = transposeSeq(array, width, height);
   var edges = detectEdgesSeq(arrayT, height, width);
   var energy = computeEnergy(edges, height, width);
   var path = findPath(energy, height, width);
   edges = null; // no longer live
   return cutPathVerticallyBWSeq(array, width, height, path);
 }
 function reduceImageBWSeq(image,
                           width, height,
                           newWidth, newHeight,
                           intermediateFunc,
                           finalFunc) {
   while (width > newWidth || height > newHeight) {
     intermediateFunc(image, width, height);
     if (width > newWidth) {
       image = cutHorizontalSeamBWSeq(image, width, height);
       width -= 1;
     }
     if (height > newHeight) {
       image = cutVerticalSeamBWSeq(image, width, height);
       height -= 1;
     }
   }
   finalFunc(image, width, height);
   return image;
 }
 ///////////////////////////////////////////////////////////////////////////
 // Parallel
 function transposePar(image) {
   var height = image.shape[0];
   var width = image.shape[1];
   return new ParallelArray([width, height], function (y, x) {
     return image.get(x, y);
   });
 }
 // detectEdgesSeq: Array Nat Nat -> Array
 function detectEdgesPar(image) {
   var height = image.shape[0];
   var width = image.shape[1];
   return new ParallelArray([height, width], function (y, x) {
     var totalX = 0;
     var totalY = 0;
     var offYMin = (y == 0 ? 0 : -1);
     var offYMax = (y == height - 1 ? 0 : 1);
     var offXMin = (x == 0 ? 0 : -1);
     var offXMax = (x == width - 1 ? 0 : 1);
     for (var offY = offYMin; offY <= offYMax; offY++) {
       for (var offX = offXMin; offX <= offXMax; offX++) {
         var e = image.get(y + offY, x + offX);
         totalX += e * SobelX[offY + 1][offX + 1];
         totalY += e * SobelY[offY + 1][offX + 1];
       }
     }
     var result = (Math.abs(totalX) + Math.abs(totalY))/8.0 | 0;
     return result;
   });
 }
 function cutPathHorizontallyBWPar(image, path) {
   var height = image.shape[0];
   var width = image.shape[1];
   return new ParallelArray([height, width-1], function (y, x) {
     if (x < path[y]-1)
       return image.get(y, x);
     if (x == path[y]-1)
       return (image.get(y, x) + image.get(y, x+1)) / 2 | 0;
     else
       return image.get(y, x+1);
   });
 }
 function cutPathVerticallyBWPar(image, path) {
   var height = image.shape[0];
   var width = image.shape[1];
   return new ParallelArray([height-1, width], function (y, x) {
     if (y < path[x]-1)
       return image.get(y, x);
     if (y == path[x]-1)
       return (image.get(y, x) + image.get(y+1, x)) / 2 | 0;
     else
       return image.get(y+1, x);
   });
 }
 function cutHorizontalSeamBWPar(image)
 {
   var height = image.shape[0];
   var width = image.shape[1];
   var edges = detectEdgesPar(image);
   var energy = computeEnergy(edges.buffer, width, height);
   var path = findPath(energy, width, height);
   edges = null; // no longer live
   return cutPathHorizontallyBWPar(image, path);
 }
 function cutVerticalSeamBWPar(image) {
   var height = image.shape[0];
   var width = image.shape[1];
   var imageT = transposePar(image);
   var edges = detectEdgesPar(imageT);
   var energy = computeEnergy(edges.buffer, height, width);
   var path = findPath(energy, height, width);
   edges = null; // no longer live
   return cutPathVerticallyBWPar(image, path);
 }
 function reduceImageBWPar(image,
                           newWidth, newHeight,
                           intermediateFunc,
                           finalFunc) {
   var height = image.shape[0];
   var width = image.shape[1];
   while (width > newWidth || height > newHeight) {
     intermediateFunc(image.buffer, width, height);
     if (width > newWidth) {
       image = cutHorizontalSeamBWPar(image);
       width -= 1;
     }
     if (height > newHeight) {
       image = cutVerticalSeamBWPar(image);
       height -= 1;
     }
   }
   finalFunc(image.buffer, width, height);
   return image.buffer;
 }
 ///////////////////////////////////////////////////////////////////////////
 // Benchmarking via run.sh
 var BenchmarkImageWidth = 512;
 var BenchmarkImageHeight = 256;
 var BenchmarkImage = stripedImage(BenchmarkImageWidth,
                                   BenchmarkImageHeight);
 var BenchmarkImagePar = parImage(BenchmarkImage,
                                  BenchmarkImageWidth,
                                  BenchmarkImageHeight);
 var benchmarking = (typeof(MODE) != "undefined");
 if (benchmarking) {
   load(libdir + "util.js");
   benchmark("LIQUID-RESIZE", 1, DEFAULT_MEASURE,
             function() {
               return reduceImageBWSeq(
                 BenchmarkImage,
                 BenchmarkImageWidth, BenchmarkImageHeight,
                 BenchmarkImageWidth/2, BenchmarkImageHeight/2,
                 function() {},
                 function() {});
             },
             function() {
               return reduceImageBWPar(
                 BenchmarkImagePar,
                 BenchmarkImageWidth/2, BenchmarkImageHeight/2,
                 function() {},
                 function() {});
             });
 }
 ///////////////////////////////////////////////////////////////////////////
 // Running (sanity check)
 if (!benchmarking) {
   var seqData =
     reduceImageBWSeq(SmallImage, SmallImageWidth, SmallImageHeight,
                      SmallImageWidth - 15, SmallImageHeight - 10,
                      function() {},
                      printImage);
   var parData =
     reduceImageBWPar(SmallImagePar,
                      SmallImageWidth - 15, SmallImageHeight - 10,
                      function() {},
                      printImage);
   var failed = false;
   assertEq(seqData.length, parData.length);
   for (var i = 0; i < seqData.length; i++) {
     if (seqData[i] !== parData[i]) {
       print("At index ", i, " sequential has ", seqData[i], " parallel has ", parData[i]);
       failed = true;
     }
   }
   if (failed)
     throw new Error();
 }