src/gdcmopenjpeg/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 }