<repo_name>aameen951/simple_compressor<file_sep>/src/file.h
#include <stdio.h>

struct ReadFileResult
{
  bool succeeded;
  DataView data;
};
ReadFileResult read_input_file(char *file_path){
  auto file = fopen(file_path, "rb");
  if(file)
  {
    fseek(file, 0, SEEK_END);
    auto size = ftell(file);
    fseek(file, 0, SEEK_SET);
    auto buffer = (u8 *)malloc(size);
    fread(buffer, size, 1, file);
    fclose(file);
    return {true, {buffer, (um)size}};
  }
  return {false};
}
void read_file_result_free(DataView *data){
  free(data->data);
  data->data = NULL;
  data->count = 0;
}
bool write_output_file(char *file_path, DataView data){
  auto file = fopen(file_path, "wb");
  if(file)
  {
    fwrite(data.data, data.count, 1, file);
    fclose(file);
    return true;
  }
  return false;
}

<file_sep>/src/LZ.cpp

struct FindPrefixResult
{
  um run_start;
  um run_len;
};
FindPrefixResult find_best_prefix_match(DataView data, um a_idx, um b_idx, um max_run_size)
{
  FindPrefixResult result = {};
  for(um j=a_idx; j<b_idx; j++)
  {
    um run_len = 0;
    while(b_idx+run_len < data.count && run_len < max_run_size)
    {
      if(data.data[j+run_len] != data.data[b_idx+run_len])
      {
        break;
      }
      run_len++;
    }
    if(run_len >= result.run_len)
    {
      result.run_len = run_len;
      result.run_start = j;
    }
  }
  return result;
}

COMPRESS_DEF(lz_compress)
{
  um MAX_RUN_SIZE = (1 << 16) - 1;
  sm MAX_LOOKBACK = (1 << 8) - 1;
  um MIN_RUN_LEN = 8;
  
  sm last_copy_idx = -1;
  sm last_copy_len = 0;
  for(sm i=0; i<input.count; )
  {
    um start = MAX(0, i-MAX_LOOKBACK);
    auto best_match = find_best_prefix_match(input, start, i, MAX_RUN_SIZE);

    if(best_match.run_len < MIN_RUN_LEN)
    {
      if(last_copy_idx == -1 || last_copy_len >= MAX_RUN_SIZE)
      {
        last_copy_idx = output->count+1;
        last_copy_len = 0;
        data_buffer_append(output, (u8)0x00);
        data_buffer_append(output, (u16)0x0000);
      }

      last_copy_len++;
      data_buffer_append(output, input.data[i]);
      *(u16 *)(output->data+last_copy_idx) = last_copy_len;
      i++;
    }
    else
    {
      data_buffer_append(output, (u8)(i-best_match.run_start));
      data_buffer_append(output, (u16)best_match.run_len);
      last_copy_idx = -1;
      i += best_match.run_len;
    }
  }
}

DECOMPRESS_DEF(lz_decompress)
{
  um i;
  for(i=0; i<input.count-3; )
  {
    u8 offset = input.data[i++];
    u16 length = *(u16 *)(input.data + i);
    i += 2;

    if(offset == 0)
    {
      if(i+length > input.count)return false;
      data_buffer_append_memory(output, {input.data+i, length});
      i += length;
    }
    else
    {
      if((sm)output->count - (sm)offset < 0)return false;
      data_buffer_ensure_room_for(output, length);
      for(um j=0; j<length; j++)
      {
        output->data[output->count+j] = output->data[output->count-offset+j];
      }
      output->count += length;
    }
  }
  if(i != input.count)return false;
  return true;
}
<file_sep>/src/RLE.cpp

