comparison: huffman/huffman.cpp
huffman/huffman.cpp
- changeset 76
- 6de6d9a64ebd
- parent 8
- 8b697d30c49f
equal
deleted
inserted
replaced
| 75:5f8a03274d75 | 76:6de6d9a64ebd |
|---|---|
| 1 /* | |
| 2 * Replacement for older Skulltag Launcher Protocol's huffman.cpp | |
| 3 * | |
| 4 * Copyright 2009 Timothy Landers | |
| 5 * email: code.vortexcortex@gmail.com | |
| 6 * | |
| 7 * Permission is hereby granted, free of charge, to any person obtaining a copy | |
| 8 * of this software and associated documentation files (the "Software"), to deal | |
| 9 * in the Software without restriction, including without limitation the rights | |
| 10 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell | |
| 11 * copies of the Software, and to permit persons to whom the Software is | |
| 12 * furnished to do so, subject to the following conditions: | |
| 13 * | |
| 14 * The above copyright notice and this permission notice shall be included in | |
| 15 * all copies or substantial portions of the Software. | |
| 16 * | |
| 17 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR | |
| 18 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, | |
| 19 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE | |
| 20 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER | |
| 21 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, | |
| 22 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN | |
| 23 * THE SOFTWARE. | |
| 24 */ | |
| 25 | |
| 26 // required for atexit() | |
| 27 #include <stdlib.h> | |
| 28 #include <stdio.h> | |
| 29 | |
| 30 #include "huffman.h" | |
| 31 #include "huffcodec.h" | |
| 32 // #include "i_system.h" | |
| 33 | |
| 34 using namespace skulltag; | |
| 35 // Global Variables | |
| 36 | |
| 37 /** Reference to the HuffmanCodec Object that will perform the encoding and decoding. */ | |
| 38 static HuffmanCodec * __codec = NULL; | |
| 39 | |
| 40 // Function Implementation | |
| 41 | |
| 42 /** Creates and intitializes a HuffmanCodec Object. <br> | |
| 43 * Also arranges for HUFFMAN_Destruct() to be called upon termination. */ | |
| 44 void HUFFMAN_Construct(){ | |
| 45 | |
| 46 // The exact structure description of a Huffman tree | |
| 47 static unsigned char const compatible_huffman_tree[] = { | |
| 48 0, 0, 0, 1,128, 0, 0, 0, 3, 38, 34, 2, 1, 80, 3,110, | |
| 49 144, 67, 0, 2, 1, 74, 3,243,142, 37, 2, 3,124, 58,182, 0, | |
| 50 0, 1, 36, 0, 3,221,131, 3,245,163, 1, 35, 3,113, 85, 0, | |
| 51 1, 41, 1, 77, 3,199,130, 0, 1,206, 3,185,153, 3, 70,118, | |
| 52 0, 3, 3, 5, 0, 0, 1, 24, 0, 2, 3,198,190, 63, 2, 3, | |
| 53 139,186, 75, 0, 1, 44, 2, 3,240,218, 56, 3, 40, 39, 0, 0, | |
| 54 2, 2, 3,244,247, 81, 65, 0, 3, 9,125, 3, 68, 60, 0, 0, | |
| 55 1, 25, 3,191,138, 3, 86, 17, 0, 1, 23, 3,220,178, 2, 3, | |
| 56 165,194, 14, 1, 0, 2, 2, 0, 0, 2, 1,208, 3,150,157,181, | |
| 57 1,222, 2, 3,216,230,211, 0, 2, 2, 3,252,141, 10, 42, 0, | |
| 58 2, 3,134,135,104, 1,103, 3,187,225, 95, 32, 0, 0, 0, 0, | |
| 59 0, 0, 1, 57, 1, 61, 3,183,237, 0, 0, 3,233,234, 3,246, | |
| 60 203, 2, 3,250,147, 79, 1,129, 0, 1, 7, 3,143,136, 1, 20, | |
| 61 3,179,148, 0, 0, 0, 3, 28,106, 3,101, 87, 1, 66, 0, 3, | |
| 62 180,219, 3,227,241, 0, 1, 26, 1,251, 3,229,214, 3, 54, 69, | |
| 63 0, 0, 0, 0, 0, 3,231,212, 3,156,176, 3, 93, 83, 0, 3, | |
| 64 96,253, 3, 30, 13, 0, 0, 2, 3,175,254, 94, 3,159, 27, 2, | |
| 65 1, 8, 3,204,226, 78, 0, 0, 0, 3,107, 88, 1, 31, 3,137, | |
| 66 169, 2, 2, 3,215,145, 6, 4, 1,127, 0, 1, 99, 3,209,217, | |
| 67 0, 3,213,238, 3,177,170, 1,132, 0, 0, 0, 2, 3, 22, 12, | |
| 68 114, 2, 2, 3,158,197, 97, 45, 0, 1, 46, 1,112, 3,174,249, | |
| 69 0, 3,224,102, 2, 3,171,151,193, 0, 0, 0, 3, 15, 16, 3, | |
| 70 2,168, 1, 49, 3, 91,146, 0, 1, 48, 3,173, 29, 0, 3, 19, | |
| 71 126, 3, 92,242, 0, 0, 0, 0, 0, 0, 3,205,192, 2, 3,235, | |
| 72 149,255, 2, 3,223,184,248, 0, 0, 3,108,236, 3,111, 90, 2, | |
| 73 3,117,115, 71, 0, 0, 3, 11, 50, 0, 3,188,119, 1,122, 3, | |
| 74 167,162, 1,160, 1,133, 3,123, 21, 0, 0, 2, 1, 59, 2, 3, | |
| 75 155,154, 98, 43, 0, 3, 76, 51, 2, 3,201,116, 72, 2, 0, 2, | |
| 76 3,109,100,121, 2, 3,195,232, 18, 1, 0, 2, 0, 1,164, 2, | |
| 77 3,120,189, 73, 0, 1,196, 3,239,210, 3, 64, 62, 89, 0, 0, | |
| 78 1, 33, 2, 3,228,161, 55, 2, 3, 84,152, 47, 0, 0, 2, 3, | |
| 79 207,172,140, 3, 82,166, 0, 3, 53,105, 1, 52, 3,202,200 | |
| 80 }; | |
| 81 | |
| 82 // create a HuffmanCodec that is compatible with the previous implementation. | |
| 83 __codec = new HuffmanCodec( compatible_huffman_tree, sizeof compatible_huffman_tree ); | |
| 84 | |
| 85 // set up the HuffmanCodec to perform in a backwards compatible fashion. | |
| 86 __codec->reversedBytes( true ); | |
| 87 __codec->allowExpansion( false ); | |
| 88 | |
| 89 // request that the destruct function be called upon exit. | |
| 90 // atterm( HUFFMAN_Destruct ); | |
| 91 atexit( HUFFMAN_Destruct ); | |
| 92 } | |
| 93 | |
| 94 /** Releases resources allocated by the HuffmanCodec. */ | |
| 95 void HUFFMAN_Destruct(){ | |
| 96 delete __codec; | |
| 97 __codec = NULL; | |
| 98 } | |
| 99 | |
| 100 /** Applies Huffman encoding to a block of data. */ | |
| 101 void HUFFMAN_Encode( | |
| 102 /** in: Pointer to start of data that is to be encoded. */ | |
| 103 unsigned char const * const inputBuffer, | |
| 104 /** out: Pointer to destination buffer where encoded data will be stored. */ | |
| 105 unsigned char * const outputBuffer, | |
| 106 /** in: Number of chars to read from inputBuffer. */ | |
| 107 int const &inputBufferSize, | |
| 108 /**< in+out: Max chars to write into outputBuffer. <br> | |
| 109 * Upon return holds the number of chars stored or 0 if an error occurs. */ | |
| 110 int * outputBufferSize | |
| 111 ){ | |
| 112 int bytesWritten = __codec->encode( inputBuffer, outputBuffer, inputBufferSize, *outputBufferSize ); | |
| 113 | |
| 114 // expansion occured -- provide backwards compatibility | |
| 115 if ( bytesWritten < 0 ){ | |
| 116 // check buffer sizes | |
| 117 if ( *outputBufferSize < (inputBufferSize + 1) ){ | |
| 118 // outputBuffer too small, return "no bytes written" | |
| 119 *outputBufferSize = 0; | |
| 120 return; | |
| 121 } | |
| 122 | |
| 123 // perform the unencoded copy | |
| 124 for ( int i = 0; i < inputBufferSize; i++ ) outputBuffer[i+1] = inputBuffer[i]; | |
| 125 // supply the "unencoded" signal and bytesWritten | |
| 126 outputBuffer[0] = 0xff; | |
| 127 *outputBufferSize = inputBufferSize + 1; | |
| 128 } else { | |
| 129 // assign the bytesWritten return value | |
| 130 *outputBufferSize = bytesWritten; | |
| 131 } | |
| 132 } // end function HUFFMAN_Encode | |
| 133 | |
| 134 /** Decodes a block of data that is Huffman encoded. */ | |
| 135 void HUFFMAN_Decode( | |
| 136 unsigned char const * const inputBuffer, /**< in: Pointer to start of data that is to be decoded. */ | |
| 137 unsigned char * const outputBuffer, /**< out: Pointer to destination buffer where decoded data will be stored. */ | |
| 138 int const &inputBufferSize, /**< in: Number of chars to read from inputBuffer. */ | |
| 139 int *outputBufferSize /**< in+out: Max chars to write into outputBuffer. Upon return holds the number of chars stored or 0 if an error occurs. */ | |
| 140 ){ | |
| 141 // check for "unencoded" signal & provide backwards compatibility | |
| 142 if ((inputBufferSize > 0) && ((inputBuffer[0]&0xff) == 0xff)){ | |
| 143 // check buffer sizes | |
| 144 if ( *outputBufferSize < (inputBufferSize - 1) ){ | |
| 145 // outputBuffer too small, return "no bytes written" | |
| 146 *outputBufferSize = 0; | |
| 147 return; | |
| 148 } | |
| 149 | |
| 150 // perform the unencoded copy | |
| 151 for ( int i = 1; i < inputBufferSize; i++ ) outputBuffer[i-1] = inputBuffer[i]; | |
| 152 | |
| 153 // supply the bytesWritten | |
| 154 *outputBufferSize = inputBufferSize - 1; | |
| 155 } else { | |
| 156 // decode the data | |
| 157 *outputBufferSize = __codec->decode( inputBuffer, outputBuffer, inputBufferSize, *outputBufferSize ); | |
| 158 } | |
| 159 } // end function HUFFMAN_Decode |
