/*
  ** Batching **
  This is the "low-latency" variant of the GZIP reference design. It differs
  from the "high-bandwidth" variant in that it tries to minimize the latency
  from when the input file is available in host memory to when the compressed
  result is available in host memory, particulary for small (< 128KB) input
  files. Universal Shared Memory (USM) is used to reduce latency whereby the
  kernel directly accesses the input/output buffers, physically located in host
  memory. This is in contrast to the "high bandwidth" variant where SYCL Buffers
  are DMA'ed to/from the FPGA's attached DDR. USM instead allows for a "zero
  copy" design, which reduces overall latency. It takes some time to relaunch
  the gzip engine and therefore, in order to maximize system throughput, it's
  important to feed the gzip engine with enough data to keep it busy while the
  next launch is being prepared. If done successfully, the kernel relaunch time
  overlaps with kernel execution and there is very little downtime between
  kernel invocations. Since this reference design is intended to be used with
  small files, it's typical that one file is not enough to keep the engine busy.
  Therefore the concept of "batching" is introduced. This simply means that the
  gzip engine compresses multiple input files, per invocation. The minimum size
  of the batch should be chosen to cover the relaunch latency and the maximum
  size should be chosen to result in a desireable overall execution time (i.e. a
  large batch size may take longer than desired to execute, thereby elongating
  overall system latency). Determining the proper batch size takes some
  experimentation.

  The 3 kernels that comprise the gzip engine are separated into separate
  functions. Each function contains a "batch loop" which simply iterates over
  the kernel code, once per file in the batch. The batch loop has loop
  pipelining disabled. This is a clear way to communicate to the compiler that
  files in the batch are independent from each other. This means there's a
  little bit of ramp-down/up of the batch loop between files. It's possible to
  pipeline the batch loop to slightly improve performance, at the cost of area
  (all variables in the loop become privatized and copied).

  The pointers to the buffers in a batch are passed to the kernel via kernel
  args. By having separate kernel arguments for each pointer we are able to
  clearly communicate to the compiler that these pointers should be treated as
  'restrict' (i.e. they will not point to the same place, which is true in this
  application). An alternative implementation to store an array of pointers in
  host-memory which the kernel then reads, but this makes it more difficult to
  communicate that these pointers don't alias.
*/

#include <sycl/sycl.hpp>
#include <sycl/ext/intel/fpga_extensions.hpp>
#include <vector>

#include "gzipkernel_ll.hpp"
#include "kernels.hpp"
#include "pipe_utils.hpp" // Included from DirectProgramming/C++SYCL_FPGA/include/


using namespace sycl;

// Pipes, for inter-kernel data transfer..
using acc_dist_channel_array =
  fpga_tools::PipeArray<          // Defined in "pipe_utils.hpp".
    class dist_channel_pipe_id,   // An identifier for the pipe.
    struct DistLen,               // The type of data in the pipe.
    32,                           // The capacity of each pipe.
    NUM_ENGINES                   // array dimension.
  >;

using acc_dist_channel_last_array =
    fpga_tools::PipeArray<
      class dist_channel_last_pipe_id,
      struct DistLen,
      32,
      NUM_ENGINES
    >;

using acc_lz_to_crc_channel_array =
    fpga_tools::PipeArray<
      class crc_channel_pipe_id,
      char_arr_32,
      32,
      NUM_ENGINES
    >;

template <int Begin, int End>
struct Unroller {
  template <typename Action>
  static void step(const Action &action) {
    action(std::integral_constant<int, Begin>());
    Unroller<Begin + 1, End>::step(action);
  }
};

template <int End>
struct Unroller<End, End> {
  template <typename Action>
  static void step(const Action &action) {}
};

int GetHuffLiteralBits(unsigned char ch) {
  CtData static_ltree[kLCodes + 2] = {
      {12, 8},  {140, 8}, {76, 8},  {204, 8}, {44, 8},  {172, 8}, {108, 8},
      {236, 8}, {28, 8},  {156, 8}, {92, 8},  {220, 8}, {60, 8},  {188, 8},
      {124, 8}, {252, 8}, {2, 8},   {130, 8}, {66, 8},  {194, 8}, {34, 8},
      {162, 8}, {98, 8},  {226, 8}, {18, 8},  {146, 8}, {82, 8},  {210, 8},
      {50, 8},  {178, 8}, {114, 8}, {242, 8}, {10, 8},  {138, 8}, {74, 8},
      {202, 8}, {42, 8},  {170, 8}, {106, 8}, {234, 8}, {26, 8},  {154, 8},
      {90, 8},  {218, 8}, {58, 8},  {186, 8}, {122, 8}, {250, 8}, {6, 8},
      {134, 8}, {70, 8},  {198, 8}, {38, 8},  {166, 8}, {102, 8}, {230, 8},
      {22, 8},  {150, 8}, {86, 8},  {214, 8}, {54, 8},  {182, 8}, {118, 8},
      {246, 8}, {14, 8},  {142, 8}, {78, 8},  {206, 8}, {46, 8},  {174, 8},
      {110, 8}, {238, 8}, {30, 8},  {158, 8}, {94, 8},  {222, 8}, {62, 8},
      {190, 8}, {126, 8}, {254, 8}, {1, 8},   {129, 8}, {65, 8},  {193, 8},
      {33, 8},  {161, 8}, {97, 8},  {225, 8}, {17, 8},  {145, 8}, {81, 8},
      {209, 8}, {49, 8},  {177, 8}, {113, 8}, {241, 8}, {9, 8},   {137, 8},
      {73, 8},  {201, 8}, {41, 8},  {169, 8}, {105, 8}, {233, 8}, {25, 8},
      {153, 8}, {89, 8},  {217, 8}, {57, 8},  {185, 8}, {121, 8}, {249, 8},
      {5, 8},   {133, 8}, {69, 8},  {197, 8}, {37, 8},  {165, 8}, {101, 8},
      {229, 8}, {21, 8},  {149, 8}, {85, 8},  {213, 8}, {53, 8},  {181, 8},
      {117, 8}, {245, 8}, {13, 8},  {141, 8}, {77, 8},  {205, 8}, {45, 8},
      {173, 8}, {109, 8}, {237, 8}, {29, 8},  {157, 8}, {93, 8},  {221, 8},
      {61, 8},  {189, 8}, {125, 8}, {253, 8}, {19, 9},  {275, 9}, {147, 9},
      {403, 9}, {83, 9},  {339, 9}, {211, 9}, {467, 9}, {51, 9},  {307, 9},
      {179, 9}, {435, 9}, {115, 9}, {371, 9}, {243, 9}, {499, 9}, {11, 9},
      {267, 9}, {139, 9}, {395, 9}, {75, 9},  {331, 9}, {203, 9}, {459, 9},
      {43, 9},  {299, 9}, {171, 9}, {427, 9}, {107, 9}, {363, 9}, {235, 9},
      {491, 9}, {27, 9},  {283, 9}, {155, 9}, {411, 9}, {91, 9},  {347, 9},
      {219, 9}, {475, 9}, {59, 9},  {315, 9}, {187, 9}, {443, 9}, {123, 9},
      {379, 9}, {251, 9}, {507, 9}, {7, 9},   {263, 9}, {135, 9}, {391, 9},
      {71, 9},  {327, 9}, {199, 9}, {455, 9}, {39, 9},  {295, 9}, {167, 9},
      {423, 9}, {103, 9}, {359, 9}, {231, 9}, {487, 9}, {23, 9},  {279, 9},
      {151, 9}, {407, 9}, {87, 9},  {343, 9}, {215, 9}, {471, 9}, {55, 9},
      {311, 9}, {183, 9}, {439, 9}, {119, 9}, {375, 9}, {247, 9}, {503, 9},
      {15, 9},  {271, 9}, {143, 9}, {399, 9}, {79, 9},  {335, 9}, {207, 9},
      {463, 9}, {47, 9},  {303, 9}, {175, 9}, {431, 9}, {111, 9}, {367, 9},
      {239, 9}, {495, 9}, {31, 9},  {287, 9}, {159, 9}, {415, 9}, {95, 9},
      {351, 9}, {223, 9}, {479, 9}, {63, 9},  {319, 9}, {191, 9}, {447, 9},
      {127, 9}, {383, 9}, {255, 9}, {511, 9}, {0, 7},   {64, 7},  {32, 7},
      {96, 7},  {16, 7},  {80, 7},  {48, 7},  {112, 7}, {8, 7},   {72, 7},
      {40, 7},  {104, 7}, {24, 7},  {88, 7},  {56, 7},  {120, 7}, {4, 7},
      {68, 7},  {36, 7},  {100, 7}, {20, 7},  {84, 7},  {52, 7},  {116, 7},
      {3, 8},   {131, 8}, {67, 8},  {195, 8}, {35, 8},  {163, 8}, {99, 8},
      {227, 8},
  };
  return static_ltree[ch].code;
}

int GetHuffLiteralLen(unsigned char ch) {
  CtData static_ltree[kLCodes + 2] = {
      {12, 8},  {140, 8}, {76, 8},  {204, 8}, {44, 8},  {172, 8}, {108, 8},
      {236, 8}, {28, 8},  {156, 8}, {92, 8},  {220, 8}, {60, 8},  {188, 8},
      {124, 8}, {252, 8}, {2, 8},   {130, 8}, {66, 8},  {194, 8}, {34, 8},
      {162, 8}, {98, 8},  {226, 8}, {18, 8},  {146, 8}, {82, 8},  {210, 8},
      {50, 8},  {178, 8}, {114, 8}, {242, 8}, {10, 8},  {138, 8}, {74, 8},
      {202, 8}, {42, 8},  {170, 8}, {106, 8}, {234, 8}, {26, 8},  {154, 8},
      {90, 8},  {218, 8}, {58, 8},  {186, 8}, {122, 8}, {250, 8}, {6, 8},
      {134, 8}, {70, 8},  {198, 8}, {38, 8},  {166, 8}, {102, 8}, {230, 8},
      {22, 8},  {150, 8}, {86, 8},  {214, 8}, {54, 8},  {182, 8}, {118, 8},
      {246, 8}, {14, 8},  {142, 8}, {78, 8},  {206, 8}, {46, 8},  {174, 8},
      {110, 8}, {238, 8}, {30, 8},  {158, 8}, {94, 8},  {222, 8}, {62, 8},
      {190, 8}, {126, 8}, {254, 8}, {1, 8},   {129, 8}, {65, 8},  {193, 8},
      {33, 8},  {161, 8}, {97, 8},  {225, 8}, {17, 8},  {145, 8}, {81, 8},
      {209, 8}, {49, 8},  {177, 8}, {113, 8}, {241, 8}, {9, 8},   {137, 8},
      {73, 8},  {201, 8}, {41, 8},  {169, 8}, {105, 8}, {233, 8}, {25, 8},
      {153, 8}, {89, 8},  {217, 8}, {57, 8},  {185, 8}, {121, 8}, {249, 8},
      {5, 8},   {133, 8}, {69, 8},  {197, 8}, {37, 8},  {165, 8}, {101, 8},
      {229, 8}, {21, 8},  {149, 8}, {85, 8},  {213, 8}, {53, 8},  {181, 8},
      {117, 8}, {245, 8}, {13, 8},  {141, 8}, {77, 8},  {205, 8}, {45, 8},
      {173, 8}, {109, 8}, {237, 8}, {29, 8},  {157, 8}, {93, 8},  {221, 8},
      {61, 8},  {189, 8}, {125, 8}, {253, 8}, {19, 9},  {275, 9}, {147, 9},
      {403, 9}, {83, 9},  {339, 9}, {211, 9}, {467, 9}, {51, 9},  {307, 9},
      {179, 9}, {435, 9}, {115, 9}, {371, 9}, {243, 9}, {499, 9}, {11, 9},
      {267, 9}, {139, 9}, {395, 9}, {75, 9},  {331, 9}, {203, 9}, {459, 9},
      {43, 9},  {299, 9}, {171, 9}, {427, 9}, {107, 9}, {363, 9}, {235, 9},
      {491, 9}, {27, 9},  {283, 9}, {155, 9}, {411, 9}, {91, 9},  {347, 9},
      {219, 9}, {475, 9}, {59, 9},  {315, 9}, {187, 9}, {443, 9}, {123, 9},
      {379, 9}, {251, 9}, {507, 9}, {7, 9},   {263, 9}, {135, 9}, {391, 9},
      {71, 9},  {327, 9}, {199, 9}, {455, 9}, {39, 9},  {295, 9}, {167, 9},
      {423, 9}, {103, 9}, {359, 9}, {231, 9}, {487, 9}, {23, 9},  {279, 9},
      {151, 9}, {407, 9}, {87, 9},  {343, 9}, {215, 9}, {471, 9}, {55, 9},
      {311, 9}, {183, 9}, {439, 9}, {119, 9}, {375, 9}, {247, 9}, {503, 9},
      {15, 9},  {271, 9}, {143, 9}, {399, 9}, {79, 9},  {335, 9}, {207, 9},
      {463, 9}, {47, 9},  {303, 9}, {175, 9}, {431, 9}, {111, 9}, {367, 9},
      {239, 9}, {495, 9}, {31, 9},  {287, 9}, {159, 9}, {415, 9}, {95, 9},
      {351, 9}, {223, 9}, {479, 9}, {63, 9},  {319, 9}, {191, 9}, {447, 9},
      {127, 9}, {383, 9}, {255, 9}, {511, 9}, {0, 7},   {64, 7},  {32, 7},
      {96, 7},  {16, 7},  {80, 7},  {48, 7},  {112, 7}, {8, 7},   {72, 7},
      {40, 7},  {104, 7}, {24, 7},  {88, 7},  {56, 7},  {120, 7}, {4, 7},
      {68, 7},  {36, 7},  {100, 7}, {20, 7},  {84, 7},  {52, 7},  {116, 7},
      {3, 8},   {131, 8}, {67, 8},  {195, 8}, {35, 8},  {163, 8}, {99, 8},
      {227, 8},
  };
  return static_ltree[ch].len;
}