COMPRESS_DEF(rle_compress)
{
  um MAX_RUN_LEN = 32767;
  um MIN_RUN_LEN = 4;
  sm last_copy_idx = -1;
  um last_copy_len = 0;
  for(um i=0; i < input.count; )
  {
    u8 c = input.data[i];
    u16 run_len = 1;
    // grap the following characters if they are the same as this character.
    while(i+run_len < input.count && run_len < MAX_RUN_LEN && c == input.data[i+run_len])run_len++;
    
    // If the run of repeated characters is above a minimum length
    if(run_len >= MIN_RUN_LEN)
    {
      // push the run length as 16bit Little Endian (the 16th bit is always zero).
      data_buffer_append(output, run_len);
      // push the repeated character.
      data_buffer_append(output, c);
      last_copy_idx = -1;
    }
    else
    {
      if(last_copy_idx == -1 || last_copy_len >= MAX_RUN_LEN)
      {
        // Initialize a data copy run.
        last_copy_idx = output->count;
        last_copy_len = 0;
        // push the initial run size as 16bit-LE (the 16th bit is always one).
        data_buffer_append(output, (u16)0x8000);
      }
      // ensure the run size doesn't exceed MAX_RUN_LEN
      run_len = MIN(run_len, MAX_RUN_LEN - last_copy_len);

      // append data to previous copy run.
      last_copy_len += run_len;
      for(um j=0; j<run_len; j++)data_buffer_append(output, input.data[i+j]);
      // overwrite the old run size with the new one as 16bit-LE (the 16th bit is always one).
      *(u16 *)(output->data+last_copy_idx) = 0x8000 + last_copy_len;
    }
    i += run_len;
  }
}

DECOMPRESS_DEF(rle_decompress)
{
  um i;
  for(i=0; i<input.count-2; )
  {
    // read 16bit-LE
    u16 run_len = *(u16 *)(input.data + i);
    i += 2;
    // If the 16th bit is set then it is a copy run
    if(run_len & 0x8000)
    {
      run_len = run_len & 0x7fff;
      if(i+run_len > input.count)return false;
      data_buffer_append_memory(output, {input.data+i, run_len});
      i += run_len;
    }
    else // it is a repeated run.
    {
      if(i >= input.count)return false;
      u8 repeated_byte = input.data[i++];
      // write the repeated byte to output.
      data_buffer_ensure_room_for(output, run_len);
      for(um j=0; j<run_len; j++)
      {
        output->data[output->count++] = repeated_byte;
      }
    }
  }
  if(i != input.count)return false;
  return true;
}
<file_sep>/src/mystd.h
#include <stdint.h>
#include <string.h>
#include <stdlib.h>
typedef uint8_t u8;
typedef uint16_t u16;
typedef size_t um;
typedef intptr_t sm;

#ifndef MAX
#define MAX(a, b) ( (a) > (b) ? (a) : (b) )
#endif
#ifndef MIN
#define MIN(a, b) ( (a) < (b) ? (a) : (b) )
#endif

struct DataView
{
  u8 *data;
  um count;
};
struct DataBuffer
{
  u8 *data;
  um size, count;

  DataView to_data_view(){
    return {data, count};
  }
};

#ifdef MYSTD_IMPLEMENTATION

void data_buffer_ensure_room_for(DataBuffer *buffer, um room_for)
{
  if(buffer->count+room_for > buffer->size)
  {
    um new_size = MAX(8, 2 * buffer->size);
    new_size = MAX(new_size, buffer->count+room_for);
    buffer->data = (u8 *)realloc(buffer->data, new_size);
    buffer->size = new_size;
  }
}
void data_buffer_append(DataBuffer *buffer, u8 byte)
{
  data_buffer_ensure_room_for(buffer, 1);
  buffer->data[buffer->count] = byte;
  buffer->count += 1;
}
void data_buffer_free(DataBuffer *buffer)
{
  free(buffer->data);
  buffer->data = NULL;
  buffer->count = 0;
  buffer->size = 0;
}
void data_buffer_append(DataBuffer *buffer, u16 two_bytes)
{
  data_buffer_ensure_room_for(buffer, 2);
  *(u16 *)(buffer->data + buffer->count) = two_bytes;
  buffer->count += 2;
}
void data_buffer_append_memory(DataBuffer *buffer, DataView memory)
{
  data_buffer_ensure_room_for(buffer, memory.count);
  memcpy(buffer->data+buffer->count, memory.data, memory.count);
  buffer->count += memory.count;
}
bool data_equal(DataView a, DataView b)
{
  if(a.count != b.count)return false;
  return memcmp(a.data, b.data, a.count) == 0;
}

