The Tor Browser / file comparison

comparison: js/src/parjs-benchmarks/liquid-resize-par.js

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

branch
TOR_BUG_3246
changeset 7
129ffea94266
equal deleted inserted replaced
-1:000000000000 0:3d68ec6f51b8
1 // -*- mode: js2; indent-tabs-mode: nil; -*-
2
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
12
13 ///////////////////////////////////////////////////////////////////////////
14 // Inputs
15
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 }
27
28 function parImage(seqImage, width, height) {
29 return new ParallelArray([height, width], function (y, x) {
30 return seqImage[y*width + x];
31 });
32 }
33
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 });
49
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 });
67
68 var SmallImagePar = parImage(SmallImage,
69 SmallImageWidth,
70 SmallImageHeight);
71
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 });
87
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 }
97
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 }
104
105 var massiveImage =
106 buildArray(70, 10000, function(y, x) (Math.abs(x%100-y%100) < 10) ? 32 : 0);
107
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 }
119
120 ///////////////////////////////////////////////////////////////////////////
121 // Common
122
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]];
129
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 }
157
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];
166
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 }
173
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 }
189
190 ///////////////////////////////////////////////////////////////////////////
191 // Sequential
192
193 function transposeSeq(array, width, height) {
194 return buildArray(height, width, function(y, x) {
195 return array[x*width + y];
196 });
197 }
198
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;
209
210 function compute(y, x) {
211 var totalX = 0;
212 var totalY = 0;
213
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);
218
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 }
226
227 return (Math.abs(totalX) + Math.abs(totalY))/8.0 | 0;
228 }
229 }
230
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 }
241
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 }
252
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 }
261
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 }
271
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);
279
280 if (width > newWidth) {
281 image = cutHorizontalSeamBWSeq(image, width, height);
282 width -= 1;
283 }
284
285 if (height > newHeight) {
286 image = cutVerticalSeamBWSeq(image, width, height);
287 height -= 1;
288 }
289 }
290
291 finalFunc(image, width, height);
292 return image;
293 }
294
295 ///////////////////////////////////////////////////////////////////////////
296 // Parallel
297
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 }
305
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;
313
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);
318
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 }
326
327 var result = (Math.abs(totalX) + Math.abs(totalY))/8.0 | 0;
328 return result;
329 });
330 }
331
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 }
344
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 }
357
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 }
368
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 }
379
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);
388
389 if (width > newWidth) {
390 image = cutHorizontalSeamBWPar(image);
391 width -= 1;
392 }
393
394 if (height > newHeight) {
395 image = cutVerticalSeamBWPar(image);
396 height -= 1;
397 }
398 }
399
400 finalFunc(image.buffer, width, height);
401 return image.buffer;
402 }
403
404 ///////////////////////////////////////////////////////////////////////////
405 // Benchmarking via run.sh
406
407 var BenchmarkImageWidth = 512;
408 var BenchmarkImageHeight = 256;
409 var BenchmarkImage = stripedImage(BenchmarkImageWidth,
410 BenchmarkImageHeight);
411 var BenchmarkImagePar = parImage(BenchmarkImage,
412 BenchmarkImageWidth,
413 BenchmarkImageHeight);
414
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 },
427
428 function() {
429 return reduceImageBWPar(
430 BenchmarkImagePar,
431 BenchmarkImageWidth/2, BenchmarkImageHeight/2,
432 function() {},
433 function() {});
434 });
435 }
436
437 ///////////////////////////////////////////////////////////////////////////
438 // Running (sanity check)
439
440 if (!benchmarking) {
441 var seqData =
442 reduceImageBWSeq(SmallImage, SmallImageWidth, SmallImageHeight,
443 SmallImageWidth - 15, SmallImageHeight - 10,
444 function() {},
445 printImage);
446
447 var parData =
448 reduceImageBWPar(SmallImagePar,
449 SmallImageWidth - 15, SmallImageHeight - 10,
450 function() {},
451 printImage);
452
453 assertEq(seqData, parData);
454 }

Mercurial Repository: The Tor Browser

Europalab SCM Repository Server

mercurial