int GetHuffRunLen(int _len, int _dist) {
  int lc;
  unsigned code;
  int extra;
  int dist;
  //int local_lbits;
  int local_llen;
  //int local_dbits;
  int local_dlen;
  //local_lbits = 0;
  local_llen = 0;

  int base_length[kLengthCodes] = {
      0,  1,  2,  3,  4,  5,  6,  7,  8,   10,  12,  14,  16,  20, 24,
      28, 32, 40, 48, 56, 64, 80, 96, 112, 128, 160, 192, 224, 0,
  };

  int extra_lbits[kLengthCodes]  // extra bits for each length code
      = {0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2,
         2, 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 0};

  CtData static_ltree[kLCodes + 2] = {
      {12, 8},  {140, 8}, {76, 8},  {204, 8}, {44, 8},  {172, 8}, {108, 8},
      {236, 8}, {28, 8},  {156, 8}, {92, 8},  {220, 8}, {60, 8},  {188, 8},
      {124, 8}, {252, 8}, {2, 8},   {130, 8}, {66, 8},  {194, 8}, {34, 8},
      {162, 8}, {98, 8},  {226, 8}, {18, 8},  {146, 8}, {82, 8},  {210, 8},
      {50, 8},  {178, 8}, {114, 8}, {242, 8}, {10, 8},  {138, 8}, {74, 8},
      {202, 8}, {42, 8},  {170, 8}, {106, 8}, {234, 8}, {26, 8},  {154, 8},
      {90, 8},  {218, 8}, {58, 8},  {186, 8}, {122, 8}, {250, 8}, {6, 8},
      {134, 8}, {70, 8},  {198, 8}, {38, 8},  {166, 8}, {102, 8}, {230, 8},
      {22, 8},  {150, 8}, {86, 8},  {214, 8}, {54, 8},  {182, 8}, {118, 8},
      {246, 8}, {14, 8},  {142, 8}, {78, 8},  {206, 8}, {46, 8},  {174, 8},
      {110, 8}, {238, 8}, {30, 8},  {158, 8}, {94, 8},  {222, 8}, {62, 8},
      {190, 8}, {126, 8}, {254, 8}, {1, 8},   {129, 8}, {65, 8},  {193, 8},
      {33, 8},  {161, 8}, {97, 8},  {225, 8}, {17, 8},  {145, 8}, {81, 8},
      {209, 8}, {49, 8},  {177, 8}, {113, 8}, {241, 8}, {9, 8},   {137, 8},
      {73, 8},  {201, 8}, {41, 8},  {169, 8}, {105, 8}, {233, 8}, {25, 8},
      {153, 8}, {89, 8},  {217, 8}, {57, 8},  {185, 8}, {121, 8}, {249, 8},
      {5, 8},   {133, 8}, {69, 8},  {197, 8}, {37, 8},  {165, 8}, {101, 8},
      {229, 8}, {21, 8},  {149, 8}, {85, 8},  {213, 8}, {53, 8},  {181, 8},
      {117, 8}, {245, 8}, {13, 8},  {141, 8}, {77, 8},  {205, 8}, {45, 8},
      {173, 8}, {109, 8}, {237, 8}, {29, 8},  {157, 8}, {93, 8},  {221, 8},
      {61, 8},  {189, 8}, {125, 8}, {253, 8}, {19, 9},  {275, 9}, {147, 9},
      {403, 9}, {83, 9},  {339, 9}, {211, 9}, {467, 9}, {51, 9},  {307, 9},
      {179, 9}, {435, 9}, {115, 9}, {371, 9}, {243, 9}, {499, 9}, {11, 9},
      {267, 9}, {139, 9}, {395, 9}, {75, 9},  {331, 9}, {203, 9}, {459, 9},
      {43, 9},  {299, 9}, {171, 9}, {427, 9}, {107, 9}, {363, 9}, {235, 9},
      {491, 9}, {27, 9},  {283, 9}, {155, 9}, {411, 9}, {91, 9},  {347, 9},
      {219, 9}, {475, 9}, {59, 9},  {315, 9}, {187, 9}, {443, 9}, {123, 9},
      {379, 9}, {251, 9}, {507, 9}, {7, 9},   {263, 9}, {135, 9}, {391, 9},
      {71, 9},  {327, 9}, {199, 9}, {455, 9}, {39, 9},  {295, 9}, {167, 9},
      {423, 9}, {103, 9}, {359, 9}, {231, 9}, {487, 9}, {23, 9},  {279, 9},
      {151, 9}, {407, 9}, {87, 9},  {343, 9}, {215, 9}, {471, 9}, {55, 9},
      {311, 9}, {183, 9}, {439, 9}, {119, 9}, {375, 9}, {247, 9}, {503, 9},
      {15, 9},  {271, 9}, {143, 9}, {399, 9}, {79, 9},  {335, 9}, {207, 9},
      {463, 9}, {47, 9},  {303, 9}, {175, 9}, {431, 9}, {111, 9}, {367, 9},
      {239, 9}, {495, 9}, {31, 9},  {287, 9}, {159, 9}, {415, 9}, {95, 9},
      {351, 9}, {223, 9}, {479, 9}, {63, 9},  {319, 9}, {191, 9}, {447, 9},
      {127, 9}, {383, 9}, {255, 9}, {511, 9}, {0, 7},   {64, 7},  {32, 7},
      {96, 7},  {16, 7},  {80, 7},  {48, 7},  {112, 7}, {8, 7},   {72, 7},
      {40, 7},  {104, 7}, {24, 7},  {88, 7},  {56, 7},  {120, 7}, {4, 7},
      {68, 7},  {36, 7},  {100, 7}, {20, 7},  {84, 7},  {52, 7},  {116, 7},
      {3, 8},   {131, 8}, {67, 8},  {195, 8}, {35, 8},  {163, 8}, {99, 8},
      {227, 8},
  };

  // distance codes. The first 256 values correspond to the distances
  // 3 .. 258, the last 256 values correspond to the top 8 bits of
  // the 15 bit distances.
  unsigned char dist_code[512] = {
      0,  1,  2,  3,  4,  4,  5,  5,  6,  6,  6,  6,  7,  7,  7,  7,  8,  8,
      8,  8,  8,  8,  8,  8,  9,  9,  9,  9,  9,  9,  9,  9,  10, 10, 10, 10,
      10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 11, 11, 11, 11, 11, 11,
      11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 12, 12, 12, 12, 12, 12, 12, 12,
      12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12,
      12, 12, 12, 12, 12, 12, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13,
      13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13,
      13, 13, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14,
      14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14,
      14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14,
      14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 15, 15, 15, 15, 15, 15,
      15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15,
      15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15,
      15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15,
      15, 15, 15, 15, 0,  0,  16, 17, 18, 18, 19, 19, 20, 20, 20, 20, 21, 21,
      21, 21, 22, 22, 22, 22, 22, 22, 22, 22, 23, 23, 23, 23, 23, 23, 23, 23,
      24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 25, 25,
      25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 26, 26, 26, 26,
      26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26,
      26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 27, 27, 27, 27, 27, 27, 27, 27,
      27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27,
      27, 27, 27, 27, 27, 27, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28,
      28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28,
      28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28,
      28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 29, 29,
      29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29,
      29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29,
      29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29,
      29, 29, 29, 29, 29, 29, 29, 29,
  };
  // length code for each normalized match length (0 == kMinMatch)
  unsigned char length_code[kMaxMatch - kMinMatch + 1] = {
      0,  1,  2,  3,  4,  5,  6,  7,  8,  8,  9,  9,  10, 10, 11, 11, 12, 12,
      12, 12, 13, 13, 13, 13, 14, 14, 14, 14, 15, 15, 15, 15, 16, 16, 16, 16,
      16, 16, 16, 16, 17, 17, 17, 17, 17, 17, 17, 17, 18, 18, 18, 18, 18, 18,
      18, 18, 19, 19, 19, 19, 19, 19, 19, 19, 20, 20, 20, 20, 20, 20, 20, 20,
      20, 20, 20, 20, 20, 20, 20, 20, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21,
      21, 21, 21, 21, 21, 21, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22,
      22, 22, 22, 22, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23,
      23, 23, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
      24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 25, 25,
      25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
      25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 26, 26, 26, 26, 26, 26,
      26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26,
      26, 26, 26, 26, 26, 26, 26, 26, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27,
      27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27,
      27, 27, 27, 28,
  };

  int extra_dbits[kDCodes]  // extra bits for each distance code
      = {0, 0, 0, 0, 1, 1, 2, 2,  3,  3,  4,  4,  5,  5,  6,
         6, 7, 7, 8, 8, 9, 9, 10, 10, 11, 11, 12, 12, 13, 13};

  int base_dist[kDCodes] = {
      0,    1,    2,    3,    4,    6,    8,    12,    16,    24,
      32,   48,   64,   96,   128,  192,  256,  384,   512,   768,
      1024, 1536, 2048, 3072, 4096, 6144, 8192, 12288, 16384, 24576,
  };

  CtData static_dtree[kDCodes] = {
      {0, 5}, {16, 5}, {8, 5},  {24, 5}, {4, 5}, {20, 5}, {12, 5}, {28, 5},
      {2, 5}, {18, 5}, {10, 5}, {26, 5}, {6, 5}, {22, 5}, {14, 5}, {30, 5},
      {1, 5}, {17, 5}, {9, 5},  {25, 5}, {5, 5}, {21, 5}, {13, 5}, {29, 5},
      {3, 5}, {19, 5}, {11, 5}, {27, 5}, {7, 5}, {23, 5},
  };

  lc = _len - kMinMatch;
  code = length_code[lc];

  //local_lbits = static_ltree[code + kLiterals + 1].code;
  local_llen = static_ltree[code + kLiterals + 1].len;
  extra = extra_lbits[code];
  if (extra) {
    lc -= base_length[code];
    //local_lbits |= lc << local_llen;
    local_llen += extra;
  }

  dist = _dist;
  dist--;
  code = d_code(dist);
  //local_dbits = static_dtree[code].code;
  local_dlen = static_dtree[code].len;
  extra = extra_dbits[code];
  if (extra) {
    dist -= base_dist[code];
    //local_dbits |= dist << local_dlen;
    local_dlen += extra;
  }

  //local_lbits |= local_dbits << local_llen;
  local_llen += local_dlen;

  return local_llen;
}

