char *program_version     = "SREP 3.2", *program_date = "April 6, 2013";
char *program_description = "huge-dictionary LZ77 preprocessor   (c) Bulat.Ziganshin@gmail.com";
char *program_homepage    = "http://freearc.org/research/SREP.aspx";

/*
Full sources required to compile srep.cpp are available at http://freearc.org/Download-Alpha.aspx
All rights reserved. Mail me if you have any questions or want to buy a commercial license for the source code.


to do:
use mmap for uncompressed file and/or keep a few last uncompressed blocks in memory
  mmap только на последний гигабайт файла - чтобы не забивать память его содержимым; или просто буферизовать последний гигабайт?
-m3: проверять другие блоки с тем же hash, если match с первым оказался слишком короток
Быстрое вычисление хеша>4байт, например умножение 32*32->64, второй хеш типа (int[0]*C)/2+int[1]....
-l512 -c256 приводит к большому числу false positives:
  dll100 7.072.327 309.211 8.829   dll700 22.443.465 1.444.311 33.207    5g 332.911.300 13.556.124 454.055   lp2 338.343.016 26.385.285 1.447.763
  if (k==saved_k && saved_match_len+(i-saved_i)<MIN_MATCH)   return last_match_end;  // для -m3 - пропуск безнадёжных матчей
  сохранять 1-битные хеши от 4/8/16/32-байтных блоков чтобы быстро проверить, можно ли будет 256-байтный матч расширить до 512 байт
3% faster: обновлять хеш на ACCELERATOR байт за один шаг:  for (int j=0; j<ACCELERATOR; i++, j++)  update_hash (buf[i], buf[i+L]);
  1 шаг:  hash = hash*N+a0-b0*N^K                                                        (1 умножение, 1 выборка из памяти, 2 сложения)
  2 шага: hash = (hash*N+a0-b0*N^K)*N+a1-b1*N^K = hash*N^2+a0*N+a1-b0*N^(K+1)-b1*N^K     (1 умножение, 3 выборки из памяти, 4 сложения)
  4 шага: hash = hash*N^4+a0*N^3+a1*N^2+a2*N+a3-b0*N^(K+3)-b1*N^(K+2)-b2*N^(K+1)-b3*N^K  (1 умножение, 7 выборок из памяти, 8 сложений)
-m1f: сохранять по 256 байт с обоих сторон от матча, чтобы потом найти его точные границы
-f:
  BUG: в случае сбоя повторить распаковку этого блока ещё два раза, печатать число исправленных ошибок
  печатать сжатый размер с учётом разбиения матчей, пересекающих границу блока
BUG: -f (de)compression may place any number of LZ matches per block, not limited to 8mb/L (now patched by using ADDITIONAL_8MB)
error checking: make all printf in main thread, perform "goto cleanup" instead of error() after file open operations
use WinAPI to create VMFILE as temporary file not necessarily saved to disk
digestarr[chunk] may not be filled at all! in particular, for L!=2^n
put into HashTable chunks split between two input blocks (situation that's almost impossible when L==2^n)
like REP, allow to use larger MinMatchLen for small distances. пример для использования совместно с lzma:64mb :
  - при дистанции <64 мб и длине совпадения <4 кб - пропускаем эти данные на выход (не ища в них других совпадений!)
  - при дистанции <64 мб и длине совпадения >4 кб - кодируем
  - при дистанции >64 мб и длине совпадения >32 байт - кодируем
segmentation algorithm: split data into 128 kb blocks, build *full* index on 512-byte chunks, and compute amount of repeated bytes for every pair of blocks

b/g:
  отдельные треды для r/w и md5/sha1 (especially important for -m1 && ACCEL=16)
  выбор mmap/read/mmap+read, суммирование байтов через 4к для заполнения mmap-буфера

m/t:
  1. схватить ReadLock и прочитать блок
  2. получить от треда пред. блока small_index_head[]
  3. заполнить digestarr(SHA1) и hasharr(rolling hash), обновить копию small_index_head[] и отослать её треду след. блока
  4. сжать блок, используя поиск в small_index_head[] и full_index, обновляя small_index_head[]
  5. получить UpdateLock от предыдущего блока и обновить full_index with rolling hashes of the block (приостановив все остальные треды)
альтернативно - тупо использовать несколько потоков одновременно, игнорируя ссылки вперёд или превращая их в ссылки назад

альтернативная реализация m/t:
  1. Для ускорения перерасчёта sliding hash выполнять расчёты заранее и сохранить в памяти (один из каждых ACCELERATOR байт).
     К примеру, прочитанный блок 8 мб разбить на кусочки в 64 кб, индексируемые несколькими фоновыми потоками. Тогда основному потоку останется только
       проверять/обновлять хеш-таблицы
  2. Для ускорения обращений в память при работе с хеш-таблицами производить эти обращения также в фоновых потоках.
     Тогда в основном потоке эти данные будут "всегда готовы" (фоновые потоки должны обрабатывать данные не очень большими блоками чтобы данные остались в кеше)

SEP 3.2
  icl: faster on -a1, sha1/md5 slower than in CryptoAPI, slower with unlikely()
  gcc4: sha1/md5 faster than in CryptoAPI

SREP 4.0
  -m3: 1-bit hash for every L/8 bytes (try incremental hash of 256+32*i bytes) OR try "bit hashtab[32][256]"
       try multiple entries with the same 256-byte hash (-hN[x])
  single-pass compression and decompression (future-lz with matches stored at EOF)
  replace sha1 with cbc-mac(aes) or universal hashing with fortuna-generated key-array

SREP 5.0
  кеширование последних 100-1000 мб прочитанных данных (возможно через mmap) с точными матчами: -d1g:512:c128 (взять код из REP)
  3x ускорение работы (1050 -> 350 seconds):
    1. 509-byte hash1 + 512-byte hash2 (позволит находить все матчи даже при -a4/16 как при -a1)
    2. поменять hasharr и chunkarr местами (искать сначала хеш, а затем считывать из парал. массива его номер чанка)
    3. выбирать один максимальный из 32 хешей внутри 512-байтного блока, искать один лучший из 16 хешей (расход памяти как в -a1, число обращений в ОЗУ: 55 млрд/16=3.5 млрд)
           при 6 байтах/блок (48 бит) в bitarr число ложных попаданий ещё в 96 раз меньше, т.е. обращений в hasharr - 35млн ложных+7млн истинных
    4. делать prefetch из bitarr на 10-30 позиций вперёд, совмещая выборку из памяти и вычисление hash1/hash2
    5. отдельный цикл пропуска matched data - только добавление, без вычитаний, поскольку нам не нужно проверять bitarr

Просто быстрый алгоритм (без bitarr):
  1. читаем байты из буфера через xmm-регистры; передвигаем CRC64 на один байт (2 memread + xor + shift); делаем prefetch из hasharr; запоминаем crc64 через xmm-регистр
  2. читаем crc64 через xmm; делаем выборку 16 байт из hasharr; ищем среди них старшее слово crc64; при необходимости - читаем след. слово из hasharr
  скорость ограничена числом выборок из памяти (hasharr) - 20 нс/выборку

Экстремально быстрый алгоритм (с bitarr, без content-based champions selection):
  1. обновляем crc32c (509 bytes) на 4/8/16 байта (crc32c+3*clmul/8байт), делаем prefetch из bitarr, запоминаем crc32c через xmm: на всё нужно 1-2 такта
  2. в след. цикле проверяем байт из bitarr, при успехе вычисляем скользящий 64-bit hash2(512 bytes) и делаем 4-8-16 выборок из hasharr (видимо, crc64):
         порядка миллиарда попаданий = хеширование 512 гбайт = 20-30 секунд на 100 гбайт файл, т.е. 1 такт/1 байт файла
  3. в след. цикле (?) сравниваем хеши из hasharr со старшими словами соответствующих hash2, при успехе регистрируем условный матч и находим его условную длину по hash2
  4. для окончательной проверки матча вместо sha1 - aes-based hashing (0.5sec/gb на calc+check, причём всё - в потоке I/O)

SREP x.x
  509'byte-based hash1 (hasharr[] contains 512'byte-based hash2 values)
  bcj/dispack/lz4/tor/lzma/delta
  overlap hashing with memaccess (prefetch, compute hashnew, hash=hanshnew unless check_match_possibility() returned true)
  hasharr += chunkarr (reduce mem accesses). alternatively: search first in hasharr, indexed by hash+hash2. once hasharr[i]==hash2 found, read chunkarr[i]
  -m3 - сохранять по 1 биту хеша от каждых 32 байт (int[0]*C)/2+int[1]...) для быстрой проверки макс. возможной длины матча
  -m3 - сохранять несколько позиций на пробу
  фоновый поток вычисления хешей + prefetch из хеш-таблицы за ~20 проверок вперёд
  тред I/O, тред md5, два треда sha1 (dynaload CryptHashData/CryptHashMessage win32 function?)
  не слишком длинные матчи (32-1024 байт?) в пределах небольших дистанций (64-1024 мб) должны запрещать дальнейшие матчи <1024 байт до своего конца?
  asm/SSE code for sha1/md5 (in particular intel sse2 sha1 implementation), replace md5 with non-broken cryptohash
  после нахождения match вычислять sha1 нескольких блоков вперёд можно параллельно поскольку типичный match имеет длину порядка 10 блоков
     (или после того, как проверенная длина совпадения превысила например 4*L, также можно сравнивать с одним-трёмя последними блоками для простых повторяющихся паттернов)
  add_hash/mark_match_possibility - делать только prefetch с фактическим выполнением в следующем цикле по L (4% ускорения)
  перед началом обработки буфера вставить все его 512-байтные блоки в хеш, не удаляя предыдущие записи (новые окажутся в конце хеш-цепочек);
     затем можно разбить буфер на 8 частей и искать матчи в них параллельно; причём вставку в хеш для *следующего* буфера можно делать параллельно с этим поиском
  -a should also enlarge bitarr (it doesn't help now - probably due to TLB overflow)
  hdd-to-hdd compression: 10% of real time spent in disk seeks (see srep-on-slow-HDD)
  botan: optimized sha1/md5/sha2 code
  hash2 - не скользящий, а быстровычисляемый (поскольку использовать его приходится не так уж и часто - 4% всех позиций)

SREP high-level
  1. I/O через внешние команды с проверкой exit code (там где возможно его делать чисто последовательно)
  2. многопоточное tor/lzma дожатие сжатых блоков
  3. использовать по умолчанию режим с записью полного списка матчей в конце сжатого файла (вариант -f с одним проходом при сжатии)

При сохранении идеологии полного поиска (вместо якорного хеширования) возможны следующие оптимизации:
  совместить выборку из памяти (делая prefetch) с обновлением хеша - сделает ненужным unrolled_update_hash
  совместить назад chunkarr и hasharr (5% faster on -a4, -a1==-a0==no bitarr)
  Избавиться от LLC misses в h.check_match_possibility() с помощью предвыборки (хешируем max(L,256) байт вперёд, запоминаем хеш,
      делаем предвыборку для h.check_match_possibility() и запоминаем её адрес). Возможно, это позволит избавиться от ACCELERATOR
  Вынести прехеширование+предвыборку в отдельный поток

Проблемы якорного хеширования: смещения, на которых сработает якорь, непредсказуемы, поэтому прохешированные блоки должны либо перекрываться, либо между ними будут
  оставаться промежутки. Далее SHA1 должен сохраняться либо от прохешированных блоков (вызывая те же самые перекрытия либо промежутки), либо их границы не будут совпадать
  с границами прохешированных блоков, в результате чего нельзя будет проверить совпадение прохешированного якорного блока со старым. Вероятно, второй вариант предпочтительней,
  поскольку совпадения не должны быть ровно L байт, обычно они продолжаются несколько дольше в обе стороны.

Якорное хеширование:
  файл разбивается на фиксированные блоки по 512 байт, из каждого блока выделяются "лучшие" 256 байт (например с макс. хеш-суммой) со смещением offset относ. начала блока
  для каждого 256-байтного блока запоминаются: chunk (4 bytes) + hash256 (4 bytes) + offset (2-4 bytes) + hash512 (2-4 bytes)
  при сканировании файла из каждых 64-256 позиций выбирается "лучшая", по hash256 ищутся похожие блоки, которые полностью сопоставляются по hash512

Полу-якорное хеширование:
  Берём K подблоков блока длины L, каждый длиной L-K+1. Выбираем из них C наибольших, или все удовлетворящие некоему условию (lb(K) старших бит равны 0 и т.д.).
  Заносим их в bitarr. При поиске проверяем по bitarr только блоки длины l-K+1, удовлетворяющие тому же условию.
  Например, из 32 подблоков длины L-31 заносим один с наибольшей хеш-суммой. При поиске выбираем из каждых 16 блоков длины L-31 один с наиб. суммой и ищем в bitarr только его.
  Отсутствие его отметки в bitarr гарантирует (?) отсутствие матча (поскольку макс. из 16 выровненных блоков должен включат макс. из 32 невыровненных).

Further optimizations:
  найти способ проверять целый байт вместо отдельного бита без существенной потери точности предсказания
      например разбить файл на 8 кусков и чекинить в первом куске только в первый бит и т.д.
      или в первом байте цикла до ACCEL устанавливать первый бит проиндекированного байта и т.д.: for (i=0..ACCEL-1)  bitarr [hash[j-L+i..j+i]] ~= (1<<i)
  найти способ повысить точность предсказания в том же объёме памяти (например определять какие конкретно из ACCEL позиций можно использовать - 15% ускорение при -a4)
  запоминать/проверять хеш от L-ACCEL+1 байт чтобы избежать потери блоков, в которых с эталоном не совпадают ACCEL-1 байт перед блоком или после него
      использовать в check хеш от 509 байт, а в find хеш от 512 байт?
  оптимизировать использование битов в хеше, например не использовать малоинформативные младшие биты (постараться исключить sha1 mismatches)

При сжатии: после len==0 обновлять инд. прогресса и только потом выходить (чтобы учесть время записи последнего буфера - добиться совпадения времён с выводом timer)
*/

