fork download 
  1. #include <stdio.h>
  2.  
  3. // Huffman table:
  4.  
  5. // a 01
  6. // b 0001
  7. // c 1
  8. // d 0010
  9.  
  10. char* string = "abdcc";
  11.  
  12. // 01 0001 0010 1 1
  13.  
  14. // reverse bit order (MSB first) an add extra 0 for padding:
  15. #define MESSAGE_LENGTH  (12)
  16. unsigned int message[] = {0b110100100010, 0};
  17.  
  18. unsigned int getBits(int start, int n)
  19. {
  20.     return ((message[start>>5] >> (start&31)) | (message[(start>>5)+1] << (32-(start&31)))) & ((1<<n)-1);
  21. }
  22.  
  23. unsigned int codes[26];
  24. int code_lengths[26];
  25. int callCount = 0;
  26.  
  27. void outputCodes()
  28. {
  29. 	// output the codes:
  30. 	int i, j;
  31. 	for(i = 0; i < 26; i++)
  32. 	{
  33. 		if(code_lengths[i] != 0)
  34. 		{
  35. 		    printf("%c ", i + 'a');
  36. 		    for(j = 0; j < code_lengths[i]; j++)
  37. 		        printf("%s", codes[i] & (1 << j) ? "1" : "0");
  38. 		    printf("\n");
  39. 		}
  40. 	}
  41. }
  42.  
  43. void matchHuffmanString(char* s, int len, int startbit)
  44. {
  45. 	callCount++;
  46.  
  47. 	if(len > MESSAGE_LENGTH - startbit)
  48. 	    return;  // not enough bits left to encode the rest of the message even at 1 bit per char
  49.  
  50. 	if(len == 0) // no more characters to match
  51. 	{
  52. 		if(startbit == MESSAGE_LENGTH)
  53. 		{
  54. 			// we exactly used up all the bits, this stream matches.
  55. 			printf("match!\n\n");
  56. 			outputCodes();
  57. 			printf("\nCall count: %d\n", callCount);
  58. 		}
  59. 		return;
  60. 	}
  61.  
  62. 	// read a character from the string (assume 'a' to 'z'):
  63. 	int c = s[0] - 'a';
  64.  
  65. 	// is there already a code for this character?
  66. 	if(code_lengths[c] != 0)
  67. 	{
  68. 		// check if the code in the bit stream matches:
  69. 		int length = code_lengths[c];
  70. 		if(startbit + length > MESSAGE_LENGTH)
  71. 		    return; // ran out of bits in stream, no match
  72. 		unsigned int bits = getBits(startbit, length);
  73. 		if(bits != codes[c])
  74. 		    return; // bits don't match
  75.  
  76. 		matchHuffmanString(s + 1, len - 1, startbit + length);
  77. 	}
  78. 	else
  79. 	{
  80. 		// this character doesn't have a code yet, consider every possible length
  81. 		int i, j;
  82. 		for(i = 1; i < 32; i++)
  83. 		{
  84. 			// are there enough bits left for a code this long?
  85. 			if(startbit + i > MESSAGE_LENGTH)
  86. 			    continue;
  87.  
  88. 			unsigned int bits = getBits(startbit, i);
  89. 			// does this code conflict with an existing code?
  90. 			for(j = 0; j < 26; j++)
  91. 			{
  92. 				if(code_lengths[j] != 0) // check existing codes only
  93. 				{
  94. 					// do the two codes match in the first i or code_lengths[j] bits, whichever is shorter?
  95. 					int length = code_lengths[j] < i ? code_lengths[j] : i;
  96. 					if((bits & ((1 << length)-1)) == (codes[j] & ((1 << length)-1)))
  97. 					    break; // there's a conflict
  98. 				}
  99. 			}
  100. 			if(j != 26)
  101. 			    continue; // there was a conflict
  102.  
  103. 			// add the new code to the codes array and recurse:
  104. 			codes[c] = bits; code_lengths[c] = i;
  105. 			matchHuffmanString(s + 1, len - 1, startbit + i);
  106. 			code_lengths[c] = 0; // clear the code (backtracking)
  107. 		}
  108. 	}
  109. }
  110.  
  111. int main(void) {
  112. 	int i;
  113. 	for(i = 0; i < 26; i++)
  114. 	    code_lengths[i] = 0;
  115.  
  116. 	matchHuffmanString(string, 5, 0);
  117.  
  118. 	return 0;
  119. }
  120.  
Success #stdin #stdout 0s 2008KB
comments ()
stdin 
Standard input is empty
stdout 
match!

a 01
b 0001
c 1
d 0010

Call count: 42
https://ideone.com/TqV3Xy
language:
C (gcc 8.3)
created:
9 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!