int GetHuffRunBits(int _len, int _dist) {
  int lc;
  unsigned code;
  int extra;
  int dist;
  int local_lbits, local_llen;
  int local_dbits, local_dlen;
  local_lbits = 0;
  local_llen = 0;

  int base_length[kLengthCodes] = {
      0,  1,  2,  3,  4,  5,  6,  7,  8,   10,  12,  14,  16,  20, 24,
      28, 32, 40, 48, 56, 64, 80, 96, 112, 128, 160, 192, 224, 0,
  };

  int extra_lbits[kLengthCodes]  // extra bits for each length code
      = {0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2,
         2, 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 0};

  CtData static_ltree[kLCodes + 2] = {
      {12, 8},  {140, 8}, {76, 8},  {204, 8}, {44, 8},  {172, 8}, {108, 8},
      {236, 8}, {28, 8},  {156, 8}, {92, 8},  {220, 8}, {60, 8},  {188, 8},
      {124, 8}, {252, 8}, {2, 8},   {130, 8}, {66, 8},  {194, 8}, {34, 8},
      {162, 8}, {98, 8},  {226, 8}, {18, 8},  {146, 8}, {82, 8},  {210, 8},
      {50, 8},  {178, 8}, {114, 8}, {242, 8}, {10, 8},  {138, 8}, {74, 8},
      {202, 8}, {42, 8},  {170, 8}, {106, 8}, {234, 8}, {26, 8},  {154, 8},
      {90, 8},  {218, 8}, {58, 8},  {186, 8}, {122, 8}, {250, 8}, {6, 8},
      {134, 8}, {70, 8},  {198, 8}, {38, 8},  {166, 8}, {102, 8}, {230, 8},
      {22, 8},  {150, 8}, {86, 8},  {214, 8}, {54, 8},  {182, 8}, {118, 8},
      {246, 8}, {14, 8},  {142, 8}, {78, 8},  {206, 8}, {46, 8},  {174, 8},
      {110, 8}, {238, 8}, {30, 8},  {158, 8}, {94, 8},  {222, 8}, {62, 8},
      {190, 8}, {126, 8}, {254, 8}, {1, 8},   {129, 8}, {65, 8},  {193, 8},
      {33, 8},  {161, 8}, {97, 8},  {225, 8}, {17, 8},  {145, 8}, {81, 8},
      {209, 8}, {49, 8},  {177, 8}, {113, 8}, {241, 8}, {9, 8},   {137, 8},
      {73, 8},  {201, 8}, {41, 8},  {169, 8}, {105, 8}, {233, 8}, {25, 8},
      {153, 8}, {89, 8},  {217, 8}, {57, 8},  {185, 8}, {121, 8}, {249, 8},
      {5, 8},   {133, 8}, {69, 8},  {197, 8}, {37, 8},  {165, 8}, {101, 8},
      {229, 8}, {21, 8},  {149, 8}, {85, 8},  {213, 8}, {53, 8},  {181, 8},
      {117, 8}, {245, 8}, {13, 8},  {141, 8}, {77, 8},  {205, 8}, {45, 8},
      {173, 8}, {109, 8}, {237, 8}, {29, 8},  {157, 8}, {93, 8},  {221, 8},
      {61, 8},  {189, 8}, {125, 8}, {253, 8}, {19, 9},  {275, 9}, {147, 9},
      {403, 9}, {83, 9},  {339, 9}, {211, 9}, {467, 9}, {51, 9},  {307, 9},
      {179, 9}, {435, 9}, {115, 9}, {371, 9}, {243, 9}, {499, 9}, {11, 9},
      {267, 9}, {139, 9}, {395, 9}, {75, 9},  {331, 9}, {203, 9}, {459, 9},
      {43, 9},  {299, 9}, {171, 9}, {427, 9}, {107, 9}, {363, 9}, {235, 9},
      {491, 9}, {27, 9},  {283, 9}, {155, 9}, {411, 9}, {91, 9},  {347, 9},
      {219, 9}, {475, 9}, {59, 9},  {315, 9}, {187, 9}, {443, 9}, {123, 9},
      {379, 9}, {251, 9}, {507, 9}, {7, 9},   {263, 9}, {135, 9}, {391, 9},
      {71, 9},  {327, 9}, {199, 9}, {455, 9}, {39, 9},  {295, 9}, {167, 9},
      {423, 9}, {103, 9}, {359, 9}, {231, 9}, {487, 9}, {23, 9},  {279, 9},
      {151, 9}, {407, 9}, {87, 9},  {343, 9}, {215, 9}, {471, 9}, {55, 9},
      {311, 9}, {183, 9}, {439, 9}, {119, 9}, {375, 9}, {247, 9}, {503, 9},
      {15, 9},  {271, 9}, {143, 9}, {399, 9}, {79, 9},  {335, 9}, {207, 9},
      {463, 9}, {47, 9},  {303, 9}, {175, 9}, {431, 9}, {111, 9}, {367, 9},
      {239, 9}, {495, 9}, {31, 9},  {287, 9}, {159, 9}, {415, 9}, {95, 9},
      {351, 9}, {223, 9}, {479, 9}, {63, 9},  {319, 9}, {191, 9}, {447, 9},
      {127, 9}, {383, 9}, {255, 9}, {511, 9}, {0, 7},   {64, 7},  {32, 7},
      {96, 7},  {16, 7},  {80, 7},  {48, 7},  {112, 7}, {8, 7},   {72, 7},
      {40, 7},  {104, 7}, {24, 7},  {88, 7},  {56, 7},  {120, 7}, {4, 7},
      {68, 7},  {36, 7},  {100, 7}, {20, 7},  {84, 7},  {52, 7},  {116, 7},
      {3, 8},   {131, 8}, {67, 8},  {195, 8}, {35, 8},  {163, 8}, {99, 8},
      {227, 8},
  };

  // distance codes. The first 256 values correspond to the distances
  // 3 .. 258, the last 256 values correspond to the top 8 bits of
  // the 15 bit distances.
  unsigned char dist_code[512] = {
      0,  1,  2,  3,  4,  4,  5,  5,  6,  6,  6,  6,  7,  7,  7,  7,  8,  8,
      8,  8,  8,  8,  8,  8,  9,  9,  9,  9,  9,  9,  9,  9,  10, 10, 10, 10,
      10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 11, 11, 11, 11, 11, 11,
      11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 12, 12, 12, 12, 12, 12, 12, 12,
      12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12,
      12, 12, 12, 12, 12, 12, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13,
      13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13,
      13, 13, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14,
      14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14,
      14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14,
      14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 15, 15, 15, 15, 15, 15,
      15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15,
      15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15,
      15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15,
      15, 15, 15, 15, 0,  0,  16, 17, 18, 18, 19, 19, 20, 20, 20, 20, 21, 21,
      21, 21, 22, 22, 22, 22, 22, 22, 22, 22, 23, 23, 23, 23, 23, 23, 23, 23,
      24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 25, 25,
      25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 26, 26, 26, 26,
      26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26,
      26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 27, 27, 27, 27, 27, 27, 27, 27,
      27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27,
      27, 27, 27, 27, 27, 27, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28,
      28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28,
      28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28,
      28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 29, 29,
      29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29,
      29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29,
      29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29,
      29, 29, 29, 29, 29, 29, 29, 29,
  };
  // length code for each normalized match length (0 == kMinMatch)
  unsigned char length_code[kMaxMatch - kMinMatch + 1] = {
      0,  1,  2,  3,  4,  5,  6,  7,  8,  8,  9,  9,  10, 10, 11, 11, 12, 12,
      12, 12, 13, 13, 13, 13, 14, 14, 14, 14, 15, 15, 15, 15, 16, 16, 16, 16,
      16, 16, 16, 16, 17, 17, 17, 17, 17, 17, 17, 17, 18, 18, 18, 18, 18, 18,
      18, 18, 19, 19, 19, 19, 19, 19, 19, 19, 20, 20, 20, 20, 20, 20, 20, 20,
      20, 20, 20, 20, 20, 20, 20, 20, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21,
      21, 21, 21, 21, 21, 21, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22,
      22, 22, 22, 22, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23,
      23, 23, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
      24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 25, 25,
      25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
      25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 26, 26, 26, 26, 26, 26,
      26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26,
      26, 26, 26, 26, 26, 26, 26, 26, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27,
      27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27,
      27, 27, 27, 28,
  };

  int extra_dbits[kDCodes]  // extra bits for each distance code
      = {0, 0, 0, 0, 1, 1, 2, 2,  3,  3,  4,  4,  5,  5,  6,
         6, 7, 7, 8, 8, 9, 9, 10, 10, 11, 11, 12, 12, 13, 13};

  int base_dist[kDCodes] = {
      0,    1,    2,    3,    4,    6,    8,    12,    16,    24,
      32,   48,   64,   96,   128,  192,  256,  384,   512,   768,
      1024, 1536, 2048, 3072, 4096, 6144, 8192, 12288, 16384, 24576,
  };

  CtData static_dtree[kDCodes] = {
      {0, 5}, {16, 5}, {8, 5},  {24, 5}, {4, 5}, {20, 5}, {12, 5}, {28, 5},
      {2, 5}, {18, 5}, {10, 5}, {26, 5}, {6, 5}, {22, 5}, {14, 5}, {30, 5},
      {1, 5}, {17, 5}, {9, 5},  {25, 5}, {5, 5}, {21, 5}, {13, 5}, {29, 5},
      {3, 5}, {19, 5}, {11, 5}, {27, 5}, {7, 5}, {23, 5},
  };

  lc = _len - kMinMatch;
  code = length_code[lc];

  local_lbits = static_ltree[code + kLiterals + 1].code;
  local_llen = static_ltree[code + kLiterals + 1].len;
  extra = extra_lbits[code];
  if (extra) {
    lc -= base_length[code];
    local_lbits |= lc << local_llen;
    local_llen += extra;
  }

  dist = _dist;
  dist--;
  code = d_code(dist);
  local_dbits = static_dtree[code].code;
  local_dlen = static_dtree[code].len;
  extra = extra_dbits[code];
  if (extra) {
    dist -= base_dist[code];
    local_dbits |= dist << local_dlen;
    local_dlen += extra;
  }

  local_lbits |= local_dbits << local_llen;
  local_llen += local_dlen;

  return local_lbits;
}

