#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <windows.h>
#include <winbase.h>

typedef struct huffnode {
  struct huffnode   *left;         /* Left child */
  struct huffnode   *right;        /* Right child */
  char              car;          /* Character stored in the node */
  int               freq;          /* Frequency that this char appeared in the file */
} Huffnode;

typedef struct {
  unsigned short  code;
  short           nbits;
} Codes;

int            hash[128];          /* hashes characters to their posisions in the codes
				    * array. */


// Buffer to hold the data while they are being zipped

#define NFILES 1
#define BUFFERSIZE 40000

char  Buffer[BUFFERSIZE];
int   Bufferlength = 0;
char  *Bufferptr;

/*char           infile[10000];
int            filelength = 0;*/

Huffnode  *    heap[20];

void           encode(void);
Huffnode **    getfreq(int *);
void           buildheap(Huffnode **, int);
Huffnode *     buildcodetree(Huffnode **, int);
Codes *        assigncodes(Huffnode *, int);
void           buildstream(HANDLE, Codes *);
void           cleanup(Huffnode *, Codes *);
void           heapify(int, int);
Huffnode *     getmin(Huffnode **, int *);
void           insert(Huffnode *, int *, Huffnode **);
void           getCodes(Huffnode *, Codes *, 
			unsigned short, short *, short);
void           delete(Huffnode *);
int            left(int);
int            right(int);
int            parent(int);


/* functions used to decode the encoded stream */

void           extract(char *);
Huffnode *     constructtree(HANDLE);
void           decodestream(HANDLE, Huffnode *, char *);

/* main has to fill out the filelength and infile[] */

int main(void) {
  HANDLE file;
  char car;
  DWORD dwActBytes;
  file = CreateFile("file.myzip", GENERIC_READ, FILE_SHARE_READ,
		NULL, OPEN_EXISTING, FILE_ATTRIBUTE_NORMAL, NULL);
  while (ReadFile(filed, &car, sizeof(char), &dwActBytes, NULL)) {
    Buffer[Bufferlength++] = car;
  }
  Buffer[Bufferlength] = '\0';
  CloseHandle(file);
  encode();
  extract("file.myzip");
  return 0;
}

void extract(HANDLE *filename) {
  HANDLE       file;
  Huffnode *   root;

  file = CreateFile(filename, GENERIC_READ, FILE_SHARE_READ,
		NULL, OPEN_EXISTING, FILE_ATTRIBUTE_NORMAL, NULL);
  root = constructtree(file);
  decodestream(file, root, filename);
}

Huffnode * constructtree(HANDLE filed) {
  char                  car;
  int                   freq;
  int                   size = 1;
  DWORD                 dwActBytes;
  Huffnode              **heap = calloc(20, sizeof(Huffnode *));

  while (1) {
    ReadFile(filed, &car, sizeof(char), &dwActBytes, NULL);
    if (car == ' ') 
      break;
    ReadFile(filed, &freq, sizeof(int), &dwActBytes, NULL);
    heap[size] = calloc(1, sizeof(Huffnode));
    heap[size]->car = car;
    heap[size++]->freq = freq;
  }
  size--;

  buildheap(heap, size);
  return buildcodetree(heap, size);
}

