YT-19324: move YT provider to ydb/library/yql

This commit is formed by the following script: https://paste.yandex-team.ru/6f92e4b8-efc5-4d34-948b-15ee2accd7e7/text.
This commit has zero effect on all projects that depend on YQL.

The summary of changes:
- `yql/providers/yt -> ydb/library/yql/providers/yt `- the whole implementation of YT provider is moved into YDB code base for further export as a part of YT YQL plugin shared library;
- `yql/providers/stat/{expr_nodes,uploader} -> ydb/library/yql/providers/stat/{expr_nodes,uploader}` - a small interface without implementation and the description of stat expr nodes;
- `yql/core/extract_predicate/ut -> ydb/library/yql/core/extract_predicate/ut`;
- `yql/core/{ut,ut_common} -> ydb/library/yql/core/{ut,ut_common}`;
- `yql/core` is gone;
- `yql/library/url_preprocessing -> ydb/library/yql/core/url_preprocessing`.

**NB**: all new targets inside `ydb/` are under `IF (NOT CMAKE_EXPORT)` clause which disables them from open-source cmake generation and ya make build. They will be enabled in the subsequent commits.

1 files changed, 371 insertions, 0 deletions

diff --git a/contrib/libs/isa-l/erasure_code/ec_base.c b/contrib/libs/isa-l/erasure_code/ec_base.c
new file mode 100644
index 0000000000..9a8fbc759e
--- /dev/null
+++ b/contrib/libs/isa-l/erasure_code/ec_base.c
@@ -0,0 +1,371 @@
+/**********************************************************************
+  Copyright(c) 2011-2015 Intel Corporation All rights reserved.
+
+  Redistribution and use in source and binary forms, with or without
+  modification, are permitted provided that the following conditions
+  are met:
+    * Redistributions of source code must retain the above copyright
+      notice, this list of conditions and the following disclaimer.
+    * Redistributions in binary form must reproduce the above copyright
+      notice, this list of conditions and the following disclaimer in
+      the documentation and/or other materials provided with the
+      distribution.
+    * Neither the name of Intel Corporation nor the names of its
+      contributors may be used to endorse or promote products derived
+      from this software without specific prior written permission.
+
+  THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+  "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+  LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+  A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
+  OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+  SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+  LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+  DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+  THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+  (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+  OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+**********************************************************************/
+
+#include <limits.h>
+#include <string.h>		// for memset
+#include "erasure_code.h"
+#include "ec_base.h"		// for GF tables
+
+void ec_init_tables(int k, int rows, unsigned char *a, unsigned char *g_tbls)
+{
+	int i, j;
+
+	for (i = 0; i < rows; i++) {
+		for (j = 0; j < k; j++) {
+			gf_vect_mul_init(*a++, g_tbls);
+			g_tbls += 32;
+		}
+	}
+}
+
+unsigned char gf_mul_erasure(unsigned char a, unsigned char b)
+{
+#ifndef GF_LARGE_TABLES
+	int i;
+
+	if ((a == 0) || (b == 0))
+		return 0;
+
+	return gff_base[(i = gflog_base[a] + gflog_base[b]) > 254 ? i - 255 : i];
+#else
+	return gf_mul_table_base[b * 256 + a];
+#endif
+}
+
+unsigned char gf_inv(unsigned char a)
+{
+#ifndef GF_LARGE_TABLES
+	if (a == 0)
+		return 0;
+
+	return gff_base[255 - gflog_base[a]];
+#else
+	return gf_inv_table_base[a];
+#endif
+}
+
+void gf_gen_rs_matrix(unsigned char *a, int m, int k)
+{
+	int i, j;
+	unsigned char p, gen = 1;
+
+	memset(a, 0, k * m);
+	for (i = 0; i < k; i++)
+		a[k * i + i] = 1;
+
+	for (i = k; i < m; i++) {
+		p = 1;
+		for (j = 0; j < k; j++) {
+			a[k * i + j] = p;
+			p = gf_mul_erasure(p, gen);
+		}
+		gen = gf_mul_erasure(gen, 2);
+	}
+}
+
+void gf_gen_cauchy1_matrix(unsigned char *a, int m, int k)
+{
+	int i, j;
+	unsigned char *p;
+
+	// Identity matrix in high position
+	memset(a, 0, k * m);
+	for (i = 0; i < k; i++)
+		a[k * i + i] = 1;
+
+	// For the rest choose 1/(i + j) | i != j
+	p = &a[k * k];
+	for (i = k; i < m; i++)
+		for (j = 0; j < k; j++)
+			*p++ = gf_inv(i ^ j);
+
+}
+
+int gf_invert_matrix(unsigned char *in_mat, unsigned char *out_mat, const int n)
+{
+	int i, j, k;
+	unsigned char temp;
+
+	// Set out_mat[] to the identity matrix
+	for (i = 0; i < n * n; i++)	// memset(out_mat, 0, n*n)
+		out_mat[i] = 0;
+
+	for (i = 0; i < n; i++)
+		out_mat[i * n + i] = 1;
+
+	// Inverse
+	for (i = 0; i < n; i++) {
+		// Check for 0 in pivot element
+		if (in_mat[i * n + i] == 0) {
+			// Find a row with non-zero in current column and swap
+			for (j = i + 1; j < n; j++)
+				if (in_mat[j * n + i])
+					break;
+
+			if (j == n)	// Couldn't find means it's singular
+				return -1;
+
+			for (k = 0; k < n; k++) {	// Swap rows i,j
+				temp = in_mat[i * n + k];
+				in_mat[i * n + k] = in_mat[j * n + k];
+				in_mat[j * n + k] = temp;
+
+				temp = out_mat[i * n + k];
+				out_mat[i * n + k] = out_mat[j * n + k];
+				out_mat[j * n + k] = temp;
+			}
+		}
+
+		temp = gf_inv(in_mat[i * n + i]);	// 1/pivot
+		for (j = 0; j < n; j++) {	// Scale row i by 1/pivot
+			in_mat[i * n + j] = gf_mul_erasure(in_mat[i * n + j], temp);
+			out_mat[i * n + j] = gf_mul_erasure(out_mat[i * n + j], temp);
+		}
+
+		for (j = 0; j < n; j++) {
+			if (j == i)
+				continue;
+
+			temp = in_mat[j * n + i];
+			for (k = 0; k < n; k++) {
+				out_mat[j * n + k] ^= gf_mul_erasure(temp, out_mat[i * n + k]);
+				in_mat[j * n + k] ^= gf_mul_erasure(temp, in_mat[i * n + k]);
+			}
+		}
+	}
+	return 0;
+}
+
+// Calculates const table gftbl in GF(2^8) from single input A
+// gftbl(A) = {A{00}, A{01}, A{02}, ... , A{0f} }, {A{00}, A{10}, A{20}, ... , A{f0} }
+
+void gf_vect_mul_init(unsigned char c, unsigned char *tbl)
+{
+	unsigned char c2 = (c << 1) ^ ((c & 0x80) ? 0x1d : 0);	//Mult by GF{2}
+	unsigned char c4 = (c2 << 1) ^ ((c2 & 0x80) ? 0x1d : 0);	//Mult by GF{2}
+	unsigned char c8 = (c4 << 1) ^ ((c4 & 0x80) ? 0x1d : 0);	//Mult by GF{2}
+
+#if __WORDSIZE == 64 || _WIN64 || __x86_64__
+	unsigned long long v1, v2, v4, v8, *t;
+	unsigned long long v10, v20, v40, v80;
+	unsigned char c17, c18, c20, c24;
+
+	t = (unsigned long long *)tbl;
+
+	v1 = c * 0x0100010001000100ull;
+	v2 = c2 * 0x0101000001010000ull;
+	v4 = c4 * 0x0101010100000000ull;
+	v8 = c8 * 0x0101010101010101ull;
+
+	v4 = v1 ^ v2 ^ v4;
+	t[0] = v4;
+	t[1] = v8 ^ v4;
+
+	c17 = (c8 << 1) ^ ((c8 & 0x80) ? 0x1d : 0);	//Mult by GF{2}
+	c18 = (c17 << 1) ^ ((c17 & 0x80) ? 0x1d : 0);	//Mult by GF{2}
+	c20 = (c18 << 1) ^ ((c18 & 0x80) ? 0x1d : 0);	//Mult by GF{2}
+	c24 = (c20 << 1) ^ ((c20 & 0x80) ? 0x1d : 0);	//Mult by GF{2}
+
+	v10 = c17 * 0x0100010001000100ull;
+	v20 = c18 * 0x0101000001010000ull;
+	v40 = c20 * 0x0101010100000000ull;
+	v80 = c24 * 0x0101010101010101ull;
+
+	v40 = v10 ^ v20 ^ v40;
+	t[2] = v40;
+	t[3] = v80 ^ v40;
+
+#else // 32-bit or other
+	unsigned char c3, c5, c6, c7, c9, c10, c11, c12, c13, c14, c15;
+	unsigned char c17, c18, c19, c20, c21, c22, c23, c24, c25, c26, c27, c28, c29, c30,
+	    c31;
+
+	c3 = c2 ^ c;
+	c5 = c4 ^ c;
+	c6 = c4 ^ c2;
+	c7 = c4 ^ c3;
+
+	c9 = c8 ^ c;
+	c10 = c8 ^ c2;
+	c11 = c8 ^ c3;
+	c12 = c8 ^ c4;
+	c13 = c8 ^ c5;
+	c14 = c8 ^ c6;
+	c15 = c8 ^ c7;
+
+	tbl[0] = 0;
+	tbl[1] = c;
+	tbl[2] = c2;
+	tbl[3] = c3;
+	tbl[4] = c4;
+	tbl[5] = c5;
+	tbl[6] = c6;
+	tbl[7] = c7;
+	tbl[8] = c8;
+	tbl[9] = c9;
+	tbl[10] = c10;
+	tbl[11] = c11;
+	tbl[12] = c12;
+	tbl[13] = c13;
+	tbl[14] = c14;
+	tbl[15] = c15;
+
+	c17 = (c8 << 1) ^ ((c8 & 0x80) ? 0x1d : 0);	//Mult by GF{2}
+	c18 = (c17 << 1) ^ ((c17 & 0x80) ? 0x1d : 0);	//Mult by GF{2}
+	c19 = c18 ^ c17;
+	c20 = (c18 << 1) ^ ((c18 & 0x80) ? 0x1d : 0);	//Mult by GF{2}
+	c21 = c20 ^ c17;
+	c22 = c20 ^ c18;
+	c23 = c20 ^ c19;
+	c24 = (c20 << 1) ^ ((c20 & 0x80) ? 0x1d : 0);	//Mult by GF{2}
+	c25 = c24 ^ c17;
+	c26 = c24 ^ c18;
+	c27 = c24 ^ c19;
+	c28 = c24 ^ c20;
+	c29 = c24 ^ c21;
+	c30 = c24 ^ c22;
+	c31 = c24 ^ c23;
+
+	tbl[16] = 0;
+	tbl[17] = c17;
+	tbl[18] = c18;
+	tbl[19] = c19;
+	tbl[20] = c20;
+	tbl[21] = c21;
+	tbl[22] = c22;
+	tbl[23] = c23;
+	tbl[24] = c24;
+	tbl[25] = c25;
+	tbl[26] = c26;
+	tbl[27] = c27;
+	tbl[28] = c28;
+	tbl[29] = c29;
+	tbl[30] = c30;
+	tbl[31] = c31;
+
+#endif //__WORDSIZE == 64 || _WIN64 || __x86_64__
+}
+
+void gf_vect_dot_prod_base(int len, int vlen, unsigned char *v,
+			   unsigned char **src, unsigned char *dest)
+{
+	int i, j;
+	unsigned char s;
+	for (i = 0; i < len; i++) {
+		s = 0;
+		for (j = 0; j < vlen; j++)
+			s ^= gf_mul_erasure(src[j][i], v[j * 32 + 1]);
+
+		dest[i] = s;
+	}
+}
+
+void gf_vect_mad_base(int len, int vec, int vec_i,
+		      unsigned char *v, unsigned char *src, unsigned char *dest)
+{
+	int i;
+	unsigned char s;
+	for (i = 0; i < len; i++) {
+		s = dest[i];
+		s ^= gf_mul_erasure(src[i], v[vec_i * 32 + 1]);
+		dest[i] = s;
+	}
+}
+
+void ec_encode_data_base(int len, int srcs, int dests, unsigned char *v,
+			 unsigned char **src, unsigned char **dest)
+{
+	int i, j, l;
+	unsigned char s;
+
+	for (l = 0; l < dests; l++) {
+		for (i = 0; i < len; i++) {
+			s = 0;
+			for (j = 0; j < srcs; j++)
+				s ^= gf_mul_erasure(src[j][i], v[j * 32 + l * srcs * 32 + 1]);
+
+			dest[l][i] = s;
+		}
+	}
+}
+
+void ec_encode_data_update_base(int len, int k, int rows, int vec_i, unsigned char *v,
+				unsigned char *data, unsigned char **dest)
+{
+	int i, l;
+	unsigned char s;
+
+	for (l = 0; l < rows; l++) {
+		for (i = 0; i < len; i++) {
+			s = dest[l][i];
+			s ^= gf_mul_erasure(data[i], v[vec_i * 32 + l * k * 32 + 1]);
+
+			dest[l][i] = s;
+		}
+	}
+}
+
+void gf_vect_mul_base(int len, unsigned char *a, unsigned char *src, unsigned char *dest)
+{
+	//2nd element of table array is ref value used to fill it in
+	unsigned char c = a[1];
+	while (len-- > 0)
+		*dest++ = gf_mul_erasure(c, *src++);
+}
+
+struct slver {
+	unsigned short snum;
+	unsigned char ver;
+	unsigned char core;
+};
+
+// Version info
+struct slver gf_vect_mul_init_slver_00020035;
+struct slver gf_vect_mul_init_slver = { 0x0035, 0x02, 0x00 };
+
+struct slver ec_encode_data_base_slver_00010135;
+struct slver ec_encode_data_base_slver = { 0x0135, 0x01, 0x00 };
+
+struct slver gf_vect_mul_base_slver_00010136;
+struct slver gf_vect_mul_base_slver = { 0x0136, 0x01, 0x00 };
+
+struct slver gf_vect_dot_prod_base_slver_00010137;
+struct slver gf_vect_dot_prod_base_slver = { 0x0137, 0x01, 0x00 };
+
+struct slver gf_mul_slver_00000214;
+struct slver gf_mul_slver = { 0x0214, 0x00, 0x00 };
+
+struct slver gf_invert_matrix_slver_00000215;
+struct slver gf_invert_matrix_slver = { 0x0215, 0x00, 0x00 };
+
+struct slver gf_gen_rs_matrix_slver_00000216;
+struct slver gf_gen_rs_matrix_slver = { 0x0216, 0x00, 0x00 };
+
+struct slver gf_gen_cauchy1_matrix_slver_00000217;
+struct slver gf_gen_cauchy1_matrix_slver = { 0x0217, 0x00, 0x00 };