int GetHuffLen(int len, int dist, unsigned char ch) {
  int returned_len;

  CtData static_ltree[kLCodes + 2] = {
      {12, 8},  {140, 8}, {76, 8},  {204, 8}, {44, 8},  {172, 8}, {108, 8},
      {236, 8}, {28, 8},  {156, 8}, {92, 8},  {220, 8}, {60, 8},  {188, 8},
      {124, 8}, {252, 8}, {2, 8},   {130, 8}, {66, 8},  {194, 8}, {34, 8},
      {162, 8}, {98, 8},  {226, 8}, {18, 8},  {146, 8}, {82, 8},  {210, 8},
      {50, 8},  {178, 8}, {114, 8}, {242, 8}, {10, 8},  {138, 8}, {74, 8},
      {202, 8}, {42, 8},  {170, 8}, {106, 8}, {234, 8}, {26, 8},  {154, 8},
      {90, 8},  {218, 8}, {58, 8},  {186, 8}, {122, 8}, {250, 8}, {6, 8},
      {134, 8}, {70, 8},  {198, 8}, {38, 8},  {166, 8}, {102, 8}, {230, 8},
      {22, 8},  {150, 8}, {86, 8},  {214, 8}, {54, 8},  {182, 8}, {118, 8},
      {246, 8}, {14, 8},  {142, 8}, {78, 8},  {206, 8}, {46, 8},  {174, 8},
      {110, 8}, {238, 8}, {30, 8},  {158, 8}, {94, 8},  {222, 8}, {62, 8},
      {190, 8}, {126, 8}, {254, 8}, {1, 8},   {129, 8}, {65, 8},  {193, 8},
      {33, 8},  {161, 8}, {97, 8},  {225, 8}, {17, 8},  {145, 8}, {81, 8},
      {209, 8}, {49, 8},  {177, 8}, {113, 8}, {241, 8}, {9, 8},   {137, 8},
      {73, 8},  {201, 8}, {41, 8},  {169, 8}, {105, 8}, {233, 8}, {25, 8},
      {153, 8}, {89, 8},  {217, 8}, {57, 8},  {185, 8}, {121, 8}, {249, 8},
      {5, 8},   {133, 8}, {69, 8},  {197, 8}, {37, 8},  {165, 8}, {101, 8},
      {229, 8}, {21, 8},  {149, 8}, {85, 8},  {213, 8}, {53, 8},  {181, 8},
      {117, 8}, {245, 8}, {13, 8},  {141, 8}, {77, 8},  {205, 8}, {45, 8},
      {173, 8}, {109, 8}, {237, 8}, {29, 8},  {157, 8}, {93, 8},  {221, 8},
      {61, 8},  {189, 8}, {125, 8}, {253, 8}, {19, 9},  {275, 9}, {147, 9},
      {403, 9}, {83, 9},  {339, 9}, {211, 9}, {467, 9}, {51, 9},  {307, 9},
      {179, 9}, {435, 9}, {115, 9}, {371, 9}, {243, 9}, {499, 9}, {11, 9},
      {267, 9}, {139, 9}, {395, 9}, {75, 9},  {331, 9}, {203, 9}, {459, 9},
      {43, 9},  {299, 9}, {171, 9}, {427, 9}, {107, 9}, {363, 9}, {235, 9},
      {491, 9}, {27, 9},  {283, 9}, {155, 9}, {411, 9}, {91, 9},  {347, 9},
      {219, 9}, {475, 9}, {59, 9},  {315, 9}, {187, 9}, {443, 9}, {123, 9},
      {379, 9}, {251, 9}, {507, 9}, {7, 9},   {263, 9}, {135, 9}, {391, 9},
      {71, 9},  {327, 9}, {199, 9}, {455, 9}, {39, 9},  {295, 9}, {167, 9},
      {423, 9}, {103, 9}, {359, 9}, {231, 9}, {487, 9}, {23, 9},  {279, 9},
      {151, 9}, {407, 9}, {87, 9},  {343, 9}, {215, 9}, {471, 9}, {55, 9},
      {311, 9}, {183, 9}, {439, 9}, {119, 9}, {375, 9}, {247, 9}, {503, 9},
      {15, 9},  {271, 9}, {143, 9}, {399, 9}, {79, 9},  {335, 9}, {207, 9},
      {463, 9}, {47, 9},  {303, 9}, {175, 9}, {431, 9}, {111, 9}, {367, 9},
      {239, 9}, {495, 9}, {31, 9},  {287, 9}, {159, 9}, {415, 9}, {95, 9},
      {351, 9}, {223, 9}, {479, 9}, {63, 9},  {319, 9}, {191, 9}, {447, 9},
      {127, 9}, {383, 9}, {255, 9}, {511, 9}, {0, 7},   {64, 7},  {32, 7},
      {96, 7},  {16, 7},  {80, 7},  {48, 7},  {112, 7}, {8, 7},   {72, 7},
      {40, 7},  {104, 7}, {24, 7},  {88, 7},  {56, 7},  {120, 7}, {4, 7},
      {68, 7},  {36, 7},  {100, 7}, {20, 7},  {84, 7},  {52, 7},  {116, 7},
      {3, 8},   {131, 8}, {67, 8},  {195, 8}, {35, 8},  {163, 8}, {99, 8},
      {227, 8},
  };
  switch (len) {
    case -3:
      returned_len = static_ltree[kEndBlock].len;
      break;
    case -2:
      returned_len = 3;
      break;
    case -1:
      returned_len = 0;
      break;
    case 0:
      returned_len = GetHuffLiteralLen(ch);
      break;
    default:
      returned_len = GetHuffRunLen(len, dist);
      break;
  }
  return returned_len;
}

int IsValid(int len, int dist, unsigned char ch) {
  switch (len) {
    case -3:
      return 1;
    case -2:
      return 1;
    case -1:
      return 0;
    case 0:
      return 1;
    default:
      return 1;
  }
}

int GetHuffBits(int len, int dist, unsigned char ch) {
  int bits;
  CtData static_ltree[kLCodes + 2] = {
      {12, 8},  {140, 8}, {76, 8},  {204, 8}, {44, 8},  {172, 8}, {108, 8},
      {236, 8}, {28, 8},  {156, 8}, {92, 8},  {220, 8}, {60, 8},  {188, 8},
      {124, 8}, {252, 8}, {2, 8},   {130, 8}, {66, 8},  {194, 8}, {34, 8},
      {162, 8}, {98, 8},  {226, 8}, {18, 8},  {146, 8}, {82, 8},  {210, 8},
      {50, 8},  {178, 8}, {114, 8}, {242, 8}, {10, 8},  {138, 8}, {74, 8},
      {202, 8}, {42, 8},  {170, 8}, {106, 8}, {234, 8}, {26, 8},  {154, 8},
      {90, 8},  {218, 8}, {58, 8},  {186, 8}, {122, 8}, {250, 8}, {6, 8},
      {134, 8}, {70, 8},  {198, 8}, {38, 8},  {166, 8}, {102, 8}, {230, 8},
      {22, 8},  {150, 8}, {86, 8},  {214, 8}, {54, 8},  {182, 8}, {118, 8},
      {246, 8}, {14, 8},  {142, 8}, {78, 8},  {206, 8}, {46, 8},  {174, 8},
      {110, 8}, {238, 8}, {30, 8},  {158, 8}, {94, 8},  {222, 8}, {62, 8},
      {190, 8}, {126, 8}, {254, 8}, {1, 8},   {129, 8}, {65, 8},  {193, 8},
      {33, 8},  {161, 8}, {97, 8},  {225, 8}, {17, 8},  {145, 8}, {81, 8},
      {209, 8}, {49, 8},  {177, 8}, {113, 8}, {241, 8}, {9, 8},   {137, 8},
      {73, 8},  {201, 8}, {41, 8},  {169, 8}, {105, 8}, {233, 8}, {25, 8},
      {153, 8}, {89, 8},  {217, 8}, {57, 8},  {185, 8}, {121, 8}, {249, 8},
      {5, 8},   {133, 8}, {69, 8},  {197, 8}, {37, 8},  {165, 8}, {101, 8},
      {229, 8}, {21, 8},  {149, 8}, {85, 8},  {213, 8}, {53, 8},  {181, 8},
      {117, 8}, {245, 8}, {13, 8},  {141, 8}, {77, 8},  {205, 8}, {45, 8},
      {173, 8}, {109, 8}, {237, 8}, {29, 8},  {157, 8}, {93, 8},  {221, 8},
      {61, 8},  {189, 8}, {125, 8}, {253, 8}, {19, 9},  {275, 9}, {147, 9},
      {403, 9}, {83, 9},  {339, 9}, {211, 9}, {467, 9}, {51, 9},  {307, 9},
      {179, 9}, {435, 9}, {115, 9}, {371, 9}, {243, 9}, {499, 9}, {11, 9},
      {267, 9}, {139, 9}, {395, 9}, {75, 9},  {331, 9}, {203, 9}, {459, 9},
      {43, 9},  {299, 9}, {171, 9}, {427, 9}, {107, 9}, {363, 9}, {235, 9},
      {491, 9}, {27, 9},  {283, 9}, {155, 9}, {411, 9}, {91, 9},  {347, 9},
      {219, 9}, {475, 9}, {59, 9},  {315, 9}, {187, 9}, {443, 9}, {123, 9},
      {379, 9}, {251, 9}, {507, 9}, {7, 9},   {263, 9}, {135, 9}, {391, 9},
      {71, 9},  {327, 9}, {199, 9}, {455, 9}, {39, 9},  {295, 9}, {167, 9},
      {423, 9}, {103, 9}, {359, 9}, {231, 9}, {487, 9}, {23, 9},  {279, 9},
      {151, 9}, {407, 9}, {87, 9},  {343, 9}, {215, 9}, {471, 9}, {55, 9},
      {311, 9}, {183, 9}, {439, 9}, {119, 9}, {375, 9}, {247, 9}, {503, 9},
      {15, 9},  {271, 9}, {143, 9}, {399, 9}, {79, 9},  {335, 9}, {207, 9},
      {463, 9}, {47, 9},  {303, 9}, {175, 9}, {431, 9}, {111, 9}, {367, 9},
      {239, 9}, {495, 9}, {31, 9},  {287, 9}, {159, 9}, {415, 9}, {95, 9},
      {351, 9}, {223, 9}, {479, 9}, {63, 9},  {319, 9}, {191, 9}, {447, 9},
      {127, 9}, {383, 9}, {255, 9}, {511, 9}, {0, 7},   {64, 7},  {32, 7},
      {96, 7},  {16, 7},  {80, 7},  {48, 7},  {112, 7}, {8, 7},   {72, 7},
      {40, 7},  {104, 7}, {24, 7},  {88, 7},  {56, 7},  {120, 7}, {4, 7},
      {68, 7},  {36, 7},  {100, 7}, {20, 7},  {84, 7},  {52, 7},  {116, 7},
      {3, 8},   {131, 8}, {67, 8},  {195, 8}, {35, 8},  {163, 8}, {99, 8},
      {227, 8},
  };
  switch (len) {
    case -3:
      bits = static_ltree[kEndBlock].code;
      break;
    case -2:
      bits = ch;
      break;
    case -1:
      bits = 0;
      break;
    case 0:
      bits = GetHuffLiteralBits(ch);
      break;
    default:
      bits = GetHuffRunBits(len, dist);
      break;
  }
  return bits;
}

// assembles up to kVecX2 unsigned char values based on given huffman encoding
// writes up to kMaxHuffcodeBits * kVecX2 bits to memory
bool HufEnc(char *len, short *dist, unsigned char *data, unsigned int *outdata,
            unsigned int *leftover, unsigned short *leftover_size) {
  // array that contains the bit position of each symbol
  unsigned short bitpos[kVec + 1];
  bitpos[0] = 0;

  Unroller<0, kVec>::step([&](int i) {
    bitpos[i + 1] = bitpos[i] + (IsValid(len[i], dist[i], data[i])
                                     ? GetHuffLen(len[i], dist[i], data[i])
                                     : 0);
  });

  // leftover is an array that carries huffman encoded data not yet written to
  // memory adjust leftover_size with the number of bits to write this time
  unsigned short prev_cycle_offset = *leftover_size;
  *leftover_size += (bitpos[kVec] & 0x3fff);

  // we'll write this cycle if we have collected enough data (kVec shorts or
  // more)
  bool write = *leftover_size & (kVec * (kMaxHuffcodeBits * 2));

  // subtract kVec shorts from leftover size (if it's bigger
  // than kVec) because we'll write those out this cycle
  *leftover_size &= ~(kVec * (kMaxHuffcodeBits * 2));

  // Adjust bitpos based on leftover offset from previous cycle
  Unroller<0, kVec>::step(
      [&](int i) { bitpos[i] += (prev_cycle_offset & 0x3fff); });

  // Huffman codes have any bit alignement, so they can spill
  // onto two shorts in the output array
  // use ushort2 to keep each part of the code separate
  // Iterate over all codes and construct ushort2 containing
  // the code properly aligned
  struct Uint2Gzip code[kVec];
  Unroller<0, kVec>::step([&](int i) {
    code[i].x = 0;
    code[i].y = 0;
  });

  Unroller<0, kVec>::step([&](int i) {
    // Codes can be more than 16 bits, so use uint32
    unsigned int curr_code = GetHuffBits(len[i], dist[i], data[i]);
    unsigned char bitpos_in_short = bitpos[i] & 0x01F;

    unsigned long long temp = (unsigned long long)curr_code << bitpos_in_short;
    unsigned int temp1 = (unsigned int)temp;
    unsigned int temp2 = temp >> 32ULL;

    if (IsValid(len[i], dist[i], data[i])) {
      code[i].x = temp1;
      code[i].y = temp2;
    } else {
      code[i].x = temp1;
      code[i].y = temp2;
    }
  });

  // Iterate over all destination locations and gather the required data
  unsigned int new_leftover[kVec];
  Unroller<0, kVec>::step([&](int i) {
    new_leftover[i] = 0;
    outdata[i] = 0;

    Unroller<0, kVec>::step([&](int j) {
      // figure out whether code[j] goes into bucket[i]
      bool match_first = ((bitpos[j] >> 5) & (kVec - 1)) == i;
      bool match_second =
          ((bitpos[j] >> 5) & (kVec - 1)) == ((i - 1) & (kVec - 1));

      // if code[j] maps onto current bucket then OR its code, else OR with 0
      unsigned int component =
          match_first ? code[j].x : (match_second ? code[j].y : 0);

      // overflow from kVec shorts, need to move onto new_leftover
      bool use_later =
          (bitpos[j] & (kVec * (kMaxHuffcodeBits * 2))) ||
          (match_second && (((bitpos[j] >> 5) & (kVec - 1)) == kVec - 1));

      // write to output
      outdata[i] |= use_later ? 0 : component;
      new_leftover[i] |= use_later ? component : 0;
    });
  });

  // Apply previous leftover on the outdata
  // Also, if didn't write, apply prev leftover onto newleftover
  Unroller<0, kVec>::step([&](int i) {
    outdata[i] |= leftover[i];
    leftover[i] = outdata[i];
  });

  // HACK: split unroll into two unrolls to avoid compiler crash
  if (write) {
    Unroller<0, kVec>::step([&](int i) { leftover[i] = new_leftover[i]; });
  }

  return write;
}