void decodestream(HANDLE filed, Huffnode *root, char *filename) {
  char        newfilename[50];
  int         length;
  short       Buffer[5000],
              bit;
  char        asci[10000];
  char        *charptr;
  int         offset;
  short       posision;
  int         i,
              place = 0;
  Huffnode    *ptr = root;
  HANDLE      ascifile;
  DWORD       dwActBytes;

  ReadFile(filed, &length, sizeof(int), &dwActBytes, NULL);
  ReadFile(filed, &posision, sizeof(short), &dwActBytes, NULL);
  ReadFile(filed, Buffer, length * sizeof(short), &dwActBytes, NULL);

  for (offset = 0; offset < length - 1; offset++) {
    for (i = sizeof(short) * 8 - 1; i >= 0; i--) {
      bit = Buffer[offset] >> i;
      if (bit & 1) {
	if (ptr->right)
	  ptr = ptr->right;
	else {
	  asci[place++] = ptr->car;
	  ptr = root->right;
	}
      }
      else {
	if (ptr->left)
	  ptr = ptr->left;
	else {
	  asci[place++] = ptr->car;
	  ptr = root->left;
	}
      }
    }
  }

  for (i = sizeof(short) * 8 - 1; i >= posision; i--) {
    bit = Buffer[offset] >> i;
    if (bit & 1) {
      if (ptr->right)
	ptr = ptr->right;
      else {
	asci[place++] = ptr->car;
	ptr = root->right;
      }
    }
    else {
      if (ptr->left)
	ptr = ptr->left;
      else {
	asci[place++] = ptr->car;
	ptr = root->left;
      }
    }
  }

  if (!ptr->left) {
    asci[place++] = ptr->car;
  }


  CloseHandle(filed);
  strcpy(newfilename, filename);
  charptr = strstr(newfilename, ".myzip");
  strcpy(charptr, ".dat");
  ascifile = CreateFile(newfilename, GENERIC_WRITE, 0,
		NULL, CREATE_ALWAYS, FILE_ATTRIBUTE_NORMAL, NULL);
  WriteFile(ascifile, asci, place * sizeof(char), &dwActBytes, NULL);
  CloseHandle(ascifile);
  return;
}

void encode(void) {
  
  Huffnode      *root;
  int           size = 1;
  Codes         *codes;
  char          space = ' ';
  HANDLE        file;
  char          str[50];
  SYSTEMTIME    st;
  DWORD         dwActBytes;
  
  int i;

	
  GetLocalTime(&st);
  wsprintf(str, ".\\dat\\%d%d%d%d%d%d%d", st.wYear, st.wMonth,
						st.wDay, st.wHour, st.wMinute, st.wSecond, st.wMilliseconds);
  file =  CreateFile(str, GENERIC_WRITE, 0,
		NULL, CREATE_ALWAYS, FILE_ATTRIBUTE_NORMAL, NULL);
              
  getfreq(&size);

  for (i = 1; i <= size; i++) {
    WriteFile(file, &heap[i]->car, sizeof(char), &dwActBytes, NULL);
    WriteFile(file, &heap[i]->freq, sizeof(int), &dwActBytes, NULL);
  }
  WriteFile(file, &space, sizeof(char), &dwActBytes, NULL);
  buildheap(heap, size);
  root = buildcodetree(heap, size);
  codes = assigncodes(root, size);
  buildstream(file, codes);
  CloseHandle(file);
  cleanup(root, codes);
}

Huffnode **    getfreq(int *size) {
  int          freq[128] = {0};
  int          i;
  char str[100];
  int          length = strlen(Buffer[Buffercounter]);

  for (i = 0; i < length; i++)
    freq[Buffer[Buffercounter][i]]++;

  for (i = 0; i < 128; i++) {
    if (freq[i]) {
		heap[*size] = calloc(1, sizeof(Huffnode));
		if (!heap[*size]) {
			wsprintf (str, "did not allocate heap size is %i", (*size) - 1);
			MessageBox(NULL, str, "Error", MB_OK);
		}
      heap[*size]->freq = freq[i];
      heap[*size]->car = i;
      (*size)++;
    }
  }
  (*size)--;
  return heap;
}

void           buildheap(Huffnode   **heap, 
			             int        size) {
  int i;
  for (i = (int) size/2; i >= 1; i--)
    heapify(size, i);
}

Huffnode *     buildcodetree(Huffnode   **heap, 
			     int        size) {
  int          i,
               org_size = size;
  Huffnode     *left,
               *right,
               *newnode;
  
  for (i = 0; i < org_size - 1; i++) {
    newnode = calloc(1, sizeof(Huffnode));
    left = getmin(heap, &size);
    right = getmin(heap, &size);
    newnode->freq = left->freq + right->freq;
    newnode->left = left;
    newnode->right = right;
    insert(newnode, &size, heap);
  }
  return getmin(heap, &size);
}

