Jabberwocky submission for Computer Organization
You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

109 lines
2.2 KiB

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. void wocky ( FILE *ifp, FILE *ofp );
  4. int main( int argc, char *argv[] ) {
  5. FILE *ifp, *ofp;
  6. if (argc < 3) {
  7. fprintf(stderr, "Not enough arguments\n");
  8. exit(1);
  9. }
  10. if (!(ifp = fopen(argv[1],"r"))) {
  11. fprintf(stderr,"Cannot open file %s\n",argv[1]);
  12. exit(1);
  13. }
  14. if (!(ofp = fopen(argv[2],"w"))) {
  15. fprintf(stderr,"Cannot open file %s\n",argv[2]);
  16. exit(1);
  17. }
  18. wocky(ifp, ofp);
  19. return 0;
  20. }
  21. typedef struct element_t {
  22. char c;
  23. struct element_t * prefix;
  24. } element;
  25. element * new_element( element * prefix, char c ) {
  26. element * e = malloc(sizeof(element));
  27. e -> prefix = prefix;
  28. e -> c = c;
  29. return e;
  30. }
  31. // Print a prefix using some recursion
  32. void fprint_element(FILE *fp, element * e) {
  33. if (e -> prefix != NULL) {
  34. fprint_element(fp, e -> prefix);
  35. fputc(e -> c, fp);
  36. }
  37. }
  38. void wocky ( FILE *ifp, FILE *ofp ) {
  39. // Read the entire file into a buffer
  40. fseek(ifp, 0L, SEEK_END);
  41. long sz = ftell(ifp);
  42. rewind(ifp);
  43. char * buffer = malloc(sz);
  44. fread(buffer, 1, sz, ifp);
  45. // Start the table of prefixes
  46. element ** table = malloc(sizeof(element*));
  47. table[0] = new_element(NULL, '\0');
  48. int t_length = 1;
  49. int t_capacity = 1;
  50. int index = 0; // Index of prefix
  51. int length = 0; // Number of bits index will be represented in
  52. int read = 0; // Number of bits currently read
  53. char c;
  54. int i;
  55. for (i = 0; i <= sz; ++i) {
  56. c = buffer[i];
  57. if (read == length) {
  58. // Print prefix at index
  59. fprint_element(ofp, table[index]);
  60. // Grow table if full
  61. if (t_length == t_capacity) {
  62. // Double capacity
  63. element ** new_table = malloc(2 * t_capacity * sizeof(element*));
  64. int j;
  65. for (j = 0; j < t_capacity; ++j) {
  66. new_table[j] = table[j];
  67. }
  68. free(table);
  69. table = new_table;
  70. t_capacity *= 2;
  71. }
  72. // Add new prefix
  73. table[t_length++] = new_element(table[index], c);
  74. element * e = table[t_length - 1];
  75. // Print bit
  76. fputc(c, ofp);
  77. // Length increases when max index requires more bits to represent
  78. if ((t_length - 1) & (1 << length) || length == 0) {
  79. ++length;
  80. }
  81. read = 0;
  82. index = 0;
  83. } else {
  84. ++read;
  85. if (c == '1') {
  86. index += 1 << (length - read);
  87. }
  88. }
  89. }
  90. }