#endif
<file_sep>/src/compressor-interface.h

#define COMPRESS_DEF(name) void name(DataView input, DataBuffer *output)
#define DECOMPRESS_DEF(name) bool name(DataView input, DataBuffer *output)

typedef COMPRESS_DEF(compress_fn);
typedef DECOMPRESS_DEF(decompress_fn);
<file_sep>/src/simple_compressor.cpp
#define MYSTD_IMPLEMENTATION
#include "mystd.h"

#include "file.h"

#include "compressor-interface.h"
#include "RLE.cpp"
#include "LZ.cpp"

#define VERIFY_COMPRESSION 1

void usage()
{
  printf("\n");
  printf("  Usage: simple_compressor compress   <raw-file>    <output-file>\n");
  printf("         simple_compressor decompress <output-file> <raw-file>\n");
  printf("\n");
}

struct CompressorDesc
{
  char *name;
  compress_fn *compress;
  decompress_fn *decompress;
};

#define COMPRESSIO_RLE 0
#define COMPRESSIO_LZ 1
CompressorDesc compressors[] = {
  {"RLE", rle_compress, rle_decompress},
  {"LZ", lz_compress, lz_decompress},
};

enum AppCommand
{
  AppCommand_Unknown,
  AppCommand_Compress,
  AppCommand_Decompress,
};

int main(int argc, char **argv)
{
  if(argc != 4)
  {
    printf("\nError: incorrect number of arguments.\n");
    usage();
    return 1;
  }

  char *command_str = argv[1];
  char *input_file_path = argv[2];
  char *output_file_path = argv[3];

  AppCommand command = AppCommand_Unknown;
  if(strcmpi(command_str, "compress") == 0)
  {
    command = AppCommand_Compress;
  }
  else if(strcmpi(command_str, "decompress") == 0)
  {
    command = AppCommand_Decompress;
  }
  else
  {
    printf("\nError: unknown command '%s'.\n", command_str);
    usage();
    return 2;
  }

  auto read_result = read_input_file(input_file_path);
  if(!read_result.succeeded)
  {
    printf("\nError: failed to load input file '%s'\n", input_file_path);
    return 3;
  }
  auto input_data = read_result.data;

  auto compressor = compressors[COMPRESSIO_LZ];

  switch(command)
  {
    case AppCommand_Compress:{

      DataBuffer compressed_data = {};
      compressor.compress(input_data, &compressed_data);

      if(VERIFY_COMPRESSION)
      {
        DataBuffer decompressed_data = {};
        auto succeeded = compressor.decompress(compressed_data.to_data_view(), &decompressed_data);
        if(!succeeded || !data_equal(input_data, decompressed_data.to_data_view()))
        {
          printf("\nError: We didn't get the same data after decompressing the compressed output!\n\n");
          return 5;
        }
        data_buffer_free(&decompressed_data);
      }

      if(!write_output_file(output_file_path, compressed_data.to_data_view()))
      {
        printf("\nError: Failed to write the compressed file to '%s'\n\n", output_file_path);
        return 4;
      }

      printf("\n");
      printf("Original size: %llu\n", input_data.count);
      printf("Compressed size: %llu\n", compressed_data.count);
      printf("Compression percentage: %%%.2f\n", 100.0 * compressed_data.count/input_data.count);
      printf("\n");

      data_buffer_free(&compressed_data);
      
    }break;
    case AppCommand_Decompress:{
      
      DataBuffer uncompressed_data = {};
      if(!compressor.decompress(input_data, &uncompressed_data))
      {
        printf("\nError: the file is corrupted. Could not decompress\n\n");
        return 5;
      }


      if(!write_output_file(output_file_path, uncompressed_data.to_data_view()))
      {
        printf("\nError: Failed to write the decompressed file to '%s'\n\n", output_file_path);
        return 4;
      }

      data_buffer_free(&uncompressed_data);

    }break;
    default:
    {
      printf("\nInternal Error: unhandled command '%d'\n", command);
      return 999;
    }break;
  }
  read_file_result_free(&input_data);
  return 0;
}