Codes *        assigncodes(Huffnode   *root,
			   int        size) {
  Codes        *codes = calloc(size, sizeof(Codes));
  short        index = 0;

  getCodes(root, codes, 0, &index, 0);
  return codes;
}

void           buildstream(HANDLE       file, 
			               Codes *      codes) {
  short           stream[5000] = {0};
  int             i;
  short           posision = sizeof(unsigned short) * 8;
  int             masklength;
  short           *streamptr = stream;
  unsigned short  mask,
                  bits;
  DWORD           dwActBytes;
  int             length = strlen(Buffer[Buffercounter]);

  for (i = 0; i < length; i++) {
    mask = codes[hash[Buffer[Buffercounter][i]]].code;
    masklength = codes[hash[Buffer[Buffercounter][i]]].nbits;
    posision = posision - masklength;
    if (posision < 0) {
      bits = mask >> abs(posision);
      (*streamptr) |= bits;
      streamptr++;
      posision = sizeof(unsigned short) * 8 + posision;
      bits = mask << posision;
      (*streamptr) |= bits;
    }
    else {
      bits = mask << posision;
      (*streamptr) |= bits;
      if (!posision) {
	posision = sizeof(unsigned short) * 8;
	streamptr++;
      }
    }
  }
  
  /* write out the rest of the file */
  i = streamptr - stream + 1;
  WriteFile(file, &i, sizeof(int), &dwActBytes, NULL);
  WriteFile(file, &posision, sizeof(short), &dwActBytes, NULL);
  WriteFile(file, stream, i * sizeof(short), &dwActBytes, NULL);

}

void           cleanup(Huffnode *     root, 
					   Codes *        codes) {


  /* deallocate the code tree */

  //delete(root);

  /* deallocate the code array */

  free(codes);
}

void           heapify(int            size,
		               int            posision) {
  int          l,
               r,
               smallest;
  Huffnode *   tmp;

  l = left(posision);
  r = right(posision);
  if (l <= size && heap[l]->freq < heap[posision]->freq)
    smallest = l;
  else
    smallest = posision;
  if (r <= size && heap[r]->freq < heap[smallest]->freq)
    smallest = r;
  if (smallest != posision) {
    tmp = heap[smallest];
    heap[smallest] = heap[posision];
    heap[posision] = tmp;
    heapify(size, smallest);
  }
}

int left(int i) {
  return 2 * i;
}

int right(int i) {
  return 2 * i + 1;
}

Huffnode *     getmin(Huffnode **     heap, 
		      int *           size) {
  
  Huffnode *   min;

  if (*size < 1) {
    printf("Error: heap underflow!\n");
    exit(0);
  }
  min = heap[1];
  heap[1] = heap[*size];
  (*size)--;
  heapify(*size, 1);
  return min;
}

void           insert(Huffnode *      newnode,
		      int *           size,
		      Huffnode **     heap) {
  int parent, child;
  Huffnode *tmp;

  (*size)++;
  heap[*size] = newnode;
  parent = (int)(*size)/2;
  child = *size;
  while (parent >= 1) {
    if (heap[parent]->freq > heap[child]->freq) {
      tmp = heap[parent];
      heap[parent] = heap[child];
      heap[child] = tmp;
      child = parent;
      parent /= 2;
    }
    else
      parent = 0;
  }
}

int parent(int i) {
  return (int) i/2;
}

void           getCodes(Huffnode *      root, 
			            Codes *         codes,
                        unsigned short  prefix, 
			            short *         index, 
			            short           nbits) {
  if (root->left && root->right) {
    prefix = prefix << 1;
    getCodes(root->left, codes, prefix, index, (short)nbits + 1);
    prefix = prefix | 1;
    getCodes(root->right, codes, prefix, index, nbits + 1);
  }
  else {
    codes[*index].code = prefix;
    codes[*index].nbits = nbits;
    (*index)++;
    hash[root->car] = (*index) - 1;
  }
}

void           delete(Huffnode * root) {
  if (root->left != NULL)
    delete(root->left);
  if (root->right != NULL)
    delete(root->right);
  free(root);
}










