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

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.

     1 // -*- mode: js2; indent-tabs-mode: nil; -*-

     3 // Adapted from

     4 //

     5 // https://github.com/RiverTrail/RiverTrail/blob/master/examples/liquid-resize/resize-compute-dp.js

     6 //

     7 // which in turn is based on an algorithm from the paper below (which

     8 // also appeared in ACM SIGGRAPH 2007):

     9 // Shai Avidan and Ariel Shamir. 2007. Seam carving for content-aware image resizing.

    10 // ACM Trans. Graph. 26, 3, Article 10 (July 2007).

    11 // DOI=10.1145/1276377.1276390 http://doi.acm.org/10.1145/1276377.1276390

    13 ///////////////////////////////////////////////////////////////////////////

    14 // Inputs

    16 function buildArray(width, height, func) {

    17   var length = width * height;

    18   var array = new Array(length);

    19   var index = 0;

    20   for (var y = 0; y < height; y++) {

    21     for (var x = 0; x < width; x++) {

    22       array[index++] = func(y, x);

    23     }

    24   }

    25   return array;

    26 }

    28 function parImage(seqImage, width, height) {

    29   return new ParallelArray([height, width], function (y, x) {

    30     return seqImage[y*width + x];

    31   });

    32 }

    34 var tinyImage =

    35   buildArray(20, 5, function(y, x) {

    36     var ret;

    37     if (6 <= x && x < 8 && 0 <= y && y < 4)

    38       ret = ".";

    39     else if ((x-15)*(x-15)+(y-1)*(y-1) < 2)

    40       ret = "^";

    41     else if ((x-20)*(x-20)+(y-3)*(y-3) < 2)

    42       ret = "%";

    43     else if ((x-1)*(x-1)+(y-3)*(y-3) < 2)

    44       ret = "@";

    45     else

    46       ret = " ";

    47     return ret.charCodeAt(0) - 32;

    48   });

    50 var SmallImageWidth = 60;

    51 var SmallImageHeight = 15;

    52 var SmallImage =

    53   buildArray(SmallImageWidth, SmallImageHeight, function(y, x) {

    54     var ret;

    55     if (6 <= x && x < 8 && 0 <= y && y < 7)

    56       ret = ".";

    57     else if ((x-15)*(x-15)+(y-1)*(y-1) < 2)

    58       ret = "^";

    59     else if ((x-40)*(x-40)+(y-6)*(y-6) < 6)

    60       ret = "%";

    61     else if ((x-1)*(x-1)+(y-12)*(y-12) < 2)

    62       ret = "@";

    63     else

    64       ret = " ";

    65     return ret.charCodeAt(0) - 32;

    66   });

    68 var SmallImagePar = parImage(SmallImage,

    69                              SmallImageWidth,

    70                              SmallImageHeight);

    72 var bigImage =

    73   buildArray(200, 70, function(y, x) {

    74     var ret;

    75     if (4 <= x && x < 7 && 10 <= y && y < 40)

    76       ret = ".";

    77     else if ((x-150)*(x-150)+(y-13)*(y-13) < 70)

    78       ret = "^";

    79     else if ((x-201)*(x-201)+(y-33)*(y-33) < 200)

    80       ret = "%";

    81     else if ((x-15)*(x-15)+(y-3)*(y-3) < 7)

    82       ret = "@";

    83     else

    84       ret = " ";

    85     return ret.charCodeAt(0) - 32;

    86   });

    88 // randomImage: Nat Nat Nat Nat -> RectArray

    89 function randomImage(w, h, sparsity, variety) {

    90   return buildArray(w, h, function (x,y) {

    91     if (Math.random() > 1/sparsity)

    92       return 0;

    93     else

    94       return 1+Math.random()*variety|0;

    95   });

    96 }

    98 // stripedImage: Nat Nat -> RectArray

    99 function stripedImage(w, h) {

   100   return buildArray(w, h, function (y, x) {

   101     return (Math.abs(x%100-y%100) < 10) ? 32 : 0;

   102   });

   103 }

   105 var massiveImage =

   106   buildArray(70, 10000, function(y, x) (Math.abs(x%100-y%100) < 10) ? 32 : 0);

   108 function printImage(array, width, height) {

   109   print("Width", width, "Height", height);

   110   for (var y = 0; y < height; y++) {

   111     var line = "";

   112     for (var x = 0; x < width; x++) {

   113       var c = array[y*width + x];

   114       line += String.fromCharCode(c + 32);

   115     }

   116     print(line);

   117   }

   118 }

   120 ///////////////////////////////////////////////////////////////////////////

   121 // Common

   123 var SobelX = [[-1.0,  0.0,  1.0],

   124               [-2.0,  0.0,  2.0],

   125               [-1.0,  0.0,  1.0]];

   126 var SobelY = [[ 1.0,  2.0,  1.0],

   127               [ 0.0,  0.0,  0.0],

   128               [-1.0, -2.0, -1.0]];

   130 // computeEnergy: Array -> RectArray

   131 //

   132 // (The return type is forced upon us, for now at least, until we add

   133 // appropriate API to ParallelArray; there's a dependency from each

   134 // row upon its predecessor, but the contents of each row could be

   135 // computed in parallel.)

   136 function computeEnergy(source, width, height) {

   137   var energy = new Array(width * height);

   138   energy[0] = 0;

   139   for (var y = 0; y < height; y++) {

   140     for (var x = 0; x < width; x++) {

   141       var e = source[y*width + x];

   142       if (y >= 1) {

   143         var p = energy[(y-1)*width + x];

   144         if (x > 0) {

   145           p = Math.min(p, energy[(y-1)*width + x-1]);

   146         }

   147         if (x < (width - 1)) {

   148           p = Math.min(p, energy[(y-1)*width + x+1]);

   149         }

   150         e += p;

   151       }

   152       energy[y*width + x] = e;

   153     }

   154   }

   155   return energy;

   156 }

   158 // findPath: RectArray -> Array

   159 // (This is inherently sequential.)

   160 function findPath(energy, width, height)

   161 {

   162   var path = new Array(height);

   163   var y = height - 1;

   164   var minPos = 0;

   165   var minEnergy = energy[y*width + minPos];

   167   for (var x = 1; x < width; x++) {

   168     if (energy[y+width + x] < minEnergy) {

   169       minEnergy = energy[y*width + x];

   170       minPos = x;

   171     }

   172   }

   174   path[y] = minPos;

   175   for (y = height - 2; y >= 0; y--) {

   176     minEnergy = energy[y*width + minPos];

   177     // var line = energy[y]

   178     var p = minPos;

   179     if (p >= 1 && energy[y*width + p-1] < minEnergy) {

   180       minPos = p-1; minEnergy = energy[y*width + p-1];

   181     }

   182     if (p < width - 1 && energy[y*width + p+1] < minEnergy) {

   183       minPos = p+1; minEnergy = energy[y*width + p+1];

   184     }

   185     path[y] = minPos;

   186   }

   187   return path;

   188 }

   190 ///////////////////////////////////////////////////////////////////////////

   191 // Sequential

   193 function transposeSeq(array, width, height) {

   194   return buildArray(height, width, function(y, x) {

   195     return array[x*width + y];

   196   });

   197 }

   199 // detectEdgesSeq: Array Nat Nat -> Array

   200 function detectEdgesSeq(data, width, height) {

   201   var data1 = new Array(width * height);

   202   for (var y = 0; y < height; y++) {

   203     for (var x = 0; x < width; x++) {

   204       var total = compute(y, x);

   205       data1[y*width + x] = total | 0;

   206     }

   207   }

   208   return data1;

   210   function compute(y, x) {

   211     var totalX = 0;

   212     var totalY = 0;

   214     var offYMin = (y == 0 ? 0 : -1);

   215     var offYMax = (y == height - 1 ? 0 : 1);

   216     var offXMin = (x == 0 ? 0 : -1);

   217     var offXMax = (x == width - 1 ? 0 : 1);

   219     for (var offY = offYMin; offY <= offYMax; offY++) {

   220       for (var offX = offXMin; offX <= offXMax; offX++) {

   221         var e = data[(y + offY) * width + x + offX];

   222         totalX += e * SobelX[offY + 1][offX + 1];

   223         totalY += e * SobelY[offY + 1][offX + 1];

   224       }

   225     }

   227     return (Math.abs(totalX) + Math.abs(totalY))/8.0 | 0;

   228   }

   229 }

   231 function cutPathHorizontallyBWSeq(array, width, height, path) {

   232   return buildArray(width-1, height, function (y, x) {

   233     if (x < path[y]-1)

   234       return array[y*width + x];

   235     if (x == path[y]-1)

   236       return (array[y*width + x] + array[y*width + x+1]) / 2 | 0;

   237     else

   238       return array[y*width + x+1];

   239   });

   240 }

   242 function cutPathVerticallyBWSeq(array, width, height, path) {

   243   return buildArray(width, height-1, function (y, x) {

   244     if (y < path[x]-1)

   245       return array[y*width + x];

   246     if (y == path[x]-1)

   247       return (array[y*width + x] + array[(y+1)*width + x]) / 2 | 0;

   248     else

   249       return array[(y+1)*width + x];

   250   });

   251 }

   253 function cutHorizontalSeamBWSeq(array, width, height)

   254 {

   255   var edges = detectEdgesSeq(array, width, height);

   256   var energy = computeEnergy(edges, width, height);

   257   var path = findPath(energy, width, height);

   258   edges = null; // no longer live

   259   return cutPathHorizontallyBWSeq(array, width, height, path);

   260 }

   262 function cutVerticalSeamBWSeq(array, width, height)

   263 {

   264   var arrayT = transposeSeq(array, width, height);

   265   var edges = detectEdgesSeq(arrayT, height, width);

   266   var energy = computeEnergy(edges, height, width);

   267   var path = findPath(energy, height, width);

   268   edges = null; // no longer live

   269   return cutPathVerticallyBWSeq(array, width, height, path);

   270 }

   272 function reduceImageBWSeq(image,

   273                           width, height,

   274                           newWidth, newHeight,

   275                           intermediateFunc,

   276                           finalFunc) {

   277   while (width > newWidth || height > newHeight) {

   278     intermediateFunc(image, width, height);

   280     if (width > newWidth) {

   281       image = cutHorizontalSeamBWSeq(image, width, height);

   282       width -= 1;

   283     }

   285     if (height > newHeight) {

   286       image = cutVerticalSeamBWSeq(image, width, height);

   287       height -= 1;

   288     }

   289   }

   291   finalFunc(image, width, height);

   292   return image;

   293 }

   295 ///////////////////////////////////////////////////////////////////////////

   296 // Parallel

   298 function transposePar(image) {

   299   var height = image.shape[0];

   300   var width = image.shape[1];

   301   return new ParallelArray([width, height], function (y, x) {

   302     return image.get(x, y);

   303   });

   304 }

   306 // detectEdgesSeq: Array Nat Nat -> Array

   307 function detectEdgesPar(image) {

   308   var height = image.shape[0];

   309   var width = image.shape[1];

   310   return new ParallelArray([height, width], function (y, x) {

   311     var totalX = 0;

   312     var totalY = 0;

   314     var offYMin = (y == 0 ? 0 : -1);

   315     var offYMax = (y == height - 1 ? 0 : 1);

   316     var offXMin = (x == 0 ? 0 : -1);

   317     var offXMax = (x == width - 1 ? 0 : 1);

   319     for (var offY = offYMin; offY <= offYMax; offY++) {

   320       for (var offX = offXMin; offX <= offXMax; offX++) {

   321         var e = image.get(y + offY, x + offX);

   322         totalX += e * SobelX[offY + 1][offX + 1];

   323         totalY += e * SobelY[offY + 1][offX + 1];

   324       }

   325     }

   327     var result = (Math.abs(totalX) + Math.abs(totalY))/8.0 | 0;

   328     return result;

   329   });

   330 }

   332 function cutPathHorizontallyBWPar(image, path) {

   333   var height = image.shape[0];

   334   var width = image.shape[1];

   335   return new ParallelArray([height, width-1], function (y, x) {

   336     if (x < path[y]-1)

   337       return image.get(y, x);

   338     if (x == path[y]-1)

   339       return (image.get(y, x) + image.get(y, x+1)) / 2 | 0;

   340     else

   341       return image.get(y, x+1);

   342   });

   343 }

   345 function cutPathVerticallyBWPar(image, path) {

   346   var height = image.shape[0];

   347   var width = image.shape[1];

   348   return new ParallelArray([height-1, width], function (y, x) {

   349     if (y < path[x]-1)

   350       return image.get(y, x);

   351     if (y == path[x]-1)

   352       return (image.get(y, x) + image.get(y+1, x)) / 2 | 0;

   353     else

   354       return image.get(y+1, x);

   355   });

   356 }

   358 function cutHorizontalSeamBWPar(image)

   359 {

   360   var height = image.shape[0];

   361   var width = image.shape[1];

   362   var edges = detectEdgesPar(image);

   363   var energy = computeEnergy(edges.buffer, width, height);

   364   var path = findPath(energy, width, height);

   365   edges = null; // no longer live

   366   return cutPathHorizontallyBWPar(image, path);

   367 }

   369 function cutVerticalSeamBWPar(image) {

   370   var height = image.shape[0];

   371   var width = image.shape[1];

   372   var imageT = transposePar(image);

   373   var edges = detectEdgesPar(imageT);

   374   var energy = computeEnergy(edges.buffer, height, width);

   375   var path = findPath(energy, height, width);

   376   edges = null; // no longer live

   377   return cutPathVerticallyBWPar(image, path);

   378 }

   380 function reduceImageBWPar(image,

   381                           newWidth, newHeight,

   382                           intermediateFunc,

   383                           finalFunc) {

   384   var height = image.shape[0];

   385   var width = image.shape[1];

   386   while (width > newWidth || height > newHeight) {

   387     intermediateFunc(image.buffer, width, height);

   389     if (width > newWidth) {

   390       image = cutHorizontalSeamBWPar(image);

   391       width -= 1;

   392     }

   394     if (height > newHeight) {

   395       image = cutVerticalSeamBWPar(image);

   396       height -= 1;

   397     }

   398   }

   400   finalFunc(image.buffer, width, height);

   401   return image.buffer;

   402 }

   404 ///////////////////////////////////////////////////////////////////////////

   405 // Benchmarking via run.sh

   407 var BenchmarkImageWidth = 512;

   408 var BenchmarkImageHeight = 256;

   409 var BenchmarkImage = stripedImage(BenchmarkImageWidth,

   410                                   BenchmarkImageHeight);

   411 var BenchmarkImagePar = parImage(BenchmarkImage,

   412                                  BenchmarkImageWidth,

   413                                  BenchmarkImageHeight);

   415 var benchmarking = (typeof(MODE) != "undefined");

   416 if (benchmarking) {

   417   load(libdir + "util.js");

   418   benchmark("LIQUID-RESIZE", 1, DEFAULT_MEASURE,

   419             function() {

   420               return reduceImageBWSeq(

   421                 BenchmarkImage,

   422                 BenchmarkImageWidth, BenchmarkImageHeight,

   423                 BenchmarkImageWidth/2, BenchmarkImageHeight/2,

   424                 function() {},

   425                 function() {});

   426             },

   428             function() {

   429               return reduceImageBWPar(

   430                 BenchmarkImagePar,

   431                 BenchmarkImageWidth/2, BenchmarkImageHeight/2,

   432                 function() {},

   433                 function() {});

   434             });

   435 }

   437 ///////////////////////////////////////////////////////////////////////////

   438 // Running (sanity check)

   440 if (!benchmarking) {

   441   var seqData =

   442     reduceImageBWSeq(SmallImage, SmallImageWidth, SmallImageHeight,

   443                      SmallImageWidth - 15, SmallImageHeight - 10,

   444                      function() {},

   445                      printImage);

   447   var parData =

   448     reduceImageBWPar(SmallImagePar,

   449                      SmallImageWidth - 15, SmallImageHeight - 10,

   450                      function() {},

   451                      printImage);

   453   var failed = false;

   454   assertEq(seqData.length, parData.length);

   455   for (var i = 0; i < seqData.length; i++) {

   456     if (seqData[i] !== parData[i]) {

   457       print("At index ", i, " sequential has ", seqData[i], " parallel has ", parData[i]);

   458       failed = true;

   459     }

   460   }

   461   if (failed)

   462     throw new Error();

   463 }

The Tor Browser / file revision

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

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