2 * Discrete wavelet transform
3 * Copyright (c) 2007 Kamil Nowosad
4 * Copyright (c) 2013 Nicolas Bertrand <nicoinattendu@gmail.com>
6 * This file is part of FFmpeg.
8 * FFmpeg is free software; you can redistribute it and/or
9 * modify it under the terms of the GNU Lesser General Public
10 * License as published by the Free Software Foundation; either
11 * version 2.1 of the License, or (at your option) any later version.
13 * FFmpeg is distributed in the hope that it will be useful,
14 * but WITHOUT ANY WARRANTY; without even the implied warranty of
15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
16 * Lesser General Public License for more details.
18 * You should have received a copy of the GNU Lesser General Public
19 * License along with FFmpeg; if not, write to the Free Software
20 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
25 * Discrete wavelet transform
28 #include "libavutil/avassert.h"
29 #include "libavutil/common.h"
30 #include "libavutil/mem.h"
31 #include "jpeg2000dwt.h"
34 /* Defines for 9/7 DWT lifting parameters.
35 * Parameters are in float. */
36 #define F_LFTG_ALPHA 1.586134342059924f
37 #define F_LFTG_BETA 0.052980118572961f
38 #define F_LFTG_GAMMA 0.882911075530934f
39 #define F_LFTG_DELTA 0.443506852043971f
40 #define F_LFTG_K 1.230174104914001f
41 #define F_LFTG_X 1.625732422f
42 /* FIXME: Why use 1.625732422 instead of 1/F_LFTG_K?
43 * Incorrect value in JPEG2000 norm.
44 * see (ISO/IEC 15444:1 (version 2002) F.3.8.2 */
46 /* Lifting parameters in integer format.
47 * Computed as param = (float param) * (1 << 16) */
48 #define I_LFTG_ALPHA 103949
49 #define I_LFTG_BETA 3472
50 #define I_LFTG_GAMMA 57862
51 #define I_LFTG_DELTA 29066
52 #define I_LFTG_K 80621
53 #define I_LFTG_X 106544
55 static inline void extend53(int *p, int i0, int i1)
57 p[i0 - 1] = p[i0 + 1];
59 p[i0 - 2] = p[i0 + 2];
60 p[i1 + 1] = p[i1 - 3];
63 static inline void extend97_float(float *p, int i0, int i1)
67 for (i = 1; i <= 4; i++) {
68 p[i0 - i] = p[i0 + i];
69 p[i1 + i - 1] = p[i1 - i - 1];
73 static inline void extend97_int(int32_t *p, int i0, int i1)
77 for (i = 1; i <= 4; i++) {
78 p[i0 - i] = p[i0 + i];
79 p[i1 + i - 1] = p[i1 - i - 1];
83 static void sd_1d53(int *p, int i0, int i1)
92 for (i = (i0+1)/2 - 1; i < (i1+1)/2; i++)
93 p[2*i+1] -= (p[2*i] + p[2*i+2]) >> 1;
94 for (i = (i0+1)/2; i < (i1+1)/2; i++)
95 p[2*i] += (p[2*i-1] + p[2*i+1] + 2) >> 2;
98 static void dwt_encode53(DWTContext *s, int *t)
101 w = s->linelen[s->ndeclevels-1][0];
102 int *line = s->i_linebuf;
105 for (lev = s->ndeclevels-1; lev >= 0; lev--){
106 int lh = s->linelen[lev][0],
107 lv = s->linelen[lev][1],
113 av_assert1(!mh && !mv);
116 for (lp = 0; lp < lv; lp++){
119 for (i = 0; i < lh; i++)
122 sd_1d53(line, mh, mh + lh);
124 // copy back and deinterleave
125 for (i = mh; i < lh; i+=2, j++)
127 for (i = 1-mh; i < lh; i+=2, j++)
133 for (lp = 0; lp < lh; lp++) {
136 for (i = 0; i < lv; i++)
139 sd_1d53(line, mv, mv + lv);
141 // copy back and deinterleave
142 for (i = mv; i < lv; i+=2, j++)
144 for (i = 1-mv; i < lv; i+=2, j++)
149 static void sd_1d97_float(float *p, int i0, int i1)
156 extend97_float(p, i0, i1);
159 for (i = i0/2 - 2; i < i1/2 + 1; i++)
160 p[2*i+1] -= 1.586134 * (p[2*i] + p[2*i+2]);
161 for (i = i0/2 - 1; i < i1/2 + 1; i++)
162 p[2*i] -= 0.052980 * (p[2*i-1] + p[2*i+1]);
163 for (i = i0/2 - 1; i < i1/2; i++)
164 p[2*i+1] += 0.882911 * (p[2*i] + p[2*i+2]);
165 for (i = i0/2; i < i1/2; i++)
166 p[2*i] += 0.443506 * (p[2*i-1] + p[2*i+1]);
169 static void dwt_encode97_float(DWTContext *s, float *t)
172 w = s->linelen[s->ndeclevels-1][0];
173 float *line = s->f_linebuf;
176 for (lev = s->ndeclevels-1; lev >= 0; lev--){
177 int lh = s->linelen[lev][0],
178 lv = s->linelen[lev][1],
184 av_assert1(!mh && !mv);
187 for (lp = 0; lp < lv; lp++){
190 for (i = 0; i < lh; i++)
193 sd_1d97_float(line, mh, mh + lh);
195 // copy back and deinterleave
196 for (i = mh; i < lh; i+=2, j++)
197 t[w*lp + j] = F_LFTG_X * l[i] / 2;
198 for (i = 1-mh; i < lh; i+=2, j++)
199 t[w*lp + j] = F_LFTG_K * l[i] / 2;
204 for (lp = 0; lp < lh; lp++) {
207 for (i = 0; i < lv; i++)
210 sd_1d97_float(line, mv, mv + lv);
212 // copy back and deinterleave
213 for (i = mv; i < lv; i+=2, j++)
214 t[w*j + lp] = F_LFTG_X * l[i] / 2;
215 for (i = 1-mv; i < lv; i+=2, j++)
216 t[w*j + lp] = F_LFTG_K * l[i] / 2;
221 static void sd_1d97_int(int *p, int i0, int i1)
228 extend97_int(p, i0, i1);
231 for (i = i0/2 - 2; i < i1/2 + 1; i++)
232 p[2 * i + 1] -= (I_LFTG_ALPHA * (p[2 * i] + p[2 * i + 2]) + (1 << 15)) >> 16;
233 for (i = i0/2 - 1; i < i1/2 + 1; i++)
234 p[2 * i] -= (I_LFTG_BETA * (p[2 * i - 1] + p[2 * i + 1]) + (1 << 15)) >> 16;
235 for (i = i0/2 - 1; i < i1/2; i++)
236 p[2 * i + 1] += (I_LFTG_GAMMA * (p[2 * i] + p[2 * i + 2]) + (1 << 15)) >> 16;
237 for (i = i0/2; i < i1/2; i++)
238 p[2 * i] += (I_LFTG_DELTA * (p[2 * i - 1] + p[2 * i + 1]) + (1 << 15)) >> 16;
241 static void dwt_encode97_int(DWTContext *s, int *t)
244 w = s->linelen[s->ndeclevels-1][0];
245 int *line = s->i_linebuf;
248 for (lev = s->ndeclevels-1; lev >= 0; lev--){
249 int lh = s->linelen[lev][0],
250 lv = s->linelen[lev][1],
256 av_assert1(!mh && !mv);
260 for (lp = 0; lp < lv; lp++){
263 for (i = 0; i < lh; i++)
266 sd_1d97_int(line, mh, mh + lh);
268 // copy back and deinterleave
269 for (i = mh; i < lh; i+=2, j++)
270 t[w*lp + j] = ((l[i] * I_LFTG_X) + (1 << 16)) >> 17;
271 for (i = 1-mh; i < lh; i+=2, j++)
272 t[w*lp + j] = ((l[i] * I_LFTG_K) + (1 << 16)) >> 17;
277 for (lp = 0; lp < lh; lp++) {
280 for (i = 0; i < lv; i++)
283 sd_1d97_int(line, mv, mv + lv);
285 // copy back and deinterleave
286 for (i = mv; i < lv; i+=2, j++)
287 t[w*j + lp] = ((l[i] * I_LFTG_X) + (1 << 16)) >> 17;
288 for (i = 1-mv; i < lv; i+=2, j++)
289 t[w*j + lp] = ((l[i] * I_LFTG_K) + (1 << 16)) >> 17;
294 static void sr_1d53(int *p, int i0, int i1)
306 for (i = i0 / 2; i < i1 / 2 + 1; i++)
307 p[2 * i] -= (p[2 * i - 1] + p[2 * i + 1] + 2) >> 2;
308 for (i = i0 / 2; i < i1 / 2; i++)
309 p[2 * i + 1] += (p[2 * i] + p[2 * i + 2]) >> 1;
312 static void dwt_decode53(DWTContext *s, int *t)
315 int w = s->linelen[s->ndeclevels - 1][0];
316 int32_t *line = s->i_linebuf;
319 for (lev = 0; lev < s->ndeclevels; lev++) {
320 int lh = s->linelen[lev][0],
321 lv = s->linelen[lev][1],
329 for (lp = 0; lp < lv; lp++) {
331 // copy with interleaving
332 for (i = mh; i < lh; i += 2, j++)
333 l[i] = t[w * lp + j];
334 for (i = 1 - mh; i < lh; i += 2, j++)
335 l[i] = t[w * lp + j];
337 sr_1d53(line, mh, mh + lh);
339 for (i = 0; i < lh; i++)
340 t[w * lp + i] = l[i];
345 for (lp = 0; lp < lh; lp++) {
347 // copy with interleaving
348 for (i = mv; i < lv; i += 2, j++)
349 l[i] = t[w * j + lp];
350 for (i = 1 - mv; i < lv; i += 2, j++)
351 l[i] = t[w * j + lp];
353 sr_1d53(line, mv, mv + lv);
355 for (i = 0; i < lv; i++)
356 t[w * i + lp] = l[i];
361 static void sr_1d97_float(float *p, int i0, int i1)
373 extend97_float(p, i0, i1);
375 for (i = i0 / 2 - 1; i < i1 / 2 + 2; i++)
376 p[2 * i] -= F_LFTG_DELTA * (p[2 * i - 1] + p[2 * i + 1]);
378 for (i = i0 / 2 - 1; i < i1 / 2 + 1; i++)
379 p[2 * i + 1] -= F_LFTG_GAMMA * (p[2 * i] + p[2 * i + 2]);
381 for (i = i0 / 2; i < i1 / 2 + 1; i++)
382 p[2 * i] += F_LFTG_BETA * (p[2 * i - 1] + p[2 * i + 1]);
384 for (i = i0 / 2; i < i1 / 2; i++)
385 p[2 * i + 1] += F_LFTG_ALPHA * (p[2 * i] + p[2 * i + 2]);
388 static void dwt_decode97_float(DWTContext *s, float *t)
391 int w = s->linelen[s->ndeclevels - 1][0];
392 float *line = s->f_linebuf;
394 /* position at index O of line range [0-5,w+5] cf. extend function */
397 for (lev = 0; lev < s->ndeclevels; lev++) {
398 int lh = s->linelen[lev][0],
399 lv = s->linelen[lev][1],
406 for (lp = 0; lp < lv; lp++) {
408 // copy with interleaving
409 for (i = mh; i < lh; i += 2, j++)
410 l[i] = data[w * lp + j] * F_LFTG_K;
411 for (i = 1 - mh; i < lh; i += 2, j++)
412 l[i] = data[w * lp + j] * F_LFTG_X;
414 sr_1d97_float(line, mh, mh + lh);
416 for (i = 0; i < lh; i++)
417 data[w * lp + i] = l[i];
422 for (lp = 0; lp < lh; lp++) {
424 // copy with interleaving
425 for (i = mv; i < lv; i += 2, j++)
426 l[i] = data[w * j + lp] * F_LFTG_K;
427 for (i = 1 - mv; i < lv; i += 2, j++)
428 l[i] = data[w * j + lp] * F_LFTG_X;
430 sr_1d97_float(line, mv, mv + lv);
432 for (i = 0; i < lv; i++)
433 data[w * i + lp] = l[i];
438 static void sr_1d97_int(int32_t *p, int i0, int i1)
444 p[1] = (p[1] * I_LFTG_K + (1<<16)) >> 17;
446 p[0] = (p[0] * I_LFTG_X + (1<<16)) >> 17;
450 extend97_int(p, i0, i1);
452 for (i = i0 / 2 - 1; i < i1 / 2 + 2; i++)
453 p[2 * i] -= (I_LFTG_DELTA * (p[2 * i - 1] + p[2 * i + 1]) + (1 << 15)) >> 16;
455 for (i = i0 / 2 - 1; i < i1 / 2 + 1; i++)
456 p[2 * i + 1] -= (I_LFTG_GAMMA * (p[2 * i] + p[2 * i + 2]) + (1 << 15)) >> 16;
458 for (i = i0 / 2; i < i1 / 2 + 1; i++)
459 p[2 * i] += (I_LFTG_BETA * (p[2 * i - 1] + p[2 * i + 1]) + (1 << 15)) >> 16;
461 for (i = i0 / 2; i < i1 / 2; i++)
462 p[2 * i + 1] += (I_LFTG_ALPHA * (p[2 * i] + p[2 * i + 2]) + (1 << 15)) >> 16;
465 static void dwt_decode97_int(DWTContext *s, int32_t *t)
468 int w = s->linelen[s->ndeclevels - 1][0];
469 int32_t *line = s->i_linebuf;
471 /* position at index O of line range [0-5,w+5] cf. extend function */
474 for (lev = 0; lev < s->ndeclevels; lev++) {
475 int lh = s->linelen[lev][0],
476 lv = s->linelen[lev][1],
483 for (lp = 0; lp < lv; lp++) {
485 // rescale with interleaving
486 for (i = mh; i < lh; i += 2, j++)
487 l[i] = ((data[w * lp + j] * I_LFTG_K) + (1 << 15)) >> 16;
488 for (i = 1 - mh; i < lh; i += 2, j++)
489 l[i] = ((data[w * lp + j] * I_LFTG_X) + (1 << 15)) >> 16;
491 sr_1d97_int(line, mh, mh + lh);
493 for (i = 0; i < lh; i++)
494 data[w * lp + i] = l[i];
499 for (lp = 0; lp < lh; lp++) {
501 // rescale with interleaving
502 for (i = mv; i < lv; i += 2, j++)
503 l[i] = ((data[w * j + lp] * I_LFTG_K) + (1 << 15)) >> 16;
504 for (i = 1 - mv; i < lv; i += 2, j++)
505 l[i] = ((data[w * j + lp] * I_LFTG_X) + (1 << 15)) >> 16;
507 sr_1d97_int(line, mv, mv + lv);
509 for (i = 0; i < lv; i++)
510 data[w * i + lp] = l[i];
515 int ff_jpeg2000_dwt_init(DWTContext *s, uint16_t border[2][2],
516 int decomp_levels, int type)
518 int i, j, lev = decomp_levels, maxlen,
521 s->ndeclevels = decomp_levels;
524 for (i = 0; i < 2; i++)
525 for (j = 0; j < 2; j++)
526 b[i][j] = border[i][j];
528 maxlen = FFMAX(b[0][1] - b[0][0],
531 for (i = 0; i < 2; i++) {
532 s->linelen[lev][i] = b[i][1] - b[i][0];
533 s->mod[lev][i] = b[i][0] & 1;
534 for (j = 0; j < 2; j++)
535 b[i][j] = (b[i][j] + 1) >> 1;
539 s->f_linebuf = av_malloc_array((maxlen + 12), sizeof(*s->f_linebuf));
541 return AVERROR(ENOMEM);
544 s->i_linebuf = av_malloc_array((maxlen + 12), sizeof(*s->i_linebuf));
546 return AVERROR(ENOMEM);
549 s->i_linebuf = av_malloc_array((maxlen + 6), sizeof(*s->i_linebuf));
551 return AVERROR(ENOMEM);
559 int ff_dwt_encode(DWTContext *s, void *t)
563 dwt_encode97_float(s, t); break;
565 dwt_encode97_int(s, t); break;
567 dwt_encode53(s, t); break;
574 int ff_dwt_decode(DWTContext *s, void *t)
578 dwt_decode97_float(s, t);
581 dwt_decode97_int(s, t);
592 void ff_dwt_destroy(DWTContext *s)
594 av_freep(&s->f_linebuf);
595 av_freep(&s->i_linebuf);