00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029 #include "image/codecs/indeo/vlc.h"
00030 #include "image/codecs/indeo/mem.h"
00031 #include "common/textconsole.h"
00032 #include "common/util.h"
00033
00034 namespace Image {
00035 namespace Indeo {
00036
00043 #define AV_QSORT(p, num, type, cmp) do {\
00044 void *stack[64][2];\
00045 int sp = 1;\
00046 stack[0][0] = p;\
00047 stack[0][1] = (p)+(num)-1;\
00048 while(sp){\
00049 type *start = (type *)stack[--sp][0];\
00050 type *end = (type *)stack[ sp][1];\
00051 while (start < end) {\
00052 if (start < end-1) {\
00053 int checksort = 0;\
00054 type *right = end - 2;\
00055 type *left = start + 1;\
00056 type *mid = start + ((end - start) >> 1);\
00057 if(cmp(start, end) > 0) {\
00058 if(cmp( end, mid) > 0) SWAP(*start, *mid);\
00059 else SWAP(*start, *end);\
00060 } else {\
00061 if(cmp(start, mid) > 0) SWAP(*start, *mid);\
00062 else checksort = 1;\
00063 }\
00064 if (cmp(mid, end) > 0) { \
00065 SWAP(*mid, *end);\
00066 checksort = 0;\
00067 }\
00068 if(start == end - 2) break;\
00069 SWAP(end[-1], *mid);\
00070 while (left <= right) {\
00071 while (left<=right && cmp(left, end - 1) < 0)\
00072 left++;\
00073 while (left<=right && cmp(right, end - 1) > 0)\
00074 right--;\
00075 if (left <= right) {\
00076 SWAP(*left, *right);\
00077 left++;\
00078 right--;\
00079 }\
00080 }\
00081 SWAP(end[-1], *left);\
00082 if(checksort && (mid == left - 1 || mid == left)){\
00083 mid= start;\
00084 while(mid<end && cmp(mid, mid+1) <= 0)\
00085 mid++;\
00086 if(mid==end)\
00087 break;\
00088 }\
00089 if (end - left < left - start){\
00090 stack[sp ][0] = start;\
00091 stack[sp++][1] = right;\
00092 start = left + 1;\
00093 } else {\
00094 stack[sp ][0] = left+1;\
00095 stack[sp++][1] = end;\
00096 end = right;\
00097 }\
00098 } else {\
00099 if (cmp(start, end) > 0)\
00100 SWAP(*start, *end);\
00101 break;\
00102 }\
00103 }\
00104 }\
00105 } while (0)
00106
00107 #define COPY(condition)\
00108 for (i = 0; i < nbCodes; i++) { \
00109 buf[j].bits = getData(p_bits, i, bitsWrap, bitsSize); \
00110 if (!(condition)) \
00111 continue; \
00112 if (buf[j].bits > (3 * nbBits) || buf[j].bits > 32) { \
00113 warning("Too long VLC (%d) in init_vlc", buf[j].bits); \
00114 if (!(flags & INIT_VLC_USE_NEW_STATIC)) \
00115 free(buf); \
00116 return -1; \
00117 } \
00118 buf[j].code = getData(codes, i, codesWrap, codesSize); \
00119 if (buf[j].code >= (1LL << buf[j].bits)) { \
00120 warning("Invalid code %x for %d in init_vlc", buf[j].code, i); \
00121 if (!(flags & INIT_VLC_USE_NEW_STATIC)) \
00122 free(buf); \
00123 return -1; \
00124 } \
00125 if (flags & INIT_VLC_LE) \
00126 buf[j].code = bitswap32(buf[j].code); \
00127 else \
00128 buf[j].code <<= 32 - buf[j].bits; \
00129 if (symbols) \
00130 buf[j].symbol = getData(symbols, i, symbolsWrap, symbolsSize); \
00131 else \
00132 buf[j].symbol = i; \
00133 j++; \
00134 }
00135
00136
00137
00138 VLC::VLC() : _bits(0), _tableSize(0), _tableAllocated(0), _table(nullptr) {
00139 }
00140
00141 int VLC::init_vlc(int nbBits, int nbCodes, const void *bits, int bitsWrap, int bitsSize,
00142 const void *codes, int codesWrap, int codesSize, int flags) {
00143 return init_vlc(nbBits, nbCodes, bits, bitsWrap, bitsSize, codes, codesWrap,
00144 codesSize, nullptr, 0, 0, flags);
00145 }
00146
00147 int VLC::init_vlc(int nbBits, int nbCodes, const void *p_bits, int bitsWrap,
00148 int bitsSize, const void *codes, int codesWrap, int codesSize,
00149 const void *symbols, int symbolsWrap, int symbolsSize, int flags) {
00150 VLCcode *buf;
00151 int i, j, ret;
00152 VLCcode localbuf[1500];
00153 VLC localvlc, *vlc;
00154
00155 vlc = this;
00156 vlc->_bits = nbBits;
00157 if (flags & INIT_VLC_USE_NEW_STATIC) {
00158 assert((nbCodes + 1) <= (int)FF_ARRAY_ELEMS(localbuf));
00159 buf = localbuf;
00160 localvlc = *this;
00161 vlc = &localvlc;
00162 vlc->_tableSize = 0;
00163 } else {
00164 vlc->_table = NULL;
00165 vlc->_tableAllocated = 0;
00166 vlc->_tableSize = 0;
00167
00168 buf = (VLCcode *)malloc((nbCodes + 1) * sizeof(VLCcode));
00169 assert(buf);
00170 }
00171
00172 assert(symbolsSize <= 2 || !symbols);
00173 j = 0;
00174
00175 COPY(buf[j].bits > nbBits);
00176
00177
00178 AV_QSORT(buf, j, VLCcode, compareVlcSpec);
00179 COPY(buf[j].bits && buf[j].bits <= nbBits);
00180 nbCodes = j;
00181
00182 ret = vlc->buildTable(nbBits, nbCodes, buf, flags);
00183
00184 if (flags & INIT_VLC_USE_NEW_STATIC) {
00185 if (vlc->_tableSize != vlc->_tableAllocated)
00186 warning("needed %d had %d", vlc->_tableSize, vlc->_tableAllocated);
00187
00188 assert(ret >= 0);
00189 *this = *vlc;
00190 } else {
00191 free(buf);
00192 if (ret < 0) {
00193 avFreeP(&vlc->_table);
00194 return -1;
00195 }
00196 }
00197
00198 return 0;
00199 }
00200
00201 void VLC::freeVlc() {
00202 free(_table);
00203 }
00204
00205 int VLC::compareVlcSpec(const void *a, const void *b) {
00206 const VLCcode *sa = (const VLCcode *)a, *sb = (const VLCcode *)b;
00207 return (sa->code >> 1) - (sb->code >> 1);
00208 }
00209
00210 int VLC::buildTable(int tableNbBits, int nbCodes,
00211 VLCcode *codes, int flags) {
00212 VLC *vlc = this;
00213 int tableSize, tableIndex, index, codePrefix, symbol, subtableBits;
00214 int i, j, k, n, nb, inc;
00215 uint32 code;
00216 VLC_TYPE (*table)[2];
00217
00218 tableSize = 1 << tableNbBits;
00219 if (tableNbBits > 30)
00220 return -1;
00221 tableIndex = allocTable(tableSize, flags & INIT_VLC_USE_NEW_STATIC);
00222
00223 if (tableIndex < 0)
00224 return tableIndex;
00225 table = &vlc->_table[tableIndex];
00226
00227
00228 for (i = 0; i < nbCodes; i++) {
00229 n = codes[i].bits;
00230 code = codes[i].code;
00231 symbol = codes[i].symbol;
00232
00233
00234 if (n <= tableNbBits) {
00235
00236 j = code >> (32 - tableNbBits);
00237 nb = 1 << (tableNbBits - n);
00238 inc = 1;
00239 if (flags & INIT_VLC_LE) {
00240 j = bitswap32(code);
00241 inc = 1 << n;
00242 }
00243 for (k = 0; k < nb; k++) {
00244 int bits = table[j][1];
00245
00246
00247 if (bits != 0 && bits != n) {
00248 warning("incorrect codes");
00249 return -1;
00250 }
00251
00252 table[j][1] = n;
00253 table[j][0] = symbol;
00254 j += inc;
00255 }
00256 } else {
00257
00258 n -= tableNbBits;
00259 codePrefix = code >> (32 - tableNbBits);
00260 subtableBits = n;
00261 codes[i].bits = n;
00262 codes[i].code = code << tableNbBits;
00263 for (k = i + 1; k < nbCodes; k++) {
00264 n = codes[k].bits - tableNbBits;
00265 if (n <= 0)
00266 break;
00267 code = codes[k].code;
00268 if (code >> (32 - tableNbBits) != (uint)codePrefix)
00269 break;
00270 codes[k].bits = n;
00271 codes[k].code = code << tableNbBits;
00272 subtableBits = MAX(subtableBits, n);
00273 }
00274 subtableBits = MIN(subtableBits, tableNbBits);
00275 j = (flags & INIT_VLC_LE) ? bitswap32(codePrefix) >> (32 - tableNbBits) : codePrefix;
00276 table[j][1] = -subtableBits;
00277
00278 index = vlc->buildTable(subtableBits, k - i, codes + i, flags);
00279 if (index < 0)
00280 return index;
00281
00282
00283 table = (VLC_TYPE (*)[2])&vlc->_table[tableIndex];
00284 table[j][0] = index;
00285 i = k - 1;
00286 }
00287 }
00288
00289 for (i = 0; i < tableSize; i++) {
00290 if (table[i][1] == 0)
00291 table[i][0] = -1;
00292 }
00293
00294 return tableIndex;
00295 }
00296
00297 int VLC::allocTable(int size, int useStatic) {
00298 VLC *vlc = this;
00299 int index = vlc->_tableSize;
00300
00301 vlc->_tableSize += size;
00302 if (vlc->_tableSize > vlc->_tableAllocated) {
00303
00304 assert(!useStatic);
00305
00306 vlc->_tableAllocated += (1 << vlc->_bits);
00307 vlc->_table = (int16(*)[2])avReallocF(vlc->_table, vlc->_tableAllocated, sizeof(VLC_TYPE) * 2);
00308 if (!vlc->_table) {
00309 vlc->_tableAllocated = 0;
00310 vlc->_tableSize = 0;
00311 return -2;
00312 }
00313
00314 memset(vlc->_table + vlc->_tableAllocated - (1 << vlc->_bits), 0, sizeof(VLC_TYPE) * 2 << vlc->_bits);
00315 }
00316
00317 return index;
00318 }
00319
00320 uint VLC::getData(const void *table, uint idx, uint wrap, uint size) {
00321 const uint8 *ptr = (const uint8 *)table + idx * wrap;
00322
00323 switch(size) {
00324 case 1:
00325 return *(const uint8 *)ptr;
00326
00327 case 2:
00328 return *(const uint16 *)ptr;
00329
00330 default:
00331 return *(const uint32 *)ptr;
00332 }
00333 }
00334
00335 }
00336 }