1 #target WASI // So that we can target Firefox 52.
   2 
   3 Function noMoreFreeMemory() Which Returns Nothing Is External;
   4 Function segmentationFault() Which Returns Nothing Is External;
   5 Function
   6 printString(PointerToCharacter string) Which Returns Nothing Is External;
   7 Function clearScreen() Which Returns Nothing Is External;
   8 Function getLengthOfTheInput() Which Returns Integer16 Is External;
   9 Function
  10 getCharacterOfTheInput(Integer16 index) Which Returns Character Is External;
  11 Function setDiagramWidth(Integer32 width) Which Returns Nothing Is External;
  12 Function setDiagramHeight(Integer32 height) Which Returns Nothing Is External;
  13 Function drawLine(Integer32 x1, Integer32 y1, Integer32 x2,
  14                   Integer32 y2) Which Returns Nothing Is External;
  15 Function drawRectangle(Integer32 x, Integer32 y, Integer32 width,
  16                        Integer32 height) Which Returns Nothing Is External;
  17 Function drawText(Integer32 x, Integer32 y,
  18                   PointerToCharacter text) Which Returns Nothing Is External;
  19 
  20 Integer32 NDEBUG := 1,
  21                  MAINTAIN_COMPATIBILITY_WITH_JAVASCRIPT_IMPLEMENTATION := 1;
  22 // The JavaScript implementation is available here:
  23 // https://flatassembler.github.io/huffman.html
  24 
  25 Structure TreeNode Consists Of
  26   Character character;
  27   Integer16 frequencyOfCharacter;
  28   PointerToTreeNode leftChild, rightChild;
  29   Character code[16];
  30   Integer32 x, y;
  31 EndStructure
  32 
  33 InstantiateStructure TreeNode treeNodes[64];
  34 Integer16 isTreeNodeUsed[64];
  35 
  36 Function isTreeNodeWithinBounds(
  37     PointerToTreeNode treeNode) Which Returns Integer32 Does
  38   Return AddressOf(treeNodes[0]) <= treeNode <= AddressOf(treeNodes[64 - 1]) and
  39       mod(treeNode - AddressOf(treeNodes[0]), SizeOf(TreeNode)) =
  40       0; // In C, testing whether the mod is equal to 0 would not be necessary,
  41          // but, since AEC supports unaligned access, it is necessary here.
  42 EndFunction
  43 
  44 Function
  45 convertIntegerToString(PointerToCharacter string,
  46                        Integer32 integer) Which Returns Nothing Is Declared;
  47 Function appendIntegerToString(PointerToCharacter string, Integer32 integer)
  48                        Which Returns Nothing Is Declared;
  49 Function strcat(PointerToCharacter dest,
  50                 PointerToCharacter src) Which Returns Nothing Is Declared;
  51 Function strlen(PointerToCharacter string) Which Returns Integer32 Is Declared;
  52 
  53 Function newTreeNode() Which Returns PointerToTreeNode Does
  54   Integer16 i := 0;
  55   While i < 64 Loop 
  56     If not(isTreeNodeUsed[i]) Then
  57       treeNodes[i].character := 0;
  58       treeNodes[i].leftChild := treeNodes[i].rightChild
  59           := PointerToTreeNode(0);
  60       treeNodes[i].code[0] := 0;
  61       treeNodes[i].frequencyOfCharacter := 0;
  62       isTreeNodeUsed[i] := 1;
  63       If NDEBUG = 0 Then
  64         Character stringToBePrinted[64] := {0};
  65         strcat(AddressOf(stringToBePrinted[0]),
  66                "NDEBUG: Allocating the TreeNode #");
  67         appendIntegerToString(AddressOf(stringToBePrinted[0]),
  68                                i);
  69         strcat(AddressOf(stringToBePrinted[0]), "\n");
  70         printString(AddressOf(stringToBePrinted[0]));
  71       EndIf
  72       Return AddressOf(treeNodes[i]);
  73     EndIf
  74     i += 1;
  75   EndWhile
  76   noMoreFreeMemory();
  77 EndFunction
  78 
  79 Function freeTreeNode(PointerToTreeNode treeNode) Which Returns Nothing Does
  80   If not(isTreeNodeWithinBounds(treeNode)) Then
  81     segmentationFault();
  82   EndIf
  83   If NDEBUG = 0 Then
  84     Character stringToBePrinted[64] := {0};
  85     strcat(AddressOf(stringToBePrinted[0]), "NDEBUG: Freeing the TreeNode #");
  86     appendIntegerToString(AddressOf(stringToBePrinted[0]),
  87                            (treeNode - AddressOf(treeNodes[0])) /
  88                                SizeOf(TreeNode));
  89     strcat(AddressOf(stringToBePrinted[0]), "\n");
  90     printString(AddressOf(stringToBePrinted[0]));
  91   EndIf
  92   isTreeNodeUsed[(treeNode - AddressOf(treeNodes[0])) / SizeOf(TreeNode)] := 0;
  93 EndFunction
  94 
  95 Function getHeight(PointerToTreeNode node) Which Returns Integer32 Does 
  96   If not(node) Then 
  97     Return 0; 
  98   EndIf
  99   Integer32 max := 0;
 100   If getHeight(node->leftChild) > max Then
 101     max := getHeight(node->leftChild);
 102   EndIf
 103   If getHeight(node->rightChild) > max Then
 104     max := getHeight(node->rightChild);
 105   EndIf
 106   Return max + 1;
 107 EndFunction
 108 
 109 Function strlen(PointerToCharacter str) Which Returns Integer32 Does
 110   If str = 0 Then
 111     Return 0;
 112   EndIf
 113   Integer32 length := 0;
 114   While ValueAt(str + length) Loop
 115     length += 1;
 116   EndWhile
 117   Return length;
 118 EndFunction
 119 
 120 Function strncmp(PointerToCharacter first, PointerToCharacter second,
 121                  Integer32 n) Which Returns Integer32 Does
 122   If first = 0 or second = 0 Then
 123     Return 1;
 124   EndIf
 125   Integer32 iterator := 0;
 126   While iterator < n Loop
 127     If ValueAt(first + iterator) = ValueAt(second + iterator) Then
 128       iterator += 1;
 129     Else 
 130       Return ValueAt(first + iterator) - ValueAt(second + iterator);
 131     EndIf
 132   EndWhile
 133   Return 0;
 134 EndFunction
 135 
 136 Function strcpy(PointerToCharacter dest,
 137                 PointerToCharacter src) Which Returns Nothing Does
 138   While ValueAt(src) Loop
 139     ValueAt(dest) := ValueAt(src);
 140     dest += 1;
 141     src += 1;
 142   EndWhile
 143   ValueAt(dest) := 0;
 144 EndFunction
 145 
 146 Function strcat(PointerToCharacter dest,
 147                 PointerToCharacter src) Which Returns Nothing Does
 148   strcpy(dest + strlen(dest), src);
 149 EndFunction
 150 
 151 Function reverseString(PointerToCharacter string) Which Returns Nothing Does
 152   PointerToCharacter pointerToLastCharacter := string + strlen(string) - 1;
 153   While pointerToLastCharacter - string > 0 Loop
 154     Character tmp := ValueAt(string);
 155     ValueAt(string) := ValueAt(pointerToLastCharacter);
 156     ValueAt(pointerToLastCharacter) := tmp;
 157     string += 1;
 158     pointerToLastCharacter -= 1;
 159   EndWhile
 160 EndFunction
 161 
 162 Function convertIntegerToString(PointerToCharacter string,
 163                                 Integer32 number) Which Returns Nothing Does
 164   Integer32 isNumberNegative := 0;
 165   If number < 0 Then
 166     number *= -1;
 167     isNumberNegative := 1;
 168   EndIf
 169   Integer32 i := 0;
 170   While number >= 10 Loop
 171     ValueAt(string + i) := '0' + mod(number, 10);
 172     number /= 10;
 173     i += 1;
 174   EndWhile
 175   ValueAt(string + i) := '0' + number;
 176   i += 1;
 177   If isNumberNegative Then
 178     ValueAt(string + i) := '-';
 179     i += 1;
 180   EndIf
 181   ValueAt(string + i) := 0;
 182   reverseString(string);
 183 EndFunction
 184 
 185 Function appendIntegerToString(PointerToCharacter string,
 186                                Integer32 number) Which Returns Nothing Does
 187   convertIntegerToString(string + strlen(string), number);
 188 EndFunction
 189 
 190 Function convertDecimalToString(PointerToCharacter string,
 191                                 Decimal32 number) Which Returns Nothing Does 
 192   convertIntegerToString(string, number);
 193   number -= Integer32(number);
 194   If number < 0 Then
 195     number *= -1; 
 196   EndIf
 197   If number = 0 Then 
 198     Return;
 199   EndIf
 200   strcat(string, ".");
 201   Integer16 numberOfDecimals := 0;
 202   While numberOfDecimals < 3 and number > 0 Loop
 203     numberOfDecimals += 1;
 204     number *= 10;
 205     Character stringWithTheNewDigit[2];
 206     stringWithTheNewDigit[0] := stringWithTheNewDigit[1] := 0;
 207     stringWithTheNewDigit[0] := '0' + number;
 208     strcat(string, AddressOf(stringWithTheNewDigit[0]));
 209     number -= Integer32(number);
 210   EndWhile
 211 EndFunction
 212 
 213 PointerToCharacter mapOfCodes[256];
 214 
 215 Function assignCode(PointerToCharacter currentCode,
 216                     PointerToTreeNode treeNode) Which Returns Nothing Does
 217   If NDEBUG = 0 Then
 218     Character stringToBePrinted[64] := {0};
 219     strcat(AddressOf(stringToBePrinted[0]), "NDEBUG: Assigning the code \"");
 220     strcat(AddressOf(stringToBePrinted[0]), currentCode);
 221     strcat(AddressOf(stringToBePrinted[0]), "\" to the TreeNode #");
 222     appendIntegerToString(AddressOf(stringToBePrinted[0]),
 223                            (treeNode - AddressOf(treeNodes[0])) /
 224                                SizeOf(TreeNode));
 225     strcat(AddressOf(stringToBePrinted[0]), ".\n");
 226     printString(AddressOf(stringToBePrinted[0]));
 227 
 228     stringToBePrinted[0] := 0;
 229     strcat(AddressOf(stringToBePrinted[0]),
 230            "NDEBUG: Its left child is the TreeNode #");
 231     If treeNode->leftChild Then
 232       appendIntegerToString(AddressOf(stringToBePrinted[0]),
 233                              (treeNode->leftChild - AddressOf(treeNodes[0])) /
 234                                  SizeOf(TreeNode));
 235     Else
 236       strcat(AddressOf(stringToBePrinted[0]), "null");
 237     EndIf
 238     strcat(AddressOf(stringToBePrinted[0]), ".\n");
 239     printString(AddressOf(stringToBePrinted[0]));
 240 
 241     stringToBePrinted[0] := 0;
 242     strcat(AddressOf(stringToBePrinted[0]),
 243            "NDEBUG: Its right child is the TreeNode #");
 244     If treeNode->leftChild Then
 245       appendIntegerToString(AddressOf(stringToBePrinted[0]),
 246                              (treeNode->rightChild - AddressOf(treeNodes[0])) /
 247                                  SizeOf(TreeNode));
 248     Else
 249       strcat(AddressOf(stringToBePrinted[0]), "null");
 250     EndIf
 251     strcat(AddressOf(stringToBePrinted[0]), ".\n");
 252     printString(AddressOf(stringToBePrinted[0]));
 253   EndIf
 254 
 255   If not(isTreeNodeWithinBounds(treeNode)) Then segmentationFault(); EndIf
 256 
 257   strcpy(AddressOf(treeNode->code[0]), currentCode);
 258 
 259   Character leftCode[16] := {0}, rightCode[16] := {0};
 260 
 261   strcpy(AddressOf(leftCode[0]), currentCode);
 262   strcat(AddressOf(leftCode[0]), "0");
 263   strcpy(AddressOf(rightCode[0]), currentCode);
 264   strcat(AddressOf(rightCode[0]), "1");
 265 
 266   If treeNode->leftChild Then
 267     assignCode(AddressOf(leftCode[0]), treeNode->leftChild);
 268   EndIf
 269   If treeNode->rightChild Then
 270     assignCode(AddressOf(rightCode[0]), treeNode->rightChild);
 271   EndIf
 272 
 273   If treeNode->character Then
 274     mapOfCodes[treeNode->character] := AddressOf(treeNode->code[0]);
 275     Character codeToPrint[32] := {
 276       '\'',
 277       treeNode->character,
 278       '\'',
 279       '=',
 280       '>',
 281       0,
 282     };
 283     strcat(AddressOf(codeToPrint[0]), AddressOf(treeNode->code[0]));
 284     strcat(AddressOf(codeToPrint[0]), "\n");
 285     printString(AddressOf(codeToPrint[0]));
 286   EndIf
 287 EndFunction
 288 
 289 Function freeUpTheTree(PointerToTreeNode tree) Which Returns Nothing Does
 290   If tree->leftChild Then
 291     freeUpTheTree(tree->leftChild); // Calling `freeTreeNode` here instead of
 292                                     // `freeUpTheTree` causes a memory leak.
 293   EndIf
 294   If tree->rightChild Then
 295     freeUpTheTree(tree->rightChild);
 296   EndIf
 297   freeTreeNode(tree);
 298 EndFunction
 299 
 300 Decimal32 PRECISION := 500;
 301 Function ln(Decimal32 x) Which Returns Decimal32 Does
 302   // Natural logarithm is the integral of 1/x from 1 to x, highschool math.
 303   Decimal32 sum := 0, epsilon := (x - 1) / (5 * PRECISION), i := 1;
 304   While epsilon > 0 and i < x or epsilon < 0 and i > x Loop
 305     sum += epsilon / i;
 306     i += epsilon;
 307   EndWhile
 308   Return sum;
 309 EndFunction
 310 
 311 Function log2(Decimal32 x) Which Returns Decimal32 Does
 312   Return ln(x) / ln(2);
 313 EndFunction
 314 
 315 Character input[64];
 316 Character output[256];
 317 
 318 Function getAddressOfTheOutput() Which Returns PointerToCharacter
 319     Does   // To be invoked by the `automaticTest.js` file in the
 320            // `HuffmanCodingInAEC` folder (that file is supposed to be run in
 321            // NodeJS) when the `main` function finishes executing, to compare
 322            // the Huffman coding stored in `output` with the known good
 323            // encodings for test strings.
 324   Return AddressOf(output[0]);
 325 EndFunction;
 326 
 327 Function shl(Integer32 first_number,
 328              Integer32 second_number) Which Returns Integer32 Does
 329   Return asm_i32(R"WebAssembly(
 330 (i32.shl
 331 	(i32.load %first_number)
 332 	(i32.load %second_number)
 333 )
 334 )WebAssembly");
 335 EndFunction
 336 
 337 Structure Maxima Consists Of
 338   Integer32 minimumX, maximumX;
 339 EndStructure
 340 Integer32 minimumX, maximumX;
 341 
 342 Function
 343 findMinimumAndMaximumX(PointerToTreeNode node,
 344                        PointerToMaxima maxima) Which Returns Nothing Does
 345   If node->x < maxima->minimumX Then
 346     maxima->minimumX := node->x;
 347   EndIf
 348   If node->x > maxima->maximumX Then
 349     maxima->maximumX := node->x;
 350   EndIf
 351 
 352   If node->rightChild Then
 353     findMinimumAndMaximumX(node->rightChild, maxima);
 354   EndIf
 355   If node->leftChild Then 
 356     findMinimumAndMaximumX(node->leftChild, maxima);
 357   EndIf
 358 EndFunction
 359 
 360 Function setCoordinates(PointerToTreeNode node, Integer32 x, Integer32 y,
 361                         Integer32 space) Which Returns Nothing Does
 362   node->x := x;
 363   node->y := y;
 364   If node->leftChild Then
 365     Integer32 newX := x - space - 10;
 366     While 1 Loop
 367       newX += 10;
 368       setCoordinates(node->leftChild, newX, y + 75,
 369                      20 * shl(1, getHeight(node->leftChild) - 1));
 370       InstantiateStructure Maxima localMaxima;
 371       localMaxima.maximumX := localMaxima.minimumX := newX;
 372       findMinimumAndMaximumX(node->leftChild, AddressOf(localMaxima));
 373       If x - localMaxima.maximumX <= 60 Then 
 374         Break;
 375       EndIf
 376     EndWhile
 377   EndIf
 378   If node->rightChild Then
 379     Integer32 newX := x + space + 10;
 380     While 1 Loop
 381       newX -= 10;
 382       setCoordinates(node->rightChild, newX, y + 75,
 383                      20 * shl(1, getHeight(node->rightChild) - 1));
 384       InstantiateStructure Maxima localMaxima;
 385       localMaxima.maximumX := localMaxima.minimumX := newX;
 386       findMinimumAndMaximumX(node->rightChild, AddressOf(localMaxima));
 387       If localMaxima.minimumX - x <= 40 Then
 388         Break;
 389       EndIf
 390     EndWhile
 391   EndIf
 392 EndFunction
 393 
 394 Function drawTree(PointerToTreeNode node) Which Returns Nothing Does
 395   drawRectangle(node->x - minimumX, node->y, 50, 50);
 396   If node->character Then
 397     Character output[4] := {'\'', node->character, '\'', 0};
 398     drawText(node->x + 5 - minimumX, node->y + 20, AddressOf(output[0]));
 399   EndIf
 400   Character output[8];
 401   output[0] := 0;
 402   convertIntegerToString(AddressOf(output[0]), node->frequencyOfCharacter);
 403   strcat(AddressOf(output[0]), "/");
 404   appendIntegerToString(AddressOf(output[0]), getLengthOfTheInput());
 405   drawText(node->x + 5 - minimumX, node->y + 40, AddressOf(output[0]));
 406   If node->leftChild Then
 407     drawText(node->x - minimumX - 10, node->y + 60, "0");
 408     drawLine(
 409              x1 := node->x + 25 - minimumX,
 410              x2 := node->x + 25 - minimumX,
 411              y1 := node->y + 50,
 412              y2 := node->y + 50 + 13,
 413             );
 414     drawLine(
 415              x1 := node->x + 25 - minimumX,
 416              x2 := node->leftChild->x + 25 - minimumX,
 417              y1 := node->y + 50 + 13,
 418              y2 := node->y + 50 + 13,
 419             );
 420     drawLine(
 421              x1 := node->leftChild->x + 25 - minimumX,
 422              x2 := node->leftChild->x + 25 - minimumX,
 423              y1 := node->y + 50 + 13,
 424              y2 := node->leftChild->y,
 425             );
 426     drawTree(node->leftChild);
 427   EndIf
 428   If node->rightChild Then
 429     drawText(node->x - minimumX + 50, node->y + 60, "1");
 430     drawLine(x1 := node->x + 25 - minimumX,
 431              y1 := node->y + 50,
 432              x2 := node->x + 25 - minimumX,
 433              y2 := node->y + 50 + 13);
 434     drawLine(x1 := node->x + 25 - minimumX,
 435              y1 := node->y + 50 + 13,
 436              x2 := node->rightChild->x + 25 - minimumX,
 437              y2 := node->y + 50 + 13);
 438     drawLine(x1 := node->rightChild->x + 25 - minimumX,
 439              y1 := node->y + 50 + 13,
 440              x2 := node->rightChild->x + 25 - minimumX,
 441              y2 := node->rightChild->y);
 442     drawTree(node->rightChild);
 443   EndIf
 444 EndFunction
 445 
 446 Function main() Which Returns Nothing Does
 447   clearScreen();
 448   Integer16 lengthOfInput := getLengthOfTheInput(), i := 0;
 449   If NDEBUG = 0 Then
 450     Character stringToBePrinted[64] := {0};
 451     strcat(AddressOf(stringToBePrinted[0]),
 452            "NDEBUG: The length of the input is: ");
 453     appendIntegerToString(AddressOf(stringToBePrinted[0]),
 454                            lengthOfInput);
 455     strcat(AddressOf(stringToBePrinted[0]), "\n");
 456     printString(AddressOf(stringToBePrinted[0]));
 457   EndIf
 458   While i < lengthOfInput Loop
 459     input[i] := getCharacterOfTheInput(i);
 460     i += 1;
 461   EndWhile
 462   input[lengthOfInput] := 0;
 463 
 464   If strlen(AddressOf(input[0])) = 0 Then
 465     printString("The input is empty!\n");
 466     Return;
 467   EndIf
 468 
 469   i := 0;
 470   While i < 256 Loop
 471     mapOfCodes[i] := PointerToCharacter(0);
 472     i += 1;
 473   EndWhile
 474 
 475   PointerToTreeNode array[32];
 476   Integer16 lengthOfTheArray := 0;
 477   i := 0;
 478   While i < lengthOfInput Loop
 479     Integer16 j := 0, haveWeFoundTheCharacterInTheArray := 0;
 480     While j < lengthOfTheArray Loop
 481       If array[j]->character = input[i] Then
 482         haveWeFoundTheCharacterInTheArray := 1;
 483         array[j]->frequencyOfCharacter += 1;
 484       EndIf
 485       j += 1;
 486     EndWhile
 487     If not(haveWeFoundTheCharacterInTheArray) Then
 488       array[lengthOfTheArray] := newTreeNode();
 489       array[lengthOfTheArray]->character := input[i];
 490       array[lengthOfTheArray]->frequencyOfCharacter := 1;
 491       lengthOfTheArray += 1;
 492     EndIf
 493     i += 1;
 494   EndWhile
 495 
 496   i := 0;
 497   While i < lengthOfTheArray Loop
 498     Character stringToBePrinted[64] := {0};
 499     strcat(AddressOf(stringToBePrinted[0]), "The character '");
 500     Integer16 indexOfCharacter := strlen(AddressOf(stringToBePrinted[0]));
 501     stringToBePrinted[indexOfCharacter] := array[i]->character;
 502     stringToBePrinted[indexOfCharacter + 1] := 0;
 503     strcat(AddressOf(stringToBePrinted[0]), "' has the frequency of ");
 504     appendIntegerToString(AddressOf(stringToBePrinted[0]),
 505                            array[i]->frequencyOfCharacter);
 506     strcat(AddressOf(stringToBePrinted[0]), ".\n");
 507     printString(AddressOf(stringToBePrinted[0]));
 508     i += 1;
 509   EndWhile
 510 
 511   Decimal32 ShannonEntropy := 0;
 512   i := 0;
 513   While i < lengthOfTheArray Loop
 514     ShannonEntropy -=
 515         (array[i]->frequencyOfCharacter / Decimal32(lengthOfInput)) *
 516         log2(array[i]->frequencyOfCharacter / Decimal32(lengthOfInput));
 517     i += 1;
 518   EndWhile
 519   output[0] := 0;
 520   strcat(AddressOf(output[0]), "The Shannon Entropy of the input string is: ");
 521   convertDecimalToString(AddressOf(output[0]) + strlen(AddressOf(output[0])),
 522                          ShannonEntropy);
 523   strcat(AddressOf(output[0]), " bits/symbol.\n");
 524   printString(AddressOf(output[0]));
 525 
 526   While lengthOfTheArray > 1 Loop
 527     Integer16 minimum := 0, secondMinimum := 0;
 528 
 529     Integer16 i := 0;
 530     If NDEBUG = 0 Then
 531       Character stringToBePrinted[64] := {0};
 532       strcat(AddressOf(stringToBePrinted[0]),
 533              "NDEBUG: The length of the array is ");
 534       appendIntegerToString(AddressOf(stringToBePrinted[0]),
 535                              lengthOfTheArray);
 536       strcat(AddressOf(stringToBePrinted[0]), ".\n");
 537       printString(AddressOf(stringToBePrinted[0]));
 538     EndIf
 539     While i < lengthOfTheArray Loop
 540       If NDEBUG = 0 Then
 541         Character stringToBePrinted[64] := {0};
 542         strcat(AddressOf(stringToBePrinted[0]),
 543                "NDEBUG: The tree at the index #");
 544         appendIntegerToString(AddressOf(stringToBePrinted[0]),
 545                                i);
 546         strcat(AddressOf(stringToBePrinted[0]), " is the TreeNode #");
 547         appendIntegerToString(AddressOf(stringToBePrinted[0]),
 548                                (array[i] - AddressOf(treeNodes[0])) /
 549                                    SizeOf(TreeNode));
 550         strcat(AddressOf(stringToBePrinted[0]), ".\n");
 551         printString(AddressOf(stringToBePrinted[0]));
 552       EndIf
 553       If not(isTreeNodeWithinBounds(array[i])) Then
 554         segmentationFault();
 555         asm("unreachable");
 556       EndIf
 557       i += 1;
 558     EndWhile
 559 
 560     i := 0;
 561     While i < lengthOfTheArray Loop
 562       If array[i]->frequencyOfCharacter <
 563           array[minimum]->frequencyOfCharacter Then
 564         minimum := i;
 565       EndIf
 566       i += 1;
 567     EndWhile
 568 
 569     i := minimum = 0 ? 1 : 0;
 570     secondMinimum := i;
 571     While i < lengthOfTheArray Loop
 572       If array[i]->frequencyOfCharacter <
 573               array[secondMinimum]->frequencyOfCharacter and
 574           not(i = minimum) Then
 575         secondMinimum := i;
 576       EndIf
 577       i += 1;
 578     EndWhile
 579 
 580     If NDEBUG = 0 Then
 581       Character stringToBePrinted[64] := {0};
 582       strcat(AddressOf(stringToBePrinted[0]),
 583              "NDEBUG: The minimum and the second minimum are ");
 584       appendIntegerToString(AddressOf(stringToBePrinted[0]),
 585                              minimum);
 586       strcat(AddressOf(stringToBePrinted[0]), " and ");
 587       appendIntegerToString(AddressOf(stringToBePrinted[0]),
 588                              secondMinimum);
 589       strcat(AddressOf(stringToBePrinted[0]), ".\n");
 590       printString(AddressOf(stringToBePrinted[0]));
 591     EndIf
 592 
 593     If NDEBUG = 0 Then
 594       Character stringToBePrinted[64] := {0};
 595       strcat(AddressOf(stringToBePrinted[0]), "NDEBUG: Joining the TreeNode #");
 596       appendIntegerToString(AddressOf(stringToBePrinted[0]),
 597                              (array[minimum] - AddressOf(treeNodes[0])) /
 598                                  SizeOf(TreeNode));
 599       strcat(AddressOf(stringToBePrinted[0]), " with the TreeNode #");
 600       appendIntegerToString(AddressOf(stringToBePrinted[0]),
 601                              (array[secondMinimum] - AddressOf(treeNodes[0])) /
 602                                  SizeOf(TreeNode));
 603       strcat(AddressOf(stringToBePrinted[0]), ".\n");
 604       printString(AddressOf(stringToBePrinted[0]));
 605     EndIf
 606 
 607     PointerToTreeNode sumOfTheTwoMostFrequent := newTreeNode();
 608     sumOfTheTwoMostFrequent->frequencyOfCharacter
 609          := array[minimum]->frequencyOfCharacter +
 610             array[secondMinimum]->frequencyOfCharacter;
 611     sumOfTheTwoMostFrequent->leftChild := array[minimum];
 612     sumOfTheTwoMostFrequent->rightChild := array[secondMinimum];
 613 
 614     If NDEBUG = 0 Then
 615       Character stringToBePrinted[64] := {0};
 616       strcat(AddressOf(stringToBePrinted[0]),
 617              "NDEBUG: The new TreeNode has the frequency of: ");
 618       appendIntegerToString(AddressOf(stringToBePrinted[0]),
 619                              sumOfTheTwoMostFrequent->frequencyOfCharacter);
 620       strcat(AddressOf(stringToBePrinted[0]), ".\n");
 621       printString(AddressOf(stringToBePrinted[0]));
 622     EndIf
 623 
 624     If not(MAINTAIN_COMPATIBILITY_WITH_JAVASCRIPT_IMPLEMENTATION) Then
 625       array[minimum] := sumOfTheTwoMostFrequent;
 626     EndIf
 627 
 628     // Delete the second minimum from the array...
 629     i := secondMinimum;
 630     While i < lengthOfTheArray - 1 Loop
 631       array[i] := array[i + 1];
 632       i += 1;
 633     EndWhile
 634     lengthOfTheArray -= 1;
 635     If not(MAINTAIN_COMPATIBILITY_WITH_JAVASCRIPT_IMPLEMENTATION) Then
 636       Continue;
 637     EndIf
 638     // Delete the first minimum from the array...
 639     If minimum >
 640         secondMinimum Then   // If the first minimum moved while we were
 641                              // deleting the second minimum from the array.
 642       minimum -= 1;
 643     EndIf
 644     i := minimum;
 645     While i < lengthOfTheArray - 1 Loop
 646       array[i] := array[i + 1];
 647       i += 1;
 648     EndWhile
 649     array[lengthOfTheArray - 1] := sumOfTheTwoMostFrequent;
 650   EndWhile
 651 
 652   If NDEBUG = 0 Then
 653     Character stringToBePrinted[128] := {0};
 654     strcat(AddressOf(stringToBePrinted[0]),
 655            "NDEBUG: The frequency of the root node is ");
 656     appendIntegerToString(AddressOf(stringToBePrinted[0]),
 657                            array[0]->frequencyOfCharacter);
 658     strcat(AddressOf(stringToBePrinted[0]),
 659            ". If the algorithm is correctly implemented, it should be ");
 660     appendIntegerToString(AddressOf(stringToBePrinted[0]),
 661                            lengthOfInput);
 662     strcat(AddressOf(stringToBePrinted[0]), ".\n");
 663     printString(AddressOf(stringToBePrinted[0]));
 664   EndIf
 665 
 666   printString("The tree has been constructed, let us assign Huffman codes to "
 667               "characters:\n");
 668   assignCode("", array[0]);
 669 
 670   Integer16 lengthOfTheOutput := 0;
 671   i := 0;
 672   While i < lengthOfInput Loop
 673     lengthOfTheOutput += strlen(mapOfCodes[input[i]]);
 674     i += 1;
 675   EndWhile
 676   output[0] := 0;
 677   strcat(AddressOf(output[0]), "The length of the encoded string is: ");
 678   appendIntegerToString(AddressOf(output[0]), lengthOfTheOutput);
 679   strcat(AddressOf(output[0]), " bits.\n");
 680   printString(AddressOf(output[0]));
 681 
 682   output[0] := 0;
 683   strcat(AddressOf(output[0]),
 684          "The average length of the symbol in the Huffman code is: ");
 685   convertDecimalToString(AddressOf(output[0]) + strlen(AddressOf(output[0])),
 686                          Decimal32(lengthOfTheOutput) / lengthOfInput);
 687   strcat(AddressOf(output[0]), " bits/symbol.\n");
 688   printString(AddressOf(output[0]));
 689 
 690   output[0] := 0;
 691   i := 0;
 692   While i < lengthOfInput Loop
 693     strcat(AddressOf(output[0]), mapOfCodes[input[i]]);
 694     i += 1;
 695   EndWhile
 696   strcat(AddressOf(output[0]), "\n");
 697   printString("The Huffman code of the input is:\n");
 698   printString(AddressOf(output[0]));
 699 
 700   setCoordinates(array[0], 0, 0, 10 * shl(1, getHeight(array[0])));
 701   InstantiateStructure Maxima globalMaxima;
 702   globalMaxima.minimumX := globalMaxima.maximumX := 0;
 703   findMinimumAndMaximumX(array[0], AddressOf(globalMaxima));
 704   minimumX := globalMaxima.minimumX;
 705   maximumX := globalMaxima.maximumX;
 706   drawTree(array[0]);
 707   setDiagramWidth(maximumX - minimumX + 55);
 708   setDiagramHeight(getHeight(array[0]) * 75);
 709 
 710   freeUpTheTree(array[0]);
 711 
 712   Character stringToBePrinted[64] := {0};
 713   strcat(AddressOf(stringToBePrinted[0]), "Decoding the output...\n");
 714   printString(AddressOf(stringToBePrinted[0]));
 715 
 716   Integer16 j := 0, k := 0;
 717   While j < strlen(AddressOf(output[0])) - 1 Loop
 718     i := 0;
 719     If NDEBUG = 0 Then
 720       printString(
 721           "NDEBUG: We are entering the loop for decoding the output!\n");
 722     EndIf
 723     While (mapOfCodes[i] = 0 or strncmp(AddressOf(output[j]), mapOfCodes[i],
 724                                        strlen(mapOfCodes[i]))) and
 725         i < 256 Loop
 726       If NDEBUG = 0 Then
 727         If mapOfCodes[i] = 0 Then
 728           printString("NDEBUG: Skipping the character because it's NULL.\n");
 729         Else
 730           printString(
 731               "NDEBUG: Skipping the character because it doesn't match!\n");
 732         EndIf
 733       EndIf
 734       i += 1;
 735     EndWhile
 736     If i = 256 Then
 737       printString("ERROR: Cannot find the beginning of the current string in "
 738                   "the map of codes!\n");
 739       Return;
 740     EndIf
 741     stringToBePrinted[0] := 0;
 742     strcat(AddressOf(stringToBePrinted[0]), mapOfCodes[i]);
 743     strcat(AddressOf(stringToBePrinted[0]), "=>");
 744     Character stringToBeAdded[5] := {'\'', i, '\'', '\n', 0};
 745     strcat(AddressOf(stringToBePrinted[0]), AddressOf(stringToBeAdded[0]));
 746     printString(AddressOf(stringToBePrinted[0]));
 747     j += strlen(mapOfCodes[i]);
 748     If not(i = getCharacterOfTheInput(k)) Then
 749       printString("ERROR: The decoded output does not match the input!\n");
 750       Break;
 751     EndIf
 752     k += 1;
 753   EndWhile
 754 EndFunction
 755