HuffmanDecode.cpp

00001 #include "mbed.h"
00002 #include "HuffmanDecode.h"
00003 #include "HuffmanCodeTable.h"
00004 #if 1
00005 #define DBG(...) do{fprintf(stderr,"[%s@%d] ",__PRETTY_FUNCTION__,__LINE__);fprintf(stderr,__VA_ARGS__);} while(0);
00006 #define DBG_ASSERT(A) while(!(A)){fprintf(stderr,"\n\n%s@%d %s ASSERT!\n\n",__PRETTY_FUNCTION__,__LINE__,#A);exit(1);};
00007 #else
00008 #define DBG(...)
00009 #define DBG_ASSERT(A) 
00010 #endif
00011 
00012 const Huff HT_DC_0[] = {
00013 /* 0 */ {0,0,2,0x0},
00014 /* 1 */ {0,1,3,0x2},
00015 /* 2 */ {0,2,3,0x3},
00016 /* 3 */ {0,3,3,0x4},
00017 /* 4 */ {0,4,3,0x5},
00018 /* 5 */ {0,5,3,0x6},
00019 /* 6 */ {0,6,4,0xe},
00020 /* 7 */ {0,7,5,0x1e},
00021 /* 8 */ {0,8,6,0x3e},
00022 /* 9 */ {0,9,7,0x7e},
00023 /* 10 */ {0,10,8,0xfe},
00024 /* 11 */ {0,11,9,0x1fe},
00025 };
00026 const Huff HT_AC_0[] = {
00027 /* 0 */ {0,1,2,0x0},
00028 /* 1 */ {0,2,2,0x1},
00029 /* 2 */ {0,3,3,0x4},
00030 /* 3 */ {0,0,4,0xa},
00031 /* 4 */ {0,4,4,0xb},
00032 /* 5 */ {1,1,4,0xc},
00033 /* 6 */ {0,5,5,0x1a},
00034 /* 7 */ {1,2,5,0x1b},
00035 /* 8 */ {2,1,5,0x1c},
00036 /* 9 */ {3,1,6,0x3a},
00037 /* 10 */ {4,1,6,0x3b},
00038 /* 11 */ {0,6,7,0x78},
00039 /* 12 */ {1,3,7,0x79},
00040 /* 13 */ {5,1,7,0x7a},
00041 /* 14 */ {6,1,7,0x7b},
00042 /* 15 */ {0,7,8,0xf8},
00043 /* 16 */ {2,2,8,0xf9},
00044 /* 17 */ {7,1,8,0xfa},
00045 /* 18 */ {1,4,9,0x1f6},
00046 /* 19 */ {3,2,9,0x1f7},
00047 /* 20 */ {8,1,9,0x1f8},
00048 /* 21 */ {9,1,9,0x1f9},
00049 /* 22 */ {10,1,9,0x1fa},
00050 /* 23 */ {0,8,10,0x3f6},
00051 /* 24 */ {2,3,10,0x3f7},
00052 /* 25 */ {4,2,10,0x3f8},
00053 /* 26 */ {11,1,10,0x3f9},
00054 /* 27 */ {12,1,10,0x3fa},
00055 /* 28 */ {1,5,11,0x7f6},
00056 /* 29 */ {5,2,11,0x7f7},
00057 /* 30 */ {13,1,11,0x7f8},
00058 /* 31 */ {15,0,11,0x7f9},
00059 /* 32 */ {2,4,12,0xff4},
00060 /* 33 */ {3,3,12,0xff5},
00061 /* 34 */ {6,2,12,0xff6},
00062 /* 35 */ {7,2,12,0xff7},
00063 /* 36 */ {8,2,15,0x7fc0},
00064 /* 37 */ {0,9,16,0xff82},
00065 /* 38 */ {0,10,16,0xff83},
00066 /* 39 */ {1,6,16,0xff84},
00067 /* 40 */ {1,7,16,0xff85},
00068 /* 41 */ {1,8,16,0xff86},
00069 /* 42 */ {1,9,16,0xff87},
00070 /* 43 */ {1,10,16,0xff88},
00071 /* 44 */ {2,5,16,0xff89},
00072 /* 45 */ {2,6,16,0xff8a},
00073 /* 46 */ {2,7,16,0xff8b},
00074 /* 47 */ {2,8,16,0xff8c},
00075 /* 48 */ {2,9,16,0xff8d},
00076 /* 49 */ {2,10,16,0xff8e},
00077 /* 50 */ {3,4,16,0xff8f},
00078 /* 51 */ {3,5,16,0xff90},
00079 /* 52 */ {3,6,16,0xff91},
00080 /* 53 */ {3,7,16,0xff92},
00081 /* 54 */ {3,8,16,0xff93},
00082 /* 55 */ {3,9,16,0xff94},
00083 /* 56 */ {3,10,16,0xff95},
00084 /* 57 */ {4,3,16,0xff96},
00085 /* 58 */ {4,4,16,0xff97},
00086 /* 59 */ {4,5,16,0xff98},
00087 /* 60 */ {4,6,16,0xff99},
00088 /* 61 */ {4,7,16,0xff9a},
00089 /* 62 */ {4,8,16,0xff9b},
00090 /* 63 */ {4,9,16,0xff9c},
00091 /* 64 */ {4,10,16,0xff9d},
00092 /* 65 */ {5,3,16,0xff9e},
00093 /* 66 */ {5,4,16,0xff9f},
00094 /* 67 */ {5,5,16,0xffa0},
00095 /* 68 */ {5,6,16,0xffa1},
00096 /* 69 */ {5,7,16,0xffa2},
00097 /* 70 */ {5,8,16,0xffa3},
00098 /* 71 */ {5,9,16,0xffa4},
00099 /* 72 */ {5,10,16,0xffa5},
00100 /* 73 */ {6,3,16,0xffa6},
00101 /* 74 */ {6,4,16,0xffa7},
00102 /* 75 */ {6,5,16,0xffa8},
00103 /* 76 */ {6,6,16,0xffa9},
00104 /* 77 */ {6,7,16,0xffaa},
00105 /* 78 */ {6,8,16,0xffab},
00106 /* 79 */ {6,9,16,0xffac},
00107 /* 80 */ {6,10,16,0xffad},
00108 /* 81 */ {7,3,16,0xffae},
00109 /* 82 */ {7,4,16,0xffaf},
00110 /* 83 */ {7,5,16,0xffb0},
00111 /* 84 */ {7,6,16,0xffb1},
00112 /* 85 */ {7,7,16,0xffb2},
00113 /* 86 */ {7,8,16,0xffb3},
00114 /* 87 */ {7,9,16,0xffb4},
00115 /* 88 */ {7,10,16,0xffb5},
00116 /* 89 */ {8,3,16,0xffb6},
00117 /* 90 */ {8,4,16,0xffb7},
00118 /* 91 */ {8,5,16,0xffb8},
00119 /* 92 */ {8,6,16,0xffb9},
00120 /* 93 */ {8,7,16,0xffba},
00121 /* 94 */ {8,8,16,0xffbb},
00122 /* 95 */ {8,9,16,0xffbc},
00123 /* 96 */ {8,10,16,0xffbd},
00124 /* 97 */ {9,2,16,0xffbe},
00125 /* 98 */ {9,3,16,0xffbf},
00126 /* 99 */ {9,4,16,0xffc0},
00127 /* 100 */ {9,5,16,0xffc1},
00128 /* 101 */ {9,6,16,0xffc2},
00129 /* 102 */ {9,7,16,0xffc3},
00130 /* 103 */ {9,8,16,0xffc4},
00131 /* 104 */ {9,9,16,0xffc5},
00132 /* 105 */ {9,10,16,0xffc6},
00133 /* 106 */ {10,2,16,0xffc7},
00134 /* 107 */ {10,3,16,0xffc8},
00135 /* 108 */ {10,4,16,0xffc9},
00136 /* 109 */ {10,5,16,0xffca},
00137 /* 110 */ {10,6,16,0xffcb},
00138 /* 111 */ {10,7,16,0xffcc},
00139 /* 112 */ {10,8,16,0xffcd},
00140 /* 113 */ {10,9,16,0xffce},
00141 /* 114 */ {10,10,16,0xffcf},
00142 /* 115 */ {11,2,16,0xffd0},
00143 /* 116 */ {11,3,16,0xffd1},
00144 /* 117 */ {11,4,16,0xffd2},
00145 /* 118 */ {11,5,16,0xffd3},
00146 /* 119 */ {11,6,16,0xffd4},
00147 /* 120 */ {11,7,16,0xffd5},
00148 /* 121 */ {11,8,16,0xffd6},
00149 /* 122 */ {11,9,16,0xffd7},
00150 /* 123 */ {11,10,16,0xffd8},
00151 /* 124 */ {12,2,16,0xffd9},
00152 /* 125 */ {12,3,16,0xffda},
00153 /* 126 */ {12,4,16,0xffdb},
00154 /* 127 */ {12,5,16,0xffdc},
00155 /* 128 */ {12,6,16,0xffdd},
00156 /* 129 */ {12,7,16,0xffde},
00157 /* 130 */ {12,8,16,0xffdf},
00158 /* 131 */ {12,9,16,0xffe0},
00159 /* 132 */ {12,10,16,0xffe1},
00160 /* 133 */ {13,2,16,0xffe2},
00161 /* 134 */ {13,3,16,0xffe3},
00162 /* 135 */ {13,4,16,0xffe4},
00163 /* 136 */ {13,5,16,0xffe5},
00164 /* 137 */ {13,6,16,0xffe6},
00165 /* 138 */ {13,7,16,0xffe7},
00166 /* 139 */ {13,8,16,0xffe8},
00167 /* 140 */ {13,9,16,0xffe9},
00168 /* 141 */ {13,10,16,0xffea},
00169 /* 142 */ {14,1,16,0xffeb},
00170 /* 143 */ {14,2,16,0xffec},
00171 /* 144 */ {14,3,16,0xffed},
00172 /* 145 */ {14,4,16,0xffee},
00173 /* 146 */ {14,5,16,0xffef},
00174 /* 147 */ {14,6,16,0xfff0},
00175 /* 148 */ {14,7,16,0xfff1},
00176 /* 149 */ {14,8,16,0xfff2},
00177 /* 150 */ {14,9,16,0xfff3},
00178 /* 151 */ {14,10,16,0xfff4},
00179 /* 152 */ {15,1,16,0xfff5},
00180 /* 153 */ {15,2,16,0xfff6},
00181 /* 154 */ {15,3,16,0xfff7},
00182 /* 155 */ {15,4,16,0xfff8},
00183 /* 156 */ {15,5,16,0xfff9},
00184 /* 157 */ {15,6,16,0xfffa},
00185 /* 158 */ {15,7,16,0xfffb},
00186 /* 159 */ {15,8,16,0xfffc},
00187 /* 160 */ {15,9,16,0xfffd},
00188 /* 161 */ {15,10,16,0xfffe},
00189 };
00190 const Huff HT_DC_1[] = {
00191 /* 0 */ {0,0,2,0x0},
00192 /* 1 */ {0,1,2,0x1},
00193 /* 2 */ {0,2,2,0x2},
00194 /* 3 */ {0,3,3,0x6},
00195 /* 4 */ {0,4,4,0xe},
00196 /* 5 */ {0,5,5,0x1e},
00197 /* 6 */ {0,6,6,0x3e},
00198 /* 7 */ {0,7,7,0x7e},
00199 /* 8 */ {0,8,8,0xfe},
00200 /* 9 */ {0,9,9,0x1fe},
00201 /* 10 */ {0,10,10,0x3fe},
00202 /* 11 */ {0,11,11,0x7fe},
00203 };
00204 const Huff HT_AC_1[] = {
00205 /* 0 */ {0,0,2,0x0},
00206 /* 1 */ {0,1,2,0x1},
00207 /* 2 */ {0,2,3,0x4},
00208 /* 3 */ {0,3,4,0xa},
00209 /* 4 */ {1,1,4,0xb},
00210 /* 5 */ {0,4,5,0x18},
00211 /* 6 */ {0,5,5,0x19},
00212 /* 7 */ {2,1,5,0x1a},
00213 /* 8 */ {3,1,5,0x1b},
00214 /* 9 */ {0,6,6,0x38},
00215 /* 10 */ {1,2,6,0x39},
00216 /* 11 */ {4,1,6,0x3a},
00217 /* 12 */ {5,1,6,0x3b},
00218 /* 13 */ {0,7,7,0x78},
00219 /* 14 */ {6,1,7,0x79},
00220 /* 15 */ {7,1,7,0x7a},
00221 /* 16 */ {1,3,8,0xf6},
00222 /* 17 */ {2,2,8,0xf7},
00223 /* 18 */ {3,2,8,0xf8},
00224 /* 19 */ {8,1,8,0xf9},
00225 /* 20 */ {0,8,9,0x1f4},
00226 /* 21 */ {1,4,9,0x1f5},
00227 /* 22 */ {4,2,9,0x1f6},
00228 /* 23 */ {9,1,9,0x1f7},
00229 /* 24 */ {10,1,9,0x1f8},
00230 /* 25 */ {11,1,9,0x1f9},
00231 /* 26 */ {12,1,9,0x1fa},
00232 /* 27 */ {0,9,10,0x3f6},
00233 /* 28 */ {2,3,10,0x3f7},
00234 /* 29 */ {3,3,10,0x3f8},
00235 /* 30 */ {5,2,10,0x3f9},
00236 /* 31 */ {15,0,10,0x3fa},
00237 /* 32 */ {1,5,11,0x7f6},
00238 /* 33 */ {6,2,11,0x7f7},
00239 /* 34 */ {7,2,11,0x7f8},
00240 /* 35 */ {13,1,11,0x7f9},
00241 /* 36 */ {0,10,12,0xff4},
00242 /* 37 */ {1,6,12,0xff5},
00243 /* 38 */ {2,4,12,0xff6},
00244 /* 39 */ {3,4,12,0xff7},
00245 /* 40 */ {14,1,14,0x3fe0},
00246 /* 41 */ {2,5,15,0x7fc2},
00247 /* 42 */ {15,1,15,0x7fc3},
00248 /* 43 */ {1,7,16,0xff88},
00249 /* 44 */ {1,8,16,0xff89},
00250 /* 45 */ {1,9,16,0xff8a},
00251 /* 46 */ {1,10,16,0xff8b},
00252 /* 47 */ {2,6,16,0xff8c},
00253 /* 48 */ {2,7,16,0xff8d},
00254 /* 49 */ {2,8,16,0xff8e},
00255 /* 50 */ {2,9,16,0xff8f},
00256 /* 51 */ {2,10,16,0xff90},
00257 /* 52 */ {3,5,16,0xff91},
00258 /* 53 */ {3,6,16,0xff92},
00259 /* 54 */ {3,7,16,0xff93},
00260 /* 55 */ {3,8,16,0xff94},
00261 /* 56 */ {3,9,16,0xff95},
00262 /* 57 */ {3,10,16,0xff96},
00263 /* 58 */ {4,3,16,0xff97},
00264 /* 59 */ {4,4,16,0xff98},
00265 /* 60 */ {4,5,16,0xff99},
00266 /* 61 */ {4,6,16,0xff9a},
00267 /* 62 */ {4,7,16,0xff9b},
00268 /* 63 */ {4,8,16,0xff9c},
00269 /* 64 */ {4,9,16,0xff9d},
00270 /* 65 */ {4,10,16,0xff9e},
00271 /* 66 */ {5,3,16,0xff9f},
00272 /* 67 */ {5,4,16,0xffa0},
00273 /* 68 */ {5,5,16,0xffa1},
00274 /* 69 */ {5,6,16,0xffa2},
00275 /* 70 */ {5,7,16,0xffa3},
00276 /* 71 */ {5,8,16,0xffa4},
00277 /* 72 */ {5,9,16,0xffa5},
00278 /* 73 */ {5,10,16,0xffa6},
00279 /* 74 */ {6,3,16,0xffa7},
00280 /* 75 */ {6,4,16,0xffa8},
00281 /* 76 */ {6,5,16,0xffa9},
00282 /* 77 */ {6,6,16,0xffaa},
00283 /* 78 */ {6,7,16,0xffab},
00284 /* 79 */ {6,8,16,0xffac},
00285 /* 80 */ {6,9,16,0xffad},
00286 /* 81 */ {6,10,16,0xffae},
00287 /* 82 */ {7,3,16,0xffaf},
00288 /* 83 */ {7,4,16,0xffb0},
00289 /* 84 */ {7,5,16,0xffb1},
00290 /* 85 */ {7,6,16,0xffb2},
00291 /* 86 */ {7,7,16,0xffb3},
00292 /* 87 */ {7,8,16,0xffb4},
00293 /* 88 */ {7,9,16,0xffb5},
00294 /* 89 */ {7,10,16,0xffb6},
00295 /* 90 */ {8,2,16,0xffb7},
00296 /* 91 */ {8,3,16,0xffb8},
00297 /* 92 */ {8,4,16,0xffb9},
00298 /* 93 */ {8,5,16,0xffba},
00299 /* 94 */ {8,6,16,0xffbb},
00300 /* 95 */ {8,7,16,0xffbc},
00301 /* 96 */ {8,8,16,0xffbd},
00302 /* 97 */ {8,9,16,0xffbe},
00303 /* 98 */ {8,10,16,0xffbf},
00304 /* 99 */ {9,2,16,0xffc0},
00305 /* 100 */ {9,3,16,0xffc1},
00306 /* 101 */ {9,4,16,0xffc2},
00307 /* 102 */ {9,5,16,0xffc3},
00308 /* 103 */ {9,6,16,0xffc4},
00309 /* 104 */ {9,7,16,0xffc5},
00310 /* 105 */ {9,8,16,0xffc6},
00311 /* 106 */ {9,9,16,0xffc7},
00312 /* 107 */ {9,10,16,0xffc8},
00313 /* 108 */ {10,2,16,0xffc9},
00314 /* 109 */ {10,3,16,0xffca},
00315 /* 110 */ {10,4,16,0xffcb},
00316 /* 111 */ {10,5,16,0xffcc},
00317 /* 112 */ {10,6,16,0xffcd},
00318 /* 113 */ {10,7,16,0xffce},
00319 /* 114 */ {10,8,16,0xffcf},
00320 /* 115 */ {10,9,16,0xffd0},
00321 /* 116 */ {10,10,16,0xffd1},
00322 /* 117 */ {11,2,16,0xffd2},
00323 /* 118 */ {11,3,16,0xffd3},
00324 /* 119 */ {11,4,16,0xffd4},
00325 /* 120 */ {11,5,16,0xffd5},
00326 /* 121 */ {11,6,16,0xffd6},
00327 /* 122 */ {11,7,16,0xffd7},
00328 /* 123 */ {11,8,16,0xffd8},
00329 /* 124 */ {11,9,16,0xffd9},
00330 /* 125 */ {11,10,16,0xffda},
00331 /* 126 */ {12,2,16,0xffdb},
00332 /* 127 */ {12,3,16,0xffdc},
00333 /* 128 */ {12,4,16,0xffdd},
00334 /* 129 */ {12,5,16,0xffde},
00335 /* 130 */ {12,6,16,0xffdf},
00336 /* 131 */ {12,7,16,0xffe0},
00337 /* 132 */ {12,8,16,0xffe1},
00338 /* 133 */ {12,9,16,0xffe2},
00339 /* 134 */ {12,10,16,0xffe3},
00340 /* 135 */ {13,2,16,0xffe4},
00341 /* 136 */ {13,3,16,0xffe5},
00342 /* 137 */ {13,4,16,0xffe6},
00343 /* 138 */ {13,5,16,0xffe7},
00344 /* 139 */ {13,6,16,0xffe8},
00345 /* 140 */ {13,7,16,0xffe9},
00346 /* 141 */ {13,8,16,0xffea},
00347 /* 142 */ {13,9,16,0xffeb},
00348 /* 143 */ {13,10,16,0xffec},
00349 /* 144 */ {14,2,16,0xffed},
00350 /* 145 */ {14,3,16,0xffee},
00351 /* 146 */ {14,4,16,0xffef},
00352 /* 147 */ {14,5,16,0xfff0},
00353 /* 148 */ {14,6,16,0xfff1},
00354 /* 149 */ {14,7,16,0xfff2},
00355 /* 150 */ {14,8,16,0xfff3},
00356 /* 151 */ {14,9,16,0xfff4},
00357 /* 152 */ {14,10,16,0xfff5},
00358 /* 153 */ {15,2,16,0xfff6},
00359 /* 154 */ {15,3,16,0xfff7},
00360 /* 155 */ {15,4,16,0xfff8},
00361 /* 156 */ {15,5,16,0xfff9},
00362 /* 157 */ {15,6,16,0xfffa},
00363 /* 158 */ {15,7,16,0xfffb},
00364 /* 159 */ {15,8,16,0xfffc},
00365 /* 160 */ {15,9,16,0xfffd},
00366 /* 161 */ {15,10,16,0xfffe},
00367 };
00368 
00369 #ifndef JPEG_USE_HUFFMAN_TABLE
00370 Huff* HuffmanDecode::Lookup(int tc, int th, BitPattern* bitpat)
00371 {
00372     Huff* huff;
00373     int size;
00374 
00375     if (tc == 0) {
00376         if (th == 0) {
00377             huff = (Huff*)HT_DC_0;
00378             size = sizeof(HT_DC_0) / sizeof(Huff);
00379         } else {
00380             huff = (Huff*)HT_DC_1;
00381             size = sizeof(HT_DC_1) / sizeof(Huff);
00382         }
00383     } else {
00384         if (th == 0) {
00385             huff = (Huff*)HT_AC_0;
00386             size = sizeof(HT_AC_0) / sizeof(Huff);
00387         } else {
00388             huff = (Huff*)HT_AC_1;
00389             size = sizeof(HT_AC_1) / sizeof(Huff);
00390         }
00391     }
00392 
00393     for(int i = 0; i < size; i++) {
00394         //DBG("%d %p\n", i, huff);
00395         if (huff->code_size > bitpat->size()) {
00396             return NULL;
00397         }
00398         BitPattern tmp(huff->code, huff->code_size);
00399         if (bitpat->match(tmp)) {
00400             return huff;
00401         }
00402         huff++;
00403     }
00404     return NULL;
00405 }
00406 
00407 #else // JPEG_USE_HUFFMAN_TABLE
00408 
00409 struct sthtinfo {
00410     const Huff* huff_table;
00411     const uint8_t* index_table;
00412     int max_code_size;
00413 };
00414 
00415 const struct sthtinfo htinfo[2][2] = {
00416     {{HT_DC_0, HT_DC_0_index,  9}, {HT_DC_1, HT_DC_1_index, 11}},
00417     {{HT_AC_0, HT_AC_0_index, 16}, {HT_AC_1, HT_AC_1_index, 16}},
00418 };
00419 
00420 Huff* HuffmanDecode::Lookup(int tc, int th, BitPattern* bitpat)
00421 {
00422     const struct sthtinfo* info = &htinfo[tc][th];
00423 
00424     int pat_size = bitpat->size();
00425     uint32_t pat = bitpat->peek(pat_size);
00426     if (pat_size > info->max_code_size) {
00427         pat >>= (pat_size-info->max_code_size);
00428     } else if (pat_size < info->max_code_size) {
00429         pat <<= (info->max_code_size-pat_size);
00430     }
00431     int index = info->index_table[pat];
00432     if (index == 0xff) {
00433         return NULL;
00434     }
00435     Huff* huff = (Huff*)&(info->huff_table[index]);
00436     if (huff->code_size > pat_size) {
00437         return NULL;
00438     }
00439     return huff;
00440 }
00441 #endif // JPEG_USE_HUFFMAN_TABLE
00442 
00443 int HuffmanDecode::getValue(Huff* huff, BitPattern* bitpat)
00444 {
00445     int value = bitpat->get(huff->value_size);
00446     if (huff->value_size == 0) {
00447         return 0;
00448     }
00449     if (value & (1<<(huff->value_size-1))) {
00450         return value;
00451     }
00452     value -= (1<<huff->value_size)-1;
00453     return value;
00454 }