gx

chenyc

2025-02-12 ea42ff3ebee1eeb3fb29423aa848a249441db81c

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
90
/**
 * @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 { backend_util, Conv3D, TensorBuffer, util } from '@tensorflow/tfjs-core';
import { assertNotComplex } from '../cpu_util';
export function conv3D(args) {
    const { inputs, backend, attrs } = args;
    const { x, filter } = inputs;
    const { strides, pad, dilations } = attrs;
    assertNotComplex([x, filter], 'conv3d');
    const convInfo = backend_util.computeConv3DInfo(x.shape, filter.shape, strides, dilations, pad);
    const { filterDepth, filterHeight, filterWidth, dilationDepth, dilationHeight, dilationWidth, padInfo } = convInfo;
    const padFront = padInfo.front;
    const padLeft = padInfo.left;
    const padTop = padInfo.top;
    const y = new TensorBuffer(convInfo.outShape, x.dtype);
    const xVals = backend.data.get(x.dataId).values;
    const wVals = backend.data.get(filter.dataId).values;
    const yVals = y.values;
    const xStrides = util.computeStrides(x.shape);
    const filterStrides = util.computeStrides(filter.shape);
    for (let b = 0; b < convInfo.batchSize; ++b) {
        const xOffset1 = b * xStrides[0];
        const yOffset1 = b * y.strides[0];
        for (let yF = 0; yF < convInfo.outDepth; ++yF) {
            const yOffset2 = yOffset1 + yF * y.strides[1];
            const xFCorner = yF * convInfo.strideDepth - padFront;
            for (let wF = 0; wF < filterDepth; ++wF) {
                const xF = xFCorner + wF * dilationDepth;
                if (xF < 0 || xF >= convInfo.inDepth) {
                    continue;
                }
                const wOffset1 = wF * filterStrides[0];
                const xOffset2 = xOffset1 + xF * xStrides[1];
                for (let yR = 0; yR < convInfo.outHeight; ++yR) {
                    const yOffset3 = yOffset2 + yR * y.strides[2];
                    const xRCorner = yR * convInfo.strideHeight - padTop;
                    for (let wR = 0; wR < filterHeight; ++wR) {
                        const xR = xRCorner + wR * dilationHeight;
                        if (xR < 0 || xR >= convInfo.inHeight) {
                            continue;
                        }
                        const wOffset2 = wOffset1 + wR * filterStrides[1];
                        const xOffset3 = xOffset2 + xR * xStrides[2];
                        for (let yC = 0; yC < convInfo.outWidth; ++yC) {
                            const yOffset4 = yOffset3 + yC * convInfo.outChannels;
                            const xCCorner = yC * convInfo.strideWidth - padLeft;
                            for (let wC = 0; wC < filterWidth; ++wC) {
                                const xC = xCCorner + wC * dilationWidth;
                                if (xC < 0 || xC >= convInfo.inWidth) {
                                    continue;
                                }
                                const wOffset3 = wOffset2 + wC * filterStrides[2];
                                const xOffset4 = xOffset3 + xC * convInfo.inChannels;
                                let wOffset4 = wOffset3;
                                for (let d1 = 0; d1 < convInfo.inChannels; ++d1) {
                                    const xVal = xVals[xOffset4 + d1];
                                    for (let d2 = 0; d2 < convInfo.outChannels; ++d2) {
                                        yVals[yOffset4 + d2] += xVal * wVals[wOffset4 + d2];
                                    }
                                    wOffset4 += convInfo.outChannels;
                                }
                            }
                        }
                    }
                }
            }
        }
    }
    return backend.makeTensorInfo(y.shape, y.dtype, y.values);
}
export const conv3DConfig = {
    kernelName: Conv3D,
    backendName: 'cpu',
    kernelFunc: conv3D
};
//# sourceMappingURL=data:application/json;base64,eyJ2ZXJzaW9uIjozLCJmaWxlIjoiQ29udjNELmpzIiwic291cmNlUm9vdCI6IiIsInNvdXJjZXMiOlsiLi4vLi4vLi4vLi4vLi4vLi4vdGZqcy1iYWNrZW5kLWNwdS9zcmMva2VybmVscy9Db252M0QudHMiXSwibmFtZXMiOltdLCJtYXBwaW5ncyI6IkFBQUE7Ozs7Ozs7Ozs7Ozs7OztHQWVHO0FBRUgsT0FBTyxFQUFDLFlBQVksRUFBRSxNQUFNLEVBQXVELFlBQVksRUFBMEIsSUFBSSxFQUFDLE1BQU0sdUJBQXVCLENBQUM7QUFHNUosT0FBTyxFQUFDLGdCQUFnQixFQUFDLE1BQU0sYUFBYSxDQUFDO0FBRTdDLE1BQU0sVUFBVSxNQUFNLENBQ2xCLElBQXlFO0lBRTNFLE1BQU0sRUFBQyxNQUFNLEVBQUUsT0FBTyxFQUFFLEtBQUssRUFBQyxHQUFHLElBQUksQ0FBQztJQUN0QyxNQUFNLEVBQUMsQ0FBQyxFQUFFLE1BQU0sRUFBQyxHQUFHLE1BQU0sQ0FBQztJQUMzQixNQUFNLEVBQUMsT0FBTyxFQUFFLEdBQUcsRUFBRSxTQUFTLEVBQUMsR0FBRyxLQUFLLENBQUM7SUFFeEMsZ0JBQWdCLENBQUMsQ0FBQyxDQUFDLEVBQUUsTUFBTSxDQUFDLEVBQUUsUUFBUSxDQUFDLENBQUM7SUFFeEMsTUFBTSxRQUFRLEdBQUcsWUFBWSxDQUFDLGlCQUFpQixDQUMzQyxDQUFDLENBQUMsS0FBaUQsRUFDbkQsTUFBTSxDQUFDLEtBQWlELEVBQUUsT0FBTyxFQUNqRSxTQUFTLEVBQUUsR0FBRyxDQUFDLENBQUM7SUFFcEIsTUFBTSxFQUNKLFdBQVcsRUFDWCxZQUFZLEVBQ1osV0FBVyxFQUNYLGFBQWEsRUFDYixjQUFjLEVBQ2QsYUFBYSxFQUNiLE9BQU8sRUFDUixHQUFHLFFBQVEsQ0FBQztJQUNiLE1BQU0sUUFBUSxHQUFHLE9BQU8sQ0FBQyxLQUFLLENBQUM7SUFDL0IsTUFBTSxPQUFPLEdBQUcsT0FBTyxDQUFDLElBQUksQ0FBQztJQUM3QixNQUFNLE1BQU0sR0FBRyxPQUFPLENBQUMsR0FBRyxDQUFDO0lBQzNCLE1BQU0sQ0FBQyxHQUFHLElBQUksWUFBWSxDQUFDLFFBQVEsQ0FBQyxRQUFRLEVBQUUsQ0FBQyxDQUFDLEtBQWtCLENBQUMsQ0FBQztJQUVwRSxNQUFNLEtBQUssR0FBRyxPQUFPLENBQUMsSUFBSSxDQUFDLEdBQUcsQ0FBQyxDQUFDLENBQUMsTUFBTSxDQUFDLENBQUMsTUFBb0IsQ0FBQztJQUM5RCxNQUFNLEtBQUssR0FBRyxPQUFPLENBQUMsSUFBSSxDQUFDLEdBQUcsQ0FBQyxNQUFNLENBQUMsTUFBTSxDQUFDLENBQUMsTUFBb0IsQ0FBQztJQUNuRSxNQUFNLEtBQUssR0FBRyxDQUFDLENBQUMsTUFBTSxDQUFDO0lBRXZCLE1BQU0sUUFBUSxHQUFHLElBQUksQ0FBQyxjQUFjLENBQUMsQ0FBQyxDQUFDLEtBQUssQ0FBQyxDQUFDO0lBQzlDLE1BQU0sYUFBYSxHQUFHLElBQUksQ0FBQyxjQUFjLENBQUMsTUFBTSxDQUFDLEtBQUssQ0FBQyxDQUFDO0lBRXhELEtBQUssSUFBSSxDQUFDLEdBQUcsQ0FBQyxFQUFFLENBQUMsR0FBRyxRQUFRLENBQUMsU0FBUyxFQUFFLEVBQUUsQ0FBQyxFQUFFO1FBQzNDLE1BQU0sUUFBUSxHQUFHLENBQUMsR0FBRyxRQUFRLENBQUMsQ0FBQyxDQUFDLENBQUM7UUFDakMsTUFBTSxRQUFRLEdBQUcsQ0FBQyxHQUFHLENBQUMsQ0FBQyxPQUFPLENBQUMsQ0FBQyxDQUFDLENBQUM7UUFDbEMsS0FBSyxJQUFJLEVBQUUsR0FBRyxDQUFDLEVBQUUsRUFBRSxHQUFHLFFBQVEsQ0FBQyxRQUFRLEVBQUUsRUFBRSxFQUFFLEVBQUU7WUFDN0MsTUFBTSxRQUFRLEdBQUcsUUFBUSxHQUFHLEVBQUUsR0FBRyxDQUFDLENBQUMsT0FBTyxDQUFDLENBQUMsQ0FBQyxDQUFDO1lBQzlDLE1BQU0sUUFBUSxHQUFHLEVBQUUsR0FBRyxRQUFRLENBQUMsV0FBVyxHQUFHLFFBQVEsQ0FBQztZQUN0RCxLQUFLLElBQUksRUFBRSxHQUFHLENBQUMsRUFBRSxFQUFFLEdBQUcsV0FBVyxFQUFFLEVBQUUsRUFBRSxFQUFFO2dCQUN2QyxNQUFNLEVBQUUsR0FBRyxRQUFRLEdBQUcsRUFBRSxHQUFHLGFBQWEsQ0FBQztnQkFDekMsSUFBSSxFQUFFLEdBQUcsQ0FBQyxJQUFJLEVBQUUsSUFBSSxRQUFRLENBQUMsT0FBTyxFQUFFO29CQUNwQyxTQUFTO2lCQUNWO2dCQUNELE1BQU0sUUFBUSxHQUFHLEVBQUUsR0FBRyxhQUFhLENBQUMsQ0FBQyxDQUFDLENBQUM7Z0JBQ3ZDLE1BQU0sUUFBUSxHQUFHLFFBQVEsR0FBRyxFQUFFLEdBQUcsUUFBUSxDQUFDLENBQUMsQ0FBQyxDQUFDO2dCQUU3QyxLQUFLLElBQUksRUFBRSxHQUFHLENBQUMsRUFBRSxFQUFFLEdBQUcsUUFBUSxDQUFDLFNBQVMsRUFBRSxFQUFFLEVBQUUsRUFBRTtvQkFDOUMsTUFBTSxRQUFRLEdBQUcsUUFBUSxHQUFHLEVBQUUsR0FBRyxDQUFDLENBQUMsT0FBTyxDQUFDLENBQUMsQ0FBQyxDQUFDO29CQUM5QyxNQUFNLFFBQVEsR0FBRyxFQUFFLEdBQUcsUUFBUSxDQUFDLFlBQVksR0FBRyxNQUFNLENBQUM7b0JBQ3JELEtBQUssSUFBSSxFQUFFLEdBQUcsQ0FBQyxFQUFFLEVBQUUsR0FBRyxZQUFZLEVBQUUsRUFBRSxFQUFFLEVBQUU7d0JBQ3hDLE1BQU0sRUFBRSxHQUFHLFFBQVEsR0FBRyxFQUFFLEdBQUcsY0FBYyxDQUFDO3dCQUMxQyxJQUFJLEVBQUUsR0FBRyxDQUFDLElBQUksRUFBRSxJQUFJLFFBQVEsQ0FBQyxRQUFRLEVBQUU7NEJBQ3JDLFNBQVM7eUJBQ1Y7d0JBQ0QsTUFBTSxRQUFRLEdBQUcsUUFBUSxHQUFHLEVBQUUsR0FBRyxhQUFhLENBQUMsQ0FBQyxDQUFDLENBQUM7d0JBQ2xELE1BQU0sUUFBUSxHQUFHLFFBQVEsR0FBRyxFQUFFLEdBQUcsUUFBUSxDQUFDLENBQUMsQ0FBQyxDQUFDO3dCQUM3QyxLQUFLLElBQUksRUFBRSxHQUFHLENBQUMsRUFBRSxFQUFFLEdBQUcsUUFBUSxDQUFDLFFBQVEsRUFBRSxFQUFFLEVBQUUsRUFBRTs0QkFDN0MsTUFBTSxRQUFRLEdBQUcsUUFBUSxHQUFHLEVBQUUsR0FBRyxRQUFRLENBQUMsV0FBVyxDQUFDOzRCQUN0RCxNQUFNLFFBQVEsR0FBRyxFQUFFLEdBQUcsUUFBUSxDQUFDLFdBQVcsR0FBRyxPQUFPLENBQUM7NEJBQ3JELEtBQUssSUFBSSxFQUFFLEdBQUcsQ0FBQyxFQUFFLEVBQUUsR0FBRyxXQUFXLEVBQUUsRUFBRSxFQUFFLEVBQUU7Z0NBQ3ZDLE1BQU0sRUFBRSxHQUFHLFFBQVEsR0FBRyxFQUFFLEdBQUcsYUFBYSxDQUFDO2dDQUN6QyxJQUFJLEVBQUUsR0FBRyxDQUFDLElBQUksRUFBRSxJQUFJLFFBQVEsQ0FBQyxPQUFPLEVBQUU7b0NBQ3BDLFNBQVM7aUNBQ1Y7Z0NBQ0QsTUFBTSxRQUFRLEdBQUcsUUFBUSxHQUFHLEVBQUUsR0FBRyxhQUFhLENBQUMsQ0FBQyxDQUFDLENBQUM7Z0NBQ2xELE1BQU0sUUFBUSxHQUFHLFFBQVEsR0FBRyxFQUFFLEdBQUcsUUFBUSxDQUFDLFVBQVUsQ0FBQztnQ0FDckQsSUFBSSxRQUFRLEdBQUcsUUFBUSxDQUFDO2dDQUN4QixLQUFLLElBQUksRUFBRSxHQUFHLENBQUMsRUFBRSxFQUFFLEdBQUcsUUFBUSxDQUFDLFVBQVUsRUFBRSxFQUFFLEVBQUUsRUFBRTtvQ0FDL0MsTUFBTSxJQUFJLEdBQUcsS0FBSyxDQUFDLFFBQVEsR0FBRyxFQUFFLENBQUMsQ0FBQztvQ0FDbEMsS0FBSyxJQUFJLEVBQUUsR0FBRyxDQUFDLEVBQUUsRUFBRSxHQUFHLFFBQVEsQ0FBQyxXQUFXLEVBQUUsRUFBRSxFQUFFLEVBQUU7d0NBQ2hELEtBQUssQ0FBQyxRQUFRLEdBQUcsRUFBRSxDQUFDLElBQUksSUFBSSxHQUFHLEtBQUssQ0FBQyxRQUFRLEdBQUcsRUFBRSxDQUFDLENBQUM7cUNBQ3JEO29DQUNELFFBQVEsSUFBSSxRQUFRLENBQUMsV0FBVyxDQUFDO2lDQUNsQzs2QkFDRjt5QkFDRjtxQkFDRjtpQkFDRjthQUNGO1NBQ0Y7S0FDRjtJQUVELE9BQU8sT0FBTyxDQUFDLGNBQWMsQ0FBQyxDQUFDLENBQUMsS0FBSyxFQUFFLENBQUMsQ0FBQyxLQUFLLEVBQUUsQ0FBQyxDQUFDLE1BQU0sQ0FBQyxDQUFDO0FBQzVELENBQUM7QUFFRCxNQUFNLENBQUMsTUFBTSxZQUFZLEdBQWlCO0lBQ3hDLFVBQVUsRUFBRSxNQUFNO0lBQ2xCLFdBQVcsRUFBRSxLQUFLO0lBQ2xCLFVBQVUsRUFBRSxNQUErQjtDQUM1QyxDQUFDIiwic291cmNlc0NvbnRlbnQiOlsiLyoqXG4gKiBAbGljZW5zZVxuICogQ29weXJpZ2h0IDIwMjAgR29vZ2xlIExMQy4gQWxsIFJpZ2h0cyBSZXNlcnZlZC5cbiAqIExpY2Vuc2VkIHVuZGVyIHRoZSBBcGFjaGUgTGljZW5zZSwgVmVyc2lvbiAyLjAgKHRoZSBcIkxpY2Vuc2VcIik7XG4gKiB5b3UgbWF5IG5vdCB1c2UgdGhpcyBmaWxlIGV4Y2VwdCBpbiBjb21wbGlhbmNlIHdpdGggdGhlIExpY2Vuc2UuXG4gKiBZb3UgbWF5IG9idGFpbiBhIGNvcHkgb2YgdGhlIExpY2Vuc2UgYXRcbiAqXG4gKiBodHRwOi8vd3d3LmFwYWNoZS5vcmcvbGljZW5zZXMvTElDRU5TRS0yLjBcbiAqXG4gKiBVbmxlc3MgcmVxdWlyZWQgYnkgYXBwbGljYWJsZSBsYXcgb3IgYWdyZWVkIHRvIGluIHdyaXRpbmcsIHNvZnR3YXJlXG4gKiBkaXN0cmlidXRlZCB1bmRlciB0aGUgTGljZW5zZSBpcyBkaXN0cmlidXRlZCBvbiBhbiBcIkFTIElTXCIgQkFTSVMsXG4gKiBXSVRIT1VUIFdBUlJBTlRJRVMgT1IgQ09ORElUSU9OUyBPRiBBTlkgS0lORCwgZWl0aGVyIGV4cHJlc3Mgb3IgaW1wbGllZC5cbiAqIFNlZSB0aGUgTGljZW5zZSBmb3IgdGhlIHNwZWNpZmljIGxhbmd1YWdlIGdvdmVybmluZyBwZXJtaXNzaW9ucyBhbmRcbiAqIGxpbWl0YXRpb25zIHVuZGVyIHRoZSBMaWNlbnNlLlxuICogPT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT1cbiAqL1xuXG5pbXBvcnQge2JhY2tlbmRfdXRpbCwgQ29udjNELCBDb252M0RBdHRycywgQ29udjNESW5wdXRzLCBLZXJuZWxDb25maWcsIEtlcm5lbEZ1bmMsIFRlbnNvckJ1ZmZlciwgVGVuc29ySW5mbywgVHlwZWRBcnJheSwgdXRpbH0gZnJvbSAnQHRlbnNvcmZsb3cvdGZqcy1jb3JlJztcblxuaW1wb3J0IHtNYXRoQmFja2VuZENQVX0gZnJvbSAnLi4vYmFja2VuZF9jcHUnO1xuaW1wb3J0IHthc3NlcnROb3RDb21wbGV4fSBmcm9tICcuLi9jcHVfdXRpbCc7XG5cbmV4cG9ydCBmdW5jdGlvbiBjb252M0QoXG4gICAgYXJnczoge2lucHV0czogQ29udjNESW5wdXRzLCBiYWNrZW5kOiBNYXRoQmFja2VuZENQVSwgYXR0cnM6IENvbnYzREF0dHJzfSk6XG4gICAgVGVuc29ySW5mbyB7XG4gIGNvbnN0IHtpbnB1dHMsIGJhY2tlbmQsIGF0dHJzfSA9IGFyZ3M7XG4gIGNvbnN0IHt4LCBmaWx0ZXJ9ID0gaW5wdXRzO1xuICBjb25zdCB7c3RyaWRlcywgcGFkLCBkaWxhdGlvbnN9ID0gYXR0cnM7XG5cbiAgYXNzZXJ0Tm90Q29tcGxleChbeCwgZmlsdGVyXSwgJ2NvbnYzZCcpO1xuXG4gIGNvbnN0IGNvbnZJbmZvID0gYmFja2VuZF91dGlsLmNvbXB1dGVDb252M0RJbmZvKFxuICAgICAgeC5zaGFwZSBhcyBbbnVtYmVyLCBudW1iZXIsIG51bWJlciwgbnVtYmVyLCBudW1iZXJdLFxuICAgICAgZmlsdGVyLnNoYXBlIGFzIFtudW1iZXIsIG51bWJlciwgbnVtYmVyLCBudW1iZXIsIG51bWJlcl0sIHN0cmlkZXMsXG4gICAgICBkaWxhdGlvbnMsIHBhZCk7XG5cbiAgY29uc3Qge1xuICAgIGZpbHRlckRlcHRoLFxuICAgIGZpbHRlckhlaWdodCxcbiAgICBmaWx0ZXJXaWR0aCxcbiAgICBkaWxhdGlvbkRlcHRoLFxuICAgIGRpbGF0aW9uSGVpZ2h0LFxuICAgIGRpbGF0aW9uV2lkdGgsXG4gICAgcGFkSW5mb1xuICB9ID0gY29udkluZm87XG4gIGNvbnN0IHBhZEZyb250ID0gcGFkSW5mby5mcm9udDtcbiAgY29uc3QgcGFkTGVmdCA9IHBhZEluZm8ubGVmdDtcbiAgY29uc3QgcGFkVG9wID0gcGFkSW5mby50b3A7XG4gIGNvbnN0IHkgPSBuZXcgVGVuc29yQnVmZmVyKGNvbnZJbmZvLm91dFNoYXBlLCB4LmR0eXBlIGFzICdmbG9hdDMyJyk7XG5cbiAgY29uc3QgeFZhbHMgPSBiYWNrZW5kLmRhdGEuZ2V0KHguZGF0YUlkKS52YWx1ZXMgYXMgVHlwZWRBcnJheTtcbiAgY29uc3Qgd1ZhbHMgPSBiYWNrZW5kLmRhdGEuZ2V0KGZpbHRlci5kYXRhSWQpLnZhbHVlcyBhcyBUeXBlZEFycmF5O1xuICBjb25zdCB5VmFscyA9IHkudmFsdWVzO1xuXG4gIGNvbnN0IHhTdHJpZGVzID0gdXRpbC5jb21wdXRlU3RyaWRlcyh4LnNoYXBlKTtcbiAgY29uc3QgZmlsdGVyU3RyaWRlcyA9IHV0aWwuY29tcHV0ZVN0cmlkZXMoZmlsdGVyLnNoYXBlKTtcblxuICBmb3IgKGxldCBiID0gMDsgYiA8IGNvbnZJbmZvLmJhdGNoU2l6ZTsgKytiKSB7XG4gICAgY29uc3QgeE9mZnNldDEgPSBiICogeFN0cmlkZXNbMF07XG4gICAgY29uc3QgeU9mZnNldDEgPSBiICogeS5zdHJpZGVzWzBdO1xuICAgIGZvciAobGV0IHlGID0gMDsgeUYgPCBjb252SW5mby5vdXREZXB0aDsgKyt5Rikge1xuICAgICAgY29uc3QgeU9mZnNldDIgPSB5T2Zmc2V0MSArIHlGICogeS5zdHJpZGVzWzFdO1xuICAgICAgY29uc3QgeEZDb3JuZXIgPSB5RiAqIGNvbnZJbmZvLnN0cmlkZURlcHRoIC0gcGFkRnJvbnQ7XG4gICAgICBmb3IgKGxldCB3RiA9IDA7IHdGIDwgZmlsdGVyRGVwdGg7ICsrd0YpIHtcbiAgICAgICAgY29uc3QgeEYgPSB4RkNvcm5lciArIHdGICogZGlsYXRpb25EZXB0aDtcbiAgICAgICAgaWYgKHhGIDwgMCB8fCB4RiA+PSBjb252SW5mby5pbkRlcHRoKSB7XG4gICAgICAgICAgY29udGludWU7XG4gICAgICAgIH1cbiAgICAgICAgY29uc3Qgd09mZnNldDEgPSB3RiAqIGZpbHRlclN0cmlkZXNbMF07XG4gICAgICAgIGNvbnN0IHhPZmZzZXQyID0geE9mZnNldDEgKyB4RiAqIHhTdHJpZGVzWzFdO1xuXG4gICAgICAgIGZvciAobGV0IHlSID0gMDsgeVIgPCBjb252SW5mby5vdXRIZWlnaHQ7ICsreVIpIHtcbiAgICAgICAgICBjb25zdCB5T2Zmc2V0MyA9IHlPZmZzZXQyICsgeVIgKiB5LnN0cmlkZXNbMl07XG4gICAgICAgICAgY29uc3QgeFJDb3JuZXIgPSB5UiAqIGNvbnZJbmZvLnN0cmlkZUhlaWdodCAtIHBhZFRvcDtcbiAgICAgICAgICBmb3IgKGxldCB3UiA9IDA7IHdSIDwgZmlsdGVySGVpZ2h0OyArK3dSKSB7XG4gICAgICAgICAgICBjb25zdCB4UiA9IHhSQ29ybmVyICsgd1IgKiBkaWxhdGlvbkhlaWdodDtcbiAgICAgICAgICAgIGlmICh4UiA8IDAgfHwgeFIgPj0gY29udkluZm8uaW5IZWlnaHQpIHtcbiAgICAgICAgICAgICAgY29udGludWU7XG4gICAgICAgICAgICB9XG4gICAgICAgICAgICBjb25zdCB3T2Zmc2V0MiA9IHdPZmZzZXQxICsgd1IgKiBmaWx0ZXJTdHJpZGVzWzFdO1xuICAgICAgICAgICAgY29uc3QgeE9mZnNldDMgPSB4T2Zmc2V0MiArIHhSICogeFN0cmlkZXNbMl07XG4gICAgICAgICAgICBmb3IgKGxldCB5QyA9IDA7IHlDIDwgY29udkluZm8ub3V0V2lkdGg7ICsreUMpIHtcbiAgICAgICAgICAgICAgY29uc3QgeU9mZnNldDQgPSB5T2Zmc2V0MyArIHlDICogY29udkluZm8ub3V0Q2hhbm5lbHM7XG4gICAgICAgICAgICAgIGNvbnN0IHhDQ29ybmVyID0geUMgKiBjb252SW5mby5zdHJpZGVXaWR0aCAtIHBhZExlZnQ7XG4gICAgICAgICAgICAgIGZvciAobGV0IHdDID0gMDsgd0MgPCBmaWx0ZXJXaWR0aDsgKyt3Qykge1xuICAgICAgICAgICAgICAgIGNvbnN0IHhDID0geENDb3JuZXIgKyB3QyAqIGRpbGF0aW9uV2lkdGg7XG4gICAgICAgICAgICAgICAgaWYgKHhDIDwgMCB8fCB4QyA+PSBjb252SW5mby5pbldpZHRoKSB7XG4gICAgICAgICAgICAgICAgICBjb250aW51ZTtcbiAgICAgICAgICAgICAgICB9XG4gICAgICAgICAgICAgICAgY29uc3Qgd09mZnNldDMgPSB3T2Zmc2V0MiArIHdDICogZmlsdGVyU3RyaWRlc1syXTtcbiAgICAgICAgICAgICAgICBjb25zdCB4T2Zmc2V0NCA9IHhPZmZzZXQzICsgeEMgKiBjb252SW5mby5pbkNoYW5uZWxzO1xuICAgICAgICAgICAgICAgIGxldCB3T2Zmc2V0NCA9IHdPZmZzZXQzO1xuICAgICAgICAgICAgICAgIGZvciAobGV0IGQxID0gMDsgZDEgPCBjb252SW5mby5pbkNoYW5uZWxzOyArK2QxKSB7XG4gICAgICAgICAgICAgICAgICBjb25zdCB4VmFsID0geFZhbHNbeE9mZnNldDQgKyBkMV07XG4gICAgICAgICAgICAgICAgICBmb3IgKGxldCBkMiA9IDA7IGQyIDwgY29udkluZm8ub3V0Q2hhbm5lbHM7ICsrZDIpIHtcbiAgICAgICAgICAgICAgICAgICAgeVZhbHNbeU9mZnNldDQgKyBkMl0gKz0geFZhbCAqIHdWYWxzW3dPZmZzZXQ0ICsgZDJdO1xuICAgICAgICAgICAgICAgICAgfVxuICAgICAgICAgICAgICAgICAgd09mZnNldDQgKz0gY29udkluZm8ub3V0Q2hhbm5lbHM7XG4gICAgICAgICAgICAgICAgfVxuICAgICAgICAgICAgICB9XG4gICAgICAgICAgICB9XG4gICAgICAgICAgfVxuICAgICAgICB9XG4gICAgICB9XG4gICAgfVxuICB9XG5cbiAgcmV0dXJuIGJhY2tlbmQubWFrZVRlbnNvckluZm8oeS5zaGFwZSwgeS5kdHlwZSwgeS52YWx1ZXMpO1xufVxuXG5leHBvcnQgY29uc3QgY29udjNEQ29uZmlnOiBLZXJuZWxDb25maWcgPSB7XG4gIGtlcm5lbE5hbWU6IENvbnYzRCxcbiAgYmFja2VuZE5hbWU6ICdjcHUnLFxuICBrZXJuZWxGdW5jOiBjb252M0QgYXMgdW5rbm93biBhcyBLZXJuZWxGdW5jXG59O1xuIl19