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.

142 lines
2.6 KiB

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. void jabber ( 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. jabber(ifp, ofp);
  19. return 0;
  20. }
  21. typedef struct node_t {
  22. int index;
  23. // Children
  24. struct node_t * zero;
  25. struct node_t * one;
  26. } node;
  27. node * new_node( int index ) {
  28. node * n = malloc(sizeof(node));
  29. n -> index = index;
  30. n -> zero = NULL;
  31. n -> one = NULL;
  32. return n;
  33. }
  34. void printTree(node * curr, int depth);
  35. void jabber( FILE *ifp, FILE *ofp ) {
  36. // Read the entire file into a buffer
  37. fseek(ifp, 0L, SEEK_END);
  38. long sz = ftell(ifp);
  39. rewind(ifp);
  40. char * buffer = malloc(sz);
  41. fread(buffer, 1, sz, ifp);
  42. // Start the tree
  43. node * root = new_node(0);
  44. node * cursor = root;
  45. int index = 0;
  46. int bits = 0;
  47. int i;
  48. for (i = 0; i < sz; ++i) {
  49. char c = buffer[i];
  50. if (c == '0') {
  51. if (cursor -> zero == NULL) {
  52. // Print index
  53. int j;
  54. for (j = bits - 1; j >= 0; --j) {
  55. fputc('0' + ((cursor -> index >> j) & 1), ofp);
  56. }
  57. // Append next bit
  58. fputc('0', ofp);
  59. // Create new node
  60. cursor -> zero = new_node(++index);
  61. } else {
  62. // Step down
  63. cursor = cursor -> zero;
  64. continue;
  65. }
  66. } else if (c == '1') {
  67. if (cursor -> one == NULL) {
  68. // Print index
  69. int j;
  70. for (j = bits - 1; j >= 0; --j) {
  71. fputc('0' + ((cursor -> index >> j) & 1), ofp);
  72. }
  73. // Append next bit
  74. fputc('1', ofp);
  75. // Create new node
  76. cursor -> one = new_node(++index);
  77. } else {
  78. // Step down
  79. cursor = cursor -> one;
  80. continue;
  81. }
  82. } else {
  83. fprintf(stderr, "Invalid character");
  84. exit(1);
  85. }
  86. // Update bits if needed
  87. if (1 << bits & index)
  88. ++bits;
  89. // Reset the cursor
  90. cursor = root;
  91. }
  92. // Final index
  93. int j;
  94. for (j = bits - 1; j >= 0; --j) {
  95. fputc('0' + ((cursor -> index >> j) & 1), ofp);
  96. }
  97. //printTree(root, 0);
  98. }
  99. int rec[1];
  100. //int rec[1000000];
  101. void printTree(node * curr, int depth)
  102. {
  103. int i;
  104. if(curr==NULL)return;
  105. printf("\t");
  106. for(i=0;i<depth;i++)
  107. if(i==depth-1)
  108. printf("%s---",rec[depth-1]?"L":"R");
  109. else
  110. printf("%s ",rec[i]?"|":" ");
  111. printf("%d\n",curr->index);
  112. rec[depth]=1;
  113. printTree(curr->zero,depth+1);
  114. rec[depth]=0;
  115. printTree(curr->one,depth+1);
  116. }