From eded0255b409bfebeece76afdb65f03182ffff3c Mon Sep 17 00:00:00 2001 From: Ian Romanick Date: Tue, 7 Jul 2009 16:22:25 -0700 Subject: [PATCH] glsl: Replace noise opcodes with a GLSL noise implementation No hardware has a noise opcode, so don't try to pretend otherwise. Instead use a reasonable GLSL based implementation. Currently this code works as-is on i965 for simple demos. However, fully implementing noise4 results in overflowing the register set. I suspect the compiler to too aggressivly inlining noise1 function calls. --- .../shader/slang/library/slang_common_builtin.gc | 186 ++++++++++++++++++-- .../shader/slang/library/slang_common_builtin_gc.h | 183 ++++++++++++------- 2 files changed, 285 insertions(+), 84 deletions(-) diff --git a/src/mesa/shader/slang/library/slang_common_builtin.gc b/src/mesa/shader/slang/library/slang_common_builtin.gc index 9764fc2..fe9989f 100644 --- a/src/mesa/shader/slang/library/slang_common_builtin.gc +++ b/src/mesa/shader/slang/library/slang_common_builtin.gc @@ -1764,28 +1764,166 @@ vec4 shadow2DRectProj(const sampler2DRectShadow sampler, const vec4 coord) // // 8.9 Noise Functions // -// AUTHOR: Stefan Gustavson (stegu@itn.liu.se), Nov 26, 2005 +// Implementation of Marc Olano's modified noise function. +// +// Fairly straight-forward implementation of the modified noise algorithm +// described in: +// +// Olano, Marc. "Modified Noise for Evaluation on Graphics Hardware". +// Proceedings of Graphics Hardware 2005, Eurographics/ACM SIGGRAPH, +// July 2005. +// +// The implementations of noise[234] could be vastly improved. Vectorizing +// the calculations instead of making multiple independent inoise1 calls +// should give a healthy speed-up in that code. I did not implement this +// because I believe that noise[234] are called much less frequently than +// noise1. Patches and evidence to the contrary are always welcome. +// +// AUTHOR: Ian Romanick // -float noise1(const float x) +/** + * Smooth transition with a 5th degree polynomial + * + * This function is much like the existing \c smoothstep function. Instead + * of using a 3rd degree polynomial, it uses the following 5th degree + * polynomial: + * + * s = 6t^5 - 15t^4 + 10t^3 + * + * This is the same smooth step function used by Perlin's improved noise + * function. See: + * + * Perlin, K. 2002. Improving noise. In Proceedings of the 29th Annual + * Conference on Computer Graphics and interactive Techniques + * (San Antonio, Texas, July 23 - 26, 2002). SIGGRAPH '02. ACM, + * New York, NY, 681-682. http://mrl.nyu.edu/~perlin/paper445.pdf + */ +vec2 smoothstep5(const vec2 t) +{ + return t * t * t * (t * (t * 6.0 - 15.0) + 10.0); +} + +float smoothstep5(const float t) { - __asm float_noise1 __retVal, x; + return t * t * t * (t * (t * 6.0 - 15.0) + 10.0); } +vec2 perm2(const float x) +{ + vec2 v = vec2(x, x + 1.0); + v = (3.0 * v) + 3.0; + return mod(v * v, 61.0); +} + +vec4 perm4(const vec2 x) +{ + vec4 v = vec4(x.x, x.x + 1.0, x.y, x.y + 1.0); + v = (3.0 * v) + 3.0; + return mod(v * v, 61.0); +} + +/** + * Vectorized 1-dimensional gradient function + * + * \return + * The output X component is \c p.x if \c x.x is even or \c -p.x if \c x.x + * is odd. The output Y component is set similarly but uses \c p.y and + * \c x.y. + */ +vec2 grad(const vec2 x, const vec2 p) +{ + /* floor(x) is... even odd + * previous % 2.0 0.0 1.0 + * 2.0 * previous 0.0 2.0 + * 1.0 - previous 1.0 -1.0 + */ + return p * (1.0 - (2.0 * mod(floor(x), 2.0))); +} + +/** + * Vectorized 2-dimensional gradient function + * + * Similar to the 1-dimensional gradient function except Y components are + * based on the parity of \c x.y / 2.0. + */ +vec2 grad(const vec2 x, const vec2 p1, const vec2 p2) +{ + const vec4 x2 = x.xxyy * vec4(1.0, 0.5, 1.0, 0.5); + const vec4 grad_val = (1.0 - (2.0 * mod(floor(x2), 2.0))); + + return vec2(dot(grad_val.xy, p1), dot(grad_val.zw, p2)); +} + +float noise1_basis(const float p, const vec2 v) +{ + const float f = smoothstep5(fract(p)); + const vec2 A = perm2(floor(p)); + const vec2 g = grad(A, v); + + return mix(g.x, g.y, f); +} + +vec2 noise1_basis(const float p, const vec4 v) +{ + const float f = smoothstep5(fract(p)); + const vec2 A = perm2(floor(p)); + const vec4 g = vec4(grad(A, v.xy), grad(A, v.zw)); + + return mix(g.xz, g.yw, f); +} + +float noise1(const float x) +{ + const float frcP = fract(x); + const vec2 v = vec2(frcP, frcP + 1.0); + const float f = smoothstep5(frcP); + const vec2 A = perm2(floor(x)); + const vec2 g = grad(A, v); + + return mix(g.x, g.y, f); +} float noise1(const vec2 x) { - __asm float_noise2 __retVal, x; + const vec2 bias = vec2(0.0, -1.0); + const vec2 intP = floor(x); + const vec2 frcP = fract(x); + const vec2 f = smoothstep5(frcP); + const vec2 A = perm2(intP.x) + intP.y; + const vec4 AA = perm4(A); + + const vec4 g = vec4(grad(AA.xz, frcP , frcP + bias.yx), + grad(AA.yw, frcP + bias.xy, frcP + bias.yy)); + const vec4 fv = vec2(f.x, 1.0 - f.x).yxyx * vec2(f.y, 1.0 - f.y).yyxx; + + return dot(g, fv); } float noise1(const vec3 x) { - __asm float_noise3 __retVal, x; + vec2 pp = perm2(floor(x.z)) + x.y; + + return noise1_basis(x.z, + vec2(noise1(vec2(x.x, pp.x)), + noise1(vec2(x.x, pp.y)))); } float noise1(const vec4 x) { - __asm float_noise4 __retVal, x; + const float intW = floor(x.w); + const vec2 pp = perm2(intW); + + const vec2 q = pp + x.zz; + const vec2 intZ = floor(q); + vec4 qq = perm4(intZ) + x.yyyy; + + qq.x = noise1(vec2(x.x, qq.x)); + qq.y = noise1(vec2(x.x, qq.y)); + qq.z = noise1(vec2(x.x, qq.z)); + qq.w = noise1(vec2(x.x, qq.w)); + + return noise1_basis(x.w, noise1_basis(q.x, qq)); } vec2 noise2(const float x) @@ -1816,58 +1954,70 @@ vec3 noise3(const float x) { __retVal.x = noise1(x); __retVal.y = noise1(x + 19.34); - __retVal.z = noise1(x + 5.47); + //__retVal.z = noise1(x + 5.47); + __retVal.z = __retVal.x; } vec3 noise3(const vec2 x) { __retVal.x = noise1(x); __retVal.y = noise1(x + vec2(19.34, 7.66)); - __retVal.z = noise1(x + vec2(5.47, 17.85)); + //__retVal.z = noise1(x + vec2(5.47, 17.85)); + __retVal.z = __retVal.x; } vec3 noise3(const vec3 x) { __retVal.x = noise1(x); __retVal.y = noise1(x + vec3(19.34, 7.66, 3.23)); - __retVal.z = noise1(x + vec3(5.47, 17.85, 11.04)); + //__retVal.z = noise1(x + vec3(5.47, 17.85, 11.04)); + __retVal.z = __retVal.x; } vec3 noise3(const vec4 x) { __retVal.x = noise1(x); __retVal.y = noise1(x + vec4(19.34, 7.66, 3.23, 2.77)); - __retVal.z = noise1(x + vec4(5.47, 17.85, 11.04, 13.19)); + //__retVal.z = noise1(x + vec4(5.47, 17.85, 11.04, 13.19)); + __retVal.z = __retVal.x; } vec4 noise4(const float x) { __retVal.x = noise1(x); __retVal.y = noise1(x + 19.34); - __retVal.z = noise1(x + 5.47); - __retVal.w = noise1(x + 23.54); + //__retVal.z = noise1(x + 5.47); + //__retVal.w = noise1(x + 23.54); + __retVal.z = __retVal.x; + __retVal.w = __retVal.y; } vec4 noise4(const vec2 x) { __retVal.x = noise1(x); __retVal.y = noise1(x + vec2 (19.34, 7.66)); - __retVal.z = noise1(x + vec2 (5.47, 17.85)); - __retVal.w = noise1(x + vec2 (23.54, 29.11)); + //__retVal.z = noise1(x + vec2 (5.47, 17.85)); + //__retVal.w = noise1(x + vec2 (23.54, 29.11)); + __retVal.z = __retVal.x; + __retVal.w = __retVal.y; } vec4 noise4(const vec3 x) { __retVal.x = noise1(x); __retVal.y = noise1(x + vec3(19.34, 7.66, 3.23)); - __retVal.z = noise1(x + vec3(5.47, 17.85, 11.04)); - __retVal.w = noise1(x + vec3(23.54, 29.11, 31.91)); + //__retVal.z = noise1(x + vec3(5.47, 17.85, 11.04)); + //__retVal.w = noise1(x + vec3(23.54, 29.11, 31.91)); + __retVal.z = __retVal.x; + __retVal.w = __retVal.y; } vec4 noise4(const vec4 x) { __retVal.x = noise1(x); __retVal.y = noise1(x + vec4(19.34, 7.66, 3.23, 2.77)); - __retVal.z = noise1(x + vec4(5.47, 17.85, 11.04, 13.19)); - __retVal.w = noise1(x + vec4(23.54, 29.11, 31.91, 37.48)); + //__retVal.z = noise1(x + vec4(5.47, 17.85, 11.04, 13.19)); + //__retVal.w = noise1(x + vec4(23.54, 29.11, 31.91, 37.48)); + __retVal.z = __retVal.x; + __retVal.w = __retVal.y; } diff --git a/src/mesa/shader/slang/library/slang_common_builtin_gc.h b/src/mesa/shader/slang/library/slang_common_builtin_gc.h index 78a7b83..6f7015b 100644 --- a/src/mesa/shader/slang/library/slang_common_builtin_gc.h +++ b/src/mesa/shader/slang/library/slang_common_builtin_gc.h @@ -801,72 +801,123 @@ 0,115,104,97,100,111,119,50,68,82,101,99,116,80,114,111,106,0,1,1,0,0,23,0,115,97,109,112,108,101, 114,0,0,1,1,0,0,12,0,99,111,111,114,100,0,0,0,1,4,118,101,99,52,95,116,101,120,95,114,101,99,116, 95,112,114,111,106,95,115,104,97,100,111,119,0,18,95,95,114,101,116,86,97,108,0,0,18,115,97,109, -112,108,101,114,0,0,18,99,111,111,114,100,0,0,0,0,1,90,95,0,0,9,0,0,110,111,105,115,101,49,0,1,1,0, -0,9,0,120,0,0,0,1,4,102,108,111,97,116,95,110,111,105,115,101,49,0,18,95,95,114,101,116,86,97,108, -0,0,18,120,0,0,0,0,1,90,95,0,0,9,0,0,110,111,105,115,101,49,0,1,1,0,0,10,0,120,0,0,0,1,4,102,108, -111,97,116,95,110,111,105,115,101,50,0,18,95,95,114,101,116,86,97,108,0,0,18,120,0,0,0,0,1,90,95,0, -0,9,0,0,110,111,105,115,101,49,0,1,1,0,0,11,0,120,0,0,0,1,4,102,108,111,97,116,95,110,111,105,115, -101,51,0,18,95,95,114,101,116,86,97,108,0,0,18,120,0,0,0,0,1,90,95,0,0,9,0,0,110,111,105,115,101, -49,0,1,1,0,0,12,0,120,0,0,0,1,4,102,108,111,97,116,95,110,111,105,115,101,52,0,18,95,95,114,101, -116,86,97,108,0,0,18,120,0,0,0,0,1,90,95,0,0,10,0,0,110,111,105,115,101,50,0,1,1,0,0,9,0,120,0,0,0, -1,9,18,95,95,114,101,116,86,97,108,0,59,120,0,58,110,111,105,115,101,49,0,0,18,120,0,0,0,20,0,9,18, -95,95,114,101,116,86,97,108,0,59,121,0,58,110,111,105,115,101,49,0,0,18,120,0,17,49,57,0,51,52,0,0, -46,0,0,20,0,0,1,90,95,0,0,10,0,0,110,111,105,115,101,50,0,1,1,0,0,10,0,120,0,0,0,1,9,18,95,95,114, -101,116,86,97,108,0,59,120,0,58,110,111,105,115,101,49,0,0,18,120,0,0,0,20,0,9,18,95,95,114,101, -116,86,97,108,0,59,121,0,58,110,111,105,115,101,49,0,0,18,120,0,58,118,101,99,50,0,0,17,49,57,0,51, -52,0,0,0,17,55,0,54,54,0,0,0,0,46,0,0,20,0,0,1,90,95,0,0,10,0,0,110,111,105,115,101,50,0,1,1,0,0, -11,0,120,0,0,0,1,9,18,95,95,114,101,116,86,97,108,0,59,120,0,58,110,111,105,115,101,49,0,0,18,120, -0,0,0,20,0,9,18,95,95,114,101,116,86,97,108,0,59,121,0,58,110,111,105,115,101,49,0,0,18,120,0,58, -118,101,99,51,0,0,17,49,57,0,51,52,0,0,0,17,55,0,54,54,0,0,0,17,51,0,50,51,0,0,0,0,46,0,0,20,0,0,1, -90,95,0,0,10,0,0,110,111,105,115,101,50,0,1,1,0,0,12,0,120,0,0,0,1,9,18,95,95,114,101,116,86,97, -108,0,59,120,0,58,110,111,105,115,101,49,0,0,18,120,0,0,0,20,0,9,18,95,95,114,101,116,86,97,108,0, -59,121,0,58,110,111,105,115,101,49,0,0,18,120,0,58,118,101,99,52,0,0,17,49,57,0,51,52,0,0,0,17,55, -0,54,54,0,0,0,17,51,0,50,51,0,0,0,17,50,0,55,55,0,0,0,0,46,0,0,20,0,0,1,90,95,0,0,11,0,0,110,111, -105,115,101,51,0,1,1,0,0,9,0,120,0,0,0,1,9,18,95,95,114,101,116,86,97,108,0,59,120,0,58,110,111, +112,108,101,114,0,0,18,99,111,111,114,100,0,0,0,0,1,90,95,0,0,10,0,0,115,109,111,111,116,104,115, +116,101,112,53,0,1,1,0,0,10,0,116,0,0,0,1,8,18,116,0,18,116,0,48,18,116,0,48,18,116,0,18,116,0,17, +54,0,48,0,0,48,17,49,53,0,48,0,0,47,48,17,49,48,0,48,0,0,46,48,0,0,1,90,95,0,0,9,0,0,115,109,111, +111,116,104,115,116,101,112,53,0,1,1,0,0,9,0,116,0,0,0,1,8,18,116,0,18,116,0,48,18,116,0,48,18,116, +0,18,116,0,17,54,0,48,0,0,48,17,49,53,0,48,0,0,47,48,17,49,48,0,48,0,0,46,48,0,0,1,90,95,0,0,10,0, +0,112,101,114,109,50,0,1,1,0,0,9,0,120,0,0,0,1,3,2,90,95,0,0,10,0,1,118,0,2,58,118,101,99,50,0,0, +18,120,0,0,18,120,0,17,49,0,48,0,0,46,0,0,0,0,9,18,118,0,17,51,0,48,0,0,18,118,0,48,17,51,0,48,0,0, +46,20,0,8,58,109,111,100,0,0,18,118,0,18,118,0,48,0,17,54,49,0,48,0,0,0,0,0,0,1,90,95,0,0,12,0,0, +112,101,114,109,52,0,1,1,0,0,10,0,120,0,0,0,1,3,2,90,95,0,0,12,0,1,118,0,2,58,118,101,99,52,0,0,18, +120,0,59,120,0,0,18,120,0,59,120,0,17,49,0,48,0,0,46,0,18,120,0,59,121,0,0,18,120,0,59,121,0,17,49, +0,48,0,0,46,0,0,0,0,9,18,118,0,17,51,0,48,0,0,18,118,0,48,17,51,0,48,0,0,46,20,0,8,58,109,111,100, +0,0,18,118,0,18,118,0,48,0,17,54,49,0,48,0,0,0,0,0,0,1,90,95,0,0,10,0,0,103,114,97,100,0,1,1,0,0, +10,0,120,0,0,1,1,0,0,10,0,112,0,0,0,1,8,18,112,0,17,49,0,48,0,0,17,50,0,48,0,0,58,109,111,100,0,0, +58,102,108,111,111,114,0,0,18,120,0,0,0,0,17,50,0,48,0,0,0,0,48,47,48,0,0,1,90,95,0,0,10,0,0,103, +114,97,100,0,1,1,0,0,10,0,120,0,0,1,1,0,0,10,0,112,49,0,0,1,1,0,0,10,0,112,50,0,0,0,1,3,2,90,95,1, +0,12,0,1,120,50,0,2,18,120,0,59,120,120,121,121,0,58,118,101,99,52,0,0,17,49,0,48,0,0,0,17,48,0,53, +0,0,0,17,49,0,48,0,0,0,17,48,0,53,0,0,0,0,48,0,0,3,2,90,95,1,0,12,0,1,103,114,97,100,95,118,97,108, +0,2,17,49,0,48,0,0,17,50,0,48,0,0,58,109,111,100,0,0,58,102,108,111,111,114,0,0,18,120,50,0,0,0,0, +17,50,0,48,0,0,0,0,48,47,0,0,8,58,118,101,99,50,0,0,58,100,111,116,0,0,18,103,114,97,100,95,118,97, +108,0,59,120,121,0,0,18,112,49,0,0,0,0,58,100,111,116,0,0,18,103,114,97,100,95,118,97,108,0,59,122, +119,0,0,18,112,50,0,0,0,0,0,0,0,1,90,95,0,0,9,0,0,110,111,105,115,101,49,95,98,97,115,105,115,0,1, +1,0,0,9,0,112,0,0,1,1,0,0,10,0,118,0,0,0,1,3,2,90,95,1,0,9,0,1,102,0,2,58,115,109,111,111,116,104, +115,116,101,112,53,0,0,58,102,114,97,99,116,0,0,18,112,0,0,0,0,0,0,0,3,2,90,95,1,0,10,0,1,65,0,2, +58,112,101,114,109,50,0,0,58,102,108,111,111,114,0,0,18,112,0,0,0,0,0,0,0,3,2,90,95,1,0,10,0,1,103, +0,2,58,103,114,97,100,0,0,18,65,0,0,18,118,0,0,0,0,0,8,58,109,105,120,0,0,18,103,0,59,120,0,0,18, +103,0,59,121,0,0,18,102,0,0,0,0,0,1,90,95,0,0,10,0,0,110,111,105,115,101,49,95,98,97,115,105,115,0, +1,1,0,0,9,0,112,0,0,1,1,0,0,12,0,118,0,0,0,1,3,2,90,95,1,0,9,0,1,102,0,2,58,115,109,111,111,116, +104,115,116,101,112,53,0,0,58,102,114,97,99,116,0,0,18,112,0,0,0,0,0,0,0,3,2,90,95,1,0,10,0,1,65,0, +2,58,112,101,114,109,50,0,0,58,102,108,111,111,114,0,0,18,112,0,0,0,0,0,0,0,3,2,90,95,1,0,12,0,1, +103,0,2,58,118,101,99,52,0,0,58,103,114,97,100,0,0,18,65,0,0,18,118,0,59,120,121,0,0,0,0,58,103, +114,97,100,0,0,18,65,0,0,18,118,0,59,122,119,0,0,0,0,0,0,0,8,58,109,105,120,0,0,18,103,0,59,120, +122,0,0,18,103,0,59,121,119,0,0,18,102,0,0,0,0,0,1,90,95,0,0,9,0,0,110,111,105,115,101,49,0,1,1,0, +0,9,0,120,0,0,0,1,3,2,90,95,1,0,9,0,1,102,114,99,80,0,2,58,102,114,97,99,116,0,0,18,120,0,0,0,0,0, +3,2,90,95,1,0,10,0,1,118,0,2,58,118,101,99,50,0,0,18,102,114,99,80,0,0,18,102,114,99,80,0,17,49,0, +48,0,0,46,0,0,0,0,3,2,90,95,1,0,9,0,1,102,0,2,58,115,109,111,111,116,104,115,116,101,112,53,0,0,18, +102,114,99,80,0,0,0,0,0,3,2,90,95,1,0,10,0,1,65,0,2,58,112,101,114,109,50,0,0,58,102,108,111,111, +114,0,0,18,120,0,0,0,0,0,0,0,3,2,90,95,1,0,10,0,1,103,0,2,58,103,114,97,100,0,0,18,65,0,0,18,118,0, +0,0,0,0,8,58,109,105,120,0,0,18,103,0,59,120,0,0,18,103,0,59,121,0,0,18,102,0,0,0,0,0,1,90,95,0,0, +9,0,0,110,111,105,115,101,49,0,1,1,0,0,10,0,120,0,0,0,1,3,2,90,95,1,0,10,0,1,98,105,97,115,0,2,58, +118,101,99,50,0,0,17,48,0,48,0,0,0,17,49,0,48,0,0,54,0,0,0,0,3,2,90,95,1,0,10,0,1,105,110,116,80,0, +2,58,102,108,111,111,114,0,0,18,120,0,0,0,0,0,3,2,90,95,1,0,10,0,1,102,114,99,80,0,2,58,102,114,97, +99,116,0,0,18,120,0,0,0,0,0,3,2,90,95,1,0,10,0,1,102,0,2,58,115,109,111,111,116,104,115,116,101, +112,53,0,0,18,102,114,99,80,0,0,0,0,0,3,2,90,95,1,0,10,0,1,65,0,2,58,112,101,114,109,50,0,0,18,105, +110,116,80,0,59,120,0,0,0,18,105,110,116,80,0,59,121,0,46,0,0,3,2,90,95,1,0,12,0,1,65,65,0,2,58, +112,101,114,109,52,0,0,18,65,0,0,0,0,0,3,2,90,95,1,0,12,0,1,103,0,2,58,118,101,99,52,0,0,58,103, +114,97,100,0,0,18,65,65,0,59,120,122,0,0,18,102,114,99,80,0,0,18,102,114,99,80,0,18,98,105,97,115, +0,59,121,120,0,46,0,0,0,58,103,114,97,100,0,0,18,65,65,0,59,121,119,0,0,18,102,114,99,80,0,18,98, +105,97,115,0,59,120,121,0,46,0,18,102,114,99,80,0,18,98,105,97,115,0,59,121,121,0,46,0,0,0,0,0,0,3, +2,90,95,1,0,12,0,1,102,118,0,2,58,118,101,99,50,0,0,18,102,0,59,120,0,0,17,49,0,48,0,0,18,102,0,59, +120,0,47,0,0,59,121,120,121,120,0,58,118,101,99,50,0,0,18,102,0,59,121,0,0,17,49,0,48,0,0,18,102,0, +59,121,0,47,0,0,59,121,121,120,120,0,48,0,0,8,58,100,111,116,0,0,18,103,0,0,18,102,118,0,0,0,0,0,1, +90,95,0,0,9,0,0,110,111,105,115,101,49,0,1,1,0,0,11,0,120,0,0,0,1,3,2,90,95,0,0,10,0,1,112,112,0,2, +58,112,101,114,109,50,0,0,58,102,108,111,111,114,0,0,18,120,0,59,122,0,0,0,0,0,18,120,0,59,121,0, +46,0,0,8,58,110,111,105,115,101,49,95,98,97,115,105,115,0,0,18,120,0,59,122,0,0,58,118,101,99,50,0, +0,58,110,111,105,115,101,49,0,0,58,118,101,99,50,0,0,18,120,0,59,120,0,0,18,112,112,0,59,120,0,0,0, +0,0,0,58,110,111,105,115,101,49,0,0,58,118,101,99,50,0,0,18,120,0,59,120,0,0,18,112,112,0,59,121,0, +0,0,0,0,0,0,0,0,0,0,1,90,95,0,0,9,0,0,110,111,105,115,101,49,0,1,1,0,0,12,0,120,0,0,0,1,3,2,90,95, +1,0,9,0,1,105,110,116,87,0,2,58,102,108,111,111,114,0,0,18,120,0,59,119,0,0,0,0,0,3,2,90,95,1,0,10, +0,1,112,112,0,2,58,112,101,114,109,50,0,0,18,105,110,116,87,0,0,0,0,0,3,2,90,95,1,0,10,0,1,113,0,2, +18,112,112,0,18,120,0,59,122,122,0,46,0,0,3,2,90,95,1,0,10,0,1,105,110,116,90,0,2,58,102,108,111, +111,114,0,0,18,113,0,0,0,0,0,3,2,90,95,0,0,12,0,1,113,113,0,2,58,112,101,114,109,52,0,0,18,105,110, +116,90,0,0,0,18,120,0,59,121,121,121,121,0,46,0,0,9,18,113,113,0,59,120,0,58,110,111,105,115,101, +49,0,0,58,118,101,99,50,0,0,18,120,0,59,120,0,0,18,113,113,0,59,120,0,0,0,0,0,20,0,9,18,113,113,0, +59,121,0,58,110,111,105,115,101,49,0,0,58,118,101,99,50,0,0,18,120,0,59,120,0,0,18,113,113,0,59, +121,0,0,0,0,0,20,0,9,18,113,113,0,59,122,0,58,110,111,105,115,101,49,0,0,58,118,101,99,50,0,0,18, +120,0,59,120,0,0,18,113,113,0,59,122,0,0,0,0,0,20,0,9,18,113,113,0,59,119,0,58,110,111,105,115,101, +49,0,0,58,118,101,99,50,0,0,18,120,0,59,120,0,0,18,113,113,0,59,119,0,0,0,0,0,20,0,8,58,110,111, +105,115,101,49,95,98,97,115,105,115,0,0,18,120,0,59,119,0,0,58,110,111,105,115,101,49,95,98,97,115, +105,115,0,0,18,113,0,59,120,0,0,18,113,113,0,0,0,0,0,0,0,1,90,95,0,0,10,0,0,110,111,105,115,101,50, +0,1,1,0,0,9,0,120,0,0,0,1,9,18,95,95,114,101,116,86,97,108,0,59,120,0,58,110,111,105,115,101,49,0, +0,18,120,0,0,0,20,0,9,18,95,95,114,101,116,86,97,108,0,59,121,0,58,110,111,105,115,101,49,0,0,18, +120,0,17,49,57,0,51,52,0,0,46,0,0,20,0,0,1,90,95,0,0,10,0,0,110,111,105,115,101,50,0,1,1,0,0,10,0, +120,0,0,0,1,9,18,95,95,114,101,116,86,97,108,0,59,120,0,58,110,111,105,115,101,49,0,0,18,120,0,0,0, +20,0,9,18,95,95,114,101,116,86,97,108,0,59,121,0,58,110,111,105,115,101,49,0,0,18,120,0,58,118,101, +99,50,0,0,17,49,57,0,51,52,0,0,0,17,55,0,54,54,0,0,0,0,46,0,0,20,0,0,1,90,95,0,0,10,0,0,110,111, +105,115,101,50,0,1,1,0,0,11,0,120,0,0,0,1,9,18,95,95,114,101,116,86,97,108,0,59,120,0,58,110,111, +105,115,101,49,0,0,18,120,0,0,0,20,0,9,18,95,95,114,101,116,86,97,108,0,59,121,0,58,110,111,105, +115,101,49,0,0,18,120,0,58,118,101,99,51,0,0,17,49,57,0,51,52,0,0,0,17,55,0,54,54,0,0,0,17,51,0,50, +51,0,0,0,0,46,0,0,20,0,0,1,90,95,0,0,10,0,0,110,111,105,115,101,50,0,1,1,0,0,12,0,120,0,0,0,1,9,18, +95,95,114,101,116,86,97,108,0,59,120,0,58,110,111,105,115,101,49,0,0,18,120,0,0,0,20,0,9,18,95,95, +114,101,116,86,97,108,0,59,121,0,58,110,111,105,115,101,49,0,0,18,120,0,58,118,101,99,52,0,0,17,49, +57,0,51,52,0,0,0,17,55,0,54,54,0,0,0,17,51,0,50,51,0,0,0,17,50,0,55,55,0,0,0,0,46,0,0,20,0,0,1,90, +95,0,0,11,0,0,110,111,105,115,101,51,0,1,1,0,0,9,0,120,0,0,0,1,9,18,95,95,114,101,116,86,97,108,0, +59,120,0,58,110,111,105,115,101,49,0,0,18,120,0,0,0,20,0,9,18,95,95,114,101,116,86,97,108,0,59,121, +0,58,110,111,105,115,101,49,0,0,18,120,0,17,49,57,0,51,52,0,0,46,0,0,20,0,9,18,95,95,114,101,116, +86,97,108,0,59,122,0,18,95,95,114,101,116,86,97,108,0,59,120,0,20,0,0,1,90,95,0,0,11,0,0,110,111, +105,115,101,51,0,1,1,0,0,10,0,120,0,0,0,1,9,18,95,95,114,101,116,86,97,108,0,59,120,0,58,110,111, 105,115,101,49,0,0,18,120,0,0,0,20,0,9,18,95,95,114,101,116,86,97,108,0,59,121,0,58,110,111,105, -115,101,49,0,0,18,120,0,17,49,57,0,51,52,0,0,46,0,0,20,0,9,18,95,95,114,101,116,86,97,108,0,59,122, -0,58,110,111,105,115,101,49,0,0,18,120,0,17,53,0,52,55,0,0,46,0,0,20,0,0,1,90,95,0,0,11,0,0,110, -111,105,115,101,51,0,1,1,0,0,10,0,120,0,0,0,1,9,18,95,95,114,101,116,86,97,108,0,59,120,0,58,110, +115,101,49,0,0,18,120,0,58,118,101,99,50,0,0,17,49,57,0,51,52,0,0,0,17,55,0,54,54,0,0,0,0,46,0,0, +20,0,9,18,95,95,114,101,116,86,97,108,0,59,122,0,18,95,95,114,101,116,86,97,108,0,59,120,0,20,0,0, +1,90,95,0,0,11,0,0,110,111,105,115,101,51,0,1,1,0,0,11,0,120,0,0,0,1,9,18,95,95,114,101,116,86,97, +108,0,59,120,0,58,110,111,105,115,101,49,0,0,18,120,0,0,0,20,0,9,18,95,95,114,101,116,86,97,108,0, +59,121,0,58,110,111,105,115,101,49,0,0,18,120,0,58,118,101,99,51,0,0,17,49,57,0,51,52,0,0,0,17,55, +0,54,54,0,0,0,17,51,0,50,51,0,0,0,0,46,0,0,20,0,9,18,95,95,114,101,116,86,97,108,0,59,122,0,18,95, +95,114,101,116,86,97,108,0,59,120,0,20,0,0,1,90,95,0,0,11,0,0,110,111,105,115,101,51,0,1,1,0,0,12, +0,120,0,0,0,1,9,18,95,95,114,101,116,86,97,108,0,59,120,0,58,110,111,105,115,101,49,0,0,18,120,0,0, +0,20,0,9,18,95,95,114,101,116,86,97,108,0,59,121,0,58,110,111,105,115,101,49,0,0,18,120,0,58,118, +101,99,52,0,0,17,49,57,0,51,52,0,0,0,17,55,0,54,54,0,0,0,17,51,0,50,51,0,0,0,17,50,0,55,55,0,0,0,0, +46,0,0,20,0,9,18,95,95,114,101,116,86,97,108,0,59,122,0,18,95,95,114,101,116,86,97,108,0,59,120,0, +20,0,0,1,90,95,0,0,12,0,0,110,111,105,115,101,52,0,1,1,0,0,9,0,120,0,0,0,1,9,18,95,95,114,101,116, +86,97,108,0,59,120,0,58,110,111,105,115,101,49,0,0,18,120,0,0,0,20,0,9,18,95,95,114,101,116,86,97, +108,0,59,121,0,58,110,111,105,115,101,49,0,0,18,120,0,17,49,57,0,51,52,0,0,46,0,0,20,0,9,18,95,95, +114,101,116,86,97,108,0,59,122,0,18,95,95,114,101,116,86,97,108,0,59,120,0,20,0,9,18,95,95,114,101, +116,86,97,108,0,59,119,0,18,95,95,114,101,116,86,97,108,0,59,121,0,20,0,0,1,90,95,0,0,12,0,0,110, +111,105,115,101,52,0,1,1,0,0,10,0,120,0,0,0,1,9,18,95,95,114,101,116,86,97,108,0,59,120,0,58,110, 111,105,115,101,49,0,0,18,120,0,0,0,20,0,9,18,95,95,114,101,116,86,97,108,0,59,121,0,58,110,111, 105,115,101,49,0,0,18,120,0,58,118,101,99,50,0,0,17,49,57,0,51,52,0,0,0,17,55,0,54,54,0,0,0,0,46,0, -0,20,0,9,18,95,95,114,101,116,86,97,108,0,59,122,0,58,110,111,105,115,101,49,0,0,18,120,0,58,118, -101,99,50,0,0,17,53,0,52,55,0,0,0,17,49,55,0,56,53,0,0,0,0,46,0,0,20,0,0,1,90,95,0,0,11,0,0,110, -111,105,115,101,51,0,1,1,0,0,11,0,120,0,0,0,1,9,18,95,95,114,101,116,86,97,108,0,59,120,0,58,110, -111,105,115,101,49,0,0,18,120,0,0,0,20,0,9,18,95,95,114,101,116,86,97,108,0,59,121,0,58,110,111, -105,115,101,49,0,0,18,120,0,58,118,101,99,51,0,0,17,49,57,0,51,52,0,0,0,17,55,0,54,54,0,0,0,17,51, -0,50,51,0,0,0,0,46,0,0,20,0,9,18,95,95,114,101,116,86,97,108,0,59,122,0,58,110,111,105,115,101,49, -0,0,18,120,0,58,118,101,99,51,0,0,17,53,0,52,55,0,0,0,17,49,55,0,56,53,0,0,0,17,49,49,0,48,52,0,0, -0,0,46,0,0,20,0,0,1,90,95,0,0,11,0,0,110,111,105,115,101,51,0,1,1,0,0,12,0,120,0,0,0,1,9,18,95,95, -114,101,116,86,97,108,0,59,120,0,58,110,111,105,115,101,49,0,0,18,120,0,0,0,20,0,9,18,95,95,114, -101,116,86,97,108,0,59,121,0,58,110,111,105,115,101,49,0,0,18,120,0,58,118,101,99,52,0,0,17,49,57, -0,51,52,0,0,0,17,55,0,54,54,0,0,0,17,51,0,50,51,0,0,0,17,50,0,55,55,0,0,0,0,46,0,0,20,0,9,18,95,95, -114,101,116,86,97,108,0,59,122,0,58,110,111,105,115,101,49,0,0,18,120,0,58,118,101,99,52,0,0,17,53, -0,52,55,0,0,0,17,49,55,0,56,53,0,0,0,17,49,49,0,48,52,0,0,0,17,49,51,0,49,57,0,0,0,0,46,0,0,20,0,0, -1,90,95,0,0,12,0,0,110,111,105,115,101,52,0,1,1,0,0,9,0,120,0,0,0,1,9,18,95,95,114,101,116,86,97, -108,0,59,120,0,58,110,111,105,115,101,49,0,0,18,120,0,0,0,20,0,9,18,95,95,114,101,116,86,97,108,0, -59,121,0,58,110,111,105,115,101,49,0,0,18,120,0,17,49,57,0,51,52,0,0,46,0,0,20,0,9,18,95,95,114, -101,116,86,97,108,0,59,122,0,58,110,111,105,115,101,49,0,0,18,120,0,17,53,0,52,55,0,0,46,0,0,20,0, -9,18,95,95,114,101,116,86,97,108,0,59,119,0,58,110,111,105,115,101,49,0,0,18,120,0,17,50,51,0,53, -52,0,0,46,0,0,20,0,0,1,90,95,0,0,12,0,0,110,111,105,115,101,52,0,1,1,0,0,10,0,120,0,0,0,1,9,18,95, -95,114,101,116,86,97,108,0,59,120,0,58,110,111,105,115,101,49,0,0,18,120,0,0,0,20,0,9,18,95,95,114, -101,116,86,97,108,0,59,121,0,58,110,111,105,115,101,49,0,0,18,120,0,58,118,101,99,50,0,0,17,49,57, -0,51,52,0,0,0,17,55,0,54,54,0,0,0,0,46,0,0,20,0,9,18,95,95,114,101,116,86,97,108,0,59,122,0,58,110, -111,105,115,101,49,0,0,18,120,0,58,118,101,99,50,0,0,17,53,0,52,55,0,0,0,17,49,55,0,56,53,0,0,0,0, -46,0,0,20,0,9,18,95,95,114,101,116,86,97,108,0,59,119,0,58,110,111,105,115,101,49,0,0,18,120,0,58, -118,101,99,50,0,0,17,50,51,0,53,52,0,0,0,17,50,57,0,49,49,0,0,0,0,46,0,0,20,0,0,1,90,95,0,0,12,0,0, -110,111,105,115,101,52,0,1,1,0,0,11,0,120,0,0,0,1,9,18,95,95,114,101,116,86,97,108,0,59,120,0,58, -110,111,105,115,101,49,0,0,18,120,0,0,0,20,0,9,18,95,95,114,101,116,86,97,108,0,59,121,0,58,110, -111,105,115,101,49,0,0,18,120,0,58,118,101,99,51,0,0,17,49,57,0,51,52,0,0,0,17,55,0,54,54,0,0,0,17, -51,0,50,51,0,0,0,0,46,0,0,20,0,9,18,95,95,114,101,116,86,97,108,0,59,122,0,58,110,111,105,115,101, -49,0,0,18,120,0,58,118,101,99,51,0,0,17,53,0,52,55,0,0,0,17,49,55,0,56,53,0,0,0,17,49,49,0,48,52,0, -0,0,0,46,0,0,20,0,9,18,95,95,114,101,116,86,97,108,0,59,119,0,58,110,111,105,115,101,49,0,0,18,120, -0,58,118,101,99,51,0,0,17,50,51,0,53,52,0,0,0,17,50,57,0,49,49,0,0,0,17,51,49,0,57,49,0,0,0,0,46,0, -0,20,0,0,1,90,95,0,0,12,0,0,110,111,105,115,101,52,0,1,1,0,0,12,0,120,0,0,0,1,9,18,95,95,114,101, -116,86,97,108,0,59,120,0,58,110,111,105,115,101,49,0,0,18,120,0,0,0,20,0,9,18,95,95,114,101,116,86, -97,108,0,59,121,0,58,110,111,105,115,101,49,0,0,18,120,0,58,118,101,99,52,0,0,17,49,57,0,51,52,0,0, -0,17,55,0,54,54,0,0,0,17,51,0,50,51,0,0,0,17,50,0,55,55,0,0,0,0,46,0,0,20,0,9,18,95,95,114,101,116, -86,97,108,0,59,122,0,58,110,111,105,115,101,49,0,0,18,120,0,58,118,101,99,52,0,0,17,53,0,52,55,0,0, -0,17,49,55,0,56,53,0,0,0,17,49,49,0,48,52,0,0,0,17,49,51,0,49,57,0,0,0,0,46,0,0,20,0,9,18,95,95, -114,101,116,86,97,108,0,59,119,0,58,110,111,105,115,101,49,0,0,18,120,0,58,118,101,99,52,0,0,17,50, -51,0,53,52,0,0,0,17,50,57,0,49,49,0,0,0,17,51,49,0,57,49,0,0,0,17,51,55,0,52,56,0,0,0,0,46,0,0,20, -0,0,0 +0,20,0,9,18,95,95,114,101,116,86,97,108,0,59,122,0,18,95,95,114,101,116,86,97,108,0,59,120,0,20,0, +9,18,95,95,114,101,116,86,97,108,0,59,119,0,18,95,95,114,101,116,86,97,108,0,59,121,0,20,0,0,1,90, +95,0,0,12,0,0,110,111,105,115,101,52,0,1,1,0,0,11,0,120,0,0,0,1,9,18,95,95,114,101,116,86,97,108,0, +59,120,0,58,110,111,105,115,101,49,0,0,18,120,0,0,0,20,0,9,18,95,95,114,101,116,86,97,108,0,59,121, +0,58,110,111,105,115,101,49,0,0,18,120,0,58,118,101,99,51,0,0,17,49,57,0,51,52,0,0,0,17,55,0,54,54, +0,0,0,17,51,0,50,51,0,0,0,0,46,0,0,20,0,9,18,95,95,114,101,116,86,97,108,0,59,122,0,18,95,95,114, +101,116,86,97,108,0,59,120,0,20,0,9,18,95,95,114,101,116,86,97,108,0,59,119,0,18,95,95,114,101,116, +86,97,108,0,59,121,0,20,0,0,1,90,95,0,0,12,0,0,110,111,105,115,101,52,0,1,1,0,0,12,0,120,0,0,0,1,9, +18,95,95,114,101,116,86,97,108,0,59,120,0,58,110,111,105,115,101,49,0,0,18,120,0,0,0,20,0,9,18,95, +95,114,101,116,86,97,108,0,59,121,0,58,110,111,105,115,101,49,0,0,18,120,0,58,118,101,99,52,0,0,17, +49,57,0,51,52,0,0,0,17,55,0,54,54,0,0,0,17,51,0,50,51,0,0,0,17,50,0,55,55,0,0,0,0,46,0,0,20,0,9,18, +95,95,114,101,116,86,97,108,0,59,122,0,18,95,95,114,101,116,86,97,108,0,59,120,0,20,0,9,18,95,95, +114,101,116,86,97,108,0,59,119,0,18,95,95,114,101,116,86,97,108,0,59,121,0,20,0,0,0 -- 1.6.3.3