src/lib/openmj2/tgt.c

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