intermediate changes

ref:cde9a383711a11544ce7e107a78147fb96cc4029

8 files changed, 882 insertions, 0 deletions

diff --git a/contrib/libs/fastlz/.yandex_meta/devtools.copyrights.report b/contrib/libs/fastlz/.yandex_meta/devtools.copyrights.report
new file mode 100644
index 0000000000..e67790bb0b
--- /dev/null
+++ b/contrib/libs/fastlz/.yandex_meta/devtools.copyrights.report
@@ -0,0 +1,75 @@
+# File format ($ symbol means the beginning of a line):
+#
+# $ # this message
+# $ # =======================
+# $     # comments (all commentaries should starts with some number of spaces and # symbol)
+# ${action} {license id} {license text hash}
+# $BELONGS ./ya/make/file/relative/path/1/ya.make ./ya/make/2/ya.make
+# ${all_file_action} filename
+# $ # user commentaries (many lines)
+# $ generated description - files with this license, license text... (some number of lines that starts with some number of spaces, do not modify)
+# ${action} {license spdx} {license text hash}
+# $BELONGS ./ya/make/file/relative/path/3/ya.make
+# ${all_file_action} filename
+# $    #    user commentaries
+# $ generated description
+# $ ...
+#
+# You can modify action, all_file_action and add commentaries
+# Available actions:
+# keep - keep license in contrib and use in credits
+# skip - skip license
+# remove - remove all files with this license
+# rename - save license text/links into licenses texts file, but not store SPDX into LINCENSE macro. You should store correct license id into devtools.license.spdx.txt file
+#
+# {all file action} records will be generated when license text contains filename that exists on filesystem (in contrib directory)
+# We suppose that that files can contain some license info
+# Available all file actions:
+# FILE_IGNORE - ignore file (do nothing)
+# FILE_INCLUDE - include all file data into licenses text file
+# =======================
+
+KEEP     COPYRIGHT_SERVICE_LABEL 63a56910668285cc7da3aa8b80de03f3
+BELONGS ya.make
+    License text:
+          Copyright (C) 2007 Ariya Hidayat (ariya@kde.org)
+          Copyright (C) 2006 Ariya Hidayat (ariya@kde.org)
+          Copyright (C) 2005 Ariya Hidayat (ariya@kde.org)
+    Scancode info:
+        Original SPDX id: COPYRIGHT_SERVICE_LABEL
+        Score           : 100.00
+        Match type      : COPYRIGHT
+    Files with this license:
+        LICENSE [3:5]
+        fastlz.c [4:6]
+        fastlz.h [4:6]
+
+KEEP     COPYRIGHT_SERVICE_LABEL 6bc37d1989a63d7fafc50cef4bc989f4
+BELONGS ya.make
+    License text:
+          Copyright (C) 2007 Ariya Hidayat (ariya@kde.org)
+          Copyright (C) 2006 Ariya Hidayat (ariya@kde.org)
+          Copyright (C) 2005 Ariya Hidayat (ariya@kde.org)
+    Scancode info:
+        Original SPDX id: COPYRIGHT_SERVICE_LABEL
+        Score           : 100.00
+        Match type      : COPYRIGHT
+    Files with this license:
+        LICENSE [3:5]
+        fastlz.c [4:6]
+        fastlz.h [4:6]
+
+KEEP     COPYRIGHT_SERVICE_LABEL dbe38c3f29fb7fee46b9cffb2d418183
+BELONGS ya.make
+    License text:
+          Copyright (C) 2007 Ariya Hidayat (ariya@kde.org)
+          Copyright (C) 2006 Ariya Hidayat (ariya@kde.org)
+          Copyright (C) 2005 Ariya Hidayat (ariya@kde.org)
+    Scancode info:
+        Original SPDX id: COPYRIGHT_SERVICE_LABEL
+        Score           : 100.00
+        Match type      : COPYRIGHT
+    Files with this license:
+        LICENSE [3:5]
+        fastlz.c [4:6]
+        fastlz.h [4:6]
diff --git a/contrib/libs/fastlz/.yandex_meta/devtools.licenses.report b/contrib/libs/fastlz/.yandex_meta/devtools.licenses.report
new file mode 100644
index 0000000000..444284ff48
--- /dev/null
+++ b/contrib/libs/fastlz/.yandex_meta/devtools.licenses.report
@@ -0,0 +1,53 @@
+# File format ($ symbol means the beginning of a line):
+#
+# $ # this message
+# $ # =======================
+# $     # comments (all commentaries should starts with some number of spaces and # symbol)
+# ${action} {license spdx} {license text hash}
+# $BELONGS ./ya/make/file/relative/path/1/ya.make ./ya/make/2/ya.make
+# ${all_file_action} filename
+# $ # user commentaries (many lines)
+# $ generated description - files with this license, license text... (some number of lines that starts with some number of spaces, do not modify)
+# ${action} {license spdx} {license text hash}
+# $BELONGS ./ya/make/file/relative/path/3/ya.make
+# ${all_file_action} filename
+# $    #    user commentaries
+# $ generated description
+# $ ...
+#
+# You can modify action, all_file_action and add commentaries
+# Available actions:
+# keep - keep license in contrib and use in credits
+# skip - skip license
+# remove - remove all files with this license
+# rename - save license text/links into licenses texts file, but not store SPDX into LINCENSE macro. You should store correct license id into devtools.license.spdx.txt file
+#
+# {all file action} records will be generated when license text contains filename that exists on filesystem (in contrib directory)
+# We suppose that that files can contain some license info
+# Available all file actions:
+# FILE_IGNORE - ignore file (do nothing)
+# FILE_INCLUDE - include all file data into licenses text file
+# =======================
+
+KEEP     MIT                  5debb370f50e1dfd24ff5144233a2ef6
+BELONGS ya.make
+    Note: matched license text is too long. Read it in the source files.
+    Scancode info:
+        Original SPDX id: MIT
+        Score           : 100.00
+        Match type      : TEXT
+        Links           : http://opensource.org/licenses/mit-license.php, https://spdx.org/licenses/MIT
+    Files with this license:
+        LICENSE [7:23]
+
+KEEP     MIT                  b86f92e26fd701d7586fe0fb46cb52a5
+BELONGS ya.make
+    Note: matched license text is too long. Read it in the source files.
+    Scancode info:
+        Original SPDX id: MIT
+        Score           : 100.00
+        Match type      : TEXT
+        Links           : http://opensource.org/licenses/mit-license.php, https://spdx.org/licenses/MIT
+    Files with this license:
+        fastlz.c [8:24]
+        fastlz.h [8:24]
diff --git a/contrib/libs/fastlz/.yandex_meta/licenses.list.txt b/contrib/libs/fastlz/.yandex_meta/licenses.list.txt
new file mode 100644
index 0000000000..bd8967ec72
--- /dev/null
+++ b/contrib/libs/fastlz/.yandex_meta/licenses.list.txt
@@ -0,0 +1,44 @@
+====================COPYRIGHT====================
+  Copyright (C) 2007 Ariya Hidayat (ariya@kde.org)
+  Copyright (C) 2006 Ariya Hidayat (ariya@kde.org)
+  Copyright (C) 2005 Ariya Hidayat (ariya@kde.org)
+
+
+====================MIT====================
+  Permission is hereby granted, free of charge, to any person obtaining a copy
+  of this software and associated documentation files (the "Software"), to deal
+  in the Software without restriction, including without limitation the rights
+  to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+  copies of the Software, and to permit persons to whom the Software is
+  furnished to do so, subject to the following conditions:
+
+  The above copyright notice and this permission notice shall be included in
+  all copies or substantial portions of the Software.
+
+  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+  IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+  FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+  AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+  LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+  OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
+  THE SOFTWARE.
+
+
+====================MIT====================
+Permission is hereby granted, free of charge, to any person obtaining a copy
+of this software and associated documentation files (the "Software"), to deal
+in the Software without restriction, including without limitation the rights
+to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+copies of the Software, and to permit persons to whom the Software is
+furnished to do so, subject to the following conditions:
+
+The above copyright notice and this permission notice shall be included in
+all copies or substantial portions of the Software.
+
+THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
+THE SOFTWARE.
diff --git a/contrib/libs/fastlz/LICENSE b/contrib/libs/fastlz/LICENSE
new file mode 100644
index 0000000000..4a6abd6acb
--- /dev/null
+++ b/contrib/libs/fastlz/LICENSE
@@ -0,0 +1,24 @@
+FastLZ - lightning-fast lossless compression library
+
+Copyright (C) 2007 Ariya Hidayat (ariya@kde.org)
+Copyright (C) 2006 Ariya Hidayat (ariya@kde.org)
+Copyright (C) 2005 Ariya Hidayat (ariya@kde.org)
+
+Permission is hereby granted, free of charge, to any person obtaining a copy
+of this software and associated documentation files (the "Software"), to deal
+in the Software without restriction, including without limitation the rights
+to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+copies of the Software, and to permit persons to whom the Software is
+furnished to do so, subject to the following conditions:
+
+The above copyright notice and this permission notice shall be included in
+all copies or substantial portions of the Software.
+
+THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
+THE SOFTWARE.
+
diff --git a/contrib/libs/fastlz/fastlz.c b/contrib/libs/fastlz/fastlz.c
new file mode 100644
index 0000000000..e671bda728
--- /dev/null
+++ b/contrib/libs/fastlz/fastlz.c
@@ -0,0 +1,553 @@
+/*  
+  FastLZ - lightning-fast lossless compression library
+
+  Copyright (C) 2007 Ariya Hidayat (ariya@kde.org)
+  Copyright (C) 2006 Ariya Hidayat (ariya@kde.org)
+  Copyright (C) 2005 Ariya Hidayat (ariya@kde.org)
+
+  Permission is hereby granted, free of charge, to any person obtaining a copy
+  of this software and associated documentation files (the "Software"), to deal
+  in the Software without restriction, including without limitation the rights
+  to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+  copies of the Software, and to permit persons to whom the Software is
+  furnished to do so, subject to the following conditions:
+
+  The above copyright notice and this permission notice shall be included in
+  all copies or substantial portions of the Software.
+
+  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+  IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+  FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+  AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+  LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+  OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
+  THE SOFTWARE.
+*/
+
+#include "fastlz.h"
+
+#if !defined(FASTLZ__COMPRESSOR) && !defined(FASTLZ_DECOMPRESSOR)
+
+/*
+ * Always check for bound when decompressing.
+ * Generally it is best to leave it defined.
+ */
+#define FASTLZ_SAFE
+
+/*
+ * Give hints to the compiler for branch prediction optimization.
+ */
+#if defined(__GNUC__) && (__GNUC__ > 2)
+#define FASTLZ_EXPECT_CONDITIONAL(c)    (__builtin_expect((c), 1))
+#define FASTLZ_UNEXPECT_CONDITIONAL(c)  (__builtin_expect((c), 0))
+#else
+#define FASTLZ_EXPECT_CONDITIONAL(c)    (c)
+#define FASTLZ_UNEXPECT_CONDITIONAL(c)  (c)
+#endif
+
+/*
+ * Use inlined functions for supported systems.
+ */
+#if defined(__GNUC__) || defined(__DMC__) || defined(__POCC__) || defined(__WATCOMC__) || defined(__SUNPRO_C)
+#define FASTLZ_INLINE inline
+#elif defined(__BORLANDC__) || defined(_MSC_VER) || defined(__LCC__)
+#define FASTLZ_INLINE __inline
+#else 
+#define FASTLZ_INLINE
+#endif
+
+/*
+ * Prevent accessing more than 8-bit at once, except on x86 architectures.
+ */
+#if !defined(FASTLZ_STRICT_ALIGN)
+#define FASTLZ_STRICT_ALIGN
+#if defined(__i386__) || defined(__386)  /* GNU C, Sun Studio */
+#undef FASTLZ_STRICT_ALIGN
+#elif defined(__i486__) || defined(__i586__) || defined(__i686__) /* GNU C */
+#undef FASTLZ_STRICT_ALIGN
+#elif defined(_M_IX86) /* Intel, MSVC */
+#undef FASTLZ_STRICT_ALIGN
+#elif defined(__386)
+#undef FASTLZ_STRICT_ALIGN
+#elif defined(_X86_) /* MinGW */
+#undef FASTLZ_STRICT_ALIGN
+#elif defined(__I86__) /* Digital Mars */
+#undef FASTLZ_STRICT_ALIGN
+#endif
+#endif
+
+/*
+ * FIXME: use preprocessor magic to set this on different platforms!
+ */
+typedef unsigned char  flzuint8;
+typedef unsigned short flzuint16;
+typedef unsigned int   flzuint32;
+
+/* prototypes */
+int fastlz_compress(const void* input, int length, void* output);
+int fastlz_compress_level(int level, const void* input, int length, void* output);
+int fastlz_decompress(const void* input, int length, void* output, int maxout);
+
+#define MAX_COPY       32
+#define MAX_LEN       264  /* 256 + 8 */
+#define MAX_DISTANCE 8192
+
+#if !defined(FASTLZ_STRICT_ALIGN)
+#define FASTLZ_READU16(p) *((const flzuint16*)(p)) 
+#else
+#define FASTLZ_READU16(p) ((p)[0] | (p)[1]<<8)
+#endif
+
+#define HASH_LOG  13
+#define HASH_SIZE (1<< HASH_LOG)
+#define HASH_MASK  (HASH_SIZE-1)
+#define HASH_FUNCTION(v,p) { v = FASTLZ_READU16(p); v ^= FASTLZ_READU16(p+1)^(v>>(16-HASH_LOG));v &= HASH_MASK; }
+
+#undef FASTLZ_LEVEL
+#define FASTLZ_LEVEL 1
+
+#undef FASTLZ_COMPRESSOR
+#undef FASTLZ_DECOMPRESSOR
+#define FASTLZ_COMPRESSOR fastlz1_compress
+#define FASTLZ_DECOMPRESSOR fastlz1_decompress
+static FASTLZ_INLINE int FASTLZ_COMPRESSOR(const void* input, int length, void* output);
+static FASTLZ_INLINE int FASTLZ_DECOMPRESSOR(const void* input, int length, void* output, int maxout);
+#include "fastlz.c"
+
+#undef FASTLZ_LEVEL
+#define FASTLZ_LEVEL 2
+
+#undef MAX_DISTANCE
+#define MAX_DISTANCE 8191
+#define MAX_FARDISTANCE (65535+MAX_DISTANCE-1)
+
+#undef FASTLZ_COMPRESSOR
+#undef FASTLZ_DECOMPRESSOR
+#define FASTLZ_COMPRESSOR fastlz2_compress
+#define FASTLZ_DECOMPRESSOR fastlz2_decompress
+static FASTLZ_INLINE int FASTLZ_COMPRESSOR(const void* input, int length, void* output);
+static FASTLZ_INLINE int FASTLZ_DECOMPRESSOR(const void* input, int length, void* output, int maxout);
+#include "fastlz.c"
+
+int fastlz_compress(const void* input, int length, void* output)
+{
+  /* for short block, choose fastlz1 */
+  if(length < 65536)
+    return fastlz1_compress(input, length, output);
+
+  /* else... */
+  return fastlz2_compress(input, length, output);
+}
+
+int fastlz_decompress(const void* input, int length, void* output, int maxout)
+{
+  /* magic identifier for compression level */
+  int level = ((*(const flzuint8*)input) >> 5) + 1;
+
+  if(level == 1)
+    return fastlz1_decompress(input, length, output, maxout);
+  if(level == 2)
+    return fastlz2_decompress(input, length, output, maxout);
+
+  /* unknown level, trigger error */
+  return 0;
+}
+
+int fastlz_compress_level(int level, const void* input, int length, void* output)
+{
+  if(level == 1)
+    return fastlz1_compress(input, length, output);
+  if(level == 2)
+    return fastlz2_compress(input, length, output);
+
+  return 0;
+}
+
+#else /* !defined(FASTLZ_COMPRESSOR) && !defined(FASTLZ_DECOMPRESSOR) */
+
+static FASTLZ_INLINE int FASTLZ_COMPRESSOR(const void* input, int length, void* output)
+{
+  const flzuint8* ip = (const flzuint8*) input;
+  const flzuint8* ip_bound = ip + length - 2;
+  const flzuint8* ip_limit = ip + length - 12;
+  flzuint8* op = (flzuint8*) output;
+
+  const flzuint8* htab[HASH_SIZE];
+  const flzuint8** hslot;
+  flzuint32 hval;
+
+  flzuint32 copy;
+
+  /* sanity check */
+  if(FASTLZ_UNEXPECT_CONDITIONAL(length < 4))
+  {
+    if(length)
+    {
+      /* create literal copy only */
+      *op++ = length-1;
+      ip_bound++;
+      while(ip <= ip_bound)
+        *op++ = *ip++;
+      return length+1;
+    }
+    else
+      return 0;
+  }
+
+  /* initializes hash table */
+  for (hslot = htab; hslot < htab + HASH_SIZE; hslot++)
+    *hslot = ip;
+
+  /* we start with literal copy */
+  copy = 2;
+  *op++ = MAX_COPY-1;
+  *op++ = *ip++;
+  *op++ = *ip++;
+
+  /* main loop */
+  while(FASTLZ_EXPECT_CONDITIONAL(ip < ip_limit))
+  {
+    const flzuint8* ref;
+    flzuint32 distance;
+
+    /* minimum match length */
+    flzuint32 len = 3;
+
+    /* comparison starting-point */
+    const flzuint8* anchor = ip;
+
+    /* check for a run */
+#if FASTLZ_LEVEL==2
+    if(ip[0] == ip[-1] && FASTLZ_READU16(ip-1)==FASTLZ_READU16(ip+1))
+    {
+      distance = 1;
+      ip += 3;
+      ref = anchor - 1 + 3;
+      goto match;
+    }
+#endif
+
+    /* find potential match */
+    HASH_FUNCTION(hval,ip);
+    hslot = htab + hval;
+    ref = htab[hval];
+
+    /* calculate distance to the match */
+    distance = anchor - ref;
+
+    /* update hash table */
+    *hslot = anchor;
+
+    /* is this a match? check the first 3 bytes */
+    if(distance==0 || 
+#if FASTLZ_LEVEL==1
+    (distance >= MAX_DISTANCE) ||
+#else
+    (distance >= MAX_FARDISTANCE) ||
+#endif
+    *ref++ != *ip++ || *ref++!=*ip++ || *ref++!=*ip++)
+      goto literal;
+
+#if FASTLZ_LEVEL==2
+    /* far, needs at least 5-byte match */
+    if(distance >= MAX_DISTANCE)
+    {
+      if(*ip++ != *ref++ || *ip++!= *ref++) 
+        goto literal;
+      len += 2;
+    }
+    
+    match:
+#endif
+
+    /* last matched byte */
+    ip = anchor + len;
+
+    /* distance is biased */
+    distance--;
+
+    if(!distance)
+    {
+      /* zero distance means a run */
+      flzuint8 x = ip[-1];
+      while(ip < ip_bound)
+        if(*ref++ != x) break; else ip++;
+    }
+    else
+    for(;;)
+    {
+      /* safe because the outer check against ip limit */
+      if(*ref++ != *ip++) break;
+      if(*ref++ != *ip++) break;
+      if(*ref++ != *ip++) break;
+      if(*ref++ != *ip++) break;
+      if(*ref++ != *ip++) break;
+      if(*ref++ != *ip++) break;
+      if(*ref++ != *ip++) break;
+      if(*ref++ != *ip++) break;
+      while(ip < ip_bound)
+        if(*ref++ != *ip++) break;
+      break;
+    }
+
+    /* if we have copied something, adjust the copy count */
+    if(copy)
+      /* copy is biased, '0' means 1 byte copy */
+      *(op-copy-1) = copy-1;
+    else
+      /* back, to overwrite the copy count */
+      op--;
+
+    /* reset literal counter */
+    copy = 0;
+
+    /* length is biased, '1' means a match of 3 bytes */
+    ip -= 3;
+    len = ip - anchor;
+
+    /* encode the match */
+#if FASTLZ_LEVEL==2
+    if(distance < MAX_DISTANCE)
+    {
+      if(len < 7)
+      {
+        *op++ = (len << 5) + (distance >> 8);
+        *op++ = (distance & 255);
+      }
+      else
+      {
+        *op++ = (7 << 5) + (distance >> 8);
+        for(len-=7; len >= 255; len-= 255)
+          *op++ = 255;
+        *op++ = len;
+        *op++ = (distance & 255);
+      }
+    }
+    else
+    {
+      /* far away, but not yet in the another galaxy... */
+      if(len < 7)
+      {
+        distance -= MAX_DISTANCE;
+        *op++ = (len << 5) + 31;
+        *op++ = 255;
+        *op++ = distance >> 8;
+        *op++ = distance & 255;
+      }
+      else
+      {
+        distance -= MAX_DISTANCE;
+        *op++ = (7 << 5) + 31;
+        for(len-=7; len >= 255; len-= 255)
+          *op++ = 255;
+        *op++ = len;
+        *op++ = 255;
+        *op++ = distance >> 8;
+        *op++ = distance & 255;
+      }
+    }
+#else
+
+    if(FASTLZ_UNEXPECT_CONDITIONAL(len > MAX_LEN-2))
+      while(len > MAX_LEN-2)
+      {
+        *op++ = (7 << 5) + (distance >> 8);
+        *op++ = MAX_LEN - 2 - 7 -2; 
+        *op++ = (distance & 255);
+        len -= MAX_LEN-2;
+      }
+
+    if(len < 7)
+    {
+      *op++ = (len << 5) + (distance >> 8);
+      *op++ = (distance & 255);
+    }
+    else
+    {
+      *op++ = (7 << 5) + (distance >> 8);
+      *op++ = len - 7;
+      *op++ = (distance & 255);
+    }
+#endif
+
+    /* update the hash at match boundary */
+    HASH_FUNCTION(hval,ip);
+    htab[hval] = ip++;
+    HASH_FUNCTION(hval,ip);
+    htab[hval] = ip++;
+
+    /* assuming literal copy */
+    *op++ = MAX_COPY-1;
+
+    continue;
+
+    literal:
+      *op++ = *anchor++;
+      ip = anchor;
+      copy++;
+      if(FASTLZ_UNEXPECT_CONDITIONAL(copy == MAX_COPY))
+      {
+        copy = 0;
+        *op++ = MAX_COPY-1;
+      }
+  }
+
+  /* left-over as literal copy */
+  ip_bound++;
+  while(ip <= ip_bound)
+  {
+    *op++ = *ip++;
+    copy++;
+    if(copy == MAX_COPY)
+    {
+      copy = 0;
+      *op++ = MAX_COPY-1;
+    }
+  }
+
+  /* if we have copied something, adjust the copy length */
+  if(copy)
+    *(op-copy-1) = copy-1;
+  else
+    op--;
+
+#if FASTLZ_LEVEL==2
+  /* marker for fastlz2 */
+  *(flzuint8*)output |= (1 << 5);
+#endif
+
+  return op - (flzuint8*)output;
+}
+
+static FASTLZ_INLINE int FASTLZ_DECOMPRESSOR(const void* input, int length, void* output, int maxout)
+{
+  const flzuint8* ip = (const flzuint8*) input;
+  const flzuint8* ip_limit  = ip + length;
+  flzuint8* op = (flzuint8*) output;
+  flzuint8* op_limit = op + maxout;
+  flzuint32 ctrl = (*ip++) & 31;
+  int loop = 1;
+
+  do
+  {
+    const flzuint8* ref = op;
+    flzuint32 len = ctrl >> 5;
+    flzuint32 ofs = (ctrl & 31) << 8;
+
+    if(ctrl >= 32)
+    {
+#if FASTLZ_LEVEL==2
+      flzuint8 code;
+#endif
+      len--;
+      ref -= ofs;
+      if (len == 7-1)
+#if FASTLZ_LEVEL==1
+        len += *ip++;
+      ref -= *ip++;
+#else
+        do
+        {
+          code = *ip++;
+          len += code;
+        } while (code==255);
+      code = *ip++;
+      ref -= code;
+
+      /* match from 16-bit distance */
+      if(FASTLZ_UNEXPECT_CONDITIONAL(code==255))
+      if(FASTLZ_EXPECT_CONDITIONAL(ofs==(31 << 8)))
+      {
+        ofs = (*ip++) << 8;
+        ofs += *ip++;
+        ref = op - ofs - MAX_DISTANCE;
+      }
+#endif
+      
+#ifdef FASTLZ_SAFE
+      if (FASTLZ_UNEXPECT_CONDITIONAL(op + len + 3 > op_limit))
+        return 0;
+
+      if (FASTLZ_UNEXPECT_CONDITIONAL(ref-1 < (flzuint8 *)output))
+        return 0;
+#endif
+
+      if(FASTLZ_EXPECT_CONDITIONAL(ip < ip_limit))
+        ctrl = *ip++;
+      else
+        loop = 0;
+
+      if(ref == op)
+      {
+        /* optimize copy for a run */
+        flzuint8 b = ref[-1];
+        *op++ = b;
+        *op++ = b;
+        *op++ = b;
+        for(; len; --len)
+          *op++ = b;
+      }
+      else
+      {
+#if !defined(FASTLZ_STRICT_ALIGN)
+        const flzuint16* p;
+        flzuint16* q;
+#endif
+        /* copy from reference */
+        ref--;
+        *op++ = *ref++;
+        *op++ = *ref++;
+        *op++ = *ref++;
+
+#if !defined(FASTLZ_STRICT_ALIGN)
+        /* copy a byte, so that now it's word aligned */
+        if(len & 1)
+        {
+          *op++ = *ref++;
+          len--;
+        }
+
+        /* copy 16-bit at once */
+        q = (flzuint16*) op;
+        op += len;
+        p = (const flzuint16*) ref;
+        for(len>>=1; len > 4; len-=4)
+        {
+          *q++ = *p++;
+          *q++ = *p++;
+          *q++ = *p++;
+          *q++ = *p++;
+        }
+        for(; len; --len)
+          *q++ = *p++;
+#else
+        for(; len; --len)
+          *op++ = *ref++;
+#endif
+      }
+    }
+    else
+    {
+      ctrl++;
+#ifdef FASTLZ_SAFE
+      if (FASTLZ_UNEXPECT_CONDITIONAL(op + ctrl > op_limit))
+        return 0;
+      if (FASTLZ_UNEXPECT_CONDITIONAL(ip + ctrl > ip_limit))
+        return 0;
+#endif
+
+      *op++ = *ip++; 
+      for(--ctrl; ctrl; ctrl--)
+        *op++ = *ip++;
+
+      loop = FASTLZ_EXPECT_CONDITIONAL(ip < ip_limit);
+      if(loop)
+        ctrl = *ip++;
+    }
+  }
+  while(FASTLZ_EXPECT_CONDITIONAL(loop));
+
+  return op - (flzuint8*)output;
+}
+
+#endif /* !defined(FASTLZ_COMPRESSOR) && !defined(FASTLZ_DECOMPRESSOR) */
diff --git a/contrib/libs/fastlz/fastlz.h b/contrib/libs/fastlz/fastlz.h
new file mode 100644
index 0000000000..5bce060a18
--- /dev/null
+++ b/contrib/libs/fastlz/fastlz.h
@@ -0,0 +1,102 @@
+/*  
+  FastLZ - lightning-fast lossless compression library
+
+  Copyright (C) 2007 Ariya Hidayat (ariya@kde.org)
+  Copyright (C) 2006 Ariya Hidayat (ariya@kde.org)
+  Copyright (C) 2005 Ariya Hidayat (ariya@kde.org)
+
+  Permission is hereby granted, free of charge, to any person obtaining a copy
+  of this software and associated documentation files (the "Software"), to deal
+  in the Software without restriction, including without limitation the rights
+  to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+  copies of the Software, and to permit persons to whom the Software is
+  furnished to do so, subject to the following conditions:
+
+  The above copyright notice and this permission notice shall be included in
+  all copies or substantial portions of the Software.
+
+  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+  IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+  FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+  AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+  LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+  OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
+  THE SOFTWARE.
+*/
+
+#ifndef FASTLZ_H
+#define FASTLZ_H
+
+#include "rename.h"
+
+#define FASTLZ_VERSION 0x000100
+
+#define FASTLZ_VERSION_MAJOR     0
+#define FASTLZ_VERSION_MINOR     0
+#define FASTLZ_VERSION_REVISION  0
+
+#define FASTLZ_VERSION_STRING "0.1.0"
+
+#if defined (__cplusplus)
+extern "C" {
+#endif
+
+/**
+  Compress a block of data in the input buffer and returns the size of 
+  compressed block. The size of input buffer is specified by length. The 
+  minimum input buffer size is 16.
+
+  The output buffer must be at least 5% larger than the input buffer  
+  and can not be smaller than 66 bytes.
+
+  If the input is not compressible, the return value might be larger than
+  length (input buffer size).
+
+  The input buffer and the output buffer can not overlap.
+*/
+
+int fastlz_compress(const void* input, int length, void* output);
+
+/**
+  Decompress a block of compressed data and returns the size of the 
+  decompressed block. If error occurs, e.g. the compressed data is 
+  corrupted or the output buffer is not large enough, then 0 (zero) 
+  will be returned instead.
+
+  The input buffer and the output buffer can not overlap.
+
+  Decompression is memory safe and guaranteed not to write the output buffer
+  more than what is specified in maxout.
+ */
+
+int fastlz_decompress(const void* input, int length, void* output, int maxout); 
+
+/**
+  Compress a block of data in the input buffer and returns the size of 
+  compressed block. The size of input buffer is specified by length. The 
+  minimum input buffer size is 16.
+
+  The output buffer must be at least 5% larger than the input buffer  
+  and can not be smaller than 66 bytes.
+
+  If the input is not compressible, the return value might be larger than
+  length (input buffer size).
+
+  The input buffer and the output buffer can not overlap.
+
+  Compression level can be specified in parameter level. At the moment, 
+  only level 1 and level 2 are supported.
+  Level 1 is the fastest compression and generally useful for short data.
+  Level 2 is slightly slower but it gives better compression ratio.
+
+  Note that the compressed data, regardless of the level, can always be
+  decompressed using the function fastlz_decompress above.
+*/  
+
+int fastlz_compress_level(int level, const void* input, int length, void* output);
+
+#if defined (__cplusplus)
+}
+#endif
+
+#endif /* FASTLZ_H */
diff --git a/contrib/libs/fastlz/rename.h b/contrib/libs/fastlz/rename.h
new file mode 100644
index 0000000000..143a9f08f4
--- /dev/null
+++ b/contrib/libs/fastlz/rename.h
@@ -0,0 +1,8 @@
+#ifndef rename_h_7d8f6576asdf5
+#define rename_h_7d8f6576asdf5
+
+#define fastlz_compress       yfastlz_compress
+#define fastlz_decompress     yfastlz_decompress
+#define fastlz_compress_level yfastlz_compress_level
+
+#endif
diff --git a/contrib/libs/fastlz/ya.make b/contrib/libs/fastlz/ya.make
new file mode 100644
index 0000000000..7f31ac0bec
--- /dev/null
+++ b/contrib/libs/fastlz/ya.make
@@ -0,0 +1,23 @@
+LIBRARY()
+
+LICENSE(MIT)
+
+LICENSE_TEXTS(.yandex_meta/licenses.list.txt)
+
+VERSION(0.1.0)
+
+OWNER(
+    g:contrib
+    g:cpp-contrib
+)
+
+NO_UTIL()
+
+NO_COMPILER_WARNINGS()
+
+SRCS(
+    fastlz.c
+    rename.h
+)
+
+END()