Subversion Repositories Kolibri OS

Rev

Go to most recent revision | Blame | Last modification | View Log | RSS feed

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