#include <algorithm>
#include <set>
#include <stack>
#include <vector>
#include <malloc.h>
#include <math.h>
#include <stdarg.h>
#include <stdio.h>

#include "../Common.h"
#include "../Compression.h"

// Constants defining compressed file format
const uint SREP_SIGNATURE = 0x50455253;
const uint SREP_FORMAT_VERSION1 = 1;
const uint SREP_FORMAT_VERSION2 = 2;
const uint SREP_FORMAT_VERSION3 = 3;
const uint SREP_FORMAT_NOMD5    = 256;
enum SREP_METHOD {SREP_METHOD1=1, SREP_METHOD2, SREP_METHOD3};
typedef uint32 STAT;
const int STAT_BITS = 32;
const char* SREP_EXT = ".srep";

// Program exit codes
enum { NO_ERRORS         = 0
     , WARNINGS          = 1
     , ERROR_CMDLINE     = 2
     , ERROR_IO          = 3
     , ERROR_COMPRESSION = 4
     , ERROR_MEMORY      = 5
     };

typedef uint64 Offset;               // Filesize or position inside file


static struct {Offset max_offset, find_match, find_match_memaccess, check_hasharr, hash_found, check_len, record_match, total_match_len;} pc;


// //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Win32 СryptoAPI: SHA-1 & MD5 *************************************************************************************************************************
// //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

#define SHA1_SIZE 20
#define MD5_SIZE  16


#if 0   // #ifdef FREEARC_WIN : unfortunately, it doesnt' show consistent speed improvement. Also, CryptoAPI functions should be dynaloaded from the Advapi32.dll (available since WinXP)

#include <Wincrypt.h>
struct Win32CryptoAPI
{
  HCRYPTPROV hCryptProv;

  // Acquire/release handle to a cryptography provider context.
  Win32CryptoAPI()   {CryptAcquireContext (&hCryptProv, NULL, NULL, PROV_RSA_FULL, 0);}
  ~Win32CryptoAPI()  {CryptReleaseContext (hCryptProv, 0);}

  bool hash (ALG_ID alg, DWORD count, void *buf, int size, void *result)
  {
    HCRYPTHASH hHash;
    if(!CryptCreateHash (hCryptProv, alg, 0, 0, &hHash))                   return false;
    if(!CryptHashData (hHash, (BYTE*)buf, size, 0))                        return false;
    if(!CryptGetHashParam (hHash, HP_HASHVAL, (BYTE*)result, &count, 0))   return false;
    CryptDestroyHash (hHash);
    return true;
  }

  bool sha1 (void *buf, int size, void *result)  {return hash (CALG_SHA1, SHA1_SIZE, buf, size, result);}
  bool md5  (void *buf, int size, void *result)  {return hash (CALG_MD5,  MD5_SIZE,  buf, size, result);}

} CryptoAPI;

#else

static struct
{
  bool sha1 (void *buf, int size, void *result)  {return false;}
  bool md5  (void *buf, int size, void *result)  {return false;}
} CryptoAPI;

#endif


// //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// LibTomCrypt: SHA-1 & MD5 *************************************************************************************************************************
// //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

#include "../_Encryption/crypt/crypt_argchk.c"
#include "../_Encryption/hashes/md5.c"
#include "../_Encryption/hashes/sha1.c"

typedef unsigned char Digest[SHA1_SIZE];

void compute_digest (void *buf, int size, Digest &result)
{
  if (CryptoAPI.sha1 (buf, size, result))  return;
  hash_state state;
  sha1_init    (&state);
  sha1_process (&state, (unsigned char*)buf, (unsigned long)size);
  sha1_done    (&state, result);
}


typedef unsigned char Checksum[MD5_SIZE];

void compute_checksum (void *buf, int size, void *result)
{
  if (CryptoAPI.md5 (buf, size, result))  return;
  hash_state state;
  md5_init    (&state);
  md5_process (&state, (unsigned char*)buf, (unsigned long)size);
  md5_done    (&state, (unsigned char*)result);
}



// //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Memory-mapped files ******************************************************************************************************************************
// //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

#ifdef FREEARC_WIN

#include <io.h>
#include <windows.h>

struct MMAP_FILE
{
  bool   initialized;
  FILE  *file;
  char*  iomode;
  Offset filesize;
  HANDLE mmapHandle;
  char  *mmapPtr;

  MMAP_FILE (bool use_mmap, FILE *_file, char* _iomode, Offset _filesize) : initialized(!use_mmap), file(_file), iomode(_iomode), filesize(_filesize), mmapHandle(NULL), mmapPtr(NULL) {}

  // Initialize only on first use
  void initialize()
  {
    if (initialized) return;
    initialized = true;

    HANDLE osfhandle = (HANDLE) _get_osfhandle(fileno(file));
    DWORD  access    = (strequ(iomode,"r")? PAGE_READONLY : PAGE_READWRITE);
    mmapHandle = CreateFileMapping (osfhandle, NULL, access, 0, 0, NULL);

    if (mmapHandle)
    {
      DWORD access = (strequ(iomode,"r")? FILE_MAP_READ :
                     (strequ(iomode,"w")? FILE_MAP_WRITE :
                                          FILE_MAP_ALL_ACCESS));
      mmapPtr = (char*) MapViewOfFile (mmapHandle, access, 0, 0, 0);
    }
  }

  // File was successully memory-mapped
  bool mmapped()
  {
    initialize();
    return (mmapHandle && mmapPtr);
  }

  // Read len bytes at offset pos; return number of bytes read
  // Data are read either into internal buffer or into provided buf[];  this address placed into *ptr
  int read (char **ptr, void *buf, Offset pos, int len, FILE *f = NULL)
  {
    if (mmapped()) {                                           // File was successully memory-mapped, return memory address corresponding to pos
      *ptr = mmapPtr+pos;
      return pos>filesize? 0 : mymin (filesize-pos, len);
    } else {                                                   // Memory-mapping isn't active, perform I/O operation into user-supplied buffer
      *ptr = (char*) buf;
      file_seek(f?f:file,pos);
      return file_read(f?f:file,buf,len);
    }
  }

  ~MMAP_FILE()
  {
    if (!initialized) return;
    UnmapViewOfFile(mmapPtr);
    CloseHandle(mmapHandle);
  }
};


#else  //!FREEARC_WIN


struct MMAP_FILE
{
  FILE  *file;

  MMAP_FILE (bool, FILE *_file, char*, Offset) : file(_file) {}

  bool mmapped()  {return false;}   // File ISN'T memory-mapped

  // Read len bytes at offset pos; return number of bytes read
  // Data are read either into internal buffer or into provided buf[];  this address placed into *ptr
  int read (char **ptr, void *buf, Offset pos, int len, FILE *f = NULL)
  {
    *ptr = (char*) buf;
    file_seek(f?f:file,pos);
    return file_read(f?f:file,buf,len);
  }
};

#endif


// //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Memory allocation ********************************************************************************************************************************
// //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

enum ForceMode {FORCE, DISABLE, TRY};

void *MyBigAlloc (size_t size, ForceMode LargePageMode)
{
  void *address = 0;

#ifdef FREEARC_WIN
  if (LargePageMode!=DISABLE)
  {
    HANDLE hToken = 0;
    LUID luid;
    TOKEN_PRIVILEGES tp;
    OpenProcessToken (GetCurrentProcess(), TOKEN_ADJUST_PRIVILEGES, &hToken);
    LookupPrivilegeValue (NULL, TEXT("SeLockMemoryPrivilege"), &luid);
    tp.PrivilegeCount = 1;
    tp.Privileges[0].Luid = luid;
    tp.Privileges[0].Attributes = SE_PRIVILEGE_ENABLED;
    AdjustTokenPrivileges (hToken, FALSE, &tp, sizeof(tp), 0, 0);
    CloseHandle (hToken);

    typedef SIZE_T (WINAPI *GetLargePageMinimumP)();
    GetLargePageMinimumP largePageMinimum  =  (GetLargePageMinimumP) GetProcAddress(GetModuleHandle(TEXT("kernel32.dll")), "GetLargePageMinimum");
    SIZE_T  page  =  largePageMinimum? largePageMinimum() : 0;

    const DWORD MY_MEM_LARGE_PAGES = 0x20000000;
    if (page  &&  (size>=page || LargePageMode==FORCE))
      address = ::VirtualAlloc(0, roundUp(size,page), MEM_COMMIT | MY_MEM_LARGE_PAGES | MEM_TOP_DOWN, PAGE_READWRITE);
  }
#endif

  if (address==0 && LargePageMode!=FORCE)
    address = BigAlloc(size);
  return address;
}


// //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Hash table ***************************************************************************************************************************************
// //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

typedef size_t HashValue;            // Hash of L-byte block, used as first step to find the match
typedef uint32 StoredHashValue;      // Hash value stored in hasharr[]
typedef uint32 Chunk;                // Uncompressed file are splitted into L-byte chunks, it's the number of chunk in the file
const Chunk  MAX_CHUNK = Chunk(-1),  NOT_FOUND = 0;
const int MAX_HASH_CHAIN = 12;

#define min_hash_size(n)   (((n)/4+1)*5)     /* Minimum size of hash for storing n elements */

// Value saved in hasharr[]
StoredHashValue stored_hash (HashValue hash, HashValue hash2)
{
  // DISABLED: 64-bit: combine 32-bit halves of hash===hash2 into 32-bit value (HSHIFT==32)
  // DISABLED: 32-bit: combine 32-bit hash and hash2 into 32-bit value         (HSHIFT==0)
  const int HSHIFT  =  CHAR_BIT * (sizeof(HashValue) - sizeof(StoredHashValue));
  return (hash>>HSHIFT);
}


#if defined(_M_X64) || defined(_M_AMD64) || defined(__x86_64__)
#define _32_or_64(_32,_64) (_64)
#define _32_only(_32)      (void(0))
#define hashx hash                   /* 64-bit code updates and uses only one 64-bit hash variable */
typedef size_t NUMBER;               // best choice for loop index variables on most 64-bit compilers
#else
#define _32_or_64(_32,_64) (_32)
#define _32_only(_32)      (_32)
#define hashx hash2                  /* 32-bit code updates and uses two 32-bit variables: hash and hash2  */
typedef int NUMBER;                  // best choice for loop index variables on most 32-bit compilers
#endif


// Improves -m3 by filtering out part of false matches.
// The first version proved to be very inefficient (only ~20% of false matches are recognized),
// thus disabled by return's until improved implementation will arrive.
struct SliceHash
{
  typedef uint32 entry;
  entry *h;  // Array holding all slice hashes
  size_t L, slices_in_block, check_slices, slice_size;

