src/test/unit/huffman_unittest.cc

   1 /*
   2  * This file is part of Cleanflight.
   3  *
   4  * Cleanflight is free software: you can redistribute it and/or modify
   5  * it under the terms of the GNU General Public License as published by
   6  * the Free Software Foundation, either version 3 of the License, or
   7  * (at your option) any later version.
   8  *
   9  * Cleanflight is distributed in the hope that it will be useful,
  10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12  * GNU General Public License for more details.
  13  *
  14  * You should have received a copy of the GNU General Public License
  15  * along with Cleanflight.  If not, see <http://www.gnu.org/licenses/>.
  16  */
  17
  18 #include <stdint.h>
  19
  20 extern "C" {
  21     #include "common/huffman.h"
  22 }
  23
  24 #include "unittest_macros.h"
  25 #include "gtest/gtest.h"
  26
  27 #define OUTBUF_LEN 128
  28 static uint8_t outBuf[OUTBUF_LEN];
  29
  30 /*
  31  * Huffman Tree, used to decompress a bytestream.
  32  *
  33  * The leaf nodes of the Huffman tree are stored in an array.
  34  */
  35
  36 #define HUFFMAN_EOF (-1)
  37
  38 #define HUFFMAN_TREE_SIZE 257 // 256 characters plus EOF
  39
  40 typedef struct huffmanTree_s {
  41     int16_t     value;
  42     uint16_t    codeLen;
  43     uint16_t    code;
  44 } huffmanTree_t;
  45
  46 static const huffmanTree_t huffmanTree[HUFFMAN_TREE_SIZE] = {
  47 //    Char  Len    Code         Bitcode
  48     { 0x00,   2, 0x0003 },  //  11
  49     { 0x01,   3, 0x0005 },  //  101
  50     { 0x02,   4, 0x0009 },  //  1001
  51     { 0x03,   5, 0x0011 },  //  10001
  52     { 0x04,   5, 0x0010 },  //  10000
  53     { 0x50,   5, 0x000F },  //  01111
  54     { 0x05,   6, 0x001D },  //  011101
  55     { 0x06,   6, 0x001C },  //  011100
  56     { 0x07,   6, 0x001B },  //  011011
  57     { 0x08,   6, 0x001A },  //  011010
  58     { 0x10,   6, 0x0019 },  //  011001
  59     { 0x09,   7, 0x0031 },  //  0110001
  60     { 0x0A,   7, 0x0030 },  //  0110000
  61     { 0x0B,   7, 0x002F },  //  0101111
  62     { 0x0C,   7, 0x002E },  //  0101110
  63     { 0x0D,   7, 0x002D },  //  0101101
  64     { 0x0E,   7, 0x002C },  //  0101100
  65     { 0x0F,   7, 0x002B },  //  0101011
  66     { 0x11,   7, 0x002A },  //  0101010
  67     { 0x12,   7, 0x0029 },  //  0101001
  68     { 0x13,   8, 0x0051 },  //  01010001
  69     { 0x14,   8, 0x0050 },  //  01010000
  70     { 0x15,   8, 0x004F },  //  01001111
  71     { 0x16,   8, 0x004E },  //  01001110
  72     { 0x17,   8, 0x004D },  //  01001101
  73     { 0x18,   8, 0x004C },  //  01001100
  74     { 0x19,   8, 0x004B },  //  01001011
  75     { 0x1A,   8, 0x004A },  //  01001010
  76     { 0x1B,   8, 0x0049 },  //  01001001
  77     { 0x1C,   8, 0x0048 },  //  01001000
  78     { 0x1D,   8, 0x0047 },  //  01000111
  79     { 0x1E,   8, 0x0046 },  //  01000110
  80     { 0x1F,   8, 0x0045 },  //  01000101
  81     { 0x20,   8, 0x0044 },  //  01000100
  82     { 0x21,   8, 0x0043 },  //  01000011
  83     { 0x22,   8, 0x0042 },  //  01000010
  84     { 0x23,   8, 0x0041 },  //  01000001
  85     { 0x24,   8, 0x0040 },  //  01000000
  86     { 0x30,   8, 0x003F },  //  00111111
  87     { 0x40,   8, 0x003E },  //  00111110
  88     { 0xF0,   8, 0x003D },  //  00111101
  89     { 0x25,   9, 0x0079 },  //  001111001
  90     { 0x26,   9, 0x0078 },  //  001111000
  91     { 0x27,   9, 0x0077 },  //  001110111
  92     { 0x28,   9, 0x0076 },  //  001110110
  93     { 0x29,   9, 0x0075 },  //  001110101
  94     { 0x2A,   9, 0x0074 },  //  001110100
  95     { 0x2B,   9, 0x0073 },  //  001110011
  96     { 0x2C,   9, 0x0072 },  //  001110010
  97     { 0x2D,   9, 0x0071 },  //  001110001
  98     { 0x2E,   9, 0x0070 },  //  001110000
  99     { 0x2F,   9, 0x006F },  //  001101111
 100     { 0x31,   9, 0x006E },  //  001101110
 101     { 0x32,   9, 0x006D },  //  001101101
 102     { 0x33,   9, 0x006C },  //  001101100
 103     { 0x34,   9, 0x006B },  //  001101011
 104     { 0x35,   9, 0x006A },  //  001101010
 105     { 0x36,   9, 0x0069 },  //  001101001
 106     { 0x37,   9, 0x0068 },  //  001101000
 107     { 0x38,   9, 0x0067 },  //  001100111
 108     { 0x39,   9, 0x0066 },  //  001100110
 109     { 0x3A,   9, 0x0065 },  //  001100101
 110     { 0x3B,   9, 0x0064 },  //  001100100
 111     { 0x3C,   9, 0x0063 },  //  001100011
 112     { 0x3D,   9, 0x0062 },  //  001100010
 113     { 0x3E,   9, 0x0061 },  //  001100001
 114     { 0x3F,   9, 0x0060 },  //  001100000
 115     { 0x41,   9, 0x005F },  //  001011111
 116     { 0x42,   9, 0x005E },  //  001011110
 117     { 0x43,   9, 0x005D },  //  001011101
 118     { 0x44,   9, 0x005C },  //  001011100
 119     { 0x45,   9, 0x005B },  //  001011011
 120     { 0x46,   9, 0x005A },  //  001011010
 121     { 0x47,   9, 0x0059 },  //  001011001
 122     { 0x48,   9, 0x0058 },  //  001011000
 123     { 0x49,   9, 0x0057 },  //  001010111
 124     { 0x4C,   9, 0x0056 },  //  001010110
 125     { 0x4F,   9, 0x0055 },  //  001010101
 126     { 0x51,   9, 0x0054 },  //  001010100
 127     { 0x80,   9, 0x0053 },  //  001010011
 128     { 0xE0,   9, 0x0052 },  //  001010010
 129     { 0xF1,   9, 0x0051 },  //  001010001
 130     { 0xFF,   9, 0x0050 },  //  001010000
 131     { 0x4A,  10, 0x009F },  //  0010011111
 132     { 0x4B,  10, 0x009E },  //  0010011110
 133     { 0x4D,  10, 0x009D },  //  0010011101
 134     { 0x4E,  10, 0x009C },  //  0010011100
 135     { 0x52,  10, 0x009B },  //  0010011011
 136     { 0x53,  10, 0x009A },  //  0010011010
 137     { 0x54,  10, 0x0099 },  //  0010011001
 138     { 0x55,  10, 0x0098 },  //  0010011000
 139     { 0x56,  10, 0x0097 },  //  0010010111
 140     { 0x57,  10, 0x0096 },  //  0010010110
 141     { 0x58,  10, 0x0095 },  //  0010010101
 142     { 0x59,  10, 0x0094 },  //  0010010100
 143     { 0x5A,  10, 0x0093 },  //  0010010011
 144     { 0x5B,  10, 0x0092 },  //  0010010010
 145     { 0x5C,  10, 0x0091 },  //  0010010001
 146     { 0x5D,  10, 0x0090 },  //  0010010000
 147     { 0x5E,  10, 0x008F },  //  0010001111
 148     { 0x5F,  10, 0x008E },  //  0010001110
 149     { 0x60,  10, 0x008D },  //  0010001101
 150     { 0x61,  10, 0x008C },  //  0010001100
 151     { 0x62,  10, 0x008B },  //  0010001011
 152     { 0x63,  10, 0x008A },  //  0010001010
 153     { 0x64,  10, 0x0089 },  //  0010001001
 154     { 0x65,  10, 0x0088 },  //  0010001000
 155     { 0x66,  10, 0x0087 },  //  0010000111
 156     { 0x67,  10, 0x0086 },  //  0010000110
 157     { 0x68,  10, 0x0085 },  //  0010000101
 158     { 0x69,  10, 0x0084 },  //  0010000100
 159     { 0x6A,  10, 0x0083 },  //  0010000011
 160     { 0x6B,  10, 0x0082 },  //  0010000010
 161     { 0x6C,  10, 0x0081 },  //  0010000001
 162     { 0x6D,  10, 0x0080 },  //  0010000000
 163     { 0x6E,  10, 0x007F },  //  0001111111
 164     { 0x6F,  10, 0x007E },  //  0001111110
 165     { 0x70,  10, 0x007D },  //  0001111101
 166     { 0x71,  10, 0x007C },  //  0001111100
 167     { 0x72,  10, 0x007B },  //  0001111011
 168     { 0x73,  10, 0x007A },  //  0001111010
 169     { 0x74,  10, 0x0079 },  //  0001111001
 170     { 0x75,  10, 0x0078 },  //  0001111000
 171     { 0x76,  10, 0x0077 },  //  0001110111
 172     { 0x77,  10, 0x0076 },  //  0001110110
 173     { 0x78,  10, 0x0075 },  //  0001110101
 174     { 0x79,  10, 0x0074 },  //  0001110100
 175     { 0x7A,  10, 0x0073 },  //  0001110011
 176     { 0x7B,  10, 0x0072 },  //  0001110010
 177     { 0x7C,  10, 0x0071 },  //  0001110001
 178     { 0x7D,  10, 0x0070 },  //  0001110000
 179     { 0x7E,  10, 0x006F },  //  0001101111
 180     { 0x7F,  10, 0x006E },  //  0001101110
 181     { 0x81,  10, 0x006D },  //  0001101101
 182     { 0x82,  10, 0x006C },  //  0001101100
 183     { 0x83,  10, 0x006B },  //  0001101011
 184     { 0x84,  10, 0x006A },  //  0001101010
 185     { 0x85,  10, 0x0069 },  //  0001101001
 186     { 0x86,  10, 0x0068 },  //  0001101000
 187     { 0x87,  10, 0x0067 },  //  0001100111
 188     { 0x88,  10, 0x0066 },  //  0001100110
 189     { 0x89,  10, 0x0065 },  //  0001100101
 190     { 0x8A,  10, 0x0064 },  //  0001100100
 191     { 0x8B,  10, 0x0063 },  //  0001100011
 192     { 0x8C,  10, 0x0062 },  //  0001100010
 193     { 0x8D,  10, 0x0061 },  //  0001100001
 194     { 0x8E,  10, 0x0060 },  //  0001100000
 195     { 0x8F,  10, 0x005F },  //  0001011111
 196     { 0x90,  10, 0x005E },  //  0001011110
 197     { 0x91,  10, 0x005D },  //  0001011101
 198     { 0x92,  10, 0x005C },  //  0001011100
 199     { 0x93,  10, 0x005B },  //  0001011011
 200     { 0x94,  10, 0x005A },  //  0001011010
 201     { 0x95,  10, 0x0059 },  //  0001011001
 202     { 0x96,  10, 0x0058 },  //  0001011000
 203     { 0x97,  10, 0x0057 },  //  0001010111
 204     { 0x98,  10, 0x0056 },  //  0001010110
 205     { 0x99,  10, 0x0055 },  //  0001010101
 206     { 0x9A,  10, 0x0054 },  //  0001010100
 207     { 0x9B,  10, 0x0053 },  //  0001010011
 208     { 0x9C,  10, 0x0052 },  //  0001010010
 209     { 0x9D,  10, 0x0051 },  //  0001010001
 210     { 0x9E,  10, 0x0050 },  //  0001010000
 211     { 0x9F,  10, 0x004F },  //  0001001111
 212     { 0xA0,  10, 0x004E },  //  0001001110
 213     { 0xA1,  10, 0x004D },  //  0001001101
 214     { 0xA2,  10, 0x004C },  //  0001001100
 215     { 0xA3,  10, 0x004B },  //  0001001011
 216     { 0xA4,  10, 0x004A },  //  0001001010
 217     { 0xA5,  10, 0x0049 },  //  0001001001
 218     { 0xA6,  10, 0x0048 },  //  0001001000
 219     { 0xA7,  10, 0x0047 },  //  0001000111
 220     { 0xA8,  10, 0x0046 },  //  0001000110
 221     { 0xA9,  10, 0x0045 },  //  0001000101
 222     { 0xAA,  10, 0x0044 },  //  0001000100
 223     { 0xAB,  10, 0x0043 },  //  0001000011
 224     { 0xAC,  10, 0x0042 },  //  0001000010
 225     { 0xAD,  10, 0x0041 },  //  0001000001
 226     { 0xAE,  10, 0x0040 },  //  0001000000
 227     { 0xAF,  10, 0x003F },  //  0000111111
 228     { 0xB0,  10, 0x003E },  //  0000111110
 229     { 0xB1,  10, 0x003D },  //  0000111101
 230     { 0xB2,  10, 0x003C },  //  0000111100
 231     { 0xB3,  10, 0x003B },  //  0000111011
 232     { 0xB4,  10, 0x003A },  //  0000111010
 233     { 0xB5,  10, 0x0039 },  //  0000111001
 234     { 0xB6,  10, 0x0038 },  //  0000111000
 235     { 0xB7,  10, 0x0037 },  //  0000110111
 236     { 0xB8,  10, 0x0036 },  //  0000110110
 237     { 0xB9,  10, 0x0035 },  //  0000110101
 238     { 0xBA,  10, 0x0034 },  //  0000110100
 239     { 0xBB,  10, 0x0033 },  //  0000110011
 240     { 0xBC,  10, 0x0032 },  //  0000110010
 241     { 0xBD,  10, 0x0031 },  //  0000110001
 242     { 0xBE,  10, 0x0030 },  //  0000110000
 243     { 0xBF,  10, 0x002F },  //  0000101111
 244     { 0xC0,  10, 0x002E },  //  0000101110
 245     { 0xC1,  10, 0x002D },  //  0000101101
 246     { 0xC2,  10, 0x002C },  //  0000101100
 247     { 0xC3,  10, 0x002B },  //  0000101011
 248     { 0xC4,  10, 0x002A },  //  0000101010
 249     { 0xC5,  10, 0x0029 },  //  0000101001
 250     { 0xC6,  10, 0x0028 },  //  0000101000
 251     { 0xC7,  10, 0x0027 },  //  0000100111
 252     { 0xC8,  10, 0x0026 },  //  0000100110
 253     { 0xC9,  10, 0x0025 },  //  0000100101
 254     { 0xCA,  10, 0x0024 },  //  0000100100
 255     { 0xCB,  10, 0x0023 },  //  0000100011
 256     { 0xCC,  10, 0x0022 },  //  0000100010
 257     { 0xCD,  10, 0x0021 },  //  0000100001
 258     { 0xCE,  10, 0x0020 },  //  0000100000
 259     { 0xCF,  10, 0x001F },  //  0000011111
 260     { 0xD0,  10, 0x001E },  //  0000011110
 261     { 0xD1,  10, 0x001D },  //  0000011101
 262     { 0xD2,  10, 0x001C },  //  0000011100
 263     { 0xD3,  10, 0x001B },  //  0000011011
 264     { 0xD4,  10, 0x001A },  //  0000011010
 265     { 0xD6,  10, 0x0019 },  //  0000011001
 266     { 0xD7,  10, 0x0018 },  //  0000011000
 267     { 0xD8,  10, 0x0017 },  //  0000010111
 268     { 0xD9,  10, 0x0016 },  //  0000010110
 269     { 0xDA,  10, 0x0015 },  //  0000010101
 270     { 0xDB,  10, 0x0014 },  //  0000010100
 271     { 0xDC,  10, 0x0013 },  //  0000010011
 272     { 0xDE,  10, 0x0012 },  //  0000010010
 273     { 0xDF,  10, 0x0011 },  //  0000010001
 274     { 0xE1,  10, 0x0010 },  //  0000010000
 275     { 0xE2,  10, 0x000F },  //  0000001111
 276     { 0xE4,  10, 0x000E },  //  0000001110
 277     { 0xEF,  10, 0x000D },  //  0000001101
 278     { 0xD5,  11, 0x0019 },  //  00000011001
 279     { 0xDD,  11, 0x0018 },  //  00000011000
 280     { 0xE3,  11, 0x0017 },  //  00000010111
 281     { 0xE5,  11, 0x0016 },  //  00000010110
 282     { 0xE6,  11, 0x0015 },  //  00000010101
 283     { 0xE7,  11, 0x0014 },  //  00000010100
 284     { 0xE8,  11, 0x0013 },  //  00000010011
 285     { 0xE9,  11, 0x0012 },  //  00000010010
 286     { 0xEA,  11, 0x0011 },  //  00000010001
 287     { 0xEB,  11, 0x0010 },  //  00000010000
 288     { 0xEC,  11, 0x000F },  //  00000001111
 289     { 0xED,  11, 0x000E },  //  00000001110
 290     { 0xEE,  11, 0x000D },  //  00000001101
 291     { 0xF2,  11, 0x000C },  //  00000001100
 292     { 0xF3,  11, 0x000B },  //  00000001011
 293     { 0xF4,  11, 0x000A },  //  00000001010
 294     { 0xF5,  11, 0x0009 },  //  00000001001
 295     { 0xF6,  11, 0x0008 },  //  00000001000
 296     { 0xF7,  11, 0x0007 },  //  00000000111
 297     { 0xF8,  11, 0x0006 },  //  00000000110
 298     { 0xFA,  11, 0x0005 },  //  00000000101
 299     { 0xFB,  11, 0x0004 },  //  00000000100
 300     { 0xFC,  11, 0x0003 },  //  00000000011
 301     { 0xFD,  11, 0x0002 },  //  00000000010
 302     { 0xFE,  11, 0x0001 },  //  00000000001
 303     { 0xF9,  12, 0x0001 },  //  000000000001
 304     { HUFFMAN_EOF,  12, 0x0000 },  //  000000000000
 305 };
 306
 307 int huffManLenIndex[HUFFMAN_TREE_SIZE];
 308
 309 void huffmanInitDecodeLenIndex(void)
 310 {
 311     // create an index of first code at each possible length
 312     for (int ii = 0; ii < HUFFMAN_TREE_SIZE; ++ii) {
 313         huffManLenIndex[ii] = -1;
 314     }
 315     for (int ii = 0; ii < HUFFMAN_TREE_SIZE; ++ii) {
 316         if (huffManLenIndex[huffmanTree[ii].codeLen] == -1) {
 317             huffManLenIndex[huffmanTree[ii].codeLen] = ii;
 318         }
 319     }
 320 }
 321
 322 int huffmanDecodeBuf(uint8_t *outBuf, int outBufLen, const uint8_t *inBuf, int inBufLen, int inBufCharacterCount, const huffmanTree_t *huffmanTree)
 323 {
 324     static bool initialized = false;
 325     if (!initialized) {
 326         huffmanInitDecodeLenIndex();
 327         initialized = true;
 328     }
 329
 330     if (inBufCharacterCount > outBufLen) {
 331         return -1;
 332     }
 333     uint16_t code = 0;
 334     int codeLen = 0;
 335     int outCount = 0;
 336     int inCount = 0;
 337     uint8_t testBit = 0x80;
 338     bool eof = false;
 339     while (!eof && outCount < outBufLen && inCount < inBufLen) {
 340         if (outCount == inBufCharacterCount) {
 341             // we've exhausted the input stream, discard any odd bits on the end
 342             return outCount;
 343         }
 344         if (inCount >= inBufLen) {
 345             return -1;
 346         }
 347         // get the next bit from the input buffer
 348         code <<= 1;
 349         ++codeLen;
 350         if (*inBuf & testBit) {
 351             code |= 0x01;
 352         }
 353         testBit >>= 1;
 354         if (testBit == 0) {
 355             testBit = 0x80;
 356             ++inBuf;
 357             ++inCount;
 358         }
 359         // check if the code is a leaf node or an interior node
 360         if (huffManLenIndex[codeLen] != -1) {
 361             // look for the code in the tree, only leaf nodes are stored in the tree
 362             for(int ii = huffManLenIndex[codeLen]; (ii < HUFFMAN_TREE_SIZE) && (huffmanTree[ii].codeLen == codeLen); ++ii) {
 363                 if (huffmanTree[ii].code == code) {
 364                     // we've found the code, so it is a leaf node
 365                     const int16_t value = huffmanTree[ii].value;
 366                     if (value == HUFFMAN_EOF) {
 367                         eof = true;
 368                     } else {
 369                         // output the value
 370                         *outBuf = (uint8_t)value;
 371                         ++outBuf;
 372                         ++outCount;
 373                     }
 374                     // reset the code to continue decompressing the input buffer
 375                     code = 0;
 376                     codeLen = 0;
 377                     break;
 378                 }
 379             }
 380         }
 381     }
 382     return outCount;
 383 }
 384
 385 TEST(HuffmanUnittest, TestHuffmanEncode)
 386 {
 387     #define INBUF_LEN1 3
 388     const uint8_t inBuf1[INBUF_LEN1] = {0,1,1};
 389     // 11 101 101
 390     // 1110 1101
 391     // e    d
 392     int len = huffmanEncodeBuf(outBuf, OUTBUF_LEN, inBuf1, INBUF_LEN1, huffmanTable);
 393     EXPECT_EQ(1, len);
 394     EXPECT_EQ(0xed, (int)outBuf[0]);
 395
 396     #define INBUF_LEN2 4
 397     const uint8_t inBuf2[INBUF_LEN2] = {0,1,2,3};
 398     // 11 101 1001 10001
 399     // 1110 1100 1100 01
 400     // e    c    c    8
 401     len = huffmanEncodeBuf(outBuf, OUTBUF_LEN, inBuf2, INBUF_LEN2, huffmanTable);
 402     EXPECT_EQ(2, len);
 403     EXPECT_EQ(0xec, (int)outBuf[0]);
 404     EXPECT_EQ(0xc4, (int)outBuf[1]);
 405
 406     #define INBUF_LEN3 8
 407     const uint8_t inBuf3[INBUF_LEN3] = {0,1,2,3,4,5,6,7};
 408     // 11 101 1001 10001 10000 011101 011100 011011
 409     // 1110 1100 1100 0110 0000 1110 1011 1000 1101 1
 410     // e    c    c    6    0    e    b    8    d    8
 411     len = huffmanEncodeBuf(outBuf, OUTBUF_LEN, inBuf3, INBUF_LEN3, huffmanTable);
 412     EXPECT_EQ(5, len);
 413     EXPECT_EQ(0xec, (int)outBuf[0]);
 414     EXPECT_EQ(0xc6, (int)outBuf[1]);
 415     EXPECT_EQ(0x0e, (int)outBuf[2]);
 416     EXPECT_EQ(0xb8, (int)outBuf[3]);
 417     EXPECT_EQ(0xd8, (int)outBuf[4]);
 418 }
 419
 420 TEST(HuffmanUnittest, TestHuffmanEncodeStreaming)
 421 {
 422     #define INBUF_LEN1  3
 423     #define INBUF_LEN1_CHUNK1 2
 424     #define INBUF_LEN1_CHUNK2 (INBUF_LEN1 - INBUF_LEN1_CHUNK1)
 425     const uint8_t inBuf1[INBUF_LEN1] = {0,1,1};
 426     // 11 101 101
 427     // 1110 1101
 428     // e    d
 429     huffmanState_t state1 = {
 430         .bytesWritten = 0,
 431         .outByte = outBuf,
 432         .outBufLen = OUTBUF_LEN,
 433         .outBit = 0x80,
 434     };
 435     *state1.outByte = 0;
 436     int status = huffmanEncodeBufStreaming(&state1, inBuf1, INBUF_LEN1_CHUNK1, huffmanTable);
 437     EXPECT_EQ(0, status);
 438     status = huffmanEncodeBufStreaming(&state1, inBuf1 + INBUF_LEN1_CHUNK1, INBUF_LEN1_CHUNK2, huffmanTable);
 439     EXPECT_EQ(0, status);
 440     if (state1.outBit != 0x80) {
 441         ++state1.bytesWritten;
 442     }
 443
 444     EXPECT_EQ(1, state1.bytesWritten);
 445     EXPECT_EQ(0xed, (int)outBuf[0]);
 446
 447     #define INBUF_LEN2 4
 448     #define INBUF_LEN2_CHUNK1 1
 449     #define INBUF_LEN2_CHUNK2 1
 450     #define INBUF_LEN2_CHUNK3 2
 451     const uint8_t inBuf2[INBUF_LEN2] = {0,1,2,3};
 452     // 11 101 1001 10001
 453     // 1110 1100 1100 01
 454     // e    c    c    8
 455     huffmanState_t state2 = {
 456         .bytesWritten = 0,
 457         .outByte = outBuf,
 458         .outBufLen = OUTBUF_LEN,
 459         .outBit = 0x80,
 460     };
 461     *state2.outByte = 0;
 462     status = huffmanEncodeBufStreaming(&state2, inBuf2, INBUF_LEN2_CHUNK1, huffmanTable);
 463     EXPECT_EQ(0, status);
 464     status = huffmanEncodeBufStreaming(&state2, inBuf2 + INBUF_LEN2_CHUNK1, INBUF_LEN2_CHUNK2, huffmanTable);
 465     EXPECT_EQ(0, status);
 466     status = huffmanEncodeBufStreaming(&state2, inBuf2 + INBUF_LEN2_CHUNK1 + INBUF_LEN2_CHUNK2, INBUF_LEN2_CHUNK3, huffmanTable);
 467     EXPECT_EQ(0, status);
 468     if (state2.outBit != 0x80) {
 469         ++state2.bytesWritten;
 470     }
 471
 472     EXPECT_EQ(2, state2.bytesWritten);
 473     EXPECT_EQ(0xec, (int)outBuf[0]);
 474     EXPECT_EQ(0xc4, (int)outBuf[1]);
 475
 476     #define INBUF_LEN3 8
 477     #define INBUF_LEN3_CHUNK1 4
 478     #define INBUF_LEN3_CHUNK2 (INBUF_LEN3 - INBUF_LEN3_CHUNK1)
 479     const uint8_t inBuf3[INBUF_LEN3] = {0,1,2,3,4,5,6,7};
 480     // 11 101 1001 10001 10000 011101 011100 011011
 481     // 1110 1100 1100 0110 0000 1110 1011 1000 1101 1
 482     // e    c    c    6    0    e    b    8    d    8
 483     huffmanState_t state3 = {
 484         .bytesWritten = 0,
 485         .outByte = outBuf,
 486         .outBufLen = OUTBUF_LEN,
 487         .outBit = 0x80,
 488     };
 489     *state3.outByte = 0;
 490     status = huffmanEncodeBufStreaming(&state3, inBuf3, INBUF_LEN3_CHUNK1, huffmanTable);
 491     EXPECT_EQ(0, status);
 492     status = huffmanEncodeBufStreaming(&state3, inBuf3 + INBUF_LEN3_CHUNK1, INBUF_LEN3_CHUNK2, huffmanTable);
 493     EXPECT_EQ(0, status);
 494     if (state3.outBit != 0x80) {
 495         ++state3.bytesWritten;
 496     }
 497
 498     EXPECT_EQ(5, state3.bytesWritten);
 499     EXPECT_EQ(0xec, (int)outBuf[0]);
 500     EXPECT_EQ(0xc6, (int)outBuf[1]);
 501     EXPECT_EQ(0x0e, (int)outBuf[2]);
 502     EXPECT_EQ(0xb8, (int)outBuf[3]);
 503     EXPECT_EQ(0xd8, (int)outBuf[4]);
 504 }
 505
 506 TEST(HuffmanUnittest, TestHuffmanDecode)
 507 {
 508     int len;
 509
 510     #define HUFF_BUF_LEN1 1
 511     #define HUFF_BUF_COUNT1 1
 512     const uint8_t inBuf1[HUFF_BUF_LEN1] = {0xc0}; // 11
 513     len = huffmanDecodeBuf(outBuf, OUTBUF_LEN, inBuf1, HUFF_BUF_LEN1, HUFF_BUF_COUNT1, huffmanTree);
 514     EXPECT_EQ(1, len);
 515     EXPECT_EQ(0x00, (int)outBuf[0]);
 516     EXPECT_EQ(-1, huffManLenIndex[0]);
 517     EXPECT_EQ(-1, huffManLenIndex[1]);
 518     EXPECT_EQ(0, huffManLenIndex[2]);
 519     EXPECT_EQ(1, huffManLenIndex[3]);
 520     EXPECT_EQ(2, huffManLenIndex[4]);
 521     EXPECT_EQ(3, huffManLenIndex[5]);
 522     EXPECT_EQ(6, huffManLenIndex[6]);
 523     EXPECT_EQ(11, huffManLenIndex[7]);
 524
 525     #define HUFF_BUF_LEN2 1
 526     #define HUFF_BUF_COUNT2 3
 527     const uint8_t inBuf2[HUFF_BUF_LEN2] = {0xed}; // 11 101 101
 528     len = huffmanDecodeBuf(outBuf, OUTBUF_LEN, inBuf2, HUFF_BUF_LEN2, HUFF_BUF_COUNT2, huffmanTree);
 529     EXPECT_EQ(3, len);
 530     EXPECT_EQ(0x00, (int)outBuf[0]);
 531     EXPECT_EQ(0x01, (int)outBuf[1]);
 532     EXPECT_EQ(0x01, (int)outBuf[2]);
 533
 534     #define HUFF_BUF_LEN3 5
 535     #define HUFF_BUF_COUNT3 8
 536     const uint8_t inBuf3[HUFF_BUF_LEN3] = {0xec, 0xc6, 0x0e, 0xb8, 0xd8};
 537     len = huffmanDecodeBuf(outBuf, OUTBUF_LEN, inBuf3, HUFF_BUF_LEN3, HUFF_BUF_COUNT3, huffmanTree);
 538     EXPECT_EQ(8, len);
 539     EXPECT_EQ(0x00, (int)outBuf[0]);
 540     EXPECT_EQ(0x01, (int)outBuf[1]);
 541     EXPECT_EQ(0x02, (int)outBuf[2]);
 542     EXPECT_EQ(0x03, (int)outBuf[3]);
 543     EXPECT_EQ(0x04, (int)outBuf[4]);
 544     EXPECT_EQ(0x05, (int)outBuf[5]);
 545     EXPECT_EQ(0x06, (int)outBuf[6]);
 546     EXPECT_EQ(0x07, (int)outBuf[7]);
 547 }
 548
 549 // STUBS
 550
 551 extern "C" {
 552 }