libopenjpeg/tgt.c

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