// Helper, for accessing the parameter pack
template <int target, typename CurrentAccessor, typename... AccessorTys>
auto get(CurrentAccessor &accessor, AccessorTys &... Args) {
  if constexpr (target == 0)
    return accessor;
  else
    return get<target - 1>(Args...);
}

template <int engineID>
class CRC;
template <int engineID, int BatchSize>
event SubmitCRC(queue &q, size_t block_size, uint32_t *result_crc,
                std::vector<event> &depend_on) {
  event e = q.submit([&](handler &h) {
    if (!depend_on.empty()) {
      h.depends_on(depend_on[kCRCIndex]);
    }

    h.single_task<CRC<engineID>>([=]() [[intel::kernel_args_restrict]] {
      auto accessor_isz = block_size;

      host_ptr<uint32_t> accresult_crc(result_crc);

      // See comments at top of file, regarding batching.
      [[intel::disable_loop_pipelining]]
      for (int iter=0;iter<BatchSize;iter++) {
        const unsigned int table64[64][16] = {
            {
                0x0,
                0xf1da05aa,
                0x38c50d15,
                0xc91f08bf,
                0x718a1a2a,
                0x80501f80,
                0x494f173f,
                0xb8951295,
                0xe3143454,
                0x12ce31fe,
                0xdbd13941,
                0x2a0b3ceb,
                0x929e2e7e,
                0x63442bd4,
                0xaa5b236b,
                0x5b8126c1,
            },

            {
                0x0,
                0x1d596ee9,
                0x3ab2ddd2,
                0x27ebb33b,
                0x7565bba4,
                0x683cd54d,
                0x4fd76676,
                0x528e089f,
                0xeacb7748,
                0xf79219a1,
                0xd079aa9a,
                0xcd20c473,
                0x9faeccec,
                0x82f7a205,
                0xa51c113e,
                0xb8457fd7,
            },

            {
                0x0,
                0xee7e8d1,
                0x1dcfd1a2,
                0x13283973,
                0x3b9fa344,
                0x35784b95,
                0x265072e6,
                0x28b79a37,
                0x773f4688,
                0x79d8ae59,
                0x6af0972a,
                0x64177ffb,
                0x4ca0e5cc,
                0x42470d1d,
                0x516f346e,
                0x5f88dcbf,
            },

            {
                0x0,
                0xee7e8d10,
                0x78c1c61,
                0xe9f29171,
                0xf1838c2,
                0xe166b5d2,
                0x89424a3,
                0xe6eaa9b3,
                0x1e307184,
                0xf04efc94,
                0x19bc6de5,
                0xf7c2e0f5,
                0x11284946,
                0xff56c456,
                0x16a45527,
                0xf8dad837,
            },

            {
                0x0,
                0x3c60e308,
                0x78c1c610,
                0x44a12518,
                0xf1838c20,
                0xcde36f28,
                0x89424a30,
                0xb522a938,
                0x38761e01,
                0x416fd09,
                0x40b7d811,
                0x7cd73b19,
                0xc9f59221,
                0xf5957129,
                0xb1345431,
                0x8d54b739,
            },

            {
                0x0,
                0x70ec3c02,
                0xe1d87804,
                0x91344406,
                0x18c1f649,
                0x682dca4b,
                0xf9198e4d,
                0x89f5b24f,
                0x3183ec92,
                0x416fd090,
                0xd05b9496,
                0xa0b7a894,
                0x29421adb,
                0x59ae26d9,
                0xc89a62df,
                0xb8765edd,
            },

            {
                0x0,
                0x6307d924,
                0xc60fb248,
                0xa5086b6c,
                0x576e62d1,
                0x3469bbf5,
                0x9161d099,
                0xf26609bd,
                0xaedcc5a2,
                0xcddb1c86,
                0x68d377ea,
                0xbd4aece,
                0xf9b2a773,
                0x9ab57e57,
                0x3fbd153b,
                0x5cbacc1f,
            },

            {
                0x0,
                0x86c88d05,
                0xd6e01c4b,
                0x5028914e,
                0x76b13ed7,
                0xf079b3d2,
                0xa051229c,
                0x2699af99,
                0xed627dae,
                0x6baaf0ab,
                0x3b8261e5,
                0xbd4aece0,
                0x9bd34379,
                0x1d1bce7c,
                0x4d335f32,
                0xcbfbd237,
            },

            {
                0x0,
                0x1b5fd1d,
                0x36bfa3a,
                0x2de0727,
                0x6d7f474,
                0x7620969,
                0x5bc0e4e,
                0x409f353,
                0xdafe8e8,
                0xc1a15f5,
                0xec412d2,
                0xf71efcf,
                0xb781c9c,
                0xacde181,
                0x813e6a6,
                0x9a61bbb,
            },

            {
                0x0,
                0x1b5fd1d0,
                0x36bfa3a0,
                0x2de07270,
                0x6d7f4740,
                0x76209690,
                0x5bc0e4e0,
                0x409f3530,
                0xdafe8e80,
                0xc1a15f50,
                0xec412d20,
                0xf71efcf0,
                0xb781c9c0,
                0xacde1810,
                0x813e6a60,
                0x9a61bbb0,
            },

            {
                0x0,
                0x6e8c1b41,
                0xdd183682,
                0xb3942dc3,
                0x61416b45,
                0xfcd7004,
                0xbc595dc7,
                0xd2d54686,
                0xc282d68a,
                0xac0ecdcb,
                0x1f9ae008,
                0x7116fb49,
                0xa3c3bdcf,
                0xcd4fa68e,
                0x7edb8b4d,
                0x1057900c,
            },

            {
                0x0,
                0x5e74ab55,
                0xbce956aa,
                0xe29dfdff,
                0xa2a3ab15,
                0xfcd70040,
                0x1e4afdbf,
                0x403e56ea,
                0x9e36506b,
                0xc042fb3e,
                0x22df06c1,
                0x7cabad94,
                0x3c95fb7e,
                0x62e1502b,
                0x807cadd4,
                0xde080681,
            },

            {
                0x0,
                0xe71da697,
                0x154a4b6f,
                0xf257edf8,
                0x2a9496de,
                0xcd893049,
                0x3fdeddb1,
                0xd8c37b26,
                0x55292dbc,
                0xb2348b2b,
                0x406366d3,
                0xa77ec044,
                0x7fbdbb62,
                0x98a01df5,
                0x6af7f00d,
                0x8dea569a,
            },

            {
                0x0,
                0xaa525b78,
                0x8fd5b0b1,
                0x2587ebc9,
                0xc4da6723,
                0x6e883c5b,
                0x4b0fd792,
                0xe15d8cea,
                0x52c5c807,
                0xf897937f,
                0xdd1078b6,
                0x774223ce,
                0x961faf24,
                0x3c4df45c,
                0x19ca1f95,
                0xb39844ed,
            },

            {
                0x0,
                0xa58b900e,
                0x9066265d,
                0x35edb653,
                0xfbbd4afb,
                0x5e36daf5,
                0x6bdb6ca6,
                0xce50fca8,
                0x2c0b93b7,
                0x898003b9,
                0xbc6db5ea,
                0x19e625e4,
                0xd7b6d94c,
                0x723d4942,
                0x47d0ff11,
                0xe25b6f1f,
            },

            {
                0x0,
                0x5817276e,
                0xb02e4edc,
                0xe83969b2,
                0xbb2d9bf9,
                0xe33abc97,
                0xb03d525,
                0x5314f24b,
                0xad2a31b3,
                0xf53d16dd,
                0x1d047f6f,
                0x45135801,
                0x1607aa4a,
                0x4e108d24,
                0xa629e496,
                0xfe3ec3f8,
            },

            {
                0x0,
                0x81256527,
                0xd93bcc0f,
                0x581ea928,
                0x69069e5f,
                0xe823fb78,
                0xb03d5250,
                0x31183777,
                0xd20d3cbe,
                0x53285999,
                0xb36f0b1,
                0x8a139596,
                0xbb0ba2e1,
                0x3a2ec7c6,
                0x62306eee,
                0xe3150bc9,
            },

            {
                0x0,
                0x7f6b7f3d,
                0xfed6fe7a,
                0x81bd8147,
                0x26dcfab5,
                0x59b78588,
                0xd80a04cf,
                0xa7617bf2,
                0x4db9f56a,
                0x32d28a57,
                0xb36f0b10,
                0xcc04742d,
                0x6b650fdf,
                0x140e70e2,
                0x95b3f1a5,
                0xead88e98,
            },

            {
                0x0,
                0x9b73ead4,
                0xed96d3e9,
                0x76e5393d,
                0x5ca193,
                0x9b2f4b47,
                0xedca727a,
                0x76b998ae,
                0xb94326,
                0x9bcaa9f2,
                0xed2f90cf,
                0x765c7a1b,
                0xe5e2b5,
                0x9b960861,
                0xed73315c,
                0x7600db88,
            },

            {
                0x0,
                0x172864c,
                0x2e50c98,
                0x3978ad4,
                0x5ca1930,
                0x4b89f7c,
                0x72f15a8,
                0x65d93e4,
                0xb943260,
                0xae6b42c,
                0x9713ef8,
                0x803b8b4,
                0xe5e2b50,
                0xf2cad1c,
                0xcbb27c8,
                0xdc9a184,
            },

            {
                0x0,
                0x172864c0,
                0x2e50c980,
                0x3978ad40,
                0x5ca19300,
                0x4b89f7c0,
                0x72f15a80,
                0x65d93e40,
                0xb9432600,
                0xae6b42c0,
                0x9713ef80,
                0x803b8b40,
                0xe5e2b500,
                0xf2cad1c0,
                0xcbb27c80,
                0xdc9a1840,
            },

            {
                0x0,
                0xa9f74a41,
                0x889f92c3,
                0x2168d882,
                0xca4e23c7,
                0x63b96986,
                0x42d1b104,
                0xeb26fb45,
                0x4fed41cf,
                0xe61a0b8e,
                0xc772d30c,
                0x6e85994d,
                0x85a36208,
                0x2c542849,
                0xd3cf0cb,
                0xa4cbba8a,
            },

            {
                0x0,
                0x9fda839e,
                0xe4c4017d,
                0x7b1e82e3,
                0x12f904bb,
                0x8d238725,
                0xf63d05c6,
                0x69e78658,
                0x25f20976,
                0xba288ae8,
                0xc136080b,
                0x5eec8b95,
                0x370b0dcd,
                0xa8d18e53,
                0xd3cf0cb0,
                0x4c158f2e,
            },

            {
                0x0,
                0x4be412ec,
                0x97c825d8,
                0xdc2c3734,
                0xf4e14df1,
                0xbf055f1d,
                0x63296829,
                0x28cd7ac5,
                0x32b39da3,
                0x79578f4f,
                0xa57bb87b,
                0xee9faa97,
                0xc652d052,
                0x8db6c2be,
                0x519af58a,
                0x1a7ee766,
            },

            {
                0x0,
                0x65673b46,
                0xcace768c,
                0xafa94dca,
                0x4eedeb59,
                0x2b8ad01f,
                0x84239dd5,
                0xe144a693,
                0x9ddbd6b2,
                0xf8bcedf4,
                0x5715a03e,
                0x32729b78,
                0xd3363deb,
                0xb65106ad,
                0x19f84b67,
                0x7c9f7021,
            },

            {
                0x0,
                0xe0c6ab25,
                0x1afc500b,
                0xfa3afb2e,
                0x35f8a016,
                0xd53e0b33,
                0x2f04f01d,
                0xcfc25b38,
                0x6bf1402c,
                0x8b37eb09,
                0x710d1027,
                0x91cbbb02,
                0x5e09e03a,
                0xbecf4b1f,
                0x44f5b031,
                0xa4331b14,
            },

            {
                0x0,
                0xd7e28058,
                0x74b406f1,
                0xa35686a9,
                0xe9680de2,
                0x3e8a8dba,
                0x9ddc0b13,
                0x4a3e8b4b,
                0x9a11d85,
                0xde439ddd,
                0x7d151b74,
                0xaaf79b2c,
                0xe0c91067,
                0x372b903f,
                0x947d1696,
                0x439f96ce,
            },

            {
                0x0,
                0x13423b0a,
                0x26847614,
                0x35c64d1e,
                0x4d08ec28,
                0x5e4ad722,
                0x6b8c9a3c,
                0x78cea136,
                0x9a11d850,
                0x8953e35a,
                0xbc95ae44,
                0xafd7954e,
                0xd7193478,
                0xc45b0f72,
                0xf19d426c,
                0xe2df7966,
            },

            {
                0x0,
                0xef52b6e1,
                0x5d46b83,
                0xea86dd62,
                0xba8d706,
                0xe4fa61e7,
                0xe7cbc85,
                0xe12e0a64,
                0x1751ae0c,
                0xf80318ed,
                0x1285c58f,
                0xfdd7736e,
                0x1cf9790a,
                0xf3abcfeb,
                0x192d1289,
                0xf67fa468,
            },

            {
                0x0,
                0x2ea35c18,
                0x5d46b830,
                0x73e5e428,
                0xba8d7060,
                0x942e2c78,
                0xe7cbc850,
                0xc9689448,
                0xae6be681,
                0x80c8ba99,
                0xf32d5eb1,
                0xdd8e02a9,
                0x14e696e1,
                0x3a45caf9,
                0x49a02ed1,
                0x670372c9,
            },

            {
                0x0,
                0x87a6cb43,
                0xd43c90c7,
                0x539a5b84,
                0x730827cf,
                0xf4aeec8c,
                0xa734b708,
                0x20927c4b,
                0xe6104f9e,
                0x61b684dd,
                0x322cdf59,
                0xb58a141a,
                0x95186851,
                0x12bea312,
                0x4124f896,
                0xc68233d5,
            },

            {
                0x0,
                0x1751997d,
                0x2ea332fa,
                0x39f2ab87,
                0x5d4665f4,
                0x4a17fc89,
                0x73e5570e,
                0x64b4ce73,
                0xba8ccbe8,
                0xaddd5295,
                0x942ff912,
                0x837e606f,
                0xe7caae1c,
                0xf09b3761,
                0xc9699ce6,
                0xde38059b,
            },

            {
                0x0,
                0xae689191,
                0x87a02563,
                0x29c8b4f2,
                0xd4314c87,
                0x7a59dd16,
                0x539169e4,
                0xfdf9f875,
                0x73139f4f,
                0xdd7b0ede,
                0xf4b3ba2c,
                0x5adb2bbd,
                0xa722d3c8,
                0x94a4259,
                0x2082f6ab,
                0x8eea673a,
            },

            {
                0x0,
                0xe6273e9e,
                0x173f7b7d,
                0xf11845e3,
                0x2e7ef6fa,
                0xc859c864,
                0x39418d87,
                0xdf66b319,
                0x5cfdedf4,
                0xbadad36a,
                0x4bc29689,
                0xade5a817,
                0x72831b0e,
                0x94a42590,
                0x65bc6073,
                0x839b5eed,
            },

            {
                0x0,
                0xb9fbdbe8,
                0xa886b191,
                0x117d6a79,
                0x8a7c6563,
                0x3387be8b,
                0x22fad4f2,
                0x9b010f1a,
                0xcf89cc87,
                0x7672176f,
                0x670f7d16,
                0xdef4a6fe,
                0x45f5a9e4,
                0xfc0e720c,
                0xed731875,
                0x5488c39d,
            },

            {
                0x0,
                0x44629f4f,
                0x88c53e9e,
                0xcca7a1d1,
                0xcafb7b7d,
                0x8e99e432,
                0x423e45e3,
                0x65cdaac,
                0x4e87f0bb,
                0xae56ff4,
                0xc642ce25,
                0x8220516a,
                0x847c8bc6,
                0xc01e1489,
                0xcb9b558,
                0x48db2a17,
            },

            {
                0x0,
                0x9d0fe176,
                0xe16ec4ad,
                0x7c6125db,
                0x19ac8f1b,
                0x84a36e6d,
                0xf8c24bb6,
                0x65cdaac0,
                0x33591e36,
                0xae56ff40,
                0xd237da9b,
                0x4f383bed,
                0x2af5912d,
                0xb7fa705b,
                0xcb9b5580,
                0x5694b4f6,
            },

            {
                0x0,
                0x66b23c6c,
                0xcd6478d8,
                0xabd644b4,
                0x41b9f7f1,
                0x270bcb9d,
                0x8cdd8f29,
                0xea6fb345,
                0x8373efe2,
                0xe5c1d38e,
                0x4e17973a,
                0x28a5ab56,
                0xc2ca1813,
                0xa478247f,
                0xfae60cb,
                0x691c5ca7,
            },

            {
                0x0,
                0xdd96d985,
                0x605cb54b,
                0xbdca6cce,
                0xc0b96a96,
                0x1d2fb313,
                0xa0e5dfdd,
                0x7d730658,
                0x5a03d36d,
                0x87950ae8,
                0x3a5f6626,
                0xe7c9bfa3,
                0x9abab9fb,
                0x472c607e,
                0xfae60cb0,
                0x2770d535,
            },

            {
                0x0,
                0xb407a6da,
                0xb37e4bf5,
                0x779ed2f,
                0xbd8d91ab,
                0x98a3771,
                0xef3da5e,
                0xbaf47c84,
                0xa06a2517,
                0x146d83cd,
                0x13146ee2,
                0xa713c838,
                0x1de7b4bc,
                0xa9e01266,
                0xae99ff49,
                0x1a9e5993,
            },

            {
                0x0,
                0x9ba54c6f,
                0xec3b9e9f,
                0x779ed2f0,
                0x3063b7f,
                0x98a37710,
                0xef3da5e0,
                0x7498e98f,
                0x60c76fe,
                0x9da93a91,
                0xea37e861,
                0x7192a40e,
                0x50a4d81,
                0x9eaf01ee,
                0xe931d31e,
                0x72949f71,
            },

            {
                0x0,
                0xc18edfc,
                0x1831dbf8,
                0x14293604,
                0x3063b7f0,
                0x3c7b5a0c,
                0x28526c08,
                0x244a81f4,
                0x60c76fe0,
                0x6cdf821c,
                0x78f6b418,
                0x74ee59e4,
                0x50a4d810,
                0x5cbc35ec,
                0x489503e8,
                0x448dee14,
            },

            {
                0x0,
                0xc18edfc0,
                0x586cb9c1,
                0x99e26601,
                0xb0d97382,
                0x7157ac42,
                0xe8b5ca43,
                0x293b1583,
                0xbac3e145,
                0x7b4d3e85,
                0xe2af5884,
                0x23218744,
                0xa1a92c7,
                0xcb944d07,
                0x52762b06,
                0x93f8f4c6,
            },

            {
                0x0,
                0xaef6c4cb,
                0x869c8fd7,
                0x286a4b1c,
                0xd64819ef,
                0x78bedd24,
                0x50d49638,
                0xfe2252f3,
                0x77e1359f,
                0xd917f154,
                0xf17dba48,
                0x5f8b7e83,
                0xa1a92c70,
                0xf5fe8bb,
                0x2735a3a7,
                0x89c3676c,
            },

            {
                0x0,
                0xefc26b3e,
                0x4f5d03d,
                0xeb37bb03,
                0x9eba07a,
                0xe629cb44,
                0xd1e7047,
                0xe2dc1b79,
                0x13d740f4,
                0xfc152bca,
                0x172290c9,
                0xf8e0fbf7,
                0x1a3ce08e,
                0xf5fe8bb0,
                0x1ec930b3,
                0xf10b5b8d,
            },

            {
                0x0,
                0x27ae81e8,
                0x4f5d03d0,
                0x68f38238,
                0x9eba07a0,
                0xb9148648,
                0xd1e70470,
                0xf6498598,
                0xe6050901,
                0xc1ab88e9,
                0xa9580ad1,
                0x8ef68b39,
                0x78bf0ea1,
                0x5f118f49,
                0x37e20d71,
                0x104c8c99,
            },

            {
                0x0,
                0x177b1443,
                0x2ef62886,
                0x398d3cc5,
                0x5dec510c,
                0x4a97454f,
                0x731a798a,
                0x64616dc9,
                0xbbd8a218,
                0xaca3b65b,
                0x952e8a9e,
                0x82559edd,
                0xe634f314,
                0xf14fe757,
                0xc8c2db92,
                0xdfb9cfd1,
            },

            {
                0x0,
                0xacc04271,
                0x82f182a3,
                0x2e31c0d2,
                0xde920307,
                0x72524176,
                0x5c6381a4,
                0xf0a3c3d5,
                0x6655004f,
                0xca95423e,
                0xe4a482ec,
                0x4864c09d,
                0xb8c70348,
                0x14074139,
                0x3a3681eb,
                0x96f6c39a,
            },

            {
                0x0,
                0xccaa009e,
                0x4225077d,
                0x8e8f07e3,
                0x844a0efa,
                0x48e00e64,
                0xc66f0987,
                0xac50919,
                0xd3e51bb5,
                0x1f4f1b2b,
                0x91c01cc8,
                0x5d6a1c56,
                0x57af154f,
                0x9b0515d1,
                0x158a1232,
                0xd92012ac,
            },

            {
                0x0,
                0x7cbb312b,
                0xf9766256,
                0x85cd537d,
                0x299dc2ed,
                0x5526f3c6,
                0xd0eba0bb,
                0xac509190,
                0x533b85da,
                0x2f80b4f1,
                0xaa4de78c,
                0xd6f6d6a7,
                0x7aa64737,
                0x61d761c,
                0x83d02561,
                0xff6b144a,
            },

            {
                0x0,
                0xa6770bb4,
                0x979f1129,
                0x31e81a9d,
                0xf44f2413,
                0x52382fa7,
                0x63d0353a,
                0xc5a73e8e,
                0x33ef4e67,
                0x959845d3,
                0xa4705f4e,
                0x20754fa,
                0xc7a06a74,
                0x61d761c0,
                0x503f7b5d,
                0xf64870e9,
            },

            {
                0x0,
                0x67de9cce,
                0xcfbd399c,
                0xa863a552,
                0x440b7579,
                0x23d5e9b7,
                0x8bb64ce5,
                0xec68d02b,
                0x8816eaf2,
                0xefc8763c,
                0x47abd36e,
                0x20754fa0,
                0xcc1d9f8b,
                0xabc30345,
                0x3a0a617,
                0x647e3ad9,
            },

            {
                0x0,
                0xcb5cd3a5,
                0x4dc8a10b,
                0x869472ae,
                0x9b914216,
                0x50cd91b3,
                0xd659e31d,
                0x1d0530b8,
                0xec53826d,
                0x270f51c8,
                0xa19b2366,
                0x6ac7f0c3,
                0x77c2c07b,
                0xbc9e13de,
                0x3a0a6170,
                0xf156b2d5,
            },

            {
                0x0,
                0x3d6029b,
                0x7ac0536,
                0x47a07ad,
                0xf580a6c,
                0xc8e08f7,
                0x8f40f5a,
                0xb220dc1,
                0x1eb014d8,
                0x1d661643,
                0x191c11ee,
                0x1aca1375,
                0x11e81eb4,
                0x123e1c2f,
                0x16441b82,
                0x15921919,
            },

            {
                0x0,
                0x3d6029b0,
                0x7ac05360,
                0x47a07ad0,
                0xf580a6c0,
                0xc8e08f70,
                0x8f40f5a0,
                0xb220dc10,
                0x30704bc1,
                0xd106271,
                0x4ab018a1,
                0x77d03111,
                0xc5f0ed01,
                0xf890c4b1,
                0xbf30be61,
                0x825097d1,
            },

            {
                0x0,
                0x60e09782,
                0xc1c12f04,
                0xa121b886,
                0x58f35849,
                0x3813cfcb,
                0x9932774d,
                0xf9d2e0cf,
                0xb1e6b092,
                0xd1062710,
                0x70279f96,
                0x10c70814,
                0xe915e8db,
                0x89f57f59,
                0x28d4c7df,
                0x4834505d,
            },

            {
                0x0,
                0xb8bc6765,
                0xaa09c88b,
                0x12b5afee,
                0x8f629757,
                0x37def032,
                0x256b5fdc,
                0x9dd738b9,
                0xc5b428ef,
                0x7d084f8a,
                0x6fbde064,
                0xd7018701,
                0x4ad6bfb8,
                0xf26ad8dd,
                0xe0df7733,
                0x58631056,
            },

            {
                0x0,
                0x5019579f,
                0xa032af3e,
                0xf02bf8a1,
                0x9b14583d,
                0xcb0d0fa2,
                0x3b26f703,
                0x6b3fa09c,
                0xed59b63b,
                0xbd40e1a4,
                0x4d6b1905,
                0x1d724e9a,
                0x764dee06,
                0x2654b999,
                0xd67f4138,
                0x866616a7,
            },

            {
                0x0,
                0x1c26a37,
                0x384d46e,
                0x246be59,
                0x709a8dc,
                0x6cbc2eb,
                0x48d7cb2,
                0x54f1685,
                0xe1351b8,
                0xfd13b8f,
                0xd9785d6,
                0xc55efe1,
                0x91af964,
                0x8d89353,
                0xa9e2d0a,
                0xb5c473d,
            },

            {
                0x0,
                0x1c26a370,
                0x384d46e0,
                0x246be590,
                0x709a8dc0,
                0x6cbc2eb0,
                0x48d7cb20,
                0x54f16850,
                0xe1351b80,
                0xfd13b8f0,
                0xd9785d60,
                0xc55efe10,
                0x91af9640,
                0x8d893530,
                0xa9e2d0a0,
                0xb5c473d0,
            },

            {
                0x0,
                0x191b3141,
                0x32366282,
                0x2b2d53c3,
                0x646cc504,
                0x7d77f445,
                0x565aa786,
                0x4f4196c7,
                0xc8d98a08,
                0xd1c2bb49,
                0xfaefe88a,
                0xe3f4d9cb,
                0xacb54f0c,
                0xb5ae7e4d,
                0x9e832d8e,
                0x87981ccf,
            },

            {
                0x0,
                0x4ac21251,
                0x958424a2,
                0xdf4636f3,
                0xf0794f05,
                0xbabb5d54,
                0x65fd6ba7,
                0x2f3f79f6,
                0x3b83984b,
                0x71418a1a,
                0xae07bce9,
                0xe4c5aeb8,
                0xcbfad74e,
                0x8138c51f,
                0x5e7ef3ec,
                0x14bce1bd,
            },

            {
                0x0,
                0x77073096,
                0xee0e612c,
                0x990951ba,
                0x76dc419,
                0x706af48f,
                0xe963a535,
                0x9e6495a3,
                0xedb8832,
                0x79dcb8a4,
                0xe0d5e91e,
                0x97d2d988,
                0x9b64c2b,
                0x7eb17cbd,
                0xe7b82d07,
                0x90bf1d91,
            },

            {
                0x0,
                0x1db71064,
                0x3b6e20c8,
                0x26d930ac,
                0x76dc4190,
                0x6b6b51f4,
                0x4db26158,
                0x5005713c,
                0xedb88320,
                0xf00f9344,
                0xd6d6a3e8,
                0xcb61b38c,
                0x9b64c2b0,
                0x86d3d2d4,
                0xa00ae278,
                0xbdbdf21c,
            },
        };

        const int num_nibbles_parallel = 64;

        // this section of code should be on the hardware accelerator
        const int num_sections =
            accessor_isz /
            (num_nibbles_parallel / 2);  // how many loop iterations

        unsigned int result = ~0;

        char_arr_32 input_data;

        for (int i = 0; i < num_sections; i++) { // Iterate over 32 byte sections)
          unsigned int result_update_odd = 0;
          unsigned int result_update_even = 0;

          // The input file data is read by the LZ kernel and transferred here
          // via a pipe.
          input_data = acc_lz_to_crc_channel_array::PipeAt<engineID>::read();

          // which 4 bit chunk within the section -- this loop can be unrolled, the
          // total update for the crc is the xor of the updates from the nibbles
          #pragma unroll
          for (int nib = 0; nib < num_nibbles_parallel; nib++) { // Iterate through the 32-bytes in this section

            unsigned char this_input_nibble =
                input_data.arr[nib / 2] >> (4 * (nib % 2));

            unsigned char this_result_nibble =
                (nib < 8) ? (result >> (4 * nib)) : 0;
            unsigned char this_table_index =
                this_input_nibble ^ this_result_nibble;
            if (nib % 2) {
              result_update_odd ^= table64[nib][this_table_index & 0xf];
            } else {
              result_update_even ^= table64[nib][this_table_index & 0xf];
            }
          }
          result = result_update_odd ^ result_update_even;
        }

        // Read and discard final data
        input_data = acc_lz_to_crc_channel_array::PipeAt<engineID>::read();

        accresult_crc[iter] = ~result;
      }
    });
  });

  return e;
}

