00001 // /// // Mx clientSDK 00002 // ///// //// Mx Crossplatform Client Library 00003 // /// XXX XXX /// 00004 // /// XXX XXX /// $RCSfile: mxcpcHuffmanTree.h,v $ 00005 // /// XXX /// $Revision: 1.3 $ 00006 // /// XXX XXX /// $Date: 2005/12/09 15:33:45 $ 00007 // //// XXX XXX //// $Author: cvs-kai $ 00008 // //// //// 00009 // //// M O B O T I X //////////////////////////////////////////////// 00010 // //// Security Vision Systems ////////////////////////////////////////////// 00011 // // 00012 // Copyright (C) 2005 - 2006, MOBOTIX AG, Germany // 00013 // This software is made available under the BSD licence. Please refer // 00014 // to the file LICENCE.TXT contained in this distribution for details. // 00015 // // 00016 // ///////////////////////////////////////////////////////////////////// 00017 00018 00019 00020 #ifndef __MXCPC_HUFFMANTREE_H__ 00021 #define __MXCPC_HUFFMANTREE_H__ 00022 00023 00024 00025 00026 //! Huffman tree with <tt>unsigned char</tt> valued leaves - used for 00027 //! <tt>MxPEG</tt> decoding. 00028 /*! 00029 * \ingroup mxcpc_core 00030 */ 00031 class mxcpcHuffmanTree { 00032 00033 public: 00034 struct Node { 00035 Node *Child0, *Child1; 00036 bool IsLeaf; 00037 unsigned char Value; 00038 }; 00039 00040 private: 00041 Node *RootNode; 00042 Node *GroundNode; 00043 00044 public: 00045 mxcpcHuffmanTree(); 00046 ~mxcpcHuffmanTree(); 00047 00048 public: 00049 //! Returns the Huffman tree's root node. 00050 const Node *getRoot(void); 00051 00052 //! Clears the Huffman tree. 00053 void clear(void); 00054 //! Reconfigures the Huffman tree as specified in the given table 00055 //! (JPEG Huffman table format). 00056 /*! 00057 * Returns <tt>false</tt> on success, and <tt>true</tt> otherwise. 00058 * In case of failue, the tree is cleared. 00059 */ 00060 bool configureFromTable(const unsigned char *table, int max_path_len = 16); 00061 //! Adds a leaf that is reached from the root via a path of length 00062 //! <tt>path_len</tt> bits. 00063 /*! 00064 * Returns <tt>false</tt> on success, and <tt>true</tt> otherwise. 00065 * In any case the tree remains in defined state. 00066 */ 00067 bool addLeaf(int path_len, unsigned char value); 00068 //! Returns the number of leaves in the tree. 00069 int countLeaves(void); 00070 00071 private: 00072 //! Wastes the specified subtree. 00073 void deleteSubTree(Node *subtree_root); 00074 //! Adds to the specified subtree a leaf that is reached from the subtree 00075 //! root via a path of length <tt>path_len</tt> bits. 00076 /*! 00077 * Returns <tt>false</tt> on success, and <tt>true</tt> otherwise. 00078 * In any case the tree remains in defined state. 00079 */ 00080 bool addLeaf(Node *subtree_root, int path_len, Node *leaf); 00081 //! Recursively makes unused child pointers of all inner nodes point to the 00082 //! special <i>ground node</i>, from which tree traversals never recover. 00083 /*! 00084 * So if invalid bitstreams are encountered the tree traversal will forever 00085 * be caught in the ground node and the Huffman decoder using the tree will 00086 * simply cease to produce video tiles - without the need of timeconsuming 00087 * code to detect such invalid bitstreams. 00088 */ 00089 void groundUnusedPaths(Node *subtree); 00090 //! Private helper method. 00091 int countLeaves(Node *subtree); 00092 }; 00093 00094 00095 00096 #endif // __MXCPC_HUFFMANTREE_H__