git.sesse.net Git - ffmpeg/blob - 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/avassert.h"
  29 #include "libavutil/common.h"
  30 #include "libavutil/mem.h"
  31 #include "jpeg2000dwt.h"
  32 #include "internal.h"
  33
  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 */
  45
  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
  54
  55 static inline void extend53(int *p, int i0, int i1)
  56 {
  57     p[i0 - 1] = p[i0 + 1];
  58     p[i1]     = p[i1 - 2];
  59     p[i0 - 2] = p[i0 + 2];
  60     p[i1 + 1] = p[i1 - 3];
  61 }
  62
  63 static inline void extend97_float(float *p, int i0, int i1)
  64 {
  65     int i;
  66
  67     for (i = 1; i <= 4; i++) {
  68         p[i0 - i]     = p[i0 + i];
  69         p[i1 + i - 1] = p[i1 - i - 1];
  70     }
  71 }
  72
  73 static inline void extend97_int(int32_t *p, int i0, int i1)
  74 {
  75     int i;
  76
  77     for (i = 1; i <= 4; i++) {
  78         p[i0 - i]     = p[i0 + i];
  79         p[i1 + i - 1] = p[i1 - i - 1];
  80     }
  81 }
  82
  83 static void sd_1d53(int *p, int i0, int i1)
  84 {
  85     int i;
  86
  87     if (i1 == i0 + 1)
  88         return;
  89
  90     extend53(p, i0, i1);
  91
  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;
  96 }
  97
  98 static void dwt_encode53(DWTContext *s, int *t)
  99 {
 100     int lev,
 101         w = s->linelen[s->ndeclevels-1][0];
 102     int *line = s->i_linebuf;
 103     line += 3;
 104
 105     for (lev = s->ndeclevels-1; lev >= 0; lev--){
 106         int lh = s->linelen[lev][0],
 107             lv = s->linelen[lev][1],
 108             mh = s->mod[lev][0],
 109             mv = s->mod[lev][1],
 110             lp;
 111         int *l;
 112
 113         av_assert1(!mh && !mv);
 114         // HOR_SD
 115         l = line + mh;
 116         for (lp = 0; lp < lv; lp++){
 117             int i, j = 0;
 118
 119             for (i = 0; i < lh; i++)
 120                 l[i] = t[w*lp + i];
 121
 122             sd_1d53(line, mh, mh + lh);
 123
 124             // copy back and deinterleave
 125             for (i =   mh; i < lh; i+=2, j++)
 126                 t[w*lp + j] = l[i];
 127             for (i = 1-mh; i < lh; i+=2, j++)
 128                 t[w*lp + j] = l[i];
 129         }
 130
 131         // VER_SD
 132         l = line + mv;
 133         for (lp = 0; lp < lh; lp++) {
 134             int i, j = 0;
 135
 136             for (i = 0; i < lv; i++)
 137                 l[i] = t[w*i + lp];
 138
 139             sd_1d53(line, mv, mv + lv);
 140
 141             // copy back and deinterleave
 142             for (i =   mv; i < lv; i+=2, j++)
 143                 t[w*j + lp] = l[i];
 144             for (i = 1-mv; i < lv; i+=2, j++)
 145                 t[w*j + lp] = l[i];
 146         }
 147     }
 148 }
 149 static void sd_1d97_float(float *p, int i0, int i1)
 150 {
 151     int i;
 152
 153     if (i1 == i0 + 1)
 154         return;
 155
 156     extend97_float(p, i0, i1);
 157     i0++; i1++;
 158
 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]);
 167 }
 168
 169 static void dwt_encode97_float(DWTContext *s, float *t)
 170 {
 171     int lev,
 172         w = s->linelen[s->ndeclevels-1][0];
 173     float *line = s->f_linebuf;
 174     line += 5;
 175
 176     for (lev = s->ndeclevels-1; lev >= 0; lev--){
 177         int lh = s->linelen[lev][0],
 178             lv = s->linelen[lev][1],
 179             mh = s->mod[lev][0],
 180             mv = s->mod[lev][1],
 181             lp;
 182         float *l;
 183
 184         av_assert1(!mh && !mv);
 185         // HOR_SD
 186         l = line + mh;
 187         for (lp = 0; lp < lv; lp++){
 188             int i, j = 0;
 189
 190             for (i = 0; i < lh; i++)
 191                 l[i] = t[w*lp + i];
 192
 193             sd_1d97_float(line, mh, mh + lh);
 194
 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;
 200         }
 201
 202         // VER_SD
 203         l = line + mv;
 204         for (lp = 0; lp < lh; lp++) {
 205             int i, j = 0;
 206
 207             for (i = 0; i < lv; i++)
 208                 l[i] = t[w*i + lp];
 209
 210             sd_1d97_float(line, mv, mv + lv);
 211
 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;
 217         }
 218     }
 219 }
 220
 221 static void sd_1d97_int(int *p, int i0, int i1)
 222 {
 223     int i;
 224
 225     if (i1 == i0 + 1)
 226         return;
 227
 228     extend97_int(p, i0, i1);
 229     i0++; i1++;
 230
 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;
 239 }
 240
 241 static void dwt_encode97_int(DWTContext *s, int *t)
 242 {
 243     int lev,
 244         w = s->linelen[s->ndeclevels-1][0];
 245     int *line = s->i_linebuf;
 246     line += 5;
 247
 248     for (lev = s->ndeclevels-1; lev >= 0; lev--){
 249         int lh = s->linelen[lev][0],
 250             lv = s->linelen[lev][1],
 251             mh = s->mod[lev][0],
 252             mv = s->mod[lev][1],
 253             lp;
 254         int *l;
 255
 256         av_assert1(!mh && !mv);
 257
 258         // HOR_SD
 259         l = line + mh;
 260         for (lp = 0; lp < lv; lp++){
 261             int i, j = 0;
 262
 263             for (i = 0; i < lh; i++)
 264                 l[i] = t[w*lp + i];
 265
 266             sd_1d97_int(line, mh, mh + lh);
 267
 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;
 273         }
 274
 275         // VER_SD
 276         l = line + mv;
 277         for (lp = 0; lp < lh; lp++) {
 278             int i, j = 0;
 279
 280             for (i = 0; i < lv; i++)
 281                 l[i] = t[w*i + lp];
 282
 283             sd_1d97_int(line, mv, mv + lv);
 284
 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;
 290         }
 291     }
 292 }
 293
 294 static void sr_1d53(int *p, int i0, int i1)
 295 {
 296     int i;
 297
 298     if (i1 <= i0 + 1) {
 299         if (i0 == 1)
 300             p[1] >>= 1;
 301         return;
 302     }
 303
 304     extend53(p, i0, i1);
 305
 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;
 310 }
 311
 312 static void dwt_decode53(DWTContext *s, int *t)
 313 {
 314     int lev;
 315     int w     = s->linelen[s->ndeclevels - 1][0];
 316     int32_t *line = s->i_linebuf;
 317     line += 3;
 318
 319     for (lev = 0; lev < s->ndeclevels; lev++) {
 320         int lh = s->linelen[lev][0],
 321             lv = s->linelen[lev][1],
 322             mh = s->mod[lev][0],
 323             mv = s->mod[lev][1],
 324             lp;
 325         int *l;
 326
 327         // HOR_SD
 328         l = line + mh;
 329         for (lp = 0; lp < lv; lp++) {
 330             int i, j = 0;
 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];
 336
 337             sr_1d53(line, mh, mh + lh);
 338
 339             for (i = 0; i < lh; i++)
 340                 t[w * lp + i] = l[i];
 341         }
 342
 343         // VER_SD
 344         l = line + mv;
 345         for (lp = 0; lp < lh; lp++) {
 346             int i, j = 0;
 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];
 352
 353             sr_1d53(line, mv, mv + lv);
 354
 355             for (i = 0; i < lv; i++)
 356                 t[w * i + lp] = l[i];
 357         }
 358     }
 359 }
 360
 361 static void sr_1d97_float(float *p, int i0, int i1)
 362 {
 363     int i;
 364
 365     if (i1 <= i0 + 1) {
 366         if (i0 == 1)
 367             p[1] *= F_LFTG_K/2;
 368         return;
 369     }
 370
 371     extend97_float(p, i0, i1);
 372
 373     for (i = i0 / 2 - 1; i < i1 / 2 + 2; i++)
 374         p[2 * i]     -= F_LFTG_DELTA * (p[2 * i - 1] + p[2 * i + 1]);
 375     /* step 4 */
 376     for (i = i0 / 2 - 1; i < i1 / 2 + 1; i++)
 377         p[2 * i + 1] -= F_LFTG_GAMMA * (p[2 * i]     + p[2 * i + 2]);
 378     /*step 5*/
 379     for (i = i0 / 2; i < i1 / 2 + 1; i++)
 380         p[2 * i]     += F_LFTG_BETA  * (p[2 * i - 1] + p[2 * i + 1]);
 381     /* step 6 */
 382     for (i = i0 / 2; i < i1 / 2; i++)
 383         p[2 * i + 1] += F_LFTG_ALPHA * (p[2 * i]     + p[2 * i + 2]);
 384 }
 385
 386 static void dwt_decode97_float(DWTContext *s, float *t)
 387 {
 388     int lev;
 389     int w       = s->linelen[s->ndeclevels - 1][0];
 390     float *line = s->f_linebuf;
 391     float *data = t;
 392     /* position at index O of line range [0-5,w+5] cf. extend function */
 393     line += 5;
 394
 395     for (lev = 0; lev < s->ndeclevels; lev++) {
 396         int lh = s->linelen[lev][0],
 397             lv = s->linelen[lev][1],
 398             mh = s->mod[lev][0],
 399             mv = s->mod[lev][1],
 400             lp;
 401         float *l;
 402         // HOR_SD
 403         l = line + mh;
 404         for (lp = 0; lp < lv; lp++) {
 405             int i, j = 0;
 406             // copy with interleaving
 407             for (i = mh; i < lh; i += 2, j++)
 408                 l[i] = data[w * lp + j] * F_LFTG_K;
 409             for (i = 1 - mh; i < lh; i += 2, j++)
 410                 l[i] = data[w * lp + j] * F_LFTG_X;
 411
 412             sr_1d97_float(line, mh, mh + lh);
 413
 414             for (i = 0; i < lh; i++)
 415                 data[w * lp + i] = l[i];
 416         }
 417
 418         // VER_SD
 419         l = line + mv;
 420         for (lp = 0; lp < lh; lp++) {
 421             int i, j = 0;
 422             // copy with interleaving
 423             for (i = mv; i < lv; i += 2, j++)
 424                 l[i] = data[w * j + lp] * F_LFTG_K;
 425             for (i = 1 - mv; i < lv; i += 2, j++)
 426                 l[i] = data[w * j + lp] * F_LFTG_X;
 427
 428             sr_1d97_float(line, mv, mv + lv);
 429
 430             for (i = 0; i < lv; i++)
 431                 data[w * i + lp] = l[i];
 432         }
 433     }
 434 }
 435
 436 static void sr_1d97_int(int32_t *p, int i0, int i1)
 437 {
 438     int i;
 439
 440     if (i1 <= i0 + 1) {
 441         if (i0 == 1)
 442             p[1] = (p[1] * I_LFTG_K + (1<<16)) >> 17;
 443         return;
 444     }
 445
 446     extend97_int(p, i0, i1);
 447
 448     for (i = i0 / 2 - 1; i < i1 / 2 + 2; i++)
 449         p[2 * i]     -= (I_LFTG_DELTA * (p[2 * i - 1] + p[2 * i + 1]) + (1 << 15)) >> 16;
 450     /* step 4 */
 451     for (i = i0 / 2 - 1; i < i1 / 2 + 1; i++)
 452         p[2 * i + 1] -= (I_LFTG_GAMMA * (p[2 * i]     + p[2 * i + 2]) + (1 << 15)) >> 16;
 453     /*step 5*/
 454     for (i = i0 / 2; i < i1 / 2 + 1; i++)
 455         p[2 * i]     += (I_LFTG_BETA  * (p[2 * i - 1] + p[2 * i + 1]) + (1 << 15)) >> 16;
 456     /* step 6 */
 457     for (i = i0 / 2; i < i1 / 2; i++)
 458         p[2 * i + 1] += (I_LFTG_ALPHA * (p[2 * i]     + p[2 * i + 2]) + (1 << 15)) >> 16;
 459 }
 460
 461 static void dwt_decode97_int(DWTContext *s, int32_t *t)
 462 {
 463     int lev;
 464     int w       = s->linelen[s->ndeclevels - 1][0];
 465     int32_t *line = s->i_linebuf;
 466     int32_t *data = t;
 467     /* position at index O of line range [0-5,w+5] cf. extend function */
 468     line += 5;
 469
 470     for (lev = 0; lev < s->ndeclevels; lev++) {
 471         int lh = s->linelen[lev][0],
 472             lv = s->linelen[lev][1],
 473             mh = s->mod[lev][0],
 474             mv = s->mod[lev][1],
 475             lp;
 476         int32_t *l;
 477         // HOR_SD
 478         l = line + mh;
 479         for (lp = 0; lp < lv; lp++) {
 480             int i, j = 0;
 481             // rescale with interleaving
 482             for (i = mh; i < lh; i += 2, j++)
 483                 l[i] = ((data[w * lp + j] * I_LFTG_K) + (1 << 15)) >> 16;
 484             for (i = 1 - mh; i < lh; i += 2, j++)
 485                 l[i] = ((data[w * lp + j] * I_LFTG_X) + (1 << 15)) >> 16;
 486
 487             sr_1d97_int(line, mh, mh + lh);
 488
 489             for (i = 0; i < lh; i++)
 490                 data[w * lp + i] = l[i];
 491         }
 492
 493         // VER_SD
 494         l = line + mv;
 495         for (lp = 0; lp < lh; lp++) {
 496             int i, j = 0;
 497             // rescale with interleaving
 498             for (i = mv; i < lv; i += 2, j++)
 499                 l[i] = ((data[w * j + lp] * I_LFTG_K) + (1 << 15)) >> 16;
 500             for (i = 1 - mv; i < lv; i += 2, j++)
 501                 l[i] = ((data[w * j + lp] * I_LFTG_X) + (1 << 15)) >> 16;
 502
 503             sr_1d97_int(line, mv, mv + lv);
 504
 505             for (i = 0; i < lv; i++)
 506                 data[w * i + lp] = l[i];
 507         }
 508     }
 509 }
 510
 511 int ff_jpeg2000_dwt_init(DWTContext *s, uint16_t border[2][2],
 512                          int decomp_levels, int type)
 513 {
 514     int i, j, lev = decomp_levels, maxlen,
 515         b[2][2];
 516
 517     s->ndeclevels = decomp_levels;
 518     s->type       = type;
 519
 520     for (i = 0; i < 2; i++)
 521         for (j = 0; j < 2; j++)
 522             b[i][j] = border[i][j];
 523
 524     maxlen = FFMAX(b[0][1] - b[0][0],
 525                    b[1][1] - b[1][0]);
 526     while (--lev >= 0)
 527         for (i = 0; i < 2; i++) {
 528             s->linelen[lev][i] = b[i][1] - b[i][0];
 529             s->mod[lev][i]     = b[i][0] & 1;
 530             for (j = 0; j < 2; j++)
 531                 b[i][j] = (b[i][j] + 1) >> 1;
 532         }
 533     switch (type) {
 534     case FF_DWT97:
 535         s->f_linebuf = av_malloc_array((maxlen + 12), sizeof(*s->f_linebuf));
 536         if (!s->f_linebuf)
 537             return AVERROR(ENOMEM);
 538         break;
 539      case FF_DWT97_INT:
 540         s->i_linebuf = av_malloc_array((maxlen + 12), sizeof(*s->i_linebuf));
 541         if (!s->i_linebuf)
 542             return AVERROR(ENOMEM);
 543         break;
 544     case FF_DWT53:
 545         s->i_linebuf = av_malloc_array((maxlen +  6), sizeof(*s->i_linebuf));
 546         if (!s->i_linebuf)
 547             return AVERROR(ENOMEM);
 548         break;
 549     default:
 550         return -1;
 551     }
 552     return 0;
 553 }
 554
 555 int ff_dwt_encode(DWTContext *s, void *t)
 556 {
 557     switch(s->type){
 558         case FF_DWT97:
 559             dwt_encode97_float(s, t); break;
 560         case FF_DWT97_INT:
 561             dwt_encode97_int(s, t); break;
 562         case FF_DWT53:
 563             dwt_encode53(s, t); break;
 564         default:
 565             return -1;
 566     }
 567     return 0;
 568 }
 569
 570 int ff_dwt_decode(DWTContext *s, void *t)
 571 {
 572     switch (s->type) {
 573     case FF_DWT97:
 574         dwt_decode97_float(s, t);
 575         break;
 576     case FF_DWT97_INT:
 577         dwt_decode97_int(s, t);
 578         break;
 579     case FF_DWT53:
 580         dwt_decode53(s, t);
 581         break;
 582     default:
 583         return -1;
 584     }
 585     return 0;
 586 }
 587
 588 void ff_dwt_destroy(DWTContext *s)
 589 {
 590     av_freep(&s->f_linebuf);
 591     av_freep(&s->i_linebuf);
 592 }