// Tool to insert a specific CRC into a text file.

#include<stdio.h>
#include<string.h>

#include<cinttypes>
#include<cstdint>
#include<array>
#include<string>

namespace {

// Replace this text with CRC.
static const char kCrcKey[] = "XXXXXXXX";

// Replace this text with adjustment string.
static const char kAdjustKey[] = "XXXXX";

// Table for updating CRC one byte at a time.
static std::array<uint32_t, 256> crc_table;

// Mapping from upper 8 bits of a CRC to an index in crc_table,
// such that (crc_table[prefix_table[byte]] >> 24) == byte.
static std::array<int, 256> prefix_table;

// Load file to memory.
static std::string LoadInput(const char *name)
{
   std::string data;
   FILE *infile = fopen(name, "rb");

   if( infile == nullptr )
   {
      fprintf(stderr, "%s: read error\n", name);
      return data;
   }

   for(std::array<char, 4096> buffer;;)
   {
      const size_t read_size = fread(buffer.data(), 1, buffer.size(), infile);
      if( read_size == 0 )
         break;
      data.append(buffer.data(), read_size);
      if( read_size < buffer.size() )
         break;
   }
   fclose(infile);

   return data;
}

// Insert target CRC into string, returns true on success.
static bool InsertCrc(std::string *text, uint32_t target_crc)
{
   const size_t offset = text->find(kCrcKey);
   if( offset == std::string::npos )
      return false;

   std::array<char, 9> buffer;
   sprintf(buffer.data(), "%08x", target_crc);
   for(int i = 0; i < 8; i++)
      (*text)[offset + i] = buffer[i];
   return true;
}

// Initialize crc_table and prefix_table.
static void InitCrcTables()
{
   static constexpr uint32_t kPoly = 0xedb88320U;
   for(int i = 0; i < 256; i++)
   {
      uint32_t crc = i;
      for(int j = 8; j > 0; j--)
      {
         if( (crc & 1) != 0 )
            crc = (crc >> 1) ^ kPoly;
         else
            crc >>= 1;
      }
      crc_table[i] = crc;
   }

   for(int i = 0; i < 256; i++)
      prefix_table[(crc_table[i] >> 24) & 0xff] = i;
}

// Compute partial CRC by scanning forward one byte at a time.
static uint32_t ForwardCrc(const std::string &data, uint32_t crc)
{
   for(uint8_t c : data)
      crc = ((crc >> 8) & 0xffffff) ^ crc_table[(crc ^ c) & 0xff];
   return crc;
}

// Compute reverse partial CRC by scanning backward one byte at a time.
static uint32_t ReverseCrc(const std::string &data, uint32_t crc)
{
   for(int i = static_cast<int>(data.size()); i-- > 0;)
   {
      // a1.b1.c1.d1 = (a0.b0.c0) ^ crc_table[d0 ^ byte]
      //
      // There is exactly one crc_table entry with the prefix a1, so we can
      // get the right side of the XOR with a single lookup.
      const int r_index = prefix_table[(crc >> 24) & 0xff];
      const uint32_t r_value = crc_table[r_index];

      // r_index = d0^byte  ->  d0 = r_index^byte.
      const uint8_t byte = data[i];
      const uint32_t d0 = r_index ^ byte;

      // b1.c1.d1 = (a0.b0.c0) ^ (r_value & 0xffffff)  ->
      // a0.b0.c0 = b1.c1.d1 ^ (r_value & 0xffffff)
      const uint32_t abc0 = r_value ^ crc;

      // Reassemble the combined CRC bytes.
      crc = ((abc0 & 0xffffff) << 8) | d0;
   }

   return crc;
}

}  // namespace

int main(int argc, char **argv)
{
   uint32_t target_crc;

   if( argc != 3 || sscanf(argv[2], "%x", &target_crc) != 1 )
      return printf("%s {input.txt} {target_crc}\n", *argv);

   // Load input to memory.
   std::string data = LoadInput(argv[1]);
   if( data.empty() )
      return 1;

   // Replace substring with desired CRC.
   if( !InsertCrc(&data, target_crc) )
   {
      fprintf(stderr, "%s: missing placeholder for CRC (%s)\n",
              argv[1], kCrcKey);
      return 1;
   }

   // Break input into three sections: prefix + adjustment + suffix.
   const size_t adjust_offset = data.find(kAdjustKey);
   if( adjust_offset == std::string::npos )
   {
      fprintf(stderr, "%s: missing placeholder for adjustment string (%s)\n",
              argv[1], kAdjustKey);
      return 1;
   }
   const std::string prefix = data.substr(0, adjust_offset);
   std::string adjustment(strlen(kAdjustKey), 33);
   const std::string suffix = data.substr(adjust_offset + adjustment.size());

   // Compute CRC of prefix and suffix.
   InitCrcTables();
   const uint32_t prefix_crc_end = ForwardCrc(prefix, ~0);
   const uint32_t suffix_crc_start = ReverseCrc(suffix, ~target_crc);

   // Brute-force the middle part.
   for(uint64_t steps = 0;;)
   {
      if( ForwardCrc(adjustment, prefix_crc_end) == suffix_crc_start )
         break;

      size_t i = 0;
      for(; i < strlen(kAdjustKey); i++)
      {
         adjustment[i]++;
         if( adjustment[i] < 127 )
            break;
         adjustment[i] = 33;
      }
      if( i == strlen(kAdjustKey) )
      {
         fprintf(stderr, "%s: failed to adjust for %08x\n",
                 argv[1], target_crc);
         return 1;
      }

      steps++;
      if( (steps & 0xffffff) == 0 )
      {
         fprintf(stderr, "%s: testing adjustment %" PRIu64 ": %s\n",
                 argv[1], steps, adjustment.c_str());
      }
   }

   // Write output.
   fwrite(prefix.data(), prefix.size(), 1, stdout);
   fwrite(adjustment.data(), adjustment.size(), 1, stdout);
   fwrite(suffix.data(), suffix.size(), 1, stdout);
   return 0;
}