  SliceHash (Offset filesize, int _L) : L(_L)
  {
return;
    h               = (entry*) BigAlloc (filesize/L * sizeof(entry));
    slices_in_block = sizeof(entry)*CHAR_BIT;
    check_slices    = slices_in_block-2;       // If less that this amount of slices around match has the same hashes, then we are sure that match can't be extended to min_match size
    slice_size      = L/slices_in_block;       //   to do: support L!=min_match/2, 8/16-byte entry (считывать в check по одному байту из h)
  }

  // Hash of these bytes
  static size_t hash (void *ptr, int size)
  {
    size_t hash = 111222341; //111222333444555666777888999;
    for (char *p = (char*)ptr;  (char*)p < (char*)ptr+size;  p++)
      hash  =  (hash*123456791) + *p;
    return (hash*123456791) >> (sizeof(size_t)*CHAR_BIT-1);   // use parity instead?!
  }

  // Fill h[] with hashes of slices of each chunk in the buf
  void prepare_buffer (Offset offset, char *buf, int size)
  {
return;
    Chunk curchunk = offset/L;
    for (char *p = buf;  p < buf+size;  )
    {
      size_t checksum = 0;
      for (int i=0;  i<slices_in_block;  i++, p+=slice_size)
        checksum  +=  hash(p,slice_size) << i;
      h[curchunk++] = checksum;
    }
  }

  bool check (Chunk chunk, void *p)
  {
return true;
    size_t checksum = h[chunk+1];  int i,k;
    for (i=0; ; i++)
    {
      if (i==check_slices)
        return true;
      if ((checksum>>i) & 1  !=  hash ((char*)p+L+i*slice_size, slice_size))
        break;
    }
    checksum = h[chunk-1];
    for (k=0; ; k++)
    {
      if (k+i==check_slices)
        return true;
      if ((checksum>>(slices_in_block-(k+1))) & 1  !=  hash ((char*)p-(k+1)*slice_size, slice_size))
        break;
    }
    return false;
  }
};


struct HashTable
{
  bool ROUND_MATCHES;
  bool COMPARE_DIGESTS;
  size_t L;
  MMAP_FILE &mmap_infile;
  Offset filesize;
  Offset hs;
  size_t hashsize, hashsize1, hash_shift;
  Digest          *digestarr;
  StoredHashValue *hasharr;
  Chunk           *chunkarr;
  SliceHash        slicehash;

  // bitarr[] used for fast probing of hash values - it helps to detect whether we ever seen such hash value before
  size_t  bitarrsize;
  size_t  bitshift;
  BYTE   *bitarr;

  HashTable (bool _ROUND_MATCHES, bool _COMPARE_DIGESTS, unsigned _L, unsigned BITARR_ACCELERATOR, MMAP_FILE &_mmap_infile, Offset _filesize, ForceMode LPMode)
    : mmap_infile(_mmap_infile), slicehash(_filesize,_L)
  {
    ROUND_MATCHES = _ROUND_MATCHES;  COMPARE_DIGESTS = _COMPARE_DIGESTS;  L = _L;  filesize = mymax(_filesize,L);
    digestarr = NULL;  hasharr = NULL;  chunkarr = NULL;  bitarr = NULL;
    hs = roundup_to_power_of (min_hash_size(filesize/L), 2);
    if (hs > size_t(-1)  ||  filesize/L > MAX_CHUNK)  return;
    hashsize = hs,  hashsize1 = hashsize-1,  hash_shift = sizeof(HashValue)*CHAR_BIT - lb(hashsize);
    bitarrsize = roundup_to_power_of (mymax(filesize/L/CHAR_BIT * BITARR_ACCELERATOR, 2), 2);   // bit array checking works fine until 1/8 of bitarr[] gets filled
    bitshift   = sizeof(HashValue)*CHAR_BIT - lb(bitarrsize);    // bitarrsize should be >=2, otherwise hash>>bitshift == hash>>64 == hash>>0 and indexing panics

    // Allocate arrays starting with the most frequently accessed (to increase their chances to become allocated with large pages)
    bitarr      = (BYTE*)            MyBigAlloc (bitarrsize                          , LPMode);    if (!bitarr   && bitarrsize!=0) return;
    chunkarr    = (Chunk*)           MyBigAlloc (hashsize   * sizeof(Chunk)          , LPMode);    if (!chunkarr ) return;
    hasharr     = (StoredHashValue*) MyBigAlloc (filesize/L * sizeof(StoredHashValue), LPMode);    if (!hasharr  ) return;
    if (COMPARE_DIGESTS)
     {digestarr = (Digest*)          MyBigAlloc (filesize/L * sizeof(Digest)         , LPMode);    if (!digestarr) return;}

    if (bitarr)
      for (size_t i=0; i<bitarrsize; i++)  bitarr[i]   = 0;
    for   (size_t i=0; i<hashsize;   i++)  chunkarr[i] = NOT_FOUND;
  }
  ~HashTable() {BigFree(bitarr); BigFree(hasharr); BigFree(chunkarr); BigFree(digestarr);}

  // Return errcode if any
  int errcode()  {return (COMPARE_DIGESTS && !digestarr) || !chunkarr || !hasharr || (!bitarr && bitarrsize!=0)?  ERROR_MEMORY  :  NO_ERRORS;}

  // How much memory required for hash tables with given file and compression method settings
  Offset memreq() {return hs * sizeof(*chunkarr)
                        + filesize/L * (sizeof(*hasharr) + (COMPARE_DIGESTS? sizeof(*digestarr) : 0))
                        + bitarrsize;}

  // Performed once for each block read
  void prepare_buffer (Offset offset, char *buf, int size)
  {
    if (COMPARE_DIGESTS) {                                        // Save chunk digests for secondary, reliable match checking
      Chunk curchunk = offset/L;
      for (char *p = buf;  p < buf+size;  p += L)
        compute_digest (p, L, digestarr[curchunk++]);
    }
    slicehash.prepare_buffer (offset, buf, size);
  }

  // Compute chunkarr[] index for given hash value h
  size_t index (size_t h)  {return h&hashsize1;}   // don't use higher bits of h since they may be lost here (unsigned != HashValue)

  // A quick first probe using bitarr[]
  template <unsigned ACCELERATOR>  bool check_match_possibility (HashValue hash)  {return ACCELERATOR!=0?  (bitarr[hash>>bitshift]  &  (1<<(size_t(hash)&(CHAR_BIT-1)))) : true;}
  template <unsigned ACCELERATOR>  void mark_match_possibility  (HashValue hash)  {if    (ACCELERATOR!=0)   bitarr[hash>>bitshift]  |=  1<<(size_t(hash)&(CHAR_BIT-1));}

  // Add chunk pointed by p to hash
  void add_hash (void *p, Offset offset, HashValue hash, HashValue hash2)
  {
    Chunk curchunk = offset/L;
    hasharr[curchunk] = stored_hash(hash,hash2);   // save hash of chunk for primary, quick match checking
    if (curchunk == NOT_FOUND)  return;            // it's impossible to hash the chunk having such offset since it's used as signal value

    size_t h = hash2;  int limit = MAX_HASH_CHAIN;
    for (Chunk chunk;  (chunk = chunkarr[index(h)]) != NOT_FOUND  &&  --limit;  )
    {
      // Replace in hash chunk with the same digest (for -m1) or hash value (for -m2), supposing that it has the same contents
      if (hasharr[chunk] == stored_hash(hash,hash2))
        if (!COMPARE_DIGESTS  ||  0==memcmp(digestarr[chunk], digestarr[curchunk], sizeof(*digestarr)))
          break;
      h++, ((limit&3)==0) && (h=h*123456791+(h>>16)+462782923);  // compute next hash slot
    }
    chunkarr[index(h)] = curchunk;
  }

  // Find previous L-byte chunk with the same contents
  Chunk find_match (void *p, HashValue hash, HashValue hash2, Offset new_offset)
  {
    pc.find_match++;
    size_t h = hash2;  int limit = MAX_HASH_CHAIN;
    for (Chunk chunk;  (chunk = chunkarr[index(h)]) != NOT_FOUND  &&  --limit;  )
    {
      Offset match_offset  =  new_offset - Offset(chunk)*L;
      if (match_offset < pc.max_offset)  pc.check_hasharr++;
      // If hash value is the same...
      if (hasharr[chunk] == stored_hash(hash,hash2))
      {
        if (match_offset < pc.max_offset)  pc.hash_found++;
        // ... we either suppose that chunks are the same (for -m2/-m3)
        if (!COMPARE_DIGESTS)
        {
          if (slicehash.check (chunk, p))
            return chunk;
        }
        else
        {
          // ... or compare their digests (for -m1)
          Digest dig;
          compute_digest (p, L, dig);
          if (0==memcmp(dig, digestarr[chunk], sizeof(dig)))
            return chunk;
        }
      }
      h++, ((limit&3)==0) && (pc.find_match_memaccess++, h=h*123456791+(h>>16)+462782923);  // compute next hash slot
    }
    return NOT_FOUND;
  }

  // Length of match, in bytes
  unsigned match_len (Chunk start_chunk, char *min_p, char *start_p, char *last_p, Offset offset, char *buf, unsigned *add_len)
  {
    Offset new_offset = offset+(start_p-buf);
    Offset old_offset = Offset(start_chunk)*L;
    if (new_offset-old_offset < pc.max_offset)  pc.check_len++;
    char *p = start_p;  *add_len = 0;

    // Comparing with data before the current block
    if (COMPARE_DIGESTS)
    {
      // -m1: check match by using saved digests of old chunks
      while (p += L, (old_offset += L) < offset)        // Skip checking first chunk since it was already done in find_match()
      {
        if (last_p-p < L)                               // We have no L-byte chunk to digest
          goto stop;

        Digest dig;                                     // Compare two L-byte blocks by comparison of their digests
        compute_digest (p, L, dig);
        if (0!=memcmp(dig, digestarr[old_offset/L], sizeof(dig)))
          goto stop;
      }
    }
    else if (old_offset < offset)
    { // -m2/-m3: check match by rereading old data from infile

      // !ROUND_MATCHES: First, compare bytes before match start (which is rounded to L-byte chunk boundary)
      int n = mymin (old_offset, mymin(L, start_p-min_p));   // how much bytes we can check
      if (n > 0  &&  !ROUND_MATCHES)
      {
        // Compare n bytes before start_p
        char *old = (char*) alloca(n);
        int len = mmap_infile.read(&old,old,old_offset-n,n), i;
        if (len != n)  goto stop;
        for (i=1;  i <= n  &&  start_p[-i] == old[n-i];  i++);
        *add_len = i-1;
      }

      // Second, compare bytes after match start
      const int BUFSIZE = 4096;
      for (;  old_offset < offset;  old_offset += BUFSIZE)
      {
        char *old, oldbuf[BUFSIZE];                                   // Buffer for old data
        int len = mmap_infile.read(&old,oldbuf,old_offset,BUFSIZE);   // Read old data from file
        if (len != BUFSIZE)  goto stop;                               // If there was any problem reading entire buf
        for (char *q = old;  q < old+len;  p++, q++)
          if (p==last_p  ||  *p != *q)  goto stop;                    // Exit function once we've found end of match
      }
    }
    else if (!ROUND_MATCHES)
    {
      // !ROUND_MATCHES: compare bytes (that are present in current block) before match start
      int i, n = mymin (old_offset-offset, mymin(L, start_p-min_p));   // how much bytes we can check
      for (i=1;  i <= n  &&  start_p[-i] == (buf+(old_offset-offset))[-i];  i++);
      *add_len = i-1;
    }

    // Comparing with data in the current block
    for (char *q = buf+(old_offset-offset);
         p < last_p  &&  *p == *q;
         p++,q++);

    stop:  return p-start_p + *add_len;
  }
};



// //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Match handling ***********************************************************************************************************************************
// //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

// Structure storing LZ match info
struct LZ_MATCH
{
  LZ_MATCH() : src(Offset(-1)), dest(Offset(-1)), len(STAT(-1)) {}
  Offset src, dest;  // LZ match source & destination absolute positions in file
  STAT   len;        // Match length
};

// Compare LZ matches by source position (for lz_matches[])
bool order_by_LZ_match_src (const LZ_MATCH &left, const LZ_MATCH &right)
{
  return (left.src < right.src);
}


