gx

chenyc

2025-06-12 7b72ac13a83764a662159d4a49b7fffb90476ecb

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
/**
 * @license
 * Copyright 2020 Google LLC. All Rights Reserved.
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 * http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 * =============================================================================
 */
import { ResizeBilinearGrad, util } from '@tensorflow/tfjs-core';
import { assertNotComplex } from '../cpu_util';
export function resizeBilinearGrad(args) {
    const { inputs, backend, attrs } = args;
    const { images, dy } = inputs;
    const { alignCorners } = attrs;
    assertNotComplex([dy, images], 'resizeBilinearGrad');
    const imagesStrides = util.computeStrides(images.shape);
    const [batch, xHeight, xWidth, depth] = images.shape;
    const [, yHeight, yWidth] = dy.shape;
    const output = new Float32Array(batch * xHeight * xWidth * depth);
    // In the backwards pass, we want to find the pixels that were generated
    // for each pixel in the input image the forward pass and add the
    // corresponding coefficient from dy to the gradient (with some
    // interpolation).
    const effectiveXSize = [
        (alignCorners && yHeight > 1) ? xHeight - 1 : xHeight,
        (alignCorners && yWidth > 1) ? xWidth - 1 : xWidth
    ];
    const effectiveYSize = [
        (alignCorners && yHeight > 1) ? yHeight - 1 : yHeight,
        (alignCorners && yWidth > 1) ? yWidth - 1 : yWidth
    ];
    const heightScale = effectiveXSize[0] / effectiveYSize[0];
    const widthScale = effectiveXSize[1] / effectiveYSize[1];
    // Reference implementation
    // tslint:disable-next-line:max-line-length
    // https://github.com/tensorflow/tensorflow/blob/3039375c86a5bbc9610c7725dcaa95d635f87ba2/tensorflow/core/kernels/resize_bilinear_op.cc#L275
    const dyValues = backend.data.get(dy.dataId).values;
    let offset = 0;
    for (let b = 0; b < batch; b++) {
        const bOffset = b * imagesStrides[0];
        for (let r = 0; r < yHeight; r++) {
            const dxR = r * heightScale;
            const topDxRIndex = Math.floor(dxR);
            const bottomDxRIndex = Math.min(Math.ceil(dxR), xHeight - 1);
            const topDxROffset = bOffset + topDxRIndex * imagesStrides[1];
            const bottomDxROffset = bOffset + bottomDxRIndex * imagesStrides[1];
            const dxRLerp = dxR - topDxRIndex;
            const inverseDxRLerp = 1.0 - dxRLerp;
            for (let c = 0; c < yWidth; c++) {
                const dxC = c * widthScale;
                const leftDxCIndex = Math.floor(dxC);
                const rightDxCIndex = Math.min(Math.ceil(dxC), xWidth - 1);
                const dxCLerp = dxC - leftDxCIndex;
                const inverseDxCLerp = 1.0 - dxCLerp;
                const topLeftRCOffset = topDxROffset + leftDxCIndex * imagesStrides[2];
                const topRightRCOffset = topDxROffset + rightDxCIndex * imagesStrides[2];
                const bottomLeftRCOffset = bottomDxROffset + leftDxCIndex * imagesStrides[2];
                const bottomRightRCOffset = bottomDxROffset + rightDxCIndex * imagesStrides[2];
                const inverseDxRLerpTimesInverseDxCLerp = inverseDxRLerp * inverseDxCLerp;
                const inverseDxRLerpTimesDxCLerp = inverseDxRLerp * dxCLerp;
                const dxRLerpTimesInverseDxCLerp = dxRLerp * inverseDxCLerp;
                const dxRLerpTimesDxCLerp = dxRLerp * dxCLerp;
                for (let d = 0; d < depth; d++) {
                    const dyVal = dyValues[offset++];
                    output[topLeftRCOffset + d] +=
                        dyVal * inverseDxRLerpTimesInverseDxCLerp;
                    output[topRightRCOffset + d] += dyVal * inverseDxRLerpTimesDxCLerp;
                    output[bottomLeftRCOffset + d] += dyVal * dxRLerpTimesInverseDxCLerp;
                    output[bottomRightRCOffset + d] += dyVal * dxRLerpTimesDxCLerp;
                }
            }
        }
    }
    return backend.makeTensorInfo([batch, xWidth, xHeight, depth], 'float32', output);
}
export const resizeBilinearGradConfig = {
    kernelName: ResizeBilinearGrad,
    backendName: 'cpu',
    kernelFunc: resizeBilinearGrad
};
//# sourceMappingURL=data:application/json;base64,eyJ2ZXJzaW9uIjozLCJmaWxlIjoiUmVzaXplQmlsaW5lYXJHcmFkLmpzIiwic291cmNlUm9vdCI6IiIsInNvdXJjZXMiOlsiLi4vLi4vLi4vLi4vLi4vLi4vdGZqcy1iYWNrZW5kLWNwdS9zcmMva2VybmVscy9SZXNpemVCaWxpbmVhckdyYWQudHMiXSwibmFtZXMiOltdLCJtYXBwaW5ncyI6IkFBQUE7Ozs7Ozs7Ozs7Ozs7OztHQWVHO0FBRUgsT0FBTyxFQUEyQixrQkFBa0IsRUFBNkUsSUFBSSxFQUFDLE1BQU0sdUJBQXVCLENBQUM7QUFHcEssT0FBTyxFQUFDLGdCQUFnQixFQUFDLE1BQU0sYUFBYSxDQUFDO0FBRTdDLE1BQU0sVUFBVSxrQkFBa0IsQ0FBQyxJQUlsQztJQUNDLE1BQU0sRUFBQyxNQUFNLEVBQUUsT0FBTyxFQUFFLEtBQUssRUFBQyxHQUFHLElBQUksQ0FBQztJQUN0QyxNQUFNLEVBQUMsTUFBTSxFQUFFLEVBQUUsRUFBQyxHQUFHLE1BQU0sQ0FBQztJQUM1QixNQUFNLEVBQUMsWUFBWSxFQUFDLEdBQUcsS0FBSyxDQUFDO0lBRTdCLGdCQUFnQixDQUFDLENBQUMsRUFBRSxFQUFFLE1BQU0sQ0FBQyxFQUFFLG9CQUFvQixDQUFDLENBQUM7SUFFckQsTUFBTSxhQUFhLEdBQUcsSUFBSSxDQUFDLGNBQWMsQ0FBQyxNQUFNLENBQUMsS0FBSyxDQUFDLENBQUM7SUFFeEQsTUFBTSxDQUFDLEtBQUssRUFBRSxPQUFPLEVBQUUsTUFBTSxFQUFFLEtBQUssQ0FBQyxHQUFHLE1BQU0sQ0FBQyxLQUFLLENBQUM7SUFDckQsTUFBTSxDQUFDLEVBQUUsT0FBTyxFQUFFLE1BQU0sQ0FBQyxHQUFHLEVBQUUsQ0FBQyxLQUFLLENBQUM7SUFFckMsTUFBTSxNQUFNLEdBQUcsSUFBSSxZQUFZLENBQUMsS0FBSyxHQUFHLE9BQU8sR0FBRyxNQUFNLEdBQUcsS0FBSyxDQUFDLENBQUM7SUFFbEUsd0VBQXdFO0lBQ3hFLGlFQUFpRTtJQUNqRSwrREFBK0Q7SUFDL0Qsa0JBQWtCO0lBRWxCLE1BQU0sY0FBYyxHQUFxQjtRQUN2QyxDQUFDLFlBQVksSUFBSSxPQUFPLEdBQUcsQ0FBQyxDQUFDLENBQUMsQ0FBQyxDQUFDLE9BQU8sR0FBRyxDQUFDLENBQUMsQ0FBQyxDQUFDLE9BQU87UUFDckQsQ0FBQyxZQUFZLElBQUksTUFBTSxHQUFHLENBQUMsQ0FBQyxDQUFDLENBQUMsQ0FBQyxNQUFNLEdBQUcsQ0FBQyxDQUFDLENBQUMsQ0FBQyxNQUFNO0tBQ25ELENBQUM7SUFFRixNQUFNLGNBQWMsR0FBcUI7UUFDdkMsQ0FBQyxZQUFZLElBQUksT0FBTyxHQUFHLENBQUMsQ0FBQyxDQUFDLENBQUMsQ0FBQyxPQUFPLEdBQUcsQ0FBQyxDQUFDLENBQUMsQ0FBQyxPQUFPO1FBQ3JELENBQUMsWUFBWSxJQUFJLE1BQU0sR0FBRyxDQUFDLENBQUMsQ0FBQyxDQUFDLENBQUMsTUFBTSxHQUFHLENBQUMsQ0FBQyxDQUFDLENBQUMsTUFBTTtLQUNuRCxDQUFDO0lBRUYsTUFBTSxXQUFXLEdBQUcsY0FBYyxDQUFDLENBQUMsQ0FBQyxHQUFHLGNBQWMsQ0FBQyxDQUFDLENBQUMsQ0FBQztJQUMxRCxNQUFNLFVBQVUsR0FBRyxjQUFjLENBQUMsQ0FBQyxDQUFDLEdBQUcsY0FBYyxDQUFDLENBQUMsQ0FBQyxDQUFDO0lBRXpELDJCQUEyQjtJQUMzQiwyQ0FBMkM7SUFDM0MsNElBQTRJO0lBQzVJLE1BQU0sUUFBUSxHQUFHLE9BQU8sQ0FBQyxJQUFJLENBQUMsR0FBRyxDQUFDLEVBQUUsQ0FBQyxNQUFNLENBQUMsQ0FBQyxNQUFvQixDQUFDO0lBQ2xFLElBQUksTUFBTSxHQUFHLENBQUMsQ0FBQztJQUNmLEtBQUssSUFBSSxDQUFDLEdBQUcsQ0FBQyxFQUFFLENBQUMsR0FBRyxLQUFLLEVBQUUsQ0FBQyxFQUFFLEVBQUU7UUFDOUIsTUFBTSxPQUFPLEdBQUcsQ0FBQyxHQUFHLGFBQWEsQ0FBQyxDQUFDLENBQUMsQ0FBQztRQUNyQyxLQUFLLElBQUksQ0FBQyxHQUFHLENBQUMsRUFBRSxDQUFDLEdBQUcsT0FBTyxFQUFFLENBQUMsRUFBRSxFQUFFO1lBQ2hDLE1BQU0sR0FBRyxHQUFHLENBQUMsR0FBRyxXQUFXLENBQUM7WUFDNUIsTUFBTSxXQUFXLEdBQUcsSUFBSSxDQUFDLEtBQUssQ0FBQyxHQUFHLENBQUMsQ0FBQztZQUNwQyxNQUFNLGNBQWMsR0FBRyxJQUFJLENBQUMsR0FBRyxDQUFDLElBQUksQ0FBQyxJQUFJLENBQUMsR0FBRyxDQUFDLEVBQUUsT0FBTyxHQUFHLENBQUMsQ0FBQyxDQUFDO1lBRTdELE1BQU0sWUFBWSxHQUFHLE9BQU8sR0FBRyxXQUFXLEdBQUcsYUFBYSxDQUFDLENBQUMsQ0FBQyxDQUFDO1lBQzlELE1BQU0sZUFBZSxHQUFHLE9BQU8sR0FBRyxjQUFjLEdBQUcsYUFBYSxDQUFDLENBQUMsQ0FBQyxDQUFDO1lBRXBFLE1BQU0sT0FBTyxHQUFHLEdBQUcsR0FBRyxXQUFXLENBQUM7WUFDbEMsTUFBTSxjQUFjLEdBQUcsR0FBRyxHQUFHLE9BQU8sQ0FBQztZQUNyQyxLQUFLLElBQUksQ0FBQyxHQUFHLENBQUMsRUFBRSxDQUFDLEdBQUcsTUFBTSxFQUFFLENBQUMsRUFBRSxFQUFFO2dCQUMvQixNQUFNLEdBQUcsR0FBRyxDQUFDLEdBQUcsVUFBVSxDQUFDO2dCQUMzQixNQUFNLFlBQVksR0FBRyxJQUFJLENBQUMsS0FBSyxDQUFDLEdBQUcsQ0FBQyxDQUFDO2dCQUNyQyxNQUFNLGFBQWEsR0FBRyxJQUFJLENBQUMsR0FBRyxDQUFDLElBQUksQ0FBQyxJQUFJLENBQUMsR0FBRyxDQUFDLEVBQUUsTUFBTSxHQUFHLENBQUMsQ0FBQyxDQUFDO2dCQUMzRCxNQUFNLE9BQU8sR0FBRyxHQUFHLEdBQUcsWUFBWSxDQUFDO2dCQUNuQyxNQUFNLGNBQWMsR0FBRyxHQUFHLEdBQUcsT0FBTyxDQUFDO2dCQUVyQyxNQUFNLGVBQWUsR0FBRyxZQUFZLEdBQUcsWUFBWSxHQUFHLGFBQWEsQ0FBQyxDQUFDLENBQUMsQ0FBQztnQkFDdkUsTUFBTSxnQkFBZ0IsR0FDbEIsWUFBWSxHQUFHLGFBQWEsR0FBRyxhQUFhLENBQUMsQ0FBQyxDQUFDLENBQUM7Z0JBQ3BELE1BQU0sa0JBQWtCLEdBQ3BCLGVBQWUsR0FBRyxZQUFZLEdBQUcsYUFBYSxDQUFDLENBQUMsQ0FBQyxDQUFDO2dCQUN0RCxNQUFNLG1CQUFtQixHQUNyQixlQUFlLEdBQUcsYUFBYSxHQUFHLGFBQWEsQ0FBQyxDQUFDLENBQUMsQ0FBQztnQkFFdkQsTUFBTSxpQ0FBaUMsR0FDbkMsY0FBYyxHQUFHLGNBQWMsQ0FBQztnQkFDcEMsTUFBTSwwQkFBMEIsR0FBRyxjQUFjLEdBQUcsT0FBTyxDQUFDO2dCQUM1RCxNQUFNLDBCQUEwQixHQUFHLE9BQU8sR0FBRyxjQUFjLENBQUM7Z0JBQzVELE1BQU0sbUJBQW1CLEdBQUcsT0FBTyxHQUFHLE9BQU8sQ0FBQztnQkFDOUMsS0FBSyxJQUFJLENBQUMsR0FBRyxDQUFDLEVBQUUsQ0FBQyxHQUFHLEtBQUssRUFBRSxDQUFDLEVBQUUsRUFBRTtvQkFDOUIsTUFBTSxLQUFLLEdBQUcsUUFBUSxDQUFDLE1BQU0sRUFBRSxDQUFDLENBQUM7b0JBQ2pDLE1BQU0sQ0FBQyxlQUFlLEdBQUcsQ0FBQyxDQUFDO3dCQUN2QixLQUFLLEdBQUcsaUNBQWlDLENBQUM7b0JBQzlDLE1BQU0sQ0FBQyxnQkFBZ0IsR0FBRyxDQUFDLENBQUMsSUFBSSxLQUFLLEdBQUcsMEJBQTBCLENBQUM7b0JBQ25FLE1BQU0sQ0FBQyxrQkFBa0IsR0FBRyxDQUFDLENBQUMsSUFBSSxLQUFLLEdBQUcsMEJBQTBCLENBQUM7b0JBQ3JFLE1BQU0sQ0FBQyxtQkFBbUIsR0FBRyxDQUFDLENBQUMsSUFBSSxLQUFLLEdBQUcsbUJBQW1CLENBQUM7aUJBQ2hFO2FBQ0Y7U0FDRjtLQUNGO0lBRUQsT0FBTyxPQUFPLENBQUMsY0FBYyxDQUN6QixDQUFDLEtBQUssRUFBRSxNQUFNLEVBQUUsT0FBTyxFQUFFLEtBQUssQ0FBQyxFQUFFLFNBQVMsRUFBRSxNQUFNLENBQUMsQ0FBQztBQUMxRCxDQUFDO0FBRUQsTUFBTSxDQUFDLE1BQU0sd0JBQXdCLEdBQWlCO0lBQ3BELFVBQVUsRUFBRSxrQkFBa0I7SUFDOUIsV0FBVyxFQUFFLEtBQUs7SUFDbEIsVUFBVSxFQUFFLGtCQUEyQztDQUN4RCxDQUFDIiwic291cmNlc0NvbnRlbnQiOlsiLyoqXG4gKiBAbGljZW5zZVxuICogQ29weXJpZ2h0IDIwMjAgR29vZ2xlIExMQy4gQWxsIFJpZ2h0cyBSZXNlcnZlZC5cbiAqIExpY2Vuc2VkIHVuZGVyIHRoZSBBcGFjaGUgTGljZW5zZSwgVmVyc2lvbiAyLjAgKHRoZSBcIkxpY2Vuc2VcIik7XG4gKiB5b3UgbWF5IG5vdCB1c2UgdGhpcyBmaWxlIGV4Y2VwdCBpbiBjb21wbGlhbmNlIHdpdGggdGhlIExpY2Vuc2UuXG4gKiBZb3UgbWF5IG9idGFpbiBhIGNvcHkgb2YgdGhlIExpY2Vuc2UgYXRcbiAqXG4gKiBodHRwOi8vd3d3LmFwYWNoZS5vcmcvbGljZW5zZXMvTElDRU5TRS0yLjBcbiAqXG4gKiBVbmxlc3MgcmVxdWlyZWQgYnkgYXBwbGljYWJsZSBsYXcgb3IgYWdyZWVkIHRvIGluIHdyaXRpbmcsIHNvZnR3YXJlXG4gKiBkaXN0cmlidXRlZCB1bmRlciB0aGUgTGljZW5zZSBpcyBkaXN0cmlidXRlZCBvbiBhbiBcIkFTIElTXCIgQkFTSVMsXG4gKiBXSVRIT1VUIFdBUlJBTlRJRVMgT1IgQ09ORElUSU9OUyBPRiBBTlkgS0lORCwgZWl0aGVyIGV4cHJlc3Mgb3IgaW1wbGllZC5cbiAqIFNlZSB0aGUgTGljZW5zZSBmb3IgdGhlIHNwZWNpZmljIGxhbmd1YWdlIGdvdmVybmluZyBwZXJtaXNzaW9ucyBhbmRcbiAqIGxpbWl0YXRpb25zIHVuZGVyIHRoZSBMaWNlbnNlLlxuICogPT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT1cbiAqL1xuXG5pbXBvcnQge0tlcm5lbENvbmZpZywgS2VybmVsRnVuYywgUmVzaXplQmlsaW5lYXJHcmFkLCBSZXNpemVCaWxpbmVhckdyYWRBdHRycywgUmVzaXplQmlsaW5lYXJHcmFkSW5wdXRzLCBUZW5zb3JJbmZvLCBUeXBlZEFycmF5LCB1dGlsfSBmcm9tICdAdGVuc29yZmxvdy90ZmpzLWNvcmUnO1xuXG5pbXBvcnQge01hdGhCYWNrZW5kQ1BVfSBmcm9tICcuLi9iYWNrZW5kX2NwdSc7XG5pbXBvcnQge2Fzc2VydE5vdENvbXBsZXh9IGZyb20gJy4uL2NwdV91dGlsJztcblxuZXhwb3J0IGZ1bmN0aW9uIHJlc2l6ZUJpbGluZWFyR3JhZChhcmdzOiB7XG4gIGlucHV0czogUmVzaXplQmlsaW5lYXJHcmFkSW5wdXRzLFxuICBiYWNrZW5kOiBNYXRoQmFja2VuZENQVSxcbiAgYXR0cnM6IFJlc2l6ZUJpbGluZWFyR3JhZEF0dHJzXG59KTogVGVuc29ySW5mbyB7XG4gIGNvbnN0IHtpbnB1dHMsIGJhY2tlbmQsIGF0dHJzfSA9IGFyZ3M7XG4gIGNvbnN0IHtpbWFnZXMsIGR5fSA9IGlucHV0cztcbiAgY29uc3Qge2FsaWduQ29ybmVyc30gPSBhdHRycztcblxuICBhc3NlcnROb3RDb21wbGV4KFtkeSwgaW1hZ2VzXSwgJ3Jlc2l6ZUJpbGluZWFyR3JhZCcpO1xuXG4gIGNvbnN0IGltYWdlc1N0cmlkZXMgPSB1dGlsLmNvbXB1dGVTdHJpZGVzKGltYWdlcy5zaGFwZSk7XG5cbiAgY29uc3QgW2JhdGNoLCB4SGVpZ2h0LCB4V2lkdGgsIGRlcHRoXSA9IGltYWdlcy5zaGFwZTtcbiAgY29uc3QgWywgeUhlaWdodCwgeVdpZHRoXSA9IGR5LnNoYXBlO1xuXG4gIGNvbnN0IG91dHB1dCA9IG5ldyBGbG9hdDMyQXJyYXkoYmF0Y2ggKiB4SGVpZ2h0ICogeFdpZHRoICogZGVwdGgpO1xuXG4gIC8vIEluIHRoZSBiYWNrd2FyZHMgcGFzcywgd2Ugd2FudCB0byBmaW5kIHRoZSBwaXhlbHMgdGhhdCB3ZXJlIGdlbmVyYXRlZFxuICAvLyBmb3IgZWFjaCBwaXhlbCBpbiB0aGUgaW5wdXQgaW1hZ2UgdGhlIGZvcndhcmQgcGFzcyBhbmQgYWRkIHRoZVxuICAvLyBjb3JyZXNwb25kaW5nIGNvZWZmaWNpZW50IGZyb20gZHkgdG8gdGhlIGdyYWRpZW50ICh3aXRoIHNvbWVcbiAgLy8gaW50ZXJwb2xhdGlvbikuXG5cbiAgY29uc3QgZWZmZWN0aXZlWFNpemU6IFtudW1iZXIsIG51bWJlcl0gPSBbXG4gICAgKGFsaWduQ29ybmVycyAmJiB5SGVpZ2h0ID4gMSkgPyB4SGVpZ2h0IC0gMSA6IHhIZWlnaHQsXG4gICAgKGFsaWduQ29ybmVycyAmJiB5V2lkdGggPiAxKSA/IHhXaWR0aCAtIDEgOiB4V2lkdGhcbiAgXTtcblxuICBjb25zdCBlZmZlY3RpdmVZU2l6ZTogW251bWJlciwgbnVtYmVyXSA9IFtcbiAgICAoYWxpZ25Db3JuZXJzICYmIHlIZWlnaHQgPiAxKSA/IHlIZWlnaHQgLSAxIDogeUhlaWdodCxcbiAgICAoYWxpZ25Db3JuZXJzICYmIHlXaWR0aCA+IDEpID8geVdpZHRoIC0gMSA6IHlXaWR0aFxuICBdO1xuXG4gIGNvbnN0IGhlaWdodFNjYWxlID0gZWZmZWN0aXZlWFNpemVbMF0gLyBlZmZlY3RpdmVZU2l6ZVswXTtcbiAgY29uc3Qgd2lkdGhTY2FsZSA9IGVmZmVjdGl2ZVhTaXplWzFdIC8gZWZmZWN0aXZlWVNpemVbMV07XG5cbiAgLy8gUmVmZXJlbmNlIGltcGxlbWVudGF0aW9uXG4gIC8vIHRzbGludDpkaXNhYmxlLW5leHQtbGluZTptYXgtbGluZS1sZW5ndGhcbiAgLy8gaHR0cHM6Ly9naXRodWIuY29tL3RlbnNvcmZsb3cvdGVuc29yZmxvdy9ibG9iLzMwMzkzNzVjODZhNWJiYzk2MTBjNzcyNWRjYWE5NWQ2MzVmODdiYTIvdGVuc29yZmxvdy9jb3JlL2tlcm5lbHMvcmVzaXplX2JpbGluZWFyX29wLmNjI0wyNzVcbiAgY29uc3QgZHlWYWx1ZXMgPSBiYWNrZW5kLmRhdGEuZ2V0KGR5LmRhdGFJZCkudmFsdWVzIGFzIFR5cGVkQXJyYXk7XG4gIGxldCBvZmZzZXQgPSAwO1xuICBmb3IgKGxldCBiID0gMDsgYiA8IGJhdGNoOyBiKyspIHtcbiAgICBjb25zdCBiT2Zmc2V0ID0gYiAqIGltYWdlc1N0cmlkZXNbMF07XG4gICAgZm9yIChsZXQgciA9IDA7IHIgPCB5SGVpZ2h0OyByKyspIHtcbiAgICAgIGNvbnN0IGR4UiA9IHIgKiBoZWlnaHRTY2FsZTtcbiAgICAgIGNvbnN0IHRvcER4UkluZGV4ID0gTWF0aC5mbG9vcihkeFIpO1xuICAgICAgY29uc3QgYm90dG9tRHhSSW5kZXggPSBNYXRoLm1pbihNYXRoLmNlaWwoZHhSKSwgeEhlaWdodCAtIDEpO1xuXG4gICAgICBjb25zdCB0b3BEeFJPZmZzZXQgPSBiT2Zmc2V0ICsgdG9wRHhSSW5kZXggKiBpbWFnZXNTdHJpZGVzWzFdO1xuICAgICAgY29uc3QgYm90dG9tRHhST2Zmc2V0ID0gYk9mZnNldCArIGJvdHRvbUR4UkluZGV4ICogaW1hZ2VzU3RyaWRlc1sxXTtcblxuICAgICAgY29uc3QgZHhSTGVycCA9IGR4UiAtIHRvcER4UkluZGV4O1xuICAgICAgY29uc3QgaW52ZXJzZUR4UkxlcnAgPSAxLjAgLSBkeFJMZXJwO1xuICAgICAgZm9yIChsZXQgYyA9IDA7IGMgPCB5V2lkdGg7IGMrKykge1xuICAgICAgICBjb25zdCBkeEMgPSBjICogd2lkdGhTY2FsZTtcbiAgICAgICAgY29uc3QgbGVmdER4Q0luZGV4ID0gTWF0aC5mbG9vcihkeEMpO1xuICAgICAgICBjb25zdCByaWdodER4Q0luZGV4ID0gTWF0aC5taW4oTWF0aC5jZWlsKGR4QyksIHhXaWR0aCAtIDEpO1xuICAgICAgICBjb25zdCBkeENMZXJwID0gZHhDIC0gbGVmdER4Q0luZGV4O1xuICAgICAgICBjb25zdCBpbnZlcnNlRHhDTGVycCA9IDEuMCAtIGR4Q0xlcnA7XG5cbiAgICAgICAgY29uc3QgdG9wTGVmdFJDT2Zmc2V0ID0gdG9wRHhST2Zmc2V0ICsgbGVmdER4Q0luZGV4ICogaW1hZ2VzU3RyaWRlc1syXTtcbiAgICAgICAgY29uc3QgdG9wUmlnaHRSQ09mZnNldCA9XG4gICAgICAgICAgICB0b3BEeFJPZmZzZXQgKyByaWdodER4Q0luZGV4ICogaW1hZ2VzU3RyaWRlc1syXTtcbiAgICAgICAgY29uc3QgYm90dG9tTGVmdFJDT2Zmc2V0ID1cbiAgICAgICAgICAgIGJvdHRvbUR4Uk9mZnNldCArIGxlZnREeENJbmRleCAqIGltYWdlc1N0cmlkZXNbMl07XG4gICAgICAgIGNvbnN0IGJvdHRvbVJpZ2h0UkNPZmZzZXQgPVxuICAgICAgICAgICAgYm90dG9tRHhST2Zmc2V0ICsgcmlnaHREeENJbmRleCAqIGltYWdlc1N0cmlkZXNbMl07XG5cbiAgICAgICAgY29uc3QgaW52ZXJzZUR4UkxlcnBUaW1lc0ludmVyc2VEeENMZXJwID1cbiAgICAgICAgICAgIGludmVyc2VEeFJMZXJwICogaW52ZXJzZUR4Q0xlcnA7XG4gICAgICAgIGNvbnN0IGludmVyc2VEeFJMZXJwVGltZXNEeENMZXJwID0gaW52ZXJzZUR4UkxlcnAgKiBkeENMZXJwO1xuICAgICAgICBjb25zdCBkeFJMZXJwVGltZXNJbnZlcnNlRHhDTGVycCA9IGR4UkxlcnAgKiBpbnZlcnNlRHhDTGVycDtcbiAgICAgICAgY29uc3QgZHhSTGVycFRpbWVzRHhDTGVycCA9IGR4UkxlcnAgKiBkeENMZXJwO1xuICAgICAgICBmb3IgKGxldCBkID0gMDsgZCA8IGRlcHRoOyBkKyspIHtcbiAgICAgICAgICBjb25zdCBkeVZhbCA9IGR5VmFsdWVzW29mZnNldCsrXTtcbiAgICAgICAgICBvdXRwdXRbdG9wTGVmdFJDT2Zmc2V0ICsgZF0gKz1cbiAgICAgICAgICAgICAgZHlWYWwgKiBpbnZlcnNlRHhSTGVycFRpbWVzSW52ZXJzZUR4Q0xlcnA7XG4gICAgICAgICAgb3V0cHV0W3RvcFJpZ2h0UkNPZmZzZXQgKyBkXSArPSBkeVZhbCAqIGludmVyc2VEeFJMZXJwVGltZXNEeENMZXJwO1xuICAgICAgICAgIG91dHB1dFtib3R0b21MZWZ0UkNPZmZzZXQgKyBkXSArPSBkeVZhbCAqIGR4UkxlcnBUaW1lc0ludmVyc2VEeENMZXJwO1xuICAgICAgICAgIG91dHB1dFtib3R0b21SaWdodFJDT2Zmc2V0ICsgZF0gKz0gZHlWYWwgKiBkeFJMZXJwVGltZXNEeENMZXJwO1xuICAgICAgICB9XG4gICAgICB9XG4gICAgfVxuICB9XG5cbiAgcmV0dXJuIGJhY2tlbmQubWFrZVRlbnNvckluZm8oXG4gICAgICBbYmF0Y2gsIHhXaWR0aCwgeEhlaWdodCwgZGVwdGhdLCAnZmxvYXQzMicsIG91dHB1dCk7XG59XG5cbmV4cG9ydCBjb25zdCByZXNpemVCaWxpbmVhckdyYWRDb25maWc6IEtlcm5lbENvbmZpZyA9IHtcbiAga2VybmVsTmFtZTogUmVzaXplQmlsaW5lYXJHcmFkLFxuICBiYWNrZW5kTmFtZTogJ2NwdScsXG4gIGtlcm5lbEZ1bmM6IHJlc2l6ZUJpbGluZWFyR3JhZCBhcyB1bmtub3duIGFzIEtlcm5lbEZ1bmNcbn07XG4iXX0=