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 =
  87         (tgt_node_t *) malloc(tree->numnodes * sizeof(tgt_node_t));
  88
  89     node = tree->nodes;
  90     parentnode = &tree->nodes[tree->numleafsh * tree->numleafsv];
  91     parentnode0 = parentnode;
  92
  93     for (i = 0; i < numlvls - 1; ++i) {
  94         for (j = 0; j < nplv[i]; ++j) {
  95             k = nplh[i];
  96             while (--k >= 0) {
  97                 node->parent = parentnode;
  98                 ++node;
  99                 if (--k >= 0) {
 100                     node->parent = parentnode;
 101                     ++node;
 102                 }
 103                 ++parentnode;
 104             }
 105             if ((j & 1) || j == nplv[i] - 1) {
 106                 parentnode0 = parentnode;
 107             } else {
 108                 parentnode = parentnode0;
 109                 parentnode0 += nplh[i];
 110             }
 111         }
 112     }
 113     node->parent = 0;
 114
 115     tgt_reset(tree);
 116
 117     return tree;
 118 }
 119
 120 /* <summary> */
 121 /* Destroy tag-tree. */
 122 /* </summary> */
 123 void tgt_destroy(tgt_tree_t * t)
 124 {
 125     free(t->nodes);
 126     free(t);
 127 }
 128
 129 /* <summary> */
 130 /* Set the value of a leaf of the tag-tree. */
 131 /* </summary> */
 132 void tgt_setvalue(tgt_tree_t * tree, int leafno, int value)
 133 {
 134     tgt_node_t *node;
 135     node = &tree->nodes[leafno];
 136     while (node && node->value > value) {
 137         node->value = value;
 138         node = node->parent;
 139     }
 140 }
 141
 142 /* <summary> */
 143 /* Encode the value of a leaf of the tag-tree. */
 144 /* </summary> */
 145 void tgt_encode(tgt_tree_t * tree, int leafno, int threshold)
 146 {
 147     tgt_node_t *stk[31];
 148     tgt_node_t **stkptr;
 149     tgt_node_t *node;
 150     int low;
 151
 152     stkptr = stk;
 153     node = &tree->nodes[leafno];
 154     while (node->parent) {
 155         *stkptr++ = node;
 156         node = node->parent;
 157     }
 158
 159     low = 0;
 160     for (;;) {
 161         if (low > node->low) {
 162             node->low = low;
 163         } else {
 164             low = node->low;
 165         }
 166
 167         while (low < threshold) {
 168             if (low >= node->value) {
 169                 if (!node->known) {
 170                     bio_write(1, 1);
 171                     node->known = 1;
 172                 }
 173                 break;
 174             }
 175             bio_write(0, 1);
 176             ++low;
 177         }
 178
 179         node->low = low;
 180         if (stkptr == stk)
 181             break;
 182         node = *--stkptr;
 183     }
 184
 185 }
 186
 187 /* <summary> */
 188 /* Decode the value of a leaf of the tag-tree. */
 189 /* </summary> */
 190 int tgt_decode(tgt_tree_t * tree, int leafno, int threshold)
 191 {
 192     tgt_node_t *stk[31];
 193     tgt_node_t **stkptr;
 194     tgt_node_t *node;
 195     int low;
 196
 197     stkptr = stk;
 198     node = &tree->nodes[leafno];
 199     while (node->parent) {
 200         *stkptr++ = node;
 201         node = node->parent;
 202     }
 203
 204     low = 0;
 205     for (;;) {
 206         if (low > node->low) {
 207             node->low = low;
 208         } else {
 209             low = node->low;
 210         }
 211         while (low < threshold && low < node->value) {
 212             if (bio_read(1)) {
 213                 node->value = low;
 214             } else {
 215                 ++low;
 216             }
 217         }
 218         node->low = low;
 219         if (stkptr == stk) {
 220             break;
 221         }
 222         node = *--stkptr;
 223     }
 224
 225     return (node->value < threshold) ? 1 : 0;
 226 }