// Maximum number of STAT values per compressed block. For every L input bytes, we can write up to 4 STAT values to statbuf
#define MAX_STATS_PER_BLOCK(block_size, L) (((block_size)/(L)+1)*4)

// Number of STAT values used to encode one LZ match
#define STATS_PER_MATCH(ROUND_MATCHES) (ROUND_MATCHES? 3:4)

// Encode one LZ record to stat[]
#define ENCODE_LZ_MATCH(stat, ROUND_MATCHES, L,  lit_len, lz_match_offset, lz_match_len)                                                             \
  unsigned L1 = (ROUND_MATCHES? L : 1);                                           /* lz_match_len should be divisible by L in -m1 and -m2 modes */   \
  *stat++ = (lit_len);                                                                                                                               \
  *stat++ = (lz_match_offset)/L1;                                                                                                                    \
  if (!ROUND_MATCHES)  *stat++ = ((lz_match_offset)/L1) >> STAT_BITS;                                                                                \
  *stat++ = ((lz_match_len)-L)/L1;

// Decode one LZ record from stat[]
#define DECODE_LZ_MATCH(stat, REVERSED_LZ, ROUND_MATCHES, L, basic_pos,  lit_len, LZ_MATCH_TYPE, lz_match)                                           \
  unsigned L1              = (ROUND_MATCHES? L : 1);                              /* lz_match_len should be divisible by L in -m1 and -m2 modes */   \
  unsigned lit_len         = *stat++;                                             /* length of literal (copied from in[]) */                         \
  Offset   lz_match_offset = *stat++;                                             /* LZ.dest-LZ.src (divided by L when ROUND_MATCHES==TRUE) */       \
  if (!ROUND_MATCHES)         lz_match_offset += Offset(*stat++) << STAT_BITS;    /* High word of lz_match_offset */                                 \
                              lz_match_offset *= L1;                                                                                                 \
  LZ_MATCH_TYPE lz_match;                                                                                                                            \
                lz_match.len = (*stat++)*L1 + L;                                                                                                     \
  if (!REVERSED_LZ) {                                                                                                                                \
           lz_match.dest   = (basic_pos) + lit_len;                                                                                                  \
           lz_match.src    = lz_match.dest/L1*L1 - lz_match_offset;                                                                                  \
  } else {                                                                                                                                           \
           lz_match.src    = (basic_pos) + lit_len;                                                                                                  \
           lz_match.dest   = lz_match.src + lz_match_offset;                                                                                         \
  }


// Копирует данные из буфера в буфер, идя в порядке возрастания адресов
// (это важно, поскольку буфера могут пересекаться и в этом случае нужно
// размножить существующие данные)
void memcpy_lz_match (void* _dest, void* _src, unsigned len)
{
  if (len) {
    char *dest = (char*)_dest,  *src = (char*)_src;
    do { *dest++ = *src++;
    } while (--len);
  }
}



// //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Single block compressor and decompressor *********************************************************************************************************
// //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

// Возведение в степень
template <class T>
T power (T base, unsigned n)
{
  T result = 1;
  while (n) {
    if (n % 2)  result*=base, n--;
    n /= 2;  base*=base;
  }
  return result;
}

// Для нахождения выравненных совпадений длины кратной L нужно заносить в хеш значения контрольной функции
//   от блоков длиной L в позициях, кратных L, и искать в этой хеш-таблице совпадения для всех блоков длиной L байт.
// hash содержит значение хеш-функции от последних L обработанных байт, для удобства обновления используется скользящая хеш-функция.
// update_hash(sub,add) выносит из хеша байт sub и добавляет байт add.

const HashValue PRIME  =  153191;       // or any other large prime number
const HashValue PRIME2 = 3141601;       // or any other large prime number

#define update_hash(sub,add)                                                             \
{                                                                                        \
            hash  = hash *PRIME  + BYTE(add) -  PRIME_power_L*BYTE(sub);                 \
  _32_only (hash2 = hash2*PRIME2 + BYTE(add) - PRIME2_power_L*BYTE(sub));                \
}


unsigned record_match (bool ROUND_MATCHES, unsigned L, unsigned MIN_MATCH, Offset block_start, HashTable &h, char *buf, int block_size, char *&out, STAT *&stat, unsigned last_match_end, unsigned i, Chunk k)
{
  unsigned add_len, match_len = h.match_len (k, &buf[last_match_end], &buf[i], buf+block_size, block_start, buf, &add_len);

  if (match_len >= MIN_MATCH)                                        // ... it's large enough, then ...
  {
    unsigned match_start = i-add_len;
    if (ROUND_MATCHES)
      match_len = match_len/L*L;

    memcpy(out, &buf[last_match_end], match_start-last_match_end);   // ... copy literal bytes after the previous match and ...
    out += match_start-last_match_end;

    Offset match_offset = block_start+i-Offset(k)*L;                 // ... save triple (literal_len, match_offset, match_len)
    if (match_offset < pc.max_offset)  pc.record_match++, pc.total_match_len += match_len;
    ENCODE_LZ_MATCH(stat, ROUND_MATCHES, L,  match_start-last_match_end, match_offset, match_len);
    return match_start+match_len;
  }
  return last_match_end;
}

#define check_match(i,hash,hashx)                                                                                                                     \
{                                                                                                                                                     \
  if (i >= last_match_end) {                                                                                                                          \
    Chunk k = h.find_match (&buf[i], hash, hashx, block_start+i);        /* Number of previous chunk with the same contents as current one  */        \
    if (k != NOT_FOUND)                                                  /* If match was found, and ...                                     */        \
      last_match_end = record_match(ROUND_MATCHES, L, MIN_MATCH, block_start, h, buf, block_size, out, stat, last_match_end, i, k);                   \
  }                                                                                                                                                   \
}

// Compress buf[] and return compressed data in outbuf[] and statbuf[]
template <unsigned ACCELERATOR>
void compress (bool ROUND_MATCHES, unsigned L, unsigned MIN_MATCH, Offset block_start, HashTable &h, char *buf, int block_size, char *outbuf, STAT *statbuf, char *&out, STAT *&stat)
{
  out  = outbuf;
  stat = statbuf;
  NUMBER last_match_end = 0;
  const NUMBER CYCLES = (ACCELERATOR? ACCELERATOR:1);
  const HashValue PRIME_power_L = power(PRIME,L),  PRIME2_power_L = power(PRIME2,L);

  if (2*L <= block_size)
  {
    HashValue hash=0, hash2=0;  for (NUMBER i=0; i<L; i++)  update_hash (0, buf[i])

    for (NUMBER i=0; i<1; i++) {
      check_match (i, hash, hashx);
      h.mark_match_possibility<ACCELERATOR> (hash);
      h.add_hash (&buf[i], block_start+i, hash, hashx);
      update_hash (buf[i], buf[i+L]);
    }

    for (NUMBER i=1; i+2*L-1<=block_size; )
    {
      for (NUMBER last_i=i+L-CYCLES; likely(i<last_i); )            // fixed L: for (NUMBER k=0; k<L/CYCLES-1; k++)
      {
        if (unlikely (i+CYCLES-1>=last_match_end  &&  h.check_match_possibility<ACCELERATOR> (hash) ))    // Let's check for match if previous match is over
        {
          for (NUMBER j=0; j<CYCLES; i++, j++) {
            check_match (i, hash, hashx);
            update_hash (buf[i], buf[i+L]);
          }
        } else {
          for (NUMBER j=0; j<CYCLES; i++, j++) {
            update_hash (buf[i], buf[i+L]);
          }
        }
      }

      bool match_possible  =  i+CYCLES-1>=last_match_end  &&  h.check_match_possibility<ACCELERATOR> (hash);
      for (NUMBER j=0; j<CYCLES; i++, j++) {
        if (match_possible)
          check_match (i, hash, hashx);
        h.mark_match_possibility<ACCELERATOR> (hash);
        if (j == CYCLES-1)
          h.add_hash (&buf[i], block_start+i, hash, hashx);
        if (i+L < block_size)
          update_hash (buf[i], buf[i+L]);
      }
    }
  }

  memcpy(out, &buf[last_match_end], block_size-last_match_end);            // Copy literal bytes after the last match
  out += block_size-last_match_end;
}


// Decompress data using stat[] and in[] and return original data in outbuf[]. Returns TRUE on successful decompression
bool decompress (bool ROUND_MATCHES, unsigned L, FILE *fout, Offset block_start, STAT *stat, char *in, char *inend, char *outbuf, char *outend)
{
  STAT *statend = (STAT*)in;
  char *out = outbuf;

  while (statend-stat >= STATS_PER_MATCH(ROUND_MATCHES))
  {
    // Like in original LZ77, LZ matches and literals are strictly interleaved
    DECODE_LZ_MATCH(stat, false, ROUND_MATCHES, L, block_start+(out-outbuf),  lit_len, LZ_MATCH, lz_match);
    if (lit_len>inend-in || lit_len+lz_match.len>outend-out || lz_match.src>=lz_match.dest)  return false;   // Bad compressed data: in/out buffer overflow or src>=dest

    // First, copy literal data
    memcpy (out, in, lit_len);
    in  += lit_len;
    out += lit_len;

    // Second, copy LZ match data from previous blocks
    if (lz_match.src < block_start)
    {
      unsigned bytes = mymin (lz_match.len, block_start-lz_match.src);
      file_seek(fout, lz_match.src);
      file_read(fout, out, bytes);
      out          += bytes;
      lz_match.src += bytes;
      lz_match.len -= bytes;
    }

    // Third, copy LZ match data from the current block
    memcpy_lz_match (out, outbuf + (lz_match.src-block_start), lz_match.len);
    out += lz_match.len;
  }

  // Copy literal data up to the block end
  if (inend-in != outend-out)  return false;    // Bad compressed data
  memcpy(out, in, inend-in);
  return true;
}



// //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Memory manager ***********************************************************************************************************************************
// //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

// Manages memory in fixed-size chunks in order to prevent uncontrolled memory fragmentation provided by malloc()
class MEMORY_MANAGER
{
public:  // ******************************************************* HIGH-LEVEL API: OPERATIONS ON VARIABLE-SIZED MEMORY AREAS *************
  typedef uint32 INDEX;                                          // Index of chunk

  INDEX save (char *ptr, int len) {                              // Save contents of memory area
    INDEX index=INVALID_INDEX, first_index=INVALID_INDEX, prev_index=INVALID_INDEX;
    while (len>0) {
      index = allocate();
      if (prev_index != INVALID_INDEX)  set_next_index(prev_index, index);  else first_index = index;
      prev_index = index;
      int bytes = mymin(len, USEFUL_CHUNK_SPACE);
      memcpy (data_ptr(index), ptr, bytes);
      ptr += bytes;
      len -= bytes;
    }
    set_next_index(index, INVALID_INDEX);
    return first_index;
  }
  void restore (INDEX index, char *ptr, int len) {               // Restore saved contents
    while (len>0) {
      int bytes = mymin(len, USEFUL_CHUNK_SPACE);
      memcpy (ptr, data_ptr(index), bytes);
      ptr += bytes;
      len -= bytes;
      index = next_index(index);
    }
  }
  void free (INDEX index) {                                      // Free saved contents
    while (index != INVALID_INDEX) {
      INDEX next = next_index(index);
      mark_as_free(index);
      index = next;
    }
  }

private: // ******************************************************* MID-LEVEL API: OPERATIONS ON CHUNKS ***********************************
  INDEX allocate() {                                             // Allocate one chunk and return its index
    if (first_free == INVALID_INDEX)  allocate_block();
    INDEX free_chunk = first_free;
    first_free = next_index(first_free);
    used_chunks++;
    return free_chunk;
  }
  void mark_as_free (INDEX index) {                              // Mark chunk as free
    set_next_index(index, first_free);
    first_free = index;
    used_chunks--;
  }
  INDEX next_index (INDEX index) {                               // Returns contents of "next chunk" field for given chunk
    return *(INDEX*)chunk_ptr(index);
  }
  void set_next_index (INDEX index, INDEX next_index) {          // Sets "next chunk" field of given chunk to the value of next_index
    *(INDEX*)chunk_ptr(index) = next_index;
  }
  char *data_ptr (INDEX index) {                                 // Data part of given chunk
    return chunk_ptr(index) + sizeof(INDEX);
  }

private: // ******************************************************* LOW-LEVEL API: OPERATIONS ON BLOCKS ***********************************
  char *chunk_ptr (INDEX index) {                                // Address of chunk with given index
    return block_addr[index>>lbK] + (index&K1)*CHUNK_SIZE;
  }
  void allocate_block() {                                        // Allocate one more block of memory and add its chunks to the chain of free chunks
    char *p = new char[aBLOCK_SIZE];
    block_addr.push_back(p);
    int block = block_addr.size()-1;
    for(INDEX i=block*K; i<(block+1)*K-1; i++)
      set_next_index(i,i+1);
    set_next_index ((block+1)*K-1, first_free);
    first_free = block*K;
    if (first_free == INVALID_INDEX)  first_free++;
  }

private: // ******************************************************* VARIABLES AND CONSTANTS ***********************************************
  std::vector<char*> block_addr;
  INDEX first_free;
  size_t used_chunks, useful_memory;

