j2k/jpeg2000: merge j2k & jpeg2000 dwts, drop j2k dwt
[ffmpeg.git] / libavcodec / jpeg2000dwt.c
1 /*
2  * Discrete wavelet transform
3  * Copyright (c) 2007 Kamil Nowosad
4  * Copyright (c) 2013 Nicolas Bertrand <nicoinattendu@gmail.com>
5  *
6  * This file is part of FFmpeg.
7  *
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.
12  *
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.
17  *
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
21  */
22
23 /**
24  * @file
25  * Discrete wavelet transform
26  */
27
28 #include "libavutil/common.h"
29 #include "libavutil/mem.h"
30 #include "jpeg2000dwt.h"
31 #include "internal.h"
32
33 /* Defines for 9/7 DWT lifting parameters.
34  * Parameters are in float. */
35 #define F_LFTG_ALPHA  1.586134342059924f
36 #define F_LFTG_BETA   0.052980118572961f
37 #define F_LFTG_GAMMA  0.882911075530934f
38 #define F_LFTG_DELTA  0.443506852043971f
39 #define F_LFTG_K      1.230174104914001f
40 #define F_LFTG_X      1.625732422f
41 /* FIXME: Why use 1.625732422 instead of 1/F_LFTG_K?
42  * Incorrect value in JPEG2000 norm.
43  * see (ISO/IEC 15444:1 (version 2002) F.3.8.2 */
44
45 /* Lifting parameters in integer format.
46  * Computed as param = (float param) * (1 << 16) */
47 #define I_LFTG_ALPHA  103949
48 #define I_LFTG_BETA     3472
49 #define I_LFTG_GAMMA   57862
50 #define I_LFTG_DELTA   29066
51 #define I_LFTG_K       80621
52 #define I_LFTG_X      106544
53
54 static inline void extend53(int *p, int i0, int i1)
55 {
56     p[i0 - 1] = p[i0 + 1];
57     p[i1]     = p[i1 - 2];
58     p[i0 - 2] = p[i0 + 2];
59     p[i1 + 1] = p[i1 - 3];
60 }
61
62 static inline void extend97_float(float *p, int i0, int i1)
63 {
64     int i;
65
66     for (i = 1; i <= 4; i++) {
67         p[i0 - i]     = p[i0 + i];
68         p[i1 + i - 1] = p[i1 - i - 1];
69     }
70 }
71
72 static inline void extend97_int(int32_t *p, int i0, int i1)
73 {
74     int i;
75
76     for (i = 1; i <= 4; i++) {
77         p[i0 - i]     = p[i0 + i];
78         p[i1 + i - 1] = p[i1 - i - 1];
79     }
80 }
81
82 static void sd_1d53(int *p, int i0, int i1)
83 {
84     int i;
85
86     if (i1 == i0 + 1)
87         return;
88
89     extend53(p, i0, i1);
90
91     for (i = (i0+1)/2 - 1; i < (i1+1)/2; i++)
92         p[2*i+1] -= (p[2*i] + p[2*i+2]) >> 1;
93     for (i = (i0+1)/2; i < (i1+1)/2; i++)
94         p[2*i] += (p[2*i-1] + p[2*i+1] + 2) >> 2;
95 }
96
97 static void dwt_encode53(DWTContext *s, int *t)
98 {
99     int lev,
100         w = s->linelen[s->ndeclevels-1][0];
101     int *line = s->i_linebuf;
102     line += 3;
103
104     for (lev = s->ndeclevels-1; lev >= 0; lev--){
105         int lh = s->linelen[lev][0],
106             lv = s->linelen[lev][1],
107             mh = s->mod[lev][0],
108             mv = s->mod[lev][1],
109             lp;
110         int *l;
111
112         // HOR_SD
113         l = line + mh;
114         for (lp = 0; lp < lv; lp++){
115             int i, j = 0;
116
117             for (i = 0; i < lh; i++)
118                 l[i] = t[w*lp + i];
119
120             sd_1d53(line, mh, mh + lh);
121
122             // copy back and deinterleave
123             for (i =   mh; i < lh; i+=2, j++)
124                 t[w*lp + j] = l[i];
125             for (i = 1-mh; i < lh; i+=2, j++)
126                 t[w*lp + j] = l[i];
127         }
128
129         // VER_SD
130         l = line + mv;
131         for (lp = 0; lp < lh; lp++) {
132             int i, j = 0;
133
134             for (i = 0; i < lv; i++)
135                 l[i] = t[w*i + lp];
136
137             sd_1d53(line, mv, mv + lv);
138
139             // copy back and deinterleave
140             for (i =   mv; i < lv; i+=2, j++)
141                 t[w*j + lp] = l[i];
142             for (i = 1-mv; i < lv; i+=2, j++)
143                 t[w*j + lp] = l[i];
144         }
145     }
146 }
147
148 static void sd_1d97(float *p, int i0, int i1)
149 {
150     int i;
151
152     if (i1 == i0 + 1)
153         return;
154
155     extend97_float(p, i0, i1);
156     i0++; i1++;
157
158     for (i = i0/2 - 2; i < i1/2 + 1; i++)
159         p[2*i+1] -= 1.586134 * (p[2*i] + p[2*i+2]);
160     for (i = i0/2 - 1; i < i1/2 + 1; i++)
161         p[2*i] -= 0.052980 * (p[2*i-1] + p[2*i+1]);
162     for (i = i0/2 - 1; i < i1/2; i++)
163         p[2*i+1] += 0.882911 * (p[2*i] + p[2*i+2]);
164     for (i = i0/2; i < i1/2; i++)
165         p[2*i] += 0.443506 * (p[2*i-1] + p[2*i+1]);
166 }
167
168 static void dwt_encode97_int(DWTContext *s, int *t)
169 {
170     int lev,
171         w = s->linelen[s->ndeclevels-1][0];
172     float *line = s->i_linebuf;
173     line += 5;
174
175     for (lev = s->ndeclevels-1; lev >= 0; lev--){
176         int lh = s->linelen[lev][0],
177             lv = s->linelen[lev][1],
178             mh = s->mod[lev][0],
179             mv = s->mod[lev][1],
180             lp;
181         float *l;
182
183         // HOR_SD
184         l = line + mh;
185         for (lp = 0; lp < lv; lp++){
186             int i, j = 0;
187
188             for (i = 0; i < lh; i++)
189                 l[i] = t[w*lp + i];
190
191             sd_1d97(line, mh, mh + lh);
192
193             // copy back and deinterleave
194             for (i =   mh; i < lh; i+=2, j++)
195                 t[w*lp + j] = F_LFTG_X * l[i] / 2;
196             for (i = 1-mh; i < lh; i+=2, j++)
197                 t[w*lp + j] = F_LFTG_K * l[i] / 2;
198         }
199
200         // VER_SD
201         l = line + mv;
202         for (lp = 0; lp < lh; lp++) {
203             int i, j = 0;
204
205             for (i = 0; i < lv; i++)
206                 l[i] = t[w*i + lp];
207
208             sd_1d97(line, mv, mv + lv);
209
210             // copy back and deinterleave
211             for (i =   mv; i < lv; i+=2, j++)
212                 t[w*j + lp] = F_LFTG_X * l[i] / 2;
213             for (i = 1-mv; i < lv; i+=2, j++)
214                 t[w*j + lp] = F_LFTG_K * l[i] / 2;
215         }
216     }
217 }
218
219 static void sr_1d53(int *p, int i0, int i1)
220 {
221     int i;
222
223     if (i1 == i0 + 1)
224         return;
225
226     extend53(p, i0, i1);
227
228     for (i = i0 / 2; i < i1 / 2 + 1; i++)
229         p[2 * i] -= (p[2 * i - 1] + p[2 * i + 1] + 2) >> 2;
230     for (i = i0 / 2; i < i1 / 2; i++)
231         p[2 * i + 1] += (p[2 * i] + p[2 * i + 2]) >> 1;
232 }
233
234 static void dwt_decode53(DWTContext *s, int *t)
235 {
236     int lev;
237     int w     = s->linelen[s->ndeclevels - 1][0];
238     int32_t *line = s->i_linebuf;
239     line += 3;
240
241     for (lev = 0; lev < s->ndeclevels; lev++) {
242         int lh = s->linelen[lev][0],
243             lv = s->linelen[lev][1],
244             mh = s->mod[lev][0],
245             mv = s->mod[lev][1],
246             lp;
247         int *l;
248
249         // HOR_SD
250         l = line + mh;
251         for (lp = 0; lp < lv; lp++) {
252             int i, j = 0;
253             // copy with interleaving
254             for (i = mh; i < lh; i += 2, j++)
255                 l[i] = t[w * lp + j];
256             for (i = 1 - mh; i < lh; i += 2, j++)
257                 l[i] = t[w * lp + j];
258
259             sr_1d53(line, mh, mh + lh);
260
261             for (i = 0; i < lh; i++)
262                 t[w * lp + i] = l[i];
263         }
264
265         // VER_SD
266         l = line + mv;
267         for (lp = 0; lp < lh; lp++) {
268             int i, j = 0;
269             // copy with interleaving
270             for (i = mv; i < lv; i += 2, j++)
271                 l[i] = t[w * j + lp];
272             for (i = 1 - mv; i < lv; i += 2, j++)
273                 l[i] = t[w * j + lp];
274
275             sr_1d53(line, mv, mv + lv);
276
277             for (i = 0; i < lv; i++)
278                 t[w * i + lp] = l[i];
279         }
280     }
281 }
282
283 static void sr_1d97_float(float *p, int i0, int i1)
284 {
285     int i;
286
287     if (i1 == i0 + 1)
288         return;
289
290     extend97_float(p, i0, i1);
291
292     /*step 1*/
293     for (i = i0 / 2 - 1; i < i1 / 2 + 2; i++)
294         p[2 * i]     *= F_LFTG_K;
295     /* step 2*/
296     for (i = i0 / 2 - 2; i < i1 / 2 + 2; i++)
297         p[2 * i + 1] *= F_LFTG_X;
298     /* step 3*/
299     for (i = i0 / 2 - 1; i < i1 / 2 + 2; i++)
300         p[2 * i]     -= F_LFTG_DELTA * (p[2 * i - 1] + p[2 * i + 1]);
301     /* step 4 */
302     for (i = i0 / 2 - 1; i < i1 / 2 + 1; i++)
303         p[2 * i + 1] -= F_LFTG_GAMMA * (p[2 * i]     + p[2 * i + 2]);
304     /*step 5*/
305     for (i = i0 / 2; i < i1 / 2 + 1; i++)
306         p[2 * i]     += F_LFTG_BETA  * (p[2 * i - 1] + p[2 * i + 1]);
307     /* step 6 */
308     for (i = i0 / 2; i < i1 / 2; i++)
309         p[2 * i + 1] += F_LFTG_ALPHA * (p[2 * i]     + p[2 * i + 2]);
310 }
311
312 static void dwt_decode97_float(DWTContext *s, float *t)
313 {
314     int lev;
315     int w       = s->linelen[s->ndeclevels - 1][0];
316     float *line = s->f_linebuf;
317     float *data = t;
318     /* position at index O of line range [0-5,w+5] cf. extend function */
319     line += 5;
320
321     for (lev = 0; lev < s->ndeclevels; lev++) {
322         int lh = s->linelen[lev][0],
323             lv = s->linelen[lev][1],
324             mh = s->mod[lev][0],
325             mv = s->mod[lev][1],
326             lp;
327         float *l;
328         // HOR_SD
329         l = line + mh;
330         for (lp = 0; lp < lv; lp++) {
331             int i, j = 0;
332             // copy with interleaving
333             for (i = mh; i < lh; i += 2, j++)
334                 l[i] = data[w * lp + j];
335             for (i = 1 - mh; i < lh; i += 2, j++)
336                 l[i] = data[w * lp + j];
337
338             sr_1d97_float(line, mh, mh + lh);
339
340             for (i = 0; i < lh; i++)
341                 data[w * lp + i] = l[i];
342         }
343
344         // VER_SD
345         l = line + mv;
346         for (lp = 0; lp < lh; lp++) {
347             int i, j = 0;
348             // copy with interleaving
349             for (i = mv; i < lv; i += 2, j++)
350                 l[i] = data[w * j + lp];
351             for (i = 1 - mv; i < lv; i += 2, j++)
352                 l[i] = data[w * j + lp];
353
354             sr_1d97_float(line, mv, mv + lv);
355
356             for (i = 0; i < lv; i++)
357                 data[w * i + lp] = l[i];
358         }
359     }
360 }
361
362 static void sr_1d97_int(int32_t *p, int i0, int i1)
363 {
364     int i;
365
366     if (i1 == i0 + 1)
367         return;
368
369     extend97_int(p, i0, i1);
370
371     /*step 1*/
372     for (i = i0 / 2 - 1; i < i1 / 2 + 2; i++)
373         p[2 * i]      = ((p[2 * i] * I_LFTG_K)     + (1 << 15)) >> 16;
374     /* step 2*/
375     for (i = i0 / 2 - 2; i < i1 / 2 + 2; i++)
376         p[2 * i + 1]  = ((p[2 * i + 1] * I_LFTG_X) + (1 << 15)) >> 16;
377     /* step 3*/
378     for (i = i0 / 2 - 1; i < i1 / 2 + 2; i++)
379         p[2 * i]     -= (I_LFTG_DELTA * (p[2 * i - 1] + p[2 * i + 1]) + (1 << 15)) >> 16;
380     /* step 4 */
381     for (i = i0 / 2 - 1; i < i1 / 2 + 1; i++)
382         p[2 * i + 1] -= (I_LFTG_GAMMA * (p[2 * i]     + p[2 * i + 2]) + (1 << 15)) >> 16;
383     /*step 5*/
384     for (i = i0 / 2; i < i1 / 2 + 1; i++)
385         p[2 * i]     += (I_LFTG_BETA  * (p[2 * i - 1] + p[2 * i + 1]) + (1 << 15)) >> 16;
386     /* step 6 */
387     for (i = i0 / 2; i < i1 / 2; i++)
388         p[2 * i + 1] += (I_LFTG_ALPHA * (p[2 * i]     + p[2 * i + 2]) + (1 << 15)) >> 16;
389 }
390
391 static void dwt_decode97_int(DWTContext *s, int32_t *t)
392 {
393     int lev;
394     int w       = s->linelen[s->ndeclevels - 1][0];
395     int32_t *line = s->i_linebuf;
396     int32_t *data = t;
397     /* position at index O of line range [0-5,w+5] cf. extend function */
398     line += 5;
399
400     for (lev = 0; lev < s->ndeclevels; lev++) {
401         int lh = s->linelen[lev][0],
402             lv = s->linelen[lev][1],
403             mh = s->mod[lev][0],
404             mv = s->mod[lev][1],
405             lp;
406         int32_t *l;
407         // HOR_SD
408         l = line + mh;
409         for (lp = 0; lp < lv; lp++) {
410             int i, j = 0;
411             // copy with interleaving
412             for (i = mh; i < lh; i += 2, j++)
413                 l[i] = data[w * lp + j];
414             for (i = 1 - mh; i < lh; i += 2, j++)
415                 l[i] = data[w * lp + j];
416
417             sr_1d97_int(line, mh, mh + lh);
418
419             for (i = 0; i < lh; i++)
420                 data[w * lp + i] = l[i];
421         }
422
423         // VER_SD
424         l = line + mv;
425         for (lp = 0; lp < lh; lp++) {
426             int i, j = 0;
427             // copy with interleaving
428             for (i = mv; i < lv; i += 2, j++)
429                 l[i] = data[w * j + lp];
430             for (i = 1 - mv; i < lv; i += 2, j++)
431                 l[i] = data[w * j + lp];
432
433             sr_1d97_int(line, mv, mv + lv);
434
435             for (i = 0; i < lv; i++)
436                 data[w * i + lp] = l[i];
437         }
438     }
439 }
440
441 int ff_jpeg2000_dwt_init(DWTContext *s, uint16_t border[2][2],
442                          int decomp_levels, int type)
443 {
444     int i, j, lev = decomp_levels, maxlen,
445         b[2][2];
446
447     s->ndeclevels = decomp_levels;
448     s->type       = type;
449
450     for (i = 0; i < 2; i++)
451         for (j = 0; j < 2; j++)
452             b[i][j] = border[i][j];
453
454     maxlen = FFMAX(b[0][1] - b[0][0],
455                    b[1][1] - b[1][0]);
456     while (--lev >= 0)
457         for (i = 0; i < 2; i++) {
458             s->linelen[lev][i] = b[i][1] - b[i][0];
459             s->mod[lev][i]     = b[i][0] & 1;
460             for (j = 0; j < 2; j++)
461                 b[i][j] = (b[i][j] + 1) >> 1;
462         }
463     switch (type) {
464     case FF_DWT97:
465         s->f_linebuf = av_malloc((maxlen + 12) * sizeof(*s->f_linebuf));
466         if (!s->f_linebuf)
467             return AVERROR(ENOMEM);
468         break;
469      case FF_DWT97_INT:
470         s->i_linebuf = av_malloc((maxlen + 12) * sizeof(*s->i_linebuf));
471         if (!s->i_linebuf)
472             return AVERROR(ENOMEM);
473         break;
474     case FF_DWT53:
475         s->i_linebuf = av_malloc((maxlen +  6) * sizeof(*s->i_linebuf));
476         if (!s->i_linebuf)
477             return AVERROR(ENOMEM);
478         break;
479     default:
480         return -1;
481     }
482     return 0;
483 }
484
485 int ff_dwt_encode(DWTContext *s, int *t)
486 {
487     switch(s->type){
488         case FF_DWT97_INT:
489             dwt_encode97_int(s, t); break;
490         case FF_DWT53:
491             dwt_encode53(s, t); break;
492         default:
493             return -1;
494     }
495     return 0;
496 }
497
498 int ff_dwt_decode(DWTContext *s, void *t)
499 {
500     switch (s->type) {
501     case FF_DWT97:
502         dwt_decode97_float(s, t);
503         break;
504     case FF_DWT97_INT:
505         dwt_decode97_int(s, t);
506         break;
507     case FF_DWT53:
508         dwt_decode53(s, t);
509         break;
510     default:
511         return -1;
512     }
513     return 0;
514 }
515
516 void ff_dwt_destroy(DWTContext *s)
517 {
518     av_freep(&s->f_linebuf);
519     av_freep(&s->i_linebuf);
520 }