1 Function noMoreFreeMemory() Which Returns Nothing Is External;
2 Function segmentationFault() Which Returns Nothing Is External;
3 Function
4 printString(PointerToCharacter string) Which Returns Nothing Is External;
5 Function clearScreen() Which Returns Nothing Is External;
6 Function getLengthOfTheInput() Which Returns Integer16 Is External;
7 Function
8 getCharacterOfTheInput(Integer16 index) Which Returns Character Is External;
9
10 Integer32 NDEBUG : = 1;
11
12 Structure TreeNode Consists Of {
13 Character character;
14 Integer16 frequencyOfCharacter;
15 PointerToTreeNode leftChild, rightChild;
16 Character code[16];
17 }
18 EndStructure;
19
20 InstantiateStructure TreeNode treeNodes[64];
21 Integer16 isTreeNodeUsed[64];
22
23 Function isTreeNodeWithinBounds(
24 PointerToTreeNode treeNode) Which Returns Integer32 Does {
25 Return AddressOf(treeNodes[0]) <= treeNode <= AddressOf(treeNodes[64 - 1]) and
26 mod(treeNode - AddressOf(treeNodes[0]), SizeOf(TreeNode)) = 0;
27 }
28 EndFunction;
29
30 Function
31 convertIntegerToString(PointerToCharacter string,
32 Integer32 integer) Which Returns Nothing Is Declared;
33 Function strcat(PointerToCharacter dest,
34 PointerToCharacter src) Which Returns Nothing Is Declared;
35 Function strlen(PointerToCharacter string) Which Returns Integer32 Is Declared;
36
37 Function newTreeNode() Which Returns PointerToTreeNode Does {
38 Integer16 i : = 0;
39 While i < 64 Loop {
40 If not(isTreeNodeUsed[i]) Then {
41 treeNodes[i].character : = 0;
42 treeNodes[i].leftChild : = treeNodes[i].rightChild
43 : = PointerToTreeNode(0);
44 treeNodes[i].code[0] : = 0;
45 treeNodes[i].frequencyOfCharacter : = 0;
46 isTreeNodeUsed[i] : = 1;
47 If NDEBUG = 0 Then {
48 Character stringToBePrinted[64] : = {0};
49 strcat(AddressOf(stringToBePrinted[0]),
50 "NDEBUG: Allocating the TreeNode #");
51 convertIntegerToString(AddressOf(stringToBePrinted[0]) +
52 strlen(AddressOf(stringToBePrinted[0])),
53 i);
54 strcat(AddressOf(stringToBePrinted[0]), "\n");
55 printString(AddressOf(stringToBePrinted[0]));
56 }
57 EndIf;
58 Return AddressOf(treeNodes[i]);
59 }
60 EndIf;
61 i += 1;
62 }
63 EndWhile;
64 noMoreFreeMemory();
65 }
66 EndFunction;
67
68 Function freeTreeNode(PointerToTreeNode treeNode) Which Returns Nothing Does {
69 If not(isTreeNodeWithinBounds(treeNode)) Then { segmentationFault(); }
70 EndIf;
71 If NDEBUG = 0 Then {
72 Character stringToBePrinted[64] : = {0};
73 strcat(AddressOf(stringToBePrinted[0]), "NDEBUG: Freeing the TreeNode #");
74 convertIntegerToString(AddressOf(stringToBePrinted[0]) +
75 strlen(AddressOf(stringToBePrinted[0])),
76 (treeNode - AddressOf(treeNodes[0])) /
77 SizeOf(TreeNode));
78 strcat(AddressOf(stringToBePrinted[0]), "\n");
79 printString(AddressOf(stringToBePrinted[0]));
80 }
81 EndIf;
82 isTreeNodeUsed[(treeNode - AddressOf(treeNodes[0])) / SizeOf(TreeNode)] : = 0;
83 }
84 EndFunction;
85
86 Function strlen(PointerToCharacter str) Which Returns Integer32 Does {
87 Integer32 length : = 0;
88 While ValueAt(str + length) Loop { length += 1; }
89 EndWhile;
90 Return length;
91 }
92 EndFunction;
93
94 Function strcpy(PointerToCharacter dest,
95 PointerToCharacter src) Which Returns Nothing Does {
96 While ValueAt(src) Loop {
97 ValueAt(dest) : = ValueAt(src);
98 dest += 1;
99 src += 1;
100 }
101 EndWhile;
102 ValueAt(dest) : = 0;
103 }
104 EndFunction;
105
106 Function strcat(PointerToCharacter dest,
107 PointerToCharacter src) Which Returns Nothing Does {
108 strcpy(dest + strlen(dest), src);
109 }
110 EndFunction;
111
112 Function reverseString(PointerToCharacter string) Which Returns Nothing Does {
113 PointerToCharacter pointerToLastCharacter : = string + strlen(string) - 1;
114 While pointerToLastCharacter - string > 0 Loop {
115 Character tmp : = ValueAt(string);
116 ValueAt(string) : = ValueAt(pointerToLastCharacter);
117 ValueAt(pointerToLastCharacter) : = tmp;
118 string += 1;
119 pointerToLastCharacter -= 1;
120 }
121 EndWhile;
122 }
123 EndFunction;
124
125 Function convertIntegerToString(PointerToCharacter string,
126 Integer32 number) Which Returns Nothing Does {
127 Integer32 isNumberNegative : = 0;
128 If number < 0 Then {
129 number:
130 = -number;
131 isNumberNegative:
132 = 1;
133 }
134 EndIf;
135 Integer32 i : = 0;
136 While number >= 10 Loop {
137 ValueAt(string + i) : = '0' + mod(number, 10);
138 number /= 10;
139 i += 1;
140 }
141 EndWhile;
142 ValueAt(string + i) : = '0' + number;
143 i += 1;
144 If isNumberNegative Then {
145 ValueAt(string + i) : = '-';
146 i += 1;
147 }
148 EndIf;
149 ValueAt(string + i) : = 0;
150 reverseString(string);
151 }
152 EndFunction;
153
154 Function convertDecimalToString(PointerToCharacter string,
155 Decimal32 number) Which Returns Nothing Does {
156 convertIntegerToString(string, number);
157 number -= Integer32(number);
158 If number < 0 Then { number *= -1; }
159 EndIf;
160 If number = 0 Then { Return; }
161 EndIf;
162 strcat(string, ".");
163 Integer16 numberOfDecimals : = 0;
164 While numberOfDecimals<3 and number> 0 Loop {
165 numberOfDecimals += 1;
166 number *= 10;
167 Character stringWithTheNewDigit[2];
168 stringWithTheNewDigit[0] : = stringWithTheNewDigit[1] : = 0;
169 stringWithTheNewDigit[0] : = '0' + number;
170 strcat(string, AddressOf(stringWithTheNewDigit[0]));
171 number -= Integer32(number);
172 }
173 EndWhile;
174 }
175 EndFunction;
176
177 PointerToCharacter mapOfCodes[256];
178
179 Function assignCode(PointerToCharacter currentCode,
180 PointerToTreeNode treeNode) Which Returns Nothing Does {
181 If NDEBUG = 0 Then {
182 Character stringToBePrinted[64] : = {0};
183 strcat(AddressOf(stringToBePrinted[0]), "NDEBUG: Assigning the code \"");
184 strcat(AddressOf(stringToBePrinted[0]), currentCode);
185 strcat(AddressOf(stringToBePrinted[0]), "\" to the TreeNode #");
186 convertIntegerToString(AddressOf(stringToBePrinted[0]) +
187 strlen(AddressOf(stringToBePrinted[0])),
188 (treeNode - AddressOf(treeNodes[0])) /
189 SizeOf(TreeNode));
190 strcat(AddressOf(stringToBePrinted[0]), ".\n");
191 printString(AddressOf(stringToBePrinted[0]));
192
193 stringToBePrinted[0] : = 0;
194 strcat(AddressOf(stringToBePrinted[0]),
195 "NDEBUG: Its left child is the TreeNode #");
196 If treeNode->leftChild Then {
197 convertIntegerToString(AddressOf(stringToBePrinted[0]) +
198 strlen(AddressOf(stringToBePrinted[0])),
199 (treeNode->leftChild - AddressOf(treeNodes[0])) /
200 SizeOf(TreeNode));
201 }
202 Else { strcat(AddressOf(stringToBePrinted[0]), "null"); }
203 EndIf;
204 strcat(AddressOf(stringToBePrinted[0]), ".\n");
205 printString(AddressOf(stringToBePrinted[0]));
206
207 stringToBePrinted[0] : = 0;
208 strcat(AddressOf(stringToBePrinted[0]),
209 "NDEBUG: Its right child is the TreeNode #");
210 If treeNode->leftChild Then {
211 convertIntegerToString(AddressOf(stringToBePrinted[0]) +
212 strlen(AddressOf(stringToBePrinted[0])),
213 (treeNode->rightChild - AddressOf(treeNodes[0])) /
214 SizeOf(TreeNode));
215 }
216 Else { strcat(AddressOf(stringToBePrinted[0]), "null"); }
217 EndIf;
218 strcat(AddressOf(stringToBePrinted[0]), ".\n");
219 printString(AddressOf(stringToBePrinted[0]));
220 }
221 EndIf;
222
223 If not(isTreeNodeWithinBounds(treeNode)) Then { segmentationFault(); }
224 EndIf;
225
226 strcpy(AddressOf(treeNode->code[0]), currentCode);
227
228 Character leftCode[16] : = {0}, rightCode[16] : = {0};
229
230 strcpy(AddressOf(leftCode[0]), currentCode);
231 strcat(AddressOf(leftCode[0]), "0");
232 strcpy(AddressOf(rightCode[0]), currentCode);
233 strcat(AddressOf(rightCode[0]), "1");
234
235 If treeNode->leftChild Then {
236 assignCode(AddressOf(leftCode[0]), treeNode->leftChild);
237 }
238 EndIf;
239 If treeNode->rightChild Then {
240 assignCode(AddressOf(rightCode[0]), treeNode->rightChild);
241 }
242 EndIf;
243
244 If treeNode->character Then {
245 mapOfCodes[treeNode->character] : = AddressOf(treeNode->code[0]);
246 Character codeToPrint[32] : = {0};
247 codeToPrint[0] : = '\'';
248 codeToPrint[1] : = treeNode->character;
249 codeToPrint[2] : = '\'';
250 codeToPrint[3] : = '=';
251 codeToPrint[4] : = '>';
252 codeToPrint[5] : = 0;
253 strcat(AddressOf(codeToPrint[0]), AddressOf(treeNode->code[0]));
254 strcat(AddressOf(codeToPrint[0]), "\n");
255 printString(AddressOf(codeToPrint[0]));
256 }
257 EndIf;
258 }
259 EndFunction;
260
261 Function freeUpTheTree(PointerToTreeNode tree) Which Returns Nothing Does {
262 If tree->leftChild Then {
263 freeUpTheTree(tree->leftChild); }
266 EndIf;
267 If tree->rightChild Then { freeUpTheTree(tree->rightChild); }
268 EndIf;
269 freeTreeNode(tree);
270 }
271 EndFunction;
272
273 Decimal32 PRECISION : = 500;
274 Function ln(Decimal32 x) Which Returns Decimal32 Does {
275 Decimal32 sum : = 0, epsilon : = (x - 1) / (5 * PRECISION), i : = 1;
277 While(epsilon > 0 and i < x) or (epsilon < 0 and i > x) Loop {
278 sum += epsilon / i;
279 i += epsilon;
280 }
281 EndWhile;
282 Return sum;
283 }
284 EndFunction;
285
286 Function log2(Decimal32 x) Which Returns Decimal32 Does {
287 Return ln(x) / ln(2);
288 }
289 EndFunction;
290
291 Character input[32];
292 Character output[256];
293
294 Function main() Which Returns Nothing Does {
295 clearScreen();
296 Integer16 lengthOfInput : = getLengthOfTheInput(), i : = 0;
297 If NDEBUG = 0 Then {
298 Character stringToBePrinted[64] : = {0};
299 strcat(AddressOf(stringToBePrinted[0]),
300 "NDEBUG: The length of the input is: ");
301 convertIntegerToString(AddressOf(stringToBePrinted[0]) +
302 strlen(AddressOf(stringToBePrinted[0])),
303 lengthOfInput);
304 strcat(AddressOf(stringToBePrinted[0]), "\n");
305 printString(AddressOf(stringToBePrinted[0]));
306 }
307 EndIf;
308 While i < lengthOfInput Loop {
309 input[i] : = getCharacterOfTheInput(i);
310 i += 1;
311 }
312 EndWhile;
313 input[lengthOfInput] : = 0;
314
315 If strlen(AddressOf(input[0])) = 0 Then {
316 printString("The input is empty!\n");
317 Return;
318 }
319 EndIf;
320 PointerToTreeNode array[32];
321 Integer16 lengthOfTheArray : = 0;
322 i:
323 = 0;
324 While i < lengthOfInput Loop {
325 Integer16 j : = 0, haveWeFoundTheCharacterInTheArray : = 0;
326 While j < lengthOfTheArray Loop {
327 If array[j]->character = input[i] Then {
328 haveWeFoundTheCharacterInTheArray:
329 = 1;
330 array[j]->frequencyOfCharacter += 1;
331 }
332 EndIf;
333 j += 1;
334 }
335 EndWhile;
336 If not(haveWeFoundTheCharacterInTheArray) Then {
337 array[lengthOfTheArray] : = newTreeNode();
338 array[lengthOfTheArray]->character : = input[i];
339 array[lengthOfTheArray]->frequencyOfCharacter : = 1;
340 lengthOfTheArray += 1;
341 }
342 EndIf;
343 i += 1;
344 }
345 EndWhile;
346
347 i:
348 = 0;
349 While i < lengthOfTheArray Loop {
350 Character stringToBePrinted[64] : = {0};
351 strcat(AddressOf(stringToBePrinted[0]), "The character '");
352 Integer16 indexOfCharacter : = strlen(AddressOf(stringToBePrinted[0]));
353 stringToBePrinted[indexOfCharacter] : = array[i]->character;
354 stringToBePrinted[indexOfCharacter + 1] : = 0;
355 strcat(AddressOf(stringToBePrinted[0]), "' has the frequency of ");
356 convertIntegerToString(AddressOf(stringToBePrinted[0]) +
357 strlen(AddressOf(stringToBePrinted[0])),
358 array[i]->frequencyOfCharacter);
359 strcat(AddressOf(stringToBePrinted[0]), ".\n");
360 printString(AddressOf(stringToBePrinted[0]));
361 i += 1;
362 }
363 EndWhile;
364
365 Decimal32 ShannonEntropy : = 0;
366 i:
367 = 0;
368 While i < lengthOfTheArray Loop {
369 ShannonEntropy -=
370 (array[i]->frequencyOfCharacter / Decimal32(lengthOfInput)) *
371 log2(array[i]->frequencyOfCharacter / Decimal32(lengthOfInput));
372 i += 1;
373 }
374 EndWhile;
375 output[0] : = 0;
376 strcat(AddressOf(output[0]), "The Shannon Entropy of the input string is: ");
377 convertDecimalToString(AddressOf(output[0]) + strlen(AddressOf(output[0])),
378 ShannonEntropy);
379 strcat(AddressOf(output[0]), " bits/symbol.\n");
380 printString(AddressOf(output[0]));
381
382 While lengthOfTheArray > 1 Loop {
383 Integer16 minimum : = 0, secondMinimum : = 0;
384
385 Integer16 i : = 0;
386 If NDEBUG = 0 Then {
387 Character stringToBePrinted[64] : = {0};
388 strcat(AddressOf(stringToBePrinted[0]),
389 "NDEBUG: The length of the array is ");
390 convertIntegerToString(AddressOf(stringToBePrinted[0]) +
391 strlen(AddressOf(stringToBePrinted[0])),
392 lengthOfTheArray);
393 strcat(AddressOf(stringToBePrinted[0]), ".\n");
394 printString(AddressOf(stringToBePrinted[0]));
395 }
396 EndIf;
397 While i < lengthOfTheArray Loop {
398 If NDEBUG = 0 Then {
399 Character stringToBePrinted[64] : = {0};
400 strcat(AddressOf(stringToBePrinted[0]),
401 "NDEBUG: The tree at the index #");
402 convertIntegerToString(AddressOf(stringToBePrinted[0]) +
403 strlen(AddressOf(stringToBePrinted[0])),
404 i);
405 strcat(AddressOf(stringToBePrinted[0]), " is the TreeNode #");
406 convertIntegerToString(AddressOf(stringToBePrinted[0]) +
407 strlen(AddressOf(stringToBePrinted[0])),
408 (array[i] - AddressOf(treeNodes[0])) /
409 SizeOf(TreeNode));
410 strcat(AddressOf(stringToBePrinted[0]), ".\n");
411 printString(AddressOf(stringToBePrinted[0]));
412 }
413 EndIf;
414 If not(isTreeNodeWithinBounds(array[i])) Then {
415 segmentationFault();
416 Return;
417 }
418 EndIf;
419 i += 1;
420 }
421 EndWhile;
422
423 i:
424 = 0;
425 While i < lengthOfTheArray Loop {
426 If array[i]->frequencyOfCharacter <
427 array[minimum]->frequencyOfCharacter Then {
428 minimum:
429 = i;
430 }
431 EndIf;
432 i += 1;
433 }
434 EndWhile;
435
436 i:
437 = minimum = 0 ? 1 : 0;
438 secondMinimum:
439 = i;
440 While i < lengthOfTheArray Loop {
441 If array[i]->frequencyOfCharacter <
442 array[secondMinimum]->frequencyOfCharacter and
443 not(i = minimum) Then {
444 secondMinimum:
445 = i;
446 }
447 EndIf;
448 i += 1;
449 }
450 EndWhile;
451
452 If NDEBUG = 0 Then {
453 Character stringToBePrinted[64] : = {0};
454 strcat(AddressOf(stringToBePrinted[0]),
455 "NDEBUG: The minimum and the second minimum are ");
456 convertIntegerToString(AddressOf(stringToBePrinted[0]) +
457 strlen(AddressOf(stringToBePrinted[0])),
458 minimum);
459 strcat(AddressOf(stringToBePrinted[0]), " and ");
460 convertIntegerToString(AddressOf(stringToBePrinted[0]) +
461 strlen(AddressOf(stringToBePrinted[0])),
462 secondMinimum);
463 strcat(AddressOf(stringToBePrinted[0]), ".\n");
464 printString(AddressOf(stringToBePrinted[0]));
465 }
466 EndIf;
467
468 If NDEBUG = 0 Then {
469 Character stringToBePrinted[64] : = {0};
470 strcat(AddressOf(stringToBePrinted[0]), "NDEBUG: Joining the TreeNode #");
471 convertIntegerToString(AddressOf(stringToBePrinted[0]) +
472 strlen(AddressOf(stringToBePrinted[0])),
473 (array[minimum] - AddressOf(treeNodes[0])) /
474 SizeOf(TreeNode));
475 strcat(AddressOf(stringToBePrinted[0]), " with the TreeNode #");
476 convertIntegerToString(AddressOf(stringToBePrinted[0]) +
477 strlen(AddressOf(stringToBePrinted[0])),
478 (array[secondMinimum] - AddressOf(treeNodes[0])) /
479 SizeOf(TreeNode));
480 strcat(AddressOf(stringToBePrinted[0]), ".\n");
481 printString(AddressOf(stringToBePrinted[0]));
482 }
483 EndIf;
484
485 PointerToTreeNode sumOfTheTwoMostFrequent : = newTreeNode();
486 sumOfTheTwoMostFrequent->frequencyOfCharacter
487 : = array[minimum]->frequencyOfCharacter +
488 array[secondMinimum]->frequencyOfCharacter;
489 sumOfTheTwoMostFrequent->leftChild : = array[minimum];
490 sumOfTheTwoMostFrequent->rightChild : = array[secondMinimum];
491
492 If NDEBUG = 0 Then {
493 Character stringToBePrinted[64] : = {0};
494 strcat(AddressOf(stringToBePrinted[0]),
495 "NDEBUG: The new TreeNode has the frequency of: ");
496 convertIntegerToString(AddressOf(stringToBePrinted[0]) +
497 strlen(AddressOf(stringToBePrinted[0])),
498 sumOfTheTwoMostFrequent->frequencyOfCharacter);
499 strcat(AddressOf(stringToBePrinted[0]), ".\n");
500 printString(AddressOf(stringToBePrinted[0]));
501 }
502 EndIf;
503
504 array[minimum] : = sumOfTheTwoMostFrequent;
505
506 i:
507 = secondMinimum;
508 While i < lengthOfTheArray - 1 Loop {
509 array[i] : = array[i + 1];
510 i += 1;
511 }
512 EndWhile;
513
514 lengthOfTheArray -= 1;
515 }
516 EndWhile;
517
518 If NDEBUG = 0 Then {
519 Character stringToBePrinted[128] : = {0};
520 strcat(AddressOf(stringToBePrinted[0]),
521 "NDEBUG: The frequency of the root node is ");
522 convertIntegerToString(AddressOf(stringToBePrinted[0]) +
523 strlen(AddressOf(stringToBePrinted[0])),
524 array[0]->frequencyOfCharacter);
525 strcat(AddressOf(stringToBePrinted[0]),
526 ". If the algorithm is correctly implemented, it should be ");
527 convertIntegerToString(AddressOf(stringToBePrinted[0]) +
528 strlen(AddressOf(stringToBePrinted[0])),
529 lengthOfInput);
530 strcat(AddressOf(stringToBePrinted[0]), ".\n");
531 printString(AddressOf(stringToBePrinted[0]));
532 }
533 EndIf;
534
535 assignCode("", array[0]);
536
537 Integer16 lengthOfTheOutput : = 0;
538 i:
539 = 0;
540 While i < lengthOfInput Loop {
541 lengthOfTheOutput += strlen(mapOfCodes[input[i]]);
542 i += 1;
543 }
544 EndWhile;
545 output[0] : = 0;
546 strcat(AddressOf(output[0]), "The length of the encoded string is: ");
547 convertIntegerToString(AddressOf(output[0]) + strlen(AddressOf(output[0])),
548 lengthOfTheOutput);
549 strcat(AddressOf(output[0]), " bits.\n");
550 printString(AddressOf(output[0]));
551
552 output[0] : = 0;
553 strcat(AddressOf(output[0]),
554 "The average length of the symbol in the Huffman code is: ");
555 convertDecimalToString(AddressOf(output[0]) + strlen(AddressOf(output[0])),
556 Decimal32(lengthOfTheOutput) / lengthOfInput);
557 strcat(AddressOf(output[0]), " bits/symbol.\n");
558 printString(AddressOf(output[0]));
559
560 output[0] : = 0;
561 i:
562 = 0;
563 While i < lengthOfInput Loop {
564 strcat(AddressOf(output[0]), mapOfCodes[input[i]]);
565 i += 1;
566 }
567 EndWhile;
568 strcat(AddressOf(output[0]), "\n");
569 printString(AddressOf(output[0]));
570
571 freeUpTheTree(array[0]);
572 }
573 EndFunction;
574