  static const size_t CHUNK_SIZE=64, USEFUL_CHUNK_SPACE = CHUNK_SIZE-sizeof(INDEX);
  static const size_t aBLOCK_SIZE=1*mb, K=aBLOCK_SIZE/CHUNK_SIZE, K1=K-1, lbK=14;

public:
  static const INDEX INVALID_INDEX=0;
  MEMORY_MANAGER (size_t memlimit)   {first_free=INVALID_INDEX; used_chunks=0; useful_memory=(memlimit/aBLOCK_SIZE*aBLOCK_SIZE/CHUNK_SIZE-1)*USEFUL_CHUNK_SPACE; CHECK(FREEARC_ERRCODE_INTERNAL,  K==(1<<lbK),  (s,"INTERNAL ERROR: K!=(1<<lbK)"));}
  Offset current_mem()               {return used_chunks*CHUNK_SIZE;}
  Offset max_mem()                   {return block_addr.size()*aBLOCK_SIZE;}
  Offset available_space()           {return useful_memory > used_chunks*USEFUL_CHUNK_SPACE? useful_memory-used_chunks*USEFUL_CHUNK_SPACE : 0;}
};



// //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Future-LZ match handling *************************************************************************************************************************
// //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

// Statistics! Statistics! Statistics!
Offset total_matches=0, cur_matches=0, max_matches=0, total_bytes=0, cur_bytes=0, max_bytes=0, total_reads=0;
void PLUS_MATCH(unsigned bytes)  {if (bytes>0)  bytes+=16;
                                  total_matches++;    cur_matches++;    max_matches=mymax(cur_matches, max_matches);
                                  total_bytes+=bytes; cur_bytes+=bytes; max_bytes  =mymax(cur_bytes,   max_bytes);}
void MINUS_MATCH(unsigned bytes) {if (bytes>0)  bytes+=16;
                                  cur_matches--;      cur_bytes-=bytes;}
void PLUS_READ()                 {total_reads++;}


// Structure storing Future-LZ match info
struct FUTURE_LZ_MATCH : LZ_MATCH
{
  MEMORY_MANAGER::INDEX  index;      // Index of data from the match saved by MEMORY_MANAGER
  FUTURE_LZ_MATCH() : index(MEMORY_MANAGER::INVALID_INDEX) {}

  // Save match data to buffers provided by MEMORY_MANAGER
  void save_match_data (MEMORY_MANAGER &mm, char *ptr)
  {
    index = mm.save (ptr, len);
    PLUS_MATCH(len);
  }

  // Copy match data to ptr
  void restore_match_data (MEMORY_MANAGER &mm, char *ptr) const
  {
    mm.restore (index, ptr, len);
  }

  // Copy match data to ptr
  void restore_match_data (MEMORY_MANAGER &mm, char *ptr, char *buf, Offset buf_start) const
  {
    if (index != MEMORY_MANAGER::INVALID_INDEX)
      mm.restore (index, ptr, len);
    else
      memcpy_lz_match (ptr, buf+(src-buf_start), len);
  }

  // Free memory allocated by match data
  void free(MEMORY_MANAGER &mm) const
  {
    mm.free(index);
    MINUS_MATCH (index!=MEMORY_MANAGER::INVALID_INDEX? len : 0);
  }

  // Pseudo-match used to mark positions where restore_from_disk() should be called
  void set_marking_point()       {len=0;}
  bool is_marking_point() const  {return len==0;}
};

typedef std::multiset<FUTURE_LZ_MATCH>  LZ_MATCH_HEAP;                            // Used to store matches ordered by LZ destination
typedef LZ_MATCH_HEAP::iterator         LZ_MATCH_ITERATOR;
typedef LZ_MATCH_HEAP::reverse_iterator LZ_MATCH_REVERSE_ITERATOR;

// Compare LZ matches by destination position (for LZ_MATCH_HEAP)
bool operator < (const FUTURE_LZ_MATCH &left, const FUTURE_LZ_MATCH &right)
{
  return (left.dest < right.dest);
}



// //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Virtual memory manager ***************************************************************************************************************************
// //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

struct VIRTUAL_MEMORY_MANAGER
{
  char *vmfile_name;                        // File used as virtual memory
  FILE *vmfile;                             // -.-
  Offset VMBLOCK_SIZE;                      // VM block size
  char *vmbuf;                              // Buffer temporarily storing one VM block contents
  std::stack<unsigned> free_blocks;         // List of free blocks (that were allocated previosly)
  unsigned new_block;                       // Next block to alloc if free_blocks list is empty
  Offset total_read, total_write;           // Bytes read/written to disk by VMM

  VIRTUAL_MEMORY_MANAGER (char *_vmfile_name, Offset _VMBLOCK_SIZE)  :  vmfile_name(_vmfile_name), vmfile(NULL), vmbuf(NULL), VMBLOCK_SIZE(_VMBLOCK_SIZE), new_block(0), total_read(0), total_write(0) {}
  ~VIRTUAL_MEMORY_MANAGER() {delete vmbuf;  if(vmfile) {fclose(vmfile); remove(vmfile_name);}}
  Offset current_mem()      {return max_mem() - free_blocks.size()*VMBLOCK_SIZE;}
  Offset max_mem()          {return new_block*VMBLOCK_SIZE;}

  // Save matches with largest LZ.dest to disk
  void save_to_disk (MEMORY_MANAGER &mm, LZ_MATCH_HEAP &lz_matches)
  {
    if (!vmbuf)    vmbuf  = new char[VMBLOCK_SIZE];
    if (!vmfile)   vmfile = fopen(vmfile_name, "w+b");

    // Encode matches to the block, while it has enough space
    Offset min_dest = Offset(-1);
    LZ_MATCH_REVERSE_ITERATOR lz = lz_matches.rbegin();
    char *p = vmbuf;
    for (;;)
    {
      lz++;
      if (lz == lz_matches.rend())                        break;      // There are no more matches in the heap :D
      if (lz->index == MEMORY_MANAGER::INVALID_INDEX)     continue;   // Match doesn't contain match data - skip it
      if (vmbuf+VMBLOCK_SIZE-p  <  24+lz->len)            break;      // Not enough space in the block to save this match - go writing block to the disk

      *(STAT*)p = lz->len;   *(Offset*)(p+4) = lz->src;   *(Offset*)(p+12) = min_dest = lz->dest;
      lz->restore_match_data(mm,p+20);
      p += 20 + lz->len;

      lz->free(mm);
      lz_matches.erase(*lz);
    }
    *(STAT*)p = 0;       // End-of-block mark

    // Save block to disk, and add to the heap pseudo-match marking the restore point
    unsigned block;  if(free_blocks.empty())  block=new_block++;  else block=free_blocks.top(), free_blocks.pop();     // First free block in the file
    file_seek (vmfile, block*VMBLOCK_SIZE);
    file_write(vmfile, vmbuf,VMBLOCK_SIZE);
    total_write += VMBLOCK_SIZE;
    FUTURE_LZ_MATCH mark;  mark.src=block;  mark.dest=min_dest;  mark.set_marking_point();
    lz_matches.insert(mark);
  }


  // Restore matches, pointed by mark, from disk
  void restore_from_disk (MEMORY_MANAGER &mm, LZ_MATCH_HEAP &lz_matches, LZ_MATCH_ITERATOR &mark)
  {
    // Free up enough memory to ensure that there are space to restore the block
    while (mm.available_space() < VMBLOCK_SIZE)   save_to_disk (mm, lz_matches);

    // Read block from disk
    unsigned block = mark->src;
    file_seek (vmfile, block*VMBLOCK_SIZE);
    file_read (vmfile, vmbuf,VMBLOCK_SIZE);
    total_read += VMBLOCK_SIZE;
    free_blocks.push(block);

    // Restore matches encoded in the block
    for (char *p=vmbuf;  *(STAT*)p != 0;)     // Until end-of-block mark
    {
      FUTURE_LZ_MATCH lz;   lz.len = *(STAT*)p;   lz.src = *(Offset*)(p+4);   lz.dest = *(Offset*)(p+12);
      lz.save_match_data(mm,p+20);
      lz_matches.insert(lz);
      p += 20 + lz.len;
    }
  }
};



// //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Single block Future-LZ decompressor **************************************************************************************************************
// //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

// Decompress data using stat[] and in[] and return original data in outbuf[]. Returns TRUE on successful decompression
bool decompress_reversed_LZ (bool ROUND_MATCHES, unsigned L, FILE *fout, Offset block_start, STAT *statbuf, char *in, char *inend, char *outbuf, char *outend,
                             MEMORY_MANAGER &mm, VIRTUAL_MEMORY_MANAGER &vm, LZ_MATCH_HEAP &lz_matches, unsigned maximum_save)
{
  Offset block_end = block_start + (outend-outbuf);   // Absolute file position corresponding to end of the current block
  STAT *statend = (STAT*)in;
  char *out = outbuf;

  // 1. Insert into lz_matches matches with LZ.dest in the current block
  Offset block_pos = block_start;
  for (STAT *stat = statbuf;  statend-stat >= STATS_PER_MATCH(ROUND_MATCHES);  )
  {
    DECODE_LZ_MATCH(stat, true, ROUND_MATCHES, L, block_pos,  lit_len, FUTURE_LZ_MATCH, lz_match);
    if (lz_match.src<block_pos || lz_match.src>=block_end || lz_match.len>block_end-lz_match.src || lz_match.dest<=lz_match.src)  return false;    // Bad compressed data
    if (lz_match.dest < block_end)
      lz_matches.insert(lz_match), PLUS_MATCH(0);
    block_pos = lz_match.src;
  }

  // 2. LZ decompression loop, processing all LZ matches with LZ.dest in the current block
  for (LZ_MATCH_ITERATOR lz_match = lz_matches.begin();  lz_match->dest < block_end;  lz_match = lz_matches.begin())
  {
    if (lz_match->is_marking_point()) {
      vm.restore_from_disk (mm, lz_matches, lz_match);
    } else {
      // Copy literal data up to match start
      int lit_len = (lz_match->dest - block_start) - (out-outbuf);
      if ((lz_match->dest < block_start+(out-outbuf))  ||  (in+lit_len > inend)  ||  (out+lit_len+lz_match->len > outend))  return false;    // Bad compressed data
      memcpy (out, in, lit_len);
      in  += lit_len;
      out += lit_len;

      // Copy match data
      if (lz_match->len >= maximum_save  &&  lz_match->src < block_start) {
        file_seek(fout, lz_match->src);
        file_read(fout, out, lz_match->len);   PLUS_READ();
      } else {
        lz_match->restore_match_data (mm, out, outbuf, block_start);
      }
      out += lz_match->len;
      lz_match->free(mm);
    }
    lz_matches.erase(lz_match);
  }
  // Copy literal data up to the block end
  if (inend-in != outend-out)  return false;    // Bad compressed data
  memcpy (out, in, inend-in);

  // 3. Insert into lz_matches matches with LZ.dest in future blocks
  block_pos = block_start;
  for (STAT *stat = statbuf;  statend-stat >= STATS_PER_MATCH(ROUND_MATCHES);  )
  {
    DECODE_LZ_MATCH(stat, true, ROUND_MATCHES, L, block_pos,  lit_len, FUTURE_LZ_MATCH, lz_match);
    if (lz_match.dest >= block_end)
    {
      if (lz_match.len >= maximum_save)  PLUS_MATCH(0);
      else {
        while (lz_match.len > mm.available_space())   vm.save_to_disk (mm, lz_matches);
        lz_match.save_match_data (mm, outbuf + (lz_match.src-block_start));      // copy match data into dynamically-allocated buffer
      }
      lz_matches.insert(lz_match);
    }
    block_pos = lz_match.src;
  }

  return true;
}



