libopenjpeg/tgt.c

   1 /*
   2  * Copyright (c) 2001-2003, David Janssens
   3  * Copyright (c) 2002-2003, Yannick Verschueren
   4  * Copyright (c) 2003-2005, Francois Devaux and Antonin Descampe
   5  * Copyright (c) 2005, Herv� Drolon, FreeImage Team
   6  * Copyright (c) 2002-2005, Communications and remote sensing Laboratory, Universite catholique de Louvain, Belgium
   7  * All rights reserved.
   8  *
   9  * Redistribution and use in source and binary forms, with or without
  10  * modification, are permitted provided that the following conditions
  11  * are met:
  12  * 1. Redistributions of source code must retain the above copyright
  13  *    notice, this list of conditions and the following disclaimer.
  14  * 2. Redistributions in binary form must reproduce the above copyright
  15  *    notice, this list of conditions and the following disclaimer in the
  16  *    documentation and/or other materials provided with the distribution.
  17  *
  18  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS `AS IS'
  19  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  20  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  21  * ARE DISCLAIMED.  IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
  22  * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
  23  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
  24  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
  25  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
  26  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  27  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
  28  * POSSIBILITY OF SUCH DAMAGE.
  29  */
  30
  31 #include "opj_includes.h"
  32
  33 /*
  34 ==========================================================
  35    Tag-tree coder interface
  36 ==========================================================
  37 */
  38
  39 opj_tgt_tree_t *tgt_create(int numleafsh, int numleafsv) {
  40         int nplh[32];
  41         int nplv[32];
  42         opj_tgt_node_t *node = NULL;
  43         opj_tgt_node_t *parentnode = NULL;
  44         opj_tgt_node_t *parentnode0 = NULL;
  45         opj_tgt_tree_t *tree = NULL;
  46         int i, j, k;
  47         int numlvls;
  48         int n;
  49
  50         tree = (opj_tgt_tree_t *) opj_malloc(sizeof(opj_tgt_tree_t));
  51         if(!tree) return NULL;
  52         tree->numleafsh = numleafsh;
  53         tree->numleafsv = numleafsv;
  54
  55         numlvls = 0;
  56         nplh[0] = numleafsh;
  57         nplv[0] = numleafsv;
  58         tree->numnodes = 0;
  59         do {
  60                 n = nplh[numlvls] * nplv[numlvls];
  61                 nplh[numlvls + 1] = (nplh[numlvls] + 1) / 2;
  62                 nplv[numlvls + 1] = (nplv[numlvls] + 1) / 2;
  63                 tree->numnodes += n;
  64                 ++numlvls;
  65         } while (n > 1);
  66
  67         /* ADD */
  68         if (tree->numnodes == 0) {
  69                 opj_free(tree);
  70                 return NULL;
  71         }
  72
  73         tree->nodes = (opj_tgt_node_t *) opj_malloc(tree->numnodes * sizeof(opj_tgt_node_t));
  74         if(!tree->nodes) {
  75                 opj_free(tree);
  76                 return NULL;
  77         }
  78
  79         node = tree->nodes;
  80         parentnode = &tree->nodes[tree->numleafsh * tree->numleafsv];
  81         parentnode0 = parentnode;
  82
  83         for (i = 0; i < numlvls - 1; ++i) {
  84                 for (j = 0; j < nplv[i]; ++j) {
  85                         k = nplh[i];
  86                         while (--k >= 0) {
  87                                 node->parent = parentnode;
  88                                 ++node;
  89                                 if (--k >= 0) {
  90                                         node->parent = parentnode;
  91                                         ++node;
  92                                 }
  93                                 ++parentnode;
  94                         }
  95                         if ((j & 1) || j == nplv[i] - 1) {
  96                                 parentnode0 = parentnode;
  97                         } else {
  98                                 parentnode = parentnode0;
  99                                 parentnode0 += nplh[i];
 100                         }
 101                 }
 102         }
 103         node->parent = 0;
 104
 105         tgt_reset(tree);
 106
 107         return tree;
 108 }
 109
 110 void tgt_destroy(opj_tgt_tree_t *tree) {
 111         opj_free(tree->nodes);
 112         opj_free(tree);
 113 }
 114
 115 void tgt_reset(opj_tgt_tree_t *tree) {
 116         int i;
 117
 118         if (NULL == tree)
 119                 return;
 120
 121         for (i = 0; i < tree->numnodes; i++) {
 122                 tree->nodes[i].value = 999;
 123                 tree->nodes[i].low = 0;
 124                 tree->nodes[i].known = 0;
 125         }
 126 }
 127
 128 void tgt_setvalue(opj_tgt_tree_t *tree, int leafno, int value) {
 129         opj_tgt_node_t *node;
 130         node = &tree->nodes[leafno];
 131         while (node && node->value > value) {
 132                 node->value = value;
 133                 node = node->parent;
 134         }
 135 }
 136
 137 void tgt_encode(opj_bio_t *bio, opj_tgt_tree_t *tree, int leafno, int threshold) {
 138         opj_tgt_node_t *stk[31];
 139         opj_tgt_node_t **stkptr;
 140         opj_tgt_node_t *node;
 141         int low;
 142
 143         stkptr = stk;
 144         node = &tree->nodes[leafno];
 145         while (node->parent) {
 146                 *stkptr++ = node;
 147                 node = node->parent;
 148         }
 149
 150         low = 0;
 151         for (;;) {
 152                 if (low > node->low) {
 153                         node->low = low;
 154                 } else {
 155                         low = node->low;
 156                 }
 157
 158                 while (low < threshold) {
 159                         if (low >= node->value) {
 160                                 if (!node->known) {
 161                                         bio_write(bio, 1, 1);
 162                                         node->known = 1;
 163                                 }
 164                                 break;
 165                         }
 166                         bio_write(bio, 0, 1);
 167                         ++low;
 168                 }
 169
 170                 node->low = low;
 171                 if (stkptr == stk)
 172                         break;
 173                 node = *--stkptr;
 174         }
 175 }
 176
 177 int tgt_decode(opj_bio_t *bio, opj_tgt_tree_t *tree, int leafno, int threshold) {
 178         opj_tgt_node_t *stk[31];
 179         opj_tgt_node_t **stkptr;
 180         opj_tgt_node_t *node;
 181         int low;
 182
 183         stkptr = stk;
 184         node = &tree->nodes[leafno];
 185         while (node->parent) {
 186                 *stkptr++ = node;
 187                 node = node->parent;
 188         }
 189
 190         low = 0;
 191         for (;;) {
 192                 if (low > node->low) {
 193                         node->low = low;
 194                 } else {
 195                         low = node->low;
 196                 }
 197                 while (low < threshold && low < node->value) {
 198                         if (bio_read(bio, 1)) {
 199                                 node->value = low;
 200                         } else {
 201                                 ++low;
 202                         }
 203                 }
 204                 node->low = low;
 205                 if (stkptr == stk) {
 206                         break;
 207                 }
 208                 node = *--stkptr;
 209         }
 210
 211         return (node->value < threshold) ? 1 : 0;
 212 }