src/lib/openjp3d/tgt.c

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