// //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Error handling ***********************************************************************************************************************************
// //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

// Exit on error
void error (int ExitCode, char *ErrmsgFormat...)
{
  va_list argp;
  va_start(argp, ErrmsgFormat);
  fprintf  (stderr, "\n  ERROR! ");
  vfprintf (stderr, ErrmsgFormat, argp);
  fprintf  (stderr, "\n");
  va_end(argp);

  exit(ExitCode);
}

#define checked_file_read(f, buf, size)                                           \
{                                                                                 \
  if (file_read(f, (buf), (size)) != (size))                                      \
  {                                                                               \
    fprintf (stderr, "\n  ERROR! Can't read from input file");                    \
    errcode = ERROR_IO;                                                           \
    goto cleanup;                                                                 \
  }                                                                               \
}                                                                                 \

#define checked_file_write(f, buf, size)                                          \
{                                                                                 \
  if (file_write(f, (buf), (size)) != (size))                                     \
  {                                                                               \
    fprintf (stderr, "\n  ERROR! Can't write to output file (disk full?)");       \
    errcode = ERROR_IO;                                                           \
    goto cleanup;                                                                 \
  }                                                                               \
}                                                                                 \



// //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Background thread ***********************************************************************************************************************************
// //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

#include "../MultiThreading.h"
#include "../MultiThreading.cpp"

struct BG_COMPRESSION_THREAD : BackgroundThread
{
  static const int BUFFERS = 2;
  unsigned k;
  char *bufptr[BUFFERS];
  char *buf[BUFFERS];
  char *outbuf[BUFFERS];
  STAT *statbuf[BUFFERS];
  STAT *header[BUFFERS];
  unsigned len[BUFFERS];
  unsigned stat_size[BUFFERS];
  unsigned outsize[BUFFERS];

  volatile int errcode;
  bool COMPARE_DIGESTS, no_writes, md5;
  unsigned L, bufsize, header_size;
  Offset filesize;
  HashTable& h;
  MMAP_FILE& infile;
  FILE *fin, *fout, *fstat;
  Event ReadDone, WriteReady, BgThreadFinished;


  BG_COMPRESSION_THREAD (bool _COMPARE_DIGESTS, unsigned _L, bool _no_writes, bool _md5, Offset _filesize, unsigned _bufsize, unsigned _header_size, HashTable& _h, MMAP_FILE& _infile, FILE* _fin, FILE* _fout, FILE* _fstat)
    : errcode(NO_ERRORS), k(0), COMPARE_DIGESTS(_COMPARE_DIGESTS), L(_L), no_writes(_no_writes), md5(_md5), filesize(_filesize), bufsize(_bufsize), header_size(_header_size), h (_h), infile(_infile), fin(_fin), fout(_fout), fstat(_fstat)
  {
    for (int i=0; i<BUFFERS; i++)
    {
      buf[i]     = new char[bufsize+10];
      outbuf[i]  = new char[bufsize+10];
      statbuf[i] = new STAT[MAX_STATS_PER_BLOCK(bufsize,L)+10];
      header[i]  = new STAT[header_size/sizeof(STAT)];
      if (!buf[i] || !outbuf[i] || !statbuf[i] || !header[i])
        {errcode=ERROR_MEMORY; return;}
      memset(header[i], 0, header_size);
    }
    start();
  }

  Offset memreq()  {return BUFFERS * (Offset(bufsize)*2 + sizeof(STAT)*MAX_STATS_PER_BLOCK(bufsize,L) + header_size);}

  void wait()
  {
    BgThreadFinished.Wait();
    for (int i=0; i<BUFFERS; i++)
    {
      delete buf[i];
      delete outbuf[i];
      delete statbuf[i];
      delete header[i];
    }
  }

  int read (char **_buf, char **_outbuf, STAT **_statbuf, STAT **_header)
  {
    if (no_writes)
      WriteReady.Signal();

    ReadDone.Wait();
    k = (k+1)%BUFFERS;
    *_buf     = bufptr[k];
    *_outbuf  = outbuf[k];
    *_statbuf = statbuf[k];
    *_header  = header[k];
    return len[k];
  }

  void write (unsigned _stat_size, unsigned _outsize)
  {
    stat_size[k] = _stat_size;
    outsize[k]   = _outsize;
    WriteReady.Signal();
  }

  // Background thread code
  void run()
  {
    Offset pos = 0;   unsigned curchunk = 0;
    for(int i=1, first_block=1;  ;  i=(i+1)%BUFFERS, first_block=0)    // i = 1 0 1 0 1...  first_block = 1 0 0 0...
    {
      // 1. Read input data
      len[i] = file_read (fin, buf[i], bufsize);  bufptr[i] = buf[i];     // file_read
      if (filesize-pos < len[i])  {fprintf (stderr, "\n  ERROR! Input file is larger that filesize specified"); errcode=ERROR_IO; ReadDone.Signal(); break;}  // Ensure that we don't read more than `filesize` bytes
      if (!COMPARE_DIGESTS  &&  infile.mmapped()) {
        len[i] = infile.read (&bufptr[i], buf[i], pos, bufsize, fin);     // mmap
      }


      // 2. Perform b/g processing of input data
      if (md5)                                                      // Save MD5 checksum of every input block for decompression error-checking
        compute_checksum (bufptr[i],len[i], header[i]+3);
      h.prepare_buffer (pos, bufptr[i], len[i]);


      // 3. Wait for output data from prev. block and write them
      if (!first_block || no_writes)
        WriteReady.Wait();                          // Wait for output data from prev. block
      ReadDone.Signal();                            // Allow to use input data
      if (!first_block && !no_writes) {
        int k = (i-1+BUFFERS)%BUFFERS;
        checked_file_write (fout,  header [k], header_size);
        checked_file_write (fstat, statbuf[k], stat_size[k]);
        checked_file_write (fout,  outbuf [k], outsize[k]);
      }

      // 4. Stop thread on EOF
      if (len[i]==0) break;
      pos += len[i];
    }
cleanup:
    BgThreadFinished.Signal();
  }
};



// //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Main *********************************************************************************************************************************************
// //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

// Structure describing one compressed block
struct COMPRESSED_BLOCK
{
  COMPRESSED_BLOCK *next;  // Next block in chain
  Offset start, end;       // First and next-after-last byte of the block
  unsigned size;           // Bytes in uncompressed block
  STAT *header;            // Block header data
  STAT *statbuf, *statend; // LZ matches in the block
};


// Parse -mem option, examples are: -mem100mb, -mem75%, -mem75p, -mem75%-600mb
int64 parse_mem_option (char *option, int &errcode)
{
  if (errcode)  return 0;

  // Parse -mem100mb variant
  int64 mem = parseMem (option, &errcode, 'm');
  if (errcode==0)  return mem;
  errcode=0;

  // Parse XX% part
  int percent = 0;
  while (*option >='0'  &&  *option <='9')
    percent = percent*10 + (*option++ - '0');
  if (*option!='%' && *option!='p')  {errcode=1; return 0;}
  option++;

  // Parse XXmb part
  if      (*option == '\0')   {mem = 0;}                                       // -mem75% variant
  else if (*option++ != '-')  {errcode=1; return 0;}                           // illegal option
  else                        {mem = parseMem (option, &errcode, 'm');}        // -mem75%-600mb variant
  return percent*(GetPhysicalMemory()/100) - mem;
}