template <int engineID>
class LZReduction;
template <int engineID, int BatchSize, typename... PtrTypes>
event SubmitLZReduction(queue &q, size_t block_size, bool last_block,
                        std::vector<event> &depend_on,
                        PtrTypes... ptrs) {
  event e = q.submit([&](handler &h) {
    auto accessor_isz = block_size;

    if (!depend_on.empty()) {
      h.depends_on(depend_on[kLZReductionIndex]);
    }

    h.single_task<LZReduction<engineID>>([=]() [[intel::kernel_args_restrict]] {
      // Unpack the ptrs parameter pack and grab all of the pointers, annotating
      // them as USM host pointers.
      // To avoid calling the default constructors and having two stores to
      // 'host_pibuf' (and therefore forcing it to a memory), we can create
      // an initializer list by expanding our pack. It's the same logic as in
      // SubmitGzipTasksHelper(); everything to the left of '...' is expanded
      // for each value in ptrs.

      host_ptr<char> host_pibuf[BatchSize];
      Unroller<0, BatchSize>::step(
          [&](auto i) { host_pibuf[i] = host_ptr<char>(get<i>(ptrs...)); });

      // See comments at top of file, regarding batching
      [[intel::disable_loop_pipelining]] for (int iter = 0;
                                                  iter < BatchSize; iter++) {
        const int iter_masked =
            iter % BatchSize;  // Hint to the compiler that the access to
                               // host_pibuf is bounded.
        host_ptr<char> acc_pibuf =
            host_pibuf[iter_masked];  // Grab new host pointer on each iteration
                                      // of the batch loop

        //-------------------------------------
        //   Hash Table(s)
        //-------------------------------------

        [[intel::singlepump]] [[intel::numbanks(kVec)]] [
            [intel::max_replicates(kVec)]] struct {
          unsigned char s[kLen];
        } dictionary[kDepth][kVec];

        [[intel::singlepump]] [[intel::numbanks(kVec)]] [
            [intel::max_replicates(
                kVec)]] unsigned int dict_offset[kDepth][kVec];

        // Initialize history to empty.
        for (int i = 0; i < kDepth; i++) {
          Unroller<0, kVec>::step([&](int k) { dict_offset[i][k] = 0; });
        }

        // This is the window of data on which we look for matches
        // We fetch twice our data size because we have kVec offsets
        unsigned char current_window[kVecX2];

        // This is the window of data on which we look for matches
        // We fetch twice our data size because we have kVec offsets
        unsigned char compare_window[kLen][kVec][kVec];
        // kVec bytes per dict----------|    |   |
        // kVec dictionaries-----------------|   |
        // one for each curr win offset----------|

        // load offset into these arrays
        unsigned int compare_offset[kVec][kVec];
        // one per kVec bytes----------|     |
        // one for each compwin--------------|

        // Initialize input stream position
        unsigned int inpos_minus_vec_div_16 = 0;

        // this is ceiling of (insize-kVec)/16, original comparison was
        // inpos < insize, now inpos is carried as (inpos-kVec)/16 so this is
        // what we compare to
        unsigned int insize_compare = (accessor_isz) / kVec;

        int ctr = insize_compare - 1;

        char first_valid_pos = 0;

        struct DistLen dist_offs_data;

        size_t inpos = 0;

        char_arr_32 input_data; // Assumes kVec = 16 because CRC expects 2 x 16 bytes.
        bool crc_ch_load_upper = true;  // A flag used to form double-wide words to send to the CRC kernel.

        // load in new data
        struct LzInput in;
        Unroller<0, kVec>::step([&](int i) {
          in.data[i] = acc_pibuf[inpos++];  // Reads 16 bytes, just one time.
          input_data.arr[i] =
              in.data[i];  // Send a copy of the data to the CRC kernel, through
                           // a pipe. input_data is used to gang the data
                           // together into a wider word.
        });

        Unroller<0, kVec>::step(
            [&](int i) { current_window[i + kVec] = in.data[i]; });

        do {
          //-----------------------------
          // Prepare current window
          //-----------------------------

          // shift current window
          Unroller<0, kVec>::step(
              [&](int i) { current_window[i] = current_window[i + kVec]; });

          // load in new data
          Unroller<0, kVec>::step([&](int i) {
            in.data[i] = acc_pibuf[inpos++];
            input_data.arr[16 * (int)crc_ch_load_upper + i] = in.data[i];
          });

          // CRC kernel expects a wider word.
          if (crc_ch_load_upper) {  // After both halves are loaded, write the
                                    // full struct to the channel
            acc_lz_to_crc_channel_array::PipeAt<engineID>::write(input_data);
          }

          // The state of this signal indicates the next half to be loaded.
          // i.e. if true, upper will be loaded next.
          crc_ch_load_upper = !crc_ch_load_upper;

          Unroller<0, kVec>::step(
              [&](int i) { current_window[kVec + i] = in.data[i]; });

          //-----------------------------
          // Compute hash
          //-----------------------------

          unsigned short hash[kVec];

          Unroller<0, kVec>::step([&](int i) {
            hash[i] = (current_window[i] ^ (current_window[i + 1] << 6) ^
                       (current_window[i + 2] << 2) ^ current_window[i + 3]) &
                      kHashMask;
          });

          //-----------------------------
          // Dictionary look-up
          //-----------------------------

          // loop over kVec compare windows, each has a different hash
          Unroller<0, kVec>::step([&](int i) {
            // loop over all kVec bytes
            Unroller<0, kLen>::step([&](int j) {
              Unroller<0, kVec>::step([&](int k) {
                compare_window[k][j][i] = dictionary[hash[i]][j].s[k];
              });
            });
          });

          // loop over compare windows
          Unroller<0, kVec>::step([&](int i) {
            Unroller<0, kLen>::step([&](int j) {
              // loop over frames in this compare window
              // (they come from different dictionaries)
              compare_offset[j][i] = dict_offset[hash[i]][j];
            });
          });

          //-----------------------------
          // Dictionary update
          //-----------------------------

          // loop over different dictionaries to store different frames
          // store one frame per dictionary
          // loop over kVec bytes to store
          Unroller<0, kLen>::step([&](int i) {
            Unroller<0, kVec>::step([&](int j) {
              // store actual bytes
              dictionary[hash[i]][i].s[j] = current_window[i + j];
            });
          });

          Unroller<0, kVec>::step([&](int i) {
            // loop over kVec different dictionaries and write one word to each
            dict_offset[hash[i]][i] =
                (inpos_minus_vec_div_16 << 4) |
                i;  // inpos - kVec + 0, we know that inpos - kVec has 0 as the
                    // 4 lower bits so really just concatenate
          });

          //-----------------------------
          // Match search
          //-----------------------------

          // arrays to store length, best length etc..
          unsigned char length[kVec];
          bool done[kVec];
          char best_length[kVec];
          unsigned int best_offset[kVec];

          // initialize best_length
          Unroller<0, kVec>::step([&](int i) {
            best_length[i] = 0;
            best_offset[i] = 0;
          });

          // loop over each comparison window frame
          // one comes from each dictionary
          Unroller<0, kVec>::step([&](int i) {
            // initialize length and done
            Unroller<0, kVec>::step([&](int l) {
              length[l] = 0;
              done[l] = 0;
            });

            // loop over each current window
            Unroller<0, kVec>::step([&](int j) {
              // loop over each char in the current window
              // and corresponding char in comparison window
              Unroller<0, kLen>::step([&](int k) {
                bool comp = current_window[k + j] == compare_window[k][i][j] &&
                            !done[j];
                length[j] += comp;
                done[j] = !comp;
              });
            });

            // Check if this the best length
            Unroller<0, kVec>::step([&](int m) {
              bool update_best =
                  (length[m] > best_length[m]) && (compare_offset[i][m] != 0) &&
                  (((inpos_minus_vec_div_16 << kVecPow) | (i & (kVec - 1))) -
                       (compare_offset[i][m]) <
                   kMaxDistance);

              unsigned int new_offset =
                  (((inpos_minus_vec_div_16 << kVecPow) | (m & (kVec - 1))) &
                   0x7ffff) -
                  ((compare_offset[i][m] & 0x7ffff));

              // Reconsider if new_offset is bigger than current offset, might
              // take more bytes to encode
              update_best = update_best && (length[m] == best_length[m]) &&
                                    (new_offset > best_offset[m])
                                ? false
                                : update_best;

              best_offset[m] = (update_best ? new_offset : best_offset[m]) &
                               0x7ffff;  // 19 bits is sufficient

              best_length[m] = (update_best ? length[m] : best_length[m]) &
                               0x1f;  // 5 bits is sufficient
            });
          });

          //-----------------------------
          // Filter matches step 1
          //-----------------------------

          // remove matches with offsets that are <= 0: this means they're
          // self-matching or didn't match and keep only the matches that, when
          // encoded, take fewer bytes than the actual match length
          Unroller<0, kVec>::step([&](int i) {
            best_length[i] = (((best_length[i] & 0x1f) >= 3) &&
                                      ((best_offset[i]) < kMaxDistance)
                                  ? best_length[i]
                                  : 0) &
                             0x1f;  // 5 bits is sufficient

            // Second level filter - remove matches with len 3, greater than
            // kTooFar
            best_length[i] =
                (((best_length[i] & 0x1f) == 3) && ((best_offset[i]) > kTooFar)
                     ? 0
                     : best_length[i]) &
                0x1f;  // 5 bits is sufficient
                       // don't emmit matches for last iteration as some of the
                       // second part of the window might be undefined
            if (ctr == 0) best_length[i] = 0;
          });

          //-----------------------------
          // Assign first_valid_pos
          //-----------------------------

          // first_valid_pos is loop-carried, and tricky to compute.  So first
          // compute it speculatively in parallel for every possible value of
          // the previous first_valid_pos.
          char first_valid_pos_speculative[kVec];

          Unroller<0, kVec>::step([&](int guess) {
            unsigned char next_match_search = guess;
            Unroller<0, kVec>::step([&](int i) {
              unsigned int len = best_length[i];

              // Skip to the next match
              next_match_search = i >= next_match_search && len > 0
                                      ? i + len
                                      : next_match_search;
            });

            first_valid_pos_speculative[guess] =
                next_match_search - kVec > 0 ? next_match_search - kVec : 0;
          });

          // For kVec=16 (the largest currently supported), this should be a
          // 16:1 mux, which is 2 6LUTs deep.  For larger kVec, it will be
          // worse.
          unsigned char current_valid_pos = first_valid_pos;
          first_valid_pos =
              first_valid_pos_speculative[first_valid_pos & (kVec - 1)] &
              (kVec -
               1);  // first_valid_pos only needs 4 bits, make this explicit

          // greedy match selection
          Unroller<0, (kVec)>::step([&](int i) {
            unsigned int len = best_length[i];
            best_length[i] = i < current_valid_pos ? -1 : best_length[i];
            // Skip to the next match
            current_valid_pos =
                i >= current_valid_pos && len > 0 ? i + len : current_valid_pos;
          });

          //-----------------------------
          // Setup LZ dist/len pairs to push to Huffman encode kernel
          //-----------------------------

          Unroller<0, kVec>::step([&](int i) {
            dist_offs_data.data[i] = 0;
            dist_offs_data.len[i] = -1;
            dist_offs_data.dist[i] = -1;
            if (best_length[i] >= 0) {
              dist_offs_data.data[i] = current_window[i];
              dist_offs_data.len[i] = best_length[i];
              dist_offs_data.dist[i] = best_offset[i];
            }
          });

          // acc_dist_channel::write(dist_offs_data);
          acc_dist_channel_array::PipeAt<engineID>::write(dist_offs_data);

          // increment input position
          inpos_minus_vec_div_16++;
          ctr--;

        } while (ctr >= 0);

        // If crc_ch_load_upper==true, then upper was to be loaded next, meaning
        // lower has been loaded. So write out this partial struct.
        if (crc_ch_load_upper) {
          acc_lz_to_crc_channel_array::PipeAt<engineID>::write(input_data);
        }

        const char lasti = accessor_isz - (accessor_isz & ~(kVec - 1));
        const char firstpos = first_valid_pos;
        Unroller<0, kVec>::step([&](unsigned char i) {
          dist_offs_data.data[i] = 0;
          dist_offs_data.len[i] = -1;
          dist_offs_data.dist[i] = -1;
        });

        Unroller<0, kVec>::step([&](unsigned char i) {
          bool pred =
              ((i - firstpos) < (lasti - firstpos)) && ((i - firstpos) >= 0);
          dist_offs_data.data[i] = pred ? current_window[i + kVec] : 0;
          dist_offs_data.len[i] = pred ? 0 : -1;
        });

        acc_dist_channel_last_array::PipeAt<engineID>::write(dist_offs_data);
      }
    });
  });

  return e;
}

