Subversion Repositories Kolibri OS

Rev

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

  1. /*
  2.  * Copyright (c) 2001-2003, David Janssens
  3.  * Copyright (c) 2002-2003, Yannick Verschueren
  4.  * Copyright (c) 2003-2005, Francois Devaux and Antonin Descampe
  5.  * Copyright (c) 2005, Hervé Drolon, FreeImage Team
  6.  * Copyright (c) 2002-2005, Communications and remote sensing Laboratory, Universite catholique de Louvain, Belgium
  7.  * All rights reserved.
  8.  *
  9.  * Redistribution and use in source and binary forms, with or without
  10.  * modification, are permitted provided that the following conditions
  11.  * are met:
  12.  * 1. Redistributions of source code must retain the above copyright
  13.  *    notice, this list of conditions and the following disclaimer.
  14.  * 2. Redistributions in binary form must reproduce the above copyright
  15.  *    notice, this list of conditions and the following disclaimer in the
  16.  *    documentation and/or other materials provided with the distribution.
  17.  *
  18.  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS `AS IS'
  19.  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  20.  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  21.  * ARE DISCLAIMED.  IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
  22.  * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
  23.  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
  24.  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
  25.  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
  26.  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  27.  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
  28.  * POSSIBILITY OF SUCH DAMAGE.
  29.  */
  30.  
  31. #include "opj_includes.h"
  32.  
  33. /*
  34. ==========================================================
  35.    Tag-tree coder interface
  36. ==========================================================
  37. */
  38. void tgt_tree_dump (FILE *fd, opj_tgt_tree_t * tree){
  39.         int nodesno;
  40.  
  41.         fprintf(fd, "TGT_TREE {\n");
  42.         fprintf(fd, "  numnodes: %d \n", tree->numnodes);      
  43.         fprintf(fd, "  numleafsh: %d, numleafsv: %d, numleafsz: %d,\n", tree->numleafsh, tree->numleafsv, tree->numleafsz);
  44.  
  45.         for (nodesno = 0; nodesno < tree->numnodes; nodesno++) {
  46.                 fprintf(fd, "tgt_node %d {\n", nodesno);
  47.                 fprintf(fd, "  value: %d \n", tree->nodes[nodesno].value);
  48.                 fprintf(fd, "  low: %d \n", tree->nodes[nodesno].low);
  49.                 fprintf(fd, "  known: %d \n", tree->nodes[nodesno].known);
  50.                 if (tree->nodes[nodesno].parent) {
  51.                         fprintf(fd, "  parent.value: %d \n", tree->nodes[nodesno].parent->value);
  52.                         fprintf(fd, "  parent.low: %d \n", tree->nodes[nodesno].parent->low);
  53.                         fprintf(fd, "  parent.known: %d \n", tree->nodes[nodesno].parent->known);
  54.                 }
  55.                 fprintf(fd, "}\n");
  56.  
  57.         }
  58.         fprintf(fd, "}\n");
  59.  
  60. }
  61.  
  62.  
  63. opj_tgt_tree_t *tgt_create(int numleafsh, int numleafsv, int numleafsz) {
  64.        
  65.         int nplh[32];
  66.         int nplv[32];
  67.         int nplz[32];
  68.         opj_tgt_node_t *node = NULL;
  69.         opj_tgt_node_t *parentnode = NULL;
  70.         opj_tgt_node_t *parentnode0 = NULL;
  71.         opj_tgt_tree_t *tree = NULL;
  72.         int i, j, k, p, p0;
  73.         int numlvls;
  74.         int n, z = 0;
  75.  
  76.         tree = (opj_tgt_tree_t *) opj_malloc(sizeof(opj_tgt_tree_t));
  77.         if(!tree)
  78.                 return NULL;
  79.         tree->numleafsh = numleafsh;
  80.         tree->numleafsv = numleafsv;
  81.         tree->numleafsz = numleafsz;
  82.  
  83.         numlvls = 0;
  84.         nplh[0] = numleafsh;
  85.         nplv[0] = numleafsv;
  86.         nplz[0] = numleafsz;
  87.         tree->numnodes = 0;
  88.         do {
  89.                 n = nplh[numlvls] * nplv[numlvls] * nplz[numlvls];
  90.                 nplh[numlvls + 1] = (nplh[numlvls] + 1) / 2;
  91.                 nplv[numlvls + 1] = (nplv[numlvls] + 1) / 2;
  92.                 nplz[numlvls + 1] = (nplz[numlvls] + 1) / 2;
  93.                 tree->numnodes += n;
  94.                 ++numlvls;
  95.         } while (n > 1);
  96.  
  97.         if (tree->numnodes == 0) {
  98.                 opj_free(tree);
  99.                 return NULL;
  100.         }
  101.  
  102.         tree->nodes = (opj_tgt_node_t *) opj_malloc(tree->numnodes * sizeof(opj_tgt_node_t));
  103.         if(!tree->nodes) {
  104.                 opj_free(tree);
  105.                 return NULL;
  106.         }
  107.  
  108.         node = tree->nodes;
  109.         parentnode = &tree->nodes[tree->numleafsh * tree->numleafsv * tree->numleafsz];
  110.         parentnode0 = parentnode;
  111.                
  112.         p = tree->numleafsh * tree->numleafsv * tree->numleafsz;
  113.         p0 = p;
  114.         n = 0;
  115.         //fprintf(stdout,"\nH %d V %d Z %d numlvls %d nodes %d\n",tree->numleafsh,tree->numleafsv,tree->numleafsz,numlvls,tree->numnodes);
  116.         for (i = 0; i < numlvls - 1; ++i) {
  117.                 for (j = 0; j < nplv[i]; ++j) {
  118.                         k = nplh[i]*nplz[i];
  119.                         while (--k >= 0) {
  120.                                 node->parent = parentnode;              //fprintf(stdout,"node[%d].parent = node[%d]\n",n,p);
  121.                                 ++node; ++n;           
  122.                                 if (--k >= 0 && n < p) {
  123.                                         node->parent = parentnode;      //fprintf(stdout,"node[%d].parent = node[%d]\n",n,p);
  124.                                         ++node; ++n;   
  125.                                 }
  126.                                 if (nplz[i] != 1){ //2D operation vs 3D operation
  127.                                         if (--k >= 0 && n < p) {
  128.                                                 node->parent = parentnode;      //fprintf(stdout,"node[%d].parent = node[%d]\n",n,p);
  129.                                                 ++node; ++n;
  130.                                         }
  131.                                         if (--k >= 0 && n < p) {
  132.                                                 node->parent = parentnode;      //fprintf(stdout,"node[%d].parent = node[%d]\n",n,p);
  133.                                                 ++node; ++n;
  134.                                         }
  135.                                 }
  136.                                 ++parentnode; ++p;
  137.                         }
  138.                         if ((j & 1) || j == nplv[i] - 1) {
  139.                                 parentnode0 = parentnode;                       p0 = p;         //fprintf(stdout,"parent = node[%d] \n",p);
  140.                         } else {
  141.                                 parentnode = parentnode0;                       p = p0;         //fprintf(stdout,"parent = node[%d] \n",p);
  142.                                 parentnode0 += nplh[i]*nplz[i];         p0 += nplh[i]*nplz[i];
  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. }
  257.