int main (int argc, char **argv)
{
  SREP_METHOD method = SREP_METHOD1;
  Offset filesize = Offset(25)*gb;
  double GlobalTime0 = GetGlobalTime();
  const int bufsize = 8*mb,  header_size = sizeof(STAT)*3 + sizeof(Checksum),  ADDITIONAL_8MB = bufsize, DEFAULT_ACCEL = 4;
  unsigned L=0, min_match=0, maximum_save=unsigned(-1), accel=9000, vm_block=8*mb;
  bool compression=true, REVERSED_LZ=true, md5=true, use_mmap=false, delete_input_files=false, print_pc=false;
  char *index_file="",  *tempfile=NULL,  *DEFAULT_TEMPFILE="srep-data.tmp",  *vmfile_name="srep-virtual-memory.tmp";
  char *newline = "    \b\b\b\b";   // required to overwrite previous, longer stats line
  int errcode=0, warnings=0, verbosity=2;               ForceMode LargePageMode=TRY;
  int64 vm_mem = parse_mem_option ("75%", errcode);     if (vm_mem > 1536*mb)    _32_only(vm_mem = 1536*mb);
  setbuf(stderr,NULL);    // Disable buffering even if stderr is redirected to file/pipe

  //*********************************************************************************************************
  /// PARSE CMDLINE
  //*********************************************************************************************************

  while(argv[1])
  {
    if (strequ(argv[1],"-d")) {
      compression = false;
    } else if (strequ(argv[1],"-delete")) {
      delete_input_files = true;
    } else if (strequ(argv[1],"-nomd5")) {
      md5 = false;
    } else if (strequ(argv[1],"-mmap")) {
      use_mmap = true;
    } else if (strequ(argv[1],"-nommap")) {
      use_mmap = false;
    } else if (strequ(argv[1],"-s")) {
      newline = "\n";
    } else if (strequ(argv[1],"-m1")) {
      method = SREP_METHOD1;  REVERSED_LZ = false;
    } else if (strequ(argv[1],"-m2")) {
      method = SREP_METHOD2;  REVERSED_LZ = false;
    } else if (strequ(argv[1],"-m3")) {
      method = SREP_METHOD3;  REVERSED_LZ = false;
    } else if (strequ(argv[1],"-f")) {
      REVERSED_LZ = TRUE;
    } else if (strequ(argv[1],"-m1f")) {
      method = SREP_METHOD1;  REVERSED_LZ = true;
    } else if (strequ(argv[1],"-m2f")) {
      method = SREP_METHOD2;  REVERSED_LZ = true;
    } else if (strequ(argv[1],"-m3f")) {
      method = SREP_METHOD3;  REVERSED_LZ = true;
    } else if ((strequ(argv[1],"-a0") || strequ(argv[1],"-a1") || strequ(argv[1],"-a2") || strequ(argv[1],"-a4") || strequ(argv[1],"-a8") || strequ(argv[1],"-a16") || strequ(argv[1],"-a32") || strequ(argv[1],"-a64"))) {
      accel = parseInt (argv[1]+2, &errcode);
    } else if (strequ(argv[1],"-slp")) {
        LargePageMode = TRY;
    } else if (strequ(argv[1],"-slp-")) {
        LargePageMode = DISABLE;
    } else if (strequ(argv[1],"-slp+")) {
        LargePageMode = FORCE;
    } else if (strequ(argv[1],"-v")) {
      verbosity = 1;
    } else if (start_with(argv[1],"-v")) {
      verbosity = parseInt (argv[1]+2, &errcode);
    } else if (start_with(argv[1],"-pc")) {
      print_pc = true;
      pc.max_offset  =  argv[1][3]? parseMem64 (argv[1]+3, &errcode, 'm') : Offset(-1);
    } else if (start_with(argv[1],"-index=")) {
      index_file = argv[1]+7;
    } else if (start_with(argv[1],"-temp=")) {
      tempfile = argv[1]+6;
    } else if (start_with(argv[1],"-vmfile=")) {
      vmfile_name = argv[1]+8;
    } else if (start_with(argv[1],"-vmblock=")) {
      vm_block = parseMem (argv[1]+9, &errcode, 'm');
    } else if (start_with(argv[1],"-mem")) {
      vm_mem = parse_mem_option (argv[1]+4, errcode);
    } else if (start_with(argv[1],"-c")) {
      L = parseMem (argv[1]+2, &errcode, 'b');
    } else if (start_with(argv[1],"-l")) {
      min_match = parseMem (argv[1]+2, &errcode, 'b');
    } else if (start_with(argv[1],"-s")) {
      filesize = parseMem64 (argv[1]+2, &errcode, 'b');
    } else if (start_with(argv[1],"-m")) {
      maximum_save = parseMem (argv[1]+2, &errcode, 'b');
      if (maximum_save < 10)  errcode=1;
    } else if (start_with(argv[1],"-rem")) {
      // Command-line remark
    } else break;
    if (errcode)
      error (ERROR_CMDLINE, "Invalid option: %s", argv[1]);
    argv++, argc--;
  }

  // (De)compress from stdin to stdout if no filenames are given, but both stdin and stdout are redirected
  if (argc==1  &&  !isatty(fileno(stdin))  &&  !isatty(fileno(stdout)))
  {
    argc = 3;
    char *_argv[] = {"","-","-",NULL};
    argv = _argv;
  }

  bool ROUND_MATCHES    =  (method == SREP_METHOD1);   // Match lengths are multiplies of L, otherwise - arbitrary match lengths >= min_match
  bool COMPARE_DIGESTS  =  (method == SREP_METHOD1);   // Check matches by comparison of SHA-1 digests, otherwise - check matches by rereading old data
  if (!L && !min_match)  min_match = 512;
  if (!L)                L  =  (method<=SREP_METHOD2?  min_match  :  rounddown_to_power_of(min_match+1,2)/2);   // only -m3 performs exhasustive search for ALL matches of min_match bytes or longer
  if (!min_match)        min_match = L;
  if (L != roundup_to_power_of(L,2)) {
    fprintf (stderr, "Warning: -l parameter should be power of 2, otherwise compressed file may be corrupt\n");
    warnings++;
  }
  if (vm_mem > size_t(-1))    vm_mem = size_t(-1);     // For 32-bit systems (75% of 8gb RAM is a bit too much). Or use GetTotalMemoryToAlloc()

  if (argc!=2 && argc!=3) {
    fprintf (stderr, "%s: %s\n"
                     "%s    homepage: %s\n"
                     "\n"
                     "Usage: SREP [options] infile [outfile]\n"
                     "   infile/outfile may be specified as \"-\" that means stdin/stdout\n"
                     "   \"SREP [options] infile\" compress data to infile.srep\n"
                     "   \"SREP [options] infile.srep\" decompress data to infile\n"
                     "   \"SREP [options]\" compress or decompress data from stdin to stdout\n"
                     "\n"
                     "Options are:\n"
                     "   -m1: check matches by SHA1 digest (compression memory = 7-10%% of filesize)\n"
                     "   -m2: check matches by rereading old data (compression memory = 3-6%% of filesize)\n"
                     "   -m3: byte-accurate matches and rereading (compression memory = 7-12%% of filesize)\n"
                     "   -l: minimum LZ match length, default %d\n"
                     "   -c: size of hash chunk, by default as small as required to find all these LZ matches\n"
                     "   -a: compression accelerator (0/1/2/4/8/16/32/64). -a0 is slowest but requires least memory\n"
                     "\n"
                     "   -m1f..-m3f: future-LZ - decompression dictionary will hold only future matches\n"
                     "   -memBYTES: amount of RAM used by future-LZ decompression (extra goes into VM file)\n"
                     "      -mem75%% AKA -mem75p means \"use no more than 75%% of RAM\" - that's by default\n"
                     "      -mem600mb means itself\n"
                     "      -mem75%%-600mb means \"use no more than 75%% of RAM minus 600 mb\"\n"
                     "   -mBYTES: don't store matches larger than BYTES on future-LZ decompression\n"
                     "\n"
                     "   -d: decompression (for -m1..m3 requires only 24 mb of memory besides of OS I/O buffers)\n"
                     "   -delete: delete source file after successful (de)compression\n"
                     "   -sBYTES: explicitly specify filesize (for compression from stdin), default %dgb\n"
                     "   -index=FILENAME: read/write index of compressed data into separate file\n"
                     "   -temp=[FILENAME]: keep uncompressed data in the file in stdin-to-stdout mode, default %s\n"
                     "   -vmfile=FILENAME: temporary file used by Virtual Memory manager, default %s\n"
                     "   -vmblock=BYTES: size of one block in VM temporary file, default %dmb\n"
                     "\n"
                     "   -nomd5: don't store/check MD5 checksum of every block\n"
                     "   -mmap: use memory-mapped files for match checking\n"
                     "   -slp[+/-/]: force/disable/try(default) large pages support\n"
                     "   -pc[max_offset]: display performance counters [for matches closer than max_offset]\n"
                     "   -s: save printed stats from overwriting\n"
                     "   -v[0..2]: verbosity level\n"
                     "   -rem...: command-line remark\n",
                     program_version, program_description, program_date, program_homepage,
                     min_match, int(filesize/gb), DEFAULT_TEMPFILE,  vmfile_name, int(vm_block/mb));
    exit (ERROR_CMDLINE);
  }


  //*********************************************************************************************************
  /// OPEN INPUT/OUTPUT/TEMPORARY FILES
  //*********************************************************************************************************

  char *finame = argv[1];
  char *foutname = argv[2];
  if (!foutname)
  {
    // If second filename isn't provided, then decompress or compress depending on infile extension (.srep or not).
    // Output filename is input filename plus .srep for compression, or minus .srep for decompression.
    foutname = new char [strlen(finame) + strlen(SREP_EXT) + 2];
    strcpy(foutname,finame);
    if (end_with(finame,SREP_EXT)) {
      foutname[strlen(foutname)-strlen(SREP_EXT)] = '\0';
      compression = FALSE;
    } else {
      strcat(foutname,SREP_EXT);
    }
  }

  bool single_pass_compression  =  COMPARE_DIGESTS && !REVERSED_LZ;    // -m1 (not -m1f) is the only compression mode that has no need to reread input data
  if (compression && !single_pass_compression && strequ(finame,"-"))
  {
    if (!tempfile)
      tempfile = DEFAULT_TEMPFILE;
    else if (*tempfile==0)
      error (ERROR_IO, "Reading data to compress from stdin without tempfile isn't supported for this method");
  }
  if (!strequ(finame,"-") && strequ(finame,foutname))
    error (ERROR_IO, "Input and output files should have different names");

  FILE *fin = strequ (finame, "-")? stdin : fopen (finame, "rb");
  if (fin == NULL)  error (ERROR_IO, "Can't open %s for read", finame);
  set_binary_mode (fin);

  FILE *fout = strequ (foutname, "-")? stdout : fopen (foutname, "w+b");
  if (fout == NULL)  error (ERROR_IO, "Can't open %s for write", foutname);
  set_binary_mode (fout);

  FILE *fstat = *index_file? fopen (index_file, compression? "wb" : "rb") : (compression? fout : fin);
  if (fstat == NULL)  error (ERROR_IO, "Can't open index file %s for write", index_file);

  FILE *ftemp = NULL;


  STAT header[header_size/sizeof(STAT)];  memset(header, 0, header_size);
  filesize  =  (strequ(finame,"-")? filesize : get_flen(fin));
  Offset origsize = 0,  compsize = sizeof(*header)*4;
  // Reduce default accel value for small L
  if (accel==9000)    accel  =  mymin (mymax(L/32,1), DEFAULT_ACCEL);
  // Maximum acceleration level for main loop is 16; larger -a values only increase bitarr[]
  unsigned ACCELERATOR = mymin(accel,16),  BITARR_ACCELERATOR = accel*8;

  if (compression)
  {
    //*********************************************************************************************************
    /// COMPRESSION
    //*********************************************************************************************************

    ftemp  =  (tempfile && *tempfile)? fopen (tempfile, "w+b") : (strequ (finame, "-")? fin : fopen (finame, "rb"));
    if (ftemp == NULL)  error (ERROR_IO, "Can't open tempfile %s for write", tempfile);
    if (tempfile && *tempfile)  use_mmap = false;

    COMPRESSED_BLOCK *first_block,  **last_block = &first_block;                 // head of blocks linked list in REVERSED_LZ mode
    Offset lz_matches_count = 0;                                                 // LZ matches found
    {
      MMAP_FILE mmap_infile(use_mmap, ftemp, "r", filesize);
      HashTable h(ROUND_MATCHES, COMPARE_DIGESTS, L, BITARR_ACCELERATOR, mmap_infile, filesize, LargePageMode);
      BG_COMPRESSION_THREAD bg_thread(COMPARE_DIGESTS, L, REVERSED_LZ, md5, filesize, bufsize, header_size, h, mmap_infile, fin, fout, fstat);
      double memreq = (h.memreq()+bg_thread.memreq()) / mb;
      if (h.errcode() || bg_thread.errcode)
        error (ERROR_MEMORY, "Can't allocate memory: %.0lf mb required", memreq);
      if (verbosity > 1)
        fprintf (stderr, "%s (%s): input size %.0lf mb, memory used %.0lf mb, -m%d%s -l%d -c%d -a%d%s\n", program_version, program_date, double(filesize/mb), memreq, method, REVERSED_LZ?"f":"", min_match, L, ACCELERATOR, use_mmap? " -mmap":"");

      // Write compressed file header
      header[0] = BULAT_ZIGANSHIN_SIGNATURE;
      header[1] = SREP_SIGNATURE;
      header[2] = (REVERSED_LZ? SREP_FORMAT_VERSION3 : (ROUND_MATCHES? SREP_FORMAT_VERSION1 : SREP_FORMAT_VERSION2))
                  + SREP_FORMAT_NOMD5 * (md5? 0 : 1);
      header[3] = L;
      checked_file_write (fout, header, sizeof(*header)*4);

      // Compress data by 8mb (bufsize) blocks until EOF
      for(;;)
      {
        // Read next input block (saving its copy to tempfile)
        char *buf, *outbuf, *out;  STAT *statbuf, *stat, *header;
        int len = bg_thread.read (&buf, &outbuf, &statbuf, &header);   // Read data from file
        if (bg_thread.errcode)  {errcode = bg_thread.errcode; goto cleanup;}
        if (len==0) break;
        if (tempfile && *tempfile) {
          file_seek (ftemp, origsize);
          checked_file_write (ftemp, buf, len);
        }

        // Compress the block
        switch (ACCELERATOR)
        {
          case  0:  compress< 0>(ROUND_MATCHES,L,min_match,origsize,h, buf,len,outbuf,statbuf,out,stat); break;
          case  1:  compress< 1>(ROUND_MATCHES,L,min_match,origsize,h, buf,len,outbuf,statbuf,out,stat); break;
          case  2:  compress< 2>(ROUND_MATCHES,L,min_match,origsize,h, buf,len,outbuf,statbuf,out,stat); break;
          case  4:  compress< 4>(ROUND_MATCHES,L,min_match,origsize,h, buf,len,outbuf,statbuf,out,stat); break;
          case  8:  compress< 8>(ROUND_MATCHES,L,min_match,origsize,h, buf,len,outbuf,statbuf,out,stat); break;
          case 16:  compress<16>(ROUND_MATCHES,L,min_match,origsize,h, buf,len,outbuf,statbuf,out,stat); break;
        }

        // Fill compressed block header
        unsigned stat_size  =  (char*)stat - (char*)statbuf;
        header[0] = out-outbuf;
        header[1] = len;
        header[2] = stat_size;

        if (!REVERSED_LZ)
        {
          // Write compressed block to output file(s)
          bg_thread.write (stat_size, out-outbuf);
          if (bg_thread.errcode)  {errcode = bg_thread.errcode; goto cleanup;}
        }
        else // In REVERSED_LZ mode, we just store matches at the first pass
        {
          lz_matches_count += (stat - statbuf) / STATS_PER_MATCH(ROUND_MATCHES);

          // Save header[] and statbuf[] to the COMPRESSED_BLOCK struct
          int blocksize = sizeof(COMPRESSED_BLOCK) + header_size + stat_size;
          COMPRESSED_BLOCK *block = (COMPRESSED_BLOCK *) new char[blocksize];

          block->start = origsize;
          block->size  = header[1];
          block->end   = block->start + block->size;
          block->header  = (STAT*)(block+1);
          block->statbuf = (STAT*)((char*)block->header + header_size);
          block->statend = (STAT*)((char*)block->statbuf + stat_size);
          memcpy(block->header,  header,  header_size);
          memcpy(block->statbuf, statbuf, stat_size);

          // Join COMPRESSED_BLOCK structs into linked list
          *last_block = block;
          last_block = &block->next;

          if (ROUND_MATCHES)
            compsize += stat_size / STATS_PER_MATCH(ROUND_MATCHES);   // Добавить размер одного слова STAT из-за того, что данные собираются с ROUND_MATCHES (по 12 байт), а кодироваться будут без него (по 16 байт)
        }

        // Update statistics
        compsize += header[0] + header[2] + header_size;
        origsize += header[1];
        if (verbosity)
        {

          double CPUTime=GetCPUTime(),  GlobalTime=GetGlobalTime()-GlobalTime0;   char temp1[100], temp2[100], temp3[100], temp4[100], temp5[100], temp6[100], temp7[100], counters[200];
          Offset x = pc.check_len-pc.record_match;
          sprintf (counters, "PC %s+%s+%s  %s%s+%s%s.  ",
                           show3(pc.find_match,temp1), show3(pc.find_match_memaccess,temp2), show3(pc.check_hasharr,temp3),
                           show3(pc.record_match,temp4), x?show3(x,temp5,"+"):"", show3(pc.hash_found-pc.check_len,temp6),
                           pc.max_offset<Offset(-1)? show3(pc.total_match_len,temp7,"  "):"");

          fprintf (stderr, "\r%d%%: %s -> %s: %.2lf%%.  %sCpu %.0lf mb/s (%.3lf sec), real %.0lf mb/s (%.3lf sec) = %.0lf%%%s",
                           int(double(origsize)*100/filesize),  show3(origsize,temp1),  show3(compsize,temp2),  double(compsize)*100/origsize, print_pc? counters:"",
                           origsize/CPUTime/mb, CPUTime, origsize/GlobalTime/mb, GlobalTime, CPUTime/GlobalTime*100, newline);
        }
      }

      // Wait until all compressed data are successfully saved to disk
      bg_thread.wait();
      if (bg_thread.errcode)  {errcode = bg_thread.errcode; goto cleanup;}
    }


    //*********************************************************************************************************
    /// SECOND PASS FOR REVERSED_LZ MODE
    //*********************************************************************************************************

    if (REVERSED_LZ)
    {
      *last_block = NULL;   // Mark end of linked list
      if (verbosity)
        fprintf (stderr, "\nSorting matches...");

      char *buf = new char[bufsize+1];
      char *outbuf  = new char[bufsize], *out;
      STAT *statbuf = new STAT[MAX_STATS_PER_BLOCK(bufsize,L)+ADDITIONAL_8MB/sizeof(STAT)], *stat;    // for every L input bytes, we can write up to 4 STAT values to statbuf

      // 1. Fill lz_matches[] with matches from all compressed blocks
      LZ_MATCH *lz_matches = new LZ_MATCH[lz_matches_count+1];          // +1 is for the loop barrier
      int i = 0;                                                        // lz_matches[] index

      for (COMPRESSED_BLOCK *block = first_block;  block;  block = block->next)
      {
        // Copy to lz_matches[] all matches from the block
        Offset block_pos = block->start;                                // current position in the input file
        for (STAT *stat = block->statbuf; stat < block->statend; )
        {
          // Copy one LZ match record from stat[] to lz_matches[]
          DECODE_LZ_MATCH(stat, false, ROUND_MATCHES, L, block_pos,  lit_len, LZ_MATCH, lz_match);
          lz_matches[i++]  = lz_match;
          block_pos       += lit_len + lz_match.len;
        }
      }


      // 2. Sort array by absolute position of LZ match source
      std::sort (lz_matches, lz_matches+lz_matches_count, order_by_LZ_match_src);
      lz_matches[lz_matches_count].src = origsize;   // Loop barrier


      // 3. Process input file once again, joining future-LZ matches info with literal data
      file_seek (ftemp, 0);  Offset processed = 0;  i = 0;
      for (COMPRESSED_BLOCK *block = first_block; block; block = block->next )
      {
        // Read next input block
        checked_file_read (ftemp, buf, block->size);

        // Fill stat[] with future-LZ matches whose LZ.src lies in the current block
        stat = statbuf;  Offset block_pos = block->start;
        int saved_i = i;                                                // First match that should be checked in the next block
        for (;  lz_matches[i].src < block->end;  i++)
        {
          if (lz_matches[i].src+lz_matches[i].len <= block->start)      // Skip any matches entirely owned by previous blocks, updating saved_i too
            {saved_i = i; continue;}
          Offset src = mymax (lz_matches[i].src, block->start);         // Truncate match if it starts before block->start ...
          STAT   len = lz_matches[i].len - (src-lz_matches[i].src);
                 len = mymin (len, block->end - src);                   // ... or ends after block->end
          ENCODE_LZ_MATCH(stat, false, L,  src - block_pos, lz_matches[i].dest - lz_matches[i].src, len);
          block_pos = src;
        }
        i = saved_i;

        // Copy literal data, not covered by LZ matches, to outbuf[]
        char *in = buf,  *out = outbuf;
        {for (STAT *stat = block->statbuf; stat < block->statend; )
        {
          DECODE_LZ_MATCH(stat, false, ROUND_MATCHES, L, 0,  lit_len, LZ_MATCH, lz_match);
          memcpy(out, in, lit_len);
          out += lit_len;
          in  += lit_len + lz_match.len;
        }}
        memcpy(out, in, block->size - (in-buf));
        out += block->size - (in-buf);

        // Fill compressed block header
        unsigned stat_size  =  (char*)stat - (char*)statbuf;
        block->header[2] = stat_size;

        // Write compressed block to output file(s)
        checked_file_write (fout,  block->header, header_size);
        checked_file_write (fstat, statbuf,       stat_size);
        checked_file_write (fout,  outbuf,        out-outbuf);

        if (verbosity)
          fprintf (stderr, "\rSecond pass: %1.0lf%%   \b\b\b", double(processed+=block->size)*100/origsize);
      }
    }
  }
  else
  {
    //*********************************************************************************************************
    /// DECOMPRESSION
    //*********************************************************************************************************

    unsigned compbufsize = bufsize + 4*sizeof(STAT) + ADDITIONAL_8MB;
    char *buf     = new char[compbufsize];
    STAT *statbuf = (STAT*) buf;
    char *out     = new char[bufsize];

    int io_mem = vm_block+bufsize+compbufsize+8*mb;
    MEMORY_MANAGER mm (vm_mem>=io_mem+vm_block*4? vm_mem-io_mem : vm_block*4);
    VIRTUAL_MEMORY_MANAGER vm(vmfile_name, vm_block);
    LZ_MATCH_HEAP lz_matches;
    FUTURE_LZ_MATCH barrier;  barrier.dest = Offset(-1);  lz_matches.insert(barrier);

    // Check header of compressed file
    int len = file_read (fin, header, sizeof(*header)*4);
    if (len != sizeof(*header)*4
     || header[0] != BULAT_ZIGANSHIN_SIGNATURE
     || header[1] != SREP_SIGNATURE)            error (ERROR_COMPRESSION, "Not an SREP compressed file: %s", finame);
    int format_version  =  header[2] & ~SREP_FORMAT_NOMD5;
    if (format_version < SREP_FORMAT_VERSION1
     || format_version > SREP_FORMAT_VERSION3)       error (ERROR_COMPRESSION, "Incompatible compressed data format: v%d (this program supports only v%d..v%d) in file %s", format_version, SREP_FORMAT_VERSION1, SREP_FORMAT_VERSION3, finame);

    // Get compression params from the header
    L = header[3];
    if ((header[2] & SREP_FORMAT_NOMD5)  &&  md5) {
      md5 = false;
      fprintf (stderr, "MD5 checksums can't be checked since they aren't saved in the compressed data\n");
    }
    bool ROUND_MATCHES  =  (format_version == SREP_FORMAT_VERSION1);
    bool REVERSED_LZ    =  (format_version == SREP_FORMAT_VERSION3);
    if (!(REVERSED_LZ && maximum_save==unsigned(-1)) && strequ(foutname,"-"))
    {
      if (!tempfile)
        tempfile = DEFAULT_TEMPFILE;
      else if (*tempfile==0)
        error (ERROR_IO, "Writing decompressed data to stdout without tempfile isn't supported for this file and settings");
    }

    ftemp  =  (tempfile && *tempfile)? fopen (tempfile, "w+b") : fout;
    if (ftemp == NULL)  error (ERROR_IO, "Can't open tempfile %s for write", tempfile);

    // Decompress data by blocks until EOF
    for(;;)
    {
      // Read block header
      int len = file_read (fin, header, header_size);
      if (len==0 && lz_matches.size()==1)  break;
      if (len!=header_size)   error (ERROR_COMPRESSION, "Decompression problem: unexpected end of file");
      unsigned compsize1 = header[0]+header[2],
               origsize1 = header[1],
               statsize1 = header[2];
      if (origsize1>bufsize)                                                         error (ERROR_COMPRESSION, "Decompression problem: uncompressed block size is %u bytes, while maximum supported size is %u bytes", origsize1, bufsize);
      if (compsize1>compbufsize || header[0]>compbufsize || header[2]>compbufsize)   error (ERROR_COMPRESSION, "Decompression problem: compressed block size is %u bytes, while maximum supported size is %u bytes",   compsize1, compbufsize);

      // Read compressed data
      char *buf = (char*)statbuf;
      len  = file_read (fstat, buf,           statsize1);
      len += file_read (fin,   buf+statsize1, compsize1-statsize1);
      if (len!=compsize1)   error (ERROR_COMPRESSION, "Decompression problem: unexpected end of input file or I/O error");

      // Perform decompression
      bool ok = REVERSED_LZ?
                  decompress_reversed_LZ (ROUND_MATCHES, L, ftemp, origsize, statbuf, buf+statsize1, buf+compsize1, out, out+origsize1, mm, vm, lz_matches, maximum_save)
                : decompress             (ROUND_MATCHES, L, ftemp, origsize, statbuf, buf+statsize1, buf+compsize1, out, out+origsize1);
      if (!ok)   error (ERROR_COMPRESSION, "Decompression problem: broken compressed data");

      // Check MD5 sum of decompressed data
      if (md5) {
        Checksum chks;
        compute_checksum (out,origsize1, &chks);
        if (0!=memcmp(chks, header+3, sizeof(Checksum)))   error (ERROR_COMPRESSION, "Decompression problem: checksum of decompressed data is not the same as checksum of original data");
      }

      // Write decompressed data to output file, plus to temporary file if it's different
      file_seek (ftemp, origsize);
      checked_file_write (ftemp, out, origsize1);
      if (tempfile && *tempfile)
        checked_file_write (fout, out, origsize1);

      // Update statistics
      compsize += header_size + compsize1;
      origsize += origsize1;
      if (verbosity)
      {
        char stats[1000], total_reads_str[100], vm_stats_str[100], temp1[100], temp2[100];
        double CPUTime=GetCPUTime(),  GlobalTime=GetGlobalTime()-GlobalTime0;
        sprintf (total_reads_str, maximum_save != unsigned(-1)? ", I/Os %.0lf":"", double(total_reads));
        sprintf (vm_stats_str, vm.total_write? ", VM %d/%d, R/W %d/%d":"", int(vm.current_mem()/mb), int(vm.max_mem()/mb), int(vm.total_read/mb), int(vm.total_write/mb));
        sprintf (stats, REVERSED_LZ? ".  Matches %.0lf %.0lf %.0lf%s, RAM %d/%d%s":"",
                 double(cur_matches), double(max_matches), double(total_matches), total_reads_str,
                 int(mm.current_mem()/mb), int(mm.max_mem()/mb), vm_stats_str);
        fprintf (stderr, "\r%d%%: %s -> %s: %.2lf%%.  Cpu %.0lf mb/s (%.3lf sec), real %.0lf mb/s (%.3lf sec) = %.0lf%%%s%s",
                 int(double(compsize)*100/filesize), show3(compsize,temp1), show3(origsize,temp2), double(compsize)*100/origsize,
                 origsize/CPUTime/mb, CPUTime, origsize/GlobalTime/mb, GlobalTime, CPUTime/GlobalTime*100, stats, newline);
      }
    }
  }


  //*********************************************************************************************************
  /// CLOSE FILES
  //*********************************************************************************************************

cleanup:
  fprintf (stderr, "\n");
  fclose(fin);
  fclose(fout);
  if (fstat!=fin && fstat!=fout)
    fclose(fstat);
  if (ftemp!=fin && ftemp!=fout)
    fclose(ftemp);
  tempfile && remove(tempfile);
  if (errcode)
  {
    // Delete output files on error
    if (!strequ(foutname,"-"))
      remove(foutname);
    if (index_file)
      remove(index_file);
    return errcode;
  }
  if (warnings==0 && delete_input_files && !strequ(finame,"-"))
    remove(finame);
  return warnings? WARNINGS : NO_ERRORS;
}