template <int engineID>
class StaticHuffman;
template <int engineID, int BatchSize, typename... PtrTypes>
event SubmitStaticHuffman(queue &q, size_t block_size,
                          struct GzipOutInfo *gzip_out_buf, bool last_block,
                          std::vector<event> &depend_on,
                          PtrTypes... ptrs) {
  event e = q.submit([&](handler &h) {
    if (!depend_on.empty()) {
      h.depends_on(depend_on[kStaticHuffmanIndex]);
    }

    h.single_task<StaticHuffman<engineID>>([=]() [[intel::kernel_args_restrict]] {

      // See comments in SubmitLZReduction, where the same parameter unpacking
      // is done.
      host_ptr<char> host_pobuf[BatchSize];
      Unroller<0, BatchSize>::step(
          [&](auto i) { host_pobuf[i] = host_ptr<char>(get<i>(ptrs...)); });

      auto accessor_isz = block_size;

      host_ptr<GzipOutInfo> acc_gzip_out(gzip_out_buf);

      auto acc_eof = last_block ? 1 : 0;

      // See comments at top of file regarding batching.
      [[intel::disable_loop_pipelining]]
      for (int iter=0; iter < BatchSize; iter++) {
        host_ptr<char> accessor_output = host_pobuf[iter % BatchSize];

        unsigned int leftover[kVec] = {0};
        Unroller<0, kVec>::step([&](int i) { leftover[i] = 0; });

        unsigned short leftover_size = 0;

        unsigned int outpos_huffman = 0;

        int ctr = ((accessor_isz) / kVec) + 2;
        int odx = 0;

        // Add the gzip start block marker. Assumes static huffman trees.
        leftover_size = 3;
        leftover[0] = ((kStaticTrees << 1) + (acc_eof));

        do {
          struct DistLen in;
          // init the input structure for the gzip end block marker.
          // this is the very last data block to be encoded and written.
          Unroller<0, kVec>::step([&](int i) {
            in.len[i] = -1;
            in.dist[i] = -1;
            in.data[i] = 0;
          });
          in.len[0] = ctr == 1 ? -3 : -1;
          in.data[0] = 0;

          in =
              ctr > 2
                  ? acc_dist_channel_array::PipeAt<engineID>::read()
                  : (ctr == 2
                         ? acc_dist_channel_last_array::PipeAt<engineID>::read()
                         : in);

          struct HuffmanOutput outdata;
          outdata.write = HufEnc(in.len, in.dist, in.data, outdata.data,
                                 leftover, &leftover_size);

          // prevent out of bounds write
          if (((ctr == 0) || outdata.write) && (odx < accessor_isz)) {
            Unroller<0, kVec * sizeof(unsigned int)>::step([&](int i) {
              accessor_output[odx + i] =
                  (ctr == 0) ? (unsigned char)(leftover[(i >> 2) & 0xf] >>
                                               ((i & 3) << 3))
                             : (unsigned char)(outdata.data[(i >> 2) & 0xf] >>
                                               ((i & 3) << 3));
            });
          }

          outpos_huffman = outdata.write ? outpos_huffman + 1 : outpos_huffman;
          odx += outdata.write ? (sizeof(unsigned int) << kVecPow) : 0;

        } while (ctr--);

        // Store summary values from lz and huffman
        acc_gzip_out[iter].compression_sz =
            (outpos_huffman * sizeof(unsigned int) * kVec) +
            (leftover_size + 7) / 8;
      }
    });
  });

  return e;
}

