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 }