// Helper function to launch the individual kernels that comprise the gzip
// engine. Templated on engineID to allow creation of multiple engines.
// Templated on BatchSize to specify, at compile time, the batch size for which
// hardware should be built.
// And templated on a pack of PtrTypes (which we know will be char*).
template <int engineID, int BatchSize, std::size_t... Indices>
std::vector<event> SubmitGzipTasksHelper(queue &q, size_t block_size,
                                         struct GzipOutInfo *gzip_out_buf,
                                         uint32_t *result_crc, bool last_block,
                                         std::vector<event> &depend_on,
                                         std::array<char *, BatchSize> in_ptrs,
                                         std::array<char *, BatchSize> out_ptrs,
                                         std::index_sequence<Indices...>) {
  // A parameter pack is used for passing a batch of pointers (i.e. pointers to
  // the input/output buffers in host-memory).

  // submit the LZReductionKernel
  // The '...' operator essentially says this: Take the pattern connected
  // to the '...' (in this case, 'in_ptrs[Indices]') and replicate it
  // for each value of the pack (Indices).
  // This means the call quite literally expands to:
  //    SubmitLZReduction<BatchSize>(<other args>, in_ptrs[0], in_ptrs[1], ...);
  event e_LZReduction = SubmitLZReduction<engineID,BatchSize>(q,
                                                     block_size,
                                                     last_block,
                                                     depend_on,
                                                     in_ptrs[Indices]...
                                                     );

  event e_CRC = SubmitCRC<engineID,BatchSize>(q,
                                    block_size,
                                    result_crc,
                                    depend_on);

  
  event e_StaticHuffman = SubmitStaticHuffman<engineID,BatchSize>(q,
                                                         block_size,
                                                         gzip_out_buf,
                                                         last_block,
                                                         depend_on,
                                                         out_ptrs[Indices]...
                                                         );

  return {e_CRC, e_LZReduction, e_StaticHuffman};
}

//template <int BatchSize>
std::vector<event> SubmitGzipTasks(queue &q, size_t block_size,
                                   struct GzipOutInfo *gzip_out_buf,
                                   uint32_t *result_crc, bool last_block,
                                   std::vector<event> depend_on,
                                   std::array<char *, BATCH_SIZE> in_ptrs,
                                   std::array<char *, BATCH_SIZE> out_ptrs,
                                   size_t engineID) {
  // A parameter pack is used for passing a batch of pointers (i.e. pointers to
  // the input/output buffers in host-memory).

  // This call to the SubmitGzipTasksHelper function creates the integer
  // sequence that we will use to access the input and output pointers.
  // This function expands to, quite literally, the following (assuming):
  //    SubmitGzipTasksHelper<BatchSize>(<other_args>, in_ptrs, out_ptrs,
  //        0, 1, 2, 3, 4, ..., BatchSize-1);

  // Statically declare the engines so that the hardware is created for them.
  // But at run time, the host can dynamically select which engine(s) to use via
  // engineID.

  if (engineID == 0) {
    return SubmitGzipTasksHelper<0, BATCH_SIZE>(
        q, block_size, gzip_out_buf, result_crc, last_block, depend_on, in_ptrs,
        out_ptrs, std::make_index_sequence<BATCH_SIZE>{});
  }
#if NUM_ENGINES > 1
  if (engineID == 1) {
    return SubmitGzipTasksHelper<1, BATCH_SIZE>(
        q, block_size, gzip_out_buf, result_crc, last_block, depend_on, in_ptrs,
        out_ptrs, std::make_index_sequence<BATCH_SIZE>{});
  }
#endif

  // Default
  return SubmitGzipTasksHelper<0, BATCH_SIZE>(
      q, block_size, gzip_out_buf, result_crc, last_block, depend_on, in_ptrs,
      out_ptrs, std::make_index_sequence<BATCH_SIZE>{});
}

